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