Subject: Re: [reiserfs-list] Directory cookie issues

From: Mike Eisler <[email-masked]>
Date: Tue, 6 Feb 2001 08:32:02 -0800 (PST)

> >>>>> " " == Brent  <[email-masked]> writes:
> 
>      > The problem doesn't get any easier with cookies bigger than 64
>      > bits.  Even a 64 bit OS won't handle those unless the offset in
>      > the getdents structure is changed to be some variable length
>      > array of bytes rather than an integer.  What kind of offset
>      > does Linux use in getdents ?
> 
> Currently we just pass the cookie directly to getdents. That's a
> pretty lame thing to do (violating POSIX and all), but it's done that
> way for historical reasons.
> 
> I have now prepared a patch that sets up a cookie dictionary and

What if the directory is over 250 thousand entries in size? That's
a large dictionary, but that's what it takes to support arbitrary seekdir()
in a file system that has cookies larger than the directory offset type.

> creates signed 32-bit offsets for use as getdents/lseek offsets. There
> are still some issues of garbage collection to work out, but I hope
> that'll ready for inclusion into the official kernel RSN.
> 
> Cheers,
>   Trond

---

From: Trond Myklebust <[email-masked]>
Date: Tue, 6 Feb 2001 19:27:37 +0100 (CET)

>>>>> " " == Mike Eisler <[email-masked]> writes:

     > What if the directory is over 250 thousand entries in size?
     > That's a large dictionary, but that's what it takes to support
     > arbitrary seekdir() in a file system that has cookies larger
     > than the directory offset type.

That's what was lying behind my `issues of garbage collection to work
out' ;-).

To expand a bit on the history of this issue: During the Linux 2.3.x
development cycle, I experimented with the idea of counting entries
and using the 'offset' thus obtained for lseek/getdents. I found that
it is very hard to make such a scheme consistent with POSIX behaviour.
Whenever `unlink' was called on a file, one ends up skipping an entry
more often than not. This was made worse by the fact that glibc relies
on being able to issue an `lseek' in order to rewind the directory
file pointer by 1 entry at any time. Hence when doing an `rm *' glibc
would end up skipping whole swathes of entries because it would rewind
to an offset that was only valid before `unlink' was called.

In order to get this sort of thing to work, I found I cannot rely on
offsets for which the meaning changes whenever you flush the page
cache; hence the need for a dictionary that can be allowed to survive
such a flush.
I currently envisage that dictionary in the form of a cache of up to
(say) 8000 entries. Once I hit that limit, I'll need to start throwing
out LRU entries and will end up losing seekdir() consistency again.

Alternative reliable schemes for crunching 64/32-bits into 31 are more
than welcome, but I imagine that if accepted, Hans' proposal for using
filenames as cookies will force us all to implement such dictionaries
(sic.) in order to continue to support seekdir()/telldir().

Cheers,
    Trond

---

From: Xuan Baldauf <[email-masked]>
Date: Tue, 06 Feb 2001 20:02:50 +0100

Trond Myklebust wrote:

> [...]

I'd like to see seekdir|telldir the current style rest in peace. It is
based on the false assumption that filesystems never change the internal
offsets of their direntries. If it is needed by applications (which ones?)
at all, the return value of telldir|second argument of seekdir should be
replaced by a "directory position handle", a costly resource by the kernel
for the application. Some aspects of this handle could be treated like a
filehandle (e.g. close() frees the dirpos handle, a dirpos handle may be
implemented internally as file-descriptor). Other aspects won't work, as
read() and write(), but this is not needed.

For classic filesystems, the dirpos handle contains just the off_t we had
before. For nfs, it contains the arbitrary-length cookie (which might be a
filename). For local reiserfs, it contains the filename. For a relational
database-fs, it contains the combination of all keys needed to
unambigously define a position within a table so that this position can
unambigously split the table in the part which was already read and the
part which is still to be read, independent of the actual contents of the
table.

The validity of the dirpos handle should depend on the validity of the
directory handle, i.e. if the directory file descriptor is closed, the
dirpos handle is also closed|invalidated.

I still don't like exposing the position within a directory listing to the
application and seeking to another position at all. Which application use
that "feature"?

Xuân.

---

From: Trond Myklebust <[email-masked]>
Date: Tue, 6 Feb 2001 20:55:02 +0100 (CET)

>>>>> " " == Xuan Baldauf <[email-masked]> writes:

     > I'd like to see seekdir|telldir the current style rest in
     > peace. It is based on the false assumption that filesystems
     > never change the internal offsets of their direntries. If it is
     > needed by applications (which ones?)  at all, the return value
     > of telldir|second argument of seekdir should be replaced by a
     > "directory position handle", a costly resource by the kernel
     > for the application. Some aspects of this handle could be
     > treated like a filehandle (e.g. close() frees the dirpos
     > handle, a dirpos handle may be implemented internally as
     > file-descriptor). Other aspects won't work, as read() and
     > write(), but this is not needed.

Then you'll end up with a problem of backward compatibility which is
contrary to the spirit of NFSv4 extensions if I read the intro in
rfc3010 correctly.

Cheers,
  Trond

---

From: Xuan Baldauf <[email-masked]>
Date: Tue, 06 Feb 2001 22:28:26 +0100

> contrary to the spirit of NFSv4 extensions if I read the intro in

