Merge branch 'lukeshu/rebuilt-v2-pt4-enhance'

7 files changed, 157 insertions, 512 deletions

diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
index b8205ae..466082c 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
@@ -75,7 +75,9 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
 	}
 	ctx = withWant(ctx, logFieldTreeWant, "resolve parent UUID", wantKey)
 	if !o._wantOff(ctx, wantKey) {
-		o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID)
+		if id, ok := o.slowLookupUUID(ctx, uuid); ok {
+			return id, nil
+		}
 		return 0, btrfstree.ErrNoItem
 	}
 	item, _ := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).TreeLookup(ctx, wantKey.Key.Key())
@@ -85,6 +87,9 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
 		return itemBody.ObjID, nil
 	case *btrfsitem.Error:
 		graphCallbacks(o).FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", wantKey, itemBody.Err))
+		if id, ok := o.slowLookupUUID(ctx, uuid); ok {
+			return id, nil
+		}
 		return 0, itemBody.Err
 	default:
 		// This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
@@ -92,3 +97,36 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
 		panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", itemBody))
 	}
 }
+
+func (o forrestCallbacks) slowLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+	rootTree, err := o.rebuilt.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+	if err != nil {
+		o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
+		return 0, false
+	}
+	var ret btrfsprim.ObjID
+	_ = rootTree.TreeRange(ctx, func(item btrfstree.Item) bool {
+		if item.Key.ItemType != btrfsprim.ROOT_ITEM_KEY {
+			return true
+		}
+		switch itemBody := item.Body.(type) {
+		case *btrfsitem.Root:
+			if itemBody.UUID == uuid {
+				ret = item.Key.ObjectID
+				return false
+			}
+		case *btrfsitem.Error:
+			graphCallbacks(o).FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", item.Key, itemBody.Err))
+		default:
+			// This is a panic because the item decoder should not emit ROOT_ITEM items as anything but
+			// btrfsitem.Root or btrfsitem.Error without this code also being updated.
+			panic(fmt.Errorf("should not happen: ROOT_ITEM item has unexpected type: %T", itemBody))
+		}
+		return true
+	})
+	if ret == 0 {
+		o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
+		return 0, false
+	}
+	return ret, true
+}
diff --git a/cmd/btrfs-rec/main.go b/cmd/btrfs-rec/main.go
index ad768de..39ba9ef 100644
--- a/cmd/btrfs-rec/main.go
+++ b/cmd/btrfs-rec/main.go
@@ -17,8 +17,10 @@ import (
 	"github.com/spf13/cobra"
 
 	"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/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsutil"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/profile"
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
@@ -51,8 +53,8 @@ var globalFlags struct {
 
 	mappings  string
 	nodeList  string
-	rebuildV1 bool
-	rebuildV2 bool
+	rebuild   bool
+	treeRoots string
 
 	stopProfiling profile.StopFunc
 
@@ -102,11 +104,12 @@ 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.rebuildV1, "rebuild", false,
-		"attempt to rebuild broken btrees when reading (v1)")
+	argparser.PersistentFlags().BoolVar(&globalFlags.rebuild, "rebuild", false,
+		"attempt to rebuild broken btrees when reading")
 
-	argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV2, "rebuild-v2", false,
-		"attempt to rebuild broken btrees when reading (v2)")
+	argparser.PersistentFlags().StringVar(&globalFlags.treeRoots, "trees", "",
+		"load list of tree roots (output of 'btrfs-recs inspect rebuild-trees') from external JSON file `trees.json`; implies --rebuild")
+	noError(argparser.MarkPersistentFlagFilename("trees"))
 
 	globalFlags.stopProfiling = profile.AddProfileFlags(argparser.PersistentFlags(), "profile.")
 
