rm -r can be tricked into reporting non-existent cycle

[Jim Meyering]

I wrote:
> 2006-03-10  Jim Meyering  <address@hidden>
>
>       * src/remove.c (AD_pop_and_chdir): Fix a bug whereby a user with
>       write access to a directory being removed could cause the removal
>       of that directory to fail with an erroneous diagnostic about a
>       directory cycle.  Reported by Vineet Chadha.

For those who haven't seen it yet, here's a copy of the original
report and fix:
  http://meyering.net/2006-03-10-rm-bug.txt

It might appear on Gmane's mirror, soon (the number is just a guess):
(the GNU mailman bug-coreutils archive appears to be about 4 days behind)
  http://article.gmane.org/gmane.comp.gnu.core-utils.bugs/6600

In CVS, the code is here:
  http://cvs.savannah.gnu.org/viewcvs/coreutils/src/remove.c?root=coreutils

This newly-exposed cycle-detection weakness means that the gnulib
cycle-check module needs an extension -- a mechanism that's not quite
as ugly as what I did in remove.c.  Having a single function taking
both parent and child dev/inode pairs sounds rather onerous, but maybe
cleanest.  If it ends up being too much trouble or expense, clients like
the fts-cycle module can rely solely on the existing O(depth)-memory
(rather than O(1)) cycle-detection code.

Bear in mind that while this bug may affect even fts-using programs like
chgrp, chown, chmod (but not du, since it uses FTS_TIGHT_CYCLE_CHECK)
that don't modify the hierarchy structure, it's much harder to provoke
the failure when the coprocess must manage to remove a key directory as
well as create lots of new ones.

Technically, even the canonicalize module's use of cycle_check is
susceptible, when traversing symlinks -- and should probably be fixed --
but the typical window is pretty darn small there.  In this case, even
I have doubts about whether it's worth the cost of a full-blown set
(implemented via hash.c) just to detect this highly unlikely failure mode.