route.c

GNU Hurd 源代码

/*
 * INET		An implementation of the TCP/IP protocol suite for the LINUX
 *		operating system.  INET is implemented using the  BSD Socket
 *		interface as the means of communication with the user level.
 *
 *		ROUTE - implementation of the IP router.
 *
 * Version:	$Id: route.c,v 1.67.2.4 1999/11/16 02:28:43 davem Exp $
 *
 * Authors:	Ross Biro, <[e-mail]>
 *		Fred N. van Kempen, <[e-mail]>
 *		Alan Cox, <[e-mail]>
 *		Linus Torvalds, <[e-mail]>
 *		Alexey Kuznetsov, <[e-mail]>
 *
 * Fixes:
 *		Alan Cox	:	Verify area fixes.
 *		Alan Cox	:	cli() protects routing changes
 *		Rui Oliveira	:	ICMP routing table updates
 *		([e-mail])	Routing table insertion and update
 *		Linus Torvalds	:	Rewrote bits to be sensible
 *		Alan Cox	:	Added BSD route gw semantics
 *		Alan Cox	:	Super /proc >4K 
 *		Alan Cox	:	MTU in route table
 *		Alan Cox	: 	MSS actually. Also added the window
 *					clamper.
 *		Sam Lantinga	:	Fixed route matching in rt_del()
 *		Alan Cox	:	Routing cache support.
 *		Alan Cox	:	Removed compatibility cruft.
 *		Alan Cox	:	RTF_REJECT support.
 *		Alan Cox	:	TCP irtt support.
 *		Jonathan Naylor	:	Added Metric support.
 *	Miquel van Smoorenburg	:	BSD API fixes.
 *	Miquel van Smoorenburg	:	Metrics.
 *		Alan Cox	:	Use __u32 properly
 *		Alan Cox	:	Aligned routing errors more closely with BSD
 *					our system is still very different.
 *		Alan Cox	:	Faster /proc handling
 *	Alexey Kuznetsov	:	Massive rework to support tree based routing,
 *					routing caches and better behaviour.
 *		
 *		Olaf Erb	:	irtt wasn't being copied right.
 *		Bjorn Ekwall	:	Kerneld route support.
 *		Alan Cox	:	Multicast fixed (I hope)
 * 		Pavel Krauz	:	Limited broadcast fixed
 *		Mike McLagan	:	Routing by source
 *	Alexey Kuznetsov	:	End of old history. Splitted to fib.c and
 *					route.c and rewritten from scratch.
 *		Andi Kleen	:	Load-limit warning messages.
 *	Vitaly E. Lavrov	:	Transparent proxy revived after year coma.
 *	Vitaly E. Lavrov	:	Race condition in ip_route_input_slow.
 *	Tobias Ringstrom	:	Uninitialized res.type in ip_route_output_slow.
 *	Vladimir V. Ivanov	:	IP rule info (flowid) is really useful.
 *		Marc Boucher	:	routing by fwmark
 *
 *		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.
 */

#include <linux/config.h>
#include <asm/uaccess.h>
#include <asm/system.h>
#include <asm/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/proc_fs.h>
#include <linux/init.h>
#include <linux/skbuff.h>
#include <linux/rtnetlink.h>
#include <linux/inetdevice.h>
#include <linux/igmp.h>
#include <linux/pkt_sched.h>
#include <linux/mroute.h>
#include <net/protocol.h>
#include <net/ip.h>
#include <net/route.h>
#include <net/sock.h>
#include <net/ip_fib.h>
#include <net/arp.h>
#include <net/tcp.h>
#include <net/icmp.h>
#ifdef CONFIG_SYSCTL
#include <linux/sysctl.h>
#endif

#define IP_MAX_MTU	0xFFF0

#define RT_GC_TIMEOUT (300*HZ)

