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