btrfstree: Rethink 'Path' yet again

10 files changed, 303 insertions, 263 deletions

diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
index 7703078..75797a8 100644
--- a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
+++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
@@ -102,8 +102,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri
 			printHeaderInfo(out, node)
 			itemOffset = node.Size - uint32(nodeHeaderSize)
 		},
-		KeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) bool {
-			treeID := path[0].FromTree
+		KeyPointer: func(_ btrfstree.Path, item btrfstree.KeyPointer) bool {
 			textui.Fprintf(out, "\tkey %v block %v gen %v\n",
 				item.Key.Format(treeID),
 				item.BlockPtr,
@@ -111,13 +110,11 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri
 			return true
 		},
 		Item: func(path btrfstree.Path, item btrfstree.Item) {
-			treeID := path[0].FromTree
-			i := path.Node(-1).FromItemSlot
 			bs, _ := binstruct.Marshal(item.Body)
 			itemSize := uint32(len(bs))
 			itemOffset -= itemSize
 			textui.Fprintf(out, "\titem %v key %v itemoff %v itemsize %v\n",
-				i,
+				path[len(path)-1].(btrfstree.PathItem).FromSlot, //nolint:forcetypeassert // has to be
 				item.Key.Format(treeID),
 				itemOffset,
 				itemSize)
diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go
index bdbdca2..5887983 100644
--- a/cmd/btrfs-rec/inspect_lstrees.go
+++ b/cmd/btrfs-rec/inspect_lstrees.go
@@ -76,10 +76,11 @@ func init() {
 				},
 				TreeWalkHandler: btrfstree.TreeWalkHandler{
 					Node: func(path btrfstree.Path, node *btrfstree.Node) {
-						visitedNodes.Insert(path.Node(-1).ToNodeAddr)
+						visitedNodes.Insert(node.Head.Addr)
 					},
 					BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
-						visitedNodes.Insert(path.Node(-1).ToNodeAddr)
+						nodeAddr, _, _ := path.NodeExpectations(ctx, false)
+						visitedNodes.Insert(nodeAddr)
 						treeErrCnt++
 						return false
 					},
diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go
index 4f5d21b..19c7c68 100644
--- a/lib/btrfs/btrfstree/btree.go
+++ b/lib/btrfs/btrfstree/btree.go
@@ -14,6 +14,17 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 )
 
+type Tree interface {
+	// CheckOwner returns whether it is permissible for a node
+	// with .Head.Owner=owner and .Head.Generation=gen to be in
+	// this tree.
+	//
+	// If there is an error determining this, then `failOpen`
+	// specifies whether it should return an error (false) or nil
+	// (true).
+	TreeCheckOwner(ctx context.Context, failOpen bool, owner btrfsprim.ObjID, gen btrfsprim.Generation) error
+}
+
 type TreeSearcher interface {
 	// How the search should be described in the event of an
 	// error.
diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go
index b04bfc0..1875c2f 100644
--- a/lib/btrfs/btrfstree/btree_forrest.go
+++ b/lib/btrfs/btrfstree/btree_forrest.go
@@ -22,7 +22,9 @@ type TreeRoot struct {
 	Level      uint8
 	Generation btrfsprim.Generation
 
-	RootInode btrfsprim.ObjID // only for subvolume trees
+	RootInode  btrfsprim.ObjID // only for subvolume trees
+	ParentUUID btrfsprim.UUID
+	ParentGen  btrfsprim.Generation // offset of this tree's root item
 }
 
 // LookupTreeRoot is a utility function to help with implementing the
@@ -72,7 +74,10 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt
 				RootNode:   rootItemBody.ByteNr,
 				Level:      rootItemBody.Level,
 				Generation: rootItemBody.Generation,
+
 				RootInode:  rootItemBody.RootDirID,
+				ParentUUID: rootItemBody.ParentUUID,
+				ParentGen:  btrfsprim.Generation(rootItem.Key.Offset),
 			}, nil
 		case *btrfsitem.Error:
 			return nil, fmt.Errorf("malformed ROOT_ITEM for tree %v: %w", treeID, rootItemBody.Err)
@@ -83,10 +88,7 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt
 }
 
 type TreeOperatorImpl struct {
-	NodeSource interface {
-		NodeSource
-		NodeFile
-	}
+	NodeSource NodeSource
 }
 
 func (fs TreeOperatorImpl) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*RawTree, error) {
@@ -108,7 +110,7 @@ func (fs TreeOperatorImpl) RawTree(ctx context.Context, treeID btrfsprim.ObjID)
 func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	tree, err := fs.RawTree(ctx, treeID)
 	if err != nil {
-		errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
+		errHandle(&TreeError{Path: Path{PathRoot{TreeID: treeID}}, Err: err})
 		return
 	}
 	tree.TreeWalk(ctx, cbs)
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index 86eab11..27d6548 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -22,27 +22,35 @@ type RawTree struct {
 }
 
 func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler) {
+	sb, err := tree.Forrest.NodeSource.Superblock()
+	if err != nil {
+		if cbs.BadSuperblock != nil {
+			cbs.BadSuperblock(err)
+		}
+		return
+	}
 	if tree.RootNode == 0 {
 		return
 	}
-	path := Path{{
-		FromTree:         tree.ID,
-		FromItemSlot:     -1,
-		ToNodeAddr:       tree.RootNode,
-		ToNodeGeneration: tree.Generation,
-		ToNodeLevel:      tree.Level,
-		ToMaxKey:         btrfsprim.MaxKey,
-	}}
-	tree.walk(ctx, path, cbs)
+	path := Path{
+		PathRoot{
+			Tree:         tree,
+			TreeID:       tree.ID,
+			ToAddr:       tree.RootNode,
+			ToGeneration: tree.Generation,
+			ToLevel:      tree.Level,
+		},
+	}
+	tree.walk(ctx, *sb, path, cbs)
 }
 
