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