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