net/ipv4/route.c

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