Subject: a Grand Unified Locking Proposal (GULP, or perhaps, GULP! :-)

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Wed, 12 Jan 2000 18:12:43 -0500

Eric suggests that a URL-based locking model should be mapped into the
underlying collection resources that implement the namespace.  I agree
with both this conclusion and the reasoning leading up to it.

But I think it is simpler to model namespace protection and state
protection as being two results of a single kind of lock, as opposed
to the result of two different kinds of locks.  This avoids the
problem of describing how namespace locks and state locks interact.

In an attempt to make the proposal both understandable and complete,
I've broken it into two parts.  The first part is a series of bullets,
which largely correspond to the "URL-based locking" proposal I mailed out
a while ago.  The second part is the same series of bullets fleshed out
with a more formal description of each bullet in terms of an underlying
resource model and effects on the visible lock state of resources.

**************************

GULP: Part I

- A URL identifies a resource.
- A LOCK request creates a lock on the request URL.
- An UNLOCK request removes all locks with the specified lock token.
- A lock on a URL protects which resource is identified by that URL.
- A Depth:N lock on a URL locks any URL that extends the locked URL by no
more than N segments.
- A Depth:infinity lock on a URL locks all URL's that extend the locked URL.
- If an exclusive lock identifies a resource, no other lock of that type can
identify that resource.
- A write-lock on a URL protects the body and dead properties of any
resource identified by that URL.

**************************

GULP: Part II

- A URL identifies a resource.

The URL "/" identifies a resource. A collection contains a set of bindings,
where a binding is a mapping from a URL segment to a resource. If "/path"
identifies a collection C, and C contains a binding that maps the segment
"x" to resource R, then the URL "/path/x" identifies resource R.

- A lock is on a URL. Every lock has a lock token and a lock owner.

Every lock on a resource has a name which is a relative URL (i.e. a slash
separated sequence of URL segments). Every LOCK request that succeeds
results in a new globally unique lock token. Every lock token has an owner
that is the principal of the LOCK request.

- A LOCK request creates a lock on the request URL.

When a request of the form "LOCK /pathX" succeeds, a lock named "pathY/."
with a new lock token is added to the resource identified by "/", where
"pathY" is the result of applying standard URL path transformations to
remove all segments named "." or ".." from "pathX". If a collection C has a
binding from "segX" to resource R, and a request adds a lock named
"segX/pathZ" with token "L" to C, then the request adds a lock named "pathZ"
with token "L" to R. Similarly, if a collection C has a lock named
"segX/pathZ" with token "L", and a request (e.g. PUT, COPY, MOVE, BIND) adds
a binding in C from "segX" to resource R, then the request adds a lock named
"pathZ" with token "L" to R. If the attempt to add the lock named "pathZ" to
R fails, the request MUST fail.

- An UNLOCK request removes all locks with the specified lock token.

When a request of the form "UNLOCK /pathX; Lock-Token L" succeeds, then the
lock with token "L" is removed from the resource identified by "/". If a
collection C has a binding from "segX" to resource R, and a request removes
a lock named "segX/pathZ" with token "L" from C, then the request removes a
lock named "pathZ" with token "L" from R. Similarly, if a collection has a
lock named "segX/pathZ" with token "L", and a request (e.g. DELETE, MOVE)
removes a binding in C from "segX" to resource R, then a lock named "pathZ"
with token "L" is removed from R.

- A lock on a URL protects which resource is identified by that URL.

If a collection identified by the URL "/colX" contains a lock named "pathZ"
with token "L", if a request would change the resource identified by
"/colX/pathZ", the request MUST specify token "L" in an IF header and the
request principal MUST be the owner of token "L".

- A Depth:N lock on a URL locks any URL that extends the locked URL by no
more than N segments.

If a collection C has a binding to resource R, and a request adds a Depth:N
lock named "." with token "L" to C, then the request adds a Depth:N-1 lock
named "." with token "L" to R. Similarly, if a collection C has a Depth:N
lock named "." with token "L", and a request adds a binding in C to resource
R, then the request adds a Depth:N-1 lock named "." with token "L" to R. If
the attempt to add the lock named "." to R fails, the request MUST fail.
Conversely, the Depth:N-1 lock is removed from R whenever a binding to R or
the Depth:N lock is removed from C.

