AFS filesystem for Linux (2/2)

Are you sure this is the right way to go?

As far as I can tell, this is a dead end, because we fundamentally cannot do the local backing store from the kernel.

whole lot more sensible to implement it as a coda client or something like that (with the networking support in-kernel, but with the caching logic etc in user space).

I dunno, I just get the feeling that a good AFS client simply cannot be done entirely in kernel space, and if you start off like this, you'll never get where you really want to go. Pls comment on this (and yeah, the comment can be a "Boy, you're really a stupid git, and here's why: xyz", but I really want the "xyz" part too ;)

Now, admittedly maybe the user-space deamon approach is crap, and what we really want is to have some way to cache network stuff on the disk directly from the kernel, ie just implement a real mapping/page-indexed cachefs that people could mount and use together with different network filesystems.

Linus

I think so. I think it makes sense for the AFS VFS-interface to go as directly as possible to the network without having to make context switches to get into userspace.

I disagree. I think we can (besides which OpenAFS does so), and that most of it is probably easier to do here than in userspace. For example:

(*) Readpage

The filesystem can either use a BIO to read directly into a new page if the page is already in the cache, or it can read from across the network, and then use a BIO to write the updated page into the cache. This should avoid as much page-aliasing as possible.

(*) Writepage

The filesystem can use a BIO to write a page into the cache, whilst simultaneously dispatching it across the network. Alternatively, it can write the page to the cache (fast) immediately and queue it up to be sent across the network (slow) from the cache if memory pressure is high.

(*) Index searching

The cache needs to keep an on disc index if the contents are to survive rebooting. This can be searched more efficiently from within the kernel.

I've written a scanning algorithm that can scan any file for fixed length records in a manner that allows the disc blocks to be scanned in whatever order they come off of the disc. This should make scanning the index files faster, and may not actually be possible in userspace.

(*) On-disc file layout

The on-disc file layout I'm using is the same as many other unix filesystems (direct, indirect and double-indirect block pointers) and is fairly simple. The biggest difference where I see a hole, I know I have to fetch the page from the server, rather that just assuming there's an implicit empty page there.

I'm fetching files a page at a time (on demand from the VM), though I may extend this to get bunches of pages for efficiency reasons.

What I'm not going to do is fetch each file into the the cache and maintain it there in its entirety from the moment it is opened to the moment it is closed. This has two definite disadvantages: you can't open a file bigger than the remaining space in the cache, and the size of the cache and the sizes of the files opened limits the number of files you can have open.

Currently my plans are not to support disconnected operation (as there are likely to be holes in the files cached). This means that I don't need to cache security information on disc, since I can "retrieve" it from the server upon opening a file anyway.

One thing I'm currently undecided on is whether the security tokens for a user should be attached to the struct file * being used, or whether they should be retrieved from a list attached to the current process in some way.

See above.

As has been suggested to me, it may be possible to unload just the space reclaimation algorithm to userspace. It may also be possible to put the index maintainer in userspace, and have afs_iget() call it to search for and add records. "Callbacks" from the server (which indicate that a file has changed in someway) could also be passed to the index maintainer so that is can release all the cache blocks for the changed file.

However, the biggest problem with splitting the caching like this is that there then has to be some sort of locking between kernel space and userspace to govern access to the allocation bitmaps (or whatever).

Arjan Van de Ven's suggestion is that all the cached data files should be exposed as files in the cachefs, which then would have an unlink method available so that the userspace daemon can tell the kernel side cache manager to reclaim a particular file.

I think it can (and should) be done in the kernel (at least for the most part
- there are auxilliary userspace tools that consult the server directly). See the reasons given above.

Hmmm... Interesting idea. There is the problem of working out which files belong to what source. The AFS filesystem has a three tier approach to identifying the source of a file: {cell,volume,vnode}, where any given volume can be on more than one server in a particular cell, and a vnode is the equivalent of an inode. I suppose NFS, say, could be handled similarly:
{server,export,inode}, and SMB would probably be {server,share,filename}.

The biggest hurdle here is the difference in potential record lengths:-/

CELL RECORD CONSISTS OF
AFS 64 + 16*4 name + 16 volume location servers
NFS 4 IPv4 address
SMB ? server name (maybe just IP address)

VLDB RECORD CONSISTS OF
AFS 64 + 64 volume name, numbers and server info
NFS 4096? export path length
SMB ? share name

VNODE INDEX CONSISTS OF
AFS 4 + 4 vnode ID number, vnode ID version
NFS 8 inode number
SMB 4096? full file name within share
or SMB 4 + 256 cache dir index and filename

To have a heterogenous cache, the VLDB record and vnode index records could be extended to 2K or 4K in size, or maybe separate catalogues and indices could be maintained for different filesystem types, and a 0th tier could be a catalogue of different types held within this cache, complete with information as to the entry sizes of the tier 1, 2 and 3 catalogues.

