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