sdk/go/arvados/collection_fs.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         "net/http"
  12         "os"
  13         "path"
  14         "regexp"
  15         "sort"
  16         "strconv"
  17         "strings"
  18         "sync"
  19         "time"
  20 )
  21
  22 var (
  23         ErrReadOnlyFile      = errors.New("read-only file")
  24         ErrNegativeOffset    = errors.New("cannot seek to negative offset")
  25         ErrFileExists        = errors.New("file exists")
  26         ErrInvalidOperation  = errors.New("invalid operation")
  27         ErrInvalidArgument   = errors.New("invalid argument")
  28         ErrDirectoryNotEmpty = errors.New("directory not empty")
  29         ErrWriteOnlyMode     = errors.New("file is O_WRONLY")
  30         ErrSyncNotSupported  = errors.New("O_SYNC flag is not supported")
  31         ErrIsDirectory       = errors.New("cannot rename file to overwrite existing directory")
  32         ErrPermission        = os.ErrPermission
  33
  34         maxBlockSize = 1 << 26
  35 )
  36
  37 // A File is an *os.File-like interface for reading and writing files
  38 // in a CollectionFileSystem.
  39 type File interface {
  40         io.Reader
  41         io.Writer
  42         io.Closer
  43         io.Seeker
  44         Size() int64
  45         Readdir(int) ([]os.FileInfo, error)
  46         Stat() (os.FileInfo, error)
  47         Truncate(int64) error
  48 }
  49
  50 type keepClient interface {
  51         ReadAt(locator string, p []byte, off int) (int, error)
  52         PutB(p []byte) (string, int, error)
  53 }
  54
  55 type fileinfo struct {
  56         name    string
  57         mode    os.FileMode
  58         size    int64
  59         modTime time.Time
  60 }
  61
  62 // Name implements os.FileInfo.
  63 func (fi fileinfo) Name() string {
  64         return fi.name
  65 }
  66
  67 // ModTime implements os.FileInfo.
  68 func (fi fileinfo) ModTime() time.Time {
  69         return fi.modTime
  70 }
  71
  72 // Mode implements os.FileInfo.
  73 func (fi fileinfo) Mode() os.FileMode {
  74         return fi.mode
  75 }
  76
  77 // IsDir implements os.FileInfo.
  78 func (fi fileinfo) IsDir() bool {
  79         return fi.mode&os.ModeDir != 0
  80 }
  81
  82 // Size implements os.FileInfo.
  83 func (fi fileinfo) Size() int64 {
  84         return fi.size
  85 }
  86
  87 // Sys implements os.FileInfo.
  88 func (fi fileinfo) Sys() interface{} {
  89         return nil
  90 }
  91
  92 // A FileSystem is an http.Filesystem plus Stat() and support for
  93 // opening writable files. All methods are safe to call from multiple
  94 // goroutines.
  95 type FileSystem interface {
  96         http.FileSystem
  97
  98         inode
  99
 100         // analogous to os.Stat()
 101         Stat(name string) (os.FileInfo, error)
 102
 103         // analogous to os.Create(): create/truncate a file and open it O_RDWR.
 104         Create(name string) (File, error)
 105
 106         // Like os.OpenFile(): create or open a file or directory.
 107         //
 108         // If flag&os.O_EXCL==0, it opens an existing file or
 109         // directory if one exists. If flag&os.O_CREATE!=0, it creates
 110         // a new empty file or directory if one does not already
 111         // exist.
 112         //
 113         // When creating a new item, perm&os.ModeDir determines
 114         // whether it is a file or a directory.
 115         //
 116         // A file can be opened multiple times and used concurrently
 117         // from multiple goroutines. However, each File object should
 118         // be used by only one goroutine at a time.
 119         OpenFile(name string, flag int, perm os.FileMode) (File, error)
 120
 121         Mkdir(name string, perm os.FileMode) error
 122         Remove(name string) error
 123         RemoveAll(name string) error
 124         Rename(oldname, newname string) error
 125 }
 126
 127 // A CollectionFileSystem is a FileSystem that can be serialized as a
 128 // manifest and stored as a collection.
 129 type CollectionFileSystem interface {
 130         FileSystem
 131
 132         // Flush all file data to Keep and return a snapshot of the
 133         // filesystem suitable for saving as (Collection)ManifestText.
 134         // Prefix (normally ".") is a top level directory, effectively
 135         // prepended to all paths in the returned manifest.
 136         MarshalManifest(prefix string) (string, error)
 137 }
 138
 139 type fileSystem struct {
 140         inode
 141 }
 142
 143 type collectionFileSystem struct {
 144         fileSystem
 145 }
 146
 147 func (fs collectionFileSystem) MarshalManifest(prefix string) (string, error) {
 148         fs.fileSystem.inode.Lock()
 149         defer fs.fileSystem.inode.Unlock()
 150         return fs.fileSystem.inode.(*dirnode).marshalManifest(prefix)
 151 }
 152
 153 // OpenFile is analogous to os.OpenFile().
 154 func (fs *fileSystem) OpenFile(name string, flag int, perm os.FileMode) (File, error) {
 155         return fs.openFile(name, flag, perm)
 156 }
 157
 158 func (fs *fileSystem) openFile(name string, flag int, perm os.FileMode) (*filehandle, error) {
 159         var dn inode = fs.inode
 160         if flag&os.O_SYNC != 0 {
 161                 return nil, ErrSyncNotSupported
 162         }
 163         dirname, name := path.Split(name)
 164         parent := rlookup(dn, dirname)
 165         if parent == nil {
 166                 return nil, os.ErrNotExist
 167         }
 168         var readable, writable bool
 169         switch flag & (os.O_RDWR | os.O_RDONLY | os.O_WRONLY) {
 170         case os.O_RDWR:
 171                 readable = true
 172                 writable = true
 173         case os.O_RDONLY:
 174                 readable = true
 175         case os.O_WRONLY:
 176                 writable = true
 177         default:
 178                 return nil, fmt.Errorf("invalid flags 0x%x", flag)
 179         }
 180         if !writable && parent.IsDir() {
 181                 // A directory can be opened via "foo/", "foo/.", or
 182                 // "foo/..".
 183                 switch name {
 184                 case ".", "":
 185                         return &filehandle{inode: parent}, nil
 186                 case "..":
 187                         return &filehandle{inode: parent.Parent()}, nil
 188                 }
 189         }
 190         createMode := flag&os.O_CREATE != 0
 191         if createMode {
 192                 parent.Lock()
 193                 defer parent.Unlock()
 194         } else {
 195                 parent.RLock()
 196                 defer parent.RUnlock()
 197         }
 198         n := parent.Child(name, nil)
 199         if n == nil {
 200                 if !createMode {
 201                         return nil, os.ErrNotExist
 202                 }
 203                 var err error
 204                 n = parent.Child(name, func(inode) inode {
 205                         var dn *dirnode
 206                         switch parent := parent.(type) {
 207                         case *dirnode:
 208                                 dn = parent
 209                         case *collectionFileSystem:
 210                                 dn = parent.inode.(*dirnode)
 211                         default:
 212                                 err = ErrInvalidArgument
 213                                 return nil
 214                         }
 215                         if perm.IsDir() {
 216                                 n, err = dn.newDirnode(dn, name, perm|0755, time.Now())
 217                         } else {
 218                                 n, err = dn.newFilenode(dn, name, perm|0755, time.Now())
 219                         }
 220                         return n
 221                 })
 222                 if err != nil {
 223                         return nil, err
 224                 } else if n == nil {
 225                         // parent rejected new child
 226                         return nil, ErrInvalidOperation
 227                 }
 228         } else if flag&os.O_EXCL != 0 {
 229                 return nil, ErrFileExists
 230         } else if flag&os.O_TRUNC != 0 {
 231                 if !writable {
 232                         return nil, fmt.Errorf("invalid flag O_TRUNC in read-only mode")
 233                 } else if fn, ok := n.(*filenode); !ok {
 234                         return nil, fmt.Errorf("invalid flag O_TRUNC when opening directory")
 235                 } else {
 236                         fn.Truncate(0)
 237                 }
 238         }
 239         return &filehandle{
 240                 inode:    n,
 241                 append:   flag&os.O_APPEND != 0,
 242                 readable: readable,
 243                 writable: writable,
 244         }, nil
 245 }
 246
 247 func (fs *fileSystem) Open(name string) (http.File, error) {
 248         return fs.OpenFile(name, os.O_RDONLY, 0)
 249 }
 250
 251 func (fs *fileSystem) Create(name string) (File, error) {
 252         return fs.OpenFile(name, os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0)
 253 }
 254
 255 func (fs *fileSystem) Mkdir(name string, perm os.FileMode) (err error) {
 256         dirname, name := path.Split(name)
 257         n := rlookup(fs.inode, dirname)
 258         if n == nil {
 259                 return os.ErrNotExist
 260         }
 261         n.Lock()
 262         defer n.Unlock()
 263         if n.Child(name, nil) != nil {
 264                 return os.ErrExist
 265         }
 266         dn, ok := n.(*dirnode)
 267         if !ok {
 268                 return ErrInvalidArgument
 269         }
 270         child := n.Child(name, func(inode) (child inode) {
 271                 child, err = dn.newDirnode(dn, name, perm, time.Now())
 272                 return
 273         })
 274         if err != nil {
 275                 return err
 276         } else if child == nil {
 277                 return ErrInvalidArgument
 278         }
 279         return nil
 280 }
 281
 282 func (fs *fileSystem) Stat(name string) (fi os.FileInfo, err error) {
 283         node := rlookup(fs.inode, name)
 284         if node == nil {
 285                 err = os.ErrNotExist
 286         } else {
 287                 fi = node.FileInfo()
 288         }
 289         return
 290 }
 291
 292 func (fs *fileSystem) Rename(oldname, newname string) error {
 293         olddir, oldname := path.Split(oldname)
 294         if oldname == "" || oldname == "." || oldname == ".." {
 295                 return ErrInvalidArgument
 296         }
 297         olddirf, err := fs.openFile(olddir+".", os.O_RDONLY, 0)
 298         if err != nil {
 299                 return fmt.Errorf("%q: %s", olddir, err)
 300         }
 301         defer olddirf.Close()
 302
 303         newdir, newname := path.Split(newname)
 304         if newname == "." || newname == ".." {
 305                 return ErrInvalidArgument
 306         } else if newname == "" {
 307                 // Rename("a/b", "c/") means Rename("a/b", "c/b")
 308                 newname = oldname
 309         }
 310         newdirf, err := fs.openFile(newdir+".", os.O_RDONLY, 0)
 311         if err != nil {
 312                 return fmt.Errorf("%q: %s", newdir, err)
 313         }
 314         defer newdirf.Close()
 315
 316         // When acquiring locks on multiple nodes, all common
 317         // ancestors must be locked first in order to avoid
 318         // deadlock. This is assured by locking the path from root to
 319         // newdir, then locking the path from root to olddir, skipping
 320         // any already-locked nodes.
 321         needLock := []sync.Locker{}
 322         for _, f := range []*filehandle{olddirf, newdirf} {
 323                 node := f.inode
 324                 needLock = append(needLock, node)
 325                 for node.Parent() != node {
 326                         node = node.Parent()
 327                         needLock = append(needLock, node)
 328                 }
 329         }
 330         locked := map[sync.Locker]bool{}
 331         for i := len(needLock) - 1; i >= 0; i-- {
 332                 if n := needLock[i]; !locked[n] {
 333                         n.Lock()
 334                         defer n.Unlock()
 335                         locked[n] = true
 336                 }
 337         }
 338
 339         if _, ok := newdirf.inode.(*dirnode); !ok {
 340                 return ErrInvalidOperation
 341         }
 342
 343         err = nil
 344         olddirf.inode.Child(oldname, func(oldinode inode) inode {
 345                 if oldinode == nil {
 346                         err = os.ErrNotExist
 347                         return nil
 348                 }
 349                 newdirf.inode.Child(newname, func(existing inode) inode {
 350                         if existing != nil && existing.IsDir() {
 351                                 err = ErrIsDirectory
 352                                 return existing
 353                         }
 354                         return oldinode
 355                 })
 356                 if err != nil {
 357                         return oldinode
 358                 }
 359                 oldinode.Lock()
 360                 defer oldinode.Unlock()
 361                 olddn := olddirf.inode.(*dirnode)
 362                 newdn := newdirf.inode.(*dirnode)
 363                 switch n := oldinode.(type) {
 364                 case *dirnode:
 365                         n.parent = newdirf.inode
 366                         n.treenode.fileinfo.name = newname
 367                 case *filenode:
 368                         n.parent = newdn
 369                         n.fileinfo.name = newname
 370                 default:
 371                         panic(fmt.Sprintf("bad inode type %T", n))
 372                 }
 373                 olddn.treenode.fileinfo.modTime = time.Now()
 374                 newdn.treenode.fileinfo.modTime = time.Now()
 375                 return nil
 376         })
 377         return err
 378 }
 379
 380 func (fs *fileSystem) Remove(name string) error {
 381         return fs.remove(strings.TrimRight(name, "/"), false)
 382 }
 383
 384 func (fs *fileSystem) RemoveAll(name string) error {
 385         err := fs.remove(strings.TrimRight(name, "/"), true)
 386         if os.IsNotExist(err) {
 387                 // "If the path does not exist, RemoveAll returns
 388                 // nil." (see "os" pkg)
 389                 err = nil
 390         }
 391         return err
 392 }
 393
 394 func (fs *fileSystem) remove(name string, recursive bool) (err error) {
 395         dirname, name := path.Split(name)
 396         if name == "" || name == "." || name == ".." {
 397                 return ErrInvalidArgument
 398         }
 399         dir := rlookup(fs, dirname)
 400         if dir == nil {
 401                 return os.ErrNotExist
 402         }
 403         dir.Lock()
 404         defer dir.Unlock()
 405         dir.Child(name, func(node inode) inode {
 406                 if node == nil {
 407                         err = os.ErrNotExist
 408                         return nil
 409                 }
 410                 if !recursive && node.IsDir() && node.Size() > 0 {
 411                         err = ErrDirectoryNotEmpty
 412                         return node
 413                 }
 414                 return nil
 415         })
 416         return err
 417 }
 418
 419 type inode interface {
 420         Parent() inode
 421         Read([]byte, filenodePtr) (int, filenodePtr, error)
 422         Write([]byte, filenodePtr) (int, filenodePtr, error)
 423         Truncate(int64) error
 424         IsDir() bool
 425         Readdir() []os.FileInfo
 426         Size() int64
 427         FileInfo() os.FileInfo
 428         // Caller must have lock (or rlock if func is nil)
 429         Child(string, func(inode) inode) inode
 430         sync.Locker
 431         RLock()
 432         RUnlock()
 433 }
 434
 435 // filenode implements inode.
 436 type filenode struct {
 437         fileinfo fileinfo
 438         parent   *dirnode
 439         segments []segment
 440         // number of times `segments` has changed in a
 441         // way that might invalidate a filenodePtr
 442         repacked int64
 443         memsize  int64 // bytes in memSegments
 444         sync.RWMutex
 445         nullnode
 446 }
 447
 448 // filenodePtr is an offset into a file that is (usually) efficient to
 449 // seek to. Specifically, if filenode.repacked==filenodePtr.repacked
 450 // then
 451 // filenode.segments[filenodePtr.segmentIdx][filenodePtr.segmentOff]
 452 // corresponds to file offset filenodePtr.off. Otherwise, it is
 453 // necessary to reexamine len(filenode.segments[0]) etc. to find the
 454 // correct segment and offset.
 455 type filenodePtr struct {
 456         off        int64
 457         segmentIdx int
 458         segmentOff int
 459         repacked   int64
 460 }
 461
 462 // seek returns a ptr that is consistent with both startPtr.off and
 463 // the current state of fn. The caller must already hold fn.RLock() or
 464 // fn.Lock().
 465 //
 466 // If startPtr is beyond EOF, ptr.segment* will indicate precisely
 467 // EOF.
 468 //
 469 // After seeking:
 470 //
 471 //     ptr.segmentIdx == len(filenode.segments) // i.e., at EOF
 472 //     ||
 473 //     filenode.segments[ptr.segmentIdx].Len() > ptr.segmentOff
 474 func (fn *filenode) seek(startPtr filenodePtr) (ptr filenodePtr) {
 475         ptr = startPtr
 476         if ptr.off < 0 {
 477                 // meaningless anyway
 478                 return
 479         } else if ptr.off >= fn.fileinfo.size {
 480                 ptr.segmentIdx = len(fn.segments)
 481                 ptr.segmentOff = 0
 482                 ptr.repacked = fn.repacked
 483                 return
 484         } else if ptr.repacked == fn.repacked {
 485                 // segmentIdx and segmentOff accurately reflect
 486                 // ptr.off, but might have fallen off the end of a
 487                 // segment
 488                 if ptr.segmentOff >= fn.segments[ptr.segmentIdx].Len() {
 489                         ptr.segmentIdx++
 490                         ptr.segmentOff = 0
 491                 }
 492                 return
 493         }
 494         defer func() {
 495                 ptr.repacked = fn.repacked
 496         }()
 497         if ptr.off >= fn.fileinfo.size {
 498                 ptr.segmentIdx, ptr.segmentOff = len(fn.segments), 0
 499                 return
 500         }
 501         // Recompute segmentIdx and segmentOff.  We have already
 502         // established fn.fileinfo.size > ptr.off >= 0, so we don't
 503         // have to deal with edge cases here.
 504         var off int64
 505         for ptr.segmentIdx, ptr.segmentOff = 0, 0; off < ptr.off; ptr.segmentIdx++ {
 506                 // This would panic (index out of range) if
 507                 // fn.fileinfo.size were larger than
 508                 // sum(fn.segments[i].Len()) -- but that can't happen
 509                 // because we have ensured fn.fileinfo.size is always
 510                 // accurate.
 511                 segLen := int64(fn.segments[ptr.segmentIdx].Len())
 512                 if off+segLen > ptr.off {
 513                         ptr.segmentOff = int(ptr.off - off)
 514                         break
 515                 }
 516                 off += segLen
 517         }
 518         return
 519 }
 520
 521 // caller must have lock
 522 func (fn *filenode) appendSegment(e segment) {
 523         fn.segments = append(fn.segments, e)
 524         fn.fileinfo.size += int64(e.Len())
 525 }
 526
 527 func (fn *filenode) Parent() inode {
 528         fn.RLock()
 529         defer fn.RUnlock()
 530         return fn.parent
 531 }
 532
 533 // Read reads file data from a single segment, starting at startPtr,
 534 // into p. startPtr is assumed not to be up-to-date. Caller must have
 535 // RLock or Lock.
 536 func (fn *filenode) Read(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) {
 537         ptr = fn.seek(startPtr)
 538         if ptr.off < 0 {
 539                 err = ErrNegativeOffset
 540                 return
 541         }
 542         if ptr.segmentIdx >= len(fn.segments) {
 543                 err = io.EOF
 544                 return
 545         }
 546         n, err = fn.segments[ptr.segmentIdx].ReadAt(p, int64(ptr.segmentOff))
 547         if n > 0 {
 548                 ptr.off += int64(n)
 549                 ptr.segmentOff += n
 550                 if ptr.segmentOff == fn.segments[ptr.segmentIdx].Len() {
 551                         ptr.segmentIdx++
 552                         ptr.segmentOff = 0
 553                         if ptr.segmentIdx < len(fn.segments) && err == io.EOF {
 554                                 err = nil
 555                         }
 556                 }
 557         }
 558         return
 559 }
 560
 561 func (fn *filenode) Size() int64 {
 562         fn.RLock()
 563         defer fn.RUnlock()
 564         return fn.fileinfo.Size()
 565 }
 566
 567 func (fn *filenode) FileInfo() os.FileInfo {
 568         fn.RLock()
 569         defer fn.RUnlock()
 570         return fn.fileinfo
 571 }
 572
 573 func (fn *filenode) Truncate(size int64) error {
 574         fn.Lock()
 575         defer fn.Unlock()
 576         return fn.truncate(size)
 577 }
 578
 579 func (fn *filenode) truncate(size int64) error {
 580         if size == fn.fileinfo.size {
 581                 return nil
 582         }
 583         fn.repacked++
 584         if size < fn.fileinfo.size {
 585                 ptr := fn.seek(filenodePtr{off: size})
 586                 for i := ptr.segmentIdx; i < len(fn.segments); i++ {
 587                         if seg, ok := fn.segments[i].(*memSegment); ok {
 588                                 fn.memsize -= int64(seg.Len())
 589                         }
 590                 }
 591                 if ptr.segmentOff == 0 {
 592                         fn.segments = fn.segments[:ptr.segmentIdx]
 593                 } else {
 594                         fn.segments = fn.segments[:ptr.segmentIdx+1]
 595                         switch seg := fn.segments[ptr.segmentIdx].(type) {
 596                         case *memSegment:
 597                                 seg.Truncate(ptr.segmentOff)
 598                                 fn.memsize += int64(seg.Len())
 599                         default:
 600                                 fn.segments[ptr.segmentIdx] = seg.Slice(0, ptr.segmentOff)
 601                         }
 602                 }
 603                 fn.fileinfo.size = size
 604                 return nil
 605         }
 606         for size > fn.fileinfo.size {
 607                 grow := size - fn.fileinfo.size
 608                 var seg *memSegment
 609                 var ok bool
 610                 if len(fn.segments) == 0 {
 611                         seg = &memSegment{}
 612                         fn.segments = append(fn.segments, seg)
 613                 } else if seg, ok = fn.segments[len(fn.segments)-1].(*memSegment); !ok || seg.Len() >= maxBlockSize {
 614                         seg = &memSegment{}
 615                         fn.segments = append(fn.segments, seg)
 616                 }
 617                 if maxgrow := int64(maxBlockSize - seg.Len()); maxgrow < grow {
 618                         grow = maxgrow
 619                 }
 620                 seg.Truncate(seg.Len() + int(grow))
 621                 fn.fileinfo.size += grow
 622                 fn.memsize += grow
 623         }
 624         return nil
 625 }
 626
 627 // Write writes data from p to the file, starting at startPtr,
 628 // extending the file size if necessary. Caller must have Lock.
 629 func (fn *filenode) Write(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) {
 630         if startPtr.off > fn.fileinfo.size {
 631                 if err = fn.truncate(startPtr.off); err != nil {
 632                         return 0, startPtr, err
 633                 }
 634         }
 635         ptr = fn.seek(startPtr)
 636         if ptr.off < 0 {
 637                 err = ErrNegativeOffset
 638                 return
 639         }
 640         for len(p) > 0 && err == nil {
 641                 cando := p
 642                 if len(cando) > maxBlockSize {
 643                         cando = cando[:maxBlockSize]
 644                 }
 645                 // Rearrange/grow fn.segments (and shrink cando if
 646                 // needed) such that cando can be copied to
 647                 // fn.segments[ptr.segmentIdx] at offset
 648                 // ptr.segmentOff.
 649                 cur := ptr.segmentIdx
 650                 prev := ptr.segmentIdx - 1
 651                 var curWritable bool
 652                 if cur < len(fn.segments) {
 653                         _, curWritable = fn.segments[cur].(*memSegment)
 654                 }
 655                 var prevAppendable bool
 656                 if prev >= 0 && fn.segments[prev].Len() < maxBlockSize {
 657                         _, prevAppendable = fn.segments[prev].(*memSegment)
 658                 }
 659                 if ptr.segmentOff > 0 && !curWritable {
 660                         // Split a non-writable block.
 661                         if max := fn.segments[cur].Len() - ptr.segmentOff; max <= len(cando) {
 662                                 // Truncate cur, and insert a new
 663                                 // segment after it.
 664                                 cando = cando[:max]
 665                                 fn.segments = append(fn.segments, nil)
 666                                 copy(fn.segments[cur+1:], fn.segments[cur:])
 667                         } else {
 668                                 // Split cur into two copies, truncate
 669                                 // the one on the left, shift the one
 670                                 // on the right, and insert a new
 671                                 // segment between them.
 672                                 fn.segments = append(fn.segments, nil, nil)
 673                                 copy(fn.segments[cur+2:], fn.segments[cur:])
 674                                 fn.segments[cur+2] = fn.segments[cur+2].Slice(ptr.segmentOff+len(cando), -1)
 675                         }
 676                         cur++
 677                         prev++
 678                         seg := &memSegment{}
 679                         seg.Truncate(len(cando))
 680                         fn.memsize += int64(len(cando))
 681                         fn.segments[cur] = seg
 682                         fn.segments[prev] = fn.segments[prev].Slice(0, ptr.segmentOff)
 683                         ptr.segmentIdx++
 684                         ptr.segmentOff = 0
 685                         fn.repacked++
 686                         ptr.repacked++
 687                 } else if curWritable {
 688                         if fit := int(fn.segments[cur].Len()) - ptr.segmentOff; fit < len(cando) {
 689                                 cando = cando[:fit]
 690                         }
 691                 } else {
 692                         if prevAppendable {
 693                                 // Shrink cando if needed to fit in
 694                                 // prev segment.
 695                                 if cangrow := maxBlockSize - fn.segments[prev].Len(); cangrow < len(cando) {
 696                                         cando = cando[:cangrow]
 697                                 }
 698                         }
 699
 700                         if cur == len(fn.segments) {
 701                                 // ptr is at EOF, filesize is changing.
 702                                 fn.fileinfo.size += int64(len(cando))
 703                         } else if el := fn.segments[cur].Len(); el <= len(cando) {
 704                                 // cando is long enough that we won't
 705                                 // need cur any more. shrink cando to
 706                                 // be exactly as long as cur
 707                                 // (otherwise we'd accidentally shift
 708                                 // the effective position of all
 709                                 // segments after cur).
 710                                 cando = cando[:el]
 711                                 copy(fn.segments[cur:], fn.segments[cur+1:])
 712                                 fn.segments = fn.segments[:len(fn.segments)-1]
 713                         } else {
 714                                 // shrink cur by the same #bytes we're growing prev
 715                                 fn.segments[cur] = fn.segments[cur].Slice(len(cando), -1)
 716                         }
 717
 718                         if prevAppendable {
 719                                 // Grow prev.
 720                                 ptr.segmentIdx--
 721                                 ptr.segmentOff = fn.segments[prev].Len()
 722                                 fn.segments[prev].(*memSegment).Truncate(ptr.segmentOff + len(cando))
 723                                 fn.memsize += int64(len(cando))
 724                                 ptr.repacked++
 725                                 fn.repacked++
 726                         } else {
 727                                 // Insert a segment between prev and
 728                                 // cur, and advance prev/cur.
 729                                 fn.segments = append(fn.segments, nil)
 730                                 if cur < len(fn.segments) {
 731                                         copy(fn.segments[cur+1:], fn.segments[cur:])
 732                                         ptr.repacked++
 733                                         fn.repacked++
 734                                 } else {
 735                                         // appending a new segment does
 736                                         // not invalidate any ptrs
 737                                 }
 738                                 seg := &memSegment{}
 739                                 seg.Truncate(len(cando))
 740                                 fn.memsize += int64(len(cando))
 741                                 fn.segments[cur] = seg
 742                                 cur++
 743                                 prev++
 744                         }
 745                 }
 746
 747                 // Finally we can copy bytes from cando to the current segment.
 748                 fn.segments[ptr.segmentIdx].(*memSegment).WriteAt(cando, ptr.segmentOff)
 749                 n += len(cando)
 750                 p = p[len(cando):]
 751
 752                 ptr.off += int64(len(cando))
 753                 ptr.segmentOff += len(cando)
 754                 if ptr.segmentOff >= maxBlockSize {
 755                         fn.pruneMemSegments()
 756                 }
 757                 if fn.segments[ptr.segmentIdx].Len() == ptr.segmentOff {
 758                         ptr.segmentOff = 0
 759                         ptr.segmentIdx++
 760                 }
 761
 762                 fn.fileinfo.modTime = time.Now()
 763         }
 764         return
 765 }
 766
 767 // Write some data out to disk to reduce memory use. Caller must have
 768 // write lock.
 769 func (fn *filenode) pruneMemSegments() {
 770         // TODO: async (don't hold Lock() while waiting for Keep)
 771         // TODO: share code with (*dirnode)sync()
 772         // TODO: pack/flush small blocks too, when fragmented
 773         for idx, seg := range fn.segments {
 774                 seg, ok := seg.(*memSegment)
 775                 if !ok || seg.Len() < maxBlockSize {
 776                         continue
 777                 }
 778                 locator, _, err := fn.parent.kc.PutB(seg.buf)
 779                 if err != nil {
 780                         // TODO: stall (or return errors from)
 781                         // subsequent writes until flushing
 782                         // starts to succeed
 783                         continue
 784                 }
 785                 fn.memsize -= int64(seg.Len())
 786                 fn.segments[idx] = storedSegment{
 787                         kc:      fn.parent.kc,
 788                         locator: locator,
 789                         size:    seg.Len(),
 790                         offset:  0,
 791                         length:  seg.Len(),
 792                 }
 793         }
 794 }
 795
 796 // FileSystem returns a CollectionFileSystem for the collection.
 797 func (c *Collection) FileSystem(client *Client, kc keepClient) (CollectionFileSystem, error) {
 798         var modTime time.Time
 799         if c.ModifiedAt == nil {
 800                 modTime = time.Now()
 801         } else {
 802                 modTime = *c.ModifiedAt
 803         }
 804         dn := &dirnode{
 805                 client: client,
 806                 kc:     kc,
 807                 treenode: treenode{
 808                         fileinfo: fileinfo{
 809                                 name:    ".",
 810                                 mode:    os.ModeDir | 0755,
 811                                 modTime: modTime,
 812                         },
 813                         parent: nil,
 814                         inodes: make(map[string]inode),
 815                 },
 816         }
 817         dn.parent = dn
 818         fs := &collectionFileSystem{fileSystem: fileSystem{inode: dn}}
 819         if err := dn.loadManifest(c.ManifestText); err != nil {
 820                 return nil, err
 821         }
 822         return fs, nil
 823 }
 824
 825 type filehandle struct {
 826         inode
 827         ptr        filenodePtr
 828         append     bool
 829         readable   bool
 830         writable   bool
 831         unreaddirs []os.FileInfo
 832 }
 833
 834 func (f *filehandle) Read(p []byte) (n int, err error) {
 835         if !f.readable {
 836                 return 0, ErrWriteOnlyMode
 837         }
 838         f.inode.RLock()
 839         defer f.inode.RUnlock()
 840         n, f.ptr, err = f.inode.Read(p, f.ptr)
 841         return
 842 }
 843
 844 func (f *filehandle) Seek(off int64, whence int) (pos int64, err error) {
 845         size := f.inode.Size()
 846         ptr := f.ptr
 847         switch whence {
 848         case io.SeekStart:
 849                 ptr.off = off
 850         case io.SeekCurrent:
 851                 ptr.off += off
 852         case io.SeekEnd:
 853                 ptr.off = size + off
 854         }
 855         if ptr.off < 0 {
 856                 return f.ptr.off, ErrNegativeOffset
 857         }
 858         if ptr.off != f.ptr.off {
 859                 f.ptr = ptr
 860                 // force filenode to recompute f.ptr fields on next
 861                 // use
 862                 f.ptr.repacked = -1
 863         }
 864         return f.ptr.off, nil
 865 }
 866
 867 func (f *filehandle) Truncate(size int64) error {
 868         return f.inode.Truncate(size)
 869 }
 870
 871 func (f *filehandle) Write(p []byte) (n int, err error) {
 872         if !f.writable {
 873                 return 0, ErrReadOnlyFile
 874         }
 875         f.inode.Lock()
 876         defer f.inode.Unlock()
 877         if fn, ok := f.inode.(*filenode); ok && f.append {
 878                 f.ptr = filenodePtr{
 879                         off:        fn.fileinfo.size,
 880                         segmentIdx: len(fn.segments),
 881                         segmentOff: 0,
 882                         repacked:   fn.repacked,
 883                 }
 884         }
 885         n, f.ptr, err = f.inode.Write(p, f.ptr)
 886         return
 887 }
 888
 889 func (f *filehandle) Readdir(count int) ([]os.FileInfo, error) {
 890         if !f.inode.IsDir() {
 891                 return nil, ErrInvalidOperation
 892         }
 893         if count <= 0 {
 894                 return f.inode.Readdir(), nil
 895         }
 896         if f.unreaddirs == nil {
 897                 f.unreaddirs = f.inode.Readdir()
 898         }
 899         if len(f.unreaddirs) == 0 {
 900                 return nil, io.EOF
 901         }
 902         if count > len(f.unreaddirs) {
 903                 count = len(f.unreaddirs)
 904         }
 905         ret := f.unreaddirs[:count]
 906         f.unreaddirs = f.unreaddirs[count:]
 907         return ret, nil
 908 }
 909
 910 func (f *filehandle) Stat() (os.FileInfo, error) {
 911         return f.inode.FileInfo(), nil
 912 }
 913
 914 func (f *filehandle) Close() error {
 915         return nil
 916 }
 917
 918 type dirnode struct {
 919         treenode
 920         client *Client
 921         kc     keepClient
 922 }
 923
 924 // sync flushes in-memory data (for all files in the tree rooted at
 925 // dn) to persistent storage. Caller must hold dn.Lock().
 926 func (dn *dirnode) sync() error {
 927         type shortBlock struct {
 928                 fn  *filenode
 929                 idx int
 930         }
 931         var pending []shortBlock
 932         var pendingLen int
 933
 934         flush := func(sbs []shortBlock) error {
 935                 if len(sbs) == 0 {
 936                         return nil
 937                 }
 938                 block := make([]byte, 0, maxBlockSize)
 939                 for _, sb := range sbs {
 940                         block = append(block, sb.fn.segments[sb.idx].(*memSegment).buf...)
 941                 }
 942                 locator, _, err := dn.kc.PutB(block)
 943                 if err != nil {
 944                         return err
 945                 }
 946                 off := 0
 947                 for _, sb := range sbs {
 948                         data := sb.fn.segments[sb.idx].(*memSegment).buf
 949                         sb.fn.segments[sb.idx] = storedSegment{
 950                                 kc:      dn.kc,
 951                                 locator: locator,
 952                                 size:    len(block),
 953                                 offset:  off,
 954                                 length:  len(data),
 955                         }
 956                         off += len(data)
 957                         sb.fn.memsize -= int64(len(data))
 958                 }
 959                 return nil
 960         }
 961
 962         names := make([]string, 0, len(dn.inodes))
 963         for name := range dn.inodes {
 964                 names = append(names, name)
 965         }
 966         sort.Strings(names)
 967
 968         for _, name := range names {
 969                 fn, ok := dn.inodes[name].(*filenode)
 970                 if !ok {
 971                         continue
 972                 }
 973                 fn.Lock()
 974                 defer fn.Unlock()
 975                 for idx, seg := range fn.segments {
 976                         seg, ok := seg.(*memSegment)
 977                         if !ok {
 978                                 continue
 979                         }
 980                         if seg.Len() > maxBlockSize/2 {
 981                                 if err := flush([]shortBlock{{fn, idx}}); err != nil {
 982                                         return err
 983                                 }
 984                                 continue
 985                         }
 986                         if pendingLen+seg.Len() > maxBlockSize {
 987                                 if err := flush(pending); err != nil {
 988                                         return err
 989                                 }
 990                                 pending = nil
 991                                 pendingLen = 0
 992                         }
 993                         pending = append(pending, shortBlock{fn, idx})
 994                         pendingLen += seg.Len()
 995                 }
 996         }
 997         return flush(pending)
 998 }
 999
