fts: do not exhaust memory when processing million-entry directory

[Jim Meyering]

A few weeks ago, I noticed that removing a directory with very many
entries made rm -rf use an inordinate amount of memory.  I've fixed the
underlying fts module to batch its readdir calls in the common case,
thus to imposing a reasonable ceiling on memory usage.  The ceiling of
~30MB is reached for any directory containing 100,000 or more entries.

The way this change is designed, it induces no semantic change unless
fts processes a directory with 100,000 entries or more, so normal
testing would be unlikely to get good coverage.  In testing, I lowered
the threshold of 100,000 first to 5, and then to 2.  In both cases,
coreutils tools (modified to use this test version of fts) passed
all of their regression tests.

I did the same with find (find.git v4.5.10-93-gd0c939a), but with
 a threshold of just 10.

I mem-profiled that, just for fun and got this:
(find /t/dir > /dev/null vs. 1M files in a tmpfs directory)

    KB
41.88^#               ::                        :
     |#:   :::   :: : : :::::::::::  ::  : ::  ::::::  : ::@:::    ::: :: :::@
     |# :::::::::: :::: : ::: :::::::::::::: ::::::: :@::: @::::::::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
     |# :: ::::: : :::: : ::: :::::: ::: ::: ::::::: :@::: @:::: :::::@::::::@
   0 +----------------------------------------------------------------------->Gi
     0                                                                   4.530

Note that the maximum memory usage was barely 40KB (note, that's K as in kilo)
and it ran for 4.5 Gi.  Note that that is using a ridiculously small test
threshold of just 10.

Compare with find-4.5.9, which consumed over 1GB and required a few
*more* instructions.

    GB
1.043^                  ##
     |                  # :
     |                 :# :::::
     |                ::# :::::::
     |               :::# ::::::::@
     |              ::::# ::::::::@::::
     |              ::::# ::::::::@::: :@
     |            @:::::# ::::::::@::: :@::@
     |           :@:::::# ::::::::@::: :@::@::
     |           :@:::::# ::::::::@::: :@::@:::::
     |          ::@:::::# ::::::::@::: :@::@:::::@::
     |        ::::@:::::# ::::::::@::: :@::@:::::@:::@
     |       :: ::@:::::# ::::::::@::: :@::@:::::@:::@:::
     |       :: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@
     |      ::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@::
     |     :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::
     |   :::::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@::
     |  :: :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@::::
     |  :: :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@:::::@:
     | ::: :::: ::@:::::# ::::::::@::: :@::@:::::@:::@:::::@:::::@:::::@:::
   0 +----------------------------------------------------------------------->Gi
     0                                                                   4.683

While it is tempting to use a much lower-than-100,000 threshold,
realize that doing so has a cost: a saved DIR* pointer (including a
file descriptor) for each level in a hierarchy that has that many entries.

With the default threshold of 100,000, the maximum is under 30MB
and slightly faster than the first run:

    MB
28.27^#
     |#                        ::  :        :            :    :     :
     |#            :  :        : :::      :::     :      :    :     :  :
     |#            :  :        : : :     :: : :   :      :    :     :  :
     |#            :  : ::     : : :     :: : :   :      :    :     :  :   : :
     |#            : :: :      : : :     :: : :   :      :    :     :  : : : :
     |#            : :: :      : : :     :: : :   :      :    :     : :: : : :
     |#        :   : :: :      : : :     :: : :   :      :   ::     : :: : : :
     |#    :   :   : :: :      : : :     :: : :   :      :   :: :   : :: : : :
     |# :  :   :   : :: :     :: : :     :: : : :::      :   :: :   : :: : : :
     |# :  :   :   : :: :     :: : :     :: : : : :      :   :: :   : :: : @ :
     |# :  :   :   : :: :     :: : :   :::: : : : :      :   :: :   @ :::: @ :
     |# ::::   :  :: :: :     :: : :  :: :: : : : :      :   :: :   @ :::: @ :
     |# :: :   :  :: :: :     :: : :  :: :: : : : :      :   :: :   @ :::: @ :
     |# :: :  ::  :: :: :  :: :: : :  :: :: : : : :      : ::::::  :@ :::: @ :
     |# :: :  ::::::::: : ::  :: : :  :: :: : ::: :::::::: : ::::  :@ :::::@ :
     |# :: :::::: ::::: : ::  :: : ::::: :: ::::: ::: : :: : ::::  :@::::::@ :
     |# :: :: ::: ::::::: ::  :: : :: :: :: ::::: ::: : :: : ::::  :@::::::@ :
     |#::: :: ::: ::::::: ::  :: : :: :: :: ::::: ::: : :: : ::::  :@::::::@ :
     |#::: :: ::: ::::::: ::  :: : :: :: :: ::::: ::: : :::: :::::::@::::::@ :
   0 +----------------------------------------------------------------------->Gi
     0                                                                   4.481


Down to business.  The first few patches clean up fts.c, making it
a little more compact and fixing some minor readability/maintainability
issues.

While the logs do contain ChangeLog entries,
there are none in the ChangeLog file.
I'll add those before pushing, which won't be for at
least a day or two.

[PATCH 1/8] maint: fts.c: remove #if-0'd FTS_WHITEOUT code
[PATCH 2/8] maint: fts.c: move __opendir2 #define "up" out of
[PATCH 3/8] maint: fts.c: correct off-by-one indentation
[PATCH 4/8] maint: fts.c (__opendir2): Remove unused parameter,
[PATCH 5/8] maint: fts: give __opendir2 a new parameter
[PATCH 6/8] fts: add/use new struct member, fts_dirp
[PATCH 7/8] fts: move decl of "dp" into while loop; split long line
[PATCH 8/8] fts: do not exhaust memory when processing million-entry