release/src/router/zebra/bgpd/bgp_table.c

   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 void bgp_node_delete (struct bgp_node *);
  32 void bgp_table_free (struct bgp_table *);
  33 \f
  34 struct bgp_table *
  35 bgp_table_init (void)
  36 {
  37   struct bgp_table *rt;
  38
  39   rt = XMALLOC (MTYPE_BGP_TABLE, sizeof (struct bgp_table));
  40   memset (rt, 0, sizeof (struct bgp_table));
  41   return rt;
  42 }
  43
  44 void
  45 bgp_table_finish (struct bgp_table *rt)
  46 {
  47   bgp_table_free (rt);
  48 }
  49
  50 struct bgp_node *
  51 bgp_node_create ()
  52 {
  53   struct bgp_node *rn;
  54
  55   rn = (struct bgp_node *) XMALLOC (MTYPE_BGP_NODE, sizeof (struct bgp_node));
  56   memset (rn, 0, sizeof (struct bgp_node));
  57   return rn;
  58 }
  59
  60 /* Allocate new route node with prefix set. */
  61 struct bgp_node *
  62 bgp_node_set (struct bgp_table *table, struct prefix *prefix)
  63 {
  64   struct bgp_node *node;
  65
  66   node = bgp_node_create ();
  67
  68   prefix_copy (&node->p, prefix);
  69   node->table = table;
  70
  71   return node;
  72 }
  73
  74 /* Free route node. */
  75 void
  76 bgp_node_free (struct bgp_node *node)
  77 {
  78   XFREE (MTYPE_BGP_NODE, node);
  79 }
  80
  81 /* Free route table. */
  82 void
  83 bgp_table_free (struct bgp_table *rt)
  84 {
  85   struct bgp_node *tmp_node;
  86   struct bgp_node *node;
  87
  88   if (rt == NULL)
  89     return;
  90
  91   node = rt->top;
  92
  93   while (node)
  94     {
  95       if (node->l_left)
  96         {
  97           node = node->l_left;
  98           continue;
  99         }
 100
 101       if (node->l_right)
 102         {
 103           node = node->l_right;
 104           continue;
 105         }
 106
 107       tmp_node = node;
 108       node = node->parent;
 109
 110       if (node != NULL)
 111         {
 112           if (node->l_left == tmp_node)
 113             node->l_left = NULL;
 114           else
 115             node->l_right = NULL;
 116
 117           bgp_node_free (tmp_node);
 118         }
 119       else
 120         {
 121           bgp_node_free (tmp_node);
 122           break;
 123         }
 124     }
 125
 126   XFREE (MTYPE_BGP_TABLE, rt);
 127   return;
 128 }
 129
 130 /* Utility mask array. */
 131 static u_char maskbit[] =
 132 {
 133   0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
 134 };
 135
 136 /* Common prefix route genaration. */
 137 static void
 138 route_common (struct prefix *n, struct prefix *p, struct prefix *new)
 139 {
 140   int i;
 141   u_char diff;
 142   u_char mask;
 143
 144   u_char *np = (u_char *)&n->u.prefix;
 145   u_char *pp = (u_char *)&p->u.prefix;
 146   u_char *newp = (u_char *)&new->u.prefix;
 147
 148   for (i = 0; i < p->prefixlen / 8; i++)
 149     {
 150       if (np[i] == pp[i])
 151         newp[i] = np[i];
 152       else
 153         break;
 154     }
 155
 156   new->prefixlen = i * 8;
 157
 158   if (new->prefixlen != p->prefixlen)
 159     {
 160       diff = np[i] ^ pp[i];
 161       mask = 0x80;
 162       while (new->prefixlen < p->prefixlen && !(mask & diff))
 163         {
 164           mask >>= 1;
 165           new->prefixlen++;
 166         }
 167       newp[i] = np[i] & maskbit[new->prefixlen % 8];
 168     }
 169 }
 170
 171 /* Macro version of check_bit (). */
 172 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
 173
 174 /* Check bit of the prefix. */
 175 static int
 176 check_bit (u_char *prefix, u_char prefixlen)
 177 {
 178   int offset;
 179   int shift;
 180   u_char *p = (u_char *)prefix;
 181
 182   assert (prefixlen <= 128);
 183
 184   offset = prefixlen / 8;
 185   shift = 7 - (prefixlen % 8);
 186
 187   return (p[offset] >> shift & 1);
 188 }
 189
 190 /* Macro version of set_link (). */
 191 #define SET_LINK(X,Y) (X)->link[CHECK_BIT(&(Y)->prefix,(X)->prefixlen)] = (Y);\
 192                       (Y)->parent = (X)
 193
 194 static void
 195 set_link (struct bgp_node *node, struct bgp_node *new)
 196 {
 197   int bit;
 198
 199   bit = check_bit (&new->p.u.prefix, node->p.prefixlen);
 200
 201   assert (bit == 0 || bit == 1);
 202
 203   node->link[bit] = new;
 204   new->parent = node;
 205 }
 206
 207 /* Lock node. */
 208 struct bgp_node *
 209 bgp_lock_node (struct bgp_node *node)
 210 {
 211   node->lock++;
 212   return node;
 213 }
 214
 215 /* Unlock node. */
 216 void
 217 bgp_unlock_node (struct bgp_node *node)
 218 {
 219   node->lock--;
 220
 221   if (node->lock == 0)
 222     bgp_node_delete (node);
 223 }
 224
 225 /* Find matched prefix. */
 226 struct bgp_node *
 227 bgp_node_match (struct bgp_table *table, struct prefix *p)
 228 {
 229   struct bgp_node *node;
 230   struct bgp_node *matched;
 231
 232   matched = NULL;
 233   node = table->top;
 234
 235   /* Walk down tree.  If there is matched route then store it to
 236      matched. */
 237   while (node && node->p.prefixlen <= p->prefixlen &&
 238          prefix_match (&node->p, p))
 239     {
 240       if (node->info)
 241         matched = node;
 242       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 243     }
 244
 245   /* If matched route found, return it. */
 246   if (matched)
 247     return bgp_lock_node (matched);
 248
 249   return NULL;
 250 }
 251
 252 struct bgp_node *
 253 bgp_node_match_ipv4 (struct bgp_table *table, struct in_addr *addr)
 254 {
 255   struct prefix_ipv4 p;
 256
 257   memset (&p, 0, sizeof (struct prefix_ipv4));
 258   p.family = AF_INET;
 259   p.prefixlen = IPV4_MAX_PREFIXLEN;
 260   p.prefix = *addr;
 261
 262   return bgp_node_match (table, (struct prefix *) &p);
 263 }
 264
 265 #ifdef HAVE_IPV6
 266 struct bgp_node *
 267 bgp_node_match_ipv6 (struct bgp_table *table, struct in6_addr *addr)
 268 {
 269   struct prefix_ipv6 p;
 270
 271   memset (&p, 0, sizeof (struct prefix_ipv6));
 272   p.family = AF_INET6;
 273   p.prefixlen = IPV6_MAX_PREFIXLEN;
 274   p.prefix = *addr;
 275
 276   return bgp_node_match (table, (struct prefix *) &p);
 277 }
 278 #endif /* HAVE_IPV6 */
 279
 280 /* Lookup same prefix node.  Return NULL when we can't find route. */
 281 struct bgp_node *
 282 bgp_node_lookup (struct bgp_table *table, struct prefix *p)
 283 {
 284   struct bgp_node *node;
 285
 286   node = table->top;
 287
 288   while (node && node->p.prefixlen <= p->prefixlen &&
 289          prefix_match (&node->p, p))
 290     {
 291       if (node->p.prefixlen == p->prefixlen && node->info)
 292         return bgp_lock_node (node);
 293
 294       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 295     }
 296
 297   return NULL;
 298 }
 299
 300 /* Add node to routing table. */
 301 struct bgp_node *
 302 bgp_node_get (struct bgp_table *table, struct prefix *p)
 303 {
 304   struct bgp_node *new;
 305   struct bgp_node *node;
 306   struct bgp_node *match;
 307
 308   match = NULL;
 309   node = table->top;
 310   while (node && node->p.prefixlen <= p->prefixlen &&
 311          prefix_match (&node->p, p))
 312     {
 313       if (node->p.prefixlen == p->prefixlen)
 314         {
 315           bgp_lock_node (node);
 316           return node;
 317         }
 318       match = node;
 319       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 320     }
 321
 322   if (node == NULL)
 323     {
 324       new = bgp_node_set (table, p);
 325       if (match)
 326         set_link (match, new);
 327       else
 328         table->top = new;
 329     }
 330   else
 331     {
 332       new = bgp_node_create ();
 333       route_common (&node->p, p, &new->p);
 334       new->p.family = p->family;
 335       new->table = table;
 336       set_link (new, node);
 337
 338       if (match)
 339         set_link (match, new);
 340       else
 341         table->top = new;
 342
 343       if (new->p.prefixlen != p->prefixlen)
 344         {
 345           match = new;
 346           new = bgp_node_set (table, p);
 347           set_link (match, new);
 348         }
 349     }
 350   bgp_lock_node (new);
 351
 352   return new;
 353 }
 354
 355 /* Delete node from the routing table. */
 356 void
 357 bgp_node_delete (struct bgp_node *node)
 358 {
 359   struct bgp_node *child;
 360   struct bgp_node *parent;
 361
 362   assert (node->lock == 0);
 363   assert (node->info == NULL);
 364
 365   if (node->l_left && node->l_right)
 366     return;
 367
 368   if (node->l_left)
 369     child = node->l_left;
 370   else
 371     child = node->l_right;
 372
 373   parent = node->parent;
 374
 375   if (child)
 376     child->parent = parent;
 377
 378   if (parent)
 379     {
 380       if (parent->l_left == node)
 381         parent->l_left = child;
 382       else
 383         parent->l_right = child;
 384     }
 385   else
 386     node->table->top = child;
 387
 388   bgp_node_free (node);
 389
 390   /* If parent node is stub then delete it also. */
 391   if (parent && parent->lock == 0)
 392     bgp_node_delete (parent);
 393 }
 394
 395 /* Get fist node and lock it.  This function is useful when one want
 396    to lookup all the node exist in the routing table. */
 397 struct bgp_node *
 398 bgp_table_top (struct bgp_table *table)
 399 {
 400   /* If there is no node in the routing table return NULL. */
 401   if (table->top == NULL)
 402     return NULL;
 403
 404   /* Lock the top node and return it. */
 405   bgp_lock_node (table->top);
 406   return table->top;
 407 }
 408
 409 /* Unlock current node and lock next node then return it. */
 410 struct bgp_node *
 411 bgp_route_next (struct bgp_node *node)
 412 {
 413   struct bgp_node *next;
 414   struct bgp_node *start;
 415
 416   /* Node may be deleted from bgp_unlock_node so we have to preserve
 417      next node's pointer. */
 418
 419   if (node->l_left)
 420     {
 421       next = node->l_left;
 422       bgp_lock_node (next);
 423       bgp_unlock_node (node);
 424       return next;
 425     }
 426   if (node->l_right)
 427     {
 428       next = node->l_right;
 429       bgp_lock_node (next);
 430       bgp_unlock_node (node);
 431       return next;
 432     }
 433
 434   start = node;
 435   while (node->parent)
 436     {
 437       if (node->parent->l_left == node && node->parent->l_right)
 438         {
 439           next = node->parent->l_right;
 440           bgp_lock_node (next);
 441           bgp_unlock_node (start);
 442           return next;
 443         }
 444       node = node->parent;
 445     }
 446   bgp_unlock_node (start);
 447   return NULL;
 448 }
 449
 450 /* Unlock current node and lock next node until limit. */
 451 struct bgp_node *
 452 bgp_route_next_until (struct bgp_node *node, struct bgp_node *limit)
 453 {
 454   struct bgp_node *next;
 455   struct bgp_node *start;
 456
 457   /* Node may be deleted from bgp_unlock_node so we have to preserve
 458      next node's pointer. */
 459
 460   if (node->l_left)
 461     {
 462       next = node->l_left;
 463       bgp_lock_node (next);
 464       bgp_unlock_node (node);
 465       return next;
 466     }
 467   if (node->l_right)
 468     {
 469       next = node->l_right;
 470       bgp_lock_node (next);
 471       bgp_unlock_node (node);
 472       return next;
 473     }
 474
 475   start = node;
 476   while (node->parent && node != limit)
 477     {
 478       if (node->parent->l_left == node && node->parent->l_right)
 479         {
 480           next = node->parent->l_right;
 481           bgp_lock_node (next);
 482           bgp_unlock_node (start);
 483           return next;
 484         }
 485       node = node->parent;
 486     }
 487   bgp_unlock_node (start);
 488   return NULL;
 489 }