Subject: lock stateid, sequence number and lease interaction

From: "William A.(Andy) Adamson" <[email-masked]>
Date: Fri, 22 Sep 2000 10:53:30 -0400

There needs to be an agreement on the interaction between
the lock sequence number, lease, and stateid error checking.

One issue is when does the client upon receiving an error
on a lock sequence number mutating operation decrement
it's lockowner sequence number?

I've divided the operations into three catagories and shown
the server's processing logic with questions for each, and 
would like to hear comments....

In what order is everyone else doing this processing on the 
server?

Operations that have a stateid and a sequence number 
---------------------------------------------------- 
CLOSE, LOCK, LOCKU, OPEN_DOWNGRADE, 
OPEN_CONFIRM (stateid in verifier otherwise server 
can't locate lockowner)

The stateid has to be checked first - it is the only way
to find the lockowner.  If the stateid is bad, the sequence
number cannot be bumped because the lockowner can't be 
identified. So, the client when getting a NFS4ERR_XXX_STATEID
error needs to decrement the lockowners sequence number otherwise
it will be inconsistant for other lockowner operations.

Should the lease be renewed on a good stateid and bad sequence number?
If so, what error should be returned in the case that the
lease has also expired (NFS4ERR_BAD_SEQ or NFS4ERR_EXPIRED)?

Should the lease be renewed on a replay? Yes, the stateid is valid.
What if the lease has expired on a replay?

Should the sequence number be bumped when the lease is expired?

        check stateid
	/            \
      bad           good
      /              |
can't bump seq num   |
don't renew lease    |
NFS4ERR_XXX_STATEID  |
                     |
                     |
             check sequence number
	     /       |      \
	    /        |       \
	   /         |        \
	bad       replay      good
	 /           |         \
don't bump seqnum    |          \
don't renew lease?   |           \
NFS4ERR_BAD_SEQ_NUM  |            \
	             |             \
           don't bump seq num       \
           don't renew lease?        \
	   return replay              | 
				      | 
                               check lease
			       /      |
                             bad    good 
			     /        |
			    /         |
                NFS4ERR_EXPIRED       | 
		(seq num bumped?)     |
		                      |	
				      |
                                  renew lease
	 	               perform operation

Operations that have a sequence number, and no stateid
------------------------------------------------------

OPEN 

Should the lease be renewed on a valid clientid and a bad 
sequence number? If so, what error should be returned in the 
case that the lease has also expired 
(NFS4ERR_BAD_SEQ or NFS4ERR_EXPIRED)?

Should the lease be renewed on a valid clientid and replay? Yes, 
the clientid is valid.  What if the lease has expired on a replay?

Should the sequence number be bumped when the lease is expired?

        check clientid
	/            \
      bad            good
      /                |
don't bump seq num     |
don't renew lease      |
NFS4ERR_STALE_CLIENTID |
                       |
             check sequence number
	     /       |      \
	    /        |       \
	   /         |        \
	bad       replay      good
	 /           |         \
don't bump seqnum    |          \
don't renew lease?   |           \
NFS4ERR_BAD_SEQ_NUM  |            \
	             |             \
           don't bump seq num       \
           don't renew lease?        \
	   return replay              | 
				      | 
                               check lease
			       /      |
                             bad    good 
			     /        |
			    /         |
                NFS4ERR_EXPIRED       | 
		(seq num bumped?)     |
		                      |	
				      |
                                  renew lease
	 	                  perform operation

Operations that have a stateid and no sequence number
------------------------------------------------------
READ, WRITE, RENEW

This case is clear, the lease is renewed only if the 
stateid is valid.

        check stateid
	/            \
      bad           good
      /              |
don't renew lease    |
NFS4ERR_XXX_STATEID  |
                     |
                     |
               check lease
		/      |
               bad    good 
		/        |
	       /         |
   NFS4ERR_EXPIRED       | 
	                 |	
	                 |
                    renew lease
                    perform operation

---

From: Mike Eisler <[email-masked]>
Date: Fri, 22 Sep 2000 11:05:09 -0700 (PDT)

I think it is very cool that the wg list is getting these kinds of questions!

Here are my responses, given from someone who hasn't attempted to
implement it. It's quite possible that since you have actual implementation
experience that you'll find flaws in my reasoning.

> Operations that have a stateid and a sequence number 

If the client gets a bad stateid status from the server, then playing
with the sequence number isn't going let the client recover, because
the next operation requiring a stateid is going to fail. The
situation is thus similar to a network partition. The only recourse
is for the client to issue a SETCLIENTID operation, which will
cause the server to free any locks held by the client previously.
The client could then attempt to reclaim all the locks previously held,
and if the change attribute doesn't indicate anyone has modified the file in
the intervening time, successful reclaim would allow application to continue
as if nothing happened.

> Should the lease be renewed on a good stateid and bad sequence number?

No, because the stateid could have been from the distant past.

> Should the lease be renewed on a replay? Yes, the stateid is valid.

Depends. Let L be the sequence number the server last received.

If the request has a sequence number r < L, then the lease should not be
renewed. If r == L or r == L+1, then the
lease must be renewed. If r >= L+2, the lease need not be renewed.
 
> What if the lease has expired on a replay?

Three scenarios:

	- the server has the last response in it's cache (either the
		RPC dup request cache, or the lock cache), then it's ok to
		return that response, otherewise ...

	- the nfs_lockowner state is not around. The server has no
		idea if this is a replay or not. In any case, return 
		NFS4ERR_EXPIRED. 
	- the nfs_lockowner state is around. If r < L, then NFS4ERR_BAD_SEQID
		is returned. If r == L, then the stored response is returned.
		If r == L+1, return NFS4ERR_EXPIRED. If r >= L+2, return
		NFS4ERR_BAD_SEQID.
				
