Subject: Re: Stateid and seqid

From: "William A.(Andy) Adamson" <[email-masked]>
Date: Mon, 29 Jan 2001 11:03:29 -0500

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: "Noveck, Dave" <[email-masked]>
Date: Tue, 30 Jan 2001 09:14:07 -0800

Sergei Klyushin wrote:
>   >
>   > Kendrick Smith wrote:
>   > >
>   > > On Sat, 27 Jan 2001, Sergey Klyushin wrote:
>   > >
>   > > > If implementation of NFS Server changes stateid on reply
>   > > > (otherwise I don't see why to return stateid, if it's not
changed),
>   > > > I can't see correct processing of replay scenario.
>   > > > I'll try to explain with more details.
>   > > > Replay request has seqid = stored_seqid, but request's stateid !=
>   > > > stored_stateid.
>   > > > So, to follow above scenario (first check stateid, then check
seqid) error
>   > > > BAD_STATEID or
>   > > > OLD_STATEID will be returned, before checking seqid.
>   > >
>   > > I suppose this means that, to guarantee correct replay protection, a
>   > > server implementation must retain the last expired stateid (per
lockowner)
>   > > in its stateid table.  This way, if a replay is received, the server
can
>   > > recognize the replayed stateid, compare seqids, and replay its
cached
>   > > response instead of erroneously returning NFS4ERR_OLD_STATEID.  This
is a
>   > > good point which, to my knowledge, hasn't come up before.  Should
>   > > something like this be written into the spec (or at least the
>   > > implementor's guidelines)?
>   >
>   > I don't think you have to separately save the last superseded (I think
>   > that's what you mean here; expired has some other
>   > connotations) stateid.
>   >
>   > What I do is first use the stateid to map to an entry in my table of
>   > state structures.  At this point, I may generate STALE_STATEID and
>   > BAD_STATEID errors, but not OLD_STATEID.  This requires that I know
>   > the range of valid values of the stateid subfield which is incremented
>   > on each change, but I need that anyway to properly distinguish between
>   > BAD_STATEID and OLD_STATEID.
>   >

> How "old" could be stateid? Probably, any operation, that takes both 
> stateid and seqid,
> makes range of valid values of the stateid subfield equal 1?
> BTW, how useful ERROR_OLD_STATEID for client? What client suppose to do
> after receiving this error?

According to the spec, OLD_STATEID should be returned for any stateid
that is not the current correct one but did designate (earlier) that
same file-lockowner pair.  So if an open assigns stateid X and
you then LOCK/UNLOCK a bunch of times and the current stateid is
X+n, then any stateid between X and X+n-1 (inclusive) results in 
OLD_STATEID.

In the case of requests that have both a stateid and a seqid, there
isn't much value in the distinction between between BAD_STATEID
and OLD_STATEID.  Getting either indicates that the client or
server is broken somehow (or a router is stomping on your packets,
etc.).

The point of OLD_STATEID is for requests that don't have seqid's
(e.g. READ and WRITE).  In these cases BAD_STATEID indicates someone
is broken, but OLD_STATEID doesn't.  On OLD_STATEID, the client will
probably retry to deal with a synchronization problem.  Suppose you
have IO requests in-flight when a subsequent request bumps the 
stateid.  Depending on request ordering, the IO requests may 
get an OLD_STATEID error, upon receiving which, the client can
retry with the new stateid.  The client could wait for all such
in-flight requests to return before issuing the new request but,
sometimes he may not know at the time the request is issued(some 
cases of OPEN), such synchronization could be annoying given 
that IO requests typically are done (essentially) asynchronously,
and in most cases ordering is good enough that the optimistic 
approach of just issuing the new request will work OK.  OLD_STATEID
allows the client a clean way of dealing with the case in which
the stateid-bumping request and the IO request are received by the
server in the "wrong" order.
 
>   > Once I have the address of a state structure, I can use this
>   > to find the
>   > corresponding owner structure which has the current seqid and replay
>   > information.  So at this point, I can notice a replay and respond.
>   >

> So, you don't store stateid (or even full request) for reply message, 
> but you are based
> only on seqid = stored_seqid? How you could be sure, that it's real 
> replay, but not logical error?
> I want to be sure at this point, that I understand replay correctly: 
> for me it's real
> retransmission of exactly the same package. Is it true?

Right now, I only check the seqid and operation.  I might save
more information if I find that there are broken clients that
are sending a seqid that matches a previous request with a 
different request.  Saving the whole operation seems excessive
to me, particurlay given OPEN which can be fairly large.  If
this really turns out to be a problem (and I kind of doubt it
will), then maybe saving a 64-checksum of the operation seems
reasonable.  

The issues are similar to the normal reply cache.  I don't know
what other systems do, but there we match on transaction id and 
then check a few other items.  We certainly don't save and check 
the entire request.  I doubt many systems do. 

> BTW, do you check lease time before reply?

Right now my lease expiration code isn't there yet.  My inclination
is to treat replay as merely retransmitting what already happened,
so I wouldn't check it.

