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
  45 #define lpm6_tbl8_gindex next_hop
  46
  47 /** Flags for setting an entry as valid/invalid. */
  48 enum valid_flag {
  49         INVALID = 0,
  50         VALID
  51 };
  52
  53 TAILQ_HEAD(rte_lpm6_list, rte_tailq_entry);
  54
  55 static struct rte_tailq_elem rte_lpm6_tailq = {
  56         .name = "RTE_LPM6",
  57 };
  58 EAL_REGISTER_TAILQ(rte_lpm6_tailq)
  59
  60 /** Tbl entry structure. It is the same for both tbl24 and tbl8 */
  61 struct rte_lpm6_tbl_entry {
  62         uint32_t next_hop:      21;  /**< Next hop / next table to be checked. */
  63         uint32_t depth  :8;      /**< Rule depth. */
  64
  65         /* Flags. */
  66         uint32_t valid     :1;   /**< Validation flag. */
  67         uint32_t valid_group :1; /**< Group validation flag. */
  68         uint32_t ext_entry :1;   /**< External entry. */
  69 };
  70
  71 /** Rules tbl entry structure. */
  72 struct rte_lpm6_rule {
  73         uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
  74         uint32_t next_hop; /**< Rule next hop. */
  75         uint8_t depth; /**< Rule depth. */
  76 };
  77
  78 /** Rules tbl entry key. */
  79 struct rte_lpm6_rule_key {
  80         uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
  81         uint8_t depth; /**< Rule depth. */
  82 };
  83
  84 /** LPM6 structure. */
  85 struct rte_lpm6 {
  86         /* LPM metadata. */
  87         char name[RTE_LPM6_NAMESIZE];    /**< Name of the lpm. */
  88         uint32_t max_rules;              /**< Max number of rules. */
  89         uint32_t used_rules;             /**< Used rules so far. */
  90         uint32_t number_tbl8s;           /**< Number of tbl8s to allocate. */
  91         uint32_t next_tbl8;              /**< Next tbl8 to be used. */
  92
  93         /* LPM Tables. */
  94         struct rte_hash *rules_tbl; /**< LPM rules. */
  95         struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
  96                         __rte_cache_aligned; /**< LPM tbl24 table. */
  97         struct rte_lpm6_tbl_entry tbl8[0]
  98                         __rte_cache_aligned; /**< LPM tbl8 table. */
  99 };
 100
 101 /*
 102  * Takes an array of uint8_t (IPv6 address) and masks it using the depth.
 103  * It leaves untouched one bit per unit in the depth variable
 104  * and set the rest to 0.
 105  */
 106 static inline void
 107 ip6_mask_addr(uint8_t *ip, uint8_t depth)
 108 {
 109         int16_t part_depth, mask;
 110         int i;
 111
 112         part_depth = depth;
 113
 114         for (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) {
 115                 if (part_depth < BYTE_SIZE && part_depth >= 0) {
 116                         mask = (uint16_t)(~(UINT8_MAX >> part_depth));
 117                         ip[i] = (uint8_t)(ip[i] & mask);
 118                 } else if (part_depth < 0)
 119                         ip[i] = 0;
 120
 121                 part_depth -= BYTE_SIZE;
 122         }
 123 }
 124
 125 /* copy ipv6 address */
 126 static inline void
 127 ip6_copy_addr(uint8_t *dst, const uint8_t *src)
 128 {
 129         rte_memcpy(dst, src, RTE_LPM6_IPV6_ADDR_SIZE);
 130 }
 131
 132 /*
 133  * LPM6 rule hash function
 134  *
 135  * It's used as a hash function for the rte_hash
 136  *      containing rules
 137  */
 138 static inline uint32_t
 139 rule_hash(const void *data, __rte_unused uint32_t data_len,
 140                   uint32_t init_val)
 141 {
 142         return rte_jhash(data, sizeof(struct rte_lpm6_rule_key), init_val);
 143 }
 144
 145 /*
 146  * Init a rule key.
 147  *        note that ip must be already masked
 148  */
 149 static inline void
 150 rule_key_init(struct rte_lpm6_rule_key *key, uint8_t *ip, uint8_t depth)
 151 {
 152         ip6_copy_addr(key->ip, ip);
 153         key->depth = depth;
 154 }
 155
 156 /*
 157  * Rebuild the entire LPM tree by reinserting all rules
 158  */
 159 static void
 160 rebuild_lpm(struct rte_lpm6 *lpm)
 161 {
 162         uint64_t next_hop;
 163         struct rte_lpm6_rule_key *rule_key;
 164         uint32_t iter = 0;
 165
 166         while (rte_hash_iterate(lpm->rules_tbl, (void *) &rule_key,
 167                         (void **) &next_hop, &iter) >= 0)
 168                 rte_lpm6_add(lpm, rule_key->ip, rule_key->depth,
 169                         (uint32_t) next_hop);
 170 }
 171
 172 /*
 173  * Allocates memory for LPM object
 174  */
 175 struct rte_lpm6 *
 176 rte_lpm6_create(const char *name, int socket_id,
 177                 const struct rte_lpm6_config *config)
 178 {
 179         char mem_name[RTE_LPM6_NAMESIZE];
 180         struct rte_lpm6 *lpm = NULL;
 181         struct rte_tailq_entry *te;
 182         uint64_t mem_size;
 183         struct rte_lpm6_list *lpm_list;
 184         struct rte_hash *rules_tbl = NULL;
 185
 186         lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
 187
 188         RTE_BUILD_BUG_ON(sizeof(struct rte_lpm6_tbl_entry) != sizeof(uint32_t));
 189
 190         /* Check user arguments. */
 191         if ((name == NULL) || (socket_id < -1) || (config == NULL) ||
 192                         (config->max_rules == 0) ||
 193                         config->number_tbl8s > RTE_LPM6_TBL8_MAX_NUM_GROUPS) {
 194                 rte_errno = EINVAL;
 195                 return NULL;
 196         }
 197
 198         /* create rules hash table */
 199         snprintf(mem_name, sizeof(mem_name), "LRH_%s", name);
 200         struct rte_hash_parameters rule_hash_tbl_params = {
 201                 .entries = config->max_rules * 1.2 +
 202                         RULE_HASH_TABLE_EXTRA_SPACE,
 203                 .key_len = sizeof(struct rte_lpm6_rule_key),
 204                 .hash_func = rule_hash,
 205                 .hash_func_init_val = 0,
 206                 .name = mem_name,
 207                 .reserved = 0,
 208                 .socket_id = socket_id,
 209                 .extra_flag = 0
 210         };
 211
 212         rules_tbl = rte_hash_create(&rule_hash_tbl_params);
 213         if (rules_tbl == NULL) {
 214                 RTE_LOG(ERR, LPM, "LPM rules hash table allocation failed: %s (%d)",
 215                                   rte_strerror(rte_errno), rte_errno);
 216                 goto fail_wo_unlock;
 217         }
 218
 219         snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);
 220
 221         /* Determine the amount of memory to allocate. */
 222         mem_size = sizeof(*lpm) + (sizeof(lpm->tbl8[0]) *
 223                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s);
 224
 225         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 226
 227         /* Guarantee there's no existing */
 228         TAILQ_FOREACH(te, lpm_list, next) {
 229                 lpm = (struct rte_lpm6 *) te->data;
 230                 if (strncmp(name, lpm->name, RTE_LPM6_NAMESIZE) == 0)
 231                         break;
 232         }
 233         lpm = NULL;
 234         if (te != NULL) {
 235                 rte_errno = EEXIST;
 236                 goto fail;
 237         }
 238
 239         /* allocate tailq entry */
 240         te = rte_zmalloc("LPM6_TAILQ_ENTRY", sizeof(*te), 0);
 241         if (te == NULL) {
 242                 RTE_LOG(ERR, LPM, "Failed to allocate tailq entry!\n");
 243                 rte_errno = ENOMEM;
 244                 goto fail;
 245         }
 246
 247         /* Allocate memory to store the LPM data structures. */
 248         lpm = rte_zmalloc_socket(mem_name, (size_t)mem_size,
 249                         RTE_CACHE_LINE_SIZE, socket_id);
 250
 251         if (lpm == NULL) {
 252                 RTE_LOG(ERR, LPM, "LPM memory allocation failed\n");
 253                 rte_free(te);
 254                 rte_errno = ENOMEM;
 255                 goto fail;
 256         }
 257
 258         /* Save user arguments. */
 259         lpm->max_rules = config->max_rules;
 260         lpm->number_tbl8s = config->number_tbl8s;
 261         snprintf(lpm->name, sizeof(lpm->name), "%s", name);
 262         lpm->rules_tbl = rules_tbl;
 263
 264         te->data = (void *) lpm;
 265
 266         TAILQ_INSERT_TAIL(lpm_list, te, next);
 267         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 268         return lpm;
 269
 270 fail:
 271         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 272
 273 fail_wo_unlock:
 274         rte_hash_free(rules_tbl);
 275
 276         return NULL;
 277 }
 278
 279 /*
 280  * Find an existing lpm table and return a pointer to it.
 281  */
 282 struct rte_lpm6 *
 283 rte_lpm6_find_existing(const char *name)
 284 {
 285         struct rte_lpm6 *l = NULL;
 286         struct rte_tailq_entry *te;
 287         struct rte_lpm6_list *lpm_list;
 288
 289         lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
 290
 291         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
 292         TAILQ_FOREACH(te, lpm_list, next) {
 293                 l = (struct rte_lpm6 *) te->data;
 294                 if (strncmp(name, l->name, RTE_LPM6_NAMESIZE) == 0)
 295                         break;
 296         }
 297         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
 298
 299         if (te == NULL) {
 300                 rte_errno = ENOENT;
 301                 return NULL;
 302         }
 303
 304         return l;
 305 }
 306
 307 /*
 308  * Deallocates memory for given LPM table.
 309  */
 310 void
 311 rte_lpm6_free(struct rte_lpm6 *lpm)
 312 {
 313         struct rte_lpm6_list *lpm_list;
 314         struct rte_tailq_entry *te;
 315
 316         /* Check user arguments. */
 317         if (lpm == NULL)
 318                 return;
 319
 320         lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
 321
 322         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 323
 324         /* find our tailq entry */
 325         TAILQ_FOREACH(te, lpm_list, next) {
 326                 if (te->data == (void *) lpm)
 327                         break;
 328         }
 329
 330         if (te != NULL)
 331                 TAILQ_REMOVE(lpm_list, te, next);
 332
 333         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 334
 335         rte_hash_free(lpm->rules_tbl);
 336         rte_free(lpm);
 337         rte_free(te);
 338 }
 339
 340 /* Find a rule */
 341 static inline int
 342 rule_find_with_key(struct rte_lpm6 *lpm,
 343                   const struct rte_lpm6_rule_key *rule_key,
 344                   uint32_t *next_hop)
 345 {
 346         uint64_t hash_val;
 347         int ret;
 348
 349         /* lookup for a rule */
 350         ret = rte_hash_lookup_data(lpm->rules_tbl, (const void *) rule_key,
 351                 (void **) &hash_val);
 352         if (ret >= 0) {
 353                 *next_hop = (uint32_t) hash_val;
 354                 return 1;
 355         }
 356
 357         return 0;
 358 }
 359
 360 /* Find a rule */
 361 static int
 362 rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
 363                   uint32_t *next_hop)
 364 {
 365         struct rte_lpm6_rule_key rule_key;
 366
 367         /* init a rule key */
 368         rule_key_init(&rule_key, ip, depth);
 369
 370         return rule_find_with_key(lpm, &rule_key, next_hop);
 371 }
 372
 373 /*
 374  * Checks if a rule already exists in the rules table and updates
 375  * the nexthop if so. Otherwise it adds a new rule if enough space is available.
 376  *
 377  * Returns:
 378  *    0 - next hop of existed rule is updated
 379  *    1 - new rule successfully added
 380  *   <0 - error
 381  */
 382 static inline int
 383 rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)
 384 {
 385         int ret, rule_exist;
 386         struct rte_lpm6_rule_key rule_key;
 387         uint32_t unused;
 388
 389         /* init a rule key */
 390         rule_key_init(&rule_key, ip, depth);
 391
 392         /* Scan through rule list to see if rule already exists. */
 393         rule_exist = rule_find_with_key(lpm, &rule_key, &unused);
 394
 395         /*
 396          * If rule does not exist check if there is space to add a new rule to
 397          * this rule group. If there is no space return error.
 398          */
 399         if (!rule_exist && lpm->used_rules == lpm->max_rules)
 400                 return -ENOSPC;
 401
 402         /* add the rule or update rules next hop */
 403         ret = rte_hash_add_key_data(lpm->rules_tbl, &rule_key,
 404                 (void *)(uintptr_t) next_hop);
 405         if (ret < 0)
 406                 return ret;
 407
 408         /* Increment the used rules counter for this rule group. */
 409         if (!rule_exist) {
 410                 lpm->used_rules++;
 411                 return 1;
 412         }
 413
 414         return 0;
 415 }
 416
 417 /*
 418  * Function that expands a rule across the data structure when a less-generic
 419  * one has been added before. It assures that every possible combination of bits
 420  * in the IP address returns a match.
 421  */
 422 static void
 423 expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
 424                 uint32_t next_hop)
 425 {
 426         uint32_t tbl8_group_end, tbl8_gindex_next, j;
 427
 428         tbl8_group_end = tbl8_gindex + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 429
 430         struct rte_lpm6_tbl_entry new_tbl8_entry = {
 431                 .valid = VALID,
 432                 .valid_group = VALID,
 433                 .depth = depth,
 434                 .next_hop = next_hop,
 435                 .ext_entry = 0,
 436         };
 437
 438         for (j = tbl8_gindex; j < tbl8_group_end; j++) {
 439                 if (!lpm->tbl8[j].valid || (lpm->tbl8[j].ext_entry == 0
 440                                 && lpm->tbl8[j].depth <= depth)) {
 441
 442                         lpm->tbl8[j] = new_tbl8_entry;
 443
 444                 } else if (lpm->tbl8[j].ext_entry == 1) {
 445
 446                         tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex
 447                                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 448                         expand_rule(lpm, tbl8_gindex_next, depth, next_hop);
 449                 }
 450         }
 451 }
 452
 453 /*
 454  * Partially adds a new route to the data structure (tbl24+tbl8s).
 455  * It returns 0 on success, a negative number on failure, or 1 if
 456  * the process needs to be continued by calling the function again.
 457  */
 458 static inline int
 459 add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
 460                 struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip, uint8_t bytes,
 461                 uint8_t first_byte, uint8_t depth, uint32_t next_hop)
 462 {
 463         uint32_t tbl_index, tbl_range, tbl8_group_start, tbl8_group_end, i;
 464         int32_t tbl8_gindex;
 465         int8_t bitshift;
 466         uint8_t bits_covered;
 467
 468         /*
 469          * Calculate index to the table based on the number and position
 470          * of the bytes being inspected in this step.
 471          */
 472         tbl_index = 0;
 473         for (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {
 474                 bitshift = (int8_t)((bytes - i)*BYTE_SIZE);
 475
 476                 if (bitshift < 0) bitshift = 0;
 477                 tbl_index = tbl_index | ip[i-1] << bitshift;
 478         }
 479
 480         /* Number of bits covered in this step */
 481         bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);
 482
 483         /*
 484          * If depth if smaller than this number (ie this is the last step)
 485          * expand the rule across the relevant positions in the table.
 486          */
 487         if (depth <= bits_covered) {
 488                 tbl_range = 1 << (bits_covered - depth);
 489
 490                 for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
 491                         if (!tbl[i].valid || (tbl[i].ext_entry == 0 &&
 492                                         tbl[i].depth <= depth)) {
 493
 494                                 struct rte_lpm6_tbl_entry new_tbl_entry = {
 495                                         .next_hop = next_hop,
 496                                         .depth = depth,
 497                                         .valid = VALID,
 498                                         .valid_group = VALID,
 499                                         .ext_entry = 0,
 500                                 };
 501
 502                                 tbl[i] = new_tbl_entry;
 503
 504                         } else if (tbl[i].ext_entry == 1) {
 505
 506                                 /*
 507                                  * If tbl entry is valid and extended calculate the index
 508                                  * into next tbl8 and expand the rule across the data structure.
 509                                  */
 510                                 tbl8_gindex = tbl[i].lpm6_tbl8_gindex *
 511                                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 512                                 expand_rule(lpm, tbl8_gindex, depth, next_hop);
 513                         }
 514                 }
 515
 516                 return 0;
 517         }
 518         /*
 519          * If this is not the last step just fill one position
 520          * and calculate the index to the next table.
 521          */
 522         else {
 523                 /* If it's invalid a new tbl8 is needed */
 524                 if (!tbl[tbl_index].valid) {
 525                         if (lpm->next_tbl8 < lpm->number_tbl8s)
 526                                 tbl8_gindex = (lpm->next_tbl8)++;
 527                         else
 528                                 return -ENOSPC;
 529
 530                         struct rte_lpm6_tbl_entry new_tbl_entry = {
 531                                 .lpm6_tbl8_gindex = tbl8_gindex,
 532                                 .depth = 0,
 533                                 .valid = VALID,
 534                                 .valid_group = VALID,
 535                                 .ext_entry = 1,
 536                         };
 537
 538                         tbl[tbl_index] = new_tbl_entry;
 539                 }
 540                 /*
 541                  * If it's valid but not extended the rule that was stored *
 542                  * here needs to be moved to the next table.
 543                  */
 544                 else if (tbl[tbl_index].ext_entry == 0) {
 545                         /* Search for free tbl8 group. */
 546                         if (lpm->next_tbl8 < lpm->number_tbl8s)
 547                                 tbl8_gindex = (lpm->next_tbl8)++;
 548                         else
 549                                 return -ENOSPC;
 550
 551                         tbl8_group_start = tbl8_gindex *
 552                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 553                         tbl8_group_end = tbl8_group_start +
 554                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 555
 556                         /* Populate new tbl8 with tbl value. */
 557                         for (i = tbl8_group_start; i < tbl8_group_end; i++) {
 558                                 lpm->tbl8[i].valid = VALID;
 559                                 lpm->tbl8[i].depth = tbl[tbl_index].depth;
 560                                 lpm->tbl8[i].next_hop = tbl[tbl_index].next_hop;
 561                                 lpm->tbl8[i].ext_entry = 0;
 562                         }
 563
 564                         /*
 565                          * Update tbl entry to point to new tbl8 entry. Note: The
 566                          * ext_flag and tbl8_index need to be updated simultaneously,
 567                          * so assign whole structure in one go.
 568                          */
 569                         struct rte_lpm6_tbl_entry new_tbl_entry = {
 570                                 .lpm6_tbl8_gindex = tbl8_gindex,
 571                                 .depth = 0,
 572                                 .valid = VALID,
 573                                 .valid_group = VALID,
 574                                 .ext_entry = 1,
 575                         };
 576
 577                         tbl[tbl_index] = new_tbl_entry;
 578                 }
 579
 580                 *tbl_next = &(lpm->tbl8[tbl[tbl_index].lpm6_tbl8_gindex *
 581                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
 582         }
 583
 584         return 1;
 585 }
 586
 587 /*
 588  * Add a route
 589  */
 590 int
 591 rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
 592                 uint8_t next_hop)
 593 {
 594         return rte_lpm6_add_v1705(lpm, ip, depth, next_hop);
 595 }
 596 VERSION_SYMBOL(rte_lpm6_add, _v20, 2.0);
 597
 598 int
 599 rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
 600                 uint32_t next_hop)
 601 {
 602         struct rte_lpm6_tbl_entry *tbl;
 603         struct rte_lpm6_tbl_entry *tbl_next = NULL;
 604         int32_t ret;
 605         int status;
 606         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
 607         int i;
 608
 609         /* Check user arguments. */
 610         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
 611                 return -EINVAL;
 612
 613         /* Copy the IP and mask it to avoid modifying user's input data. */
 614         ip6_copy_addr(masked_ip, ip);
 615         ip6_mask_addr(masked_ip, depth);
 616
 617         /* Add the rule to the rule table. */
 618         ret = rule_add(lpm, masked_ip, depth, next_hop);
 619         /* If there is no space available for new rule return error. */
 620         if (ret < 0)
 621                 return ret;
 622
 623         /* Inspect the first three bytes through tbl24 on the first step. */
 624         tbl = lpm->tbl24;
 625         status = add_step (lpm, tbl, &tbl_next, masked_ip, ADD_FIRST_BYTE, 1,
 626                         depth, next_hop);
 627         if (status < 0) {
 628                 rte_lpm6_delete(lpm, masked_ip, depth);
 629
 630                 return status;
 631         }
 632
 633         /*
 634          * Inspect one by one the rest of the bytes until
 635          * the process is completed.
 636          */
 637         for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && status == 1; i++) {
 638                 tbl = tbl_next;
 639                 status = add_step (lpm, tbl, &tbl_next, masked_ip, 1, (uint8_t)(i+1),
 640                                 depth, next_hop);
 641                 if (status < 0) {
 642                         rte_lpm6_delete(lpm, masked_ip, depth);
 643
 644                         return status;
 645                 }
 646         }
 647
 648         return status;
 649 }
 650 BIND_DEFAULT_SYMBOL(rte_lpm6_add, _v1705, 17.05);
 651 MAP_STATIC_SYMBOL(int rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip,
 652                                 uint8_t depth, uint32_t next_hop),
 653                 rte_lpm6_add_v1705);
 654
 655 /*
 656  * Takes a pointer to a table entry and inspect one level.
 657  * The function returns 0 on lookup success, ENOENT if no match was found
 658  * or 1 if the process needs to be continued by calling the function again.
 659  */
 660 static inline int
 661 lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
 662                 const struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip,
 663                 uint8_t first_byte, uint32_t *next_hop)
 664 {
 665         uint32_t tbl8_index, tbl_entry;
 666
 667         /* Take the integer value from the pointer. */
 668         tbl_entry = *(const uint32_t *)tbl;
 669
 670         /* If it is valid and extended we calculate the new pointer to return. */
 671         if ((tbl_entry & RTE_LPM6_VALID_EXT_ENTRY_BITMASK) ==
 672                         RTE_LPM6_VALID_EXT_ENTRY_BITMASK) {
 673
 674                 tbl8_index = ip[first_byte-1] +
 675                                 ((tbl_entry & RTE_LPM6_TBL8_BITMASK) *
 676                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES);
 677
 678                 *tbl_next = &lpm->tbl8[tbl8_index];
 679
 680                 return 1;
 681         } else {
 682                 /* If not extended then we can have a match. */
 683                 *next_hop = ((uint32_t)tbl_entry & RTE_LPM6_TBL8_BITMASK);
 684                 return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT;
 685         }
 686 }
 687
 688 /*
 689  * Looks up an IP
 690  */
 691 int
 692 rte_lpm6_lookup_v20(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
 693 {
 694         uint32_t next_hop32 = 0;
 695         int32_t status;
 696
 697         /* DEBUG: Check user input arguments. */
 698         if (next_hop == NULL)
 699                 return -EINVAL;
 700
 701         status = rte_lpm6_lookup_v1705(lpm, ip, &next_hop32);
 702         if (status == 0)
 703                 *next_hop = (uint8_t)next_hop32;
 704
 705         return status;
 706 }
 707 VERSION_SYMBOL(rte_lpm6_lookup, _v20, 2.0);
 708
 709 int
 710 rte_lpm6_lookup_v1705(const struct rte_lpm6 *lpm, uint8_t *ip,
 711                 uint32_t *next_hop)
 712 {
 713         const struct rte_lpm6_tbl_entry *tbl;
 714         const struct rte_lpm6_tbl_entry *tbl_next = NULL;
 715         int status;
 716         uint8_t first_byte;
 717         uint32_t tbl24_index;
 718
 719         /* DEBUG: Check user input arguments. */
 720         if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL)) {
 721                 return -EINVAL;
 722         }
 723
 724         first_byte = LOOKUP_FIRST_BYTE;
 725         tbl24_index = (ip[0] << BYTES2_SIZE) | (ip[1] << BYTE_SIZE) | ip[2];
 726
 727         /* Calculate pointer to the first entry to be inspected */
 728         tbl = &lpm->tbl24[tbl24_index];
 729
 730         do {
 731                 /* Continue inspecting following levels until success or failure */
 732                 status = lookup_step(lpm, tbl, &tbl_next, ip, first_byte++, next_hop);
 733                 tbl = tbl_next;
 734         } while (status == 1);
 735
 736         return status;
 737 }
 738 BIND_DEFAULT_SYMBOL(rte_lpm6_lookup, _v1705, 17.05);
 739 MAP_STATIC_SYMBOL(int rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip,
 740                                 uint32_t *next_hop), rte_lpm6_lookup_v1705);
 741
 742 /*
 743  * Looks up a group of IP addresses
 744  */
 745 int
 746 rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm,
 747                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
 748                 int16_t * next_hops, unsigned n)
 749 {
 750         unsigned i;
 751         const struct rte_lpm6_tbl_entry *tbl;
 752         const struct rte_lpm6_tbl_entry *tbl_next = NULL;
 753         uint32_t tbl24_index, next_hop;
 754         uint8_t first_byte;
 755         int status;
 756
 757         /* DEBUG: Check user input arguments. */
 758         if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL)) {
 759                 return -EINVAL;
 760         }
 761
 762         for (i = 0; i < n; i++) {
 763                 first_byte = LOOKUP_FIRST_BYTE;
 764                 tbl24_index = (ips[i][0] << BYTES2_SIZE) |
 765                                 (ips[i][1] << BYTE_SIZE) | ips[i][2];
 766
 767                 /* Calculate pointer to the first entry to be inspected */
 768                 tbl = &lpm->tbl24[tbl24_index];
 769
 770                 do {
 771                         /* Continue inspecting following levels until success or failure */
 772                         status = lookup_step(lpm, tbl, &tbl_next, ips[i], first_byte++,
 773                                         &next_hop);
 774                         tbl = tbl_next;
 775                 } while (status == 1);
 776
 777                 if (status < 0)
 778                         next_hops[i] = -1;
 779                 else
 780                         next_hops[i] = (int16_t)next_hop;
 781         }
 782
 783         return 0;
 784 }
 785 VERSION_SYMBOL(rte_lpm6_lookup_bulk_func, _v20, 2.0);
 786
 787 int
 788 rte_lpm6_lookup_bulk_func_v1705(const struct rte_lpm6 *lpm,
 789                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
 790                 int32_t *next_hops, unsigned int n)
 791 {
 792         unsigned int i;
 793         const struct rte_lpm6_tbl_entry *tbl;
 794         const struct rte_lpm6_tbl_entry *tbl_next = NULL;
 795         uint32_t tbl24_index, next_hop;
 796         uint8_t first_byte;
 797         int status;
 798
 799         /* DEBUG: Check user input arguments. */
 800         if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL))
 801                 return -EINVAL;
 802
 803         for (i = 0; i < n; i++) {
 804                 first_byte = LOOKUP_FIRST_BYTE;
 805                 tbl24_index = (ips[i][0] << BYTES2_SIZE) |
 806                                 (ips[i][1] << BYTE_SIZE) | ips[i][2];
 807
 808                 /* Calculate pointer to the first entry to be inspected */
 809                 tbl = &lpm->tbl24[tbl24_index];
 810
 811                 do {
 812                         /* Continue inspecting following levels
 813                          * until success or failure
 814                          */
 815                         status = lookup_step(lpm, tbl, &tbl_next, ips[i],
 816                                         first_byte++, &next_hop);
 817                         tbl = tbl_next;
 818                 } while (status == 1);
 819
 820                 if (status < 0)
 821                         next_hops[i] = -1;
 822                 else
 823                         next_hops[i] = (int32_t)next_hop;
 824         }
 825
 826         return 0;
 827 }
 828 BIND_DEFAULT_SYMBOL(rte_lpm6_lookup_bulk_func, _v1705, 17.05);
 829 MAP_STATIC_SYMBOL(int rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
 830                                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
 831                                 int32_t *next_hops, unsigned int n),
 832                 rte_lpm6_lookup_bulk_func_v1705);
 833
 834 /*
 835  * Look for a rule in the high-level rules table
 836  */
 837 int
 838 rte_lpm6_is_rule_present_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
 839                 uint8_t *next_hop)
 840 {
 841         uint32_t next_hop32 = 0;
 842         int32_t status;
 843
 844         /* DEBUG: Check user input arguments. */
 845         if (next_hop == NULL)
 846                 return -EINVAL;
 847
 848         status = rte_lpm6_is_rule_present_v1705(lpm, ip, depth, &next_hop32);
 849         if (status > 0)
 850                 *next_hop = (uint8_t)next_hop32;
 851
 852         return status;
 853
 854 }
 855 VERSION_SYMBOL(rte_lpm6_is_rule_present, _v20, 2.0);
 856
 857 int
 858 rte_lpm6_is_rule_present_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
 859                 uint32_t *next_hop)
 860 {
 861         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
 862
 863         /* Check user arguments. */
 864         if ((lpm == NULL) || next_hop == NULL || ip == NULL ||
 865                         (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
 866                 return -EINVAL;
 867
 868         /* Copy the IP and mask it to avoid modifying user's input data. */
 869         ip6_copy_addr(masked_ip, ip);
 870         ip6_mask_addr(masked_ip, depth);
 871
 872         return rule_find(lpm, masked_ip, depth, next_hop);
 873 }
 874 BIND_DEFAULT_SYMBOL(rte_lpm6_is_rule_present, _v1705, 17.05);
 875 MAP_STATIC_SYMBOL(int rte_lpm6_is_rule_present(struct rte_lpm6 *lpm,
 876                                 uint8_t *ip, uint8_t depth, uint32_t *next_hop),
 877                 rte_lpm6_is_rule_present_v1705);
 878
 879 /*
 880  * Delete a rule from the rule table.
 881  * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
 882  * return
 883  *        0 on success
 884  *   <0 on failure
 885  */
 886 static inline int
 887 rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
 888 {
 889         int ret;
 890         struct rte_lpm6_rule_key rule_key;
 891
 892         /* init rule key */
 893         rule_key_init(&rule_key, ip, depth);
 894
 895         /* delete the rule */
 896         ret = rte_hash_del_key(lpm->rules_tbl, (void *) &rule_key);
 897         if (ret >= 0)
 898                 lpm->used_rules--;
 899
 900         return ret;
 901 }
 902
 903 /*
 904  * Deletes a rule
 905  */
 906 int
 907 rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
 908 {
 909         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
 910         int ret;
 911
 912         /*
 913          * Check input arguments.
 914          */
 915         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) {
 916                 return -EINVAL;
 917         }
 918
 919         /* Copy the IP and mask it to avoid modifying user's input data. */
 920         ip6_copy_addr(masked_ip, ip);
 921         ip6_mask_addr(masked_ip, depth);
 922
 923         /* Delete the rule from the rule table. */
 924         ret = rule_delete(lpm, masked_ip, depth);
 925         if (ret < 0)
 926                 return -ENOENT;
 927
 928         /*
 929          * Set all the table entries to 0 (ie delete every rule
 930          * from the data structure.
 931          */
 932         lpm->next_tbl8 = 0;
 933         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
 934         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
 935                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
 936
 937         /*
 938          * Add every rule again (except for the one that was removed from
 939          * the rules table).
 940          */
 941         rebuild_lpm(lpm);
 942
 943         return 0;
 944 }
 945
 946 /*
 947  * Deletes a group of rules
 948  */
 949 int
 950 rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
 951                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, unsigned n)
 952 {
 953         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
 954         unsigned i;
 955
 956         /*
 957          * Check input arguments.
 958          */
 959         if ((lpm == NULL) || (ips == NULL) || (depths == NULL))
 960                 return -EINVAL;
 961
 962         for (i = 0; i < n; i++) {
 963                 ip6_copy_addr(masked_ip, ips[i]);
 964                 ip6_mask_addr(masked_ip, depths[i]);
 965                 rule_delete(lpm, masked_ip, depths[i]);
 966         }
 967
 968         /*
 969          * Set all the table entries to 0 (ie delete every rule
 970          * from the data structure.
 971          */
 972         lpm->next_tbl8 = 0;
 973         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
 974         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
 975                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
 976
 977         /*
 978          * Add every rule again (except for the ones that were removed from
 979          * the rules table).
 980          */
 981         rebuild_lpm(lpm);
 982
 983         return 0;
 984 }
 985
 986 /*
 987  * Delete all rules from the LPM table.
 988  */
 989 void
 990 rte_lpm6_delete_all(struct rte_lpm6 *lpm)
 991 {
 992         /* Zero used rules counter. */
 993         lpm->used_rules = 0;
 994
 995         /* Zero next tbl8 index. */
 996         lpm->next_tbl8 = 0;
 997
 998         /* Zero tbl24. */
 999         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
1000
1001         /* Zero tbl8. */
1002         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *
1003                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
1004
1005         /* Delete all rules form the rules table. */
1006         rte_hash_reset(lpm->rules_tbl);
1007 }