net/ipv4/route.c

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