int ip_rt_min_delay = 2*HZ;
int ip_rt_max_delay = 10*HZ;
int ip_rt_gc_thresh = RT_HASH_DIVISOR;
int ip_rt_max_size = RT_HASH_DIVISOR*16;
int ip_rt_gc_timeout = RT_GC_TIMEOUT;
int ip_rt_gc_interval = 60*HZ;
int ip_rt_gc_min_interval = 5*HZ;
int ip_rt_redirect_number = 9;
int ip_rt_redirect_load = HZ/50;
int ip_rt_redirect_silence = ((HZ/50) << (9+1));
int ip_rt_error_cost = HZ;
int ip_rt_error_burst = 5*HZ;
int ip_rt_gc_elasticity = 8;
int ip_rt_mtu_expires = 10*60*HZ;

static unsigned long rt_deadline = 0;

#define RTprint(a...)	printk(KERN_DEBUG a)

static void rt_run_flush(unsigned long dummy);

static struct timer_list rt_flush_timer =
	{ NULL, NULL, 0, 0L, rt_run_flush };
static struct timer_list rt_periodic_timer =
	{ NULL, NULL, 0, 0L, NULL };

/*
 *	Interface to generic destination cache.
 */

static struct dst_entry * ipv4_dst_check(struct dst_entry * dst, u32);
static struct dst_entry * ipv4_dst_reroute(struct dst_entry * dst,
					   struct sk_buff *);
static struct dst_entry * ipv4_negative_advice(struct dst_entry *);
static void		  ipv4_link_failure(struct sk_buff *skb);
static int rt_garbage_collect(void);


struct dst_ops ipv4_dst_ops =
{
	AF_INET,
	__constant_htons(ETH_P_IP),
	RT_HASH_DIVISOR,

	rt_garbage_collect,
	ipv4_dst_check,
	ipv4_dst_reroute,
	NULL,
	ipv4_negative_advice,
	ipv4_link_failure,
};

__u8 ip_tos2prio[16] = {
	TC_PRIO_BESTEFFORT,
	TC_PRIO_FILLER,
	TC_PRIO_BESTEFFORT,
	TC_PRIO_FILLER,
	TC_PRIO_BULK,
	TC_PRIO_FILLER,
	TC_PRIO_BULK,
	TC_PRIO_FILLER,
	TC_PRIO_INTERACTIVE,
	TC_PRIO_FILLER,
	TC_PRIO_INTERACTIVE,
	TC_PRIO_FILLER,
	TC_PRIO_INTERACTIVE_BULK,
	TC_PRIO_FILLER,
	TC_PRIO_INTERACTIVE_BULK,
	TC_PRIO_FILLER
};


/*
 * Route cache.
 */

struct rtable 	*rt_hash_table[RT_HASH_DIVISOR];

static int rt_intern_hash(unsigned hash, struct rtable * rth, struct rtable ** res);

static __inline__ unsigned rt_hash_code(u32 daddr, u32 saddr, u8 tos)
{
	unsigned hash = ((daddr&0xF0F0F0F0)>>4)|((daddr&0x0F0F0F0F)<<4);
	hash = hash^saddr^tos;
	hash = hash^(hash>>16);
	return (hash^(hash>>8)) & 0xFF;
}

#ifdef CONFIG_PROC_FS

static int rt_cache_get_info(char *buffer, char **start, off_t offset, int length, int dummy)
{
	int len=0;
	off_t pos=0;
	char temp[129];
	struct rtable *r;
	int i;

	pos = 128;

	if (offset<128)	{
		sprintf(buffer,"%-127s\n", "Iface\tDestination\tGateway \tFlags\t\tRefCnt\tUse\tMetric\tSource\t\tMTU\tWindow\tIRTT\tTOS\tHHRef\tHHUptod\tSpecDst");
		len = 128;
  	}
	
  	
	start_bh_atomic();

	for (i = 0; i<RT_HASH_DIVISOR; i++) {
		for (r = rt_hash_table[i]; r; r = r->u.rt_next) {
			/*
			 *	Spin through entries until we are ready
			 */
			pos += 128;

			if (pos <= offset) {
				len = 0;
				continue;
			}
			sprintf(temp, "%s\t%08lX\t%08lX\t%8X\t%d\t%u\t%d\t%08lX\t%d\t%u\t%u\t%02X\t%d\t%1d\t%08X",
				r->u.dst.dev ? r->u.dst.dev->name : "*",
				(unsigned long)r->rt_dst,
				(unsigned long)r->rt_gateway,
				r->rt_flags,
				atomic_read(&r->u.dst.use),
				atomic_read(&r->u.dst.refcnt),
				0,
				(unsigned long)r->rt_src, (int)r->u.dst.pmtu,
				r->u.dst.window,
				(int)r->u.dst.rtt, r->key.tos,
				r->u.dst.hh ? atomic_read(&r->u.dst.hh->hh_refcnt) : -1,
				r->u.dst.hh ? (r->u.dst.hh->hh_output == dev_queue_xmit) : 0,
				r->rt_spec_dst);
			sprintf(buffer+len,"%-127s\n",temp);
			len += 128;
			if (pos >= offset+length)
				goto done;
		}
        }

done:
	end_bh_atomic();
  	
  	*start = buffer+len-(pos-offset);
  	len = pos-offset;
  	if (len>length)
  		len = length;
  	return len;
}
#endif
  
