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 <stdbool.h>
7 : : #include <stdint.h>
8 : : #include <sys/queue.h>
9 : :
10 : : #include <eal_export.h>
11 : : #include <rte_eal_memconfig.h>
12 : : #include <rte_errno.h>
13 : : #include <rte_malloc.h>
14 : : #include <rte_mempool.h>
15 : : #include <rte_string_fns.h>
16 : : #include <rte_tailq.h>
17 : :
18 : : #include <rte_rib.h>
19 : :
20 : : #include "rib_log.h"
21 : :
22 [ - + ]: 252 : RTE_LOG_REGISTER_DEFAULT(rib_logtype, INFO);
23 : :
24 : : TAILQ_HEAD(rte_rib_list, rte_tailq_entry);
25 : : static struct rte_tailq_elem rte_rib_tailq = {
26 : : .name = "RTE_RIB",
27 : : };
28 [ - + ]: 252 : EAL_REGISTER_TAILQ(rte_rib_tailq)
29 : :
30 : : #define RTE_RIB_VALID_NODE 1
31 : : /* Maximum depth value possible for IPv4 RIB. */
32 : : #define RIB_MAXDEPTH 32
33 : : /* Maximum length of a RIB name. */
34 : : #define RTE_RIB_NAMESIZE 64
35 : :
36 : : struct rte_rib_node {
37 : : struct rte_rib_node *left;
38 : : struct rte_rib_node *right;
39 : : struct rte_rib_node *parent;
40 : : uint32_t ip;
41 : : uint8_t depth;
42 : : uint8_t flag;
43 : : uint64_t nh;
44 : : uint64_t ext[];
45 : : };
46 : :
47 : : struct rte_rib {
48 : : char name[RTE_RIB_NAMESIZE];
49 : : struct rte_rib_node *tree;
50 : : struct rte_mempool *node_pool;
51 : : uint32_t cur_nodes;
52 : : uint32_t cur_routes;
53 : : uint32_t max_nodes;
54 : : };
55 : :
56 : : static inline bool
57 : : is_valid_node(const struct rte_rib_node *node)
58 : : {
59 : 38923 : return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
60 : : }
61 : :
62 : : static inline bool
63 : : is_right_node(const struct rte_rib_node *node)
64 : : {
65 : 249 : return node->parent->right == node;
66 : : }
67 : :
68 : : /*
69 : : * Check if ip1 is covered by ip2/depth prefix
70 : : */
71 : : static inline bool
72 : : is_covered(uint32_t ip1, uint32_t ip2, uint8_t depth)
73 : : {
74 [ + - ]: 2480 : return ((ip1 ^ ip2) & rte_rib_depth_to_mask(depth)) == 0;
75 : : }
76 : :
77 : : static inline struct rte_rib_node *
78 : : get_nxt_node(struct rte_rib_node *node, uint32_t ip)
79 : : {
80 [ + - + - : 49155 : if (node->depth == RIB_MAXDEPTH)
+ + ]
81 : : return NULL;
82 [ + + - + : 49091 : return (ip & (1 << (31 - node->depth))) ? node->right : node->left;
+ + ]
83 : : }
84 : :
85 : : static struct rte_rib_node *
86 : 839 : node_alloc(struct rte_rib *rib)
87 : : {
88 : : struct rte_rib_node *ent;
89 : : int ret;
90 : :
91 [ - + ]: 839 : ret = rte_mempool_get(rib->node_pool, (void *)&ent);
92 [ + - ]: 839 : if (unlikely(ret != 0))
93 : : return NULL;
94 : 839 : ++rib->cur_nodes;
95 : 839 : return ent;
96 : : }
97 : :
98 : : static void
99 : 839 : node_free(struct rte_rib *rib, struct rte_rib_node *ent)
100 : : {
101 : 839 : --rib->cur_nodes;
102 [ - + ]: 839 : rte_mempool_put(rib->node_pool, ent);
103 : 839 : }
104 : :
105 : : RTE_EXPORT_SYMBOL(rte_rib_lookup)
106 : : struct rte_rib_node *
107 : 4259 : rte_rib_lookup(struct rte_rib *rib, uint32_t ip)
108 : : {
109 : : struct rte_rib_node *cur, *prev = NULL;
110 : :
111 [ - + ]: 4259 : if (unlikely(rib == NULL)) {
112 : 0 : rte_errno = EINVAL;
113 : 0 : return NULL;
114 : : }
115 : :
116 : 4259 : cur = rib->tree;
117 [ + + + + ]: 38052 : while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
118 [ + - ]: 33793 : if (is_valid_node(cur))
119 : : prev = cur;
120 : : cur = get_nxt_node(cur, ip);
121 : : }
122 : : return prev;
123 : : }
124 : :
125 : : RTE_EXPORT_SYMBOL(rte_rib_lookup_parent)
126 : : struct rte_rib_node *
127 : 1537 : rte_rib_lookup_parent(struct rte_rib_node *ent)
128 : : {
129 : : struct rte_rib_node *tmp;
130 : :
131 [ + - ]: 1537 : if (ent == NULL)
132 : : return NULL;
133 : 1537 : tmp = ent->parent;
134 [ + + - + ]: 1537 : while ((tmp != NULL) && !is_valid_node(tmp))
135 : 0 : tmp = tmp->parent;
136 : : return tmp;
137 : : }
138 : :
139 : : static struct rte_rib_node *
140 : 3344 : __rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)
141 : : {
142 : : struct rte_rib_node *cur;
143 : :
144 : 3344 : cur = rib->tree;
145 [ + + ]: 13265 : while (cur != NULL) {
146 [ + + + + : 11904 : if ((cur->ip == ip) && (cur->depth == depth) &&
+ - ]
147 : : is_valid_node(cur))
148 : 1672 : return cur;
149 [ + + + + ]: 10232 : if ((cur->depth > depth) ||
150 [ + + ]: 9922 : !is_covered(ip, cur->ip, cur->depth))
151 : : break;
152 : : cur = get_nxt_node(cur, ip);
153 : : }
154 : : return NULL;
155 : : }
156 : :
157 : : RTE_EXPORT_SYMBOL(rte_rib_lookup_exact)
158 : : struct rte_rib_node *
159 : 2505 : rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)
160 : : {
161 [ - + ]: 2505 : if (unlikely(rib == NULL || depth > RIB_MAXDEPTH)) {
162 : 0 : rte_errno = EINVAL;
163 : 0 : return NULL;
164 : : }
165 : 2505 : ip &= rte_rib_depth_to_mask(depth);
166 : :
167 : 2505 : return __rib_lookup_exact(rib, ip, depth);
168 : : }
169 : :
170 : : /*
171 : : * Traverses on subtree and retrieves more specific routes
172 : : * for a given in args ip/depth prefix
173 : : * last = NULL means the first invocation
174 : : */
175 : : RTE_EXPORT_SYMBOL(rte_rib_get_nxt)
176 : : struct rte_rib_node *
177 : 2961 : rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip,
178 : : uint8_t depth, struct rte_rib_node *last, int flag)
179 : : {
180 : : struct rte_rib_node *tmp, *prev = NULL;
181 : :
182 [ - + ]: 2961 : if (unlikely(rib == NULL || depth > RIB_MAXDEPTH)) {
183 : 0 : rte_errno = EINVAL;
184 : 0 : return NULL;
185 : : }
186 : :
187 [ + + ]: 2961 : if (last == NULL) {
188 : 2708 : tmp = rib->tree;
189 [ + + + + ]: 8149 : while ((tmp) && (tmp->depth < depth))
190 : : tmp = get_nxt_node(tmp, ip);
191 : : } else {
192 : : tmp = last;
193 [ + + - + : 501 : while ((tmp->parent != NULL) && (is_right_node(tmp) ||
+ + ]
194 : : (tmp->parent->right == NULL))) {
195 : : tmp = tmp->parent;
196 [ + - + - ]: 248 : if (is_valid_node(tmp) &&
197 [ + - ]: 248 : (is_covered(tmp->ip, ip, depth) &&
198 [ - + ]: 248 : (tmp->depth > depth)))
199 : 0 : return tmp;
200 : : }
201 [ + + ]: 253 : tmp = (tmp->parent) ? tmp->parent->right : NULL;
202 : : }
203 [ + + ]: 4569 : while (tmp) {
204 [ + + + - ]: 1968 : if (is_valid_node(tmp) &&
205 [ + - ]: 1967 : (is_covered(tmp->ip, ip, depth) &&
206 [ + + ]: 1967 : (tmp->depth > depth))) {
207 : : prev = tmp;
208 [ + + ]: 366 : if (flag == RTE_RIB_GET_NXT_COVER)
209 : 360 : return prev;
210 : : }
211 [ + + ]: 1608 : tmp = (tmp->left) ? tmp->left : tmp->right;
212 : : }
213 : : return prev;
214 : : }
215 : :
216 : : RTE_EXPORT_SYMBOL(rte_rib_remove)
217 : : void
218 : 838 : rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth)
219 : : {
220 : : struct rte_rib_node *cur, *prev, *child;
221 : :
222 : 838 : cur = rte_rib_lookup_exact(rib, ip, depth);
223 [ + - ]: 838 : if (cur == NULL)
224 : : return;
225 : :
226 : 838 : --rib->cur_routes;
227 : 838 : cur->flag &= ~RTE_RIB_VALID_NODE;
228 [ + + ]: 994 : while (!is_valid_node(cur)) {
229 [ + + + - ]: 839 : if ((cur->left != NULL) && (cur->right != NULL))
230 : : return;
231 [ + + ]: 839 : child = (cur->left == NULL) ? cur->right : cur->left;
232 [ + + ]: 839 : if (child != NULL)
233 : 156 : child->parent = cur->parent;
234 [ + + ]: 839 : if (cur->parent == NULL) {
235 : 683 : rib->tree = child;
236 : 683 : node_free(rib, cur);
237 : 683 : return;
238 : : }
239 [ + - ]: 156 : if (cur->parent->left == cur)
240 : 156 : cur->parent->left = child;
241 : : else
242 : 0 : cur->parent->right = child;
243 : : prev = cur;
244 : : cur = cur->parent;
245 : 156 : node_free(rib, prev);
246 : : }
247 : : }
248 : :
249 : : RTE_EXPORT_SYMBOL(rte_rib_insert)
250 : : struct rte_rib_node *
251 : 841 : rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
252 : : {
253 : : struct rte_rib_node **tmp;
254 : : struct rte_rib_node *prev = NULL;
255 : : struct rte_rib_node *new_node = NULL;
256 : : struct rte_rib_node *common_node = NULL;
257 : : int d = 0;
258 : : uint32_t common_prefix;
259 : : uint8_t common_depth;
260 : :
261 [ + + ]: 841 : if (unlikely(rib == NULL || depth > RIB_MAXDEPTH)) {
262 : 2 : rte_errno = EINVAL;
263 : 2 : return NULL;
264 : : }
265 : :
266 : 839 : tmp = &rib->tree;
267 : 839 : ip &= rte_rib_depth_to_mask(depth);
268 : 839 : new_node = __rib_lookup_exact(rib, ip, depth);
269 [ + + ]: 839 : if (new_node != NULL) {
270 : 1 : rte_errno = EEXIST;
271 : 1 : return NULL;
272 : : }
273 : :
274 : 838 : new_node = node_alloc(rib);
275 [ - + ]: 838 : if (new_node == NULL) {
276 : 0 : rte_errno = ENOMEM;
277 : 0 : return NULL;
278 : : }
279 : 838 : new_node->left = NULL;
280 : 838 : new_node->right = NULL;
281 : 838 : new_node->parent = NULL;
282 : 838 : new_node->ip = ip;
283 : 838 : new_node->depth = depth;
284 : 838 : new_node->flag = RTE_RIB_VALID_NODE;
285 : :
286 : : /* traverse down the tree to find matching node or closest matching */
287 : : while (1) {
288 : : /* insert as the last node in the branch */
289 [ + + ]: 3318 : if (*tmp == NULL) {
290 : 682 : *tmp = new_node;
291 : 682 : new_node->parent = prev;
292 : 682 : ++rib->cur_routes;
293 : 682 : return *tmp;
294 : : }
295 : : /*
296 : : * Intermediate node found.
297 : : * Previous rte_rib_lookup_exact() returned NULL
298 : : * but node with proper search criteria is found.
299 : : * Validate intermediate node and return.
300 : : */
301 [ + + - + ]: 2636 : if ((ip == (*tmp)->ip) && (depth == (*tmp)->depth)) {
302 : 0 : node_free(rib, new_node);
303 : 0 : (*tmp)->flag |= RTE_RIB_VALID_NODE;
304 : 0 : ++rib->cur_routes;
305 : 0 : return *tmp;
306 : : }
307 : 2636 : d = (*tmp)->depth;
308 [ + + + - ]: 2636 : if ((d >= depth) || !is_covered(ip, (*tmp)->ip, d))
309 : : break;
310 : : prev = *tmp;
311 [ - + ]: 2480 : tmp = (ip & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
312 : : }
313 : : /* closest node found, new_node should be inserted in the middle */
314 : 156 : common_depth = RTE_MIN(depth, (*tmp)->depth);
315 : 156 : common_prefix = ip ^ (*tmp)->ip;
316 [ + + ]: 156 : d = (common_prefix == 0) ? 32 : rte_clz32(common_prefix);
317 : :
318 [ + + ]: 156 : common_depth = RTE_MIN(d, common_depth);
319 : 156 : common_prefix = ip & rte_rib_depth_to_mask(common_depth);
320 [ + + ]: 156 : if ((common_prefix == ip) && (common_depth == depth)) {
321 : : /* insert as a parent */
322 [ - + ]: 155 : if ((*tmp)->ip & (1 << (31 - depth)))
323 : 0 : new_node->right = *tmp;
324 : : else
325 : 155 : new_node->left = *tmp;
326 : 155 : new_node->parent = (*tmp)->parent;
327 : 155 : (*tmp)->parent = new_node;
328 : 155 : *tmp = new_node;
329 : : } else {
330 : : /* create intermediate node */
331 : 1 : common_node = node_alloc(rib);
332 [ - + ]: 1 : if (common_node == NULL) {
333 : 0 : node_free(rib, new_node);
334 : 0 : rte_errno = ENOMEM;
335 : 0 : return NULL;
336 : : }
337 : 1 : common_node->ip = common_prefix;
338 : 1 : common_node->depth = common_depth;
339 : 1 : common_node->flag = 0;
340 : 1 : common_node->parent = (*tmp)->parent;
341 : 1 : new_node->parent = common_node;
342 : 1 : (*tmp)->parent = common_node;
343 [ - + ]: 1 : if ((new_node->ip & (1 << (31 - common_depth))) == 0) {
344 : 0 : common_node->left = new_node;
345 : 0 : common_node->right = *tmp;
346 : : } else {
347 : 1 : common_node->left = *tmp;
348 : 1 : common_node->right = new_node;
349 : : }
350 : 1 : *tmp = common_node;
351 : : }
352 : 156 : ++rib->cur_routes;
353 : 156 : return new_node;
354 : : }
355 : :
356 : : RTE_EXPORT_SYMBOL(rte_rib_get_ip)
357 : : int
358 : 251 : rte_rib_get_ip(const struct rte_rib_node *node, uint32_t *ip)
359 : : {
360 [ + + ]: 251 : if (unlikely(node == NULL || ip == NULL)) {
361 : 2 : rte_errno = EINVAL;
362 : 2 : return -1;
363 : : }
364 : 249 : *ip = node->ip;
365 : 249 : return 0;
366 : : }
367 : :
368 : : RTE_EXPORT_SYMBOL(rte_rib_get_depth)
369 : : int
370 : 251 : rte_rib_get_depth(const struct rte_rib_node *node, uint8_t *depth)
371 : : {
372 [ + + ]: 251 : if (unlikely(node == NULL || depth == NULL)) {
373 : 2 : rte_errno = EINVAL;
374 : 2 : return -1;
375 : : }
376 : 249 : *depth = node->depth;
377 : 249 : return 0;
378 : : }
379 : :
380 : : RTE_EXPORT_SYMBOL(rte_rib_get_ext)
381 : : void *
382 : 1 : rte_rib_get_ext(struct rte_rib_node *node)
383 : : {
384 [ - + ]: 1 : return (node == NULL) ? NULL : &node->ext[0];
385 : : }
386 : :
387 : : RTE_EXPORT_SYMBOL(rte_rib_get_nh)
388 : : int
389 : 3417 : rte_rib_get_nh(const struct rte_rib_node *node, uint64_t *nh)
390 : : {
391 [ + + ]: 3417 : if (unlikely(node == NULL || nh == NULL)) {
392 : 2 : rte_errno = EINVAL;
393 : 2 : return -1;
394 : : }
395 : 3415 : *nh = node->nh;
396 : 3415 : return 0;
397 : : }
398 : :
399 : : RTE_EXPORT_SYMBOL(rte_rib_set_nh)
400 : : int
401 : 836 : rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh)
402 : : {
403 [ + + ]: 836 : if (unlikely(node == NULL)) {
404 : 1 : rte_errno = EINVAL;
405 : 1 : return -1;
406 : : }
407 : 835 : node->nh = nh;
408 : 835 : return 0;
409 : : }
410 : :
411 : : RTE_EXPORT_SYMBOL(rte_rib_create)
412 : : struct rte_rib *
413 : 23 : rte_rib_create(const char *name, int socket_id, const struct rte_rib_conf *conf)
414 : : {
415 : : char mem_name[RTE_RIB_NAMESIZE];
416 : : struct rte_rib *rib = NULL;
417 : : struct rte_tailq_entry *te;
418 : : struct rte_rib_list *rib_list;
419 : : struct rte_mempool *node_pool;
420 : :
421 : : /* Check user arguments. */
422 [ + + + + ]: 23 : if (unlikely(name == NULL || conf == NULL || conf->max_nodes <= 0)) {
423 : 4 : rte_errno = EINVAL;
424 : 4 : return NULL;
425 : : }
426 : :
427 : : snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
428 : 19 : node_pool = rte_mempool_create(mem_name, conf->max_nodes,
429 : 19 : sizeof(struct rte_rib_node) + conf->ext_sz, 0, 0,
430 : : NULL, NULL, NULL, NULL, socket_id, 0);
431 : :
432 [ + + ]: 19 : if (node_pool == NULL) {
433 : 2 : RIB_LOG(ERR,
434 : : "Can not allocate mempool for RIB %s", name);
435 : 2 : return NULL;
436 : : }
437 : :
438 : : snprintf(mem_name, sizeof(mem_name), "RIB_%s", name);
439 : 17 : rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
440 : :
441 : 17 : rte_mcfg_tailq_write_lock();
442 : :
443 : : /* guarantee there's no existing */
444 [ - + ]: 17 : TAILQ_FOREACH(te, rib_list, next) {
445 : 0 : rib = (struct rte_rib *)te->data;
446 [ # # ]: 0 : if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
447 : : break;
448 : : }
449 : : rib = NULL;
450 [ - + ]: 17 : if (te != NULL) {
451 : 0 : rte_errno = EEXIST;
452 : 0 : goto exit;
453 : : }
454 : :
455 : : /* allocate tailq entry */
456 : 17 : te = rte_zmalloc("RIB_TAILQ_ENTRY", sizeof(*te), 0);
457 [ - + ]: 17 : if (unlikely(te == NULL)) {
458 : 0 : RIB_LOG(ERR,
459 : : "Can not allocate tailq entry for RIB %s", name);
460 : 0 : rte_errno = ENOMEM;
461 : 0 : goto exit;
462 : : }
463 : :
464 : : /* Allocate memory to store the RIB data structures. */
465 : 17 : rib = rte_zmalloc_socket(mem_name,
466 : : sizeof(struct rte_rib), RTE_CACHE_LINE_SIZE, socket_id);
467 [ - + ]: 17 : if (unlikely(rib == NULL)) {
468 : 0 : RIB_LOG(ERR, "RIB %s memory allocation failed", name);
469 : 0 : rte_errno = ENOMEM;
470 : 0 : goto free_te;
471 : : }
472 : :
473 : 17 : rte_strlcpy(rib->name, name, sizeof(rib->name));
474 : 17 : rib->tree = NULL;
475 : 17 : rib->max_nodes = conf->max_nodes;
476 : 17 : rib->node_pool = node_pool;
477 : 17 : te->data = (void *)rib;
478 : 17 : TAILQ_INSERT_TAIL(rib_list, te, next);
479 : :
480 : 17 : rte_mcfg_tailq_write_unlock();
481 : :
482 : 17 : return rib;
483 : :
484 : : free_te:
485 : 0 : rte_free(te);
486 : 0 : exit:
487 : 0 : rte_mcfg_tailq_write_unlock();
488 : 0 : rte_mempool_free(node_pool);
489 : :
490 : 0 : return NULL;
491 : : }
492 : :
493 : : RTE_EXPORT_SYMBOL(rte_rib_find_existing)
494 : : struct rte_rib *
495 : 0 : rte_rib_find_existing(const char *name)
496 : : {
497 : : struct rte_rib *rib = NULL;
498 : : struct rte_tailq_entry *te;
499 : : struct rte_rib_list *rib_list;
500 : :
501 : 0 : rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
502 : :
503 : 0 : rte_mcfg_tailq_read_lock();
504 [ # # ]: 0 : TAILQ_FOREACH(te, rib_list, next) {
505 : 0 : rib = (struct rte_rib *) te->data;
506 [ # # ]: 0 : if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
507 : : break;
508 : : }
509 : 0 : rte_mcfg_tailq_read_unlock();
510 : :
511 [ # # ]: 0 : if (te == NULL) {
512 : 0 : rte_errno = ENOENT;
513 : 0 : return NULL;
514 : : }
515 : :
516 : : return rib;
517 : : }
518 : :
519 : : RTE_EXPORT_SYMBOL(rte_rib_free)
520 : : void
521 : 18 : rte_rib_free(struct rte_rib *rib)
522 : : {
523 : : struct rte_tailq_entry *te;
524 : : struct rte_rib_list *rib_list;
525 : : struct rte_rib_node *tmp = NULL;
526 : :
527 [ + + ]: 18 : if (rib == NULL)
528 : : return;
529 : :
530 : 17 : rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
531 : :
532 : 17 : rte_mcfg_tailq_write_lock();
533 : :
534 : : /* find our tailq entry */
535 [ + - ]: 17 : TAILQ_FOREACH(te, rib_list, next) {
536 [ - + ]: 17 : if (te->data == (void *)rib)
537 : : break;
538 : : }
539 [ + - ]: 17 : if (te != NULL)
540 [ - + ]: 17 : TAILQ_REMOVE(rib_list, te, next);
541 : :
542 : 17 : rte_mcfg_tailq_write_unlock();
543 : :
544 : 22 : while ((tmp = rte_rib_get_nxt(rib, 0, 0, tmp,
545 [ + + ]: 22 : RTE_RIB_GET_NXT_ALL)) != NULL)
546 : 5 : rte_rib_remove(rib, tmp->ip, tmp->depth);
547 : :
548 : 17 : rte_mempool_free(rib->node_pool);
549 : 17 : rte_free(rib);
550 : 17 : rte_free(te);
551 : : }
|
