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: Windows password security audit tool. GUI, reports in PDF.

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

Date:	Thu, 2 Oct 2008 11:13:58 +0400
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	David Miller <davem@...emloft.net>, nhorman@...driver.com,
	netdev@...r.kernel.org, kuznet@....inr.ac.ru, pekkas@...core.fi,
	jmorris@...ei.org, yoshfuji@...ux-ipv6.org, kaber@...sh.net
Subject: Re: [PATCH] net: implement emergency route cache rebulds when gc_elasticity is exceeded

Hi.

On Tue, Sep 30, 2008 at 07:16:50PM +0200, Eric Dumazet (dada1@...mosbay.com) wrote:
> 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 :) )

:)

If it is a hash table with fixed size, and hash is being produced like
some function result modulo size of the table, then there will be always
fluctuations with longer chain lenghts than 'usual', since, for example,
hash function produces result in 2^32 field, which hash table size is
only 2^20 or something smaller than maxiumum hash result. When I
analyzed Jenkin's hash I mistakenly concluded that such pikes are result
of the hash distribution itself and not final modulo operation.

Plus, it is always a gaussian distribution, so there will be (although
depending on parameters amount may be small enough) entries with longer
and smaller than average chains.

I tested list walking speed compared to rb-tree and trie on p4 machines
without prefetch and lists with upto 10 element are processed faster
than anything else, so if your average chain lengths are less than 10
elements, you are in a good condition.

Also I have a tricky algorithm to automatically scale RCU protected hash
table (with additional overhead at scale time though, but I believe it
is not a problem), which just waits to be implemented in netchannels, so
long chain length problem can be fixed, if algorithm works. Ok, I've
finished my advertisement rants :)

-- 
	Evgeniy Polyakov
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html