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