17464: Add DebugLocksPanicMode and fix some missing locks.
[arvados.git] / sdk / go / arvados / fs_collection.go
1 // Copyright (C) The Arvados Authors. All rights reserved.
2 //
3 // SPDX-License-Identifier: Apache-2.0
4
5 package arvados
6
7 import (
8         "context"
9         "encoding/json"
10         "fmt"
11         "io"
12         "os"
13         "path"
14         "regexp"
15         "sort"
16         "strconv"
17         "strings"
18         "sync"
19         "sync/atomic"
20         "time"
21 )
22
23 var (
24         maxBlockSize      = 1 << 26
25         concurrentWriters = 4 // max goroutines writing to Keep in background and during flush()
26 )
27
28 // A CollectionFileSystem is a FileSystem that can be serialized as a
29 // manifest and stored as a collection.
30 type CollectionFileSystem interface {
31         FileSystem
32
33         // Flush all file data to Keep and return a snapshot of the
34         // filesystem suitable for saving as (Collection)ManifestText.
35         // Prefix (normally ".") is a top level directory, effectively
36         // prepended to all paths in the returned manifest.
37         MarshalManifest(prefix string) (string, error)
38
39         // Total data bytes in all files.
40         Size() int64
41 }
42
43 type collectionFileSystem struct {
44         fileSystem
45         uuid string
46 }
47
48 // FileSystem returns a CollectionFileSystem for the collection.
49 func (c *Collection) FileSystem(client apiClient, kc keepClient) (CollectionFileSystem, error) {
50         modTime := c.ModifiedAt
51         if modTime.IsZero() {
52                 modTime = time.Now()
53         }
54         fs := &collectionFileSystem{
55                 uuid: c.UUID,
56                 fileSystem: fileSystem{
57                         fsBackend: keepBackend{apiClient: client, keepClient: kc},
58                         thr:       newThrottle(concurrentWriters),
59                 },
60         }
61         root := &dirnode{
62                 fs: fs,
63                 treenode: treenode{
64                         fileinfo: fileinfo{
65                                 name:    ".",
66                                 mode:    os.ModeDir | 0755,
67                                 modTime: modTime,
68                         },
69                         inodes: make(map[string]inode),
70                 },
71         }
72         root.SetParent(root, ".")
73         if err := root.loadManifest(c.ManifestText); err != nil {
74                 return nil, err
75         }
76         backdateTree(root, modTime)
77         fs.root = root
78         return fs, nil
79 }
80
81 func backdateTree(n inode, modTime time.Time) {
82         switch n := n.(type) {
83         case *filenode:
84                 n.fileinfo.modTime = modTime
85         case *dirnode:
86                 n.fileinfo.modTime = modTime
87                 for _, n := range n.inodes {
88                         backdateTree(n, modTime)
89                 }
90         }
91 }
92
93 func (fs *collectionFileSystem) newNode(name string, perm os.FileMode, modTime time.Time) (node inode, err error) {
94         if name == "" || name == "." || name == ".." {
95                 return nil, ErrInvalidArgument
96         }
97         if perm.IsDir() {
98                 return &dirnode{
99                         fs: fs,
100                         treenode: treenode{
101                                 fileinfo: fileinfo{
102                                         name:    name,
103                                         mode:    perm | os.ModeDir,
104                                         modTime: modTime,
105                                 },
106                                 inodes: make(map[string]inode),
107                         },
108                 }, nil
109         }
110         return &filenode{
111                 fs: fs,
112                 fileinfo: fileinfo{
113                         name:    name,
114                         mode:    perm & ^os.ModeDir,
115                         modTime: modTime,
116                 },
117         }, nil
118 }
119
120 func (fs *collectionFileSystem) Child(name string, replace func(inode) (inode, error)) (inode, error) {
121         return fs.rootnode().Child(name, replace)
122 }
123
124 func (fs *collectionFileSystem) FS() FileSystem {
125         return fs
126 }
127
128 func (fs *collectionFileSystem) FileInfo() os.FileInfo {
129         return fs.rootnode().FileInfo()
130 }
131
132 func (fs *collectionFileSystem) IsDir() bool {
133         return true
134 }
135
136 func (fs *collectionFileSystem) Lock() {
137         fs.rootnode().Lock()
138 }
139
140 func (fs *collectionFileSystem) Unlock() {
141         fs.rootnode().Unlock()
142 }
143
144 func (fs *collectionFileSystem) RLock() {
145         fs.rootnode().RLock()
146 }
147
148 func (fs *collectionFileSystem) RUnlock() {
149         fs.rootnode().RUnlock()
150 }
151
152 func (fs *collectionFileSystem) Parent() inode {
153         return fs.rootnode().Parent()
154 }
155
156 func (fs *collectionFileSystem) Read(_ []byte, ptr filenodePtr) (int, filenodePtr, error) {
157         return 0, ptr, ErrInvalidOperation
158 }
159
160 func (fs *collectionFileSystem) Write(_ []byte, ptr filenodePtr) (int, filenodePtr, error) {
161         return 0, ptr, ErrInvalidOperation
162 }
163
164 func (fs *collectionFileSystem) Readdir() ([]os.FileInfo, error) {
165         return fs.rootnode().Readdir()
166 }
167
168 func (fs *collectionFileSystem) SetParent(parent inode, name string) {
169         fs.rootnode().SetParent(parent, name)
170 }
171
172 func (fs *collectionFileSystem) Truncate(int64) error {
173         return ErrInvalidOperation
174 }
175
176 func (fs *collectionFileSystem) Sync() error {
177         if fs.uuid == "" {
178                 return nil
179         }
180         txt, err := fs.MarshalManifest(".")
181         if err != nil {
182                 return fmt.Errorf("sync failed: %s", err)
183         }
184         coll := &Collection{
185                 UUID:         fs.uuid,
186                 ManifestText: txt,
187         }
188         err = fs.RequestAndDecode(nil, "PUT", "arvados/v1/collections/"+fs.uuid, nil, map[string]interface{}{
189                 "collection": map[string]string{
190                         "manifest_text": coll.ManifestText,
191                 },
192                 "select": []string{"uuid"},
193         })
194         if err != nil {
195                 return fmt.Errorf("sync failed: update %s: %s", fs.uuid, err)
196         }
197         return nil
198 }
199
200 func (fs *collectionFileSystem) Flush(path string, shortBlocks bool) error {
201         node, err := rlookup(fs.fileSystem.root, path)
202         if err != nil {
203                 return err
204         }
205         dn, ok := node.(*dirnode)
206         if !ok {
207                 return ErrNotADirectory
208         }
209         dn.Lock()
210         defer dn.Unlock()
211         names := dn.sortedNames()
212         if path != "" {
213                 // Caller only wants to flush the specified dir,
214                 // non-recursively.  Drop subdirs from the list of
215                 // names.
216                 var filenames []string
217                 for _, name := range names {
218                         if _, ok := dn.inodes[name].(*filenode); ok {
219                                 filenames = append(filenames, name)
220                         }
221                 }
222                 names = filenames
223         }
224         for _, name := range names {
225                 child := dn.inodes[name]
226                 child.Lock()
227                 defer child.Unlock()
228         }
229         return dn.flush(context.TODO(), names, flushOpts{sync: false, shortBlocks: shortBlocks})
230 }
231
232 func (fs *collectionFileSystem) MemorySize() int64 {
233         fs.fileSystem.root.Lock()
234         defer fs.fileSystem.root.Unlock()
235         return fs.fileSystem.root.(*dirnode).MemorySize()
236 }
237
238 func (fs *collectionFileSystem) MarshalManifest(prefix string) (string, error) {
239         fs.fileSystem.root.Lock()
240         defer fs.fileSystem.root.Unlock()
241         return fs.fileSystem.root.(*dirnode).marshalManifest(context.TODO(), prefix)
242 }
243
244 func (fs *collectionFileSystem) Size() int64 {
245         return fs.fileSystem.root.(*dirnode).TreeSize()
246 }
247
248 // filenodePtr is an offset into a file that is (usually) efficient to
249 // seek to. Specifically, if filenode.repacked==filenodePtr.repacked
250 // then
251 // filenode.segments[filenodePtr.segmentIdx][filenodePtr.segmentOff]
252 // corresponds to file offset filenodePtr.off. Otherwise, it is
253 // necessary to reexamine len(filenode.segments[0]) etc. to find the
254 // correct segment and offset.
255 type filenodePtr struct {
256         off        int64
257         segmentIdx int
258         segmentOff int
259         repacked   int64
260 }
261
262 // seek returns a ptr that is consistent with both startPtr.off and
263 // the current state of fn. The caller must already hold fn.RLock() or
264 // fn.Lock().
265 //
266 // If startPtr is beyond EOF, ptr.segment* will indicate precisely
267 // EOF.
268 //
269 // After seeking:
270 //
271 //     ptr.segmentIdx == len(filenode.segments) // i.e., at EOF
272 //     ||
273 //     filenode.segments[ptr.segmentIdx].Len() > ptr.segmentOff
274 func (fn *filenode) seek(startPtr filenodePtr) (ptr filenodePtr) {
275         ptr = startPtr
276         if ptr.off < 0 {
277                 // meaningless anyway
278                 return
279         } else if ptr.off >= fn.fileinfo.size {
280                 ptr.segmentIdx = len(fn.segments)
281                 ptr.segmentOff = 0
282                 ptr.repacked = fn.repacked
283                 return
284         } else if ptr.repacked == fn.repacked {
285                 // segmentIdx and segmentOff accurately reflect
286                 // ptr.off, but might have fallen off the end of a
287                 // segment
288                 if ptr.segmentOff >= fn.segments[ptr.segmentIdx].Len() {
289                         ptr.segmentIdx++
290                         ptr.segmentOff = 0
291                 }
292                 return
293         }
294         defer func() {
295                 ptr.repacked = fn.repacked
296         }()
297         if ptr.off >= fn.fileinfo.size {
298                 ptr.segmentIdx, ptr.segmentOff = len(fn.segments), 0
299                 return
300         }
301         // Recompute segmentIdx and segmentOff.  We have already
302         // established fn.fileinfo.size > ptr.off >= 0, so we don't
303         // have to deal with edge cases here.
304         var off int64
305         for ptr.segmentIdx, ptr.segmentOff = 0, 0; off < ptr.off; ptr.segmentIdx++ {
306                 // This would panic (index out of range) if
307                 // fn.fileinfo.size were larger than
308                 // sum(fn.segments[i].Len()) -- but that can't happen
309                 // because we have ensured fn.fileinfo.size is always
310                 // accurate.
311                 segLen := int64(fn.segments[ptr.segmentIdx].Len())
312                 if off+segLen > ptr.off {
313                         ptr.segmentOff = int(ptr.off - off)
314                         break
315                 }
316                 off += segLen
317         }
318         return
319 }
320
321 // filenode implements inode.
322 type filenode struct {
323         parent   inode
324         fs       FileSystem
325         fileinfo fileinfo
326         segments []segment
327         // number of times `segments` has changed in a
328         // way that might invalidate a filenodePtr
329         repacked int64
330         memsize  int64 // bytes in memSegments
331         sync.RWMutex
332         nullnode
333 }
334
335 // caller must have lock
336 func (fn *filenode) appendSegment(e segment) {
337         fn.segments = append(fn.segments, e)
338         fn.fileinfo.size += int64(e.Len())
339 }
340
341 func (fn *filenode) SetParent(p inode, name string) {
342         fn.Lock()
343         defer fn.Unlock()
344         fn.parent = p
345         fn.fileinfo.name = name
346 }
347
348 func (fn *filenode) Parent() inode {
349         fn.RLock()
350         defer fn.RUnlock()
351         return fn.parent
352 }
353
354 func (fn *filenode) FS() FileSystem {
355         return fn.fs
356 }
357
358 // Read reads file data from a single segment, starting at startPtr,
359 // into p. startPtr is assumed not to be up-to-date. Caller must have
360 // RLock or Lock.
361 func (fn *filenode) Read(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) {
362         ptr = fn.seek(startPtr)
363         if ptr.off < 0 {
364                 err = ErrNegativeOffset
365                 return
366         }
367         if ptr.segmentIdx >= len(fn.segments) {
368                 err = io.EOF
369                 return
370         }
371         n, err = fn.segments[ptr.segmentIdx].ReadAt(p, int64(ptr.segmentOff))
372         if n > 0 {
373                 ptr.off += int64(n)
374                 ptr.segmentOff += n
375                 if ptr.segmentOff == fn.segments[ptr.segmentIdx].Len() {
376                         ptr.segmentIdx++
377                         ptr.segmentOff = 0
378                         if ptr.segmentIdx < len(fn.segments) && err == io.EOF {
379                                 err = nil
380                         }
381                 }
382         }
383         return
384 }
385
386 func (fn *filenode) Size() int64 {
387         fn.RLock()
388         defer fn.RUnlock()
389         return fn.fileinfo.Size()
390 }
391
392 func (fn *filenode) FileInfo() os.FileInfo {
393         fn.RLock()
394         defer fn.RUnlock()
395         return fn.fileinfo
396 }
397
398 func (fn *filenode) Truncate(size int64) error {
399         fn.Lock()
400         defer fn.Unlock()
401         return fn.truncate(size)
402 }
403
404 func (fn *filenode) truncate(size int64) error {
405         if size == fn.fileinfo.size {
406                 return nil
407         }
408         fn.repacked++
409         if size < fn.fileinfo.size {
410                 ptr := fn.seek(filenodePtr{off: size})
411                 for i := ptr.segmentIdx; i < len(fn.segments); i++ {
412                         if seg, ok := fn.segments[i].(*memSegment); ok {
413                                 fn.memsize -= int64(seg.Len())
414                         }
415                 }
416                 if ptr.segmentOff == 0 {
417                         fn.segments = fn.segments[:ptr.segmentIdx]
418                 } else {
419                         fn.segments = fn.segments[:ptr.segmentIdx+1]
420                         switch seg := fn.segments[ptr.segmentIdx].(type) {
421                         case *memSegment:
422                                 seg.Truncate(ptr.segmentOff)
423                                 fn.memsize += int64(seg.Len())
424                         default:
425                                 fn.segments[ptr.segmentIdx] = seg.Slice(0, ptr.segmentOff)
426                         }
427                 }
428                 fn.fileinfo.size = size
429                 return nil
430         }
431         for size > fn.fileinfo.size {
432                 grow := size - fn.fileinfo.size
433                 var seg *memSegment
434                 var ok bool
435                 if len(fn.segments) == 0 {
436                         seg = &memSegment{}
437                         fn.segments = append(fn.segments, seg)
438                 } else if seg, ok = fn.segments[len(fn.segments)-1].(*memSegment); !ok || seg.Len() >= maxBlockSize {
439                         seg = &memSegment{}
440                         fn.segments = append(fn.segments, seg)
441                 }
442                 if maxgrow := int64(maxBlockSize - seg.Len()); maxgrow < grow {
443                         grow = maxgrow
444                 }
445                 seg.Truncate(seg.Len() + int(grow))
446                 fn.fileinfo.size += grow
447                 fn.memsize += grow
448         }
449         return nil
450 }
451
452 // Write writes data from p to the file, starting at startPtr,
453 // extending the file size if necessary. Caller must have Lock.
454 func (fn *filenode) Write(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) {
455         if startPtr.off > fn.fileinfo.size {
456                 if err = fn.truncate(startPtr.off); err != nil {
457                         return 0, startPtr, err
458                 }
459         }
460         ptr = fn.seek(startPtr)
461         if ptr.off < 0 {
462                 err = ErrNegativeOffset
463                 return
464         }
465         for len(p) > 0 && err == nil {
466                 cando := p
467                 if len(cando) > maxBlockSize {
468                         cando = cando[:maxBlockSize]
469                 }
470                 // Rearrange/grow fn.segments (and shrink cando if
471                 // needed) such that cando can be copied to
472                 // fn.segments[ptr.segmentIdx] at offset
473                 // ptr.segmentOff.
474                 cur := ptr.segmentIdx
475                 prev := ptr.segmentIdx - 1
476                 var curWritable bool
477                 if cur < len(fn.segments) {
478                         _, curWritable = fn.segments[cur].(*memSegment)
479                 }
480                 var prevAppendable bool
481                 if prev >= 0 && fn.segments[prev].Len() < maxBlockSize {
482                         _, prevAppendable = fn.segments[prev].(*memSegment)
483                 }
484                 if ptr.segmentOff > 0 && !curWritable {
485                         // Split a non-writable block.
486                         if max := fn.segments[cur].Len() - ptr.segmentOff; max <= len(cando) {
487                                 // Truncate cur, and insert a new
488                                 // segment after it.
489                                 cando = cando[:max]
490                                 fn.segments = append(fn.segments, nil)
491                                 copy(fn.segments[cur+1:], fn.segments[cur:])
492                         } else {
493                                 // Split cur into two copies, truncate
494                                 // the one on the left, shift the one
495                                 // on the right, and insert a new
496                                 // segment between them.
497                                 fn.segments = append(fn.segments, nil, nil)
498                                 copy(fn.segments[cur+2:], fn.segments[cur:])
499                                 fn.segments[cur+2] = fn.segments[cur+2].Slice(ptr.segmentOff+len(cando), -1)
500                         }
501                         cur++
502                         prev++
503                         seg := &memSegment{}
504                         seg.Truncate(len(cando))
505                         fn.memsize += int64(len(cando))
506                         fn.segments[cur] = seg
507                         fn.segments[prev] = fn.segments[prev].Slice(0, ptr.segmentOff)
508                         ptr.segmentIdx++
509                         ptr.segmentOff = 0
510                         fn.repacked++
511                         ptr.repacked++
512                 } else if curWritable {
513                         if fit := int(fn.segments[cur].Len()) - ptr.segmentOff; fit < len(cando) {
514                                 cando = cando[:fit]
515                         }
516                 } else {
517                         if prevAppendable {
518                                 // Shrink cando if needed to fit in
519                                 // prev segment.
520                                 if cangrow := maxBlockSize - fn.segments[prev].Len(); cangrow < len(cando) {
521                                         cando = cando[:cangrow]
522                                 }
523                         }
524
525                         if cur == len(fn.segments) {
526                                 // ptr is at EOF, filesize is changing.
527                                 fn.fileinfo.size += int64(len(cando))
528                         } else if el := fn.segments[cur].Len(); el <= len(cando) {
529                                 // cando is long enough that we won't
530                                 // need cur any more. shrink cando to
531                                 // be exactly as long as cur
532                                 // (otherwise we'd accidentally shift
533                                 // the effective position of all
534                                 // segments after cur).
535                                 cando = cando[:el]
536                                 copy(fn.segments[cur:], fn.segments[cur+1:])
537                                 fn.segments = fn.segments[:len(fn.segments)-1]
538                         } else {
539                                 // shrink cur by the same #bytes we're growing prev
540                                 fn.segments[cur] = fn.segments[cur].Slice(len(cando), -1)
541                         }
542
543                         if prevAppendable {
544                                 // Grow prev.
545                                 ptr.segmentIdx--
546                                 ptr.segmentOff = fn.segments[prev].Len()
547                                 fn.segments[prev].(*memSegment).Truncate(ptr.segmentOff + len(cando))
548                                 fn.memsize += int64(len(cando))
549                                 ptr.repacked++
550                                 fn.repacked++
551                         } else {
552                                 // Insert a segment between prev and
553                                 // cur, and advance prev/cur.
554                                 fn.segments = append(fn.segments, nil)
555                                 if cur < len(fn.segments) {
556                                         copy(fn.segments[cur+1:], fn.segments[cur:])
557                                         ptr.repacked++
558                                         fn.repacked++
559                                 } else {
560                                         // appending a new segment does
561                                         // not invalidate any ptrs
562                                 }
563                                 seg := &memSegment{}
564                                 seg.Truncate(len(cando))
565                                 fn.memsize += int64(len(cando))
566                                 fn.segments[cur] = seg
567                         }
568                 }
569
570                 // Finally we can copy bytes from cando to the current segment.
571                 fn.segments[ptr.segmentIdx].(*memSegment).WriteAt(cando, ptr.segmentOff)
572                 n += len(cando)
573                 p = p[len(cando):]
574
575                 ptr.off += int64(len(cando))
576                 ptr.segmentOff += len(cando)
577                 if ptr.segmentOff >= maxBlockSize {
578                         fn.pruneMemSegments()
579                 }
580                 if fn.segments[ptr.segmentIdx].Len() == ptr.segmentOff {
581                         ptr.segmentOff = 0
582                         ptr.segmentIdx++
583                 }
584
585                 fn.fileinfo.modTime = time.Now()
586         }
587         return
588 }
589
590 // Write some data out to disk to reduce memory use. Caller must have
591 // write lock.
592 func (fn *filenode) pruneMemSegments() {
593         // TODO: share code with (*dirnode)flush()
594         // TODO: pack/flush small blocks too, when fragmented
595         for idx, seg := range fn.segments {
596                 seg, ok := seg.(*memSegment)
597                 if !ok || seg.Len() < maxBlockSize || seg.flushing != nil {
598                         continue
599                 }
600                 // Setting seg.flushing guarantees seg.buf will not be
601                 // modified in place: WriteAt and Truncate will
602                 // allocate a new buf instead, if necessary.
603                 idx, buf := idx, seg.buf
604                 done := make(chan struct{})
605                 seg.flushing = done
606                 // If lots of background writes are already in
607                 // progress, block here until one finishes, rather
608                 // than pile up an unlimited number of buffered writes
609                 // and network flush operations.
610                 fn.fs.throttle().Acquire()
611                 go func() {
612                         defer close(done)
613                         locator, _, err := fn.FS().PutB(buf)
614                         fn.fs.throttle().Release()
615                         fn.Lock()
616                         defer fn.Unlock()
617                         if seg.flushing != done {
618                                 // A new seg.buf has been allocated.
619                                 return
620                         }
621                         if err != nil {
622                                 // TODO: stall (or return errors from)
623                                 // subsequent writes until flushing
624                                 // starts to succeed.
625                                 return
626                         }
627                         if len(fn.segments) <= idx || fn.segments[idx] != seg || len(seg.buf) != len(buf) {
628                                 // Segment has been dropped/moved/resized.
629                                 return
630                         }
631                         fn.memsize -= int64(len(buf))
632                         fn.segments[idx] = storedSegment{
633                                 kc:      fn.FS(),
634                                 locator: locator,
635                                 size:    len(buf),
636                                 offset:  0,
637                                 length:  len(buf),
638                         }
639                 }()
640         }
641 }
642
643 // Block until all pending pruneMemSegments/flush work is
644 // finished. Caller must NOT have lock.
645 func (fn *filenode) waitPrune() {
646         var pending []<-chan struct{}
647         fn.Lock()
648         for _, seg := range fn.segments {
649                 if seg, ok := seg.(*memSegment); ok && seg.flushing != nil {
650                         pending = append(pending, seg.flushing)
651                 }
652         }
653         fn.Unlock()
654         for _, p := range pending {
655                 <-p
656         }
657 }
658
659 type dirnode struct {
660         fs *collectionFileSystem
661         treenode
662 }
663
664 func (dn *dirnode) FS() FileSystem {
665         return dn.fs
666 }
667
668 func (dn *dirnode) Child(name string, replace func(inode) (inode, error)) (inode, error) {
669         if dn == dn.fs.rootnode() && name == ".arvados#collection" {
670                 gn := &getternode{Getter: func() ([]byte, error) {
671                         var coll Collection
672                         var err error
673                         coll.ManifestText, err = dn.fs.MarshalManifest(".")
674                         if err != nil {
675                                 return nil, err
676                         }
677                         data, err := json.Marshal(&coll)
678                         if err == nil {
679                                 data = append(data, '\n')
680                         }
681                         return data, err
682                 }}
683                 gn.SetParent(dn, name)
684                 return gn, nil
685         }
686         return dn.treenode.Child(name, replace)
687 }
688
689 type fnSegmentRef struct {
690         fn  *filenode
691         idx int
692 }
693
694 // commitBlock concatenates the data from the given filenode segments
695 // (which must be *memSegments), writes the data out to Keep as a
696 // single block, and replaces the filenodes' *memSegments with
697 // storedSegments that reference the relevant portions of the new
698 // block.
699 //
700 // bufsize is the total data size in refs. It is used to preallocate
701 // the correct amount of memory when len(refs)>1.
702 //
703 // If sync is false, commitBlock returns right away, after starting a
704 // goroutine to do the writes, reacquire the filenodes' locks, and
705 // swap out the *memSegments. Some filenodes' segments might get
706 // modified/rearranged in the meantime, in which case commitBlock
707 // won't replace them.
708 //
709 // Caller must have write lock.
710 func (dn *dirnode) commitBlock(ctx context.Context, refs []fnSegmentRef, bufsize int, sync bool) error {
711         if len(refs) == 0 {
712                 return nil
713         }
714         if err := ctx.Err(); err != nil {
715                 return err
716         }
717         done := make(chan struct{})
718         var block []byte
719         segs := make([]*memSegment, 0, len(refs))
720         offsets := make([]int, 0, len(refs)) // location of segment's data within block
721         for _, ref := range refs {
722                 seg := ref.fn.segments[ref.idx].(*memSegment)
723                 if !sync && seg.flushingUnfinished() {
724                         // Let the other flushing goroutine finish. If
725                         // it fails, we'll try again next time.
726                         close(done)
727                         return nil
728                 }
729                 // In sync mode, we proceed regardless of
730                 // whether another flush is in progress: It
731                 // can't finish before we do, because we hold
732                 // fn's lock until we finish our own writes.
733                 seg.flushing = done
734                 offsets = append(offsets, len(block))
735                 if len(refs) == 1 {
736                         block = seg.buf
737                 } else if block == nil {
738                         block = append(make([]byte, 0, bufsize), seg.buf...)
739                 } else {
740                         block = append(block, seg.buf...)
741                 }
742                 segs = append(segs, seg)
743         }
744         blocksize := len(block)
745         dn.fs.throttle().Acquire()
746         errs := make(chan error, 1)
747         go func() {
748                 defer close(done)
749                 defer close(errs)
750                 locator, _, err := dn.fs.PutB(block)
751                 dn.fs.throttle().Release()
752                 if err != nil {
753                         errs <- err
754                         return
755                 }
756                 for idx, ref := range refs {
757                         if !sync {
758                                 ref.fn.Lock()
759                                 // In async mode, fn's lock was
760                                 // released while we were waiting for
761                                 // PutB(); lots of things might have
762                                 // changed.
763                                 if len(ref.fn.segments) <= ref.idx {
764                                         // file segments have
765                                         // rearranged or changed in
766                                         // some way
767                                         ref.fn.Unlock()
768                                         continue
769                                 } else if seg, ok := ref.fn.segments[ref.idx].(*memSegment); !ok || seg != segs[idx] {
770                                         // segment has been replaced
771                                         ref.fn.Unlock()
772                                         continue
773                                 } else if seg.flushing != done {
774                                         // seg.buf has been replaced
775                                         ref.fn.Unlock()
776                                         continue
777                                 }
778                         }
779                         data := ref.fn.segments[ref.idx].(*memSegment).buf
780                         ref.fn.segments[ref.idx] = storedSegment{
781                                 kc:      dn.fs,
782                                 locator: locator,
783                                 size:    blocksize,
784                                 offset:  offsets[idx],
785                                 length:  len(data),
786                         }
787                         // atomic is needed here despite caller having
788                         // lock: caller might be running concurrent
789                         // commitBlock() goroutines using the same
790                         // lock, writing different segments from the
791                         // same file.
792                         atomic.AddInt64(&ref.fn.memsize, -int64(len(data)))
793                         if !sync {
794                                 ref.fn.Unlock()
795                         }
796                 }
797         }()
798         if sync {
799                 return <-errs
800         }
801         return nil
802 }
803
804 type flushOpts struct {
805         sync        bool
806         shortBlocks bool
807 }
808
809 // flush in-memory data and remote-cluster block references (for the
810 // children with the given names, which must be children of dn) to
811 // local-cluster persistent storage.
812 //
813 // Caller must have write lock on dn and the named children.
814 //
815 // If any children are dirs, they will be flushed recursively.
816 func (dn *dirnode) flush(ctx context.Context, names []string, opts flushOpts) error {
817         cg := newContextGroup(ctx)
818         defer cg.Cancel()
819
820         goCommit := func(refs []fnSegmentRef, bufsize int) {
821                 cg.Go(func() error {
822                         return dn.commitBlock(cg.Context(), refs, bufsize, opts.sync)
823                 })
824         }
825
826         var pending []fnSegmentRef
827         var pendingLen int = 0
828         localLocator := map[string]string{}
829         for _, name := range names {
830                 switch node := dn.inodes[name].(type) {
831                 case *dirnode:
832                         grandchildNames := node.sortedNames()
833                         for _, grandchildName := range grandchildNames {
834                                 grandchild := node.inodes[grandchildName]
835                                 grandchild.Lock()
836                                 defer grandchild.Unlock()
837                         }
838                         cg.Go(func() error { return node.flush(cg.Context(), grandchildNames, opts) })
839                 case *filenode:
840                         for idx, seg := range node.segments {
841                                 switch seg := seg.(type) {
842                                 case storedSegment:
843                                         loc, ok := localLocator[seg.locator]
844                                         if !ok {
845                                                 var err error
846                                                 loc, err = dn.fs.LocalLocator(seg.locator)
847                                                 if err != nil {
848                                                         return err
849                                                 }
850                                                 localLocator[seg.locator] = loc
851                                         }
852                                         seg.locator = loc
853                                         node.segments[idx] = seg
854                                 case *memSegment:
855                                         if seg.Len() > maxBlockSize/2 {
856                                                 goCommit([]fnSegmentRef{{node, idx}}, seg.Len())
857                                                 continue
858                                         }
859                                         if pendingLen+seg.Len() > maxBlockSize {
860                                                 goCommit(pending, pendingLen)
861                                                 pending = nil
862                                                 pendingLen = 0
863                                         }
864                                         pending = append(pending, fnSegmentRef{node, idx})
865                                         pendingLen += seg.Len()
866                                 default:
867                                         panic(fmt.Sprintf("can't sync segment type %T", seg))
868                                 }
869                         }
870                 }
871         }
872         if opts.shortBlocks {
873                 goCommit(pending, pendingLen)
874         }
875         return cg.Wait()
876 }
877
878 // caller must have write lock.
879 func (dn *dirnode) MemorySize() (size int64) {
880         for _, name := range dn.sortedNames() {
881                 node := dn.inodes[name]
882                 node.Lock()
883                 defer node.Unlock()
884                 switch node := node.(type) {
885                 case *dirnode:
886                         size += node.MemorySize()
887                 case *filenode:
888                         for _, seg := range node.segments {
889                                 switch seg := seg.(type) {
890                                 case *memSegment:
891                                         size += int64(seg.Len())
892                                 }
893                         }
894                 }
895         }
896         return
897 }
898
899 // caller must have write lock.
900 func (dn *dirnode) sortedNames() []string {
901         names := make([]string, 0, len(dn.inodes))
902         for name := range dn.inodes {
903                 names = append(names, name)
904         }
905         sort.Strings(names)
906         return names
907 }
908
909 // caller must have write lock.
910 func (dn *dirnode) marshalManifest(ctx context.Context, prefix string) (string, error) {
911         cg := newContextGroup(ctx)
912         defer cg.Cancel()
913
914         if len(dn.inodes) == 0 {
915                 if prefix == "." {
916                         return "", nil
917                 }
918                 // Express the existence of an empty directory by
919                 // adding an empty file named `\056`, which (unlike
920                 // the more obvious spelling `.`) is accepted by the
921                 // API's manifest validator.
922                 return manifestEscape(prefix) + " d41d8cd98f00b204e9800998ecf8427e+0 0:0:\\056\n", nil
923         }
924
925         names := dn.sortedNames()
926
927         // Wait for children to finish any pending write operations
928         // before locking them.
929         for _, name := range names {
930                 node := dn.inodes[name]
931                 if fn, ok := node.(*filenode); ok {
932                         fn.waitPrune()
933                 }
934         }
935
936         var dirnames []string
937         var filenames []string
938         for _, name := range names {
939                 node := dn.inodes[name]
940                 node.Lock()
941                 defer node.Unlock()
942                 switch node := node.(type) {
943                 case *dirnode:
944                         dirnames = append(dirnames, name)
945                 case *filenode:
946                         filenames = append(filenames, name)
947                 default:
948                         panic(fmt.Sprintf("can't marshal inode type %T", node))
949                 }
950         }
951
952         subdirs := make([]string, len(dirnames))
953         rootdir := ""
954         for i, name := range dirnames {
955                 i, name := i, name
956                 cg.Go(func() error {
957                         txt, err := dn.inodes[name].(*dirnode).marshalManifest(cg.Context(), prefix+"/"+name)
958                         subdirs[i] = txt
959                         return err
960                 })
961         }
962
963         cg.Go(func() error {
964                 var streamLen int64
965                 type filepart struct {
966                         name   string
967                         offset int64
968                         length int64
969                 }
970
971                 var fileparts []filepart
972                 var blocks []string
973                 if err := dn.flush(cg.Context(), filenames, flushOpts{sync: true, shortBlocks: true}); err != nil {
974                         return err
975                 }
976                 for _, name := range filenames {
977                         node := dn.inodes[name].(*filenode)
978                         if len(node.segments) == 0 {
979                                 fileparts = append(fileparts, filepart{name: name})
980                                 continue
981                         }
982                         for _, seg := range node.segments {
983                                 switch seg := seg.(type) {
984                                 case storedSegment:
985                                         if len(blocks) > 0 && blocks[len(blocks)-1] == seg.locator {
986                                                 streamLen -= int64(seg.size)
987                                         } else {
988                                                 blocks = append(blocks, seg.locator)
989                                         }
990                                         next := filepart{
991                                                 name:   name,
992                                                 offset: streamLen + int64(seg.offset),
993                                                 length: int64(seg.length),
994                                         }
995                                         if prev := len(fileparts) - 1; prev >= 0 &&
996                                                 fileparts[prev].name == name &&
997                                                 fileparts[prev].offset+fileparts[prev].length == next.offset {
998                                                 fileparts[prev].length += next.length
999                                         } else {
1000                                                 fileparts = append(fileparts, next)
1001                                         }
1002                                         streamLen += int64(seg.size)
1003                                 default:
1004                                         // This can't happen: we
1005                                         // haven't unlocked since
1006                                         // calling flush(sync=true).
1007                                         panic(fmt.Sprintf("can't marshal segment type %T", seg))
1008                                 }
1009                         }
1010                 }
1011                 var filetokens []string
1012                 for _, s := range fileparts {
1013                         filetokens = append(filetokens, fmt.Sprintf("%d:%d:%s", s.offset, s.length, manifestEscape(s.name)))
1014                 }
1015                 if len(filetokens) == 0 {
1016                         return nil
1017                 } else if len(blocks) == 0 {
1018                         blocks = []string{"d41d8cd98f00b204e9800998ecf8427e+0"}
1019                 }
1020                 rootdir = manifestEscape(prefix) + " " + strings.Join(blocks, " ") + " " + strings.Join(filetokens, " ") + "\n"
1021                 return nil
1022         })
1023         err := cg.Wait()
1024         return rootdir + strings.Join(subdirs, ""), err
1025 }
1026
1027 func (dn *dirnode) loadManifest(txt string) error {
1028         var dirname string
1029         streams := strings.Split(txt, "\n")
1030         if streams[len(streams)-1] != "" {
1031                 return fmt.Errorf("line %d: no trailing newline", len(streams))
1032         }
1033         streams = streams[:len(streams)-1]
1034         segments := []storedSegment{}
1035         for i, stream := range streams {
1036                 lineno := i + 1
1037                 var anyFileTokens bool
1038                 var pos int64
1039                 var segIdx int
1040                 segments = segments[:0]
1041                 for i, token := range strings.Split(stream, " ") {
1042                         if i == 0 {
1043                                 dirname = manifestUnescape(token)
1044                                 continue
1045                         }
1046                         if !strings.Contains(token, ":") {
1047                                 if anyFileTokens {
1048                                         return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1049                                 }
1050                                 toks := strings.SplitN(token, "+", 3)
1051                                 if len(toks) < 2 {
1052                                         return fmt.Errorf("line %d: bad locator %q", lineno, token)
1053                                 }
1054                                 length, err := strconv.ParseInt(toks[1], 10, 32)
1055                                 if err != nil || length < 0 {
1056                                         return fmt.Errorf("line %d: bad locator %q", lineno, token)
1057                                 }
1058                                 segments = append(segments, storedSegment{
1059                                         locator: token,
1060                                         size:    int(length),
1061                                         offset:  0,
1062                                         length:  int(length),
1063                                 })
1064                                 continue
1065                         } else if len(segments) == 0 {
1066                                 return fmt.Errorf("line %d: bad locator %q", lineno, token)
1067                         }
1068
1069                         toks := strings.SplitN(token, ":", 3)
1070                         if len(toks) != 3 {
1071                                 return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1072                         }
1073                         anyFileTokens = true
1074
1075                         offset, err := strconv.ParseInt(toks[0], 10, 64)
1076                         if err != nil || offset < 0 {
1077                                 return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1078                         }
1079                         length, err := strconv.ParseInt(toks[1], 10, 64)
1080                         if err != nil || length < 0 {
1081                                 return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1082                         }
1083                         name := dirname + "/" + manifestUnescape(toks[2])
1084                         fnode, err := dn.createFileAndParents(name)
1085                         if fnode == nil && err == nil && length == 0 {
1086                                 // Special case: an empty file used as
1087                                 // a marker to preserve an otherwise
1088                                 // empty directory in a manifest.
1089                                 continue
1090                         }
1091                         if err != nil || (fnode == nil && length != 0) {
1092                                 return fmt.Errorf("line %d: cannot use path %q with length %d: %s", lineno, name, length, err)
1093                         }
1094                         // Map the stream offset/range coordinates to
1095                         // block/offset/range coordinates and add
1096                         // corresponding storedSegments to the filenode
1097                         if pos > offset {
1098                                 // Can't continue where we left off.
1099                                 // TODO: binary search instead of
1100                                 // rewinding all the way (but this
1101                                 // situation might be rare anyway)
1102                                 segIdx, pos = 0, 0
1103                         }
1104                         for ; segIdx < len(segments); segIdx++ {
1105                                 seg := segments[segIdx]
1106                                 next := pos + int64(seg.Len())
1107                                 if next <= offset || seg.Len() == 0 {
1108                                         pos = next
1109                                         continue
1110                                 }
1111                                 if pos >= offset+length {
1112                                         break
1113                                 }
1114                                 var blkOff int
1115                                 if pos < offset {
1116                                         blkOff = int(offset - pos)
1117                                 }
1118                                 blkLen := seg.Len() - blkOff
1119                                 if pos+int64(blkOff+blkLen) > offset+length {
1120                                         blkLen = int(offset + length - pos - int64(blkOff))
1121                                 }
1122                                 fnode.appendSegment(storedSegment{
1123                                         kc:      dn.fs,
1124                                         locator: seg.locator,
1125                                         size:    seg.size,
1126                                         offset:  blkOff,
1127                                         length:  blkLen,
1128                                 })
1129                                 if next > offset+length {
1130                                         break
1131                                 } else {
1132                                         pos = next
1133                                 }
1134                         }
1135                         if segIdx == len(segments) && pos < offset+length {
1136                                 return fmt.Errorf("line %d: invalid segment in %d-byte stream: %q", lineno, pos, token)
1137                         }
1138                 }
1139                 if !anyFileTokens {
1140                         return fmt.Errorf("line %d: no file segments", lineno)
1141                 } else if len(segments) == 0 {
1142                         return fmt.Errorf("line %d: no locators", lineno)
1143                 } else if dirname == "" {
1144                         return fmt.Errorf("line %d: no stream name", lineno)
1145                 }
1146         }
1147         return nil
1148 }
1149
1150 // only safe to call from loadManifest -- no locking.
1151 //
1152 // If path is a "parent directory exists" marker (the last path
1153 // component is "."), the returned values are both nil.
1154 func (dn *dirnode) createFileAndParents(path string) (fn *filenode, err error) {
1155         var node inode = dn
1156         names := strings.Split(path, "/")
1157         basename := names[len(names)-1]
1158         for _, name := range names[:len(names)-1] {
1159                 switch name {
1160                 case "", ".":
1161                         continue
1162                 case "..":
1163                         if node == dn {
1164                                 // can't be sure parent will be a *dirnode
1165                                 return nil, ErrInvalidArgument
1166                         }
1167                         node = node.Parent()
1168                         continue
1169                 }
1170                 modtime := node.Parent().FileInfo().ModTime()
1171                 node.Lock()
1172                 locked := node
1173                 node, err = node.Child(name, func(child inode) (inode, error) {
1174                         if child == nil {
1175                                 child, err := node.FS().newNode(name, 0755|os.ModeDir, modtime)
1176                                 if err != nil {
1177                                         return nil, err
1178                                 }
1179                                 child.SetParent(node, name)
1180                                 return child, nil
1181                         } else if !child.IsDir() {
1182                                 return child, ErrFileExists
1183                         } else {
1184                                 return child, nil
1185                         }
1186                 })
1187                 locked.Unlock()
1188                 if err != nil {
1189                         return
1190                 }
1191         }
1192         if basename == "." {
1193                 return
1194         } else if !permittedName(basename) {
1195                 err = fmt.Errorf("invalid file part %q in path %q", basename, path)
1196                 return
1197         }
1198         modtime := node.FileInfo().ModTime()
1199         node.Lock()
1200         defer node.Unlock()
1201         _, err = node.Child(basename, func(child inode) (inode, error) {
1202                 switch child := child.(type) {
1203                 case nil:
1204                         child, err = node.FS().newNode(basename, 0755, modtime)
1205                         if err != nil {
1206                                 return nil, err
1207                         }
1208                         child.SetParent(node, basename)
1209                         fn = child.(*filenode)
1210                         return child, nil
1211                 case *filenode:
1212                         fn = child
1213                         return child, nil
1214                 case *dirnode:
1215                         return child, ErrIsDirectory
1216                 default:
1217                         return child, ErrInvalidArgument
1218                 }
1219         })
1220         return
1221 }
1222
1223 func (dn *dirnode) TreeSize() (bytes int64) {
1224         dn.RLock()
1225         defer dn.RUnlock()
1226         for _, i := range dn.inodes {
1227                 switch i := i.(type) {
1228                 case *filenode:
1229                         bytes += i.Size()
1230                 case *dirnode:
1231                         bytes += i.TreeSize()
1232                 }
1233         }
1234         return
1235 }
1236
1237 type segment interface {
1238         io.ReaderAt
1239         Len() int
1240         // Return a new segment with a subsection of the data from this
1241         // one. length<0 means length=Len()-off.
1242         Slice(off int, length int) segment
1243 }
1244
1245 type memSegment struct {
1246         buf []byte
1247         // If flushing is not nil and not ready/closed, then a) buf is
1248         // being shared by a pruneMemSegments goroutine, and must be
1249         // copied on write; and b) the flushing channel will close
1250         // when the goroutine finishes, whether it succeeds or not.
1251         flushing <-chan struct{}
1252 }
1253
1254 func (me *memSegment) flushingUnfinished() bool {
1255         if me.flushing == nil {
1256                 return false
1257         }
1258         select {
1259         case <-me.flushing:
1260                 me.flushing = nil
1261                 return false
1262         default:
1263                 return true
1264         }
1265 }
1266
1267 func (me *memSegment) Len() int {
1268         return len(me.buf)
1269 }
1270
1271 func (me *memSegment) Slice(off, length int) segment {
1272         if length < 0 {
1273                 length = len(me.buf) - off
1274         }
1275         buf := make([]byte, length)
1276         copy(buf, me.buf[off:])
1277         return &memSegment{buf: buf}
1278 }
1279
1280 func (me *memSegment) Truncate(n int) {
1281         if n > cap(me.buf) || (me.flushing != nil && n > len(me.buf)) {
1282                 newsize := 1024
1283                 for newsize < n {
1284                         newsize = newsize << 2
1285                 }
1286                 newbuf := make([]byte, n, newsize)
1287                 copy(newbuf, me.buf)
1288                 me.buf, me.flushing = newbuf, nil
1289         } else {
1290                 // reclaim existing capacity, and zero reclaimed part
1291                 oldlen := len(me.buf)
1292                 me.buf = me.buf[:n]
1293                 for i := oldlen; i < n; i++ {
1294                         me.buf[i] = 0
1295                 }
1296         }
1297 }
1298
1299 func (me *memSegment) WriteAt(p []byte, off int) {
1300         if off+len(p) > len(me.buf) {
1301                 panic("overflowed segment")
1302         }
1303         if me.flushing != nil {
1304                 me.buf, me.flushing = append([]byte(nil), me.buf...), nil
1305         }
1306         copy(me.buf[off:], p)
1307 }
1308
1309 func (me *memSegment) ReadAt(p []byte, off int64) (n int, err error) {
1310         if off > int64(me.Len()) {
1311                 err = io.EOF
1312                 return
1313         }
1314         n = copy(p, me.buf[int(off):])
1315         if n < len(p) {
1316                 err = io.EOF
1317         }
1318         return
1319 }
1320
1321 type storedSegment struct {
1322         kc      fsBackend
1323         locator string
1324         size    int // size of stored block (also encoded in locator)
1325         offset  int // position of segment within the stored block
1326         length  int // bytes in this segment (offset + length <= size)
1327 }
1328
1329 func (se storedSegment) Len() int {
1330         return se.length
1331 }
1332
1333 func (se storedSegment) Slice(n, size int) segment {
1334         se.offset += n
1335         se.length -= n
1336         if size >= 0 && se.length > size {
1337                 se.length = size
1338         }
1339         return se
1340 }
1341
1342 func (se storedSegment) ReadAt(p []byte, off int64) (n int, err error) {
1343         if off > int64(se.length) {
1344                 return 0, io.EOF
1345         }
1346         maxlen := se.length - int(off)
1347         if len(p) > maxlen {
1348                 p = p[:maxlen]
1349                 n, err = se.kc.ReadAt(se.locator, p, int(off)+se.offset)
1350                 if err == nil {
1351                         err = io.EOF
1352                 }
1353                 return
1354         }
1355         return se.kc.ReadAt(se.locator, p, int(off)+se.offset)
1356 }
1357
1358 func canonicalName(name string) string {
1359         name = path.Clean("/" + name)
1360         if name == "/" || name == "./" {
1361                 name = "."
1362         } else if strings.HasPrefix(name, "/") {
1363                 name = "." + name
1364         }
1365         return name
1366 }
1367
1368 var manifestEscapeSeq = regexp.MustCompile(`\\([0-7]{3}|\\)`)
1369
1370 func manifestUnescapeFunc(seq string) string {
1371         if seq == `\\` {
1372                 return `\`
1373         }
1374         i, err := strconv.ParseUint(seq[1:], 8, 8)
1375         if err != nil {
1376                 // Invalid escape sequence: can't unescape.
1377                 return seq
1378         }
1379         return string([]byte{byte(i)})
1380 }
1381
1382 func manifestUnescape(s string) string {
1383         return manifestEscapeSeq.ReplaceAllStringFunc(s, manifestUnescapeFunc)
1384 }
1385
1386 var manifestEscapedChar = regexp.MustCompile(`[\000-\040:\s\\]`)
1387
1388 func manifestEscapeFunc(seq string) string {
1389         return fmt.Sprintf("\\%03o", byte(seq[0]))
1390 }
1391
1392 func manifestEscape(s string) string {
1393         return manifestEscapedChar.ReplaceAllStringFunc(s, manifestEscapeFunc)
1394 }