static __inline__ void rt_free(struct rtable *rt)
{
	dst_free(&rt->u.dst);
}

static __inline__ void rt_drop(struct rtable *rt)
{
	ip_rt_put(rt);
	dst_free(&rt->u.dst);
}

static __inline__ int rt_fast_clean(struct rtable *rth)
{
	/* Kill broadcast/multicast entries very aggresively, if they
	   collide in hash table with more useful entries */
	return ((rth->rt_flags&(RTCF_BROADCAST|RTCF_MULTICAST))
		&& rth->key.iif && rth->u.rt_next);
}

static __inline__ int rt_valuable(struct rtable *rth)
{
	return ((rth->rt_flags&(RTCF_REDIRECTED|RTCF_NOTIFY))
		|| rth->u.dst.expires);
}

static __inline__ int rt_may_expire(struct rtable *rth, int tmo1, int tmo2)
{
	int age;

	if (atomic_read(&rth->u.dst.use))
		return 0;

	if (rth->u.dst.expires && (long)(rth->u.dst.expires - jiffies) <= 0)
		return 1;

	age = jiffies - rth->u.dst.lastuse;
	if (age <= tmo1 && !rt_fast_clean(rth))
		return 0;
	if (age <= tmo2 && rt_valuable(rth))
		return 0;
	return 1;
}

static void rt_check_expire(unsigned long dummy)
{
	int i;
	static int rover;
	struct rtable *rth, **rthp;
	unsigned long now = jiffies;

	for (i=0; i<RT_HASH_DIVISOR/5; i++) {
		unsigned tmo = ip_rt_gc_timeout;

		rover = (rover + 1) & (RT_HASH_DIVISOR-1);
		rthp = &rt_hash_table[rover];

		while ((rth = *rthp) != NULL) {
			if (rth->u.dst.expires) {
				/* Entrie is expired even if it is in use */
				if ((long)(now - rth->u.dst.expires) <= 0) {
					tmo >>= 1;
					rthp = &rth->u.rt_next;
					continue;
				}
			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
				tmo >>= 1;
				rthp = &rth->u.rt_next;
				continue;
			}

			/*
			 * Cleanup aged off entries.
			 */
			*rthp = rth->u.rt_next;
			rt_free(rth);
		}

		/* Fallback loop breaker. */
		if ((jiffies - now) > 0)
			break;
	}
	rt_periodic_timer.expires = now + ip_rt_gc_interval;
	add_timer(&rt_periodic_timer);
}

static void rt_run_flush(unsigned long dummy)
{
	int i;
	struct rtable * rth, * next;

	rt_deadline = 0;

	start_bh_atomic();
	for (i=0; i<RT_HASH_DIVISOR; i++) {
		if ((rth = xchg(&rt_hash_table[i], NULL)) == NULL)
			continue;
		end_bh_atomic();

		for (; rth; rth=next) {
			next = rth->u.rt_next;
			rth->u.rt_next = NULL;
			rt_free(rth);
		}

		start_bh_atomic();
	}
	end_bh_atomic();
}
  
