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