netdev - Re: [PATCH] HTB O(1) class lookup

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:	Mon, 5 Feb 2007 12:24:53 +0100
From:	Andi Kleen <ak@...e.de>
To:	Jarek Poplawski <jarkao2@...pl>
Cc:	Simon Lodal <simonl@...knet.dk>, Patrick McHardy <kaber@...sh.net>,
	netdev@...r.kernel.org, lartc@...lman.ds9a.nl
Subject: Re: [PATCH] HTB O(1) class lookup

On Monday 05 February 2007 11:16, Jarek Poplawski wrote:

> 
> Strange - it seems you gave only arguments against this
> analysis...

For a naturally clustered key space (as is common in this case) the two 
level structure is likely more cache efficient than a generic hash function. 
That is because the hash will likely spread out the natural clusters and then require
more cache lines to access them because there will be less sharing.

Ok in theory a very tuned for this case hash function might have similar 
properties, but normally people don't put that much care into 
designing hashes and just use some generic one.

> > And the worst memory consumption case considered by Patrick should
> > be relatively unlikely.
> 
> Anyway, such approach, that most users do something
> this (reasonable) way, doesn't look like good
> programming practice.

In the unlikely worst case they will get half a MB of tables. Hardly a 
show stopper. 

> I wonder, why not try, at least for a while, to do this
> a compile (menuconfig) option with a comment:
> recommended for a large number of classes. After hash
> optimization and some testing, final decisions could be
> made.

There are already far too many obscure CONFIGs. Don't add more.

-Andi

-
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