Subject: nfs standards guys still screwing up in definition of cookies, it's still a thinly disguised hardcoded byte offset

From: Hans Reiser <[email-masked]>
Date: Sun, 04 Feb 2001 12:25:03 +0300

The NFS guys need to just return the last filename that was read, and then we
can efficiently find that name and resume from there.  Let cookies be a hint
that the filesystem can ignore and neglect if they have a competent directory
lookup implementation, and if they have a stupid uncompressable file as their
directory mechanism let them use the byte offset in the cookie.

Cookies are a thinly disguised hardcoding of byte offsets into files.  You can
pretend all you want that 64 bits aren't a constraint on those trying to use
directory lookup mechanisms that are more recent than the stone age, but it
isn't so. 

Thanks to the NFS committee reiserfs cannot implement stem compressed
directories.  Reiserfs cannot take the known superior methods of the hypertext
indexes culture, in which indexes take less space than the total length of all
the names in them, and bring them into use in our filesystem, because of the NFS
standards committee.  Instead, we have to use hashing of filenames, which is a
clearly inferior technology, so that we can squeeze the filename into 64 bits
for the sake of these silly cookies.

The verifier is an ugly hack compared to just using the filename.  What really
gets me is that using the last filename read is SOOOO simple to code.... and
this verifier is going to be so much more complex in all of its ramifications.

Hans

Xuan Baldauf wrote:

> > > nfs is indeed braindead, but that isn't very useful to say since everyone uses
> > > it, we think we have a patch (posted on the list) that needs users to test it
> > > that should get the last remaining bug out in the interface to NFS.  The code
> > > passes internal testing.  (Thanks to NFS we have to hash filenames rather than
> > > stem compressing them because they hardcode the use of a 32 bit int for
> > > recording position in a directory while reading, and we have to have an extra
> > > field in the stat data just for it (this is our most recent fix by Nikita).)
> >
> > In kernel 2.2.18 NFSv3 is supported in the standard kernel, rather than
> > needing extra patches. In your position I'd be tempted to say "we do not
> > support the use of NFSv2". Given NFSv3's 64 bit limit there are better
> > strategies, mainly you can use a linear address, rather than needing
> > hashes. The question that comes is how soon are we going to see
> > disks/arrays that can hold 2^64 bytes?
> 
> The really good news are not the 8 byte cookie (cookies have to be variable length to
> be valid for an indefinite amount of time for a directory which can grow indefinitely
> large, or they have to be stateful), but the cookie verifier (which is a kind of
> statefulness). The server may now reject continued readdir operations if a cookie
> verifier is given to the server which the server does not want to be used.
> 
> This way we are not bound to hashing anymore (for NFSv3), we may just reject resumed
> readdir operations which come too late. It also allows internal stateful tracking of
> all cookies out there. (After a given amount of time or memory pressure, the nfs
> server may just forget tracking and just reject any resumed readdir commands.)
> 
> Of course, this can only work of the client retries the readdir operation...
> 
> RFC1813 says:
> 
> READDIR
>          The READDIR arguments now include a verifier to allow
>          the server to validate the cookie. The cookie is now a
>          64 bit unsigned integer instead of the 4 byte array
>          which was used in the NFS version 2 protocol.  This
>          will help to reduce interoperability problems.
> 
> [...]
> 
> In the NFS version 2 protocol, each directory entry
>       returned included a cookie identifying a point in the
>       directory. By including this cookie in a subsequent
>       READDIR, the client could resume the directory read at any
>       point in the directory.  One problem with this scheme was
> 
>       that there was no easy way for a server to verify that a
>       cookie was valid. If two READDIRs were separated by one or
>       more operations that changed the directory in some way
>       (for example, reordering or compressing it), it was
>       possible that the second READDIR could miss entries, or
>       process entries more than once. If the cookie was no
>       longer usable, for example, pointing into the middle of a
>       directory entry, the server would have to either round the
>       cookie down to the cookie of the previous entry or round
>       it up to the cookie of the next entry in the directory.
>       Either way would possibly lead to incorrect results and
>       the client would be unaware that any problem existed.
> 
>       In the NFS version 3 protocol, each READDIR request
>       includes both a cookie and a cookie verifier. For the
>       first call, both are set to 0.  The response includes a
>       new cookie verifier, with a cookie per entry.  For
>       subsequent READDIRs, the client must present both the
>       cookie and the corresponding cookie verifier.  If the
>       server detects that the cookie is no longer valid, the
>       server will reject the READDIR request with the status,
>       NFS3ERR_BAD_COOKIE. The client should be careful to
>       avoid holding directory entry cookies across operations
>       that modify the directory contents, such as REMOVE and
>       CREATE.
> 
> XuБn.

---

From: Xuan Baldauf <[email-masked]>
Date: Sun, 04 Feb 2001 11:54:08 +0100

Yes,

I know, fixed length of position information is incompatible with the timeless (stateless)
nature of the position information as used in NFSv2, v3, v4 (therefore it is bad design to
still use that), and the cookie verifier is a bad hack, but maybe you can do stem
compression:

