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