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.