David Miller a écrit :

From: Eric Dumazet <redacted>
Date: Tue, 30 Sep 2008 08:02:44 +0200

quoted

When a machine is targeted by a DDOS attack, about all slots of the
hash table are fully loaded (ie chain length >= elasticity). We dont
need to invalidate the cache, but find an equilibrium, with small
adjustements.

Sure, but it is possible to determine that some hash chains
are unevenly growing out of control compared to others,
and that is the algorithm that Neil is trying to discover.

No problem, but my suggestion to use a separate threshold than elasticity
was apparently not taken into consideration.

I ran an experiment on a big stable machine with 2^19 rtcache slots,
 scanning all chains and found *many* of them having length > elasticity,
maximum being 13. I am sure its allowed by statistics laws.

(average chain length : 3.55)

In order to avoid unecessary cache invalidation, we need some 
calculation from a statistics expert.

Given rt_hash_size and elasticity (or rt_max_size), compute the "maximum reasonable" 
chain length, ie some X number where probability(chain_length < X) > 0.9999

(CCed Evgeniy Polyakov :) )



MemTotal:   32963064 kB
8 CPUS
/proc/sys/net/ipv4/route/max_size:8388608 (default at boot time)
/proc/sys/net/ipv4/route/gc_thresh:2000000
/proc/sys/net/ipv4/route/gc_elasticity:4
/proc/sys/net/ipv4/route/gc_interval:1

Linux version 2.6.24.5
cat /proc/net/sockstat
sockets: used 957514
TCP: inuse 963998 orphan 7100 tw 10393 alloc 964646 mem 376389

rtstat -c5 -i5 (minus first sample)
rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|
 entries|  in_hit|in_slow_|in_slow_|in_no_ro|  in_brd|in_marti|in_marti| out_hit|out_slow|out_slow|gc_total|gc_ignor|gc_goal_|gc_dst_o|in_hlist|out_hlis|
        |        |     tot|      mc|     ute|        |  an_dst|  an_src|        |    _tot|     _mc|        |      ed|    miss| verflow| _search|t_search|

 1862477|   23758|    4400|       0|       0|       0|       0|       0|    4142|    1134|       0|       0|       0|       0|       0|   45754|   11785|
 1863310|   24794|    4504|       0|       0|       0|       0|       0|    4089|    1183|       0|       0|       0|       0|       0|   47558|   11640|
 1863604|   24183|    4383|       0|       0|       0|       0|       0|    3910|    1061|       0|       0|       0|       0|       0|   46002|   10819|
 1864473|   23899|    4510|       0|       0|       0|       0|       0|    4113|    1193|       0|       0|       0|       0|       0|   46451|   11798|

grep ip_dst_cache /proc/slabinfo
ip_dst_cache      1863543 1868660    384   10    1 : tunables    0    0    0 : slabdata 186866 186866      0

On this machine, a single "ip route flush cache" is risky 
(commit 29e75252da20f3ab9e132c68c9aed156b87beae6 [IPV4] route cache: Introduce rt_genid for smooth cache invalidation)
not yet included in kernel)