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