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
  18  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  19  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20  * 02111-1307, USA.
  21  */
  22
  23 #include <zebra.h>
  24
  25 #include "prefix.h"
  26 #include "table.h"
  27 #include "memory.h"
  28 #include "sockunion.h"
  29
  30 DEFINE_MTYPE(LIB, ROUTE_TABLE, "Route table")
  31 DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node")
  32
  33 static void route_node_delete(struct route_node *);
  34 static void route_table_free(struct route_table *);
  35
  36
  37 /*
  38  * route_table_init_with_delegate
  39  */
  40 struct route_table *
  41 route_table_init_with_delegate(route_table_delegate_t *delegate)
  42 {
  43         struct route_table *rt;
  44
  45         rt = XCALLOC(MTYPE_ROUTE_TABLE, sizeof(struct route_table));
  46         rt->delegate = delegate;
  47         return rt;
  48 }
  49
  50 void route_table_finish(struct route_table *rt)
  51 {
  52         route_table_free(rt);
  53 }
  54
  55 /* Allocate new route node. */
  56 static struct route_node *route_node_new(struct route_table *table)
  57 {
  58         return table->delegate->create_node(table->delegate, table);
  59 }
  60
  61 /* Allocate new route node with prefix set. */
  62 static struct route_node *route_node_set(struct route_table *table,
  63                                          const struct prefix *prefix)
  64 {
  65         struct route_node *node;
  66
  67         node = route_node_new(table);
  68
  69         prefix_copy(&node->p, prefix);
  70         node->table = table;
  71
  72         return node;
  73 }
  74
  75 /* Free route node. */
  76 static void route_node_free(struct route_table *table, struct route_node *node)
  77 {
  78         if (table->cleanup)
  79                 table->cleanup(table, node);
  80         table->delegate->destroy_node(table->delegate, table, node);
  81 }
  82
  83 /* Free route table. */
  84 static void route_table_free(struct route_table *rt)
  85 {
  86         struct route_node *tmp_node;
  87         struct route_node *node;
  88
  89         if (rt == NULL)
  90                 return;
  91
  92         node = rt->top;
  93
  94         /* Bulk deletion of nodes remaining in this table.  This function is not
  95            called until workers have completed their dependency on this table.
  96            A final route_unlock_node() will not be called for these nodes. */
  97         while (node) {
  98                 if (node->l_left) {
  99                         node = node->l_left;
 100                         continue;
 101                 }
 102
 103                 if (node->l_right) {
 104                         node = node->l_right;
 105                         continue;
 106                 }
 107
 108                 tmp_node = node;
 109                 node = node->parent;
 110
 111                 tmp_node->table->count--;
 112                 tmp_node->lock = 0; /* to cause assert if unlocked after this */
 113                 route_node_free(rt, tmp_node);
 114
 115                 if (node != NULL) {
 116                         if (node->l_left == tmp_node)
 117                                 node->l_left = NULL;
 118                         else
 119                                 node->l_right = NULL;
 120                 } else {
 121                         break;
 122                 }
 123         }
 124
 125         assert(rt->count == 0);
 126
 127         XFREE(MTYPE_ROUTE_TABLE, rt);
 128         return;
 129 }
 130
 131 /* Utility mask array. */
 132 static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
 133                                  0xf8, 0xfc, 0xfe, 0xff};
 134
 135 /* Common prefix route genaration. */
 136 static void route_common(const struct prefix *n, const struct prefix *p,
 137                          struct prefix *new)
 138 {
 139         int i;
 140         u_char diff;
 141         u_char mask;
 142
 143         const u_char *np = (const u_char *)&n->u.prefix;
 144         const u_char *pp = (const u_char *)&p->u.prefix;
 145         u_char *newp = (u_char *)&new->u.prefix;
 146
 147         for (i = 0; i < p->prefixlen / 8; i++) {
 148                 if (np[i] == pp[i])
 149                         newp[i] = np[i];
 150                 else
 151                         break;
 152         }
 153
 154         new->prefixlen = i * 8;
 155
 156         if (new->prefixlen != p->prefixlen) {
 157                 diff = np[i] ^ pp[i];
 158                 mask = 0x80;
 159                 while (new->prefixlen < p->prefixlen && !(mask & diff)) {
 160                         mask >>= 1;
 161                         new->prefixlen++;
 162                 }
 163                 newp[i] = np[i] & maskbit[new->prefixlen % 8];
 164         }
 165 }
 166
 167 static void set_link(struct route_node *node, struct route_node *new)
 168 {
 169         unsigned int bit = prefix_bit(&new->p.u.prefix, node->p.prefixlen);
 170
 171         node->link[bit] = new;
 172         new->parent = node;
 173 }
 174
 175 /* Lock node. */
 176 struct route_node *route_lock_node(struct route_node *node)
 177 {
 178         node->lock++;
 179         return node;
 180 }
 181
 182 /* Unlock node. */
 183 void route_unlock_node(struct route_node *node)
 184 {
 185         assert(node->lock > 0);
 186         node->lock--;
 187
 188         if (node->lock == 0)
 189                 route_node_delete(node);
 190 }
 191
 192 /* Find matched prefix. */
 193 struct route_node *route_node_match(const struct route_table *table,
 194                                     const struct prefix *p)
 195 {
 196         struct route_node *node;
 197         struct route_node *matched;
 198
 199         matched = NULL;
 200         node = table->top;
 201
 202         /* Walk down tree.  If there is matched route then store it to
 203            matched. */
 204         while (node && node->p.prefixlen <= p->prefixlen
 205                && prefix_match(&node->p, p)) {
 206                 if (node->info)
 207                         matched = node;
 208
 209                 if (node->p.prefixlen == p->prefixlen)
 210                         break;
 211
 212                 node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
 213         }
 214
 215         /* If matched route found, return it. */
 216         if (matched)
 217                 return route_lock_node(matched);
 218
 219         return NULL;
 220 }
 221
 222 struct route_node *route_node_match_ipv4(const struct route_table *table,
 223                                          const struct in_addr *addr)
 224 {
 225         struct prefix_ipv4 p;
 226
 227         memset(&p, 0, sizeof(struct prefix_ipv4));
 228         p.family = AF_INET;
 229         p.prefixlen = IPV4_MAX_PREFIXLEN;
 230         p.prefix = *addr;
 231
 232         return route_node_match(table, (struct prefix *)&p);
 233 }
 234
 235 struct route_node *route_node_match_ipv6(const struct route_table *table,
 236                                          const struct in6_addr *addr)
 237 {
 238         struct prefix_ipv6 p;
 239
 240         memset(&p, 0, sizeof(struct prefix_ipv6));
 241         p.family = AF_INET6;
 242         p.prefixlen = IPV6_MAX_PREFIXLEN;
 243         p.prefix = *addr;
 244
 245         return route_node_match(table, (struct prefix *)&p);
 246 }
 247
 248 /* Lookup same prefix node.  Return NULL when we can't find route. */
 249 struct route_node *route_node_lookup(const struct route_table *table,
 250                                      const struct prefix *p)
 251 {
 252         struct route_node *node;
 253         u_char prefixlen = p->prefixlen;
 254         const u_char *prefix = &p->u.prefix;
 255
 256         node = table->top;
 257
 258         while (node && node->p.prefixlen <= prefixlen
 259                && prefix_match(&node->p, p)) {
 260                 if (node->p.prefixlen == prefixlen)
 261                         return node->info ? route_lock_node(node) : NULL;
 262
 263                 node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 264         }
 265
 266         return NULL;
 267 }
 268
 269 /* Lookup same prefix node.  Return NULL when we can't find route. */
 270 struct route_node *route_node_lookup_maynull(const struct route_table *table,
 271                                              const struct prefix *p)
 272 {
 273         struct route_node *node;
 274         u_char prefixlen = p->prefixlen;
 275         const u_char *prefix = &p->u.prefix;
 276
 277         node = table->top;
 278
 279         while (node && node->p.prefixlen <= prefixlen
 280                && prefix_match(&node->p, p)) {
 281                 if (node->p.prefixlen == prefixlen)
 282                         return route_lock_node(node);
 283
 284                 node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 285         }
 286
 287         return NULL;
 288 }
 289
 290 /* Add node to routing table. */
 291 struct route_node *route_node_get(struct route_table *const table,
 292                                   const struct prefix *p)
 293 {
 294         struct route_node *new;
 295         struct route_node *node;
 296         struct route_node *match;
 297         u_char prefixlen = p->prefixlen;
 298         const u_char *prefix = &p->u.prefix;
 299
 300         match = NULL;
 301         node = table->top;
 302         while (node && node->p.prefixlen <= prefixlen
 303                && prefix_match(&node->p, p)) {
 304                 if (node->p.prefixlen == prefixlen)
 305                         return route_lock_node(node);
 306
 307                 match = node;
 308                 node = node->link[prefix_bit(prefix, node->p.prefixlen)];
 309         }
 310
 311         if (node == NULL) {
 312                 new = route_node_set(table, p);
 313                 if (match)
 314                         set_link(match, new);
 315                 else
 316                         table->top = new;
 317         } else {
 318                 new = route_node_new(table);
 319                 route_common(&node->p, p, &new->p);
 320                 new->p.family = p->family;
 321                 new->table = table;
 322                 set_link(new, node);
 323
 324                 if (match)
 325                         set_link(match, new);
 326                 else
 327                         table->top = new;
 328
 329                 if (new->p.prefixlen != p->prefixlen) {
 330                         match = new;
 331                         new = route_node_set(table, p);
 332                         set_link(match, new);
 333                         table->count++;
 334                 }
 335         }
 336         table->count++;
 337         route_lock_node(new);
 338
 339         return new;
 340 }
 341
 342 /* Delete node from the routing table. */
 343 static void route_node_delete(struct route_node *node)
 344 {
 345         struct route_node *child;
 346         struct route_node *parent;
 347
 348         assert(node->lock == 0);
 349         assert(node->info == NULL);
 350
 351         if (node->l_left && node->l_right)
 352                 return;
 353
 354         if (node->l_left)
 355                 child = node->l_left;
 356         else
 357                 child = node->l_right;
 358
 359         parent = node->parent;
 360
 361         if (child)
 362                 child->parent = parent;
 363
 364         if (parent) {
 365                 if (parent->l_left == node)
 366                         parent->l_left = child;
 367                 else
 368                         parent->l_right = child;
 369         } else
 370                 node->table->top = child;
 371
 372         node->table->count--;
 373
 374         /* WARNING: FRAGILE CODE!
 375          * route_node_free may have the side effect of free'ing the entire
 376          * table.
 377          * this is permitted only if table->count got decremented to zero above,
 378          * because in that case parent will also be NULL, so that we won't try
 379          * to
 380          * delete a now-stale parent below.
 381          *
 382          * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */
 383
 384         route_node_free(node->table, node);
 385
 386         /* If parent node is stub then delete it also. */
 387         if (parent && parent->lock == 0)
 388                 route_node_delete(parent);
 389 }
 390
 391 /* Get fist node and lock it.  This function is useful when one want
 392    to lookup all the node exist in the routing table. */
 393 struct route_node *route_top(struct route_table *table)
 394 {
 395         /* If there is no node in the routing table return NULL. */
 396         if (table->top == NULL)
 397                 return NULL;
 398
 399         /* Lock the top node and return it. */
 400         route_lock_node(table->top);
 401         return table->top;
 402 }
 403
 404 /* Unlock current node and lock next node then return it. */
 405 struct route_node *route_next(struct route_node *node)
 406 {
 407         struct route_node *next;
 408         struct route_node *start;
 409
 410         /* Node may be deleted from route_unlock_node so we have to preserve
 411            next node's pointer. */
 412
 413         if (node->l_left) {
 414                 next = node->l_left;
 415                 route_lock_node(next);
 416                 route_unlock_node(node);
 417                 return next;
 418         }
 419         if (node->l_right) {
 420                 next = node->l_right;
 421                 route_lock_node(next);
 422                 route_unlock_node(node);
 423                 return next;
 424         }
 425
 426         start = node;
 427         while (node->parent) {
 428                 if (node->parent->l_left == node && node->parent->l_right) {
 429                         next = node->parent->l_right;
 430                         route_lock_node(next);
 431                         route_unlock_node(start);
 432                         return next;
 433                 }
 434                 node = node->parent;
 435         }
 436         route_unlock_node(start);
 437         return NULL;
 438 }
 439
 440 /* Unlock current node and lock next node until limit. */
 441 struct route_node *route_next_until(struct route_node *node,
 442                                     struct route_node *limit)
 443 {
 444         struct route_node *next;
 445         struct route_node *start;
 446
 447         /* Node may be deleted from route_unlock_node so we have to preserve
 448            next node's pointer. */
 449
 450         if (node->l_left) {
 451                 next = node->l_left;
 452                 route_lock_node(next);
 453                 route_unlock_node(node);
 454                 return next;
 455         }
 456         if (node->l_right) {
 457                 next = node->l_right;
 458                 route_lock_node(next);
 459                 route_unlock_node(node);
 460                 return next;
 461         }
 462
 463         start = node;
 464         while (node->parent && node != limit) {
 465                 if (node->parent->l_left == node && node->parent->l_right) {
 466                         next = node->parent->l_right;
 467                         route_lock_node(next);
 468                         route_unlock_node(start);
 469                         return next;
 470                 }
 471                 node = node->parent;
 472         }
 473         route_unlock_node(start);
 474         return NULL;
 475 }
 476
 477 unsigned long route_table_count(const struct route_table *table)
 478 {
 479         return table->count;
 480 }
 481
 482 /**
 483  * route_node_create
 484  *
 485  * Default function for creating a route node.
 486  */
 487 struct route_node *route_node_create(route_table_delegate_t *delegate,
 488                                      struct route_table *table)
 489 {
 490         struct route_node *node;
 491         node = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct route_node));
 492         return node;
 493 }
 494
 495 /**
 496  * route_node_destroy
 497  *
 498  * Default function for destroying a route node.
 499  */
 500 void route_node_destroy(route_table_delegate_t *delegate,
 501                         struct route_table *table, struct route_node *node)
 502 {
 503         XFREE(MTYPE_ROUTE_NODE, node);
 504 }
 505
 506 /*
 507  * Default delegate.
 508  */
 509 static route_table_delegate_t default_delegate = {
 510         .create_node = route_node_create,
 511         .destroy_node = route_node_destroy};
 512
 513 route_table_delegate_t *route_table_get_default_delegate(void)
 514 {
 515         return &default_delegate;
 516 }
 517
 518 /*
 519  * route_table_init
 520  */
 521 struct route_table *route_table_init(void)
 522 {
 523         return route_table_init_with_delegate(&default_delegate);
 524 }
 525
 526 /**
 527  * route_table_prefix_iter_cmp
 528  *
 529  * Compare two prefixes according to the order in which they appear in
 530  * an iteration over a tree.
 531  *
 532  * @return -1 if p1 occurs before p2 (p1 < p2)
 533  *          0 if the prefixes are identical (p1 == p2)
 534  *         +1 if p1 occurs after p2 (p1 > p2)
 535  */
 536 int route_table_prefix_iter_cmp(struct prefix *p1, struct prefix *p2)
 537 {
 538         struct prefix common_space;
 539         struct prefix *common = &common_space;
 540
 541         if (p1->prefixlen <= p2->prefixlen) {
 542                 if (prefix_match(p1, p2)) {
 543
 544                         /*
 545                          * p1 contains p2, or is equal to it.
 546                          */
 547                         return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
 548                 }
 549         } else {
 550
 551                 /*
 552                  * Check if p2 contains p1.
 553                  */
 554                 if (prefix_match(p2, p1))
 555                         return 1;
 556         }
 557
 558         route_common(p1, p2, common);
 559         assert(common->prefixlen < p1->prefixlen);
 560         assert(common->prefixlen < p2->prefixlen);
 561
 562         /*
 563          * Both prefixes are longer than the common prefix.
 564          *
 565          * We need to check the bit after the common prefixlen to determine
 566          * which one comes later.
 567          */
 568         if (prefix_bit(&p1->u.prefix, common->prefixlen)) {
 569
 570                 /*
 571                  * We branch to the right to get to p1 from the common prefix.
 572                  */
 573                 assert(!prefix_bit(&p2->u.prefix, common->prefixlen));
 574                 return 1;
 575         }
 576
 577         /*
 578          * We branch to the right to get to p2 from the common prefix.
 579          */
 580         assert(prefix_bit(&p2->u.prefix, common->prefixlen));
 581         return -1;
 582 }
 583
 584 /*
 585  * route_get_subtree_next
 586  *
 587  * Helper function that returns the first node that follows the nodes
 588  * in the sub-tree under 'node' in iteration order.
 589  */
 590 static struct route_node *route_get_subtree_next(struct route_node *node)
 591 {
 592         while (node->parent) {
 593                 if (node->parent->l_left == node && node->parent->l_right)
 594                         return node->parent->l_right;
 595
 596                 node = node->parent;
 597         }
 598
 599         return NULL;
 600 }
 601
 602 /**
 603  * route_table_get_next_internal
 604  *
 605  * Helper function to find the node that occurs after the given prefix in
 606  * order of iteration.
 607  *
 608  * @see route_table_get_next
 609  */
 610 static struct route_node *
 611 route_table_get_next_internal(const struct route_table *table, 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                                         struct prefix *p)
 713 {
 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 }