@@ -214,9 +217,7 @@ 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.rebuildV1 {
-			rfs = btrfsutil.NewOldRebuiltForrest(fs)
-		} else if globalFlags.rebuildV2 {
+		if globalFlags.rebuild || globalFlags.treeRoots != "" {
 			ctx := cmd.Context()
 
 			graph, err := btrfsutil.ReadGraph(ctx, fs, nodeList)
@@ -224,14 +225,24 @@ func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvo
 				return err
 			}
 
-			rfs = btrfsutil.NewRebuiltForrest(fs, graph, nil, true)
+			_rfs := btrfsutil.NewRebuiltForrest(fs, graph, nil, true)
+
+			if globalFlags.treeRoots != "" {
+				roots, err := readJSONFile[map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]](ctx, globalFlags.treeRoots)
+				if err != nil {
+					return err
+				}
+				_rfs.RebuiltAddRoots(ctx, roots)
+			}
+
+			rfs = _rfs
 		}
 
 		return runE(rfs, nodeList, cmd, args)
 	}
 
 	return func(cmd *cobra.Command, args []string) error {
-		if wantNodeList || globalFlags.rebuildV2 {
+		if wantNodeList || globalFlags.rebuild || globalFlags.treeRoots != "" {
 			return runWithRawFSAndNodeList(inner)(cmd, args)
 		}
 		return runWithRawFS(func(fs *btrfs.FS, cmd *cobra.Command, args []string) error {
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
deleted file mode 100644
index a23278c..0000000
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ /dev/null
@@ -1,471 +0,0 @@
-// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
-	"context"
-	"fmt"
-	"sync"
-
-	"github.com/datawire/dlib/derror"
-	"github.com/datawire/dlib/dlog"
-
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
-	"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"
-)
-
-type oldRebuiltTree struct {
-	forrest *OldRebuiltForrest
-
-	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
-	Node btrfsvol.LogicalAddr
-	Err  error
-}
-
-func (e oldRebuiltTreeError) Error() string {
-	return fmt.Sprintf("keys %v-%v: node@%v: %v", e.Min, e.Max, e.Node, e.Err)
-}
-
-func (e oldRebuiltTreeError) Unwrap() error {
-	return e.Err
-}
-
-type oldRebuiltTreeValue struct {
-	Key      btrfsprim.Key
-	ItemSize uint32
-
-	Node oldRebuiltNodeInfo
-	Slot int
-}
-
-type oldRebuiltNodeInfo struct {
-	LAddr      btrfsvol.LogicalAddr
-	Level      uint8
-	Generation btrfsprim.Generation
-	Owner      btrfsprim.ObjID
-	MinItem    btrfsprim.Key
-	MaxItem    btrfsprim.Key
-}
-
-// Compare implements containers.Ordered.
-func (a oldRebuiltTreeValue) Compare(b oldRebuiltTreeValue) int {
-	return a.Key.Compare(b.Key)
-}
-
-func newOldRebuiltTree() oldRebuiltTree {
-	return oldRebuiltTree{
-		Items: new(containers.RBTree[oldRebuiltTreeValue]),
-		Errors: &containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]{
-			MinFn: func(err oldRebuiltTreeError) btrfsprim.Key {
-				return err.Min
-			},
-			MaxFn: func(err oldRebuiltTreeError) btrfsprim.Key {
-				return err.Max
-			},
-		},
-	}
-}
-
-type OldRebuiltForrest struct {
-	inner *btrfs.FS
-
-	// btrfsprim.ROOT_TREE_OBJECTID
-	rootTreeMu sync.Mutex
-	rootTree   *oldRebuiltTree
-	// for all other trees
-	treesMu sync.Mutex
-	trees   map[btrfsprim.ObjID]oldRebuiltTree
-}
-
-var _ btrfs.ReadableFS = (*OldRebuiltForrest)(nil)
-
-// NewOldRebuiltForrest wraps a *btrfs.FS to support looking up
-// information from broken trees.
-//
-// Of the btrfstree.Tree methods:
-//
-//   - TreeRange works on broken trees
-//   - TreeSubrange relies on the tree being properly ordered (which a
-//     broken tree might not be).
-//   - TreeSearch relies on the tree being properly ordered (which a
-//     broken tree might not be).
-//   - TreeLookup relies on the tree being properly ordered (which a
-//     broken tree might not be).
-//
-// NewOldRebuiltForrest attempts to remedy these deficiencies by
-// building an out-of-FS index of all of the items in the tree, and
-// re-implements TreeLookup, TreeSearch, TreeSubrange, and TreeRange
-// using that index.
-func NewOldRebuiltForrest(inner *btrfs.FS) *OldRebuiltForrest {
-	return &OldRebuiltForrest{
-		inner: inner,
-	}
-}
-
-// ForrestLookup implements btrfstree.Forrest.
-func (bt *OldRebuiltForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfstree.Tree, error) {
-	tree := bt.RebuiltTree(ctx, treeID)
-	if tree.RootErr != nil {
-		return nil, tree.RootErr
-	}
-	return tree, nil
-}
-
-// RebuiltTree is a variant of ForrestLookup that returns a concrete
-// type instead of an interface.  An error is indicated by the
-// ret.RootErr member.
-func (bt *OldRebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) oldRebuiltTree {
-	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
-		bt.rootTreeMu.Lock()
-		defer bt.rootTreeMu.Unlock()
-		if bt.rootTree != nil {
-			return *bt.rootTree
-		}
-	} else {
-		bt.treesMu.Lock()
-		defer bt.treesMu.Unlock()
-		if bt.trees == nil {
-			bt.trees = make(map[btrfsprim.ObjID]oldRebuiltTree)
-		}
-		if cacheEntry, exists := bt.trees[treeID]; exists {
-			return cacheEntry
-		}
-	}
-
-	cacheEntry := newOldRebuiltTree()
-	cacheEntry.forrest = bt
-	cacheEntry.ID = treeID
-	dlog.Infof(ctx, "indexing tree %v...", treeID)
-	bt.rawTreeWalk(ctx, treeID, &cacheEntry)
-	dlog.Infof(ctx, "... done indexing tree %v", treeID)
-
-	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
-		bt.rootTree = &cacheEntry
-	} else {
-		bt.trees[treeID] = cacheEntry
-	}
-	return cacheEntry
-}
-
-func discardOK[T any](x T, _ bool) T { return x }
-
-func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
-	sb, err := bt.inner.Superblock()
-	if err != nil {
-		cacheEntry.RootErr = err
-		return
-	}
-	root, err := btrfstree.LookupTreeRoot(ctx, bt, *sb, treeID)
-	if err != nil {
-		cacheEntry.RootErr = err
-		return
-	}
-	tree := &btrfstree.RawTree{
-		Forrest:  btrfstree.RawForrest{NodeSource: bt.inner},
-		TreeRoot: *root,
-	}
-
-	cacheEntry.ParentUUID = root.ParentUUID
-	cacheEntry.ParentGen = root.ParentGen
-
-	var curNode oldRebuiltNodeInfo
-	cbs := btrfstree.TreeWalkHandler{
-		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
-			nodeAddr, nodeExp, _ := path.NodeExpectations(ctx)
-			cacheEntry.Errors.Insert(oldRebuiltTreeError{
-				Min:  nodeExp.MinItem.Val,
-				Max:  nodeExp.MaxItem.Val,
-				Node: nodeAddr,
-				Err:  err,
-			})
-			return false
-		},
-		Node: func(path btrfstree.Path, node *btrfstree.Node) {
-			curNode = oldRebuiltNodeInfo{
-				LAddr:      node.Head.Addr,
-				Level:      node.Head.Level,
-				Generation: node.Head.Generation,
-				Owner:      node.Head.Owner,
-				MinItem:    discardOK(node.MinItem()),
-				MaxItem:    discardOK(node.MaxItem()),
-			}
-		},
-		Item: func(path btrfstree.Path, item btrfstree.Item) {
-			if cacheEntry.Items.Search(func(v oldRebuiltTreeValue) int { return item.Key.Compare(v.Key) }) != nil {
-				// This is a panic because I'm not really sure what the best way to
-				// handle this is, and so if this happens I want the program to crash
-				// and force me to figure out how to handle it.
-				panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, treeID))
-			}
-			cacheEntry.Items.Insert(oldRebuiltTreeValue{
-				Key:      item.Key,
-				ItemSize: item.BodySize,
-
-				Node: curNode,
-				Slot: path[len(path)-1].(btrfstree.PathItem).FromSlot, //nolint:forcetypeassert // has to be
-			})
-		},
-	}
-	cbs.BadItem = cbs.Item
-
-	tree.TreeWalk(ctx, cbs)
-}
-
-func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
-	var errs derror.MultiError
-	tree.Errors.Subrange(
-		func(k btrfsprim.Key) int { return fn(k, 0) },
-		func(v oldRebuiltTreeError) bool {
-			errs = append(errs, v)
-			return true
-		})
-	if len(errs) == 0 {
-		return err
-	}
-	if err != nil {
-		errs = append(errs, err)
-	}
-	return errs
-}
-
-func (bt *OldRebuiltForrest) readNode(ctx context.Context, nodeInfo oldRebuiltNodeInfo) *btrfstree.Node {
-	node, err := bt.AcquireNode(ctx, nodeInfo.LAddr, btrfstree.NodeExpectations{
-		LAddr:      containers.OptionalValue(nodeInfo.LAddr),
-		Level:      containers.OptionalValue(nodeInfo.Level),
-		Generation: containers.OptionalValue(nodeInfo.Generation),
-		Owner: func(treeID btrfsprim.ObjID, gen btrfsprim.Generation) error {
-			if treeID != nodeInfo.Owner || gen != nodeInfo.Generation {
-				return fmt.Errorf("expected owner=%v generation=%v but claims to have owner=%v generation=%v",
-					nodeInfo.Owner, nodeInfo.Generation,
-					treeID, gen)
-			}
-			return nil
-		},
-		MinItem: containers.OptionalValue(nodeInfo.MinItem),
-		MaxItem: containers.OptionalValue(nodeInfo.MaxItem),
-	})
-	if err != nil {
-		panic(fmt.Errorf("should not happen: i/o error: %w", err))
-	}
-
-	return node
-}
-
-// TreeLookup implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btrfstree.Item, error) {
-	return tree.TreeSearch(ctx, btrfstree.SearchExactKey(key))
-}
-
-// TreeSearch implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
-	if tree.RootErr != nil {
-		return btrfstree.Item{}, tree.RootErr
-	}
-
-	indexItem := tree.Items.Search(func(indexItem oldRebuiltTreeValue) int {
-		return searcher.Search(indexItem.Key, indexItem.ItemSize)
-	})
-	if indexItem == nil {
-		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
-	}
-
-	node := tree.forrest.readNode(ctx, indexItem.Value.Node)
-	defer tree.forrest.ReleaseNode(node)
-
-	item := node.BodyLeaf[indexItem.Value.Slot]
-	item.Body = item.Body.CloneItem()
-
-	// Since we were only asked to return 1 item, it isn't
-	// necessary to augment this `nil` with tree.addErrs().
-	return item, nil
-}
-
-// TreeRange implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeRange(ctx context.Context, handleFn func(btrfstree.Item) bool) error {
-	if tree.RootErr != nil {
-		return tree.RootErr
-	}
-
-	var node *btrfstree.Node
-	tree.Items.Range(
-		func(rbnode *containers.RBNode[oldRebuiltTreeValue]) bool {
-			if node == nil || node.Head.Addr != rbnode.Value.Node.LAddr {
-				tree.forrest.ReleaseNode(node)
-				node = tree.forrest.readNode(ctx, rbnode.Value.Node)
-			}
-			return handleFn(node.BodyLeaf[rbnode.Value.Slot])
-		})
-	tree.forrest.ReleaseNode(node)
-
-	return tree.addErrs(func(btrfsprim.Key, uint32) int { return 0 }, nil)
-}
-
-// TreeSubrange implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeSubrange(ctx context.Context, min int, searcher btrfstree.TreeSearcher, handleFn func(btrfstree.Item) bool) error {
-	var node *btrfstree.Node
-	var cnt int
-	tree.Items.Subrange(
-		func(indexItem oldRebuiltTreeValue) int {
-			return searcher.Search(indexItem.Key, indexItem.ItemSize)
-		},
-		func(rbNode *containers.RBNode[oldRebuiltTreeValue]) bool {
-			cnt++
-			if node == nil || node.Head.Addr != rbNode.Value.Node.LAddr {
-				tree.forrest.ReleaseNode(node)
-				node = tree.forrest.readNode(ctx, rbNode.Value.Node)
-			}
-			return handleFn(node.BodyLeaf[rbNode.Value.Slot])
-		})
-	tree.forrest.ReleaseNode(node)
-
-	var err error
-	if cnt < min {
-		err = btrfstree.ErrNoItem
-	}
-	err = tree.addErrs(searcher.Search, err)
-	if err != nil {
-		err = fmt.Errorf("items with %s: %w", searcher, err)
-	}
-	return err
-}
-
-// TreeWalk implements btrfstree.Tree.  It only visits items and valid
-// leaf nodes (not the superblock, interior nodes, or bad nodes).
-func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
-	if cbs.Node == nil && cbs.Item == nil && cbs.BadItem == nil {
-		return
-	}
-	visitedNodes := make(containers.Set[btrfsvol.LogicalAddr])
-	var node *btrfstree.Node
-	tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
-		if ctx.Err() != nil {
-			return false
-		}
-
-		if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
-			tree.forrest.ReleaseNode(node)
-			node = tree.forrest.readNode(ctx, indexItem.Value.Node)
-			if cbs.Node != nil && !visitedNodes.Has(indexItem.Value.Node.LAddr) {
-				nodePath := btrfstree.Path{
-					btrfstree.PathRoot{
-						Forrest:      tree.forrest,
-						TreeID:       tree.ID,
-						ToAddr:       indexItem.Value.Node.LAddr,
-						ToGeneration: indexItem.Value.Node.Generation,
-						ToLevel:      indexItem.Value.Node.Level,
-					},
-				}
-				cbs.Node(nodePath, node)
-				if ctx.Err() != nil {
-					return false
-				}
-				visitedNodes.Insert(indexItem.Value.Node.LAddr)
-			}
-		}
-
-		if cbs.Item != nil || cbs.BadItem != nil {
-			item := node.BodyLeaf[indexItem.Value.Slot]
-			itemPath := btrfstree.Path{
-				btrfstree.PathRoot{
-					Forrest:      tree.forrest,
-					TreeID:       tree.ID,
-					ToAddr:       indexItem.Value.Node.LAddr,
-					ToGeneration: indexItem.Value.Node.Generation,
-					ToLevel:      indexItem.Value.Node.Level,
-				},
-				btrfstree.PathItem{
-					FromTree: indexItem.Value.Node.Owner,
-					FromSlot: indexItem.Value.Slot,
-					ToKey:    indexItem.Value.Key,
-				},
-			}
-			switch item.Body.(type) {
-			case *btrfsitem.Error:
-				if cbs.BadItem != nil {
-					cbs.BadItem(itemPath, item)
-				}
-			default:
-				if cbs.Item != nil {
-					cbs.Item(itemPath, item)
-				}
-			}
-			if ctx.Err() != nil {
-				return false
-			}
-		}
-
-		return true
-	})
-	tree.forrest.ReleaseNode(node)
-}
-
-// TreeParentID implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) {
-	if tree.ParentUUID == (btrfsprim.UUID{}) {
-		return 0, 0, nil
-	}
-	uuidTree := tree.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
-	if uuidTree.RootErr != nil {
-		return 0, 0, uuidTree.RootErr
-	}
-	parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID))
-	if err != nil {
-		return 0, 0, err
-	}
-	switch parentIDBody := parentIDItem.Body.(type) {
-	case *btrfsitem.UUIDMap:
-		return parentIDBody.ObjID, tree.ParentGen, nil
-	case *btrfsitem.Error:
-		return 0, 0, 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))
-	}
-}
-
-// btrfs.ReadableFS (other than btrfstree.Forrest) /////////////////////////////////////////////////////////////////////
-
-// Name implements btrfs.ReadableFS.
-func (bt *OldRebuiltForrest) Name() string {
-	return bt.inner.Name()
-}
-
-// Superblock implements btrfstree.NodeSource (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
-	return bt.inner.Superblock()
-}
-
-// AcquireNode implements btrfstree.NodeSource (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp btrfstree.NodeExpectations) (*btrfstree.Node, error) {
-	return bt.inner.AcquireNode(ctx, addr, exp)
-}
-
-// ReleaseNode implements btrfstree.NodeSource (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) ReleaseNode(node *btrfstree.Node) {
-	bt.inner.ReleaseNode(node)
-}
-
-// ReadAt implements diskio.ReaderAt[btrfsvol.LogicalAddr] (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
-	return bt.inner.ReadAt(p, off)
-}
diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go
index b5fbc91..8d96c41 100644
--- a/lib/btrfsutil/rebuilt_callbacks.go
+++ b/lib/btrfsutil/rebuilt_callbacks.go
@@ -57,11 +57,17 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) {
 	uuidTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.UUID_TREE_OBJECTID)
 	if err != nil {
+		if id, ok := cb.slowLookupUUID(ctx, uuid); ok {
+			return id, nil
+		}
 		return 0, err
 	}
 	tgt := btrfsitem.UUIDToKey(uuid)
 	item, err := uuidTree.TreeLookup(ctx, tgt)
 	if err != nil {
+		if id, ok := cb.slowLookupUUID(ctx, uuid); ok {
+			return id, nil
+		}
 		return 0, err
 	}
 	defer item.Body.Free()
