readdir() and moving directories

[Robert_Krten1]

I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
I’m 99% certain of this, just want to confirm.

For example, I cannot do this:

0 .
1 …
2 a
3 b
4 c

“rm b”

0 .
1 …
2 a
3 c

and instead I must do this:

0 .
1 …
2 a
3
4 c

while an opendir() is in effect, right?

Just trying to track down a bug…

Thanks in advance,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Igor_Kovalenko2]

You’re supposed to do rewinddir() to refresh the state if you think it might
have changed.
– igor

“Robert Krten” <nospam83@parse.com> wrote in message
news:aun2ve$bd1$1@inn.qnx.com…

I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
I’m 99% certain of this, just want to confirm.

For example, I cannot do this:

0 .
1 …
2 a
3 b
4 c

“rm b”

0 .
1 …
2 a
3 c

and instead I must do this:

0 .
1 …
2 a
3 <not used
4 c

while an opendir() is in effect, right?

Just trying to track down a bug… >

Thanks in advance,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at > www.parse.com> .
Email my initials at parse dot com.

[John_Garvey1]

Robert Krten <nospam83@parse.com> wrote:

I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?

No reason to not do so, although POSIX states that whether or
not a file created/deleted from a directory which has an open
directory stream appears or not is unspecified (5.1.2.2). As
Igor says, if you (a client, not the server) modify the contents
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …

[Robert_Krten1]

John Garvey <jgarvey@qnx.com> wrote:

Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?

No reason to not do so, although POSIX states that whether or
not a file created/deleted from a directory which has an open
directory stream appears or not is unspecified (5.1.2.2). As
Igor says, if you (a client, not the server) modify the contents
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …

Huh. In that case, rm -rfv is broken When I stopped moving stuff
around in directories, rm -rfv worked; when I was moving stuff around,
it claimed “directory not empty”…

Cheers,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Robert_Krten1]

Igor Kovalenko <kovalenko@attbi.com> wrote:

You’re supposed to do rewinddir() to refresh the state if you think it might
have changed.

Ok, thanks – as I’ve told John in the other thread, I therefore think
in that case that rm -rfv is broken That’s what caused my grief,
and not moving directory entries around fixed it.

Cheers,
-RK

– igor

“Robert Krten” <> nospam83@parse.com> > wrote in message
news:aun2ve$bd1$> 1@inn.qnx.com> …
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
I’m 99% certain of this, just want to confirm.

For example, I cannot do this:

0 .
1 …
2 a
3 b
4 c

“rm b”

0 .
1 …
2 a
3 c

and instead I must do this:

0 .
1 …
2 a
3 <not used
4 c

while an opendir() is in effect, right?

Just trying to track down a bug… >

Thanks in advance,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at > www.parse.com> .
Email my initials at parse dot com.

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Wojtek_Lerch1]

Robert Krten <nospam83@parse.com> wrote:

John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?

No reason to not do so, although POSIX states that whether or
not a file created/deleted from a directory which has an open
directory stream appears or not is unspecified (5.1.2.2). As
Igor says, if you (a client, not the server) modify the contents
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …

Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
around in directories, rm -rfv worked; when I was moving stuff around,
it claimed “directory not empty”…

In your example, “c” was neither created nor deleted, so it’s your
responsibility to make sure that readdir() reports it. The easiest way
may be by never moving stuff around, but that doesn’t mean it’s the only
way…

[Robert_Krten1]

Wojtek Lerch <wojtek_l@yahoo.ca> wrote:

Robert Krten <> nospam83@parse.com> > wrote:
John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?

No reason to not do so, although POSIX states that whether or
not a file created/deleted from a directory which has an open
directory stream appears or not is unspecified (5.1.2.2). As
Igor says, if you (a client, not the server) modify the contents
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …

Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
around in directories, rm -rfv worked; when I was moving stuff around,
it claimed “directory not empty”…

In your example, “c” was neither created nor deleted, so it’s your
responsibility to make sure that readdir() reports it. The easiest way
may be by never moving stuff around, but that doesn’t mean it’s the only
way…

Ok, but that gets complicated 'cuz I now have to keep track of all the
users of a directory to see how far they’ve read and only make changes on
stuff that they haven’t read you – if I wanted, for example, to keep all
my directory entries sorted that would be problematic…