- using the upper 32 bits for a at most 4 byte stem
- using the lower 32 bits for the hash value.

This is really ugly, but might be more performant. Often, the parts of the filename which
equal (the stem) often are only some bytes, so you could handle stems this ways, with those
limitation.

Another way is to do connection tracking and invalidating requests which come too late.
This is against the stateless spirit of NFS.

And yet, another way is to be able to use a variable length cookie (the length is
determined by the server). This is the most elegant and the only non-hack solution.

You cannot use a limited integer to determine a position within an unlimited set (the set
is unlimited because the integer does not only have to point to the position within the
current set configuration, but within the current and all possible set configurations _of
the future_).

Maybe someone of the NFS standards people can explain why this should be possible. I'd
really like to listen.

Xuân.

Hans Reiser wrote:

> > Xuân.

---

From: Hans Reiser <[email-masked]>
Date: Sun, 04 Feb 2001 15:33:41 +0300

> equal (the stem) often are only some bytes, so you could handle stems this ways, with those

I thought about this some time ago.  It might be better, but it would require
serious effort resulting in what is still a hack.  Time perhaps better spent
complaining to the standards committee.

> determined by the server). This is the most elegant and the only non-hack solution.

Yes, exactly.  If cookie is variable length and can be filename last read,
everything
works out really nicely in the code.

---

From: "Mark K. Patterson" <[email-masked]>
Date: Sun, 04 Feb 2001 11:37:54 -0500

Hans,

Would it be worthwhile to perhaps develop two trees?  Reiserfs and
Reiserfs-no-nfs?  Perhaps this could allow for a 'show me the code'
approach to the NFS folks as to why indeces have merit.  Let them try to
challenge the resulting benchmarks.  Or would this involve too great a
code fork for the time being?

Just a couple of thoughts.

P.S.  Running linux-2.2.18 + reiserfs-3.5.29 with no problems.  Fabulous
work!

-M-

---

From: Eric Werme USG <[email-masked]>
Date: Sun, 04 Feb 2001 13:27:38 -0500

Hans Reiser wrote:

It would seem to me the cookie would have to be the _next_ filename to read.
While Unix-like shells take commands like "rm foo.*" and read the directory
completely before deleting files, MS-DOS's "del foo.*" reads a chunk of
directory, deletes files, reads the next chunk, etc.  If you returned the
last filename read, then it may not be there for the next directory read.
Note this presupposes deleting files doesn't change the position of the
"next file" when directory reading resumes.  I imagine that could be a
problem with some tree-structured directory designs.

Returning the directory offset lets MS-DOS's "del foo.*" work, as deleting
a file would change an in-use bit in the directory but not rearrange the
content of the directory file.  (Or does it change the first character of
the filename to 0xE5?  Or both?)  I doubt anyone considered that case in the
V2/V3 design days, we just lucked out.

At any rate, any debate on changes to the directory cookie need to keep
in mind the readdir/delete/readdir cases and do the best to avoid
falling back on the NFS3ERR_BAD_COOKIE return.  Unix has a lot of trouble
recovering from that gracefully.  One nice thing about a change to a variable
length opaque is that many of these issues turn into server implementation
details and not things that would impact the protocol.

It does mean some difficulties on Unix clients that have gotten away with
saving the cookie in the file offset field of the open directory, but
that's been problematic since the early days of V3 development.

	-Ric Werme

--
Eric (Ric) Werme         |  [email-masked]
Compaq Computer Corp.

---

From: Xuan Baldauf <[email-masked]>
Date: Sun, 04 Feb 2001 20:18:33 +0100

> V2/V3 design days, we just lucked out.

I don't think so. See following direntries:

abc
abd
abdb

If the client receives "abc", "abd" and "abdb" as a cookie, what will happen if a
file "abda" was inserted in the meantime?

abc
abd
abda
abdb

You're right, "abda" would not reach the nfs client. This is still legal, but could
be avoided if you use the last name you sent to the client. In such a case, the
cookie of the first packet would be "abd" and in the next run, everything after
"abd" should be returned. I think that this is cleaner.

Note that it does _not_ matter wether a direntry whose name is the cookie filename
exists at the time the cookie filename is used. Consider that "abd" was deleted and
the cookie to be used is "abd", the direntries are following:

abc
abda
abdb

Even if you do not have a file "abd", you can know that "abda" and "abdb" are after
"abd" while "abc" is before. You only need a defined sort order for this.

> recovering from that gracefully.

This is really bad but the only chance for reiserfs to be better in supporting
NFSv3 as it is the case for NFSv2. Only if clients retry readdirs, server may use
NFS3ERR_BAD_COOKIE. Otherwise, this error condition is fairly useless.

>  One nice thing about a change to a variable

Xuân.

---

From: Eric Werme USG <[email-masked]>
Date: Sun, 04 Feb 2001 16:02:24 -0500

> You're right, "abda" would not reach the nfs client. This is still
> legal, but could be avoided if you use the last name you sent to the
> client.

And what would happen if "aaa" were inserted?

 In such a case, the cookie of the first packet would be
