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