Subject: RE: Stateid and seqid

From: "Sergey Klyushin" <[email-masked]>
Date: Thu, 1 Feb 2001 00:03:28 -0500

Please, take a look at the attached file.
I've made some changes and it would be really appreciated,
if we could review one before next meeting.
Any comments (specially for OPEN_CONFIRM) are very welcome.

Sergey
    > 
    > 
    > here is (finnally!) what i have for the flow diagram of 
    > stateid, seq num, and 
    > lease processing that was agreed upon at the last bakeoff, 
    > and discussed in 
    > the flurry of post bake-off email. i think it includes the 
    > processing that 
    > dave described concerning stateid and sequence number.
    > 
    > i would appreciate it if the list would look it over - it 
    > would be great to 
    > agree on this issue before connectathon..
    > 
    > -->Andy
    >

---

From: "Sergey Klyushin" <[email-masked]>
Date: Thu, 1 Feb 2001 00:17:10 -0500

>
    >
    > On Wednesday January 31, [email-masked] wrote:
    > > >    If the operation is successful and state changes, then the
stateid
    > > >      changes.
    > >
    > > According to David Robinson, the server may in some cases return the
    > > same stateid (ie. not change it).
    >
    > I can see, from a operational perspective, that you could argue this
    >  - all operations that effect state maintenance also have a seqid to
    >    ensure sequencing and
    >  - the operations that only have a stateid (read/write) will not be
    >    adversely affected by certain state changes - e.g. gaining a lock.
    >
    > however I think that if you try to understand a protocol like NFSv4
    > from a purely operation perspective, you will get bad confused very
    > quickly (Well, maye you won't but I suspect that many would, myself
    > included).   Complexity needs to managed by abstraction (that is what
    > computer science is all about) and so we need to understand and reason
    > about the protocol at an abstract level.
    >
    > When you are reasoning like this (abstractly), having a "stateid" that
    > "uniquely defines the locking state granted by the server for a
    > specific lock owner for a specific file" and then not changing that
    > stateid when the locking state changes is a recipe for disaster.
    >
    >
    > >
    > > >    If the operation fails and the state doesn't change, then the
    > > >      seqid changes.
    > >
    > > The current approach is that seqid does not change if the operation
    > > fails.  That's what people are implementing to, but there has been
    > > disagreement about whether the spec says that (e.g. Mike
    > Eisler believes
    > > it does)
    > >
    >
    > ButButButButButButButButButButButButButBut
    > Numbers in [brackets] are seqids.  As our story opens, the "last
    > sequence number (L) received" is [L].
    >
    >  Client say [L+1] "lock this bit of that file".
    >  Server says "No, there is a conflicting lock" but reply is delayed in
    >       transit.  As this is an error return (NFS4ERR_DENIED), the
    >       server doesn't touch the seqid (you seem to say), it leave it at
    >       [L].
    >  Client is impatient and again says [L+1] "lock this bit of
    > that file".
    >  Client gets first reply and says "oh well, such it life".
    >  SomeotherClient unlocks "this bit of that file".
    >  Server gets resend.  The rpc reply cache has been busy and it doesn't
    >    catch this one. The seqid looks fine ([L+1] just like the
    > last time), and
    >    the server notices that there is no conflicting lock now, so it
    >    returns with success. It updates the "last sequence number
    >    received" to [L+1] and stores "the response that was returned.
    >  Client doesn't notice this reply because it doesn't really care any
    >    more.  Maybe it was lost in transit anyway - it happens.
    >  Client tries to [L+1] "lock that other bit of that file".
    >    Now this has the same seqid as the last successful lock request
    >    for this lockowner, so "the stored response is returned" -
    >    success.
    >
    > Net result: client thinks that it locked "that other bit" and server
    > thinks that it has "this bit" locked.  Not a good situation.
    >
    > Am I missing something?
    >
I agree, that seqid should be changed on ERROR also (see my previous email)

Sergey

---

From: "Noveck, Dave" <[email-masked]>
Date: Thu, 1 Feb 2001 06:38:38 -0800

mre> Should a replay a renew a lease?
This leaves the server open to attacks.  

I don't understand this.  What attacks are you
thinking of?

---

From: Mike Eisler <[email-masked]>
Date: Thu, 1 Feb 2001 07:37:56 -0800 (PST)

An attacker can record a client's request, and resend it
to the server before the lease time expires, thereby causing the
server to continue to reserve resources on the dead client's behalf.
>From: "Noveck, Dave" <[email-masked]>
>To: "'Mike Eisler'" <[email-masked]>, "William A.(Andy) Adamson" 
<[email-masked]>
>Cc: [email-masked]
>Subject: RE: Stateid and seqid 
>Date: Thu, 1 Feb 2001 06:38:38 -0800 
>MIME-Version: 1.0
>
>

