X-Git-Url: https://git.arvados.org/arvados.git/blobdiff_plain/fdc739318a2f0ec44ad3da69465221b48d30c29c..9f842eecf59f293fd800ece28be2730ff3a39487:/sdk/go/arvados/collection_fs.go diff --git a/sdk/go/arvados/collection_fs.go b/sdk/go/arvados/collection_fs.go index e720b93287..d8ee2a2b1c 100644 --- a/sdk/go/arvados/collection_fs.go +++ b/sdk/go/arvados/collection_fs.go @@ -24,14 +24,18 @@ var ( ErrNegativeOffset = errors.New("cannot seek to negative offset") ErrFileExists = errors.New("file exists") ErrInvalidOperation = errors.New("invalid operation") + ErrInvalidArgument = errors.New("invalid argument") ErrDirectoryNotEmpty = errors.New("directory not empty") ErrWriteOnlyMode = errors.New("file is O_WRONLY") ErrSyncNotSupported = errors.New("O_SYNC flag is not supported") + ErrIsDirectory = errors.New("cannot rename file to overwrite existing directory") ErrPermission = os.ErrPermission maxBlockSize = 1 << 26 ) +// A File is an *os.File-like interface for reading and writing files +// in a CollectionFileSystem. type File interface { io.Reader io.Writer @@ -86,15 +90,42 @@ func (fi fileinfo) Sys() interface{} { } // A CollectionFileSystem is an http.Filesystem plus Stat() and -// support for opening writable files. +// support for opening writable files. All methods are safe to call +// from multiple goroutines. type CollectionFileSystem interface { http.FileSystem + + // analogous to os.Stat() Stat(name string) (os.FileInfo, error) + + // analogous to os.Create(): create/truncate a file and open it O_RDWR. Create(name string) (File, error) + + // Like os.OpenFile(): create or open a file or directory. + // + // If flag&os.O_EXCL==0, it opens an existing file or + // directory if one exists. If flag&os.O_CREATE!=0, it creates + // a new empty file or directory if one does not already + // exist. + // + // When creating a new item, perm&os.ModeDir determines + // whether it is a file or a directory. + // + // A file can be opened multiple times and used concurrently + // from multiple goroutines. However, each File object should + // be used by only one goroutine at a time. OpenFile(name string, flag int, perm os.FileMode) (File, error) + Mkdir(name string, perm os.FileMode) error Remove(name string) error - MarshalManifest(string) (string, error) + RemoveAll(name string) error + Rename(oldname, newname string) error + + // Flush all file data to Keep and return a snapshot of the + // filesystem suitable for saving as (Collection)ManifestText. + // Prefix (normally ".") is a top level directory, effectively + // prepended to all paths in the returned manifest. + MarshalManifest(prefix string) (string, error) } type fileSystem struct { @@ -102,24 +133,25 @@ type fileSystem struct { } func (fs *fileSystem) OpenFile(name string, flag int, perm os.FileMode) (File, error) { - return fs.dirnode.OpenFile(path.Clean(name), flag, perm) + return fs.dirnode.OpenFile(name, flag, perm) } func (fs *fileSystem) Open(name string) (http.File, error) { - return fs.dirnode.OpenFile(path.Clean(name), os.O_RDONLY, 0) + return fs.dirnode.OpenFile(name, os.O_RDONLY, 0) } func (fs *fileSystem) Create(name string) (File, error) { - return fs.dirnode.OpenFile(path.Clean(name), os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0) + return fs.dirnode.OpenFile(name, os.O_CREATE|os.O_RDWR|os.O_TRUNC, 0) } -func (fs *fileSystem) Stat(name string) (os.FileInfo, error) { - f, err := fs.OpenFile(name, os.O_RDONLY, 0) - if err != nil { - return nil, err +func (fs *fileSystem) Stat(name string) (fi os.FileInfo, err error) { + node := fs.dirnode.lookupPath(name) + if node == nil { + err = os.ErrNotExist + } else { + fi = node.Stat() } - defer f.Close() - return f.Stat() + return } type inode interface { @@ -139,54 +171,57 @@ type inode interface { type filenode struct { fileinfo fileinfo parent *dirnode - extents []extent - repacked int64 // number of times anything in []extents has changed len - memsize int64 // bytes in memExtents + segments []segment + // number of times `segments` has changed in a + // way that might invalidate a filenodePtr + repacked int64 + memsize int64 // bytes in memSegments sync.RWMutex } // filenodePtr is an offset into a file that is (usually) efficient to // seek to. Specifically, if filenode.repacked==filenodePtr.repacked -// then filenode.extents[filenodePtr.extentIdx][filenodePtr.extentOff] +// then +// filenode.segments[filenodePtr.segmentIdx][filenodePtr.segmentOff] // corresponds to file offset filenodePtr.off. Otherwise, it is -// necessary to reexamine len(filenode.extents[0]) etc. to find the -// correct extent and offset. +// necessary to reexamine len(filenode.segments[0]) etc. to find the +// correct segment and offset. type filenodePtr struct { - off int64 - extentIdx int - extentOff int - repacked int64 + off int64 + segmentIdx int + segmentOff int + repacked int64 } // seek returns a ptr that is consistent with both startPtr.off and // the current state of fn. The caller must already hold fn.RLock() or // fn.Lock(). // -// If startPtr points beyond the end of the file, ptr will point to -// exactly the end of the file. +// If startPtr is beyond EOF, ptr.segment* will indicate precisely +// EOF. // // After seeking: // -// ptr.extentIdx == len(filenode.extents) // i.e., at EOF +// ptr.segmentIdx == len(filenode.segments) // i.e., at EOF // || -// filenode.extents[ptr.extentIdx].Len() >= ptr.extentOff +// filenode.segments[ptr.segmentIdx].Len() > ptr.segmentOff func (fn *filenode) seek(startPtr filenodePtr) (ptr filenodePtr) { ptr = startPtr if ptr.off < 0 { // meaningless anyway return } else if ptr.off >= fn.fileinfo.size { - ptr.off = fn.fileinfo.size - ptr.extentIdx = len(fn.extents) - ptr.extentOff = 0 + ptr.segmentIdx = len(fn.segments) + ptr.segmentOff = 0 ptr.repacked = fn.repacked return } else if ptr.repacked == fn.repacked { - // extentIdx and extentOff accurately reflect ptr.off, - // but might have fallen off the end of an extent - if ptr.extentOff >= fn.extents[ptr.extentIdx].Len() { - ptr.extentIdx++ - ptr.extentOff = 0 + // segmentIdx and segmentOff accurately reflect + // ptr.off, but might have fallen off the end of a + // segment + if ptr.segmentOff >= fn.segments[ptr.segmentIdx].Len() { + ptr.segmentIdx++ + ptr.segmentOff = 0 } return } @@ -194,37 +229,38 @@ func (fn *filenode) seek(startPtr filenodePtr) (ptr filenodePtr) { ptr.repacked = fn.repacked }() if ptr.off >= fn.fileinfo.size { - ptr.extentIdx, ptr.extentOff = len(fn.extents), 0 + ptr.segmentIdx, ptr.segmentOff = len(fn.segments), 0 return } - // Recompute extentIdx and extentOff. We have already + // Recompute segmentIdx and segmentOff. We have already // established fn.fileinfo.size > ptr.off >= 0, so we don't // have to deal with edge cases here. var off int64 - for ptr.extentIdx, ptr.extentOff = 0, 0; off < ptr.off; ptr.extentIdx++ { + for ptr.segmentIdx, ptr.segmentOff = 0, 0; off < ptr.off; ptr.segmentIdx++ { // This would panic (index out of range) if // fn.fileinfo.size were larger than - // sum(fn.extents[i].Len()) -- but that can't happen + // sum(fn.segments[i].Len()) -- but that can't happen // because we have ensured fn.fileinfo.size is always // accurate. - extLen := int64(fn.extents[ptr.extentIdx].Len()) - if off+extLen > ptr.off { - ptr.extentOff = int(ptr.off - off) + segLen := int64(fn.segments[ptr.segmentIdx].Len()) + if off+segLen > ptr.off { + ptr.segmentOff = int(ptr.off - off) break } - off += extLen + off += segLen } return } -func (fn *filenode) appendExtent(e extent) { - fn.Lock() - defer fn.Unlock() - fn.extents = append(fn.extents, e) +// caller must have lock +func (fn *filenode) appendSegment(e segment) { + fn.segments = append(fn.segments, e) fn.fileinfo.size += int64(e.Len()) } func (fn *filenode) Parent() inode { + fn.RLock() + defer fn.RUnlock() return fn.parent } @@ -232,24 +268,27 @@ func (fn *filenode) Readdir() []os.FileInfo { return nil } +// Read reads file data from a single segment, starting at startPtr, +// into p. startPtr is assumed not to be up-to-date. Caller must have +// RLock or Lock. func (fn *filenode) Read(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) { ptr = fn.seek(startPtr) if ptr.off < 0 { err = ErrNegativeOffset return } - if ptr.extentIdx >= len(fn.extents) { + if ptr.segmentIdx >= len(fn.segments) { err = io.EOF return } - n, err = fn.extents[ptr.extentIdx].ReadAt(p, int64(ptr.extentOff)) + n, err = fn.segments[ptr.segmentIdx].ReadAt(p, int64(ptr.segmentOff)) if n > 0 { ptr.off += int64(n) - ptr.extentOff += n - if ptr.extentOff == fn.extents[ptr.extentIdx].Len() { - ptr.extentIdx++ - ptr.extentOff = 0 - if ptr.extentIdx < len(fn.extents) && err == io.EOF { + ptr.segmentOff += n + if ptr.segmentOff == fn.segments[ptr.segmentIdx].Len() { + ptr.segmentIdx++ + ptr.segmentOff = 0 + if ptr.segmentIdx < len(fn.segments) && err == io.EOF { err = nil } } @@ -272,53 +311,65 @@ func (fn *filenode) Stat() os.FileInfo { func (fn *filenode) Truncate(size int64) error { fn.Lock() defer fn.Unlock() + return fn.truncate(size) +} + +func (fn *filenode) truncate(size int64) error { + if size == fn.fileinfo.size { + return nil + } + fn.repacked++ if size < fn.fileinfo.size { - ptr := fn.seek(filenodePtr{off: size, repacked: fn.repacked - 1}) - for i := ptr.extentIdx; i < len(fn.extents); i++ { - if ext, ok := fn.extents[i].(*memExtent); ok { - fn.memsize -= int64(ext.Len()) + ptr := fn.seek(filenodePtr{off: size}) + for i := ptr.segmentIdx; i < len(fn.segments); i++ { + if seg, ok := fn.segments[i].(*memSegment); ok { + fn.memsize -= int64(seg.Len()) } } - if ptr.extentOff == 0 { - fn.extents = fn.extents[:ptr.extentIdx] + if ptr.segmentOff == 0 { + fn.segments = fn.segments[:ptr.segmentIdx] } else { - fn.extents = fn.extents[:ptr.extentIdx+1] - switch ext := fn.extents[ptr.extentIdx].(type) { - case *memExtent: - ext.Truncate(ptr.extentOff) - fn.memsize += int64(ext.Len()) + fn.segments = fn.segments[:ptr.segmentIdx+1] + switch seg := fn.segments[ptr.segmentIdx].(type) { + case *memSegment: + seg.Truncate(ptr.segmentOff) + fn.memsize += int64(seg.Len()) default: - fn.extents[ptr.extentIdx] = ext.Slice(0, ptr.extentOff) + fn.segments[ptr.segmentIdx] = seg.Slice(0, ptr.segmentOff) } } fn.fileinfo.size = size - fn.repacked++ return nil } for size > fn.fileinfo.size { grow := size - fn.fileinfo.size - var e writableExtent + var seg *memSegment var ok bool - if len(fn.extents) == 0 { - e = &memExtent{} - fn.extents = append(fn.extents, e) - } else if e, ok = fn.extents[len(fn.extents)-1].(writableExtent); !ok || e.Len() >= maxBlockSize { - e = &memExtent{} - fn.extents = append(fn.extents, e) - } else { - fn.repacked++ + if len(fn.segments) == 0 { + seg = &memSegment{} + fn.segments = append(fn.segments, seg) + } else if seg, ok = fn.segments[len(fn.segments)-1].(*memSegment); !ok || seg.Len() >= maxBlockSize { + seg = &memSegment{} + fn.segments = append(fn.segments, seg) } - if maxgrow := int64(maxBlockSize - e.Len()); maxgrow < grow { + if maxgrow := int64(maxBlockSize - seg.Len()); maxgrow < grow { grow = maxgrow } - e.Truncate(e.Len() + int(grow)) + seg.Truncate(seg.Len() + int(grow)) fn.fileinfo.size += grow fn.memsize += grow } return nil } +// Write writes data from p to the file, starting at startPtr, +// extending the file size if necessary. Caller must have Lock. func (fn *filenode) Write(p []byte, startPtr filenodePtr) (n int, ptr filenodePtr, err error) { + if startPtr.off > fn.fileinfo.size { + if err = fn.truncate(startPtr.off); err != nil { + return 0, startPtr, err + } + } ptr = fn.seek(startPtr) if ptr.off < 0 { err = ErrNegativeOffset @@ -329,160 +380,175 @@ func (fn *filenode) Write(p []byte, startPtr filenodePtr) (n int, ptr filenodePt if len(cando) > maxBlockSize { cando = cando[:maxBlockSize] } - // Rearrange/grow fn.extents (and shrink cando if + // Rearrange/grow fn.segments (and shrink cando if // needed) such that cando can be copied to - // fn.extents[ptr.extentIdx] at offset ptr.extentOff. - cur := ptr.extentIdx - prev := ptr.extentIdx - 1 + // fn.segments[ptr.segmentIdx] at offset + // ptr.segmentOff. + cur := ptr.segmentIdx + prev := ptr.segmentIdx - 1 var curWritable bool - if cur < len(fn.extents) { - _, curWritable = fn.extents[cur].(writableExtent) + if cur < len(fn.segments) { + _, curWritable = fn.segments[cur].(*memSegment) } var prevAppendable bool - if prev >= 0 && fn.extents[prev].Len() < maxBlockSize { - _, prevAppendable = fn.extents[prev].(writableExtent) + if prev >= 0 && fn.segments[prev].Len() < maxBlockSize { + _, prevAppendable = fn.segments[prev].(*memSegment) } - if ptr.extentOff > 0 && !curWritable { + if ptr.segmentOff > 0 && !curWritable { // Split a non-writable block. - if max := fn.extents[cur].Len() - ptr.extentOff; max <= len(cando) { + if max := fn.segments[cur].Len() - ptr.segmentOff; max <= len(cando) { // Truncate cur, and insert a new - // extent after it. + // segment after it. cando = cando[:max] - fn.extents = append(fn.extents, nil) - copy(fn.extents[cur+1:], fn.extents[cur:]) + fn.segments = append(fn.segments, nil) + copy(fn.segments[cur+1:], fn.segments[cur:]) } else { // Split cur into two copies, truncate // the one on the left, shift the one // on the right, and insert a new - // extent between them. - fn.extents = append(fn.extents, nil, nil) - copy(fn.extents[cur+2:], fn.extents[cur:]) - fn.extents[cur+2] = fn.extents[cur+2].Slice(ptr.extentOff+len(cando), -1) + // segment between them. + fn.segments = append(fn.segments, nil, nil) + copy(fn.segments[cur+2:], fn.segments[cur:]) + fn.segments[cur+2] = fn.segments[cur+2].Slice(ptr.segmentOff+len(cando), -1) } cur++ prev++ - e := &memExtent{} - e.Truncate(len(cando)) + seg := &memSegment{} + seg.Truncate(len(cando)) fn.memsize += int64(len(cando)) - fn.extents[cur] = e - fn.extents[prev] = fn.extents[prev].Slice(0, ptr.extentOff) - ptr.extentIdx++ - ptr.extentOff = 0 + fn.segments[cur] = seg + fn.segments[prev] = fn.segments[prev].Slice(0, ptr.segmentOff) + ptr.segmentIdx++ + ptr.segmentOff = 0 fn.repacked++ ptr.repacked++ } else if curWritable { - if fit := int(fn.extents[cur].Len()) - ptr.extentOff; fit < len(cando) { + if fit := int(fn.segments[cur].Len()) - ptr.segmentOff; fit < len(cando) { cando = cando[:fit] } } else { if prevAppendable { - // Shrink cando if needed to fit in prev extent. - if cangrow := maxBlockSize - fn.extents[prev].Len(); cangrow < len(cando) { + // Shrink cando if needed to fit in + // prev segment. + if cangrow := maxBlockSize - fn.segments[prev].Len(); cangrow < len(cando) { cando = cando[:cangrow] } } - if cur == len(fn.extents) { + if cur == len(fn.segments) { // ptr is at EOF, filesize is changing. fn.fileinfo.size += int64(len(cando)) - } else if el := fn.extents[cur].Len(); el <= len(cando) { + } else if el := fn.segments[cur].Len(); el <= len(cando) { // cando is long enough that we won't // need cur any more. shrink cando to // be exactly as long as cur // (otherwise we'd accidentally shift // the effective position of all - // extents after cur). + // segments after cur). cando = cando[:el] - copy(fn.extents[cur:], fn.extents[cur+1:]) - fn.extents = fn.extents[:len(fn.extents)-1] + copy(fn.segments[cur:], fn.segments[cur+1:]) + fn.segments = fn.segments[:len(fn.segments)-1] } else { // shrink cur by the same #bytes we're growing prev - fn.extents[cur] = fn.extents[cur].Slice(len(cando), -1) + fn.segments[cur] = fn.segments[cur].Slice(len(cando), -1) } if prevAppendable { // Grow prev. - ptr.extentIdx-- - ptr.extentOff = fn.extents[prev].Len() - fn.extents[prev].(writableExtent).Truncate(ptr.extentOff + len(cando)) + ptr.segmentIdx-- + ptr.segmentOff = fn.segments[prev].Len() + fn.segments[prev].(*memSegment).Truncate(ptr.segmentOff + len(cando)) fn.memsize += int64(len(cando)) ptr.repacked++ fn.repacked++ } else { - // Insert an extent between prev and cur, and advance prev/cur. - fn.extents = append(fn.extents, nil) - if cur < len(fn.extents) { - copy(fn.extents[cur+1:], fn.extents[cur:]) + // Insert a segment between prev and + // cur, and advance prev/cur. + fn.segments = append(fn.segments, nil) + if cur < len(fn.segments) { + copy(fn.segments[cur+1:], fn.segments[cur:]) ptr.repacked++ fn.repacked++ } else { - // appending a new extent does + // appending a new segment does // not invalidate any ptrs } - e := &memExtent{} - e.Truncate(len(cando)) + seg := &memSegment{} + seg.Truncate(len(cando)) fn.memsize += int64(len(cando)) - fn.extents[cur] = e + fn.segments[cur] = seg cur++ prev++ } } - // Finally we can copy bytes from cando to the current extent. - fn.extents[ptr.extentIdx].(writableExtent).WriteAt(cando, ptr.extentOff) + // Finally we can copy bytes from cando to the current segment. + fn.segments[ptr.segmentIdx].(*memSegment).WriteAt(cando, ptr.segmentOff) n += len(cando) p = p[len(cando):] ptr.off += int64(len(cando)) - ptr.extentOff += len(cando) - if ptr.extentOff >= maxBlockSize { - fn.pruneMemExtents() + ptr.segmentOff += len(cando) + if ptr.segmentOff >= maxBlockSize { + fn.pruneMemSegments() } - if fn.extents[ptr.extentIdx].Len() == ptr.extentOff { - ptr.extentOff = 0 - ptr.extentIdx++ + if fn.segments[ptr.segmentIdx].Len() == ptr.segmentOff { + ptr.segmentOff = 0 + ptr.segmentIdx++ } + + fn.fileinfo.modTime = time.Now() } return } // Write some data out to disk to reduce memory use. Caller must have // write lock. -func (fn *filenode) pruneMemExtents() { +func (fn *filenode) pruneMemSegments() { // TODO: async (don't hold Lock() while waiting for Keep) // TODO: share code with (*dirnode)sync() // TODO: pack/flush small blocks too, when fragmented - for idx, ext := range fn.extents { - ext, ok := ext.(*memExtent) - if !ok || ext.Len() < maxBlockSize { + for idx, seg := range fn.segments { + seg, ok := seg.(*memSegment) + if !ok || seg.Len() < maxBlockSize { continue } - locator, _, err := fn.parent.kc.PutB(ext.buf) + locator, _, err := fn.parent.kc.PutB(seg.buf) if err != nil { // TODO: stall (or return errors from) // subsequent writes until flushing // starts to succeed continue } - fn.memsize -= int64(ext.Len()) - fn.extents[idx] = storedExtent{ + fn.memsize -= int64(seg.Len()) + fn.segments[idx] = storedSegment{ kc: fn.parent.kc, locator: locator, - size: ext.Len(), + size: seg.Len(), offset: 0, - length: ext.Len(), + length: seg.Len(), } } } // FileSystem returns a CollectionFileSystem for the collection. func (c *Collection) FileSystem(client *Client, kc keepClient) (CollectionFileSystem, error) { + var modTime time.Time + if c.ModifiedAt == nil { + modTime = time.Now() + } else { + modTime = *c.ModifiedAt + } fs := &fileSystem{dirnode: dirnode{ - client: client, - kc: kc, - fileinfo: fileinfo{name: ".", mode: os.ModeDir | 0755}, - parent: nil, - inodes: make(map[string]inode), + client: client, + kc: kc, + fileinfo: fileinfo{ + name: ".", + mode: os.ModeDir | 0755, + modTime: modTime, + }, + parent: nil, + inodes: make(map[string]inode), }} fs.dirnode.parent = &fs.dirnode if err := fs.dirnode.loadManifest(c.ManifestText); err != nil { @@ -491,7 +557,7 @@ func (c *Collection) FileSystem(client *Client, kc keepClient) (CollectionFileSy return fs, nil } -type file struct { +type filehandle struct { inode ptr filenodePtr append bool @@ -500,7 +566,7 @@ type file struct { unreaddirs []os.FileInfo } -func (f *file) Read(p []byte) (n int, err error) { +func (f *filehandle) Read(p []byte) (n int, err error) { if !f.readable { return 0, ErrWriteOnlyMode } @@ -510,23 +576,20 @@ func (f *file) Read(p []byte) (n int, err error) { return } -func (f *file) Seek(off int64, whence int) (pos int64, err error) { +func (f *filehandle) Seek(off int64, whence int) (pos int64, err error) { size := f.inode.Size() ptr := f.ptr switch whence { - case os.SEEK_SET: + case io.SeekStart: ptr.off = off - case os.SEEK_CUR: + case io.SeekCurrent: ptr.off += off - case os.SEEK_END: + case io.SeekEnd: ptr.off = size + off } if ptr.off < 0 { return f.ptr.off, ErrNegativeOffset } - if ptr.off > size { - ptr.off = size - } if ptr.off != f.ptr.off { f.ptr = ptr // force filenode to recompute f.ptr fields on next @@ -536,11 +599,11 @@ func (f *file) Seek(off int64, whence int) (pos int64, err error) { return f.ptr.off, nil } -func (f *file) Truncate(size int64) error { +func (f *filehandle) Truncate(size int64) error { return f.inode.Truncate(size) } -func (f *file) Write(p []byte) (n int, err error) { +func (f *filehandle) Write(p []byte) (n int, err error) { if !f.writable { return 0, ErrReadOnlyFile } @@ -548,17 +611,17 @@ func (f *file) Write(p []byte) (n int, err error) { defer f.inode.Unlock() if fn, ok := f.inode.(*filenode); ok && f.append { f.ptr = filenodePtr{ - off: fn.fileinfo.size, - extentIdx: len(fn.extents), - extentOff: 0, - repacked: fn.repacked, + off: fn.fileinfo.size, + segmentIdx: len(fn.segments), + segmentOff: 0, + repacked: fn.repacked, } } n, f.ptr, err = f.inode.Write(p, f.ptr) return } -func (f *file) Readdir(count int) ([]os.FileInfo, error) { +func (f *filehandle) Readdir(count int) ([]os.FileInfo, error) { if !f.inode.Stat().IsDir() { return nil, ErrInvalidOperation } @@ -579,12 +642,11 @@ func (f *file) Readdir(count int) ([]os.FileInfo, error) { return ret, nil } -func (f *file) Stat() (os.FileInfo, error) { +func (f *filehandle) Stat() (os.FileInfo, error) { return f.inode.Stat(), nil } -func (f *file) Close() error { - // FIXME: flush +func (f *filehandle) Close() error { return nil } @@ -613,7 +675,7 @@ func (dn *dirnode) sync() error { } block := make([]byte, 0, maxBlockSize) for _, sb := range sbs { - block = append(block, sb.fn.extents[sb.idx].(*memExtent).buf...) + block = append(block, sb.fn.segments[sb.idx].(*memSegment).buf...) } locator, _, err := dn.kc.PutB(block) if err != nil { @@ -621,8 +683,8 @@ func (dn *dirnode) sync() error { } off := 0 for _, sb := range sbs { - data := sb.fn.extents[sb.idx].(*memExtent).buf - sb.fn.extents[sb.idx] = storedExtent{ + data := sb.fn.segments[sb.idx].(*memSegment).buf + sb.fn.segments[sb.idx] = storedSegment{ kc: dn.kc, locator: locator, size: len(block), @@ -648,18 +710,18 @@ func (dn *dirnode) sync() error { } fn.Lock() defer fn.Unlock() - for idx, ext := range fn.extents { - ext, ok := ext.(*memExtent) + for idx, seg := range fn.segments { + seg, ok := seg.(*memSegment) if !ok { continue } - if ext.Len() > maxBlockSize/2 { + if seg.Len() > maxBlockSize/2 { if err := flush([]shortBlock{{fn, idx}}); err != nil { return err } continue } - if pendingLen+ext.Len() > maxBlockSize { + if pendingLen+seg.Len() > maxBlockSize { if err := flush(pending); err != nil { return err } @@ -667,7 +729,7 @@ func (dn *dirnode) sync() error { pendingLen = 0 } pending = append(pending, shortBlock{fn, idx}) - pendingLen += ext.Len() + pendingLen += seg.Len() } } return flush(pending) @@ -682,12 +744,12 @@ func (dn *dirnode) MarshalManifest(prefix string) (string, error) { // caller must have read lock. func (dn *dirnode) marshalManifest(prefix string) (string, error) { var streamLen int64 - type m1segment struct { + type filepart struct { name string offset int64 length int64 } - var segments []m1segment + var fileparts []filepart var subdirs string var blocks []string @@ -704,8 +766,7 @@ func (dn *dirnode) marshalManifest(prefix string) (string, error) { sort.Strings(names) for _, name := range names { - node := dn.inodes[name] - switch node := node.(type) { + switch node := dn.inodes[name].(type) { case *dirnode: subdir, err := node.marshalManifest(prefix + "/" + name) if err != nil { @@ -713,36 +774,36 @@ func (dn *dirnode) marshalManifest(prefix string) (string, error) { } subdirs = subdirs + subdir case *filenode: - if len(node.extents) == 0 { - segments = append(segments, m1segment{name: name}) + if len(node.segments) == 0 { + fileparts = append(fileparts, filepart{name: name}) break } - for _, e := range node.extents { - switch e := e.(type) { - case storedExtent: - if len(blocks) > 0 && blocks[len(blocks)-1] == e.locator { - streamLen -= int64(e.size) + for _, seg := range node.segments { + switch seg := seg.(type) { + case storedSegment: + if len(blocks) > 0 && blocks[len(blocks)-1] == seg.locator { + streamLen -= int64(seg.size) } else { - blocks = append(blocks, e.locator) + blocks = append(blocks, seg.locator) } - next := m1segment{ + next := filepart{ name: name, - offset: streamLen + int64(e.offset), - length: int64(e.length), + offset: streamLen + int64(seg.offset), + length: int64(seg.length), } - if prev := len(segments) - 1; prev >= 0 && - segments[prev].name == name && - segments[prev].offset+segments[prev].length == next.offset { - segments[prev].length += next.length + if prev := len(fileparts) - 1; prev >= 0 && + fileparts[prev].name == name && + fileparts[prev].offset+fileparts[prev].length == next.offset { + fileparts[prev].length += next.length } else { - segments = append(segments, next) + fileparts = append(fileparts, next) } - streamLen += int64(e.size) + streamLen += int64(seg.size) default: // This can't happen: we // haven't unlocked since // calling sync(). - panic(fmt.Sprintf("can't marshal extent type %T", e)) + panic(fmt.Sprintf("can't marshal segment type %T", seg)) } } default: @@ -750,7 +811,7 @@ func (dn *dirnode) marshalManifest(prefix string) (string, error) { } } var filetokens []string - for _, s := range segments { + for _, s := range fileparts { filetokens = append(filetokens, fmt.Sprintf("%d:%d:%s", s.offset, s.length, manifestEscape(s.name))) } if len(filetokens) == 0 { @@ -762,16 +823,19 @@ func (dn *dirnode) marshalManifest(prefix string) (string, error) { } func (dn *dirnode) loadManifest(txt string) error { - // FIXME: faster var dirname string streams := strings.Split(txt, "\n") if streams[len(streams)-1] != "" { return fmt.Errorf("line %d: no trailing newline", len(streams)) } - for i, stream := range streams[:len(streams)-1] { + streams = streams[:len(streams)-1] + segments := []storedSegment{} + for i, stream := range streams { lineno := i + 1 - var extents []storedExtent var anyFileTokens bool + var pos int64 + var segIdx int + segments = segments[:0] for i, token := range strings.Split(stream, " ") { if i == 0 { dirname = manifestUnescape(token) @@ -789,18 +853,18 @@ func (dn *dirnode) loadManifest(txt string) error { if err != nil || length < 0 { return fmt.Errorf("line %d: bad locator %q", lineno, token) } - extents = append(extents, storedExtent{ + segments = append(segments, storedSegment{ locator: token, size: int(length), offset: 0, length: int(length), }) continue - } else if len(extents) == 0 { + } else if len(segments) == 0 { return fmt.Errorf("line %d: bad locator %q", lineno, token) } - toks := strings.Split(token, ":") + toks := strings.SplitN(token, ":", 3) if len(toks) != 3 { return fmt.Errorf("line %d: bad file segment %q", lineno, token) } @@ -814,57 +878,59 @@ func (dn *dirnode) loadManifest(txt string) error { if err != nil || length < 0 { return fmt.Errorf("line %d: bad file segment %q", lineno, token) } - name := path.Clean(dirname + "/" + manifestUnescape(toks[2])) - err = dn.makeParentDirs(name) + name := dirname + "/" + manifestUnescape(toks[2]) + fnode, err := dn.createFileAndParents(name) if err != nil { return fmt.Errorf("line %d: cannot use path %q: %s", lineno, name, err) } - f, err := dn.OpenFile(name, os.O_CREATE|os.O_WRONLY|os.O_APPEND, 0700) - if err != nil { - return fmt.Errorf("line %d: cannot append to %q: %s", lineno, name, err) - } - if f.inode.Stat().IsDir() { - f.Close() - return fmt.Errorf("line %d: cannot append to %q: is a directory", lineno, name) - } // Map the stream offset/range coordinates to // block/offset/range coordinates and add - // corresponding storedExtents to the filenode - var pos int64 - for _, e := range extents { - next := pos + int64(e.Len()) - if next < offset { + // corresponding storedSegments to the filenode + if pos > offset { + // Can't continue where we left off. + // TODO: binary search instead of + // rewinding all the way (but this + // situation might be rare anyway) + segIdx, pos = 0, 0 + } + for next := int64(0); segIdx < len(segments); segIdx++ { + seg := segments[segIdx] + next = pos + int64(seg.Len()) + if next <= offset || seg.Len() == 0 { pos = next continue } - if pos > offset+length { + if pos >= offset+length { break } var blkOff int if pos < offset { blkOff = int(offset - pos) } - blkLen := e.Len() - blkOff + blkLen := seg.Len() - blkOff if pos+int64(blkOff+blkLen) > offset+length { blkLen = int(offset + length - pos - int64(blkOff)) } - f.inode.(*filenode).appendExtent(storedExtent{ + fnode.appendSegment(storedSegment{ kc: dn.kc, - locator: e.locator, - size: e.size, + locator: seg.locator, + size: seg.size, offset: blkOff, length: blkLen, }) - pos = next + if next > offset+length { + break + } else { + pos = next + } } - f.Close() - if pos < offset+length { + if segIdx == len(segments) && pos < offset+length { return fmt.Errorf("line %d: invalid segment in %d-byte stream: %q", lineno, pos, token) } } if !anyFileTokens { return fmt.Errorf("line %d: no file segments", lineno) - } else if len(extents) == 0 { + } else if len(segments) == 0 { return fmt.Errorf("line %d: no locators", lineno) } else if dirname == "" { return fmt.Errorf("line %d: no stream name", lineno) @@ -873,24 +939,43 @@ func (dn *dirnode) loadManifest(txt string) error { return nil } -func (dn *dirnode) makeParentDirs(name string) (err error) { - names := strings.Split(name, "/") +// only safe to call from loadManifest -- no locking +func (dn *dirnode) createFileAndParents(path string) (fn *filenode, err error) { + names := strings.Split(path, "/") + basename := names[len(names)-1] + if basename == "" || basename == "." || basename == ".." { + err = fmt.Errorf("invalid filename") + return + } for _, name := range names[:len(names)-1] { - f, err := dn.OpenFile(name, os.O_CREATE, os.ModeDir|0755) - if err != nil { - return err - } - defer f.Close() - var ok bool - dn, ok = f.inode.(*dirnode) - if !ok { - return ErrFileExists + switch name { + case "", ".": + case "..": + dn = dn.parent + default: + switch node := dn.inodes[name].(type) { + case nil: + dn = dn.newDirnode(name, 0755, dn.fileinfo.modTime) + case *dirnode: + dn = node + case *filenode: + err = ErrFileExists + return + } } } - return nil + switch node := dn.inodes[basename].(type) { + case nil: + fn = dn.newFilenode(basename, 0755, dn.fileinfo.modTime) + case *filenode: + fn = node + case *dirnode: + err = ErrIsDirectory + } + return } -func (dn *dirnode) mkdir(name string) (*file, error) { +func (dn *dirnode) mkdir(name string) (*filehandle, error) { return dn.OpenFile(name, os.O_CREATE|os.O_EXCL, os.ModeDir|0755) } @@ -903,9 +988,23 @@ func (dn *dirnode) Mkdir(name string, perm os.FileMode) error { } func (dn *dirnode) Remove(name string) error { + return dn.remove(strings.TrimRight(name, "/"), false) +} + +func (dn *dirnode) RemoveAll(name string) error { + err := dn.remove(strings.TrimRight(name, "/"), true) + if os.IsNotExist(err) { + // "If the path does not exist, RemoveAll returns + // nil." (see "os" pkg) + err = nil + } + return err +} + +func (dn *dirnode) remove(name string, recursive bool) error { dirname, name := path.Split(name) if name == "" || name == "." || name == ".." { - return ErrInvalidOperation + return ErrInvalidArgument } dn, ok := dn.lookupPath(dirname).(*dirnode) if !ok { @@ -919,7 +1018,7 @@ func (dn *dirnode) Remove(name string) error { case *dirnode: node.RLock() defer node.RUnlock() - if len(node.inodes) > 0 { + if !recursive && len(node.inodes) > 0 { return ErrDirectoryNotEmpty } } @@ -927,6 +1026,94 @@ func (dn *dirnode) Remove(name string) error { return nil } +func (dn *dirnode) Rename(oldname, newname string) error { + olddir, oldname := path.Split(oldname) + if oldname == "" || oldname == "." || oldname == ".." { + return ErrInvalidArgument + } + olddirf, err := dn.OpenFile(olddir+".", os.O_RDONLY, 0) + if err != nil { + return fmt.Errorf("%q: %s", olddir, err) + } + defer olddirf.Close() + newdir, newname := path.Split(newname) + if newname == "." || newname == ".." { + return ErrInvalidArgument + } else if newname == "" { + // Rename("a/b", "c/") means Rename("a/b", "c/b") + newname = oldname + } + newdirf, err := dn.OpenFile(newdir+".", os.O_RDONLY, 0) + if err != nil { + return fmt.Errorf("%q: %s", newdir, err) + } + defer newdirf.Close() + + // When acquiring locks on multiple nodes, all common + // ancestors must be locked first in order to avoid + // deadlock. This is assured by locking the path from root to + // newdir, then locking the path from root to olddir, skipping + // any already-locked nodes. + needLock := []sync.Locker{} + for _, f := range []*filehandle{olddirf, newdirf} { + node := f.inode + needLock = append(needLock, node) + for node.Parent() != node { + node = node.Parent() + needLock = append(needLock, node) + } + } + locked := map[sync.Locker]bool{} + for i := len(needLock) - 1; i >= 0; i-- { + if n := needLock[i]; !locked[n] { + n.Lock() + defer n.Unlock() + locked[n] = true + } + } + + olddn := olddirf.inode.(*dirnode) + newdn := newdirf.inode.(*dirnode) + oldinode, ok := olddn.inodes[oldname] + if !ok { + return os.ErrNotExist + } + if locked[oldinode] { + // oldinode cannot become a descendant of itself. + return ErrInvalidArgument + } + if existing, ok := newdn.inodes[newname]; ok { + // overwriting an existing file or dir + if dn, ok := existing.(*dirnode); ok { + if !oldinode.Stat().IsDir() { + return ErrIsDirectory + } + dn.RLock() + defer dn.RUnlock() + if len(dn.inodes) > 0 { + return ErrDirectoryNotEmpty + } + } + } else { + if newdn.inodes == nil { + newdn.inodes = make(map[string]inode) + } + newdn.fileinfo.size++ + } + newdn.inodes[newname] = oldinode + switch n := oldinode.(type) { + case *dirnode: + n.parent = newdn + case *filenode: + n.parent = newdn + default: + panic(fmt.Sprintf("bad inode type %T", n)) + } + delete(olddn.inodes, oldname) + olddn.fileinfo.size-- + return nil +} + func (dn *dirnode) Parent() inode { dn.RLock() defer dn.RUnlock() @@ -991,7 +1178,44 @@ func (dn *dirnode) lookupPath(path string) (node inode) { return } -func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*file, error) { +func (dn *dirnode) newDirnode(name string, perm os.FileMode, modTime time.Time) *dirnode { + child := &dirnode{ + parent: dn, + client: dn.client, + kc: dn.kc, + fileinfo: fileinfo{ + name: name, + mode: os.ModeDir | perm, + modTime: modTime, + }, + } + if dn.inodes == nil { + dn.inodes = make(map[string]inode) + } + dn.inodes[name] = child + dn.fileinfo.size++ + return child +} + +func (dn *dirnode) newFilenode(name string, perm os.FileMode, modTime time.Time) *filenode { + child := &filenode{ + parent: dn, + fileinfo: fileinfo{ + name: name, + mode: perm, + modTime: modTime, + }, + } + if dn.inodes == nil { + dn.inodes = make(map[string]inode) + } + dn.inodes[name] = child + dn.fileinfo.size++ + return child +} + +// OpenFile is analogous to os.OpenFile(). +func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*filehandle, error) { if flag&os.O_SYNC != 0 { return nil, ErrSyncNotSupported } @@ -1017,9 +1241,9 @@ func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*file, err // "foo/..". switch name { case ".", "": - return &file{inode: dn}, nil + return &filehandle{inode: dn}, nil case "..": - return &file{inode: dn.Parent()}, nil + return &filehandle{inode: dn.Parent()}, nil } } createMode := flag&os.O_CREATE != 0 @@ -1036,29 +1260,10 @@ func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*file, err return nil, os.ErrNotExist } if perm.IsDir() { - n = &dirnode{ - parent: dn, - client: dn.client, - kc: dn.kc, - fileinfo: fileinfo{ - name: name, - mode: os.ModeDir | 0755, - }, - } + n = dn.newDirnode(name, 0755, time.Now()) } else { - n = &filenode{ - parent: dn, - fileinfo: fileinfo{ - name: name, - mode: 0755, - }, - } - } - if dn.inodes == nil { - dn.inodes = make(map[string]inode) + n = dn.newFilenode(name, 0755, time.Now()) } - dn.inodes[name] = n - dn.fileinfo.size++ } else if flag&os.O_EXCL != 0 { return nil, ErrFileExists } else if flag&os.O_TRUNC != 0 { @@ -1070,7 +1275,7 @@ func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*file, err fn.Truncate(0) } } - return &file{ + return &filehandle{ inode: n, append: flag&os.O_APPEND != 0, readable: readable, @@ -1078,38 +1283,32 @@ func (dn *dirnode) OpenFile(name string, flag int, perm os.FileMode) (*file, err }, nil } -type extent interface { +type segment interface { io.ReaderAt Len() int - // Return a new extent with a subsection of the data from this + // Return a new segment with a subsection of the data from this // one. length<0 means length=Len()-off. - Slice(off int, length int) extent -} - -type writableExtent interface { - extent - WriteAt(p []byte, off int) - Truncate(n int) + Slice(off int, length int) segment } -type memExtent struct { +type memSegment struct { buf []byte } -func (me *memExtent) Len() int { +func (me *memSegment) Len() int { return len(me.buf) } -func (me *memExtent) Slice(off, length int) extent { +func (me *memSegment) Slice(off, length int) segment { if length < 0 { length = len(me.buf) - off } buf := make([]byte, length) copy(buf, me.buf[off:]) - return &memExtent{buf: buf} + return &memSegment{buf: buf} } -func (me *memExtent) Truncate(n int) { +func (me *memSegment) Truncate(n int) { if n > cap(me.buf) { newsize := 1024 for newsize < n { @@ -1128,14 +1327,14 @@ func (me *memExtent) Truncate(n int) { me.buf = me.buf[:n] } -func (me *memExtent) WriteAt(p []byte, off int) { +func (me *memSegment) WriteAt(p []byte, off int) { if off+len(p) > len(me.buf) { - panic("overflowed extent") + panic("overflowed segment") } copy(me.buf[off:], p) } -func (me *memExtent) ReadAt(p []byte, off int64) (n int, err error) { +func (me *memSegment) ReadAt(p []byte, off int64) (n int, err error) { if off > int64(me.Len()) { err = io.EOF return @@ -1147,19 +1346,19 @@ func (me *memExtent) ReadAt(p []byte, off int64) (n int, err error) { return } -type storedExtent struct { +type storedSegment struct { kc keepClient locator string - size int - offset int - length int + size int // size of stored block (also encoded in locator) + offset int // position of segment within the stored block + length int // bytes in this segment (offset + length <= size) } -func (se storedExtent) Len() int { +func (se storedSegment) Len() int { return se.length } -func (se storedExtent) Slice(n, size int) extent { +func (se storedSegment) Slice(n, size int) segment { se.offset += n se.length -= n if size >= 0 && se.length > size { @@ -1168,7 +1367,7 @@ func (se storedExtent) Slice(n, size int) extent { return se } -func (se storedExtent) ReadAt(p []byte, off int64) (n int, err error) { +func (se storedSegment) ReadAt(p []byte, off int64) (n int, err error) { if off > int64(se.length) { return 0, io.EOF } @@ -1194,7 +1393,7 @@ func canonicalName(name string) string { return name } -var manifestEscapeSeq = regexp.MustCompile(`\\([0-9]{3}|\\)`) +var manifestEscapeSeq = regexp.MustCompile(`\\([0-7]{3}|\\)`) func manifestUnescapeFunc(seq string) string { if seq == `\\` { @@ -1212,7 +1411,7 @@ func manifestUnescape(s string) string { return manifestEscapeSeq.ReplaceAllStringFunc(s, manifestUnescapeFunc) } -var manifestEscapedChar = regexp.MustCompile(`[^\.\w/]`) +var manifestEscapedChar = regexp.MustCompile(`[\000-\040:\s\\]`) func manifestEscapeFunc(seq string) string { return fmt.Sprintf("\\%03o", byte(seq[0]))