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