18600: Fix Snapshot/Splice at collectionfs root.
[arvados.git] / sdk / go / arvados / fs_base.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         "errors"
9         "fmt"
10         "io"
11         "io/fs"
12         "log"
13         "net/http"
14         "os"
15         "path"
16         "strings"
17         "sync"
18         "time"
19 )
20
21 var (
22         ErrReadOnlyFile      = errors.New("read-only file")
23         ErrNegativeOffset    = errors.New("cannot seek to negative offset")
24         ErrFileExists        = errors.New("file exists")
25         ErrInvalidOperation  = errors.New("invalid operation")
26         ErrInvalidArgument   = errors.New("invalid argument")
27         ErrDirectoryNotEmpty = errors.New("directory not empty")
28         ErrWriteOnlyMode     = errors.New("file is O_WRONLY")
29         ErrSyncNotSupported  = errors.New("O_SYNC flag is not supported")
30         ErrIsDirectory       = errors.New("cannot rename file to overwrite existing directory")
31         ErrNotADirectory     = errors.New("not a directory")
32         ErrPermission        = os.ErrPermission
33         DebugLocksPanicMode  = false
34 )
35
36 type syncer interface {
37         Sync() error
38 }
39
40 func debugPanicIfNotLocked(l sync.Locker, writing bool) {
41         if !DebugLocksPanicMode {
42                 return
43         }
44         race := false
45         if rl, ok := l.(interface {
46                 RLock()
47                 RUnlock()
48         }); ok && writing {
49                 go func() {
50                         // Fail if we can grab the read lock during an
51                         // operation that purportedly has write lock.
52                         rl.RLock()
53                         race = true
54                         rl.RUnlock()
55                 }()
56         } else {
57                 go func() {
58                         l.Lock()
59                         race = true
60                         l.Unlock()
61                 }()
62         }
63         time.Sleep(100)
64         if race {
65                 panic("bug: caller-must-have-lock func called, but nobody has lock")
66         }
67 }
68
69 // A File is an *os.File-like interface for reading and writing files
70 // in a FileSystem.
71 type File interface {
72         io.Reader
73         io.Writer
74         io.Closer
75         io.Seeker
76         Size() int64
77         Readdir(int) ([]os.FileInfo, error)
78         Stat() (os.FileInfo, error)
79         Truncate(int64) error
80         Sync() error
81         // Create a snapshot of a file or directory tree, which can
82         // then be spliced onto a different path or a different
83         // collection.
84         Snapshot() (*Subtree, error)
85         // Replace this file or directory with the given snapshot.
86         // The target must be inside a collection: Splice returns an
87         // error if the File is a virtual file or directory like
88         // by_id, a project directory, .arvados#collection,
89         // etc. Splice can replace directories with regular files and
90         // vice versa, except it cannot replace the root directory of
91         // a collection with a regular file.
92         Splice(snapshot *Subtree) error
93 }
94
95 // A Subtree is a detached part of a filesystem tree that can be
96 // spliced into a filesystem via (File)Splice().
97 type Subtree struct {
98         inode inode
99 }
100
101 // A FileSystem is an http.Filesystem plus Stat() and support for
102 // opening writable files. All methods are safe to call from multiple
103 // goroutines.
104 type FileSystem interface {
105         http.FileSystem
106         fsBackend
107
108         rootnode() inode
109
110         // filesystem-wide lock: used by Rename() to prevent deadlock
111         // while locking multiple inodes.
112         locker() sync.Locker
113
114         // throttle for limiting concurrent background writers
115         throttle() *throttle
116
117         // create a new node with nil parent.
118         newNode(name string, perm os.FileMode, modTime time.Time) (node inode, err error)
119
120         // analogous to os.Stat()
121         Stat(name string) (os.FileInfo, error)
122
123         // analogous to os.Create(): create/truncate a file and open it O_RDWR.
124         Create(name string) (File, error)
125
126         // Like os.OpenFile(): create or open a file or directory.
127         //
128         // If flag&os.O_EXCL==0, it opens an existing file or
129         // directory if one exists. If flag&os.O_CREATE!=0, it creates
130         // a new empty file or directory if one does not already
131         // exist.
132         //
133         // When creating a new item, perm&os.ModeDir determines
134         // whether it is a file or a directory.
135         //
136         // A file can be opened multiple times and used concurrently
137         // from multiple goroutines. However, each File object should
138         // be used by only one goroutine at a time.
139         OpenFile(name string, flag int, perm os.FileMode) (File, error)
140
141         Mkdir(name string, perm os.FileMode) error
142         Remove(name string) error
143         RemoveAll(name string) error
144         Rename(oldname, newname string) error
145
146         // Write buffered data from memory to storage, returning when
147         // all updates have been saved to persistent storage.
148         Sync() error
149
150         // Write buffered data from memory to storage, but don't wait
151         // for all writes to finish before returning. If shortBlocks
152         // is true, flush everything; otherwise, if there's less than
153         // a full block of buffered data at the end of a stream, leave
154         // it buffered in memory in case more data can be appended. If
155         // path is "", flush all dirs/streams; otherwise, flush only
156         // the specified dir/stream.
157         Flush(path string, shortBlocks bool) error
158
159         // Estimate current memory usage.
160         MemorySize() int64
161 }
162
163 type fsFS struct {
164         FileSystem
165 }
166
167 // FS returns an fs.FS interface to the given FileSystem, to enable
168 // the use of fs.WalkDir, etc.
169 func FS(fs FileSystem) fs.FS { return fsFS{fs} }
170 func (fs fsFS) Open(path string) (fs.File, error) {
171         f, err := fs.FileSystem.Open(path)
172         return f, err
173 }
174
175 type inode interface {
176         SetParent(parent inode, name string)
177         Parent() inode
178         FS() FileSystem
179         Read([]byte, filenodePtr) (int, filenodePtr, error)
180         Write([]byte, filenodePtr) (int, filenodePtr, error)
181         Truncate(int64) error
182         IsDir() bool
183         Readdir() ([]os.FileInfo, error)
184         Size() int64
185         FileInfo() os.FileInfo
186         // Create a snapshot of this node and its descendants.
187         Snapshot() (inode, error)
188         // Replace this node with a copy of the provided snapshot.
189         // Caller may provide the same snapshot to multiple Splice
190         // calls, but must not modify the snapshot concurrently.
191         Splice(inode) error
192
193         // Child() performs lookups and updates of named child nodes.
194         //
195         // (The term "child" here is used strictly. This means name is
196         // not "." or "..", and name does not contain "/".)
197         //
198         // If replace is non-nil, Child calls replace(x) where x is
199         // the current child inode with the given name. If possible,
200         // the child inode is replaced with the one returned by
201         // replace().
202         //
203         // If replace(x) returns an inode (besides x or nil) that is
204         // subsequently returned by Child(), then Child()'s caller
205         // must ensure the new child's name and parent are set/updated
206         // to Child()'s name argument and its receiver respectively.
207         // This is not necessarily done before replace(x) returns, but
208         // it must be done before Child()'s caller releases the
209         // parent's lock.
210         //
211         // Nil represents "no child". replace(nil) signifies that no
212         // child with this name exists yet. If replace() returns nil,
213         // the existing child should be deleted if possible.
214         //
215         // An implementation of Child() is permitted to ignore
216         // replace() or its return value. For example, a regular file
217         // inode does not have children, so Child() always returns
218         // nil.
219         //
220         // Child() returns the child, if any, with the given name: if
221         // a child was added or changed, the new child is returned.
222         //
223         // Caller must have lock (or rlock if replace is nil).
224         Child(name string, replace func(inode) (inode, error)) (inode, error)
225
226         sync.Locker
227         RLock()
228         RUnlock()
229         MemorySize() int64
230 }
231
232 type fileinfo struct {
233         name    string
234         mode    os.FileMode
235         size    int64
236         modTime time.Time
237 }
238
239 // Name implements os.FileInfo.
240 func (fi fileinfo) Name() string {
241         return fi.name
242 }
243
244 // ModTime implements os.FileInfo.
245 func (fi fileinfo) ModTime() time.Time {
246         return fi.modTime
247 }
248
249 // Mode implements os.FileInfo.
250 func (fi fileinfo) Mode() os.FileMode {
251         return fi.mode
252 }
253
254 // IsDir implements os.FileInfo.
255 func (fi fileinfo) IsDir() bool {
256         return fi.mode&os.ModeDir != 0
257 }
258
259 // Size implements os.FileInfo.
260 func (fi fileinfo) Size() int64 {
261         return fi.size
262 }
263
264 // Sys implements os.FileInfo.
265 func (fi fileinfo) Sys() interface{} {
266         return nil
267 }
268
269 type nullnode struct{}
270
271 func (*nullnode) Mkdir(string, os.FileMode) error {
272         return ErrInvalidOperation
273 }
274
275 func (*nullnode) Read([]byte, filenodePtr) (int, filenodePtr, error) {
276         return 0, filenodePtr{}, ErrInvalidOperation
277 }
278
279 func (*nullnode) Write([]byte, filenodePtr) (int, filenodePtr, error) {
280         return 0, filenodePtr{}, ErrInvalidOperation
281 }
282
283 func (*nullnode) Truncate(int64) error {
284         return ErrInvalidOperation
285 }
286
287 func (*nullnode) FileInfo() os.FileInfo {
288         return fileinfo{}
289 }
290
291 func (*nullnode) IsDir() bool {
292         return false
293 }
294
295 func (*nullnode) Readdir() ([]os.FileInfo, error) {
296         return nil, ErrInvalidOperation
297 }
298
299 func (*nullnode) Child(name string, replace func(inode) (inode, error)) (inode, error) {
300         return nil, ErrNotADirectory
301 }
302
303 func (*nullnode) MemorySize() int64 {
304         // Types that embed nullnode should report their own size, but
305         // if they don't, we at least report a non-zero size to ensure
306         // a large tree doesn't get reported as 0 bytes.
307         return 64
308 }
309
310 func (*nullnode) Snapshot() (inode, error) {
311         return nil, ErrInvalidOperation
312 }
313
314 func (*nullnode) Splice(inode) error {
315         return ErrInvalidOperation
316 }
317
318 type treenode struct {
319         fs       FileSystem
320         parent   inode
321         inodes   map[string]inode
322         fileinfo fileinfo
323         sync.RWMutex
324         nullnode
325 }
326
327 func (n *treenode) FS() FileSystem {
328         return n.fs
329 }
330
331 func (n *treenode) SetParent(p inode, name string) {
332         n.Lock()
333         defer n.Unlock()
334         n.parent = p
335         n.fileinfo.name = name
336 }
337
338 func (n *treenode) Parent() inode {
339         n.RLock()
340         defer n.RUnlock()
341         return n.parent
342 }
343
344 func (n *treenode) IsDir() bool {
345         return true
346 }
347
348 func (n *treenode) Child(name string, replace func(inode) (inode, error)) (child inode, err error) {
349         debugPanicIfNotLocked(n, false)
350         child = n.inodes[name]
351         if name == "" || name == "." || name == ".." {
352                 err = ErrInvalidArgument
353                 return
354         }
355         if replace == nil {
356                 return
357         }
358         newchild, err := replace(child)
359         if err != nil {
360                 return
361         }
362         if newchild == nil {
363                 debugPanicIfNotLocked(n, true)
364                 delete(n.inodes, name)
365         } else if newchild != child {
366                 debugPanicIfNotLocked(n, true)
367                 n.inodes[name] = newchild
368                 n.fileinfo.modTime = time.Now()
369                 child = newchild
370         }
371         return
372 }
373
374 func (n *treenode) Size() int64 {
375         return n.FileInfo().Size()
376 }
377
378 func (n *treenode) FileInfo() os.FileInfo {
379         n.Lock()
380         defer n.Unlock()
381         n.fileinfo.size = int64(len(n.inodes))
382         return n.fileinfo
383 }
384
385 func (n *treenode) Readdir() (fi []os.FileInfo, err error) {
386         n.RLock()
387         defer n.RUnlock()
388         fi = make([]os.FileInfo, 0, len(n.inodes))
389         for _, inode := range n.inodes {
390                 fi = append(fi, inode.FileInfo())
391         }
392         return
393 }
394
395 func (n *treenode) Sync() error {
396         n.RLock()
397         defer n.RUnlock()
398         for _, inode := range n.inodes {
399                 syncer, ok := inode.(syncer)
400                 if !ok {
401                         return ErrInvalidOperation
402                 }
403                 err := syncer.Sync()
404                 if err != nil {
405                         return err
406                 }
407         }
408         return nil
409 }
410
411 func (n *treenode) MemorySize() (size int64) {
412         n.RLock()
413         defer n.RUnlock()
414         debugPanicIfNotLocked(n, false)
415         for _, inode := range n.inodes {
416                 size += inode.MemorySize()
417         }
418         return
419 }
420
421 type fileSystem struct {
422         root inode
423         fsBackend
424         mutex sync.Mutex
425         thr   *throttle
426 }
427
428 func (fs *fileSystem) rootnode() inode {
429         return fs.root
430 }
431
432 func (fs *fileSystem) throttle() *throttle {
433         return fs.thr
434 }
435
436 func (fs *fileSystem) locker() sync.Locker {
437         return &fs.mutex
438 }
439
440 // OpenFile is analogous to os.OpenFile().
441 func (fs *fileSystem) OpenFile(name string, flag int, perm os.FileMode) (File, error) {
442         return fs.openFile(name, flag, perm)
443 }
444
445 func (fs *fileSystem) openFile(name string, flag int, perm os.FileMode) (*filehandle, error) {
446         if flag&os.O_SYNC != 0 {
447                 return nil, ErrSyncNotSupported
448         }
449         dirname, name := path.Split(name)
450         parent, err := rlookup(fs.root, dirname)
451         if err != nil {
452                 return nil, err
453         }
454         var readable, writable bool
455         switch flag & (os.O_RDWR | os.O_RDONLY | os.O_WRONLY) {
456         case os.O_RDWR:
457                 readable = true
458                 writable = true
459         case os.O_RDONLY:
460                 readable = true
461         case os.O_WRONLY:
462                 writable = true
463         default:
464                 return nil, fmt.Errorf("invalid flags 0x%x", flag)
465         }
466         if parent.IsDir() {
467                 // A directory can be opened via "foo/", "foo/.", or
468                 // "foo/..".
469                 switch name {
470                 case ".", "":
471                         return &filehandle{inode: parent, readable: readable, writable: writable}, nil
472                 case "..":
473                         return &filehandle{inode: parent.Parent(), readable: readable, writable: writable}, nil
474                 }
475         }
476         createMode := flag&os.O_CREATE != 0
477         // We always need to take Lock() here, not just RLock(). Even
478         // if we know we won't be creating a file, parent might be a
479         // lookupnode, which sometimes populates its inodes map during
480         // a Child() call.
481         parent.Lock()
482         defer parent.Unlock()
483         n, err := parent.Child(name, nil)
484         if err != nil {
485                 return nil, err
486         } else if n == nil {
487                 if !createMode {
488                         return nil, os.ErrNotExist
489                 }
490                 n, err = parent.Child(name, func(inode) (repl inode, err error) {
491                         repl, err = parent.FS().newNode(name, perm|0755, time.Now())
492                         if err != nil {
493                                 return
494                         }
495                         repl.SetParent(parent, name)
496                         return
497                 })
498                 if err != nil {
499                         return nil, err
500                 } else if n == nil {
501                         // Parent rejected new child, but returned no error
502                         return nil, ErrInvalidArgument
503                 }
504         } else if flag&os.O_EXCL != 0 {
505                 return nil, ErrFileExists
506         } else if flag&os.O_TRUNC != 0 {
507                 if !writable {
508                         return nil, fmt.Errorf("invalid flag O_TRUNC in read-only mode")
509                 } else if n.IsDir() {
510                         return nil, fmt.Errorf("invalid flag O_TRUNC when opening directory")
511                 } else if err := n.Truncate(0); err != nil {
512                         return nil, err
513                 }
514         }
515         return &filehandle{
516                 inode:    n,
517                 append:   flag&os.O_APPEND != 0,
518                 readable: readable,
519                 writable: writable,
520         }, nil
521 }
522
523 func (fs *fileSystem) Open(name string) (http.File, error) {
524         return fs.OpenFile(name, os.O_RDONLY, 0)
525 }
526
527 func (fs *fileSystem) Create(name string) (File, error) {
528         return fs.OpenFile(name, os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0)
529 }
530
531 func (fs *fileSystem) Mkdir(name string, perm os.FileMode) error {
532         dirname, name := path.Split(name)
533         n, err := rlookup(fs.root, dirname)
534         if err != nil {
535                 return err
536         }
537         n.Lock()
538         defer n.Unlock()
539         if child, err := n.Child(name, nil); err != nil {
540                 return err
541         } else if child != nil {
542                 return os.ErrExist
543         }
544
545         _, err = n.Child(name, func(inode) (repl inode, err error) {
546                 repl, err = n.FS().newNode(name, perm|os.ModeDir, time.Now())
547                 if err != nil {
548                         return
549                 }
550                 repl.SetParent(n, name)
551                 return
552         })
553         return err
554 }
555
556 func (fs *fileSystem) Stat(name string) (os.FileInfo, error) {
557         node, err := rlookup(fs.root, name)
558         if err != nil {
559                 return nil, err
560         }
561         return node.FileInfo(), nil
562 }
563
564 func (fs *fileSystem) Rename(oldname, newname string) error {
565         olddir, oldname := path.Split(oldname)
566         if oldname == "" || oldname == "." || oldname == ".." {
567                 return ErrInvalidArgument
568         }
569         olddirf, err := fs.openFile(olddir+".", os.O_RDONLY, 0)
570         if err != nil {
571                 return fmt.Errorf("%q: %s", olddir, err)
572         }
573         defer olddirf.Close()
574
575         newdir, newname := path.Split(newname)
576         if newname == "." || newname == ".." {
577                 return ErrInvalidArgument
578         } else if newname == "" {
579                 // Rename("a/b", "c/") means Rename("a/b", "c/b")
580                 newname = oldname
581         }
582         newdirf, err := fs.openFile(newdir+".", os.O_RDONLY, 0)
583         if err != nil {
584                 return fmt.Errorf("%q: %s", newdir, err)
585         }
586         defer newdirf.Close()
587
588         // TODO: If the nearest common ancestor ("nca") of olddirf and
589         // newdirf is on a different filesystem than fs, we should
590         // call nca.FS().Rename() instead of proceeding. Until then
591         // it's awkward for filesystems to implement their own Rename
592         // methods effectively: the only one that runs is the one on
593         // the root FileSystem exposed to the caller (webdav, fuse,
594         // etc).
595
596         // When acquiring locks on multiple inodes, avoid deadlock by
597         // locking the entire containing filesystem first.
598         cfs := olddirf.inode.FS()
599         cfs.locker().Lock()
600         defer cfs.locker().Unlock()
601
602         if cfs != newdirf.inode.FS() {
603                 // Moving inodes across filesystems is not (yet)
604                 // supported. Locking inodes from different
605                 // filesystems could deadlock, so we must error out
606                 // now.
607                 return ErrInvalidOperation
608         }
609
610         // To ensure we can test reliably whether we're about to move
611         // a directory into itself, lock all potential common
612         // ancestors of olddir and newdir.
613         needLock := []sync.Locker{}
614         for _, node := range []inode{olddirf.inode, newdirf.inode} {
615                 needLock = append(needLock, node)
616                 for node.Parent() != node && node.Parent().FS() == node.FS() {
617                         node = node.Parent()
618                         needLock = append(needLock, node)
619                 }
620         }
621         locked := map[sync.Locker]bool{}
622         for i := len(needLock) - 1; i >= 0; i-- {
623                 if n := needLock[i]; !locked[n] {
624                         n.Lock()
625                         defer n.Unlock()
626                         locked[n] = true
627                 }
628         }
629
630         _, err = olddirf.inode.Child(oldname, func(oldinode inode) (inode, error) {
631                 if oldinode == nil {
632                         return oldinode, os.ErrNotExist
633                 }
634                 if locked[oldinode] {
635                         // oldinode cannot become a descendant of itself.
636                         return oldinode, ErrInvalidArgument
637                 }
638                 if oldinode.FS() != cfs && newdirf.inode != olddirf.inode {
639                         // moving a mount point to a different parent
640                         // is not (yet) supported.
641                         return oldinode, ErrInvalidArgument
642                 }
643                 accepted, err := newdirf.inode.Child(newname, func(existing inode) (inode, error) {
644                         if existing != nil && existing.IsDir() {
645                                 return existing, ErrIsDirectory
646                         }
647                         return oldinode, nil
648                 })
649                 if err != nil {
650                         // Leave oldinode in olddir.
651                         return oldinode, err
652                 }
653                 accepted.SetParent(newdirf.inode, newname)
654                 return nil, nil
655         })
656         return err
657 }
658
659 func (fs *fileSystem) Remove(name string) error {
660         return fs.remove(strings.TrimRight(name, "/"), false)
661 }
662
663 func (fs *fileSystem) RemoveAll(name string) error {
664         err := fs.remove(strings.TrimRight(name, "/"), true)
665         if os.IsNotExist(err) {
666                 // "If the path does not exist, RemoveAll returns
667                 // nil." (see "os" pkg)
668                 err = nil
669         }
670         return err
671 }
672
673 func (fs *fileSystem) remove(name string, recursive bool) error {
674         dirname, name := path.Split(name)
675         if name == "" || name == "." || name == ".." {
676                 return ErrInvalidArgument
677         }
678         dir, err := rlookup(fs.root, dirname)
679         if err != nil {
680                 return err
681         }
682         dir.Lock()
683         defer dir.Unlock()
684         _, err = dir.Child(name, func(node inode) (inode, error) {
685                 if node == nil {
686                         return nil, os.ErrNotExist
687                 }
688                 if !recursive && node.IsDir() && node.Size() > 0 {
689                         return node, ErrDirectoryNotEmpty
690                 }
691                 return nil, nil
692         })
693         return err
694 }
695
696 func (fs *fileSystem) Sync() error {
697         if syncer, ok := fs.root.(syncer); ok {
698                 return syncer.Sync()
699         }
700         return ErrInvalidOperation
701 }
702
703 func (fs *fileSystem) Flush(string, bool) error {
704         log.Printf("TODO: flush fileSystem")
705         return ErrInvalidOperation
706 }
707
708 func (fs *fileSystem) MemorySize() int64 {
709         return fs.root.MemorySize()
710 }
711
712 // rlookup (recursive lookup) returns the inode for the file/directory
713 // with the given name (which may contain "/" separators). If no such
714 // file/directory exists, the returned node is nil.
715 func rlookup(start inode, path string) (node inode, err error) {
716         node = start
717         for _, name := range strings.Split(path, "/") {
718                 if node.IsDir() {
719                         if name == "." || name == "" {
720                                 continue
721                         }
722                         if name == ".." {
723                                 node = node.Parent()
724                                 continue
725                         }
726                 }
727                 node, err = func() (inode, error) {
728                         node.Lock()
729                         defer node.Unlock()
730                         return node.Child(name, nil)
731                 }()
732                 if node == nil || err != nil {
733                         break
734                 }
735         }
736         if node == nil && err == nil {
737                 err = os.ErrNotExist
738         }
739         return
740 }
741
742 func permittedName(name string) bool {
743         return name != "" && name != "." && name != ".." && !strings.Contains(name, "/")
744 }
745
746 // Snapshot returns a Subtree that's a copy of the given path. It
747 // returns an error if the path is not inside a collection.
748 func Snapshot(fs FileSystem, path string) (*Subtree, error) {
749         f, err := fs.OpenFile(path, os.O_RDONLY, 0)
750         if err != nil {
751                 return nil, err
752         }
753         defer f.Close()
754         return f.Snapshot()
755 }
756
757 // Splice inserts newsubtree at the indicated target path.
758 //
759 // Splice returns an error if target is not inside a collection.
760 //
761 // Splice returns an error if target is the root of a collection and
762 // newsubtree is a snapshot of a file.
763 func Splice(fs FileSystem, target string, newsubtree *Subtree) error {
764         f, err := fs.OpenFile(target, os.O_WRONLY, 0)
765         if os.IsNotExist(err) {
766                 f, err = fs.OpenFile(target, os.O_CREATE|os.O_WRONLY, 0700)
767         }
768         if err != nil {
769                 return fmt.Errorf("open %s: %w", target, err)
770         }
771         defer f.Close()
772         return f.Splice(newsubtree)
773 }