Re: Route cache performance under stress

["David S. Miller" <davem@xxxxxxxxxx>]

Ok Simon/Robert/Mr.Foo :), give this a try, it's my final installment
for the evening :-)

If this shows improvement, we can make even larger strides
by moving the struct flowi up into struct dst_entry.

--- net/core/dst.c.~1~  Mon Jun  9 01:47:26 2003
+++ net/core/dst.c      Mon Jun  9 03:13:56 2003
@@ -122,13 +122,34 @@ void * dst_alloc(struct dst_ops * ops)
        dst = kmem_cache_alloc(ops->kmem_cachep, SLAB_ATOMIC);
        if (!dst)
                return NULL;
-       memset(dst, 0, ops->entry_size);
+       dst->next = NULL;
        atomic_set(&dst->__refcnt, 0);
-       dst->ops = ops;
+       dst->__use = 0;
+       dst->child = NULL;
+       dst->dev = NULL;
+       dst->obsolete = 0;
+       dst->flags = 0;
        dst->lastuse = jiffies;
+       dst->expires = 0;
+       dst->header_len = 0;
+       dst->trailer_len = 0;
+       memset(dst->metrics, 0, sizeof(dst->metrics));
        dst->path = dst;
+       dst->rate_last = 0;
+       dst->rate_tokens = 0;
+       dst->error = 0;
+       dst->neighbour = NULL;
+       dst->hh = NULL;
+       dst->xfrm = NULL;
        dst->input = dst_discard;
        dst->output = dst_blackhole;
+#ifdef CONFIG_NET_CLS_ROUTE
+       dst->tclassid = 0;
+#endif
+       dst->ops = ops;
+       INIT_RCU_HEAD(&dst->rcu_head);
+       memset(dst->info, 0,
+              ops->entry_size - offsetof(struct dst_entry, info));
 #if RT_CACHE_DEBUG >= 2 
        atomic_inc(&dst_total);
 #endif
--- net/ipv4/route.c.~1~        Sun Jun  8 23:28:00 2003
+++ net/ipv4/route.c    Mon Jun  9 06:49:15 2003
@@ -88,6 +88,7 @@
 #include <linux/random.h>
 #include <linux/jhash.h>
 #include <linux/rcupdate.h>
+#include <linux/prefetch.h>
 #include <net/protocol.h>
 #include <net/ip.h>
 #include <net/route.h>
@@ -882,6 +883,60 @@ static void rt_del(unsigned hash, struct
        spin_unlock_bh(&rt_hash_table[hash].lock);
 }
 