1000 // caller must have read lock.
1001 func (dn *dirnode) marshalManifest(prefix string) (string, error) {
1002         var streamLen int64
1003         type filepart struct {
1004                 name   string
1005                 offset int64
1006                 length int64
1007         }
1008         var fileparts []filepart
1009         var subdirs string
1010         var blocks []string
1011
1012         if err := dn.sync(); err != nil {
1013                 return "", err
1014         }
1015
1016         names := make([]string, 0, len(dn.inodes))
1017         for name, node := range dn.inodes {
1018                 names = append(names, name)
1019                 node.Lock()
1020                 defer node.Unlock()
1021         }
1022         sort.Strings(names)
1023
1024         for _, name := range names {
1025                 switch node := dn.inodes[name].(type) {
1026                 case *dirnode:
1027                         subdir, err := node.marshalManifest(prefix + "/" + name)
1028                         if err != nil {
1029                                 return "", err
1030                         }
1031                         subdirs = subdirs + subdir
1032                 case *filenode:
1033                         if len(node.segments) == 0 {
1034                                 fileparts = append(fileparts, filepart{name: name})
1035                                 break
1036                         }
1037                         for _, seg := range node.segments {
1038                                 switch seg := seg.(type) {
1039                                 case storedSegment:
1040                                         if len(blocks) > 0 && blocks[len(blocks)-1] == seg.locator {
1041                                                 streamLen -= int64(seg.size)
1042                                         } else {
1043                                                 blocks = append(blocks, seg.locator)
1044                                         }
1045                                         next := filepart{
1046                                                 name:   name,
1047                                                 offset: streamLen + int64(seg.offset),
1048                                                 length: int64(seg.length),
1049                                         }
1050                                         if prev := len(fileparts) - 1; prev >= 0 &&
1051                                                 fileparts[prev].name == name &&
1052                                                 fileparts[prev].offset+fileparts[prev].length == next.offset {
1053                                                 fileparts[prev].length += next.length
1054                                         } else {
1055                                                 fileparts = append(fileparts, next)
1056                                         }
1057                                         streamLen += int64(seg.size)
1058                                 default:
1059                                         // This can't happen: we
1060                                         // haven't unlocked since
1061                                         // calling sync().
1062                                         panic(fmt.Sprintf("can't marshal segment type %T", seg))
1063                                 }
1064                         }
1065                 default:
1066                         panic(fmt.Sprintf("can't marshal inode type %T", node))
1067                 }
1068         }
1069         var filetokens []string
1070         for _, s := range fileparts {
1071                 filetokens = append(filetokens, fmt.Sprintf("%d:%d:%s", s.offset, s.length, manifestEscape(s.name)))
1072         }
1073         if len(filetokens) == 0 {
1074                 return subdirs, nil
1075         } else if len(blocks) == 0 {
1076                 blocks = []string{"d41d8cd98f00b204e9800998ecf8427e+0"}
1077         }
1078         return manifestEscape(prefix) + " " + strings.Join(blocks, " ") + " " + strings.Join(filetokens, " ") + "\n" + subdirs, nil
1079 }
1080
1081 func (dn *dirnode) loadManifest(txt string) error {
1082         var dirname string
1083         streams := strings.Split(txt, "\n")
1084         if streams[len(streams)-1] != "" {
1085                 return fmt.Errorf("line %d: no trailing newline", len(streams))
1086         }
1087         streams = streams[:len(streams)-1]
1088         segments := []storedSegment{}
1089         for i, stream := range streams {
1090                 lineno := i + 1
1091                 var anyFileTokens bool
1092                 var pos int64
1093                 var segIdx int
1094                 segments = segments[:0]
1095                 for i, token := range strings.Split(stream, " ") {
1096                         if i == 0 {
1097                                 dirname = manifestUnescape(token)
1098                                 continue
1099                         }
1100                         if !strings.Contains(token, ":") {
1101                                 if anyFileTokens {
1102                                         return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1103                                 }
1104                                 toks := strings.SplitN(token, "+", 3)
1105                                 if len(toks) < 2 {
1106                                         return fmt.Errorf("line %d: bad locator %q", lineno, token)
1107                                 }
1108                                 length, err := strconv.ParseInt(toks[1], 10, 32)
1109                                 if err != nil || length < 0 {
1110                                         return fmt.Errorf("line %d: bad locator %q", lineno, token)
1111                                 }
1112                                 segments = append(segments, storedSegment{
1113                                         locator: token,
1114                                         size:    int(length),
1115                                         offset:  0,
1116                                         length:  int(length),
1117                                 })
1118                                 continue
1119                         } else if len(segments) == 0 {
1120                                 return fmt.Errorf("line %d: bad locator %q", lineno, token)
1121                         }
1122
1123                         toks := strings.SplitN(token, ":", 3)
1124                         if len(toks) != 3 {
1125                                 return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1126                         }
1127                         anyFileTokens = true
1128
1129                         offset, err := strconv.ParseInt(toks[0], 10, 64)
1130                         if err != nil || offset < 0 {
1131                                 return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1132                         }
1133                         length, err := strconv.ParseInt(toks[1], 10, 64)
1134                         if err != nil || length < 0 {
1135                                 return fmt.Errorf("line %d: bad file segment %q", lineno, token)
1136                         }
1137                         name := dirname + "/" + manifestUnescape(toks[2])
1138                         fnode, err := dn.createFileAndParents(name)
1139                         if err != nil {
1140                                 return fmt.Errorf("line %d: cannot use path %q: %s", lineno, name, err)
1141                         }
1142                         // Map the stream offset/range coordinates to
1143                         // block/offset/range coordinates and add
1144                         // corresponding storedSegments to the filenode
1145                         if pos > offset {
1146                                 // Can't continue where we left off.
1147                                 // TODO: binary search instead of
1148                                 // rewinding all the way (but this
1149                                 // situation might be rare anyway)
1150                                 segIdx, pos = 0, 0
1151                         }
1152                         for next := int64(0); segIdx < len(segments); segIdx++ {
1153                                 seg := segments[segIdx]
1154                                 next = pos + int64(seg.Len())
1155                                 if next <= offset || seg.Len() == 0 {
1156                                         pos = next
1157                                         continue
1158                                 }
1159                                 if pos >= offset+length {
1160                                         break
1161                                 }
1162                                 var blkOff int
1163                                 if pos < offset {
1164                                         blkOff = int(offset - pos)
1165                                 }
1166                                 blkLen := seg.Len() - blkOff
1167                                 if pos+int64(blkOff+blkLen) > offset+length {
1168                                         blkLen = int(offset + length - pos - int64(blkOff))
1169                                 }
1170                                 fnode.appendSegment(storedSegment{
1171                                         kc:      dn.kc,
1172                                         locator: seg.locator,
1173                                         size:    seg.size,
1174                                         offset:  blkOff,
1175                                         length:  blkLen,
1176                                 })
1177                                 if next > offset+length {
1178                                         break
1179                                 } else {
1180                                         pos = next
1181                                 }
1182                         }
1183                         if segIdx == len(segments) && pos < offset+length {
1184                                 return fmt.Errorf("line %d: invalid segment in %d-byte stream: %q", lineno, pos, token)
1185                         }
1186                 }
1187                 if !anyFileTokens {
1188                         return fmt.Errorf("line %d: no file segments", lineno)
1189                 } else if len(segments) == 0 {
1190                         return fmt.Errorf("line %d: no locators", lineno)
1191                 } else if dirname == "" {
1192                         return fmt.Errorf("line %d: no stream name", lineno)
1193                 }
1194         }
1195         return nil
1196 }
1197
1198 // only safe to call from loadManifest -- no locking
1199 func (dn *dirnode) createFileAndParents(path string) (fn *filenode, err error) {
1200         node := dn
1201         names := strings.Split(path, "/")
1202         basename := names[len(names)-1]
1203         if basename == "" || basename == "." || basename == ".." {
1204                 err = fmt.Errorf("invalid filename")
1205                 return
1206         }
1207         for _, name := range names[:len(names)-1] {
1208                 switch name {
1209                 case "", ".":
1210                         continue
1211                 case "..":
1212                         if node == dn {
1213                                 // can't be sure parent will be a *dirnode
1214                                 return nil, ErrInvalidArgument
1215                         }
1216                         node = node.Parent().(*dirnode)
1217                         continue
1218                 }
1219                 node.Child(name, func(child inode) inode {
1220                         switch child.(type) {
1221                         case nil:
1222                                 node, err = dn.newDirnode(node, name, 0755|os.ModeDir, node.Parent().FileInfo().ModTime())
1223                                 child = node
1224                         case *dirnode:
1225                                 node = child.(*dirnode)
1226                         case *filenode:
1227                                 err = ErrFileExists
1228                         default:
1229                                 err = ErrInvalidOperation
1230                         }
1231                         return child
1232                 })
1233                 if err != nil {
1234                         return
1235                 }
1236         }
1237         node.Child(basename, func(child inode) inode {
1238                 switch child := child.(type) {
1239                 case nil:
1240                         fn, err = dn.newFilenode(node, basename, 0755, node.FileInfo().ModTime())
1241                         return fn
1242                 case *filenode:
1243                         fn = child
1244                         return child
1245                 case *dirnode:
1246                         err = ErrIsDirectory
1247                         return child
1248                 default:
1249                         err = ErrInvalidOperation
1250                         return child
1251                 }
1252         })
1253         return
1254 }
1255
1256 // rlookup (recursive lookup) returns the inode for the file/directory
1257 // with the given name (which may contain "/" separators). If no such
1258 // file/directory exists, the returned node is nil.
1259 func rlookup(start inode, path string) (node inode) {
1260         node = start
1261         for _, name := range strings.Split(path, "/") {
1262                 if node == nil {
1263                         break
1264                 }
1265                 if node.IsDir() {
1266                         if name == "." || name == "" {
1267                                 continue
1268                         }
1269                         if name == ".." {
1270                                 node = node.Parent()
1271                                 continue
1272                         }
1273                 }
1274                 node = func() inode {
1275                         node.RLock()
1276                         defer node.RUnlock()
1277                         return node.Child(name, nil)
1278                 }()
1279         }
1280         return
1281 }
1282
1283 // Caller must have lock, and must have already ensured
1284 // Children(name,nil) is nil.
1285 func (dn *dirnode) newDirnode(parent *dirnode, name string, perm os.FileMode, modTime time.Time) (node *dirnode, err error) {
1286         if name == "" || name == "." || name == ".." {
1287                 return nil, ErrInvalidArgument
1288         }
1289         return &dirnode{
1290                 client: dn.client,
1291                 kc:     dn.kc,
1292                 treenode: treenode{
1293                         parent: parent,
1294                         fileinfo: fileinfo{
1295                                 name:    name,
1296                                 mode:    perm | os.ModeDir,
1297                                 modTime: modTime,
1298                         },
1299                         inodes: make(map[string]inode),
1300                 },
1301         }, nil
1302 }
1303
1304 func (dn *dirnode) newFilenode(parent *dirnode, name string, perm os.FileMode, modTime time.Time) (node *filenode, err error) {
1305         if name == "" || name == "." || name == ".." {
1306                 return nil, ErrInvalidArgument
1307         }
1308         return &filenode{
1309                 parent: parent,
1310                 fileinfo: fileinfo{
1311                         name:    name,
1312                         mode:    perm & ^os.ModeDir,
1313                         modTime: modTime,
1314                 },
1315         }, nil
1316 }
1317
1318 type segment interface {
1319         io.ReaderAt
1320         Len() int
1321         // Return a new segment with a subsection of the data from this
1322         // one. length<0 means length=Len()-off.
1323         Slice(off int, length int) segment
1324 }
1325
1326 type memSegment struct {
1327         buf []byte
1328 }
1329
1330 func (me *memSegment) Len() int {
1331         return len(me.buf)
1332 }
1333
1334 func (me *memSegment) Slice(off, length int) segment {
1335         if length < 0 {
1336                 length = len(me.buf) - off
1337         }
1338         buf := make([]byte, length)
1339         copy(buf, me.buf[off:])
1340         return &memSegment{buf: buf}
1341 }
1342
1343 func (me *memSegment) Truncate(n int) {
1344         if n > cap(me.buf) {
1345                 newsize := 1024
1346                 for newsize < n {
1347                         newsize = newsize << 2
1348                 }
1349                 newbuf := make([]byte, n, newsize)
1350                 copy(newbuf, me.buf)
1351                 me.buf = newbuf
1352         } else {
1353                 // Zero unused part when shrinking, in case we grow
1354                 // and start using it again later.
1355                 for i := n; i < len(me.buf); i++ {
1356                         me.buf[i] = 0
1357                 }
1358         }
1359         me.buf = me.buf[:n]
1360 }
1361
1362 func (me *memSegment) WriteAt(p []byte, off int) {
1363         if off+len(p) > len(me.buf) {
1364                 panic("overflowed segment")
1365         }
1366         copy(me.buf[off:], p)
1367 }
1368
1369 func (me *memSegment) ReadAt(p []byte, off int64) (n int, err error) {
1370         if off > int64(me.Len()) {
1371                 err = io.EOF
1372                 return
1373         }
1374         n = copy(p, me.buf[int(off):])
1375         if n < len(p) {
1376                 err = io.EOF
1377         }
1378         return
1379 }
1380
1381 type storedSegment struct {
1382         kc      keepClient
1383         locator string
1384         size    int // size of stored block (also encoded in locator)
1385         offset  int // position of segment within the stored block
1386         length  int // bytes in this segment (offset + length <= size)
1387 }
1388
1389 func (se storedSegment) Len() int {
1390         return se.length
1391 }
1392
1393 func (se storedSegment) Slice(n, size int) segment {
1394         se.offset += n
1395         se.length -= n
1396         if size >= 0 && se.length > size {
1397                 se.length = size
1398         }
1399         return se
1400 }
1401
1402 func (se storedSegment) ReadAt(p []byte, off int64) (n int, err error) {
1403         if off > int64(se.length) {
1404                 return 0, io.EOF
1405         }
1406         maxlen := se.length - int(off)
1407         if len(p) > maxlen {
1408                 p = p[:maxlen]
1409                 n, err = se.kc.ReadAt(se.locator, p, int(off)+se.offset)
1410                 if err == nil {
1411                         err = io.EOF
1412                 }
1413                 return
1414         }
1415         return se.kc.ReadAt(se.locator, p, int(off)+se.offset)
1416 }
1417
1418 func canonicalName(name string) string {
1419         name = path.Clean("/" + name)
1420         if name == "/" || name == "./" {
1421                 name = "."
1422         } else if strings.HasPrefix(name, "/") {
1423                 name = "." + name
1424         }
1425         return name
1426 }
1427
1428 var manifestEscapeSeq = regexp.MustCompile(`\\([0-7]{3}|\\)`)
1429
1430 func manifestUnescapeFunc(seq string) string {
1431         if seq == `\\` {
1432                 return `\`
1433         }
1434         i, err := strconv.ParseUint(seq[1:], 8, 8)
1435         if err != nil {
1436                 // Invalid escape sequence: can't unescape.
1437                 return seq
1438         }
1439         return string([]byte{byte(i)})
1440 }
1441
1442 func manifestUnescape(s string) string {
1443         return manifestEscapeSeq.ReplaceAllStringFunc(s, manifestUnescapeFunc)
1444 }
1445
1446 var manifestEscapedChar = regexp.MustCompile(`[\000-\040:\s\\]`)
1447
1448 func manifestEscapeFunc(seq string) string {
1449         return fmt.Sprintf("\\%03o", byte(seq[0]))
1450 }
1451
1452 func manifestEscape(s string) string {
1453         return manifestEscapedChar.ReplaceAllStringFunc(s, manifestEscapeFunc)
1454 }