David

THE CACHE LAYOUT
================

The local cache will be structured as a set of files:

(1) Meta-data file. Contains meta data records (~=inodes) for every "file" in the cache (including itself).

Each meta-data record contains a set of direct block pointers, an indirect block pointer and a double indirect block pointer by which the data to which it points can be located on disc.

There will always be enough direct pointers to refer to all the blocks in a directory directly.

(2) Cell cache catalogue. Any cell for which we have data cached will be recorded in this file.

(3) Volume location catalogue. Any volume for which we have data cached will be recorded in this file. Each VL entry points to the cell record to which it belongs.

(4) A set of indexes (hash table type thing) with fixed size records as small as I can make them that cross-reference a volume location and a vnode number with an entry in the meta-data file that describes where to find the cached data on disc.

Index entries are also time stamped to show the last time they were accessed.

(5) The cached vnodes (files/dirs/symlinks) themselves.

Note that in the case of a cached file, any hole in the file _actually_ represents a page not yet fetched from the server.

There is also a bitmap to indicate which blocks are currently allocated.

I wasn't planning on storing user accessiblity data in the cache itself, though I can always change my mind later, because this differs from user to user, and is subject to change without notice from one attempt to read to another due to the lack of notifications from the protection server when ACLs change. This sort of thing will have to be stored in each "struct file".

So you want to eventually link kerberos into the kernel to get the security right?

Coda 'solves' the page-aliasing issues by passing the kernel the same file descriptor as it is using itself to put the data into the container (cache) file. You could do the same and tell the kernel what the 'expected size' is, it can then block or trigger further fetches when that part of the file isn't available yet.

We don't need to do it at such a granualarity because of the disconnected operation. It is more reliable as we can return a stale copy when we lose the network halfway during the fetch.

Hmm, a version of AFS that doesn't adhere to AFS semantics, interesting. Are you going to emulate the same broken behaviour as transarc AFS on O_RDWR? Basically when you open a file O_RDWR and write some data, and anyone else 'commits' an update to the file before you close the filehandle. Your client writes back the previously committed data, which it has proactively fetched, but with the local metadata (i.e. i_size). So you end up with something that closely resembles neither of the actual versions that were written.

Can you say hack. Different underlying filesystems will lay out their data differently, who says that ext3 with the dirindex hashes or reiserfs, or foofs will not suddenly break your solution and still work reliable (and faster) from userspace. When you can a file from userspace the kernel will give you readahead, and with a well working elevator any 'improvements' you obtain really should end up in the noise.

Intermezzo does the same thing, they even proposed a 'punch hole' syscall to allow a userspace daemon to 'invalidate' parts of a file so that the kernel will send the upcall to refetch the data from the server.

VM/VFS will handle appropriate readahead for you, you might just want to join the separate requests into one bigger request.

And one definite advantage, you actually provide AFS session semantics.

And my current development version of Coda has {cell,volume,vnode,unique} (128 bits), which is the same size as a UUID which was designed to have a very high probability of uniqueness. So if I ever consider adding another 'ident', I'll just switch to identifying each object with a UUID.

How about IPv6?

Or you could use a hash or a userspace daemon that can map a fs-specific handle to a local cache file.

Jan

I just thought of the fh_to_dentry stuff that is used by knfsd. Those fh keys should be just the right (and fs independent) thing to index such a generic fs-cache with.

Jan

Hi Jan,

True. But how should I tell when a page isn't available yet, if I do as Coda appears to do and directly use a file on another local filesystem (for Coda, this doesn't matter since it maintains the entire file in its cache).

As for writing, surely Coda's solution is even worse? Since the pages in question are "owned" by the backing cache file as far as the VM is concerned, and all writes to a Coda file are ducted directly through to the backing cache file, how do you (a) tell when the file has changed, and (b) tell which bits of the file need to be sent back to the server? Do you send the entire file back every time it gets changed? Do you keep a copy and "diff" the two?

This appears to be a flaw in the protocol, and it's going to be a problem, no matter where the writes are done.

David

Yeah, you could say I'm pretty much responsible of where we're going with Coda nowadays. Don't know whether that's a good thing, because I can be a bit stubborn on some things sometimes ;)

The challenge response then might the same as Coda's, a modified needham-schroeder handshake based on a shared secret which in your case is obtained through kerberos. But I thought Kerberos was better integrated in AFS and they actually were even using krb encryption for the rxrpc packets (i.e. how are packets kept secure after the handshake)

If not kerberos, at least some for of encryption. IP/Sec would need the same things.

We don't. Coda has the all or nothing fetch. When we get an open upcall and the file isn't cached we get the whole file, and return the filehandle we just used to fetch the file, that way even when pages haven't been flushed to disk yet, the kernel will see the same data. All reads and writes are wrapped in such a way that readpage and writepage directly access the cache file, when an mmap is active the Coda inode isn't even touched anymore.