>   > If it is not a replay (and we don't have a BAD_SEQID error), then I
>   > can check the stateid against the current stateid in the
>   > state structure and generated aN OLD_STATEID error if appropriate.
>   >
>   > I thought this was discussed in the session Andy organized regarding
>   > order-of-processing issues at the last bake-off.  I thought this
>   > was on the flow-charts that we came up with.  Then I again I was
>   > pretty tired so maybe my memmory is faulty.  In any case I think this
>   > should be documented somewhere (implementation RFC?).
>   >
>   > >
>   > > > BTW, seqid = stored_seqid doesn't mean real replay, because full
request
>   > > > must be the same, and
>   > > > NFS Server should keep previous request to compare it with current
one. In
>   > > > some implementation it's done on RPC layer.
>   > > > From my point of view, including index inside stateid is enough to
monitor
>   > > > replay without seqid at all. (which makes live more easy)
>   > >
>   > > It sounds to me like you are suggesting removing seqids from the
protocol
>   > > entirely, and relying on stateids to provide replay protection for
>   > > non-idempotent operations.  Perusing the protocol, it seems that
every
>   > > non-idempotent operation does change a stateid, so it should be
possible
>   > > to use stateids for replay protection and still have the correct
replay
>   > > semantics.
>   >
>   > I don't think so.  In the case of open, I don't see how you can do
without
>   > a seqid.  The fact that it generates a stateid (updated or not)
doesn't
>   > give you any replay protection.
>   >
>   > I send an open for read-write, deny=read-write.  It succeeds and I
send
>   > back a stateid.  The reply is lost.  A replay of the OPEN is sent and
>   > it fails because open for read or write is denied, which is definitely
>   > not what you want.  You might fall back on various kind of ad hoc
replay
>   > protection mechanisms specific to OPEN but that doesn't give me a very
good
>   > feeling.

> I don't see any place when you need both seqid and stateid in one request.
> OPEN may take seqid and generate stateid, and stateid will be used later
> without seqid

It is possible that you might be able to come up with something along
these lines.  But I don't think it is easy.  Unless you are prepared
to devote 32 bits of the stateid to actually being the seqid
(e.g. for sequencing of OPEN's and CLOSE's in the same sequence space
one of which has a seqid and the other a stateid), you have a lot
of edge conditions to deal with.  Devoting 32 bits of stateid to
a sequence isn't possible if stateid is kept at 64 bits.  What
might be posssible is making stqeid 96 bits, 32 of which are
defined as a sequence number and the rest designating a 
(file,lockowner)-pair which doesn't change on each state update. 

> But, probably, changing seqid to stateid is really too late now
> (even if it's needed only for OPEN).

There may be some official definition of the proper standards right
now, but I'd say that such a significant change shouldn't be made, 
unless:

     The protocol just won't work as it stands.

     There is major class of servers or clients that just can't
     implement the protocol as it stands.

     There is a *major* performance problem with the protocol
     as it stands in important environments.

If what we have is implementable, let's implement it.

-

---

From: Mike Eisler <[email-masked]>
Date: Wed, 31 Jan 2001 12:07:29 -0800 (PST)

> agree on this issue before connectathon..

            check stateid
            /     |  \  \
           /      |   \  \
          /        \   \  \
         /          \   \   \_______
	/            |   \          \
      stale         good  old      bad
      /               |     \       |
      |               |     |   server can't bump seq num  
      |               |     |   client undo seq num increment
      |               |     |   don't renew lease  
      |               |     |   NFSERR_BAD_STATEID  
seq knowlege is       |      \
reset on client       |       \
and server            |    check sequence number
NFS4ERR_STALE_STATEID |          /       \
                      |     bad or good   replay (should hit this) 
                      |         |         send from replay cache
                      |         |
		      |    good: server increment seq num 
		      |    good: client leaves seq num alone
		           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
mre>If the sequence number is good, then why does client leave its seq
num alone?  Perhaps you are assuming the client increments seq# when
the request is sent, rather than when the response is received. If so,
you might make this clearer, not that I agree with that implementation
practice.

		      |    NFSERR_OLD_STATEID
		           ^^^^^^^^^^^^^^^^^^^^
mre>What happens to the sequence number if NFSERR_OLD_STATEID is
returned in this branch?

		      |
             check sequence number
	     /       |      \
	    /        |       \
	   /         |        \
	bad       replay      good
	 /           |         \
don't bump seqnum    |          \
don't renew lease?   |           \
NFS4ERR_BAD_SEQ_NUM  |            \
	             |             \
           don't bump seq num       \
	   return replay             \ 
	        |                     |
	   check lease                |
		|                     |
            bad  good                 | 
            /     \             check lease
       don't    renew lease    /      |
       renew                  /       |
       lease                bad     good 
       
mre> Should a replay a renew a lease?
This leaves the server open to attacks. Keep 
in midn that the lease is on all the open
and locked objects sharing the client id.
it's odd that this replay branch renews the lease
but the old stateid --> replay seq. num. branch
does not.

			     /        |
			    /         |
                NFS4ERR_EXPIRED       | 
	         seq num bumped       |
                 ^^^^^^^^^^^^^^
mre>Why increment sequence number on an error?

	-mre