linux-kernel - Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

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]

Message-ID: <CA+55aFybtRdg=AzcHv3CPm-_wx8LT2_CXaKr4K+i94QSPauZOw@mail.gmail.com>
Date:	Thu, 2 Aug 2012 13:32:41 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Josh Triplett <josh@...htriplett.org>
Cc:	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Sasha Levin <levinsasha928@...il.com>,
	Tejun Heo <tj@...nel.org>, akpm@...ux-foundation.org,
	linux-kernel@...r.kernel.org, linux-mm@...ck.org,
	paul.gortmaker@...driver.com
Subject: Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett <josh@...htriplett.org> wrote:
>
> Sorry, I should clarify what I meant: you'll have a total of one extra
> indirection, not two.

Yes. But the hash table address generation is noticeably bigger and
slower due to the non-fixed size too.

In general, you can basically think of a dynamic hash table as always
having one extra entry in the hash chains. Sure, the base address
*may* cache well, but on the other hand, a smaller static hash table
caches better than a big one, so you lose some and you win some.
According to my numbers, you win a lot more than you lose.

> Does your two-level dcache handle eviction?
>
> Mind posting the WIP patches?

Attached. It's against an older kernel, but I suspect it still applies
cleanly. The patch is certainly simple, but note the warning (you can
*run* it, though - the race is almost entirely theoretical, so you can
get numbers without ever seeing it)

           Linus

Download attachment "patch.diff" of type "application/octet-stream" (6855 bytes)