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