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