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