route.c 65.7 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7
/*
 * 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.
 *
Linus Torvalds's avatar
Linus Torvalds committed
8
 * Version:	$Id: route.c,v 1.103 2002/01/12 07:44:09 davem Exp $
Linus Torvalds's avatar
Linus Torvalds committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
 *
 * Authors:	Ross Biro, <bir7@leland.Stanford.Edu>
 *		Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
 *		Alan Cox, <gw4pts@gw4pts.ampr.org>
 *		Linus Torvalds, <Linus.Torvalds@helsinki.fi>
 *		Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 *
 * Fixes:
 *		Alan Cox	:	Verify area fixes.
 *		Alan Cox	:	cli() protects routing changes
 *		Rui Oliveira	:	ICMP routing table updates
 *		(rco@di.uminho.pt)	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
Linus Torvalds's avatar
Linus Torvalds committed
55
 *	Robert Olsson		:	Added rt_cache statistics
56
 *	Arnaldo C. Melo		:	Convert proc stuff to seq_file
Linus Torvalds's avatar
Linus Torvalds committed
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
 *
 *		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 <linux/netfilter_ipv4.h>
#include <linux/random.h>
89
#include <linux/rcupdate.h>
Linus Torvalds's avatar
Linus Torvalds committed
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
#include <net/protocol.h>
#include <net/ip.h>
#include <net/route.h>
#include <net/inetpeer.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)

Linus Torvalds's avatar
Linus Torvalds committed
107 108
int ip_rt_min_delay		= 2 * HZ;
int ip_rt_max_delay		= 10 * HZ;
Linus Torvalds's avatar
Linus Torvalds committed
109
int ip_rt_max_size;
Linus Torvalds's avatar
Linus Torvalds committed
110 111 112 113 114 115 116 117 118 119 120 121
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;
int ip_rt_min_pmtu		= 512 + 20 + 20;
int ip_rt_min_advmss		= 256;
Linus Torvalds's avatar
Linus Torvalds committed
122 123 124 125 126 127 128 129 130 131 132 133

static unsigned long rt_deadline;

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

static struct timer_list rt_flush_timer;
static struct timer_list rt_periodic_timer;

/*
 *	Interface to generic destination cache.
 */

Linus Torvalds's avatar
Linus Torvalds committed
134 135 136 137
static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie);
static void		 ipv4_dst_destroy(struct dst_entry *dst);
static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst);
static void		 ipv4_link_failure(struct sk_buff *skb);
138
static void		 ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu);
Linus Torvalds's avatar
Linus Torvalds committed
139 140 141
static int rt_garbage_collect(void);


Linus Torvalds's avatar
Linus Torvalds committed
142
struct dst_ops ipv4_dst_ops = {
143 144 145 146 147 148 149
	.family =		AF_INET,
	.protocol =		__constant_htons(ETH_P_IP),
	.gc =			rt_garbage_collect,
	.check =		ipv4_dst_check,
	.destroy =		ipv4_dst_destroy,
	.negative_advice =	ipv4_negative_advice,
	.link_failure =		ipv4_link_failure,
150
	.update_pmtu =		ip_rt_update_pmtu,
151
	.entry_size =		sizeof(struct rtable),
Linus Torvalds's avatar
Linus Torvalds committed
152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
};

#define ECN_OR_COST(class)	TC_PRIO_##class

__u8 ip_tos2prio[16] = {
	TC_PRIO_BESTEFFORT,
	ECN_OR_COST(FILLER),
	TC_PRIO_BESTEFFORT,
	ECN_OR_COST(BESTEFFORT),
	TC_PRIO_BULK,
	ECN_OR_COST(BULK),
	TC_PRIO_BULK,
	ECN_OR_COST(BULK),
	TC_PRIO_INTERACTIVE,
	ECN_OR_COST(INTERACTIVE),
	TC_PRIO_INTERACTIVE,
	ECN_OR_COST(INTERACTIVE),
	TC_PRIO_INTERACTIVE_BULK,
	ECN_OR_COST(INTERACTIVE_BULK),
	TC_PRIO_INTERACTIVE_BULK,
	ECN_OR_COST(INTERACTIVE_BULK)
};


/*
 * Route cache.
 */

/* The locking scheme is rather straight forward:
 *
182
 * 1) Read-Copy Update protects the buckets of the central route hash.
Linus Torvalds's avatar
Linus Torvalds committed
183 184 185 186 187 188 189 190 191
 * 2) Only writers remove entries, and they hold the lock
 *    as they look at rtable reference counts.
 * 3) Only readers acquire references to rtable entries,
 *    they do so with atomic increments and with the
 *    lock held.
 */

struct rt_hash_bucket {
	struct rtable	*chain;
192
	spinlock_t	lock;
Linus Torvalds's avatar
Linus Torvalds committed
193 194 195 196 197 198
} __attribute__((__aligned__(8)));

static struct rt_hash_bucket 	*rt_hash_table;
static unsigned			rt_hash_mask;
static int			rt_hash_log;

Linus Torvalds's avatar
Linus Torvalds committed
199 200
struct rt_cache_stat rt_cache_stat[NR_CPUS];

Linus Torvalds's avatar
Linus Torvalds committed
201 202
static int rt_intern_hash(unsigned hash, struct rtable *rth,
				struct rtable **res);
Linus Torvalds's avatar
Linus Torvalds committed
203 204 205

static __inline__ unsigned rt_hash_code(u32 daddr, u32 saddr, u8 tos)
{
Linus Torvalds's avatar
Linus Torvalds committed
206 207 208 209 210
	unsigned hash = ((daddr & 0xF0F0F0F0) >> 4) |
			((daddr & 0x0F0F0F0F) << 4);
	hash ^= saddr ^ tos;
	hash ^= (hash >> 16);
	return (hash ^ (hash >> 8)) & rt_hash_mask;
Linus Torvalds's avatar
Linus Torvalds committed
211 212
}

213 214 215 216 217 218
#ifdef CONFIG_PROC_FS
struct rt_cache_iter_state {
	int bucket;
};

static struct rtable *rt_cache_get_first(struct seq_file *seq)
Linus Torvalds's avatar
Linus Torvalds committed
219
{
220 221
	struct rtable *r = NULL;
	struct rt_cache_iter_state *st = seq->private;
Linus Torvalds's avatar
Linus Torvalds committed
222

223
	for (st->bucket = rt_hash_mask; st->bucket >= 0; --st->bucket) {
224
		rcu_read_lock();
225 226 227
		r = rt_hash_table[st->bucket].chain;
		if (r)
			break;
228
		rcu_read_unlock();
229 230 231
	}
	return r;
}
Linus Torvalds's avatar
Linus Torvalds committed
232

233 234 235
static struct rtable *rt_cache_get_next(struct seq_file *seq, struct rtable *r)
{
	struct rt_cache_iter_state *st = seq->private;
Linus Torvalds's avatar
Linus Torvalds committed
236

237
	read_barrier_depends();
238 239
	r = r->u.rt_next;
	while (!r) {
240
		rcu_read_unlock();
241 242
		if (--st->bucket < 0)
			break;
243
		rcu_read_lock();
244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
		r = rt_hash_table[st->bucket].chain;
	}
	return r;
}

static struct rtable *rt_cache_get_idx(struct seq_file *seq, loff_t pos)
{
	struct rtable *r = rt_cache_get_first(seq);

	if (r)
		while (pos && (r = rt_cache_get_next(seq, r)))
			--pos;
	return pos ? NULL : r;
}

static void *rt_cache_seq_start(struct seq_file *seq, loff_t *pos)
{
	return *pos ? rt_cache_get_idx(seq, *pos) : (void *)1;
}

static void *rt_cache_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{
	struct rtable *r = NULL;

	if (v == (void *)1)
		r = rt_cache_get_first(seq);
	else
		r = rt_cache_get_next(seq, v);
	++*pos;
	return r;
}

static void rt_cache_seq_stop(struct seq_file *seq, void *v)
{
	if (v && v != (void *)1) {
		struct rt_cache_iter_state *st = seq->private;

281
		rcu_read_unlock();
282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
	}
}

static int rt_cache_seq_show(struct seq_file *seq, void *v)
{
	if (v == (void *)1)
		seq_printf(seq, "%-127s\n",
			   "Iface\tDestination\tGateway \tFlags\t\tRefCnt\tUse\t"
			   "Metric\tSource\t\tMTU\tWindow\tIRTT\tTOS\tHHRef\t"
			   "HHUptod\tSpecDst");
	else {
		struct rtable *r = v;
		char temp[256];

		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.__refcnt),
			r->u.dst.__use, 0, (unsigned long)r->rt_src,
			(dst_metric(&r->u.dst, RTAX_ADVMSS) ?
			     (int)dst_metric(&r->u.dst, RTAX_ADVMSS) + 40 : 0),
			dst_metric(&r->u.dst, RTAX_WINDOW),
			(int)((dst_metric(&r->u.dst, RTAX_RTT) >> 3) +
			      dst_metric(&r->u.dst, RTAX_RTTVAR)),
			r->fl.fl4_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);
		seq_printf(seq, "%-127s\n", temp);
        }
  	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
315
}
Linus Torvalds's avatar
Linus Torvalds committed
316 317 318 319

static int rt_cache_stat_get_info(char *buffer, char **start, off_t offset, int length)
{
	unsigned int dst_entries = atomic_read(&ipv4_dst_ops.entries);
320
	int i;
Linus Torvalds's avatar
Linus Torvalds committed
321 322
	int len = 0;

323
	for (i = 0; i < NR_CPUS; i++) {
324
		len += sprintf(buffer+len, "%08x  %08x %08x %08x %08x %08x %08x %08x  %08x %08x %08x %08x %08x %08x %08x \n",
Linus Torvalds's avatar
Linus Torvalds committed
325 326 327 328 329 330 331 332 333 334 335
			       dst_entries,		       
			       rt_cache_stat[i].in_hit,
			       rt_cache_stat[i].in_slow_tot,
			       rt_cache_stat[i].in_slow_mc,
			       rt_cache_stat[i].in_no_route,
			       rt_cache_stat[i].in_brd,
			       rt_cache_stat[i].in_martian_dst,
			       rt_cache_stat[i].in_martian_src,

			       rt_cache_stat[i].out_hit,
			       rt_cache_stat[i].out_slow_tot,
336 337 338 339 340 341 342
			       rt_cache_stat[i].out_slow_mc, 

			       rt_cache_stat[i].gc_total,
			       rt_cache_stat[i].gc_ignored,
			       rt_cache_stat[i].gc_goal_miss,
			       rt_cache_stat[i].gc_dst_overflow

Linus Torvalds's avatar
Linus Torvalds committed
343 344 345 346 347 348 349 350 351 352 353 354
			);
	}
	len -= offset;

	if (len > length)
		len = length;
	if (len < 0)
		len = 0;

	*start = buffer + offset;
  	return len;
}
355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407

static struct seq_operations rt_cache_seq_ops = {
	.start  = rt_cache_seq_start,
	.next   = rt_cache_seq_next,
	.stop   = rt_cache_seq_stop,
	.show   = rt_cache_seq_show,
};

static int rt_cache_seq_open(struct inode *inode, struct file *file)
{
	struct seq_file *seq;
	int rc = -ENOMEM;
	struct rt_cache_iter_state *s = kmalloc(sizeof(*s), GFP_KERNEL);

	if (!s)
		goto out;
	rc = seq_open(file, &rt_cache_seq_ops);
	if (rc)
		goto out_kfree;
	seq          = file->private_data;
	seq->private = s;
	memset(s, 0, sizeof(*s));
out:
	return rc;
out_kfree:
	kfree(s);
	goto out;
}

static struct file_operations rt_cache_seq_fops = {
	.open	 = rt_cache_seq_open,
	.read	 = seq_read,
	.llseek	 = seq_lseek,
	.release = ip_seq_release,
};

int __init rt_cache_proc_init(void)
{
	int rc = 0;
	struct proc_dir_entry *p = create_proc_entry("rt_cache", S_IRUGO,
						     proc_net);
	if (p)
		p->proc_fops = &rt_cache_seq_fops;
	else
		rc = -ENOMEM;
	return rc;
}

void __init rt_cache_proc_exit(void)
{
	remove_proc_entry("rt_cache", proc_net);
}
#endif /* CONFIG_PROC_FS */
Linus Torvalds's avatar
Linus Torvalds committed
408 409 410
  
static __inline__ void rt_free(struct rtable *rt)
{
411
	call_rcu(&rt->u.dst.rcu_head, (void (*)(void *))dst_free, &rt->u.dst);
Linus Torvalds's avatar
Linus Torvalds committed
412 413 414 415 416
}

static __inline__ void rt_drop(struct rtable *rt)
{
	ip_rt_put(rt);
417
	call_rcu(&rt->u.dst.rcu_head, (void (*)(void *))dst_free, &rt->u.dst);
Linus Torvalds's avatar
Linus Torvalds committed
418 419 420 421 422 423
}

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 */
Linus Torvalds's avatar
Linus Torvalds committed
424
	return (rth->rt_flags & (RTCF_BROADCAST | RTCF_MULTICAST)) &&
425
		rth->fl.iif && rth->u.rt_next;
Linus Torvalds's avatar
Linus Torvalds committed
426 427 428 429
}

static __inline__ int rt_valuable(struct rtable *rth)
{
Linus Torvalds's avatar
Linus Torvalds committed
430 431
	return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) ||
		rth->u.dst.expires;
Linus Torvalds's avatar
Linus Torvalds committed
432 433 434 435 436
}

static __inline__ int rt_may_expire(struct rtable *rth, int tmo1, int tmo2)
{
	int age;
Linus Torvalds's avatar
Linus Torvalds committed
437
	int ret = 0;
Linus Torvalds's avatar
Linus Torvalds committed
438 439

	if (atomic_read(&rth->u.dst.__refcnt))
Linus Torvalds's avatar
Linus Torvalds committed
440
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
441

Linus Torvalds's avatar
Linus Torvalds committed
442
	ret = 1;
Linus Torvalds's avatar
Linus Torvalds committed
443
	if (rth->u.dst.expires && (long)(rth->u.dst.expires - jiffies) <= 0)
Linus Torvalds's avatar
Linus Torvalds committed
444
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
445 446

	age = jiffies - rth->u.dst.lastuse;
Linus Torvalds's avatar
Linus Torvalds committed
447 448 449 450 451 452
	ret = 0;
	if ((age <= tmo1 && !rt_fast_clean(rth)) ||
	    (age <= tmo2 && rt_valuable(rth)))
		goto out;
	ret = 1;
out:	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
453 454 455 456 457 458
}

