Re: eliminating find's recursion-related stack limitation

[James Youngman]

On Sun, Jan 23, 2005 at 07:40:59PM +0100, Jim Meyering wrote:
> Hi James,
> 
> Have you considered changing GNU find not to use explicit recursion?

Yes, I thought about it when we first discussed it.  It's on the
"wibni" list, but I'm deferring that until after the next "stable"
release, because - as you say - it requires a major change.

> I didn't see it listed in findutils' TODO file.

No, everything in the TODO file has been there since before I was
maintainer of findutils.  Are there any entries in that file that
anybody on the list really thinks would be worthwhile?  

> Currently, a malicious user can easily arrange so that find does not
> process some files: just put them so deep (say 50,000 levels down)
> in a hierarchy that find would blow its stack and segfault before
> getting that far.  Of course, such a deep hierarchy would also disrupt
> periodic updatedb runs, unless someone thinks to limit the depth (e.g.,
> via -maxdepth) of the updatedb-invoked find command.

Yes.  I suppose a watchful system administrator could detect this sort
of thing with

        find / -mindepth 200 -print -prune

The greatest nesting level on my machine here is only 18 levels (not
altogether surprisingly, the most deeply nested files are Java
classes).  A "reasonable" number will vary, I suppose, from system to
system.

> I converted GNU rm, chmod, chown, chgrp, and du from using explicit
> recursion to using stateful iteration via fts.
> ls and cp still remain to be converted, but are less important.
> fts worked well for the latter four, but perhaps find is too demanding.
> Unfortunately, to properly evaluate such a solution seems to require
> doing most of the work of converting the tool to use fts.

Yes.  I'm not unwilling to do the work, it's just that while there are
outstanding bugs, I wanted to fix those and release the fixes.  The
fatal flaw in this plan is that that policy means that we implement
the switch to fts sometime after the end of the Universe.

On a more serious note, I have been toying with the idea that find
could be refactored to more cleanly separate the part which descends
the filesystem from the part which evaluates predicates.  This might
usefully allow the plugging-in of loadable predicates and perhaps
loadable things-to-search (web pages, for example).  There is, of
course, a distinction to be made between "interesting feature" and
"pointless bells and whistles" (for US readers, "chrome").

Regards,
James.