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