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 alignas(RTE_CACHE_LINE_SIZE) uint64_t tbl24[]; 38 }; 39 40 static inline void * 41 get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) 42 { 43 return (void *)&((uint8_t *)dp->tbl24)[(ip & 44 DIR24_8_TBL24_MASK) >> (8 - nh_sz)]; 45 } 46 47 static inline uint8_t 48 bits_in_nh(uint8_t nh_sz) 49 { 50 return 8 * (1 << nh_sz); 51 } 52 53 static inline uint64_t 54 get_max_nh(uint8_t nh_sz) 55 { 56 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 return ip >> 8; 63 } 64 65 static inline uint32_t 66 get_tbl8_idx(uint32_t res, uint32_t ip) 67 { 68 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 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 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 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 return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >> 93 (get_psd_idx(get_tbl24_idx(ip), nh_sz) * 94 bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 95 } 96 97 static inline uint64_t 98 get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz) 99 { 100 return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >> 101 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) * 102 bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 103 } 104 105 static inline int 106 is_entry_extended(uint64_t ent) 107 { 108 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 LOOKUP_FUNC(1b, uint8_t, 5, 0) 142 LOOKUP_FUNC(2b, uint16_t, 6, 1) 143 LOOKUP_FUNC(4b, uint32_t, 15, 2) 144 LOOKUP_FUNC(8b, uint64_t, 12, 3) 145 146 static inline void 147 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 uint32_t prefetch_offset = RTE_MIN(15U, n); 153 154 for (i = 0; i < prefetch_offset; i++) 155 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); 156 for (i = 0; i < (n - prefetch_offset); i++) { 157 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], 158 nh_sz)); 159 tmp = get_tbl24(dp, ips[i], nh_sz); 160 if (unlikely(is_entry_extended(tmp))) 161 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 162 163 next_hops[i] = tmp >> 1; 164 } 165 for (; i < n; i++) { 166 tmp = get_tbl24(dp, ips[i], nh_sz); 167 if (unlikely(is_entry_extended(tmp))) 168 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 169 170 next_hops[i] = tmp >> 1; 171 } 172 } 173 174 static inline void 175 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 dir24_8_lookup_bulk(dp, ips, next_hops, n, 0); 181 } 182 183 static inline void 184 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 dir24_8_lookup_bulk(dp, ips, next_hops, n, 1); 190 } 191 192 static inline void 193 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 dir24_8_lookup_bulk(dp, ips, next_hops, n, 2); 199 } 200 201 static inline void 202 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 dir24_8_lookup_bulk(dp, ips, next_hops, n, 3); 208 } 209 210 static inline void 211 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 uint32_t prefetch_offset = RTE_MIN(15U, n); 218 uint8_t nh_sz = dp->nh_sz; 219 220 for (i = 0; i < prefetch_offset; i++) 221 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); 222 for (i = 0; i < (n - prefetch_offset); i++) { 223 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], 224 nh_sz)); 225 tmp = get_tbl24(dp, ips[i], nh_sz); 226 if (unlikely(is_entry_extended(tmp))) 227 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 228 229 next_hops[i] = tmp >> 1; 230 } 231 for (; i < n; i++) { 232 tmp = get_tbl24(dp, ips[i], nh_sz); 233 if (unlikely(is_entry_extended(tmp))) 234 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 235 236 next_hops[i] = tmp >> 1; 237 } 238 } 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_ */ 254