I think I’ll just do the placeholder-for-deleted-entries stuff – that
seems to work fine for now…

Cheers,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Wojtek_Lerch1]

Robert Krten <nospam83@parse.com> wrote:

Wojtek Lerch <> wojtek_l@yahoo.ca> > wrote:
…
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
…
In your example, “c” was neither created nor deleted, so it’s your
responsibility to make sure that readdir() reports it. The easiest way
may be by never moving stuff around, but that doesn’t mean it’s the only
way…

Ok, but that gets complicated 'cuz I now have to keep track of all the
users of a directory to see how far they’ve read and only make changes on
stuff that they haven’t read you – if I wanted, for example, to keep all
my directory entries sorted > > that would be problematic…

You could take a complete snapshot of the directory when someone calls
opendir(), and feed it in pieces to their readdir() calls.

I think I’ll just do the placeholder-for-deleted-entries stuff – that
seems to work fine for now…

Sure; that’s how filesystems work, and that’s what POSIX is modelled
after, right?

If you keep track of how many readers you have, you can remove the
placeholders on the last closedir(). And if someone deletes a file
while you know there’s no readers, you don’t have to create a
placeholder.

[Robert_Krten1]

Wojtek Lerch <wojtek_l@yahoo.ca> wrote:

Robert Krten <> nospam83@parse.com> > wrote:
Wojtek Lerch <> wojtek_l@yahoo.ca> > wrote:
…
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
…
In your example, “c” was neither created nor deleted, so it’s your
responsibility to make sure that readdir() reports it. The easiest way
may be by never moving stuff around, but that doesn’t mean it’s the only
way…

Ok, but that gets complicated 'cuz I now have to keep track of all the
users of a directory to see how far they’ve read and only make changes on
stuff that they haven’t read you – if I wanted, for example, to keep all
my directory entries sorted > > that would be problematic…

You could take a complete snapshot of the directory when someone calls
opendir(), and feed it in pieces to their readdir() calls.

OMG! Now that’s a DOS attack waiting to happen
I’ll be avoiding that, as directories are unbounded in size

I think I’ll just do the placeholder-for-deleted-entries stuff – that
seems to work fine for now…

Sure; that’s how filesystems work, and that’s what POSIX is modelled
after, right?

That’s how some filesystems work, yes…

If you keep track of how many readers you have, you can remove the
placeholders on the last closedir(). And if someone deletes a file
while you know there’s no readers, you don’t have to create a
placeholder.

I was thinking of a “cleanup” thread that would run around at low
priority optimizing things, but… I’ll prolly avoid that in the
short term as well.
There is one optimization I do already, which is to clean out entries
starting at the end – if you delete a whack of entries, and then (finally)
delete the last entry, the directory will collapse to no longer take into
account the FINAL deleted components.

Cheers,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Wojtek_Lerch1]

Robert Krten <nospam83@parse.com> wrote:

Wojtek Lerch <> wojtek_l@yahoo.ca> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
Wojtek Lerch <> wojtek_l@yahoo.ca> > wrote:
…
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
…
In your example, “c” was neither created nor deleted, so it’s your
responsibility to make sure that readdir() reports it. The easiest way
may be by never moving stuff around, but that doesn’t mean it’s the only
way…

Ok, but that gets complicated 'cuz I now have to keep track of all the
users of a directory to see how far they’ve read and only make changes on
stuff that they haven’t read you – if I wanted, for example, to keep all
my directory entries sorted > > that would be problematic…

You could take a complete snapshot of the directory when someone calls
opendir(), and feed it in pieces to their readdir() calls.

OMG! Now that’s a DOS attack waiting to happen >
I’ll be avoiding that, as directories are unbounded in size >

Is allowing directories to be unbounded in size so much less of a
potential DOS attack?..

Seriously, I didn’t say that was the best way – my intention was to
demonstrate that there’s a simple way to do it even if you want to keep
your directories sorted. There are other possible ways of organizing
your data structures that would let you do it much cheaper, but most of
them are more complicated and depend on details of whether you actually
want to keep the entries sorted or just move a file when a file is
deleted, or maybe something else.

…

