Subject: reiserfs and knfsd and NFSv4 and volatile file handles

From: "Neil F. Brown" <[email-masked]>
Date: Wed, 15 Mar 2000 14:10:39 +1100 (EST)

On Thursday March 2, Hans Reiser wrote to linux-kernel (and others) :
> Andi Kleen wrote:
> 
> > 
> > [NFSv4 has volatile file handles that require the client to store the
> > path and relookup when needed, but of course the
> > end result will be even farther away from POSIX semantics as current NFS
> > is already]
> 
> If I am correct in guessing what a volatile file handle is, it sounds like the
> right answer to me, that and changing the posix semantics.  What exactly is a
> volatile file handle?  Does it allow a file handle to go bad and then just
> relookup?  Is it an attempt to cure stale file handles?
> 

and later, Hans Reiser wrote:
> Currently having to find files by something other than a dentry or a filename
> (or a key) uglifies our design.  Even the use of a 64 bit number forces us to
> use fixed length keys which forces us to use hashing which by destroying sorting
> makes it impossible to use stem compression in our directories.  (This affects
> one of our web search engine sponsors who would like for 30 million entry
> directories to fit into RAM in our next major version of reiserfs.) If knfsd
> goes to using dentries to talk to reiserfs, we will be very happy.

I've Cc:ed this to the nfsv4 working group as well.

Maybe I can shed a bit of light.

knfsd cannot just used dentries (internal structures accessed by path
name) to talk to reiserfs as NFS requires it to use "file handles"
which have a maximum length.  To support NFSv2 or v3 you will need to
provide a way to map from a fix-size identifier to a file, that is
stable across rename, write, truncate, reboot.

The volatile filehandles of NFSv4 aim to get around this restriction,
and if you will (one day) be happy to only support NFSv4, not v2 or v3
(once the spec if finalised and the implementations are done and
clients are common...)  then you have more flexability in talking to
NFS.

The NFS client only *needs* a file handle to be stable while it has
the file open.  Having it stable while the client does not have the
file open is at best a convenience for caching.

NFSv4 allows the client to "open" and subsequently "close" a file -
abstractions that absent from NFSv2,3.

NFSv4 allows the server to assert that file handles are stable
(non-volatile, persistant) while a file is open, but that it will
provide no guarantees at other times.

This can work quite well for an MSDOS style filesystem which can use
filehandles based on the file name (E.g. disc address of directory
entry) and which disallows hard links, and disallows unlink or rename
while a file is open.

This should be able to be made to work fairly well for reiserfs too.

