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