[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150916174227.GA11031@openwall.com>
Date: Wed, 16 Sep 2015 20:42:27 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: larger bitmaps and hash tables
On Wed, Sep 16, 2015 at 07:02:37PM +0200, magnum wrote:
> I have committed a patch where params.h defines PH_MASK_6 as
> (PASSWORD_HASH_SIZE_6 - 1), and changed ALL formats to use PH_MASK_6. So
> we could commit this, or something similar if/when desired.
I think we'll be changing all hash table sizes at once, not just the
6th. So maybe you can prepare us for that?
I think we'll obsolete the smallest two sizes, shifting everything else
by two sizes. The new smallest size will be a 4096-bit entry bitmap and
a 1024-entry hash table (with the current SHR=2), which is 8.5 KB total
on a 64-bit system (so is still in L1 cache).
This frees up the highest two sizes for reuse, and I think we may make
them 30 and 32 bits. The latter would exist only in 64-bit builds
unless we increase SHR (maybe we should introduce "magic SHR" on 32-bit,
where an extra 2 or 3 bits would be skipped for the largest sizes).
So we'll have: 12, 16, 20, 24, 27, 30, 32.
30 bits means a 128 MB bitmap followed by a 1 GB (on 32-bit) or 2 GB (on
64-bit) hash table (but maybe Fred will contribute a replacement for the
hash table soon). 128 MB might have non-negligible L3 cache hit rate
(and possibly will fit in L3 cache in a few years), and might fit in
L4/eDRAM cache on CPUs that have that (typically at exactly 128 MB).
32 bits is the maximum we can readily have with many hash types (e.g.,
when the first word of MD5 output is ready), and it also eliminates the
need to mask any bits (just use the 32-bit word directly).
The binary_hash_*() functions will need to be merged into one, accepting
the size in bits (or mask?) The get_hash_*() functions will stay (but
be revised to support these larger sizes).
> BTW we now get some warnings from clang and/or with 32-bit builds.
>
> loader.c:211:18: warning: comparison of unsigned expression >= 0 is
> always true
> [-Wtautological-compare]
> } while (--size >= 0);
> ~~~~~~ ^ ~
> loader.c:212:11: warning: comparison of unsigned expression < 0 is
> always false
> [-Wtautological-compare]
> if (size < 0)
> ~~~~ ^ ~
Oh, we'll need to deal with these now.
Also, that patch was only good up to 31-bit since it kept
password_hash_sizes[] at "unsigned int". Would need to use a 64-bit
type right there to include a 32-bit maximum size, or alternatively
would need to specify masks rather than sizes. (BTW, size_t wouldn't
hold a value of exactly 2^32 on 32-bit.)
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