- A Depth:infinity lock on a URL locks all URL's that extend the locked URL.

If a collection C has a binding to resource R, and a request adds a
Depth:infinity lock named "." with token "L" to C, and this is the first
Depth:infinity lock named "." with token "L" on C, then the request adds a
Depth:infinity lock named "." with token "L" to R. Similarly, if a
collection C has a Depth:infinity lock named "." with token "L", and a
request adds a binding in C to resource R, then the request adds a
Depth:infinity lock named "." with token "L" to R. If the attempt to add the
lock named "." to R fails, the request MUST fail. If a collection C has a
binding to resource R, and a request removes the last Depth:infinity lock
named "." with token "L" from C, then the request removes a Depth:infinity
lock named "." with token "L" from R. Similarly, if a collection has a
Depth:infinity lock named "." with token "L", and a request removes a
binding in C to resource R, then a Depth:infinity lock named "." with token
"L" is removed from R. Note that multiple Depth:infinity locks named "."
with the same token can be placed on the same resource due to multiple
bindings to that resource in a Depth:infinity locked collection.

- If an exclusive lock identifies a resource, no other lock of that type can
identify that resource.

If a request attempts to add a lock named "pathZ" with token "L" and type T
to resource R, and R already has an exclusive lock named "pathZ" with type
"L" but with a different token, the request MUST fail. Similarly, if a
request attempts to add an exclusive lock named "pathZ" with token "L" and
type T to resource R, and R already has a lock named "pathZ" with type T but
with a different token, the request MUST fail.

- A write-lock on a URL protects the body and dead properties of any
resource identified by that URL.

If a resource has a write lock named "." with token "L", in order to modify
the body or dead properties of that resource, a request MUST specify token
"L" in an IF header and the request principal must be the principal that
created the lock.

**************************

OK, Jason, Yaron, Eric, et. al, what did I forget this time? (:-)

Cheers,
Geoff

---

From: "Eric Sedlar" <[email-masked]>
Date: Thu, 13 Jan 2000 12:46:34 -0800

This is pretty dense, but let me see if I get the gist of how your proposal
differs from mine:

You want to avoid having name and resource locks as separate entities, so
you basically say that a name lock (as in my proposal) locks the resource it
is bound to, if any.  If the lock is exclusive, you can't lock any other
name applied to that resource.  For example, if I have /a/foo.html and
/b/foo.html both identifying the same resource, if I exclusive lock
/a/foo.html, I can't protect the name "/b/foo.html" since I can't lock it.

Since the LOCK protocol request currently doesn't distinguish between name
and resource locks, you couldn't lock /b/foo.html anyway (which is why you
are ok with the restriction above), since the protocol request would try to
lock the resource identified by /b/foo.html as well as the name.

However, it does seem like there will be reasons to protect the namespace in
this way, and I think you are paying a price for reducing the number of
locks.

> - If an exclusive lock identifies a resource, no other lock of that type
can

Here's a scenario: it seems like if application A has an exclusive lock on
/a/foo.html (say because it is planning on updating the resource to create a
new version, and it wants to prevent lost updates) and application B wants
to only read /b/foo.html and protect the namespace so that it can find it
again later, application B cannot create a shared lock on /b/foo.html,
correct?  The problem is that application A will not actually update the
resource that app B is working with--it will just create a new revision.
(Although this may affect the revision selected by app B).  Is this an issue
your versioned locks deal with?

--Eric

----- Original Message -----
From: "Geoffrey M. Clemm" <[email-masked]>
To: <[email-masked]>
Sent: Wednesday, January 12, 2000 3:12 PM
Subject: a Grand Unified Locking Proposal (GULP, or perhaps, GULP! :-)

> resource model and effects on the visible lock state of resources.
Depth:N

---

From: Jim Whitehead <[email-masked]>
Date: Thu, 13 Jan 2000 17:03:15 -0800