Correct, but it is part of the Coda semantics, while disconnected from the network/servers you are given the last cached version of a file.

Actually, throwing out the old copy is still done, but I consider that a bug. And from numerous reports I've seen, others consider it a bug as well. That is mainly because people who use Coda actively at some point start to expect Coda's semantic model and know that when they open a file that is cached they should get something, even when the wire is pulled (or the server dies).

Pretty much, but we need that extra space for the disconnected writes anyways, that way we can always roll back to a consistent version.

Ok, traditional AFS semantics is 'session semantics'. Very strict, whenever you read from a file, everything is consistent wrt. the time you opened the file. Whatever you write isn't committed on the server until you close the file. This model has great advantages such as minimizing network traffic, giving lock free read/write consistency.

The problems with the model are, you might be looking at stale data, or you might overwrite someone elses changed (last writer wins). To avoid the first you would need to reopen the file regularily, to avoid the second you need to lock files.

However, once AFS became commercial, there was a lot of pressure from new users to provide something more similar to UNIX semantics. So whenever a callback was received from the servers, and the file was open for reading, the client would pull in the latest version. That way processes (shared databases?) didn't need to do close/open to see new updates. (oops, lost the read consistency)

Now people started throwing big databases in the filesystem, and the cache issues became important. So they introduced 'chunked access', dirty chunks are still written when the file is closed, but also when the cache is full (oops, lost write consistency).

When a file is open for both reading and writing you get effects like the one I described above. With a full cache on the writing side you can imagine even more interesting interactions, where we end up with a file that contains alternating 64KB blocks of both files. So the nice combination of these two subtle changes made the AFS3 file system in my opinion unreliable and unusable, ofcourse all of this can be avoided by locking the file, but in that case the original semantics were probably already more than sufficient.

You don't have the choices if you are trying to implement an AFS compatible filesystem.

That would be sufficient. But you _really_ need to block during the final close operation when you have to make sure the data is on the server before returning.

As far as I know this is impossible without changing the existing AFS servers.

Doesn't AFS3 give callbacks when it updates a chunk of the file? I guess it still has retained at least that part of the original semantics, send callbacks when the file is closed (and the data is 'officially' committed). It is still up in the air what clients see that read the file between the chunked writes and the actual file close.

Disconnected operation has never been 'AFS semantics'. That's a Coda thing.

A Coda cell is simply a FQDN, whenever the userspace cachemanager accesses a new cell it a locally unique ID, which will exist as long as there are objects from that cell in the cache.

Why would it probably be swapped out to disc? If you're really worried about that you could mlock the memory. And if you think that is too expensive, it is still better to mlock memory in userspace that to allocate that same memory in kernel space.

Yeah, that's why Coda is using a recoverable VM, basically a mmapped file with an log where modifications are recorded so that we can replay/rollback uncommitted operations when we're restarting.

Jan

> If not kerberos, at least some for of encryption. IP/Sec would > need the same things.

