xref: /openbmc/linux/net/ipv6/ip6_fib.c (revision 4da722ca)
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  *	Changes:
14  *	Yuji SEKIYA @USAGI:	Support default route on router node;
15  *				remove ip6_null_entry from the top of
16  *				routing table.
17  *	Ville Nuorvala:		Fixed routing subtrees.
18  */
19 
20 #define pr_fmt(fmt) "IPv6: " fmt
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>
29 #include <linux/list.h>
30 #include <linux/slab.h>
31 
32 #include <net/ipv6.h>
33 #include <net/ndisc.h>
34 #include <net/addrconf.h>
35 #include <net/lwtunnel.h>
36 
37 #include <net/ip6_fib.h>
38 #include <net/ip6_route.h>
39 
40 #define RT6_DEBUG 2
41 
42 #if RT6_DEBUG >= 3
43 #define RT6_TRACE(x...) pr_debug(x)
44 #else
45 #define RT6_TRACE(x...) do { ; } while (0)
46 #endif
47 
48 static struct kmem_cache *fib6_node_kmem __read_mostly;
49 
50 struct fib6_cleaner {
51 	struct fib6_walker w;
52 	struct net *net;
53 	int (*func)(struct rt6_info *, void *arg);
54 	int sernum;
55 	void *arg;
56 };
57 
58 #ifdef CONFIG_IPV6_SUBTREES
59 #define FWS_INIT FWS_S
60 #else
61 #define FWS_INIT FWS_L
62 #endif
63 
64 static void fib6_prune_clones(struct net *net, struct fib6_node *fn);
65 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
66 static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
67 static int fib6_walk(struct net *net, struct fib6_walker *w);
68 static int fib6_walk_continue(struct fib6_walker *w);
69 
70 /*
71  *	A routing update causes an increase of the serial number on the
72  *	affected subtree. This allows for cached routes to be asynchronously
73  *	tested when modifications are made to the destination cache as a
74  *	result of redirects, path MTU changes, etc.
75  */
76 
77 static void fib6_gc_timer_cb(unsigned long arg);
78 
79 #define FOR_WALKERS(net, w) \
80 	list_for_each_entry(w, &(net)->ipv6.fib6_walkers, lh)
81 
82 static void fib6_walker_link(struct net *net, struct fib6_walker *w)
83 {
84 	write_lock_bh(&net->ipv6.fib6_walker_lock);
85 	list_add(&w->lh, &net->ipv6.fib6_walkers);
86 	write_unlock_bh(&net->ipv6.fib6_walker_lock);
87 }
88 
89 static void fib6_walker_unlink(struct net *net, struct fib6_walker *w)
90 {
91 	write_lock_bh(&net->ipv6.fib6_walker_lock);
92 	list_del(&w->lh);
93 	write_unlock_bh(&net->ipv6.fib6_walker_lock);
94 }
95 
96 static int fib6_new_sernum(struct net *net)
97 {
98 	int new, old;
99 
100 	do {
101 		old = atomic_read(&net->ipv6.fib6_sernum);
102 		new = old < INT_MAX ? old + 1 : 1;
103 	} while (atomic_cmpxchg(&net->ipv6.fib6_sernum,
104 				old, new) != old);
105 	return new;
106 }
107 
108 enum {
109 	FIB6_NO_SERNUM_CHANGE = 0,
110 };
111 
112 /*
113  *	Auxiliary address test functions for the radix tree.
114  *
115  *	These assume a 32bit processor (although it will work on
116  *	64bit processors)
117  */
118 
119 /*
120  *	test bit
121  */
122 #if defined(__LITTLE_ENDIAN)
123 # define BITOP_BE32_SWIZZLE	(0x1F & ~7)
124 #else
125 # define BITOP_BE32_SWIZZLE	0
126 #endif
127 
128 static __be32 addr_bit_set(const void *token, int fn_bit)
129 {
130 	const __be32 *addr = token;
131 	/*
132 	 * Here,
133 	 *	1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
134 	 * is optimized version of
135 	 *	htonl(1 << ((~fn_bit)&0x1F))
136 	 * See include/asm-generic/bitops/le.h.
137 	 */
138 	return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
139 	       addr[fn_bit >> 5];
140 }
141 
142 static struct fib6_node *node_alloc(void)
143 {
144 	struct fib6_node *fn;
145 
146 	fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
147 
148 	return fn;
149 }
150 
151 static void node_free(struct fib6_node *fn)
152 {
153 	kmem_cache_free(fib6_node_kmem, fn);
154 }
155 
156 static void rt6_free_pcpu(struct rt6_info *non_pcpu_rt)
157 {
158 	int cpu;
159 
160 	if (!non_pcpu_rt->rt6i_pcpu)
161 		return;
162 
163 	for_each_possible_cpu(cpu) {
164 		struct rt6_info **ppcpu_rt;
165 		struct rt6_info *pcpu_rt;
166 
167 		ppcpu_rt = per_cpu_ptr(non_pcpu_rt->rt6i_pcpu, cpu);
168 		pcpu_rt = *ppcpu_rt;
169 		if (pcpu_rt) {
170 			dst_dev_put(&pcpu_rt->dst);
171 			dst_release(&pcpu_rt->dst);
172 			*ppcpu_rt = NULL;
173 		}
174 	}
175 
176 	free_percpu(non_pcpu_rt->rt6i_pcpu);
177 	non_pcpu_rt->rt6i_pcpu = NULL;
178 }
179 
180 static void rt6_release(struct rt6_info *rt)
181 {
182 	if (atomic_dec_and_test(&rt->rt6i_ref)) {
183 		rt6_free_pcpu(rt);
184 		dst_dev_put(&rt->dst);
185 		dst_release(&rt->dst);
186 	}
187 }
188 
189 static void fib6_link_table(struct net *net, struct fib6_table *tb)
190 {
191 	unsigned int h;
192 
193 	/*
194 	 * Initialize table lock at a single place to give lockdep a key,
195 	 * tables aren't visible prior to being linked to the list.
196 	 */
197 	rwlock_init(&tb->tb6_lock);
198 
199 	h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
200 
201 	/*
202 	 * No protection necessary, this is the only list mutatation
203 	 * operation, tables never disappear once they exist.
204 	 */
205 	hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
206 }
207 
208 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
209 
210 static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
211 {
212 	struct fib6_table *table;
213 
214 	table = kzalloc(sizeof(*table), GFP_ATOMIC);
215 	if (table) {
216 		table->tb6_id = id;
217 		table->tb6_root.leaf = net->ipv6.ip6_null_entry;
218 		table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
219 		inet_peer_base_init(&table->tb6_peers);
220 	}
221 
222 	return table;
223 }
224 
225 struct fib6_table *fib6_new_table(struct net *net, u32 id)
226 {
227 	struct fib6_table *tb;
228 
229 	if (id == 0)
230 		id = RT6_TABLE_MAIN;
231 	tb = fib6_get_table(net, id);
232 	if (tb)
233 		return tb;
234 
235 	tb = fib6_alloc_table(net, id);
236 	if (tb)
237 		fib6_link_table(net, tb);
238 
239 	return tb;
240 }
241 EXPORT_SYMBOL_GPL(fib6_new_table);
242 
243 struct fib6_table *fib6_get_table(struct net *net, u32 id)
244 {
245 	struct fib6_table *tb;
246 	struct hlist_head *head;
247 	unsigned int h;
248 
249 	if (id == 0)
250 		id = RT6_TABLE_MAIN;
251 	h = id & (FIB6_TABLE_HASHSZ - 1);
252 	rcu_read_lock();
253 	head = &net->ipv6.fib_table_hash[h];
254 	hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
255 		if (tb->tb6_id == id) {
256 			rcu_read_unlock();
257 			return tb;
258 		}
259 	}
260 	rcu_read_unlock();
261 
262 	return NULL;
263 }
264 EXPORT_SYMBOL_GPL(fib6_get_table);
265 
266 static void __net_init fib6_tables_init(struct net *net)
267 {
268 	fib6_link_table(net, net->ipv6.fib6_main_tbl);
269 	fib6_link_table(net, net->ipv6.fib6_local_tbl);
270 }
271 #else
272 
273 struct fib6_table *fib6_new_table(struct net *net, u32 id)
274 {
275 	return fib6_get_table(net, id);
276 }
277 
278 struct fib6_table *fib6_get_table(struct net *net, u32 id)
279 {
280 	  return net->ipv6.fib6_main_tbl;
281 }
282 
283 struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
284 				   int flags, pol_lookup_t lookup)
285 {
286 	struct rt6_info *rt;
287 
288 	rt = lookup(net, net->ipv6.fib6_main_tbl, fl6, flags);
289 	if (rt->dst.error == -EAGAIN) {
290 		ip6_rt_put(rt);
291 		rt = net->ipv6.ip6_null_entry;
292 		dst_hold(&rt->dst);
293 	}
294 
295 	return &rt->dst;
296 }
297 
298 static void __net_init fib6_tables_init(struct net *net)
299 {
300 	fib6_link_table(net, net->ipv6.fib6_main_tbl);
301 }
302 
303 #endif
304 
305 static int fib6_dump_node(struct fib6_walker *w)
306 {
307 	int res;
308 	struct rt6_info *rt;
309 
310 	for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
311 		res = rt6_dump_route(rt, w->args);
312 		if (res < 0) {
313 			/* Frame is full, suspend walking */
314 			w->leaf = rt;
315 			return 1;
316 		}
317 
318 		/* Multipath routes are dumped in one route with the
319 		 * RTA_MULTIPATH attribute. Jump 'rt' to point to the
320 		 * last sibling of this route (no need to dump the
321 		 * sibling routes again)
322 		 */
323 		if (rt->rt6i_nsiblings)
324 			rt = list_last_entry(&rt->rt6i_siblings,
325 					     struct rt6_info,
326 					     rt6i_siblings);
327 	}
328 	w->leaf = NULL;
329 	return 0;
330 }
331 
332 static void fib6_dump_end(struct netlink_callback *cb)
333 {
334 	struct net *net = sock_net(cb->skb->sk);
335 	struct fib6_walker *w = (void *)cb->args[2];
336 
337 	if (w) {
338 		if (cb->args[4]) {
339 			cb->args[4] = 0;
340 			fib6_walker_unlink(net, w);
341 		}
342 		cb->args[2] = 0;
343 		kfree(w);
344 	}
345 	cb->done = (void *)cb->args[3];
346 	cb->args[1] = 3;
347 }
348 
349 static int fib6_dump_done(struct netlink_callback *cb)
350 {
351 	fib6_dump_end(cb);
352 	return cb->done ? cb->done(cb) : 0;
353 }
354 
355 static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
356 			   struct netlink_callback *cb)
357 {
358 	struct net *net = sock_net(skb->sk);
359 	struct fib6_walker *w;
360 	int res;
361 
362 	w = (void *)cb->args[2];
363 	w->root = &table->tb6_root;
364 
365 	if (cb->args[4] == 0) {
366 		w->count = 0;
367 		w->skip = 0;
368 
369 		read_lock_bh(&table->tb6_lock);
370 		res = fib6_walk(net, w);
371 		read_unlock_bh(&table->tb6_lock);
372 		if (res > 0) {
373 			cb->args[4] = 1;
374 			cb->args[5] = w->root->fn_sernum;
375 		}
376 	} else {
377 		if (cb->args[5] != w->root->fn_sernum) {
378 			/* Begin at the root if the tree changed */
379 			cb->args[5] = w->root->fn_sernum;
380 			w->state = FWS_INIT;
381 			w->node = w->root;
382 			w->skip = w->count;
383 		} else
384 			w->skip = 0;
385 
386 		read_lock_bh(&table->tb6_lock);
387 		res = fib6_walk_continue(w);
388 		read_unlock_bh(&table->tb6_lock);
389 		if (res <= 0) {
390 			fib6_walker_unlink(net, w);
391 			cb->args[4] = 0;
392 		}
393 	}
394 
395 	return res;
396 }
397 
398 static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
399 {
400 	struct net *net = sock_net(skb->sk);
401 	unsigned int h, s_h;
402 	unsigned int e = 0, s_e;
403 	struct rt6_rtnl_dump_arg arg;
404 	struct fib6_walker *w;
405 	struct fib6_table *tb;
406 	struct hlist_head *head;
407 	int res = 0;
408 
409 	s_h = cb->args[0];
410 	s_e = cb->args[1];
411 
412 	w = (void *)cb->args[2];
413 	if (!w) {
414 		/* New dump:
415 		 *
416 		 * 1. hook callback destructor.
417 		 */
418 		cb->args[3] = (long)cb->done;
419 		cb->done = fib6_dump_done;
420 
421 		/*
422 		 * 2. allocate and initialize walker.
423 		 */
424 		w = kzalloc(sizeof(*w), GFP_ATOMIC);
425 		if (!w)
426 			return -ENOMEM;
427 		w->func = fib6_dump_node;
428 		cb->args[2] = (long)w;
429 	}
430 
431 	arg.skb = skb;
432 	arg.cb = cb;
433 	arg.net = net;
434 	w->args = &arg;
435 
436 	rcu_read_lock();
437 	for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
438 		e = 0;
439 		head = &net->ipv6.fib_table_hash[h];
440 		hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
441 			if (e < s_e)
442 				goto next;
443 			res = fib6_dump_table(tb, skb, cb);
444 			if (res != 0)
445 				goto out;
446 next:
447 			e++;
448 		}
449 	}
450 out:
451 	rcu_read_unlock();
452 	cb->args[1] = e;
453 	cb->args[0] = h;
454 
455 	res = res < 0 ? res : skb->len;
456 	if (res <= 0)
457 		fib6_dump_end(cb);
458 	return res;
459 }
460 
461 /*
462  *	Routing Table
463  *
464  *	return the appropriate node for a routing tree "add" operation
465  *	by either creating and inserting or by returning an existing
466  *	node.
467  */
468 
469 static struct fib6_node *fib6_add_1(struct fib6_node *root,
470 				     struct in6_addr *addr, int plen,
471 				     int offset, int allow_create,
472 				     int replace_required, int sernum,
473 				     struct netlink_ext_ack *extack)
474 {
475 	struct fib6_node *fn, *in, *ln;
476 	struct fib6_node *pn = NULL;
477 	struct rt6key *key;
478 	int	bit;
479 	__be32	dir = 0;
480 
481 	RT6_TRACE("fib6_add_1\n");
482 
483 	/* insert node in tree */
484 
485 	fn = root;
486 
487 	do {
488 		key = (struct rt6key *)((u8 *)fn->leaf + offset);
489 
490 		/*
491 		 *	Prefix match
492 		 */
493 		if (plen < fn->fn_bit ||
494 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
495 			if (!allow_create) {
496 				if (replace_required) {
497 					NL_SET_ERR_MSG(extack,
498 						       "Can not replace route - no match found");
499 					pr_warn("Can't replace route, no match found\n");
500 					return ERR_PTR(-ENOENT);
501 				}
502 				pr_warn("NLM_F_CREATE should be set when creating new route\n");
503 			}
504 			goto insert_above;
505 		}
506 
507 		/*
508 		 *	Exact match ?
509 		 */
510 
511 		if (plen == fn->fn_bit) {
512 			/* clean up an intermediate node */
513 			if (!(fn->fn_flags & RTN_RTINFO)) {
514 				rt6_release(fn->leaf);
515 				fn->leaf = NULL;
516 			}
517 
518 			fn->fn_sernum = sernum;
519 
520 			return fn;
521 		}
522 
523 		/*
524 		 *	We have more bits to go
525 		 */
526 
527 		/* Try to walk down on tree. */
528 		fn->fn_sernum = sernum;
529 		dir = addr_bit_set(addr, fn->fn_bit);
530 		pn = fn;
531 		fn = dir ? fn->right : fn->left;
532 	} while (fn);
533 
534 	if (!allow_create) {
535 		/* We should not create new node because
536 		 * NLM_F_REPLACE was specified without NLM_F_CREATE
537 		 * I assume it is safe to require NLM_F_CREATE when
538 		 * REPLACE flag is used! Later we may want to remove the
539 		 * check for replace_required, because according
540 		 * to netlink specification, NLM_F_CREATE
541 		 * MUST be specified if new route is created.
542 		 * That would keep IPv6 consistent with IPv4
543 		 */
544 		if (replace_required) {
545 			NL_SET_ERR_MSG(extack,
546 				       "Can not replace route - no match found");
547 			pr_warn("Can't replace route, no match found\n");
548 			return ERR_PTR(-ENOENT);
549 		}
550 		pr_warn("NLM_F_CREATE should be set when creating new route\n");
551 	}
552 	/*
553 	 *	We walked to the bottom of tree.
554 	 *	Create new leaf node without children.
555 	 */
556 
557 	ln = node_alloc();
558 
559 	if (!ln)
560 		return ERR_PTR(-ENOMEM);
561 	ln->fn_bit = plen;
562 
563 	ln->parent = pn;
564 	ln->fn_sernum = sernum;
565 
566 	if (dir)
567 		pn->right = ln;
568 	else
569 		pn->left  = ln;
570 
571 	return ln;
572 
573 
574 insert_above:
575 	/*
576 	 * split since we don't have a common prefix anymore or
577 	 * we have a less significant route.
578 	 * we've to insert an intermediate node on the list
579 	 * this new node will point to the one we need to create
580 	 * and the current
581 	 */
582 
583 	pn = fn->parent;
584 
585 	/* find 1st bit in difference between the 2 addrs.
586 
587 	   See comment in __ipv6_addr_diff: bit may be an invalid value,
588 	   but if it is >= plen, the value is ignored in any case.
589 	 */
590 
591 	bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
592 
593 	/*
594 	 *		(intermediate)[in]
595 	 *	          /	   \
596 	 *	(new leaf node)[ln] (old node)[fn]
597 	 */
598 	if (plen > bit) {
599 		in = node_alloc();
600 		ln = node_alloc();
601 
602 		if (!in || !ln) {
603 			if (in)
604 				node_free(in);
605 			if (ln)
606 				node_free(ln);
607 			return ERR_PTR(-ENOMEM);
608 		}
609 
610 		/*
611 		 * new intermediate node.
612 		 * RTN_RTINFO will
613 		 * be off since that an address that chooses one of
614 		 * the branches would not match less specific routes
615 		 * in the other branch
616 		 */
617 
618 		in->fn_bit = bit;
619 
620 		in->parent = pn;
621 		in->leaf = fn->leaf;
622 		atomic_inc(&in->leaf->rt6i_ref);
623 
624 		in->fn_sernum = sernum;
625 
626 		/* update parent pointer */
627 		if (dir)
628 			pn->right = in;
629 		else
630 			pn->left  = in;
631 
632 		ln->fn_bit = plen;
633 
634 		ln->parent = in;
635 		fn->parent = in;
636 
637 		ln->fn_sernum = sernum;
638 
639 		if (addr_bit_set(addr, bit)) {
640 			in->right = ln;
641 			in->left  = fn;
642 		} else {
643 			in->left  = ln;
644 			in->right = fn;
645 		}
646 	} else { /* plen <= bit */
647 
648 		/*
649 		 *		(new leaf node)[ln]
650 		 *	          /	   \
651 		 *	     (old node)[fn] NULL
652 		 */
653 
654 		ln = node_alloc();
655 
656 		if (!ln)
657 			return ERR_PTR(-ENOMEM);
658 
659 		ln->fn_bit = plen;
660 
661 		ln->parent = pn;
662 
663 		ln->fn_sernum = sernum;
664 
665 		if (dir)
666 			pn->right = ln;
667 		else
668 			pn->left  = ln;
669 
670 		if (addr_bit_set(&key->addr, plen))
671 			ln->right = fn;
672 		else
673 			ln->left  = fn;
674 
675 		fn->parent = ln;
676 	}
677 	return ln;
678 }
679 
680 static bool rt6_qualify_for_ecmp(struct rt6_info *rt)
681 {
682 	return (rt->rt6i_flags & (RTF_GATEWAY|RTF_ADDRCONF|RTF_DYNAMIC)) ==
683 	       RTF_GATEWAY;
684 }
685 
686 static void fib6_copy_metrics(u32 *mp, const struct mx6_config *mxc)
687 {
688 	int i;
689 
690 	for (i = 0; i < RTAX_MAX; i++) {
691 		if (test_bit(i, mxc->mx_valid))
692 			mp[i] = mxc->mx[i];
693 	}
694 }
695 
696 static int fib6_commit_metrics(struct dst_entry *dst, struct mx6_config *mxc)
697 {
698 	if (!mxc->mx)
699 		return 0;
700 
701 	if (dst->flags & DST_HOST) {
702 		u32 *mp = dst_metrics_write_ptr(dst);
703 
704 		if (unlikely(!mp))
705 			return -ENOMEM;
706 
707 		fib6_copy_metrics(mp, mxc);
708 	} else {
709 		dst_init_metrics(dst, mxc->mx, false);
710 
711 		/* We've stolen mx now. */
712 		mxc->mx = NULL;
713 	}
714 
715 	return 0;
716 }
717 
718 static void fib6_purge_rt(struct rt6_info *rt, struct fib6_node *fn,
719 			  struct net *net)
720 {
721 	if (atomic_read(&rt->rt6i_ref) != 1) {
722 		/* This route is used as dummy address holder in some split
723 		 * nodes. It is not leaked, but it still holds other resources,
724 		 * which must be released in time. So, scan ascendant nodes
725 		 * and replace dummy references to this route with references
726 		 * to still alive ones.
727 		 */
728 		while (fn) {
729 			if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) {
730 				fn->leaf = fib6_find_prefix(net, fn);
731 				atomic_inc(&fn->leaf->rt6i_ref);
732 				rt6_release(rt);
733 			}
734 			fn = fn->parent;
735 		}
736 		/* No more references are possible at this point. */
737 		BUG_ON(atomic_read(&rt->rt6i_ref) != 1);
738 	}
739 }
740 
741 /*
742  *	Insert routing information in a node.
743  */
744 
745 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
746 			    struct nl_info *info, struct mx6_config *mxc)
747 {
748 	struct rt6_info *iter = NULL;
749 	struct rt6_info **ins;
750 	struct rt6_info **fallback_ins = NULL;
751 	int replace = (info->nlh &&
752 		       (info->nlh->nlmsg_flags & NLM_F_REPLACE));
753 	int add = (!info->nlh ||
754 		   (info->nlh->nlmsg_flags & NLM_F_CREATE));
755 	int found = 0;
756 	bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
757 	u16 nlflags = NLM_F_EXCL;
758 	int err;
759 
760 	if (info->nlh && (info->nlh->nlmsg_flags & NLM_F_APPEND))
761 		nlflags |= NLM_F_APPEND;
762 
763 	ins = &fn->leaf;
764 
765 	for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) {
766 		/*
767 		 *	Search for duplicates
768 		 */
769 
770 		if (iter->rt6i_metric == rt->rt6i_metric) {
771 			/*
772 			 *	Same priority level
773 			 */
774 			if (info->nlh &&
775 			    (info->nlh->nlmsg_flags & NLM_F_EXCL))
776 				return -EEXIST;
777 
778 			nlflags &= ~NLM_F_EXCL;
779 			if (replace) {
780 				if (rt_can_ecmp == rt6_qualify_for_ecmp(iter)) {
781 					found++;
782 					break;
783 				}
784 				if (rt_can_ecmp)
785 					fallback_ins = fallback_ins ?: ins;
786 				goto next_iter;
787 			}
788 
789 			if (rt6_duplicate_nexthop(iter, rt)) {
790 				if (rt->rt6i_nsiblings)
791 					rt->rt6i_nsiblings = 0;
792 				if (!(iter->rt6i_flags & RTF_EXPIRES))
793 					return -EEXIST;
794 				if (!(rt->rt6i_flags & RTF_EXPIRES))
795 					rt6_clean_expires(iter);
796 				else
797 					rt6_set_expires(iter, rt->dst.expires);
798 				iter->rt6i_pmtu = rt->rt6i_pmtu;
799 				return -EEXIST;
800 			}
801 			/* If we have the same destination and the same metric,
802 			 * but not the same gateway, then the route we try to
803 			 * add is sibling to this route, increment our counter
804 			 * of siblings, and later we will add our route to the
805 			 * list.
806 			 * Only static routes (which don't have flag
807 			 * RTF_EXPIRES) are used for ECMPv6.
808 			 *
809 			 * To avoid long list, we only had siblings if the
810 			 * route have a gateway.
811 			 */
812 			if (rt_can_ecmp &&
813 			    rt6_qualify_for_ecmp(iter))
814 				rt->rt6i_nsiblings++;
815 		}
816 
817 		if (iter->rt6i_metric > rt->rt6i_metric)
818 			break;
819 
820 next_iter:
821 		ins = &iter->dst.rt6_next;
822 	}
823 
824 	if (fallback_ins && !found) {
825 		/* No ECMP-able route found, replace first non-ECMP one */
826 		ins = fallback_ins;
827 		iter = *ins;
828 		found++;
829 	}
830 
831 	/* Reset round-robin state, if necessary */
832 	if (ins == &fn->leaf)
833 		fn->rr_ptr = NULL;
834 
835 	/* Link this route to others same route. */
836 	if (rt->rt6i_nsiblings) {
837 		unsigned int rt6i_nsiblings;
838 		struct rt6_info *sibling, *temp_sibling;
839 
840 		/* Find the first route that have the same metric */
841 		sibling = fn->leaf;
842 		while (sibling) {
843 			if (sibling->rt6i_metric == rt->rt6i_metric &&
844 			    rt6_qualify_for_ecmp(sibling)) {
845 				list_add_tail(&rt->rt6i_siblings,
846 					      &sibling->rt6i_siblings);
847 				break;
848 			}
849 			sibling = sibling->dst.rt6_next;
850 		}
851 		/* For each sibling in the list, increment the counter of
852 		 * siblings. BUG() if counters does not match, list of siblings
853 		 * is broken!
854 		 */
855 		rt6i_nsiblings = 0;
856 		list_for_each_entry_safe(sibling, temp_sibling,
857 					 &rt->rt6i_siblings, rt6i_siblings) {
858 			sibling->rt6i_nsiblings++;
859 			BUG_ON(sibling->rt6i_nsiblings != rt->rt6i_nsiblings);
860 			rt6i_nsiblings++;
861 		}
862 		BUG_ON(rt6i_nsiblings != rt->rt6i_nsiblings);
863 	}
864 
865 	/*
866 	 *	insert node
867 	 */
868 	if (!replace) {
869 		if (!add)
870 			pr_warn("NLM_F_CREATE should be set when creating new route\n");
871 
872 add:
873 		nlflags |= NLM_F_CREATE;
874 		err = fib6_commit_metrics(&rt->dst, mxc);
875 		if (err)
876 			return err;
877 
878 		rt->dst.rt6_next = iter;
879 		*ins = rt;
880 		rt->rt6i_node = fn;
881 		atomic_inc(&rt->rt6i_ref);
882 		if (!info->skip_notify)
883 			inet6_rt_notify(RTM_NEWROUTE, rt, info, nlflags);
884 		info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
885 
886 		if (!(fn->fn_flags & RTN_RTINFO)) {
887 			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
888 			fn->fn_flags |= RTN_RTINFO;
889 		}
890 
891 	} else {
892 		int nsiblings;
893 
894 		if (!found) {
895 			if (add)
896 				goto add;
897 			pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
898 			return -ENOENT;
899 		}
900 
901 		err = fib6_commit_metrics(&rt->dst, mxc);
902 		if (err)
903 			return err;
904 
905 		*ins = rt;
906 		rt->rt6i_node = fn;
907 		rt->dst.rt6_next = iter->dst.rt6_next;
908 		atomic_inc(&rt->rt6i_ref);
909 		if (!info->skip_notify)
910 			inet6_rt_notify(RTM_NEWROUTE, rt, info, NLM_F_REPLACE);
911 		if (!(fn->fn_flags & RTN_RTINFO)) {
912 			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
913 			fn->fn_flags |= RTN_RTINFO;
914 		}
915 		nsiblings = iter->rt6i_nsiblings;
916 		fib6_purge_rt(iter, fn, info->nl_net);
917 		rt6_release(iter);
918 
919 		if (nsiblings) {
920 			/* Replacing an ECMP route, remove all siblings */
921 			ins = &rt->dst.rt6_next;
922 			iter = *ins;
923 			while (iter) {
924 				if (iter->rt6i_metric > rt->rt6i_metric)
925 					break;
926 				if (rt6_qualify_for_ecmp(iter)) {
927 					*ins = iter->dst.rt6_next;
928 					fib6_purge_rt(iter, fn, info->nl_net);
929 					rt6_release(iter);
930 					nsiblings--;
931 				} else {
932 					ins = &iter->dst.rt6_next;
933 				}
934 				iter = *ins;
935 			}
936 			WARN_ON(nsiblings != 0);
937 		}
938 	}
939 
940 	return 0;
941 }
942 
943 static void fib6_start_gc(struct net *net, struct rt6_info *rt)
944 {
945 	if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
946 	    (rt->rt6i_flags & (RTF_EXPIRES | RTF_CACHE)))
947 		mod_timer(&net->ipv6.ip6_fib_timer,
948 			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
949 }
950 
951 void fib6_force_start_gc(struct net *net)
952 {
953 	if (!timer_pending(&net->ipv6.ip6_fib_timer))
954 		mod_timer(&net->ipv6.ip6_fib_timer,
955 			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
956 }
957 
958 /*
959  *	Add routing information to the routing tree.
960  *	<destination addr>/<source addr>
961  *	with source addr info in sub-trees
962  */
963 
964 int fib6_add(struct fib6_node *root, struct rt6_info *rt,
965 	     struct nl_info *info, struct mx6_config *mxc,
966 	     struct netlink_ext_ack *extack)
967 {
968 	struct fib6_node *fn, *pn = NULL;
969 	int err = -ENOMEM;
970 	int allow_create = 1;
971 	int replace_required = 0;
972 	int sernum = fib6_new_sernum(info->nl_net);
973 
974 	if (WARN_ON_ONCE(!atomic_read(&rt->dst.__refcnt)))
975 		return -EINVAL;
976 
977 	if (info->nlh) {
978 		if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
979 			allow_create = 0;
980 		if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
981 			replace_required = 1;
982 	}
983 	if (!allow_create && !replace_required)
984 		pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
985 
986 	fn = fib6_add_1(root, &rt->rt6i_dst.addr, rt->rt6i_dst.plen,
987 			offsetof(struct rt6_info, rt6i_dst), allow_create,
988 			replace_required, sernum, extack);
989 	if (IS_ERR(fn)) {
990 		err = PTR_ERR(fn);
991 		fn = NULL;
992 		goto out;
993 	}
994 
995 	pn = fn;
996 
997 #ifdef CONFIG_IPV6_SUBTREES
998 	if (rt->rt6i_src.plen) {
999 		struct fib6_node *sn;
1000 
1001 		if (!fn->subtree) {
1002 			struct fib6_node *sfn;
1003 
1004 			/*
1005 			 * Create subtree.
1006 			 *
1007 			 *		fn[main tree]
1008 			 *		|
1009 			 *		sfn[subtree root]
1010 			 *		   \
1011 			 *		    sn[new leaf node]
1012 			 */
1013 
1014 			/* Create subtree root node */
1015 			sfn = node_alloc();
1016 			if (!sfn)
1017 				goto st_failure;
1018 
1019 			sfn->leaf = info->nl_net->ipv6.ip6_null_entry;
1020 			atomic_inc(&info->nl_net->ipv6.ip6_null_entry->rt6i_ref);
1021 			sfn->fn_flags = RTN_ROOT;
1022 			sfn->fn_sernum = sernum;
1023 
1024 			/* Now add the first leaf node to new subtree */
1025 
1026 			sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
1027 					rt->rt6i_src.plen,
1028 					offsetof(struct rt6_info, rt6i_src),
1029 					allow_create, replace_required, sernum,
1030 					extack);
1031 
1032 			if (IS_ERR(sn)) {
1033 				/* If it is failed, discard just allocated
1034 				   root, and then (in st_failure) stale node
1035 				   in main tree.
1036 				 */
1037 				node_free(sfn);
1038 				err = PTR_ERR(sn);
1039 				goto st_failure;
1040 			}
1041 
1042 			/* Now link new subtree to main tree */
1043 			sfn->parent = fn;
1044 			fn->subtree = sfn;
1045 		} else {
1046 			sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
1047 					rt->rt6i_src.plen,
1048 					offsetof(struct rt6_info, rt6i_src),
1049 					allow_create, replace_required, sernum,
1050 					extack);
1051 
1052 			if (IS_ERR(sn)) {
1053 				err = PTR_ERR(sn);
1054 				goto st_failure;
1055 			}
1056 		}
1057 
1058 		if (!fn->leaf) {
1059 			fn->leaf = rt;
1060 			atomic_inc(&rt->rt6i_ref);
1061 		}
1062 		fn = sn;
1063 	}
1064 #endif
1065 
1066 	err = fib6_add_rt2node(fn, rt, info, mxc);
1067 	if (!err) {
1068 		fib6_start_gc(info->nl_net, rt);
1069 		if (!(rt->rt6i_flags & RTF_CACHE))
1070 			fib6_prune_clones(info->nl_net, pn);
1071 	}
1072 
1073 out:
1074 	if (err) {
1075 #ifdef CONFIG_IPV6_SUBTREES
1076 		/*
1077 		 * If fib6_add_1 has cleared the old leaf pointer in the
1078 		 * super-tree leaf node we have to find a new one for it.
1079 		 */
1080 		if (pn != fn && pn->leaf == rt) {
1081 			pn->leaf = NULL;
1082 			atomic_dec(&rt->rt6i_ref);
1083 		}
1084 		if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
1085 			pn->leaf = fib6_find_prefix(info->nl_net, pn);
1086 #if RT6_DEBUG >= 2
1087 			if (!pn->leaf) {
1088 				WARN_ON(pn->leaf == NULL);
1089 				pn->leaf = info->nl_net->ipv6.ip6_null_entry;
1090 			}
1091 #endif
1092 			atomic_inc(&pn->leaf->rt6i_ref);
1093 		}
1094 #endif
1095 		/* Always release dst as dst->__refcnt is guaranteed
1096 		 * to be taken before entering this function
1097 		 */
1098 		dst_release_immediate(&rt->dst);
1099 	}
1100 	return err;
1101 
1102 #ifdef CONFIG_IPV6_SUBTREES
1103 	/* Subtree creation failed, probably main tree node
1104 	   is orphan. If it is, shoot it.
1105 	 */
1106 st_failure:
1107 	if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
1108 		fib6_repair_tree(info->nl_net, fn);
1109 	/* Always release dst as dst->__refcnt is guaranteed
1110 	 * to be taken before entering this function
1111 	 */
1112 	dst_release_immediate(&rt->dst);
1113 	return err;
1114 #endif
1115 }
1116 
1117 /*
1118  *	Routing tree lookup
1119  *
1120  */
1121 
1122 struct lookup_args {
1123 	int			offset;		/* key offset on rt6_info	*/
1124 	const struct in6_addr	*addr;		/* search key			*/
1125 };
1126 
1127 static struct fib6_node *fib6_lookup_1(struct fib6_node *root,
1128 				       struct lookup_args *args)
1129 {
1130 	struct fib6_node *fn;
1131 	__be32 dir;
1132 
1133 	if (unlikely(args->offset == 0))
1134 		return NULL;
1135 
1136 	/*
1137 	 *	Descend on a tree
1138 	 */
1139 
1140 	fn = root;
1141 
1142 	for (;;) {
1143 		struct fib6_node *next;
1144 
1145 		dir = addr_bit_set(args->addr, fn->fn_bit);
1146 
1147 		next = dir ? fn->right : fn->left;
1148 
1149 		if (next) {
1150 			fn = next;
1151 			continue;
1152 		}
1153 		break;
1154 	}
1155 
1156 	while (fn) {
1157 		if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
1158 			struct rt6key *key;
1159 
1160 			key = (struct rt6key *) ((u8 *) fn->leaf +
1161 						 args->offset);
1162 
1163 			if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
1164 #ifdef CONFIG_IPV6_SUBTREES
1165 				if (fn->subtree) {
1166 					struct fib6_node *sfn;
1167 					sfn = fib6_lookup_1(fn->subtree,
1168 							    args + 1);
1169 					if (!sfn)
1170 						goto backtrack;
1171 					fn = sfn;
1172 				}
1173 #endif
1174 				if (fn->fn_flags & RTN_RTINFO)
1175 					return fn;
1176 			}
1177 		}
1178 #ifdef CONFIG_IPV6_SUBTREES
1179 backtrack:
1180 #endif
1181 		if (fn->fn_flags & RTN_ROOT)
1182 			break;
1183 
1184 		fn = fn->parent;
1185 	}
1186 
1187 	return NULL;
1188 }
1189 
1190 struct fib6_node *fib6_lookup(struct fib6_node *root, const struct in6_addr *daddr,
1191 			      const struct in6_addr *saddr)
1192 {
1193 	struct fib6_node *fn;
1194 	struct lookup_args args[] = {
1195 		{
1196 			.offset = offsetof(struct rt6_info, rt6i_dst),
1197 			.addr = daddr,
1198 		},
1199 #ifdef CONFIG_IPV6_SUBTREES
1200 		{
1201 			.offset = offsetof(struct rt6_info, rt6i_src),
1202 			.addr = saddr,
1203 		},
1204 #endif
1205 		{
1206 			.offset = 0,	/* sentinel */
1207 		}
1208 	};
1209 
1210 	fn = fib6_lookup_1(root, daddr ? args : args + 1);
1211 	if (!fn || fn->fn_flags & RTN_TL_ROOT)
1212 		fn = root;
1213 
1214 	return fn;
1215 }
1216 
1217 /*
1218  *	Get node with specified destination prefix (and source prefix,
1219  *	if subtrees are used)
1220  */
1221 
1222 
1223 static struct fib6_node *fib6_locate_1(struct fib6_node *root,
1224 				       const struct in6_addr *addr,
1225 				       int plen, int offset)
1226 {
1227 	struct fib6_node *fn;
1228 
1229 	for (fn = root; fn ; ) {
1230 		struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
1231 
1232 		/*
1233 		 *	Prefix match
1234 		 */
1235 		if (plen < fn->fn_bit ||
1236 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1237 			return NULL;
1238 
1239 		if (plen == fn->fn_bit)
1240 			return fn;
1241 
1242 		/*
1243 		 *	We have more bits to go
1244 		 */
1245 		if (addr_bit_set(addr, fn->fn_bit))
1246 			fn = fn->right;
1247 		else
1248 			fn = fn->left;
1249 	}
1250 	return NULL;
1251 }
1252 
1253 struct fib6_node *fib6_locate(struct fib6_node *root,
1254 			      const struct in6_addr *daddr, int dst_len,
1255 			      const struct in6_addr *saddr, int src_len)
1256 {
1257 	struct fib6_node *fn;
1258 
1259 	fn = fib6_locate_1(root, daddr, dst_len,
1260 			   offsetof(struct rt6_info, rt6i_dst));
1261 
1262 #ifdef CONFIG_IPV6_SUBTREES
1263 	if (src_len) {
1264 		WARN_ON(saddr == NULL);
1265 		if (fn && fn->subtree)
1266 			fn = fib6_locate_1(fn->subtree, saddr, src_len,
1267 					   offsetof(struct rt6_info, rt6i_src));
1268 	}
1269 #endif
1270 
1271 	if (fn && fn->fn_flags & RTN_RTINFO)
1272 		return fn;
1273 
1274 	return NULL;
1275 }
1276 
1277 
1278 /*
1279  *	Deletion
1280  *
1281  */
1282 
1283 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn)
1284 {
1285 	if (fn->fn_flags & RTN_ROOT)
1286 		return net->ipv6.ip6_null_entry;
1287 
1288 	while (fn) {
1289 		if (fn->left)
1290 			return fn->left->leaf;
1291 		if (fn->right)
1292 			return fn->right->leaf;
1293 
1294 		fn = FIB6_SUBTREE(fn);
1295 	}
1296 	return NULL;
1297 }
1298 
1299 /*
1300  *	Called to trim the tree of intermediate nodes when possible. "fn"
1301  *	is the node we want to try and remove.
1302  */
1303 
1304 static struct fib6_node *fib6_repair_tree(struct net *net,
1305 					   struct fib6_node *fn)
1306 {
1307 	int children;
1308 	int nstate;
1309 	struct fib6_node *child, *pn;
1310 	struct fib6_walker *w;
1311 	int iter = 0;
1312 
1313 	for (;;) {
1314 		RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1315 		iter++;
1316 
1317 		WARN_ON(fn->fn_flags & RTN_RTINFO);
1318 		WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1319 		WARN_ON(fn->leaf);
1320 
1321 		children = 0;
1322 		child = NULL;
1323 		if (fn->right)
1324 			child = fn->right, children |= 1;
1325 		if (fn->left)
1326 			child = fn->left, children |= 2;
1327 
1328 		if (children == 3 || FIB6_SUBTREE(fn)
1329 #ifdef CONFIG_IPV6_SUBTREES
1330 		    /* Subtree root (i.e. fn) may have one child */
1331 		    || (children && fn->fn_flags & RTN_ROOT)
1332 #endif
1333 		    ) {
1334 			fn->leaf = fib6_find_prefix(net, fn);
1335 #if RT6_DEBUG >= 2
1336 			if (!fn->leaf) {
1337 				WARN_ON(!fn->leaf);
1338 				fn->leaf = net->ipv6.ip6_null_entry;
1339 			}
1340 #endif
1341 			atomic_inc(&fn->leaf->rt6i_ref);
1342 			return fn->parent;
1343 		}
1344 
1345 		pn = fn->parent;
1346 #ifdef CONFIG_IPV6_SUBTREES
1347 		if (FIB6_SUBTREE(pn) == fn) {
1348 			WARN_ON(!(fn->fn_flags & RTN_ROOT));
1349 			FIB6_SUBTREE(pn) = NULL;
1350 			nstate = FWS_L;
1351 		} else {
1352 			WARN_ON(fn->fn_flags & RTN_ROOT);
1353 #endif
1354 			if (pn->right == fn)
1355 				pn->right = child;
1356 			else if (pn->left == fn)
1357 				pn->left = child;
1358 #if RT6_DEBUG >= 2
1359 			else
1360 				WARN_ON(1);
1361 #endif
1362 			if (child)
1363 				child->parent = pn;
1364 			nstate = FWS_R;
1365 #ifdef CONFIG_IPV6_SUBTREES
1366 		}
1367 #endif
1368 
1369 		read_lock(&net->ipv6.fib6_walker_lock);
1370 		FOR_WALKERS(net, w) {
1371 			if (!child) {
1372 				if (w->root == fn) {
1373 					w->root = w->node = NULL;
1374 					RT6_TRACE("W %p adjusted by delroot 1\n", w);
1375 				} else if (w->node == fn) {
1376 					RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1377 					w->node = pn;
1378 					w->state = nstate;
1379 				}
1380 			} else {
1381 				if (w->root == fn) {
1382 					w->root = child;
1383 					RT6_TRACE("W %p adjusted by delroot 2\n", w);
1384 				}
1385 				if (w->node == fn) {
1386 					w->node = child;
1387 					if (children&2) {
1388 						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1389 						w->state = w->state >= FWS_R ? FWS_U : FWS_INIT;
1390 					} else {
1391 						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1392 						w->state = w->state >= FWS_C ? FWS_U : FWS_INIT;
1393 					}
1394 				}
1395 			}
1396 		}
1397 		read_unlock(&net->ipv6.fib6_walker_lock);
1398 
1399 		node_free(fn);
1400 		if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
1401 			return pn;
1402 
1403 		rt6_release(pn->leaf);
1404 		pn->leaf = NULL;
1405 		fn = pn;
1406 	}
1407 }
1408 
1409 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
1410 			   struct nl_info *info)
1411 {
1412 	struct fib6_walker *w;
1413 	struct rt6_info *rt = *rtp;
1414 	struct net *net = info->nl_net;
1415 
1416 	RT6_TRACE("fib6_del_route\n");
1417 
1418 	/* Unlink it */
1419 	*rtp = rt->dst.rt6_next;
1420 	rt->rt6i_node = NULL;
1421 	net->ipv6.rt6_stats->fib_rt_entries--;
1422 	net->ipv6.rt6_stats->fib_discarded_routes++;
1423 
1424 	/* Reset round-robin state, if necessary */
1425 	if (fn->rr_ptr == rt)
1426 		fn->rr_ptr = NULL;
1427 
1428 	/* Remove this entry from other siblings */
1429 	if (rt->rt6i_nsiblings) {
1430 		struct rt6_info *sibling, *next_sibling;
1431 
1432 		list_for_each_entry_safe(sibling, next_sibling,
1433 					 &rt->rt6i_siblings, rt6i_siblings)
1434 			sibling->rt6i_nsiblings--;
1435 		rt->rt6i_nsiblings = 0;
1436 		list_del_init(&rt->rt6i_siblings);
1437 	}
1438 
1439 	/* Adjust walkers */
1440 	read_lock(&net->ipv6.fib6_walker_lock);
1441 	FOR_WALKERS(net, w) {
1442 		if (w->state == FWS_C && w->leaf == rt) {
1443 			RT6_TRACE("walker %p adjusted by delroute\n", w);
1444 			w->leaf = rt->dst.rt6_next;
1445 			if (!w->leaf)
1446 				w->state = FWS_U;
1447 		}
1448 	}
1449 	read_unlock(&net->ipv6.fib6_walker_lock);
1450 
1451 	rt->dst.rt6_next = NULL;
1452 
1453 	/* If it was last route, expunge its radix tree node */
1454 	if (!fn->leaf) {
1455 		fn->fn_flags &= ~RTN_RTINFO;
1456 		net->ipv6.rt6_stats->fib_route_nodes--;
1457 		fn = fib6_repair_tree(net, fn);
1458 	}
1459 
1460 	fib6_purge_rt(rt, fn, net);
1461 
1462 	if (!info->skip_notify)
1463 		inet6_rt_notify(RTM_DELROUTE, rt, info, 0);
1464 	rt6_release(rt);
1465 }
1466 
1467 int fib6_del(struct rt6_info *rt, struct nl_info *info)
1468 {
1469 	struct net *net = info->nl_net;
1470 	struct fib6_node *fn = rt->rt6i_node;
1471 	struct rt6_info **rtp;
1472 
1473 #if RT6_DEBUG >= 2
1474 	if (rt->dst.obsolete > 0) {
1475 		WARN_ON(fn);
1476 		return -ENOENT;
1477 	}
1478 #endif
1479 	if (!fn || rt == net->ipv6.ip6_null_entry)
1480 		return -ENOENT;
1481 
1482 	WARN_ON(!(fn->fn_flags & RTN_RTINFO));
1483 
1484 	if (!(rt->rt6i_flags & RTF_CACHE)) {
1485 		struct fib6_node *pn = fn;
1486 #ifdef CONFIG_IPV6_SUBTREES
1487 		/* clones of this route might be in another subtree */
1488 		if (rt->rt6i_src.plen) {
1489 			while (!(pn->fn_flags & RTN_ROOT))
1490 				pn = pn->parent;
1491 			pn = pn->parent;
1492 		}
1493 #endif
1494 		fib6_prune_clones(info->nl_net, pn);
1495 	}
1496 
1497 	/*
1498 	 *	Walk the leaf entries looking for ourself
1499 	 */
1500 
1501 	for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) {
1502 		if (*rtp == rt) {
1503 			fib6_del_route(fn, rtp, info);
1504 			return 0;
1505 		}
1506 	}
1507 	return -ENOENT;
1508 }
1509 
1510 /*
1511  *	Tree traversal function.
1512  *
1513  *	Certainly, it is not interrupt safe.
1514  *	However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1515  *	It means, that we can modify tree during walking
1516  *	and use this function for garbage collection, clone pruning,
1517  *	cleaning tree when a device goes down etc. etc.
1518  *
1519  *	It guarantees that every node will be traversed,
1520  *	and that it will be traversed only once.
1521  *
1522  *	Callback function w->func may return:
1523  *	0 -> continue walking.
1524  *	positive value -> walking is suspended (used by tree dumps,
1525  *	and probably by gc, if it will be split to several slices)
1526  *	negative value -> terminate walking.
1527  *
1528  *	The function itself returns:
1529  *	0   -> walk is complete.
1530  *	>0  -> walk is incomplete (i.e. suspended)
1531  *	<0  -> walk is terminated by an error.
1532  */
1533 
1534 static int fib6_walk_continue(struct fib6_walker *w)
1535 {
1536 	struct fib6_node *fn, *pn;
1537 
1538 	for (;;) {
1539 		fn = w->node;
1540 		if (!fn)
1541 			return 0;
1542 
1543 		if (w->prune && fn != w->root &&
1544 		    fn->fn_flags & RTN_RTINFO && w->state < FWS_C) {
1545 			w->state = FWS_C;
1546 			w->leaf = fn->leaf;
1547 		}
1548 		switch (w->state) {
1549 #ifdef CONFIG_IPV6_SUBTREES
1550 		case FWS_S:
1551 			if (FIB6_SUBTREE(fn)) {
1552 				w->node = FIB6_SUBTREE(fn);
1553 				continue;
1554 			}
1555 			w->state = FWS_L;
1556 #endif
1557 		case FWS_L:
1558 			if (fn->left) {
1559 				w->node = fn->left;
1560 				w->state = FWS_INIT;
1561 				continue;
1562 			}
1563 			w->state = FWS_R;
1564 		case FWS_R:
1565 			if (fn->right) {
1566 				w->node = fn->right;
1567 				w->state = FWS_INIT;
1568 				continue;
1569 			}
1570 			w->state = FWS_C;
1571 			w->leaf = fn->leaf;
1572 		case FWS_C:
1573 			if (w->leaf && fn->fn_flags & RTN_RTINFO) {
1574 				int err;
1575 
1576 				if (w->skip) {
1577 					w->skip--;
1578 					goto skip;
1579 				}
1580 
1581 				err = w->func(w);
1582 				if (err)
1583 					return err;
1584 
1585 				w->count++;
1586 				continue;
1587 			}
1588 skip:
1589 			w->state = FWS_U;
1590 		case FWS_U:
1591 			if (fn == w->root)
1592 				return 0;
1593 			pn = fn->parent;
1594 			w->node = pn;
1595 #ifdef CONFIG_IPV6_SUBTREES
1596 			if (FIB6_SUBTREE(pn) == fn) {
1597 				WARN_ON(!(fn->fn_flags & RTN_ROOT));
1598 				w->state = FWS_L;
1599 				continue;
1600 			}
1601 #endif
1602 			if (pn->left == fn) {
1603 				w->state = FWS_R;
1604 				continue;
1605 			}
1606 			if (pn->right == fn) {
1607 				w->state = FWS_C;
1608 				w->leaf = w->node->leaf;
1609 				continue;
1610 			}
1611 #if RT6_DEBUG >= 2
1612 			WARN_ON(1);
1613 #endif
1614 		}
1615 	}
1616 }
1617 
1618 static int fib6_walk(struct net *net, struct fib6_walker *w)
1619 {
1620 	int res;
1621 
1622 	w->state = FWS_INIT;
1623 	w->node = w->root;
1624 
1625 	fib6_walker_link(net, w);
1626 	res = fib6_walk_continue(w);
1627 	if (res <= 0)
1628 		fib6_walker_unlink(net, w);
1629 	return res;
1630 }
1631 
1632 static int fib6_clean_node(struct fib6_walker *w)
1633 {
1634 	int res;
1635 	struct rt6_info *rt;
1636 	struct fib6_cleaner *c = container_of(w, struct fib6_cleaner, w);
1637 	struct nl_info info = {
1638 		.nl_net = c->net,
1639 	};
1640 
1641 	if (c->sernum != FIB6_NO_SERNUM_CHANGE &&
1642 	    w->node->fn_sernum != c->sernum)
1643 		w->node->fn_sernum = c->sernum;
1644 
1645 	if (!c->func) {
1646 		WARN_ON_ONCE(c->sernum == FIB6_NO_SERNUM_CHANGE);
1647 		w->leaf = NULL;
1648 		return 0;
1649 	}
1650 
1651 	for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
1652 		res = c->func(rt, c->arg);
1653 		if (res < 0) {
1654 			w->leaf = rt;
1655 			res = fib6_del(rt, &info);
1656 			if (res) {
1657 #if RT6_DEBUG >= 2
1658 				pr_debug("%s: del failed: rt=%p@%p err=%d\n",
1659 					 __func__, rt, rt->rt6i_node, res);
1660 #endif
1661 				continue;
1662 			}
1663 			return 0;
1664 		}
1665 		WARN_ON(res != 0);
1666 	}
1667 	w->leaf = rt;
1668 	return 0;
1669 }
1670 
1671 /*
1672  *	Convenient frontend to tree walker.
1673  *
1674  *	func is called on each route.
1675  *		It may return -1 -> delete this route.
1676  *		              0  -> continue walking
1677  *
1678  *	prune==1 -> only immediate children of node (certainly,
1679  *	ignoring pure split nodes) will be scanned.
1680  */
1681 
1682 static void fib6_clean_tree(struct net *net, struct fib6_node *root,
1683 			    int (*func)(struct rt6_info *, void *arg),
1684 			    bool prune, int sernum, void *arg)
1685 {
1686 	struct fib6_cleaner c;
1687 
1688 	c.w.root = root;
1689 	c.w.func = fib6_clean_node;
1690 	c.w.prune = prune;
1691 	c.w.count = 0;
1692 	c.w.skip = 0;
1693 	c.func = func;
1694 	c.sernum = sernum;
1695 	c.arg = arg;
1696 	c.net = net;
1697 
1698 	fib6_walk(net, &c.w);
1699 }
1700 
1701 static void __fib6_clean_all(struct net *net,
1702 			     int (*func)(struct rt6_info *, void *),
1703 			     int sernum, void *arg)
1704 {
1705 	struct fib6_table *table;
1706 	struct hlist_head *head;
1707 	unsigned int h;
1708 
1709 	rcu_read_lock();
1710 	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
1711 		head = &net->ipv6.fib_table_hash[h];
1712 		hlist_for_each_entry_rcu(table, head, tb6_hlist) {
1713 			write_lock_bh(&table->tb6_lock);
1714 			fib6_clean_tree(net, &table->tb6_root,
1715 					func, false, sernum, arg);
1716 			write_unlock_bh(&table->tb6_lock);
1717 		}
1718 	}
1719 	rcu_read_unlock();
1720 }
1721 
1722 void fib6_clean_all(struct net *net, int (*func)(struct rt6_info *, void *),
1723 		    void *arg)
1724 {
1725 	__fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg);
1726 }
1727 
1728 static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1729 {
1730 	if (rt->rt6i_flags & RTF_CACHE) {
1731 		RT6_TRACE("pruning clone %p\n", rt);
1732 		return -1;
1733 	}
1734 
1735 	return 0;
1736 }
1737 
1738 static void fib6_prune_clones(struct net *net, struct fib6_node *fn)
1739 {
1740 	fib6_clean_tree(net, fn, fib6_prune_clone, true,
1741 			FIB6_NO_SERNUM_CHANGE, NULL);
1742 }
1743 
1744 static void fib6_flush_trees(struct net *net)
1745 {
1746 	int new_sernum = fib6_new_sernum(net);
1747 
1748 	__fib6_clean_all(net, NULL, new_sernum, NULL);
1749 }
1750 
1751 /*
1752  *	Garbage collection
1753  */
1754 
1755 struct fib6_gc_args
1756 {
1757 	int			timeout;
1758 	int			more;
1759 };
1760 
1761 static int fib6_age(struct rt6_info *rt, void *arg)
1762 {
1763 	struct fib6_gc_args *gc_args = arg;
1764 	unsigned long now = jiffies;
1765 
1766 	/*
1767 	 *	check addrconf expiration here.
1768 	 *	Routes are expired even if they are in use.
1769 	 *
1770 	 *	Also age clones. Note, that clones are aged out
1771 	 *	only if they are not in use now.
1772 	 */
1773 
1774 	if (rt->rt6i_flags & RTF_EXPIRES && rt->dst.expires) {
1775 		if (time_after(now, rt->dst.expires)) {
1776 			RT6_TRACE("expiring %p\n", rt);
1777 			return -1;
1778 		}
1779 		gc_args->more++;
1780 	} else if (rt->rt6i_flags & RTF_CACHE) {
1781 		if (atomic_read(&rt->dst.__refcnt) == 1 &&
1782 		    time_after_eq(now, rt->dst.lastuse + gc_args->timeout)) {
1783 			RT6_TRACE("aging clone %p\n", rt);
1784 			return -1;
1785 		} else if (rt->rt6i_flags & RTF_GATEWAY) {
1786 			struct neighbour *neigh;
1787 			__u8 neigh_flags = 0;
1788 
1789 			neigh = dst_neigh_lookup(&rt->dst, &rt->rt6i_gateway);
1790 			if (neigh) {
1791 				neigh_flags = neigh->flags;
1792 				neigh_release(neigh);
1793 			}
1794 			if (!(neigh_flags & NTF_ROUTER)) {
1795 				RT6_TRACE("purging route %p via non-router but gateway\n",
1796 					  rt);
1797 				return -1;
1798 			}
1799 		}
1800 		gc_args->more++;
1801 	}
1802 
1803 	return 0;
1804 }
1805 
1806 void fib6_run_gc(unsigned long expires, struct net *net, bool force)
1807 {
1808 	struct fib6_gc_args gc_args;
1809 	unsigned long now;
1810 
1811 	if (force) {
1812 		spin_lock_bh(&net->ipv6.fib6_gc_lock);
1813 	} else if (!spin_trylock_bh(&net->ipv6.fib6_gc_lock)) {
1814 		mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
1815 		return;
1816 	}
1817 	gc_args.timeout = expires ? (int)expires :
1818 			  net->ipv6.sysctl.ip6_rt_gc_interval;
1819 	gc_args.more = 0;
1820 
1821 	fib6_clean_all(net, fib6_age, &gc_args);
1822 	now = jiffies;
1823 	net->ipv6.ip6_rt_last_gc = now;
1824 
1825 	if (gc_args.more)
1826 		mod_timer(&net->ipv6.ip6_fib_timer,
1827 			  round_jiffies(now
1828 					+ net->ipv6.sysctl.ip6_rt_gc_interval));
1829 	else
1830 		del_timer(&net->ipv6.ip6_fib_timer);
1831 	spin_unlock_bh(&net->ipv6.fib6_gc_lock);
1832 }
1833 
1834 static void fib6_gc_timer_cb(unsigned long arg)
1835 {
1836 	fib6_run_gc(0, (struct net *)arg, true);
1837 }
1838 
1839 static int __net_init fib6_net_init(struct net *net)
1840 {
1841 	size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
1842 
1843 	spin_lock_init(&net->ipv6.fib6_gc_lock);
1844 	rwlock_init(&net->ipv6.fib6_walker_lock);
1845 	INIT_LIST_HEAD(&net->ipv6.fib6_walkers);
1846 	setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (unsigned long)net);
1847 
1848 	net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
1849 	if (!net->ipv6.rt6_stats)
1850 		goto out_timer;
1851 
1852 	/* Avoid false sharing : Use at least a full cache line */
1853 	size = max_t(size_t, size, L1_CACHE_BYTES);
1854 
1855 	net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
1856 	if (!net->ipv6.fib_table_hash)
1857 		goto out_rt6_stats;
1858 
1859 	net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
1860 					  GFP_KERNEL);
1861 	if (!net->ipv6.fib6_main_tbl)
1862 		goto out_fib_table_hash;
1863 
1864 	net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
1865 	net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1866 	net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
1867 		RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1868 	inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
1869 
1870 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1871 	net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
1872 					   GFP_KERNEL);
1873 	if (!net->ipv6.fib6_local_tbl)
1874 		goto out_fib6_main_tbl;
1875 	net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
1876 	net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1877 	net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
1878 		RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1879 	inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
1880 #endif
1881 	fib6_tables_init(net);
1882 
1883 	return 0;
1884 
1885 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1886 out_fib6_main_tbl:
1887 	kfree(net->ipv6.fib6_main_tbl);
1888 #endif
1889 out_fib_table_hash:
1890 	kfree(net->ipv6.fib_table_hash);
1891 out_rt6_stats:
1892 	kfree(net->ipv6.rt6_stats);
1893 out_timer:
1894 	return -ENOMEM;
1895 }
1896 
1897 static void fib6_net_exit(struct net *net)
1898 {
1899 	rt6_ifdown(net, NULL);
1900 	del_timer_sync(&net->ipv6.ip6_fib_timer);
1901 
1902 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1903 	inetpeer_invalidate_tree(&net->ipv6.fib6_local_tbl->tb6_peers);
1904 	kfree(net->ipv6.fib6_local_tbl);
1905 #endif
1906 	inetpeer_invalidate_tree(&net->ipv6.fib6_main_tbl->tb6_peers);
1907 	kfree(net->ipv6.fib6_main_tbl);
1908 	kfree(net->ipv6.fib_table_hash);
1909 	kfree(net->ipv6.rt6_stats);
1910 }
1911 
1912 static struct pernet_operations fib6_net_ops = {
1913 	.init = fib6_net_init,
1914 	.exit = fib6_net_exit,
1915 };
1916 
1917 int __init fib6_init(void)
1918 {
1919 	int ret = -ENOMEM;
1920 
1921 	fib6_node_kmem = kmem_cache_create("fib6_nodes",
1922 					   sizeof(struct fib6_node),
1923 					   0, SLAB_HWCACHE_ALIGN,
1924 					   NULL);
1925 	if (!fib6_node_kmem)
1926 		goto out;
1927 
1928 	ret = register_pernet_subsys(&fib6_net_ops);
1929 	if (ret)
1930 		goto out_kmem_cache_create;
1931 
1932 	ret = __rtnl_register(PF_INET6, RTM_GETROUTE, NULL, inet6_dump_fib,
1933 			      NULL);
1934 	if (ret)
1935 		goto out_unregister_subsys;
1936 
1937 	__fib6_flush_trees = fib6_flush_trees;
1938 out:
1939 	return ret;
1940 
1941 out_unregister_subsys:
1942 	unregister_pernet_subsys(&fib6_net_ops);
1943 out_kmem_cache_create:
1944 	kmem_cache_destroy(fib6_node_kmem);
1945 	goto out;
1946 }
1947 
1948 void fib6_gc_cleanup(void)
1949 {
1950 	unregister_pernet_subsys(&fib6_net_ops);
1951 	kmem_cache_destroy(fib6_node_kmem);
1952 }
1953 
1954 #ifdef CONFIG_PROC_FS
1955 
1956 struct ipv6_route_iter {
1957 	struct seq_net_private p;
1958 	struct fib6_walker w;
1959 	loff_t skip;
1960 	struct fib6_table *tbl;
1961 	int sernum;
1962 };
1963 
1964 static int ipv6_route_seq_show(struct seq_file *seq, void *v)
1965 {
1966 	struct rt6_info *rt = v;
1967 	struct ipv6_route_iter *iter = seq->private;
1968 
1969 	seq_printf(seq, "%pi6 %02x ", &rt->rt6i_dst.addr, rt->rt6i_dst.plen);
1970 
1971 #ifdef CONFIG_IPV6_SUBTREES
1972 	seq_printf(seq, "%pi6 %02x ", &rt->rt6i_src.addr, rt->rt6i_src.plen);
1973 #else
1974 	seq_puts(seq, "00000000000000000000000000000000 00 ");
1975 #endif
1976 	if (rt->rt6i_flags & RTF_GATEWAY)
1977 		seq_printf(seq, "%pi6", &rt->rt6i_gateway);
1978 	else
1979 		seq_puts(seq, "00000000000000000000000000000000");
1980 
1981 	seq_printf(seq, " %08x %08x %08x %08x %8s\n",
1982 		   rt->rt6i_metric, atomic_read(&rt->dst.__refcnt),
1983 		   rt->dst.__use, rt->rt6i_flags,
1984 		   rt->dst.dev ? rt->dst.dev->name : "");
1985 	iter->w.leaf = NULL;
1986 	return 0;
1987 }
1988 
1989 static int ipv6_route_yield(struct fib6_walker *w)
1990 {
1991 	struct ipv6_route_iter *iter = w->args;
1992 
1993 	if (!iter->skip)
1994 		return 1;
1995 
1996 	do {
1997 		iter->w.leaf = iter->w.leaf->dst.rt6_next;
1998 		iter->skip--;
1999 		if (!iter->skip && iter->w.leaf)
2000 			return 1;
2001 	} while (iter->w.leaf);
2002 
2003 	return 0;
2004 }
2005 
2006 static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter,
2007 				      struct net *net)
2008 {
2009 	memset(&iter->w, 0, sizeof(iter->w));
2010 	iter->w.func = ipv6_route_yield;
2011 	iter->w.root = &iter->tbl->tb6_root;
2012 	iter->w.state = FWS_INIT;
2013 	iter->w.node = iter->w.root;
2014 	iter->w.args = iter;
2015 	iter->sernum = iter->w.root->fn_sernum;
2016 	INIT_LIST_HEAD(&iter->w.lh);
2017 	fib6_walker_link(net, &iter->w);
2018 }
2019 
2020 static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
2021 						    struct net *net)
2022 {
2023 	unsigned int h;
2024 	struct hlist_node *node;
2025 
2026 	if (tbl) {
2027 		h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
2028 		node = rcu_dereference_bh(hlist_next_rcu(&tbl->tb6_hlist));
2029 	} else {
2030 		h = 0;
2031 		node = NULL;
2032 	}
2033 
2034 	while (!node && h < FIB6_TABLE_HASHSZ) {
2035 		node = rcu_dereference_bh(
2036 			hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
2037 	}
2038 	return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
2039 }
2040 
2041 static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
2042 {
2043 	if (iter->sernum != iter->w.root->fn_sernum) {
2044 		iter->sernum = iter->w.root->fn_sernum;
2045 		iter->w.state = FWS_INIT;
2046 		iter->w.node = iter->w.root;
2047 		WARN_ON(iter->w.skip);
2048 		iter->w.skip = iter->w.count;
2049 	}
2050 }
2051 
2052 static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2053 {
2054 	int r;
2055 	struct rt6_info *n;
2056 	struct net *net = seq_file_net(seq);
2057 	struct ipv6_route_iter *iter = seq->private;
2058 
2059 	if (!v)
2060 		goto iter_table;
2061 
2062 	n = ((struct rt6_info *)v)->dst.rt6_next;
2063 	if (n) {
2064 		++*pos;
2065 		return n;
2066 	}
2067 
2068 iter_table:
2069 	ipv6_route_check_sernum(iter);
2070 	read_lock(&iter->tbl->tb6_lock);
2071 	r = fib6_walk_continue(&iter->w);
2072 	read_unlock(&iter->tbl->tb6_lock);
2073 	if (r > 0) {
2074 		if (v)
2075 			++*pos;
2076 		return iter->w.leaf;
2077 	} else if (r < 0) {
2078 		fib6_walker_unlink(net, &iter->w);
2079 		return NULL;
2080 	}
2081 	fib6_walker_unlink(net, &iter->w);
2082 
2083 	iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
2084 	if (!iter->tbl)
2085 		return NULL;
2086 
2087 	ipv6_route_seq_setup_walk(iter, net);
2088 	goto iter_table;
2089 }
2090 
2091 static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
2092 	__acquires(RCU_BH)
2093 {
2094 	struct net *net = seq_file_net(seq);
2095 	struct ipv6_route_iter *iter = seq->private;
2096 
2097 	rcu_read_lock_bh();
2098 	iter->tbl = ipv6_route_seq_next_table(NULL, net);
2099 	iter->skip = *pos;
2100 
2101 	if (iter->tbl) {
2102 		ipv6_route_seq_setup_walk(iter, net);
2103 		return ipv6_route_seq_next(seq, NULL, pos);
2104 	} else {
2105 		return NULL;
2106 	}
2107 }
2108 
2109 static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
2110 {
2111 	struct fib6_walker *w = &iter->w;
2112 	return w->node && !(w->state == FWS_U && w->node == w->root);
2113 }
2114 
2115 static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
2116 	__releases(RCU_BH)
2117 {
2118 	struct net *net = seq_file_net(seq);
2119 	struct ipv6_route_iter *iter = seq->private;
2120 
2121 	if (ipv6_route_iter_active(iter))
2122 		fib6_walker_unlink(net, &iter->w);
2123 
2124 	rcu_read_unlock_bh();
2125 }
2126 
2127 static const struct seq_operations ipv6_route_seq_ops = {
2128 	.start	= ipv6_route_seq_start,
2129 	.next	= ipv6_route_seq_next,
2130 	.stop	= ipv6_route_seq_stop,
2131 	.show	= ipv6_route_seq_show
2132 };
2133 
2134 int ipv6_route_open(struct inode *inode, struct file *file)
2135 {
2136 	return seq_open_net(inode, file, &ipv6_route_seq_ops,
2137 			    sizeof(struct ipv6_route_iter));
2138 }
2139 
2140 #endif /* CONFIG_PROC_FS */
2141