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