1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
3 * Copyright(c) 2019 Intel Corporation
9 #include <rte_eal_memconfig.h>
10 #include <rte_errno.h>
11 #include <rte_malloc.h>
12 #include <rte_mempool.h>
13 #include <rte_string_fns.h>
14 #include <rte_tailq.h>
18 #define RTE_RIB_VALID_NODE 1
19 #define RIB6_MAXDEPTH 128
20 /* Maximum length of a RIB6 name. */
21 #define RTE_RIB6_NAMESIZE 64
23 TAILQ_HEAD(rte_rib6_list, rte_tailq_entry);
24 static struct rte_tailq_elem rte_rib6_tailq = {
27 EAL_REGISTER_TAILQ(rte_rib6_tailq)
29 struct rte_rib6_node {
30 struct rte_rib6_node *left;
31 struct rte_rib6_node *right;
32 struct rte_rib6_node *parent;
34 uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE];
37 __extension__ uint64_t ext[0];
41 char name[RTE_RIB6_NAMESIZE];
42 struct rte_rib6_node *tree;
43 struct rte_mempool *node_pool;
50 is_valid_node(struct rte_rib6_node *node)
52 return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
56 is_right_node(struct rte_rib6_node *node)
58 return node->parent->right == node;
62 * Check if ip1 is covered by ip2/depth prefix
65 is_covered(const uint8_t ip1[RTE_RIB6_IPV6_ADDR_SIZE],
66 const uint8_t ip2[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
70 for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
71 if ((ip1[i] ^ ip2[i]) & get_msk_part(depth, i))
78 get_dir(const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
83 * depth & 127 clamps depth to values that will not
84 * read off the end of ip.
85 * depth is the number of bits deep into ip to traverse, and
86 * is incremented in blocks of 8 (1 byte). This means the last
87 * 3 bits are irrelevant to what the index of ip should be.
89 index = (depth & INT8_MAX) / CHAR_BIT;
92 * msk is the bitmask used to extract the bit used to decide the
93 * direction of the next step of the binary search.
95 msk = 1 << (7 - (depth & 7));
97 return (ip[index] & msk) != 0;
100 static inline struct rte_rib6_node *
101 get_nxt_node(struct rte_rib6_node *node,
102 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
104 if (node->depth == RIB6_MAXDEPTH)
107 return (get_dir(ip, node->depth)) ? node->right : node->left;
110 static struct rte_rib6_node *
111 node_alloc(struct rte_rib6 *rib)
113 struct rte_rib6_node *ent;
116 ret = rte_mempool_get(rib->node_pool, (void *)&ent);
117 if (unlikely(ret != 0))
124 node_free(struct rte_rib6 *rib, struct rte_rib6_node *ent)
127 rte_mempool_put(rib->node_pool, ent);
130 struct rte_rib6_node *
131 rte_rib6_lookup(struct rte_rib6 *rib,
132 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
134 struct rte_rib6_node *cur;
135 struct rte_rib6_node *prev = NULL;
137 if (unlikely(rib == NULL)) {
143 while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
144 if (is_valid_node(cur))
146 cur = get_nxt_node(cur, ip);
151 struct rte_rib6_node *
152 rte_rib6_lookup_parent(struct rte_rib6_node *ent)
154 struct rte_rib6_node *tmp;
160 while ((tmp != NULL) && (!is_valid_node(tmp)))
166 struct rte_rib6_node *
167 rte_rib6_lookup_exact(struct rte_rib6 *rib,
168 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
170 struct rte_rib6_node *cur;
171 uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
174 if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
180 for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
181 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
183 while (cur != NULL) {
184 if (rte_rib6_is_equal(cur->ip, tmp_ip) &&
185 (cur->depth == depth) &&
189 if (!(is_covered(tmp_ip, cur->ip, cur->depth)) ||
190 (cur->depth >= depth))
193 cur = get_nxt_node(cur, tmp_ip);
200 * Traverses on subtree and retrieves more specific routes
201 * for a given in args ip/depth prefix
202 * last = NULL means the first invocation
204 struct rte_rib6_node *
205 rte_rib6_get_nxt(struct rte_rib6 *rib,
206 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE],
207 uint8_t depth, struct rte_rib6_node *last, int flag)
209 struct rte_rib6_node *tmp, *prev = NULL;
210 uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
213 if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
218 for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
219 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
223 while ((tmp) && (tmp->depth < depth))
224 tmp = get_nxt_node(tmp, tmp_ip);
227 while ((tmp->parent != NULL) && (is_right_node(tmp) ||
228 (tmp->parent->right == NULL))) {
230 if (is_valid_node(tmp) &&
231 (is_covered(tmp->ip, tmp_ip, depth) &&
232 (tmp->depth > depth)))
235 tmp = (tmp->parent != NULL) ? tmp->parent->right : NULL;
238 if (is_valid_node(tmp) &&
239 (is_covered(tmp->ip, tmp_ip, depth) &&
240 (tmp->depth > depth))) {
242 if (flag == RTE_RIB6_GET_NXT_COVER)
245 tmp = (tmp->left != NULL) ? tmp->left : tmp->right;
251 rte_rib6_remove(struct rte_rib6 *rib,
252 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
254 struct rte_rib6_node *cur, *prev, *child;
256 cur = rte_rib6_lookup_exact(rib, ip, depth);
261 cur->flag &= ~RTE_RIB_VALID_NODE;
262 while (!is_valid_node(cur)) {
263 if ((cur->left != NULL) && (cur->right != NULL))
265 child = (cur->left == NULL) ? cur->right : cur->left;
267 child->parent = cur->parent;
268 if (cur->parent == NULL) {
273 if (cur->parent->left == cur)
274 cur->parent->left = child;
276 cur->parent->right = child;
279 node_free(rib, prev);
283 struct rte_rib6_node *
284 rte_rib6_insert(struct rte_rib6 *rib,
285 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
287 struct rte_rib6_node **tmp;
288 struct rte_rib6_node *prev = NULL;
289 struct rte_rib6_node *new_node = NULL;
290 struct rte_rib6_node *common_node = NULL;
291 uint8_t common_prefix[RTE_RIB6_IPV6_ADDR_SIZE];
292 uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
294 uint8_t common_depth, ip_xor;
296 if (unlikely((rib == NULL) || (ip == NULL) ||
297 (depth > RIB6_MAXDEPTH))) {
304 for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
305 tmp_ip[i] = ip[i] & get_msk_part(depth, i);
307 new_node = rte_rib6_lookup_exact(rib, tmp_ip, depth);
308 if (new_node != NULL) {
313 new_node = node_alloc(rib);
314 if (new_node == NULL) {
318 new_node->left = NULL;
319 new_node->right = NULL;
320 new_node->parent = NULL;
321 rte_rib6_copy_addr(new_node->ip, tmp_ip);
322 new_node->depth = depth;
323 new_node->flag = RTE_RIB_VALID_NODE;
325 /* traverse down the tree to find matching node or closest matching */
327 /* insert as the last node in the branch */
330 new_node->parent = prev;
335 * Intermediate node found.
336 * Previous rte_rib6_lookup_exact() returned NULL
337 * but node with proper search criteria is found.
338 * Validate intermediate node and return.
340 if (rte_rib6_is_equal(tmp_ip, (*tmp)->ip) &&
341 (depth == (*tmp)->depth)) {
342 node_free(rib, new_node);
343 (*tmp)->flag |= RTE_RIB_VALID_NODE;
348 if (!is_covered(tmp_ip, (*tmp)->ip, (*tmp)->depth) ||
349 ((*tmp)->depth >= depth)) {
354 tmp = (get_dir(tmp_ip, (*tmp)->depth)) ? &(*tmp)->right :
358 /* closest node found, new_node should be inserted in the middle */
359 common_depth = RTE_MIN(depth, (*tmp)->depth);
360 for (i = 0, d = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) {
361 ip_xor = tmp_ip[i] ^ (*tmp)->ip[i];
365 d += __builtin_clz(ip_xor << 24);
370 common_depth = RTE_MIN(d, common_depth);
372 for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
373 common_prefix[i] = tmp_ip[i] & get_msk_part(common_depth, i);
375 if (rte_rib6_is_equal(common_prefix, tmp_ip) &&
376 (common_depth == depth)) {
377 /* insert as a parent */
378 if (get_dir((*tmp)->ip, depth))
379 new_node->right = *tmp;
381 new_node->left = *tmp;
382 new_node->parent = (*tmp)->parent;
383 (*tmp)->parent = new_node;
386 /* create intermediate node */
387 common_node = node_alloc(rib);
388 if (common_node == NULL) {
389 node_free(rib, new_node);
393 rte_rib6_copy_addr(common_node->ip, common_prefix);
394 common_node->depth = common_depth;
395 common_node->flag = 0;
396 common_node->parent = (*tmp)->parent;
397 new_node->parent = common_node;
398 (*tmp)->parent = common_node;
399 if (get_dir((*tmp)->ip, common_depth) == 1) {
400 common_node->left = new_node;
401 common_node->right = *tmp;
403 common_node->left = *tmp;
404 common_node->right = new_node;
413 rte_rib6_get_ip(const struct rte_rib6_node *node,
414 uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
416 if ((node == NULL) || (ip == NULL)) {
420 rte_rib6_copy_addr(ip, node->ip);
425 rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
427 if ((node == NULL) || (depth == NULL)) {
431 *depth = node->depth;
436 rte_rib6_get_ext(struct rte_rib6_node *node)
438 return (node == NULL) ? NULL : &node->ext[0];
442 rte_rib6_get_nh(const struct rte_rib6_node *node, uint64_t *nh)
444 if ((node == NULL) || (nh == NULL)) {
453 rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh)
464 rte_rib6_create(const char *name, int socket_id,
465 const struct rte_rib6_conf *conf)
467 char mem_name[RTE_RIB6_NAMESIZE];
468 struct rte_rib6 *rib = NULL;
469 struct rte_tailq_entry *te;
470 struct rte_rib6_list *rib6_list;
471 struct rte_mempool *node_pool;
473 /* Check user arguments. */
474 if (name == NULL || conf == NULL || conf->max_nodes <= 0) {
479 snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
480 node_pool = rte_mempool_create(mem_name, conf->max_nodes,
481 sizeof(struct rte_rib6_node) + conf->ext_sz, 0, 0,
482 NULL, NULL, NULL, NULL, socket_id, 0);
484 if (node_pool == NULL) {
486 "Can not allocate mempool for RIB6 %s\n", name);
490 snprintf(mem_name, sizeof(mem_name), "RIB6_%s", name);
491 rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
493 rte_mcfg_tailq_write_lock();
495 /* guarantee there's no existing */
496 TAILQ_FOREACH(te, rib6_list, next) {
497 rib = (struct rte_rib6 *)te->data;
498 if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
507 /* allocate tailq entry */
508 te = rte_zmalloc("RIB6_TAILQ_ENTRY", sizeof(*te), 0);
511 "Can not allocate tailq entry for RIB6 %s\n", name);
516 /* Allocate memory to store the RIB6 data structures. */
517 rib = rte_zmalloc_socket(mem_name,
518 sizeof(struct rte_rib6), RTE_CACHE_LINE_SIZE, socket_id);
520 RTE_LOG(ERR, LPM, "RIB6 %s memory allocation failed\n", name);
525 rte_strlcpy(rib->name, name, sizeof(rib->name));
527 rib->max_nodes = conf->max_nodes;
528 rib->node_pool = node_pool;
530 te->data = (void *)rib;
531 TAILQ_INSERT_TAIL(rib6_list, te, next);
533 rte_mcfg_tailq_write_unlock();
540 rte_mcfg_tailq_write_unlock();
541 rte_mempool_free(node_pool);
547 rte_rib6_find_existing(const char *name)
549 struct rte_rib6 *rib = NULL;
550 struct rte_tailq_entry *te;
551 struct rte_rib6_list *rib6_list;
553 if (unlikely(name == NULL)) {
558 rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
560 rte_mcfg_tailq_read_lock();
561 TAILQ_FOREACH(te, rib6_list, next) {
562 rib = (struct rte_rib6 *) te->data;
563 if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
566 rte_mcfg_tailq_read_unlock();
577 rte_rib6_free(struct rte_rib6 *rib)
579 struct rte_tailq_entry *te;
580 struct rte_rib6_list *rib6_list;
581 struct rte_rib6_node *tmp = NULL;
583 if (unlikely(rib == NULL)) {
588 rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
590 rte_mcfg_tailq_write_lock();
592 /* find our tailq entry */
593 TAILQ_FOREACH(te, rib6_list, next) {
594 if (te->data == (void *)rib)
598 TAILQ_REMOVE(rib6_list, te, next);
600 rte_mcfg_tailq_write_unlock();
602 while ((tmp = rte_rib6_get_nxt(rib, 0, 0, tmp,
603 RTE_RIB6_GET_NXT_ALL)) != NULL)
604 rte_rib6_remove(rib, tmp->ip, tmp->depth);
606 rte_mempool_free(rib->node_pool);