Annotation of embedaddon/quagga/bgpd/bgp_table.c, revision 1.1
1.1 ! misho 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