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