LCOV - code coverage report
Current view: top level - lib/fib - dir24_8.h (source / functions) Hit Total Coverage
Test: Code coverage Lines: 15 66 22.7 %
Date: 2024-04-01 19:00:53 Functions: 4 11 36.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 41 70 58.6 %

           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                 :            : #ifndef _DIR24_8_H_
       7                 :            : #define _DIR24_8_H_
       8                 :            : 
       9                 :            : #include <stdalign.h>
      10                 :            : 
      11                 :            : #include <rte_prefetch.h>
      12                 :            : #include <rte_branch_prediction.h>
      13                 :            : 
      14                 :            : /**
      15                 :            :  * @file
      16                 :            :  * DIR24_8 algorithm
      17                 :            :  */
      18                 :            : 
      19                 :            : #define DIR24_8_TBL24_NUM_ENT           (1 << 24)
      20                 :            : #define DIR24_8_TBL8_GRP_NUM_ENT        256U
      21                 :            : #define DIR24_8_EXT_ENT                 1
      22                 :            : #define DIR24_8_TBL24_MASK              0xffffff00
      23                 :            : 
      24                 :            : #define BITMAP_SLAB_BIT_SIZE_LOG2       6
      25                 :            : #define BITMAP_SLAB_BIT_SIZE            (1 << BITMAP_SLAB_BIT_SIZE_LOG2)
      26                 :            : #define BITMAP_SLAB_BITMASK             (BITMAP_SLAB_BIT_SIZE - 1)
      27                 :            : 
      28                 :            : struct dir24_8_tbl {
      29                 :            :         uint32_t        number_tbl8s;   /**< Total number of tbl8s */
      30                 :            :         uint32_t        rsvd_tbl8s;     /**< Number of reserved tbl8s */
      31                 :            :         uint32_t        cur_tbl8s;      /**< Current number of tbl8s */
      32                 :            :         enum rte_fib_dir24_8_nh_sz      nh_sz;  /**< Size of nexthop entry */
      33                 :            :         uint64_t        def_nh;         /**< Default next hop */
      34                 :            :         uint64_t        *tbl8;          /**< tbl8 table. */
      35                 :            :         uint64_t        *tbl8_idxes;    /**< bitmap containing free tbl8 idxes*/
      36                 :            :         /* tbl24 table. */
      37                 :            :         __extension__ alignas(RTE_CACHE_LINE_SIZE) uint64_t     tbl24[0];
      38                 :            : };
      39                 :            : 
      40                 :            : static inline void *
      41                 :            : get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
      42                 :            : {
      43                 :      17420 :         return (void *)&((uint8_t *)dp->tbl24)[(ip &
      44                 :        392 :                 DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
      45                 :            : }
      46                 :            : 
      47                 :            : static inline  uint8_t
      48                 :            : bits_in_nh(uint8_t nh_sz)
      49                 :            : {
      50                 :        653 :         return 8 * (1 << nh_sz);
      51                 :            : }
      52                 :            : 
      53                 :            : static inline uint64_t
      54                 :            : get_max_nh(uint8_t nh_sz)
      55                 :            : {
      56   [ +  -  +  - ]:        517 :         return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
      57                 :            : }
      58                 :            : 
      59                 :            : static  inline uint32_t
      60                 :            : get_tbl24_idx(uint32_t ip)
      61                 :            : {
      62                 :          0 :         return ip >> 8;
      63                 :            : }
      64                 :            : 
      65                 :            : static  inline uint32_t
      66                 :            : get_tbl8_idx(uint32_t res, uint32_t ip)
      67                 :            : {
      68                 :          0 :         return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
      69                 :            : }
      70                 :            : 
      71                 :            : static inline uint64_t
      72                 :            : lookup_msk(uint8_t nh_sz)
      73                 :            : {
      74                 :        136 :         return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
      75                 :            : }
      76                 :            : 
      77                 :            : static inline uint8_t
      78                 :            : get_psd_idx(uint32_t val, uint8_t nh_sz)
      79                 :            : {
      80                 :        136 :         return val & ((1 << (3 - nh_sz)) - 1);
      81                 :            : }
      82                 :            : 
      83                 :            : static inline uint32_t
      84                 :            : get_tbl_idx(uint32_t val, uint8_t nh_sz)
      85                 :            : {
      86                 :        136 :         return val >> (3 - nh_sz);
      87                 :            : }
      88                 :            : 
      89                 :            : static inline uint64_t
      90                 :            : get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
      91                 :            : {
      92                 :        136 :         return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >>
      93                 :        136 :                 (get_psd_idx(get_tbl24_idx(ip), nh_sz) *
      94   [ -  +  -  -  :        136 :                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
                   +  + ]
      95                 :            : }
      96                 :            : 
      97                 :            : static inline uint64_t
      98                 :          0 : get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz)
      99                 :            : {
     100                 :          0 :         return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >>
     101                 :          0 :                 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) *
     102                 :          0 :                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
     103                 :            : }
     104                 :            : 
     105                 :            : static inline int
     106                 :            : is_entry_extended(uint64_t ent)
     107                 :            : {
     108                 :       8514 :         return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT;
     109                 :            : }
     110                 :            : 
     111                 :            : #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz)                 \
     112                 :            : static inline void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \
     113                 :            :         uint64_t *next_hops, const unsigned int n)                      \
     114                 :            : {                                                                       \
     115                 :            :         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;               \
     116                 :            :         uint64_t tmp;                                                   \
     117                 :            :         uint32_t i;                                                     \
     118                 :            :         uint32_t prefetch_offset =                                      \
     119                 :            :                 RTE_MIN((unsigned int)bulk_prefetch, n);                \
     120                 :            :                                                                         \
     121                 :            :         for (i = 0; i < prefetch_offset; i++)                                \
     122                 :            :                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));          \
     123                 :            :         for (i = 0; i < (n - prefetch_offset); i++) {                        \
     124                 :            :                 rte_prefetch0(get_tbl24_p(dp,                           \
     125                 :            :                         ips[i + prefetch_offset], nh_sz));              \
     126                 :            :                 tmp = ((type *)dp->tbl24)[ips[i] >> 8];                        \
     127                 :            :                 if (unlikely(is_entry_extended(tmp)))                   \
     128                 :            :                         tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] +   \
     129                 :            :                                 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
     130                 :            :                 next_hops[i] = tmp >> 1;                          \
     131                 :            :         }                                                               \
     132                 :            :         for (; i < n; i++) {                                         \
     133                 :            :                 tmp = ((type *)dp->tbl24)[ips[i] >> 8];                        \
     134                 :            :                 if (unlikely(is_entry_extended(tmp)))                   \
     135                 :            :                         tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] +   \
     136                 :            :                                 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
     137                 :            :                 next_hops[i] = tmp >> 1;                          \
     138                 :            :         }                                                               \
     139                 :            : }                                                                       \
     140                 :            : 
     141   [ +  +  +  +  :       5289 : LOOKUP_FUNC(1b, uint8_t, 5, 0)
          +  +  -  +  +  
                      + ]
     142   [ +  +  +  +  :       5418 : LOOKUP_FUNC(2b, uint16_t, 6, 1)
          +  +  -  +  +  
                      + ]
     143   [ +  +  +  +  :       6579 : LOOKUP_FUNC(4b, uint32_t, 15, 2)
          +  +  -  +  +  
                      + ]
     144   [ +  +  +  +  :       6192 : LOOKUP_FUNC(8b, uint64_t, 12, 3)
          +  +  -  +  +  
                      + ]
     145                 :            : 
     146                 :            : static inline void
     147                 :          0 : dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips,
     148                 :            :         uint64_t *next_hops, const unsigned int n, uint8_t nh_sz)
     149                 :            : {
     150                 :            :         uint64_t tmp;
     151                 :            :         uint32_t i;
     152                 :          0 :         uint32_t prefetch_offset = RTE_MIN(15U, n);
     153                 :            : 
     154         [ #  # ]:          0 :         for (i = 0; i < prefetch_offset; i++)
     155                 :          0 :                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
     156         [ #  # ]:          0 :         for (i = 0; i < (n - prefetch_offset); i++) {
     157                 :          0 :                 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
     158                 :            :                         nh_sz));
     159                 :          0 :                 tmp = get_tbl24(dp, ips[i], nh_sz);
     160         [ #  # ]:          0 :                 if (unlikely(is_entry_extended(tmp)))
     161                 :          0 :                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
     162                 :            : 
     163                 :          0 :                 next_hops[i] = tmp >> 1;
     164                 :            :         }
     165         [ #  # ]:          0 :         for (; i < n; i++) {
     166                 :          0 :                 tmp = get_tbl24(dp, ips[i], nh_sz);
     167         [ #  # ]:          0 :                 if (unlikely(is_entry_extended(tmp)))
     168                 :          0 :                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
     169                 :            : 
     170                 :          0 :                 next_hops[i] = tmp >> 1;
     171                 :            :         }
     172                 :          0 : }
     173                 :            : 
     174                 :            : static inline void
     175                 :          0 : dir24_8_lookup_bulk_0(void *p, const uint32_t *ips,
     176                 :            :         uint64_t *next_hops, const unsigned int n)
     177                 :            : {
     178                 :            :         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
     179                 :            : 
     180                 :          0 :         dir24_8_lookup_bulk(dp, ips, next_hops, n, 0);
     181                 :          0 : }
     182                 :            : 
     183                 :            : static inline void
     184                 :          0 : dir24_8_lookup_bulk_1(void *p, const uint32_t *ips,
     185                 :            :         uint64_t *next_hops, const unsigned int n)
     186                 :            : {
     187                 :            :         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
     188                 :            : 
     189                 :          0 :         dir24_8_lookup_bulk(dp, ips, next_hops, n, 1);
     190                 :          0 : }
     191                 :            : 
     192                 :            : static inline void
     193                 :          0 : dir24_8_lookup_bulk_2(void *p, const uint32_t *ips,
     194                 :            :         uint64_t *next_hops, const unsigned int n)
     195                 :            : {
     196                 :            :         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
     197                 :            : 
     198                 :          0 :         dir24_8_lookup_bulk(dp, ips, next_hops, n, 2);
     199                 :          0 : }
     200                 :            : 
     201                 :            : static inline void
     202                 :          0 : dir24_8_lookup_bulk_3(void *p, const uint32_t *ips,
     203                 :            :         uint64_t *next_hops, const unsigned int n)
     204                 :            : {
     205                 :            :         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
     206                 :            : 
     207                 :          0 :         dir24_8_lookup_bulk(dp, ips, next_hops, n, 3);
     208                 :          0 : }
     209                 :            : 
     210                 :            : static inline void
     211                 :          0 : dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips,
     212                 :            :         uint64_t *next_hops, const unsigned int n)
     213                 :            : {
     214                 :            :         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
     215                 :            :         uint64_t tmp;
     216                 :            :         uint32_t i;
     217                 :          0 :         uint32_t prefetch_offset = RTE_MIN(15U, n);
     218                 :          0 :         uint8_t nh_sz = dp->nh_sz;
     219                 :            : 
     220         [ #  # ]:          0 :         for (i = 0; i < prefetch_offset; i++)
     221                 :          0 :                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
     222         [ #  # ]:          0 :         for (i = 0; i < (n - prefetch_offset); i++) {
     223                 :          0 :                 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
     224                 :            :                         nh_sz));
     225                 :          0 :                 tmp = get_tbl24(dp, ips[i], nh_sz);
     226         [ #  # ]:          0 :                 if (unlikely(is_entry_extended(tmp)))
     227                 :          0 :                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
     228                 :            : 
     229                 :          0 :                 next_hops[i] = tmp >> 1;
     230                 :            :         }
     231         [ #  # ]:          0 :         for (; i < n; i++) {
     232                 :          0 :                 tmp = get_tbl24(dp, ips[i], nh_sz);
     233         [ #  # ]:          0 :                 if (unlikely(is_entry_extended(tmp)))
     234                 :          0 :                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
     235                 :            : 
     236                 :          0 :                 next_hops[i] = tmp >> 1;
     237                 :            :         }
     238                 :          0 : }
     239                 :            : 
     240                 :            : void *
     241                 :            : dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf);
     242                 :            : 
     243                 :            : void
     244                 :            : dir24_8_free(void *p);
     245                 :            : 
     246                 :            : rte_fib_lookup_fn_t
     247                 :            : dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type);
     248                 :            : 
     249                 :            : int
     250                 :            : dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
     251                 :            :         uint64_t next_hop, int op);
     252                 :            : 
     253                 :            : #endif /* _DIR24_8_H_ */

Generated by: LCOV version 1.14