route.c

Linux Kernel 2.6.9 for OMAP1710

/*
 *	Linux INET6 implementation
 *	FIB front-end.
 *
 *	Authors:
 *	Pedro Roque		<[e-mail]>	
 *
 *	$Id: route.c,v 1.56 2001/10/31 21:55:55 davem Exp $
 *
 *	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.
 */

#include <linux/config.h>
#include <linux/errno.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/init.h>
#include <linux/netlink.h>
#include <linux/if_arp.h>

#ifdef 	CONFIG_PROC_FS
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#endif

#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 <asm/uaccess.h>

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

/* Set to 3 to get tracing. */
#define RT6_DEBUG 2

#if RT6_DEBUG >= 3
#define RDBG(x) printk x
#define RT6_TRACE(x...) printk(KERN_DEBUG x)
#else
#define RDBG(x)
#define RT6_TRACE(x...) do { ; } while (0)
#endif


static int ip6_rt_max_size = 4096;
static int ip6_rt_gc_min_interval = HZ / 2;
static int ip6_rt_gc_timeout = 60*HZ;
int ip6_rt_gc_interval = 30*HZ;
static int ip6_rt_gc_elasticity = 9;
static int ip6_rt_mtu_expires = 10*60*HZ;
static int ip6_rt_min_advmss = IPV6_MIN_MTU - 20 - 40;

static struct rt6_info * ip6_rt_copy(struct rt6_info *ort);
static struct dst_entry	*ip6_dst_check(struct dst_entry *dst, u32 cookie);
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 *, int how);
static int		 ip6_dst_gc(void);

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

static struct dst_ops ip6_dst_ops = {
	.family			=	AF_INET6,
	.protocol		=	__constant_htons(ETH_P_IPV6),
	.gc			=	ip6_dst_gc,
	.gc_thresh		=	1024,
	.check			=	ip6_dst_check,
	.destroy		=	ip6_dst_destroy,
	.ifdown			=	ip6_dst_ifdown,
	.negative_advice	=	ip6_negative_advice,
	.link_failure		=	ip6_link_failure,
	.update_pmtu		=	ip6_rt_update_pmtu,
	.entry_size		=	sizeof(struct rt6_info),
};

struct rt6_info ip6_null_entry = {
	.u = {
		.dst = {
			.__refcnt	= ATOMIC_INIT(1),
			.__use		= 1,
			.dev		= &loopback_dev,
			.obsolete	= -1,
			.error		= -ENETUNREACH,
			.metrics	= { [RTAX_HOPLIMIT - 1] = 255, },
			.input		= ip6_pkt_discard,
			.output		= ip6_pkt_discard_out,
			.ops		= &ip6_dst_ops,
			.path		= (struct dst_entry*)&ip6_null_entry,
		}
	},
	.rt6i_flags	= (RTF_REJECT | RTF_NONEXTHOP),
	.rt6i_metric	= ~(u32) 0,
	.rt6i_ref	= ATOMIC_INIT(1),
};

struct fib6_node ip6_routing_table = {
	.leaf		= &ip6_null_entry,
	.fn_flags	= RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO,
};

/* Protects all the ip6 fib */

rwlock_t rt6_lock = RW_LOCK_UNLOCKED;


/* allocate dst with ip6_dst_ops */
static __inline__ struct rt6_info *ip6_dst_alloc(void)
{
	return (struct rt6_info *)dst_alloc(&ip6_dst_ops);
}

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

	if (idev != NULL) {
		rt->rt6i_idev = NULL;
		in6_dev_put(idev);
	}	
}

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

	if (idev != NULL && idev->dev != &loopback_dev) {
		struct inet6_dev *loopback_idev = in6_dev_get(&loopback_dev);
		if (loopback_idev != NULL) {
			rt->rt6i_idev = loopback_idev;
			in6_dev_put(idev);
		}
	}
}

/*
 *	Route lookup. Any rt6_lock is implied.
 */

static __inline__ struct rt6_info *rt6_device_match(struct rt6_info *rt,
						    int oif,
						    int strict)
{
	struct rt6_info *local = NULL;
	struct rt6_info *sprt;

	if (oif) {
		for (sprt = rt; sprt; sprt = sprt->u.next) {
			struct net_device *dev = sprt->rt6i_dev;
			if (dev->ifindex == oif)
				return sprt;
			if (dev->flags & IFF_LOOPBACK) {
				if (sprt->rt6i_idev == NULL ||
				    sprt->rt6i_idev->dev->ifindex != oif) {
					if (strict && oif)
						continue;
					if (local && (!oif || 
						      local->rt6i_idev->dev->ifindex == oif))
						continue;
				}
				local = sprt;
			}
		}

		if (local)
			return local;

		if (strict)
			return &ip6_null_entry;
	}
	return rt;
}

