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