Re: [PATCH] fstests: generic: Add test of seek in directories

Re: [PATCH] fstests: generic: Add test of seek in directories

[Christoph Hellwig]

Please include the mainling list for the file system you think is
buggy or at least odd.  Done now.

On Fri, Aug 28, 2026 at 09:36:10AM +1000, NeilBrown wrote:
> The test then reads the directory to find the order of the stable name,
> which should never change. It also find the "d_off" of all names.
> These d_off should be usable as a "seek" offset to find at least all
> the stable names that came after that point in the original listing.
> 
> After creating the names and finding the order, a loop which repeatly:
>   - makes random changes to unstable names
>   - checks the complete order of stable names in a new readdir
>   - checks what appears after a seek() to a randomly chosen offet
> 
> In Linux 7.2 this test always passes for xfs and ext4 but fails
> for btrfs unless we suppress renames with a "stable" name as target.
> It also fails for tmpfs.

There is no requirement where the entry for a renamed entry is placed.
Posix requires telldir/seekdir to provide a stable cookie, but how
that cookie behaves when the directory is modified is completely
undefined.  The same is true for NFS which requires basically the
same, but more stateless than local telldir/seekdir.

Re: [PATCH] fstests: generic: Add test of seek in directories

[Christoph Hellwig]

On Fri, Aug 28, 2026 at 09:12:41PM +1000, NeilBrown wrote:
> If you happened to know the sizes of the all the names in the directory,
> you could make a sequence of getdents calls which each return precisely
> 1 entry,  You could then use lseek to determine the seek offset at every
> point.

No, you can't.  Despite the historic naming d_off is not an offset, but
a cookie.  You can not arithmetics on it.

> Linux getdents64 makes this a bit simpler by returning exactly that same
> number (the seek offset to the next name) in the d_off field.
> 
> So posix certainly allows, indirectly, seeking to each d_off.

Posix and Linux allow to seekdir to each cookie returned from telldir,
it does not allow to do arithmetics on it.

> 
> Posix refers to one directory entry "immediately following" another
> which clearly implies a well defined sequence (if you exclude names
> added and removed during the read).

I think you're talking about posix_getdents here, which isn't really
Posix as we know it, but was added in the 2024 edition without actually
having relevant implementation so far.  It does however implement
the syscall-level API in most modern Unixes.  It does not mention
d_off at all, just the lseek-able file offset, though.

> I think a strong argument for Linux needing something is that NFS needs
> working directory offsets to be able to support READDIR, because there
> is no "OPEN" request for directories.

I don't think anyone disputes the need for stable directory offsets,
and we should (*knock on wood*) have implementation of native
file systems that fail this.

What the test tries to force is a specific behavior for rename onto
existing file names, replacing the original file name entry with
a new one of the same name.  The test expects that to reuse the
previous d_off, which is not required by any real or de facto standard.

> I know less about btrfs.  It appears to always add new names to the end
> of the directory listing.  When you rename over an existing name, that
> existing name is relocated to the end.  I can only guess why it might do
> that.  I have no idea if it "needs" to do that.

btrfs doesn't manage freespace for the d_off space (doing so is quite
complicated and requires a lot of code in XFS for example), so it
simply uses a monotonically increasing counter for the value reported
in d_off.  This simplifies things a lot, and should work well on 64-bit
systems were you are basically impossible to round out of d_off values.
It might be a lot more problematic on 32-bit systems because the
seekdir/telldir cookie is a long and not a guaranteed 64-bit value.

> Fun fact: This behaviour of btrfs (which I think is perfectly defensible
> for new names) resulted in generic/736 (which I think is an unreasonable
> test to impose) which btrfs "fixed" with a mechanism that doesn't work
> over NFS.  i.e.  it doesn't work if you close and re-open the file for
> each getdents call.
> If I mount a btrfs filesystem over nfs with rsize=4096, then generic/736
> fails.

That code and the tests looks a bit questionable, as readdir by
definition can't every complete in other file systems either if you add
new entries faster than the pace of readdir calls.  I.e. if you replace
the rename there with link calls adding new entries you run into the
same issue with every file system.

> The link you provided says:
>   If a sequence of calls to posix_getdents() is made that reads from
>   offset zero to end-of-file and a file is removed from or added to the
>   directory between the first and last of those calls, whether the
>   sequence of calls returns an entry for that file is unspecified. 
> 
> which unfortunately doesn't cover what happens when a file is renamed.
> When renamed to a non-existing name, it might be reasonable to describe
> this as "removed from" and "added to" so its appearance could be
> unspecified.
> When renamed to an existing name, I don't think it reasonable to
> describe the target name a being either "removed from" or "added to" the
> directory.

