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