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_ */ 252