lib/librte_lpm/rte_lpm6.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2013 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  */
  34 #include <string.h>
  35 #include <stdint.h>
  36 #include <errno.h>
  37 #include <stdarg.h>
  38 #include <stdio.h>
  39 #include <errno.h>
  40 #include <sys/queue.h>
  41
  42 #include <rte_log.h>
  43 #include <rte_branch_prediction.h>
  44 #include <rte_common.h>
  45 #include <rte_memory.h>
  46 #include <rte_malloc.h>
  47 #include <rte_memzone.h>
  48 #include <rte_memcpy.h>
  49 #include <rte_tailq.h>
  50 #include <rte_eal.h>
  51 #include <rte_eal_memconfig.h>
  52 #include <rte_per_lcore.h>
  53 #include <rte_string_fns.h>
  54 #include <rte_errno.h>
  55 #include <rte_rwlock.h>
  56 #include <rte_spinlock.h>
  57
  58 #include "rte_lpm6.h"
  59
  60 #define RTE_LPM6_TBL24_NUM_ENTRIES        (1 << 24)
  61 #define RTE_LPM6_TBL8_GROUP_NUM_ENTRIES         256
  62 #define RTE_LPM6_TBL8_MAX_NUM_GROUPS      (1 << 21)
  63
  64 #define RTE_LPM6_VALID_EXT_ENTRY_BITMASK 0xA0000000
  65 #define RTE_LPM6_LOOKUP_SUCCESS          0x20000000
  66 #define RTE_LPM6_TBL8_BITMASK            0x001FFFFF
  67
  68 #define ADD_FIRST_BYTE                            3
  69 #define LOOKUP_FIRST_BYTE                         4
  70 #define BYTE_SIZE                                 8
  71 #define BYTES2_SIZE                              16
  72
  73 #define lpm6_tbl8_gindex next_hop
  74
  75 /** Flags for setting an entry as valid/invalid. */
  76 enum valid_flag {
  77         INVALID = 0,
  78         VALID
  79 };
  80
  81 TAILQ_HEAD(rte_lpm6_list, rte_lpm6);
  82
  83 /** Tbl entry structure. It is the same for both tbl24 and tbl8 */
  84 struct rte_lpm6_tbl_entry {
  85         uint32_t next_hop:      21;  /**< Next hop / next table to be checked. */
  86         uint32_t depth  :8;      /**< Rule depth. */
  87
  88         /* Flags. */
  89         uint32_t valid     :1;   /**< Validation flag. */
  90         uint32_t valid_group :1; /**< Group validation flag. */
  91         uint32_t ext_entry :1;   /**< External entry. */
  92 };
  93
  94 /** Rules tbl entry structure. */
  95 struct rte_lpm6_rule {
  96         uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
  97         uint8_t next_hop; /**< Rule next hop. */
  98         uint8_t depth; /**< Rule depth. */
  99 };
 100
 101 /** LPM6 structure. */
 102 struct rte_lpm6 {
 103         TAILQ_ENTRY(rte_lpm6) next;      /**< Next in list. */
 104
 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         uint64_t mem_size, rules_size;
 154         struct rte_lpm6_list *lpm_list;
 155
 156         /* Check that we have an initialised tail queue */
 157         if ((lpm_list =
 158              RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_LPM6, rte_lpm6_list)) == NULL) {
 159                 rte_errno = E_RTE_NO_TAILQ;
 160                 return NULL;
 161         }
 162
 163         RTE_BUILD_BUG_ON(sizeof(struct rte_lpm6_tbl_entry) != sizeof(uint32_t));
 164
 165         /* Check user arguments. */
 166         if ((name == NULL) || (socket_id < -1) || (config == NULL) ||
 167                         (config->max_rules == 0) ||
 168                         config->number_tbl8s > RTE_LPM6_TBL8_MAX_NUM_GROUPS) {
 169                 rte_errno = EINVAL;
 170                 return NULL;
 171         }
 172
 173         rte_snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);
 174
 175         /* Determine the amount of memory to allocate. */
 176         mem_size = sizeof(*lpm) + (sizeof(lpm->tbl8[0]) *
 177                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s);
 178         rules_size = sizeof(struct rte_lpm6_rule) * config->max_rules;
 179
 180         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 181
 182         /* Guarantee there's no existing */
 183         TAILQ_FOREACH(lpm, lpm_list, next) {
 184                 if (strncmp(name, lpm->name, RTE_LPM6_NAMESIZE) == 0)
 185                         break;
 186         }
 187         if (lpm != NULL)
 188                 goto exit;
 189
 190         /* Allocate memory to store the LPM data structures. */
 191         lpm = (struct rte_lpm6 *)rte_zmalloc_socket(mem_name, (size_t)mem_size,
 192                         CACHE_LINE_SIZE, socket_id);
 193
 194         if (lpm == NULL) {
 195                 RTE_LOG(ERR, LPM, "LPM memory allocation failed\n");
 196                 goto exit;
 197         }
 198
 199         lpm->rules_tbl = (struct rte_lpm6_rule *)rte_zmalloc_socket(NULL,
 200                         (size_t)rules_size, CACHE_LINE_SIZE, socket_id);
 201
 202         if (lpm->rules_tbl == NULL) {
 203                 RTE_LOG(ERR, LPM, "LPM memory allocation failed\n");
 204                 rte_free(lpm);
 205                 goto exit;
 206         }
 207
 208         /* Save user arguments. */
 209         lpm->max_rules = config->max_rules;
 210         lpm->number_tbl8s = config->number_tbl8s;
 211         rte_snprintf(lpm->name, sizeof(lpm->name), "%s", name);
 212
 213         TAILQ_INSERT_TAIL(lpm_list, lpm, next);
 214
 215 exit:
 216         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 217
 218         return lpm;
 219 }
 220
 221 /*
 222  * Find an existing lpm table and return a pointer to it.
 223  */
 224 struct rte_lpm6 *
 225 rte_lpm6_find_existing(const char *name)
 226 {
 227         struct rte_lpm6 *l;
 228         struct rte_lpm6_list *lpm_list;
 229
 230         /* Check that we have an initialised tail queue */
 231         if ((lpm_list = RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_LPM6,
 232                         rte_lpm6_list)) == NULL) {
 233                 rte_errno = E_RTE_NO_TAILQ;
 234                 return NULL;
 235         }
 236
 237         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
 238         TAILQ_FOREACH(l, lpm_list, next) {
 239                 if (strncmp(name, l->name, RTE_LPM6_NAMESIZE) == 0)
 240                         break;
 241         }
 242         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
 243
 244         if (l == NULL)
 245                 rte_errno = ENOENT;
 246
 247         return l;
 248 }
 249
 250 /*
 251  * Deallocates memory for given LPM table.
 252  */
 253 void
 254 rte_lpm6_free(struct rte_lpm6 *lpm)
 255 {
 256         /* Check user arguments. */
 257         if (lpm == NULL)
 258                 return;
 259
 260         RTE_EAL_TAILQ_REMOVE(RTE_TAILQ_LPM6, rte_lpm6_list, lpm);
 261         rte_free(lpm->rules_tbl);
 262         rte_free(lpm);
 263 }
 264
 265 /*
 266  * Checks if a rule already exists in the rules table and updates
 267  * the nexthop if so. Otherwise it adds a new rule if enough space is available.
 268  */
 269 static inline int32_t
 270 rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t next_hop, uint8_t depth)
 271 {
 272         uint32_t rule_index;
 273
 274         /* Scan through rule list to see if rule already exists. */
 275         for (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {
 276
 277                 /* If rule already exists update its next_hop and return. */
 278                 if ((memcmp (lpm->rules_tbl[rule_index].ip, ip,
 279                                 RTE_LPM6_IPV6_ADDR_SIZE) == 0) &&
 280                                 lpm->rules_tbl[rule_index].depth == depth) {
 281                         lpm->rules_tbl[rule_index].next_hop = next_hop;
 282
 283                         return rule_index;
 284                 }
 285         }
 286
 287         /*
 288          * If rule does not exist check if there is space to add a new rule to
 289          * this rule group. If there is no space return error.
 290          */
 291         if (lpm->used_rules == lpm->max_rules) {
 292                 return -ENOSPC;
 293         }
 294
 295         /* If there is space for the new rule add it. */
 296         rte_memcpy(lpm->rules_tbl[rule_index].ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
 297         lpm->rules_tbl[rule_index].next_hop = next_hop;
 298         lpm->rules_tbl[rule_index].depth = depth;
 299
 300         /* Increment the used rules counter for this rule group. */
 301         lpm->used_rules++;
 302
 303         return rule_index;
 304 }
 305
 306 /*
 307  * Function that expands a rule across the data structure when a less-generic
 308  * one has been added before. It assures that every possible combination of bits
 309  * in the IP address returns a match.
 310  */
 311 static void
 312 expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
 313                 uint8_t next_hop)
 314 {
 315         uint32_t tbl8_group_end, tbl8_gindex_next, j;
 316
 317         tbl8_group_end = tbl8_gindex + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 318
 319         struct rte_lpm6_tbl_entry new_tbl8_entry = {
 320                 .valid = VALID,
 321                 .valid_group = VALID,
 322                 .depth = depth,
 323                 .next_hop = next_hop,
 324                 .ext_entry = 0,
 325         };
 326
 327         for (j = tbl8_gindex; j < tbl8_group_end; j++) {
 328                 if (!lpm->tbl8[j].valid || (lpm->tbl8[j].ext_entry == 0
 329                                 && lpm->tbl8[j].depth <= depth)) {
 330
 331                         lpm->tbl8[j] = new_tbl8_entry;
 332
 333                 } else if (lpm->tbl8[j].ext_entry == 1) {
 334
 335                         tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex
 336                                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 337                         expand_rule(lpm, tbl8_gindex_next, depth, next_hop);
 338                 }
 339         }
 340 }
 341
 342 /*
 343  * Partially adds a new route to the data structure (tbl24+tbl8s).
 344  * It returns 0 on success, a negative number on failure, or 1 if
 345  * the process needs to be continued by calling the function again.
 346  */
 347 static inline int
 348 add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
 349                 struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip, uint8_t bytes,
 350                 uint8_t first_byte, uint8_t depth, uint8_t next_hop)
 351 {
 352         uint32_t tbl_index, tbl_range, tbl8_group_start, tbl8_group_end, i;
 353         int32_t tbl8_gindex;
 354         int8_t bitshift;
 355         uint8_t bits_covered;
 356
 357         /*
 358          * Calculate index to the table based on the number and position
 359          * of the bytes being inspected in this step.
 360          */
 361         tbl_index = 0;
 362         for (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {
 363                 bitshift = (int8_t)((bytes - i)*BYTE_SIZE);
 364
 365                 if (bitshift < 0) bitshift = 0;
 366                 tbl_index = tbl_index | ip[i-1] << bitshift;
 367         }
 368
 369         /* Number of bits covered in this step */
 370         bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);
 371
 372         /*
 373          * If depth if smaller than this number (ie this is the last step)
 374          * expand the rule across the relevant positions in the table.
 375          */
 376         if (depth <= bits_covered) {
 377                 tbl_range = 1 << (bits_covered - depth);
 378
 379                 for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
 380                         if (!tbl[i].valid || (tbl[i].ext_entry == 0 &&
 381                                         tbl[i].depth <= depth)) {
 382
 383                                 struct rte_lpm6_tbl_entry new_tbl_entry = {
 384                                         .next_hop = next_hop,
 385                                         .depth = depth,
 386                                         .valid = VALID,
 387                                         .valid_group = VALID,
 388                                         .ext_entry = 0,
 389                                 };
 390
 391                                 tbl[i] = new_tbl_entry;
 392
 393                         } else if (tbl[i].ext_entry == 1) {
 394
 395                                 /*
 396                                  * If tbl entry is valid and extended calculate the index
 397                                  * into next tbl8 and expand the rule across the data structure.
 398                                  */
 399                                 tbl8_gindex = tbl[i].lpm6_tbl8_gindex *
 400                                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 401                                 expand_rule(lpm, tbl8_gindex, depth, next_hop);
 402                         }
 403                 }
 404
 405                 return 0;
 406         }
 407         /*
 408          * If this is not the last step just fill one position
 409          * and calculate the index to the next table.
 410          */
 411         else {
 412                 /* If it's invalid a new tbl8 is needed */
 413                 if (!tbl[tbl_index].valid) {
 414                         if (lpm->next_tbl8 < lpm->number_tbl8s)
 415                                 tbl8_gindex = (lpm->next_tbl8)++;
 416                         else
 417                                 return -ENOSPC;
 418
 419                         struct rte_lpm6_tbl_entry new_tbl_entry = {
 420                                 .lpm6_tbl8_gindex = tbl8_gindex,
 421                                 .depth = 0,
 422                                 .valid = VALID,
 423                                 .valid_group = VALID,
 424                                 .ext_entry = 1,
 425                         };
 426
 427                         tbl[tbl_index] = new_tbl_entry;
 428                 }
 429                 /*
 430                  * If it's valid but not extended the rule that was stored *
 431                  * here needs to be moved to the next table.
 432                  */
 433                 else if (tbl[tbl_index].ext_entry == 0) {
 434                         /* Search for free tbl8 group. */
 435                         if (lpm->next_tbl8 < lpm->number_tbl8s)
 436                                 tbl8_gindex = (lpm->next_tbl8)++;
 437                         else
 438                                 return -ENOSPC;
 439
 440                         tbl8_group_start = tbl8_gindex *
 441                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 442                         tbl8_group_end = tbl8_group_start +
 443                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
 444
 445                         /* Populate new tbl8 with tbl value. */
 446                         for (i = tbl8_group_start; i < tbl8_group_end; i++) {
 447                                 lpm->tbl8[i].valid = VALID;
 448                                 lpm->tbl8[i].depth = tbl[tbl_index].depth;
 449                                 lpm->tbl8[i].next_hop = tbl[tbl_index].next_hop;
 450                                 lpm->tbl8[i].ext_entry = 0;
 451                         }
 452
 453                         /*
 454                          * Update tbl entry to point to new tbl8 entry. Note: The
 455                          * ext_flag and tbl8_index need to be updated simultaneously,
 456                          * so assign whole structure in one go.
 457                          */
 458                         struct rte_lpm6_tbl_entry new_tbl_entry = {
 459                                 .lpm6_tbl8_gindex = tbl8_gindex,
 460                                 .depth = 0,
 461                                 .valid = VALID,
 462                                 .valid_group = VALID,
 463                                 .ext_entry = 1,
 464                         };
 465
 466                         tbl[tbl_index] = new_tbl_entry;
 467                 }
 468
 469                 *tbl_next = &(lpm->tbl8[tbl[tbl_index].lpm6_tbl8_gindex *
 470                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
 471         }
 472
 473         return 1;
 474 }
 475
 476 /*
 477  * Add a route
 478  */
 479 int
 480 rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
 481                 uint8_t next_hop)
 482 {
 483         struct rte_lpm6_tbl_entry *tbl;
 484         struct rte_lpm6_tbl_entry *tbl_next;
 485         int32_t rule_index;
 486         int status;
 487         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
 488         int i;
 489
 490         /* Check user arguments. */
 491         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
 492                 return -EINVAL;
 493
 494         /* Copy the IP and mask it to avoid modifying user's input data. */
 495         memcpy(masked_ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
 496         mask_ip(masked_ip, depth);
 497
 498         /* Add the rule to the rule table. */
 499         rule_index = rule_add(lpm, masked_ip, next_hop, depth);
 500
 501         /* If there is no space available for new rule return error. */
 502         if (rule_index < 0) {
 503                 return rule_index;
 504         }
 505
 506         /* Inspect the first three bytes through tbl24 on the first step. */
 507         tbl = lpm->tbl24;
 508         status = add_step (lpm, tbl, &tbl_next, masked_ip, ADD_FIRST_BYTE, 1,
 509                         depth, next_hop);
 510         if (status < 0) {
 511                 rte_lpm6_delete(lpm, masked_ip, depth);
 512
 513                 return status;
 514         }
 515
 516         /*
 517          * Inspect one by one the rest of the bytes until
 518          * the process is completed.
 519          */
 520         for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && status == 1; i++) {
 521                 tbl = tbl_next;
 522                 status = add_step (lpm, tbl, &tbl_next, masked_ip, 1, (uint8_t)(i+1),
 523                                 depth, next_hop);
 524                 if (status < 0) {
 525                         rte_lpm6_delete(lpm, masked_ip, depth);
 526
 527                         return status;
 528                 }
 529         }
 530
 531         return status;
 532 }
 533
 534 /*
 535  * Takes a pointer to a table entry and inspect one level.
 536  * The function returns 0 on lookup success, ENOENT if no match was found
 537  * or 1 if the process needs to be continued by calling the function again.
 538  */
 539 static inline int
 540 lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
 541                 const struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip,
 542                 uint8_t first_byte, uint8_t *next_hop)
 543 {
 544         uint32_t tbl8_index, tbl_entry;
 545
 546         /* Take the integer value from the pointer. */
 547         tbl_entry = *(const uint32_t *)tbl;
 548
 549         /* If it is valid and extended we calculate the new pointer to return. */
 550         if ((tbl_entry & RTE_LPM6_VALID_EXT_ENTRY_BITMASK) ==
 551                         RTE_LPM6_VALID_EXT_ENTRY_BITMASK) {
 552
 553                 tbl8_index = ip[first_byte-1] +
 554                                 ((tbl_entry & RTE_LPM6_TBL8_BITMASK) *
 555                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES);
 556
 557                 *tbl_next = &lpm->tbl8[tbl8_index];
 558
 559                 return 1;
 560         } else {
 561                 /* If not extended then we can have a match. */
 562                 *next_hop = (uint8_t)tbl_entry;
 563                 return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT;
 564         }
 565 }
 566
 567 /*
 568  * Looks up an IP
 569  */
 570 int
 571 rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
 572 {
 573         const struct rte_lpm6_tbl_entry *tbl;
 574         const struct rte_lpm6_tbl_entry *tbl_next;
 575         int status;
 576         uint8_t first_byte;
 577         uint32_t tbl24_index;
 578
 579         /* DEBUG: Check user input arguments. */
 580         if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL)) {
 581                 return -EINVAL;
 582         }
 583
 584         first_byte = LOOKUP_FIRST_BYTE;
 585         tbl24_index = (ip[0] << BYTES2_SIZE) | (ip[1] << BYTE_SIZE) | ip[2];
 586
 587         /* Calculate pointer to the first entry to be inspected */
 588         tbl = &lpm->tbl24[tbl24_index];
 589
 590         do {
 591                 /* Continue inspecting following levels until success or failure */
 592                 status = lookup_step(lpm, tbl, &tbl_next, ip, first_byte++, next_hop);
 593                 tbl = tbl_next;
 594         } while (status == 1);
 595
 596         return status;
 597 }
 598
 599 /*
 600  * Looks up a group of IP addresses
 601  */
 602 int
 603 rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
 604                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
 605                 int16_t * next_hops, unsigned n)
 606 {
 607         unsigned i;
 608         const struct rte_lpm6_tbl_entry *tbl;
 609         const struct rte_lpm6_tbl_entry *tbl_next;
 610         uint32_t tbl24_index;
 611         uint8_t first_byte, next_hop;
 612         int status;
 613
 614         /* DEBUG: Check user input arguments. */
 615         if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL)) {
 616                 return -EINVAL;
 617         }
 618
 619         for (i = 0; i < n; i++) {
 620                 first_byte = LOOKUP_FIRST_BYTE;
 621                 tbl24_index = (ips[i][0] << BYTES2_SIZE) |
 622                                 (ips[i][1] << BYTE_SIZE) | ips[i][2];
 623
 624                 /* Calculate pointer to the first entry to be inspected */
 625                 tbl = &lpm->tbl24[tbl24_index];
 626
 627                 do {
 628                         /* Continue inspecting following levels until success or failure */
 629                         status = lookup_step(lpm, tbl, &tbl_next, ips[i], first_byte++,
 630                                         &next_hop);
 631                         tbl = tbl_next;
 632                 } while (status == 1);
 633
 634                 if (status < 0)
 635                         next_hops[i] = -1;
 636                 else
 637                         next_hops[i] = next_hop;
 638         }
 639
 640         return 0;
 641 }
 642
 643 /*
 644  * Finds a rule in rule table.
 645  * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
 646  */
 647 static inline int32_t
 648 rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
 649 {
 650         uint32_t rule_index;
 651
 652         /* Scan used rules at given depth to find rule. */
 653         for (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {
 654                 /* If rule is found return the rule index. */
 655                 if ((memcmp (lpm->rules_tbl[rule_index].ip, ip,
 656                                 RTE_LPM6_IPV6_ADDR_SIZE) == 0) &&
 657                                 lpm->rules_tbl[rule_index].depth == depth) {
 658
 659                         return rule_index;
 660                 }
 661         }
 662
 663         /* If rule is not found return -ENOENT. */
 664         return -ENOENT;
 665 }
 666
 667 /*
 668  * Delete a rule from the rule table.
 669  * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
 670  */
 671 static inline void
 672 rule_delete(struct rte_lpm6 *lpm, int32_t rule_index)
 673 {
 674         /*
 675          * Overwrite redundant rule with last rule in group and decrement rule
 676          * counter.
 677          */
 678         lpm->rules_tbl[rule_index] = lpm->rules_tbl[lpm->used_rules-1];
 679         lpm->used_rules--;
 680 }
 681
 682 /*
 683  * Deletes a rule
 684  */
 685 int
 686 rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
 687 {
 688         int32_t rule_to_delete_index;
 689         uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
 690         unsigned i;
 691
 692         /*
 693          * Check input arguments.
 694          */
 695         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) {
 696                 return -EINVAL;
 697         }
 698
 699         /* Copy the IP and mask it to avoid modifying user's input data. */
 700         memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
 701         mask_ip(ip_masked, depth);
 702
 703         /*
 704          * Find the index of the input rule, that needs to be deleted, in the
 705          * rule table.
 706          */
 707         rule_to_delete_index = rule_find(lpm, ip_masked, depth);
 708
 709         /*
 710          * Check if rule_to_delete_index was found. If no rule was found the
 711          * function rule_find returns -ENOENT.
 712          */
 713         if (rule_to_delete_index < 0)
 714                 return rule_to_delete_index;
 715
 716         /* Delete the rule from the rule table. */
 717         rule_delete(lpm, rule_to_delete_index);
 718
 719         /*
 720          * Set all the table entries to 0 (ie delete every rule
 721          * from the data structure.
 722          */
 723         lpm->next_tbl8 = 0;
 724         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
 725         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
 726                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
 727
 728         /*
 729          * Add every rule again (except for the one that was removed from
 730          * the rules table).
 731          */
 732         for (i = 0; i < lpm->used_rules; i++) {
 733                 rte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,
 734                                 lpm->rules_tbl[i].next_hop);
 735         }
 736
 737         return 0;
 738 }
 739
 740 /*
 741  * Deletes a group of rules
 742  */
 743 int
 744 rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
 745                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, unsigned n)
 746 {
 747         int32_t rule_to_delete_index;
 748         uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
 749         unsigned i;
 750
 751         /*
 752          * Check input arguments.
 753          */
 754         if ((lpm == NULL) || (ips == NULL) || (depths == NULL)) {
 755                 return -EINVAL;
 756         }
 757
 758         for (i = 0; i < n; i++) {
 759                 /* Copy the IP and mask it to avoid modifying user's input data. */
 760                 memcpy(ip_masked, ips[i], RTE_LPM6_IPV6_ADDR_SIZE);
 761                 mask_ip(ip_masked, depths[i]);
 762
 763                 /*
 764                  * Find the index of the input rule, that needs to be deleted, in the
 765                  * rule table.
 766                  */
 767                 rule_to_delete_index = rule_find(lpm, ip_masked, depths[i]);
 768
 769                 /*
 770                  * Check if rule_to_delete_index was found. If no rule was found the
 771                  * function rule_find returns -ENOENT.
 772                  */
 773                 if (rule_to_delete_index < 0)
 774                         continue;
 775
 776                 /* Delete the rule from the rule table. */
 777                 rule_delete(lpm, rule_to_delete_index);
 778         }
 779
 780         /*
 781          * Set all the table entries to 0 (ie delete every rule
 782          * from the data structure.
 783          */
 784         lpm->next_tbl8 = 0;
 785         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
 786         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
 787                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
 788
 789         /*
 790          * Add every rule again (except for the ones that were removed from
 791          * the rules table).
 792          */
 793         for (i = 0; i < lpm->used_rules; i++) {
 794                 rte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,
 795                                 lpm->rules_tbl[i].next_hop);
 796         }
 797
 798         return 0;
 799 }
 800
 801 /*
 802  * Delete all rules from the LPM table.
 803  */
 804 void
 805 rte_lpm6_delete_all(struct rte_lpm6 *lpm)
 806 {
 807         /* Zero used rules counter. */
 808         lpm->used_rules = 0;
 809
 810         /* Zero next tbl8 index. */
 811         lpm->next_tbl8 = 0;
 812
 813         /* Zero tbl24. */
 814         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
 815
 816         /* Zero tbl8. */
 817         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *
 818                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
 819
 820         /* Delete all rules form the rules table. */
 821         memset(lpm->rules_tbl, 0, sizeof(struct rte_lpm6_rule) * lpm->max_rules);
 822 }