As I understand reiserfs (which isn't very deeply), it has an emphasis
on efficient support for lots of small files, and so likes to keep
meta-data and some or all of the data associated with a file in the
directory entry that references the file.
I can imaging that this would mean changing the size of the file,
renaming the file, or even adding files to the directory could all
change the physical location of the meta-data on disc, making it hard
to have a fixed-length, stable index to a file, as needed by NFSv2,3.

A simple minded approach to providing presistant-only-when-open
file handles for reiserfs might be to allocate sequential file handles
and to keep a cache of "filehandle to metadata-disc-address"
mappings. This cache would have to be kept up-to-date whenever a file's
metadata moved.
When a file was opened, the mapping would be marked as 'persistant'
and be logged to stable storage.  On the last close, the mapping could
have the presistant flag removed.

Then the cache could be regularly cleaned of non-persistant mappings,
in an LRU fashion, and any filehandle that is presented which is not
in the cache gets an "NFS4ERR_FHEXPIRED" response.

The logging to stable storage is required so that in the event of a
reboot, the server will still honour open file handles.

As this approach requires logging all opens to disc, it is very likely
to be a performance nightmare.

If we can assume that while the disc address of metadata can change,
it doesn't change very often, then a suitable alternative might be:

- Store a uniquifier in the metadata for each file - an essentally
  random 32-64 bit number.
- Make file handles out of disc-address+uniquifier.
- When an open file has the disc address of its metadata changed, cache
  the old filehandle and the new address both in memory and on stable
  storage.

Then, when a file handle is received, first check the cache.  If it
isn't there, check to see if valid metadata exists at the disc address
and has the given uniquifier.  If it doesn't only then give a
NFS4ERR_FHEXPIRED.

On reboot, you would need to prime the cache from the stable-storage
log.

This should provide the client with the stability it needs, and not
incur too much performance overhead (or does the address of metadata
change a lot?)

I would like the server to be able to tell the client that a
filehandle needs to be updated, and for the client to be able to ask
for an updated copy of a given filehandle - so that entries in the
old-to-new cache could be discarded even while a file was still open,
but that proposal wasn't accepted (yet).

NeilBrown

---

From: "Andi Kleen" <[email-masked]>
Date: Wed, 15 Mar 2000 14:21:30 +0100

> to have a fixed-length, stable index to a file, as needed by NFSv2,3.

Reiserfs has a stable index to a file. It is currently 64bit (32 bit object
ID + ID of the directory). Hans apparently plans to go for longer variable
size keys in the future, although that may not work out given the NFS
limitations. If the 32bit directory key is not available searching the
file is very expensive.

-Andi

---

From: Hans Reiser <[email-masked]>
Date: Wed, 15 Mar 2000 20:39:12 +0300

"Neil F. Brown" wrote:
> on efficient support for lots of small files,

Yes

> and so likes to keep
Not true at the moment, and not the issue.  The issue is that we don't have
on-disk inodes and we don't have inode numbers.  This means that we don't have
fixed allocations of space for inodes, and we can't do lookups by 32bit numbers
for files.

We do have keys, but these are currently 16 bytes and soon will be of variable
length.

Currently we hash filenames as part of constructing keys of fixed length, but
this is ugly and mostly motivated by NFS.

It hurts our performance, and makes directories difficult to compress since stem
compression doesn't work on randomly ordered entries.  Directory entries are
ordered by the hash of the filename currently.  This is bad for performance for
directories too big to fit into RAM, or even moderately large ones.

> filehandle needs to be updated, and for the client to be able to ask

This would definitely be a cleaner architecture that would allow repackers to
not disrupt NFS if they change the key.  We have a repacker in progress.  I can
easily imagine your getting lots of NFS troubles every time the repacker changes
things without having a way to tell NFS that it was changed.

> but that proposal wasn't accepted (yet).

Thanks much Neil.
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email-masked]
> Please read the FAQ at http://www.tux.org/lkml/

-- 
You can get ReiserFS at http://devlinux.org/namesys, and customizations and
industrial grade support at [email-masked].

---

From: Alexander Viro <[email-masked]>
Date: Thu, 16 Mar 2000 01:40:04 -0500 (EST)

> ID + ID of the directory). Hans apparently plans to go for longer variable

Eh? Parse the last part of it, please. How the heck can it be stable upon
rename()? And how does it work with fs/reiserfs/namei.c::reiserfs_link()? 

If you mean that we need ID of parent for knfsd - see our discussion on
that stuff. VFS doesn't need to know parents of non-directories.

Let me ask again:
	a) is your "32 bit object ID" sufficient to
read/write/chmod/truncate/chown the file? Forget VFS, does the thing
contain enough information to do it in principle (aside of scanning the
whole tree, indeed)?
	b) if you have a directory, is its "32 bit object ID" sufficient to
find ID of its parent?
	c) <<---------------------------------------------------------->> to
find the entry of subdirectory with given ID?

If answer to all of those is positive - wonderful. If not - we got a
problem. If you can do it with s/32 bit/64 bit/ - not a big deal, provided
that ID is stable over rename() and depends only on file (== doesn't
depend on which link you are looking at). If you really need to know
parent to perform operations on opened file - you are _deep_ in trouble.

I assume that you _do_ support link(2) - if you don't I would really like
to know what reiserfs_link() does. As in: why it is there and what will
actually happen if you'll start calling it.
								Al

---

From: Hans Reiser <[email-masked]>
Date: Wed, 15 Mar 2000 23:24:49 +0300

> rename()? And how does it work with fs/reiserfs/namei.c::reiserfs_link()?

Not sure I understand your question, but I'll take a stab at it.  Currently the
first directory a file is created in stays its packing locality parent for the
life of the file.  The packing locality parent is the first key component.  So,
currently, if you know the parent directory id the file was created in you know
the first component of the key, and the last component of the key is the offset
which you can also know.  This leaves the middle of the key unknown.  

