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