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