The immutability of keys is true merely because we don't yet have a repacker to
do re-optimize once a day, and it will change, but for now it is true.  The
first version of our repacker probably won't change keys, but clearly it should
eventually have that functionality.

The notion that keys/objectids should be immutable over the life of the object
is a notion I once believed in but have since conceded was wrong of me.

So, if you create a file in one directory and then access from another
directory, we are as inefficient as using conventional inodes.  At least until
the repacker that has not yet been authored gets written by us....
 
> contain enough information to do it in principle (aside of scanning the
No, we need the directory id plus the objectid (plus the offset) to know what
the key is.
>         b) if you have a directory, is its "32 bit object ID" sufficient to

directories are their own parents as far as constructing keys is concerned in
plan A which is our next version, key construction for the current version puts
directories in the parent of the directory which is an ~10% performance losing
notion of a former project member, sigh.  If 2.4 had been another month or two
out we would have fixed it, such is life....  it will wait for 2.6.

> parent to perform operations on opened file - you are _deep_ in trouble.

If you know the parent it was created in you know the first 32 bits and only
need to know another 32 (plus the offset in the file).  Otherwise you need 64
bits plus the offset.  Note that we already have potential sponsors saying that
4 billion files isn't enough, and that they need more bits for objectids.

> actually happen if you'll start calling it.

link works.:-)  I think I explained the difficult part above, if you need more
detail ask.

>                                                                 Al

Hans

---

From: Alexander Viro <[email-masked]>
Date: Thu, 16 Mar 2000 03:10:01 -0500 (EST)

> which you can also know.  This leaves the middle of the key unknown.  

Ouch. What happens if you
	mkdir foo
	create foo/bar
	rename foo/bar baz/bar
	rmdir foo
and ditto for
	mkdir foo
	create foo/bar
	open foo/bar
	unlink foo/bar
	rmdir foo
- where does your packing locality <whatever> go?

Another question: how does your write_inode() interact with readdir() and
friends on parent? Do they need any sort of exclusion? What kind of
metadata is stored in the directory and is it affected by notify_change()?

One more: suppose you've got
	create foo/bar
	link foo/bar baz/bar
	unlink foo/bar
	create foo/quux		unlink baz/bar
Do the last two of them need any sort of exclusion? VFS _does_ allow the
last two happen at the same time. You have big lock, but if one of them
blocks (and you are very unlikely to avoid that) - that's it.

The reason why I'm asking is that I've done a filesystem with metadata in
directory and I know what kind of PITA it can become. _And_ I've dealt
with a monster that keeps metadata in directory trying to support links.
In case if you wonder - it's AFFS. It's racey as hell and basically I'm
trying to figure out how did you solve the same set of problems. 

> eventually have that functionality.

And how do you expect NFS to handle that?

> is a notion I once believed in but have since conceded was wrong of me.

	Unfortunately, NFS can't survive without that. POSIX also requires
constant inumbers, BTW.

> No, we need the directory id plus the objectid (plus the offset) to know what

What's the size of key?

> out we would have fixed it, such is life....  it will wait for 2.6.

Wait a minute. Assume that somebody gave you the key of directory. Can you
find the key of its current parent? Notice that it could very well be
renamed since the moment of its cretion.

> link works.:-)  I think I explained the difficult part above, if you need more

Erm... I need details on the locking you use within your tree. This scheme 
has a huge potential for hidden (and hard to hit unless you know what you
are hunting for) races, unless you are very accurate with that stuff. One
more thing that began to scare me - readdir() and offsets in directory.
How do you do them?
								Al

---

From: "Andi Kleen" <[email-masked]>
Date: Thu, 16 Mar 2000 12:02:39 +0100

> - where does your packing locality <whatever> go?

The packing locality is saved in each directory entry and in the 
in core inode.

> metadata is stored in the directory and is it affected by notify_change()?

No metadata in directories (there are comments in the code that say
that they plan to change that in the future, but I have my doubts
if it is really a good idea) 

> trying to figure out how did you solve the same set of problems. 

reiserfs does not have metadata in directories. The directories are just
like ordinary unix directories being basically a special kind of file with
points to other objects in the tree.

> And how do you expect NFS to handle that?

He can't. Unix also cannot handle changing inodes (objectids in reiserfs speak).
Oh well, not all future plans work out.

> > No, we need the directory id plus the objectid (plus the offset) to know what

