Merge branch 'lukeshu/rebuild-nodes-take4'

16 files changed, 1248 insertions, 828 deletions

diff --git a/.golangci.yml b/.golangci.yml
index 6b9a830..355664f 100644
--- a/.golangci.yml
+++ b/.golangci.yml
@@ -51,7 +51,6 @@ linters:
     - revive
     - testpackage
     - thelper
-    - unparam
     - varnamelen
     - wrapcheck
 linters-settings:
diff --git a/cmd/btrfs-rec/inspect_rebuildnodes.go b/cmd/btrfs-rec/inspect_rebuildnodes.go
index e61e6d2..d813f36 100644
--- a/cmd/btrfs-rec/inspect_rebuildnodes.go
+++ b/cmd/btrfs-rec/inspect_rebuildnodes.go
@@ -5,7 +5,10 @@
 package main
 
 import (
+	"context"
 	"os"
+	"runtime"
+	"time"
 
 	"git.lukeshu.com/go/lowmemjson"
 	"github.com/datawire/dlib/dlog"
@@ -15,6 +18,7 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
 func init() {
@@ -26,28 +30,45 @@ func init() {
 		RunE: func(fs *btrfs.FS, cmd *cobra.Command, args []string) error {
 			ctx := cmd.Context()
 
-			dlog.Infof(ctx, "Reading %q...", args[0])
-			nodeScanResults, err := readJSONFile[btrfsinspect.ScanDevicesResult](ctx, args[0])
-			if err != nil {
-				return err
-			}
-			dlog.Infof(ctx, "... done reading %q", args[0])
+			// This is wrapped in a func in order to *ensure* that `nodeScanResults` goes out of scope once
+			// `rebuilder` has been created.
+			rebuilder, err := func(ctx context.Context) (rebuildnodes.Rebuilder, error) {
+				dlog.Infof(ctx, "Reading %q...", args[0])
+				nodeScanResults, err := readJSONFile[btrfsinspect.ScanDevicesResult](ctx, args[0])
+				if err != nil {
+					return nil, err
+				}
+				dlog.Infof(ctx, "... done reading %q", args[0])
 
-			rebuiltNodes, err := rebuildnodes.RebuildNodes(ctx, fs, nodeScanResults)
+				return rebuildnodes.NewRebuilder(ctx, fs, nodeScanResults)
+			}(ctx)
 			if err != nil {
 				return err
 			}
 
-			dlog.Info(ctx, "Writing re-built nodes to stdout...")
-			if err := writeJSONFile(os.Stdout, rebuiltNodes, lowmemjson.ReEncoder{
+			runtime.GC()
+			time.Sleep(textui.LiveMemUseUpdateInterval) // let the logs reflect that GC right away
+
+			dlog.Info(ctx, "Rebuilding node tree...")
+			rebuildErr := rebuilder.Rebuild(ctx)
+			dst := os.Stdout
+			if rebuildErr != nil {
+				dst = os.Stderr
+				dlog.Errorf(ctx, "rebuild error: %v", rebuildErr)
+			}
+			dlog.Infof(ctx, "Writing re-built nodes to %s...", dst.Name())
+			if err := writeJSONFile(dst, rebuilder.ListRoots(), lowmemjson.ReEncoder{
 				Indent:                "\t",
 				ForceTrailingNewlines: true,
 			}); err != nil {
+				if rebuildErr != nil {
+					return rebuildErr
+				}
 				return err
 			}
 			dlog.Info(ctx, "... done writing")
 
-			return nil
+			return rebuildErr
 		},
 	})
 }
diff --git a/cmd/btrfs-rec/util.go b/cmd/btrfs-rec/util.go
index ffc03cc..9a0d60c 100644
--- a/cmd/btrfs-rec/util.go
+++ b/cmd/btrfs-rec/util.go
@@ -18,6 +18,7 @@ import (
 )
 
 type runeScanner struct {
+	ctx            context.Context //nolint:containedctx // For detecting shutdown from methods
 	progress       textui.Portion[int64]
 	progressWriter *textui.Progress[textui.Portion[int64]]
 	unreadCnt      uint64
@@ -31,6 +32,7 @@ func newRuneScanner(ctx context.Context, fh *os.File) (*runeScanner, error) {
 		return nil, err
 	}
 	ret := &runeScanner{
+		ctx: ctx,
 		progress: textui.Portion[int64]{
 			D: fi.Size(),
 		},
@@ -42,6 +44,9 @@ func newRuneScanner(ctx context.Context, fh *os.File) (*runeScanner, error) {
 }
 
 func (rs *runeScanner) ReadRune() (r rune, size int, err error) {
+	if err := rs.ctx.Err(); err != nil {
+		return 0, 0, err
+	}
 	r, size, err = rs.reader.ReadRune()
 	if rs.unreadCnt > 0 {
 		rs.unreadCnt--
@@ -53,8 +58,14 @@ func (rs *runeScanner) ReadRune() (r rune, size int, err error) {
 }
 
 func (rs *runeScanner) UnreadRune() error {
+	if err := rs.ctx.Err(); err != nil {
+		return err
+	}
+	if err := rs.reader.UnreadRune(); err != nil {
+		return err
+	}
 	rs.unreadCnt++
-	return rs.reader.UnreadRune()
+	return nil
 }
 
 func (rs *runeScanner) Close() error {
@@ -69,6 +80,9 @@ func readJSONFile[T any](ctx context.Context, filename string) (T, error) {
 		return zero, err
 	}
 	buf, err := newRuneScanner(dlog.WithField(ctx, "btrfs.read-json-file", filename), fh)
+	defer func() {
+		_ = buf.Close()
+	}()
 	if err != nil {
 		var zero T
 		return zero, err
@@ -78,7 +92,6 @@ func readJSONFile[T any](ctx context.Context, filename string) (T, error) {
 		var zero T
 		return zero, err
 	}
-	_ = buf.Close()
 	return ret, nil
 }
 
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
new file mode 100644
index 0000000..ff6b1c5
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
@@ -0,0 +1,193 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrees
+
+import (
+	"context"
+
+	"github.com/datawire/dlib/dlog"
+
+	"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"
+	pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+// RebuiltForrest is an abstraction for rebuilding and accessing
+// potentially broken btrees.
+//
+// It is conceptually a btrfstree.TreeOperator, and adds similar
+// broken-tree handling to btrfsutil.BrokenForrest.  However, the API
+// is different thant btrfstree.TreeOperator, and is much more
+// efficient than btrfsutil.BrokenForrest.
+//
+// The efficiency improvements are possible because of the API
+// differences, which are necessary for how it is used in
+// rebuildnodes:
+//
+//   - it consumes an already-read graph.Graph instead of reading the
+//     graph itself
+//
+//   - it does not use `btrfstree.TreePath`
+//
+//   - it does not keep track of errors encountered in a tree
+//
+// Additionally, it provides some functionality that
+// btrfsutil.BrokenForrest does not:
+//
+//   - it provides a .LeafToRoots() method to advise on what
+//     additional roots should be added
+//
+//   - it provides a .COWDistance() method to compare how related two
+//     trees are
+//
+// A zero RebuiltForrest is invalid; it must be initialized with
+// NewRebuiltForrest().
+type RebuiltForrest struct {
+	// static
+	sb    btrfstree.Superblock
+	graph pkggraph.Graph
+	keyIO *keyio.Handle
+
+	// static callbacks
+	cbAddedItem  func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
+	cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
+	cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
+
+	// mutable
+	trees    containers.SyncMap[btrfsprim.ObjID, *RebuiltTree]
+	leafs    *containers.LRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
+	incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex]
+	excItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex]
+}
+
+// NewRebuiltForrest returns a new RebuiltForrest instance.  All of
+// the callbacks must be non-nil.
+func NewRebuiltForrest(
+	sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle,
+	cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key),
+	cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool),
+	cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool),
+) *RebuiltForrest {
+	return &RebuiltForrest{
+		sb:    sb,
+		graph: graph,
+		keyIO: keyIO,
+
+		cbAddedItem:  cbAddedItem,
+		cbLookupRoot: cbLookupRoot,
+		cbLookupUUID: cbLookupUUID,
+
+		leafs:    containers.NewLRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](textui.Tunable(8)),
+		incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)),
+		excItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)),
+	}
+}
+
+// Tree 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.
+func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
+	if !ts.addTree(ctx, treeID, nil) {
+		return nil
+	}
+	tree, _ := ts.trees.Load(treeID)
+	return tree
+}
+
+func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
+	if tree, ok := ts.trees.Load(treeID); ok {
+		return tree != nil
+	}
+	defer func() {
+		if !ok {
+			// Store a negative cache of this.  tree.AddRoot() for the ROOT or UUID
+			// trees will invalidate the negative cache.
+			ts.trees.Store(treeID, nil)
+		}
+	}()
+	stack = append(stack, treeID)
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.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
+	}
+
+	tree := &RebuiltTree{
+		ID:      treeID,
+		Roots:   make(containers.Set[btrfsvol.LogicalAddr]),
+		forrest: ts,
+	}
+	var root btrfsvol.LogicalAddr
+	switch treeID {
+	case btrfsprim.ROOT_TREE_OBJECTID:
+		root = ts.sb.RootTree
+	case btrfsprim.CHUNK_TREE_OBJECTID:
+		root = ts.sb.ChunkTree
+	case btrfsprim.TREE_LOG_OBJECTID:
+		root = ts.sb.LogTree
+	case btrfsprim.BLOCK_GROUP_TREE_OBJECTID:
+		root = ts.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.cbLookupRoot(ctx, treeID)
+		if !ok {
+			dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM")
+			return false
+		}
+		root = rootItem.ByteNr
+		tree.UUID = rootItem.UUID
+		if rootItem.ParentUUID != (btrfsprim.UUID{}) {
+			tree.ParentGen = rootOff
+			if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
+				return false
+			}
+			parentID, ok := ts.cbLookupUUID(ctx, rootItem.ParentUUID)
+			if !ok {
+				dlog.Error(ctx, "failed to add tree: lookup UUID")
+				return false
+			}
+			if !ts.addTree(ctx, parentID, stack) {
+				dlog.Error(ctx, "failed to add tree: add parent tree")
+				return false
+			}
+			tree.Parent, _ = ts.trees.Load(parentID)
+		}
+	}
+
+	ts.trees.Store(treeID, tree)
+	if root != 0 {
+		tree.AddRoot(ctx, root)
+	}
+
+	return true
+}
+
+// ListRoots returns a listing of all initialized trees and their root
+// nodes.
+//
+// Do not mutate the set of roots for a tree; it is a pointer to the
+// RebuiltForrest's internal set!
+func (ts *RebuiltForrest) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
+	ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
+	ts.trees.Range(func(treeID btrfsprim.ObjID, tree *RebuiltTree) bool {
+		if tree != nil {
+			ret[treeID] = tree.Roots
+		}
+		return true
+	})
+	return ret
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
deleted file mode 100644
index b53a28e..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.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 btrees
-
-import (
-	"context"
-	"fmt"
-	"time"
-
-	"github.com/datawire/dlib/dlog"
-
-	"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"
-	pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
-	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
-	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
-	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type rebuiltTree struct {
-	// static
-	ID        btrfsprim.ObjID
-	UUID      btrfsprim.UUID
-	Parent    *rebuiltTree
-	ParentGen btrfsprim.Generation // offset of this tree's root item
-
-	// all leafs (lvl=0) that pass .isOwnerOK, even if not in the tree
-	leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]
-	keys        containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
-
-	// mutable
-	Roots containers.Set[btrfsvol.LogicalAddr]
-	Leafs containers.Set[btrfsvol.LogicalAddr]
-	Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
-}
-
-// isOwnerOK returns whether it is permissible for a node with
-// .Head.Owner=owner to be in this tree.
-func (tree *rebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool {
-	for {
-		if owner == tree.ID {
-			return true
-		}
-		if tree.Parent == nil || gen >= tree.ParentGen {
-			return false
-		}
-		tree = tree.Parent
-	}
-}
-
-// cowDistance returns how many COW-snapshots down the 'tree' is from
-// the 'parent'.
-func (tree *rebuiltTree) cowDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
-	for {
-		if parentID == tree.ID {
-			return dist, true
-		}
-		if tree.Parent == nil {
-			return 0, false
-		}
-		tree = tree.Parent
-		dist++
-	}
-}
-
-func (tree *rebuiltTree) shouldReplace(graph pkggraph.Graph, oldNode, newNode btrfsvol.LogicalAddr) bool {
-	oldDist, _ := tree.cowDistance(graph.Nodes[oldNode].Owner)
-	newDist, _ := tree.cowDistance(graph.Nodes[newNode].Owner)
-	switch {
-	case newDist < oldDist:
-		// Replace the old one with the new lower-dist one.
-		return true
-	case newDist > oldDist:
-		// Retain the old lower-dist one.
-		return false
-	default:
-		oldGen := graph.Nodes[oldNode].Generation
-		newGen := graph.Nodes[newNode].Generation
-		switch {
-		case newGen > oldGen:
-			// Replace the old one with the new higher-gen one.
-			return true
-		case newGen < oldGen:
-			// Retain the old higher-gen one.
-			return false
-		default:
-			// 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 nodes in tree=%v: old=%v=%v ; new=%v=%v",
-				tree.ID,
-				oldNode, graph.Nodes[oldNode],
-				newNode, graph.Nodes[newNode]))
-		}
-	}
-}
-
-// RebuiltTrees is an abstraction for rebuilding and accessing
-// potentially broken btrees.
-//
-// It is conceptually a btrfstree.TreeOperator, and adds similar
-// broken-tree handling to btrfsutil.BrokenTrees.  However, the API is
-// different thant btrfstree.TreeOperator, and is much more efficient
-// than btrfsutil.BrokenTrees.
-//
-// The efficiency improvements are possible because of the API
-// differences, which are necessary for how it is used in
-// rebuildnodes:
-//
-//   - it consumes an already-read graph.Graph instead of reading the
-//     graph itself
-//
-//   - it does not use `btrfstree.TreePath`
-//
-//   - it does not keep track of errors encountered in a tree
-//
-// Additionally, it provides some functionality that
-// btrfsutil.BrokenTrees does not:
-//
-//   - it provides a .LeafToRoots() method to advise on what
-//     additional roots should be added
-//
-//   - it provides a .COWDistance() method to compare how related two
-//     trees are
-//
-// A zero RebuiltTrees is invalid; it must be initialized with
-// NewRebuiltTrees().
-type RebuiltTrees struct {
-	// static
-	sb    btrfstree.Superblock
-	graph pkggraph.Graph
-	keyIO *keyio.Handle
-
-	// static callbacks
-	cbAddedItem  func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
-	cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
-	cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
-
-	// mutable
-	trees map[btrfsprim.ObjID]*rebuiltTree
-}
-
-// NewRebuiltTrees returns a new RebuiltTrees instance.  All of the
-// callbacks must be non-nil.
-func NewRebuiltTrees(
-	sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle,
-	cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key),
-	cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool),
-	cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool),
-) *RebuiltTrees {
-	return &RebuiltTrees{
-		sb:    sb,
-		graph: graph,
-		keyIO: keyIO,
-
-		cbAddedItem:  cbAddedItem,
-		cbLookupRoot: cbLookupRoot,
-		cbLookupUUID: cbLookupUUID,
-
-		trees: make(map[btrfsprim.ObjID]*rebuiltTree),
-	}
-}
-
-type rootStats struct {
-	Leafs         textui.Portion[int]
-	AddedItems    int
-	ReplacedItems int
-}
-
-func (s rootStats) String() string {
-	return textui.Sprintf("%v (added %v items, replaced %v items)",
-		s.Leafs, s.AddedItems, s.ReplacedItems)
-}
-
-// AddRoot adds an additional root node to an existing tree.  It is
-// useful to call .AddRoot() to re-attach part of the tree that has
-// been broken off.
-//
-// It is invalid (panic) to call AddRoot for a tree without having
-// called AddTree first.
-func (ts *RebuiltTrees) AddRoot(ctx context.Context, treeID btrfsprim.ObjID, rootNode btrfsvol.LogicalAddr) {
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", treeID, rootNode))
-	tree := ts.trees[treeID]
-	tree.Roots.Insert(rootNode)
-
-	var stats rootStats
-	stats.Leafs.D = len(tree.leafToRoots)
-	progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-	for i, leaf := range maps.SortedKeys(tree.leafToRoots) {
-		stats.Leafs.N = i
-		progressWriter.Set(stats)
-		if tree.Leafs.Has(leaf) || !tree.leafToRoots[leaf].Has(rootNode) {
-			continue
-		}
-		tree.Leafs.Insert(leaf)
-		for j, itemKey := range ts.graph.Nodes[leaf].Items {
-			newPtr := keyio.ItemPtr{
-				Node: leaf,
-				Idx:  j,
-			}
-			if oldPtr, exists := tree.Items.Load(itemKey); !exists {
-				tree.Items.Store(itemKey, newPtr)
-				stats.AddedItems++
-			} else if tree.shouldReplace(ts.graph, oldPtr.Node, newPtr.Node) {
-				tree.Items.Store(itemKey, newPtr)
-				stats.ReplacedItems++
-			}
-			ts.cbAddedItem(ctx, treeID, itemKey)
-			progressWriter.Set(stats)
-		}
-	}
-	stats.Leafs.N = len(tree.leafToRoots)
-	progressWriter.Set(stats)
-	progressWriter.Done()
-}
-
-// AddTree initializes the given tree, returning true if it was able
-// to do so, or false if there was a problem and nothing was done.
-// The tree is initialized with the normal root node of the tree.
-//
-// Subsequent calls to AddTree for the same tree are no-ops.
-func (ts *RebuiltTrees) AddTree(ctx context.Context, treeID btrfsprim.ObjID) (ok bool) {
-	return ts.addTree(ctx, treeID, nil)
-}
-
-func (ts *RebuiltTrees) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
-	if _, ok := ts.trees[treeID]; ok {
-		return true
-	}
-	if slices.Contains(treeID, stack) {
-		return false
-	}
-	stack = append(stack, treeID)
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack)
-	dlog.Info(ctx, "adding tree...")
-
-	tree := &rebuiltTree{
-		ID:    treeID,
-		Roots: make(containers.Set[btrfsvol.LogicalAddr]),
-		Leafs: make(containers.Set[btrfsvol.LogicalAddr]),
-	}
-	var root btrfsvol.LogicalAddr
-	switch treeID {
-	case btrfsprim.ROOT_TREE_OBJECTID:
-		root = ts.sb.RootTree
-	case btrfsprim.CHUNK_TREE_OBJECTID:
-		root = ts.sb.ChunkTree
-	case btrfsprim.TREE_LOG_OBJECTID:
-		root = ts.sb.LogTree
-	case btrfsprim.BLOCK_GROUP_TREE_OBJECTID:
-		root = ts.sb.BlockGroupRoot
-	default:
-		if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) {
-			return false
-		}
-		rootOff, rootItem, ok := ts.cbLookupRoot(ctx, treeID)
-		if !ok {
-			return false
-		}
-		root = rootItem.ByteNr
-		tree.UUID = rootItem.UUID
-		if rootItem.ParentUUID != (btrfsprim.UUID{}) {
-			tree.ParentGen = rootOff
-			if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
-				return false
-			}
-			parentID, ok := ts.cbLookupUUID(ctx, rootItem.ParentUUID)
-			if !ok {
-				return false
-			}
-			if !ts.addTree(ctx, parentID, append(stack, treeID)) {
-				return false
-			}
-			tree.Parent = ts.trees[parentID]
-		}
-	}
-	tree.indexLeafs(ctx, ts.graph)
-
-	ts.trees[treeID] = tree
-	if root != 0 {
-		ts.AddRoot(ctx, treeID, root)
-	}
-
-	return true
-}
-
-func (tree *rebuiltTree) indexLeafs(ctx context.Context, graph pkggraph.Graph) {
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep", "index-nodes")
-
-	nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
-
-	var stats textui.Portion[int]
-	stats.D = len(graph.Nodes)
-	progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-	progress := func() {
-		stats.N = len(nodeToRoots)
-		progressWriter.Set(stats)
-	}
-
-	progress()
-	for _, node := range maps.SortedKeys(graph.Nodes) {
-		tree.indexNode(graph, node, nodeToRoots, progress, nil)
-	}
-	progressWriter.Done()
-
-	tree.leafToRoots = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
-	for node, roots := range nodeToRoots {
-		if graph.Nodes[node].Level == 0 && len(roots) > 0 {
-			tree.leafToRoots[node] = roots
-		}
-	}
-}
-
-func (tree *rebuiltTree) indexNode(graph pkggraph.Graph, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) {
-	defer progress()
-	if _, done := index[node]; done {
-		return
-	}
-	if slices.Contains(node, stack) {
-		// This is a panic because graph.FinalCheck() should
-		// have already checked for loops.
-		panic("loop")
-	}
-	if !tree.isOwnerOK(graph.Nodes[node].Owner, graph.Nodes[node].Generation) {
-		index[node] = nil
-		return
-	}
-
-	// tree.leafToRoots
-	stack = append(stack, node)
-	var roots containers.Set[btrfsvol.LogicalAddr]
-	kps := slices.RemoveAllFunc(graph.EdgesTo[node], func(kp *pkggraph.Edge) bool {
-		return !tree.isOwnerOK(graph.Nodes[kp.FromNode].Owner, graph.Nodes[kp.FromNode].Generation)
-	})
-	for _, kp := range kps {
-		tree.indexNode(graph, kp.FromNode, index, progress, stack)
-		if len(index[kp.FromNode]) > 0 {
-			if roots == nil {
-				roots = make(containers.Set[btrfsvol.LogicalAddr])
-			}
-			roots.InsertFrom(index[kp.FromNode])
-		}
-	}
-	if roots == nil {
-		roots = containers.NewSet[btrfsvol.LogicalAddr](node)
-	}
-	index[node] = roots
-
-	// tree.keys
-	for i, key := range graph.Nodes[node].Items {
-		if oldPtr, ok := tree.keys.Load(key); !ok || tree.shouldReplace(graph, oldPtr.Node, node) {
-			tree.keys.Store(key, keyio.ItemPtr{
-				Node: node,
-				Idx:  i,
-			})
-		}
-	}
-}
-
-// Load reads an item from a tree.
-//
-// It is not nescessary to call AddTree for that tree first; Load will
-// call it for you.
-func (ts *RebuiltTrees) Load(ctx context.Context, treeID btrfsprim.ObjID, key btrfsprim.Key) (item btrfsitem.Item, ok bool) {
-	if !ts.AddTree(ctx, treeID) {
-		return nil, false
-	}
-	ptr, ok := ts.trees[treeID].Items.Load(key)
-	if !ok {
-		return nil, false
-	}
-	return ts.keyIO.ReadItem(ctx, ptr)
-}
-
-// Search searches for an item from a tree.
-//
-// It is not nescessary to call AddTree for that tree first; Search
-// will call it for you.
-func (ts *RebuiltTrees) Search(ctx context.Context, treeID btrfsprim.ObjID, fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) {
-	if !ts.AddTree(ctx, treeID) {
-		return btrfsprim.Key{}, false
-	}
-	k, _, ok := ts.trees[treeID].Items.Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int {
-		return fn(k)
-	})
-	return k, ok
-}
-
-// Search searches for a range of items from a tree.
-//
-// It is not nescessary to call AddTree for that tree first; SearchAll
-// will call it for you.
-func (ts *RebuiltTrees) SearchAll(ctx context.Context, treeID btrfsprim.ObjID, fn func(btrfsprim.Key) int) []btrfsprim.Key {
-	if !ts.AddTree(ctx, treeID) {
-		return nil
-	}
-	kvs := ts.trees[treeID].Items.SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int {
-		return fn(k)
-	})
-	if len(kvs) == 0 {
-		return nil
-	}
-	ret := make([]btrfsprim.Key, len(kvs))
-	for i := range kvs {
-		ret[i] = kvs[i].K
-	}
-	return ret
-}
-
-// LeafToRoots returns the list of potential roots (to pass to
-// .AddRoot) that include a given leaf-node.
-//
-// It is not nescessary to call AddTree for the tree first;
-// LeafToRoots will call it for you.
-func (ts *RebuiltTrees) LeafToRoots(ctx context.Context, treeID btrfsprim.ObjID, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
-	if !ts.AddTree(ctx, treeID) {
-		return nil
-	}
-	if ts.graph.Nodes[leaf].Level != 0 {
-		panic(fmt.Errorf("should not happen: NodeToRoots(tree=%v, leaf=%v): not a leaf",
-			treeID, leaf))
-	}
-	ret := make(containers.Set[btrfsvol.LogicalAddr])
-	for root := range ts.trees[treeID].leafToRoots[leaf] {
-		if ts.trees[treeID].Roots.Has(root) {
-			panic(fmt.Errorf("should not happen: NodeToRoots(tree=%v, leaf=%v): tree contains root=%v but not leaf",
-				treeID, leaf, root))
-		}
-		ret.Insert(root)
-	}
-	if len(ret) == 0 {
-		return nil
-	}
-	return ret
-}
-
-// Keys returns a map of all keys in node that would be valid in this tree.
-//
-// It is invalid (panic) to call Keys for a tree without having called
-// AddTree first.
-func (ts *RebuiltTrees) Keys(treeID btrfsprim.ObjID) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
-	return &ts.trees[treeID].keys
-}
-
-// COWDistance returns how many COW-snapshots down from the 'child'
-// tree is from the 'parent' tree.
-//
-// It is invalid (panic) to call COWDistance for a tree without having
-// called AddTree for the child first.
-func (ts *RebuiltTrees) COWDistance(ctx context.Context, childID, parentID btrfsprim.ObjID) (dist int, ok bool) {
-	return ts.trees[childID].cowDistance(parentID)
-}
-
-// ListRoots returns a listing of all initialized trees and their root
-// nodes.
-//
-// Do not mutate the set of roots for a tree; it is a pointer to the
-// RebuiltTrees' internal set!
-func (ts *RebuiltTrees) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
-	ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(ts.trees))
-	for treeID := range ts.trees {
-		ret[treeID] = ts.trees[treeID].Roots
-	}
-	return ret
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
new file mode 100644
index 0000000..c381274
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
@@ -0,0 +1,361 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrees
+
+import (
+	"context"
+	"fmt"
+	"sync"
+	"time"
+
+	"github.com/datawire/dlib/dlog"
+
+	"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"
+	pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+type RebuiltTree struct {
+	// static
+	ID        btrfsprim.ObjID
+	UUID      btrfsprim.UUID
+	Parent    *RebuiltTree
+	ParentGen btrfsprim.Generation // offset of this tree's root item
+	forrest   *RebuiltForrest
+
+	// mutable
+	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 LRUcache.  They are all
+	// derived from tree.Roots, which is why it's OK if they get
+	// evicted.
+	//
+	//  1. tree.leafToRoots()    = tree.forrest.leafs.Load(tree.ID)
+	//  2. tree.Items()          = tree.forrest.incItems.Load(tree.ID)
+	//  3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID)
+}
+
+// LRU member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////
+
+// leafToRoots returns all leafs (lvl=0) in the filesystem that pass
+// .isOwnerOK, whether or not they're in the tree.
+func (tree *RebuiltTree) leafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
+	return tree.forrest.leafs.GetOrElse(tree.ID, func() map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
+		ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-nodes", fmt.Sprintf("tree=%v", tree.ID))
+
+		nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
+
+		var stats textui.Portion[int]
+		stats.D = len(tree.forrest.graph.Nodes)
+		progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+		progress := func() {
+			stats.N = len(nodeToRoots)
+			progressWriter.Set(stats)
+		}
+
+		progress()
+		for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) {
+			tree.indexNode(ctx, node, nodeToRoots, progress, nil)
+		}
+		progressWriter.Done()
+
+		ret := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
+		for node, roots := range nodeToRoots {
+			if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 {
+				ret[node] = roots
+			}
+		}
+		return ret
+	})
+}
+
+func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) {
+	defer progress()
+	if err := ctx.Err(); err != nil {
+		return
+	}
+	if _, done := index[node]; done {
+		return
+	}
+	if slices.Contains(node, stack) {
+		// This is a panic because tree.forrest.graph.FinalCheck() should
+		// have already checked for loops.
+		panic("loop")
+	}
+	if !tree.isOwnerOK(tree.forrest.graph.Nodes[node].Owner, tree.forrest.graph.Nodes[node].Generation) {
+		index[node] = nil
+		return
+	}
+
+	// tree.leafToRoots
+	stack = append(stack, node)
+	var roots containers.Set[btrfsvol.LogicalAddr]
+	kps := slices.RemoveAllFunc(tree.forrest.graph.EdgesTo[node], func(kp *pkggraph.Edge) bool {
+		return !tree.isOwnerOK(tree.forrest.graph.Nodes[kp.FromNode].Owner, tree.forrest.graph.Nodes[kp.FromNode].Generation)
+	})
+	for _, kp := range kps {
+		tree.indexNode(ctx, kp.FromNode, index, progress, stack)
+		if len(index[kp.FromNode]) > 0 {
+			if roots == nil {
+				roots = make(containers.Set[btrfsvol.LogicalAddr])
+			}
+			roots.InsertFrom(index[kp.FromNode])
+		}
+	}
+	if roots == nil {
+		roots = containers.NewSet[btrfsvol.LogicalAddr](node)
+	}
+	index[node] = roots
+}
+
+// isOwnerOK returns whether it is permissible for a node with
+// .Head.Owner=owner to be in this tree.
+func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool {
+	for {
+		if owner == tree.ID {
+			return true
+		}
+		if tree.Parent == nil || gen >= tree.ParentGen {
+			return false
+		}
+		tree = tree.Parent
+	}
+}
+
+// LRU members 2 and 3: .Items() and .PotentialItems() /////////////////////////////////////////////////////////////////
+
+// Items returns a map of the items contained in this tree.
+//
+// Do not mutate the returned map; it is a pointer to the
+// RebuiltTree's internal map!
+func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-inc-items", fmt.Sprintf("tree=%v", tree.ID))
+	return tree.items(ctx, tree.forrest.incItems, tree.Roots.HasAny)
+}
+
+// PotentialItems returns a map of items that could be added to this
+// tree with .AddRoot().
+//
+// Do not mutate the returned map; it is a pointer to the
+// RebuiltTree's internal map!
+func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-all-items", fmt.Sprintf("tree=%v", tree.ID))
+	return tree.items(ctx, tree.forrest.excItems,
+		func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
+			return !tree.Roots.HasAny(roots)
+		})
+}
+
+type itemIndex = containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
+
+type itemStats struct {
+	Leafs    textui.Portion[int]
+	NumItems int
+	NumDups  int
+}
+
+func (s itemStats) String() string {
+	return textui.Sprintf("%v (%v items, %v dups)",
+		s.Leafs, s.NumItems, s.NumDups)
+}
+
+func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex],
+	leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool,
+) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+
+	return cache.GetOrElse(tree.ID, func() *itemIndex {
+		var leafs []btrfsvol.LogicalAddr
+		for leaf, roots := range tree.leafToRoots(ctx) {
+			if leafFn(roots) {
+				leafs = append(leafs, leaf)
+			}
+		}
+		slices.Sort(leafs)
+
+		var stats itemStats
+		stats.Leafs.D = len(leafs)
+		progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+
+		index := new(containers.SortedMap[btrfsprim.Key, keyio.ItemPtr])
+		for i, leaf := range leafs {
+			stats.Leafs.N = i
+			progressWriter.Set(stats)
+			for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
+				newPtr := keyio.ItemPtr{
+					Node: leaf,
+					Idx:  j,
+				}
+				if oldPtr, exists := index.Load(itemKey); !exists {
+					index.Store(itemKey, newPtr)
+					stats.NumItems++
+				} else {
+					if tree.shouldReplace(oldPtr.Node, newPtr.Node) {
+						index.Store(itemKey, newPtr)
+					}
+					stats.NumDups++
+				}
+				progressWriter.Set(stats)
+			}
+		}
+		if stats.Leafs.N > 0 {
+			stats.Leafs.N = len(leafs)
+			progressWriter.Set(stats)
+			progressWriter.Done()
+		}
+
+		return index
+	})
+}
+
+func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
+	oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
+	newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner)
+	switch {
+	case newDist < oldDist:
+		// Replace the old one with the new lower-dist one.
+		return true
+	case newDist > oldDist:
+		// Retain the old lower-dist one.
+		return false
+	default:
+		oldGen := tree.forrest.graph.Nodes[oldNode].Generation
+		newGen := tree.forrest.graph.Nodes[newNode].Generation
+		switch {
+		case newGen > oldGen:
+			// Replace the old one with the new higher-gen one.
+			return true
+		case newGen < oldGen:
+			// Retain the old higher-gen one.
+			return false
+		default:
+			// TODO: 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 nodes in tree=%v: old=%v=%v ; new=%v=%v",
+				tree.ID,
+				oldNode, tree.forrest.graph.Nodes[oldNode],
+				newNode, tree.forrest.graph.Nodes[newNode]))
+		}
+	}
+}
+
+// .AddRoot() //////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+type rootStats struct {
+	Leafs      textui.Portion[int]
+	AddedLeafs int
+	AddedItems int
+}
+
+func (s rootStats) String() string {
+	return textui.Sprintf("%v (added %v leafs, added %v items)",
+		s.Leafs, s.AddedLeafs, s.AddedItems)
+}
+
+// AddRoot adds an additional root node to the tree.  It is useful to
+// call .AddRoot() to re-attach part of the tree that has been broken
+// off.
+func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
+	tree.mu.Lock()
+	defer tree.mu.Unlock()
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
+
+	leafToRoots := tree.leafToRoots(ctx)
+
+	var stats rootStats
+	stats.Leafs.D = len(leafToRoots)
+	progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	for i, leaf := range maps.SortedKeys(leafToRoots) {
+		stats.Leafs.N = i
+		progressWriter.Set(stats)
+
+		if tree.Roots.HasAny(leafToRoots[leaf]) || !leafToRoots[leaf].Has(rootNode) {
+			continue
+		}
+
+		stats.AddedLeafs++
+		progressWriter.Set(stats)
+
+		for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
+			tree.forrest.cbAddedItem(ctx, tree.ID, itemKey)
+			stats.AddedItems++
+			progressWriter.Set(stats)
+		}
+	}
+	stats.Leafs.N = len(leafToRoots)
+	progressWriter.Set(stats)
+	progressWriter.Done()
+
+	tree.Roots.Insert(rootNode)
+	tree.forrest.incItems.Remove(tree.ID) // force re-gen
+	tree.forrest.excItems.Remove(tree.ID) // force re-gen
+
+	if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 {
+		tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool {
+			if otherTree == nil {
+				tree.forrest.trees.Delete(otherTreeID)
+			}
+			return true
+		})
+	}
+}
+
+// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
+
+// COWDistance returns how many COW-snapshots down the 'tree' is from
+// the 'parent'.
+func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
+	for {
+		if parentID == tree.ID {
+			return dist, true
+		}
+		if tree.Parent == nil {
+			return 0, false
+		}
+		tree = tree.Parent
+		dist++
+	}
+}
+
+// ReadItem reads an item from a tree.
+func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) (item btrfsitem.Item, ok bool) {
+	ptr, ok := tree.Items(ctx).Load(key)
+	if !ok {
+		return nil, false
+	}
+	return tree.forrest.keyIO.ReadItem(ctx, ptr)
+}
+
+// LeafToRoots returns the list of potential roots (to pass to
+// .AddRoot) that include a given leaf-node.
+func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
+	if tree.forrest.graph.Nodes[leaf].Level != 0 {
+		panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf",
+			tree.ID, leaf))
+	}
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+	ret := make(containers.Set[btrfsvol.LogicalAddr])
+	for root := range tree.leafToRoots(ctx)[leaf] {
+		if tree.Roots.Has(root) {
+			panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf",
+				tree.ID, leaf, root))
+		}
+		ret.Insert(root)
+	}
+	if len(ret) == 0 {
+		return nil
+	}
+	return ret
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
index 24c3dcf..64a9828 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
@@ -34,12 +34,19 @@ type SizeAndErr struct {
 	Err  error
 }
 
