linux-kernel - Re: [GIT PULL] Please pull NFS client changes for Linux 5.18

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:   Wed, 30 Mar 2022 22:22:52 +0000
From:   Trond Myklebust <trondmy@...merspace.com>
To:     "torvalds@...ux-foundation.org" <torvalds@...ux-foundation.org>
CC:     "linux-nfs@...r.kernel.org" <linux-nfs@...r.kernel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [GIT PULL] Please pull NFS client changes for Linux 5.18

On Wed, 2022-03-30 at 16:01 -0400, Trond Myklebust wrote:
> On Wed, 2022-03-30 at 11:17 -0700, Linus Torvalds wrote:
> > On Tue, Mar 29, 2022 at 12:36 PM Trond Myklebust
> > <trondmy@...merspace.com> wrote:
> > > 
> > > - Readdir fixes to improve cacheability of large directories when
> > > there
> > >   are multiple readers and writers.
> > 
> > So I only took a look at this part now. I've obviously already
> > pulled
> > it, but that use of 'xxhash()' just made me go "Whaaa?"
> > 
> > It's claimed that it's used because of its extreme performance, but
> > the performance numbers come from using it as a block hash.
> > 
> > That's not what nfs does.
> > 
> > The nfs code just does
> > 
> >     xxhash(&cookie, sizeof(cookie), 0) & NFS_READDIR_COOKIE_MASK;
> > 
> > where that "cookie" is just a 64-bit entity. And then it masks off
> > everything but 18 bits.
> > 
> > Is that *really* appropriate use of a new hash function?
> > 
> > Why is this not just doing
> > 
> >   #include <hash.h>
> > 
> >   hash_64(cookie, 18);
> > 
> > which is a lot more obvious than xxhash().
> > 
> > If there really are some serious problems with the perfectly
> > standard
> > hash() functionality, I think you should document them.
> > 
> > Because just randomly picking xxhash() without explaining _why_ you
> > can't just use the same simple thing we use elsewhere is very odd.
> > 
> > Or rather, when the only documentation is "performance", then I
> > think
> > the regular "hash_64()" is the obvious and trivial choice.
> > 
> >                   Linus
> 
> My main worry was that hash_64() would have too many collisions.
> Since
> this is using cuckoo nesting, that would be a problem.
> 
> I did some quick studies after I got your email, and it seems as if
> my
> concerns were unfounded. I've tested both a linear index and a sample
> of ext4 getdents offsets.
> While the sample of ext4 offsets did show a larger number of
> collisions
> than a simple linear index, it wasn't too terrible (3 collisions in a
> sample of 9000 entries).

Actually, let me correct that.

With 9175 ext4 offsets, I see 157 collisions (== hash buckets with > 1
entry). So hash_64() does perform less well when you're hashing a value
that is already a hash.

> The linear index showed no collisions up to about 100000 entries.

This is unchanged, so with XFS and btrfs as the exported filesystems,
we should not have a problem.

> 
> So, I'd be OK with changing to hash_64() and will queue up a bugfix
> for
> it. I should have done this study earlier...
> 

-- 
Trond Myklebust
Linux NFS client maintainer, Hammerspace
trond.myklebust@...merspace.com