> Should the sequence number be bumped when the lease is expired?

No. Once the lease has expired, the nfs_lockowner state is immutable
until it is disposed of, or the client issues a SETCLIENTID.

> Operations that have a sequence number, and no stateid

No, NFS4ERR_BAD_SEQ should be returned.

> Should the lease be renewed on a valid clientid and replay? Yes, 

Depends. Let L be the sequence number the server last received.

If the request has a sequence number r < L, then the lease should not be
renewed. If r == L or r == L+1, then the
lease must be renewed. If r >= L+2, the lease need not be renewed.

> the clientid is valid.  What if the lease has expired on a replay?

Three scenarios:

	- the server has the last response in it's cache (either the
		RPC dup request cache, or the lock cache), then it's ok to
		return that response, otherewise ...

	- the nfs_lockowner state is not around. The server has no
		idea if this is a replay or not. In any case, return 
		NFS4ERR_EXPIRED. 
	- the nfs_lockowner state is around. If r < L, then NFS4ERR_BAD_SEQID
		is returned. If r == L, then the stored response is returned.
		If r == L+1, return NFS4ERR_EXPIRED. If r >= L+2, return
		NFS4ERR_BAD_SEQID.

> Should the sequence number be bumped when the lease is expired?

No. Once the lease has expired, the nfs_lockowner state is immutable
until it is disposed of, or the client issues a SETCLIENTID.

> Operations that have a stateid and no sequence number

Agreed.

	-mre

---

From: "William A.(Andy) Adamson" <[email-masked]>
Date: Fri, 22 Sep 2000 14:54:30 -0400

>the next operation requiring a stateid is going to fail.

here's where i struggle with the assumptions behind the concept of lockowner 
on the client.

first, to set the stage:

the stateid -> lockowner,lock,file association.
there are many stateid's associated with a lockowner, one per open file.
there is one seq num counter associated with a lockowner that services all 
stateid's.

lets futher say that a lockowner is defined as the clientid and the pid, or 
from the clients perspective, a lockowner = pid.

is there an assumption that all file access's are serialized per lockowner? or 
does the protocol allow for per lock owner async file access?