+type FlagsAndErr struct {
+	NoDataSum bool
+	Err       error
+}
+
 type Handle struct {
 	rawFile diskio.File[btrfsvol.LogicalAddr]
 	sb      btrfstree.Superblock
 	graph   graph.Graph
 
-	Sizes map[ItemPtr]SizeAndErr
+	Flags map[ItemPtr]FlagsAndErr // INODE_ITEM
+	Names map[ItemPtr][]byte      // DIR_INDEX
+	Sizes map[ItemPtr]SizeAndErr  // EXTENT_CSUM and EXTENT_DATA
 
 	cache *containers.LRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
 }
@@ -49,6 +56,8 @@ func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock)
 		rawFile: file,
 		sb:      sb,
 
+		Flags: make(map[ItemPtr]FlagsAndErr),
+		Names: make(map[ItemPtr][]byte),
 		Sizes: make(map[ItemPtr]SizeAndErr),
 
 		cache: containers.NewLRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]](textui.Tunable(8)),
@@ -62,6 +71,15 @@ func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.
 			Idx:  i,
 		}
 		switch itemBody := item.Body.(type) {
+		case btrfsitem.Inode:
+			o.Flags[ptr] = FlagsAndErr{
+				NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM),
+				Err:       nil,
+			}
+		case btrfsitem.DirEntry:
+			if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY {
+				o.Names[ptr] = append([]byte(nil), itemBody.Name...)
+			}
 		case btrfsitem.ExtentCSum:
 			o.Sizes[ptr] = SizeAndErr{
 				Size: uint64(itemBody.Size()),
@@ -75,6 +93,11 @@ func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.
 			}
 		case btrfsitem.Error:
 			switch item.Key.ItemType {
+			case btrfsprim.INODE_ITEM_KEY:
+				o.Flags[ptr] = FlagsAndErr{
+					Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
+						ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
+				}
 			case btrfsprim.EXTENT_CSUM_KEY, btrfsprim.EXTENT_DATA_KEY:
 				o.Sizes[ptr] = SizeAndErr{
 					Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
index 7e55732..ebca2bd 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
@@ -5,16 +5,21 @@
 package rebuildnodes
 
 import (
+	"bytes"
 	"context"
 	"fmt"
+	"runtime"
 	"sort"
+	"strings"
 	"time"
 
+	"github.com/datawire/dlib/dgroup"
 	"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/btrfssum"
 	"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/btrfsprogs/btrfsinspect"
@@ -32,10 +37,10 @@ type keyAndTree struct {
 }
 
 func (a keyAndTree) Cmp(b keyAndTree) int {
-	if d := a.Key.Cmp(b.Key); d != 0 {
+	if d := containers.NativeCmp(a.TreeID, b.TreeID); d != 0 {
 		return d
 	}
-	return containers.NativeCmp(a.TreeID, b.TreeID)
+	return a.Key.Cmp(b.Key)
 }
 
 func (o keyAndTree) String() string {
@@ -43,47 +48,47 @@ func (o keyAndTree) String() string {
 }
 
 type rebuilder struct {
-	sb      btrfstree.Superblock
-	rebuilt *btrees.RebuiltTrees
-
+	sb    btrfstree.Superblock
 	graph graph.Graph
 	keyIO *keyio.Handle
 
-	curKey       keyAndTree
-	treeQueue    []btrfsprim.ObjID
-	itemQueue    []keyAndTree
-	augmentQueue map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int
+	rebuilt *btrees.RebuiltForrest
+
+	curKey             keyAndTree
+	treeQueue          containers.Set[btrfsprim.ObjID]
+	itemQueue          containers.Set[keyAndTree]
+	augmentQueue       map[btrfsprim.ObjID]*treeAugmentQueue
+	numAugments        int
+	numAugmentFailures int
 }
 
-func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], error) {
-	_ctx := ctx
+type treeAugmentQueue struct {
+	keyBuf strings.Builder
+	zero   map[string]struct{}
+	single map[string]btrfsvol.LogicalAddr
+	multi  map[string]containers.Set[btrfsvol.LogicalAddr]
+}
 
-	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "read-fs-data")
-	dlog.Info(ctx, "Reading superblock...")
-	sb, err := fs.Superblock()
-	if err != nil {
-		return nil, err
-	}
-	nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging
+type Rebuilder interface {
+	Rebuild(context.Context) error
+	ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]
+}
+
+func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (Rebuilder, error) {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.step", "read-fs-data")
+	sb, nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging
 	if err != nil {
 		return nil, err
 	}
 
-	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "rebuild")
-	dlog.Info(ctx, "Rebuilding node tree...")
 	o := &rebuilder{
-		sb: *sb,
-
+		sb:    sb,
 		graph: nodeGraph,
 		keyIO: keyIO,
 	}
-	o.rebuilt = btrees.NewRebuiltTrees(*sb, nodeGraph, keyIO,
+	o.rebuilt = btrees.NewRebuiltForrest(sb, nodeGraph, keyIO,
 		o.cbAddedItem, o.cbLookupRoot, o.cbLookupUUID)
-	if err := o.rebuild(ctx); err != nil {
-		return nil, err
-	}
-
-	return o.rebuilt.ListRoots(), nil
+	return o, nil
 }
 
 func (o *rebuilder) ioErr(ctx context.Context, err error) {
@@ -92,92 +97,173 @@ func (o *rebuilder) ioErr(ctx context.Context, err error) {
 	panic(err)
 }
 
-func (o *rebuilder) rebuild(_ctx context.Context) error {
+func (o *rebuilder) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
+	return o.rebuilt.ListRoots()
+}
+
+type itemStats struct {
+	textui.Portion[int]
+	NumAugments     int
+	NumFailures     int
+	NumAugmentTrees int
+}
+
+func (s itemStats) String() string {
+	// return textui.Sprintf("%v (queued %v augments and %v failures across %v trees)",
+	return textui.Sprintf("%v (aug:%v fail:%v trees:%v)",
+		s.Portion, s.NumAugments, s.NumFailures, s.NumAugmentTrees)
+}
+
+func (o *rebuilder) Rebuild(_ctx context.Context) error {
+	_ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "rebuild")
+
 	// Initialize
-	o.augmentQueue = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int)
+	o.itemQueue = make(containers.Set[keyAndTree])
+	o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue)
 
 	// Seed the queue
-	o.treeQueue = []btrfsprim.ObjID{
+	o.treeQueue = containers.NewSet[btrfsprim.ObjID](
 		btrfsprim.ROOT_TREE_OBJECTID,
 		btrfsprim.CHUNK_TREE_OBJECTID,
 		// btrfsprim.TREE_LOG_OBJECTID, // TODO(lukeshu): Special LOG_TREE handling
 		btrfsprim.BLOCK_GROUP_TREE_OBJECTID,
-	}
+	)
 
 	for passNum := 0; len(o.treeQueue) > 0 || len(o.itemQueue) > 0 || len(o.augmentQueue) > 0; passNum++ {
 		passCtx := dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.rebuild.pass", passNum)
 
 		// Add items to the queue (drain o.treeQueue, fill o.itemQueue)
-		stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items")
-		treeQueue := o.treeQueue
-		o.treeQueue = nil
-		sort.Slice(treeQueue, func(i, j int) bool {
-			return treeQueue[i] < treeQueue[j]
-		})
-		// Because trees can be wildly different sizes, it's impossible to have a meaningful
-		// progress percentage here.
-		for _, treeID := range treeQueue {
-			o.rebuilt.AddTree(stepCtx, treeID)
+		if true {
+			stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items")
+			treeQueue := o.treeQueue
+			o.treeQueue = make(containers.Set[btrfsprim.ObjID])
+			// Because trees can be wildly different sizes, it's impossible to have a meaningful
+			// progress percentage here.
+			for _, treeID := range maps.SortedKeys(treeQueue) {
+				if err := _ctx.Err(); err != nil {
+					return err
+				}
+				o.curKey = keyAndTree{TreeID: treeID}
+				o.rebuilt.Tree(stepCtx, treeID)
+			}
 		}
+		runtime.GC()
 
 		// Handle items in the queue (drain o.itemQueue, fill o.augmentQueue and o.treeQueue)
-		stepCtx = dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items")
-		itemQueue := o.itemQueue
-		o.itemQueue = nil
-		var progress textui.Portion[int]
-		progress.D = len(itemQueue)
-		progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-		stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
-		for i, key := range itemQueue {
-			itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key)
-			progress.N = i
-			progressWriter.Set(progress)
-			o.curKey = key
-			itemBody, ok := o.rebuilt.Load(itemCtx, key.TreeID, key.Key)
-			if !ok {
-				o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key))
+		if true {
+			stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items")
+			itemQueue := maps.Keys(o.itemQueue)
+			o.itemQueue = make(containers.Set[keyAndTree])
+			sort.Slice(itemQueue, func(i, j int) bool {
+				return itemQueue[i].Cmp(itemQueue[j]) < 0
+			})
+			var progress itemStats
+			progress.D = len(itemQueue)
+			progressWriter := textui.NewProgress[itemStats](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+			stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
+			type keyAndBody struct {
+				keyAndTree
+				Body btrfsitem.Item
 			}
-			handleItem(o, itemCtx, key.TreeID, btrfstree.Item{
-				Key:  key.Key,
-				Body: itemBody,
+			itemChan := make(chan keyAndBody, textui.Tunable(300)) // average items-per-node≈100; let's have a buffer of ~3 nodes
+			grp := dgroup.NewGroup(stepCtx, dgroup.GroupConfig{})
+			grp.Go("io", func(stepCtx context.Context) error {
+				defer close(itemChan)
+				for _, key := range itemQueue {
+					if err := stepCtx.Err(); err != nil {
+						return err
+					}
+					itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key)
+					itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).ReadItem(itemCtx, key.Key)
+					if !ok {
+						o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key))
+					}
+					itemChan <- keyAndBody{
+						keyAndTree: key,
+						Body:       itemBody,
+					}
+				}
+				return nil
+			})
+			grp.Go("cpu", func(stepCtx context.Context) error {
+				defer progressWriter.Done()
+				for item := range itemChan {
+					itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", item.keyAndTree)
+					o.curKey = item.keyAndTree
+					handleItem(o, itemCtx, item.TreeID, btrfstree.Item{
+						Key:  item.Key,
+						Body: item.Body,
+					})
+					if item.ItemType == btrfsitem.ROOT_ITEM_KEY {
+						o.treeQueue.Insert(item.ObjectID)
+					}
+					progress.N++
+					progress.NumAugments = o.numAugments
+					progress.NumFailures = o.numAugmentFailures
+					progress.NumAugmentTrees = len(o.augmentQueue)
+					progressWriter.Set(progress)
+				}
+				return nil
 			})
-			if key.ItemType == btrfsitem.ROOT_ITEM_KEY {
-				o.treeQueue = append(o.treeQueue, key.ObjectID)
+			if err := grp.Wait(); err != nil {
+				return err
 			}
 		}
-		progress.N = len(itemQueue)
-		progressWriter.Set(progress)
-		progressWriter.Done()
+		runtime.GC()
 
 		// Apply augments (drain o.augmentQueue, fill o.itemQueue)
-		stepCtx = dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "apply-augments")
-		resolvedAugments := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(o.augmentQueue))
-		progress.N = 0
-		progress.D = 0
-		for _, treeID := range maps.SortedKeys(o.augmentQueue) {
-			treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
-			resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, o.augmentQueue[treeID])
-			progress.D += len(resolvedAugments[treeID])
-		}
-		o.augmentQueue = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int)
-		progressWriter = textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-		stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
-		for _, treeID := range maps.SortedKeys(resolvedAugments) {
-			treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
-			for _, nodeAddr := range maps.SortedKeys(resolvedAugments[treeID]) {
-				progressWriter.Set(progress)
-				o.rebuilt.AddRoot(treeCtx, treeID, nodeAddr)
-				progress.N++
+		if true {
+			stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "apply-augments")
+			resolvedAugments := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(o.augmentQueue))
+			var progress textui.Portion[int]
+			for _, treeID := range maps.SortedKeys(o.augmentQueue) {
+				if err := _ctx.Err(); err != nil {
+					return err
+				}
+				treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
+				resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, treeID)
+				progress.D += len(resolvedAugments[treeID])
 			}
