more fuse

6 files changed, 368 insertions, 72 deletions

diff --git a/cmd/btrfs-mount/subvol.go b/cmd/btrfs-mount/subvol.go
index 7c6a7ac..e4e0460 100644
--- a/cmd/btrfs-mount/subvol.go
+++ b/cmd/btrfs-mount/subvol.go
@@ -3,17 +3,19 @@ package main
 import (
 	"context"
 	"fmt"
+	"reflect"
 	"sync"
 
 	"github.com/datawire/dlib/dcontext"
 	"github.com/datawire/dlib/dlog"
+	lru "github.com/hashicorp/golang-lru"
 	"github.com/jacobsa/fuse"
-	"github.com/jacobsa/fuse/fuseops"
 	"github.com/jacobsa/fuse/fuseutil"
 
 	"lukeshu.com/btrfs-tools/pkg/btrfs"
 	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
 	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol"
+	"lukeshu.com/btrfs-tools/pkg/util"
 )
 
 type Subvolume struct {
@@ -22,11 +24,14 @@ type Subvolume struct {
 	Mountpoint string
 	TreeID     btrfs.ObjID
 
-	fuseutil.NotImplementedFileSystem
-
 	rootOnce sync.Once
 	rootVal  btrfsitem.Root
 	rootErr  error
+
+	inodeCache *lru.ARCCache
+	dirCache   *lru.ARCCache
+
+	subvolumeFUSE
 }
 
 func (sv *Subvolume) Run(ctx context.Context) error {
@@ -49,7 +54,7 @@ func (sv *Subvolume) Run(ctx context.Context) error {
 	return mount.Join(dcontext.HardContext(ctx))
 }
 
-func (sv *Subvolume) initRoot() {
+func (sv *Subvolume) init() {
 	sv.rootOnce.Do(func() {
 		sb, err := sv.FS.Superblock()
 		if err != nil {
@@ -74,96 +79,157 @@ func (sv *Subvolume) initRoot() {
 		}
 
 		sv.rootVal = rootBody
+
+		sv.inodeCache, _ = lru.NewARC(128)
+		sv.dirCache, _ = lru.NewARC(128)
+
+		sv.subvolumeFUSE.init()
 	})
 }
 
 func (sv *Subvolume) getRootInode() (btrfs.ObjID, error) {
-	sv.initRoot()
+	sv.init()
 	return sv.rootVal.RootDirID, sv.rootErr
 }
 
 func (sv *Subvolume) getFSTree() (btrfsvol.LogicalAddr, error) {
-	sv.initRoot()
+	sv.init()
 	return sv.rootVal.ByteNr, sv.rootErr
 }
 
-func (sv *Subvolume) StatFS(_ context.Context, op *fuseops.StatFSOp) error {
-	// See linux.git/fs/btrfs/super.c:btrfs_statfs()
-	sb, err := sv.FS.Superblock()
-	if err != nil {
-		return err
-	}
-
-	op.IoSize = sb.Data.SectorSize
-	op.BlockSize = sb.Data.SectorSize
-	op.Blocks = sb.Data.TotalBytes / uint64(sb.Data.SectorSize) // TODO: adjust for RAID type
-	//op.BlocksFree = TODO
-
-	// btrfs doesn't have a fixed number of inodes
-	op.Inodes = 0
-	op.InodesFree = 0
-
-	// jacobsa/fuse doesn't expose namelen, instead hard-coding it
-	// to 255.  Which is fine by us, because that's what it is for
-	// btrfs.
-
-	return nil
-}
-
-// func (sv *Subvolume) LookUpInode(_ context.Context, op *fuseops.LookUpInodeOp) error               {}
-
-func (sv *Subvolume) GetInodeAttributes(ctx context.Context, op *fuseops.GetInodeAttributesOp) error {
-	if op.Inode == fuseops.RootInodeID {
-		inode, err := sv.getRootInode()
-		if err != nil {
-			return err
-		}
-		op.Inode = fuseops.InodeID(inode)
-	}
-
+func (sv *Subvolume) loadInode(inode btrfs.ObjID) (btrfsitem.Inode, error) {
 	tree, err := sv.getFSTree()
 	if err != nil {
-		return err
+		return btrfsitem.Inode{}, nil
+	}
+	if ret, ok := sv.inodeCache.Get(inode); ok {
+		return ret.(btrfsitem.Inode), nil
 	}
-
 	item, err := sv.FS.TreeLookup(tree, btrfs.Key{
-		ObjectID: btrfs.ObjID(op.Inode),
+		ObjectID: inode,
 		ItemType: btrfsitem.INODE_ITEM_KEY,
 		Offset:   0,
 	})
 	if err != nil {
-		return err
+		return btrfsitem.Inode{}, err
 	}
 
 	itemBody, ok := item.Body.(btrfsitem.Inode)
 	if !ok {
-		return fmt.Errorf("malformed inode")
+		return btrfsitem.Inode{}, fmt.Errorf("malformed inode")
 	}
 
-	op.Attributes = fuseops.InodeAttributes{
-		Size:  uint64(itemBody.Size),
-		Nlink: uint32(itemBody.NLink),
-		Mode:  uint32(itemBody.Mode),
-		//RDev: itemBody.Rdev, // jacobsa/fuse doesn't expose rdev
-		Atime: itemBody.ATime.ToStd(),
-		Mtime: itemBody.MTime.ToStd(),
-		Ctime: itemBody.CTime.ToStd(),
-		//Crtime: itemBody.OTime,
-		Uid: uint32(itemBody.UID),
-		Gid: uint32(itemBody.GID),
-	}
-	return nil
+	sv.inodeCache.Add(inode, itemBody)
+	return itemBody, nil
+}
+
+type dir struct {
+	Inode           btrfs.ObjID
+	InodeDat        *btrfsitem.Inode
+	ChildrenByName  map[string]btrfsitem.DirEntry
+	ChildrenByIndex map[uint64]btrfsitem.DirEntry
+	Errs            []error
 }
 
-// func (sv *Subvolume) ForgetInode(_ context.Context, op *fuseops.ForgetInodeOp) error               {}
-// func (sv *Subvolume) BatchForget(_ context.Context, op *fuseops.BatchForgetOp) error               {}
-// func (sv *Subvolume) OpenDir(_ context.Context, op *fuseops.OpenDirOp) error                       {}
-// func (sv *Subvolume) ReadDir(_ context.Context, op *fuseops.ReadDirOp) error                       {}
-// func (sv *Subvolume) ReleaseDirHandle(_ context.Context, op *fuseops.ReleaseDirHandleOp) error     {}
-// func (sv *Subvolume) OpenFile(_ context.Context, op *fuseops.OpenFileOp) error                     {}
-// func (sv *Subvolume) ReadFile(_ context.Context, op *fuseops.ReadFileOp) error                     {}
-// func (sv *Subvolume) ReleaseFileHandle(_ context.Context, op *fuseops.ReleaseFileHandleOp) error   {}
-// func (sv *Subvolume) ReadSymlink(_ context.Context, op *fuseops.ReadSymlinkOp) error               {}
-// func (sv *Subvolume) GetXattr(_ context.Context, op *fuseops.GetXattrOp) error                     {}
-// func (sv *Subvolume) ListXattr(_ context.Context, op *fuseops.ListXattrOp) error                   {}
-// func (sv *Subvolume) Destroy()                                                                {}
+func (sv *Subvolume) loadDir(inode btrfs.ObjID) (*dir, error) {
+	tree, err := sv.getFSTree()
+	if err != nil {
+		return nil, err
+	}
+	if ret, ok := sv.dirCache.Get(inode); ok {
+		return ret.(*dir), nil
+	}
+	ret := &dir{
+		Inode:           inode,
+		ChildrenByName:  make(map[string]btrfsitem.DirEntry),
+		ChildrenByIndex: make(map[uint64]btrfsitem.DirEntry),
+	}
+	items, err := sv.FS.TreeSearchAll(tree, func(key btrfs.Key) int {
+		return util.CmpUint(inode, key.ObjectID)
+	})
+	if err != nil {
+		if len(items) == 0 {
+			return nil, err
+		}
+		ret.Errs = append(ret.Errs, err)
+	}
+	for _, item := range items {
+		switch item.Head.Key.ItemType {
+		case btrfsitem.INODE_ITEM_KEY:
+			itemBody := item.Body.(btrfsitem.Inode)
+			if ret.InodeDat != nil {
+				if !reflect.DeepEqual(itemBody, *ret.InodeDat) {
+					ret.Errs = append(ret.Errs, fmt.Errorf("multiple inodes"))
+				}
+				continue
+			}
+			ret.InodeDat = &itemBody
+		case btrfsitem.INODE_REF_KEY:
+			// TODO
+		case btrfsitem.DIR_ITEM_KEY:
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				ret.Errs = append(ret.Errs, fmt.Errorf("multiple direntries in single DIR_ITEM?"))
+				continue
+			}
+			for _, entry := range body {
+				namehash := btrfsitem.NameHash(entry.Name)
+				if namehash != item.Head.Key.Offset {
+					ret.Errs = append(ret.Errs, fmt.Errorf("direntry crc32c mismatch: key=%#x crc32c(%q)=%#x",
+						item.Head.Key.Offset, entry.Name, namehash))
+					continue
+				}
+				if other, exists := ret.ChildrenByName[string(entry.Name)]; exists {
+					if !reflect.DeepEqual(entry, other) {
+						ret.Errs = append(ret.Errs, fmt.Errorf("multiple instances of direntry name %q", entry.Name))
+					}
+					continue
+				}
+				ret.ChildrenByName[string(entry.Name)] = entry
+			}
+		case btrfsitem.DIR_INDEX_KEY:
+			index := item.Head.Key.Offset
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				ret.Errs = append(ret.Errs, fmt.Errorf("multiple direntries in single DIR_INDEX?"))
+				continue
+			}
+			for _, entry := range body {
+				if other, exists := ret.ChildrenByIndex[index]; exists {
+					if !reflect.DeepEqual(entry, other) {
+						ret.Errs = append(ret.Errs, fmt.Errorf("multiple instances of direntry index %v", index))
+					}
+					continue
+				}
+				ret.ChildrenByIndex[index] = entry
+			}
+		//case btrfsitem.XATTR_ITEM_KEY:
+		default:
+			ret.Errs = append(ret.Errs, fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
+		}
+	}
+	entriesWithIndexes := make(map[string]struct{})
+	nextIndex := uint64(2)
+	for index, entry := range ret.ChildrenByIndex {
+		if index+1 > nextIndex {
+			nextIndex = index + 1
+		}
+		entriesWithIndexes[string(entry.Name)] = struct{}{}
+		if other, exists := ret.ChildrenByName[string(entry.Name)]; !exists {
+			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-name direntry for %q", entry.Name))
+			ret.ChildrenByName[string(entry.Name)] = entry
+		} else if !reflect.DeepEqual(entry, other) {
+			ret.Errs = append(ret.Errs, fmt.Errorf("direntry index %v and direntry name %q disagree", index, entry.Name))
+			ret.ChildrenByName[string(entry.Name)] = entry
+		}
+	}
+	for _, name := range util.SortedMapKeys(ret.ChildrenByName) {
+		if _, exists := entriesWithIndexes[name]; !exists {
+			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-index direntry for %q", name))
+			ret.ChildrenByIndex[nextIndex] = ret.ChildrenByName[name]
+			nextIndex++
+		}
+	}
+	sv.dirCache.Add(inode, ret)
+	return ret, nil
+}
diff --git a/cmd/btrfs-mount/subvol_fuse.go b/cmd/btrfs-mount/subvol_fuse.go
new file mode 100644
index 0000000..6ffc7d6
--- /dev/null
+++ b/cmd/btrfs-mount/subvol_fuse.go
@@ -0,0 +1,196 @@
+package main
+
+import (
+	"context"
+	"fmt"
+	"sync/atomic"
+	"syscall"
+
+	"github.com/jacobsa/fuse/fuseops"
+	"github.com/jacobsa/fuse/fuseutil"
+
+	"lukeshu.com/btrfs-tools/pkg/btrfs"
+	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
+	"lukeshu.com/btrfs-tools/pkg/util"
+)
+
+type dirState struct {
+	Dir *dir
+}
+
+type subvolumeFUSE struct {
+	fuseutil.NotImplementedFileSystem
+	lastHandle uint64
+	dirHandles util.SyncMap[uint64, *dirState]
+}
+
+func (sv *subvolumeFUSE) init() {}
+
+func inodeItemToFUSE(itemBody btrfsitem.Inode) fuseops.InodeAttributes {
+	return fuseops.InodeAttributes{
+		Size:  uint64(itemBody.Size),
+		Nlink: uint32(itemBody.NLink),
+		Mode:  uint32(itemBody.Mode),
+		//RDev: itemBody.Rdev, // jacobsa/fuse doesn't expose rdev
+		Atime: itemBody.ATime.ToStd(),
+		Mtime: itemBody.MTime.ToStd(),
+		Ctime: itemBody.CTime.ToStd(),
+		//Crtime: itemBody.OTime,
+		Uid: uint32(itemBody.UID),
+		Gid: uint32(itemBody.GID),
+	}
+}
+
+func (sv *Subvolume) StatFS(_ context.Context, op *fuseops.StatFSOp) error {
+	// See linux.git/fs/btrfs/super.c:btrfs_statfs()
+	sb, err := sv.FS.Superblock()
+	if err != nil {
+		return err
+	}
+
+	op.IoSize = sb.Data.SectorSize
+	op.BlockSize = sb.Data.SectorSize
+	op.Blocks = sb.Data.TotalBytes / uint64(sb.Data.SectorSize) // TODO: adjust for RAID type
+	//op.BlocksFree = TODO
+
+	// btrfs doesn't have a fixed number of inodes
+	op.Inodes = 0
+	op.InodesFree = 0
+
+	// jacobsa/fuse doesn't expose namelen, instead hard-coding it
+	// to 255.  Which is fine by us, because that's what it is for
+	// btrfs.
+
+	return nil
+}
+
+func (sv *Subvolume) LookUpInode(_ context.Context, op *fuseops.LookUpInodeOp) error {
+	if op.Parent == fuseops.RootInodeID {
+		parent, err := sv.getRootInode()
+		if err != nil {
+			return err
+		}
+		op.Parent = fuseops.InodeID(parent)
+	}
+
+	dir, err := sv.loadDir(btrfs.ObjID(op.Parent))
+	if err != nil {
+		return err
+	}
+	entry, ok := dir.ChildrenByName[op.Name]
+	if !ok {
+		return syscall.ENOENT
+	}
+	if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY {
+		return fmt.Errorf("child %q is not an inode: %w", op.Name, syscall.ENOSYS)
+	}
+	inodeItem, err := sv.loadInode(entry.Location.ObjectID)
+	if err != nil {
+		return err
+	}
+	op.Entry = fuseops.ChildInodeEntry{
+		Child:      fuseops.InodeID(entry.Location.ObjectID),
+		Generation: fuseops.GenerationNumber(inodeItem.Sequence),
+		Attributes: inodeItemToFUSE(inodeItem),
+	}
+	return nil
+}
+
+func (sv *Subvolume) GetInodeAttributes(_ context.Context, op *fuseops.GetInodeAttributesOp) error {
+	if op.Inode == fuseops.RootInodeID {
+		inode, err := sv.getRootInode()
+		if err != nil {
+			return err
+		}
+		op.Inode = fuseops.InodeID(inode)
+	}
+
+	inodeItem, err := sv.loadInode(btrfs.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+
+	op.Attributes = inodeItemToFUSE(inodeItem)
+	return nil
+}
+
+func (sv *Subvolume) OpenDir(_ context.Context, op *fuseops.OpenDirOp) error {
+	if op.Inode == fuseops.RootInodeID {
+		inode, err := sv.getRootInode()
+		if err != nil {
+			return err
+		}
+		op.Inode = fuseops.InodeID(inode)
+	}
+
+	dir, err := sv.loadDir(btrfs.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+	handle := atomic.AddUint64(&sv.lastHandle, 1)
+	sv.dirHandles.Store(handle, &dirState{
+		Dir: dir,
+	})
+	op.Handle = fuseops.HandleID(handle)
+	return nil
+}
+
+func (sv *Subvolume) ReadDir(_ context.Context, op *fuseops.ReadDirOp) error {
+	state, ok := sv.dirHandles.Load(uint64(op.Handle))
+	if !ok {
+		return syscall.EBADF
+	}
+	indexes := util.SortedMapKeys(state.Dir.ChildrenByIndex)
+	origOffset := op.Offset
+	for _, index := range indexes {
+		if index < uint64(origOffset) {
+			continue
+		}
+		entry := state.Dir.ChildrenByIndex[index]
+		n := fuseutil.WriteDirent(op.Dst[op.BytesRead:], fuseutil.Dirent{
+			Offset: fuseops.DirOffset(index + 1),
+			Inode:  fuseops.InodeID(entry.Location.ObjectID),
+			Name:   string(entry.Name),
+			Type: map[btrfsitem.FileType]fuseutil.DirentType{
+				btrfsitem.FT_UNKNOWN:  fuseutil.DT_Unknown,
+				btrfsitem.FT_REG_FILE: fuseutil.DT_File,
+				btrfsitem.FT_DIR:      fuseutil.DT_Directory,
+				btrfsitem.FT_CHRDEV:   fuseutil.DT_Char,
+				btrfsitem.FT_BLKDEV:   fuseutil.DT_Block,
+				btrfsitem.FT_FIFO:     fuseutil.DT_FIFO,
+				btrfsitem.FT_SOCK:     fuseutil.DT_Socket,
+				btrfsitem.FT_SYMLINK:  fuseutil.DT_Link,
+			}[entry.Type],
+		})
+		if n == 0 {
+			break
+		}
+		op.BytesRead += n
+	}
+	return nil
+}
+
+func (sv *Subvolume) ReleaseDirHandle(_ context.Context, op *fuseops.ReleaseDirHandleOp) error {
+	_, ok := sv.dirHandles.LoadAndDelete(uint64(op.Handle))
+	if !ok {
+		return syscall.EBADF
+	}
+	return nil
+}
+
+func (sv *Subvolume) OpenFile(_ context.Context, op *fuseops.OpenFileOp) error { return syscall.ENOSYS }
+func (sv *Subvolume) ReadFile(_ context.Context, op *fuseops.ReadFileOp) error { return syscall.ENOSYS }
+func (sv *Subvolume) ReleaseFileHandle(_ context.Context, op *fuseops.ReleaseFileHandleOp) error {
+	return syscall.ENOSYS
+}
+
+func (sv *Subvolume) ReadSymlink(_ context.Context, op *fuseops.ReadSymlinkOp) error {
+	return syscall.ENOSYS
+}
+
+func (sv *Subvolume) GetXattr(_ context.Context, op *fuseops.GetXattrOp) error { return syscall.ENOSYS }
+func (sv *Subvolume) ListXattr(_ context.Context, op *fuseops.ListXattrOp) error {
+	return syscall.ENOSYS
+}
+
+func (sv *Subvolume) Destroy() {}
diff --git a/go.mod b/go.mod
index a5d3e22..562d87b 100644
--- a/go.mod
+++ b/go.mod
@@ -5,6 +5,7 @@ go 1.18
 require (
 	github.com/datawire/dlib v1.3.0
 	github.com/davecgh/go-spew v1.1.1
+	github.com/hashicorp/golang-lru v0.5.4
 	github.com/jacobsa/fuse v0.0.0-20220702091825-13117049f383
 	github.com/sirupsen/logrus v1.6.0
 	github.com/stretchr/testify v1.7.1
diff --git a/go.sum b/go.sum
index 06b22dd..2737b1b 100644
--- a/go.sum
+++ b/go.sum
@@ -3,8 +3,8 @@ github.com/datawire/dlib v1.3.0/go.mod h1:NiGDmetmbkBvtznpWSx6C0vA0s0LK9aHna3LJD
 github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
 github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
-github.com/jacobsa/fuse v0.0.0-20220702091825-13117049f383 h1:LmgK5WyqEu12BdEFkD5XxNxyK1SFk5Iz4TQsq96NxQM=
-github.com/jacobsa/fuse v0.0.0-20220702091825-13117049f383/go.mod h1:liOmRdJd8oTwHCQ5M9JemRE3CebdlYcZWLk+ZjQeuq0=
+github.com/hashicorp/golang-lru v0.5.4 h1:YDjusn29QI/Das2iO9M0BHnIbxPeyuCHsjMW+lJfyTc=
+github.com/hashicorp/golang-lru v0.5.4/go.mod h1:iADmTwqILo4mZ8BN3D2Q6+9jd8WM5uGBxy+E8yxSoD4=
 github.com/konsorten/go-windows-terminal-sequences v1.0.3 h1:CE8S1cTafDpPvMhIxNJKvHsGVBgn1xWYf1NbHQhywc8=
 github.com/konsorten/go-windows-terminal-sequences v1.0.3/go.mod h1:T0+1ngSBFLxvqU3pZ+m/2kptfBszLMUkC4ZK/EgS/cQ=
 github.com/kr/pretty v0.1.0 h1:L/CwN0zerZDmRFUapSPitk6f+Q3+0za1rQkzVuMiMFI=
diff --git a/pkg/btrfs/btrfsitem/item_dir.go b/pkg/btrfs/btrfsitem/item_dir.go
index 14541bd..4467d83 100644
--- a/pkg/btrfs/btrfsitem/item_dir.go
+++ b/pkg/btrfs/btrfsitem/item_dir.go
@@ -92,6 +92,7 @@ const (
 	FT_SOCK     = FileType(6)
 	FT_SYMLINK  = FileType(7)
 	FT_XATTR    = FileType(8)
+
 	FT_MAX      = FileType(9)
 )
 
diff --git a/pkg/util/generic.go b/pkg/util/generic.go
index dbe077f..6882724 100644
--- a/pkg/util/generic.go
+++ b/pkg/util/generic.go
@@ -2,6 +2,7 @@ package util
 
 import (
 	"sort"
+	"sync"
 
 	"golang.org/x/exp/constraints"
 )
@@ -88,3 +89,34 @@ func CmpUint[T constraints.Unsigned](a, b T) int {
 		return 1
 	}
 }
+
+type SyncMap[K comparable, V any] struct {
+	inner sync.Map
+}
+
+func (m *SyncMap[K, V]) Delete(key K) { m.inner.Delete(key) }
+func (m *SyncMap[K, V]) Load(key K) (value V, ok bool) {
+	_value, ok := m.inner.Load(key)
+	if ok {
+		value = _value.(V)
+	}
+	return value, ok
+}
+func (m *SyncMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) {
+	_value, ok := m.inner.LoadAndDelete(key)
+	if ok {
+		value = _value.(V)
+	}
+	return value, ok
+}
+func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) {
+	_actual, loaded := m.inner.LoadOrStore(key, value)
+	actual = _actual.(V)
+	return actual, loaded
+}
+func (m *SyncMap[K, V]) Range(f func(key K, value V) bool) {
+	m.inner.Range(func(key, value any) bool {
+		return f(key.(K), value.(V))
+	})
+}
+func (m *SyncMap[K, V]) Store(key K, value V) { m.inner.Store(key, value) }