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