← Back to branch summary

~nskaggs/+junk/xenial-test

« back to all changes in this revision

Viewing changes to src/golang.org/x/net/webdav/lock.go

  • Committer: Nicholas Skaggs
  • Date: 2016-10-24 20:56:05 UTC
  • Revision ID: nicholas.skaggs@canonical.com-20161024205605-z8lta0uvuhtxwzwl
Initi with beta15

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/golang.org/x/net/webdav/lock.go
 
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
}