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