bugfindutils - Bugs: bug #23443, cycle detection in ftsfind yields...

 
 

bug #23443: cycle detection in ftsfind yields false positives on some filesystems with imperfect POSIX compliance

Submitter:  Juergen Weigert <jnweiger>
Submitted:  Sat 31 May 2008 12:09:26 PM UTC
   
 
Category:  find Severity:  3 - Normal
Item Group:  Wrong result Status:  None
Privacy:  Public Assigned to:  jay
Originator Name:  Open/Closed:  Open
Release:  4.4.0 Fixed Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 06 Sep 2008 10:46:25 AM UTC, comment #13: 

That sounds useful.   In fact the non-POSIX-semantics detection could also be useful, perhaps in a module form, for figuring out if we can trust st_nlink on directories as well.    We might need a bitmap for an answer (i.e. one bit per POSIX-like behaviour) though.

 James Youngman <jay>
Group administrator
Sat 06 Sep 2008 10:33:22 AM UTC, comment #12: 

I've realized there's a better way to do this. When the current code detects a loop (looking solely at dev/ino), call fstatvfs to determine the type of the current file system, and if it's of a type that may exhibit non-POSIX semantics, perform a more-involved test as outlined below.  Otherwise, continue as currently done and report the cycle.

While the current cycle-checking code is efficient even for very deep trees, once we've found a potential cycle, there's little down-side to using the classic (inefficient-in-general) approach of examining each parent FTSENT in succession, looking for a match.  Each FTSENT does have stat information, so comparing other st_* members is easy and requires no additional memory.

 Jim Meyering <meyering>
Sat 06 Sep 2008 09:39:22 AM UTC, comment #11: 

If we save additional information from stuct stat as potentially disambiguating information, we run the risk of (more) false negatives.   For example while we are searching /a/b/c/d something could concurrently modify /a/b, changing its mtime, ctime, size, mode, number of links, uid, gid, and in extreme cases also block count.   The only things I can see in struct stat that would not change are the file-type fields in st_mode (that is, S_ISDIR would still be true) and probably st_blksize (which is likely not disambiguating anyway). 

We could also try to qualify possible false positives by checking st_dev and st_ino on the directory containing the potential ancestor in the loop.  There are a number of possible problems with this (poor performance and possible problems with FTS_LOGICAL).  I suppose this also slightly changes the side effects of "mv /a/b/c/d /a", though I guess in the worst case the new parent would make us traverse the cycle one more time before becoming sure there is a cycle.   That would mean in our case that we would return FTS_D for some things for which we should return FTS_DC.

James Youngman <jay>
Group administrator
Fri 05 Sep 2008 02:25:51 PM UTC, comment #10: 

Hi James.