-func (tree *RawTree) walk(ctx context.Context, path Path, cbs TreeWalkHandler) {
+func (tree *RawTree) walk(ctx context.Context, sb Superblock, path Path, cbs TreeWalkHandler) {
 	if ctx.Err() != nil {
 		return
 	}
 
 	// 001
-	nodeAddr, nodeExp, ok := path.NodeExpectations(tree.Forrest.NodeSource)
+	nodeAddr, nodeExp, ok := path.NodeExpectations(ctx, true) // TODO(lukeshu): Consider whether failing open is the right thing here
 	if !ok {
 		return
 	}
@@ -74,18 +82,20 @@ func (tree *RawTree) walk(ctx context.Context, path Path, cbs TreeWalkHandler) {
 	}
 	// branch a (interior)
 	for i, item := range node.BodyInterior {
-		toMaxKey := path.Node(-1).ToMaxKey
+		toMaxKey := nodeExp.MaxItem.Val
 		if i+1 < len(node.BodyInterior) {
 			toMaxKey = node.BodyInterior[i+1].Key.Mm()
 		}
-		itemPath := append(path, PathElem{
-			FromTree:         node.Head.Owner,
-			FromItemSlot:     i,
-			ToNodeAddr:       item.BlockPtr,
-			ToNodeGeneration: item.Generation,
-			ToNodeLevel:      node.Head.Level - 1,
-			ToKey:            item.Key,
-			ToMaxKey:         toMaxKey,
+		itemPath := append(path, PathKP{
+			FromTree: node.Head.Owner,
+			FromSlot: i,
+
+			ToAddr:       item.BlockPtr,
+			ToGeneration: item.Generation,
+			ToMinKey:     item.Key,
+
+			ToMaxKey: toMaxKey,
+			ToLevel:  node.Head.Level - 1,
 		})
 		// 003a
 		recurse := cbs.KeyPointer == nil || cbs.KeyPointer(itemPath, item)
@@ -94,7 +104,7 @@ func (tree *RawTree) walk(ctx context.Context, path Path, cbs TreeWalkHandler) {
 		}
 		// 004a
 		if recurse {
-			tree.walk(ctx, itemPath, cbs)
+			tree.walk(ctx, sb, itemPath, cbs)
 			if ctx.Err() != nil {
 				return
 			}
@@ -105,11 +115,11 @@ func (tree *RawTree) walk(ctx context.Context, path Path, cbs TreeWalkHandler) {
 		return
 	}
 	for i, item := range node.BodyLeaf {
-		itemPath := append(path, PathElem{
-			FromTree:     node.Head.Owner,
-			FromItemSlot: i,
-			ToKey:        item.Key,
-			ToMaxKey:     item.Key,
+		itemPath := append(path, PathItem{
+			FromTree: node.Head.Owner,
+			FromSlot: i,
+
+			ToKey: item.Key,
 		})
 		// 003b
 		switch item.Body.(type) {
@@ -271,3 +281,64 @@ func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSea
 	}
 	return nil
 }
+
+// TreeCheckOwner implements the 'Tree' interface.
+func (tree *RawTree) TreeCheckOwner(ctx context.Context, failOpen bool, owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
+	var uuidTree *RawTree
+	for {
+		// Main.
+		if owner == tree.ID {
+			return nil
+		}
+		if tree.ParentUUID == (btrfsprim.UUID{}) {
+			return fmt.Errorf("owner=%v is not acceptable in this tree",
+				owner)
+		}
+		if gen > tree.ParentGen {
+			return fmt.Errorf("claimed owner=%v might be acceptable in this tree (if generation<=%v) but not with claimed generation=%v",
+				owner, tree.ParentGen, gen)
+		}
+
+		// Loop update.
+		if uuidTree == nil {
+			var err error
+			uuidTree, err = tree.Forrest.RawTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+			if err != nil {
+				if failOpen {
+					return nil
+				}
+				return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+					owner, gen, err)
+			}
+		}
+		parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID))
+		if err != nil {
+			if failOpen {
+				return nil
+			}
+			return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+				owner, gen, err)
+		}
+		switch parentIDBody := parentIDItem.Body.(type) {
+		case *btrfsitem.UUIDMap:
+			tree, err = tree.Forrest.RawTree(ctx, parentIDBody.ObjID)
+			if err != nil {
+				if failOpen {
+					return nil
+				}
+				return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+					owner, gen, err)
+			}
+		case *btrfsitem.Error:
+			if failOpen {
+				return nil
+			}
+			return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+				owner, gen, parentIDBody.Err)
+		default:
+			// This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
+			// btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated.
+			panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", parentIDBody))
+		}
+	}
+}
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 1335b76..537df9a 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -5,8 +5,8 @@
 package btrfstree
 
 import (
+	"context"
 	"fmt"
-	"io"
 	"strings"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
@@ -14,11 +14,10 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 )
 
-// Path 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.
+// Path is a path from the superblock or a ROOT_ITEM to a node or
+// item within one of the btrees in the system.
 //
-//   - The first element will always have an ItemSlot of -1.
+//   - The first element will always have a FromSlot of -1.
 //
 //   - For .Item() callbacks, the last element will always have a
 //     NodeAddr of 0.
@@ -27,164 +26,156 @@ import (
 //
 //	[superblock: tree=B, lvl=3, gen=6]
 //	     |
-//	     | <------------------------------------------ pathElem={from_tree:B, from_slot=-1,
-//	     |                                                       to_addr:0x01, to_gen=6, to_lvl=3}
+//	     | <------------------------------------------ PathRoot={Tree:B,
+//	     |                                                       ToAddr:0x01, ToGen=6, ToLvl=3}
 //	  +[0x01]-------------+
 //	  | lvl=3 gen=6 own=B |
 //	  +-+-+-+-+-+-+-+-+-+-+
 //	  |0|1|2|3|4|5|6|7|8|9|
 //	  +-+-+-+-+-+-+-+-+-+-+
 //	                 |
-//	                 | <------------------------------ pathElem:{from_tree:B, from_slot:7,
-//	                 |                                           to_addr:0x02, to_gen:5, to_lvl:2}
+//	                 | <------------------------------ PathKP={FromTree:B, FromSlot:7,
+//	                 |                                         ToAddr:0x02, ToGen:5, ToLvl:2}
 //	              +[0x02]--------------+
 //	              | lvl=2 gen=5 own=B  |
 //	              +-+-+-+-+-+-+-+-+-+-+
 //	              |0|1|2|3|4|5|6|7|8|9|
 //	              +-+-+-+-+-+-+-+-+-+-+
 //	                           |
-//	                           | <-------------------- pathElem={from_tree:B, from_slot:6,
-//	                           |                                 to_addr:0x03, to_gen:5, to_lvl:1}
+//	                           | <-------------------- PathKP={FromTree:B, FromSlot:6,
+//	                           |                               ToAddr:0x03, ToGen:5, ToLvl:1}
 //	                        +[0x03]-------------+
 //	                        | lvl=1 gen=5 own=A |
 //	                        +-+-+-+-+-+-+-+-+-+-+
 //	                        |0|1|2|3|4|5|6|7|8|9|
 //	                        +-+-+-+-+-+-+-+-+-+-+
 //	                               |
-//	                               | <---------------- pathElem={from_tree:A, from_slot:3,
-//	                               |                             to_addr:0x04, to_gen:2, lvl:0}
+//	                               | <---------------- PathKP={FromTree:A, FromSlot:3,
+//	                               |                           ToAddr:0x04, ToGen:2, ToLvl:0}
 //	                             +[0x04]-------------+
 //	                             | lvl=0 gen=2 own=A |
 //	                             +-+-+-+-+-+-+-+-+-+-+
 //	                             |0|1|2|3|4|5|6|7|8|9|
 //	                             +-+-+-+-+-+-+-+-+-+-+
 //	                                |
-//	                                | <--------------- pathElem={from_tree:A, from_slot:1,
-//	                                |                            to_addr:0, to_gen: 0, to_lvl:0}
+//	                                | <--------------- PathItem={FromTree:A, FromSlot:1}
+//	                                |
 //	                              [item]
 type Path []PathElem
 
-// A PathElem essentially represents a KeyPointer.
-type PathElem struct {
-	// FromTree is the owning tree ID of the parent node; or the
-	// well-known tree ID if this is the root.
-	FromTree btrfsprim.ObjID
-	// FromItemSlot is the index of this KeyPointer in the parent
-	// Node; or -1 if this is the root and there is no KeyPointer.
-	FromItemSlot int
+// A PathElem is either a PathRoot, a PathKP, or a PathItem.
+type PathElem interface {
+	isPathElem()
+}
 
-	// ToNodeAddr is the address of the node that the KeyPointer
-	// points at, or 0 if this is a leaf item and nothing is being
-	// pointed at.
-	ToNodeAddr btrfsvol.LogicalAddr
-	// ToNodeGeneration is the expected generation of the node at
-	// ToNodeAddr, or 0 if this is a leaf item and nothing is
-	// being pointed at.
-	ToNodeGeneration btrfsprim.Generation
-	// ToNodeLevel is the expected level of the node at
-	// ToNodeAddr, or 0 if this is a leaf item and nothing is
-	// being pointed at.
-	ToNodeLevel uint8
-	// ToKey is either
-	//  - btrfprim.Key{} if this is the root node being pointed
-	//    to,
-	//  - the KeyPointer.Key if this is a non-root node being
-	//    pointed to, or
-	//  - the key of the leaf item being pointed to.
-	ToKey    btrfsprim.Key
+type PathRoot struct {
+	Tree Tree
+	// It should be no surprise that these 4 members mimic the 4
+	// members of a 'RawTree'.
+	TreeID       btrfsprim.ObjID
+	ToAddr       btrfsvol.LogicalAddr
+	ToGeneration btrfsprim.Generation
+	ToLevel      uint8
+}
+
+func (PathRoot) isPathElem() {}
+
+type PathKP struct {
+	// From the containing Node.
+	FromTree btrfsprim.ObjID
+	FromSlot int
+	// From the KP itself.
+	ToAddr       btrfsvol.LogicalAddr
+	ToGeneration btrfsprim.Generation
+	ToMinKey     btrfsprim.Key
+	// From the structure of the tree.
 	ToMaxKey btrfsprim.Key
+	ToLevel  uint8
 }
 
-func (elem PathElem) writeNodeTo(w io.Writer) {
-	fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr)
+func (PathKP) isPathElem() {}
+
+type PathItem struct {
+	// From the containing Node.
+	FromTree btrfsprim.ObjID
+	FromSlot int
+	// From the Item itself.
+	ToKey btrfsprim.Key
 }
 
+func (PathItem) isPathElem() {}
+
 func (path Path) String() string {
 	if len(path) == 0 {
 		return "(empty-path)"
 	}
 	var ret strings.Builder
-	fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsprim.ROOT_TREE_OBJECTID))
-	if len(path) == 1 && path[0] == (PathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) {
-		ret.WriteString("(empty-path)")
-	} else {
-		path[0].writeNodeTo(&ret)
-	}
-	for _, elem := range path[1:] {
-		fmt.Fprintf(&ret, "[%v]", elem.FromItemSlot)
-		if elem.ToNodeAddr != 0 {
-			ret.WriteString("->")
-			elem.writeNodeTo(&ret)
+	for _, elem := range path {
+		switch elem := elem.(type) {
+		case PathRoot:
+			fmt.Fprintf(&ret, "%s->node:%d@%v",
+				elem.TreeID.Format(btrfsprim.ROOT_TREE_OBJECTID),
+				elem.ToLevel, elem.ToAddr)
+		case PathKP:
+			fmt.Fprintf(&ret, "[%d]->node:%d@%v",
+				elem.FromSlot,
+				elem.ToLevel, elem.ToAddr)
+		case PathItem:
+			// fmt.Fprintf(&ret, "[%d]->item:%v",
+			// 	elem.FromSlot,
+			// 	elem.ToKey)
+			fmt.Fprintf(&ret, "[%d]",
+				elem.FromSlot)
+		default:
+			panic(fmt.Errorf("should not happen: unexpected PathElem type: %T", elem))
 		}
 	}
 	return ret.String()
 }
 
-func (path Path) DeepCopy() Path {
-	return append(Path(nil), path...)
-}
-
 // NodeExpectations returns the address to read and the expectations
 // to have when reading the node pointed to by this Path.
 //
 // `ok` is false if the path is empty or if this Path points to an
 // item rather than a node.
-func (path Path) NodeExpectations(fs NodeFile) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) {
-	if path.Node(-1).ToNodeAddr == 0 && path.Node(-1).ToNodeGeneration == 0 && path.Node(-1).ToNodeLevel == 0 {
+func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) {
+	if len(path) == 0 {
 		return 0, NodeExpectations{}, false
 	}
-
-	checkOwner := func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
-		var treeParents []btrfsprim.ObjID
-
-		tree := path.Node(-1).FromTree
-		for {
-			if owner == tree {
-				// OK!
-				return nil
-			}
-
-			treeParents = append(treeParents, tree)
-			parent, parentGen, parentOK := fs.ParentTree(tree)
-			if !parentOK {
-				// Failed look up parent info; fail open.
-				return nil
-			}
-
-			if parent == 0 {
-				// End of the line.
-				return fmt.Errorf("expected owner in %v but claims to have owner=%v",
-					treeParents, owner)
-			}
-			if gen > parentGen {
-				return fmt.Errorf("claimed owner=%v might be acceptable in this tree (if generation<=%v) but not with claimed generation=%v",
-					owner, parentGen, gen)
-			}
-			tree = parent
-		}
+	firstElem, ok := path[0].(PathRoot)
+	if !ok {
+		panic(fmt.Errorf("should not happen: first PathElem is not PathRoot: %T", path[0]))
+	}
+	switch lastElem := path[len(path)-1].(type) {
+	case PathRoot:
+		return lastElem.ToAddr, NodeExpectations{
+			LAddr:      containers.OptionalValue(lastElem.ToAddr),
+			Level:      containers.OptionalValue(lastElem.ToLevel),
+			Generation: containers.OptionalValue(lastElem.ToGeneration),
+			Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
+				return firstElem.Tree.TreeCheckOwner(ctx, failOpen, owner, gen)
+			},
+			MinItem: containers.OptionalValue(btrfsprim.Key{}),
+			MaxItem: containers.OptionalValue(btrfsprim.MaxKey),
+		}, true
+	case PathKP:
+		return lastElem.ToAddr, NodeExpectations{
+			LAddr:      containers.OptionalValue(lastElem.ToAddr),
+			Level:      containers.OptionalValue(lastElem.ToLevel),
+			Generation: containers.OptionalValue(lastElem.ToGeneration),
+			Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
+				return firstElem.Tree.TreeCheckOwner(ctx, failOpen, owner, gen)
+			},
+			MinItem: containers.OptionalValue(lastElem.ToMinKey),
+			MaxItem: containers.OptionalValue(lastElem.ToMaxKey),
+		}, true
+	case PathItem:
+		return 0, NodeExpectations{}, false
+	default:
+		panic(fmt.Errorf("should not happen: unexpected PathElem type: %T", lastElem))
 	}
-
-	return path.Node(-1).ToNodeAddr, NodeExpectations{
-		LAddr:      containers.OptionalValue(path.Node(-1).ToNodeAddr),
-		Level:      containers.OptionalValue(path.Node(-1).ToNodeLevel),
-		Generation: containers.OptionalValue(path.Node(-1).ToNodeGeneration),
-		Owner:      checkOwner,
-		MinItem:    containers.OptionalValue(path.Node(-1).ToKey),
-		MaxItem:    containers.OptionalValue(path.Node(-1).ToMaxKey),
-	}, true
 }
 
 func (path Path) Parent() Path {
 	return path[:len(path)-1]
 }
-
-// Node is returns an element from the path; `path.Node(x)` is like
-// `&path[x]`, but negative values of x move down from the end of path
-// (similar to how lists work in many other languages, such as
-// Python).
-func (path Path) Node(x int) *PathElem {
-	if x < 0 {
-		x += len(path)
-	}
-	return &path[x]
-}
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
deleted file mode 100644
index c9642da..0000000
--- a/lib/btrfs/btrfstree/readnode.go
+++ /dev/null
@@ -1,26 +0,0 @@
-// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfstree
-
-import (
-	"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/diskio"
-)
-
-type NodeFile interface {
-	diskio.ReaderAt[btrfsvol.LogicalAddr]
-
-	// ParentTree, given a tree ID, returns that tree's parent
-	// tree, if it has one.
-	//
-	//  - non-zero, ?, true : the parent tree ID
-	//
-	//  - 0, 0, true : the tree does not have a parent
-	//
-	//  - ?, ?, false : the tree's parent information could not be
-	//    looked up
-	ParentTree(btrfsprim.ObjID) (btrfsprim.ObjID, btrfsprim.Generation, bool)
-}
diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go
index 72e97f3..44378a0 100644
--- a/lib/btrfs/io2_lv.go
+++ b/lib/btrfs/io2_lv.go
@@ -29,9 +29,6 @@ type FS struct {
 	cacheSuperblock  *btrfstree.Superblock
 
 	cacheNodes containers.Cache[btrfsvol.LogicalAddr, nodeCacheEntry]
-
-	cacheObjID2All  map[btrfsprim.ObjID]treeInfo
-	cacheUUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID
 }
 
 var _ diskio.File[btrfsvol.LogicalAddr] = (*FS)(nil)
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 8aa485f..030ea41 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -8,7 +8,6 @@ import (
 	"context"
 	"fmt"
 
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
 	"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"
@@ -18,68 +17,6 @@ import (
 
 // This file is ordered from low-level to high-level.
 
-// btrfstree.NodeFile //////////////////////////////////////////////////////////
-
-type treeInfo struct {
-	UUID       btrfsprim.UUID
-	ParentUUID btrfsprim.UUID
-	ParentGen  btrfsprim.Generation
-}
-
-func (fs *FS) populateTreeUUIDs(ctx context.Context) {
-	if fs.cacheObjID2All != nil && fs.cacheUUID2ObjID != nil {
-		return
-	}
-	fs.cacheObjID2All = make(map[btrfsprim.ObjID]treeInfo)
-	fs.cacheUUID2ObjID = make(map[btrfsprim.UUID]btrfsprim.ObjID)
-	fs.TreeWalk(ctx, btrfsprim.ROOT_TREE_OBJECTID,
-		func(err *btrfstree.TreeError) {
-			// do nothing
-		},
-		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.Path, item btrfstree.Item) {
-				itemBody, ok := item.Body.(*btrfsitem.Root)
-				if !ok {
-					return
-				}
-				fs.cacheObjID2All[item.Key.ObjectID] = treeInfo{
-					UUID:       itemBody.UUID,
-					ParentUUID: itemBody.ParentUUID,
-					ParentGen:  btrfsprim.Generation(item.Key.Offset),
-				}
-				fs.cacheUUID2ObjID[itemBody.UUID] = item.Key.ObjectID
-			},
-		},
-	)
-}
-
-// ParentTree implements btrfstree.NodeFile.
-func (fs *FS) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, btrfsprim.Generation, bool) {
-	if tree < btrfsprim.FIRST_FREE_OBJECTID || tree > btrfsprim.LAST_FREE_OBJECTID {
-		// no parent
-		return 0, 0, true
-	}
-	fs.populateTreeUUIDs(context.TODO())
-
-	all, ok := fs.cacheObjID2All[tree]
-	if !ok {
-		// could not look up parent info
-		return 0, 0, false
-	}
-	if all.ParentUUID == (btrfsprim.UUID{}) {
-		// no parent
-		return 0, 0, true
-	}
-	parentObjID, ok := fs.cacheUUID2ObjID[all.ParentUUID]
-	if !ok {
-		// could not look up parent info
-		return 0, 0, false
-	}
-	return parentObjID, all.ParentGen, true
-}
-
-var _ btrfstree.NodeFile = (*FS)(nil)
-
 // btrfstree.NodeSource ////////////////////////////////////////////////////////
 
 type nodeCacheEntry struct {
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index 36abe6f..d17aa4a 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -23,13 +23,17 @@ import (
 type oldRebuiltTree struct {
 	forrest *OldRebuiltForrest
 
-	ID btrfsprim.ObjID
+	ID         btrfsprim.ObjID
+	ParentUUID btrfsprim.UUID
+	ParentGen  btrfsprim.Generation // offset of this tree's root item
 
 	RootErr error
 	Items   *containers.RBTree[oldRebuiltTreeValue]
 	Errors  *containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]
 }
 
+var _ btrfstree.Tree = oldRebuiltTree{}
+
 type oldRebuiltTreeError struct {
 	Min btrfsprim.Key
 	Max btrfsprim.Key
@@ -172,19 +176,23 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O
 		TreeRoot: *root,
 	}
 
+	cacheEntry.ParentUUID = root.ParentUUID
+	cacheEntry.ParentGen = root.ParentGen
+
 	var curNode nodeInfo
 	cbs := btrfstree.TreeWalkHandler{
 		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
+			_, nodeExp, _ := path.NodeExpectations(ctx, false)
 			cacheEntry.Errors.Insert(oldRebuiltTreeError{
-				Min: path.Node(-1).ToKey,
-				Max: path.Node(-1).ToMaxKey,
+				Min: nodeExp.MinItem.Val,
+				Max: nodeExp.MaxItem.Val,
 				Err: err,
 			})
 			return false
 		},
 		Node: func(path btrfstree.Path, node *btrfstree.Node) {
 			curNode = nodeInfo{
-				LAddr:      path.Node(-1).ToNodeAddr,
+				LAddr:      node.Head.Addr,
 				Level:      node.Head.Level,
 				Generation: node.Head.Generation,
 				Owner:      node.Head.Owner,
@@ -204,7 +212,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O
 				ItemSize: item.BodySize,
 
 				Node: curNode,
-				Slot: path.Node(-1).FromItemSlot,
+				Slot: path[len(path)-1].(btrfstree.PathItem).FromSlot, //nolint:forcetypeassert // has to be
 			})
 		},
 	}
