Date: Sat, 28 Oct 2006 19:50:28 GMT From: Bruce Evans <bde@zeta.org.au> To: freebsd-bugs@FreeBSD.org Subject: Re: bin/104458: fts(3) can't handle very deep trees Message-ID: <200610281950.k9SJoSho076294@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
The following reply was made to PR bin/104458; it has been noted by GNATS.
From: Bruce Evans <bde@zeta.org.au>
To: Yar Tikhiy <yar@comp.chem.msu.su>
Cc:
Subject: Re: bin/104458: fts(3) can't handle very deep trees
Date: Mon, 16 Oct 2006 22:53:40 +1000 (EST)
>> Description:
>
> Utilities using fts(3), find(1) and rm(1) being among them,
> fail to handle a directory tree so deep that a path in it is
> longer than ~49-50K.
ISTR that POSIX requires at least rm and cp to work with any depth that
can occur in theory, and QOI of course requires any utility that
traverses trees to work with any possiible depth that occurs in practice.
cp ensures brokeness using FTS_NOCHDIR, but this bug is missing in cp.
This was easy to debug. fts has a bogus USHRT_MAX limit on path lengths
in FTSENT. It normally fails at about 50K because it keeps doubling
the length and 2*50K is the first doubling to above 64K. FTS only
has a limit of INT_MAX. These limits are well documented in the source.
>> How-To-Repeat:
>
> 1. Create a long chain of subdirectories using the script
> attached. Each subdir name will be "000...". The overall
> structure will be 000*/000*/000*/000*/...
> This is better done on a scratch mfs because the
> resulting chain will be hard to delete using stock tools.
I used /compat/linux/bin/cp. It just worked :-(. /compat/linux/usr/bin/du
also just worked, while du just failed. I debugged using du.
FTSENT has quite a few shorts. ISTR a discussion about one of them
not being large enough for use as a cookie, but don't remember the
path length one being noticed as a limit before. It also has a
limit of 64K on the number of levels. This can easily be reached.
It also has some INT_MAX limits. These are not easy to reach yet.
Implementing the POSIX requirement to work for any tree is an
interesting problem. The program cannot use any stacks or counters,
since no stack or counter can be large enough. However, a counter
with 640K of bits should be large enough for anyone in practice.
A stack of parent directories can easily overflow in practice. In
particular, ".." must be used to traverse back since a stack of
fd's to fchdir() back to would hit the {OPEN_MAX} limit very easily.
fts(3) seems to handle this right (it doesn't keep directories open).
ft's most fundamental limit seems to be the INT_MAX one on path
lengths. For some reason, it wants to construct a full path. That
feature should probably just be turned off for deep paths, or always
as an option, since it is impossible to use paths longer than
{PATH_MAX} and often only the path relative to a subdir is needed/
Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200610281950.k9SJoSho076294>