build: use static deps for pkg-config libs.private
[dpdk.git] / lib / librte_lpm / rte_lpm6.c
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2010-2014 Intel Corporation
3  */
4 #include <string.h>
5 #include <stdint.h>
6 #include <errno.h>
7 #include <stdarg.h>
8 #include <stdio.h>
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>
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>
24 #include <rte_hash.h>
25 #include <assert.h>
26 #include <rte_jhash.h>
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
43 #define RULE_HASH_TABLE_EXTRA_SPACE              64
44 #define TBL24_IND                        UINT32_MAX
45
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. */
75         uint32_t next_hop; /**< Rule next hop. */
76         uint8_t depth; /**< Rule depth. */
77 };
78
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
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. */
103
104         /* LPM Tables. */
105         struct rte_hash *rules_tbl; /**< LPM rules. */
106         struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
107                         __rte_cache_aligned; /**< LPM tbl24 table. */
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
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
124 ip6_mask_addr(uint8_t *ip, uint8_t depth)
125 {
126         int16_t part_depth, mask;
127         int i;
128
129         part_depth = depth;
130
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);
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;
252         uint64_t mem_size;
253         struct rte_lpm6_list *lpm_list;
254         struct rte_hash *rules_tbl = NULL;
255         uint32_t *tbl8_pool = NULL;
256         struct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL;
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
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
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);
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;
330                 goto fail;
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");
337                 rte_errno = ENOMEM;
338                 goto fail;
339         }
340
341         /* Allocate memory to store the LPM data structures. */
342         lpm = rte_zmalloc_socket(mem_name, (size_t)mem_size,
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);
348                 rte_errno = ENOMEM;
349                 goto fail;
350         }
351
352         /* Save user arguments. */
353         lpm->max_rules = config->max_rules;
354         lpm->number_tbl8s = config->number_tbl8s;
355         snprintf(lpm->name, sizeof(lpm->name), "%s", 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);
362
363         te->data = (void *) lpm;
364
365         TAILQ_INSERT_TAIL(lpm_list, te, next);
366         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
367         return lpm;
368
369 fail:
370         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
371
372 fail_wo_unlock:
373         rte_free(tbl8_hdrs);
374         rte_free(tbl8_pool);
375         rte_hash_free(rules_tbl);
376
377         return NULL;
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
436         rte_free(lpm->tbl8_hdrs);
437         rte_free(lpm->tbl8_pool);
438         rte_hash_free(lpm->rules_tbl);
439         rte_free(lpm);
440         rte_free(te);
441 }
442
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
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.
479  *
480  * Returns:
481  *    0 - next hop of existed rule is updated
482  *    1 - new rule successfully added
483  *   <0 - error
484  */
485 static inline int
486 rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)
487 {
488         int ret, rule_exist;
489         struct rte_lpm6_rule_key rule_key;
490         uint32_t unused;
491
492         /* init a rule key */
493         rule_key_init(&rule_key, ip, depth);
494
495         /* Scan through rule list to see if rule already exists. */
496         rule_exist = rule_find_with_key(lpm, &rule_key, &unused);
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          */
502         if (!rule_exist && lpm->used_rules == lpm->max_rules)
503                 return -ENOSPC;
504
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;
510
511         /* Increment the used rules counter for this rule group. */
512         if (!rule_exist) {
513                 lpm->used_rules++;
514                 return 1;
515         }
516
517         return 0;
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
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)
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 = {
534                 .valid = valid,
535                 .valid_group = valid,
536                 .depth = new_depth,
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
543                                 && lpm->tbl8[j].depth <= old_depth)) {
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;
551                         expand_rule(lpm, tbl8_gindex_next, old_depth, new_depth,
552                                         next_hop, valid);
553                 }
554         }
555 }
556
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
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,
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)
657 {
658         uint32_t entry_ind, tbl_range, tbl8_group_start, tbl8_group_end, i;
659         uint32_t tbl8_gindex;
660         uint8_t bits_covered;
661         int ret;
662
663         /*
664          * Calculate index to the table based on the number and position
665          * of the bytes being inspected in this step.
666          */
667         entry_ind = get_bitshift(ip, first_byte, bytes);
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
679                 for (i = entry_ind; i < (entry_ind + tbl_range); i++) {
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;
701                                 expand_rule(lpm, tbl8_gindex, depth, depth,
702                                                 next_hop, VALID);
703                         }
704                 }
705
706                 /* update tbl8 rule reference counter */
707                 if (tbl_ind != TBL24_IND && is_new_rule)
708                         lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
709
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 */
718                 if (!tbl[entry_ind].valid) {
719                         /* get a new table */
720                         ret = tbl8_get(lpm, &tbl8_gindex);
721                         if (ret != 0)
722                                 return -ENOSPC;
723
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 */
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
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++;
749                 }
750                 /*
751                  * If it's valid but not extended the rule that was stored
752                  * here needs to be moved to the next table.
753                  */
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)
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
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
773                         /* Populate new tbl8 with tbl value. */
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);
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
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++;
800                 }
801
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]);
805         }
806
807         return 1;
808 }
809
810 /*
811  * Add a route
812  */
813 int
814 rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
815                 uint8_t next_hop)
816 {
817         return rte_lpm6_add_v1705(lpm, ip, depth, next_hop);
818 }
819 VERSION_SYMBOL(rte_lpm6_add, _v20, 2.0);
820
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
863 int
864 rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
865                 uint32_t next_hop)
866 {
867         struct rte_lpm6_tbl_entry *tbl;
868         struct rte_lpm6_tbl_entry *tbl_next = NULL;
869         /* init to avoid compiler warning */
870         uint32_t tbl_next_num = 123456;
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. */
880         ip6_copy_addr(masked_ip, ip);
881         ip6_mask_addr(masked_ip, depth);
882
883         /* Simulate adding a new route */
884         int ret = simulate_add(lpm, masked_ip, depth);
885         if (ret < 0)
886                 return ret;
887
888         /* Add the rule to the rule table. */
889         int is_new_rule = rule_add(lpm, masked_ip, depth, next_hop);
890         /* If there is no space available for new rule return error. */
891         if (is_new_rule < 0)
892                 return is_new_rule;
893
894         /* Inspect the first three bytes through tbl24 on the first step. */
895         tbl = lpm->tbl24;
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);
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;
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);
911         }
912
913         return status;
914 }
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);
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,
928                 uint8_t first_byte, uint32_t *next_hop)
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. */
948                 *next_hop = ((uint32_t)tbl_entry & RTE_LPM6_TBL8_BITMASK);
949                 return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT;
950         }
951 }
952
953 /*
954  * Looks up an IP
955  */
956 int
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)
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. */
985         if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL))
986                 return -EINVAL;
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 }
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);
1005
1006 /*
1007  * Looks up a group of IP addresses
1008  */
1009 int
1010 rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm,
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;
1017         uint32_t tbl24_index, next_hop;
1018         uint8_t first_byte;
1019         int status;
1020
1021         /* DEBUG: Check user input arguments. */
1022         if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL))
1023                 return -EINVAL;
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
1043                         next_hops[i] = (int16_t)next_hop;
1044         }
1045
1046         return 0;
1047 }
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);
1096
1097 /*
1098  * Look for a rule in the high-level rules table
1099  */
1100 int
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)
1123 {
1124         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
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. */
1132         ip6_copy_addr(masked_ip, ip);
1133         ip6_mask_addr(masked_ip, depth);
1134
1135         return rule_find(lpm, masked_ip, depth, next_hop);
1136 }
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);
1141
1142 /*
1143  * Delete a rule from the rule table.
1144  * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
1145  * return
1146  *        0 on success
1147  *   <0 on failure
1148  */
1149 static inline int
1150 rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
1151 {
1152         int ret;
1153         struct rte_lpm6_rule_key rule_key;
1154
1155         /* init rule key */
1156         rule_key_init(&rule_key, ip, depth);
1157
1158         /* delete the rule */
1159         ret = rte_hash_del_key(lpm->rules_tbl, (void *) &rule_key);
1160         if (ret >= 0)
1161                 lpm->used_rules--;
1162
1163         return ret;
1164 }
1165
1166 /*
1167  * Deletes a group of rules
1168  *
1169  * Note that the function rebuilds the lpm table,
1170  * rather than doing incremental updates like
1171  * the regular delete function
1172  */
1173 int
1174 rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
1175                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths,
1176                 unsigned n)
1177 {
1178         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
1179         unsigned i;
1180
1181         /* Check input arguments. */
1182         if ((lpm == NULL) || (ips == NULL) || (depths == NULL))
1183                 return -EINVAL;
1184
1185         for (i = 0; i < n; i++) {
1186                 ip6_copy_addr(masked_ip, ips[i]);
1187                 ip6_mask_addr(masked_ip, depths[i]);
1188                 rule_delete(lpm, masked_ip, depths[i]);
1189         }
1190
1191         /*
1192          * Set all the table entries to 0 (ie delete every rule
1193          * from the data structure.
1194          */
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);
1198         tbl8_pool_init(lpm);
1199
1200         /*
1201          * Add every rule again (except for the ones that were removed from
1202          * the rules table).
1203          */
1204         rebuild_lpm(lpm);
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
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
1225         /* init pool of free tbl8 indexes */
1226         tbl8_pool_init(lpm);
1227
1228         /* Delete all rules form the rules table. */
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;
1489 }