void rt_cache_flush(int delay)
{
	unsigned long now = jiffies;
	int user_mode = !in_interrupt();

	if (delay < 0)
		delay = ip_rt_min_delay;

	start_bh_atomic();

	if (del_timer(&rt_flush_timer) && delay > 0 && rt_deadline) {
		long tmo = (long)(rt_deadline - now);

		/* If flush timer is already running
		   and flush request is not immediate (delay > 0):

		   if deadline is not achieved, prolongate timer to "delay",
		   otherwise fire it at deadline time.
		 */

		if (user_mode && tmo < ip_rt_max_delay-ip_rt_min_delay)
			tmo = 0;
		
		if (delay > tmo)
			delay = tmo;
	}

	if (delay <= 0) {
		end_bh_atomic();
		rt_run_flush(0);
		return;
	}

	if (rt_deadline == 0)
		rt_deadline = now + ip_rt_max_delay;

	rt_flush_timer.expires = now + delay;
	add_timer(&rt_flush_timer);
	end_bh_atomic();
}

/*
   Short description of GC goals.

   We want to build algorithm, which will keep routing cache
   at some equilibrium point, when number of aged off entries
   is kept approximately equal to newly generated ones.

   Current expiration strength is variable "expire".
   We try to adjust it dynamically, so that if networking
   is idle expires is large enough to keep enough of warm entries,
   and when load increases it reduces to limit cache size.
 */

static int rt_garbage_collect(void)
{
	static unsigned expire = RT_GC_TIMEOUT;
	static unsigned long last_gc;
	static int rover;
	static int equilibrium;
	struct rtable *rth, **rthp;
	unsigned long now = jiffies;
	int goal;

	/*
	 * Garbage collection is pretty expensive,
	 * do not make it too frequently.
	 */
	if (now - last_gc < ip_rt_gc_min_interval &&
	    atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
		return 0;

	/* Calculate number of entries, which we want to expire now. */
	goal = atomic_read(&ipv4_dst_ops.entries) - RT_HASH_DIVISOR*ip_rt_gc_elasticity;
	if (goal <= 0) {
		if (equilibrium < ipv4_dst_ops.gc_thresh)
			equilibrium = ipv4_dst_ops.gc_thresh;
		goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
		if (goal > 0) {
			equilibrium += min(goal/2, RT_HASH_DIVISOR);
			goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
		}
	} else {
		/* We are in dangerous area. Try to reduce cache really
		 * aggressively.
		 */
		goal = max(goal/2, RT_HASH_DIVISOR);
		equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
	}

	if (now - last_gc >= ip_rt_gc_min_interval)
		last_gc = now;

	if (goal <= 0) {
		equilibrium += goal;
		goto work_done;
	}

	do {
		int i, k;

		start_bh_atomic();
		for (i=0, k=rover; i<RT_HASH_DIVISOR; i++) {
			unsigned tmo = expire;

			k = (k + 1) & (RT_HASH_DIVISOR-1);
			rthp = &rt_hash_table[k];
			while ((rth = *rthp) != NULL) {
				if (!rt_may_expire(rth, tmo, expire)) {
					tmo >>= 1;
					rthp = &rth->u.rt_next;
					continue;
				}
				*rthp = rth->u.rt_next;
				rth->u.rt_next = NULL;
				rt_free(rth);
				goal--;
			}
			if (goal <= 0)
				break;
		}
		rover = k;
		end_bh_atomic();

		if (goal <= 0)
			goto work_done;

		/* Goal is not achieved. We stop process if:

		   - if expire reduced to zero. Otherwise, expire is halfed.
		   - if table is not full.
		   - if we are called from interrupt.
		   - jiffies check is just fallback/debug loop breaker.
		     We will not spin here for long time in any case.
		 */

		if (expire == 0)
			break;

		expire >>= 1;
#if RT_CACHE_DEBUG >= 2
		printk(KERN_DEBUG "expire>> %u %d %d %d\n", expire, atomic_read(&ipv4_dst_ops.entries), goal, i);
#endif

		if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
			return 0;
	} while (!in_interrupt() && jiffies - now < 1);

	if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
		return 0;
	if (net_ratelimit())
		printk("dst cache overflow\n");
	return 1;