Currently 12 bytes (packing locality, object id, offset). Offset is fixed
if you just want to find a file (and implicit in NFS anyways). It is also
fixed if you want to e.g. find the .. of a directory.  So the NFS 
fh needs to store 8 byte.

> renamed since the moment of its cretion.

Sure. Just look for (parent, directoryid, DOT_DOT_OFFSET) and read the 
full parent key from the directory entry.  It is really like Unix in
this regard.

> more thing that began to scare me - readdir() and offsets in directory.

That is what they use all the ugly "has rescheduled" flags for. The entry
also has a "recently deleted" flag that is checked (hidden). When the tree
is rebalanced inbetween they catch that with a relookup (because offset
stays a fixed position). When you insert new entries before the current
filldir offset inbetween you lose (but standard ext2 is no better in that
as far as I can see). In the 2.3 version they use generation counts for
most things, so they can more easily find out if a object changed.
As far as I can see the reiserfs readdir handles all races the ext2
readdir handles.

[Note that I'm no reiserfs hacker, that just came from my own reading
of the source. Maybe it is better you apply the patch and do some
real RTFS ;]

-Andi 

P.S.: The loopback device in 2.3.51 seems to be still very unstable
when accessing block devices.  I get weird hangs all the time. It 
looks like it is leaking some important inode semaphore or similar, 
because all new processes hang and then the remaining processes
start to block one after another as they try to do file system
accesses.

---

From: "Andi Kleen" <[email-masked]>
Date: Thu, 16 Mar 2000 12:08:43 +0100

> Currently 12 bytes (packing locality, object id, offset). Offset is fixed
            ^^
This should be 16 bytes in the 2.3 version, because offset is 64bit.
2.2 has 12 bytes.

-Andi

---

From: "Manfred Spraul" <[email-masked]>
Date: Thu, 16 Mar 2000 20:32:22 +0100

From: "Hans Reiser" <[email-masked]>
> No, we need the directory id plus the objectid (plus the offset) to know
what
I'm not sure if I understood your post:
does "directory id" mean the id of the directory the entry was initialy
created in? So the inode number of the current directory doesn't help?

knfsd currently stores the following members in the nfs handle: [fh_compose
in linux/fs/nfsd/nfsfh.c]

        fhp->fh_handle.fh_dirino = ino_t_to_u32(parent->d_inode->i_ino);
        fhp->fh_handle.fh_dev    = kdev_t_to_u32(parent->d_inode->i_dev);
        fhp->fh_handle.fh_xdev   = kdev_t_to_u32(exp->ex_dev);
        fhp->fh_handle.fh_xino   = ino_t_to_u32(exp->ex_ino);
        fhp->fh_handle.fh_ino = ino_t_to_u32(inode->i_ino);
        fhp->fh_handle.fh_generation = inode->i_generation;

fh_xino is needed internally to check the security
fh_dev is needed to find the superblock.
fh_dirino ==NULL is used internally by knfsd.
fh_ino is the inode number. IIRC POSIX mandates that the 32-bit number is
unique and never 0?
fh_xdev is unused [was used for the sun emulation]
fh_generation is for uniqueness.

What about adding an explicit "get_persistant_id()" function pointer to
inode_operation?
it returns an 80-bit block.
knfsd stores it instead of fh_xdev, fh_dirino, fh_generation in the handle.
It might be possible to extent it to 96 bits, I don't understand when
fh_dirino is set to NULL.

Each filesystem must support "from superblock to dentry/in-memory inode"
with that 80-bit block and the 32-bit inode number of the entry.

> >         b) if you have a directory, is its "32 bit object ID" sufficient
to

given what? super block, in-memory inode?

If I'm correct, then a filesystem must
* get the parent of a directory [given the in-memory inode] with 0-bits
additional information.
* get the parent of a non-directory with the same 112 bits.

So VFS+knfsd need:
* super_block operation: go from 10 bytes + inode number to in-memory inodes
of both entry + it's parent.
* inode operation: get the 10-byte persistant id.
* inode operation, only supported for directories: get the parent.

I would prefer if VFS never uses the inode number for any lookups.

> >         b) if you have a directory, is its "32 bit object ID" sufficient
to

where do you need that?
IMHO
    super_operations->get_dir_inode(dentry->inode->i_dirino)
