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