If we are talking about files, it is very clear that the target over
which is renamed is removed from the directory.  And if the source
was outside the directory it also is very clearly added.  The only
gray area is a source file that already was in the same directory.

Re: [PATCH] fstests: generic: Add test of seek in directories

[NeilBrown]

On Mon, 31 Aug 2026, Christoph Hellwig wrote:
> Please include the mainling list for the file system you think is
> buggy or at least odd.  Done now.

Thanks.

> 
> On Fri, Aug 28, 2026 at 09:36:10AM +1000, NeilBrown wrote:
> > The test then reads the directory to find the order of the stable name,
> > which should never change. It also find the "d_off" of all names.
> > These d_off should be usable as a "seek" offset to find at least all
> > the stable names that came after that point in the original listing.
> > 
> > After creating the names and finding the order, a loop which repeatly:
> >   - makes random changes to unstable names
> >   - checks the complete order of stable names in a new readdir
> >   - checks what appears after a seek() to a randomly chosen offet
> > 
> > In Linux 7.2 this test always passes for xfs and ext4 but fails
> > for btrfs unless we suppress renames with a "stable" name as target.
> > It also fails for tmpfs.
> 
> There is no requirement where the entry for a renamed entry is placed.
> Posix requires telldir/seekdir to provide a stable cookie, but how
> that cookie behaves when the directory is modified is completely
> undefined.  The same is true for NFS which requires basically the
> same, but more stateless than local telldir/seekdir.
> 
> 

I don't think the behaviour is "completely" undefined in the face of
change.

https://pubs.opengroup.org/onlinepubs/007908799/xsh/readdir.html

says the directory stream represents "all the directory entries in a
particular directory" and makes exceptions:

  If a file is removed from or added to the directory after the most
  recent call to opendir() or rewinddir(), whether a subsequent call to
  readdir() returns an entry for that file is unspecified. 

so "all" doesn't need to includes things that were added or removed.
Does a rename over an existing file "add" or "remove"?
It depends on how you understand "file".

We are told "Directory entries represent files" so we need to understand
"files" in that context.
If we considered "file" to mean "filesystem object", then the above
would allow readdir to ignore multiple hard-links to a file reporting
only one of them.  Hopefully we all agree that would be wrong.

So I think "file" in this context must mean "name" (that is the main
part of a "directory entry").

So, when we rename over an existing name, is that name added or removed?
I think not. It is critical to rename(2) that the replacement is atomic.

With btrfs at present, if a name is the target of a rename while a
readdir is happening, that name might not be reported.  This is because
btrfs iterate_shared deliberately skips any names that are "new" since
the start of the readdir, and it considers a name replaced in a rename
as "new".  I think this is incorrect behaviour and could be harmful.

Prior to 
Commit: 9b378f6ad48c ("btrfs: fix infinite directory reads")

btrfs could report the target of a rename twice in a readdir listing
(but always at least once).
While I think the duplication is unnecessary it is harder to criticise.

NeilBrown

Re: [PATCH] fstests: generic: Add test of seek in directories

[NeilBrown]

On Mon, 31 Aug 2026, Christoph Hellwig wrote:
> On Fri, Aug 28, 2026 at 09:12:41PM +1000, NeilBrown wrote:
> > If you happened to know the sizes of the all the names in the directory,
> > you could make a sequence of getdents calls which each return precisely
> > 1 entry,  You could then use lseek to determine the seek offset at every
> > point.
> 
> No, you can't.  Despite the historic naming d_off is not an offset, but
> a cookie.  You can not arithmetics on it.
> 
> > Linux getdents64 makes this a bit simpler by returning exactly that same
> > number (the seek offset to the next name) in the d_off field.
> > 
> > So posix certainly allows, indirectly, seeking to each d_off.
> 
> Posix and Linux allow to seekdir to each cookie returned from telldir,
> it does not allow to do arithmetics on it.

I agree. No arithmetic, but seek is allowed.
The cookies should all be unique across a single readdir pass, and none
of them may be zero as d_off is a seek address *after* the current name,
and the seek address zero is *before* all names.

> 
> > 
> > Posix refers to one directory entry "immediately following" another
> > which clearly implies a well defined sequence (if you exclude names
> > added and removed during the read).
> 
> I think you're talking about posix_getdents here, which isn't really
> Posix as we know it, but was added in the 2024 edition without actually
> having relevant implementation so far.  It does however implement
> the syscall-level API in most modern Unixes.  It does not mention
> d_off at all, just the lseek-able file offset, though.

The d_off provided by Linux is precisely a seek-address with a
granularity of one name, rather than a granularity of one getdents call.
This is implicit in the VFS implementation.

> 
> > I think a strong argument for Linux needing something is that NFS needs
> > working directory offsets to be able to support READDIR, because there
> > is no "OPEN" request for directories.
> 
> I don't think anyone disputes the need for stable directory offsets,
> and we should (*knock on wood*) have implementation of native
> file systems that fail this.

