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