lib/fib/dir24_8.h

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