/*
 *	pointer to the last default router chosen. BH is disabled locally.
 */
struct rt6_info *rt6_dflt_pointer;
spinlock_t rt6_dflt_lock = SPIN_LOCK_UNLOCKED;

void rt6_reset_dflt_pointer(struct rt6_info *rt)
{
	spin_lock_bh(&rt6_dflt_lock);
	if (rt == NULL || rt == rt6_dflt_pointer) {
		RT6_TRACE("reset default router: %p->NULL\n", rt6_dflt_pointer);
		rt6_dflt_pointer = NULL;
	}
	spin_unlock_bh(&rt6_dflt_lock);
}

/* Default Router Selection (RFC 2461 6.3.6) */
static struct rt6_info *rt6_best_dflt(struct rt6_info *rt, int oif)
{
	struct rt6_info *match = NULL;
	struct rt6_info *sprt;
	int mpri = 0;

	for (sprt = rt; sprt; sprt = sprt->u.next) {
		struct neighbour *neigh;
		int m = 0;

		if (!oif ||
		    (sprt->rt6i_dev &&
		     sprt->rt6i_dev->ifindex == oif))
			m += 8;

		if ((sprt->rt6i_flags & RTF_EXPIRES) &&
		    time_after(jiffies, sprt->rt6i_expires))
			continue;

		if (sprt == rt6_dflt_pointer)
			m += 4;

		if ((neigh = sprt->rt6i_nexthop) != NULL) {
			read_lock_bh(&neigh->lock);
			switch (neigh->nud_state) {
			case NUD_REACHABLE:
				m += 3;
				break;

			case NUD_STALE:
			case NUD_DELAY:
			case NUD_PROBE:
				m += 2;
				break;

			case NUD_NOARP:
			case NUD_PERMANENT:
				m += 1;
				break;

			case NUD_INCOMPLETE:
			default:
				read_unlock_bh(&neigh->lock);
				continue;
			}
			read_unlock_bh(&neigh->lock);
		} else {
			continue;
		}

		if (m > mpri || m >= 12) {
			match = sprt;
			mpri = m;
			if (m >= 12) {
				/* we choose the last default router if it
				 * is in (probably) reachable state.
				 * If route changed, we should do pmtu
				 * discovery. --yoshfuji
				 */
				break;
			}
		}
	}

	spin_lock(&rt6_dflt_lock);
	if (!match) {
		/*
		 *	No default routers are known to be reachable.
		 *	SHOULD round robin
		 */
		if (rt6_dflt_pointer) {
			for (sprt = rt6_dflt_pointer->u.next;
			     sprt; sprt = sprt->u.next) {
				if (sprt->u.dst.obsolete <= 0 &&
				    sprt->u.dst.error == 0) {
					match = sprt;
					break;
				}
			}
			for (sprt = rt;
			     !match && sprt;
			     sprt = sprt->u.next) {
				if (sprt->u.dst.obsolete <= 0 &&
				    sprt->u.dst.error == 0) {
					match = sprt;
					break;
				}
				if (sprt == rt6_dflt_pointer)
					break;
			}
		}
	}

	if (match) {
		if (rt6_dflt_pointer != match)
			RT6_TRACE("changed default router: %p->%p\n",
				  rt6_dflt_pointer, match);
		rt6_dflt_pointer = match;
	}
	spin_unlock(&rt6_dflt_lock);

	if (!match) {
		/*
		 * Last Resort: if no default routers found, 
		 * use addrconf default route.
		 * We don't record this route.
		 */
		for (sprt = ip6_routing_table.leaf;
		     sprt; sprt = sprt->u.next) {
			if ((sprt->rt6i_flags & RTF_DEFAULT) &&
			    (!oif ||
			     (sprt->rt6i_dev &&
			      sprt->rt6i_dev->ifindex == oif))) {
				match = sprt;
				break;
			}
		}
		if (!match) {
			/* no default route.  give up. */
			match = &ip6_null_entry;
		}
	}

	return match;
}

struct rt6_info *rt6_lookup(struct in6_addr *daddr, struct in6_addr *saddr,
			    int oif, int strict)
{
	struct fib6_node *fn;
	struct rt6_info *rt;

	read_lock_bh(&rt6_lock);
	fn = fib6_lookup(&ip6_routing_table, daddr, saddr);
	rt = rt6_device_match(fn->leaf, oif, strict);
	dst_hold(&rt->u.dst);
	rt->u.dst.__use++;
	read_unlock_bh(&rt6_lock);

	rt->u.dst.lastuse = jiffies;
	if (rt->u.dst.error == 0)
		return rt;
	dst_release(&rt->u.dst);
	return NULL;
}

/* ip6_ins_rt is called with FREE rt6_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.
 */

