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