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