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