/* This runs via a timer and thus is always in BH context. */
static void SMP_TIMER_NAME(rt_check_expire)(unsigned long dummy)
{
	static int rover;
Linus Torvalds's avatar
Linus Torvalds committed
459
	int i = rover, t;
Linus Torvalds's avatar
Linus Torvalds committed
460 461 462
	struct rtable *rth, **rthp;
	unsigned long now = jiffies;

Linus Torvalds's avatar
Linus Torvalds committed
463 464
	for (t = ip_rt_gc_interval << rt_hash_log; t >= 0;
	     t -= ip_rt_gc_timeout) {
Linus Torvalds's avatar
Linus Torvalds committed
465 466 467 468 469
		unsigned tmo = ip_rt_gc_timeout;

		i = (i + 1) & rt_hash_mask;
		rthp = &rt_hash_table[i].chain;

470
		spin_lock(&rt_hash_table[i].lock);
Linus Torvalds's avatar
Linus Torvalds committed
471 472 473 474 475 476 477 478 479 480 481 482 483 484
		while ((rth = *rthp) != NULL) {
			if (rth->u.dst.expires) {
				/* Entry 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;
			}

Linus Torvalds's avatar
Linus Torvalds committed
485
			/* Cleanup aged off entries. */
Linus Torvalds's avatar
Linus Torvalds committed
486 487 488
			*rthp = rth->u.rt_next;
			rt_free(rth);
		}
489
		spin_unlock(&rt_hash_table[i].lock);
Linus Torvalds's avatar
Linus Torvalds committed
490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506

		/* Fallback loop breaker. */
		if ((jiffies - now) > 0)
			break;
	}
	rover = i;
	mod_timer(&rt_periodic_timer, now + ip_rt_gc_interval);
}

SMP_TIMER_DEFINE(rt_check_expire, rt_gc_task);

/* This can run from both BH and non-BH contexts, the latter
 * in the case of a forced flush event.
 */
static void SMP_TIMER_NAME(rt_run_flush)(unsigned long dummy)
{
	int i;
Linus Torvalds's avatar
Linus Torvalds committed
507
	struct rtable *rth, *next;
Linus Torvalds's avatar
Linus Torvalds committed
508 509 510

	rt_deadline = 0;

Linus Torvalds's avatar
Linus Torvalds committed
511
	for (i = rt_hash_mask; i >= 0; i--) {
512
		spin_lock_bh(&rt_hash_table[i].lock);
Linus Torvalds's avatar
Linus Torvalds committed
513 514 515
		rth = rt_hash_table[i].chain;
		if (rth)
			rt_hash_table[i].chain = NULL;
516
		spin_unlock_bh(&rt_hash_table[i].lock);
Linus Torvalds's avatar
Linus Torvalds committed
517

Linus Torvalds's avatar
Linus Torvalds committed
518
		for (; rth; rth = next) {
Linus Torvalds's avatar
Linus Torvalds committed
519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595
			next = rth->u.rt_next;
			rt_free(rth);
		}
	}
}

SMP_TIMER_DEFINE(rt_run_flush, rt_cache_flush_task);
  
static spinlock_t rt_flush_lock = SPIN_LOCK_UNLOCKED;

void rt_cache_flush(int delay)
{
	unsigned long now = jiffies;
	int user_mode = !in_softirq();

	if (delay < 0)
		delay = ip_rt_min_delay;

	spin_lock_bh(&rt_flush_lock);

	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) {
		spin_unlock_bh(&rt_flush_lock);
		SMP_TIMER_NAME(rt_run_flush)(0);
		return;
	}

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

	mod_timer(&rt_flush_timer, now+delay);
	spin_unlock_bh(&rt_flush_lock);
}

/*
   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.
	 */
596 597 598

	rt_cache_stat[smp_processor_id()].gc_total++;

Linus Torvalds's avatar
Linus Torvalds committed
599
	if (now - last_gc < ip_rt_gc_min_interval &&
600 601
	    atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size) {
		rt_cache_stat[smp_processor_id()].gc_ignored++;
Linus Torvalds's avatar
Linus Torvalds committed
602
		goto out;
603
	}
Linus Torvalds's avatar
Linus Torvalds committed
604 605

	/* Calculate number of entries, which we want to expire now. */
Linus Torvalds's avatar
Linus Torvalds committed
606 607
	goal = atomic_read(&ipv4_dst_ops.entries) -
		(ip_rt_gc_elasticity << rt_hash_log);
Linus Torvalds's avatar
Linus Torvalds committed
608 609 610 611 612
	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) {
Linus Torvalds's avatar
Linus Torvalds committed
613
			equilibrium += min_t(unsigned int, goal / 2, rt_hash_mask + 1);
Linus Torvalds's avatar
Linus Torvalds committed
614 615 616 617 618 619
			goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
		}
	} else {
		/* We are in dangerous area. Try to reduce cache really
		 * aggressively.
		 */
Linus Torvalds's avatar
Linus Torvalds committed
620
		goal = max_t(unsigned int, goal / 2, rt_hash_mask + 1);
Linus Torvalds's avatar
Linus Torvalds committed
621 622 623 624 625 626 627 628 629 630 631 632 633 634
		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;

Linus Torvalds's avatar
Linus Torvalds committed
635
		for (i = rt_hash_mask, k = rover; i >= 0; i--) {
Linus Torvalds's avatar
Linus Torvalds committed
636 637 638 639
			unsigned tmo = expire;

			k = (k + 1) & rt_hash_mask;
			rthp = &rt_hash_table[k].chain;
640
			spin_lock_bh(&rt_hash_table[k].lock);
Linus Torvalds's avatar
Linus Torvalds committed
641 642 643 644 645 646 647 648 649 650
			while ((rth = *rthp) != NULL) {
				if (!rt_may_expire(rth, tmo, expire)) {
					tmo >>= 1;
					rthp = &rth->u.rt_next;
					continue;
				}
				*rthp = rth->u.rt_next;
				rt_free(rth);
				goal--;
			}
651
			spin_unlock_bh(&rt_hash_table[k].lock);
Linus Torvalds's avatar
Linus Torvalds committed
652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668
			if (goal <= 0)
				break;
		}
		rover = k;

		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.
		 */

669 670
		rt_cache_stat[smp_processor_id()].gc_goal_miss++;

Linus Torvalds's avatar
Linus Torvalds committed
671 672 673 674 675
		if (expire == 0)
			break;

		expire >>= 1;
#if RT_CACHE_DEBUG >= 2
Linus Torvalds's avatar
Linus Torvalds committed
676 677
		printk(KERN_DEBUG "expire>> %u %d %d %d\n", expire,
				atomic_read(&ipv4_dst_ops.entries), goal, i);
Linus Torvalds's avatar
Linus Torvalds committed
678 679 680
#endif

		if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
Linus Torvalds's avatar
Linus Torvalds committed
681
			goto out;
Linus Torvalds's avatar
Linus Torvalds committed
682 683 684
	} while (!in_softirq() && jiffies - now < 1);

	if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
Linus Torvalds's avatar
Linus Torvalds committed
685
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
686
	if (net_ratelimit())
687
		printk(KERN_WARNING "dst cache overflow\n");
688
	rt_cache_stat[smp_processor_id()].gc_dst_overflow++;
Linus Torvalds's avatar
Linus Torvalds committed
689 690 691 692 693 694 695 696
	return 1;

work_done:
	expire += ip_rt_gc_min_interval;
	if (expire > ip_rt_gc_timeout ||
	    atomic_read(&ipv4_dst_ops.entries) < ipv4_dst_ops.gc_thresh)
		expire = ip_rt_gc_timeout;
#if RT_CACHE_DEBUG >= 2
Linus Torvalds's avatar
Linus Torvalds committed
697 698
	printk(KERN_DEBUG "expire++ %u %d %d %d\n", expire,
			atomic_read(&ipv4_dst_ops.entries), goal, rover);
Linus Torvalds's avatar
Linus Torvalds committed
699
#endif
Linus Torvalds's avatar
Linus Torvalds committed
700
out:	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
701 702
}

703 704 705 706 707 708 709
static inline int compare_keys(struct flowi *fl1, struct flowi *fl2)
{
	return memcmp(&fl1->nl_u.ip4_u, &fl2->nl_u.ip4_u, sizeof(fl1->nl_u.ip4_u)) == 0 &&
	       fl1->oif     == fl2->oif &&
	       fl1->iif     == fl2->iif;
}

Linus Torvalds's avatar
Linus Torvalds committed
710
static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
Linus Torvalds's avatar
Linus Torvalds committed
711 712 713 714 715 716 717 718
{
	struct rtable	*rth, **rthp;
	unsigned long	now = jiffies;
	int attempts = !in_softirq();

restart:
	rthp = &rt_hash_table[hash].chain;

719
	spin_lock_bh(&rt_hash_table[hash].lock);
Linus Torvalds's avatar
Linus Torvalds committed
720
	while ((rth = *rthp) != NULL) {
721
		if (compare_keys(&rth->fl, &rt->fl)) {
Linus Torvalds's avatar
Linus Torvalds committed
722 723 724 725 726 727 728 729
			/* Put it first */
			*rthp = rth->u.rt_next;
			rth->u.rt_next = rt_hash_table[hash].chain;
			rt_hash_table[hash].chain = rth;

			rth->u.dst.__use++;
			dst_hold(&rth->u.dst);
			rth->u.dst.lastuse = now;
730
			spin_unlock_bh(&rt_hash_table[hash].lock);
Linus Torvalds's avatar
Linus Torvalds committed
731 732 733 734 735 736 737 738 739 740 741 742

			rt_drop(rt);
			*rp = rth;
			return 0;
		}

		rthp = &rth->u.rt_next;
	}

	/* Try to bind route to arp only if it is output
	   route or unicast forwarding path.
	 */
743
	if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
Linus Torvalds's avatar
Linus Torvalds committed
744 745
		int err = arp_bind_neighbour(&rt->u.dst);
		if (err) {
746
			spin_unlock_bh(&rt_hash_table[hash].lock);
Linus Torvalds's avatar
Linus Torvalds committed
747 748 749 750 751 752 753 754 755 756 757 758 759

			if (err != -ENOBUFS) {
				rt_drop(rt);
				return err;
			}

			/* Neighbour tables are full and nothing
			   can be released. Try to shrink route cache,
			   it is most likely it holds some neighbour records.
			 */
			if (attempts-- > 0) {
				int saved_elasticity = ip_rt_gc_elasticity;
				int saved_int = ip_rt_gc_min_interval;
Linus Torvalds's avatar
Linus Torvalds committed
760 761
				ip_rt_gc_elasticity	= 1;
				ip_rt_gc_min_interval	= 0;
Linus Torvalds's avatar
Linus Torvalds committed
762
				rt_garbage_collect();
Linus Torvalds's avatar
Linus Torvalds committed
763 764
				ip_rt_gc_min_interval	= saved_int;
				ip_rt_gc_elasticity	= saved_elasticity;
Linus Torvalds's avatar
Linus Torvalds committed
765 766 767 768
				goto restart;
			}

			if (net_ratelimit())
769
				printk(KERN_WARNING "Neighbour table overflow.\n");
Linus Torvalds's avatar
Linus Torvalds committed
770 771 772 773 774 775 776 777
			rt_drop(rt);
			return -ENOBUFS;
		}
	}

	rt->u.rt_next = rt_hash_table[hash].chain;
#if RT_CACHE_DEBUG >= 2
	if (rt->u.rt_next) {
Linus Torvalds's avatar
Linus Torvalds committed
778
		struct rtable *trt;
779 780
		printk(KERN_DEBUG "rt_cache @%02x: %u.%u.%u.%u", hash,
		       NIPQUAD(rt->rt_dst));
Linus Torvalds's avatar
Linus Torvalds committed
781
		for (trt = rt->u.rt_next; trt; trt = trt->u.rt_next)
Linus Torvalds's avatar
Linus Torvalds committed
782 783 784 785 786
			printk(" . %u.%u.%u.%u", NIPQUAD(trt->rt_dst));
		printk("\n");
	}
#endif
	rt_hash_table[hash].chain = rt;
787
	spin_unlock_bh(&rt_hash_table[hash].lock);
Linus Torvalds's avatar
Linus Torvalds committed
788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823
	*rp = rt;
	return 0;
}

void rt_bind_peer(struct rtable *rt, int create)
{
	static spinlock_t rt_peer_lock = SPIN_LOCK_UNLOCKED;
	struct inet_peer *peer;

	peer = inet_getpeer(rt->rt_dst, create);

	spin_lock_bh(&rt_peer_lock);
	if (rt->peer == NULL) {
		rt->peer = peer;
		peer = NULL;
	}
	spin_unlock_bh(&rt_peer_lock);
	if (peer)
		inet_putpeer(peer);
}

/*
 * Peer allocation may fail only in serious out-of-memory conditions.  However
 * we still can generate some output.
 * Random ID selection looks a bit dangerous because we have no chances to
 * select ID being unique in a reasonable period of time.
 * But broken packet identifier may be better than no packet at all.
 */
static void ip_select_fb_ident(struct iphdr *iph)
{
	static spinlock_t ip_fb_id_lock = SPIN_LOCK_UNLOCKED;
	static u32 ip_fallback_id;
	u32 salt;

	spin_lock_bh(&ip_fb_id_lock);
	salt = secure_ip_id(ip_fallback_id ^ iph->daddr);
Linus Torvalds's avatar
Linus Torvalds committed
824
	iph->id = htons(salt & 0xFFFF);
Linus Torvalds's avatar
Linus Torvalds committed
825 826 827 828
	ip_fallback_id = salt;
	spin_unlock_bh(&ip_fb_id_lock);
}

829
void __ip_select_ident(struct iphdr *iph, struct dst_entry *dst, int more)
Linus Torvalds's avatar
Linus Torvalds committed
830 831 832 833 834 835 836 837 838 839 840
{
	struct rtable *rt = (struct rtable *) dst;

	if (rt) {
		if (rt->peer == NULL)
			rt_bind_peer(rt, 1);

		/* If peer is attached to destination, it is never detached,
		   so that we need not to grab a lock to dereference it.
		 */
		if (rt->peer) {
841
			iph->id = htons(inet_getid(rt->peer, more));
Linus Torvalds's avatar
Linus Torvalds committed
842 843
			return;
		}
Linus Torvalds's avatar
Linus Torvalds committed
844
	} else
Linus Torvalds's avatar
Linus Torvalds committed
845 846 847 848 849 850 851 852 853
		printk(KERN_DEBUG "rt_bind_peer(0) @%p\n", NET_CALLER(iph));

	ip_select_fb_ident(iph);
}

static void rt_del(unsigned hash, struct rtable *rt)
{
	struct rtable **rthp;

854
	spin_lock_bh(&rt_hash_table[hash].lock);
Linus Torvalds's avatar
Linus Torvalds committed
855
	ip_rt_put(rt);
Linus Torvalds's avatar
Linus Torvalds committed
856 857
	for (rthp = &rt_hash_table[hash].chain; *rthp;
	     rthp = &(*rthp)->u.rt_next)
Linus Torvalds's avatar
Linus Torvalds committed
858 859 860 861 862
		if (*rthp == rt) {
			*rthp = rt->u.rt_next;
			rt_free(rt);
			break;
		}
863
	spin_unlock_bh(&rt_hash_table[hash].lock);
Linus Torvalds's avatar
Linus Torvalds committed
864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893
}

