Patchwork net: implement emergency route cache rebulds when gc_elasticity is exceeded

login
register
mail settings
Submitter Eric Dumazet
Date Oct. 6, 2008, 10:49 a.m.
Message ID <48E9ED3D.2020005@cosmosbay.com>
Download mbox | patch
Permalink /patch/2896/
State RFC
Delegated to: David Miller
Headers show

Comments

Neil Horman - Oct. 6, 2008, 1:14 p.m.
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

Patch

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;
 }