Merge branch 'lukeshu/rebuilt-v2-pt1-naive'

12 files changed, 663 insertions, 113 deletions

diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
index d1ccfac..7e2e49f 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
@@ -159,7 +159,7 @@ func (o *rebuilder) processTreeQueue(ctx context.Context) error {
 		}
 		// This will call o.AddedItem as nescessary, which
 		// inserts to o.addedItemQueue.
-		_ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID)
+		_, _ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID)
 	}
 
 	return nil
@@ -197,7 +197,7 @@ func (o *rebuilder) processAddedItemQueue(ctx context.Context) error {
 
 	for _, key := range queue {
 		ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.settle.item", key)
-		tree := o.rebuilt.RebuiltTree(ctx, key.TreeID)
+		tree := discardErr(o.rebuilt.RebuiltTree(ctx, key.TreeID))
 		incPtr, ok := tree.RebuiltAcquireItems(ctx).Load(key.Key)
 		tree.RebuiltReleaseItems()
 		if !ok {
@@ -333,9 +333,8 @@ func (o *rebuilder) sortSettledItemQueue(ctx context.Context, unorderedQueue con
 	// EXTENT_TREE; if that fails, then there can't be any items
 	// in the EXTENT_TREE for us to have to handle special, and
 	// all of the following code will fall through common-path.
-	extentTree := o.rebuilt.RebuiltTree(ctx, btrfsprim.EXTENT_TREE_OBJECTID)
 	var extentItems *containers.SortedMap[btrfsprim.Key, btrfsutil.ItemPtr]
-	if extentTree != nil {
+	if extentTree, err := o.rebuilt.RebuiltTree(ctx, btrfsprim.EXTENT_TREE_OBJECTID); err == nil {
 		extentItems = extentTree.RebuiltAcquireItems(ctx)
 		defer extentTree.RebuiltReleaseItems()
 	}
@@ -416,7 +415,7 @@ func (o *rebuilder) processSettledItemQueue(ctx context.Context) error {
 			ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.process.item", key)
 			item := keyAndBody{
 				itemToVisit: key,
-				Body:        o.rebuilt.RebuiltTree(ctx, key.TreeID).ReadItem(ctx, key.Key),
+				Body:        discardErr(o.rebuilt.RebuiltTree(ctx, key.TreeID)).ReadItem(ctx, key.Key),
 			}
 			if key.TreeID == btrfsprim.EXTENT_TREE_OBJECTID &&
 				(key.ItemType == btrfsprim.EXTENT_ITEM_KEY || key.ItemType == btrfsprim.METADATA_ITEM_KEY) {
@@ -503,7 +502,7 @@ func (o *rebuilder) processAugmentQueue(ctx context.Context) error {
 			}
 			// This will call o.AddedItem as nescessary, which
 			// inserts to o.addedItemQueue.
-			o.rebuilt.RebuiltTree(ctx, treeID).RebuiltAddRoot(ctx, nodeAddr)
+			discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltAddRoot(ctx, nodeAddr)
 			progress.N++
 			progressWriter.Set(progress)
 		}
@@ -550,7 +549,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob
 		} else {
 			choices[choice] = ChoiceInfo{
 				Count:      1,
-				Distance:   discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
+				Distance:   discardOK(discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
 				Generation: o.scan.Graph.Nodes[choice].Generation,
 			}
 		}
@@ -564,7 +563,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob
 			} else {
 				choices[choice] = ChoiceInfo{
 					Count:      1,
-					Distance:   discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
+					Distance:   discardOK(discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
 					Generation: o.scan.Graph.Nodes[choice].Generation,
 				}
 			}
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
index 0c52556..e227cc7 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
@@ -51,7 +51,7 @@ func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID)
 		o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
 		return 0, btrfsitem.Root{}, false
 	}
-	itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey)
+	itemBody := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).ReadItem(ctx, foundKey)
 	defer itemBody.Free()
 	switch itemBody := itemBody.(type) {
 	case *btrfsitem.Root:
@@ -77,7 +77,7 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
 		o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID)
 		return 0, false
 	}
-	itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key())
+	itemBody := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).ReadItem(ctx, wantKey.Key.Key())
 	defer itemBody.Free()
 	switch itemBody := itemBody.(type) {
 	case *btrfsitem.UUIDMap:
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
index 0526e93..382d88b 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
@@ -43,8 +43,8 @@ func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfspri
 }
 
 func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsprim.Key, ok bool) {
-	tree := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
+	if err != nil {
 		o.enqueueRetry(wantKey.TreeID)
 		return btrfsprim.Key{}, false
 	}
@@ -98,8 +98,8 @@ func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfs
 }
 
 func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool) {
-	tree := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
+	if err != nil {
 		o.enqueueRetry(wantKey.TreeID)
 		return false
 	}
@@ -144,8 +144,8 @@ func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID
 	}
 	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
 
-	tree := o.rebuilt.RebuiltTree(ctx, treeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, treeID)
+	if err != nil {
 		o.enqueueRetry(treeID)
 		return
 	}
