netdev - [IPV4] route cache: Introduce rt_genid for smooth cache invalidation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 30 Jan 2008 09:08:56 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	"David S. Miller" <davem@...emloft.net>
CC:	Linux Netdev List <netdev@...r.kernel.org>,
	Robert Olsson <Robert.Olsson@...a.slu.se>
Subject: [IPV4] route cache: Introduce rt_genid for smooth cache invalidation

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.

Signed-off-by: Eric Dumazet <dada1@...mosbay.com>

  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(-)

View attachment "rt_genid.patch" of type "text/plain" (14826 bytes)