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: <9ff2e09c-57e4-455e-8614-1b3b17b652f4@email.android.com>
Date:	Thu, 19 Apr 2012 11:55:00 -0700
From:	"H. Peter Anvin" <hpa@...or.com>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
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

Either way I suggest picking up David's presorting patchset since it is already done and use its infrastructure for any further improvements.

As far as a linear probe you get an average of n lookups with a packing density of 1-1/n so you are right; a linear probe with a density of say 1/2 is probably best.

Linus Torvalds <torvalds@...ux-foundation.org> wrote:

>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

-- 
Sent from my mobile phone. Please excuse brevity and lack of formatting.
--
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/