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.
|
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.
|
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.
|
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.
|
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.)
|
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.
|
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.
|
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.
|
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?
|
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)
|
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?
|
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
$
|
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.
|
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.
|