@@ -342,11 +350,8 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 	tree := bt.RebuiltTree(ctx, treeID)
 	if tree.RootErr != nil {
 		errHandle(&btrfstree.TreeError{
-			Path: btrfstree.Path{{
-				FromTree: treeID,
-				ToMaxKey: btrfsprim.MaxKey,
-			}},
-			Err: tree.RootErr,
+			Path: btrfstree.Path{btrfstree.PathRoot{TreeID: treeID}},
+			Err:  tree.RootErr,
 		})
 		return
 	}
@@ -372,19 +377,17 @@ func (tree oldRebuiltTree) treeWalk(ctx context.Context, cbs btrfstree.TreeWalkH
 		item := node.BodyLeaf[indexItem.Value.Slot]
 
 		itemPath := btrfstree.Path{
-			{
-				FromTree:         tree.ID,
-				ToNodeAddr:       indexItem.Value.Node.LAddr,
-				ToNodeGeneration: indexItem.Value.Node.Generation,
-				ToNodeLevel:      indexItem.Value.Node.Level,
-				ToKey:            indexItem.Value.Node.MinItem,
-				ToMaxKey:         indexItem.Value.Node.MaxItem,
+			btrfstree.PathRoot{
+				Tree:         tree,
+				TreeID:       tree.ID,
+				ToAddr:       indexItem.Value.Node.LAddr,
+				ToGeneration: indexItem.Value.Node.Generation,
+				ToLevel:      indexItem.Value.Node.Level,
 			},
-			{
-				FromTree:     indexItem.Value.Node.Owner,
-				FromItemSlot: indexItem.Value.Slot,
-				ToKey:        indexItem.Value.Key,
-				ToMaxKey:     indexItem.Value.Key,
+			btrfstree.PathItem{
+				FromTree: indexItem.Value.Node.Owner,
+				FromSlot: indexItem.Value.Slot,
+				ToKey:    indexItem.Value.Key,
 			},
 		}
 		switch item.Body.(type) {
@@ -411,3 +414,59 @@ func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
 func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
 	return bt.inner.ReadAt(p, off)
 }
+
+// TreeCheckOwner implements btrfstree.Tree.
+func (tree oldRebuiltTree) TreeCheckOwner(ctx context.Context, failOpen bool, owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
+	var uuidTree oldRebuiltTree
+	for {
+		// Main.
+		if owner == tree.ID {
+			return nil
+		}
+		if tree.ParentUUID == (btrfsprim.UUID{}) {
+			return fmt.Errorf("owner=%v is not acceptable in this tree",
+				owner)
+		}
+		if gen > tree.ParentGen {
+			return fmt.Errorf("claimed owner=%v might be acceptable in this tree (if generation<=%v) but not with claimed generation=%v",
+				owner, tree.ParentGen, gen)
+		}
+
+		// Loop update.
+		if uuidTree.forrest == nil {
+			uuidTree = tree.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+			if uuidTree.RootErr != nil {
+				return nil //nolint:nilerr // fail open
+			}
+		}
+		parentIDItem, err := uuidTree.treeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID))
+		if err != nil {
+			if failOpen {
+				return nil
+			}
+			return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+				owner, gen, err)
+		}
+		switch parentIDBody := parentIDItem.Body.(type) {
+		case *btrfsitem.UUIDMap:
+			tree = tree.forrest.RebuiltTree(ctx, parentIDBody.ObjID)
+			if tree.RootErr != nil {
+				if failOpen {
+					return nil
+				}
+				return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+					owner, gen, tree.RootErr)
+			}
+		case *btrfsitem.Error:
+			if failOpen {
+				return nil
+			}
+			return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
+				owner, gen, parentIDBody.Err)
+		default:
+			// This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
+			// btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated.
+			panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", parentIDBody))
+		}
+	}
+}