Actually, yes.
Whereas the gnulib-fts cycle checks only device and inode numbers (because that's all it needs to do on POSIX-conforming file system), some tools resort to comparing additional members of struct stat.  For example diff has an option you can enable (configure-time?) to make it perform extra checks of several other members.  Note how the comparison in comment #5 shows size, link count and block count fields differ, even though dev/inode match.

Unfortunately, testing those fields would mean storing them, and currently we don't store an entire 144-byte stat field, but rather just dev+inode for the cycle check.  We'll have to weigh the cost/benefit of encumbering the code (that will impact all users) to accommodate a non-POSIX file system.

 Jim Meyering <meyering>
Thu 04 Sep 2008 09:23:53 PM UTC, comment #9: 

Jim, can you see any way to work around the fts cycle detection problem outlined in comment #5?     I can't right now, but I thought I'd ask you before marking the problem as non-fixable.

(it amounts to, is there any evidence we could use to avoid a false positive in cycle detection for directories that genuinely share the same block device number and inode number?    I can't think of a way which would still be POSIX-compliant.)

James Youngman <jay>
Group administrator
Mon 02 Jun 2008 09:18:33 PM UTC, comment #8: 

bingo.
I now officially love findutils-4.4.0/find/oldfind :-)

I was able to trigger bad behaviour with
findutils-4.4.0/find/find twice. oldfind was always correct.

It also complains about the loop. It says:
findutils-4.4.0/find/oldfind: Filesystem loop detected; `/suse/jw/.snapshot/hourly.2' has the same device number and inode as a directory which is 1 level higher in the file system hierarchy

.. but it continues correctly.

 Juergen Weigert <jnweiger>
Mon 02 Jun 2008 11:17:07 AM UTC, comment #7: 

I'd missed the significance of the 4.3.0/4.3.1 change, thanks for pointing it out again.

The differences between 4.3.0 and 4.3.1 were very substantial, which unfortunately makes pinpointing the cause quite difficult. 

However, one possibility if the fact that in 4.3.1 find now defailts to using fts() to descend the filesystem hierarchy rather than the old built-in recursive method.   The 4.3.1 source tarball (and later releases up to and including 4.5.0) builds two find binaries.  One of them is "find" and the other is wither "newfind" or "oldfind" dependng on whether fts was selected as the default or not (as of 4.3.1, fts is the default, you can see "FTS" in the output of find--version). 

So it would be helpful if you could perform this test with "oldfind" (though you may need to download the source from alpha.gnu.org and build it).  That would narrow down the possibilities a lot.

James Youngman <jay>
Group administrator
Mon 02 Jun 2008 10:52:59 AM UTC, comment #6: 

Thanks for the Review.
I am not challenging posix compliance. A sound cycle detection is of top priority.

My impression is, that up to including 4.3.1 find had a cycle detection that did not give me this kind of false positives.
My suggestion is to go back and review the changes
between 4.3.1 and 4.3.2
I'd like to subdivide the patchset in smaller chunks and
apply/revert them one by one, until I see where the behaviour changed. If such subdividing is possible.

Thanks for the netapp hint. I'll check with our IS&T, if hiding .snapshot is an option. It also causes other issues.

 Juergen Weigert <jnweiger>
Mon 02 Jun 2008 10:27:23 AM UTC, comment #5: 

Editing the full output you gave:-

# stat /suse/jw/.snapshot/hourly.0 /suse/jw/.snapshot
  File: `/suse/jw/.snapshot/hourly.0'
  Size: 28672           Blocks: 56         IO Block: 8192   directory
Device: 1bh/27d Inode: 67          Links: 75

  File: `/suse/jw/.snapshot'
  Size: 4096            Blocks: 8          IO Block: 8192   directory
Device: 1bh/27d Inode: 67          Links: 5

POSIX requires find implementation to detect filesystem loops (e.g. cases where are hard link to a parent or grandparent directory exists).   That's a POSIX requirement.  I guess the thinking behind that is to avoid non-terminating searches.  Anyway, as far as I understand it, POSIX also requires that a single device/inode pair should uniquely identify a file.    GNU findutils uses a list of 'ancestor' dev/inode numbers to figure out if it's seen this directory before in order to detect such loops.  That should be sufficient to prevent false negatives (i.e. being inside a loop without realising). 

However, in this case we have a false positive (there is no loop but find thinks there is).  I can't right now think of any change that will remove this false positive without exposing us to the risk of a false negative.   If we can find a way of fixing this problem without risking non-POSIX-compliance, I'm happy to do it.   But no approach seems obvious to me right now. 

NetApp filers have a directory layout similar to the one you seem to have, but I think they generally avoid this problem by ensuring that ".snapshot" is not returned by readdir(3) even though it is possible to stat that directory, chdir into it, and so forth.   That generally seems like a workable solution.   However, it looks like readdir is returning ".snapshot" in your case.  Maybe you're not on a NetApp filer, just something that looks a bit similar. 

Anyway, to summarise, the wrong thing does seem to be happening here, but I can't think of a way to work around the problem without sacrificing POSIX compliance.   Any suggestions?


James Youngman <jay>
Group administrator
Sun 01 Jun 2008 08:03:17 PM UTC, comment #4: 

All tests today done with find-4.4.0
Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS() CBO(level=0)


-noloaf makes no difference.
Trying with different -maxdepth <n> settings makes a strange difference, as it caused the issue to disappear, thus ending my tests.

Tests done as root, who is an unprivileged user with regard to these nfs filesystems.

I found, that identical device/inode pairs exist under different mountpoints.

find today complained about a filesystem loop.
stat showed that my ~/.snapshot/hourly.0 has the same dev/ino pair as its parent, but different contents ... I admit, this is insane.
Should this cause sufficient confusion for find to skip directories that have a different dev/ino pair?

Typescript attached.

(file #15776)

 Juergen Weigert <jnweiger>
Sun 01 Jun 2008 12:38:23 AM UTC, comment #3: 

Somethign I forgot to ask was does it make a difference if you give the "-noleaf" option?

 James Youngman <jay>
Group administrator
Sat 31 May 2008 11:29:14 PM UTC, comment #2: 

I meant to say 4.3.1 and 4.3.2 instead of 3.9.x
(looked at too many different packages meanwhile, sorry)

Currently I can no longer reproduce the issue.
I have found that when it is reproducable, it is consistently reproducable for some time, then suddenly all is well again.
Thereafter I need to wait several hours.

This is todays typescript (I'll retry tomorrow with
stat(1) first):

$ find . -maxdepth 3 -name weg
./.snapshot/hourly.0/weg
$ # broken ....

$ ls -ld weg
drwxr-xr-x 6 jw suse 4096 May 16 16:30 weg
$

$ find . -name weg
./.snapshot/hourly.0/weg
./.snapshot/hourly.1/weg
./.snapshot/hourly.2/weg
./weg
$ # okay, ....???

$ find . -maxdepth 3 -name weg
./.snapshot/hourly.0/weg
./.snapshot/hourly.1/weg
./.snapshot/hourly.2/weg
./weg
$ # sigh, lost it ...

$ stat weg .snapshot/*/weg
  File: `weg'
  Size: 4096            Blocks: 8          IO Block: 8192   directory
Device: 17h/23d Inode: 31712587    Links: 6
Access: (0755/drwxr-xr-x)  Uid: (10668/      jw)   Gid: (   50/    suse)
Access: 2008-06-01 00:45:51.714820000 +0200
Modify: 2008-05-16 16:30:04.488067000 +0200
Change: 2008-05-16 16:30:04.488067000 +0200
  File: `.snapshot/hourly.0/weg'
  Size: 4096            Blocks: 8          IO Block: 8192   directory
Device: 1ch/28d Inode: 31712587    Links: 6
Access: (0755/drwxr-xr-x)  Uid: (10668/      jw)   Gid: (   50/    suse)
Access: 2008-05-31 17:00:14.877621000 +0200
Modify: 2008-05-16 16:30:04.488067000 +0200
Change: 2008-05-16 16:30:04.488067000 +0200
  File: `.snapshot/hourly.1/weg'
  Size: 4096            Blocks: 8          IO Block: 8192   directory
Device: 1dh/29d Inode: 31712587    Links: 6
Access: (0755/drwxr-xr-x)  Uid: (10668/      jw)   Gid: (   50/    suse)
Access: 2008-05-31 12:00:15.823078000 +0200
Modify: 2008-05-16 16:30:04.488067000 +0200
Change: 2008-05-16 16:30:04.488067000 +0200
  File: `.snapshot/hourly.2/weg'
  Size: 4096            Blocks: 8          IO Block: 8192   directory
Device: 1eh/30d Inode: 31712587    Links: 6
Access: (0755/drwxr-xr-x)  Uid: (10668/      jw)   Gid: (   50/    suse)
Access: 2008-05-30 17:00:20.870448000 +0200
Modify: 2008-05-16 16:30:04.488067000 +0200
Change: 2008-05-16 16:30:04.488067000 +0200
$

Juergen Weigert <jnweiger>
Sat 31 May 2008 07:16:24 PM UTC, comment #1: 

Please double-check those release numbers.  There was never any findutils-3.9.x.

As for the problem itself pleae post the stat(1) output for two files that find believes are on the same filesystem, but which are actually not.

James Youngman <jay>
Group administrator
Sat 31 May 2008 12:09:26 PM UTC, original submission:  

$ find $HOME -name somedir -print

reports nothing, alhough

$ ls -l $HOME/somedir

shows the directory.

This is reproducable on an nfs-mounted $HOME which
has a backup server mounted under $HOME/.snapshot
The $HOME/.snapshot server uses the same inode numbers as
used by the $HOME server.

findutils-3.9.1 and before were unaffected.
findutils-3.9.2 and later are.

https://bugzilla.novell.com/show_bug.cgi?id=393294
suggests that find became more vulnerable to issues with the filesystems.

If guided, I will go in smaller steps from 3.9.1 to 3.9.2 in order to zoom in on the change that causes this regression.

Juergen Weigert <jnweiger>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #15776:  typescript added by jnweiger (8KiB - text/plain)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by meyering (Posted a comment)
  • -email is unavailable- added by jay
  • -email is unavailable- added by jay (Posted a comment)
  • -email is unavailable- added by jnweiger (Submitted the item)
  • -email is unavailable- added by jnweiger

    •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 8 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-04-12 jay Summarycycle detection in ftsfind yields false positives on some filesystems with imperect POSIX compliance cycle detection in ftsfind yields false positives on some filesystems with imperfect POSIX compliance
    2008-09-06 jay Summaryfind regression: now fooled when crossing mountpoints cycle detection in ftsfind yields false positives on some filesystems with imperect POSIX compliance
    2008-09-04 jay Carbon-Copy- Added jim meyering <jim@meyering.net>
    2008-06-02 jay CategoryNone find
        Item GroupNone Wrong result
        Assigned toNone jay
    2008-06-01 jnweiger Attached File- Added typescript, #15776
    2008-05-31 jnweiger Carbon-Copy- Added -email is unavailable-

    Back to the top

    Copyright © 2024 Free Software Foundation, Inc.
    Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
    The Levitating, Meditating, Flute-playing Gnu logo is a GNU GPL'ed image provided by the Nevrax Design Team.
    Page source code

    Powered by Savane 3.14-f13d.
    Corresponding source code