This patch effects all users of libfs' dcache directory implementation.
Old glibc implementations (e.g. glibc-2.2.5) are lseeking after every call to
getdents(), subsequent calls to getdents() are starting to read from a wrong
f_pos, when the directory is modified in between. Therefore not all directory
entries are returned. IMHO this is a bug and it breaks applications, e.g. "rm
-fr" on tmpfs.
SuSV3 only says:
"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_r()
returns an entry for that file is unspecified."
Although I tried to provide a small fix, this is a complete rework of the
libfs' dcache_readdir() and dcache_dir_lseek(). This patch use the dentries
name hashes as the offsets for the directory entries. I'm not that sure it is
maybe a problem to use full_name_hash() for that. If hash collisions occur,
readdir() might return duplicate entries after an lseek(). Any ideas?
This patch is compile and boot tested. This patch is against 2.6.14-git of
today.
Comments, please.
Jan
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
On Fri, Nov 04, 2005 at 12:38:51PM +0100, [email protected] wrote:
> This patch effects all users of libfs' dcache directory implementation.
>
> Old glibc implementations (e.g. glibc-2.2.5) are lseeking after every call to
> getdents(), subsequent calls to getdents() are starting to read from a wrong
> f_pos, when the directory is modified in between. Therefore not all directory
> entries are returned. IMHO this is a bug and it breaks applications, e.g. "rm
> -fr" on tmpfs.
>
> SuSV3 only says:
> "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_r()
> returns an entry for that file is unspecified."
IOW, the applications in question are broken since they rely on unspecified
behaviour, not provided by old libc versions.
On Fri, Nov 04, Al Viro wrote:
> >
> > SuSV3 only says:
> > "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_r()
> > returns an entry for that file is unspecified."
>
> IOW, the applications in question are broken since they rely on unspecified
> behaviour, not provided by old libc versions.
No. SuSV3 only says that the behavior of readdir() is unspecified w.r.t. an
entry for the removed/added file. I think readdir() should still return the
entries which are not removed/added. What do you think?
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
On Fri, 4 November 2005 12:38:51 +0100, [email protected] wrote:
> #include <stdio.h>
> #include <unistd.h>
> #include <dirent.h>
>
> int main(int argc, char *argv[])
> {
> DIR *dir;
> struct dirent *entry;
> unsigned int offset;
>
> if (argc < 2) {
> printf("USAGE: %s <directory>\n", argv[0]);
> return 1;
> }
>
> dir = opendir(argv[1]);
> if (!dir)
> return 1;
>
> while((entry = readdir(dir)) != NULL) {
> seekdir(dir, entry->d_off);
> printf("name=%s\tino=%d off=%d\n", entry->d_name, entry->d_ino,
> entry->d_off);
> if (*entry->d_name == '.')
> continue;
That catches "." and "..", but also ".foo". Doesn't matter for the
test, just wanted to mention it.
> if(unlink(entry->d_name) != 0)
> break;
> }
>
> closedir(dir);
> return 0;
> }
J?rn
--
With a PC, I always felt limited by the software available. On Unix,
I am limited only by my knowledge.
-- Peter J. Schoenster
> > >
> > > SuSV3 only says: "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_r() returns an
> > > entry for that file is unspecified."
> >
> > IOW, the applications in question are broken since they rely on
> > unspecified behaviour, not provided by old libc versions.
>
> No. SuSV3 only says that the behavior of readdir() is unspecified
> w.r.t. an entry for the removed/added file. I think readdir() should
> still return the entries which are not removed/added. What do you
> think?
What 'rm' is this? Mine (coreutils 5.2.1) doesn't do any seeking and
I don't think that glibc does either.
Miklos
On Fri, Nov 04, Miklos Szeredi wrote:
> > > >
> > > > SuSV3 only says: "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_r() returns an
> > > > entry for that file is unspecified."
> > >
> > > IOW, the applications in question are broken since they rely on
> > > unspecified behaviour, not provided by old libc versions.
> >
> > No. SuSV3 only says that the behavior of readdir() is unspecified
> > w.r.t. an entry for the removed/added file. I think readdir() should
> > still return the entries which are not removed/added. What do you
> > think?
>
> What 'rm' is this? Mine (coreutils 5.2.1) doesn't do any seeking and
> I don't think that glibc does either.
>
As I said:
"Old glibc implementations (e.g. glibc-2.2.5) are lseeking after every call to
getdents() ..."
Precisely this is a SLES8 on s390-64bit.
s390vm02:/# rpm -qf /bin/rm
fileutils-4.1.11-144
s390vm02:/# rpm -q glibc
glibc-2.2.5-234
But you can also try my testcase.
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
> As I said: "Old glibc implementations (e.g. glibc-2.2.5) are
> lseeking after every call to getdents() ..."
Hmm, why would it do that? This seems like it's glibc being stupid.
That said, you are right that the libfs readdir implementation is not
strictly standards conforming. But neither is your patch: this
algorithm will break if the entry at the current position is removed
and then a new entry with the same name is created.
> Precisely this is a SLES8 on s390-64bit.
> s390vm02:/# rpm -qf /bin/rm
> fileutils-4.1.11-144
> s390vm02:/# rpm -q glibc
> glibc-2.2.5-234
>
> But you can also try my testcase.
Unfortunately I can't since I don't have such old glibc.
Miklos
On Fri, Nov 04, Miklos Szeredi wrote:
> > As I said: "Old glibc implementations (e.g. glibc-2.2.5) are
> > lseeking after every call to getdents() ..."
>
> Hmm, why would it do that? This seems like it's glibc being stupid.
>
Well, glibc is that stupid and triggers the bug.
> That said, you are right that the libfs readdir implementation is not
> strictly standards conforming. But neither is your patch: this
> algorithm will break if the entry at the current position is removed
> and then a new entry with the same name is created.
True. Seeking to that offset should at least fail and shouldn't stop at the
new entry. But SuSV3 says that the offset given by telldir() is valid until
the next rewinddir(). This is no problem for directories that can only grow.
I tried to implement some kind of deferred dput'ing of the d_child's but that
was too hackish and was wasting memory. So the best thing I can do now is fail
if someone wants to seek to an offset of an already unlinked file.
So I can include the inode number in the hashing process somehow. Any ideas on
that one?
> Unfortunately I can't since I don't have such old glibc.
The testcase is similar to what "rm *" with the old glibc would do. It just
a testcase to show where the problem is.
On Fri, 4 November 2005 16:11:04 +0100, [email protected] wrote:
>
> True. Seeking to that offset should at least fail and shouldn't stop at the
> new entry. But SuSV3 says that the offset given by telldir() is valid until
> the next rewinddir(). This is no problem for directories that can only grow.
> I tried to implement some kind of deferred dput'ing of the d_child's but that
> was too hackish and was wasting memory. So the best thing I can do now is fail
> if someone wants to seek to an offset of an already unlinked file.
Does that mean that, to satisfy the standard, you'd have to allow the
seek, but return 0 bytes on further reads, as you're already at (or
beyond, whatever) EOF?
Sounds quite ugly and it would be nice if this wasn't necessary.
J?rn
--
When people work hard for you for a pat on the back, you've got
to give them that pat.
-- Robert Heinlein
> > > As I said: "Old glibc implementations (e.g. glibc-2.2.5) are
> > > lseeking after every call to getdents() ..."
> >
> > Hmm, why would it do that? This seems like it's glibc being stupid.
> >
>
> Well, glibc is that stupid and triggers the bug.
Seems to me, the simple solution is to upgrade your glibc.
> > That said, you are right that the libfs readdir implementation is not
> > strictly standards conforming. But neither is your patch: this
> > algorithm will break if the entry at the current position is removed
> > and then a new entry with the same name is created.
>
> True. Seeking to that offset should at least fail and shouldn't stop at the
> new entry.
No it should _not_ fail, it should continue from the next _existing_
entry.
> But SuSV3 says that the offset given by telldir() is valid until the
> next rewinddir(). This is no problem for directories that can only
> grow. I tried to implement some kind of deferred dput'ing of the
> d_child's but that was too hackish and was wasting memory. So the
> best thing I can do now is fail if someone wants to seek to an
> offset of an already unlinked file.
>
> So I can include the inode number in the hashing process
> somehow. Any ideas on that one?
No good. Same problem if you move out then move back the entry.
>
> > Unfortunately I can't since I don't have such old glibc.
>
> The testcase is similar to what "rm *" with the old glibc would do. It just
> a testcase to show where the problem is.
I understand, but I have glibc-2.3.5 which apparently doesn't seek
after readdir().
Miklos
On Fri, Nov 04, J?rn Engel wrote:
> On Fri, 4 November 2005 16:11:04 +0100, [email protected] wrote:
> >
> > True. Seeking to that offset should at least fail and shouldn't stop at the
> > new entry. But SuSV3 says that the offset given by telldir() is valid until
> > the next rewinddir(). This is no problem for directories that can only grow.
> > I tried to implement some kind of deferred dput'ing of the d_child's but that
> > was too hackish and was wasting memory. So the best thing I can do now is fail
> > if someone wants to seek to an offset of an already unlinked file.
>
> Does that mean that, to satisfy the standard, you'd have to allow the
> seek, but return 0 bytes on further reads, as you're already at (or
> beyond, whatever) EOF?
No. To satisfy the standard, it would be necessary to let the seek succeed and
to return the already unlinked dentry or the next dentry (this is
unspecified). I think we should return the next dentry, therefore I let the
seek fail (seekdir() doesn't even have a return value) and the cursor/f_pos is
still at the old offset.
The real problem is this IMHO:
...
telldir() = a
...
telldir() = b
readdir() = foo.txt
unlink(foo.txt)
seekdir(a)
seekdir(b)
readdir() = ???
With my patch the seekdir(b) doesn't find the offset and is placing the cursor
at the end of the directory. In my understanding of the SuSV3 this should be
possible and should return either "foo.txt" or the next entry after
"foo.txt". I don't see any chance how I can implement that.
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
> > True. Seeking to that offset should at least fail and shouldn't
> > stop at the new entry. But SuSV3 says that the offset given by
> > telldir() is valid until the next rewinddir(). This is no problem
> > for directories that can only grow. I tried to implement some
> > kind of deferred dput'ing of the d_child's but that was too
> > hackish and was wasting memory. So the best thing I can do now is
> > fail if someone wants to seek to an offset of an already unlinked
> > file.
>
> Does that mean that, to satisfy the standard, you'd have to allow the
> seek, but return 0 bytes on further reads, as you're already at (or
> beyond, whatever) EOF?
>
> Sounds quite ugly and it would be nice if this wasn't necessary.
The directory position not _on_ an entry, but _between_ two entries.
So it doesn't matter if the next entry is removed, the offset stays
perfectly valid.
If there doesn't remain any entries after the position, readdir should
return EOF. Otherwise it should continue reading normally.
What SUS doesn't specify is what happens entries added between
opendir() and before rewinddir().
Miklos
On Fri, Nov 04, Miklos Szeredi wrote:
> >
> > Well, glibc is that stupid and triggers the bug.
>
> Seems to me, the simple solution is to upgrade your glibc.
>
This is SLES8. You don't want to update the glibc.
> >
> > True. Seeking to that offset should at least fail and shouldn't stop at the
> > new entry.
>
> No it should _not_ fail, it should continue from the next _existing_
> entry.
>
And how do we achieve this for all the libfs users like tmpfs etc.? At least
with my patch you can seek to the offsets of existing entries. Even that isn't
possible at the moment if you remove directory entries. But I don't know how to
implement that for the offsets of unlinked entries.
>
> No good. Same problem if you move out then move back the entry.
>
Yeah, I know.
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
On Fri, 4 November 2005 16:34:20 +0100, [email protected] wrote:
> On Fri, Nov 04, J?rn Engel wrote:
> > On Fri, 4 November 2005 16:11:04 +0100, [email protected] wrote:
> > >
> > > True. Seeking to that offset should at least fail and shouldn't stop at the
> > > new entry. But SuSV3 says that the offset given by telldir() is valid until
> > > the next rewinddir(). This is no problem for directories that can only grow.
> > > I tried to implement some kind of deferred dput'ing of the d_child's but that
> > > was too hackish and was wasting memory. So the best thing I can do now is fail
> > > if someone wants to seek to an offset of an already unlinked file.
> >
> > Does that mean that, to satisfy the standard, you'd have to allow the
> > seek, but return 0 bytes on further reads, as you're already at (or
> > beyond, whatever) EOF?
>
> No. To satisfy the standard, it would be necessary to let the seek succeed and
> to return the already unlinked dentry or the next dentry (this is
> unspecified).
Do you have a link to the standard? Iirc, it is explicitly
unspecified whether files created/deleted after opendir/rewinddir are
returned. Why do you want to return one such unspecified file now?
Especially when the implementation is ugly and the whole concept
appears to be plain stupid.
> I think we should return the next dentry, therefore I let the
> seek fail (seekdir() doesn't even have a return value) and the cursor/f_pos is
> still at the old offset.
>
> The real problem is this IMHO:
> ...
> telldir() = a
> ...
> telldir() = b
> readdir() = foo.txt
> unlink(foo.txt)
> seekdir(a)
> seekdir(b)
> readdir() = ???
>
> With my patch the seekdir(b) doesn't find the offset and is placing the cursor
> at the end of the directory. In my understanding of the SuSV3 this should be
> possible and should return either "foo.txt" or the next entry after
> "foo.txt". I don't see any chance how I can implement that.
Does the above really happen, or is this just a theoretical case? At
least it looks as if ext3 with dir_index will simply barf on it:
/* Some one has messed with f_pos; reset the world */
if (info->last_pos != filp->f_pos) {
...
And imo, that is the correct behaviour. Anything else would leave the
door wide open for trivial DOS attacks on kernel memory.
J?rn
--
The strong give up and move away, while the weak give up and stay.
-- unknown
> > >
> > > Well, glibc is that stupid and triggers the bug.
> >
> > Seems to me, the simple solution is to upgrade your glibc.
> >
>
> This is SLES8. You don't want to update the glibc.
OK, but then it's basically a SLES8 kernel issue, not a mainline
kernel issue.
Probably very few people are using brand new kernels with glibc from
the last millennium ;)
Miklos
On Fri, Nov 04, Miklos Szeredi wrote:
> > > >
> > > > Well, glibc is that stupid and triggers the bug.
> > >
> > > Seems to me, the simple solution is to upgrade your glibc.
> > >
> >
> > This is SLES8. You don't want to update the glibc.
>
> OK, but then it's basically a SLES8 kernel issue, not a mainline
> kernel issue.
>
> Probably very few people are using brand new kernels with glibc from
> the last millennium ;)
>
Hmm, so I should only send patches for bugs that are often triggered
upstream? Just start using seekdir() and modify the directory contents on an
upstream tmpfs. You'll see that this isn't working well.
This is a bug and it should get fixed. I hope that it doesn't depend on how
many people using what library :)
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
> > > > >
> > > > > Well, glibc is that stupid and triggers the bug.
> > > >
> > > > Seems to me, the simple solution is to upgrade your glibc.
> > > >
> > >
> > > This is SLES8. You don't want to update the glibc.
> >
> > OK, but then it's basically a SLES8 kernel issue, not a mainline
> > kernel issue.
> >
> > Probably very few people are using brand new kernels with glibc from
> > the last millennium ;)
> >
>
> Hmm, so I should only send patches for bugs that are often triggered
> upstream? Just start using seekdir() and modify the directory contents on an
> upstream tmpfs. You'll see that this isn't working well.
>
> This is a bug and it should get fixed. I hope that it doesn't depend on how
> many people using what library :)
Ah, but it's a bug in the _system_ and glibc is part of the system
too, not just the kernel.
Upgrading glibc solves the problem, so why work around it in kernel
too?
Your patch is not a solution, since readdir will remain nonconforming.
It is basically a workaround for a bug in glibc. It makes readdir
nonconforming in a different way, but the end result in not
necessarily better.
If you manage to make dcache_readdir conform to SUS without overly
bloating the implementation, that's fine.
Miklos
On Fri, 2005-11-04 at 16:11 +0100, [email protected] wrote:
> On Fri, Nov 04, Miklos Szeredi wrote:
>
> > > As I said: "Old glibc implementations (e.g. glibc-2.2.5) are
> > > lseeking after every call to getdents() ..."
> >
> > Hmm, why would it do that? This seems like it's glibc being stupid.
> >
>
> Well, glibc is that stupid and triggers the bug.
It is due to the kernel's 32-bit struct dirent being smaller than
glibc's 32-bit struct dirent (glibc has the extra ->d_type field).
Because the dirent record length depends on the filename length, the
exact expansion factor for the results of a call to getdents() may not
be precomputed.
glibc uses a heuristic in order to estimate the expansion size, and then
uses that to allocate an intermediate buffer in which to store the
results of the getdents syscall.
If the contents of said intermediate buffer still happen to overflow the
user-allocated buffer, then glibc calls lseek() in order to rewind the
file pointer to the next entry it wants to read (and screws any
filesystem that doesn't support lseek on directories).
This code appears still to be part of glibc, however it is rarely
triggered these days because glibc's implementation now defaults to
using the getdents64 syscall (if it exists) instead of the 32-bit
version. Since the kernel's struct dirent64 is the same size as the
glibc struct dirent64 (and larger than the 32-bit struct dirent), there
is never any chance of buffer overflow.
The new bug is rather that glibc will return EOVERFLOW, and try to
rewind your file pointer if your filesystem happens to return 64-bit
offsets to getdents64().
> > Unfortunately I can't since I don't have such old glibc.
>
> The testcase is similar to what "rm *" with the old glibc would do. It just
> a testcase to show where the problem is.
'rm -rf' on a large directory used to be a great way to trigger it.
Cheers,
Trond
On Fri, Nov 04, 2005 at 05:04:43PM +0100, [email protected] wrote:
> This is a bug and it should get fixed.
So fix your libc...
> The new bug is rather that glibc will return EOVERFLOW, and try to
> rewind your file pointer if your filesystem happens to return 64-bit
> offsets to getdents64().
Well, that's sort of understandable. It has to map unique 64-bit
offsets to unique 32-bits offsets, which is rather hard.
Miklos
On Friday 04 November 2005 05:51, Al Viro wrote:
> On Fri, Nov 04, 2005 at 12:38:51PM +0100, [email protected] wrote:
> > This patch effects all users of libfs' dcache directory implementation.
> >
> > Old glibc implementations (e.g. glibc-2.2.5) are lseeking after every
> > call to getdents(), subsequent calls to getdents() are starting to read
> > from a wrong f_pos, when the directory is modified in between. Therefore
> > not all directory entries are returned. IMHO this is a bug and it breaks
> > applications, e.g. "rm -fr" on tmpfs.
> >
> > SuSV3 only says:
> > "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_r() returns an entry for that file is unspecified."
>
> IOW, the applications in question are broken since they rely on unspecified
> behaviour, not provided by old libc versions.
Are you sure that's the problem?
Directory starts with 26 files named A-F.
Reading through directory starts at A, makes it to J (position 10).
File B gets deleted.
directory reading continues at new position 11, which is now L.
So directory read returns A-J, L-Z, and never returns K even though K didn't
change.
The "that file" mentioned by SuSv3 above would be _B_ here. Not K. K didn't
change.
That said, I'm pretty sure it's the old libc behavior that's defective. If a
new entry B' had been inserted instead, the directory traversal would have
seen L twice. Iterating by position is just wrong...
Rob
On Fri, Nov 04, Rob Landley wrote:
>
> That said, I'm pretty sure it's the old libc behavior that's defective. If a
So, what should the libc do? Reread the whole directory if it is changed? It
would be a nice DoS attack to just create and delete files and prevent others
from reading that directory.
IMHO it is the job of the filesystem implementation to allow correct SuSV3
specified directory reading.
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de
On Fri, Nov 04, Miklos Szeredi wrote:
>
> Your patch is not a solution, since readdir will remain nonconforming.
> It is basically a workaround for a bug in glibc.
Updating the glibc is no solution because this isn't possible here. And I still
have the opinion that it is the filesystems job to remember the right
offset. At least this is what SuSV3 is telling me.
> It makes readdir
> nonconforming in a different way, but the end result in not
> necessarily better.
Hmm, yes you are right.
>
> If you manage to make dcache_readdir conform to SUS without overly
> bloating the implementation, that's fine.
Will look into that, if its possible.
Regards,
Jan Blunck
--
Jan Blunck [email protected]
SuSE LINUX AG - A Novell company
Maxfeldstr. 5 +49-911-74053-608
D-90409 N?rnberg http://www.suse.de