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? 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@xxxxxxxxxxxxx