---

From: "Noveck, Dave" <[email-masked]>
Date: Thu, 1 Feb 2001 08:07:57 -0800

Neil Brown wrote: 
> > >    If the operation is successful and state changes, then the stateid
> > >      changes.
> > 

> stateid when the locking state changes is a recipe for disaster.

I see your point.

Right now I don't think the spec even requires you to change the stateid
at all.  The protocol (by returning stateid on various operations) give
the server the opportunity to do so.  (It's not the law.  It's just a 
*damn* good idea).

The spec should make clear when you (the server) should update the stateid
including whether you are allowed to use Robinson's trick of not bumping
it on LOCK (for example) or not.

Similarly, for the techniques that Mike Eisler mentioned (I tried to find
these in the archive but couldn't find them) whereby a server might
recognize recently superseded stateid's on READ and WRITE and check
the IO's using the locking state in effect at that time the stateid's
were generated.  The spec should be clear about whether these are OK.
I hope the answer is "yes", since they could help performance for some
other troublesome environments (i.e. when locking operations and in-flight
IO requests might otherwise cause frequent retries or excessive delays
for request synchronization).

---

From: "Noveck, Dave" <[email-masked]>
Date: Thu, 1 Feb 2001 11:23:36 -0800

> We interpreted the spec as saying that the request-level caching should be
> done, but operation-level caching makes a lot more sense (and also seems
> necessary for correctness in all cases), so if everyone agrees that
> operation-level caching is correct, we'll switch to operation-level
> caching.  (The only server implementation we haven't heard from yet is
> Sun's.. correct?)

The only server implementations we haven't heard from yet are Sun's.
(i.e. Java Server and Solaris server).

---

From: Eric Kustarz <[email-masked]>
Date: Thu, 8 Feb 2001 10:04:09 -0800 (PST)

>To: "'Kendrick M. Smith'" <[email-masked]>, [email-masked]
>Date: Thu, 1 Feb 2001 11:23:36 -0800 
>MIME-Version: 1.0
>
> 

We already have request level caching at the RPC layer (for retransmissions, 
ie: same xid).  This RPC level caching doesn't handle cases (without 
modifications) where a new compound (therefore new xid) request comes in but 
one of the ops has a replayed seqid.  However, a new compound request with a 
different xid having a replayed seqid sounds like a broken client to me.  But 
yeah, operation-level caching makes more sense, so we will add that up in the 
NFS layer.

eric

---

From: "Noveck, Dave" <[email-masked]>
Date: Thu, 15 Feb 2001 13:08:45 -0800

Neil Brown wrote:
> On Friday February 9, [email-masked] wrote:
> > 
> > The open/upgrade downgrade issue is not just that NT servers want (or
> > need) multiple opens instead of upgrade/downgrade.  It is also that
> > UNIX clients don't want (or can't have) multiple independent opens
> > that they have to manage and present to the server.  NT is open-file
> > oriented while UNIX VFS interfaces are vnode-orineted and don't
> > want to know about open files.  I think the fact that this has been
> > discussed without vituperation may have obscured how fundamental the
> > issue is.  (Can you imagine Bill Gates and Scott MacNealy discussing
> > this?).
> > 
> > We could put multiple opens in the current protocol very easily.
> > A second open would produce a new stateid which the client would
> > use, without inspecting the fileid.  The problem is that this would
> > not work for UNIX clients, as far as I can see.
> > 
> > I did propose a somewhat unsatisfactory compromise for this issue
> > a while back.  There wasn't any response either positive or 
> > negative.  I can try to find it and repost it if anyone is
> > interested.
> >  
> 
> Now that you mention it, I do vaguely recall you mentioning this
> before.  I would be interested in seeing your compromise again if it
> isn't too hard to dig up.

I found it.  I'll fix some typo's and resend it.

> 
> I guess this is closely related to how the OS caches things.

Yes.

> 
> Because the Unix philosophy has always been that multiple access to a
> file is fine, there is a file cache that all processes can access
> equally.   The processes talk to the cache, the cache talks to the
> device.  In particular, it is the cache that writes to the device, not
> a particular process.... so how do you choose which lockowner to
> associate with a particular write request .. and does it matter?

