linux-kernel - Re: [v4 1/1] mm: Adaptive hash table scaling

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 22 May 2017 15:38:34 +0200
From:   Michal Hocko <mhocko@...nel.org>
To:     Pasha Tatashin <pasha.tatashin@...cle.com>
Cc:     akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
        linux-mm@...ck.org, Michael Ellerman <mpe@...erman.id.au>
Subject: Re: [v4 1/1] mm: Adaptive hash table scaling

On Mon 22-05-17 09:18:58, Pasha Tatashin wrote:
> >
> >I have only noticed this email today because my incoming emails stopped
> >syncing since Friday. But this is _definitely_ not the right approachh.
> >64G for 32b systems is _way_ off. We have only ~1G for the kernel. I've
> >already proposed scaling up to 32M for 32b systems and Andi seems to be
> >suggesting the same. So can we fold or apply the following instead?
> 
> Hi Michal,
> 
> Thank you for your suggestion. I will update the patch.
> 
> 64G base for 32bit systems is not meant to be ever used, as the adaptive
> scaling for 32bit system is just not needed. 32M and 64G are going to be
> exactly the same on such systems.
> 
> Here is theoretical limit for the max hash size of entries (dentry cache
> example):
> 
> size of bucket: sizeof(struct hlist_bl_head) = 4 bytes
> numentries:  (1 << 32) / PAGE_SIZE  = 1048576 (for 4K pages)
> hash size: 4b * 1048576 = 4M
> 
> In practice it is going to be an order smaller, as number of kernel pages is
> less then (1<<32).

I haven't double check your math but if the above is correct then I
would just go and disable the adaptive scaling for 32b altogether. More
on that below.

> However, I will apply your suggestions as there seems to be a problem of
> overflowing in comparing ul vs. ull as reported by Michael Ellerman, and
> having a large base on 32bit systems will solve this issue. I will revert
> back to "ul" all the quantities.

Yeah, that is just calling for troubles.
 
> Another approach is to make it a 64 bit only macro like this:
> 
> #if __BITS_PER_LONG > 32
> 
> #define ADAPT_SCALE_BASE     (64ull << 30)
> #define ADAPT_SCALE_SHIFT    2
> #define ADAPT_SCALE_NPAGES   (ADAPT_SCALE_BASE >> PAGE_SHIFT)
> 
> #define adapt_scale(high_limit, numentries, scalep)
>       if (!(high_limit)) {                                    \
>               unsigned long adapt;                            \
>               for (adapt = ADAPT_SCALE_NPAGES; adapt <        \
>                    (numentries); adapt <<= ADAPT_SCALE_SHIFT) \
>                       (*(scalep))++;                          \
>       }
> #else
> #define adapt_scale(high_limit, numentries scalep)
> #endif

This is just too ugly to live, really. If we do not need adaptive
scaling then just make it #if __BITS_PER_LONG around the code. I would
be fine with this. A big fat warning explaining why this is 64b only
would be appropriate.

-- 
Michal Hocko
SUSE Labs