@@ -273,8 +273,8 @@ func (o graphCallbacks) _wantRange(
 	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
 	wantKey.Key.OffsetType = offsetRange
 
-	tree := o.rebuilt.RebuiltTree(ctx, treeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, treeID)
+	if err != nil {
 		o.enqueueRetry(treeID)
 		return
 	}
@@ -389,7 +389,7 @@ func (o graphCallbacks) WantCSum(ctx context.Context, reason string, inodeTree,
 		o.enqueueRetry(inodeTree)
 		return
 	}
-	tree := o.rebuilt.RebuiltTree(inodeCtx, inodeTree)
+	tree := discardErr(o.rebuilt.RebuiltTree(inodeCtx, inodeTree))
 	inodePtr, ok := tree.RebuiltAcquireItems(inodeCtx).Load(inodeWant.Key.Key())
 	tree.RebuiltReleaseItems()
 	if !ok {
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/util.go b/cmd/btrfs-rec/inspect/rebuildtrees/util.go
index 842fb55..ee06394 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/util.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/util.go
@@ -19,3 +19,7 @@ func roundUp[T constraints.Integer](n, d T) T {
 func discardOK[T any](val T, _ bool) T {
 	return val
 }
+
+func discardErr[T any](val T, _ error) T {
+	return val
+}
diff --git a/cmd/btrfs-rec/main.go b/cmd/btrfs-rec/main.go
index da3aced..26857f0 100644
--- a/cmd/btrfs-rec/main.go
+++ b/cmd/btrfs-rec/main.go
@@ -49,9 +49,10 @@ var globalFlags struct {
 	logLevel textui.LogLevelFlag
 	pvs      []string
 
-	mappings string
-	nodeList string
-	rebuild  bool
+	mappings  string
+	nodeList  string
+	rebuildV1 bool
+	rebuildV2 bool
 
 	stopProfiling profile.StopFunc
 
@@ -101,8 +102,11 @@ func main() {
 		"load node list (output of 'btrfs-recs inspect [rebuild-mappings] list-nodes') from external JSON file `nodes.json`")
 	noError(argparser.MarkPersistentFlagFilename("node-list"))
 
-	argparser.PersistentFlags().BoolVar(&globalFlags.rebuild, "rebuild", false,
-		"attempt to rebuild broken btrees when reading")
+	argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV1, "rebuild", false,
+		"attempt to rebuild broken btrees when reading (v1)")
+
+	argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV2, "rebuild-v2", false,
+		"attempt to rebuild broken btrees when reading (v2)")
 
 	globalFlags.stopProfiling = profile.AddProfileFlags(argparser.PersistentFlags(), "profile.")
 
@@ -210,15 +214,24 @@ func runWithRawFSAndNodeList(runE func(*btrfs.FS, []btrfsvol.LogicalAddr, *cobra
 func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvol.LogicalAddr, *cobra.Command, []string) error) func(*cobra.Command, []string) error {
 	inner := func(fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr, cmd *cobra.Command, args []string) error {
 		var rfs btrfs.ReadableFS = fs
-		if globalFlags.rebuild {
+		if globalFlags.rebuildV1 {
 			rfs = btrfsutil.NewOldRebuiltForrest(fs)
+		} else if globalFlags.rebuildV2 {
+			ctx := cmd.Context()
+
+			graph, err := btrfsutil.ReadGraph(ctx, fs, nodeList)
+			if err != nil {
+				return err
+			}
+
+			rfs = btrfsutil.NewRebuiltForrest(fs, graph, nil)
 		}
 
 		return runE(rfs, nodeList, cmd, args)
 	}
 
 	return func(cmd *cobra.Command, args []string) error {
-		if wantNodeList {
+		if wantNodeList || globalFlags.rebuildV2 {
 			return runWithRawFSAndNodeList(inner)(cmd, args)
 		}
 		return runWithRawFS(func(fs *btrfs.FS, cmd *cobra.Command, args []string) error {
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 860a49c..1b55642 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -24,12 +24,17 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
+type KeyAndSize struct {
+	Key  btrfsprim.Key
+	Size uint32
+}
+
 type GraphNode struct {
 	Addr       btrfsvol.LogicalAddr
 	Level      uint8
 	Generation btrfsprim.Generation
 	Owner      btrfsprim.ObjID
-	Items      []btrfsprim.Key
+	Items      []KeyAndSize
 }
 
 func (n GraphNode) NumItems(g Graph) int {
@@ -47,7 +52,7 @@ func (n GraphNode) MinItem(g Graph) btrfsprim.Key {
 	}
 	switch n.Level {
 	case 0:
-		return n.Items[0]
+		return n.Items[0].Key
 	default:
 		return g.EdgesFrom[n.Addr][0].ToKey
 	}
@@ -59,7 +64,7 @@ func (n GraphNode) MaxItem(g Graph) btrfsprim.Key {
 	}
 	switch n.Level {
 	case 0:
-		return n.Items[len(n.Items)-1]
+		return n.Items[len(n.Items)-1].Key
 	default:
 		return g.EdgesFrom[n.Addr][len(g.EdgesFrom[n.Addr])-1].ToKey
 	}
@@ -225,11 +230,13 @@ func (g Graph) InsertNode(node *btrfstree.Node) {
 			}
 		}
 		kps := make([]GraphEdge, 0, cnt)
-		keys := make([]btrfsprim.Key, len(node.BodyLeaf))
-		nodeData.Items = keys
+		nodeData.Items = make([]KeyAndSize, len(node.BodyLeaf))
 		g.Nodes[node.Head.Addr] = nodeData
 		for i, item := range node.BodyLeaf {
-			keys[i] = item.Key
+			nodeData.Items[i] = KeyAndSize{
+				Key:  item.Key,
+				Size: item.BodySize,
+			}
 			if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
 				kps = append(kps, GraphEdge{
 					FromRoot:     node.Head.Addr,
diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go
index 3a7e6e6..fdc826c 100644
--- a/lib/btrfsutil/rebuilt_callbacks.go
+++ b/lib/btrfsutil/rebuilt_callbacks.go
@@ -32,8 +32,8 @@ func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, b
 }
 
 func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, ok bool) {
-	rootTree := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
-	if rootTree == nil {
+	rootTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+	if err != nil {
 		return 0, btrfsitem.Root{}, false
 	}
 	tgt := btrfsprim.Key{
@@ -48,9 +48,9 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 	if !ok {
 		return 0, btrfsitem.Root{}, false
 	}
-	itemBody := cb.forrest.readItem(ctx, itemPtr)
-	defer itemBody.Free()
-	switch itemBody := itemBody.(type) {
+	item := cb.forrest.readItem(ctx, itemPtr)
+	defer item.Body.Free()
+	switch itemBody := item.Body.(type) {
 	case *btrfsitem.Root:
 		return btrfsprim.Generation(itemKey.Offset), *itemBody, true
 	case *btrfsitem.Error:
@@ -63,8 +63,8 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 }
 
 func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
-	uuidTree := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
-	if uuidTree == nil {
+	uuidTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+	if err != nil {
 		return 0, false
 	}
 	tgt := btrfsitem.UUIDToKey(uuid)
@@ -73,9 +73,9 @@ func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfs
 	if !ok {
 		return 0, false
 	}
-	itemBody := cb.forrest.readItem(ctx, itemPtr)
-	defer itemBody.Free()
-	switch itemBody := itemBody.(type) {
+	item := cb.forrest.readItem(ctx, itemPtr)
+	defer item.Body.Free()
+	switch itemBody := item.Body.(type) {
 	case *btrfsitem.UUIDMap:
 		return itemBody.ObjID, true
 	case *btrfsitem.Error:
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 4249396..b935d85 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -6,13 +6,16 @@ package btrfsutil
 
 import (
 	"context"
+	"fmt"
 
 	"github.com/datawire/dlib/dlog"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
 	"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/maps"
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
@@ -98,42 +101,57 @@ func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallba
 }
 
 // RebuiltTree returns a given tree, initializing it if nescessary.
-// If it is unable to initialize the tree, then nil is returned, and
-// nothing is done to the forrest.
 //
 // The tree is initialized with the normal root node of the tree.
 //
 // This is identical to .ForrestLookup(), but returns a concrete type
 // rather than an interface.
-func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
+func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) (*RebuiltTree, error) {
 	ctx = ts.treesMu.Lock(ctx)
 	defer ts.treesMu.Unlock()
-	if !ts.addTree(ctx, treeID, nil) {
-		return nil
+	ts.rebuildTree(ctx, treeID, nil)
+	tree := ts.trees[treeID]
+	if tree.ancestorLoop && tree.rootErr == nil {
+		var loop []btrfsprim.ObjID
+		for ancestor := tree; true; ancestor = ancestor.Parent {
+			loop = append(loop, ancestor.ID)
+			if slices.Contains(ancestor.ID, loop[:len(loop)-1]) {
+				break
+			}
+		}
+		tree.rootErr = fmt.Errorf("loop detected: %v", loop)
 	}
-	return ts.trees[treeID]
+	if tree.rootErr != nil {
+		return nil, tree.rootErr
+	}
+	return tree, nil
 }
 
-func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
-	if tree, ok := ts.trees[treeID]; ok {
-		return tree != nil
+func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) {
+	loop := false
+	if maps.HasKey(ts.trees, treeID) {
+		loop = slices.Contains(treeID, stack)
+		if !loop {
+			return
+		}
 	}
+
+	stack = append(stack, treeID)
+	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack)
 	defer func() {
-		if !ok {
-			// Store a negative cache of this.  tree.RebuiltAddRoot() for the ROOT or
-			// UUID trees will call .flushNegativeCache().
-			ts.trees[treeID] = nil
+		if ts.trees[treeID].rootErr != nil {
+			dlog.Errorf(ctx, "failed to add tree: %v", ts.trees[treeID].rootErr)
 		}
 	}()
-	stack = append(stack, treeID)
-	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack)
 	dlog.Info(ctx, "adding tree...")
-	if slices.Contains(treeID, stack[:len(stack)-1]) {
-		dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack)
-		return false
+
+	if loop {
+		ts.trees[treeID].ancestorLoop = true
+		dlog.Error(ctx, "loop detected")
+		return
 	}
 
-	tree := &RebuiltTree{
+	ts.trees[treeID] = &RebuiltTree{
 		ID:      treeID,
 		Roots:   make(containers.Set[btrfsvol.LogicalAddr]),
 		forrest: ts,
@@ -153,48 +171,43 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
 		sb, _ := ts.inner.Superblock()
 		root = sb.BlockGroupRoot
 	default:
-		if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) {
-			dlog.Error(ctx, "failed to add tree: add ROOT_TREE")
-			return false
-		}
 		rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID)
 		if !ok {
-			dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM")
-			return false
+			ts.trees[treeID].rootErr = btrfstree.ErrNoTree
+			return
 		}
 		root = rootItem.ByteNr
-		tree.UUID = rootItem.UUID
+		ts.trees[treeID].UUID = rootItem.UUID
 		if rootItem.ParentUUID != (btrfsprim.UUID{}) {
-			tree.ParentGen = rootOff
-			if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
-				return false
-			}
+			ts.trees[treeID].ParentGen = rootOff
 			parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
 			if !ok {
-				dlog.Errorf(ctx, "failed to add tree: lookup UUID %v", rootItem.ParentUUID)
-				return false
+				ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID)
+				return
 			}
-			if !ts.addTree(ctx, parentID, stack) {
-				dlog.Errorf(ctx, "failed to add tree: add parent tree %v", parentID)
-				return false
+			ts.rebuildTree(ctx, parentID, stack)
+			ts.trees[treeID].Parent = ts.trees[parentID]
+			switch {
+			case ts.trees[treeID].Parent.ancestorLoop:
+				ts.trees[treeID].ancestorLoop = true
+				return
+			case ts.trees[treeID].Parent.rootErr != nil:
+				ts.trees[treeID].rootErr = fmt.Errorf("failed to rebuild parent tree: %v: %w", parentID, ts.trees[treeID].Parent.rootErr)
+				return
 			}
-			tree.Parent = ts.trees[parentID]
 		}
 	}
 
-	ts.trees[treeID] = tree
 	if root != 0 {
-		tree.RebuiltAddRoot(ctx, root)
+		ts.trees[treeID].RebuiltAddRoot(ctx, root)
 	}
-
-	return true
 }
 
 func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
 	_ = ts.treesMu.Lock(ctx)
 	defer ts.treesMu.Unlock()
 	for treeID, tree := range ts.trees {
-		if tree == nil {
+		if tree.rootErr != nil || tree.ancestorLoop {
 			delete(ts.trees, treeID)
 		}
 	}
@@ -210,9 +223,46 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob
 	defer ts.treesMu.Unlock()
 	ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
 	for treeID, tree := range ts.trees {
-		if tree != nil && len(tree.Roots) > 0 {
+		if len(tree.Roots) > 0 {
 			ret[treeID] = tree.Roots
 		}
 	}
 	return ret
 }
+
+// btrfs.ReadableFS interface //////////////////////////////////////////////////////////////////////////////////////////
+
+var _ btrfs.ReadableFS = (*RebuiltForrest)(nil)
+
+// Name implements btrfs.ReadableFS.
+func (ts *RebuiltForrest) Name() string {
+	return ts.inner.Name()
+}
+
+// ForrestLookup implements btrfstree.Forrest (and btrfs.ReadableFS).
+//
+// It is identical to .RebuiltTree(), but returns an interface rather
+// than a concrete type.
+func (ts *RebuiltForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfstree.Tree, error) {
+	return ts.RebuiltTree(ctx, treeID)
+}
+
+// Superblock implements btrfstree.NodeSource (and btrfs.ReadableFS).
+func (ts *RebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
+	return ts.inner.Superblock()
+}
+
+// AcquireNode implements btrfstree.NodeSource (and btrfs.ReadableFS).
+func (ts *RebuiltForrest) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp btrfstree.NodeExpectations) (*btrfstree.Node, error) {
+	return ts.inner.AcquireNode(ctx, addr, exp)
+}
+
+// ReleaseNode implements btrfstree.NodeSource (and btrfs.ReadableFS).
+func (ts *RebuiltForrest) ReleaseNode(node *btrfstree.Node) {
+	ts.inner.ReleaseNode(node)
+}
+
+// ReadAt implements diskio.ReaderAt[btrfsvol.LogicalAddr] (and btrfs.ReadableFS).
+func (ts *RebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
+	return ts.inner.ReadAt(p, off)
+}
diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go
new file mode 100644
index 0000000..96749c4
--- /dev/null
+++ b/lib/btrfsutil/rebuilt_forrest_test.go
@@ -0,0 +1,193 @@
+// Copyright (C) 2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsutil
+
+import (
+	"context"
+	"testing"
+
+	"github.com/datawire/dlib/dlog"
+	"github.com/stretchr/testify/assert"
+
+	"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/btrfsvol"
+)
+
+type rebuiltForrestCallbacks struct {
+	addedItem  func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
+	addedRoot  func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr)
+	lookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
+	lookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
+}
+
+func (cbs rebuiltForrestCallbacks) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+	cbs.addedItem(ctx, tree, key)
+}
+
+func (cbs rebuiltForrestCallbacks) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+	cbs.addedRoot(ctx, tree, root)
+}
+
+func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+	return cbs.lookupRoot(ctx, tree)
+}
+
+func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+	return cbs.lookupUUID(ctx, uuid)
+}
+
+func TestRebuiltTreeCycles(t *testing.T) {
+	t.Parallel()
+
+	ctx := dlog.NewTestContext(t, true)
+
+	type mockRoot struct {
+		ID         btrfsprim.ObjID
+		UUID       btrfsprim.UUID
+		ParentUUID btrfsprim.UUID
+		ParentGen  btrfsprim.Generation
+	}
+	roots := []mockRoot{
+		{
+			ID:         306,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000006"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentGen:  1005,
+		},
+		{
+			ID:         305,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+			ParentGen:  1004,
+		},
+		{
+			ID:         304,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"),
+			ParentGen:  1003,
+		},
+		{
+			ID:         303,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentGen:  1002,
+		},
+	}
+
+	cbs := rebuiltForrestCallbacks{
+		addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+			// do nothing
+		},
+		addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+			// do nothing
+		},
+		lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+			for _, root := range roots {
+				if root.ID == tree {
+					return root.ParentGen, btrfsitem.Root{
+						Generation: 2000,
+						UUID:       root.UUID,
+						ParentUUID: root.ParentUUID,
+					}, true
+				}
+			}
+			return 0, btrfsitem.Root{}, false
+		},
+		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+			for _, root := range roots {
+				if root.UUID == uuid {
+					return root.ID, true
+				}
+			}
+			return 0, false
+		},
+	}
+
+	rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+
+	tree, err := rfs.RebuiltTree(ctx, 306)
+	assert.EqualError(t, err, `loop detected: [306 305 304 303 305]`)
+	assert.Nil(t, tree)
+
+	assert.NotNil(t, rfs.trees[305])
+	tree, err = rfs.RebuiltTree(ctx, 305)
+	assert.EqualError(t, err, `loop detected: [305 304 303 305]`)
+	assert.Nil(t, tree)
+
+	assert.NotNil(t, rfs.trees[304])
+	tree, err = rfs.RebuiltTree(ctx, 304)
+	assert.EqualError(t, err, `loop detected: [304 303 305 304]`)
+	assert.Nil(t, tree)
+
+	assert.NotNil(t, rfs.trees[303])
+	tree, err = rfs.RebuiltTree(ctx, 303)
+	assert.EqualError(t, err, `loop detected: [303 305 304 303]`)
+	assert.Nil(t, tree)
+}
+
+func TestRebuiltTreeParentErr(t *testing.T) {
+	t.Parallel()
+
+	ctx := dlog.NewTestContext(t, true)
+
+	type mockRoot struct {
+		ID         btrfsprim.ObjID
+		UUID       btrfsprim.UUID
+		ParentUUID btrfsprim.UUID
+		ParentGen  btrfsprim.Generation
+	}
+	roots := []mockRoot{
+		{
+			ID:         305,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+			ParentGen:  1004,
+		},
+		{
+			ID:   304,
+			UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+		},
+	}
+
+	cbs := rebuiltForrestCallbacks{
+		addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+			// do nothing
+		},
+		addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+			// do nothing
+		},
+		lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+			if tree == 304 {
+				// Force a fault.
+				return 0, btrfsitem.Root{}, false
+			}
+			for _, root := range roots {
+				if root.ID == tree {
+					return root.ParentGen, btrfsitem.Root{
+						Generation: 2000,
+						UUID:       root.UUID,
+						ParentUUID: root.ParentUUID,
+					}, true
+				}
+			}
+			return 0, btrfsitem.Root{}, false
+		},
+		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+			for _, root := range roots {
+				if root.UUID == uuid {
+					return root.ID, true
+				}
+			}
+			return 0, false
+		},
+	}
+
+	rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+
+	tree, err := rfs.RebuiltTree(ctx, 305)
+	assert.EqualError(t, err, `failed to rebuild parent tree: 304: tree does not exist`)
+	assert.Nil(t, tree)
+}
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index d1d1319..e5faa45 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.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"
@@ -24,7 +23,7 @@ func (ptr ItemPtr) String() string {
 	return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot)
 }
 
