Message ID | 48E9ED3D.2020005@cosmosbay.com |
---|---|
State | RFC, archived |
Delegated to: | David Miller |
Headers | show |
On Mon, Oct 06, 2008 at 12:49:33PM +0200, Eric Dumazet wrote: > > Empty chains should be accounted for, or average and standard > deviation are not correct. Fair enough, although for such a large hash table, I would assume that this would unfairly bias our average to zero, although as I think about that, our standard deviation would make up for that. > >> + if (unlikely(temp)) >> + sd += (temp-average)^2; > > Out of curiosity, what do you expect to do here ? > Doh! Show off how stupid I can be apparently. I was doing too much at once, and was thinking exponentiation there, rather than bitwise XOR. My bad. > (temp-average) XOR 2 > or (temp-average) * (temp-average) > > Also, your computations use integer arithmetic. > > If avg = 2.5 and sd = 1.9, avg+4*sd you'll find 6 instead of 10 > Yes, but I think we're going to have to tolerate some error, since we're using integer arithmatic here. > Anyway, we wont add so many atomic operations and double > hash table size in order to be able to compute sd. > That I have to agree with. The growth in size at the very least doesn't look overly acceptible. > If we really want to be smart, we can have a pretty good > estimate of average and sd for free in rt_check_expire() > > Something like this untested patch. (We should make sure > we dont overflow sum2 for example) > > diff --git a/net/ipv4/route.c b/net/ipv4/route.c > index 6ee5354..85182d9 100644 > --- a/net/ipv4/route.c > +++ b/net/ipv4/route.c > @@ -125,6 +125,7 @@ static int ip_rt_redirect_silence __read_mostly = ((HZ / 50) << (9 + 1)); > static int ip_rt_error_cost __read_mostly = HZ; > static int ip_rt_error_burst __read_mostly = 5 * HZ; > static int ip_rt_gc_elasticity __read_mostly = 8; > +static int rt_chain_length_max __read_mostly = 32; > static int ip_rt_mtu_expires __read_mostly = 10 * 60 * HZ; > static int ip_rt_min_pmtu __read_mostly = 512 + 20 + 20; > static int ip_rt_min_advmss __read_mostly = 256; > @@ -748,11 +749,24 @@ static void rt_do_flush(int process_context) > } > } > > +/* > + * While freeing expired entries, we compute average chain length > + * and standard deviation, using fixed-point arithmetic. > + * This to have an estimation of rt_chain_length_max > + * rt_chain_length_max = max(elasticity, AVG + 4*SD) > + * We use 3 bits for frational part, and 29 (or 61) for magnitude. > + */ > + > +#define FRACT_BITS 3 > +#define ONE (1UL << FRACT_BITS) > + > static void rt_check_expire(void) > { > static unsigned int rover; > unsigned int i = rover, goal; > struct rtable *rth, **rthp; > + unsigned long sum = 0, sum2 = 0; > + unsigned long length, samples = 0; > u64 mult; > > mult = ((u64)ip_rt_gc_interval) << rt_hash_log; > @@ -770,8 +784,10 @@ static void rt_check_expire(void) > if (need_resched()) > cond_resched(); > > + samples++; > if (*rthp == NULL) > continue; > + length = 0; > spin_lock_bh(rt_hash_lock_addr(i)); > while ((rth = *rthp) != NULL) { > if (rt_is_expired(rth)) { > @@ -784,11 +800,13 @@ static void rt_check_expire(void) > if (time_before_eq(jiffies, rth->u.dst.expires)) { > tmo >>= 1; > rthp = &rth->u.dst.rt_next; > + length += ONE; > continue; > } > } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) { > tmo >>= 1; > rthp = &rth->u.dst.rt_next; > + length += ONE; > continue; > } > > @@ -797,6 +815,15 @@ static void rt_check_expire(void) > rt_free(rth); > } > spin_unlock_bh(rt_hash_lock_addr(i)); > + sum += length; > + sum2 += length*length; > + } > + if (samples) { > + unsigned long avg = sum / samples; > + unsigned long sd = int_sqrt(sum2 / samples - avg*avg); > + rt_chain_length_max = max_t(unsigned long, > + ip_rt_gc_elasticity, > + (avg + 4*sd) >> FRACT_BITS); Oh! Thats pretty nifty, I hadn't considered breaking the interger up like that to avoid round off error. Although Like computing sd during garbage collection, this method leaves a hole during which the addition of several entries to one chain may provide a false positive before the next run of rt_check_expire. Or is the likelyhood of that low enough that its not particularly relevant? Regards Neil
diff --git a/net/ipv4/route.c b/net/ipv4/route.c index 6ee5354..85182d9 100644 --- a/net/ipv4/route.c +++ b/net/ipv4/route.c @@ -125,6 +125,7 @@ static int ip_rt_redirect_silence __read_mostly = ((HZ / 50) << (9 + 1)); static int ip_rt_error_cost __read_mostly = HZ; static int ip_rt_error_burst __read_mostly = 5 * HZ; static int ip_rt_gc_elasticity __read_mostly = 8; +static int rt_chain_length_max __read_mostly = 32; static int ip_rt_mtu_expires __read_mostly = 10 * 60 * HZ; static int ip_rt_min_pmtu __read_mostly = 512 + 20 + 20; static int ip_rt_min_advmss __read_mostly = 256; @@ -748,11 +749,24 @@ static void rt_do_flush(int process_context) } } +/* + * While freeing expired entries, we compute average chain length + * and standard deviation, using fixed-point arithmetic. + * This to have an estimation of rt_chain_length_max + * rt_chain_length_max = max(elasticity, AVG + 4*SD) + * We use 3 bits for frational part, and 29 (or 61) for magnitude. + */ + +#define FRACT_BITS 3 +#define ONE (1UL << FRACT_BITS) + static void rt_check_expire(void) { static unsigned int rover; unsigned int i = rover, goal; struct rtable *rth, **rthp; + unsigned long sum = 0, sum2 = 0; + unsigned long length, samples = 0; u64 mult; mult = ((u64)ip_rt_gc_interval) << rt_hash_log; @@ -770,8 +784,10 @@ static void rt_check_expire(void) if (need_resched()) cond_resched(); + samples++; if (*rthp == NULL) continue; + length = 0; spin_lock_bh(rt_hash_lock_addr(i)); while ((rth = *rthp) != NULL) { if (rt_is_expired(rth)) { @@ -784,11 +800,13 @@ static void rt_check_expire(void) if (time_before_eq(jiffies, rth->u.dst.expires)) { tmo >>= 1; rthp = &rth->u.dst.rt_next; + length += ONE; continue; } } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) { tmo >>= 1; rthp = &rth->u.dst.rt_next; + length += ONE; continue; } @@ -797,6 +815,15 @@ static void rt_check_expire(void) rt_free(rth); } spin_unlock_bh(rt_hash_lock_addr(i)); + sum += length; + sum2 += length*length; + } + if (samples) { + unsigned long avg = sum / samples; + unsigned long sd = int_sqrt(sum2 / samples - avg*avg); + rt_chain_length_max = max_t(unsigned long, + ip_rt_gc_elasticity, + (avg + 4*sd) >> FRACT_BITS); } rover = i; }