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
18 * along with GNU Zebra; see the file COPYING. If not, write to the Free
19 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
28 #include "sockunion.h"
30 DEFINE_MTYPE( LIB
, ROUTE_TABLE
, "Route table")
31 DEFINE_MTYPE_STATIC(LIB
, ROUTE_NODE
, "Route node")
33 static void route_node_delete (struct route_node
*);
34 static void route_table_free (struct route_table
*);
38 * route_table_init_with_delegate
41 route_table_init_with_delegate (route_table_delegate_t
*delegate
)
43 struct route_table
*rt
;
45 rt
= XCALLOC (MTYPE_ROUTE_TABLE
, sizeof (struct route_table
));
46 rt
->delegate
= delegate
;
51 route_table_finish (struct route_table
*rt
)
53 route_table_free (rt
);
56 /* Allocate new route node. */
57 static struct route_node
*
58 route_node_new (struct route_table
*table
)
60 return table
->delegate
->create_node (table
->delegate
, table
);
63 /* Allocate new route node with prefix set. */
64 static struct route_node
*
65 route_node_set (struct route_table
*table
, const struct prefix
*prefix
)
67 struct route_node
*node
;
69 node
= route_node_new (table
);
71 prefix_copy (&node
->p
, prefix
);
77 /* Free route node. */
79 route_node_free (struct route_table
*table
, struct route_node
*node
)
81 table
->delegate
->destroy_node (table
->delegate
, table
, node
);
84 /* Free route table. */
86 route_table_free (struct route_table
*rt
)
88 struct route_node
*tmp_node
;
89 struct route_node
*node
;
96 /* Bulk deletion of nodes remaining in this table. This function is not
97 called until workers have completed their dependency on this table.
98 A final route_unlock_node() will not be called for these nodes. */
109 node
= node
->l_right
;
116 tmp_node
->table
->count
--;
117 tmp_node
->lock
= 0; /* to cause assert if unlocked after this */
118 route_node_free (rt
, tmp_node
);
122 if (node
->l_left
== tmp_node
)
125 node
->l_right
= NULL
;
133 assert (rt
->count
== 0);
135 XFREE (MTYPE_ROUTE_TABLE
, rt
);
139 /* Utility mask array. */
140 static const u_char maskbit
[] =
142 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
145 /* Common prefix route genaration. */
147 route_common (const struct prefix
*n
, const struct prefix
*p
, struct prefix
*new)
153 const u_char
*np
= (const u_char
*)&n
->u
.prefix
;
154 const u_char
*pp
= (const u_char
*)&p
->u
.prefix
;
155 u_char
*newp
= (u_char
*)&new->u
.prefix
;
157 for (i
= 0; i
< p
->prefixlen
/ 8; i
++)
165 new->prefixlen
= i
* 8;
167 if (new->prefixlen
!= p
->prefixlen
)
169 diff
= np
[i
] ^ pp
[i
];
171 while (new->prefixlen
< p
->prefixlen
&& !(mask
& diff
))
176 newp
[i
] = np
[i
] & maskbit
[new->prefixlen
% 8];
181 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;
191 route_lock_node (struct route_node
*node
)
199 route_unlock_node (struct route_node
*node
)
201 assert (node
->lock
> 0);
205 route_node_delete (node
);
208 /* Find matched prefix. */
210 route_node_match (const struct route_table
*table
, const struct prefix
*p
)
212 struct route_node
*node
;
213 struct route_node
*matched
;
218 /* Walk down tree. If there is matched route then store it to
220 while (node
&& node
->p
.prefixlen
<= p
->prefixlen
&&
221 prefix_match (&node
->p
, p
))
226 if (node
->p
.prefixlen
== p
->prefixlen
)
229 node
= node
->link
[prefix_bit(&p
->u
.prefix
, node
->p
.prefixlen
)];
232 /* If matched route found, return it. */
234 return route_lock_node (matched
);
240 route_node_match_ipv4 (const struct route_table
*table
,
241 const struct in_addr
*addr
)
243 struct prefix_ipv4 p
;
245 memset (&p
, 0, sizeof (struct prefix_ipv4
));
247 p
.prefixlen
= IPV4_MAX_PREFIXLEN
;
250 return route_node_match (table
, (struct prefix
*) &p
);
255 route_node_match_ipv6 (const struct route_table
*table
,
256 const struct in6_addr
*addr
)
258 struct prefix_ipv6 p
;
260 memset (&p
, 0, sizeof (struct prefix_ipv6
));
262 p
.prefixlen
= IPV6_MAX_PREFIXLEN
;
265 return route_node_match (table
, (struct prefix
*) &p
);
267 #endif /* HAVE_IPV6 */
269 /* Lookup same prefix node. Return NULL when we can't find route. */
271 route_node_lookup (const struct route_table
*table
, const struct prefix
*p
)
273 struct route_node
*node
;
274 u_char prefixlen
= p
->prefixlen
;
275 const u_char
*prefix
= &p
->u
.prefix
;
279 while (node
&& node
->p
.prefixlen
<= prefixlen
&&
280 prefix_match (&node
->p
, p
))
282 if (node
->p
.prefixlen
== prefixlen
)
283 return node
->info
? route_lock_node (node
) : NULL
;
285 node
= node
->link
[prefix_bit(prefix
, node
->p
.prefixlen
)];
291 /* Add node to routing table. */
293 route_node_get (struct route_table
*const table
, const struct prefix
*p
)
295 struct route_node
*new;
296 struct route_node
*node
;
297 struct route_node
*match
;
298 u_char prefixlen
= p
->prefixlen
;
299 const u_char
*prefix
= &p
->u
.prefix
;
303 while (node
&& node
->p
.prefixlen
<= prefixlen
&&
304 prefix_match (&node
->p
, p
))
306 if (node
->p
.prefixlen
== prefixlen
)
307 return route_lock_node (node
);
310 node
= node
->link
[prefix_bit(prefix
, node
->p
.prefixlen
)];
315 new = route_node_set (table
, p
);
317 set_link (match
, new);
323 new = route_node_new (table
);
324 route_common (&node
->p
, p
, &new->p
);
325 new->p
.family
= p
->family
;
327 set_link (new, node
);
330 set_link (match
, new);
334 if (new->p
.prefixlen
!= p
->prefixlen
)
337 new = route_node_set (table
, p
);
338 set_link (match
, new);
343 route_lock_node (new);
348 /* Delete node from the routing table. */
350 route_node_delete (struct route_node
*node
)
352 struct route_node
*child
;
353 struct route_node
*parent
;
355 assert (node
->lock
== 0);
356 assert (node
->info
== NULL
);
358 if (node
->l_left
&& node
->l_right
)
362 child
= node
->l_left
;
364 child
= node
->l_right
;
366 parent
= node
->parent
;
369 child
->parent
= parent
;
373 if (parent
->l_left
== node
)
374 parent
->l_left
= child
;
376 parent
->l_right
= child
;
379 node
->table
->top
= child
;
381 node
->table
->count
--;
383 route_node_free (node
->table
, node
);
385 /* If parent node is stub then delete it also. */
386 if (parent
&& parent
->lock
== 0)
387 route_node_delete (parent
);
390 /* Get fist node and lock it. This function is useful when one want
391 to lookup all the node exist in the routing table. */
393 route_top (struct route_table
*table
)
395 /* If there is no node in the routing table return NULL. */
396 if (table
->top
== NULL
)
399 /* Lock the top node and return it. */
400 route_lock_node (table
->top
);
404 /* Unlock current node and lock next node then return it. */
406 route_next (struct route_node
*node
)
408 struct route_node
*next
;
409 struct route_node
*start
;
411 /* Node may be deleted from route_unlock_node so we have to preserve
412 next node's pointer. */
417 route_lock_node (next
);
418 route_unlock_node (node
);
423 next
= node
->l_right
;
424 route_lock_node (next
);
425 route_unlock_node (node
);
432 if (node
->parent
->l_left
== node
&& node
->parent
->l_right
)
434 next
= node
->parent
->l_right
;
435 route_lock_node (next
);
436 route_unlock_node (start
);
441 route_unlock_node (start
);
445 /* Unlock current node and lock next node until limit. */
447 route_next_until (struct route_node
*node
, struct route_node
*limit
)
449 struct route_node
*next
;
450 struct route_node
*start
;
452 /* Node may be deleted from route_unlock_node so we have to preserve
453 next node's pointer. */
458 route_lock_node (next
);
459 route_unlock_node (node
);
464 next
= node
->l_right
;
465 route_lock_node (next
);
466 route_unlock_node (node
);
471 while (node
->parent
&& node
!= limit
)
473 if (node
->parent
->l_left
== node
&& node
->parent
->l_right
)
475 next
= node
->parent
->l_right
;
476 route_lock_node (next
);
477 route_unlock_node (start
);
482 route_unlock_node (start
);
487 route_table_count (const struct route_table
*table
)
495 * Default function for creating a route node.
497 static struct route_node
*
498 route_node_create (route_table_delegate_t
*delegate
,
499 struct route_table
*table
)
501 struct route_node
*node
;
502 node
= XCALLOC (MTYPE_ROUTE_NODE
, sizeof (struct route_node
));
509 * Default function for destroying a route node.
512 route_node_destroy (route_table_delegate_t
*delegate
,
513 struct route_table
*table
, struct route_node
*node
)
515 XFREE (MTYPE_ROUTE_NODE
, node
);
521 static route_table_delegate_t default_delegate
= {
522 .create_node
= route_node_create
,
523 .destroy_node
= route_node_destroy
526 route_table_delegate_t
*
527 route_table_get_default_delegate(void)
529 return &default_delegate
;
536 route_table_init (void)
538 return route_table_init_with_delegate (&default_delegate
);
542 * route_table_prefix_iter_cmp
544 * Compare two prefixes according to the order in which they appear in
545 * an iteration over a tree.
547 * @return -1 if p1 occurs before p2 (p1 < p2)
548 * 0 if the prefixes are identical (p1 == p2)
549 * +1 if p1 occurs after p2 (p1 > p2)
552 route_table_prefix_iter_cmp (struct prefix
*p1
, struct prefix
*p2
)
554 struct prefix common_space
;
555 struct prefix
*common
= &common_space
;
557 if (p1
->prefixlen
<= p2
->prefixlen
)
559 if (prefix_match (p1
, p2
))
563 * p1 contains p2, or is equal to it.
565 return (p1
->prefixlen
== p2
->prefixlen
) ? 0 : -1;
572 * Check if p2 contains p1.
574 if (prefix_match (p2
, p1
))
578 route_common (p1
, p2
, common
);
579 assert (common
->prefixlen
< p1
->prefixlen
);
580 assert (common
->prefixlen
< p2
->prefixlen
);
583 * Both prefixes are longer than the common prefix.
585 * We need to check the bit after the common prefixlen to determine
586 * which one comes later.
588 if (prefix_bit (&p1
->u
.prefix
, common
->prefixlen
))
592 * We branch to the right to get to p1 from the common prefix.
594 assert (!prefix_bit (&p2
->u
.prefix
, common
->prefixlen
));
599 * We branch to the right to get to p2 from the common prefix.
601 assert (prefix_bit (&p2
->u
.prefix
, common
->prefixlen
));
606 * route_get_subtree_next
608 * Helper function that returns the first node that follows the nodes
609 * in the sub-tree under 'node' in iteration order.
611 static struct route_node
*
612 route_get_subtree_next (struct route_node
*node
)
616 if (node
->parent
->l_left
== node
&& node
->parent
->l_right
)
617 return node
->parent
->l_right
;
626 * route_table_get_next_internal
628 * Helper function to find the node that occurs after the given prefix in
629 * order of iteration.
631 * @see route_table_get_next
633 static struct route_node
*
634 route_table_get_next_internal (const struct route_table
*table
,
637 struct route_node
*node
, *tmp_node
;
646 if (node
->p
.prefixlen
< p
->prefixlen
)
647 match
= prefix_match (&node
->p
, p
);
649 match
= prefix_match (p
, &node
->p
);
653 if (node
->p
.prefixlen
== p
->prefixlen
)
657 * The prefix p exists in the tree, just return the next
660 route_lock_node (node
);
661 node
= route_next (node
);
663 route_unlock_node (node
);
668 if (node
->p
.prefixlen
> p
->prefixlen
)
672 * Node is in the subtree of p, and hence greater than p.
678 * p is in the sub-tree under node.
680 tmp_node
= node
->link
[prefix_bit (&p
->u
.prefix
, node
->p
.prefixlen
)];
689 * There are no nodes in the direction where p should be. If
690 * node has a right child, then it must be greater than p.
693 return node
->l_right
;
696 * No more children to follow, go upwards looking for the next
699 return route_get_subtree_next (node
);
703 * Neither node prefix nor 'p' contains the other.
705 cmp
= route_table_prefix_iter_cmp (&node
->p
, p
);
710 * Node follows p in iteration order. Return it.
718 * Node and the subtree under it come before prefix p in
719 * iteration order. Prefix p and its sub-tree are not present in
720 * the tree. Go upwards and find the first node that follows the
721 * subtree. That node will also succeed p.
723 return route_get_subtree_next (node
);
730 * route_table_get_next
732 * Find the node that occurs after the given prefix in order of
736 route_table_get_next (const struct route_table
*table
, struct prefix
*p
)
738 struct route_node
*node
;
740 node
= route_table_get_next_internal (table
, p
);
743 assert (route_table_prefix_iter_cmp (&node
->p
, p
) > 0);
744 route_lock_node (node
);
750 * route_table_iter_init
753 route_table_iter_init (route_table_iter_t
* iter
, struct route_table
*table
)
755 memset (iter
, 0, sizeof (*iter
));
756 iter
->state
= RT_ITER_STATE_INIT
;
761 * route_table_iter_pause
763 * Pause an iteration over the table. This allows the iteration to be
764 * resumed point after arbitrary additions/deletions from the table.
765 * An iteration can be resumed by just calling route_table_iter_next()
769 route_table_iter_pause (route_table_iter_t
* iter
)
774 case RT_ITER_STATE_INIT
:
775 case RT_ITER_STATE_PAUSED
:
776 case RT_ITER_STATE_DONE
:
779 case RT_ITER_STATE_ITERATING
:
782 * Save the prefix that we are currently at. The next call to
783 * route_table_iter_next() will return the node after this prefix
786 prefix_copy (&iter
->pause_prefix
, &iter
->current
->p
);
787 route_unlock_node (iter
->current
);
788 iter
->current
= NULL
;
789 iter
->state
= RT_ITER_STATE_PAUSED
;
799 * route_table_iter_cleanup
801 * Release any resources held by the iterator.
804 route_table_iter_cleanup (route_table_iter_t
* iter
)
806 if (iter
->state
== RT_ITER_STATE_ITERATING
)
808 route_unlock_node (iter
->current
);
809 iter
->current
= NULL
;
811 assert (!iter
->current
);
814 * Set the state to RT_ITER_STATE_DONE to make any
815 * route_table_iter_next() calls on this iterator return NULL.
817 iter
->state
= RT_ITER_STATE_DONE
;