wip

7 files changed, 100 insertions, 63 deletions

diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go
index 83c08c4..02511f5 100644
--- a/lib/btrfs/btrfstree/ops.go
+++ b/lib/btrfs/btrfstree/ops.go
@@ -20,7 +20,8 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
-type Trees interface {
+// TreeOperator is an interface for performing basic btree operations.
+type TreeOperator interface {
 	// TreeWalk walks a tree, triggering callbacks for every node,
 	// key-pointer, and item; as well as for any errors encountered.
 	//
@@ -91,12 +92,12 @@ type NodeSource interface {
 	ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error)
 }
 
-type TreesImpl struct {
+type TreeOperatorImpl struct {
 	NodeSource
 }
 
 // TreeWalk implements the 'Trees' interface.
-func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	sb, err := fs.Superblock()
 	if err != nil {
 		errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err})
@@ -109,9 +110,9 @@ func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHan
 	fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs)
 }
 
-// TreeWalk is a utility function to help with implementing the 'Trees'
+// TreeWalk is a utility method to help with implementing the 'Trees'.
 // interface.
-func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	path := TreePath{{
 		FromTree:       rootInfo.TreeID,
 		FromGeneration: rootInfo.Generation,
@@ -122,7 +123,7 @@ func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandl
 	fs.treeWalk(ctx, path, errHandle, cbs)
 }
 
-func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	if ctx.Err() != nil {
 		return
 	}
@@ -233,7 +234,7 @@ func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(
 	}
 }
 
-func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
 	path := TreePath{{
 		FromTree:       treeRoot.TreeID,
 		FromGeneration: treeRoot.Generation,
@@ -303,7 +304,7 @@ func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32)
 	}
 }
 
-func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
 	var err error
 	path = path.DeepCopy()
 
@@ -359,7 +360,7 @@ func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, N
 	return path, node, nil
 }
 
-func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
 	var err error
 	path = path.DeepCopy()
 
@@ -431,7 +432,7 @@ func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, N
 }
 
 // TreeSearch implements the 'Trees' interface.
-func (fs TreesImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) {
+func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) {
 	sb, err := fs.Superblock()
 	if err != nil {
 		return Item{}, err
@@ -455,7 +456,7 @@ func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int {
 }
 
 // TreeLookup implements the 'Trees' interface.
-func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
+func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
 	item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp))
 	if err != nil {
 		err = fmt.Errorf("item with key=%v: %w", key, err)
@@ -464,7 +465,7 @@ func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item,
 }
 
 // TreeSearchAll implements the 'Trees' interface.
-func (fs TreesImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) {
+func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) {
 	sb, err := fs.Superblock()
 	if err != nil {
 		return nil, err
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 99461a4..4a4d66e 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -14,7 +14,11 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 )
 
-// - The first element will always have an ItemIdx of -1.
+// TreePath is a path from the superblock (i.e. the root of the btrfs
+// system) to the a node or item within one of the btrees in the
+// system.
+//
+//   - The first element will always have an ItemIdx of -1.
 //
 //   - For .Item() callbacks, the last element will always have a
 //     NodeAddr of 0.
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
new file mode 100644
index 0000000..bb80d20
--- /dev/null
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -0,0 +1,54 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+// FSReadNode is a utility function to help with implementing the
+// 'NodeSource' interface.
+func FSReadNode(
+	fs interface {
+		diskio.File[btrfsvol.LogicalAddr]
+		Superblock() (*Superblock, error)
+		ParentTree(btrfsprim.ObjID) (btrfsprim.ObjID, bool)
+	},
+	path TreePath,
+) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err)
+	}
+
+	var treeParents []btrfsprim.ObjID
+	checkOwner := func(owner btrfsprim.ObjID) error {
+		exp := path.Node(-1).FromTree
+		for {
+			if owner == exp {
+				return nil
+			}
+			treeParents = append(treeParents, exp)
+			var ok bool
+			exp, ok = fs.ParentTree(exp)
+			if !ok {
+				return fmt.Errorf("expected owner in %v but claims to have owner=%v",
+					treeParents, owner)
+			}
+		}
+	}
+
+	return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{
+		LAddr:         containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
+		Level:         containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
+		MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration},
+		Owner:         checkOwner,
+	})
+}
diff --git a/lib/btrfs/btrfstree/root.go b/lib/btrfs/btrfstree/root.go
index 41aac69..a233ef0 100644
--- a/lib/btrfs/btrfstree/root.go
+++ b/lib/btrfs/btrfstree/root.go
@@ -23,7 +23,7 @@ type TreeRoot struct {
 
 // LookupTreeRoot is a utility function to help with implementing the 'Trees'
 // interface.
-func LookupTreeRoot(fs Trees, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
+func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
 	switch treeID {
 	case btrfsprim.ROOT_TREE_OBJECTID:
 		return &TreeRoot{
diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
index aecdf9c..6718fbe 100644
--- a/lib/btrfs/btrfstree/types_node.go
+++ b/lib/btrfs/btrfstree/types_node.go
@@ -17,7 +17,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 	"git.lukeshu.com/btrfs-progs-ng/lib/fmtutil"
-	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
 type NodeFlags uint64
@@ -386,7 +385,7 @@ type NodeExpectations struct {
 	// Things knowable from the parent.
 	Level         containers.Optional[uint8]
 	MaxGeneration containers.Optional[btrfsprim.Generation]
-	Owner         []btrfsprim.ObjID
+	Owner         func(btrfsprim.ObjID) error
 }
 
 func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) {
@@ -437,9 +436,10 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
 		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected generation<=%v but claims to be generation=%v",
 			addr, exp.MaxGeneration.Val, nodeRef.Data.Head.Generation)
 	}
-	if len(exp.Owner) > 0 && !slices.Contains(nodeRef.Data.Head.Owner, exp.Owner) {
-		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected owner in %v but claims to have owner=%v",
-			addr, exp.Owner, nodeRef.Data.Head.Owner)
+	if exp.Owner != nil {
+		if err := exp.Owner(nodeRef.Data.Head.Owner); err != nil {
+			return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+		}
 	}
 
 	// parse (main)
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 31cf857..8455eee 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -6,7 +6,6 @@ package btrfs
 
 import (
 	"context"
-	"fmt"
 
 	"github.com/datawire/dlib/dlog"
 
@@ -14,24 +13,23 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 )
 
 func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
-	btrfstree.TreesImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs)
+	btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs)
 }
 func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