+			o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue)
+			o.numAugments = 0
+			o.numAugmentFailures = 0
+			runtime.GC()
+			progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+			stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
+			for _, treeID := range maps.SortedKeys(resolvedAugments) {
+				treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
+				for _, nodeAddr := range maps.SortedKeys(resolvedAugments[treeID]) {
+					if err := _ctx.Err(); err != nil {
+						progressWriter.Set(progress)
+						progressWriter.Done()
+						return err
+					}
+					progressWriter.Set(progress)
+					o.rebuilt.Tree(treeCtx, treeID).AddRoot(treeCtx, nodeAddr)
+					progress.N++
+				}
+			}
+			progressWriter.Set(progress)
+			progressWriter.Done()
 		}
-		progressWriter.Set(progress)
-		progressWriter.Done()
+		runtime.GC()
 	}
 	return nil
 }
 
+func (o *rebuilder) enqueueRetry() {
+	if o.curKey.Key == (btrfsprim.Key{}) {
+		o.treeQueue.Insert(o.curKey.TreeID)
+	} else {
+		o.itemQueue.Insert(o.curKey)
+	}
+}
+
 func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
-	o.itemQueue = append(o.itemQueue, keyAndTree{
+	if handleWouldBeNoOp(key.ItemType) {
+		return
+	}
+	o.itemQueue.Insert(keyAndTree{
 		TreeID: tree,
 		Key:    key,
 	})
@@ -185,14 +271,21 @@ func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key b
 
 func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "tree Root")
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key",
-		fmt.Sprintf("tree=%v key={%v %v ?}", btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY))
-	key, ok := o._want(ctx, btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY)
+	key := keyAndTree{
+		TreeID: btrfsprim.ROOT_TREE_OBJECTID,
+		Key: btrfsprim.Key{
+			ObjectID: tree,
+			ItemType: btrfsitem.ROOT_ITEM_KEY,
+		},
+	}
+	wantKey := fmt.Sprintf("tree=%v key={%v %v ?}", key.TreeID, key.ObjectID, key.ItemType)
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", wantKey)
+	key.Key, ok = o._want(ctx, key.TreeID, wantKey, key.ObjectID, key.ItemType)
 	if !ok {
-		o.itemQueue = append(o.itemQueue, o.curKey)
+		o.enqueueRetry()
 		return 0, btrfsitem.Root{}, false
 	}
