Merge branch 'core/percpu' into percpu-cpumask-x86-for-linus-2
[linux-2.6.git] / net / ipv4 / route.c
1 /*
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.
5  *
6  *              ROUTE - implementation of the IP router.
7  *
8  * Authors:     Ross Biro
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>
13  *
14  * Fixes:
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
24  *                                      clamper.
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.
39  *
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
58  *
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.
63  */
64
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>
71 #include <linux/mm.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>
77 #include <linux/in.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>
93 #include <net/dst.h>
94 #include <net/net_namespace.h>
95 #include <net/protocol.h>
96 #include <net/ip.h>
97 #include <net/route.h>
98 #include <net/inetpeer.h>
99 #include <net/sock.h>
100 #include <net/ip_fib.h>
101 #include <net/arp.h>
102 #include <net/tcp.h>
103 #include <net/icmp.h>
104 #include <net/xfrm.h>
105 #include <net/netevent.h>
106 #include <net/rtnetlink.h>
107 #ifdef CONFIG_SYSCTL
108 #include <linux/sysctl.h>
109 #endif
110
111 #define RT_FL_TOS(oldflp) \
112     ((u32)(oldflp->fl4_tos & (IPTOS_RT_MASK | RTO_ONLINK)))
113
114 #define IP_MAX_MTU      0xFFF0
115
116 #define RT_GC_TIMEOUT (300*HZ)
117
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;
132 static int rt_chain_length_max __read_mostly    = 20;
133
134 static void rt_worker_func(struct work_struct *work);
135 static DECLARE_DELAYED_WORK(expires_work, rt_worker_func);
136
137 /*
138  *      Interface to generic destination cache.
139  */
140
141 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie);
142 static void              ipv4_dst_destroy(struct dst_entry *dst);
143 static void              ipv4_dst_ifdown(struct dst_entry *dst,
144                                          struct net_device *dev, int how);
145 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst);
146 static void              ipv4_link_failure(struct sk_buff *skb);
147 static void              ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu);
148 static int rt_garbage_collect(struct dst_ops *ops);
149 static void rt_emergency_hash_rebuild(struct net *net);
150
151
152 static struct dst_ops ipv4_dst_ops = {
153         .family =               AF_INET,
154         .protocol =             cpu_to_be16(ETH_P_IP),
155         .gc =                   rt_garbage_collect,
156         .check =                ipv4_dst_check,
157         .destroy =              ipv4_dst_destroy,
158         .ifdown =               ipv4_dst_ifdown,
159         .negative_advice =      ipv4_negative_advice,
160         .link_failure =         ipv4_link_failure,
161         .update_pmtu =          ip_rt_update_pmtu,
162         .local_out =            __ip_local_out,
163         .entries =              ATOMIC_INIT(0),
164 };
165
166 #define ECN_OR_COST(class)      TC_PRIO_##class
167
168 const __u8 ip_tos2prio[16] = {
169         TC_PRIO_BESTEFFORT,
170         ECN_OR_COST(FILLER),
171         TC_PRIO_BESTEFFORT,
172         ECN_OR_COST(BESTEFFORT),
173         TC_PRIO_BULK,
174         ECN_OR_COST(BULK),
175         TC_PRIO_BULK,
176         ECN_OR_COST(BULK),
177         TC_PRIO_INTERACTIVE,
178         ECN_OR_COST(INTERACTIVE),
179         TC_PRIO_INTERACTIVE,
180         ECN_OR_COST(INTERACTIVE),
181         TC_PRIO_INTERACTIVE_BULK,
182         ECN_OR_COST(INTERACTIVE_BULK),
183         TC_PRIO_INTERACTIVE_BULK,
184         ECN_OR_COST(INTERACTIVE_BULK)
185 };
186
187
188 /*
189  * Route cache.
190  */
191
192 /* The locking scheme is rather straight forward:
193  *
194  * 1) Read-Copy Update protects the buckets of the central route hash.
195  * 2) Only writers remove entries, and they hold the lock
196  *    as they look at rtable reference counts.
197  * 3) Only readers acquire references to rtable entries,
198  *    they do so with atomic increments and with the
199  *    lock held.
200  */
201
202 struct rt_hash_bucket {
203         struct rtable   *chain;
204 };
205
206 #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) || \
207         defined(CONFIG_PROVE_LOCKING)
208 /*
209  * Instead of using one spinlock for each rt_hash_bucket, we use a table of spinlocks
210  * The size of this table is a power of two and depends on the number of CPUS.
211  * (on lockdep we have a quite big spinlock_t, so keep the size down there)
212  */
213 #ifdef CONFIG_LOCKDEP
214 # define RT_HASH_LOCK_SZ        256
215 #else
216 # if NR_CPUS >= 32
217 #  define RT_HASH_LOCK_SZ       4096
218 # elif NR_CPUS >= 16
219 #  define RT_HASH_LOCK_SZ       2048
220 # elif NR_CPUS >= 8
221 #  define RT_HASH_LOCK_SZ       1024
222 # elif NR_CPUS >= 4
223 #  define RT_HASH_LOCK_SZ       512
224 # else
225 #  define RT_HASH_LOCK_SZ       256
226 # endif
227 #endif
228
229 static spinlock_t       *rt_hash_locks;
230 # define rt_hash_lock_addr(slot) &rt_hash_locks[(slot) & (RT_HASH_LOCK_SZ - 1)]
231
232 static __init void rt_hash_lock_init(void)
233 {
234         int i;
235
236         rt_hash_locks = kmalloc(sizeof(spinlock_t) * RT_HASH_LOCK_SZ,
237                         GFP_KERNEL);
238         if (!rt_hash_locks)
239                 panic("IP: failed to allocate rt_hash_locks\n");
240
241         for (i = 0; i < RT_HASH_LOCK_SZ; i++)
242                 spin_lock_init(&rt_hash_locks[i]);
243 }
244 #else
245 # define rt_hash_lock_addr(slot) NULL
246
247 static inline void rt_hash_lock_init(void)
248 {
249 }
250 #endif
251
252 static struct rt_hash_bucket    *rt_hash_table __read_mostly;
253 static unsigned                 rt_hash_mask __read_mostly;
254 static unsigned int             rt_hash_log  __read_mostly;
255
256 static DEFINE_PER_CPU(struct rt_cache_stat, rt_cache_stat);
257 #define RT_CACHE_STAT_INC(field) \
258         (__raw_get_cpu_var(rt_cache_stat).field++)
259
260 static inline unsigned int rt_hash(__be32 daddr, __be32 saddr, int idx,
261                 int genid)
262 {
263         return jhash_3words((__force u32)(__be32)(daddr),
264                             (__force u32)(__be32)(saddr),
265                             idx, genid)
266                 & rt_hash_mask;
267 }
268
269 static inline int rt_genid(struct net *net)
270 {
271         return atomic_read(&net->ipv4.rt_genid);
272 }
273
274 #ifdef CONFIG_PROC_FS
275 struct rt_cache_iter_state {
276         struct seq_net_private p;
277         int bucket;
278         int genid;
279 };
280
281 static struct rtable *rt_cache_get_first(struct seq_file *seq)
282 {
283         struct rt_cache_iter_state *st = seq->private;
284         struct rtable *r = NULL;
285
286         for (st->bucket = rt_hash_mask; st->bucket >= 0; --st->bucket) {
287                 if (!rt_hash_table[st->bucket].chain)
288                         continue;
289                 rcu_read_lock_bh();
290                 r = rcu_dereference(rt_hash_table[st->bucket].chain);
291                 while (r) {
292                         if (dev_net(r->u.dst.dev) == seq_file_net(seq) &&
293                             r->rt_genid == st->genid)
294                                 return r;
295                         r = rcu_dereference(r->u.dst.rt_next);
296                 }
297                 rcu_read_unlock_bh();
298         }
299         return r;
300 }
301
302 static struct rtable *__rt_cache_get_next(struct seq_file *seq,
303                                           struct rtable *r)
304 {
305         struct rt_cache_iter_state *st = seq->private;
306
307         r = r->u.dst.rt_next;
308         while (!r) {
309                 rcu_read_unlock_bh();
310                 do {
311                         if (--st->bucket < 0)
312                                 return NULL;
313                 } while (!rt_hash_table[st->bucket].chain);
314                 rcu_read_lock_bh();
315                 r = rt_hash_table[st->bucket].chain;
316         }
317         return rcu_dereference(r);
318 }
319
320 static struct rtable *rt_cache_get_next(struct seq_file *seq,
321                                         struct rtable *r)
322 {
323         struct rt_cache_iter_state *st = seq->private;
324         while ((r = __rt_cache_get_next(seq, r)) != NULL) {
325                 if (dev_net(r->u.dst.dev) != seq_file_net(seq))
326                         continue;
327                 if (r->rt_genid == st->genid)
328                         break;
329         }
330         return r;
331 }
332
333 static struct rtable *rt_cache_get_idx(struct seq_file *seq, loff_t pos)
334 {
335         struct rtable *r = rt_cache_get_first(seq);
336
337         if (r)
338                 while (pos && (r = rt_cache_get_next(seq, r)))
339                         --pos;
340         return pos ? NULL : r;
341 }
342
343 static void *rt_cache_seq_start(struct seq_file *seq, loff_t *pos)
344 {
345         struct rt_cache_iter_state *st = seq->private;
346         if (*pos)
347                 return rt_cache_get_idx(seq, *pos - 1);
348         st->genid = rt_genid(seq_file_net(seq));
349         return SEQ_START_TOKEN;
350 }
351
352 static void *rt_cache_seq_next(struct seq_file *seq, void *v, loff_t *pos)
353 {
354         struct rtable *r;
355
356         if (v == SEQ_START_TOKEN)
357                 r = rt_cache_get_first(seq);
358         else
359                 r = rt_cache_get_next(seq, v);
360         ++*pos;
361         return r;
362 }
363
364 static void rt_cache_seq_stop(struct seq_file *seq, void *v)
365 {
366         if (v && v != SEQ_START_TOKEN)
367                 rcu_read_unlock_bh();
368 }
369
370 static int rt_cache_seq_show(struct seq_file *seq, void *v)
371 {
372         if (v == SEQ_START_TOKEN)
373                 seq_printf(seq, "%-127s\n",
374                            "Iface\tDestination\tGateway \tFlags\t\tRefCnt\tUse\t"
375                            "Metric\tSource\t\tMTU\tWindow\tIRTT\tTOS\tHHRef\t"
376                            "HHUptod\tSpecDst");
377         else {
378                 struct rtable *r = v;
379                 int len;
380
381                 seq_printf(seq, "%s\t%08lX\t%08lX\t%8X\t%d\t%u\t%d\t"
382                               "%08lX\t%d\t%u\t%u\t%02X\t%d\t%1d\t%08X%n",
383                         r->u.dst.dev ? r->u.dst.dev->name : "*",
384                         (unsigned long)r->rt_dst, (unsigned long)r->rt_gateway,
385                         r->rt_flags, atomic_read(&r->u.dst.__refcnt),
386                         r->u.dst.__use, 0, (unsigned long)r->rt_src,
387                         (dst_metric(&r->u.dst, RTAX_ADVMSS) ?
388                              (int)dst_metric(&r->u.dst, RTAX_ADVMSS) + 40 : 0),
389                         dst_metric(&r->u.dst, RTAX_WINDOW),
390                         (int)((dst_metric(&r->u.dst, RTAX_RTT) >> 3) +
391                               dst_metric(&r->u.dst, RTAX_RTTVAR)),
392                         r->fl.fl4_tos,
393                         r->u.dst.hh ? atomic_read(&r->u.dst.hh->hh_refcnt) : -1,
394                         r->u.dst.hh ? (r->u.dst.hh->hh_output ==
395                                        dev_queue_xmit) : 0,
396                         r->rt_spec_dst, &len);
397
398                 seq_printf(seq, "%*s\n", 127 - len, "");
399         }
400         return 0;
401 }
402
403 static const struct seq_operations rt_cache_seq_ops = {
404         .start  = rt_cache_seq_start,
405         .next   = rt_cache_seq_next,
406         .stop   = rt_cache_seq_stop,
407         .show   = rt_cache_seq_show,
408 };
409
410 static int rt_cache_seq_open(struct inode *inode, struct file *file)
411 {
412         return seq_open_net(inode, file, &rt_cache_seq_ops,
413                         sizeof(struct rt_cache_iter_state));
414 }
415
416 static const struct file_operations rt_cache_seq_fops = {
417         .owner   = THIS_MODULE,
418         .open    = rt_cache_seq_open,
419         .read    = seq_read,
420         .llseek  = seq_lseek,
421         .release = seq_release_net,
422 };
423
424
425 static void *rt_cpu_seq_start(struct seq_file *seq, loff_t *pos)
426 {
427         int cpu;
428
429         if (*pos == 0)
430                 return SEQ_START_TOKEN;
431
432         for (cpu = *pos-1; cpu < nr_cpu_ids; ++cpu) {
433                 if (!cpu_possible(cpu))
434                         continue;
435                 *pos = cpu+1;
436                 return &per_cpu(rt_cache_stat, cpu);
437         }
438         return NULL;
439 }
440
441 static void *rt_cpu_seq_next(struct seq_file *seq, void *v, loff_t *pos)
442 {
443         int cpu;
444
445         for (cpu = *pos; cpu < nr_cpu_ids; ++cpu) {
446                 if (!cpu_possible(cpu))
447                         continue;
448                 *pos = cpu+1;
449                 return &per_cpu(rt_cache_stat, cpu);
450         }
451         return NULL;
452
453 }
454
455 static void rt_cpu_seq_stop(struct seq_file *seq, void *v)
456 {
457
458 }
459
460 static int rt_cpu_seq_show(struct seq_file *seq, void *v)
461 {
462         struct rt_cache_stat *st = v;
463
464         if (v == SEQ_START_TOKEN) {
465                 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");
466                 return 0;
467         }
468
469         seq_printf(seq,"%08x  %08x %08x %08x %08x %08x %08x %08x "
470                    " %08x %08x %08x %08x %08x %08x %08x %08x %08x \n",
471                    atomic_read(&ipv4_dst_ops.entries),
472                    st->in_hit,
473                    st->in_slow_tot,
474                    st->in_slow_mc,
475                    st->in_no_route,
476                    st->in_brd,
477                    st->in_martian_dst,
478                    st->in_martian_src,
479
480                    st->out_hit,
481                    st->out_slow_tot,
482                    st->out_slow_mc,
483
484                    st->gc_total,
485                    st->gc_ignored,
486                    st->gc_goal_miss,
487                    st->gc_dst_overflow,
488                    st->in_hlist_search,
489                    st->out_hlist_search
490                 );
491         return 0;
492 }
493
494 static const struct seq_operations rt_cpu_seq_ops = {
495         .start  = rt_cpu_seq_start,
496         .next   = rt_cpu_seq_next,
497         .stop   = rt_cpu_seq_stop,
498         .show   = rt_cpu_seq_show,
499 };
500
501
502 static int rt_cpu_seq_open(struct inode *inode, struct file *file)
503 {
504         return seq_open(file, &rt_cpu_seq_ops);
505 }
506
507 static const struct file_operations rt_cpu_seq_fops = {
508         .owner   = THIS_MODULE,
509         .open    = rt_cpu_seq_open,
510         .read    = seq_read,
511         .llseek  = seq_lseek,
512         .release = seq_release,
513 };
514
515 #ifdef CONFIG_NET_CLS_ROUTE
516 static int ip_rt_acct_read(char *buffer, char **start, off_t offset,
517                            int length, int *eof, void *data)
518 {
519         unsigned int i;
520
521         if ((offset & 3) || (length & 3))
522                 return -EIO;
523
524         if (offset >= sizeof(struct ip_rt_acct) * 256) {
525                 *eof = 1;
526                 return 0;
527         }
528
529         if (offset + length >= sizeof(struct ip_rt_acct) * 256) {
530                 length = sizeof(struct ip_rt_acct) * 256 - offset;
531                 *eof = 1;
532         }
533
534         offset /= sizeof(u32);
535
536         if (length > 0) {
537                 u32 *dst = (u32 *) buffer;
538
539                 *start = buffer;
540                 memset(dst, 0, length);
541
542                 for_each_possible_cpu(i) {
543                         unsigned int j;
544                         u32 *src;
545
546                         src = ((u32 *) per_cpu_ptr(ip_rt_acct, i)) + offset;
547                         for (j = 0; j < length/4; j++)
548                                 dst[j] += src[j];
549                 }
550         }
551         return length;
552 }
553 #endif
554
555 static int __net_init ip_rt_do_proc_init(struct net *net)
556 {
557         struct proc_dir_entry *pde;
558
559         pde = proc_net_fops_create(net, "rt_cache", S_IRUGO,
560                         &rt_cache_seq_fops);
561         if (!pde)
562                 goto err1;
563
564         pde = proc_create("rt_cache", S_IRUGO,
565                           net->proc_net_stat, &rt_cpu_seq_fops);
566         if (!pde)
567                 goto err2;
568
569 #ifdef CONFIG_NET_CLS_ROUTE
570         pde = create_proc_read_entry("rt_acct", 0, net->proc_net,
571                         ip_rt_acct_read, NULL);
572         if (!pde)
573                 goto err3;
574 #endif
575         return 0;
576
577 #ifdef CONFIG_NET_CLS_ROUTE
578 err3:
579         remove_proc_entry("rt_cache", net->proc_net_stat);
580 #endif
581 err2:
582         remove_proc_entry("rt_cache", net->proc_net);
583 err1:
584         return -ENOMEM;
585 }
586
587 static void __net_exit ip_rt_do_proc_exit(struct net *net)
588 {
589         remove_proc_entry("rt_cache", net->proc_net_stat);
590         remove_proc_entry("rt_cache", net->proc_net);
591         remove_proc_entry("rt_acct", net->proc_net);
592 }
593
594 static struct pernet_operations ip_rt_proc_ops __net_initdata =  {
595         .init = ip_rt_do_proc_init,
596         .exit = ip_rt_do_proc_exit,
597 };
598
599 static int __init ip_rt_proc_init(void)
600 {
601         return register_pernet_subsys(&ip_rt_proc_ops);
602 }
603
604 #else
605 static inline int ip_rt_proc_init(void)
606 {
607         return 0;
608 }
609 #endif /* CONFIG_PROC_FS */
610
611 static inline void rt_free(struct rtable *rt)
612 {
613         call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
614 }
615
616 static inline void rt_drop(struct rtable *rt)
617 {
618         ip_rt_put(rt);
619         call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
620 }
621
622 static inline int rt_fast_clean(struct rtable *rth)
623 {
624         /* Kill broadcast/multicast entries very aggresively, if they
625            collide in hash table with more useful entries */
626         return (rth->rt_flags & (RTCF_BROADCAST | RTCF_MULTICAST)) &&
627                 rth->fl.iif && rth->u.dst.rt_next;
628 }
629
630 static inline int rt_valuable(struct rtable *rth)
631 {
632         return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) ||
633                 rth->u.dst.expires;
634 }
635
636 static int rt_may_expire(struct rtable *rth, unsigned long tmo1, unsigned long tmo2)
637 {
638         unsigned long age;
639         int ret = 0;
640
641         if (atomic_read(&rth->u.dst.__refcnt))
642                 goto out;
643
644         ret = 1;
645         if (rth->u.dst.expires &&
646             time_after_eq(jiffies, rth->u.dst.expires))
647                 goto out;
648
649         age = jiffies - rth->u.dst.lastuse;
650         ret = 0;
651         if ((age <= tmo1 && !rt_fast_clean(rth)) ||
652             (age <= tmo2 && rt_valuable(rth)))
653                 goto out;
654         ret = 1;
655 out:    return ret;
656 }
657
658 /* Bits of score are:
659  * 31: very valuable
660  * 30: not quite useless
661  * 29..0: usage counter
662  */
663 static inline u32 rt_score(struct rtable *rt)
664 {
665         u32 score = jiffies - rt->u.dst.lastuse;
666
667         score = ~score & ~(3<<30);
668
669         if (rt_valuable(rt))
670                 score |= (1<<31);
671
672         if (!rt->fl.iif ||
673             !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL)))
674                 score |= (1<<30);
675
676         return score;
677 }
678
679 static inline bool rt_caching(const struct net *net)
680 {
681         return net->ipv4.current_rt_cache_rebuild_count <=
682                 net->ipv4.sysctl_rt_cache_rebuild_count;
683 }
684
685 static inline bool compare_hash_inputs(const struct flowi *fl1,
686                                         const struct flowi *fl2)
687 {
688         return (__force u32)(((fl1->nl_u.ip4_u.daddr ^ fl2->nl_u.ip4_u.daddr) |
689                 (fl1->nl_u.ip4_u.saddr ^ fl2->nl_u.ip4_u.saddr) |
690                 (fl1->iif ^ fl2->iif)) == 0);
691 }
692
693 static inline int compare_keys(struct flowi *fl1, struct flowi *fl2)
694 {
695         return ((__force u32)((fl1->nl_u.ip4_u.daddr ^ fl2->nl_u.ip4_u.daddr) |
696                 (fl1->nl_u.ip4_u.saddr ^ fl2->nl_u.ip4_u.saddr)) |
697                 (fl1->mark ^ fl2->mark) |
698                 (*(u16 *)&fl1->nl_u.ip4_u.tos ^
699                  *(u16 *)&fl2->nl_u.ip4_u.tos) |
700                 (fl1->oif ^ fl2->oif) |
701                 (fl1->iif ^ fl2->iif)) == 0;
702 }
703
704 static inline int compare_netns(struct rtable *rt1, struct rtable *rt2)
705 {
706         return dev_net(rt1->u.dst.dev) == dev_net(rt2->u.dst.dev);
707 }
708
709 static inline int rt_is_expired(struct rtable *rth)
710 {
711         return rth->rt_genid != rt_genid(dev_net(rth->u.dst.dev));
712 }
713
714 /*
715  * Perform a full scan of hash table and free all entries.
716  * Can be called by a softirq or a process.
717  * In the later case, we want to be reschedule if necessary
718  */
719 static void rt_do_flush(int process_context)
720 {
721         unsigned int i;
722         struct rtable *rth, *next;
723         struct rtable * tail;
724
725         for (i = 0; i <= rt_hash_mask; i++) {
726                 if (process_context && need_resched())
727                         cond_resched();
728                 rth = rt_hash_table[i].chain;
729                 if (!rth)
730                         continue;
731
732                 spin_lock_bh(rt_hash_lock_addr(i));
733 #ifdef CONFIG_NET_NS
734                 {
735                 struct rtable ** prev, * p;
736
737                 rth = rt_hash_table[i].chain;
738
739                 /* defer releasing the head of the list after spin_unlock */
740                 for (tail = rth; tail; tail = tail->u.dst.rt_next)
741                         if (!rt_is_expired(tail))
742                                 break;
743                 if (rth != tail)
744                         rt_hash_table[i].chain = tail;
745
746                 /* call rt_free on entries after the tail requiring flush */
747                 prev = &rt_hash_table[i].chain;
748                 for (p = *prev; p; p = next) {
749                         next = p->u.dst.rt_next;
750                         if (!rt_is_expired(p)) {
751                                 prev = &p->u.dst.rt_next;
752                         } else {
753                                 *prev = next;
754                                 rt_free(p);
755                         }
756                 }
757                 }
758 #else
759                 rth = rt_hash_table[i].chain;
760                 rt_hash_table[i].chain = NULL;
761                 tail = NULL;
762 #endif
763                 spin_unlock_bh(rt_hash_lock_addr(i));
764
765                 for (; rth != tail; rth = next) {
766                         next = rth->u.dst.rt_next;
767                         rt_free(rth);
768                 }
769         }
770 }
771
772 /*
773  * While freeing expired entries, we compute average chain length
774  * and standard deviation, using fixed-point arithmetic.
775  * This to have an estimation of rt_chain_length_max
776  *  rt_chain_length_max = max(elasticity, AVG + 4*SD)
777  * We use 3 bits for frational part, and 29 (or 61) for magnitude.
778  */
779
780 #define FRACT_BITS 3
781 #define ONE (1UL << FRACT_BITS)
782
783 static void rt_check_expire(void)
784 {
785         static unsigned int rover;
786         unsigned int i = rover, goal;
787         struct rtable *rth, **rthp;
788         unsigned long length = 0, samples = 0;
789         unsigned long sum = 0, sum2 = 0;
790         u64 mult;
791
792         mult = ((u64)ip_rt_gc_interval) << rt_hash_log;
793         if (ip_rt_gc_timeout > 1)
794                 do_div(mult, ip_rt_gc_timeout);
795         goal = (unsigned int)mult;
796         if (goal > rt_hash_mask)
797                 goal = rt_hash_mask + 1;
798         length = 0;
799         for (; goal > 0; goal--) {
800                 unsigned long tmo = ip_rt_gc_timeout;
801
802                 i = (i + 1) & rt_hash_mask;
803                 rthp = &rt_hash_table[i].chain;
804
805                 if (need_resched())
806                         cond_resched();
807
808                 samples++;
809
810                 if (*rthp == NULL)
811                         continue;
812                 spin_lock_bh(rt_hash_lock_addr(i));
813                 while ((rth = *rthp) != NULL) {
814                         if (rt_is_expired(rth)) {
815                                 *rthp = rth->u.dst.rt_next;
816                                 rt_free(rth);
817                                 continue;
818                         }
819                         if (rth->u.dst.expires) {
820                                 /* Entry is expired even if it is in use */
821                                 if (time_before_eq(jiffies, rth->u.dst.expires)) {
822                                         tmo >>= 1;
823                                         rthp = &rth->u.dst.rt_next;
824                                         /*
825                                          * Only bump our length if the hash
826                                          * inputs on entries n and n+1 are not
827                                          * the same, we only count entries on
828                                          * a chain with equal hash inputs once
829                                          * so that entries for different QOS
830                                          * levels, and other non-hash input
831                                          * attributes don't unfairly skew
832                                          * the length computation
833                                          */
834                                         if ((*rthp == NULL) ||
835                                             !compare_hash_inputs(&(*rthp)->fl,
836                                                                  &rth->fl))
837                                                 length += ONE;
838                                         continue;
839                                 }
840                         } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
841                                 tmo >>= 1;
842                                 rthp = &rth->u.dst.rt_next;
843                                 if ((*rthp == NULL) ||
844                                     !compare_hash_inputs(&(*rthp)->fl,
845                                                          &rth->fl))
846                                         length += ONE;
847                                 continue;
848                         }
849
850                         /* Cleanup aged off entries. */
851                         *rthp = rth->u.dst.rt_next;
852                         rt_free(rth);
853                 }
854                 spin_unlock_bh(rt_hash_lock_addr(i));
855                 sum += length;
856                 sum2 += length*length;
857         }
858         if (samples) {
859                 unsigned long avg = sum / samples;
860                 unsigned long sd = int_sqrt(sum2 / samples - avg*avg);
861                 rt_chain_length_max = max_t(unsigned long,
862                                         ip_rt_gc_elasticity,
863                                         (avg + 4*sd) >> FRACT_BITS);
864         }
865         rover = i;
866 }
867
868 /*
869  * rt_worker_func() is run in process context.
870  * we call rt_check_expire() to scan part of the hash table
871  */
872 static void rt_worker_func(struct work_struct *work)
873 {
874         rt_check_expire();
875         schedule_delayed_work(&expires_work, ip_rt_gc_interval);
876 }
877
878 /*
879  * Pertubation of rt_genid by a small quantity [1..256]
880  * Using 8 bits of shuffling ensure we can call rt_cache_invalidate()
881  * many times (2^24) without giving recent rt_genid.
882  * Jenkins hash is strong enough that litle changes of rt_genid are OK.
883  */
884 static void rt_cache_invalidate(struct net *net)
885 {
886         unsigned char shuffle;
887
888         get_random_bytes(&shuffle, sizeof(shuffle));
889         atomic_add(shuffle + 1U, &net->ipv4.rt_genid);
890 }
891
892 /*
893  * delay < 0  : invalidate cache (fast : entries will be deleted later)
894  * delay >= 0 : invalidate & flush cache (can be long)
895  */
896 void rt_cache_flush(struct net *net, int delay)
897 {
898         rt_cache_invalidate(net);
899         if (delay >= 0)
900                 rt_do_flush(!in_softirq());
901 }
902
903 /*
904  * We change rt_genid and let gc do the cleanup
905  */
906 static void rt_secret_rebuild(unsigned long __net)
907 {
908         struct net *net = (struct net *)__net;
909         rt_cache_invalidate(net);
910         mod_timer(&net->ipv4.rt_secret_timer, jiffies + ip_rt_secret_interval);
911 }
912
913 static void rt_secret_rebuild_oneshot(struct net *net)
914 {
915         del_timer_sync(&net->ipv4.rt_secret_timer);
916         rt_cache_invalidate(net);
917         if (ip_rt_secret_interval) {
918                 net->ipv4.rt_secret_timer.expires += ip_rt_secret_interval;
919                 add_timer(&net->ipv4.rt_secret_timer);
920         }
921 }
922
923 static void rt_emergency_hash_rebuild(struct net *net)
924 {
925         if (net_ratelimit()) {
926                 printk(KERN_WARNING "Route hash chain too long!\n");
927                 printk(KERN_WARNING "Adjust your secret_interval!\n");
928         }
929
930         rt_secret_rebuild_oneshot(net);
931 }
932
933 /*
934    Short description of GC goals.
935
936    We want to build algorithm, which will keep routing cache
937    at some equilibrium point, when number of aged off entries
938    is kept approximately equal to newly generated ones.
939
940    Current expiration strength is variable "expire".
941    We try to adjust it dynamically, so that if networking
942    is idle expires is large enough to keep enough of warm entries,
943    and when load increases it reduces to limit cache size.
944  */
945
946 static int rt_garbage_collect(struct dst_ops *ops)
947 {
948         static unsigned long expire = RT_GC_TIMEOUT;
949         static unsigned long last_gc;
950         static int rover;
951         static int equilibrium;
952         struct rtable *rth, **rthp;
953         unsigned long now = jiffies;
954         int goal;
955
956         /*
957          * Garbage collection is pretty expensive,
958          * do not make it too frequently.
959          */
960
961         RT_CACHE_STAT_INC(gc_total);
962
963         if (now - last_gc < ip_rt_gc_min_interval &&
964             atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size) {
965                 RT_CACHE_STAT_INC(gc_ignored);
966                 goto out;
967         }
968
969         /* Calculate number of entries, which we want to expire now. */
970         goal = atomic_read(&ipv4_dst_ops.entries) -
971                 (ip_rt_gc_elasticity << rt_hash_log);
972         if (goal <= 0) {
973                 if (equilibrium < ipv4_dst_ops.gc_thresh)
974                         equilibrium = ipv4_dst_ops.gc_thresh;
975                 goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
976                 if (goal > 0) {
977                         equilibrium += min_t(unsigned int, goal >> 1, rt_hash_mask + 1);
978                         goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
979                 }
980         } else {
981                 /* We are in dangerous area. Try to reduce cache really
982                  * aggressively.
983                  */
984                 goal = max_t(unsigned int, goal >> 1, rt_hash_mask + 1);
985                 equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
986         }
987
988         if (now - last_gc >= ip_rt_gc_min_interval)
989                 last_gc = now;
990
991         if (goal <= 0) {
992                 equilibrium += goal;
993                 goto work_done;
994         }
995
996         do {
997                 int i, k;
998
999                 for (i = rt_hash_mask, k = rover; i >= 0; i--) {
1000                         unsigned long tmo = expire;
1001
1002                         k = (k + 1) & rt_hash_mask;
1003                         rthp = &rt_hash_table[k].chain;
1004                         spin_lock_bh(rt_hash_lock_addr(k));
1005                         while ((rth = *rthp) != NULL) {
1006                                 if (!rt_is_expired(rth) &&
1007                                         !rt_may_expire(rth, tmo, expire)) {
1008                                         tmo >>= 1;
1009                                         rthp = &rth->u.dst.rt_next;
1010                                         continue;
1011                                 }
1012                                 *rthp = rth->u.dst.rt_next;
1013                                 rt_free(rth);
1014                                 goal--;
1015                         }
1016                         spin_unlock_bh(rt_hash_lock_addr(k));
1017                         if (goal <= 0)
1018                                 break;
1019                 }
1020                 rover = k;
1021
1022                 if (goal <= 0)
1023                         goto work_done;
1024
1025                 /* Goal is not achieved. We stop process if:
1026
1027                    - if expire reduced to zero. Otherwise, expire is halfed.
1028                    - if table is not full.
1029                    - if we are called from interrupt.
1030                    - jiffies check is just fallback/debug loop breaker.
1031                      We will not spin here for long time in any case.
1032                  */
1033
1034                 RT_CACHE_STAT_INC(gc_goal_miss);
1035
1036                 if (expire == 0)
1037                         break;
1038
1039                 expire >>= 1;
1040 #if RT_CACHE_DEBUG >= 2
1041                 printk(KERN_DEBUG "expire>> %u %d %d %d\n", expire,
1042                                 atomic_read(&ipv4_dst_ops.entries), goal, i);
1043 #endif
1044
1045                 if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
1046                         goto out;
1047         } while (!in_softirq() && time_before_eq(jiffies, now));
1048
1049         if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
1050                 goto out;
1051         if (net_ratelimit())
1052                 printk(KERN_WARNING "dst cache overflow\n");
1053         RT_CACHE_STAT_INC(gc_dst_overflow);
1054         return 1;
1055
1056 work_done:
1057         expire += ip_rt_gc_min_interval;
1058         if (expire > ip_rt_gc_timeout ||
1059             atomic_read(&ipv4_dst_ops.entries) < ipv4_dst_ops.gc_thresh)
1060                 expire = ip_rt_gc_timeout;
1061 #if RT_CACHE_DEBUG >= 2
1062         printk(KERN_DEBUG "expire++ %u %d %d %d\n", expire,
1063                         atomic_read(&ipv4_dst_ops.entries), goal, rover);
1064 #endif
1065 out:    return 0;
1066 }
1067
1068 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
1069 {
1070         struct rtable   *rth, **rthp;
1071         struct rtable   *rthi;
1072         unsigned long   now;
1073         struct rtable *cand, **candp;
1074         u32             min_score;
1075         int             chain_length;
1076         int attempts = !in_softirq();
1077
1078 restart:
1079         chain_length = 0;
1080         min_score = ~(u32)0;
1081         cand = NULL;
1082         candp = NULL;
1083         now = jiffies;
1084
1085         if (!rt_caching(dev_net(rt->u.dst.dev))) {
1086                 rt_drop(rt);
1087                 return 0;
1088         }
1089
1090         rthp = &rt_hash_table[hash].chain;
1091         rthi = NULL;
1092
1093         spin_lock_bh(rt_hash_lock_addr(hash));
1094         while ((rth = *rthp) != NULL) {
1095                 if (rt_is_expired(rth)) {
1096                         *rthp = rth->u.dst.rt_next;
1097                         rt_free(rth);
1098                         continue;
1099                 }
1100                 if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) {
1101                         /* Put it first */
1102                         *rthp = rth->u.dst.rt_next;
1103                         /*
1104                          * Since lookup is lockfree, the deletion
1105                          * must be visible to another weakly ordered CPU before
1106                          * the insertion at the start of the hash chain.
1107                          */
1108                         rcu_assign_pointer(rth->u.dst.rt_next,
1109                                            rt_hash_table[hash].chain);
1110                         /*
1111                          * Since lookup is lockfree, the update writes
1112                          * must be ordered for consistency on SMP.
1113                          */
1114                         rcu_assign_pointer(rt_hash_table[hash].chain, rth);
1115
1116                         dst_use(&rth->u.dst, now);
1117                         spin_unlock_bh(rt_hash_lock_addr(hash));
1118
1119                         rt_drop(rt);
1120                         *rp = rth;
1121                         return 0;
1122                 }
1123
1124                 if (!atomic_read(&rth->u.dst.__refcnt)) {
1125                         u32 score = rt_score(rth);
1126
1127                         if (score <= min_score) {
1128                                 cand = rth;
1129                                 candp = rthp;
1130                                 min_score = score;
1131                         }
1132                 }
1133
1134                 chain_length++;
1135
1136                 rthp = &rth->u.dst.rt_next;
1137
1138                 /*
1139                  * check to see if the next entry in the chain
1140                  * contains the same hash input values as rt.  If it does
1141                  * This is where we will insert into the list, instead of
1142                  * at the head.  This groups entries that differ by aspects not
1143                  * relvant to the hash function together, which we use to adjust
1144                  * our chain length
1145                  */
1146                 if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
1147                         rthi = rth;
1148         }
1149
1150         if (cand) {
1151                 /* ip_rt_gc_elasticity used to be average length of chain
1152                  * length, when exceeded gc becomes really aggressive.
1153                  *
1154                  * The second limit is less certain. At the moment it allows
1155                  * only 2 entries per bucket. We will see.
1156                  */
1157                 if (chain_length > ip_rt_gc_elasticity) {
1158                         *candp = cand->u.dst.rt_next;
1159                         rt_free(cand);
1160                 }
1161         } else {
1162                 if (chain_length > rt_chain_length_max) {
1163                         struct net *net = dev_net(rt->u.dst.dev);
1164                         int num = ++net->ipv4.current_rt_cache_rebuild_count;
1165                         if (!rt_caching(dev_net(rt->u.dst.dev))) {
1166                                 printk(KERN_WARNING "%s: %d rebuilds is over limit, route caching disabled\n",
1167                                         rt->u.dst.dev->name, num);
1168                         }
1169                         rt_emergency_hash_rebuild(dev_net(rt->u.dst.dev));
1170                 }
1171         }
1172
1173         /* Try to bind route to arp only if it is output
1174            route or unicast forwarding path.
1175          */
1176         if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
1177                 int err = arp_bind_neighbour(&rt->u.dst);
1178                 if (err) {
1179                         spin_unlock_bh(rt_hash_lock_addr(hash));
1180
1181                         if (err != -ENOBUFS) {
1182                                 rt_drop(rt);
1183                                 return err;
1184                         }
1185
1186                         /* Neighbour tables are full and nothing
1187                            can be released. Try to shrink route cache,
1188                            it is most likely it holds some neighbour records.
1189                          */
1190                         if (attempts-- > 0) {
1191                                 int saved_elasticity = ip_rt_gc_elasticity;
1192                                 int saved_int = ip_rt_gc_min_interval;
1193                                 ip_rt_gc_elasticity     = 1;
1194                                 ip_rt_gc_min_interval   = 0;
1195                                 rt_garbage_collect(&ipv4_dst_ops);
1196                                 ip_rt_gc_min_interval   = saved_int;
1197                                 ip_rt_gc_elasticity     = saved_elasticity;
1198                                 goto restart;
1199                         }
1200
1201                         if (net_ratelimit())
1202                                 printk(KERN_WARNING "Neighbour table overflow.\n");
1203                         rt_drop(rt);
1204                         return -ENOBUFS;
1205                 }
1206         }
1207
1208         if (rthi)
1209                 rt->u.dst.rt_next = rthi->u.dst.rt_next;
1210         else
1211                 rt->u.dst.rt_next = rt_hash_table[hash].chain;
1212
1213 #if RT_CACHE_DEBUG >= 2
1214         if (rt->u.dst.rt_next) {
1215                 struct rtable *trt;
1216                 printk(KERN_DEBUG "rt_cache @%02x: %pI4", hash, &rt->rt_dst);
1217                 for (trt = rt->u.dst.rt_next; trt; trt = trt->u.dst.rt_next)
1218                         printk(" . %pI4", &trt->rt_dst);
1219                 printk("\n");
1220         }
1221 #endif
1222         /*
1223          * Since lookup is lockfree, we must make sure
1224          * previous writes to rt are comitted to memory
1225          * before making rt visible to other CPUS.
1226          */
1227         if (rthi)
1228                 rcu_assign_pointer(rthi->u.dst.rt_next, rt);
1229         else
1230                 rcu_assign_pointer(rt_hash_table[hash].chain, rt);
1231
1232         spin_unlock_bh(rt_hash_lock_addr(hash));
1233         *rp = rt;
1234         return 0;
1235 }
1236
1237 void rt_bind_peer(struct rtable *rt, int create)
1238 {
1239         static DEFINE_SPINLOCK(rt_peer_lock);
1240         struct inet_peer *peer;
1241
1242         peer = inet_getpeer(rt->rt_dst, create);
1243
1244         spin_lock_bh(&rt_peer_lock);
1245         if (rt->peer == NULL) {
1246                 rt->peer = peer;
1247                 peer = NULL;
1248         }
1249         spin_unlock_bh(&rt_peer_lock);
1250         if (peer)
1251                 inet_putpeer(peer);
1252 }
1253
1254 /*
1255  * Peer allocation may fail only in serious out-of-memory conditions.  However
1256  * we still can generate some output.
1257  * Random ID selection looks a bit dangerous because we have no chances to
1258  * select ID being unique in a reasonable period of time.
1259  * But broken packet identifier may be better than no packet at all.
1260  */
1261 static void ip_select_fb_ident(struct iphdr *iph)
1262 {
1263         static DEFINE_SPINLOCK(ip_fb_id_lock);
1264         static u32 ip_fallback_id;
1265         u32 salt;
1266
1267         spin_lock_bh(&ip_fb_id_lock);
1268         salt = secure_ip_id((__force __be32)ip_fallback_id ^ iph->daddr);
1269         iph->id = htons(salt & 0xFFFF);
1270         ip_fallback_id = salt;
1271         spin_unlock_bh(&ip_fb_id_lock);
1272 }
1273
1274 void __ip_select_ident(struct iphdr *iph, struct dst_entry *dst, int more)
1275 {
1276         struct rtable *rt = (struct rtable *) dst;
1277
1278         if (rt) {
1279                 if (rt->peer == NULL)
1280                         rt_bind_peer(rt, 1);
1281
1282                 /* If peer is attached to destination, it is never detached,
1283                    so that we need not to grab a lock to dereference it.
1284                  */
1285                 if (rt->peer) {
1286                         iph->id = htons(inet_getid(rt->peer, more));
1287                         return;
1288                 }
1289         } else
1290                 printk(KERN_DEBUG "rt_bind_peer(0) @%p\n",
1291                        __builtin_return_address(0));
1292
1293         ip_select_fb_ident(iph);
1294 }
1295
1296 static void rt_del(unsigned hash, struct rtable *rt)
1297 {
1298         struct rtable **rthp, *aux;
1299
1300         rthp = &rt_hash_table[hash].chain;
1301         spin_lock_bh(rt_hash_lock_addr(hash));
1302         ip_rt_put(rt);
1303         while ((aux = *rthp) != NULL) {
1304                 if (aux == rt || rt_is_expired(aux)) {
1305                         *rthp = aux->u.dst.rt_next;
1306                         rt_free(aux);
1307                         continue;
1308                 }
1309                 rthp = &aux->u.dst.rt_next;
1310         }
1311         spin_unlock_bh(rt_hash_lock_addr(hash));
1312 }
1313
1314 void ip_rt_redirect(__be32 old_gw, __be32 daddr, __be32 new_gw,
1315                     __be32 saddr, struct net_device *dev)
1316 {
1317         int i, k;
1318         struct in_device *in_dev = in_dev_get(dev);
1319         struct rtable *rth, **rthp;
1320         __be32  skeys[2] = { saddr, 0 };
1321         int  ikeys[2] = { dev->ifindex, 0 };
1322         struct netevent_redirect netevent;
1323         struct net *net;
1324
1325         if (!in_dev)
1326                 return;
1327
1328         net = dev_net(dev);
1329         if (new_gw == old_gw || !IN_DEV_RX_REDIRECTS(in_dev)
1330             || ipv4_is_multicast(new_gw) || ipv4_is_lbcast(new_gw)
1331             || ipv4_is_zeronet(new_gw))
1332                 goto reject_redirect;
1333
1334         if (!rt_caching(net))
1335                 goto reject_redirect;
1336
1337         if (!IN_DEV_SHARED_MEDIA(in_dev)) {
1338                 if (!inet_addr_onlink(in_dev, new_gw, old_gw))
1339                         goto reject_redirect;
1340                 if (IN_DEV_SEC_REDIRECTS(in_dev) && ip_fib_check_default(new_gw, dev))
1341                         goto reject_redirect;
1342         } else {
1343                 if (inet_addr_type(net, new_gw) != RTN_UNICAST)
1344                         goto reject_redirect;
1345         }
1346
1347         for (i = 0; i < 2; i++) {
1348                 for (k = 0; k < 2; k++) {
1349                         unsigned hash = rt_hash(daddr, skeys[i], ikeys[k],
1350                                                 rt_genid(net));
1351
1352                         rthp=&rt_hash_table[hash].chain;
1353
1354                         rcu_read_lock();
1355                         while ((rth = rcu_dereference(*rthp)) != NULL) {
1356                                 struct rtable *rt;
1357
1358                                 if (rth->fl.fl4_dst != daddr ||
1359                                     rth->fl.fl4_src != skeys[i] ||
1360                                     rth->fl.oif != ikeys[k] ||
1361                                     rth->fl.iif != 0 ||
1362                                     rt_is_expired(rth) ||
1363                                     !net_eq(dev_net(rth->u.dst.dev), net)) {
1364                                         rthp = &rth->u.dst.rt_next;
1365                                         continue;
1366                                 }
1367
1368                                 if (rth->rt_dst != daddr ||
1369                                     rth->rt_src != saddr ||
1370                                     rth->u.dst.error ||
1371                                     rth->rt_gateway != old_gw ||
1372                                     rth->u.dst.dev != dev)
1373                                         break;
1374
1375                                 dst_hold(&rth->u.dst);
1376                                 rcu_read_unlock();
1377
1378                                 rt = dst_alloc(&ipv4_dst_ops);
1379                                 if (rt == NULL) {
1380                                         ip_rt_put(rth);
1381                                         in_dev_put(in_dev);
1382                                         return;
1383                                 }
1384
1385                                 /* Copy all the information. */
1386                                 *rt = *rth;
1387                                 rt->u.dst.__use         = 1;
1388                                 atomic_set(&rt->u.dst.__refcnt, 1);
1389                                 rt->u.dst.child         = NULL;
1390                                 if (rt->u.dst.dev)
1391                                         dev_hold(rt->u.dst.dev);
1392                                 if (rt->idev)
1393                                         in_dev_hold(rt->idev);
1394                                 rt->u.dst.obsolete      = 0;
1395                                 rt->u.dst.lastuse       = jiffies;
1396                                 rt->u.dst.path          = &rt->u.dst;
1397                                 rt->u.dst.neighbour     = NULL;
1398                                 rt->u.dst.hh            = NULL;
1399 #ifdef CONFIG_XFRM
1400                                 rt->u.dst.xfrm          = NULL;
1401 #endif
1402                                 rt->rt_genid            = rt_genid(net);
1403                                 rt->rt_flags            |= RTCF_REDIRECTED;
1404
1405                                 /* Gateway is different ... */
1406                                 rt->rt_gateway          = new_gw;
1407
1408                                 /* Redirect received -> path was valid */
1409                                 dst_confirm(&rth->u.dst);
1410
1411                                 if (rt->peer)
1412                                         atomic_inc(&rt->peer->refcnt);
1413
1414                                 if (arp_bind_neighbour(&rt->u.dst) ||
1415                                     !(rt->u.dst.neighbour->nud_state &
1416                                             NUD_VALID)) {
1417                                         if (rt->u.dst.neighbour)
1418                                                 neigh_event_send(rt->u.dst.neighbour, NULL);
1419                                         ip_rt_put(rth);
1420                                         rt_drop(rt);
1421                                         goto do_next;
1422                                 }
1423
1424                                 netevent.old = &rth->u.dst;
1425                                 netevent.new = &rt->u.dst;
1426                                 call_netevent_notifiers(NETEVENT_REDIRECT,
1427                                                         &netevent);
1428
1429                                 rt_del(hash, rth);
1430                                 if (!rt_intern_hash(hash, rt, &rt))
1431                                         ip_rt_put(rt);
1432                                 goto do_next;
1433                         }
1434                         rcu_read_unlock();
1435                 do_next:
1436                         ;
1437                 }
1438         }
1439         in_dev_put(in_dev);
1440         return;
1441
1442 reject_redirect:
1443 #ifdef CONFIG_IP_ROUTE_VERBOSE
1444         if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
1445                 printk(KERN_INFO "Redirect from %pI4 on %s about %pI4 ignored.\n"
1446                         "  Advised path = %pI4 -> %pI4\n",
1447                        &old_gw, dev->name, &new_gw,
1448                        &saddr, &daddr);
1449 #endif
1450         in_dev_put(in_dev);
1451 }
1452
1453 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst)
1454 {
1455         struct rtable *rt = (struct rtable *)dst;
1456         struct dst_entry *ret = dst;
1457
1458         if (rt) {
1459                 if (dst->obsolete) {
1460                         ip_rt_put(rt);
1461                         ret = NULL;
1462                 } else if ((rt->rt_flags & RTCF_REDIRECTED) ||
1463                            rt->u.dst.expires) {
1464                         unsigned hash = rt_hash(rt->fl.fl4_dst, rt->fl.fl4_src,
1465                                                 rt->fl.oif,
1466                                                 rt_genid(dev_net(dst->dev)));
1467 #if RT_CACHE_DEBUG >= 1
1468                         printk(KERN_DEBUG "ipv4_negative_advice: redirect to %pI4/%02x dropped\n",
1469                                 &rt->rt_dst, rt->fl.fl4_tos);
1470 #endif
1471                         rt_del(hash, rt);
1472                         ret = NULL;
1473                 }
1474         }
1475         return ret;
1476 }
1477
1478 /*
1479  * Algorithm:
1480  *      1. The first ip_rt_redirect_number redirects are sent
1481  *         with exponential backoff, then we stop sending them at all,
1482  *         assuming that the host ignores our redirects.
1483  *      2. If we did not see packets requiring redirects
1484  *         during ip_rt_redirect_silence, we assume that the host
1485  *         forgot redirected route and start to send redirects again.
1486  *
1487  * This algorithm is much cheaper and more intelligent than dumb load limiting
1488  * in icmp.c.
1489  *
1490  * NOTE. Do not forget to inhibit load limiting for redirects (redundant)
1491  * and "frag. need" (breaks PMTU discovery) in icmp.c.
1492  */
1493
1494 void ip_rt_send_redirect(struct sk_buff *skb)
1495 {
1496         struct rtable *rt = skb->rtable;
1497         struct in_device *in_dev = in_dev_get(rt->u.dst.dev);
1498
1499         if (!in_dev)
1500                 return;
1501
1502         if (!IN_DEV_TX_REDIRECTS(in_dev))
1503                 goto out;
1504
1505         /* No redirected packets during ip_rt_redirect_silence;
1506          * reset the algorithm.
1507          */
1508         if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence))
1509                 rt->u.dst.rate_tokens = 0;
1510
1511         /* Too many ignored redirects; do not send anything
1512          * set u.dst.rate_last to the last seen redirected packet.
1513          */
1514         if (rt->u.dst.rate_tokens >= ip_rt_redirect_number) {
1515                 rt->u.dst.rate_last = jiffies;
1516                 goto out;
1517         }
1518
1519         /* Check for load limit; set rate_last to the latest sent
1520          * redirect.
1521          */
1522         if (rt->u.dst.rate_tokens == 0 ||
1523             time_after(jiffies,
1524                        (rt->u.dst.rate_last +
1525                         (ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
1526                 icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
1527                 rt->u.dst.rate_last = jiffies;
1528                 ++rt->u.dst.rate_tokens;
1529 #ifdef CONFIG_IP_ROUTE_VERBOSE
1530                 if (IN_DEV_LOG_MARTIANS(in_dev) &&
1531                     rt->u.dst.rate_tokens == ip_rt_redirect_number &&
1532                     net_ratelimit())
1533                         printk(KERN_WARNING "host %pI4/if%d ignores redirects for %pI4 to %pI4.\n",
1534                                 &rt->rt_src, rt->rt_iif,
1535                                 &rt->rt_dst, &rt->rt_gateway);
1536 #endif
1537         }
1538 out:
1539         in_dev_put(in_dev);
1540 }
1541
1542 static int ip_error(struct sk_buff *skb)
1543 {
1544         struct rtable *rt = skb->rtable;
1545         unsigned long now;
1546         int code;
1547
1548         switch (rt->u.dst.error) {
1549                 case EINVAL:
1550                 default:
1551                         goto out;
1552                 case EHOSTUNREACH:
1553                         code = ICMP_HOST_UNREACH;
1554                         break;
1555                 case ENETUNREACH:
1556                         code = ICMP_NET_UNREACH;
1557                         IP_INC_STATS_BH(dev_net(rt->u.dst.dev),
1558                                         IPSTATS_MIB_INNOROUTES);
1559                         break;
1560                 case EACCES:
1561                         code = ICMP_PKT_FILTERED;
1562                         break;
1563         }
1564
1565         now = jiffies;
1566         rt->u.dst.rate_tokens += now - rt->u.dst.rate_last;
1567         if (rt->u.dst.rate_tokens > ip_rt_error_burst)
1568                 rt->u.dst.rate_tokens = ip_rt_error_burst;
1569         rt->u.dst.rate_last = now;
1570         if (rt->u.dst.rate_tokens >= ip_rt_error_cost) {
1571                 rt->u.dst.rate_tokens -= ip_rt_error_cost;
1572                 icmp_send(skb, ICMP_DEST_UNREACH, code, 0);
1573         }
1574
1575 out:    kfree_skb(skb);
1576         return 0;
1577 }
1578
1579 /*
1580  *      The last two values are not from the RFC but
1581  *      are needed for AMPRnet AX.25 paths.
1582  */
1583
1584 static const unsigned short mtu_plateau[] =
1585 {32000, 17914, 8166, 4352, 2002, 1492, 576, 296, 216, 128 };
1586
1587 static inline unsigned short guess_mtu(unsigned short old_mtu)
1588 {
1589         int i;
1590
1591         for (i = 0; i < ARRAY_SIZE(mtu_plateau); i++)
1592                 if (old_mtu > mtu_plateau[i])
1593                         return mtu_plateau[i];
1594         return 68;
1595 }
1596
1597 unsigned short ip_rt_frag_needed(struct net *net, struct iphdr *iph,
1598                                  unsigned short new_mtu,
1599                                  struct net_device *dev)
1600 {
1601         int i, k;
1602         unsigned short old_mtu = ntohs(iph->tot_len);
1603         struct rtable *rth;
1604         int  ikeys[2] = { dev->ifindex, 0 };
1605         __be32  skeys[2] = { iph->saddr, 0, };
1606         __be32  daddr = iph->daddr;
1607         unsigned short est_mtu = 0;
1608
1609         if (ipv4_config.no_pmtu_disc)
1610                 return 0;
1611
1612         for (k = 0; k < 2; k++) {
1613                 for (i = 0; i < 2; i++) {
1614                         unsigned hash = rt_hash(daddr, skeys[i], ikeys[k],
1615                                                 rt_genid(net));
1616
1617                         rcu_read_lock();
1618                         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
1619                              rth = rcu_dereference(rth->u.dst.rt_next)) {
1620                                 unsigned short mtu = new_mtu;
1621
1622                                 if (rth->fl.fl4_dst != daddr ||
1623                                     rth->fl.fl4_src != skeys[i] ||
1624                                     rth->rt_dst != daddr ||
1625                                     rth->rt_src != iph->saddr ||
1626                                     rth->fl.oif != ikeys[k] ||
1627                                     rth->fl.iif != 0 ||
1628                                     dst_metric_locked(&rth->u.dst, RTAX_MTU) ||
1629                                     !net_eq(dev_net(rth->u.dst.dev), net) ||
1630                                     rt_is_expired(rth))
1631                                         continue;
1632
1633                                 if (new_mtu < 68 || new_mtu >= old_mtu) {
1634
1635                                         /* BSD 4.2 compatibility hack :-( */
1636                                         if (mtu == 0 &&
1637                                             old_mtu >= dst_mtu(&rth->u.dst) &&
1638                                             old_mtu >= 68 + (iph->ihl << 2))
1639                                                 old_mtu -= iph->ihl << 2;
1640
1641                                         mtu = guess_mtu(old_mtu);
1642                                 }
1643                                 if (mtu <= dst_mtu(&rth->u.dst)) {
1644                                         if (mtu < dst_mtu(&rth->u.dst)) {
1645                                                 dst_confirm(&rth->u.dst);
1646                                                 if (mtu < ip_rt_min_pmtu) {
1647                                                         mtu = ip_rt_min_pmtu;
1648                                                         rth->u.dst.metrics[RTAX_LOCK-1] |=
1649                                                                 (1 << RTAX_MTU);
1650                                                 }
1651                                                 rth->u.dst.metrics[RTAX_MTU-1] = mtu;
1652                                                 dst_set_expires(&rth->u.dst,
1653                                                         ip_rt_mtu_expires);
1654                                         }
1655                                         est_mtu = mtu;
1656                                 }
1657                         }
1658                         rcu_read_unlock();
1659                 }
1660         }
1661         return est_mtu ? : new_mtu;
1662 }
1663
1664 static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu)
1665 {
1666         if (dst_mtu(dst) > mtu && mtu >= 68 &&
1667             !(dst_metric_locked(dst, RTAX_MTU))) {
1668                 if (mtu < ip_rt_min_pmtu) {
1669                         mtu = ip_rt_min_pmtu;
1670                         dst->metrics[RTAX_LOCK-1] |= (1 << RTAX_MTU);
1671                 }
1672                 dst->metrics[RTAX_MTU-1] = mtu;
1673                 dst_set_expires(dst, ip_rt_mtu_expires);
1674                 call_netevent_notifiers(NETEVENT_PMTU_UPDATE, dst);
1675         }
1676 }
1677
1678 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie)
1679 {
1680         return NULL;
1681 }
1682
1683 static void ipv4_dst_destroy(struct dst_entry *dst)
1684 {
1685         struct rtable *rt = (struct rtable *) dst;
1686         struct inet_peer *peer = rt->peer;
1687         struct in_device *idev = rt->idev;
1688
1689         if (peer) {
1690                 rt->peer = NULL;
1691                 inet_putpeer(peer);
1692         }
1693
1694         if (idev) {
1695                 rt->idev = NULL;
1696                 in_dev_put(idev);
1697         }
1698 }
1699
1700 static void ipv4_dst_ifdown(struct dst_entry *dst, struct net_device *dev,
1701                             int how)
1702 {
1703         struct rtable *rt = (struct rtable *) dst;
1704         struct in_device *idev = rt->idev;
1705         if (dev != dev_net(dev)->loopback_dev && idev && idev->dev == dev) {
1706                 struct in_device *loopback_idev =
1707                         in_dev_get(dev_net(dev)->loopback_dev);
1708                 if (loopback_idev) {
1709                         rt->idev = loopback_idev;
1710                         in_dev_put(idev);
1711                 }
1712         }
1713 }
1714
1715 static void ipv4_link_failure(struct sk_buff *skb)
1716 {
1717         struct rtable *rt;
1718
1719         icmp_send(skb, ICMP_DEST_UNREACH, ICMP_HOST_UNREACH, 0);
1720
1721         rt = skb->rtable;
1722         if (rt)
1723                 dst_set_expires(&rt->u.dst, 0);
1724 }
1725
1726 static int ip_rt_bug(struct sk_buff *skb)
1727 {
1728         printk(KERN_DEBUG "ip_rt_bug: %pI4 -> %pI4, %s\n",
1729                 &ip_hdr(skb)->saddr, &ip_hdr(skb)->daddr,
1730                 skb->dev ? skb->dev->name : "?");
1731         kfree_skb(skb);
1732         return 0;
1733 }
1734
1735 /*
1736    We do not cache source address of outgoing interface,
1737    because it is used only by IP RR, TS and SRR options,
1738    so that it out of fast path.
1739
1740    BTW remember: "addr" is allowed to be not aligned
1741    in IP options!
1742  */
1743
1744 void ip_rt_get_source(u8 *addr, struct rtable *rt)
1745 {
1746         __be32 src;
1747         struct fib_result res;
1748
1749         if (rt->fl.iif == 0)
1750                 src = rt->rt_src;
1751         else if (fib_lookup(dev_net(rt->u.dst.dev), &rt->fl, &res) == 0) {
1752                 src = FIB_RES_PREFSRC(res);
1753                 fib_res_put(&res);
1754         } else
1755                 src = inet_select_addr(rt->u.dst.dev, rt->rt_gateway,
1756                                         RT_SCOPE_UNIVERSE);
1757         memcpy(addr, &src, 4);
1758 }
1759
1760 #ifdef CONFIG_NET_CLS_ROUTE
1761 static void set_class_tag(struct rtable *rt, u32 tag)
1762 {
1763         if (!(rt->u.dst.tclassid & 0xFFFF))
1764                 rt->u.dst.tclassid |= tag & 0xFFFF;
1765         if (!(rt->u.dst.tclassid & 0xFFFF0000))
1766                 rt->u.dst.tclassid |= tag & 0xFFFF0000;
1767 }
1768 #endif
1769
1770 static void rt_set_nexthop(struct rtable *rt, struct fib_result *res, u32 itag)
1771 {
1772         struct fib_info *fi = res->fi;
1773
1774         if (fi) {
1775                 if (FIB_RES_GW(*res) &&
1776                     FIB_RES_NH(*res).nh_scope == RT_SCOPE_LINK)
1777                         rt->rt_gateway = FIB_RES_GW(*res);
1778                 memcpy(rt->u.dst.metrics, fi->fib_metrics,
1779                        sizeof(rt->u.dst.metrics));
1780                 if (fi->fib_mtu == 0) {
1781                         rt->u.dst.metrics[RTAX_MTU-1] = rt->u.dst.dev->mtu;
1782                         if (dst_metric_locked(&rt->u.dst, RTAX_MTU) &&
1783                             rt->rt_gateway != rt->rt_dst &&
1784                             rt->u.dst.dev->mtu > 576)
1785                                 rt->u.dst.metrics[RTAX_MTU-1] = 576;
1786                 }
1787 #ifdef CONFIG_NET_CLS_ROUTE
1788                 rt->u.dst.tclassid = FIB_RES_NH(*res).nh_tclassid;
1789 #endif
1790         } else
1791                 rt->u.dst.metrics[RTAX_MTU-1]= rt->u.dst.dev->mtu;
1792
1793         if (dst_metric(&rt->u.dst, RTAX_HOPLIMIT) == 0)
1794                 rt->u.dst.metrics[RTAX_HOPLIMIT-1] = sysctl_ip_default_ttl;
1795         if (dst_mtu(&rt->u.dst) > IP_MAX_MTU)
1796                 rt->u.dst.metrics[RTAX_MTU-1] = IP_MAX_MTU;
1797         if (dst_metric(&rt->u.dst, RTAX_ADVMSS) == 0)
1798                 rt->u.dst.metrics[RTAX_ADVMSS-1] = max_t(unsigned int, rt->u.dst.dev->mtu - 40,
1799                                        ip_rt_min_advmss);
1800         if (dst_metric(&rt->u.dst, RTAX_ADVMSS) > 65535 - 40)
1801                 rt->u.dst.metrics[RTAX_ADVMSS-1] = 65535 - 40;
1802
1803 #ifdef CONFIG_NET_CLS_ROUTE
1804 #ifdef CONFIG_IP_MULTIPLE_TABLES
1805         set_class_tag(rt, fib_rules_tclass(res));
1806 #endif
1807         set_class_tag(rt, itag);
1808 #endif
1809         rt->rt_type = res->type;
1810 }
1811
1812 static int ip_route_input_mc(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1813                                 u8 tos, struct net_device *dev, int our)
1814 {
1815         unsigned hash;
1816         struct rtable *rth;
1817         __be32 spec_dst;
1818         struct in_device *in_dev = in_dev_get(dev);
1819         u32 itag = 0;
1820
1821         /* Primary sanity checks. */
1822
1823         if (in_dev == NULL)
1824                 return -EINVAL;
1825
1826         if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr) ||
1827             ipv4_is_loopback(saddr) || skb->protocol != htons(ETH_P_IP))
1828                 goto e_inval;
1829
1830         if (ipv4_is_zeronet(saddr)) {
1831                 if (!ipv4_is_local_multicast(daddr))
1832                         goto e_inval;
1833                 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
1834         } else if (fib_validate_source(saddr, 0, tos, 0,
1835                                         dev, &spec_dst, &itag) < 0)
1836                 goto e_inval;
1837
1838         rth = dst_alloc(&ipv4_dst_ops);
1839         if (!rth)
1840                 goto e_nobufs;
1841
1842         rth->u.dst.output= ip_rt_bug;
1843
1844         atomic_set(&rth->u.dst.__refcnt, 1);
1845         rth->u.dst.flags= DST_HOST;
1846         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1847                 rth->u.dst.flags |= DST_NOPOLICY;
1848         rth->fl.fl4_dst = daddr;
1849         rth->rt_dst     = daddr;
1850         rth->fl.fl4_tos = tos;
1851         rth->fl.mark    = skb->mark;
1852         rth->fl.fl4_src = saddr;
1853         rth->rt_src     = saddr;
1854 #ifdef CONFIG_NET_CLS_ROUTE
1855         rth->u.dst.tclassid = itag;
1856 #endif
1857         rth->rt_iif     =
1858         rth->fl.iif     = dev->ifindex;
1859         rth->u.dst.dev  = init_net.loopback_dev;
1860         dev_hold(rth->u.dst.dev);
1861         rth->idev       = in_dev_get(rth->u.dst.dev);
1862         rth->fl.oif     = 0;
1863         rth->rt_gateway = daddr;
1864         rth->rt_spec_dst= spec_dst;
1865         rth->rt_genid   = rt_genid(dev_net(dev));
1866         rth->rt_flags   = RTCF_MULTICAST;
1867         rth->rt_type    = RTN_MULTICAST;
1868         if (our) {
1869                 rth->u.dst.input= ip_local_deliver;
1870                 rth->rt_flags |= RTCF_LOCAL;
1871         }
1872
1873 #ifdef CONFIG_IP_MROUTE
1874         if (!ipv4_is_local_multicast(daddr) && IN_DEV_MFORWARD(in_dev))
1875                 rth->u.dst.input = ip_mr_input;
1876 #endif
1877         RT_CACHE_STAT_INC(in_slow_mc);
1878
1879         in_dev_put(in_dev);
1880         hash = rt_hash(daddr, saddr, dev->ifindex, rt_genid(dev_net(dev)));
1881         return rt_intern_hash(hash, rth, &skb->rtable);
1882
1883 e_nobufs:
1884         in_dev_put(in_dev);
1885         return -ENOBUFS;
1886
1887 e_inval:
1888         in_dev_put(in_dev);
1889         return -EINVAL;
1890 }
1891
1892
1893 static void ip_handle_martian_source(struct net_device *dev,
1894                                      struct in_device *in_dev,
1895                                      struct sk_buff *skb,
1896                                      __be32 daddr,
1897                                      __be32 saddr)
1898 {
1899         RT_CACHE_STAT_INC(in_martian_src);
1900 #ifdef CONFIG_IP_ROUTE_VERBOSE
1901         if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit()) {
1902                 /*
1903                  *      RFC1812 recommendation, if source is martian,
1904                  *      the only hint is MAC header.
1905                  */
1906                 printk(KERN_WARNING "martian source %pI4 from %pI4, on dev %s\n",
1907                         &daddr, &saddr, dev->name);
1908                 if (dev->hard_header_len && skb_mac_header_was_set(skb)) {
1909                         int i;
1910                         const unsigned char *p = skb_mac_header(skb);
1911                         printk(KERN_WARNING "ll header: ");
1912                         for (i = 0; i < dev->hard_header_len; i++, p++) {
1913                                 printk("%02x", *p);
1914                                 if (i < (dev->hard_header_len - 1))
1915                                         printk(":");
1916                         }
1917                         printk("\n");
1918                 }
1919         }
1920 #endif
1921 }
1922
1923 static int __mkroute_input(struct sk_buff *skb,
1924                            struct fib_result *res,
1925                            struct in_device *in_dev,
1926                            __be32 daddr, __be32 saddr, u32 tos,
1927                            struct rtable **result)
1928 {
1929
1930         struct rtable *rth;
1931         int err;
1932         struct in_device *out_dev;
1933         unsigned flags = 0;
1934         __be32 spec_dst;
1935         u32 itag;
1936
1937         /* get a working reference to the output device */
1938         out_dev = in_dev_get(FIB_RES_DEV(*res));
1939         if (out_dev == NULL) {
1940                 if (net_ratelimit())
1941                         printk(KERN_CRIT "Bug in ip_route_input" \
1942                                "_slow(). Please, report\n");
1943                 return -EINVAL;
1944         }
1945
1946
1947         err = fib_validate_source(saddr, daddr, tos, FIB_RES_OIF(*res),
1948                                   in_dev->dev, &spec_dst, &itag);
1949         if (err < 0) {
1950                 ip_handle_martian_source(in_dev->dev, in_dev, skb, daddr,
1951                                          saddr);
1952
1953                 err = -EINVAL;
1954                 goto cleanup;
1955         }
1956
1957         if (err)
1958                 flags |= RTCF_DIRECTSRC;
1959
1960         if (out_dev == in_dev && err &&
1961             (IN_DEV_SHARED_MEDIA(out_dev) ||
1962              inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
1963                 flags |= RTCF_DOREDIRECT;
1964
1965         if (skb->protocol != htons(ETH_P_IP)) {
1966                 /* Not IP (i.e. ARP). Do not create route, if it is
1967                  * invalid for proxy arp. DNAT routes are always valid.
1968                  */
1969                 if (out_dev == in_dev) {
1970                         err = -EINVAL;
1971                         goto cleanup;
1972                 }
1973         }
1974
1975
1976         rth = dst_alloc(&ipv4_dst_ops);
1977         if (!rth) {
1978                 err = -ENOBUFS;
1979                 goto cleanup;
1980         }
1981
1982         atomic_set(&rth->u.dst.__refcnt, 1);
1983         rth->u.dst.flags= DST_HOST;
1984         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1985                 rth->u.dst.flags |= DST_NOPOLICY;
1986         if (IN_DEV_CONF_GET(out_dev, NOXFRM))
1987                 rth->u.dst.flags |= DST_NOXFRM;
1988         rth->fl.fl4_dst = daddr;
1989         rth->rt_dst     = daddr;
1990         rth->fl.fl4_tos = tos;
1991         rth->fl.mark    = skb->mark;
1992         rth->fl.fl4_src = saddr;
1993         rth->rt_src     = saddr;
1994         rth->rt_gateway = daddr;
1995         rth->rt_iif     =
1996                 rth->fl.iif     = in_dev->dev->ifindex;
1997         rth->u.dst.dev  = (out_dev)->dev;
1998         dev_hold(rth->u.dst.dev);
1999         rth->idev       = in_dev_get(rth->u.dst.dev);
2000         rth->fl.oif     = 0;
2001         rth->rt_spec_dst= spec_dst;
2002
2003         rth->u.dst.input = ip_forward;
2004         rth->u.dst.output = ip_output;
2005         rth->rt_genid = rt_genid(dev_net(rth->u.dst.dev));
2006
2007         rt_set_nexthop(rth, res, itag);
2008
2009         rth->rt_flags = flags;
2010
2011         *result = rth;
2012         err = 0;
2013  cleanup:
2014         /* release the working reference to the output device */
2015         in_dev_put(out_dev);
2016         return err;
2017 }
2018
2019 static int ip_mkroute_input(struct sk_buff *skb,
2020                             struct fib_result *res,
2021                             const struct flowi *fl,
2022                             struct in_device *in_dev,
2023                             __be32 daddr, __be32 saddr, u32 tos)
2024 {
2025         struct rtable* rth = NULL;
2026         int err;
2027         unsigned hash;
2028
2029 #ifdef CONFIG_IP_ROUTE_MULTIPATH
2030         if (res->fi && res->fi->fib_nhs > 1 && fl->oif == 0)
2031                 fib_select_multipath(fl, res);
2032 #endif
2033
2034         /* create a routing cache entry */
2035         err = __mkroute_input(skb, res, in_dev, daddr, saddr, tos, &rth);
2036         if (err)
2037                 return err;
2038
2039         /* put it into the cache */
2040         hash = rt_hash(daddr, saddr, fl->iif,
2041                        rt_genid(dev_net(rth->u.dst.dev)));
2042         return rt_intern_hash(hash, rth, &skb->rtable);
2043 }
2044
2045 /*
2046  *      NOTE. We drop all the packets that has local source
2047  *      addresses, because every properly looped back packet
2048  *      must have correct destination already attached by output routine.
2049  *
2050  *      Such approach solves two big problems:
2051  *      1. Not simplex devices are handled properly.
2052  *      2. IP spoofing attempts are filtered with 100% of guarantee.
2053  */
2054
2055 static int ip_route_input_slow(struct sk_buff *skb, __be32 daddr, __be32 saddr,
2056                                u8 tos, struct net_device *dev)
2057 {
2058         struct fib_result res;
2059         struct in_device *in_dev = in_dev_get(dev);
2060         struct flowi fl = { .nl_u = { .ip4_u =
2061                                       { .daddr = daddr,
2062                                         .saddr = saddr,
2063                                         .tos = tos,
2064                                         .scope = RT_SCOPE_UNIVERSE,
2065                                       } },
2066                             .mark = skb->mark,
2067                             .iif = dev->ifindex };
2068         unsigned        flags = 0;
2069         u32             itag = 0;
2070         struct rtable * rth;
2071         unsigned        hash;
2072         __be32          spec_dst;
2073         int             err = -EINVAL;
2074         int             free_res = 0;
2075         struct net    * net = dev_net(dev);
2076
2077         /* IP on this device is disabled. */
2078
2079         if (!in_dev)
2080                 goto out;
2081
2082         /* Check for the most weird martians, which can be not detected
2083            by fib_lookup.
2084          */
2085
2086         if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr) ||
2087             ipv4_is_loopback(saddr))
2088                 goto martian_source;
2089
2090         if (daddr == htonl(0xFFFFFFFF) || (saddr == 0 && daddr == 0))
2091                 goto brd_input;
2092
2093         /* Accept zero addresses only to limited broadcast;
2094          * I even do not know to fix it or not. Waiting for complains :-)
2095          */
2096         if (ipv4_is_zeronet(saddr))
2097                 goto martian_source;
2098
2099         if (ipv4_is_lbcast(daddr) || ipv4_is_zeronet(daddr) ||
2100             ipv4_is_loopback(daddr))
2101                 goto martian_destination;
2102
2103         /*
2104          *      Now we are ready to route packet.
2105          */
2106         if ((err = fib_lookup(net, &fl, &res)) != 0) {
2107                 if (!IN_DEV_FORWARD(in_dev))
2108                         goto e_hostunreach;
2109                 goto no_route;
2110         }
2111         free_res = 1;
2112
2113         RT_CACHE_STAT_INC(in_slow_tot);
2114
2115         if (res.type == RTN_BROADCAST)
2116                 goto brd_input;
2117
2118         if (res.type == RTN_LOCAL) {
2119                 int result;
2120                 result = fib_validate_source(saddr, daddr, tos,
2121                                              net->loopback_dev->ifindex,
2122                                              dev, &spec_dst, &itag);
2123                 if (result < 0)
2124                         goto martian_source;
2125                 if (result)
2126                         flags |= RTCF_DIRECTSRC;
2127                 spec_dst = daddr;
2128                 goto local_input;
2129         }
2130
2131         if (!IN_DEV_FORWARD(in_dev))
2132                 goto e_hostunreach;
2133         if (res.type != RTN_UNICAST)
2134                 goto martian_destination;
2135
2136         err = ip_mkroute_input(skb, &res, &fl, in_dev, daddr, saddr, tos);
2137 done:
2138         in_dev_put(in_dev);
2139         if (free_res)
2140                 fib_res_put(&res);
2141 out:    return err;
2142
2143 brd_input:
2144         if (skb->protocol != htons(ETH_P_IP))
2145                 goto e_inval;
2146
2147         if (ipv4_is_zeronet(saddr))
2148                 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
2149         else {
2150                 err = fib_validate_source(saddr, 0, tos, 0, dev, &spec_dst,
2151                                           &itag);
2152                 if (err < 0)
2153                         goto martian_source;
2154                 if (err)
2155                         flags |= RTCF_DIRECTSRC;
2156         }
2157         flags |= RTCF_BROADCAST;
2158         res.type = RTN_BROADCAST;
2159         RT_CACHE_STAT_INC(in_brd);
2160
2161 local_input:
2162         rth = dst_alloc(&ipv4_dst_ops);
2163         if (!rth)
2164                 goto e_nobufs;
2165
2166         rth->u.dst.output= ip_rt_bug;
2167         rth->rt_genid = rt_genid(net);
2168
2169         atomic_set(&rth->u.dst.__refcnt, 1);
2170         rth->u.dst.flags= DST_HOST;
2171         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2172                 rth->u.dst.flags |= DST_NOPOLICY;
2173         rth->fl.fl4_dst = daddr;
2174         rth->rt_dst     = daddr;
2175         rth->fl.fl4_tos = tos;
2176         rth->fl.mark    = skb->mark;
2177         rth->fl.fl4_src = saddr;
2178         rth->rt_src     = saddr;
2179 #ifdef CONFIG_NET_CLS_ROUTE
2180         rth->u.dst.tclassid = itag;
2181 #endif
2182         rth->rt_iif     =
2183         rth->fl.iif     = dev->ifindex;
2184         rth->u.dst.dev  = net->loopback_dev;
2185         dev_hold(rth->u.dst.dev);
2186         rth->idev       = in_dev_get(rth->u.dst.dev);
2187         rth->rt_gateway = daddr;
2188         rth->rt_spec_dst= spec_dst;
2189         rth->u.dst.input= ip_local_deliver;
2190         rth->rt_flags   = flags|RTCF_LOCAL;
2191         if (res.type == RTN_UNREACHABLE) {
2192                 rth->u.dst.input= ip_error;
2193                 rth->u.dst.error= -err;
2194                 rth->rt_flags   &= ~RTCF_LOCAL;
2195         }
2196         rth->rt_type    = res.type;
2197         hash = rt_hash(daddr, saddr, fl.iif, rt_genid(net));
2198         err = rt_intern_hash(hash, rth, &skb->rtable);
2199         goto done;
2200
2201 no_route:
2202         RT_CACHE_STAT_INC(in_no_route);
2203         spec_dst = inet_select_addr(dev, 0, RT_SCOPE_UNIVERSE);
2204         res.type = RTN_UNREACHABLE;
2205         if (err == -ESRCH)
2206                 err = -ENETUNREACH;
2207         goto local_input;
2208
2209         /*
2210          *      Do not cache martian addresses: they should be logged (RFC1812)
2211          */
2212 martian_destination:
2213         RT_CACHE_STAT_INC(in_martian_dst);
2214 #ifdef CONFIG_IP_ROUTE_VERBOSE
2215         if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
2216                 printk(KERN_WARNING "martian destination %pI4 from %pI4, dev %s\n",
2217                         &daddr, &saddr, dev->name);
2218 #endif
2219
2220 e_hostunreach:
2221         err = -EHOSTUNREACH;
2222         goto done;
2223
2224 e_inval:
2225         err = -EINVAL;
2226         goto done;
2227
2228 e_nobufs:
2229         err = -ENOBUFS;
2230         goto done;
2231
2232 martian_source:
2233         ip_handle_martian_source(dev, in_dev, skb, daddr, saddr);
2234         goto e_inval;
2235 }
2236
2237 int ip_route_input(struct sk_buff *skb, __be32 daddr, __be32 saddr,
2238                    u8 tos, struct net_device *dev)
2239 {
2240         struct rtable * rth;
2241         unsigned        hash;
2242         int iif = dev->ifindex;
2243         struct net *net;
2244
2245         net = dev_net(dev);
2246
2247         if (!rt_caching(net))
2248                 goto skip_cache;
2249
2250         tos &= IPTOS_RT_MASK;
2251         hash = rt_hash(daddr, saddr, iif, rt_genid(net));
2252
2253         rcu_read_lock();
2254         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2255              rth = rcu_dereference(rth->u.dst.rt_next)) {
2256                 if (((rth->fl.fl4_dst ^ daddr) |
2257                      (rth->fl.fl4_src ^ saddr) |
2258                      (rth->fl.iif ^ iif) |
2259                      rth->fl.oif |
2260                      (rth->fl.fl4_tos ^ tos)) == 0 &&
2261                     rth->fl.mark == skb->mark &&
2262                     net_eq(dev_net(rth->u.dst.dev), net) &&
2263                     !rt_is_expired(rth)) {
2264                         dst_use(&rth->u.dst, jiffies);
2265                         RT_CACHE_STAT_INC(in_hit);
2266                         rcu_read_unlock();
2267                         skb->rtable = rth;
2268                         return 0;
2269                 }
2270                 RT_CACHE_STAT_INC(in_hlist_search);
2271         }
2272         rcu_read_unlock();
2273
2274 skip_cache:
2275         /* Multicast recognition logic is moved from route cache to here.
2276            The problem was that too many Ethernet cards have broken/missing
2277            hardware multicast filters :-( As result the host on multicasting
2278            network acquires a lot of useless route cache entries, sort of
2279            SDR messages from all the world. Now we try to get rid of them.
2280            Really, provided software IP multicast filter is organized
2281            reasonably (at least, hashed), it does not result in a slowdown
2282            comparing with route cache reject entries.
2283            Note, that multicast routers are not affected, because
2284            route cache entry is created eventually.
2285          */
2286         if (ipv4_is_multicast(daddr)) {
2287                 struct in_device *in_dev;
2288
2289                 rcu_read_lock();
2290                 if ((in_dev = __in_dev_get_rcu(dev)) != NULL) {
2291                         int our = ip_check_mc(in_dev, daddr, saddr,
2292                                 ip_hdr(skb)->protocol);
2293                         if (our
2294 #ifdef CONFIG_IP_MROUTE
2295                             || (!ipv4_is_local_multicast(daddr) &&
2296                                 IN_DEV_MFORWARD(in_dev))
2297 #endif
2298                             ) {
2299                                 rcu_read_unlock();
2300                                 return ip_route_input_mc(skb, daddr, saddr,
2301                                                          tos, dev, our);
2302                         }
2303                 }
2304                 rcu_read_unlock();
2305                 return -EINVAL;
2306         }
2307         return ip_route_input_slow(skb, daddr, saddr, tos, dev);
2308 }
2309
2310 static int __mkroute_output(struct rtable **result,
2311                             struct fib_result *res,
2312                             const struct flowi *fl,
2313                             const struct flowi *oldflp,
2314                             struct net_device *dev_out,
2315                             unsigned flags)
2316 {
2317         struct rtable *rth;
2318         struct in_device *in_dev;
2319         u32 tos = RT_FL_TOS(oldflp);
2320         int err = 0;
2321
2322         if (ipv4_is_loopback(fl->fl4_src) && !(dev_out->flags&IFF_LOOPBACK))
2323                 return -EINVAL;
2324
2325         if (fl->fl4_dst == htonl(0xFFFFFFFF))
2326                 res->type = RTN_BROADCAST;
2327         else if (ipv4_is_multicast(fl->fl4_dst))
2328                 res->type = RTN_MULTICAST;
2329         else if (ipv4_is_lbcast(fl->fl4_dst) || ipv4_is_zeronet(fl->fl4_dst))
2330                 return -EINVAL;
2331
2332         if (dev_out->flags & IFF_LOOPBACK)
2333                 flags |= RTCF_LOCAL;
2334
2335         /* get work reference to inet device */
2336         in_dev = in_dev_get(dev_out);
2337         if (!in_dev)
2338                 return -EINVAL;
2339
2340         if (res->type == RTN_BROADCAST) {
2341                 flags |= RTCF_BROADCAST | RTCF_LOCAL;
2342                 if (res->fi) {
2343                         fib_info_put(res->fi);
2344                         res->fi = NULL;
2345                 }
2346         } else if (res->type == RTN_MULTICAST) {
2347                 flags |= RTCF_MULTICAST|RTCF_LOCAL;
2348                 if (!ip_check_mc(in_dev, oldflp->fl4_dst, oldflp->fl4_src,
2349                                  oldflp->proto))
2350                         flags &= ~RTCF_LOCAL;
2351                 /* If multicast route do not exist use
2352                    default one, but do not gateway in this case.
2353                    Yes, it is hack.
2354                  */
2355                 if (res->fi && res->prefixlen < 4) {
2356                         fib_info_put(res->fi);
2357                         res->fi = NULL;
2358                 }
2359         }
2360
2361
2362         rth = dst_alloc(&ipv4_dst_ops);
2363         if (!rth) {
2364                 err = -ENOBUFS;
2365                 goto cleanup;
2366         }
2367
2368         atomic_set(&rth->u.dst.__refcnt, 1);
2369         rth->u.dst.flags= DST_HOST;
2370         if (IN_DEV_CONF_GET(in_dev, NOXFRM))
2371                 rth->u.dst.flags |= DST_NOXFRM;
2372         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2373                 rth->u.dst.flags |= DST_NOPOLICY;
2374
2375         rth->fl.fl4_dst = oldflp->fl4_dst;
2376         rth->fl.fl4_tos = tos;
2377         rth->fl.fl4_src = oldflp->fl4_src;
2378         rth->fl.oif     = oldflp->oif;
2379         rth->fl.mark    = oldflp->mark;
2380         rth->rt_dst     = fl->fl4_dst;
2381         rth->rt_src     = fl->fl4_src;
2382         rth->rt_iif     = oldflp->oif ? : dev_out->ifindex;
2383         /* get references to the devices that are to be hold by the routing
2384            cache entry */
2385         rth->u.dst.dev  = dev_out;
2386         dev_hold(dev_out);
2387         rth->idev       = in_dev_get(dev_out);
2388         rth->rt_gateway = fl->fl4_dst;
2389         rth->rt_spec_dst= fl->fl4_src;
2390
2391         rth->u.dst.output=ip_output;
2392         rth->rt_genid = rt_genid(dev_net(dev_out));
2393
2394         RT_CACHE_STAT_INC(out_slow_tot);
2395
2396         if (flags & RTCF_LOCAL) {
2397                 rth->u.dst.input = ip_local_deliver;
2398                 rth->rt_spec_dst = fl->fl4_dst;
2399         }
2400         if (flags & (RTCF_BROADCAST | RTCF_MULTICAST)) {
2401                 rth->rt_spec_dst = fl->fl4_src;
2402                 if (flags & RTCF_LOCAL &&
2403                     !(dev_out->flags & IFF_LOOPBACK)) {
2404                         rth->u.dst.output = ip_mc_output;
2405                         RT_CACHE_STAT_INC(out_slow_mc);
2406                 }
2407 #ifdef CONFIG_IP_MROUTE
2408                 if (res->type == RTN_MULTICAST) {
2409                         if (IN_DEV_MFORWARD(in_dev) &&
2410                             !ipv4_is_local_multicast(oldflp->fl4_dst)) {
2411                                 rth->u.dst.input = ip_mr_input;
2412                                 rth->u.dst.output = ip_mc_output;
2413                         }
2414                 }
2415 #endif
2416         }
2417
2418         rt_set_nexthop(rth, res, 0);
2419
2420         rth->rt_flags = flags;
2421
2422         *result = rth;
2423  cleanup:
2424         /* release work reference to inet device */
2425         in_dev_put(in_dev);
2426
2427         return err;
2428 }
2429
2430 static int ip_mkroute_output(struct rtable **rp,
2431                              struct fib_result *res,
2432                              const struct flowi *fl,
2433                              const struct flowi *oldflp,
2434                              struct net_device *dev_out,
2435                              unsigned flags)
2436 {
2437         struct rtable *rth = NULL;
2438         int err = __mkroute_output(&rth, res, fl, oldflp, dev_out, flags);
2439         unsigned hash;
2440         if (err == 0) {
2441                 hash = rt_hash(oldflp->fl4_dst, oldflp->fl4_src, oldflp->oif,
2442                                rt_genid(dev_net(dev_out)));
2443                 err = rt_intern_hash(hash, rth, rp);
2444         }
2445
2446         return err;
2447 }
2448
2449 /*
2450  * Major route resolver routine.
2451  */
2452
2453 static int ip_route_output_slow(struct net *net, struct rtable **rp,
2454                                 const struct flowi *oldflp)
2455 {
2456         u32 tos = RT_FL_TOS(oldflp);
2457         struct flowi fl = { .nl_u = { .ip4_u =
2458                                       { .daddr = oldflp->fl4_dst,
2459                                         .saddr = oldflp->fl4_src,
2460                                         .tos = tos & IPTOS_RT_MASK,
2461                                         .scope = ((tos & RTO_ONLINK) ?
2462                                                   RT_SCOPE_LINK :
2463                                                   RT_SCOPE_UNIVERSE),
2464                                       } },
2465                             .mark = oldflp->mark,
2466                             .iif = net->loopback_dev->ifindex,
2467                             .oif = oldflp->oif };
2468         struct fib_result res;
2469         unsigned flags = 0;
2470         struct net_device *dev_out = NULL;
2471         int free_res = 0;
2472         int err;
2473
2474
2475         res.fi          = NULL;
2476 #ifdef CONFIG_IP_MULTIPLE_TABLES
2477         res.r           = NULL;
2478 #endif
2479
2480         if (oldflp->fl4_src) {
2481                 err = -EINVAL;
2482                 if (ipv4_is_multicast(oldflp->fl4_src) ||
2483                     ipv4_is_lbcast(oldflp->fl4_src) ||
2484                     ipv4_is_zeronet(oldflp->fl4_src))
2485                         goto out;
2486
2487                 /* I removed check for oif == dev_out->oif here.
2488                    It was wrong for two reasons:
2489                    1. ip_dev_find(net, saddr) can return wrong iface, if saddr
2490                       is assigned to multiple interfaces.
2491                    2. Moreover, we are allowed to send packets with saddr
2492                       of another iface. --ANK
2493                  */
2494
2495                 if (oldflp->oif == 0
2496                     && (ipv4_is_multicast(oldflp->fl4_dst) ||
2497                         oldflp->fl4_dst == htonl(0xFFFFFFFF))) {
2498                         /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
2499                         dev_out = ip_dev_find(net, oldflp->fl4_src);
2500                         if (dev_out == NULL)
2501                                 goto out;
2502
2503                         /* Special hack: user can direct multicasts
2504                            and limited broadcast via necessary interface
2505                            without fiddling with IP_MULTICAST_IF or IP_PKTINFO.
2506                            This hack is not just for fun, it allows
2507                            vic,vat and friends to work.
2508                            They bind socket to loopback, set ttl to zero
2509                            and expect that it will work.
2510                            From the viewpoint of routing cache they are broken,
2511                            because we are not allowed to build multicast path
2512                            with loopback source addr (look, routing cache
2513                            cannot know, that ttl is zero, so that packet
2514                            will not leave this host and route is valid).
2515                            Luckily, this hack is good workaround.
2516                          */
2517
2518                         fl.oif = dev_out->ifindex;
2519                         goto make_route;
2520                 }
2521
2522                 if (!(oldflp->flags & FLOWI_FLAG_ANYSRC)) {
2523                         /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
2524                         dev_out = ip_dev_find(net, oldflp->fl4_src);
2525                         if (dev_out == NULL)
2526                                 goto out;
2527                         dev_put(dev_out);
2528                         dev_out = NULL;
2529                 }
2530         }
2531
2532
2533         if (oldflp->oif) {
2534                 dev_out = dev_get_by_index(net, oldflp->oif);
2535                 err = -ENODEV;
2536                 if (dev_out == NULL)
2537                         goto out;
2538
2539                 /* RACE: Check return value of inet_select_addr instead. */
2540                 if (__in_dev_get_rtnl(dev_out) == NULL) {
2541                         dev_put(dev_out);
2542                         goto out;       /* Wrong error code */
2543                 }
2544
2545                 if (ipv4_is_local_multicast(oldflp->fl4_dst) ||
2546                     oldflp->fl4_dst == htonl(0xFFFFFFFF)) {
2547                         if (!fl.fl4_src)
2548                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2549                                                               RT_SCOPE_LINK);
2550                         goto make_route;
2551                 }
2552                 if (!fl.fl4_src) {
2553                         if (ipv4_is_multicast(oldflp->fl4_dst))
2554                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2555                                                               fl.fl4_scope);
2556                         else if (!oldflp->fl4_dst)
2557                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2558                                                               RT_SCOPE_HOST);
2559                 }
2560         }
2561
2562         if (!fl.fl4_dst) {
2563                 fl.fl4_dst = fl.fl4_src;
2564                 if (!fl.fl4_dst)
2565                         fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
2566                 if (dev_out)
2567                         dev_put(dev_out);
2568                 dev_out = net->loopback_dev;
2569                 dev_hold(dev_out);
2570                 fl.oif = net->loopback_dev->ifindex;
2571                 res.type = RTN_LOCAL;
2572                 flags |= RTCF_LOCAL;
2573                 goto make_route;
2574         }
2575
2576         if (fib_lookup(net, &fl, &res)) {
2577                 res.fi = NULL;
2578                 if (oldflp->oif) {
2579                         /* Apparently, routing tables are wrong. Assume,
2580                            that the destination is on link.
2581
2582                            WHY? DW.
2583                            Because we are allowed to send to iface
2584                            even if it has NO routes and NO assigned
2585                            addresses. When oif is specified, routing
2586                            tables are looked up with only one purpose:
2587                            to catch if destination is gatewayed, rather than
2588                            direct. Moreover, if MSG_DONTROUTE is set,
2589                            we send packet, ignoring both routing tables
2590                            and ifaddr state. --ANK
2591
2592
2593                            We could make it even if oif is unknown,
2594                            likely IPv6, but we do not.
2595                          */
2596
2597                         if (fl.fl4_src == 0)
2598                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2599                                                               RT_SCOPE_LINK);
2600                         res.type = RTN_UNICAST;
2601                         goto make_route;
2602                 }
2603                 if (dev_out)
2604                         dev_put(dev_out);
2605                 err = -ENETUNREACH;
2606                 goto out;
2607         }
2608         free_res = 1;
2609
2610         if (res.type == RTN_LOCAL) {
2611                 if (!fl.fl4_src)
2612                         fl.fl4_src = fl.fl4_dst;
2613                 if (dev_out)
2614                         dev_put(dev_out);
2615                 dev_out = net->loopback_dev;
2616                 dev_hold(dev_out);
2617                 fl.oif = dev_out->ifindex;
2618                 if (res.fi)
2619                         fib_info_put(res.fi);
2620                 res.fi = NULL;
2621                 flags |= RTCF_LOCAL;
2622                 goto make_route;
2623         }
2624
2625 #ifdef CONFIG_IP_ROUTE_MULTIPATH
2626         if (res.fi->fib_nhs > 1 && fl.oif == 0)
2627                 fib_select_multipath(&fl, &res);
2628         else
2629 #endif
2630         if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
2631                 fib_select_default(net, &fl, &res);
2632
2633         if (!fl.fl4_src)
2634                 fl.fl4_src = FIB_RES_PREFSRC(res);
2635
2636         if (dev_out)
2637                 dev_put(dev_out);
2638         dev_out = FIB_RES_DEV(res);
2639         dev_hold(dev_out);
2640         fl.oif = dev_out->ifindex;
2641
2642
2643 make_route:
2644         err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
2645
2646
2647         if (free_res)
2648                 fib_res_put(&res);
2649         if (dev_out)
2650                 dev_put(dev_out);
2651 out:    return err;
2652 }
2653
2654 int __ip_route_output_key(struct net *net, struct rtable **rp,
2655                           const struct flowi *flp)
2656 {
2657         unsigned hash;
2658         struct rtable *rth;
2659
2660         if (!rt_caching(net))
2661                 goto slow_output;
2662
2663         hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif, rt_genid(net));
2664
2665         rcu_read_lock_bh();
2666         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2667                 rth = rcu_dereference(rth->u.dst.rt_next)) {
2668                 if (rth->fl.fl4_dst == flp->fl4_dst &&
2669                     rth->fl.fl4_src == flp->fl4_src &&
2670                     rth->fl.iif == 0 &&
2671                     rth->fl.oif == flp->oif &&
2672                     rth->fl.mark == flp->mark &&
2673                     !((rth->fl.fl4_tos ^ flp->fl4_tos) &
2674                             (IPTOS_RT_MASK | RTO_ONLINK)) &&
2675                     net_eq(dev_net(rth->u.dst.dev), net) &&
2676                     !rt_is_expired(rth)) {
2677                         dst_use(&rth->u.dst, jiffies);
2678                         RT_CACHE_STAT_INC(out_hit);
2679                         rcu_read_unlock_bh();
2680                         *rp = rth;
2681                         return 0;
2682                 }
2683                 RT_CACHE_STAT_INC(out_hlist_search);
2684         }
2685         rcu_read_unlock_bh();
2686
2687 slow_output:
2688         return ip_route_output_slow(net, rp, flp);
2689 }
2690
2691 EXPORT_SYMBOL_GPL(__ip_route_output_key);
2692
2693 static void ipv4_rt_blackhole_update_pmtu(struct dst_entry *dst, u32 mtu)
2694 {
2695 }
2696
2697 static struct dst_ops ipv4_dst_blackhole_ops = {
2698         .family                 =       AF_INET,
2699         .protocol               =       cpu_to_be16(ETH_P_IP),
2700         .destroy                =       ipv4_dst_destroy,
2701         .check                  =       ipv4_dst_check,
2702         .update_pmtu            =       ipv4_rt_blackhole_update_pmtu,
2703         .entries                =       ATOMIC_INIT(0),
2704 };
2705
2706
2707 static int ipv4_dst_blackhole(struct net *net, struct rtable **rp, struct flowi *flp)
2708 {
2709         struct rtable *ort = *rp;
2710         struct rtable *rt = (struct rtable *)
2711                 dst_alloc(&ipv4_dst_blackhole_ops);
2712
2713         if (rt) {
2714                 struct dst_entry *new = &rt->u.dst;
2715
2716                 atomic_set(&new->__refcnt, 1);
2717                 new->__use = 1;
2718                 new->input = dst_discard;
2719                 new->output = dst_discard;
2720                 memcpy(new->metrics, ort->u.dst.metrics, RTAX_MAX*sizeof(u32));
2721
2722                 new->dev = ort->u.dst.dev;
2723                 if (new->dev)
2724                         dev_hold(new->dev);
2725
2726                 rt->fl = ort->fl;
2727
2728                 rt->idev = ort->idev;
2729                 if (rt->idev)
2730                         in_dev_hold(rt->idev);
2731                 rt->rt_genid = rt_genid(net);
2732                 rt->rt_flags = ort->rt_flags;
2733                 rt->rt_type = ort->rt_type;
2734                 rt->rt_dst = ort->rt_dst;
2735                 rt->rt_src = ort->rt_src;
2736                 rt->rt_iif = ort->rt_iif;
2737                 rt->rt_gateway = ort->rt_gateway;
2738                 rt->rt_spec_dst = ort->rt_spec_dst;
2739                 rt->peer = ort->peer;
2740                 if (rt->peer)
2741                         atomic_inc(&rt->peer->refcnt);
2742
2743                 dst_free(new);
2744         }
2745
2746         dst_release(&(*rp)->u.dst);
2747         *rp = rt;
2748         return (rt ? 0 : -ENOMEM);
2749 }
2750
2751 int ip_route_output_flow(struct net *net, struct rtable **rp, struct flowi *flp,
2752                          struct sock *sk, int flags)
2753 {
2754         int err;
2755
2756         if ((err = __ip_route_output_key(net, rp, flp)) != 0)
2757                 return err;
2758
2759         if (flp->proto) {
2760                 if (!flp->fl4_src)
2761                         flp->fl4_src = (*rp)->rt_src;
2762                 if (!flp->fl4_dst)
2763                         flp->fl4_dst = (*rp)->rt_dst;
2764                 err = __xfrm_lookup(net, (struct dst_entry **)rp, flp, sk,
2765                                     flags ? XFRM_LOOKUP_WAIT : 0);
2766                 if (err == -EREMOTE)
2767                         err = ipv4_dst_blackhole(net, rp, flp);
2768
2769                 return err;
2770         }
2771
2772         return 0;
2773 }
2774
2775 EXPORT_SYMBOL_GPL(ip_route_output_flow);
2776
2777 int ip_route_output_key(struct net *net, struct rtable **rp, struct flowi *flp)
2778 {
2779         return ip_route_output_flow(net, rp, flp, NULL, 0);
2780 }
2781
2782 static int rt_fill_info(struct net *net,
2783                         struct sk_buff *skb, u32 pid, u32 seq, int event,
2784                         int nowait, unsigned int flags)
2785 {
2786         struct rtable *rt = skb->rtable;
2787         struct rtmsg *r;
2788         struct nlmsghdr *nlh;
2789         long expires;
2790         u32 id = 0, ts = 0, tsage = 0, error;
2791
2792         nlh = nlmsg_put(skb, pid, seq, event, sizeof(*r), flags);
2793         if (nlh == NULL)
2794                 return -EMSGSIZE;
2795
2796         r = nlmsg_data(nlh);
2797         r->rtm_family    = AF_INET;
2798         r->rtm_dst_len  = 32;
2799         r->rtm_src_len  = 0;
2800         r->rtm_tos      = rt->fl.fl4_tos;
2801         r->rtm_table    = RT_TABLE_MAIN;
2802         NLA_PUT_U32(skb, RTA_TABLE, RT_TABLE_MAIN);
2803         r->rtm_type     = rt->rt_type;
2804         r->rtm_scope    = RT_SCOPE_UNIVERSE;
2805         r->rtm_protocol = RTPROT_UNSPEC;
2806         r->rtm_flags    = (rt->rt_flags & ~0xFFFF) | RTM_F_CLONED;
2807         if (rt->rt_flags & RTCF_NOTIFY)
2808                 r->rtm_flags |= RTM_F_NOTIFY;
2809
2810         NLA_PUT_BE32(skb, RTA_DST, rt->rt_dst);
2811
2812         if (rt->fl.fl4_src) {
2813                 r->rtm_src_len = 32;
2814                 NLA_PUT_BE32(skb, RTA_SRC, rt->fl.fl4_src);
2815         }
2816         if (rt->u.dst.dev)
2817                 NLA_PUT_U32(skb, RTA_OIF, rt->u.dst.dev->ifindex);
2818 #ifdef CONFIG_NET_CLS_ROUTE
2819         if (rt->u.dst.tclassid)
2820                 NLA_PUT_U32(skb, RTA_FLOW, rt->u.dst.tclassid);
2821 #endif
2822         if (rt->fl.iif)
2823                 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_spec_dst);
2824         else if (rt->rt_src != rt->fl.fl4_src)
2825                 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_src);
2826
2827         if (rt->rt_dst != rt->rt_gateway)
2828                 NLA_PUT_BE32(skb, RTA_GATEWAY, rt->rt_gateway);
2829
2830         if (rtnetlink_put_metrics(skb, rt->u.dst.metrics) < 0)
2831                 goto nla_put_failure;
2832
2833         error = rt->u.dst.error;
2834         expires = rt->u.dst.expires ? rt->u.dst.expires - jiffies : 0;
2835         if (rt->peer) {
2836                 id = rt->peer->ip_id_count;
2837                 if (rt->peer->tcp_ts_stamp) {
2838                         ts = rt->peer->tcp_ts;
2839                         tsage = get_seconds() - rt->peer->tcp_ts_stamp;
2840                 }
2841         }
2842
2843         if (rt->fl.iif) {
2844 #ifdef CONFIG_IP_MROUTE
2845                 __be32 dst = rt->rt_dst;
2846
2847                 if (ipv4_is_multicast(dst) && !ipv4_is_local_multicast(dst) &&
2848                     IPV4_DEVCONF_ALL(net, MC_FORWARDING)) {
2849                         int err = ipmr_get_route(net, skb, r, nowait);
2850                         if (err <= 0) {
2851                                 if (!nowait) {
2852                                         if (err == 0)
2853                                                 return 0;
2854                                         goto nla_put_failure;
2855                                 } else {
2856                                         if (err == -EMSGSIZE)
2857                                                 goto nla_put_failure;
2858                                         error = err;
2859                                 }
2860                         }
2861                 } else
2862 #endif
2863                         NLA_PUT_U32(skb, RTA_IIF, rt->fl.iif);
2864         }
2865
2866         if (rtnl_put_cacheinfo(skb, &rt->u.dst, id, ts, tsage,
2867                                expires, error) < 0)
2868                 goto nla_put_failure;
2869
2870         return nlmsg_end(skb, nlh);
2871
2872 nla_put_failure:
2873         nlmsg_cancel(skb, nlh);
2874         return -EMSGSIZE;
2875 }
2876
2877 static int inet_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg)
2878 {
2879         struct net *net = sock_net(in_skb->sk);
2880         struct rtmsg *rtm;
2881         struct nlattr *tb[RTA_MAX+1];
2882         struct rtable *rt = NULL;
2883         __be32 dst = 0;
2884         __be32 src = 0;
2885         u32 iif;
2886         int err;
2887         struct sk_buff *skb;
2888
2889         err = nlmsg_parse(nlh, sizeof(*rtm), tb, RTA_MAX, rtm_ipv4_policy);
2890         if (err < 0)
2891                 goto errout;
2892
2893         rtm = nlmsg_data(nlh);
2894
2895         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
2896         if (skb == NULL) {
2897                 err = -ENOBUFS;
2898                 goto errout;
2899         }
2900
2901         /* Reserve room for dummy headers, this skb can pass
2902            through good chunk of routing engine.
2903          */
2904         skb_reset_mac_header(skb);
2905         skb_reset_network_header(skb);
2906
2907         /* Bugfix: need to give ip_route_input enough of an IP header to not gag. */
2908         ip_hdr(skb)->protocol = IPPROTO_ICMP;
2909         skb_reserve(skb, MAX_HEADER + sizeof(struct iphdr));
2910
2911         src = tb[RTA_SRC] ? nla_get_be32(tb[RTA_SRC]) : 0;
2912         dst = tb[RTA_DST] ? nla_get_be32(tb[RTA_DST]) : 0;
2913         iif = tb[RTA_IIF] ? nla_get_u32(tb[RTA_IIF]) : 0;
2914
2915         if (iif) {
2916                 struct net_device *dev;
2917
2918                 dev = __dev_get_by_index(net, iif);
2919                 if (dev == NULL) {
2920                         err = -ENODEV;
2921                         goto errout_free;
2922                 }
2923
2924                 skb->protocol   = htons(ETH_P_IP);
2925                 skb->dev        = dev;
2926                 local_bh_disable();
2927                 err = ip_route_input(skb, dst, src, rtm->rtm_tos, dev);
2928                 local_bh_enable();
2929
2930                 rt = skb->rtable;
2931                 if (err == 0 && rt->u.dst.error)
2932                         err = -rt->u.dst.error;
2933         } else {
2934                 struct flowi fl = {
2935                         .nl_u = {
2936                                 .ip4_u = {
2937                                         .daddr = dst,
2938                                         .saddr = src,
2939                                         .tos = rtm->rtm_tos,
2940                                 },
2941                         },
2942                         .oif = tb[RTA_OIF] ? nla_get_u32(tb[RTA_OIF]) : 0,
2943                 };
2944                 err = ip_route_output_key(net, &rt, &fl);
2945         }
2946
2947         if (err)
2948                 goto errout_free;
2949
2950         skb->rtable = rt;
2951         if (rtm->rtm_flags & RTM_F_NOTIFY)
2952                 rt->rt_flags |= RTCF_NOTIFY;
2953
2954         err = rt_fill_info(net, skb, NETLINK_CB(in_skb).pid, nlh->nlmsg_seq,
2955                            RTM_NEWROUTE, 0, 0);
2956         if (err <= 0)
2957                 goto errout_free;
2958
2959         err = rtnl_unicast(skb, net, NETLINK_CB(in_skb).pid);
2960 errout:
2961         return err;
2962
2963 errout_free:
2964         kfree_skb(skb);
2965         goto errout;
2966 }
2967
2968 int ip_rt_dump(struct sk_buff *skb,  struct netlink_callback *cb)
2969 {
2970         struct rtable *rt;
2971         int h, s_h;
2972         int idx, s_idx;
2973         struct net *net;
2974
2975         net = sock_net(skb->sk);
2976
2977         s_h = cb->args[0];
2978         if (s_h < 0)
2979                 s_h = 0;
2980         s_idx = idx = cb->args[1];
2981         for (h = s_h; h <= rt_hash_mask; h++, s_idx = 0) {
2982                 if (!rt_hash_table[h].chain)
2983                         continue;
2984                 rcu_read_lock_bh();
2985                 for (rt = rcu_dereference(rt_hash_table[h].chain), idx = 0; rt;
2986                      rt = rcu_dereference(rt->u.dst.rt_next), idx++) {
2987                         if (!net_eq(dev_net(rt->u.dst.dev), net) || idx < s_idx)
2988                                 continue;
2989                         if (rt_is_expired(rt))
2990                                 continue;
2991                         skb->dst = dst_clone(&rt->u.dst);
2992                         if (rt_fill_info(net, skb, NETLINK_CB(cb->skb).pid,
2993                                          cb->nlh->nlmsg_seq, RTM_NEWROUTE,
2994                                          1, NLM_F_MULTI) <= 0) {
2995                                 dst_release(xchg(&skb->dst, NULL));
2996                                 rcu_read_unlock_bh();
2997                                 goto done;
2998                         }
2999                         dst_release(xchg(&skb->dst, NULL));
3000                 }
3001                 rcu_read_unlock_bh();
3002         }
3003
3004 done:
3005         cb->args[0] = h;
3006         cb->args[1] = idx;
3007         return skb->len;
3008 }
3009
3010 void ip_rt_multicast_event(struct in_device *in_dev)
3011 {
3012         rt_cache_flush(dev_net(in_dev->dev), 0);
3013 }
3014
3015 #ifdef CONFIG_SYSCTL
3016 static int ipv4_sysctl_rtcache_flush(ctl_table *__ctl, int write,
3017                                         struct file *filp, void __user *buffer,
3018                                         size_t *lenp, loff_t *ppos)
3019 {
3020         if (write) {
3021                 int flush_delay;
3022                 ctl_table ctl;
3023                 struct net *net;
3024
3025                 memcpy(&ctl, __ctl, sizeof(ctl));
3026                 ctl.data = &flush_delay;
3027                 proc_dointvec(&ctl, write, filp, buffer, lenp, ppos);
3028
3029                 net = (struct net *)__ctl->extra1;
3030                 rt_cache_flush(net, flush_delay);
3031                 return 0;
3032         }
3033
3034         return -EINVAL;
3035 }
3036
3037 static int ipv4_sysctl_rtcache_flush_strategy(ctl_table *table,
3038                                                 void __user *oldval,
3039                                                 size_t __user *oldlenp,
3040                                                 void __user *newval,
3041                                                 size_t newlen)
3042 {
3043         int delay;
3044         struct net *net;
3045         if (newlen != sizeof(int))
3046                 return -EINVAL;
3047         if (get_user(delay, (int __user *)newval))
3048                 return -EFAULT;
3049         net = (struct net *)table->extra1;
3050         rt_cache_flush(net, delay);
3051         return 0;
3052 }
3053
3054 static void rt_secret_reschedule(int old)
3055 {
3056         struct net *net;
3057         int new = ip_rt_secret_interval;
3058         int diff = new - old;
3059
3060         if (!diff)
3061                 return;
3062
3063         rtnl_lock();
3064         for_each_net(net) {
3065                 int deleted = del_timer_sync(&net->ipv4.rt_secret_timer);
3066
3067                 if (!new)
3068                         continue;
3069
3070                 if (deleted) {
3071                         long time = net->ipv4.rt_secret_timer.expires - jiffies;
3072
3073                         if (time <= 0 || (time += diff) <= 0)
3074                                 time = 0;
3075
3076                         net->ipv4.rt_secret_timer.expires = time;
3077                 } else
3078                         net->ipv4.rt_secret_timer.expires = new;
3079
3080                 net->ipv4.rt_secret_timer.expires += jiffies;
3081                 add_timer(&net->ipv4.rt_secret_timer);
3082         }
3083         rtnl_unlock();
3084 }
3085
3086 static int ipv4_sysctl_rt_secret_interval(ctl_table *ctl, int write,
3087                                           struct file *filp,
3088                                           void __user *buffer, size_t *lenp,
3089                                           loff_t *ppos)
3090 {
3091         int old = ip_rt_secret_interval;
3092         int ret = proc_dointvec_jiffies(ctl, write, filp, buffer, lenp, ppos);
3093
3094         rt_secret_reschedule(old);
3095
3096         return ret;
3097 }
3098
3099 static int ipv4_sysctl_rt_secret_interval_strategy(ctl_table *table,
3100                                                    void __user *oldval,
3101                                                    size_t __user *oldlenp,
3102                                                    void __user *newval,
3103                                                    size_t newlen)
3104 {
3105         int old = ip_rt_secret_interval;
3106         int ret = sysctl_jiffies(table, oldval, oldlenp, newval, newlen);
3107
3108         rt_secret_reschedule(old);
3109
3110         return ret;
3111 }
3112
3113 static ctl_table ipv4_route_table[] = {
3114         {
3115                 .ctl_name       = NET_IPV4_ROUTE_GC_THRESH,
3116                 .procname       = "gc_thresh",
3117                 .data           = &ipv4_dst_ops.gc_thresh,
3118                 .maxlen         = sizeof(int),
3119                 .mode           = 0644,
3120                 .proc_handler   = proc_dointvec,
3121         },
3122         {
3123                 .ctl_name       = NET_IPV4_ROUTE_MAX_SIZE,
3124                 .procname       = "max_size",
3125                 .data           = &ip_rt_max_size,
3126                 .maxlen         = sizeof(int),
3127                 .mode           = 0644,
3128                 .proc_handler   = proc_dointvec,
3129         },
3130         {
3131                 /*  Deprecated. Use gc_min_interval_ms */
3132
3133                 .ctl_name       = NET_IPV4_ROUTE_GC_MIN_INTERVAL,
3134                 .procname       = "gc_min_interval",
3135                 .data           = &ip_rt_gc_min_interval,
3136                 .maxlen         = sizeof(int),
3137                 .mode           = 0644,
3138                 .proc_handler   = proc_dointvec_jiffies,
3139                 .strategy       = sysctl_jiffies,
3140         },
3141         {
3142                 .ctl_name       = NET_IPV4_ROUTE_GC_MIN_INTERVAL_MS,
3143                 .procname       = "gc_min_interval_ms",
3144                 .data           = &ip_rt_gc_min_interval,
3145                 .maxlen         = sizeof(int),
3146                 .mode           = 0644,
3147                 .proc_handler   = proc_dointvec_ms_jiffies,
3148                 .strategy       = sysctl_ms_jiffies,
3149         },
3150         {
3151                 .ctl_name       = NET_IPV4_ROUTE_GC_TIMEOUT,
3152                 .procname       = "gc_timeout",
3153                 .data           = &ip_rt_gc_timeout,
3154                 .maxlen         = sizeof(int),
3155                 .mode           = 0644,
3156                 .proc_handler   = proc_dointvec_jiffies,
3157                 .strategy       = sysctl_jiffies,
3158         },
3159         {
3160                 .ctl_name       = NET_IPV4_ROUTE_GC_INTERVAL,
3161                 .procname       = "gc_interval",
3162                 .data           = &ip_rt_gc_interval,
3163                 .maxlen         = sizeof(int),
3164                 .mode           = 0644,
3165                 .proc_handler   = proc_dointvec_jiffies,
3166                 .strategy       = sysctl_jiffies,
3167         },
3168         {
3169                 .ctl_name       = NET_IPV4_ROUTE_REDIRECT_LOAD,
3170                 .procname       = "redirect_load",
3171                 .data           = &ip_rt_redirect_load,
3172                 .maxlen         = sizeof(int),
3173                 .mode           = 0644,
3174                 .proc_handler   = proc_dointvec,
3175         },
3176         {
3177                 .ctl_name       = NET_IPV4_ROUTE_REDIRECT_NUMBER,
3178                 .procname       = "redirect_number",
3179                 .data           = &ip_rt_redirect_number,
3180                 .maxlen         = sizeof(int),
3181                 .mode           = 0644,
3182                 .proc_handler   = proc_dointvec,
3183         },
3184         {
3185                 .ctl_name       = NET_IPV4_ROUTE_REDIRECT_SILENCE,
3186                 .procname       = "redirect_silence",
3187                 .data           = &ip_rt_redirect_silence,
3188                 .maxlen         = sizeof(int),
3189                 .mode           = 0644,
3190                 .proc_handler   = proc_dointvec,
3191         },
3192         {
3193                 .ctl_name       = NET_IPV4_ROUTE_ERROR_COST,
3194                 .procname       = "error_cost",
3195                 .data           = &ip_rt_error_cost,
3196                 .maxlen         = sizeof(int),
3197                 .mode           = 0644,
3198                 .proc_handler   = proc_dointvec,
3199         },
3200         {
3201                 .ctl_name       = NET_IPV4_ROUTE_ERROR_BURST,
3202                 .procname       = "error_burst",
3203                 .data           = &ip_rt_error_burst,
3204                 .maxlen         = sizeof(int),
3205                 .mode           = 0644,
3206                 .proc_handler   = proc_dointvec,
3207         },
3208         {
3209                 .ctl_name       = NET_IPV4_ROUTE_GC_ELASTICITY,
3210                 .procname       = "gc_elasticity",
3211                 .data           = &ip_rt_gc_elasticity,
3212                 .maxlen         = sizeof(int),
3213                 .mode           = 0644,
3214                 .proc_handler   = proc_dointvec,
3215         },
3216         {
3217                 .ctl_name       = NET_IPV4_ROUTE_MTU_EXPIRES,
3218                 .procname       = "mtu_expires",
3219                 .data           = &ip_rt_mtu_expires,
3220                 .maxlen         = sizeof(int),
3221                 .mode           = 0644,
3222                 .proc_handler   = proc_dointvec_jiffies,
3223                 .strategy       = sysctl_jiffies,
3224         },
3225         {
3226                 .ctl_name       = NET_IPV4_ROUTE_MIN_PMTU,
3227                 .procname       = "min_pmtu",
3228                 .data           = &ip_rt_min_pmtu,
3229                 .maxlen         = sizeof(int),
3230                 .mode           = 0644,
3231                 .proc_handler   = proc_dointvec,
3232         },
3233         {
3234                 .ctl_name       = NET_IPV4_ROUTE_MIN_ADVMSS,
3235                 .procname       = "min_adv_mss",
3236                 .data           = &ip_rt_min_advmss,
3237                 .maxlen         = sizeof(int),
3238                 .mode           = 0644,
3239                 .proc_handler   = proc_dointvec,
3240         },
3241         {
3242                 .ctl_name       = NET_IPV4_ROUTE_SECRET_INTERVAL,
3243                 .procname       = "secret_interval",
3244                 .data           = &ip_rt_secret_interval,
3245                 .maxlen         = sizeof(int),
3246                 .mode           = 0644,
3247                 .proc_handler   = ipv4_sysctl_rt_secret_interval,
3248                 .strategy       = ipv4_sysctl_rt_secret_interval_strategy,
3249         },
3250         { .ctl_name = 0 }
3251 };
3252
3253 static struct ctl_table empty[1];
3254
3255 static struct ctl_table ipv4_skeleton[] =
3256 {
3257         { .procname = "route", .ctl_name = NET_IPV4_ROUTE,
3258           .mode = 0555, .child = ipv4_route_table},
3259         { .procname = "neigh", .ctl_name = NET_IPV4_NEIGH,
3260           .mode = 0555, .child = empty},
3261         { }
3262 };
3263
3264 static __net_initdata struct ctl_path ipv4_path[] = {
3265         { .procname = "net", .ctl_name = CTL_NET, },
3266         { .procname = "ipv4", .ctl_name = NET_IPV4, },
3267         { },
3268 };
3269
3270 static struct ctl_table ipv4_route_flush_table[] = {
3271         {
3272                 .ctl_name       = NET_IPV4_ROUTE_FLUSH,
3273                 .procname       = "flush",
3274                 .maxlen         = sizeof(int),
3275                 .mode           = 0200,
3276                 .proc_handler   = ipv4_sysctl_rtcache_flush,
3277                 .strategy       = ipv4_sysctl_rtcache_flush_strategy,
3278         },
3279         { .ctl_name = 0 },
3280 };
3281
3282 static __net_initdata struct ctl_path ipv4_route_path[] = {
3283         { .procname = "net", .ctl_name = CTL_NET, },
3284         { .procname = "ipv4", .ctl_name = NET_IPV4, },
3285         { .procname = "route", .ctl_name = NET_IPV4_ROUTE, },
3286         { },
3287 };
3288
3289 static __net_init int sysctl_route_net_init(struct net *net)
3290 {
3291         struct ctl_table *tbl;
3292
3293         tbl = ipv4_route_flush_table;
3294         if (net != &init_net) {
3295                 tbl = kmemdup(tbl, sizeof(ipv4_route_flush_table), GFP_KERNEL);
3296                 if (tbl == NULL)
3297                         goto err_dup;
3298         }
3299         tbl[0].extra1 = net;
3300
3301         net->ipv4.route_hdr =
3302                 register_net_sysctl_table(net, ipv4_route_path, tbl);
3303         if (net->ipv4.route_hdr == NULL)
3304                 goto err_reg;
3305         return 0;
3306
3307 err_reg:
3308         if (tbl != ipv4_route_flush_table)
3309                 kfree(tbl);
3310 err_dup:
3311         return -ENOMEM;
3312 }
3313
3314 static __net_exit void sysctl_route_net_exit(struct net *net)
3315 {
3316         struct ctl_table *tbl;
3317
3318         tbl = net->ipv4.route_hdr->ctl_table_arg;
3319         unregister_net_sysctl_table(net->ipv4.route_hdr);
3320         BUG_ON(tbl == ipv4_route_flush_table);
3321         kfree(tbl);
3322 }
3323
3324 static __net_initdata struct pernet_operations sysctl_route_ops = {
3325         .init = sysctl_route_net_init,
3326         .exit = sysctl_route_net_exit,
3327 };
3328 #endif
3329
3330
3331 static __net_init int rt_secret_timer_init(struct net *net)
3332 {
3333         atomic_set(&net->ipv4.rt_genid,
3334                         (int) ((num_physpages ^ (num_physpages>>8)) ^
3335                         (jiffies ^ (jiffies >> 7))));
3336
3337         net->ipv4.rt_secret_timer.function = rt_secret_rebuild;
3338         net->ipv4.rt_secret_timer.data = (unsigned long)net;
3339         init_timer_deferrable(&net->ipv4.rt_secret_timer);
3340
3341         if (ip_rt_secret_interval) {
3342                 net->ipv4.rt_secret_timer.expires =
3343                         jiffies + net_random() % ip_rt_secret_interval +
3344                         ip_rt_secret_interval;
3345                 add_timer(&net->ipv4.rt_secret_timer);
3346         }
3347         return 0;
3348 }
3349
3350 static __net_exit void rt_secret_timer_exit(struct net *net)
3351 {
3352         del_timer_sync(&net->ipv4.rt_secret_timer);
3353 }
3354
3355 static __net_initdata struct pernet_operations rt_secret_timer_ops = {
3356         .init = rt_secret_timer_init,
3357         .exit = rt_secret_timer_exit,
3358 };
3359
3360
3361 #ifdef CONFIG_NET_CLS_ROUTE
3362 struct ip_rt_acct *ip_rt_acct __read_mostly;
3363 #endif /* CONFIG_NET_CLS_ROUTE */
3364
3365 static __initdata unsigned long rhash_entries;
3366 static int __init set_rhash_entries(char *str)
3367 {
3368         if (!str)
3369                 return 0;
3370         rhash_entries = simple_strtoul(str, &str, 0);
3371         return 1;
3372 }
3373 __setup("rhash_entries=", set_rhash_entries);
3374
3375 int __init ip_rt_init(void)
3376 {
3377         int rc = 0;
3378
3379 #ifdef CONFIG_NET_CLS_ROUTE
3380         ip_rt_acct = __alloc_percpu(256 * sizeof(struct ip_rt_acct), __alignof__(struct ip_rt_acct));
3381         if (!ip_rt_acct)
3382                 panic("IP: failed to allocate ip_rt_acct\n");
3383 #endif
3384
3385         ipv4_dst_ops.kmem_cachep =
3386                 kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
3387                                   SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
3388
3389         ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;
3390
3391         rt_hash_table = (struct rt_hash_bucket *)
3392                 alloc_large_system_hash("IP route cache",
3393                                         sizeof(struct rt_hash_bucket),
3394                                         rhash_entries,
3395                                         (num_physpages >= 128 * 1024) ?
3396                                         15 : 17,
3397                                         0,
3398                                         &rt_hash_log,
3399                                         &rt_hash_mask,
3400                                         0);
3401         memset(rt_hash_table, 0, (rt_hash_mask + 1) * sizeof(struct rt_hash_bucket));
3402         rt_hash_lock_init();
3403
3404         ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
3405         ip_rt_max_size = (rt_hash_mask + 1) * 16;
3406
3407         devinet_init();
3408         ip_fib_init();
3409
3410         /* All the timers, started at system startup tend
3411            to synchronize. Perturb it a bit.
3412          */
3413         schedule_delayed_work(&expires_work,
3414                 net_random() % ip_rt_gc_interval + ip_rt_gc_interval);
3415
3416         if (register_pernet_subsys(&rt_secret_timer_ops))
3417                 printk(KERN_ERR "Unable to setup rt_secret_timer\n");
3418
3419         if (ip_rt_proc_init())
3420                 printk(KERN_ERR "Unable to create route proc files\n");
3421 #ifdef CONFIG_XFRM
3422         xfrm_init();
3423         xfrm4_init();
3424 #endif
3425         rtnl_register(PF_INET, RTM_GETROUTE, inet_rtm_getroute, NULL);
3426
3427 #ifdef CONFIG_SYSCTL
3428         register_pernet_subsys(&sysctl_route_ops);
3429 #endif
3430         return rc;
3431 }
3432
3433 #ifdef CONFIG_SYSCTL
3434 /*
3435  * We really need to sanitize the damn ipv4 init order, then all
3436  * this nonsense will go away.
3437  */
3438 void __init ip_static_sysctl_init(void)
3439 {
3440         register_sysctl_paths(ipv4_path, ipv4_skeleton);
3441 }
3442 #endif
3443
3444 EXPORT_SYMBOL(__ip_select_ident);
3445 EXPORT_SYMBOL(ip_route_input);
3446 EXPORT_SYMBOL(ip_route_output_key);