XFS parent pointers [LWN.net]

XFS parent pointers

Posted May 8, 2018 22:00 UTC (Tue) by Paf (subscriber, #91811)
In reply to: XFS parent pointers by Cyberax
Parent article: XFS parent pointers

Wait, how? And come to think of it, why aren’t those allowed today?

to post comments

XFS parent pointers

Posted May 8, 2018 22:05 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link] (3 responses)

I refer you to a previous discussion: https://lwn.net/Articles/681685/

XFS parent pointers

Posted May 14, 2018 21:10 UTC (Mon) by viro (subscriber, #7872) [Link] (2 responses)

Still no go - you'd need to scan all "ancestor" chains (with all the IO it would imply) and do that while the graph structure is guaranteed not to change under you. Good luck with the locking, or with DoS potential in that...

XFS parent pointers

Posted May 14, 2018 23:16 UTC (Mon) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

Shouldn't all of the parents' dentries already be in RAM, though? Locking will be more complicated, but a parallel "rename stack locking" structure specifically for renames should suffice.

XFS parent pointers

Posted May 14, 2018 23:54 UTC (Mon) by viro (subscriber, #7872) [Link]

Why would they? You've looked up foo/bar/baz and found that oh, BTW, it also has links from a/b/c/d/e/never/been/there/whatever/the/hell/it/might/be and a dozen other directories. Each of those having a bunch of ancestors of its own, etc.

Ancestors are guaranteed to be in dcache when there's only one path from root to it... Even that takes some work to maintain in the face of open_by_handle() - fs/exportfs/expfs.c is where it's dealt with. With multiple paths, that becomes a non-starter; do you really want stat(2) capable of sucking in thousands of directories from disk, all of that - with rename/link/unlink blocked on the entire filesystem? Or doing that already joyful work on a graph that keeps changing under you...

Sure, you could pull *everything* into dcache on mount and keep it there all along. Then everything will be in dcache at all times, but that means memory footprint from hell and hash chains' lengths from the same place. And you still have a potentially enormous graph (remember, you've got everything in dcache) and need to answer questions like "will it remain a connected directed graph if we remove this edge?" and "will adding such an edge create a loop in it?", atomically wrt graph modifications...

XFS parent pointers

Posted May 8, 2018 22:29 UTC (Tue) by nevyn (guest, #33129) [Link] (4 responses)

Answering backwards:

> And come to think of it, why aren’t those allowed today?

Because it's impossible to stop loops. Eg. /tmp/p/c and then you hardlink p into c. gg.
Lots of bad things happen if you do that.

> Wait, how?

Because, in theory, if you have a single "parent" for each directory entry you don't have loops. I'm less sure this solves all the problems though. At best it seems like another way to do mount --bind, at worst you'd have all the same problems.

XFS parent pointers

Posted May 10, 2018 0:32 UTC (Thu) by Paf (subscriber, #91811) [Link]

Thanks nevyn, and cyberax as well.

XFS parent pointers

Posted May 14, 2018 12:55 UTC (Mon) by cortana (subscriber, #24596) [Link] (2 responses)

I believe Mac OS X supports directory hardlinks on HFS+... does anyone know how software that isn't prepared for this behaves if you set up an infinite loop in this way?

XFS parent pointers

Posted May 16, 2018 1:15 UTC (Wed) by foom (subscriber, #14868) [Link]

HFS+'s directory hardlink support doesn't let you make loops. It has a bunch of restrictions which make that impossible, although they also prohibit making some directory hardlinks which _don't_ create a loop. (That's okay, it wasn't intended to be a generally-used feature, only really for Time Machine backups' use.)

See the comment starting "Source parent and" here, for what it actually checks: https://opensource.apple.com/source/hfs/hfs-407.30.1/core...

XFS parent pointers

Posted Jun 8, 2018 23:58 UTC (Fri) by JanC_ (subscriber, #34940) [Link]

You can make directory hardlinks on NTFS too, by doing direct NT kernel API calls, but it's not a good idea to actually do that (I don't think anything in Windows userspace can actually handle that properly).