/*
   *	Linux INET6 implementation
   *	FIB front-end.
   *
   *	Authors:

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

   *

   *	This program is free software; you can redistribute it and/or
   *      modify it under the terms of the GNU General Public License
   *      as published by the Free Software Foundation; either version
   *      2 of the License, or (at your option) any later version.
   */
  
  /*	Changes:
   *
   *	YOSHIFUJI Hideaki @USAGI
   *		reworked default router selection.
   *		- respect outgoing interface
   *		- select from (probably) reachable routers (i.e.
   *		routers in REACHABLE, STALE, DELAY or PROBE states).
   *		- always select the same router if it is (probably)
   *		reachable.  otherwise, round-robin the list.

   *	Ville Nuorvala
   *		Fixed routing subtrees.

   */

  #include <linux/capability.h>

  #include <linux/errno.h>

  #include <linux/export.h>

  #include <linux/types.h>
  #include <linux/times.h>
  #include <linux/socket.h>
  #include <linux/sockios.h>
  #include <linux/net.h>
  #include <linux/route.h>
  #include <linux/netdevice.h>
  #include <linux/in6.h>

  #include <linux/mroute6.h>

  #include <linux/init.h>

  #include <linux/if_arp.h>

  #include <linux/proc_fs.h>
  #include <linux/seq_file.h>

  #include <linux/nsproxy.h>

  #include <linux/slab.h>

  #include <net/net_namespace.h>

  #include <net/snmp.h>
  #include <net/ipv6.h>
  #include <net/ip6_fib.h>
  #include <net/ip6_route.h>
  #include <net/ndisc.h>
  #include <net/addrconf.h>
  #include <net/tcp.h>
  #include <linux/rtnetlink.h>
  #include <net/dst.h>
  #include <net/xfrm.h>

  #include <net/netevent.h>

  #include <net/netlink.h>

  
  #include <asm/uaccess.h>
  
  #ifdef CONFIG_SYSCTL
  #include <linux/sysctl.h>
  #endif

  static struct rt6_info *ip6_rt_copy(const struct rt6_info *ort,
  				    const struct in6_addr *dest);

  static struct dst_entry	*ip6_dst_check(struct dst_entry *dst, u32 cookie);

  static unsigned int	 ip6_default_advmss(const struct dst_entry *dst);

  static unsigned int	 ip6_mtu(const struct dst_entry *dst);

  static struct dst_entry *ip6_negative_advice(struct dst_entry *);
  static void		ip6_dst_destroy(struct dst_entry *);
  static void		ip6_dst_ifdown(struct dst_entry *,
  				       struct net_device *dev, int how);

  static int		 ip6_dst_gc(struct dst_ops *ops);

  
  static int		ip6_pkt_discard(struct sk_buff *skb);
  static int		ip6_pkt_discard_out(struct sk_buff *skb);
  static void		ip6_link_failure(struct sk_buff *skb);
  static void		ip6_rt_update_pmtu(struct dst_entry *dst, u32 mtu);

  #ifdef CONFIG_IPV6_ROUTE_INFO

  static struct rt6_info *rt6_add_route_info(struct net *net,

  					   const struct in6_addr *prefix, int prefixlen,
  					   const struct in6_addr *gwaddr, int ifindex,

  					   unsigned pref);

  static struct rt6_info *rt6_get_route_info(struct net *net,

  					   const struct in6_addr *prefix, int prefixlen,
  					   const struct in6_addr *gwaddr, int ifindex);

  #endif

  static u32 *ipv6_cow_metrics(struct dst_entry *dst, unsigned long old)
  {
  	struct rt6_info *rt = (struct rt6_info *) dst;
  	struct inet_peer *peer;
  	u32 *p = NULL;

  	if (!(rt->dst.flags & DST_HOST))
  		return NULL;

  	if (!rt->rt6i_peer)
  		rt6_bind_peer(rt, 1);
  
  	peer = rt->rt6i_peer;
  	if (peer) {
  		u32 *old_p = __DST_METRICS_PTR(old);
  		unsigned long prev, new;
  
  		p = peer->metrics;
  		if (inet_metrics_new(peer))
  			memcpy(p, old_p, sizeof(u32) * RTAX_MAX);
  
  		new = (unsigned long) p;
  		prev = cmpxchg(&dst->_metrics, old, new);
  
  		if (prev != old) {
  			p = __DST_METRICS_PTR(prev);
  			if (prev & DST_METRICS_READ_ONLY)
  				p = NULL;
  		}
  	}
  	return p;
  }

  static struct neighbour *ip6_neigh_lookup(const struct dst_entry *dst, const void *daddr)
  {

  	struct neighbour *n = __ipv6_neigh_lookup(&nd_tbl, dst->dev, daddr);
  	if (n)
  		return n;
  	return neigh_create(&nd_tbl, daddr, dst->dev);
  }

  static int rt6_bind_neighbour(struct rt6_info *rt, struct net_device *dev)

  {

  	struct neighbour *n = __ipv6_neigh_lookup(&nd_tbl, dev, &rt->rt6i_gateway);
  	if (!n) {
  		n = neigh_create(&nd_tbl, &rt->rt6i_gateway, dev);
  		if (IS_ERR(n))
  			return PTR_ERR(n);
  	}

  	dst_set_neighbour(&rt->dst, n);
  
  	return 0;

  }

  static struct dst_ops ip6_dst_ops_template = {

  	.family			=	AF_INET6,

  	.protocol		=	cpu_to_be16(ETH_P_IPV6),

  	.gc			=	ip6_dst_gc,
  	.gc_thresh		=	1024,
  	.check			=	ip6_dst_check,

  	.default_advmss		=	ip6_default_advmss,

  	.mtu			=	ip6_mtu,

  	.cow_metrics		=	ipv6_cow_metrics,

  	.destroy		=	ip6_dst_destroy,
  	.ifdown			=	ip6_dst_ifdown,
  	.negative_advice	=	ip6_negative_advice,
  	.link_failure		=	ip6_link_failure,
  	.update_pmtu		=	ip6_rt_update_pmtu,

  	.local_out		=	__ip6_local_out,

  	.neigh_lookup		=	ip6_neigh_lookup,

  };

  static unsigned int ip6_blackhole_mtu(const struct dst_entry *dst)

  {

  	unsigned int mtu = dst_metric_raw(dst, RTAX_MTU);
  
  	return mtu ? : dst->dev->mtu;

  }

  static void ip6_rt_blackhole_update_pmtu(struct dst_entry *dst, u32 mtu)
  {
  }

  static u32 *ip6_rt_blackhole_cow_metrics(struct dst_entry *dst,
  					 unsigned long old)
  {
  	return NULL;
  }

  static struct dst_ops ip6_dst_blackhole_ops = {
  	.family			=	AF_INET6,

  	.protocol		=	cpu_to_be16(ETH_P_IPV6),

  	.destroy		=	ip6_dst_destroy,
  	.check			=	ip6_dst_check,

  	.mtu			=	ip6_blackhole_mtu,

  	.default_advmss		=	ip6_default_advmss,

  	.update_pmtu		=	ip6_rt_blackhole_update_pmtu,

  	.cow_metrics		=	ip6_rt_blackhole_cow_metrics,

  	.neigh_lookup		=	ip6_neigh_lookup,

  };

  static const u32 ip6_template_metrics[RTAX_MAX] = {
  	[RTAX_HOPLIMIT - 1] = 255,
  };

  static struct rt6_info ip6_null_entry_template = {

  	.dst = {
  		.__refcnt	= ATOMIC_INIT(1),
  		.__use		= 1,
  		.obsolete	= -1,
  		.error		= -ENETUNREACH,

  		.input		= ip6_pkt_discard,
  		.output		= ip6_pkt_discard_out,

  	},
  	.rt6i_flags	= (RTF_REJECT | RTF_NONEXTHOP),

  	.rt6i_protocol  = RTPROT_KERNEL,

  	.rt6i_metric	= ~(u32) 0,
  	.rt6i_ref	= ATOMIC_INIT(1),
  };

  #ifdef CONFIG_IPV6_MULTIPLE_TABLES

  static int ip6_pkt_prohibit(struct sk_buff *skb);
  static int ip6_pkt_prohibit_out(struct sk_buff *skb);

  static struct rt6_info ip6_prohibit_entry_template = {

  	.dst = {
  		.__refcnt	= ATOMIC_INIT(1),
  		.__use		= 1,
  		.obsolete	= -1,
  		.error		= -EACCES,

  		.input		= ip6_pkt_prohibit,
  		.output		= ip6_pkt_prohibit_out,

  	},
  	.rt6i_flags	= (RTF_REJECT | RTF_NONEXTHOP),

  	.rt6i_protocol  = RTPROT_KERNEL,

  	.rt6i_metric	= ~(u32) 0,
  	.rt6i_ref	= ATOMIC_INIT(1),
  };

  static struct rt6_info ip6_blk_hole_entry_template = {

  	.dst = {
  		.__refcnt	= ATOMIC_INIT(1),
  		.__use		= 1,
  		.obsolete	= -1,
  		.error		= -EINVAL,

  		.input		= dst_discard,
  		.output		= dst_discard,

  	},
  	.rt6i_flags	= (RTF_REJECT | RTF_NONEXTHOP),

  	.rt6i_protocol  = RTPROT_KERNEL,

  	.rt6i_metric	= ~(u32) 0,
  	.rt6i_ref	= ATOMIC_INIT(1),
  };
  
  #endif

  /* allocate dst with ip6_dst_ops */

  static inline struct rt6_info *ip6_dst_alloc(struct dst_ops *ops,

  					     struct net_device *dev,
  					     int flags)

  {

  	struct rt6_info *rt = dst_alloc(ops, dev, 0, 0, flags);

  	if (rt)

  		memset(&rt->rt6i_table, 0,

  		       sizeof(*rt) - sizeof(struct dst_entry));

  
  	return rt;

  }
  
  static void ip6_dst_destroy(struct dst_entry *dst)
  {
  	struct rt6_info *rt = (struct rt6_info *)dst;
  	struct inet6_dev *idev = rt->rt6i_idev;

  	struct inet_peer *peer = rt->rt6i_peer;

  	if (!(rt->dst.flags & DST_HOST))
  		dst_destroy_metrics_generic(dst);

  	if (idev) {

  		rt->rt6i_idev = NULL;
  		in6_dev_put(idev);

  	}

  	if (peer) {

  		rt->rt6i_peer = NULL;
  		inet_putpeer(peer);
  	}
  }

  static atomic_t __rt6_peer_genid = ATOMIC_INIT(0);
  
  static u32 rt6_peer_genid(void)
  {
  	return atomic_read(&__rt6_peer_genid);
  }

  void rt6_bind_peer(struct rt6_info *rt, int create)
  {
  	struct inet_peer *peer;

  	peer = inet_getpeer_v6(&rt->rt6i_dst.addr, create);
  	if (peer && cmpxchg(&rt->rt6i_peer, NULL, peer) != NULL)
  		inet_putpeer(peer);

  	else
  		rt->rt6i_peer_genid = rt6_peer_genid();

  }
  
  static void ip6_dst_ifdown(struct dst_entry *dst, struct net_device *dev,
  			   int how)
  {
  	struct rt6_info *rt = (struct rt6_info *)dst;
  	struct inet6_dev *idev = rt->rt6i_idev;

  	struct net_device *loopback_dev =

  		dev_net(dev)->loopback_dev;

  	if (dev != loopback_dev && idev && idev->dev == dev) {

  		struct inet6_dev *loopback_idev =
  			in6_dev_get(loopback_dev);

  		if (loopback_idev) {

  			rt->rt6i_idev = loopback_idev;
  			in6_dev_put(idev);
  		}
  	}
  }
  
  static __inline__ int rt6_check_expired(const struct rt6_info *rt)
  {

  	return (rt->rt6i_flags & RTF_EXPIRES) &&

  		time_after(jiffies, rt->dst.expires);

  }

  static inline int rt6_need_strict(const struct in6_addr *daddr)

  {

  	return ipv6_addr_type(daddr) &
  		(IPV6_ADDR_MULTICAST | IPV6_ADDR_LINKLOCAL | IPV6_ADDR_LOOPBACK);

  }

  /*

   *	Route lookup. Any table->tb6_lock is implied.

   */

  static inline struct rt6_info *rt6_device_match(struct net *net,
  						    struct rt6_info *rt,

  						    const struct in6_addr *saddr,

  						    int oif,

  						    int flags)

  {
  	struct rt6_info *local = NULL;
  	struct rt6_info *sprt;

  	if (!oif && ipv6_addr_any(saddr))
  		goto out;

  	for (sprt = rt; sprt; sprt = sprt->dst.rt6_next) {

  		struct net_device *dev = sprt->dst.dev;

  
  		if (oif) {

  			if (dev->ifindex == oif)
  				return sprt;
  			if (dev->flags & IFF_LOOPBACK) {

  				if (!sprt->rt6i_idev ||

  				    sprt->rt6i_idev->dev->ifindex != oif) {

  					if (flags & RT6_LOOKUP_F_IFACE && oif)

  						continue;

  					if (local && (!oif ||

  						      local->rt6i_idev->dev->ifindex == oif))
  						continue;
  				}
  				local = sprt;
  			}

  		} else {
  			if (ipv6_chk_addr(net, saddr, dev,
  					  flags & RT6_LOOKUP_F_IFACE))
  				return sprt;

  		}

  	}

  	if (oif) {

  		if (local)
  			return local;

  		if (flags & RT6_LOOKUP_F_IFACE)

  			return net->ipv6.ip6_null_entry;

  	}

  out:

  	return rt;
  }

  #ifdef CONFIG_IPV6_ROUTER_PREF
  static void rt6_probe(struct rt6_info *rt)
  {

  	struct neighbour *neigh;

  	/*
  	 * Okay, this does not seem to be appropriate
  	 * for now, however, we need to check if it
  	 * is really so; aka Router Reachability Probing.
  	 *
  	 * Router Reachability Probe MUST be rate-limited
  	 * to no more than one per minute.
  	 */

  	rcu_read_lock();

  	neigh = rt ? dst_get_neighbour_noref(&rt->dst) : NULL;

  	if (!neigh || (neigh->nud_state & NUD_VALID))

  		goto out;

  	read_lock_bh(&neigh->lock);
  	if (!(neigh->nud_state & NUD_VALID) &&

  	    time_after(jiffies, neigh->updated + rt->rt6i_idev->cnf.rtr_probe_interval)) {

  		struct in6_addr mcaddr;
  		struct in6_addr *target;
  
  		neigh->updated = jiffies;
  		read_unlock_bh(&neigh->lock);
  
  		target = (struct in6_addr *)&neigh->primary_key;
  		addrconf_addr_solict_mult(target, &mcaddr);

  		ndisc_send_ns(rt->dst.dev, NULL, target, &mcaddr, NULL);

  	} else {

  		read_unlock_bh(&neigh->lock);

  	}
  out:
  	rcu_read_unlock();

  }
  #else
  static inline void rt6_probe(struct rt6_info *rt)
  {

  }
  #endif

  /*

   * Default Router Selection (RFC 2461 6.3.6)

   */

  static inline int rt6_check_dev(struct rt6_info *rt, int oif)

  {

  	struct net_device *dev = rt->dst.dev;

  	if (!oif || dev->ifindex == oif)

  		return 2;

  	if ((dev->flags & IFF_LOOPBACK) &&
  	    rt->rt6i_idev && rt->rt6i_idev->dev->ifindex == oif)
  		return 1;
  	return 0;

  }

  static inline int rt6_check_neigh(struct rt6_info *rt)

  {

  	struct neighbour *neigh;

  	int m;

  
  	rcu_read_lock();

  	neigh = dst_get_neighbour_noref(&rt->dst);

  	if (rt->rt6i_flags & RTF_NONEXTHOP ||
  	    !(rt->rt6i_flags & RTF_GATEWAY))
  		m = 1;
  	else if (neigh) {

  		read_lock_bh(&neigh->lock);
  		if (neigh->nud_state & NUD_VALID)

  			m = 2;

  #ifdef CONFIG_IPV6_ROUTER_PREF
  		else if (neigh->nud_state & NUD_FAILED)
  			m = 0;
  #endif
  		else

  			m = 1;

  		read_unlock_bh(&neigh->lock);

  	} else
  		m = 0;

  	rcu_read_unlock();

  	return m;

  }

  static int rt6_score_route(struct rt6_info *rt, int oif,
  			   int strict)

  {

  	int m, n;

  	m = rt6_check_dev(rt, oif);

  	if (!m && (strict & RT6_LOOKUP_F_IFACE))

  		return -1;

  #ifdef CONFIG_IPV6_ROUTER_PREF
  	m |= IPV6_DECODE_PREF(IPV6_EXTRACT_PREF(rt->rt6i_flags)) << 2;
  #endif

  	n = rt6_check_neigh(rt);

  	if (!n && (strict & RT6_LOOKUP_F_REACHABLE))

  		return -1;
  	return m;
  }

  static struct rt6_info *find_match(struct rt6_info *rt, int oif, int strict,
  				   int *mpri, struct rt6_info *match)

  {

  	int m;
  
  	if (rt6_check_expired(rt))
  		goto out;
  
  	m = rt6_score_route(rt, oif, strict);
  	if (m < 0)
  		goto out;
  
  	if (m > *mpri) {
  		if (strict & RT6_LOOKUP_F_REACHABLE)
  			rt6_probe(match);
  		*mpri = m;
  		match = rt;
  	} else if (strict & RT6_LOOKUP_F_REACHABLE) {
  		rt6_probe(rt);
  	}
  
  out:
  	return match;
  }
  
  static struct rt6_info *find_rr_leaf(struct fib6_node *fn,
  				     struct rt6_info *rr_head,
  				     u32 metric, int oif, int strict)
  {
  	struct rt6_info *rt, *match;

  	int mpri = -1;

  	match = NULL;
  	for (rt = rr_head; rt && rt->rt6i_metric == metric;

  	     rt = rt->dst.rt6_next)

  		match = find_match(rt, oif, strict, &mpri, match);
  	for (rt = fn->leaf; rt && rt != rr_head && rt->rt6i_metric == metric;

  	     rt = rt->dst.rt6_next)

  		match = find_match(rt, oif, strict, &mpri, match);

  	return match;
  }

  static struct rt6_info *rt6_select(struct fib6_node *fn, int oif, int strict)
  {
  	struct rt6_info *match, *rt0;

  	struct net *net;

  	rt0 = fn->rr_ptr;
  	if (!rt0)
  		fn->rr_ptr = rt0 = fn->leaf;

  	match = find_rr_leaf(fn, rt0, rt0->rt6i_metric, oif, strict);

  	if (!match &&

  	    (strict & RT6_LOOKUP_F_REACHABLE)) {

  		struct rt6_info *next = rt0->dst.rt6_next;

  		/* no entries matched; do round-robin */

  		if (!next || next->rt6i_metric != rt0->rt6i_metric)
  			next = fn->leaf;
  
  		if (next != rt0)
  			fn->rr_ptr = next;

  	}

  	net = dev_net(rt0->dst.dev);

  	return match ? match : net->ipv6.ip6_null_entry;

  }

  #ifdef CONFIG_IPV6_ROUTE_INFO
  int rt6_route_rcv(struct net_device *dev, u8 *opt, int len,

  		  const struct in6_addr *gwaddr)

  {

  	struct net *net = dev_net(dev);

  	struct route_info *rinfo = (struct route_info *) opt;
  	struct in6_addr prefix_buf, *prefix;
  	unsigned int pref;

  	unsigned long lifetime;

  	struct rt6_info *rt;
  
  	if (len < sizeof(struct route_info)) {
  		return -EINVAL;
  	}
  
  	/* Sanity check for prefix_len and length */
  	if (rinfo->length > 3) {
  		return -EINVAL;
  	} else if (rinfo->prefix_len > 128) {
  		return -EINVAL;
  	} else if (rinfo->prefix_len > 64) {
  		if (rinfo->length < 2) {
  			return -EINVAL;
  		}
  	} else if (rinfo->prefix_len > 0) {
  		if (rinfo->length < 1) {
  			return -EINVAL;
  		}
  	}
  
  	pref = rinfo->route_pref;
  	if (pref == ICMPV6_ROUTER_PREF_INVALID)

  		return -EINVAL;

  	lifetime = addrconf_timeout_fixup(ntohl(rinfo->lifetime), HZ);

  
  	if (rinfo->length == 3)
  		prefix = (struct in6_addr *)rinfo->prefix;
  	else {
  		/* this function is safe */
  		ipv6_addr_prefix(&prefix_buf,
  				 (struct in6_addr *)rinfo->prefix,
  				 rinfo->prefix_len);
  		prefix = &prefix_buf;
  	}

  	rt = rt6_get_route_info(net, prefix, rinfo->prefix_len, gwaddr,
  				dev->ifindex);

  
  	if (rt && !lifetime) {

  		ip6_del_rt(rt);

  		rt = NULL;
  	}
  
  	if (!rt && lifetime)

  		rt = rt6_add_route_info(net, prefix, rinfo->prefix_len, gwaddr, dev->ifindex,

  					pref);
  	else if (rt)
  		rt->rt6i_flags = RTF_ROUTEINFO |
  				 (rt->rt6i_flags & ~RTF_PREF_MASK) | RTF_PREF(pref);
  
  	if (rt) {

  		if (!addrconf_finite_timeout(lifetime)) {

  			rt->rt6i_flags &= ~RTF_EXPIRES;
  		} else {

  			rt->dst.expires = jiffies + HZ * lifetime;

  			rt->rt6i_flags |= RTF_EXPIRES;
  		}

  		dst_release(&rt->dst);

  	}
  	return 0;
  }
  #endif

  #define BACKTRACK(__net, saddr)			\

  do { \

  	if (rt == __net->ipv6.ip6_null_entry) {	\

  		struct fib6_node *pn; \

  		while (1) { \

  			if (fn->fn_flags & RTN_TL_ROOT) \
  				goto out; \
  			pn = fn->parent; \
  			if (FIB6_SUBTREE(pn) && FIB6_SUBTREE(pn) != fn) \

  				fn = fib6_lookup(FIB6_SUBTREE(pn), NULL, saddr); \

  			else \
  				fn = pn; \
  			if (fn->fn_flags & RTN_RTINFO) \
  				goto restart; \

  		} \

  	} \

  } while (0)

  static struct rt6_info *ip6_pol_route_lookup(struct net *net,
  					     struct fib6_table *table,

  					     struct flowi6 *fl6, int flags)

  {
  	struct fib6_node *fn;
  	struct rt6_info *rt;

  	read_lock_bh(&table->tb6_lock);

  	fn = fib6_lookup(&table->tb6_root, &fl6->daddr, &fl6->saddr);

  restart:
  	rt = fn->leaf;

  	rt = rt6_device_match(net, rt, &fl6->saddr, fl6->flowi6_oif, flags);
  	BACKTRACK(net, &fl6->saddr);

  out:

  	dst_use(&rt->dst, jiffies);

  	read_unlock_bh(&table->tb6_lock);

  	return rt;
  
  }

  struct dst_entry * ip6_route_lookup(struct net *net, struct flowi6 *fl6,
  				    int flags)
  {
  	return fib6_rule_lookup(net, fl6, flags, ip6_pol_route_lookup);
  }
  EXPORT_SYMBOL_GPL(ip6_route_lookup);

  struct rt6_info *rt6_lookup(struct net *net, const struct in6_addr *daddr,
  			    const struct in6_addr *saddr, int oif, int strict)

  {

  	struct flowi6 fl6 = {
  		.flowi6_oif = oif,
  		.daddr = *daddr,

  	};
  	struct dst_entry *dst;

  	int flags = strict ? RT6_LOOKUP_F_IFACE : 0;

  	if (saddr) {

  		memcpy(&fl6.saddr, saddr, sizeof(*saddr));

  		flags |= RT6_LOOKUP_F_HAS_SADDR;
  	}

  	dst = fib6_rule_lookup(net, &fl6, flags, ip6_pol_route_lookup);

  	if (dst->error == 0)
  		return (struct rt6_info *) dst;
  
  	dst_release(dst);

  	return NULL;
  }

  EXPORT_SYMBOL(rt6_lookup);

  /* ip6_ins_rt is called with FREE table->tb6_lock.

     It takes new route entry, the addition fails by any reason the
     route is freed. In any case, if caller does not hold it, it may
     be destroyed.
   */

  static int __ip6_ins_rt(struct rt6_info *rt, struct nl_info *info)

  {
  	int err;

  	struct fib6_table *table;

  	table = rt->rt6i_table;
  	write_lock_bh(&table->tb6_lock);

  	err = fib6_add(&table->tb6_root, rt, info);

  	write_unlock_bh(&table->tb6_lock);

  
  	return err;
  }

  int ip6_ins_rt(struct rt6_info *rt)
  {

  	struct nl_info info = {

  		.nl_net = dev_net(rt->dst.dev),

  	};

  	return __ip6_ins_rt(rt, &info);

  }

  static struct rt6_info *rt6_alloc_cow(const struct rt6_info *ort,
  				      const struct in6_addr *daddr,

  				      const struct in6_addr *saddr)

  {

  	struct rt6_info *rt;
  
  	/*
  	 *	Clone the route.
  	 */

  	rt = ip6_rt_copy(ort, daddr);

  
  	if (rt) {

  		int attempts = !in_softirq();

  		if (!(rt->rt6i_flags & RTF_GATEWAY)) {

  			if (ort->rt6i_dst.plen != 128 &&

  			    ipv6_addr_equal(&ort->rt6i_dst.addr, daddr))

  				rt->rt6i_flags |= RTF_ANYCAST;

  			rt->rt6i_gateway = *daddr;

  		}

  		rt->rt6i_flags |= RTF_CACHE;

  
  #ifdef CONFIG_IPV6_SUBTREES
  		if (rt->rt6i_src.plen && saddr) {

  			rt->rt6i_src.addr = *saddr;

  			rt->rt6i_src.plen = 128;
  		}
  #endif

  	retry:

  		if (rt6_bind_neighbour(rt, rt->dst.dev)) {

  			struct net *net = dev_net(rt->dst.dev);

  			int saved_rt_min_interval =
  				net->ipv6.sysctl.ip6_rt_gc_min_interval;
  			int saved_rt_elasticity =
  				net->ipv6.sysctl.ip6_rt_gc_elasticity;
  
  			if (attempts-- > 0) {
  				net->ipv6.sysctl.ip6_rt_gc_elasticity = 1;
  				net->ipv6.sysctl.ip6_rt_gc_min_interval = 0;

  				ip6_dst_gc(&net->ipv6.ip6_dst_ops);

  
  				net->ipv6.sysctl.ip6_rt_gc_elasticity =
  					saved_rt_elasticity;
  				net->ipv6.sysctl.ip6_rt_gc_min_interval =
  					saved_rt_min_interval;
  				goto retry;
  			}
  
  			if (net_ratelimit())
  				printk(KERN_WARNING

  				       "ipv6: Neighbour table overflow.
  ");

  			dst_free(&rt->dst);

  			return NULL;
  		}

  	}

  	return rt;
  }

  static struct rt6_info *rt6_alloc_clone(struct rt6_info *ort,
  					const struct in6_addr *daddr)

  {

  	struct rt6_info *rt = ip6_rt_copy(ort, daddr);

  	if (rt) {

  		rt->rt6i_flags |= RTF_CACHE;

  		dst_set_neighbour(&rt->dst, neigh_clone(dst_get_neighbour_noref_raw(&ort->dst)));

  	}
  	return rt;
  }

  static struct rt6_info *ip6_pol_route(struct net *net, struct fib6_table *table, int oif,

  				      struct flowi6 *fl6, int flags)

  {
  	struct fib6_node *fn;

  	struct rt6_info *rt, *nrt;

  	int strict = 0;

  	int attempts = 3;

  	int err;

  	int reachable = net->ipv6.devconf_all->forwarding ? 0 : RT6_LOOKUP_F_REACHABLE;

  	strict |= flags & RT6_LOOKUP_F_IFACE;

  
  relookup:

  	read_lock_bh(&table->tb6_lock);

  restart_2:

  	fn = fib6_lookup(&table->tb6_root, &fl6->daddr, &fl6->saddr);

  
  restart:

  	rt = rt6_select(fn, oif, strict | reachable);

  	BACKTRACK(net, &fl6->saddr);

  	if (rt == net->ipv6.ip6_null_entry ||

  	    rt->rt6i_flags & RTF_CACHE)

  		goto out;

  	dst_hold(&rt->dst);

  	read_unlock_bh(&table->tb6_lock);

  	if (!dst_get_neighbour_noref_raw(&rt->dst) && !(rt->rt6i_flags & RTF_NONEXTHOP))

  		nrt = rt6_alloc_cow(rt, &fl6->daddr, &fl6->saddr);

  	else if (!(rt->dst.flags & DST_HOST))

  		nrt = rt6_alloc_clone(rt, &fl6->daddr);

  	else
  		goto out2;

  	dst_release(&rt->dst);

  	rt = nrt ? : net->ipv6.ip6_null_entry;

  	dst_hold(&rt->dst);

  	if (nrt) {

  		err = ip6_ins_rt(nrt);

  		if (!err)

  			goto out2;

  	}

  	if (--attempts <= 0)
  		goto out2;
  
  	/*

  	 * Race condition! In the gap, when table->tb6_lock was

  	 * released someone could insert this route.  Relookup.
  	 */

  	dst_release(&rt->dst);

  	goto relookup;
  
  out:

  	if (reachable) {
  		reachable = 0;
  		goto restart_2;
  	}

  	dst_hold(&rt->dst);

  	read_unlock_bh(&table->tb6_lock);

  out2:

  	rt->dst.lastuse = jiffies;
  	rt->dst.__use++;

  
  	return rt;

  }

  static struct rt6_info *ip6_pol_route_input(struct net *net, struct fib6_table *table,

  					    struct flowi6 *fl6, int flags)

  {

  	return ip6_pol_route(net, table, fl6->flowi6_iif, fl6, flags);

  }

  void ip6_route_input(struct sk_buff *skb)
  {

  	const struct ipv6hdr *iph = ipv6_hdr(skb);

  	struct net *net = dev_net(skb->dev);

  	int flags = RT6_LOOKUP_F_HAS_SADDR;

  	struct flowi6 fl6 = {
  		.flowi6_iif = skb->dev->ifindex,
  		.daddr = iph->daddr,
  		.saddr = iph->saddr,

  		.flowlabel = (* (__be32 *) iph) & IPV6_FLOWINFO_MASK,

  		.flowi6_mark = skb->mark,
  		.flowi6_proto = iph->nexthdr,

  	};

  	if (rt6_need_strict(&iph->daddr) && skb->dev->type != ARPHRD_PIMREG)

  		flags |= RT6_LOOKUP_F_IFACE;

  	skb_dst_set(skb, fib6_rule_lookup(net, &fl6, flags, ip6_pol_route_input));

  }

  static struct rt6_info *ip6_pol_route_output(struct net *net, struct fib6_table *table,

  					     struct flowi6 *fl6, int flags)

  {

  	return ip6_pol_route(net, table, fl6->flowi6_oif, fl6, flags);

  }

  struct dst_entry * ip6_route_output(struct net *net, const struct sock *sk,

  				    struct flowi6 *fl6)

  {
  	int flags = 0;

  	if ((sk && sk->sk_bound_dev_if) || rt6_need_strict(&fl6->daddr))

  		flags |= RT6_LOOKUP_F_IFACE;

  	if (!ipv6_addr_any(&fl6->saddr))

  		flags |= RT6_LOOKUP_F_HAS_SADDR;

  	else if (sk)
  		flags |= rt6_srcprefs2flags(inet6_sk(sk)->srcprefs);

  	return fib6_rule_lookup(net, fl6, flags, ip6_pol_route_output);

  }

  EXPORT_SYMBOL(ip6_route_output);

  struct dst_entry *ip6_blackhole_route(struct net *net, struct dst_entry *dst_orig)

  {

  	struct rt6_info *rt, *ort = (struct rt6_info *) dst_orig;

  	struct dst_entry *new = NULL;

  	rt = dst_alloc(&ip6_dst_blackhole_ops, ort->dst.dev, 1, 0, 0);

  	if (rt) {

  		memset(&rt->rt6i_table, 0, sizeof(*rt) - sizeof(struct dst_entry));

  		new = &rt->dst;

  		new->__use = 1;

  		new->input = dst_discard;
  		new->output = dst_discard;

  		if (dst_metrics_read_only(&ort->dst))
  			new->_metrics = ort->dst._metrics;
  		else
  			dst_copy_metrics(new, &ort->dst);

  		rt->rt6i_idev = ort->rt6i_idev;
  		if (rt->rt6i_idev)
  			in6_dev_hold(rt->rt6i_idev);

  		rt->dst.expires = 0;

  		rt->rt6i_gateway = ort->rt6i_gateway;

  		rt->rt6i_flags = ort->rt6i_flags & ~RTF_EXPIRES;
  		rt->rt6i_metric = 0;
  
  		memcpy(&rt->rt6i_dst, &ort->rt6i_dst, sizeof(struct rt6key));
  #ifdef CONFIG_IPV6_SUBTREES
  		memcpy(&rt->rt6i_src, &ort->rt6i_src, sizeof(struct rt6key));
  #endif
  
  		dst_free(new);
  	}

  	dst_release(dst_orig);
  	return new ? new : ERR_PTR(-ENOMEM);

  }

  /*
   *	Destination cache support functions
   */
  
  static struct dst_entry *ip6_dst_check(struct dst_entry *dst, u32 cookie)
  {
  	struct rt6_info *rt;
  
  	rt = (struct rt6_info *) dst;

  	if (rt->rt6i_node && (rt->rt6i_node->fn_sernum == cookie)) {
  		if (rt->rt6i_peer_genid != rt6_peer_genid()) {
  			if (!rt->rt6i_peer)
  				rt6_bind_peer(rt, 0);
  			rt->rt6i_peer_genid = rt6_peer_genid();
  		}

  		return dst;

  	}

  	return NULL;
  }
  
  static struct dst_entry *ip6_negative_advice(struct dst_entry *dst)
  {
  	struct rt6_info *rt = (struct rt6_info *) dst;
  
  	if (rt) {

  		if (rt->rt6i_flags & RTF_CACHE) {
  			if (rt6_check_expired(rt)) {
  				ip6_del_rt(rt);
  				dst = NULL;
  			}
  		} else {

  			dst_release(dst);

  			dst = NULL;
  		}

  	}

  	return dst;

  }
  
  static void ip6_link_failure(struct sk_buff *skb)
  {
  	struct rt6_info *rt;

  	icmpv6_send(skb, ICMPV6_DEST_UNREACH, ICMPV6_ADDR_UNREACH, 0);

  	rt = (struct rt6_info *) skb_dst(skb);

  	if (rt) {

  		if (rt->rt6i_flags & RTF_CACHE) {

  			dst_set_expires(&rt->dst, 0);

  			rt->rt6i_flags |= RTF_EXPIRES;
  		} else if (rt->rt6i_node && (rt->rt6i_flags & RTF_DEFAULT))
  			rt->rt6i_node->fn_sernum = -1;
  	}
  }
  
  static void ip6_rt_update_pmtu(struct dst_entry *dst, u32 mtu)
  {
  	struct rt6_info *rt6 = (struct rt6_info*)dst;
  
  	if (mtu < dst_mtu(dst) && rt6->rt6i_dst.plen == 128) {
  		rt6->rt6i_flags |= RTF_MODIFIED;
  		if (mtu < IPV6_MIN_MTU) {

  			u32 features = dst_metric(dst, RTAX_FEATURES);

  			mtu = IPV6_MIN_MTU;

  			features |= RTAX_FEATURE_ALLFRAG;
  			dst_metric_set(dst, RTAX_FEATURES, features);

  		}

  		dst_metric_set(dst, RTAX_MTU, mtu);

  	}
  }

  static unsigned int ip6_default_advmss(const struct dst_entry *dst)

  {

  	struct net_device *dev = dst->dev;
  	unsigned int mtu = dst_mtu(dst);
  	struct net *net = dev_net(dev);

  	mtu -= sizeof(struct ipv6hdr) + sizeof(struct tcphdr);

  	if (mtu < net->ipv6.sysctl.ip6_rt_min_advmss)
  		mtu = net->ipv6.sysctl.ip6_rt_min_advmss;

  
  	/*

  	 * Maximal non-jumbo IPv6 payload is IPV6_MAXPLEN and
  	 * corresponding MSS is IPV6_MAXPLEN - tcp_header_size.
  	 * IPV6_MAXPLEN is also valid and means: "any MSS,

  	 * rely only on pmtu discovery"
  	 */
  	if (mtu > IPV6_MAXPLEN - sizeof(struct tcphdr))
  		mtu = IPV6_MAXPLEN;
  	return mtu;
  }

  static unsigned int ip6_mtu(const struct dst_entry *dst)

  {

  	struct inet6_dev *idev;

  	unsigned int mtu = dst_metric_raw(dst, RTAX_MTU);
  
  	if (mtu)
  		return mtu;
  
  	mtu = IPV6_MIN_MTU;

  
  	rcu_read_lock();
  	idev = __in6_dev_get(dst->dev);
  	if (idev)
  		mtu = idev->cnf.mtu6;
  	rcu_read_unlock();
  
  	return mtu;
  }

  static struct dst_entry *icmp6_dst_gc_list;
  static DEFINE_SPINLOCK(icmp6_dst_lock);

  struct dst_entry *icmp6_dst_alloc(struct net_device *dev,

  				  struct neighbour *neigh,

  				  struct flowi6 *fl6)

  {

  	struct dst_entry *dst;

  	struct rt6_info *rt;
  	struct inet6_dev *idev = in6_dev_get(dev);

  	struct net *net = dev_net(dev);

  	if (unlikely(!idev))

  		return NULL;

  	rt = ip6_dst_alloc(&net->ipv6.ip6_dst_ops, dev, 0);

  	if (unlikely(!rt)) {

  		in6_dev_put(idev);

  		dst = ERR_PTR(-ENOMEM);

  		goto out;
  	}

  	if (neigh)
  		neigh_hold(neigh);

  	else {

  		neigh = ip6_neigh_lookup(&rt->dst, &fl6->daddr);

  		if (IS_ERR(neigh)) {
  			dst_free(&rt->dst);
  			return ERR_CAST(neigh);
  		}

  	}

  	rt->dst.flags |= DST_HOST;
  	rt->dst.output  = ip6_output;

  	dst_set_neighbour(&rt->dst, neigh);

  	atomic_set(&rt->dst.__refcnt, 1);

  	rt->rt6i_dst.addr = fl6->daddr;

  	rt->rt6i_dst.plen = 128;
  	rt->rt6i_idev     = idev;

  	dst_metric_set(&rt->dst, RTAX_HOPLIMIT, 255);

  	spin_lock_bh(&icmp6_dst_lock);

  	rt->dst.next = icmp6_dst_gc_list;
  	icmp6_dst_gc_list = &rt->dst;

  	spin_unlock_bh(&icmp6_dst_lock);

  	fib6_force_start_gc(net);

  	dst = xfrm_lookup(net, &rt->dst, flowi6_to_flowi(fl6), NULL, 0);

  out:

  	return dst;

  }

  int icmp6_dst_gc(void)

  {

  	struct dst_entry *dst, **pprev;

  	int more = 0;

  	spin_lock_bh(&icmp6_dst_lock);
  	pprev = &icmp6_dst_gc_list;

  	while ((dst = *pprev) != NULL) {
  		if (!atomic_read(&dst->__refcnt)) {
  			*pprev = dst->next;
  			dst_free(dst);

  		} else {
  			pprev = &dst->next;

  			++more;

  		}
  	}

  	spin_unlock_bh(&icmp6_dst_lock);

  	return more;

  }

  static void icmp6_clean_all(int (*func)(struct rt6_info *rt, void *arg),
  			    void *arg)
  {
  	struct dst_entry *dst, **pprev;
  
  	spin_lock_bh(&icmp6_dst_lock);
  	pprev = &icmp6_dst_gc_list;
  	while ((dst = *pprev) != NULL) {
  		struct rt6_info *rt = (struct rt6_info *) dst;
  		if (func(rt, arg)) {
  			*pprev = dst->next;
  			dst_free(dst);
  		} else {
  			pprev = &dst->next;
  		}
  	}
  	spin_unlock_bh(&icmp6_dst_lock);
  }

  static int ip6_dst_gc(struct dst_ops *ops)

  {

  	unsigned long now = jiffies;

  	struct net *net = container_of(ops, struct net, ipv6.ip6_dst_ops);

  	int rt_min_interval = net->ipv6.sysctl.ip6_rt_gc_min_interval;
  	int rt_max_size = net->ipv6.sysctl.ip6_rt_max_size;
  	int rt_elasticity = net->ipv6.sysctl.ip6_rt_gc_elasticity;
  	int rt_gc_timeout = net->ipv6.sysctl.ip6_rt_gc_timeout;
  	unsigned long rt_last_gc = net->ipv6.ip6_rt_last_gc;

  	int entries;

  	entries = dst_entries_get_fast(ops);

  	if (time_after(rt_last_gc + rt_min_interval, now) &&

  	    entries <= rt_max_size)

  		goto out;

  	net->ipv6.ip6_rt_gc_expire++;
  	fib6_run_gc(net->ipv6.ip6_rt_gc_expire, net);
  	net->ipv6.ip6_rt_last_gc = now;

  	entries = dst_entries_get_slow(ops);
  	if (entries < ops->gc_thresh)

  		net->ipv6.ip6_rt_gc_expire = rt_gc_timeout>>1;

  out:

  	net->ipv6.ip6_rt_gc_expire -= net->ipv6.ip6_rt_gc_expire>>rt_elasticity;

  	return entries > rt_max_size;

  }
  
  /* Clean host part of a prefix. Not necessary in radix tree,
     but results in cleaner routing tables.
  
     Remove it only when all the things will work!
   */

  int ip6_dst_hoplimit(struct dst_entry *dst)

  {

  	int hoplimit = dst_metric_raw(dst, RTAX_HOPLIMIT);

  	if (hoplimit == 0) {

  		struct net_device *dev = dst->dev;

  		struct inet6_dev *idev;
  
  		rcu_read_lock();
  		idev = __in6_dev_get(dev);
  		if (idev)

  			hoplimit = idev->cnf.hop_limit;

  		else

  			hoplimit = dev_net(dev)->ipv6.devconf_all->hop_limit;

  		rcu_read_unlock();

  	}
  	return hoplimit;
  }

  EXPORT_SYMBOL(ip6_dst_hoplimit);

  
  /*
   *
   */

  int ip6_route_add(struct fib6_config *cfg)

  {
  	int err;

  	struct net *net = cfg->fc_nlinfo.nl_net;

  	struct rt6_info *rt = NULL;
  	struct net_device *dev = NULL;
  	struct inet6_dev *idev = NULL;

  	struct fib6_table *table;

  	int addr_type;

  	if (cfg->fc_dst_len > 128 || cfg->fc_src_len > 128)

  		return -EINVAL;
  #ifndef CONFIG_IPV6_SUBTREES

  	if (cfg->fc_src_len)

  		return -EINVAL;
  #endif

  	if (cfg->fc_ifindex) {

  		err = -ENODEV;

  		dev = dev_get_by_index(net, cfg->fc_ifindex);

  		if (!dev)
  			goto out;
  		idev = in6_dev_get(dev);
  		if (!idev)
  			goto out;
  	}

  	if (cfg->fc_metric == 0)
  		cfg->fc_metric = IP6_RT_PRIO_USER;

  	err = -ENOBUFS;

  	if (cfg->fc_nlinfo.nlh &&
  	    !(cfg->fc_nlinfo.nlh->nlmsg_flags & NLM_F_CREATE)) {

  		table = fib6_get_table(net, cfg->fc_table);

  		if (!table) {

  			printk(KERN_WARNING "IPv6: NLM_F_CREATE should be specified when creating new route
  ");
  			table = fib6_new_table(net, cfg->fc_table);
  		}
  	} else {
  		table = fib6_new_table(net, cfg->fc_table);
  	}

  
  	if (!table)

  		goto out;

  	rt = ip6_dst_alloc(&net->ipv6.ip6_dst_ops, NULL, DST_NOCOUNT);

  	if (!rt) {

  		err = -ENOMEM;
  		goto out;
  	}

  	rt->dst.obsolete = -1;

  	rt->dst.expires = (cfg->fc_flags & RTF_EXPIRES) ?

  				jiffies + clock_t_to_jiffies(cfg->fc_expires) :
  				0;

  	if (cfg->fc_protocol == RTPROT_UNSPEC)
  		cfg->fc_protocol = RTPROT_BOOT;
  	rt->rt6i_protocol = cfg->fc_protocol;
  
  	addr_type = ipv6_addr_type(&cfg->fc_dst);

  
  	if (addr_type & IPV6_ADDR_MULTICAST)

  		rt->dst.input = ip6_mc_input;

  	else if (cfg->fc_flags & RTF_LOCAL)
  		rt->dst.input = ip6_input;

  	else

  		rt->dst.input = ip6_forward;

  	rt->dst.output = ip6_output;

  	ipv6_addr_prefix(&rt->rt6i_dst.addr, &cfg->fc_dst, cfg->fc_dst_len);
  	rt->rt6i_dst.plen = cfg->fc_dst_len;

  	if (rt->rt6i_dst.plen == 128)

  	       rt->dst.flags |= DST_HOST;

  	if (!(rt->dst.flags & DST_HOST) && cfg->fc_mx) {
  		u32 *metrics = kzalloc(sizeof(u32) * RTAX_MAX, GFP_KERNEL);
  		if (!metrics) {
  			err = -ENOMEM;
  			goto out;
  		}
  		dst_init_metrics(&rt->dst, metrics, 0);
  	}

  #ifdef CONFIG_IPV6_SUBTREES

  	ipv6_addr_prefix(&rt->rt6i_src.addr, &cfg->fc_src, cfg->fc_src_len);
  	rt->rt6i_src.plen = cfg->fc_src_len;

  #endif

  	rt->rt6i_metric = cfg->fc_metric;

  
  	/* We cannot add true routes via loopback here,
  	   they would result in kernel looping; promote them to reject routes
  	 */

  	if ((cfg->fc_flags & RTF_REJECT) ||

  	    (dev && (dev->flags & IFF_LOOPBACK) &&
  	     !(addr_type & IPV6_ADDR_LOOPBACK) &&
  	     !(cfg->fc_flags & RTF_LOCAL))) {

  		/* hold loopback dev/idev if we haven't done so. */

  		if (dev != net->loopback_dev) {

  			if (dev) {
  				dev_put(dev);
  				in6_dev_put(idev);
  			}

  			dev = net->loopback_dev;

  			dev_hold(dev);
  			idev = in6_dev_get(dev);
  			if (!idev) {
  				err = -ENODEV;
  				goto out;
  			}
  		}

  		rt->dst.output = ip6_pkt_discard_out;
  		rt->dst.input = ip6_pkt_discard;
  		rt->dst.error = -ENETUNREACH;

  		rt->rt6i_flags = RTF_REJECT|RTF_NONEXTHOP;
  		goto install_route;
  	}

  	if (cfg->fc_flags & RTF_GATEWAY) {

  		const struct in6_addr *gw_addr;

  		int gwa_type;

  		gw_addr = &cfg->fc_gateway;

  		rt->rt6i_gateway = *gw_addr;

  		gwa_type = ipv6_addr_type(gw_addr);
  
  		if (gwa_type != (IPV6_ADDR_LINKLOCAL|IPV6_ADDR_UNICAST)) {
  			struct rt6_info *grt;
  
  			/* IPv6 strictly inhibits using not link-local
  			   addresses as nexthop address.
  			   Otherwise, router will not able to send redirects.
  			   It is very good, but in some (rare!) circumstances
  			   (SIT, PtP, NBMA NOARP links) it is handy to allow
  			   some exceptions. --ANK
  			 */
  			err = -EINVAL;