-	return btrfstree.TreesImpl{NodeSource: fs}.TreeLookup(treeID, key)
+	return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key)
 }
 func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) {
-	return btrfstree.TreesImpl{NodeSource: fs}.TreeSearch(treeID, fn)
+	return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn)
 }
 func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) {
-	return btrfstree.TreesImpl{NodeSource: fs}.TreeSearchAll(treeID, fn)
+	return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn)
 }
 
-var _ btrfstree.Trees = (*FS)(nil)
+var _ btrfstree.TreeOperator = (*FS)(nil)
 
 func (fs *FS) populateTreeUUIDs(ctx context.Context) {
 	if fs.cacheObjID2UUID == nil || fs.cacheUUID2ObjID == nil || fs.cacheTreeParent == nil {
@@ -59,44 +57,24 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) {
 	}
 }
 
-var noParents = make(map[btrfsprim.ObjID]struct{})
-
-func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) {
-	sb, err := fs.Superblock()
-	if err != nil {
-		return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err)
+func (fs *FS) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) {
+	ctx := context.TODO()
+	if tree < btrfsprim.FIRST_FREE_OBJECTID {
+		return 0, false
 	}
-
-	potentialOwners := []btrfsprim.ObjID{
-		path.Node(-1).FromTree,
+	fs.populateTreeUUIDs(ctx)
+	parentUUID := fs.cacheTreeParent[tree]
+	if parentUUID == (btrfsprim.UUID{}) {
+		return 0, false
 	}
-	if potentialOwners[0] >= btrfsprim.FIRST_FREE_OBJECTID {
-		ctx := context.TODO()
-		fs.populateTreeUUIDs(ctx)
-		for potentialOwners[len(potentialOwners)-1] >= btrfsprim.FIRST_FREE_OBJECTID {
-			objID := potentialOwners[len(potentialOwners)-1]
-			parentUUID := fs.cacheTreeParent[objID]
-			if parentUUID == (btrfsprim.UUID{}) {
-				if _, already := noParents[objID]; !already {
-					dlog.Infof(ctx, "dbg: objID=%v has no parent", objID)
-					noParents[objID] = struct{}{}
-				}
-				break
-			}
-			dlog.Infof(ctx, "dbg: parent of objID=%v is %v", objID, parentUUID)
-			parentObjID, ok := fs.cacheUUID2ObjID[parentUUID]
-			if !ok {
-				dlog.Errorf(ctx, "dbg: could not resolve parentUUID=%v to an ObjID", parentUUID)
-				break
-			}
-			potentialOwners = append(potentialOwners, parentObjID)
-		}
+	parentObjID, ok := fs.cacheUUID2ObjID[parentUUID]
+	if !ok {
+		dlog.Errorf(ctx, "dbg: could not resolve parentUUID=%v to an ObjID", parentUUID)
+		return 0, false
 	}
+	return parentObjID, true
+}
 
-	return btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{
-		LAddr:         containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
-		Level:         containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
-		MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration},
-		Owner:         potentialOwners,
-	})
+func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) {
+	return btrfstree.FSReadNode(fs, path)
 }
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
index 7bfcc00..8751078 100644
--- a/lib/btrfs/io4_fs.go
+++ b/lib/btrfs/io4_fs.go
@@ -61,7 +61,7 @@ type File struct {
 
 type Subvolume struct {
 	FS interface {
-		btrfstree.Trees
+		btrfstree.TreeOperator
 		Superblock() (*btrfstree.Superblock, error)
 		ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error)
 	}