Skip to contentSkip to conversation

route cache: Introduce rt_genid for smooth cache invalidation

IPV4 Eric Dumazet 2 participants 2 messages Jan 30, 2008 – Feb 1, 2008

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

Current ip route cache implementation is not suited to large caches.

We can consume a lot of CPU when cache must be invalidated, since we currently need to evict all cache entries, and this eviction is sometimes asynchronous. min_delay & max_delay can somewhat control this asynchronism behavior, but whole thing is a kludge, regularly triggering infamous soft lockup messages. When entries are still in use, this also consumes a lot of ram, filling dst_garbage.list.

A better scheme is to use a generation identifier on each entry, so that cache invalidation can be performed by changing the table identifier, without having to scan all entries.
No more delayed flushing, no more stalling when secret_interval expires.

Invalidated entries will then be freed at GC time (controled by ip_rt_gc_timeout or stress), or when an invalidated entry is found in a chain when an insert is done.
Thus we keep a normal equilibrium.

This patch :
- renames rt_hash_rnd to rt_genid (and makes it an atomic_t)
- Adds a new rt_genid field to 'struct rtable' (filling a hole on 64bit)
- Checks entry->rt_genid at appropriate places :
--- Readers have to ignore invalidated entries.
--- Writers can delete invalidated entries.
- Removes rt_flush_timer timer
- Removes unused /proc/sys/net/ipv4/{min_delay,max_delay}

We even reduce size of route.o

# size net/ipv4/route.o
   text    data     bss     dec     hex filename
  20038    1331     160   21529    5419 net/ipv4/route.o.before
  19991    1203     104   21298    5332 net/ipv4/route.o

Next step will be to audit all rt_cache_flush(0) (aka flushes) users, see if they can be converted to "invalidate the cache" users.

 Documentation/filesystems/proc.txt |    4
 include/linux/sysctl.h             |    4
 include/net/route.h                |    1
 net/ipv4/route.c                   |  209 +++++++++++----------------
 4 files changed, 92 insertions(+), 126 deletions(-)
Documentation/filesystems/proc.txt +0 -5
index 4413a2d..11fe51c 100644
@@ -1919,11 +1919,6 @@ max_size
 Maximum size  of  the routing cache. Old entries will be purged once the cache
 reached has this size.
 
-max_delay, min_delay
---------------------
-
-Delays for flushing the routing cache.
-
 redirect_load, redirect_number
 ------------------------------
 
include/linux/sysctl.h +2 -2
index 89faebf..bf4ae4e 100644
@@ -440,8 +440,8 @@ enum
 
 enum {
 	NET_IPV4_ROUTE_FLUSH=1,
-	NET_IPV4_ROUTE_MIN_DELAY=2,
-	NET_IPV4_ROUTE_MAX_DELAY=3,
+	NET_IPV4_ROUTE_MIN_DELAY=2, /* obsolete since 2.6.25 */
+	NET_IPV4_ROUTE_MAX_DELAY=3, /* obsolete since 2.6.25 */
 	NET_IPV4_ROUTE_GC_THRESH=4,
 	NET_IPV4_ROUTE_MAX_SIZE=5,
 	NET_IPV4_ROUTE_GC_MIN_INTERVAL=6,
include/net/route.h +1 -0
index 4eabf00..c0675a4 100644
@@ -61,6 +61,7 @@ struct rtable
 
 	struct in_device	*idev;
 	
+	int			rt_genid;
 	unsigned		rt_flags;
 	__u16			rt_type;
 
net/ipv4/route.c +89 -120

415 lines not on this page · raw message

maintainer
#1 lore raw

From: Eric Dumazet <[email protected]>
Date: Wed, 30 Jan 2008 09:08:56 +0100

Quoted 35 lines

Current ip route cache implementation is not suited to large caches.

We can consume a lot of CPU when cache must be invalidated, since we currently need to evict all cache entries, and this eviction is sometimes asynchronous. min_delay & max_delay can somewhat control this asynchronism behavior, but whole thing is a kludge, regularly triggering infamous soft lockup messages. When entries are still in use, this also consumes a lot of ram, filling dst_garbage.list.

A better scheme is to use a generation identifier on each entry, so that cache invalidation can be performed by changing the table identifier, without having to scan all entries.
No more delayed flushing, no more stalling when secret_interval expires.

Invalidated entries will then be freed at GC time (controled by ip_rt_gc_timeout or stress), or when an invalidated entry is found in a chain when an insert is done.
Thus we keep a normal equilibrium.

This patch :
- renames rt_hash_rnd to rt_genid (and makes it an atomic_t)
- Adds a new rt_genid field to 'struct rtable' (filling a hole on 64bit)
- Checks entry->rt_genid at appropriate places :
--- Readers have to ignore invalidated entries.
--- Writers can delete invalidated entries.
- Removes rt_flush_timer timer
- Removes unused /proc/sys/net/ipv4/{min_delay,max_delay}

We even reduce size of route.o

# size net/ipv4/route.o
    text    data     bss     dec     hex filename
   20038    1331     160   21529    5419 net/ipv4/route.o.before
   19991    1203     104   21298    5332 net/ipv4/route.o
Quoted 4 lines

Next step will be to audit all rt_cache_flush(0) (aka flushes) users, see if they can be converted to "invalidate the cache" users.

This looks really nice, applied, thanks Eric.