net/ipv6/ip6_fib.c

   1 /*
   2  *      Linux INET6 implementation
   3  *      Forwarding Information Database
   4  *
   5  *      Authors:
   6  *      Pedro Roque             <roque@di.fc.ul.pt>
   7  *
   8  *      $Id: ip6_fib.c,v 1.25 2001/10/31 21:55:55 davem Exp $
   9  *
  10  *      This program is free software; you can redistribute it and/or
  11  *      modify it under the terms of the GNU General Public License
  12  *      as published by the Free Software Foundation; either version
  13  *      2 of the License, or (at your option) any later version.
  14  */
  15
  16 /*
  17  *      Changes:
  18  *      Yuji SEKIYA @USAGI:     Support default route on router node;
  19  *                              remove ip6_null_entry from the top of
  20  *                              routing table.
  21  */
  22 #include <linux/errno.h>
  23 #include <linux/types.h>
  24 #include <linux/net.h>
  25 #include <linux/route.h>
  26 #include <linux/netdevice.h>
  27 #include <linux/in6.h>
  28 #include <linux/init.h>
  29 #include <linux/list.h>
  30
  31 #ifdef  CONFIG_PROC_FS
  32 #include <linux/proc_fs.h>
  33 #endif
  34
  35 #include <net/ipv6.h>
  36 #include <net/ndisc.h>
  37 #include <net/addrconf.h>
  38
  39 #include <net/ip6_fib.h>
  40 #include <net/ip6_route.h>
  41
  42 #define RT6_DEBUG 2
  43
  44 #if RT6_DEBUG >= 3
  45 #define RT6_TRACE(x...) printk(KERN_DEBUG x)
  46 #else
  47 #define RT6_TRACE(x...) do { ; } while (0)
  48 #endif
  49
  50 struct rt6_statistics   rt6_stats;
  51
  52 static kmem_cache_t * fib6_node_kmem __read_mostly;
  53
  54 enum fib_walk_state_t
  55 {
  56 #ifdef CONFIG_IPV6_SUBTREES
  57         FWS_S,
  58 #endif
  59         FWS_L,
  60         FWS_R,
  61         FWS_C,
  62         FWS_U
  63 };
  64
  65 struct fib6_cleaner_t
  66 {
  67         struct fib6_walker_t w;
  68         int (*func)(struct rt6_info *, void *arg);
  69         void *arg;
  70 };
  71
  72 DEFINE_RWLOCK(fib6_walker_lock);
  73
  74
  75 #ifdef CONFIG_IPV6_SUBTREES
  76 #define FWS_INIT FWS_S
  77 #define SUBTREE(fn) ((fn)->subtree)
  78 #else
  79 #define FWS_INIT FWS_L
  80 #define SUBTREE(fn) NULL
  81 #endif
  82
  83 static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt);
  84 static struct fib6_node * fib6_repair_tree(struct fib6_node *fn);
  85
  86 /*
  87  *      A routing update causes an increase of the serial number on the
  88  *      affected subtree. This allows for cached routes to be asynchronously
  89  *      tested when modifications are made to the destination cache as a
  90  *      result of redirects, path MTU changes, etc.
  91  */
  92
  93 static __u32 rt_sernum;
  94
  95 static DEFINE_TIMER(ip6_fib_timer, fib6_run_gc, 0, 0);
  96
  97 struct fib6_walker_t fib6_walker_list = {
  98         .prev   = &fib6_walker_list,
  99         .next   = &fib6_walker_list,
 100 };
 101
 102 #define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)
 103
 104 static __inline__ u32 fib6_new_sernum(void)
 105 {
 106         u32 n = ++rt_sernum;
 107         if ((__s32)n <= 0)
 108                 rt_sernum = n = 1;
 109         return n;
 110 }
 111
 112 /*
 113  *      Auxiliary address test functions for the radix tree.
 114  *
 115  *      These assume a 32bit processor (although it will work on
 116  *      64bit processors)
 117  */
 118
 119 /*
 120  *      test bit
 121  */
 122
 123 static __inline__ int addr_bit_set(void *token, int fn_bit)
 124 {
 125         __u32 *addr = token;
 126
 127         return htonl(1 << ((~fn_bit)&0x1F)) & addr[fn_bit>>5];
 128 }
 129
 130 static __inline__ struct fib6_node * node_alloc(void)
 131 {
 132         struct fib6_node *fn;
 133
 134         if ((fn = kmem_cache_alloc(fib6_node_kmem, SLAB_ATOMIC)) != NULL)
 135                 memset(fn, 0, sizeof(struct fib6_node));
 136
 137         return fn;
 138 }
 139
 140 static __inline__ void node_free(struct fib6_node * fn)
 141 {
 142         kmem_cache_free(fib6_node_kmem, fn);
 143 }
 144
 145 static __inline__ void rt6_release(struct rt6_info *rt)
 146 {
 147         if (atomic_dec_and_test(&rt->rt6i_ref))
 148                 dst_free(&rt->u.dst);
 149 }
 150
 151 static struct fib6_table fib6_main_tbl = {
 152         .tb6_id         = RT6_TABLE_MAIN,
 153         .tb6_lock       = RW_LOCK_UNLOCKED,
 154         .tb6_root       = {
 155                 .leaf           = &ip6_null_entry,
 156                 .fn_flags       = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO,
 157         },
 158 };
 159
 160 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
 161
 162 static struct fib6_table fib6_local_tbl = {
 163         .tb6_id         = RT6_TABLE_LOCAL,
 164         .tb6_lock       = RW_LOCK_UNLOCKED,
 165         .tb6_root       = {
 166                 .leaf           = &ip6_null_entry,
 167                 .fn_flags       = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO,
 168         },
 169 };
 170
 171 #define FIB_TABLE_HASHSZ 256
 172 static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ];
 173
 174 static struct fib6_table *fib6_alloc_table(u32 id)
 175 {
 176         struct fib6_table *table;
 177
 178         table = kzalloc(sizeof(*table), GFP_ATOMIC);
 179         if (table != NULL) {
 180                 table->tb6_id = id;
 181                 table->tb6_lock = RW_LOCK_UNLOCKED;
 182                 table->tb6_root.leaf = &ip6_null_entry;
 183                 table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
 184         }
 185
 186         return table;
 187 }
 188
 189 static void fib6_link_table(struct fib6_table *tb)
 190 {
 191         unsigned int h;
 192
 193         h = tb->tb6_id & (FIB_TABLE_HASHSZ - 1);
 194
 195         /*
 196          * No protection necessary, this is the only list mutatation
 197          * operation, tables never disappear once they exist.
 198          */
 199         hlist_add_head_rcu(&tb->tb6_hlist, &fib_table_hash[h]);
 200 }
 201
 202 struct fib6_table *fib6_new_table(u32 id)
 203 {
 204         struct fib6_table *tb;
 205
 206         if (id == 0)
 207                 id = RT6_TABLE_MAIN;
 208         tb = fib6_get_table(id);
 209         if (tb)
 210                 return tb;
 211
 212         tb = fib6_alloc_table(id);
 213         if (tb != NULL)
 214                 fib6_link_table(tb);
 215
 216         return tb;
 217 }
 218
 219 struct fib6_table *fib6_get_table(u32 id)
 220 {
 221         struct fib6_table *tb;
 222         struct hlist_node *node;
 223         unsigned int h;
 224
 225         if (id == 0)
 226                 id = RT6_TABLE_MAIN;
 227         h = id & (FIB_TABLE_HASHSZ - 1);
 228         rcu_read_lock();
 229         hlist_for_each_entry_rcu(tb, node, &fib_table_hash[h], tb6_hlist) {
 230                 if (tb->tb6_id == id) {
 231                         rcu_read_unlock();
 232                         return tb;
 233                 }
 234         }
 235         rcu_read_unlock();
 236
 237         return NULL;
 238 }
 239
 240 static void __init fib6_tables_init(void)
 241 {
 242         fib6_link_table(&fib6_main_tbl);
 243         fib6_link_table(&fib6_local_tbl);
 244 }
 245
 246 #else
 247
 248 struct fib6_table *fib6_new_table(u32 id)
 249 {
 250         return fib6_get_table(id);
 251 }
 252
 253 struct fib6_table *fib6_get_table(u32 id)
 254 {
 255         return &fib6_main_tbl;
 256 }
 257
 258 struct dst_entry *fib6_rule_lookup(struct flowi *fl, int flags,
 259                                    pol_lookup_t lookup)
 260 {
 261         return (struct dst_entry *) lookup(&fib6_main_tbl, fl, flags);
 262 }
 263
 264 static void __init fib6_tables_init(void)
 265 {
 266 }
 267
 268 #endif
 269
 270
 271 /*
 272  *      Routing Table
 273  *
 274  *      return the appropriate node for a routing tree "add" operation
 275  *      by either creating and inserting or by returning an existing
 276  *      node.
 277  */
 278
 279 static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
 280                                      int addrlen, int plen,
 281                                      int offset)
 282 {
 283         struct fib6_node *fn, *in, *ln;
 284         struct fib6_node *pn = NULL;
 285         struct rt6key *key;
 286         int     bit;
 287         int     dir = 0;
 288         __u32   sernum = fib6_new_sernum();
 289
 290         RT6_TRACE("fib6_add_1\n");
 291
 292         /* insert node in tree */
 293
 294         fn = root;
 295
 296         do {
 297                 key = (struct rt6key *)((u8 *)fn->leaf + offset);
 298
 299                 /*
 300                  *      Prefix match
 301                  */
 302                 if (plen < fn->fn_bit ||
 303                     !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
 304                         goto insert_above;
 305
 306                 /*
 307                  *      Exact match ?
 308                  */
 309
 310                 if (plen == fn->fn_bit) {
 311                         /* clean up an intermediate node */
 312                         if ((fn->fn_flags & RTN_RTINFO) == 0) {
 313                                 rt6_release(fn->leaf);
 314                                 fn->leaf = NULL;
 315                         }
 316
 317                         fn->fn_sernum = sernum;
 318
 319                         return fn;
 320                 }
 321
 322                 /*
 323                  *      We have more bits to go
 324                  */
 325
 326                 /* Try to walk down on tree. */
 327                 fn->fn_sernum = sernum;
 328                 dir = addr_bit_set(addr, fn->fn_bit);
 329                 pn = fn;
 330                 fn = dir ? fn->right: fn->left;
 331         } while (fn);
 332
 333         /*
 334          *      We walked to the bottom of tree.
 335          *      Create new leaf node without children.
 336          */
 337
 338         ln = node_alloc();
 339
 340         if (ln == NULL)
 341                 return NULL;
 342         ln->fn_bit = plen;
 343
 344         ln->parent = pn;
 345         ln->fn_sernum = sernum;
 346
 347         if (dir)
 348                 pn->right = ln;
 349         else
 350                 pn->left  = ln;
 351
 352         return ln;
 353
 354
 355 insert_above:
 356         /*
 357          * split since we don't have a common prefix anymore or
 358          * we have a less significant route.
 359          * we've to insert an intermediate node on the list
 360          * this new node will point to the one we need to create
 361          * and the current
 362          */
 363
 364         pn = fn->parent;
 365
 366         /* find 1st bit in difference between the 2 addrs.
 367
 368            See comment in __ipv6_addr_diff: bit may be an invalid value,
 369            but if it is >= plen, the value is ignored in any case.
 370          */
 371
 372         bit = __ipv6_addr_diff(addr, &key->addr, addrlen);
 373
 374         /*
 375          *              (intermediate)[in]
 376          *                /        \
 377          *      (new leaf node)[ln] (old node)[fn]
 378          */
 379         if (plen > bit) {
 380                 in = node_alloc();
 381                 ln = node_alloc();
 382
 383                 if (in == NULL || ln == NULL) {
 384                         if (in)
 385                                 node_free(in);
 386                         if (ln)
 387                                 node_free(ln);
 388                         return NULL;
 389                 }
 390
 391                 /*
 392                  * new intermediate node.
 393                  * RTN_RTINFO will
 394                  * be off since that an address that chooses one of
 395                  * the branches would not match less specific routes
 396                  * in the other branch
 397                  */
 398
 399                 in->fn_bit = bit;
 400
 401                 in->parent = pn;
 402                 in->leaf = fn->leaf;
 403                 atomic_inc(&in->leaf->rt6i_ref);
 404
 405                 in->fn_sernum = sernum;
 406
 407                 /* update parent pointer */
 408                 if (dir)
 409                         pn->right = in;
 410                 else
 411                         pn->left  = in;
 412
 413                 ln->fn_bit = plen;
 414
 415                 ln->parent = in;
 416                 fn->parent = in;
 417
 418                 ln->fn_sernum = sernum;
 419
 420                 if (addr_bit_set(addr, bit)) {
 421                         in->right = ln;
 422                         in->left  = fn;
 423                 } else {
 424                         in->left  = ln;
 425                         in->right = fn;
 426                 }
 427         } else { /* plen <= bit */
 428
 429                 /*
 430                  *              (new leaf node)[ln]
 431                  *                /        \
 432                  *           (old node)[fn] NULL
 433                  */
 434
 435                 ln = node_alloc();
 436
 437                 if (ln == NULL)
 438                         return NULL;
 439
 440                 ln->fn_bit = plen;
 441
 442                 ln->parent = pn;
 443
 444                 ln->fn_sernum = sernum;
 445
 446                 if (dir)
 447                         pn->right = ln;
 448                 else
 449                         pn->left  = ln;
 450
 451                 if (addr_bit_set(&key->addr, plen))
 452                         ln->right = fn;
 453                 else
 454                         ln->left  = fn;
 455
 456                 fn->parent = ln;
 457         }
 458         return ln;
 459 }
 460
 461 /*
 462  *      Insert routing information in a node.
 463  */
 464
 465 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
 466                 struct nlmsghdr *nlh,  struct netlink_skb_parms *req)
 467 {
 468         struct rt6_info *iter = NULL;
 469         struct rt6_info **ins;
 470
 471         ins = &fn->leaf;
 472
 473         if (fn->fn_flags&RTN_TL_ROOT &&
 474             fn->leaf == &ip6_null_entry &&
 475             !(rt->rt6i_flags & (RTF_DEFAULT | RTF_ADDRCONF)) ){
 476                 fn->leaf = rt;
 477                 rt->u.next = NULL;
 478                 goto out;
 479         }
 480
 481         for (iter = fn->leaf; iter; iter=iter->u.next) {
 482                 /*
 483                  *      Search for duplicates
 484                  */
 485
 486                 if (iter->rt6i_metric == rt->rt6i_metric) {
 487                         /*
 488                          *      Same priority level
 489                          */
 490
 491                         if (iter->rt6i_dev == rt->rt6i_dev &&
 492                             iter->rt6i_idev == rt->rt6i_idev &&
 493                             ipv6_addr_equal(&iter->rt6i_gateway,
 494                                             &rt->rt6i_gateway)) {
 495                                 if (!(iter->rt6i_flags&RTF_EXPIRES))
 496                                         return -EEXIST;
 497                                 iter->rt6i_expires = rt->rt6i_expires;
 498                                 if (!(rt->rt6i_flags&RTF_EXPIRES)) {
 499                                         iter->rt6i_flags &= ~RTF_EXPIRES;
 500                                         iter->rt6i_expires = 0;
 501                                 }
 502                                 return -EEXIST;
 503                         }
 504                 }
 505
 506                 if (iter->rt6i_metric > rt->rt6i_metric)
 507                         break;
 508
 509                 ins = &iter->u.next;
 510         }
 511
 512         /*
 513          *      insert node
 514          */
 515
 516 out:
 517         rt->u.next = iter;
 518         *ins = rt;
 519         rt->rt6i_node = fn;
 520         atomic_inc(&rt->rt6i_ref);
 521         inet6_rt_notify(RTM_NEWROUTE, rt, nlh, req);
 522         rt6_stats.fib_rt_entries++;
 523
 524         if ((fn->fn_flags & RTN_RTINFO) == 0) {
 525                 rt6_stats.fib_route_nodes++;
 526                 fn->fn_flags |= RTN_RTINFO;
 527         }
 528
 529         return 0;
 530 }
 531
 532 static __inline__ void fib6_start_gc(struct rt6_info *rt)
 533 {
 534         if (ip6_fib_timer.expires == 0 &&
 535             (rt->rt6i_flags & (RTF_EXPIRES|RTF_CACHE)))
 536                 mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
 537 }
 538
 539 void fib6_force_start_gc(void)
 540 {
 541         if (ip6_fib_timer.expires == 0)
 542                 mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
 543 }
 544
 545 /*
 546  *      Add routing information to the routing tree.
 547  *      <destination addr>/<source addr>
 548  *      with source addr info in sub-trees
 549  */
 550
 551 int fib6_add(struct fib6_node *root, struct rt6_info *rt,
 552                 struct nlmsghdr *nlh, void *_rtattr, struct netlink_skb_parms *req)
 553 {
 554         struct fib6_node *fn;
 555         int err = -ENOMEM;
 556
 557         fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
 558                         rt->rt6i_dst.plen, offsetof(struct rt6_info, rt6i_dst));
 559
 560         if (fn == NULL)
 561                 goto out;
 562
 563 #ifdef CONFIG_IPV6_SUBTREES
 564         if (rt->rt6i_src.plen) {
 565                 struct fib6_node *sn;
 566
 567                 if (fn->subtree == NULL) {
 568                         struct fib6_node *sfn;
 569
 570                         /*
 571                          * Create subtree.
 572                          *
 573                          *              fn[main tree]
 574                          *              |
 575                          *              sfn[subtree root]
 576                          *                 \
 577                          *                  sn[new leaf node]
 578                          */
 579
 580                         /* Create subtree root node */
 581                         sfn = node_alloc();
 582                         if (sfn == NULL)
 583                                 goto st_failure;
 584
 585                         sfn->leaf = &ip6_null_entry;
 586                         atomic_inc(&ip6_null_entry.rt6i_ref);
 587                         sfn->fn_flags = RTN_ROOT;
 588                         sfn->fn_sernum = fib6_new_sernum();
 589
 590                         /* Now add the first leaf node to new subtree */
 591
 592                         sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
 593                                         sizeof(struct in6_addr), rt->rt6i_src.plen,
 594                                         offsetof(struct rt6_info, rt6i_src));
 595
 596                         if (sn == NULL) {
 597                                 /* If it is failed, discard just allocated
 598                                    root, and then (in st_failure) stale node
 599                                    in main tree.
 600                                  */
 601                                 node_free(sfn);
 602                                 goto st_failure;
 603                         }
 604
 605                         /* Now link new subtree to main tree */
 606                         sfn->parent = fn;
 607                         fn->subtree = sfn;
 608                         if (fn->leaf == NULL) {
 609                                 fn->leaf = rt;
 610                                 atomic_inc(&rt->rt6i_ref);
 611                         }
 612                 } else {
 613                         sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
 614                                         sizeof(struct in6_addr), rt->rt6i_src.plen,
 615                                         offsetof(struct rt6_info, rt6i_src));
 616
 617                         if (sn == NULL)
 618                                 goto st_failure;
 619                 }
 620
 621                 fn = sn;
 622         }
 623 #endif
 624
 625         err = fib6_add_rt2node(fn, rt, nlh, req);
 626
 627         if (err == 0) {
 628                 fib6_start_gc(rt);
 629                 if (!(rt->rt6i_flags&RTF_CACHE))
 630                         fib6_prune_clones(fn, rt);
 631         }
 632
 633 out:
 634         if (err)
 635                 dst_free(&rt->u.dst);
 636         return err;
 637
 638 #ifdef CONFIG_IPV6_SUBTREES
 639         /* Subtree creation failed, probably main tree node
 640            is orphan. If it is, shoot it.
 641          */
 642 st_failure:
 643         if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
 644                 fib6_repair_tree(fn);
 645         dst_free(&rt->u.dst);
 646         return err;
 647 #endif
 648 }
 649
 650 /*
 651  *      Routing tree lookup
 652  *
 653  */
 654
 655 struct lookup_args {
 656         int             offset;         /* key offset on rt6_info       */
 657         struct in6_addr *addr;          /* search key                   */
 658 };
 659
 660 static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
 661                                         struct lookup_args *args)
 662 {
 663         struct fib6_node *fn;
 664         int dir;
 665
 666         /*
 667          *      Descend on a tree
 668          */
 669
 670         fn = root;
 671
 672         for (;;) {
 673                 struct fib6_node *next;
 674
 675                 dir = addr_bit_set(args->addr, fn->fn_bit);
 676
 677                 next = dir ? fn->right : fn->left;
 678
 679                 if (next) {
 680                         fn = next;
 681                         continue;
 682                 }
 683
 684                 break;
 685         }
 686
 687         while ((fn->fn_flags & RTN_ROOT) == 0) {
 688 #ifdef CONFIG_IPV6_SUBTREES
 689                 if (fn->subtree) {
 690                         struct fib6_node *st;
 691                         struct lookup_args *narg;
 692
 693                         narg = args + 1;
 694
 695                         if (narg->addr) {
 696                                 st = fib6_lookup_1(fn->subtree, narg);
 697
 698                                 if (st && !(st->fn_flags & RTN_ROOT))
 699                                         return st;
 700                         }
 701                 }
 702 #endif
 703
 704                 if (fn->fn_flags & RTN_RTINFO) {
 705                         struct rt6key *key;
 706
 707                         key = (struct rt6key *) ((u8 *) fn->leaf +
 708                                                  args->offset);
 709
 710                         if (ipv6_prefix_equal(&key->addr, args->addr, key->plen))
 711                                 return fn;
 712                 }
 713
 714                 fn = fn->parent;
 715         }
 716
 717         return NULL;
 718 }
 719
 720 struct fib6_node * fib6_lookup(struct fib6_node *root, struct in6_addr *daddr,
 721                                struct in6_addr *saddr)
 722 {
 723         struct lookup_args args[2];
 724         struct fib6_node *fn;
 725
 726         args[0].offset = offsetof(struct rt6_info, rt6i_dst);
 727         args[0].addr = daddr;
 728
 729 #ifdef CONFIG_IPV6_SUBTREES
 730         args[1].offset = offsetof(struct rt6_info, rt6i_src);
 731         args[1].addr = saddr;
 732 #endif
 733
 734         fn = fib6_lookup_1(root, args);
 735
 736         if (fn == NULL || fn->fn_flags & RTN_TL_ROOT)
 737                 fn = root;
 738
 739         return fn;
 740 }
 741
 742 /*
 743  *      Get node with specified destination prefix (and source prefix,
 744  *      if subtrees are used)
 745  */
 746
 747
 748 static struct fib6_node * fib6_locate_1(struct fib6_node *root,
 749                                         struct in6_addr *addr,
 750                                         int plen, int offset)
 751 {
 752         struct fib6_node *fn;
 753
 754         for (fn = root; fn ; ) {
 755                 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
 756
 757                 /*
 758                  *      Prefix match
 759                  */
 760                 if (plen < fn->fn_bit ||
 761                     !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
 762                         return NULL;
 763
 764                 if (plen == fn->fn_bit)
 765                         return fn;
 766
 767                 /*
 768                  *      We have more bits to go
 769                  */
 770                 if (addr_bit_set(addr, fn->fn_bit))
 771                         fn = fn->right;
 772                 else
 773                         fn = fn->left;
 774         }
 775         return NULL;
 776 }
 777
 778 struct fib6_node * fib6_locate(struct fib6_node *root,
 779                                struct in6_addr *daddr, int dst_len,
 780                                struct in6_addr *saddr, int src_len)
 781 {
 782         struct fib6_node *fn;
 783
 784         fn = fib6_locate_1(root, daddr, dst_len,
 785                            offsetof(struct rt6_info, rt6i_dst));
 786
 787 #ifdef CONFIG_IPV6_SUBTREES
 788         if (src_len) {
 789                 BUG_TRAP(saddr!=NULL);
 790                 if (fn == NULL)
 791                         fn = fn->subtree;
 792                 if (fn)
 793                         fn = fib6_locate_1(fn, saddr, src_len,
 794                                            offsetof(struct rt6_info, rt6i_src));
 795         }
 796 #endif
 797
 798         if (fn && fn->fn_flags&RTN_RTINFO)
 799                 return fn;
 800
 801         return NULL;
 802 }
 803
 804
 805 /*
 806  *      Deletion
 807  *
 808  */
 809
 810 static struct rt6_info * fib6_find_prefix(struct fib6_node *fn)
 811 {
 812         if (fn->fn_flags&RTN_ROOT)
 813                 return &ip6_null_entry;
 814
 815         while(fn) {
 816                 if(fn->left)
 817                         return fn->left->leaf;
 818
 819                 if(fn->right)
 820                         return fn->right->leaf;
 821
 822                 fn = SUBTREE(fn);
 823         }
 824         return NULL;
 825 }
 826
 827 /*
 828  *      Called to trim the tree of intermediate nodes when possible. "fn"
 829  *      is the node we want to try and remove.
 830  */
 831
 832 static struct fib6_node * fib6_repair_tree(struct fib6_node *fn)
 833 {
 834         int children;
 835         int nstate;
 836         struct fib6_node *child, *pn;
 837         struct fib6_walker_t *w;
 838         int iter = 0;
 839
 840         for (;;) {
 841                 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
 842                 iter++;
 843
 844                 BUG_TRAP(!(fn->fn_flags&RTN_RTINFO));
 845                 BUG_TRAP(!(fn->fn_flags&RTN_TL_ROOT));
 846                 BUG_TRAP(fn->leaf==NULL);
 847
 848                 children = 0;
 849                 child = NULL;
 850                 if (fn->right) child = fn->right, children |= 1;
 851                 if (fn->left) child = fn->left, children |= 2;
 852
 853                 if (children == 3 || SUBTREE(fn)
 854 #ifdef CONFIG_IPV6_SUBTREES
 855                     /* Subtree root (i.e. fn) may have one child */
 856                     || (children && fn->fn_flags&RTN_ROOT)
 857 #endif
 858                     ) {
 859                         fn->leaf = fib6_find_prefix(fn);
 860 #if RT6_DEBUG >= 2
 861                         if (fn->leaf==NULL) {
 862                                 BUG_TRAP(fn->leaf);
 863                                 fn->leaf = &ip6_null_entry;
 864                         }
 865 #endif
 866                         atomic_inc(&fn->leaf->rt6i_ref);
 867                         return fn->parent;
 868                 }
 869
 870                 pn = fn->parent;
 871 #ifdef CONFIG_IPV6_SUBTREES
 872                 if (SUBTREE(pn) == fn) {
 873                         BUG_TRAP(fn->fn_flags&RTN_ROOT);
 874                         SUBTREE(pn) = NULL;
 875                         nstate = FWS_L;
 876                 } else {
 877                         BUG_TRAP(!(fn->fn_flags&RTN_ROOT));
 878 #endif
 879                         if (pn->right == fn) pn->right = child;
 880                         else if (pn->left == fn) pn->left = child;
 881 #if RT6_DEBUG >= 2
 882                         else BUG_TRAP(0);
 883 #endif
 884                         if (child)
 885                                 child->parent = pn;
 886                         nstate = FWS_R;
 887 #ifdef CONFIG_IPV6_SUBTREES
 888                 }
 889 #endif
 890
 891                 read_lock(&fib6_walker_lock);
 892                 FOR_WALKERS(w) {
 893                         if (child == NULL) {
 894                                 if (w->root == fn) {
 895                                         w->root = w->node = NULL;
 896                                         RT6_TRACE("W %p adjusted by delroot 1\n", w);
 897                                 } else if (w->node == fn) {
 898                                         RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
 899                                         w->node = pn;
 900                                         w->state = nstate;
 901                                 }
 902                         } else {
 903                                 if (w->root == fn) {
 904                                         w->root = child;
 905                                         RT6_TRACE("W %p adjusted by delroot 2\n", w);
 906                                 }
 907                                 if (w->node == fn) {
 908                                         w->node = child;
 909                                         if (children&2) {
 910                                                 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
 911                                                 w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
 912                                         } else {
 913                                                 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
 914                                                 w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
 915                                         }
 916                                 }
 917                         }
 918                 }
 919                 read_unlock(&fib6_walker_lock);
 920
 921                 node_free(fn);
 922                 if (pn->fn_flags&RTN_RTINFO || SUBTREE(pn))
 923                         return pn;
 924
 925                 rt6_release(pn->leaf);
 926                 pn->leaf = NULL;
 927                 fn = pn;
 928         }
 929 }
 930
 931 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
 932     struct nlmsghdr *nlh, void *_rtattr, struct netlink_skb_parms *req)
 933 {
 934         struct fib6_walker_t *w;
 935         struct rt6_info *rt = *rtp;
 936
 937         RT6_TRACE("fib6_del_route\n");
 938
 939         /* Unlink it */
 940         *rtp = rt->u.next;
 941         rt->rt6i_node = NULL;
 942         rt6_stats.fib_rt_entries--;
 943         rt6_stats.fib_discarded_routes++;
 944
 945         /* Adjust walkers */
 946         read_lock(&fib6_walker_lock);
 947         FOR_WALKERS(w) {
 948                 if (w->state == FWS_C && w->leaf == rt) {
 949                         RT6_TRACE("walker %p adjusted by delroute\n", w);
 950                         w->leaf = rt->u.next;
 951                         if (w->leaf == NULL)
 952                                 w->state = FWS_U;
 953                 }
 954         }
 955         read_unlock(&fib6_walker_lock);
 956
 957         rt->u.next = NULL;
 958
 959         if (fn->leaf == NULL && fn->fn_flags&RTN_TL_ROOT)
 960                 fn->leaf = &ip6_null_entry;
 961
 962         /* If it was last route, expunge its radix tree node */
 963         if (fn->leaf == NULL) {
 964                 fn->fn_flags &= ~RTN_RTINFO;
 965                 rt6_stats.fib_route_nodes--;
 966                 fn = fib6_repair_tree(fn);
 967         }
 968
 969         if (atomic_read(&rt->rt6i_ref) != 1) {
 970                 /* This route is used as dummy address holder in some split
 971                  * nodes. It is not leaked, but it still holds other resources,
 972                  * which must be released in time. So, scan ascendant nodes
 973                  * and replace dummy references to this route with references
 974                  * to still alive ones.
 975                  */
 976                 while (fn) {
 977                         if (!(fn->fn_flags&RTN_RTINFO) && fn->leaf == rt) {
 978                                 fn->leaf = fib6_find_prefix(fn);
 979                                 atomic_inc(&fn->leaf->rt6i_ref);
 980                                 rt6_release(rt);
 981                         }
 982                         fn = fn->parent;
 983                 }
 984                 /* No more references are possible at this point. */
 985                 if (atomic_read(&rt->rt6i_ref) != 1) BUG();
 986         }
 987
 988         inet6_rt_notify(RTM_DELROUTE, rt, nlh, req);
 989         rt6_release(rt);
 990 }
 991
 992 int fib6_del(struct rt6_info *rt, struct nlmsghdr *nlh, void *_rtattr, struct netlink_skb_parms *req)
 993 {
 994         struct fib6_node *fn = rt->rt6i_node;
 995         struct rt6_info **rtp;
 996
 997 #if RT6_DEBUG >= 2
 998         if (rt->u.dst.obsolete>0) {
 999                 BUG_TRAP(fn==NULL);
1000                 return -ENOENT;
1001         }
1002 #endif
1003         if (fn == NULL || rt == &ip6_null_entry)
1004                 return -ENOENT;
1005
1006         BUG_TRAP(fn->fn_flags&RTN_RTINFO);
1007
1008         if (!(rt->rt6i_flags&RTF_CACHE))
1009                 fib6_prune_clones(fn, rt);
1010
1011         /*
1012          *      Walk the leaf entries looking for ourself
1013          */
1014
1015         for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.next) {
1016                 if (*rtp == rt) {
1017                         fib6_del_route(fn, rtp, nlh, _rtattr, req);
1018                         return 0;
1019                 }
1020         }
1021         return -ENOENT;
1022 }
1023
1024 /*
1025  *      Tree traversal function.
1026  *
1027  *      Certainly, it is not interrupt safe.
1028  *      However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1029  *      It means, that we can modify tree during walking
1030  *      and use this function for garbage collection, clone pruning,
1031  *      cleaning tree when a device goes down etc. etc.
1032  *
1033  *      It guarantees that every node will be traversed,
1034  *      and that it will be traversed only once.
1035  *
1036  *      Callback function w->func may return:
1037  *      0 -> continue walking.
1038  *      positive value -> walking is suspended (used by tree dumps,
1039  *      and probably by gc, if it will be split to several slices)
1040  *      negative value -> terminate walking.
1041  *
1042  *      The function itself returns:
1043  *      0   -> walk is complete.
1044  *      >0  -> walk is incomplete (i.e. suspended)
1045  *      <0  -> walk is terminated by an error.
1046  */
1047
1048 int fib6_walk_continue(struct fib6_walker_t *w)
1049 {
1050         struct fib6_node *fn, *pn;
1051
1052         for (;;) {
1053                 fn = w->node;
1054                 if (fn == NULL)
1055                         return 0;
1056
1057                 if (w->prune && fn != w->root &&
1058                     fn->fn_flags&RTN_RTINFO && w->state < FWS_C) {
1059                         w->state = FWS_C;
1060                         w->leaf = fn->leaf;
1061                 }
1062                 switch (w->state) {
1063 #ifdef CONFIG_IPV6_SUBTREES
1064                 case FWS_S:
1065                         if (SUBTREE(fn)) {
1066                                 w->node = SUBTREE(fn);
1067                                 continue;
1068                         }
1069                         w->state = FWS_L;
1070 #endif
1071                 case FWS_L:
1072                         if (fn->left) {
1073                                 w->node = fn->left;
1074                                 w->state = FWS_INIT;
1075                                 continue;
1076                         }
1077                         w->state = FWS_R;
1078                 case FWS_R:
1079                         if (fn->right) {
1080                                 w->node = fn->right;
1081                                 w->state = FWS_INIT;
1082                                 continue;
1083                         }
1084                         w->state = FWS_C;
1085                         w->leaf = fn->leaf;
1086                 case FWS_C:
1087                         if (w->leaf && fn->fn_flags&RTN_RTINFO) {
1088                                 int err = w->func(w);
1089                                 if (err)
1090                                         return err;
1091                                 continue;
1092                         }
1093                         w->state = FWS_U;
1094                 case FWS_U:
1095                         if (fn == w->root)
1096                                 return 0;
1097                         pn = fn->parent;
1098                         w->node = pn;
1099 #ifdef CONFIG_IPV6_SUBTREES
1100                         if (SUBTREE(pn) == fn) {
1101                                 BUG_TRAP(fn->fn_flags&RTN_ROOT);
1102                                 w->state = FWS_L;
1103                                 continue;
1104                         }
1105 #endif
1106                         if (pn->left == fn) {
1107                                 w->state = FWS_R;
1108                                 continue;
1109                         }
1110                         if (pn->right == fn) {
1111                                 w->state = FWS_C;
1112                                 w->leaf = w->node->leaf;
1113                                 continue;
1114                         }
1115 #if RT6_DEBUG >= 2
1116                         BUG_TRAP(0);
1117 #endif
1118                 }
1119         }
1120 }
1121
1122 int fib6_walk(struct fib6_walker_t *w)
1123 {
1124         int res;
1125
1126         w->state = FWS_INIT;
1127         w->node = w->root;
1128
1129         fib6_walker_link(w);
1130         res = fib6_walk_continue(w);
1131         if (res <= 0)
1132                 fib6_walker_unlink(w);
1133         return res;
1134 }
1135
1136 static int fib6_clean_node(struct fib6_walker_t *w)
1137 {
1138         int res;
1139         struct rt6_info *rt;
1140         struct fib6_cleaner_t *c = (struct fib6_cleaner_t*)w;
1141
1142         for (rt = w->leaf; rt; rt = rt->u.next) {
1143                 res = c->func(rt, c->arg);
1144                 if (res < 0) {
1145                         w->leaf = rt;
1146                         res = fib6_del(rt, NULL, NULL, NULL);
1147                         if (res) {
1148 #if RT6_DEBUG >= 2
1149                                 printk(KERN_DEBUG "fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt, rt->rt6i_node, res);
1150 #endif
1151                                 continue;
1152                         }
1153                         return 0;
1154                 }
1155                 BUG_TRAP(res==0);
1156         }
1157         w->leaf = rt;
1158         return 0;
1159 }
1160
1161 /*
1162  *      Convenient frontend to tree walker.
1163  *
1164  *      func is called on each route.
1165  *              It may return -1 -> delete this route.
1166  *                            0  -> continue walking
1167  *
1168  *      prune==1 -> only immediate children of node (certainly,
1169  *      ignoring pure split nodes) will be scanned.
1170  */
1171
1172 static void fib6_clean_tree(struct fib6_node *root,
1173                             int (*func)(struct rt6_info *, void *arg),
1174                             int prune, void *arg)
1175 {
1176         struct fib6_cleaner_t c;
1177
1178         c.w.root = root;
1179         c.w.func = fib6_clean_node;
1180         c.w.prune = prune;
1181         c.func = func;
1182         c.arg = arg;
1183
1184         fib6_walk(&c.w);
1185 }
1186
1187 void fib6_clean_all(int (*func)(struct rt6_info *, void *arg),
1188                     int prune, void *arg)
1189 {
1190         int i;
1191         struct fib6_table *table;
1192
1193         for (i = FIB6_TABLE_MIN; i <= FIB6_TABLE_MAX; i++) {
1194                 table = fib6_get_table(i);
1195                 if (table != NULL) {
1196                         write_lock_bh(&table->tb6_lock);
1197                         fib6_clean_tree(&table->tb6_root, func, prune, arg);
1198                         write_unlock_bh(&table->tb6_lock);
1199                 }
1200         }
1201 }
1202
1203 static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1204 {
1205         if (rt->rt6i_flags & RTF_CACHE) {
1206                 RT6_TRACE("pruning clone %p\n", rt);
1207                 return -1;
1208         }
1209
1210         return 0;
1211 }
1212
1213 static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt)
1214 {
1215         fib6_clean_tree(fn, fib6_prune_clone, 1, rt);
1216 }
1217
1218 /*
1219  *      Garbage collection
1220  */
1221
1222 static struct fib6_gc_args
1223 {
1224         int                     timeout;
1225         int                     more;
1226 } gc_args;
1227
1228 static int fib6_age(struct rt6_info *rt, void *arg)
1229 {
1230         unsigned long now = jiffies;
1231
1232         /*
1233          *      check addrconf expiration here.
1234          *      Routes are expired even if they are in use.
1235          *
1236          *      Also age clones. Note, that clones are aged out
1237          *      only if they are not in use now.
1238          */
1239
1240         if (rt->rt6i_flags&RTF_EXPIRES && rt->rt6i_expires) {
1241                 if (time_after(now, rt->rt6i_expires)) {
1242                         RT6_TRACE("expiring %p\n", rt);
1243                         return -1;
1244                 }
1245                 gc_args.more++;
1246         } else if (rt->rt6i_flags & RTF_CACHE) {
1247                 if (atomic_read(&rt->u.dst.__refcnt) == 0 &&
1248                     time_after_eq(now, rt->u.dst.lastuse + gc_args.timeout)) {
1249                         RT6_TRACE("aging clone %p\n", rt);
1250                         return -1;
1251                 } else if ((rt->rt6i_flags & RTF_GATEWAY) &&
1252                            (!(rt->rt6i_nexthop->flags & NTF_ROUTER))) {
1253                         RT6_TRACE("purging route %p via non-router but gateway\n",
1254                                   rt);
1255                         return -1;
1256                 }
1257                 gc_args.more++;
1258         }
1259
1260         return 0;
1261 }
1262
1263 static DEFINE_SPINLOCK(fib6_gc_lock);
1264
1265 void fib6_run_gc(unsigned long dummy)
1266 {
1267         if (dummy != ~0UL) {
1268                 spin_lock_bh(&fib6_gc_lock);
1269                 gc_args.timeout = dummy ? (int)dummy : ip6_rt_gc_interval;
1270         } else {
1271                 local_bh_disable();
1272                 if (!spin_trylock(&fib6_gc_lock)) {
1273                         mod_timer(&ip6_fib_timer, jiffies + HZ);
1274                         local_bh_enable();
1275                         return;
1276                 }
1277                 gc_args.timeout = ip6_rt_gc_interval;
1278         }
1279         gc_args.more = 0;
1280
1281         ndisc_dst_gc(&gc_args.more);
1282         fib6_clean_all(fib6_age, 0, NULL);
1283
1284         if (gc_args.more)
1285                 mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
1286         else {
1287                 del_timer(&ip6_fib_timer);
1288                 ip6_fib_timer.expires = 0;
1289         }
1290         spin_unlock_bh(&fib6_gc_lock);
1291 }
1292
1293 void __init fib6_init(void)
1294 {
1295         fib6_node_kmem = kmem_cache_create("fib6_nodes",
1296                                            sizeof(struct fib6_node),
1297                                            0, SLAB_HWCACHE_ALIGN,
1298                                            NULL, NULL);
1299         if (!fib6_node_kmem)
1300                 panic("cannot create fib6_nodes cache");
1301
1302         fib6_tables_init();
1303 }
1304
1305 void fib6_gc_cleanup(void)
1306 {
1307         del_timer(&ip6_fib_timer);
1308         kmem_cache_destroy(fib6_node_kmem);
1309 }