Subject: "indivisible lock" semantics

From: Mike Kupfer <[email-masked]>
Date: Mon, 10 Jan 2000 16:33:08 -0800

Spencer and I exchanged some mail last week about the fact that v4
locks are indivisible (i.e., they follow Windows semantics, rather
than Unix semantics).  The rest of this message contains excerpts from
two messages that I sent to Spencer.

I'm not proposing a change to the protocol, but I would like to put
this on the table for discussion, to see if anyone has further
comments that might impact the protocol or spec.  The reason I'm not
proposing a protocol change is that I think it's rare for Unix
applications to take advantage of "divisible lock" semantics.  Given
the date, I think it's more important to move forward with what we
have.

Excerpt #1:

>>>>> "Mike" == Mike Kupfer <[email-masked]> writes:

    Mike> Page 58, Section 8.2.3: for a Unix client talking to a Win32
    Mike> server, some entity, either the client or the server, has to
    Mike> map a Posix locking request to (potentially) a series of
    Mike> Win32 locking requests.  The series of Win32 requests should
    Mike> be atomic.  For example, it is a legal Posix request to
    Mike> unlock a hole out of the middle of an existing lock.  The
    Mike> Win32 API expresses this as removing the old lock and
    Mike> creating two new ones.  The atomicity requirement is that
    Mike> nobody else create a conflicting lock between the time the
    Mike> first lock is removed and the two new locks are created.

    Mike> The I-D places this responsibility on the client, asserting
    Mike> that it is easier for the (Unix) client to do this
    Mike> conversion than it is for the (Win32) server.  I think this
    Mike> is false, particularly in light of the atomicity issue.

    Mike> I don't see any simple ways to deal with the atomicity
    Mike> issue.  Fortunately, it's rare for a Unix application to
    Mike> change subranges of an existing lock, so perhaps the
    Mike> protocol need not provide an atomicity guarantee.  If a
    Mike> conflicting lock is created in the middle of a series of
    Mike> "Win32" operations, the client could simply treat the lock
    Mike> as being lost and notify the application.

    Mike> So I guess I'm asking that the last paragraph of Section
    Mike> 8.2.3 be rewritten to clarify this issue.  Let me know if
    Mike> you want help with specific verbage.

Excerpt #2:

>>>>> "Mike" == Mike Kupfer <[email-masked]> writes:

    Mike> Hmm, the more I look at the indivisible locks semantics, the
    Mike> less I like them.  Suppose you have two processes, A and B,
    Mike> each of which has a read lock on a byte range.  Now suppose
    Mike> process A submits a blocking request (F_SETLKW) to upgrade
    Mike> half the region to a write lock.  You can do this with the
    Mike> current NLM protocol.  Process A simply requests the upgrade
    Mike> and goes to sleep until the server grants it.  With
    Mike> indivisible locks, process A goes to sleep and wakes up
    Mike> every now and then to see if there are conflicting locks for
    Mike> the range.  Once there are no more conflicts, process A can
    Mike> release its lock and obtain the 2 new locks (one for the new
    Mike> write-lock range, one for the remaining read-lock range).
    Mike> Yuck.

    Mike> Of course, a Win32 server would have to do something similar
    Mike> if the protocol supported Posix-style locking.  The
    Mike> difference is that with indivisible locks, the client has to
    Mike> poll the server.  (Or I suppose it could submit a dummy
    Mike> write lock request and wait for the server to grant it.)
    Mike> With Posix-style locking, the server only has to poll the
    Mike> local locking interace provided by the OS.

    Mike> I guess the good news is that this can be considered unusual
    Mike> behavior, and that most applications will not split up
    Mike> existing locks like that.

    Mike> Anway, here's a counter-proposal for the first replacement
    Mike> paragraph that you suggested:

    Mike> "The byte range of a lock is indivisible.  A range may be
    Mike> locked or unlocked between read and write but may not have
    Mike> subranges unlocked or changed between read and write.  These
    Mike> are the semantics provided by the Win32 environment but only
    Mike> a subset of the semantics provided by Unix environment.
    Mike> This means that Unix clients may need to emulate a single
    Mike> locking request with multiple NFS calls.  For example, if a
    Mike> subrange is unlocked, the client will need to unlock the
    Mike> entire range and lock the new regions.  This creates a
    Mike> window during which a conflicting lock can be taken by
    Mike> another client.  If this happens, the server will reject the
    Mike> client's attempt to create the new regions, and the client
    Mike> will notify the application that the lock has been lost."

