2 * INET An implementation of the TCP/IP protocol suite for the LINUX
3 * operating system. INET is implemented using the BSD Socket
4 * interface as the means of communication with the user level.
6 * ROUTE - implementation of the IP router.
9 * Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
10 * Alan Cox, <gw4pts@gw4pts.ampr.org>
11 * Linus Torvalds, <Linus.Torvalds@helsinki.fi>
12 * Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
15 * Alan Cox : Verify area fixes.
16 * Alan Cox : cli() protects routing changes
17 * Rui Oliveira : ICMP routing table updates
18 * (rco@di.uminho.pt) Routing table insertion and update
19 * Linus Torvalds : Rewrote bits to be sensible
20 * Alan Cox : Added BSD route gw semantics
21 * Alan Cox : Super /proc >4K
22 * Alan Cox : MTU in route table
23 * Alan Cox : MSS actually. Also added the window
25 * Sam Lantinga : Fixed route matching in rt_del()
26 * Alan Cox : Routing cache support.
27 * Alan Cox : Removed compatibility cruft.
28 * Alan Cox : RTF_REJECT support.
29 * Alan Cox : TCP irtt support.
30 * Jonathan Naylor : Added Metric support.
31 * Miquel van Smoorenburg : BSD API fixes.
32 * Miquel van Smoorenburg : Metrics.
33 * Alan Cox : Use __u32 properly
34 * Alan Cox : Aligned routing errors more closely with BSD
35 * our system is still very different.
36 * Alan Cox : Faster /proc handling
37 * Alexey Kuznetsov : Massive rework to support tree based routing,
38 * routing caches and better behaviour.
40 * Olaf Erb : irtt wasn't being copied right.
41 * Bjorn Ekwall : Kerneld route support.
42 * Alan Cox : Multicast fixed (I hope)
43 * Pavel Krauz : Limited broadcast fixed
44 * Mike McLagan : Routing by source
45 * Alexey Kuznetsov : End of old history. Split to fib.c and
46 * route.c and rewritten from scratch.
47 * Andi Kleen : Load-limit warning messages.
48 * Vitaly E. Lavrov : Transparent proxy revived after year coma.
49 * Vitaly E. Lavrov : Race condition in ip_route_input_slow.
50 * Tobias Ringstrom : Uninitialized res.type in ip_route_output_slow.
51 * Vladimir V. Ivanov : IP rule info (flowid) is really useful.
52 * Marc Boucher : routing by fwmark
53 * Robert Olsson : Added rt_cache statistics
54 * Arnaldo C. Melo : Convert proc stuff to seq_file
55 * Eric Dumazet : hashed spinlocks and rt_check_expire() fixes.
56 * Ilia Sotnikov : Ignore TOS on PMTUD and Redirect
57 * Ilia Sotnikov : Removed TOS from hash calculations
59 * This program is free software; you can redistribute it and/or
60 * modify it under the terms of the GNU General Public License
61 * as published by the Free Software Foundation; either version
62 * 2 of the License, or (at your option) any later version.
65 #include <linux/module.h>
66 #include <asm/uaccess.h>
67 #include <asm/system.h>
68 #include <linux/bitops.h>
69 #include <linux/types.h>
70 #include <linux/kernel.h>
72 #include <linux/bootmem.h>
73 #include <linux/string.h>
74 #include <linux/socket.h>
75 #include <linux/sockios.h>
76 #include <linux/errno.h>
78 #include <linux/inet.h>
79 #include <linux/netdevice.h>
80 #include <linux/proc_fs.h>
81 #include <linux/init.h>
82 #include <linux/workqueue.h>
83 #include <linux/skbuff.h>
84 #include <linux/inetdevice.h>
85 #include <linux/igmp.h>
86 #include <linux/pkt_sched.h>
87 #include <linux/mroute.h>
88 #include <linux/netfilter_ipv4.h>
89 #include <linux/random.h>
90 #include <linux/jhash.h>
91 #include <linux/rcupdate.h>
92 #include <linux/times.h>
94 #include <net/net_namespace.h>
95 #include <net/protocol.h>
97 #include <net/route.h>
98 #include <net/inetpeer.h>
100 #include <net/ip_fib.h>
103 #include <net/icmp.h>
104 #include <net/xfrm.h>
105 #include <net/netevent.h>
106 #include <net/rtnetlink.h>
108 #include <linux/sysctl.h>
111 #define RT_FL_TOS(oldflp) \
112 ((u32)(oldflp->fl4_tos & (IPTOS_RT_MASK | RTO_ONLINK)))
114 #define IP_MAX_MTU 0xFFF0
116 #define RT_GC_TIMEOUT (300*HZ)
118 static int ip_rt_max_size;
119 static int ip_rt_gc_timeout __read_mostly = RT_GC_TIMEOUT;
120 static int ip_rt_gc_interval __read_mostly = 60 * HZ;
121 static int ip_rt_gc_min_interval __read_mostly = HZ / 2;
122 static int ip_rt_redirect_number __read_mostly = 9;
123 static int ip_rt_redirect_load __read_mostly = HZ / 50;
124 static int ip_rt_redirect_silence __read_mostly = ((HZ / 50) << (9 + 1));
125 static int ip_rt_error_cost __read_mostly = HZ;
126 static int ip_rt_error_burst __read_mostly = 5 * HZ;
127 static int ip_rt_gc_elasticity __read_mostly = 8;
128 static int ip_rt_mtu_expires __read_mostly = 10 * 60 * HZ;
129 static int ip_rt_min_pmtu __read_mostly = 512 + 20 + 20;
130 static int ip_rt_min_advmss __read_mostly = 256;
131 static int ip_rt_secret_interval __read_mostly = 10 * 60 * HZ;
133 static void rt_worker_func(struct work_struct *work);
134 static DECLARE_DELAYED_WORK(expires_work, rt_worker_func);
137 * Interface to generic destination cache.
140 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie);
141 static void ipv4_dst_destroy(struct dst_entry *dst);
142 static void ipv4_dst_ifdown(struct dst_entry *dst,
143 struct net_device *dev, int how);
144 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst);
145 static void ipv4_link_failure(struct sk_buff *skb);
146 static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu);
147 static int rt_garbage_collect(struct dst_ops *ops);
150 static struct dst_ops ipv4_dst_ops = {
152 .protocol = __constant_htons(ETH_P_IP),
153 .gc = rt_garbage_collect,
154 .check = ipv4_dst_check,
155 .destroy = ipv4_dst_destroy,
156 .ifdown = ipv4_dst_ifdown,
157 .negative_advice = ipv4_negative_advice,
158 .link_failure = ipv4_link_failure,
159 .update_pmtu = ip_rt_update_pmtu,
160 .local_out = __ip_local_out,
161 .entry_size = sizeof(struct rtable),
162 .entries = ATOMIC_INIT(0),
165 #define ECN_OR_COST(class) TC_PRIO_##class
167 const __u8 ip_tos2prio[16] = {
171 ECN_OR_COST(BESTEFFORT),
177 ECN_OR_COST(INTERACTIVE),
179 ECN_OR_COST(INTERACTIVE),
180 TC_PRIO_INTERACTIVE_BULK,
181 ECN_OR_COST(INTERACTIVE_BULK),
182 TC_PRIO_INTERACTIVE_BULK,
183 ECN_OR_COST(INTERACTIVE_BULK)
191 /* The locking scheme is rather straight forward:
193 * 1) Read-Copy Update protects the buckets of the central route hash.
194 * 2) Only writers remove entries, and they hold the lock
195 * as they look at rtable reference counts.
196 * 3) Only readers acquire references to rtable entries,
197 * they do so with atomic increments and with the
201 struct rt_hash_bucket {
202 struct rtable *chain;
204 #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) || \
205 defined(CONFIG_PROVE_LOCKING)
207 * Instead of using one spinlock for each rt_hash_bucket, we use a table of spinlocks
208 * The size of this table is a power of two and depends on the number of CPUS.
209 * (on lockdep we have a quite big spinlock_t, so keep the size down there)
211 #ifdef CONFIG_LOCKDEP
212 # define RT_HASH_LOCK_SZ 256
215 # define RT_HASH_LOCK_SZ 4096
217 # define RT_HASH_LOCK_SZ 2048
219 # define RT_HASH_LOCK_SZ 1024
221 # define RT_HASH_LOCK_SZ 512
223 # define RT_HASH_LOCK_SZ 256
227 static spinlock_t *rt_hash_locks;
228 # define rt_hash_lock_addr(slot) &rt_hash_locks[(slot) & (RT_HASH_LOCK_SZ - 1)]
230 static __init void rt_hash_lock_init(void)
234 rt_hash_locks = kmalloc(sizeof(spinlock_t) * RT_HASH_LOCK_SZ,
237 panic("IP: failed to allocate rt_hash_locks\n");
239 for (i = 0; i < RT_HASH_LOCK_SZ; i++)
240 spin_lock_init(&rt_hash_locks[i]);
243 # define rt_hash_lock_addr(slot) NULL
245 static inline void rt_hash_lock_init(void)
250 static struct rt_hash_bucket *rt_hash_table __read_mostly;
251 static unsigned rt_hash_mask __read_mostly;
252 static unsigned int rt_hash_log __read_mostly;
254 static DEFINE_PER_CPU(struct rt_cache_stat, rt_cache_stat);
255 #define RT_CACHE_STAT_INC(field) \
256 (__raw_get_cpu_var(rt_cache_stat).field++)
258 static inline unsigned int rt_hash(__be32 daddr, __be32 saddr, int idx,
261 return jhash_3words((__force u32)(__be32)(daddr),
262 (__force u32)(__be32)(saddr),
267 static inline int rt_genid(struct net *net)
269 return atomic_read(&net->ipv4.rt_genid);
272 #ifdef CONFIG_PROC_FS
273 struct rt_cache_iter_state {
274 struct seq_net_private p;
279 static struct rtable *rt_cache_get_first(struct seq_file *seq)
281 struct rt_cache_iter_state *st = seq->private;
282 struct rtable *r = NULL;
284 for (st->bucket = rt_hash_mask; st->bucket >= 0; --st->bucket) {
286 r = rcu_dereference(rt_hash_table[st->bucket].chain);
288 if (dev_net(r->u.dst.dev) == seq_file_net(seq) &&
289 r->rt_genid == st->genid)
291 r = rcu_dereference(r->u.dst.rt_next);
293 rcu_read_unlock_bh();
298 static struct rtable *__rt_cache_get_next(struct seq_file *seq,
301 struct rt_cache_iter_state *st = seq->private;
302 r = r->u.dst.rt_next;
304 rcu_read_unlock_bh();
305 if (--st->bucket < 0)
308 r = rt_hash_table[st->bucket].chain;
310 return rcu_dereference(r);
313 static struct rtable *rt_cache_get_next(struct seq_file *seq,
316 struct rt_cache_iter_state *st = seq->private;
317 while ((r = __rt_cache_get_next(seq, r)) != NULL) {
318 if (dev_net(r->u.dst.dev) != seq_file_net(seq))
320 if (r->rt_genid == st->genid)
326 static struct rtable *rt_cache_get_idx(struct seq_file *seq, loff_t pos)
328 struct rtable *r = rt_cache_get_first(seq);
331 while (pos && (r = rt_cache_get_next(seq, r)))
333 return pos ? NULL : r;
336 static void *rt_cache_seq_start(struct seq_file *seq, loff_t *pos)
338 struct rt_cache_iter_state *st = seq->private;
340 return rt_cache_get_idx(seq, *pos - 1);
341 st->genid = rt_genid(seq_file_net(seq));
342 return SEQ_START_TOKEN;
345 static void *rt_cache_seq_next(struct seq_file *seq, void *v, loff_t *pos)
349 if (v == SEQ_START_TOKEN)
350 r = rt_cache_get_first(seq);
352 r = rt_cache_get_next(seq, v);
357 static void rt_cache_seq_stop(struct seq_file *seq, void *v)
359 if (v && v != SEQ_START_TOKEN)
360 rcu_read_unlock_bh();
363 static int rt_cache_seq_show(struct seq_file *seq, void *v)
365 if (v == SEQ_START_TOKEN)
366 seq_printf(seq, "%-127s\n",
367 "Iface\tDestination\tGateway \tFlags\t\tRefCnt\tUse\t"
368 "Metric\tSource\t\tMTU\tWindow\tIRTT\tTOS\tHHRef\t"
371 struct rtable *r = v;
374 seq_printf(seq, "%s\t%08lX\t%08lX\t%8X\t%d\t%u\t%d\t"
375 "%08lX\t%d\t%u\t%u\t%02X\t%d\t%1d\t%08X%n",
376 r->u.dst.dev ? r->u.dst.dev->name : "*",
377 (unsigned long)r->rt_dst, (unsigned long)r->rt_gateway,
378 r->rt_flags, atomic_read(&r->u.dst.__refcnt),
379 r->u.dst.__use, 0, (unsigned long)r->rt_src,
380 (dst_metric(&r->u.dst, RTAX_ADVMSS) ?
381 (int)dst_metric(&r->u.dst, RTAX_ADVMSS) + 40 : 0),
382 dst_metric(&r->u.dst, RTAX_WINDOW),
383 (int)((dst_metric(&r->u.dst, RTAX_RTT) >> 3) +
384 dst_metric(&r->u.dst, RTAX_RTTVAR)),
386 r->u.dst.hh ? atomic_read(&r->u.dst.hh->hh_refcnt) : -1,
387 r->u.dst.hh ? (r->u.dst.hh->hh_output ==
389 r->rt_spec_dst, &len);
391 seq_printf(seq, "%*s\n", 127 - len, "");
396 static const struct seq_operations rt_cache_seq_ops = {
397 .start = rt_cache_seq_start,
398 .next = rt_cache_seq_next,
399 .stop = rt_cache_seq_stop,
400 .show = rt_cache_seq_show,
403 static int rt_cache_seq_open(struct inode *inode, struct file *file)
405 return seq_open_net(inode, file, &rt_cache_seq_ops,
406 sizeof(struct rt_cache_iter_state));
409 static const struct file_operations rt_cache_seq_fops = {
410 .owner = THIS_MODULE,
411 .open = rt_cache_seq_open,
414 .release = seq_release_net,
418 static void *rt_cpu_seq_start(struct seq_file *seq, loff_t *pos)
423 return SEQ_START_TOKEN;
425 for (cpu = *pos-1; cpu < NR_CPUS; ++cpu) {
426 if (!cpu_possible(cpu))
429 return &per_cpu(rt_cache_stat, cpu);
434 static void *rt_cpu_seq_next(struct seq_file *seq, void *v, loff_t *pos)
438 for (cpu = *pos; cpu < NR_CPUS; ++cpu) {
439 if (!cpu_possible(cpu))
442 return &per_cpu(rt_cache_stat, cpu);
448 static void rt_cpu_seq_stop(struct seq_file *seq, void *v)
453 static int rt_cpu_seq_show(struct seq_file *seq, void *v)
455 struct rt_cache_stat *st = v;
457 if (v == SEQ_START_TOKEN) {
458 seq_printf(seq, "entries in_hit in_slow_tot in_slow_mc in_no_route in_brd in_martian_dst in_martian_src out_hit out_slow_tot out_slow_mc gc_total gc_ignored gc_goal_miss gc_dst_overflow in_hlist_search out_hlist_search\n");
462 seq_printf(seq,"%08x %08x %08x %08x %08x %08x %08x %08x "
463 " %08x %08x %08x %08x %08x %08x %08x %08x %08x \n",
464 atomic_read(&ipv4_dst_ops.entries),
487 static const struct seq_operations rt_cpu_seq_ops = {
488 .start = rt_cpu_seq_start,
489 .next = rt_cpu_seq_next,
490 .stop = rt_cpu_seq_stop,
491 .show = rt_cpu_seq_show,
495 static int rt_cpu_seq_open(struct inode *inode, struct file *file)
497 return seq_open(file, &rt_cpu_seq_ops);
500 static const struct file_operations rt_cpu_seq_fops = {
501 .owner = THIS_MODULE,
502 .open = rt_cpu_seq_open,
505 .release = seq_release,
508 #ifdef CONFIG_NET_CLS_ROUTE
509 static int ip_rt_acct_read(char *buffer, char **start, off_t offset,
510 int length, int *eof, void *data)
514 if ((offset & 3) || (length & 3))
517 if (offset >= sizeof(struct ip_rt_acct) * 256) {
522 if (offset + length >= sizeof(struct ip_rt_acct) * 256) {
523 length = sizeof(struct ip_rt_acct) * 256 - offset;
527 offset /= sizeof(u32);
530 u32 *dst = (u32 *) buffer;
533 memset(dst, 0, length);
535 for_each_possible_cpu(i) {
539 src = ((u32 *) per_cpu_ptr(ip_rt_acct, i)) + offset;
540 for (j = 0; j < length/4; j++)
548 static int __net_init ip_rt_do_proc_init(struct net *net)
550 struct proc_dir_entry *pde;
552 pde = proc_net_fops_create(net, "rt_cache", S_IRUGO,
557 pde = proc_create("rt_cache", S_IRUGO,
558 net->proc_net_stat, &rt_cpu_seq_fops);
562 #ifdef CONFIG_NET_CLS_ROUTE
563 pde = create_proc_read_entry("rt_acct", 0, net->proc_net,
564 ip_rt_acct_read, NULL);
570 #ifdef CONFIG_NET_CLS_ROUTE
572 remove_proc_entry("rt_cache", net->proc_net_stat);
575 remove_proc_entry("rt_cache", net->proc_net);
580 static void __net_exit ip_rt_do_proc_exit(struct net *net)
582 remove_proc_entry("rt_cache", net->proc_net_stat);
583 remove_proc_entry("rt_cache", net->proc_net);
584 remove_proc_entry("rt_acct", net->proc_net);
587 static struct pernet_operations ip_rt_proc_ops __net_initdata = {
588 .init = ip_rt_do_proc_init,
589 .exit = ip_rt_do_proc_exit,
592 static int __init ip_rt_proc_init(void)
594 return register_pernet_subsys(&ip_rt_proc_ops);
598 static inline int ip_rt_proc_init(void)
602 #endif /* CONFIG_PROC_FS */
604 static inline void rt_free(struct rtable *rt)
606 call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
609 static inline void rt_drop(struct rtable *rt)
612 call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
615 static inline int rt_fast_clean(struct rtable *rth)
617 /* Kill broadcast/multicast entries very aggresively, if they
618 collide in hash table with more useful entries */
619 return (rth->rt_flags & (RTCF_BROADCAST | RTCF_MULTICAST)) &&
620 rth->fl.iif && rth->u.dst.rt_next;
623 static inline int rt_valuable(struct rtable *rth)
625 return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) ||
629 static int rt_may_expire(struct rtable *rth, unsigned long tmo1, unsigned long tmo2)
634 if (atomic_read(&rth->u.dst.__refcnt))
638 if (rth->u.dst.expires &&
639 time_after_eq(jiffies, rth->u.dst.expires))
642 age = jiffies - rth->u.dst.lastuse;
644 if ((age <= tmo1 && !rt_fast_clean(rth)) ||
645 (age <= tmo2 && rt_valuable(rth)))
651 /* Bits of score are:
653 * 30: not quite useless
654 * 29..0: usage counter
656 static inline u32 rt_score(struct rtable *rt)
658 u32 score = jiffies - rt->u.dst.lastuse;
660 score = ~score & ~(3<<30);
666 !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL)))
672 static inline int compare_keys(struct flowi *fl1, struct flowi *fl2)
674 return ((__force u32)((fl1->nl_u.ip4_u.daddr ^ fl2->nl_u.ip4_u.daddr) |
675 (fl1->nl_u.ip4_u.saddr ^ fl2->nl_u.ip4_u.saddr)) |
676 (fl1->mark ^ fl2->mark) |
677 (*(u16 *)&fl1->nl_u.ip4_u.tos ^
678 *(u16 *)&fl2->nl_u.ip4_u.tos) |
679 (fl1->oif ^ fl2->oif) |
680 (fl1->iif ^ fl2->iif)) == 0;
683 static inline int compare_netns(struct rtable *rt1, struct rtable *rt2)
685 return dev_net(rt1->u.dst.dev) == dev_net(rt2->u.dst.dev);
688 static inline int rt_is_expired(struct rtable *rth)
690 return rth->rt_genid != rt_genid(dev_net(rth->u.dst.dev));
694 * Perform a full scan of hash table and free all entries.
695 * Can be called by a softirq or a process.
696 * In the later case, we want to be reschedule if necessary
698 static void rt_do_flush(int process_context)
701 struct rtable *rth, *next;
702 struct rtable * tail;
704 for (i = 0; i <= rt_hash_mask; i++) {
705 if (process_context && need_resched())
707 rth = rt_hash_table[i].chain;
711 spin_lock_bh(rt_hash_lock_addr(i));
714 struct rtable ** prev, * p;
716 rth = rt_hash_table[i].chain;
718 /* defer releasing the head of the list after spin_unlock */
719 for (tail = rth; tail; tail = tail->u.dst.rt_next)
720 if (!rt_is_expired(tail))
723 rt_hash_table[i].chain = tail;
725 /* call rt_free on entries after the tail requiring flush */
726 prev = &rt_hash_table[i].chain;
727 for (p = *prev; p; p = next) {
728 next = p->u.dst.rt_next;
729 if (!rt_is_expired(p)) {
730 prev = &p->u.dst.rt_next;
738 rth = rt_hash_table[i].chain;
739 rt_hash_table[i].chain = NULL;
742 spin_unlock_bh(rt_hash_lock_addr(i));
744 for (; rth != tail; rth = next) {
745 next = rth->u.dst.rt_next;
751 static void rt_check_expire(void)
753 static unsigned int rover;
754 unsigned int i = rover, goal;
755 struct rtable *rth, **rthp;
758 mult = ((u64)ip_rt_gc_interval) << rt_hash_log;
759 if (ip_rt_gc_timeout > 1)
760 do_div(mult, ip_rt_gc_timeout);
761 goal = (unsigned int)mult;
762 if (goal > rt_hash_mask)
763 goal = rt_hash_mask + 1;
764 for (; goal > 0; goal--) {
765 unsigned long tmo = ip_rt_gc_timeout;
767 i = (i + 1) & rt_hash_mask;
768 rthp = &rt_hash_table[i].chain;
775 spin_lock_bh(rt_hash_lock_addr(i));
776 while ((rth = *rthp) != NULL) {
777 if (rt_is_expired(rth)) {
778 *rthp = rth->u.dst.rt_next;
782 if (rth->u.dst.expires) {
783 /* Entry is expired even if it is in use */
784 if (time_before_eq(jiffies, rth->u.dst.expires)) {
786 rthp = &rth->u.dst.rt_next;
789 } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
791 rthp = &rth->u.dst.rt_next;
795 /* Cleanup aged off entries. */
796 *rthp = rth->u.dst.rt_next;
799 spin_unlock_bh(rt_hash_lock_addr(i));
805 * rt_worker_func() is run in process context.
806 * we call rt_check_expire() to scan part of the hash table
808 static void rt_worker_func(struct work_struct *work)
811 schedule_delayed_work(&expires_work, ip_rt_gc_interval);
815 * Pertubation of rt_genid by a small quantity [1..256]
816 * Using 8 bits of shuffling ensure we can call rt_cache_invalidate()
817 * many times (2^24) without giving recent rt_genid.
818 * Jenkins hash is strong enough that litle changes of rt_genid are OK.
820 static void rt_cache_invalidate(struct net *net)
822 unsigned char shuffle;
824 get_random_bytes(&shuffle, sizeof(shuffle));
825 atomic_add(shuffle + 1U, &net->ipv4.rt_genid);
829 * delay < 0 : invalidate cache (fast : entries will be deleted later)
830 * delay >= 0 : invalidate & flush cache (can be long)
832 void rt_cache_flush(struct net *net, int delay)
834 rt_cache_invalidate(net);
836 rt_do_flush(!in_softirq());
840 * We change rt_genid and let gc do the cleanup
842 static void rt_secret_rebuild(unsigned long __net)
844 struct net *net = (struct net *)__net;
845 rt_cache_invalidate(net);
846 mod_timer(&net->ipv4.rt_secret_timer, jiffies + ip_rt_secret_interval);
850 Short description of GC goals.
852 We want to build algorithm, which will keep routing cache
853 at some equilibrium point, when number of aged off entries
854 is kept approximately equal to newly generated ones.
856 Current expiration strength is variable "expire".
857 We try to adjust it dynamically, so that if networking
858 is idle expires is large enough to keep enough of warm entries,
859 and when load increases it reduces to limit cache size.
862 static int rt_garbage_collect(struct dst_ops *ops)
864 static unsigned long expire = RT_GC_TIMEOUT;
865 static unsigned long last_gc;
867 static int equilibrium;
868 struct rtable *rth, **rthp;
869 unsigned long now = jiffies;
873 * Garbage collection is pretty expensive,
874 * do not make it too frequently.
877 RT_CACHE_STAT_INC(gc_total);
879 if (now - last_gc < ip_rt_gc_min_interval &&
880 atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size) {
881 RT_CACHE_STAT_INC(gc_ignored);
885 /* Calculate number of entries, which we want to expire now. */
886 goal = atomic_read(&ipv4_dst_ops.entries) -
887 (ip_rt_gc_elasticity << rt_hash_log);
889 if (equilibrium < ipv4_dst_ops.gc_thresh)
890 equilibrium = ipv4_dst_ops.gc_thresh;
891 goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
893 equilibrium += min_t(unsigned int, goal >> 1, rt_hash_mask + 1);
894 goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
897 /* We are in dangerous area. Try to reduce cache really
900 goal = max_t(unsigned int, goal >> 1, rt_hash_mask + 1);
901 equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
904 if (now - last_gc >= ip_rt_gc_min_interval)
915 for (i = rt_hash_mask, k = rover; i >= 0; i--) {
916 unsigned long tmo = expire;
918 k = (k + 1) & rt_hash_mask;
919 rthp = &rt_hash_table[k].chain;
920 spin_lock_bh(rt_hash_lock_addr(k));
921 while ((rth = *rthp) != NULL) {
922 if (!rt_is_expired(rth) &&
923 !rt_may_expire(rth, tmo, expire)) {
925 rthp = &rth->u.dst.rt_next;
928 *rthp = rth->u.dst.rt_next;
932 spin_unlock_bh(rt_hash_lock_addr(k));
941 /* Goal is not achieved. We stop process if:
943 - if expire reduced to zero. Otherwise, expire is halfed.
944 - if table is not full.
945 - if we are called from interrupt.
946 - jiffies check is just fallback/debug loop breaker.
947 We will not spin here for long time in any case.
950 RT_CACHE_STAT_INC(gc_goal_miss);
956 #if RT_CACHE_DEBUG >= 2
957 printk(KERN_DEBUG "expire>> %u %d %d %d\n", expire,
958 atomic_read(&ipv4_dst_ops.entries), goal, i);
961 if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
963 } while (!in_softirq() && time_before_eq(jiffies, now));
965 if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
968 printk(KERN_WARNING "dst cache overflow\n");
969 RT_CACHE_STAT_INC(gc_dst_overflow);
973 expire += ip_rt_gc_min_interval;
974 if (expire > ip_rt_gc_timeout ||
975 atomic_read(&ipv4_dst_ops.entries) < ipv4_dst_ops.gc_thresh)
976 expire = ip_rt_gc_timeout;
977 #if RT_CACHE_DEBUG >= 2
978 printk(KERN_DEBUG "expire++ %u %d %d %d\n", expire,
979 atomic_read(&ipv4_dst_ops.entries), goal, rover);
984 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
986 struct rtable *rth, **rthp;
988 struct rtable *cand, **candp;
991 int attempts = !in_softirq();
1000 rthp = &rt_hash_table[hash].chain;
1002 spin_lock_bh(rt_hash_lock_addr(hash));
1003 while ((rth = *rthp) != NULL) {
1004 if (rt_is_expired(rth)) {
1005 *rthp = rth->u.dst.rt_next;
1009 if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) {
1011 *rthp = rth->u.dst.rt_next;
1013 * Since lookup is lockfree, the deletion
1014 * must be visible to another weakly ordered CPU before
1015 * the insertion at the start of the hash chain.
1017 rcu_assign_pointer(rth->u.dst.rt_next,
1018 rt_hash_table[hash].chain);
1020 * Since lookup is lockfree, the update writes
1021 * must be ordered for consistency on SMP.
1023 rcu_assign_pointer(rt_hash_table[hash].chain, rth);
1025 dst_use(&rth->u.dst, now);
1026 spin_unlock_bh(rt_hash_lock_addr(hash));
1033 if (!atomic_read(&rth->u.dst.__refcnt)) {
1034 u32 score = rt_score(rth);
1036 if (score <= min_score) {
1045 rthp = &rth->u.dst.rt_next;
1049 /* ip_rt_gc_elasticity used to be average length of chain
1050 * length, when exceeded gc becomes really aggressive.
1052 * The second limit is less certain. At the moment it allows
1053 * only 2 entries per bucket. We will see.
1055 if (chain_length > ip_rt_gc_elasticity) {
1056 *candp = cand->u.dst.rt_next;
1061 /* Try to bind route to arp only if it is output
1062 route or unicast forwarding path.
1064 if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
1065 int err = arp_bind_neighbour(&rt->u.dst);
1067 spin_unlock_bh(rt_hash_lock_addr(hash));
1069 if (err != -ENOBUFS) {
1074 /* Neighbour tables are full and nothing
1075 can be released. Try to shrink route cache,
1076 it is most likely it holds some neighbour records.
1078 if (attempts-- > 0) {
1079 int saved_elasticity = ip_rt_gc_elasticity;
1080 int saved_int = ip_rt_gc_min_interval;
1081 ip_rt_gc_elasticity = 1;
1082 ip_rt_gc_min_interval = 0;
1083 rt_garbage_collect(&ipv4_dst_ops);
1084 ip_rt_gc_min_interval = saved_int;
1085 ip_rt_gc_elasticity = saved_elasticity;
1089 if (net_ratelimit())
1090 printk(KERN_WARNING "Neighbour table overflow.\n");
1096 rt->u.dst.rt_next = rt_hash_table[hash].chain;
1097 #if RT_CACHE_DEBUG >= 2
1098 if (rt->u.dst.rt_next) {
1100 printk(KERN_DEBUG "rt_cache @%02x: " NIPQUAD_FMT, hash,
1101 NIPQUAD(rt->rt_dst));
1102 for (trt = rt->u.dst.rt_next; trt; trt = trt->u.dst.rt_next)
1103 printk(" . " NIPQUAD_FMT, NIPQUAD(trt->rt_dst));
1107 rt_hash_table[hash].chain = rt;
1108 spin_unlock_bh(rt_hash_lock_addr(hash));
1113 void rt_bind_peer(struct rtable *rt, int create)
1115 static DEFINE_SPINLOCK(rt_peer_lock);
1116 struct inet_peer *peer;
1118 peer = inet_getpeer(rt->rt_dst, create);
1120 spin_lock_bh(&rt_peer_lock);
1121 if (rt->peer == NULL) {
1125 spin_unlock_bh(&rt_peer_lock);
1131 * Peer allocation may fail only in serious out-of-memory conditions. However
1132 * we still can generate some output.
1133 * Random ID selection looks a bit dangerous because we have no chances to
1134 * select ID being unique in a reasonable period of time.
1135 * But broken packet identifier may be better than no packet at all.
1137 static void ip_select_fb_ident(struct iphdr *iph)
1139 static DEFINE_SPINLOCK(ip_fb_id_lock);
1140 static u32 ip_fallback_id;
1143 spin_lock_bh(&ip_fb_id_lock);
1144 salt = secure_ip_id((__force __be32)ip_fallback_id ^ iph->daddr);
1145 iph->id = htons(salt & 0xFFFF);
1146 ip_fallback_id = salt;
1147 spin_unlock_bh(&ip_fb_id_lock);
1150 void __ip_select_ident(struct iphdr *iph, struct dst_entry *dst, int more)
1152 struct rtable *rt = (struct rtable *) dst;
1155 if (rt->peer == NULL)
1156 rt_bind_peer(rt, 1);
1158 /* If peer is attached to destination, it is never detached,
1159 so that we need not to grab a lock to dereference it.
1162 iph->id = htons(inet_getid(rt->peer, more));
1166 printk(KERN_DEBUG "rt_bind_peer(0) @%p\n",
1167 __builtin_return_address(0));
1169 ip_select_fb_ident(iph);
1172 static void rt_del(unsigned hash, struct rtable *rt)
1174 struct rtable **rthp, *aux;
1176 rthp = &rt_hash_table[hash].chain;
1177 spin_lock_bh(rt_hash_lock_addr(hash));
1179 while ((aux = *rthp) != NULL) {
1180 if (aux == rt || rt_is_expired(aux)) {
1181 *rthp = aux->u.dst.rt_next;
1185 rthp = &aux->u.dst.rt_next;
1187 spin_unlock_bh(rt_hash_lock_addr(hash));
1190 void ip_rt_redirect(__be32 old_gw, __be32 daddr, __be32 new_gw,
1191 __be32 saddr, struct net_device *dev)
1194 struct in_device *in_dev = in_dev_get(dev);
1195 struct rtable *rth, **rthp;
1196 __be32 skeys[2] = { saddr, 0 };
1197 int ikeys[2] = { dev->ifindex, 0 };
1198 struct netevent_redirect netevent;
1205 if (new_gw == old_gw || !IN_DEV_RX_REDIRECTS(in_dev)
1206 || ipv4_is_multicast(new_gw) || ipv4_is_lbcast(new_gw)
1207 || ipv4_is_zeronet(new_gw))
1208 goto reject_redirect;
1210 if (!IN_DEV_SHARED_MEDIA(in_dev)) {
1211 if (!inet_addr_onlink(in_dev, new_gw, old_gw))
1212 goto reject_redirect;
1213 if (IN_DEV_SEC_REDIRECTS(in_dev) && ip_fib_check_default(new_gw, dev))
1214 goto reject_redirect;
1216 if (inet_addr_type(net, new_gw) != RTN_UNICAST)
1217 goto reject_redirect;
1220 for (i = 0; i < 2; i++) {
1221 for (k = 0; k < 2; k++) {
1222 unsigned hash = rt_hash(daddr, skeys[i], ikeys[k],
1225 rthp=&rt_hash_table[hash].chain;
1228 while ((rth = rcu_dereference(*rthp)) != NULL) {
1231 if (rth->fl.fl4_dst != daddr ||
1232 rth->fl.fl4_src != skeys[i] ||
1233 rth->fl.oif != ikeys[k] ||
1235 rt_is_expired(rth) ||
1236 !net_eq(dev_net(rth->u.dst.dev), net)) {
1237 rthp = &rth->u.dst.rt_next;
1241 if (rth->rt_dst != daddr ||
1242 rth->rt_src != saddr ||
1244 rth->rt_gateway != old_gw ||
1245 rth->u.dst.dev != dev)
1248 dst_hold(&rth->u.dst);
1251 rt = dst_alloc(&ipv4_dst_ops);
1258 /* Copy all the information. */
1260 INIT_RCU_HEAD(&rt->u.dst.rcu_head);
1261 rt->u.dst.__use = 1;
1262 atomic_set(&rt->u.dst.__refcnt, 1);
1263 rt->u.dst.child = NULL;
1265 dev_hold(rt->u.dst.dev);
1267 in_dev_hold(rt->idev);
1268 rt->u.dst.obsolete = 0;
1269 rt->u.dst.lastuse = jiffies;
1270 rt->u.dst.path = &rt->u.dst;
1271 rt->u.dst.neighbour = NULL;
1272 rt->u.dst.hh = NULL;
1273 rt->u.dst.xfrm = NULL;
1274 rt->rt_genid = rt_genid(net);
1275 rt->rt_flags |= RTCF_REDIRECTED;
1277 /* Gateway is different ... */
1278 rt->rt_gateway = new_gw;
1280 /* Redirect received -> path was valid */
1281 dst_confirm(&rth->u.dst);
1284 atomic_inc(&rt->peer->refcnt);
1286 if (arp_bind_neighbour(&rt->u.dst) ||
1287 !(rt->u.dst.neighbour->nud_state &
1289 if (rt->u.dst.neighbour)
1290 neigh_event_send(rt->u.dst.neighbour, NULL);
1296 netevent.old = &rth->u.dst;
1297 netevent.new = &rt->u.dst;
1298 call_netevent_notifiers(NETEVENT_REDIRECT,
1302 if (!rt_intern_hash(hash, rt, &rt))
1315 #ifdef CONFIG_IP_ROUTE_VERBOSE
1316 if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
1317 printk(KERN_INFO "Redirect from " NIPQUAD_FMT " on %s about "
1318 NIPQUAD_FMT " ignored.\n"
1319 " Advised path = " NIPQUAD_FMT " -> " NIPQUAD_FMT "\n",
1320 NIPQUAD(old_gw), dev->name, NIPQUAD(new_gw),
1321 NIPQUAD(saddr), NIPQUAD(daddr));
1326 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst)
1328 struct rtable *rt = (struct rtable *)dst;
1329 struct dst_entry *ret = dst;
1332 if (dst->obsolete) {
1335 } else if ((rt->rt_flags & RTCF_REDIRECTED) ||
1336 rt->u.dst.expires) {
1337 unsigned hash = rt_hash(rt->fl.fl4_dst, rt->fl.fl4_src,
1339 rt_genid(dev_net(dst->dev)));
1340 #if RT_CACHE_DEBUG >= 1
1341 printk(KERN_DEBUG "ipv4_negative_advice: redirect to "
1342 NIPQUAD_FMT "/%02x dropped\n",
1343 NIPQUAD(rt->rt_dst), rt->fl.fl4_tos);
1354 * 1. The first ip_rt_redirect_number redirects are sent
1355 * with exponential backoff, then we stop sending them at all,
1356 * assuming that the host ignores our redirects.
1357 * 2. If we did not see packets requiring redirects
1358 * during ip_rt_redirect_silence, we assume that the host
1359 * forgot redirected route and start to send redirects again.
1361 * This algorithm is much cheaper and more intelligent than dumb load limiting
1364 * NOTE. Do not forget to inhibit load limiting for redirects (redundant)
1365 * and "frag. need" (breaks PMTU discovery) in icmp.c.
1368 void ip_rt_send_redirect(struct sk_buff *skb)
1370 struct rtable *rt = skb->rtable;
1371 struct in_device *in_dev = in_dev_get(rt->u.dst.dev);
1376 if (!IN_DEV_TX_REDIRECTS(in_dev))
1379 /* No redirected packets during ip_rt_redirect_silence;
1380 * reset the algorithm.
1382 if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence))
1383 rt->u.dst.rate_tokens = 0;
1385 /* Too many ignored redirects; do not send anything
1386 * set u.dst.rate_last to the last seen redirected packet.
1388 if (rt->u.dst.rate_tokens >= ip_rt_redirect_number) {
1389 rt->u.dst.rate_last = jiffies;
1393 /* Check for load limit; set rate_last to the latest sent
1396 if (rt->u.dst.rate_tokens == 0 ||
1398 (rt->u.dst.rate_last +
1399 (ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
1400 icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
1401 rt->u.dst.rate_last = jiffies;
1402 ++rt->u.dst.rate_tokens;
1403 #ifdef CONFIG_IP_ROUTE_VERBOSE
1404 if (IN_DEV_LOG_MARTIANS(in_dev) &&
1405 rt->u.dst.rate_tokens == ip_rt_redirect_number &&
1407 printk(KERN_WARNING "host " NIPQUAD_FMT "/if%d ignores "
1408 "redirects for " NIPQUAD_FMT " to " NIPQUAD_FMT ".\n",
1409 NIPQUAD(rt->rt_src), rt->rt_iif,
1410 NIPQUAD(rt->rt_dst), NIPQUAD(rt->rt_gateway));
1417 static int ip_error(struct sk_buff *skb)
1419 struct rtable *rt = skb->rtable;
1423 switch (rt->u.dst.error) {
1428 code = ICMP_HOST_UNREACH;
1431 code = ICMP_NET_UNREACH;
1432 IP_INC_STATS_BH(IPSTATS_MIB_INNOROUTES);
1435 code = ICMP_PKT_FILTERED;
1440 rt->u.dst.rate_tokens += now - rt->u.dst.rate_last;
1441 if (rt->u.dst.rate_tokens > ip_rt_error_burst)
1442 rt->u.dst.rate_tokens = ip_rt_error_burst;
1443 rt->u.dst.rate_last = now;
1444 if (rt->u.dst.rate_tokens >= ip_rt_error_cost) {
1445 rt->u.dst.rate_tokens -= ip_rt_error_cost;
1446 icmp_send(skb, ICMP_DEST_UNREACH, code, 0);
1449 out: kfree_skb(skb);
1454 * The last two values are not from the RFC but
1455 * are needed for AMPRnet AX.25 paths.
1458 static const unsigned short mtu_plateau[] =
1459 {32000, 17914, 8166, 4352, 2002, 1492, 576, 296, 216, 128 };
1461 static inline unsigned short guess_mtu(unsigned short old_mtu)
1465 for (i = 0; i < ARRAY_SIZE(mtu_plateau); i++)
1466 if (old_mtu > mtu_plateau[i])
1467 return mtu_plateau[i];
1471 unsigned short ip_rt_frag_needed(struct net *net, struct iphdr *iph,
1472 unsigned short new_mtu,
1473 struct net_device *dev)
1476 unsigned short old_mtu = ntohs(iph->tot_len);
1478 int ikeys[2] = { dev->ifindex, 0 };
1479 __be32 skeys[2] = { iph->saddr, 0, };
1480 __be32 daddr = iph->daddr;
1481 unsigned short est_mtu = 0;
1483 if (ipv4_config.no_pmtu_disc)
1486 for (k = 0; k < 2; k++) {
1487 for (i = 0; i < 2; i++) {
1488 unsigned hash = rt_hash(daddr, skeys[i], ikeys[k],
1492 for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
1493 rth = rcu_dereference(rth->u.dst.rt_next)) {
1494 unsigned short mtu = new_mtu;
1496 if (rth->fl.fl4_dst != daddr ||
1497 rth->fl.fl4_src != skeys[i] ||
1498 rth->rt_dst != daddr ||
1499 rth->rt_src != iph->saddr ||
1500 rth->fl.oif != ikeys[k] ||
1502 dst_metric_locked(&rth->u.dst, RTAX_MTU) ||
1503 !net_eq(dev_net(rth->u.dst.dev), net) ||
1504 !rt_is_expired(rth))
1507 if (new_mtu < 68 || new_mtu >= old_mtu) {
1509 /* BSD 4.2 compatibility hack :-( */
1511 old_mtu >= dst_metric(&rth->u.dst, RTAX_MTU) &&
1512 old_mtu >= 68 + (iph->ihl << 2))
1513 old_mtu -= iph->ihl << 2;
1515 mtu = guess_mtu(old_mtu);
1517 if (mtu <= dst_metric(&rth->u.dst, RTAX_MTU)) {
1518 if (mtu < dst_metric(&rth->u.dst, RTAX_MTU)) {
1519 dst_confirm(&rth->u.dst);
1520 if (mtu < ip_rt_min_pmtu) {
1521 mtu = ip_rt_min_pmtu;
1522 rth->u.dst.metrics[RTAX_LOCK-1] |=
1525 rth->u.dst.metrics[RTAX_MTU-1] = mtu;
1526 dst_set_expires(&rth->u.dst,
1535 return est_mtu ? : new_mtu;
1538 static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu)
1540 if (dst_metric(dst, RTAX_MTU) > mtu && mtu >= 68 &&
1541 !(dst_metric_locked(dst, RTAX_MTU))) {
1542 if (mtu < ip_rt_min_pmtu) {
1543 mtu = ip_rt_min_pmtu;
1544 dst->metrics[RTAX_LOCK-1] |= (1 << RTAX_MTU);
1546 dst->metrics[RTAX_MTU-1] = mtu;
1547 dst_set_expires(dst, ip_rt_mtu_expires);
1548 call_netevent_notifiers(NETEVENT_PMTU_UPDATE, dst);
1552 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie)
1557 static void ipv4_dst_destroy(struct dst_entry *dst)
1559 struct rtable *rt = (struct rtable *) dst;
1560 struct inet_peer *peer = rt->peer;
1561 struct in_device *idev = rt->idev;
1574 static void ipv4_dst_ifdown(struct dst_entry *dst, struct net_device *dev,
1577 struct rtable *rt = (struct rtable *) dst;
1578 struct in_device *idev = rt->idev;
1579 if (dev != dev_net(dev)->loopback_dev && idev && idev->dev == dev) {
1580 struct in_device *loopback_idev =
1581 in_dev_get(dev_net(dev)->loopback_dev);
1582 if (loopback_idev) {
1583 rt->idev = loopback_idev;
1589 static void ipv4_link_failure(struct sk_buff *skb)
1593 icmp_send(skb, ICMP_DEST_UNREACH, ICMP_HOST_UNREACH, 0);
1597 dst_set_expires(&rt->u.dst, 0);
1600 static int ip_rt_bug(struct sk_buff *skb)
1602 printk(KERN_DEBUG "ip_rt_bug: " NIPQUAD_FMT " -> " NIPQUAD_FMT ", %s\n",
1603 NIPQUAD(ip_hdr(skb)->saddr), NIPQUAD(ip_hdr(skb)->daddr),
1604 skb->dev ? skb->dev->name : "?");
1610 We do not cache source address of outgoing interface,
1611 because it is used only by IP RR, TS and SRR options,
1612 so that it out of fast path.
1614 BTW remember: "addr" is allowed to be not aligned
1618 void ip_rt_get_source(u8 *addr, struct rtable *rt)
1621 struct fib_result res;
1623 if (rt->fl.iif == 0)
1625 else if (fib_lookup(dev_net(rt->u.dst.dev), &rt->fl, &res) == 0) {
1626 src = FIB_RES_PREFSRC(res);
1629 src = inet_select_addr(rt->u.dst.dev, rt->rt_gateway,
1631 memcpy(addr, &src, 4);
1634 #ifdef CONFIG_NET_CLS_ROUTE
1635 static void set_class_tag(struct rtable *rt, u32 tag)
1637 if (!(rt->u.dst.tclassid & 0xFFFF))
1638 rt->u.dst.tclassid |= tag & 0xFFFF;
1639 if (!(rt->u.dst.tclassid & 0xFFFF0000))
1640 rt->u.dst.tclassid |= tag & 0xFFFF0000;
1644 static void rt_set_nexthop(struct rtable *rt, struct fib_result *res, u32 itag)
1646 struct fib_info *fi = res->fi;
1649 if (FIB_RES_GW(*res) &&
1650 FIB_RES_NH(*res).nh_scope == RT_SCOPE_LINK)
1651 rt->rt_gateway = FIB_RES_GW(*res);
1652 memcpy(rt->u.dst.metrics, fi->fib_metrics,
1653 sizeof(rt->u.dst.metrics));
1654 if (fi->fib_mtu == 0) {
1655 rt->u.dst.metrics[RTAX_MTU-1] = rt->u.dst.dev->mtu;
1656 if (dst_metric_locked(&rt->u.dst, RTAX_MTU) &&
1657 rt->rt_gateway != rt->rt_dst &&
1658 rt->u.dst.dev->mtu > 576)
1659 rt->u.dst.metrics[RTAX_MTU-1] = 576;
1661 #ifdef CONFIG_NET_CLS_ROUTE
1662 rt->u.dst.tclassid = FIB_RES_NH(*res).nh_tclassid;
1665 rt->u.dst.metrics[RTAX_MTU-1]= rt->u.dst.dev->mtu;
1667 if (dst_metric(&rt->u.dst, RTAX_HOPLIMIT) == 0)
1668 rt->u.dst.metrics[RTAX_HOPLIMIT-1] = sysctl_ip_default_ttl;
1669 if (dst_metric(&rt->u.dst, RTAX_MTU) > IP_MAX_MTU)
1670 rt->u.dst.metrics[RTAX_MTU-1] = IP_MAX_MTU;
1671 if (dst_metric(&rt->u.dst, RTAX_ADVMSS) == 0)
1672 rt->u.dst.metrics[RTAX_ADVMSS-1] = max_t(unsigned int, rt->u.dst.dev->mtu - 40,
1674 if (dst_metric(&rt->u.dst, RTAX_ADVMSS) > 65535 - 40)
1675 rt->u.dst.metrics[RTAX_ADVMSS-1] = 65535 - 40;
1677 #ifdef CONFIG_NET_CLS_ROUTE
1678 #ifdef CONFIG_IP_MULTIPLE_TABLES
1679 set_class_tag(rt, fib_rules_tclass(res));
1681 set_class_tag(rt, itag);
1683 rt->rt_type = res->type;
1686 static int ip_route_input_mc(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1687 u8 tos, struct net_device *dev, int our)
1692 struct in_device *in_dev = in_dev_get(dev);
1695 /* Primary sanity checks. */
1700 if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr) ||
1701 ipv4_is_loopback(saddr) || skb->protocol != htons(ETH_P_IP))
1704 if (ipv4_is_zeronet(saddr)) {
1705 if (!ipv4_is_local_multicast(daddr))
1707 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
1708 } else if (fib_validate_source(saddr, 0, tos, 0,
1709 dev, &spec_dst, &itag) < 0)
1712 rth = dst_alloc(&ipv4_dst_ops);
1716 rth->u.dst.output= ip_rt_bug;
1718 atomic_set(&rth->u.dst.__refcnt, 1);
1719 rth->u.dst.flags= DST_HOST;
1720 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1721 rth->u.dst.flags |= DST_NOPOLICY;
1722 rth->fl.fl4_dst = daddr;
1723 rth->rt_dst = daddr;
1724 rth->fl.fl4_tos = tos;
1725 rth->fl.mark = skb->mark;
1726 rth->fl.fl4_src = saddr;
1727 rth->rt_src = saddr;
1728 #ifdef CONFIG_NET_CLS_ROUTE
1729 rth->u.dst.tclassid = itag;
1732 rth->fl.iif = dev->ifindex;
1733 rth->u.dst.dev = init_net.loopback_dev;
1734 dev_hold(rth->u.dst.dev);
1735 rth->idev = in_dev_get(rth->u.dst.dev);
1737 rth->rt_gateway = daddr;
1738 rth->rt_spec_dst= spec_dst;
1739 rth->rt_genid = rt_genid(dev_net(dev));
1740 rth->rt_flags = RTCF_MULTICAST;
1741 rth->rt_type = RTN_MULTICAST;
1743 rth->u.dst.input= ip_local_deliver;
1744 rth->rt_flags |= RTCF_LOCAL;
1747 #ifdef CONFIG_IP_MROUTE
1748 if (!ipv4_is_local_multicast(daddr) && IN_DEV_MFORWARD(in_dev))
1749 rth->u.dst.input = ip_mr_input;
1751 RT_CACHE_STAT_INC(in_slow_mc);
1754 hash = rt_hash(daddr, saddr, dev->ifindex, rt_genid(dev_net(dev)));
1755 return rt_intern_hash(hash, rth, &skb->rtable);
1767 static void ip_handle_martian_source(struct net_device *dev,
1768 struct in_device *in_dev,
1769 struct sk_buff *skb,
1773 RT_CACHE_STAT_INC(in_martian_src);
1774 #ifdef CONFIG_IP_ROUTE_VERBOSE
1775 if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit()) {
1777 * RFC1812 recommendation, if source is martian,
1778 * the only hint is MAC header.
1780 printk(KERN_WARNING "martian source " NIPQUAD_FMT " from "
1781 NIPQUAD_FMT", on dev %s\n",
1782 NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
1783 if (dev->hard_header_len && skb_mac_header_was_set(skb)) {
1785 const unsigned char *p = skb_mac_header(skb);
1786 printk(KERN_WARNING "ll header: ");
1787 for (i = 0; i < dev->hard_header_len; i++, p++) {
1789 if (i < (dev->hard_header_len - 1))
1798 static int __mkroute_input(struct sk_buff *skb,
1799 struct fib_result *res,
1800 struct in_device *in_dev,
1801 __be32 daddr, __be32 saddr, u32 tos,
1802 struct rtable **result)
1807 struct in_device *out_dev;
1812 /* get a working reference to the output device */
1813 out_dev = in_dev_get(FIB_RES_DEV(*res));
1814 if (out_dev == NULL) {
1815 if (net_ratelimit())
1816 printk(KERN_CRIT "Bug in ip_route_input" \
1817 "_slow(). Please, report\n");
1822 err = fib_validate_source(saddr, daddr, tos, FIB_RES_OIF(*res),
1823 in_dev->dev, &spec_dst, &itag);
1825 ip_handle_martian_source(in_dev->dev, in_dev, skb, daddr,
1833 flags |= RTCF_DIRECTSRC;
1835 if (out_dev == in_dev && err &&
1836 (IN_DEV_SHARED_MEDIA(out_dev) ||
1837 inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
1838 flags |= RTCF_DOREDIRECT;
1840 if (skb->protocol != htons(ETH_P_IP)) {
1841 /* Not IP (i.e. ARP). Do not create route, if it is
1842 * invalid for proxy arp. DNAT routes are always valid.
1844 if (out_dev == in_dev) {
1851 rth = dst_alloc(&ipv4_dst_ops);
1857 atomic_set(&rth->u.dst.__refcnt, 1);
1858 rth->u.dst.flags= DST_HOST;
1859 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1860 rth->u.dst.flags |= DST_NOPOLICY;
1861 if (IN_DEV_CONF_GET(out_dev, NOXFRM))
1862 rth->u.dst.flags |= DST_NOXFRM;
1863 rth->fl.fl4_dst = daddr;
1864 rth->rt_dst = daddr;
1865 rth->fl.fl4_tos = tos;
1866 rth->fl.mark = skb->mark;
1867 rth->fl.fl4_src = saddr;
1868 rth->rt_src = saddr;
1869 rth->rt_gateway = daddr;
1871 rth->fl.iif = in_dev->dev->ifindex;
1872 rth->u.dst.dev = (out_dev)->dev;
1873 dev_hold(rth->u.dst.dev);
1874 rth->idev = in_dev_get(rth->u.dst.dev);
1876 rth->rt_spec_dst= spec_dst;
1878 rth->u.dst.input = ip_forward;
1879 rth->u.dst.output = ip_output;
1880 rth->rt_genid = rt_genid(dev_net(rth->u.dst.dev));
1882 rt_set_nexthop(rth, res, itag);
1884 rth->rt_flags = flags;
1889 /* release the working reference to the output device */
1890 in_dev_put(out_dev);
1894 static int ip_mkroute_input(struct sk_buff *skb,
1895 struct fib_result *res,
1896 const struct flowi *fl,
1897 struct in_device *in_dev,
1898 __be32 daddr, __be32 saddr, u32 tos)
1900 struct rtable* rth = NULL;
1904 #ifdef CONFIG_IP_ROUTE_MULTIPATH
1905 if (res->fi && res->fi->fib_nhs > 1 && fl->oif == 0)
1906 fib_select_multipath(fl, res);
1909 /* create a routing cache entry */
1910 err = __mkroute_input(skb, res, in_dev, daddr, saddr, tos, &rth);
1914 /* put it into the cache */
1915 hash = rt_hash(daddr, saddr, fl->iif,
1916 rt_genid(dev_net(rth->u.dst.dev)));
1917 return rt_intern_hash(hash, rth, &skb->rtable);
1921 * NOTE. We drop all the packets that has local source
1922 * addresses, because every properly looped back packet
1923 * must have correct destination already attached by output routine.
1925 * Such approach solves two big problems:
1926 * 1. Not simplex devices are handled properly.
1927 * 2. IP spoofing attempts are filtered with 100% of guarantee.
1930 static int ip_route_input_slow(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1931 u8 tos, struct net_device *dev)
1933 struct fib_result res;
1934 struct in_device *in_dev = in_dev_get(dev);
1935 struct flowi fl = { .nl_u = { .ip4_u =
1939 .scope = RT_SCOPE_UNIVERSE,
1942 .iif = dev->ifindex };
1945 struct rtable * rth;
1950 struct net * net = dev_net(dev);
1952 /* IP on this device is disabled. */
1957 /* Check for the most weird martians, which can be not detected
1961 if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr) ||
1962 ipv4_is_loopback(saddr))
1963 goto martian_source;
1965 if (daddr == htonl(0xFFFFFFFF) || (saddr == 0 && daddr == 0))
1968 /* Accept zero addresses only to limited broadcast;
1969 * I even do not know to fix it or not. Waiting for complains :-)
1971 if (ipv4_is_zeronet(saddr))
1972 goto martian_source;
1974 if (ipv4_is_lbcast(daddr) || ipv4_is_zeronet(daddr) ||
1975 ipv4_is_loopback(daddr))
1976 goto martian_destination;
1979 * Now we are ready to route packet.
1981 if ((err = fib_lookup(net, &fl, &res)) != 0) {
1982 if (!IN_DEV_FORWARD(in_dev))
1988 RT_CACHE_STAT_INC(in_slow_tot);
1990 if (res.type == RTN_BROADCAST)
1993 if (res.type == RTN_LOCAL) {
1995 result = fib_validate_source(saddr, daddr, tos,
1996 net->loopback_dev->ifindex,
1997 dev, &spec_dst, &itag);
1999 goto martian_source;
2001 flags |= RTCF_DIRECTSRC;
2006 if (!IN_DEV_FORWARD(in_dev))
2008 if (res.type != RTN_UNICAST)
2009 goto martian_destination;
2011 err = ip_mkroute_input(skb, &res, &fl, in_dev, daddr, saddr, tos);
2019 if (skb->protocol != htons(ETH_P_IP))
2022 if (ipv4_is_zeronet(saddr))
2023 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
2025 err = fib_validate_source(saddr, 0, tos, 0, dev, &spec_dst,
2028 goto martian_source;
2030 flags |= RTCF_DIRECTSRC;
2032 flags |= RTCF_BROADCAST;
2033 res.type = RTN_BROADCAST;
2034 RT_CACHE_STAT_INC(in_brd);
2037 rth = dst_alloc(&ipv4_dst_ops);
2041 rth->u.dst.output= ip_rt_bug;
2042 rth->rt_genid = rt_genid(net);
2044 atomic_set(&rth->u.dst.__refcnt, 1);
2045 rth->u.dst.flags= DST_HOST;
2046 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2047 rth->u.dst.flags |= DST_NOPOLICY;
2048 rth->fl.fl4_dst = daddr;
2049 rth->rt_dst = daddr;
2050 rth->fl.fl4_tos = tos;
2051 rth->fl.mark = skb->mark;
2052 rth->fl.fl4_src = saddr;
2053 rth->rt_src = saddr;
2054 #ifdef CONFIG_NET_CLS_ROUTE
2055 rth->u.dst.tclassid = itag;
2058 rth->fl.iif = dev->ifindex;
2059 rth->u.dst.dev = net->loopback_dev;
2060 dev_hold(rth->u.dst.dev);
2061 rth->idev = in_dev_get(rth->u.dst.dev);
2062 rth->rt_gateway = daddr;
2063 rth->rt_spec_dst= spec_dst;
2064 rth->u.dst.input= ip_local_deliver;
2065 rth->rt_flags = flags|RTCF_LOCAL;
2066 if (res.type == RTN_UNREACHABLE) {
2067 rth->u.dst.input= ip_error;
2068 rth->u.dst.error= -err;
2069 rth->rt_flags &= ~RTCF_LOCAL;
2071 rth->rt_type = res.type;
2072 hash = rt_hash(daddr, saddr, fl.iif, rt_genid(net));
2073 err = rt_intern_hash(hash, rth, &skb->rtable);
2077 RT_CACHE_STAT_INC(in_no_route);
2078 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_UNIVERSE);
2079 res.type = RTN_UNREACHABLE;
2085 * Do not cache martian addresses: they should be logged (RFC1812)
2087 martian_destination:
2088 RT_CACHE_STAT_INC(in_martian_dst);
2089 #ifdef CONFIG_IP_ROUTE_VERBOSE
2090 if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
2091 printk(KERN_WARNING "martian destination " NIPQUAD_FMT " from "
2092 NIPQUAD_FMT ", dev %s\n",
2093 NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
2097 err = -EHOSTUNREACH;
2109 ip_handle_martian_source(dev, in_dev, skb, daddr, saddr);
2113 int ip_route_input(struct sk_buff *skb, __be32 daddr, __be32 saddr,
2114 u8 tos, struct net_device *dev)
2116 struct rtable * rth;
2118 int iif = dev->ifindex;
2122 tos &= IPTOS_RT_MASK;
2123 hash = rt_hash(daddr, saddr, iif, rt_genid(net));
2126 for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2127 rth = rcu_dereference(rth->u.dst.rt_next)) {
2128 if (((rth->fl.fl4_dst ^ daddr) |
2129 (rth->fl.fl4_src ^ saddr) |
2130 (rth->fl.iif ^ iif) |
2132 (rth->fl.fl4_tos ^ tos)) == 0 &&
2133 rth->fl.mark == skb->mark &&
2134 net_eq(dev_net(rth->u.dst.dev), net) &&
2135 !rt_is_expired(rth)) {
2136 dst_use(&rth->u.dst, jiffies);
2137 RT_CACHE_STAT_INC(in_hit);
2142 RT_CACHE_STAT_INC(in_hlist_search);
2146 /* Multicast recognition logic is moved from route cache to here.
2147 The problem was that too many Ethernet cards have broken/missing
2148 hardware multicast filters :-( As result the host on multicasting
2149 network acquires a lot of useless route cache entries, sort of
2150 SDR messages from all the world. Now we try to get rid of them.
2151 Really, provided software IP multicast filter is organized
2152 reasonably (at least, hashed), it does not result in a slowdown
2153 comparing with route cache reject entries.
2154 Note, that multicast routers are not affected, because
2155 route cache entry is created eventually.
2157 if (ipv4_is_multicast(daddr)) {
2158 struct in_device *in_dev;
2161 if ((in_dev = __in_dev_get_rcu(dev)) != NULL) {
2162 int our = ip_check_mc(in_dev, daddr, saddr,
2163 ip_hdr(skb)->protocol);
2165 #ifdef CONFIG_IP_MROUTE
2166 || (!ipv4_is_local_multicast(daddr) &&
2167 IN_DEV_MFORWARD(in_dev))
2171 return ip_route_input_mc(skb, daddr, saddr,
2178 return ip_route_input_slow(skb, daddr, saddr, tos, dev);
2181 static int __mkroute_output(struct rtable **result,
2182 struct fib_result *res,
2183 const struct flowi *fl,
2184 const struct flowi *oldflp,
2185 struct net_device *dev_out,
2189 struct in_device *in_dev;
2190 u32 tos = RT_FL_TOS(oldflp);
2193 if (ipv4_is_loopback(fl->fl4_src) && !(dev_out->flags&IFF_LOOPBACK))
2196 if (fl->fl4_dst == htonl(0xFFFFFFFF))
2197 res->type = RTN_BROADCAST;
2198 else if (ipv4_is_multicast(fl->fl4_dst))
2199 res->type = RTN_MULTICAST;
2200 else if (ipv4_is_lbcast(fl->fl4_dst) || ipv4_is_zeronet(fl->fl4_dst))
2203 if (dev_out->flags & IFF_LOOPBACK)
2204 flags |= RTCF_LOCAL;
2206 /* get work reference to inet device */
2207 in_dev = in_dev_get(dev_out);
2211 if (res->type == RTN_BROADCAST) {
2212 flags |= RTCF_BROADCAST | RTCF_LOCAL;
2214 fib_info_put(res->fi);
2217 } else if (res->type == RTN_MULTICAST) {
2218 flags |= RTCF_MULTICAST|RTCF_LOCAL;
2219 if (!ip_check_mc(in_dev, oldflp->fl4_dst, oldflp->fl4_src,
2221 flags &= ~RTCF_LOCAL;
2222 /* If multicast route do not exist use
2223 default one, but do not gateway in this case.
2226 if (res->fi && res->prefixlen < 4) {
2227 fib_info_put(res->fi);
2233 rth = dst_alloc(&ipv4_dst_ops);
2239 atomic_set(&rth->u.dst.__refcnt, 1);
2240 rth->u.dst.flags= DST_HOST;
2241 if (IN_DEV_CONF_GET(in_dev, NOXFRM))
2242 rth->u.dst.flags |= DST_NOXFRM;
2243 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2244 rth->u.dst.flags |= DST_NOPOLICY;
2246 rth->fl.fl4_dst = oldflp->fl4_dst;
2247 rth->fl.fl4_tos = tos;
2248 rth->fl.fl4_src = oldflp->fl4_src;
2249 rth->fl.oif = oldflp->oif;
2250 rth->fl.mark = oldflp->mark;
2251 rth->rt_dst = fl->fl4_dst;
2252 rth->rt_src = fl->fl4_src;
2253 rth->rt_iif = oldflp->oif ? : dev_out->ifindex;
2254 /* get references to the devices that are to be hold by the routing
2256 rth->u.dst.dev = dev_out;
2258 rth->idev = in_dev_get(dev_out);
2259 rth->rt_gateway = fl->fl4_dst;
2260 rth->rt_spec_dst= fl->fl4_src;
2262 rth->u.dst.output=ip_output;
2263 rth->rt_genid = rt_genid(dev_net(dev_out));
2265 RT_CACHE_STAT_INC(out_slow_tot);
2267 if (flags & RTCF_LOCAL) {
2268 rth->u.dst.input = ip_local_deliver;
2269 rth->rt_spec_dst = fl->fl4_dst;
2271 if (flags & (RTCF_BROADCAST | RTCF_MULTICAST)) {
2272 rth->rt_spec_dst = fl->fl4_src;
2273 if (flags & RTCF_LOCAL &&
2274 !(dev_out->flags & IFF_LOOPBACK)) {
2275 rth->u.dst.output = ip_mc_output;
2276 RT_CACHE_STAT_INC(out_slow_mc);
2278 #ifdef CONFIG_IP_MROUTE
2279 if (res->type == RTN_MULTICAST) {
2280 if (IN_DEV_MFORWARD(in_dev) &&
2281 !ipv4_is_local_multicast(oldflp->fl4_dst)) {
2282 rth->u.dst.input = ip_mr_input;
2283 rth->u.dst.output = ip_mc_output;
2289 rt_set_nexthop(rth, res, 0);
2291 rth->rt_flags = flags;
2295 /* release work reference to inet device */
2301 static int ip_mkroute_output(struct rtable **rp,
2302 struct fib_result *res,
2303 const struct flowi *fl,
2304 const struct flowi *oldflp,
2305 struct net_device *dev_out,
2308 struct rtable *rth = NULL;
2309 int err = __mkroute_output(&rth, res, fl, oldflp, dev_out, flags);
2312 hash = rt_hash(oldflp->fl4_dst, oldflp->fl4_src, oldflp->oif,
2313 rt_genid(dev_net(dev_out)));
2314 err = rt_intern_hash(hash, rth, rp);
2321 * Major route resolver routine.
2324 static int ip_route_output_slow(struct net *net, struct rtable **rp,
2325 const struct flowi *oldflp)
2327 u32 tos = RT_FL_TOS(oldflp);
2328 struct flowi fl = { .nl_u = { .ip4_u =
2329 { .daddr = oldflp->fl4_dst,
2330 .saddr = oldflp->fl4_src,
2331 .tos = tos & IPTOS_RT_MASK,
2332 .scope = ((tos & RTO_ONLINK) ?
2336 .mark = oldflp->mark,
2337 .iif = net->loopback_dev->ifindex,
2338 .oif = oldflp->oif };
2339 struct fib_result res;
2341 struct net_device *dev_out = NULL;
2347 #ifdef CONFIG_IP_MULTIPLE_TABLES
2351 if (oldflp->fl4_src) {
2353 if (ipv4_is_multicast(oldflp->fl4_src) ||
2354 ipv4_is_lbcast(oldflp->fl4_src) ||
2355 ipv4_is_zeronet(oldflp->fl4_src))
2358 /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
2359 dev_out = ip_dev_find(net, oldflp->fl4_src);
2360 if (dev_out == NULL)
2363 /* I removed check for oif == dev_out->oif here.
2364 It was wrong for two reasons:
2365 1. ip_dev_find(net, saddr) can return wrong iface, if saddr
2366 is assigned to multiple interfaces.
2367 2. Moreover, we are allowed to send packets with saddr
2368 of another iface. --ANK
2371 if (oldflp->oif == 0
2372 && (ipv4_is_multicast(oldflp->fl4_dst) ||
2373 oldflp->fl4_dst == htonl(0xFFFFFFFF))) {
2374 /* Special hack: user can direct multicasts
2375 and limited broadcast via necessary interface
2376 without fiddling with IP_MULTICAST_IF or IP_PKTINFO.
2377 This hack is not just for fun, it allows
2378 vic,vat and friends to work.
2379 They bind socket to loopback, set ttl to zero
2380 and expect that it will work.
2381 From the viewpoint of routing cache they are broken,
2382 because we are not allowed to build multicast path
2383 with loopback source addr (look, routing cache
2384 cannot know, that ttl is zero, so that packet
2385 will not leave this host and route is valid).
2386 Luckily, this hack is good workaround.
2389 fl.oif = dev_out->ifindex;
2399 dev_out = dev_get_by_index(net, oldflp->oif);
2401 if (dev_out == NULL)
2404 /* RACE: Check return value of inet_select_addr instead. */
2405 if (__in_dev_get_rtnl(dev_out) == NULL) {
2407 goto out; /* Wrong error code */
2410 if (ipv4_is_local_multicast(oldflp->fl4_dst) ||
2411 oldflp->fl4_dst == htonl(0xFFFFFFFF)) {
2413 fl.fl4_src = inet_select_addr(dev_out, 0,
2418 if (ipv4_is_multicast(oldflp->fl4_dst))
2419 fl.fl4_src = inet_select_addr(dev_out, 0,
2421 else if (!oldflp->fl4_dst)
2422 fl.fl4_src = inet_select_addr(dev_out, 0,
2428 fl.fl4_dst = fl.fl4_src;
2430 fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
2433 dev_out = net->loopback_dev;
2435 fl.oif = net->loopback_dev->ifindex;
2436 res.type = RTN_LOCAL;
2437 flags |= RTCF_LOCAL;
2441 if (fib_lookup(net, &fl, &res)) {
2444 /* Apparently, routing tables are wrong. Assume,
2445 that the destination is on link.
2448 Because we are allowed to send to iface
2449 even if it has NO routes and NO assigned
2450 addresses. When oif is specified, routing
2451 tables are looked up with only one purpose:
2452 to catch if destination is gatewayed, rather than
2453 direct. Moreover, if MSG_DONTROUTE is set,
2454 we send packet, ignoring both routing tables
2455 and ifaddr state. --ANK
2458 We could make it even if oif is unknown,
2459 likely IPv6, but we do not.
2462 if (fl.fl4_src == 0)
2463 fl.fl4_src = inet_select_addr(dev_out, 0,
2465 res.type = RTN_UNICAST;
2475 if (res.type == RTN_LOCAL) {
2477 fl.fl4_src = fl.fl4_dst;
2480 dev_out = net->loopback_dev;
2482 fl.oif = dev_out->ifindex;
2484 fib_info_put(res.fi);
2486 flags |= RTCF_LOCAL;
2490 #ifdef CONFIG_IP_ROUTE_MULTIPATH
2491 if (res.fi->fib_nhs > 1 && fl.oif == 0)
2492 fib_select_multipath(&fl, &res);
2495 if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
2496 fib_select_default(net, &fl, &res);
2499 fl.fl4_src = FIB_RES_PREFSRC(res);
2503 dev_out = FIB_RES_DEV(res);
2505 fl.oif = dev_out->ifindex;
2509 err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
2519 int __ip_route_output_key(struct net *net, struct rtable **rp,
2520 const struct flowi *flp)
2525 hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif, rt_genid(net));
2528 for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2529 rth = rcu_dereference(rth->u.dst.rt_next)) {
2530 if (rth->fl.fl4_dst == flp->fl4_dst &&
2531 rth->fl.fl4_src == flp->fl4_src &&
2533 rth->fl.oif == flp->oif &&
2534 rth->fl.mark == flp->mark &&
2535 !((rth->fl.fl4_tos ^ flp->fl4_tos) &
2536 (IPTOS_RT_MASK | RTO_ONLINK)) &&
2537 net_eq(dev_net(rth->u.dst.dev), net) &&
2538 !rt_is_expired(rth)) {
2539 dst_use(&rth->u.dst, jiffies);
2540 RT_CACHE_STAT_INC(out_hit);
2541 rcu_read_unlock_bh();
2545 RT_CACHE_STAT_INC(out_hlist_search);
2547 rcu_read_unlock_bh();
2549 return ip_route_output_slow(net, rp, flp);
2552 EXPORT_SYMBOL_GPL(__ip_route_output_key);
2554 static void ipv4_rt_blackhole_update_pmtu(struct dst_entry *dst, u32 mtu)
2558 static struct dst_ops ipv4_dst_blackhole_ops = {
2560 .protocol = __constant_htons(ETH_P_IP),
2561 .destroy = ipv4_dst_destroy,
2562 .check = ipv4_dst_check,
2563 .update_pmtu = ipv4_rt_blackhole_update_pmtu,
2564 .entry_size = sizeof(struct rtable),
2565 .entries = ATOMIC_INIT(0),
2569 static int ipv4_dst_blackhole(struct net *net, struct rtable **rp, struct flowi *flp)
2571 struct rtable *ort = *rp;
2572 struct rtable *rt = (struct rtable *)
2573 dst_alloc(&ipv4_dst_blackhole_ops);
2576 struct dst_entry *new = &rt->u.dst;
2578 atomic_set(&new->__refcnt, 1);
2580 new->input = dst_discard;
2581 new->output = dst_discard;
2582 memcpy(new->metrics, ort->u.dst.metrics, RTAX_MAX*sizeof(u32));
2584 new->dev = ort->u.dst.dev;
2590 rt->idev = ort->idev;
2592 in_dev_hold(rt->idev);
2593 rt->rt_genid = rt_genid(net);
2594 rt->rt_flags = ort->rt_flags;
2595 rt->rt_type = ort->rt_type;
2596 rt->rt_dst = ort->rt_dst;
2597 rt->rt_src = ort->rt_src;
2598 rt->rt_iif = ort->rt_iif;
2599 rt->rt_gateway = ort->rt_gateway;
2600 rt->rt_spec_dst = ort->rt_spec_dst;
2601 rt->peer = ort->peer;
2603 atomic_inc(&rt->peer->refcnt);
2608 dst_release(&(*rp)->u.dst);
2610 return (rt ? 0 : -ENOMEM);
2613 int ip_route_output_flow(struct net *net, struct rtable **rp, struct flowi *flp,
2614 struct sock *sk, int flags)
2618 if ((err = __ip_route_output_key(net, rp, flp)) != 0)
2623 flp->fl4_src = (*rp)->rt_src;
2625 flp->fl4_dst = (*rp)->rt_dst;
2626 err = __xfrm_lookup((struct dst_entry **)rp, flp, sk,
2627 flags ? XFRM_LOOKUP_WAIT : 0);
2628 if (err == -EREMOTE)
2629 err = ipv4_dst_blackhole(net, rp, flp);
2637 EXPORT_SYMBOL_GPL(ip_route_output_flow);
2639 int ip_route_output_key(struct net *net, struct rtable **rp, struct flowi *flp)
2641 return ip_route_output_flow(net, rp, flp, NULL, 0);
2644 static int rt_fill_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
2645 int nowait, unsigned int flags)
2647 struct rtable *rt = skb->rtable;
2649 struct nlmsghdr *nlh;
2651 u32 id = 0, ts = 0, tsage = 0, error;
2653 nlh = nlmsg_put(skb, pid, seq, event, sizeof(*r), flags);
2657 r = nlmsg_data(nlh);
2658 r->rtm_family = AF_INET;
2659 r->rtm_dst_len = 32;
2661 r->rtm_tos = rt->fl.fl4_tos;
2662 r->rtm_table = RT_TABLE_MAIN;
2663 NLA_PUT_U32(skb, RTA_TABLE, RT_TABLE_MAIN);
2664 r->rtm_type = rt->rt_type;
2665 r->rtm_scope = RT_SCOPE_UNIVERSE;
2666 r->rtm_protocol = RTPROT_UNSPEC;
2667 r->rtm_flags = (rt->rt_flags & ~0xFFFF) | RTM_F_CLONED;
2668 if (rt->rt_flags & RTCF_NOTIFY)
2669 r->rtm_flags |= RTM_F_NOTIFY;
2671 NLA_PUT_BE32(skb, RTA_DST, rt->rt_dst);
2673 if (rt->fl.fl4_src) {
2674 r->rtm_src_len = 32;
2675 NLA_PUT_BE32(skb, RTA_SRC, rt->fl.fl4_src);
2678 NLA_PUT_U32(skb, RTA_OIF, rt->u.dst.dev->ifindex);
2679 #ifdef CONFIG_NET_CLS_ROUTE
2680 if (rt->u.dst.tclassid)
2681 NLA_PUT_U32(skb, RTA_FLOW, rt->u.dst.tclassid);
2684 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_spec_dst);
2685 else if (rt->rt_src != rt->fl.fl4_src)
2686 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_src);
2688 if (rt->rt_dst != rt->rt_gateway)
2689 NLA_PUT_BE32(skb, RTA_GATEWAY, rt->rt_gateway);
2691 if (rtnetlink_put_metrics(skb, rt->u.dst.metrics) < 0)
2692 goto nla_put_failure;
2694 error = rt->u.dst.error;
2695 expires = rt->u.dst.expires ? rt->u.dst.expires - jiffies : 0;
2697 id = rt->peer->ip_id_count;
2698 if (rt->peer->tcp_ts_stamp) {
2699 ts = rt->peer->tcp_ts;
2700 tsage = get_seconds() - rt->peer->tcp_ts_stamp;
2705 #ifdef CONFIG_IP_MROUTE
2706 __be32 dst = rt->rt_dst;
2708 if (ipv4_is_multicast(dst) && !ipv4_is_local_multicast(dst) &&
2709 IPV4_DEVCONF_ALL(&init_net, MC_FORWARDING)) {
2710 int err = ipmr_get_route(skb, r, nowait);
2715 goto nla_put_failure;
2717 if (err == -EMSGSIZE)
2718 goto nla_put_failure;
2724 NLA_PUT_U32(skb, RTA_IIF, rt->fl.iif);
2727 if (rtnl_put_cacheinfo(skb, &rt->u.dst, id, ts, tsage,
2728 expires, error) < 0)
2729 goto nla_put_failure;
2731 return nlmsg_end(skb, nlh);
2734 nlmsg_cancel(skb, nlh);
2738 static int inet_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg)
2740 struct net *net = sock_net(in_skb->sk);
2742 struct nlattr *tb[RTA_MAX+1];
2743 struct rtable *rt = NULL;
2748 struct sk_buff *skb;
2750 err = nlmsg_parse(nlh, sizeof(*rtm), tb, RTA_MAX, rtm_ipv4_policy);
2754 rtm = nlmsg_data(nlh);
2756 skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
2762 /* Reserve room for dummy headers, this skb can pass
2763 through good chunk of routing engine.
2765 skb_reset_mac_header(skb);
2766 skb_reset_network_header(skb);
2768 /* Bugfix: need to give ip_route_input enough of an IP header to not gag. */
2769 ip_hdr(skb)->protocol = IPPROTO_ICMP;
2770 skb_reserve(skb, MAX_HEADER + sizeof(struct iphdr));
2772 src = tb[RTA_SRC] ? nla_get_be32(tb[RTA_SRC]) : 0;
2773 dst = tb[RTA_DST] ? nla_get_be32(tb[RTA_DST]) : 0;
2774 iif = tb[RTA_IIF] ? nla_get_u32(tb[RTA_IIF]) : 0;
2777 struct net_device *dev;
2779 dev = __dev_get_by_index(net, iif);
2785 skb->protocol = htons(ETH_P_IP);
2788 err = ip_route_input(skb, dst, src, rtm->rtm_tos, dev);
2792 if (err == 0 && rt->u.dst.error)
2793 err = -rt->u.dst.error;
2800 .tos = rtm->rtm_tos,
2803 .oif = tb[RTA_OIF] ? nla_get_u32(tb[RTA_OIF]) : 0,
2805 err = ip_route_output_key(net, &rt, &fl);
2812 if (rtm->rtm_flags & RTM_F_NOTIFY)
2813 rt->rt_flags |= RTCF_NOTIFY;
2815 err = rt_fill_info(skb, NETLINK_CB(in_skb).pid, nlh->nlmsg_seq,
2816 RTM_NEWROUTE, 0, 0);
2820 err = rtnl_unicast(skb, net, NETLINK_CB(in_skb).pid);
2829 int ip_rt_dump(struct sk_buff *skb, struct netlink_callback *cb)
2836 net = sock_net(skb->sk);
2841 s_idx = idx = cb->args[1];
2842 for (h = s_h; h <= rt_hash_mask; h++) {
2844 for (rt = rcu_dereference(rt_hash_table[h].chain), idx = 0; rt;
2845 rt = rcu_dereference(rt->u.dst.rt_next), idx++) {
2846 if (!net_eq(dev_net(rt->u.dst.dev), net) || idx < s_idx)
2848 if (rt_is_expired(rt))
2850 skb->dst = dst_clone(&rt->u.dst);
2851 if (rt_fill_info(skb, NETLINK_CB(cb->skb).pid,
2852 cb->nlh->nlmsg_seq, RTM_NEWROUTE,
2853 1, NLM_F_MULTI) <= 0) {
2854 dst_release(xchg(&skb->dst, NULL));
2855 rcu_read_unlock_bh();
2858 dst_release(xchg(&skb->dst, NULL));
2860 rcu_read_unlock_bh();
2870 void ip_rt_multicast_event(struct in_device *in_dev)
2872 rt_cache_flush(dev_net(in_dev->dev), 0);
2875 #ifdef CONFIG_SYSCTL
2876 static int ipv4_sysctl_rtcache_flush(ctl_table *__ctl, int write,
2877 struct file *filp, void __user *buffer,
2878 size_t *lenp, loff_t *ppos)
2885 memcpy(&ctl, __ctl, sizeof(ctl));
2886 ctl.data = &flush_delay;
2887 proc_dointvec(&ctl, write, filp, buffer, lenp, ppos);
2889 net = (struct net *)__ctl->extra1;
2890 rt_cache_flush(net, flush_delay);
2897 static int ipv4_sysctl_rtcache_flush_strategy(ctl_table *table,
2900 void __user *oldval,
2901 size_t __user *oldlenp,
2902 void __user *newval,
2907 if (newlen != sizeof(int))
2909 if (get_user(delay, (int __user *)newval))
2911 net = (struct net *)table->extra1;
2912 rt_cache_flush(net, delay);
2916 ctl_table ipv4_route_table[] = {
2918 .ctl_name = NET_IPV4_ROUTE_GC_THRESH,
2919 .procname = "gc_thresh",
2920 .data = &ipv4_dst_ops.gc_thresh,
2921 .maxlen = sizeof(int),
2923 .proc_handler = &proc_dointvec,
2926 .ctl_name = NET_IPV4_ROUTE_MAX_SIZE,
2927 .procname = "max_size",
2928 .data = &ip_rt_max_size,
2929 .maxlen = sizeof(int),
2931 .proc_handler = &proc_dointvec,
2934 /* Deprecated. Use gc_min_interval_ms */
2936 .ctl_name = NET_IPV4_ROUTE_GC_MIN_INTERVAL,
2937 .procname = "gc_min_interval",
2938 .data = &ip_rt_gc_min_interval,
2939 .maxlen = sizeof(int),
2941 .proc_handler = &proc_dointvec_jiffies,
2942 .strategy = &sysctl_jiffies,
2945 .ctl_name = NET_IPV4_ROUTE_GC_MIN_INTERVAL_MS,
2946 .procname = "gc_min_interval_ms",
2947 .data = &ip_rt_gc_min_interval,
2948 .maxlen = sizeof(int),
2950 .proc_handler = &proc_dointvec_ms_jiffies,
2951 .strategy = &sysctl_ms_jiffies,
2954 .ctl_name = NET_IPV4_ROUTE_GC_TIMEOUT,
2955 .procname = "gc_timeout",
2956 .data = &ip_rt_gc_timeout,
2957 .maxlen = sizeof(int),
2959 .proc_handler = &proc_dointvec_jiffies,
2960 .strategy = &sysctl_jiffies,
2963 .ctl_name = NET_IPV4_ROUTE_GC_INTERVAL,
2964 .procname = "gc_interval",
2965 .data = &ip_rt_gc_interval,
2966 .maxlen = sizeof(int),
2968 .proc_handler = &proc_dointvec_jiffies,
2969 .strategy = &sysctl_jiffies,
2972 .ctl_name = NET_IPV4_ROUTE_REDIRECT_LOAD,
2973 .procname = "redirect_load",
2974 .data = &ip_rt_redirect_load,
2975 .maxlen = sizeof(int),
2977 .proc_handler = &proc_dointvec,
2980 .ctl_name = NET_IPV4_ROUTE_REDIRECT_NUMBER,
2981 .procname = "redirect_number",
2982 .data = &ip_rt_redirect_number,
2983 .maxlen = sizeof(int),
2985 .proc_handler = &proc_dointvec,
2988 .ctl_name = NET_IPV4_ROUTE_REDIRECT_SILENCE,
2989 .procname = "redirect_silence",
2990 .data = &ip_rt_redirect_silence,
2991 .maxlen = sizeof(int),
2993 .proc_handler = &proc_dointvec,
2996 .ctl_name = NET_IPV4_ROUTE_ERROR_COST,
2997 .procname = "error_cost",
2998 .data = &ip_rt_error_cost,
2999 .maxlen = sizeof(int),
3001 .proc_handler = &proc_dointvec,
3004 .ctl_name = NET_IPV4_ROUTE_ERROR_BURST,
3005 .procname = "error_burst",
3006 .data = &ip_rt_error_burst,
3007 .maxlen = sizeof(int),
3009 .proc_handler = &proc_dointvec,
3012 .ctl_name = NET_IPV4_ROUTE_GC_ELASTICITY,
3013 .procname = "gc_elasticity",
3014 .data = &ip_rt_gc_elasticity,
3015 .maxlen = sizeof(int),
3017 .proc_handler = &proc_dointvec,
3020 .ctl_name = NET_IPV4_ROUTE_MTU_EXPIRES,
3021 .procname = "mtu_expires",
3022 .data = &ip_rt_mtu_expires,
3023 .maxlen = sizeof(int),
3025 .proc_handler = &proc_dointvec_jiffies,
3026 .strategy = &sysctl_jiffies,
3029 .ctl_name = NET_IPV4_ROUTE_MIN_PMTU,
3030 .procname = "min_pmtu",
3031 .data = &ip_rt_min_pmtu,
3032 .maxlen = sizeof(int),
3034 .proc_handler = &proc_dointvec,
3037 .ctl_name = NET_IPV4_ROUTE_MIN_ADVMSS,
3038 .procname = "min_adv_mss",
3039 .data = &ip_rt_min_advmss,
3040 .maxlen = sizeof(int),
3042 .proc_handler = &proc_dointvec,
3045 .ctl_name = NET_IPV4_ROUTE_SECRET_INTERVAL,
3046 .procname = "secret_interval",
3047 .data = &ip_rt_secret_interval,
3048 .maxlen = sizeof(int),
3050 .proc_handler = &proc_dointvec_jiffies,
3051 .strategy = &sysctl_jiffies,
3056 static __net_initdata struct ctl_path ipv4_route_path[] = {
3057 { .procname = "net", .ctl_name = CTL_NET, },
3058 { .procname = "ipv4", .ctl_name = NET_IPV4, },
3059 { .procname = "route", .ctl_name = NET_IPV4_ROUTE, },
3064 static struct ctl_table ipv4_route_flush_table[] = {
3066 .ctl_name = NET_IPV4_ROUTE_FLUSH,
3067 .procname = "flush",
3068 .maxlen = sizeof(int),
3070 .proc_handler = &ipv4_sysctl_rtcache_flush,
3071 .strategy = &ipv4_sysctl_rtcache_flush_strategy,
3076 static __net_init int sysctl_route_net_init(struct net *net)
3078 struct ctl_table *tbl;
3080 tbl = ipv4_route_flush_table;
3081 if (net != &init_net) {
3082 tbl = kmemdup(tbl, sizeof(ipv4_route_flush_table), GFP_KERNEL);
3086 tbl[0].extra1 = net;
3088 net->ipv4.route_hdr =
3089 register_net_sysctl_table(net, ipv4_route_path, tbl);
3090 if (net->ipv4.route_hdr == NULL)
3095 if (tbl != ipv4_route_flush_table)
3101 static __net_exit void sysctl_route_net_exit(struct net *net)
3103 struct ctl_table *tbl;
3105 tbl = net->ipv4.route_hdr->ctl_table_arg;
3106 unregister_net_sysctl_table(net->ipv4.route_hdr);
3107 BUG_ON(tbl == ipv4_route_flush_table);
3111 static __net_initdata struct pernet_operations sysctl_route_ops = {
3112 .init = sysctl_route_net_init,
3113 .exit = sysctl_route_net_exit,
3118 static __net_init int rt_secret_timer_init(struct net *net)
3120 atomic_set(&net->ipv4.rt_genid,
3121 (int) ((num_physpages ^ (num_physpages>>8)) ^
3122 (jiffies ^ (jiffies >> 7))));
3124 net->ipv4.rt_secret_timer.function = rt_secret_rebuild;
3125 net->ipv4.rt_secret_timer.data = (unsigned long)net;
3126 init_timer_deferrable(&net->ipv4.rt_secret_timer);
3128 net->ipv4.rt_secret_timer.expires =
3129 jiffies + net_random() % ip_rt_secret_interval +
3130 ip_rt_secret_interval;
3131 add_timer(&net->ipv4.rt_secret_timer);
3135 static __net_exit void rt_secret_timer_exit(struct net *net)
3137 del_timer_sync(&net->ipv4.rt_secret_timer);
3140 static __net_initdata struct pernet_operations rt_secret_timer_ops = {
3141 .init = rt_secret_timer_init,
3142 .exit = rt_secret_timer_exit,
3146 #ifdef CONFIG_NET_CLS_ROUTE
3147 struct ip_rt_acct *ip_rt_acct __read_mostly;
3148 #endif /* CONFIG_NET_CLS_ROUTE */
3150 static __initdata unsigned long rhash_entries;
3151 static int __init set_rhash_entries(char *str)
3155 rhash_entries = simple_strtoul(str, &str, 0);
3158 __setup("rhash_entries=", set_rhash_entries);
3160 int __init ip_rt_init(void)
3164 #ifdef CONFIG_NET_CLS_ROUTE
3165 ip_rt_acct = __alloc_percpu(256 * sizeof(struct ip_rt_acct));
3167 panic("IP: failed to allocate ip_rt_acct\n");
3170 ipv4_dst_ops.kmem_cachep =
3171 kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
3172 SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
3174 ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;
3176 rt_hash_table = (struct rt_hash_bucket *)
3177 alloc_large_system_hash("IP route cache",
3178 sizeof(struct rt_hash_bucket),
3180 (num_physpages >= 128 * 1024) ?
3186 memset(rt_hash_table, 0, (rt_hash_mask + 1) * sizeof(struct rt_hash_bucket));
3187 rt_hash_lock_init();
3189 ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
3190 ip_rt_max_size = (rt_hash_mask + 1) * 16;
3195 /* All the timers, started at system startup tend
3196 to synchronize. Perturb it a bit.
3198 schedule_delayed_work(&expires_work,
3199 net_random() % ip_rt_gc_interval + ip_rt_gc_interval);
3201 if (register_pernet_subsys(&rt_secret_timer_ops))
3202 printk(KERN_ERR "Unable to setup rt_secret_timer\n");
3204 if (ip_rt_proc_init())
3205 printk(KERN_ERR "Unable to create route proc files\n");
3210 rtnl_register(PF_INET, RTM_GETROUTE, inet_rtm_getroute, NULL);
3212 #ifdef CONFIG_SYSCTL
3213 register_pernet_subsys(&sysctl_route_ops);
3218 EXPORT_SYMBOL(__ip_select_ident);
3219 EXPORT_SYMBOL(ip_route_input);
3220 EXPORT_SYMBOL(ip_route_output_key);