xref: /openbmc/linux/net/ipv6/ip6_fib.c (revision da097dcc)
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  *	Linux INET6 implementation
4  *	Forwarding Information Database
5  *
6  *	Authors:
7  *	Pedro Roque		<roque@di.fc.ul.pt>
8  *
9  *	Changes:
10  *	Yuji SEKIYA @USAGI:	Support default route on router node;
11  *				remove ip6_null_entry from the top of
12  *				routing table.
13  *	Ville Nuorvala:		Fixed routing subtrees.
14  */
15 
16 #define pr_fmt(fmt) "IPv6: " fmt
17 
18 #include <linux/bpf.h>
19 #include <linux/errno.h>
20 #include <linux/types.h>
21 #include <linux/net.h>
22 #include <linux/route.h>
23 #include <linux/netdevice.h>
24 #include <linux/in6.h>
25 #include <linux/init.h>
26 #include <linux/list.h>
27 #include <linux/slab.h>
28 
29 #include <net/ip.h>
30 #include <net/ipv6.h>
31 #include <net/ndisc.h>
32 #include <net/addrconf.h>
33 #include <net/lwtunnel.h>
34 #include <net/fib_notifier.h>
35 
36 #include <net/ip_fib.h>
37 #include <net/ip6_fib.h>
38 #include <net/ip6_route.h>
39 
40 static struct kmem_cache *fib6_node_kmem __read_mostly;
41 
42 struct fib6_cleaner {
43 	struct fib6_walker w;
44 	struct net *net;
45 	int (*func)(struct fib6_info *, void *arg);
46 	int sernum;
47 	void *arg;
48 	bool skip_notify;
49 };
50 
51 #ifdef CONFIG_IPV6_SUBTREES
52 #define FWS_INIT FWS_S
53 #else
54 #define FWS_INIT FWS_L
55 #endif
56 
57 static struct fib6_info *fib6_find_prefix(struct net *net,
58 					 struct fib6_table *table,
59 					 struct fib6_node *fn);
60 static struct fib6_node *fib6_repair_tree(struct net *net,
61 					  struct fib6_table *table,
62 					  struct fib6_node *fn);
63 static int fib6_walk(struct net *net, struct fib6_walker *w);
64 static int fib6_walk_continue(struct fib6_walker *w);
65 
66 /*
67  *	A routing update causes an increase of the serial number on the
68  *	affected subtree. This allows for cached routes to be asynchronously
69  *	tested when modifications are made to the destination cache as a
70  *	result of redirects, path MTU changes, etc.
71  */
72 
73 static void fib6_gc_timer_cb(struct timer_list *t);
74 
75 #define FOR_WALKERS(net, w) \
76 	list_for_each_entry(w, &(net)->ipv6.fib6_walkers, lh)
77 
78 static void fib6_walker_link(struct net *net, struct fib6_walker *w)
79 {
80 	write_lock_bh(&net->ipv6.fib6_walker_lock);
81 	list_add(&w->lh, &net->ipv6.fib6_walkers);
82 	write_unlock_bh(&net->ipv6.fib6_walker_lock);
83 }
84 
85 static void fib6_walker_unlink(struct net *net, struct fib6_walker *w)
86 {
87 	write_lock_bh(&net->ipv6.fib6_walker_lock);
88 	list_del(&w->lh);
89 	write_unlock_bh(&net->ipv6.fib6_walker_lock);
90 }
91 
92 static int fib6_new_sernum(struct net *net)
93 {
94 	int new, old = atomic_read(&net->ipv6.fib6_sernum);
95 
96 	do {
97 		new = old < INT_MAX ? old + 1 : 1;
98 	} while (!atomic_try_cmpxchg(&net->ipv6.fib6_sernum, &old, new));
99 
100 	return new;
101 }
102 
103 enum {
104 	FIB6_NO_SERNUM_CHANGE = 0,
105 };
106 
107 void fib6_update_sernum(struct net *net, struct fib6_info *f6i)
108 {
109 	struct fib6_node *fn;
110 
111 	fn = rcu_dereference_protected(f6i->fib6_node,
112 			lockdep_is_held(&f6i->fib6_table->tb6_lock));
113 	if (fn)
114 		WRITE_ONCE(fn->fn_sernum, fib6_new_sernum(net));
115 }
116 
117 /*
118  *	Auxiliary address test functions for the radix tree.
119  *
120  *	These assume a 32bit processor (although it will work on
121  *	64bit processors)
122  */
123 
124 /*
125  *	test bit
126  */
127 #if defined(__LITTLE_ENDIAN)
128 # define BITOP_BE32_SWIZZLE	(0x1F & ~7)
129 #else
130 # define BITOP_BE32_SWIZZLE	0
131 #endif
132 
133 static __be32 addr_bit_set(const void *token, int fn_bit)
134 {
135 	const __be32 *addr = token;
136 	/*
137 	 * Here,
138 	 *	1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
139 	 * is optimized version of
140 	 *	htonl(1 << ((~fn_bit)&0x1F))
141 	 * See include/asm-generic/bitops/le.h.
142 	 */
143 	return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
144 	       addr[fn_bit >> 5];
145 }
146 
147 struct fib6_info *fib6_info_alloc(gfp_t gfp_flags, bool with_fib6_nh)
148 {
149 	struct fib6_info *f6i;
150 	size_t sz = sizeof(*f6i);
151 
152 	if (with_fib6_nh)
153 		sz += sizeof(struct fib6_nh);
154 
155 	f6i = kzalloc(sz, gfp_flags);
156 	if (!f6i)
157 		return NULL;
158 
159 	/* fib6_siblings is a union with nh_list, so this initializes both */
160 	INIT_LIST_HEAD(&f6i->fib6_siblings);
161 	refcount_set(&f6i->fib6_ref, 1);
162 
163 	return f6i;
164 }
165 
166 void fib6_info_destroy_rcu(struct rcu_head *head)
167 {
168 	struct fib6_info *f6i = container_of(head, struct fib6_info, rcu);
169 
170 	WARN_ON(f6i->fib6_node);
171 
172 	if (f6i->nh)
173 		nexthop_put(f6i->nh);
174 	else
175 		fib6_nh_release(f6i->fib6_nh);
176 
177 	ip_fib_metrics_put(f6i->fib6_metrics);
178 	kfree(f6i);
179 }
180 EXPORT_SYMBOL_GPL(fib6_info_destroy_rcu);
181 
182 static struct fib6_node *node_alloc(struct net *net)
183 {
184 	struct fib6_node *fn;
185 
186 	fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
187 	if (fn)
188 		net->ipv6.rt6_stats->fib_nodes++;
189 
190 	return fn;
191 }
192 
193 static void node_free_immediate(struct net *net, struct fib6_node *fn)
194 {
195 	kmem_cache_free(fib6_node_kmem, fn);
196 	net->ipv6.rt6_stats->fib_nodes--;
197 }
198 
199 static void node_free_rcu(struct rcu_head *head)
200 {
201 	struct fib6_node *fn = container_of(head, struct fib6_node, rcu);
202 
203 	kmem_cache_free(fib6_node_kmem, fn);
204 }
205 
206 static void node_free(struct net *net, struct fib6_node *fn)
207 {
208 	call_rcu(&fn->rcu, node_free_rcu);
209 	net->ipv6.rt6_stats->fib_nodes--;
210 }
211 
212 static void fib6_free_table(struct fib6_table *table)
213 {
214 	inetpeer_invalidate_tree(&table->tb6_peers);
215 	kfree(table);
216 }
217 
218 static void fib6_link_table(struct net *net, struct fib6_table *tb)
219 {
220 	unsigned int h;
221 
222 	/*
223 	 * Initialize table lock at a single place to give lockdep a key,
224 	 * tables aren't visible prior to being linked to the list.
225 	 */
226 	spin_lock_init(&tb->tb6_lock);
227 	h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
228 
229 	/*
230 	 * No protection necessary, this is the only list mutatation
231 	 * operation, tables never disappear once they exist.
232 	 */
233 	hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
234 }
235 
236 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
237 
238 static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
239 {
240 	struct fib6_table *table;
241 
242 	table = kzalloc(sizeof(*table), GFP_ATOMIC);
243 	if (table) {
244 		table->tb6_id = id;
245 		rcu_assign_pointer(table->tb6_root.leaf,
246 				   net->ipv6.fib6_null_entry);
247 		table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
248 		inet_peer_base_init(&table->tb6_peers);
249 	}
250 
251 	return table;
252 }
253 
254 struct fib6_table *fib6_new_table(struct net *net, u32 id)
255 {
256 	struct fib6_table *tb;
257 
258 	if (id == 0)
259 		id = RT6_TABLE_MAIN;
260 	tb = fib6_get_table(net, id);
261 	if (tb)
262 		return tb;
263 
264 	tb = fib6_alloc_table(net, id);
265 	if (tb)
266 		fib6_link_table(net, tb);
267 
268 	return tb;
269 }
270 EXPORT_SYMBOL_GPL(fib6_new_table);
271 
272 struct fib6_table *fib6_get_table(struct net *net, u32 id)
273 {
274 	struct fib6_table *tb;
275 	struct hlist_head *head;
276 	unsigned int h;
277 
278 	if (id == 0)
279 		id = RT6_TABLE_MAIN;
280 	h = id & (FIB6_TABLE_HASHSZ - 1);
281 	rcu_read_lock();
282 	head = &net->ipv6.fib_table_hash[h];
283 	hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
284 		if (tb->tb6_id == id) {
285 			rcu_read_unlock();
286 			return tb;
287 		}
288 	}
289 	rcu_read_unlock();
290 
291 	return NULL;
292 }
293 EXPORT_SYMBOL_GPL(fib6_get_table);
294 
295 static void __net_init fib6_tables_init(struct net *net)
296 {
297 	fib6_link_table(net, net->ipv6.fib6_main_tbl);
298 	fib6_link_table(net, net->ipv6.fib6_local_tbl);
299 }
300 #else
301 
302 struct fib6_table *fib6_new_table(struct net *net, u32 id)
303 {
304 	return fib6_get_table(net, id);
305 }
306 
307 struct fib6_table *fib6_get_table(struct net *net, u32 id)
308 {
309 	  return net->ipv6.fib6_main_tbl;
310 }
311 
312 struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
313 				   const struct sk_buff *skb,
314 				   int flags, pol_lookup_t lookup)
315 {
316 	struct rt6_info *rt;
317 
318 	rt = pol_lookup_func(lookup,
319 			net, net->ipv6.fib6_main_tbl, fl6, skb, flags);
320 	if (rt->dst.error == -EAGAIN) {
321 		ip6_rt_put_flags(rt, flags);
322 		rt = net->ipv6.ip6_null_entry;
323 		if (!(flags & RT6_LOOKUP_F_DST_NOREF))
324 			dst_hold(&rt->dst);
325 	}
326 
327 	return &rt->dst;
328 }
329 
330 /* called with rcu lock held; no reference taken on fib6_info */
331 int fib6_lookup(struct net *net, int oif, struct flowi6 *fl6,
332 		struct fib6_result *res, int flags)
333 {
334 	return fib6_table_lookup(net, net->ipv6.fib6_main_tbl, oif, fl6,
335 				 res, flags);
336 }
337 
338 static void __net_init fib6_tables_init(struct net *net)
339 {
340 	fib6_link_table(net, net->ipv6.fib6_main_tbl);
341 }
342 
343 #endif
344 
345 unsigned int fib6_tables_seq_read(struct net *net)
346 {
347 	unsigned int h, fib_seq = 0;
348 
349 	rcu_read_lock();
350 	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
351 		struct hlist_head *head = &net->ipv6.fib_table_hash[h];
352 		struct fib6_table *tb;
353 
354 		hlist_for_each_entry_rcu(tb, head, tb6_hlist)
355 			fib_seq += tb->fib_seq;
356 	}
357 	rcu_read_unlock();
358 
359 	return fib_seq;
360 }
361 
362 static int call_fib6_entry_notifier(struct notifier_block *nb,
363 				    enum fib_event_type event_type,
364 				    struct fib6_info *rt,
365 				    struct netlink_ext_ack *extack)
366 {
367 	struct fib6_entry_notifier_info info = {
368 		.info.extack = extack,
369 		.rt = rt,
370 	};
371 
372 	return call_fib6_notifier(nb, event_type, &info.info);
373 }
374 
375 static int call_fib6_multipath_entry_notifier(struct notifier_block *nb,
376 					      enum fib_event_type event_type,
377 					      struct fib6_info *rt,
378 					      unsigned int nsiblings,
379 					      struct netlink_ext_ack *extack)
380 {
381 	struct fib6_entry_notifier_info info = {
382 		.info.extack = extack,
383 		.rt = rt,
384 		.nsiblings = nsiblings,
385 	};
386 
387 	return call_fib6_notifier(nb, event_type, &info.info);
388 }
389 
390 int call_fib6_entry_notifiers(struct net *net,
391 			      enum fib_event_type event_type,
392 			      struct fib6_info *rt,
393 			      struct netlink_ext_ack *extack)
394 {
395 	struct fib6_entry_notifier_info info = {
396 		.info.extack = extack,
397 		.rt = rt,
398 	};
399 
400 	rt->fib6_table->fib_seq++;
401 	return call_fib6_notifiers(net, event_type, &info.info);
402 }
403 
404 int call_fib6_multipath_entry_notifiers(struct net *net,
405 					enum fib_event_type event_type,
406 					struct fib6_info *rt,
407 					unsigned int nsiblings,
408 					struct netlink_ext_ack *extack)
409 {
410 	struct fib6_entry_notifier_info info = {
411 		.info.extack = extack,
412 		.rt = rt,
413 		.nsiblings = nsiblings,
414 	};
415 
416 	rt->fib6_table->fib_seq++;
417 	return call_fib6_notifiers(net, event_type, &info.info);
418 }
419 
420 int call_fib6_entry_notifiers_replace(struct net *net, struct fib6_info *rt)
421 {
422 	struct fib6_entry_notifier_info info = {
423 		.rt = rt,
424 		.nsiblings = rt->fib6_nsiblings,
425 	};
426 
427 	rt->fib6_table->fib_seq++;
428 	return call_fib6_notifiers(net, FIB_EVENT_ENTRY_REPLACE, &info.info);
429 }
430 
431 struct fib6_dump_arg {
432 	struct net *net;
433 	struct notifier_block *nb;
434 	struct netlink_ext_ack *extack;
435 };
436 
437 static int fib6_rt_dump(struct fib6_info *rt, struct fib6_dump_arg *arg)
438 {
439 	enum fib_event_type fib_event = FIB_EVENT_ENTRY_REPLACE;
440 	int err;
441 
442 	if (!rt || rt == arg->net->ipv6.fib6_null_entry)
443 		return 0;
444 
445 	if (rt->fib6_nsiblings)
446 		err = call_fib6_multipath_entry_notifier(arg->nb, fib_event,
447 							 rt,
448 							 rt->fib6_nsiblings,
449 							 arg->extack);
450 	else
451 		err = call_fib6_entry_notifier(arg->nb, fib_event, rt,
452 					       arg->extack);
453 
454 	return err;
455 }
456 
457 static int fib6_node_dump(struct fib6_walker *w)
458 {
459 	int err;
460 
461 	err = fib6_rt_dump(w->leaf, w->args);
462 	w->leaf = NULL;
463 	return err;
464 }
465 
466 static int fib6_table_dump(struct net *net, struct fib6_table *tb,
467 			   struct fib6_walker *w)
468 {
469 	int err;
470 
471 	w->root = &tb->tb6_root;
472 	spin_lock_bh(&tb->tb6_lock);
473 	err = fib6_walk(net, w);
474 	spin_unlock_bh(&tb->tb6_lock);
475 	return err;
476 }
477 
478 /* Called with rcu_read_lock() */
479 int fib6_tables_dump(struct net *net, struct notifier_block *nb,
480 		     struct netlink_ext_ack *extack)
481 {
482 	struct fib6_dump_arg arg;
483 	struct fib6_walker *w;
484 	unsigned int h;
485 	int err = 0;
486 
487 	w = kzalloc(sizeof(*w), GFP_ATOMIC);
488 	if (!w)
489 		return -ENOMEM;
490 
491 	w->func = fib6_node_dump;
492 	arg.net = net;
493 	arg.nb = nb;
494 	arg.extack = extack;
495 	w->args = &arg;
496 
497 	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
498 		struct hlist_head *head = &net->ipv6.fib_table_hash[h];
499 		struct fib6_table *tb;
500 
501 		hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
502 			err = fib6_table_dump(net, tb, w);
503 			if (err)
504 				goto out;
505 		}
506 	}
507 
508 out:
509 	kfree(w);
510 
511 	/* The tree traversal function should never return a positive value. */
512 	return err > 0 ? -EINVAL : err;
513 }
514 
515 static int fib6_dump_node(struct fib6_walker *w)
516 {
517 	int res;
518 	struct fib6_info *rt;
519 
520 	for_each_fib6_walker_rt(w) {
521 		res = rt6_dump_route(rt, w->args, w->skip_in_node);
522 		if (res >= 0) {
523 			/* Frame is full, suspend walking */
524 			w->leaf = rt;
525 
526 			/* We'll restart from this node, so if some routes were
527 			 * already dumped, skip them next time.
528 			 */
529 			w->skip_in_node += res;
530 
531 			return 1;
532 		}
533 		w->skip_in_node = 0;
534 
535 		/* Multipath routes are dumped in one route with the
536 		 * RTA_MULTIPATH attribute. Jump 'rt' to point to the
537 		 * last sibling of this route (no need to dump the
538 		 * sibling routes again)
539 		 */
540 		if (rt->fib6_nsiblings)
541 			rt = list_last_entry(&rt->fib6_siblings,
542 					     struct fib6_info,
543 					     fib6_siblings);
544 	}
545 	w->leaf = NULL;
546 	return 0;
547 }
548 
549 static void fib6_dump_end(struct netlink_callback *cb)
550 {
551 	struct net *net = sock_net(cb->skb->sk);
552 	struct fib6_walker *w = (void *)cb->args[2];
553 
554 	if (w) {
555 		if (cb->args[4]) {
556 			cb->args[4] = 0;
557 			fib6_walker_unlink(net, w);
558 		}
559 		cb->args[2] = 0;
560 		kfree(w);
561 	}
562 	cb->done = (void *)cb->args[3];
563 	cb->args[1] = 3;
564 }
565 
566 static int fib6_dump_done(struct netlink_callback *cb)
567 {
568 	fib6_dump_end(cb);
569 	return cb->done ? cb->done(cb) : 0;
570 }
571 
572 static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
573 			   struct netlink_callback *cb)
574 {
575 	struct net *net = sock_net(skb->sk);
576 	struct fib6_walker *w;
577 	int res;
578 
579 	w = (void *)cb->args[2];
580 	w->root = &table->tb6_root;
581 
582 	if (cb->args[4] == 0) {
583 		w->count = 0;
584 		w->skip = 0;
585 		w->skip_in_node = 0;
586 
587 		spin_lock_bh(&table->tb6_lock);
588 		res = fib6_walk(net, w);
589 		spin_unlock_bh(&table->tb6_lock);
590 		if (res > 0) {
591 			cb->args[4] = 1;
592 			cb->args[5] = READ_ONCE(w->root->fn_sernum);
593 		}
594 	} else {
595 		int sernum = READ_ONCE(w->root->fn_sernum);
596 		if (cb->args[5] != sernum) {
597 			/* Begin at the root if the tree changed */
598 			cb->args[5] = sernum;
599 			w->state = FWS_INIT;
600 			w->node = w->root;
601 			w->skip = w->count;
602 			w->skip_in_node = 0;
603 		} else
604 			w->skip = 0;
605 
606 		spin_lock_bh(&table->tb6_lock);
607 		res = fib6_walk_continue(w);
608 		spin_unlock_bh(&table->tb6_lock);
609 		if (res <= 0) {
610 			fib6_walker_unlink(net, w);
611 			cb->args[4] = 0;
612 		}
613 	}
614 
615 	return res;
616 }
617 
618 static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
619 {
620 	struct rt6_rtnl_dump_arg arg = { .filter.dump_exceptions = true,
621 					 .filter.dump_routes = true };
622 	const struct nlmsghdr *nlh = cb->nlh;
623 	struct net *net = sock_net(skb->sk);
624 	unsigned int h, s_h;
625 	unsigned int e = 0, s_e;
626 	struct fib6_walker *w;
627 	struct fib6_table *tb;
628 	struct hlist_head *head;
629 	int res = 0;
630 
631 	if (cb->strict_check) {
632 		int err;
633 
634 		err = ip_valid_fib_dump_req(net, nlh, &arg.filter, cb);
635 		if (err < 0)
636 			return err;
637 	} else if (nlmsg_len(nlh) >= sizeof(struct rtmsg)) {
638 		struct rtmsg *rtm = nlmsg_data(nlh);
639 
640 		if (rtm->rtm_flags & RTM_F_PREFIX)
641 			arg.filter.flags = RTM_F_PREFIX;
642 	}
643 
644 	w = (void *)cb->args[2];
645 	if (!w) {
646 		/* New dump:
647 		 *
648 		 * 1. allocate and initialize walker.
649 		 */
650 		w = kzalloc(sizeof(*w), GFP_ATOMIC);
651 		if (!w)
652 			return -ENOMEM;
653 		w->func = fib6_dump_node;
654 		cb->args[2] = (long)w;
655 
656 		/* 2. hook callback destructor.
657 		 */
658 		cb->args[3] = (long)cb->done;
659 		cb->done = fib6_dump_done;
660 
661 	}
662 
663 	arg.skb = skb;
664 	arg.cb = cb;
665 	arg.net = net;
666 	w->args = &arg;
667 
668 	if (arg.filter.table_id) {
669 		tb = fib6_get_table(net, arg.filter.table_id);
670 		if (!tb) {
671 			if (rtnl_msg_family(cb->nlh) != PF_INET6)
672 				goto out;
673 
674 			NL_SET_ERR_MSG_MOD(cb->extack, "FIB table does not exist");
675 			return -ENOENT;
676 		}
677 
678 		if (!cb->args[0]) {
679 			res = fib6_dump_table(tb, skb, cb);
680 			if (!res)
681 				cb->args[0] = 1;
682 		}
683 		goto out;
684 	}
685 
686 	s_h = cb->args[0];
687 	s_e = cb->args[1];
688 
689 	rcu_read_lock();
690 	for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
691 		e = 0;
692 		head = &net->ipv6.fib_table_hash[h];
693 		hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
694 			if (e < s_e)
695 				goto next;
696 			res = fib6_dump_table(tb, skb, cb);
697 			if (res != 0)
698 				goto out_unlock;
699 next:
700 			e++;
701 		}
702 	}
703 out_unlock:
704 	rcu_read_unlock();
705 	cb->args[1] = e;
706 	cb->args[0] = h;
707 out:
708 	res = res < 0 ? res : skb->len;
709 	if (res <= 0)
710 		fib6_dump_end(cb);
711 	return res;
712 }
713 
714 void fib6_metric_set(struct fib6_info *f6i, int metric, u32 val)
715 {
716 	if (!f6i)
717 		return;
718 
719 	if (f6i->fib6_metrics == &dst_default_metrics) {
720 		struct dst_metrics *p = kzalloc(sizeof(*p), GFP_ATOMIC);
721 
722 		if (!p)
723 			return;
724 
725 		refcount_set(&p->refcnt, 1);
726 		f6i->fib6_metrics = p;
727 	}
728 
729 	f6i->fib6_metrics->metrics[metric - 1] = val;
730 }
731 
732 /*
733  *	Routing Table
734  *
735  *	return the appropriate node for a routing tree "add" operation
736  *	by either creating and inserting or by returning an existing
737  *	node.
738  */
739 
740 static struct fib6_node *fib6_add_1(struct net *net,
741 				    struct fib6_table *table,
742 				    struct fib6_node *root,
743 				    struct in6_addr *addr, int plen,
744 				    int offset, int allow_create,
745 				    int replace_required,
746 				    struct netlink_ext_ack *extack)
747 {
748 	struct fib6_node *fn, *in, *ln;
749 	struct fib6_node *pn = NULL;
750 	struct rt6key *key;
751 	int	bit;
752 	__be32	dir = 0;
753 
754 	RT6_TRACE("fib6_add_1\n");
755 
756 	/* insert node in tree */
757 
758 	fn = root;
759 
760 	do {
761 		struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
762 					    lockdep_is_held(&table->tb6_lock));
763 		key = (struct rt6key *)((u8 *)leaf + offset);
764 
765 		/*
766 		 *	Prefix match
767 		 */
768 		if (plen < fn->fn_bit ||
769 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
770 			if (!allow_create) {
771 				if (replace_required) {
772 					NL_SET_ERR_MSG(extack,
773 						       "Can not replace route - no match found");
774 					pr_warn("Can't replace route, no match found\n");
775 					return ERR_PTR(-ENOENT);
776 				}
777 				pr_warn("NLM_F_CREATE should be set when creating new route\n");
778 			}
779 			goto insert_above;
780 		}
781 
782 		/*
783 		 *	Exact match ?
784 		 */
785 
786 		if (plen == fn->fn_bit) {
787 			/* clean up an intermediate node */
788 			if (!(fn->fn_flags & RTN_RTINFO)) {
789 				RCU_INIT_POINTER(fn->leaf, NULL);
790 				fib6_info_release(leaf);
791 			/* remove null_entry in the root node */
792 			} else if (fn->fn_flags & RTN_TL_ROOT &&
793 				   rcu_access_pointer(fn->leaf) ==
794 				   net->ipv6.fib6_null_entry) {
795 				RCU_INIT_POINTER(fn->leaf, NULL);
796 			}
797 
798 			return fn;
799 		}
800 
801 		/*
802 		 *	We have more bits to go
803 		 */
804 
805 		/* Try to walk down on tree. */
806 		dir = addr_bit_set(addr, fn->fn_bit);
807 		pn = fn;
808 		fn = dir ?
809 		     rcu_dereference_protected(fn->right,
810 					lockdep_is_held(&table->tb6_lock)) :
811 		     rcu_dereference_protected(fn->left,
812 					lockdep_is_held(&table->tb6_lock));
813 	} while (fn);
814 
815 	if (!allow_create) {
816 		/* We should not create new node because
817 		 * NLM_F_REPLACE was specified without NLM_F_CREATE
818 		 * I assume it is safe to require NLM_F_CREATE when
819 		 * REPLACE flag is used! Later we may want to remove the
820 		 * check for replace_required, because according
821 		 * to netlink specification, NLM_F_CREATE
822 		 * MUST be specified if new route is created.
823 		 * That would keep IPv6 consistent with IPv4
824 		 */
825 		if (replace_required) {
826 			NL_SET_ERR_MSG(extack,
827 				       "Can not replace route - no match found");
828 			pr_warn("Can't replace route, no match found\n");
829 			return ERR_PTR(-ENOENT);
830 		}
831 		pr_warn("NLM_F_CREATE should be set when creating new route\n");
832 	}
833 	/*
834 	 *	We walked to the bottom of tree.
835 	 *	Create new leaf node without children.
836 	 */
837 
838 	ln = node_alloc(net);
839 
840 	if (!ln)
841 		return ERR_PTR(-ENOMEM);
842 	ln->fn_bit = plen;
843 	RCU_INIT_POINTER(ln->parent, pn);
844 
845 	if (dir)
846 		rcu_assign_pointer(pn->right, ln);
847 	else
848 		rcu_assign_pointer(pn->left, ln);
849 
850 	return ln;
851 
852 
853 insert_above:
854 	/*
855 	 * split since we don't have a common prefix anymore or
856 	 * we have a less significant route.
857 	 * we've to insert an intermediate node on the list
858 	 * this new node will point to the one we need to create
859 	 * and the current
860 	 */
861 
862 	pn = rcu_dereference_protected(fn->parent,
863 				       lockdep_is_held(&table->tb6_lock));
864 
865 	/* find 1st bit in difference between the 2 addrs.
866 
867 	   See comment in __ipv6_addr_diff: bit may be an invalid value,
868 	   but if it is >= plen, the value is ignored in any case.
869 	 */
870 
871 	bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
872 
873 	/*
874 	 *		(intermediate)[in]
875 	 *	          /	   \
876 	 *	(new leaf node)[ln] (old node)[fn]
877 	 */
878 	if (plen > bit) {
879 		in = node_alloc(net);
880 		ln = node_alloc(net);
881 
882 		if (!in || !ln) {
883 			if (in)
884 				node_free_immediate(net, in);
885 			if (ln)
886 				node_free_immediate(net, ln);
887 			return ERR_PTR(-ENOMEM);
888 		}
889 
890 		/*
891 		 * new intermediate node.
892 		 * RTN_RTINFO will
893 		 * be off since that an address that chooses one of
894 		 * the branches would not match less specific routes
895 		 * in the other branch
896 		 */
897 
898 		in->fn_bit = bit;
899 
900 		RCU_INIT_POINTER(in->parent, pn);
901 		in->leaf = fn->leaf;
902 		fib6_info_hold(rcu_dereference_protected(in->leaf,
903 				lockdep_is_held(&table->tb6_lock)));
904 
905 		/* update parent pointer */
906 		if (dir)
907 			rcu_assign_pointer(pn->right, in);
908 		else
909 			rcu_assign_pointer(pn->left, in);
910 
911 		ln->fn_bit = plen;
912 
913 		RCU_INIT_POINTER(ln->parent, in);
914 		rcu_assign_pointer(fn->parent, in);
915 
916 		if (addr_bit_set(addr, bit)) {
917 			rcu_assign_pointer(in->right, ln);
918 			rcu_assign_pointer(in->left, fn);
919 		} else {
920 			rcu_assign_pointer(in->left, ln);
921 			rcu_assign_pointer(in->right, fn);
922 		}
923 	} else { /* plen <= bit */
924 
925 		/*
926 		 *		(new leaf node)[ln]
927 		 *	          /	   \
928 		 *	     (old node)[fn] NULL
929 		 */
930 
931 		ln = node_alloc(net);
932 
933 		if (!ln)
934 			return ERR_PTR(-ENOMEM);
935 
936 		ln->fn_bit = plen;
937 
938 		RCU_INIT_POINTER(ln->parent, pn);
939 
940 		if (addr_bit_set(&key->addr, plen))
941 			RCU_INIT_POINTER(ln->right, fn);
942 		else
943 			RCU_INIT_POINTER(ln->left, fn);
944 
945 		rcu_assign_pointer(fn->parent, ln);
946 
947 		if (dir)
948 			rcu_assign_pointer(pn->right, ln);
949 		else
950 			rcu_assign_pointer(pn->left, ln);
951 	}
952 	return ln;
953 }
954 
955 static void __fib6_drop_pcpu_from(struct fib6_nh *fib6_nh,
956 				  const struct fib6_info *match,
957 				  const struct fib6_table *table)
958 {
959 	int cpu;
960 
961 	if (!fib6_nh->rt6i_pcpu)
962 		return;
963 
964 	rcu_read_lock();
965 	/* release the reference to this fib entry from
966 	 * all of its cached pcpu routes
967 	 */
968 	for_each_possible_cpu(cpu) {
969 		struct rt6_info **ppcpu_rt;
970 		struct rt6_info *pcpu_rt;
971 
972 		ppcpu_rt = per_cpu_ptr(fib6_nh->rt6i_pcpu, cpu);
973 
974 		/* Paired with xchg() in rt6_get_pcpu_route() */
975 		pcpu_rt = READ_ONCE(*ppcpu_rt);
976 
977 		/* only dropping the 'from' reference if the cached route
978 		 * is using 'match'. The cached pcpu_rt->from only changes
979 		 * from a fib6_info to NULL (ip6_dst_destroy); it can never
980 		 * change from one fib6_info reference to another
981 		 */
982 		if (pcpu_rt && rcu_access_pointer(pcpu_rt->from) == match) {
983 			struct fib6_info *from;
984 
985 			from = xchg((__force struct fib6_info **)&pcpu_rt->from, NULL);
986 			fib6_info_release(from);
987 		}
988 	}
989 	rcu_read_unlock();
990 }
991 
992 struct fib6_nh_pcpu_arg {
993 	struct fib6_info	*from;
994 	const struct fib6_table *table;
995 };
996 
997 static int fib6_nh_drop_pcpu_from(struct fib6_nh *nh, void *_arg)
998 {
999 	struct fib6_nh_pcpu_arg *arg = _arg;
1000 
1001 	__fib6_drop_pcpu_from(nh, arg->from, arg->table);
1002 	return 0;
1003 }
1004 
1005 static void fib6_drop_pcpu_from(struct fib6_info *f6i,
1006 				const struct fib6_table *table)
1007 {
1008 	/* Make sure rt6_make_pcpu_route() wont add other percpu routes
1009 	 * while we are cleaning them here.
1010 	 */
1011 	f6i->fib6_destroying = 1;
1012 	mb(); /* paired with the cmpxchg() in rt6_make_pcpu_route() */
1013 
1014 	if (f6i->nh) {
1015 		struct fib6_nh_pcpu_arg arg = {
1016 			.from = f6i,
1017 			.table = table
1018 		};
1019 
1020 		nexthop_for_each_fib6_nh(f6i->nh, fib6_nh_drop_pcpu_from,
1021 					 &arg);
1022 	} else {
1023 		struct fib6_nh *fib6_nh;
1024 
1025 		fib6_nh = f6i->fib6_nh;
1026 		__fib6_drop_pcpu_from(fib6_nh, f6i, table);
1027 	}
1028 }
1029 
1030 static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,
1031 			  struct net *net)
1032 {
1033 	struct fib6_table *table = rt->fib6_table;
1034 
1035 	/* Flush all cached dst in exception table */
1036 	rt6_flush_exceptions(rt);
1037 	fib6_drop_pcpu_from(rt, table);
1038 
1039 	if (rt->nh && !list_empty(&rt->nh_list))
1040 		list_del_init(&rt->nh_list);
1041 
1042 	if (refcount_read(&rt->fib6_ref) != 1) {
1043 		/* This route is used as dummy address holder in some split
1044 		 * nodes. It is not leaked, but it still holds other resources,
1045 		 * which must be released in time. So, scan ascendant nodes
1046 		 * and replace dummy references to this route with references
1047 		 * to still alive ones.
1048 		 */
1049 		while (fn) {
1050 			struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
1051 					    lockdep_is_held(&table->tb6_lock));
1052 			struct fib6_info *new_leaf;
1053 			if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {
1054 				new_leaf = fib6_find_prefix(net, table, fn);
1055 				fib6_info_hold(new_leaf);
1056 
1057 				rcu_assign_pointer(fn->leaf, new_leaf);
1058 				fib6_info_release(rt);
1059 			}
1060 			fn = rcu_dereference_protected(fn->parent,
1061 				    lockdep_is_held(&table->tb6_lock));
1062 		}
1063 	}
1064 }
1065 
1066 /*
1067  *	Insert routing information in a node.
1068  */
1069 
1070 static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,
1071 			    struct nl_info *info,
1072 			    struct netlink_ext_ack *extack)
1073 {
1074 	struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
1075 				    lockdep_is_held(&rt->fib6_table->tb6_lock));
1076 	struct fib6_info *iter = NULL;
1077 	struct fib6_info __rcu **ins;
1078 	struct fib6_info __rcu **fallback_ins = NULL;
1079 	int replace = (info->nlh &&
1080 		       (info->nlh->nlmsg_flags & NLM_F_REPLACE));
1081 	int add = (!info->nlh ||
1082 		   (info->nlh->nlmsg_flags & NLM_F_CREATE));
1083 	int found = 0;
1084 	bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
1085 	bool notify_sibling_rt = false;
1086 	u16 nlflags = NLM_F_EXCL;
1087 	int err;
1088 
1089 	if (info->nlh && (info->nlh->nlmsg_flags & NLM_F_APPEND))
1090 		nlflags |= NLM_F_APPEND;
1091 
1092 	ins = &fn->leaf;
1093 
1094 	for (iter = leaf; iter;
1095 	     iter = rcu_dereference_protected(iter->fib6_next,
1096 				lockdep_is_held(&rt->fib6_table->tb6_lock))) {
1097 		/*
1098 		 *	Search for duplicates
1099 		 */
1100 
1101 		if (iter->fib6_metric == rt->fib6_metric) {
1102 			/*
1103 			 *	Same priority level
1104 			 */
1105 			if (info->nlh &&
1106 			    (info->nlh->nlmsg_flags & NLM_F_EXCL))
1107 				return -EEXIST;
1108 
1109 			nlflags &= ~NLM_F_EXCL;
1110 			if (replace) {
1111 				if (rt_can_ecmp == rt6_qualify_for_ecmp(iter)) {
1112 					found++;
1113 					break;
1114 				}
1115 				fallback_ins = fallback_ins ?: ins;
1116 				goto next_iter;
1117 			}
1118 
1119 			if (rt6_duplicate_nexthop(iter, rt)) {
1120 				if (rt->fib6_nsiblings)
1121 					rt->fib6_nsiblings = 0;
1122 				if (!(iter->fib6_flags & RTF_EXPIRES))
1123 					return -EEXIST;
1124 				if (!(rt->fib6_flags & RTF_EXPIRES))
1125 					fib6_clean_expires(iter);
1126 				else
1127 					fib6_set_expires(iter, rt->expires);
1128 
1129 				if (rt->fib6_pmtu)
1130 					fib6_metric_set(iter, RTAX_MTU,
1131 							rt->fib6_pmtu);
1132 				return -EEXIST;
1133 			}
1134 			/* If we have the same destination and the same metric,
1135 			 * but not the same gateway, then the route we try to
1136 			 * add is sibling to this route, increment our counter
1137 			 * of siblings, and later we will add our route to the
1138 			 * list.
1139 			 * Only static routes (which don't have flag
1140 			 * RTF_EXPIRES) are used for ECMPv6.
1141 			 *
1142 			 * To avoid long list, we only had siblings if the
1143 			 * route have a gateway.
1144 			 */
1145 			if (rt_can_ecmp &&
1146 			    rt6_qualify_for_ecmp(iter))
1147 				rt->fib6_nsiblings++;
1148 		}
1149 
1150 		if (iter->fib6_metric > rt->fib6_metric)
1151 			break;
1152 
1153 next_iter:
1154 		ins = &iter->fib6_next;
1155 	}
1156 
1157 	if (fallback_ins && !found) {
1158 		/* No matching route with same ecmp-able-ness found, replace
1159 		 * first matching route
1160 		 */
1161 		ins = fallback_ins;
1162 		iter = rcu_dereference_protected(*ins,
1163 				    lockdep_is_held(&rt->fib6_table->tb6_lock));
1164 		found++;
1165 	}
1166 
1167 	/* Reset round-robin state, if necessary */
1168 	if (ins == &fn->leaf)
1169 		fn->rr_ptr = NULL;
1170 
1171 	/* Link this route to others same route. */
1172 	if (rt->fib6_nsiblings) {
1173 		unsigned int fib6_nsiblings;
1174 		struct fib6_info *sibling, *temp_sibling;
1175 
1176 		/* Find the first route that have the same metric */
1177 		sibling = leaf;
1178 		notify_sibling_rt = true;
1179 		while (sibling) {
1180 			if (sibling->fib6_metric == rt->fib6_metric &&
1181 			    rt6_qualify_for_ecmp(sibling)) {
1182 				list_add_tail(&rt->fib6_siblings,
1183 					      &sibling->fib6_siblings);
1184 				break;
1185 			}
1186 			sibling = rcu_dereference_protected(sibling->fib6_next,
1187 				    lockdep_is_held(&rt->fib6_table->tb6_lock));
1188 			notify_sibling_rt = false;
1189 		}
1190 		/* For each sibling in the list, increment the counter of
1191 		 * siblings. BUG() if counters does not match, list of siblings
1192 		 * is broken!
1193 		 */
1194 		fib6_nsiblings = 0;
1195 		list_for_each_entry_safe(sibling, temp_sibling,
1196 					 &rt->fib6_siblings, fib6_siblings) {
1197 			sibling->fib6_nsiblings++;
1198 			BUG_ON(sibling->fib6_nsiblings != rt->fib6_nsiblings);
1199 			fib6_nsiblings++;
1200 		}
1201 		BUG_ON(fib6_nsiblings != rt->fib6_nsiblings);
1202 		rt6_multipath_rebalance(temp_sibling);
1203 	}
1204 
1205 	/*
1206 	 *	insert node
1207 	 */
1208 	if (!replace) {
1209 		if (!add)
1210 			pr_warn("NLM_F_CREATE should be set when creating new route\n");
1211 
1212 add:
1213 		nlflags |= NLM_F_CREATE;
1214 
1215 		/* The route should only be notified if it is the first
1216 		 * route in the node or if it is added as a sibling
1217 		 * route to the first route in the node.
1218 		 */
1219 		if (!info->skip_notify_kernel &&
1220 		    (notify_sibling_rt || ins == &fn->leaf)) {
1221 			enum fib_event_type fib_event;
1222 
1223 			if (notify_sibling_rt)
1224 				fib_event = FIB_EVENT_ENTRY_APPEND;
1225 			else
1226 				fib_event = FIB_EVENT_ENTRY_REPLACE;
1227 			err = call_fib6_entry_notifiers(info->nl_net,
1228 							fib_event, rt,
1229 							extack);
1230 			if (err) {
1231 				struct fib6_info *sibling, *next_sibling;
1232 
1233 				/* If the route has siblings, then it first
1234 				 * needs to be unlinked from them.
1235 				 */
1236 				if (!rt->fib6_nsiblings)
1237 					return err;
1238 
1239 				list_for_each_entry_safe(sibling, next_sibling,
1240 							 &rt->fib6_siblings,
1241 							 fib6_siblings)
1242 					sibling->fib6_nsiblings--;
1243 				rt->fib6_nsiblings = 0;
1244 				list_del_init(&rt->fib6_siblings);
1245 				rt6_multipath_rebalance(next_sibling);
1246 				return err;
1247 			}
1248 		}
1249 
1250 		rcu_assign_pointer(rt->fib6_next, iter);
1251 		fib6_info_hold(rt);
1252 		rcu_assign_pointer(rt->fib6_node, fn);
1253 		rcu_assign_pointer(*ins, rt);
1254 		if (!info->skip_notify)
1255 			inet6_rt_notify(RTM_NEWROUTE, rt, info, nlflags);
1256 		info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
1257 
1258 		if (!(fn->fn_flags & RTN_RTINFO)) {
1259 			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
1260 			fn->fn_flags |= RTN_RTINFO;
1261 		}
1262 
1263 	} else {
1264 		int nsiblings;
1265 
1266 		if (!found) {
1267 			if (add)
1268 				goto add;
1269 			pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
1270 			return -ENOENT;
1271 		}
1272 
1273 		if (!info->skip_notify_kernel && ins == &fn->leaf) {
1274 			err = call_fib6_entry_notifiers(info->nl_net,
1275 							FIB_EVENT_ENTRY_REPLACE,
1276 							rt, extack);
1277 			if (err)
1278 				return err;
1279 		}
1280 
1281 		fib6_info_hold(rt);
1282 		rcu_assign_pointer(rt->fib6_node, fn);
1283 		rt->fib6_next = iter->fib6_next;
1284 		rcu_assign_pointer(*ins, rt);
1285 		if (!info->skip_notify)
1286 			inet6_rt_notify(RTM_NEWROUTE, rt, info, NLM_F_REPLACE);
1287 		if (!(fn->fn_flags & RTN_RTINFO)) {
1288 			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
1289 			fn->fn_flags |= RTN_RTINFO;
1290 		}
1291 		nsiblings = iter->fib6_nsiblings;
1292 		iter->fib6_node = NULL;
1293 		fib6_purge_rt(iter, fn, info->nl_net);
1294 		if (rcu_access_pointer(fn->rr_ptr) == iter)
1295 			fn->rr_ptr = NULL;
1296 		fib6_info_release(iter);
1297 
1298 		if (nsiblings) {
1299 			/* Replacing an ECMP route, remove all siblings */
1300 			ins = &rt->fib6_next;
1301 			iter = rcu_dereference_protected(*ins,
1302 				    lockdep_is_held(&rt->fib6_table->tb6_lock));
1303 			while (iter) {
1304 				if (iter->fib6_metric > rt->fib6_metric)
1305 					break;
1306 				if (rt6_qualify_for_ecmp(iter)) {
1307 					*ins = iter->fib6_next;
1308 					iter->fib6_node = NULL;
1309 					fib6_purge_rt(iter, fn, info->nl_net);
1310 					if (rcu_access_pointer(fn->rr_ptr) == iter)
1311 						fn->rr_ptr = NULL;
1312 					fib6_info_release(iter);
1313 					nsiblings--;
1314 					info->nl_net->ipv6.rt6_stats->fib_rt_entries--;
1315 				} else {
1316 					ins = &iter->fib6_next;
1317 				}
1318 				iter = rcu_dereference_protected(*ins,
1319 					lockdep_is_held(&rt->fib6_table->tb6_lock));
1320 			}
1321 			WARN_ON(nsiblings != 0);
1322 		}
1323 	}
1324 
1325 	return 0;
1326 }
1327 
1328 static void fib6_start_gc(struct net *net, struct fib6_info *rt)
1329 {
1330 	if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
1331 	    (rt->fib6_flags & RTF_EXPIRES))
1332 		mod_timer(&net->ipv6.ip6_fib_timer,
1333 			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
1334 }
1335 
1336 void fib6_force_start_gc(struct net *net)
1337 {
1338 	if (!timer_pending(&net->ipv6.ip6_fib_timer))
1339 		mod_timer(&net->ipv6.ip6_fib_timer,
1340 			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
1341 }
1342 
1343 static void __fib6_update_sernum_upto_root(struct fib6_info *rt,
1344 					   int sernum)
1345 {
1346 	struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,
1347 				lockdep_is_held(&rt->fib6_table->tb6_lock));
1348 
1349 	/* paired with smp_rmb() in fib6_get_cookie_safe() */
1350 	smp_wmb();
1351 	while (fn) {
1352 		WRITE_ONCE(fn->fn_sernum, sernum);
1353 		fn = rcu_dereference_protected(fn->parent,
1354 				lockdep_is_held(&rt->fib6_table->tb6_lock));
1355 	}
1356 }
1357 
1358 void fib6_update_sernum_upto_root(struct net *net, struct fib6_info *rt)
1359 {
1360 	__fib6_update_sernum_upto_root(rt, fib6_new_sernum(net));
1361 }
1362 
1363 /* allow ipv4 to update sernum via ipv6_stub */
1364 void fib6_update_sernum_stub(struct net *net, struct fib6_info *f6i)
1365 {
1366 	spin_lock_bh(&f6i->fib6_table->tb6_lock);
1367 	fib6_update_sernum_upto_root(net, f6i);
1368 	spin_unlock_bh(&f6i->fib6_table->tb6_lock);
1369 }
1370 
1371 /*
1372  *	Add routing information to the routing tree.
1373  *	<destination addr>/<source addr>
1374  *	with source addr info in sub-trees
1375  *	Need to own table->tb6_lock
1376  */
1377 
1378 int fib6_add(struct fib6_node *root, struct fib6_info *rt,
1379 	     struct nl_info *info, struct netlink_ext_ack *extack)
1380 {
1381 	struct fib6_table *table = rt->fib6_table;
1382 	struct fib6_node *fn;
1383 #ifdef CONFIG_IPV6_SUBTREES
1384 	struct fib6_node *pn = NULL;
1385 #endif
1386 	int err = -ENOMEM;
1387 	int allow_create = 1;
1388 	int replace_required = 0;
1389 
1390 	if (info->nlh) {
1391 		if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
1392 			allow_create = 0;
1393 		if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
1394 			replace_required = 1;
1395 	}
1396 	if (!allow_create && !replace_required)
1397 		pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
1398 
1399 	fn = fib6_add_1(info->nl_net, table, root,
1400 			&rt->fib6_dst.addr, rt->fib6_dst.plen,
1401 			offsetof(struct fib6_info, fib6_dst), allow_create,
1402 			replace_required, extack);
1403 	if (IS_ERR(fn)) {
1404 		err = PTR_ERR(fn);
1405 		fn = NULL;
1406 		goto out;
1407 	}
1408 
1409 #ifdef CONFIG_IPV6_SUBTREES
1410 	pn = fn;
1411 
1412 	if (rt->fib6_src.plen) {
1413 		struct fib6_node *sn;
1414 
1415 		if (!rcu_access_pointer(fn->subtree)) {
1416 			struct fib6_node *sfn;
1417 
1418 			/*
1419 			 * Create subtree.
1420 			 *
1421 			 *		fn[main tree]
1422 			 *		|
1423 			 *		sfn[subtree root]
1424 			 *		   \
1425 			 *		    sn[new leaf node]
1426 			 */
1427 
1428 			/* Create subtree root node */
1429 			sfn = node_alloc(info->nl_net);
1430 			if (!sfn)
1431 				goto failure;
1432 
1433 			fib6_info_hold(info->nl_net->ipv6.fib6_null_entry);
1434 			rcu_assign_pointer(sfn->leaf,
1435 					   info->nl_net->ipv6.fib6_null_entry);
1436 			sfn->fn_flags = RTN_ROOT;
1437 
1438 			/* Now add the first leaf node to new subtree */
1439 
1440 			sn = fib6_add_1(info->nl_net, table, sfn,
1441 					&rt->fib6_src.addr, rt->fib6_src.plen,
1442 					offsetof(struct fib6_info, fib6_src),
1443 					allow_create, replace_required, extack);
1444 
1445 			if (IS_ERR(sn)) {
1446 				/* If it is failed, discard just allocated
1447 				   root, and then (in failure) stale node
1448 				   in main tree.
1449 				 */
1450 				node_free_immediate(info->nl_net, sfn);
1451 				err = PTR_ERR(sn);
1452 				goto failure;
1453 			}
1454 
1455 			/* Now link new subtree to main tree */
1456 			rcu_assign_pointer(sfn->parent, fn);
1457 			rcu_assign_pointer(fn->subtree, sfn);
1458 		} else {
1459 			sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),
1460 					&rt->fib6_src.addr, rt->fib6_src.plen,
1461 					offsetof(struct fib6_info, fib6_src),
1462 					allow_create, replace_required, extack);
1463 
1464 			if (IS_ERR(sn)) {
1465 				err = PTR_ERR(sn);
1466 				goto failure;
1467 			}
1468 		}
1469 
1470 		if (!rcu_access_pointer(fn->leaf)) {
1471 			if (fn->fn_flags & RTN_TL_ROOT) {
1472 				/* put back null_entry for root node */
1473 				rcu_assign_pointer(fn->leaf,
1474 					    info->nl_net->ipv6.fib6_null_entry);
1475 			} else {
1476 				fib6_info_hold(rt);
1477 				rcu_assign_pointer(fn->leaf, rt);
1478 			}
1479 		}
1480 		fn = sn;
1481 	}
1482 #endif
1483 
1484 	err = fib6_add_rt2node(fn, rt, info, extack);
1485 	if (!err) {
1486 		if (rt->nh)
1487 			list_add(&rt->nh_list, &rt->nh->f6i_list);
1488 		__fib6_update_sernum_upto_root(rt, fib6_new_sernum(info->nl_net));
1489 		fib6_start_gc(info->nl_net, rt);
1490 	}
1491 
1492 out:
1493 	if (err) {
1494 #ifdef CONFIG_IPV6_SUBTREES
1495 		/*
1496 		 * If fib6_add_1 has cleared the old leaf pointer in the
1497 		 * super-tree leaf node we have to find a new one for it.
1498 		 */
1499 		if (pn != fn) {
1500 			struct fib6_info *pn_leaf =
1501 				rcu_dereference_protected(pn->leaf,
1502 				    lockdep_is_held(&table->tb6_lock));
1503 			if (pn_leaf == rt) {
1504 				pn_leaf = NULL;
1505 				RCU_INIT_POINTER(pn->leaf, NULL);
1506 				fib6_info_release(rt);
1507 			}
1508 			if (!pn_leaf && !(pn->fn_flags & RTN_RTINFO)) {
1509 				pn_leaf = fib6_find_prefix(info->nl_net, table,
1510 							   pn);
1511 				if (!pn_leaf)
1512 					pn_leaf =
1513 					    info->nl_net->ipv6.fib6_null_entry;
1514 				fib6_info_hold(pn_leaf);
1515 				rcu_assign_pointer(pn->leaf, pn_leaf);
1516 			}
1517 		}
1518 #endif
1519 		goto failure;
1520 	} else if (fib6_requires_src(rt)) {
1521 		fib6_routes_require_src_inc(info->nl_net);
1522 	}
1523 	return err;
1524 
1525 failure:
1526 	/* fn->leaf could be NULL and fib6_repair_tree() needs to be called if:
1527 	 * 1. fn is an intermediate node and we failed to add the new
1528 	 * route to it in both subtree creation failure and fib6_add_rt2node()
1529 	 * failure case.
1530 	 * 2. fn is the root node in the table and we fail to add the first
1531 	 * default route to it.
1532 	 */
1533 	if (fn &&
1534 	    (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||
1535 	     (fn->fn_flags & RTN_TL_ROOT &&
1536 	      !rcu_access_pointer(fn->leaf))))
1537 		fib6_repair_tree(info->nl_net, table, fn);
1538 	return err;
1539 }
1540 
1541 /*
1542  *	Routing tree lookup
1543  *
1544  */
1545 
1546 struct lookup_args {
1547 	int			offset;		/* key offset on fib6_info */
1548 	const struct in6_addr	*addr;		/* search key			*/
1549 };
1550 
1551 static struct fib6_node *fib6_node_lookup_1(struct fib6_node *root,
1552 					    struct lookup_args *args)
1553 {
1554 	struct fib6_node *fn;
1555 	__be32 dir;
1556 
1557 	if (unlikely(args->offset == 0))
1558 		return NULL;
1559 
1560 	/*
1561 	 *	Descend on a tree
1562 	 */
1563 
1564 	fn = root;
1565 
1566 	for (;;) {
1567 		struct fib6_node *next;
1568 
1569 		dir = addr_bit_set(args->addr, fn->fn_bit);
1570 
1571 		next = dir ? rcu_dereference(fn->right) :
1572 			     rcu_dereference(fn->left);
1573 
1574 		if (next) {
1575 			fn = next;
1576 			continue;
1577 		}
1578 		break;
1579 	}
1580 
1581 	while (fn) {
1582 		struct fib6_node *subtree = FIB6_SUBTREE(fn);
1583 
1584 		if (subtree || fn->fn_flags & RTN_RTINFO) {
1585 			struct fib6_info *leaf = rcu_dereference(fn->leaf);
1586 			struct rt6key *key;
1587 
1588 			if (!leaf)
1589 				goto backtrack;
1590 
1591 			key = (struct rt6key *) ((u8 *)leaf + args->offset);
1592 
1593 			if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
1594 #ifdef CONFIG_IPV6_SUBTREES
1595 				if (subtree) {
1596 					struct fib6_node *sfn;
1597 					sfn = fib6_node_lookup_1(subtree,
1598 								 args + 1);
1599 					if (!sfn)
1600 						goto backtrack;
1601 					fn = sfn;
1602 				}
1603 #endif
1604 				if (fn->fn_flags & RTN_RTINFO)
1605 					return fn;
1606 			}
1607 		}
1608 backtrack:
1609 		if (fn->fn_flags & RTN_ROOT)
1610 			break;
1611 
1612 		fn = rcu_dereference(fn->parent);
1613 	}
1614 
1615 	return NULL;
1616 }
1617 
1618 /* called with rcu_read_lock() held
1619  */
1620 struct fib6_node *fib6_node_lookup(struct fib6_node *root,
1621 				   const struct in6_addr *daddr,
1622 				   const struct in6_addr *saddr)
1623 {
1624 	struct fib6_node *fn;
1625 	struct lookup_args args[] = {
1626 		{
1627 			.offset = offsetof(struct fib6_info, fib6_dst),
1628 			.addr = daddr,
1629 		},
1630 #ifdef CONFIG_IPV6_SUBTREES
1631 		{
1632 			.offset = offsetof(struct fib6_info, fib6_src),
1633 			.addr = saddr,
1634 		},
1635 #endif
1636 		{
1637 			.offset = 0,	/* sentinel */
1638 		}
1639 	};
1640 
1641 	fn = fib6_node_lookup_1(root, daddr ? args : args + 1);
1642 	if (!fn || fn->fn_flags & RTN_TL_ROOT)
1643 		fn = root;
1644 
1645 	return fn;
1646 }
1647 
1648 /*
1649  *	Get node with specified destination prefix (and source prefix,
1650  *	if subtrees are used)
1651  *	exact_match == true means we try to find fn with exact match of
1652  *	the passed in prefix addr
1653  *	exact_match == false means we try to find fn with longest prefix
1654  *	match of the passed in prefix addr. This is useful for finding fn
1655  *	for cached route as it will be stored in the exception table under
1656  *	the node with longest prefix length.
1657  */
1658 
1659 
1660 static struct fib6_node *fib6_locate_1(struct fib6_node *root,
1661 				       const struct in6_addr *addr,
1662 				       int plen, int offset,
1663 				       bool exact_match)
1664 {
1665 	struct fib6_node *fn, *prev = NULL;
1666 
1667 	for (fn = root; fn ; ) {
1668 		struct fib6_info *leaf = rcu_dereference(fn->leaf);
1669 		struct rt6key *key;
1670 
1671 		/* This node is being deleted */
1672 		if (!leaf) {
1673 			if (plen <= fn->fn_bit)
1674 				goto out;
1675 			else
1676 				goto next;
1677 		}
1678 
1679 		key = (struct rt6key *)((u8 *)leaf + offset);
1680 
1681 		/*
1682 		 *	Prefix match
1683 		 */
1684 		if (plen < fn->fn_bit ||
1685 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1686 			goto out;
1687 
1688 		if (plen == fn->fn_bit)
1689 			return fn;
1690 
1691 		if (fn->fn_flags & RTN_RTINFO)
1692 			prev = fn;
1693 
1694 next:
1695 		/*
1696 		 *	We have more bits to go
1697 		 */
1698 		if (addr_bit_set(addr, fn->fn_bit))
1699 			fn = rcu_dereference(fn->right);
1700 		else
1701 			fn = rcu_dereference(fn->left);
1702 	}
1703 out:
1704 	if (exact_match)
1705 		return NULL;
1706 	else
1707 		return prev;
1708 }
1709 
1710 struct fib6_node *fib6_locate(struct fib6_node *root,
1711 			      const struct in6_addr *daddr, int dst_len,
1712 			      const struct in6_addr *saddr, int src_len,
1713 			      bool exact_match)
1714 {
1715 	struct fib6_node *fn;
1716 
1717 	fn = fib6_locate_1(root, daddr, dst_len,
1718 			   offsetof(struct fib6_info, fib6_dst),
1719 			   exact_match);
1720 
1721 #ifdef CONFIG_IPV6_SUBTREES
1722 	if (src_len) {
1723 		WARN_ON(saddr == NULL);
1724 		if (fn) {
1725 			struct fib6_node *subtree = FIB6_SUBTREE(fn);
1726 
1727 			if (subtree) {
1728 				fn = fib6_locate_1(subtree, saddr, src_len,
1729 					   offsetof(struct fib6_info, fib6_src),
1730 					   exact_match);
1731 			}
1732 		}
1733 	}
1734 #endif
1735 
1736 	if (fn && fn->fn_flags & RTN_RTINFO)
1737 		return fn;
1738 
1739 	return NULL;
1740 }
1741 
1742 
1743 /*
1744  *	Deletion
1745  *
1746  */
1747 
1748 static struct fib6_info *fib6_find_prefix(struct net *net,
1749 					 struct fib6_table *table,
1750 					 struct fib6_node *fn)
1751 {
1752 	struct fib6_node *child_left, *child_right;
1753 
1754 	if (fn->fn_flags & RTN_ROOT)
1755 		return net->ipv6.fib6_null_entry;
1756 
1757 	while (fn) {
1758 		child_left = rcu_dereference_protected(fn->left,
1759 				    lockdep_is_held(&table->tb6_lock));
1760 		child_right = rcu_dereference_protected(fn->right,
1761 				    lockdep_is_held(&table->tb6_lock));
1762 		if (child_left)
1763 			return rcu_dereference_protected(child_left->leaf,
1764 					lockdep_is_held(&table->tb6_lock));
1765 		if (child_right)
1766 			return rcu_dereference_protected(child_right->leaf,
1767 					lockdep_is_held(&table->tb6_lock));
1768 
1769 		fn = FIB6_SUBTREE(fn);
1770 	}
1771 	return NULL;
1772 }
1773 
1774 /*
1775  *	Called to trim the tree of intermediate nodes when possible. "fn"
1776  *	is the node we want to try and remove.
1777  *	Need to own table->tb6_lock
1778  */
1779 
1780 static struct fib6_node *fib6_repair_tree(struct net *net,
1781 					  struct fib6_table *table,
1782 					  struct fib6_node *fn)
1783 {
1784 	int children;
1785 	int nstate;
1786 	struct fib6_node *child;
1787 	struct fib6_walker *w;
1788 	int iter = 0;
1789 
1790 	/* Set fn->leaf to null_entry for root node. */
1791 	if (fn->fn_flags & RTN_TL_ROOT) {
1792 		rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);
1793 		return fn;
1794 	}
1795 
1796 	for (;;) {
1797 		struct fib6_node *fn_r = rcu_dereference_protected(fn->right,
1798 					    lockdep_is_held(&table->tb6_lock));
1799 		struct fib6_node *fn_l = rcu_dereference_protected(fn->left,
1800 					    lockdep_is_held(&table->tb6_lock));
1801 		struct fib6_node *pn = rcu_dereference_protected(fn->parent,
1802 					    lockdep_is_held(&table->tb6_lock));
1803 		struct fib6_node *pn_r = rcu_dereference_protected(pn->right,
1804 					    lockdep_is_held(&table->tb6_lock));
1805 		struct fib6_node *pn_l = rcu_dereference_protected(pn->left,
1806 					    lockdep_is_held(&table->tb6_lock));
1807 		struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,
1808 					    lockdep_is_held(&table->tb6_lock));
1809 		struct fib6_info *pn_leaf = rcu_dereference_protected(pn->leaf,
1810 					    lockdep_is_held(&table->tb6_lock));
1811 		struct fib6_info *new_fn_leaf;
1812 
1813 		RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1814 		iter++;
1815 
1816 		WARN_ON(fn->fn_flags & RTN_RTINFO);
1817 		WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1818 		WARN_ON(fn_leaf);
1819 
1820 		children = 0;
1821 		child = NULL;
1822 		if (fn_r) {
1823 			child = fn_r;
1824 			children |= 1;
1825 		}
1826 		if (fn_l) {
1827 			child = fn_l;
1828 			children |= 2;
1829 		}
1830 
1831 		if (children == 3 || FIB6_SUBTREE(fn)
1832 #ifdef CONFIG_IPV6_SUBTREES
1833 		    /* Subtree root (i.e. fn) may have one child */
1834 		    || (children && fn->fn_flags & RTN_ROOT)
1835 #endif
1836 		    ) {
1837 			new_fn_leaf = fib6_find_prefix(net, table, fn);
1838 #if RT6_DEBUG >= 2
1839 			if (!new_fn_leaf) {
1840 				WARN_ON(!new_fn_leaf);
1841 				new_fn_leaf = net->ipv6.fib6_null_entry;
1842 			}
1843 #endif
1844 			fib6_info_hold(new_fn_leaf);
1845 			rcu_assign_pointer(fn->leaf, new_fn_leaf);
1846 			return pn;
1847 		}
1848 
1849 #ifdef CONFIG_IPV6_SUBTREES
1850 		if (FIB6_SUBTREE(pn) == fn) {
1851 			WARN_ON(!(fn->fn_flags & RTN_ROOT));
1852 			RCU_INIT_POINTER(pn->subtree, NULL);
1853 			nstate = FWS_L;
1854 		} else {
1855 			WARN_ON(fn->fn_flags & RTN_ROOT);
1856 #endif
1857 			if (pn_r == fn)
1858 				rcu_assign_pointer(pn->right, child);
1859 			else if (pn_l == fn)
1860 				rcu_assign_pointer(pn->left, child);
1861 #if RT6_DEBUG >= 2
1862 			else
1863 				WARN_ON(1);
1864 #endif
1865 			if (child)
1866 				rcu_assign_pointer(child->parent, pn);
1867 			nstate = FWS_R;
1868 #ifdef CONFIG_IPV6_SUBTREES
1869 		}
1870 #endif
1871 
1872 		read_lock(&net->ipv6.fib6_walker_lock);
1873 		FOR_WALKERS(net, w) {
1874 			if (!child) {
1875 				if (w->node == fn) {
1876 					RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1877 					w->node = pn;
1878 					w->state = nstate;
1879 				}
1880 			} else {
1881 				if (w->node == fn) {
1882 					w->node = child;
1883 					if (children&2) {
1884 						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1885 						w->state = w->state >= FWS_R ? FWS_U : FWS_INIT;
1886 					} else {
1887 						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1888 						w->state = w->state >= FWS_C ? FWS_U : FWS_INIT;
1889 					}
1890 				}
1891 			}
1892 		}
1893 		read_unlock(&net->ipv6.fib6_walker_lock);
1894 
1895 		node_free(net, fn);
1896 		if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
1897 			return pn;
1898 
1899 		RCU_INIT_POINTER(pn->leaf, NULL);
1900 		fib6_info_release(pn_leaf);
1901 		fn = pn;
1902 	}
1903 }
1904 
1905 static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,
1906 			   struct fib6_info __rcu **rtp, struct nl_info *info)
1907 {
1908 	struct fib6_info *leaf, *replace_rt = NULL;
1909 	struct fib6_walker *w;
1910 	struct fib6_info *rt = rcu_dereference_protected(*rtp,
1911 				    lockdep_is_held(&table->tb6_lock));
1912 	struct net *net = info->nl_net;
1913 	bool notify_del = false;
1914 
1915 	RT6_TRACE("fib6_del_route\n");
1916 
1917 	/* If the deleted route is the first in the node and it is not part of
1918 	 * a multipath route, then we need to replace it with the next route
1919 	 * in the node, if exists.
1920 	 */
1921 	leaf = rcu_dereference_protected(fn->leaf,
1922 					 lockdep_is_held(&table->tb6_lock));
1923 	if (leaf == rt && !rt->fib6_nsiblings) {
1924 		if (rcu_access_pointer(rt->fib6_next))
1925 			replace_rt = rcu_dereference_protected(rt->fib6_next,
1926 					    lockdep_is_held(&table->tb6_lock));
1927 		else
1928 			notify_del = true;
1929 	}
1930 
1931 	/* Unlink it */
1932 	*rtp = rt->fib6_next;
1933 	rt->fib6_node = NULL;
1934 	net->ipv6.rt6_stats->fib_rt_entries--;
1935 	net->ipv6.rt6_stats->fib_discarded_routes++;
1936 
1937 	/* Reset round-robin state, if necessary */
1938 	if (rcu_access_pointer(fn->rr_ptr) == rt)
1939 		fn->rr_ptr = NULL;
1940 
1941 	/* Remove this entry from other siblings */
1942 	if (rt->fib6_nsiblings) {
1943 		struct fib6_info *sibling, *next_sibling;
1944 
1945 		/* The route is deleted from a multipath route. If this
1946 		 * multipath route is the first route in the node, then we need
1947 		 * to emit a delete notification. Otherwise, we need to skip
1948 		 * the notification.
1949 		 */
1950 		if (rt->fib6_metric == leaf->fib6_metric &&
1951 		    rt6_qualify_for_ecmp(leaf))
1952 			notify_del = true;
1953 		list_for_each_entry_safe(sibling, next_sibling,
1954 					 &rt->fib6_siblings, fib6_siblings)
1955 			sibling->fib6_nsiblings--;
1956 		rt->fib6_nsiblings = 0;
1957 		list_del_init(&rt->fib6_siblings);
1958 		rt6_multipath_rebalance(next_sibling);
1959 	}
1960 
1961 	/* Adjust walkers */
1962 	read_lock(&net->ipv6.fib6_walker_lock);
1963 	FOR_WALKERS(net, w) {
1964 		if (w->state == FWS_C && w->leaf == rt) {
1965 			RT6_TRACE("walker %p adjusted by delroute\n", w);
1966 			w->leaf = rcu_dereference_protected(rt->fib6_next,
1967 					    lockdep_is_held(&table->tb6_lock));
1968 			if (!w->leaf)
1969 				w->state = FWS_U;
1970 		}
1971 	}
1972 	read_unlock(&net->ipv6.fib6_walker_lock);
1973 
1974 	/* If it was last route, call fib6_repair_tree() to:
1975 	 * 1. For root node, put back null_entry as how the table was created.
1976 	 * 2. For other nodes, expunge its radix tree node.
1977 	 */
1978 	if (!rcu_access_pointer(fn->leaf)) {
1979 		if (!(fn->fn_flags & RTN_TL_ROOT)) {
1980 			fn->fn_flags &= ~RTN_RTINFO;
1981 			net->ipv6.rt6_stats->fib_route_nodes--;
1982 		}
1983 		fn = fib6_repair_tree(net, table, fn);
1984 	}
1985 
1986 	fib6_purge_rt(rt, fn, net);
1987 
1988 	if (!info->skip_notify_kernel) {
1989 		if (notify_del)
1990 			call_fib6_entry_notifiers(net, FIB_EVENT_ENTRY_DEL,
1991 						  rt, NULL);
1992 		else if (replace_rt)
1993 			call_fib6_entry_notifiers_replace(net, replace_rt);
1994 	}
1995 	if (!info->skip_notify)
1996 		inet6_rt_notify(RTM_DELROUTE, rt, info, 0);
1997 
1998 	fib6_info_release(rt);
1999 }
2000 
2001 /* Need to own table->tb6_lock */
2002 int fib6_del(struct fib6_info *rt, struct nl_info *info)
2003 {
2004 	struct net *net = info->nl_net;
2005 	struct fib6_info __rcu **rtp;
2006 	struct fib6_info __rcu **rtp_next;
2007 	struct fib6_table *table;
2008 	struct fib6_node *fn;
2009 
2010 	if (rt == net->ipv6.fib6_null_entry)
2011 		return -ENOENT;
2012 
2013 	table = rt->fib6_table;
2014 	fn = rcu_dereference_protected(rt->fib6_node,
2015 				       lockdep_is_held(&table->tb6_lock));
2016 	if (!fn)
2017 		return -ENOENT;
2018 
2019 	WARN_ON(!(fn->fn_flags & RTN_RTINFO));
2020 
2021 	/*
2022 	 *	Walk the leaf entries looking for ourself
2023 	 */
2024 
2025 	for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {
2026 		struct fib6_info *cur = rcu_dereference_protected(*rtp,
2027 					lockdep_is_held(&table->tb6_lock));
2028 		if (rt == cur) {
2029 			if (fib6_requires_src(cur))
2030 				fib6_routes_require_src_dec(info->nl_net);
2031 			fib6_del_route(table, fn, rtp, info);
2032 			return 0;
2033 		}
2034 		rtp_next = &cur->fib6_next;
2035 	}
2036 	return -ENOENT;
2037 }
2038 
2039 /*
2040  *	Tree traversal function.
2041  *
2042  *	Certainly, it is not interrupt safe.
2043  *	However, it is internally reenterable wrt itself and fib6_add/fib6_del.
2044  *	It means, that we can modify tree during walking
2045  *	and use this function for garbage collection, clone pruning,
2046  *	cleaning tree when a device goes down etc. etc.
2047  *
2048  *	It guarantees that every node will be traversed,
2049  *	and that it will be traversed only once.
2050  *
2051  *	Callback function w->func may return:
2052  *	0 -> continue walking.
2053  *	positive value -> walking is suspended (used by tree dumps,
2054  *	and probably by gc, if it will be split to several slices)
2055  *	negative value -> terminate walking.
2056  *
2057  *	The function itself returns:
2058  *	0   -> walk is complete.
2059  *	>0  -> walk is incomplete (i.e. suspended)
2060  *	<0  -> walk is terminated by an error.
2061  *
2062  *	This function is called with tb6_lock held.
2063  */
2064 
2065 static int fib6_walk_continue(struct fib6_walker *w)
2066 {
2067 	struct fib6_node *fn, *pn, *left, *right;
2068 
2069 	/* w->root should always be table->tb6_root */
2070 	WARN_ON_ONCE(!(w->root->fn_flags & RTN_TL_ROOT));
2071 
2072 	for (;;) {
2073 		fn = w->node;
2074 		if (!fn)
2075 			return 0;
2076 
2077 		switch (w->state) {
2078 #ifdef CONFIG_IPV6_SUBTREES
2079 		case FWS_S:
2080 			if (FIB6_SUBTREE(fn)) {
2081 				w->node = FIB6_SUBTREE(fn);
2082 				continue;
2083 			}
2084 			w->state = FWS_L;
2085 			fallthrough;
2086 #endif
2087 		case FWS_L:
2088 			left = rcu_dereference_protected(fn->left, 1);
2089 			if (left) {
2090 				w->node = left;
2091 				w->state = FWS_INIT;
2092 				continue;
2093 			}
2094 			w->state = FWS_R;
2095 			fallthrough;
2096 		case FWS_R:
2097 			right = rcu_dereference_protected(fn->right, 1);
2098 			if (right) {
2099 				w->node = right;
2100 				w->state = FWS_INIT;
2101 				continue;
2102 			}
2103 			w->state = FWS_C;
2104 			w->leaf = rcu_dereference_protected(fn->leaf, 1);
2105 			fallthrough;
2106 		case FWS_C:
2107 			if (w->leaf && fn->fn_flags & RTN_RTINFO) {
2108 				int err;
2109 
2110 				if (w->skip) {
2111 					w->skip--;
2112 					goto skip;
2113 				}
2114 
2115 				err = w->func(w);
2116 				if (err)
2117 					return err;
2118 
2119 				w->count++;
2120 				continue;
2121 			}
2122 skip:
2123 			w->state = FWS_U;
2124 			fallthrough;
2125 		case FWS_U:
2126 			if (fn == w->root)
2127 				return 0;
2128 			pn = rcu_dereference_protected(fn->parent, 1);
2129 			left = rcu_dereference_protected(pn->left, 1);
2130 			right = rcu_dereference_protected(pn->right, 1);
2131 			w->node = pn;
2132 #ifdef CONFIG_IPV6_SUBTREES
2133 			if (FIB6_SUBTREE(pn) == fn) {
2134 				WARN_ON(!(fn->fn_flags & RTN_ROOT));
2135 				w->state = FWS_L;
2136 				continue;
2137 			}
2138 #endif
2139 			if (left == fn) {
2140 				w->state = FWS_R;
2141 				continue;
2142 			}
2143 			if (right == fn) {
2144 				w->state = FWS_C;
2145 				w->leaf = rcu_dereference_protected(w->node->leaf, 1);
2146 				continue;
2147 			}
2148 #if RT6_DEBUG >= 2
2149 			WARN_ON(1);
2150 #endif
2151 		}
2152 	}
2153 }
2154 
2155 static int fib6_walk(struct net *net, struct fib6_walker *w)
2156 {
2157 	int res;
2158 
2159 	w->state = FWS_INIT;
2160 	w->node = w->root;
2161 
2162 	fib6_walker_link(net, w);
2163 	res = fib6_walk_continue(w);
2164 	if (res <= 0)
2165 		fib6_walker_unlink(net, w);
2166 	return res;
2167 }
2168 
2169 static int fib6_clean_node(struct fib6_walker *w)
2170 {
2171 	int res;
2172 	struct fib6_info *rt;
2173 	struct fib6_cleaner *c = container_of(w, struct fib6_cleaner, w);
2174 	struct nl_info info = {
2175 		.nl_net = c->net,
2176 		.skip_notify = c->skip_notify,
2177 	};
2178 
2179 	if (c->sernum != FIB6_NO_SERNUM_CHANGE &&
2180 	    READ_ONCE(w->node->fn_sernum) != c->sernum)
2181 		WRITE_ONCE(w->node->fn_sernum, c->sernum);
2182 
2183 	if (!c->func) {
2184 		WARN_ON_ONCE(c->sernum == FIB6_NO_SERNUM_CHANGE);
2185 		w->leaf = NULL;
2186 		return 0;
2187 	}
2188 
2189 	for_each_fib6_walker_rt(w) {
2190 		res = c->func(rt, c->arg);
2191 		if (res == -1) {
2192 			w->leaf = rt;
2193 			res = fib6_del(rt, &info);
2194 			if (res) {
2195 #if RT6_DEBUG >= 2
2196 				pr_debug("%s: del failed: rt=%p@%p err=%d\n",
2197 					 __func__, rt,
2198 					 rcu_access_pointer(rt->fib6_node),
2199 					 res);
2200 #endif
2201 				continue;
2202 			}
2203 			return 0;
2204 		} else if (res == -2) {
2205 			if (WARN_ON(!rt->fib6_nsiblings))
2206 				continue;
2207 			rt = list_last_entry(&rt->fib6_siblings,
2208 					     struct fib6_info, fib6_siblings);
2209 			continue;
2210 		}
2211 		WARN_ON(res != 0);
2212 	}
2213 	w->leaf = rt;
2214 	return 0;
2215 }
2216 
2217 /*
2218  *	Convenient frontend to tree walker.
2219  *
2220  *	func is called on each route.
2221  *		It may return -2 -> skip multipath route.
2222  *			      -1 -> delete this route.
2223  *		              0  -> continue walking
2224  */
2225 
2226 static void fib6_clean_tree(struct net *net, struct fib6_node *root,
2227 			    int (*func)(struct fib6_info *, void *arg),
2228 			    int sernum, void *arg, bool skip_notify)
2229 {
2230 	struct fib6_cleaner c;
2231 
2232 	c.w.root = root;
2233 	c.w.func = fib6_clean_node;
2234 	c.w.count = 0;
2235 	c.w.skip = 0;
2236 	c.w.skip_in_node = 0;
2237 	c.func = func;
2238 	c.sernum = sernum;
2239 	c.arg = arg;
2240 	c.net = net;
2241 	c.skip_notify = skip_notify;
2242 
2243 	fib6_walk(net, &c.w);
2244 }
2245 
2246 static void __fib6_clean_all(struct net *net,
2247 			     int (*func)(struct fib6_info *, void *),
2248 			     int sernum, void *arg, bool skip_notify)
2249 {
2250 	struct fib6_table *table;
2251 	struct hlist_head *head;
2252 	unsigned int h;
2253 
2254 	rcu_read_lock();
2255 	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
2256 		head = &net->ipv6.fib_table_hash[h];
2257 		hlist_for_each_entry_rcu(table, head, tb6_hlist) {
2258 			spin_lock_bh(&table->tb6_lock);
2259 			fib6_clean_tree(net, &table->tb6_root,
2260 					func, sernum, arg, skip_notify);
2261 			spin_unlock_bh(&table->tb6_lock);
2262 		}
2263 	}
2264 	rcu_read_unlock();
2265 }
2266 
2267 void fib6_clean_all(struct net *net, int (*func)(struct fib6_info *, void *),
2268 		    void *arg)
2269 {
2270 	__fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, false);
2271 }
2272 
2273 void fib6_clean_all_skip_notify(struct net *net,
2274 				int (*func)(struct fib6_info *, void *),
2275 				void *arg)
2276 {
2277 	__fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, true);
2278 }
2279 
2280 static void fib6_flush_trees(struct net *net)
2281 {
2282 	int new_sernum = fib6_new_sernum(net);
2283 
2284 	__fib6_clean_all(net, NULL, new_sernum, NULL, false);
2285 }
2286 
2287 /*
2288  *	Garbage collection
2289  */
2290 
2291 static int fib6_age(struct fib6_info *rt, void *arg)
2292 {
2293 	struct fib6_gc_args *gc_args = arg;
2294 	unsigned long now = jiffies;
2295 
2296 	/*
2297 	 *	check addrconf expiration here.
2298 	 *	Routes are expired even if they are in use.
2299 	 */
2300 
2301 	if (rt->fib6_flags & RTF_EXPIRES && rt->expires) {
2302 		if (time_after(now, rt->expires)) {
2303 			RT6_TRACE("expiring %p\n", rt);
2304 			return -1;
2305 		}
2306 		gc_args->more++;
2307 	}
2308 
2309 	/*	Also age clones in the exception table.
2310 	 *	Note, that clones are aged out
2311 	 *	only if they are not in use now.
2312 	 */
2313 	rt6_age_exceptions(rt, gc_args, now);
2314 
2315 	return 0;
2316 }
2317 
2318 void fib6_run_gc(unsigned long expires, struct net *net, bool force)
2319 {
2320 	struct fib6_gc_args gc_args;
2321 	unsigned long now;
2322 
2323 	if (force) {
2324 		spin_lock_bh(&net->ipv6.fib6_gc_lock);
2325 	} else if (!spin_trylock_bh(&net->ipv6.fib6_gc_lock)) {
2326 		mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
2327 		return;
2328 	}
2329 	gc_args.timeout = expires ? (int)expires :
2330 			  net->ipv6.sysctl.ip6_rt_gc_interval;
2331 	gc_args.more = 0;
2332 
2333 	fib6_clean_all(net, fib6_age, &gc_args);
2334 	now = jiffies;
2335 	net->ipv6.ip6_rt_last_gc = now;
2336 
2337 	if (gc_args.more)
2338 		mod_timer(&net->ipv6.ip6_fib_timer,
2339 			  round_jiffies(now
2340 					+ net->ipv6.sysctl.ip6_rt_gc_interval));
2341 	else
2342 		del_timer(&net->ipv6.ip6_fib_timer);
2343 	spin_unlock_bh(&net->ipv6.fib6_gc_lock);
2344 }
2345 
2346 static void fib6_gc_timer_cb(struct timer_list *t)
2347 {
2348 	struct net *arg = from_timer(arg, t, ipv6.ip6_fib_timer);
2349 
2350 	fib6_run_gc(0, arg, true);
2351 }
2352 
2353 static int __net_init fib6_net_init(struct net *net)
2354 {
2355 	size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
2356 	int err;
2357 
2358 	err = fib6_notifier_init(net);
2359 	if (err)
2360 		return err;
2361 
2362 	/* Default to 3-tuple */
2363 	net->ipv6.sysctl.multipath_hash_fields =
2364 		FIB_MULTIPATH_HASH_FIELD_DEFAULT_MASK;
2365 
2366 	spin_lock_init(&net->ipv6.fib6_gc_lock);
2367 	rwlock_init(&net->ipv6.fib6_walker_lock);
2368 	INIT_LIST_HEAD(&net->ipv6.fib6_walkers);
2369 	timer_setup(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, 0);
2370 
2371 	net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
2372 	if (!net->ipv6.rt6_stats)
2373 		goto out_notifier;
2374 
2375 	/* Avoid false sharing : Use at least a full cache line */
2376 	size = max_t(size_t, size, L1_CACHE_BYTES);
2377 
2378 	net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
2379 	if (!net->ipv6.fib_table_hash)
2380 		goto out_rt6_stats;
2381 
2382 	net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
2383 					  GFP_KERNEL);
2384 	if (!net->ipv6.fib6_main_tbl)
2385 		goto out_fib_table_hash;
2386 
2387 	net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
2388 	rcu_assign_pointer(net->ipv6.fib6_main_tbl->tb6_root.leaf,
2389 			   net->ipv6.fib6_null_entry);
2390 	net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
2391 		RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
2392 	inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
2393 
2394 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
2395 	net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
2396 					   GFP_KERNEL);
2397 	if (!net->ipv6.fib6_local_tbl)
2398 		goto out_fib6_main_tbl;
2399 	net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
2400 	rcu_assign_pointer(net->ipv6.fib6_local_tbl->tb6_root.leaf,
2401 			   net->ipv6.fib6_null_entry);
2402 	net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
2403 		RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
2404 	inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
2405 #endif
2406 	fib6_tables_init(net);
2407 
2408 	return 0;
2409 
2410 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
2411 out_fib6_main_tbl:
2412 	kfree(net->ipv6.fib6_main_tbl);
2413 #endif
2414 out_fib_table_hash:
2415 	kfree(net->ipv6.fib_table_hash);
2416 out_rt6_stats:
2417 	kfree(net->ipv6.rt6_stats);
2418 out_notifier:
2419 	fib6_notifier_exit(net);
2420 	return -ENOMEM;
2421 }
2422 
2423 static void fib6_net_exit(struct net *net)
2424 {
2425 	unsigned int i;
2426 
2427 	del_timer_sync(&net->ipv6.ip6_fib_timer);
2428 
2429 	for (i = 0; i < FIB6_TABLE_HASHSZ; i++) {
2430 		struct hlist_head *head = &net->ipv6.fib_table_hash[i];
2431 		struct hlist_node *tmp;
2432 		struct fib6_table *tb;
2433 
2434 		hlist_for_each_entry_safe(tb, tmp, head, tb6_hlist) {
2435 			hlist_del(&tb->tb6_hlist);
2436 			fib6_free_table(tb);
2437 		}
2438 	}
2439 
2440 	kfree(net->ipv6.fib_table_hash);
2441 	kfree(net->ipv6.rt6_stats);
2442 	fib6_notifier_exit(net);
2443 }
2444 
2445 static struct pernet_operations fib6_net_ops = {
2446 	.init = fib6_net_init,
2447 	.exit = fib6_net_exit,
2448 };
2449 
2450 int __init fib6_init(void)
2451 {
2452 	int ret = -ENOMEM;
2453 
2454 	fib6_node_kmem = kmem_cache_create("fib6_nodes",
2455 					   sizeof(struct fib6_node), 0,
2456 					   SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT,
2457 					   NULL);
2458 	if (!fib6_node_kmem)
2459 		goto out;
2460 
2461 	ret = register_pernet_subsys(&fib6_net_ops);
2462 	if (ret)
2463 		goto out_kmem_cache_create;
2464 
2465 	ret = rtnl_register_module(THIS_MODULE, PF_INET6, RTM_GETROUTE, NULL,
2466 				   inet6_dump_fib, 0);
2467 	if (ret)
2468 		goto out_unregister_subsys;
2469 
2470 	__fib6_flush_trees = fib6_flush_trees;
2471 out:
2472 	return ret;
2473 
2474 out_unregister_subsys:
2475 	unregister_pernet_subsys(&fib6_net_ops);
2476 out_kmem_cache_create:
2477 	kmem_cache_destroy(fib6_node_kmem);
2478 	goto out;
2479 }
2480 
2481 void fib6_gc_cleanup(void)
2482 {
2483 	unregister_pernet_subsys(&fib6_net_ops);
2484 	kmem_cache_destroy(fib6_node_kmem);
2485 }
2486 
2487 #ifdef CONFIG_PROC_FS
2488 static int ipv6_route_native_seq_show(struct seq_file *seq, void *v)
2489 {
2490 	struct fib6_info *rt = v;
2491 	struct ipv6_route_iter *iter = seq->private;
2492 	struct fib6_nh *fib6_nh = rt->fib6_nh;
2493 	unsigned int flags = rt->fib6_flags;
2494 	const struct net_device *dev;
2495 
2496 	if (rt->nh)
2497 		fib6_nh = nexthop_fib6_nh(rt->nh);
2498 
2499 	seq_printf(seq, "%pi6 %02x ", &rt->fib6_dst.addr, rt->fib6_dst.plen);
2500 
2501 #ifdef CONFIG_IPV6_SUBTREES
2502 	seq_printf(seq, "%pi6 %02x ", &rt->fib6_src.addr, rt->fib6_src.plen);
2503 #else
2504 	seq_puts(seq, "00000000000000000000000000000000 00 ");
2505 #endif
2506 	if (fib6_nh->fib_nh_gw_family) {
2507 		flags |= RTF_GATEWAY;
2508 		seq_printf(seq, "%pi6", &fib6_nh->fib_nh_gw6);
2509 	} else {
2510 		seq_puts(seq, "00000000000000000000000000000000");
2511 	}
2512 
2513 	dev = fib6_nh->fib_nh_dev;
2514 	seq_printf(seq, " %08x %08x %08x %08x %8s\n",
2515 		   rt->fib6_metric, refcount_read(&rt->fib6_ref), 0,
2516 		   flags, dev ? dev->name : "");
2517 	iter->w.leaf = NULL;
2518 	return 0;
2519 }
2520 
2521 static int ipv6_route_yield(struct fib6_walker *w)
2522 {
2523 	struct ipv6_route_iter *iter = w->args;
2524 
2525 	if (!iter->skip)
2526 		return 1;
2527 
2528 	do {
2529 		iter->w.leaf = rcu_dereference_protected(
2530 				iter->w.leaf->fib6_next,
2531 				lockdep_is_held(&iter->tbl->tb6_lock));
2532 		iter->skip--;
2533 		if (!iter->skip && iter->w.leaf)
2534 			return 1;
2535 	} while (iter->w.leaf);
2536 
2537 	return 0;
2538 }
2539 
2540 static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter,
2541 				      struct net *net)
2542 {
2543 	memset(&iter->w, 0, sizeof(iter->w));
2544 	iter->w.func = ipv6_route_yield;
2545 	iter->w.root = &iter->tbl->tb6_root;
2546 	iter->w.state = FWS_INIT;
2547 	iter->w.node = iter->w.root;
2548 	iter->w.args = iter;
2549 	iter->sernum = READ_ONCE(iter->w.root->fn_sernum);
2550 	INIT_LIST_HEAD(&iter->w.lh);
2551 	fib6_walker_link(net, &iter->w);
2552 }
2553 
2554 static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
2555 						    struct net *net)
2556 {
2557 	unsigned int h;
2558 	struct hlist_node *node;
2559 
2560 	if (tbl) {
2561 		h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
2562 		node = rcu_dereference(hlist_next_rcu(&tbl->tb6_hlist));
2563 	} else {
2564 		h = 0;
2565 		node = NULL;
2566 	}
2567 
2568 	while (!node && h < FIB6_TABLE_HASHSZ) {
2569 		node = rcu_dereference(
2570 			hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
2571 	}
2572 	return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
2573 }
2574 
2575 static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
2576 {
2577 	int sernum = READ_ONCE(iter->w.root->fn_sernum);
2578 
2579 	if (iter->sernum != sernum) {
2580 		iter->sernum = sernum;
2581 		iter->w.state = FWS_INIT;
2582 		iter->w.node = iter->w.root;
2583 		WARN_ON(iter->w.skip);
2584 		iter->w.skip = iter->w.count;
2585 	}
2586 }
2587 
2588 static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2589 {
2590 	int r;
2591 	struct fib6_info *n;
2592 	struct net *net = seq_file_net(seq);
2593 	struct ipv6_route_iter *iter = seq->private;
2594 
2595 	++(*pos);
2596 	if (!v)
2597 		goto iter_table;
2598 
2599 	n = rcu_dereference(((struct fib6_info *)v)->fib6_next);
2600 	if (n)
2601 		return n;
2602 
2603 iter_table:
2604 	ipv6_route_check_sernum(iter);
2605 	spin_lock_bh(&iter->tbl->tb6_lock);
2606 	r = fib6_walk_continue(&iter->w);
2607 	spin_unlock_bh(&iter->tbl->tb6_lock);
2608 	if (r > 0) {
2609 		return iter->w.leaf;
2610 	} else if (r < 0) {
2611 		fib6_walker_unlink(net, &iter->w);
2612 		return NULL;
2613 	}
2614 	fib6_walker_unlink(net, &iter->w);
2615 
2616 	iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
2617 	if (!iter->tbl)
2618 		return NULL;
2619 
2620 	ipv6_route_seq_setup_walk(iter, net);
2621 	goto iter_table;
2622 }
2623 
2624 static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
2625 	__acquires(RCU)
2626 {
2627 	struct net *net = seq_file_net(seq);
2628 	struct ipv6_route_iter *iter = seq->private;
2629 
2630 	rcu_read_lock();
2631 	iter->tbl = ipv6_route_seq_next_table(NULL, net);
2632 	iter->skip = *pos;
2633 
2634 	if (iter->tbl) {
2635 		loff_t p = 0;
2636 
2637 		ipv6_route_seq_setup_walk(iter, net);
2638 		return ipv6_route_seq_next(seq, NULL, &p);
2639 	} else {
2640 		return NULL;
2641 	}
2642 }
2643 
2644 static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
2645 {
2646 	struct fib6_walker *w = &iter->w;
2647 	return w->node && !(w->state == FWS_U && w->node == w->root);
2648 }
2649 
2650 static void ipv6_route_native_seq_stop(struct seq_file *seq, void *v)
2651 	__releases(RCU)
2652 {
2653 	struct net *net = seq_file_net(seq);
2654 	struct ipv6_route_iter *iter = seq->private;
2655 
2656 	if (ipv6_route_iter_active(iter))
2657 		fib6_walker_unlink(net, &iter->w);
2658 
2659 	rcu_read_unlock();
2660 }
2661 
2662 #if IS_BUILTIN(CONFIG_IPV6) && defined(CONFIG_BPF_SYSCALL)
2663 static int ipv6_route_prog_seq_show(struct bpf_prog *prog,
2664 				    struct bpf_iter_meta *meta,
2665 				    void *v)
2666 {
2667 	struct bpf_iter__ipv6_route ctx;
2668 
2669 	ctx.meta = meta;
2670 	ctx.rt = v;
2671 	return bpf_iter_run_prog(prog, &ctx);
2672 }
2673 
2674 static int ipv6_route_seq_show(struct seq_file *seq, void *v)
2675 {
2676 	struct ipv6_route_iter *iter = seq->private;
2677 	struct bpf_iter_meta meta;
2678 	struct bpf_prog *prog;
2679 	int ret;
2680 
2681 	meta.seq = seq;
2682 	prog = bpf_iter_get_info(&meta, false);
2683 	if (!prog)
2684 		return ipv6_route_native_seq_show(seq, v);
2685 
2686 	ret = ipv6_route_prog_seq_show(prog, &meta, v);
2687 	iter->w.leaf = NULL;
2688 
2689 	return ret;
2690 }
2691 
2692 static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
2693 {
2694 	struct bpf_iter_meta meta;
2695 	struct bpf_prog *prog;
2696 
2697 	if (!v) {
2698 		meta.seq = seq;
2699 		prog = bpf_iter_get_info(&meta, true);
2700 		if (prog)
2701 			(void)ipv6_route_prog_seq_show(prog, &meta, v);
2702 	}
2703 
2704 	ipv6_route_native_seq_stop(seq, v);
2705 }
2706 #else
2707 static int ipv6_route_seq_show(struct seq_file *seq, void *v)
2708 {
2709 	return ipv6_route_native_seq_show(seq, v);
2710 }
2711 
2712 static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
2713 {
2714 	ipv6_route_native_seq_stop(seq, v);
2715 }
2716 #endif
2717 
2718 const struct seq_operations ipv6_route_seq_ops = {
2719 	.start	= ipv6_route_seq_start,
2720 	.next	= ipv6_route_seq_next,
2721 	.stop	= ipv6_route_seq_stop,
2722 	.show	= ipv6_route_seq_show
2723 };
2724 #endif /* CONFIG_PROC_FS */
2725