1: /* BGP routing table
2: Copyright (C) 1998, 2001 Kunihiro Ishiguro
3:
4: This file is part of GNU Zebra.
5:
6: GNU Zebra is free software; you can redistribute it and/or modify it
7: under the terms of the GNU General Public License as published by the
8: Free Software Foundation; either version 2, or (at your option) any
9: later version.
10:
11: GNU Zebra is distributed in the hope that it will be useful, but
12: WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU Zebra; see the file COPYING. If not, write to the Free
18: Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
19: 02111-1307, USA. */
20:
21: #include <zebra.h>
22:
23: #include "prefix.h"
24: #include "memory.h"
25: #include "sockunion.h"
26: #include "vty.h"
27:
28: #include "bgpd/bgpd.h"
29: #include "bgpd/bgp_table.h"
30:
31: static void bgp_node_delete (struct bgp_node *);
32: static void bgp_table_free (struct bgp_table *);
33:
34: struct bgp_table *
35: bgp_table_init (afi_t afi, safi_t safi)
36: {
37: struct bgp_table *rt;
38:
39: rt = XCALLOC (MTYPE_BGP_TABLE, sizeof (struct bgp_table));
40:
41: bgp_table_lock(rt);
42: rt->type = BGP_TABLE_MAIN;
43: rt->afi = afi;
44: rt->safi = safi;
45:
46: return rt;
47: }
48:
49: void
50: bgp_table_lock (struct bgp_table *rt)
51: {
52: rt->lock++;
53: }
54:
55: void
56: bgp_table_unlock (struct bgp_table *rt)
57: {
58: assert (rt->lock > 0);
59: rt->lock--;
60:
61: if (rt->lock == 0)
62: bgp_table_free (rt);
63: }
64:
65: void
66: bgp_table_finish (struct bgp_table **rt)
67: {
68: if (*rt != NULL)
69: {
70: bgp_table_unlock(*rt);
71: *rt = NULL;
72: }
73: }
74:
75: static struct bgp_node *
76: bgp_node_create (void)
77: {
78: return XCALLOC (MTYPE_BGP_NODE, sizeof (struct bgp_node));
79: }
80:
81: /* Allocate new route node with prefix set. */
82: static struct bgp_node *
83: bgp_node_set (struct bgp_table *table, struct prefix *prefix)
84: {
85: struct bgp_node *node;
86:
87: node = bgp_node_create ();
88:
89: prefix_copy (&node->p, prefix);
90: node->table = table;
91:
92: return node;
93: }
94:
95: /* Free route node. */
96: static void
97: bgp_node_free (struct bgp_node *node)
98: {
99: XFREE (MTYPE_BGP_NODE, node);
100: }
101:
102: /* Free route table. */
103: static void
104: bgp_table_free (struct bgp_table *rt)
105: {
106: struct bgp_node *tmp_node;
107: struct bgp_node *node;
108:
109: if (rt == NULL)
110: return;
111:
112: node = rt->top;
113:
114: /* Bulk deletion of nodes remaining in this table. This function is not
115: called until workers have completed their dependency on this table.
116: A final bgp_unlock_node() will not be called for these nodes. */
117: while (node)
118: {
119: if (node->l_left)
120: {
121: node = node->l_left;
122: continue;
123: }
124:
125: if (node->l_right)
126: {
127: node = node->l_right;
128: continue;
129: }
130:
131: tmp_node = node;
132: node = node->parent;
133:
134: tmp_node->table->count--;
135: tmp_node->lock = 0; /* to cause assert if unlocked after this */
136: bgp_node_free (tmp_node);
137:
138: if (node != NULL)
139: {
140: if (node->l_left == tmp_node)
141: node->l_left = NULL;
142: else
143: node->l_right = NULL;
144: }
145: else
146: {
147: break;
148: }
149: }
150:
151: assert (rt->count == 0);
152:
153: if (rt->owner)
154: {
155: peer_unlock (rt->owner);
156: rt->owner = NULL;
157: }
158:
159: XFREE (MTYPE_BGP_TABLE, rt);
160: return;
161: }
162:
163: /* Utility mask array. */
164: static u_char maskbit[] =
165: {
166: 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
167: };
168:
169: /* Common prefix route genaration. */
170: static void
171: route_common (struct prefix *n, struct prefix *p, struct prefix *new)
172: {
173: int i;
174: u_char diff;
175: u_char mask;
176:
177: u_char *np = (u_char *)&n->u.prefix;
178: u_char *pp = (u_char *)&p->u.prefix;
179: u_char *newp = (u_char *)&new->u.prefix;
180:
181: for (i = 0; i < p->prefixlen / 8; i++)
182: {
183: if (np[i] == pp[i])
184: newp[i] = np[i];
185: else
186: break;
187: }
188:
189: new->prefixlen = i * 8;
190:
191: if (new->prefixlen != p->prefixlen)
192: {
193: diff = np[i] ^ pp[i];
194: mask = 0x80;
195: while (new->prefixlen < p->prefixlen && !(mask & diff))
196: {
197: mask >>= 1;
198: new->prefixlen++;
199: }
200: newp[i] = np[i] & maskbit[new->prefixlen % 8];
201: }
202: }
203:
204: static void
205: set_link (struct bgp_node *node, struct bgp_node *new)
206: {
207: unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
208:
209: node->link[bit] = new;
210: new->parent = node;
211: }
212:
213: /* Lock node. */
214: struct bgp_node *
215: bgp_lock_node (struct bgp_node *node)
216: {
217: node->lock++;
218: return node;
219: }
220:
221: /* Unlock node. */
222: void
223: bgp_unlock_node (struct bgp_node *node)
224: {
225: assert (node->lock > 0);
226: node->lock--;
227:
228: if (node->lock == 0)
229: bgp_node_delete (node);
230: }
231:
232: /* Find matched prefix. */
233: struct bgp_node *
234: bgp_node_match (const struct bgp_table *table, struct prefix *p)
235: {
236: struct bgp_node *node;
237: struct bgp_node *matched;
238:
239: matched = NULL;
240: node = table->top;
241:
242: /* Walk down tree. If there is matched route then store it to
243: matched. */
244: while (node && node->p.prefixlen <= p->prefixlen &&
245: prefix_match (&node->p, p))
246: {
247: if (node->info)
248: matched = node;
249: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
250: }
251:
252: /* If matched route found, return it. */
253: if (matched)
254: return bgp_lock_node (matched);
255:
256: return NULL;
257: }
258:
259: struct bgp_node *
260: bgp_node_match_ipv4 (const struct bgp_table *table, struct in_addr *addr)
261: {
262: struct prefix_ipv4 p;
263:
264: memset (&p, 0, sizeof (struct prefix_ipv4));
265: p.family = AF_INET;
266: p.prefixlen = IPV4_MAX_PREFIXLEN;
267: p.prefix = *addr;
268:
269: return bgp_node_match (table, (struct prefix *) &p);
270: }
271:
272: #ifdef HAVE_IPV6
273: struct bgp_node *
274: bgp_node_match_ipv6 (const struct bgp_table *table, struct in6_addr *addr)
275: {
276: struct prefix_ipv6 p;
277:
278: memset (&p, 0, sizeof (struct prefix_ipv6));
279: p.family = AF_INET6;
280: p.prefixlen = IPV6_MAX_PREFIXLEN;
281: p.prefix = *addr;
282:
283: return bgp_node_match (table, (struct prefix *) &p);
284: }
285: #endif /* HAVE_IPV6 */
286:
287: /* Lookup same prefix node. Return NULL when we can't find route. */
288: struct bgp_node *
289: bgp_node_lookup (const struct bgp_table *table, struct prefix *p)
290: {
291: struct bgp_node *node;
292:
293: node = table->top;
294:
295: while (node && node->p.prefixlen <= p->prefixlen &&
296: prefix_match (&node->p, p))
297: {
298: if (node->p.prefixlen == p->prefixlen && node->info)
299: return bgp_lock_node (node);
300:
301: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
302: }
303:
304: return NULL;
305: }
306:
307: /* Add node to routing table. */
308: struct bgp_node *
309: bgp_node_get (struct bgp_table *const table, struct prefix *p)
310: {
311: struct bgp_node *new;
312: struct bgp_node *node;
313: struct bgp_node *match;
314:
315: match = NULL;
316: node = table->top;
317: while (node && node->p.prefixlen <= p->prefixlen &&
318: prefix_match (&node->p, p))
319: {
320: if (node->p.prefixlen == p->prefixlen)
321: {
322: bgp_lock_node (node);
323: return node;
324: }
325: match = node;
326: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
327: }
328:
329: if (node == NULL)
330: {
331: new = bgp_node_set (table, p);
332: if (match)
333: set_link (match, new);
334: else
335: table->top = new;
336: }
337: else
338: {
339: new = bgp_node_create ();
340: route_common (&node->p, p, &new->p);
341: new->p.family = p->family;
342: new->table = table;
343: set_link (new, node);
344:
345: if (match)
346: set_link (match, new);
347: else
348: table->top = new;
349:
350: if (new->p.prefixlen != p->prefixlen)
351: {
352: match = new;
353: new = bgp_node_set (table, p);
354: set_link (match, new);
355: table->count++;
356: }
357: }
358: table->count++;
359: bgp_lock_node (new);
360:
361: return new;
362: }
363:
364: /* Delete node from the routing table. */
365: static void
366: bgp_node_delete (struct bgp_node *node)
367: {
368: struct bgp_node *child;
369: struct bgp_node *parent;
370:
371: assert (node->lock == 0);
372: assert (node->info == NULL);
373:
374: if (node->l_left && node->l_right)
375: return;
376:
377: if (node->l_left)
378: child = node->l_left;
379: else
380: child = node->l_right;
381:
382: parent = node->parent;
383:
384: if (child)
385: child->parent = parent;
386:
387: if (parent)
388: {
389: if (parent->l_left == node)
390: parent->l_left = child;
391: else
392: parent->l_right = child;
393: }
394: else
395: node->table->top = child;
396:
397: node->table->count--;
398:
399: bgp_node_free (node);
400:
401: /* If parent node is stub then delete it also. */
402: if (parent && parent->lock == 0)
403: bgp_node_delete (parent);
404: }
405:
406: /* Get fist node and lock it. This function is useful when one want
407: to lookup all the node exist in the routing table. */
408: struct bgp_node *
409: bgp_table_top (const struct bgp_table *const table)
410: {
411: /* If there is no node in the routing table return NULL. */
412: if (table->top == NULL)
413: return NULL;
414:
415: /* Lock the top node and return it. */
416: bgp_lock_node (table->top);
417: return table->top;
418: }
419:
420: /* Unlock current node and lock next node then return it. */
421: struct bgp_node *
422: bgp_route_next (struct bgp_node *node)
423: {
424: struct bgp_node *next;
425: struct bgp_node *start;
426:
427: /* Node may be deleted from bgp_unlock_node so we have to preserve
428: next node's pointer. */
429:
430: if (node->l_left)
431: {
432: next = node->l_left;
433: bgp_lock_node (next);
434: bgp_unlock_node (node);
435: return next;
436: }
437: if (node->l_right)
438: {
439: next = node->l_right;
440: bgp_lock_node (next);
441: bgp_unlock_node (node);
442: return next;
443: }
444:
445: start = node;
446: while (node->parent)
447: {
448: if (node->parent->l_left == node && node->parent->l_right)
449: {
450: next = node->parent->l_right;
451: bgp_lock_node (next);
452: bgp_unlock_node (start);
453: return next;
454: }
455: node = node->parent;
456: }
457: bgp_unlock_node (start);
458: return NULL;
459: }
460:
461: /* Unlock current node and lock next node until limit. */
462: struct bgp_node *
463: bgp_route_next_until (struct bgp_node *node, struct bgp_node *limit)
464: {
465: struct bgp_node *next;
466: struct bgp_node *start;
467:
468: /* Node may be deleted from bgp_unlock_node so we have to preserve
469: next node's pointer. */
470:
471: if (node->l_left)
472: {
473: next = node->l_left;
474: bgp_lock_node (next);
475: bgp_unlock_node (node);
476: return next;
477: }
478: if (node->l_right)
479: {
480: next = node->l_right;
481: bgp_lock_node (next);
482: bgp_unlock_node (node);
483: return next;
484: }
485:
486: start = node;
487: while (node->parent && node != limit)
488: {
489: if (node->parent->l_left == node && node->parent->l_right)
490: {
491: next = node->parent->l_right;
492: bgp_lock_node (next);
493: bgp_unlock_node (start);
494: return next;
495: }
496: node = node->parent;
497: }
498: bgp_unlock_node (start);
499: return NULL;
500: }
501:
502: unsigned long
503: bgp_table_count (const struct bgp_table *table)
504: {
505: return table->count;
506: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bgp_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 / bgpd