mike

---

From: "Noveck, Dave" <[email-masked]>
Date: Tue, 11 Jan 2000 08:18:46 -0800

> the date, I think it's more important to move forward with what we

I agree that this is not something that should cause us to delay the
protocol.  I'm not even sure that we would need to accomodate this
if we had lots of spare time.

I'm curious about the adjective "rare" as opposed to "non-existent".
I'm not saying that such programs don't exist, but I've never
seen one.  Has anybody else?

>     Mike> as being lost and notify the application.

It wouldn't necessarily know.  It could be that another client got 
a conflicting lock and gave it up before you got around to getting 
the second locked region.  The result would be that you wouldn't
have the atomicity guarantee and you wouldn't know it.

As you say, the assertion that this allows you to duplicate UNIX
semantics is false.  I think the spec should say that the protoocl
allows you to provide a useful subset ("the useful subset" would be
more correct) of UNIX semantics but that atomically unlocking a 
subrange is not possible.

>     Mike> write-lock range, one for the remaining read-lock range).

I want to be clear about the details here.  Let's suppose that 
region Z consists of two abutting sub-regions: X and Y.

In your example, process A has a read lock on Z and is attempting
to upgrade his lock on the sub-region X to a write lock.

The overall transition [read(Z)] -> [write(X)+read(Y)] is *not*
atomic in the UNIX locking implementations that I've seen.  If
there were two processes trying to do this, they would either 
have to wait forever or get EDEADLCK and I don't think that 
happens.  

In the code I've seen, there are two separate atomic state transitions,
one to unlock X and then one to get the write lock on X.  Conflicting
locks on the region X are not excluded between the two state transitions.

The following are each atomic but the sequence is not atomic (it's
molecular):

    1) [read(X)] -> [read(Z)]
    2) [read(Z)] -> [write(X)+read(Z)]

My understanding is based on the flock implementation in Irix.
I did a rewrite for performance and scalability and so I looked
pretty closely at making sure that I was duplicating the existing
semantics, although this was over a year ago and I may have forgotten
some part of this.  I didn't do an exhaustive comparison but this
aspect of the locking implementation seemed to come over pretty
directly from BSD.

Does anybody have a different understanding of what UNIX semantics
are in this regard?

The question of upgrade poses some issues even apart form the
divisiblity issue.  If you simplify your example to a single region and 
say that two processes are trying to upgrade a lock for the region X
from read to write.  With the spec as it is, what happens?  A and
B both keeps sending upgrade reequests which are denied.  They
continue to poll and maybe do it slower after a while but they 
don't make any progress.

There is no way that the server can ever grant A's request for
upgrade without revoking B's lock.  The conclusion that I draw
is that upgrade should be done by the client using an unlock
followed by getting a write lock.  This is not atomic but I
don't think UNIX has atomicity in this regard now (don't know
about Windows).  There is also a performance issue in that
this turns an upgrade into a two-RPC operation, but maybe upgrade
is not common enough for that to be a worry.

>     Mike> locked or unlocked between read and write but may not have

locked or unlocked or changed between read and write [but I am still 
unsure about supporting that]

>     Mike> will notify the application that the lock has been lost."

I would replace the last sentence with the following:

      Thus, atomically unlocking a subrange (as provided locally by
      UNIX systems) may not be possible under NFS version 4.

---

From: "Noveck, Dave" <[email-masked]>
Date: Tue, 11 Jan 2000 11:42:16 -0800

> >>>>> "Dave" == Noveck, Dave <[email-masked]> writes:
> 
>     Dave> I'm curious about the adjective "rare" as opposed to
>     Dave> "non-existent".  I'm not saying that such programs don't
>     Dave> exist, but I've never seen one.  Has anybody else?
> 
> I can't point to a specific program that expects indivisible locks,
> but
> 
> 1. Mr. Murphy says that as soon as we declare that nobody does that,
> someone will come along and do it.
> 
> 2. I do remember being surprised at some of the locking calls CAD
> programs make.
> 
> 3. I can imagine someone wanting to process a UNIX mail file by
> initially read-locking the entire file, then obtaining write locks as
> necessary to process user edits.

I can imagine someone wanting to do that (i.e 3) but I have trouble 
imagining someone actually implementing it and dealing with the deadlock 
issues.

