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 const 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 static void
 169 set_link (struct route_node *node, struct route_node *new)
 170 {
 171   unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
 172
 173   node->link[bit] = new;
 174   new->parent = node;
 175 }
 176
 177 /* Lock node. */
 178 struct route_node *
 179 route_lock_node (struct route_node *node)
 180 {
 181   node->lock++;
 182   return node;
 183 }
 184
 185 /* Unlock node. */
 186 void
 187 route_unlock_node (struct route_node *node)
 188 {
 189   node->lock--;
 190
 191   if (node->lock == 0)
 192     route_node_delete (node);
 193 }
 194
 195 /* Find matched prefix. */
 196 struct route_node *
 197 route_node_match (const struct route_table *table, const struct prefix *p)
 198 {
 199   struct route_node *node;
 200   struct route_node *matched;
 201
 202   matched = NULL;
 203   node = table->top;
 204
 205   /* Walk down tree.  If there is matched route then store it to
 206      matched. */
 207   while (node && node->p.prefixlen <= p->prefixlen &&
 208          prefix_match (&node->p, p))
 209     {
 210       if (node->info)
 211         matched = node;
 212
 213       if (node->p.prefixlen == p->prefixlen)
 214         break;
 215
 216       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
 217     }
 218
 219   /* If matched route found, return it. */
 220   if (matched)
 221     return route_lock_node (matched);
 222
 223   return NULL;
 224 }
 225
 226 struct route_node *
 227 route_node_match_ipv4 (const struct route_table *table,
 228                        const struct in_addr *addr)
 229 {
 230   struct prefix_ipv4 p;
 231
 232   memset (&p, 0, sizeof (struct prefix_ipv4));
 233   p.family = AF_INET;
 234   p.prefixlen = IPV4_MAX_PREFIXLEN;
 235   p.prefix = *addr;
 236
 237   return route_node_match (table, (struct prefix *) &p);
 238 }
 239
 240 #ifdef HAVE_IPV6
 241 struct route_node *
 242 route_node_match_ipv6 (const struct route_table *table,
 243                        const struct in6_addr *addr)
 244 {
 245   struct prefix_ipv6 p;
 246
 247   memset (&p, 0, sizeof (struct prefix_ipv6));
 248   p.family = AF_INET6;
 249   p.prefixlen = IPV6_MAX_PREFIXLEN;
 250   p.prefix = *addr;
 251
 252   return route_node_match (table, (struct prefix *) &p);
 253 }
 254 #endif /* HAVE_IPV6 */
 255
 256 /* Lookup same prefix node.  Return NULL when we can't find route. */
 257 struct route_node *
 258 route_node_lookup (struct route_table *table, struct prefix *p)
 259 {
 260   struct route_node *node;
 261
 262   node = table->top;
 263
 264   while (node && node->p.prefixlen <= p->prefixlen &&
 265          prefix_match (&node->p, p))
 266     {
 267       if (node->p.prefixlen == p->prefixlen)
 268         return node->info ? route_lock_node (node) : NULL;
 269
 270       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
 271     }
 272
 273   return NULL;
 274 }
 275
 276 /* Add node to routing table. */
 277 struct route_node *
 278 route_node_get (struct route_table *table, struct prefix *p)
 279 {
 280   struct route_node *new;
 281   struct route_node *node;
 282   struct route_node *match;
 283
 284   match = NULL;
 285   node = table->top;
 286   while (node && node->p.prefixlen <= p->prefixlen &&
 287          prefix_match (&node->p, p))
 288     {
 289       if (node->p.prefixlen == p->prefixlen)
 290         return route_lock_node (node);
 291
 292       match = node;
 293       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
 294     }
 295
 296   if (node == NULL)
 297     {
 298       new = route_node_set (table, p);
 299       if (match)
 300         set_link (match, new);
 301       else
 302         table->top = new;
 303     }
 304   else
 305     {
 306       new = route_node_new ();
 307       route_common (&node->p, p, &new->p);
 308       new->p.family = p->family;
 309       new->table = table;
 310       set_link (new, node);
 311
 312       if (match)
 313         set_link (match, new);
 314       else
 315         table->top = new;
 316
 317       if (new->p.prefixlen != p->prefixlen)
 318         {
 319           match = new;
 320           new = route_node_set (table, p);
 321           set_link (match, new);
 322         }
 323     }
 324   route_lock_node (new);
 325
 326   return new;
 327 }
 328
 329 /* Delete node from the routing table. */
 330 void
 331 route_node_delete (struct route_node *node)
 332 {
 333   struct route_node *child;
 334   struct route_node *parent;
 335
 336   assert (node->lock == 0);
 337   assert (node->info == NULL);
 338
 339   if (node->l_left && node->l_right)
 340     return;
 341
 342   if (node->l_left)
 343     child = node->l_left;
 344   else
 345     child = node->l_right;
 346
 347   parent = node->parent;
 348
 349   if (child)
 350     child->parent = parent;
 351
 352   if (parent)
 353     {
 354       if (parent->l_left == node)
 355         parent->l_left = child;
 356       else
 357         parent->l_right = child;
 358     }
 359   else
 360     node->table->top = child;
 361
 362   route_node_free (node);
 363
 364   /* If parent node is stub then delete it also. */
 365   if (parent && parent->lock == 0)
 366     route_node_delete (parent);
 367 }
 368
 369 /* Get fist node and lock it.  This function is useful when one want
 370    to lookup all the node exist in the routing table. */
 371 struct route_node *
 372 route_top (struct route_table *table)
 373 {
 374   /* If there is no node in the routing table return NULL. */
 375   if (table->top == NULL)
 376     return NULL;
 377
 378   /* Lock the top node and return it. */
 379   route_lock_node (table->top);
 380   return table->top;
 381 }
 382
 383 /* Unlock current node and lock next node then return it. */
 384 struct route_node *
 385 route_next (struct route_node *node)
 386 {
 387   struct route_node *next;
 388   struct route_node *start;
 389
 390   /* Node may be deleted from route_unlock_node so we have to preserve
 391      next node's pointer. */
 392
 393   if (node->l_left)
 394     {
 395       next = node->l_left;
 396       route_lock_node (next);
 397       route_unlock_node (node);
 398       return next;
 399     }
 400   if (node->l_right)
 401     {
 402       next = node->l_right;
 403       route_lock_node (next);
 404       route_unlock_node (node);
 405       return next;
 406     }
 407
 408   start = node;
 409   while (node->parent)
 410     {
 411       if (node->parent->l_left == node && node->parent->l_right)
 412         {
 413           next = node->parent->l_right;
 414           route_lock_node (next);
 415           route_unlock_node (start);
 416           return next;
 417         }
 418       node = node->parent;
 419     }
 420   route_unlock_node (start);
 421   return NULL;
 422 }
 423
 424 /* Unlock current node and lock next node until limit. */
 425 struct route_node *
 426 route_next_until (struct route_node *node, struct route_node *limit)
 427 {
 428   struct route_node *next;
 429   struct route_node *start;
 430
 431   /* Node may be deleted from route_unlock_node so we have to preserve
 432      next node's pointer. */
 433
 434   if (node->l_left)
 435     {
 436       next = node->l_left;
 437       route_lock_node (next);
 438       route_unlock_node (node);
 439       return next;
 440     }
 441   if (node->l_right)
 442     {
 443       next = node->l_right;
 444       route_lock_node (next);
 445       route_unlock_node (node);
 446       return next;
 447     }
 448
 449   start = node;
 450   while (node->parent && node != limit)
 451     {
 452       if (node->parent->l_left == node && node->parent->l_right)
 453         {
 454           next = node->parent->l_right;
 455           route_lock_node (next);
 456           route_unlock_node (start);
 457           return next;
 458         }
 459       node = node->parent;
 460     }
 461   route_unlock_node (start);
 462   return NULL;
 463 }