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