lib/librte_lpm/rte_lpm.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2014 Intel Corporation
   3  */
   4
   5 #include <string.h>
   6 #include <stdint.h>
   7 #include <errno.h>
   8 #include <stdarg.h>
   9 #include <stdio.h>
  10 #include <sys/queue.h>
  11
  12 #include <rte_log.h>
  13 #include <rte_branch_prediction.h>
  14 #include <rte_common.h>
  15 #include <rte_memory.h>        /* for definition of RTE_CACHE_LINE_SIZE */
  16 #include <rte_malloc.h>
  17 #include <rte_eal.h>
  18 #include <rte_eal_memconfig.h>
  19 #include <rte_per_lcore.h>
  20 #include <rte_string_fns.h>
  21 #include <rte_errno.h>
  22 #include <rte_rwlock.h>
  23 #include <rte_spinlock.h>
  24
  25 #include "rte_lpm.h"
  26
  27 TAILQ_HEAD(rte_lpm_list, rte_tailq_entry);
  28
  29 static struct rte_tailq_elem rte_lpm_tailq = {
  30         .name = "RTE_LPM",
  31 };
  32 EAL_REGISTER_TAILQ(rte_lpm_tailq)
  33
  34 #define MAX_DEPTH_TBL24 24
  35
  36 enum valid_flag {
  37         INVALID = 0,
  38         VALID
  39 };
  40
  41 /* Macro to enable/disable run-time checks. */
  42 #if defined(RTE_LIBRTE_LPM_DEBUG)
  43 #include <rte_debug.h>
  44 #define VERIFY_DEPTH(depth) do {                                \
  45         if ((depth == 0) || (depth > RTE_LPM_MAX_DEPTH))        \
  46                 rte_panic("LPM: Invalid depth (%u) at line %d", \
  47                                 (unsigned)(depth), __LINE__);   \
  48 } while (0)
  49 #else
  50 #define VERIFY_DEPTH(depth)
  51 #endif
  52
  53 /*
  54  * Converts a given depth value to its corresponding mask value.
  55  *
  56  * depth  (IN)          : range = 1 - 32
  57  * mask   (OUT)         : 32bit mask
  58  */
  59 static uint32_t __attribute__((pure))
  60 depth_to_mask(uint8_t depth)
  61 {
  62         VERIFY_DEPTH(depth);
  63
  64         /* To calculate a mask start with a 1 on the left hand side and right
  65          * shift while populating the left hand side with 1's
  66          */
  67         return (int)0x80000000 >> (depth - 1);
  68 }
  69
  70 /*
  71  * Converts given depth value to its corresponding range value.
  72  */
  73 static inline uint32_t __attribute__((pure))
  74 depth_to_range(uint8_t depth)
  75 {
  76         VERIFY_DEPTH(depth);
  77
  78         /*
  79          * Calculate tbl24 range. (Note: 2^depth = 1 << depth)
  80          */
  81         if (depth <= MAX_DEPTH_TBL24)
  82                 return 1 << (MAX_DEPTH_TBL24 - depth);
  83
  84         /* Else if depth is greater than 24 */
  85         return 1 << (RTE_LPM_MAX_DEPTH - depth);
  86 }
  87
  88 /*
  89  * Find an existing lpm table and return a pointer to it.
  90  */
  91 struct rte_lpm_v20 *
  92 rte_lpm_find_existing_v20(const char *name)
  93 {
  94         struct rte_lpm_v20 *l = NULL;
  95         struct rte_tailq_entry *te;
  96         struct rte_lpm_list *lpm_list;
  97
  98         lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);
  99
 100         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
 101         TAILQ_FOREACH(te, lpm_list, next) {
 102                 l = te->data;
 103                 if (strncmp(name, l->name, RTE_LPM_NAMESIZE) == 0)
 104                         break;
 105         }
 106         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
 107
 108         if (te == NULL) {
 109                 rte_errno = ENOENT;
 110                 return NULL;
 111         }
 112
 113         return l;
 114 }
 115 VERSION_SYMBOL(rte_lpm_find_existing, _v20, 2.0);
 116
 117 struct rte_lpm *
 118 rte_lpm_find_existing_v1604(const char *name)
 119 {
 120         struct rte_lpm *l = NULL;
 121         struct rte_tailq_entry *te;
 122         struct rte_lpm_list *lpm_list;
 123
 124         lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);
 125
 126         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
 127         TAILQ_FOREACH(te, lpm_list, next) {
 128                 l = te->data;
 129                 if (strncmp(name, l->name, RTE_LPM_NAMESIZE) == 0)
 130                         break;
 131         }
 132         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
 133
 134         if (te == NULL) {
 135                 rte_errno = ENOENT;
 136                 return NULL;
 137         }
 138
 139         return l;
 140 }
 141 BIND_DEFAULT_SYMBOL(rte_lpm_find_existing, _v1604, 16.04);
 142 MAP_STATIC_SYMBOL(struct rte_lpm *rte_lpm_find_existing(const char *name),
 143                 rte_lpm_find_existing_v1604);
 144
 145 /*
 146  * Allocates memory for LPM object
 147  */
 148 struct rte_lpm_v20 *
 149 rte_lpm_create_v20(const char *name, int socket_id, int max_rules,
 150                 __rte_unused int flags)
 151 {
 152         char mem_name[RTE_LPM_NAMESIZE];
 153         struct rte_lpm_v20 *lpm = NULL;
 154         struct rte_tailq_entry *te;
 155         uint32_t mem_size;
 156         struct rte_lpm_list *lpm_list;
 157
 158         lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);
 159
 160         RTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl_entry_v20) != 2);
 161
 162         /* Check user arguments. */
 163         if ((name == NULL) || (socket_id < -1) || (max_rules == 0)) {
 164                 rte_errno = EINVAL;
 165                 return NULL;
 166         }
 167
 168         snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);
 169
 170         /* Determine the amount of memory to allocate. */
 171         mem_size = sizeof(*lpm) + (sizeof(lpm->rules_tbl[0]) * max_rules);
 172
 173         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 174
 175         /* guarantee there's no existing */
 176         TAILQ_FOREACH(te, lpm_list, next) {
 177                 lpm = te->data;
 178                 if (strncmp(name, lpm->name, RTE_LPM_NAMESIZE) == 0)
 179                         break;
 180         }
 181
 182         if (te != NULL) {
 183                 lpm = NULL;
 184                 rte_errno = EEXIST;
 185                 goto exit;
 186         }
 187
 188         /* allocate tailq entry */
 189         te = rte_zmalloc("LPM_TAILQ_ENTRY", sizeof(*te), 0);
 190         if (te == NULL) {
 191                 RTE_LOG(ERR, LPM, "Failed to allocate tailq entry\n");
 192                 rte_errno = ENOMEM;
 193                 goto exit;
 194         }
 195
 196         /* Allocate memory to store the LPM data structures. */
 197         lpm = rte_zmalloc_socket(mem_name, mem_size,
 198                         RTE_CACHE_LINE_SIZE, socket_id);
 199         if (lpm == NULL) {
 200                 RTE_LOG(ERR, LPM, "LPM memory allocation failed\n");
 201                 rte_free(te);
 202                 rte_errno = ENOMEM;
 203                 goto exit;
 204         }
 205
 206         /* Save user arguments. */
 207         lpm->max_rules = max_rules;
 208         snprintf(lpm->name, sizeof(lpm->name), "%s", name);
 209
 210         te->data = lpm;
 211
 212         TAILQ_INSERT_TAIL(lpm_list, te, next);
 213
 214 exit:
 215         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 216
 217         return lpm;
 218 }
 219 VERSION_SYMBOL(rte_lpm_create, _v20, 2.0);
 220
 221 struct rte_lpm *
 222 rte_lpm_create_v1604(const char *name, int socket_id,
 223                 const struct rte_lpm_config *config)
 224 {
 225         char mem_name[RTE_LPM_NAMESIZE];
 226         struct rte_lpm *lpm = NULL;
 227         struct rte_tailq_entry *te;
 228         uint32_t mem_size, rules_size, tbl8s_size;
 229         struct rte_lpm_list *lpm_list;
 230
 231         lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);
 232
 233         RTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl_entry) != 4);
 234
 235         /* Check user arguments. */
 236         if ((name == NULL) || (socket_id < -1) || (config->max_rules == 0)
 237                         || config->number_tbl8s > RTE_LPM_MAX_TBL8_NUM_GROUPS) {
 238                 rte_errno = EINVAL;
 239                 return NULL;
 240         }
 241
 242         snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);
 243
 244         /* Determine the amount of memory to allocate. */
 245         mem_size = sizeof(*lpm);
 246         rules_size = sizeof(struct rte_lpm_rule) * config->max_rules;
 247         tbl8s_size = (sizeof(struct rte_lpm_tbl_entry) *
 248                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s);
 249
 250         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 251
 252         /* guarantee there's no existing */
 253         TAILQ_FOREACH(te, lpm_list, next) {
 254                 lpm = te->data;
 255                 if (strncmp(name, lpm->name, RTE_LPM_NAMESIZE) == 0)
 256                         break;
 257         }
 258
 259         if (te != NULL) {
 260                 lpm = NULL;
 261                 rte_errno = EEXIST;
 262                 goto exit;
 263         }
 264
 265         /* allocate tailq entry */
 266         te = rte_zmalloc("LPM_TAILQ_ENTRY", sizeof(*te), 0);
 267         if (te == NULL) {
 268                 RTE_LOG(ERR, LPM, "Failed to allocate tailq entry\n");
 269                 rte_errno = ENOMEM;
 270                 goto exit;
 271         }
 272
 273         /* Allocate memory to store the LPM data structures. */
 274         lpm = rte_zmalloc_socket(mem_name, mem_size,
 275                         RTE_CACHE_LINE_SIZE, socket_id);
 276         if (lpm == NULL) {
 277                 RTE_LOG(ERR, LPM, "LPM memory allocation failed\n");
 278                 rte_free(te);
 279                 rte_errno = ENOMEM;
 280                 goto exit;
 281         }
 282
 283         lpm->rules_tbl = rte_zmalloc_socket(NULL,
 284                         (size_t)rules_size, RTE_CACHE_LINE_SIZE, socket_id);
 285
 286         if (lpm->rules_tbl == NULL) {
 287                 RTE_LOG(ERR, LPM, "LPM rules_tbl memory allocation failed\n");
 288                 rte_free(lpm);
 289                 lpm = NULL;
 290                 rte_free(te);
 291                 rte_errno = ENOMEM;
 292                 goto exit;
 293         }
 294
 295         lpm->tbl8 = rte_zmalloc_socket(NULL,
 296                         (size_t)tbl8s_size, RTE_CACHE_LINE_SIZE, socket_id);
 297
 298         if (lpm->tbl8 == NULL) {
 299                 RTE_LOG(ERR, LPM, "LPM tbl8 memory allocation failed\n");
 300                 rte_free(lpm->rules_tbl);
 301                 rte_free(lpm);
 302                 lpm = NULL;
 303                 rte_free(te);
 304                 rte_errno = ENOMEM;
 305                 goto exit;
 306         }
 307
 308         /* Save user arguments. */
 309         lpm->max_rules = config->max_rules;
 310         lpm->number_tbl8s = config->number_tbl8s;
 311         snprintf(lpm->name, sizeof(lpm->name), "%s", name);
 312
 313         te->data = lpm;
 314
 315         TAILQ_INSERT_TAIL(lpm_list, te, next);
 316
 317 exit:
 318         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 319
 320         return lpm;
 321 }
 322 BIND_DEFAULT_SYMBOL(rte_lpm_create, _v1604, 16.04);
 323 MAP_STATIC_SYMBOL(
 324         struct rte_lpm *rte_lpm_create(const char *name, int socket_id,
 325                         const struct rte_lpm_config *config), rte_lpm_create_v1604);
 326
 327 /*
 328  * Deallocates memory for given LPM table.
 329  */
 330 void
 331 rte_lpm_free_v20(struct rte_lpm_v20 *lpm)
 332 {
 333         struct rte_lpm_list *lpm_list;
 334         struct rte_tailq_entry *te;
 335
 336         /* Check user arguments. */
 337         if (lpm == NULL)
 338                 return;
 339
 340         lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);
 341
 342         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 343
 344         /* find our tailq entry */
 345         TAILQ_FOREACH(te, lpm_list, next) {
 346                 if (te->data == (void *) lpm)
 347                         break;
 348         }
 349         if (te != NULL)
 350                 TAILQ_REMOVE(lpm_list, te, next);
 351
 352         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 353
 354         rte_free(lpm);
 355         rte_free(te);
 356 }
 357 VERSION_SYMBOL(rte_lpm_free, _v20, 2.0);
 358
 359 void
 360 rte_lpm_free_v1604(struct rte_lpm *lpm)
 361 {
 362         struct rte_lpm_list *lpm_list;
 363         struct rte_tailq_entry *te;
 364
 365         /* Check user arguments. */
 366         if (lpm == NULL)
 367                 return;
 368
 369         lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);
 370
 371         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 372
 373         /* find our tailq entry */
 374         TAILQ_FOREACH(te, lpm_list, next) {
 375                 if (te->data == (void *) lpm)
 376                         break;
 377         }
 378         if (te != NULL)
 379                 TAILQ_REMOVE(lpm_list, te, next);
 380
 381         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 382
 383         rte_free(lpm->tbl8);
 384         rte_free(lpm->rules_tbl);
 385         rte_free(lpm);
 386         rte_free(te);
 387 }
 388 BIND_DEFAULT_SYMBOL(rte_lpm_free, _v1604, 16.04);
 389 MAP_STATIC_SYMBOL(void rte_lpm_free(struct rte_lpm *lpm),
 390                 rte_lpm_free_v1604);
 391
 392 /*
 393  * Adds a rule to the rule table.
 394  *
 395  * NOTE: The rule table is split into 32 groups. Each group contains rules that
 396  * apply to a specific prefix depth (i.e. group 1 contains rules that apply to
 397  * prefixes with a depth of 1 etc.). In the following code (depth - 1) is used
 398  * to refer to depth 1 because even though the depth range is 1 - 32, depths
 399  * are stored in the rule table from 0 - 31.
 400  * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.
 401  */
 402 static inline int32_t
 403 rule_add_v20(struct rte_lpm_v20 *lpm, uint32_t ip_masked, uint8_t depth,
 404         uint8_t next_hop)
 405 {
 406         uint32_t rule_gindex, rule_index, last_rule;
 407         int i;
 408
 409         VERIFY_DEPTH(depth);
 410
 411         /* Scan through rule group to see if rule already exists. */
 412         if (lpm->rule_info[depth - 1].used_rules > 0) {
 413
 414                 /* rule_gindex stands for rule group index. */
 415                 rule_gindex = lpm->rule_info[depth - 1].first_rule;
 416                 /* Initialise rule_index to point to start of rule group. */
 417                 rule_index = rule_gindex;
 418                 /* Last rule = Last used rule in this rule group. */
 419                 last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;
 420
 421                 for (; rule_index < last_rule; rule_index++) {
 422
 423                         /* If rule already exists update its next_hop and return. */
 424                         if (lpm->rules_tbl[rule_index].ip == ip_masked) {
 425                                 lpm->rules_tbl[rule_index].next_hop = next_hop;
 426
 427                                 return rule_index;
 428                         }
 429                 }
 430
 431                 if (rule_index == lpm->max_rules)
 432                         return -ENOSPC;
 433         } else {
 434                 /* Calculate the position in which the rule will be stored. */
 435                 rule_index = 0;
 436
 437                 for (i = depth - 1; i > 0; i--) {
 438                         if (lpm->rule_info[i - 1].used_rules > 0) {
 439                                 rule_index = lpm->rule_info[i - 1].first_rule
 440                                                 + lpm->rule_info[i - 1].used_rules;
 441                                 break;
 442                         }
 443                 }
 444                 if (rule_index == lpm->max_rules)
 445                         return -ENOSPC;
 446
 447                 lpm->rule_info[depth - 1].first_rule = rule_index;
 448         }
 449
 450         /* Make room for the new rule in the array. */
 451         for (i = RTE_LPM_MAX_DEPTH; i > depth; i--) {
 452                 if (lpm->rule_info[i - 1].first_rule
 453                                 + lpm->rule_info[i - 1].used_rules == lpm->max_rules)
 454                         return -ENOSPC;
 455
 456                 if (lpm->rule_info[i - 1].used_rules > 0) {
 457                         lpm->rules_tbl[lpm->rule_info[i - 1].first_rule
 458                                 + lpm->rule_info[i - 1].used_rules]
 459                                         = lpm->rules_tbl[lpm->rule_info[i - 1].first_rule];
 460                         lpm->rule_info[i - 1].first_rule++;
 461                 }
 462         }
 463
 464         /* Add the new rule. */
 465         lpm->rules_tbl[rule_index].ip = ip_masked;
 466         lpm->rules_tbl[rule_index].next_hop = next_hop;
 467
 468         /* Increment the used rules counter for this rule group. */
 469         lpm->rule_info[depth - 1].used_rules++;
 470
 471         return rule_index;
 472 }
 473
 474 static inline int32_t
 475 rule_add_v1604(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,
 476         uint32_t next_hop)
 477 {
 478         uint32_t rule_gindex, rule_index, last_rule;
 479         int i;
 480
 481         VERIFY_DEPTH(depth);
 482
 483         /* Scan through rule group to see if rule already exists. */
 484         if (lpm->rule_info[depth - 1].used_rules > 0) {
 485
 486                 /* rule_gindex stands for rule group index. */
 487                 rule_gindex = lpm->rule_info[depth - 1].first_rule;
 488                 /* Initialise rule_index to point to start of rule group. */
 489                 rule_index = rule_gindex;
 490                 /* Last rule = Last used rule in this rule group. */
 491                 last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;
 492
 493                 for (; rule_index < last_rule; rule_index++) {
 494
 495                         /* If rule already exists update its next_hop and return. */
 496                         if (lpm->rules_tbl[rule_index].ip == ip_masked) {
 497                                 lpm->rules_tbl[rule_index].next_hop = next_hop;
 498
 499                                 return rule_index;
 500                         }
 501                 }
 502
 503                 if (rule_index == lpm->max_rules)
 504                         return -ENOSPC;
 505         } else {
 506                 /* Calculate the position in which the rule will be stored. */
 507                 rule_index = 0;
 508
 509                 for (i = depth - 1; i > 0; i--) {
 510                         if (lpm->rule_info[i - 1].used_rules > 0) {
 511                                 rule_index = lpm->rule_info[i - 1].first_rule
 512                                                 + lpm->rule_info[i - 1].used_rules;
 513                                 break;
 514                         }
 515                 }
 516                 if (rule_index == lpm->max_rules)
 517                         return -ENOSPC;
 518
 519                 lpm->rule_info[depth - 1].first_rule = rule_index;
 520         }
 521
 522         /* Make room for the new rule in the array. */
 523         for (i = RTE_LPM_MAX_DEPTH; i > depth; i--) {
 524                 if (lpm->rule_info[i - 1].first_rule
 525                                 + lpm->rule_info[i - 1].used_rules == lpm->max_rules)
 526                         return -ENOSPC;
 527
 528                 if (lpm->rule_info[i - 1].used_rules > 0) {
 529                         lpm->rules_tbl[lpm->rule_info[i - 1].first_rule
 530                                 + lpm->rule_info[i - 1].used_rules]
 531                                         = lpm->rules_tbl[lpm->rule_info[i - 1].first_rule];
 532                         lpm->rule_info[i - 1].first_rule++;
 533                 }
 534         }
 535
 536         /* Add the new rule. */
 537         lpm->rules_tbl[rule_index].ip = ip_masked;
 538         lpm->rules_tbl[rule_index].next_hop = next_hop;
 539
 540         /* Increment the used rules counter for this rule group. */
 541         lpm->rule_info[depth - 1].used_rules++;
 542
 543         return rule_index;
 544 }
 545
 546 /*
 547  * Delete a rule from the rule table.
 548  * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.
 549  */
 550 static inline void
 551 rule_delete_v20(struct rte_lpm_v20 *lpm, int32_t rule_index, uint8_t depth)
 552 {
 553         int i;
 554
 555         VERIFY_DEPTH(depth);
 556
 557         lpm->rules_tbl[rule_index] =
 558                         lpm->rules_tbl[lpm->rule_info[depth - 1].first_rule
 559                                 + lpm->rule_info[depth - 1].used_rules - 1];
 560
 561         for (i = depth; i < RTE_LPM_MAX_DEPTH; i++) {
 562                 if (lpm->rule_info[i].used_rules > 0) {
 563                         lpm->rules_tbl[lpm->rule_info[i].first_rule - 1] =
 564                                 lpm->rules_tbl[lpm->rule_info[i].first_rule
 565                                         + lpm->rule_info[i].used_rules - 1];
 566                         lpm->rule_info[i].first_rule--;
 567                 }
 568         }
 569
 570         lpm->rule_info[depth - 1].used_rules--;
 571 }
 572
 573 static inline void
 574 rule_delete_v1604(struct rte_lpm *lpm, int32_t rule_index, uint8_t depth)
 575 {
 576         int i;
 577
 578         VERIFY_DEPTH(depth);
 579
 580         lpm->rules_tbl[rule_index] =
 581                         lpm->rules_tbl[lpm->rule_info[depth - 1].first_rule
 582                         + lpm->rule_info[depth - 1].used_rules - 1];
 583
 584         for (i = depth; i < RTE_LPM_MAX_DEPTH; i++) {
 585                 if (lpm->rule_info[i].used_rules > 0) {
 586                         lpm->rules_tbl[lpm->rule_info[i].first_rule - 1] =
 587                                         lpm->rules_tbl[lpm->rule_info[i].first_rule
 588                                                 + lpm->rule_info[i].used_rules - 1];
 589                         lpm->rule_info[i].first_rule--;
 590                 }
 591         }
 592
 593         lpm->rule_info[depth - 1].used_rules--;
 594 }
 595
 596 /*
 597  * Finds a rule in rule table.
 598  * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.
 599  */
 600 static inline int32_t
 601 rule_find_v20(struct rte_lpm_v20 *lpm, uint32_t ip_masked, uint8_t depth)
 602 {
 603         uint32_t rule_gindex, last_rule, rule_index;
 604
 605         VERIFY_DEPTH(depth);
 606
 607         rule_gindex = lpm->rule_info[depth - 1].first_rule;
 608         last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;
 609
 610         /* Scan used rules at given depth to find rule. */
 611         for (rule_index = rule_gindex; rule_index < last_rule; rule_index++) {
 612                 /* If rule is found return the rule index. */
 613                 if (lpm->rules_tbl[rule_index].ip == ip_masked)
 614                         return rule_index;
 615         }
 616
 617         /* If rule is not found return -EINVAL. */
 618         return -EINVAL;
 619 }
 620
 621 static inline int32_t
 622 rule_find_v1604(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth)
 623 {
 624         uint32_t rule_gindex, last_rule, rule_index;
 625
 626         VERIFY_DEPTH(depth);
 627
 628         rule_gindex = lpm->rule_info[depth - 1].first_rule;
 629         last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;
 630
 631         /* Scan used rules at given depth to find rule. */
 632         for (rule_index = rule_gindex; rule_index < last_rule; rule_index++) {
 633                 /* If rule is found return the rule index. */
 634                 if (lpm->rules_tbl[rule_index].ip == ip_masked)
 635                         return rule_index;
 636         }
 637
 638         /* If rule is not found return -EINVAL. */
 639         return -EINVAL;
 640 }
 641
 642 /*
 643  * Find, clean and allocate a tbl8.
 644  */
 645 static inline int32_t
 646 tbl8_alloc_v20(struct rte_lpm_tbl_entry_v20 *tbl8)
 647 {
 648         uint32_t group_idx; /* tbl8 group index. */
 649         struct rte_lpm_tbl_entry_v20 *tbl8_entry;
 650
 651         /* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */
 652         for (group_idx = 0; group_idx < RTE_LPM_TBL8_NUM_GROUPS;
 653                         group_idx++) {
 654                 tbl8_entry = &tbl8[group_idx * RTE_LPM_TBL8_GROUP_NUM_ENTRIES];
 655                 /* If a free tbl8 group is found clean it and set as VALID. */
 656                 if (!tbl8_entry->valid_group) {
 657                         memset(&tbl8_entry[0], 0,
 658                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES *
 659                                         sizeof(tbl8_entry[0]));
 660
 661                         tbl8_entry->valid_group = VALID;
 662
 663                         /* Return group index for allocated tbl8 group. */
 664                         return group_idx;
 665                 }
 666         }
 667
 668         /* If there are no tbl8 groups free then return error. */
 669         return -ENOSPC;
 670 }
 671
 672 static inline int32_t
 673 tbl8_alloc_v1604(struct rte_lpm_tbl_entry *tbl8, uint32_t number_tbl8s)
 674 {
 675         uint32_t group_idx; /* tbl8 group index. */
 676         struct rte_lpm_tbl_entry *tbl8_entry;
 677
 678         /* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */
 679         for (group_idx = 0; group_idx < number_tbl8s; group_idx++) {
 680                 tbl8_entry = &tbl8[group_idx * RTE_LPM_TBL8_GROUP_NUM_ENTRIES];
 681                 /* If a free tbl8 group is found clean it and set as VALID. */
 682                 if (!tbl8_entry->valid_group) {
 683                         memset(&tbl8_entry[0], 0,
 684                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES *
 685                                         sizeof(tbl8_entry[0]));
 686
 687                         tbl8_entry->valid_group = VALID;
 688
 689                         /* Return group index for allocated tbl8 group. */
 690                         return group_idx;
 691                 }
 692         }
 693
 694         /* If there are no tbl8 groups free then return error. */
 695         return -ENOSPC;
 696 }
 697
 698 static inline void
 699 tbl8_free_v20(struct rte_lpm_tbl_entry_v20 *tbl8, uint32_t tbl8_group_start)
 700 {
 701         /* Set tbl8 group invalid*/
 702         tbl8[tbl8_group_start].valid_group = INVALID;
 703 }
 704
 705 static inline void
 706 tbl8_free_v1604(struct rte_lpm_tbl_entry *tbl8, uint32_t tbl8_group_start)
 707 {
 708         /* Set tbl8 group invalid*/
 709         tbl8[tbl8_group_start].valid_group = INVALID;
 710 }
 711
 712 static inline int32_t
 713 add_depth_small_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
 714                 uint8_t next_hop)
 715 {
 716         uint32_t tbl24_index, tbl24_range, tbl8_index, tbl8_group_end, i, j;
 717
 718         /* Calculate the index into Table24. */
 719         tbl24_index = ip >> 8;
 720         tbl24_range = depth_to_range(depth);
 721
 722         for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {
 723                 /*
 724                  * For invalid OR valid and non-extended tbl 24 entries set
 725                  * entry.
 726                  */
 727                 if (!lpm->tbl24[i].valid || (lpm->tbl24[i].valid_group == 0 &&
 728                                 lpm->tbl24[i].depth <= depth)) {
 729
 730                         struct rte_lpm_tbl_entry_v20 new_tbl24_entry = {
 731                                 .valid = VALID,
 732                                 .valid_group = 0,
 733                                 .depth = depth,
 734                         };
 735                         new_tbl24_entry.next_hop = next_hop;
 736
 737                         /* Setting tbl24 entry in one go to avoid race
 738                          * conditions
 739                          */
 740                         lpm->tbl24[i] = new_tbl24_entry;
 741
 742                         continue;
 743                 }
 744
 745                 if (lpm->tbl24[i].valid_group == 1) {
 746                         /* If tbl24 entry is valid and extended calculate the
 747                          *  index into tbl8.
 748                          */
 749                         tbl8_index = lpm->tbl24[i].group_idx *
 750                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 751                         tbl8_group_end = tbl8_index +
 752                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 753
 754                         for (j = tbl8_index; j < tbl8_group_end; j++) {
 755                                 if (!lpm->tbl8[j].valid ||
 756                                                 lpm->tbl8[j].depth <= depth) {
 757                                         struct rte_lpm_tbl_entry_v20
 758                                                 new_tbl8_entry = {
 759                                                 .valid = VALID,
 760                                                 .valid_group = VALID,
 761                                                 .depth = depth,
 762                                         };
 763                                         new_tbl8_entry.next_hop = next_hop;
 764
 765                                         /*
 766                                          * Setting tbl8 entry in one go to avoid
 767                                          * race conditions
 768                                          */
 769                                         lpm->tbl8[j] = new_tbl8_entry;
 770
 771                                         continue;
 772                                 }
 773                         }
 774                 }
 775         }
 776
 777         return 0;
 778 }
 779
 780 static inline int32_t
 781 add_depth_small_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
 782                 uint32_t next_hop)
 783 {
 784 #define group_idx next_hop
 785         uint32_t tbl24_index, tbl24_range, tbl8_index, tbl8_group_end, i, j;
 786
 787         /* Calculate the index into Table24. */
 788         tbl24_index = ip >> 8;
 789         tbl24_range = depth_to_range(depth);
 790
 791         for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {
 792                 /*
 793                  * For invalid OR valid and non-extended tbl 24 entries set
 794                  * entry.
 795                  */
 796                 if (!lpm->tbl24[i].valid || (lpm->tbl24[i].valid_group == 0 &&
 797                                 lpm->tbl24[i].depth <= depth)) {
 798
 799                         struct rte_lpm_tbl_entry new_tbl24_entry = {
 800                                 .next_hop = next_hop,
 801                                 .valid = VALID,
 802                                 .valid_group = 0,
 803                                 .depth = depth,
 804                         };
 805
 806                         /* Setting tbl24 entry in one go to avoid race
 807                          * conditions
 808                          */
 809                         lpm->tbl24[i] = new_tbl24_entry;
 810
 811                         continue;
 812                 }
 813
 814                 if (lpm->tbl24[i].valid_group == 1) {
 815                         /* If tbl24 entry is valid and extended calculate the
 816                          *  index into tbl8.
 817                          */
 818                         tbl8_index = lpm->tbl24[i].group_idx *
 819                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 820                         tbl8_group_end = tbl8_index +
 821                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 822
 823                         for (j = tbl8_index; j < tbl8_group_end; j++) {
 824                                 if (!lpm->tbl8[j].valid ||
 825                                                 lpm->tbl8[j].depth <= depth) {
 826                                         struct rte_lpm_tbl_entry
 827                                                 new_tbl8_entry = {
 828                                                 .valid = VALID,
 829                                                 .valid_group = VALID,
 830                                                 .depth = depth,
 831                                                 .next_hop = next_hop,
 832                                         };
 833
 834                                         /*
 835                                          * Setting tbl8 entry in one go to avoid
 836                                          * race conditions
 837                                          */
 838                                         lpm->tbl8[j] = new_tbl8_entry;
 839
 840                                         continue;
 841                                 }
 842                         }
 843                 }
 844         }
 845 #undef group_idx
 846         return 0;
 847 }
 848
 849 static inline int32_t
 850 add_depth_big_v20(struct rte_lpm_v20 *lpm, uint32_t ip_masked, uint8_t depth,
 851                 uint8_t next_hop)
 852 {
 853         uint32_t tbl24_index;
 854         int32_t tbl8_group_index, tbl8_group_start, tbl8_group_end, tbl8_index,
 855                 tbl8_range, i;
 856
 857         tbl24_index = (ip_masked >> 8);
 858         tbl8_range = depth_to_range(depth);
 859
 860         if (!lpm->tbl24[tbl24_index].valid) {
 861                 /* Search for a free tbl8 group. */
 862                 tbl8_group_index = tbl8_alloc_v20(lpm->tbl8);
 863
 864                 /* Check tbl8 allocation was successful. */
 865                 if (tbl8_group_index < 0) {
 866                         return tbl8_group_index;
 867                 }
 868
 869                 /* Find index into tbl8 and range. */
 870                 tbl8_index = (tbl8_group_index *
 871                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES) +
 872                                 (ip_masked & 0xFF);
 873
 874                 /* Set tbl8 entry. */
 875                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
 876                         lpm->tbl8[i].depth = depth;
 877                         lpm->tbl8[i].next_hop = next_hop;
 878                         lpm->tbl8[i].valid = VALID;
 879                 }
 880
 881                 /*
 882                  * Update tbl24 entry to point to new tbl8 entry. Note: The
 883                  * ext_flag and tbl8_index need to be updated simultaneously,
 884                  * so assign whole structure in one go
 885                  */
 886
 887                 struct rte_lpm_tbl_entry_v20 new_tbl24_entry = {
 888                         .group_idx = (uint8_t)tbl8_group_index,
 889                         .valid = VALID,
 890                         .valid_group = 1,
 891                         .depth = 0,
 892                 };
 893
 894                 lpm->tbl24[tbl24_index] = new_tbl24_entry;
 895
 896         } /* If valid entry but not extended calculate the index into Table8. */
 897         else if (lpm->tbl24[tbl24_index].valid_group == 0) {
 898                 /* Search for free tbl8 group. */
 899                 tbl8_group_index = tbl8_alloc_v20(lpm->tbl8);
 900
 901                 if (tbl8_group_index < 0) {
 902                         return tbl8_group_index;
 903                 }
 904
 905                 tbl8_group_start = tbl8_group_index *
 906                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 907                 tbl8_group_end = tbl8_group_start +
 908                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 909
 910                 /* Populate new tbl8 with tbl24 value. */
 911                 for (i = tbl8_group_start; i < tbl8_group_end; i++) {
 912                         lpm->tbl8[i].valid = VALID;
 913                         lpm->tbl8[i].depth = lpm->tbl24[tbl24_index].depth;
 914                         lpm->tbl8[i].next_hop =
 915                                         lpm->tbl24[tbl24_index].next_hop;
 916                 }
 917
 918                 tbl8_index = tbl8_group_start + (ip_masked & 0xFF);
 919
 920                 /* Insert new rule into the tbl8 entry. */
 921                 for (i = tbl8_index; i < tbl8_index + tbl8_range; i++) {
 922                         lpm->tbl8[i].valid = VALID;
 923                         lpm->tbl8[i].depth = depth;
 924                         lpm->tbl8[i].next_hop = next_hop;
 925                 }
 926
 927                 /*
 928                  * Update tbl24 entry to point to new tbl8 entry. Note: The
 929                  * ext_flag and tbl8_index need to be updated simultaneously,
 930                  * so assign whole structure in one go.
 931                  */
 932
 933                 struct rte_lpm_tbl_entry_v20 new_tbl24_entry = {
 934                                 .group_idx = (uint8_t)tbl8_group_index,
 935                                 .valid = VALID,
 936                                 .valid_group = 1,
 937                                 .depth = 0,
 938                 };
 939
 940                 lpm->tbl24[tbl24_index] = new_tbl24_entry;
 941
 942         } else { /*
 943                 * If it is valid, extended entry calculate the index into tbl8.
 944                 */
 945                 tbl8_group_index = lpm->tbl24[tbl24_index].group_idx;
 946                 tbl8_group_start = tbl8_group_index *
 947                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
 948                 tbl8_index = tbl8_group_start + (ip_masked & 0xFF);
 949
 950                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
 951
 952                         if (!lpm->tbl8[i].valid ||
 953                                         lpm->tbl8[i].depth <= depth) {
 954                                 struct rte_lpm_tbl_entry_v20 new_tbl8_entry = {
 955                                         .valid = VALID,
 956                                         .depth = depth,
 957                                         .valid_group = lpm->tbl8[i].valid_group,
 958                                 };
 959                                 new_tbl8_entry.next_hop = next_hop;
 960                                 /*
 961                                  * Setting tbl8 entry in one go to avoid race
 962                                  * condition
 963                                  */
 964                                 lpm->tbl8[i] = new_tbl8_entry;
 965
 966                                 continue;
 967                         }
 968                 }
 969         }
 970
 971         return 0;
 972 }
 973
 974 static inline int32_t
 975 add_depth_big_v1604(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,
 976                 uint32_t next_hop)
 977 {
 978 #define group_idx next_hop
 979         uint32_t tbl24_index;
 980         int32_t tbl8_group_index, tbl8_group_start, tbl8_group_end, tbl8_index,
 981                 tbl8_range, i;
 982
 983         tbl24_index = (ip_masked >> 8);
 984         tbl8_range = depth_to_range(depth);
 985
 986         if (!lpm->tbl24[tbl24_index].valid) {
 987                 /* Search for a free tbl8 group. */
 988                 tbl8_group_index = tbl8_alloc_v1604(lpm->tbl8, lpm->number_tbl8s);
 989
 990                 /* Check tbl8 allocation was successful. */
 991                 if (tbl8_group_index < 0) {
 992                         return tbl8_group_index;
 993                 }
 994
 995                 /* Find index into tbl8 and range. */
 996                 tbl8_index = (tbl8_group_index *
 997                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES) +
 998                                 (ip_masked & 0xFF);
 999
1000                 /* Set tbl8 entry. */
1001                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
1002                         lpm->tbl8[i].depth = depth;
1003                         lpm->tbl8[i].next_hop = next_hop;
1004                         lpm->tbl8[i].valid = VALID;
1005                 }
1006
1007                 /*
1008                  * Update tbl24 entry to point to new tbl8 entry. Note: The
1009                  * ext_flag and tbl8_index need to be updated simultaneously,
1010                  * so assign whole structure in one go
1011                  */
1012
1013                 struct rte_lpm_tbl_entry new_tbl24_entry = {
1014                         .group_idx = tbl8_group_index,
1015                         .valid = VALID,
1016                         .valid_group = 1,
1017                         .depth = 0,
1018                 };
1019
1020                 lpm->tbl24[tbl24_index] = new_tbl24_entry;
1021
1022         } /* If valid entry but not extended calculate the index into Table8. */
1023         else if (lpm->tbl24[tbl24_index].valid_group == 0) {
1024                 /* Search for free tbl8 group. */
1025                 tbl8_group_index = tbl8_alloc_v1604(lpm->tbl8, lpm->number_tbl8s);
1026
1027                 if (tbl8_group_index < 0) {
1028                         return tbl8_group_index;
1029                 }
1030
1031                 tbl8_group_start = tbl8_group_index *
1032                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1033                 tbl8_group_end = tbl8_group_start +
1034                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1035
1036                 /* Populate new tbl8 with tbl24 value. */
1037                 for (i = tbl8_group_start; i < tbl8_group_end; i++) {
1038                         lpm->tbl8[i].valid = VALID;
1039                         lpm->tbl8[i].depth = lpm->tbl24[tbl24_index].depth;
1040                         lpm->tbl8[i].next_hop =
1041                                         lpm->tbl24[tbl24_index].next_hop;
1042                 }
1043
1044                 tbl8_index = tbl8_group_start + (ip_masked & 0xFF);
1045
1046                 /* Insert new rule into the tbl8 entry. */
1047                 for (i = tbl8_index; i < tbl8_index + tbl8_range; i++) {
1048                         lpm->tbl8[i].valid = VALID;
1049                         lpm->tbl8[i].depth = depth;
1050                         lpm->tbl8[i].next_hop = next_hop;
1051                 }
1052
1053                 /*
1054                  * Update tbl24 entry to point to new tbl8 entry. Note: The
1055                  * ext_flag and tbl8_index need to be updated simultaneously,
1056                  * so assign whole structure in one go.
1057                  */
1058
1059                 struct rte_lpm_tbl_entry new_tbl24_entry = {
1060                                 .group_idx = tbl8_group_index,
1061                                 .valid = VALID,
1062                                 .valid_group = 1,
1063                                 .depth = 0,
1064                 };
1065
1066                 lpm->tbl24[tbl24_index] = new_tbl24_entry;
1067
1068         } else { /*
1069                 * If it is valid, extended entry calculate the index into tbl8.
1070                 */
1071                 tbl8_group_index = lpm->tbl24[tbl24_index].group_idx;
1072                 tbl8_group_start = tbl8_group_index *
1073                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1074                 tbl8_index = tbl8_group_start + (ip_masked & 0xFF);
1075
1076                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
1077
1078                         if (!lpm->tbl8[i].valid ||
1079                                         lpm->tbl8[i].depth <= depth) {
1080                                 struct rte_lpm_tbl_entry new_tbl8_entry = {
1081                                         .valid = VALID,
1082                                         .depth = depth,
1083                                         .next_hop = next_hop,
1084                                         .valid_group = lpm->tbl8[i].valid_group,
1085                                 };
1086
1087                                 /*
1088                                  * Setting tbl8 entry in one go to avoid race
1089                                  * condition
1090                                  */
1091                                 lpm->tbl8[i] = new_tbl8_entry;
1092
1093                                 continue;
1094                         }
1095                 }
1096         }
1097 #undef group_idx
1098         return 0;
1099 }
1100
1101 /*
1102  * Add a route
1103  */
1104 int
1105 rte_lpm_add_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
1106                 uint8_t next_hop)
1107 {
1108         int32_t rule_index, status = 0;
1109         uint32_t ip_masked;
1110
1111         /* Check user arguments. */
1112         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH))
1113                 return -EINVAL;
1114
1115         ip_masked = ip & depth_to_mask(depth);
1116
1117         /* Add the rule to the rule table. */
1118         rule_index = rule_add_v20(lpm, ip_masked, depth, next_hop);
1119
1120         /* If the is no space available for new rule return error. */
1121         if (rule_index < 0) {
1122                 return rule_index;
1123         }
1124
1125         if (depth <= MAX_DEPTH_TBL24) {
1126                 status = add_depth_small_v20(lpm, ip_masked, depth, next_hop);
1127         } else { /* If depth > RTE_LPM_MAX_DEPTH_TBL24 */
1128                 status = add_depth_big_v20(lpm, ip_masked, depth, next_hop);
1129
1130                 /*
1131                  * If add fails due to exhaustion of tbl8 extensions delete
1132                  * rule that was added to rule table.
1133                  */
1134                 if (status < 0) {
1135                         rule_delete_v20(lpm, rule_index, depth);
1136
1137                         return status;
1138                 }
1139         }
1140
1141         return 0;
1142 }
1143 VERSION_SYMBOL(rte_lpm_add, _v20, 2.0);
1144
1145 int
1146 rte_lpm_add_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
1147                 uint32_t next_hop)
1148 {
1149         int32_t rule_index, status = 0;
1150         uint32_t ip_masked;
1151
1152         /* Check user arguments. */
1153         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH))
1154                 return -EINVAL;
1155
1156         ip_masked = ip & depth_to_mask(depth);
1157
1158         /* Add the rule to the rule table. */
1159         rule_index = rule_add_v1604(lpm, ip_masked, depth, next_hop);
1160
1161         /* If the is no space available for new rule return error. */
1162         if (rule_index < 0) {
1163                 return rule_index;
1164         }
1165
1166         if (depth <= MAX_DEPTH_TBL24) {
1167                 status = add_depth_small_v1604(lpm, ip_masked, depth, next_hop);
1168         } else { /* If depth > RTE_LPM_MAX_DEPTH_TBL24 */
1169                 status = add_depth_big_v1604(lpm, ip_masked, depth, next_hop);
1170
1171                 /*
1172                  * If add fails due to exhaustion of tbl8 extensions delete
1173                  * rule that was added to rule table.
1174                  */
1175                 if (status < 0) {
1176                         rule_delete_v1604(lpm, rule_index, depth);
1177
1178                         return status;
1179                 }
1180         }
1181
1182         return 0;
1183 }
1184 BIND_DEFAULT_SYMBOL(rte_lpm_add, _v1604, 16.04);
1185 MAP_STATIC_SYMBOL(int rte_lpm_add(struct rte_lpm *lpm, uint32_t ip,
1186                 uint8_t depth, uint32_t next_hop), rte_lpm_add_v1604);
1187
1188 /*
1189  * Look for a rule in the high-level rules table
1190  */
1191 int
1192 rte_lpm_is_rule_present_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
1193 uint8_t *next_hop)
1194 {
1195         uint32_t ip_masked;
1196         int32_t rule_index;
1197
1198         /* Check user arguments. */
1199         if ((lpm == NULL) ||
1200                 (next_hop == NULL) ||
1201                 (depth < 1) || (depth > RTE_LPM_MAX_DEPTH))
1202                 return -EINVAL;
1203
1204         /* Look for the rule using rule_find. */
1205         ip_masked = ip & depth_to_mask(depth);
1206         rule_index = rule_find_v20(lpm, ip_masked, depth);
1207
1208         if (rule_index >= 0) {
1209                 *next_hop = lpm->rules_tbl[rule_index].next_hop;
1210                 return 1;
1211         }
1212
1213         /* If rule is not found return 0. */
1214         return 0;
1215 }
1216 VERSION_SYMBOL(rte_lpm_is_rule_present, _v20, 2.0);
1217
1218 int
1219 rte_lpm_is_rule_present_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
1220 uint32_t *next_hop)
1221 {
1222         uint32_t ip_masked;
1223         int32_t rule_index;
1224
1225         /* Check user arguments. */
1226         if ((lpm == NULL) ||
1227                 (next_hop == NULL) ||
1228                 (depth < 1) || (depth > RTE_LPM_MAX_DEPTH))
1229                 return -EINVAL;
1230
1231         /* Look for the rule using rule_find. */
1232         ip_masked = ip & depth_to_mask(depth);
1233         rule_index = rule_find_v1604(lpm, ip_masked, depth);
1234
1235         if (rule_index >= 0) {
1236                 *next_hop = lpm->rules_tbl[rule_index].next_hop;
1237                 return 1;
1238         }
1239
1240         /* If rule is not found return 0. */
1241         return 0;
1242 }
1243 BIND_DEFAULT_SYMBOL(rte_lpm_is_rule_present, _v1604, 16.04);
1244 MAP_STATIC_SYMBOL(int rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip,
1245                 uint8_t depth, uint32_t *next_hop), rte_lpm_is_rule_present_v1604);
1246
1247 static inline int32_t
1248 find_previous_rule_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
1249                 uint8_t *sub_rule_depth)
1250 {
1251         int32_t rule_index;
1252         uint32_t ip_masked;
1253         uint8_t prev_depth;
1254
1255         for (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) {
1256                 ip_masked = ip & depth_to_mask(prev_depth);
1257
1258                 rule_index = rule_find_v20(lpm, ip_masked, prev_depth);
1259
1260                 if (rule_index >= 0) {
1261                         *sub_rule_depth = prev_depth;
1262                         return rule_index;
1263                 }
1264         }
1265
1266         return -1;
1267 }
1268
1269 static inline int32_t
1270 find_previous_rule_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
1271                 uint8_t *sub_rule_depth)
1272 {
1273         int32_t rule_index;
1274         uint32_t ip_masked;
1275         uint8_t prev_depth;
1276
1277         for (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) {
1278                 ip_masked = ip & depth_to_mask(prev_depth);
1279
1280                 rule_index = rule_find_v1604(lpm, ip_masked, prev_depth);
1281
1282                 if (rule_index >= 0) {
1283                         *sub_rule_depth = prev_depth;
1284                         return rule_index;
1285                 }
1286         }
1287
1288         return -1;
1289 }
1290
1291 static inline int32_t
1292 delete_depth_small_v20(struct rte_lpm_v20 *lpm, uint32_t ip_masked,
1293         uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)
1294 {
1295         uint32_t tbl24_range, tbl24_index, tbl8_group_index, tbl8_index, i, j;
1296
1297         /* Calculate the range and index into Table24. */
1298         tbl24_range = depth_to_range(depth);
1299         tbl24_index = (ip_masked >> 8);
1300
1301         /*
1302          * Firstly check the sub_rule_index. A -1 indicates no replacement rule
1303          * and a positive number indicates a sub_rule_index.
1304          */
1305         if (sub_rule_index < 0) {
1306                 /*
1307                  * If no replacement rule exists then invalidate entries
1308                  * associated with this rule.
1309                  */
1310                 for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {
1311
1312                         if (lpm->tbl24[i].valid_group == 0 &&
1313                                         lpm->tbl24[i].depth <= depth) {
1314                                 lpm->tbl24[i].valid = INVALID;
1315                         } else if (lpm->tbl24[i].valid_group == 1) {
1316                                 /*
1317                                  * If TBL24 entry is extended, then there has
1318                                  * to be a rule with depth >= 25 in the
1319                                  * associated TBL8 group.
1320                                  */
1321
1322                                 tbl8_group_index = lpm->tbl24[i].group_idx;
1323                                 tbl8_index = tbl8_group_index *
1324                                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1325
1326                                 for (j = tbl8_index; j < (tbl8_index +
1327                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) {
1328
1329                                         if (lpm->tbl8[j].depth <= depth)
1330                                                 lpm->tbl8[j].valid = INVALID;
1331                                 }
1332                         }
1333                 }
1334         } else {
1335                 /*
1336                  * If a replacement rule exists then modify entries
1337                  * associated with this rule.
1338                  */
1339
1340                 struct rte_lpm_tbl_entry_v20 new_tbl24_entry = {
1341                         .next_hop = lpm->rules_tbl[sub_rule_index].next_hop,
1342                         .valid = VALID,
1343                         .valid_group = 0,
1344                         .depth = sub_rule_depth,
1345                 };
1346
1347                 struct rte_lpm_tbl_entry_v20 new_tbl8_entry = {
1348                         .valid = VALID,
1349                         .valid_group = VALID,
1350                         .depth = sub_rule_depth,
1351                 };
1352                 new_tbl8_entry.next_hop =
1353                                 lpm->rules_tbl[sub_rule_index].next_hop;
1354
1355                 for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {
1356
1357                         if (lpm->tbl24[i].valid_group == 0 &&
1358                                         lpm->tbl24[i].depth <= depth) {
1359                                 lpm->tbl24[i] = new_tbl24_entry;
1360                         } else  if (lpm->tbl24[i].valid_group == 1) {
1361                                 /*
1362                                  * If TBL24 entry is extended, then there has
1363                                  * to be a rule with depth >= 25 in the
1364                                  * associated TBL8 group.
1365                                  */
1366
1367                                 tbl8_group_index = lpm->tbl24[i].group_idx;
1368                                 tbl8_index = tbl8_group_index *
1369                                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1370
1371                                 for (j = tbl8_index; j < (tbl8_index +
1372                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) {
1373
1374                                         if (lpm->tbl8[j].depth <= depth)
1375                                                 lpm->tbl8[j] = new_tbl8_entry;
1376                                 }
1377                         }
1378                 }
1379         }
1380
1381         return 0;
1382 }
1383
1384 static inline int32_t
1385 delete_depth_small_v1604(struct rte_lpm *lpm, uint32_t ip_masked,
1386         uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)
1387 {
1388 #define group_idx next_hop
1389         uint32_t tbl24_range, tbl24_index, tbl8_group_index, tbl8_index, i, j;
1390
1391         /* Calculate the range and index into Table24. */
1392         tbl24_range = depth_to_range(depth);
1393         tbl24_index = (ip_masked >> 8);
1394
1395         /*
1396          * Firstly check the sub_rule_index. A -1 indicates no replacement rule
1397          * and a positive number indicates a sub_rule_index.
1398          */
1399         if (sub_rule_index < 0) {
1400                 /*
1401                  * If no replacement rule exists then invalidate entries
1402                  * associated with this rule.
1403                  */
1404                 for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {
1405
1406                         if (lpm->tbl24[i].valid_group == 0 &&
1407                                         lpm->tbl24[i].depth <= depth) {
1408                                 lpm->tbl24[i].valid = INVALID;
1409                         } else if (lpm->tbl24[i].valid_group == 1) {
1410                                 /*
1411                                  * If TBL24 entry is extended, then there has
1412                                  * to be a rule with depth >= 25 in the
1413                                  * associated TBL8 group.
1414                                  */
1415
1416                                 tbl8_group_index = lpm->tbl24[i].group_idx;
1417                                 tbl8_index = tbl8_group_index *
1418                                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1419
1420                                 for (j = tbl8_index; j < (tbl8_index +
1421                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) {
1422
1423                                         if (lpm->tbl8[j].depth <= depth)
1424                                                 lpm->tbl8[j].valid = INVALID;
1425                                 }
1426                         }
1427                 }
1428         } else {
1429                 /*
1430                  * If a replacement rule exists then modify entries
1431                  * associated with this rule.
1432                  */
1433
1434                 struct rte_lpm_tbl_entry new_tbl24_entry = {
1435                         .next_hop = lpm->rules_tbl[sub_rule_index].next_hop,
1436                         .valid = VALID,
1437                         .valid_group = 0,
1438                         .depth = sub_rule_depth,
1439                 };
1440
1441                 struct rte_lpm_tbl_entry new_tbl8_entry = {
1442                         .valid = VALID,
1443                         .valid_group = VALID,
1444                         .depth = sub_rule_depth,
1445                         .next_hop = lpm->rules_tbl
1446                         [sub_rule_index].next_hop,
1447                 };
1448
1449                 for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {
1450
1451                         if (lpm->tbl24[i].valid_group == 0 &&
1452                                         lpm->tbl24[i].depth <= depth) {
1453                                 lpm->tbl24[i] = new_tbl24_entry;
1454                         } else  if (lpm->tbl24[i].valid_group == 1) {
1455                                 /*
1456                                  * If TBL24 entry is extended, then there has
1457                                  * to be a rule with depth >= 25 in the
1458                                  * associated TBL8 group.
1459                                  */
1460
1461                                 tbl8_group_index = lpm->tbl24[i].group_idx;
1462                                 tbl8_index = tbl8_group_index *
1463                                                 RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1464
1465                                 for (j = tbl8_index; j < (tbl8_index +
1466                                         RTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) {
1467
1468                                         if (lpm->tbl8[j].depth <= depth)
1469                                                 lpm->tbl8[j] = new_tbl8_entry;
1470                                 }
1471                         }
1472                 }
1473         }
1474 #undef group_idx
1475         return 0;
1476 }
1477
1478 /*
1479  * Checks if table 8 group can be recycled.
1480  *
1481  * Return of -EEXIST means tbl8 is in use and thus can not be recycled.
1482  * Return of -EINVAL means tbl8 is empty and thus can be recycled
1483  * Return of value > -1 means tbl8 is in use but has all the same values and
1484  * thus can be recycled
1485  */
1486 static inline int32_t
1487 tbl8_recycle_check_v20(struct rte_lpm_tbl_entry_v20 *tbl8,
1488                 uint32_t tbl8_group_start)
1489 {
1490         uint32_t tbl8_group_end, i;
1491         tbl8_group_end = tbl8_group_start + RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1492
1493         /*
1494          * Check the first entry of the given tbl8. If it is invalid we know
1495          * this tbl8 does not contain any rule with a depth < RTE_LPM_MAX_DEPTH
1496          *  (As they would affect all entries in a tbl8) and thus this table
1497          *  can not be recycled.
1498          */
1499         if (tbl8[tbl8_group_start].valid) {
1500                 /*
1501                  * If first entry is valid check if the depth is less than 24
1502                  * and if so check the rest of the entries to verify that they
1503                  * are all of this depth.
1504                  */
1505                 if (tbl8[tbl8_group_start].depth <= MAX_DEPTH_TBL24) {
1506                         for (i = (tbl8_group_start + 1); i < tbl8_group_end;
1507                                         i++) {
1508
1509                                 if (tbl8[i].depth !=
1510                                                 tbl8[tbl8_group_start].depth) {
1511
1512                                         return -EEXIST;
1513                                 }
1514                         }
1515                         /* If all entries are the same return the tb8 index */
1516                         return tbl8_group_start;
1517                 }
1518
1519                 return -EEXIST;
1520         }
1521         /*
1522          * If the first entry is invalid check if the rest of the entries in
1523          * the tbl8 are invalid.
1524          */
1525         for (i = (tbl8_group_start + 1); i < tbl8_group_end; i++) {
1526                 if (tbl8[i].valid)
1527                         return -EEXIST;
1528         }
1529         /* If no valid entries are found then return -EINVAL. */
1530         return -EINVAL;
1531 }
1532
1533 static inline int32_t
1534 tbl8_recycle_check_v1604(struct rte_lpm_tbl_entry *tbl8,
1535                 uint32_t tbl8_group_start)
1536 {
1537         uint32_t tbl8_group_end, i;
1538         tbl8_group_end = tbl8_group_start + RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1539
1540         /*
1541          * Check the first entry of the given tbl8. If it is invalid we know
1542          * this tbl8 does not contain any rule with a depth < RTE_LPM_MAX_DEPTH
1543          *  (As they would affect all entries in a tbl8) and thus this table
1544          *  can not be recycled.
1545          */
1546         if (tbl8[tbl8_group_start].valid) {
1547                 /*
1548                  * If first entry is valid check if the depth is less than 24
1549                  * and if so check the rest of the entries to verify that they
1550                  * are all of this depth.
1551                  */
1552                 if (tbl8[tbl8_group_start].depth <= MAX_DEPTH_TBL24) {
1553                         for (i = (tbl8_group_start + 1); i < tbl8_group_end;
1554                                         i++) {
1555
1556                                 if (tbl8[i].depth !=
1557                                                 tbl8[tbl8_group_start].depth) {
1558
1559                                         return -EEXIST;
1560                                 }
1561                         }
1562                         /* If all entries are the same return the tb8 index */
1563                         return tbl8_group_start;
1564                 }
1565
1566                 return -EEXIST;
1567         }
1568         /*
1569          * If the first entry is invalid check if the rest of the entries in
1570          * the tbl8 are invalid.
1571          */
1572         for (i = (tbl8_group_start + 1); i < tbl8_group_end; i++) {
1573                 if (tbl8[i].valid)
1574                         return -EEXIST;
1575         }
1576         /* If no valid entries are found then return -EINVAL. */
1577         return -EINVAL;
1578 }
1579
1580 static inline int32_t
1581 delete_depth_big_v20(struct rte_lpm_v20 *lpm, uint32_t ip_masked,
1582         uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)
1583 {
1584         uint32_t tbl24_index, tbl8_group_index, tbl8_group_start, tbl8_index,
1585                         tbl8_range, i;
1586         int32_t tbl8_recycle_index;
1587
1588         /*
1589          * Calculate the index into tbl24 and range. Note: All depths larger
1590          * than MAX_DEPTH_TBL24 are associated with only one tbl24 entry.
1591          */
1592         tbl24_index = ip_masked >> 8;
1593
1594         /* Calculate the index into tbl8 and range. */
1595         tbl8_group_index = lpm->tbl24[tbl24_index].group_idx;
1596         tbl8_group_start = tbl8_group_index * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1597         tbl8_index = tbl8_group_start + (ip_masked & 0xFF);
1598         tbl8_range = depth_to_range(depth);
1599
1600         if (sub_rule_index < 0) {
1601                 /*
1602                  * Loop through the range of entries on tbl8 for which the
1603                  * rule_to_delete must be removed or modified.
1604                  */
1605                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
1606                         if (lpm->tbl8[i].depth <= depth)
1607                                 lpm->tbl8[i].valid = INVALID;
1608                 }
1609         } else {
1610                 /* Set new tbl8 entry. */
1611                 struct rte_lpm_tbl_entry_v20 new_tbl8_entry = {
1612                         .valid = VALID,
1613                         .depth = sub_rule_depth,
1614                         .valid_group = lpm->tbl8[tbl8_group_start].valid_group,
1615                 };
1616
1617                 new_tbl8_entry.next_hop =
1618                                 lpm->rules_tbl[sub_rule_index].next_hop;
1619                 /*
1620                  * Loop through the range of entries on tbl8 for which the
1621                  * rule_to_delete must be modified.
1622                  */
1623                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
1624                         if (lpm->tbl8[i].depth <= depth)
1625                                 lpm->tbl8[i] = new_tbl8_entry;
1626                 }
1627         }
1628
1629         /*
1630          * Check if there are any valid entries in this tbl8 group. If all
1631          * tbl8 entries are invalid we can free the tbl8 and invalidate the
1632          * associated tbl24 entry.
1633          */
1634
1635         tbl8_recycle_index = tbl8_recycle_check_v20(lpm->tbl8, tbl8_group_start);
1636
1637         if (tbl8_recycle_index == -EINVAL) {
1638                 /* Set tbl24 before freeing tbl8 to avoid race condition. */
1639                 lpm->tbl24[tbl24_index].valid = 0;
1640                 tbl8_free_v20(lpm->tbl8, tbl8_group_start);
1641         } else if (tbl8_recycle_index > -1) {
1642                 /* Update tbl24 entry. */
1643                 struct rte_lpm_tbl_entry_v20 new_tbl24_entry = {
1644                         .next_hop = lpm->tbl8[tbl8_recycle_index].next_hop,
1645                         .valid = VALID,
1646                         .valid_group = 0,
1647                         .depth = lpm->tbl8[tbl8_recycle_index].depth,
1648                 };
1649
1650                 /* Set tbl24 before freeing tbl8 to avoid race condition. */
1651                 lpm->tbl24[tbl24_index] = new_tbl24_entry;
1652                 tbl8_free_v20(lpm->tbl8, tbl8_group_start);
1653         }
1654
1655         return 0;
1656 }
1657
1658 static inline int32_t
1659 delete_depth_big_v1604(struct rte_lpm *lpm, uint32_t ip_masked,
1660         uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)
1661 {
1662 #define group_idx next_hop
1663         uint32_t tbl24_index, tbl8_group_index, tbl8_group_start, tbl8_index,
1664                         tbl8_range, i;
1665         int32_t tbl8_recycle_index;
1666
1667         /*
1668          * Calculate the index into tbl24 and range. Note: All depths larger
1669          * than MAX_DEPTH_TBL24 are associated with only one tbl24 entry.
1670          */
1671         tbl24_index = ip_masked >> 8;
1672
1673         /* Calculate the index into tbl8 and range. */
1674         tbl8_group_index = lpm->tbl24[tbl24_index].group_idx;
1675         tbl8_group_start = tbl8_group_index * RTE_LPM_TBL8_GROUP_NUM_ENTRIES;
1676         tbl8_index = tbl8_group_start + (ip_masked & 0xFF);
1677         tbl8_range = depth_to_range(depth);
1678
1679         if (sub_rule_index < 0) {
1680                 /*
1681                  * Loop through the range of entries on tbl8 for which the
1682                  * rule_to_delete must be removed or modified.
1683                  */
1684                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
1685                         if (lpm->tbl8[i].depth <= depth)
1686                                 lpm->tbl8[i].valid = INVALID;
1687                 }
1688         } else {
1689                 /* Set new tbl8 entry. */
1690                 struct rte_lpm_tbl_entry new_tbl8_entry = {
1691                         .valid = VALID,
1692                         .depth = sub_rule_depth,
1693                         .valid_group = lpm->tbl8[tbl8_group_start].valid_group,
1694                         .next_hop = lpm->rules_tbl[sub_rule_index].next_hop,
1695                 };
1696
1697                 /*
1698                  * Loop through the range of entries on tbl8 for which the
1699                  * rule_to_delete must be modified.
1700                  */
1701                 for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) {
1702                         if (lpm->tbl8[i].depth <= depth)
1703                                 lpm->tbl8[i] = new_tbl8_entry;
1704                 }
1705         }
1706
1707         /*
1708          * Check if there are any valid entries in this tbl8 group. If all
1709          * tbl8 entries are invalid we can free the tbl8 and invalidate the
1710          * associated tbl24 entry.
1711          */
1712
1713         tbl8_recycle_index = tbl8_recycle_check_v1604(lpm->tbl8, tbl8_group_start);
1714
1715         if (tbl8_recycle_index == -EINVAL) {
1716                 /* Set tbl24 before freeing tbl8 to avoid race condition. */
1717                 lpm->tbl24[tbl24_index].valid = 0;
1718                 tbl8_free_v1604(lpm->tbl8, tbl8_group_start);
1719         } else if (tbl8_recycle_index > -1) {
1720                 /* Update tbl24 entry. */
1721                 struct rte_lpm_tbl_entry new_tbl24_entry = {
1722                         .next_hop = lpm->tbl8[tbl8_recycle_index].next_hop,
1723                         .valid = VALID,
1724                         .valid_group = 0,
1725                         .depth = lpm->tbl8[tbl8_recycle_index].depth,
1726                 };
1727
1728                 /* Set tbl24 before freeing tbl8 to avoid race condition. */
1729                 lpm->tbl24[tbl24_index] = new_tbl24_entry;
1730                 tbl8_free_v1604(lpm->tbl8, tbl8_group_start);
1731         }
1732 #undef group_idx
1733         return 0;
1734 }
1735
1736 /*
1737  * Deletes a rule
1738  */
1739 int
1740 rte_lpm_delete_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth)
1741 {
1742         int32_t rule_to_delete_index, sub_rule_index;
1743         uint32_t ip_masked;
1744         uint8_t sub_rule_depth;
1745         /*
1746          * Check input arguments. Note: IP must be a positive integer of 32
1747          * bits in length therefore it need not be checked.
1748          */
1749         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) {
1750                 return -EINVAL;
1751         }
1752
1753         ip_masked = ip & depth_to_mask(depth);
1754
1755         /*
1756          * Find the index of the input rule, that needs to be deleted, in the
1757          * rule table.
1758          */
1759         rule_to_delete_index = rule_find_v20(lpm, ip_masked, depth);
1760
1761         /*
1762          * Check if rule_to_delete_index was found. If no rule was found the
1763          * function rule_find returns -EINVAL.
1764          */
1765         if (rule_to_delete_index < 0)
1766                 return -EINVAL;
1767
1768         /* Delete the rule from the rule table. */
1769         rule_delete_v20(lpm, rule_to_delete_index, depth);
1770
1771         /*
1772          * Find rule to replace the rule_to_delete. If there is no rule to
1773          * replace the rule_to_delete we return -1 and invalidate the table
1774          * entries associated with this rule.
1775          */
1776         sub_rule_depth = 0;
1777         sub_rule_index = find_previous_rule_v20(lpm, ip, depth, &sub_rule_depth);
1778
1779         /*
1780          * If the input depth value is less than 25 use function
1781          * delete_depth_small otherwise use delete_depth_big.
1782          */
1783         if (depth <= MAX_DEPTH_TBL24) {
1784                 return delete_depth_small_v20(lpm, ip_masked, depth,
1785                                 sub_rule_index, sub_rule_depth);
1786         } else { /* If depth > MAX_DEPTH_TBL24 */
1787                 return delete_depth_big_v20(lpm, ip_masked, depth, sub_rule_index,
1788                                 sub_rule_depth);
1789         }
1790 }
1791 VERSION_SYMBOL(rte_lpm_delete, _v20, 2.0);
1792
1793 int
1794 rte_lpm_delete_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)
1795 {
1796         int32_t rule_to_delete_index, sub_rule_index;
1797         uint32_t ip_masked;
1798         uint8_t sub_rule_depth;
1799         /*
1800          * Check input arguments. Note: IP must be a positive integer of 32
1801          * bits in length therefore it need not be checked.
1802          */
1803         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) {
1804                 return -EINVAL;
1805         }
1806
1807         ip_masked = ip & depth_to_mask(depth);
1808
1809         /*
1810          * Find the index of the input rule, that needs to be deleted, in the
1811          * rule table.
1812          */
1813         rule_to_delete_index = rule_find_v1604(lpm, ip_masked, depth);
1814
1815         /*
1816          * Check if rule_to_delete_index was found. If no rule was found the
1817          * function rule_find returns -EINVAL.
1818          */
1819         if (rule_to_delete_index < 0)
1820                 return -EINVAL;
1821
1822         /* Delete the rule from the rule table. */
1823         rule_delete_v1604(lpm, rule_to_delete_index, depth);
1824
1825         /*
1826          * Find rule to replace the rule_to_delete. If there is no rule to
1827          * replace the rule_to_delete we return -1 and invalidate the table
1828          * entries associated with this rule.
1829          */
1830         sub_rule_depth = 0;
1831         sub_rule_index = find_previous_rule_v1604(lpm, ip, depth, &sub_rule_depth);
1832
1833         /*
1834          * If the input depth value is less than 25 use function
1835          * delete_depth_small otherwise use delete_depth_big.
1836          */
1837         if (depth <= MAX_DEPTH_TBL24) {
1838                 return delete_depth_small_v1604(lpm, ip_masked, depth,
1839                                 sub_rule_index, sub_rule_depth);
1840         } else { /* If depth > MAX_DEPTH_TBL24 */
1841                 return delete_depth_big_v1604(lpm, ip_masked, depth, sub_rule_index,
1842                                 sub_rule_depth);
1843         }
1844 }
1845 BIND_DEFAULT_SYMBOL(rte_lpm_delete, _v1604, 16.04);
1846 MAP_STATIC_SYMBOL(int rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip,
1847                 uint8_t depth), rte_lpm_delete_v1604);
1848
1849 /*
1850  * Delete all rules from the LPM table.
1851  */
1852 void
1853 rte_lpm_delete_all_v20(struct rte_lpm_v20 *lpm)
1854 {
1855         /* Zero rule information. */
1856         memset(lpm->rule_info, 0, sizeof(lpm->rule_info));
1857
1858         /* Zero tbl24. */
1859         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
1860
1861         /* Zero tbl8. */
1862         memset(lpm->tbl8, 0, sizeof(lpm->tbl8));
1863
1864         /* Delete all rules form the rules table. */
1865         memset(lpm->rules_tbl, 0, sizeof(lpm->rules_tbl[0]) * lpm->max_rules);
1866 }
1867 VERSION_SYMBOL(rte_lpm_delete_all, _v20, 2.0);
1868
1869 void
1870 rte_lpm_delete_all_v1604(struct rte_lpm *lpm)
1871 {
1872         /* Zero rule information. */
1873         memset(lpm->rule_info, 0, sizeof(lpm->rule_info));
1874
1875         /* Zero tbl24. */
1876         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
1877
1878         /* Zero tbl8. */
1879         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
1880                         * RTE_LPM_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
1881
1882         /* Delete all rules form the rules table. */
1883         memset(lpm->rules_tbl, 0, sizeof(lpm->rules_tbl[0]) * lpm->max_rules);
1884 }
1885 BIND_DEFAULT_SYMBOL(rte_lpm_delete_all, _v1604, 16.04);
1886 MAP_STATIC_SYMBOL(void rte_lpm_delete_all(struct rte_lpm *lpm),
1887                 rte_lpm_delete_all_v1604);