-	itemBody, ok := o.rebuilt.Load(ctx, btrfsprim.ROOT_TREE_OBJECTID, key)
+	itemBody, ok := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key)
 	if !ok {
 		o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key))
 	}
@@ -200,7 +293,7 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off
 	case btrfsitem.Root:
 		return btrfsprim.Generation(key.Offset), itemBody, true
 	case btrfsitem.Error:
-		o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", btrfsprim.ROOT_TREE_OBJECTID, key, itemBody.Err))
+		o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", key, itemBody.Err))
 		return 0, btrfsitem.Root{}, false
 	default:
 		// This is a panic because the item decoder should not emit ROOT_ITEM items as anything but
@@ -210,14 +303,14 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off
 }
 
 func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
-	key := btrfsitem.UUIDToKey(uuid)
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "resolve parent UUID")
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: key})
-	if ok := o._wantOff(ctx, btrfsprim.UUID_TREE_OBJECTID, key); !ok {
-		o.itemQueue = append(o.itemQueue, o.curKey)
+	key := keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: btrfsitem.UUIDToKey(uuid)}
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", key.String())
+	if !o._wantOff(ctx, key.TreeID, key.String(), key.Key) {
+		o.enqueueRetry()
 		return 0, false
 	}
-	itemBody, ok := o.rebuilt.Load(ctx, btrfsprim.UUID_TREE_OBJECTID, key)
+	itemBody, ok := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key)
 	if !ok {
 		o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key))
 	}