int ip6_ins_rt(struct rt6_info *rt, struct nlmsghdr *nlh, void *_rtattr)
{
	int err;

	write_lock_bh(&rt6_lock);
	err = fib6_add(&ip6_routing_table, rt, nlh, _rtattr);
	write_unlock_bh(&rt6_lock);

	return err;
}

/* No rt6_lock! If COW failed, the function returns dead route entry
   with dst->error set to errno value.
 */

static struct rt6_info *rt6_cow(struct rt6_info *ort, struct in6_addr *daddr,
				struct in6_addr *saddr)
{
	int err;
	struct rt6_info *rt;

	/*
	 *	Clone the route.
	 */

	rt = ip6_rt_copy(ort);

	if (rt) {
		ipv6_addr_copy(&rt->rt6i_dst.addr, daddr);

		if (!(rt->rt6i_flags&RTF_GATEWAY))
			ipv6_addr_copy(&rt->rt6i_gateway, daddr);

		rt->rt6i_dst.plen = 128;
		rt->rt6i_flags |= RTF_CACHE;
		rt->u.dst.flags |= DST_HOST;

#ifdef CONFIG_IPV6_SUBTREES
		if (rt->rt6i_src.plen && saddr) {
			ipv6_addr_copy(&rt->rt6i_src.addr, saddr);
			rt->rt6i_src.plen = 128;
		}
#endif

		rt->rt6i_nexthop = ndisc_get_neigh(rt->rt6i_dev, &rt->rt6i_gateway);

		dst_hold(&rt->u.dst);

		err = ip6_ins_rt(rt, NULL, NULL);
		if (err == 0)
			return rt;

		rt->u.dst.error = err;

		return rt;
	}
	dst_hold(&ip6_null_entry.u.dst);
	return &ip6_null_entry;
}

#define BACKTRACK() \
if (rt == &ip6_null_entry && strict) { \
       while ((fn = fn->parent) != NULL) { \
		if (fn->fn_flags & RTN_ROOT) { \
			dst_hold(&rt->u.dst); \
			goto out; \
		} \
		if (fn->fn_flags & RTN_RTINFO) \
			goto restart; \
	} \
}


void ip6_route_input(struct sk_buff *skb)
{
	struct fib6_node *fn;
	struct rt6_info *rt;
	int strict;
	int attempts = 3;

	strict = ipv6_addr_type(&skb->nh.ipv6h->daddr) & (IPV6_ADDR_MULTICAST|IPV6_ADDR_LINKLOCAL);

relookup:
	read_lock_bh(&rt6_lock);

	fn = fib6_lookup(&ip6_routing_table, &skb->nh.ipv6h->daddr,
			 &skb->nh.ipv6h->saddr);

restart:
	rt = fn->leaf;

	if ((rt->rt6i_flags & RTF_CACHE)) {
		rt = rt6_device_match(rt, skb->dev->ifindex, strict);
		BACKTRACK();
		dst_hold(&rt->u.dst);
		goto out;
	}

	rt = rt6_device_match(rt, skb->dev->ifindex, 0);
	BACKTRACK();

	if (!rt->rt6i_nexthop && !(rt->rt6i_flags & RTF_NONEXTHOP)) {
		read_unlock_bh(&rt6_lock);

		rt = rt6_cow(rt, &skb->nh.ipv6h->daddr,
			     &skb->nh.ipv6h->saddr);
			
		if (rt->u.dst.error != -EEXIST || --attempts <= 0)
			goto out2;
		/* Race condition! In the gap, when rt6_lock was
		   released someone could insert this route.  Relookup.
		*/
		dst_release(&rt->u.dst);
		goto relookup;
	}
	dst_hold(&rt->u.dst);

out:
	read_unlock_bh(&rt6_lock);
out2:
	rt->u.dst.lastuse = jiffies;
	rt->u.dst.__use++;
	skb->dst = (struct dst_entry *) rt;
}

struct dst_entry * ip6_route_output(struct sock *sk, struct flowi *fl)
{
	struct fib6_node *fn;
	struct rt6_info *rt;
	int strict;
	int attempts = 3;

	strict = ipv6_addr_type(&fl->fl6_dst) & (IPV6_ADDR_MULTICAST|IPV6_ADDR_LINKLOCAL);

relookup:
	read_lock_bh(&rt6_lock);

	fn = fib6_lookup(&ip6_routing_table, &fl->fl6_dst, &fl->fl6_src);

restart:
	rt = fn->leaf;

	if ((rt->rt6i_flags & RTF_CACHE)) {
		rt = rt6_device_match(rt, fl->oif, strict);
		BACKTRACK();
		dst_hold(&rt->u.dst);
		goto out;
	}
	if (rt->rt6i_flags & RTF_DEFAULT) {
		if (rt->rt6i_metric >= IP6_RT_PRIO_ADDRCONF)