I guess I can't say nobody does this (splitting a lock range).  I guess 
I'll say that I have never seen such a program nor heard any reliable 
report of one.  Sort of like Alien Abductions, I guess :-)

> 
>     Dave> It wouldn't necessarily know.  It could be that another
>     Dave> client got a conflicting lock and gave it up before you got
>     Dave> around to getting the second locked region.  The result
>     Dave> would be that you wouldn't have the atomicity guarantee and
>     Dave> you wouldn't know about the conflicting lock.
> 
> Gack, you're right.  To be safe, a UNIX v4 client would have to
> disallow any locking operations that open a window for a conflicting
> lock.

But these operations (the ones which open a window) are all the ones
we are talking about here, those that change a sub-region.  The
UNIX v4 client can't disallow them, and he can't perform them safely.
I think he has to perform them unsafely.

> 
>     Dave> I want to be clear about the details here.  Let's suppose
>     Dave> that region Z consists of two abutting sub-regions: X and Y.
> 
>     Dave> In your example, process A has a read lock on Z and is
>     Dave> attempting to upgrade his lock on the sub-region X to a
>     Dave> write lock.
> 
>     Dave> The overall transition [read(Z)] -> [write(X)+read(Y)] is
>     Dave> *not* atomic in the UNIX locking implementations that I've
>     Dave> seen.  If there were two processes trying to do this, they
>     Dave> would either have to wait forever or get EDEADLCK and I
>     Dave> don't think that happens.
> 
> The implementation is not the API spec.  My reading of the UNIX '98
> spec <http://www.opengroup.org/onlinepubs/007908799/xsh/fcntl.html> is
> that if process A attempts such an upgrade (using F_SETLKW) while
> process B has region Z read-locked, process A will sleep until process
> B releases its lock.  If both processes A and B attempt such an
> upgrade, you'll get a deadlock, which the OS might or might not
> detect.

I agree that the spec, and the implementations I know about will have
A sleep until B releases its lock.  As far as the simultaneous 
upgrade scenario, I don't see that the spec addresses this one way 
or the other.  It boils down to the same upgrade atomicity question
and the spec simply says that each byte of region X winds up write
locked.  You could argue that the actual language "replaced by
the new lock type" while it doesn't imply atomicity of the entire
operation, does seem to imply that for each byte, the locking type 
does not go through any intermediate state (like unlocked).  If it 
is a fact that most (or all) UNIX implementations don't have this 
property, that would count (for me) as strong evidence that that
interpretation of the spec isn't really a tenable one. 

> 
>     Dave> The question of upgrade poses some issues even apart form
>     Dave> the divisiblity issue.  If you simplify your example to a
>     Dave> single region and say that two processes are trying to
>     Dave> upgrade a lock for the region X from read to write.  With
>     Dave> the spec as it is, what happens?  A and B both keeps sending
>     Dave> upgrade reequests which are denied.  They continue to poll
>     Dave> and maybe do it slower after a while but they don't make any
>     Dave> progress.
> 
>     Dave> There is no way that the server can ever grant A's request
>     Dave> for upgrade without revoking B's lock.  The conclusion that
>     Dave> I draw is that upgrade should be done by the client using an
>     Dave> unlock followed by getting a write lock.  This is not atomic
>     Dave> but I don't think UNIX has atomicity in this regard now
>     Dave> (don't know about Windows).  
> 
> The UNIX '98 spec is less clear here.  "Atomic" does not appear in the
> fcntl documentation.  What it does say is "the previous lock type for
> each byte ... will be replaced by the new lock type".  I will contact
> our local standards gurus for an interpretation of that phrase.

Gee, if it is supposed to be atomic but you don't have to detect 
deadlock, then the protocol as it stands, by causing the client to
loop forver, will be more POSIX-conformant, for this particular
case than what I believe to be the typical UNIX behavior for
local files.

I'm going to try this on some Solaris and Alpha machines and see
how they behave for local files.
 
>     Dave> locked or unlocked or changed between read and write
> 
> Right, thanks.
> 
>     Dave> I would replace the last sentence with the following:
> 
>     Dave>       Thus, atomically unlocking a subrange (as provided
>     Dave> locally by UNIX systems) may not be possible under NFS
>     Dave> version 4.
>  
> Yeah, let me see what our Standards folks say about atomicity
> requirements.  Then we figure out what to tell UNIX clients they need
> to do.