@@ -225,7 +318,7 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b
 	case btrfsitem.UUIDMap:
 		return itemBody.ObjID, true
 	case btrfsitem.Error:
-		o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", btrfsprim.UUID_TREE_OBJECTID, key, itemBody.Err))
+		o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", key, itemBody.Err))
 		return 0, false
 	default:
 		// This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
@@ -234,24 +327,51 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b
 	}
 }
 
-func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances []map[btrfsvol.LogicalAddr]int) containers.Set[btrfsvol.LogicalAddr] {
-	distances := make(map[btrfsvol.LogicalAddr]int)
-	generations := make(map[btrfsvol.LogicalAddr]btrfsprim.Generation)
-	lists := make([]containers.Set[btrfsvol.LogicalAddr], len(listsWithDistances))
-	for i, listWithDistances := range listsWithDistances {
-		lists[i] = make(containers.Set[btrfsvol.LogicalAddr], len(listWithDistances))
-		for item, dist := range listWithDistances {
-			lists[i].Insert(item)
-			distances[item] = dist
-			generations[item] = o.graph.Nodes[item].Generation
-		}
-	}
-
+func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.ObjID) containers.Set[btrfsvol.LogicalAddr] {
 	// Define an algorithm that takes several lists of items, and returns a
 	// set of those items such that each input list contains zero or one of
 	// the items from your return set.  The same item may appear in multiple
 	// of the input lists.
-	//
+
+	type ChoiceInfo struct {
+		Count      int
+		Distance   int
+		Generation btrfsprim.Generation
+	}
+	choices := make(map[btrfsvol.LogicalAddr]ChoiceInfo)
+	// o.augmentQueue[treeID].zero is optimized storage for lists
+	// with zero items.  Go ahead and free that memory up.
+	o.augmentQueue[treeID].zero = nil
+	// o.augmentQueue[treeID].single is optimized storage for
+	// lists with exactly 1 item.
+	for _, choice := range o.augmentQueue[treeID].single {
+		if old, ok := choices[choice]; ok {
+			old.Count++
+			choices[choice] = old
+		} else {
+			choices[choice] = ChoiceInfo{
+				Count:      1,
+				Distance:   discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)),
+				Generation: o.graph.Nodes[choice].Generation,
+			}
+		}
+	}
+	// o.augmentQueue[treeID].multi is the main list storage.
+	for _, list := range o.augmentQueue[treeID].multi {
+		for choice := range list {
+			if old, ok := choices[choice]; ok {
+				old.Count++
+				choices[choice] = old
+			} else {
+				choices[choice] = ChoiceInfo{
+					Count:      1,
+					Distance:   discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)),
+					Generation: o.graph.Nodes[choice].Generation,
+				}
+			}
+		}
+	}
+
 	// > Example 1: Given the input lists
 	// >
 	// >     0: [A, B]
