lib/table.c

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