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 }