On Wed, Mar 29, 2023 at 09:29:59AM +1100, Dave Chinner wrote: > 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@xxxxxxxxxx> 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@xxxxxxxxxx> 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? That's not difficult to do, but it'll break name obscuring in metadump unless you know of a quick way to derive B from A and maintain crc32c(A) == crc32c(B). Granted I had mostly written off name obscuring in metadump on parent pointer filesystems anyway. > 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. Wellllll I was 10 minutes away from sending v11 with all of my changes integrated, but I guess now I'll go rework the dabtree to use crc32c, encode the crc32c in the parent pointer attr name, and get rid of all the variable length value decoding. Now that I just got rid of all the intermediate patches with hash-in-attr-name. Let's see if I can hammer that out in the next 15 minutes. --D > Cheers, > > Dave. > -- > Dave Chinner > david@xxxxxxxxxxxxx