"should not" ??

> 
> What the test tries to force is a specific behavior for rename onto
> existing file names, replacing the original file name entry with
> a new one of the same name.  The test expects that to reuse the
> previous d_off, which is not required by any real or de facto standard.

That's debatable.  The documents that I have found don't mention rename.
Does that mean anything goes, or do that mean it doesn't get an
exemption from the general rule that all names must be listed?

> 
> > I know less about btrfs.  It appears to always add new names to the end
> > of the directory listing.  When you rename over an existing name, that
> > existing name is relocated to the end.  I can only guess why it might do
> > that.  I have no idea if it "needs" to do that.
> 
> btrfs doesn't manage freespace for the d_off space (doing so is quite
> complicated and requires a lot of code in XFS for example), so it
> simply uses a monotonically increasing counter for the value reported
> in d_off.  This simplifies things a lot, and should work well on 64-bit
> systems were you are basically impossible to round out of d_off values.
> It might be a lot more problematic on 32-bit systems because the
> seekdir/telldir cookie is a long and not a guaranteed 64-bit value.

I think that always allocating the next unused number when adding a name
to a directory is perfectly reasonable when 64bit seek addressing is
available.  The only question is on whether a replacing rename involves
"adding a name".

> 
> > Fun fact: This behaviour of btrfs (which I think is perfectly defensible
> > for new names) resulted in generic/736 (which I think is an unreasonable
> > test to impose) which btrfs "fixed" with a mechanism that doesn't work
> > over NFS.  i.e.  it doesn't work if you close and re-open the file for
> > each getdents call.
> > If I mount a btrfs filesystem over nfs with rsize=4096, then generic/736
> > fails.
> 
> That code and the tests looks a bit questionable, as readdir by
> definition can't every complete in other file systems either if you add
> new entries faster than the pace of readdir calls.  I.e. if you replace
> the rename there with link calls adding new entries you run into the
> same issue with every file system.

According to
  https://www.spinics.net/lists/linux-btrfs/msg138653.html
this seem to come from
  https://github.com/landley/toybox/issues/306
which suggests that

  toybox find testdir -type f -print0 | xargs -0 -n1 sed -i s/a/b/ 

runs forever on btrfs.  Certainly this is unexpected behaviour.  Should
it be fixed in the filesystem or in toybox/find?

I can understand toybox wanting to be as simple as possible.  But
readdir() doesn't make any promises about terminating.

I wouldn't object to btrfs "fixing" this by never reporting new names
except that:
 1/ the interaction with rename/replace is problematic
 2/ the current fix doesn't work over NFS.

I think the rename issue can be fixed by simply reusing the existing
offset when reusing a name.  I might try a patch if a find some time.

I think a fix to make it work over NFS would be to report the entries in
reverse order - most recently added to least recently added.  This would
effectively encode the timestamp (last_index) in the seek cookie instead
of in btrfs_file_private.
Changing how the seek-cookie is interpreted could cause a hiccup
for an NFS client which was in the middle of a READDIR when a server
we reboot to a new verion of btrfs, but that is likely not significant.

Note that
  https://pubs.opengroup.org/onlinepubs/9799919799/functions/posix_getdents.html

uses the word "incremented" in 

  the directory entry immediately following the last entry whose
  information was returned

but I don't think anyone seems interested in that detail.

> 
> > The link you provided says:
> >   If a sequence of calls to posix_getdents() is made that reads from
> >   offset zero to end-of-file and a file is removed from or added to the
> >   directory between the first and last of those calls, whether the
> >   sequence of calls returns an entry for that file is unspecified. 
> > 
> > which unfortunately doesn't cover what happens when a file is renamed.
> > When renamed to a non-existing name, it might be reasonable to describe
> > this as "removed from" and "added to" so its appearance could be
> > unspecified.
> > When renamed to an existing name, I don't think it reasonable to
> > describe the target name a being either "removed from" or "added to" the
> > directory.
> 
> If we are talking about files, it is very clear that the target over
> which is renamed is removed from the directory.  And if the source
> was outside the directory it also is very clearly added.  The only
> gray area is a source file that already was in the same directory.
> 
> 

As I explained in another email, I don't think it is reasonable to
interpret "files" as mentioned in the documentation as "inodes" but only
as "names".  I think the text is sloppy and should be more explicit but
if you uniformly assume "file" to mean "filesystem object" is doesn't
make sense.

Thanks,
NeilBrown

Re: [PATCH] fstests: generic: Add test of seek in directories

[Christoph Hellwig]