void ip_rt_redirect(u32 old_gw, u32 daddr, u32 new_gw,
		    u32 saddr, u8 tos, struct net_device *dev)
{
	int i, k;
	struct in_device *in_dev = in_dev_get(dev);
	struct rtable *rth, **rthp;
	u32  skeys[2] = { saddr, 0 };
	int  ikeys[2] = { dev->ifindex, 0 };

	tos &= IPTOS_RT_MASK;

	if (!in_dev)
		return;

	if (new_gw == old_gw || !IN_DEV_RX_REDIRECTS(in_dev)
	    || MULTICAST(new_gw) || BADCLASS(new_gw) || ZERONET(new_gw))
		goto reject_redirect;

	if (!IN_DEV_SHARED_MEDIA(in_dev)) {
		if (!inet_addr_onlink(in_dev, new_gw, old_gw))
			goto reject_redirect;
		if (IN_DEV_SEC_REDIRECTS(in_dev) && ip_fib_check_default(new_gw, dev))
			goto reject_redirect;
	} else {
		if (inet_addr_type(new_gw) != RTN_UNICAST)
			goto reject_redirect;
	}

Linus Torvalds's avatar
Linus Torvalds committed
894 895 896 897 898
	for (i = 0; i < 2; i++) {
		for (k = 0; k < 2; k++) {
			unsigned hash = rt_hash_code(daddr,
						     skeys[i] ^ (ikeys[k] << 5),
						     tos);
Linus Torvalds's avatar
Linus Torvalds committed
899 900 901

			rthp=&rt_hash_table[hash].chain;

902
			rcu_read_lock();
Linus Torvalds's avatar
Linus Torvalds committed
903
			while ((rth = *rthp) != NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
904 905
				struct rtable *rt;

906
				read_barrier_depends();
907 908 909 910 911
				if (rth->fl.fl4_dst != daddr ||
				    rth->fl.fl4_src != skeys[i] ||
				    rth->fl.fl4_tos != tos ||
				    rth->fl.oif != ikeys[k] ||
				    rth->fl.iif != 0) {
Linus Torvalds's avatar
Linus Torvalds committed
912 913 914 915 916 917 918 919 920 921 922 923
					rthp = &rth->u.rt_next;
					continue;
				}

				if (rth->rt_dst != daddr ||
				    rth->rt_src != saddr ||
				    rth->u.dst.error ||
				    rth->rt_gateway != old_gw ||
				    rth->u.dst.dev != dev)
					break;

				dst_clone(&rth->u.dst);
924
				rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
925 926 927 928 929 930 931 932

				rt = dst_alloc(&ipv4_dst_ops);
				if (rt == NULL) {
					ip_rt_put(rth);
					in_dev_put(in_dev);
					return;
				}

Linus Torvalds's avatar
Linus Torvalds committed
933
				/* Copy all the information. */
Linus Torvalds's avatar
Linus Torvalds committed
934
				*rt = *rth;
935
 				INIT_RCU_HEAD(&rt->u.dst.rcu_head);
Linus Torvalds's avatar
Linus Torvalds committed
936
				rt->u.dst.__use		= 1;
Linus Torvalds's avatar
Linus Torvalds committed
937 938 939
				atomic_set(&rt->u.dst.__refcnt, 1);
				if (rt->u.dst.dev)
					dev_hold(rt->u.dst.dev);
Linus Torvalds's avatar
Linus Torvalds committed
940 941 942 943
				rt->u.dst.lastuse	= jiffies;
				rt->u.dst.neighbour	= NULL;
				rt->u.dst.hh		= NULL;
				rt->u.dst.obsolete	= 0;
Linus Torvalds's avatar
Linus Torvalds committed
944

Linus Torvalds's avatar
Linus Torvalds committed
945
				rt->rt_flags		|= RTCF_REDIRECTED;
Linus Torvalds's avatar
Linus Torvalds committed
946 947

				/* Gateway is different ... */
Linus Torvalds's avatar
Linus Torvalds committed
948
				rt->rt_gateway		= new_gw;
Linus Torvalds's avatar
Linus Torvalds committed
949 950 951 952 953 954 955 956

				/* Redirect received -> path was valid */
				dst_confirm(&rth->u.dst);

				if (rt->peer)
					atomic_inc(&rt->peer->refcnt);

				if (arp_bind_neighbour(&rt->u.dst) ||
Linus Torvalds's avatar
Linus Torvalds committed
957 958
				    !(rt->u.dst.neighbour->nud_state &
					    NUD_VALID)) {
Linus Torvalds's avatar
Linus Torvalds committed
959 960 961 962 963 964 965 966 967 968 969 970
					if (rt->u.dst.neighbour)
						neigh_event_send(rt->u.dst.neighbour, NULL);
					ip_rt_put(rth);
					rt_drop(rt);
					goto do_next;
				}

				rt_del(hash, rth);
				if (!rt_intern_hash(hash, rt, &rt))
					ip_rt_put(rt);
				goto do_next;
			}
971
			rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
972 973 974 975 976 977 978 979 980 981
		do_next:
			;
		}
	}
	in_dev_put(in_dev);
	return;

reject_redirect:
#ifdef CONFIG_IP_ROUTE_VERBOSE
	if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
Linus Torvalds's avatar
Linus Torvalds committed
982 983 984 985
		printk(KERN_INFO "Redirect from %u.%u.%u.%u on %s about "
			"%u.%u.%u.%u ignored.\n"
			"  Advised path = %u.%u.%u.%u -> %u.%u.%u.%u, "
			"tos %02x\n",
Linus Torvalds's avatar
Linus Torvalds committed
986 987 988 989 990 991 992 993 994
		       NIPQUAD(old_gw), dev->name, NIPQUAD(new_gw),
		       NIPQUAD(saddr), NIPQUAD(daddr), tos);
#endif
	in_dev_put(in_dev);
}

static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst)
{
	struct rtable *rt = (struct rtable*)dst;
Linus Torvalds's avatar
Linus Torvalds committed
995
	struct dst_entry *ret = dst;
Linus Torvalds's avatar
Linus Torvalds committed
996

Linus Torvalds's avatar
Linus Torvalds committed
997
	if (rt) {
Linus Torvalds's avatar
Linus Torvalds committed
998 999
		if (dst->obsolete) {
			ip_rt_put(rt);
Linus Torvalds's avatar
Linus Torvalds committed
1000 1001 1002
			ret = NULL;
		} else if ((rt->rt_flags & RTCF_REDIRECTED) ||
			   rt->u.dst.expires) {
1003 1004 1005 1006
			unsigned hash = rt_hash_code(rt->fl.fl4_dst,
						     rt->fl.fl4_src ^
							(rt->fl.oif << 5),
						     rt->fl.fl4_tos);
Linus Torvalds's avatar
Linus Torvalds committed
1007
#if RT_CACHE_DEBUG >= 1
Linus Torvalds's avatar
Linus Torvalds committed
1008 1009
			printk(KERN_DEBUG "ip_rt_advice: redirect to "
					  "%u.%u.%u.%u/%02x dropped\n",
1010
				NIPQUAD(rt->rt_dst), rt->fl.fl4_tos);
Linus Torvalds's avatar
Linus Torvalds committed
1011 1012
#endif
			rt_del(hash, rt);
Linus Torvalds's avatar
Linus Torvalds committed
1013
			ret = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1014 1015
		}
	}
Linus Torvalds's avatar
Linus Torvalds committed
1016
	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062
}

/*
 * Algorithm:
 *	1. The first ip_rt_redirect_number redirects are sent
 *	   with exponential backoff, then we stop sending them at all,
 *	   assuming that the host ignores our redirects.
 *	2. If we did not see packets requiring redirects
 *	   during ip_rt_redirect_silence, we assume that the host
 *	   forgot redirected route and start to send redirects again.
 *
 * This algorithm is much cheaper and more intelligent than dumb load limiting
 * in icmp.c.
 *
 * NOTE. Do not forget to inhibit load limiting for redirects (redundant)
 * and "frag. need" (breaks PMTU discovery) in icmp.c.
 */

void ip_rt_send_redirect(struct sk_buff *skb)
{
	struct rtable *rt = (struct rtable*)skb->dst;
	struct in_device *in_dev = in_dev_get(rt->u.dst.dev);

	if (!in_dev)
		return;

	if (!IN_DEV_TX_REDIRECTS(in_dev))
		goto out;

	/* No redirected packets during ip_rt_redirect_silence;
	 * reset the algorithm.
	 */
	if (jiffies - rt->u.dst.rate_last > ip_rt_redirect_silence)
		rt->u.dst.rate_tokens = 0;

	/* Too many ignored redirects; do not send anything
	 * set u.dst.rate_last to the last seen redirected packet.
	 */
	if (rt->u.dst.rate_tokens >= ip_rt_redirect_number) {
		rt->u.dst.rate_last = jiffies;
		goto out;
	}

	/* Check for load limit; set rate_last to the latest sent
	 * redirect.
	 */
Linus Torvalds's avatar
Linus Torvalds committed
1063 1064
	if (jiffies - rt->u.dst.rate_last >
	    (ip_rt_redirect_load << rt->u.dst.rate_tokens)) {
Linus Torvalds's avatar
Linus Torvalds committed
1065 1066 1067 1068 1069
		icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
		rt->u.dst.rate_last = jiffies;
		++rt->u.dst.rate_tokens;
#ifdef CONFIG_IP_ROUTE_VERBOSE
		if (IN_DEV_LOG_MARTIANS(in_dev) &&
Linus Torvalds's avatar
Linus Torvalds committed
1070 1071 1072 1073
		    rt->u.dst.rate_tokens == ip_rt_redirect_number &&
		    net_ratelimit())
			printk(KERN_WARNING "host %u.%u.%u.%u/if%d ignores "
				"redirects for %u.%u.%u.%u to %u.%u.%u.%u.\n",
Linus Torvalds's avatar
Linus Torvalds committed
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088
				NIPQUAD(rt->rt_src), rt->rt_iif,
				NIPQUAD(rt->rt_dst), NIPQUAD(rt->rt_gateway));
#endif
	}
out:
        in_dev_put(in_dev);
}

static int ip_error(struct sk_buff *skb)
{
	struct rtable *rt = (struct rtable*)skb->dst;
	unsigned long now;
	int code;

	switch (rt->u.dst.error) {
Linus Torvalds's avatar
Linus Torvalds committed
1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
		case EINVAL:
		default:
			goto out;
		case EHOSTUNREACH:
			code = ICMP_HOST_UNREACH;
			break;
		case ENETUNREACH:
			code = ICMP_NET_UNREACH;
			break;
		case EACCES:
			code = ICMP_PKT_FILTERED;
			break;
Linus Torvalds's avatar
Linus Torvalds committed
1101 1102 1103
	}

	now = jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
1104 1105
	rt->u.dst.rate_tokens += now - rt->u.dst.rate_last;
	if (rt->u.dst.rate_tokens > ip_rt_error_burst)
Linus Torvalds's avatar
Linus Torvalds committed
1106 1107 1108 1109 1110 1111 1112
		rt->u.dst.rate_tokens = ip_rt_error_burst;
	rt->u.dst.rate_last = now;
	if (rt->u.dst.rate_tokens >= ip_rt_error_cost) {
		rt->u.dst.rate_tokens -= ip_rt_error_cost;
		icmp_send(skb, ICMP_DEST_UNREACH, code, 0);
	}

Linus Torvalds's avatar
Linus Torvalds committed
1113
out:	kfree_skb(skb);
Linus Torvalds's avatar
Linus Torvalds committed
1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
	return 0;
} 

/*
 *	The last two values are not from the RFC but
 *	are needed for AMPRnet AX.25 paths.
 */

static unsigned short mtu_plateau[] =
{32000, 17914, 8166, 4352, 2002, 1492, 576, 296, 216, 128 };

static __inline__ unsigned short guess_mtu(unsigned short old_mtu)
{
	int i;
	
Linus Torvalds's avatar
Linus Torvalds committed
1129
	for (i = 0; i < sizeof(mtu_plateau) / sizeof(mtu_plateau[0]); i++)
Linus Torvalds's avatar
Linus Torvalds committed
1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147
		if (old_mtu > mtu_plateau[i])
			return mtu_plateau[i];
	return 68;
}

unsigned short ip_rt_frag_needed(struct iphdr *iph, unsigned short new_mtu)
{
	int i;
	unsigned short old_mtu = ntohs(iph->tot_len);
	struct rtable *rth;
	u32  skeys[2] = { iph->saddr, 0, };
	u32  daddr = iph->daddr;
	u8   tos = iph->tos & IPTOS_RT_MASK;
	unsigned short est_mtu = 0;

	if (ipv4_config.no_pmtu_disc)
		return 0;

Linus Torvalds's avatar
Linus Torvalds committed
1148
	for (i = 0; i < 2; i++) {
Linus Torvalds's avatar
Linus Torvalds committed
1149 1150
		unsigned hash = rt_hash_code(daddr, skeys[i], tos);

1151
		rcu_read_lock();
Linus Torvalds's avatar
Linus Torvalds committed
1152 1153
		for (rth = rt_hash_table[hash].chain; rth;
		     rth = rth->u.rt_next) {
1154
			read_barrier_depends();
1155 1156
			if (rth->fl.fl4_dst == daddr &&
			    rth->fl.fl4_src == skeys[i] &&
Linus Torvalds's avatar
Linus Torvalds committed
1157 1158
			    rth->rt_dst  == daddr &&
			    rth->rt_src  == iph->saddr &&
1159 1160
			    rth->fl.fl4_tos == tos &&
			    rth->fl.iif == 0 &&
1161
			    !(dst_metric_locked(&rth->u.dst, RTAX_MTU))) {
Linus Torvalds's avatar
Linus Torvalds committed
1162 1163 1164 1165 1166
				unsigned short mtu = new_mtu;

				if (new_mtu < 68 || new_mtu >= old_mtu) {

					/* BSD 4.2 compatibility hack :-( */
Linus Torvalds's avatar
Linus Torvalds committed
1167
					if (mtu == 0 &&
1168
					    old_mtu >= rth->u.dst.metrics[RTAX_MTU-1] &&
Linus Torvalds's avatar
Linus Torvalds committed
1169 1170
					    old_mtu >= 68 + (iph->ihl << 2))
						old_mtu -= iph->ihl << 2;
Linus Torvalds's avatar
Linus Torvalds committed
1171 1172 1173

					mtu = guess_mtu(old_mtu);
				}
1174 1175
				if (mtu <= rth->u.dst.metrics[RTAX_MTU-1]) {
					if (mtu < rth->u.dst.metrics[RTAX_MTU-1]) { 
Linus Torvalds's avatar
Linus Torvalds committed
1176 1177 1178
						dst_confirm(&rth->u.dst);
						if (mtu < ip_rt_min_pmtu) {
							mtu = ip_rt_min_pmtu;
1179
							rth->u.dst.metrics[RTAX_LOCK-1] |=
Linus Torvalds's avatar
Linus Torvalds committed
1180
								(1 << RTAX_MTU);
Linus Torvalds's avatar
Linus Torvalds committed
1181
						}
1182
						rth->u.dst.metrics[RTAX_MTU-1] = mtu;
Linus Torvalds's avatar
Linus Torvalds committed
1183 1184
						dst_set_expires(&rth->u.dst,
							ip_rt_mtu_expires);
Linus Torvalds's avatar
Linus Torvalds committed
1185 1186 1187 1188 1189
					}
					est_mtu = mtu;
				}
			}
		}
1190
		rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
1191 1192 1193 1194
	}
	return est_mtu ? : new_mtu;
}

