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