On Tue, Sep 01, 2026 at 08:47:58AM +1000, NeilBrown wrote:
> > Posix requires telldir/seekdir to provide a stable cookie, but how
> > that cookie behaves when the directory is modified is completely
> > undefined.  The same is true for NFS which requires basically the
> > same, but more stateless than local telldir/seekdir.
> 
> I don't think the behaviour is "completely" undefined in the face of
> change.
> 
> https://pubs.opengroup.org/onlinepubs/007908799/xsh/readdir.html
> 
> says the directory stream represents "all the directory entries in a
> particular directory" and makes exceptions:
> 
>   If a file is removed from or added to the directory after the most
>   recent call to opendir() or rewinddir(), whether a subsequent call to
>   readdir() returns an entry for that file is unspecified. 
> 
> so "all" doesn't need to includes things that were added or removed.
> Does a rename over an existing file "add" or "remove"?
> It depends on how you understand "file".
> 
> We are told "Directory entries represent files" so we need to understand
> "files" in that context.
> If we considered "file" to mean "filesystem object", then the above
> would allow readdir to ignore multiple hard-links to a file reporting
> only one of them.  Hopefully we all agree that would be wrong.
> 
> So I think "file" in this context must mean "name" (that is the main
> part of a "directory entry").

It does not.  Posix very precisely uses "directory entry" when referring
to directory entries, and files refer to what is an inode in Linux.
This is very clear in the rename documentation:

    The rename() function shall change the name of a file. The old
    argument points to the pathname of the file to be renamed. The new
    argument points to the new pathname of the file.
    If the new argument does not resolve to an existing directory
    entry...

https://pubs.opengroup.org/onlinepubs/9799919799/functions/rename.html

> So, when we rename over an existing name, is that name added or removed?
> I think not. It is critical to rename(2) that the replacement is atomic.

The directory entry for the old file is removed, and the directory entry
for the file is added in one atomic transaction.

> With btrfs at present, if a name is the target of a rename while a
> readdir is happening, that name might not be reported.  This is because
> btrfs iterate_shared deliberately skips any names that are "new" since
> the start of the readdir, and it considers a name replaced in a rename
> as "new".  I think this is incorrect behaviour and could be harmful.
> 
> Prior to 
> Commit: 9b378f6ad48c ("btrfs: fix infinite directory reads")
> 
> btrfs could report the target of a rename twice in a readdir listing
> (but always at least once).
> While I think the duplication is unnecessary it is harder to criticise.

I'm in agreement here.

Re: [PATCH] fstests: generic: Add test of seek in directories

[Christoph Hellwig]

On Tue, Sep 01, 2026 at 11:05:35AM +1000, NeilBrown wrote:
> > > I think a strong argument for Linux needing something is that NFS needs
> > > working directory offsets to be able to support READDIR, because there
> > > is no "OPEN" request for directories.
> > 
> > I don't think anyone disputes the need for stable directory offsets,
> > and we should (*knock on wood*) have implementation of native
> > file systems that fail this.
> 
> "should not" ??

Yes.

> > What the test tries to force is a specific behavior for rename onto
> > existing file names, replacing the original file name entry with
> > a new one of the same name.  The test expects that to reuse the
> > previous d_off, which is not required by any real or de facto standard.
> 
> That's debatable.  The documents that I have found don't mention rename.
> Does that mean anything goes, or do that mean it doesn't get an
> exemption from the general rule that all names must be listed?

The Posix definition of rename is very explicit that the old directory
entry shall be removed:

    Otherwise, if the directory entry named by new exists, it shall be
    removed and old renamed to new. In this case, a directory entry named
    new shall remain visible to other threads throughout the renaming
    operation and refer either to the file referred to by new or old
    before the operation began.

So the previous directory entry for "new" shall be removed.  If a
file system reuses the same d_off for the renamed file, it just created
a new entry that happens to instantly reuse the d_off in the same atomic
operation.

> I think a fix to make it work over NFS would be to report the entries in
> reverse order - most recently added to least recently added.  This would
> effectively encode the timestamp (last_index) in the seek cookie instead
> of in btrfs_file_private.
> Changing how the seek-cookie is interpreted could cause a hiccup
> for an NFS client which was in the middle of a READDIR when a server
> we reboot to a new verion of btrfs, but that is likely not significant.
> 
> Note that
>   https://pubs.opengroup.org/onlinepubs/9799919799/functions/posix_getdents.html
> 
> uses the word "incremented" in 
> 
>   the directory entry immediately following the last entry whose
>   information was returned
> 
> but I don't think anyone seems interested in that detail.

I would suggest to ignore posix_getdents or the whole Issue 8 base spec,
as unlike previous versions I did not try to document and norm existing
behavior, but instead comes up with it's own things.  If we need a
justification we should look at historic Linux and Unix behaviors and
older Posix specs that haven't drifted away from the purpose as much
as the current one.