2 * Routing Table functions.
3 * Copyright (C) 1998 Kunihiro Ishiguro
5 * This file is part of GNU Zebra.
7 * GNU Zebra is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2, or (at your option) any
12 * GNU Zebra is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; see the file COPYING; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 #define FRR_COMPILING_TABLE_C
29 #include "sockunion.h"
31 DEFINE_MTYPE(LIB
, ROUTE_TABLE
, "Route table")
32 DEFINE_MTYPE(LIB
, ROUTE_NODE
, "Route node")
34 static void route_table_free(struct route_table
*);
36 static int route_table_hash_cmp(const void *a
, const void *b
)
38 const struct prefix
*pa
= a
, *pb
= b
;
39 return prefix_cmp(pa
, pb
) == 0;
43 * route_table_init_with_delegate
46 route_table_init_with_delegate(route_table_delegate_t
*delegate
)
48 struct route_table
*rt
;
50 rt
= XCALLOC(MTYPE_ROUTE_TABLE
, sizeof(struct route_table
));
51 rt
->delegate
= delegate
;
52 rt
->hash
= hash_create(prefix_hash_key
, route_table_hash_cmp
,
57 void route_table_finish(struct route_table
*rt
)
62 /* Allocate new route node. */
63 static struct route_node
*route_node_new(struct route_table
*table
)
65 return table
->delegate
->create_node(table
->delegate
, table
);
68 /* Allocate new route node with prefix set. */
69 static struct route_node
*route_node_set(struct route_table
*table
,
70 const struct prefix
*prefix
)
72 struct route_node
*node
, *inserted
;
74 node
= route_node_new(table
);
76 prefix_copy(&node
->p
, prefix
);
80 inserted
= hash_get(node
->table
->hash
, node
, hash_alloc_intern
);
81 assert(inserted
== node
);
86 /* Free route node. */
87 static void route_node_free(struct route_table
*table
, struct route_node
*node
)
90 table
->cleanup(table
, node
);
91 table
->delegate
->destroy_node(table
->delegate
, table
, node
);
94 /* Free route table. */
95 static void route_table_free(struct route_table
*rt
)
97 struct route_node
*tmp_node
;
98 struct route_node
*node
;
103 hash_clean(rt
->hash
, NULL
);
108 /* Bulk deletion of nodes remaining in this table. This function is not
109 called until workers have completed their dependency on this table.
110 A final route_unlock_node() will not be called for these nodes. */
118 node
= node
->l_right
;
125 tmp_node
->table
->count
--;
126 tmp_node
->lock
= 0; /* to cause assert if unlocked after this */
127 route_node_free(rt
, tmp_node
);
130 if (node
->l_left
== tmp_node
)
133 node
->l_right
= NULL
;
139 assert(rt
->count
== 0);
141 XFREE(MTYPE_ROUTE_TABLE
, rt
);
145 /* Utility mask array. */
146 static const u_char maskbit
[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
147 0xf8, 0xfc, 0xfe, 0xff};
149 /* Common prefix route genaration. */
150 static void route_common(const struct prefix
*n
, const struct prefix
*p
,
157 const u_char
*np
= (const u_char
*)&n
->u
.prefix
;
158 const u_char
*pp
= (const u_char
*)&p
->u
.prefix
;
159 u_char
*newp
= (u_char
*)&new->u
.prefix
;
161 for (i
= 0; i
< p
->prefixlen
/ 8; i
++) {
168 new->prefixlen
= i
* 8;
170 if (new->prefixlen
!= p
->prefixlen
) {
171 diff
= np
[i
] ^ pp
[i
];
173 while (new->prefixlen
< p
->prefixlen
&& !(mask
& diff
)) {
177 newp
[i
] = np
[i
] & maskbit
[new->prefixlen
% 8];
181 static void set_link(struct route_node
*node
, struct route_node
*new)
183 unsigned int bit
= prefix_bit(&new->p
.u
.prefix
, node
->p
.prefixlen
);
185 node
->link
[bit
] = new;
189 /* Find matched prefix. */
190 struct route_node
*route_node_match(const struct route_table
*table
,
191 union prefixconstptr pu
)
193 const struct prefix
*p
= pu
.p
;
194 struct route_node
*node
;
195 struct route_node
*matched
;
200 /* Walk down tree. If there is matched route then store it to
202 while (node
&& node
->p
.prefixlen
<= p
->prefixlen
203 && prefix_match(&node
->p
, p
)) {
207 if (node
->p
.prefixlen
== p
->prefixlen
)
210 node
= node
->link
[prefix_bit(&p
->u
.prefix
, node
->p
.prefixlen
)];
213 /* If matched route found, return it. */
215 return route_lock_node(matched
);
220 struct route_node
*route_node_match_ipv4(const struct route_table
*table
,
221 const struct in_addr
*addr
)
223 struct prefix_ipv4 p
;
225 memset(&p
, 0, sizeof(struct prefix_ipv4
));
227 p
.prefixlen
= IPV4_MAX_PREFIXLEN
;
230 return route_node_match(table
, (struct prefix
*)&p
);
233 struct route_node
*route_node_match_ipv6(const struct route_table
*table
,
234 const struct in6_addr
*addr
)
236 struct prefix_ipv6 p
;
238 memset(&p
, 0, sizeof(struct prefix_ipv6
));
240 p
.prefixlen
= IPV6_MAX_PREFIXLEN
;
243 return route_node_match(table
, (struct prefix
*)&p
);
246 /* Lookup same prefix node. Return NULL when we can't find route. */
247 struct route_node
*route_node_lookup(const struct route_table
*table
,
248 union prefixconstptr pu
)
251 struct route_node
*node
;
252 prefix_copy(&p
, pu
.p
);
255 node
= hash_get(table
->hash
, (void *)&p
, NULL
);
256 return (node
&& node
->info
) ? route_lock_node(node
) : NULL
;
259 /* Lookup same prefix node. Return NULL when we can't find route. */
260 struct route_node
*route_node_lookup_maynull(const struct route_table
*table
,
261 union prefixconstptr pu
)
264 struct route_node
*node
;
265 prefix_copy(&p
, pu
.p
);
268 node
= hash_get(table
->hash
, (void *)&p
, NULL
);
269 return node
? route_lock_node(node
) : NULL
;
272 /* Add node to routing table. */
273 struct route_node
*route_node_get(struct route_table
*const table
,
274 union prefixconstptr pu
)
276 const struct prefix
*p
= pu
.p
;
277 struct route_node
*new;
278 struct route_node
*node
;
279 struct route_node
*match
;
280 struct route_node
*inserted
;
281 u_char prefixlen
= p
->prefixlen
;
282 const u_char
*prefix
= &p
->u
.prefix
;
284 apply_mask((struct prefix
*)p
);
285 node
= hash_get(table
->hash
, (void *)p
, NULL
);
286 if (node
&& node
->info
)
287 return route_lock_node(node
);
291 while (node
&& node
->p
.prefixlen
<= prefixlen
292 && prefix_match(&node
->p
, p
)) {
293 if (node
->p
.prefixlen
== prefixlen
)
294 return route_lock_node(node
);
297 node
= node
->link
[prefix_bit(prefix
, node
->p
.prefixlen
)];
301 new = route_node_set(table
, p
);
303 set_link(match
, new);
307 new = route_node_new(table
);
308 route_common(&node
->p
, p
, &new->p
);
309 new->p
.family
= p
->family
;
312 inserted
= hash_get(node
->table
->hash
, new, hash_alloc_intern
);
313 assert(inserted
== new);
316 set_link(match
, new);
320 if (new->p
.prefixlen
!= p
->prefixlen
) {
322 new = route_node_set(table
, p
);
323 set_link(match
, new);
328 route_lock_node(new);
333 /* Delete node from the routing table. */
334 void route_node_delete(struct route_node
*node
)
336 struct route_node
*child
;
337 struct route_node
*parent
;
339 assert(node
->lock
== 0);
340 assert(node
->info
== NULL
);
342 if (node
->l_left
&& node
->l_right
)
346 child
= node
->l_left
;
348 child
= node
->l_right
;
350 parent
= node
->parent
;
353 child
->parent
= parent
;
356 if (parent
->l_left
== node
)
357 parent
->l_left
= child
;
359 parent
->l_right
= child
;
361 node
->table
->top
= child
;
363 node
->table
->count
--;
365 hash_release(node
->table
->hash
, node
);
367 /* WARNING: FRAGILE CODE!
368 * route_node_free may have the side effect of free'ing the entire
370 * this is permitted only if table->count got decremented to zero above,
371 * because in that case parent will also be NULL, so that we won't try
373 * delete a now-stale parent below.
375 * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */
377 route_node_free(node
->table
, node
);
379 /* If parent node is stub then delete it also. */
380 if (parent
&& parent
->lock
== 0)
381 route_node_delete(parent
);
384 /* Get fist node and lock it. This function is useful when one want
385 to lookup all the node exist in the routing table. */
386 struct route_node
*route_top(struct route_table
*table
)
388 /* If there is no node in the routing table return NULL. */
389 if (table
->top
== NULL
)
392 /* Lock the top node and return it. */
393 route_lock_node(table
->top
);
397 /* Unlock current node and lock next node then return it. */
398 struct route_node
*route_next(struct route_node
*node
)
400 struct route_node
*next
;
401 struct route_node
*start
;
403 /* Node may be deleted from route_unlock_node so we have to preserve
404 next node's pointer. */
408 route_lock_node(next
);
409 route_unlock_node(node
);
413 next
= node
->l_right
;
414 route_lock_node(next
);
415 route_unlock_node(node
);
420 while (node
->parent
) {
421 if (node
->parent
->l_left
== node
&& node
->parent
->l_right
) {
422 next
= node
->parent
->l_right
;
423 route_lock_node(next
);
424 route_unlock_node(start
);
429 route_unlock_node(start
);
433 /* Unlock current node and lock next node until limit. */
434 struct route_node
*route_next_until(struct route_node
*node
,
435 const struct route_node
*limit
)
437 struct route_node
*next
;
438 struct route_node
*start
;
440 /* Node may be deleted from route_unlock_node so we have to preserve
441 next node's pointer. */
445 route_lock_node(next
);
446 route_unlock_node(node
);
450 next
= node
->l_right
;
451 route_lock_node(next
);
452 route_unlock_node(node
);
457 while (node
->parent
&& node
!= limit
) {
458 if (node
->parent
->l_left
== node
&& node
->parent
->l_right
) {
459 next
= node
->parent
->l_right
;
460 route_lock_node(next
);
461 route_unlock_node(start
);
466 route_unlock_node(start
);
470 unsigned long route_table_count(const struct route_table
*table
)
478 * Default function for creating a route node.
480 struct route_node
*route_node_create(route_table_delegate_t
*delegate
,
481 struct route_table
*table
)
483 struct route_node
*node
;
484 node
= XCALLOC(MTYPE_ROUTE_NODE
, sizeof(struct route_node
));
491 * Default function for destroying a route node.
493 void route_node_destroy(route_table_delegate_t
*delegate
,
494 struct route_table
*table
, struct route_node
*node
)
496 XFREE(MTYPE_ROUTE_NODE
, node
);
502 static route_table_delegate_t default_delegate
= {
503 .create_node
= route_node_create
,
504 .destroy_node
= route_node_destroy
};
506 route_table_delegate_t
*route_table_get_default_delegate(void)
508 return &default_delegate
;
514 struct route_table
*route_table_init(void)
516 return route_table_init_with_delegate(&default_delegate
);
520 * route_table_prefix_iter_cmp
522 * Compare two prefixes according to the order in which they appear in
523 * an iteration over a tree.
525 * @return -1 if p1 occurs before p2 (p1 < p2)
526 * 0 if the prefixes are identical (p1 == p2)
527 * +1 if p1 occurs after p2 (p1 > p2)
529 int route_table_prefix_iter_cmp(const struct prefix
*p1
,
530 const struct prefix
*p2
)
532 struct prefix common_space
;
533 struct prefix
*common
= &common_space
;
535 if (p1
->prefixlen
<= p2
->prefixlen
) {
536 if (prefix_match(p1
, p2
)) {
539 * p1 contains p2, or is equal to it.
541 return (p1
->prefixlen
== p2
->prefixlen
) ? 0 : -1;
546 * Check if p2 contains p1.
548 if (prefix_match(p2
, p1
))
552 route_common(p1
, p2
, common
);
553 assert(common
->prefixlen
< p1
->prefixlen
);
554 assert(common
->prefixlen
< p2
->prefixlen
);
557 * Both prefixes are longer than the common prefix.
559 * We need to check the bit after the common prefixlen to determine
560 * which one comes later.
562 if (prefix_bit(&p1
->u
.prefix
, common
->prefixlen
)) {
565 * We branch to the right to get to p1 from the common prefix.
567 assert(!prefix_bit(&p2
->u
.prefix
, common
->prefixlen
));
572 * We branch to the right to get to p2 from the common prefix.
574 assert(prefix_bit(&p2
->u
.prefix
, common
->prefixlen
));
579 * route_get_subtree_next
581 * Helper function that returns the first node that follows the nodes
582 * in the sub-tree under 'node' in iteration order.
584 static struct route_node
*route_get_subtree_next(struct route_node
*node
)
586 while (node
->parent
) {
587 if (node
->parent
->l_left
== node
&& node
->parent
->l_right
)
588 return node
->parent
->l_right
;
597 * route_table_get_next_internal
599 * Helper function to find the node that occurs after the given prefix in
600 * order of iteration.
602 * @see route_table_get_next
604 static struct route_node
*
605 route_table_get_next_internal(const struct route_table
*table
,
606 const struct prefix
*p
)
608 struct route_node
*node
, *tmp_node
;
616 if (node
->p
.prefixlen
< p
->prefixlen
)
617 match
= prefix_match(&node
->p
, p
);
619 match
= prefix_match(p
, &node
->p
);
622 if (node
->p
.prefixlen
== p
->prefixlen
) {
625 * The prefix p exists in the tree, just return
629 route_lock_node(node
);
630 node
= route_next(node
);
632 route_unlock_node(node
);
637 if (node
->p
.prefixlen
> p
->prefixlen
) {
640 * Node is in the subtree of p, and hence
647 * p is in the sub-tree under node.
649 tmp_node
= node
->link
[prefix_bit(&p
->u
.prefix
,
658 * There are no nodes in the direction where p should
660 * node has a right child, then it must be greater than
664 return node
->l_right
;
667 * No more children to follow, go upwards looking for
671 return route_get_subtree_next(node
);
675 * Neither node prefix nor 'p' contains the other.
677 cmp
= route_table_prefix_iter_cmp(&node
->p
, p
);
681 * Node follows p in iteration order. Return it.
689 * Node and the subtree under it come before prefix p in
690 * iteration order. Prefix p and its sub-tree are not present in
691 * the tree. Go upwards and find the first node that follows the
692 * subtree. That node will also succeed p.
694 return route_get_subtree_next(node
);
701 * route_table_get_next
703 * Find the node that occurs after the given prefix in order of
706 struct route_node
*route_table_get_next(const struct route_table
*table
,
707 union prefixconstptr pu
)
709 const struct prefix
*p
= pu
.p
;
710 struct route_node
*node
;
712 node
= route_table_get_next_internal(table
, p
);
714 assert(route_table_prefix_iter_cmp(&node
->p
, p
) > 0);
715 route_lock_node(node
);
721 * route_table_iter_init
723 void route_table_iter_init(route_table_iter_t
*iter
, struct route_table
*table
)
725 memset(iter
, 0, sizeof(*iter
));
726 iter
->state
= RT_ITER_STATE_INIT
;
731 * route_table_iter_pause
733 * Pause an iteration over the table. This allows the iteration to be
734 * resumed point after arbitrary additions/deletions from the table.
735 * An iteration can be resumed by just calling route_table_iter_next()
738 void route_table_iter_pause(route_table_iter_t
*iter
)
740 switch (iter
->state
) {
742 case RT_ITER_STATE_INIT
:
743 case RT_ITER_STATE_PAUSED
:
744 case RT_ITER_STATE_DONE
:
747 case RT_ITER_STATE_ITERATING
:
750 * Save the prefix that we are currently at. The next call to
751 * route_table_iter_next() will return the node after this
755 prefix_copy(&iter
->pause_prefix
, &iter
->current
->p
);
756 route_unlock_node(iter
->current
);
757 iter
->current
= NULL
;
758 iter
->state
= RT_ITER_STATE_PAUSED
;
767 * route_table_iter_cleanup
769 * Release any resources held by the iterator.
771 void route_table_iter_cleanup(route_table_iter_t
*iter
)
773 if (iter
->state
== RT_ITER_STATE_ITERATING
) {
774 route_unlock_node(iter
->current
);
775 iter
->current
= NULL
;
777 assert(!iter
->current
);
780 * Set the state to RT_ITER_STATE_DONE to make any
781 * route_table_iter_next() calls on this iterator return NULL.
783 iter
->state
= RT_ITER_STATE_DONE
;