lib/librte_lpm/rte_lpm6.c

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