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 static void bgp_node_delete (struct bgp_node *);
  32 static void bgp_table_free (struct bgp_table *);
  33 \f
  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 /* Macro version of check_bit (). */
 205 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
 206
 207 /* Check bit of the prefix. */
 208 static int
 209 check_bit (u_char *prefix, u_char prefixlen)
 210 {
 211   int offset;
 212   int shift;
 213   u_char *p = (u_char *)prefix;
 214
 215   assert (prefixlen <= 128);
 216
 217   offset = prefixlen / 8;
 218   shift = 7 - (prefixlen % 8);
 219
 220   return (p[offset] >> shift & 1);
 221 }
 222
 223 /* Macro version of set_link (). */
 224 #define SET_LINK(X,Y) (X)->link[CHECK_BIT(&(Y)->prefix,(X)->prefixlen)] = (Y);\
 225                       (Y)->parent = (X)
 226
 227 static void
 228 set_link (struct bgp_node *node, struct bgp_node *new)
 229 {
 230   int bit;
 231
 232   bit = check_bit (&new->p.u.prefix, node->p.prefixlen);
 233
 234   assert (bit == 0 || bit == 1);
 235
 236   node->link[bit] = new;
 237   new->parent = node;
 238 }
 239
 240 /* Lock node. */
 241 struct bgp_node *
 242 bgp_lock_node (struct bgp_node *node)
 243 {
 244   node->lock++;
 245   return node;
 246 }
 247
 248 /* Unlock node. */
 249 void
 250 bgp_unlock_node (struct bgp_node *node)
 251 {
 252   assert (node->lock > 0);
 253   node->lock--;
 254
 255   if (node->lock == 0)
 256     bgp_node_delete (node);
 257 }
 258
 259 /* Find matched prefix. */
 260 struct bgp_node *
 261 bgp_node_match (const struct bgp_table *table, struct prefix *p)
 262 {
 263   struct bgp_node *node;
 264   struct bgp_node *matched;
 265
 266   matched = NULL;
 267   node = table->top;
 268
 269   /* Walk down tree.  If there is matched route then store it to
 270      matched. */
 271   while (node && node->p.prefixlen <= p->prefixlen &&
 272          prefix_match (&node->p, p))
 273     {
 274       if (node->info)
 275         matched = node;
 276       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 277     }
 278
 279   /* If matched route found, return it. */
 280   if (matched)
 281     return bgp_lock_node (matched);
 282
 283   return NULL;
 284 }
 285
 286 struct bgp_node *
 287 bgp_node_match_ipv4 (const struct bgp_table *table, struct in_addr *addr)
 288 {
 289   struct prefix_ipv4 p;
 290
 291   memset (&p, 0, sizeof (struct prefix_ipv4));
 292   p.family = AF_INET;
 293   p.prefixlen = IPV4_MAX_PREFIXLEN;
 294   p.prefix = *addr;
 295
 296   return bgp_node_match (table, (struct prefix *) &p);
 297 }
 298
 299 #ifdef HAVE_IPV6
 300 struct bgp_node *
 301 bgp_node_match_ipv6 (const struct bgp_table *table, struct in6_addr *addr)
 302 {
 303   struct prefix_ipv6 p;
 304
 305   memset (&p, 0, sizeof (struct prefix_ipv6));
 306   p.family = AF_INET6;
 307   p.prefixlen = IPV6_MAX_PREFIXLEN;
 308   p.prefix = *addr;
 309
 310   return bgp_node_match (table, (struct prefix *) &p);
 311 }
 312 #endif /* HAVE_IPV6 */
 313
 314 /* Lookup same prefix node.  Return NULL when we can't find route. */
 315 struct bgp_node *
 316 bgp_node_lookup (const struct bgp_table *table, struct prefix *p)
 317 {
 318   struct bgp_node *node;
 319
 320   node = table->top;
 321
 322   while (node && node->p.prefixlen <= p->prefixlen &&
 323          prefix_match (&node->p, p))
 324     {
 325       if (node->p.prefixlen == p->prefixlen && node->info)
 326         return bgp_lock_node (node);
 327
 328       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 329     }
 330
 331   return NULL;
 332 }
 333
 334 /* Add node to routing table. */
 335 struct bgp_node *
 336 bgp_node_get (struct bgp_table *const table, struct prefix *p)
 337 {
 338   struct bgp_node *new;
 339   struct bgp_node *node;
 340   struct bgp_node *match;
 341
 342   match = NULL;
 343   node = table->top;
 344   while (node && node->p.prefixlen <= p->prefixlen &&
 345          prefix_match (&node->p, p))
 346     {
 347       if (node->p.prefixlen == p->prefixlen)
 348         {
 349           bgp_lock_node (node);
 350           return node;
 351         }
 352       match = node;
 353       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 354     }
 355
 356   if (node == NULL)
 357     {
 358       new = bgp_node_set (table, p);
 359       if (match)
 360         set_link (match, new);
 361       else
 362         table->top = new;
 363     }
 364   else
 365     {
 366       new = bgp_node_create ();
 367       route_common (&node->p, p, &new->p);
 368       new->p.family = p->family;
 369       new->table = table;
 370       set_link (new, node);
 371
 372       if (match)
 373         set_link (match, new);
 374       else
 375         table->top = new;
 376
 377       if (new->p.prefixlen != p->prefixlen)
 378         {
 379           match = new;
 380           bgp_lock_node (match);
 381           new = bgp_node_set (table, p);
 382           set_link (match, new);
 383           table->count++;
 384         }
 385     }
 386   table->count++;
 387   bgp_lock_node (new);
 388
 389   return new;
 390 }
 391
 392 /* Delete node from the routing table. */
 393 static void
 394 bgp_node_delete (struct bgp_node *node)
 395 {
 396   struct bgp_node *child;
 397   struct bgp_node *parent;
 398
 399   assert (node->lock == 0);
 400   assert (node->info == NULL);
 401
 402   if (node->l_left && node->l_right)
 403     return;
 404
 405   if (node->l_left)
 406     child = node->l_left;
 407   else
 408     child = node->l_right;
 409
 410   parent = node->parent;
 411
 412   if (child)
 413     child->parent = parent;
 414
 415   if (parent)
 416     {
 417       if (parent->l_left == node)
 418         parent->l_left = child;
 419       else
 420         parent->l_right = child;
 421     }
 422   else
 423     node->table->top = child;
 424
 425   node->table->count--;
 426
 427   bgp_node_free (node);
 428
 429   /* If parent node is stub then delete it also. */
 430   if (parent && parent->lock == 0)
 431     bgp_node_delete (parent);
 432 }
 433
 434 /* Get fist node and lock it.  This function is useful when one want
 435    to lookup all the node exist in the routing table. */
 436 struct bgp_node *
 437 bgp_table_top (const struct bgp_table *const table)
 438 {
 439   /* If there is no node in the routing table return NULL. */
 440   if (table->top == NULL)
 441     return NULL;
 442
 443   /* Lock the top node and return it. */
 444   bgp_lock_node (table->top);
 445   return table->top;
 446 }
 447
 448 /* Unlock current node and lock next node then return it. */
 449 struct bgp_node *
 450 bgp_route_next (struct bgp_node *node)
 451 {
 452   struct bgp_node *next;
 453   struct bgp_node *start;
 454
 455   /* Node may be deleted from bgp_unlock_node so we have to preserve
 456      next node's pointer. */
 457
 458   if (node->l_left)
 459     {
 460       next = node->l_left;
 461       bgp_lock_node (next);
 462       bgp_unlock_node (node);
 463       return next;
 464     }
 465   if (node->l_right)
 466     {
 467       next = node->l_right;
 468       bgp_lock_node (next);
 469       bgp_unlock_node (node);
 470       return next;
 471     }
 472
 473   start = node;
 474   while (node->parent)
 475     {
 476       if (node->parent->l_left == node && node->parent->l_right)
 477         {
 478           next = node->parent->l_right;
 479           bgp_lock_node (next);
 480           bgp_unlock_node (start);
 481           return next;
 482         }
 483       node = node->parent;
 484     }
 485   bgp_unlock_node (start);
 486   return NULL;
 487 }
 488
 489 /* Unlock current node and lock next node until limit. */
 490 struct bgp_node *
 491 bgp_route_next_until (struct bgp_node *node, struct bgp_node *limit)
 492 {
 493   struct bgp_node *next;
 494   struct bgp_node *start;
 495
 496   /* Node may be deleted from bgp_unlock_node so we have to preserve
 497      next node's pointer. */
 498
 499   if (node->l_left)
 500     {
 501       next = node->l_left;
 502       bgp_lock_node (next);
 503       bgp_unlock_node (node);
 504       return next;
 505     }
 506   if (node->l_right)
 507     {
 508       next = node->l_right;
 509       bgp_lock_node (next);
 510       bgp_unlock_node (node);
 511       return next;
 512     }
 513
 514   start = node;
 515   while (node->parent && node != limit)
 516     {
 517       if (node->parent->l_left == node && node->parent->l_right)
 518         {
 519           next = node->parent->l_right;
 520           bgp_lock_node (next);
 521           bgp_unlock_node (start);
 522           return next;
 523         }
 524       node = node->parent;
 525     }
 526   bgp_unlock_node (start);
 527   return NULL;
 528 }
 529
 530 unsigned long
 531 bgp_table_count (const struct bgp_table *table)
 532 {
 533   return table->count;
 534 }