LCOV - code coverage report
Current view: top level - lib/fib - trie.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 257 298 86.2 %
Date: 2024-01-22 15:55:54 Functions: 14 14 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 155 225 68.9 %

           Branch data     Line data    Source code
       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
       3                 :            :  * Copyright(c) 2019 Intel Corporation
       4                 :            :  */
       5                 :            : 
       6                 :            : #include <stdint.h>
       7                 :            : #include <stdio.h>
       8                 :            : 
       9                 :            : #include <rte_debug.h>
      10                 :            : #include <rte_malloc.h>
      11                 :            : #include <rte_errno.h>
      12                 :            : 
      13                 :            : #include <rte_rib6.h>
      14                 :            : #include <rte_fib6.h>
      15                 :            : #include "trie.h"
      16                 :            : 
      17                 :            : #ifdef CC_TRIE_AVX512_SUPPORT
      18                 :            : 
      19                 :            : #include "trie_avx512.h"
      20                 :            : 
      21                 :            : #endif /* CC_TRIE_AVX512_SUPPORT */
      22                 :            : 
      23                 :            : #define TRIE_NAMESIZE           64
      24                 :            : 
      25                 :            : enum edge {
      26                 :            :         LEDGE,
      27                 :            :         REDGE
      28                 :            : };
      29                 :            : 
      30                 :            : static inline rte_fib6_lookup_fn_t
      31                 :            : get_scalar_fn(enum rte_fib_trie_nh_sz nh_sz)
      32                 :            : {
      33   [ -  -  -  -  :          3 :         switch (nh_sz) {
             +  +  -  + ]
      34                 :            :         case RTE_FIB6_TRIE_2B:
      35                 :            :                 return rte_trie_lookup_bulk_2b;
      36                 :          1 :         case RTE_FIB6_TRIE_4B:
      37                 :          1 :                 return rte_trie_lookup_bulk_4b;
      38                 :          1 :         case RTE_FIB6_TRIE_8B:
      39                 :          1 :                 return rte_trie_lookup_bulk_8b;
      40                 :          0 :         default:
      41                 :          0 :                 return NULL;
      42                 :            :         }
      43                 :            : }
      44                 :            : 
      45                 :            : static inline rte_fib6_lookup_fn_t
      46                 :          3 : get_vector_fn(enum rte_fib_trie_nh_sz nh_sz)
      47                 :            : {
      48                 :            : #ifdef CC_TRIE_AVX512_SUPPORT
      49   [ +  -  +  - ]:          6 :         if ((rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) <= 0) ||
      50                 :          3 :                         (rte_vect_get_max_simd_bitwidth() < RTE_VECT_SIMD_512))
      51                 :          3 :                 return NULL;
      52   [ #  #  #  # ]:          0 :         switch (nh_sz) {
      53                 :            :         case RTE_FIB6_TRIE_2B:
      54                 :            :                 return rte_trie_vec_lookup_bulk_2b;
      55                 :          0 :         case RTE_FIB6_TRIE_4B:
      56                 :          0 :                 return rte_trie_vec_lookup_bulk_4b;
      57                 :          0 :         case RTE_FIB6_TRIE_8B:
      58                 :          0 :                 return rte_trie_vec_lookup_bulk_8b;
      59                 :          0 :         default:
      60                 :          0 :                 return NULL;
      61                 :            :         }
      62                 :            : #else
      63                 :            :         RTE_SET_USED(nh_sz);
      64                 :            : #endif
      65                 :            :         return NULL;
      66                 :            : }
      67                 :            : 
      68                 :            : rte_fib6_lookup_fn_t
      69                 :          3 : trie_get_lookup_fn(void *p, enum rte_fib6_lookup_type type)
      70                 :            : {
      71                 :            :         enum rte_fib_trie_nh_sz nh_sz;
      72                 :            :         rte_fib6_lookup_fn_t ret_fn;
      73                 :            :         struct rte_trie_tbl *dp = p;
      74                 :            : 
      75         [ +  - ]:          3 :         if (dp == NULL)
      76                 :            :                 return NULL;
      77                 :            : 
      78                 :          3 :         nh_sz = dp->nh_sz;
      79                 :            : 
      80   [ -  -  +  - ]:          3 :         switch (type) {
      81                 :            :         case RTE_FIB6_LOOKUP_TRIE_SCALAR:
      82                 :            :                 return get_scalar_fn(nh_sz);
      83                 :          0 :         case RTE_FIB6_LOOKUP_TRIE_VECTOR_AVX512:
      84                 :          0 :                 return get_vector_fn(nh_sz);
      85                 :          3 :         case RTE_FIB6_LOOKUP_DEFAULT:
      86                 :          3 :                 ret_fn = get_vector_fn(nh_sz);
      87         [ +  - ]:          3 :                 return (ret_fn != NULL) ? ret_fn : get_scalar_fn(nh_sz);
      88                 :            :         default:
      89                 :            :                 return NULL;
      90                 :            :         }
      91                 :            :         return NULL;
      92                 :            : }
      93                 :            : 
      94                 :            : static void
      95                 :       7287 : write_to_dp(void *ptr, uint64_t val, enum rte_fib_trie_nh_sz size, int n)
      96                 :            : {
      97                 :            :         int i;
      98                 :            :         uint16_t *ptr16 = (uint16_t *)ptr;
      99                 :            :         uint32_t *ptr32 = (uint32_t *)ptr;
     100                 :            :         uint64_t *ptr64 = (uint64_t *)ptr;
     101                 :            : 
     102   [ +  +  +  - ]:       7287 :         switch (size) {
     103                 :            :         case RTE_FIB6_TRIE_2B:
     104         [ +  + ]:   67250281 :                 for (i = 0; i < n; i++)
     105                 :   67247852 :                         ptr16[i] = (uint16_t)val;
     106                 :            :                 break;
     107                 :            :         case RTE_FIB6_TRIE_4B:
     108         [ +  + ]:   67250281 :                 for (i = 0; i < n; i++)
     109                 :   67247852 :                         ptr32[i] = (uint32_t)val;
     110                 :            :                 break;
     111                 :            :         case RTE_FIB6_TRIE_8B:
     112         [ +  + ]:   67250281 :                 for (i = 0; i < n; i++)
     113                 :   67247852 :                         ptr64[i] = (uint64_t)val;
     114                 :            :                 break;
     115                 :            :         }
     116                 :       7287 : }
     117                 :            : 
     118                 :            : static void
     119                 :            : tbl8_pool_init(struct rte_trie_tbl *dp)
     120                 :            : {
     121                 :            :         uint32_t i;
     122                 :            : 
     123                 :            :         /* put entire range of indexes to the tbl8 pool */
     124         [ +  + ]:      98306 :         for (i = 0; i < dp->number_tbl8s; i++)
     125                 :      98303 :                 dp->tbl8_pool[i] = i;
     126                 :            : 
     127                 :          3 :         dp->tbl8_pool_pos = 0;
     128                 :            : }
     129                 :            : 
     130                 :            : /*
     131                 :            :  * Get an index of a free tbl8 from the pool
     132                 :            :  */
     133                 :            : static inline int32_t
     134                 :            : tbl8_get(struct rte_trie_tbl *dp)
     135                 :            : {
     136                 :        774 :         if (dp->tbl8_pool_pos == dp->number_tbl8s)
     137                 :            :                 /* no more free tbl8 */
     138                 :            :                 return -ENOSPC;
     139                 :            : 
     140                 :            :         /* next index */
     141                 :        774 :         return dp->tbl8_pool[dp->tbl8_pool_pos++];
     142                 :            : }
     143                 :            : 
     144                 :            : /*
     145                 :            :  * Put an index of a free tbl8 back to the pool
     146                 :            :  */
     147                 :            : static inline void
     148                 :            : tbl8_put(struct rte_trie_tbl *dp, uint32_t tbl8_ind)
     149                 :            : {
     150                 :        774 :         dp->tbl8_pool[--dp->tbl8_pool_pos] = tbl8_ind;
     151                 :        774 : }
     152                 :            : 
     153                 :            : static int
     154         [ +  - ]:        774 : tbl8_alloc(struct rte_trie_tbl *dp, uint64_t nh)
     155                 :            : {
     156                 :            :         int64_t         tbl8_idx;
     157                 :            :         uint8_t         *tbl8_ptr;
     158                 :            : 
     159                 :        774 :         tbl8_idx = tbl8_get(dp);
     160         [ +  - ]:        774 :         if (tbl8_idx < 0)
     161                 :            :                 return tbl8_idx;
     162                 :        774 :         tbl8_ptr = get_tbl_p_by_idx(dp->tbl8,
     163                 :        774 :                 tbl8_idx * TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz);
     164                 :            :         /*Init tbl8 entries with nexthop from tbl24*/
     165                 :        774 :         write_to_dp((void *)tbl8_ptr, nh, dp->nh_sz,
     166                 :            :                 TRIE_TBL8_GRP_NUM_ENT);
     167                 :        774 :         return tbl8_idx;
     168                 :            : }
     169                 :            : 
     170                 :            : static void
     171                 :       9510 : tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t tbl8_idx)
     172                 :            : {
     173                 :            :         uint32_t i;
     174                 :            :         uint64_t nh;
     175                 :            :         uint16_t *ptr16;
     176                 :            :         uint32_t *ptr32;
     177                 :            :         uint64_t *ptr64;
     178                 :            : 
     179   [ +  +  +  - ]:       9510 :         switch (dp->nh_sz) {
     180                 :       3170 :         case RTE_FIB6_TRIE_2B:
     181                 :       3170 :                 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
     182                 :            :                                 TRIE_TBL8_GRP_NUM_ENT];
     183                 :       3170 :                 nh = *ptr16;
     184         [ +  + ]:       3170 :                 if (nh & TRIE_EXT_ENT)
     185                 :            :                         return;
     186         [ +  + ]:      72694 :                 for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
     187         [ +  + ]:      72436 :                         if (nh != ptr16[i])
     188                 :            :                                 return;
     189                 :            :                 }
     190                 :        258 :                 write_to_dp(par, nh, dp->nh_sz, 1);
     191         [ +  + ]:      66306 :                 for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
     192                 :      66048 :                         ptr16[i] = 0;
     193                 :            :                 break;
     194                 :       3170 :         case RTE_FIB6_TRIE_4B:
     195                 :       3170 :                 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
     196                 :            :                                 TRIE_TBL8_GRP_NUM_ENT];
     197                 :       3170 :                 nh = *ptr32;
     198         [ +  + ]:       3170 :                 if (nh & TRIE_EXT_ENT)
     199                 :            :                         return;
     200         [ +  + ]:      72694 :                 for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
     201         [ +  + ]:      72436 :                         if (nh != ptr32[i])
     202                 :            :                                 return;
     203                 :            :                 }
     204                 :        258 :                 write_to_dp(par, nh, dp->nh_sz, 1);
     205         [ +  + ]:      66306 :                 for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
     206                 :      66048 :                         ptr32[i] = 0;
     207                 :            :                 break;
     208                 :       3170 :         case RTE_FIB6_TRIE_8B:
     209                 :       3170 :                 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
     210                 :            :                                 TRIE_TBL8_GRP_NUM_ENT];
     211                 :       3170 :                 nh = *ptr64;
     212         [ +  + ]:       3170 :                 if (nh & TRIE_EXT_ENT)
     213                 :            :                         return;
     214         [ +  + ]:      72694 :                 for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
     215         [ +  + ]:      72436 :                         if (nh != ptr64[i])
     216                 :            :                                 return;
     217                 :            :                 }
     218                 :        258 :                 write_to_dp(par, nh, dp->nh_sz, 1);
     219         [ +  + ]:      66306 :                 for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
     220                 :      66048 :                         ptr64[i] = 0;
     221                 :            :                 break;
     222                 :            :         }
     223                 :        774 :         tbl8_put(dp, tbl8_idx);
     224                 :            : }
     225                 :            : 
     226                 :            : #define BYTE_SIZE       8
     227                 :            : static inline uint32_t
     228                 :            : get_idx(const uint8_t *ip, uint32_t prev_idx, int bytes, int first_byte)
     229                 :            : {
     230                 :            :         int i;
     231                 :            :         uint32_t idx = 0;
     232                 :            :         uint8_t bitshift;
     233                 :            : 
     234   [ +  +  +  +  :      27696 :         for (i = first_byte; i < (first_byte + bytes); i++) {
                   +  + ]
     235                 :      15654 :                 bitshift = (int8_t)(((first_byte + bytes - 1) - i)*BYTE_SIZE);
     236                 :      15654 :                 idx |= ip[i] <<  bitshift;
     237                 :            :         }
     238                 :       8970 :         return (prev_idx * TRIE_TBL8_GRP_NUM_ENT) + idx;
     239                 :            : }
     240                 :            : 
     241                 :            : static inline uint64_t
     242                 :            : get_val_by_p(void *p, uint8_t nh_sz)
     243                 :            : {
     244                 :            :         uint64_t val = 0;
     245                 :            : 
     246                 :      11046 :         switch (nh_sz) {
     247                 :       3682 :         case RTE_FIB6_TRIE_2B:
     248                 :       3682 :                 val = *(uint16_t *)p;
     249                 :       3682 :                 break;
     250                 :       3682 :         case RTE_FIB6_TRIE_4B:
     251                 :       3682 :                 val = *(uint32_t *)p;
     252                 :       3682 :                 break;
     253                 :       3682 :         case RTE_FIB6_TRIE_8B:
     254                 :       3682 :                 val = *(uint64_t *)p;
     255                 :       3682 :                 break;
     256                 :            :         }
     257                 :            :         return val;
     258                 :            : }
     259                 :            : 
     260                 :            : /*
     261                 :            :  * recursively recycle tbl8's
     262                 :            :  */
     263                 :            : static void
     264                 :      10506 : recycle_root_path(struct rte_trie_tbl *dp, const uint8_t *ip_part,
     265                 :            :         uint8_t common_tbl8, void *prev)
     266                 :            : {
     267                 :            :         void *p;
     268                 :            :         uint64_t val;
     269                 :            : 
     270   [ +  +  +  - ]:      10506 :         val = get_val_by_p(prev, dp->nh_sz);
     271         [ +  + ]:      10506 :         if (unlikely((val & TRIE_EXT_ENT) != TRIE_EXT_ENT))
     272                 :            :                 return;
     273                 :            : 
     274         [ +  - ]:       8970 :         if (common_tbl8 != 0) {
     275                 :       8970 :                 p = get_tbl_p_by_idx(dp->tbl8, (val >> 1) *
     276                 :       8970 :                         TRIE_TBL8_GRP_NUM_ENT + *ip_part, dp->nh_sz);
     277                 :       8970 :                 recycle_root_path(dp, ip_part + 1, common_tbl8 - 1, p);
     278                 :            :         }
     279                 :       8970 :         tbl8_recycle(dp, prev, val >> 1);
     280                 :            : }
     281                 :            : 
     282                 :            : static inline int
     283                 :       1536 : build_common_root(struct rte_trie_tbl *dp, const uint8_t *ip,
     284                 :            :         int common_bytes, void **tbl)
     285                 :            : {
     286                 :            :         void *tbl_ptr = NULL;
     287                 :            :         uint64_t *cur_tbl;
     288                 :            :         uint64_t val;
     289                 :            :         int i, j, idx, prev_idx = 0;
     290                 :            : 
     291                 :       1536 :         cur_tbl = dp->tbl24;
     292         [ +  + ]:      10506 :         for (i = 3, j = 0; i <= common_bytes; i++) {
     293                 :       8970 :                 idx = get_idx(ip, prev_idx, i - j, j);
     294         [ +  + ]:       8970 :                 val = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz);
     295         [ +  + ]:       8970 :                 tbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz);
     296         [ +  + ]:       8970 :                 if ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) {
     297                 :        234 :                         idx = tbl8_alloc(dp, val);
     298         [ -  + ]:        234 :                         if (unlikely(idx < 0))
     299                 :          0 :                                 return idx;
     300                 :        234 :                         write_to_dp(tbl_ptr, (idx << 1) |
     301                 :            :                                 TRIE_EXT_ENT, dp->nh_sz, 1);
     302                 :            :                         prev_idx = idx;
     303                 :            :                 } else
     304                 :       8736 :                         prev_idx = val >> 1;
     305                 :            : 
     306                 :            :                 j = i;
     307                 :       8970 :                 cur_tbl = dp->tbl8;
     308                 :            :         }
     309                 :       1536 :         *tbl = get_tbl_p_by_idx(cur_tbl, prev_idx * TRIE_TBL8_GRP_NUM_ENT,
     310                 :       1536 :                 dp->nh_sz);
     311                 :       1536 :         return 0;
     312                 :            : }
     313                 :            : 
     314                 :            : static int
     315                 :       3612 : write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part, uint64_t next_hop,
     316                 :            :         int len, enum edge edge, void *ent)
     317                 :            : {
     318                 :       3612 :         uint64_t val = next_hop << 1;
     319                 :            :         int tbl8_idx;
     320                 :            :         int ret = 0;
     321                 :            :         void *p;
     322                 :            : 
     323         [ +  + ]:       3612 :         if (len != 0) {
     324   [ +  +  +  - ]:        540 :                 val = get_val_by_p(ent, dp->nh_sz);
     325         [ -  + ]:        540 :                 if ((val & TRIE_EXT_ENT) == TRIE_EXT_ENT)
     326                 :          0 :                         tbl8_idx = val >> 1;
     327                 :            :                 else {
     328                 :        540 :                         tbl8_idx = tbl8_alloc(dp, val);
     329         [ +  - ]:        540 :                         if (tbl8_idx < 0)
     330                 :            :                                 return tbl8_idx;
     331                 :        540 :                         val = (tbl8_idx << 1)|TRIE_EXT_ENT;
     332                 :            :                 }
     333                 :        540 :                 p = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx *
     334                 :        540 :                         TRIE_TBL8_GRP_NUM_ENT) + *ip_part, dp->nh_sz);
     335                 :        540 :                 ret = write_edge(dp, ip_part + 1, next_hop, len - 1, edge, p);
     336         [ +  - ]:        540 :                 if (ret < 0)
     337                 :            :                         return ret;
     338         [ +  + ]:        540 :                 if (edge == LEDGE) {
     339                 :        270 :                         write_to_dp((uint8_t *)p + (1 << dp->nh_sz),
     340                 :        270 :                                 next_hop << 1, dp->nh_sz, UINT8_MAX - *ip_part);
     341                 :            :                 } else {
     342                 :        270 :                         write_to_dp(get_tbl_p_by_idx(dp->tbl8, tbl8_idx *
     343                 :            :                                 TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz),
     344                 :        270 :                                 next_hop << 1, dp->nh_sz, *ip_part);
     345                 :            :                 }
     346                 :        540 :                 tbl8_recycle(dp, &val, tbl8_idx);
     347                 :            :         }
     348                 :            : 
     349                 :       3612 :         write_to_dp(ent, val, dp->nh_sz, 1);
     350                 :       3612 :         return ret;
     351                 :            : }
     352                 :            : 
     353                 :            : #define IPV6_MAX_IDX    (RTE_FIB6_IPV6_ADDR_SIZE - 1)
     354                 :            : #define TBL24_BYTES     3
     355                 :            : #define TBL8_LEN        (RTE_FIB6_IPV6_ADDR_SIZE - TBL24_BYTES)
     356                 :            : 
     357                 :            : static int
     358         [ +  - ]:       1536 : install_to_dp(struct rte_trie_tbl *dp, const uint8_t *ledge, const uint8_t *r,
     359                 :            :         uint64_t next_hop)
     360                 :            : {
     361                 :            :         void *common_root_tbl;
     362                 :            :         void *ent;
     363                 :            :         int ret;
     364                 :            :         int i;
     365                 :            :         int common_bytes;
     366                 :            :         int llen, rlen;
     367                 :            :         uint8_t redge[16];
     368                 :            : 
     369                 :            :         /* decrement redge by 1*/
     370                 :            :         rte_rib6_copy_addr(redge, r);
     371         [ +  + ]:      13068 :         for (i = 15; i >= 0; i--) {
     372                 :      13056 :                 redge[i]--;
     373         [ +  + ]:      13056 :                 if (redge[i] != 0xff)
     374                 :            :                         break;
     375                 :            :         }
     376                 :            : 
     377         [ +  + ]:      13326 :         for (common_bytes = 0; common_bytes < 15; common_bytes++) {
     378         [ +  + ]:      13212 :                 if (ledge[common_bytes] != redge[common_bytes])
     379                 :            :                         break;
     380                 :            :         }
     381                 :            : 
     382                 :       1536 :         ret = build_common_root(dp, ledge, common_bytes, &common_root_tbl);
     383         [ +  - ]:       1536 :         if (unlikely(ret != 0))
     384                 :            :                 return ret;
     385                 :            :         /*first uncommon tbl8 byte idx*/
     386                 :       1536 :         uint8_t first_tbl8_byte = RTE_MAX(common_bytes, TBL24_BYTES);
     387                 :            : 
     388         [ +  + ]:      12264 :         for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
     389         [ +  - ]:      10728 :                 if (ledge[i] != 0)
     390                 :            :                         break;
     391                 :            :         }
     392                 :            : 
     393                 :       1536 :         llen = i - first_tbl8_byte + (common_bytes < 3);
     394                 :            : 
     395         [ +  + ]:      12264 :         for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
     396         [ +  - ]:      10728 :                 if (redge[i] != UINT8_MAX)
     397                 :            :                         break;
     398                 :            :         }
     399                 :       1536 :         rlen = i - first_tbl8_byte + (common_bytes < 3);
     400                 :            : 
     401                 :            :         /*first noncommon byte*/
     402         [ +  + ]:       1536 :         uint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes;
     403         [ +  + ]:       1536 :         uint8_t first_idx_len = (common_bytes < 3) ? 3 : 1;
     404                 :            : 
     405                 :       1536 :         uint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);
     406                 :            :         uint32_t right_idx = get_idx(redge, 0, first_idx_len, first_byte_idx);
     407                 :            : 
     408                 :       1536 :         ent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz);
     409                 :       1536 :         ret = write_edge(dp, &ledge[first_tbl8_byte + !(common_bytes < 3)],
     410                 :            :                 next_hop, llen, LEDGE, ent);
     411         [ +  - ]:       1536 :         if (ret < 0)
     412                 :            :                 return ret;
     413                 :            : 
     414         [ +  + ]:       1536 :         if (right_idx > left_idx + 1) {
     415                 :       1350 :                 ent = get_tbl_p_by_idx(common_root_tbl, left_idx + 1,
     416                 :       1350 :                         dp->nh_sz);
     417                 :       1350 :                 write_to_dp(ent, next_hop << 1, dp->nh_sz,
     418                 :       1350 :                         right_idx - (left_idx + 1));
     419                 :            :         }
     420                 :       1536 :         ent = get_tbl_p_by_idx(common_root_tbl, right_idx, dp->nh_sz);
     421                 :       1536 :         ret = write_edge(dp, &redge[first_tbl8_byte + !((common_bytes < 3))],
     422                 :            :                 next_hop, rlen, REDGE, ent);
     423         [ +  - ]:       1536 :         if (ret < 0)
     424                 :            :                 return ret;
     425                 :            : 
     426                 :       1536 :         uint8_t common_tbl8 = (common_bytes < TBL24_BYTES) ?
     427                 :       1536 :                         0 : common_bytes - (TBL24_BYTES - 1);
     428                 :       1536 :         ent = get_tbl24_p(dp, ledge, dp->nh_sz);
     429                 :       1536 :         recycle_root_path(dp, ledge + TBL24_BYTES, common_tbl8, ent);
     430                 :       1536 :         return 0;
     431                 :            : }
     432                 :            : 
     433                 :            : static void
     434                 :       2298 : get_nxt_net(uint8_t *ip, uint8_t depth)
     435                 :            : {
     436                 :            :         int i;
     437                 :            :         uint8_t part_depth;
     438                 :            :         uint8_t prev_byte;
     439                 :            : 
     440         [ +  + ]:      19578 :         for (i = 0, part_depth = depth; part_depth > 8; part_depth -= 8, i++)
     441                 :            :                 ;
     442                 :            : 
     443                 :       2298 :         prev_byte = ip[i];
     444                 :       2298 :         ip[i] += 1 << (8 - part_depth);
     445         [ +  + ]:       2298 :         if (ip[i] < prev_byte) {
     446         [ -  + ]:         12 :                 while (i > 0) {
     447                 :          0 :                         ip[--i] += 1;
     448         [ #  # ]:          0 :                         if (ip[i] != 0)
     449                 :            :                                 break;
     450                 :            :                 }
     451                 :            :         }
     452                 :       2298 : }
     453                 :            : 
     454                 :            : static int
     455                 :            : v6_addr_is_zero(const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE])
     456                 :            : {
     457                 :          0 :         uint8_t ip_addr[RTE_FIB6_IPV6_ADDR_SIZE] = {0};
     458                 :            : 
     459                 :            :         return rte_rib6_is_equal(ip, ip_addr);
     460                 :            : }
     461                 :            : 
     462                 :            : static int
     463                 :       1536 : modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
     464                 :            :         const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
     465                 :            :         uint8_t depth, uint64_t next_hop)
     466                 :            : {
     467                 :            :         struct rte_rib6_node *tmp = NULL;
     468                 :            :         uint8_t ledge[RTE_FIB6_IPV6_ADDR_SIZE];
     469                 :            :         uint8_t redge[RTE_FIB6_IPV6_ADDR_SIZE];
     470                 :            :         int ret;
     471                 :            :         uint8_t tmp_depth;
     472                 :            : 
     473         [ +  - ]:       1536 :         if (next_hop > get_max_nh(dp->nh_sz))
     474                 :            :                 return -EINVAL;
     475                 :            : 
     476                 :            :         rte_rib6_copy_addr(ledge, ip);
     477                 :            :         do {
     478                 :       2298 :                 tmp = rte_rib6_get_nxt(rib, ip, depth, tmp,
     479                 :            :                         RTE_RIB6_GET_NXT_COVER);
     480         [ +  + ]:       2298 :                 if (tmp != NULL) {
     481                 :        762 :                         rte_rib6_get_depth(tmp, &tmp_depth);
     482         [ -  + ]:        762 :                         if (tmp_depth == depth)
     483                 :          0 :                                 continue;
     484                 :        762 :                         rte_rib6_get_ip(tmp, redge);
     485         [ +  - ]:        762 :                         if (rte_rib6_is_equal(ledge, redge)) {
     486                 :        762 :                                 get_nxt_net(ledge, tmp_depth);
     487                 :        762 :                                 continue;
     488                 :            :                         }
     489                 :          0 :                         ret = install_to_dp(dp, ledge, redge,
     490                 :            :                                 next_hop);
     491         [ #  # ]:          0 :                         if (ret != 0)
     492                 :          0 :                                 return ret;
     493                 :          0 :                         get_nxt_net(redge, tmp_depth);
     494                 :            :                         rte_rib6_copy_addr(ledge, redge);
     495                 :            :                         /*
     496                 :            :                          * we got to the end of address space
     497                 :            :                          * and wrapped around
     498                 :            :                          */
     499         [ #  # ]:          0 :                         if (v6_addr_is_zero(ledge))
     500                 :            :                                 break;
     501                 :            :                 } else {
     502                 :            :                         rte_rib6_copy_addr(redge, ip);
     503                 :       1536 :                         get_nxt_net(redge, depth);
     504   [ -  +  -  - ]:       1536 :                         if (rte_rib6_is_equal(ledge, redge) &&
     505                 :            :                                         !v6_addr_is_zero(ledge))
     506                 :            :                                 break;
     507                 :            : 
     508                 :       1536 :                         ret = install_to_dp(dp, ledge, redge,
     509                 :            :                                 next_hop);
     510         [ -  + ]:       1536 :                         if (ret != 0)
     511                 :          0 :                                 return ret;
     512                 :            :                 }
     513         [ +  + ]:       2298 :         } while (tmp);
     514                 :            : 
     515                 :            :         return 0;
     516                 :            : }
     517                 :            : 
     518                 :            : int
     519                 :       1536 : trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
     520                 :            :         uint8_t depth, uint64_t next_hop, int op)
     521                 :            : {
     522                 :            :         struct rte_trie_tbl *dp;
     523                 :            :         struct rte_rib6 *rib;
     524                 :            :         struct rte_rib6_node *tmp = NULL;
     525                 :            :         struct rte_rib6_node *node;
     526                 :            :         struct rte_rib6_node *parent;
     527                 :            :         uint8_t ip_masked[RTE_FIB6_IPV6_ADDR_SIZE];
     528                 :            :         int i, ret = 0;
     529                 :            :         uint64_t par_nh, node_nh;
     530                 :            :         uint8_t tmp_depth, depth_diff = 0, parent_depth = 24;
     531                 :            : 
     532   [ +  -  +  - ]:       1536 :         if ((fib == NULL) || (ip == NULL) || (depth > RTE_FIB6_MAXDEPTH))
     533                 :            :                 return -EINVAL;
     534                 :            : 
     535                 :       1536 :         dp = rte_fib6_get_dp(fib);
     536                 :            :         RTE_ASSERT(dp);
     537                 :       1536 :         rib = rte_fib6_get_rib(fib);
     538                 :            :         RTE_ASSERT(rib);
     539                 :            : 
     540         [ +  + ]:      26112 :         for (i = 0; i < RTE_FIB6_IPV6_ADDR_SIZE; i++)
     541                 :      24576 :                 ip_masked[i] = ip[i] & get_msk_part(depth, i);
     542                 :            : 
     543         [ +  + ]:       1536 :         if (depth > 24) {
     544                 :       1248 :                 tmp = rte_rib6_get_nxt(rib, ip_masked,
     545                 :            :                         RTE_ALIGN_FLOOR(depth, 8), NULL,
     546                 :            :                         RTE_RIB6_GET_NXT_COVER);
     547         [ +  + ]:       1248 :                 if (tmp == NULL) {
     548                 :        123 :                         tmp = rte_rib6_lookup(rib, ip);
     549         [ +  + ]:        123 :                         if (tmp != NULL) {
     550                 :        120 :                                 rte_rib6_get_depth(tmp, &tmp_depth);
     551                 :        120 :                                 parent_depth = RTE_MAX(tmp_depth, 24);
     552                 :            :                         }
     553                 :        123 :                         depth_diff = RTE_ALIGN_CEIL(depth, 8) -
     554                 :        123 :                                 RTE_ALIGN_CEIL(parent_depth, 8);
     555                 :        123 :                         depth_diff = depth_diff >> 3;
     556                 :            :                 }
     557                 :            :         }
     558                 :       1536 :         node = rte_rib6_lookup_exact(rib, ip_masked, depth);
     559      [ +  +  - ]:       1536 :         switch (op) {
     560                 :        768 :         case RTE_FIB6_ADD:
     561         [ -  + ]:        768 :                 if (node != NULL) {
     562                 :          0 :                         rte_rib6_get_nh(node, &node_nh);
     563         [ #  # ]:          0 :                         if (node_nh == next_hop)
     564                 :            :                                 return 0;
     565                 :          0 :                         ret = modify_dp(dp, rib, ip_masked, depth, next_hop);
     566         [ #  # ]:          0 :                         if (ret == 0)
     567                 :          0 :                                 rte_rib6_set_nh(node, next_hop);
     568                 :          0 :                         return 0;
     569                 :            :                 }
     570                 :            : 
     571         [ +  + ]:        768 :                 if ((depth > 24) && (dp->rsvd_tbl8s >=
     572         [ +  - ]:        624 :                                 dp->number_tbl8s - depth_diff))
     573                 :            :                         return -ENOSPC;
     574                 :            : 
     575                 :        768 :                 node = rte_rib6_insert(rib, ip_masked, depth);
     576         [ -  + ]:        768 :                 if (node == NULL)
     577                 :          0 :                         return -rte_errno;
     578                 :        768 :                 rte_rib6_set_nh(node, next_hop);
     579                 :        768 :                 parent = rte_rib6_lookup_parent(node);
     580         [ +  + ]:        768 :                 if (parent != NULL) {
     581                 :        381 :                         rte_rib6_get_nh(parent, &par_nh);
     582         [ +  - ]:        381 :                         if (par_nh == next_hop)
     583                 :            :                                 return 0;
     584                 :            :                 }
     585                 :        768 :                 ret = modify_dp(dp, rib, ip_masked, depth, next_hop);
     586         [ -  + ]:        768 :                 if (ret != 0) {
     587                 :          0 :                         rte_rib6_remove(rib, ip_masked, depth);
     588                 :          0 :                         return ret;
     589                 :            :                 }
     590                 :            : 
     591                 :        768 :                 dp->rsvd_tbl8s += depth_diff;
     592                 :        768 :                 return 0;
     593                 :        768 :         case RTE_FIB6_DEL:
     594         [ +  - ]:        768 :                 if (node == NULL)
     595                 :            :                         return -ENOENT;
     596                 :            : 
     597                 :        768 :                 parent = rte_rib6_lookup_parent(node);
     598         [ +  + ]:        768 :                 if (parent != NULL) {
     599                 :        381 :                         rte_rib6_get_nh(parent, &par_nh);
     600                 :        381 :                         rte_rib6_get_nh(node, &node_nh);
     601         [ +  - ]:        381 :                         if (par_nh != node_nh)
     602                 :        381 :                                 ret = modify_dp(dp, rib, ip_masked, depth,
     603                 :            :                                         par_nh);
     604                 :            :                 } else
     605                 :        387 :                         ret = modify_dp(dp, rib, ip_masked, depth, dp->def_nh);
     606                 :            : 
     607         [ +  - ]:        768 :                 if (ret != 0)
     608                 :            :                         return ret;
     609                 :        768 :                 rte_rib6_remove(rib, ip, depth);
     610                 :            : 
     611                 :        768 :                 dp->rsvd_tbl8s -= depth_diff;
     612                 :        768 :                 return 0;
     613                 :            :         default:
     614                 :            :                 break;
     615                 :            :         }
     616                 :            :         return -EINVAL;
     617                 :            : }
     618                 :            : 
     619                 :            : void *
     620                 :          5 : trie_create(const char *name, int socket_id,
     621                 :            :         struct rte_fib6_conf *conf)
     622                 :            : {
     623                 :            :         char mem_name[TRIE_NAMESIZE];
     624                 :            :         struct rte_trie_tbl *dp = NULL;
     625                 :            :         uint64_t        def_nh;
     626                 :            :         uint32_t        num_tbl8;
     627                 :            :         enum rte_fib_trie_nh_sz nh_sz;
     628                 :            : 
     629         [ +  - ]:          5 :         if ((name == NULL) || (conf == NULL) ||
     630   [ +  -  +  + ]:          5 :                         (conf->trie.nh_sz < RTE_FIB6_TRIE_2B) ||
     631         [ +  - ]:          4 :                         (conf->trie.nh_sz > RTE_FIB6_TRIE_8B) ||
     632                 :          4 :                         (conf->trie.num_tbl8 >
     633   [ +  -  +  + ]:          4 :                         get_max_nh(conf->trie.nh_sz)) ||
     634                 :          3 :                         (conf->trie.num_tbl8 == 0) ||
     635         [ -  + ]:          3 :                         (conf->default_nh >
     636                 :            :                         get_max_nh(conf->trie.nh_sz))) {
     637                 :            : 
     638                 :          2 :                 rte_errno = EINVAL;
     639                 :          2 :                 return NULL;
     640                 :            :         }
     641                 :            : 
     642                 :            :         def_nh = conf->default_nh;
     643                 :            :         nh_sz = conf->trie.nh_sz;
     644                 :            :         num_tbl8 = conf->trie.num_tbl8;
     645                 :            : 
     646                 :            :         snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
     647                 :          3 :         dp = rte_zmalloc_socket(name, sizeof(struct rte_trie_tbl) +
     648                 :          3 :                 TRIE_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
     649                 :            :                 socket_id);
     650         [ -  + ]:          3 :         if (dp == NULL) {
     651                 :          0 :                 rte_errno = ENOMEM;
     652                 :          0 :                 return dp;
     653                 :            :         }
     654                 :            : 
     655                 :          3 :         write_to_dp(&dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
     656                 :            : 
     657                 :            :         snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
     658                 :          6 :         dp->tbl8 = rte_zmalloc_socket(mem_name, TRIE_TBL8_GRP_NUM_ENT *
     659                 :          3 :                         (1ll << nh_sz) * (num_tbl8 + 1),
     660                 :            :                         RTE_CACHE_LINE_SIZE, socket_id);
     661         [ -  + ]:          3 :         if (dp->tbl8 == NULL) {
     662                 :          0 :                 rte_errno = ENOMEM;
     663                 :          0 :                 rte_free(dp);
     664                 :          0 :                 return NULL;
     665                 :            :         }
     666                 :          3 :         dp->def_nh = def_nh;
     667                 :          3 :         dp->nh_sz = nh_sz;
     668                 :          3 :         dp->number_tbl8s = num_tbl8;
     669                 :            : 
     670                 :            :         snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
     671                 :          6 :         dp->tbl8_pool = rte_zmalloc_socket(mem_name,
     672                 :          3 :                         sizeof(uint32_t) * dp->number_tbl8s,
     673                 :            :                         RTE_CACHE_LINE_SIZE, socket_id);
     674         [ -  + ]:          3 :         if (dp->tbl8_pool == NULL) {
     675                 :          0 :                 rte_errno = ENOMEM;
     676                 :          0 :                 rte_free(dp->tbl8);
     677                 :          0 :                 rte_free(dp);
     678                 :          0 :                 return NULL;
     679                 :            :         }
     680                 :            : 
     681                 :            :         tbl8_pool_init(dp);
     682                 :            : 
     683                 :          3 :         return dp;
     684                 :            : }
     685                 :            : 
     686                 :            : void
     687                 :          3 : trie_free(void *p)
     688                 :            : {
     689                 :            :         struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;
     690                 :            : 
     691                 :          3 :         rte_free(dp->tbl8_pool);
     692                 :          3 :         rte_free(dp->tbl8);
     693                 :          3 :         rte_free(dp);
     694                 :          3 : }

Generated by: LCOV version 1.14