webdav: first cut of a memLS implementation.
Change-Id: If5745dcc1d66fdaa083d4085440b1535aa75e0da
Reviewed-on: https://go-review.googlesource.com/2430
Reviewed-by: Dave Cheney <dave@cheney.net>
diff --git a/webdav/lock.go b/webdav/lock.go
index 6538ded..215d6dd 100644
--- a/webdav/lock.go
+++ b/webdav/lock.go
@@ -6,14 +6,22 @@
import (
"errors"
- "io"
+ "path"
+ "strconv"
+ "strings"
+ "sync"
"time"
)
var (
+ // ErrConfirmationFailed is returned by a LockSystem's Confirm method.
ErrConfirmationFailed = errors.New("webdav: confirmation failed")
- ErrForbidden = errors.New("webdav: forbidden")
- ErrNoSuchLock = errors.New("webdav: no such lock")
+ // ErrForbidden is returned by a LockSystem's Unlock method.
+ ErrForbidden = errors.New("webdav: forbidden")
+ // ErrLocked is returned by a LockSystem's Create, Refresh and Unlock methods.
+ ErrLocked = errors.New("webdav: locked")
+ // ErrNoSuchLock is returned by a LockSystem's Refresh and Unlock methods.
+ ErrNoSuchLock = errors.New("webdav: no such lock")
)
// Condition can match a WebDAV resource, based on a token or ETag.
@@ -24,21 +32,263 @@
ETag string
}
+// Releaser releases previously confirmed lock claims.
+//
+// Calling Release does not unlock the lock, in the WebDAV UNLOCK sense, but
+// once LockSystem.Confirm has confirmed that a lock claim is valid, that lock
+// cannot be Confirmed again until it has been Released.
+type Releaser interface {
+ Release()
+}
+
+// LockSystem manages access to a collection of named resources. The elements
+// in a lock name are separated by slash ('/', U+002F) characters, regardless
+// of host operating system convention.
type LockSystem interface {
- // TODO: comment that the conditions should be ANDed together.
- Confirm(path string, conditions ...Condition) (c io.Closer, err error)
- // TODO: comment that token should be an absolute URI as defined by RFC 3986,
- // Section 4.3. In particular, it should not contain whitespace.
- Create(path string, now time.Time, ld LockDetails) (token string, c io.Closer, err error)
- Refresh(token string, now time.Time, duration time.Duration) (ld LockDetails, c io.Closer, err error)
- Unlock(token string) error
+ // Confirm confirms that the caller can claim all of the locks specified by
+ // the given conditions, and that holding the union of all of those locks
+ // gives exclusive access to the named resource.
+ //
+ // Exactly one of r and err will be non-nil. If r is non-nil, all of the
+ // requested locks are held until r.Release is called.
+ //
+ // If Confirm returns ErrConfirmationFailed then the Handler will continue
+ // to try any other set of locks presented (a WebDAV HTTP request can
+ // present more than one set of locks). If it returns any other non-nil
+ // error, the Handler will write a "500 Internal Server Error" HTTP status.
+ Confirm(now time.Time, name string, conditions ...Condition) (r Releaser, err error)
+
+ // Create creates a lock with the given depth, duration, owner and root
+ // (name). The depth will either be negative (meaning infinite) or zero.
+ //
+ // If Create returns ErrLocked then the Handler will write a "423 Locked"
+ // HTTP status. If it returns any other non-nil error, the Handler will
+ // write a "500 Internal Server Error" HTTP status.
+ //
+ // See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.10.6 for
+ // when to use each error.
+ //
+ // The token returned identifies the created lock. It should be an absolute
+ // URI as defined by RFC 3986, Section 4.3. In particular, it should not
+ // contain whitespace.
+ Create(now time.Time, details LockDetails) (token string, err error)
+
+ // Refresh refreshes the lock with the given token.
+ //
+ // If Refresh returns ErrLocked then the Handler will write a "423 Locked"
+ // HTTP Status. If Refresh returns ErrNoSuchLock then the Handler will write
+ // a "412 Precondition Failed" HTTP Status. If it returns any other non-nil
+ // error, the Handler will write a "500 Internal Server Error" HTTP status.
+ //
+ // See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.10.6 for
+ // when to use each error.
+ Refresh(now time.Time, token string, duration time.Duration) (LockDetails, error)
+
+ // Unlock unlocks the lock with the given token.
+ //
+ // If Unlock returns ErrForbidden then the Handler will write a "403
+ // Forbidden" HTTP Status. If Unlock returns ErrLocked then the Handler
+ // will write a "423 Locked" HTTP status. If Unlock returns ErrNoSuchLock
+ // then the Handler will write a "409 Conflict" HTTP Status. If it returns
+ // any other non-nil error, the Handler will write a "500 Internal Server
+ // Error" HTTP status.
+ //
+ // See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.11.1 for
+ // when to use each error.
+ Unlock(now time.Time, token string) error
}
+// LockDetails are a lock's metadata.
type LockDetails struct {
- Depth int // Negative means infinite depth.
- Duration time.Duration // Negative means unlimited duration.
- OwnerXML string // Verbatim XML.
- Path string
+ // Root is the root resource name being locked. For a zero-depth lock, the
+ // root is the only resource being locked.
+ Root string
+ // Depth is the lock depth. A negative depth means infinite.
+ //
+ // TODO: should depth be restricted to just "0 or infinite" (i.e. change
+ // this field to "Recursive bool") or just "0 or 1 or infinite"? Is
+ // validating that the responsibility of the Handler or the LockSystem
+ // implementations?
+ Depth int
+ // Duration is the lock timeout. A negative duration means infinite.
+ Duration time.Duration
+ // OwnerXML is the verbatim <owner> XML given in a LOCK HTTP request.
+ //
+ // TODO: does the "verbatim" nature play well with XML namespaces?
+ // Does the OwnerXML field need to have more structure? See
+ // https://codereview.appspot.com/175140043/#msg2
+ OwnerXML string
}
-// TODO: a MemLS implementation.
+// NewMemLS returns a new in-memory LockSystem.
+func NewMemLS() LockSystem {
+ return &memLS{
+ byName: make(map[string]*memLSNode),
+ byToken: make(map[string]*memLSNode),
+ gen: uint64(time.Now().Unix()),
+ }
+}
+
+type memLS struct {
+ mu sync.Mutex
+ byName map[string]*memLSNode
+ byToken map[string]*memLSNode
+ gen uint64
+}
+
+func (m *memLS) nextToken() string {
+ m.gen++
+ return strconv.FormatUint(m.gen, 10)
+}
+
+func (m *memLS) collectExpiredNodes(now time.Time) {
+ // TODO: implement.
+}
+
+func (m *memLS) Confirm(now time.Time, name string, conditions ...Condition) (Releaser, error) {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ m.collectExpiredNodes(now)
+ name = path.Clean("/" + name)
+
+ // TODO: touch n.held.
+ panic("TODO")
+}
+
+func (m *memLS) Create(now time.Time, details LockDetails) (string, error) {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ m.collectExpiredNodes(now)
+ name := path.Clean("/" + details.Root)
+
+ if !m.canCreate(name, details.Depth) {
+ return "", ErrLocked
+ }
+ n := m.create(name)
+ n.token = m.nextToken()
+ m.byToken[n.token] = n
+ n.details = details
+ // TODO: set n.expiry.
+ return n.token, nil
+}
+
+func (m *memLS) Refresh(now time.Time, token string, duration time.Duration) (LockDetails, error) {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ m.collectExpiredNodes(now)
+
+ n := m.byToken[token]
+ if n == nil {
+ return LockDetails{}, ErrNoSuchLock
+ }
+ if n.held {
+ return LockDetails{}, ErrLocked
+ }
+ n.details.Duration = duration
+ // TODO: update n.expiry.
+ return n.details, nil
+}
+
+func (m *memLS) Unlock(now time.Time, token string) error {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ m.collectExpiredNodes(now)
+
+ n := m.byToken[token]
+ if n == nil {
+ return ErrNoSuchLock
+ }
+ if n.held {
+ return ErrLocked
+ }
+ m.remove(n)
+ return nil
+}
+
+func (m *memLS) canCreate(name string, depth int) bool {
+ return walkToRoot(name, func(name0 string, first bool) bool {
+ n := m.byName[name0]
+ if n == nil {
+ return true
+ }
+ if first {
+ if n.token != "" {
+ // The target node is already locked.
+ return false
+ }
+ if depth < 0 {
+ // The requested lock depth is infinite, and the fact that n exists
+ // (n != nil) means that a descendent of the target node is locked.
+ return false
+ }
+ } else if n.token != "" && n.details.Depth < 0 {
+ // An ancestor of the target node is locked with infinite depth.
+ return false
+ }
+ return true
+ })
+}
+
+func (m *memLS) create(name string) (ret *memLSNode) {
+ walkToRoot(name, func(name0 string, first bool) bool {
+ n := m.byName[name0]
+ if n == nil {
+ n = &memLSNode{
+ details: LockDetails{
+ Root: name0,
+ },
+ }
+ m.byName[name0] = n
+ }
+ n.refCount++
+ if first {
+ ret = n
+ }
+ return true
+ })
+ return ret
+}
+
+func (m *memLS) remove(n *memLSNode) {
+ delete(m.byToken, n.token)
+ n.token = ""
+ walkToRoot(n.details.Root, func(name0 string, first bool) bool {
+ x := m.byName[name0]
+ x.refCount--
+ if x.refCount == 0 {
+ delete(m.byName, name0)
+ }
+ return true
+ })
+}
+
+func walkToRoot(name string, f func(name0 string, first bool) bool) bool {
+ for first := true; ; first = false {
+ if !f(name, first) {
+ return false
+ }
+ if name == "/" {
+ break
+ }
+ name = name[:strings.LastIndex(name, "/")]
+ if name == "" {
+ name = "/"
+ }
+ }
+ return true
+}
+
+type memLSNode struct {
+ // details are the lock metadata. Even if this node's name is not explicitly locked,
+ // details.Root will still equal the node's name.
+ details LockDetails
+ // token is the unique identifier for this node's lock. An empty token means that
+ // this node is not explicitly locked.
+ token string
+ // refCount is the number of self-or-descendent nodes that are explicitly locked.
+ refCount int
+ // expiry is when this node's lock expires.
+ expiry time.Time
+ // held is whether this node's lock is actively held by a Confirm call.
+ held bool
+}
diff --git a/webdav/lock_test.go b/webdav/lock_test.go
new file mode 100644
index 0000000..090314b
--- /dev/null
+++ b/webdav/lock_test.go
@@ -0,0 +1,253 @@
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package webdav
+
+import (
+ "fmt"
+ "math/rand"
+ "path"
+ "reflect"
+ "sort"
+ "strings"
+ "testing"
+ "time"
+)
+
+func TestWalkToRoot(t *testing.T) {
+ testCases := []struct {
+ name string
+ want []string
+ }{{
+ "/a/b/c/d",
+ []string{
+ "/a/b/c/d",
+ "/a/b/c",
+ "/a/b",
+ "/a",
+ "/",
+ },
+ }, {
+ "/a",
+ []string{
+ "/a",
+ "/",
+ },
+ }, {
+ "/",
+ []string{
+ "/",
+ },
+ }}
+
+ for _, tc := range testCases {
+ var got []string
+ if !walkToRoot(tc.name, func(name0 string, first bool) bool {
+ if first != (len(got) == 0) {
+ t.Errorf("name=%q: first=%t but len(got)==%d", tc.name, first, len(got))
+ return false
+ }
+ got = append(got, name0)
+ return true
+ }) {
+ continue
+ }
+ if !reflect.DeepEqual(got, tc.want) {
+ t.Errorf("name=%q:\ngot %q\nwant %q", tc.name, got, tc.want)
+ }
+ }
+}
+
+// lockTestNames are the names of a set of mutually compatible locks. For each
+// name fragment:
+// - _ means no explicit lock.
+// - i means a infinite-depth lock,
+// - z means a zero-depth lock,
+var lockTestNames = []string{
+ "/_/_/_/_/z",
+ "/_/_/i",
+ "/_/z",
+ "/_/z/i",
+ "/_/z/z",
+ "/_/z/_/i",
+ "/_/z/_/z",
+ "/i",
+ "/z",
+ "/z/_/i",
+ "/z/_/z",
+}
+
+func lockTestDepth(name string) int {
+ switch name[len(name)-1] {
+ case 'i':
+ return -1
+ case 'z':
+ return 0
+ }
+ panic(fmt.Sprintf("lock name %q did not end with 'i' or 'z'", name))
+}
+
+func TestMemLSCanCreate(t *testing.T) {
+ now := time.Unix(0, 0)
+ m := NewMemLS().(*memLS)
+
+ for _, name := range lockTestNames {
+ _, err := m.Create(now, LockDetails{
+ Depth: lockTestDepth(name),
+ Duration: -1,
+ Root: name,
+ })
+ if err != nil {
+ t.Fatalf("creating lock for %q: %v", name, err)
+ }
+ }
+
+ wantCanCreate := func(name string, depth int) bool {
+ for _, n := range lockTestNames {
+ switch {
+ case n == name:
+ // An existing lock has the same name as the proposed lock.
+ return false
+ case strings.HasPrefix(n, name):
+ // An existing lock would be a child of the proposed lock,
+ // which conflicts if the proposed lock has infinite depth.
+ if depth < 0 {
+ return false
+ }
+ case strings.HasPrefix(name, n):
+ // An existing lock would be an ancestor of the proposed lock,
+ // which conflicts if the ancestor has infinite depth.
+ if n[len(n)-1] == 'i' {
+ return false
+ }
+ }
+ }
+ return true
+ }
+
+ var check func(int, string)
+ check = func(recursion int, name string) {
+ for _, depth := range []int{-1, 0} {
+ got := m.canCreate(name, depth)
+ want := wantCanCreate(name, depth)
+ if got != want {
+ t.Errorf("canCreate name=%q depth=%d: got %t, want %t", name, depth, got, want)
+ }
+ }
+ if recursion == 6 {
+ return
+ }
+ if name != "/" {
+ name += "/"
+ }
+ for _, c := range "_iz" {
+ check(recursion+1, name+string(c))
+ }
+ }
+ check(0, "/")
+}
+
+func TestMemLSCreateUnlock(t *testing.T) {
+ now := time.Unix(0, 0)
+ m := NewMemLS().(*memLS)
+ rng := rand.New(rand.NewSource(0))
+ tokens := map[string]string{}
+ for i := 0; i < 1000; i++ {
+ name := lockTestNames[rng.Intn(len(lockTestNames))]
+ if token := tokens[name]; token != "" {
+ if err := m.Unlock(now, token); err != nil {
+ t.Fatalf("iteration #%d: unlock %q: %v", i, name, err)
+ }
+ tokens[name] = ""
+ } else {
+ token, err := m.Create(now, LockDetails{
+ Depth: lockTestDepth(name),
+ Duration: -1,
+ Root: name,
+ })
+ if err != nil {
+ t.Fatalf("iteration #%d: create %q: %v", i, name, err)
+ }
+ tokens[name] = token
+ }
+ if err := m.consistent(); err != nil {
+ t.Fatalf("iteration #%d: inconsistent state: %v", i, err)
+ }
+ }
+}
+
+func (m *memLS) consistent() error {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+
+ // If m.byName is non-empty, then it must contain an entry for the root "/",
+ // and its refCount should equal the number of locked nodes.
+ if len(m.byName) > 0 {
+ n := m.byName["/"]
+ if n == nil {
+ return fmt.Errorf(`non-empty m.byName does not contain the root "/"`)
+ }
+ if n.refCount != len(m.byToken) {
+ return fmt.Errorf("root node refCount=%d, differs from len(m.byToken)=%d", n.refCount, len(m.byToken))
+ }
+ }
+
+ for name, n := range m.byName {
+ // The map keys should be consistent with the node's copy of the key.
+ if n.details.Root != name {
+ return fmt.Errorf("node name %q != byName map key %q", n.details.Root, name)
+ }
+
+ // A name must be clean, and start with a "/".
+ if len(name) == 0 || name[0] != '/' {
+ return fmt.Errorf(`node name %q does not start with "/"`, name)
+ }
+ if name != path.Clean(name) {
+ return fmt.Errorf(`node name %q is not clean`, name)
+ }
+
+ // A node's refCount should be positive.
+ if n.refCount <= 0 {
+ return fmt.Errorf("non-positive refCount for node at name %q", name)
+ }
+
+ // A node's refCount should be the number of self-or-descendents that
+ // are locked (i.e. have a non-empty token).
+ var list []string
+ for name0, n0 := range m.byName {
+ // All of lockTestNames' name fragments are one byte long: '_', 'i' or 'z',
+ // so strings.HasPrefix is equivalent to self-or-descendent name match.
+ // We don't have to worry about "/foo/bar" being a false positive match
+ // for "/foo/b".
+ if strings.HasPrefix(name0, name) && n0.token != "" {
+ list = append(list, name0)
+ }
+ }
+ if n.refCount != len(list) {
+ sort.Strings(list)
+ return fmt.Errorf("node at name %q has refCount %d but locked self-or-descendents are %q (len=%d)",
+ name, n.refCount, list, len(list))
+ }
+
+ // A node n is in m.byToken if it has a non-empty token.
+ if n.token != "" {
+ if _, ok := m.byToken[n.token]; !ok {
+ return fmt.Errorf("node at name %q has token %q but not in m.byToken", name, n.token)
+ }
+ }
+ }
+
+ for token, n := range m.byToken {
+ // The map keys should be consistent with the node's copy of the key.
+ if n.token != token {
+ return fmt.Errorf("node token %q != byToken map key %q", n.token, token)
+ }
+
+ // Every node in m.byToken is in m.byName.
+ if _, ok := m.byName[n.details.Root]; !ok {
+ return fmt.Errorf("node at name %q in m.byToken but not in m.byName", n.details.Root)
+ }
+ }
+ return nil
+}
diff --git a/webdav/webdav.go b/webdav/webdav.go
index 192dc7e..1a31bd0 100644
--- a/webdav/webdav.go
+++ b/webdav/webdav.go
@@ -67,16 +67,14 @@
}
}
-type nopCloser struct{}
+type nopReleaser struct{}
-func (nopCloser) Close() error {
- return nil
-}
+func (nopReleaser) Release() {}
-func (h *Handler) confirmLocks(r *http.Request) (closer io.Closer, status int, err error) {
+func (h *Handler) confirmLocks(r *http.Request) (releaser Releaser, status int, err error) {
hdr := r.Header.Get("If")
if hdr == "" {
- return nopCloser{}, 0, nil
+ return nopReleaser{}, 0, nil
}
ih, ok := parseIfHeader(hdr)
if !ok {
@@ -88,16 +86,16 @@
if path == "" {
path = r.URL.Path
}
- closer, err = h.LockSystem.Confirm(path, l.conditions...)
+ releaser, err = h.LockSystem.Confirm(time.Now(), path, l.conditions...)
if err == ErrConfirmationFailed {
continue
}
if err != nil {
return nil, http.StatusInternalServerError, err
}
- return closer, 0, nil
+ return releaser, 0, nil
}
- return nil, http.StatusPreconditionFailed, errLocked
+ return nil, http.StatusPreconditionFailed, ErrLocked
}
func (h *Handler) handleOptions(w http.ResponseWriter, r *http.Request) (status int, err error) {
@@ -134,11 +132,11 @@
}
func (h *Handler) handleDelete(w http.ResponseWriter, r *http.Request) (status int, err error) {
- closer, status, err := h.confirmLocks(r)
+ releaser, status, err := h.confirmLocks(r)
if err != nil {
return status, err
}
- defer closer.Close()
+ defer releaser.Release()
if err := h.FileSystem.RemoveAll(r.URL.Path); err != nil {
if os.IsNotExist(err) {
@@ -151,11 +149,11 @@
}
func (h *Handler) handlePut(w http.ResponseWriter, r *http.Request) (status int, err error) {
- closer, status, err := h.confirmLocks(r)
+ releaser, status, err := h.confirmLocks(r)
if err != nil {
return status, err
}
- defer closer.Close()
+ defer releaser.Release()
f, err := h.FileSystem.OpenFile(r.URL.Path, os.O_RDWR|os.O_CREATE|os.O_TRUNC, 0666)
if err != nil {
@@ -169,11 +167,11 @@
}
func (h *Handler) handleMkcol(w http.ResponseWriter, r *http.Request) (status int, err error) {
- closer, status, err := h.confirmLocks(r)
+ releaser, status, err := h.confirmLocks(r)
if err != nil {
return status, err
}
- defer closer.Close()
+ defer releaser.Release()
if r.ContentLength > 0 {
return http.StatusUnsupportedMediaType, nil
@@ -197,7 +195,7 @@
return status, err
}
- token, ld := "", LockDetails{}
+ token, ld, now := "", LockDetails{}, time.Now()
if li == (lockInfo{}) {
// An empty lockInfo means to refresh the lock.
ih, ok := parseIfHeader(r.Header.Get("If"))
@@ -210,38 +208,42 @@
if token == "" {
return http.StatusBadRequest, errInvalidLockToken
}
- var closer io.Closer
- ld, closer, err = h.LockSystem.Refresh(token, time.Now(), duration)
+ ld, err = h.LockSystem.Refresh(now, token, duration)
if err != nil {
if err == ErrNoSuchLock {
return http.StatusPreconditionFailed, err
}
return http.StatusInternalServerError, err
}
- defer closer.Close()
} else {
depth, err := parseDepth(r.Header.Get("Depth"))
if err != nil {
return http.StatusBadRequest, err
}
+ if depth > 0 {
+ // Section 9.10.3 says that "Values other than 0 or infinity must not be
+ // used with the Depth header on a LOCK method".
+ return http.StatusBadRequest, errInvalidDepth
+ }
ld = LockDetails{
Depth: depth,
Duration: duration,
OwnerXML: li.Owner.InnerXML,
- Path: r.URL.Path,
+ Root: r.URL.Path,
}
- var closer io.Closer
- token, closer, err = h.LockSystem.Create(r.URL.Path, time.Now(), ld)
+ token, err = h.LockSystem.Create(now, ld)
if err != nil {
+ if err == ErrLocked {
+ return StatusLocked, err
+ }
return http.StatusInternalServerError, err
}
defer func() {
if retErr != nil {
- h.LockSystem.Unlock(token)
+ h.LockSystem.Unlock(now, token)
}
}()
- defer closer.Close()
// Create the resource if it didn't previously exist.
if _, err := h.FileSystem.Stat(r.URL.Path); err != nil {
@@ -272,11 +274,13 @@
}
t = t[1 : len(t)-1]
- switch err = h.LockSystem.Unlock(t); err {
+ switch err = h.LockSystem.Unlock(time.Now(), t); err {
case nil:
return http.StatusNoContent, err
case ErrForbidden:
return http.StatusForbidden, err
+ case ErrLocked:
+ return StatusLocked, err
case ErrNoSuchLock:
return http.StatusConflict, err
default:
@@ -320,10 +324,10 @@
}
var (
+ errInvalidDepth = errors.New("webdav: invalid depth")
errInvalidIfHeader = errors.New("webdav: invalid If header")
errInvalidLockInfo = errors.New("webdav: invalid lock info")
errInvalidLockToken = errors.New("webdav: invalid lock token")
- errLocked = errors.New("webdav: locked")
errNoFileSystem = errors.New("webdav: no file system")
errNoLockSystem = errors.New("webdav: no lock system")
errUnsupportedLockInfo = errors.New("webdav: unsupported lock info")
diff --git a/webdav/xml.go b/webdav/xml.go
index 5939373..c48fc0f 100644
--- a/webdav/xml.go
+++ b/webdav/xml.go
@@ -79,7 +79,7 @@
" <D:locktoken><D:href>%s</D:href></D:locktoken>\n"+
" <D:lockroot><D:href>%s</D:href></D:lockroot>\n"+
"</D:activelock></D:lockdiscovery></D:prop>",
- depth, ld.OwnerXML, timeout, escape(token), escape(ld.Path),
+ depth, ld.OwnerXML, timeout, escape(token), escape(ld.Root),
)
}