-func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
+func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfstree.Item {
 	graphInfo, ok := ts.graph.Nodes[ptr.Node]
 	if !ok {
 		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for node@%v not mentioned in the in-memory graph", ptr.Node))
@@ -62,5 +61,8 @@ func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.I
 		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for out-of-bounds item slot: slot=%v len=%v",
 			ptr.Slot, len(items)))
 	}
-	return items[ptr.Slot].Body.CloneItem()
+
+	item := items[ptr.Slot]
+	item.Body = item.Body.CloneItem()
+	return item
 }
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 177b859..9ab0356 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -14,6 +14,7 @@ import (
 
 	"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"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
@@ -23,6 +24,10 @@ import (
 
 type RebuiltTree struct {
 	// static
+
+	rootErr      error
+	ancestorLoop bool
+
 	ID        btrfsprim.ObjID
 	UUID      btrfsprim.UUID
 	Parent    *RebuiltTree
@@ -30,8 +35,11 @@ type RebuiltTree struct {
 	forrest   *RebuiltForrest
 
 	// mutable
-	mu    sync.RWMutex
+
+	mu sync.RWMutex
+
 	Roots containers.Set[btrfsvol.LogicalAddr]
+
 	// There are 3 more mutable "members" that are protected by
 	// `mu`; but they live in a shared Cache.  They are all
 	// derived from tree.Roots, which is why it's OK if they get
@@ -81,9 +89,12 @@ type rebuiltPathInfo struct {
 }
 
 type rebuiltNodeIndex struct {
-	// leafToRoots contains all leafs (lvl=0) in the filesystem
-	// that pass .isOwnerOK, whether or not they're in the tree.
-	leafToRoots map[btrfsvol.LogicalAddr]rebuiltRoots
+	// idToTree contains this tree, and all of its ancestor trees.
+	idToTree map[btrfsprim.ObjID]*RebuiltTree
+
+	// nodeToRoots contains all nodes in the filesystem that pass
+	// .isOwnerOK, whether or not they're in the tree.
+	nodeToRoots map[btrfsvol.LogicalAddr]rebuiltRoots
 }
 
 func (tree *RebuiltTree) acquireNodeIndex(ctx context.Context) rebuiltNodeIndex {
@@ -108,11 +119,12 @@ func (tree *RebuiltTree) uncachedNodeIndex(ctx context.Context) rebuiltNodeIndex
 	}
 
 	ret := rebuiltNodeIndex{
-		leafToRoots: make(map[btrfsvol.LogicalAddr]rebuiltRoots),
+		idToTree:    indexer.idToTree,
+		nodeToRoots: make(map[btrfsvol.LogicalAddr]rebuiltRoots),
 	}
 	for node, roots := range indexer.run(ctx) {
-		if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 {
-			ret.leafToRoots[node] = roots
+		if len(roots) > 0 {
+			ret.nodeToRoots[node] = roots
 		}
 	}
 	return ret
@@ -313,9 +325,9 @@ func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedM
 	defer tree.mu.RUnlock()
 
 	var leafs []btrfsvol.LogicalAddr
-	for leaf, roots := range tree.acquireNodeIndex(ctx).leafToRoots {
-		if maps.HaveAnyKeysInCommon(tree.Roots, roots) == inc {
-			leafs = append(leafs, leaf)
+	for node, roots := range tree.acquireNodeIndex(ctx).nodeToRoots {
+		if tree.forrest.graph.Nodes[node].Level == 0 && maps.HaveAnyKeysInCommon(tree.Roots, roots) == inc {
+			leafs = append(leafs, node)
 		}
 	}
 	tree.releaseNodeIndex()
@@ -329,17 +341,17 @@ func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedM
 	for i, leaf := range leafs {
 		stats.Leafs.N = i
 		progressWriter.Set(stats)
-		for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
+		for j, itemKeyAndSize := range tree.forrest.graph.Nodes[leaf].Items {
 			newPtr := ItemPtr{
 				Node: leaf,
 				Slot: j,
 			}
-			if oldPtr, exists := index.Load(itemKey); !exists {
-				index.Store(itemKey, newPtr)
+			if oldPtr, exists := index.Load(itemKeyAndSize.Key); !exists {
+				index.Store(itemKeyAndSize.Key, newPtr)
 				stats.NumItems++
 			} else {
 				if tree.RebuiltShouldReplace(oldPtr.Node, newPtr.Node) {
-					index.Store(itemKey, newPtr)
+					index.Store(itemKeyAndSize.Key, newPtr)
 				}
 				stats.NumDups++
 			}
@@ -388,14 +400,14 @@ func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalA
 }
 
 type rebuiltRootStats struct {
-	Leafs      textui.Portion[int]
+	Nodes      textui.Portion[int]
 	AddedLeafs int
 	AddedItems int
 }
 
 func (s rebuiltRootStats) String() string {
 	return textui.Sprintf("%v (added %v leafs, added %v items)",
-		s.Leafs, s.AddedLeafs, s.AddedItems)
+		s.Nodes, s.AddedLeafs, s.AddedItems)
 }
 
 // RebuiltAddRoot adds an additional root node to the tree.  It is
@@ -411,27 +423,27 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 
 	if extCB, ok := tree.forrest.cb.(RebuiltForrestExtendedCallbacks); ok {
 		var stats rebuiltRootStats
-		leafToRoots := tree.acquireNodeIndex(ctx).leafToRoots
-		stats.Leafs.D = len(leafToRoots)
+		nodeToRoots := tree.acquireNodeIndex(ctx).nodeToRoots
+		stats.Nodes.D = len(nodeToRoots)
 		progressWriter := textui.NewProgress[rebuiltRootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-		for i, leaf := range maps.SortedKeys(leafToRoots) {
-			stats.Leafs.N = i
+		for i, node := range maps.SortedKeys(nodeToRoots) {
+			stats.Nodes.N = i
 			progressWriter.Set(stats)
 
-			if maps.HaveAnyKeysInCommon(tree.Roots, leafToRoots[leaf]) || !maps.HasKey(leafToRoots[leaf], rootNode) {
+			if tree.forrest.graph.Nodes[node].Level > 0 || maps.HaveAnyKeysInCommon(tree.Roots, nodeToRoots[node]) || !maps.HasKey(nodeToRoots[node], rootNode) {
 				continue
 			}
 
 			stats.AddedLeafs++
 			progressWriter.Set(stats)
 
-			for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
-				extCB.AddedItem(ctx, tree.ID, itemKey)
+			for _, itemKeyAndSize := range tree.forrest.graph.Nodes[node].Items {
+				extCB.AddedItem(ctx, tree.ID, itemKeyAndSize.Key)
 				stats.AddedItems++
 				progressWriter.Set(stats)
 			}
 		}
-		stats.Leafs.N = len(leafToRoots)
+		stats.Nodes.N = len(nodeToRoots)
 		tree.releaseNodeIndex()
 		progressWriter.Set(stats)
 		progressWriter.Done()
@@ -473,7 +485,7 @@ func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsi
 	if !ok {
 		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltTree.ReadItem called for not-included key: %v", key))
 	}
-	return tree.forrest.readItem(ctx, ptr)
+	return tree.forrest.readItem(ctx, ptr).Body
 }
 
 // RebuiltLeafToRoots returns the list of potential roots (to pass to
@@ -486,7 +498,7 @@ func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.L
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
 	ret := make(containers.Set[btrfsvol.LogicalAddr])
-	for root := range tree.acquireNodeIndex(ctx).leafToRoots[leaf] {
+	for root := range tree.acquireNodeIndex(ctx).nodeToRoots[leaf] {
 		if tree.Roots.Has(root) {
 			panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): tree contains root=%v but not leaf",
 				tree.ID, leaf, root))
@@ -499,3 +511,262 @@ func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.L
 	}
 	return ret
 }
+
+// btrfstree.Tree interface ////////////////////////////////////////////////////////////////////////////////////////////
+
+var _ btrfstree.Tree = (*RebuiltTree)(nil)
+
+// TreeParentID implements btrfstree.Tree.
+func (tree *RebuiltTree) TreeParentID(_ context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) {
+	if tree.Parent == nil {
+		return 0, 0, nil
+	}
+	return tree.Parent.ID, tree.ParentGen, nil
+}
+
+// TreeLookup implements btrfstree.Tree.
+//
+// BUG(lukeshu): Errors in the tree are not ever returned.
+func (tree *RebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btrfstree.Item, error) {
+	return tree.TreeSearch(ctx, btrfstree.SearchExactKey(key))
+}
+
+// TreeSearch implements btrfstree.Tree.  It is a thin wrapper around
+// tree.RebuiltItems(ctx).Search (to do the search) and
+// tree.TreeLookup (to read item bodies).
+//
+// BUG(lukeshu): Errors in the tree are not ever returned.
+func (tree *RebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
+	_, ptr, ok := tree.RebuiltAcquireItems(ctx).Search(func(_ btrfsprim.Key, ptr ItemPtr) int {
+		straw := tree.forrest.graph.Nodes[ptr.Node].Items[ptr.Slot]
+		return searcher.Search(straw.Key, straw.Size)
+	})
+	tree.RebuiltReleaseItems()
+	if !ok {
+		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, btrfstree.ErrNoItem)
+	}
+	return tree.forrest.readItem(ctx, ptr), nil
+}
+
+// TreeRange implements btrfstree.Tree.  It is a thin wrapper around
+// tree.RebuiltItems(ctx).Range (to do the iteration) and
+// tree.TreeLookup (to read item bodies).
+//
+// BUG(lukeshu): Errors in the tree are not ever returned.
+func (tree *RebuiltTree) TreeRange(ctx context.Context, handleFn func(btrfstree.Item) bool) error {
+	tree.RebuiltAcquireItems(ctx).Range(func(_ btrfsprim.Key, ptr ItemPtr) bool {
+		return handleFn(tree.forrest.readItem(ctx, ptr))
+	})
+	tree.RebuiltReleaseItems()
+	return nil
+}
+
+// TreeSubrange implements btrfstree.Tree.  It is a thin wrapper
+// around tree.RebuiltItems(ctx).Subrange (to do the iteration) and
+// tree.TreeLookup (to read item bodies).
+//
+// BUG(lukeshu): Errors in the tree are not ever returned.
+func (tree *RebuiltTree) TreeSubrange(ctx context.Context,
+	min int,
+	searcher btrfstree.TreeSearcher,
+	handleFn func(btrfstree.Item) bool,
+) error {
+	var cnt int
+	tree.RebuiltAcquireItems(ctx).Subrange(
+		func(_ btrfsprim.Key, ptr ItemPtr) int {
+			straw := tree.forrest.graph.Nodes[ptr.Node].Items[ptr.Slot]
+			return searcher.Search(straw.Key, straw.Size)
+		},
+		func(_ btrfsprim.Key, ptr ItemPtr) bool {
+			cnt++
+			return handleFn(tree.forrest.readItem(ctx, ptr))
+		},
+	)
+	tree.RebuiltReleaseItems()
+
+	if cnt < min {
+		return btrfstree.ErrNoItem
+	}
+
+	return nil
+}
+
+// TreeWalk implements btrfstree.Tree.
+func (tree *RebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+
+	if _, err := tree.forrest.Superblock(); err != nil && cbs.BadSuperblock != nil {
+		cbs.BadSuperblock(err)
+	}
+
+	walker := &rebuiltWalker{
+		// Input: tree
+		tree:      tree,
+		nodeIndex: tree.acquireNodeIndex(ctx),
+		items:     tree.RebuiltAcquireItems(ctx),
+
+		// Input: args
+		cbs: cbs,
+
+		// State
+		visited: make(containers.Set[btrfsvol.LogicalAddr]),
+	}
+	defer tree.releaseNodeIndex()
+	defer tree.RebuiltReleaseItems()
+
+	for _, root := range maps.SortedKeys(tree.Roots) {
+		path := btrfstree.Path{
+			btrfstree.PathRoot{
+				Forrest:      tree.forrest,
+				TreeID:       tree.ID,
+				ToAddr:       root,
+				ToGeneration: tree.forrest.graph.Nodes[root].Generation,
+				ToLevel:      tree.forrest.graph.Nodes[root].Level,
+			},
+		}
+		walker.walk(ctx, path)
+		if ctx.Err() != nil {
+			return
+		}
+	}
+}
+
+type rebuiltWalker struct {
+	// Input: tree
+	tree      *RebuiltTree
+	nodeIndex rebuiltNodeIndex
+	items     *containers.SortedMap[btrfsprim.Key, ItemPtr]
+
+	// Input: args
+	cbs btrfstree.TreeWalkHandler
+
+	// State
+	visited containers.Set[btrfsvol.LogicalAddr]
+}
+
+func (walker *rebuiltWalker) walk(ctx context.Context, path btrfstree.Path) {
+	if ctx.Err() != nil {
+		return
+	}
+
+	// 001
+	nodeAddr, nodeExp, ok := path.NodeExpectations(ctx, true)
+	if !ok {
+		panic(fmt.Errorf("should not happen: btrfsutil.rebuiltWalker.walk called with non-node path: %v",
+			path))
+	}
+	if err := walker.tree.forrest.graph.BadNodes[nodeAddr]; err != nil {
+		if walker.cbs.BadNode != nil {
+			_ = walker.cbs.BadNode(path, nil, err)
+		}
+		return
+	}
+	// 001-002
+	nodeInfo := walker.tree.forrest.graph.Nodes[nodeAddr]
+	if err := nodeInfo.CheckExpectations(walker.tree.forrest.graph, nodeExp); err != nil {
+		if walker.cbs.BadNode != nil {
+			// 001
+			node, _ := walker.tree.forrest.AcquireNode(ctx, nodeAddr, nodeExp)
+			defer walker.tree.forrest.ReleaseNode(node)
+			if ctx.Err() != nil {
+				return
+			}
+			// 002
+			_ = walker.cbs.BadNode(path, node, err)
+		}
+		return
+	}
+	if walker.visited.Has(nodeAddr) {
+		return
+	}
+	walker.visited.Insert(nodeAddr)
+	if walker.cbs.Node != nil {
+		// 001
+		node, _ := walker.tree.forrest.AcquireNode(ctx, nodeAddr, nodeExp)
+		if ctx.Err() != nil {
+			walker.tree.forrest.ReleaseNode(node)
+			return
+		}
+		// 002
+		walker.cbs.Node(path, node)
+		walker.tree.forrest.ReleaseNode(node)
+		if ctx.Err() != nil {
+			return
+		}
+	}
+
+	// branch a (interior)
+	for i, kp := range walker.tree.forrest.graph.EdgesFrom[nodeAddr] {
+		var toMaxKey btrfsprim.Key
+		for root, rootInfo := range walker.nodeIndex.nodeToRoots[nodeAddr] {
+			if !walker.tree.Roots.Has(root) {
+				continue
+			}
+			if rootInfo.hiMaxItem.Compare(toMaxKey) > 0 {
+				toMaxKey = rootInfo.hiMaxItem
+			}
+		}
+		itemPath := append(path, btrfstree.PathKP{
+			FromTree: walker.tree.forrest.graph.Nodes[nodeAddr].Owner,
+			FromSlot: i,
+
+			ToAddr:       kp.ToNode,
+			ToGeneration: kp.ToGeneration,
+			ToMinKey:     kp.ToKey,
+
+			ToMaxKey: toMaxKey,
+			ToLevel:  kp.ToLevel,
+		})
+		// 003a
+		recurse := walker.cbs.KeyPointer == nil || walker.cbs.KeyPointer(itemPath, btrfstree.KeyPointer{
+			Key:        kp.ToKey,
+			BlockPtr:   kp.ToNode,
+			Generation: kp.ToGeneration,
+		})
+		if ctx.Err() != nil {
+			return
+		}
+		// 004a
+		if recurse {
+			walker.walk(ctx, itemPath)
+			if ctx.Err() != nil {
+				return
+			}
+		}
+	}
+
+	// branch b (leaf)
+	if walker.cbs.Item != nil || walker.cbs.BadItem != nil {
+		for i, keyAndSize := range walker.tree.forrest.graph.Nodes[nodeAddr].Items {
+			ptr, ok := walker.items.Load(keyAndSize.Key)
+			if !ok {
+				panic(fmt.Errorf("should not happen: index does not contain present item %v", keyAndSize.Key))
+			}
+			if ptr.Node != nodeAddr {
+				continue
+			}
+			itemPath := append(path, btrfstree.PathItem{
+				FromTree: walker.tree.forrest.graph.Nodes[nodeAddr].Owner,
+				FromSlot: i,
+
+				ToKey: keyAndSize.Key,
+			})
+			item := walker.tree.forrest.readItem(ctx, ptr)
+			// 003b
+			switch item.Body.(type) {
+			case *btrfsitem.Error:
+				if walker.cbs.BadItem != nil {
+					walker.cbs.BadItem(itemPath, item)
+				}
+			default:
+				if walker.cbs.Item != nil {
+					walker.cbs.Item(itemPath, item)
+				}
+			}
+			if ctx.Err() != nil {
+				return
+			}
+		}
+	}
+}
diff --git a/scripts/main.sh b/scripts/main.sh
index c5fc238..c9c6f4e 100755
--- a/scripts/main.sh
+++ b/scripts/main.sh
@@ -80,7 +80,18 @@ run-btrfs-rec $gendir/4.ls-files.txt \
     --mappings=$gendir/2.mappings.json \
     --rebuild \
     inspect ls-files
+run-btrfs-rec $gendir/4.ls-files.v2.txt \
+    --mappings=$gendir/2.mappings.json \
+    --node-list=$gendir/0.nodes.json \
+    --rebuild-v2 \
+    inspect ls-files
+
 run-btrfs-rec $gendir/4.ls-trees.txt \
     --mappings=$gendir/2.mappings.json \
     --node-list=$gendir/0.nodes.json \
     inspect ls-trees
+run-btrfs-rec $gendir/4.ls-trees.v2.txt \
+    --mappings=$gendir/2.mappings.json \
+    --node-list=$gendir/0.nodes.json \
+    --rebuild-v2 \
+    inspect ls-trees