ia64/linux-2.6.18-xen.hg

view net/ipv6/ip6_fib.c @ 673:3161879fdf22

[IA64] xencomm: support XENMEM_add_to_physmap and XENMEM_remove_from_phsymap

support XENMEM_add_to_physmap and XENMEM_remove_from_phsymap.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
author Isaku Yamahata <yamahata@valinux.co.jp>
date Tue Sep 16 21:26:15 2008 +0900 (2008-09-16)
parents 831230e53067
children
line source
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/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>
30 #ifdef CONFIG_PROC_FS
31 #include <linux/proc_fs.h>
32 #endif
34 #include <net/ipv6.h>
35 #include <net/ndisc.h>
36 #include <net/addrconf.h>
38 #include <net/ip6_fib.h>
39 #include <net/ip6_route.h>
41 #define RT6_DEBUG 2
43 #if RT6_DEBUG >= 3
44 #define RT6_TRACE(x...) printk(KERN_DEBUG x)
45 #else
46 #define RT6_TRACE(x...) do { ; } while (0)
47 #endif
49 struct rt6_statistics rt6_stats;
51 static kmem_cache_t * fib6_node_kmem __read_mostly;
53 enum fib_walk_state_t
54 {
55 #ifdef CONFIG_IPV6_SUBTREES
56 FWS_S,
57 #endif
58 FWS_L,
59 FWS_R,
60 FWS_C,
61 FWS_U
62 };
64 struct fib6_cleaner_t
65 {
66 struct fib6_walker_t w;
67 int (*func)(struct rt6_info *, void *arg);
68 void *arg;
69 };
71 DEFINE_RWLOCK(fib6_walker_lock);
74 #ifdef CONFIG_IPV6_SUBTREES
75 #define FWS_INIT FWS_S
76 #define SUBTREE(fn) ((fn)->subtree)
77 #else
78 #define FWS_INIT FWS_L
79 #define SUBTREE(fn) NULL
80 #endif
82 static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt);
83 static struct fib6_node * fib6_repair_tree(struct fib6_node *fn);
85 /*
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.
90 */
92 static __u32 rt_sernum;
94 static DEFINE_TIMER(ip6_fib_timer, fib6_run_gc, 0, 0);
96 struct fib6_walker_t fib6_walker_list = {
97 .prev = &fib6_walker_list,
98 .next = &fib6_walker_list,
99 };
101 #define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)
103 static __inline__ u32 fib6_new_sernum(void)
104 {
105 u32 n = ++rt_sernum;
106 if ((__s32)n <= 0)
107 rt_sernum = n = 1;
108 return n;
109 }
111 /*
112 * Auxiliary address test functions for the radix tree.
113 *
114 * These assume a 32bit processor (although it will work on
115 * 64bit processors)
116 */
118 /*
119 * test bit
120 */
122 static __inline__ int addr_bit_set(void *token, int fn_bit)
123 {
124 __u32 *addr = token;
126 return htonl(1 << ((~fn_bit)&0x1F)) & addr[fn_bit>>5];
127 }
129 static __inline__ struct fib6_node * node_alloc(void)
130 {
131 struct fib6_node *fn;
133 if ((fn = kmem_cache_alloc(fib6_node_kmem, SLAB_ATOMIC)) != NULL)
134 memset(fn, 0, sizeof(struct fib6_node));
136 return fn;
137 }
139 static __inline__ void node_free(struct fib6_node * fn)
140 {
141 kmem_cache_free(fib6_node_kmem, fn);
142 }
144 static __inline__ void rt6_release(struct rt6_info *rt)
145 {
146 if (atomic_dec_and_test(&rt->rt6i_ref))
147 dst_free(&rt->u.dst);
148 }
151 /*
152 * Routing Table
153 *
154 * return the appropriate node for a routing tree "add" operation
155 * by either creating and inserting or by returning an existing
156 * node.
157 */
159 static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
160 int addrlen, int plen,
161 int offset)
162 {
163 struct fib6_node *fn, *in, *ln;
164 struct fib6_node *pn = NULL;
165 struct rt6key *key;
166 int bit;
167 int dir = 0;
168 __u32 sernum = fib6_new_sernum();
170 RT6_TRACE("fib6_add_1\n");
172 /* insert node in tree */
174 fn = root;
176 do {
177 key = (struct rt6key *)((u8 *)fn->leaf + offset);
179 /*
180 * Prefix match
181 */
182 if (plen < fn->fn_bit ||
183 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
184 goto insert_above;
186 /*
187 * Exact match ?
188 */
190 if (plen == fn->fn_bit) {
191 /* clean up an intermediate node */
192 if ((fn->fn_flags & RTN_RTINFO) == 0) {
193 rt6_release(fn->leaf);
194 fn->leaf = NULL;
195 }
197 fn->fn_sernum = sernum;
199 return fn;
200 }
202 /*
203 * We have more bits to go
204 */
206 /* Try to walk down on tree. */
207 fn->fn_sernum = sernum;
208 dir = addr_bit_set(addr, fn->fn_bit);
209 pn = fn;
210 fn = dir ? fn->right: fn->left;
211 } while (fn);
213 /*
214 * We walked to the bottom of tree.
215 * Create new leaf node without children.
216 */
218 ln = node_alloc();
220 if (ln == NULL)
221 return NULL;
222 ln->fn_bit = plen;
224 ln->parent = pn;
225 ln->fn_sernum = sernum;
227 if (dir)
228 pn->right = ln;
229 else
230 pn->left = ln;
232 return ln;
235 insert_above:
236 /*
237 * split since we don't have a common prefix anymore or
238 * we have a less significant route.
239 * we've to insert an intermediate node on the list
240 * this new node will point to the one we need to create
241 * and the current
242 */
244 pn = fn->parent;
246 /* find 1st bit in difference between the 2 addrs.
248 See comment in __ipv6_addr_diff: bit may be an invalid value,
249 but if it is >= plen, the value is ignored in any case.
250 */
252 bit = __ipv6_addr_diff(addr, &key->addr, addrlen);
254 /*
255 * (intermediate)[in]
256 * / \
257 * (new leaf node)[ln] (old node)[fn]
258 */
259 if (plen > bit) {
260 in = node_alloc();
261 ln = node_alloc();
263 if (in == NULL || ln == NULL) {
264 if (in)
265 node_free(in);
266 if (ln)
267 node_free(ln);
268 return NULL;
269 }
271 /*
272 * new intermediate node.
273 * RTN_RTINFO will
274 * be off since that an address that chooses one of
275 * the branches would not match less specific routes
276 * in the other branch
277 */
279 in->fn_bit = bit;
281 in->parent = pn;
282 in->leaf = fn->leaf;
283 atomic_inc(&in->leaf->rt6i_ref);
285 in->fn_sernum = sernum;
287 /* update parent pointer */
288 if (dir)
289 pn->right = in;
290 else
291 pn->left = in;
293 ln->fn_bit = plen;
295 ln->parent = in;
296 fn->parent = in;
298 ln->fn_sernum = sernum;
300 if (addr_bit_set(addr, bit)) {
301 in->right = ln;
302 in->left = fn;
303 } else {
304 in->left = ln;
305 in->right = fn;
306 }
307 } else { /* plen <= bit */
309 /*
310 * (new leaf node)[ln]
311 * / \
312 * (old node)[fn] NULL
313 */
315 ln = node_alloc();
317 if (ln == NULL)
318 return NULL;
320 ln->fn_bit = plen;
322 ln->parent = pn;
324 ln->fn_sernum = sernum;
326 if (dir)
327 pn->right = ln;
328 else
329 pn->left = ln;
331 if (addr_bit_set(&key->addr, plen))
332 ln->right = fn;
333 else
334 ln->left = fn;
336 fn->parent = ln;
337 }
338 return ln;
339 }
341 /*
342 * Insert routing information in a node.
343 */
345 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
346 struct nlmsghdr *nlh, struct netlink_skb_parms *req)
347 {
348 struct rt6_info *iter = NULL;
349 struct rt6_info **ins;
351 ins = &fn->leaf;
353 if (fn->fn_flags&RTN_TL_ROOT &&
354 fn->leaf == &ip6_null_entry &&
355 !(rt->rt6i_flags & (RTF_DEFAULT | RTF_ADDRCONF)) ){
356 fn->leaf = rt;
357 rt->u.next = NULL;
358 goto out;
359 }
361 for (iter = fn->leaf; iter; iter=iter->u.next) {
362 /*
363 * Search for duplicates
364 */
366 if (iter->rt6i_metric == rt->rt6i_metric) {
367 /*
368 * Same priority level
369 */
371 if (iter->rt6i_dev == rt->rt6i_dev &&
372 iter->rt6i_idev == rt->rt6i_idev &&
373 ipv6_addr_equal(&iter->rt6i_gateway,
374 &rt->rt6i_gateway)) {
375 if (!(iter->rt6i_flags&RTF_EXPIRES))
376 return -EEXIST;
377 iter->rt6i_expires = rt->rt6i_expires;
378 if (!(rt->rt6i_flags&RTF_EXPIRES)) {
379 iter->rt6i_flags &= ~RTF_EXPIRES;
380 iter->rt6i_expires = 0;
381 }
382 return -EEXIST;
383 }
384 }
386 if (iter->rt6i_metric > rt->rt6i_metric)
387 break;
389 ins = &iter->u.next;
390 }
392 /*
393 * insert node
394 */
396 out:
397 rt->u.next = iter;
398 *ins = rt;
399 rt->rt6i_node = fn;
400 atomic_inc(&rt->rt6i_ref);
401 inet6_rt_notify(RTM_NEWROUTE, rt, nlh, req);
402 rt6_stats.fib_rt_entries++;
404 if ((fn->fn_flags & RTN_RTINFO) == 0) {
405 rt6_stats.fib_route_nodes++;
406 fn->fn_flags |= RTN_RTINFO;
407 }
409 return 0;
410 }
412 static __inline__ void fib6_start_gc(struct rt6_info *rt)
413 {
414 if (ip6_fib_timer.expires == 0 &&
415 (rt->rt6i_flags & (RTF_EXPIRES|RTF_CACHE)))
416 mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
417 }
419 void fib6_force_start_gc(void)
420 {
421 if (ip6_fib_timer.expires == 0)
422 mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
423 }
425 /*
426 * Add routing information to the routing tree.
427 * <destination addr>/<source addr>
428 * with source addr info in sub-trees
429 */
431 int fib6_add(struct fib6_node *root, struct rt6_info *rt,
432 struct nlmsghdr *nlh, void *_rtattr, struct netlink_skb_parms *req)
433 {
434 struct fib6_node *fn;
435 int err = -ENOMEM;
437 fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
438 rt->rt6i_dst.plen, offsetof(struct rt6_info, rt6i_dst));
440 if (fn == NULL)
441 goto out;
443 #ifdef CONFIG_IPV6_SUBTREES
444 if (rt->rt6i_src.plen) {
445 struct fib6_node *sn;
447 if (fn->subtree == NULL) {
448 struct fib6_node *sfn;
450 /*
451 * Create subtree.
452 *
453 * fn[main tree]
454 * |
455 * sfn[subtree root]
456 * \
457 * sn[new leaf node]
458 */
460 /* Create subtree root node */
461 sfn = node_alloc();
462 if (sfn == NULL)
463 goto st_failure;
465 sfn->leaf = &ip6_null_entry;
466 atomic_inc(&ip6_null_entry.rt6i_ref);
467 sfn->fn_flags = RTN_ROOT;
468 sfn->fn_sernum = fib6_new_sernum();
470 /* Now add the first leaf node to new subtree */
472 sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
473 sizeof(struct in6_addr), rt->rt6i_src.plen,
474 offsetof(struct rt6_info, rt6i_src));
476 if (sn == NULL) {
477 /* If it is failed, discard just allocated
478 root, and then (in st_failure) stale node
479 in main tree.
480 */
481 node_free(sfn);
482 goto st_failure;
483 }
485 /* Now link new subtree to main tree */
486 sfn->parent = fn;
487 fn->subtree = sfn;
488 if (fn->leaf == NULL) {
489 fn->leaf = rt;
490 atomic_inc(&rt->rt6i_ref);
491 }
492 } else {
493 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
494 sizeof(struct in6_addr), rt->rt6i_src.plen,
495 offsetof(struct rt6_info, rt6i_src));
497 if (sn == NULL)
498 goto st_failure;
499 }
501 fn = sn;
502 }
503 #endif
505 err = fib6_add_rt2node(fn, rt, nlh, req);
507 if (err == 0) {
508 fib6_start_gc(rt);
509 if (!(rt->rt6i_flags&RTF_CACHE))
510 fib6_prune_clones(fn, rt);
511 }
513 out:
514 if (err)
515 dst_free(&rt->u.dst);
516 return err;
518 #ifdef CONFIG_IPV6_SUBTREES
519 /* Subtree creation failed, probably main tree node
520 is orphan. If it is, shoot it.
521 */
522 st_failure:
523 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
524 fib6_repair_tree(fn);
525 dst_free(&rt->u.dst);
526 return err;
527 #endif
528 }
530 /*
531 * Routing tree lookup
532 *
533 */
535 struct lookup_args {
536 int offset; /* key offset on rt6_info */
537 struct in6_addr *addr; /* search key */
538 };
540 static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
541 struct lookup_args *args)
542 {
543 struct fib6_node *fn;
544 int dir;
546 /*
547 * Descend on a tree
548 */
550 fn = root;
552 for (;;) {
553 struct fib6_node *next;
555 dir = addr_bit_set(args->addr, fn->fn_bit);
557 next = dir ? fn->right : fn->left;
559 if (next) {
560 fn = next;
561 continue;
562 }
564 break;
565 }
567 while ((fn->fn_flags & RTN_ROOT) == 0) {
568 #ifdef CONFIG_IPV6_SUBTREES
569 if (fn->subtree) {
570 struct fib6_node *st;
571 struct lookup_args *narg;
573 narg = args + 1;
575 if (narg->addr) {
576 st = fib6_lookup_1(fn->subtree, narg);
578 if (st && !(st->fn_flags & RTN_ROOT))
579 return st;
580 }
581 }
582 #endif
584 if (fn->fn_flags & RTN_RTINFO) {
585 struct rt6key *key;
587 key = (struct rt6key *) ((u8 *) fn->leaf +
588 args->offset);
590 if (ipv6_prefix_equal(&key->addr, args->addr, key->plen))
591 return fn;
592 }
594 fn = fn->parent;
595 }
597 return NULL;
598 }
600 struct fib6_node * fib6_lookup(struct fib6_node *root, struct in6_addr *daddr,
601 struct in6_addr *saddr)
602 {
603 struct lookup_args args[2];
604 struct fib6_node *fn;
606 args[0].offset = offsetof(struct rt6_info, rt6i_dst);
607 args[0].addr = daddr;
609 #ifdef CONFIG_IPV6_SUBTREES
610 args[1].offset = offsetof(struct rt6_info, rt6i_src);
611 args[1].addr = saddr;
612 #endif
614 fn = fib6_lookup_1(root, args);
616 if (fn == NULL || fn->fn_flags & RTN_TL_ROOT)
617 fn = root;
619 return fn;
620 }
622 /*
623 * Get node with specified destination prefix (and source prefix,
624 * if subtrees are used)
625 */
628 static struct fib6_node * fib6_locate_1(struct fib6_node *root,
629 struct in6_addr *addr,
630 int plen, int offset)
631 {
632 struct fib6_node *fn;
634 for (fn = root; fn ; ) {
635 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
637 /*
638 * Prefix match
639 */
640 if (plen < fn->fn_bit ||
641 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
642 return NULL;
644 if (plen == fn->fn_bit)
645 return fn;
647 /*
648 * We have more bits to go
649 */
650 if (addr_bit_set(addr, fn->fn_bit))
651 fn = fn->right;
652 else
653 fn = fn->left;
654 }
655 return NULL;
656 }
658 struct fib6_node * fib6_locate(struct fib6_node *root,
659 struct in6_addr *daddr, int dst_len,
660 struct in6_addr *saddr, int src_len)
661 {
662 struct fib6_node *fn;
664 fn = fib6_locate_1(root, daddr, dst_len,
665 offsetof(struct rt6_info, rt6i_dst));
667 #ifdef CONFIG_IPV6_SUBTREES
668 if (src_len) {
669 BUG_TRAP(saddr!=NULL);
670 if (fn == NULL)
671 fn = fn->subtree;
672 if (fn)
673 fn = fib6_locate_1(fn, saddr, src_len,
674 offsetof(struct rt6_info, rt6i_src));
675 }
676 #endif
678 if (fn && fn->fn_flags&RTN_RTINFO)
679 return fn;
681 return NULL;
682 }
685 /*
686 * Deletion
687 *
688 */
690 static struct rt6_info * fib6_find_prefix(struct fib6_node *fn)
691 {
692 if (fn->fn_flags&RTN_ROOT)
693 return &ip6_null_entry;
695 while(fn) {
696 if(fn->left)
697 return fn->left->leaf;
699 if(fn->right)
700 return fn->right->leaf;
702 fn = SUBTREE(fn);
703 }
704 return NULL;
705 }
707 /*
708 * Called to trim the tree of intermediate nodes when possible. "fn"
709 * is the node we want to try and remove.
710 */
712 static struct fib6_node * fib6_repair_tree(struct fib6_node *fn)
713 {
714 int children;
715 int nstate;
716 struct fib6_node *child, *pn;
717 struct fib6_walker_t *w;
718 int iter = 0;
720 for (;;) {
721 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
722 iter++;
724 BUG_TRAP(!(fn->fn_flags&RTN_RTINFO));
725 BUG_TRAP(!(fn->fn_flags&RTN_TL_ROOT));
726 BUG_TRAP(fn->leaf==NULL);
728 children = 0;
729 child = NULL;
730 if (fn->right) child = fn->right, children |= 1;
731 if (fn->left) child = fn->left, children |= 2;
733 if (children == 3 || SUBTREE(fn)
734 #ifdef CONFIG_IPV6_SUBTREES
735 /* Subtree root (i.e. fn) may have one child */
736 || (children && fn->fn_flags&RTN_ROOT)
737 #endif
738 ) {
739 fn->leaf = fib6_find_prefix(fn);
740 #if RT6_DEBUG >= 2
741 if (fn->leaf==NULL) {
742 BUG_TRAP(fn->leaf);
743 fn->leaf = &ip6_null_entry;
744 }
745 #endif
746 atomic_inc(&fn->leaf->rt6i_ref);
747 return fn->parent;
748 }
750 pn = fn->parent;
751 #ifdef CONFIG_IPV6_SUBTREES
752 if (SUBTREE(pn) == fn) {
753 BUG_TRAP(fn->fn_flags&RTN_ROOT);
754 SUBTREE(pn) = NULL;
755 nstate = FWS_L;
756 } else {
757 BUG_TRAP(!(fn->fn_flags&RTN_ROOT));
758 #endif
759 if (pn->right == fn) pn->right = child;
760 else if (pn->left == fn) pn->left = child;
761 #if RT6_DEBUG >= 2
762 else BUG_TRAP(0);
763 #endif
764 if (child)
765 child->parent = pn;
766 nstate = FWS_R;
767 #ifdef CONFIG_IPV6_SUBTREES
768 }
769 #endif
771 read_lock(&fib6_walker_lock);
772 FOR_WALKERS(w) {
773 if (child == NULL) {
774 if (w->root == fn) {
775 w->root = w->node = NULL;
776 RT6_TRACE("W %p adjusted by delroot 1\n", w);
777 } else if (w->node == fn) {
778 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
779 w->node = pn;
780 w->state = nstate;
781 }
782 } else {
783 if (w->root == fn) {
784 w->root = child;
785 RT6_TRACE("W %p adjusted by delroot 2\n", w);
786 }
787 if (w->node == fn) {
788 w->node = child;
789 if (children&2) {
790 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
791 w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
792 } else {
793 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
794 w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
795 }
796 }
797 }
798 }
799 read_unlock(&fib6_walker_lock);
801 node_free(fn);
802 if (pn->fn_flags&RTN_RTINFO || SUBTREE(pn))
803 return pn;
805 rt6_release(pn->leaf);
806 pn->leaf = NULL;
807 fn = pn;
808 }
809 }
811 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
812 struct nlmsghdr *nlh, void *_rtattr, struct netlink_skb_parms *req)
813 {
814 struct fib6_walker_t *w;
815 struct rt6_info *rt = *rtp;
817 RT6_TRACE("fib6_del_route\n");
819 /* Unlink it */
820 *rtp = rt->u.next;
821 rt->rt6i_node = NULL;
822 rt6_stats.fib_rt_entries--;
823 rt6_stats.fib_discarded_routes++;
825 /* Adjust walkers */
826 read_lock(&fib6_walker_lock);
827 FOR_WALKERS(w) {
828 if (w->state == FWS_C && w->leaf == rt) {
829 RT6_TRACE("walker %p adjusted by delroute\n", w);
830 w->leaf = rt->u.next;
831 if (w->leaf == NULL)
832 w->state = FWS_U;
833 }
834 }
835 read_unlock(&fib6_walker_lock);
837 rt->u.next = NULL;
839 if (fn->leaf == NULL && fn->fn_flags&RTN_TL_ROOT)
840 fn->leaf = &ip6_null_entry;
842 /* If it was last route, expunge its radix tree node */
843 if (fn->leaf == NULL) {
844 fn->fn_flags &= ~RTN_RTINFO;
845 rt6_stats.fib_route_nodes--;
846 fn = fib6_repair_tree(fn);
847 }
849 if (atomic_read(&rt->rt6i_ref) != 1) {
850 /* This route is used as dummy address holder in some split
851 * nodes. It is not leaked, but it still holds other resources,
852 * which must be released in time. So, scan ascendant nodes
853 * and replace dummy references to this route with references
854 * to still alive ones.
855 */
856 while (fn) {
857 if (!(fn->fn_flags&RTN_RTINFO) && fn->leaf == rt) {
858 fn->leaf = fib6_find_prefix(fn);
859 atomic_inc(&fn->leaf->rt6i_ref);
860 rt6_release(rt);
861 }
862 fn = fn->parent;
863 }
864 /* No more references are possible at this point. */
865 if (atomic_read(&rt->rt6i_ref) != 1) BUG();
866 }
868 inet6_rt_notify(RTM_DELROUTE, rt, nlh, req);
869 rt6_release(rt);
870 }
872 int fib6_del(struct rt6_info *rt, struct nlmsghdr *nlh, void *_rtattr, struct netlink_skb_parms *req)
873 {
874 struct fib6_node *fn = rt->rt6i_node;
875 struct rt6_info **rtp;
877 #if RT6_DEBUG >= 2
878 if (rt->u.dst.obsolete>0) {
879 BUG_TRAP(fn==NULL);
880 return -ENOENT;
881 }
882 #endif
883 if (fn == NULL || rt == &ip6_null_entry)
884 return -ENOENT;
886 BUG_TRAP(fn->fn_flags&RTN_RTINFO);
888 if (!(rt->rt6i_flags&RTF_CACHE))
889 fib6_prune_clones(fn, rt);
891 /*
892 * Walk the leaf entries looking for ourself
893 */
895 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.next) {
896 if (*rtp == rt) {
897 fib6_del_route(fn, rtp, nlh, _rtattr, req);
898 return 0;
899 }
900 }
901 return -ENOENT;
902 }
904 /*
905 * Tree traversal function.
906 *
907 * Certainly, it is not interrupt safe.
908 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
909 * It means, that we can modify tree during walking
910 * and use this function for garbage collection, clone pruning,
911 * cleaning tree when a device goes down etc. etc.
912 *
913 * It guarantees that every node will be traversed,
914 * and that it will be traversed only once.
915 *
916 * Callback function w->func may return:
917 * 0 -> continue walking.
918 * positive value -> walking is suspended (used by tree dumps,
919 * and probably by gc, if it will be split to several slices)
920 * negative value -> terminate walking.
921 *
922 * The function itself returns:
923 * 0 -> walk is complete.
924 * >0 -> walk is incomplete (i.e. suspended)
925 * <0 -> walk is terminated by an error.
926 */
928 int fib6_walk_continue(struct fib6_walker_t *w)
929 {
930 struct fib6_node *fn, *pn;
932 for (;;) {
933 fn = w->node;
934 if (fn == NULL)
935 return 0;
937 if (w->prune && fn != w->root &&
938 fn->fn_flags&RTN_RTINFO && w->state < FWS_C) {
939 w->state = FWS_C;
940 w->leaf = fn->leaf;
941 }
942 switch (w->state) {
943 #ifdef CONFIG_IPV6_SUBTREES
944 case FWS_S:
945 if (SUBTREE(fn)) {
946 w->node = SUBTREE(fn);
947 continue;
948 }
949 w->state = FWS_L;
950 #endif
951 case FWS_L:
952 if (fn->left) {
953 w->node = fn->left;
954 w->state = FWS_INIT;
955 continue;
956 }
957 w->state = FWS_R;
958 case FWS_R:
959 if (fn->right) {
960 w->node = fn->right;
961 w->state = FWS_INIT;
962 continue;
963 }
964 w->state = FWS_C;
965 w->leaf = fn->leaf;
966 case FWS_C:
967 if (w->leaf && fn->fn_flags&RTN_RTINFO) {
968 int err = w->func(w);
969 if (err)
970 return err;
971 continue;
972 }
973 w->state = FWS_U;
974 case FWS_U:
975 if (fn == w->root)
976 return 0;
977 pn = fn->parent;
978 w->node = pn;
979 #ifdef CONFIG_IPV6_SUBTREES
980 if (SUBTREE(pn) == fn) {
981 BUG_TRAP(fn->fn_flags&RTN_ROOT);
982 w->state = FWS_L;
983 continue;
984 }
985 #endif
986 if (pn->left == fn) {
987 w->state = FWS_R;
988 continue;
989 }
990 if (pn->right == fn) {
991 w->state = FWS_C;
992 w->leaf = w->node->leaf;
993 continue;
994 }
995 #if RT6_DEBUG >= 2
996 BUG_TRAP(0);
997 #endif
998 }
999 }
1002 int fib6_walk(struct fib6_walker_t *w)
1004 int res;
1006 w->state = FWS_INIT;
1007 w->node = w->root;
1009 fib6_walker_link(w);
1010 res = fib6_walk_continue(w);
1011 if (res <= 0)
1012 fib6_walker_unlink(w);
1013 return res;
1016 static int fib6_clean_node(struct fib6_walker_t *w)
1018 int res;
1019 struct rt6_info *rt;
1020 struct fib6_cleaner_t *c = (struct fib6_cleaner_t*)w;
1022 for (rt = w->leaf; rt; rt = rt->u.next) {
1023 res = c->func(rt, c->arg);
1024 if (res < 0) {
1025 w->leaf = rt;
1026 res = fib6_del(rt, NULL, NULL, NULL);
1027 if (res) {
1028 #if RT6_DEBUG >= 2
1029 printk(KERN_DEBUG "fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt, rt->rt6i_node, res);
1030 #endif
1031 continue;
1033 return 0;
1035 BUG_TRAP(res==0);
1037 w->leaf = rt;
1038 return 0;
1041 /*
1042 * Convenient frontend to tree walker.
1044 * func is called on each route.
1045 * It may return -1 -> delete this route.
1046 * 0 -> continue walking
1048 * prune==1 -> only immediate children of node (certainly,
1049 * ignoring pure split nodes) will be scanned.
1050 */
1052 void fib6_clean_tree(struct fib6_node *root,
1053 int (*func)(struct rt6_info *, void *arg),
1054 int prune, void *arg)
1056 struct fib6_cleaner_t c;
1058 c.w.root = root;
1059 c.w.func = fib6_clean_node;
1060 c.w.prune = prune;
1061 c.func = func;
1062 c.arg = arg;
1064 fib6_walk(&c.w);
1067 static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1069 if (rt->rt6i_flags & RTF_CACHE) {
1070 RT6_TRACE("pruning clone %p\n", rt);
1071 return -1;
1074 return 0;
1077 static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt)
1079 fib6_clean_tree(fn, fib6_prune_clone, 1, rt);
1082 /*
1083 * Garbage collection
1084 */
1086 static struct fib6_gc_args
1088 int timeout;
1089 int more;
1090 } gc_args;
1092 static int fib6_age(struct rt6_info *rt, void *arg)
1094 unsigned long now = jiffies;
1096 /*
1097 * check addrconf expiration here.
1098 * Routes are expired even if they are in use.
1100 * Also age clones. Note, that clones are aged out
1101 * only if they are not in use now.
1102 */
1104 if (rt->rt6i_flags&RTF_EXPIRES && rt->rt6i_expires) {
1105 if (time_after(now, rt->rt6i_expires)) {
1106 RT6_TRACE("expiring %p\n", rt);
1107 return -1;
1109 gc_args.more++;
1110 } else if (rt->rt6i_flags & RTF_CACHE) {
1111 if (atomic_read(&rt->u.dst.__refcnt) == 0 &&
1112 time_after_eq(now, rt->u.dst.lastuse + gc_args.timeout)) {
1113 RT6_TRACE("aging clone %p\n", rt);
1114 return -1;
1115 } else if ((rt->rt6i_flags & RTF_GATEWAY) &&
1116 (!(rt->rt6i_nexthop->flags & NTF_ROUTER))) {
1117 RT6_TRACE("purging route %p via non-router but gateway\n",
1118 rt);
1119 return -1;
1121 gc_args.more++;
1124 return 0;
1127 static DEFINE_SPINLOCK(fib6_gc_lock);
1129 void fib6_run_gc(unsigned long dummy)
1131 if (dummy != ~0UL) {
1132 spin_lock_bh(&fib6_gc_lock);
1133 gc_args.timeout = dummy ? (int)dummy : ip6_rt_gc_interval;
1134 } else {
1135 local_bh_disable();
1136 if (!spin_trylock(&fib6_gc_lock)) {
1137 mod_timer(&ip6_fib_timer, jiffies + HZ);
1138 local_bh_enable();
1139 return;
1141 gc_args.timeout = ip6_rt_gc_interval;
1143 gc_args.more = 0;
1146 write_lock_bh(&rt6_lock);
1147 ndisc_dst_gc(&gc_args.more);
1148 fib6_clean_tree(&ip6_routing_table, fib6_age, 0, NULL);
1149 write_unlock_bh(&rt6_lock);
1151 if (gc_args.more)
1152 mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
1153 else {
1154 del_timer(&ip6_fib_timer);
1155 ip6_fib_timer.expires = 0;
1157 spin_unlock_bh(&fib6_gc_lock);
1160 void __init fib6_init(void)
1162 fib6_node_kmem = kmem_cache_create("fib6_nodes",
1163 sizeof(struct fib6_node),
1164 0, SLAB_HWCACHE_ALIGN,
1165 NULL, NULL);
1166 if (!fib6_node_kmem)
1167 panic("cannot create fib6_nodes cache");
1170 void fib6_gc_cleanup(void)
1172 del_timer(&ip6_fib_timer);
1173 kmem_cache_destroy(fib6_node_kmem);