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: <20120802212140.GC7916@jtriplet-mobl1>
Date:	Thu, 2 Aug 2012 14:21:41 -0700
From:	Josh Triplett <josh@...htriplett.org>
To:	Linus Torvalds <torvalds@...ux-foundation.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 02, 2012 at 01:32:41PM -0700, Linus Torvalds wrote:
> 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.

If you store the size as a precomputed bitmask, that should simplify the
bucket lookup to just a fetch, mask, and offset.  (You shouldn't ever
need the actual number of buckets or the shift except when resizing, so
the bitmask seems like the optimal thing to store.)  With a fixed table
size, I'd expect to see the same code minus the fetch, with an immediate
in the masking instruction.  Did GCC's generated code have worse
differences than an immediate versus a fetched value?

> 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.

Agreed.

I don't think any of this argues against having a second-level cache,
though, and making that one resizable seems sensible.  So, having a
scalable resizable hash table seems orthogonal to having a small
fixed-size hash table as a first-level cache.  I already agree with you
that the hash table API should not make the latter more complex or
expensive to better suit the former; as far as I can tell, address
generation seems like the only issue there.

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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/