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