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_STATIC(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 struct route_node *a,
  37                                 const struct route_node *b)
  38 {
  39         return prefix_cmp(&a->p, &b->p);
  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(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(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(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, &p);
 248 }
 249
 250 /* Lookup same prefix node.  Return NULL when we can't find route. */
 251 struct route_node *route_node_lookup(struct route_table *table,
 252                                      union prefixconstptr pu)
 253 {
 254         struct route_node rn, *node;
 255         prefix_copy(&rn.p, pu.p);
 256         apply_mask(&rn.p);
 257
 258         node = rn_hash_node_find(&table->hash, &rn);
 259         return (node && node->info) ? route_lock_node(node) : NULL;
 260 }
 261
 262 /* Lookup same prefix node.  Return NULL when we can't find route. */
 263 struct route_node *route_node_lookup_maynull(struct route_table *table,
 264                                              union prefixconstptr pu)
 265 {
 266         struct route_node rn, *node;
 267         prefix_copy(&rn.p, pu.p);
 268         apply_mask(&rn.p);
 269
 270         node = rn_hash_node_find(&table->hash, &rn);
 271         return node ? route_lock_node(node) : NULL;
 272 }
 273
 274 /* Add node to routing table. */
 275 struct route_node *route_node_get(struct route_table *table,
 276                                   union prefixconstptr pu)
 277 {
 278         struct route_node search;
 279         struct prefix *p = &search.p;
 280
 281         prefix_copy(p, pu.p);
 282         apply_mask(p);
 283
 284         struct route_node *new;
 285         struct route_node *node;
 286         struct route_node *match;
 287         uint16_t prefixlen = p->prefixlen;
 288         const uint8_t *prefix = &p->u.prefix;
 289
 290         node = rn_hash_node_find(&table->hash, &search);
 291         if (node && node->info)
 292                 return route_lock_node(node);
 293
 294         match = NULL;
 295         node = table->top;
 296         while (node && node->p.prefixlen <= prefixlen
 297                && prefix_match(&node->p, p)) {
 298                 if (node->p.prefixlen == prefixlen)
 299                         return route_lock_node(node);
 300
 301                 match = node;
 302                 node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 303         }
 304
 305         if (node == NULL) {
 306                 new = route_node_set(table, p);
 307                 if (match)
 308                         set_link(match, new);
 309                 else
 310                         table->top = new;
 311         } else {
 312                 new = route_node_new(table);
 313                 route_common(&node->p, p, &new->p);
 314                 new->p.family = p->family;
 315                 new->table = table;
 316                 set_link(new, node);
 317                 rn_hash_node_add(&table->hash, new);
 318
 319                 if (match)
 320                         set_link(match, new);
 321                 else
 322                         table->top = new;
 323
 324                 if (new->p.prefixlen != p->prefixlen) {
 325                         match = new;
 326                         new = route_node_set(table, p);
 327                         set_link(match, new);
 328                         table->count++;
 329                 }
 330         }
 331         table->count++;
 332         route_lock_node(new);
 333
 334         return new;
 335 }
 336
 337 /* Delete node from the routing table. */
 338 void route_node_delete(struct route_node *node)
 339 {
 340         struct route_node *child;
 341         struct route_node *parent;
 342
 343         assert(node->lock == 0);
 344         assert(node->info == NULL);
 345
 346         if (node->l_left && node->l_right)
 347                 return;
 348
 349         if (node->l_left)
 350                 child = node->l_left;
 351         else
 352                 child = node->l_right;
 353
 354         parent = node->parent;
 355
 356         if (child)
 357                 child->parent = parent;
 358
 359         if (parent) {
 360                 if (parent->l_left == node)
 361                         parent->l_left = child;
 362                 else
 363                         parent->l_right = child;
 364         } else
 365                 node->table->top = child;
 366
 367         node->table->count--;
 368
 369         rn_hash_node_del(&node->table->hash, node);
 370
 371         /* WARNING: FRAGILE CODE!
 372          * route_node_free may have the side effect of free'ing the entire
 373          * table.
 374          * this is permitted only if table->count got decremented to zero above,
 375          * because in that case parent will also be NULL, so that we won't try
 376          * to
 377          * delete a now-stale parent below.
 378          *
 379          * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */
 380
 381         route_node_free(node->table, node);
 382
 383         /* If parent node is stub then delete it also. */
 384         if (parent && parent->lock == 0)
 385                 route_node_delete(parent);
 386 }
 387
 388 /* Get fist node and lock it.  This function is useful when one want
 389    to lookup all the node exist in the routing table. */
 390 struct route_node *route_top(struct route_table *table)
 391 {
 392         /* If there is no node in the routing table return NULL. */
 393         if (table->top == NULL)
 394                 return NULL;
 395
 396         /* Lock the top node and return it. */
 397         route_lock_node(table->top);
 398         return table->top;
 399 }
 400
 401 /* Unlock current node and lock next node then return it. */
 402 struct route_node *route_next(struct route_node *node)
 403 {
 404         struct route_node *next;
 405         struct route_node *start;
 406
 407         /* Node may be deleted from route_unlock_node so we have to preserve
 408            next node's pointer. */
 409
 410         if (node->l_left) {
 411                 next = node->l_left;
 412                 route_lock_node(next);
 413                 route_unlock_node(node);
 414                 return next;
 415         }
 416         if (node->l_right) {
 417                 next = node->l_right;
 418                 route_lock_node(next);
 419                 route_unlock_node(node);
 420                 return next;
 421         }
 422
 423         start = node;
 424         while (node->parent) {
 425                 if (node->parent->l_left == node && node->parent->l_right) {
 426                         next = node->parent->l_right;
 427                         route_lock_node(next);
 428                         route_unlock_node(start);
 429                         return next;
 430                 }
 431                 node = node->parent;
 432         }
 433         route_unlock_node(start);
 434         return NULL;
 435 }
 436
 437 /* Unlock current node and lock next node until limit. */
 438 struct route_node *route_next_until(struct route_node *node,
 439                                     const struct route_node *limit)
 440 {
 441         struct route_node *next;
 442         struct route_node *start;
 443
 444         /* Node may be deleted from route_unlock_node so we have to preserve
 445            next node's pointer. */
 446
 447         if (node->l_left) {
 448                 next = node->l_left;
 449                 route_lock_node(next);
 450                 route_unlock_node(node);
 451                 return next;
 452         }
 453         if (node->l_right) {
 454                 next = node->l_right;
 455                 route_lock_node(next);
 456                 route_unlock_node(node);
 457                 return next;
 458         }
 459
 460         start = node;
 461         while (node->parent && node != limit) {
 462                 if (node->parent->l_left == node && node->parent->l_right) {
 463                         next = node->parent->l_right;
 464                         route_lock_node(next);
 465                         route_unlock_node(start);
 466                         return next;
 467                 }
 468                 node = node->parent;
 469         }
 470         route_unlock_node(start);
 471         return NULL;
 472 }
 473
 474 unsigned long route_table_count(struct route_table *table)
 475 {
 476         return table->count;
 477 }
 478
 479 /**
 480  * route_node_create
 481  *
 482  * Default function for creating a route node.
 483  */
 484 struct route_node *route_node_create(route_table_delegate_t *delegate,
 485                                      struct route_table *table)
 486 {
 487         struct route_node *node;
 488         node = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct route_node));
 489         return node;
 490 }
 491
 492 /**
 493  * route_node_destroy
 494  *
 495  * Default function for destroying a route node.
 496  */
 497 void route_node_destroy(route_table_delegate_t *delegate,
 498                         struct route_table *table, struct route_node *node)
 499 {
 500         XFREE(MTYPE_ROUTE_NODE, node);
 501 }
 502
 503 /*
 504  * Default delegate.
 505  */
 506 static route_table_delegate_t default_delegate = {
 507         .create_node = route_node_create,
 508         .destroy_node = route_node_destroy};
 509
 510 route_table_delegate_t *route_table_get_default_delegate(void)
 511 {
 512         return &default_delegate;
 513 }
 514
 515 /*
 516  * route_table_init
 517  */
 518 struct route_table *route_table_init(void)
 519 {
 520         return route_table_init_with_delegate(&default_delegate);
 521 }
 522
 523 /**
 524  * route_table_prefix_iter_cmp
 525  *
 526  * Compare two prefixes according to the order in which they appear in
 527  * an iteration over a tree.
 528  *
 529  * @return -1 if p1 occurs before p2 (p1 < p2)
 530  *          0 if the prefixes are identical (p1 == p2)
 531  *         +1 if p1 occurs after p2 (p1 > p2)
 532  */
 533 int route_table_prefix_iter_cmp(const struct prefix *p1,
 534                                 const struct prefix *p2)
 535 {
 536         struct prefix common_space;
 537         struct prefix *common = &common_space;
 538
 539         if (p1->prefixlen <= p2->prefixlen) {
 540                 if (prefix_match(p1, p2)) {
 541
 542                         /*
 543                          * p1 contains p2, or is equal to it.
 544                          */
 545                         return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
 546                 }
 547         } else {
 548
 549                 /*
 550                  * Check if p2 contains p1.
 551                  */
 552                 if (prefix_match(p2, p1))
 553                         return 1;
 554         }
 555
 556         route_common(p1, p2, common);
 557         assert(common->prefixlen < p1->prefixlen);
 558         assert(common->prefixlen < p2->prefixlen);
 559
 560         /*
 561          * Both prefixes are longer than the common prefix.
 562          *
 563          * We need to check the bit after the common prefixlen to determine
 564          * which one comes later.
 565          */
 566         if (prefix_bit(&p1->u.prefix, common->prefixlen)) {
 567
 568                 /*
 569                  * We branch to the right to get to p1 from the common prefix.
 570                  */
 571                 assert(!prefix_bit(&p2->u.prefix, common->prefixlen));
 572                 return 1;
 573         }
 574
 575         /*
 576          * We branch to the right to get to p2 from the common prefix.
 577          */
 578         assert(prefix_bit(&p2->u.prefix, common->prefixlen));
 579         return -1;
 580 }
 581
 582 /*
 583  * route_get_subtree_next
 584  *
 585  * Helper function that returns the first node that follows the nodes
 586  * in the sub-tree under 'node' in iteration order.
 587  */
 588 static struct route_node *route_get_subtree_next(struct route_node *node)
 589 {
 590         while (node->parent) {
 591                 if (node->parent->l_left == node && node->parent->l_right)
 592                         return node->parent->l_right;
 593
 594                 node = node->parent;
 595         }
 596
 597         return NULL;
 598 }
 599
 600 /**
 601  * route_table_get_next_internal
 602  *
 603  * Helper function to find the node that occurs after the given prefix in
 604  * order of iteration.
 605  *
 606  * @see route_table_get_next
 607  */
 608 static struct route_node *
 609 route_table_get_next_internal(struct route_table *table,
 610                               const struct prefix *p)
 611 {
 612         struct route_node *node, *tmp_node;
 613         int cmp;
 614
 615         node = table->top;
 616
 617         while (node) {
 618                 int match;
 619
 620                 if (node->p.prefixlen < p->prefixlen)
 621                         match = prefix_match(&node->p, p);
 622                 else
 623                         match = prefix_match(p, &node->p);
 624
 625                 if (match) {
 626                         if (node->p.prefixlen == p->prefixlen) {
 627
 628                                 /*
 629                                  * The prefix p exists in the tree, just return
 630                                  * the next
 631                                  * node.
 632                                  */
 633                                 route_lock_node(node);
 634                                 node = route_next(node);
 635                                 if (node)
 636                                         route_unlock_node(node);
 637
 638                                 return (node);
 639                         }
 640
 641                         if (node->p.prefixlen > p->prefixlen) {
 642
 643                                 /*
 644                                  * Node is in the subtree of p, and hence
 645                                  * greater than p.
 646                                  */
 647                                 return node;
 648                         }
 649
 650                         /*
 651                          * p is in the sub-tree under node.
 652                          */
 653                         tmp_node = node->link[prefix_bit(&p->u.prefix,
 654                                                          node->p.prefixlen)];
 655
 656                         if (tmp_node) {
 657                                 node = tmp_node;
 658                                 continue;
 659                         }
 660
 661                         /*
 662                          * There are no nodes in the direction where p should
 663                          * be. If
 664                          * node has a right child, then it must be greater than
 665                          * p.
 666                          */
 667                         if (node->l_right)
 668                                 return node->l_right;
 669
 670                         /*
 671                          * No more children to follow, go upwards looking for
 672                          * the next
 673                          * node.
 674                          */
 675                         return route_get_subtree_next(node);
 676                 }
 677
 678                 /*
 679                  * Neither node prefix nor 'p' contains the other.
 680                  */
 681                 cmp = route_table_prefix_iter_cmp(&node->p, p);
 682                 if (cmp > 0) {
 683
 684                         /*
 685                          * Node follows p in iteration order. Return it.
 686                          */
 687                         return node;
 688                 }
 689
 690                 assert(cmp < 0);
 691
 692                 /*
 693                  * Node and the subtree under it come before prefix p in
 694                  * iteration order. Prefix p and its sub-tree are not present in
 695                  * the tree. Go upwards and find the first node that follows the
 696                  * subtree. That node will also succeed p.
 697                  */
 698                 return route_get_subtree_next(node);
 699         }
 700
 701         return NULL;
 702 }
 703
 704 /**
 705  * route_table_get_next
 706  *
 707  * Find the node that occurs after the given prefix in order of
 708  * iteration.
 709  */
 710 struct route_node *route_table_get_next(struct route_table *table,
 711                                         union prefixconstptr pu)
 712 {
 713         const struct prefix *p = pu.p;
 714         struct route_node *node;
 715
 716         node = route_table_get_next_internal(table, p);
 717         if (node) {
 718                 assert(route_table_prefix_iter_cmp(&node->p, p) > 0);
 719                 route_lock_node(node);
 720         }
 721         return node;
 722 }
 723
 724 /*
 725  * route_table_iter_init
 726  */
 727 void route_table_iter_init(route_table_iter_t *iter, struct route_table *table)
 728 {
 729         memset(iter, 0, sizeof(*iter));
 730         iter->state = RT_ITER_STATE_INIT;
 731         iter->table = table;
 732 }
 733
 734 /*
 735  * route_table_iter_pause
 736  *
 737  * Pause an iteration over the table. This allows the iteration to be
 738  * resumed point after arbitrary additions/deletions from the table.
 739  * An iteration can be resumed by just calling route_table_iter_next()
 740  * on the iterator.
 741  */
 742 void route_table_iter_pause(route_table_iter_t *iter)
 743 {
 744         switch (iter->state) {
 745
 746         case RT_ITER_STATE_INIT:
 747         case RT_ITER_STATE_PAUSED:
 748         case RT_ITER_STATE_DONE:
 749                 return;
 750
 751         case RT_ITER_STATE_ITERATING:
 752
 753                 /*
 754                  * Save the prefix that we are currently at. The next call to
 755                  * route_table_iter_next() will return the node after this
 756                  * prefix
 757                  * in the tree.
 758                  */
 759                 prefix_copy(&iter->pause_prefix, &iter->current->p);
 760                 route_unlock_node(iter->current);
 761                 iter->current = NULL;
 762                 iter->state = RT_ITER_STATE_PAUSED;
 763                 return;
 764
 765         default:
 766                 assert(0);
 767         }
 768 }
 769
 770 /*
 771  * route_table_iter_cleanup
 772  *
 773  * Release any resources held by the iterator.
 774  */
 775 void route_table_iter_cleanup(route_table_iter_t *iter)
 776 {
 777         if (iter->state == RT_ITER_STATE_ITERATING) {
 778                 route_unlock_node(iter->current);
 779                 iter->current = NULL;
 780         }
 781         assert(!iter->current);
 782
 783         /*
 784          * Set the state to RT_ITER_STATE_DONE to make any
 785          * route_table_iter_next() calls on this iterator return NULL.
 786          */
 787         iter->state = RT_ITER_STATE_DONE;
 788 }