is a bad idea,
    dentry->inode->i_ops->get_parent();

gives far more flexibility to the filesystem. get_parent returns -ENOTDIR if
you try to get the parent of a file.

--
    Manfred

---

From: Alexander Viro <[email-masked]>
Date: Thu, 16 Mar 2000 15:39:59 -0500 (EST)

> as far as I can see). In the 2.3 version they use generation counts for

ext2 relies on directory being locked during readdir(). I'm not sure that
I understand what you mean. Notice that ext2_readdir() used to have a
nasty race - it checked for ->i_version (which is constant), but failed to
check for ->f_version (which can change along with ->f_pos if somebody
does lseek() on descriptor of the same struct file). So it didn't redo the
sanity checks on ->f_pos if somebody did lseek() and that gave a fairly
nasty DoS - ext2 decided to remount the thing r/o, since it thought that
on-disk structure was fucked.

> of the source. Maybe it is better you apply the patch and do some

<shrug> if you know how to pack more than 100-odd working hours into the
week - share, lot of people will be very grateful.

> start to block one after another as they try to do file system

Hmm... That's the path I didn't change at all. I'll look at it. Sigh...

---

From: Hans Reiser <[email-masked]>
Date: Thu, 16 Mar 2000 23:29:41 +0300

> Ouch. What happens if you

packing locality is foo.

> - where does your packing locality <whatever> go?

packing locality is foo

> And how do you expect NFS to handle that?

I don't.  NFS v4 guys should listen to Neil.

>         Unfortunately, NFS can't survive without that. POSIX also requires

It is bad design to require it.  Currently we provide it, but it is bad design. 
It appears to be something fundamental that you cannot change access patterns,
and have a fixed id, and avoid adding a random I/O to a usage pattern that could
otherwise be optimized for by a clever repacker that could optimize that I/O
away by packing the object with other objects it is accessed with.  I was forced
to concede this many years ago by clever persons working for me.  I wanted
immutable objectids, they clean things up so nicely in the architecture. 
Mutable ids require what is effectively two way linking.  I lost the argument.

Thanks for being helpful to us despite a rocky start to our relationship.

I believe your other questions were answered in other emails, not all by me. 
Correct me if I err in this.

Hans

---

From: Alexander Viro <[email-masked]>
Date: Fri, 17 Mar 2000 20:32:33 -0500 (EST)

> > Ouch. What happens if you

Even though inode of foo is gone? OK, fine with me. Do you mean that your
"locality" is roughly an equivalent of cylinder group on FFS?

> Correct me if I err in this.

Umm... I'd still like to hear a description of your internal locking. In
particular, what do you lock/release upon reiserfs_find_entry()/pathrelse()?
When do you rebalance the tree? How do you do serialization between that
and things a-la write_inode()/readdir()/lookup()? Currently locking is
masked by the VFS one and that's one of the reasons why I want to see
cleaned variant.

---

From: Hans Reiser <[email-masked]>
Date: Sat, 18 Mar 2000 14:29:58 +0300

> "locality" is roughly an equivalent of cylinder group on FFS?

The objects in the tree are fully ordered by their keys.  The packing locality
is the first component of the key.  The bitmap.c algorithms, when assigning
blocks to nodes of the tree, put new nodes in the first free block after the
block holding the left neighbor in this tree ordering of the new node.

> > Correct me if I err in this.

I leave the below for Alexei and Vladimir to answer in detail.  Generally
speaking, we can only do clean effective SMP after implementing per buffer
seals.  I see that as unlikely to make it into 2.4 due to it requiring a per
buffer/page fs specific struct, but it is actively being coded by Zarochentcev
and Roma.  If 2.4 is slow enough in coming out, maybe we will submit it just in
case Linus will take it.  Our SMP will be poor until we have it.

---

From: "Stephen C. Tweedie" <[email-masked]>
Date: Mon, 20 Mar 2000 18:21:19 +0000

> It is bad design to require it.  Currently we provide it, but it is bad design. 

Unfortunately a lot of existing applications require it.  "cp" and "tar", 
for example: if you use a "cp -a" or a tar over hard links, it is the 
unique (filesystem, inode number) identifier for the file which allows
hard links to be identified.

If you abandon the existence of such an identifier, then how can tar 
maintain the current behaviour?

--Stephen