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