@@ -69,10 +75,44 @@ func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfs
 	case *btrfsitem.UUIDMap:
 		return itemBody.ObjID, nil
 	case *btrfsitem.Error:
-		return 0, itemBody.Err
+		if id, ok := cb.slowLookupUUID(ctx, uuid); ok {
+			return id, nil
+		}
+		return 0, 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", itemBody))
 	}
 }
+
+func (cb noopRebuiltForrestCallbacks) slowLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+	rootTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+	if err != nil {
+		return 0, false
+	}
+	var ret btrfsprim.ObjID
+	_ = rootTree.TreeRange(ctx, func(item btrfstree.Item) bool {
+		if item.Key.ItemType != btrfsprim.ROOT_ITEM_KEY {
+			return true
+		}
+		switch itemBody := item.Body.(type) {
+		case *btrfsitem.Root:
+			if itemBody.UUID == uuid {
+				ret = item.Key.ObjectID
+				return false
+			}
+		case *btrfsitem.Error:
+			// do nothing
+		default:
+			// This is a panic because the item decoder should not emit ROOT_ITEM items as anything but
+			// btrfsitem.Root or btrfsitem.Error without this code also being updated.
+			panic(fmt.Errorf("should not happen: ROOT_ITEM item has unexpected type: %T", itemBody))
+		}
+		return true
+	})
+	if ret == 0 {
+		return 0, false
+	}
+	return ret, true
+}
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 79d8beb..4ce2435 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -23,29 +23,18 @@ import (
 // RebuiltForrest is an abstraction for rebuilding and accessing
 // potentially broken btrees.
 //
-// It is conceptually a btrfstree.Forrest, and adds similar
-// broken-tree handling to OldRebuiltForrest.  However, it is much
-// more efficient than OldRebuiltForrest.
+// Additionally, it provides some functionality on top of a vanilla
+// btrfs.ReadableFS:
 //
-// The efficiency improvements are possible because of the API
-// differences, which are necessary for how it is used in
-// rebuildtrees:
-//
-//   - it consumes an already-read Graph instead of reading the graph
-//     itself
-//
-//   - it does not use `btrfstree.Path`
-//
-//   - it does not keep track of errors encountered in a tree
-//
-// Additionally, it provides some functionality that OldRebuiltForrest
-// does not:
+//   - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a
+//     tree.
 //
 //   - it provides a RebuiltForrest.RebuiltListRoots() method for
 //     listing how trees have been repaired.
 //
-//   - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a
-//     tree.
+//   - it provides a RebuiltForrest.RebuiltAddRoots() method for
+//     batch-loading the results from
+//     RebuiltForrest.RebuiltListroots().
 //
 //   - it provides several RebuiltTree methods that provide advice on
 //     what roots should be added to a tree in order to repair it:
@@ -275,6 +264,48 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob
 	return ret
 }
 
