lib/table.c

   1 /*
   2  * Routing Table functions.
   3  * Copyright (C) 1998 Kunihiro Ishiguro
   4  *
   5  * This file is part of GNU Zebra.
   6  *
   7  * GNU Zebra is free software; you can redistribute it and/or modify it
   8  * under the terms of the GNU General Public License as published by the
   9  * Free Software Foundation; either version 2, or (at your option) any
  10  * later version.
  11  *
  12  * GNU Zebra is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  19  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20  * 02111-1307, USA.
  21  */
  22
  23 #include <zebra.h>
  24
  25 #include "prefix.h"
  26 #include "table.h"
  27 #include "memory.h"
  28 #include "sockunion.h"
  29
  30 void route_node_delete (struct route_node *);
  31 void route_table_free (struct route_table *);
  32 \f
  33 struct route_table *
  34 route_table_init (void)
  35 {
  36   struct route_table *rt;
  37
  38   rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
  39   return rt;
  40 }
  41
  42 void
  43 route_table_finish (struct route_table *rt)
  44 {
  45   route_table_free (rt);
  46 }
  47
  48 /* Allocate new route node. */
  49 static struct route_node *
  50 route_node_new (void)
  51 {
  52   struct route_node *node;
  53   node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
  54   return node;
  55 }
  56
  57 /* Allocate new route node with prefix set. */
  58 static struct route_node *
  59 route_node_set (struct route_table *table, struct prefix *prefix)
  60 {
  61   struct route_node *node;
  62
  63   node = route_node_new ();
  64
  65   prefix_copy (&node->p, prefix);
  66   node->table = table;
  67
  68   return node;
  69 }
  70
  71 /* Free route node. */
  72 static void
  73 route_node_free (struct route_node *node)
  74 {
  75   XFREE (MTYPE_ROUTE_NODE, node);
  76 }
  77
  78 /* Free route table. */
  79 void
  80 route_table_free (struct route_table *rt)
  81 {
  82   struct route_node *tmp_node;
  83   struct route_node *node;
  84
  85   if (rt == NULL)
  86     return;
  87
  88   node = rt->top;
  89
  90   while (node)
  91     {
  92       if (node->l_left)
  93         {
  94           node = node->l_left;
  95           continue;
  96         }
  97
  98       if (node->l_right)
  99         {
 100           node = node->l_right;
 101           continue;
 102         }
 103
 104       tmp_node = node;
 105       node = node->parent;
 106
 107       if (node != NULL)
 108         {
 109           if (node->l_left == tmp_node)
 110             node->l_left = NULL;
 111           else
 112             node->l_right = NULL;
 113
 114           route_node_free (tmp_node);
 115         }
 116       else
 117         {
 118           route_node_free (tmp_node);
 119           break;
 120         }
 121     }
 122
 123   XFREE (MTYPE_ROUTE_TABLE, rt);
 124   return;
 125 }
 126
 127 /* Utility mask array. */
 128 static u_char maskbit[] =
 129 {
 130   0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
 131 };
 132
 133 /* Common prefix route genaration. */
 134 static void
 135 route_common (struct prefix *n, struct prefix *p, struct prefix *new)
 136 {
 137   int i;
 138   u_char diff;
 139   u_char mask;
 140
 141   u_char *np = (u_char *)&n->u.prefix;
 142   u_char *pp = (u_char *)&p->u.prefix;
 143   u_char *newp = (u_char *)&new->u.prefix;
 144
 145   for (i = 0; i < p->prefixlen / 8; i++)
 146     {
 147       if (np[i] == pp[i])
 148         newp[i] = np[i];
 149       else
 150         break;
 151     }
 152
 153   new->prefixlen = i * 8;
 154
 155   if (new->prefixlen != p->prefixlen)
 156     {
 157       diff = np[i] ^ pp[i];
 158       mask = 0x80;
 159       while (new->prefixlen < p->prefixlen && !(mask & diff))
 160         {
 161           mask >>= 1;
 162           new->prefixlen++;
 163         }
 164       newp[i] = np[i] & maskbit[new->prefixlen % 8];
 165     }
 166 }
 167
 168 /* Macro version of check_bit (). */
 169 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
 170
 171 /* Check bit of the prefix. */
 172 static int
 173 check_bit (u_char *prefix, u_char prefixlen)
 174 {
 175   int offset;
 176   int shift;
 177   u_char *p = (u_char *)prefix;
 178
 179   assert (prefixlen <= 128);
 180
 181   offset = prefixlen / 8;
 182   shift = 7 - (prefixlen % 8);
 183
 184   return (p[offset] >> shift & 1);
 185 }
 186
 187 /* Macro version of set_link (). */
 188 #define SET_LINK(X,Y) do { (X)->link[CHECK_BIT(&(Y)->p.u.prefix,(X)->p.prefixlen)] = (Y);\
 189                       (Y)->parent = (X); } while (0)
 190
 191 static void
 192 set_link (struct route_node *node, struct route_node *new)
 193 {
 194   int bit;
 195
 196   bit = check_bit (&new->p.u.prefix, node->p.prefixlen);
 197
 198   assert (bit == 0 || bit == 1);
 199
 200   node->link[bit] = new;
 201   new->parent = node;
 202 }
 203
 204 /* Lock node. */
 205 struct route_node *
 206 route_lock_node (struct route_node *node)
 207 {
 208   node->lock++;
 209   return node;
 210 }
 211
 212 /* Unlock node. */
 213 void
 214 route_unlock_node (struct route_node *node)
 215 {
 216   node->lock--;
 217
 218   if (node->lock == 0)
 219     route_node_delete (node);
 220 }
 221
 222 /* Dump routing table. */
 223 static void __attribute__ ((unused))
 224 route_dump_node (struct route_table *t)
 225 {
 226   struct route_node *node;
 227   char buf[46];
 228
 229   for (node = route_top (t); node != NULL; node = route_next (node))
 230     {
 231       printf ("[%d] %p %s/%d\n",
 232               node->lock,
 233               node->info,
 234               inet_ntop (node->p.family, &node->p.u.prefix, buf, 46),
 235               node->p.prefixlen);
 236     }
 237 }
 238
 239 /* Find matched prefix. */
 240 struct route_node *
 241 route_node_match (struct route_table *table, struct prefix *p)
 242 {
 243   struct route_node *node;
 244   struct route_node *matched;
 245
 246   matched = NULL;
 247   node = table->top;
 248
 249   /* Walk down tree.  If there is matched route then store it to
 250      matched. */
 251   while (node && node->p.prefixlen <= p->prefixlen &&
 252          prefix_match (&node->p, p))
 253     {
 254       if (node->info)
 255         matched = node;
 256       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 257     }
 258
 259   /* If matched route found, return it. */
 260   if (matched)
 261     return route_lock_node (matched);
 262
 263   return NULL;
 264 }
 265
 266 struct route_node *
 267 route_node_match_ipv4 (struct route_table *table, struct in_addr *addr)
 268 {
 269   struct prefix_ipv4 p;
 270
 271   memset (&p, 0, sizeof (struct prefix_ipv4));
 272   p.family = AF_INET;
 273   p.prefixlen = IPV4_MAX_PREFIXLEN;
 274   p.prefix = *addr;
 275
 276   return route_node_match (table, (struct prefix *) &p);
 277 }
 278
 279 #ifdef HAVE_IPV6
 280 struct route_node *
 281 route_node_match_ipv6 (struct route_table *table, struct in6_addr *addr)
 282 {
 283   struct prefix_ipv6 p;
 284
 285   memset (&p, 0, sizeof (struct prefix_ipv6));
 286   p.family = AF_INET6;
 287   p.prefixlen = IPV6_MAX_PREFIXLEN;
 288   p.prefix = *addr;
 289
 290   return route_node_match (table, (struct prefix *) &p);
 291 }
 292 #endif /* HAVE_IPV6 */
 293
 294 /* Lookup same prefix node.  Return NULL when we can't find route. */
 295 struct route_node *
 296 route_node_lookup (struct route_table *table, struct prefix *p)
 297 {
 298   struct route_node *node;
 299
 300   node = table->top;
 301
 302   while (node && node->p.prefixlen <= p->prefixlen &&
 303          prefix_match (&node->p, p))
 304     {
 305       if (node->p.prefixlen == p->prefixlen && node->info)
 306         return route_lock_node (node);
 307
 308       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 309     }
 310
 311   return NULL;
 312 }
 313
 314 /* Add node to routing table. */
 315 struct route_node *
 316 route_node_get (struct route_table *table, struct prefix *p)
 317 {
 318   struct route_node *new;
 319   struct route_node *node;
 320   struct route_node *match;
 321
 322   match = NULL;
 323   node = table->top;
 324   while (node && node->p.prefixlen <= p->prefixlen &&
 325          prefix_match (&node->p, p))
 326     {
 327       if (node->p.prefixlen == p->prefixlen)
 328         {
 329           route_lock_node (node);
 330           return node;
 331         }
 332       match = node;
 333       node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
 334     }
 335
 336   if (node == NULL)
 337     {
 338       new = route_node_set (table, p);
 339       if (match)
 340         set_link (match, new);
 341       else
 342         table->top = new;
 343     }
 344   else
 345     {
 346       new = route_node_new ();
 347       route_common (&node->p, p, &new->p);
 348       new->p.family = p->family;
 349       new->table = table;
 350       set_link (new, node);
 351
 352       if (match)
 353         set_link (match, new);
 354       else
 355         table->top = new;
 356
 357       if (new->p.prefixlen != p->prefixlen)
 358         {
 359           match = new;
 360           new = route_node_set (table, p);
 361           set_link (match, new);
 362         }
 363     }
 364   route_lock_node (new);
 365
 366   return new;
 367 }
 368
 369 /* Delete node from the routing table. */
 370 void
 371 route_node_delete (struct route_node *node)
 372 {
 373   struct route_node *child;
 374   struct route_node *parent;
 375
 376   assert (node->lock == 0);
 377   assert (node->info == NULL);
 378
 379   if (node->l_left && node->l_right)
 380     return;
 381
 382   if (node->l_left)
 383     child = node->l_left;
 384   else
 385     child = node->l_right;
 386
 387   parent = node->parent;
 388
 389   if (child)
 390     child->parent = parent;
 391
 392   if (parent)
 393     {
 394       if (parent->l_left == node)
 395         parent->l_left = child;
 396       else
 397         parent->l_right = child;
 398     }
 399   else
 400     node->table->top = child;
 401
 402   route_node_free (node);
 403
 404   /* If parent node is stub then delete it also. */
 405   if (parent && parent->lock == 0)
 406     route_node_delete (parent);
 407 }
 408
 409 /* Get fist node and lock it.  This function is useful when one want
 410    to lookup all the node exist in the routing table. */
 411 struct route_node *
 412 route_top (struct route_table *table)
 413 {
 414   /* If there is no node in the routing table return NULL. */
 415   if (table->top == NULL)
 416     return NULL;
 417
 418   /* Lock the top node and return it. */
 419   route_lock_node (table->top);
 420   return table->top;
 421 }
 422
 423 /* Unlock current node and lock next node then return it. */
 424 struct route_node *
 425 route_next (struct route_node *node)
 426 {
 427   struct route_node *next;
 428   struct route_node *start;
 429
 430   /* Node may be deleted from route_unlock_node so we have to preserve
 431      next node's pointer. */
 432
 433   if (node->l_left)
 434     {
 435       next = node->l_left;
 436       route_lock_node (next);
 437       route_unlock_node (node);
 438       return next;
 439     }
 440   if (node->l_right)
 441     {
 442       next = node->l_right;
 443       route_lock_node (next);
 444       route_unlock_node (node);
 445       return next;
 446     }
 447
 448   start = node;
 449   while (node->parent)
 450     {
 451       if (node->parent->l_left == node && node->parent->l_right)
 452         {
 453           next = node->parent->l_right;
 454           route_lock_node (next);
 455           route_unlock_node (start);
 456           return next;
 457         }
 458       node = node->parent;
 459     }
 460   route_unlock_node (start);
 461   return NULL;
 462 }
 463
 464 /* Unlock current node and lock next node until limit. */
 465 struct route_node *
 466 route_next_until (struct route_node *node, struct route_node *limit)
 467 {
 468   struct route_node *next;
 469   struct route_node *start;
 470
 471   /* Node may be deleted from route_unlock_node so we have to preserve
 472      next node's pointer. */
 473
 474   if (node->l_left)
 475     {
 476       next = node->l_left;
 477       route_lock_node (next);
 478       route_unlock_node (node);
 479       return next;
 480     }
 481   if (node->l_right)
 482     {
 483       next = node->l_right;
 484       route_lock_node (next);
 485       route_unlock_node (node);
 486       return next;
 487     }
 488
 489   start = node;
 490   while (node->parent && node != limit)
 491     {
 492       if (node->parent->l_left == node && node->parent->l_right)
 493         {
 494           next = node->parent->l_right;
 495           route_lock_node (next);
 496           route_unlock_node (start);
 497           return next;
 498         }
 499       node = node->parent;
 500     }
 501   route_unlock_node (start);
 502   return NULL;
 503 }