@@ -307,31 +427,24 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances
 	illegal := make(containers.Set[btrfsvol.LogicalAddr]) // cannot-be-accepted and already-accepted
 	accept := func(item btrfsvol.LogicalAddr) {
 		ret.Insert(item)
-		for _, list := range lists {
+		for _, list := range o.augmentQueue[treeID].multi {
 			if list.Has(item) {
 				illegal.InsertFrom(list)
 			}
 		}
 	}
 
-	counts := make(map[btrfsvol.LogicalAddr]int)
-	for _, list := range lists {
-		for item := range list {
-			counts[item]++
-		}
-	}
-
-	sortedItems := maps.Keys(distances)
+	sortedItems := maps.Keys(choices)
 	sort.Slice(sortedItems, func(i, j int) bool {
 		iItem, jItem := sortedItems[i], sortedItems[j]
-		if counts[iItem] != counts[jItem] {
-			return counts[iItem] > counts[jItem] // reverse this check; higher counts should sort lower
+		if choices[iItem].Count != choices[jItem].Count {
+			return choices[iItem].Count > choices[jItem].Count // reverse this check; higher counts should sort lower
 		}
-		if distances[iItem] != distances[jItem] {
-			return distances[iItem] < distances[jItem]
+		if choices[iItem].Distance != choices[jItem].Distance {
+			return choices[iItem].Distance < choices[jItem].Distance
 		}
-		if generations[iItem] != generations[jItem] {
-			return generations[iItem] > generations[jItem] // reverse this check; higher generations should sort lower
+		if choices[iItem].Generation != choices[jItem].Generation {
+			return choices[iItem].Generation > choices[jItem].Generation // reverse this check; higher generations should sort lower
 		}
 		return iItem < jItem // laddr is as good a tiebreaker as anything
 	})
@@ -341,35 +454,117 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances
 		}
 	}
 
-	for i, list := range lists {
+	// Log our result
+	wantKeys := append(
+		maps.Keys(o.augmentQueue[treeID].single),
+		maps.Keys(o.augmentQueue[treeID].multi)...)
+	sort.Strings(wantKeys)
+	for _, wantKey := range wantKeys {
+		list, ok := o.augmentQueue[treeID].multi[wantKey]
+		if !ok {
+			list = containers.NewSet[btrfsvol.LogicalAddr](o.augmentQueue[treeID].single[wantKey])
+		}
 		chose := list.Intersection(ret)
 		if len(chose) == 0 {
-			dlog.Infof(ctx, "lists[%d]: chose (none) from %v", i, maps.SortedKeys(list))
+			dlog.Infof(ctx, "lists[%q]: chose (none) from %v", wantKey, maps.SortedKeys(list))
 		} else {
-			dlog.Infof(ctx, "lists[%d]: chose %v from %v", i, chose.TakeOne(), maps.SortedKeys(list))
+			dlog.Infof(ctx, "lists[%q]: chose %v from %v", wantKey, chose.TakeOne(), maps.SortedKeys(list))
 		}
 	}
 
+	// Free some memory
+	o.augmentQueue[treeID].single = nil
+	o.augmentQueue[treeID].multi = nil
+	o.augmentQueue[treeID].keyBuf.Reset()
+
 	return ret
 }
 
 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
-func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, choices containers.Set[btrfsvol.LogicalAddr]) {
-	if len(choices) == 0 {
-		dlog.Error(ctx, "could not find wanted item")
+func shortenWantKey(wantKey string) string {
+	if !strings.HasPrefix(wantKey, "tree=") {
+		panic("should not happen")
+	}
+	sp := strings.IndexByte(wantKey, ' ')
+	if sp < 0 {
+		panic("should not happen")
+	}
+	return wantKey[sp+1:]
+}
+
+func (treeQueue *treeAugmentQueue) has(wantKey string) bool {
+	if treeQueue != nil {
+		wantKey = shortenWantKey(wantKey)
+		if treeQueue.zero != nil {
+			if _, ok := treeQueue.zero[wantKey]; ok {
+				return true
+			}
+		}
+		if treeQueue.single != nil {
+			if _, ok := treeQueue.single[wantKey]; ok {
+				return true
+			}
+		}
+		if treeQueue.multi != nil {
+			if _, ok := treeQueue.multi[wantKey]; ok {
+				return true
+			}
+		}
+	}
+	return false
+}
+
+func (treeQueue *treeAugmentQueue) store(wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) {
+	if len(choices) == 0 && (strings.Contains(wantKey, " name=") || strings.Contains(wantKey, "-")) {
+		// This wantKey is unlikely to come up again, so it's not worth storing a negative result.
 		return
 	}
-	choicesWithDist := make(map[btrfsvol.LogicalAddr]int, len(choices))
-	for choice := range choices {
-		dist, ok := o.rebuilt.COWDistance(ctx, treeID, o.graph.Nodes[choice].Owner)
-		if !ok {
-			panic(fmt.Errorf("should not happen: .wantAugment called for tree=%v with invalid choice=%v", treeID, choice))
+	wantKey = shortenWantKey(wantKey)
+	beg := treeQueue.keyBuf.Len()
+	if treeQueue.keyBuf.Cap()-beg < len(wantKey) {
+		treeQueue.keyBuf.Reset()
+		treeQueue.keyBuf.Grow(textui.Tunable(4096))
+		beg = 0
+	}
+	treeQueue.keyBuf.WriteString(wantKey)
+	wantKey = treeQueue.keyBuf.String()[beg:]
+
+	switch len(choices) {
+	case 0:
+		if treeQueue.zero == nil {
+			treeQueue.zero = make(map[string]struct{})
+		}
+		treeQueue.zero[wantKey] = struct{}{}
+	case 1:
+		if treeQueue.single == nil {
+			treeQueue.single = make(map[string]btrfsvol.LogicalAddr)
 		}
-		choicesWithDist[choice] = dist
+		treeQueue.single[wantKey] = choices.TakeOne()
+	default:
+		if treeQueue.multi == nil {
+			treeQueue.multi = make(map[string]containers.Set[btrfsvol.LogicalAddr])
+		}
+		treeQueue.multi[wantKey] = choices
+	}
+}
+
+func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool {
+	return o.augmentQueue[treeID].has(wantKey)
+}
+
+func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) {
+	if o.augmentQueue[treeID] == nil {
+		o.augmentQueue[treeID] = new(treeAugmentQueue)
+	}
+	o.augmentQueue[treeID].store(wantKey, choices)
+	if len(choices) == 0 {
+		dlog.Error(ctx, "could not find wanted item")
+		o.numAugmentFailures++
+	} else {
+		dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices))
+		o.numAugments++
 	}
-	dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choicesWithDist))
-	o.augmentQueue[treeID] = append(o.augmentQueue[treeID], choicesWithDist)
 }
 
 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
@@ -382,14 +577,14 @@ func (o *rebuilder) fsErr(ctx context.Context, e error) {
 // want implements rebuildCallbacks.
 func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) {
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
-		fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ))
-	o._want(ctx, treeID, objID, typ)
+	wantKey := fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey)
+	o._want(ctx, treeID, wantKey, objID, typ)
 }
 
-func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) {
-	if !o.rebuilt.AddTree(ctx, treeID) {
-		o.itemQueue = append(o.itemQueue, o.curKey)
+func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) {
+	if o.rebuilt.Tree(ctx, treeID) == nil {
+		o.enqueueRetry()
 		return btrfsprim.Key{}, false
 	}
 
@@ -399,7 +594,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr
 		ObjectID: objID,
 		ItemType: typ,
 	}
-	if key, ok := o.rebuilt.Search(ctx, treeID, func(key btrfsprim.Key) int {
+	if key, _, ok := o.rebuilt.Tree(ctx, treeID).Items(ctx).Search(func(key btrfsprim.Key, _ keyio.ItemPtr) int {
 		key.Offset = 0
 		return tgt.Cmp(key)
 	}); ok {
@@ -408,14 +603,17 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr
 
 	// OK, we need to insert it
 
+	if o.hasAugment(treeID, wantKey) {
+		return btrfsprim.Key{}, false
+	}
 	wants := make(containers.Set[btrfsvol.LogicalAddr])
-	o.rebuilt.Keys(treeID).Subrange(
+	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
 		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) },
 		func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
-			wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node))
+			wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
 			return true
 		})
-	o.wantAugment(ctx, treeID, wants)
+	o.wantAugment(ctx, treeID, wantKey, wants)
 	return btrfsprim.Key{}, false
 }
 
@@ -427,43 +625,42 @@ func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim
 		Offset:   off,
 	}
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", keyAndTree{TreeID: treeID, Key: key})
-	o._wantOff(ctx, treeID, key)
+	wantKey := keyAndTree{TreeID: treeID, Key: key}.String()
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey)
+	o._wantOff(ctx, treeID, wantKey, key)
 }
 
-func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt btrfsprim.Key) (ok bool) {
-	if !o.rebuilt.AddTree(ctx, treeID) {
-		o.itemQueue = append(o.itemQueue, o.curKey)
+func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, tgt btrfsprim.Key) (ok bool) {
+	if o.rebuilt.Tree(ctx, treeID) == nil {
+		o.enqueueRetry()
 		return false
 	}
 
 	// check if we already have it
 
-	if _, ok := o.rebuilt.Load(ctx, treeID, tgt); ok {
+	if _, ok := o.rebuilt.Tree(ctx, treeID).Items(ctx).Load(tgt); ok {
 		return true
 	}
 
 	// OK, we need to insert it
 
+	if o.hasAugment(treeID, wantKey) {
+		return false
+	}
 	wants := make(containers.Set[btrfsvol.LogicalAddr])
-	o.rebuilt.Keys(treeID).Subrange(
+	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
 		func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) },
 		func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
-			wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node))
+			wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
 			return true
 		})
-	o.wantAugment(ctx, treeID, wants)
+	o.wantAugment(ctx, treeID, wantKey, wants)
 	return false
 }
 
