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