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