-// wantFunc implements rebuildCallbacks.
-func (o *rebuilder) wantFunc(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) {
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
-		fmt.Sprintf("tree=%v key={%v %v ?} +func", treeID, objID, typ))
-
-	if !o.rebuilt.AddTree(ctx, treeID) {
-		o.itemQueue = append(o.itemQueue, o.curKey)
+func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) {
+	if o.rebuilt.Tree(ctx, treeID) == nil {
+		o.enqueueRetry()
 		return
 	}
 
@@ -473,36 +670,104 @@ func (o *rebuilder) wantFunc(ctx context.Context, reason string, treeID btrfspri
 		ObjectID: objID,
 		ItemType: typ,
 	}
-	keys := o.rebuilt.SearchAll(ctx, treeID, func(key btrfsprim.Key) int {
-		key.Offset = 0
-		return tgt.Cmp(key)
-	})
-	for _, itemKey := range keys {
-		itemBody, ok := o.rebuilt.Load(ctx, treeID, itemKey)
-		if !ok {
-			o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", itemKey))
-		}
-		if fn(itemBody) {
-			return
-		}
+	found := false
+	o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange(
+		func(key btrfsprim.Key, _ keyio.ItemPtr) int {
+			key.Offset = 0
+			return tgt.Cmp(key)
+		},
+		func(_ btrfsprim.Key, itemPtr keyio.ItemPtr) bool {
+			if fn(itemPtr) {
+				found = true
+			}
+			return !found
+		})
+	if found {
+		return
 	}
 
 	// OK, we need to insert it
 
+	if o.hasAugment(treeID, wantKey) {
+		return
+	}
 	wants := make(containers.Set[btrfsvol.LogicalAddr])
-	o.rebuilt.Keys(treeID).Subrange(
+	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
 		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) },
 		func(k btrfsprim.Key, v keyio.ItemPtr) bool {
-			itemBody, ok := o.keyIO.ReadItem(ctx, v)
+			if fn(v) {
+				wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
+			}
+			return true
+		})
+	o.wantAugment(ctx, treeID, wantKey, wants)
+}
+
+// wantDirIndex implements rebuildCallbacks.
+func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) {
+	typ := btrfsitem.DIR_INDEX_KEY
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
+	wantKey := fmt.Sprintf("tree=%v key={%v %v ?} name=%q", treeID, objID, typ, name)
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey)
+	o._wantFunc(ctx, treeID, wantKey, objID, typ, func(ptr keyio.ItemPtr) bool {
+		itemName, ok := o.keyIO.Names[ptr]
+		return ok && bytes.Equal(itemName, name)
+	})
+}
+
+func (o *rebuilder) _walkRange(
+	ctx context.Context,
+	items *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr],
+	treeID, objID btrfsprim.ObjID, typ btrfsprim.ItemType,
+	beg, end uint64,
+	fn func(key btrfsprim.Key, ptr keyio.ItemPtr, beg, end uint64),
+) {
+	min := btrfsprim.Key{
+		ObjectID: objID,
+		ItemType: typ,
+		Offset:   0, // *NOT* `beg`
+	}
+	max := btrfsprim.Key{
+		ObjectID: objID,
+		ItemType: typ,
+		Offset:   end - 1,
+	}
+	items.Subrange(
+		func(runKey btrfsprim.Key, _ keyio.ItemPtr) int {
+			switch {
+			case min.Cmp(runKey) < 0:
+				return 1
+			case max.Cmp(runKey) > 0:
+				return -1
+			default:
+				return 0
+			}
+		},
+		func(runKey btrfsprim.Key, runPtr keyio.ItemPtr) bool {
+			runSizeAndErr, ok := o.keyIO.Sizes[runPtr]
 			if !ok {
-				o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v at %v", k, v))
+				panic(fmt.Errorf("should not happen: %v (%v) did not have a size recorded",
+					runPtr, keyAndTree{TreeID: treeID, Key: runKey}))
+			}
+			if runSizeAndErr.Err != nil {
+				o.fsErr(ctx, fmt.Errorf("get size: %v (%v): %w",
+					runPtr, keyAndTree{TreeID: treeID, Key: runKey},
+					runSizeAndErr.Err))
+				return true
 			}
-			if fn(itemBody) {
-				wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node))
+			runSize := runSizeAndErr.Size
+			if runSize == 0 {
+				return true
+			}
+			runBeg := runKey.Offset
+			runEnd := runBeg + runSize
+			if runEnd <= beg {
+				return true
 			}
+
+			fn(runKey, runPtr, runBeg, runEnd)
 			return true
 		})
-	o.wantAugment(ctx, treeID, wants)
 }
 
 func (o *rebuilder) _wantRange(
@@ -513,46 +778,12 @@ func (o *rebuilder) _wantRange(
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
 		fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ))
 
-	if !o.rebuilt.AddTree(ctx, treeID) {
-		o.itemQueue = append(o.itemQueue, o.curKey)
+	if o.rebuilt.Tree(ctx, treeID) == nil {
+		o.enqueueRetry()
 		return
 	}
 
-	sizeFn := func(key btrfsprim.Key) (uint64, error) {
-		ptr, ok := o.rebuilt.Keys(treeID).Load(key)
-		if !ok {
-			panic(fmt.Errorf("should not happen: could not load key: %v", key))
-		}
-		sizeAndErr, ok := o.keyIO.Sizes[ptr]
-		if !ok {
-			panic(fmt.Errorf("should not happen: %v item did not have a size recorded", typ))
-		}
-		return sizeAndErr.Size, sizeAndErr.Err
-	}
-
-	// Step 1: Build a listing of the runs that we do have.
-	runMin := btrfsprim.Key{
-		ObjectID: objID,
-		ItemType: typ,
-		Offset:   0, // *NOT* `beg`
-	}
-	runMax := btrfsprim.Key{
-		ObjectID: objID,
-		ItemType: typ,
-		Offset:   end - 1,
-	}
-	runKeys := o.rebuilt.SearchAll(ctx, treeID, func(key btrfsprim.Key) int {
-		switch {
-		case runMin.Cmp(key) < 0:
-			return 1
-		case runMax.Cmp(key) > 0:
-			return -1
-		default:
-			return 0
-		}
-	})
-
-	// Step 2: Build a listing of the gaps.
+	// Step 1: Build a listing of the gaps.
 	//
 	// Start with a gap of the whole range, then subtract each run
 	// from it.
@@ -569,111 +800,79 @@ func (o *rebuilder) _wantRange(
 		Beg: beg,
 		End: end,
 	})
-	for _, runKey := range runKeys {
-		runSize, err := sizeFn(runKey)
-		if err != nil {
-			o.fsErr(ctx, fmt.Errorf("tree=%v key=%v: %w", treeID, runKey, err))
-		}
-		if runSize == 0 {
-			continue
-		}
-		runBeg := runKey.Offset
-		runEnd := runBeg + runSize
-		if runEnd <= beg {
-			continue
-		}
-		overlappingGaps := gaps.SearchRange(func(gap gap) int {
-			switch {
-			case gap.End <= runBeg:
-				return 1
-			case runEnd <= gap.Beg:
-				return -1
-			default:
-				return 0
-			}
-		})
-		if len(overlappingGaps) == 0 {
-			continue
-		}
-		gapsBeg := overlappingGaps[0].Beg
-		gapsEnd := overlappingGaps[len(overlappingGaps)-1].End
-		for _, gap := range overlappingGaps {
-			gaps.Delete(containers.NativeOrdered[uint64]{Val: gap.Beg})
-		}
-		if gapsBeg < runBeg {
-			gaps.Insert(gap{
-				Beg: gapsBeg,
-				End: runBeg,
-			})
-		}
-		if gapsEnd > runEnd {
-			gaps.Insert(gap{
-				Beg: runEnd,
-				End: gapsEnd,
-			})
-		}
-	}
-
-	// Step 2: Fill each gap.
-	_ = gaps.Walk(func(rbNode *containers.RBNode[gap]) error {
-		gap := rbNode.Value
-		last := gap.Beg
-		runMin := btrfsprim.Key{
-			ObjectID: objID,
-			ItemType: typ,
-			Offset:   0, // *NOT* `gap.Beg`
-		}
-		runMax := btrfsprim.Key{
-			ObjectID: objID,
-			ItemType: typ,
-			Offset:   gap.End - 1,
-		}
-		o.rebuilt.Keys(treeID).Subrange(
-			func(key btrfsprim.Key, _ keyio.ItemPtr) int {
+	o._walkRange(
+		ctx,
+		o.rebuilt.Tree(ctx, treeID).Items(ctx),
+		treeID, objID, typ, beg, end,
+		func(runKey btrfsprim.Key, _ keyio.ItemPtr, runBeg, runEnd uint64) {
+			overlappingGaps := gaps.SearchRange(func(gap gap) int {
 				switch {
-				case runMin.Cmp(key) < 0:
+				case gap.End <= runBeg:
 					return 1
-				case runMax.Cmp(key) > 0:
+				case runEnd <= gap.Beg:
 					return -1
 				default:
 					return 0
 				}
-			},
-			func(k btrfsprim.Key, v keyio.ItemPtr) bool {
-				runSize, err := sizeFn(k)
-				if err != nil {
-					o.fsErr(ctx, fmt.Errorf("tree=%v key=%v: %w", treeID, k, err))
-					return true
-				}
-				if runSize == 0 {
-					return true
-				}
-				runBeg := k.Offset
-				runEnd := runBeg + runSize
-				if runEnd <= gap.Beg {
-					return true
-				}
+			})
+			if len(overlappingGaps) == 0 {
+				return
+			}
+			gapsBeg := overlappingGaps[0].Beg
+			gapsEnd := overlappingGaps[len(overlappingGaps)-1].End
+			for _, gap := range overlappingGaps {
+				gaps.Delete(containers.NativeOrdered[uint64]{Val: gap.Beg})
+			}
+			if gapsBeg < runBeg {
+				gaps.Insert(gap{
+					Beg: gapsBeg,
+					End: runBeg,
+				})
+			}
+			if gapsEnd > runEnd {
+				gaps.Insert(gap{
+					Beg: runEnd,
+					End: gapsEnd,
+				})
+			}
+		})
 
+	// Step 2: Fill each gap.
+	if gaps.Len() == 0 {
+		return
+	}
+	potentialItems := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx)
+	_ = gaps.Walk(func(rbNode *containers.RBNode[gap]) error {
+		gap := rbNode.Value
+		last := gap.Beg
+		o._walkRange(
+			ctx,
+			potentialItems,
+			treeID, objID, typ, gap.Beg, gap.End,
+			func(k btrfsprim.Key, v keyio.ItemPtr, runBeg, runEnd uint64) {
 				// TODO: This is dumb and greedy.
 				if last < runBeg {
 					// log an error
-					wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
-						fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, last, runBeg))
-					o.wantAugment(wantCtx, treeID, nil)
+					wantKey := fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, last, runBeg)
+					if !o.hasAugment(treeID, wantKey) {
+						wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey)
+						o.wantAugment(wantCtx, treeID, wantKey, nil)
+					}
+				}
+				wantKey := fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, gap.Beg, gap.End)
+				if !o.hasAugment(treeID, wantKey) {
+					wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey)
+					o.wantAugment(wantCtx, treeID, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node))
 				}
-				wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
-					fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, gap.Beg, gap.End))
-				o.wantAugment(wantCtx, treeID, o.rebuilt.LeafToRoots(ctx, treeID, v.Node))
 				last = runEnd
-
-				return true
 			})
 		if last < gap.End {
 			// log an error
-			wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
-				fmt.Sprintf("tree=%v key={%v, %v, %v-%v}",
-					treeID, objID, typ, last, gap.End))
-			o.wantAugment(wantCtx, treeID, nil)
+			wantKey := fmt.Sprintf("tree=%v key={%v, %v, %v-%v}", treeID, objID, typ, last, gap.End)
+			if !o.hasAugment(treeID, wantKey) {
+				wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey)
+				o.wantAugment(wantCtx, treeID, wantKey, nil)
+			}
 		}
 		return nil
 	})
@@ -682,8 +881,41 @@ func (o *rebuilder) _wantRange(
 // func implements rebuildCallbacks.
 //
 // interval is [beg, end)
-func (o *rebuilder) wantCSum(ctx context.Context, reason string, beg, end btrfsvol.LogicalAddr) {
+func (o *rebuilder) wantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) {
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
+
+	inodeKey := keyAndTree{
+		TreeID: inodeTree,
+		Key: btrfsprim.Key{
+			ObjectID: inode,
+			ItemType: btrfsitem.INODE_ITEM_KEY,
+			Offset:   0,
+		},
+	}
+	inodeCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", inodeKey.String())
+	if !o._wantOff(inodeCtx, inodeKey.TreeID, inodeKey.String(), inodeKey.Key) {
+		o.enqueueRetry()
+		return
+	}
+	inodePtr, ok := o.rebuilt.Tree(inodeCtx, inodeKey.TreeID).Items(inodeCtx).Load(inodeKey.Key)
+	if !ok {
+		panic(fmt.Errorf("should not happen: could not load key: %v", inodeKey))
+	}
+	inodeFlags, ok := o.keyIO.Flags[inodePtr]
+	if !ok {
+		panic(fmt.Errorf("should not happen: INODE_ITEM did not have flags recorded"))
+	}
+	if inodeFlags.Err != nil {
+		o.fsErr(inodeCtx, inodeFlags.Err)
+		return
+	}
+
+	if inodeFlags.NoDataSum {
+		return
+	}
+
+	beg = roundDown(beg, btrfssum.BlockSize)
+	end = roundUp(end, btrfssum.BlockSize)
 	const treeID = btrfsprim.CSUM_TREE_OBJECTID
 	o._wantRange(ctx, treeID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY,
 		uint64(beg), uint64(end))
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
index bf4c95d..9e40465 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
@@ -7,11 +7,9 @@ package rebuildnodes
 import (
 	"context"
 	"fmt"
-	"reflect"
 
 	"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/btrfssum"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 )
@@ -20,11 +18,33 @@ type rebuildCallbacks interface {
 	fsErr(ctx context.Context, e error)
 	want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType)
 	wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64)
-	wantFunc(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool)
-	wantCSum(ctx context.Context, reason string, beg, end btrfsvol.LogicalAddr) // interval is [beg, end)
+	wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte)
+	wantCSum(ctx context.Context, reason string, inodeTree, inodeItem btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) // interval is [beg, end)
 	wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64)
 }
 
