开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 查看源码
ip6_fib.c
资源名称：linux-2.4.20.tar.gz　[点击查看]
上传用户：jlfgdled
上传日期：2013-04-10
资源大小：33168k
文件大小：24k
源码类别：

Linux/Unix编程

开发平台：

Unix_Linux

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.  */
  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/config.h>
  23. #include <linux/errno.h>
  24. #include <linux/types.h>
  25. #include <linux/net.h>
  26. #include <linux/route.h>
  27. #include <linux/netdevice.h>
  28. #include <linux/in6.h>
  29. #include <linux/init.h>
  31. #ifdef  CONFIG_PROC_FS
  32. #include <linux/proc_fs.h>
  33. #endif
  35. #include <net/ipv6.h>
  36. #include <net/ndisc.h>
  37. #include <net/addrconf.h>
  39. #include <net/ip6_fib.h>
  40. #include <net/ip6_route.h>
  42. #define RT6_DEBUG 2
  43. #undef CONFIG_IPV6_SUBTREES
  45. #if RT6_DEBUG >= 3
  46. #define RT6_TRACE(x...) printk(KERN_DEBUG x)
  47. #else
  48. #define RT6_TRACE(x...) do { ; } while (0)
  49. #endif
  51. struct rt6_statistics rt6_stats;
  53. static kmem_cache_t * fib6_node_kmem;
  55. enum fib_walk_state_t
  56. {
  57. #ifdef CONFIG_IPV6_SUBTREES
  58. FWS_S,
  59. #endif
  60. FWS_L,
  61. FWS_R,
  62. FWS_C,
  63. FWS_U
  64. };
  66. struct fib6_cleaner_t
  67. {
  68. struct fib6_walker_t w;
  69. int (*func)(struct rt6_info *, void *arg);
  70. void *arg;
  71. };
  73. rwlock_t fib6_walker_lock = RW_LOCK_UNLOCKED;
  76. #ifdef CONFIG_IPV6_SUBTREES
  77. #define FWS_INIT FWS_S
  78. #define SUBTREE(fn) ((fn)->subtree)
  79. #else
  80. #define FWS_INIT FWS_L
  81. #define SUBTREE(fn) NULL
  82. #endif
  84. static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt);
  85. static struct fib6_node * fib6_repair_tree(struct fib6_node *fn);
  87. /*
  88.  * A routing update causes an increase of the serial number on the
  89.  * afected subtree. This allows for cached routes to be asynchronously
  90.  * tested when modifications are made to the destination cache as a
  91.  * result of redirects, path MTU changes, etc.
  92.  */
  94. static __u32 rt_sernum = 0;
  96. static struct timer_list ip6_fib_timer = { function: fib6_run_gc };
  98. static struct fib6_walker_t fib6_walker_list = {
  99. &fib6_walker_list, &fib6_walker_list, 
  100. };
  102. #define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)
  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. }
  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.  */
  119. /*
  120.  * compare "prefix length" bits of an address
  121.  */
  123. static __inline__ int addr_match(void *token1, void *token2, int prefixlen)
  124. {
  125. __u32 *a1 = token1;
  126. __u32 *a2 = token2;
  127. int pdw;
  128. int pbi;
  130. pdw = prefixlen >> 5;   /* num of whole __u32 in prefix */
  131. pbi = prefixlen &  0x1f;  /* num of bits in incomplete u32 in prefix */
  133. if (pdw)
  134. if (memcmp(a1, a2, pdw << 2))
  135. return 0;
  137. if (pbi) {
  138. __u32 mask;
  140. mask = htonl((0xffffffff) << (32 - pbi));
  142. if ((a1[pdw] ^ a2[pdw]) & mask)
  143. return 0;
  144. }
  146. return 1;
  147. }
  149. /*
  150.  * test bit
  151.  */
  153. static __inline__ int addr_bit_set(void *token, int fn_bit)
  154. {
  155. __u32 *addr = token;
  157. return htonl(1 << ((~fn_bit)&0x1F)) & addr[fn_bit>>5];
  158. }
  160. /*
  161.  * find the first different bit between two addresses
  162.  * length of address must be a multiple of 32bits
  163.  */
  165. static __inline__ int addr_diff(void *token1, void *token2, int addrlen)
  166. {
  167. __u32 *a1 = token1;
  168. __u32 *a2 = token2;
  169. int i;
  171. addrlen >>= 2;
  173. for (i = 0; i < addrlen; i++) {
  174. __u32 xb;
  176. xb = a1[i] ^ a2[i];
  178. if (xb) {
  179. int j = 31;
  181. xb = ntohl(xb);
  183. while ((xb & (1 << j)) == 0)
  184. j--;
  186. return (i * 32 + 31 - j);
  187. }
  188. }
  190. /*
  191.  * we should *never* get to this point since that 
  192.  * would mean the addrs are equal
  193.  *
  194.  * However, we do get to it 8) And exacly, when
  195.  * addresses are equal 8)
  196.  *
  197.  * ip route add 1111::/128 via ...
  198.  * ip route add 1111::/64 via ...
  199.  * and we are here.
  200.  *
  201.  * Ideally, this function should stop comparison
  202.  * at prefix length. It does not, but it is still OK,
  203.  * if returned value is greater than prefix length.
  204.  * --ANK (980803)
  205.  */
  207. return addrlen<<5;
  208. }
  210. static __inline__ struct fib6_node * node_alloc(void)
  211. {
  212. struct fib6_node *fn;
  214. if ((fn = kmem_cache_alloc(fib6_node_kmem, SLAB_ATOMIC)) != NULL)
  215. memset(fn, 0, sizeof(struct fib6_node));
  217. return fn;
  218. }
  220. static __inline__ void node_free(struct fib6_node * fn)
  221. {
  222. kmem_cache_free(fib6_node_kmem, fn);
  223. }
  225. static __inline__ void rt6_release(struct rt6_info *rt)
  226. {
  227. if (atomic_dec_and_test(&rt->rt6i_ref))
  228. dst_free(&rt->u.dst);
  229. }
  232. /*
  233.  * Routing Table
  234.  *
  235.  * return the apropriate node for a routing tree "add" operation
  236.  * by either creating and inserting or by returning an existing
  237.  * node.
  238.  */
  240. static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
  241.      int addrlen, int plen,
  242.      int offset)
  243. {
  244. struct fib6_node *fn, *in, *ln;
  245. struct fib6_node *pn = NULL;
  246. struct rt6key *key;
  247. int bit;
  248.         int dir = 0;
  249. __u32 sernum = fib6_new_sernum();
  251. RT6_TRACE("fib6_add_1n");
  253. /* insert node in tree */
  255. fn = root;
  257. do {
  258. key = (struct rt6key *)((u8 *)fn->leaf + offset);
  260. /*
  261.  * Prefix match
  262.  */
  263. if (plen < fn->fn_bit ||
  264.     !addr_match(&key->addr, addr, fn->fn_bit))
  265. goto insert_above;
  267. /*
  268.  * Exact match ?
  269.  */
  270.  
  271. if (plen == fn->fn_bit) {
  272. /* clean up an intermediate node */
  273. if ((fn->fn_flags & RTN_RTINFO) == 0) {
  274. rt6_release(fn->leaf);
  275. fn->leaf = NULL;
  276. }
  278. fn->fn_sernum = sernum;
  280. return fn;
  281. }
  283. /*
  284.  * We have more bits to go
  285.  */
  286.  
  287. /* Try to walk down on tree. */
  288. fn->fn_sernum = sernum;
  289. dir = addr_bit_set(addr, fn->fn_bit);
  290. pn = fn;
  291. fn = dir ? fn->right: fn->left;
  292. } while (fn);
  294. /*
  295.  * We walked to the bottom of tree.
  296.  * Create new leaf node without children.
  297.  */
  299. ln = node_alloc();
  301. if (ln == NULL)
  302. return NULL;
  303. ln->fn_bit = plen;
  305. ln->parent = pn;
  306. ln->fn_sernum = sernum;
  308. if (dir)
  309. pn->right = ln;
  310. else
  311. pn->left  = ln;
  313. return ln;
  316. insert_above:
  317. /*
  318.  * split since we don't have a common prefix anymore or 
  319.  * we have a less significant route.
  320.  * we've to insert an intermediate node on the list
  321.  * this new node will point to the one we need to create
  322.  * and the current
  323.  */
  325. pn = fn->parent;
  327. /* find 1st bit in difference between the 2 addrs.
  329.    See comment in addr_diff: bit may be an invalid value,
  330.    but if it is >= plen, the value is ignored in any case.
  331.  */
  333. bit = addr_diff(addr, &key->addr, addrlen);
  335. /* 
  336.  * (intermediate)[in]
  337.  *           /    
  338.  * (new leaf node)[ln] (old node)[fn]
  339.  */
  340. if (plen > bit) {
  341. in = node_alloc();
  342. ln = node_alloc();
  344. if (in == NULL || ln == NULL) {
  345. if (in)
  346. node_free(in);
  347. if (ln)
  348. node_free(ln);
  349. return NULL;
  350. }
  352. /* 
  353.  * new intermediate node. 
  354.  * RTN_RTINFO will
  355.  * be off since that an address that chooses one of
  356.  * the branches would not match less specific routes
  357.  * in the other branch
  358.  */
  360. in->fn_bit = bit;
  362. in->parent = pn;
  363. in->leaf = fn->leaf;
  364. atomic_inc(&in->leaf->rt6i_ref);
  366. in->fn_sernum = sernum;
  368. /* update parent pointer */
  369. if (dir)
  370. pn->right = in;
  371. else
  372. pn->left  = in;
  374. ln->fn_bit = plen;
  376. ln->parent = in;
  377. fn->parent = in;
  379. ln->fn_sernum = sernum;
  381. if (addr_bit_set(addr, bit)) {
  382. in->right = ln;
  383. in->left  = fn;
  384. } else {
  385. in->left  = ln;
  386. in->right = fn;
  387. }
  388. } else { /* plen <= bit */
  390. /* 
  391.  * (new leaf node)[ln]
  392.  *           /    
  393.  *      (old node)[fn] NULL
  394.  */
  396. ln = node_alloc();
  398. if (ln == NULL)
  399. return NULL;
  401. ln->fn_bit = plen;
  403. ln->parent = pn;
  405. ln->fn_sernum = sernum;
  407. if (dir)
  408. pn->right = ln;
  409. else
  410. pn->left  = ln;
  412. if (addr_bit_set(&key->addr, plen))
  413. ln->right = fn;
  414. else
  415. ln->left  = fn;
  417. fn->parent = ln;
  418. }
  419. return ln;
  420. }
  422. /*
  423.  * Insert routing information in a node.
  424.  */
  426. static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt)
  427. {
  428. struct rt6_info *iter = NULL;
  429. struct rt6_info **ins;
  431. ins = &fn->leaf;
  433. if (fn->fn_flags&RTN_TL_ROOT &&
  434.     fn->leaf == &ip6_null_entry &&
  435.     !(rt->rt6i_flags & (RTF_DEFAULT | RTF_ADDRCONF | RTF_ALLONLINK)) ){
  436. /*
  437.  * The top fib of ip6 routing table includes ip6_null_entry.
  438.  */
  439. fn->leaf = rt;
  440. rt->u.next = NULL;
  441. goto out;
  442. }
  444. for (iter = fn->leaf; iter; iter=iter->u.next) {
  445. /*
  446.  * Search for duplicates
  447.  */
  449. if (iter->rt6i_metric == rt->rt6i_metric) {
  450. /*
  451.  * Same priority level
  452.  */
  454. if ((iter->rt6i_dev == rt->rt6i_dev) &&
  455.     (iter->rt6i_flowr == rt->rt6i_flowr) &&
  456.     (ipv6_addr_cmp(&iter->rt6i_gateway,
  457.    &rt->rt6i_gateway) == 0)) {
  458. if (!(iter->rt6i_flags&RTF_EXPIRES))
  459. return -EEXIST;
  460. iter->rt6i_expires = rt->rt6i_expires;
  461. if (!(rt->rt6i_flags&RTF_EXPIRES)) {
  462. iter->rt6i_flags &= ~RTF_EXPIRES;
  463. iter->rt6i_expires = 0;
  464. }
  465. return -EEXIST;
  466. }
  467. }
  469. if (iter->rt6i_metric > rt->rt6i_metric)
  470. break;
  472. ins = &iter->u.next;
  473. }
  475. /*
  476.  * insert node
  477.  */
  479. out:
  480. rt->u.next = iter;
  481. *ins = rt;
  482. rt->rt6i_node = fn;
  483. atomic_inc(&rt->rt6i_ref);
  484. inet6_rt_notify(RTM_NEWROUTE, rt);
  485. rt6_stats.fib_rt_entries++;
  487. if ((fn->fn_flags & RTN_RTINFO) == 0) {
  488. rt6_stats.fib_route_nodes++;
  489. fn->fn_flags |= RTN_RTINFO;
  490. }
  492. return 0;
  493. }
  495. static __inline__ void fib6_start_gc(struct rt6_info *rt)
  496. {
  497. if (ip6_fib_timer.expires == 0 &&
  498.     (rt->rt6i_flags & (RTF_EXPIRES|RTF_CACHE)))
  499. mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
  500. }
  502. /*
  503.  * Add routing information to the routing tree.
  504.  * <destination addr>/<source addr>
  505.  * with source addr info in sub-trees
  506.  */
  508. int fib6_add(struct fib6_node *root, struct rt6_info *rt)
  509. {
  510. struct fib6_node *fn;
  511. int err = -ENOMEM;
  513. fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
  514. rt->rt6i_dst.plen, (u8*) &rt->rt6i_dst - (u8*) rt);
  516. if (fn == NULL)
  517. goto out;
  519. #ifdef CONFIG_IPV6_SUBTREES
  520. if (rt->rt6i_src.plen) {
  521. struct fib6_node *sn;
  523. if (fn->subtree == NULL) {
  524. struct fib6_node *sfn;
  526. /*
  527.  * Create subtree.
  528.  *
  529.  * fn[main tree]
  530.  * |
  531.  * sfn[subtree root]
  532.  *    
  533.  *     sn[new leaf node]
  534.  */
  536. /* Create subtree root node */
  537. sfn = node_alloc();
  538. if (sfn == NULL)
  539. goto st_failure;
  541. sfn->leaf = &ip6_null_entry;
  542. atomic_inc(&ip6_null_entry.rt6i_ref);
  543. sfn->fn_flags = RTN_ROOT;
  544. sfn->fn_sernum = fib6_new_sernum();
  546. /* Now add the first leaf node to new subtree */
  548. sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
  549. sizeof(struct in6_addr), rt->rt6i_src.plen,
  550. (u8*) &rt->rt6i_src - (u8*) rt);
  552. if (sn == NULL) {
  553. /* If it is failed, discard just allocated
  554.    root, and then (in st_failure) stale node
  555.    in main tree.
  556.  */
  557. node_free(sfn);
  558. goto st_failure;
  559. }
  561. /* Now link new subtree to main tree */
  562. sfn->parent = fn;
  563. fn->subtree = sfn;
  564. if (fn->leaf == NULL) {
  565. fn->leaf = rt;
  566. atomic_inc(&rt->rt6i_ref);
  567. }
  568. } else {
  569. sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
  570. sizeof(struct in6_addr), rt->rt6i_src.plen,
  571. (u8*) &rt->rt6i_src - (u8*) rt);
  573. if (sn == NULL)
  574. goto st_failure;
  575. }
  577. fn = sn;
  578. }
  579. #endif
  581. err = fib6_add_rt2node(fn, rt);
  583. if (err == 0) {
  584. fib6_start_gc(rt);
  585. if (!(rt->rt6i_flags&RTF_CACHE))
  586. fib6_prune_clones(fn, rt);
  587. }
  589. out:
  590. if (err)
  591. dst_free(&rt->u.dst);
  592. return err;
  594. #ifdef CONFIG_IPV6_SUBTREES
  595. /* Subtree creation failed, probably main tree node
  596.    is orphan. If it is, shot it.
  597.  */
  598. st_failure:
  599. if (fn && !(fn->fn_flags&RTN_RTINFO|RTN_ROOT))
  600. fib_repair_tree(fn);
  601. dst_free(&rt->u.dst);
  602. return err;
  603. #endif
  604. }
  606. /*
  607.  * Routing tree lookup
  608.  *
  609.  */
  611. struct lookup_args {
  612. int offset; /* key offset on rt6_info */
  613. struct in6_addr *addr; /* search key */
  614. };
  616. static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
  617. struct lookup_args *args)
  618. {
  619. struct fib6_node *fn;
  620. int dir;
  622. /*
  623.  * Descend on a tree
  624.  */
  626. fn = root;
  628. for (;;) {
  629. struct fib6_node *next;
  631. dir = addr_bit_set(args->addr, fn->fn_bit);
  633. next = dir ? fn->right : fn->left;
  635. if (next) {
  636. fn = next;
  637. continue;
  638. }
  640. break;
  641. }
  643. while ((fn->fn_flags & RTN_ROOT) == 0) {
  644. #ifdef CONFIG_IPV6_SUBTREES
  645. if (fn->subtree) {
  646. struct fib6_node *st;
  647. struct lookup_args *narg;
  649. narg = args + 1;
  651. if (narg->addr) {
  652. st = fib6_lookup_1(fn->subtree, narg);
  654. if (st && !(st->fn_flags & RTN_ROOT))
  655. return st;
  656. }
  657. }
  658. #endif
  660. if (fn->fn_flags & RTN_RTINFO) {
  661. struct rt6key *key;
  663. key = (struct rt6key *) ((u8 *) fn->leaf +
  664.  args->offset);
  666. if (addr_match(&key->addr, args->addr, key->plen))
  667. return fn;
  668. }
  670. fn = fn->parent;
  671. }
  673. return NULL;
  674. }
  676. struct fib6_node * fib6_lookup(struct fib6_node *root, struct in6_addr *daddr,
  677.        struct in6_addr *saddr)
  678. {
  679. struct lookup_args args[2];
  680. struct rt6_info *rt = NULL;
  681. struct fib6_node *fn;
  683. args[0].offset = (u8*) &rt->rt6i_dst - (u8*) rt;
  684. args[0].addr = daddr;
  686. #ifdef CONFIG_IPV6_SUBTREES
  687. args[1].offset = (u8*) &rt->rt6i_src - (u8*) rt;
  688. args[1].addr = saddr;
  689. #endif
  691. fn = fib6_lookup_1(root, args);
  693. if (fn == NULL || fn->fn_flags & RTN_TL_ROOT)
  694. fn = root;
  696. return fn;
  697. }
  699. /*
  700.  * Get node with sepciafied destination prefix (and source prefix,
  701.  * if subtrees are used)
  702.  */
  705. static struct fib6_node * fib6_locate_1(struct fib6_node *root,
  706. struct in6_addr *addr,
  707. int plen, int offset)
  708. {
  709. struct fib6_node *fn;
  711. for (fn = root; fn ; ) {
  712. struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
  714. /*
  715.  * Prefix match
  716.  */
  717. if (plen < fn->fn_bit ||
  718.     !addr_match(&key->addr, addr, fn->fn_bit))
  719. return NULL;
  721. if (plen == fn->fn_bit)
  722. return fn;
  724. /*
  725.  * We have more bits to go
  726.  */
  727. if (addr_bit_set(addr, fn->fn_bit))
  728. fn = fn->right;
  729. else
  730. fn = fn->left;
  731. }
  732. return NULL;
  733. }
  735. struct fib6_node * fib6_locate(struct fib6_node *root,
  736.        struct in6_addr *daddr, int dst_len,
  737.        struct in6_addr *saddr, int src_len)
  738. {
  739. struct rt6_info *rt = NULL;
  740. struct fib6_node *fn;
  742. fn = fib6_locate_1(root, daddr, dst_len,
  743.    (u8*) &rt->rt6i_dst - (u8*) rt);
  745. #ifdef CONFIG_IPV6_SUBTREES
  746. if (src_len) {
  747. BUG_TRAP(saddr!=NULL);
  748. if (fn == NULL)
  749. fn = fn->subtree;
  750. if (fn)
  751. fn = fib6_locate_1(fn, saddr, src_len,
  752.    (u8*) &rt->rt6i_src - (u8*) rt);
  753. }
  754. #endif
  756. if (fn && fn->fn_flags&RTN_RTINFO)
  757. return fn;
  759. return NULL;
  760. }
  763. /*
  764.  * Deletion
  765.  *
  766.  */
  768. static struct rt6_info * fib6_find_prefix(struct fib6_node *fn)
  769. {
  770. if (fn->fn_flags&RTN_ROOT)
  771. return &ip6_null_entry;
  773. while(fn) {
  774. if(fn->left)
  775. return fn->left->leaf;
  777. if(fn->right)
  778. return fn->right->leaf;
  780. fn = SUBTREE(fn);
  781. }
  782. return NULL;
  783. }
  785. /*
  786.  * Called to trim the tree of intermediate nodes when possible. "fn"
  787.  * is the node we want to try and remove.
  788.  */
  790. static struct fib6_node * fib6_repair_tree(struct fib6_node *fn)
  791. {
  792. int children;
  793. int nstate;
  794. struct fib6_node *child, *pn;
  795. struct fib6_walker_t *w;
  796. int iter = 0;
  798. for (;;) {
  799. RT6_TRACE("fixing tree: plen=%d iter=%dn", fn->fn_bit, iter);
  800. iter++;
  802. BUG_TRAP(!(fn->fn_flags&RTN_RTINFO));
  803. BUG_TRAP(!(fn->fn_flags&RTN_TL_ROOT));
  804. BUG_TRAP(fn->leaf==NULL);
  806. children = 0;
  807. child = NULL;
  808. if (fn->right) child = fn->right, children |= 1;
  809. if (fn->left) child = fn->left, children |= 2;
  811. if (children == 3 || SUBTREE(fn) 
  812. #ifdef CONFIG_IPV6_SUBTREES
  813.     /* Subtree root (i.e. fn) may have one child */
  814.     || (children && fn->fn_flags&RTN_ROOT)
  815. #endif
  816.     ) {
  817. fn->leaf = fib6_find_prefix(fn);
  818. #if RT6_DEBUG >= 2
  819. if (fn->leaf==NULL) {
  820. BUG_TRAP(fn->leaf);
  821. fn->leaf = &ip6_null_entry;
  822. }
  823. #endif
  824. atomic_inc(&fn->leaf->rt6i_ref);
  825. return fn->parent;
  826. }
  828. pn = fn->parent;
  829. #ifdef CONFIG_IPV6_SUBTREES
  830. if (SUBTREE(pn) == fn) {
  831. BUG_TRAP(fn->fn_flags&RTN_ROOT);
  832. SUBTREE(pn) = NULL;
  833. nstate = FWS_L;
  834. } else {
  835. BUG_TRAP(!(fn->fn_flags&RTN_ROOT));
  836. #endif
  837. if (pn->right == fn) pn->right = child;
  838. else if (pn->left == fn) pn->left = child;
  839. #if RT6_DEBUG >= 2
  840. else BUG_TRAP(0);
  841. #endif
  842. if (child)
  843. child->parent = pn;
  844. nstate = FWS_R;
  845. #ifdef CONFIG_IPV6_SUBTREES
  846. }
  847. #endif
  849. read_lock(&fib6_walker_lock);
  850. FOR_WALKERS(w) {
  851. if (child == NULL) {
  852. if (w->root == fn) {
  853. w->root = w->node = NULL;
  854. RT6_TRACE("W %p adjusted by delroot 1n", w);
  855. } else if (w->node == fn) {
  856. RT6_TRACE("W %p adjusted by delnode 1, s=%d/%dn", w, w->state, nstate);
  857. w->node = pn;
  858. w->state = nstate;
  859. }
  860. } else {
  861. if (w->root == fn) {
  862. w->root = child;
  863. RT6_TRACE("W %p adjusted by delroot 2n", w);
  864. }
  865. if (w->node == fn) {
  866. w->node = child;
  867. if (children&2) {
  868. RT6_TRACE("W %p adjusted by delnode 2, s=%dn", w, w->state);
  869. w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
  870. } else {
  871. RT6_TRACE("W %p adjusted by delnode 2, s=%dn", w, w->state);
  872. w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
  873. }
  874. }
  875. }
  876. }
  877. read_unlock(&fib6_walker_lock);
  879. node_free(fn);
  880. if (pn->fn_flags&RTN_RTINFO || SUBTREE(pn))
  881. return pn;
  883. rt6_release(pn->leaf);
  884. pn->leaf = NULL;
  885. fn = pn;
  886. }
  887. }
  889. static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp)
  890. {
  891. struct fib6_walker_t *w;
  892. struct rt6_info *rt = *rtp;
  894. RT6_TRACE("fib6_del_routen");
  896. /* Unlink it */
  897. *rtp = rt->u.next;
  898. rt->rt6i_node = NULL;
  899. rt6_stats.fib_rt_entries--;
  901. /* Adjust walkers */
  902. read_lock(&fib6_walker_lock);
  903. FOR_WALKERS(w) {
  904. if (w->state == FWS_C && w->leaf == rt) {
  905. RT6_TRACE("walker %p adjusted by delrouten", w);
  906. w->leaf = rt->u.next;
  907. if (w->leaf == NULL)
  908. w->state = FWS_U;
  909. }
  910. }
  911. read_unlock(&fib6_walker_lock);
  913. rt->u.next = NULL;
  915. if (fn->leaf == NULL && fn->fn_flags&RTN_TL_ROOT)
  916. fn->leaf = &ip6_null_entry;
  918. /* If it was last route, expunge its radix tree node */
  919. if (fn->leaf == NULL) {
  920. fn->fn_flags &= ~RTN_RTINFO;
  921. rt6_stats.fib_route_nodes--;
  922. fn = fib6_repair_tree(fn);
  923. }
  925. if (atomic_read(&rt->rt6i_ref) != 1) {
  926. /* This route is used as dummy address holder in some split
  927.  * nodes. It is not leaked, but it still holds other resources,
  928.  * which must be released in time. So, scan ascendant nodes
  929.  * and replace dummy references to this route with references
  930.  * to still alive ones.
  931.  */
  932. while (fn) {
  933. if (!(fn->fn_flags&RTN_RTINFO) && fn->leaf == rt) {
  934. fn->leaf = fib6_find_prefix(fn);
  935. atomic_inc(&fn->leaf->rt6i_ref);
  936. rt6_release(rt);
  937. }
  938. fn = fn->parent;
  939. }
  940. /* No more references are possiible at this point. */
  941. if (atomic_read(&rt->rt6i_ref) != 1) BUG();
  942. }
  944. inet6_rt_notify(RTM_DELROUTE, rt);
  945. rt6_release(rt);
  946. }
  948. int fib6_del(struct rt6_info *rt)
  949. {
  950. struct fib6_node *fn = rt->rt6i_node;
  951. struct rt6_info **rtp;
  953. #if RT6_DEBUG >= 2
  954. if (rt->u.dst.obsolete>0) {
  955. BUG_TRAP(fn==NULL || rt->u.dst.obsolete<=0);
  956. return -ENOENT;
  957. }
  958. #endif
  959. if (fn == NULL || rt == &ip6_null_entry)
  960. return -ENOENT;
  962. BUG_TRAP(fn->fn_flags&RTN_RTINFO);
  964. if (!(rt->rt6i_flags&RTF_CACHE))
  965. fib6_prune_clones(fn, rt);
  967. /*
  968.  * Walk the leaf entries looking for ourself
  969.  */
  971. for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.next) {
  972. if (*rtp == rt) {
  973. fib6_del_route(fn, rtp);
  974. return 0;
  975. }
  976. }
  977. return -ENOENT;
  978. }
  980. /*
  981.  * Tree transversal function.
  982.  *
  983.  * Certainly, it is not interrupt safe.
  984.  * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
  985.  * It means, that we can modify tree during walking
  986.  * and use this function for garbage collection, clone pruning,
  987.  * cleaning tree when a device goes down etc. etc.
  988.  *
  989.  * It guarantees that every node will be traversed,
  990.  * and that it will be traversed only once.
  991.  *
  992.  * Callback function w->func may return:
  993.  * 0 -> continue walking.
  994.  * positive value -> walking is suspended (used by tree dumps,
  995.  * and probably by gc, if it will be split to several slices)
  996.  * negative value -> terminate walking.
  997.  *
  998.  * The function itself returns:
  999.  * 0   -> walk is complete.
  1000.  * >0  -> walk is incomplete (i.e. suspended)
  1001.  * <0  -> walk is terminated by an error.
  1002.  */
  1004. int fib6_walk_continue(struct fib6_walker_t *w)
  1005. {
  1006. struct fib6_node *fn, *pn;
  1008. for (;;) {
  1009. fn = w->node;
  1010. if (fn == NULL)
  1011. return 0;
  1013. if (w->prune && fn != w->root &&
  1014.     fn->fn_flags&RTN_RTINFO && w->state < FWS_C) {
  1015. w->state = FWS_C;
  1016. w->leaf = fn->leaf;
  1017. }
  1018. switch (w->state) {
  1019. #ifdef CONFIG_IPV6_SUBTREES
  1020. case FWS_S:
  1021. if (SUBTREE(fn)) {
  1022. w->node = SUBTREE(fn);
  1023. continue;
  1024. }
  1025. w->state = FWS_L;
  1026. #endif
  1027. case FWS_L:
  1028. if (fn->left) {
  1029. w->node = fn->left;
  1030. w->state = FWS_INIT;
  1031. continue;
  1032. }
  1033. w->state = FWS_R;
  1034. case FWS_R:
  1035. if (fn->right) {
  1036. w->node = fn->right;
  1037. w->state = FWS_INIT;
  1038. continue;
  1039. }
  1040. w->state = FWS_C;
  1041. w->leaf = fn->leaf;
  1042. case FWS_C:
  1043. if (w->leaf && fn->fn_flags&RTN_RTINFO) {
  1044. int err = w->func(w);
  1045. if (err)
  1046. return err;
  1047. continue;
  1048. }
  1049. w->state = FWS_U;
  1050. case FWS_U:
  1051. if (fn == w->root)
  1052. return 0;
  1053. pn = fn->parent;
  1054. w->node = pn;
  1055. #ifdef CONFIG_IPV6_SUBTREES
  1056. if (SUBTREE(pn) == fn) {
  1057. BUG_TRAP(fn->fn_flags&RTN_ROOT);
  1058. w->state = FWS_L;
  1059. continue;
  1060. }
  1061. #endif
  1062. if (pn->left == fn) {
  1063. w->state = FWS_R;
  1064. continue;
  1065. }
  1066. if (pn->right == fn) {
  1067. w->state = FWS_C;
  1068. w->leaf = w->node->leaf;
  1069. continue;
  1070. }
  1071. #if RT6_DEBUG >= 2
  1072. BUG_TRAP(0);
  1073. #endif
  1074. }
  1075. }
  1076. }
  1078. int fib6_walk(struct fib6_walker_t *w)
  1079. {
  1080. int res;
  1082. w->state = FWS_INIT;
  1083. w->node = w->root;
  1085. fib6_walker_link(w);
  1086. res = fib6_walk_continue(w);
  1087. if (res <= 0)
  1088. fib6_walker_unlink(w);
  1089. return res;
  1090. }
  1092. static int fib6_clean_node(struct fib6_walker_t *w)
  1093. {
  1094. int res;
  1095. struct rt6_info *rt;
  1096. struct fib6_cleaner_t *c = (struct fib6_cleaner_t*)w;
  1098. for (rt = w->leaf; rt; rt = rt->u.next) {
  1099. res = c->func(rt, c->arg);
  1100. if (res < 0) {
  1101. w->leaf = rt;
  1102. res = fib6_del(rt);
  1103. if (res) {
  1104. #if RT6_DEBUG >= 2
  1105. printk(KERN_DEBUG "fib6_clean_node: del failed: rt=%p@%p err=%dn", rt, rt->rt6i_node, res);
  1106. #endif
  1107. continue;
  1108. }
  1109. return 0;
  1110. }
  1111. BUG_TRAP(res==0);
  1112. }
  1113. w->leaf = rt;
  1114. return 0;
  1115. }
  1117. /*
  1118.  * Convenient frontend to tree walker.
  1119.  *
  1120.  * func is called on each route.
  1121.  * It may return -1 -> delete this route.
  1122.  *               0  -> continue walking
  1123.  *
  1124.  * prune==1 -> only immediate children of node (certainly,
  1125.  * ignoring pure split nodes) will be scanned.
  1126.  */
  1128. void fib6_clean_tree(struct fib6_node *root,
  1129.      int (*func)(struct rt6_info *, void *arg),
  1130.      int prune, void *arg)
  1131. {
  1132. struct fib6_cleaner_t c;
  1134. c.w.root = root;
  1135. c.w.func = fib6_clean_node;
  1136. c.w.prune = prune;
  1137. c.func = func;
  1138. c.arg = arg;
  1140. fib6_walk(&c.w);
  1141. }
  1143. static int fib6_prune_clone(struct rt6_info *rt, void *arg)
  1144. {
  1145. if (rt->rt6i_flags & RTF_CACHE) {
  1146. RT6_TRACE("pruning clone %pn", rt);
  1147. return -1;
  1148. }
  1150. return 0;
  1151. }
  1153. static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt)
  1154. {
  1155. fib6_clean_tree(fn, fib6_prune_clone, 1, rt);
  1156. }
  1158. /*
  1159.  * Garbage collection
  1160.  */
  1162. static struct fib6_gc_args
  1163. {
  1164. int timeout;
  1165. int more;
  1166. } gc_args;
  1168. static int fib6_age(struct rt6_info *rt, void *arg)
  1169. {
  1170. unsigned long now = jiffies;
  1172. /* Age clones. Note, that clones are aged out
  1173.    only if they are not in use now.
  1174.  */
  1176. /*
  1177.  * check addrconf expiration here.
  1178.  * They are expired even if they are in use.
  1179.  */
  1181. if (rt->rt6i_flags&RTF_EXPIRES && rt->rt6i_expires) {
  1182. if ((long)(now - rt->rt6i_expires) > 0) {
  1183. RT6_TRACE("expiring %pn", rt);
  1184. return -1;
  1185. }
  1186. gc_args.more++;
  1187. } else if (rt->rt6i_flags & RTF_CACHE) {
  1188. if (atomic_read(&rt->u.dst.__refcnt) == 0 &&
  1189.     (long)(now - rt->u.dst.lastuse) >= gc_args.timeout) {
  1190. RT6_TRACE("aging clone %pn", rt);
  1191. return -1;
  1192. }
  1193. gc_args.more++;
  1194. }
  1196. return 0;
  1197. }
  1199. static spinlock_t fib6_gc_lock = SPIN_LOCK_UNLOCKED;
  1201. void fib6_run_gc(unsigned long dummy)
  1202. {
  1203. if (dummy != ~0UL) {
  1204. spin_lock_bh(&fib6_gc_lock);
  1205. gc_args.timeout = (int)dummy;
  1206. } else {
  1207. local_bh_disable();
  1208. if (!spin_trylock(&fib6_gc_lock)) {
  1209. mod_timer(&ip6_fib_timer, jiffies + HZ);
  1210. local_bh_enable();
  1211. return;
  1212. }
  1213. gc_args.timeout = ip6_rt_gc_interval;
  1214. }
  1215. gc_args.more = 0;
  1218. write_lock_bh(&rt6_lock);
  1219. fib6_clean_tree(&ip6_routing_table, fib6_age, 0, NULL);
  1220. write_unlock_bh(&rt6_lock);
  1222. if (gc_args.more)
  1223. mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
  1224. else {
  1225. del_timer(&ip6_fib_timer);
  1226. ip6_fib_timer.expires = 0;
  1227. }
  1228. spin_unlock_bh(&fib6_gc_lock);
  1229. }
  1231. void __init fib6_init(void)
  1232. {
  1233. if (!fib6_node_kmem)
  1234. fib6_node_kmem = kmem_cache_create("fib6_nodes",
  1235.    sizeof(struct fib6_node),
  1236.    0, SLAB_HWCACHE_ALIGN,
  1237.    NULL, NULL);
  1238. }
  1240. #ifdef MODULE
  1241. void fib6_gc_cleanup(void)
  1242. {
  1243. del_timer(&ip6_fib_timer);
  1244. }
  1245. #endif