for example, a userlevel pthread application running in the process could have 
serveral files opened, and could spawn 2 threads that each try to lock a byte 
range of two different files. in this case, one thread could get a bad stateid 
status, andit would not be true that the next operation requiring a stateid
 would fail if it came from the other thread. 

if, however, lockowner file access is synchronous, it would be true that the 
bad stateid error status -> the next stateid operation fails.

---

From: "Noveck, Dave" <[email-masked]>
Date: Fri, 22 Sep 2000 12:19:49 -0700

> does the protocol allow for per lock owner async file access?

I believe async access is allowed.  The performance implications of restricting
file access requests to one-per-lockowner at a time are kind of distressing.  

> would fail if it came from the other thread. 

Your example requires more than mere access.  If operations change the 
locking state (e.g. locking a byte), opposed to accessing the file, they have
a sequence number and operations that have a sequence number have to be
serialized.  
Only one should be outstanding at a time.

     Operations state have a stateid and no sequence id are not single-
     threaded.

     Operations that have a sequence id need to be signle-threaded on a per-
     lockowner basis.

> bad stateid error status -> the next stateid operation fails.

There is a case in which you get validly get a stateid error (OLD_STATEID)
if one thread is doing a lock while another is doing an io.  In this case,
the IO may get OLD_STATEID since the stateid for the file changed and
a request issued with the old stateid which arrived after the lock changed
the stateid will fail.  In this case, the IO can be retried with the updated 
stateid and all will be well.  But no request shich has both a stateid
and a sequence id should get this error.  There should only be one such
request outstanding for a given lcokowner at a given time.

---

From: Mike Eisler <[email-masked]>
Date: Fri, 22 Sep 2000 12:29:07 -0700 (PDT)

>From: "William A.(Andy) Adamson" <[email-masked]>
>

The client must serialize on a per nfs_lockowner basis all accesses
that involve a sequence number.  So if the client sends what it thinks is
a valid stateid and sequence number pair, and the server say, no,
something very bad has occurred on the client or server or both, e.g. a
bug or a skilled attacker.

I believe every operation that takes a seqid and stateid as an argument
returns a new stateid (though I haven't made an exhaustive check ...
if there is an exception, then this might be a protocol bug). It should
also be the case that every opersation that takes a stateid but not
a seqid, does not return a new stateid.

So in fact there are not many stateids associated with a nfs_lockowner,
there's only one active at one time, plus the stateid argument of the request
in the lock manager replay cache.

> would fail if it came from the other thread. 

The client code has to synchronize the accesses. For the conventional
in-kernel NFS file system model, this is straightforward. For
use-levle models, it is probably best that each thread be assigned
a unique nfs_lockowner. 

	-mre

---

From: "Noveck, Dave" <[email-masked]>
Date: Fri, 22 Sep 2000 12:51:40 -0700

> use-levle models, it is probably best that each thread be assigned

But making each thread its own nfs_lockowner might not have the semantics
that you want.  One thread might lock a region and send a message
to another thread to do something using that region whereupon that
other thread will fail since someone else (the other thread has the
region locked).

Is there anybody out there planning user-level NFS-v4 implementations
for whom this might be an issue?

---

From: Mike Eisler <[email-masked]>
Date: Fri, 22 Sep 2000 12:58:57 -0700 (PDT)

>From: "Noveck, Dave" <[email-masked]>

>request outstanding for a given lcokowner at a given time.

Or the client could serialize stateid operations when there is an
operation involving a seqid in progress, and vice versa. Either way
though, given that frequency of some of those operations, such as open,
this could have nasty performance effects.

I wonder if it might be more reasonable for the server to keep a window
of previous stateids for purpose of handling operations that take a
stateid and not a seqid as an argument?

	-mre

	-mre

---

From: Mike Eisler <[email-masked]>
Date: Fri, 22 Sep 2000 13:04:49 -0700 (PDT)

