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 : : #include <stdint.h>
7 : : #include <stdio.h>
8 : :
9 : : #include <rte_debug.h>
10 : : #include <rte_malloc.h>
11 : : #include <rte_cpuflags.h>
12 : : #include <rte_errno.h>
13 : :
14 : : #include <rte_rib6.h>
15 : : #include <rte_fib6.h>
16 : : #include "fib_log.h"
17 : : #include "trie.h"
18 : :
19 : : #ifdef CC_AVX512_SUPPORT
20 : :
21 : : #include "trie_avx512.h"
22 : :
23 : : #endif /* CC_AVX512_SUPPORT */
24 : :
25 : : #define TRIE_NAMESIZE 64
26 : :
27 : : enum edge {
28 : : LEDGE,
29 : : REDGE
30 : : };
31 : :
32 : : static inline rte_fib6_lookup_fn_t
33 : : get_scalar_fn(enum rte_fib_trie_nh_sz nh_sz)
34 : : {
35 [ - - - - : 5 : switch (nh_sz) {
+ + - + ]
36 : : case RTE_FIB6_TRIE_2B:
37 : : return rte_trie_lookup_bulk_2b;
38 : 3 : case RTE_FIB6_TRIE_4B:
39 : 3 : return rte_trie_lookup_bulk_4b;
40 : 1 : case RTE_FIB6_TRIE_8B:
41 : 1 : return rte_trie_lookup_bulk_8b;
42 : 0 : default:
43 : 0 : return NULL;
44 : : }
45 : : }
46 : :
47 : : static inline rte_fib6_lookup_fn_t
48 : 5 : get_vector_fn(enum rte_fib_trie_nh_sz nh_sz)
49 : : {
50 : : #ifdef CC_AVX512_SUPPORT
51 [ + - + - ]: 10 : if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) <= 0 ||
52 [ + - ]: 10 : rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512DQ) <= 0 ||
53 [ + - ]: 10 : rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512BW) <= 0 ||
54 : 5 : rte_vect_get_max_simd_bitwidth() < RTE_VECT_SIMD_512)
55 : 5 : return NULL;
56 [ # # # # ]: 0 : switch (nh_sz) {
57 : : case RTE_FIB6_TRIE_2B:
58 : : return rte_trie_vec_lookup_bulk_2b;
59 : 0 : case RTE_FIB6_TRIE_4B:
60 : 0 : return rte_trie_vec_lookup_bulk_4b;
61 : 0 : case RTE_FIB6_TRIE_8B:
62 : 0 : return rte_trie_vec_lookup_bulk_8b;
63 : 0 : default:
64 : 0 : return NULL;
65 : : }
66 : : #else
67 : : RTE_SET_USED(nh_sz);
68 : : #endif
69 : : return NULL;
70 : : }
71 : :
72 : : rte_fib6_lookup_fn_t
73 : 5 : trie_get_lookup_fn(void *p, enum rte_fib6_lookup_type type)
74 : : {
75 : : enum rte_fib_trie_nh_sz nh_sz;
76 : : rte_fib6_lookup_fn_t ret_fn;
77 : : struct rte_trie_tbl *dp = p;
78 : :
79 [ + - ]: 5 : if (dp == NULL)
80 : : return NULL;
81 : :
82 : 5 : nh_sz = dp->nh_sz;
83 : :
84 [ - - + - ]: 5 : switch (type) {
85 : : case RTE_FIB6_LOOKUP_TRIE_SCALAR:
86 : : return get_scalar_fn(nh_sz);
87 : 0 : case RTE_FIB6_LOOKUP_TRIE_VECTOR_AVX512:
88 : 0 : return get_vector_fn(nh_sz);
89 : 5 : case RTE_FIB6_LOOKUP_DEFAULT:
90 : 5 : ret_fn = get_vector_fn(nh_sz);
91 [ + - ]: 5 : return (ret_fn != NULL) ? ret_fn : get_scalar_fn(nh_sz);
92 : : default:
93 : : return NULL;
94 : : }
95 : : return NULL;
96 : : }
97 : :
98 : : static void
99 : 11902 : write_to_dp(void *ptr, uint64_t val, enum rte_fib_trie_nh_sz size, int n)
100 : : {
101 : : int i;
102 : : uint16_t *ptr16 = (uint16_t *)ptr;
103 : : uint32_t *ptr32 = (uint32_t *)ptr;
104 : : uint64_t *ptr64 = (uint64_t *)ptr;
105 : :
106 [ + + + - ]: 11902 : switch (size) {
107 : : case RTE_FIB6_TRIE_2B:
108 [ + + ]: 67250281 : for (i = 0; i < n; i++)
109 : 67247852 : ptr16[i] = (uint16_t)val;
110 : : break;
111 : : case RTE_FIB6_TRIE_4B:
112 [ + + ]: 100958081 : for (i = 0; i < n; i++)
113 : 100951037 : ptr32[i] = (uint32_t)val;
114 : : break;
115 : : case RTE_FIB6_TRIE_8B:
116 [ + + ]: 67250281 : for (i = 0; i < n; i++)
117 : 67247852 : ptr64[i] = (uint64_t)val;
118 : : break;
119 : : }
120 : 11902 : }
121 : :
122 : : static void
123 : : tbl8_pool_init(struct rte_trie_tbl *dp)
124 : : {
125 : : uint32_t i;
126 : :
127 : : /* put entire range of indexes to the tbl8 pool */
128 [ + + ]: 131077 : for (i = 0; i < dp->number_tbl8s; i++)
129 : 131072 : dp->tbl8_pool[i] = i;
130 : :
131 : 5 : dp->tbl8_pool_pos = 0;
132 : : }
133 : :
134 : : /*
135 : : * Get an index of a free tbl8 from the pool
136 : : */
137 : : static inline int32_t
138 : : tbl8_get(struct rte_trie_tbl *dp)
139 : : {
140 [ # # ]: 0 : if (dp->tbl8_pool_pos == dp->number_tbl8s)
141 : : /* no more free tbl8 */
142 : : return -ENOSPC;
143 : :
144 : : /* next index */
145 : 1287 : return dp->tbl8_pool[dp->tbl8_pool_pos++];
146 : : }
147 : :
148 : : /*
149 : : * Put an index of a free tbl8 back to the pool
150 : : */
151 : : static inline void
152 : : tbl8_put(struct rte_trie_tbl *dp, uint32_t tbl8_ind)
153 : : {
154 : 1286 : dp->tbl8_pool[--dp->tbl8_pool_pos] = tbl8_ind;
155 : : }
156 : :
157 : : static int
158 [ + - ]: 1287 : tbl8_alloc(struct rte_trie_tbl *dp, uint64_t nh)
159 : : {
160 : : int64_t tbl8_idx;
161 : : uint8_t *tbl8_ptr;
162 : :
163 : 1287 : tbl8_idx = tbl8_get(dp);
164 : :
165 : : /* If there are no tbl8 groups try to reclaim one. */
166 [ - + - - : 1287 : if (unlikely(tbl8_idx == -ENOSPC && dp->dq &&
- - ]
167 : : !rte_rcu_qsbr_dq_reclaim(dp->dq, 1, NULL, NULL, NULL)))
168 : 0 : tbl8_idx = tbl8_get(dp);
169 : :
170 [ - + ]: 1287 : if (tbl8_idx < 0)
171 : 0 : return tbl8_idx;
172 : 1287 : tbl8_ptr = get_tbl_p_by_idx(dp->tbl8,
173 : 1287 : tbl8_idx * TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz);
174 : : /*Init tbl8 entries with nexthop from tbl24*/
175 : 1287 : write_to_dp((void *)tbl8_ptr, nh, dp->nh_sz,
176 : : TRIE_TBL8_GRP_NUM_ENT);
177 : 1287 : return tbl8_idx;
178 : : }
179 : :
180 : : static void
181 : 1286 : tbl8_cleanup_and_free(struct rte_trie_tbl *dp, uint64_t tbl8_idx)
182 : : {
183 : 1286 : uint8_t *ptr = (uint8_t *)dp->tbl8 + (tbl8_idx * TRIE_TBL8_GRP_NUM_ENT << dp->nh_sz);
184 : :
185 : 1286 : memset(ptr, 0, TRIE_TBL8_GRP_NUM_ENT << dp->nh_sz);
186 : 1286 : tbl8_put(dp, tbl8_idx);
187 : 1286 : }
188 : :
189 : : static void
190 : 0 : __rcu_qsbr_free_resource(void *p, void *data, unsigned int n __rte_unused)
191 : : {
192 : : struct rte_trie_tbl *dp = p;
193 : 0 : uint64_t tbl8_idx = *(uint64_t *)data;
194 : 0 : tbl8_cleanup_and_free(dp, tbl8_idx);
195 : 0 : }
196 : :
197 : : static void
198 : 10535 : tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t tbl8_idx)
199 : : {
200 : : uint32_t i;
201 : : uint64_t nh;
202 : : uint16_t *ptr16;
203 : : uint32_t *ptr32;
204 : : uint64_t *ptr64;
205 : :
206 [ + + + - ]: 10535 : switch (dp->nh_sz) {
207 : 3170 : case RTE_FIB6_TRIE_2B:
208 : 3170 : ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
209 : : TRIE_TBL8_GRP_NUM_ENT];
210 : 3170 : nh = *ptr16;
211 [ + + ]: 3170 : if (nh & TRIE_EXT_ENT)
212 : : return;
213 [ + + ]: 72694 : for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
214 [ + + ]: 72436 : if (nh != ptr16[i])
215 : : return;
216 : : }
217 : 258 : write_to_dp(par, nh, dp->nh_sz, 1);
218 : 258 : break;
219 : 4195 : case RTE_FIB6_TRIE_4B:
220 : 4195 : ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
221 : : TRIE_TBL8_GRP_NUM_ENT];
222 : 4195 : nh = *ptr32;
223 [ + + ]: 4195 : if (nh & TRIE_EXT_ENT)
224 : : return;
225 [ + + ]: 302262 : for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
226 [ + + ]: 301492 : if (nh != ptr32[i])
227 : : return;
228 : : }
229 : 770 : write_to_dp(par, nh, dp->nh_sz, 1);
230 : 770 : break;
231 : 3170 : case RTE_FIB6_TRIE_8B:
232 : 3170 : ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
233 : : TRIE_TBL8_GRP_NUM_ENT];
234 : 3170 : nh = *ptr64;
235 [ + + ]: 3170 : if (nh & TRIE_EXT_ENT)
236 : : return;
237 [ + + ]: 72694 : for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
238 [ + + ]: 72436 : if (nh != ptr64[i])
239 : : return;
240 : : }
241 : 258 : write_to_dp(par, nh, dp->nh_sz, 1);
242 : 258 : break;
243 : : }
244 : :
245 [ + + ]: 1286 : if (dp->v == NULL) {
246 : 774 : tbl8_cleanup_and_free(dp, tbl8_idx);
247 [ + - ]: 512 : } else if (dp->rcu_mode == RTE_FIB6_QSBR_MODE_SYNC) {
248 : 512 : rte_rcu_qsbr_synchronize(dp->v, RTE_QSBR_THRID_INVALID);
249 : 512 : tbl8_cleanup_and_free(dp, tbl8_idx);
250 : : } else { /* RTE_FIB6_QSBR_MODE_DQ */
251 [ # # ]: 0 : if (rte_rcu_qsbr_dq_enqueue(dp->dq, &tbl8_idx))
252 : 0 : FIB_LOG(ERR, "Failed to push QSBR FIFO");
253 : : }
254 : : }
255 : :
256 : : #define BYTE_SIZE 8
257 : : static inline uint32_t
258 : : get_idx(const struct rte_ipv6_addr *ip, uint32_t prev_idx, int bytes, int first_byte)
259 : : {
260 : : int i;
261 : : uint32_t idx = 0;
262 : : uint8_t bitshift;
263 : :
264 [ + + + + : 35896 : for (i = first_byte; i < (first_byte + bytes); i++) {
+ + ]
265 : 20779 : bitshift = (int8_t)(((first_byte + bytes - 1) - i)*BYTE_SIZE);
266 : 20779 : idx |= ip->a[i] << bitshift;
267 : : }
268 : 9995 : return (prev_idx * TRIE_TBL8_GRP_NUM_ENT) + idx;
269 : : }
270 : :
271 : : static inline uint64_t
272 : : get_val_by_p(void *p, uint8_t nh_sz)
273 : : {
274 : : uint64_t val = 0;
275 : :
276 : 13096 : switch (nh_sz) {
277 : 3682 : case RTE_FIB6_TRIE_2B:
278 : 3682 : val = *(uint16_t *)p;
279 : 3682 : break;
280 : 5732 : case RTE_FIB6_TRIE_4B:
281 : 5732 : val = *(uint32_t *)p;
282 : 5732 : break;
283 : 3682 : case RTE_FIB6_TRIE_8B:
284 : 3682 : val = *(uint64_t *)p;
285 : 3682 : break;
286 : : }
287 : : return val;
288 : : }
289 : :
290 : : /*
291 : : * recursively recycle tbl8's
292 : : */
293 : : static void
294 : 12556 : recycle_root_path(struct rte_trie_tbl *dp, const uint8_t *ip_part,
295 : : uint8_t common_tbl8, void *prev)
296 : : {
297 : : void *p;
298 : : uint64_t val;
299 : :
300 [ + + + - ]: 12556 : val = get_val_by_p(prev, dp->nh_sz);
301 [ + + ]: 12556 : if (unlikely((val & TRIE_EXT_ENT) != TRIE_EXT_ENT))
302 : : return;
303 : :
304 [ + - ]: 9995 : if (common_tbl8 != 0) {
305 : 9995 : p = get_tbl_p_by_idx(dp->tbl8, (val >> 1) *
306 : 9995 : TRIE_TBL8_GRP_NUM_ENT + *ip_part, dp->nh_sz);
307 : 9995 : recycle_root_path(dp, ip_part + 1, common_tbl8 - 1, p);
308 : : }
309 : 9995 : tbl8_recycle(dp, prev, val >> 1);
310 : : }
311 : :
312 : : static inline int
313 : 2561 : build_common_root(struct rte_trie_tbl *dp, const struct rte_ipv6_addr *ip,
314 : : int common_bytes, void **tbl)
315 : : {
316 : : void *tbl_ptr = NULL;
317 : : uint64_t *cur_tbl;
318 : : uint64_t val;
319 : : int i, j, idx, prev_idx = 0;
320 : :
321 : 2561 : cur_tbl = dp->tbl24;
322 [ + + ]: 12556 : for (i = 3, j = 0; i <= common_bytes; i++) {
323 : 9995 : idx = get_idx(ip, prev_idx, i - j, j);
324 [ + + ]: 9995 : val = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz);
325 [ + + ]: 9995 : tbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz);
326 [ + + ]: 9995 : if ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) {
327 : 747 : idx = tbl8_alloc(dp, val);
328 [ - + ]: 747 : if (unlikely(idx < 0))
329 : 0 : return idx;
330 : 747 : write_to_dp(tbl_ptr, (idx << 1) |
331 : : TRIE_EXT_ENT, dp->nh_sz, 1);
332 : : prev_idx = idx;
333 : : } else
334 : 9248 : prev_idx = val >> 1;
335 : :
336 : : j = i;
337 : 9995 : cur_tbl = dp->tbl8;
338 : : }
339 : 2561 : *tbl = get_tbl_p_by_idx(cur_tbl, prev_idx * TRIE_TBL8_GRP_NUM_ENT,
340 : 2561 : dp->nh_sz);
341 : 2561 : return 0;
342 : : }
343 : :
344 : : static int
345 : 5662 : write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part, uint64_t next_hop,
346 : : int len, enum edge edge, void *ent)
347 : : {
348 : 5662 : uint64_t val = next_hop << 1;
349 : : int tbl8_idx;
350 : : int ret = 0;
351 : : void *p;
352 : :
353 [ + + ]: 5662 : if (len != 0) {
354 [ + + + - ]: 540 : val = get_val_by_p(ent, dp->nh_sz);
355 [ - + ]: 540 : if ((val & TRIE_EXT_ENT) == TRIE_EXT_ENT)
356 : 0 : tbl8_idx = val >> 1;
357 : : else {
358 : 540 : tbl8_idx = tbl8_alloc(dp, val);
359 [ + - ]: 540 : if (tbl8_idx < 0)
360 : : return tbl8_idx;
361 : 540 : val = (tbl8_idx << 1)|TRIE_EXT_ENT;
362 : : }
363 : 540 : p = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx *
364 : 540 : TRIE_TBL8_GRP_NUM_ENT) + *ip_part, dp->nh_sz);
365 : 540 : ret = write_edge(dp, ip_part + 1, next_hop, len - 1, edge, p);
366 [ + - ]: 540 : if (ret < 0)
367 : : return ret;
368 [ + + ]: 540 : if (edge == LEDGE) {
369 : 270 : write_to_dp(RTE_PTR_ADD(p, (uintptr_t)(1) << dp->nh_sz),
370 : 270 : next_hop << 1, dp->nh_sz, UINT8_MAX - *ip_part);
371 : : } else {
372 : 270 : write_to_dp(get_tbl_p_by_idx(dp->tbl8, tbl8_idx *
373 : : TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz),
374 : 270 : next_hop << 1, dp->nh_sz, *ip_part);
375 : : }
376 : 540 : tbl8_recycle(dp, &val, tbl8_idx);
377 : : }
378 : :
379 : 5662 : write_to_dp(ent, val, dp->nh_sz, 1);
380 : 5662 : return ret;
381 : : }
382 : :
383 : : #define IPV6_MAX_IDX (RTE_IPV6_ADDR_SIZE - 1)
384 : : #define TBL24_BYTES 3
385 : : #define TBL8_LEN (RTE_IPV6_ADDR_SIZE - TBL24_BYTES)
386 : :
387 : : static int
388 : 2561 : install_to_dp(struct rte_trie_tbl *dp, const struct rte_ipv6_addr *ledge,
389 : : const struct rte_ipv6_addr *r, uint64_t next_hop)
390 : : {
391 : : void *common_root_tbl;
392 : : void *ent;
393 : : int ret;
394 : : int i;
395 : : int common_bytes;
396 : : int llen, rlen;
397 : : struct rte_ipv6_addr redge;
398 : :
399 : : /* decrement redge by 1*/
400 : 2561 : redge = *r;
401 [ + + ]: 26393 : for (i = 15; i >= 0; i--) {
402 : 26381 : redge.a[i]--;
403 [ + + ]: 26381 : if (redge.a[i] != 0xff)
404 : : break;
405 : : }
406 : :
407 [ + + ]: 17426 : for (common_bytes = 0; common_bytes < 15; common_bytes++) {
408 [ + + ]: 17312 : if (ledge->a[common_bytes] != redge.a[common_bytes])
409 : : break;
410 : : }
411 : :
412 : 2561 : ret = build_common_root(dp, ledge, common_bytes, &common_root_tbl);
413 [ + - ]: 2561 : if (unlikely(ret != 0))
414 : : return ret;
415 : : /*first uncommon tbl8 byte idx*/
416 : 2561 : uint8_t first_tbl8_byte = RTE_MAX(common_bytes, TBL24_BYTES);
417 : :
418 [ + + ]: 25589 : for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
419 [ + - ]: 23028 : if (ledge->a[i] != 0)
420 : : break;
421 : : }
422 : :
423 : 2561 : llen = i - first_tbl8_byte + (common_bytes < 3);
424 : :
425 [ + + ]: 25589 : for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
426 [ + - ]: 23028 : if (redge.a[i] != UINT8_MAX)
427 : : break;
428 : : }
429 : 2561 : rlen = i - first_tbl8_byte + (common_bytes < 3);
430 : :
431 : : /*first noncommon byte*/
432 [ + + ]: 2561 : uint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes;
433 [ + + ]: 2561 : uint8_t first_idx_len = (common_bytes < 3) ? 3 : 1;
434 : :
435 : 2561 : uint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);
436 : : uint32_t right_idx = get_idx(&redge, 0, first_idx_len, first_byte_idx);
437 : :
438 : 2561 : ent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz);
439 : 2561 : ret = write_edge(dp, &ledge->a[first_tbl8_byte + !(common_bytes < 3)],
440 : : next_hop, llen, LEDGE, ent);
441 [ + - ]: 2561 : if (ret < 0)
442 : : return ret;
443 : :
444 [ + + ]: 2561 : if (right_idx > left_idx + 1) {
445 : 2375 : ent = get_tbl_p_by_idx(common_root_tbl, left_idx + 1,
446 : 2375 : dp->nh_sz);
447 : 2375 : write_to_dp(ent, next_hop << 1, dp->nh_sz,
448 : 2375 : right_idx - (left_idx + 1));
449 : : }
450 : 2561 : ent = get_tbl_p_by_idx(common_root_tbl, right_idx, dp->nh_sz);
451 : 2561 : ret = write_edge(dp, &redge.a[first_tbl8_byte + !((common_bytes < 3))],
452 : : next_hop, rlen, REDGE, ent);
453 [ + - ]: 2561 : if (ret < 0)
454 : : return ret;
455 : :
456 : 2561 : uint8_t common_tbl8 = (common_bytes < TBL24_BYTES) ?
457 : 2561 : 0 : common_bytes - (TBL24_BYTES - 1);
458 : 2561 : ent = get_tbl24_p(dp, ledge, dp->nh_sz);
459 : 2561 : recycle_root_path(dp, ledge->a + TBL24_BYTES, common_tbl8, ent);
460 : 2561 : return 0;
461 : : }
462 : :
463 : : static void
464 : 3323 : get_nxt_net(struct rte_ipv6_addr *ip, uint8_t depth)
465 : : {
466 : : int i;
467 : : uint8_t part_depth;
468 : : uint8_t prev_byte;
469 : :
470 [ + + ]: 23678 : for (i = 0, part_depth = depth; part_depth > 8; part_depth -= 8, i++)
471 : : ;
472 : :
473 : 3323 : prev_byte = ip->a[i];
474 : 3323 : ip->a[i] += 1 << (8 - part_depth);
475 [ + + ]: 3323 : if (ip->a[i] < prev_byte) {
476 [ - + ]: 12 : while (i > 0) {
477 : 0 : ip->a[--i] += 1;
478 [ # # ]: 0 : if (ip->a[i] != 0)
479 : : break;
480 : : }
481 : : }
482 : 3323 : }
483 : :
484 : : static int
485 : 2561 : modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
486 : : const struct rte_ipv6_addr *ip,
487 : : uint8_t depth, uint64_t next_hop)
488 : : {
489 : : struct rte_rib6_node *tmp = NULL;
490 : : struct rte_ipv6_addr ledge, redge;
491 : : int ret;
492 : : uint8_t tmp_depth;
493 : :
494 [ + - ]: 2561 : if (next_hop > get_max_nh(dp->nh_sz))
495 : : return -EINVAL;
496 : :
497 : 2561 : ledge = *ip;
498 : : do {
499 : 3323 : tmp = rte_rib6_get_nxt(rib, ip, depth, tmp,
500 : : RTE_RIB6_GET_NXT_COVER);
501 [ + + ]: 3323 : if (tmp != NULL) {
502 : 762 : rte_rib6_get_depth(tmp, &tmp_depth);
503 [ - + ]: 762 : if (tmp_depth == depth)
504 : 0 : continue;
505 : 762 : rte_rib6_get_ip(tmp, &redge);
506 [ + - ]: 762 : if (rte_ipv6_addr_eq(&ledge, &redge)) {
507 : 762 : get_nxt_net(&ledge, tmp_depth);
508 : 762 : continue;
509 : : }
510 : 0 : ret = install_to_dp(dp, &ledge, &redge, next_hop);
511 [ # # ]: 0 : if (ret != 0)
512 : 0 : return ret;
513 : 0 : get_nxt_net(&redge, tmp_depth);
514 [ # # ]: 0 : ledge = redge;
515 : : /*
516 : : * we got to the end of address space
517 : : * and wrapped around
518 : : */
519 [ # # ]: 0 : if (rte_ipv6_addr_is_unspec(&ledge))
520 : : break;
521 : : } else {
522 : 2561 : redge = *ip;
523 : 2561 : get_nxt_net(&redge, depth);
524 [ - + - - ]: 2561 : if (rte_ipv6_addr_eq(&ledge, &redge) &&
525 : : !rte_ipv6_addr_is_unspec(&ledge))
526 : : break;
527 : :
528 : 2561 : ret = install_to_dp(dp, &ledge, &redge, next_hop);
529 [ - + ]: 2561 : if (ret != 0)
530 : 0 : return ret;
531 : : }
532 [ + + ]: 3323 : } while (tmp);
533 : :
534 : : return 0;
535 : : }
536 : :
537 : : int
538 : 2561 : trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
539 : : uint8_t depth, uint64_t next_hop, int op)
540 : : {
541 : : struct rte_trie_tbl *dp;
542 : : struct rte_rib6 *rib;
543 : : struct rte_rib6_node *tmp = NULL;
544 : : struct rte_rib6_node *node;
545 : : struct rte_rib6_node *parent;
546 : : struct rte_ipv6_addr ip_masked, tmp_ip;
547 : : int ret = 0;
548 : : uint64_t par_nh, node_nh;
549 : : uint8_t tmp_depth, depth_diff = 0, parent_depth = 24;
550 : :
551 [ + - + - ]: 2561 : if ((fib == NULL) || (ip == NULL) || (depth > RTE_IPV6_MAX_DEPTH))
552 : : return -EINVAL;
553 : :
554 : 2561 : dp = rte_fib6_get_dp(fib);
555 : : RTE_ASSERT(dp);
556 : 2561 : rib = rte_fib6_get_rib(fib);
557 : : RTE_ASSERT(rib);
558 : :
559 : 2561 : ip_masked = *ip;
560 [ + + ]: 2561 : rte_ipv6_addr_mask(&ip_masked, depth);
561 : :
562 [ + + ]: 2561 : if (depth > 24) {
563 : 2273 : tmp = rte_rib6_get_nxt(rib, &ip_masked,
564 : : RTE_ALIGN_FLOOR(depth, 8), NULL,
565 : : RTE_RIB6_GET_NXT_ALL);
566 [ + + ]: 2273 : if (tmp && op == RTE_FIB6_DEL) {
567 : : /* in case of delete operation, skip the prefix we are going to delete */
568 : 1094 : rte_rib6_get_ip(tmp, &tmp_ip);
569 : 1094 : rte_rib6_get_depth(tmp, &tmp_depth);
570 [ + - + + ]: 1094 : if (rte_ipv6_addr_eq(&ip_masked, &tmp_ip) && depth == tmp_depth)
571 : 785 : tmp = rte_rib6_get_nxt(rib, &ip_masked,
572 : : RTE_ALIGN_FLOOR(depth, 8), tmp, RTE_RIB6_GET_NXT_ALL);
573 : : }
574 : :
575 [ + + ]: 2273 : if (tmp == NULL) {
576 : 1187 : tmp = rte_rib6_lookup(rib, ip);
577 : : /**
578 : : * in case of delete operation, lookup returns the prefix
579 : : * we are going to delete. Find the parent.
580 : : */
581 [ + + ]: 1187 : if (tmp && op == RTE_FIB6_DEL)
582 : 593 : tmp = rte_rib6_lookup_parent(tmp);
583 : :
584 [ + + ]: 1187 : if (tmp != NULL) {
585 : 156 : rte_rib6_get_depth(tmp, &tmp_depth);
586 : 156 : parent_depth = RTE_MAX(tmp_depth, 24);
587 : : }
588 : 1187 : depth_diff = RTE_ALIGN_CEIL(depth, 8) -
589 : 1187 : RTE_ALIGN_CEIL(parent_depth, 8);
590 : 1187 : depth_diff = depth_diff >> 3;
591 : : }
592 : : }
593 : 2561 : node = rte_rib6_lookup_exact(rib, &ip_masked, depth);
594 [ + + - ]: 2561 : switch (op) {
595 : 1281 : case RTE_FIB6_ADD:
596 [ - + ]: 1281 : if (node != NULL) {
597 : 0 : rte_rib6_get_nh(node, &node_nh);
598 [ # # ]: 0 : if (node_nh == next_hop)
599 : : return 0;
600 : 0 : ret = modify_dp(dp, rib, &ip_masked, depth, next_hop);
601 [ # # ]: 0 : if (ret == 0)
602 : 0 : rte_rib6_set_nh(node, next_hop);
603 : 0 : return 0;
604 : : }
605 : :
606 [ + + + - ]: 1281 : if ((depth > 24) && (dp->rsvd_tbl8s + depth_diff > dp->number_tbl8s))
607 : : return -ENOSPC;
608 : :
609 : 1281 : node = rte_rib6_insert(rib, &ip_masked, depth);
610 [ - + ]: 1281 : if (node == NULL)
611 : 0 : return -rte_errno;
612 : 1281 : rte_rib6_set_nh(node, next_hop);
613 : 1281 : parent = rte_rib6_lookup_parent(node);
614 [ + + ]: 1281 : if (parent != NULL) {
615 : 381 : rte_rib6_get_nh(parent, &par_nh);
616 [ + - ]: 381 : if (par_nh == next_hop)
617 : : return 0;
618 : : }
619 : 1281 : ret = modify_dp(dp, rib, &ip_masked, depth, next_hop);
620 [ - + ]: 1281 : if (ret != 0) {
621 : 0 : rte_rib6_remove(rib, &ip_masked, depth);
622 : 0 : return ret;
623 : : }
624 : :
625 : 1281 : dp->rsvd_tbl8s += depth_diff;
626 : 1281 : return 0;
627 : 1280 : case RTE_FIB6_DEL:
628 [ + - ]: 1280 : if (node == NULL)
629 : : return -ENOENT;
630 : :
631 : 1280 : parent = rte_rib6_lookup_parent(node);
632 [ + + ]: 1280 : if (parent != NULL) {
633 : 381 : rte_rib6_get_nh(parent, &par_nh);
634 : 381 : rte_rib6_get_nh(node, &node_nh);
635 [ + - ]: 381 : if (par_nh != node_nh)
636 : 381 : ret = modify_dp(dp, rib, &ip_masked, depth,
637 : : par_nh);
638 : : } else
639 : 899 : ret = modify_dp(dp, rib, &ip_masked, depth, dp->def_nh);
640 : :
641 [ + - ]: 1280 : if (ret != 0)
642 : : return ret;
643 : 1280 : rte_rib6_remove(rib, ip, depth);
644 : :
645 : 1280 : dp->rsvd_tbl8s -= depth_diff;
646 : 1280 : return 0;
647 : : default:
648 : : break;
649 : : }
650 : : return -EINVAL;
651 : : }
652 : :
653 : : void *
654 : 7 : trie_create(const char *name, int socket_id,
655 : : struct rte_fib6_conf *conf)
656 : : {
657 : : char mem_name[TRIE_NAMESIZE];
658 : : struct rte_trie_tbl *dp = NULL;
659 : : uint64_t def_nh;
660 : : uint32_t num_tbl8;
661 : : enum rte_fib_trie_nh_sz nh_sz;
662 : :
663 [ + - ]: 7 : if ((name == NULL) || (conf == NULL) ||
664 [ + - + + ]: 7 : (conf->trie.nh_sz < RTE_FIB6_TRIE_2B) ||
665 [ + - ]: 6 : (conf->trie.nh_sz > RTE_FIB6_TRIE_8B) ||
666 : 6 : (conf->trie.num_tbl8 >
667 [ + - + + ]: 6 : get_max_nh(conf->trie.nh_sz)) ||
668 : 5 : (conf->trie.num_tbl8 == 0) ||
669 [ - + ]: 5 : (conf->default_nh >
670 : : get_max_nh(conf->trie.nh_sz))) {
671 : :
672 : 2 : rte_errno = EINVAL;
673 : 2 : return NULL;
674 : : }
675 : :
676 : : def_nh = conf->default_nh;
677 : : nh_sz = conf->trie.nh_sz;
678 : : num_tbl8 = conf->trie.num_tbl8;
679 : :
680 : : snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
681 : 5 : dp = rte_zmalloc_socket(name, sizeof(struct rte_trie_tbl) +
682 : 5 : TRIE_TBL24_NUM_ENT * (1 << nh_sz) + sizeof(uint32_t),
683 : : RTE_CACHE_LINE_SIZE, socket_id);
684 [ - + ]: 5 : if (dp == NULL) {
685 : 0 : rte_errno = ENOMEM;
686 : 0 : return dp;
687 : : }
688 : :
689 : 5 : write_to_dp(&dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
690 : :
691 : : snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
692 : 10 : dp->tbl8 = rte_zmalloc_socket(mem_name, TRIE_TBL8_GRP_NUM_ENT *
693 : 5 : (1ll << nh_sz) * (num_tbl8 + 1),
694 : : RTE_CACHE_LINE_SIZE, socket_id);
695 [ - + ]: 5 : if (dp->tbl8 == NULL) {
696 : 0 : rte_errno = ENOMEM;
697 : 0 : rte_free(dp);
698 : 0 : return NULL;
699 : : }
700 : 5 : dp->def_nh = def_nh;
701 : 5 : dp->nh_sz = nh_sz;
702 : 5 : dp->number_tbl8s = num_tbl8;
703 : :
704 : : snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
705 : 10 : dp->tbl8_pool = rte_zmalloc_socket(mem_name,
706 : 5 : sizeof(uint32_t) * dp->number_tbl8s,
707 : : RTE_CACHE_LINE_SIZE, socket_id);
708 [ - + ]: 5 : if (dp->tbl8_pool == NULL) {
709 : 0 : rte_errno = ENOMEM;
710 : 0 : rte_free(dp->tbl8);
711 : 0 : rte_free(dp);
712 : 0 : return NULL;
713 : : }
714 : :
715 : : tbl8_pool_init(dp);
716 : :
717 : 5 : return dp;
718 : : }
719 : :
720 : : void
721 : 5 : trie_free(void *p)
722 : : {
723 : : struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;
724 : :
725 : 5 : rte_rcu_qsbr_dq_delete(dp->dq);
726 : 5 : rte_free(dp->tbl8_pool);
727 : 5 : rte_free(dp->tbl8);
728 : 5 : rte_free(dp);
729 : 5 : }
730 : :
731 : : int
732 : 4 : trie_rcu_qsbr_add(struct rte_trie_tbl *dp, struct rte_fib6_rcu_config *cfg,
733 : : const char *name)
734 : : {
735 : 4 : struct rte_rcu_qsbr_dq_parameters params = {0};
736 : : char rcu_dq_name[RTE_RCU_QSBR_DQ_NAMESIZE];
737 : :
738 [ + - ]: 4 : if (dp == NULL || cfg == NULL)
739 : : return -EINVAL;
740 : :
741 [ + + ]: 4 : if (dp->v != NULL)
742 : : return -EEXIST;
743 : :
744 [ + + + ]: 3 : switch (cfg->mode) {
745 : : case RTE_FIB6_QSBR_MODE_DQ:
746 : : /* Init QSBR defer queue. */
747 : : snprintf(rcu_dq_name, sizeof(rcu_dq_name),
748 : : "FIB_RCU_%s", name);
749 : 1 : params.name = rcu_dq_name;
750 : 1 : params.size = cfg->dq_size;
751 [ + - ]: 1 : if (params.size == 0)
752 : 1 : params.size = RTE_FIB6_RCU_DQ_RECLAIM_SZ;
753 : 1 : params.trigger_reclaim_limit = cfg->reclaim_thd;
754 : 1 : params.max_reclaim_size = cfg->reclaim_max;
755 [ + - ]: 1 : if (params.max_reclaim_size == 0)
756 : 1 : params.max_reclaim_size = RTE_FIB6_RCU_DQ_RECLAIM_MAX;
757 : 1 : params.esize = sizeof(uint64_t);
758 : 1 : params.free_fn = __rcu_qsbr_free_resource;
759 : 1 : params.p = dp;
760 : 1 : params.v = cfg->v;
761 : 1 : dp->dq = rte_rcu_qsbr_dq_create(¶ms);
762 [ - + ]: 1 : if (dp->dq == NULL) {
763 : 0 : FIB_LOG(ERR, "FIB6 defer queue creation failed");
764 : 0 : return -ENOMEM;
765 : : }
766 : : break;
767 : : case RTE_FIB6_QSBR_MODE_SYNC:
768 : : /* No other things to do. */
769 : : break;
770 : : default:
771 : : return -EINVAL;
772 : : }
773 : 2 : dp->rcu_mode = cfg->mode;
774 : 2 : dp->v = cfg->v;
775 : :
776 : 2 : return 0;
777 : : }
|