If you keep track of how many readers you have, you can remove the
placeholders on the last closedir(). And if someone deletes a file
while you know there’s no readers, you don’t have to create a
placeholder.

I was thinking of a “cleanup” thread that would run around at low
priority optimizing things, but… I’ll prolly avoid that in the
short term as well.

But having it in a separate thread wouldn’t make it any simpler, would
it? The only thing it could buy you is that if a higher-priority thread
deletes a bunch of files, it might sometimes prevent you from optimizing
the directory multiple times.

[John_Garvey1]

Robert Krten <nospam83@parse.com> wrote:

John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …
Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
around in directories, rm -rfv worked; when I was moving stuff around,
it claimed “directory not empty”…

Hmm, looks like “rm -r” does not rewinddir(), and is thus broken
(since the disk filesystems effectively do not shuffle things
around and just mark as “unused” it would appear to work for them).
I’ll raise a PR for the utility guys on “rm” …

[John_Garvey1]

John Garvey <jgarvey@qnx.com> wrote:

Robert Krten <> nospam83@parse.com> > wrote:
Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
Hmm, looks like “rm -r” does not rewinddir(), and is thus broken
I’ll raise a PR for the utility guys on “rm” …

FYI, PR/14477. Note that you have to require multiple readdir()s
to show up the missed items, so either your a/b/c example was
abbreviated too much, or you have a horribly inefficient readdir
implementation (you get given a 2k buffer to populate with as many
directory contents as can fit, not just 1-at-a-time) …

[Robert_Krten1]

John Garvey <jgarvey@qnx.com> wrote:

John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
Hmm, looks like “rm -r” does not rewinddir(), and is thus broken
I’ll raise a PR for the utility guys on “rm” …

FYI, PR/14477. Note that you have to require multiple readdir()s
to show up the missed items, so either your a/b/c example was
abbreviated too much, or you have a horribly inefficient readdir
implementation (you get given a 2k buffer to populate with as many
directory contents as can fit, not just 1-at-a-time) … >

Thanks John.

The example was abbreviated – I do indeed fill as much of the 2k buffer
as I possibly can. In the failing testcase, the directory had hundreds
of entries, with the deleted entry always being replaced by the
last entry to allow for easy “next free” allocation.

Cheers,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Wojtek_Lerch1]

John Garvey <jgarvey@qnx.com> wrote:

Robert Krten <> nospam83@parse.com> > wrote:
John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …
Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
around in directories, rm -rfv worked; when I was moving stuff around,
it claimed “directory not empty”…

Hmm, looks like “rm -r” does not rewinddir(), and is thus broken
(since the disk filesystems effectively do not shuffle things
around and just mark as “unused” it would appear to work for them).
I’ll raise a PR for the utility guys on “rm” …

I don’t think rm should be required to do rewinddir(). POSIX doesn’t
say that the behaviour of readdir() is completely unspecified if a file
is deleted or added; the only thing that’s unspecified is whether
readdir() returns an entry FOR THE DELETED OR ADDED FILE. This doesn’t
give readdir() a licence to skip over any other files. In particular,
if you only remove files that readdir() has already returned (like rm -r
does), readdir() MUST RETURN ALL FILES.

Or am I missing something?

[Robert_Krten1]

Wojtek Lerch <wojtek_l@yahoo.ca> wrote:

John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
John Garvey <> jgarvey@qnx.com> > wrote:
Robert Krten <> nospam83@parse.com> > wrote:
I assume that it is invalid to move directory entries around
in a directory while an opendir() is in effect, right?
yourself (say, eg, in a recursive delete sequence), then you
should use rewinddir() to reset the directory stream and start
readdir()ing again from the beginning for a consistent view …
Huh. In that case, rm -rfv is broken > > When I stopped moving stuff
around in directories, rm -rfv worked; when I was moving stuff around,
it claimed “directory not empty”…

Hmm, looks like “rm -r” does not rewinddir(), and is thus broken
(since the disk filesystems effectively do not shuffle things
around and just mark as “unused” it would appear to work for them).
I’ll raise a PR for the utility guys on “rm” …