1195
static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu)
Linus Torvalds's avatar
Linus Torvalds committed
1196
{
1197 1198
	if (dst->metrics[RTAX_MTU-1] > mtu && mtu >= 68 &&
	    !(dst_metric_locked(dst, RTAX_MTU))) {
Linus Torvalds's avatar
Linus Torvalds committed
1199 1200
		if (mtu < ip_rt_min_pmtu) {
			mtu = ip_rt_min_pmtu;
1201
			dst->metrics[RTAX_LOCK-1] |= (1 << RTAX_MTU);
Linus Torvalds's avatar
Linus Torvalds committed
1202
		}
1203
		dst->metrics[RTAX_MTU-1] = mtu;
Linus Torvalds's avatar
Linus Torvalds committed
1204 1205 1206 1207
		dst_set_expires(dst, ip_rt_mtu_expires);
	}
}

Linus Torvalds's avatar
Linus Torvalds committed
1208
static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie)
Linus Torvalds's avatar
Linus Torvalds committed
1209 1210 1211 1212 1213
{
	dst_release(dst);
	return NULL;
}

Linus Torvalds's avatar
Linus Torvalds committed
1214
static void ipv4_dst_destroy(struct dst_entry *dst)
Linus Torvalds's avatar
Linus Torvalds committed
1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258
{
	struct rtable *rt = (struct rtable *) dst;
	struct inet_peer *peer = rt->peer;

	if (peer) {
		rt->peer = NULL;
		inet_putpeer(peer);
	}
}

static void ipv4_link_failure(struct sk_buff *skb)
{
	struct rtable *rt;

	icmp_send(skb, ICMP_DEST_UNREACH, ICMP_HOST_UNREACH, 0);

	rt = (struct rtable *) skb->dst;
	if (rt)
		dst_set_expires(&rt->u.dst, 0);
}

static int ip_rt_bug(struct sk_buff *skb)
{
	printk(KERN_DEBUG "ip_rt_bug: %u.%u.%u.%u -> %u.%u.%u.%u, %s\n",
		NIPQUAD(skb->nh.iph->saddr), NIPQUAD(skb->nh.iph->daddr),
		skb->dev ? skb->dev->name : "?");
	kfree_skb(skb);
	return 0;
}

/*
   We do not cache source address of outgoing interface,
   because it is used only by IP RR, TS and SRR options,
   so that it out of fast path.

   BTW remember: "addr" is allowed to be not aligned
   in IP options!
 */

void ip_rt_get_source(u8 *addr, struct rtable *rt)
{
	u32 src;
	struct fib_result res;

1259
	if (rt->fl.iif == 0)
Linus Torvalds's avatar
Linus Torvalds committed
1260
		src = rt->rt_src;
1261
	else if (fib_lookup(&rt->fl, &res) == 0) {
Linus Torvalds's avatar
Linus Torvalds committed
1262 1263
#ifdef CONFIG_IP_ROUTE_NAT
		if (res.type == RTN_NAT)
Linus Torvalds's avatar
Linus Torvalds committed
1264 1265
			src = inet_select_addr(rt->u.dst.dev, rt->rt_gateway,
						RT_SCOPE_UNIVERSE);
Linus Torvalds's avatar
Linus Torvalds committed
1266 1267 1268 1269 1270
		else
#endif
			src = FIB_RES_PREFSRC(res);
		fib_res_put(&res);
	} else
Linus Torvalds's avatar
Linus Torvalds committed
1271 1272
		src = inet_select_addr(rt->u.dst.dev, rt->rt_gateway,
					RT_SCOPE_UNIVERSE);
Linus Torvalds's avatar
Linus Torvalds committed
1273 1274 1275 1276 1277 1278
	memcpy(addr, &src, 4);
}

#ifdef CONFIG_NET_CLS_ROUTE
static void set_class_tag(struct rtable *rt, u32 tag)
{
Linus Torvalds's avatar
Linus Torvalds committed
1279 1280 1281 1282
	if (!(rt->u.dst.tclassid & 0xFFFF))
		rt->u.dst.tclassid |= tag & 0xFFFF;
	if (!(rt->u.dst.tclassid & 0xFFFF0000))
		rt->u.dst.tclassid |= tag & 0xFFFF0000;
Linus Torvalds's avatar
Linus Torvalds committed
1283 1284 1285 1286 1287 1288 1289 1290
}
#endif

static void rt_set_nexthop(struct rtable *rt, struct fib_result *res, u32 itag)
{
	struct fib_info *fi = res->fi;

	if (fi) {
Linus Torvalds's avatar
Linus Torvalds committed
1291 1292
		if (FIB_RES_GW(*res) &&
		    FIB_RES_NH(*res).nh_scope == RT_SCOPE_LINK)
Linus Torvalds's avatar
Linus Torvalds committed
1293
			rt->rt_gateway = FIB_RES_GW(*res);
1294 1295
		memcpy(rt->u.dst.metrics, fi->fib_metrics,
		       sizeof(rt->u.dst.metrics));
Linus Torvalds's avatar
Linus Torvalds committed
1296
		if (fi->fib_mtu == 0) {
1297 1298
			rt->u.dst.metrics[RTAX_MTU-1] = rt->u.dst.dev->mtu;
			if (rt->u.dst.metrics[RTAX_LOCK-1] & (1 << RTAX_MTU) &&
Linus Torvalds's avatar
Linus Torvalds committed
1299
			    rt->rt_gateway != rt->rt_dst &&
1300 1301
			    rt->u.dst.dev->mtu > 576)
				rt->u.dst.metrics[RTAX_MTU-1] = 576;
Linus Torvalds's avatar
Linus Torvalds committed
1302 1303 1304 1305
		}
#ifdef CONFIG_NET_CLS_ROUTE
		rt->u.dst.tclassid = FIB_RES_NH(*res).nh_tclassid;
#endif
Linus Torvalds's avatar
Linus Torvalds committed
1306
	} else
1307
		rt->u.dst.metrics[RTAX_MTU-1]= rt->u.dst.dev->mtu;
Linus Torvalds's avatar
Linus Torvalds committed
1308

1309 1310 1311 1312
	if (rt->u.dst.metrics[RTAX_MTU-1] > IP_MAX_MTU)
		rt->u.dst.metrics[RTAX_MTU-1] = IP_MAX_MTU;
	if (rt->u.dst.metrics[RTAX_ADVMSS-1] == 0)
		rt->u.dst.metrics[RTAX_ADVMSS-1] = max_t(unsigned int, rt->u.dst.dev->mtu - 40,
Linus Torvalds's avatar
Linus Torvalds committed
1313
				       ip_rt_min_advmss);
1314 1315
	if (rt->u.dst.metrics[RTAX_ADVMSS-1] > 65535 - 40)
		rt->u.dst.metrics[RTAX_ADVMSS-1] = 65535 - 40;
Linus Torvalds's avatar
Linus Torvalds committed
1316 1317 1318 1319 1320 1321 1322 1323 1324 1325

#ifdef CONFIG_NET_CLS_ROUTE
#ifdef CONFIG_IP_MULTIPLE_TABLES
	set_class_tag(rt, fib_rules_tclass(res));
#endif
	set_class_tag(rt, itag);
#endif
        rt->rt_type = res->type;
}

Linus Torvalds's avatar
Linus Torvalds committed
1326 1327
static int ip_route_input_mc(struct sk_buff *skb, u32 daddr, u32 saddr,
				u8 tos, struct net_device *dev, int our)
Linus Torvalds's avatar
Linus Torvalds committed
1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340
{
	unsigned hash;
	struct rtable *rth;
	u32 spec_dst;
	struct in_device *in_dev = in_dev_get(dev);
	u32 itag = 0;

	/* Primary sanity checks. */

	if (in_dev == NULL)
		return -EINVAL;

	if (MULTICAST(saddr) || BADCLASS(saddr) || LOOPBACK(saddr) ||
1341
	    skb->protocol != htons(ETH_P_IP))
Linus Torvalds's avatar
Linus Torvalds committed
1342 1343 1344 1345 1346 1347
		goto e_inval;

	if (ZERONET(saddr)) {
		if (!LOCAL_MCAST(daddr))
			goto e_inval;
		spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
Linus Torvalds's avatar
Linus Torvalds committed
1348 1349
	} else if (fib_validate_source(saddr, 0, tos, 0,
					dev, &spec_dst, &itag) < 0)
Linus Torvalds's avatar
Linus Torvalds committed
1350 1351 1352 1353 1354 1355 1356 1357 1358 1359
		goto e_inval;

	rth = dst_alloc(&ipv4_dst_ops);
	if (!rth)
		goto e_nobufs;

	rth->u.dst.output= ip_rt_bug;

	atomic_set(&rth->u.dst.__refcnt, 1);
	rth->u.dst.flags= DST_HOST;
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
1360 1361
	if (in_dev->cnf.no_policy)
		rth->u.dst.flags |= DST_NOPOLICY;
1362
	rth->fl.fl4_dst	= daddr;
Linus Torvalds's avatar
Linus Torvalds committed
1363
	rth->rt_dst	= daddr;
1364
	rth->fl.fl4_tos	= tos;
Linus Torvalds's avatar
Linus Torvalds committed
1365
#ifdef CONFIG_IP_ROUTE_FWMARK
1366
	rth->fl.fl4_fwmark= skb->nfmark;
Linus Torvalds's avatar
Linus Torvalds committed
1367
#endif
1368
	rth->fl.fl4_src	= saddr;
Linus Torvalds's avatar
Linus Torvalds committed
1369 1370 1371 1372 1373 1374 1375 1376 1377
	rth->rt_src	= saddr;
#ifdef CONFIG_IP_ROUTE_NAT
	rth->rt_dst_map	= daddr;
	rth->rt_src_map	= saddr;
#endif
#ifdef CONFIG_NET_CLS_ROUTE
	rth->u.dst.tclassid = itag;
#endif
	rth->rt_iif	=
1378
	rth->fl.iif	= dev->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1379 1380
	rth->u.dst.dev	= &loopback_dev;
	dev_hold(rth->u.dst.dev);
1381
	rth->fl.oif	= 0;
Linus Torvalds's avatar
Linus Torvalds committed
1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394
	rth->rt_gateway	= daddr;
	rth->rt_spec_dst= spec_dst;
	rth->rt_type	= RTN_MULTICAST;
	rth->rt_flags	= RTCF_MULTICAST;
	if (our) {
		rth->u.dst.input= ip_local_deliver;
		rth->rt_flags |= RTCF_LOCAL;
	}

#ifdef CONFIG_IP_MROUTE
	if (!LOCAL_MCAST(daddr) && IN_DEV_MFORWARD(in_dev))
		rth->u.dst.input = ip_mr_input;
#endif
Linus Torvalds's avatar
Linus Torvalds committed
1395
	rt_cache_stat[smp_processor_id()].in_slow_mc++;
Linus Torvalds's avatar
Linus Torvalds committed
1396 1397

	in_dev_put(in_dev);
Linus Torvalds's avatar
Linus Torvalds committed
1398 1399
	hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos);
	return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);
Linus Torvalds's avatar
Linus Torvalds committed
1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425

e_nobufs:
	in_dev_put(in_dev);
	return -ENOBUFS;

e_inval:
	in_dev_put(in_dev);
	return -EINVAL;
}

/*
 *	NOTE. We drop all the packets that has local source
 *	addresses, because every properly looped back packet
 *	must have correct destination already attached by output routine.
 *
 *	Such approach solves two big problems:
 *	1. Not simplex devices are handled properly.
 *	2. IP spoofing attempts are filtered with 100% of guarantee.
 */

