linux-kernel - Re: [PATCH 3/3] x86, extable: Handle early exceptions

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+55aFxhY1Ug5esj==Sm=o1Epg+NFnvFs74syqRxbYDbPQJEFA@mail.gmail.com>
Date:	Thu, 19 Apr 2012 11:25:17 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	Borislav Petkov <bp@...64.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...nel.org>,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [PATCH 3/3] x86, extable: Handle early exceptions

On Thu, Apr 19, 2012 at 10:59 AM, H. Peter Anvin <hpa@...or.com> wrote:
>
> I would argue that the O(1) hash makes things simpler as there is no
> need to deal with collisions at all.

Most of the O(1) hashes I have seen more than made up for the trivial
complexity of a few linear lookups by making the hash function way
more complicated.

A linear probe with a step of one really is pretty simple. Sure, you
might want to make the initial hash "good enough" to not often hit the
probing code, but doing a few linear probes is cheap.

In contrast, the perfect linear hashes do crazy things like having
table lookups *JUST TO COMPUTE THE HASH*.

Which is f*cking stupid, really. They'll miss in the cache just at
hash compute time, never mind at hash lookup. The table-driven
versions look beautiful in microbenchmarks that have the tables in the
L1 cache, but for something like the exception handling, I can
guarantee that *nothing* is in L1, and probably not even L2.

So what you want is:
 - no table lookups for hashing
 - simple code (ie a normal "a multiply and a shift/mask or two") to
keep the I$ footprint down too
 - you *will* take a cache miss on the actual hash table lookup, that
cannot be avoided, but linear probing at least hopefully keeps it to
that single cache miss even if you have to do a probe or two.

Remember: this is very much a "cold-cache behavior matters" case. We
would never ever call this in a loop, at most we have loads that get a
fair amount of exceptions (but will go through the exception code, so
the L1 is probably blown even then).

                         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/