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