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