netdev - Re: [PATCH] net: implement emergency route cache rebulds when gc

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <48E9ED3D.2020005@cosmosbay.com>
Date:	Mon, 06 Oct 2008 12:49:33 +0200
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Neil Horman <nhorman@...driver.com>
Cc:	Bill Fink <billfink@...dspring.com>,
	David Miller <davem@...emloft.net>, netdev@...r.kernel.org,
	kuznet@....inr.ac.ru, pekkas@...core.fi, jmorris@...ei.org,
	yoshfuji@...ux-ipv6.org, kaber@...sh.net,
	Evgeniy Polyakov <johnpol@....mipt.ru>
Subject: Re: [PATCH] net: implement emergency route cache rebulds when	gc_elasticity
 is exceeded

Neil Horman a écrit :
> Hey all-
> 	So, I've been doing some testing here with this patch, and am
> comfortable that the sd estimation is working reasonably well. For a hash table
> with an average chain length of 1, it computes the stadard deviation to be 2,
> which gives us a max chain length of 9 (4*sd + avg), and it manages to do that
> in about 7 jiffies over about 524000 hash buckets.  I'm reasonably pleased with
> that speed I think, and after thinking about it, I like this implementation
> somewhat better, as it doesn't create a window in which chains can be
> artifically overrun (until the nect gc round) (although I'm happy to hear
> arguments against my implementation).  Anywho here it is, comments and thoughts
> welcome!
> 
> Thanks & Regards
> Neil
> 
> Signed-off-by: Neil Horman <nhorman@...driver.com>
> 
> 
>  route.c |  121 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 118 insertions(+), 3 deletions(-)
> 
> 
> diff --git a/net/ipv4/route.c b/net/ipv4/route.c
> index 6ee5354..4f8c5b5 100644
> --- a/net/ipv4/route.c
> +++ b/net/ipv4/route.c
> @@ -145,6 +145,7 @@ static struct dst_entry *ipv4_negative_advice(struct dst_entry *dst);
>  static void		 ipv4_link_failure(struct sk_buff *skb);
>  static void		 ip_rt_update_pmtu(struct dst_entry *dst, u32 mtu);
>  static int rt_garbage_collect(struct dst_ops *ops);
> +static void rt_emergency_hash_rebuild(struct net *net);
>  
>  
>  static struct dst_ops ipv4_dst_ops = {
> @@ -200,7 +201,14 @@ const __u8 ip_tos2prio[16] = {
>  
>  struct rt_hash_bucket {
>  	struct rtable	*chain;
> +	atomic_t	chain_length;
>  };
> +
> +atomic_t rt_hash_total_count;
> +atomic_t rt_hash_nz_count;
> +
> +static int rt_chain_length_max;
> +
>  #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) || \
>  	defined(CONFIG_PROVE_LOCKING)
>  /*
> @@ -601,6 +609,68 @@ static inline int ip_rt_proc_init(void)
>  }
>  #endif /* CONFIG_PROC_FS */
>  
> +static void rt_hash_sd_update(void)
> +{
> +	int temp, i;
> +	unsigned long long sd;
> +	int average = atomic_read(&rt_hash_total_count);
> +	int nzcount = atomic_read(&rt_hash_nz_count);
> +
> +	/*
> + 	 * Don't divide by zero
> + 	 */
> +	if (!nzcount)
> +		return;
> +
> +	average = DIV_ROUND_UP(average, nzcount);
> +
> +	sd = 0;
> +	for (i = 0; i < (1 << rt_hash_log); i++) {
> +		temp = atomic_read(&rt_hash_table[i].chain_length);
> +		/*
> + 		 * Don't count zero entries, as most of the table
> + 		 * will likely be empty.  We don't want to unfairly
> + 		 * bias our average chain length down so far
> + 		 */

Empty chains should be accounted for, or average and standard
deviation are not correct.

> +		if (unlikely(temp))
> +			sd += (temp-average)^2;

Out of curiosity, what do you expect to do here ?

(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 

Anyway, we wont add so many atomic operations and double
hash table size in order to be able to compute sd.

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)


View attachment "avg_sd.patch" of type "text/plain" (2354 bytes)