NFSv4 does indeed require the full kerberos encryption stuff in the kernel. The RFC specifies that krb5 support is a minimum requirement, and we will expect to have that in 2.6 (or 3.0 or whatever it's called these days...)

Cheers,
Trond

Might this be something I can make use of for my AFS filesystem too?

David

> Might this be something I can make use of for my AFS filesystem > too?

Possibly. Our intention is to integrate the RPCSEC_GSS security protocol (see RFC2203) into the sunrpc code, then use krb5 as one of the authentication flavours.

Whereas I doubt that AFS uses RPCSEC_GSS, I believe that the kerberos code itself (+ upcall mechanism for getting user tokens etc.) could be reused by you. I presume that you would make use of the sunrpc code too?

Cheers,
Trond

I would if I could, but RxRPC is a sufficiently different protocol to make that impractical:-/

David

> I would if I could, but RxRPC is a sufficiently different > protocol to make that impractical:-/

How badly does it differ? If you are talking only about a couple of differences in the RPC headers, then that is something that can easily be overcome...

Cheers,
Trond

There appears to be more to it than that. RxRPC has sequencing and ACKing windows and things that I don't think SUNRPC has (basically it tries to do some of TCP itself). I've attached the struct definitions for the RxRPC header and the ACK packet body from my RxRPC implementation for your reference.

Furthermore, RxRPC allows for big binary blobs to be interpolated in the middle of packets (though if I understand it correctly it effectively encodes them as an XDR octet array of sorts).

David

struct rxrpc_header

{
	u32	epoch;		/* client boot timestamp */

	u32	cid;		/* connection and channel ID */

#define RXRPC_MAXCALLS 4 /* max active calls per conn */
#define RXRPC_CHANNELMASK (RXRPC_MAXCALLS-1) /* mask for channel ID */
#define RXRPC_CIDMASK (~RXRPC_CHANNELMASK) /* mask for connection ID */
#define RXRPC_CIDSHIFT 2 /* shift for connection ID */

u32 callNumber; /* call ID (0 for connection-level packets) */
#define RXRPC_PROCESS_MAXCALLS (1<<2) /* maximum number of active calls per conn (power of 2) */

u32 seq; /* sequence number of pkt in call stream */
u32 serial; /* serial number of pkt sent to network */

u8 type; /* packet type */
#define RXRPC_PACKET_TYPE_DATA 1 /* data */
#define RXRPC_PACKET_TYPE_ACK 2 /* ACK */
#define RXRPC_PACKET_TYPE_BUSY 3 /* call reject */
#define RXRPC_PACKET_TYPE_ABORT 4 /* call/connection abort */
#define RXRPC_PACKET_TYPE_ACKALL 5 /* ACK all outstanding packets on call */
#define RXRPC_PACKET_TYPE_CHALLENGE 6 /* connection security challenge (SRVR->CLNT) */
#define RXRPC_PACKET_TYPE_RESPONSE 7 /* connection secutity response (CLNT->SRVR) */
#define RXRPC_PACKET_TYPE_DEBUG 8 /* debug info request */
#define RXRPC_N_PACKET_TYPES 9 /* number of packet types (incl type 0) */

	u8	flags;		/* packet flags */

#define RXRPC_CLIENT_INITIATED 0x01 /* signifies a packet generated by a client */
#define RXRPC_REQUEST_ACK 0x02 /* request an unconditional ACK of this packet */
#define RXRPC_LAST_PACKET 0x04 /* the last packet from this side for this call */
#define RXRPC_MORE_PACKETS 0x08 /* more packets to come */
#define RXRPC_JUMBO_PACKET 0x20 /* [DATA] this is a jumbo packet */
#define RXRPC_SLOW_START_OK 0x20 /* [ACK] slow start supported */

u8 userStatus; /* app-layer defined status */
u8 securityIndex; /* security protocol ID */
u16 _rsvd; /* reserved (used by kerberos security as cksum) */
u16 serviceId; /* service ID */

} __attribute__((packed));

struct rxrpc_ackpacket
{
u16 bufferSpace; /* number of packet buffers available */
u16 maxSkew; /* diff between serno being ACK'd and highest serial no received */
u32 firstPacket; /* sequence no of first ACK'd packet in attached list */
u32 previousPacket; /* sequence no of previous packet received */
u32 serial; /* serial no of packet that prompted this ACK */

u8 reason; /* reason for ACK */
#define RXRPC_ACK_REQUESTED 1 /* ACK was requested on packet */
#define RXRPC_ACK_DUPLICATE 2 /* duplicate packet received */
#define RXRPC_ACK_OUT_OF_SEQUENCE 3 /* out of sequence packet received */
#define RXRPC_ACK_EXCEEDS_WINDOW 4 /* packet received beyond end of ACK window */
#define RXRPC_ACK_NOSPACE 5 /* packet discarded due to lack of buffer space */
#define RXRPC_ACK_PING 6 /* keep alive ACK */
#define RXRPC_ACK_PING_RESPONSE 7 /* response to RXRPC_ACK_PING */
#define RXRPC_ACK_DELAY 8 /* nothing happened since received packet */
#define RXRPC_ACK_IDLE 9 /* ACK due to fully received ACK window */

	u8	nAcks;		/* number of ACKs */

#define RXRPC_MAXACKS 255

	u8	acks[0];	/* list of ACK/NAKs */

#define RXRPC_ACK_TYPE_NACK 0
#define RXRPC_ACK_TYPE_ACK 1

} __attribute__((packed));

> There appears to be more to it than that. RxRPC has sequencing > and ACKing windows and things that I don't think SUNRPC has > (basically it tries to do some of TCP itself). I've attached > the struct definitions for the RxRPC header and the ACK packet > body from my RxRPC implementation for your reference.

The 'socket protocol' stuff already copes with UDP w/ congestion control + TCP. It will eventually do SCTP and IPv6 when we get down to it all.
Fitting UDP w/ sequencing+acking as an extra protocol should be possible, and in fact support for sequencing is needed anyway for the security code in RPCSEC_GSS.

The nice thing about the SunRPC code is that it provides a generic engine for sending and receiving messages asynchronously. For the client, the SunRPC specific stuff is almost all in net/sunrpc/clnt.c. If you write a replacement for that in order to deal with the RxRPC quirks, you should still be able to make use of rpciod and the socket + auth code.

Ditto for the server stuff: nobody forces you to use svc_process to interpret the RPC headers.

> Furthermore, RxRPC allows for big binary blobs to be > interpolated in the middle of packets (though if I understand > it correctly it effectively encodes them as an XDR octet array > of sorts).

The RPC layer doesn't worry too much about the contents of the data you send. We're already interpolating pages into our RPC messages...

Cheers,
Trond

Interesting idea. What do you mean by an extra protocol exactly? An extra IPPROTO_xxxx option as might be passed to socket()?

My RxRPC implementation currently does all the incoming message management and routing in process context in a worker thread.

The following details have to be resolved wherever it is done:

(*) RxRPC calls (operations) may be aborted or rejected.

(*) RxRPC packets have to be ACK'd/NAK'd and maybe resent. ACK packets may
ACK or NAK multiple data packets.

(*) RxRPC packets have their own "connection number" and "channel number" and
"call number" spaces on top UDP port numbers, thus require multi-tier routing.

(*) An operation (a "call") may get challenged or may be challenged for
security details in the middle of transmission or reception.

(*) RxRPC packets may get merged together and placed into one UDP
packet. They then have to be split and processed individually upon reception.

I don't see that there should be a problem with the first three (after all, TCP does all of them). The fourth may be the trickiest, but that may also be the one NFSv4 has to deal with.

It's not entirely clear as to how to use it.

That's useful. I also pass pages to my rxrpc receive data routine to copy into directly from skbuffs, but I don't see that being a problem.

David

Does NFSv4 involve caching? If so, might working out a common cache API be of use to you?

David

> Does NFSv4 involve caching? If so, might working out a common > cache API be of use to you?

NFSv4 does not specify that files need to be backed by local storage the way AFS does if that is what you mean. However it does offer AFS-like features (such as file delegation / leases) that make a cachefs a much more feasible proposition.

I, for one, would be very interested in seeing a cachefs add-on for NFSv4. I think that it would be of great use for GRID / distributed computation applications, which is where my personal interest in NFSv4 lies.

Cheers,
Trond

Can you give me some sort of idea as to what keys I might use for indexing?

For instance, AFS has the following:

PRIMARY KEY SIZE AUXILLIARY DATA IN INDEX
============== ============== ============================
cell name up to 64 ASCII - volume location database
server addresses

volume ID 32-bit number - name of volume
- associated keys
- fileserver addresses

vnode ID 32-bit number - access time
- vnode metadata record pointer
- vnode ID version
- vnode data version
- modify time
- size
- data block pointers

Each index entry of course has a pointer back up the hierarchy.

Furthermore, to determine whether a cached file's contents are still valid, I can compare the the vnode ID version and vnode data version numbers against the server.

Not all these indices and keys will necessarily be useful for NFS.

David

We will also need kerberos for Lustre when we start implementing security. We will be using the GSSAPI for security, so basically the same as what AFS is using.

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

Hi Jan,

So, say you've got a really big file in your cache. Someone changes a single byte in it. You can work out that the file has changed by one of a number of means. How do you avoid having to throw the entire file back to the server?

How do you sync up with the server on reconnection? This is similar to the problem you pointed out that I have to solve - how to deal with the file on the server being changed by another client whilst I'm also trying to write to it.

Whatever model you choose, you have to accept some compromises.

The model I'm thinking of is as follows:

(*) Data that the client doesn't have immediately to hand (ie is not yet
cached) it fetched a chunk at a time upon request of the VM (thus allowing data readahead to be driven by the VM).