int ip_route_input_slow(struct sk_buff *skb, u32 daddr, u32 saddr,
			u8 tos, struct net_device *dev)
{
	struct fib_result res;
	struct in_device *in_dev = in_dev_get(dev);
	struct in_device *out_dev = NULL;
1426 1427 1428 1429 1430 1431 1432 1433 1434 1435
	struct flowi fl = { .nl_u = { .ip4_u =
				      { .daddr = daddr,
					.saddr = saddr,
					.tos = tos,
					.scope = RT_SCOPE_UNIVERSE,
#ifdef CONFIG_IP_ROUTE_FWMARK
					.fwmark = skb->nfmark
#endif
				      } },
			    .iif = dev->ifindex };
Linus Torvalds's avatar
Linus Torvalds committed
1436 1437 1438 1439 1440 1441 1442 1443
	unsigned	flags = 0;
	u32		itag = 0;
	struct rtable * rth;
	unsigned	hash;
	u32		spec_dst;
	int		err = -EINVAL;
	int		free_res = 0;

Linus Torvalds's avatar
Linus Torvalds committed
1444
	/* IP on this device is disabled. */
Linus Torvalds's avatar
Linus Torvalds committed
1445 1446

	if (!in_dev)
Linus Torvalds's avatar
Linus Torvalds committed
1447
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
1448

1449
	hash = rt_hash_code(daddr, saddr ^ (fl.iif << 5), tos);
Linus Torvalds's avatar
Linus Torvalds committed
1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472

	/* Check for the most weird martians, which can be not detected
	   by fib_lookup.
	 */

	if (MULTICAST(saddr) || BADCLASS(saddr) || LOOPBACK(saddr))
		goto martian_source;

	if (daddr == 0xFFFFFFFF || (saddr == 0 && daddr == 0))
		goto brd_input;

	/* Accept zero addresses only to limited broadcast;
	 * I even do not know to fix it or not. Waiting for complains :-)
	 */
	if (ZERONET(saddr))
		goto martian_source;

	if (BADCLASS(daddr) || ZERONET(daddr) || LOOPBACK(daddr))
		goto martian_destination;

	/*
	 *	Now we are ready to route packet.
	 */
1473
	if ((err = fib_lookup(&fl, &res)) != 0) {
Linus Torvalds's avatar
Linus Torvalds committed
1474 1475 1476 1477 1478 1479
		if (!IN_DEV_FORWARD(in_dev))
			goto e_inval;
		goto no_route;
	}
	free_res = 1;

Linus Torvalds's avatar
Linus Torvalds committed
1480 1481
	rt_cache_stat[smp_processor_id()].in_slow_tot++;

Linus Torvalds's avatar
Linus Torvalds committed
1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492
#ifdef CONFIG_IP_ROUTE_NAT
	/* Policy is applied before mapping destination,
	   but rerouting after map should be made with old source.
	 */

	if (1) {
		u32 src_map = saddr;
		if (res.r)
			src_map = fib_rules_policy(saddr, &res, &flags);

		if (res.type == RTN_NAT) {
1493
			fl.fl4_dst = fib_rules_map_destination(daddr, &res);
Linus Torvalds's avatar
Linus Torvalds committed
1494 1495
			fib_res_put(&res);
			free_res = 0;
1496
			if (fib_lookup(&fl, &res))
Linus Torvalds's avatar
Linus Torvalds committed
1497 1498 1499 1500 1501 1502
				goto e_inval;
			free_res = 1;
			if (res.type != RTN_UNICAST)
				goto e_inval;
			flags |= RTCF_DNAT;
		}
1503
		fl.fl4_src = src_map;
Linus Torvalds's avatar
Linus Torvalds committed
1504 1505 1506 1507 1508 1509 1510 1511
	}
#endif

	if (res.type == RTN_BROADCAST)
		goto brd_input;

	if (res.type == RTN_LOCAL) {
		int result;
Linus Torvalds's avatar
Linus Torvalds committed
1512 1513
		result = fib_validate_source(saddr, daddr, tos,
					     loopback_dev.ifindex,
Linus Torvalds's avatar
Linus Torvalds committed
1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528
					     dev, &spec_dst, &itag);
		if (result < 0)
			goto martian_source;
		if (result)
			flags |= RTCF_DIRECTSRC;
		spec_dst = daddr;
		goto local_input;
	}

	if (!IN_DEV_FORWARD(in_dev))
		goto e_inval;
	if (res.type != RTN_UNICAST)
		goto martian_destination;

#ifdef CONFIG_IP_ROUTE_MULTIPATH
1529 1530
	if (res.fi->fib_nhs > 1 && fl.oif == 0)
		fib_select_multipath(&fl, &res);
Linus Torvalds's avatar
Linus Torvalds committed
1531 1532 1533 1534
#endif
	out_dev = in_dev_get(FIB_RES_DEV(res));
	if (out_dev == NULL) {
		if (net_ratelimit())
Linus Torvalds's avatar
Linus Torvalds committed
1535 1536
			printk(KERN_CRIT "Bug in ip_route_input_slow(). "
					 "Please, report\n");
Linus Torvalds's avatar
Linus Torvalds committed
1537 1538 1539
		goto e_inval;
	}

Linus Torvalds's avatar
Linus Torvalds committed
1540 1541
	err = fib_validate_source(saddr, daddr, tos, FIB_RES_OIF(res), dev,
				  &spec_dst, &itag);
Linus Torvalds's avatar
Linus Torvalds committed
1542 1543 1544 1545 1546 1547
	if (err < 0)
		goto martian_source;

	if (err)
		flags |= RTCF_DIRECTSRC;

Linus Torvalds's avatar
Linus Torvalds committed
1548 1549 1550
	if (out_dev == in_dev && err && !(flags & (RTCF_NAT | RTCF_MASQ)) &&
	    (IN_DEV_SHARED_MEDIA(out_dev) ||
	     inet_addr_onlink(out_dev, saddr, FIB_RES_GW(res))))
Linus Torvalds's avatar
Linus Torvalds committed
1551 1552
		flags |= RTCF_DOREDIRECT;

1553
	if (skb->protocol != htons(ETH_P_IP)) {
Linus Torvalds's avatar
Linus Torvalds committed
1554 1555 1556
		/* Not IP (i.e. ARP). Do not create route, if it is
		 * invalid for proxy arp. DNAT routes are always valid.
		 */
Linus Torvalds's avatar
Linus Torvalds committed
1557
		if (out_dev == in_dev && !(flags & RTCF_DNAT))
Linus Torvalds's avatar
Linus Torvalds committed
1558 1559 1560 1561 1562 1563 1564 1565 1566
			goto e_inval;
	}

	rth = dst_alloc(&ipv4_dst_ops);
	if (!rth)
		goto e_nobufs;

	atomic_set(&rth->u.dst.__refcnt, 1);
	rth->u.dst.flags= DST_HOST;
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
1567 1568 1569 1570
	if (in_dev->cnf.no_policy)
		rth->u.dst.flags |= DST_NOPOLICY;
	if (in_dev->cnf.no_xfrm)
		rth->u.dst.flags |= DST_NOXFRM;
1571
	rth->fl.fl4_dst	= daddr;
Linus Torvalds's avatar
Linus Torvalds committed
1572
	rth->rt_dst	= daddr;
1573
	rth->fl.fl4_tos	= tos;
Linus Torvalds's avatar
Linus Torvalds committed
1574
#ifdef CONFIG_IP_ROUTE_FWMARK
1575
	rth->fl.fl4_fwmark= skb->nfmark;
Linus Torvalds's avatar
Linus Torvalds committed
1576
#endif
1577
	rth->fl.fl4_src	= saddr;
Linus Torvalds's avatar
Linus Torvalds committed
1578 1579 1580
	rth->rt_src	= saddr;
	rth->rt_gateway	= daddr;
#ifdef CONFIG_IP_ROUTE_NAT
1581 1582
	rth->rt_src_map	= fl.fl4_src;
	rth->rt_dst_map	= fl.fl4_dst;
Linus Torvalds's avatar
Linus Torvalds committed
1583
	if (flags&RTCF_DNAT)
1584
		rth->rt_gateway	= fl.fl4_dst;
Linus Torvalds's avatar
Linus Torvalds committed
1585 1586
#endif
	rth->rt_iif 	=
1587
	rth->fl.iif	= dev->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1588 1589
	rth->u.dst.dev	= out_dev->dev;
	dev_hold(rth->u.dst.dev);
1590
	rth->fl.oif 	= 0;
Linus Torvalds's avatar
Linus Torvalds committed
1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618
	rth->rt_spec_dst= spec_dst;

	rth->u.dst.input = ip_forward;
	rth->u.dst.output = ip_output;

	rt_set_nexthop(rth, &res, itag);

	rth->rt_flags = flags;

#ifdef CONFIG_NET_FASTROUTE
	if (netdev_fastroute && !(flags&(RTCF_NAT|RTCF_MASQ|RTCF_DOREDIRECT))) {
		struct net_device *odev = rth->u.dst.dev;
		if (odev != dev &&
		    dev->accept_fastpath &&
		    odev->mtu >= dev->mtu &&
		    dev->accept_fastpath(dev, &rth->u.dst) == 0)
			rth->rt_flags |= RTCF_FAST;
	}
#endif

intern:
	err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);
done:
	in_dev_put(in_dev);
	if (out_dev)
		in_dev_put(out_dev);
	if (free_res)
		fib_res_put(&res);
Linus Torvalds's avatar
Linus Torvalds committed
1619
out:	return err;
Linus Torvalds's avatar
Linus Torvalds committed
1620 1621

brd_input:
1622
	if (skb->protocol != htons(ETH_P_IP))
Linus Torvalds's avatar
Linus Torvalds committed
1623 1624
		goto e_inval;

Linus Torvalds's avatar
Linus Torvalds committed
1625
	if (ZERONET(saddr))
Linus Torvalds's avatar
Linus Torvalds committed
1626
		spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
Linus Torvalds's avatar
Linus Torvalds committed
1627 1628 1629
	else {
		err = fib_validate_source(saddr, 0, tos, 0, dev, &spec_dst,
					  &itag);
Linus Torvalds's avatar
Linus Torvalds committed
1630 1631 1632 1633 1634 1635 1636
		if (err < 0)
			goto martian_source;
		if (err)
			flags |= RTCF_DIRECTSRC;
	}
	flags |= RTCF_BROADCAST;
	res.type = RTN_BROADCAST;
Linus Torvalds's avatar
Linus Torvalds committed
1637
	rt_cache_stat[smp_processor_id()].in_brd++;
Linus Torvalds's avatar
Linus Torvalds committed
1638 1639 1640 1641 1642 1643 1644 1645 1646 1647

local_input:
	rth = dst_alloc(&ipv4_dst_ops);
	if (!rth)
		goto e_nobufs;

	rth->u.dst.output= ip_rt_bug;

	atomic_set(&rth->u.dst.__refcnt, 1);
	rth->u.dst.flags= DST_HOST;
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
1648 1649
	if (in_dev->cnf.no_policy)
		rth->u.dst.flags |= DST_NOPOLICY;
1650
	rth->fl.fl4_dst	= daddr;
Linus Torvalds's avatar
Linus Torvalds committed
1651
	rth->rt_dst	= daddr;
1652
	rth->fl.fl4_tos	= tos;
Linus Torvalds's avatar
Linus Torvalds committed
1653
#ifdef CONFIG_IP_ROUTE_FWMARK
1654
	rth->fl.fl4_fwmark= skb->nfmark;
Linus Torvalds's avatar
Linus Torvalds committed
1655
#endif
1656
	rth->fl.fl4_src	= saddr;
Linus Torvalds's avatar
Linus Torvalds committed
1657 1658
	rth->rt_src	= saddr;
#ifdef CONFIG_IP_ROUTE_NAT
1659 1660
	rth->rt_dst_map	= fl.fl4_dst;
	rth->rt_src_map	= fl.fl4_src;
Linus Torvalds's avatar
Linus Torvalds committed
1661 1662 1663 1664 1665
#endif
#ifdef CONFIG_NET_CLS_ROUTE
	rth->u.dst.tclassid = itag;
#endif
	rth->rt_iif	=
1666
	rth->fl.iif	= dev->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681
	rth->u.dst.dev	= &loopback_dev;
	dev_hold(rth->u.dst.dev);
	rth->rt_gateway	= daddr;
	rth->rt_spec_dst= spec_dst;
	rth->u.dst.input= ip_local_deliver;
	rth->rt_flags 	= flags|RTCF_LOCAL;
	if (res.type == RTN_UNREACHABLE) {
		rth->u.dst.input= ip_error;
		rth->u.dst.error= -err;
		rth->rt_flags 	&= ~RTCF_LOCAL;
	}
	rth->rt_type	= res.type;
	goto intern;

no_route:
Linus Torvalds's avatar
Linus Torvalds committed
1682
	rt_cache_stat[smp_processor_id()].in_no_route++;
Linus Torvalds's avatar
Linus Torvalds committed
1683 1684 1685 1686 1687 1688 1689 1690
	spec_dst = inet_select_addr(dev, 0, RT_SCOPE_UNIVERSE);
	res.type = RTN_UNREACHABLE;
	goto local_input;

	/*
	 *	Do not cache martian addresses: they should be logged (RFC1812)
	 */
martian_destination:
Linus Torvalds's avatar
Linus Torvalds committed
1691
	rt_cache_stat[smp_processor_id()].in_martian_dst++;
Linus Torvalds's avatar
Linus Torvalds committed
1692 1693
#ifdef CONFIG_IP_ROUTE_VERBOSE
	if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
Linus Torvalds's avatar
Linus Torvalds committed
1694 1695
		printk(KERN_WARNING "martian destination %u.%u.%u.%u from "
			"%u.%u.%u.%u, dev %s\n",
Linus Torvalds's avatar
Linus Torvalds committed
1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706
			NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
#endif
e_inval:
	err = -EINVAL;
	goto done;

e_nobufs:
	err = -ENOBUFS;
	goto done;

martian_source:
Linus Torvalds's avatar
Linus Torvalds committed
1707 1708

	rt_cache_stat[smp_processor_id()].in_martian_src++;
Linus Torvalds's avatar
Linus Torvalds committed
1709 1710 1711 1712 1713 1714
#ifdef CONFIG_IP_ROUTE_VERBOSE
	if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit()) {
		/*
		 *	RFC1812 recommendation, if source is martian,
		 *	the only hint is MAC header.
		 */
Linus Torvalds's avatar
Linus Torvalds committed
1715 1716
		printk(KERN_WARNING "martian source %u.%u.%u.%u from "
			"%u.%u.%u.%u, on dev %s\n",
Linus Torvalds's avatar
Linus Torvalds committed
1717 1718 1719 1720 1721
			NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
		if (dev->hard_header_len) {
			int i;
			unsigned char *p = skb->mac.raw;
			printk(KERN_WARNING "ll header: ");
Linus Torvalds's avatar
Linus Torvalds committed
1722
			for (i = 0; i < dev->hard_header_len; i++, p++) {
Linus Torvalds's avatar
Linus Torvalds committed
1723
				printk("%02x", *p);
Linus Torvalds's avatar
Linus Torvalds committed
1724
				if (i < (dev->hard_header_len - 1))
Linus Torvalds's avatar
Linus Torvalds committed
1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
					printk(":");
			}
			printk("\n");
		}
	}
#endif
	goto e_inval;
}

int ip_route_input(struct sk_buff *skb, u32 daddr, u32 saddr,
		   u8 tos, struct net_device *dev)
{
	struct rtable * rth;
	unsigned	hash;
	int iif = dev->ifindex;

	tos &= IPTOS_RT_MASK;
Linus Torvalds's avatar
Linus Torvalds committed
1742
	hash = rt_hash_code(daddr, saddr ^ (iif << 5), tos);
Linus Torvalds's avatar
Linus Torvalds committed
1743

1744
	rcu_read_lock();
Linus Torvalds's avatar
Linus Torvalds committed
1745
	for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.rt_next) {
1746
		read_barrier_depends();
1747 1748 1749 1750
		if (rth->fl.fl4_dst == daddr &&
		    rth->fl.fl4_src == saddr &&
		    rth->fl.iif == iif &&
		    rth->fl.oif == 0 &&
Linus Torvalds's avatar
Linus Torvalds committed
1751
#ifdef CONFIG_IP_ROUTE_FWMARK
1752
		    rth->fl.fl4_fwmark == skb->nfmark &&
Linus Torvalds's avatar
Linus Torvalds committed
1753
#endif
1754
		    rth->fl.fl4_tos == tos) {
Linus Torvalds's avatar
Linus Torvalds committed
1755 1756 1757
			rth->u.dst.lastuse = jiffies;
			dst_hold(&rth->u.dst);
			rth->u.dst.__use++;
Linus Torvalds's avatar
Linus Torvalds committed
1758
			rt_cache_stat[smp_processor_id()].in_hit++;
1759
			rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
1760 1761 1762 1763
			skb->dst = (struct dst_entry*)rth;
			return 0;
		}
	}
