Security fix for remove_dir_all may have introduced a regression how filesystem loops are handled

[the8472]

Normally traversing very deep directory trees (e.g. created by bind mounts or FUSE) will result in ENAMETOOLONG or ELOOP.
The fix in #93110, #93112 and #93111 switches to using -at syscalls and keeping file descriptors for each child directory that's being descended into. But this way we loose loop detection (as far as I can tell), which means the process will run out of stack space or file descriptors instead of returning a proper error.

#88731 was already open which does contain proper loop handling.

[hkratz]

As I wrote in the PR in my opinion there should be no loops. Bind mounts on Linux and directory hardlinks (available for Macos only) are not allowed to loop and we are not descending into symlinked dirs because we open them with openat(..., O_NOFOLLOW).

But of course running out of file descriptors is currently a problem. I have a follow-up draft branch ready which fixes that differently from #88731 (going up using openat(dirf, "..", O_NOFOLLOW) + inode comparison going back up because using iterated openat() turned out to be to slow for very deep directories. With this PR I can delete one million nested dirs in 16 seconds just like "rm -r".

[hkratz]

I would love to merge that with your work somehow so we don't run into conflicts or one of us incorporates the work of the other. Either way is fine for me.

I will open the draft PR tomorrow so you can have a look and then we can decide on how to proceed.

[the8472]

But of course running out of file descriptors is currently a problem. I have a follow-up draft branch ready which fixes that differently from #88731 (going up using openat(dirf, "..", O_NOFOLLOW) + inode comparison going back up because using iterated openat() turned out to be to slow for very deep directories.

My approach is keeping a fixed-size stack of some directory fds open so it go back up and recurse into siblings most of the time and only has to re-walk path occasionally. Using .. + a fallback does seem less complex though.
But I also use a loop instead of recursion to avoid stack overflows which means I have to mutably update some stuff which does make the code more gnarly.

[the8472]

I have tried to reproduce loops with bind mounts and overlayfs and it looks I cannot. That leaves the possibility of FUSE or maybe mounted network filesystems containing them, which should make this an even smaller edge-case.

[hkratz]

I am using an iterative version too (@cuviper did the first conversion). I added the fixed deque inspired by your work and then replaced the iterated openat() for reopening fds that have fallen out of the cache when going back up with openat(dirf, "..", O_NOFOLLOW). Because with the iterated openat() it took much, much longer in the adversarial case of just very deeply (1<<20) nested directories. It is essentially quadratic in fs operations in the depth with a fixed fd cache because going back up every size-of-cache times you have to refill the cache.

[hkratz]

A HashSet with visited inodes or (device, inode) pairs could easily be added for cycle detection.

[the8472]

I assume there's still a fallback in case the .. case fails? That'll need deep path handling. But it sounds like your followup PR should cover most issues already that I had in mind and it also applies to more platforms. I can implement the long path handling on top of that instead.

[hkratz]

Currently there is no fallback for going back up via .., though I still have the code working in a previous commit and could incorporate it. In what scenarios do you expect that to fail? Bind mounts?

[the8472]

A parent directory getting moved while we're somewhere deeper in the tree, then it won't match the original parent.

[hkratz]

Ah OK. If the inode comparison fails my current implementation returns an error, just as with many other concurrent modification races (added files/directories at the right time cause ENOTEMPTY going up, deleted files/directories cause ENOENT on openat() or unlinkat()).

[the8472]

Good point, if it gets moved then unlinking would fail anyway after we go back up. Then a fallback isn't necessary.

[cuviper]

which means the process will run out of stack space or file descriptors instead of returning a proper error.

Running out of file descriptors should result in a proper error with EMFILE. Running out of stack is unfortunately a crash/abort, but we found that with default process limits, FDs should run out first.