lock.go 12 KB

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