1764
	rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788

	/* Multicast recognition logic is moved from route cache to here.
	   The problem was that too many Ethernet cards have broken/missing
	   hardware multicast filters :-( As result the host on multicasting
	   network acquires a lot of useless route cache entries, sort of
	   SDR messages from all the world. Now we try to get rid of them.
	   Really, provided software IP multicast filter is organized
	   reasonably (at least, hashed), it does not result in a slowdown
	   comparing with route cache reject entries.
	   Note, that multicast routers are not affected, because
	   route cache entry is created eventually.
	 */
	if (MULTICAST(daddr)) {
		struct in_device *in_dev;

		read_lock(&inetdev_lock);
		if ((in_dev = __in_dev_get(dev)) != NULL) {
			int our = ip_check_mc(in_dev, daddr);
			if (our
#ifdef CONFIG_IP_MROUTE
			    || (!LOCAL_MCAST(daddr) && IN_DEV_MFORWARD(in_dev))
#endif
			    ) {
				read_unlock(&inetdev_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1789 1790
				return ip_route_input_mc(skb, daddr, saddr,
							 tos, dev, our);
Linus Torvalds's avatar
Linus Torvalds committed
1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802
			}
		}
		read_unlock(&inetdev_lock);
		return -EINVAL;
	}
	return ip_route_input_slow(skb, daddr, saddr, tos, dev);
}

/*
 * Major route resolver routine.
 */

1803
int ip_route_output_slow(struct rtable **rp, const struct flowi *oldflp)
Linus Torvalds's avatar
Linus Torvalds committed
1804
{
1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818
	u32 tos	= oldflp->fl4_tos & (IPTOS_RT_MASK | RTO_ONLINK);
	struct flowi fl = { .nl_u = { .ip4_u =
				      { .daddr = oldflp->fl4_dst,
					.saddr = oldflp->fl4_src,
					.tos = tos & IPTOS_RT_MASK,
					.scope = ((tos & RTO_ONLINK) ?
						  RT_SCOPE_LINK :
						  RT_SCOPE_UNIVERSE),
#ifdef CONFIG_IP_ROUTE_FWMARK
					.fwmark = oldflp->fl4_fwmark
#endif
				      } },
			    .iif = loopback_dev.ifindex,
			    .oif = oldflp->oif };
Linus Torvalds's avatar
Linus Torvalds committed
1819 1820 1821 1822
	struct fib_result res;
	unsigned flags = 0;
	struct rtable *rth;
	struct net_device *dev_out = NULL;
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
1823
	struct in_device *in_dev = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1824 1825 1826
	unsigned hash;
	int free_res = 0;
	int err;
1827

Linus Torvalds's avatar
Linus Torvalds committed
1828
	res.fi		= NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1829
#ifdef CONFIG_IP_MULTIPLE_TABLES
Linus Torvalds's avatar
Linus Torvalds committed
1830
	res.r		= NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1831 1832
#endif

1833
	if (oldflp->fl4_src) {
Linus Torvalds's avatar
Linus Torvalds committed
1834
		err = -EINVAL;
1835 1836 1837
		if (MULTICAST(oldflp->fl4_src) ||
		    BADCLASS(oldflp->fl4_src) ||
		    ZERONET(oldflp->fl4_src))
Linus Torvalds's avatar
Linus Torvalds committed
1838
			goto out;
Linus Torvalds's avatar
Linus Torvalds committed
1839 1840

		/* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
1841
		dev_out = ip_dev_find(oldflp->fl4_src);
Linus Torvalds's avatar
Linus Torvalds committed
1842
		if (dev_out == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
1843
			goto out;
Linus Torvalds's avatar
Linus Torvalds committed
1844 1845 1846 1847 1848 1849 1850 1851 1852

		/* I removed check for oif == dev_out->oif here.
		   It was wrong by three reasons:
		   1. ip_dev_find(saddr) can return wrong iface, if saddr is
		      assigned to multiple interfaces.
		   2. Moreover, we are allowed to send packets with saddr
		      of another iface. --ANK
		 */

1853 1854
		if (oldflp->oif == 0
		    && (MULTICAST(oldflp->fl4_dst) || oldflp->fl4_dst == 0xFFFFFFFF)) {
Linus Torvalds's avatar
Linus Torvalds committed
1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869
			/* Special hack: user can direct multicasts
			   and limited broadcast via necessary interface
			   without fiddling with IP_MULTICAST_IF or IP_PKTINFO.
			   This hack is not just for fun, it allows
			   vic,vat and friends to work.
			   They bind socket to loopback, set ttl to zero
			   and expect that it will work.
			   From the viewpoint of routing cache they are broken,
			   because we are not allowed to build multicast path
			   with loopback source addr (look, routing cache
			   cannot know, that ttl is zero, so that packet
			   will not leave this host and route is valid).
			   Luckily, this hack is good workaround.
			 */

1870
			fl.oif = dev_out->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1871 1872 1873 1874 1875 1876
			goto make_route;
		}
		if (dev_out)
			dev_put(dev_out);
		dev_out = NULL;
	}
1877 1878
	if (oldflp->oif) {
		dev_out = dev_get_by_index(oldflp->oif);
Linus Torvalds's avatar
Linus Torvalds committed
1879
		err = -ENODEV;
Linus Torvalds's avatar
Linus Torvalds committed
1880
		if (dev_out == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
1881
			goto out;
Linus Torvalds's avatar
Linus Torvalds committed
1882 1883
		if (__in_dev_get(dev_out) == NULL) {
			dev_put(dev_out);
Linus Torvalds's avatar
Linus Torvalds committed
1884
			goto out;	/* Wrong error code */
Linus Torvalds's avatar
Linus Torvalds committed
1885 1886
		}

1887 1888 1889 1890
		if (LOCAL_MCAST(oldflp->fl4_dst) || oldflp->fl4_dst == 0xFFFFFFFF) {
			if (!fl.fl4_src)
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      RT_SCOPE_LINK);
Linus Torvalds's avatar
Linus Torvalds committed
1891 1892
			goto make_route;
		}
1893 1894 1895 1896 1897 1898 1899
		if (!fl.fl4_src) {
			if (MULTICAST(oldflp->fl4_dst))
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      fl.fl4_scope);
			else if (!oldflp->fl4_dst)
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      RT_SCOPE_HOST);
Linus Torvalds's avatar
Linus Torvalds committed
1900 1901 1902
		}
	}

1903 1904 1905 1906
	if (!fl.fl4_dst) {
		fl.fl4_dst = fl.fl4_src;
		if (!fl.fl4_dst)
			fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
Linus Torvalds's avatar
Linus Torvalds committed
1907 1908 1909 1910
		if (dev_out)
			dev_put(dev_out);
		dev_out = &loopback_dev;
		dev_hold(dev_out);
1911
		fl.oif = loopback_dev.ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1912 1913 1914 1915 1916
		res.type = RTN_LOCAL;
		flags |= RTCF_LOCAL;
		goto make_route;
	}

1917
	if (fib_lookup(&fl, &res)) {
Linus Torvalds's avatar
Linus Torvalds committed
1918
		res.fi = NULL;
1919
		if (oldflp->oif) {
Linus Torvalds's avatar
Linus Torvalds committed
1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937
			/* Apparently, routing tables are wrong. Assume,
			   that the destination is on link.

			   WHY? DW.
			   Because we are allowed to send to iface
			   even if it has NO routes and NO assigned
			   addresses. When oif is specified, routing
			   tables are looked up with only one purpose:
			   to catch if destination is gatewayed, rather than
			   direct. Moreover, if MSG_DONTROUTE is set,
			   we send packet, ignoring both routing tables
			   and ifaddr state. --ANK


			   We could make it even if oif is unknown,
			   likely IPv6, but we do not.
			 */

1938 1939 1940
			if (fl.fl4_src == 0)
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      RT_SCOPE_LINK);
Linus Torvalds's avatar
Linus Torvalds committed
1941 1942 1943 1944 1945
			res.type = RTN_UNICAST;
			goto make_route;
		}
		if (dev_out)
			dev_put(dev_out);
Linus Torvalds's avatar
Linus Torvalds committed
1946 1947
		err = -ENETUNREACH;
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
1948 1949 1950 1951 1952 1953 1954
	}
	free_res = 1;

	if (res.type == RTN_NAT)
		goto e_inval;

	if (res.type == RTN_LOCAL) {
1955 1956
		if (!fl.fl4_src)
			fl.fl4_src = fl.fl4_dst;
Linus Torvalds's avatar
Linus Torvalds committed
1957 1958 1959 1960
		if (dev_out)
			dev_put(dev_out);
		dev_out = &loopback_dev;
		dev_hold(dev_out);
1961
		fl.oif = dev_out->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1962 1963 1964 1965 1966 1967 1968 1969
		if (res.fi)
			fib_info_put(res.fi);
		res.fi = NULL;
		flags |= RTCF_LOCAL;
		goto make_route;
	}

#ifdef CONFIG_IP_ROUTE_MULTIPATH
1970 1971
	if (res.fi->fib_nhs > 1 && fl.oif == 0)
		fib_select_multipath(&fl, &res);
Linus Torvalds's avatar
Linus Torvalds committed
1972 1973
	else
#endif
1974 1975
	if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
		fib_select_default(&fl, &res);
Linus Torvalds's avatar
Linus Torvalds committed
1976

1977 1978
	if (!fl.fl4_src)
		fl.fl4_src = FIB_RES_PREFSRC(res);
Linus Torvalds's avatar
Linus Torvalds committed
1979 1980 1981 1982 1983

	if (dev_out)
		dev_put(dev_out);
	dev_out = FIB_RES_DEV(res);
	dev_hold(dev_out);
1984
	fl.oif = dev_out->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
1985 1986

make_route:
1987
	if (LOOPBACK(fl.fl4_src) && !(dev_out->flags&IFF_LOOPBACK))
Linus Torvalds's avatar
Linus Torvalds committed
1988 1989
		goto e_inval;

1990
	if (fl.fl4_dst == 0xFFFFFFFF)
Linus Torvalds's avatar
Linus Torvalds committed
1991
		res.type = RTN_BROADCAST;
1992
	else if (MULTICAST(fl.fl4_dst))
Linus Torvalds's avatar
Linus Torvalds committed
1993
		res.type = RTN_MULTICAST;
1994
	else if (BADCLASS(fl.fl4_dst) || ZERONET(fl.fl4_dst))
Linus Torvalds's avatar
Linus Torvalds committed
1995 1996
		goto e_inval;

Linus Torvalds's avatar
Linus Torvalds committed
1997
	if (dev_out->flags & IFF_LOOPBACK)
Linus Torvalds's avatar
Linus Torvalds committed
1998 1999
		flags |= RTCF_LOCAL;

Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
2000 2001 2002 2003
	in_dev = in_dev_get(dev_out);
	if (!in_dev)
		goto e_inval;

Linus Torvalds's avatar
Linus Torvalds committed
2004
	if (res.type == RTN_BROADCAST) {
Linus Torvalds's avatar
Linus Torvalds committed
2005
		flags |= RTCF_BROADCAST | RTCF_LOCAL;
Linus Torvalds's avatar
Linus Torvalds committed
2006 2007 2008 2009 2010 2011
		if (res.fi) {
			fib_info_put(res.fi);
			res.fi = NULL;
		}
	} else if (res.type == RTN_MULTICAST) {
		flags |= RTCF_MULTICAST|RTCF_LOCAL;
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
2012
		if (!ip_check_mc(in_dev, oldflp->fl4_dst))
Linus Torvalds's avatar
Linus Torvalds committed
2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029
			flags &= ~RTCF_LOCAL;
		/* If multicast route do not exist use
		   default one, but do not gateway in this case.
		   Yes, it is hack.
		 */
		if (res.fi && res.prefixlen < 4) {
			fib_info_put(res.fi);
			res.fi = NULL;
		}
	}

	rth = dst_alloc(&ipv4_dst_ops);
	if (!rth)
		goto e_nobufs;

	atomic_set(&rth->u.dst.__refcnt, 1);
	rth->u.dst.flags= DST_HOST;
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
2030 2031 2032 2033
	if (in_dev->cnf.no_xfrm)
		rth->u.dst.flags |= DST_NOXFRM;
	if (in_dev->cnf.no_policy)
		rth->u.dst.flags |= DST_NOPOLICY;
2034 2035 2036 2037
	rth->fl.fl4_dst	= oldflp->fl4_dst;
	rth->fl.fl4_tos	= tos;
	rth->fl.fl4_src	= oldflp->fl4_src;
	rth->fl.oif	= oldflp->oif;
Linus Torvalds's avatar
Linus Torvalds committed
2038
#ifdef CONFIG_IP_ROUTE_FWMARK
2039
	rth->fl.fl4_fwmark= oldflp->fl4_fwmark;
Linus Torvalds's avatar
Linus Torvalds committed
2040
#endif
2041 2042
	rth->rt_dst	= fl.fl4_dst;
	rth->rt_src	= fl.fl4_src;
Linus Torvalds's avatar
Linus Torvalds committed
2043
#ifdef CONFIG_IP_ROUTE_NAT
2044 2045
	rth->rt_dst_map	= fl.fl4_dst;
	rth->rt_src_map	= fl.fl4_src;
Linus Torvalds's avatar
Linus Torvalds committed
2046
#endif
2047
	rth->rt_iif	= oldflp->oif ? : dev_out->ifindex;
Linus Torvalds's avatar
Linus Torvalds committed
2048 2049
	rth->u.dst.dev	= dev_out;
	dev_hold(dev_out);
2050 2051
	rth->rt_gateway = fl.fl4_dst;
	rth->rt_spec_dst= fl.fl4_src;
Linus Torvalds's avatar
Linus Torvalds committed
2052 2053 2054

	rth->u.dst.output=ip_output;

Linus Torvalds's avatar
Linus Torvalds committed
2055 2056
	rt_cache_stat[smp_processor_id()].out_slow_tot++;

Linus Torvalds's avatar
Linus Torvalds committed
2057
	if (flags & RTCF_LOCAL) {
Linus Torvalds's avatar
Linus Torvalds committed
2058
		rth->u.dst.input = ip_local_deliver;
2059
		rth->rt_spec_dst = fl.fl4_dst;
Linus Torvalds's avatar
Linus Torvalds committed
2060
	}
Linus Torvalds's avatar
Linus Torvalds committed
2061
	if (flags & (RTCF_BROADCAST | RTCF_MULTICAST)) {
2062
		rth->rt_spec_dst = fl.fl4_src;
Linus Torvalds's avatar
Linus Torvalds committed
2063
		if (flags & RTCF_LOCAL && !(dev_out->flags & IFF_LOOPBACK)) {
Linus Torvalds's avatar
Linus Torvalds committed
2064
			rth->u.dst.output = ip_mc_output;
Linus Torvalds's avatar
Linus Torvalds committed
2065 2066
			rt_cache_stat[smp_processor_id()].out_slow_mc++;
		}
Linus Torvalds's avatar
Linus Torvalds committed
2067 2068
#ifdef CONFIG_IP_MROUTE
		if (res.type == RTN_MULTICAST) {
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
2069 2070 2071 2072
			if (IN_DEV_MFORWARD(in_dev) &&
			    !LOCAL_MCAST(oldflp->fl4_dst)) {
				rth->u.dst.input = ip_mr_input;
				rth->u.dst.output = ip_mc_output;
Linus Torvalds's avatar
Linus Torvalds committed
2073 2074 2075 2076 2077 2078
			}
		}
#endif
	}

	rt_set_nexthop(rth, &res, 0);
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
2079
	
