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                                 rt->u.dst.__use         = 1;
1390                                 atomic_set(&rt->u.dst.__refcnt, 1);
1391                                 rt->u.dst.child         = NULL;
1392                                 if (rt->u.dst.dev)
1393                                         dev_hold(rt->u.dst.dev);
1394                                 if (rt->idev)
1395                                         in_dev_hold(rt->idev);
1396                                 rt->u.dst.obsolete      = 0;
1397                                 rt->u.dst.lastuse       = jiffies;
1398                                 rt->u.dst.path          = &rt->u.dst;
1399                                 rt->u.dst.neighbour     = NULL;
1400                                 rt->u.dst.hh            = NULL;
1401 #ifdef CONFIG_XFRM
1402                                 rt->u.dst.xfrm          = NULL;
1403 #endif
1404                                 rt->rt_genid            = rt_genid(net);
1405                                 rt->rt_flags            |= RTCF_REDIRECTED;
1406
1407                                 /* Gateway is different ... */
1408                                 rt->rt_gateway          = new_gw;
1409
1410                                 /* Redirect received -> path was valid */
1411                                 dst_confirm(&rth->u.dst);
1412
1413                                 if (rt->peer)
1414                                         atomic_inc(&rt->peer->refcnt);
1415
1416                                 if (arp_bind_neighbour(&rt->u.dst) ||
1417                                     !(rt->u.dst.neighbour->nud_state &
1418                                             NUD_VALID)) {
1419                                         if (rt->u.dst.neighbour)
1420                                                 neigh_event_send(rt->u.dst.neighbour, NULL);
1421                                         ip_rt_put(rth);
1422                                         rt_drop(rt);
1423                                         goto do_next;
1424                                 }
1425
1426                                 netevent.old = &rth->u.dst;
1427                                 netevent.new = &rt->u.dst;
1428                                 call_netevent_notifiers(NETEVENT_REDIRECT,
1429                                                         &netevent);
1430
1431                                 rt_del(hash, rth);
1432                                 if (!rt_intern_hash(hash, rt, &rt))
1433                                         ip_rt_put(rt);
1434                                 goto do_next;
1435                         }
1436                         rcu_read_unlock();
1437                 do_next:
1438                         ;
1439                 }
1440         }
1441         in_dev_put(in_dev);
1442         return;
1443
1444 reject_redirect:
1445 #ifdef CONFIG_IP_ROUTE_VERBOSE
1446         if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
1447                 printk(KERN_INFO "Redirect from " NIPQUAD_FMT " on %s about "
1448                         NIPQUAD_FMT " ignored.\n"
1449                         "  Advised path = " NIPQUAD_FMT " -> " NIPQUAD_FMT "\n",
1450                        NIPQUAD(old_gw), dev->name, NIPQUAD(new_gw),
1451                        NIPQUAD(saddr), NIPQUAD(daddr));
1452 #endif
1453         in_dev_put(in_dev);
1454 }
1455
1456 static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst)
1457 {
1458         struct rtable *rt = (struct rtable *)dst;
1459         struct dst_entry *ret = dst;
1460
1461         if (rt) {
1462                 if (dst->obsolete) {
1463                         ip_rt_put(rt);
1464                         ret = NULL;
1465                 } else if ((rt->rt_flags & RTCF_REDIRECTED) ||
1466                            rt->u.dst.expires) {
1467                         unsigned hash = rt_hash(rt->fl.fl4_dst, rt->fl.fl4_src,
1468                                                 rt->fl.oif,
1469                                                 rt_genid(dev_net(dst->dev)));
1470 #if RT_CACHE_DEBUG >= 1
1471                         printk(KERN_DEBUG "ipv4_negative_advice: redirect to "
1472                                           NIPQUAD_FMT "/%02x dropped\n",
1473                                 NIPQUAD(rt->rt_dst), rt->fl.fl4_tos);
1474 #endif
1475                         rt_del(hash, rt);
1476                         ret = NULL;
1477                 }
1478         }
1479         return ret;
1480 }
1481
1482 /*
1483  * Algorithm:
1484  *      1. The first ip_rt_redirect_number redirects are sent
1485  *         with exponential backoff, then we stop sending them at all,
1486  *         assuming that the host ignores our redirects.
1487  *      2. If we did not see packets requiring redirects
1488  *         during ip_rt_redirect_silence, we assume that the host
1489  *         forgot redirected route and start to send redirects again.
1490  *
1491  * This algorithm is much cheaper and more intelligent than dumb load limiting
1492  * in icmp.c.
1493  *
1494  * NOTE. Do not forget to inhibit load limiting for redirects (redundant)
1495  * and "frag. need" (breaks PMTU discovery) in icmp.c.
1496  */
1497
1498 void ip_rt_send_redirect(struct sk_buff *skb)
1499 {
1500         struct rtable *rt = skb->rtable;
1501         struct in_device *in_dev = in_dev_get(rt->u.dst.dev);
1502
1503         if (!in_dev)
1504                 return;
1505
1506         if (!IN_DEV_TX_REDIRECTS(in_dev))
1507                 goto out;
1508
1509         /* No redirected packets during ip_rt_redirect_silence;
1510          * reset the algorithm.
1511          */
1512         if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence))
1513                 rt->u.dst.rate_tokens = 0;
1514
1515         /* Too many ignored redirects; do not send anything
1516          * set u.dst.rate_last to the last seen redirected packet.
1517          */
1518         if (rt->u.dst.rate_tokens >= ip_rt_redirect_number) {
1519                 rt->u.dst.rate_last = jiffies;
1520                 goto out;
1521         }
1522
1523         /* Check for load limit; set rate_last to the latest sent
1524          * redirect.
1525          */
1526         if (rt->u.dst.rate_tokens == 0 ||
1527             time_after(jiffies,
1528                        (rt->u.dst.rate_last +
1529                         (ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
1530                 icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
1531                 rt->u.dst.rate_last = jiffies;
1532                 ++rt->u.dst.rate_tokens;
1533 #ifdef CONFIG_IP_ROUTE_VERBOSE
1534                 if (IN_DEV_LOG_MARTIANS(in_dev) &&
1535                     rt->u.dst.rate_tokens == ip_rt_redirect_number &&
1536                     net_ratelimit())
1537                         printk(KERN_WARNING "host " NIPQUAD_FMT "/if%d ignores "
1538                                 "redirects for " NIPQUAD_FMT " to " NIPQUAD_FMT ".\n",
1539                                 NIPQUAD(rt->rt_src), rt->rt_iif,
1540                                 NIPQUAD(rt->rt_dst), NIPQUAD(rt->rt_gateway));
1541 #endif
1542         }
1543 out:
1544         in_dev_put(in_dev);
1545 }
1546
1547 static int ip_error(struct sk_buff *skb)
1548 {
1549         struct rtable *rt = skb->rtable;
1550         unsigned long now;
1551         int code;
1552
1553         switch (rt->u.dst.error) {
1554                 case EINVAL:
1555                 default:
1556                         goto out;
1557                 case EHOSTUNREACH:
1558                         code = ICMP_HOST_UNREACH;
1559                         break;
1560                 case ENETUNREACH:
1561                         code = ICMP_NET_UNREACH;
1562                         IP_INC_STATS_BH(dev_net(rt->u.dst.dev),
1563                                         IPSTATS_MIB_INNOROUTES);
1564                         break;
1565                 case EACCES:
1566                         code = ICMP_PKT_FILTERED;
1567                         break;
1568         }
1569
1570         now = jiffies;
1571         rt->u.dst.rate_tokens += now - rt->u.dst.rate_last;
1572         if (rt->u.dst.rate_tokens > ip_rt_error_burst)
1573                 rt->u.dst.rate_tokens = ip_rt_error_burst;
1574         rt->u.dst.rate_last = now;
1575         if (rt->u.dst.rate_tokens >= ip_rt_error_cost) {
1576                 rt->u.dst.rate_tokens -= ip_rt_error_cost;
1577                 icmp_send(skb, ICMP_DEST_UNREACH, code, 0);
1578         }
1579
1580 out:    kfree_skb(skb);
1581         return 0;
1582 }
1583
1584 /*
1585  *      The last two values are not from the RFC but
1586  *      are needed for AMPRnet AX.25 paths.
1587  */
1588
1589 static const unsigned short mtu_plateau[] =
1590 {32000, 17914, 8166, 4352, 2002, 1492, 576, 296, 216, 128 };
1591
1592 static inline unsigned short guess_mtu(unsigned short old_mtu)
1593 {
1594         int i;
1595
1596         for (i = 0; i < ARRAY_SIZE(mtu_plateau); i++)
1597                 if (old_mtu > mtu_plateau[i])
1598                         return mtu_plateau[i];
1599         return 68;
1600 }
1601
1602 unsigned short ip_rt_frag_needed(struct net *net, struct iphdr *iph,
1603                                  unsigned short new_mtu,
1604                                  struct net_device *dev)
1605 {
1606         int i, k;
1607         unsigned short old_mtu = ntohs(iph->tot_len);
1608         struct rtable *rth;
1609         int  ikeys[2] = { dev->ifindex, 0 };
1610         __be32  skeys[2] = { iph->saddr, 0, };
1611         __be32  daddr = iph->daddr;
1612         unsigned short est_mtu = 0;
1613
1614         if (ipv4_config.no_pmtu_disc)
1615                 return 0;
1616
1617         for (k = 0; k < 2; k++) {
1618                 for (i = 0; i < 2; i++) {
1619                         unsigned hash = rt_hash(daddr, skeys[i], ikeys[k],
1620                                                 rt_genid(net));
1621
1622                         rcu_read_lock();
1623                         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
1624                              rth = rcu_dereference(rth->u.dst.rt_next)) {
1625                                 unsigned short mtu = new_mtu;
1626
1627                                 if (rth->fl.fl4_dst != daddr ||
1628                                     rth->fl.fl4_src != skeys[i] ||
1629                                     rth->rt_dst != daddr ||
1630                                     rth->rt_src != iph->saddr ||
1631                                     rth->fl.oif != ikeys[k] ||
1632                                     rth->fl.iif != 0 ||
1633                                     dst_metric_locked(&rth->u.dst, RTAX_MTU) ||
1634                                     !net_eq(dev_net(rth->u.dst.dev), net) ||
1635                                     rt_is_expired(rth))
1636                                         continue;
1637
1638                                 if (new_mtu < 68 || new_mtu >= old_mtu) {
1639
1640                                         /* BSD 4.2 compatibility hack :-( */
1641                                         if (mtu == 0 &&
1642                                             old_mtu >= dst_mtu(&rth->u.dst) &&
1643                                             old_mtu >= 68 + (iph->ihl << 2))
1644                                                 old_mtu -= iph->ihl << 2;
1645
1646                                         mtu = guess_mtu(old_mtu);
1647                                 }
1648                                 if (mtu <= dst_mtu(&rth->u.dst)) {
1649                                         if (mtu < dst_mtu(&rth->u.dst)) {
1650                                                 dst_confirm(&rth->u.dst);
1651                                                 if (mtu < ip_rt_min_pmtu) {
1652                                                         mtu = ip_rt_min_pmtu;
1653                                                         rth->u.dst.metrics[RTAX_LOCK-1] |=
1654                                                                 (1 << RTAX_MTU);
1655                                                 }
1656                                                 rth->u.dst.metrics[RTAX_MTU-1] = mtu;
1657                                                 dst_set_expires(&rth->u.dst,
1658                                                         ip_rt_mtu_expires);
1659                                         }
1660                                         est_mtu = mtu;
1661                                 }
1662                         }
1663                         rcu_read_unlock();
1664                 }
1665         }
1666         return est_mtu ? : new_mtu;
1667 }
1668
1669 static void ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu)
1670 {
1671         if (dst_mtu(dst) > mtu && mtu >= 68 &&
1672             !(dst_metric_locked(dst, RTAX_MTU))) {
1673                 if (mtu < ip_rt_min_pmtu) {
1674                         mtu = ip_rt_min_pmtu;
1675                         dst->metrics[RTAX_LOCK-1] |= (1 << RTAX_MTU);
1676                 }
1677                 dst->metrics[RTAX_MTU-1] = mtu;
1678                 dst_set_expires(dst, ip_rt_mtu_expires);
1679                 call_netevent_notifiers(NETEVENT_PMTU_UPDATE, dst);
1680         }
1681 }
1682
1683 static struct dst_entry *ipv4_dst_check(struct dst_entry *dst, u32 cookie)
1684 {
1685         return NULL;
1686 }
1687
1688 static void ipv4_dst_destroy(struct dst_entry *dst)
1689 {
1690         struct rtable *rt = (struct rtable *) dst;
1691         struct inet_peer *peer = rt->peer;
1692         struct in_device *idev = rt->idev;
1693
1694         if (peer) {
1695                 rt->peer = NULL;
1696                 inet_putpeer(peer);
1697         }
1698
1699         if (idev) {
1700                 rt->idev = NULL;
1701                 in_dev_put(idev);
1702         }
1703 }
1704
1705 static void ipv4_dst_ifdown(struct dst_entry *dst, struct net_device *dev,
1706                             int how)
1707 {
1708         struct rtable *rt = (struct rtable *) dst;
1709         struct in_device *idev = rt->idev;
1710         if (dev != dev_net(dev)->loopback_dev && idev && idev->dev == dev) {
1711                 struct in_device *loopback_idev =
1712                         in_dev_get(dev_net(dev)->loopback_dev);
1713                 if (loopback_idev) {
1714                         rt->idev = loopback_idev;
1715                         in_dev_put(idev);
1716                 }
1717         }
1718 }
1719
1720 static void ipv4_link_failure(struct sk_buff *skb)
1721 {
1722         struct rtable *rt;
1723
1724         icmp_send(skb, ICMP_DEST_UNREACH, ICMP_HOST_UNREACH, 0);
1725
1726         rt = skb->rtable;
1727         if (rt)
1728                 dst_set_expires(&rt->u.dst, 0);
1729 }
1730
1731 static int ip_rt_bug(struct sk_buff *skb)
1732 {
1733         printk(KERN_DEBUG "ip_rt_bug: " NIPQUAD_FMT " -> " NIPQUAD_FMT ", %s\n",
1734                 NIPQUAD(ip_hdr(skb)->saddr), NIPQUAD(ip_hdr(skb)->daddr),
1735                 skb->dev ? skb->dev->name : "?");
1736         kfree_skb(skb);
1737         return 0;
1738 }
1739
1740 /*
1741    We do not cache source address of outgoing interface,
1742    because it is used only by IP RR, TS and SRR options,
1743    so that it out of fast path.
1744
1745    BTW remember: "addr" is allowed to be not aligned
1746    in IP options!
1747  */
1748
1749 void ip_rt_get_source(u8 *addr, struct rtable *rt)
1750 {
1751         __be32 src;
1752         struct fib_result res;
1753
1754         if (rt->fl.iif == 0)
1755                 src = rt->rt_src;
1756         else if (fib_lookup(dev_net(rt->u.dst.dev), &rt->fl, &res) == 0) {
1757                 src = FIB_RES_PREFSRC(res);
1758                 fib_res_put(&res);
1759         } else
1760                 src = inet_select_addr(rt->u.dst.dev, rt->rt_gateway,
1761                                         RT_SCOPE_UNIVERSE);
1762         memcpy(addr, &src, 4);
1763 }
1764
1765 #ifdef CONFIG_NET_CLS_ROUTE
1766 static void set_class_tag(struct rtable *rt, u32 tag)
1767 {
1768         if (!(rt->u.dst.tclassid & 0xFFFF))
1769                 rt->u.dst.tclassid |= tag & 0xFFFF;
1770         if (!(rt->u.dst.tclassid & 0xFFFF0000))
1771                 rt->u.dst.tclassid |= tag & 0xFFFF0000;
1772 }
1773 #endif
1774
1775 static void rt_set_nexthop(struct rtable *rt, struct fib_result *res, u32 itag)
1776 {
1777         struct fib_info *fi = res->fi;
1778
1779         if (fi) {
1780                 if (FIB_RES_GW(*res) &&
1781                     FIB_RES_NH(*res).nh_scope == RT_SCOPE_LINK)
1782                         rt->rt_gateway = FIB_RES_GW(*res);
1783                 memcpy(rt->u.dst.metrics, fi->fib_metrics,
1784                        sizeof(rt->u.dst.metrics));
1785                 if (fi->fib_mtu == 0) {
1786                         rt->u.dst.metrics[RTAX_MTU-1] = rt->u.dst.dev->mtu;
1787                         if (dst_metric_locked(&rt->u.dst, RTAX_MTU) &&
1788                             rt->rt_gateway != rt->rt_dst &&
1789                             rt->u.dst.dev->mtu > 576)
1790                                 rt->u.dst.metrics[RTAX_MTU-1] = 576;
1791                 }
1792 #ifdef CONFIG_NET_CLS_ROUTE
1793                 rt->u.dst.tclassid = FIB_RES_NH(*res).nh_tclassid;
1794 #endif
1795         } else
1796                 rt->u.dst.metrics[RTAX_MTU-1]= rt->u.dst.dev->mtu;
1797
1798         if (dst_metric(&rt->u.dst, RTAX_HOPLIMIT) == 0)
1799                 rt->u.dst.metrics[RTAX_HOPLIMIT-1] = sysctl_ip_default_ttl;
1800         if (dst_mtu(&rt->u.dst) > IP_MAX_MTU)
1801                 rt->u.dst.metrics[RTAX_MTU-1] = IP_MAX_MTU;
1802         if (dst_metric(&rt->u.dst, RTAX_ADVMSS) == 0)
1803                 rt->u.dst.metrics[RTAX_ADVMSS-1] = max_t(unsigned int, rt->u.dst.dev->mtu - 40,
1804                                        ip_rt_min_advmss);
1805         if (dst_metric(&rt->u.dst, RTAX_ADVMSS) > 65535 - 40)
1806                 rt->u.dst.metrics[RTAX_ADVMSS-1] = 65535 - 40;
1807
1808 #ifdef CONFIG_NET_CLS_ROUTE
1809 #ifdef CONFIG_IP_MULTIPLE_TABLES
1810         set_class_tag(rt, fib_rules_tclass(res));
1811 #endif
1812         set_class_tag(rt, itag);
1813 #endif
1814         rt->rt_type = res->type;
1815 }
1816
1817 static int ip_route_input_mc(struct sk_buff *skb, __be32 daddr, __be32 saddr,
1818                                 u8 tos, struct net_device *dev, int our)
1819 {
1820         unsigned hash;
1821         struct rtable *rth;
1822         __be32 spec_dst;
1823         struct in_device *in_dev = in_dev_get(dev);
1824         u32 itag = 0;
1825
1826         /* Primary sanity checks. */
1827
1828         if (in_dev == NULL)
1829                 return -EINVAL;
1830
1831         if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr) ||
1832             ipv4_is_loopback(saddr) || skb->protocol != htons(ETH_P_IP))
1833                 goto e_inval;
1834
1835         if (ipv4_is_zeronet(saddr)) {
1836                 if (!ipv4_is_local_multicast(daddr))
1837                         goto e_inval;
1838                 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
1839         } else if (fib_validate_source(saddr, 0, tos, 0,
1840                                         dev, &spec_dst, &itag) < 0)
1841                 goto e_inval;
1842
1843         rth = dst_alloc(&ipv4_dst_ops);
1844         if (!rth)
1845                 goto e_nobufs;
1846
1847         rth->u.dst.output= ip_rt_bug;
1848
1849         atomic_set(&rth->u.dst.__refcnt, 1);
1850         rth->u.dst.flags= DST_HOST;
1851         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1852                 rth->u.dst.flags |= DST_NOPOLICY;
1853         rth->fl.fl4_dst = daddr;
1854         rth->rt_dst     = daddr;
1855         rth->fl.fl4_tos = tos;
1856         rth->fl.mark    = skb->mark;
1857         rth->fl.fl4_src = saddr;
1858         rth->rt_src     = saddr;
1859 #ifdef CONFIG_NET_CLS_ROUTE
1860         rth->u.dst.tclassid = itag;
1861 #endif
1862         rth->rt_iif     =
1863         rth->fl.iif     = dev->ifindex;
1864         rth->u.dst.dev  = init_net.loopback_dev;
1865         dev_hold(rth->u.dst.dev);
1866         rth->idev       = in_dev_get(rth->u.dst.dev);
1867         rth->fl.oif     = 0;
1868         rth->rt_gateway = daddr;
1869         rth->rt_spec_dst= spec_dst;
1870         rth->rt_genid   = rt_genid(dev_net(dev));
1871         rth->rt_flags   = RTCF_MULTICAST;
1872         rth->rt_type    = RTN_MULTICAST;
1873         if (our) {
1874                 rth->u.dst.input= ip_local_deliver;
1875                 rth->rt_flags |= RTCF_LOCAL;
1876         }
1877
1878 #ifdef CONFIG_IP_MROUTE
1879         if (!ipv4_is_local_multicast(daddr) && IN_DEV_MFORWARD(in_dev))
1880                 rth->u.dst.input = ip_mr_input;
1881 #endif
1882         RT_CACHE_STAT_INC(in_slow_mc);
1883
1884         in_dev_put(in_dev);
1885         hash = rt_hash(daddr, saddr, dev->ifindex, rt_genid(dev_net(dev)));
1886         return rt_intern_hash(hash, rth, &skb->rtable);
1887
1888 e_nobufs:
1889         in_dev_put(in_dev);
1890         return -ENOBUFS;
1891
1892 e_inval:
1893         in_dev_put(in_dev);
1894         return -EINVAL;
1895 }
1896
1897
1898 static void ip_handle_martian_source(struct net_device *dev,
1899                                      struct in_device *in_dev,
1900                                      struct sk_buff *skb,
1901                                      __be32 daddr,
1902                                      __be32 saddr)
1903 {
1904         RT_CACHE_STAT_INC(in_martian_src);
1905 #ifdef CONFIG_IP_ROUTE_VERBOSE
1906         if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit()) {
1907                 /*
1908                  *      RFC1812 recommendation, if source is martian,
1909                  *      the only hint is MAC header.
1910                  */
1911                 printk(KERN_WARNING "martian source " NIPQUAD_FMT " from "
1912                         NIPQUAD_FMT", on dev %s\n",
1913                         NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
1914                 if (dev->hard_header_len && skb_mac_header_was_set(skb)) {
1915                         int i;
1916                         const unsigned char *p = skb_mac_header(skb);
1917                         printk(KERN_WARNING "ll header: ");
1918                         for (i = 0; i < dev->hard_header_len; i++, p++) {
1919                                 printk("%02x", *p);
1920                                 if (i < (dev->hard_header_len - 1))
1921                                         printk(":");
1922                         }
1923                         printk("\n");
1924                 }
1925         }
1926 #endif
1927 }
1928
1929 static int __mkroute_input(struct sk_buff *skb,
1930                            struct fib_result *res,
1931                            struct in_device *in_dev,
1932                            __be32 daddr, __be32 saddr, u32 tos,
1933                            struct rtable **result)
1934 {
1935
1936         struct rtable *rth;
1937         int err;
1938         struct in_device *out_dev;
1939         unsigned flags = 0;
1940         __be32 spec_dst;
1941         u32 itag;
1942
1943         /* get a working reference to the output device */
1944         out_dev = in_dev_get(FIB_RES_DEV(*res));
1945         if (out_dev == NULL) {
1946                 if (net_ratelimit())
1947                         printk(KERN_CRIT "Bug in ip_route_input" \
1948                                "_slow(). Please, report\n");
1949                 return -EINVAL;
1950         }
1951
1952
1953         err = fib_validate_source(saddr, daddr, tos, FIB_RES_OIF(*res),
1954                                   in_dev->dev, &spec_dst, &itag);
1955         if (err < 0) {
1956                 ip_handle_martian_source(in_dev->dev, in_dev, skb, daddr,
1957                                          saddr);
1958
1959                 err = -EINVAL;
1960                 goto cleanup;
1961         }
1962
1963         if (err)
1964                 flags |= RTCF_DIRECTSRC;
1965
1966         if (out_dev == in_dev && err &&
1967             (IN_DEV_SHARED_MEDIA(out_dev) ||
1968              inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
1969                 flags |= RTCF_DOREDIRECT;
1970
1971         if (skb->protocol != htons(ETH_P_IP)) {
1972                 /* Not IP (i.e. ARP). Do not create route, if it is
1973                  * invalid for proxy arp. DNAT routes are always valid.
1974                  */
1975                 if (out_dev == in_dev) {
1976                         err = -EINVAL;
1977                         goto cleanup;
1978                 }
1979         }
1980
1981
1982         rth = dst_alloc(&ipv4_dst_ops);
1983         if (!rth) {
1984                 err = -ENOBUFS;
1985                 goto cleanup;
1986         }
1987
1988         atomic_set(&rth->u.dst.__refcnt, 1);
1989         rth->u.dst.flags= DST_HOST;
1990         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
1991                 rth->u.dst.flags |= DST_NOPOLICY;
1992         if (IN_DEV_CONF_GET(out_dev, NOXFRM))
1993                 rth->u.dst.flags |= DST_NOXFRM;
1994         rth->fl.fl4_dst = daddr;
1995         rth->rt_dst     = daddr;
1996         rth->fl.fl4_tos = tos;
1997         rth->fl.mark    = skb->mark;
1998         rth->fl.fl4_src = saddr;
1999         rth->rt_src     = saddr;
2000         rth->rt_gateway = daddr;
2001         rth->rt_iif     =
2002                 rth->fl.iif     = in_dev->dev->ifindex;
2003         rth->u.dst.dev  = (out_dev)->dev;
2004         dev_hold(rth->u.dst.dev);
2005         rth->idev       = in_dev_get(rth->u.dst.dev);
2006         rth->fl.oif     = 0;
2007         rth->rt_spec_dst= spec_dst;
2008
2009         rth->u.dst.input = ip_forward;
2010         rth->u.dst.output = ip_output;
2011         rth->rt_genid = rt_genid(dev_net(rth->u.dst.dev));
2012
2013         rt_set_nexthop(rth, res, itag);
2014
2015         rth->rt_flags = flags;
2016
2017         *result = rth;
2018         err = 0;
2019  cleanup:
2020         /* release the working reference to the output device */
2021         in_dev_put(out_dev);
2022         return err;
2023 }
2024
2025 static int ip_mkroute_input(struct sk_buff *skb,
2026                             struct fib_result *res,
2027                             const struct flowi *fl,
2028                             struct in_device *in_dev,
2029                             __be32 daddr, __be32 saddr, u32 tos)
2030 {
2031         struct rtable* rth = NULL;
2032         int err;
2033         unsigned hash;
2034
2035 #ifdef CONFIG_IP_ROUTE_MULTIPATH
2036         if (res->fi && res->fi->fib_nhs > 1 && fl->oif == 0)
2037                 fib_select_multipath(fl, res);
2038 #endif
2039
2040         /* create a routing cache entry */
2041         err = __mkroute_input(skb, res, in_dev, daddr, saddr, tos, &rth);
2042         if (err)
2043                 return err;
2044
2045         /* put it into the cache */
2046         hash = rt_hash(daddr, saddr, fl->iif,
2047                        rt_genid(dev_net(rth->u.dst.dev)));
2048         return rt_intern_hash(hash, rth, &skb->rtable);
2049 }
2050
2051 /*
2052  *      NOTE. We drop all the packets that has local source
2053  *      addresses, because every properly looped back packet
2054  *      must have correct destination already attached by output routine.
2055  *
2056  *      Such approach solves two big problems:
2057  *      1. Not simplex devices are handled properly.
2058  *      2. IP spoofing attempts are filtered with 100% of guarantee.
2059  */
2060
2061 static int ip_route_input_slow(struct sk_buff *skb, __be32 daddr, __be32 saddr,
2062                                u8 tos, struct net_device *dev)
2063 {
2064         struct fib_result res;
2065         struct in_device *in_dev = in_dev_get(dev);
2066         struct flowi fl = { .nl_u = { .ip4_u =
2067                                       { .daddr = daddr,
2068                                         .saddr = saddr,
2069                                         .tos = tos,
2070                                         .scope = RT_SCOPE_UNIVERSE,
2071                                       } },
2072                             .mark = skb->mark,
2073                             .iif = dev->ifindex };
2074         unsigned        flags = 0;
2075         u32             itag = 0;
2076         struct rtable * rth;
2077         unsigned        hash;
2078         __be32          spec_dst;
2079         int             err = -EINVAL;
2080         int             free_res = 0;
2081         struct net    * net = dev_net(dev);
2082
2083         /* IP on this device is disabled. */
2084
2085         if (!in_dev)
2086                 goto out;
2087
2088         /* Check for the most weird martians, which can be not detected
2089            by fib_lookup.
2090          */
2091
2092         if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr) ||
2093             ipv4_is_loopback(saddr))
2094                 goto martian_source;
2095
2096         if (daddr == htonl(0xFFFFFFFF) || (saddr == 0 && daddr == 0))
2097                 goto brd_input;
2098
2099         /* Accept zero addresses only to limited broadcast;
2100          * I even do not know to fix it or not. Waiting for complains :-)
2101          */
2102         if (ipv4_is_zeronet(saddr))
2103                 goto martian_source;
2104
2105         if (ipv4_is_lbcast(daddr) || ipv4_is_zeronet(daddr) ||
2106             ipv4_is_loopback(daddr))
2107                 goto martian_destination;
2108
2109         /*
2110          *      Now we are ready to route packet.
2111          */
2112         if ((err = fib_lookup(net, &fl, &res)) != 0) {
2113                 if (!IN_DEV_FORWARD(in_dev))
2114                         goto e_hostunreach;
2115                 goto no_route;
2116         }
2117         free_res = 1;
2118
2119         RT_CACHE_STAT_INC(in_slow_tot);
2120
2121         if (res.type == RTN_BROADCAST)
2122                 goto brd_input;
2123
2124         if (res.type == RTN_LOCAL) {
2125                 int result;
2126                 result = fib_validate_source(saddr, daddr, tos,
2127                                              net->loopback_dev->ifindex,
2128                                              dev, &spec_dst, &itag);
2129                 if (result < 0)
2130                         goto martian_source;
2131                 if (result)
2132                         flags |= RTCF_DIRECTSRC;
2133                 spec_dst = daddr;
2134                 goto local_input;
2135         }
2136
2137         if (!IN_DEV_FORWARD(in_dev))
2138                 goto e_hostunreach;
2139         if (res.type != RTN_UNICAST)
2140                 goto martian_destination;
2141
2142         err = ip_mkroute_input(skb, &res, &fl, in_dev, daddr, saddr, tos);
2143 done:
2144         in_dev_put(in_dev);
2145         if (free_res)
2146                 fib_res_put(&res);
2147 out:    return err;
2148
2149 brd_input:
2150         if (skb->protocol != htons(ETH_P_IP))
2151                 goto e_inval;
2152
2153         if (ipv4_is_zeronet(saddr))
2154                 spec_dst = inet_select_addr(dev, 0, RT_SCOPE_LINK);
2155         else {
2156                 err = fib_validate_source(saddr, 0, tos, 0, dev, &spec_dst,
2157                                           &itag);
2158                 if (err < 0)
2159                         goto martian_source;
2160                 if (err)
2161                         flags |= RTCF_DIRECTSRC;
2162         }
2163         flags |= RTCF_BROADCAST;
2164         res.type = RTN_BROADCAST;
2165         RT_CACHE_STAT_INC(in_brd);
2166
2167 local_input:
2168         rth = dst_alloc(&ipv4_dst_ops);
2169         if (!rth)
2170                 goto e_nobufs;
2171
2172         rth->u.dst.output= ip_rt_bug;
2173         rth->rt_genid = rt_genid(net);
2174
2175         atomic_set(&rth->u.dst.__refcnt, 1);
2176         rth->u.dst.flags= DST_HOST;
2177         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2178                 rth->u.dst.flags |= DST_NOPOLICY;
2179         rth->fl.fl4_dst = daddr;
2180         rth->rt_dst     = daddr;
2181         rth->fl.fl4_tos = tos;
2182         rth->fl.mark    = skb->mark;
2183         rth->fl.fl4_src = saddr;
2184         rth->rt_src     = saddr;
2185 #ifdef CONFIG_NET_CLS_ROUTE
2186         rth->u.dst.tclassid = itag;
2187 #endif
2188         rth->rt_iif     =
2189         rth->fl.iif     = dev->ifindex;
2190         rth->u.dst.dev  = net->loopback_dev;
2191         dev_hold(rth->u.dst.dev);
2192         rth->idev       = in_dev_get(rth->u.dst.dev);
2193         rth->rt_gateway = daddr;
2194         rth->rt_spec_dst= spec_dst;
2195         rth->u.dst.input= ip_local_deliver;
2196         rth->rt_flags   = flags|RTCF_LOCAL;
2197         if (res.type == RTN_UNREACHABLE) {
2198                 rth->u.dst.input= ip_error;
2199                 rth->u.dst.error= -err;
2200                 rth->rt_flags   &= ~RTCF_LOCAL;
2201         }
2202         rth->rt_type    = res.type;
2203         hash = rt_hash(daddr, saddr, fl.iif, rt_genid(net));
2204         err = rt_intern_hash(hash, rth, &skb->rtable);
2205         goto done;
2206
2207 no_route:
2208         RT_CACHE_STAT_INC(in_no_route);
2209         spec_dst = inet_select_addr(dev, 0, RT_SCOPE_UNIVERSE);
2210         res.type = RTN_UNREACHABLE;
2211         if (err == -ESRCH)
2212                 err = -ENETUNREACH;
2213         goto local_input;
2214
2215         /*
2216          *      Do not cache martian addresses: they should be logged (RFC1812)
2217          */
2218 martian_destination:
2219         RT_CACHE_STAT_INC(in_martian_dst);
2220 #ifdef CONFIG_IP_ROUTE_VERBOSE
2221         if (IN_DEV_LOG_MARTIANS(in_dev) && net_ratelimit())
2222                 printk(KERN_WARNING "martian destination " NIPQUAD_FMT " from "
2223                         NIPQUAD_FMT ", dev %s\n",
2224                         NIPQUAD(daddr), NIPQUAD(saddr), dev->name);
2225 #endif
2226
2227 e_hostunreach:
2228         err = -EHOSTUNREACH;
2229         goto done;
2230
2231 e_inval:
2232         err = -EINVAL;
2233         goto done;
2234
2235 e_nobufs:
2236         err = -ENOBUFS;
2237         goto done;
2238
2239 martian_source:
2240         ip_handle_martian_source(dev, in_dev, skb, daddr, saddr);
2241         goto e_inval;
2242 }
2243
2244 int ip_route_input(struct sk_buff *skb, __be32 daddr, __be32 saddr,
2245                    u8 tos, struct net_device *dev)
2246 {
2247         struct rtable * rth;
2248         unsigned        hash;
2249         int iif = dev->ifindex;
2250         struct net *net;
2251
2252         net = dev_net(dev);
2253
2254         if (!rt_caching(net))
2255                 goto skip_cache;
2256
2257         tos &= IPTOS_RT_MASK;
2258         hash = rt_hash(daddr, saddr, iif, rt_genid(net));
2259
2260         rcu_read_lock();
2261         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2262              rth = rcu_dereference(rth->u.dst.rt_next)) {
2263                 if (((rth->fl.fl4_dst ^ daddr) |
2264                      (rth->fl.fl4_src ^ saddr) |
2265                      (rth->fl.iif ^ iif) |
2266                      rth->fl.oif |
2267                      (rth->fl.fl4_tos ^ tos)) == 0 &&
2268                     rth->fl.mark == skb->mark &&
2269                     net_eq(dev_net(rth->u.dst.dev), net) &&
2270                     !rt_is_expired(rth)) {
2271                         dst_use(&rth->u.dst, jiffies);
2272                         RT_CACHE_STAT_INC(in_hit);
2273                         rcu_read_unlock();
2274                         skb->rtable = rth;
2275                         return 0;
2276                 }
2277                 RT_CACHE_STAT_INC(in_hlist_search);
2278         }
2279         rcu_read_unlock();
2280
2281 skip_cache:
2282         /* Multicast recognition logic is moved from route cache to here.
2283            The problem was that too many Ethernet cards have broken/missing
2284            hardware multicast filters :-( As result the host on multicasting
2285            network acquires a lot of useless route cache entries, sort of
2286            SDR messages from all the world. Now we try to get rid of them.
2287            Really, provided software IP multicast filter is organized
2288            reasonably (at least, hashed), it does not result in a slowdown
2289            comparing with route cache reject entries.
2290            Note, that multicast routers are not affected, because
2291            route cache entry is created eventually.
2292          */
2293         if (ipv4_is_multicast(daddr)) {
2294                 struct in_device *in_dev;
2295
2296                 rcu_read_lock();
2297                 if ((in_dev = __in_dev_get_rcu(dev)) != NULL) {
2298                         int our = ip_check_mc(in_dev, daddr, saddr,
2299                                 ip_hdr(skb)->protocol);
2300                         if (our
2301 #ifdef CONFIG_IP_MROUTE
2302                             || (!ipv4_is_local_multicast(daddr) &&
2303                                 IN_DEV_MFORWARD(in_dev))
2304 #endif
2305                             ) {
2306                                 rcu_read_unlock();
2307                                 return ip_route_input_mc(skb, daddr, saddr,
2308                                                          tos, dev, our);
2309                         }
2310                 }
2311                 rcu_read_unlock();
2312                 return -EINVAL;
2313         }
2314         return ip_route_input_slow(skb, daddr, saddr, tos, dev);
2315 }
2316
2317 static int __mkroute_output(struct rtable **result,
2318                             struct fib_result *res,
2319                             const struct flowi *fl,
2320                             const struct flowi *oldflp,
2321                             struct net_device *dev_out,
2322                             unsigned flags)
2323 {
2324         struct rtable *rth;
2325         struct in_device *in_dev;
2326         u32 tos = RT_FL_TOS(oldflp);
2327         int err = 0;
2328
2329         if (ipv4_is_loopback(fl->fl4_src) && !(dev_out->flags&IFF_LOOPBACK))
2330                 return -EINVAL;
2331
2332         if (fl->fl4_dst == htonl(0xFFFFFFFF))
2333                 res->type = RTN_BROADCAST;
2334         else if (ipv4_is_multicast(fl->fl4_dst))
2335                 res->type = RTN_MULTICAST;
2336         else if (ipv4_is_lbcast(fl->fl4_dst) || ipv4_is_zeronet(fl->fl4_dst))
2337                 return -EINVAL;
2338
2339         if (dev_out->flags & IFF_LOOPBACK)
2340                 flags |= RTCF_LOCAL;
2341
2342         /* get work reference to inet device */
2343         in_dev = in_dev_get(dev_out);
2344         if (!in_dev)
2345                 return -EINVAL;
2346
2347         if (res->type == RTN_BROADCAST) {
2348                 flags |= RTCF_BROADCAST | RTCF_LOCAL;
2349                 if (res->fi) {
2350                         fib_info_put(res->fi);
2351                         res->fi = NULL;
2352                 }
2353         } else if (res->type == RTN_MULTICAST) {
2354                 flags |= RTCF_MULTICAST|RTCF_LOCAL;
2355                 if (!ip_check_mc(in_dev, oldflp->fl4_dst, oldflp->fl4_src,
2356                                  oldflp->proto))
2357                         flags &= ~RTCF_LOCAL;
2358                 /* If multicast route do not exist use
2359                    default one, but do not gateway in this case.
2360                    Yes, it is hack.
2361                  */
2362                 if (res->fi && res->prefixlen < 4) {
2363                         fib_info_put(res->fi);
2364                         res->fi = NULL;
2365                 }
2366         }
2367
2368
2369         rth = dst_alloc(&ipv4_dst_ops);
2370         if (!rth) {
2371                 err = -ENOBUFS;
2372                 goto cleanup;
2373         }
2374
2375         atomic_set(&rth->u.dst.__refcnt, 1);
2376         rth->u.dst.flags= DST_HOST;
2377         if (IN_DEV_CONF_GET(in_dev, NOXFRM))
2378                 rth->u.dst.flags |= DST_NOXFRM;
2379         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
2380                 rth->u.dst.flags |= DST_NOPOLICY;
2381
2382         rth->fl.fl4_dst = oldflp->fl4_dst;
2383         rth->fl.fl4_tos = tos;
2384         rth->fl.fl4_src = oldflp->fl4_src;
2385         rth->fl.oif     = oldflp->oif;
2386         rth->fl.mark    = oldflp->mark;
2387         rth->rt_dst     = fl->fl4_dst;
2388         rth->rt_src     = fl->fl4_src;
2389         rth->rt_iif     = oldflp->oif ? : dev_out->ifindex;
2390         /* get references to the devices that are to be hold by the routing
2391            cache entry */
2392         rth->u.dst.dev  = dev_out;
2393         dev_hold(dev_out);
2394         rth->idev       = in_dev_get(dev_out);
2395         rth->rt_gateway = fl->fl4_dst;
2396         rth->rt_spec_dst= fl->fl4_src;
2397
2398         rth->u.dst.output=ip_output;
2399         rth->rt_genid = rt_genid(dev_net(dev_out));
2400
2401         RT_CACHE_STAT_INC(out_slow_tot);
2402
2403         if (flags & RTCF_LOCAL) {
2404                 rth->u.dst.input = ip_local_deliver;
2405                 rth->rt_spec_dst = fl->fl4_dst;
2406         }
2407         if (flags & (RTCF_BROADCAST | RTCF_MULTICAST)) {
2408                 rth->rt_spec_dst = fl->fl4_src;
2409                 if (flags & RTCF_LOCAL &&
2410                     !(dev_out->flags & IFF_LOOPBACK)) {
2411                         rth->u.dst.output = ip_mc_output;
2412                         RT_CACHE_STAT_INC(out_slow_mc);
2413                 }
2414 #ifdef CONFIG_IP_MROUTE
2415                 if (res->type == RTN_MULTICAST) {
2416                         if (IN_DEV_MFORWARD(in_dev) &&
2417                             !ipv4_is_local_multicast(oldflp->fl4_dst)) {
2418                                 rth->u.dst.input = ip_mr_input;
2419                                 rth->u.dst.output = ip_mc_output;
2420                         }
2421                 }
2422 #endif
2423         }
2424
2425         rt_set_nexthop(rth, res, 0);
2426
2427         rth->rt_flags = flags;
2428
2429         *result = rth;
2430  cleanup:
2431         /* release work reference to inet device */
2432         in_dev_put(in_dev);
2433
2434         return err;
2435 }
2436
2437 static int ip_mkroute_output(struct rtable **rp,
2438                              struct fib_result *res,
2439                              const struct flowi *fl,
2440                              const struct flowi *oldflp,
2441                              struct net_device *dev_out,
2442                              unsigned flags)
2443 {
2444         struct rtable *rth = NULL;
2445         int err = __mkroute_output(&rth, res, fl, oldflp, dev_out, flags);
2446         unsigned hash;
2447         if (err == 0) {
2448                 hash = rt_hash(oldflp->fl4_dst, oldflp->fl4_src, oldflp->oif,
2449                                rt_genid(dev_net(dev_out)));
2450                 err = rt_intern_hash(hash, rth, rp);
2451         }
2452
2453         return err;
2454 }
2455
2456 /*
2457  * Major route resolver routine.
2458  */
2459
2460 static int ip_route_output_slow(struct net *net, struct rtable **rp,
2461                                 const struct flowi *oldflp)
2462 {
2463         u32 tos = RT_FL_TOS(oldflp);
2464         struct flowi fl = { .nl_u = { .ip4_u =
2465                                       { .daddr = oldflp->fl4_dst,
2466                                         .saddr = oldflp->fl4_src,
2467                                         .tos = tos & IPTOS_RT_MASK,
2468                                         .scope = ((tos & RTO_ONLINK) ?
2469                                                   RT_SCOPE_LINK :
2470                                                   RT_SCOPE_UNIVERSE),
2471                                       } },
2472                             .mark = oldflp->mark,
2473                             .iif = net->loopback_dev->ifindex,
2474                             .oif = oldflp->oif };
2475         struct fib_result res;
2476         unsigned flags = 0;
2477         struct net_device *dev_out = NULL;
2478         int free_res = 0;
2479         int err;
2480
2481
2482         res.fi          = NULL;
2483 #ifdef CONFIG_IP_MULTIPLE_TABLES
2484         res.r           = NULL;
2485 #endif
2486
2487         if (oldflp->fl4_src) {
2488                 err = -EINVAL;
2489                 if (ipv4_is_multicast(oldflp->fl4_src) ||
2490                     ipv4_is_lbcast(oldflp->fl4_src) ||
2491                     ipv4_is_zeronet(oldflp->fl4_src))
2492                         goto out;
2493
2494                 /* I removed check for oif == dev_out->oif here.
2495                    It was wrong for two reasons:
2496                    1. ip_dev_find(net, saddr) can return wrong iface, if saddr
2497                       is assigned to multiple interfaces.
2498                    2. Moreover, we are allowed to send packets with saddr
2499                       of another iface. --ANK
2500                  */
2501
2502                 if (oldflp->oif == 0
2503                     && (ipv4_is_multicast(oldflp->fl4_dst) ||
2504                         oldflp->fl4_dst == htonl(0xFFFFFFFF))) {
2505                         /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
2506                         dev_out = ip_dev_find(net, oldflp->fl4_src);
2507                         if (dev_out == NULL)
2508                                 goto out;
2509
2510                         /* Special hack: user can direct multicasts
2511                            and limited broadcast via necessary interface
2512                            without fiddling with IP_MULTICAST_IF or IP_PKTINFO.
2513                            This hack is not just for fun, it allows
2514                            vic,vat and friends to work.
2515                            They bind socket to loopback, set ttl to zero
2516                            and expect that it will work.
2517                            From the viewpoint of routing cache they are broken,
2518                            because we are not allowed to build multicast path
2519                            with loopback source addr (look, routing cache
2520                            cannot know, that ttl is zero, so that packet
2521                            will not leave this host and route is valid).
2522                            Luckily, this hack is good workaround.
2523                          */
2524
2525                         fl.oif = dev_out->ifindex;
2526                         goto make_route;
2527                 }
2528
2529                 if (!(oldflp->flags & FLOWI_FLAG_ANYSRC)) {
2530                         /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
2531                         dev_out = ip_dev_find(net, oldflp->fl4_src);
2532                         if (dev_out == NULL)
2533                                 goto out;
2534                         dev_put(dev_out);
2535                         dev_out = NULL;
2536                 }
2537         }
2538
2539
2540         if (oldflp->oif) {
2541                 dev_out = dev_get_by_index(net, oldflp->oif);
2542                 err = -ENODEV;
2543                 if (dev_out == NULL)
2544                         goto out;
2545
2546                 /* RACE: Check return value of inet_select_addr instead. */
2547                 if (__in_dev_get_rtnl(dev_out) == NULL) {
2548                         dev_put(dev_out);
2549                         goto out;       /* Wrong error code */
2550                 }
2551
2552                 if (ipv4_is_local_multicast(oldflp->fl4_dst) ||
2553                     oldflp->fl4_dst == htonl(0xFFFFFFFF)) {
2554                         if (!fl.fl4_src)
2555                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2556                                                               RT_SCOPE_LINK);
2557                         goto make_route;
2558                 }
2559                 if (!fl.fl4_src) {
2560                         if (ipv4_is_multicast(oldflp->fl4_dst))
2561                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2562                                                               fl.fl4_scope);
2563                         else if (!oldflp->fl4_dst)
2564                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2565                                                               RT_SCOPE_HOST);
2566                 }
2567         }
2568
2569         if (!fl.fl4_dst) {
2570                 fl.fl4_dst = fl.fl4_src;
2571                 if (!fl.fl4_dst)
2572                         fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
2573                 if (dev_out)
2574                         dev_put(dev_out);
2575                 dev_out = net->loopback_dev;
2576                 dev_hold(dev_out);
2577                 fl.oif = net->loopback_dev->ifindex;
2578                 res.type = RTN_LOCAL;
2579                 flags |= RTCF_LOCAL;
2580                 goto make_route;
2581         }
2582
2583         if (fib_lookup(net, &fl, &res)) {
2584                 res.fi = NULL;
2585                 if (oldflp->oif) {
2586                         /* Apparently, routing tables are wrong. Assume,
2587                            that the destination is on link.
2588
2589                            WHY? DW.
2590                            Because we are allowed to send to iface
2591                            even if it has NO routes and NO assigned
2592                            addresses. When oif is specified, routing
2593                            tables are looked up with only one purpose:
2594                            to catch if destination is gatewayed, rather than
2595                            direct. Moreover, if MSG_DONTROUTE is set,
2596                            we send packet, ignoring both routing tables
2597                            and ifaddr state. --ANK
2598
2599
2600                            We could make it even if oif is unknown,
2601                            likely IPv6, but we do not.
2602                          */
2603
2604                         if (fl.fl4_src == 0)
2605                                 fl.fl4_src = inet_select_addr(dev_out, 0,
2606                                                               RT_SCOPE_LINK);
2607                         res.type = RTN_UNICAST;
2608                         goto make_route;
2609                 }
2610                 if (dev_out)
2611                         dev_put(dev_out);
2612                 err = -ENETUNREACH;
2613                 goto out;
2614         }
2615         free_res = 1;
2616
2617         if (res.type == RTN_LOCAL) {
2618                 if (!fl.fl4_src)
2619                         fl.fl4_src = fl.fl4_dst;
2620                 if (dev_out)
2621                         dev_put(dev_out);
2622                 dev_out = net->loopback_dev;
2623                 dev_hold(dev_out);
2624                 fl.oif = dev_out->ifindex;
2625                 if (res.fi)
2626                         fib_info_put(res.fi);
2627                 res.fi = NULL;
2628                 flags |= RTCF_LOCAL;
2629                 goto make_route;
2630         }
2631
2632 #ifdef CONFIG_IP_ROUTE_MULTIPATH
2633         if (res.fi->fib_nhs > 1 && fl.oif == 0)
2634                 fib_select_multipath(&fl, &res);
2635         else
2636 #endif
2637         if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
2638                 fib_select_default(net, &fl, &res);
2639
2640         if (!fl.fl4_src)
2641                 fl.fl4_src = FIB_RES_PREFSRC(res);
2642
2643         if (dev_out)
2644                 dev_put(dev_out);
2645         dev_out = FIB_RES_DEV(res);
2646         dev_hold(dev_out);
2647         fl.oif = dev_out->ifindex;
2648
2649
2650 make_route:
2651         err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
2652
2653
2654         if (free_res)
2655                 fib_res_put(&res);
2656         if (dev_out)
2657                 dev_put(dev_out);
2658 out:    return err;
2659 }
2660
2661 int __ip_route_output_key(struct net *net, struct rtable **rp,
2662                           const struct flowi *flp)
2663 {
2664         unsigned hash;
2665         struct rtable *rth;
2666
2667         if (!rt_caching(net))
2668                 goto slow_output;
2669
2670         hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif, rt_genid(net));
2671
2672         rcu_read_lock_bh();
2673         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
2674                 rth = rcu_dereference(rth->u.dst.rt_next)) {
2675                 if (rth->fl.fl4_dst == flp->fl4_dst &&
2676                     rth->fl.fl4_src == flp->fl4_src &&
2677                     rth->fl.iif == 0 &&
2678                     rth->fl.oif == flp->oif &&
2679                     rth->fl.mark == flp->mark &&
2680                     !((rth->fl.fl4_tos ^ flp->fl4_tos) &
2681                             (IPTOS_RT_MASK | RTO_ONLINK)) &&
2682                     net_eq(dev_net(rth->u.dst.dev), net) &&
2683                     !rt_is_expired(rth)) {
2684                         dst_use(&rth->u.dst, jiffies);
2685                         RT_CACHE_STAT_INC(out_hit);
2686                         rcu_read_unlock_bh();
2687                         *rp = rth;
2688                         return 0;
2689                 }
2690                 RT_CACHE_STAT_INC(out_hlist_search);
2691         }
2692         rcu_read_unlock_bh();
2693
2694 slow_output:
2695         return ip_route_output_slow(net, rp, flp);
2696 }
2697
2698 EXPORT_SYMBOL_GPL(__ip_route_output_key);
2699
2700 static void ipv4_rt_blackhole_update_pmtu(struct dst_entry *dst, u32 mtu)
2701 {
2702 }
2703
2704 static struct dst_ops ipv4_dst_blackhole_ops = {
2705         .family                 =       AF_INET,
2706         .protocol               =       __constant_htons(ETH_P_IP),
2707         .destroy                =       ipv4_dst_destroy,
2708         .check                  =       ipv4_dst_check,
2709         .update_pmtu            =       ipv4_rt_blackhole_update_pmtu,
2710         .entry_size             =       sizeof(struct rtable),
2711         .entries                =       ATOMIC_INIT(0),
2712 };
2713
2714
2715 static int ipv4_dst_blackhole(struct net *net, struct rtable **rp, struct flowi *flp)
2716 {
2717         struct rtable *ort = *rp;
2718         struct rtable *rt = (struct rtable *)
2719                 dst_alloc(&ipv4_dst_blackhole_ops);
2720
2721         if (rt) {
2722                 struct dst_entry *new = &rt->u.dst;
2723
2724                 atomic_set(&new->__refcnt, 1);
2725                 new->__use = 1;
2726                 new->input = dst_discard;
2727                 new->output = dst_discard;
2728                 memcpy(new->metrics, ort->u.dst.metrics, RTAX_MAX*sizeof(u32));
2729
2730                 new->dev = ort->u.dst.dev;
2731                 if (new->dev)
2732                         dev_hold(new->dev);
2733
2734                 rt->fl = ort->fl;
2735
2736                 rt->idev = ort->idev;
2737                 if (rt->idev)
2738                         in_dev_hold(rt->idev);
2739                 rt->rt_genid = rt_genid(net);
2740                 rt->rt_flags = ort->rt_flags;
2741                 rt->rt_type = ort->rt_type;
2742                 rt->rt_dst = ort->rt_dst;
2743                 rt->rt_src = ort->rt_src;
2744                 rt->rt_iif = ort->rt_iif;
2745                 rt->rt_gateway = ort->rt_gateway;
2746                 rt->rt_spec_dst = ort->rt_spec_dst;
2747                 rt->peer = ort->peer;
2748                 if (rt->peer)
2749                         atomic_inc(&rt->peer->refcnt);
2750
2751                 dst_free(new);
2752         }
2753
2754         dst_release(&(*rp)->u.dst);
2755         *rp = rt;
2756         return (rt ? 0 : -ENOMEM);
2757 }
2758
2759 int ip_route_output_flow(struct net *net, struct rtable **rp, struct flowi *flp,
2760                          struct sock *sk, int flags)
2761 {
2762         int err;
2763
2764         if ((err = __ip_route_output_key(net, rp, flp)) != 0)
2765                 return err;
2766
2767         if (flp->proto) {
2768                 if (!flp->fl4_src)
2769                         flp->fl4_src = (*rp)->rt_src;
2770                 if (!flp->fl4_dst)
2771                         flp->fl4_dst = (*rp)->rt_dst;
2772                 err = __xfrm_lookup((struct dst_entry **)rp, flp, sk,
2773                                     flags ? XFRM_LOOKUP_WAIT : 0);
2774                 if (err == -EREMOTE)
2775                         err = ipv4_dst_blackhole(net, rp, flp);
2776
2777                 return err;
2778         }
2779
2780         return 0;
2781 }
2782
2783 EXPORT_SYMBOL_GPL(ip_route_output_flow);
2784
2785 int ip_route_output_key(struct net *net, struct rtable **rp, struct flowi *flp)
2786 {
2787         return ip_route_output_flow(net, rp, flp, NULL, 0);
2788 }
2789
2790 static int rt_fill_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
2791                         int nowait, unsigned int flags)
2792 {
2793         struct rtable *rt = skb->rtable;
2794         struct rtmsg *r;
2795         struct nlmsghdr *nlh;
2796         long expires;
2797         u32 id = 0, ts = 0, tsage = 0, error;
2798
2799         nlh = nlmsg_put(skb, pid, seq, event, sizeof(*r), flags);
2800         if (nlh == NULL)
2801                 return -EMSGSIZE;
2802
2803         r = nlmsg_data(nlh);
2804         r->rtm_family    = AF_INET;
2805         r->rtm_dst_len  = 32;
2806         r->rtm_src_len  = 0;
2807         r->rtm_tos      = rt->fl.fl4_tos;
2808         r->rtm_table    = RT_TABLE_MAIN;
2809         NLA_PUT_U32(skb, RTA_TABLE, RT_TABLE_MAIN);
2810         r->rtm_type     = rt->rt_type;
2811         r->rtm_scope    = RT_SCOPE_UNIVERSE;
2812         r->rtm_protocol = RTPROT_UNSPEC;
2813         r->rtm_flags    = (rt->rt_flags & ~0xFFFF) | RTM_F_CLONED;
2814         if (rt->rt_flags & RTCF_NOTIFY)
2815                 r->rtm_flags |= RTM_F_NOTIFY;
2816
2817         NLA_PUT_BE32(skb, RTA_DST, rt->rt_dst);
2818
2819         if (rt->fl.fl4_src) {
2820                 r->rtm_src_len = 32;
2821                 NLA_PUT_BE32(skb, RTA_SRC, rt->fl.fl4_src);
2822         }
2823         if (rt->u.dst.dev)
2824                 NLA_PUT_U32(skb, RTA_OIF, rt->u.dst.dev->ifindex);
2825 #ifdef CONFIG_NET_CLS_ROUTE
2826         if (rt->u.dst.tclassid)
2827                 NLA_PUT_U32(skb, RTA_FLOW, rt->u.dst.tclassid);
2828 #endif
2829         if (rt->fl.iif)
2830                 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_spec_dst);
2831         else if (rt->rt_src != rt->fl.fl4_src)
2832                 NLA_PUT_BE32(skb, RTA_PREFSRC, rt->rt_src);
2833
2834         if (rt->rt_dst != rt->rt_gateway)
2835                 NLA_PUT_BE32(skb, RTA_GATEWAY, rt->rt_gateway);
2836
2837         if (rtnetlink_put_metrics(skb, rt->u.dst.metrics) < 0)
2838                 goto nla_put_failure;
2839
2840         error = rt->u.dst.error;
2841         expires = rt->u.dst.expires ? rt->u.dst.expires - jiffies : 0;
2842         if (rt->peer) {
2843                 id = rt->peer->ip_id_count;
2844                 if (rt->peer->tcp_ts_stamp) {
2845                         ts = rt->peer->tcp_ts;
2846                         tsage = get_seconds() - rt->peer->tcp_ts_stamp;
2847                 }
2848         }
2849
2850         if (rt->fl.iif) {
2851 #ifdef CONFIG_IP_MROUTE
2852                 __be32 dst = rt->rt_dst;
2853
2854                 if (ipv4_is_multicast(dst) && !ipv4_is_local_multicast(dst) &&
2855                     IPV4_DEVCONF_ALL(&init_net, MC_FORWARDING)) {
2856                         int err = ipmr_get_route(skb, r, nowait);
2857                         if (err <= 0) {
2858                                 if (!nowait) {
2859                                         if (err == 0)
2860                                                 return 0;
2861                                         goto nla_put_failure;
2862                                 } else {
2863                                         if (err == -EMSGSIZE)
2864                                                 goto nla_put_failure;
2865                                         error = err;
2866                                 }
2867                         }
2868                 } else
2869 #endif
2870                         NLA_PUT_U32(skb, RTA_IIF, rt->fl.iif);
2871         }
2872
2873         if (rtnl_put_cacheinfo(skb, &rt->u.dst, id, ts, tsage,
2874                                expires, error) < 0)
2875                 goto nla_put_failure;
2876
2877         return nlmsg_end(skb, nlh);
2878
2879 nla_put_failure:
2880         nlmsg_cancel(skb, nlh);
2881         return -EMSGSIZE;
2882 }
2883
2884 static int inet_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg)
2885 {
2886         struct net *net = sock_net(in_skb->sk);
2887         struct rtmsg *rtm;
2888         struct nlattr *tb[RTA_MAX+1];
2889         struct rtable *rt = NULL;
2890         __be32 dst = 0;
2891         __be32 src = 0;
2892         u32 iif;
2893         int err;
2894         struct sk_buff *skb;
2895
2896         err = nlmsg_parse(nlh, sizeof(*rtm), tb, RTA_MAX, rtm_ipv4_policy);
2897         if (err < 0)
2898                 goto errout;
2899
2900         rtm = nlmsg_data(nlh);
2901
2902         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
2903         if (skb == NULL) {
2904                 err = -ENOBUFS;
2905                 goto errout;
2906         }
2907
2908         /* Reserve room for dummy headers, this skb can pass
2909            through good chunk of routing engine.
2910          */
2911         skb_reset_mac_header(skb);
2912         skb_reset_network_header(skb);
2913
2914         /* Bugfix: need to give ip_route_input enough of an IP header to not gag. */
2915         ip_hdr(skb)->protocol = IPPROTO_ICMP;
2916         skb_reserve(skb, MAX_HEADER + sizeof(struct iphdr));
2917
2918         src = tb[RTA_SRC] ? nla_get_be32(tb[RTA_SRC]) : 0;
2919         dst = tb[RTA_DST] ? nla_get_be32(tb[RTA_DST]) : 0;
2920         iif = tb[RTA_IIF] ? nla_get_u32(tb[RTA_IIF]) : 0;
2921
2922         if (iif) {
2923                 struct net_device *dev;
2924
2925                 dev = __dev_get_by_index(net, iif);
2926                 if (dev == NULL) {
2927                         err = -ENODEV;
2928                         goto errout_free;
2929                 }
2930
2931                 skb->protocol   = htons(ETH_P_IP);
2932                 skb->dev        = dev;
2933                 local_bh_disable();
2934                 err = ip_route_input(skb, dst, src, rtm->rtm_tos, dev);
2935                 local_bh_enable();
2936
2937                 rt = skb->rtable;
2938                 if (err == 0 && rt->u.dst.error)
2939                         err = -rt->u.dst.error;
2940         } else {
2941                 struct flowi fl = {
2942                         .nl_u = {
2943                                 .ip4_u = {
2944                                         .daddr = dst,
2945                                         .saddr = src,
2946                                         .tos = rtm->rtm_tos,
2947                                 },
2948                         },
2949                         .oif = tb[RTA_OIF] ? nla_get_u32(tb[RTA_OIF]) : 0,
2950                 };
2951                 err = ip_route_output_key(net, &rt, &fl);
2952         }
2953
2954         if (err)
2955                 goto errout_free;
2956
2957         skb->rtable = rt;
2958         if (rtm->rtm_flags & RTM_F_NOTIFY)
2959                 rt->rt_flags |= RTCF_NOTIFY;
2960
2961         err = rt_fill_info(skb, NETLINK_CB(in_skb).pid, nlh->nlmsg_seq,
2962                            RTM_NEWROUTE, 0, 0);
2963         if (err <= 0)
2964                 goto errout_free;
2965
2966         err = rtnl_unicast(skb, net, NETLINK_CB(in_skb).pid);
2967 errout:
2968         return err;
2969
2970 errout_free:
2971         kfree_skb(skb);
2972         goto errout;
2973 }
2974
2975 int ip_rt_dump(struct sk_buff *skb,  struct netlink_callback *cb)
2976 {
2977         struct rtable *rt;
2978         int h, s_h;
2979         int idx, s_idx;
2980         struct net *net;
2981
2982         net = sock_net(skb->sk);
2983
2984         s_h = cb->args[0];
2985         if (s_h < 0)
2986                 s_h = 0;
2987         s_idx = idx = cb->args[1];
2988         for (h = s_h; h <= rt_hash_mask; h++, s_idx = 0) {
2989                 if (!rt_hash_table[h].chain)
2990                         continue;
2991                 rcu_read_lock_bh();
2992                 for (rt = rcu_dereference(rt_hash_table[h].chain), idx = 0; rt;
2993                      rt = rcu_dereference(rt->u.dst.rt_next), idx++) {
2994                         if (!net_eq(dev_net(rt->u.dst.dev), net) || idx < s_idx)
2995                                 continue;
2996                         if (rt_is_expired(rt))
2997                                 continue;
2998                         skb->dst = dst_clone(&rt->u.dst);
2999                         if (rt_fill_info(skb, NETLINK_CB(cb->skb).pid,
3000                                          cb->nlh->nlmsg_seq, RTM_NEWROUTE,
3001                                          1, NLM_F_MULTI) <= 0) {
3002                                 dst_release(xchg(&skb->dst, NULL));
3003                                 rcu_read_unlock_bh();
3004                                 goto done;
3005                         }
3006                         dst_release(xchg(&skb->dst, NULL));
3007                 }
3008                 rcu_read_unlock_bh();
3009         }
3010
3011 done:
3012         cb->args[0] = h;
3013         cb->args[1] = idx;
3014         return skb->len;
3015 }
3016
3017 void ip_rt_multicast_event(struct in_device *in_dev)
3018 {
3019         rt_cache_flush(dev_net(in_dev->dev), 0);
3020 }
3021
3022 #ifdef CONFIG_SYSCTL
3023 static int ipv4_sysctl_rtcache_flush(ctl_table *__ctl, int write,
3024                                         struct file *filp, void __user *buffer,
3025                                         size_t *lenp, loff_t *ppos)
3026 {
3027         if (write) {
3028                 int flush_delay;
3029                 ctl_table ctl;
3030                 struct net *net;
3031
3032                 memcpy(&ctl, __ctl, sizeof(ctl));
3033                 ctl.data = &flush_delay;
3034                 proc_dointvec(&ctl, write, filp, buffer, lenp, ppos);
3035
3036                 net = (struct net *)__ctl->extra1;
3037                 rt_cache_flush(net, flush_delay);
3038                 return 0;
3039         }
3040
3041         return -EINVAL;
3042 }
3043
3044 static int ipv4_sysctl_rtcache_flush_strategy(ctl_table *table,
3045                                                 void __user *oldval,
3046                                                 size_t __user *oldlenp,
3047                                                 void __user *newval,
3048                                                 size_t newlen)
3049 {
3050         int delay;
3051         struct net *net;
3052         if (newlen != sizeof(int))
3053                 return -EINVAL;
3054         if (get_user(delay, (int __user *)newval))
3055                 return -EFAULT;
3056         net = (struct net *)table->extra1;
3057         rt_cache_flush(net, delay);
3058         return 0;
3059 }
3060
3061 static void rt_secret_reschedule(int old)
3062 {
3063         struct net *net;
3064         int new = ip_rt_secret_interval;
3065         int diff = new - old;
3066
3067         if (!diff)
3068                 return;
3069
3070         rtnl_lock();
3071         for_each_net(net) {
3072                 int deleted = del_timer_sync(&net->ipv4.rt_secret_timer);
3073
3074                 if (!new)
3075                         continue;
3076
3077                 if (deleted) {
3078                         long time = net->ipv4.rt_secret_timer.expires - jiffies;
3079
3080                         if (time <= 0 || (time += diff) <= 0)
3081                                 time = 0;
3082
3083                         net->ipv4.rt_secret_timer.expires = time;
3084                 } else
3085                         net->ipv4.rt_secret_timer.expires = new;
3086
3087                 net->ipv4.rt_secret_timer.expires += jiffies;
3088                 add_timer(&net->ipv4.rt_secret_timer);
3089         }
3090         rtnl_unlock();
3091 }
3092
3093 static int ipv4_sysctl_rt_secret_interval(ctl_table *ctl, int write,
3094                                           struct file *filp,
3095                                           void __user *buffer, size_t *lenp,
3096                                           loff_t *ppos)
3097 {
3098         int old = ip_rt_secret_interval;
3099         int ret = proc_dointvec_jiffies(ctl, write, filp, buffer, lenp, ppos);
3100
3101         rt_secret_reschedule(old);
3102
3103         return ret;
3104 }
3105
3106 static int ipv4_sysctl_rt_secret_interval_strategy(ctl_table *table,
3107                                                    void __user *oldval,
3108                                                    size_t __user *oldlenp,
3109                                                    void __user *newval,
3110                                                    size_t newlen)
3111 {
3112         int old = ip_rt_secret_interval;
3113         int ret = sysctl_jiffies(table, oldval, oldlenp, newval, newlen);
3114
3115         rt_secret_reschedule(old);
3116
3117         return ret;
3118 }
3119
3120 static ctl_table ipv4_route_table[] = {
3121         {
3122                 .ctl_name       = NET_IPV4_ROUTE_GC_THRESH,
3123                 .procname       = "gc_thresh",
3124                 .data           = &ipv4_dst_ops.gc_thresh,
3125                 .maxlen         = sizeof(int),
3126                 .mode           = 0644,
3127                 .proc_handler   = &proc_dointvec,
3128         },
3129         {
3130                 .ctl_name       = NET_IPV4_ROUTE_MAX_SIZE,
3131                 .procname       = "max_size",
3132                 .data           = &ip_rt_max_size,
3133                 .maxlen         = sizeof(int),
3134                 .mode           = 0644,
3135                 .proc_handler   = &proc_dointvec,
3136         },
3137         {
3138                 /*  Deprecated. Use gc_min_interval_ms */
3139
3140                 .ctl_name       = NET_IPV4_ROUTE_GC_MIN_INTERVAL,
3141                 .procname       = "gc_min_interval",
3142                 .data           = &ip_rt_gc_min_interval,
3143                 .maxlen         = sizeof(int),
3144                 .mode           = 0644,
3145                 .proc_handler   = &proc_dointvec_jiffies,
3146                 .strategy       = &sysctl_jiffies,
3147         },
3148         {
3149                 .ctl_name       = NET_IPV4_ROUTE_GC_MIN_INTERVAL_MS,
3150                 .procname       = "gc_min_interval_ms",
3151                 .data           = &ip_rt_gc_min_interval,
3152                 .maxlen         = sizeof(int),
3153                 .mode           = 0644,
3154                 .proc_handler   = &proc_dointvec_ms_jiffies,
3155                 .strategy       = &sysctl_ms_jiffies,
3156         },
3157         {
3158                 .ctl_name       = NET_IPV4_ROUTE_GC_TIMEOUT,
3159                 .procname       = "gc_timeout",
3160                 .data           = &ip_rt_gc_timeout,
3161                 .maxlen         = sizeof(int),
3162                 .mode           = 0644,
3163                 .proc_handler   = &proc_dointvec_jiffies,
3164                 .strategy       = &sysctl_jiffies,
3165         },
3166         {
3167                 .ctl_name       = NET_IPV4_ROUTE_GC_INTERVAL,
3168                 .procname       = "gc_interval",
3169                 .data           = &ip_rt_gc_interval,
3170                 .maxlen         = sizeof(int),
3171                 .mode           = 0644,
3172                 .proc_handler   = &proc_dointvec_jiffies,
3173                 .strategy       = &sysctl_jiffies,
3174         },
3175         {
3176                 .ctl_name       = NET_IPV4_ROUTE_REDIRECT_LOAD,
3177                 .procname       = "redirect_load",
3178                 .data           = &ip_rt_redirect_load,
3179                 .maxlen         = sizeof(int),
3180                 .mode           = 0644,
3181                 .proc_handler   = &proc_dointvec,
3182         },
3183         {
3184                 .ctl_name       = NET_IPV4_ROUTE_REDIRECT_NUMBER,
3185                 .procname       = "redirect_number",
3186                 .data           = &ip_rt_redirect_number,
3187                 .maxlen         = sizeof(int),
3188                 .mode           = 0644,
3189                 .proc_handler   = &proc_dointvec,
3190         },
3191         {
3192                 .ctl_name       = NET_IPV4_ROUTE_REDIRECT_SILENCE,
3193                 .procname       = "redirect_silence",
3194                 .data           = &ip_rt_redirect_silence,
3195                 .maxlen         = sizeof(int),
3196                 .mode           = 0644,
3197                 .proc_handler   = &proc_dointvec,
3198         },
3199         {
3200                 .ctl_name       = NET_IPV4_ROUTE_ERROR_COST,
3201                 .procname       = "error_cost",
3202                 .data           = &ip_rt_error_cost,
3203                 .maxlen         = sizeof(int),
3204                 .mode           = 0644,
3205                 .proc_handler   = &proc_dointvec,
3206         },
3207         {
3208                 .ctl_name       = NET_IPV4_ROUTE_ERROR_BURST,
3209                 .procname       = "error_burst",
3210                 .data           = &ip_rt_error_burst,
3211                 .maxlen         = sizeof(int),
3212                 .mode           = 0644,
3213                 .proc_handler   = &proc_dointvec,
3214         },
3215         {
3216                 .ctl_name       = NET_IPV4_ROUTE_GC_ELASTICITY,
3217                 .procname       = "gc_elasticity",
3218                 .data           = &ip_rt_gc_elasticity,
3219                 .maxlen         = sizeof(int),
3220                 .mode           = 0644,
3221                 .proc_handler   = &proc_dointvec,
3222         },
3223         {
3224                 .ctl_name       = NET_IPV4_ROUTE_MTU_EXPIRES,
3225                 .procname       = "mtu_expires",
3226                 .data           = &ip_rt_mtu_expires,
3227                 .maxlen         = sizeof(int),
3228                 .mode           = 0644,
3229                 .proc_handler   = &proc_dointvec_jiffies,
3230                 .strategy       = &sysctl_jiffies,
3231         },
3232         {
3233                 .ctl_name       = NET_IPV4_ROUTE_MIN_PMTU,
3234                 .procname       = "min_pmtu",
3235                 .data           = &ip_rt_min_pmtu,
3236                 .maxlen         = sizeof(int),
3237                 .mode           = 0644,
3238                 .proc_handler   = &proc_dointvec,
3239         },
3240         {
3241                 .ctl_name       = NET_IPV4_ROUTE_MIN_ADVMSS,
3242                 .procname       = "min_adv_mss",
3243                 .data           = &ip_rt_min_advmss,
3244                 .maxlen         = sizeof(int),
3245                 .mode           = 0644,
3246                 .proc_handler   = &proc_dointvec,
3247         },
3248         {
3249                 .ctl_name       = NET_IPV4_ROUTE_SECRET_INTERVAL,
3250                 .procname       = "secret_interval",
3251                 .data           = &ip_rt_secret_interval,
3252                 .maxlen         = sizeof(int),
3253                 .mode           = 0644,
3254                 .proc_handler   = &ipv4_sysctl_rt_secret_interval,
3255                 .strategy       = &ipv4_sysctl_rt_secret_interval_strategy,
3256         },
3257         { .ctl_name = 0 }
3258 };
3259
3260 static struct ctl_table empty[1];
3261
3262 static struct ctl_table ipv4_skeleton[] =
3263 {
3264         { .procname = "route", .ctl_name = NET_IPV4_ROUTE,
3265           .mode = 0555, .child = ipv4_route_table},
3266         { .procname = "neigh", .ctl_name = NET_IPV4_NEIGH,
3267           .mode = 0555, .child = empty},
3268         { }
3269 };
3270
3271 static __net_initdata struct ctl_path ipv4_path[] = {
3272         { .procname = "net", .ctl_name = CTL_NET, },
3273         { .procname = "ipv4", .ctl_name = NET_IPV4, },
3274         { },
3275 };
3276
3277 static struct ctl_table ipv4_route_flush_table[] = {
3278         {
3279                 .ctl_name       = NET_IPV4_ROUTE_FLUSH,
3280                 .procname       = "flush",
3281                 .maxlen         = sizeof(int),
3282                 .mode           = 0200,
3283                 .proc_handler   = &ipv4_sysctl_rtcache_flush,
3284                 .strategy       = &ipv4_sysctl_rtcache_flush_strategy,
3285         },
3286         { .ctl_name = 0 },
3287 };
3288
3289 static __net_initdata struct ctl_path ipv4_route_path[] = {
3290         { .procname = "net", .ctl_name = CTL_NET, },
3291         { .procname = "ipv4", .ctl_name = NET_IPV4, },
3292         { .procname = "route", .ctl_name = NET_IPV4_ROUTE, },
3293         { },
3294 };
3295
3296 static __net_init int sysctl_route_net_init(struct net *net)
3297 {
3298         struct ctl_table *tbl;
3299
3300         tbl = ipv4_route_flush_table;
3301         if (net != &init_net) {
3302                 tbl = kmemdup(tbl, sizeof(ipv4_route_flush_table), GFP_KERNEL);
3303                 if (tbl == NULL)
3304                         goto err_dup;
3305         }
3306         tbl[0].extra1 = net;
3307
3308         net->ipv4.route_hdr =
3309                 register_net_sysctl_table(net, ipv4_route_path, tbl);
3310         if (net->ipv4.route_hdr == NULL)
3311                 goto err_reg;
3312         return 0;
3313
3314 err_reg:
3315         if (tbl != ipv4_route_flush_table)
3316                 kfree(tbl);
3317 err_dup:
3318         return -ENOMEM;
3319 }
3320
3321 static __net_exit void sysctl_route_net_exit(struct net *net)
3322 {
3323         struct ctl_table *tbl;
3324
3325         tbl = net->ipv4.route_hdr->ctl_table_arg;
3326         unregister_net_sysctl_table(net->ipv4.route_hdr);
3327         BUG_ON(tbl == ipv4_route_flush_table);
3328         kfree(tbl);
3329 }
3330
3331 static __net_initdata struct pernet_operations sysctl_route_ops = {
3332         .init = sysctl_route_net_init,
3333         .exit = sysctl_route_net_exit,
3334 };
3335 #endif
3336
3337
3338 static __net_init int rt_secret_timer_init(struct net *net)
3339 {
3340         atomic_set(&net->ipv4.rt_genid,
3341                         (int) ((num_physpages ^ (num_physpages>>8)) ^
3342                         (jiffies ^ (jiffies >> 7))));
3343
3344         net->ipv4.rt_secret_timer.function = rt_secret_rebuild;
3345         net->ipv4.rt_secret_timer.data = (unsigned long)net;
3346         init_timer_deferrable(&net->ipv4.rt_secret_timer);
3347
3348         if (ip_rt_secret_interval) {
3349                 net->ipv4.rt_secret_timer.expires =
3350                         jiffies + net_random() % ip_rt_secret_interval +
3351                         ip_rt_secret_interval;
3352                 add_timer(&net->ipv4.rt_secret_timer);
3353         }
3354         return 0;
3355 }
3356
3357 static __net_exit void rt_secret_timer_exit(struct net *net)
3358 {
3359         del_timer_sync(&net->ipv4.rt_secret_timer);
3360 }
3361
3362 static __net_initdata struct pernet_operations rt_secret_timer_ops = {
3363         .init = rt_secret_timer_init,
3364         .exit = rt_secret_timer_exit,
3365 };
3366
3367
3368 #ifdef CONFIG_NET_CLS_ROUTE
3369 struct ip_rt_acct *ip_rt_acct __read_mostly;
3370 #endif /* CONFIG_NET_CLS_ROUTE */
3371
3372 static __initdata unsigned long rhash_entries;
3373 static int __init set_rhash_entries(char *str)
3374 {
3375         if (!str)
3376                 return 0;
3377         rhash_entries = simple_strtoul(str, &str, 0);
3378         return 1;
3379 }
3380 __setup("rhash_entries=", set_rhash_entries);
3381
3382 int __init ip_rt_init(void)
3383 {
3384         int rc = 0;
3385
3386 #ifdef CONFIG_NET_CLS_ROUTE
3387         ip_rt_acct = __alloc_percpu(256 * sizeof(struct ip_rt_acct));
3388         if (!ip_rt_acct)
3389                 panic("IP: failed to allocate ip_rt_acct\n");
3390 #endif
3391
3392         ipv4_dst_ops.kmem_cachep =
3393                 kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
3394                                   SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
3395
3396         ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;
3397
3398         rt_hash_table = (struct rt_hash_bucket *)
3399                 alloc_large_system_hash("IP route cache",
3400                                         sizeof(struct rt_hash_bucket),
3401                                         rhash_entries,
3402                                         (num_physpages >= 128 * 1024) ?
3403                                         15 : 17,
3404                                         0,
3405                                         &rt_hash_log,
3406                                         &rt_hash_mask,
3407                                         0);
3408         memset(rt_hash_table, 0, (rt_hash_mask + 1) * sizeof(struct rt_hash_bucket));
3409         rt_hash_lock_init();
3410
3411         ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
3412         ip_rt_max_size = (rt_hash_mask + 1) * 16;
3413
3414         devinet_init();
3415         ip_fib_init();
3416
3417         /* All the timers, started at system startup tend
3418            to synchronize. Perturb it a bit.
3419          */
3420         schedule_delayed_work(&expires_work,
3421                 net_random() % ip_rt_gc_interval + ip_rt_gc_interval);
3422
3423         if (register_pernet_subsys(&rt_secret_timer_ops))
3424                 printk(KERN_ERR "Unable to setup rt_secret_timer\n");
3425
3426         if (ip_rt_proc_init())
3427                 printk(KERN_ERR "Unable to create route proc files\n");
3428 #ifdef CONFIG_XFRM
3429         xfrm_init();
3430         xfrm4_init();
3431 #endif
3432         rtnl_register(PF_INET, RTM_GETROUTE, inet_rtm_getroute, NULL);
3433
3434 #ifdef CONFIG_SYSCTL
3435         register_pernet_subsys(&sysctl_route_ops);
3436 #endif
3437         return rc;
3438 }
3439
3440 #ifdef CONFIG_SYSCTL
3441 /*
3442  * We really need to sanitize the damn ipv4 init order, then all
3443  * this nonsense will go away.
3444  */
3445 void __init ip_static_sysctl_init(void)
3446 {
3447         register_sysctl_paths(ipv4_path, ipv4_skeleton);
3448 }
3449 #endif
3450
3451 EXPORT_SYMBOL(__ip_select_ident);
3452 EXPORT_SYMBOL(ip_route_input);
3453 EXPORT_SYMBOL(ip_route_output_key);