When locks (and particularly mandatory locks) are involved, it
certainly does.  The client can simplify his job by doing reads
and write when locks are present straight through to the server,
using the stateid of the process doing the IO.  If he just puts
the data in the buffer cache, he will need to make his buffer cache
more v4-aware so that the proper stateid can be used as well as
avoiding writes (because of block granularity issues) outside the
area actually locked.

> 
> The DOS/Windows philosophy was always "only one process can have a
> given file open at a time" so the cache is probably a lot closer the
> the file descriptor than it is in Unix.  File SHAREing was only added
> later, and I suspect this is reflected in the internals of the FS
> code.
> So presumably a client implementation for WIN32 would be able to
> present separate opens to the server in a way that Unix cannot (I
> think actually that Linux could, but it wouldn't make for the most
> efficient implementation and would probably cause problems for mmap).
> 
> So the setting is:
>  - Unix clients can only present one open per file per process (or if
>    I had my way, one open per file per client :-), and need to be able
>    up-grade/down-grade the open mode between nothing/read/write/both.

There may be Unix variants in which the vfs interface allows open
file information to passed to the fs implementation, but I don't
know of any.  Certainly the typical Unix client can't do this.

>  - WIN32 client can (presumably) present multiple opens per file,
>    probably one per filedescriptor (or equivalent).
>  - Unix kernel-based-servers and probably cope with anything (?)
>  - WIN32 server (I don't know enough to suggest what level they might
>    be at) cannot provide upgrade/downgrade of share reservations.
>  - Unix user-space servers don't know what "DENY_*" means, and cannot
>    convert a file descriptor from read to write or visa-versa.

Some might know about DENY_*.  Because of the ubiquity of Windows
programs, even Unix systems may find themselves providing this.
Certainly may Unix user-space servers will not be able to do
much with DENY_ (other than arbitrate among the nfs users leaving
local users to do whatever they do).  I think Unix user-space 
servers can probably convert between read and write.  They will
have to open a new fd and close the old one, but the big problem
which NT servers have, may not affect them.  NT servers have the
problem that byte-range locks may be on the old fd and can't be
transparently moved to the new one.  I believe most Unix's don't 
have that problem.  I think the locking support is vnode oriented,
so if you open a new fd and close the old one, the byte range
locks remain.  Not positive though.  Perhaps someone who is 
currently working on Unix kernel internals will corect me.

> 
> Lets assume that:
>   Unix clients never make "DENY_*" requests - they only assert an
>   access type.  They only present one openfile per file per lockowner,
>   and may want to upgrade/downgrade the access type on this file, but
>   only by adding or subtracting, never both at once.

OK but I wouldn't assume that Unix systems are safe from infection
by the DENY virus.  Note that not all viruses are pathogenic.  
Whether you consider that one to be pathogenic or not is a matter
of personal judgement.  I don't.
 
> 
>   WIN32 clients do make use of DENY_* requests, but (somehow) present
>   different openfiles for the one file+lockowner.  These will only
>   ever by OPEN_DOWNGRADEd to zero access, and will never be involved
>   in a secondary OPEN (which might upgrade the DENY_* modes).

I'm not sure I understand what you are saying here.  When you say
"will never be involved in a secondary open", do you mean that
the client will take some steps to avoid it, in which case I
don't see how it could do this in the presence of hard links on
the server since the client will not know he is opening the same
file until after the open (secondary open is done).  Or are you 
proposing that all OPEN's cause a nwe open-file-instance to be
created (i.e. no OPEN-upgrade and per-open-file-instance stateids)?

Also I don't understand OPEN_DOWNGRADE to zero access.  That sounds
like a close to me.

> 
> It should then be possible to implement the server over WIN32, or
> anywhere.
> When asked to open a file with no DENY_* modes, the server potentially
> opens 2 file descriptors - one for READ access, one for WRITE access.
> Any shared byterange locks and any read requests are made on the READ
> file.  Any exclusive byterange locks and any write requests are made
> on the WRITE file. An OPEN_DOWNGRADE can be handled by closing one of
> these. An OPEN which does an upgrade can be handled by opening the one
> that is currently closed.

This is kind of cute.  I hadn't been aware that Unix enforced this
restriction requiring that lock types on advisory locks match open
types.  I tried it on Linux and Solaris and it works that way.

One issue is upgrade and downgrade of byte range locks.  Maybe this
is OK, since in NT you can't do that (and the spec doesn't require
it), and in UNIX (for which the spec allows the server to provide 
those extended semantics), getting the shared lock will, I think,
cause a downgrade, even thhough they are done different fd's,
since Unix is not open-file oriented.

> 
> Any opened file that does actually DENY something gets its own local
> (to the server) open.
> 
> Is that at all similar to what you suggested?

