ip6_fib.c

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