xref: /dpdk/lib/rib/rte_rib6.c (revision bbbac4cd) 
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
3  * Copyright(c) 2019 Intel Corporation
4  */
5 
6 #include <stdbool.h>
7 #include <stdint.h>
8 
9 #include <rte_eal.h>
10 #include <rte_eal_memconfig.h>
11 #include <rte_errno.h>
12 #include <rte_malloc.h>
13 #include <rte_mempool.h>
14 #include <rte_rwlock.h>
15 #include <rte_string_fns.h>
16 #include <rte_tailq.h>
17 
18 #include <rte_rib6.h>
19 
20 #define RTE_RIB_VALID_NODE	1
21 #define RIB6_MAXDEPTH		128
22 /* Maximum length of a RIB6 name. */
23 #define RTE_RIB6_NAMESIZE	64
24 
25 TAILQ_HEAD(rte_rib6_list, rte_tailq_entry);
26 static struct rte_tailq_elem rte_rib6_tailq = {
27 	.name = "RTE_RIB6",
28 };
29 EAL_REGISTER_TAILQ(rte_rib6_tailq)
30 
31 struct rte_rib6_node {
32 	struct rte_rib6_node	*left;
33 	struct rte_rib6_node	*right;
34 	struct rte_rib6_node	*parent;
35 	uint64_t		nh;
36 	uint8_t			ip[RTE_RIB6_IPV6_ADDR_SIZE];
37 	uint8_t			depth;
38 	uint8_t			flag;
39 	__extension__ uint64_t		ext[0];
40 };
41 
42 struct rte_rib6 {
43 	char		name[RTE_RIB6_NAMESIZE];
44 	struct rte_rib6_node	*tree;
45 	struct rte_mempool	*node_pool;
46 	uint32_t		cur_nodes;
47 	uint32_t		cur_routes;
48 	int			max_nodes;
49 };
50 
51 static inline bool
52 is_valid_node(struct rte_rib6_node *node)
53 {
54 	return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;
55 }
56 
57 static inline bool
58 is_right_node(struct rte_rib6_node *node)
59 {
60 	return node->parent->right == node;
61 }
62 
63 /*
64  * Check if ip1 is covered by ip2/depth prefix
65  */
66 static inline bool
67 is_covered(const uint8_t ip1[RTE_RIB6_IPV6_ADDR_SIZE],
68 		const uint8_t ip2[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
69 {
70 	int i;
71 
72 	for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
73 		if ((ip1[i] ^ ip2[i]) & get_msk_part(depth, i))
74 			return false;
75 
76 	return true;
77 }
78 
79 static inline int
80 get_dir(const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
81 {
82 	uint8_t index, msk;
83 
84 	/*
85 	 * depth & 127 clamps depth to values that will not
86 	 * read off the end of ip.
87 	 * depth is the number of bits deep into ip to traverse, and
88 	 * is incremented in blocks of 8 (1 byte). This means the last
89 	 * 3 bits are irrelevant to what the index of ip should be.
90 	 */
91 	index = (depth & INT8_MAX) / CHAR_BIT;
92 
93 	/*
94 	 * msk is the bitmask used to extract the bit used to decide the
95 	 * direction of the next step of the binary search.
96 	 */
97 	msk = 1 << (7 - (depth & 7));
98 
99 	return (ip[index] & msk) != 0;
100 }
101 
102 static inline struct rte_rib6_node *
103 get_nxt_node(struct rte_rib6_node *node,
104 	const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
105 {
106 	if (node->depth == RIB6_MAXDEPTH)
107 		return NULL;
108 
109 	return (get_dir(ip, node->depth)) ? node->right : node->left;
110 }
111 
112 static struct rte_rib6_node *
113 node_alloc(struct rte_rib6 *rib)
114 {
115 	struct rte_rib6_node *ent;
116 	int ret;
117 
118 	ret = rte_mempool_get(rib->node_pool, (void *)&ent);
119 	if (unlikely(ret != 0))
120 		return NULL;
121 	++rib->cur_nodes;
122 	return ent;
123 }
124 
125 static void
126 node_free(struct rte_rib6 *rib, struct rte_rib6_node *ent)
127 {
128 	--rib->cur_nodes;
129 	rte_mempool_put(rib->node_pool, ent);
130 }
131 
132 struct rte_rib6_node *
133 rte_rib6_lookup(struct rte_rib6 *rib,
134 	const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
135 {
136 	struct rte_rib6_node *cur;
137 	struct rte_rib6_node *prev = NULL;
138 
139 	if (unlikely(rib == NULL)) {
140 		rte_errno = EINVAL;
141 		return NULL;
142 	}
143 	cur = rib->tree;
144 
145 	while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {
146 		if (is_valid_node(cur))
147 			prev = cur;
148 		cur = get_nxt_node(cur, ip);
149 	}
150 	return prev;
151 }
152 
153 struct rte_rib6_node *
154 rte_rib6_lookup_parent(struct rte_rib6_node *ent)
155 {
156 	struct rte_rib6_node *tmp;
157 
158 	if (ent == NULL)
159 		return NULL;
160 
161 	tmp = ent->parent;
162 	while ((tmp != NULL) && (!is_valid_node(tmp)))
163 		tmp = tmp->parent;
164 
165 	return tmp;
166 }
167 
168 struct rte_rib6_node *
169 rte_rib6_lookup_exact(struct rte_rib6 *rib,
170 	const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
171 {
172 	struct rte_rib6_node *cur;
173 	uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
174 	int i;
175 
176 	if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
177 		rte_errno = EINVAL;
178 		return NULL;
179 	}
180 	cur = rib->tree;
181 
182 	for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
183 		tmp_ip[i] = ip[i] & get_msk_part(depth, i);
184 
185 	while (cur != NULL) {
186 		if (rte_rib6_is_equal(cur->ip, tmp_ip) &&
187 				(cur->depth == depth) &&
188 				is_valid_node(cur))
189 			return cur;
190 
191 		if (!(is_covered(tmp_ip, cur->ip, cur->depth)) ||
192 				(cur->depth >= depth))
193 			break;
194 
195 		cur = get_nxt_node(cur, tmp_ip);
196 	}
197 
198 	return NULL;
199 }
200 
201 /*
202  *  Traverses on subtree and retreeves more specific routes
203  *  for a given in args ip/depth prefix
204  *  last = NULL means the first invocation
205  */
206 struct rte_rib6_node *
207 rte_rib6_get_nxt(struct rte_rib6 *rib,
208 	const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE],
209 	uint8_t depth, struct rte_rib6_node *last, int flag)
210 {
211 	struct rte_rib6_node *tmp, *prev = NULL;
212 	uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
213 	int i;
214 
215 	if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) {
216 		rte_errno = EINVAL;
217 		return NULL;
218 	}
219 
220 	for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
221 		tmp_ip[i] = ip[i] & get_msk_part(depth, i);
222 
223 	if (last == NULL) {
224 		tmp = rib->tree;
225 		while ((tmp) && (tmp->depth < depth))
226 			tmp = get_nxt_node(tmp, tmp_ip);
227 	} else {
228 		tmp = last;
229 		while ((tmp->parent != NULL) && (is_right_node(tmp) ||
230 				(tmp->parent->right == NULL))) {
231 			tmp = tmp->parent;
232 			if (is_valid_node(tmp) &&
233 					(is_covered(tmp->ip, tmp_ip, depth) &&
234 					(tmp->depth > depth)))
235 				return tmp;
236 		}
237 		tmp = (tmp->parent != NULL) ? tmp->parent->right : NULL;
238 	}
239 	while (tmp) {
240 		if (is_valid_node(tmp) &&
241 				(is_covered(tmp->ip, tmp_ip, depth) &&
242 				(tmp->depth > depth))) {
243 			prev = tmp;
244 			if (flag == RTE_RIB6_GET_NXT_COVER)
245 				return prev;
246 		}
247 		tmp = (tmp->left != NULL) ? tmp->left : tmp->right;
248 	}
249 	return prev;
250 }
251 
252 void
253 rte_rib6_remove(struct rte_rib6 *rib,
254 	const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
255 {
256 	struct rte_rib6_node *cur, *prev, *child;
257 
258 	cur = rte_rib6_lookup_exact(rib, ip, depth);
259 	if (cur == NULL)
260 		return;
261 
262 	--rib->cur_routes;
263 	cur->flag &= ~RTE_RIB_VALID_NODE;
264 	while (!is_valid_node(cur)) {
265 		if ((cur->left != NULL) && (cur->right != NULL))
266 			return;
267 		child = (cur->left == NULL) ? cur->right : cur->left;
268 		if (child != NULL)
269 			child->parent = cur->parent;
270 		if (cur->parent == NULL) {
271 			rib->tree = child;
272 			node_free(rib, cur);
273 			return;
274 		}
275 		if (cur->parent->left == cur)
276 			cur->parent->left = child;
277 		else
278 			cur->parent->right = child;
279 		prev = cur;
280 		cur = cur->parent;
281 		node_free(rib, prev);
282 	}
283 }
284 
285 struct rte_rib6_node *
286 rte_rib6_insert(struct rte_rib6 *rib,
287 	const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth)
288 {
289 	struct rte_rib6_node **tmp;
290 	struct rte_rib6_node *prev = NULL;
291 	struct rte_rib6_node *new_node = NULL;
292 	struct rte_rib6_node *common_node = NULL;
293 	uint8_t common_prefix[RTE_RIB6_IPV6_ADDR_SIZE];
294 	uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE];
295 	int i, d;
296 	uint8_t common_depth, ip_xor;
297 
298 	if (unlikely((rib == NULL) || (ip == NULL) ||
299 			(depth > RIB6_MAXDEPTH))) {
300 		rte_errno = EINVAL;
301 		return NULL;
302 	}
303 
304 	tmp = &rib->tree;
305 
306 	for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
307 		tmp_ip[i] = ip[i] & get_msk_part(depth, i);
308 
309 	new_node = rte_rib6_lookup_exact(rib, tmp_ip, depth);
310 	if (new_node != NULL) {
311 		rte_errno = EEXIST;
312 		return NULL;
313 	}
314 
315 	new_node = node_alloc(rib);
316 	if (new_node == NULL) {
317 		rte_errno = ENOMEM;
318 		return NULL;
319 	}
320 	new_node->left = NULL;
321 	new_node->right = NULL;
322 	new_node->parent = NULL;
323 	rte_rib6_copy_addr(new_node->ip, tmp_ip);
324 	new_node->depth = depth;
325 	new_node->flag = RTE_RIB_VALID_NODE;
326 
327 	/* traverse down the tree to find matching node or closest matching */
328 	while (1) {
329 		/* insert as the last node in the branch */
330 		if (*tmp == NULL) {
331 			*tmp = new_node;
332 			new_node->parent = prev;
333 			++rib->cur_routes;
334 			return *tmp;
335 		}
336 		/*
337 		 * Intermediate node found.
338 		 * Previous rte_rib6_lookup_exact() returned NULL
339 		 * but node with proper search criteria is found.
340 		 * Validate intermediate node and return.
341 		 */
342 		if (rte_rib6_is_equal(tmp_ip, (*tmp)->ip) &&
343 				(depth == (*tmp)->depth)) {
344 			node_free(rib, new_node);
345 			(*tmp)->flag |= RTE_RIB_VALID_NODE;
346 			++rib->cur_routes;
347 			return *tmp;
348 		}
349 
350 		if (!is_covered(tmp_ip, (*tmp)->ip, (*tmp)->depth) ||
351 				((*tmp)->depth >= depth)) {
352 			break;
353 		}
354 		prev = *tmp;
355 
356 		tmp = (get_dir(tmp_ip, (*tmp)->depth)) ? &(*tmp)->right :
357 				&(*tmp)->left;
358 	}
359 
360 	/* closest node found, new_node should be inserted in the middle */
361 	common_depth = RTE_MIN(depth, (*tmp)->depth);
362 	for (i = 0, d = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) {
363 		ip_xor = tmp_ip[i] ^ (*tmp)->ip[i];
364 		if (ip_xor == 0)
365 			d += 8;
366 		else {
367 			d += __builtin_clz(ip_xor << 24);
368 			break;
369 		}
370 	}
371 
372 	common_depth = RTE_MIN(d, common_depth);
373 
374 	for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++)
375 		common_prefix[i] = tmp_ip[i] & get_msk_part(common_depth, i);
376 
377 	if (rte_rib6_is_equal(common_prefix, tmp_ip) &&
378 			(common_depth == depth)) {
379 		/* insert as a parent */
380 		if (get_dir((*tmp)->ip, depth))
381 			new_node->right = *tmp;
382 		else
383 			new_node->left = *tmp;
384 		new_node->parent = (*tmp)->parent;
385 		(*tmp)->parent = new_node;
386 		*tmp = new_node;
387 	} else {
388 		/* create intermediate node */
389 		common_node = node_alloc(rib);
390 		if (common_node == NULL) {
391 			node_free(rib, new_node);
392 			rte_errno = ENOMEM;
393 			return NULL;
394 		}
395 		rte_rib6_copy_addr(common_node->ip, common_prefix);
396 		common_node->depth = common_depth;
397 		common_node->flag = 0;
398 		common_node->parent = (*tmp)->parent;
399 		new_node->parent = common_node;
400 		(*tmp)->parent = common_node;
401 		if (get_dir((*tmp)->ip, common_depth) == 1) {
402 			common_node->left = new_node;
403 			common_node->right = *tmp;
404 		} else {
405 			common_node->left = *tmp;
406 			common_node->right = new_node;
407 		}
408 		*tmp = common_node;
409 	}
410 	++rib->cur_routes;
411 	return new_node;
412 }
413 
414 int
415 rte_rib6_get_ip(const struct rte_rib6_node *node,
416 		uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE])
417 {
418 	if ((node == NULL) || (ip == NULL)) {
419 		rte_errno = EINVAL;
420 		return -1;
421 	}
422 	rte_rib6_copy_addr(ip, node->ip);
423 	return 0;
424 }
425 
426 int
427 rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
428 {
429 	if ((node == NULL) || (depth == NULL)) {
430 		rte_errno = EINVAL;
431 		return -1;
432 	}
433 	*depth = node->depth;
434 	return 0;
435 }
436 
437 void *
438 rte_rib6_get_ext(struct rte_rib6_node *node)
439 {
440 	return (node == NULL) ? NULL : &node->ext[0];
441 }
442 
443 int
444 rte_rib6_get_nh(const struct rte_rib6_node *node, uint64_t *nh)
445 {
446 	if ((node == NULL) || (nh == NULL)) {
447 		rte_errno = EINVAL;
448 		return -1;
449 	}
450 	*nh = node->nh;
451 	return 0;
452 }
453 
454 int
455 rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh)
456 {
457 	if (node == NULL) {
458 		rte_errno = EINVAL;
459 		return -1;
460 	}
461 	node->nh = nh;
462 	return 0;
463 }
464 
465 struct rte_rib6 *
466 rte_rib6_create(const char *name, int socket_id,
467 		const struct rte_rib6_conf *conf)
468 {
469 	char mem_name[RTE_RIB6_NAMESIZE];
470 	struct rte_rib6 *rib = NULL;
471 	struct rte_tailq_entry *te;
472 	struct rte_rib6_list *rib6_list;
473 	struct rte_mempool *node_pool;
474 
475 	/* Check user arguments. */
476 	if (name == NULL || conf == NULL || conf->max_nodes <= 0) {
477 		rte_errno = EINVAL;
478 		return NULL;
479 	}
480 
481 	snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
482 	node_pool = rte_mempool_create(mem_name, conf->max_nodes,
483 		sizeof(struct rte_rib6_node) + conf->ext_sz, 0, 0,
484 		NULL, NULL, NULL, NULL, socket_id, 0);
485 
486 	if (node_pool == NULL) {
487 		RTE_LOG(ERR, LPM,
488 			"Can not allocate mempool for RIB6 %s\n", name);
489 		return NULL;
490 	}
491 
492 	snprintf(mem_name, sizeof(mem_name), "RIB6_%s", name);
493 	rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
494 
495 	rte_mcfg_tailq_write_lock();
496 
497 	/* guarantee there's no existing */
498 	TAILQ_FOREACH(te, rib6_list, next) {
499 		rib = (struct rte_rib6 *)te->data;
500 		if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
501 			break;
502 	}
503 	rib = NULL;
504 	if (te != NULL) {
505 		rte_errno = EEXIST;
506 		goto exit;
507 	}
508 
509 	/* allocate tailq entry */
510 	te = rte_zmalloc("RIB6_TAILQ_ENTRY", sizeof(*te), 0);
511 	if (te == NULL) {
512 		RTE_LOG(ERR, LPM,
513 			"Can not allocate tailq entry for RIB6 %s\n", name);
514 		rte_errno = ENOMEM;
515 		goto exit;
516 	}
517 
518 	/* Allocate memory to store the RIB6 data structures. */
519 	rib = rte_zmalloc_socket(mem_name,
520 		sizeof(struct rte_rib6), RTE_CACHE_LINE_SIZE, socket_id);
521 	if (rib == NULL) {
522 		RTE_LOG(ERR, LPM, "RIB6 %s memory allocation failed\n", name);
523 		rte_errno = ENOMEM;
524 		goto free_te;
525 	}
526 
527 	rte_strlcpy(rib->name, name, sizeof(rib->name));
528 	rib->tree = NULL;
529 	rib->max_nodes = conf->max_nodes;
530 	rib->node_pool = node_pool;
531 
532 	te->data = (void *)rib;
533 	TAILQ_INSERT_TAIL(rib6_list, te, next);
534 
535 	rte_mcfg_tailq_write_unlock();
536 
537 	return rib;
538 
539 free_te:
540 	rte_free(te);
541 exit:
542 	rte_mcfg_tailq_write_unlock();
543 	rte_mempool_free(node_pool);
544 
545 	return NULL;
546 }
547 
548 struct rte_rib6 *
549 rte_rib6_find_existing(const char *name)
550 {
551 	struct rte_rib6 *rib = NULL;
552 	struct rte_tailq_entry *te;
553 	struct rte_rib6_list *rib6_list;
554 
555 	if (unlikely(name == NULL)) {
556 		rte_errno = EINVAL;
557 		return NULL;
558 	}
559 
560 	rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
561 
562 	rte_mcfg_tailq_read_lock();
563 	TAILQ_FOREACH(te, rib6_list, next) {
564 		rib = (struct rte_rib6 *) te->data;
565 		if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0)
566 			break;
567 	}
568 	rte_mcfg_tailq_read_unlock();
569 
570 	if (te == NULL) {
571 		rte_errno = ENOENT;
572 		return NULL;
573 	}
574 
575 	return rib;
576 }
577 
578 void
579 rte_rib6_free(struct rte_rib6 *rib)
580 {
581 	struct rte_tailq_entry *te;
582 	struct rte_rib6_list *rib6_list;
583 	struct rte_rib6_node *tmp = NULL;
584 
585 	if (unlikely(rib == NULL)) {
586 		rte_errno = EINVAL;
587 		return;
588 	}
589 
590 	rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list);
591 
592 	rte_mcfg_tailq_write_lock();
593 
594 	/* find our tailq entry */
595 	TAILQ_FOREACH(te, rib6_list, next) {
596 		if (te->data == (void *)rib)
597 			break;
598 	}
599 	if (te != NULL)
600 		TAILQ_REMOVE(rib6_list, te, next);
601 
602 	rte_mcfg_tailq_write_unlock();
603 
604 	while ((tmp = rte_rib6_get_nxt(rib, 0, 0, tmp,
605 			RTE_RIB6_GET_NXT_ALL)) != NULL)
606 		rte_rib6_remove(rib, tmp->ip, tmp->depth);
607 
608 	rte_mempool_free(rib->node_pool);
609 
610 	rte_free(rib);
611 	rte_free(te);
612 }
613