]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | /* SPDX-License-Identifier: BSD-3-Clause |
2 | * Copyright(c) 2010-2014 Intel Corporation | |
7c673cae FG |
3 | */ |
4 | #include <string.h> | |
5 | #include <stdint.h> | |
6 | #include <errno.h> | |
7 | #include <stdarg.h> | |
8 | #include <stdio.h> | |
7c673cae FG |
9 | #include <sys/queue.h> |
10 | ||
11 | #include <rte_log.h> | |
12 | #include <rte_branch_prediction.h> | |
13 | #include <rte_common.h> | |
14 | #include <rte_memory.h> | |
15 | #include <rte_malloc.h> | |
7c673cae FG |
16 | #include <rte_memcpy.h> |
17 | #include <rte_eal.h> | |
18 | #include <rte_eal_memconfig.h> | |
19 | #include <rte_per_lcore.h> | |
20 | #include <rte_string_fns.h> | |
21 | #include <rte_errno.h> | |
22 | #include <rte_rwlock.h> | |
23 | #include <rte_spinlock.h> | |
9f95a23c TL |
24 | #include <rte_hash.h> |
25 | #include <assert.h> | |
26 | #include <rte_jhash.h> | |
7c673cae FG |
27 | |
28 | #include "rte_lpm6.h" | |
29 | ||
30 | #define RTE_LPM6_TBL24_NUM_ENTRIES (1 << 24) | |
31 | #define RTE_LPM6_TBL8_GROUP_NUM_ENTRIES 256 | |
32 | #define RTE_LPM6_TBL8_MAX_NUM_GROUPS (1 << 21) | |
33 | ||
34 | #define RTE_LPM6_VALID_EXT_ENTRY_BITMASK 0xA0000000 | |
35 | #define RTE_LPM6_LOOKUP_SUCCESS 0x20000000 | |
36 | #define RTE_LPM6_TBL8_BITMASK 0x001FFFFF | |
37 | ||
38 | #define ADD_FIRST_BYTE 3 | |
39 | #define LOOKUP_FIRST_BYTE 4 | |
40 | #define BYTE_SIZE 8 | |
41 | #define BYTES2_SIZE 16 | |
42 | ||
9f95a23c TL |
43 | #define RULE_HASH_TABLE_EXTRA_SPACE 64 |
44 | #define TBL24_IND UINT32_MAX | |
45 | ||
7c673cae FG |
46 | #define lpm6_tbl8_gindex next_hop |
47 | ||
48 | /** Flags for setting an entry as valid/invalid. */ | |
49 | enum valid_flag { | |
50 | INVALID = 0, | |
51 | VALID | |
52 | }; | |
53 | ||
54 | TAILQ_HEAD(rte_lpm6_list, rte_tailq_entry); | |
55 | ||
56 | static struct rte_tailq_elem rte_lpm6_tailq = { | |
57 | .name = "RTE_LPM6", | |
58 | }; | |
59 | EAL_REGISTER_TAILQ(rte_lpm6_tailq) | |
60 | ||
61 | /** Tbl entry structure. It is the same for both tbl24 and tbl8 */ | |
62 | struct rte_lpm6_tbl_entry { | |
63 | uint32_t next_hop: 21; /**< Next hop / next table to be checked. */ | |
64 | uint32_t depth :8; /**< Rule depth. */ | |
65 | ||
66 | /* Flags. */ | |
67 | uint32_t valid :1; /**< Validation flag. */ | |
68 | uint32_t valid_group :1; /**< Group validation flag. */ | |
69 | uint32_t ext_entry :1; /**< External entry. */ | |
70 | }; | |
71 | ||
72 | /** Rules tbl entry structure. */ | |
73 | struct rte_lpm6_rule { | |
74 | uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */ | |
11fdf7f2 | 75 | uint32_t next_hop; /**< Rule next hop. */ |
7c673cae FG |
76 | uint8_t depth; /**< Rule depth. */ |
77 | }; | |
78 | ||
9f95a23c TL |
79 | /** Rules tbl entry key. */ |
80 | struct rte_lpm6_rule_key { | |
81 | uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */ | |
82 | uint8_t depth; /**< Rule depth. */ | |
83 | }; | |
84 | ||
85 | /* Header of tbl8 */ | |
86 | struct rte_lpm_tbl8_hdr { | |
87 | uint32_t owner_tbl_ind; /**< owner table: TBL24_IND if owner is tbl24, | |
88 | * otherwise index of tbl8 | |
89 | */ | |
90 | uint32_t owner_entry_ind; /**< index of the owner table entry where | |
91 | * pointer to the tbl8 is stored | |
92 | */ | |
93 | uint32_t ref_cnt; /**< table reference counter */ | |
94 | }; | |
95 | ||
7c673cae FG |
96 | /** LPM6 structure. */ |
97 | struct rte_lpm6 { | |
98 | /* LPM metadata. */ | |
99 | char name[RTE_LPM6_NAMESIZE]; /**< Name of the lpm. */ | |
100 | uint32_t max_rules; /**< Max number of rules. */ | |
101 | uint32_t used_rules; /**< Used rules so far. */ | |
102 | uint32_t number_tbl8s; /**< Number of tbl8s to allocate. */ | |
7c673cae FG |
103 | |
104 | /* LPM Tables. */ | |
9f95a23c | 105 | struct rte_hash *rules_tbl; /**< LPM rules. */ |
7c673cae FG |
106 | struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES] |
107 | __rte_cache_aligned; /**< LPM tbl24 table. */ | |
9f95a23c TL |
108 | |
109 | uint32_t *tbl8_pool; /**< pool of indexes of free tbl8s */ | |
110 | uint32_t tbl8_pool_pos; /**< current position in the tbl8 pool */ | |
111 | ||
112 | struct rte_lpm_tbl8_hdr *tbl8_hdrs; /* array of tbl8 headers */ | |
113 | ||
7c673cae FG |
114 | struct rte_lpm6_tbl_entry tbl8[0] |
115 | __rte_cache_aligned; /**< LPM tbl8 table. */ | |
116 | }; | |
117 | ||
118 | /* | |
119 | * Takes an array of uint8_t (IPv6 address) and masks it using the depth. | |
120 | * It leaves untouched one bit per unit in the depth variable | |
121 | * and set the rest to 0. | |
122 | */ | |
123 | static inline void | |
9f95a23c | 124 | ip6_mask_addr(uint8_t *ip, uint8_t depth) |
7c673cae | 125 | { |
9f95a23c TL |
126 | int16_t part_depth, mask; |
127 | int i; | |
7c673cae | 128 | |
9f95a23c | 129 | part_depth = depth; |
7c673cae | 130 | |
9f95a23c TL |
131 | for (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) { |
132 | if (part_depth < BYTE_SIZE && part_depth >= 0) { | |
133 | mask = (uint16_t)(~(UINT8_MAX >> part_depth)); | |
134 | ip[i] = (uint8_t)(ip[i] & mask); | |
135 | } else if (part_depth < 0) | |
136 | ip[i] = 0; | |
137 | ||
138 | part_depth -= BYTE_SIZE; | |
139 | } | |
140 | } | |
141 | ||
142 | /* copy ipv6 address */ | |
143 | static inline void | |
144 | ip6_copy_addr(uint8_t *dst, const uint8_t *src) | |
145 | { | |
146 | rte_memcpy(dst, src, RTE_LPM6_IPV6_ADDR_SIZE); | |
147 | } | |
148 | ||
149 | /* | |
150 | * LPM6 rule hash function | |
151 | * | |
152 | * It's used as a hash function for the rte_hash | |
153 | * containing rules | |
154 | */ | |
155 | static inline uint32_t | |
156 | rule_hash(const void *data, __rte_unused uint32_t data_len, | |
157 | uint32_t init_val) | |
158 | { | |
159 | return rte_jhash(data, sizeof(struct rte_lpm6_rule_key), init_val); | |
160 | } | |
161 | ||
162 | /* | |
163 | * Init pool of free tbl8 indexes | |
164 | */ | |
165 | static void | |
166 | tbl8_pool_init(struct rte_lpm6 *lpm) | |
167 | { | |
168 | uint32_t i; | |
169 | ||
170 | /* put entire range of indexes to the tbl8 pool */ | |
171 | for (i = 0; i < lpm->number_tbl8s; i++) | |
172 | lpm->tbl8_pool[i] = i; | |
173 | ||
174 | lpm->tbl8_pool_pos = 0; | |
175 | } | |
176 | ||
177 | /* | |
178 | * Get an index of a free tbl8 from the pool | |
179 | */ | |
180 | static inline uint32_t | |
181 | tbl8_get(struct rte_lpm6 *lpm, uint32_t *tbl8_ind) | |
182 | { | |
183 | if (lpm->tbl8_pool_pos == lpm->number_tbl8s) | |
184 | /* no more free tbl8 */ | |
185 | return -ENOSPC; | |
186 | ||
187 | /* next index */ | |
188 | *tbl8_ind = lpm->tbl8_pool[lpm->tbl8_pool_pos++]; | |
189 | return 0; | |
190 | } | |
191 | ||
192 | /* | |
193 | * Put an index of a free tbl8 back to the pool | |
194 | */ | |
195 | static inline uint32_t | |
196 | tbl8_put(struct rte_lpm6 *lpm, uint32_t tbl8_ind) | |
197 | { | |
198 | if (lpm->tbl8_pool_pos == 0) | |
199 | /* pool is full */ | |
200 | return -ENOSPC; | |
201 | ||
202 | lpm->tbl8_pool[--lpm->tbl8_pool_pos] = tbl8_ind; | |
203 | return 0; | |
204 | } | |
205 | ||
206 | /* | |
207 | * Returns number of tbl8s available in the pool | |
208 | */ | |
209 | static inline uint32_t | |
210 | tbl8_available(struct rte_lpm6 *lpm) | |
211 | { | |
212 | return lpm->number_tbl8s - lpm->tbl8_pool_pos; | |
213 | } | |
214 | ||
215 | /* | |
216 | * Init a rule key. | |
217 | * note that ip must be already masked | |
218 | */ | |
219 | static inline void | |
220 | rule_key_init(struct rte_lpm6_rule_key *key, uint8_t *ip, uint8_t depth) | |
221 | { | |
222 | ip6_copy_addr(key->ip, ip); | |
223 | key->depth = depth; | |
224 | } | |
225 | ||
226 | /* | |
227 | * Rebuild the entire LPM tree by reinserting all rules | |
228 | */ | |
229 | static void | |
230 | rebuild_lpm(struct rte_lpm6 *lpm) | |
231 | { | |
232 | uint64_t next_hop; | |
233 | struct rte_lpm6_rule_key *rule_key; | |
234 | uint32_t iter = 0; | |
235 | ||
236 | while (rte_hash_iterate(lpm->rules_tbl, (void *) &rule_key, | |
237 | (void **) &next_hop, &iter) >= 0) | |
238 | rte_lpm6_add(lpm, rule_key->ip, rule_key->depth, | |
239 | (uint32_t) next_hop); | |
7c673cae FG |
240 | } |
241 | ||
242 | /* | |
243 | * Allocates memory for LPM object | |
244 | */ | |
245 | struct rte_lpm6 * | |
246 | rte_lpm6_create(const char *name, int socket_id, | |
247 | const struct rte_lpm6_config *config) | |
248 | { | |
249 | char mem_name[RTE_LPM6_NAMESIZE]; | |
250 | struct rte_lpm6 *lpm = NULL; | |
251 | struct rte_tailq_entry *te; | |
9f95a23c | 252 | uint64_t mem_size; |
7c673cae | 253 | struct rte_lpm6_list *lpm_list; |
9f95a23c TL |
254 | struct rte_hash *rules_tbl = NULL; |
255 | uint32_t *tbl8_pool = NULL; | |
256 | struct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL; | |
7c673cae FG |
257 | |
258 | lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list); | |
259 | ||
260 | RTE_BUILD_BUG_ON(sizeof(struct rte_lpm6_tbl_entry) != sizeof(uint32_t)); | |
261 | ||
262 | /* Check user arguments. */ | |
263 | if ((name == NULL) || (socket_id < -1) || (config == NULL) || | |
264 | (config->max_rules == 0) || | |
265 | config->number_tbl8s > RTE_LPM6_TBL8_MAX_NUM_GROUPS) { | |
266 | rte_errno = EINVAL; | |
267 | return NULL; | |
268 | } | |
269 | ||
9f95a23c TL |
270 | /* create rules hash table */ |
271 | snprintf(mem_name, sizeof(mem_name), "LRH_%s", name); | |
272 | struct rte_hash_parameters rule_hash_tbl_params = { | |
273 | .entries = config->max_rules * 1.2 + | |
274 | RULE_HASH_TABLE_EXTRA_SPACE, | |
275 | .key_len = sizeof(struct rte_lpm6_rule_key), | |
276 | .hash_func = rule_hash, | |
277 | .hash_func_init_val = 0, | |
278 | .name = mem_name, | |
279 | .reserved = 0, | |
280 | .socket_id = socket_id, | |
281 | .extra_flag = 0 | |
282 | }; | |
283 | ||
284 | rules_tbl = rte_hash_create(&rule_hash_tbl_params); | |
285 | if (rules_tbl == NULL) { | |
286 | RTE_LOG(ERR, LPM, "LPM rules hash table allocation failed: %s (%d)", | |
287 | rte_strerror(rte_errno), rte_errno); | |
288 | goto fail_wo_unlock; | |
289 | } | |
290 | ||
291 | /* allocate tbl8 indexes pool */ | |
292 | tbl8_pool = rte_malloc(NULL, | |
293 | sizeof(uint32_t) * config->number_tbl8s, | |
294 | RTE_CACHE_LINE_SIZE); | |
295 | if (tbl8_pool == NULL) { | |
296 | RTE_LOG(ERR, LPM, "LPM tbl8 pool allocation failed: %s (%d)", | |
297 | rte_strerror(rte_errno), rte_errno); | |
298 | rte_errno = ENOMEM; | |
299 | goto fail_wo_unlock; | |
300 | } | |
301 | ||
302 | /* allocate tbl8 headers */ | |
303 | tbl8_hdrs = rte_malloc(NULL, | |
304 | sizeof(struct rte_lpm_tbl8_hdr) * config->number_tbl8s, | |
305 | RTE_CACHE_LINE_SIZE); | |
306 | if (tbl8_hdrs == NULL) { | |
307 | RTE_LOG(ERR, LPM, "LPM tbl8 headers allocation failed: %s (%d)", | |
308 | rte_strerror(rte_errno), rte_errno); | |
309 | rte_errno = ENOMEM; | |
310 | goto fail_wo_unlock; | |
311 | } | |
312 | ||
7c673cae FG |
313 | snprintf(mem_name, sizeof(mem_name), "LPM_%s", name); |
314 | ||
315 | /* Determine the amount of memory to allocate. */ | |
316 | mem_size = sizeof(*lpm) + (sizeof(lpm->tbl8[0]) * | |
317 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s); | |
7c673cae FG |
318 | |
319 | rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); | |
320 | ||
321 | /* Guarantee there's no existing */ | |
322 | TAILQ_FOREACH(te, lpm_list, next) { | |
323 | lpm = (struct rte_lpm6 *) te->data; | |
324 | if (strncmp(name, lpm->name, RTE_LPM6_NAMESIZE) == 0) | |
325 | break; | |
326 | } | |
327 | lpm = NULL; | |
328 | if (te != NULL) { | |
329 | rte_errno = EEXIST; | |
9f95a23c | 330 | goto fail; |
7c673cae FG |
331 | } |
332 | ||
333 | /* allocate tailq entry */ | |
334 | te = rte_zmalloc("LPM6_TAILQ_ENTRY", sizeof(*te), 0); | |
335 | if (te == NULL) { | |
336 | RTE_LOG(ERR, LPM, "Failed to allocate tailq entry!\n"); | |
11fdf7f2 | 337 | rte_errno = ENOMEM; |
9f95a23c | 338 | goto fail; |
7c673cae FG |
339 | } |
340 | ||
341 | /* Allocate memory to store the LPM data structures. */ | |
11fdf7f2 | 342 | lpm = rte_zmalloc_socket(mem_name, (size_t)mem_size, |
7c673cae FG |
343 | RTE_CACHE_LINE_SIZE, socket_id); |
344 | ||
345 | if (lpm == NULL) { | |
346 | RTE_LOG(ERR, LPM, "LPM memory allocation failed\n"); | |
347 | rte_free(te); | |
11fdf7f2 | 348 | rte_errno = ENOMEM; |
9f95a23c | 349 | goto fail; |
7c673cae FG |
350 | } |
351 | ||
352 | /* Save user arguments. */ | |
353 | lpm->max_rules = config->max_rules; | |
354 | lpm->number_tbl8s = config->number_tbl8s; | |
9f95a23c TL |
355 | strlcpy(lpm->name, name, sizeof(lpm->name)); |
356 | lpm->rules_tbl = rules_tbl; | |
357 | lpm->tbl8_pool = tbl8_pool; | |
358 | lpm->tbl8_hdrs = tbl8_hdrs; | |
359 | ||
360 | /* init the stack */ | |
361 | tbl8_pool_init(lpm); | |
7c673cae FG |
362 | |
363 | te->data = (void *) lpm; | |
364 | ||
365 | TAILQ_INSERT_TAIL(lpm_list, te, next); | |
9f95a23c TL |
366 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); |
367 | return lpm; | |
7c673cae | 368 | |
9f95a23c | 369 | fail: |
7c673cae FG |
370 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); |
371 | ||
9f95a23c TL |
372 | fail_wo_unlock: |
373 | rte_free(tbl8_hdrs); | |
374 | rte_free(tbl8_pool); | |
375 | rte_hash_free(rules_tbl); | |
376 | ||
377 | return NULL; | |
7c673cae FG |
378 | } |
379 | ||
380 | /* | |
381 | * Find an existing lpm table and return a pointer to it. | |
382 | */ | |
383 | struct rte_lpm6 * | |
384 | rte_lpm6_find_existing(const char *name) | |
385 | { | |
386 | struct rte_lpm6 *l = NULL; | |
387 | struct rte_tailq_entry *te; | |
388 | struct rte_lpm6_list *lpm_list; | |
389 | ||
390 | lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list); | |
391 | ||
392 | rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); | |
393 | TAILQ_FOREACH(te, lpm_list, next) { | |
394 | l = (struct rte_lpm6 *) te->data; | |
395 | if (strncmp(name, l->name, RTE_LPM6_NAMESIZE) == 0) | |
396 | break; | |
397 | } | |
398 | rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); | |
399 | ||
400 | if (te == NULL) { | |
401 | rte_errno = ENOENT; | |
402 | return NULL; | |
403 | } | |
404 | ||
405 | return l; | |
406 | } | |
407 | ||
408 | /* | |
409 | * Deallocates memory for given LPM table. | |
410 | */ | |
411 | void | |
412 | rte_lpm6_free(struct rte_lpm6 *lpm) | |
413 | { | |
414 | struct rte_lpm6_list *lpm_list; | |
415 | struct rte_tailq_entry *te; | |
416 | ||
417 | /* Check user arguments. */ | |
418 | if (lpm == NULL) | |
419 | return; | |
420 | ||
421 | lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list); | |
422 | ||
423 | rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); | |
424 | ||
425 | /* find our tailq entry */ | |
426 | TAILQ_FOREACH(te, lpm_list, next) { | |
427 | if (te->data == (void *) lpm) | |
428 | break; | |
429 | } | |
430 | ||
431 | if (te != NULL) | |
432 | TAILQ_REMOVE(lpm_list, te, next); | |
433 | ||
434 | rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); | |
435 | ||
9f95a23c TL |
436 | rte_free(lpm->tbl8_hdrs); |
437 | rte_free(lpm->tbl8_pool); | |
438 | rte_hash_free(lpm->rules_tbl); | |
7c673cae FG |
439 | rte_free(lpm); |
440 | rte_free(te); | |
441 | } | |
442 | ||
9f95a23c TL |
443 | /* Find a rule */ |
444 | static inline int | |
445 | rule_find_with_key(struct rte_lpm6 *lpm, | |
446 | const struct rte_lpm6_rule_key *rule_key, | |
447 | uint32_t *next_hop) | |
448 | { | |
449 | uint64_t hash_val; | |
450 | int ret; | |
451 | ||
452 | /* lookup for a rule */ | |
453 | ret = rte_hash_lookup_data(lpm->rules_tbl, (const void *) rule_key, | |
454 | (void **) &hash_val); | |
455 | if (ret >= 0) { | |
456 | *next_hop = (uint32_t) hash_val; | |
457 | return 1; | |
458 | } | |
459 | ||
460 | return 0; | |
461 | } | |
462 | ||
463 | /* Find a rule */ | |
464 | static int | |
465 | rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, | |
466 | uint32_t *next_hop) | |
467 | { | |
468 | struct rte_lpm6_rule_key rule_key; | |
469 | ||
470 | /* init a rule key */ | |
471 | rule_key_init(&rule_key, ip, depth); | |
472 | ||
473 | return rule_find_with_key(lpm, &rule_key, next_hop); | |
474 | } | |
475 | ||
7c673cae FG |
476 | /* |
477 | * Checks if a rule already exists in the rules table and updates | |
478 | * the nexthop if so. Otherwise it adds a new rule if enough space is available. | |
9f95a23c TL |
479 | * |
480 | * Returns: | |
481 | * 0 - next hop of existed rule is updated | |
482 | * 1 - new rule successfully added | |
483 | * <0 - error | |
7c673cae | 484 | */ |
9f95a23c TL |
485 | static inline int |
486 | rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop) | |
7c673cae | 487 | { |
9f95a23c TL |
488 | int ret, rule_exist; |
489 | struct rte_lpm6_rule_key rule_key; | |
490 | uint32_t unused; | |
7c673cae | 491 | |
9f95a23c TL |
492 | /* init a rule key */ |
493 | rule_key_init(&rule_key, ip, depth); | |
7c673cae | 494 | |
9f95a23c TL |
495 | /* Scan through rule list to see if rule already exists. */ |
496 | rule_exist = rule_find_with_key(lpm, &rule_key, &unused); | |
7c673cae FG |
497 | |
498 | /* | |
499 | * If rule does not exist check if there is space to add a new rule to | |
500 | * this rule group. If there is no space return error. | |
501 | */ | |
9f95a23c | 502 | if (!rule_exist && lpm->used_rules == lpm->max_rules) |
7c673cae | 503 | return -ENOSPC; |
7c673cae | 504 | |
9f95a23c TL |
505 | /* add the rule or update rules next hop */ |
506 | ret = rte_hash_add_key_data(lpm->rules_tbl, &rule_key, | |
507 | (void *)(uintptr_t) next_hop); | |
508 | if (ret < 0) | |
509 | return ret; | |
7c673cae FG |
510 | |
511 | /* Increment the used rules counter for this rule group. */ | |
9f95a23c TL |
512 | if (!rule_exist) { |
513 | lpm->used_rules++; | |
514 | return 1; | |
515 | } | |
7c673cae | 516 | |
9f95a23c | 517 | return 0; |
7c673cae FG |
518 | } |
519 | ||
520 | /* | |
521 | * Function that expands a rule across the data structure when a less-generic | |
522 | * one has been added before. It assures that every possible combination of bits | |
523 | * in the IP address returns a match. | |
524 | */ | |
525 | static void | |
9f95a23c TL |
526 | expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t old_depth, |
527 | uint8_t new_depth, uint32_t next_hop, uint8_t valid) | |
7c673cae FG |
528 | { |
529 | uint32_t tbl8_group_end, tbl8_gindex_next, j; | |
530 | ||
531 | tbl8_group_end = tbl8_gindex + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; | |
532 | ||
533 | struct rte_lpm6_tbl_entry new_tbl8_entry = { | |
9f95a23c TL |
534 | .valid = valid, |
535 | .valid_group = valid, | |
536 | .depth = new_depth, | |
7c673cae FG |
537 | .next_hop = next_hop, |
538 | .ext_entry = 0, | |
539 | }; | |
540 | ||
541 | for (j = tbl8_gindex; j < tbl8_group_end; j++) { | |
542 | if (!lpm->tbl8[j].valid || (lpm->tbl8[j].ext_entry == 0 | |
9f95a23c | 543 | && lpm->tbl8[j].depth <= old_depth)) { |
7c673cae FG |
544 | |
545 | lpm->tbl8[j] = new_tbl8_entry; | |
546 | ||
547 | } else if (lpm->tbl8[j].ext_entry == 1) { | |
548 | ||
549 | tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex | |
550 | * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; | |
9f95a23c TL |
551 | expand_rule(lpm, tbl8_gindex_next, old_depth, new_depth, |
552 | next_hop, valid); | |
7c673cae FG |
553 | } |
554 | } | |
555 | } | |
556 | ||
9f95a23c TL |
557 | /* |
558 | * Init a tbl8 header | |
559 | */ | |
560 | static inline void | |
561 | init_tbl8_header(struct rte_lpm6 *lpm, uint32_t tbl_ind, | |
562 | uint32_t owner_tbl_ind, uint32_t owner_entry_ind) | |
563 | { | |
564 | struct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind]; | |
565 | tbl_hdr->owner_tbl_ind = owner_tbl_ind; | |
566 | tbl_hdr->owner_entry_ind = owner_entry_ind; | |
567 | tbl_hdr->ref_cnt = 0; | |
568 | } | |
569 | ||
570 | /* | |
571 | * Calculate index to the table based on the number and position | |
572 | * of the bytes being inspected in this step. | |
573 | */ | |
574 | static uint32_t | |
575 | get_bitshift(const uint8_t *ip, uint8_t first_byte, uint8_t bytes) | |
576 | { | |
577 | uint32_t entry_ind, i; | |
578 | int8_t bitshift; | |
579 | ||
580 | entry_ind = 0; | |
581 | for (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) { | |
582 | bitshift = (int8_t)((bytes - i)*BYTE_SIZE); | |
583 | ||
584 | if (bitshift < 0) | |
585 | bitshift = 0; | |
586 | entry_ind = entry_ind | ip[i-1] << bitshift; | |
587 | } | |
588 | ||
589 | return entry_ind; | |
590 | } | |
591 | ||
592 | /* | |
593 | * Simulate adding a new route to the LPM counting number | |
594 | * of new tables that will be needed | |
595 | * | |
596 | * It returns 0 on success, or 1 if | |
597 | * the process needs to be continued by calling the function again. | |
598 | */ | |
599 | static inline int | |
600 | simulate_add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl, | |
601 | struct rte_lpm6_tbl_entry **next_tbl, const uint8_t *ip, | |
602 | uint8_t bytes, uint8_t first_byte, uint8_t depth, | |
603 | uint32_t *need_tbl_nb) | |
604 | { | |
605 | uint32_t entry_ind; | |
606 | uint8_t bits_covered; | |
607 | uint32_t next_tbl_ind; | |
608 | ||
609 | /* | |
610 | * Calculate index to the table based on the number and position | |
611 | * of the bytes being inspected in this step. | |
612 | */ | |
613 | entry_ind = get_bitshift(ip, first_byte, bytes); | |
614 | ||
615 | /* Number of bits covered in this step */ | |
616 | bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE); | |
617 | ||
618 | if (depth <= bits_covered) { | |
619 | *need_tbl_nb = 0; | |
620 | return 0; | |
621 | } | |
622 | ||
623 | if (tbl[entry_ind].valid == 0 || tbl[entry_ind].ext_entry == 0) { | |
624 | /* from this point on a new table is needed on each level | |
625 | * that is not covered yet | |
626 | */ | |
627 | depth -= bits_covered; | |
628 | uint32_t cnt = depth >> 3; /* depth / BYTE_SIZE */ | |
629 | if (depth & 7) /* 0b00000111 */ | |
630 | /* if depth % 8 > 0 then one more table is needed | |
631 | * for those last bits | |
632 | */ | |
633 | cnt++; | |
634 | ||
635 | *need_tbl_nb = cnt; | |
636 | return 0; | |
637 | } | |
638 | ||
639 | next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex; | |
640 | *next_tbl = &(lpm->tbl8[next_tbl_ind * | |
641 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]); | |
642 | *need_tbl_nb = 0; | |
643 | return 1; | |
644 | } | |
645 | ||
7c673cae FG |
646 | /* |
647 | * Partially adds a new route to the data structure (tbl24+tbl8s). | |
648 | * It returns 0 on success, a negative number on failure, or 1 if | |
649 | * the process needs to be continued by calling the function again. | |
650 | */ | |
651 | static inline int | |
652 | add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl, | |
9f95a23c TL |
653 | uint32_t tbl_ind, struct rte_lpm6_tbl_entry **next_tbl, |
654 | uint32_t *next_tbl_ind, uint8_t *ip, uint8_t bytes, | |
655 | uint8_t first_byte, uint8_t depth, uint32_t next_hop, | |
656 | uint8_t is_new_rule) | |
7c673cae | 657 | { |
9f95a23c TL |
658 | uint32_t entry_ind, tbl_range, tbl8_group_start, tbl8_group_end, i; |
659 | uint32_t tbl8_gindex; | |
7c673cae | 660 | uint8_t bits_covered; |
9f95a23c | 661 | int ret; |
7c673cae FG |
662 | |
663 | /* | |
664 | * Calculate index to the table based on the number and position | |
665 | * of the bytes being inspected in this step. | |
666 | */ | |
9f95a23c | 667 | entry_ind = get_bitshift(ip, first_byte, bytes); |
7c673cae FG |
668 | |
669 | /* Number of bits covered in this step */ | |
670 | bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE); | |
671 | ||
672 | /* | |
673 | * If depth if smaller than this number (ie this is the last step) | |
674 | * expand the rule across the relevant positions in the table. | |
675 | */ | |
676 | if (depth <= bits_covered) { | |
677 | tbl_range = 1 << (bits_covered - depth); | |
678 | ||
9f95a23c | 679 | for (i = entry_ind; i < (entry_ind + tbl_range); i++) { |
7c673cae FG |
680 | if (!tbl[i].valid || (tbl[i].ext_entry == 0 && |
681 | tbl[i].depth <= depth)) { | |
682 | ||
683 | struct rte_lpm6_tbl_entry new_tbl_entry = { | |
684 | .next_hop = next_hop, | |
685 | .depth = depth, | |
686 | .valid = VALID, | |
687 | .valid_group = VALID, | |
688 | .ext_entry = 0, | |
689 | }; | |
690 | ||
691 | tbl[i] = new_tbl_entry; | |
692 | ||
693 | } else if (tbl[i].ext_entry == 1) { | |
694 | ||
695 | /* | |
696 | * If tbl entry is valid and extended calculate the index | |
697 | * into next tbl8 and expand the rule across the data structure. | |
698 | */ | |
699 | tbl8_gindex = tbl[i].lpm6_tbl8_gindex * | |
700 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; | |
9f95a23c TL |
701 | expand_rule(lpm, tbl8_gindex, depth, depth, |
702 | next_hop, VALID); | |
7c673cae FG |
703 | } |
704 | } | |
705 | ||
9f95a23c TL |
706 | /* update tbl8 rule reference counter */ |
707 | if (tbl_ind != TBL24_IND && is_new_rule) | |
708 | lpm->tbl8_hdrs[tbl_ind].ref_cnt++; | |
709 | ||
7c673cae FG |
710 | return 0; |
711 | } | |
712 | /* | |
713 | * If this is not the last step just fill one position | |
714 | * and calculate the index to the next table. | |
715 | */ | |
716 | else { | |
717 | /* If it's invalid a new tbl8 is needed */ | |
9f95a23c TL |
718 | if (!tbl[entry_ind].valid) { |
719 | /* get a new table */ | |
720 | ret = tbl8_get(lpm, &tbl8_gindex); | |
721 | if (ret != 0) | |
7c673cae FG |
722 | return -ENOSPC; |
723 | ||
9f95a23c TL |
724 | /* invalidate all new tbl8 entries */ |
725 | tbl8_group_start = tbl8_gindex * | |
726 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; | |
727 | memset(&lpm->tbl8[tbl8_group_start], 0, | |
728 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES); | |
729 | ||
730 | /* init the new table's header: | |
731 | * save the reference to the owner table | |
732 | */ | |
733 | init_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind); | |
734 | ||
735 | /* reference to a new tbl8 */ | |
7c673cae FG |
736 | struct rte_lpm6_tbl_entry new_tbl_entry = { |
737 | .lpm6_tbl8_gindex = tbl8_gindex, | |
738 | .depth = 0, | |
739 | .valid = VALID, | |
740 | .valid_group = VALID, | |
741 | .ext_entry = 1, | |
742 | }; | |
743 | ||
9f95a23c TL |
744 | tbl[entry_ind] = new_tbl_entry; |
745 | ||
746 | /* update the current table's reference counter */ | |
747 | if (tbl_ind != TBL24_IND) | |
748 | lpm->tbl8_hdrs[tbl_ind].ref_cnt++; | |
7c673cae FG |
749 | } |
750 | /* | |
9f95a23c | 751 | * If it's valid but not extended the rule that was stored |
7c673cae FG |
752 | * here needs to be moved to the next table. |
753 | */ | |
9f95a23c TL |
754 | else if (tbl[entry_ind].ext_entry == 0) { |
755 | /* get a new tbl8 index */ | |
756 | ret = tbl8_get(lpm, &tbl8_gindex); | |
757 | if (ret != 0) | |
7c673cae FG |
758 | return -ENOSPC; |
759 | ||
760 | tbl8_group_start = tbl8_gindex * | |
761 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; | |
762 | tbl8_group_end = tbl8_group_start + | |
763 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; | |
764 | ||
9f95a23c TL |
765 | struct rte_lpm6_tbl_entry tbl_entry = { |
766 | .next_hop = tbl[entry_ind].next_hop, | |
767 | .depth = tbl[entry_ind].depth, | |
768 | .valid = VALID, | |
769 | .valid_group = VALID, | |
770 | .ext_entry = 0 | |
771 | }; | |
772 | ||
7c673cae | 773 | /* Populate new tbl8 with tbl value. */ |
9f95a23c TL |
774 | for (i = tbl8_group_start; i < tbl8_group_end; i++) |
775 | lpm->tbl8[i] = tbl_entry; | |
776 | ||
777 | /* init the new table's header: | |
778 | * save the reference to the owner table | |
779 | */ | |
780 | init_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind); | |
7c673cae FG |
781 | |
782 | /* | |
783 | * Update tbl entry to point to new tbl8 entry. Note: The | |
784 | * ext_flag and tbl8_index need to be updated simultaneously, | |
785 | * so assign whole structure in one go. | |
786 | */ | |
787 | struct rte_lpm6_tbl_entry new_tbl_entry = { | |
788 | .lpm6_tbl8_gindex = tbl8_gindex, | |
789 | .depth = 0, | |
790 | .valid = VALID, | |
791 | .valid_group = VALID, | |
792 | .ext_entry = 1, | |
793 | }; | |
794 | ||
9f95a23c TL |
795 | tbl[entry_ind] = new_tbl_entry; |
796 | ||
797 | /* update the current table's reference counter */ | |
798 | if (tbl_ind != TBL24_IND) | |
799 | lpm->tbl8_hdrs[tbl_ind].ref_cnt++; | |
7c673cae FG |
800 | } |
801 | ||
9f95a23c TL |
802 | *next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex; |
803 | *next_tbl = &(lpm->tbl8[*next_tbl_ind * | |
804 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]); | |
7c673cae FG |
805 | } |
806 | ||
807 | return 1; | |
808 | } | |
809 | ||
810 | /* | |
811 | * Add a route | |
812 | */ | |
813 | int | |
11fdf7f2 | 814 | rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, |
7c673cae | 815 | uint8_t next_hop) |
11fdf7f2 TL |
816 | { |
817 | return rte_lpm6_add_v1705(lpm, ip, depth, next_hop); | |
818 | } | |
819 | VERSION_SYMBOL(rte_lpm6_add, _v20, 2.0); | |
820 | ||
9f95a23c TL |
821 | |
822 | /* | |
823 | * Simulate adding a route to LPM | |
824 | * | |
825 | * Returns: | |
826 | * 0 on success | |
827 | * -ENOSPC not enought tbl8 left | |
828 | */ | |
829 | static int | |
830 | simulate_add(struct rte_lpm6 *lpm, const uint8_t *masked_ip, uint8_t depth) | |
831 | { | |
832 | struct rte_lpm6_tbl_entry *tbl; | |
833 | struct rte_lpm6_tbl_entry *tbl_next = NULL; | |
834 | int ret, i; | |
835 | ||
836 | /* number of new tables needed for a step */ | |
837 | uint32_t need_tbl_nb; | |
838 | /* total number of new tables needed */ | |
839 | uint32_t total_need_tbl_nb; | |
840 | ||
841 | /* Inspect the first three bytes through tbl24 on the first step. */ | |
842 | ret = simulate_add_step(lpm, lpm->tbl24, &tbl_next, masked_ip, | |
843 | ADD_FIRST_BYTE, 1, depth, &need_tbl_nb); | |
844 | total_need_tbl_nb = need_tbl_nb; | |
845 | /* | |
846 | * Inspect one by one the rest of the bytes until | |
847 | * the process is completed. | |
848 | */ | |
849 | for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && ret == 1; i++) { | |
850 | tbl = tbl_next; | |
851 | ret = simulate_add_step(lpm, tbl, &tbl_next, masked_ip, 1, | |
852 | (uint8_t)(i+1), depth, &need_tbl_nb); | |
853 | total_need_tbl_nb += need_tbl_nb; | |
854 | } | |
855 | ||
856 | if (tbl8_available(lpm) < total_need_tbl_nb) | |
857 | /* not enought tbl8 to add a rule */ | |
858 | return -ENOSPC; | |
859 | ||
860 | return 0; | |
861 | } | |
862 | ||
11fdf7f2 TL |
863 | int |
864 | rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, | |
865 | uint32_t next_hop) | |
7c673cae FG |
866 | { |
867 | struct rte_lpm6_tbl_entry *tbl; | |
11fdf7f2 | 868 | struct rte_lpm6_tbl_entry *tbl_next = NULL; |
9f95a23c TL |
869 | /* init to avoid compiler warning */ |
870 | uint32_t tbl_next_num = 123456; | |
7c673cae FG |
871 | int status; |
872 | uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE]; | |
873 | int i; | |
874 | ||
875 | /* Check user arguments. */ | |
876 | if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) | |
877 | return -EINVAL; | |
878 | ||
879 | /* Copy the IP and mask it to avoid modifying user's input data. */ | |
9f95a23c TL |
880 | ip6_copy_addr(masked_ip, ip); |
881 | ip6_mask_addr(masked_ip, depth); | |
7c673cae | 882 | |
9f95a23c TL |
883 | /* Simulate adding a new route */ |
884 | int ret = simulate_add(lpm, masked_ip, depth); | |
885 | if (ret < 0) | |
886 | return ret; | |
7c673cae | 887 | |
9f95a23c TL |
888 | /* Add the rule to the rule table. */ |
889 | int is_new_rule = rule_add(lpm, masked_ip, depth, next_hop); | |
7c673cae | 890 | /* If there is no space available for new rule return error. */ |
9f95a23c TL |
891 | if (is_new_rule < 0) |
892 | return is_new_rule; | |
7c673cae FG |
893 | |
894 | /* Inspect the first three bytes through tbl24 on the first step. */ | |
895 | tbl = lpm->tbl24; | |
9f95a23c TL |
896 | status = add_step(lpm, tbl, TBL24_IND, &tbl_next, &tbl_next_num, |
897 | masked_ip, ADD_FIRST_BYTE, 1, depth, next_hop, | |
898 | is_new_rule); | |
899 | assert(status >= 0); | |
7c673cae FG |
900 | |
901 | /* | |
902 | * Inspect one by one the rest of the bytes until | |
903 | * the process is completed. | |
904 | */ | |
905 | for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && status == 1; i++) { | |
906 | tbl = tbl_next; | |
9f95a23c TL |
907 | status = add_step(lpm, tbl, tbl_next_num, &tbl_next, |
908 | &tbl_next_num, masked_ip, 1, (uint8_t)(i+1), | |
909 | depth, next_hop, is_new_rule); | |
910 | assert(status >= 0); | |
7c673cae FG |
911 | } |
912 | ||
913 | return status; | |
914 | } | |
11fdf7f2 TL |
915 | BIND_DEFAULT_SYMBOL(rte_lpm6_add, _v1705, 17.05); |
916 | MAP_STATIC_SYMBOL(int rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, | |
917 | uint8_t depth, uint32_t next_hop), | |
918 | rte_lpm6_add_v1705); | |
7c673cae FG |
919 | |
920 | /* | |
921 | * Takes a pointer to a table entry and inspect one level. | |
922 | * The function returns 0 on lookup success, ENOENT if no match was found | |
923 | * or 1 if the process needs to be continued by calling the function again. | |
924 | */ | |
925 | static inline int | |
926 | lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl, | |
927 | const struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip, | |
11fdf7f2 | 928 | uint8_t first_byte, uint32_t *next_hop) |
7c673cae FG |
929 | { |
930 | uint32_t tbl8_index, tbl_entry; | |
931 | ||
932 | /* Take the integer value from the pointer. */ | |
933 | tbl_entry = *(const uint32_t *)tbl; | |
934 | ||
935 | /* If it is valid and extended we calculate the new pointer to return. */ | |
936 | if ((tbl_entry & RTE_LPM6_VALID_EXT_ENTRY_BITMASK) == | |
937 | RTE_LPM6_VALID_EXT_ENTRY_BITMASK) { | |
938 | ||
939 | tbl8_index = ip[first_byte-1] + | |
940 | ((tbl_entry & RTE_LPM6_TBL8_BITMASK) * | |
941 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES); | |
942 | ||
943 | *tbl_next = &lpm->tbl8[tbl8_index]; | |
944 | ||
945 | return 1; | |
946 | } else { | |
947 | /* If not extended then we can have a match. */ | |
11fdf7f2 | 948 | *next_hop = ((uint32_t)tbl_entry & RTE_LPM6_TBL8_BITMASK); |
7c673cae FG |
949 | return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT; |
950 | } | |
951 | } | |
952 | ||
953 | /* | |
954 | * Looks up an IP | |
955 | */ | |
956 | int | |
11fdf7f2 TL |
957 | rte_lpm6_lookup_v20(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop) |
958 | { | |
959 | uint32_t next_hop32 = 0; | |
960 | int32_t status; | |
961 | ||
962 | /* DEBUG: Check user input arguments. */ | |
963 | if (next_hop == NULL) | |
964 | return -EINVAL; | |
965 | ||
966 | status = rte_lpm6_lookup_v1705(lpm, ip, &next_hop32); | |
967 | if (status == 0) | |
968 | *next_hop = (uint8_t)next_hop32; | |
969 | ||
970 | return status; | |
971 | } | |
972 | VERSION_SYMBOL(rte_lpm6_lookup, _v20, 2.0); | |
973 | ||
974 | int | |
975 | rte_lpm6_lookup_v1705(const struct rte_lpm6 *lpm, uint8_t *ip, | |
976 | uint32_t *next_hop) | |
7c673cae FG |
977 | { |
978 | const struct rte_lpm6_tbl_entry *tbl; | |
979 | const struct rte_lpm6_tbl_entry *tbl_next = NULL; | |
980 | int status; | |
981 | uint8_t first_byte; | |
982 | uint32_t tbl24_index; | |
983 | ||
984 | /* DEBUG: Check user input arguments. */ | |
9f95a23c | 985 | if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL)) |
7c673cae | 986 | return -EINVAL; |
7c673cae FG |
987 | |
988 | first_byte = LOOKUP_FIRST_BYTE; | |
989 | tbl24_index = (ip[0] << BYTES2_SIZE) | (ip[1] << BYTE_SIZE) | ip[2]; | |
990 | ||
991 | /* Calculate pointer to the first entry to be inspected */ | |
992 | tbl = &lpm->tbl24[tbl24_index]; | |
993 | ||
994 | do { | |
995 | /* Continue inspecting following levels until success or failure */ | |
996 | status = lookup_step(lpm, tbl, &tbl_next, ip, first_byte++, next_hop); | |
997 | tbl = tbl_next; | |
998 | } while (status == 1); | |
999 | ||
1000 | return status; | |
1001 | } | |
11fdf7f2 TL |
1002 | BIND_DEFAULT_SYMBOL(rte_lpm6_lookup, _v1705, 17.05); |
1003 | MAP_STATIC_SYMBOL(int rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, | |
1004 | uint32_t *next_hop), rte_lpm6_lookup_v1705); | |
7c673cae FG |
1005 | |
1006 | /* | |
1007 | * Looks up a group of IP addresses | |
1008 | */ | |
1009 | int | |
11fdf7f2 | 1010 | rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm, |
7c673cae FG |
1011 | uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], |
1012 | int16_t * next_hops, unsigned n) | |
1013 | { | |
1014 | unsigned i; | |
1015 | const struct rte_lpm6_tbl_entry *tbl; | |
1016 | const struct rte_lpm6_tbl_entry *tbl_next = NULL; | |
11fdf7f2 TL |
1017 | uint32_t tbl24_index, next_hop; |
1018 | uint8_t first_byte; | |
7c673cae FG |
1019 | int status; |
1020 | ||
1021 | /* DEBUG: Check user input arguments. */ | |
9f95a23c | 1022 | if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL)) |
7c673cae | 1023 | return -EINVAL; |
7c673cae FG |
1024 | |
1025 | for (i = 0; i < n; i++) { | |
1026 | first_byte = LOOKUP_FIRST_BYTE; | |
1027 | tbl24_index = (ips[i][0] << BYTES2_SIZE) | | |
1028 | (ips[i][1] << BYTE_SIZE) | ips[i][2]; | |
1029 | ||
1030 | /* Calculate pointer to the first entry to be inspected */ | |
1031 | tbl = &lpm->tbl24[tbl24_index]; | |
1032 | ||
1033 | do { | |
1034 | /* Continue inspecting following levels until success or failure */ | |
1035 | status = lookup_step(lpm, tbl, &tbl_next, ips[i], first_byte++, | |
1036 | &next_hop); | |
1037 | tbl = tbl_next; | |
1038 | } while (status == 1); | |
1039 | ||
1040 | if (status < 0) | |
1041 | next_hops[i] = -1; | |
1042 | else | |
11fdf7f2 | 1043 | next_hops[i] = (int16_t)next_hop; |
7c673cae FG |
1044 | } |
1045 | ||
1046 | return 0; | |
1047 | } | |
11fdf7f2 TL |
1048 | VERSION_SYMBOL(rte_lpm6_lookup_bulk_func, _v20, 2.0); |
1049 | ||
1050 | int | |
1051 | rte_lpm6_lookup_bulk_func_v1705(const struct rte_lpm6 *lpm, | |
1052 | uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], | |
1053 | int32_t *next_hops, unsigned int n) | |
1054 | { | |
1055 | unsigned int i; | |
1056 | const struct rte_lpm6_tbl_entry *tbl; | |
1057 | const struct rte_lpm6_tbl_entry *tbl_next = NULL; | |
1058 | uint32_t tbl24_index, next_hop; | |
1059 | uint8_t first_byte; | |
1060 | int status; | |
1061 | ||
1062 | /* DEBUG: Check user input arguments. */ | |
1063 | if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL)) | |
1064 | return -EINVAL; | |
1065 | ||
1066 | for (i = 0; i < n; i++) { | |
1067 | first_byte = LOOKUP_FIRST_BYTE; | |
1068 | tbl24_index = (ips[i][0] << BYTES2_SIZE) | | |
1069 | (ips[i][1] << BYTE_SIZE) | ips[i][2]; | |
1070 | ||
1071 | /* Calculate pointer to the first entry to be inspected */ | |
1072 | tbl = &lpm->tbl24[tbl24_index]; | |
1073 | ||
1074 | do { | |
1075 | /* Continue inspecting following levels | |
1076 | * until success or failure | |
1077 | */ | |
1078 | status = lookup_step(lpm, tbl, &tbl_next, ips[i], | |
1079 | first_byte++, &next_hop); | |
1080 | tbl = tbl_next; | |
1081 | } while (status == 1); | |
1082 | ||
1083 | if (status < 0) | |
1084 | next_hops[i] = -1; | |
1085 | else | |
1086 | next_hops[i] = (int32_t)next_hop; | |
1087 | } | |
1088 | ||
1089 | return 0; | |
1090 | } | |
1091 | BIND_DEFAULT_SYMBOL(rte_lpm6_lookup_bulk_func, _v1705, 17.05); | |
1092 | MAP_STATIC_SYMBOL(int rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm, | |
1093 | uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], | |
1094 | int32_t *next_hops, unsigned int n), | |
1095 | rte_lpm6_lookup_bulk_func_v1705); | |
7c673cae | 1096 | |
7c673cae FG |
1097 | /* |
1098 | * Look for a rule in the high-level rules table | |
1099 | */ | |
1100 | int | |
11fdf7f2 TL |
1101 | rte_lpm6_is_rule_present_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, |
1102 | uint8_t *next_hop) | |
1103 | { | |
1104 | uint32_t next_hop32 = 0; | |
1105 | int32_t status; | |
1106 | ||
1107 | /* DEBUG: Check user input arguments. */ | |
1108 | if (next_hop == NULL) | |
1109 | return -EINVAL; | |
1110 | ||
1111 | status = rte_lpm6_is_rule_present_v1705(lpm, ip, depth, &next_hop32); | |
1112 | if (status > 0) | |
1113 | *next_hop = (uint8_t)next_hop32; | |
1114 | ||
1115 | return status; | |
1116 | ||
1117 | } | |
1118 | VERSION_SYMBOL(rte_lpm6_is_rule_present, _v20, 2.0); | |
1119 | ||
1120 | int | |
1121 | rte_lpm6_is_rule_present_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, | |
1122 | uint32_t *next_hop) | |
7c673cae | 1123 | { |
9f95a23c | 1124 | uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE]; |
7c673cae FG |
1125 | |
1126 | /* Check user arguments. */ | |
1127 | if ((lpm == NULL) || next_hop == NULL || ip == NULL || | |
1128 | (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) | |
1129 | return -EINVAL; | |
1130 | ||
1131 | /* Copy the IP and mask it to avoid modifying user's input data. */ | |
9f95a23c TL |
1132 | ip6_copy_addr(masked_ip, ip); |
1133 | ip6_mask_addr(masked_ip, depth); | |
7c673cae | 1134 | |
9f95a23c | 1135 | return rule_find(lpm, masked_ip, depth, next_hop); |
7c673cae | 1136 | } |
11fdf7f2 TL |
1137 | BIND_DEFAULT_SYMBOL(rte_lpm6_is_rule_present, _v1705, 17.05); |
1138 | MAP_STATIC_SYMBOL(int rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, | |
1139 | uint8_t *ip, uint8_t depth, uint32_t *next_hop), | |
1140 | rte_lpm6_is_rule_present_v1705); | |
7c673cae FG |
1141 | |
1142 | /* | |
1143 | * Delete a rule from the rule table. | |
1144 | * NOTE: Valid range for depth parameter is 1 .. 128 inclusive. | |
9f95a23c TL |
1145 | * return |
1146 | * 0 on success | |
1147 | * <0 on failure | |
7c673cae | 1148 | */ |
9f95a23c TL |
1149 | static inline int |
1150 | rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth) | |
7c673cae | 1151 | { |
9f95a23c TL |
1152 | int ret; |
1153 | struct rte_lpm6_rule_key rule_key; | |
7c673cae | 1154 | |
9f95a23c TL |
1155 | /* init rule key */ |
1156 | rule_key_init(&rule_key, ip, depth); | |
7c673cae | 1157 | |
9f95a23c TL |
1158 | /* delete the rule */ |
1159 | ret = rte_hash_del_key(lpm->rules_tbl, (void *) &rule_key); | |
1160 | if (ret >= 0) | |
1161 | lpm->used_rules--; | |
7c673cae | 1162 | |
9f95a23c | 1163 | return ret; |
7c673cae FG |
1164 | } |
1165 | ||
1166 | /* | |
1167 | * Deletes a group of rules | |
9f95a23c TL |
1168 | * |
1169 | * Note that the function rebuilds the lpm table, | |
1170 | * rather than doing incremental updates like | |
1171 | * the regular delete function | |
7c673cae FG |
1172 | */ |
1173 | int | |
1174 | rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm, | |
9f95a23c TL |
1175 | uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, |
1176 | unsigned n) | |
7c673cae | 1177 | { |
9f95a23c | 1178 | uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE]; |
7c673cae FG |
1179 | unsigned i; |
1180 | ||
9f95a23c TL |
1181 | /* Check input arguments. */ |
1182 | if ((lpm == NULL) || (ips == NULL) || (depths == NULL)) | |
7c673cae | 1183 | return -EINVAL; |
7c673cae FG |
1184 | |
1185 | for (i = 0; i < n; i++) { | |
9f95a23c TL |
1186 | ip6_copy_addr(masked_ip, ips[i]); |
1187 | ip6_mask_addr(masked_ip, depths[i]); | |
1188 | rule_delete(lpm, masked_ip, depths[i]); | |
7c673cae FG |
1189 | } |
1190 | ||
1191 | /* | |
1192 | * Set all the table entries to 0 (ie delete every rule | |
1193 | * from the data structure. | |
1194 | */ | |
7c673cae FG |
1195 | memset(lpm->tbl24, 0, sizeof(lpm->tbl24)); |
1196 | memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) | |
1197 | * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s); | |
9f95a23c | 1198 | tbl8_pool_init(lpm); |
7c673cae FG |
1199 | |
1200 | /* | |
1201 | * Add every rule again (except for the ones that were removed from | |
1202 | * the rules table). | |
1203 | */ | |
9f95a23c | 1204 | rebuild_lpm(lpm); |
7c673cae FG |
1205 | |
1206 | return 0; | |
1207 | } | |
1208 | ||
1209 | /* | |
1210 | * Delete all rules from the LPM table. | |
1211 | */ | |
1212 | void | |
1213 | rte_lpm6_delete_all(struct rte_lpm6 *lpm) | |
1214 | { | |
1215 | /* Zero used rules counter. */ | |
1216 | lpm->used_rules = 0; | |
1217 | ||
7c673cae FG |
1218 | /* Zero tbl24. */ |
1219 | memset(lpm->tbl24, 0, sizeof(lpm->tbl24)); | |
1220 | ||
1221 | /* Zero tbl8. */ | |
1222 | memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) * | |
1223 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s); | |
1224 | ||
9f95a23c TL |
1225 | /* init pool of free tbl8 indexes */ |
1226 | tbl8_pool_init(lpm); | |
1227 | ||
7c673cae | 1228 | /* Delete all rules form the rules table. */ |
9f95a23c TL |
1229 | rte_hash_reset(lpm->rules_tbl); |
1230 | } | |
1231 | ||
1232 | /* | |
1233 | * Convert a depth to a one byte long mask | |
1234 | * Example: 4 will be converted to 0xF0 | |
1235 | */ | |
1236 | static uint8_t __attribute__((pure)) | |
1237 | depth_to_mask_1b(uint8_t depth) | |
1238 | { | |
1239 | /* To calculate a mask start with a 1 on the left hand side and right | |
1240 | * shift while populating the left hand side with 1's | |
1241 | */ | |
1242 | return (signed char)0x80 >> (depth - 1); | |
1243 | } | |
1244 | ||
1245 | /* | |
1246 | * Find a less specific rule | |
1247 | */ | |
1248 | static int | |
1249 | rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, | |
1250 | struct rte_lpm6_rule *rule) | |
1251 | { | |
1252 | int ret; | |
1253 | uint32_t next_hop; | |
1254 | uint8_t mask; | |
1255 | struct rte_lpm6_rule_key rule_key; | |
1256 | ||
1257 | if (depth == 1) | |
1258 | return 0; | |
1259 | ||
1260 | rule_key_init(&rule_key, ip, depth); | |
1261 | ||
1262 | while (depth > 1) { | |
1263 | depth--; | |
1264 | ||
1265 | /* each iteration zero one more bit of the key */ | |
1266 | mask = depth & 7; /* depth % BYTE_SIZE */ | |
1267 | if (mask > 0) | |
1268 | mask = depth_to_mask_1b(mask); | |
1269 | ||
1270 | rule_key.depth = depth; | |
1271 | rule_key.ip[depth >> 3] &= mask; | |
1272 | ||
1273 | ret = rule_find_with_key(lpm, &rule_key, &next_hop); | |
1274 | if (ret) { | |
1275 | rule->depth = depth; | |
1276 | ip6_copy_addr(rule->ip, rule_key.ip); | |
1277 | rule->next_hop = next_hop; | |
1278 | return 1; | |
1279 | } | |
1280 | } | |
1281 | ||
1282 | return 0; | |
1283 | } | |
1284 | ||
1285 | /* | |
1286 | * Find range of tbl8 cells occupied by a rule | |
1287 | */ | |
1288 | static void | |
1289 | rule_find_range(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth, | |
1290 | struct rte_lpm6_tbl_entry **from, | |
1291 | struct rte_lpm6_tbl_entry **to, | |
1292 | uint32_t *out_tbl_ind) | |
1293 | { | |
1294 | uint32_t ind; | |
1295 | uint32_t first_3bytes = (uint32_t)ip[0] << 16 | ip[1] << 8 | ip[2]; | |
1296 | ||
1297 | if (depth <= 24) { | |
1298 | /* rule is within the top level */ | |
1299 | ind = first_3bytes; | |
1300 | *from = &lpm->tbl24[ind]; | |
1301 | ind += (1 << (24 - depth)) - 1; | |
1302 | *to = &lpm->tbl24[ind]; | |
1303 | *out_tbl_ind = TBL24_IND; | |
1304 | } else { | |
1305 | /* top level entry */ | |
1306 | struct rte_lpm6_tbl_entry *tbl = &lpm->tbl24[first_3bytes]; | |
1307 | assert(tbl->ext_entry == 1); | |
1308 | /* first tbl8 */ | |
1309 | uint32_t tbl_ind = tbl->lpm6_tbl8_gindex; | |
1310 | tbl = &lpm->tbl8[tbl_ind * | |
1311 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]; | |
1312 | /* current ip byte, the top level is already behind */ | |
1313 | uint8_t byte = 3; | |
1314 | /* minus top level */ | |
1315 | depth -= 24; | |
1316 | ||
1317 | /* interate through levels (tbl8s) | |
1318 | * until we reach the last one | |
1319 | */ | |
1320 | while (depth > 8) { | |
1321 | tbl += ip[byte]; | |
1322 | assert(tbl->ext_entry == 1); | |
1323 | /* go to the next level/tbl8 */ | |
1324 | tbl_ind = tbl->lpm6_tbl8_gindex; | |
1325 | tbl = &lpm->tbl8[tbl_ind * | |
1326 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]; | |
1327 | byte += 1; | |
1328 | depth -= 8; | |
1329 | } | |
1330 | ||
1331 | /* last level/tbl8 */ | |
1332 | ind = ip[byte] & depth_to_mask_1b(depth); | |
1333 | *from = &tbl[ind]; | |
1334 | ind += (1 << (8 - depth)) - 1; | |
1335 | *to = &tbl[ind]; | |
1336 | *out_tbl_ind = tbl_ind; | |
1337 | } | |
1338 | } | |
1339 | ||
1340 | /* | |
1341 | * Remove a table from the LPM tree | |
1342 | */ | |
1343 | static void | |
1344 | remove_tbl(struct rte_lpm6 *lpm, struct rte_lpm_tbl8_hdr *tbl_hdr, | |
1345 | uint32_t tbl_ind, struct rte_lpm6_rule *lsp_rule) | |
1346 | { | |
1347 | struct rte_lpm6_tbl_entry *owner_entry; | |
1348 | ||
1349 | if (tbl_hdr->owner_tbl_ind == TBL24_IND) | |
1350 | owner_entry = &lpm->tbl24[tbl_hdr->owner_entry_ind]; | |
1351 | else { | |
1352 | uint32_t owner_tbl_ind = tbl_hdr->owner_tbl_ind; | |
1353 | owner_entry = &lpm->tbl8[ | |
1354 | owner_tbl_ind * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES + | |
1355 | tbl_hdr->owner_entry_ind]; | |
1356 | ||
1357 | struct rte_lpm_tbl8_hdr *owner_tbl_hdr = | |
1358 | &lpm->tbl8_hdrs[owner_tbl_ind]; | |
1359 | if (--owner_tbl_hdr->ref_cnt == 0) | |
1360 | remove_tbl(lpm, owner_tbl_hdr, owner_tbl_ind, lsp_rule); | |
1361 | } | |
1362 | ||
1363 | assert(owner_entry->ext_entry == 1); | |
1364 | ||
1365 | /* unlink the table */ | |
1366 | if (lsp_rule != NULL) { | |
1367 | struct rte_lpm6_tbl_entry new_tbl_entry = { | |
1368 | .next_hop = lsp_rule->next_hop, | |
1369 | .depth = lsp_rule->depth, | |
1370 | .valid = VALID, | |
1371 | .valid_group = VALID, | |
1372 | .ext_entry = 0 | |
1373 | }; | |
1374 | ||
1375 | *owner_entry = new_tbl_entry; | |
1376 | } else { | |
1377 | struct rte_lpm6_tbl_entry new_tbl_entry = { | |
1378 | .next_hop = 0, | |
1379 | .depth = 0, | |
1380 | .valid = INVALID, | |
1381 | .valid_group = INVALID, | |
1382 | .ext_entry = 0 | |
1383 | }; | |
1384 | ||
1385 | *owner_entry = new_tbl_entry; | |
1386 | } | |
1387 | ||
1388 | /* return the table to the pool */ | |
1389 | tbl8_put(lpm, tbl_ind); | |
1390 | } | |
1391 | ||
1392 | /* | |
1393 | * Deletes a rule | |
1394 | */ | |
1395 | int | |
1396 | rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth) | |
1397 | { | |
1398 | uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE]; | |
1399 | struct rte_lpm6_rule lsp_rule_obj; | |
1400 | struct rte_lpm6_rule *lsp_rule; | |
1401 | int ret; | |
1402 | uint32_t tbl_ind; | |
1403 | struct rte_lpm6_tbl_entry *from, *to; | |
1404 | ||
1405 | /* Check input arguments. */ | |
1406 | if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) | |
1407 | return -EINVAL; | |
1408 | ||
1409 | /* Copy the IP and mask it to avoid modifying user's input data. */ | |
1410 | ip6_copy_addr(masked_ip, ip); | |
1411 | ip6_mask_addr(masked_ip, depth); | |
1412 | ||
1413 | /* Delete the rule from the rule table. */ | |
1414 | ret = rule_delete(lpm, masked_ip, depth); | |
1415 | if (ret < 0) | |
1416 | return -ENOENT; | |
1417 | ||
1418 | /* find rule cells */ | |
1419 | rule_find_range(lpm, masked_ip, depth, &from, &to, &tbl_ind); | |
1420 | ||
1421 | /* find a less specific rule (a rule with smaller depth) | |
1422 | * note: masked_ip will be modified, don't use it anymore | |
1423 | */ | |
1424 | ret = rule_find_less_specific(lpm, masked_ip, depth, | |
1425 | &lsp_rule_obj); | |
1426 | lsp_rule = ret ? &lsp_rule_obj : NULL; | |
1427 | ||
1428 | /* decrement the table rule counter, | |
1429 | * note that tbl24 doesn't have a header | |
1430 | */ | |
1431 | if (tbl_ind != TBL24_IND) { | |
1432 | struct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind]; | |
1433 | if (--tbl_hdr->ref_cnt == 0) { | |
1434 | /* remove the table */ | |
1435 | remove_tbl(lpm, tbl_hdr, tbl_ind, lsp_rule); | |
1436 | return 0; | |
1437 | } | |
1438 | } | |
1439 | ||
1440 | /* iterate rule cells */ | |
1441 | for (; from <= to; from++) | |
1442 | if (from->ext_entry == 1) { | |
1443 | /* reference to a more specific space | |
1444 | * of the prefix/rule. Entries in a more | |
1445 | * specific space that are not used by | |
1446 | * a more specific prefix must be occupied | |
1447 | * by the prefix | |
1448 | */ | |
1449 | if (lsp_rule != NULL) | |
1450 | expand_rule(lpm, | |
1451 | from->lpm6_tbl8_gindex * | |
1452 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES, | |
1453 | depth, lsp_rule->depth, | |
1454 | lsp_rule->next_hop, VALID); | |
1455 | else | |
1456 | /* since the prefix has no less specific prefix, | |
1457 | * its more specific space must be invalidated | |
1458 | */ | |
1459 | expand_rule(lpm, | |
1460 | from->lpm6_tbl8_gindex * | |
1461 | RTE_LPM6_TBL8_GROUP_NUM_ENTRIES, | |
1462 | depth, 0, 0, INVALID); | |
1463 | } else if (from->depth == depth) { | |
1464 | /* entry is not a reference and belongs to the prefix */ | |
1465 | if (lsp_rule != NULL) { | |
1466 | struct rte_lpm6_tbl_entry new_tbl_entry = { | |
1467 | .next_hop = lsp_rule->next_hop, | |
1468 | .depth = lsp_rule->depth, | |
1469 | .valid = VALID, | |
1470 | .valid_group = VALID, | |
1471 | .ext_entry = 0 | |
1472 | }; | |
1473 | ||
1474 | *from = new_tbl_entry; | |
1475 | } else { | |
1476 | struct rte_lpm6_tbl_entry new_tbl_entry = { | |
1477 | .next_hop = 0, | |
1478 | .depth = 0, | |
1479 | .valid = INVALID, | |
1480 | .valid_group = INVALID, | |
1481 | .ext_entry = 0 | |
1482 | }; | |
1483 | ||
1484 | *from = new_tbl_entry; | |
1485 | } | |
1486 | } | |
1487 | ||
1488 | return 0; | |
7c673cae | 1489 | } |