Branch data Line data Source code
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 : : #include <stdbool.h>
11 : :
12 : : #include <rte_byteorder.h>
13 : : #include <rte_prefetch.h>
14 : : #include <rte_branch_prediction.h>
15 : : #include <rte_rcu_qsbr.h>
16 : :
17 : : /**
18 : : * @file
19 : : * DIR24_8 algorithm
20 : : */
21 : :
22 : : #define DIR24_8_TBL24_NUM_ENT (1 << 24)
23 : : #define DIR24_8_TBL8_GRP_NUM_ENT 256U
24 : : #define DIR24_8_EXT_ENT 1
25 : : #define DIR24_8_TBL24_MASK 0xffffff00
26 : :
27 : : #define BITMAP_SLAB_BIT_SIZE_LOG2 6
28 : : #define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2)
29 : : #define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1)
30 : :
31 : : struct dir24_8_tbl {
32 : : uint32_t number_tbl8s; /**< Total number of tbl8s */
33 : : uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */
34 : : uint32_t cur_tbl8s; /**< Current number of tbl8s */
35 : : enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */
36 : : /* RCU config. */
37 : : enum rte_fib_qsbr_mode rcu_mode;/* Blocking, defer queue. */
38 : : struct rte_rcu_qsbr *v; /* RCU QSBR variable. */
39 : : struct rte_rcu_qsbr_dq *dq; /* RCU QSBR defer queue. */
40 : : uint64_t def_nh; /**< Default next hop */
41 : : uint64_t *tbl8; /**< tbl8 table. */
42 : : uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/
43 : : /* tbl24 table. */
44 : : alignas(RTE_CACHE_LINE_SIZE) uint64_t tbl24[];
45 : : };
46 : :
47 : : static inline void *
48 : : get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
49 : : {
50 : 620045 : return (void *)&((uint8_t *)dp->tbl24)[(ip &
51 : 905 : DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
52 : : }
53 : :
54 : : static inline uint8_t
55 : : bits_in_nh(uint8_t nh_sz)
56 : : {
57 : 2705 : return 8 * (1 << nh_sz);
58 : : }
59 : :
60 : : static inline uint64_t
61 : : get_max_nh(uint8_t nh_sz)
62 : : {
63 [ + - + - ]: 1544 : return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
64 : : }
65 : :
66 : : static inline uint32_t
67 : : get_tbl24_idx(uint32_t ip)
68 : : {
69 : 0 : return ip >> 8;
70 : : }
71 : :
72 : : static inline uint32_t
73 : : get_tbl8_idx(uint32_t res, uint32_t ip)
74 : : {
75 : 0 : return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
76 : : }
77 : :
78 : : static inline uint64_t
79 : : lookup_msk(uint8_t nh_sz)
80 : : {
81 : 1161 : return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
82 : : }
83 : :
84 : : static inline uint8_t
85 : : get_psd_idx(uint32_t val, uint8_t nh_sz)
86 : : {
87 : 1161 : return val & ((1 << (3 - nh_sz)) - 1);
88 : : }
89 : :
90 : : static inline uint32_t
91 : : get_tbl_idx(uint32_t val, uint8_t nh_sz)
92 : : {
93 : 1161 : return val >> (3 - nh_sz);
94 : : }
95 : :
96 : : static inline uint64_t
97 : : get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
98 : : {
99 : 1161 : return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >>
100 : 1161 : (get_psd_idx(get_tbl24_idx(ip), nh_sz) *
101 [ - + - - : 1161 : bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
+ + ]
102 : : }
103 : :
104 : : static inline uint64_t
105 : 0 : get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz)
106 : : {
107 : 0 : return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >>
108 : 0 : (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) *
109 : 0 : bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
110 : : }
111 : :
112 : : static inline int
113 : : is_entry_extended(uint64_t ent)
114 : : {
115 : 8514 : return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT;
116 : : }
117 : :
118 : : #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \
119 : : static inline void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \
120 : : uint64_t *next_hops, const unsigned int n) \
121 : : { \
122 : : struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \
123 : : uint64_t tmp; \
124 : : uint32_t i; \
125 : : uint32_t prefetch_offset = \
126 : : RTE_MIN((unsigned int)bulk_prefetch, n); \
127 : : \
128 : : for (i = 0; i < prefetch_offset; i++) \
129 : : rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \
130 : : for (i = 0; i < (n - prefetch_offset); i++) { \
131 : : rte_prefetch0(get_tbl24_p(dp, \
132 : : ips[i + prefetch_offset], nh_sz)); \
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 : : for (; i < n; i++) { \
140 : : tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \
141 : : if (unlikely(is_entry_extended(tmp))) \
142 : : tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \
143 : : ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
144 : : next_hops[i] = tmp >> 1; \
145 : : } \
146 : : } \
147 : :
148 [ + + + + : 5289 : LOOKUP_FUNC(1b, uint8_t, 5, 0)
+ + - + +
+ ]
149 [ + + + + : 5418 : LOOKUP_FUNC(2b, uint16_t, 6, 1)
+ + - + +
+ ]
150 [ + + + + : 1812915 : LOOKUP_FUNC(4b, uint32_t, 15, 2)
+ + + + +
+ ]
151 [ + + + + : 6192 : LOOKUP_FUNC(8b, uint64_t, 12, 3)
+ + - + +
+ ]
152 : :
153 : : static inline void
154 : 0 : dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips,
155 : : uint64_t *next_hops, const unsigned int n, uint8_t nh_sz)
156 : : {
157 : : uint64_t tmp;
158 : : uint32_t i;
159 : 0 : uint32_t prefetch_offset = RTE_MIN(15U, n);
160 : :
161 [ # # ]: 0 : for (i = 0; i < prefetch_offset; i++)
162 : 0 : rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
163 [ # # ]: 0 : for (i = 0; i < (n - prefetch_offset); i++) {
164 : 0 : rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
165 : : nh_sz));
166 : 0 : tmp = get_tbl24(dp, ips[i], nh_sz);
167 [ # # ]: 0 : if (unlikely(is_entry_extended(tmp)))
168 : 0 : tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
169 : :
170 : 0 : next_hops[i] = tmp >> 1;
171 : : }
172 [ # # ]: 0 : for (; i < n; i++) {
173 : 0 : tmp = get_tbl24(dp, ips[i], nh_sz);
174 [ # # ]: 0 : if (unlikely(is_entry_extended(tmp)))
175 : 0 : tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
176 : :
177 : 0 : next_hops[i] = tmp >> 1;
178 : : }
179 : 0 : }
180 : :
181 : : static inline void
182 : 0 : dir24_8_lookup_bulk_0(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 : 0 : dir24_8_lookup_bulk(dp, ips, next_hops, n, 0);
188 : 0 : }
189 : :
190 : : static inline void
191 : 0 : dir24_8_lookup_bulk_1(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 : 0 : dir24_8_lookup_bulk(dp, ips, next_hops, n, 1);
197 : 0 : }
198 : :
199 : : static inline void
200 : 0 : dir24_8_lookup_bulk_2(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 : 0 : dir24_8_lookup_bulk(dp, ips, next_hops, n, 2);
206 : 0 : }
207 : :
208 : : static inline void
209 : 0 : dir24_8_lookup_bulk_3(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 : :
214 : 0 : dir24_8_lookup_bulk(dp, ips, next_hops, n, 3);
215 : 0 : }
216 : :
217 : : static inline void
218 : 0 : dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips,
219 : : uint64_t *next_hops, const unsigned int n)
220 : : {
221 : : struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
222 : : uint64_t tmp;
223 : : uint32_t i;
224 : 0 : uint32_t prefetch_offset = RTE_MIN(15U, n);
225 : 0 : uint8_t nh_sz = dp->nh_sz;
226 : :
227 [ # # ]: 0 : for (i = 0; i < prefetch_offset; i++)
228 : 0 : rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
229 [ # # ]: 0 : for (i = 0; i < (n - prefetch_offset); i++) {
230 : 0 : rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
231 : : nh_sz));
232 : 0 : tmp = get_tbl24(dp, ips[i], nh_sz);
233 [ # # ]: 0 : if (unlikely(is_entry_extended(tmp)))
234 : 0 : tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
235 : :
236 : 0 : next_hops[i] = tmp >> 1;
237 : : }
238 [ # # ]: 0 : for (; i < n; i++) {
239 : 0 : tmp = get_tbl24(dp, ips[i], nh_sz);
240 [ # # ]: 0 : if (unlikely(is_entry_extended(tmp)))
241 : 0 : tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
242 : :
243 : 0 : next_hops[i] = tmp >> 1;
244 : : }
245 : 0 : }
246 : :
247 : : #define BSWAP_MAX_LENGTH 64
248 : :
249 : : typedef void (*dir24_8_lookup_bulk_be_cb)(void *p, const uint32_t *ips, uint64_t *next_hops,
250 : : const unsigned int n);
251 : :
252 : : static inline void
253 : 0 : dir24_8_lookup_bulk_be(void *p, const uint32_t *ips, uint64_t *next_hops, const unsigned int n,
254 : : dir24_8_lookup_bulk_be_cb cb)
255 : : {
256 : : uint32_t le_ips[BSWAP_MAX_LENGTH];
257 : : unsigned int i;
258 : :
259 : : #if RTE_BYTE_ORDER == RTE_BIG_ENDIAN
260 : : cb(p, ips, next_hops, n);
261 : : #else
262 [ # # ]: 0 : for (i = 0; i < n; i += BSWAP_MAX_LENGTH) {
263 : : int j;
264 [ # # # # ]: 0 : for (j = 0; j < BSWAP_MAX_LENGTH && i + j < n; j++)
265 [ # # ]: 0 : le_ips[j] = rte_be_to_cpu_32(ips[i + j]);
266 : :
267 : 0 : cb(p, le_ips, next_hops + i, j);
268 : : }
269 : : #endif
270 : 0 : }
271 : :
272 : : #define DECLARE_BE_LOOKUP_FN(name) \
273 : : static inline void \
274 : : name##_be(void *p, const uint32_t *ips, uint64_t *next_hops, const unsigned int n) \
275 : : { \
276 : : dir24_8_lookup_bulk_be(p, ips, next_hops, n, name); \
277 : : }
278 : :
279 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_1b)
280 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_2b)
281 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_4b)
282 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_8b)
283 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_0)
284 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_1)
285 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_2)
286 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_3)
287 : 0 : DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_uni)
288 : :
289 : : void *
290 : : dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf);
291 : :
292 : : void
293 : : dir24_8_free(void *p);
294 : :
295 : : rte_fib_lookup_fn_t
296 : : dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type, bool be_addr);
297 : :
298 : : int
299 : : dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
300 : : uint64_t next_hop, int op);
301 : :
302 : : int
303 : : dir24_8_rcu_qsbr_add(struct dir24_8_tbl *dp, struct rte_fib_rcu_config *cfg,
304 : : const char *name);
305 : :
306 : : #endif /* _DIR24_8_H_ */
|
