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