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