>To: "'Mike Eisler'" <[email-masked]>, [email-masked]
>Cc: [email-masked]
>Subject: RE: lock stateid, sequence number and lease interaction 
>Date: Fri, 22 Sep 2000 12:51:40 -0700
>MIME-Version: 1.0

>other thread will fail since someone else (the other thread has the

The message from thread 1 to thread 2 could contain a stateid.

There may be other other examples that are unworkable though. In
which case, the nfsv4 libarary the threads are using can take care
of the serialization when nfs_lockowners are shared.

	-mre

---

From: "Noveck, Dave" <[email-masked]>
Date: Fri, 22 Sep 2000 13:35:12 -0700

> this could have nasty performance effects.

You would only have to serialize when the open (or other such operation)
was on the same file as one just using a stateid.  Of course the 
problem with open is that you may not know that you are opening the
same file when you issue the open.

With the optimistic approach (of returning OLD_STATEID and then
retrying), the only conflict is when you have IO and state-modifying
operation by the same lockowner on the same file.  I'm hoping
this won't be a problem very often.

> stateid and not a seqid as an argument?

Possibly.  The issue is what the server has to do to validly verify
that there is an agreement between the client and server about the 
locking state of the file.

As I understand it, the reason for changing the stateid on each 
lock-state-modifying request was to catch a delayed replay (our
old friends the Byzantine routers, again) of, for example, a WRITE
which was issued before an UNLOCK/CLOSE and now should not be 
processed when the state of locking for the file has changed.

Maybe the the spec needs some words to define when a server may
validly decide that an old stateid has not been invalidated by
lock-state-modifying requests thathave happened in the interim.

The idea might be that if only lock-adding requests have occurred,
the server can accept an old stateid.  Also if unlocks have occurred
and they don't span the area of the io.  I think it might be 
difficult for the server to do this checking in the general case,
but if the spec set forth the general rules, servers might find
useful cases that could be easily checked and avoid having to
return OLD_STATEID in cases that were important for performance.

---

From: Mike Eisler <[email-masked]>
Date: Fri, 22 Sep 2000 14:06:59 -0700 (PDT)

>locking state of the file.

So what if instead of a window, for every open file, the server records
the last stateid it returned for a stateid modifying operation on that
file.

Such a scheme covers the 99% case when user 1 is messing with his
file, user 2 is messing with her files, and each is doing operations
that modify the stateid of the common nfs_lockowner. If user 1's
applciation doesn't synchronize stateid modifying operatings to
his file, then there will be worse problems for that application
than the bad effects of retried IO operations.

>processed when the state of locking for the file has changed.

Certainly, if the file is closed, the server can't allow old stateids,
and my refinement above easily covers the situation.

BTW, my intent was not to unfreeze the spec for what is admittably a
half-baked idea, but to provide fodder for server implementors, and
ultimately, the implementation i-d. My suspicion is that server vendors
will be compelled to something in this area, just as they were
compelled to use Chet's dup request cache design.

	-mre

---

From: "Noveck, Dave" <[email-masked]>
Date: Fri, 22 Sep 2000 14:29:23 -0700

> the last stateid it returned for a stateid modifying operation on that

I think that could work.
 
> and my refinement above easily covers the situation.

Yes.

To deal with unlock you could record wether the last state-change
was an unlock and the associated range.

I think it's very likely that this would deal with 99% of the
problem.

> compelled to use Chet's dup request cache design.

Given the above, I think it's three-quarters baked, at the very least.

My concern is that the spec as it stands might foreclose this 
option.  I don't know that that is the case, but if it is, it makes
sense (at least to me) to fix things so that it is clear what
servers are allowed to do in this area before we go to Draft
Standard.

---

From: Mike Eisler <[email-masked]>
Date: Fri, 22 Sep 2000 15:50:05 -0700 (PDT)

>servers are allowed to do in this area before we go to Draft

I don't think it forecloses it, but agree that DS is a good time to
make it clear.

	-mre