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