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+55aFwjWBFq75uQzVekv_ZygG9Sejrf2ok-EhvfvSPxhTFzfg@mail.gmail.com>
Date:	Thu, 2 Aug 2012 14:50:18 -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 2:21 PM, Josh Triplett <josh@...htriplett.org> wrote:
>
>  Did GCC's generated code have worse differences than an immediate
>  versus a fetched value?

Oh, *way* worse.

Nobody just masks the low bits. You have more bits than the low bits,
and unless you have some cryptographic hash (seldom) you want to use
them.

So no, it's not just as mask. For the dcache, it's

        hash = hash + (hash >> D_HASHBITS);
        return dentry_hashtable + (hash & D_HASHMASK);

so it's "shift + mask", and the constants mean less register pressure
and fewer latencies. One of the advantages of the L1 dcache code is
that the code gets *so* much simpler that it doesn't need a stack save
area at all, for example.

But as mentioned, the dcache L1 patch had other simplifications than
just the hash calculations, though. It doesn't do any loop over next
fields at all (it falls back to the slow case if it isn't a direct
hit), and it doesn't care about the d_compare() case (they will never
be added to the L1, since looking those things up is so slow that
there's no point). So there are other issues at play than just
avoiding the indirection to fetch base/mask/bitcount things and the
simplified hash calculation.

Not having a loop makes the register lifetimes simpler and again
causes less register pressure.

               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/