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.
8 * Version: $Id: route.c,v 1.103 2002/01/12 07:44:09 davem Exp $
11 * Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
12 * Alan Cox, <gw4pts@gw4pts.ampr.org>
13 * Linus Torvalds, <Linus.Torvalds@helsinki.fi>
14 * Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
17 * Alan Cox : Verify area fixes.
18 * Alan Cox : cli() protects routing changes
19 * Rui Oliveira : ICMP routing table updates
20 * (rco@di.uminho.pt) Routing table insertion and update
21 * Linus Torvalds : Rewrote bits to be sensible
22 * Alan Cox : Added BSD route gw semantics
23 * Alan Cox : Super /proc >4K
24 * Alan Cox : MTU in route table
25 * Alan Cox : MSS actually. Also added the window
27 * Sam Lantinga : Fixed route matching in rt_del()
28 * Alan Cox : Routing cache support.
29 * Alan Cox : Removed compatibility cruft.
30 * Alan Cox : RTF_REJECT support.
31 * Alan Cox : TCP irtt support.
32 * Jonathan Naylor : Added Metric support.
33 * Miquel van Smoorenburg : BSD API fixes.
34 * Miquel van Smoorenburg : Metrics.
35 * Alan Cox : Use __u32 properly
36 * Alan Cox : Aligned routing errors more closely with BSD
37 * our system is still very different.
38 * Alan Cox : Faster /proc handling
39 * Alexey Kuznetsov : Massive rework to support tree based routing,
40 * routing caches and better behaviour.
42 * Olaf Erb : irtt wasn't being copied right.
43 * Bjorn Ekwall : Kerneld route support.
44 * Alan Cox : Multicast fixed (I hope)
45 * Pavel Krauz : Limited broadcast fixed
46 * Mike McLagan : Routing by source
47 * Alexey Kuznetsov : End of old history. Split to fib.c and
48 * route.c and rewritten from scratch.
49 * Andi Kleen : Load-limit warning messages.
50 * Vitaly E. Lavrov : Transparent proxy revived after year coma.
51 * Vitaly E. Lavrov : Race condition in ip_route_input_slow.
52 * Tobias Ringstrom : Uninitialized res.type in ip_route_output_slow.
53 * Vladimir V. Ivanov : IP rule info (flowid) is really useful.
54 * Marc Boucher : routing by fwmark
55 * Robert Olsson : Added rt_cache statistics
56 * Arnaldo C. Melo : Convert proc stuff to seq_file
57 * Eric Dumazet : hashed spinlocks and rt_check_expire() fixes.
58 * Ilia Sotnikov : Ignore TOS on PMTUD and Redirect
59 * Ilia Sotnikov : Removed TOS from hash calculations
61 * This program is free software; you can redistribute it and/or
62 * modify it under the terms of the GNU General Public License
63 * as published by the Free Software Foundation; either version
64 * 2 of the License, or (at your option) any later version.
67 #include <linux/module.h>
68 #include <asm/uaccess.h>
69 #include <asm/system.h>
70 #include <linux/bitops.h>
71 #include <linux/types.h>
72 #include <linux/kernel.h>
74 #include <linux/bootmem.h>
75 #include <linux/string.h>
76 #include <linux/socket.h>
77 #include <linux/sockios.h>
78 #include <linux/errno.h>
80 #include <linux/inet.h>
81 #include <linux/netdevice.h>
82 #include <linux/proc_fs.h>
83 #include <linux/init.h>
84 #include <linux/workqueue.h>
85 #include <linux/skbuff.h>
86 #include <linux/inetdevice.h>
87 #include <linux/igmp.h>
88 #include <linux/pkt_sched.h>
89 #include <linux/mroute.h>
90 #include <linux/netfilter_ipv4.h>
91 #include <linux/random.h>
92 #include <linux/jhash.h>
93 #include <linux/rcupdate.h>
94 #include <linux/times.h>
95 #include <net/net_namespace.h>
96 #include <net/protocol.h>
98 #include <net/route.h>
99 #include <net/inetpeer.h>
100 #include <net/sock.h>
101 #include <net/ip_fib.h>
104 #include <net/icmp.h>
105 #include <net/xfrm.h>
106 #include <net/netevent.h>
107 #include <net/rtnetlink.h>
109 #include <linux/sysctl.h>
112 #define RT_FL_TOS(oldflp) \
113 ((u32)(oldflp->fl4_tos & (IPTOS_RT_MASK | RTO_ONLINK)))
115 #define IP_MAX_MTU 0xFFF0
117 #define RT_GC_TIMEOUT (300*HZ)
119 static int ip_rt_min_delay = 2 * HZ;
120 static int ip_rt_max_delay = 10 * HZ;
121 static int ip_rt_max_size;
122 static int ip_rt_gc_timeout = RT_GC_TIMEOUT;
123 static int ip_rt_gc_interval = 60 * HZ;
124 static int ip_rt_gc_min_interval = HZ / 2;
125 static int ip_rt_redirect_number = 9;
126 static int ip_rt_redirect_load = HZ / 50;
127 static int ip_rt_redirect_silence = ((HZ / 50) << (9 + 1));
128 static int ip_rt_error_cost = HZ;
129 static int ip_rt_error_burst = 5 * HZ;
130 static int ip_rt_gc_elasticity = 8;
131 static int ip_rt_mtu_expires = 10 * 60 * HZ;
132 static int ip_rt_min_pmtu = 512 + 20 + 20;
133 static int ip_rt_min_advmss = 256;
134 static int ip_rt_secret_interval = 10 * 60 * HZ;
135 static unsigned long rt_deadline;
137 #define RTprint(a...) printk(KERN_DEBUG a)
139 static struct timer_list rt_flush_timer;
140 static void rt_check_expire(struct work_struct *work);
141 static DECLARE_DELAYED_WORK(expires_work, rt_check_expire);
142 static struct timer_list rt_secret_timer;
145 * Interface to generic destination cache.
148 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie);
149 static void ipv4_dst_destroy(struct dst_entry *dst);
150 static void ipv4_dst_ifdown(struct dst_entry *dst,
151 struct net_device *dev, int how);
152 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst);
153 static void ipv4_link_failure(struct sk_buff *skb);
154 static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu);
155 static int rt_garbage_collect(void);
158 static struct dst_ops ipv4_dst_ops = {
160 .protocol = __constant_htons(ETH_P_IP),
161 .gc = rt_garbage_collect,
162 .check = ipv4_dst_check,
163 .destroy = ipv4_dst_destroy,
164 .ifdown = ipv4_dst_ifdown,
165 .negative_advice = ipv4_negative_advice,
166 .link_failure = ipv4_link_failure,
167 .update_pmtu = ip_rt_update_pmtu,
168 .entry_size = sizeof(struct rtable),
171 #define ECN_OR_COST(class) TC_PRIO_##class
173 const __u8 ip_tos2prio[16] = {
177 ECN_OR_COST(BESTEFFORT),
183 ECN_OR_COST(INTERACTIVE),
185 ECN_OR_COST(INTERACTIVE),
186 TC_PRIO_INTERACTIVE_BULK,
187 ECN_OR_COST(INTERACTIVE_BULK),
188 TC_PRIO_INTERACTIVE_BULK,
189 ECN_OR_COST(INTERACTIVE_BULK)
197 /* The locking scheme is rather straight forward:
199 * 1) Read-Copy Update protects the buckets of the central route hash.
200 * 2) Only writers remove entries, and they hold the lock
201 * as they look at rtable reference counts.
202 * 3) Only readers acquire references to rtable entries,
203 * they do so with atomic increments and with the
207 struct rt_hash_bucket {
208 struct rtable *chain;
210 #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) || \
211 defined(CONFIG_PROVE_LOCKING)
213 * Instead of using one spinlock for each rt_hash_bucket, we use a table of spinlocks
214 * The size of this table is a power of two and depends on the number of CPUS.
215 * (on lockdep we have a quite big spinlock_t, so keep the size down there)
217 #ifdef CONFIG_LOCKDEP
218 # define RT_HASH_LOCK_SZ 256
221 # define RT_HASH_LOCK_SZ 4096
223 # define RT_HASH_LOCK_SZ 2048
225 # define RT_HASH_LOCK_SZ 1024
227 # define RT_HASH_LOCK_SZ 512
229 # define RT_HASH_LOCK_SZ 256
233 static spinlock_t *rt_hash_locks;
234 # define rt_hash_lock_addr(slot) &rt_hash_locks[(slot) & (RT_HASH_LOCK_SZ - 1)]
235 # define rt_hash_lock_init() { \
237 rt_hash_locks = kmalloc(sizeof(spinlock_t) * RT_HASH_LOCK_SZ, GFP_KERNEL); \
238 if (!rt_hash_locks) 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
244 # define rt_hash_lock_init()
247 static struct rt_hash_bucket *rt_hash_table;
248 static unsigned rt_hash_mask;
249 static int rt_hash_log;
250 static unsigned int rt_hash_rnd;
252 static DEFINE_PER_CPU(struct rt_cache_stat, rt_cache_stat);
253 #define RT_CACHE_STAT_INC(field) \
254 (__raw_get_cpu_var(rt_cache_stat).field++)
256 static int rt_intern_hash(unsigned hash, struct rtable *rth,
257 struct rtable **res);
259 static unsigned int rt_hash_code(u32 daddr, u32 saddr)
261 return (jhash_2words(daddr, saddr, rt_hash_rnd)
265 #define rt_hash(daddr, saddr, idx) \
266 rt_hash_code((__force u32)(__be32)(daddr),\
267 (__force u32)(__be32)(saddr) ^ ((idx) << 5))
269 #ifdef CONFIG_PROC_FS
270 struct rt_cache_iter_state {
274 static struct rtable *rt_cache_get_first(struct seq_file *seq)
276 struct rtable *r = NULL;
277 struct rt_cache_iter_state *st = seq->private;
279 for (st->bucket = rt_hash_mask; st->bucket >= 0; --st->bucket) {
281 r = rt_hash_table[st->bucket].chain;
284 rcu_read_unlock_bh();
289 static struct rtable *rt_cache_get_next(struct seq_file *seq, struct rtable *r)
291 struct rt_cache_iter_state *st = rcu_dereference(seq->private);
293 r = r->u.dst.rt_next;
295 rcu_read_unlock_bh();
296 if (--st->bucket < 0)
299 r = rt_hash_table[st->bucket].chain;
304 static struct rtable *rt_cache_get_idx(struct seq_file *seq, loff_t pos)
306 struct rtable *r = rt_cache_get_first(seq);
309 while (pos && (r = rt_cache_get_next(seq, r)))
311 return pos ? NULL : r;
314 static void *rt_cache_seq_start(struct seq_file *seq, loff_t *pos)
316 return *pos ? rt_cache_get_idx(seq, *pos - 1) : SEQ_START_TOKEN;
319 static void *rt_cache_seq_next(struct seq_file *seq, void *v, loff_t *pos)
321 struct rtable *r = NULL;
323 if (v == SEQ_START_TOKEN)
324 r = rt_cache_get_first(seq);
326 r = rt_cache_get_next(seq, v);
331 static void rt_cache_seq_stop(struct seq_file *seq, void *v)
333 if (v && v != SEQ_START_TOKEN)
334 rcu_read_unlock_bh();
337 static int rt_cache_seq_show(struct seq_file *seq, void *v)
339 if (v == SEQ_START_TOKEN)
340 seq_printf(seq, "%-127s\n",
341 "Iface\tDestination\tGateway \tFlags\t\tRefCnt\tUse\t"
342 "Metric\tSource\t\tMTU\tWindow\tIRTT\tTOS\tHHRef\t"
345 struct rtable *r = v;
348 sprintf(temp, "%s\t%08lX\t%08lX\t%8X\t%d\t%u\t%d\t"
349 "%08lX\t%d\t%u\t%u\t%02X\t%d\t%1d\t%08X",
350 r->u.dst.dev ? r->u.dst.dev->name : "*",
351 (unsigned long)r->rt_dst, (unsigned long)r->rt_gateway,
352 r->rt_flags, atomic_read(&r->u.dst.__refcnt),
353 r->u.dst.__use, 0, (unsigned long)r->rt_src,
354 (dst_metric(&r->u.dst, RTAX_ADVMSS) ?
355 (int)dst_metric(&r->u.dst, RTAX_ADVMSS) + 40 : 0),
356 dst_metric(&r->u.dst, RTAX_WINDOW),
357 (int)((dst_metric(&r->u.dst, RTAX_RTT) >> 3) +
358 dst_metric(&r->u.dst, RTAX_RTTVAR)),
360 r->u.dst.hh ? atomic_read(&r->u.dst.hh->hh_refcnt) : -1,
361 r->u.dst.hh ? (r->u.dst.hh->hh_output ==
364 seq_printf(seq, "%-127s\n", temp);
369 static const struct seq_operations rt_cache_seq_ops = {
370 .start = rt_cache_seq_start,
371 .next = rt_cache_seq_next,
372 .stop = rt_cache_seq_stop,
373 .show = rt_cache_seq_show,
376 static int rt_cache_seq_open(struct inode *inode, struct file *file)
378 struct seq_file *seq;
380 struct rt_cache_iter_state *s;
382 s = kzalloc(sizeof(*s), GFP_KERNEL);
385 rc = seq_open(file, &rt_cache_seq_ops);
388 seq = file->private_data;
397 static const struct file_operations rt_cache_seq_fops = {
398 .owner = THIS_MODULE,
399 .open = rt_cache_seq_open,
402 .release = seq_release_private,
406 static void *rt_cpu_seq_start(struct seq_file *seq, loff_t *pos)
411 return SEQ_START_TOKEN;
413 for (cpu = *pos-1; cpu < NR_CPUS; ++cpu) {
414 if (!cpu_possible(cpu))
417 return &per_cpu(rt_cache_stat, cpu);
422 static void *rt_cpu_seq_next(struct seq_file *seq, void *v, loff_t *pos)
426 for (cpu = *pos; cpu < NR_CPUS; ++cpu) {
427 if (!cpu_possible(cpu))
430 return &per_cpu(rt_cache_stat, cpu);
436 static void rt_cpu_seq_stop(struct seq_file *seq, void *v)
441 static int rt_cpu_seq_show(struct seq_file *seq, void *v)
443 struct rt_cache_stat *st = v;
445 if (v == SEQ_START_TOKEN) {
446 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");
450 seq_printf(seq,"%08x %08x %08x %08x %08x %08x %08x %08x "
451 " %08x %08x %08x %08x %08x %08x %08x %08x %08x \n",
452 atomic_read(&ipv4_dst_ops.entries),
475 static const struct seq_operations rt_cpu_seq_ops = {
476 .start = rt_cpu_seq_start,
477 .next = rt_cpu_seq_next,
478 .stop = rt_cpu_seq_stop,
479 .show = rt_cpu_seq_show,
483 static int rt_cpu_seq_open(struct inode *inode, struct file *file)
485 return seq_open(file, &rt_cpu_seq_ops);
488 static const struct file_operations rt_cpu_seq_fops = {
489 .owner = THIS_MODULE,
490 .open = rt_cpu_seq_open,
493 .release = seq_release,
496 #endif /* CONFIG_PROC_FS */
498 static __inline__ void rt_free(struct rtable *rt)
500 call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
503 static __inline__ void rt_drop(struct rtable *rt)
506 call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
509 static __inline__ int rt_fast_clean(struct rtable *rth)
511 /* Kill broadcast/multicast entries very aggresively, if they
512 collide in hash table with more useful entries */
513 return (rth->rt_flags & (RTCF_BROADCAST | RTCF_MULTICAST)) &&
514 rth->fl.iif && rth->u.dst.rt_next;
517 static __inline__ int rt_valuable(struct rtable *rth)
519 return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) ||
523 static int rt_may_expire(struct rtable *rth, unsigned long tmo1, unsigned long tmo2)
528 if (atomic_read(&rth->u.dst.__refcnt))
532 if (rth->u.dst.expires &&
533 time_after_eq(jiffies, rth->u.dst.expires))
536 age = jiffies - rth->u.dst.lastuse;
538 if ((age <= tmo1 && !rt_fast_clean(rth)) ||
539 (age <= tmo2 && rt_valuable(rth)))
545 /* Bits of score are:
547 * 30: not quite useless
548 * 29..0: usage counter
550 static inline u32 rt_score(struct rtable *rt)
552 u32 score = jiffies - rt->u.dst.lastuse;
554 score = ~score & ~(3<<30);
560 !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL)))
566 static inline int compare_keys(struct flowi *fl1, struct flowi *fl2)
568 return ((__force u32)((fl1->nl_u.ip4_u.daddr ^ fl2->nl_u.ip4_u.daddr) |
569 (fl1->nl_u.ip4_u.saddr ^ fl2->nl_u.ip4_u.saddr)) |
570 (fl1->mark ^ fl2->mark) |
571 (*(u16 *)&fl1->nl_u.ip4_u.tos ^
572 *(u16 *)&fl2->nl_u.ip4_u.tos) |
573 (fl1->oif ^ fl2->oif) |
574 (fl1->iif ^ fl2->iif)) == 0;
577 static void rt_check_expire(struct work_struct *work)
579 static unsigned int rover;
580 unsigned int i = rover, goal;
581 struct rtable *rth, **rthp;
584 mult = ((u64)ip_rt_gc_interval) << rt_hash_log;
585 if (ip_rt_gc_timeout > 1)
586 do_div(mult, ip_rt_gc_timeout);
587 goal = (unsigned int)mult;
588 if (goal > rt_hash_mask)
589 goal = rt_hash_mask + 1;
590 for (; goal > 0; goal--) {
591 unsigned long tmo = ip_rt_gc_timeout;
593 i = (i + 1) & rt_hash_mask;
594 rthp = &rt_hash_table[i].chain;
598 spin_lock_bh(rt_hash_lock_addr(i));
599 while ((rth = *rthp) != NULL) {
600 if (rth->u.dst.expires) {
601 /* Entry is expired even if it is in use */
602 if (time_before_eq(jiffies, rth->u.dst.expires)) {
604 rthp = &rth->u.dst.rt_next;
607 } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
609 rthp = &rth->u.dst.rt_next;
613 /* Cleanup aged off entries. */
614 *rthp = rth->u.dst.rt_next;
617 spin_unlock_bh(rt_hash_lock_addr(i));
620 schedule_delayed_work(&expires_work, ip_rt_gc_interval);
623 /* This can run from both BH and non-BH contexts, the latter
624 * in the case of a forced flush event.
626 static void rt_run_flush(unsigned long dummy)
629 struct rtable *rth, *next;
633 get_random_bytes(&rt_hash_rnd, 4);
635 for (i = rt_hash_mask; i >= 0; i--) {
636 spin_lock_bh(rt_hash_lock_addr(i));
637 rth = rt_hash_table[i].chain;
639 rt_hash_table[i].chain = NULL;
640 spin_unlock_bh(rt_hash_lock_addr(i));
642 for (; rth; rth = next) {
643 next = rth->u.dst.rt_next;
649 static DEFINE_SPINLOCK(rt_flush_lock);
651 void rt_cache_flush(int delay)
653 unsigned long now = jiffies;
654 int user_mode = !in_softirq();
657 delay = ip_rt_min_delay;
659 spin_lock_bh(&rt_flush_lock);
661 if (del_timer(&rt_flush_timer) && delay > 0 && rt_deadline) {
662 long tmo = (long)(rt_deadline - now);
664 /* If flush timer is already running
665 and flush request is not immediate (delay > 0):
667 if deadline is not achieved, prolongate timer to "delay",
668 otherwise fire it at deadline time.
671 if (user_mode && tmo < ip_rt_max_delay-ip_rt_min_delay)
679 spin_unlock_bh(&rt_flush_lock);
684 if (rt_deadline == 0)
685 rt_deadline = now + ip_rt_max_delay;
687 mod_timer(&rt_flush_timer, now+delay);
688 spin_unlock_bh(&rt_flush_lock);
691 static void rt_secret_rebuild(unsigned long dummy)
693 unsigned long now = jiffies;
696 mod_timer(&rt_secret_timer, now + ip_rt_secret_interval);
700 Short description of GC goals.
702 We want to build algorithm, which will keep routing cache
703 at some equilibrium point, when number of aged off entries
704 is kept approximately equal to newly generated ones.
706 Current expiration strength is variable "expire".
707 We try to adjust it dynamically, so that if networking
708 is idle expires is large enough to keep enough of warm entries,
709 and when load increases it reduces to limit cache size.
712 static int rt_garbage_collect(void)
714 static unsigned long expire = RT_GC_TIMEOUT;
715 static unsigned long last_gc;
717 static int equilibrium;
718 struct rtable *rth, **rthp;
719 unsigned long now = jiffies;
723 * Garbage collection is pretty expensive,
724 * do not make it too frequently.
727 RT_CACHE_STAT_INC(gc_total);
729 if (now - last_gc < ip_rt_gc_min_interval &&
730 atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size) {
731 RT_CACHE_STAT_INC(gc_ignored);
735 /* Calculate number of entries, which we want to expire now. */
736 goal = atomic_read(&ipv4_dst_ops.entries) -
737 (ip_rt_gc_elasticity << rt_hash_log);
739 if (equilibrium < ipv4_dst_ops.gc_thresh)
740 equilibrium = ipv4_dst_ops.gc_thresh;
741 goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
743 equilibrium += min_t(unsigned int, goal / 2, rt_hash_mask + 1);
744 goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
747 /* We are in dangerous area. Try to reduce cache really
750 goal = max_t(unsigned int, goal / 2, rt_hash_mask + 1);
751 equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
754 if (now - last_gc >= ip_rt_gc_min_interval)
765 for (i = rt_hash_mask, k = rover; i >= 0; i--) {
766 unsigned long tmo = expire;
768 k = (k + 1) & rt_hash_mask;
769 rthp = &rt_hash_table[k].chain;
770 spin_lock_bh(rt_hash_lock_addr(k));
771 while ((rth = *rthp) != NULL) {
772 if (!rt_may_expire(rth, tmo, expire)) {
774 rthp = &rth->u.dst.rt_next;
777 *rthp = rth->u.dst.rt_next;
781 spin_unlock_bh(rt_hash_lock_addr(k));
790 /* Goal is not achieved. We stop process if:
792 - if expire reduced to zero. Otherwise, expire is halfed.
793 - if table is not full.
794 - if we are called from interrupt.
795 - jiffies check is just fallback/debug loop breaker.
796 We will not spin here for long time in any case.
799 RT_CACHE_STAT_INC(gc_goal_miss);
805 #if RT_CACHE_DEBUG >= 2
806 printk(KERN_DEBUG "expire>> %u %d %d %d\n", expire,
807 atomic_read(&ipv4_dst_ops.entries), goal, i);
810 if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
812 } while (!in_softirq() && time_before_eq(jiffies, now));
814 if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
817 printk(KERN_WARNING "dst cache overflow\n");
818 RT_CACHE_STAT_INC(gc_dst_overflow);
822 expire += ip_rt_gc_min_interval;
823 if (expire > ip_rt_gc_timeout ||
824 atomic_read(&ipv4_dst_ops.entries) < ipv4_dst_ops.gc_thresh)
825 expire = ip_rt_gc_timeout;
826 #if RT_CACHE_DEBUG >= 2
827 printk(KERN_DEBUG "expire++ %u %d %d %d\n", expire,
828 atomic_read(&ipv4_dst_ops.entries), goal, rover);
833 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
835 struct rtable *rth, **rthp;
837 struct rtable *cand, **candp;
840 int attempts = !in_softirq();
849 rthp = &rt_hash_table[hash].chain;
851 spin_lock_bh(rt_hash_lock_addr(hash));
852 while ((rth = *rthp) != NULL) {
853 if (compare_keys(&rth->fl, &rt->fl)) {
855 *rthp = rth->u.dst.rt_next;
857 * Since lookup is lockfree, the deletion
858 * must be visible to another weakly ordered CPU before
859 * the insertion at the start of the hash chain.
861 rcu_assign_pointer(rth->u.dst.rt_next,
862 rt_hash_table[hash].chain);
864 * Since lookup is lockfree, the update writes
865 * must be ordered for consistency on SMP.
867 rcu_assign_pointer(rt_hash_table[hash].chain, rth);
870 dst_hold(&rth->u.dst);
871 rth->u.dst.lastuse = now;
872 spin_unlock_bh(rt_hash_lock_addr(hash));
879 if (!atomic_read(&rth->u.dst.__refcnt)) {
880 u32 score = rt_score(rth);
882 if (score <= min_score) {
891 rthp = &rth->u.dst.rt_next;
895 /* ip_rt_gc_elasticity used to be average length of chain
896 * length, when exceeded gc becomes really aggressive.
898 * The second limit is less certain. At the moment it allows
899 * only 2 entries per bucket. We will see.
901 if (chain_length > ip_rt_gc_elasticity) {
902 *candp = cand->u.dst.rt_next;
907 /* Try to bind route to arp only if it is output
908 route or unicast forwarding path.
910 if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
911 int err = arp_bind_neighbour(&rt->u.dst);
913 spin_unlock_bh(rt_hash_lock_addr(hash));
915 if (err != -ENOBUFS) {
920 /* Neighbour tables are full and nothing
921 can be released. Try to shrink route cache,
922 it is most likely it holds some neighbour records.
924 if (attempts-- > 0) {
925 int saved_elasticity = ip_rt_gc_elasticity;
926 int saved_int = ip_rt_gc_min_interval;
927 ip_rt_gc_elasticity = 1;
928 ip_rt_gc_min_interval = 0;
929 rt_garbage_collect();
930 ip_rt_gc_min_interval = saved_int;
931 ip_rt_gc_elasticity = saved_elasticity;
936 printk(KERN_WARNING "Neighbour table overflow.\n");
942 rt->u.dst.rt_next = rt_hash_table[hash].chain;
943 #if RT_CACHE_DEBUG >= 2
944 if (rt->u.dst.rt_next) {
946 printk(KERN_DEBUG "rt_cache @%02x: %u.%u.%u.%u", hash,
947 NIPQUAD(rt->rt_dst));
948 for (trt = rt->u.dst.rt_next; trt; trt = trt->u.dst.rt_next)
949 printk(" . %u.%u.%u.%u", NIPQUAD(trt->rt_dst));
953 rt_hash_table[hash].chain = rt;
954 spin_unlock_bh(rt_hash_lock_addr(hash));
959 void rt_bind_peer(struct rtable *rt, int create)
961 static DEFINE_SPINLOCK(rt_peer_lock);
962 struct inet_peer *peer;
964 peer = inet_getpeer(rt->rt_dst, create);
966 spin_lock_bh(&rt_peer_lock);
967 if (rt->peer == NULL) {
971 spin_unlock_bh(&rt_peer_lock);
977 * Peer allocation may fail only in serious out-of-memory conditions. However
978 * we still can generate some output.
979 * Random ID selection looks a bit dangerous because we have no chances to
980 * select ID being unique in a reasonable period of time.
981 * But broken packet identifier may be better than no packet at all.
983 static void ip_select_fb_ident(struct iphdr *iph)
985 static DEFINE_SPINLOCK(ip_fb_id_lock);
986 static u32 ip_fallback_id;
989 spin_lock_bh(&ip_fb_id_lock);
990 salt = secure_ip_id((__force __be32)ip_fallback_id ^ iph->daddr);
991 iph->id = htons(salt & 0xFFFF);
992 ip_fallback_id = salt;
993 spin_unlock_bh(&ip_fb_id_lock);
996 void __ip_select_ident(struct iphdr *iph, struct dst_entry *dst, int more)
998 struct rtable *rt = (struct rtable *) dst;
1001 if (rt->peer == NULL)
1002 rt_bind_peer(rt, 1);
1004 /* If peer is attached to destination, it is never detached,
1005 so that we need not to grab a lock to dereference it.
1008 iph->id = htons(inet_getid(rt->peer, more));
1012 printk(KERN_DEBUG "rt_bind_peer(0) @%p\n",
1013 __builtin_return_address(0));
1015 ip_select_fb_ident(iph);
1018 static void rt_del(unsigned hash, struct rtable *rt)
1020 struct rtable **rthp;
1022 spin_lock_bh(rt_hash_lock_addr(hash));
1024 for (rthp = &rt_hash_table[hash].chain; *rthp;
1025 rthp = &(*rthp)->u.dst.rt_next)
1027 *rthp = rt->u.dst.rt_next;
1031 spin_unlock_bh(rt_hash_lock_addr(hash));
1034 void ip_rt_redirect(__be32 old_gw, __be32 daddr, __be32 new_gw,
1035 __be32 saddr, struct net_device *dev)
1038 struct in_device *in_dev = in_dev_get(dev);
1039 struct rtable *rth, **rthp;
1040 __be32 skeys[2] = { saddr, 0 };
1041 int ikeys[2] = { dev->ifindex, 0 };
1042 struct netevent_redirect netevent;
1047 if (new_gw == old_gw || !IN_DEV_RX_REDIRECTS(in_dev)
1048 || MULTICAST(new_gw) || BADCLASS(new_gw) || ZERONET(new_gw))
1049 goto reject_redirect;
1051 if (!IN_DEV_SHARED_MEDIA(in_dev)) {
1052 if (!inet_addr_onlink(in_dev, new_gw, old_gw))
1053 goto reject_redirect;
1054 if (IN_DEV_SEC_REDIRECTS(in_dev) && ip_fib_check_default(new_gw, dev))
1055 goto reject_redirect;
1057 if (inet_addr_type(new_gw) != RTN_UNICAST)
1058 goto reject_redirect;
1061 for (i = 0; i < 2; i++) {
1062 for (k = 0; k < 2; k++) {
1063 unsigned hash = rt_hash(daddr, skeys[i], ikeys[k]);
1065 rthp=&rt_hash_table[hash].chain;
1068 while ((rth = rcu_dereference(*rthp)) != NULL) {
1071 if (rth->fl.fl4_dst != daddr ||
1072 rth->fl.fl4_src != skeys[i] ||
1073 rth->fl.oif != ikeys[k] ||
1075 rthp = &rth->u.dst.rt_next;
1079 if (rth->rt_dst != daddr ||
1080 rth->rt_src != saddr ||
1082 rth->rt_gateway != old_gw ||
1083 rth->u.dst.dev != dev)
1086 dst_hold(&rth->u.dst);
1089 rt = dst_alloc(&ipv4_dst_ops);
1096 /* Copy all the information. */
1098 INIT_RCU_HEAD(&rt->u.dst.rcu_head);
1099 rt->u.dst.__use = 1;
1100 atomic_set(&rt->u.dst.__refcnt, 1);
1101 rt->u.dst.child = NULL;
1103 dev_hold(rt->u.dst.dev);
1105 in_dev_hold(rt->idev);
1106 rt->u.dst.obsolete = 0;
1107 rt->u.dst.lastuse = jiffies;
1108 rt->u.dst.path = &rt->u.dst;
1109 rt->u.dst.neighbour = NULL;
1110 rt->u.dst.hh = NULL;
1111 rt->u.dst.xfrm = NULL;
1113 rt->rt_flags |= RTCF_REDIRECTED;
1115 /* Gateway is different ... */
1116 rt->rt_gateway = new_gw;
1118 /* Redirect received -> path was valid */
1119 dst_confirm(&rth->u.dst);
1122 atomic_inc(&rt->peer->refcnt);
1124 if (arp_bind_neighbour(&rt->u.dst) ||
1125 !(rt->u.dst.neighbour->nud_state &
1127 if (rt->u.dst.neighbour)
1128 neigh_event_send(rt->u.dst.neighbour, NULL);
1134 netevent.old = &rth->u.dst;
1135 netevent.new = &rt->u.dst;
1136 call_netevent_notifiers(NETEVENT_REDIRECT,
1140 if (!rt_intern_hash(hash, rt, &rt))
1153 #ifdef CONFIG_IP_ROUTE_VERBOSE
1154 if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
1155 printk(KERN_INFO "Redirect from %u.%u.%u.%u on %s about "
1156 "%u.%u.%u.%u ignored.\n"
1157 " Advised path = %u.%u.%u.%u -> %u.%u.%u.%u\n",
1158 NIPQUAD(old_gw), dev->name, NIPQUAD(new_gw),
1159 NIPQUAD(saddr), NIPQUAD(daddr));
1164 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst)
1166 struct rtable *rt = (struct rtable*)dst;
1167 struct dst_entry *ret = dst;
1170 if (dst->obsolete) {
1173 } else if ((rt->rt_flags & RTCF_REDIRECTED) ||
1174 rt->u.dst.expires) {
1175 unsigned hash = rt_hash(rt->fl.fl4_dst, rt->fl.fl4_src,
1177 #if RT_CACHE_DEBUG >= 1
1178 printk(KERN_DEBUG "ip_rt_advice: redirect to "
1179 "%u.%u.%u.%u/%02x dropped\n",
1180 NIPQUAD(rt->rt_dst), rt->fl.fl4_tos);
1191 * 1. The first ip_rt_redirect_number redirects are sent
1192 * with exponential backoff, then we stop sending them at all,
1193 * assuming that the host ignores our redirects.
1194 * 2. If we did not see packets requiring redirects
1195 * during ip_rt_redirect_silence, we assume that the host
1196 * forgot redirected route and start to send redirects again.
1198 * This algorithm is much cheaper and more intelligent than dumb load limiting
1201 * NOTE. Do not forget to inhibit load limiting for redirects (redundant)
1202 * and "frag. need" (breaks PMTU discovery) in icmp.c.
1205 void ip_rt_send_redirect(struct sk_buff *skb)
1207 struct rtable *rt = (struct rtable*)skb->dst;
1208 struct in_device *in_dev = in_dev_get(rt->u.dst.dev);
1213 if (!IN_DEV_TX_REDIRECTS(in_dev))
1216 /* No redirected packets during ip_rt_redirect_silence;
1217 * reset the algorithm.
1219 if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence))
1220 rt->u.dst.rate_tokens = 0;
1222 /* Too many ignored redirects; do not send anything
1223 * set u.dst.rate_last to the last seen redirected packet.
1225 if (rt->u.dst.rate_tokens >= ip_rt_redirect_number) {
1226 rt->u.dst.rate_last = jiffies;
1230 /* Check for load limit; set rate_last to the latest sent
1233 if (rt->u.dst.rate_tokens == 0 ||
1235 (rt->u.dst.rate_last +
1236 (ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
1237 icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
1238 rt->u.dst.rate_last = jiffies;
1239 ++rt->u.dst.rate_tokens;
1240 #ifdef CONFIG_IP_ROUTE_VERBOSE
1241 if (IN_DEV_LOG_MARTIANS(in_dev) &&
1242 rt->u.dst.rate_tokens == ip_rt_redirect_number &&
1244 printk(KERN_WARNING "host %u.%u.%u.%u/if%d ignores "
1245 "redirects for %u.%u.%u.%u to %u.%u.%u.%u.\n",
1246 NIPQUAD(rt->rt_src), rt->rt_iif,
1247 NIPQUAD(rt->rt_dst), NIPQUAD(rt->rt_gateway));
1254 static int ip_error(struct sk_buff *skb)
1256 struct rtable *rt = (struct rtable*)skb->dst;
1260 switch (rt->u.dst.error) {
1265 code = ICMP_HOST_UNREACH;
1268 code = ICMP_NET_UNREACH;
1271 code = ICMP_PKT_FILTERED;
1276 rt->u.dst.rate_tokens += now - rt->u.dst.rate_last;
1277 if (rt->u.dst.rate_tokens > ip_rt_error_burst)
1278 rt->u.dst.rate_tokens = ip_rt_error_burst;
1279 rt->u.dst.rate_last = now;
1280 if (rt->u.dst.rate_tokens >= ip_rt_error_cost) {
1281 rt->u.dst.rate_tokens -= ip_rt_error_cost;
1282 icmp_send(skb, ICMP_DEST_UNREACH, code, 0);
1285 out: kfree_skb(skb);
1290 * The last two values are not from the RFC but
1291 * are needed for AMPRnet AX.25 paths.
1294 static const unsigned short mtu_plateau[] =
1295 {32000, 17914, 8166, 4352, 2002, 1492, 576, 296, 216, 128 };
1297 static __inline__ unsigned short guess_mtu(unsigned short old_mtu)
1301 for (i = 0; i < ARRAY_SIZE(mtu_plateau); i++)
1302 if (old_mtu > mtu_plateau[i])
1303 return mtu_plateau[i];
1307 unsigned short ip_rt_frag_needed(struct iphdr *iph, unsigned short new_mtu)
1310 unsigned short old_mtu = ntohs(iph->tot_len);
1312 __be32 skeys[2] = { iph->saddr, 0, };
1313 __be32 daddr = iph->daddr;
1314 unsigned short est_mtu = 0;
1316 if (ipv4_config.no_pmtu_disc)
1319 for (i = 0; i < 2; i++) {
1320 unsigned hash = rt_hash(daddr, skeys[i], 0);
1323 for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
1324 rth = rcu_dereference(rth->u.dst.rt_next)) {
1325 if (rth->fl.fl4_dst == daddr &&
1326 rth->fl.fl4_src == skeys[i] &&
1327 rth->rt_dst == daddr &&
1328 rth->rt_src == iph->saddr &&
1330 !(dst_metric_locked(&rth->u.dst, RTAX_MTU))) {
1331 unsigned short mtu = new_mtu;
1333 if (new_mtu < 68 || new_mtu >= old_mtu) {
1335 /* BSD 4.2 compatibility hack :-( */
1337 old_mtu >= rth->u.dst.metrics[RTAX_MTU-1] &&
1338 old_mtu >= 68 + (iph->ihl << 2))
1339 old_mtu -= iph->ihl << 2;
1341 mtu = guess_mtu(old_mtu);
1343 if (mtu <= rth->u.dst.metrics[RTAX_MTU-1]) {
1344 if (mtu < rth->u.dst.metrics[RTAX_MTU-1]) {
1345 dst_confirm(&rth->u.dst);
1346 if (mtu < ip_rt_min_pmtu) {
1347 mtu = ip_rt_min_pmtu;
1348 rth->u.dst.metrics[RTAX_LOCK-1] |=
1351 rth->u.dst.metrics[RTAX_MTU-1] = mtu;
1352 dst_set_expires(&rth->u.dst,
1361 return est_mtu ? : new_mtu;
1364 static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu)
1366 if (dst->metrics[RTAX_MTU-1] > mtu && mtu >= 68 &&
1367 !(dst_metric_locked(dst, RTAX_MTU))) {
1368 if (mtu < ip_rt_min_pmtu) {
1369 mtu = ip_rt_min_pmtu;
1370 dst->metrics[RTAX_LOCK-1] |= (1 << RTAX_MTU);
1372 dst->metrics[RTAX_MTU-1] = mtu;
1373 dst_set_expires(dst, ip_rt_mtu_expires);
1374 call_netevent_notifiers(NETEVENT_PMTU_UPDATE, dst);
1378 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie)
1383 static void ipv4_dst_destroy(struct dst_entry *dst)
1385 struct rtable *rt = (struct rtable *) dst;
1386 struct inet_peer *peer = rt->peer;
1387 struct in_device *idev = rt->idev;
1400 static void ipv4_dst_ifdown(struct dst_entry *dst, struct net_device *dev,
1403 struct rtable *rt = (struct rtable *) dst;
1404 struct in_device *idev = rt->idev;
1405 if (dev != loopback_dev && idev && idev->dev == dev) {
1406 struct in_device *loopback_idev = in_dev_get(loopback_dev);
1407 if (loopback_idev) {
1408 rt->idev = loopback_idev;
1414 static void ipv4_link_failure(struct sk_buff *skb)
1418 icmp_send(skb, ICMP_DEST_UNREACH, ICMP_HOST_UNREACH, 0);
1420 rt = (struct rtable *) skb->dst;
1422 dst_set_expires(&rt->u.dst, 0);
1425 static int ip_rt_bug(struct sk_buff *skb)
1427 printk(KERN_DEBUG "ip_rt_bug: %u.%u.%u.%u -> %u.%u.%u.%u, %s\n",
1428 NIPQUAD(ip_hdr(skb)->saddr), NIPQUAD(ip_hdr(skb)->daddr),
1429 skb->dev ? skb->dev->name : "?");
1435 We do not cache source address of outgoing interface,
1436 because it is used only by IP RR, TS and SRR options,
1437 so that it out of fast path.
1439 BTW remember: "addr" is allowed to be not aligned
1443 void ip_rt_get_source(u8 *addr, struct rtable *rt)
1446 struct fib_result res;
1448 if (rt->fl.iif == 0)
1450 else if (fib_lookup(&rt->fl, &res) == 0) {
1451 src = FIB_RES_PREFSRC(res);
1454 src = inet_select_addr(rt->u.dst.dev, rt->rt_gateway,
1456 memcpy(addr, &src, 4);
1459 #ifdef CONFIG_NET_CLS_ROUTE
1460 static void set_class_tag(struct rtable *rt, u32 tag)
1462 if (!(rt->u.dst.tclassid & 0xFFFF))
1463 rt->u.dst.tclassid |= tag & 0xFFFF;
1464 if (!(rt->u.dst.tclassid & 0xFFFF0000))
1465 rt->u.dst.tclassid |= tag & 0xFFFF0000;
1469 static void rt_set_nexthop(struct rtable *rt, struct fib_result *res, u32 itag)
1471 struct fib_info *fi = res->fi;
1474 if (FIB_RES_GW(*res) &&
1475 FIB_RES_NH(*res).nh_scope == RT_SCOPE_LINK)
1476 rt->rt_gateway = FIB_RES_GW(*res);
1477 memcpy(rt->u.dst.metrics, fi->fib_metrics,
1478 sizeof(rt->u.dst.metrics));
1479 if (fi->fib_mtu == 0) {
1480 rt->u.dst.metrics[RTAX_MTU-1] = rt->u.dst.dev->mtu;
1481 if (rt->u.dst.metrics[RTAX_LOCK-1] & (1 << RTAX_MTU) &&
1482 rt->rt_gateway != rt->rt_dst &&
1483 rt->u.dst.dev->mtu > 576)
1484 rt->u.dst.metrics[RTAX_MTU-1] = 576;
1486 #ifdef CONFIG_NET_CLS_ROUTE
1487 rt->u.dst.tclassid = FIB_RES_NH(*res).nh_tclassid;
1490 rt->u.dst.metrics[RTAX_MTU-1]= rt->u.dst.dev->mtu;
1492 if (rt->u.dst.metrics[RTAX_HOPLIMIT-1] == 0)
1493 rt->u.dst.metrics[RTAX_HOPLIMIT-1] = sysctl_ip_default_ttl;
1494 if (rt->u.dst.metrics[RTAX_MTU-1] > IP_MAX_MTU)
1495 rt->u.dst.metrics[RTAX_MTU-1] = IP_MAX_MTU;
1496 if (rt->u.dst.metrics[RTAX_ADVMSS-1] == 0)
1497 rt->u.dst.metrics[RTAX_ADVMSS-1] = max_t(unsigned int, rt->u.dst.dev->mtu - 40,
1499 if (rt->u.dst.metrics[RTAX_ADVMSS-1] > 65535 - 40)
1500 rt->u.dst.metrics[RTAX_ADVMSS-1] = 65535 - 40;
1502 #ifdef CONFIG_NET_CLS_ROUTE
1503 #ifdef CONFIG_IP_MULTIPLE_TABLES
1504 set_class_tag(rt, fib_rules_tclass(res));
1506 set_class_tag(rt, itag);
1508 rt->rt_type = res->type;
1511 static int ip_route_input_mc(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1512 u8 tos, struct net_device *dev, int our)
1517 struct in_device *in_dev = in_dev_get(dev);
1520 /* Primary sanity checks. */
1525 if (MULTICAST(saddr) || BADCLASS(saddr) || LOOPBACK(saddr) ||
1526 skb->protocol != htons(ETH_P_IP))
1529 if (ZERONET(saddr)) {
1530 if (!LOCAL_MCAST(daddr))
1532 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
1533 } else if (fib_validate_source(saddr, 0, tos, 0,
1534 dev, &spec_dst, &itag) < 0)
1537 rth = dst_alloc(&ipv4_dst_ops);
1541 rth->u.dst.output= ip_rt_bug;
1543 atomic_set(&rth->u.dst.__refcnt, 1);
1544 rth->u.dst.flags= DST_HOST;
1545 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1546 rth->u.dst.flags |= DST_NOPOLICY;
1547 rth->fl.fl4_dst = daddr;
1548 rth->rt_dst = daddr;
1549 rth->fl.fl4_tos = tos;
1550 rth->fl.mark = skb->mark;
1551 rth->fl.fl4_src = saddr;
1552 rth->rt_src = saddr;
1553 #ifdef CONFIG_NET_CLS_ROUTE
1554 rth->u.dst.tclassid = itag;
1557 rth->fl.iif = dev->ifindex;
1558 rth->u.dst.dev = loopback_dev;
1559 dev_hold(rth->u.dst.dev);
1560 rth->idev = in_dev_get(rth->u.dst.dev);
1562 rth->rt_gateway = daddr;
1563 rth->rt_spec_dst= spec_dst;
1564 rth->rt_type = RTN_MULTICAST;
1565 rth->rt_flags = RTCF_MULTICAST;
1567 rth->u.dst.input= ip_local_deliver;
1568 rth->rt_flags |= RTCF_LOCAL;
1571 #ifdef CONFIG_IP_MROUTE
1572 if (!LOCAL_MCAST(daddr) && IN_DEV_MFORWARD(in_dev))
1573 rth->u.dst.input = ip_mr_input;
1575 RT_CACHE_STAT_INC(in_slow_mc);
1578 hash = rt_hash(daddr, saddr, dev->ifindex);
1579 return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);
1591 static void ip_handle_martian_source(struct net_device *dev,
1592 struct in_device *in_dev,
1593 struct sk_buff *skb,
1597 RT_CACHE_STAT_INC(in_martian_src);
1598 #ifdef CONFIG_IP_ROUTE_VERBOSE
1599 if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit()) {
1601 * RFC1812 recommendation, if source is martian,
1602 * the only hint is MAC header.
1604 printk(KERN_WARNING "martian source %u.%u.%u.%u from "
1605 "%u.%u.%u.%u, on dev %s\n",
1606 NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
1607 if (dev->hard_header_len && skb_mac_header_was_set(skb)) {
1609 const unsigned char *p = skb_mac_header(skb);
1610 printk(KERN_WARNING "ll header: ");
1611 for (i = 0; i < dev->hard_header_len; i++, p++) {
1613 if (i < (dev->hard_header_len - 1))
1622 static inline int __mkroute_input(struct sk_buff *skb,
1623 struct fib_result* res,
1624 struct in_device *in_dev,
1625 __be32 daddr, __be32 saddr, u32 tos,
1626 struct rtable **result)
1631 struct in_device *out_dev;
1636 /* get a working reference to the output device */
1637 out_dev = in_dev_get(FIB_RES_DEV(*res));
1638 if (out_dev == NULL) {
1639 if (net_ratelimit())
1640 printk(KERN_CRIT "Bug in ip_route_input" \
1641 "_slow(). Please, report\n");
1646 err = fib_validate_source(saddr, daddr, tos, FIB_RES_OIF(*res),
1647 in_dev->dev, &spec_dst, &itag);
1649 ip_handle_martian_source(in_dev->dev, in_dev, skb, daddr,
1657 flags |= RTCF_DIRECTSRC;
1659 if (out_dev == in_dev && err && !(flags & (RTCF_NAT | RTCF_MASQ)) &&
1660 (IN_DEV_SHARED_MEDIA(out_dev) ||
1661 inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
1662 flags |= RTCF_DOREDIRECT;
1664 if (skb->protocol != htons(ETH_P_IP)) {
1665 /* Not IP (i.e. ARP). Do not create route, if it is
1666 * invalid for proxy arp. DNAT routes are always valid.
1668 if (out_dev == in_dev && !(flags & RTCF_DNAT)) {
1675 rth = dst_alloc(&ipv4_dst_ops);
1681 atomic_set(&rth->u.dst.__refcnt, 1);
1682 rth->u.dst.flags= DST_HOST;
1683 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1684 rth->u.dst.flags |= DST_NOPOLICY;
1685 if (IN_DEV_CONF_GET(out_dev, NOXFRM))
1686 rth->u.dst.flags |= DST_NOXFRM;
1687 rth->fl.fl4_dst = daddr;
1688 rth->rt_dst = daddr;
1689 rth->fl.fl4_tos = tos;
1690 rth->fl.mark = skb->mark;
1691 rth->fl.fl4_src = saddr;
1692 rth->rt_src = saddr;
1693 rth->rt_gateway = daddr;
1695 rth->fl.iif = in_dev->dev->ifindex;
1696 rth->u.dst.dev = (out_dev)->dev;
1697 dev_hold(rth->u.dst.dev);
1698 rth->idev = in_dev_get(rth->u.dst.dev);
1700 rth->rt_spec_dst= spec_dst;
1702 rth->u.dst.input = ip_forward;
1703 rth->u.dst.output = ip_output;
1705 rt_set_nexthop(rth, res, itag);
1707 rth->rt_flags = flags;
1712 /* release the working reference to the output device */
1713 in_dev_put(out_dev);
1717 static inline int ip_mkroute_input(struct sk_buff *skb,
1718 struct fib_result* res,
1719 const struct flowi *fl,
1720 struct in_device *in_dev,
1721 __be32 daddr, __be32 saddr, u32 tos)
1723 struct rtable* rth = NULL;
1727 #ifdef CONFIG_IP_ROUTE_MULTIPATH
1728 if (res->fi && res->fi->fib_nhs > 1 && fl->oif == 0)
1729 fib_select_multipath(fl, res);
1732 /* create a routing cache entry */
1733 err = __mkroute_input(skb, res, in_dev, daddr, saddr, tos, &rth);
1737 /* put it into the cache */
1738 hash = rt_hash(daddr, saddr, fl->iif);
1739 return rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);
1743 * NOTE. We drop all the packets that has local source
1744 * addresses, because every properly looped back packet
1745 * must have correct destination already attached by output routine.
1747 * Such approach solves two big problems:
1748 * 1. Not simplex devices are handled properly.
1749 * 2. IP spoofing attempts are filtered with 100% of guarantee.
1752 static int ip_route_input_slow(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1753 u8 tos, struct net_device *dev)
1755 struct fib_result res;
1756 struct in_device *in_dev = in_dev_get(dev);
1757 struct flowi fl = { .nl_u = { .ip4_u =
1761 .scope = RT_SCOPE_UNIVERSE,
1764 .iif = dev->ifindex };
1767 struct rtable * rth;
1773 /* IP on this device is disabled. */
1778 /* Check for the most weird martians, which can be not detected
1782 if (MULTICAST(saddr) || BADCLASS(saddr) || LOOPBACK(saddr))
1783 goto martian_source;
1785 if (daddr == htonl(0xFFFFFFFF) || (saddr == 0 && daddr == 0))
1788 /* Accept zero addresses only to limited broadcast;
1789 * I even do not know to fix it or not. Waiting for complains :-)
1792 goto martian_source;
1794 if (BADCLASS(daddr) || ZERONET(daddr) || LOOPBACK(daddr))
1795 goto martian_destination;
1798 * Now we are ready to route packet.
1800 if ((err = fib_lookup(&fl, &res)) != 0) {
1801 if (!IN_DEV_FORWARD(in_dev))
1807 RT_CACHE_STAT_INC(in_slow_tot);
1809 if (res.type == RTN_BROADCAST)
1812 if (res.type == RTN_LOCAL) {
1814 result = fib_validate_source(saddr, daddr, tos,
1815 loopback_dev->ifindex,
1816 dev, &spec_dst, &itag);
1818 goto martian_source;
1820 flags |= RTCF_DIRECTSRC;
1825 if (!IN_DEV_FORWARD(in_dev))
1827 if (res.type != RTN_UNICAST)
1828 goto martian_destination;
1830 err = ip_mkroute_input(skb, &res, &fl, in_dev, daddr, saddr, tos);
1831 if (err == -ENOBUFS)
1843 if (skb->protocol != htons(ETH_P_IP))
1847 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
1849 err = fib_validate_source(saddr, 0, tos, 0, dev, &spec_dst,
1852 goto martian_source;
1854 flags |= RTCF_DIRECTSRC;
1856 flags |= RTCF_BROADCAST;
1857 res.type = RTN_BROADCAST;
1858 RT_CACHE_STAT_INC(in_brd);
1861 rth = dst_alloc(&ipv4_dst_ops);
1865 rth->u.dst.output= ip_rt_bug;
1867 atomic_set(&rth->u.dst.__refcnt, 1);
1868 rth->u.dst.flags= DST_HOST;
1869 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1870 rth->u.dst.flags |= DST_NOPOLICY;
1871 rth->fl.fl4_dst = daddr;
1872 rth->rt_dst = daddr;
1873 rth->fl.fl4_tos = tos;
1874 rth->fl.mark = skb->mark;
1875 rth->fl.fl4_src = saddr;
1876 rth->rt_src = saddr;
1877 #ifdef CONFIG_NET_CLS_ROUTE
1878 rth->u.dst.tclassid = itag;
1881 rth->fl.iif = dev->ifindex;
1882 rth->u.dst.dev = loopback_dev;
1883 dev_hold(rth->u.dst.dev);
1884 rth->idev = in_dev_get(rth->u.dst.dev);
1885 rth->rt_gateway = daddr;
1886 rth->rt_spec_dst= spec_dst;
1887 rth->u.dst.input= ip_local_deliver;
1888 rth->rt_flags = flags|RTCF_LOCAL;
1889 if (res.type == RTN_UNREACHABLE) {
1890 rth->u.dst.input= ip_error;
1891 rth->u.dst.error= -err;
1892 rth->rt_flags &= ~RTCF_LOCAL;
1894 rth->rt_type = res.type;
1895 hash = rt_hash(daddr, saddr, fl.iif);
1896 err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);
1900 RT_CACHE_STAT_INC(in_no_route);
1901 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_UNIVERSE);
1902 res.type = RTN_UNREACHABLE;
1906 * Do not cache martian addresses: they should be logged (RFC1812)
1908 martian_destination:
1909 RT_CACHE_STAT_INC(in_martian_dst);
1910 #ifdef CONFIG_IP_ROUTE_VERBOSE
1911 if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
1912 printk(KERN_WARNING "martian destination %u.%u.%u.%u from "
1913 "%u.%u.%u.%u, dev %s\n",
1914 NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
1918 err = -EHOSTUNREACH;
1930 ip_handle_martian_source(dev, in_dev, skb, daddr, saddr);
1934 int ip_route_input(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1935 u8 tos, struct net_device *dev)
1937 struct rtable * rth;
1939 int iif = dev->ifindex;
1941 tos &= IPTOS_RT_MASK;
1942 hash = rt_hash(daddr, saddr, iif);
1945 for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
1946 rth = rcu_dereference(rth->u.dst.rt_next)) {
1947 if (rth->fl.fl4_dst == daddr &&
1948 rth->fl.fl4_src == saddr &&
1949 rth->fl.iif == iif &&
1951 rth->fl.mark == skb->mark &&
1952 rth->fl.fl4_tos == tos) {
1953 rth->u.dst.lastuse = jiffies;
1954 dst_hold(&rth->u.dst);
1956 RT_CACHE_STAT_INC(in_hit);
1958 skb->dst = (struct dst_entry*)rth;
1961 RT_CACHE_STAT_INC(in_hlist_search);
1965 /* Multicast recognition logic is moved from route cache to here.
1966 The problem was that too many Ethernet cards have broken/missing
1967 hardware multicast filters :-( As result the host on multicasting
1968 network acquires a lot of useless route cache entries, sort of
1969 SDR messages from all the world. Now we try to get rid of them.
1970 Really, provided software IP multicast filter is organized
1971 reasonably (at least, hashed), it does not result in a slowdown
1972 comparing with route cache reject entries.
1973 Note, that multicast routers are not affected, because
1974 route cache entry is created eventually.
1976 if (MULTICAST(daddr)) {
1977 struct in_device *in_dev;
1980 if ((in_dev = __in_dev_get_rcu(dev)) != NULL) {
1981 int our = ip_check_mc(in_dev, daddr, saddr,
1982 ip_hdr(skb)->protocol);
1984 #ifdef CONFIG_IP_MROUTE
1985 || (!LOCAL_MCAST(daddr) && IN_DEV_MFORWARD(in_dev))
1989 return ip_route_input_mc(skb, daddr, saddr,
1996 return ip_route_input_slow(skb, daddr, saddr, tos, dev);
1999 static inline int __mkroute_output(struct rtable **result,
2000 struct fib_result* res,
2001 const struct flowi *fl,
2002 const struct flowi *oldflp,
2003 struct net_device *dev_out,
2007 struct in_device *in_dev;
2008 u32 tos = RT_FL_TOS(oldflp);
2011 if (LOOPBACK(fl->fl4_src) && !(dev_out->flags&IFF_LOOPBACK))
2014 if (fl->fl4_dst == htonl(0xFFFFFFFF))
2015 res->type = RTN_BROADCAST;
2016 else if (MULTICAST(fl->fl4_dst))
2017 res->type = RTN_MULTICAST;
2018 else if (BADCLASS(fl->fl4_dst) || ZERONET(fl->fl4_dst))
2021 if (dev_out->flags & IFF_LOOPBACK)
2022 flags |= RTCF_LOCAL;
2024 /* get work reference to inet device */
2025 in_dev = in_dev_get(dev_out);
2029 if (res->type == RTN_BROADCAST) {
2030 flags |= RTCF_BROADCAST | RTCF_LOCAL;
2032 fib_info_put(res->fi);
2035 } else if (res->type == RTN_MULTICAST) {
2036 flags |= RTCF_MULTICAST|RTCF_LOCAL;
2037 if (!ip_check_mc(in_dev, oldflp->fl4_dst, oldflp->fl4_src,
2039 flags &= ~RTCF_LOCAL;
2040 /* If multicast route do not exist use
2041 default one, but do not gateway in this case.
2044 if (res->fi && res->prefixlen < 4) {
2045 fib_info_put(res->fi);
2051 rth = dst_alloc(&ipv4_dst_ops);
2057 atomic_set(&rth->u.dst.__refcnt, 1);
2058 rth->u.dst.flags= DST_HOST;
2059 if (IN_DEV_CONF_GET(in_dev, NOXFRM))
2060 rth->u.dst.flags |= DST_NOXFRM;
2061 if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2062 rth->u.dst.flags |= DST_NOPOLICY;
2064 rth->fl.fl4_dst = oldflp->fl4_dst;
2065 rth->fl.fl4_tos = tos;
2066 rth->fl.fl4_src = oldflp->fl4_src;
2067 rth->fl.oif = oldflp->oif;
2068 rth->fl.mark = oldflp->mark;
2069 rth->rt_dst = fl->fl4_dst;
2070 rth->rt_src = fl->fl4_src;
2071 rth->rt_iif = oldflp->oif ? : dev_out->ifindex;
2072 /* get references to the devices that are to be hold by the routing
2074 rth->u.dst.dev = dev_out;
2076 rth->idev = in_dev_get(dev_out);
2077 rth->rt_gateway = fl->fl4_dst;
2078 rth->rt_spec_dst= fl->fl4_src;
2080 rth->u.dst.output=ip_output;
2082 RT_CACHE_STAT_INC(out_slow_tot);
2084 if (flags & RTCF_LOCAL) {
2085 rth->u.dst.input = ip_local_deliver;
2086 rth->rt_spec_dst = fl->fl4_dst;
2088 if (flags & (RTCF_BROADCAST | RTCF_MULTICAST)) {
2089 rth->rt_spec_dst = fl->fl4_src;
2090 if (flags & RTCF_LOCAL &&
2091 !(dev_out->flags & IFF_LOOPBACK)) {
2092 rth->u.dst.output = ip_mc_output;
2093 RT_CACHE_STAT_INC(out_slow_mc);
2095 #ifdef CONFIG_IP_MROUTE
2096 if (res->type == RTN_MULTICAST) {
2097 if (IN_DEV_MFORWARD(in_dev) &&
2098 !LOCAL_MCAST(oldflp->fl4_dst)) {
2099 rth->u.dst.input = ip_mr_input;
2100 rth->u.dst.output = ip_mc_output;
2106 rt_set_nexthop(rth, res, 0);
2108 rth->rt_flags = flags;
2112 /* release work reference to inet device */
2118 static inline int ip_mkroute_output(struct rtable **rp,
2119 struct fib_result* res,
2120 const struct flowi *fl,
2121 const struct flowi *oldflp,
2122 struct net_device *dev_out,
2125 struct rtable *rth = NULL;
2126 int err = __mkroute_output(&rth, res, fl, oldflp, dev_out, flags);
2129 hash = rt_hash(oldflp->fl4_dst, oldflp->fl4_src, oldflp->oif);
2130 err = rt_intern_hash(hash, rth, rp);
2137 * Major route resolver routine.
2140 static int ip_route_output_slow(struct rtable **rp, const struct flowi *oldflp)
2142 u32 tos = RT_FL_TOS(oldflp);
2143 struct flowi fl = { .nl_u = { .ip4_u =
2144 { .daddr = oldflp->fl4_dst,
2145 .saddr = oldflp->fl4_src,
2146 .tos = tos & IPTOS_RT_MASK,
2147 .scope = ((tos & RTO_ONLINK) ?
2151 .mark = oldflp->mark,
2152 .iif = loopback_dev->ifindex,
2153 .oif = oldflp->oif };
2154 struct fib_result res;
2156 struct net_device *dev_out = NULL;
2162 #ifdef CONFIG_IP_MULTIPLE_TABLES
2166 if (oldflp->fl4_src) {
2168 if (MULTICAST(oldflp->fl4_src) ||
2169 BADCLASS(oldflp->fl4_src) ||
2170 ZERONET(oldflp->fl4_src))
2173 /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
2174 dev_out = ip_dev_find(oldflp->fl4_src);
2175 if (dev_out == NULL)
2178 /* I removed check for oif == dev_out->oif here.
2179 It was wrong for two reasons:
2180 1. ip_dev_find(saddr) can return wrong iface, if saddr is
2181 assigned to multiple interfaces.
2182 2. Moreover, we are allowed to send packets with saddr
2183 of another iface. --ANK
2186 if (oldflp->oif == 0
2187 && (MULTICAST(oldflp->fl4_dst) || oldflp->fl4_dst == htonl(0xFFFFFFFF))) {
2188 /* Special hack: user can direct multicasts
2189 and limited broadcast via necessary interface
2190 without fiddling with IP_MULTICAST_IF or IP_PKTINFO.
2191 This hack is not just for fun, it allows
2192 vic,vat and friends to work.
2193 They bind socket to loopback, set ttl to zero
2194 and expect that it will work.
2195 From the viewpoint of routing cache they are broken,
2196 because we are not allowed to build multicast path
2197 with loopback source addr (look, routing cache
2198 cannot know, that ttl is zero, so that packet
2199 will not leave this host and route is valid).
2200 Luckily, this hack is good workaround.
2203 fl.oif = dev_out->ifindex;
2213 dev_out = dev_get_by_index(&init_net, oldflp->oif);
2215 if (dev_out == NULL)
2218 /* RACE: Check return value of inet_select_addr instead. */
2219 if (__in_dev_get_rtnl(dev_out) == NULL) {
2221 goto out; /* Wrong error code */
2224 if (LOCAL_MCAST(oldflp->fl4_dst) || oldflp->fl4_dst == htonl(0xFFFFFFFF)) {
2226 fl.fl4_src = inet_select_addr(dev_out, 0,
2231 if (MULTICAST(oldflp->fl4_dst))
2232 fl.fl4_src = inet_select_addr(dev_out, 0,
2234 else if (!oldflp->fl4_dst)
2235 fl.fl4_src = inet_select_addr(dev_out, 0,
2241 fl.fl4_dst = fl.fl4_src;
2243 fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
2246 dev_out = loopback_dev;
2248 fl.oif = loopback_dev->ifindex;
2249 res.type = RTN_LOCAL;
2250 flags |= RTCF_LOCAL;
2254 if (fib_lookup(&fl, &res)) {
2257 /* Apparently, routing tables are wrong. Assume,
2258 that the destination is on link.
2261 Because we are allowed to send to iface
2262 even if it has NO routes and NO assigned
2263 addresses. When oif is specified, routing
2264 tables are looked up with only one purpose:
2265 to catch if destination is gatewayed, rather than
2266 direct. Moreover, if MSG_DONTROUTE is set,
2267 we send packet, ignoring both routing tables
2268 and ifaddr state. --ANK
2271 We could make it even if oif is unknown,
2272 likely IPv6, but we do not.
2275 if (fl.fl4_src == 0)
2276 fl.fl4_src = inet_select_addr(dev_out, 0,
2278 res.type = RTN_UNICAST;
2288 if (res.type == RTN_LOCAL) {
2290 fl.fl4_src = fl.fl4_dst;
2293 dev_out = loopback_dev;
2295 fl.oif = dev_out->ifindex;
2297 fib_info_put(res.fi);
2299 flags |= RTCF_LOCAL;
2303 #ifdef CONFIG_IP_ROUTE_MULTIPATH
2304 if (res.fi->fib_nhs > 1 && fl.oif == 0)
2305 fib_select_multipath(&fl, &res);
2308 if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
2309 fib_select_default(&fl, &res);
2312 fl.fl4_src = FIB_RES_PREFSRC(res);
2316 dev_out = FIB_RES_DEV(res);
2318 fl.oif = dev_out->ifindex;
2322 err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
2332 int __ip_route_output_key(struct rtable **rp, const struct flowi *flp)
2337 hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif);
2340 for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2341 rth = rcu_dereference(rth->u.dst.rt_next)) {
2342 if (rth->fl.fl4_dst == flp->fl4_dst &&
2343 rth->fl.fl4_src == flp->fl4_src &&
2345 rth->fl.oif == flp->oif &&
2346 rth->fl.mark == flp->mark &&
2347 !((rth->fl.fl4_tos ^ flp->fl4_tos) &
2348 (IPTOS_RT_MASK | RTO_ONLINK))) {
2349 rth->u.dst.lastuse = jiffies;
2350 dst_hold(&rth->u.dst);
2352 RT_CACHE_STAT_INC(out_hit);
2353 rcu_read_unlock_bh();
2357 RT_CACHE_STAT_INC(out_hlist_search);
2359 rcu_read_unlock_bh();
2361 return ip_route_output_slow(rp, flp);
2364 EXPORT_SYMBOL_GPL(__ip_route_output_key);
2366 static void ipv4_rt_blackhole_update_pmtu(struct dst_entry *dst, u32 mtu)
2370 static struct dst_ops ipv4_dst_blackhole_ops = {
2372 .protocol = __constant_htons(ETH_P_IP),
2373 .destroy = ipv4_dst_destroy,
2374 .check = ipv4_dst_check,
2375 .update_pmtu = ipv4_rt_blackhole_update_pmtu,
2376 .entry_size = sizeof(struct rtable),
2380 static int ipv4_blackhole_output(struct sk_buff *skb)
2386 static int ipv4_dst_blackhole(struct rtable **rp, struct flowi *flp, struct sock *sk)
2388 struct rtable *ort = *rp;
2389 struct rtable *rt = (struct rtable *)
2390 dst_alloc(&ipv4_dst_blackhole_ops);
2393 struct dst_entry *new = &rt->u.dst;
2395 atomic_set(&new->__refcnt, 1);
2397 new->input = ipv4_blackhole_output;
2398 new->output = ipv4_blackhole_output;
2399 memcpy(new->metrics, ort->u.dst.metrics, RTAX_MAX*sizeof(u32));
2401 new->dev = ort->u.dst.dev;
2407 rt->idev = ort->idev;
2409 in_dev_hold(rt->idev);
2410 rt->rt_flags = ort->rt_flags;
2411 rt->rt_type = ort->rt_type;
2412 rt->rt_dst = ort->rt_dst;
2413 rt->rt_src = ort->rt_src;
2414 rt->rt_iif = ort->rt_iif;
2415 rt->rt_gateway = ort->rt_gateway;
2416 rt->rt_spec_dst = ort->rt_spec_dst;
2417 rt->peer = ort->peer;
2419 atomic_inc(&rt->peer->refcnt);
2424 dst_release(&(*rp)->u.dst);
2426 return (rt ? 0 : -ENOMEM);
2429 int ip_route_output_flow(struct rtable **rp, struct flowi *flp, struct sock *sk, int flags)
2433 if ((err = __ip_route_output_key(rp, flp)) != 0)
2438 flp->fl4_src = (*rp)->rt_src;
2440 flp->fl4_dst = (*rp)->rt_dst;
2441 err = __xfrm_lookup((struct dst_entry **)rp, flp, sk, flags);
2442 if (err == -EREMOTE)
2443 err = ipv4_dst_blackhole(rp, flp, sk);
2451 EXPORT_SYMBOL_GPL(ip_route_output_flow);
2453 int ip_route_output_key(struct rtable **rp, struct flowi *flp)
2455 return ip_route_output_flow(rp, flp, NULL, 0);
2458 static int rt_fill_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
2459 int nowait, unsigned int flags)
2461 struct rtable *rt = (struct rtable*)skb->dst;
2463 struct nlmsghdr *nlh;
2465 u32 id = 0, ts = 0, tsage = 0, error;
2467 nlh = nlmsg_put(skb, pid, seq, event, sizeof(*r), flags);
2471 r = nlmsg_data(nlh);
2472 r->rtm_family = AF_INET;
2473 r->rtm_dst_len = 32;
2475 r->rtm_tos = rt->fl.fl4_tos;
2476 r->rtm_table = RT_TABLE_MAIN;
2477 NLA_PUT_U32(skb, RTA_TABLE, RT_TABLE_MAIN);
2478 r->rtm_type = rt->rt_type;
2479 r->rtm_scope = RT_SCOPE_UNIVERSE;
2480 r->rtm_protocol = RTPROT_UNSPEC;
2481 r->rtm_flags = (rt->rt_flags & ~0xFFFF) | RTM_F_CLONED;
2482 if (rt->rt_flags & RTCF_NOTIFY)
2483 r->rtm_flags |= RTM_F_NOTIFY;
2485 NLA_PUT_BE32(skb, RTA_DST, rt->rt_dst);
2487 if (rt->fl.fl4_src) {
2488 r->rtm_src_len = 32;
2489 NLA_PUT_BE32(skb, RTA_SRC, rt->fl.fl4_src);
2492 NLA_PUT_U32(skb, RTA_OIF, rt->u.dst.dev->ifindex);
2493 #ifdef CONFIG_NET_CLS_ROUTE
2494 if (rt->u.dst.tclassid)
2495 NLA_PUT_U32(skb, RTA_FLOW, rt->u.dst.tclassid);
2498 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_spec_dst);
2499 else if (rt->rt_src != rt->fl.fl4_src)
2500 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_src);
2502 if (rt->rt_dst != rt->rt_gateway)
2503 NLA_PUT_BE32(skb, RTA_GATEWAY, rt->rt_gateway);
2505 if (rtnetlink_put_metrics(skb, rt->u.dst.metrics) < 0)
2506 goto nla_put_failure;
2508 error = rt->u.dst.error;
2509 expires = rt->u.dst.expires ? rt->u.dst.expires - jiffies : 0;
2511 id = rt->peer->ip_id_count;
2512 if (rt->peer->tcp_ts_stamp) {
2513 ts = rt->peer->tcp_ts;
2514 tsage = get_seconds() - rt->peer->tcp_ts_stamp;
2519 #ifdef CONFIG_IP_MROUTE
2520 __be32 dst = rt->rt_dst;
2522 if (MULTICAST(dst) && !LOCAL_MCAST(dst) &&
2523 IPV4_DEVCONF_ALL(MC_FORWARDING)) {
2524 int err = ipmr_get_route(skb, r, nowait);
2529 goto nla_put_failure;
2531 if (err == -EMSGSIZE)
2532 goto nla_put_failure;
2538 NLA_PUT_U32(skb, RTA_IIF, rt->fl.iif);
2541 if (rtnl_put_cacheinfo(skb, &rt->u.dst, id, ts, tsage,
2542 expires, error) < 0)
2543 goto nla_put_failure;
2545 return nlmsg_end(skb, nlh);
2548 nlmsg_cancel(skb, nlh);
2552 static int inet_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg)
2555 struct nlattr *tb[RTA_MAX+1];
2556 struct rtable *rt = NULL;
2561 struct sk_buff *skb;
2563 err = nlmsg_parse(nlh, sizeof(*rtm), tb, RTA_MAX, rtm_ipv4_policy);
2567 rtm = nlmsg_data(nlh);
2569 skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
2575 /* Reserve room for dummy headers, this skb can pass
2576 through good chunk of routing engine.
2578 skb_reset_mac_header(skb);
2579 skb_reset_network_header(skb);
2581 /* Bugfix: need to give ip_route_input enough of an IP header to not gag. */
2582 ip_hdr(skb)->protocol = IPPROTO_ICMP;
2583 skb_reserve(skb, MAX_HEADER + sizeof(struct iphdr));
2585 src = tb[RTA_SRC] ? nla_get_be32(tb[RTA_SRC]) : 0;
2586 dst = tb[RTA_DST] ? nla_get_be32(tb[RTA_DST]) : 0;
2587 iif = tb[RTA_IIF] ? nla_get_u32(tb[RTA_IIF]) : 0;
2590 struct net_device *dev;
2592 dev = __dev_get_by_index(&init_net, iif);
2598 skb->protocol = htons(ETH_P_IP);
2601 err = ip_route_input(skb, dst, src, rtm->rtm_tos, dev);
2604 rt = (struct rtable*) skb->dst;
2605 if (err == 0 && rt->u.dst.error)
2606 err = -rt->u.dst.error;
2613 .tos = rtm->rtm_tos,
2616 .oif = tb[RTA_OIF] ? nla_get_u32(tb[RTA_OIF]) : 0,
2618 err = ip_route_output_key(&rt, &fl);
2624 skb->dst = &rt->u.dst;
2625 if (rtm->rtm_flags & RTM_F_NOTIFY)
2626 rt->rt_flags |= RTCF_NOTIFY;
2628 err = rt_fill_info(skb, NETLINK_CB(in_skb).pid, nlh->nlmsg_seq,
2629 RTM_NEWROUTE, 0, 0);
2633 err = rtnl_unicast(skb, NETLINK_CB(in_skb).pid);
2642 int ip_rt_dump(struct sk_buff *skb, struct netlink_callback *cb)
2649 s_idx = idx = cb->args[1];
2650 for (h = 0; h <= rt_hash_mask; h++) {
2651 if (h < s_h) continue;
2655 for (rt = rcu_dereference(rt_hash_table[h].chain), idx = 0; rt;
2656 rt = rcu_dereference(rt->u.dst.rt_next), idx++) {
2659 skb->dst = dst_clone(&rt->u.dst);
2660 if (rt_fill_info(skb, NETLINK_CB(cb->skb).pid,
2661 cb->nlh->nlmsg_seq, RTM_NEWROUTE,
2662 1, NLM_F_MULTI) <= 0) {
2663 dst_release(xchg(&skb->dst, NULL));
2664 rcu_read_unlock_bh();
2667 dst_release(xchg(&skb->dst, NULL));
2669 rcu_read_unlock_bh();
2678 void ip_rt_multicast_event(struct in_device *in_dev)
2683 #ifdef CONFIG_SYSCTL
2684 static int flush_delay;
2686 static int ipv4_sysctl_rtcache_flush(ctl_table *ctl, int write,
2687 struct file *filp, void __user *buffer,
2688 size_t *lenp, loff_t *ppos)
2691 proc_dointvec(ctl, write, filp, buffer, lenp, ppos);
2692 rt_cache_flush(flush_delay);
2699 static int ipv4_sysctl_rtcache_flush_strategy(ctl_table *table,
2702 void __user *oldval,
2703 size_t __user *oldlenp,
2704 void __user *newval,
2708 if (newlen != sizeof(int))
2710 if (get_user(delay, (int __user *)newval))
2712 rt_cache_flush(delay);
2716 ctl_table ipv4_route_table[] = {
2718 .ctl_name = NET_IPV4_ROUTE_FLUSH,
2719 .procname = "flush",
2720 .data = &flush_delay,
2721 .maxlen = sizeof(int),
2723 .proc_handler = &ipv4_sysctl_rtcache_flush,
2724 .strategy = &ipv4_sysctl_rtcache_flush_strategy,
2727 .ctl_name = NET_IPV4_ROUTE_MIN_DELAY,
2728 .procname = "min_delay",
2729 .data = &ip_rt_min_delay,
2730 .maxlen = sizeof(int),
2732 .proc_handler = &proc_dointvec_jiffies,
2733 .strategy = &sysctl_jiffies,
2736 .ctl_name = NET_IPV4_ROUTE_MAX_DELAY,
2737 .procname = "max_delay",
2738 .data = &ip_rt_max_delay,
2739 .maxlen = sizeof(int),
2741 .proc_handler = &proc_dointvec_jiffies,
2742 .strategy = &sysctl_jiffies,
2745 .ctl_name = NET_IPV4_ROUTE_GC_THRESH,
2746 .procname = "gc_thresh",
2747 .data = &ipv4_dst_ops.gc_thresh,
2748 .maxlen = sizeof(int),
2750 .proc_handler = &proc_dointvec,
2753 .ctl_name = NET_IPV4_ROUTE_MAX_SIZE,
2754 .procname = "max_size",
2755 .data = &ip_rt_max_size,
2756 .maxlen = sizeof(int),
2758 .proc_handler = &proc_dointvec,
2761 /* Deprecated. Use gc_min_interval_ms */
2763 .ctl_name = NET_IPV4_ROUTE_GC_MIN_INTERVAL,
2764 .procname = "gc_min_interval",
2765 .data = &ip_rt_gc_min_interval,
2766 .maxlen = sizeof(int),
2768 .proc_handler = &proc_dointvec_jiffies,
2769 .strategy = &sysctl_jiffies,
2772 .ctl_name = NET_IPV4_ROUTE_GC_MIN_INTERVAL_MS,
2773 .procname = "gc_min_interval_ms",
2774 .data = &ip_rt_gc_min_interval,
2775 .maxlen = sizeof(int),
2777 .proc_handler = &proc_dointvec_ms_jiffies,
2778 .strategy = &sysctl_ms_jiffies,
2781 .ctl_name = NET_IPV4_ROUTE_GC_TIMEOUT,
2782 .procname = "gc_timeout",
2783 .data = &ip_rt_gc_timeout,
2784 .maxlen = sizeof(int),
2786 .proc_handler = &proc_dointvec_jiffies,
2787 .strategy = &sysctl_jiffies,
2790 .ctl_name = NET_IPV4_ROUTE_GC_INTERVAL,
2791 .procname = "gc_interval",
2792 .data = &ip_rt_gc_interval,
2793 .maxlen = sizeof(int),
2795 .proc_handler = &proc_dointvec_jiffies,
2796 .strategy = &sysctl_jiffies,
2799 .ctl_name = NET_IPV4_ROUTE_REDIRECT_LOAD,
2800 .procname = "redirect_load",
2801 .data = &ip_rt_redirect_load,
2802 .maxlen = sizeof(int),
2804 .proc_handler = &proc_dointvec,
2807 .ctl_name = NET_IPV4_ROUTE_REDIRECT_NUMBER,
2808 .procname = "redirect_number",
2809 .data = &ip_rt_redirect_number,
2810 .maxlen = sizeof(int),
2812 .proc_handler = &proc_dointvec,
2815 .ctl_name = NET_IPV4_ROUTE_REDIRECT_SILENCE,
2816 .procname = "redirect_silence",
2817 .data = &ip_rt_redirect_silence,
2818 .maxlen = sizeof(int),
2820 .proc_handler = &proc_dointvec,
2823 .ctl_name = NET_IPV4_ROUTE_ERROR_COST,
2824 .procname = "error_cost",
2825 .data = &ip_rt_error_cost,
2826 .maxlen = sizeof(int),
2828 .proc_handler = &proc_dointvec,
2831 .ctl_name = NET_IPV4_ROUTE_ERROR_BURST,
2832 .procname = "error_burst",
2833 .data = &ip_rt_error_burst,
2834 .maxlen = sizeof(int),
2836 .proc_handler = &proc_dointvec,
2839 .ctl_name = NET_IPV4_ROUTE_GC_ELASTICITY,
2840 .procname = "gc_elasticity",
2841 .data = &ip_rt_gc_elasticity,
2842 .maxlen = sizeof(int),
2844 .proc_handler = &proc_dointvec,
2847 .ctl_name = NET_IPV4_ROUTE_MTU_EXPIRES,
2848 .procname = "mtu_expires",
2849 .data = &ip_rt_mtu_expires,
2850 .maxlen = sizeof(int),
2852 .proc_handler = &proc_dointvec_jiffies,
2853 .strategy = &sysctl_jiffies,
2856 .ctl_name = NET_IPV4_ROUTE_MIN_PMTU,
2857 .procname = "min_pmtu",
2858 .data = &ip_rt_min_pmtu,
2859 .maxlen = sizeof(int),
2861 .proc_handler = &proc_dointvec,
2864 .ctl_name = NET_IPV4_ROUTE_MIN_ADVMSS,
2865 .procname = "min_adv_mss",
2866 .data = &ip_rt_min_advmss,
2867 .maxlen = sizeof(int),
2869 .proc_handler = &proc_dointvec,
2872 .ctl_name = NET_IPV4_ROUTE_SECRET_INTERVAL,
2873 .procname = "secret_interval",
2874 .data = &ip_rt_secret_interval,
2875 .maxlen = sizeof(int),
2877 .proc_handler = &proc_dointvec_jiffies,
2878 .strategy = &sysctl_jiffies,
2884 #ifdef CONFIG_NET_CLS_ROUTE
2885 struct ip_rt_acct *ip_rt_acct;
2887 /* This code sucks. But you should have seen it before! --RR */
2889 /* IP route accounting ptr for this logical cpu number. */
2890 #define IP_RT_ACCT_CPU(i) (ip_rt_acct + i * 256)
2892 #ifdef CONFIG_PROC_FS
2893 static int ip_rt_acct_read(char *buffer, char **start, off_t offset,
2894 int length, int *eof, void *data)
2898 if ((offset & 3) || (length & 3))
2901 if (offset >= sizeof(struct ip_rt_acct) * 256) {
2906 if (offset + length >= sizeof(struct ip_rt_acct) * 256) {
2907 length = sizeof(struct ip_rt_acct) * 256 - offset;
2911 offset /= sizeof(u32);
2914 u32 *src = ((u32 *) IP_RT_ACCT_CPU(0)) + offset;
2915 u32 *dst = (u32 *) buffer;
2917 /* Copy first cpu. */
2919 memcpy(dst, src, length);
2921 /* Add the other cpus in, one int at a time */
2922 for_each_possible_cpu(i) {
2925 src = ((u32 *) IP_RT_ACCT_CPU(i)) + offset;
2927 for (j = 0; j < length/4; j++)
2933 #endif /* CONFIG_PROC_FS */
2934 #endif /* CONFIG_NET_CLS_ROUTE */
2936 static __initdata unsigned long rhash_entries;
2937 static int __init set_rhash_entries(char *str)
2941 rhash_entries = simple_strtoul(str, &str, 0);
2944 __setup("rhash_entries=", set_rhash_entries);
2946 int __init ip_rt_init(void)
2950 rt_hash_rnd = (int) ((num_physpages ^ (num_physpages>>8)) ^
2951 (jiffies ^ (jiffies >> 7)));
2953 #ifdef CONFIG_NET_CLS_ROUTE
2957 (PAGE_SIZE << order) < 256 * sizeof(struct ip_rt_acct) * NR_CPUS; order++)
2959 ip_rt_acct = (struct ip_rt_acct *)__get_free_pages(GFP_KERNEL, order);
2961 panic("IP: failed to allocate ip_rt_acct\n");
2962 memset(ip_rt_acct, 0, PAGE_SIZE << order);
2966 ipv4_dst_ops.kmem_cachep =
2967 kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
2968 SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
2970 ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;
2972 rt_hash_table = (struct rt_hash_bucket *)
2973 alloc_large_system_hash("IP route cache",
2974 sizeof(struct rt_hash_bucket),
2976 (num_physpages >= 128 * 1024) ?
2982 memset(rt_hash_table, 0, (rt_hash_mask + 1) * sizeof(struct rt_hash_bucket));
2983 rt_hash_lock_init();
2985 ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
2986 ip_rt_max_size = (rt_hash_mask + 1) * 16;
2991 init_timer(&rt_flush_timer);
2992 rt_flush_timer.function = rt_run_flush;
2993 init_timer(&rt_secret_timer);
2994 rt_secret_timer.function = rt_secret_rebuild;
2996 /* All the timers, started at system startup tend
2997 to synchronize. Perturb it a bit.
2999 schedule_delayed_work(&expires_work,
3000 net_random() % ip_rt_gc_interval + ip_rt_gc_interval);
3002 rt_secret_timer.expires = jiffies + net_random() % ip_rt_secret_interval +
3003 ip_rt_secret_interval;
3004 add_timer(&rt_secret_timer);
3006 #ifdef CONFIG_PROC_FS
3008 struct proc_dir_entry *rtstat_pde = NULL; /* keep gcc happy */
3009 if (!proc_net_fops_create(&init_net, "rt_cache", S_IRUGO, &rt_cache_seq_fops) ||
3010 !(rtstat_pde = create_proc_entry("rt_cache", S_IRUGO,
3011 init_net.proc_net_stat))) {
3014 rtstat_pde->proc_fops = &rt_cpu_seq_fops;
3016 #ifdef CONFIG_NET_CLS_ROUTE
3017 create_proc_read_entry("rt_acct", 0, init_net.proc_net, ip_rt_acct_read, NULL);
3024 rtnl_register(PF_INET, RTM_GETROUTE, inet_rtm_getroute, NULL);
3029 EXPORT_SYMBOL(__ip_select_ident);
3030 EXPORT_SYMBOL(ip_route_input);
3031 EXPORT_SYMBOL(ip_route_output_key);