2 * Linux INET6 implementation
3 * Forwarding Information Database
6 * Pedro Roque <roque@di.fc.ul.pt>
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version
11 * 2 of the License, or (at your option) any later version.
16 * Yuji SEKIYA @USAGI: Support default route on router node;
17 * remove ip6_null_entry from the top of
19 * Ville Nuorvala: Fixed routing subtrees.
21 #include <linux/errno.h>
22 #include <linux/types.h>
23 #include <linux/net.h>
24 #include <linux/route.h>
25 #include <linux/netdevice.h>
26 #include <linux/in6.h>
27 #include <linux/init.h>
28 #include <linux/list.h>
31 #include <linux/proc_fs.h>
35 #include <net/ndisc.h>
36 #include <net/addrconf.h>
38 #include <net/ip6_fib.h>
39 #include <net/ip6_route.h>
44 #define RT6_TRACE(x...) printk(KERN_DEBUG x)
46 #define RT6_TRACE(x...) do { ; } while (0)
49 static struct kmem_cache
* fib6_node_kmem __read_mostly
;
53 #ifdef CONFIG_IPV6_SUBTREES
64 struct fib6_walker_t w
;
66 int (*func
)(struct rt6_info
*, void *arg
);
70 static DEFINE_RWLOCK(fib6_walker_lock
);
72 #ifdef CONFIG_IPV6_SUBTREES
73 #define FWS_INIT FWS_S
75 #define FWS_INIT FWS_L
78 static void fib6_prune_clones(struct net
*net
, struct fib6_node
*fn
,
80 static struct rt6_info
*fib6_find_prefix(struct net
*net
, struct fib6_node
*fn
);
81 static struct fib6_node
*fib6_repair_tree(struct net
*net
, struct fib6_node
*fn
);
82 static int fib6_walk(struct fib6_walker_t
*w
);
83 static int fib6_walk_continue(struct fib6_walker_t
*w
);
86 * A routing update causes an increase of the serial number on the
87 * affected subtree. This allows for cached routes to be asynchronously
88 * tested when modifications are made to the destination cache as a
89 * result of redirects, path MTU changes, etc.
92 static __u32 rt_sernum
;
94 static void fib6_gc_timer_cb(unsigned long arg
);
96 static struct fib6_walker_t fib6_walker_list
= {
97 .prev
= &fib6_walker_list
,
98 .next
= &fib6_walker_list
,
101 #define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)
103 static inline void fib6_walker_link(struct fib6_walker_t
*w
)
105 write_lock_bh(&fib6_walker_lock
);
106 w
->next
= fib6_walker_list
.next
;
107 w
->prev
= &fib6_walker_list
;
110 write_unlock_bh(&fib6_walker_lock
);
113 static inline void fib6_walker_unlink(struct fib6_walker_t
*w
)
115 write_lock_bh(&fib6_walker_lock
);
116 w
->next
->prev
= w
->prev
;
117 w
->prev
->next
= w
->next
;
118 w
->prev
= w
->next
= w
;
119 write_unlock_bh(&fib6_walker_lock
);
121 static __inline__ u32
fib6_new_sernum(void)
130 * Auxiliary address test functions for the radix tree.
132 * These assume a 32bit processor (although it will work on
140 static __inline__ __be32
addr_bit_set(void *token
, int fn_bit
)
142 __be32
*addr
= token
;
144 return htonl(1 << ((~fn_bit
)&0x1F)) & addr
[fn_bit
>>5];
147 static __inline__
struct fib6_node
* node_alloc(void)
149 struct fib6_node
*fn
;
151 fn
= kmem_cache_zalloc(fib6_node_kmem
, GFP_ATOMIC
);
156 static __inline__
void node_free(struct fib6_node
* fn
)
158 kmem_cache_free(fib6_node_kmem
, fn
);
161 static __inline__
void rt6_release(struct rt6_info
*rt
)
163 if (atomic_dec_and_test(&rt
->rt6i_ref
))
164 dst_free(&rt
->u
.dst
);
167 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
168 #define FIB_TABLE_HASHSZ 256
170 #define FIB_TABLE_HASHSZ 1
173 static void fib6_link_table(struct net
*net
, struct fib6_table
*tb
)
178 * Initialize table lock at a single place to give lockdep a key,
179 * tables aren't visible prior to being linked to the list.
181 rwlock_init(&tb
->tb6_lock
);
183 h
= tb
->tb6_id
& (FIB_TABLE_HASHSZ
- 1);
186 * No protection necessary, this is the only list mutatation
187 * operation, tables never disappear once they exist.
189 hlist_add_head_rcu(&tb
->tb6_hlist
, &net
->ipv6
.fib_table_hash
[h
]);
192 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
194 static struct fib6_table
*fib6_alloc_table(struct net
*net
, u32 id
)
196 struct fib6_table
*table
;
198 table
= kzalloc(sizeof(*table
), GFP_ATOMIC
);
201 table
->tb6_root
.leaf
= net
->ipv6
.ip6_null_entry
;
202 table
->tb6_root
.fn_flags
= RTN_ROOT
| RTN_TL_ROOT
| RTN_RTINFO
;
208 struct fib6_table
*fib6_new_table(struct net
*net
, u32 id
)
210 struct fib6_table
*tb
;
214 tb
= fib6_get_table(net
, id
);
218 tb
= fib6_alloc_table(net
, id
);
220 fib6_link_table(net
, tb
);
225 struct fib6_table
*fib6_get_table(struct net
*net
, u32 id
)
227 struct fib6_table
*tb
;
228 struct hlist_head
*head
;
229 struct hlist_node
*node
;
234 h
= id
& (FIB_TABLE_HASHSZ
- 1);
236 head
= &net
->ipv6
.fib_table_hash
[h
];
237 hlist_for_each_entry_rcu(tb
, node
, head
, tb6_hlist
) {
238 if (tb
->tb6_id
== id
) {
248 static void fib6_tables_init(struct net
*net
)
250 fib6_link_table(net
, net
->ipv6
.fib6_main_tbl
);
251 fib6_link_table(net
, net
->ipv6
.fib6_local_tbl
);
255 struct fib6_table
*fib6_new_table(struct net
*net
, u32 id
)
257 return fib6_get_table(net
, id
);
260 struct fib6_table
*fib6_get_table(struct net
*net
, u32 id
)
262 return net
->ipv6
.fib6_main_tbl
;
265 struct dst_entry
*fib6_rule_lookup(struct net
*net
, struct flowi
*fl
,
266 int flags
, pol_lookup_t lookup
)
268 return (struct dst_entry
*) lookup(net
, net
->ipv6
.fib6_main_tbl
, fl
, flags
);
271 static void fib6_tables_init(struct net
*net
)
273 fib6_link_table(net
, net
->ipv6
.fib6_main_tbl
);
278 static int fib6_dump_node(struct fib6_walker_t
*w
)
283 for (rt
= w
->leaf
; rt
; rt
= rt
->u
.dst
.rt6_next
) {
284 res
= rt6_dump_route(rt
, w
->args
);
286 /* Frame is full, suspend walking */
296 static void fib6_dump_end(struct netlink_callback
*cb
)
298 struct fib6_walker_t
*w
= (void*)cb
->args
[2];
304 cb
->done
= (void*)cb
->args
[3];
308 static int fib6_dump_done(struct netlink_callback
*cb
)
311 return cb
->done
? cb
->done(cb
) : 0;
314 static int fib6_dump_table(struct fib6_table
*table
, struct sk_buff
*skb
,
315 struct netlink_callback
*cb
)
317 struct fib6_walker_t
*w
;
320 w
= (void *)cb
->args
[2];
321 w
->root
= &table
->tb6_root
;
323 if (cb
->args
[4] == 0) {
324 read_lock_bh(&table
->tb6_lock
);
326 read_unlock_bh(&table
->tb6_lock
);
330 read_lock_bh(&table
->tb6_lock
);
331 res
= fib6_walk_continue(w
);
332 read_unlock_bh(&table
->tb6_lock
);
335 fib6_walker_unlink(w
);
338 fib6_walker_unlink(w
);
345 static int inet6_dump_fib(struct sk_buff
*skb
, struct netlink_callback
*cb
)
347 struct net
*net
= sock_net(skb
->sk
);
349 unsigned int e
= 0, s_e
;
350 struct rt6_rtnl_dump_arg arg
;
351 struct fib6_walker_t
*w
;
352 struct fib6_table
*tb
;
353 struct hlist_node
*node
;
354 struct hlist_head
*head
;
360 w
= (void *)cb
->args
[2];
364 * 1. hook callback destructor.
366 cb
->args
[3] = (long)cb
->done
;
367 cb
->done
= fib6_dump_done
;
370 * 2. allocate and initialize walker.
372 w
= kzalloc(sizeof(*w
), GFP_ATOMIC
);
375 w
->func
= fib6_dump_node
;
376 cb
->args
[2] = (long)w
;
383 for (h
= s_h
; h
< FIB_TABLE_HASHSZ
; h
++, s_e
= 0) {
385 head
= &net
->ipv6
.fib_table_hash
[h
];
386 hlist_for_each_entry(tb
, node
, head
, tb6_hlist
) {
389 res
= fib6_dump_table(tb
, skb
, cb
);
400 res
= res
< 0 ? res
: skb
->len
;
409 * return the appropriate node for a routing tree "add" operation
410 * by either creating and inserting or by returning an existing
414 static struct fib6_node
* fib6_add_1(struct fib6_node
*root
, void *addr
,
415 int addrlen
, int plen
,
418 struct fib6_node
*fn
, *in
, *ln
;
419 struct fib6_node
*pn
= NULL
;
423 __u32 sernum
= fib6_new_sernum();
425 RT6_TRACE("fib6_add_1\n");
427 /* insert node in tree */
432 key
= (struct rt6key
*)((u8
*)fn
->leaf
+ offset
);
437 if (plen
< fn
->fn_bit
||
438 !ipv6_prefix_equal(&key
->addr
, addr
, fn
->fn_bit
))
445 if (plen
== fn
->fn_bit
) {
446 /* clean up an intermediate node */
447 if ((fn
->fn_flags
& RTN_RTINFO
) == 0) {
448 rt6_release(fn
->leaf
);
452 fn
->fn_sernum
= sernum
;
458 * We have more bits to go
461 /* Try to walk down on tree. */
462 fn
->fn_sernum
= sernum
;
463 dir
= addr_bit_set(addr
, fn
->fn_bit
);
465 fn
= dir
? fn
->right
: fn
->left
;
469 * We walked to the bottom of tree.
470 * Create new leaf node without children.
480 ln
->fn_sernum
= sernum
;
492 * split since we don't have a common prefix anymore or
493 * we have a less significant route.
494 * we've to insert an intermediate node on the list
495 * this new node will point to the one we need to create
501 /* find 1st bit in difference between the 2 addrs.
503 See comment in __ipv6_addr_diff: bit may be an invalid value,
504 but if it is >= plen, the value is ignored in any case.
507 bit
= __ipv6_addr_diff(addr
, &key
->addr
, addrlen
);
512 * (new leaf node)[ln] (old node)[fn]
518 if (in
== NULL
|| ln
== NULL
) {
527 * new intermediate node.
529 * be off since that an address that chooses one of
530 * the branches would not match less specific routes
531 * in the other branch
538 atomic_inc(&in
->leaf
->rt6i_ref
);
540 in
->fn_sernum
= sernum
;
542 /* update parent pointer */
553 ln
->fn_sernum
= sernum
;
555 if (addr_bit_set(addr
, bit
)) {
562 } else { /* plen <= bit */
565 * (new leaf node)[ln]
567 * (old node)[fn] NULL
579 ln
->fn_sernum
= sernum
;
586 if (addr_bit_set(&key
->addr
, plen
))
597 * Insert routing information in a node.
600 static int fib6_add_rt2node(struct fib6_node
*fn
, struct rt6_info
*rt
,
601 struct nl_info
*info
)
603 struct rt6_info
*iter
= NULL
;
604 struct rt6_info
**ins
;
608 for (iter
= fn
->leaf
; iter
; iter
=iter
->u
.dst
.rt6_next
) {
610 * Search for duplicates
613 if (iter
->rt6i_metric
== rt
->rt6i_metric
) {
615 * Same priority level
618 if (iter
->rt6i_dev
== rt
->rt6i_dev
&&
619 iter
->rt6i_idev
== rt
->rt6i_idev
&&
620 ipv6_addr_equal(&iter
->rt6i_gateway
,
621 &rt
->rt6i_gateway
)) {
622 if (!(iter
->rt6i_flags
&RTF_EXPIRES
))
624 iter
->rt6i_expires
= rt
->rt6i_expires
;
625 if (!(rt
->rt6i_flags
&RTF_EXPIRES
)) {
626 iter
->rt6i_flags
&= ~RTF_EXPIRES
;
627 iter
->rt6i_expires
= 0;
633 if (iter
->rt6i_metric
> rt
->rt6i_metric
)
636 ins
= &iter
->u
.dst
.rt6_next
;
639 /* Reset round-robin state, if necessary */
640 if (ins
== &fn
->leaf
)
647 rt
->u
.dst
.rt6_next
= iter
;
650 atomic_inc(&rt
->rt6i_ref
);
651 inet6_rt_notify(RTM_NEWROUTE
, rt
, info
);
652 info
->nl_net
->ipv6
.rt6_stats
->fib_rt_entries
++;
654 if ((fn
->fn_flags
& RTN_RTINFO
) == 0) {
655 info
->nl_net
->ipv6
.rt6_stats
->fib_route_nodes
++;
656 fn
->fn_flags
|= RTN_RTINFO
;
662 static __inline__
void fib6_start_gc(struct net
*net
, struct rt6_info
*rt
)
664 if (!timer_pending(&net
->ipv6
.ip6_fib_timer
) &&
665 (rt
->rt6i_flags
& (RTF_EXPIRES
|RTF_CACHE
)))
666 mod_timer(&net
->ipv6
.ip6_fib_timer
,
667 jiffies
+ net
->ipv6
.sysctl
.ip6_rt_gc_interval
);
670 void fib6_force_start_gc(struct net
*net
)
672 if (!timer_pending(&net
->ipv6
.ip6_fib_timer
))
673 mod_timer(&net
->ipv6
.ip6_fib_timer
,
674 jiffies
+ net
->ipv6
.sysctl
.ip6_rt_gc_interval
);
678 * Add routing information to the routing tree.
679 * <destination addr>/<source addr>
680 * with source addr info in sub-trees
683 int fib6_add(struct fib6_node
*root
, struct rt6_info
*rt
, struct nl_info
*info
)
685 struct fib6_node
*fn
, *pn
= NULL
;
688 fn
= fib6_add_1(root
, &rt
->rt6i_dst
.addr
, sizeof(struct in6_addr
),
689 rt
->rt6i_dst
.plen
, offsetof(struct rt6_info
, rt6i_dst
));
696 #ifdef CONFIG_IPV6_SUBTREES
697 if (rt
->rt6i_src
.plen
) {
698 struct fib6_node
*sn
;
700 if (fn
->subtree
== NULL
) {
701 struct fib6_node
*sfn
;
713 /* Create subtree root node */
718 sfn
->leaf
= info
->nl_net
->ipv6
.ip6_null_entry
;
719 atomic_inc(&info
->nl_net
->ipv6
.ip6_null_entry
->rt6i_ref
);
720 sfn
->fn_flags
= RTN_ROOT
;
721 sfn
->fn_sernum
= fib6_new_sernum();
723 /* Now add the first leaf node to new subtree */
725 sn
= fib6_add_1(sfn
, &rt
->rt6i_src
.addr
,
726 sizeof(struct in6_addr
), rt
->rt6i_src
.plen
,
727 offsetof(struct rt6_info
, rt6i_src
));
730 /* If it is failed, discard just allocated
731 root, and then (in st_failure) stale node
738 /* Now link new subtree to main tree */
742 sn
= fib6_add_1(fn
->subtree
, &rt
->rt6i_src
.addr
,
743 sizeof(struct in6_addr
), rt
->rt6i_src
.plen
,
744 offsetof(struct rt6_info
, rt6i_src
));
750 if (fn
->leaf
== NULL
) {
752 atomic_inc(&rt
->rt6i_ref
);
758 err
= fib6_add_rt2node(fn
, rt
, info
);
761 fib6_start_gc(info
->nl_net
, rt
);
762 if (!(rt
->rt6i_flags
&RTF_CACHE
))
763 fib6_prune_clones(info
->nl_net
, pn
, rt
);
768 #ifdef CONFIG_IPV6_SUBTREES
770 * If fib6_add_1 has cleared the old leaf pointer in the
771 * super-tree leaf node we have to find a new one for it.
773 if (pn
!= fn
&& pn
->leaf
== rt
) {
775 atomic_dec(&rt
->rt6i_ref
);
777 if (pn
!= fn
&& !pn
->leaf
&& !(pn
->fn_flags
& RTN_RTINFO
)) {
778 pn
->leaf
= fib6_find_prefix(info
->nl_net
, pn
);
781 WARN_ON(pn
->leaf
== NULL
);
782 pn
->leaf
= info
->nl_net
->ipv6
.ip6_null_entry
;
785 atomic_inc(&pn
->leaf
->rt6i_ref
);
788 dst_free(&rt
->u
.dst
);
792 #ifdef CONFIG_IPV6_SUBTREES
793 /* Subtree creation failed, probably main tree node
794 is orphan. If it is, shoot it.
797 if (fn
&& !(fn
->fn_flags
& (RTN_RTINFO
|RTN_ROOT
)))
798 fib6_repair_tree(info
->nl_net
, fn
);
799 dst_free(&rt
->u
.dst
);
805 * Routing tree lookup
810 int offset
; /* key offset on rt6_info */
811 struct in6_addr
*addr
; /* search key */
814 static struct fib6_node
* fib6_lookup_1(struct fib6_node
*root
,
815 struct lookup_args
*args
)
817 struct fib6_node
*fn
;
820 if (unlikely(args
->offset
== 0))
830 struct fib6_node
*next
;
832 dir
= addr_bit_set(args
->addr
, fn
->fn_bit
);
834 next
= dir
? fn
->right
: fn
->left
;
845 if (FIB6_SUBTREE(fn
) || fn
->fn_flags
& RTN_RTINFO
) {
848 key
= (struct rt6key
*) ((u8
*) fn
->leaf
+
851 if (ipv6_prefix_equal(&key
->addr
, args
->addr
, key
->plen
)) {
852 #ifdef CONFIG_IPV6_SUBTREES
854 fn
= fib6_lookup_1(fn
->subtree
, args
+ 1);
856 if (!fn
|| fn
->fn_flags
& RTN_RTINFO
)
861 if (fn
->fn_flags
& RTN_ROOT
)
870 struct fib6_node
* fib6_lookup(struct fib6_node
*root
, struct in6_addr
*daddr
,
871 struct in6_addr
*saddr
)
873 struct fib6_node
*fn
;
874 struct lookup_args args
[] = {
876 .offset
= offsetof(struct rt6_info
, rt6i_dst
),
879 #ifdef CONFIG_IPV6_SUBTREES
881 .offset
= offsetof(struct rt6_info
, rt6i_src
),
886 .offset
= 0, /* sentinel */
890 fn
= fib6_lookup_1(root
, daddr
? args
: args
+ 1);
892 if (fn
== NULL
|| fn
->fn_flags
& RTN_TL_ROOT
)
899 * Get node with specified destination prefix (and source prefix,
900 * if subtrees are used)
904 static struct fib6_node
* fib6_locate_1(struct fib6_node
*root
,
905 struct in6_addr
*addr
,
906 int plen
, int offset
)
908 struct fib6_node
*fn
;
910 for (fn
= root
; fn
; ) {
911 struct rt6key
*key
= (struct rt6key
*)((u8
*)fn
->leaf
+ offset
);
916 if (plen
< fn
->fn_bit
||
917 !ipv6_prefix_equal(&key
->addr
, addr
, fn
->fn_bit
))
920 if (plen
== fn
->fn_bit
)
924 * We have more bits to go
926 if (addr_bit_set(addr
, fn
->fn_bit
))
934 struct fib6_node
* fib6_locate(struct fib6_node
*root
,
935 struct in6_addr
*daddr
, int dst_len
,
936 struct in6_addr
*saddr
, int src_len
)
938 struct fib6_node
*fn
;
940 fn
= fib6_locate_1(root
, daddr
, dst_len
,
941 offsetof(struct rt6_info
, rt6i_dst
));
943 #ifdef CONFIG_IPV6_SUBTREES
945 WARN_ON(saddr
== NULL
);
946 if (fn
&& fn
->subtree
)
947 fn
= fib6_locate_1(fn
->subtree
, saddr
, src_len
,
948 offsetof(struct rt6_info
, rt6i_src
));
952 if (fn
&& fn
->fn_flags
&RTN_RTINFO
)
964 static struct rt6_info
*fib6_find_prefix(struct net
*net
, struct fib6_node
*fn
)
966 if (fn
->fn_flags
&RTN_ROOT
)
967 return net
->ipv6
.ip6_null_entry
;
971 return fn
->left
->leaf
;
974 return fn
->right
->leaf
;
976 fn
= FIB6_SUBTREE(fn
);
982 * Called to trim the tree of intermediate nodes when possible. "fn"
983 * is the node we want to try and remove.
986 static struct fib6_node
*fib6_repair_tree(struct net
*net
,
987 struct fib6_node
*fn
)
991 struct fib6_node
*child
, *pn
;
992 struct fib6_walker_t
*w
;
996 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn
->fn_bit
, iter
);
999 WARN_ON(fn
->fn_flags
& RTN_RTINFO
);
1000 WARN_ON(fn
->fn_flags
& RTN_TL_ROOT
);
1001 WARN_ON(fn
->leaf
!= NULL
);
1005 if (fn
->right
) child
= fn
->right
, children
|= 1;
1006 if (fn
->left
) child
= fn
->left
, children
|= 2;
1008 if (children
== 3 || FIB6_SUBTREE(fn
)
1009 #ifdef CONFIG_IPV6_SUBTREES
1010 /* Subtree root (i.e. fn) may have one child */
1011 || (children
&& fn
->fn_flags
&RTN_ROOT
)
1014 fn
->leaf
= fib6_find_prefix(net
, fn
);
1016 if (fn
->leaf
==NULL
) {
1018 fn
->leaf
= net
->ipv6
.ip6_null_entry
;
1021 atomic_inc(&fn
->leaf
->rt6i_ref
);
1026 #ifdef CONFIG_IPV6_SUBTREES
1027 if (FIB6_SUBTREE(pn
) == fn
) {
1028 WARN_ON(!(fn
->fn_flags
& RTN_ROOT
));
1029 FIB6_SUBTREE(pn
) = NULL
;
1032 WARN_ON(fn
->fn_flags
& RTN_ROOT
);
1034 if (pn
->right
== fn
) pn
->right
= child
;
1035 else if (pn
->left
== fn
) pn
->left
= child
;
1043 #ifdef CONFIG_IPV6_SUBTREES
1047 read_lock(&fib6_walker_lock
);
1049 if (child
== NULL
) {
1050 if (w
->root
== fn
) {
1051 w
->root
= w
->node
= NULL
;
1052 RT6_TRACE("W %p adjusted by delroot 1\n", w
);
1053 } else if (w
->node
== fn
) {
1054 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w
, w
->state
, nstate
);
1059 if (w
->root
== fn
) {
1061 RT6_TRACE("W %p adjusted by delroot 2\n", w
);
1063 if (w
->node
== fn
) {
1066 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w
, w
->state
);
1067 w
->state
= w
->state
>=FWS_R
? FWS_U
: FWS_INIT
;
1069 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w
, w
->state
);
1070 w
->state
= w
->state
>=FWS_C
? FWS_U
: FWS_INIT
;
1075 read_unlock(&fib6_walker_lock
);
1078 if (pn
->fn_flags
&RTN_RTINFO
|| FIB6_SUBTREE(pn
))
1081 rt6_release(pn
->leaf
);
1087 static void fib6_del_route(struct fib6_node
*fn
, struct rt6_info
**rtp
,
1088 struct nl_info
*info
)
1090 struct fib6_walker_t
*w
;
1091 struct rt6_info
*rt
= *rtp
;
1092 struct net
*net
= info
->nl_net
;
1094 RT6_TRACE("fib6_del_route\n");
1097 *rtp
= rt
->u
.dst
.rt6_next
;
1098 rt
->rt6i_node
= NULL
;
1099 net
->ipv6
.rt6_stats
->fib_rt_entries
--;
1100 net
->ipv6
.rt6_stats
->fib_discarded_routes
++;
1102 /* Reset round-robin state, if necessary */
1103 if (fn
->rr_ptr
== rt
)
1106 /* Adjust walkers */
1107 read_lock(&fib6_walker_lock
);
1109 if (w
->state
== FWS_C
&& w
->leaf
== rt
) {
1110 RT6_TRACE("walker %p adjusted by delroute\n", w
);
1111 w
->leaf
= rt
->u
.dst
.rt6_next
;
1112 if (w
->leaf
== NULL
)
1116 read_unlock(&fib6_walker_lock
);
1118 rt
->u
.dst
.rt6_next
= NULL
;
1120 /* If it was last route, expunge its radix tree node */
1121 if (fn
->leaf
== NULL
) {
1122 fn
->fn_flags
&= ~RTN_RTINFO
;
1123 net
->ipv6
.rt6_stats
->fib_route_nodes
--;
1124 fn
= fib6_repair_tree(net
, fn
);
1127 if (atomic_read(&rt
->rt6i_ref
) != 1) {
1128 /* This route is used as dummy address holder in some split
1129 * nodes. It is not leaked, but it still holds other resources,
1130 * which must be released in time. So, scan ascendant nodes
1131 * and replace dummy references to this route with references
1132 * to still alive ones.
1135 if (!(fn
->fn_flags
&RTN_RTINFO
) && fn
->leaf
== rt
) {
1136 fn
->leaf
= fib6_find_prefix(net
, fn
);
1137 atomic_inc(&fn
->leaf
->rt6i_ref
);
1142 /* No more references are possible at this point. */
1143 BUG_ON(atomic_read(&rt
->rt6i_ref
) != 1);
1146 inet6_rt_notify(RTM_DELROUTE
, rt
, info
);
1150 int fib6_del(struct rt6_info
*rt
, struct nl_info
*info
)
1152 struct net
*net
= info
->nl_net
;
1153 struct fib6_node
*fn
= rt
->rt6i_node
;
1154 struct rt6_info
**rtp
;
1157 if (rt
->u
.dst
.obsolete
>0) {
1158 WARN_ON(fn
!= NULL
);
1162 if (fn
== NULL
|| rt
== net
->ipv6
.ip6_null_entry
)
1165 WARN_ON(!(fn
->fn_flags
& RTN_RTINFO
));
1167 if (!(rt
->rt6i_flags
&RTF_CACHE
)) {
1168 struct fib6_node
*pn
= fn
;
1169 #ifdef CONFIG_IPV6_SUBTREES
1170 /* clones of this route might be in another subtree */
1171 if (rt
->rt6i_src
.plen
) {
1172 while (!(pn
->fn_flags
&RTN_ROOT
))
1177 fib6_prune_clones(info
->nl_net
, pn
, rt
);
1181 * Walk the leaf entries looking for ourself
1184 for (rtp
= &fn
->leaf
; *rtp
; rtp
= &(*rtp
)->u
.dst
.rt6_next
) {
1186 fib6_del_route(fn
, rtp
, info
);
1194 * Tree traversal function.
1196 * Certainly, it is not interrupt safe.
1197 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1198 * It means, that we can modify tree during walking
1199 * and use this function for garbage collection, clone pruning,
1200 * cleaning tree when a device goes down etc. etc.
1202 * It guarantees that every node will be traversed,
1203 * and that it will be traversed only once.
1205 * Callback function w->func may return:
1206 * 0 -> continue walking.
1207 * positive value -> walking is suspended (used by tree dumps,
1208 * and probably by gc, if it will be split to several slices)
1209 * negative value -> terminate walking.
1211 * The function itself returns:
1212 * 0 -> walk is complete.
1213 * >0 -> walk is incomplete (i.e. suspended)
1214 * <0 -> walk is terminated by an error.
1217 static int fib6_walk_continue(struct fib6_walker_t
*w
)
1219 struct fib6_node
*fn
, *pn
;
1226 if (w
->prune
&& fn
!= w
->root
&&
1227 fn
->fn_flags
&RTN_RTINFO
&& w
->state
< FWS_C
) {
1232 #ifdef CONFIG_IPV6_SUBTREES
1234 if (FIB6_SUBTREE(fn
)) {
1235 w
->node
= FIB6_SUBTREE(fn
);
1243 w
->state
= FWS_INIT
;
1249 w
->node
= fn
->right
;
1250 w
->state
= FWS_INIT
;
1256 if (w
->leaf
&& fn
->fn_flags
&RTN_RTINFO
) {
1257 int err
= w
->func(w
);
1268 #ifdef CONFIG_IPV6_SUBTREES
1269 if (FIB6_SUBTREE(pn
) == fn
) {
1270 WARN_ON(!(fn
->fn_flags
& RTN_ROOT
));
1275 if (pn
->left
== fn
) {
1279 if (pn
->right
== fn
) {
1281 w
->leaf
= w
->node
->leaf
;
1291 static int fib6_walk(struct fib6_walker_t
*w
)
1295 w
->state
= FWS_INIT
;
1298 fib6_walker_link(w
);
1299 res
= fib6_walk_continue(w
);
1301 fib6_walker_unlink(w
);
1305 static int fib6_clean_node(struct fib6_walker_t
*w
)
1308 struct rt6_info
*rt
;
1309 struct fib6_cleaner_t
*c
= container_of(w
, struct fib6_cleaner_t
, w
);
1310 struct nl_info info
= {
1314 for (rt
= w
->leaf
; rt
; rt
= rt
->u
.dst
.rt6_next
) {
1315 res
= c
->func(rt
, c
->arg
);
1318 res
= fib6_del(rt
, &info
);
1321 printk(KERN_DEBUG
"fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt
, rt
->rt6i_node
, res
);
1334 * Convenient frontend to tree walker.
1336 * func is called on each route.
1337 * It may return -1 -> delete this route.
1338 * 0 -> continue walking
1340 * prune==1 -> only immediate children of node (certainly,
1341 * ignoring pure split nodes) will be scanned.
1344 static void fib6_clean_tree(struct net
*net
, struct fib6_node
*root
,
1345 int (*func
)(struct rt6_info
*, void *arg
),
1346 int prune
, void *arg
)
1348 struct fib6_cleaner_t c
;
1351 c
.w
.func
= fib6_clean_node
;
1360 void fib6_clean_all(struct net
*net
, int (*func
)(struct rt6_info
*, void *arg
),
1361 int prune
, void *arg
)
1363 struct fib6_table
*table
;
1364 struct hlist_node
*node
;
1365 struct hlist_head
*head
;
1369 for (h
= 0; h
< FIB_TABLE_HASHSZ
; h
++) {
1370 head
= &net
->ipv6
.fib_table_hash
[h
];
1371 hlist_for_each_entry_rcu(table
, node
, head
, tb6_hlist
) {
1372 write_lock_bh(&table
->tb6_lock
);
1373 fib6_clean_tree(net
, &table
->tb6_root
,
1375 write_unlock_bh(&table
->tb6_lock
);
1381 static int fib6_prune_clone(struct rt6_info
*rt
, void *arg
)
1383 if (rt
->rt6i_flags
& RTF_CACHE
) {
1384 RT6_TRACE("pruning clone %p\n", rt
);
1391 static void fib6_prune_clones(struct net
*net
, struct fib6_node
*fn
,
1392 struct rt6_info
*rt
)
1394 fib6_clean_tree(net
, fn
, fib6_prune_clone
, 1, rt
);
1398 * Garbage collection
1401 static struct fib6_gc_args
1407 static int fib6_age(struct rt6_info
*rt
, void *arg
)
1409 unsigned long now
= jiffies
;
1412 * check addrconf expiration here.
1413 * Routes are expired even if they are in use.
1415 * Also age clones. Note, that clones are aged out
1416 * only if they are not in use now.
1419 if (rt
->rt6i_flags
&RTF_EXPIRES
&& rt
->rt6i_expires
) {
1420 if (time_after(now
, rt
->rt6i_expires
)) {
1421 RT6_TRACE("expiring %p\n", rt
);
1425 } else if (rt
->rt6i_flags
& RTF_CACHE
) {
1426 if (atomic_read(&rt
->u
.dst
.__refcnt
) == 0 &&
1427 time_after_eq(now
, rt
->u
.dst
.lastuse
+ gc_args
.timeout
)) {
1428 RT6_TRACE("aging clone %p\n", rt
);
1430 } else if ((rt
->rt6i_flags
& RTF_GATEWAY
) &&
1431 (!(rt
->rt6i_nexthop
->flags
& NTF_ROUTER
))) {
1432 RT6_TRACE("purging route %p via non-router but gateway\n",
1442 static DEFINE_SPINLOCK(fib6_gc_lock
);
1444 void fib6_run_gc(unsigned long expires
, struct net
*net
)
1446 if (expires
!= ~0UL) {
1447 spin_lock_bh(&fib6_gc_lock
);
1448 gc_args
.timeout
= expires
? (int)expires
:
1449 net
->ipv6
.sysctl
.ip6_rt_gc_interval
;
1451 if (!spin_trylock_bh(&fib6_gc_lock
)) {
1452 mod_timer(&net
->ipv6
.ip6_fib_timer
, jiffies
+ HZ
);
1455 gc_args
.timeout
= net
->ipv6
.sysctl
.ip6_rt_gc_interval
;
1458 gc_args
.more
= icmp6_dst_gc();
1460 fib6_clean_all(net
, fib6_age
, 0, NULL
);
1463 mod_timer(&net
->ipv6
.ip6_fib_timer
,
1464 round_jiffies(jiffies
1465 + net
->ipv6
.sysctl
.ip6_rt_gc_interval
));
1467 del_timer(&net
->ipv6
.ip6_fib_timer
);
1468 spin_unlock_bh(&fib6_gc_lock
);
1471 static void fib6_gc_timer_cb(unsigned long arg
)
1473 fib6_run_gc(0, (struct net
*)arg
);
1476 static int fib6_net_init(struct net
*net
)
1478 setup_timer(&net
->ipv6
.ip6_fib_timer
, fib6_gc_timer_cb
, (unsigned long)net
);
1480 net
->ipv6
.rt6_stats
= kzalloc(sizeof(*net
->ipv6
.rt6_stats
), GFP_KERNEL
);
1481 if (!net
->ipv6
.rt6_stats
)
1484 net
->ipv6
.fib_table_hash
= kcalloc(FIB_TABLE_HASHSZ
,
1485 sizeof(*net
->ipv6
.fib_table_hash
),
1487 if (!net
->ipv6
.fib_table_hash
)
1490 net
->ipv6
.fib6_main_tbl
= kzalloc(sizeof(*net
->ipv6
.fib6_main_tbl
),
1492 if (!net
->ipv6
.fib6_main_tbl
)
1493 goto out_fib_table_hash
;
1495 net
->ipv6
.fib6_main_tbl
->tb6_id
= RT6_TABLE_MAIN
;
1496 net
->ipv6
.fib6_main_tbl
->tb6_root
.leaf
= net
->ipv6
.ip6_null_entry
;
1497 net
->ipv6
.fib6_main_tbl
->tb6_root
.fn_flags
=
1498 RTN_ROOT
| RTN_TL_ROOT
| RTN_RTINFO
;
1500 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1501 net
->ipv6
.fib6_local_tbl
= kzalloc(sizeof(*net
->ipv6
.fib6_local_tbl
),
1503 if (!net
->ipv6
.fib6_local_tbl
)
1504 goto out_fib6_main_tbl
;
1505 net
->ipv6
.fib6_local_tbl
->tb6_id
= RT6_TABLE_LOCAL
;
1506 net
->ipv6
.fib6_local_tbl
->tb6_root
.leaf
= net
->ipv6
.ip6_null_entry
;
1507 net
->ipv6
.fib6_local_tbl
->tb6_root
.fn_flags
=
1508 RTN_ROOT
| RTN_TL_ROOT
| RTN_RTINFO
;
1510 fib6_tables_init(net
);
1514 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1516 kfree(net
->ipv6
.fib6_main_tbl
);
1519 kfree(net
->ipv6
.fib_table_hash
);
1521 kfree(net
->ipv6
.rt6_stats
);
1526 static void fib6_net_exit(struct net
*net
)
1528 rt6_ifdown(net
, NULL
);
1529 del_timer_sync(&net
->ipv6
.ip6_fib_timer
);
1531 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1532 kfree(net
->ipv6
.fib6_local_tbl
);
1534 kfree(net
->ipv6
.fib6_main_tbl
);
1535 kfree(net
->ipv6
.fib_table_hash
);
1536 kfree(net
->ipv6
.rt6_stats
);
1539 static struct pernet_operations fib6_net_ops
= {
1540 .init
= fib6_net_init
,
1541 .exit
= fib6_net_exit
,
1544 int __init
fib6_init(void)
1548 fib6_node_kmem
= kmem_cache_create("fib6_nodes",
1549 sizeof(struct fib6_node
),
1550 0, SLAB_HWCACHE_ALIGN
,
1552 if (!fib6_node_kmem
)
1555 ret
= register_pernet_subsys(&fib6_net_ops
);
1557 goto out_kmem_cache_create
;
1559 ret
= __rtnl_register(PF_INET6
, RTM_GETROUTE
, NULL
, inet6_dump_fib
);
1561 goto out_unregister_subsys
;
1565 out_unregister_subsys
:
1566 unregister_pernet_subsys(&fib6_net_ops
);
1567 out_kmem_cache_create
:
1568 kmem_cache_destroy(fib6_node_kmem
);
1572 void fib6_gc_cleanup(void)
1574 unregister_pernet_subsys(&fib6_net_ops
);
1575 kmem_cache_destroy(fib6_node_kmem
);