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