Linus Torvalds's avatar
Linus Torvalds committed
2080 2081 2082

	rth->rt_flags = flags;

2083
	hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos);
Linus Torvalds's avatar
Linus Torvalds committed
2084 2085 2086 2087 2088 2089
	err = rt_intern_hash(hash, rth, rp);
done:
	if (free_res)
		fib_res_put(&res);
	if (dev_out)
		dev_put(dev_out);
Alexey Kuznetsov's avatar
Alexey Kuznetsov committed
2090 2091
	if (in_dev)
		in_dev_put(in_dev);
Linus Torvalds's avatar
Linus Torvalds committed
2092
out:	return err;
Linus Torvalds's avatar
Linus Torvalds committed
2093 2094 2095 2096 2097 2098 2099 2100 2101

e_inval:
	err = -EINVAL;
	goto done;
e_nobufs:
	err = -ENOBUFS;
	goto done;
}

2102
int __ip_route_output_key(struct rtable **rp, const struct flowi *flp)
Linus Torvalds's avatar
Linus Torvalds committed
2103 2104 2105 2106
{
	unsigned hash;
	struct rtable *rth;

2107
	hash = rt_hash_code(flp->fl4_dst, flp->fl4_src ^ (flp->oif << 5), flp->fl4_tos);
Linus Torvalds's avatar
Linus Torvalds committed
2108

2109
	rcu_read_lock();
Linus Torvalds's avatar
Linus Torvalds committed
2110
	for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.rt_next) {
2111
		read_barrier_depends();
2112 2113 2114 2115
		if (rth->fl.fl4_dst == flp->fl4_dst &&
		    rth->fl.fl4_src == flp->fl4_src &&
		    rth->fl.iif == 0 &&
		    rth->fl.oif == flp->oif &&
Linus Torvalds's avatar
Linus Torvalds committed
2116
#ifdef CONFIG_IP_ROUTE_FWMARK
2117
		    rth->fl.fl4_fwmark == flp->fl4_fwmark &&
Linus Torvalds's avatar
Linus Torvalds committed
2118
#endif
2119
		    !((rth->fl.fl4_tos ^ flp->fl4_tos) &
Linus Torvalds's avatar
Linus Torvalds committed
2120
			    (IPTOS_RT_MASK | RTO_ONLINK))) {
Linus Torvalds's avatar
Linus Torvalds committed
2121 2122 2123
			rth->u.dst.lastuse = jiffies;
			dst_hold(&rth->u.dst);
			rth->u.dst.__use++;
Linus Torvalds's avatar
Linus Torvalds committed
2124
			rt_cache_stat[smp_processor_id()].out_hit++;
2125
			rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
2126 2127 2128 2129
			*rp = rth;
			return 0;
		}
	}
2130
	rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
2131

2132
	return ip_route_output_slow(rp, flp);
2133 2134 2135 2136 2137 2138 2139 2140 2141 2142
}

int ip_route_output_key(struct rtable **rp, struct flowi *flp)
{
	int err;

	if ((err = __ip_route_output_key(rp, flp)) != 0)
		return err;
	return flp->proto ? xfrm_lookup((struct dst_entry**)rp, flp, NULL, 0) : 0;
}
Linus Torvalds's avatar
Linus Torvalds committed
2143

2144 2145 2146 2147 2148 2149 2150 2151 2152
int ip_route_output_flow(struct rtable **rp, struct flowi *flp, struct sock *sk, int flags)
{
	int err;

	if ((err = __ip_route_output_key(rp, flp)) != 0)
		return err;
	return flp->proto ? xfrm_lookup((struct dst_entry**)rp, flp, sk, flags) : 0;
}

Linus Torvalds's avatar
Linus Torvalds committed
2153 2154
static int rt_fill_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
			int nowait)
Linus Torvalds's avatar
Linus Torvalds committed
2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166
{
	struct rtable *rt = (struct rtable*)skb->dst;
	struct rtmsg *r;
	struct nlmsghdr  *nlh;
	unsigned char	 *b = skb->tail;
	struct rta_cacheinfo ci;
#ifdef CONFIG_IP_MROUTE
	struct rtattr *eptr;
#endif
	nlh = NLMSG_PUT(skb, pid, seq, event, sizeof(*r));
	r = NLMSG_DATA(nlh);
	nlh->nlmsg_flags = (nowait && pid) ? NLM_F_MULTI : 0;
Linus Torvalds's avatar
Linus Torvalds committed
2167 2168 2169
	r->rtm_family	 = AF_INET;
	r->rtm_dst_len	= 32;
	r->rtm_src_len	= 0;
2170
	r->rtm_tos	= rt->fl.fl4_tos;
Linus Torvalds's avatar
Linus Torvalds committed
2171 2172 2173
	r->rtm_table	= RT_TABLE_MAIN;
	r->rtm_type	= rt->rt_type;
	r->rtm_scope	= RT_SCOPE_UNIVERSE;
Linus Torvalds's avatar
Linus Torvalds committed
2174
	r->rtm_protocol = RTPROT_UNSPEC;
Linus Torvalds's avatar
Linus Torvalds committed
2175
	r->rtm_flags	= (rt->rt_flags & ~0xFFFF) | RTM_F_CLONED;
Linus Torvalds's avatar
Linus Torvalds committed
2176 2177 2178
	if (rt->rt_flags & RTCF_NOTIFY)
		r->rtm_flags |= RTM_F_NOTIFY;
	RTA_PUT(skb, RTA_DST, 4, &rt->rt_dst);
2179
	if (rt->fl.fl4_src) {
Linus Torvalds's avatar
Linus Torvalds committed
2180
		r->rtm_src_len = 32;
2181
		RTA_PUT(skb, RTA_SRC, 4, &rt->fl.fl4_src);
Linus Torvalds's avatar
Linus Torvalds committed
2182 2183 2184 2185 2186 2187 2188
	}
	if (rt->u.dst.dev)
		RTA_PUT(skb, RTA_OIF, sizeof(int), &rt->u.dst.dev->ifindex);
#ifdef CONFIG_NET_CLS_ROUTE
	if (rt->u.dst.tclassid)
		RTA_PUT(skb, RTA_FLOW, 4, &rt->u.dst.tclassid);
#endif
2189
	if (rt->fl.iif)
Linus Torvalds's avatar
Linus Torvalds committed
2190
		RTA_PUT(skb, RTA_PREFSRC, 4, &rt->rt_spec_dst);
2191
	else if (rt->rt_src != rt->fl.fl4_src)
Linus Torvalds's avatar
Linus Torvalds committed
2192 2193 2194
		RTA_PUT(skb, RTA_PREFSRC, 4, &rt->rt_src);
	if (rt->rt_dst != rt->rt_gateway)
		RTA_PUT(skb, RTA_GATEWAY, 4, &rt->rt_gateway);
2195
	if (rtnetlink_put_metrics(skb, rt->u.dst.metrics) < 0)
Linus Torvalds's avatar
Linus Torvalds committed
2196
		goto rtattr_failure;
Linus Torvalds's avatar
Linus Torvalds committed
2197 2198 2199
	ci.rta_lastuse	= jiffies - rt->u.dst.lastuse;
	ci.rta_used	= rt->u.dst.__use;
	ci.rta_clntref	= atomic_read(&rt->u.dst.__refcnt);
Linus Torvalds's avatar
Linus Torvalds committed
2200 2201 2202 2203
	if (rt->u.dst.expires)
		ci.rta_expires = rt->u.dst.expires - jiffies;
	else
		ci.rta_expires = 0;
Linus Torvalds's avatar
Linus Torvalds committed
2204 2205
	ci.rta_error	= rt->u.dst.error;
	ci.rta_id	= ci.rta_ts = ci.rta_tsage = 0;
Linus Torvalds's avatar
Linus Torvalds committed
2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216
	if (rt->peer) {
		ci.rta_id = rt->peer->ip_id_count;
		if (rt->peer->tcp_ts_stamp) {
			ci.rta_ts = rt->peer->tcp_ts;
			ci.rta_tsage = xtime.tv_sec - rt->peer->tcp_ts_stamp;
		}
	}
#ifdef CONFIG_IP_MROUTE
	eptr = (struct rtattr*)skb->tail;
#endif
	RTA_PUT(skb, RTA_CACHEINFO, sizeof(ci), &ci);
2217
	if (rt->fl.iif) {
Linus Torvalds's avatar
Linus Torvalds committed
2218 2219 2220
#ifdef CONFIG_IP_MROUTE
		u32 dst = rt->rt_dst;

Linus Torvalds's avatar
Linus Torvalds committed
2221 2222
		if (MULTICAST(dst) && !LOCAL_MCAST(dst) &&
		    ipv4_devconf.mc_forwarding) {
Linus Torvalds's avatar
Linus Torvalds committed
2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236
			int err = ipmr_get_route(skb, r, nowait);
			if (err <= 0) {
				if (!nowait) {
					if (err == 0)
						return 0;
					goto nlmsg_failure;
				} else {
					if (err == -EMSGSIZE)
						goto nlmsg_failure;
					((struct rta_cacheinfo*)RTA_DATA(eptr))->rta_error = err;
				}
			}
		} else
#endif
2237
			RTA_PUT(skb, RTA_IIF, sizeof(int), &rt->fl.iif);
Linus Torvalds's avatar
Linus Torvalds committed
2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256
	}

	nlh->nlmsg_len = skb->tail - b;
	return skb->len;

nlmsg_failure:
rtattr_failure:
	skb_trim(skb, b - skb->data);
	return -1;
}

int inet_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg)
{
	struct rtattr **rta = arg;
	struct rtmsg *rtm = NLMSG_DATA(nlh);
	struct rtable *rt = NULL;
	u32 dst = 0;
	u32 src = 0;
	int iif = 0;
Linus Torvalds's avatar
Linus Torvalds committed
2257
	int err = -ENOBUFS;
Linus Torvalds's avatar
Linus Torvalds committed
2258 2259 2260
	struct sk_buff *skb;

	skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
2261 2262
	if (!skb)
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
2263 2264 2265 2266 2267 2268 2269

	/* Reserve room for dummy headers, this skb can pass
	   through good chunk of routing engine.
	 */
	skb->mac.raw = skb->data;
	skb_reserve(skb, MAX_HEADER + sizeof(struct iphdr));

Linus Torvalds's avatar
Linus Torvalds committed
2270 2271 2272 2273 2274 2275
	if (rta[RTA_SRC - 1])
		memcpy(&src, RTA_DATA(rta[RTA_SRC - 1]), 4);
	if (rta[RTA_DST - 1])
		memcpy(&dst, RTA_DATA(rta[RTA_DST - 1]), 4);
	if (rta[RTA_IIF - 1])
		memcpy(&iif, RTA_DATA(rta[RTA_IIF - 1]), sizeof(int));
Linus Torvalds's avatar
Linus Torvalds committed
2276 2277

	if (iif) {
Linus Torvalds's avatar
Linus Torvalds committed
2278 2279
		struct net_device *dev = __dev_get_by_index(iif);
		err = -ENODEV;
Linus Torvalds's avatar
Linus Torvalds committed
2280
		if (!dev)
Linus Torvalds's avatar
Linus Torvalds committed
2281
			goto out;
2282
		skb->protocol	= htons(ETH_P_IP);
Linus Torvalds's avatar
Linus Torvalds committed
2283
		skb->dev	= dev;
Linus Torvalds's avatar
Linus Torvalds committed
2284 2285 2286 2287 2288 2289 2290
		local_bh_disable();
		err = ip_route_input(skb, dst, src, rtm->rtm_tos, dev);
		local_bh_enable();
		rt = (struct rtable*)skb->dst;
		if (!err && rt->u.dst.error)
			err = -rt->u.dst.error;
	} else {
2291 2292 2293
		struct flowi fl = { .nl_u = { .ip4_u = { .daddr = dst,
							 .saddr = src,
							 .tos = rtm->rtm_tos } } };
Linus Torvalds's avatar
Linus Torvalds committed
2294
		int oif = 0;
Linus Torvalds's avatar
Linus Torvalds committed
2295 2296
		if (rta[RTA_OIF - 1])
			memcpy(&oif, RTA_DATA(rta[RTA_OIF - 1]), sizeof(int));
2297 2298
		fl.oif = oif;
		err = ip_route_output_key(&rt, &fl);
Linus Torvalds's avatar
Linus Torvalds committed
2299 2300 2301
	}
	if (err) {
		kfree_skb(skb);
Linus Torvalds's avatar
Linus Torvalds committed
2302
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
2303 2304 2305 2306 2307 2308 2309 2310
	}

	skb->dst = &rt->u.dst;
	if (rtm->rtm_flags & RTM_F_NOTIFY)
		rt->rt_flags |= RTCF_NOTIFY;

	NETLINK_CB(skb).dst_pid = NETLINK_CB(in_skb).pid;

Linus Torvalds's avatar
Linus Torvalds committed
2311 2312 2313 2314 2315 2316 2317 2318
	err = rt_fill_info(skb, NETLINK_CB(in_skb).pid, nlh->nlmsg_seq,
				RTM_NEWROUTE, 0);
	if (!err)
		goto out;
	if (err < 0) {
		err = -EMSGSIZE;
		goto out;
	}
Linus Torvalds's avatar
Linus Torvalds committed
2319 2320

	err = netlink_unicast(rtnl, skb, NETLINK_CB(in_skb).pid, MSG_DONTWAIT);
Linus Torvalds's avatar
Linus Torvalds committed
2321 2322 2323
	if (err > 0)
		err = 0;
out:	return err;
Linus Torvalds's avatar
Linus Torvalds committed
2324 2325 2326 2327 2328 2329 2330 2331 2332 2333
}

int ip_rt_dump(struct sk_buff *skb,  struct netlink_callback *cb)
{
	struct rtable *rt;
	int h, s_h;
	int idx, s_idx;

	s_h = cb->args[0];
	s_idx = idx = cb->args[1];
Linus Torvalds's avatar
Linus Torvalds committed
2334
	for (h = 0; h <= rt_hash_mask; h++) {
Linus Torvalds's avatar
Linus Torvalds committed
2335 2336 2337
		if (h < s_h) continue;
		if (h > s_h)
			s_idx = 0;
2338
		rcu_read_lock();
Linus Torvalds's avatar
Linus Torvalds committed
2339 2340
		for (rt = rt_hash_table[h].chain, idx = 0; rt;
		     rt = rt->u.rt_next, idx++) {
2341
			read_barrier_depends();
Linus Torvalds's avatar
Linus Torvalds committed
2342 2343 2344 2345
			if (idx < s_idx)
				continue;
			skb->dst = dst_clone(&rt->u.dst);
			if (rt_fill_info(skb, NETLINK_CB(cb->skb).pid,
Linus Torvalds's avatar
Linus Torvalds committed
2346 2347
					 cb->nlh->nlmsg_seq,
					 RTM_NEWROUTE, 1) <= 0) {
Linus Torvalds's avatar
Linus Torvalds committed
2348
				dst_release(xchg(&skb->dst, NULL));
2349
				rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
2350 2351 2352 2353
				goto done;
			}
			dst_release(xchg(&skb->dst, NULL));
		}
2354
		rcu_read_unlock();
Linus Torvalds's avatar
Linus Torvalds committed
2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370
	}

done:
	cb->args[0] = h;
	cb->args[1] = idx;
	return skb->len;
}

