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 #ifdef HAVE_IPV6
 254 struct route_node *
 255 route_node_match_ipv6 (const struct route_table *table,
 256                        const struct in6_addr *addr)
 257 {
 258   struct prefix_ipv6 p;
 259
 260   memset (&p, 0, sizeof (struct prefix_ipv6));
 261   p.family = AF_INET6;
 262   p.prefixlen = IPV6_MAX_PREFIXLEN;
 263   p.prefix = *addr;
 264
 265   return route_node_match (table, (struct prefix *) &p);
 266 }
 267 #endif /* HAVE_IPV6 */
 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 /* Add node to routing table. */
 292 struct route_node *
 293 route_node_get (struct route_table *const table, const struct prefix *p)
 294 {
 295   struct route_node *new;
 296   struct route_node *node;
 297   struct route_node *match;
 298   u_char prefixlen = p->prefixlen;
 299   const u_char *prefix = &p->u.prefix;
 300
 301   match = NULL;
 302   node = table->top;
 303   while (node && node->p.prefixlen <= prefixlen &&
 304          prefix_match (&node->p, p))
 305     {
 306       if (node->p.prefixlen == prefixlen)
 307         return route_lock_node (node);
 308
 309       match = node;
 310       node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 311     }
 312
 313   if (node == NULL)
 314     {
 315       new = route_node_set (table, p);
 316       if (match)
 317         set_link (match, new);
 318       else
 319         table->top = new;
 320     }
 321   else
 322     {
 323       new = route_node_new (table);
 324       route_common (&node->p, p, &new->p);
 325       new->p.family = p->family;
 326       new->table = table;
 327       set_link (new, node);
 328
 329       if (match)
 330         set_link (match, new);
 331       else
 332         table->top = new;
 333
 334       if (new->p.prefixlen != p->prefixlen)
 335         {
 336           match = new;
 337           new = route_node_set (table, p);
 338           set_link (match, new);
 339           table->count++;
 340         }
 341     }
 342   table->count++;
 343   route_lock_node (new);
 344
 345   return new;
 346 }
 347
 348 /* Delete node from the routing table. */
 349 static void
 350 route_node_delete (struct route_node *node)
 351 {
 352   struct route_node *child;
 353   struct route_node *parent;
 354
 355   assert (node->lock == 0);
 356   assert (node->info == NULL);
 357
 358   if (node->l_left && node->l_right)
 359     return;
 360
 361   if (node->l_left)
 362     child = node->l_left;
 363   else
 364     child = node->l_right;
 365
 366   parent = node->parent;
 367
 368   if (child)
 369     child->parent = parent;
 370
 371   if (parent)
 372     {
 373       if (parent->l_left == node)
 374         parent->l_left = child;
 375       else
 376         parent->l_right = child;
 377     }
 378   else
 379     node->table->top = child;
 380
 381   node->table->count--;
 382
 383   route_node_free (node->table, node);
 384
 385   /* If parent node is stub then delete it also. */
 386   if (parent && parent->lock == 0)
 387     route_node_delete (parent);
 388 }
 389
 390 /* Get fist node and lock it.  This function is useful when one want
 391    to lookup all the node exist in the routing table. */
 392 struct route_node *
 393 route_top (struct route_table *table)
 394 {
 395   /* If there is no node in the routing table return NULL. */
 396   if (table->top == NULL)
 397     return NULL;
 398
 399   /* Lock the top node and return it. */
 400   route_lock_node (table->top);
 401   return table->top;
 402 }
 403
 404 /* Unlock current node and lock next node then return it. */
 405 struct route_node *
 406 route_next (struct route_node *node)
 407 {
 408   struct route_node *next;
 409   struct route_node *start;
 410
 411   /* Node may be deleted from route_unlock_node so we have to preserve
 412      next node's pointer. */
 413
 414   if (node->l_left)
 415     {
 416       next = node->l_left;
 417       route_lock_node (next);
 418       route_unlock_node (node);
 419       return next;
 420     }
 421   if (node->l_right)
 422     {
 423       next = node->l_right;
 424       route_lock_node (next);
 425       route_unlock_node (node);
 426       return next;
 427     }
 428
 429   start = node;
 430   while (node->parent)
 431     {
 432       if (node->parent->l_left == node && node->parent->l_right)
 433         {
 434           next = node->parent->l_right;
 435           route_lock_node (next);
 436           route_unlock_node (start);
 437           return next;
 438         }
 439       node = node->parent;
 440     }
 441   route_unlock_node (start);
 442   return NULL;
 443 }
 444
 445 /* Unlock current node and lock next node until limit. */
 446 struct route_node *
 447 route_next_until (struct route_node *node, struct route_node *limit)
 448 {
 449   struct route_node *next;
 450   struct route_node *start;
 451
 452   /* Node may be deleted from route_unlock_node so we have to preserve
 453      next node's pointer. */
 454
 455   if (node->l_left)
 456     {
 457       next = node->l_left;
 458       route_lock_node (next);
 459       route_unlock_node (node);
 460       return next;
 461     }
 462   if (node->l_right)
 463     {
 464       next = node->l_right;
 465       route_lock_node (next);
 466       route_unlock_node (node);
 467       return next;
 468     }
 469
 470   start = node;
 471   while (node->parent && node != limit)
 472     {
 473       if (node->parent->l_left == node && node->parent->l_right)
 474         {
 475           next = node->parent->l_right;
 476           route_lock_node (next);
 477           route_unlock_node (start);
 478           return next;
 479         }
 480       node = node->parent;
 481     }
 482   route_unlock_node (start);
 483   return NULL;
 484 }
 485
 486 unsigned long
 487 route_table_count (const struct route_table *table)
 488 {
 489   return table->count;
 490 }
 491
 492 /**
 493  * route_node_create
 494  *
 495  * Default function for creating a route node.
 496  */
 497 static struct route_node *
 498 route_node_create (route_table_delegate_t *delegate,
 499                    struct route_table *table)
 500 {
 501   struct route_node *node;
 502   node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
 503   return node;
 504 }
 505
 506 /**
 507  * route_node_destroy
 508  *
 509  * Default function for destroying a route node.
 510  */
 511 static void
 512 route_node_destroy (route_table_delegate_t *delegate,
 513                     struct route_table *table, struct route_node *node)
 514 {
 515   XFREE (MTYPE_ROUTE_NODE, node);
 516 }
 517
 518 /*
 519  * Default delegate.
 520  */
 521 static route_table_delegate_t default_delegate = {
 522   .create_node = route_node_create,
 523   .destroy_node = route_node_destroy
 524 };
 525
 526 route_table_delegate_t *
 527 route_table_get_default_delegate(void)
 528 {
 529   return &default_delegate;
 530 }
 531
 532 /*
 533  * route_table_init
 534  */
 535 struct route_table *
 536 route_table_init (void)
 537 {
 538   return route_table_init_with_delegate (&default_delegate);
 539 }
 540
 541 /**
 542  * route_table_prefix_iter_cmp
 543  *
 544  * Compare two prefixes according to the order in which they appear in
 545  * an iteration over a tree.
 546  *
 547  * @return -1 if p1 occurs before p2 (p1 < p2)
 548  *          0 if the prefixes are identical (p1 == p2)
 549  *         +1 if p1 occurs after p2 (p1 > p2)
 550  */
 551 int
 552 route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2)
 553 {
 554   struct prefix common_space;
 555   struct prefix *common = &common_space;
 556
 557   if (p1->prefixlen <= p2->prefixlen)
 558     {
 559       if (prefix_match (p1, p2))
 560         {
 561
 562           /*
 563            * p1 contains p2, or is equal to it.
 564            */
 565           return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
 566         }
 567     }
 568   else
 569     {
 570
 571       /*
 572        * Check if p2 contains p1.
 573        */
 574       if (prefix_match (p2, p1))
 575           return 1;
 576     }
 577
 578   route_common (p1, p2, common);
 579   assert (common->prefixlen < p1->prefixlen);
 580   assert (common->prefixlen < p2->prefixlen);
 581
 582   /*
 583    * Both prefixes are longer than the common prefix.
 584    *
 585    * We need to check the bit after the common prefixlen to determine
 586    * which one comes later.
 587    */
 588   if (prefix_bit (&p1->u.prefix, common->prefixlen))
 589     {
 590
 591       /*
 592        * We branch to the right to get to p1 from the common prefix.
 593        */
 594       assert (!prefix_bit (&p2->u.prefix, common->prefixlen));
 595       return 1;
 596     }
 597
 598   /*
 599    * We branch to the right to get to p2 from the common prefix.
 600    */
 601   assert (prefix_bit (&p2->u.prefix, common->prefixlen));
 602   return -1;
 603 }
 604
 605 /*
 606  * route_get_subtree_next
 607  *
 608  * Helper function that returns the first node that follows the nodes
 609  * in the sub-tree under 'node' in iteration order.
 610  */
 611 static struct route_node *
 612 route_get_subtree_next (struct route_node *node)
 613 {
 614   while (node->parent)
 615     {
 616       if (node->parent->l_left == node && node->parent->l_right)
 617         return node->parent->l_right;
 618
 619       node = node->parent;
 620     }
 621
 622   return NULL;
 623 }
 624
 625 /**
 626  * route_table_get_next_internal
 627  *
 628  * Helper function to find the node that occurs after the given prefix in
 629  * order of iteration.
 630  *
 631  * @see route_table_get_next
 632  */
 633 static struct route_node *
 634 route_table_get_next_internal (const struct route_table *table,
 635                                struct prefix *p)
 636 {
 637   struct route_node *node, *tmp_node;
 638   int cmp;
 639
 640   node = table->top;
 641
 642   while (node)
 643     {
 644       int match;
 645
 646       if (node->p.prefixlen < p->prefixlen)
 647         match = prefix_match (&node->p, p);
 648       else
 649         match = prefix_match (p, &node->p);
 650
 651       if (match)
 652         {
 653           if (node->p.prefixlen == p->prefixlen)
 654             {
 655
 656               /*
 657                * The prefix p exists in the tree, just return the next
 658                * node.
 659                */
 660               route_lock_node (node);
 661               node = route_next (node);
 662               if (node)
 663                 route_unlock_node (node);
 664
 665               return (node);
 666             }
 667
 668           if (node->p.prefixlen > p->prefixlen)
 669             {
 670
 671               /*
 672                * Node is in the subtree of p, and hence greater than p.
 673                */
 674               return node;
 675             }
 676
 677           /*
 678            * p is in the sub-tree under node.
 679            */
 680           tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)];
 681
 682           if (tmp_node)
 683             {
 684               node = tmp_node;
 685               continue;
 686             }
 687
 688           /*
 689            * There are no nodes in the direction where p should be. If
 690            * node has a right child, then it must be greater than p.
 691            */
 692           if (node->l_right)
 693             return node->l_right;
 694
 695           /*
 696            * No more children to follow, go upwards looking for the next
 697            * node.
 698            */
 699           return route_get_subtree_next (node);
 700         }
 701
 702       /*
 703        * Neither node prefix nor 'p' contains the other.
 704        */
 705       cmp = route_table_prefix_iter_cmp (&node->p, p);
 706       if (cmp > 0)
 707         {
 708
 709           /*
 710            * Node follows p in iteration order. Return it.
 711            */
 712           return node;
 713         }
 714
 715       assert (cmp < 0);
 716
 717       /*
 718        * Node and the subtree under it come before prefix p in
 719        * iteration order. Prefix p and its sub-tree are not present in
 720        * the tree. Go upwards and find the first node that follows the
 721        * subtree. That node will also succeed p.
 722        */
 723       return route_get_subtree_next (node);
 724     }
 725
 726   return NULL;
 727 }
 728
 729 /**
 730  * route_table_get_next
 731  *
 732  * Find the node that occurs after the given prefix in order of
 733  * iteration.
 734  */
 735 struct route_node *
 736 route_table_get_next (const struct route_table *table, struct prefix *p)
 737 {
 738   struct route_node *node;
 739
 740   node = route_table_get_next_internal (table, p);
 741   if (node)
 742     {
 743       assert (route_table_prefix_iter_cmp (&node->p, p) > 0);
 744       route_lock_node (node);
 745     }
 746   return node;
 747 }
 748
 749 /*
 750  * route_table_iter_init
 751  */
 752 void
 753 route_table_iter_init (route_table_iter_t * iter, struct route_table *table)
 754 {
 755   memset (iter, 0, sizeof (*iter));
 756   iter->state = RT_ITER_STATE_INIT;
 757   iter->table = table;
 758 }
 759
 760 /*
 761  * route_table_iter_pause
 762  *
 763  * Pause an iteration over the table. This allows the iteration to be
 764  * resumed point after arbitrary additions/deletions from the table.
 765  * An iteration can be resumed by just calling route_table_iter_next()
 766  * on the iterator.
 767  */
 768 void
 769 route_table_iter_pause (route_table_iter_t * iter)
 770 {
 771   switch (iter->state)
 772     {
 773
 774     case RT_ITER_STATE_INIT:
 775     case RT_ITER_STATE_PAUSED:
 776     case RT_ITER_STATE_DONE:
 777       return;
 778
 779     case RT_ITER_STATE_ITERATING:
 780
 781       /*
 782        * Save the prefix that we are currently at. The next call to
 783        * route_table_iter_next() will return the node after this prefix
 784        * in the tree.
 785        */
 786       prefix_copy (&iter->pause_prefix, &iter->current->p);
 787       route_unlock_node (iter->current);
 788       iter->current = NULL;
 789       iter->state = RT_ITER_STATE_PAUSED;
 790       return;
 791
 792     default:
 793       assert (0);
 794     }
 795
 796 }
 797
 798 /*
 799  * route_table_iter_cleanup
 800  *
 801  * Release any resources held by the iterator.
 802  */
 803 void
 804 route_table_iter_cleanup (route_table_iter_t * iter)
 805 {
 806   if (iter->state == RT_ITER_STATE_ITERATING)
 807     {
 808       route_unlock_node (iter->current);
 809       iter->current = NULL;
 810     }
 811   assert (!iter->current);
 812
 813   /*
 814    * Set the state to RT_ITER_STATE_DONE to make any
 815    * route_table_iter_next() calls on this iterator return NULL.
 816    */
 817   iter->state = RT_ITER_STATE_DONE;
 818 }