Re: make getdents/readdir POSIX compliant wrt mount-point dirent.d_ino

[Jim Meyering]

Ulrich Drepper wrote:

> On Tue, Sep 1, 2009 at 13:19, Theodore Tso<tytso@...> wrote:
>> Furthermore, there are
>> plenty of Unix systems that have received POSIX certifications despite
>> having this behavior.
>
> A common misunderstanding of certification.
>
> Like for all certifications, being POSIX certified doesn't mean the
> certification is valid for all situations.  it only means that there
> is (at least) one configuration which meets the requirements.  In this
> case it means the environment simply uses one single filesystem and no
> mount points.  This way the problem doesn't even arise.
>
>> Fixing it is also going to be decidedly non-trivial since it depends
>> on how the directory was orignally accessed.  [...]
>
> I guess that this is really a difficult way to solve.  I wouldn't want
> to pay for something which is hardly ever really used.
>
> But there are programs out there which would like to use the inode
> uniqueness.  Therefore the next best thing to do is perhaps to return
> a flag in the getdents information (in d_type, perhaps) to indicate
> that this is a mount point and/or that there are multiple ways to
> access the file in question.  Then programs which can use the inode
> information can be watching for this flag and enter the slow path only
> if it's set.

Hi Uli,

Here is another reason to do what you suggest.
This bug report started it:

    on the fly varying device numbers on a NFS mount point
    http://bugzilla.redhat.com/501848

More discussion here:

    http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/18553/focus=18822

The problem is with hierarchy traversals again.  The first time
a mount-point directory is encountered, fts opens it (with openat),
stats it and records dev,ino, and then reads entries.  The first readdir
triggers the automount and thus, the assignment of a new device number
to the already-open directory.  When the traversal process finishes
processing the hierarchy and traverses back "up" to that mount point,
it fails due to the old-st_dev/new-st_dev mismatch.[1]  Normally such
a mismatch indicates that someone is attempting to subvert a traversal,
or perhaps has inadvertently moved a subtree while it's being traversed.
In any case, once such a mismatch has been detected, there is no way
the traversal can safely continue.

One way to accommodate the current automount semantics, is to make fts.c
incur, _for every directory traversed_, the cost of an additional
stat (fstatat, actually) call just in case this happens to be one of
those rare mount points.

I would really rather not pessimize most[*] hierarchy-traversing
command-line tools by up to 17% (though usually far less) in order
to accommodate device-number change semantics that arise
for an automountable directory.

Jim

[*] At least the following GNU tools would be affected: find, chmod,
chown, chgrp, chcon, du, rm, and possibly soon, cp and ls.

[1] Note that if the mounted hierarchy is not too deep (I think it's
4 or 5 levels), cached "active-directory" file descriptors mask the
problem, because when we traverse back to the mount point, we still
have an open file descriptor for that directory.  In that case, we don't
even need to perform the dev/inode comparison.

[Theodore Ts'o-2]

On Wed, Nov 04, 2009 at 08:29:00PM +0100, Jim Meyering wrote:
> One way to accommodate the current automount semantics, is to make fts.c
> incur, _for every directory traversed_, the cost of an additional
> stat (fstatat, actually) call just in case this happens to be one of
> those rare mount points.
>
> I would really rather not pessimize most[*] hierarchy-traversing
> command-line tools by up to 17% (though usually far less) in order
> to accommodate device-number change semantics that arise
> for an automountable directory.

I must be missing something.  How do you come up with the 17% penalty
figure?  And what does this actually mean in real life?

stat() in Linux is fast.  Really fast.  A quick benchmark clocks
stat() on my system at 0.814 *microseconds* in the warm cache case,
and if you're stating a directory that you've traversed, odds are
extremely high that it will still be in the cache.

My entire laptop root filesystem has 53,934 directories, so an extra
stat() per directory translates to an extra 43 milliseconds, assuming
I needed to walk my entire root filesystem.  It's really hard to see
why kernel developers should get worked up into a lather over that
kind of "performance penalty".

Regards,

                                                - Ted

[Jim Meyering]

Theodore Tso wrote:

> On Wed, Nov 04, 2009 at 08:29:00PM +0100, Jim Meyering wrote:
>> One way to accommodate the current automount semantics, is to make fts.c
>> incur, _for every directory traversed_, the cost of an additional
>> stat (fstatat, actually) call just in case this happens to be one of
>> those rare mount points.
>>
>> I would really rather not pessimize most[*] hierarchy-traversing
>> command-line tools by up to 17% (though usually far less) in order
>> to accommodate device-number change semantics that arise
>> for an automountable directory.
>
> I must be missing something.  How do you come up with the 17% penalty
> figure?  And what does this actually mean in real life?

Actually, it can approach 25%.  See below.

> stat() in Linux is fast.  Really fast.

Sure.  But so are chown, rm, du, etc.
And an extra stat can make more than a measurable difference.
On an absolute scale, the difference is not prohibitive,
but wouldn't it be a shame to penalize everyone
for a feature that some of us don't ever use?

> A quick benchmark clocks
> stat() on my system at 0.814 *microseconds* in the warm cache case,
> and if you're stating a directory that you've traversed, odds are
> extremely high that it will still be in the cache.
>
> My entire laptop root filesystem has 53,934 directories, so an extra
> stat() per directory translates to an extra 43 milliseconds, assuming
> I needed to walk my entire root filesystem.  It's really hard to see
> why kernel developers should get worked up into a lather over that
> kind of "performance penalty".

Here's a comparison with fewer than 5000 directories:
Given a directory named z, with 70 subdirs, each containing 70 empty subdirs.
All names are in 0..69.  Hot cache.  On a tmpfs file system.
linux 2.6.31.1-56.fc12.x86_64

Compare chgrp -R applied to "z", with and without the stat-adding patch:

  $ for i in 1 2 3; do for p in prev .; do echo $p; \
    env time $p/chgrp -R group2 z; done; done;
  prev
  0.03user 0.31system 0:00.34elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (0major+235minor)pagefaults 0swaps
  .
  0.02user 0.39system 0:00.42elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (0major+235minor)pagefaults 0swaps
  prev
  0.03user 0.30system 0:00.34elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (0major+235minor)pagefaults 0swaps
  .
  0.04user 0.38system 0:00.43elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (0major+236minor)pagefaults 0swaps
  prev
  0.03user 0.31system 0:00.34elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (0major+236minor)pagefaults 0swaps
  .
  0.04user 0.37system 0:00.41elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (0major+235minor)pagefaults 0swaps

That's a 23.5% performance hit. (42-34)/34

Sure, it's not even 1/10th of a second, but remember this is a tiny
hierarchy, and it's not just chgrp, but also find, rm, du, etc. that
are affected.  And this is not the sole reason to make a change, but
rather one more reason, in addition to the one that started this thread.