// SPDX-License-Identifier: GPL-2.0-or-later

  /*

   *	Linux INET6 implementation

   *	Forwarding Information Database
   *
   *	Authors:

   *	Pedro Roque		<roque@di.fc.ul.pt>

   *

   *	Changes:
   *	Yuji SEKIYA @USAGI:	Support default route on router node;
   *				remove ip6_null_entry from the top of
   *				routing table.
   *	Ville Nuorvala:		Fixed routing subtrees.

   */

  
  #define pr_fmt(fmt) "IPv6: " fmt

  #include <linux/errno.h>
  #include <linux/types.h>
  #include <linux/net.h>
  #include <linux/route.h>
  #include <linux/netdevice.h>
  #include <linux/in6.h>
  #include <linux/init.h>

  #include <linux/list.h>

  #include <linux/slab.h>

  #include <net/ip.h>

  #include <net/ipv6.h>
  #include <net/ndisc.h>
  #include <net/addrconf.h>

  #include <net/lwtunnel.h>

  #include <net/fib_notifier.h>

  
  #include <net/ip6_fib.h>
  #include <net/ip6_route.h>

  static struct kmem_cache *fib6_node_kmem __read_mostly;

  struct fib6_cleaner {
  	struct fib6_walker w;

  	struct net *net;

  	int (*func)(struct fib6_info *, void *arg);

  	int sernum;

  	void *arg;

  	bool skip_notify;

  };

  #ifdef CONFIG_IPV6_SUBTREES
  #define FWS_INIT FWS_S

  #else
  #define FWS_INIT FWS_L

  #endif

  static struct fib6_info *fib6_find_prefix(struct net *net,

  					 struct fib6_table *table,
  					 struct fib6_node *fn);
  static struct fib6_node *fib6_repair_tree(struct net *net,
  					  struct fib6_table *table,
  					  struct fib6_node *fn);

  static int fib6_walk(struct net *net, struct fib6_walker *w);

  static int fib6_walk_continue(struct fib6_walker *w);

  
  /*
   *	A routing update causes an increase of the serial number on the
   *	affected subtree. This allows for cached routes to be asynchronously
   *	tested when modifications are made to the destination cache as a
   *	result of redirects, path MTU changes, etc.
   */

  static void fib6_gc_timer_cb(struct timer_list *t);

  #define FOR_WALKERS(net, w) \
  	list_for_each_entry(w, &(net)->ipv6.fib6_walkers, lh)

  static void fib6_walker_link(struct net *net, struct fib6_walker *w)

  {

  	write_lock_bh(&net->ipv6.fib6_walker_lock);
  	list_add(&w->lh, &net->ipv6.fib6_walkers);
  	write_unlock_bh(&net->ipv6.fib6_walker_lock);

  }

  static void fib6_walker_unlink(struct net *net, struct fib6_walker *w)

  {

  	write_lock_bh(&net->ipv6.fib6_walker_lock);

  	list_del(&w->lh);

  	write_unlock_bh(&net->ipv6.fib6_walker_lock);

  }

  static int fib6_new_sernum(struct net *net)

  {

  	int new, old;
  
  	do {

  		old = atomic_read(&net->ipv6.fib6_sernum);

  		new = old < INT_MAX ? old + 1 : 1;

  	} while (atomic_cmpxchg(&net->ipv6.fib6_sernum,
  				old, new) != old);

  	return new;

  }

  enum {
  	FIB6_NO_SERNUM_CHANGE = 0,
  };

  void fib6_update_sernum(struct net *net, struct fib6_info *f6i)

  {

  	struct fib6_node *fn;

  	fn = rcu_dereference_protected(f6i->fib6_node,
  			lockdep_is_held(&f6i->fib6_table->tb6_lock));

  	if (fn)
  		fn->fn_sernum = fib6_new_sernum(net);

  }

  /*
   *	Auxiliary address test functions for the radix tree.
   *

   *	These assume a 32bit processor (although it will work on

   *	64bit processors)
   */
  
  /*
   *	test bit
   */

  #if defined(__LITTLE_ENDIAN)
  # define BITOP_BE32_SWIZZLE	(0x1F & ~7)
  #else
  # define BITOP_BE32_SWIZZLE	0
  #endif

  static __be32 addr_bit_set(const void *token, int fn_bit)

  {

  	const __be32 *addr = token;

  	/*
  	 * Here,

  	 *	1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)

  	 * is optimized version of
  	 *	htonl(1 << ((~fn_bit)&0x1F))
  	 * See include/asm-generic/bitops/le.h.
  	 */

  	return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
  	       addr[fn_bit >> 5];

  }

  struct fib6_info *fib6_info_alloc(gfp_t gfp_flags, bool with_fib6_nh)

  {

  	struct fib6_info *f6i;

  	size_t sz = sizeof(*f6i);

  	if (with_fib6_nh)
  		sz += sizeof(struct fib6_nh);
  
  	f6i = kzalloc(sz, gfp_flags);

  	if (!f6i)
  		return NULL;

  	/* fib6_siblings is a union with nh_list, so this initializes both */

  	INIT_LIST_HEAD(&f6i->fib6_siblings);

  	refcount_set(&f6i->fib6_ref, 1);

  
  	return f6i;
  }

  void fib6_info_destroy_rcu(struct rcu_head *head)

  {

  	struct fib6_info *f6i = container_of(head, struct fib6_info, rcu);

  	WARN_ON(f6i->fib6_node);

  	if (f6i->nh)
  		nexthop_put(f6i->nh);
  	else
  		fib6_nh_release(f6i->fib6_nh);

  	ip_fib_metrics_put(f6i->fib6_metrics);

  	kfree(f6i);
  }

  EXPORT_SYMBOL_GPL(fib6_info_destroy_rcu);

  static struct fib6_node *node_alloc(struct net *net)

  {
  	struct fib6_node *fn;

  	fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);

  	if (fn)
  		net->ipv6.rt6_stats->fib_nodes++;

  
  	return fn;
  }

  static void node_free_immediate(struct net *net, struct fib6_node *fn)

  {
  	kmem_cache_free(fib6_node_kmem, fn);

  	net->ipv6.rt6_stats->fib_nodes--;

  }
  
  static void node_free_rcu(struct rcu_head *head)

  {

  	struct fib6_node *fn = container_of(head, struct fib6_node, rcu);

  	kmem_cache_free(fib6_node_kmem, fn);
  }

  static void node_free(struct net *net, struct fib6_node *fn)

  {
  	call_rcu(&fn->rcu, node_free_rcu);

  	net->ipv6.rt6_stats->fib_nodes--;

  }

  static void fib6_free_table(struct fib6_table *table)
  {
  	inetpeer_invalidate_tree(&table->tb6_peers);
  	kfree(table);
  }

  static void fib6_link_table(struct net *net, struct fib6_table *tb)

  {
  	unsigned int h;

  	/*
  	 * Initialize table lock at a single place to give lockdep a key,
  	 * tables aren't visible prior to being linked to the list.
  	 */

  	spin_lock_init(&tb->tb6_lock);

  	h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);

  
  	/*
  	 * No protection necessary, this is the only list mutatation
  	 * operation, tables never disappear once they exist.
  	 */

  	hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);

  }

  #ifdef CONFIG_IPV6_MULTIPLE_TABLES

  static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)

  {
  	struct fib6_table *table;
  
  	table = kzalloc(sizeof(*table), GFP_ATOMIC);

  	if (table) {

  		table->tb6_id = id;

  		rcu_assign_pointer(table->tb6_root.leaf,

  				   net->ipv6.fib6_null_entry);

  		table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;

  		inet_peer_base_init(&table->tb6_peers);

  	}
  
  	return table;
  }

  struct fib6_table *fib6_new_table(struct net *net, u32 id)

  {
  	struct fib6_table *tb;
  
  	if (id == 0)
  		id = RT6_TABLE_MAIN;

  	tb = fib6_get_table(net, id);

  	if (tb)
  		return tb;

  	tb = fib6_alloc_table(net, id);

  	if (tb)

  		fib6_link_table(net, tb);

  
  	return tb;
  }

  EXPORT_SYMBOL_GPL(fib6_new_table);

  struct fib6_table *fib6_get_table(struct net *net, u32 id)

  {
  	struct fib6_table *tb;

  	struct hlist_head *head;

  	unsigned int h;
  
  	if (id == 0)
  		id = RT6_TABLE_MAIN;

  	h = id & (FIB6_TABLE_HASHSZ - 1);

  	rcu_read_lock();

  	head = &net->ipv6.fib_table_hash[h];

  	hlist_for_each_entry_rcu(tb, head, tb6_hlist) {

  		if (tb->tb6_id == id) {
  			rcu_read_unlock();
  			return tb;
  		}
  	}
  	rcu_read_unlock();
  
  	return NULL;
  }

  EXPORT_SYMBOL_GPL(fib6_get_table);

  static void __net_init fib6_tables_init(struct net *net)

  {

  	fib6_link_table(net, net->ipv6.fib6_main_tbl);
  	fib6_link_table(net, net->ipv6.fib6_local_tbl);

  }

  #else

  struct fib6_table *fib6_new_table(struct net *net, u32 id)

  {

  	return fib6_get_table(net, id);

  }

  struct fib6_table *fib6_get_table(struct net *net, u32 id)

  {

  	  return net->ipv6.fib6_main_tbl;

  }

  struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,

  				   const struct sk_buff *skb,

  				   int flags, pol_lookup_t lookup)

  {

  	struct rt6_info *rt;

  	rt = pol_lookup_func(lookup,
  			net, net->ipv6.fib6_main_tbl, fl6, skb, flags);

  	if (rt->dst.error == -EAGAIN) {

  		ip6_rt_put_flags(rt, flags);

  		rt = net->ipv6.ip6_null_entry;

  		if (!(flags & RT6_LOOKUP_F_DST_NOREF))

  			dst_hold(&rt->dst);

  	}
  
  	return &rt->dst;

  }

  /* called with rcu lock held; no reference taken on fib6_info */

  int fib6_lookup(struct net *net, int oif, struct flowi6 *fl6,
  		struct fib6_result *res, int flags)

  {

  	return fib6_table_lookup(net, net->ipv6.fib6_main_tbl, oif, fl6,
  				 res, flags);

  }

  static void __net_init fib6_tables_init(struct net *net)

  {

  	fib6_link_table(net, net->ipv6.fib6_main_tbl);

  }
  
  #endif

  unsigned int fib6_tables_seq_read(struct net *net)
  {
  	unsigned int h, fib_seq = 0;
  
  	rcu_read_lock();
  	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
  		struct hlist_head *head = &net->ipv6.fib_table_hash[h];
  		struct fib6_table *tb;

  		hlist_for_each_entry_rcu(tb, head, tb6_hlist)

  			fib_seq += tb->fib_seq;

  	}
  	rcu_read_unlock();
  
  	return fib_seq;
  }

  static int call_fib6_entry_notifier(struct notifier_block *nb,

  				    enum fib_event_type event_type,

  				    struct fib6_info *rt,
  				    struct netlink_ext_ack *extack)

  {
  	struct fib6_entry_notifier_info info = {

  		.info.extack = extack,

  		.rt = rt,
  	};

  	return call_fib6_notifier(nb, event_type, &info.info);

  }

  static int call_fib6_multipath_entry_notifier(struct notifier_block *nb,
  					      enum fib_event_type event_type,
  					      struct fib6_info *rt,
  					      unsigned int nsiblings,
  					      struct netlink_ext_ack *extack)
  {
  	struct fib6_entry_notifier_info info = {
  		.info.extack = extack,
  		.rt = rt,
  		.nsiblings = nsiblings,
  	};
  
  	return call_fib6_notifier(nb, event_type, &info.info);
  }

  int call_fib6_entry_notifiers(struct net *net,
  			      enum fib_event_type event_type,
  			      struct fib6_info *rt,
  			      struct netlink_ext_ack *extack)

  {
  	struct fib6_entry_notifier_info info = {

  		.info.extack = extack,

  		.rt = rt,
  	};

  	rt->fib6_table->fib_seq++;

  	return call_fib6_notifiers(net, event_type, &info.info);
  }

  int call_fib6_multipath_entry_notifiers(struct net *net,
  					enum fib_event_type event_type,
  					struct fib6_info *rt,
  					unsigned int nsiblings,
  					struct netlink_ext_ack *extack)
  {
  	struct fib6_entry_notifier_info info = {
  		.info.extack = extack,
  		.rt = rt,
  		.nsiblings = nsiblings,

  	};
  
  	rt->fib6_table->fib_seq++;
  	return call_fib6_notifiers(net, event_type, &info.info);
  }

  int call_fib6_entry_notifiers_replace(struct net *net, struct fib6_info *rt)
  {
  	struct fib6_entry_notifier_info info = {
  		.rt = rt,
  		.nsiblings = rt->fib6_nsiblings,
  	};
  
  	rt->fib6_table->fib_seq++;

  	return call_fib6_notifiers(net, FIB_EVENT_ENTRY_REPLACE, &info.info);

  }

  struct fib6_dump_arg {
  	struct net *net;
  	struct notifier_block *nb;

  	struct netlink_ext_ack *extack;

  };

  static int fib6_rt_dump(struct fib6_info *rt, struct fib6_dump_arg *arg)

  {

  	enum fib_event_type fib_event = FIB_EVENT_ENTRY_REPLACE;

  	int err;
  
  	if (!rt || rt == arg->net->ipv6.fib6_null_entry)
  		return 0;
  
  	if (rt->fib6_nsiblings)
  		err = call_fib6_multipath_entry_notifier(arg->nb, fib_event,
  							 rt,
  							 rt->fib6_nsiblings,
  							 arg->extack);
  	else
  		err = call_fib6_entry_notifier(arg->nb, fib_event, rt,
  					       arg->extack);
  
  	return err;
  }

  static int fib6_node_dump(struct fib6_walker *w)
  {

  	int err;

  	err = fib6_rt_dump(w->leaf, w->args);

  	w->leaf = NULL;

  	return err;

  }

  static int fib6_table_dump(struct net *net, struct fib6_table *tb,
  			   struct fib6_walker *w)

  {

  	int err;

  	w->root = &tb->tb6_root;

  	spin_lock_bh(&tb->tb6_lock);

  	err = fib6_walk(net, w);

  	spin_unlock_bh(&tb->tb6_lock);

  	return err;

  }
  
  /* Called with rcu_read_lock() */

  int fib6_tables_dump(struct net *net, struct notifier_block *nb,
  		     struct netlink_ext_ack *extack)

  {
  	struct fib6_dump_arg arg;
  	struct fib6_walker *w;
  	unsigned int h;

  	int err = 0;

  
  	w = kzalloc(sizeof(*w), GFP_ATOMIC);
  	if (!w)
  		return -ENOMEM;
  
  	w->func = fib6_node_dump;
  	arg.net = net;
  	arg.nb = nb;

  	arg.extack = extack;

  	w->args = &arg;
  
  	for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
  		struct hlist_head *head = &net->ipv6.fib_table_hash[h];
  		struct fib6_table *tb;

  		hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
  			err = fib6_table_dump(net, tb, w);
  			if (err < 0)
  				goto out;
  		}

  	}

  out:

  	kfree(w);

  	return err;

  }

  static int fib6_dump_node(struct fib6_walker *w)

  {
  	int res;

  	struct fib6_info *rt;

  	for_each_fib6_walker_rt(w) {

  		res = rt6_dump_route(rt, w->args, w->skip_in_node);

  		if (res >= 0) {

  			/* Frame is full, suspend walking */
  			w->leaf = rt;

  
  			/* We'll restart from this node, so if some routes were
  			 * already dumped, skip them next time.
  			 */
  			w->skip_in_node += res;

  			return 1;
  		}

  		w->skip_in_node = 0;

  
  		/* Multipath routes are dumped in one route with the
  		 * RTA_MULTIPATH attribute. Jump 'rt' to point to the
  		 * last sibling of this route (no need to dump the
  		 * sibling routes again)
  		 */

  		if (rt->fib6_nsiblings)
  			rt = list_last_entry(&rt->fib6_siblings,

  					     struct fib6_info,

  					     fib6_siblings);

  	}
  	w->leaf = NULL;
  	return 0;
  }
  
  static void fib6_dump_end(struct netlink_callback *cb)
  {

  	struct net *net = sock_net(cb->skb->sk);

  	struct fib6_walker *w = (void *)cb->args[2];

  
  	if (w) {

  		if (cb->args[4]) {
  			cb->args[4] = 0;

  			fib6_walker_unlink(net, w);

  		}

  		cb->args[2] = 0;
  		kfree(w);
  	}

  	cb->done = (void *)cb->args[3];

  	cb->args[1] = 3;
  }
  
  static int fib6_dump_done(struct netlink_callback *cb)
  {
  	fib6_dump_end(cb);
  	return cb->done ? cb->done(cb) : 0;
  }
  
  static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
  			   struct netlink_callback *cb)
  {

  	struct net *net = sock_net(skb->sk);

  	struct fib6_walker *w;

  	int res;
  
  	w = (void *)cb->args[2];
  	w->root = &table->tb6_root;
  
  	if (cb->args[4] == 0) {

  		w->count = 0;
  		w->skip = 0;

  		w->skip_in_node = 0;

  		spin_lock_bh(&table->tb6_lock);

  		res = fib6_walk(net, w);

  		spin_unlock_bh(&table->tb6_lock);

  		if (res > 0) {

  			cb->args[4] = 1;

  			cb->args[5] = w->root->fn_sernum;
  		}

  	} else {

  		if (cb->args[5] != w->root->fn_sernum) {
  			/* Begin at the root if the tree changed */
  			cb->args[5] = w->root->fn_sernum;
  			w->state = FWS_INIT;
  			w->node = w->root;
  			w->skip = w->count;

  			w->skip_in_node = 0;

  		} else
  			w->skip = 0;

  		spin_lock_bh(&table->tb6_lock);

  		res = fib6_walk_continue(w);

  		spin_unlock_bh(&table->tb6_lock);

  		if (res <= 0) {

  			fib6_walker_unlink(net, w);

  			cb->args[4] = 0;

  		}

  	}

  	return res;
  }

  static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)

  {

  	struct rt6_rtnl_dump_arg arg = { .filter.dump_exceptions = true,
  					 .filter.dump_routes = true };

  	const struct nlmsghdr *nlh = cb->nlh;

  	struct net *net = sock_net(skb->sk);

  	unsigned int h, s_h;
  	unsigned int e = 0, s_e;

  	struct fib6_walker *w;

  	struct fib6_table *tb;

  	struct hlist_head *head;

  	int res = 0;

  	if (cb->strict_check) {

  		int err;

  		err = ip_valid_fib_dump_req(net, nlh, &arg.filter, cb);

  		if (err < 0)
  			return err;

  	} else if (nlmsg_len(nlh) >= sizeof(struct rtmsg)) {
  		struct rtmsg *rtm = nlmsg_data(nlh);

  		if (rtm->rtm_flags & RTM_F_PREFIX)
  			arg.filter.flags = RTM_F_PREFIX;

  	}

  
  	w = (void *)cb->args[2];

  	if (!w) {

  		/* New dump:
  		 *
  		 * 1. hook callback destructor.
  		 */
  		cb->args[3] = (long)cb->done;
  		cb->done = fib6_dump_done;
  
  		/*
  		 * 2. allocate and initialize walker.
  		 */
  		w = kzalloc(sizeof(*w), GFP_ATOMIC);

  		if (!w)

  			return -ENOMEM;
  		w->func = fib6_dump_node;
  		cb->args[2] = (long)w;
  	}
  
  	arg.skb = skb;
  	arg.cb = cb;

  	arg.net = net;

  	w->args = &arg;

  	if (arg.filter.table_id) {
  		tb = fib6_get_table(net, arg.filter.table_id);
  		if (!tb) {

  			if (rtnl_msg_family(cb->nlh) != PF_INET6)

  				goto out;

  			NL_SET_ERR_MSG_MOD(cb->extack, "FIB table does not exist");
  			return -ENOENT;
  		}

  		if (!cb->args[0]) {
  			res = fib6_dump_table(tb, skb, cb);
  			if (!res)
  				cb->args[0] = 1;
  		}

  		goto out;
  	}
  
  	s_h = cb->args[0];
  	s_e = cb->args[1];

  	rcu_read_lock();

  	for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {

  		e = 0;

  		head = &net->ipv6.fib_table_hash[h];

  		hlist_for_each_entry_rcu(tb, head, tb6_hlist) {

  			if (e < s_e)
  				goto next;
  			res = fib6_dump_table(tb, skb, cb);
  			if (res != 0)

  				goto out_unlock;

  next:
  			e++;
  		}
  	}

  out_unlock:

  	rcu_read_unlock();

  	cb->args[1] = e;
  	cb->args[0] = h;

  out:

  	res = res < 0 ? res : skb->len;
  	if (res <= 0)
  		fib6_dump_end(cb);
  	return res;
  }

  void fib6_metric_set(struct fib6_info *f6i, int metric, u32 val)

  {
  	if (!f6i)
  		return;
  
  	if (f6i->fib6_metrics == &dst_default_metrics) {
  		struct dst_metrics *p = kzalloc(sizeof(*p), GFP_ATOMIC);
  
  		if (!p)
  			return;
  
  		refcount_set(&p->refcnt, 1);
  		f6i->fib6_metrics = p;
  	}
  
  	f6i->fib6_metrics->metrics[metric - 1] = val;
  }

  /*
   *	Routing Table
   *
   *	return the appropriate node for a routing tree "add" operation
   *	by either creating and inserting or by returning an existing
   *	node.
   */

  static struct fib6_node *fib6_add_1(struct net *net,
  				    struct fib6_table *table,

  				    struct fib6_node *root,
  				    struct in6_addr *addr, int plen,
  				    int offset, int allow_create,
  				    int replace_required,
  				    struct netlink_ext_ack *extack)

  {
  	struct fib6_node *fn, *in, *ln;
  	struct fib6_node *pn = NULL;
  	struct rt6key *key;
  	int	bit;

  	__be32	dir = 0;

  
  	RT6_TRACE("fib6_add_1
  ");
  
  	/* insert node in tree */
  
  	fn = root;
  
  	do {

  		struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,

  					    lockdep_is_held(&table->tb6_lock));
  		key = (struct rt6key *)((u8 *)leaf + offset);

  
  		/*
  		 *	Prefix match
  		 */
  		if (plen < fn->fn_bit ||

  		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {

  			if (!allow_create) {
  				if (replace_required) {

  					NL_SET_ERR_MSG(extack,
  						       "Can not replace route - no match found");

  					pr_warn("Can't replace route, no match found
  ");

  					return ERR_PTR(-ENOENT);
  				}

  				pr_warn("NLM_F_CREATE should be set when creating new route
  ");

  			}

  			goto insert_above;

  		}

  		/*
  		 *	Exact match ?
  		 */

  		if (plen == fn->fn_bit) {
  			/* clean up an intermediate node */

  			if (!(fn->fn_flags & RTN_RTINFO)) {

  				RCU_INIT_POINTER(fn->leaf, NULL);

  				fib6_info_release(leaf);

  			/* remove null_entry in the root node */
  			} else if (fn->fn_flags & RTN_TL_ROOT &&
  				   rcu_access_pointer(fn->leaf) ==

  				   net->ipv6.fib6_null_entry) {

  				RCU_INIT_POINTER(fn->leaf, NULL);

  			}

  			return fn;
  		}
  
  		/*
  		 *	We have more bits to go
  		 */

  		/* Try to walk down on tree. */

  		dir = addr_bit_set(addr, fn->fn_bit);
  		pn = fn;

  		fn = dir ?
  		     rcu_dereference_protected(fn->right,
  					lockdep_is_held(&table->tb6_lock)) :
  		     rcu_dereference_protected(fn->left,
  					lockdep_is_held(&table->tb6_lock));

  	} while (fn);

  	if (!allow_create) {

  		/* We should not create new node because
  		 * NLM_F_REPLACE was specified without NLM_F_CREATE
  		 * I assume it is safe to require NLM_F_CREATE when
  		 * REPLACE flag is used! Later we may want to remove the
  		 * check for replace_required, because according
  		 * to netlink specification, NLM_F_CREATE
  		 * MUST be specified if new route is created.
  		 * That would keep IPv6 consistent with IPv4
  		 */

  		if (replace_required) {

  			NL_SET_ERR_MSG(extack,
  				       "Can not replace route - no match found");

  			pr_warn("Can't replace route, no match found
  ");

  			return ERR_PTR(-ENOENT);
  		}

  		pr_warn("NLM_F_CREATE should be set when creating new route
  ");

  	}

  	/*
  	 *	We walked to the bottom of tree.
  	 *	Create new leaf node without children.
  	 */

  	ln = node_alloc(net);

  	if (!ln)

  		return ERR_PTR(-ENOMEM);

  	ln->fn_bit = plen;

  	RCU_INIT_POINTER(ln->parent, pn);

  
  	if (dir)

  		rcu_assign_pointer(pn->right, ln);

  	else

  		rcu_assign_pointer(pn->left, ln);

  
  	return ln;
  
  
  insert_above:
  	/*

  	 * split since we don't have a common prefix anymore or

  	 * we have a less significant route.
  	 * we've to insert an intermediate node on the list
  	 * this new node will point to the one we need to create
  	 * and the current
  	 */

  	pn = rcu_dereference_protected(fn->parent,
  				       lockdep_is_held(&table->tb6_lock));

  
  	/* find 1st bit in difference between the 2 addrs.

  	   See comment in __ipv6_addr_diff: bit may be an invalid value,

  	   but if it is >= plen, the value is ignored in any case.
  	 */

  	bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));

  	/*
  	 *		(intermediate)[in]

  	 *	          /	   \
  	 *	(new leaf node)[ln] (old node)[fn]
  	 */
  	if (plen > bit) {

  		in = node_alloc(net);
  		ln = node_alloc(net);

  		if (!in || !ln) {

  			if (in)

  				node_free_immediate(net, in);

  			if (ln)

  				node_free_immediate(net, ln);

  			return ERR_PTR(-ENOMEM);

  		}

  		/*
  		 * new intermediate node.

  		 * RTN_RTINFO will
  		 * be off since that an address that chooses one of
  		 * the branches would not match less specific routes
  		 * in the other branch
  		 */
  
  		in->fn_bit = bit;

  		RCU_INIT_POINTER(in->parent, pn);

  		in->leaf = fn->leaf;

  		fib6_info_hold(rcu_dereference_protected(in->leaf,
  				lockdep_is_held(&table->tb6_lock)));

  		/* update parent pointer */
  		if (dir)

  			rcu_assign_pointer(pn->right, in);

  		else

  			rcu_assign_pointer(pn->left, in);

  
  		ln->fn_bit = plen;

  		RCU_INIT_POINTER(ln->parent, in);
  		rcu_assign_pointer(fn->parent, in);

  		if (addr_bit_set(addr, bit)) {

  			rcu_assign_pointer(in->right, ln);
  			rcu_assign_pointer(in->left, fn);

  		} else {

  			rcu_assign_pointer(in->left, ln);
  			rcu_assign_pointer(in->right, fn);

  		}
  	} else { /* plen <= bit */

  		/*

  		 *		(new leaf node)[ln]
  		 *	          /	   \
  		 *	     (old node)[fn] NULL
  		 */

  		ln = node_alloc(net);

  		if (!ln)

  			return ERR_PTR(-ENOMEM);

  
  		ln->fn_bit = plen;

  		RCU_INIT_POINTER(ln->parent, pn);

  
  		if (addr_bit_set(&key->addr, plen))

  			RCU_INIT_POINTER(ln->right, fn);

  		else

  			RCU_INIT_POINTER(ln->left, fn);
  
  		rcu_assign_pointer(fn->parent, ln);

  		if (dir)
  			rcu_assign_pointer(pn->right, ln);
  		else
  			rcu_assign_pointer(pn->left, ln);

  	}
  	return ln;
  }

  static void __fib6_drop_pcpu_from(struct fib6_nh *fib6_nh,
  				  const struct fib6_info *match,
  				  const struct fib6_table *table)

  {

  	int cpu;

  	if (!fib6_nh->rt6i_pcpu)
  		return;

  	/* release the reference to this fib entry from
  	 * all of its cached pcpu routes
  	 */
  	for_each_possible_cpu(cpu) {
  		struct rt6_info **ppcpu_rt;
  		struct rt6_info *pcpu_rt;

  		ppcpu_rt = per_cpu_ptr(fib6_nh->rt6i_pcpu, cpu);

  		pcpu_rt = *ppcpu_rt;

  
  		/* only dropping the 'from' reference if the cached route
  		 * is using 'match'. The cached pcpu_rt->from only changes
  		 * from a fib6_info to NULL (ip6_dst_destroy); it can never
  		 * change from one fib6_info reference to another
  		 */
  		if (pcpu_rt && rcu_access_pointer(pcpu_rt->from) == match) {

  			struct fib6_info *from;

  			from = xchg((__force struct fib6_info **)&pcpu_rt->from, NULL);

  			fib6_info_release(from);

  		}

  	}

  }

  struct fib6_nh_pcpu_arg {
  	struct fib6_info	*from;
  	const struct fib6_table *table;
  };
  
  static int fib6_nh_drop_pcpu_from(struct fib6_nh *nh, void *_arg)
  {
  	struct fib6_nh_pcpu_arg *arg = _arg;
  
  	__fib6_drop_pcpu_from(nh, arg->from, arg->table);
  	return 0;
  }

  static void fib6_drop_pcpu_from(struct fib6_info *f6i,
  				const struct fib6_table *table)
  {

  	/* Make sure rt6_make_pcpu_route() wont add other percpu routes
  	 * while we are cleaning them here.
  	 */
  	f6i->fib6_destroying = 1;
  	mb(); /* paired with the cmpxchg() in rt6_make_pcpu_route() */

  	if (f6i->nh) {
  		struct fib6_nh_pcpu_arg arg = {
  			.from = f6i,
  			.table = table
  		};
  
  		nexthop_for_each_fib6_nh(f6i->nh, fib6_nh_drop_pcpu_from,
  					 &arg);
  	} else {
  		struct fib6_nh *fib6_nh;
  
  		fib6_nh = f6i->fib6_nh;
  		__fib6_drop_pcpu_from(fib6_nh, f6i, table);
  	}

  }

  static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,

  			  struct net *net)
  {

  	struct fib6_table *table = rt->fib6_table;

  	/* Flush all cached dst in exception table */
  	rt6_flush_exceptions(rt);

  	fib6_drop_pcpu_from(rt, table);

  	if (rt->nh && !list_empty(&rt->nh_list))
  		list_del_init(&rt->nh_list);

  	if (refcount_read(&rt->fib6_ref) != 1) {

  		/* This route is used as dummy address holder in some split
  		 * nodes. It is not leaked, but it still holds other resources,
  		 * which must be released in time. So, scan ascendant nodes
  		 * and replace dummy references to this route with references
  		 * to still alive ones.
  		 */
  		while (fn) {

  			struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,

  					    lockdep_is_held(&table->tb6_lock));

  			struct fib6_info *new_leaf;

  			if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {
  				new_leaf = fib6_find_prefix(net, table, fn);

  				fib6_info_hold(new_leaf);

  				rcu_assign_pointer(fn->leaf, new_leaf);

  				fib6_info_release(rt);

  			}

  			fn = rcu_dereference_protected(fn->parent,
  				    lockdep_is_held(&table->tb6_lock));

  		}

  	}
  }

  /*
   *	Insert routing information in a node.
   */

  static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,

  			    struct nl_info *info,

  			    struct netlink_ext_ack *extack)

  {

  	struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,

  				    lockdep_is_held(&rt->fib6_table->tb6_lock));

  	struct fib6_info *iter = NULL;

  	struct fib6_info __rcu **ins;

  	struct fib6_info __rcu **fallback_ins = NULL;

  	int replace = (info->nlh &&
  		       (info->nlh->nlmsg_flags & NLM_F_REPLACE));
  	int add = (!info->nlh ||
  		   (info->nlh->nlmsg_flags & NLM_F_CREATE));

  	int found = 0;

  	bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);

  	bool notify_sibling_rt = false;

  	u16 nlflags = NLM_F_EXCL;

  	int err;

  	if (info->nlh && (info->nlh->nlmsg_flags & NLM_F_APPEND))

  		nlflags |= NLM_F_APPEND;

  	ins = &fn->leaf;

  	for (iter = leaf; iter;

  	     iter = rcu_dereference_protected(iter->fib6_next,

  				lockdep_is_held(&rt->fib6_table->tb6_lock))) {

  		/*
  		 *	Search for duplicates
  		 */

  		if (iter->fib6_metric == rt->fib6_metric) {

  			/*
  			 *	Same priority level
  			 */

  			if (info->nlh &&
  			    (info->nlh->nlmsg_flags & NLM_F_EXCL))

  				return -EEXIST;

  
  			nlflags &= ~NLM_F_EXCL;

  			if (replace) {

  				if (rt_can_ecmp == rt6_qualify_for_ecmp(iter)) {
  					found++;
  					break;
  				}

  				fallback_ins = fallback_ins ?: ins;

  				goto next_iter;

  			}

  			if (rt6_duplicate_nexthop(iter, rt)) {

  				if (rt->fib6_nsiblings)
  					rt->fib6_nsiblings = 0;
  				if (!(iter->fib6_flags & RTF_EXPIRES))

  					return -EEXIST;

  				if (!(rt->fib6_flags & RTF_EXPIRES))

  					fib6_clean_expires(iter);

  				else

  					fib6_set_expires(iter, rt->expires);

  
  				if (rt->fib6_pmtu)
  					fib6_metric_set(iter, RTAX_MTU,
  							rt->fib6_pmtu);

  				return -EEXIST;
  			}

  			/* If we have the same destination and the same metric,
  			 * but not the same gateway, then the route we try to
  			 * add is sibling to this route, increment our counter
  			 * of siblings, and later we will add our route to the
  			 * list.
  			 * Only static routes (which don't have flag
  			 * RTF_EXPIRES) are used for ECMPv6.
  			 *
  			 * To avoid long list, we only had siblings if the
  			 * route have a gateway.
  			 */
  			if (rt_can_ecmp &&
  			    rt6_qualify_for_ecmp(iter))
  				rt->fib6_nsiblings++;

  		}

  		if (iter->fib6_metric > rt->fib6_metric)

  			break;

  next_iter:

  		ins = &iter->fib6_next;

  	}

  	if (fallback_ins && !found) {

  		/* No matching route with same ecmp-able-ness found, replace
  		 * first matching route
  		 */

  		ins = fallback_ins;
  		iter = rcu_dereference_protected(*ins,
  				    lockdep_is_held(&rt->fib6_table->tb6_lock));
  		found++;
  	}

  	/* Reset round-robin state, if necessary */
  	if (ins == &fn->leaf)
  		fn->rr_ptr = NULL;

  	/* Link this route to others same route. */

  	if (rt->fib6_nsiblings) {
  		unsigned int fib6_nsiblings;

  		struct fib6_info *sibling, *temp_sibling;

  		/* Find the first route that have the same metric */
  		sibling = leaf;

  		notify_sibling_rt = true;

  		while (sibling) {
  			if (sibling->fib6_metric == rt->fib6_metric &&
  			    rt6_qualify_for_ecmp(sibling)) {
  				list_add_tail(&rt->fib6_siblings,
  					      &sibling->fib6_siblings);
  				break;
  			}
  			sibling = rcu_dereference_protected(sibling->fib6_next,
  				    lockdep_is_held(&rt->fib6_table->tb6_lock));

  			notify_sibling_rt = false;

  		}
  		/* For each sibling in the list, increment the counter of
  		 * siblings. BUG() if counters does not match, list of siblings
  		 * is broken!
  		 */

  		fib6_nsiblings = 0;

  		list_for_each_entry_safe(sibling, temp_sibling,

  					 &rt->fib6_siblings, fib6_siblings) {

  			sibling->fib6_nsiblings++;

  			BUG_ON(sibling->fib6_nsiblings != rt->fib6_nsiblings);
  			fib6_nsiblings++;

  		}

  		BUG_ON(fib6_nsiblings != rt->fib6_nsiblings);
  		rt6_multipath_rebalance(temp_sibling);

  	}

  	/*
  	 *	insert node
  	 */

  	if (!replace) {
  		if (!add)

  			pr_warn("NLM_F_CREATE should be set when creating new route
  ");

  
  add:

  		nlflags |= NLM_F_CREATE;

  		/* The route should only be notified if it is the first
  		 * route in the node or if it is added as a sibling
  		 * route to the first route in the node.
  		 */
  		if (!info->skip_notify_kernel &&
  		    (notify_sibling_rt || ins == &fn->leaf)) {

  			enum fib_event_type fib_event;
  
  			if (notify_sibling_rt)
  				fib_event = FIB_EVENT_ENTRY_APPEND;
  			else

  				fib_event = FIB_EVENT_ENTRY_REPLACE;

  			err = call_fib6_entry_notifiers(info->nl_net,

  							fib_event, rt,
  							extack);

  			if (err) {
  				struct fib6_info *sibling, *next_sibling;
  
  				/* If the route has siblings, then it first
  				 * needs to be unlinked from them.
  				 */
  				if (!rt->fib6_nsiblings)
  					return err;
  
  				list_for_each_entry_safe(sibling, next_sibling,
  							 &rt->fib6_siblings,
  							 fib6_siblings)
  					sibling->fib6_nsiblings--;
  				rt->fib6_nsiblings = 0;
  				list_del_init(&rt->fib6_siblings);
  				rt6_multipath_rebalance(next_sibling);

  				return err;

  			}

  		}

  		rcu_assign_pointer(rt->fib6_next, iter);

  		fib6_info_hold(rt);

  		rcu_assign_pointer(rt->fib6_node, fn);

  		rcu_assign_pointer(*ins, rt);

  		if (!info->skip_notify)
  			inet6_rt_notify(RTM_NEWROUTE, rt, info, nlflags);

  		info->nl_net->ipv6.rt6_stats->fib_rt_entries++;

  		if (!(fn->fn_flags & RTN_RTINFO)) {

  			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
  			fn->fn_flags |= RTN_RTINFO;
  		}

  	} else {

  		int nsiblings;

  		if (!found) {
  			if (add)
  				goto add;

  			pr_warn("NLM_F_REPLACE set, but no existing node found!
  ");

  			return -ENOENT;
  		}

  		if (!info->skip_notify_kernel && ins == &fn->leaf) {

  			err = call_fib6_entry_notifiers(info->nl_net,
  							FIB_EVENT_ENTRY_REPLACE,
  							rt, extack);
  			if (err)
  				return err;
  		}

  		fib6_info_hold(rt);

  		rcu_assign_pointer(rt->fib6_node, fn);

  		rt->fib6_next = iter->fib6_next;

  		rcu_assign_pointer(*ins, rt);

  		if (!info->skip_notify)
  			inet6_rt_notify(RTM_NEWROUTE, rt, info, NLM_F_REPLACE);

  		if (!(fn->fn_flags & RTN_RTINFO)) {

  			info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
  			fn->fn_flags |= RTN_RTINFO;
  		}

  		nsiblings = iter->fib6_nsiblings;
  		iter->fib6_node = NULL;
  		fib6_purge_rt(iter, fn, info->nl_net);
  		if (rcu_access_pointer(fn->rr_ptr) == iter)
  			fn->rr_ptr = NULL;
  		fib6_info_release(iter);

  		if (nsiblings) {

  			/* Replacing an ECMP route, remove all siblings */

  			ins = &rt->fib6_next;
  			iter = rcu_dereference_protected(*ins,
  				    lockdep_is_held(&rt->fib6_table->tb6_lock));
  			while (iter) {
  				if (iter->fib6_metric > rt->fib6_metric)
  					break;
  				if (rt6_qualify_for_ecmp(iter)) {
  					*ins = iter->fib6_next;
  					iter->fib6_node = NULL;
  					fib6_purge_rt(iter, fn, info->nl_net);
  					if (rcu_access_pointer(fn->rr_ptr) == iter)
  						fn->rr_ptr = NULL;
  					fib6_info_release(iter);
  					nsiblings--;
  					info->nl_net->ipv6.rt6_stats->fib_rt_entries--;
  				} else {
  					ins = &iter->fib6_next;
  				}
  				iter = rcu_dereference_protected(*ins,
  					lockdep_is_held(&rt->fib6_table->tb6_lock));

  			}

  			WARN_ON(nsiblings != 0);

  		}

  	}
  
  	return 0;
  }

  static void fib6_start_gc(struct net *net, struct fib6_info *rt)

  {

  	if (!timer_pending(&net->ipv6.ip6_fib_timer) &&

  	    (rt->fib6_flags & RTF_EXPIRES))

  		mod_timer(&net->ipv6.ip6_fib_timer,

  			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);

  }

  void fib6_force_start_gc(struct net *net)

  {

  	if (!timer_pending(&net->ipv6.ip6_fib_timer))
  		mod_timer(&net->ipv6.ip6_fib_timer,

  			  jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);

  }

  static void __fib6_update_sernum_upto_root(struct fib6_info *rt,

  					   int sernum)

  {

  	struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,
  				lockdep_is_held(&rt->fib6_table->tb6_lock));

  
  	/* paired with smp_rmb() in rt6_get_cookie_safe() */
  	smp_wmb();
  	while (fn) {
  		fn->fn_sernum = sernum;

  		fn = rcu_dereference_protected(fn->parent,

  				lockdep_is_held(&rt->fib6_table->tb6_lock));

  	}
  }

  void fib6_update_sernum_upto_root(struct net *net, struct fib6_info *rt)

  {
  	__fib6_update_sernum_upto_root(rt, fib6_new_sernum(net));
  }

  /* allow ipv4 to update sernum via ipv6_stub */
  void fib6_update_sernum_stub(struct net *net, struct fib6_info *f6i)
  {
  	spin_lock_bh(&f6i->fib6_table->tb6_lock);
  	fib6_update_sernum_upto_root(net, f6i);
  	spin_unlock_bh(&f6i->fib6_table->tb6_lock);
  }

  /*
   *	Add routing information to the routing tree.
   *	<destination addr>/<source addr>
   *	with source addr info in sub-trees

   *	Need to own table->tb6_lock

   */

  int fib6_add(struct fib6_node *root, struct fib6_info *rt,

  	     struct nl_info *info, struct netlink_ext_ack *extack)

  {

  	struct fib6_table *table = rt->fib6_table;

  	struct fib6_node *fn, *pn = NULL;

  	int err = -ENOMEM;

  	int allow_create = 1;
  	int replace_required = 0;

  	int sernum = fib6_new_sernum(info->nl_net);

  
  	if (info->nlh) {
  		if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))