LCOV - code coverage report
Current view: top level - lib/lpm - rte_lpm6.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 337 360 93.6 %
Date: 2024-04-01 19:00:53 Functions: 22 22 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 218 244 89.3 %

           Branch data     Line data    Source code
       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  * Copyright(c) 2010-2014 Intel Corporation
       3                 :            :  */
       4                 :            : #include <string.h>
       5                 :            : #include <stdalign.h>
       6                 :            : #include <stdint.h>
       7                 :            : #include <errno.h>
       8                 :            : #include <stdio.h>
       9                 :            : #include <sys/queue.h>
      10                 :            : 
      11                 :            : #include <rte_log.h>
      12                 :            : #include <rte_common.h>
      13                 :            : #include <rte_malloc.h>
      14                 :            : #include <rte_memcpy.h>
      15                 :            : #include <rte_eal_memconfig.h>
      16                 :            : #include <rte_string_fns.h>
      17                 :            : #include <rte_errno.h>
      18                 :            : #include <rte_hash.h>
      19                 :            : #include <assert.h>
      20                 :            : #include <rte_jhash.h>
      21                 :            : #include <rte_tailq.h>
      22                 :            : 
      23                 :            : #include "rte_lpm6.h"
      24                 :            : #include "lpm_log.h"
      25                 :            : 
      26                 :            : #define RTE_LPM6_TBL24_NUM_ENTRIES        (1 << 24)
      27                 :            : #define RTE_LPM6_TBL8_GROUP_NUM_ENTRIES         256
      28                 :            : #define RTE_LPM6_TBL8_MAX_NUM_GROUPS      (1 << 21)
      29                 :            : 
      30                 :            : #define RTE_LPM6_VALID_EXT_ENTRY_BITMASK 0xA0000000
      31                 :            : #define RTE_LPM6_LOOKUP_SUCCESS          0x20000000
      32                 :            : #define RTE_LPM6_TBL8_BITMASK            0x001FFFFF
      33                 :            : 
      34                 :            : #define ADD_FIRST_BYTE                            3
      35                 :            : #define LOOKUP_FIRST_BYTE                         4
      36                 :            : #define BYTE_SIZE                                 8
      37                 :            : #define BYTES2_SIZE                              16
      38                 :            : 
      39                 :            : #define RULE_HASH_TABLE_EXTRA_SPACE              64
      40                 :            : #define TBL24_IND                        UINT32_MAX
      41                 :            : 
      42                 :            : #define lpm6_tbl8_gindex next_hop
      43                 :            : 
      44                 :            : /** Flags for setting an entry as valid/invalid. */
      45                 :            : enum valid_flag {
      46                 :            :         INVALID = 0,
      47                 :            :         VALID
      48                 :            : };
      49                 :            : 
      50                 :            : TAILQ_HEAD(rte_lpm6_list, rte_tailq_entry);
      51                 :            : 
      52                 :            : static struct rte_tailq_elem rte_lpm6_tailq = {
      53                 :            :         .name = "RTE_LPM6",
      54                 :            : };
      55         [ -  + ]:        238 : EAL_REGISTER_TAILQ(rte_lpm6_tailq)
      56                 :            : 
      57                 :            : /** Tbl entry structure. It is the same for both tbl24 and tbl8 */
      58                 :            : struct rte_lpm6_tbl_entry {
      59                 :            :         uint32_t next_hop:      21;  /**< Next hop / next table to be checked. */
      60                 :            :         uint32_t depth  :8;      /**< Rule depth. */
      61                 :            : 
      62                 :            :         /* Flags. */
      63                 :            :         uint32_t valid     :1;   /**< Validation flag. */
      64                 :            :         uint32_t valid_group :1; /**< Group validation flag. */
      65                 :            :         uint32_t ext_entry :1;   /**< External entry. */
      66                 :            : };
      67                 :            : 
      68                 :            : /** Rules tbl entry structure. */
      69                 :            : struct rte_lpm6_rule {
      70                 :            :         uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
      71                 :            :         uint32_t next_hop; /**< Rule next hop. */
      72                 :            :         uint8_t depth; /**< Rule depth. */
      73                 :            : };
      74                 :            : 
      75                 :            : /** Rules tbl entry key. */
      76                 :            : struct rte_lpm6_rule_key {
      77                 :            :         uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
      78                 :            :         uint32_t depth; /**< Rule depth. */
      79                 :            : };
      80                 :            : 
      81                 :            : /* Header of tbl8 */
      82                 :            : struct rte_lpm_tbl8_hdr {
      83                 :            :         uint32_t owner_tbl_ind; /**< owner table: TBL24_IND if owner is tbl24,
      84                 :            :                                   *  otherwise index of tbl8
      85                 :            :                                   */
      86                 :            :         uint32_t owner_entry_ind; /**< index of the owner table entry where
      87                 :            :                                     *  pointer to the tbl8 is stored
      88                 :            :                                     */
      89                 :            :         uint32_t ref_cnt; /**< table reference counter */
      90                 :            : };
      91                 :            : 
      92                 :            : /** LPM6 structure. */
      93                 :            : struct rte_lpm6 {
      94                 :            :         /* LPM metadata. */
      95                 :            :         char name[RTE_LPM6_NAMESIZE];    /**< Name of the lpm. */
      96                 :            :         uint32_t max_rules;              /**< Max number of rules. */
      97                 :            :         uint32_t used_rules;             /**< Used rules so far. */
      98                 :            :         uint32_t number_tbl8s;           /**< Number of tbl8s to allocate. */
      99                 :            : 
     100                 :            :         /* LPM Tables. */
     101                 :            :         struct rte_hash *rules_tbl; /**< LPM rules. */
     102                 :            :         alignas(RTE_CACHE_LINE_SIZE) struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES];
     103                 :            :                         /**< LPM tbl24 table. */
     104                 :            : 
     105                 :            :         uint32_t *tbl8_pool; /**< pool of indexes of free tbl8s */
     106                 :            :         uint32_t tbl8_pool_pos; /**< current position in the tbl8 pool */
     107                 :            : 
     108                 :            :         struct rte_lpm_tbl8_hdr *tbl8_hdrs; /* array of tbl8 headers */
     109                 :            : 
     110                 :            :         alignas(RTE_CACHE_LINE_SIZE) struct rte_lpm6_tbl_entry tbl8[0];
     111                 :            :                         /**< LPM tbl8 table. */
     112                 :            : };
     113                 :            : 
     114                 :            : /*
     115                 :            :  * Takes an array of uint8_t (IPv6 address) and masks it using the depth.
     116                 :            :  * It leaves untouched one bit per unit in the depth variable
     117                 :            :  * and set the rest to 0.
     118                 :            :  */
     119                 :            : static inline void
     120                 :            : ip6_mask_addr(uint8_t *ip, uint8_t depth)
     121                 :            : {
     122                 :            :         int16_t part_depth, mask;
     123                 :            :         int i;
     124                 :            : 
     125                 :       1577 :         part_depth = depth;
     126                 :            : 
     127   [ +  +  +  +  :      26809 :         for (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) {
             +  +  +  + ]
     128   [ +  +  +  +  :      25232 :                 if (part_depth < BYTE_SIZE && part_depth >= 0) {
             +  +  +  + ]
     129                 :       1501 :                         mask = (uint16_t)(~(UINT8_MAX >> part_depth));
     130                 :       1501 :                         ip[i] = (uint8_t)(ip[i] & mask);
     131   [ +  +  +  +  :      23731 :                 } else if (part_depth < 0)
             +  +  +  + ]
     132                 :      13057 :                         ip[i] = 0;
     133                 :            : 
     134                 :      25232 :                 part_depth -= BYTE_SIZE;
     135                 :            :         }
     136                 :            : }
     137                 :            : 
     138                 :            : /* copy ipv6 address */
     139                 :            : static inline void
     140                 :            : ip6_copy_addr(uint8_t *dst, const uint8_t *src)
     141                 :            : {
     142                 :            :         rte_memcpy(dst, src, RTE_LPM6_IPV6_ADDR_SIZE);
     143                 :            : }
     144                 :            : 
     145                 :            : /*
     146                 :            :  * LPM6 rule hash function
     147                 :            :  *
     148                 :            :  * It's used as a hash function for the rte_hash
     149                 :            :  *      containing rules
     150                 :            :  */
     151                 :            : static inline uint32_t
     152                 :       7621 : rule_hash(const void *data, __rte_unused uint32_t data_len,
     153                 :            :                   uint32_t init_val)
     154                 :            : {
     155                 :       7621 :         return rte_jhash(data, sizeof(struct rte_lpm6_rule_key), init_val);
     156                 :            : }
     157                 :            : 
     158                 :            : /*
     159                 :            :  * Init pool of free tbl8 indexes
     160                 :            :  */
     161                 :            : static void
     162                 :            : tbl8_pool_init(struct rte_lpm6 *lpm)
     163                 :            : {
     164                 :            :         uint32_t i;
     165                 :            : 
     166                 :            :         /* put entire range of indexes to the tbl8 pool */
     167   [ +  +  +  +  :    4415843 :         for (i = 0; i < lpm->number_tbl8s; i++)
                   +  + ]
     168                 :    4415776 :                 lpm->tbl8_pool[i] = i;
     169                 :            : 
     170                 :         67 :         lpm->tbl8_pool_pos = 0;
     171                 :            : }
     172                 :            : 
     173                 :            : /*
     174                 :            :  * Get an index of a free tbl8 from the pool
     175                 :            :  */
     176                 :            : static inline uint32_t
     177                 :            : tbl8_get(struct rte_lpm6 *lpm, uint32_t *tbl8_ind)
     178                 :            : {
     179   [ +  -  +  - ]:       6275 :         if (lpm->tbl8_pool_pos == lpm->number_tbl8s)
     180                 :            :                 /* no more free tbl8 */
     181                 :            :                 return -ENOSPC;
     182                 :            : 
     183                 :            :         /* next index */
     184                 :       6275 :         *tbl8_ind = lpm->tbl8_pool[lpm->tbl8_pool_pos++];
     185                 :            :         return 0;
     186                 :            : }
     187                 :            : 
     188                 :            : /*
     189                 :            :  * Put an index of a free tbl8 back to the pool
     190                 :            :  */
     191                 :            : static inline uint32_t
     192                 :            : tbl8_put(struct rte_lpm6 *lpm, uint32_t tbl8_ind)
     193                 :            : {
     194         [ +  - ]:        427 :         if (lpm->tbl8_pool_pos == 0)
     195                 :            :                 /* pool is full */
     196                 :            :                 return -ENOSPC;
     197                 :            : 
     198                 :        427 :         lpm->tbl8_pool[--lpm->tbl8_pool_pos] = tbl8_ind;
     199                 :        427 :         return 0;
     200                 :            : }
     201                 :            : 
     202                 :            : /*
     203                 :            :  * Returns number of tbl8s available in the pool
     204                 :            :  */
     205                 :            : static inline uint32_t
     206                 :            : tbl8_available(struct rte_lpm6 *lpm)
     207                 :            : {
     208                 :       1490 :         return lpm->number_tbl8s - lpm->tbl8_pool_pos;
     209                 :            : }
     210                 :            : 
     211                 :            : /*
     212                 :            :  * Init a rule key.
     213                 :            :  *        note that ip must be already masked
     214                 :            :  */
     215                 :            : static inline void
     216                 :            : rule_key_init(struct rte_lpm6_rule_key *key, uint8_t *ip, uint8_t depth)
     217                 :            : {
     218                 :            :         ip6_copy_addr(key->ip, ip);
     219                 :       1574 :         key->depth = depth;
     220                 :         71 : }
     221                 :            : 
     222                 :            : /*
     223                 :            :  * Rebuild the entire LPM tree by reinserting all rules
     224                 :            :  */
     225                 :            : static void
     226                 :          4 : rebuild_lpm(struct rte_lpm6 *lpm)
     227                 :            : {
     228                 :            :         uint64_t next_hop;
     229                 :            :         struct rte_lpm6_rule_key *rule_key;
     230                 :          4 :         uint32_t iter = 0;
     231                 :            : 
     232                 :         10 :         while (rte_hash_iterate(lpm->rules_tbl, (void *) &rule_key,
     233         [ +  + ]:         10 :                         (void **) &next_hop, &iter) >= 0)
     234                 :          6 :                 rte_lpm6_add(lpm, rule_key->ip, rule_key->depth,
     235                 :            :                         (uint32_t) next_hop);
     236                 :          4 : }
     237                 :            : 
     238                 :            : /*
     239                 :            :  * Allocates memory for LPM object
     240                 :            :  */
     241                 :            : struct rte_lpm6 *
     242                 :         59 : rte_lpm6_create(const char *name, int socket_id,
     243                 :            :                 const struct rte_lpm6_config *config)
     244                 :            : {
     245                 :            :         char mem_name[RTE_LPM6_NAMESIZE];
     246                 :            :         struct rte_lpm6 *lpm = NULL;
     247                 :            :         struct rte_tailq_entry *te;
     248                 :            :         uint64_t mem_size;
     249                 :            :         struct rte_lpm6_list *lpm_list;
     250                 :            :         struct rte_hash *rules_tbl = NULL;
     251                 :            :         uint32_t *tbl8_pool = NULL;
     252                 :            :         struct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL;
     253                 :            : 
     254                 :         59 :         lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
     255                 :            : 
     256                 :            :         RTE_BUILD_BUG_ON(sizeof(struct rte_lpm6_tbl_entry) != sizeof(uint32_t));
     257                 :            :         RTE_BUILD_BUG_ON(sizeof(struct rte_lpm6_rule_key) %
     258                 :            :                 sizeof(uint32_t) != 0);
     259                 :            : 
     260                 :            :         /* Check user arguments. */
     261   [ +  +  +  + ]:         59 :         if ((name == NULL) || (socket_id < -1) || (config == NULL) ||
     262         [ +  + ]:         56 :                         (config->max_rules == 0) ||
     263         [ +  + ]:         55 :                         config->number_tbl8s > RTE_LPM6_TBL8_MAX_NUM_GROUPS) {
     264                 :          5 :                 rte_errno = EINVAL;
     265                 :          5 :                 return NULL;
     266                 :            :         }
     267                 :            : 
     268                 :            :         /* create rules hash table */
     269                 :            :         snprintf(mem_name, sizeof(mem_name), "LRH_%s", name);
     270                 :         54 :         struct rte_hash_parameters rule_hash_tbl_params = {
     271                 :         54 :                 .entries = config->max_rules * 1.2 +
     272                 :            :                         RULE_HASH_TABLE_EXTRA_SPACE,
     273                 :            :                 .key_len = sizeof(struct rte_lpm6_rule_key),
     274                 :            :                 .hash_func = rule_hash,
     275                 :            :                 .hash_func_init_val = 0,
     276                 :            :                 .name = mem_name,
     277                 :            :                 .reserved = 0,
     278                 :            :                 .socket_id = socket_id,
     279                 :            :                 .extra_flag = 0
     280                 :            :         };
     281                 :            : 
     282                 :         54 :         rules_tbl = rte_hash_create(&rule_hash_tbl_params);
     283         [ +  + ]:         54 :         if (rules_tbl == NULL) {
     284                 :          1 :                 LPM_LOG(ERR, "LPM rules hash table allocation failed: %s (%d)",
     285                 :            :                                   rte_strerror(rte_errno), rte_errno);
     286                 :          1 :                 goto fail_wo_unlock;
     287                 :            :         }
     288                 :            : 
     289                 :            :         /* allocate tbl8 indexes pool */
     290                 :         53 :         tbl8_pool = rte_malloc(NULL,
     291                 :         53 :                         sizeof(uint32_t) * config->number_tbl8s,
     292                 :            :                         RTE_CACHE_LINE_SIZE);
     293         [ -  + ]:         53 :         if (tbl8_pool == NULL) {
     294                 :          0 :                 LPM_LOG(ERR, "LPM tbl8 pool allocation failed: %s (%d)",
     295                 :            :                                   rte_strerror(rte_errno), rte_errno);
     296                 :          0 :                 rte_errno = ENOMEM;
     297                 :          0 :                 goto fail_wo_unlock;
     298                 :            :         }
     299                 :            : 
     300                 :            :         /* allocate tbl8 headers */
     301                 :         53 :         tbl8_hdrs = rte_malloc(NULL,
     302                 :         53 :                         sizeof(struct rte_lpm_tbl8_hdr) * config->number_tbl8s,
     303                 :            :                         RTE_CACHE_LINE_SIZE);
     304         [ -  + ]:         53 :         if (tbl8_hdrs == NULL) {
     305                 :          0 :                 LPM_LOG(ERR, "LPM tbl8 headers allocation failed: %s (%d)",
     306                 :            :                                   rte_strerror(rte_errno), rte_errno);
     307                 :          0 :                 rte_errno = ENOMEM;
     308                 :          0 :                 goto fail_wo_unlock;
     309                 :            :         }
     310                 :            : 
     311                 :            :         snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);
     312                 :            : 
     313                 :            :         /* Determine the amount of memory to allocate. */
     314                 :         53 :         mem_size = sizeof(*lpm) + (sizeof(lpm->tbl8[0]) *
     315                 :         53 :                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s);
     316                 :            : 
     317                 :         53 :         rte_mcfg_tailq_write_lock();
     318                 :            : 
     319                 :            :         /* Guarantee there's no existing */
     320         [ +  + ]:         54 :         TAILQ_FOREACH(te, lpm_list, next) {
     321                 :          1 :                 lpm = (struct rte_lpm6 *) te->data;
     322         [ +  - ]:          1 :                 if (strncmp(name, lpm->name, RTE_LPM6_NAMESIZE) == 0)
     323                 :            :                         break;
     324                 :            :         }
     325                 :            :         lpm = NULL;
     326         [ -  + ]:         53 :         if (te != NULL) {
     327                 :          0 :                 rte_errno = EEXIST;
     328                 :          0 :                 goto fail;
     329                 :            :         }
     330                 :            : 
     331                 :            :         /* allocate tailq entry */
     332                 :         53 :         te = rte_zmalloc("LPM6_TAILQ_ENTRY", sizeof(*te), 0);
     333         [ -  + ]:         53 :         if (te == NULL) {
     334                 :          0 :                 LPM_LOG(ERR, "Failed to allocate tailq entry!");
     335                 :          0 :                 rte_errno = ENOMEM;
     336                 :          0 :                 goto fail;
     337                 :            :         }
     338                 :            : 
     339                 :            :         /* Allocate memory to store the LPM data structures. */
     340                 :         53 :         lpm = rte_zmalloc_socket(mem_name, (size_t)mem_size,
     341                 :            :                         RTE_CACHE_LINE_SIZE, socket_id);
     342                 :            : 
     343         [ -  + ]:         53 :         if (lpm == NULL) {
     344                 :          0 :                 LPM_LOG(ERR, "LPM memory allocation failed");
     345                 :          0 :                 rte_free(te);
     346                 :          0 :                 rte_errno = ENOMEM;
     347                 :          0 :                 goto fail;
     348                 :            :         }
     349                 :            : 
     350                 :            :         /* Save user arguments. */
     351                 :         53 :         lpm->max_rules = config->max_rules;
     352                 :         53 :         lpm->number_tbl8s = config->number_tbl8s;
     353                 :         53 :         strlcpy(lpm->name, name, sizeof(lpm->name));
     354                 :         53 :         lpm->rules_tbl = rules_tbl;
     355                 :         53 :         lpm->tbl8_pool = tbl8_pool;
     356                 :         53 :         lpm->tbl8_hdrs = tbl8_hdrs;
     357                 :            : 
     358                 :            :         /* init the stack */
     359                 :            :         tbl8_pool_init(lpm);
     360                 :            : 
     361                 :         53 :         te->data = (void *) lpm;
     362                 :            : 
     363                 :         53 :         TAILQ_INSERT_TAIL(lpm_list, te, next);
     364                 :         53 :         rte_mcfg_tailq_write_unlock();
     365                 :         53 :         return lpm;
     366                 :            : 
     367                 :          0 : fail:
     368                 :          0 :         rte_mcfg_tailq_write_unlock();
     369                 :            : 
     370                 :          1 : fail_wo_unlock:
     371                 :          1 :         rte_free(tbl8_hdrs);
     372                 :          1 :         rte_free(tbl8_pool);
     373                 :          1 :         rte_hash_free(rules_tbl);
     374                 :            : 
     375                 :          1 :         return NULL;
     376                 :            : }
     377                 :            : 
     378                 :            : /*
     379                 :            :  * Find an existing lpm table and return a pointer to it.
     380                 :            :  */
     381                 :            : struct rte_lpm6 *
     382                 :          2 : rte_lpm6_find_existing(const char *name)
     383                 :            : {
     384                 :            :         struct rte_lpm6 *l = NULL;
     385                 :            :         struct rte_tailq_entry *te;
     386                 :            :         struct rte_lpm6_list *lpm_list;
     387                 :            : 
     388                 :          2 :         lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
     389                 :            : 
     390                 :          2 :         rte_mcfg_tailq_read_lock();
     391         [ +  + ]:          3 :         TAILQ_FOREACH(te, lpm_list, next) {
     392                 :          2 :                 l = (struct rte_lpm6 *) te->data;
     393         [ +  + ]:          2 :                 if (strncmp(name, l->name, RTE_LPM6_NAMESIZE) == 0)
     394                 :            :                         break;
     395                 :            :         }
     396                 :          2 :         rte_mcfg_tailq_read_unlock();
     397                 :            : 
     398         [ +  + ]:          2 :         if (te == NULL) {
     399                 :          1 :                 rte_errno = ENOENT;
     400                 :          1 :                 return NULL;
     401                 :            :         }
     402                 :            : 
     403                 :            :         return l;
     404                 :            : }
     405                 :            : 
     406                 :            : /*
     407                 :            :  * Deallocates memory for given LPM table.
     408                 :            :  */
     409                 :            : void
     410                 :         54 : rte_lpm6_free(struct rte_lpm6 *lpm)
     411                 :            : {
     412                 :            :         struct rte_lpm6_list *lpm_list;
     413                 :            :         struct rte_tailq_entry *te;
     414                 :            : 
     415                 :            :         /* Check user arguments. */
     416         [ +  + ]:         54 :         if (lpm == NULL)
     417                 :            :                 return;
     418                 :            : 
     419                 :         53 :         lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
     420                 :            : 
     421                 :         53 :         rte_mcfg_tailq_write_lock();
     422                 :            : 
     423                 :            :         /* find our tailq entry */
     424         [ +  - ]:         53 :         TAILQ_FOREACH(te, lpm_list, next) {
     425         [ -  + ]:         53 :                 if (te->data == (void *) lpm)
     426                 :            :                         break;
     427                 :            :         }
     428                 :            : 
     429         [ +  - ]:         53 :         if (te != NULL)
     430         [ +  + ]:         53 :                 TAILQ_REMOVE(lpm_list, te, next);
     431                 :            : 
     432                 :         53 :         rte_mcfg_tailq_write_unlock();
     433                 :            : 
     434                 :         53 :         rte_free(lpm->tbl8_hdrs);
     435                 :         53 :         rte_free(lpm->tbl8_pool);
     436                 :         53 :         rte_hash_free(lpm->rules_tbl);
     437                 :         53 :         rte_free(lpm);
     438                 :         53 :         rte_free(te);
     439                 :            : }
     440                 :            : 
     441                 :            : /* Find a rule */
     442                 :            : static inline int
     443                 :            : rule_find_with_key(struct rte_lpm6 *lpm,
     444                 :            :                   const struct rte_lpm6_rule_key *rule_key,
     445                 :            :                   uint32_t *next_hop)
     446                 :            : {
     447                 :            :         uint64_t hash_val;
     448                 :            :         int ret;
     449                 :            : 
     450                 :            :         /* lookup for a rule */
     451                 :       1494 :         ret = rte_hash_lookup_data(lpm->rules_tbl, (const void *) rule_key,
     452                 :            :                 (void **) &hash_val);
     453   [ +  +  +  +  :       6056 :         if (ret >= 0) {
                   +  + ]
     454                 :         22 :                 *next_hop = (uint32_t) hash_val;
     455                 :          3 :                 return 1;
     456                 :            :         }
     457                 :            : 
     458                 :            :         return 0;
     459                 :            : }
     460                 :            : 
     461                 :            : /* Find a rule */
     462                 :            : static int
     463                 :            : rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
     464                 :            :                   uint32_t *next_hop)
     465                 :            : {
     466                 :            :         struct rte_lpm6_rule_key rule_key;
     467                 :            : 
     468                 :            :         /* init a rule key */
     469                 :            :         rule_key_init(&rule_key, ip, depth);
     470                 :            : 
     471                 :            :         return rule_find_with_key(lpm, &rule_key, next_hop);
     472                 :            : }
     473                 :            : 
     474                 :            : /*
     475                 :            :  * Checks if a rule already exists in the rules table and updates
     476                 :            :  * the nexthop if so. Otherwise it adds a new rule if enough space is available.
     477                 :            :  *
     478                 :            :  * Returns:
     479                 :            :  *    0 - next hop of existed rule is updated
     480                 :            :  *    1 - new rule successfully added
     481                 :            :  *   <0 - error
     482                 :            :  */
     483                 :            : static inline int
     484         [ +  + ]:       1487 : rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)
     485                 :            : {
     486                 :            :         int ret, rule_exist;
     487                 :            :         struct rte_lpm6_rule_key rule_key;
     488                 :            :         uint32_t unused;
     489                 :            : 
     490                 :            :         /* init a rule key */
     491                 :            :         rule_key_init(&rule_key, ip, depth);
     492                 :            : 
     493                 :            :         /* Scan through rule list to see if rule already exists. */
     494                 :            :         rule_exist = rule_find_with_key(lpm, &rule_key, &unused);
     495                 :            : 
     496                 :            :         /*
     497                 :            :          * If rule does not exist check if there is space to add a new rule to
     498                 :            :          * this rule group. If there is no space return error.
     499                 :            :          */
     500         [ +  + ]:       1460 :         if (!rule_exist && lpm->used_rules == lpm->max_rules)
     501                 :            :                 return -ENOSPC;
     502                 :            : 
     503                 :            :         /* add the rule or update rules next hop */
     504                 :       1485 :         ret = rte_hash_add_key_data(lpm->rules_tbl, &rule_key,
     505                 :       1485 :                 (void *)(uintptr_t) next_hop);
     506         [ +  - ]:       1485 :         if (ret < 0)
     507                 :            :                 return ret;
     508                 :            : 
     509                 :            :         /* Increment the used rules counter for this rule group. */
     510         [ +  + ]:       1485 :         if (!rule_exist) {
     511                 :       1458 :                 lpm->used_rules++;
     512                 :       1458 :                 return 1;
     513                 :            :         }
     514                 :            : 
     515                 :            :         return 0;
     516                 :            : }
     517                 :            : 
     518                 :            : /*
     519                 :            :  * Function that expands a rule across the data structure when a less-generic
     520                 :            :  * one has been added before. It assures that every possible combination of bits
     521                 :            :  * in the IP address returns a match.
     522                 :            :  */
     523                 :            : static void
     524                 :      18333 : expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t old_depth,
     525                 :            :                 uint8_t new_depth, uint32_t next_hop, uint8_t valid)
     526                 :            : {
     527                 :            :         uint32_t tbl8_group_end, tbl8_gindex_next, j;
     528                 :            : 
     529                 :      18333 :         tbl8_group_end = tbl8_gindex + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
     530                 :            : 
     531                 :      18333 :         struct rte_lpm6_tbl_entry new_tbl8_entry = {
     532                 :            :                 .valid = valid,
     533                 :            :                 .valid_group = valid,
     534                 :            :                 .depth = new_depth,
     535                 :            :                 .next_hop = next_hop,
     536                 :            :                 .ext_entry = 0,
     537                 :            :         };
     538                 :            : 
     539         [ +  + ]:    4711581 :         for (j = tbl8_gindex; j < tbl8_group_end; j++) {
     540   [ +  +  +  + ]:    4693248 :                 if (!lpm->tbl8[j].valid || (lpm->tbl8[j].ext_entry == 0
     541         [ +  + ]:    4498626 :                                 && lpm->tbl8[j].depth <= old_depth)) {
     542                 :            : 
     543                 :    1722425 :                         lpm->tbl8[j] = new_tbl8_entry;
     544                 :            : 
     545         [ +  + ]:    2970823 :                 } else if (lpm->tbl8[j].ext_entry == 1) {
     546                 :            : 
     547                 :      15615 :                         tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex
     548                 :      15615 :                                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
     549                 :      15615 :                         expand_rule(lpm, tbl8_gindex_next, old_depth, new_depth,
     550                 :            :                                         next_hop, valid);
     551                 :            :                 }
     552                 :            :         }
     553                 :      18333 : }
     554                 :            : 
     555                 :            : /*
     556                 :            :  * Init a tbl8 header
     557                 :            :  */
     558                 :            : static inline void
     559                 :            : init_tbl8_header(struct rte_lpm6 *lpm, uint32_t tbl_ind,
     560                 :            :                 uint32_t owner_tbl_ind, uint32_t owner_entry_ind)
     561                 :            : {
     562                 :       6275 :         struct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind];
     563                 :       6275 :         tbl_hdr->owner_tbl_ind = owner_tbl_ind;
     564                 :       6275 :         tbl_hdr->owner_entry_ind = owner_entry_ind;
     565                 :       6275 :         tbl_hdr->ref_cnt = 0;
     566                 :            : }
     567                 :            : 
     568                 :            : /*
     569                 :            :  * Calculate index to the table based on the number and position
     570                 :            :  * of the bytes being inspected in this step.
     571                 :            :  */
     572                 :            : static uint32_t
     573                 :            : get_bitshift(const uint8_t *ip, uint8_t first_byte, uint8_t bytes)
     574                 :            : {
     575                 :            :         uint32_t entry_ind, i;
     576                 :            :         int8_t bitshift;
     577                 :            : 
     578                 :            :         entry_ind = 0;
     579   [ +  +  +  + ]:      27506 :         for (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {
     580                 :      16728 :                 bitshift = (int8_t)((bytes - i)*BYTE_SIZE);
     581                 :            : 
     582                 :            :                 if (bitshift < 0)
     583                 :            :                         bitshift = 0;
     584                 :      16728 :                 entry_ind = entry_ind | ip[i-1] << bitshift;
     585                 :            :         }
     586                 :            : 
     587                 :            :         return entry_ind;
     588                 :            : }
     589                 :            : 
     590                 :            : /*
     591                 :            :  * Simulate adding a new route to the LPM counting number
     592                 :            :  * of new tables that will be needed
     593                 :            :  *
     594                 :            :  * It returns 0 on success, or 1 if
     595                 :            :  * the process needs to be continued by calling the function again.
     596                 :            :  */
     597                 :            : static inline int
     598                 :       2262 : simulate_add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
     599                 :            :                 struct rte_lpm6_tbl_entry **next_tbl, const uint8_t *ip,
     600                 :            :                 uint8_t bytes, uint8_t first_byte, uint8_t depth,
     601                 :            :                 uint32_t *need_tbl_nb)
     602                 :            : {
     603                 :            :         uint32_t entry_ind;
     604                 :            :         uint8_t bits_covered;
     605                 :            :         uint32_t next_tbl_ind;
     606                 :            : 
     607                 :            :         /*
     608                 :            :          * Calculate index to the table based on the number and position
     609                 :            :          * of the bytes being inspected in this step.
     610                 :            :          */
     611                 :       2262 :         entry_ind = get_bitshift(ip, first_byte, bytes);
     612                 :            : 
     613                 :            :         /* Number of bits covered in this step */
     614                 :       2262 :         bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);
     615                 :            : 
     616         [ +  + ]:       2262 :         if (depth <= bits_covered) {
     617                 :        359 :                 *need_tbl_nb = 0;
     618                 :        359 :                 return 0;
     619                 :            :         }
     620                 :            : 
     621         [ +  + ]:       1903 :         if (tbl[entry_ind].valid == 0 || tbl[entry_ind].ext_entry == 0) {
     622                 :            :                 /* from this point on a new table is needed on each level
     623                 :            :                  * that is not covered yet
     624                 :            :                  */
     625                 :       1131 :                 depth -= bits_covered;
     626                 :       1131 :                 uint32_t cnt = depth >> 3; /* depth / BYTE_SIZE */
     627         [ +  + ]:       1131 :                 if (depth & 7) /* 0b00000111 */
     628                 :            :                         /* if depth % 8 > 0 then one more table is needed
     629                 :            :                          * for those last bits
     630                 :            :                          */
     631                 :        978 :                         cnt++;
     632                 :            : 
     633                 :       1131 :                 *need_tbl_nb = cnt;
     634                 :       1131 :                 return 0;
     635                 :            :         }
     636                 :            : 
     637                 :        772 :         next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex;
     638                 :        772 :         *next_tbl = &(lpm->tbl8[next_tbl_ind *
     639                 :            :                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
     640                 :        772 :         *need_tbl_nb = 0;
     641                 :        772 :         return 1;
     642                 :            : }
     643                 :            : 
     644                 :            : /*
     645                 :            :  * Partially adds a new route to the data structure (tbl24+tbl8s).
     646                 :            :  * It returns 0 on success, a negative number on failure, or 1 if
     647                 :            :  * the process needs to be continued by calling the function again.
     648                 :            :  */
     649                 :            : static inline int
     650                 :       8516 : add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
     651                 :            :                 uint32_t tbl_ind, struct rte_lpm6_tbl_entry **next_tbl,
     652                 :            :                 uint32_t *next_tbl_ind, uint8_t *ip, uint8_t bytes,
     653                 :            :                 uint8_t first_byte, uint8_t depth, uint32_t next_hop,
     654                 :            :                 uint8_t is_new_rule)
     655                 :            : {
     656                 :            :         uint32_t entry_ind, tbl_range, tbl8_group_start, tbl8_group_end, i;
     657                 :            :         uint32_t tbl8_gindex;
     658                 :            :         uint8_t bits_covered;
     659                 :            :         int ret;
     660                 :            : 
     661                 :            :         /*
     662                 :            :          * Calculate index to the table based on the number and position
     663                 :            :          * of the bytes being inspected in this step.
     664                 :            :          */
     665                 :       8516 :         entry_ind = get_bitshift(ip, first_byte, bytes);
     666                 :            : 
     667                 :            :         /* Number of bits covered in this step */
     668                 :       8516 :         bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);
     669                 :            : 
     670                 :            :         /*
     671                 :            :          * If depth if smaller than this number (ie this is the last step)
     672                 :            :          * expand the rule across the relevant positions in the table.
     673                 :            :          */
     674         [ +  + ]:       8516 :         if (depth <= bits_covered) {
     675                 :       1485 :                 tbl_range = 1 << (bits_covered - depth);
     676                 :            : 
     677         [ +  + ]:  160450456 :                 for (i = entry_ind; i < (entry_ind + tbl_range); i++) {
     678   [ +  +  +  + ]:  160448971 :                         if (!tbl[i].valid || (tbl[i].ext_entry == 0 &&
     679         [ +  + ]:  118464127 :                                         tbl[i].depth <= depth)) {
     680                 :            : 
     681                 :   99764208 :                                 struct rte_lpm6_tbl_entry new_tbl_entry = {
     682                 :            :                                         .next_hop = next_hop,
     683                 :            :                                         .depth = depth,
     684                 :            :                                         .valid = VALID,
     685                 :            :                                         .valid_group = VALID,
     686                 :            :                                         .ext_entry = 0,
     687                 :            :                                 };
     688                 :            : 
     689                 :   99764208 :                                 tbl[i] = new_tbl_entry;
     690                 :            : 
     691         [ +  + ]:   60684763 :                         } else if (tbl[i].ext_entry == 1) {
     692                 :            : 
     693                 :            :                                 /*
     694                 :            :                                  * If tbl entry is valid and extended calculate the index
     695                 :            :                                  * into next tbl8 and expand the rule across the data structure.
     696                 :            :                                  */
     697                 :       2716 :                                 tbl8_gindex = tbl[i].lpm6_tbl8_gindex *
     698                 :            :                                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
     699                 :       2716 :                                 expand_rule(lpm, tbl8_gindex, depth, depth,
     700                 :            :                                                 next_hop, VALID);
     701                 :            :                         }
     702                 :            :                 }
     703                 :            : 
     704                 :            :                 /* update tbl8 rule reference counter */
     705         [ +  + ]:       1485 :                 if (tbl_ind != TBL24_IND && is_new_rule)
     706                 :       1225 :                         lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
     707                 :            : 
     708                 :       1485 :                 return 0;
     709                 :            :         }
     710                 :            :         /*
     711                 :            :          * If this is not the last step just fill one position
     712                 :            :          * and calculate the index to the next table.
     713                 :            :          */
     714                 :            :         else {
     715                 :            :                 /* If it's invalid a new tbl8 is needed */
     716         [ +  + ]:       7031 :                 if (!tbl[entry_ind].valid) {
     717                 :            :                         /* get a new table */
     718                 :            :                         ret = tbl8_get(lpm, &tbl8_gindex);
     719                 :            :                         if (ret != 0)
     720                 :            :                                 return -ENOSPC;
     721                 :            : 
     722                 :            :                         /* invalidate all new tbl8 entries */
     723                 :       1445 :                         tbl8_group_start = tbl8_gindex *
     724                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
     725         [ +  + ]:       1445 :                         memset(&lpm->tbl8[tbl8_group_start], 0,
     726                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES *
     727                 :            :                                         sizeof(struct rte_lpm6_tbl_entry));
     728                 :            : 
     729                 :            :                         /* init the new table's header:
     730                 :            :                          *   save the reference to the owner table
     731                 :            :                          */
     732                 :            :                         init_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind);
     733                 :            : 
     734                 :            :                         /* reference to a new tbl8 */
     735                 :       1445 :                         struct rte_lpm6_tbl_entry new_tbl_entry = {
     736                 :            :                                 .lpm6_tbl8_gindex = tbl8_gindex,
     737                 :            :                                 .depth = 0,
     738                 :            :                                 .valid = VALID,
     739                 :            :                                 .valid_group = VALID,
     740                 :            :                                 .ext_entry = 1,
     741                 :            :                         };
     742                 :            : 
     743                 :       1445 :                         tbl[entry_ind] = new_tbl_entry;
     744                 :            : 
     745                 :            :                         /* update the current table's reference counter */
     746         [ +  + ]:       1445 :                         if (tbl_ind != TBL24_IND)
     747                 :       1027 :                                 lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
     748                 :            :                 }
     749                 :            :                 /*
     750                 :            :                  * If it's valid but not extended the rule that was stored
     751                 :            :                  * here needs to be moved to the next table.
     752                 :            :                  */
     753         [ +  + ]:       5586 :                 else if (tbl[entry_ind].ext_entry == 0) {
     754                 :            :                         /* get a new tbl8 index */
     755                 :            :                         ret = tbl8_get(lpm, &tbl8_gindex);
     756                 :            :                         if (ret != 0)
     757                 :            :                                 return -ENOSPC;
     758                 :            : 
     759                 :       4830 :                         tbl8_group_start = tbl8_gindex *
     760                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
     761                 :       4830 :                         tbl8_group_end = tbl8_group_start +
     762                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
     763                 :            : 
     764                 :            :                         struct rte_lpm6_tbl_entry tbl_entry = {
     765                 :       4830 :                                 .next_hop = tbl[entry_ind].next_hop,
     766                 :       4830 :                                 .depth = tbl[entry_ind].depth,
     767                 :            :                                 .valid = VALID,
     768                 :            :                                 .valid_group = VALID,
     769                 :            :                                 .ext_entry = 0
     770                 :            :                         };
     771                 :            : 
     772                 :            :                         /* Populate new tbl8 with tbl value. */
     773         [ +  + ]:    1241310 :                         for (i = tbl8_group_start; i < tbl8_group_end; i++)
     774                 :    1236480 :                                 lpm->tbl8[i] = tbl_entry;
     775                 :            : 
     776                 :            :                         /* init the new table's header:
     777                 :            :                          *   save the reference to the owner table
     778                 :            :                          */
     779                 :            :                         init_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind);
     780                 :            : 
     781                 :            :                         /*
     782                 :            :                          * Update tbl entry to point to new tbl8 entry. Note: The
     783                 :            :                          * ext_flag and tbl8_index need to be updated simultaneously,
     784                 :            :                          * so assign whole structure in one go.
     785                 :            :                          */
     786                 :       4830 :                         struct rte_lpm6_tbl_entry new_tbl_entry = {
     787                 :            :                                 .lpm6_tbl8_gindex = tbl8_gindex,
     788                 :            :                                 .depth = 0,
     789                 :            :                                 .valid = VALID,
     790                 :            :                                 .valid_group = VALID,
     791                 :            :                                 .ext_entry = 1,
     792                 :            :                         };
     793                 :            : 
     794                 :       4830 :                         tbl[entry_ind] = new_tbl_entry;
     795                 :            : 
     796                 :            :                         /* update the current table's reference counter */
     797         [ +  + ]:       4830 :                         if (tbl_ind != TBL24_IND)
     798                 :       4132 :                                 lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
     799                 :            :                 }
     800                 :            : 
     801                 :       7031 :                 *next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex;
     802                 :       7031 :                 *next_tbl = &(lpm->tbl8[*next_tbl_ind *
     803                 :            :                                   RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
     804                 :            :         }
     805                 :            : 
     806                 :       7031 :         return 1;
     807                 :            : }
     808                 :            : 
     809                 :            : /*
     810                 :            :  * Simulate adding a route to LPM
     811                 :            :  *
     812                 :            :  *      Returns:
     813                 :            :  *    0 on success
     814                 :            :  *    -ENOSPC not enough tbl8 left
     815                 :            :  */
     816                 :            : static int
     817                 :       1490 : simulate_add(struct rte_lpm6 *lpm, const uint8_t *masked_ip, uint8_t depth)
     818                 :            : {
     819                 :            :         struct rte_lpm6_tbl_entry *tbl;
     820                 :       1490 :         struct rte_lpm6_tbl_entry *tbl_next = NULL;
     821                 :            :         int ret, i;
     822                 :            : 
     823                 :            :         /* number of new tables needed for a step */
     824                 :            :         uint32_t need_tbl_nb;
     825                 :            :         /* total number of new tables needed */
     826                 :            :         uint32_t total_need_tbl_nb;
     827                 :            : 
     828                 :            :         /* Inspect the first three bytes through tbl24 on the first step. */
     829                 :       1490 :         ret = simulate_add_step(lpm, lpm->tbl24, &tbl_next, masked_ip,
     830                 :            :                 ADD_FIRST_BYTE, 1, depth, &need_tbl_nb);
     831                 :       1490 :         total_need_tbl_nb = need_tbl_nb;
     832                 :            :         /*
     833                 :            :          * Inspect one by one the rest of the bytes until
     834                 :            :          * the process is completed.
     835                 :            :          */
     836         [ +  + ]:       2262 :         for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && ret == 1; i++) {
     837                 :        772 :                 tbl = tbl_next;
     838                 :        772 :                 ret = simulate_add_step(lpm, tbl, &tbl_next, masked_ip, 1,
     839                 :        772 :                         (uint8_t)(i + 1), depth, &need_tbl_nb);
     840                 :        772 :                 total_need_tbl_nb += need_tbl_nb;
     841                 :            :         }
     842                 :            : 
     843         [ +  + ]:       1490 :         if (tbl8_available(lpm) < total_need_tbl_nb)
     844                 :            :                 /* not enough tbl8 to add a rule */
     845                 :          3 :                 return -ENOSPC;
     846                 :            : 
     847                 :            :         return 0;
     848                 :            : }
     849                 :            : 
     850                 :            : /*
     851                 :            :  * Add a route
     852                 :            :  */
     853                 :            : int
     854                 :       1493 : rte_lpm6_add(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth,
     855                 :            :              uint32_t next_hop)
     856                 :            : {
     857                 :            :         struct rte_lpm6_tbl_entry *tbl;
     858                 :       1493 :         struct rte_lpm6_tbl_entry *tbl_next = NULL;
     859                 :            :         /* init to avoid compiler warning */
     860                 :       1493 :         uint32_t tbl_next_num = 123456;
     861                 :            :         int status;
     862                 :            :         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
     863                 :            :         int i;
     864                 :            : 
     865                 :            :         /* Check user arguments. */
     866   [ +  +  +  + ]:       1493 :         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
     867                 :            :                 return -EINVAL;
     868                 :            : 
     869                 :            :         /* Copy the IP and mask it to avoid modifying user's input data. */
     870                 :            :         ip6_copy_addr(masked_ip, ip);
     871                 :       1490 :         ip6_mask_addr(masked_ip, depth);
     872                 :            : 
     873                 :            :         /* Simulate adding a new route */
     874                 :       1490 :         int ret = simulate_add(lpm, masked_ip, depth);
     875         [ +  + ]:       1490 :         if (ret < 0)
     876                 :            :                 return ret;
     877                 :            : 
     878                 :            :         /* Add the rule to the rule table. */
     879                 :       1487 :         int is_new_rule = rule_add(lpm, masked_ip, depth, next_hop);
     880                 :            :         /* If there is no space available for new rule return error. */
     881         [ +  + ]:       1487 :         if (is_new_rule < 0)
     882                 :            :                 return is_new_rule;
     883                 :            : 
     884                 :            :         /* Inspect the first three bytes through tbl24 on the first step. */
     885                 :       1485 :         tbl = lpm->tbl24;
     886                 :       1485 :         status = add_step(lpm, tbl, TBL24_IND, &tbl_next, &tbl_next_num,
     887                 :            :                 masked_ip, ADD_FIRST_BYTE, 1, depth, next_hop,
     888                 :            :                 is_new_rule);
     889         [ -  + ]:       1485 :         assert(status >= 0);
     890                 :            : 
     891                 :            :         /*
     892                 :            :          * Inspect one by one the rest of the bytes until
     893                 :            :          * the process is completed.
     894                 :            :          */
     895         [ +  + ]:       8516 :         for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && status == 1; i++) {
     896                 :       7031 :                 tbl = tbl_next;
     897                 :       7031 :                 status = add_step(lpm, tbl, tbl_next_num, &tbl_next,
     898                 :       7031 :                         &tbl_next_num, masked_ip, 1, (uint8_t)(i + 1),
     899                 :            :                         depth, next_hop, is_new_rule);
     900         [ -  + ]:       7031 :                 assert(status >= 0);
     901                 :            :         }
     902                 :            : 
     903                 :            :         return status;
     904                 :            : }
     905                 :            : 
     906                 :            : /*
     907                 :            :  * Takes a pointer to a table entry and inspect one level.
     908                 :            :  * The function returns 0 on lookup success, ENOENT if no match was found
     909                 :            :  * or 1 if the process needs to be continued by calling the function again.
     910                 :            :  */
     911                 :            : static inline int
     912                 :            : lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
     913                 :            :                 const struct rte_lpm6_tbl_entry **tbl_next, const uint8_t *ip,
     914                 :            :                 uint8_t first_byte, uint32_t *next_hop)
     915                 :            : {
     916                 :            :         uint32_t tbl8_index, tbl_entry;
     917                 :            : 
     918                 :            :         /* Take the integer value from the pointer. */
     919                 :    1505327 :         tbl_entry = *(const uint32_t *)tbl;
     920                 :            : 
     921                 :            :         /* If it is valid and extended we calculate the new pointer to return. */
     922                 :    1505327 :         if ((tbl_entry & RTE_LPM6_VALID_EXT_ENTRY_BITMASK) ==
     923                 :            :                         RTE_LPM6_VALID_EXT_ENTRY_BITMASK) {
     924                 :            : 
     925                 :    1338820 :                 tbl8_index = ip[first_byte-1] +
     926                 :    1338820 :                                 ((tbl_entry & RTE_LPM6_TBL8_BITMASK) *
     927                 :            :                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES);
     928                 :            : 
     929                 :    1338748 :                 *tbl_next = &lpm->tbl8[tbl8_index];
     930                 :            : 
     931                 :         72 :                 return 1;
     932                 :            :         } else {
     933                 :            :                 /* If not extended then we can have a match. */
     934                 :     166507 :                 *next_hop = ((uint32_t)tbl_entry & RTE_LPM6_TBL8_BITMASK);
     935   [ +  +  +  + ]:     166507 :                 return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT;
     936                 :            :         }
     937                 :            : }
     938                 :            : 
     939                 :            : /*
     940                 :            :  * Looks up an IP
     941                 :            :  */
     942                 :            : int
     943                 :     166481 : rte_lpm6_lookup(const struct rte_lpm6 *lpm, const uint8_t *ip,
     944                 :            :                 uint32_t *next_hop)
     945                 :            : {
     946                 :            :         const struct rte_lpm6_tbl_entry *tbl;
     947                 :            :         const struct rte_lpm6_tbl_entry *tbl_next = NULL;
     948                 :            :         int status;
     949                 :            :         uint8_t first_byte;
     950                 :            :         uint32_t tbl24_index;
     951                 :            : 
     952                 :            :         /* DEBUG: Check user input arguments. */
     953   [ +  +  +  + ]:     166481 :         if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL))
     954                 :            :                 return -EINVAL;
     955                 :            : 
     956                 :            :         first_byte = LOOKUP_FIRST_BYTE;
     957                 :     166478 :         tbl24_index = (ip[0] << BYTES2_SIZE) | (ip[1] << BYTE_SIZE) | ip[2];
     958                 :            : 
     959                 :            :         /* Calculate pointer to the first entry to be inspected */
     960                 :     166478 :         tbl = &lpm->tbl24[tbl24_index];
     961                 :            : 
     962                 :            :         do {
     963                 :            :                 /* Continue inspecting following levels until success or failure */
     964         [ +  + ]:    1505226 :                 status = lookup_step(lpm, tbl, &tbl_next, ip, first_byte++, next_hop);
     965                 :            :                 tbl = tbl_next;
     966                 :            :         } while (status == 1);
     967                 :            : 
     968                 :            :         return status;
     969                 :            : }
     970                 :            : 
     971                 :            : /*
     972                 :            :  * Looks up a group of IP addresses
     973                 :            :  */
     974                 :            : int
     975                 :          9 : rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
     976                 :            :                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
     977                 :            :                 int32_t *next_hops, unsigned int n)
     978                 :            : {
     979                 :            :         unsigned int i;
     980                 :            :         const struct rte_lpm6_tbl_entry *tbl;
     981                 :            :         const struct rte_lpm6_tbl_entry *tbl_next = NULL;
     982                 :            :         uint32_t tbl24_index, next_hop;
     983                 :            :         uint8_t first_byte;
     984                 :            :         int status;
     985                 :            : 
     986                 :            :         /* DEBUG: Check user input arguments. */
     987   [ +  +  +  + ]:          9 :         if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL))
     988                 :            :                 return -EINVAL;
     989                 :            : 
     990         [ +  + ]:         35 :         for (i = 0; i < n; i++) {
     991                 :            :                 first_byte = LOOKUP_FIRST_BYTE;
     992                 :         29 :                 tbl24_index = (ips[i][0] << BYTES2_SIZE) |
     993                 :         29 :                                 (ips[i][1] << BYTE_SIZE) | ips[i][2];
     994                 :            : 
     995                 :            :                 /* Calculate pointer to the first entry to be inspected */
     996                 :         29 :                 tbl = &lpm->tbl24[tbl24_index];
     997                 :            : 
     998                 :            :                 do {
     999                 :            :                         /* Continue inspecting following levels
    1000                 :            :                          * until success or failure
    1001                 :            :                          */
    1002                 :            :                         status = lookup_step(lpm, tbl, &tbl_next, ips[i],
    1003         [ +  + ]:        101 :                                         first_byte++, &next_hop);
    1004                 :            :                         tbl = tbl_next;
    1005         [ +  + ]:        101 :                 } while (status == 1);
    1006                 :            : 
    1007         [ +  + ]:         29 :                 if (status < 0)
    1008                 :         15 :                         next_hops[i] = -1;
    1009                 :            :                 else
    1010                 :         14 :                         next_hops[i] = (int32_t)next_hop;
    1011                 :            :         }
    1012                 :            : 
    1013                 :            :         return 0;
    1014                 :            : }
    1015                 :            : 
    1016                 :            : /*
    1017                 :            :  * Look for a rule in the high-level rules table
    1018                 :            :  */
    1019                 :            : int
    1020                 :          7 : rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth,
    1021                 :            :                          uint32_t *next_hop)
    1022                 :            : {
    1023                 :            :         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
    1024                 :            : 
    1025                 :            :         /* Check user arguments. */
    1026         [ +  - ]:          7 :         if ((lpm == NULL) || next_hop == NULL || ip == NULL ||
    1027   [ +  -  +  - ]:          7 :                         (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
    1028                 :            :                 return -EINVAL;
    1029                 :            : 
    1030                 :            :         /* Copy the IP and mask it to avoid modifying user's input data. */
    1031                 :            :         ip6_copy_addr(masked_ip, ip);
    1032                 :            :         ip6_mask_addr(masked_ip, depth);
    1033                 :            : 
    1034                 :          7 :         return rule_find(lpm, masked_ip, depth, next_hop);
    1035                 :            : }
    1036                 :            : 
    1037                 :            : /*
    1038                 :            :  * Delete a rule from the rule table.
    1039                 :            :  * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
    1040                 :            :  * return
    1041                 :            :  *        0 on success
    1042                 :            :  *   <0 on failure
    1043                 :            :  */
    1044                 :            : static inline int
    1045         [ +  + ]:         80 : rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
    1046                 :            : {
    1047                 :            :         int ret;
    1048                 :            :         struct rte_lpm6_rule_key rule_key;
    1049                 :            : 
    1050                 :            :         /* init rule key */
    1051                 :            :         rule_key_init(&rule_key, ip, depth);
    1052                 :            : 
    1053                 :            :         /* delete the rule */
    1054                 :         80 :         ret = rte_hash_del_key(lpm->rules_tbl, (void *) &rule_key);
    1055         [ +  + ]:         80 :         if (ret >= 0)
    1056                 :         77 :                 lpm->used_rules--;
    1057                 :            : 
    1058                 :         80 :         return ret;
    1059                 :            : }
    1060                 :            : 
    1061                 :            : /*
    1062                 :            :  * Deletes a group of rules
    1063                 :            :  *
    1064                 :            :  * Note that the function rebuilds the lpm table,
    1065                 :            :  * rather than doing incremental updates like
    1066                 :            :  * the regular delete function
    1067                 :            :  */
    1068                 :            : int
    1069                 :          7 : rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
    1070                 :            :                 uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths,
    1071                 :            :                 unsigned n)
    1072                 :            : {
    1073                 :            :         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
    1074                 :            :         unsigned i;
    1075                 :            : 
    1076                 :            :         /* Check input arguments. */
    1077   [ +  +  +  + ]:          7 :         if ((lpm == NULL) || (ips == NULL) || (depths == NULL))
    1078                 :            :                 return -EINVAL;
    1079                 :            : 
    1080         [ +  + ]:         10 :         for (i = 0; i < n; i++) {
    1081         [ +  + ]:          6 :                 ip6_copy_addr(masked_ip, ips[i]);
    1082                 :          6 :                 ip6_mask_addr(masked_ip, depths[i]);
    1083                 :          6 :                 rule_delete(lpm, masked_ip, depths[i]);
    1084                 :            :         }
    1085                 :            : 
    1086                 :            :         /*
    1087                 :            :          * Set all the table entries to 0 (ie delete every rule
    1088                 :            :          * from the data structure.
    1089                 :            :          */
    1090                 :          4 :         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
    1091                 :          4 :         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
    1092                 :          4 :                         * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
    1093                 :            :         tbl8_pool_init(lpm);
    1094                 :            : 
    1095                 :            :         /*
    1096                 :            :          * Add every rule again (except for the ones that were removed from
    1097                 :            :          * the rules table).
    1098                 :            :          */
    1099                 :          4 :         rebuild_lpm(lpm);
    1100                 :            : 
    1101                 :          4 :         return 0;
    1102                 :            : }
    1103                 :            : 
    1104                 :            : /*
    1105                 :            :  * Delete all rules from the LPM table.
    1106                 :            :  */
    1107                 :            : void
    1108                 :         10 : rte_lpm6_delete_all(struct rte_lpm6 *lpm)
    1109                 :            : {
    1110                 :            :         /* Zero used rules counter. */
    1111                 :         10 :         lpm->used_rules = 0;
    1112                 :            : 
    1113                 :            :         /* Zero tbl24. */
    1114                 :         10 :         memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
    1115                 :            : 
    1116                 :            :         /* Zero tbl8. */
    1117                 :         10 :         memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *
    1118                 :         10 :                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
    1119                 :            : 
    1120                 :            :         /* init pool of free tbl8 indexes */
    1121                 :            :         tbl8_pool_init(lpm);
    1122                 :            : 
    1123                 :            :         /* Delete all rules form the rules table. */
    1124                 :         10 :         rte_hash_reset(lpm->rules_tbl);
    1125                 :         10 : }
    1126                 :            : 
    1127                 :            : /*
    1128                 :            :  * Convert a depth to a one byte long mask
    1129                 :            :  *   Example: 4 will be converted to 0xF0
    1130                 :            :  */
    1131                 :            : static uint8_t __attribute__((pure))
    1132                 :            : depth_to_mask_1b(uint8_t depth)
    1133                 :            : {
    1134                 :            :         /* To calculate a mask start with a 1 on the left hand side and right
    1135                 :            :          * shift while populating the left hand side with 1's
    1136                 :            :          */
    1137                 :       4077 :         return (signed char)0x80 >> (depth - 1);
    1138                 :            : }
    1139                 :            : 
    1140                 :            : /*
    1141                 :            :  * Find a less specific rule
    1142                 :            :  */
    1143                 :            : static int
    1144                 :         72 : rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
    1145                 :            :         struct rte_lpm6_rule *rule)
    1146                 :            : {
    1147                 :            :         int ret;
    1148                 :            :         uint32_t next_hop;
    1149                 :            :         uint8_t mask;
    1150                 :            :         struct rte_lpm6_rule_key rule_key;
    1151                 :            : 
    1152         [ +  + ]:         72 :         if (depth == 1)
    1153                 :            :                 return 0;
    1154                 :            : 
    1155                 :            :         rule_key_init(&rule_key, ip, depth);
    1156                 :            : 
    1157         [ +  + ]:       4614 :         while (depth > 1) {
    1158                 :       4562 :                 depth--;
    1159                 :            : 
    1160                 :            :                 /* each iteration zero one more bit of the key */
    1161                 :       4562 :                 mask = depth & 7; /* depth % BYTE_SIZE */
    1162         [ +  + ]:       4562 :                 if (mask > 0)
    1163                 :       4034 :                         mask = depth_to_mask_1b(mask);
    1164                 :            : 
    1165                 :       4562 :                 rule_key.depth = depth;
    1166                 :       4562 :                 rule_key.ip[depth >> 3] &= mask;
    1167                 :            : 
    1168                 :            :                 ret = rule_find_with_key(lpm, &rule_key, &next_hop);
    1169                 :            :                 if (ret) {
    1170                 :         19 :                         rule->depth = depth;
    1171         [ +  + ]:         19 :                         ip6_copy_addr(rule->ip, rule_key.ip);
    1172                 :         19 :                         rule->next_hop = next_hop;
    1173                 :         19 :                         return 1;
    1174                 :            :                 }
    1175                 :            :         }
    1176                 :            : 
    1177                 :            :         return 0;
    1178                 :            : }
    1179                 :            : 
    1180                 :            : /*
    1181                 :            :  * Find range of tbl8 cells occupied by a rule
    1182                 :            :  */
    1183                 :            : static void
    1184                 :         72 : rule_find_range(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth,
    1185                 :            :                   struct rte_lpm6_tbl_entry **from,
    1186                 :            :                   struct rte_lpm6_tbl_entry **to,
    1187                 :            :                   uint32_t *out_tbl_ind)
    1188                 :            : {
    1189                 :            :         uint32_t ind;
    1190                 :         72 :         uint32_t first_3bytes = (uint32_t)ip[0] << 16 | ip[1] << 8 | ip[2];
    1191                 :            : 
    1192         [ +  + ]:         72 :         if (depth <= 24) {
    1193                 :            :                 /* rule is within the top level */
    1194                 :            :                 ind = first_3bytes;
    1195                 :         29 :                 *from = &lpm->tbl24[ind];
    1196                 :         29 :                 ind += (1 << (24 - depth)) - 1;
    1197                 :         29 :                 *to = &lpm->tbl24[ind];
    1198                 :         29 :                 *out_tbl_ind = TBL24_IND;
    1199                 :            :         } else {
    1200                 :            :                 /* top level entry */
    1201                 :            :                 struct rte_lpm6_tbl_entry *tbl = &lpm->tbl24[first_3bytes];
    1202         [ -  + ]:         43 :                 assert(tbl->ext_entry == 1);
    1203                 :            :                 /* first tbl8 */
    1204                 :         43 :                 uint32_t tbl_ind = tbl->lpm6_tbl8_gindex;
    1205                 :         43 :                 tbl = &lpm->tbl8[tbl_ind *
    1206                 :            :                                 RTE_LPM6_TBL8_GROUP_NUM_ENTRIES];
    1207                 :            :                 /* current ip byte, the top level is already behind */
    1208                 :            :                 uint8_t byte = 3;
    1209                 :            :                 /* minus top level */
    1210                 :         43 :                 depth -= 24;
    1211                 :            : 
    1212                 :            :                 /* iterate through levels (tbl8s)
    1213                 :            :                  * until we reach the last one
    1214                 :            :                  */
    1215         [ +  + ]:        442 :                 while (depth > 8) {
    1216                 :        399 :                         tbl += ip[byte];
    1217         [ -  + ]:        399 :                         assert(tbl->ext_entry == 1);
    1218                 :            :                         /* go to the next level/tbl8 */
    1219                 :        399 :                         tbl_ind = tbl->lpm6_tbl8_gindex;
    1220                 :        399 :                         tbl = &lpm->tbl8[tbl_ind *
    1221                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES];
    1222                 :        399 :                         byte += 1;
    1223                 :        399 :                         depth -= 8;
    1224                 :            :                 }
    1225                 :            : 
    1226                 :            :                 /* last level/tbl8 */
    1227                 :         43 :                 ind = ip[byte] & depth_to_mask_1b(depth);
    1228                 :         43 :                 *from = &tbl[ind];
    1229                 :         43 :                 ind += (1 << (8 - depth)) - 1;
    1230                 :         43 :                 *to = &tbl[ind];
    1231                 :         43 :                 *out_tbl_ind = tbl_ind;
    1232                 :            :         }
    1233                 :         72 : }
    1234                 :            : 
    1235                 :            : /*
    1236                 :            :  * Remove a table from the LPM tree
    1237                 :            :  */
    1238                 :            : static void
    1239                 :        427 : remove_tbl(struct rte_lpm6 *lpm, struct rte_lpm_tbl8_hdr *tbl_hdr,
    1240                 :            :                   uint32_t tbl_ind, struct rte_lpm6_rule *lsp_rule)
    1241                 :            : {
    1242                 :            :         struct rte_lpm6_tbl_entry *owner_entry;
    1243                 :            : 
    1244         [ +  + ]:        427 :         if (tbl_hdr->owner_tbl_ind == TBL24_IND)
    1245                 :         40 :                 owner_entry = &lpm->tbl24[tbl_hdr->owner_entry_ind];
    1246                 :            :         else {
    1247                 :            :                 uint32_t owner_tbl_ind = tbl_hdr->owner_tbl_ind;
    1248                 :        387 :                 owner_entry = &lpm->tbl8[
    1249                 :        387 :                         owner_tbl_ind * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES +
    1250                 :        387 :                         tbl_hdr->owner_entry_ind];
    1251                 :            : 
    1252                 :        387 :                 struct rte_lpm_tbl8_hdr *owner_tbl_hdr =
    1253                 :        387 :                         &lpm->tbl8_hdrs[owner_tbl_ind];
    1254         [ +  - ]:        387 :                 if (--owner_tbl_hdr->ref_cnt == 0)
    1255                 :        387 :                         remove_tbl(lpm, owner_tbl_hdr, owner_tbl_ind, lsp_rule);
    1256                 :            :         }
    1257                 :            : 
    1258         [ -  + ]:        427 :         assert(owner_entry->ext_entry == 1);
    1259                 :            : 
    1260                 :            :         /* unlink the table */
    1261         [ -  + ]:        427 :         if (lsp_rule != NULL) {
    1262                 :            :                 struct rte_lpm6_tbl_entry new_tbl_entry = {
    1263                 :          0 :                         .next_hop = lsp_rule->next_hop,
    1264                 :          0 :                         .depth = lsp_rule->depth,
    1265                 :            :                         .valid = VALID,
    1266                 :            :                         .valid_group = VALID,
    1267                 :            :                         .ext_entry = 0
    1268                 :            :                 };
    1269                 :            : 
    1270                 :          0 :                 *owner_entry = new_tbl_entry;
    1271                 :            :         } else {
    1272                 :            :                 struct rte_lpm6_tbl_entry new_tbl_entry = {
    1273                 :            :                         .next_hop = 0,
    1274                 :            :                         .depth = 0,
    1275                 :            :                         .valid = INVALID,
    1276                 :            :                         .valid_group = INVALID,
    1277                 :            :                         .ext_entry = 0
    1278                 :            :                 };
    1279                 :            : 
    1280                 :        427 :                 *owner_entry = new_tbl_entry;
    1281                 :            :         }
    1282                 :            : 
    1283                 :            :         /* return the table to the pool */
    1284                 :            :         tbl8_put(lpm, tbl_ind);
    1285                 :        427 : }
    1286                 :            : 
    1287                 :            : /*
    1288                 :            :  * Deletes a rule
    1289                 :            :  */
    1290                 :            : int
    1291                 :         77 : rte_lpm6_delete(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth)
    1292                 :            : {
    1293                 :            :         uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
    1294                 :            :         struct rte_lpm6_rule lsp_rule_obj;
    1295                 :            :         struct rte_lpm6_rule *lsp_rule;
    1296                 :            :         int ret;
    1297                 :            :         uint32_t tbl_ind;
    1298                 :            :         struct rte_lpm6_tbl_entry *from, *to;
    1299                 :            : 
    1300                 :            :         /* Check input arguments. */
    1301   [ +  +  +  + ]:         77 :         if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
    1302                 :            :                 return -EINVAL;
    1303                 :            : 
    1304                 :            :         /* Copy the IP and mask it to avoid modifying user's input data. */
    1305                 :            :         ip6_copy_addr(masked_ip, ip);
    1306                 :         74 :         ip6_mask_addr(masked_ip, depth);
    1307                 :            : 
    1308                 :            :         /* Delete the rule from the rule table. */
    1309                 :         74 :         ret = rule_delete(lpm, masked_ip, depth);
    1310         [ +  + ]:         74 :         if (ret < 0)
    1311                 :            :                 return -ENOENT;
    1312                 :            : 
    1313                 :            :         /* find rule cells */
    1314                 :         72 :         rule_find_range(lpm, masked_ip, depth, &from, &to, &tbl_ind);
    1315                 :            : 
    1316                 :            :         /* find a less specific rule (a rule with smaller depth)
    1317                 :            :          * note: masked_ip will be modified, don't use it anymore
    1318                 :            :          */
    1319                 :         72 :         ret = rule_find_less_specific(lpm, masked_ip, depth,
    1320                 :            :                         &lsp_rule_obj);
    1321         [ +  + ]:         72 :         lsp_rule = ret ? &lsp_rule_obj : NULL;
    1322                 :            : 
    1323                 :            :         /* decrement the table rule counter,
    1324                 :            :          * note that tbl24 doesn't have a header
    1325                 :            :          */
    1326         [ +  + ]:         72 :         if (tbl_ind != TBL24_IND) {
    1327                 :         43 :                 struct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind];
    1328         [ +  + ]:         43 :                 if (--tbl_hdr->ref_cnt == 0) {
    1329                 :            :                         /* remove the table */
    1330                 :         40 :                         remove_tbl(lpm, tbl_hdr, tbl_ind, lsp_rule);
    1331                 :         40 :                         return 0;
    1332                 :            :                 }
    1333                 :            :         }
    1334                 :            : 
    1335                 :            :         /* iterate rule cells */
    1336         [ +  + ]:   20972588 :         for (; from <= to; from++)
    1337         [ +  + ]:   20972556 :                 if (from->ext_entry == 1) {
    1338                 :            :                         /* reference to a more specific space
    1339                 :            :                          * of the prefix/rule. Entries in a more
    1340                 :            :                          * specific space that are not used by
    1341                 :            :                          * a more specific prefix must be occupied
    1342                 :            :                          * by the prefix
    1343                 :            :                          */
    1344         [ -  + ]:          2 :                         if (lsp_rule != NULL)
    1345                 :          0 :                                 expand_rule(lpm,
    1346                 :          0 :                                         from->lpm6_tbl8_gindex *
    1347                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES,
    1348                 :          0 :                                         depth, lsp_rule->depth,
    1349                 :            :                                         lsp_rule->next_hop, VALID);
    1350                 :            :                         else
    1351                 :            :                                 /* since the prefix has no less specific prefix,
    1352                 :            :                                  * its more specific space must be invalidated
    1353                 :            :                                  */
    1354                 :          2 :                                 expand_rule(lpm,
    1355                 :          2 :                                         from->lpm6_tbl8_gindex *
    1356                 :            :                                         RTE_LPM6_TBL8_GROUP_NUM_ENTRIES,
    1357                 :            :                                         depth, 0, 0, INVALID);
    1358         [ +  - ]:   20972554 :                 } else if (from->depth == depth) {
    1359                 :            :                         /* entry is not a reference and belongs to the prefix */
    1360         [ +  + ]:   20972554 :                         if (lsp_rule != NULL) {
    1361                 :            :                                 struct rte_lpm6_tbl_entry new_tbl_entry = {
    1362                 :   12582660 :                                         .next_hop = lsp_rule->next_hop,
    1363                 :   12582660 :                                         .depth = lsp_rule->depth,
    1364                 :            :                                         .valid = VALID,
    1365                 :            :                                         .valid_group = VALID,
    1366                 :            :                                         .ext_entry = 0
    1367                 :            :                                 };
    1368                 :            : 
    1369                 :   12582660 :                                 *from = new_tbl_entry;
    1370                 :            :                         } else {
    1371                 :            :                                 struct rte_lpm6_tbl_entry new_tbl_entry = {
    1372                 :            :                                         .next_hop = 0,
    1373                 :            :                                         .depth = 0,
    1374                 :            :                                         .valid = INVALID,
    1375                 :            :                                         .valid_group = INVALID,
    1376                 :            :                                         .ext_entry = 0
    1377                 :            :                                 };
    1378                 :            : 
    1379                 :    8389894 :                                 *from = new_tbl_entry;
    1380                 :            :                         }
    1381                 :            :                 }
    1382                 :            : 
    1383                 :            :         return 0;
    1384                 :            : }

Generated by: LCOV version 1.14