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