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