A problem with this proposal (and, to be fair, the same problem is shared by
RFC 2518) is it never defines what a lock *is*. That is, there is no
sentence here that begins, "A lock is a ...". As a result, this makes it
hard to assess whether statements such as the following make sense: "A lock
is on a URL. Every lock has a lock token and a lock owner."

Initially, a lock was a metaphor, extending the meaning of real-world locks
into the realm of computer data.  Real-world locks have several properties.
They have mass and volume.  That is, there is a physical lock mechanism that
takes up space, and hence be located someplace.  Examples are a lock set
into a door, and a padlock, where the lock is separate from the thing being
locked, and is connected by hooks, or a chain. Locks also have some way to
open them, and provide access to the locked item, either via a key, or a
combination.  When locking a volume of space, such as a room, it is possible
to simultaneously lock people out (prevent access), and lock people in
(guarantee exclusive access).  Ownership of a real world lock is separate
from the ability to lock and unlock it.  While typically the owner of a lock
also has the ability to lock and unlock it, there are often others who have
the same ability. Think of your office door -- you probably don't own the
door, but you can unlock it.

A WebDAV lock is an abstraction that arbitrates operations on resources. A
WebDAV write lock simultaneously guarantees that only the lock owner (or
owners, in the case of a shared lock), can write to the resource, and that
non-lock-owners are prevented from writing to the resource. Lock ownership
in WebDAV is synonymous having the ability to perform the lock-arbitrated
operation and unlock the locked resource.

WebDAV locks have state, the equivalent to mass and volume for real-world
locks.  The only description of the state of a lock in RFC 2518 can be found
in the lock discovery property, which gives the state of a lock as
containing:

  - lock type
  - lock scope
  - lock depth
  - lock timeout time
  - lock token
  - lock owner
  - lock URL (implicit)

For any stateful abstraction, such as a lock, there are several meaningful
questions.  Is the abstraction a first-class object?  That is, is its state
and existence independent of other system objects, and does it have its own
independent identity?  Or is the abstraction a component of some other
object.  Following the real-world lock analogy, is the lock more akin to a
padlock, independent of the items being locked, or a door lock, where the
lock is a component of the door.

So far in WebDAV, lock state has been part of a resource, since resources
are the only stateful objects in HTTP.  The GULP proposal, with statements
like, "a LOCK request creates a lock on the request URL," seems to imply
that lock state is part of a URL.  This is a troubling assertion since URLs
have not, to date, been stateful objects.  But, a further examination of
GULP (in the section "a LOCK request creates a lock on the request URL")
shows that the lock state is kept on the locked resource's collection, and
perhaps on the locked resource as well. Thus the lock is not "on" the URL at
all, but is instead on the locked resource's parent collection, and on the
resource.  The lock certaintly affects the URL, but it isn't "on" the URL.

Having the lock state as part of the collection is troublesome, since it
implies that only WebDAV resources inside WebDAV collections may be locked.
This is an additional (and unnecessary) restriction over anything specified
in RFC 2518.  Furthermore, duplicating the lock state in the resource and
its parent collection seems unnecessary.

So, before we proceed, I would like to see a definition of a lock that
begins with "A lock is a ...", and I'd like to see a better description of
what constitutes the state of a lock, and where this state is kept.
Answering these questions will help clarify the rest of the semantics
described in the GULP proposal.

- Jim

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Geoffrey M. Clemm
> Sent: Wednesday, January 12, 2000 3:13 PM
> To: [email-masked]

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Thu, 13 Jan 2000 20:36:25 -0500

Basically, I agree with all of Jim's points.  In particular, I'll try
out the "lock is on the resource" approach in the next draft of GULP.
As Jim noted, in GULP the locking semantics *are* in fact all defined
in terms of affect on the states of resources, so the "lock is on a URL"
is at best a metaphor.  So I'll leave the semantics alone, and just
change the metaphor.

I'll also modify the way I refer to a lock in the semantics so that it
always is in the form of a tuple (e.g. [x, y, z]) so it is clearer when
a "lock" appears in the rules.