+// RebuiltAddRoots takes a listing of the root nodes for trees (as
+// returned by RebuiltListRoots), and augments the trees to include
+// them.
+func (ts *RebuiltForrest) RebuiltAddRoots(ctx context.Context, roots map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) {
+	ctx = ts.treesMu.Lock(ctx)
+	defer ts.treesMu.Unlock()
+
+	essentialTrees := []btrfsprim.ObjID{
+		btrfsprim.ROOT_TREE_OBJECTID,
+		btrfsprim.UUID_TREE_OBJECTID,
+	}
+
+	for _, treeID := range essentialTrees {
+		treeRoots, ok := roots[treeID]
+		if !ok {
+			continue
+		}
+		tree, err := ts.RebuiltTree(ctx, treeID)
+		if err != nil {
+			dlog.Errorf(ctx, "RebuiltForrest.RebuiltAddRoots: cannot load essential tree %v: %v", treeID, err)
+			return
+		}
+		for _, root := range maps.SortedKeys(treeRoots) {
+			tree.RebuiltAddRoot(ctx, root)
+		}
+	}
+
+	for _, treeID := range maps.SortedKeys(roots) {
+		if slices.Contains(treeID, essentialTrees) {
+			continue
+		}
+		tree, err := ts.RebuiltTree(ctx, treeID)
+		if err != nil {
+			dlog.Errorf(ctx, "RebuiltForrest.RebuiltAddRoots: cannot load non-essential tree %v: %v", treeID, err)
+			continue
+		}
+		for _, root := range maps.SortedKeys(roots[treeID]) {
+			tree.RebuiltAddRoot(ctx, root)
+		}
+	}
+}
+
 // btrfs.ReadableFS interface //////////////////////////////////////////////////////////////////////////////////////////
 
 var _ btrfs.ReadableFS = (*RebuiltForrest)(nil)
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 97308a3..f002ea6 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -700,6 +700,10 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 	tree.mu.Lock()
 	defer tree.mu.Unlock()
 
+	if tree.Roots.Has(rootNode) {
+		return
+	}
+
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
 	dlog.Info(ctx, "adding root...")
 
diff --git a/scripts/main.sh b/scripts/main.sh
index c9c6f4e..082576a 100755
--- a/scripts/main.sh
+++ b/scripts/main.sh
@@ -78,20 +78,12 @@ run-btrfs-rec $gendir/3.trees.json \
 
 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 \
+    --trees=$gendir/3.trees.json \
     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 \
+    --trees=$gendir/3.trees.json \
     inspect ls-trees