1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
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 *
get_tbl24_p(struct dir24_8_tbl * dp,uint32_t ip,uint8_t nh_sz)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
bits_in_nh(uint8_t nh_sz)50 bits_in_nh(uint8_t nh_sz)
51 {
52 return 8 * (1 << nh_sz);
53 }
54
55 static inline uint64_t
get_max_nh(uint8_t nh_sz)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
get_tbl24_idx(uint32_t ip)62 get_tbl24_idx(uint32_t ip)
63 {
64 return ip >> 8;
65 }
66
67 static inline uint32_t
get_tbl8_idx(uint32_t res,uint32_t ip)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
lookup_msk(uint8_t nh_sz)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
get_psd_idx(uint32_t val,uint8_t nh_sz)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
get_tbl_idx(uint32_t val,uint8_t nh_sz)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
get_tbl24(struct dir24_8_tbl * dp,uint32_t ip,uint8_t nh_sz)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
get_tbl8(struct dir24_8_tbl * dp,uint32_t res,uint32_t ip,uint8_t nh_sz)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
is_entry_extended(uint64_t ent)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
dir24_8_lookup_bulk(struct dir24_8_tbl * dp,const uint32_t * ips,uint64_t * next_hops,const unsigned int n,uint8_t nh_sz)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
dir24_8_lookup_bulk_0(void * p,const uint32_t * ips,uint64_t * next_hops,const unsigned int n)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
dir24_8_lookup_bulk_1(void * p,const uint32_t * ips,uint64_t * next_hops,const unsigned int n)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
dir24_8_lookup_bulk_2(void * p,const uint32_t * ips,uint64_t * next_hops,const unsigned int n)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
dir24_8_lookup_bulk_3(void * p,const uint32_t * ips,uint64_t * next_hops,const unsigned int n)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
dir24_8_lookup_bulk_uni(void * p,const uint32_t * ips,uint64_t * next_hops,const unsigned int n)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_ */
260