You are absolutely right that this API change is not backward compatible.
But this API change has not much to do with NFS. It has something to do
with application-OS-interaction. If we already have to emulate 32 bit
cookies for userland due to NFSv3 (64 bit or more bits of the underlying
cookie, it does not matter how long the underlying cookie is), we can do
the same for other cases as well. So if a new API was to be established,
the old API can still be emulated.

See glibc2.1.3/sysdeps/unix/bsd/telldir.c. Here, they are already
emulating cookies. A cookie handle is internally created with telldir()
and is freed with seekdir(). A comment from there:

<comment>
 /* To prevent leaking memory, cookies returned from telldir
    can only be used once.  So free this one's record now.  */
</comment>

If current applications are compatible with this (e.g. they work properly
on BSD), they are able to work with the new scheme without any
modification, just the glibc implementation would have to change. And now
I ask again: Which application do use seekdir (except to the start of the
directory, which is no problem), and why? And then: Which application do
not work with the BSD-implementation of that scheme? (Only those
applications have to be changed or only for those applications, cookie
emulation on the kernel side is necessary.)

Maybe someone can point me to applications needing seekdir|telldir.

Xuân.

---

From: Hans Reiser <[email-masked]>
Date: Wed, 07 Feb 2001 00:17:12 +0300

Xuan Baldauf wrote:
> XuБn.

In database circles it is called a "cursor".  Having a next and a previous
operation are in principle valid features to have, and someday reiserfs will
allow defining arbitrary ordering on directories (another feature cookies make
difficult).  Killing off seekdir would improve POSIX.  All of that said, I think
that from the NFS group it is enough to ask to generalize cookies, and reforming
those who use seekdir is a task for us to ask of others (glibc folks, etc.).

Hans

---

From: Trond Myklebust <[email-masked]>
Date: Tue, 6 Feb 2001 23:16:59 +0100 (CET)

> You are absolutely right that this API change is not backward
     > compatible.  But this API change has not much to do with
     > NFS. It has something to do with application-OS-interaction. If
     > we already have to emulate 32 bit cookies for userland due to
     > NFSv3 (64 bit or more bits of the underlying cookie, it does
     > not matter how long the underlying cookie is), we can do the
     > same for other cases as well. So if a new API was to be
     > established, the old API can still be emulated.
<....>
     > If current applications are compatible with this (e.g. they
     > work properly on BSD), they are able to work with the new
     > scheme without any modification, just the glibc implementation
     > would have to change. And now I ask again: Which application do
     > use seekdir (except to the start of the directory, which is no
     > problem), and why? And then: Which application do not work with
     > the BSD-implementation of that scheme? (Only those applications
     > have to be changed or only for those applications, cookie

The NFS servers themselves consitute a large class of such
applications:

Don't forget that an NFS server has to be able to recover gracefully
from a reboot/crash. If your cookie cache is entirely in software, you
will lose it.
In addition, NFSv2/v3 compatibility requires your cookie cache on the
server to be more or less permanent. Unlike NFSv4, the former 2
protocols don't have any OPEN/CLOSE, so your server has no way of
knowing when it's safe to invalidate a cookie and drop it from your
cache.

     > Maybe someone can point me to applications needing

In Linux userland: all applications that use

     glibc-2.x/sysdeps/unix/linux/getdents.c

Cheers,
  Trond

---

From: Hans Reiser <[email-masked]>
Date: Wed, 07 Feb 2001 00:48:10 +0300

>      glibc-2.x/sysdeps/unix/linux/getdents.c
A lot more applications use getdents than use seekdir, am I right?

Hans

---

From: Trond Myklebust <[email-masked]>
Date: Tue, 6 Feb 2001 23:38:06 +0100 (CET)

>>>>> " " == Hans Reiser <[email-masked]> writes:

    >> Cheers, Trond

My point was that the glibc implementation of getdents() under Linux
also uses lseek() (same thing as seekdir as far as we're concerned) in
order to rewind the directory pointer. It's part of a heuristic they
implemented to deal with the difference between the kernel and libc
definitions of 'struct dirent'.

Cheers,
  Trond.

---

From: Xuan Baldauf <[email-masked]>
Date: Wed, 07 Feb 2001 00:00:40 +0100

> from a reboot/crash. If your cookie cache is entirely in software, you

Maybe you missunderstood me. The cookie cache should be at the nfs client,
not the nfs server. If the nfs server crashes, the nfs client still knows
the "real" cookie from the server for the server. If the nfs client
crashes, it forgets that cookie, but apps needing that cookie forget it
too. :-)

> knowing when it's safe to invalidate a cookie and drop it from your

When you talk about NFSv2|v3 daemons running with the new API, you're
right. (But those daemons do not really count, because they only do that
for other applications...) Well, those daemons could use the kernel calls
directly (old style), while other applications use the libc wrapper
(emulated old style using new style).

>      glibc-2.x/sysdeps/unix/linux/getdents.c

That alone does not count. The information obtained by getdents has to be
used (given back to libc|kernel to achieve something). If it (specifically
dirent.d_off) is not used, it is not needed. The fact that
glibc-2.x/sysdeps/unix/linux/getdents.c itself uses lseek with a 32bit or
64bit dirpos is not a problem, because libc has to be changed for the new
API anyway. Getdents could be reimplemented using the dirpos handle
mechanism.

Effectively only an application which uses seekdir() (or bypasses glibc
with a very good reason and using lseek() on a directory fd) can be
affected. I searched the net for source code which uses seekdir(). So far
I've only found the midnight commander. And you'll laugh, it defines
readdir() and seekdir() in its VFS for internal use, but it does not use
it.

>   Trond

Xuân. :-)