There are some similarities but more differences I think.

Part of the problem is that I'm having trouble disentangling
the issue of what model the client sees (upgrade or per-open-instance)
from how you might do the implementation on various servers, so
it's not clear if I understand what you are proposing.
 
> It doesn't deal with the awkwardness that an OPEN might, without the
> client being directly told, get interpreted as an openupgrade and not
> actually create new state, but that is a separate issue. 

The issue for the client is does he have to do a CLOSE.  Right now
the protocol says opens for same file and lockowner merge so that
the client must do exactly one CLOSE. (and he may do DOWNGRADES
to simulate the effect of local closes).

The other model is doing one CLOSE per (successful) OPEN.  

So I'm not sure exactly what you are intending to do here.

---

From: "Noveck, Dave" <[email-masked]>
Date: Fri, 16 Feb 2001 12:56:40 -0800

Neil Brown:
> > > How is state managed:
> > >    State is stored on the server.  While the client will keep it's own
> > >    records of the current state, the state stored on the server is
> > >    authoritative.
> > 
> > An exception is reclaim logic.  When the server re-initializes, he
> > accepts the clients reclaim request as presumptively correct,
> > if not authoritative.
> >     
> 
> An interesting point.  From a high-level perspective, it probably is
> appropriate to think of the clients information as being authoritative
> immediately after a server restart.  However when considering the
> practicalities, I don't think that  the server will give any more
> weight to a request made during the "grace" period than it will at any
> other time - except that delegation requests can be made at this time.
> 
> I think that the rule for the server comes quite close to:
>  During grace period, only accept state-changing requests that are
>  marked as "reclaiming",
>  At other times, only accept state-changing requests that are not
>  marked as "reclaiming"
> In both cases the server should do the same checks about permission
> and conflicting locks.

Right.  The only difference is the implications of failure.

Outside of the grace period it's just , "You lose".

During the grace period, it's "One of you is a liar!"

> 
> > >    The server's period of uncertainty about the client's view of state
> > >    is between sending a reply and getting some new request that in
> > >    some way confirms that the client received the reply.  For the
> > >    server to become certain about the clients view, there needs to be
> > >    some way for the client to confirm reply.  The model presented in
> > >    the RFC (which I believe is a good one) is to use a "cookie" (my
> > >    term) to represent a particular state.  The architypal cookie in
> > >    the spec is the stateid.
> > 
> > During the period in which the client is uncertain about the server's
> > view of the state, he may want to change the state yet again.  If he
> > cannot start to do so during that window, you may have unacceptable
> > performance constraints due to excessive single-threading of requests.
> > 
> > I suspect this is what has driven (at least in many cases) the choices
> > that the spec has made in establishing its state heirarchy, although
> > this model makes that all that clearer.
> 
> Serialisation of requests is definately an important issue.
> Infact, if serialisation were OK, we could manage with just one level
> of state per client.  But obviously this is unacceptable.
> I had thought that serialisation at the client level wouldn't be a
> problem because:
>  1/ When sub-state is created, the client cookie doesn't change so
>     multiple creates can happen in parallel and
>  2/ If sub-state is "emptied" (i.e. unlock all locks, downgrade all
>     opens) first, then destroying the state becomes a simple
>     house-keeping operation that doesn't interact with any "real"
>     work, and so can be done serially by some background thread.
> 
> However on describing the model competely, I see (and you point out
> below) that 1 doesn't apply, as the client cookie must change on a
> failed create.
> So I suspect that the need to reduce serialisation would be sufficient
> justification for another level of state.
> 
> > > 
> > >    For server-initiated state changes, the client can find out that
> > >    something has happened by receiving a failure status for a request
> > >    with a cookie that is no longer valid.  The spec isn't clear on
> > >    exactly how the client informs the server that it has figured out
> > >    the new state.  I think that the neatest approach is that the
> > >    client should send unlock/close requests to release any state that
> > >    is in question, and that in these requests, old cookies should be
> > >    accepted.
> > 
> > Not sure if you consder server reboot a server-initiated state
> > change.  In that case, the client doesn't unlock/close.  I guess in
> > that case the SETCLIENTID tells the server that the client 
> > know about the reboot (or if didn't, they both agree that they are
> > starting with a clean slate).
> 
> Yes, I would consider server reboot as a server-initiated state change,
and
> no, the "neatest approach" mentioned above does not really cover that.
> I guess it depends on how much information is deemed to be in each
> possible error code:
>   NFS4ERR_STALE_STATEID  and
>   NFS4ERR_STALE_CLIENTID
>               say "All state associated with the <server> level
>               state that corresponds with the given stateid has been
> 	      revoked:  Client needs to start again from scratch.
>   NFS4ERR_EXPIRED say "The state at the level of the stateid presented
>               has been revoked:  Client needs to attempt to "close"
> 	      that stateid - it may find that state at a higher level
> 	      has gone too.

