Re: [PATCHSET v10r1d2 00/17] xfs: encode parent pointer name in xattr key

[Dave Chinner <david@fromorbit.com>]

On Mon, Mar 27, 2023 at 06:29:32PM -0700, Darrick J. Wong wrote:
> On Sun, Mar 26, 2023 at 06:21:17AM +0300, Amir Goldstein wrote:
> > On Sat, Mar 25, 2023 at 8:01 PM Darrick J. Wong <djwong@kernel.org> wrote:
> > > On Sat, Mar 25, 2023 at 10:59:16AM +0300, Amir Goldstein wrote:
> > > > On Fri, Mar 24, 2023 at 8:19 PM Allison Henderson
> > > > <allison.henderson@oracle.com> wrote:
> > Right.
> > So how about
> > (parent_ino, parent_gen, dirent_hash) -> (dirent_name)
> > 
> > This is not a breaking change and you won't need to do another
> > breaking change later.
> > 
> > This could also be internal to VLOOKUP: appended vhash to
> > attr name and limit VLOOKUP name size to  255 - vhashsize.
> 
> The original "put the hash in the xattr name" patches did that, but I
> discarded that approach because it increases the size of each parent
> pointer by 4 bytes, and was really easy to make a verrrry slow
> filesystem:

Right, that's because hash collision resolution is very dumb. It's
just a linear walk from start to end comparing the names of each
coliding entry.

> I wrote an xfs_io command to compute lists of names with the same
> dirhash value.  If I created a giant directory with the same file
> hardlinked millions of times where all those dirent names all hash to
> the same value, lookups in the directory gets really slow because the
> dabtree code has to walk (on average) half a million dirents to find the
> matching one.

That's worst case behaviour, not real-world production behaviour.
It's also a dabtree optimisation problem, not a parent pointer
problem. i.e. if this is a real world issue, we need to fix the
dabtree indexing, not work around it in the parent pointer format.

IOWs, optimising the parent pointer structure for the *rare* corner
case of an intentionally crafted dahash btree collision farm is, to
me, the wrong way to design a structure.

Optimising it for the common fast path (single parent xattrs,
followed by small numbers of parents) is what we should be doing,
because that situation will occur an uncountable number of times
more frequently than this theorectical worst case behaviour. i.e.
the worst case will, in all likelihood, never happen in production
environments - behaviour in this circumstance is only a
consideration for mitigating malicious attacks.

And, quite frankly, nobody is going to bother attacking a filesystem
this way - there is literally nothing that can be gained from
slowing down access to a single directory in this manner. It's a DOS
at best, but there are *much* easier ways of doing that and it
doesn't require parent pointers or dahash collisions at all.


> 
> There were also millions of parent pointer xattrs, all with the same
> attr name and hence the same hash value here too.  Doing that made the
> performance totally awful.  Changing the hash to crc32c and then sha512
> made it much harder to induce collision slowdowns on both ends like
> that, though sha512 added a noticeable performance hit for what it was
> preventing.

So why not change the dahash for parent pointer enabled filesystems
to use crc32c everywhere?

I'd much prefer we have a parent pointer index key that is fixed
length, has constant hash time and a dabtree hash that is far more
resilient to collision farming than to have to perform
encoding/decoding of varaible length values into the key to work
around a collision-rich hashing algorithm.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com