Re: [PATCH] net: implement emergency route cache rebulds when gc_elasticity is exceeded

[Eric Dumazet <dada1@cosmosbay.com>]

David Miller a écrit :
> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Tue, 30 Sep 2008 08:02:44 +0200
> 
>> 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)