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