Finally, I believe it is sufficient to say that "lock discovery only
displays the locks on WebDAV resources", so that the locks on non-WebDAV
collections above the WebDAV are logically there, but you just can't inspect
them with PROPFIND.  (Jim et. al, does this work for you? Or maybe
you can't really say, until you see it written up.)

Cheers,
Geoff

   From: Jim Whitehead <[email-masked]>

Good point.  I'll add such a statement in the next rev.

     - lock type
     - lock scope
     - lock depth
     - lock timeout time
     - lock token
     - lock owner
     - lock URL (implicit)

   - Jim

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Fri, 14 Jan 2000 01:11:54 -0500

Here is a second version of the GULP.  I've updated the descriptive
text based on the feedback from Jason, Jim, and Eric (not that I've
successfully addressed their issues, but it was based on it :-).
Jason: I'm now using "target" instead of "name" ... let me know if
you think that works better.

The only semantic change has been the deletion of Depth:N behavior,
for N other than 0 and infinity (this brings it more in line with 2518).

I need some more examples, and I still need to address the use cases
raised by Eric and Jason ...  I believe they are handled properly by
the proposal, but I probably should get some sleep first before
working them through (:-).

Cheers,
Geoff

GULP: Part I

- A URL is a string that can identify a resource.

- A collection is a resource that contains a set of named members.

- A lock is 7-tuple, consisting of a target, token, type, scope,
depth, timeout, and owner.

- Locking a resource means to add a lock to the state of that
resource.

- Unlocking a resource means to remove a lock from the state of that
resource.

- A lock will cause certain requests to fail with a 423 (Locked)
status code, where that request would have succeeded if the lock had
not been present.

- A resource can be locked by multiple locks concurrently.

- One or more resources can be locked with a LOCK request.

- Locking a collection can lock one or more members of that
collection.

- Adding a resource to a locked collectin can lock that resource.

- One or more resources can be unlocked with an UNLOCK request.

- Unlocking a collection can unlock one or more members of that
collection.

- Removing a resource from a locked collection can unlock that resource.

- The depth of a lock can be a 0 or infinity.  If a collection has a
depth infinity lock, all members of that collection are also locked.

- If a member is added to a depth:infinity locked collection, that
member is locked by that depth:infinity lock.

- A lock protects which resource is identified by that lock.

- If a resource has an exclusive lock, that resource cannot be locked
with another lock with the same type and target but a different token.

- If a resource has a write lock with target ".", the body and
properties of that resource are protected from unauthorized
modification.

GULP: Part II

- A URL is a string that can identify a resource.

A server initially defines what resource (if any) is identified by a
URL.  Most URL's do not identify a resource, but a client can cause
a URL to identify a resource, and later change which resource is
identified by that URL.

Examples of methods that can cause a URL to identify a resource (or
change the resource identified by a URL) are PUT, MKRESOURCE, MKCOL,
BIND, MOVE, and COPY.  Examples of methods that can cause a URL to no
longer identify a resource are DELETE and MOVE.

- A lock is 7-tuple, consisting of a target, token, type, scope, depth,
timeout, and owner.

The "target" is an extension to locks as defined in rfc2518.  This new
field is defined to distinguish the implicit locks on the state of a
collection implied by the locking semantics of rfc2518, from the
explicit locks that are defined by rfc2518.  The explicit locks in
rfc2518 correspond to locks with target "." in this proposal.

Since all locks with the same token will share the same type, scope,
depth, timeout, and owner, a lock will be represented in this proposal
as a string of the form "[target, token]".

For example, ["x/.", "K"] defines a lock with target "x/." and token "K".

- A collection is a resource that contains a set of named members.

A collection contains a set of bindings, where a binding is a mapping
from a URL segment to a resource.  If a URL identifies a collection,
that URL extended by the URL segment will identify the bound resource.

For example, If "/path" identifies a collection C, and C contains a
binding that binds the segment "x" to resource R, then the URL
"/path/x" identifies resource R.

- Locking a resource means to add a lock to the state of that
resource.

The lock is added to the DAV:lockdiscovery property of the resource.

- Unlocking a resource means to remove a lock from the state of that
resource.

The lock is deleted from the DAV:lockdiscovery property of the
resource.

- A lock will cause certain requests to fail with a 423 (Locked)
status code, where that request would have succeeded if the lock had
not been present.

Whether a particular request will fail can depends on the
target, token, type, scope, and owner of the lock.

- A resource can be locked by multiple locks concurrently.

A lock can be locked by multiple locks with different values or
multiple identical locks.  Some lock combinations will be disallowed
based on information such as the the scope of the lock.

- One or more resources can be locked with a LOCK request.

When a LOCK request succeeds, a lock is added to the resource
identified by shortest sequence of initial segments of the request URL
that identifies a WebDAV resource.

The lock target is the relative URL formed by using standard URL
transformations to remove all segments of the request-URL named "." or
"..", then removing the prefix that identifies the locked resource,
and then appending a segment named ".".

For example, if "LOCK /seg1/seg2/seg3/.../segN" succeeds, and if
/seg1 does not identify a WebDAV resource but /seg1/seg2 does,
then a lock with target "seg3/.../segN/." is added to the resource
identified by "/seg1/seg2".

The type and scope, and owner of the lock is specified in the LOCK
request body.  The depth and timeout of the lock is specified in the
LOCK request headers.  The token of the lock is a unique string
allocated for that LOCK request by the server.

The principal that issued the LOCK request is called the "owner" of
the lock.

- Locking a collection can lock one or more members of that collection.

If a collection C has a binding from "segX" to resource R, and a
request adds a ["segX/pathZ", "K"] lock to C, then the request adds a
["pathZ", "K"] lock to R.

- Adding a resource to a locked collectin can lock that resource.

If a collection C has a ["segX/pathZ", "K"] lock, and a request adds a
binding in C from "segX" to resource R, then the request adds a
["pathZ", "K"] lock to R. If the attempt to add this lock to R fails,
the request MUST fail.

- One or more resources can be unlocked with an UNLOCK request.

When a request of the form "UNLOCK /pathX; Lock-Token K" succeeds,
then all locks with token "K" are removed.

- Unlocking a collection can unlock one or more members of that
collection.

If a collection C has a binding from "segX" to resource R, and a
request removes a ["segX/pathZ", "K"] lock from C, then the request
removes a ["pathZ", "K"] lock from R.

- Removing a resource from a locked collection can unlock that resource.

If a collection has a ["segX/pathZ", "K"] lock, and a request removes
a binding in C from "segX" to resource R, then a ["pathZ", "K"] lock
is removed from R.

- The depth of a lock can be a 0 or infinity.  If a collection has a
depth infinity lock, all members of that collection are also locked.

If a collection C has a binding to resource R, and a request adds a
Depth:infinity [".", "K"] lock to C, and this is the first [".", "K"]
lock on C, then the request adds a [".", "K"] lock to R.  Conversely,
if a collection C has a binding to resource R, and a request removes
the last Depth:infinity [".", "K"] lock from C, then the request
removes a [".", "K"] lock from R.

Note that multiple Depth:infinity locks with target "." and with the
same token can be placed on the same resource due to multiple bindings
to that resource in a Depth:infinity locked collection.  Only the
first such lock on a particular collection adds locks to the members
of that collection to avoid generating an infinite number of locks for
cyclic bindings.

- If a member is added to a depth:infinity locked collection, that
member is locked by that depth:infinity lock.

If a collection C has a Depth:infinity [".", "K"] lock, and a request
adds a binding in C to resource R, then the request adds a [".","K"]
lock to R. If the attempt to add this lock to R fails, the request
MUST fail.  Conversely, if a collection has a Depth:infinity [".",
"K"] lock, and a request removes a binding in C to resource R, then a
[".", "K"] lock removed from R.

- A lock protects which resource is identified by that lock.

More precisely, if a collection has a ["X/....", "K"] lock, a request
cannot delete the member named X from that collection unless the
principal of the request owns all locks with target "X/..." and the
tokens of all those locks are specified in an IF header.

- If a resource has an exclusive lock, that resource cannot be locked
with another locks with the same type and target but a different
token.

If a request attempts to add a type T ["pathZ", "K"] lock to resource
R, and R already has an exclusive lock with target "pathZ" and type T
but with a different token, the request MUST fail. Similarly, if a
request attempts to add an exclusive type T ["pathZ", "K"] lock to
resource R, and R already has a lock with target "pathZ" and type T
but with a different token, the request MUST fail.

- If a resource has a write lock with target ".", the body and
properties of that resource are protected from unauthorized
modification.

If a resource has a write lock with target ".", a request cannot
modify the body or dead properties of that resource unless the
principal of the request owns a write lock with target "." on that
resource and the token of that write lock is specified in an IF
header.

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Fri, 14 Jan 2000 08:52:21 -0500

From: "Eric Sedlar" <[email-masked]>

   is bound to, if any.

Yes.

   If the lock is exclusive, you can't lock any other
   name applied to that resource.  For example, if I have /a/foo.html and
   /b/foo.html both identifying the same resource, if I exclusive lock
   /a/foo.html, I can't protect the name "/b/foo.html" since I can't lock it.

You cannot apply an exclusive lock of the same type to /b/foo.html,
but if you just wanted to protect the name /b/foo.html, you could
request a lock of a different type on /b/foo.html (exclusivity is
lock-type specific).

Alternatively, if your server only supports one kind of lock type, you
could lock /b/foo.html/dummy-namespace-lock, which would have a similar effect
(and does not conflict with the exclusive lock already on /b/foo.html.

GULP does not distinguish between "locking the resource" and "locking the
name", although it does distinguish "a lock whose target is X/." and 
"a lock whose target is ."

If you wanted to introduce a "namespace lock", you could do so with the
standard lock extension mechanism (i.e. allow both "write" and "namespace"
locks), but that is different from saying there are two different kinds
of locks in the underlying locking model.

   > - If an exclusive lock identifies a resource, no other lock of that type
   can

Note that I have modified this statement to read:

This ties the semantics to the lock state of a single resource, rather
than using the vaguer concept of "the resource identified by a lock".

   correct?

They can add a lock with a different type from the exclusive lock,
or if there are no other lock types available, they can do the "dummy lock"
approach of locking "/b/foo.html/dummy-namespace-lock".

   The problem is that application A will not actually update the
   resource that app B is working with--it will just create a new revision.
   (Although this may affect the revision selected by app B).  Is this an issue
   your versioned locks deal with?

Versioning is (of course :-) somewhat trickier.  A lock in the presence of
versioning isn't so much concerned with locking the state of a resource
(the majority of the visible resources will be checked-in revisions, and
couldn't be modified even if you wanted to), but rather is concerned with
locking the target selection (so that you don't end up effectively getting
a namespace or state change because new revisions are selected).  This
issue (as you suggest) is addressed with the "revision selection freezing"
I've proposed for the versioning protocol.

Cheers,
Geoff

---

From: "Eric Sedlar" <[email-masked]>
Date: Fri, 14 Jan 2000 10:37:44 -0800

Why are you still allowing the "lock-null" approach (now renamed as the
dummy namespace lock)?  I thought one of the goals of GULP was to get rid of
that horrible concept.

--Eric

----- Original Message -----
From: Geoffrey M. Clemm <[email-masked]>
To: <[email-masked]>
Sent: Friday, January 14, 2000 5:52 AM
Subject: Re: a Grand Unified Locking Proposal (GULP, or perhaps, GULP! :-)

>    > - If an exclusive lock identifies a resource, no other lock of that
type

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Sat, 15 Jan 2000 01:27:15 -0500

Actually, it is the "lock null resource" concept that I strenuously
object to, not the concept that a lock can be on a target that does
not yet exist.

I believe being able to create a lock on a target that does not yet
exist is no worse/harder than namespace protection, so I would include
it in any proposal that includes namespace protection.

Also, the "grand unified" aspect of GULP was intended to allow us to
model everything that folks have been asking for, and then with that
in hand, we can decide which parts to defer (possibly indefinitely).

Cheers,
Geoff