Annotation of embedaddon/quagga/lib/table.c, revision 1.1.1.2
1.1 misho 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:
1.1.1.2 ! misho 30: static void route_node_delete (struct route_node *);
! 31: static void route_table_free (struct route_table *);
1.1 misho 32:
1.1.1.2 ! misho 33:
! 34: /*
! 35: * route_table_init_with_delegate
! 36: */
1.1 misho 37: struct route_table *
1.1.1.2 ! misho 38: route_table_init_with_delegate (route_table_delegate_t *delegate)
1.1 misho 39: {
40: struct route_table *rt;
41:
42: rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
1.1.1.2 ! misho 43: rt->delegate = delegate;
1.1 misho 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 *
1.1.1.2 ! misho 55: route_node_new (struct route_table *table)
1.1 misho 56: {
1.1.1.2 ! misho 57: return table->delegate->create_node (table->delegate, table);
1.1 misho 58: }
59:
60: /* Allocate new route node with prefix set. */
61: static struct route_node *
62: route_node_set (struct route_table *table, struct prefix *prefix)
63: {
64: struct route_node *node;
65:
1.1.1.2 ! misho 66: node = route_node_new (table);
1.1 misho 67:
68: prefix_copy (&node->p, prefix);
69: node->table = table;
70:
71: return node;
72: }
73:
74: /* Free route node. */
75: static void
1.1.1.2 ! misho 76: route_node_free (struct route_table *table, struct route_node *node)
1.1 misho 77: {
1.1.1.2 ! misho 78: table->delegate->destroy_node (table->delegate, table, node);
1.1 misho 79: }
80:
81: /* Free route table. */
1.1.1.2 ! misho 82: static void
1.1 misho 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:
1.1.1.2 ! misho 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. */
1.1 misho 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:
1.1.1.2 ! misho 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:
1.1 misho 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:
1.1.1.2 ! misho 130: assert (rt->count == 0);
! 131:
1.1 misho 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 (struct prefix *n, struct prefix *p, struct prefix *new)
145: {
146: int i;
147: u_char diff;
148: u_char mask;
149:
150: u_char *np = (u_char *)&n->u.prefix;
151: u_char *pp = (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: {
1.1.1.2 ! misho 198: assert (node->lock > 0);
1.1 misho 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 *
1.1.1.2 ! misho 268: route_node_lookup (const struct route_table *table, struct prefix *p)
1.1 misho 269: {
270: struct route_node *node;
1.1.1.2 ! misho 271: u_char prefixlen = p->prefixlen;
! 272: const u_char *prefix = &p->u.prefix;
1.1 misho 273:
274: node = table->top;
275:
1.1.1.2 ! misho 276: while (node && node->p.prefixlen <= prefixlen &&
1.1 misho 277: prefix_match (&node->p, p))
278: {
1.1.1.2 ! misho 279: if (node->p.prefixlen == prefixlen)
1.1 misho 280: return node->info ? route_lock_node (node) : NULL;
281:
1.1.1.2 ! misho 282: node = node->link[prefix_bit(prefix, node->p.prefixlen)];
1.1 misho 283: }
284:
285: return NULL;
286: }
287:
288: /* Add node to routing table. */
289: struct route_node *
1.1.1.2 ! misho 290: route_node_get (struct route_table *const table, struct prefix *p)
1.1 misho 291: {
292: struct route_node *new;
293: struct route_node *node;
294: struct route_node *match;
1.1.1.2 ! misho 295: u_char prefixlen = p->prefixlen;
! 296: const u_char *prefix = &p->u.prefix;
1.1 misho 297:
298: match = NULL;
299: node = table->top;
1.1.1.2 ! misho 300: while (node && node->p.prefixlen <= prefixlen &&
1.1 misho 301: prefix_match (&node->p, p))
302: {
1.1.1.2 ! misho 303: if (node->p.prefixlen == prefixlen)
1.1 misho 304: return route_lock_node (node);
1.1.1.2 ! misho 305:
1.1 misho 306: match = node;
1.1.1.2 ! misho 307: node = node->link[prefix_bit(prefix, node->p.prefixlen)];
1.1 misho 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: {
1.1.1.2 ! misho 320: new = route_node_new (table);
1.1 misho 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);
1.1.1.2 ! misho 336: table->count++;
1.1 misho 337: }
338: }
1.1.1.2 ! misho 339: table->count++;
1.1 misho 340: route_lock_node (new);
341:
342: return new;
343: }
344:
345: /* Delete node from the routing table. */
1.1.1.2 ! misho 346: static void
1.1 misho 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:
1.1.1.2 ! misho 378: node->table->count--;
! 379:
! 380: route_node_free (node->table, node);
1.1 misho 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: }
1.1.1.2 ! misho 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: u_char prefixlen;
! 630: int cmp;
! 631:
! 632: prefixlen = p->prefixlen;
! 633:
! 634: node = table->top;
! 635:
! 636: while (node)
! 637: {
! 638: int match;
! 639:
! 640: if (node->p.prefixlen < p->prefixlen)
! 641: match = prefix_match (&node->p, p);
! 642: else
! 643: match = prefix_match (p, &node->p);
! 644:
! 645: if (match)
! 646: {
! 647: if (node->p.prefixlen == p->prefixlen)
! 648: {
! 649:
! 650: /*
! 651: * The prefix p exists in the tree, just return the next
! 652: * node.
! 653: */
! 654: route_lock_node (node);
! 655: node = route_next (node);
! 656: if (node)
! 657: route_unlock_node (node);
! 658:
! 659: return (node);
! 660: }
! 661:
! 662: if (node->p.prefixlen > p->prefixlen)
! 663: {
! 664:
! 665: /*
! 666: * Node is in the subtree of p, and hence greater than p.
! 667: */
! 668: return node;
! 669: }
! 670:
! 671: /*
! 672: * p is in the sub-tree under node.
! 673: */
! 674: tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)];
! 675:
! 676: if (tmp_node)
! 677: {
! 678: node = tmp_node;
! 679: continue;
! 680: }
! 681:
! 682: /*
! 683: * There are no nodes in the direction where p should be. If
! 684: * node has a right child, then it must be greater than p.
! 685: */
! 686: if (node->l_right)
! 687: return node->l_right;
! 688:
! 689: /*
! 690: * No more children to follow, go upwards looking for the next
! 691: * node.
! 692: */
! 693: return route_get_subtree_next (node);
! 694: }
! 695:
! 696: /*
! 697: * Neither node prefix nor 'p' contains the other.
! 698: */
! 699: cmp = route_table_prefix_iter_cmp (&node->p, p);
! 700: if (cmp > 0)
! 701: {
! 702:
! 703: /*
! 704: * Node follows p in iteration order. Return it.
! 705: */
! 706: return node;
! 707: }
! 708:
! 709: assert (cmp < 0);
! 710:
! 711: /*
! 712: * Node and the subtree under it come before prefix p in
! 713: * iteration order. Prefix p and its sub-tree are not present in
! 714: * the tree. Go upwards and find the first node that follows the
! 715: * subtree. That node will also succeed p.
! 716: */
! 717: return route_get_subtree_next (node);
! 718: }
! 719:
! 720: return NULL;
! 721: }
! 722:
! 723: /**
! 724: * route_table_get_next
! 725: *
! 726: * Find the node that occurs after the given prefix in order of
! 727: * iteration.
! 728: */
! 729: struct route_node *
! 730: route_table_get_next (const struct route_table *table, struct prefix *p)
! 731: {
! 732: struct route_node *node;
! 733:
! 734: node = route_table_get_next_internal (table, p);
! 735: if (node)
! 736: {
! 737: assert (route_table_prefix_iter_cmp (&node->p, p) > 0);
! 738: route_lock_node (node);
! 739: }
! 740: return node;
! 741: }
! 742:
! 743: /*
! 744: * route_table_iter_init
! 745: */
! 746: void
! 747: route_table_iter_init (route_table_iter_t * iter, struct route_table *table)
! 748: {
! 749: memset (iter, 0, sizeof (*iter));
! 750: iter->state = RT_ITER_STATE_INIT;
! 751: iter->table = table;
! 752: }
! 753:
! 754: /*
! 755: * route_table_iter_pause
! 756: *
! 757: * Pause an iteration over the table. This allows the iteration to be
! 758: * resumed point after arbitrary additions/deletions from the table.
! 759: * An iteration can be resumed by just calling route_table_iter_next()
! 760: * on the iterator.
! 761: */
! 762: void
! 763: route_table_iter_pause (route_table_iter_t * iter)
! 764: {
! 765: switch (iter->state)
! 766: {
! 767:
! 768: case RT_ITER_STATE_INIT:
! 769: case RT_ITER_STATE_PAUSED:
! 770: case RT_ITER_STATE_DONE:
! 771: return;
! 772:
! 773: case RT_ITER_STATE_ITERATING:
! 774:
! 775: /*
! 776: * Save the prefix that we are currently at. The next call to
! 777: * route_table_iter_next() will return the node after this prefix
! 778: * in the tree.
! 779: */
! 780: prefix_copy (&iter->pause_prefix, &iter->current->p);
! 781: route_unlock_node (iter->current);
! 782: iter->current = NULL;
! 783: iter->state = RT_ITER_STATE_PAUSED;
! 784: return;
! 785:
! 786: default:
! 787: assert (0);
! 788: }
! 789:
! 790: }
! 791:
! 792: /*
! 793: * route_table_iter_cleanup
! 794: *
! 795: * Release any resources held by the iterator.
! 796: */
! 797: void
! 798: route_table_iter_cleanup (route_table_iter_t * iter)
! 799: {
! 800: if (iter->state == RT_ITER_STATE_ITERATING)
! 801: {
! 802: route_unlock_node (iter->current);
! 803: iter->current = NULL;
! 804: }
! 805: assert (!iter->current);
! 806:
! 807: /*
! 808: * Set the state to RT_ITER_STATE_DONE to make any
! 809: * route_table_iter_next() calls on this iterator return NULL.
! 810: */
! 811: iter->state = RT_ITER_STATE_DONE;
! 812: }
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