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 TAILQ_HEAD(rte_rib_list, rte_tailq_entry);
19 static struct rte_tailq_elem rte_rib_tailq = {
22 EAL_REGISTER_TAILQ(rte_rib_tailq)
24 #define RTE_RIB_VALID_NODE 1
25 /* Maximum depth value possible for IPv4 RIB. */
26 #define RIB_MAXDEPTH 32
27 /* Maximum length of a RIB name. */
28 #define RTE_RIB_NAMESIZE 64
31 struct rte_rib_node *left;
32 struct rte_rib_node *right;
33 struct rte_rib_node *parent;
38 __extension__ uint64_t ext[0];
42 char name[RTE_RIB_NAMESIZE];
43 struct rte_rib_node *tree;
44 struct rte_mempool *node_pool;
51 is_valid_node(struct rte_rib_node *node)
53 return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
57 is_right_node(struct rte_rib_node *node)
59 return node->parent->right == node;
63 * Check if ip1 is covered by ip2/depth prefix
66 is_covered(uint32_t ip1, uint32_t ip2, uint8_t depth)
68 return ((ip1 ^ ip2) & rte_rib_depth_to_mask(depth)) == 0;
71 static inline struct rte_rib_node *
72 get_nxt_node(struct rte_rib_node *node, uint32_t ip)
74 return (ip & (1 << (31 - node->depth))) ? node->right : node->left;
77 static struct rte_rib_node *
78 node_alloc(struct rte_rib *rib)
80 struct rte_rib_node *ent;
83 ret = rte_mempool_get(rib->node_pool, (void *)&ent);
84 if (unlikely(ret != 0))
91 node_free(struct rte_rib *rib, struct rte_rib_node *ent)
94 rte_mempool_put(rib->node_pool, ent);
98 rte_rib_lookup(struct rte_rib *rib, uint32_t ip)
100 struct rte_rib_node *cur, *prev = NULL;
108 while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
109 if (is_valid_node(cur))
111 cur = get_nxt_node(cur, ip);
116 struct rte_rib_node *
117 rte_rib_lookup_parent(struct rte_rib_node *ent)
119 struct rte_rib_node *tmp;
124 while ((tmp != NULL) && !is_valid_node(tmp))
129 static struct rte_rib_node *
130 __rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)
132 struct rte_rib_node *cur;
135 while (cur != NULL) {
136 if ((cur->ip == ip) && (cur->depth == depth) &&
139 if ((cur->depth > depth) ||
140 !is_covered(ip, cur->ip, cur->depth))
142 cur = get_nxt_node(cur, ip);
147 struct rte_rib_node *
148 rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)
150 if ((rib == NULL) || (depth > RIB_MAXDEPTH)) {
154 ip &= rte_rib_depth_to_mask(depth);
156 return __rib_lookup_exact(rib, ip, depth);
160 * Traverses on subtree and retrieves more specific routes
161 * for a given in args ip/depth prefix
162 * last = NULL means the first invocation
164 struct rte_rib_node *
165 rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip,
166 uint8_t depth, struct rte_rib_node *last, int flag)
168 struct rte_rib_node *tmp, *prev = NULL;
170 if ((rib == NULL) || (depth > RIB_MAXDEPTH)) {
177 while ((tmp) && (tmp->depth < depth))
178 tmp = get_nxt_node(tmp, ip);
181 while ((tmp->parent != NULL) && (is_right_node(tmp) ||
182 (tmp->parent->right == NULL))) {
184 if (is_valid_node(tmp) &&
185 (is_covered(tmp->ip, ip, depth) &&
186 (tmp->depth > depth)))
189 tmp = (tmp->parent) ? tmp->parent->right : NULL;
192 if (is_valid_node(tmp) &&
193 (is_covered(tmp->ip, ip, depth) &&
194 (tmp->depth > depth))) {
196 if (flag == RTE_RIB_GET_NXT_COVER)
199 tmp = (tmp->left) ? tmp->left : tmp->right;
205 rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth)
207 struct rte_rib_node *cur, *prev, *child;
209 cur = rte_rib_lookup_exact(rib, ip, depth);
214 cur->flag &= ~RTE_RIB_VALID_NODE;
215 while (!is_valid_node(cur)) {
216 if ((cur->left != NULL) && (cur->right != NULL))
218 child = (cur->left == NULL) ? cur->right : cur->left;
220 child->parent = cur->parent;
221 if (cur->parent == NULL) {
226 if (cur->parent->left == cur)
227 cur->parent->left = child;
229 cur->parent->right = child;
232 node_free(rib, prev);
236 struct rte_rib_node *
237 rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
239 struct rte_rib_node **tmp;
240 struct rte_rib_node *prev = NULL;
241 struct rte_rib_node *new_node = NULL;
242 struct rte_rib_node *common_node = NULL;
244 uint32_t common_prefix;
245 uint8_t common_depth;
247 if ((rib == NULL) || (depth > RIB_MAXDEPTH)) {
253 ip &= rte_rib_depth_to_mask(depth);
254 new_node = __rib_lookup_exact(rib, ip, depth);
255 if (new_node != NULL) {
260 new_node = node_alloc(rib);
261 if (new_node == NULL) {
265 new_node->left = NULL;
266 new_node->right = NULL;
267 new_node->parent = NULL;
269 new_node->depth = depth;
270 new_node->flag = RTE_RIB_VALID_NODE;
272 /* traverse down the tree to find matching node or closest matching */
274 /* insert as the last node in the branch */
277 new_node->parent = prev;
282 * Intermediate node found.
283 * Previous rte_rib_lookup_exact() returned NULL
284 * but node with proper search criteria is found.
285 * Validate intermediate node and return.
287 if ((ip == (*tmp)->ip) && (depth == (*tmp)->depth)) {
288 node_free(rib, new_node);
289 (*tmp)->flag |= RTE_RIB_VALID_NODE;
294 if ((d >= depth) || !is_covered(ip, (*tmp)->ip, d))
297 tmp = (ip & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
299 /* closest node found, new_node should be inserted in the middle */
300 common_depth = RTE_MIN(depth, (*tmp)->depth);
301 common_prefix = ip ^ (*tmp)->ip;
302 d = (common_prefix == 0) ? 32 : __builtin_clz(common_prefix);
304 common_depth = RTE_MIN(d, common_depth);
305 common_prefix = ip & rte_rib_depth_to_mask(common_depth);
306 if ((common_prefix == ip) && (common_depth == depth)) {
307 /* insert as a parent */
308 if ((*tmp)->ip & (1 << (31 - depth)))
309 new_node->right = *tmp;
311 new_node->left = *tmp;
312 new_node->parent = (*tmp)->parent;
313 (*tmp)->parent = new_node;
316 /* create intermediate node */
317 common_node = node_alloc(rib);
318 if (common_node == NULL) {
319 node_free(rib, new_node);
323 common_node->ip = common_prefix;
324 common_node->depth = common_depth;
325 common_node->flag = 0;
326 common_node->parent = (*tmp)->parent;
327 new_node->parent = common_node;
328 (*tmp)->parent = common_node;
329 if ((new_node->ip & (1 << (31 - common_depth))) == 0) {
330 common_node->left = new_node;
331 common_node->right = *tmp;
333 common_node->left = *tmp;
334 common_node->right = new_node;
343 rte_rib_get_ip(const struct rte_rib_node *node, uint32_t *ip)
345 if ((node == NULL) || (ip == NULL)) {
354 rte_rib_get_depth(const struct rte_rib_node *node, uint8_t *depth)
356 if ((node == NULL) || (depth == NULL)) {
360 *depth = node->depth;
365 rte_rib_get_ext(struct rte_rib_node *node)
367 return (node == NULL) ? NULL : &node->ext[0];
371 rte_rib_get_nh(const struct rte_rib_node *node, uint64_t *nh)
373 if ((node == NULL) || (nh == NULL)) {
382 rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh)
393 rte_rib_create(const char *name, int socket_id, const struct rte_rib_conf *conf)
395 char mem_name[RTE_RIB_NAMESIZE];
396 struct rte_rib *rib = NULL;
397 struct rte_tailq_entry *te;
398 struct rte_rib_list *rib_list;
399 struct rte_mempool *node_pool;
401 /* Check user arguments. */
402 if (name == NULL || conf == NULL || conf->max_nodes <= 0) {
407 snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
408 node_pool = rte_mempool_create(mem_name, conf->max_nodes,
409 sizeof(struct rte_rib_node) + conf->ext_sz, 0, 0,
410 NULL, NULL, NULL, NULL, socket_id, 0);
412 if (node_pool == NULL) {
414 "Can not allocate mempool for RIB %s\n", name);
418 snprintf(mem_name, sizeof(mem_name), "RIB_%s", name);
419 rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
421 rte_mcfg_tailq_write_lock();
423 /* guarantee there's no existing */
424 TAILQ_FOREACH(te, rib_list, next) {
425 rib = (struct rte_rib *)te->data;
426 if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
435 /* allocate tailq entry */
436 te = rte_zmalloc("RIB_TAILQ_ENTRY", sizeof(*te), 0);
439 "Can not allocate tailq entry for RIB %s\n", name);
444 /* Allocate memory to store the RIB data structures. */
445 rib = rte_zmalloc_socket(mem_name,
446 sizeof(struct rte_rib), RTE_CACHE_LINE_SIZE, socket_id);
448 RTE_LOG(ERR, LPM, "RIB %s memory allocation failed\n", name);
453 rte_strlcpy(rib->name, name, sizeof(rib->name));
455 rib->max_nodes = conf->max_nodes;
456 rib->node_pool = node_pool;
457 te->data = (void *)rib;
458 TAILQ_INSERT_TAIL(rib_list, te, next);
460 rte_mcfg_tailq_write_unlock();
467 rte_mcfg_tailq_write_unlock();
468 rte_mempool_free(node_pool);
474 rte_rib_find_existing(const char *name)
476 struct rte_rib *rib = NULL;
477 struct rte_tailq_entry *te;
478 struct rte_rib_list *rib_list;
480 rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
482 rte_mcfg_tailq_read_lock();
483 TAILQ_FOREACH(te, rib_list, next) {
484 rib = (struct rte_rib *) te->data;
485 if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
488 rte_mcfg_tailq_read_unlock();
499 rte_rib_free(struct rte_rib *rib)
501 struct rte_tailq_entry *te;
502 struct rte_rib_list *rib_list;
503 struct rte_rib_node *tmp = NULL;
508 rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
510 rte_mcfg_tailq_write_lock();
512 /* find our tailq entry */
513 TAILQ_FOREACH(te, rib_list, next) {
514 if (te->data == (void *)rib)
518 TAILQ_REMOVE(rib_list, te, next);
520 rte_mcfg_tailq_write_unlock();
522 while ((tmp = rte_rib_get_nxt(rib, 0, 0, tmp,
523 RTE_RIB_GET_NXT_ALL)) != NULL)
524 rte_rib_remove(rib, tmp->ip, tmp->depth);
526 rte_mempool_free(rib->node_pool);