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         ErrDirectoryNotEmpty = errors.New("directory not empty")
  28         ErrPermission        = os.ErrPermission
  29
  30         maxBlockSize = 1 << 26
  31 )
  32
  33 type File interface {
  34         io.Reader
  35         io.Writer
  36         io.Closer
  37         io.Seeker
  38         Size() int64
  39         Readdir(int) ([]os.FileInfo, error)
  40         Stat() (os.FileInfo, error)
  41         Truncate(int64) error
  42 }
  43
  44 type keepClient interface {
  45         ReadAt(locator string, p []byte, off int) (int, error)
  46         PutB(p []byte) (string, int, error)
  47 }
  48
  49 type fileinfo struct {
  50         name    string
  51         mode    os.FileMode
  52         size    int64
  53         modTime time.Time
  54 }
  55
  56 // Name implements os.FileInfo.
  57 func (fi fileinfo) Name() string {
  58         return fi.name
  59 }
  60
  61 // ModTime implements os.FileInfo.
  62 func (fi fileinfo) ModTime() time.Time {
  63         return fi.modTime
  64 }
  65
  66 // Mode implements os.FileInfo.
  67 func (fi fileinfo) Mode() os.FileMode {
  68         return fi.mode
  69 }
  70
  71 // IsDir implements os.FileInfo.
  72 func (fi fileinfo) IsDir() bool {
  73         return fi.mode&os.ModeDir != 0
  74 }
  75
  76 // Size implements os.FileInfo.
  77 func (fi fileinfo) Size() int64 {
  78         return fi.size
  79 }
  80
  81 // Sys implements os.FileInfo.
  82 func (fi fileinfo) Sys() interface{} {
  83         return nil
  84 }
  85
  86 func (fi fileinfo) Stat() os.FileInfo {
  87         return fi
  88 }
  89
  90 // A CollectionFileSystem is an http.Filesystem plus Stat() and
  91 // support for opening writable files.
  92 type CollectionFileSystem interface {
  93         http.FileSystem
  94         Stat(name string) (os.FileInfo, error)
  95         Create(name string) (File, error)
  96         OpenFile(name string, flag int, perm os.FileMode) (File, error)
  97         Mkdir(name string, perm os.FileMode) error
  98         Remove(name string) error
  99         MarshalManifest(string) (string, error)
 100 }
 101
 102 type fileSystem struct {
 103         dirnode
 104 }
 105
 106 func (fs *fileSystem) OpenFile(name string, flag int, perm os.FileMode) (File, error) {
 107         return fs.dirnode.OpenFile(path.Clean(name), flag, perm)
 108 }
 109
 110 func (fs *fileSystem) Open(name string) (http.File, error) {
 111         return fs.dirnode.OpenFile(path.Clean(name), os.O_RDONLY, 0)
 112 }
 113
 114 func (fs *fileSystem) Create(name string) (File, error) {
 115         return fs.dirnode.OpenFile(path.Clean(name), os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0)
 116 }
 117
 118 func (fs *fileSystem) Stat(name string) (os.FileInfo, error) {
 119         f, err := fs.OpenFile(name, os.O_RDONLY, 0)
 120         if err != nil {
 121                 return nil, err
 122         }
 123         defer f.Close()
 124         return f.Stat()
 125 }
 126
 127 type inode interface {
 128         os.FileInfo
 129         Parent() inode
 130         Read([]byte, filenodePtr) (int, filenodePtr, error)
 131         Write([]byte, filenodePtr) (int, filenodePtr, error)
 132         Truncate(int64) error
 133         Readdir() []os.FileInfo
 134         Stat() os.FileInfo
 135         sync.Locker
 136         RLock()
 137         RUnlock()
 138 }
 139
 140 // filenode implements inode.
 141 type filenode struct {
 142         fileinfo
 143         parent   *dirnode
 144         extents  []extent
 145         repacked int64 // number of times anything in []extents has changed len
 146         sync.RWMutex
 147 }
 148
 149 // filenodePtr is an offset into a file that is (usually) efficient to
 150 // seek to. Specifically, if filenode.repacked==filenodePtr.repacked
 151 // then filenode.extents[filenodePtr.extentIdx][filenodePtr.extentOff]
 152 // corresponds to file offset filenodePtr.off. Otherwise, it is
 153 // necessary to reexamine len(filenode.extents[0]) etc. to find the
 154 // correct extent and offset.
 155 type filenodePtr struct {
 156         off       int64
 157         extentIdx int
 158         extentOff int
 159         repacked  int64
 160 }
 161
 162 // seek returns a ptr that is consistent with both startPtr.off and
 163 // the current state of fn. The caller must already hold fn.RLock() or
 164 // fn.Lock().
 165 //
 166 // If startPtr points beyond the end of the file, ptr will point to
 167 // exactly the end of the file.
 168 //
 169 // After seeking:
 170 //
 171 //     ptr.extentIdx == len(filenode.extents) // i.e., at EOF
 172 //     ||
 173 //     filenode.extents[ptr.extentIdx].Len() >= ptr.extentOff
 174 func (fn *filenode) seek(startPtr filenodePtr) (ptr filenodePtr) {
 175         ptr = startPtr
 176         if ptr.off < 0 {
 177                 // meaningless anyway
 178                 return
 179         } else if ptr.off >= fn.fileinfo.size {
 180                 ptr.off = fn.fileinfo.size
 181                 ptr.extentIdx = len(fn.extents)
 182                 ptr.extentOff = 0
 183                 ptr.repacked = fn.repacked
 184                 return
 185         } else if ptr.repacked == fn.repacked {
 186                 // extentIdx and extentOff accurately reflect ptr.off,
 187                 // but might have fallen off the end of an extent
 188                 if ptr.extentOff >= fn.extents[ptr.extentIdx].Len() {
 189                         ptr.extentIdx++
 190                         ptr.extentOff = 0
 191                 }
 192                 return
 193         }
 194         defer func() {
 195                 ptr.repacked = fn.repacked
 196         }()
 197         if ptr.off >= fn.fileinfo.size {
 198                 ptr.extentIdx, ptr.extentOff = len(fn.extents), 0
 199                 return
 200         }
 201         // Recompute extentIdx and extentOff.  We have already
 202         // established fn.fileinfo.size > ptr.off >= 0, so we don't
 203         // have to deal with edge cases here.
 204         var off int64
 205         for ptr.extentIdx, ptr.extentOff = 0, 0; off < ptr.off; ptr.extentIdx++ {
 206                 // This would panic (index out of range) if
 207                 // fn.fileinfo.size were larger than
 208                 // sum(fn.extents[i].Len()) -- but that can't happen
 209                 // because we have ensured fn.fileinfo.size is always
 210                 // accurate.
 211                 extLen := int64(fn.extents[ptr.extentIdx].Len())
 212                 if off+extLen > ptr.off {
 213                         ptr.extentOff = int(ptr.off - off)
 214                         break
 215                 }
 216                 off += extLen
 217         }
 218         return
 219 }
 220
 221 func (fn *filenode) appendExtent(e extent) {
 222         fn.Lock()
 223         defer fn.Unlock()
 224         fn.extents = append(fn.extents, e)
 225         fn.fileinfo.size += int64(e.Len())
 226 }
 227
 228 func (fn *filenode) Parent() inode {
 229         return fn.parent
 230 }
 231
 232 func (fn *filenode) Readdir() []os.FileInfo {
 233         return nil
 234 }
 235
 236 func (fn *filenode) Read(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) {
 237         fn.RLock()
 238         defer fn.RUnlock()
 239         ptr = fn.seek(startPtr)
 240         if ptr.off < 0 {
 241                 err = ErrNegativeOffset
 242                 return
 243         }
 244         if ptr.extentIdx >= len(fn.extents) {
 245                 err = io.EOF
 246                 return
 247         }
 248         n, err = fn.extents[ptr.extentIdx].ReadAt(p, int64(ptr.extentOff))
 249         if n > 0 {
 250                 ptr.off += int64(n)
 251                 ptr.extentOff += n
 252                 if ptr.extentOff == fn.extents[ptr.extentIdx].Len() {
 253                         ptr.extentIdx++
 254                         ptr.extentOff = 0
 255                         if ptr.extentIdx < len(fn.extents) && err == io.EOF {
 256                                 err = nil
 257                         }
 258                 }
 259         }
 260         return
 261 }
 262
 263 func (fn *filenode) Truncate(size int64) error {
 264         fn.Lock()
 265         defer fn.Unlock()
 266         if size < fn.fileinfo.size {
 267                 ptr := fn.seek(filenodePtr{off: size, repacked: fn.repacked - 1})
 268                 if ptr.extentOff == 0 {
 269                         fn.extents = fn.extents[:ptr.extentIdx]
 270                 } else {
 271                         fn.extents = fn.extents[:ptr.extentIdx+1]
 272                         e := fn.extents[ptr.extentIdx]
 273                         if e, ok := e.(writableExtent); ok {
 274                                 e.Truncate(ptr.extentOff)
 275                         } else {
 276                                 fn.extents[ptr.extentIdx] = e.Slice(0, ptr.extentOff)
 277                         }
 278                 }
 279                 fn.fileinfo.size = size
 280                 fn.repacked++
 281                 return nil
 282         }
 283         for size > fn.fileinfo.size {
 284                 grow := size - fn.fileinfo.size
 285                 var e writableExtent
 286                 var ok bool
 287                 if len(fn.extents) == 0 {
 288                         e = &memExtent{}
 289                         fn.extents = append(fn.extents, e)
 290                 } else if e, ok = fn.extents[len(fn.extents)-1].(writableExtent); !ok || e.Len() >= maxBlockSize {
 291                         e = &memExtent{}
 292                         fn.extents = append(fn.extents, e)
 293                 } else {
 294                         fn.repacked++
 295                 }
 296                 if maxgrow := int64(maxBlockSize - e.Len()); maxgrow < grow {
 297                         grow = maxgrow
 298                 }
 299                 e.Truncate(e.Len() + int(grow))
 300                 fn.fileinfo.size += grow
 301         }
 302         return nil
 303 }
 304
 305 func (fn *filenode) Write(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) {
 306         fn.Lock()
 307         defer fn.Unlock()
 308         ptr = fn.seek(startPtr)
 309         if ptr.off < 0 {
 310                 err = ErrNegativeOffset
 311                 return
 312         }
 313         for len(p) > 0 && err == nil {
 314                 cando := p
 315                 if len(cando) > maxBlockSize {
 316                         cando = cando[:maxBlockSize]
 317                 }
 318                 // Rearrange/grow fn.extents (and shrink cando if
 319                 // needed) such that cando can be copied to
 320                 // fn.extents[ptr.extentIdx] at offset ptr.extentOff.
 321                 cur := ptr.extentIdx
 322                 prev := ptr.extentIdx - 1
 323                 var curWritable bool
 324                 if cur < len(fn.extents) {
 325                         _, curWritable = fn.extents[cur].(writableExtent)
 326                 }
 327                 var prevAppendable bool
 328                 if prev >= 0 && fn.extents[prev].Len() < maxBlockSize {
 329                         _, prevAppendable = fn.extents[prev].(writableExtent)
 330                 }
 331                 if ptr.extentOff > 0 && !curWritable {
 332                         // Split a non-writable block.
 333                         if max := fn.extents[cur].Len() - ptr.extentOff; max <= len(cando) {
 334                                 // Truncate cur, and insert a new
 335                                 // extent after it.
 336                                 cando = cando[:max]
 337                                 fn.extents = append(fn.extents, nil)
 338                                 copy(fn.extents[cur+1:], fn.extents[cur:])
 339                         } else {
 340                                 // Split cur into two copies, truncate
 341                                 // the one on the left, shift the one
 342                                 // on the right, and insert a new
 343                                 // extent between them.
 344                                 fn.extents = append(fn.extents, nil, nil)
 345                                 copy(fn.extents[cur+2:], fn.extents[cur:])
 346                                 fn.extents[cur+2] = fn.extents[cur+2].Slice(ptr.extentOff+len(cando), -1)
 347                         }
 348                         cur++
 349                         prev++
 350                         e := &memExtent{}
 351                         e.Truncate(len(cando))
 352                         fn.extents[cur] = e
 353                         fn.extents[prev] = fn.extents[prev].Slice(0, ptr.extentOff)
 354                         ptr.extentIdx++
 355                         ptr.extentOff = 0
 356                         fn.repacked++
 357                         ptr.repacked++
 358                 } else if curWritable {
 359                         if fit := int(fn.extents[cur].Len()) - ptr.extentOff; fit < len(cando) {
 360                                 cando = cando[:fit]
 361                         }
 362                 } else {
 363                         if prevAppendable {
 364                                 // Shrink cando if needed to fit in prev extent.
 365                                 if cangrow := maxBlockSize - fn.extents[prev].Len(); cangrow < len(cando) {
 366                                         cando = cando[:cangrow]
 367                                 }
 368                         }
 369
 370                         if cur == len(fn.extents) {
 371                                 // ptr is at EOF, filesize is changing.
 372                                 fn.fileinfo.size += int64(len(cando))
 373                         } else if el := fn.extents[cur].Len(); el <= len(cando) {
 374                                 // cando is long enough that we won't
 375                                 // need cur any more. shrink cando to
 376                                 // be exactly as long as cur
 377                                 // (otherwise we'd accidentally shift
 378                                 // the effective position of all
 379                                 // extents after cur).
 380                                 cando = cando[:el]
 381                                 copy(fn.extents[cur:], fn.extents[cur+1:])
 382                                 fn.extents = fn.extents[:len(fn.extents)-1]
 383                         } else {
 384                                 // shrink cur by the same #bytes we're growing prev
 385                                 fn.extents[cur] = fn.extents[cur].Slice(len(cando), -1)
 386                         }
 387
 388                         if prevAppendable {
 389                                 // Grow prev.
 390                                 ptr.extentIdx--
 391                                 ptr.extentOff = fn.extents[prev].Len()
 392                                 fn.extents[prev].(writableExtent).Truncate(ptr.extentOff + len(cando))
 393                                 ptr.repacked++
 394                                 fn.repacked++
 395                         } else {
 396                                 // Insert an extent between prev and cur, and advance prev/cur.
 397                                 fn.extents = append(fn.extents, nil)
 398                                 if cur < len(fn.extents) {
 399                                         copy(fn.extents[cur+1:], fn.extents[cur:])
 400                                         ptr.repacked++
 401                                         fn.repacked++
 402                                 } else {
 403                                         // appending a new extent does
 404                                         // not invalidate any ptrs
 405                                 }
 406                                 e := &memExtent{}
 407                                 e.Truncate(len(cando))
 408                                 fn.extents[cur] = e
 409                                 cur++
 410                                 prev++
 411                         }
 412                 }
 413
 414                 // Finally we can copy bytes from cando to the current extent.
 415                 fn.extents[ptr.extentIdx].(writableExtent).WriteAt(cando, ptr.extentOff)
 416                 n += len(cando)
 417                 p = p[len(cando):]
 418
 419                 ptr.off += int64(len(cando))
 420                 ptr.extentOff += len(cando)
 421                 if fn.extents[ptr.extentIdx].Len() == ptr.extentOff {
 422                         ptr.extentOff = 0
 423                         ptr.extentIdx++
 424                 }
 425         }
 426         return
 427 }
 428
 429 // FileSystem returns a CollectionFileSystem for the collection.
 430 func (c *Collection) FileSystem(client *Client, kc keepClient) CollectionFileSystem {
 431         fs := &fileSystem{dirnode: dirnode{
 432                 client:   client,
 433                 kc:       kc,
 434                 fileinfo: fileinfo{name: ".", mode: os.ModeDir | 0755},
 435                 parent:   nil,
 436                 inodes:   make(map[string]inode),
 437         }}
 438         fs.dirnode.parent = &fs.dirnode
 439         fs.dirnode.loadManifest(c.ManifestText)
 440         return fs
 441 }
 442
 443 type file struct {
 444         inode
 445         ptr        filenodePtr
 446         append     bool
 447         writable   bool
 448         unreaddirs []os.FileInfo
 449 }
 450
 451 func (f *file) Read(p []byte) (n int, err error) {
 452         n, f.ptr, err = f.inode.Read(p, f.ptr)
 453         return
 454 }
 455
 456 func (f *file) Seek(off int64, whence int) (pos int64, err error) {
 457         size := f.inode.Size()
 458         ptr := f.ptr
 459         switch whence {
 460         case os.SEEK_SET:
 461                 ptr.off = off
 462         case os.SEEK_CUR:
 463                 ptr.off += off
 464         case os.SEEK_END:
 465                 ptr.off = size + off
 466         }
 467         if ptr.off < 0 {
 468                 return f.ptr.off, ErrNegativeOffset
 469         }
 470         if ptr.off > size {
 471                 ptr.off = size
 472         }
 473         if ptr.off != f.ptr.off {
 474                 f.ptr = ptr
 475                 // force filenode to recompute f.ptr fields on next
 476                 // use
 477                 f.ptr.repacked = -1
 478         }
 479         return f.ptr.off, nil
 480 }
 481
 482 func (f *file) Truncate(size int64) error {
 483         return f.inode.Truncate(size)
 484 }
 485
 486 func (f *file) Write(p []byte) (n int, err error) {
 487         if !f.writable {
 488                 return 0, ErrReadOnlyFile
 489         }
 490         n, f.ptr, err = f.inode.Write(p, f.ptr)
 491         return
 492 }
 493
 494 func (f *file) Readdir(count int) ([]os.FileInfo, error) {
 495         if !f.inode.IsDir() {
 496                 return nil, ErrInvalidOperation
 497         }
 498         if count <= 0 {
 499                 return f.inode.Readdir(), nil
 500         }
 501         if f.unreaddirs == nil {
 502                 f.unreaddirs = f.inode.Readdir()
 503         }
 504         if len(f.unreaddirs) == 0 {
 505                 return nil, io.EOF
 506         }
 507         if count > len(f.unreaddirs) {
 508                 count = len(f.unreaddirs)
 509         }
 510         ret := f.unreaddirs[:count]
 511         f.unreaddirs = f.unreaddirs[count:]
 512         return ret, nil
 513 }
 514
 515 func (f *file) Stat() (os.FileInfo, error) {
 516         return f.inode, nil
 517 }
 518
 519 func (f *file) Close() error {
 520         // FIXME: flush
 521         return nil
 522 }
 523
 524 type dirnode struct {
 525         fileinfo
 526         parent *dirnode
 527         client *Client
 528         kc     keepClient
 529         inodes map[string]inode
 530         sync.RWMutex
 531 }
 532
 533 // caller must hold dn.Lock().
 534 func (dn *dirnode) sync() error {
 535         type shortBlock struct {
 536                 fn  *filenode
 537                 idx int
 538         }
 539         var pending []shortBlock
 540         var pendingLen int
 541
 542         flush := func(sbs []shortBlock) error {
 543                 if len(sbs) == 0 {
 544                         return nil
 545                 }
 546                 block := make([]byte, 0, maxBlockSize)
 547                 for _, sb := range sbs {
 548                         block = append(block, sb.fn.extents[sb.idx].(*memExtent).buf...)
 549                 }
 550                 locator, _, err := dn.kc.PutB(block)
 551                 if err != nil {
 552                         return err
 553                 }
 554                 off := 0
 555                 for _, sb := range sbs {
 556                         data := sb.fn.extents[sb.idx].(*memExtent).buf
 557                         sb.fn.extents[sb.idx] = storedExtent{
 558                                 kc:      dn.kc,
 559                                 locator: locator,
 560                                 size:    len(block),
 561                                 offset:  off,
 562                                 length:  len(data),
 563                         }
 564                         off += len(data)
 565                 }
 566                 return nil
 567         }
 568
 569         names := make([]string, 0, len(dn.inodes))
 570         for name := range dn.inodes {
 571                 names = append(names, name)
 572         }
 573         sort.Strings(names)
 574
 575         for _, name := range names {
 576                 fn, ok := dn.inodes[name].(*filenode)
 577                 if !ok {
 578                         continue
 579                 }
 580                 fn.Lock()
 581                 defer fn.Unlock()
 582                 for idx, ext := range fn.extents {
 583                         ext, ok := ext.(*memExtent)
 584                         if !ok {
 585                                 continue
 586                         }
 587                         if ext.Len() > maxBlockSize/2 {
 588                                 if err := flush([]shortBlock{{fn, idx}}); err != nil {
 589                                         return err
 590                                 }
 591                                 continue
 592                         }
 593                         if pendingLen+ext.Len() > maxBlockSize {
 594                                 if err := flush(pending); err != nil {
 595                                         return err
 596                                 }
 597                                 pending = nil
 598                                 pendingLen = 0
 599                         }
 600                         pending = append(pending, shortBlock{fn, idx})
 601                         pendingLen += ext.Len()
 602                 }
 603         }
 604         return flush(pending)
 605 }
 606
 607 func (dn *dirnode) MarshalManifest(prefix string) (string, error) {
 608         dn.Lock()
 609         defer dn.Unlock()
 610         return dn.marshalManifest(prefix)
 611 }
 612
 613 // caller must have read lock.
 614 func (dn *dirnode) marshalManifest(prefix string) (string, error) {
 615         var streamLen int64
 616         type m1segment struct {
 617                 name   string
 618                 offset int64
 619                 length int64
 620         }
 621         var segments []m1segment
 622         var subdirs string
 623         var blocks []string
 624
 625         if err := dn.sync(); err != nil {
 626                 return "", err
 627         }
 628
 629         names := make([]string, 0, len(dn.inodes))
 630         for name, node := range dn.inodes {
 631                 names = append(names, name)
 632                 node.Lock()
 633                 defer node.Unlock()
 634         }
 635         sort.Strings(names)
 636
 637         for _, name := range names {
 638                 node := dn.inodes[name]
 639                 switch node := node.(type) {
 640                 case *dirnode:
 641                         subdir, err := node.marshalManifest(prefix + "/" + node.Name())
 642                         if err != nil {
 643                                 return "", err
 644                         }
 645                         subdirs = subdirs + subdir
 646                 case *filenode:
 647                         for _, e := range node.extents {
 648                                 switch e := e.(type) {
 649                                 case storedExtent:
 650                                         if len(blocks) > 0 && blocks[len(blocks)-1] == e.locator {
 651                                                 streamLen -= int64(e.size)
 652                                         } else {
 653                                                 blocks = append(blocks, e.locator)
 654                                         }
 655                                         segments = append(segments, m1segment{
 656                                                 name:   node.Name(),
 657                                                 offset: streamLen + int64(e.offset),
 658                                                 length: int64(e.length),
 659                                         })
 660                                         streamLen += int64(e.size)
 661                                 default:
 662                                         // This can't happen: we
 663                                         // haven't unlocked since
 664                                         // calling sync().
 665                                         panic(fmt.Sprintf("can't marshal extent type %T", e))
 666                                 }
 667                         }
 668                 default:
 669                         panic(fmt.Sprintf("can't marshal inode type %T", node))
 670                 }
 671         }
 672         var filetokens []string
 673         for _, s := range segments {
 674                 filetokens = append(filetokens, fmt.Sprintf("%d:%d:%s", s.offset, s.length, manifestEscape(s.name)))
 675         }
 676         if len(filetokens) == 0 {
 677                 return subdirs, nil
 678         } else if len(blocks) == 0 {
 679                 blocks = []string{"d41d8cd98f00b204e9800998ecf8427e+0"}
 680         }
 681         return manifestEscape(prefix) + " " + strings.Join(blocks, " ") + " " + strings.Join(filetokens, " ") + "\n" + subdirs, nil
 682 }
 683
 684 func (dn *dirnode) loadManifest(txt string) {
 685         // FIXME: faster
 686         var dirname string
 687         for _, stream := range strings.Split(txt, "\n") {
 688                 var extents []storedExtent
 689                 for i, token := range strings.Split(stream, " ") {
 690                         if i == 0 {
 691                                 dirname = manifestUnescape(token)
 692                                 continue
 693                         }
 694                         if !strings.Contains(token, ":") {
 695                                 toks := strings.SplitN(token, "+", 3)
 696                                 if len(toks) < 2 {
 697                                         // FIXME: broken
 698                                         continue
 699                                 }
 700                                 length, err := strconv.ParseInt(toks[1], 10, 32)
 701                                 if err != nil || length < 0 {
 702                                         // FIXME: broken
 703                                         continue
 704                                 }
 705                                 extents = append(extents, storedExtent{
 706                                         locator: token,
 707                                         size:    int(length),
 708                                         offset:  0,
 709                                         length:  int(length),
 710                                 })
 711                                 continue
 712                         }
 713                         toks := strings.Split(token, ":")
 714                         if len(toks) != 3 {
 715                                 // FIXME: broken manifest
 716                                 continue
 717                         }
 718                         offset, err := strconv.ParseInt(toks[0], 10, 64)
 719                         if err != nil || offset < 0 {
 720                                 // FIXME: broken manifest
 721                                 continue
 722                         }
 723                         length, err := strconv.ParseInt(toks[1], 10, 64)
 724                         if err != nil || length < 0 {
 725                                 // FIXME: broken manifest
 726                                 continue
 727                         }
 728                         name := path.Clean(dirname + "/" + manifestUnescape(toks[2]))
 729                         dn.makeParentDirs(name)
 730                         f, err := dn.OpenFile(name, os.O_CREATE|os.O_WRONLY|os.O_APPEND, 0700)
 731                         if err != nil {
 732                                 // FIXME: don't panic
 733                                 panic(fmt.Errorf("cannot append to %q: %s", name, err))
 734                         }
 735                         if f.inode.Stat().IsDir() {
 736                                 f.Close()
 737                                 // FIXME: don't panic
 738                                 panic(fmt.Errorf("cannot append to %q: is a directory", name))
 739                         }
 740                         // Map the stream offset/range coordinates to
 741                         // block/offset/range coordinates and add
 742                         // corresponding storedExtents to the filenode
 743                         var pos int64
 744                         for _, e := range extents {
 745                                 next := pos + int64(e.Len())
 746                                 if next < offset {
 747                                         pos = next
 748                                         continue
 749                                 }
 750                                 if pos > offset+length {
 751                                         break
 752                                 }
 753                                 var blkOff int
 754                                 if pos < offset {
 755                                         blkOff = int(offset - pos)
 756                                 }
 757                                 blkLen := e.Len() - blkOff
 758                                 if pos+int64(blkOff+blkLen) > offset+length {
 759                                         blkLen = int(offset + length - pos - int64(blkOff))
 760                                 }
 761                                 f.inode.(*filenode).appendExtent(storedExtent{
 762                                         kc:      dn.kc,
 763                                         locator: e.locator,
 764                                         size:    e.size,
 765                                         offset:  blkOff,
 766                                         length:  blkLen,
 767                                 })
 768                                 pos = next
 769                         }
 770                         f.Close()
 771                 }
 772         }
 773 }
 774
 775 func (dn *dirnode) makeParentDirs(name string) (err error) {
 776         names := strings.Split(name, "/")
 777         for _, name := range names[:len(names)-1] {
 778                 f, err := dn.mkdir(name)
 779                 if err != nil {
 780                         return err
 781                 }
 782                 defer f.Close()
 783                 var ok bool
 784                 dn, ok = f.inode.(*dirnode)
 785                 if !ok {
 786                         return ErrFileExists
 787                 }
 788         }
 789         return nil
 790 }
 791
 792 func (dn *dirnode) mkdir(name string) (*file, error) {
 793         return dn.OpenFile(name, os.O_CREATE|os.O_EXCL, os.ModeDir|0755)
 794 }
 795
 796 func (dn *dirnode) Mkdir(name string, perm os.FileMode) error {
 797         f, err := dn.mkdir(name)
 798         if err != nil {
 799                 f.Close()
 800         }
 801         return err
 802 }
 803
 804 func (dn *dirnode) Remove(name string) error {
 805         dirname, name := path.Split(name)
 806         if name == "" || name == "." || name == ".." {
 807                 return ErrInvalidOperation
 808         }
 809         dn, ok := dn.lookupPath(dirname).(*dirnode)
 810         if !ok {
 811                 return os.ErrNotExist
 812         }
 813         dn.Lock()
 814         defer dn.Unlock()
 815         switch node := dn.inodes[name].(type) {
 816         case nil:
 817                 return os.ErrNotExist
 818         case *dirnode:
 819                 node.RLock()
 820                 defer node.RUnlock()
 821                 if len(node.inodes) > 0 {
 822                         return ErrDirectoryNotEmpty
 823                 }
 824         }
 825         delete(dn.inodes, name)
 826         return nil
 827 }
 828
 829 func (dn *dirnode) Parent() inode {
 830         dn.RLock()
 831         defer dn.RUnlock()
 832         return dn.parent
 833 }
 834
 835 func (dn *dirnode) Readdir() (fi []os.FileInfo) {
 836         dn.RLock()
 837         defer dn.RUnlock()
 838         fi = make([]os.FileInfo, 0, len(dn.inodes))
 839         for _, inode := range dn.inodes {
 840                 fi = append(fi, inode.Stat())
 841         }
 842         return
 843 }
 844
 845 func (dn *dirnode) Read(p []byte, ptr filenodePtr) (int, filenodePtr, error) {
 846         return 0, ptr, ErrInvalidOperation
 847 }
 848
 849 func (dn *dirnode) Write(p []byte, ptr filenodePtr) (int, filenodePtr, error) {
 850         return 0, ptr, ErrInvalidOperation
 851 }
 852
 853 func (dn *dirnode) Truncate(int64) error {
 854         return ErrInvalidOperation
 855 }
 856
 857 // lookupPath returns the inode for the file/directory with the given
 858 // name (which may contain "/" separators), along with its parent
 859 // node. If no such file/directory exists, the returned node is nil.
 860 func (dn *dirnode) lookupPath(path string) (node inode) {
 861         node = dn
 862         for _, name := range strings.Split(path, "/") {
 863                 dn, ok := node.(*dirnode)
 864                 if !ok {
 865                         return nil
 866                 }
 867                 if name == "." || name == "" {
 868                         continue
 869                 }
 870                 if name == ".." {
 871                         node = node.Parent()
 872                         continue
 873                 }
 874                 dn.RLock()
 875                 node = dn.inodes[name]
 876                 dn.RUnlock()
 877         }
 878         return
 879 }
 880
 881 func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*file, error) {
 882         dirname, name := path.Split(name)
 883         dn, ok := dn.lookupPath(dirname).(*dirnode)
 884         if !ok {
 885                 return nil, os.ErrNotExist
 886         }
 887         writeMode := flag&(os.O_RDWR|os.O_WRONLY|os.O_CREATE) != 0
 888         if !writeMode {
 889                 // A directory can be opened via "foo/", "foo/.", or
 890                 // "foo/..".
 891                 switch name {
 892                 case ".", "":
 893                         return &file{inode: dn}, nil
 894                 case "..":
 895                         return &file{inode: dn.Parent()}, nil
 896                 }
 897         }
 898         createMode := flag&os.O_CREATE != 0
 899         if createMode {
 900                 dn.Lock()
 901                 defer dn.Unlock()
 902         } else {
 903                 dn.RLock()
 904                 defer dn.RUnlock()
 905         }
 906         n, ok := dn.inodes[name]
 907         if !ok {
 908                 if !createMode {
 909                         return nil, os.ErrNotExist
 910                 }
 911                 if perm.IsDir() {
 912                         n = &dirnode{
 913                                 parent: dn,
 914                                 client: dn.client,
 915                                 kc:     dn.kc,
 916                                 fileinfo: fileinfo{
 917                                         name: name,
 918                                         mode: os.ModeDir | 0755,
 919                                 },
 920                         }
 921                 } else {
 922                         n = &filenode{
 923                                 parent: dn,
 924                                 fileinfo: fileinfo{
 925                                         name: name,
 926                                         mode: 0755,
 927                                 },
 928                         }
 929                 }
 930                 if dn.inodes == nil {
 931                         dn.inodes = make(map[string]inode)
 932                 }
 933                 dn.inodes[name] = n
 934                 dn.fileinfo.size++
 935         } else if flag&os.O_EXCL != 0 {
 936                 return nil, ErrFileExists
 937         }
 938         return &file{
 939                 inode:    n,
 940                 append:   flag&os.O_APPEND != 0,
 941                 writable: flag&(os.O_WRONLY|os.O_RDWR) != 0,
 942         }, nil
 943 }
 944
 945 type extent interface {
 946         io.ReaderAt
 947         Len() int
 948         // Return a new extent with a subsection of the data from this
 949         // one. length<0 means length=Len()-off.
 950         Slice(off int, length int) extent
 951 }
 952
 953 type writableExtent interface {
 954         extent
 955         WriteAt(p []byte, off int)
 956         Truncate(n int)
 957 }
 958
 959 type memExtent struct {
 960         buf []byte
 961 }
 962
 963 func (me *memExtent) Len() int {
 964         return len(me.buf)
 965 }
 966
 967 func (me *memExtent) Slice(off, length int) extent {
 968         if length < 0 {
 969                 length = len(me.buf) - off
 970         }
 971         buf := make([]byte, length)
 972         copy(buf, me.buf[off:])
 973         return &memExtent{buf: buf}
 974 }
 975
 976 func (me *memExtent) Truncate(n int) {
 977         if n > cap(me.buf) {
 978                 newsize := 1024
 979                 for newsize < n {
 980                         newsize = newsize << 2
 981                 }
 982                 newbuf := make([]byte, n, newsize)
 983                 copy(newbuf, me.buf)
 984                 me.buf = newbuf
 985         } else {
 986                 // Zero unused part when shrinking, in case we grow
 987                 // and start using it again later.
 988                 for i := n; i < len(me.buf); i++ {
 989                         me.buf[i] = 0
 990                 }
 991         }
 992         me.buf = me.buf[:n]
 993 }
 994
 995 func (me *memExtent) WriteAt(p []byte, off int) {
 996         if off+len(p) > len(me.buf) {
 997                 panic("overflowed extent")
 998         }
 999         copy(me.buf[off:], p)
1000 }
1001
1002 func (me *memExtent) ReadAt(p []byte, off int64) (n int, err error) {
1003         if off > int64(me.Len()) {
1004                 err = io.EOF
1005                 return
1006         }
1007         n = copy(p, me.buf[int(off):])
1008         if n < len(p) {
1009                 err = io.EOF
1010         }
1011         return
1012 }
1013
1014 type storedExtent struct {
1015         kc      keepClient
1016         locator string
1017         size    int
1018         offset  int
1019         length  int
1020 }
1021
1022 func (se storedExtent) Len() int {
1023         return se.length
1024 }
1025
1026 func (se storedExtent) Slice(n, size int) extent {
1027         se.offset += n
1028         se.length -= n
1029         if size >= 0 && se.length > size {
1030                 se.length = size
1031         }
1032         return se
1033 }
1034
1035 func (se storedExtent) ReadAt(p []byte, off int64) (n int, err error) {
1036         if off > int64(se.length) {
1037                 return 0, io.EOF
1038         }
1039         maxlen := se.length - int(off)
1040         if len(p) > maxlen {
1041                 p = p[:maxlen]
1042                 n, err = se.kc.ReadAt(se.locator, p, int(off)+se.offset)
1043                 if err == nil {
1044                         err = io.EOF
1045                 }
1046                 return
1047         }
1048         return se.kc.ReadAt(se.locator, p, int(off)+se.offset)
1049 }
1050
1051 func canonicalName(name string) string {
1052         name = path.Clean("/" + name)
1053         if name == "/" || name == "./" {
1054                 name = "."
1055         } else if strings.HasPrefix(name, "/") {
1056                 name = "." + name
1057         }
1058         return name
1059 }
1060
1061 var manifestEscapeSeq = regexp.MustCompile(`\\([0-9]{3}|\\)`)
1062
1063 func manifestUnescapeFunc(seq string) string {
1064         if seq == `\\` {
1065                 return `\`
1066         }
1067         i, err := strconv.ParseUint(seq[1:], 8, 8)
1068         if err != nil {
1069                 // Invalid escape sequence: can't unescape.
1070                 return seq
1071         }
1072         return string([]byte{byte(i)})
1073 }
1074
1075 func manifestUnescape(s string) string {
1076         return manifestEscapeSeq.ReplaceAllStringFunc(s, manifestUnescapeFunc)
1077 }
1078
1079 var manifestEscapedChar = regexp.MustCompile(`[^\.\w/]`)
1080
1081 func manifestEscapeFunc(seq string) string {
1082         return fmt.Sprintf("\\%03o", byte(seq[0]))
1083 }
1084
1085 func manifestEscape(s string) string {
1086         return manifestEscapedChar.ReplaceAllStringFunc(s, manifestEscapeFunc)
1087 }