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 static void route_node_delete (struct route_node *);
  31 static void route_table_free (struct route_table *);
  32
  33
  34 /*
  35  * route_table_init_with_delegate
  36  */
  37 struct route_table *
  38 route_table_init_with_delegate (route_table_delegate_t *delegate)
  39 {
  40   struct route_table *rt;
  41
  42   rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
  43   rt->delegate = delegate;
  44   return rt;
  45 }
  46
  47 void
  48 route_table_finish (struct route_table *rt)
  49 {
  50   route_table_free (rt);
  51 }
  52
  53 /* Allocate new route node. */
  54 static struct route_node *
  55 route_node_new (struct route_table *table)
  56 {
  57   return table->delegate->create_node (table->delegate, table);
  58 }
  59
  60 /* Allocate new route node with prefix set. */
  61 static struct route_node *
  62 route_node_set (struct route_table *table, const struct prefix *prefix)
  63 {
  64   struct route_node *node;
  65
  66   node = route_node_new (table);
  67
  68   prefix_copy (&node->p, prefix);
  69   node->table = table;
  70
  71   return node;
  72 }
  73
  74 /* Free route node. */
  75 static void
  76 route_node_free (struct route_table *table, struct route_node *node)
  77 {
  78   table->delegate->destroy_node (table->delegate, table, node);
  79 }
  80
  81 /* Free route table. */
  82 static void
  83 route_table_free (struct route_table *rt)
  84 {
  85   struct route_node *tmp_node;
  86   struct route_node *node;
  87
  88   if (rt == NULL)
  89     return;
  90
  91   node = rt->top;
  92
  93   /* Bulk deletion of nodes remaining in this table.  This function is not
  94      called until workers have completed their dependency on this table.
  95      A final route_unlock_node() will not be called for these nodes. */
  96   while (node)
  97     {
  98       if (node->l_left)
  99         {
 100           node = node->l_left;
 101           continue;
 102         }
 103
 104       if (node->l_right)
 105         {
 106           node = node->l_right;
 107           continue;
 108         }
 109
 110       tmp_node = node;
 111       node = node->parent;
 112
 113       tmp_node->table->count--;
 114       tmp_node->lock = 0;  /* to cause assert if unlocked after this */
 115       route_node_free (rt, tmp_node);
 116
 117       if (node != NULL)
 118         {
 119           if (node->l_left == tmp_node)
 120             node->l_left = NULL;
 121           else
 122             node->l_right = NULL;
 123         }
 124       else
 125         {
 126           break;
 127         }
 128     }
 129
 130   assert (rt->count == 0);
 131
 132   XFREE (MTYPE_ROUTE_TABLE, rt);
 133   return;
 134 }
 135
 136 /* Utility mask array. */
 137 static const 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 (const struct prefix *n, const struct prefix *p, struct prefix *new)
 145 {
 146   int i;
 147   u_char diff;
 148   u_char mask;
 149
 150   const u_char *np = (const u_char *)&n->u.prefix;
 151   const u_char *pp = (const 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 static void
 178 set_link (struct route_node *node, struct route_node *new)
 179 {
 180   unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
 181
 182   node->link[bit] = new;
 183   new->parent = node;
 184 }
 185
 186 /* Lock node. */
 187 struct route_node *
 188 route_lock_node (struct route_node *node)
 189 {
 190   node->lock++;
 191   return node;
 192 }
 193
 194 /* Unlock node. */
 195 void
 196 route_unlock_node (struct route_node *node)
 197 {
 198   assert (node->lock > 0);
 199   node->lock--;
 200
 201   if (node->lock == 0)
 202     route_node_delete (node);
 203 }
 204
 205 /* Find matched prefix. */
 206 struct route_node *
 207 route_node_match (const struct route_table *table, const struct prefix *p)
 208 {
 209   struct route_node *node;
 210   struct route_node *matched;
 211
 212   matched = NULL;
 213   node = table->top;
 214
 215   /* Walk down tree.  If there is matched route then store it to
 216      matched. */
 217   while (node && node->p.prefixlen <= p->prefixlen &&
 218          prefix_match (&node->p, p))
 219     {
 220       if (node->info)
 221         matched = node;
 222
 223       if (node->p.prefixlen == p->prefixlen)
 224         break;
 225
 226       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
 227     }
 228
 229   /* If matched route found, return it. */
 230   if (matched)
 231     return route_lock_node (matched);
 232
 233   return NULL;
 234 }
 235
 236 struct route_node *
 237 route_node_match_ipv4 (const struct route_table *table,
 238                        const struct in_addr *addr)
 239 {
 240   struct prefix_ipv4 p;
 241
 242   memset (&p, 0, sizeof (struct prefix_ipv4));
 243   p.family = AF_INET;
 244   p.prefixlen = IPV4_MAX_PREFIXLEN;
 245   p.prefix = *addr;
 246
 247   return route_node_match (table, (struct prefix *) &p);
 248 }
 249
 250 #ifdef HAVE_IPV6
 251 struct route_node *
 252 route_node_match_ipv6 (const struct route_table *table,
 253                        const struct in6_addr *addr)
 254 {
 255   struct prefix_ipv6 p;
 256
 257   memset (&p, 0, sizeof (struct prefix_ipv6));
 258   p.family = AF_INET6;
 259   p.prefixlen = IPV6_MAX_PREFIXLEN;
 260   p.prefix = *addr;
 261
 262   return route_node_match (table, (struct prefix *) &p);
 263 }
 264 #endif /* HAVE_IPV6 */
 265
 266 /* Lookup same prefix node.  Return NULL when we can't find route. */
 267 struct route_node *
 268 route_node_lookup (const struct route_table *table, const struct prefix *p)
 269 {
 270   struct route_node *node;
 271   u_char prefixlen = p->prefixlen;
 272   const u_char *prefix = &p->u.prefix;
 273
 274   node = table->top;
 275
 276   while (node && node->p.prefixlen <= prefixlen &&
 277          prefix_match (&node->p, p))
 278     {
 279       if (node->p.prefixlen == prefixlen)
 280         return node->info ? route_lock_node (node) : NULL;
 281
 282       node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 283     }
 284
 285   return NULL;
 286 }
 287
 288 /* Add node to routing table. */
 289 struct route_node *
 290 route_node_get (struct route_table *const table, const struct prefix *p)
 291 {
 292   struct route_node *new;
 293   struct route_node *node;
 294   struct route_node *match;
 295   u_char prefixlen = p->prefixlen;
 296   const u_char *prefix = &p->u.prefix;
 297
 298   match = NULL;
 299   node = table->top;
 300   while (node && node->p.prefixlen <= prefixlen &&
 301          prefix_match (&node->p, p))
 302     {
 303       if (node->p.prefixlen == prefixlen)
 304         return route_lock_node (node);
 305
 306       match = node;
 307       node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 308     }
 309
 310   if (node == NULL)
 311     {
 312       new = route_node_set (table, p);
 313       if (match)
 314         set_link (match, new);
 315       else
 316         table->top = new;
 317     }
 318   else
 319     {
 320       new = route_node_new (table);
 321       route_common (&node->p, p, &new->p);
 322       new->p.family = p->family;
 323       new->table = table;
 324       set_link (new, node);
 325
 326       if (match)
 327         set_link (match, new);
 328       else
 329         table->top = new;
 330
 331       if (new->p.prefixlen != p->prefixlen)
 332         {
 333           match = new;
 334           new = route_node_set (table, p);
 335           set_link (match, new);
 336           table->count++;
 337         }
 338     }
 339   table->count++;
 340   route_lock_node (new);
 341
 342   return new;
 343 }
 344
 345 /* Delete node from the routing table. */
 346 static void
 347 route_node_delete (struct route_node *node)
 348 {
 349   struct route_node *child;
 350   struct route_node *parent;
 351
 352   assert (node->lock == 0);
 353   assert (node->info == NULL);
 354
 355   if (node->l_left && node->l_right)
 356     return;
 357
 358   if (node->l_left)
 359     child = node->l_left;
 360   else
 361     child = node->l_right;
 362
 363   parent = node->parent;
 364
 365   if (child)
 366     child->parent = parent;
 367
 368   if (parent)
 369     {
 370       if (parent->l_left == node)
 371         parent->l_left = child;
 372       else
 373         parent->l_right = child;
 374     }
 375   else
 376     node->table->top = child;
 377
 378   node->table->count--;
 379
 380   route_node_free (node->table, node);
 381
 382   /* If parent node is stub then delete it also. */
 383   if (parent && parent->lock == 0)
 384     route_node_delete (parent);
 385 }
 386
 387 /* Get fist node and lock it.  This function is useful when one want
 388    to lookup all the node exist in the routing table. */
 389 struct route_node *
 390 route_top (struct route_table *table)
 391 {
 392   /* If there is no node in the routing table return NULL. */
 393   if (table->top == NULL)
 394     return NULL;
 395
 396   /* Lock the top node and return it. */
 397   route_lock_node (table->top);
 398   return table->top;
 399 }
 400
 401 /* Unlock current node and lock next node then return it. */
 402 struct route_node *
 403 route_next (struct route_node *node)
 404 {
 405   struct route_node *next;
 406   struct route_node *start;
 407
 408   /* Node may be deleted from route_unlock_node so we have to preserve
 409      next node's pointer. */
 410
 411   if (node->l_left)
 412     {
 413       next = node->l_left;
 414       route_lock_node (next);
 415       route_unlock_node (node);
 416       return next;
 417     }
 418   if (node->l_right)
 419     {
 420       next = node->l_right;
 421       route_lock_node (next);
 422       route_unlock_node (node);
 423       return next;
 424     }
 425
 426   start = node;
 427   while (node->parent)
 428     {
 429       if (node->parent->l_left == node && node->parent->l_right)
 430         {
 431           next = node->parent->l_right;
 432           route_lock_node (next);
 433           route_unlock_node (start);
 434           return next;
 435         }
 436       node = node->parent;
 437     }
 438   route_unlock_node (start);
 439   return NULL;
 440 }
 441
 442 /* Unlock current node and lock next node until limit. */
 443 struct route_node *
 444 route_next_until (struct route_node *node, struct route_node *limit)
 445 {
 446   struct route_node *next;
 447   struct route_node *start;
 448
 449   /* Node may be deleted from route_unlock_node so we have to preserve
 450      next node's pointer. */
 451
 452   if (node->l_left)
 453     {
 454       next = node->l_left;
 455       route_lock_node (next);
 456       route_unlock_node (node);
 457       return next;
 458     }
 459   if (node->l_right)
 460     {
 461       next = node->l_right;
 462       route_lock_node (next);
 463       route_unlock_node (node);
 464       return next;
 465     }
 466
 467   start = node;
 468   while (node->parent && node != limit)
 469     {
 470       if (node->parent->l_left == node && node->parent->l_right)
 471         {
 472           next = node->parent->l_right;
 473           route_lock_node (next);
 474           route_unlock_node (start);
 475           return next;
 476         }
 477       node = node->parent;
 478     }
 479   route_unlock_node (start);
 480   return NULL;
 481 }
 482
 483 unsigned long
 484 route_table_count (const struct route_table *table)
 485 {
 486   return table->count;
 487 }
 488
 489 /**
 490  * route_node_create
 491  *
 492  * Default function for creating a route node.
 493  */
 494 static struct route_node *
 495 route_node_create (route_table_delegate_t *delegate,
 496                    struct route_table *table)
 497 {
 498   struct route_node *node;
 499   node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
 500   return node;
 501 }
 502
 503 /**
 504  * route_node_destroy
 505  *
 506  * Default function for destroying a route node.
 507  */
 508 static void
 509 route_node_destroy (route_table_delegate_t *delegate,
 510                     struct route_table *table, struct route_node *node)
 511 {
 512   XFREE (MTYPE_ROUTE_NODE, node);
 513 }
 514
 515 /*
 516  * Default delegate.
 517  */
 518 static route_table_delegate_t default_delegate = {
 519   .create_node = route_node_create,
 520   .destroy_node = route_node_destroy
 521 };
 522
 523 /*
 524  * route_table_init
 525  */
 526 struct route_table *
 527 route_table_init (void)
 528 {
 529   return route_table_init_with_delegate (&default_delegate);
 530 }
 531
 532 /**
 533  * route_table_prefix_iter_cmp
 534  *
 535  * Compare two prefixes according to the order in which they appear in
 536  * an iteration over a tree.
 537  *
 538  * @return -1 if p1 occurs before p2 (p1 < p2)
 539  *          0 if the prefixes are identical (p1 == p2)
 540  *         +1 if p1 occurs after p2 (p1 > p2)
 541  */
 542 int
 543 route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2)
 544 {
 545   struct prefix common_space;
 546   struct prefix *common = &common_space;
 547
 548   if (p1->prefixlen <= p2->prefixlen)
 549     {
 550       if (prefix_match (p1, p2))
 551         {
 552
 553           /*
 554            * p1 contains p2, or is equal to it.
 555            */
 556           return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
 557         }
 558     }
 559   else
 560     {
 561
 562       /*
 563        * Check if p2 contains p1.
 564        */
 565       if (prefix_match (p2, p1))
 566           return 1;
 567     }
 568
 569   route_common (p1, p2, common);
 570   assert (common->prefixlen < p1->prefixlen);
 571   assert (common->prefixlen < p2->prefixlen);
 572
 573   /*
 574    * Both prefixes are longer than the common prefix.
 575    *
 576    * We need to check the bit after the common prefixlen to determine
 577    * which one comes later.
 578    */
 579   if (prefix_bit (&p1->u.prefix, common->prefixlen))
 580     {
 581
 582       /*
 583        * We branch to the right to get to p1 from the common prefix.
 584        */
 585       assert (!prefix_bit (&p2->u.prefix, common->prefixlen));
 586       return 1;
 587     }
 588
 589   /*
 590    * We branch to the right to get to p2 from the common prefix.
 591    */
 592   assert (prefix_bit (&p2->u.prefix, common->prefixlen));
 593   return -1;
 594 }
 595
 596 /*
 597  * route_get_subtree_next
 598  *
 599  * Helper function that returns the first node that follows the nodes
 600  * in the sub-tree under 'node' in iteration order.
 601  */
 602 static struct route_node *
 603 route_get_subtree_next (struct route_node *node)
 604 {
 605   while (node->parent)
 606     {
 607       if (node->parent->l_left == node && node->parent->l_right)
 608         return node->parent->l_right;
 609
 610       node = node->parent;
 611     }
 612
 613   return NULL;
 614 }
 615
 616 /**
 617  * route_table_get_next_internal
 618  *
 619  * Helper function to find the node that occurs after the given prefix in
 620  * order of iteration.
 621  *
 622  * @see route_table_get_next
 623  */
 624 static struct route_node *
 625 route_table_get_next_internal (const struct route_table *table,
 626                                struct prefix *p)
 627 {
 628   struct route_node *node, *tmp_node;
 629   int cmp;
 630
 631   node = table->top;
 632
 633   while (node)
 634     {
 635       int match;
 636
 637       if (node->p.prefixlen < p->prefixlen)
 638         match = prefix_match (&node->p, p);
 639       else
 640         match = prefix_match (p, &node->p);
 641
 642       if (match)
 643         {
 644           if (node->p.prefixlen == p->prefixlen)
 645             {
 646
 647               /*
 648                * The prefix p exists in the tree, just return the next
 649                * node.
 650                */
 651               route_lock_node (node);
 652               node = route_next (node);
 653               if (node)
 654                 route_unlock_node (node);
 655
 656               return (node);
 657             }
 658
 659           if (node->p.prefixlen > p->prefixlen)
 660             {
 661
 662               /*
 663                * Node is in the subtree of p, and hence greater than p.
 664                */
 665               return node;
 666             }
 667
 668           /*
 669            * p is in the sub-tree under node.
 670            */
 671           tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)];
 672
 673           if (tmp_node)
 674             {
 675               node = tmp_node;
 676               continue;
 677             }
 678
 679           /*
 680            * There are no nodes in the direction where p should be. If
 681            * node has a right child, then it must be greater than p.
 682            */
 683           if (node->l_right)
 684             return node->l_right;
 685
 686           /*
 687            * No more children to follow, go upwards looking for the next
 688            * node.
 689            */
 690           return route_get_subtree_next (node);
 691         }
 692
 693       /*
 694        * Neither node prefix nor 'p' contains the other.
 695        */
 696       cmp = route_table_prefix_iter_cmp (&node->p, p);
 697       if (cmp > 0)
 698         {
 699
 700           /*
 701            * Node follows p in iteration order. Return it.
 702            */
 703           return node;
 704         }
 705
 706       assert (cmp < 0);
 707
 708       /*
 709        * Node and the subtree under it come before prefix p in
 710        * iteration order. Prefix p and its sub-tree are not present in
 711        * the tree. Go upwards and find the first node that follows the
 712        * subtree. That node will also succeed p.
 713        */
 714       return route_get_subtree_next (node);
 715     }
 716
 717   return NULL;
 718 }
 719
 720 /**
 721  * route_table_get_next
 722  *
 723  * Find the node that occurs after the given prefix in order of
 724  * iteration.
 725  */
 726 struct route_node *
 727 route_table_get_next (const struct route_table *table, struct prefix *p)
 728 {
 729   struct route_node *node;
 730
 731   node = route_table_get_next_internal (table, p);
 732   if (node)
 733     {
 734       assert (route_table_prefix_iter_cmp (&node->p, p) > 0);
 735       route_lock_node (node);
 736     }
 737   return node;
 738 }
 739
 740 /*
 741  * route_table_iter_init
 742  */
 743 void
 744 route_table_iter_init (route_table_iter_t * iter, struct route_table *table)
 745 {
 746   memset (iter, 0, sizeof (*iter));
 747   iter->state = RT_ITER_STATE_INIT;
 748   iter->table = table;
 749 }
 750
 751 /*
 752  * route_table_iter_pause
 753  *
 754  * Pause an iteration over the table. This allows the iteration to be
 755  * resumed point after arbitrary additions/deletions from the table.
 756  * An iteration can be resumed by just calling route_table_iter_next()
 757  * on the iterator.
 758  */
 759 void
 760 route_table_iter_pause (route_table_iter_t * iter)
 761 {
 762   switch (iter->state)
 763     {
 764
 765     case RT_ITER_STATE_INIT:
 766     case RT_ITER_STATE_PAUSED:
 767     case RT_ITER_STATE_DONE:
 768       return;
 769
 770     case RT_ITER_STATE_ITERATING:
 771
 772       /*
 773        * Save the prefix that we are currently at. The next call to
 774        * route_table_iter_next() will return the node after this prefix
 775        * in the tree.
 776        */
 777       prefix_copy (&iter->pause_prefix, &iter->current->p);
 778       route_unlock_node (iter->current);
 779       iter->current = NULL;
 780       iter->state = RT_ITER_STATE_PAUSED;
 781       return;
 782
 783     default:
 784       assert (0);
 785     }
 786
 787 }
 788
 789 /*
 790  * route_table_iter_cleanup
 791  *
 792  * Release any resources held by the iterator.
 793  */
 794 void
 795 route_table_iter_cleanup (route_table_iter_t * iter)
 796 {
 797   if (iter->state == RT_ITER_STATE_ITERATING)
 798     {
 799       route_unlock_node (iter->current);
 800       iter->current = NULL;
 801     }
 802   assert (!iter->current);
 803
 804   /*
 805    * Set the state to RT_ITER_STATE_DONE to make any
 806    * route_table_iter_next() calls on this iterator return NULL.
 807    */
 808   iter->state = RT_ITER_STATE_DONE;
 809 }