I think this is a good way of putting it.

It also means that there is one other consideration that might cause
you to create a state level in the protocol (or dynamically as might
be proposed in the manifesto of the State Management Liberation
Front :-).  That is the  desire to isolate revocations so that they 
do not cause too much state to be lost, since below the lowest level,
you can't distinguish revocation.  For example, currently if you lose
a lock, you lose all locks on the entire file for that lockowner.
I'm not saying this is undesirable, but it illustrates another
consequence of how we choose to aggregate or sub-divide state.
 
> 
> 
> >  
> > > 
> > >    Ok, it took a little while to get here, but we now have an
> > >    hierarchical state and a cookie for state confirmation.
> > > 
> > > State transitions:
> > > 
> > >    There are three sorts of state transitions that we need to
> > >    consider:
> > >     1/ creating a new state
> > >     2/ modifying a state
> > >     3/ discarding an old state.
> > 
> > What are the simultaniety restrictions that are assumed there?
> > 
> > I assume that only one type-2 request may be outstanding for a
> > a given state.  Also that no type-3 request for a given state
> > may be issued while a type-2 request for that same state is
> > outstanding.  And clearly you can't have multiple type-3's
> > for the same state, nor can you issue a type-2 or type-3
> > before you have completed the request that created it (a
> > type-1).
> > 
> 
> I agree with all of that.
> 
> > These are related to the child state.  I'll speculate below
> > about the simultaneity contraints relative to the parent state.
> >  
> > > 
> > >    For each of these, we need to understand:
> > >     A/ what cookie must be presented by the client to convince the
> > >        server that the client and server views of state are
sufficiently
> > >        consistant.
> > >     B/ what cookies get changed or created and how are these returned.
> > > 
> > >    I will assert the answers to these questions and leave the
> > >    justification to when I compare the model to the current protocol.
> > > 
> > >    When creating a new state, the cookie for the parent state must be
> > >    presented, and a new cookie is created and returned for the new
> > >    state.  The cookie for the parent state doesn't change.
> > 
> > I'm guessing that this (not changing the parent state) would allow
> > multiple simultaneous type-1 requests specifying the same parent.
> > 
> > This makes me uneasy as I consider OPEN's.  An open creates a piece
> > of state but I think that sequencing opens and close as the current
> > protoocl does is a good thing and a lot of problems would flow from
> > not doing that.  The issue is that while OPEN creates a new state, it
> > also modifies the parent state in ways that would not allow multiple
> > open from a given lockowner to be handled without sequencing them.
> 
> Is the issue that you are seeing this:
>   a given lockowner on a given client issues two parallel open
>   requests for two different names that happen to refer to the same
>   file.  This creates creates only one openfile state, but it is not
>   clear which returned cookie should be used for that state.

Not sure I had a clear example in mind, but OPEN is complicated and
when it isn't tighly serialized, my experience is that it is hard 
to avoid problems.

