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