bin/104458: fts(3) can't handle very deep trees

[Bruce Evans]

The following reply was made to PR bin/104458; it has been noted by GNATS.

From: Bruce Evans <bde at zeta.org.au>
To: Yar Tikhiy <yar at 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