lock.go

Documentation: golang.org/x/net/webdav

     1  // Copyright 2014 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package webdav
     6  
     7  import (
     8  	"container/heap"
     9  	"errors"
    10  	"strconv"
    11  	"strings"
    12  	"sync"
    13  	"time"
    14  )
    15  
    16  var (
    17  	// ErrConfirmationFailed is returned by a LockSystem's Confirm method.
    18  	ErrConfirmationFailed = errors.New("webdav: confirmation failed")
    19  	// ErrForbidden is returned by a LockSystem's Unlock method.
    20  	ErrForbidden = errors.New("webdav: forbidden")
    21  	// ErrLocked is returned by a LockSystem's Create, Refresh and Unlock methods.
    22  	ErrLocked = errors.New("webdav: locked")
    23  	// ErrNoSuchLock is returned by a LockSystem's Refresh and Unlock methods.
    24  	ErrNoSuchLock = errors.New("webdav: no such lock")
    25  )
    26  
    27  // Condition can match a WebDAV resource, based on a token or ETag.
    28  // Exactly one of Token and ETag should be non-empty.
    29  type Condition struct {
    30  	Not   bool
    31  	Token string
    32  	ETag  string
    33  }
    34  
    35  // LockSystem manages access to a collection of named resources. The elements
    36  // in a lock name are separated by slash ('/', U+002F) characters, regardless
    37  // of host operating system convention.
    38  type LockSystem interface {
    39  	// Confirm confirms that the caller can claim all of the locks specified by
    40  	// the given conditions, and that holding the union of all of those locks
    41  	// gives exclusive access to all of the named resources. Up to two resources
    42  	// can be named. Empty names are ignored.
    43  	//
    44  	// Exactly one of release and err will be non-nil. If release is non-nil,
    45  	// all of the requested locks are held until release is called. Calling
    46  	// release does not unlock the lock, in the WebDAV UNLOCK sense, but once
    47  	// Confirm has confirmed that a lock claim is valid, that lock cannot be
    48  	// Confirmed again until it has been released.
    49  	//
    50  	// If Confirm returns ErrConfirmationFailed then the Handler will continue
    51  	// to try any other set of locks presented (a WebDAV HTTP request can
    52  	// present more than one set of locks). If it returns any other non-nil
    53  	// error, the Handler will write a "500 Internal Server Error" HTTP status.
    54  	Confirm(now time.Time, name0, name1 string, conditions ...Condition) (release func(), err error)
    55  
    56  	// Create creates a lock with the given depth, duration, owner and root
    57  	// (name). The depth will either be negative (meaning infinite) or zero.
    58  	//
    59  	// If Create returns ErrLocked then the Handler will write a "423 Locked"
    60  	// HTTP status. If it returns any other non-nil error, the Handler will
    61  	// write a "500 Internal Server Error" HTTP status.
    62  	//
    63  	// See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.10.6 for
    64  	// when to use each error.
    65  	//
    66  	// The token returned identifies the created lock. It should be an absolute
    67  	// URI as defined by RFC 3986, Section 4.3. In particular, it should not
    68  	// contain whitespace.
    69  	Create(now time.Time, details LockDetails) (token string, err error)
    70  
    71  	// Refresh refreshes the lock with the given token.
    72  	//
    73  	// If Refresh returns ErrLocked then the Handler will write a "423 Locked"
    74  	// HTTP Status. If Refresh returns ErrNoSuchLock then the Handler will write
    75  	// a "412 Precondition Failed" HTTP Status. If it returns any other non-nil
    76  	// error, the Handler will write a "500 Internal Server Error" HTTP status.
    77  	//
    78  	// See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.10.6 for
    79  	// when to use each error.
    80  	Refresh(now time.Time, token string, duration time.Duration) (LockDetails, error)
    81  
    82  	// Unlock unlocks the lock with the given token.
    83  	//
    84  	// If Unlock returns ErrForbidden then the Handler will write a "403
    85  	// Forbidden" HTTP Status. If Unlock returns ErrLocked then the Handler
    86  	// will write a "423 Locked" HTTP status. If Unlock returns ErrNoSuchLock
    87  	// then the Handler will write a "409 Conflict" HTTP Status. If it returns
    88  	// any other non-nil error, the Handler will write a "500 Internal Server
    89  	// Error" HTTP status.
    90  	//
    91  	// See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.11.1 for
    92  	// when to use each error.
    93  	Unlock(now time.Time, token string) error
    94  }
    95  
    96  // LockDetails are a lock's metadata.
    97  type LockDetails struct {
    98  	// Root is the root resource name being locked. For a zero-depth lock, the
    99  	// root is the only resource being locked.
   100  	Root string
   101  	// Duration is the lock timeout. A negative duration means infinite.
   102  	Duration time.Duration
   103  	// OwnerXML is the verbatim <owner> XML given in a LOCK HTTP request.
   104  	//
   105  	// TODO: does the "verbatim" nature play well with XML namespaces?
   106  	// Does the OwnerXML field need to have more structure? See
   107  	// https://codereview.appspot.com/175140043/#msg2
   108  	OwnerXML string
   109  	// ZeroDepth is whether the lock has zero depth. If it does not have zero
   110  	// depth, it has infinite depth.
   111  	ZeroDepth bool
   112  }
   113  
   114  // NewMemLS returns a new in-memory LockSystem.
   115  func NewMemLS() LockSystem {
   116  	return &memLS{
   117  		byName:  make(map[string]*memLSNode),
   118  		byToken: make(map[string]*memLSNode),
   119  		gen:     uint64(time.Now().Unix()),
   120  	}
   121  }
   122  
   123  type memLS struct {
   124  	mu      sync.Mutex
   125  	byName  map[string]*memLSNode
   126  	byToken map[string]*memLSNode
   127  	gen     uint64
   128  	// byExpiry only contains those nodes whose LockDetails have a finite
   129  	// Duration and are yet to expire.
   130  	byExpiry byExpiry
   131  }
   132  
   133  func (m *memLS) nextToken() string {
   134  	m.gen++
   135  	return strconv.FormatUint(m.gen, 10)
   136  }
   137  
   138  func (m *memLS) collectExpiredNodes(now time.Time) {
   139  	for len(m.byExpiry) > 0 {
   140  		if now.Before(m.byExpiry[0].expiry) {
   141  			break
   142  		}
   143  		m.remove(m.byExpiry[0])
   144  	}
   145  }
   146  
   147  func (m *memLS) Confirm(now time.Time, name0, name1 string, conditions ...Condition) (func(), error) {
   148  	m.mu.Lock()
   149  	defer m.mu.Unlock()
   150  	m.collectExpiredNodes(now)
   151  
   152  	var n0, n1 *memLSNode
   153  	if name0 != "" {
   154  		if n0 = m.lookup(slashClean(name0), conditions...); n0 == nil {
   155  			return nil, ErrConfirmationFailed
   156  		}
   157  	}
   158  	if name1 != "" {
   159  		if n1 = m.lookup(slashClean(name1), conditions...); n1 == nil {
   160  			return nil, ErrConfirmationFailed
   161  		}
   162  	}
   163  
   164  	// Don't hold the same node twice.
   165  	if n1 == n0 {
   166  		n1 = nil
   167  	}
   168  
   169  	if n0 != nil {
   170  		m.hold(n0)
   171  	}
   172  	if n1 != nil {
   173  		m.hold(n1)
   174  	}
   175  	return func() {
   176  		m.mu.Lock()
   177  		defer m.mu.Unlock()
   178  		if n1 != nil {
   179  			m.unhold(n1)
   180  		}
   181  		if n0 != nil {
   182  			m.unhold(n0)
   183  		}
   184  	}, nil
   185  }
   186  
   187  // lookup returns the node n that locks the named resource, provided that n
   188  // matches at least one of the given conditions and that lock isn't held by
   189  // another party. Otherwise, it returns nil.
   190  //
   191  // n may be a parent of the named resource, if n is an infinite depth lock.
   192  func (m *memLS) lookup(name string, conditions ...Condition) (n *memLSNode) {
   193  	// TODO: support Condition.Not and Condition.ETag.
   194  	for _, c := range conditions {
   195  		n = m.byToken[c.Token]
   196  		if n == nil || n.held {
   197  			continue
   198  		}
   199  		if name == n.details.Root {
   200  			return n
   201  		}
   202  		if n.details.ZeroDepth {
   203  			continue
   204  		}
   205  		if n.details.Root == "/" || strings.HasPrefix(name, n.details.Root+"/") {
   206  			return n
   207  		}
   208  	}
   209  	return nil
   210  }
   211  
   212  func (m *memLS) hold(n *memLSNode) {
   213  	if n.held {
   214  		panic("webdav: memLS inconsistent held state")
   215  	}
   216  	n.held = true
   217  	if n.details.Duration >= 0 && n.byExpiryIndex >= 0 {
   218  		heap.Remove(&m.byExpiry, n.byExpiryIndex)
   219  	}
   220  }
   221  
   222  func (m *memLS) unhold(n *memLSNode) {
   223  	if !n.held {
   224  		panic("webdav: memLS inconsistent held state")
   225  	}
   226  	n.held = false
   227  	if n.details.Duration >= 0 {
   228  		heap.Push(&m.byExpiry, n)
   229  	}
   230  }
   231  
   232  func (m *memLS) Create(now time.Time, details LockDetails) (string, error) {
   233  	m.mu.Lock()
   234  	defer m.mu.Unlock()
   235  	m.collectExpiredNodes(now)
   236  	details.Root = slashClean(details.Root)
   237  
   238  	if !m.canCreate(details.Root, details.ZeroDepth) {
   239  		return "", ErrLocked
   240  	}
   241  	n := m.create(details.Root)
   242  	n.token = m.nextToken()
   243  	m.byToken[n.token] = n
   244  	n.details = details
   245  	if n.details.Duration >= 0 {
   246  		n.expiry = now.Add(n.details.Duration)
   247  		heap.Push(&m.byExpiry, n)
   248  	}
   249  	return n.token, nil
   250  }
   251  
   252  func (m *memLS) Refresh(now time.Time, token string, duration time.Duration) (LockDetails, error) {
   253  	m.mu.Lock()
   254  	defer m.mu.Unlock()
   255  	m.collectExpiredNodes(now)
   256  
   257  	n := m.byToken[token]
   258  	if n == nil {
   259  		return LockDetails{}, ErrNoSuchLock
   260  	}
   261  	if n.held {
   262  		return LockDetails{}, ErrLocked
   263  	}
   264  	if n.byExpiryIndex >= 0 {
   265  		heap.Remove(&m.byExpiry, n.byExpiryIndex)
   266  	}
   267  	n.details.Duration = duration
   268  	if n.details.Duration >= 0 {
   269  		n.expiry = now.Add(n.details.Duration)
   270  		heap.Push(&m.byExpiry, n)
   271  	}
   272  	return n.details, nil
   273  }
   274  
   275  func (m *memLS) Unlock(now time.Time, token string) error {
   276  	m.mu.Lock()
   277  	defer m.mu.Unlock()
   278  	m.collectExpiredNodes(now)
   279  
   280  	n := m.byToken[token]
   281  	if n == nil {
   282  		return ErrNoSuchLock
   283  	}
   284  	if n.held {
   285  		return ErrLocked
   286  	}
   287  	m.remove(n)
   288  	return nil
   289  }
   290  
   291  func (m *memLS) canCreate(name string, zeroDepth bool) bool {
   292  	return walkToRoot(name, func(name0 string, first bool) bool {
   293  		n := m.byName[name0]
   294  		if n == nil {
   295  			return true
   296  		}
   297  		if first {
   298  			if n.token != "" {
   299  				// The target node is already locked.
   300  				return false
   301  			}
   302  			if !zeroDepth {
   303  				// The requested lock depth is infinite, and the fact that n exists
   304  				// (n != nil) means that a descendent of the target node is locked.
   305  				return false
   306  			}
   307  		} else if n.token != "" && !n.details.ZeroDepth {
   308  			// An ancestor of the target node is locked with infinite depth.
   309  			return false
   310  		}
   311  		return true
   312  	})
   313  }
   314  
   315  func (m *memLS) create(name string) (ret *memLSNode) {
   316  	walkToRoot(name, func(name0 string, first bool) bool {
   317  		n := m.byName[name0]
   318  		if n == nil {
   319  			n = &memLSNode{
   320  				details: LockDetails{
   321  					Root: name0,
   322  				},
   323  				byExpiryIndex: -1,
   324  			}
   325  			m.byName[name0] = n
   326  		}
   327  		n.refCount++
   328  		if first {
   329  			ret = n
   330  		}
   331  		return true
   332  	})
   333  	return ret
   334  }
   335  
   336  func (m *memLS) remove(n *memLSNode) {
   337  	delete(m.byToken, n.token)
   338  	n.token = ""
   339  	walkToRoot(n.details.Root, func(name0 string, first bool) bool {
   340  		x := m.byName[name0]
   341  		x.refCount--
   342  		if x.refCount == 0 {
   343  			delete(m.byName, name0)
   344  		}
   345  		return true
   346  	})
   347  	if n.byExpiryIndex >= 0 {
   348  		heap.Remove(&m.byExpiry, n.byExpiryIndex)
   349  	}
   350  }
   351  
   352  func walkToRoot(name string, f func(name0 string, first bool) bool) bool {
   353  	for first := true; ; first = false {
   354  		if !f(name, first) {
   355  			return false
   356  		}
   357  		if name == "/" {
   358  			break
   359  		}
   360  		name = name[:strings.LastIndex(name, "/")]
   361  		if name == "" {
   362  			name = "/"
   363  		}
   364  	}
   365  	return true
   366  }
   367  
   368  type memLSNode struct {
   369  	// details are the lock metadata. Even if this node's name is not explicitly locked,
   370  	// details.Root will still equal the node's name.
   371  	details LockDetails
   372  	// token is the unique identifier for this node's lock. An empty token means that
   373  	// this node is not explicitly locked.
   374  	token string
   375  	// refCount is the number of self-or-descendent nodes that are explicitly locked.
   376  	refCount int
   377  	// expiry is when this node's lock expires.
   378  	expiry time.Time
   379  	// byExpiryIndex is the index of this node in memLS.byExpiry. It is -1
   380  	// if this node does not expire, or has expired.
   381  	byExpiryIndex int
   382  	// held is whether this node's lock is actively held by a Confirm call.
   383  	held bool
   384  }
   385  
   386  type byExpiry []*memLSNode
   387  
   388  func (b *byExpiry) Len() int {
   389  	return len(*b)
   390  }
   391  
   392  func (b *byExpiry) Less(i, j int) bool {
   393  	return (*b)[i].expiry.Before((*b)[j].expiry)
   394  }
   395  
   396  func (b *byExpiry) Swap(i, j int) {
   397  	(*b)[i], (*b)[j] = (*b)[j], (*b)[i]
   398  	(*b)[i].byExpiryIndex = i
   399  	(*b)[j].byExpiryIndex = j
   400  }
   401  
   402  func (b *byExpiry) Push(x interface{}) {
   403  	n := x.(*memLSNode)
   404  	n.byExpiryIndex = len(*b)
   405  	*b = append(*b, n)
   406  }
   407  
   408  func (b *byExpiry) Pop() interface{} {
   409  	i := len(*b) - 1
   410  	n := (*b)[i]
   411  	(*b)[i] = nil
   412  	n.byExpiryIndex = -1
   413  	*b = (*b)[:i]
   414  	return n
   415  }
   416  
   417  const infiniteTimeout = -1
   418  
   419  // parseTimeout parses the Timeout HTTP header, as per section 10.7. If s is
   420  // empty, an infiniteTimeout is returned.
   421  func parseTimeout(s string) (time.Duration, error) {
   422  	if s == "" {
   423  		return infiniteTimeout, nil
   424  	}
   425  	if i := strings.IndexByte(s, ','); i >= 0 {
   426  		s = s[:i]
   427  	}
   428  	s = strings.TrimSpace(s)
   429  	if s == "Infinite" {
   430  		return infiniteTimeout, nil
   431  	}
   432  	const pre = "Second-"
   433  	if !strings.HasPrefix(s, pre) {
   434  		return 0, errInvalidTimeout
   435  	}
   436  	s = s[len(pre):]
   437  	if s == "" || s[0] < '0' || '9' < s[0] {
   438  		return 0, errInvalidTimeout
   439  	}
   440  	n, err := strconv.ParseInt(s, 10, 64)
   441  	if err != nil || 1<<32-1 < n {
   442  		return 0, errInvalidTimeout
   443  	}
   444  	return time.Duration(n) * time.Second, nil
   445  }
   446
View as plain text