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

From: Eric Dumazet <[email-masked]>
Date: Thu, 02 Oct 2008 16:20:52 +0200

Eric Dumazet a écrit :
> Eric Dumazet a écrit :
>> Bill Fink a écrit :
>>> I believe the general rule of thumb for something like this is at
>>> least two standard deviations.  For a normal distribution, one standard
>>> deviation covers about 68 % of the sample universe, while two standard
>>> deviations covers about 95 % (three standard deviations covers 99.73 %).
>>> See the Wikipedia entry:
>>>
>>>     http://en.wikipedia.org/wiki/Standard_deviation
>>>
>>
>> Thanks Bill for the pointer, this is the trick.
>>
>> I believe we should target "4σ 99.993666% " case.
>>
>> But we dont need to really compute Standard deviation at runtime, only 
>> find an (upper) approximation of it.
>>
>> For elasticity=4 and 512*1024 samples (mean < 4), I guess 4σ can be 
>> approximated by 20 or something.
>>
> 
> Good estimation of Standard Deviation could be computed for free
> in rt_check_expire(). (each runs scans 20% of hash table with default 
> tunables timeout & ip_rt_gc_interval)
> 
> We could update 4σ estimation in this function, every minute 
> (ip_rt_gc_interval)
> 
> At softirq time we then can detect a particular hash chain is
> longer than 4σ estimation and trigger an appropriate action.
> 
> This action is to : flush table, and while we do that, expand hash table
> if its current size is under ip_rt_max_size/elasticity...
> 

I ran again my litle dirty program that reads /proc/kcore to explore rt
hash table on a busy server and found :

hptr=0xffff81082ec00000 hsize=524288
total=2299242 dst entries
4306 chains of length 0
23807 chains of length 1
60119 chains of length 2
95112 chains of length 3
106364 chains of length 4
92307 chains of length 5
65743 chains of length 6
39710 chains of length 7
20997 chains of length 8
15775 chains of length 9
39 chains of length 10
7 chains of length 11
2 chains of length 12

avg = 4.38546
sd = 1.94614
X = avg + 4*sd = 12.17

I tried various elasticity settings and found litle variations of X

This is because lot of entries are in use (refcnt>1) and can
not be freed, regardless of elasticity.