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