void ip_rt_multicast_event(struct in_device *in_dev)
{
	rt_cache_flush(0);
}

#ifdef CONFIG_SYSCTL
static int flush_delay;

Linus Torvalds's avatar
Linus Torvalds committed
2371 2372 2373
static int ipv4_sysctl_rtcache_flush(ctl_table *ctl, int write,
					struct file *filp, void *buffer,
					size_t *lenp)
Linus Torvalds's avatar
Linus Torvalds committed
2374 2375 2376 2377 2378
{
	if (write) {
		proc_dointvec(ctl, write, filp, buffer, lenp);
		rt_cache_flush(flush_delay);
		return 0;
Linus Torvalds's avatar
Linus Torvalds committed
2379 2380 2381
	} 

	return -EINVAL;
Linus Torvalds's avatar
Linus Torvalds committed
2382 2383
}

Linus Torvalds's avatar
Linus Torvalds committed
2384 2385 2386 2387
static int ipv4_sysctl_rtcache_flush_strategy(ctl_table *table, int *name,
						int nlen, void *oldval,
						size_t *oldlenp, void *newval,
						size_t newlen, void **context)
Linus Torvalds's avatar
Linus Torvalds committed
2388 2389 2390 2391
{
	int delay;
	if (newlen != sizeof(int))
		return -EINVAL;
Linus Torvalds's avatar
Linus Torvalds committed
2392
	if (get_user(delay, (int *)newval))
Linus Torvalds's avatar
Linus Torvalds committed
2393 2394 2395 2396 2397 2398
		return -EFAULT; 
	rt_cache_flush(delay); 
	return 0;
}

ctl_table ipv4_route_table[] = {
Linus Torvalds's avatar
Linus Torvalds committed
2399
        {
2400 2401 2402 2403 2404 2405 2406
		.ctl_name =	NET_IPV4_ROUTE_FLUSH,
		.procname =	"flush",
		.data =	&flush_delay,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&ipv4_sysctl_rtcache_flush,
		.strategy =	&ipv4_sysctl_rtcache_flush_strategy,
Linus Torvalds's avatar
Linus Torvalds committed
2407 2408
	},
	{
2409 2410 2411 2412 2413 2414 2415
		.ctl_name =	NET_IPV4_ROUTE_MIN_DELAY,
		.procname =	"min_delay",
		.data =	&ip_rt_min_delay,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec_jiffies,
		.strategy =	&sysctl_jiffies,
Linus Torvalds's avatar
Linus Torvalds committed
2416 2417
	},
	{
2418 2419 2420 2421 2422 2423 2424
		.ctl_name =	NET_IPV4_ROUTE_MAX_DELAY,
		.procname =	"max_delay",
		.data =	&ip_rt_max_delay,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec_jiffies,
		.strategy =	&sysctl_jiffies,
Linus Torvalds's avatar
Linus Torvalds committed
2425 2426
	},
	{
2427 2428 2429 2430 2431 2432
		.ctl_name =	NET_IPV4_ROUTE_GC_THRESH,
		.procname =	"gc_thresh",
		.data =	&ipv4_dst_ops.gc_thresh,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2433 2434
	},
	{
2435 2436 2437 2438 2439 2440
		.ctl_name =	NET_IPV4_ROUTE_MAX_SIZE,
		.procname =	"max_size",
		.data =	&ip_rt_max_size,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2441 2442
	},
	{
2443 2444 2445 2446 2447 2448 2449
		.ctl_name =	NET_IPV4_ROUTE_GC_MIN_INTERVAL,
		.procname =	"gc_min_interval",
		.data =	&ip_rt_gc_min_interval,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec_jiffies,
		.strategy =	&sysctl_jiffies,
Linus Torvalds's avatar
Linus Torvalds committed
2450 2451
	},
	{
2452 2453 2454 2455 2456 2457 2458
		.ctl_name =	NET_IPV4_ROUTE_GC_TIMEOUT,
		.procname =	"gc_timeout",
		.data =	&ip_rt_gc_timeout,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec_jiffies,
		.strategy =	&sysctl_jiffies,
Linus Torvalds's avatar
Linus Torvalds committed
2459 2460
	},
	{
2461 2462 2463 2464 2465 2466 2467
		.ctl_name =	NET_IPV4_ROUTE_GC_INTERVAL,
		.procname =	"gc_interval",
		.data =	&ip_rt_gc_interval,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec_jiffies,
		.strategy =	&sysctl_jiffies,
Linus Torvalds's avatar
Linus Torvalds committed
2468 2469
	},
	{
2470 2471 2472 2473 2474 2475
		.ctl_name =	NET_IPV4_ROUTE_REDIRECT_LOAD,
		.procname =	"redirect_load",
		.data =	&ip_rt_redirect_load,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2476 2477
	},
	{
2478 2479 2480 2481 2482 2483
		.ctl_name =	NET_IPV4_ROUTE_REDIRECT_NUMBER,
		.procname =	"redirect_number",
		.data =	&ip_rt_redirect_number,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2484 2485
	},
	{
2486 2487 2488 2489 2490 2491
		.ctl_name =	NET_IPV4_ROUTE_REDIRECT_SILENCE,
		.procname =	"redirect_silence",
		.data =	&ip_rt_redirect_silence,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2492 2493
	},
	{
2494 2495 2496 2497 2498 2499
		.ctl_name =	NET_IPV4_ROUTE_ERROR_COST,
		.procname =	"error_cost",
		.data =	&ip_rt_error_cost,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2500 2501
	},
	{
2502 2503 2504 2505 2506 2507
		.ctl_name =	NET_IPV4_ROUTE_ERROR_BURST,
		.procname =	"error_burst",
		.data =	&ip_rt_error_burst,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2508 2509
	},
	{
2510 2511 2512 2513 2514 2515
		.ctl_name =	NET_IPV4_ROUTE_GC_ELASTICITY,
		.procname =	"gc_elasticity",
		.data =	&ip_rt_gc_elasticity,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2516 2517
	},
	{
2518 2519 2520 2521 2522 2523 2524
		.ctl_name =	NET_IPV4_ROUTE_MTU_EXPIRES,
		.procname =	"mtu_expires",
		.data =	&ip_rt_mtu_expires,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec_jiffies,
		.strategy =	&sysctl_jiffies,
Linus Torvalds's avatar
Linus Torvalds committed
2525 2526
	},
	{
2527 2528 2529 2530 2531 2532
		.ctl_name =	NET_IPV4_ROUTE_MIN_PMTU,
		.procname =	"min_pmtu",
		.data =	&ip_rt_min_pmtu,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2533 2534
	},
	{
2535 2536 2537 2538 2539 2540
		.ctl_name =	NET_IPV4_ROUTE_MIN_ADVMSS,
		.procname =	"min_adv_mss",
		.data =	&ip_rt_min_advmss,
		.maxlen =		sizeof(int),
		.mode =	0644,
		.proc_handler =&proc_dointvec,
Linus Torvalds's avatar
Linus Torvalds committed
2541 2542
	},
	 { 0 }
Linus Torvalds's avatar
Linus Torvalds committed
2543 2544 2545 2546 2547 2548
};
#endif

#ifdef CONFIG_NET_CLS_ROUTE
struct ip_rt_acct *ip_rt_acct;

2549 2550 2551
/* This code sucks.  But you should have seen it before! --RR */

/* IP route accounting ptr for this logical cpu number. */
2552
#define IP_RT_ACCT_CPU(i) (ip_rt_acct + i * 256)
2553

2554
#ifdef CONFIG_PROC_FS
Linus Torvalds's avatar
Linus Torvalds committed
2555 2556 2557
static int ip_rt_acct_read(char *buffer, char **start, off_t offset,
			   int length, int *eof, void *data)
{
2558
	unsigned int i;
Linus Torvalds's avatar
Linus Torvalds committed
2559

Linus Torvalds's avatar
Linus Torvalds committed
2560
	if ((offset & 3) || (length & 3))
Linus Torvalds's avatar
Linus Torvalds committed
2561 2562
		return -EIO;

2563 2564 2565 2566 2567
	if (offset >= sizeof(struct ip_rt_acct) * 256) {
		*eof = 1;
		return 0;
	}

Linus Torvalds's avatar
Linus Torvalds committed
2568 2569
	if (offset + length >= sizeof(struct ip_rt_acct) * 256) {
		length = sizeof(struct ip_rt_acct) * 256 - offset;
Linus Torvalds's avatar
Linus Torvalds committed
2570 2571 2572
		*eof = 1;
	}

2573 2574 2575
	/* Copy first cpu. */
	*start = buffer;
	memcpy(buffer, IP_RT_ACCT_CPU(0), length);
Linus Torvalds's avatar
Linus Torvalds committed
2576

2577
	/* Add the other cpus in, one int at a time */
2578
	for (i = 1; i < NR_CPUS; i++) {
2579
		unsigned int j;
2580 2581
		if (!cpu_online(i))
			continue;
2582 2583
		for (j = 0; j < length/4; j++)
			((u32*)buffer)[j] += ((u32*)IP_RT_ACCT_CPU(i))[j];
Linus Torvalds's avatar
Linus Torvalds committed
2584
	}
2585
	return length;
Linus Torvalds's avatar
Linus Torvalds committed
2586
}
2587 2588
#endif /* CONFIG_PROC_FS */
#endif /* CONFIG_NET_CLS_ROUTE */
Linus Torvalds's avatar
Linus Torvalds committed
2589

2590
int __init ip_rt_init(void)
Linus Torvalds's avatar
Linus Torvalds committed
2591
{
2592
	int i, order, goal, rc = 0;
Linus Torvalds's avatar
Linus Torvalds committed
2593 2594

#ifdef CONFIG_NET_CLS_ROUTE
Linus Torvalds's avatar
Linus Torvalds committed
2595
	for (order = 0;
2596
	     (PAGE_SIZE << order) < 256 * sizeof(struct ip_rt_acct) * NR_CPUS; order++)
Linus Torvalds's avatar
Linus Torvalds committed
2597 2598 2599 2600
		/* NOTHING */;
	ip_rt_acct = (struct ip_rt_acct *)__get_free_pages(GFP_KERNEL, order);
	if (!ip_rt_acct)
		panic("IP: failed to allocate ip_rt_acct\n");
Linus Torvalds's avatar
Linus Torvalds committed
2601
	memset(ip_rt_acct, 0, PAGE_SIZE << order);
Linus Torvalds's avatar
Linus Torvalds committed
2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619
#endif

	ipv4_dst_ops.kmem_cachep = kmem_cache_create("ip_dst_cache",
						     sizeof(struct rtable),
						     0, SLAB_HWCACHE_ALIGN,
						     NULL, NULL);

	if (!ipv4_dst_ops.kmem_cachep)
		panic("IP: failed to allocate ip_dst_cache\n");

	goal = num_physpages >> (26 - PAGE_SHIFT);

	for (order = 0; (1UL << order) < goal; order++)
		/* NOTHING */;

	do {
		rt_hash_mask = (1UL << order) * PAGE_SIZE /
			sizeof(struct rt_hash_bucket);
Linus Torvalds's avatar
Linus Torvalds committed
2620
		while (rt_hash_mask & (rt_hash_mask - 1))
Linus Torvalds's avatar
Linus Torvalds committed
2621 2622 2623 2624 2625 2626 2627 2628
			rt_hash_mask--;
		rt_hash_table = (struct rt_hash_bucket *)
			__get_free_pages(GFP_ATOMIC, order);
	} while (rt_hash_table == NULL && --order > 0);

	if (!rt_hash_table)
		panic("Failed to allocate IP route cache hash table\n");

2629
	printk(KERN_INFO "IP: routing cache hash table of %u buckets, %ldKbytes\n",
Linus Torvalds's avatar
Linus Torvalds committed
2630
	       rt_hash_mask,
Linus Torvalds's avatar
Linus Torvalds committed
2631
	       (long) (rt_hash_mask * sizeof(struct rt_hash_bucket)) / 1024);
Linus Torvalds's avatar
Linus Torvalds committed
2632

Linus Torvalds's avatar
Linus Torvalds committed
2633
	for (rt_hash_log = 0; (1 << rt_hash_log) != rt_hash_mask; rt_hash_log++)
Linus Torvalds's avatar
Linus Torvalds committed
2634 2635 2636 2637
		/* NOTHING */;

	rt_hash_mask--;
	for (i = 0; i <= rt_hash_mask; i++) {
2638
		rt_hash_table[i].lock = SPIN_LOCK_UNLOCKED;
Linus Torvalds's avatar
Linus Torvalds committed
2639 2640 2641
		rt_hash_table[i].chain = NULL;
	}

Linus Torvalds's avatar
Linus Torvalds committed
2642 2643
	ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
	ip_rt_max_size = (rt_hash_mask + 1) * 16;
Linus Torvalds's avatar
Linus Torvalds committed
2644 2645 2646 2647

	devinet_init();
	ip_fib_init();

2648
	init_timer(&rt_flush_timer);
Linus Torvalds's avatar
Linus Torvalds committed
2649
	rt_flush_timer.function = rt_run_flush;
2650
	init_timer(&rt_periodic_timer);
Linus Torvalds's avatar
Linus Torvalds committed
2651 2652 2653 2654 2655
	rt_periodic_timer.function = rt_check_expire;

	/* All the timers, started at system startup tend
	   to synchronize. Perturb it a bit.
	 */
Linus Torvalds's avatar
Linus Torvalds committed
2656 2657
	rt_periodic_timer.expires = jiffies + net_random() % ip_rt_gc_interval +
					ip_rt_gc_interval;
Linus Torvalds's avatar
Linus Torvalds committed
2658 2659
	add_timer(&rt_periodic_timer);

2660 2661
	if (rt_cache_proc_init())
		goto out_enomem;
Linus Torvalds's avatar
Linus Torvalds committed
2662
	proc_net_create ("rt_cache_stat", 0, rt_cache_stat_get_info);
Linus Torvalds's avatar
Linus Torvalds committed
2663 2664 2665
#ifdef CONFIG_NET_CLS_ROUTE
	create_proc_read_entry("net/rt_acct", 0, 0, ip_rt_acct_read, NULL);
#endif
2666
	xfrm_init();
2667 2668 2669 2670 2671
out:
	return rc;
out_enomem:
	rc = -ENOMEM;
	goto out;
Linus Torvalds's avatar
Linus Torvalds committed
2672
}