+// handleWouldBeNoOp returns whether or not a call to handleItem for a
+// given item type would be a no-op.
+func handleWouldBeNoOp(typ btrfsprim.ItemType) bool {
+	switch typ {
+	case // btrfsitem.Dev
+		btrfsprim.DEV_ITEM_KEY,
+		// btrfsitem.DevStats
+		btrfsprim.PERSISTENT_ITEM_KEY,
+		// btrfsitem.Empty
+		btrfsprim.ORPHAN_ITEM_KEY,
+		btrfsprim.TREE_BLOCK_REF_KEY,
+		btrfsprim.SHARED_BLOCK_REF_KEY,
+		btrfsprim.FREE_SPACE_EXTENT_KEY,
+		btrfsprim.QGROUP_RELATION_KEY,
+		// btrfsite.ExtentCSum
+		btrfsprim.EXTENT_CSUM_KEY:
+		return true
+	default:
+		return false
+	}
+}
+
 func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, item btrfstree.Item) {
 	// Notionally, just express the relationships shown in
 	// https://btrfs.wiki.kernel.org/index.php/File:References.png (from the page
@@ -65,13 +85,10 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 		// siblings
 		switch item.Key.ItemType {
 		case btrfsitem.DIR_ITEM_KEY:
-			o.wantFunc(ctx, "corresponding DIR_INDEX",
+			o.wantDirIndex(ctx, "corresponding DIR_INDEX",
 				treeID,
 				item.Key.ObjectID,
-				btrfsitem.DIR_INDEX_KEY,
-				func(peerItem btrfsitem.Item) bool {
-					return reflect.DeepEqual(item, peerItem)
-				})
+				body.Name)
 		case btrfsitem.DIR_INDEX_KEY:
 			o.wantOff(ctx, "corresponding DIR_ITEM",
 				treeID,
@@ -169,10 +186,11 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 		case btrfsitem.FILE_EXTENT_INLINE:
 			// nothing
 		case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC:
-			// TODO: Check if inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM)
+			// NB: o.wantCSum checks inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) for us.
 			o.wantCSum(ctx, "data sum",
-				roundDown(body.BodyExtent.DiskByteNr, btrfssum.BlockSize),
-				roundUp(body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes), btrfssum.BlockSize))
+				treeID, item.Key.ObjectID,
+				body.BodyExtent.DiskByteNr,
+				body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes))
 		default:
 			o.fsErr(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type))
 		}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
index 7e96e29..7e19802 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
@@ -20,14 +20,15 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
-func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (graph.Graph, *keyio.Handle, error) {
-	dlog.Infof(ctx, "Reading node data from FS...")
-
+func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (btrfstree.Superblock, graph.Graph, *keyio.Handle, error) {
+	dlog.Info(ctx, "Reading superblock...")
 	sb, err := fs.Superblock()
 	if err != nil {
-		return graph.Graph{}, nil, err
+		return btrfstree.Superblock{}, graph.Graph{}, nil, err
 	}
 
+	dlog.Infof(ctx, "Reading node data from FS...")
+
 	var stats textui.Portion[int]
 	stats.D = countNodes(scanResults)
 	progressWriter := textui.NewProgress[textui.Portion[int]](
@@ -40,11 +41,14 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
 	progressWriter.Set(stats)
 	for _, devResults := range scanResults {
 		for laddr := range devResults.FoundNodes {
+			if err := ctx.Err(); err != nil {
+				return btrfstree.Superblock{}, graph.Graph{}, nil, err
+			}
 			nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
 				LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
 			})
 			if err != nil {
-				return graph.Graph{}, nil, err
+				return btrfstree.Superblock{}, graph.Graph{}, nil, err
 			}
 
 			nodeGraph.InsertNode(nodeRef)
@@ -61,9 +65,9 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
 	dlog.Info(ctx, "... done reading node data")
 
 	if err := nodeGraph.FinalCheck(ctx, fs, *sb); err != nil {
-		return graph.Graph{}, nil, err
+		return btrfstree.Superblock{}, graph.Graph{}, nil, err
 	}
 	keyIO.SetGraph(*nodeGraph)
 
-	return *nodeGraph, keyIO, nil
+	return *sb, *nodeGraph, keyIO, nil
 }
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
index 8c43dad..9d91f23 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
@@ -25,3 +25,7 @@ func roundDown[T constraints.Integer](n, d T) T {
 func roundUp[T constraints.Integer](n, d T) T {
 	return ((n + d - 1) / d) * d
 }
+
+func discardOK[T any](val T, _ bool) T {
+	return val
+}
diff --git a/lib/containers/sortedmap.go b/lib/containers/sortedmap.go
index d6d2f9e..52308c9 100644
--- a/lib/containers/sortedmap.go
+++ b/lib/containers/sortedmap.go
@@ -92,3 +92,7 @@ func (m *SortedMap[K, V]) SearchAll(fn func(K, V) int) []OrderedKV[K, V] {
 		return fn(kv.K, kv.V)
 	})
 }
+
+func (m *SortedMap[K, V]) Len() int {
+	return m.inner.Len()
+}
diff --git a/lib/textui/log.go b/lib/textui/log.go
index 801e9eb..110e1aa 100644
--- a/lib/textui/log.go
+++ b/lib/textui/log.go
@@ -180,7 +180,7 @@ func (l *logger) log(lvl dlog.LogLevel, writeMsg func(io.Writer)) {
 
 	// time ////////////////////////////////////////////////////////////////
 	now := time.Now()
-	const timeFmt = "2006-01-02 15:04:05.0000"
+	const timeFmt = "15:04:05.0000"
 	logBuf.WriteString(timeFmt)
 	now.AppendFormat(logBuf.Bytes()[:0], timeFmt)
 
@@ -317,18 +317,22 @@ func fieldOrd(key string) int {
 		return -25
 	// step=rebuild (any substep)
 	case "btrfsinspect.rebuild-nodes.rebuild.want.key":
-		return -7
+		return -9
 	case "btrfsinspect.rebuild-nodes.rebuild.want.reason":
-		return -6
+		return -8
 	case "btrfsinspect.rebuild-nodes.rebuild.add-tree":
+		return -7
+	case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key":
+		return -6
+	case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason":
 		return -5
-	case "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep":
+	case "btrfsinspect.rebuild-nodes.rebuild.add-root":
 		return -4
-	case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key":
+	case "btrfsinspect.rebuild-nodes.rebuild.index-inc-items":
 		return -3
-	case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason":
+	case "btrfsinspect.rebuild-nodes.rebuild.index-all-items":
 		return -2
-	case "btrfsinspect.rebuild-nodes.rebuild.add-root":
+	case "btrfsinspect.rebuild-nodes.rebuild.index-nodes":
 		return -1
 
 	// other ///////////////////////////////////////////////////////////////
@@ -368,6 +372,7 @@ func writeField(w io.Writer, key string, val any) {
 			if strings.HasPrefix(valStr, "/main/") {
 				valStr = strings.TrimPrefix(valStr, "/main")
 			}
+			valStr = strings.TrimPrefix(valStr, "/")
 		}
 	case strings.HasSuffix(name, ".pass"):
 		fmt.Fprintf(w, "/pass-%s", valStr)
diff --git a/lib/textui/log_memstats.go b/lib/textui/log_memstats.go
index 6e3c3a1..31d526f 100644
--- a/lib/textui/log_memstats.go
+++ b/lib/textui/log_memstats.go
@@ -11,6 +11,13 @@ import (
 	"time"
 )
 
+// LiveMemUse is an object that stringifies as the live memory use of
+// the program.
+//
+// It is intended to be used with dlog by attaching it as a field, so
+// that all log lines include the current memory use:
+//
+//	ctx = dlog.WithField(ctx, "mem", new(textui.LiveMemUse))
 type LiveMemUse struct {
 	mu    sync.Mutex
 	stats runtime.MemStats
@@ -19,14 +26,19 @@ type LiveMemUse struct {
 
 var _ fmt.Stringer = (*LiveMemUse)(nil)
 
-var liveMemUseUpdateInterval = Tunable(1 * time.Second)
+// LiveMemUseUpdateInterval is the shortest interval on which
+// LiveMemUse is willing to update; we have this minimum interval
+// because it stops the world to collect memory statistics, so we
+// don't want to be updating the statistics too often.
+var LiveMemUseUpdateInterval = Tunable(1 * time.Second)
 
+// String implements fmt.Stringer.
 func (o *LiveMemUse) String() string {
 	o.mu.Lock()
 
 	// runtime.ReadMemStats() calls stopTheWorld(), so we want to
 	// rate-limit how often we call it.
-	if now := time.Now(); now.Sub(o.last) > liveMemUseUpdateInterval {
+	if now := time.Now(); now.Sub(o.last) > LiveMemUseUpdateInterval {
 		runtime.ReadMemStats(&o.stats)
 		o.last = now
 	}
diff --git a/lib/textui/log_test.go b/lib/textui/log_test.go
index 514d96e..bcd9c39 100644
--- a/lib/textui/log_test.go
+++ b/lib/textui/log_test.go
@@ -16,7 +16,7 @@ import (
 )
 
 func logLineRegexp(inner string) string {
-	return `[0-9]{4}-[0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}:[0-9]{2}\.[0-9]{4} ` + inner + ` \(from lib/textui/log_test\.go:[0-9]+\)\n`
+	return `[0-9]{2}:[0-9]{2}:[0-9]{2}\.[0-9]{4} ` + inner + ` \(from lib/textui/log_test\.go:[0-9]+\)\n`
 }
 
 func TestLogFormat(t *testing.T) {
diff --git a/scripts/main.sh b/scripts/main.sh
index 160aa42..d89f387 100755
--- a/scripts/main.sh
+++ b/scripts/main.sh
@@ -17,6 +17,8 @@ CGO_ENABLED=0 go build -trimpath ./cmd/btrfs-rec
 mkdir -p "$b.gen"
 { set +x; } &>/dev/null
 
+export GOMEMLIMIT="$(awk '/^MemTotal:/{ print $2 "KiB" }' </proc/meminfo)"
+
 gen $b.gen/0.scandevices.json \
     ./btrfs-rec --pv=$b.img \
     inspect scandevices