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