xref: /linux/net/ipv6/ip6_fib.c (revision 4413e16d9d21673bb5048a2e542f1aaa00015c2e)
1 /*
2  *	Linux INET6 implementation
3  *	Forwarding Information Database
4  *
5  *	Authors:
6  *	Pedro Roque		<roque@di.fc.ul.pt>
7  *
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.
12  */
13 
14 /*
15  * 	Changes:
16  * 	Yuji SEKIYA @USAGI:	Support default route on router node;
17  * 				remove ip6_null_entry from the top of
18  * 				routing table.
19  * 	Ville Nuorvala:		Fixed routing subtrees.
20  */
21 
22 #define pr_fmt(fmt) "IPv6: " fmt
23 
24 #include <linux/errno.h>
25 #include <linux/types.h>
26 #include <linux/net.h>
27 #include <linux/route.h>
28 #include <linux/netdevice.h>
29 #include <linux/in6.h>
30 #include <linux/init.h>
31 #include <linux/list.h>
32 #include <linux/slab.h>
33 
34 #include <net/ipv6.h>
35 #include <net/ndisc.h>
36 #include <net/addrconf.h>
37 
38 #include <net/ip6_fib.h>
39 #include <net/ip6_route.h>
40 
41 #define RT6_DEBUG 2
42 
43 #if RT6_DEBUG >= 3
44 #define RT6_TRACE(x...) pr_debug(x)
45 #else
46 #define RT6_TRACE(x...) do { ; } while (0)
47 #endif
48 
49 static struct kmem_cache * fib6_node_kmem __read_mostly;
50 
51 enum fib_walk_state_t
52 {
53 #ifdef CONFIG_IPV6_SUBTREES
54 	FWS_S,
55 #endif
56 	FWS_L,
57 	FWS_R,
58 	FWS_C,
59 	FWS_U
60 };
61 
62 struct fib6_cleaner_t
63 {
64 	struct fib6_walker_t w;
65 	struct net *net;
66 	int (*func)(struct rt6_info *, void *arg);
67 	void *arg;
68 };
69 
70 static DEFINE_RWLOCK(fib6_walker_lock);
71 
72 #ifdef CONFIG_IPV6_SUBTREES
73 #define FWS_INIT FWS_S
74 #else
75 #define FWS_INIT FWS_L
76 #endif
77 
78 static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
79 			      struct rt6_info *rt);
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);
84 
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  */
91 
92 static __u32 rt_sernum;
93 
94 static void fib6_gc_timer_cb(unsigned long arg);
95 
96 static LIST_HEAD(fib6_walkers);
97 #define FOR_WALKERS(w) list_for_each_entry(w, &fib6_walkers, lh)
98 
99 static inline void fib6_walker_link(struct fib6_walker_t *w)
100 {
101 	write_lock_bh(&fib6_walker_lock);
102 	list_add(&w->lh, &fib6_walkers);
103 	write_unlock_bh(&fib6_walker_lock);
104 }
105 
106 static inline void fib6_walker_unlink(struct fib6_walker_t *w)
107 {
108 	write_lock_bh(&fib6_walker_lock);
109 	list_del(&w->lh);
110 	write_unlock_bh(&fib6_walker_lock);
111 }
112 static __inline__ u32 fib6_new_sernum(void)
113 {
114 	u32 n = ++rt_sernum;
115 	if ((__s32)n <= 0)
116 		rt_sernum = n = 1;
117 	return n;
118 }
119 
120 /*
121  *	Auxiliary address test functions for the radix tree.
122  *
123  *	These assume a 32bit processor (although it will work on
124  *	64bit processors)
125  */
126 
127 /*
128  *	test bit
129  */
130 #if defined(__LITTLE_ENDIAN)
131 # define BITOP_BE32_SWIZZLE	(0x1F & ~7)
132 #else
133 # define BITOP_BE32_SWIZZLE	0
134 #endif
135 
136 static __inline__ __be32 addr_bit_set(const void *token, int fn_bit)
137 {
138 	const __be32 *addr = token;
139 	/*
140 	 * Here,
141 	 * 	1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
142 	 * is optimized version of
143 	 *	htonl(1 << ((~fn_bit)&0x1F))
144 	 * See include/asm-generic/bitops/le.h.
145 	 */
146 	return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
147 	       addr[fn_bit >> 5];
148 }
149 
150 static __inline__ struct fib6_node * node_alloc(void)
151 {
152 	struct fib6_node *fn;
153 
154 	fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
155 
156 	return fn;
157 }
158 
159 static __inline__ void node_free(struct fib6_node * fn)
160 {
161 	kmem_cache_free(fib6_node_kmem, fn);
162 }
163 
164 static __inline__ void rt6_release(struct rt6_info *rt)
165 {
166 	if (atomic_dec_and_test(&rt->rt6i_ref))
167 		dst_free(&rt->dst);
168 }
169 
170 static void fib6_link_table(struct net *net, struct fib6_table *tb)
171 {
172 	unsigned int h;
173 
174 	/*
175 	 * Initialize table lock at a single place to give lockdep a key,
176 	 * tables aren't visible prior to being linked to the list.
177 	 */
178 	rwlock_init(&tb->tb6_lock);
179 
180 	h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
181 
182 	/*
183 	 * No protection necessary, this is the only list mutatation
184 	 * operation, tables never disappear once they exist.
185 	 */
186 	hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
187 }
188 
189 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
190 
191 static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
192 {
193 	struct fib6_table *table;
194 
195 	table = kzalloc(sizeof(*table), GFP_ATOMIC);
196 	if (table) {
197 		table->tb6_id = id;
198 		table->tb6_root.leaf = net->ipv6.ip6_null_entry;
199 		table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
200 		inet_peer_base_init(&table->tb6_peers);
201 	}
202 
203 	return table;
204 }
205 
206 struct fib6_table *fib6_new_table(struct net *net, u32 id)
207 {
208 	struct fib6_table *tb;
209 
210 	if (id == 0)
211 		id = RT6_TABLE_MAIN;
212 	tb = fib6_get_table(net, id);
213 	if (tb)
214 		return tb;
215 
216 	tb = fib6_alloc_table(net, id);
217 	if (tb)
218 		fib6_link_table(net, tb);
219 
220 	return tb;
221 }
222 
223 struct fib6_table *fib6_get_table(struct net *net, u32 id)
224 {
225 	struct fib6_table *tb;
226 	struct hlist_head *head;
227 	struct hlist_node *node;
228 	unsigned int h;
229 
230 	if (id == 0)
231 		id = RT6_TABLE_MAIN;
232 	h = id & (FIB6_TABLE_HASHSZ - 1);
233 	rcu_read_lock();
234 	head = &net->ipv6.fib_table_hash[h];
235 	hlist_for_each_entry_rcu(tb, node, head, tb6_hlist) {
236 		if (tb->tb6_id == id) {
237 			rcu_read_unlock();
238 			return tb;
239 		}
240 	}
241 	rcu_read_unlock();
242 
243 	return NULL;
244 }
245 
246 static void __net_init fib6_tables_init(struct net *net)
247 {
248 	fib6_link_table(net, net->ipv6.fib6_main_tbl);
249 	fib6_link_table(net, net->ipv6.fib6_local_tbl);
250 }
251 #else
252 
253 struct fib6_table *fib6_new_table(struct net *net, u32 id)
254 {
255 	return fib6_get_table(net, id);
256 }
257 
258 struct fib6_table *fib6_get_table(struct net *net, u32 id)
259 {
260 	  return net->ipv6.fib6_main_tbl;
261 }
262 
263 struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
264 				   int flags, pol_lookup_t lookup)
265 {
266 	return (struct dst_entry *) lookup(net, net->ipv6.fib6_main_tbl, fl6, flags);
267 }
268 
269 static void __net_init fib6_tables_init(struct net *net)
270 {
271 	fib6_link_table(net, net->ipv6.fib6_main_tbl);
272 }
273 
274 #endif
275 
276 static int fib6_dump_node(struct fib6_walker_t *w)
277 {
278 	int res;
279 	struct rt6_info *rt;
280 
281 	for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
282 		res = rt6_dump_route(rt, w->args);
283 		if (res < 0) {
284 			/* Frame is full, suspend walking */
285 			w->leaf = rt;
286 			return 1;
287 		}
288 		WARN_ON(res == 0);
289 	}
290 	w->leaf = NULL;
291 	return 0;
292 }
293 
294 static void fib6_dump_end(struct netlink_callback *cb)
295 {
296 	struct fib6_walker_t *w = (void*)cb->args[2];
297 
298 	if (w) {
299 		if (cb->args[4]) {
300 			cb->args[4] = 0;
301 			fib6_walker_unlink(w);
302 		}
303 		cb->args[2] = 0;
304 		kfree(w);
305 	}
306 	cb->done = (void*)cb->args[3];
307 	cb->args[1] = 3;
308 }
309 
310 static int fib6_dump_done(struct netlink_callback *cb)
311 {
312 	fib6_dump_end(cb);
313 	return cb->done ? cb->done(cb) : 0;
314 }
315 
316 static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
317 			   struct netlink_callback *cb)
318 {
319 	struct fib6_walker_t *w;
320 	int res;
321 
322 	w = (void *)cb->args[2];
323 	w->root = &table->tb6_root;
324 
325 	if (cb->args[4] == 0) {
326 		w->count = 0;
327 		w->skip = 0;
328 
329 		read_lock_bh(&table->tb6_lock);
330 		res = fib6_walk(w);
331 		read_unlock_bh(&table->tb6_lock);
332 		if (res > 0) {
333 			cb->args[4] = 1;
334 			cb->args[5] = w->root->fn_sernum;
335 		}
336 	} else {
337 		if (cb->args[5] != w->root->fn_sernum) {
338 			/* Begin at the root if the tree changed */
339 			cb->args[5] = w->root->fn_sernum;
340 			w->state = FWS_INIT;
341 			w->node = w->root;
342 			w->skip = w->count;
343 		} else
344 			w->skip = 0;
345 
346 		read_lock_bh(&table->tb6_lock);
347 		res = fib6_walk_continue(w);
348 		read_unlock_bh(&table->tb6_lock);
349 		if (res <= 0) {
350 			fib6_walker_unlink(w);
351 			cb->args[4] = 0;
352 		}
353 	}
354 
355 	return res;
356 }
357 
358 static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
359 {
360 	struct net *net = sock_net(skb->sk);
361 	unsigned int h, s_h;
362 	unsigned int e = 0, s_e;
363 	struct rt6_rtnl_dump_arg arg;
364 	struct fib6_walker_t *w;
365 	struct fib6_table *tb;
366 	struct hlist_node *node;
367 	struct hlist_head *head;
368 	int res = 0;
369 
370 	s_h = cb->args[0];
371 	s_e = cb->args[1];
372 
373 	w = (void *)cb->args[2];
374 	if (!w) {
375 		/* New dump:
376 		 *
377 		 * 1. hook callback destructor.
378 		 */
379 		cb->args[3] = (long)cb->done;
380 		cb->done = fib6_dump_done;
381 
382 		/*
383 		 * 2. allocate and initialize walker.
384 		 */
385 		w = kzalloc(sizeof(*w), GFP_ATOMIC);
386 		if (!w)
387 			return -ENOMEM;
388 		w->func = fib6_dump_node;
389 		cb->args[2] = (long)w;
390 	}
391 
392 	arg.skb = skb;
393 	arg.cb = cb;
394 	arg.net = net;
395 	w->args = &arg;
396 
397 	rcu_read_lock();
398 	for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
399 		e = 0;
400 		head = &net->ipv6.fib_table_hash[h];
401 		hlist_for_each_entry_rcu(tb, node, head, tb6_hlist) {
402 			if (e < s_e)
403 				goto next;
404 			res = fib6_dump_table(tb, skb, cb);
405 			if (res != 0)
406 				goto out;
407 next:
408 			e++;
409 		}
410 	}
411 out:
412 	rcu_read_unlock();
413 	cb->args[1] = e;
414 	cb->args[0] = h;
415 
416 	res = res < 0 ? res : skb->len;
417 	if (res <= 0)
418 		fib6_dump_end(cb);
419 	return res;
420 }
421 
422 /*
423  *	Routing Table
424  *
425  *	return the appropriate node for a routing tree "add" operation
426  *	by either creating and inserting or by returning an existing
427  *	node.
428  */
429 
430 static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
431 				     int addrlen, int plen,
432 				     int offset, int allow_create,
433 				     int replace_required)
434 {
435 	struct fib6_node *fn, *in, *ln;
436 	struct fib6_node *pn = NULL;
437 	struct rt6key *key;
438 	int	bit;
439 	__be32	dir = 0;
440 	__u32	sernum = fib6_new_sernum();
441 
442 	RT6_TRACE("fib6_add_1\n");
443 
444 	/* insert node in tree */
445 
446 	fn = root;
447 
448 	do {
449 		key = (struct rt6key *)((u8 *)fn->leaf + offset);
450 
451 		/*
452 		 *	Prefix match
453 		 */
454 		if (plen < fn->fn_bit ||
455 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
456 			if (!allow_create) {
457 				if (replace_required) {
458 					pr_warn("Can't replace route, no match found\n");
459 					return ERR_PTR(-ENOENT);
460 				}
461 				pr_warn("NLM_F_CREATE should be set when creating new route\n");
462 			}
463 			goto insert_above;
464 		}
465 
466 		/*
467 		 *	Exact match ?
468 		 */
469 
470 		if (plen == fn->fn_bit) {
471 			/* clean up an intermediate node */
472 			if (!(fn->fn_flags & RTN_RTINFO)) {
473 				rt6_release(fn->leaf);
474 				fn->leaf = NULL;
475 			}
476 
477 			fn->fn_sernum = sernum;
478 
479 			return fn;
480 		}
481 
482 		/*
483 		 *	We have more bits to go
484 		 */
485 
486 		/* Try to walk down on tree. */
487 		fn->fn_sernum = sernum;
488 		dir = addr_bit_set(addr, fn->fn_bit);
489 		pn = fn;
490 		fn = dir ? fn->right: fn->left;
491 	} while (fn);
492 
493 	if (!allow_create) {
494 		/* We should not create new node because
495 		 * NLM_F_REPLACE was specified without NLM_F_CREATE
496 		 * I assume it is safe to require NLM_F_CREATE when
497 		 * REPLACE flag is used! Later we may want to remove the
498 		 * check for replace_required, because according
499 		 * to netlink specification, NLM_F_CREATE
500 		 * MUST be specified if new route is created.
501 		 * That would keep IPv6 consistent with IPv4
502 		 */
503 		if (replace_required) {
504 			pr_warn("Can't replace route, no match found\n");
505 			return ERR_PTR(-ENOENT);
506 		}
507 		pr_warn("NLM_F_CREATE should be set when creating new route\n");
508 	}
509 	/*
510 	 *	We walked to the bottom of tree.
511 	 *	Create new leaf node without children.
512 	 */
513 
514 	ln = node_alloc();
515 
516 	if (!ln)
517 		return NULL;
518 	ln->fn_bit = plen;
519 
520 	ln->parent = pn;
521 	ln->fn_sernum = sernum;
522 
523 	if (dir)
524 		pn->right = ln;
525 	else
526 		pn->left  = ln;
527 
528 	return ln;
529 
530 
531 insert_above:
532 	/*
533 	 * split since we don't have a common prefix anymore or
534 	 * we have a less significant route.
535 	 * we've to insert an intermediate node on the list
536 	 * this new node will point to the one we need to create
537 	 * and the current
538 	 */
539 
540 	pn = fn->parent;
541 
542 	/* find 1st bit in difference between the 2 addrs.
543 
544 	   See comment in __ipv6_addr_diff: bit may be an invalid value,
545 	   but if it is >= plen, the value is ignored in any case.
546 	 */
547 
548 	bit = __ipv6_addr_diff(addr, &key->addr, addrlen);
549 
550 	/*
551 	 *		(intermediate)[in]
552 	 *	          /	   \
553 	 *	(new leaf node)[ln] (old node)[fn]
554 	 */
555 	if (plen > bit) {
556 		in = node_alloc();
557 		ln = node_alloc();
558 
559 		if (!in || !ln) {
560 			if (in)
561 				node_free(in);
562 			if (ln)
563 				node_free(ln);
564 			return NULL;
565 		}
566 
567 		/*
568 		 * new intermediate node.
569 		 * RTN_RTINFO will
570 		 * be off since that an address that chooses one of
571 		 * the branches would not match less specific routes
572 		 * in the other branch
573 		 */
574 
575 		in->fn_bit = bit;
576 
577 		in->parent = pn;
578 		in->leaf = fn->leaf;
579 		atomic_inc(&in->leaf->rt6i_ref);
580 
581 		in->fn_sernum = sernum;
582 
583 		/* update parent pointer */
584 		if (dir)
585 			pn->right = in;
586 		else
587 			pn->left  = in;
588 
589 		ln->fn_bit = plen;
590 
591 		ln->parent = in;
592 		fn->parent = in;
593 
594 		ln->fn_sernum = sernum;
595 
596 		if (addr_bit_set(addr, bit)) {
597 			in->right = ln;
598 			in->left  = fn;
599 		} else {
600 			in->left  = ln;
601 			in->right = fn;
602 		}
603 	} else { /* plen <= bit */
604 
605 		/*
606 		 *		(new leaf node)[ln]
607 		 *	          /	   \
608 		 *	     (old node)[fn] NULL
609 		 */
610 
611 		ln = node_alloc();
612 
613 		if (!ln)
614 			return NULL;
615 
616 		ln->fn_bit = plen;
617 
618 		ln->parent = pn;
619 
620 		ln->fn_sernum = sernum;
621 
622 		if (dir)
623 			pn->right = ln;
624 		else
625 			pn->left  = ln;
626 
627 		if (addr_bit_set(&key->addr, plen))
628 			ln->right = fn;
629 		else
630 			ln->left  = fn;
631 
632 		fn->parent = ln;
633 	}
634 	return ln;
635 }
636 
637 /*
638  *	Insert routing information in a node.
639  */
640 
641 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
642 			    struct nl_info *info)
643 {
644 	struct rt6_info *iter = NULL;
645 	struct rt6_info **ins;
646 	int replace = (info->nlh &&
647 		       (info->nlh->nlmsg_flags & NLM_F_REPLACE));
648 	int add = (!info->nlh ||
649 		   (info->nlh->nlmsg_flags & NLM_F_CREATE));
650 	int found = 0;
651 
652 	ins = &fn->leaf;
653 
654 	for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) {
655 		/*
656 		 *	Search for duplicates
657 		 */
658 
659 		if (iter->rt6i_metric == rt->rt6i_metric) {
660 			/*
661 			 *	Same priority level
662 			 */
663 			if (info->nlh &&
664 			    (info->nlh->nlmsg_flags & NLM_F_EXCL))
665 				return -EEXIST;
666 			if (replace) {
667 				found++;
668 				break;
669 			}
670 
671 			if (iter->dst.dev == rt->dst.dev &&
672 			    iter->rt6i_idev == rt->rt6i_idev &&
673 			    ipv6_addr_equal(&iter->rt6i_gateway,
674 					    &rt->rt6i_gateway)) {
675 				if (!(iter->rt6i_flags & RTF_EXPIRES))
676 					return -EEXIST;
677 				if (!(rt->rt6i_flags & RTF_EXPIRES))
678 					rt6_clean_expires(iter);
679 				else
680 					rt6_set_expires(iter, rt->dst.expires);
681 				return -EEXIST;
682 			}
683 		}
684 
685 		if (iter->rt6i_metric > rt->rt6i_metric)
686 			break;
687 
688 		ins = &iter->dst.rt6_next;
689 	}
690 
691 	/* Reset round-robin state, if necessary */
692 	if (ins == &fn->leaf)
693 		fn->rr_ptr = NULL;
694 
695 	/*
696 	 *	insert node
697 	 */
698 	if (!replace) {
699 		if (!add)
700 			pr_warn("NLM_F_CREATE should be set when creating new route\n");
701 
702 add:
703 		rt->dst.rt6_next = iter;
704 		*ins = rt;
705 		rt->rt6i_node = fn;
706 		atomic_inc(&rt->rt6i_ref);
707 		inet6_rt_notify(RTM_NEWROUTE, rt, info);
708 		info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
709 
710 		if (!(fn->fn_flags & RTN_RTINFO)) {
711 			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
712 			fn->fn_flags |= RTN_RTINFO;
713 		}
714 
715 	} else {
716 		if (!found) {
717 			if (add)
718 				goto add;
719 			pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
720 			return -ENOENT;
721 		}
722 		*ins = rt;
723 		rt->rt6i_node = fn;
724 		rt->dst.rt6_next = iter->dst.rt6_next;
725 		atomic_inc(&rt->rt6i_ref);
726 		inet6_rt_notify(RTM_NEWROUTE, rt, info);
727 		rt6_release(iter);
728 		if (!(fn->fn_flags & RTN_RTINFO)) {
729 			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
730 			fn->fn_flags |= RTN_RTINFO;
731 		}
732 	}
733 
734 	return 0;
735 }
736 
737 static __inline__ void fib6_start_gc(struct net *net, struct rt6_info *rt)
738 {
739 	if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
740 	    (rt->rt6i_flags & (RTF_EXPIRES | RTF_CACHE)))
741 		mod_timer(&net->ipv6.ip6_fib_timer,
742 			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
743 }
744 
745 void fib6_force_start_gc(struct net *net)
746 {
747 	if (!timer_pending(&net->ipv6.ip6_fib_timer))
748 		mod_timer(&net->ipv6.ip6_fib_timer,
749 			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
750 }
751 
752 /*
753  *	Add routing information to the routing tree.
754  *	<destination addr>/<source addr>
755  *	with source addr info in sub-trees
756  */
757 
758 int fib6_add(struct fib6_node *root, struct rt6_info *rt, struct nl_info *info)
759 {
760 	struct fib6_node *fn, *pn = NULL;
761 	int err = -ENOMEM;
762 	int allow_create = 1;
763 	int replace_required = 0;
764 
765 	if (info->nlh) {
766 		if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
767 			allow_create = 0;
768 		if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
769 			replace_required = 1;
770 	}
771 	if (!allow_create && !replace_required)
772 		pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
773 
774 	fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
775 			rt->rt6i_dst.plen, offsetof(struct rt6_info, rt6i_dst),
776 			allow_create, replace_required);
777 
778 	if (IS_ERR(fn)) {
779 		err = PTR_ERR(fn);
780 		fn = NULL;
781 	}
782 
783 	if (!fn)
784 		goto out;
785 
786 	pn = fn;
787 
788 #ifdef CONFIG_IPV6_SUBTREES
789 	if (rt->rt6i_src.plen) {
790 		struct fib6_node *sn;
791 
792 		if (!fn->subtree) {
793 			struct fib6_node *sfn;
794 
795 			/*
796 			 * Create subtree.
797 			 *
798 			 *		fn[main tree]
799 			 *		|
800 			 *		sfn[subtree root]
801 			 *		   \
802 			 *		    sn[new leaf node]
803 			 */
804 
805 			/* Create subtree root node */
806 			sfn = node_alloc();
807 			if (!sfn)
808 				goto st_failure;
809 
810 			sfn->leaf = info->nl_net->ipv6.ip6_null_entry;
811 			atomic_inc(&info->nl_net->ipv6.ip6_null_entry->rt6i_ref);
812 			sfn->fn_flags = RTN_ROOT;
813 			sfn->fn_sernum = fib6_new_sernum();
814 
815 			/* Now add the first leaf node to new subtree */
816 
817 			sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
818 					sizeof(struct in6_addr), rt->rt6i_src.plen,
819 					offsetof(struct rt6_info, rt6i_src),
820 					allow_create, replace_required);
821 
822 			if (IS_ERR(sn)) {
823 				err = PTR_ERR(sn);
824 				sn = NULL;
825 			}
826 			if (!sn) {
827 				/* If it is failed, discard just allocated
828 				   root, and then (in st_failure) stale node
829 				   in main tree.
830 				 */
831 				node_free(sfn);
832 				goto st_failure;
833 			}
834 
835 			/* Now link new subtree to main tree */
836 			sfn->parent = fn;
837 			fn->subtree = sfn;
838 		} else {
839 			sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
840 					sizeof(struct in6_addr), rt->rt6i_src.plen,
841 					offsetof(struct rt6_info, rt6i_src),
842 					allow_create, replace_required);
843 
844 			if (IS_ERR(sn)) {
845 				err = PTR_ERR(sn);
846 				sn = NULL;
847 			}
848 			if (!sn)
849 				goto st_failure;
850 		}
851 
852 		if (!fn->leaf) {
853 			fn->leaf = rt;
854 			atomic_inc(&rt->rt6i_ref);
855 		}
856 		fn = sn;
857 	}
858 #endif
859 
860 	err = fib6_add_rt2node(fn, rt, info);
861 	if (!err) {
862 		fib6_start_gc(info->nl_net, rt);
863 		if (!(rt->rt6i_flags & RTF_CACHE))
864 			fib6_prune_clones(info->nl_net, pn, rt);
865 	}
866 
867 out:
868 	if (err) {
869 #ifdef CONFIG_IPV6_SUBTREES
870 		/*
871 		 * If fib6_add_1 has cleared the old leaf pointer in the
872 		 * super-tree leaf node we have to find a new one for it.
873 		 */
874 		if (pn != fn && pn->leaf == rt) {
875 			pn->leaf = NULL;
876 			atomic_dec(&rt->rt6i_ref);
877 		}
878 		if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
879 			pn->leaf = fib6_find_prefix(info->nl_net, pn);
880 #if RT6_DEBUG >= 2
881 			if (!pn->leaf) {
882 				WARN_ON(pn->leaf == NULL);
883 				pn->leaf = info->nl_net->ipv6.ip6_null_entry;
884 			}
885 #endif
886 			atomic_inc(&pn->leaf->rt6i_ref);
887 		}
888 #endif
889 		dst_free(&rt->dst);
890 	}
891 	return err;
892 
893 #ifdef CONFIG_IPV6_SUBTREES
894 	/* Subtree creation failed, probably main tree node
895 	   is orphan. If it is, shoot it.
896 	 */
897 st_failure:
898 	if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
899 		fib6_repair_tree(info->nl_net, fn);
900 	dst_free(&rt->dst);
901 	return err;
902 #endif
903 }
904 
905 /*
906  *	Routing tree lookup
907  *
908  */
909 
910 struct lookup_args {
911 	int			offset;		/* key offset on rt6_info	*/
912 	const struct in6_addr	*addr;		/* search key			*/
913 };
914 
915 static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
916 					struct lookup_args *args)
917 {
918 	struct fib6_node *fn;
919 	__be32 dir;
920 
921 	if (unlikely(args->offset == 0))
922 		return NULL;
923 
924 	/*
925 	 *	Descend on a tree
926 	 */
927 
928 	fn = root;
929 
930 	for (;;) {
931 		struct fib6_node *next;
932 
933 		dir = addr_bit_set(args->addr, fn->fn_bit);
934 
935 		next = dir ? fn->right : fn->left;
936 
937 		if (next) {
938 			fn = next;
939 			continue;
940 		}
941 		break;
942 	}
943 
944 	while (fn) {
945 		if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
946 			struct rt6key *key;
947 
948 			key = (struct rt6key *) ((u8 *) fn->leaf +
949 						 args->offset);
950 
951 			if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
952 #ifdef CONFIG_IPV6_SUBTREES
953 				if (fn->subtree)
954 					fn = fib6_lookup_1(fn->subtree, args + 1);
955 #endif
956 				if (!fn || fn->fn_flags & RTN_RTINFO)
957 					return fn;
958 			}
959 		}
960 
961 		if (fn->fn_flags & RTN_ROOT)
962 			break;
963 
964 		fn = fn->parent;
965 	}
966 
967 	return NULL;
968 }
969 
970 struct fib6_node * fib6_lookup(struct fib6_node *root, const struct in6_addr *daddr,
971 			       const struct in6_addr *saddr)
972 {
973 	struct fib6_node *fn;
974 	struct lookup_args args[] = {
975 		{
976 			.offset = offsetof(struct rt6_info, rt6i_dst),
977 			.addr = daddr,
978 		},
979 #ifdef CONFIG_IPV6_SUBTREES
980 		{
981 			.offset = offsetof(struct rt6_info, rt6i_src),
982 			.addr = saddr,
983 		},
984 #endif
985 		{
986 			.offset = 0,	/* sentinel */
987 		}
988 	};
989 
990 	fn = fib6_lookup_1(root, daddr ? args : args + 1);
991 	if (!fn || fn->fn_flags & RTN_TL_ROOT)
992 		fn = root;
993 
994 	return fn;
995 }
996 
997 /*
998  *	Get node with specified destination prefix (and source prefix,
999  *	if subtrees are used)
1000  */
1001 
1002 
1003 static struct fib6_node * fib6_locate_1(struct fib6_node *root,
1004 					const struct in6_addr *addr,
1005 					int plen, int offset)
1006 {
1007 	struct fib6_node *fn;
1008 
1009 	for (fn = root; fn ; ) {
1010 		struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
1011 
1012 		/*
1013 		 *	Prefix match
1014 		 */
1015 		if (plen < fn->fn_bit ||
1016 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1017 			return NULL;
1018 
1019 		if (plen == fn->fn_bit)
1020 			return fn;
1021 
1022 		/*
1023 		 *	We have more bits to go
1024 		 */
1025 		if (addr_bit_set(addr, fn->fn_bit))
1026 			fn = fn->right;
1027 		else
1028 			fn = fn->left;
1029 	}
1030 	return NULL;
1031 }
1032 
1033 struct fib6_node * fib6_locate(struct fib6_node *root,
1034 			       const struct in6_addr *daddr, int dst_len,
1035 			       const struct in6_addr *saddr, int src_len)
1036 {
1037 	struct fib6_node *fn;
1038 
1039 	fn = fib6_locate_1(root, daddr, dst_len,
1040 			   offsetof(struct rt6_info, rt6i_dst));
1041 
1042 #ifdef CONFIG_IPV6_SUBTREES
1043 	if (src_len) {
1044 		WARN_ON(saddr == NULL);
1045 		if (fn && fn->subtree)
1046 			fn = fib6_locate_1(fn->subtree, saddr, src_len,
1047 					   offsetof(struct rt6_info, rt6i_src));
1048 	}
1049 #endif
1050 
1051 	if (fn && fn->fn_flags & RTN_RTINFO)
1052 		return fn;
1053 
1054 	return NULL;
1055 }
1056 
1057 
1058 /*
1059  *	Deletion
1060  *
1061  */
1062 
1063 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn)
1064 {
1065 	if (fn->fn_flags & RTN_ROOT)
1066 		return net->ipv6.ip6_null_entry;
1067 
1068 	while (fn) {
1069 		if (fn->left)
1070 			return fn->left->leaf;
1071 		if (fn->right)
1072 			return fn->right->leaf;
1073 
1074 		fn = FIB6_SUBTREE(fn);
1075 	}
1076 	return NULL;
1077 }
1078 
1079 /*
1080  *	Called to trim the tree of intermediate nodes when possible. "fn"
1081  *	is the node we want to try and remove.
1082  */
1083 
1084 static struct fib6_node *fib6_repair_tree(struct net *net,
1085 					   struct fib6_node *fn)
1086 {
1087 	int children;
1088 	int nstate;
1089 	struct fib6_node *child, *pn;
1090 	struct fib6_walker_t *w;
1091 	int iter = 0;
1092 
1093 	for (;;) {
1094 		RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1095 		iter++;
1096 
1097 		WARN_ON(fn->fn_flags & RTN_RTINFO);
1098 		WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1099 		WARN_ON(fn->leaf != NULL);
1100 
1101 		children = 0;
1102 		child = NULL;
1103 		if (fn->right) child = fn->right, children |= 1;
1104 		if (fn->left) child = fn->left, children |= 2;
1105 
1106 		if (children == 3 || FIB6_SUBTREE(fn)
1107 #ifdef CONFIG_IPV6_SUBTREES
1108 		    /* Subtree root (i.e. fn) may have one child */
1109 		    || (children && fn->fn_flags & RTN_ROOT)
1110 #endif
1111 		    ) {
1112 			fn->leaf = fib6_find_prefix(net, fn);
1113 #if RT6_DEBUG >= 2
1114 			if (!fn->leaf) {
1115 				WARN_ON(!fn->leaf);
1116 				fn->leaf = net->ipv6.ip6_null_entry;
1117 			}
1118 #endif
1119 			atomic_inc(&fn->leaf->rt6i_ref);
1120 			return fn->parent;
1121 		}
1122 
1123 		pn = fn->parent;
1124 #ifdef CONFIG_IPV6_SUBTREES
1125 		if (FIB6_SUBTREE(pn) == fn) {
1126 			WARN_ON(!(fn->fn_flags & RTN_ROOT));
1127 			FIB6_SUBTREE(pn) = NULL;
1128 			nstate = FWS_L;
1129 		} else {
1130 			WARN_ON(fn->fn_flags & RTN_ROOT);
1131 #endif
1132 			if (pn->right == fn) pn->right = child;
1133 			else if (pn->left == fn) pn->left = child;
1134 #if RT6_DEBUG >= 2
1135 			else
1136 				WARN_ON(1);
1137 #endif
1138 			if (child)
1139 				child->parent = pn;
1140 			nstate = FWS_R;
1141 #ifdef CONFIG_IPV6_SUBTREES
1142 		}
1143 #endif
1144 
1145 		read_lock(&fib6_walker_lock);
1146 		FOR_WALKERS(w) {
1147 			if (!child) {
1148 				if (w->root == fn) {
1149 					w->root = w->node = NULL;
1150 					RT6_TRACE("W %p adjusted by delroot 1\n", w);
1151 				} else if (w->node == fn) {
1152 					RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1153 					w->node = pn;
1154 					w->state = nstate;
1155 				}
1156 			} else {
1157 				if (w->root == fn) {
1158 					w->root = child;
1159 					RT6_TRACE("W %p adjusted by delroot 2\n", w);
1160 				}
1161 				if (w->node == fn) {
1162 					w->node = child;
1163 					if (children&2) {
1164 						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1165 						w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
1166 					} else {
1167 						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1168 						w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
1169 					}
1170 				}
1171 			}
1172 		}
1173 		read_unlock(&fib6_walker_lock);
1174 
1175 		node_free(fn);
1176 		if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
1177 			return pn;
1178 
1179 		rt6_release(pn->leaf);
1180 		pn->leaf = NULL;
1181 		fn = pn;
1182 	}
1183 }
1184 
1185 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
1186 			   struct nl_info *info)
1187 {
1188 	struct fib6_walker_t *w;
1189 	struct rt6_info *rt = *rtp;
1190 	struct net *net = info->nl_net;
1191 
1192 	RT6_TRACE("fib6_del_route\n");
1193 
1194 	/* Unlink it */
1195 	*rtp = rt->dst.rt6_next;
1196 	rt->rt6i_node = NULL;
1197 	net->ipv6.rt6_stats->fib_rt_entries--;
1198 	net->ipv6.rt6_stats->fib_discarded_routes++;
1199 
1200 	/* Reset round-robin state, if necessary */
1201 	if (fn->rr_ptr == rt)
1202 		fn->rr_ptr = NULL;
1203 
1204 	/* Adjust walkers */
1205 	read_lock(&fib6_walker_lock);
1206 	FOR_WALKERS(w) {
1207 		if (w->state == FWS_C && w->leaf == rt) {
1208 			RT6_TRACE("walker %p adjusted by delroute\n", w);
1209 			w->leaf = rt->dst.rt6_next;
1210 			if (!w->leaf)
1211 				w->state = FWS_U;
1212 		}
1213 	}
1214 	read_unlock(&fib6_walker_lock);
1215 
1216 	rt->dst.rt6_next = NULL;
1217 
1218 	/* If it was last route, expunge its radix tree node */
1219 	if (!fn->leaf) {
1220 		fn->fn_flags &= ~RTN_RTINFO;
1221 		net->ipv6.rt6_stats->fib_route_nodes--;
1222 		fn = fib6_repair_tree(net, fn);
1223 	}
1224 
1225 	if (atomic_read(&rt->rt6i_ref) != 1) {
1226 		/* This route is used as dummy address holder in some split
1227 		 * nodes. It is not leaked, but it still holds other resources,
1228 		 * which must be released in time. So, scan ascendant nodes
1229 		 * and replace dummy references to this route with references
1230 		 * to still alive ones.
1231 		 */
1232 		while (fn) {
1233 			if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) {
1234 				fn->leaf = fib6_find_prefix(net, fn);
1235 				atomic_inc(&fn->leaf->rt6i_ref);
1236 				rt6_release(rt);
1237 			}
1238 			fn = fn->parent;
1239 		}
1240 		/* No more references are possible at this point. */
1241 		BUG_ON(atomic_read(&rt->rt6i_ref) != 1);
1242 	}
1243 
1244 	inet6_rt_notify(RTM_DELROUTE, rt, info);
1245 	rt6_release(rt);
1246 }
1247 
1248 int fib6_del(struct rt6_info *rt, struct nl_info *info)
1249 {
1250 	struct net *net = info->nl_net;
1251 	struct fib6_node *fn = rt->rt6i_node;
1252 	struct rt6_info **rtp;
1253 
1254 #if RT6_DEBUG >= 2
1255 	if (rt->dst.obsolete>0) {
1256 		WARN_ON(fn != NULL);
1257 		return -ENOENT;
1258 	}
1259 #endif
1260 	if (!fn || rt == net->ipv6.ip6_null_entry)
1261 		return -ENOENT;
1262 
1263 	WARN_ON(!(fn->fn_flags & RTN_RTINFO));
1264 
1265 	if (!(rt->rt6i_flags & RTF_CACHE)) {
1266 		struct fib6_node *pn = fn;
1267 #ifdef CONFIG_IPV6_SUBTREES
1268 		/* clones of this route might be in another subtree */
1269 		if (rt->rt6i_src.plen) {
1270 			while (!(pn->fn_flags & RTN_ROOT))
1271 				pn = pn->parent;
1272 			pn = pn->parent;
1273 		}
1274 #endif
1275 		fib6_prune_clones(info->nl_net, pn, rt);
1276 	}
1277 
1278 	/*
1279 	 *	Walk the leaf entries looking for ourself
1280 	 */
1281 
1282 	for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) {
1283 		if (*rtp == rt) {
1284 			fib6_del_route(fn, rtp, info);
1285 			return 0;
1286 		}
1287 	}
1288 	return -ENOENT;
1289 }
1290 
1291 /*
1292  *	Tree traversal function.
1293  *
1294  *	Certainly, it is not interrupt safe.
1295  *	However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1296  *	It means, that we can modify tree during walking
1297  *	and use this function for garbage collection, clone pruning,
1298  *	cleaning tree when a device goes down etc. etc.
1299  *
1300  *	It guarantees that every node will be traversed,
1301  *	and that it will be traversed only once.
1302  *
1303  *	Callback function w->func may return:
1304  *	0 -> continue walking.
1305  *	positive value -> walking is suspended (used by tree dumps,
1306  *	and probably by gc, if it will be split to several slices)
1307  *	negative value -> terminate walking.
1308  *
1309  *	The function itself returns:
1310  *	0   -> walk is complete.
1311  *	>0  -> walk is incomplete (i.e. suspended)
1312  *	<0  -> walk is terminated by an error.
1313  */
1314 
1315 static int fib6_walk_continue(struct fib6_walker_t *w)
1316 {
1317 	struct fib6_node *fn, *pn;
1318 
1319 	for (;;) {
1320 		fn = w->node;
1321 		if (!fn)
1322 			return 0;
1323 
1324 		if (w->prune && fn != w->root &&
1325 		    fn->fn_flags & RTN_RTINFO && w->state < FWS_C) {
1326 			w->state = FWS_C;
1327 			w->leaf = fn->leaf;
1328 		}
1329 		switch (w->state) {
1330 #ifdef CONFIG_IPV6_SUBTREES
1331 		case FWS_S:
1332 			if (FIB6_SUBTREE(fn)) {
1333 				w->node = FIB6_SUBTREE(fn);
1334 				continue;
1335 			}
1336 			w->state = FWS_L;
1337 #endif
1338 		case FWS_L:
1339 			if (fn->left) {
1340 				w->node = fn->left;
1341 				w->state = FWS_INIT;
1342 				continue;
1343 			}
1344 			w->state = FWS_R;
1345 		case FWS_R:
1346 			if (fn->right) {
1347 				w->node = fn->right;
1348 				w->state = FWS_INIT;
1349 				continue;
1350 			}
1351 			w->state = FWS_C;
1352 			w->leaf = fn->leaf;
1353 		case FWS_C:
1354 			if (w->leaf && fn->fn_flags & RTN_RTINFO) {
1355 				int err;
1356 
1357 				if (w->skip) {
1358 					w->skip--;
1359 					continue;
1360 				}
1361 
1362 				err = w->func(w);
1363 				if (err)
1364 					return err;
1365 
1366 				w->count++;
1367 				continue;
1368 			}
1369 			w->state = FWS_U;
1370 		case FWS_U:
1371 			if (fn == w->root)
1372 				return 0;
1373 			pn = fn->parent;
1374 			w->node = pn;
1375 #ifdef CONFIG_IPV6_SUBTREES
1376 			if (FIB6_SUBTREE(pn) == fn) {
1377 				WARN_ON(!(fn->fn_flags & RTN_ROOT));
1378 				w->state = FWS_L;
1379 				continue;
1380 			}
1381 #endif
1382 			if (pn->left == fn) {
1383 				w->state = FWS_R;
1384 				continue;
1385 			}
1386 			if (pn->right == fn) {
1387 				w->state = FWS_C;
1388 				w->leaf = w->node->leaf;
1389 				continue;
1390 			}
1391 #if RT6_DEBUG >= 2
1392 			WARN_ON(1);
1393 #endif
1394 		}
1395 	}
1396 }
1397 
1398 static int fib6_walk(struct fib6_walker_t *w)
1399 {
1400 	int res;
1401 
1402 	w->state = FWS_INIT;
1403 	w->node = w->root;
1404 
1405 	fib6_walker_link(w);
1406 	res = fib6_walk_continue(w);
1407 	if (res <= 0)
1408 		fib6_walker_unlink(w);
1409 	return res;
1410 }
1411 
1412 static int fib6_clean_node(struct fib6_walker_t *w)
1413 {
1414 	int res;
1415 	struct rt6_info *rt;
1416 	struct fib6_cleaner_t *c = container_of(w, struct fib6_cleaner_t, w);
1417 	struct nl_info info = {
1418 		.nl_net = c->net,
1419 	};
1420 
1421 	for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
1422 		res = c->func(rt, c->arg);
1423 		if (res < 0) {
1424 			w->leaf = rt;
1425 			res = fib6_del(rt, &info);
1426 			if (res) {
1427 #if RT6_DEBUG >= 2
1428 				pr_debug("%s: del failed: rt=%p@%p err=%d\n",
1429 					 __func__, rt, rt->rt6i_node, res);
1430 #endif
1431 				continue;
1432 			}
1433 			return 0;
1434 		}
1435 		WARN_ON(res != 0);
1436 	}
1437 	w->leaf = rt;
1438 	return 0;
1439 }
1440 
1441 /*
1442  *	Convenient frontend to tree walker.
1443  *
1444  *	func is called on each route.
1445  *		It may return -1 -> delete this route.
1446  *		              0  -> continue walking
1447  *
1448  *	prune==1 -> only immediate children of node (certainly,
1449  *	ignoring pure split nodes) will be scanned.
1450  */
1451 
1452 static void fib6_clean_tree(struct net *net, struct fib6_node *root,
1453 			    int (*func)(struct rt6_info *, void *arg),
1454 			    int prune, void *arg)
1455 {
1456 	struct fib6_cleaner_t c;
1457 
1458 	c.w.root = root;
1459 	c.w.func = fib6_clean_node;
1460 	c.w.prune = prune;
1461 	c.w.count = 0;
1462 	c.w.skip = 0;
1463 	c.func = func;
1464 	c.arg = arg;
1465 	c.net = net;
1466 
1467 	fib6_walk(&c.w);
1468 }
1469 
1470 void fib6_clean_all_ro(struct net *net, int (*func)(struct rt6_info *, void *arg),
1471 		    int prune, void *arg)
1472 {
1473 	struct fib6_table *table;
1474 	struct hlist_node *node;
1475 	struct hlist_head *head;
1476 	unsigned int h;
1477 
1478 	rcu_read_lock();
1479 	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
1480 		head = &net->ipv6.fib_table_hash[h];
1481 		hlist_for_each_entry_rcu(table, node, head, tb6_hlist) {
1482 			read_lock_bh(&table->tb6_lock);
1483 			fib6_clean_tree(net, &table->tb6_root,
1484 					func, prune, arg);
1485 			read_unlock_bh(&table->tb6_lock);
1486 		}
1487 	}
1488 	rcu_read_unlock();
1489 }
1490 void fib6_clean_all(struct net *net, int (*func)(struct rt6_info *, void *arg),
1491 		    int prune, void *arg)
1492 {
1493 	struct fib6_table *table;
1494 	struct hlist_node *node;
1495 	struct hlist_head *head;
1496 	unsigned int h;
1497 
1498 	rcu_read_lock();
1499 	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
1500 		head = &net->ipv6.fib_table_hash[h];
1501 		hlist_for_each_entry_rcu(table, node, head, tb6_hlist) {
1502 			write_lock_bh(&table->tb6_lock);
1503 			fib6_clean_tree(net, &table->tb6_root,
1504 					func, prune, arg);
1505 			write_unlock_bh(&table->tb6_lock);
1506 		}
1507 	}
1508 	rcu_read_unlock();
1509 }
1510 
1511 static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1512 {
1513 	if (rt->rt6i_flags & RTF_CACHE) {
1514 		RT6_TRACE("pruning clone %p\n", rt);
1515 		return -1;
1516 	}
1517 
1518 	return 0;
1519 }
1520 
1521 static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
1522 			      struct rt6_info *rt)
1523 {
1524 	fib6_clean_tree(net, fn, fib6_prune_clone, 1, rt);
1525 }
1526 
1527 /*
1528  *	Garbage collection
1529  */
1530 
1531 static struct fib6_gc_args
1532 {
1533 	int			timeout;
1534 	int			more;
1535 } gc_args;
1536 
1537 static int fib6_age(struct rt6_info *rt, void *arg)
1538 {
1539 	unsigned long now = jiffies;
1540 
1541 	/*
1542 	 *	check addrconf expiration here.
1543 	 *	Routes are expired even if they are in use.
1544 	 *
1545 	 *	Also age clones. Note, that clones are aged out
1546 	 *	only if they are not in use now.
1547 	 */
1548 
1549 	if (rt->rt6i_flags & RTF_EXPIRES && rt->dst.expires) {
1550 		if (time_after(now, rt->dst.expires)) {
1551 			RT6_TRACE("expiring %p\n", rt);
1552 			return -1;
1553 		}
1554 		gc_args.more++;
1555 	} else if (rt->rt6i_flags & RTF_CACHE) {
1556 		if (atomic_read(&rt->dst.__refcnt) == 0 &&
1557 		    time_after_eq(now, rt->dst.lastuse + gc_args.timeout)) {
1558 			RT6_TRACE("aging clone %p\n", rt);
1559 			return -1;
1560 		} else if (rt->rt6i_flags & RTF_GATEWAY) {
1561 			struct neighbour *neigh;
1562 			__u8 neigh_flags = 0;
1563 
1564 			neigh = dst_neigh_lookup(&rt->dst, &rt->rt6i_gateway);
1565 			if (neigh) {
1566 				neigh_flags = neigh->flags;
1567 				neigh_release(neigh);
1568 			}
1569 			if (!(neigh_flags & NTF_ROUTER)) {
1570 				RT6_TRACE("purging route %p via non-router but gateway\n",
1571 					  rt);
1572 				return -1;
1573 			}
1574 		}
1575 		gc_args.more++;
1576 	}
1577 
1578 	return 0;
1579 }
1580 
1581 static DEFINE_SPINLOCK(fib6_gc_lock);
1582 
1583 void fib6_run_gc(unsigned long expires, struct net *net)
1584 {
1585 	if (expires != ~0UL) {
1586 		spin_lock_bh(&fib6_gc_lock);
1587 		gc_args.timeout = expires ? (int)expires :
1588 			net->ipv6.sysctl.ip6_rt_gc_interval;
1589 	} else {
1590 		if (!spin_trylock_bh(&fib6_gc_lock)) {
1591 			mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
1592 			return;
1593 		}
1594 		gc_args.timeout = net->ipv6.sysctl.ip6_rt_gc_interval;
1595 	}
1596 
1597 	gc_args.more = icmp6_dst_gc();
1598 
1599 	fib6_clean_all(net, fib6_age, 0, NULL);
1600 
1601 	if (gc_args.more)
1602 		mod_timer(&net->ipv6.ip6_fib_timer,
1603 			  round_jiffies(jiffies
1604 					+ net->ipv6.sysctl.ip6_rt_gc_interval));
1605 	else
1606 		del_timer(&net->ipv6.ip6_fib_timer);
1607 	spin_unlock_bh(&fib6_gc_lock);
1608 }
1609 
1610 static void fib6_gc_timer_cb(unsigned long arg)
1611 {
1612 	fib6_run_gc(0, (struct net *)arg);
1613 }
1614 
1615 static int __net_init fib6_net_init(struct net *net)
1616 {
1617 	size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
1618 
1619 	setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (unsigned long)net);
1620 
1621 	net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
1622 	if (!net->ipv6.rt6_stats)
1623 		goto out_timer;
1624 
1625 	/* Avoid false sharing : Use at least a full cache line */
1626 	size = max_t(size_t, size, L1_CACHE_BYTES);
1627 
1628 	net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
1629 	if (!net->ipv6.fib_table_hash)
1630 		goto out_rt6_stats;
1631 
1632 	net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
1633 					  GFP_KERNEL);
1634 	if (!net->ipv6.fib6_main_tbl)
1635 		goto out_fib_table_hash;
1636 
1637 	net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
1638 	net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1639 	net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
1640 		RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1641 	inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
1642 
1643 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1644 	net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
1645 					   GFP_KERNEL);
1646 	if (!net->ipv6.fib6_local_tbl)
1647 		goto out_fib6_main_tbl;
1648 	net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
1649 	net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1650 	net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
1651 		RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1652 	inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
1653 #endif
1654 	fib6_tables_init(net);
1655 
1656 	return 0;
1657 
1658 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1659 out_fib6_main_tbl:
1660 	kfree(net->ipv6.fib6_main_tbl);
1661 #endif
1662 out_fib_table_hash:
1663 	kfree(net->ipv6.fib_table_hash);
1664 out_rt6_stats:
1665 	kfree(net->ipv6.rt6_stats);
1666 out_timer:
1667 	return -ENOMEM;
1668  }
1669 
1670 static void fib6_net_exit(struct net *net)
1671 {
1672 	rt6_ifdown(net, NULL);
1673 	del_timer_sync(&net->ipv6.ip6_fib_timer);
1674 
1675 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1676 	inetpeer_invalidate_tree(&net->ipv6.fib6_local_tbl->tb6_peers);
1677 	kfree(net->ipv6.fib6_local_tbl);
1678 #endif
1679 	inetpeer_invalidate_tree(&net->ipv6.fib6_main_tbl->tb6_peers);
1680 	kfree(net->ipv6.fib6_main_tbl);
1681 	kfree(net->ipv6.fib_table_hash);
1682 	kfree(net->ipv6.rt6_stats);
1683 }
1684 
1685 static struct pernet_operations fib6_net_ops = {
1686 	.init = fib6_net_init,
1687 	.exit = fib6_net_exit,
1688 };
1689 
1690 int __init fib6_init(void)
1691 {
1692 	int ret = -ENOMEM;
1693 
1694 	fib6_node_kmem = kmem_cache_create("fib6_nodes",
1695 					   sizeof(struct fib6_node),
1696 					   0, SLAB_HWCACHE_ALIGN,
1697 					   NULL);
1698 	if (!fib6_node_kmem)
1699 		goto out;
1700 
1701 	ret = register_pernet_subsys(&fib6_net_ops);
1702 	if (ret)
1703 		goto out_kmem_cache_create;
1704 
1705 	ret = __rtnl_register(PF_INET6, RTM_GETROUTE, NULL, inet6_dump_fib,
1706 			      NULL);
1707 	if (ret)
1708 		goto out_unregister_subsys;
1709 out:
1710 	return ret;
1711 
1712 out_unregister_subsys:
1713 	unregister_pernet_subsys(&fib6_net_ops);
1714 out_kmem_cache_create:
1715 	kmem_cache_destroy(fib6_node_kmem);
1716 	goto out;
1717 }
1718 
1719 void fib6_gc_cleanup(void)
1720 {
1721 	unregister_pernet_subsys(&fib6_net_ops);
1722 	kmem_cache_destroy(fib6_node_kmem);
1723 }
1724