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