> "abd" and in the next run, everything after "abd" should be
> returned. I think that this is cleaner.

> Note that it does _not_ matter wether a direntry whose name is the
> cookie filename exists at the time the cookie filename is
> used. Consider that "abd" was deleted and the cookie to be used is
> "abd", the direntries are following:

> abc
> abda
> abdb
> 
> Even if you do not have a file "abd", you can know that "abda" and
> "abdb" are after "abd" while "abc" is before. You only need a
> defined sort order for this.

You are assuming that either the file system presents filenames is some sort
order (I hope it's compatible with UTF-8) or requiring that the NFS server
read the entire directory and sort it.  If it did that, it might as well
cache it and let the cookie be the item number.  Some file systems, isn't
reiserfs one of them?, are designed to support huge directories.  Requiring
the NFS server sort them seems unlikely to me.  If that were practical, then
Linux's NFS V2 and V3 servers could do that today.

How does reiserfs handle getdirentries/delete/getdirentries?  What does
it track internally to know where to resume?

> This is really bad but the only chance for reiserfs to be better in
> supporting NFSv3 as it is the case for NFSv2. Only if clients retry
> readdirs, server may use NFS3ERR_BAD_COOKIE. Otherwise, this error
> condition is fairly useless.

I'm not certain what you are saying is really bad.  Handling
readdir/delete/readir?  Returning NFS3ERR_BAD_COOKIE?  NFS clients that
can't recover from NFS3ERR_BAD_COOKIE?

	-Ric Werme

---

From: Xuan Baldauf <[email-masked]>
Date: Sun, 04 Feb 2001 22:26:39 +0100

> And what would happen if "aaa" were inserted?

That is why I say that this is still legal, but why should we miss something we are
able to hit? This is just about taste, nothing crucial. :-)

> cache it and let the cookie be the item number.

No, because the NFS server does not know when to forget the cache. The cookie is
defined to be also usable in 20 years when the server resumes operation. Should NFS
servers cache cookies for such a long time? :-)

>  Some file systems, isn't

ReiserFS is AFAIK based on a modified form of B*-trees. All trees have an internal
sort order. For trees, it is cheap to do a lookup by key. It is also cheap and
possible to get the previous or next tree entry for that given key. All you'd have
to do with a variable length cookie is to do a lookup by using the cookie as the key
and return all the entries found after (but not including) the key. This method is
independent of the sort order used, there just has to be one sort order.

> can't recover from NFS3ERR_BAD_COOKIE?

If clients cannot recover from NFS3ERR_BAD_COOKIE (by retrying readdir), the
situation with NFSv3 would not be better than with NFSv2. (And the situation with
NFSv2 is bad.) Only if clients do recover from NFS3ERR_BAD_COOKIE, returning
NFS3ERR_BAD_COOKIE from reiserfs to the nfs client is of use. (The "use" is to be
not bound to hashing filenames but to do stem compression and the like.)

>         -Ric Werme

Xuân. :-)

---

From: Hans Reiser <[email-masked]>
Date: Mon, 05 Feb 2001 00:40:36 +0300

> last filename read, then it may not be there for the next directory read.

Either one could work.  The filename doesn't need to be there for it to tell us
where to continue the read.   The next filename also might not be there....
 
> that's been problematic since the early days of V3 development.

It is very doable, and essential to allowing decent optimizations of
directories.  We are going to delay implementing filename compression in
directories until disributed reiserfs exists primarily because of NFS being a
problem, and even then we will have to make it an option so that those who need
NFS can use it.

Hans

---

From: Xuan Baldauf <[email-masked]>
Date: Sun, 04 Feb 2001 23:22:45 +0100

> problem, and even then we will have to make it an option so that those who need

Maybe a directory format plugin would be desirable. People needing stable NFS use the
hash format (with the various hash algorithms). People needing fast access to their
thousands of subdirectories use alternative formats (e.g. stem compression,
everything you like) at the cost of being not fully NFSv2 compatible (and having a
question mark at NFS in general). The cases where both needs (NFS and large
directories) collide are much more rare than the cases where the current hash format
and large directories do collide.

But be cautious, if you implement directory format plugins, plugins for other things
(like stat data emulator), etc., we can end up in SuperFS. *grin*

Xuân. :-)

P.S.: What will be special with distributed reiserfs? Could a modified|better
samba|smbfs do equal work?

---

From: Hans Reiser <[email-masked]>
Date: Mon, 05 Feb 2001 01:48:24 +0300

> Maybe a directory format plugin would be desirable. People needing stable NFS use the

Yes, that is my intention, you think alike.:)  But it is going to be a lower
priority because
we can't just make it the default.

> XuБn. :-)
Long topic, and it is late, sorry....

Hans

---

From: Hans Reiser <[email-masked]>
Date: Mon, 05 Feb 2001 01:45:06 +0300

> Linux's NFS V2 and V3 servers could do that today.

We aren't saying you should tell filesystems not to use 64 bit byte offsets, we
are saying don't require it, give us variable length cookies we can store
filenames in and other filesystems can store something else in.