I don’t think rm should be required to do rewinddir(). POSIX doesn’t
say that the behaviour of readdir() is completely unspecified if a file
is deleted or added; the only thing that’s unspecified is whether
readdir() returns an entry FOR THE DELETED OR ADDED FILE. This doesn’t
give readdir() a licence to skip over any other files. In particular,
if you only remove files that readdir() has already returned (like rm -r
does), readdir() MUST RETURN ALL FILES.

Or am I missing something?
I’d vote that rm do a rewinddir() as a two-fold defensive programming

approach – first of all, to handle dirents moving around, and secondly
to kill off any new entries that were added while the rm was running

But hey, I’m not doing the one doing the change in rm (BTW, the ramdisk now does
not move the entries around, and everything looks ok).

Cheers,
-RK

\

Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.

[Wojtek_Lerch1]

Robert Krten <nospam83@parse.com> wrote:

Wojtek Lerch <> wojtek_l@yahoo.ca> > wrote:
I don’t think rm should be required to do rewinddir(). POSIX doesn’t
say that the behaviour of readdir() is completely unspecified if a file
is deleted or added; the only thing that’s unspecified is whether
readdir() returns an entry FOR THE DELETED OR ADDED FILE. This doesn’t
give readdir() a licence to skip over any other files. In particular,
if you only remove files that readdir() has already returned (like rm -r
does), readdir() MUST RETURN ALL FILES.

I’d vote that rm do a rewinddir() as a two-fold defensive programming
approach – first of all, to handle dirents moving around, and secondly
to kill off any new entries that were added while the rm was running >

If you added new files to a directory that rm was removing, you probably
did it by mistake and don’t want rm to delete them.

BTW Adding a simple rewinddir() + repeat stage to rm is not good enough
– you don’t want to do it if you’ve failed to remove a file for some
reason. Whatever workarounds we add to rm to handle broken filesystems,
it would be good not to break the behaviour that POSIX requires from rm
on a POSIX filesystem. And POSIX is quite specific about what rm should
do.


(Personally, I don’t think it’s a good idea to allow a resmgr to
accidentally “hide” a file from readdir() just because someone has
deleted a different file. I think a resmgr that does that should be
considered broken, just like one that reports a file twice when
someone adds an unrelated file.

Or do you think that that’s acceptable behaviour, too, and that it’s rm
that should watch for duplicate entries to avoid trying to remove a file
that it’s already removed?)

[Robert_Krten1]

Wojtek Lerch <wojtek_l@yahoo.ca> wrote:

Robert Krten <> nospam83@parse.com> > wrote:
Wojtek Lerch <> wojtek_l@yahoo.ca> > wrote:
I don’t think rm should be required to do rewinddir(). POSIX doesn’t
say that the behaviour of readdir() is completely unspecified if a file
is deleted or added; the only thing that’s unspecified is whether
readdir() returns an entry FOR THE DELETED OR ADDED FILE. This doesn’t
give readdir() a licence to skip over any other files. In particular,
if you only remove files that readdir() has already returned (like rm -r
does), readdir() MUST RETURN ALL FILES.

I’d vote that rm do a rewinddir() as a two-fold defensive programming
approach – first of all, to handle dirents moving around, and secondly
to kill off any new entries that were added while the rm was running >

If you added new files to a directory that rm was removing, you probably
did it by mistake and don’t want rm to delete them. >

Nah, I often (as root, no less), do “rm -rfv” on active directories that
have stuff being added to them, and then I rerun rm -rfv again and again
until the stuff is gone. Hey, it’s a tightly managed system

BTW Adding a simple rewinddir() + repeat stage to rm is not good enough
– you don’t want to do it if you’ve failed to remove a file for some
reason. Whatever workarounds we add to rm to handle broken filesystems,
it would be good not to break the behaviour that POSIX requires from rm
on a POSIX filesystem. And POSIX is quite specific about what rm should
do.

Yah, I guess you’re right there

(Personally, I don’t think it’s a good idea to allow a resmgr to
accidentally “hide” a file from readdir() just because someone has
deleted a different file. I think a resmgr that does that should be
considered broken, just like one that reports a file twice when
someone adds an unrelated file.

Or do you think that that’s acceptable behaviour, too, and that it’s rm
that should watch for duplicate entries to avoid trying to remove a file
that it’s already removed?)

I will let the POSIX gurus decide

Cheers,
-RK

–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.