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