Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /*
3 : * Routing Table functions.
4 : * Copyright (C) 1998 Kunihiro Ishiguro
5 : */
6 :
7 : #define FRR_COMPILING_TABLE_C
8 :
9 : #include <zebra.h>
10 :
11 : #include "prefix.h"
12 : #include "table.h"
13 : #include "memory.h"
14 : #include "sockunion.h"
15 : #include "libfrr_trace.h"
16 :
17 12 : DEFINE_MTYPE_STATIC(LIB, ROUTE_TABLE, "Route table");
18 12 : DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node");
19 :
20 : static void route_table_free(struct route_table *);
21 :
22 200 : static int route_table_hash_cmp(const struct route_node *a,
23 : const struct route_node *b)
24 : {
25 200 : return prefix_cmp(&a->p, &b->p);
26 : }
27 :
28 1923 : DECLARE_HASH(rn_hash_node, struct route_node, nodehash, route_table_hash_cmp,
29 : prefix_hash_key);
30 : /*
31 : * route_table_init_with_delegate
32 : */
33 : struct route_table *
34 230 : route_table_init_with_delegate(route_table_delegate_t *delegate)
35 : {
36 230 : struct route_table *rt;
37 :
38 230 : rt = XCALLOC(MTYPE_ROUTE_TABLE, sizeof(struct route_table));
39 230 : rt->delegate = delegate;
40 230 : rn_hash_node_init(&rt->hash);
41 230 : return rt;
42 : }
43 :
44 144 : void route_table_finish(struct route_table *rt)
45 : {
46 144 : route_table_free(rt);
47 144 : }
48 :
49 : /* Allocate new route node. */
50 130 : static struct route_node *route_node_new(struct route_table *table)
51 : {
52 130 : return table->delegate->create_node(table->delegate, table);
53 : }
54 :
55 : /* Allocate new route node with prefix set. */
56 80 : static struct route_node *route_node_set(struct route_table *table,
57 : const struct prefix *prefix)
58 : {
59 80 : struct route_node *node;
60 :
61 80 : node = route_node_new(table);
62 :
63 80 : prefix_copy(&node->p, prefix);
64 80 : node->table = table;
65 :
66 80 : rn_hash_node_add(&node->table->hash, node);
67 :
68 80 : return node;
69 : }
70 :
71 : /* Free route node. */
72 106 : static void route_node_free(struct route_table *table, struct route_node *node)
73 : {
74 106 : if (table->cleanup)
75 74 : table->cleanup(table, node);
76 106 : table->delegate->destroy_node(table->delegate, table, node);
77 106 : }
78 :
79 : /* Free route table. */
80 144 : static void route_table_free(struct route_table *rt)
81 : {
82 144 : struct route_node *tmp_node;
83 144 : struct route_node *node;
84 :
85 144 : if (rt == NULL)
86 : return;
87 :
88 98 : node = rt->top;
89 :
90 : /* Bulk deletion of nodes remaining in this table. This function is not
91 : called until workers have completed their dependency on this table.
92 : A final route_unlock_node() will not be called for these nodes. */
93 202 : while (node) {
94 116 : if (node->l_left) {
95 26 : node = node->l_left;
96 26 : continue;
97 : }
98 :
99 90 : if (node->l_right) {
100 26 : node = node->l_right;
101 26 : continue;
102 : }
103 :
104 64 : tmp_node = node;
105 64 : node = node->parent;
106 :
107 64 : tmp_node->table->count--;
108 64 : tmp_node->lock =
109 : 0; /* to cause assert if unlocked after this */
110 64 : rn_hash_node_del(&rt->hash, tmp_node);
111 64 : route_node_free(rt, tmp_node);
112 :
113 64 : if (node != NULL) {
114 52 : if (node->l_left == tmp_node)
115 26 : node->l_left = NULL;
116 : else
117 26 : node->l_right = NULL;
118 : } else {
119 : break;
120 : }
121 : }
122 :
123 98 : assert(rt->count == 0);
124 :
125 98 : rn_hash_node_fini(&rt->hash);
126 98 : XFREE(MTYPE_ROUTE_TABLE, rt);
127 98 : return;
128 : }
129 :
130 : /* Utility mask array. */
131 : static const uint8_t maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
132 : 0xf8, 0xfc, 0xfe, 0xff};
133 :
134 : /* Common prefix route genaration. */
135 50 : static void route_common(const struct prefix *n, const struct prefix *p,
136 : struct prefix *new)
137 : {
138 50 : int i;
139 50 : uint8_t diff;
140 50 : uint8_t mask;
141 50 : const uint8_t *np;
142 50 : const uint8_t *pp;
143 50 : uint8_t *newp;
144 :
145 50 : if (n->family == AF_FLOWSPEC)
146 0 : return prefix_copy(new, p);
147 50 : np = (const uint8_t *)&n->u.prefix;
148 50 : pp = (const uint8_t *)&p->u.prefix;
149 :
150 50 : newp = &new->u.prefix;
151 :
152 152 : for (i = 0; i < p->prefixlen / 8; i++) {
153 152 : if (np[i] == pp[i])
154 102 : newp[i] = np[i];
155 : else
156 : break;
157 : }
158 :
159 50 : new->prefixlen = i * 8;
160 :
161 50 : if (new->prefixlen != p->prefixlen) {
162 50 : diff = np[i] ^ pp[i];
163 50 : mask = 0x80;
164 244 : while (new->prefixlen < p->prefixlen && !(mask & diff)) {
165 194 : mask >>= 1;
166 194 : new->prefixlen++;
167 : }
168 50 : newp[i] = np[i] & maskbit[new->prefixlen % 8];
169 : }
170 : }
171 :
172 145 : static void set_link(struct route_node *node, struct route_node *new)
173 : {
174 145 : unsigned int bit = prefix_bit(&new->p.u.prefix, node->p.prefixlen);
175 :
176 145 : node->link[bit] = new;
177 145 : new->parent = node;
178 145 : }
179 :
180 : /* Find matched prefix. */
181 58 : struct route_node *route_node_match(struct route_table *table,
182 : union prefixconstptr pu)
183 : {
184 58 : const struct prefix *p = pu.p;
185 58 : struct route_node *node;
186 58 : struct route_node *matched;
187 :
188 58 : matched = NULL;
189 58 : node = table->top;
190 :
191 : /* Walk down tree. If there is matched route then store it to
192 : matched. */
193 187 : while (node && node->p.prefixlen <= p->prefixlen
194 275 : && prefix_match(&node->p, p)) {
195 120 : if (node->info)
196 74 : matched = node;
197 :
198 120 : if (node->p.prefixlen == p->prefixlen)
199 : break;
200 :
201 88 : node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
202 : }
203 :
204 : /* If matched route found, return it. */
205 58 : if (matched)
206 50 : return route_lock_node(matched);
207 :
208 : return NULL;
209 : }
210 :
211 0 : struct route_node *route_node_match_ipv4(struct route_table *table,
212 : const struct in_addr *addr)
213 : {
214 0 : struct prefix_ipv4 p;
215 :
216 0 : memset(&p, 0, sizeof(p));
217 0 : p.family = AF_INET;
218 0 : p.prefixlen = IPV4_MAX_BITLEN;
219 0 : p.prefix = *addr;
220 :
221 0 : return route_node_match(table, (struct prefix *)&p);
222 : }
223 :
224 0 : struct route_node *route_node_match_ipv6(struct route_table *table,
225 : const struct in6_addr *addr)
226 : {
227 0 : struct prefix_ipv6 p;
228 :
229 0 : memset(&p, 0, sizeof(p));
230 0 : p.family = AF_INET6;
231 0 : p.prefixlen = IPV6_MAX_BITLEN;
232 0 : p.prefix = *addr;
233 :
234 0 : return route_node_match(table, &p);
235 : }
236 :
237 : /* Lookup same prefix node. Return NULL when we can't find route. */
238 135 : struct route_node *route_node_lookup(struct route_table *table,
239 : union prefixconstptr pu)
240 : {
241 135 : struct route_node rn, *node;
242 135 : prefix_copy(&rn.p, pu.p);
243 135 : apply_mask(&rn.p);
244 :
245 135 : node = rn_hash_node_find(&table->hash, &rn);
246 135 : return (node && node->info) ? route_lock_node(node) : NULL;
247 : }
248 :
249 : /* Lookup same prefix node. Return NULL when we can't find route. */
250 8 : struct route_node *route_node_lookup_maynull(struct route_table *table,
251 : union prefixconstptr pu)
252 : {
253 8 : struct route_node rn, *node;
254 8 : prefix_copy(&rn.p, pu.p);
255 8 : apply_mask(&rn.p);
256 :
257 8 : node = rn_hash_node_find(&table->hash, &rn);
258 8 : return node ? route_lock_node(node) : NULL;
259 : }
260 :
261 : /* Add node to routing table. */
262 180 : struct route_node *route_node_get(struct route_table *table,
263 : union prefixconstptr pu)
264 : {
265 180 : if (frrtrace_enabled(frr_libfrr, route_node_get)) {
266 : char buf[PREFIX2STR_BUFFER];
267 : prefix2str(pu, buf, sizeof(buf));
268 : frrtrace(2, frr_libfrr, route_node_get, table, buf);
269 : }
270 :
271 180 : struct route_node search;
272 180 : struct prefix *p = &search.p;
273 :
274 180 : prefix_copy(p, pu.p);
275 180 : apply_mask(p);
276 :
277 180 : struct route_node *new;
278 180 : struct route_node *node;
279 180 : struct route_node *match;
280 180 : uint16_t prefixlen = p->prefixlen;
281 180 : const uint8_t *prefix = &p->u.prefix;
282 :
283 180 : node = rn_hash_node_find(&table->hash, &search);
284 180 : if (node && node->info)
285 88 : return route_lock_node(node);
286 :
287 92 : match = NULL;
288 92 : node = table->top;
289 258 : while (node && node->p.prefixlen <= prefixlen
290 347 : && prefix_match(&node->p, p)) {
291 116 : if (node->p.prefixlen == prefixlen)
292 12 : return route_lock_node(node);
293 :
294 104 : match = node;
295 104 : node = node->link[prefix_bit(prefix, node->p.prefixlen)];
296 : }
297 :
298 80 : if (node == NULL) {
299 30 : new = route_node_set(table, p);
300 30 : if (match)
301 8 : set_link(match, new);
302 : else
303 22 : table->top = new;
304 : } else {
305 50 : new = route_node_new(table);
306 50 : route_common(&node->p, p, &new->p);
307 50 : new->p.family = p->family;
308 50 : new->table = table;
309 50 : set_link(new, node);
310 50 : rn_hash_node_add(&table->hash, new);
311 :
312 50 : if (match)
313 37 : set_link(match, new);
314 : else
315 13 : table->top = new;
316 :
317 50 : if (new->p.prefixlen != p->prefixlen) {
318 50 : match = new;
319 50 : new = route_node_set(table, p);
320 50 : set_link(match, new);
321 50 : table->count++;
322 : }
323 : }
324 80 : table->count++;
325 80 : route_lock_node(new);
326 :
327 80 : return new;
328 : }
329 :
330 : /* Delete node from the routing table. */
331 162 : void route_node_delete(struct route_node *node)
332 : {
333 193 : struct route_node *child;
334 193 : struct route_node *parent;
335 :
336 193 : assert(node->lock == 0);
337 :
338 193 : if (node->l_left && node->l_right)
339 : return;
340 :
341 42 : if (node->l_left)
342 : child = node->l_left;
343 : else
344 31 : child = node->l_right;
345 :
346 42 : parent = node->parent;
347 :
348 42 : if (child)
349 19 : child->parent = parent;
350 :
351 42 : if (parent) {
352 33 : if (parent->l_left == node)
353 16 : parent->l_left = child;
354 : else
355 17 : parent->l_right = child;
356 : } else
357 9 : node->table->top = child;
358 :
359 42 : node->table->count--;
360 :
361 42 : rn_hash_node_del(&node->table->hash, node);
362 :
363 : /* WARNING: FRAGILE CODE!
364 : * route_node_free may have the side effect of free'ing the entire
365 : * table.
366 : * this is permitted only if table->count got decremented to zero above,
367 : * because in that case parent will also be NULL, so that we won't try
368 : * to
369 : * delete a now-stale parent below.
370 : *
371 : * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */
372 :
373 42 : route_node_free(node->table, node);
374 :
375 : /* If parent node is stub then delete it also. */
376 42 : if (parent && parent->lock == 0)
377 : route_node_delete(parent);
378 : }
379 :
380 : /* Get first node and lock it. This function is useful when one wants
381 : to lookup all the node exist in the routing table. */
382 427 : struct route_node *route_top(struct route_table *table)
383 : {
384 : /* If there is no node in the routing table return NULL. */
385 427 : if (table->top == NULL)
386 : return NULL;
387 :
388 : /* Lock the top node and return it. */
389 75 : route_lock_node(table->top);
390 75 : return table->top;
391 : }
392 :
393 : /* Unlock current node and lock next node then return it. */
394 345 : struct route_node *route_next(struct route_node *node)
395 : {
396 345 : struct route_node *next;
397 345 : struct route_node *start;
398 :
399 : /* Node may be deleted from route_unlock_node so we have to preserve
400 : next node's pointer. */
401 :
402 345 : if (node->l_left) {
403 151 : next = node->l_left;
404 151 : route_lock_node(next);
405 151 : route_unlock_node(node);
406 151 : return next;
407 : }
408 194 : if (node->l_right) {
409 10 : next = node->l_right;
410 10 : route_lock_node(next);
411 10 : route_unlock_node(node);
412 10 : return next;
413 : }
414 :
415 : start = node;
416 315 : while (node->parent) {
417 253 : if (node->parent->l_left == node && node->parent->l_right) {
418 122 : next = node->parent->l_right;
419 122 : route_lock_node(next);
420 122 : route_unlock_node(start);
421 122 : return next;
422 : }
423 : node = node->parent;
424 : }
425 62 : route_unlock_node(start);
426 62 : return NULL;
427 : }
428 :
429 : /* Unlock current node and lock next node until limit. */
430 0 : struct route_node *route_next_until(struct route_node *node,
431 : const struct route_node *limit)
432 : {
433 0 : struct route_node *next;
434 0 : struct route_node *start;
435 :
436 : /* Node may be deleted from route_unlock_node so we have to preserve
437 : next node's pointer. */
438 :
439 0 : if (node->l_left) {
440 0 : next = node->l_left;
441 0 : route_lock_node(next);
442 0 : route_unlock_node(node);
443 0 : return next;
444 : }
445 0 : if (node->l_right) {
446 0 : next = node->l_right;
447 0 : route_lock_node(next);
448 0 : route_unlock_node(node);
449 0 : return next;
450 : }
451 :
452 : start = node;
453 0 : while (node->parent && node != limit) {
454 0 : if (node->parent->l_left == node && node->parent->l_right) {
455 0 : next = node->parent->l_right;
456 0 : route_lock_node(next);
457 0 : route_unlock_node(start);
458 0 : return next;
459 : }
460 : node = node->parent;
461 : }
462 0 : route_unlock_node(start);
463 0 : return NULL;
464 : }
465 :
466 0 : unsigned long route_table_count(struct route_table *table)
467 : {
468 0 : return table->count;
469 : }
470 :
471 : /**
472 : * route_node_create
473 : *
474 : * Default function for creating a route node.
475 : */
476 84 : struct route_node *route_node_create(route_table_delegate_t *delegate,
477 : struct route_table *table)
478 : {
479 84 : struct route_node *node;
480 84 : node = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct route_node));
481 84 : return node;
482 : }
483 :
484 : /**
485 : * route_node_destroy
486 : *
487 : * Default function for destroying a route node.
488 : */
489 46 : void route_node_destroy(route_table_delegate_t *delegate,
490 : struct route_table *table, struct route_node *node)
491 : {
492 46 : XFREE(MTYPE_ROUTE_NODE, node);
493 46 : }
494 :
495 : /*
496 : * Default delegate.
497 : */
498 : static route_table_delegate_t default_delegate = {
499 : .create_node = route_node_create,
500 : .destroy_node = route_node_destroy};
501 :
502 0 : route_table_delegate_t *route_table_get_default_delegate(void)
503 : {
504 0 : return &default_delegate;
505 : }
506 :
507 : /*
508 : * route_table_init
509 : */
510 18 : struct route_table *route_table_init(void)
511 : {
512 18 : return route_table_init_with_delegate(&default_delegate);
513 : }
514 :
515 : /**
516 : * route_table_prefix_iter_cmp
517 : *
518 : * Compare two prefixes according to the order in which they appear in
519 : * an iteration over a tree.
520 : *
521 : * @return -1 if p1 occurs before p2 (p1 < p2)
522 : * 0 if the prefixes are identical (p1 == p2)
523 : * +1 if p1 occurs after p2 (p1 > p2)
524 : */
525 0 : int route_table_prefix_iter_cmp(const struct prefix *p1,
526 : const struct prefix *p2)
527 : {
528 0 : struct prefix common_space;
529 0 : struct prefix *common = &common_space;
530 :
531 0 : if (p1->prefixlen <= p2->prefixlen) {
532 0 : if (prefix_match(p1, p2)) {
533 :
534 : /*
535 : * p1 contains p2, or is equal to it.
536 : */
537 0 : return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
538 : }
539 : } else {
540 :
541 : /*
542 : * Check if p2 contains p1.
543 : */
544 0 : if (prefix_match(p2, p1))
545 : return 1;
546 : }
547 :
548 0 : route_common(p1, p2, common);
549 0 : assert(common->prefixlen < p1->prefixlen);
550 0 : assert(common->prefixlen < p2->prefixlen);
551 :
552 : /*
553 : * Both prefixes are longer than the common prefix.
554 : *
555 : * We need to check the bit after the common prefixlen to determine
556 : * which one comes later.
557 : */
558 0 : if (prefix_bit(&p1->u.prefix, common->prefixlen)) {
559 :
560 : /*
561 : * We branch to the right to get to p1 from the common prefix.
562 : */
563 0 : assert(!prefix_bit(&p2->u.prefix, common->prefixlen));
564 : return 1;
565 : }
566 :
567 : /*
568 : * We branch to the right to get to p2 from the common prefix.
569 : */
570 0 : assert(prefix_bit(&p2->u.prefix, common->prefixlen));
571 : return -1;
572 : }
573 :
574 : /*
575 : * route_get_subtree_next
576 : *
577 : * Helper function that returns the first node that follows the nodes
578 : * in the sub-tree under 'node' in iteration order.
579 : */
580 : static struct route_node *route_get_subtree_next(struct route_node *node)
581 : {
582 0 : while (node->parent) {
583 0 : if (node->parent->l_left == node && node->parent->l_right)
584 : return node->parent->l_right;
585 :
586 : node = node->parent;
587 : }
588 :
589 : return NULL;
590 : }
591 :
592 : /**
593 : * route_table_get_next_internal
594 : *
595 : * Helper function to find the node that occurs after the given prefix in
596 : * order of iteration.
597 : *
598 : * @see route_table_get_next
599 : */
600 : static struct route_node *
601 0 : route_table_get_next_internal(struct route_table *table,
602 : const struct prefix *p)
603 : {
604 0 : struct route_node *node, *tmp_node;
605 0 : int cmp;
606 :
607 0 : node = table->top;
608 :
609 0 : while (node) {
610 0 : int match;
611 :
612 0 : if (node->p.prefixlen < p->prefixlen)
613 0 : match = prefix_match(&node->p, p);
614 : else
615 0 : match = prefix_match(p, &node->p);
616 :
617 0 : if (match) {
618 0 : if (node->p.prefixlen == p->prefixlen) {
619 :
620 : /*
621 : * The prefix p exists in the tree, just return
622 : * the next
623 : * node.
624 : */
625 0 : route_lock_node(node);
626 0 : node = route_next(node);
627 0 : if (node)
628 0 : route_unlock_node(node);
629 :
630 0 : return (node);
631 : }
632 :
633 0 : if (node->p.prefixlen > p->prefixlen) {
634 :
635 : /*
636 : * Node is in the subtree of p, and hence
637 : * greater than p.
638 : */
639 0 : return node;
640 : }
641 :
642 : /*
643 : * p is in the sub-tree under node.
644 : */
645 0 : tmp_node = node->link[prefix_bit(&p->u.prefix,
646 : node->p.prefixlen)];
647 :
648 0 : if (tmp_node) {
649 0 : node = tmp_node;
650 0 : continue;
651 : }
652 :
653 : /*
654 : * There are no nodes in the direction where p should
655 : * be. If
656 : * node has a right child, then it must be greater than
657 : * p.
658 : */
659 0 : if (node->l_right)
660 : return node->l_right;
661 :
662 : /*
663 : * No more children to follow, go upwards looking for
664 : * the next
665 : * node.
666 : */
667 0 : return route_get_subtree_next(node);
668 : }
669 :
670 : /*
671 : * Neither node prefix nor 'p' contains the other.
672 : */
673 0 : cmp = route_table_prefix_iter_cmp(&node->p, p);
674 0 : if (cmp > 0) {
675 :
676 : /*
677 : * Node follows p in iteration order. Return it.
678 : */
679 : return node;
680 : }
681 :
682 0 : assert(cmp < 0);
683 :
684 : /*
685 : * Node and the subtree under it come before prefix p in
686 : * iteration order. Prefix p and its sub-tree are not present in
687 : * the tree. Go upwards and find the first node that follows the
688 : * subtree. That node will also succeed p.
689 : */
690 0 : return route_get_subtree_next(node);
691 : }
692 :
693 : return NULL;
694 : }
695 :
696 : /**
697 : * route_table_get_next
698 : *
699 : * Find the node that occurs after the given prefix in order of
700 : * iteration.
701 : */
702 0 : struct route_node *route_table_get_next(struct route_table *table,
703 : union prefixconstptr pu)
704 : {
705 0 : const struct prefix *p = pu.p;
706 0 : struct route_node *node;
707 :
708 0 : node = route_table_get_next_internal(table, p);
709 0 : if (node) {
710 0 : assert(route_table_prefix_iter_cmp(&node->p, p) > 0);
711 0 : route_lock_node(node);
712 : }
713 0 : return node;
714 : }
715 :
716 : /*
717 : * route_table_iter_init
718 : */
719 0 : void route_table_iter_init(route_table_iter_t *iter, struct route_table *table)
720 : {
721 0 : memset(iter, 0, sizeof(*iter));
722 0 : iter->state = RT_ITER_STATE_INIT;
723 0 : iter->table = table;
724 0 : }
725 :
726 : /*
727 : * route_table_iter_pause
728 : *
729 : * Pause an iteration over the table. This allows the iteration to be
730 : * resumed point after arbitrary additions/deletions from the table.
731 : * An iteration can be resumed by just calling route_table_iter_next()
732 : * on the iterator.
733 : */
734 0 : void route_table_iter_pause(route_table_iter_t *iter)
735 : {
736 0 : switch (iter->state) {
737 :
738 : case RT_ITER_STATE_INIT:
739 : case RT_ITER_STATE_PAUSED:
740 : case RT_ITER_STATE_DONE:
741 : return;
742 :
743 0 : case RT_ITER_STATE_ITERATING:
744 :
745 : /*
746 : * Save the prefix that we are currently at. The next call to
747 : * route_table_iter_next() will return the node after this
748 : * prefix
749 : * in the tree.
750 : */
751 0 : prefix_copy(&iter->pause_prefix, &iter->current->p);
752 0 : route_unlock_node(iter->current);
753 0 : iter->current = NULL;
754 0 : iter->state = RT_ITER_STATE_PAUSED;
755 0 : return;
756 :
757 : default:
758 0 : assert(0);
759 : }
760 : }
761 :
762 : /*
763 : * route_table_iter_cleanup
764 : *
765 : * Release any resources held by the iterator.
766 : */
767 0 : void route_table_iter_cleanup(route_table_iter_t *iter)
768 : {
769 0 : if (iter->state == RT_ITER_STATE_ITERATING) {
770 0 : route_unlock_node(iter->current);
771 0 : iter->current = NULL;
772 : }
773 0 : assert(!iter->current);
774 :
775 : /*
776 : * Set the state to RT_ITER_STATE_DONE to make any
777 : * route_table_iter_next() calls on this iterator return NULL.
778 : */
779 0 : iter->state = RT_ITER_STATE_DONE;
780 0 : }
|