(*) All data cached by a client for a particular file is zapped if I get a
callback from the server and/or the data version number of that file appears to have changed.

(*) In O_SYNC mode, data is written back to the server as promptly as
possible within the write() call (maybe through the auspices of prepare_write and commit_write).

(*) In non-O_SYNC mode, I would like the data to be written back through the
page cache's writepage() routine(s). By setting the dirty bits on pages, the write will be scheduled by the VM at some point. This would permit better write coelescing locally. However, security becomes a problem, since I have to say to the server which user I'm doing a store as, and if the data is coelesced from writes done as several different users, then there could be a problem if the store is rejected.

How does Coda deal with this security problem?

I admit there are a number of problems with this model that might be alleviated by better operations being available in the AFS spec (such as data insertion without having to nominate a new EOF position, and data appending without needing to know the old or specify a new EOF position.

Anyone using a network filesystem of any type to store a big databases is probably just asking for trouble. IMHO they're far better off talking to a distributed DB through its own network access protocol. But that's besides the point.

It can be done entirely in the client, provided it has a copy of the unmodified page still in its cache.

All it says is that a given file has changed. It doesn't provide a clue as to where. Hence the entire file has to be flushed.

I didn't say it was. It's explicitly denied in the AFS docs, though it's discussed under the future developments section.

The 32-bit ID still has to be mapped through a catalogue somewhere (may be a text file that the cache manager reads on starting), and if the catalogue is external to the cache, the catalogue may change what the ID corresponds to without the cache being invalidated.

I'm storing mine on disc as do normal disc-based FS's. That means it can be a lot bigger. Besides, you don't really want to mlock memory or store it in the kernel - that would be a big chunk of memory permanently committed and unavailable for other uses.

What's "VM" in this context?

David

Coda actually writes the whole file back. Someone was working on an rsync based method, but I haven't heard anything for a while. It is actually mostly databases that update single bytes in large files. Anything like a text editor will move the original file to a backup copy and write a new version anyways. Compilers tend to throw away the old object files and create a new file, etc.

We automatically resolve directory conflict, file conflicts are 'punted' to userspace. There is a manual repair tool, where a user can pick the version that he believes is the most appropriate, or he can substitute a replacement or merged copy.

There is also a framework for application specific resolvers, these can try to automatically merge f.i. calendar files, or email boxes, or remove/recompile object files when there is a conflict, etc.

For AFS you don't have to care, it's semantics without locking are that the 'last writer to close it's fd' wins.

I thought you were implementing AFS, how can you choose your model?

...

How about dirty data, that was locally modified? There is a network latency that comes into play here. If you want last writer wins you should not zap dirty data.

So other clients will read inconsistent data if they don't have that chunk cached. And if the server generates callbacks on the write of a chunk, all clients see the update?

Ehh, access permissions should already be checked when the file is opened. NFS is dealing with the same problems here.

What problem? If you don't have write permission you can't write to the file. If you do have write permissions you can write. When the last writer closes it's filehandle the data is sent to the server with his permissions.

Now if the ACL is changed on the servers before the close so that this last writer loses write access we get a 'conflict' that is punted to userspace, similar to the case when writing to an already updated file.

So I store it in VM on the disk and you store it in your private FS on disk. Looks like the same thing to me, except I get to enjoy the benefits of the page/swapcache keeping the data in memory when it is frequently used without having to do anything smart.

Virtual Memory. A private mmap of a file. Updates dirty the pages, so they end up in swap, but we log the same update in a logfile (journal), when the log fills up, the changes written directly to the underlying file. Optionally, when we know that the swap copy and the file copy of the page are identical, the page is remapped to reduce swap usage. That is where we store all the metadata and the Coda file -> cache file mappings so that they can survive a reboot or system crash.

Jan

Hrrm, well, I'm in the middle of deploying AFS (moving away from NFS), and one of the ideas I toyed with was how to get a diskless AFS client. (yeah, that sounds silly at first, 2GB disks used to be large, not systems with 2GB of ram are common.) A mostly kernel-based implementation of AFS would be quite usefull for this. (and the remaining bits could be in an initramfs)

Troy Benjegerdes | master of mispeeling | 'da hozer' |  [email protected]
-----"If this message isn't misspelled, I didn't write it" -- Me -----
"Why do musicians compose symphonies and poets write poems? They do it
because life wouldn't have any meaning for them if they didn't. That's 
why I draw cartoons. It's my life." -- Charles Schulz

My client will be able to run without using any cache other than the pagecache (as it does now).

David

Linus> Now, admittedly maybe the user-space deamon approach is Linus> crap, and what we really want is to have some way to cache Linus> network stuff on the disk directly from the kernel, ie just Linus> implement a real mapping/page-indexed cachefs that people Linus> could mount and use together with different network Linus> filesystems.

Cachefs has been on our most wanted list for a while now in Linux
biocomputing.. Using NFS for huge datasets with cachefs on Solaris is a breeze and Linux currently offers no alternative
(well... coda/intermezzo are close but no close enough). A general purpose cachefs would be beautiful.

Patrick Audley

`Every program attempts to expand until it can read mail. Those programs
   which cannot so expand are replaced by ones which can.'' 
                  - The Law of Software Development
...
Patrick Audley                [email protected]
Computational Biology         http://www.compbio.dundee.ac.uk
University of Dundee          http://blackcat.ca
Dundee, Scotland              +44 1382 348721

Hi Jan,

Do I take it you were (partially) responsible for Coda development? I have to admit I don't know much about Coda.

That's unnecessary judging by OpenAFS. AFAICT, only the ticket needs to be cached in the kernel (this is obtained by means of a userspace program), and then the ticket is passed through the security challenge/response mechanism provided by RxRPC.

Otherwise, the entire network side of OpenAFS would have to be in userspace too, I suspect.

It may be possible to offload the security aspects to userspace. I'll have to think about that.

Besides, I get the impression that NFSv4 may require some level of kerberos support in the kernel.

I presume Coda uses a 1:1 mapping between Coda files and cache files stored under a local filesystem (such as EXT3). If so, how do you detect holes in the file, given that the underlying fs doesn't permit you to differentiate between a hole and a block of zeros.

OTOH, if you have a copy that you know is now out of date, then one could argue that you shouldn't let the user/application see it, as they/it are then basing anything they do on known "bad" data.

Should I also take it that Coda keeps the old file around until it has fetched a revised copy? If so, then surely you can't update a file unless your cache can find room for the entire revised copy. Surely another consequence of this is that the practical maximum file size you can deal with is half the size of your cache.

What I'm intending to do is have the write VFS method attempt to write the new data direct to the server and to the cache simultaneously where possible. If the volume is not available for some reason, I have a number of choices:

(1) Make the write block until the volume becomes available again.

(2) Immediately(-ish) fail with an error.

(3) Store the write in the cache and try and sync up with the volume when it becomes available again.

However, with shared writable mappings, this isn't necessarily possible as we can only really get the data when the VM prods our writepage(s) method. In this case, we have another choice:

(4) "Diff" the page in the pagecache against a copy stored in the cache and try to send the changes to the server.

Using disconnected operation doesn't actually make this any easier. The problem of how and when write conflicts are resolved still arises.

There is a fifth option, and that is to try to lock the target file against other accessors whilst we are trying to write to it (prepare/commit write maybe).

Because (and I may not have made this clear) you nominate a block device as the cache, not an already existing filesystem, and mount it as afscache filesystem type. _This_ specifies the layout of the cache, and so whatever other filesystems do is irrelevant.

No need to. I can go direct to the block device through the BIO system, and so can throw a heap of requests at the blockdev and deal with them as they complete, in the order they are read off of the disc when scanning catalogues.

Since I can fire off several requests simultaneously, I effectively obtain a readahead type of effect, and since I don't have to follow any ordering constraints (my catalogues are unordered), I can deal with the blocks in whatever order the elevator delivers them to me.

I don't need a hole punching syscall or ioctl. Apart from the fact that the filesystem is already in the kernel and doesn't require a syscall, the cache filesystem has to discard an entire file as a whole when it notices or is told of a change.

Agreed. That would be a reasonable way of doing it. The reason I thought of doing it the way I suggested is that I could make the block size bigger in the cache, and thus reduce indexing walking latency for adjacent pages.

According to the AFS-3 Architectural Overview, "AFS does _not_ provide for completely disconnected operation of file system clients" [their emphasis].

Furthermore, the overview also talks about "Chunked Access", in which it allows files to be pulled over to the client and pushed back to the server in chunks of 64Kb, thus allowing "AFS files of any size to be accessed from a client".

Note that 64Kb is also a "default" that can be configured.

It also mentions that the read-entire-file notion was dropped, giving some of the reasons I've mentioned.

Does this mean that every Coda cell is issued with a 4-byte ID number? Or does there need to be an additional index in the cache?

These were just examples I know fairly well to illustrate the problems.

You still have to store a hash somewhere, and if it's stored in a userspace daemon's VM, then it'll probably end up being swapped out to disc, and it may have to be regenerated from indices every time the daemon is restarted (or else your cache has to be started afresh.

Thanks for your insights though.

Cheers,
David

Hi Jan,

I see. So users have to know how to resolve conflicts themselves...

Is that a requirement for AFS? I'm looking at trying to pass writes to the server as soon as possible.

Where there's leeway, I can choose.

In some ways, what I'd ideally like to do is have write() contact the server and actually send the data direct, then assuming that wasn't rejected, update the local cache. Any bits of the write that don't overlap pages that are cached _can_ just be discarded once written to the server, as I can always retrieve them from the server later, complete with their surrounding data.

Alternatively, I can use prepare-write to make sure I hold copies of all the pages I want to modify, and then use commit-write to write them back. The problem with doing that is that I potentially have bits either side that may end up reverting a write made to the server by someone else.

The third option - using writepage() - has the same problems as the second.

However, I could get around this by doing a binary "diff" of the page in the local cache against the modified page in memory and just send the changes to the server. Or, I could then retrieve a fresh copy of the page and apply the differences to that. The problem there is that I can't detect changes that have made no difference.

I have to zap pages that some other client has modified. The server has told me to invalidate it, and so I need to reread it from the server.

This is probably only going to be a problem with shared-writable mappings, and the problem is due to AFS, not how I do my caching.

Not with prepare-/commit-write if commit-write is synchronous.

In any case, if they don't have that chunk cached they'll have to fetch it from the server.

AFS fileservers don't have a concept of an open file. Every time you do a fetch or a store (be for it data or metadata) you get a short-term "lease" on the file that the server breaks if some other client modifies it.

Furthermore, every operation a client issues is checked at the RxRPC level. This way a client can have several users holding a file open in the local VFS and just label the operations sent to the server with tokens representing the users doing the access.

How does Coda do it? Does it get "open" the file on the server with a particular set of credentials for each user that wants to use it?

For instance: you have one file in your cache, several people write to it, but one of the people in the middle had permission taken away as far as the server is concerned.

Also, when writing the file back, if several people have changed it, whose credentials do you present to the server as having made the change?

What if someone changes the permissions on the server's copy of the file whilst you have the file open?

This is what I was getting at. The main issue is how do you deal with a file in the cache that has been written to by several people, some of whom don't have write permission any more.

And I get to enjoy the benefits of the pagecache keeping the data in memory when it is frequently used, and I can also do smart stuff and try to optimise access.

I thought you might have meant a "Volume Manager" rather than the kernel's VM subsystem.

So you keep everything in triplicate whilst running? (or at least duplicate plus a frequently emptied journal).

I see... you can have dirty data residing in the cache over a reboot, and thus you can't just nuke your cache partially or wholly, and you have to keep careful account of all the entries in there... Hmmm... I'll have to think about that, but I don't think it'll be a problem, provided I don't let close() complete until all the dirty data from a file is written to the server.

David

Last time I checked, yes. Callbacks should be sent only when the file is closed.

But local modification are per definition more up-to-date because you haven't closed the file yet. It is very much a problem of how you do your caching. I'm trying to tell you AFS has a well defined consistency model called session semantics. That directly influenzes every decision you make wrt. to caching and everything I've seen up until now shows me that you're simply implementing an NFS client that happens to speak to AFS servers.

Actually AFS is most definitely a stateful filesystem and as such has the concept of an open file.

Just google for "AFS NFS stateful stateless" and you get literally hundreds of handouts and lecture notes from distributes systems classes that describe exactly these differences. UNIX/session semantics, stateless/stateful, etc.

Yes. If the user hasn't opened the file before, we have to check the permissions with the server. So every user that opens the same file will generate an "open" rpc to the server.

First of all, typical write-write sharing is extremely low, otherwise Coda wouldn't have even worked with it's optimistic replication and caching. Second of all permission changes are even rarer.

So on the off chance that a write-write shared file on happens to be affected by a permission change.

- We either succeed in writing the file when the person who lost access closed before the last writer who still had access. Big deal, he had access when he opened the file, and it is next to impossible to tell wheter his close arrived before or after the permission was taken away except when every operation is somehow given an absolute linear ordering in time. Generally too expensive on a distributed system with clients that may come and go as they please.

- Or the person who lost access is the last one to close the file and trigger the writeback. In this case the servers will deny the write operation and the client will declare a conflict on that object and switch to disconnected mode. Someone who has write permission can repair the conflict.

Like I said in the section you quoted yourself, the last writer who closes the file.

Actually, for any unmodified data there is only one copy. Once it is modified there are two (the dirty page and the logged change), why would there be a third, I don't care about the copy in the backing file...

It has the advantage that even if you pull the powercord, we can still recover the last consistent set of metadata and from that validate both the data in the cache files, and revalidate everything against the servers, which we already need for the disconnected operation.

Jan

Sent by whom?

The client doesn't send callbacks. The server breaks all the callbacks on a file whenever the contents or metadata of that file are changed. Closing has nothing to do with it as far as the server is concerned (indeed, there is no close).

I'm trying to follow the AFS architecture guide, without sacrificing too much to cache coherency problems - which it sounds like Coda has... You've said it requires user intervention (automated maybe) to fix up files for which the cache has become inconsistent with respect to the server.

The difference is between Write-Back and Write-Through caching (to use h/w CPU caching terminology). What I'm looking at doing is using Write-Through caching, but I could make it configurable.

As I've said, Write-Back caching has more tricky security issues, particularly when more than one user is changing a file on a client, given that the file can't be "opened" with the server.

Check the AFS fileserver API. There is no open call (and no close call). You _can't_ "open" the file on the server. All you can do is fetch/store data or metadata which gets you a short-term guarantee that you'll be told if what you have is invalidated. (Admittedly, there are also calls for creating/destroying various sorts of files, but they aren't pertinent to this discussion).

Thus, every time you access the file, your credentials have to be effectively rechecked (the fileserver may cache granted permissions, but that's an optimisation).

Furthermore, whilst the fileserver will inform you if the mode bits on a vnode are changed, and probably when the ACL is changed on a directory, it won't inform you when group ACEs of that ACL are changed in the protection server. Therefore, the access rights granted to any particular set of credentials may change without a client knowing about it - even if it still holds a valid unbroken lease.

My point is that it can't be assumed that security details negotiated at client-side open will still be valid come the first operation on that file.

Rare isn't the same as impossible. If it can happen, it has to be considered and has to be catered for.

So someone else submits the now denied user's changes, thus allowing them to bypass security... I'm not arguing that you're necessarily wrong. Some compromise has to be made, and without being able to account to the server for every one who has made a change to the data being submitted, and perform full database style rollback and re-execute, the options are limited.

This is not an option I can use.

You listed three (not including RAM): swap, logfile, underlying file.

Does your cache run in synchronous mode with respect to the disc?

It may be that I can improve matters in my caching by using a journal... and the VM/VFS has hooks for use by journalling filesystems such as EXT3.

David