+static void __rt_hash_shrink(unsigned int hash)
+{
+       struct rtable *rth, **rthp;
+       struct rtable *cand, **candp;
+       unsigned int min_use = ~(unsigned int) 0;
+
+       spin_lock_bh(&rt_hash_table[hash].lock);
+       cand = NULL;
+       candp = NULL;
+       rthp = &rt_hash_table[hash].chain;
+       while ((rth = *rthp) != NULL) {
+               if (!atomic_read(&rth->u.dst.__refcnt) &&
+                   ((unsigned int) rth->u.dst.__use) < min_use) {
+                       cand = rth;
+                       candp = rthp;
+                       min_use = rth->u.dst.__use;
+               }
+               rthp = &rth->u.rt_next;
+       }
+       if (cand) {
+               *candp = cand->u.rt_next;
+               rt_free(cand);
+       }
+
+       spin_unlock_bh(&rt_hash_table[hash].lock);
+}
+
+static inline struct rtable *ip_rt_dst_alloc(unsigned int hash)
+{
+       if (atomic_read(&ipv4_dst_ops.entries) >
+           ipv4_dst_ops.gc_thresh)
+               __rt_hash_shrink(hash);
+
+       return dst_alloc(&ipv4_dst_ops);
+}
+
+static void ip_rt_copy(struct rtable *rt, struct rtable *old)
+{
+       memcpy(rt, old, sizeof(*rt));
+
+       INIT_RCU_HEAD(&rt->u.dst.rcu_head);
+       rt->u.dst.__use         = 1;
+       atomic_set(&rt->u.dst.__refcnt, 1);
+       rt->u.dst.child         = NULL;
+       if (rt->u.dst.dev)
+               dev_hold(rt->u.dst.dev);
+       rt->u.dst.obsolete      = 0;
+       rt->u.dst.lastuse       = jiffies;
+       rt->u.dst.path          = &rt->u.dst;
+       rt->u.dst.neighbour     = NULL;
+       rt->u.dst.hh            = NULL;
+       rt->u.dst.xfrm          = NULL;
+}
+
 void ip_rt_redirect(u32 old_gw, u32 daddr, u32 new_gw,
                    u32 saddr, u8 tos, struct net_device *dev)
 {
@@ -912,9 +967,10 @@ void ip_rt_redirect(u32 old_gw, u32 dadd
 
        for (i = 0; i < 2; i++) {
                for (k = 0; k < 2; k++) {
-                       unsigned hash = rt_hash_code(daddr,
-                                                    skeys[i] ^ (ikeys[k] << 5),
-                                                    tos);
+                       unsigned int hash = rt_hash_code(daddr,
+                                                        skeys[i] ^
+                                                        (ikeys[k] << 5),
+                                                        tos);
 
                        rthp=&rt_hash_table[hash].chain;
 
@@ -942,7 +998,7 @@ void ip_rt_redirect(u32 old_gw, u32 dadd
                                dst_hold(&rth->u.dst);
                                rcu_read_unlock();
 
-                               rt = dst_alloc(&ipv4_dst_ops);
+                               rt = ip_rt_dst_alloc(hash);
                                if (rt == NULL) {
                                        ip_rt_put(rth);
                                        in_dev_put(in_dev);
@@ -950,19 +1006,7 @@ void ip_rt_redirect(u32 old_gw, u32 dadd
                                }
 
                                /* Copy all the information. */
-                               *rt = *rth;
-                               INIT_RCU_HEAD(&rt->u.dst.rcu_head);
-                               rt->u.dst.__use         = 1;
-                               atomic_set(&rt->u.dst.__refcnt, 1);
-                               rt->u.dst.child         = NULL;
-                               if (rt->u.dst.dev)
-                                       dev_hold(rt->u.dst.dev);
-                               rt->u.dst.obsolete      = 0;
-                               rt->u.dst.lastuse       = jiffies;
-                               rt->u.dst.path          = &rt->u.dst;
-                               rt->u.dst.neighbour     = NULL;
-                               rt->u.dst.hh            = NULL;
-                               rt->u.dst.xfrm          = NULL;
+                               ip_rt_copy(rt, rth);
 
                                rt->rt_flags            |= RTCF_REDIRECTED;
 
@@ -1352,7 +1396,7 @@ static void rt_set_nexthop(struct rtable
 static int ip_route_input_mc(struct sk_buff *skb, u32 daddr, u32 saddr,
                                u8 tos, struct net_device *dev, int our)
 {
-       unsigned hash;
+       unsigned int hash;
        struct rtable *rth;
        u32 spec_dst;
        struct in_device *in_dev = in_dev_get(dev);
@@ -1375,7 +1419,9 @@ static int ip_route_input_mc(struct sk_b
                                        dev, &spec_dst, &itag) < 0)
                goto e_inval;
 
-       rth = dst_alloc(&ipv4_dst_ops);
+       hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos);
+
+       rth = ip_rt_dst_alloc(hash);
        if (!rth)
                goto e_nobufs;
 
@@ -1421,7 +1467,6 @@ static int ip_route_input_mc(struct sk_b
        RT_CACHE_STAT_INC(in_slow_mc);
 
        in_dev_put(in_dev);
-       hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos);
        return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);
 
 e_nobufs:
@@ -1584,45 +1629,42 @@ int ip_route_input_slow(struct sk_buff *
                        goto e_inval;
        }
 
-       rth = dst_alloc(&ipv4_dst_ops);
+       rth = ip_rt_dst_alloc(hash);
        if (!rth)
                goto e_nobufs;
 
        atomic_set(&rth->u.dst.__refcnt, 1);
-       rth->u.dst.flags= DST_HOST;
-       if (in_dev->cnf.no_policy)
-               rth->u.dst.flags |= DST_NOPOLICY;
-       if (in_dev->cnf.no_xfrm)
-               rth->u.dst.flags |= DST_NOXFRM;
-       rth->fl.fl4_dst = daddr;
+       rth->u.dst.dev  = out_dev->dev;
+       dev_hold(out_dev->dev);
+       rth->u.dst.flags= (DST_HOST |
+                          (in_dev->cnf.no_policy ? DST_NOPOLICY : 0) |
+                          (in_dev->cnf.no_xfrm ? DST_NOXFRM : 0));
+       rth->u.dst.input = ip_forward;
+       rth->u.dst.output = ip_output;
+
+       rth->rt_flags   = flags;
+       rth->rt_src     = saddr;
        rth->rt_dst     = daddr;
-       rth->fl.fl4_tos = tos;
+       rth->rt_iif     = dev->ifindex;
+       rth->rt_gateway = daddr;
+
+       rth->fl.iif     = dev->ifindex;
+       rth->fl.fl4_dst = daddr;
+       rth->fl.fl4_src = saddr;
 #ifdef CONFIG_IP_ROUTE_FWMARK
        rth->fl.fl4_fwmark= skb->nfmark;
 #endif
-       rth->fl.fl4_src = saddr;
-       rth->rt_src     = saddr;
-       rth->rt_gateway = daddr;
+       rth->fl.fl4_tos = tos;
+       rth->rt_spec_dst= spec_dst;
 #ifdef CONFIG_IP_ROUTE_NAT
        rth->rt_src_map = fl.fl4_src;
        rth->rt_dst_map = fl.fl4_dst;
-       if (flags&RTCF_DNAT)
+       if (flags & RTCF_DNAT)
                rth->rt_gateway = fl.fl4_dst;
 #endif
-       rth->rt_iif     =
-       rth->fl.iif     = dev->ifindex;
-       rth->u.dst.dev  = out_dev->dev;
-       dev_hold(rth->u.dst.dev);
-       rth->fl.oif     = 0;
-       rth->rt_spec_dst= spec_dst;
-
-       rth->u.dst.input = ip_forward;
-       rth->u.dst.output = ip_output;
 
        rt_set_nexthop(rth, &res, itag);
 
-       rth->rt_flags = flags;
-
 #ifdef CONFIG_NET_FASTROUTE
        if (netdev_fastroute && !(flags&(RTCF_NAT|RTCF_MASQ|RTCF_DOREDIRECT))) {
                struct net_device *odev = rth->u.dst.dev;
@@ -1663,45 +1705,45 @@ brd_input:
        RT_CACHE_STAT_INC(in_brd);
 
 local_input:
-       rth = dst_alloc(&ipv4_dst_ops);
+       rth = ip_rt_dst_alloc(hash);
        if (!rth)
                goto e_nobufs;
 
+       atomic_set(&rth->u.dst.__refcnt, 1);
+       rth->u.dst.dev  = &loopback_dev;
+       dev_hold(&loopback_dev);
+       rth->u.dst.flags= (DST_HOST |
+                          (in_dev->cnf.no_policy ? DST_NOPOLICY : 0));
+       rth->u.dst.input= ip_local_deliver;
        rth->u.dst.output= ip_rt_bug;
+#ifdef CONFIG_NET_CLS_ROUTE
+       rth->u.dst.tclassid = itag;
+#endif
 
-       atomic_set(&rth->u.dst.__refcnt, 1);
-       rth->u.dst.flags= DST_HOST;
-       if (in_dev->cnf.no_policy)
-               rth->u.dst.flags |= DST_NOPOLICY;
-       rth->fl.fl4_dst = daddr;
+       rth->rt_flags   = flags|RTCF_LOCAL;
+       rth->rt_type    = res.type;
+       rth->rt_src     = saddr;
        rth->rt_dst     = daddr;
-       rth->fl.fl4_tos = tos;
+       rth->rt_iif     = dev->ifindex;
+       rth->rt_gateway = daddr;
+
+       rth->fl.iif     = dev->ifindex;
+       rth->fl.fl4_dst = daddr;
+       rth->fl.fl4_src = saddr;
 #ifdef CONFIG_IP_ROUTE_FWMARK
        rth->fl.fl4_fwmark= skb->nfmark;
 #endif
-       rth->fl.fl4_src = saddr;
-       rth->rt_src     = saddr;
+       rth->fl.fl4_tos = tos;
+       rth->rt_spec_dst= spec_dst;
 #ifdef CONFIG_IP_ROUTE_NAT
        rth->rt_dst_map = fl.fl4_dst;
        rth->rt_src_map = fl.fl4_src;
 #endif
-#ifdef CONFIG_NET_CLS_ROUTE
-       rth->u.dst.tclassid = itag;
-#endif
-       rth->rt_iif     =
-       rth->fl.iif     = dev->ifindex;
-       rth->u.dst.dev  = &loopback_dev;
-       dev_hold(rth->u.dst.dev);
-       rth->rt_gateway = daddr;
-       rth->rt_spec_dst= spec_dst;
-       rth->u.dst.input= ip_local_deliver;
-       rth->rt_flags   = flags|RTCF_LOCAL;
        if (res.type == RTN_UNREACHABLE) {
                rth->u.dst.input= ip_error;
                rth->u.dst.error= -err;
                rth->rt_flags   &= ~RTCF_LOCAL;
        }
-       rth->rt_type    = res.type;
        goto intern;
 
 no_route:
@@ -1767,6 +1809,8 @@ int ip_route_input(struct sk_buff *skb, 
        tos &= IPTOS_RT_MASK;
        hash = rt_hash_code(daddr, saddr ^ (iif << 5), tos);
 
+       prefetch(&rt_hash_table[hash].chain->fl);
+
        rcu_read_lock();
        for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.rt_next) {
                smp_read_barrier_depends();
@@ -2048,7 +2092,10 @@ make_route:
                }
        }
 
-       rth = dst_alloc(&ipv4_dst_ops);
+       hash = rt_hash_code(oldflp->fl4_dst,
+                           oldflp->fl4_src ^ (oldflp->oif << 5), tos);
+
+       rth = ip_rt_dst_alloc(hash);
        if (!rth)
                goto e_nobufs;
 
@@ -2104,10 +2151,6 @@ make_route:
 
        rt_set_nexthop(rth, &res, 0);
        
-
-       rth->rt_flags = flags;
-
-       hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 
5), tos);
        err = rt_intern_hash(hash, rth, rp);
 done:
        if (free_res)
@@ -2132,6 +2175,8 @@ int __ip_route_output_key(struct rtable 
        struct rtable *rth;
 
        hash = rt_hash_code(flp->fl4_dst, flp->fl4_src ^ (flp->oif << 5), 
flp->fl4_tos);
+
+       prefetch(&rt_hash_table[hash].chain->fl);
 
        rcu_read_lock();
        for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.rt_next) {