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