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         "path/filepath"
  17         "strings"
  18         "sync"
  19         "time"
  20 )
  21
  22 var (
  23         ErrReadOnlyFile      = errors.New("read-only file")
  24         ErrNegativeOffset    = errors.New("cannot seek to negative offset")
  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         // If not nil, sys() returns the source data structure, which
 238         // can be a *Collection, *Group, or nil. Currently populated
 239         // only for project dirs and top-level collection dirs. Does
 240         // not stay up to date with upstream changes.
 241         //
 242         // Intended to support keep-web's properties-as-s3-metadata
 243         // feature (https://dev.arvados.org/issues/19088).
 244         sys func() interface{}
 245 }
 246
 247 // Name implements os.FileInfo.
 248 func (fi fileinfo) Name() string {
 249         return fi.name
 250 }
 251
 252 // ModTime implements os.FileInfo.
 253 func (fi fileinfo) ModTime() time.Time {
 254         return fi.modTime
 255 }
 256
 257 // Mode implements os.FileInfo.
 258 func (fi fileinfo) Mode() os.FileMode {
 259         return fi.mode
 260 }
 261
 262 // IsDir implements os.FileInfo.
 263 func (fi fileinfo) IsDir() bool {
 264         return fi.mode&os.ModeDir != 0
 265 }
 266
 267 // Size implements os.FileInfo.
 268 func (fi fileinfo) Size() int64 {
 269         return fi.size
 270 }
 271
 272 // Sys implements os.FileInfo. See comment in fileinfo struct.
 273 func (fi fileinfo) Sys() interface{} {
 274         if fi.sys == nil {
 275                 return nil
 276         }
 277         return fi.sys()
 278 }
 279
 280 type nullnode struct{}
 281
 282 func (*nullnode) Mkdir(string, os.FileMode) error {
 283         return ErrInvalidOperation
 284 }
 285
 286 func (*nullnode) Read([]byte, filenodePtr) (int, filenodePtr, error) {
 287         return 0, filenodePtr{}, ErrInvalidOperation
 288 }
 289
 290 func (*nullnode) Write([]byte, filenodePtr) (int, filenodePtr, error) {
 291         return 0, filenodePtr{}, ErrInvalidOperation
 292 }
 293
 294 func (*nullnode) Truncate(int64) error {
 295         return ErrInvalidOperation
 296 }
 297
 298 func (*nullnode) FileInfo() os.FileInfo {
 299         return fileinfo{}
 300 }
 301
 302 func (*nullnode) IsDir() bool {
 303         return false
 304 }
 305
 306 func (*nullnode) Readdir() ([]os.FileInfo, error) {
 307         return nil, ErrInvalidOperation
 308 }
 309
 310 func (*nullnode) Child(name string, replace func(inode) (inode, error)) (inode, error) {
 311         return nil, ErrNotADirectory
 312 }
 313
 314 func (*nullnode) MemorySize() int64 {
 315         // Types that embed nullnode should report their own size, but
 316         // if they don't, we at least report a non-zero size to ensure
 317         // a large tree doesn't get reported as 0 bytes.
 318         return 64
 319 }
 320
 321 func (*nullnode) Snapshot() (inode, error) {
 322         return nil, ErrInvalidOperation
 323 }
 324
 325 func (*nullnode) Splice(inode) error {
 326         return ErrInvalidOperation
 327 }
 328
 329 type treenode struct {
 330         fs       FileSystem
 331         parent   inode
 332         inodes   map[string]inode
 333         fileinfo fileinfo
 334         sync.RWMutex
 335         nullnode
 336 }
 337
 338 func (n *treenode) FS() FileSystem {
 339         return n.fs
 340 }
 341
 342 func (n *treenode) SetParent(p inode, name string) {
 343         n.Lock()
 344         defer n.Unlock()
 345         n.parent = p
 346         n.fileinfo.name = name
 347 }
 348
 349 func (n *treenode) Parent() inode {
 350         n.RLock()
 351         defer n.RUnlock()
 352         return n.parent
 353 }
 354
 355 func (n *treenode) IsDir() bool {
 356         return true
 357 }
 358
 359 func (n *treenode) Child(name string, replace func(inode) (inode, error)) (child inode, err error) {
 360         debugPanicIfNotLocked(n, false)
 361         child = n.inodes[name]
 362         if name == "" || name == "." || name == ".." {
 363                 err = ErrInvalidArgument
 364                 return
 365         }
 366         if replace == nil {
 367                 return
 368         }
 369         newchild, err := replace(child)
 370         if err != nil {
 371                 return
 372         }
 373         if newchild == nil {
 374                 debugPanicIfNotLocked(n, true)
 375                 delete(n.inodes, name)
 376         } else if newchild != child {
 377                 debugPanicIfNotLocked(n, true)
 378                 n.inodes[name] = newchild
 379                 n.fileinfo.modTime = time.Now()
 380                 child = newchild
 381         }
 382         return
 383 }
 384
 385 func (n *treenode) Size() int64 {
 386         return n.FileInfo().Size()
 387 }
 388
 389 func (n *treenode) FileInfo() os.FileInfo {
 390         n.RLock()
 391         defer n.RUnlock()
 392         fi := n.fileinfo
 393         fi.size = int64(len(n.inodes))
 394         return fi
 395 }
 396
 397 func (n *treenode) Readdir() (fi []os.FileInfo, err error) {
 398         // We need RLock to safely read n.inodes, but we must release
 399         // it before calling FileInfo() on the child nodes. Otherwise,
 400         // we risk deadlock when filter groups A and B match each
 401         // other, concurrent Readdir() calls try to RLock them in
 402         // opposite orders, and one cannot be RLocked a second time
 403         // because a third caller is waiting for a write lock.
 404         n.RLock()
 405         inodes := make([]inode, 0, len(n.inodes))
 406         for _, inode := range n.inodes {
 407                 inodes = append(inodes, inode)
 408         }
 409         n.RUnlock()
 410         fi = make([]os.FileInfo, 0, len(inodes))
 411         for _, inode := range inodes {
 412                 fi = append(fi, inode.FileInfo())
 413         }
 414         return
 415 }
 416
 417 func (n *treenode) Sync() error {
 418         n.RLock()
 419         defer n.RUnlock()
 420         for _, inode := range n.inodes {
 421                 syncer, ok := inode.(syncer)
 422                 if !ok {
 423                         return ErrInvalidOperation
 424                 }
 425                 err := syncer.Sync()
 426                 if err != nil {
 427                         return err
 428                 }
 429         }
 430         return nil
 431 }
 432
 433 func (n *treenode) MemorySize() (size int64) {
 434         // To avoid making other callers wait while we count the
 435         // entire filesystem size, we lock the node only long enough
 436         // to copy the list of children. We accept that the resulting
 437         // size will sometimes be misleading (e.g., we will
 438         // double-count an item that moves from A to B after we check
 439         // A's size but before we check B's size).
 440         n.RLock()
 441         debugPanicIfNotLocked(n, false)
 442         todo := make([]inode, 0, len(n.inodes))
 443         for _, inode := range n.inodes {
 444                 todo = append(todo, inode)
 445         }
 446         n.RUnlock()
 447         for _, inode := range todo {
 448                 size += inode.MemorySize()
 449         }
 450         return 64 + size
 451 }
 452
 453 type fileSystem struct {
 454         root inode
 455         fsBackend
 456         mutex sync.Mutex
 457         thr   *throttle
 458 }
 459
 460 func (fs *fileSystem) rootnode() inode {
 461         return fs.root
 462 }
 463
 464 func (fs *fileSystem) throttle() *throttle {
 465         return fs.thr
 466 }
 467
 468 func (fs *fileSystem) locker() sync.Locker {
 469         return &fs.mutex
 470 }
 471
 472 // OpenFile is analogous to os.OpenFile().
 473 func (fs *fileSystem) OpenFile(name string, flag int, perm os.FileMode) (File, error) {
 474         return fs.openFile(name, flag, perm)
 475 }
 476
 477 func (fs *fileSystem) openFile(name string, flag int, perm os.FileMode) (*filehandle, error) {
 478         if flag&os.O_SYNC != 0 {
 479                 return nil, ErrSyncNotSupported
 480         }
 481         dirname, name := path.Split(name)
 482         ancestors := map[inode]bool{}
 483         parent, err := rlookup(fs.root, dirname, ancestors)
 484         if err != nil {
 485                 return nil, err
 486         }
 487         var readable, writable bool
 488         switch flag & (os.O_RDWR | os.O_RDONLY | os.O_WRONLY) {
 489         case os.O_RDWR:
 490                 readable = true
 491                 writable = true
 492         case os.O_RDONLY:
 493                 readable = true
 494         case os.O_WRONLY:
 495                 writable = true
 496         default:
 497                 return nil, fmt.Errorf("invalid flags 0x%x", flag)
 498         }
 499         if parent.IsDir() {
 500                 // A directory can be opened via "foo/", "foo/.", or
 501                 // "foo/..".
 502                 switch name {
 503                 case ".", "":
 504                         return &filehandle{inode: parent, readable: readable, writable: writable}, nil
 505                 case "..":
 506                         return &filehandle{inode: parent.Parent(), readable: readable, writable: writable}, nil
 507                 }
 508         }
 509         createMode := flag&os.O_CREATE != 0
 510         // We always need to take Lock() here, not just RLock(). Even
 511         // if we know we won't be creating a file, parent might be a
 512         // lookupnode, which sometimes populates its inodes map during
 513         // a Child() call.
 514         parent.Lock()
 515         defer parent.Unlock()
 516         n, err := parent.Child(name, nil)
 517         if err != nil {
 518                 return nil, err
 519         } else if n == nil {
 520                 if !createMode {
 521                         return nil, os.ErrNotExist
 522                 }
 523                 n, err = parent.Child(name, func(inode) (repl inode, err error) {
 524                         repl, err = parent.FS().newNode(name, perm|0755, time.Now())
 525                         if err != nil {
 526                                 return
 527                         }
 528                         repl.SetParent(parent, name)
 529                         return
 530                 })
 531                 if err != nil {
 532                         return nil, err
 533                 } else if n == nil {
 534                         // Parent rejected new child, but returned no error
 535                         return nil, ErrInvalidArgument
 536                 }
 537         } else if flag&os.O_EXCL != 0 {
 538                 return nil, os.ErrExist
 539         } else if flag&os.O_TRUNC != 0 {
 540                 if !writable {
 541                         return nil, fmt.Errorf("invalid flag O_TRUNC in read-only mode")
 542                 } else if n.IsDir() {
 543                         return nil, fmt.Errorf("invalid flag O_TRUNC when opening directory")
 544                 } else if err := n.Truncate(0); err != nil {
 545                         return nil, err
 546                 }
 547         }
 548         // If n and one of its parents/ancestors are [hardlinks to]
 549         // the same node (e.g., a filter group that matches itself),
 550         // open an "empty directory" node instead, so the inner
 551         // hardlink appears empty. This is needed to ensure
 552         // Open("a/b/c/x/x").Readdir() appears empty, matching the
 553         // behavior of rlookup("a/b/c/x/x/z") => ErrNotExist.
 554         if hl, ok := n.(*hardlink); (ok && ancestors[hl.inode]) || ancestors[n] {
 555                 n = &treenode{
 556                         fs:     n.FS(),
 557                         parent: parent,
 558                         inodes: nil,
 559                         fileinfo: fileinfo{
 560                                 name:    name,
 561                                 modTime: time.Now(),
 562                                 mode:    0555 | os.ModeDir,
 563                         },
 564                 }
 565         }
 566         return &filehandle{
 567                 inode:    n,
 568                 append:   flag&os.O_APPEND != 0,
 569                 readable: readable,
 570                 writable: writable,
 571         }, nil
 572 }
 573
 574 func (fs *fileSystem) Open(name string) (http.File, error) {
 575         return fs.OpenFile(name, os.O_RDONLY, 0)
 576 }
 577
 578 func (fs *fileSystem) Create(name string) (File, error) {
 579         return fs.OpenFile(name, os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0)
 580 }
 581
 582 func (fs *fileSystem) Mkdir(name string, perm os.FileMode) error {
 583         dirname, name := path.Split(name)
 584         n, err := rlookup(fs.root, dirname, nil)
 585         if err != nil {
 586                 return err
 587         }
 588         n.Lock()
 589         defer n.Unlock()
 590         if child, err := n.Child(name, nil); err != nil {
 591                 return err
 592         } else if child != nil {
 593                 return os.ErrExist
 594         }
 595
 596         _, err = n.Child(name, func(inode) (repl inode, err error) {
 597                 repl, err = n.FS().newNode(name, perm|os.ModeDir, time.Now())
 598                 if err != nil {
 599                         return
 600                 }
 601                 repl.SetParent(n, name)
 602                 return
 603         })
 604         return err
 605 }
 606
 607 func (fs *fileSystem) Stat(name string) (os.FileInfo, error) {
 608         node, err := rlookup(fs.root, name, nil)
 609         if err != nil {
 610                 return nil, err
 611         }
 612         return node.FileInfo(), nil
 613 }
 614
 615 func (fs *fileSystem) Rename(oldname, newname string) error {
 616         olddir, oldname := path.Split(oldname)
 617         if oldname == "" || oldname == "." || oldname == ".." {
 618                 return ErrInvalidArgument
 619         }
 620         olddirf, err := fs.openFile(olddir+".", os.O_RDONLY, 0)
 621         if err != nil {
 622                 return fmt.Errorf("%q: %s", olddir, err)
 623         }
 624         defer olddirf.Close()
 625
 626         newdir, newname := path.Split(newname)
 627         if newname == "." || newname == ".." {
 628                 return ErrInvalidArgument
 629         } else if newname == "" {
 630                 // Rename("a/b", "c/") means Rename("a/b", "c/b")
 631                 newname = oldname
 632         }
 633         newdirf, err := fs.openFile(newdir+".", os.O_RDONLY, 0)
 634         if err != nil {
 635                 return fmt.Errorf("%q: %s", newdir, err)
 636         }
 637         defer newdirf.Close()
 638
 639         // TODO: If the nearest common ancestor ("nca") of olddirf and
 640         // newdirf is on a different filesystem than fs, we should
 641         // call nca.FS().Rename() instead of proceeding. Until then
 642         // it's awkward for filesystems to implement their own Rename
 643         // methods effectively: the only one that runs is the one on
 644         // the root FileSystem exposed to the caller (webdav, fuse,
 645         // etc).
 646
 647         // When acquiring locks on multiple inodes, avoid deadlock by
 648         // locking the entire containing filesystem first.
 649         cfs := olddirf.inode.FS()
 650         cfs.locker().Lock()
 651         defer cfs.locker().Unlock()
 652
 653         if cfs != newdirf.inode.FS() {
 654                 // Moving inodes across filesystems is not (yet)
 655                 // supported. Locking inodes from different
 656                 // filesystems could deadlock, so we must error out
 657                 // now.
 658                 return ErrInvalidOperation
 659         }
 660
 661         // To ensure we can test reliably whether we're about to move
 662         // a directory into itself, lock all potential common
 663         // ancestors of olddir and newdir.
 664         needLock := []sync.Locker{}
 665         for _, node := range []inode{olddirf.inode, newdirf.inode} {
 666                 needLock = append(needLock, node)
 667                 for node.Parent() != node && node.Parent().FS() == node.FS() {
 668                         node = node.Parent()
 669                         needLock = append(needLock, node)
 670                 }
 671         }
 672         locked := map[sync.Locker]bool{}
 673         for i := len(needLock) - 1; i >= 0; i-- {
 674                 n := needLock[i]
 675                 if fs, ok := n.(interface{ rootnode() inode }); ok {
 676                         // Lock the fs's root dir directly, not
 677                         // through the fs. Otherwise our "locked" map
 678                         // would not reliably prevent double-locking
 679                         // the fs's root dir.
 680                         n = fs.rootnode()
 681                 }
 682                 if !locked[n] {
 683                         n.Lock()
 684                         defer n.Unlock()
 685                         locked[n] = true
 686                 }
 687         }
 688
 689         _, err = olddirf.inode.Child(oldname, func(oldinode inode) (inode, error) {
 690                 if oldinode == nil {
 691                         return oldinode, os.ErrNotExist
 692                 }
 693                 if locked[oldinode] {
 694                         // oldinode cannot become a descendant of itself.
 695                         return oldinode, ErrInvalidArgument
 696                 }
 697                 if oldinode.FS() != cfs && newdirf.inode != olddirf.inode {
 698                         // moving a mount point to a different parent
 699                         // is not (yet) supported.
 700                         return oldinode, ErrInvalidArgument
 701                 }
 702                 accepted, err := newdirf.inode.Child(newname, func(existing inode) (inode, error) {
 703                         if existing != nil && existing.IsDir() {
 704                                 return existing, ErrIsDirectory
 705                         }
 706                         return oldinode, nil
 707                 })
 708                 if err != nil {
 709                         // Leave oldinode in olddir.
 710                         return oldinode, err
 711                 }
 712                 accepted.SetParent(newdirf.inode, newname)
 713                 return nil, nil
 714         })
 715         return err
 716 }
 717
 718 func (fs *fileSystem) Remove(name string) error {
 719         return fs.remove(strings.TrimRight(name, "/"), false)
 720 }
 721
 722 func (fs *fileSystem) RemoveAll(name string) error {
 723         err := fs.remove(strings.TrimRight(name, "/"), true)
 724         if os.IsNotExist(err) {
 725                 // "If the path does not exist, RemoveAll returns
 726                 // nil." (see "os" pkg)
 727                 err = nil
 728         }
 729         return err
 730 }
 731
 732 func (fs *fileSystem) remove(name string, recursive bool) error {
 733         dirname, name := path.Split(name)
 734         if name == "" || name == "." || name == ".." {
 735                 return ErrInvalidArgument
 736         }
 737         dir, err := rlookup(fs.root, dirname, nil)
 738         if err != nil {
 739                 return err
 740         }
 741         dir.Lock()
 742         defer dir.Unlock()
 743         _, err = dir.Child(name, func(node inode) (inode, error) {
 744                 if node == nil {
 745                         return nil, os.ErrNotExist
 746                 }
 747                 if !recursive && node.IsDir() && node.Size() > 0 {
 748                         return node, ErrDirectoryNotEmpty
 749                 }
 750                 return nil, nil
 751         })
 752         return err
 753 }
 754
 755 func (fs *fileSystem) Sync() error {
 756         if syncer, ok := fs.root.(syncer); ok {
 757                 return syncer.Sync()
 758         }
 759         return ErrInvalidOperation
 760 }
 761
 762 func (fs *fileSystem) Flush(string, bool) error {
 763         log.Printf("TODO: flush fileSystem")
 764         return ErrInvalidOperation
 765 }
 766
 767 func (fs *fileSystem) MemorySize() int64 {
 768         return fs.root.MemorySize()
 769 }
 770
 771 // rlookup (recursive lookup) returns the inode for the file/directory
 772 // with the given name (which may contain "/" separators). If no such
 773 // file/directory exists, the returned node is nil.
 774 //
 775 // The visited map should be either nil or empty. If non-nil, all
 776 // nodes and hardlink targets visited by the given path will be added
 777 // to it.
 778 //
 779 // If a cycle is detected, the second occurrence of the offending node
 780 // will be replaced by an empty directory. For example, if "x" is a
 781 // filter group that matches itself, then rlookup("a/b/c/x") will
 782 // return the filter group, and rlookup("a/b/c/x/x") will return an
 783 // empty directory.
 784 func rlookup(start inode, path string, visited map[inode]bool) (node inode, err error) {
 785         if visited == nil {
 786                 visited = map[inode]bool{}
 787         }
 788         node = start
 789         // Clean up ./ and ../ and double-slashes, but (unlike
 790         // filepath.Clean) retain a trailing slash, because looking up
 791         // ".../regularfile/" should fail.
 792         trailingSlash := strings.HasSuffix(path, "/")
 793         path = filepath.Clean(path)
 794         if trailingSlash && path != "/" {
 795                 path += "/"
 796         }
 797         for _, name := range strings.Split(path, "/") {
 798                 visited[node] = true
 799                 if node.IsDir() {
 800                         if name == "." || name == "" {
 801                                 continue
 802                         }
 803                         if name == ".." {
 804                                 node = node.Parent()
 805                                 continue
 806                         }
 807                 }
 808                 node, err = func() (inode, error) {
 809                         node.Lock()
 810                         defer node.Unlock()
 811                         return node.Child(name, nil)
 812                 }()
 813                 if node == nil || err != nil {
 814                         break
 815                 }
 816                 checknode := node
 817                 if hardlinked, ok := checknode.(*hardlink); ok {
 818                         checknode = hardlinked.inode
 819                 }
 820                 if visited[checknode] {
 821                         node = &treenode{
 822                                 fs:     node.FS(),
 823                                 parent: node.Parent(),
 824                                 inodes: nil,
 825                                 fileinfo: fileinfo{
 826                                         name:    name,
 827                                         modTime: time.Now(),
 828                                         mode:    0555 | os.ModeDir,
 829                                 },
 830                         }
 831                 } else {
 832                         visited[checknode] = true
 833                 }
 834         }
 835         if node == nil && err == nil {
 836                 err = os.ErrNotExist
 837         }
 838         return
 839 }
 840
 841 func permittedName(name string) bool {
 842         return name != "" && name != "." && name != ".." && !strings.Contains(name, "/")
 843 }
 844
 845 // Snapshot returns a Subtree that's a copy of the given path. It
 846 // returns an error if the path is not inside a collection.
 847 func Snapshot(fs FileSystem, path string) (*Subtree, error) {
 848         f, err := fs.OpenFile(path, os.O_RDONLY, 0)
 849         if err != nil {
 850                 return nil, err
 851         }
 852         defer f.Close()
 853         return f.Snapshot()
 854 }
 855
 856 // Splice inserts newsubtree at the indicated target path.
 857 //
 858 // Splice returns an error if target is not inside a collection.
 859 //
 860 // Splice returns an error if target is the root of a collection and
 861 // newsubtree is a snapshot of a file.
 862 func Splice(fs FileSystem, target string, newsubtree *Subtree) error {
 863         f, err := fs.OpenFile(target, os.O_WRONLY, 0)
 864         if os.IsNotExist(err) {
 865                 f, err = fs.OpenFile(target, os.O_CREATE|os.O_WRONLY, 0700)
 866         }
 867         if err != nil {
 868                 return fmt.Errorf("open %s: %w", target, err)
 869         }
 870         defer f.Close()
 871         return f.Splice(newsubtree)
 872 }