> 
> I think that is an problem with OPEN (don't get me started on OPEN:-),
> but I think we agree that OPENs do need to be serialised to cope with
> the possible failure of an OPEN (though I don't think you had got
> there by this stage).
> 
> > 
> > >    When modifying a state, the cookie for that state must be presented
> > >    and a new cookie for the new state is returned.  Note that only the
> > >    bottom level of state can be directly modified.  Higher levels are
> > >    modified by creating/deleting a lower level state.
> > > 
> > >    When deleting a state, the cookie for the state and the parent
> > >    state must be presented, and a new cookie for the parent state is
> > >    returned.
> > 
> > Which I assume means that only one type-3 specifying a given parent
> > can be outstanding at a given time.
> 
> Yes, though if it were possible to pass state cookies forward through
> a COMPOUND operation (like you can for filehandles) I think it could
> work to include several type-3 requests for a given parent in a single
> COMPOUND.

OK.  The issue is serialization and since OP's in a COMPOUND are 
handled serially, this would work.

> > > 
> > >     One way to look at this, is that the server maintains a client
> > >     cookie which is the clientid plus something else.  When the client
> > >     makes a request that requires the "something else", the server
> > >     replies by saying "you also need this datum to confirm the
> > >     request".  The client then confirms.
> > 
> > Normally the lockowner/seq-id pair is the something else.  In the 
> > current protocol, the client doesn't know whether that is enough
> > and has to be told.
> >
> 
> My interpretation is that "normally" clients are fairly long lived,
> while lockowners are relatively short lived, so for most clients, at
> least one lockowner will have been disposed for.  Thus from the
> paragraph on page 139 for RFC3010:
> 
>       A lazy server implementation might require confirmation for every
>       nfs_lockowner for which it has no record.  However, this is not
>       necessary until the server records the fact that it has disposed
>       of one nfs_lockowner for the given clientid.
> 
> the server will mostly (normally) have to require confirmation.  The
> only time it doesn't need to is between client creation and first
> lockowner disposal.

You could use a more sophisticated scheme but with any lockowner 
turnover at all, you fairly soon wind up requiring confirmation.

> 
> > > 
> > > 
> > >  Openfiles:
> > > 
> > >   Object creation:
> > >     An "openfile" object is created with the "OPEN" operation.  The
> > >     client must present the "cookie" for the lockowner, being the
> > >     nfs_lockowner4 structure and the seqid (and possibly must present
> > >     a verifier with OPEN_CONFIRM, but that is to confirm the creation
> > >     of the lockowner, not to confirm the creation of the openfile.
> > > 
> > >   Object creation failure:
> > > 
> > >     It is quite possible for openfile creation to fail in a way that a
> > >     subsequent identical request could succeed.  One possibility is a
> > >     request for exclusive create: the file could be removed between
> > >     the initial request and the retransmit.  Another possibility is a
> > >     conflicting share reservation.
> > >     For this reason the "cookie" that is presented for the parent
state -
> > >     the lockowner -  must change when an OPEN fails for one of these
> > >     reasons.
> > 
> > OK.  So state-creating requests that can fail may change the parent
> > state, without creating a new element of state.  So the client must
> > not only send the parent cookie, he must be prepare for it to change.
> > This implies to me that stat-creating and state-deleting requests 
> > for the same parent state must be serialized.
> 
> Yes :-(
> There is an alternate approach for state-creation:
> We could require that state creation always succeeds in that a new
> state is created, but that it may not always have the properties
> desired.
> (e.g. I OPEN and ask for READ/DENY_WRITE, and I get given an open
> which (I am told) is only READ.  Probably though, if not all
> access/deny request can be given, then none should be given).
> If this state is not useful to me I can then OPEN_DOWNGRADE if
> necessary and schedule a CLOSE.  As mentioned above, state-deletion
> (CLOSE) must be serialised, but that isn't as much of a problem.
> 
> The big problem I see with this approach is NFS4ERR_RESOURCE.
> This is an error that in the class of "a retry might work", so it must
> cause a state change.
> Expecting a failurecount counter to be incremented when the server is
> having resource problems isn't much of an ask.  Asking it to always be
> able to allocate a new cookie, even when low on resources might be too
> much to expect.
> 
> > > 
> > > Summary of issues:
> > > 
> > >  - While there is a clear hierarchy of state, the way that state is
> > >    indicated (the cookie) is very different at different levels.
> > >  - It is unclear what the purpose of the lockowner level is.
> > >    I am happy to detail my view of the lockowner level but this email
> > >    is too long as it is, so I have cut it out and will send it
> > >    separately if anyone is interested.
> > 
> > I'll try to collapse my view into a few sentences.
> > 
> > Lockowners as protoocl elements (apart from their role in the state
> > hierarchy), need to exist to represent the various independent 
> > actors by which files may be opened/locked, and for which the 
> > client implementation acts as the agent.  Various semantics on
> > the server (particlularly in their UNIX variants) depends on the
> > identity (or lack thereof) of a lock requestor and the lockowner 
> > for the lock which represents a potential conflict.
> 
> I have heard this claimed more than once, and I still don't get it.
> Can you help me?
> I cannot see why the client shouldn't appear to the server as being a
> single lockowner: arbitration between any idependant agents on the
> client would be done by the client:
> 
>    Agent-1 asks for a lock
>                        Client asks server for the lock
> 		                              Server grants the lock.
> 		       Client grants the lock to Agent-1
>    Agent-2 asks for a conflicting lock
>                        Client detects conflict and blocks Agent-2
>    Agent-1 releases lock
>                        Client grant lock to Agent-2
>    Agent-2 uses lock
>    Agent-2 releases lock
>                        Client releases lock
> 		                              Server acknowledges
>                                                 release of lock
> 
> It could be suggested that the client should release and reclaim the
> lock with the server before granting it to Agent-2, and that is
> certainly an issue worth considering, but I am sure that locking could
> be don't quite effectively without the server knowing "who" on the
> client has the lock.
> 
> Certainly telling the server and letting it arbitrate works too, but I
> don't see that it is necessary.

OK.  Maybe "necessary" is too strong.

The alternate design of client arbitration might work but I think it
creates some difficult implementation problems for the client.  I 
think your example is a bit oversimplified.  When you have to deal
with overlapping locks, upgrades, downgrades, etc. things can get
ugly.  

For example, if process A share locks bytes 1-2 and process B
share locks bytes 2-3, the server has to be told about both.
You would not be able to just tell the server about a new lock
for byte 3 because locks on NT are not divisible and recombinable
as they are on UNIX.  Now if process C asks for an exclusive 
lock on bytes 3-4 then he waits.  Now if B releases his lock
the server has to be told and once that is done (or as part of 
the same operation or if you want to special-case that), has to
request the lock for C which may or may not be available.  Add
in failures, retransmissions, re-ordering possiblities and request
simultaneity restrictions and things can get unpleasant fast. 

> 
> > >    
> > > 
> > > ------------------------- My proposed protocol -----------------------
> > > 
> > > You may have guessed much of my model by the foregoing treatment of
> > > the current model, so I'll try not to be too verbose.
> > > In this model I will completely leave out the lockowner level, because
> > > I cannot convincingly argue for it's existance.  You might find it an
> > > interesting exercise to see what it takes to add the lockowner level
> > > back in.  Hopefully you will be pleasantly surprised.
> > 
> > Unless I'm misunderstanding how this would work, it seems that the
> > client could only have one OPEN/CLOSE at a time.  That would be
> > reason enough add another level (e.g. lockowner) to the hierarchy.
> > 
> > Another possiblity is to retain lockowner in its actor-identification
> > function but take it out of the state-hierarchy.  You could allow
> > the creation of multiple levels in the state-hierarchy solely to
> > allow greater request simultaneity on the part fo the client.
> > The client could choose the boundaries of the state elements
> > and even the number of levels solely as ways of optimizing the
> > transmission (trading off setup-teardown time against the degree
> > of simultaneity desired).  With a more regular model, that would
> > be possible.  I fear I'm positioning myself on the Lunatic Fringe 
> > now so I guess I'll just stop here.
> 
> Hmmm. I like it... It is possibly excessive in it's generality, but it
> does help to make the issues clear.

Thanks for joining me on the Lunatic Fringe :-)  Actually, sometimes
(occasionally) the Lunatic Fringe turns out to be the home of
Premature Sanity.  I'm beginning to think that may be the case 
here.  

Here's a couple of reasons this is starting to appear attractive.
First, note that, as you point out, fairly soon you are going to 
enter a regime in which every new process (i.e. lockowner) requires
an extra round-trip for a confirm operation.  If you separated
state management from lock-owner-identification, then the
client might create an appropriate number of state-objects
(based on his serialization requirements) and use those as
the basis of sequencing quite apart from whatever lockowner
was sent on open requests they were used for (e.g. Unix clients
might set up per-process-table-slot objects).  Thus we avoid
all that extra open_confirm chatter, which is going to be a drag 
in environments with many short-lived processes.

By allowing the client to choose to create substates when he 
needs them for serialization, it might be possible to allow
multiple outstanding lock/unlock requests from the same
(multi-threaded) process.  DAFS, which is a VI/Infiniband-based
protocol whose locking is based on NFS-v4, achieves this by
tight integration with the transport (connection-based so you
don't need seqid or changing stateid's).  It occurs to me that
this approach might allow some of the same benefits within 
NFS-v4's looser (much looser) transport requirments.
    
> 
> > 
> > > 
> > > Foundation:
> > >   There is an hierarchy of state maintained on the server.  The levels
> > >   of the hierarchy are:
> > >       server
> > >       client
> > >       openfile
> > > 
> > >   The state of an object at each level is represented by a "stateid"
> > >   and a "failurecount". These together form the cookie.  
> > > 
> > >   There is precisely one server level state on each server.  It is
> > >   created by the server at start time and assigned a unique server
> > >   stateid.
> > 
> > I was having trouble with this.  It seemed that it was bizarre variant
> > in that all other state cookies could only change when you changed them
> > while this one was routinely changed when other clients made requests.
> > 
> > But now I see that this one never changes because the only thing that
> > happens si that new clients get created which does change the 
> > parent state and cleint creation can't file (?) so no changes for
> > that.
> > 
> > What about deletion of clients?  Can they happen?
> > 
> > I still think it's bizarre.  I just mean it in a derogatory way any 
> > more.
> >
> 
> I'm beginning to have doubts about the server level as well.. I hope
> they can be sorted out.
> I basically extrapolated upwards to get the server-state concept, and
> it seemed to work and to fit the current protocol (as well as the rest
> of the model fitted the protocol).
> Some issues:
>   - Yes, clients can and should be deleted, though the server is
>     allowed to destroy a client-state if it hasn't heard from the
>     client for a while (least-time and all that).
>     + this implies that the client should give
>          current-server-cookie + current-client-cookie
>       and get back new-server-cookie.
>       However it would have to ask for the current-server-cookie,
>       which seems pointless, and doesn't really need the
>       new-server-cookie.
> 
>       Maybe the right thing is not to have the client destroy it's own
>       state, but simple to cause a (type-2) state change to "this
>       client state will never be used again".  Then the server can
>       confidently clean up and update it's cookie.
> 
>   - When a client is reclaiming state after a server restart, the
>     server must be able to determine if the client is reclaiming a
>     sufficiently recent state.  The third paragraph of section
>     8.5.3 (Network Partitions and Recovery) talks about this.   If the
>     server has expired locks due to a network partition and then
>     restarted, the client can not reliably reclaim locks any more -
>     the state is not sufficiently recent.  I think that same holds if
>     a server has restarted twice during a network partition.  A client
>     coming back in contact after the partition should not be able to
>     reclaim locks from 2 restarts ago.
> 
>     It would be nice if this sort of issue could be embodied in the
>     server state cookie, but I don't see a clean way to do it.
>     It would require to server to update it's cookie periodically
>     (when it destroys client state), and then to prompt all client to
>     refresh their idea of the server cookie (NFS4ERR_GET_NEW_COOKIE to
>     all requests which have a stateid... not nice).
>     
> So, yes. That is an aspect of my model that is a bit incomplete.  I
> see now that the concept of "server-state" really needs to tie in with
> the issues around server restart, and I had been avoiding those issues
> to keep the model simple.
> 
> > 
> > One thing this doesn't address is IO (i.e. requests that depend on 
> > state but don't change it).  You want to avoid excessive serialization
> > without letting requests (WRITEs particularly) being acted upon
> > when they are no longer valid.  The current solution which uses
> > optimistic issue with retry on OLD_STATEID isn't pretty but it
> > serves the need.
> 
> I didn't address that, because I thought the current approach was
> adequate and would fit equally well into my model.
> Two thoughts:
> 
>  1/ a generous server could keep a short history of recent states for
>    each open_file and could accept an IO with an old cookie if it was
>    not contraindicated by subsequent state changes (i.e. no lock or
>    unlock on that region).

Mike Eisler had this idea.  Mike thinks it is already allowed by
the spec.  I wasn't so sure but we agreed the spec should let you 
do this.

>    [Hmmm. a similarly generous server could in a similar way allow
>    OPENs not be serialised even in the event of occasional
>    failure.. The amount of parallelism would be determined by the server's
>    history length (the generosity factor).]

Not sure how this would work.  The situation is a little different.
In the previous case we were dealing with the interaction of 
non-sequenced IO with a stricly sequenced string of locking requests.  
Here you are talking relaxing something that is sequenced so it's not
clear to me what the implementation would be here.

> 
>  2/ One issue that neither model addresses explicitly is the
>     possibility of two different write requests for the same region
>     being re-ordered in flight by a byzantine router.  It's a pretty
>     slim possibility I think, but given that we have allowed the
>     "byzantine router" argument in the past...
>     I essentially requires a "barrier" operation which changes the
>     state cookie without actually locking or unlocking anything.  This
>     would ofcourse mean that the generous server in point 1 must not
>     allow write requests from before a barrier.

Just to clarify here, if requests are truly in-flight, then the client
is saying he doesn't care about ordering.  The worry is that because
of retranmissions, a situation may arise in which only one request is
really in-flight as far as the client is concerned, but there are
two as seen from the server.

So a barrier seems like a reasonable operation.  When should the 
client generate it?  Here is my best guess at the answer:

Assuming that Byzantine routers are not so byzantine as to actually
copy messages, only hold them for a while and disgorge them at 
the worst time, bad things can only happen when we actually
retransmit a write.  So, when we complete a write for which we 
have done any retransmission, do a barrier operation.  I'm assuming
that we would allow barrier for a range to avoid interrupting
other in-flight writes on that file, but that' an optimization.
Until you get a response from the barrier operation, the buffer
from which you did the write is locked (the write conceptually has
not completed), so this makes things safe.