2 * Linux INET6 implementation
3 * Forwarding Information Database
6 * Pedro Roque <roque@di.fc.ul.pt>
8 * $Id: ip6_fib.c,v 1.25 2001/10/31 21:55:55 davem Exp $
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.
18 * Yuji SEKIYA @USAGI: Support default route on router node;
19 * remove ip6_null_entry from the top of
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>
32 #include <linux/proc_fs.h>
36 #include <net/ndisc.h>
37 #include <net/addrconf.h>
39 #include <net/ip6_fib.h>
40 #include <net/ip6_route.h>
45 #define RT6_TRACE(x...) printk(KERN_DEBUG x)
47 #define RT6_TRACE(x...) do { ; } while (0)
50 struct rt6_statistics rt6_stats
;
52 static kmem_cache_t
* fib6_node_kmem
;
56 #ifdef CONFIG_IPV6_SUBTREES
67 struct fib6_walker_t w
;
68 int (*func
)(struct rt6_info
*, void *arg
);
72 rwlock_t fib6_walker_lock
= RW_LOCK_UNLOCKED
;
75 #ifdef CONFIG_IPV6_SUBTREES
76 #define FWS_INIT FWS_S
77 #define SUBTREE(fn) ((fn)->subtree)
79 #define FWS_INIT FWS_L
80 #define SUBTREE(fn) NULL
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
);
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.
93 static __u32 rt_sernum
;
95 static struct timer_list ip6_fib_timer
= TIMER_INITIALIZER(fib6_run_gc
, 0, 0);
97 struct fib6_walker_t fib6_walker_list
= {
98 .prev
= &fib6_walker_list
,
99 .next
= &fib6_walker_list
,
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)
113 * Auxiliary address test functions for the radix tree.
115 * These assume a 32bit processor (although it will work on
120 * compare "prefix length" bits of an address
123 static __inline__
int addr_match(void *token1
, void *token2
, int prefixlen
)
130 pdw
= prefixlen
>> 5; /* num of whole __u32 in prefix */
131 pbi
= prefixlen
& 0x1f; /* num of bits in incomplete u32 in prefix */
134 if (memcmp(a1
, a2
, pdw
<< 2))
140 mask
= htonl((0xffffffff) << (32 - pbi
));
142 if ((a1
[pdw
] ^ a2
[pdw
]) & mask
)
153 static __inline__
int addr_bit_set(void *token
, int fn_bit
)
157 return htonl(1 << ((~fn_bit
)&0x1F)) & addr
[fn_bit
>>5];
161 * find the first different bit between two addresses
162 * length of address must be a multiple of 32bits
165 static __inline__
int addr_diff(void *token1
, void *token2
, int addrlen
)
173 for (i
= 0; i
< addrlen
; i
++) {
183 while ((xb
& (1 << j
)) == 0)
186 return (i
* 32 + 31 - j
);
191 * we should *never* get to this point since that
192 * would mean the addrs are equal
194 * However, we do get to it 8) And exacly, when
195 * addresses are equal 8)
197 * ip route add 1111::/128 via ...
198 * ip route add 1111::/64 via ...
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.
210 static __inline__
struct fib6_node
* node_alloc(void)
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
));
220 static __inline__
void node_free(struct fib6_node
* fn
)
222 kmem_cache_free(fib6_node_kmem
, fn
);
225 static __inline__
void rt6_release(struct rt6_info
*rt
)
227 if (atomic_dec_and_test(&rt
->rt6i_ref
))
228 dst_free(&rt
->u
.dst
);
235 * return the appropriate node for a routing tree "add" operation
236 * by either creating and inserting or by returning an existing
240 static struct fib6_node
* fib6_add_1(struct fib6_node
*root
, void *addr
,
241 int addrlen
, int plen
,
244 struct fib6_node
*fn
, *in
, *ln
;
245 struct fib6_node
*pn
= NULL
;
249 __u32 sernum
= fib6_new_sernum();
251 RT6_TRACE("fib6_add_1\n");
253 /* insert node in tree */
258 key
= (struct rt6key
*)((u8
*)fn
->leaf
+ offset
);
263 if (plen
< fn
->fn_bit
||
264 !addr_match(&key
->addr
, addr
, fn
->fn_bit
))
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
);
278 fn
->fn_sernum
= sernum
;
284 * We have more bits to go
287 /* Try to walk down on tree. */
288 fn
->fn_sernum
= sernum
;
289 dir
= addr_bit_set(addr
, fn
->fn_bit
);
291 fn
= dir
? fn
->right
: fn
->left
;
295 * We walked to the bottom of tree.
296 * Create new leaf node without children.
306 ln
->fn_sernum
= sernum
;
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
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.
333 bit
= addr_diff(addr
, &key
->addr
, addrlen
);
338 * (new leaf node)[ln] (old node)[fn]
344 if (in
== NULL
|| ln
== NULL
) {
353 * new intermediate node.
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
364 atomic_inc(&in
->leaf
->rt6i_ref
);
366 in
->fn_sernum
= sernum
;
368 /* update parent pointer */
379 ln
->fn_sernum
= sernum
;
381 if (addr_bit_set(addr
, bit
)) {
388 } else { /* plen <= bit */
391 * (new leaf node)[ln]
393 * (old node)[fn] NULL
405 ln
->fn_sernum
= sernum
;
412 if (addr_bit_set(&key
->addr
, plen
))
423 * Insert routing information in a node.
426 static int fib6_add_rt2node(struct fib6_node
*fn
, struct rt6_info
*rt
,
427 struct nlmsghdr
*nlh
)
429 struct rt6_info
*iter
= NULL
;
430 struct rt6_info
**ins
;
434 if (fn
->fn_flags
&RTN_TL_ROOT
&&
435 fn
->leaf
== &ip6_null_entry
&&
436 !(rt
->rt6i_flags
& (RTF_DEFAULT
| RTF_ADDRCONF
| RTF_ALLONLINK
)) ){
442 for (iter
= fn
->leaf
; iter
; iter
=iter
->u
.next
) {
444 * Search for duplicates
447 if (iter
->rt6i_metric
== rt
->rt6i_metric
) {
449 * Same priority level
452 if (iter
->rt6i_dev
== rt
->rt6i_dev
&&
453 iter
->rt6i_idev
== rt
->rt6i_idev
&&
454 ipv6_addr_cmp(&iter
->rt6i_gateway
,
455 &rt
->rt6i_gateway
) == 0) {
456 if (!(iter
->rt6i_flags
&RTF_EXPIRES
))
458 iter
->rt6i_expires
= rt
->rt6i_expires
;
459 if (!(rt
->rt6i_flags
&RTF_EXPIRES
)) {
460 iter
->rt6i_flags
&= ~RTF_EXPIRES
;
461 iter
->rt6i_expires
= 0;
467 if (iter
->rt6i_metric
> rt
->rt6i_metric
)
481 atomic_inc(&rt
->rt6i_ref
);
482 inet6_rt_notify(RTM_NEWROUTE
, rt
, nlh
);
483 rt6_stats
.fib_rt_entries
++;
485 if ((fn
->fn_flags
& RTN_RTINFO
) == 0) {
486 rt6_stats
.fib_route_nodes
++;
487 fn
->fn_flags
|= RTN_RTINFO
;
493 static __inline__
void fib6_start_gc(struct rt6_info
*rt
)
495 if (ip6_fib_timer
.expires
== 0 &&
496 (rt
->rt6i_flags
& (RTF_EXPIRES
|RTF_CACHE
)))
497 mod_timer(&ip6_fib_timer
, jiffies
+ ip6_rt_gc_interval
);
500 void fib6_force_start_gc(void)
502 if (ip6_fib_timer
.expires
== 0)
503 mod_timer(&ip6_fib_timer
, jiffies
+ ip6_rt_gc_interval
);
507 * Add routing information to the routing tree.
508 * <destination addr>/<source addr>
509 * with source addr info in sub-trees
512 int fib6_add(struct fib6_node
*root
, struct rt6_info
*rt
, struct nlmsghdr
*nlh
, void *_rtattr
)
514 struct fib6_node
*fn
;
517 fn
= fib6_add_1(root
, &rt
->rt6i_dst
.addr
, sizeof(struct in6_addr
),
518 rt
->rt6i_dst
.plen
, offsetof(struct rt6_info
, rt6i_dst
));
523 #ifdef CONFIG_IPV6_SUBTREES
524 if (rt
->rt6i_src
.plen
) {
525 struct fib6_node
*sn
;
527 if (fn
->subtree
== NULL
) {
528 struct fib6_node
*sfn
;
540 /* Create subtree root node */
545 sfn
->leaf
= &ip6_null_entry
;
546 atomic_inc(&ip6_null_entry
.rt6i_ref
);
547 sfn
->fn_flags
= RTN_ROOT
;
548 sfn
->fn_sernum
= fib6_new_sernum();
550 /* Now add the first leaf node to new subtree */
552 sn
= fib6_add_1(sfn
, &rt
->rt6i_src
.addr
,
553 sizeof(struct in6_addr
), rt
->rt6i_src
.plen
,
554 offsetof(struct rt6_info
, rt6i_src
));
557 /* If it is failed, discard just allocated
558 root, and then (in st_failure) stale node
565 /* Now link new subtree to main tree */
568 if (fn
->leaf
== NULL
) {
570 atomic_inc(&rt
->rt6i_ref
);
573 sn
= fib6_add_1(fn
->subtree
, &rt
->rt6i_src
.addr
,
574 sizeof(struct in6_addr
), rt
->rt6i_src
.plen
,
575 offsetof(struct rt6_info
, rt6i_src
));
585 err
= fib6_add_rt2node(fn
, rt
, nlh
);
589 if (!(rt
->rt6i_flags
&RTF_CACHE
))
590 fib6_prune_clones(fn
, rt
);
595 dst_free(&rt
->u
.dst
);
598 #ifdef CONFIG_IPV6_SUBTREES
599 /* Subtree creation failed, probably main tree node
600 is orphan. If it is, shoot it.
603 if (fn
&& !(fn
->fn_flags
& (RTN_RTINFO
|RTN_ROOT
)))
604 fib6_repair_tree(fn
);
605 dst_free(&rt
->u
.dst
);
611 * Routing tree lookup
616 int offset
; /* key offset on rt6_info */
617 struct in6_addr
*addr
; /* search key */
620 static struct fib6_node
* fib6_lookup_1(struct fib6_node
*root
,
621 struct lookup_args
*args
)
623 struct fib6_node
*fn
;
633 struct fib6_node
*next
;
635 dir
= addr_bit_set(args
->addr
, fn
->fn_bit
);
637 next
= dir
? fn
->right
: fn
->left
;
647 while ((fn
->fn_flags
& RTN_ROOT
) == 0) {
648 #ifdef CONFIG_IPV6_SUBTREES
650 struct fib6_node
*st
;
651 struct lookup_args
*narg
;
656 st
= fib6_lookup_1(fn
->subtree
, narg
);
658 if (st
&& !(st
->fn_flags
& RTN_ROOT
))
664 if (fn
->fn_flags
& RTN_RTINFO
) {
667 key
= (struct rt6key
*) ((u8
*) fn
->leaf
+
670 if (addr_match(&key
->addr
, args
->addr
, key
->plen
))
680 struct fib6_node
* fib6_lookup(struct fib6_node
*root
, struct in6_addr
*daddr
,
681 struct in6_addr
*saddr
)
683 struct lookup_args args
[2];
684 struct fib6_node
*fn
;
686 args
[0].offset
= offsetof(struct rt6_info
, rt6i_dst
);
687 args
[0].addr
= daddr
;
689 #ifdef CONFIG_IPV6_SUBTREES
690 args
[1].offset
= offsetof(struct rt6_info
, rt6i_src
);
691 args
[1].addr
= saddr
;
694 fn
= fib6_lookup_1(root
, args
);
696 if (fn
== NULL
|| fn
->fn_flags
& RTN_TL_ROOT
)
703 * Get node with specified destination prefix (and source prefix,
704 * if subtrees are used)
708 static struct fib6_node
* fib6_locate_1(struct fib6_node
*root
,
709 struct in6_addr
*addr
,
710 int plen
, int offset
)
712 struct fib6_node
*fn
;
714 for (fn
= root
; fn
; ) {
715 struct rt6key
*key
= (struct rt6key
*)((u8
*)fn
->leaf
+ offset
);
720 if (plen
< fn
->fn_bit
||
721 !addr_match(&key
->addr
, addr
, fn
->fn_bit
))
724 if (plen
== fn
->fn_bit
)
728 * We have more bits to go
730 if (addr_bit_set(addr
, fn
->fn_bit
))
738 struct fib6_node
* fib6_locate(struct fib6_node
*root
,
739 struct in6_addr
*daddr
, int dst_len
,
740 struct in6_addr
*saddr
, int src_len
)
742 struct fib6_node
*fn
;
744 fn
= fib6_locate_1(root
, daddr
, dst_len
,
745 offsetof(struct rt6_info
, rt6i_dst
));
747 #ifdef CONFIG_IPV6_SUBTREES
749 BUG_TRAP(saddr
!=NULL
);
753 fn
= fib6_locate_1(fn
, saddr
, src_len
,
754 offsetof(struct rt6_info
, rt6i_src
));
758 if (fn
&& fn
->fn_flags
&RTN_RTINFO
)
770 static struct rt6_info
* fib6_find_prefix(struct fib6_node
*fn
)
772 if (fn
->fn_flags
&RTN_ROOT
)
773 return &ip6_null_entry
;
777 return fn
->left
->leaf
;
780 return fn
->right
->leaf
;
788 * Called to trim the tree of intermediate nodes when possible. "fn"
789 * is the node we want to try and remove.
792 static struct fib6_node
* fib6_repair_tree(struct fib6_node
*fn
)
796 struct fib6_node
*child
, *pn
;
797 struct fib6_walker_t
*w
;
801 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn
->fn_bit
, iter
);
804 BUG_TRAP(!(fn
->fn_flags
&RTN_RTINFO
));
805 BUG_TRAP(!(fn
->fn_flags
&RTN_TL_ROOT
));
806 BUG_TRAP(fn
->leaf
==NULL
);
810 if (fn
->right
) child
= fn
->right
, children
|= 1;
811 if (fn
->left
) child
= fn
->left
, children
|= 2;
813 if (children
== 3 || SUBTREE(fn
)
814 #ifdef CONFIG_IPV6_SUBTREES
815 /* Subtree root (i.e. fn) may have one child */
816 || (children
&& fn
->fn_flags
&RTN_ROOT
)
819 fn
->leaf
= fib6_find_prefix(fn
);
821 if (fn
->leaf
==NULL
) {
823 fn
->leaf
= &ip6_null_entry
;
826 atomic_inc(&fn
->leaf
->rt6i_ref
);
831 #ifdef CONFIG_IPV6_SUBTREES
832 if (SUBTREE(pn
) == fn
) {
833 BUG_TRAP(fn
->fn_flags
&RTN_ROOT
);
837 BUG_TRAP(!(fn
->fn_flags
&RTN_ROOT
));
839 if (pn
->right
== fn
) pn
->right
= child
;
840 else if (pn
->left
== fn
) pn
->left
= child
;
847 #ifdef CONFIG_IPV6_SUBTREES
851 read_lock(&fib6_walker_lock
);
855 w
->root
= w
->node
= NULL
;
856 RT6_TRACE("W %p adjusted by delroot 1\n", w
);
857 } else if (w
->node
== fn
) {
858 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w
, w
->state
, nstate
);
865 RT6_TRACE("W %p adjusted by delroot 2\n", w
);
870 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w
, w
->state
);
871 w
->state
= w
->state
>=FWS_R
? FWS_U
: FWS_INIT
;
873 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w
, w
->state
);
874 w
->state
= w
->state
>=FWS_C
? FWS_U
: FWS_INIT
;
879 read_unlock(&fib6_walker_lock
);
882 if (pn
->fn_flags
&RTN_RTINFO
|| SUBTREE(pn
))
885 rt6_release(pn
->leaf
);
891 static void fib6_del_route(struct fib6_node
*fn
, struct rt6_info
**rtp
,
892 struct nlmsghdr
*nlh
, void *_rtattr
)
894 struct fib6_walker_t
*w
;
895 struct rt6_info
*rt
= *rtp
;
897 RT6_TRACE("fib6_del_route\n");
901 rt
->rt6i_node
= NULL
;
902 rt6_stats
.fib_rt_entries
--;
903 rt6_stats
.fib_discarded_routes
++;
906 read_lock(&fib6_walker_lock
);
908 if (w
->state
== FWS_C
&& w
->leaf
== rt
) {
909 RT6_TRACE("walker %p adjusted by delroute\n", w
);
910 w
->leaf
= rt
->u
.next
;
915 read_unlock(&fib6_walker_lock
);
919 if (fn
->leaf
== NULL
&& fn
->fn_flags
&RTN_TL_ROOT
)
920 fn
->leaf
= &ip6_null_entry
;
922 /* If it was last route, expunge its radix tree node */
923 if (fn
->leaf
== NULL
) {
924 fn
->fn_flags
&= ~RTN_RTINFO
;
925 rt6_stats
.fib_route_nodes
--;
926 fn
= fib6_repair_tree(fn
);
929 if (atomic_read(&rt
->rt6i_ref
) != 1) {
930 /* This route is used as dummy address holder in some split
931 * nodes. It is not leaked, but it still holds other resources,
932 * which must be released in time. So, scan ascendant nodes
933 * and replace dummy references to this route with references
934 * to still alive ones.
937 if (!(fn
->fn_flags
&RTN_RTINFO
) && fn
->leaf
== rt
) {
938 fn
->leaf
= fib6_find_prefix(fn
);
939 atomic_inc(&fn
->leaf
->rt6i_ref
);
944 /* No more references are possible at this point. */
945 if (atomic_read(&rt
->rt6i_ref
) != 1) BUG();
948 inet6_rt_notify(RTM_DELROUTE
, rt
, nlh
);
952 int fib6_del(struct rt6_info
*rt
, struct nlmsghdr
*nlh
, void *_rtattr
)
954 struct fib6_node
*fn
= rt
->rt6i_node
;
955 struct rt6_info
**rtp
;
958 if (rt
->u
.dst
.obsolete
>0) {
963 if (fn
== NULL
|| rt
== &ip6_null_entry
)
966 BUG_TRAP(fn
->fn_flags
&RTN_RTINFO
);
968 if (!(rt
->rt6i_flags
&RTF_CACHE
))
969 fib6_prune_clones(fn
, rt
);
972 * Walk the leaf entries looking for ourself
975 for (rtp
= &fn
->leaf
; *rtp
; rtp
= &(*rtp
)->u
.next
) {
977 fib6_del_route(fn
, rtp
, nlh
, _rtattr
);
985 * Tree traversal function.
987 * Certainly, it is not interrupt safe.
988 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
989 * It means, that we can modify tree during walking
990 * and use this function for garbage collection, clone pruning,
991 * cleaning tree when a device goes down etc. etc.
993 * It guarantees that every node will be traversed,
994 * and that it will be traversed only once.
996 * Callback function w->func may return:
997 * 0 -> continue walking.
998 * positive value -> walking is suspended (used by tree dumps,
999 * and probably by gc, if it will be split to several slices)
1000 * negative value -> terminate walking.
1002 * The function itself returns:
1003 * 0 -> walk is complete.
1004 * >0 -> walk is incomplete (i.e. suspended)
1005 * <0 -> walk is terminated by an error.
1008 int fib6_walk_continue(struct fib6_walker_t
*w
)
1010 struct fib6_node
*fn
, *pn
;
1017 if (w
->prune
&& fn
!= w
->root
&&
1018 fn
->fn_flags
&RTN_RTINFO
&& w
->state
< FWS_C
) {
1023 #ifdef CONFIG_IPV6_SUBTREES
1026 w
->node
= SUBTREE(fn
);
1034 w
->state
= FWS_INIT
;
1040 w
->node
= fn
->right
;
1041 w
->state
= FWS_INIT
;
1047 if (w
->leaf
&& fn
->fn_flags
&RTN_RTINFO
) {
1048 int err
= w
->func(w
);
1059 #ifdef CONFIG_IPV6_SUBTREES
1060 if (SUBTREE(pn
) == fn
) {
1061 BUG_TRAP(fn
->fn_flags
&RTN_ROOT
);
1066 if (pn
->left
== fn
) {
1070 if (pn
->right
== fn
) {
1072 w
->leaf
= w
->node
->leaf
;
1082 int fib6_walk(struct fib6_walker_t
*w
)
1086 w
->state
= FWS_INIT
;
1089 fib6_walker_link(w
);
1090 res
= fib6_walk_continue(w
);
1092 fib6_walker_unlink(w
);
1096 static int fib6_clean_node(struct fib6_walker_t
*w
)
1099 struct rt6_info
*rt
;
1100 struct fib6_cleaner_t
*c
= (struct fib6_cleaner_t
*)w
;
1102 for (rt
= w
->leaf
; rt
; rt
= rt
->u
.next
) {
1103 res
= c
->func(rt
, c
->arg
);
1106 res
= fib6_del(rt
, NULL
, NULL
);
1109 printk(KERN_DEBUG
"fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt
, rt
->rt6i_node
, res
);
1122 * Convenient frontend to tree walker.
1124 * func is called on each route.
1125 * It may return -1 -> delete this route.
1126 * 0 -> continue walking
1128 * prune==1 -> only immediate children of node (certainly,
1129 * ignoring pure split nodes) will be scanned.
1132 void fib6_clean_tree(struct fib6_node
*root
,
1133 int (*func
)(struct rt6_info
*, void *arg
),
1134 int prune
, void *arg
)
1136 struct fib6_cleaner_t c
;
1139 c
.w
.func
= fib6_clean_node
;
1147 static int fib6_prune_clone(struct rt6_info
*rt
, void *arg
)
1149 if (rt
->rt6i_flags
& RTF_CACHE
) {
1150 RT6_TRACE("pruning clone %p\n", rt
);
1157 static void fib6_prune_clones(struct fib6_node
*fn
, struct rt6_info
*rt
)
1159 fib6_clean_tree(fn
, fib6_prune_clone
, 1, rt
);
1163 * Garbage collection
1166 static struct fib6_gc_args
1172 static int fib6_age(struct rt6_info
*rt
, void *arg
)
1174 unsigned long now
= jiffies
;
1177 * check addrconf expiration here.
1178 * Routes are expired even if they are in use.
1180 * Also age clones. Note, that clones are aged out
1181 * only if they are not in use now.
1184 if (rt
->rt6i_flags
&RTF_EXPIRES
&& rt
->rt6i_expires
) {
1185 if (time_after(now
, rt
->rt6i_expires
)) {
1186 RT6_TRACE("expiring %p\n", rt
);
1187 rt6_reset_dflt_pointer(rt
);
1191 } else if (rt
->rt6i_flags
& RTF_CACHE
) {
1192 if (atomic_read(&rt
->u
.dst
.__refcnt
) == 0 &&
1193 time_after_eq(now
, rt
->u
.dst
.lastuse
+ gc_args
.timeout
)) {
1194 RT6_TRACE("aging clone %p\n", rt
);
1196 } else if ((rt
->rt6i_flags
& RTF_GATEWAY
) &&
1197 (!(rt
->rt6i_nexthop
->flags
& NTF_ROUTER
))) {
1198 RT6_TRACE("purging route %p via non-router but gateway\n",
1208 static spinlock_t fib6_gc_lock
= SPIN_LOCK_UNLOCKED
;
1210 void fib6_run_gc(unsigned long dummy
)
1212 if (dummy
!= ~0UL) {
1213 spin_lock_bh(&fib6_gc_lock
);
1214 gc_args
.timeout
= (int)dummy
;
1217 if (!spin_trylock(&fib6_gc_lock
)) {
1218 mod_timer(&ip6_fib_timer
, jiffies
+ HZ
);
1222 gc_args
.timeout
= ip6_rt_gc_interval
;
1227 write_lock_bh(&rt6_lock
);
1228 ndisc_dst_gc(&gc_args
.more
);
1229 fib6_clean_tree(&ip6_routing_table
, fib6_age
, 0, NULL
);
1230 write_unlock_bh(&rt6_lock
);
1233 mod_timer(&ip6_fib_timer
, jiffies
+ ip6_rt_gc_interval
);
1235 del_timer(&ip6_fib_timer
);
1236 ip6_fib_timer
.expires
= 0;
1238 spin_unlock_bh(&fib6_gc_lock
);
1241 void __init
fib6_init(void)
1243 fib6_node_kmem
= kmem_cache_create("fib6_nodes",
1244 sizeof(struct fib6_node
),
1245 0, SLAB_HWCACHE_ALIGN
,
1247 if (!fib6_node_kmem
)
1248 panic("cannot create fib6_nodes cache");
1251 void __exit
fib6_gc_cleanup(void)
1253 del_timer(&ip6_fib_timer
);
1254 kmem_cache_destroy(fib6_node_kmem
);