Merge branch 'lukeshu/rebuild-nodes-take5'

1 files changed, 261 insertions, 624 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
index 624441f..dc78c2e 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
@@ -5,12 +5,10 @@
 package rebuildnodes
 
 import (
-	"bytes"
 	"context"
 	"fmt"
 	"runtime"
 	"sort"
-	"strings"
 	"time"
 
 	"github.com/datawire/dlib/dgroup"
@@ -19,7 +17,6 @@ import (
 	"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"
@@ -54,24 +51,27 @@ type rebuilder struct {
 
 	rebuilt *btrees.RebuiltForrest
 
-	curKey             keyAndTree
+	curKey struct {
+		TreeID btrfsprim.ObjID
+		Key    containers.Optional[btrfsprim.Key]
+	}
 	treeQueue          containers.Set[btrfsprim.ObjID]
-	itemQueue          containers.Set[keyAndTree]
+	addedItemQueue     containers.Set[keyAndTree]
+	settledItemQueue   containers.Set[keyAndTree]
 	augmentQueue       map[btrfsprim.ObjID]*treeAugmentQueue
 	numAugments        int
 	numAugmentFailures int
 }
 
 type treeAugmentQueue struct {
-	keyBuf strings.Builder
-	zero   map[string]struct{}
-	single map[string]btrfsvol.LogicalAddr
-	multi  map[string]containers.Set[btrfsvol.LogicalAddr]
+	zero   map[Want]struct{}
+	single map[Want]btrfsvol.LogicalAddr
+	multi  map[Want]containers.Set[btrfsvol.LogicalAddr]
 }
 
 type Rebuilder interface {
 	Rebuild(context.Context) error
-	ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]
+	ListRoots(context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]
 }
 
 func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (Rebuilder, error) {
@@ -86,39 +86,20 @@ func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec
 		graph: nodeGraph,
 		keyIO: keyIO,
 	}
-	o.rebuilt = btrees.NewRebuiltForrest(sb, nodeGraph, keyIO,
-		o.cbAddedItem, o.cbLookupRoot, o.cbLookupUUID)
+	o.rebuilt = btrees.NewRebuiltForrest(sb, nodeGraph, keyIO, o)
 	return o, nil
 }
 
-func (o *rebuilder) ioErr(ctx context.Context, err error) {
-	err = fmt.Errorf("should not happen: i/o error: %w", err)
-	dlog.Error(ctx, err)
-	panic(err)
-}
-
-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) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
+	return o.rebuilt.ListRoots(ctx)
 }
 
-func (o *rebuilder) Rebuild(_ctx context.Context) error {
-	_ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "rebuild")
+func (o *rebuilder) Rebuild(ctx context.Context) error {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.step", "rebuild")
 
 	// Initialize
-	o.itemQueue = make(containers.Set[keyAndTree])
+	o.addedItemQueue = make(containers.Set[keyAndTree])
+	o.settledItemQueue = make(containers.Set[keyAndTree])
 	o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue)
 
 	// Seed the queue
@@ -129,201 +110,246 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error {
 		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)
-		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)
-			}
+	// Run
+	for passNum := 0; len(o.treeQueue) > 0 || len(o.addedItemQueue) > 0 || len(o.settledItemQueue) > 0 || len(o.augmentQueue) > 0; passNum++ {
+		ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.pass", passNum)
+
+		// Crawl trees (Drain o.treeQueue, fill o.addedItemQueue).
+		if err := o.processTreeQueue(ctx); err != nil {
+			return err
 		}
 		runtime.GC()
 
-		// Handle items in the queue (drain o.itemQueue, fill o.augmentQueue and o.treeQueue)
-		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].Compare(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
+		if len(o.addedItemQueue) > 0 {
+			// Settle items (drain o.addedItemQueue, fill o.augmentQueue and o.settledItemQueue).
+			if err := o.processAddedItemQueue(ctx); err != nil {
+				return err
 			}
-			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 err := grp.Wait(); err != nil {
+		} else {
+			// Process items (drain o.settledItemQueue, fill o.augmentQueue and o.treeQueue).
+			if err := o.processSettledItemQueue(ctx); err != nil {
 				return err
 			}
 		}
 		runtime.GC()
 
-		// Apply augments (drain o.augmentQueue, fill o.itemQueue)
-		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()
+		// Apply augments (drain o.augmentQueue, fill o.addedItemQueue).
+		if err := o.processAugmentQueue(ctx); err != nil {
+			return err
 		}
 		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)
+// processTreeQueue drains o.treeQueue, filling o.addedItemQueue.
+func (o *rebuilder) processTreeQueue(ctx context.Context) error {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items")
+
+	queue := maps.SortedKeys(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.
+	o.curKey.Key.OK = false
+	for _, o.curKey.TreeID = range queue {
+		if err := ctx.Err(); err != nil {
+			return err
+		}
+		// This will call o.AddedItem as nescessary, which
+		// inserts to o.addedItemQueue.
+		_ = o.rebuilt.Tree(ctx, o.curKey.TreeID)
 	}
+
+	return nil
 }
 
-func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
-	if handleWouldBeNoOp(key.ItemType) {
-		return
+type settleItemStats struct {
+	textui.Portion[int]
+	NumAugments     int
+	NumAugmentTrees int
+}
+
+func (s settleItemStats) String() string {
+	// return textui.Sprintf("%v (queued %v augments across %v trees)",
+	return textui.Sprintf("%v (aug:%v trees:%v)",
+		s.Portion, s.NumAugments, s.NumAugmentTrees)
+}
+
+// processAddedItemQueue drains o.addedItemQueue, filling o.augmentQueue and o.settledItemQueue.
+func (o *rebuilder) processAddedItemQueue(ctx context.Context) error {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "settle-items")
+
+	queue := maps.Keys(o.addedItemQueue)
+	o.addedItemQueue = make(containers.Set[keyAndTree])
+	sort.Slice(queue, func(i, j int) bool {
+		return queue[i].Compare(queue[j]) < 0
+	})
+
+	var progress settleItemStats
+	progress.D = len(queue)
+	progressWriter := textui.NewProgress[settleItemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
+
+	for i, key := range queue {
+		progress.N = i
+		progressWriter.Set(progress)
+
+		ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.settle.item", key)
+		tree := o.rebuilt.Tree(ctx, key.TreeID)
+		incPtr, ok := tree.Items(ctx).Load(key.Key)
+		if !ok {
+			panic(fmt.Errorf("should not happen: failed to load already-added item: %v", key))
+		}
+		excPtr, ok := tree.PotentialItems(ctx).Load(key.Key)
+		if ok && tree.ShouldReplace(incPtr.Node, excPtr.Node) {
+			wantKey := WantWithTree{
+				TreeID: key.TreeID,
+				Key:    wantFromKey(key.Key),
+			}
+			o.wantAugment(ctx, wantKey, tree.LeafToRoots(ctx, excPtr.Node))
+			progress.NumAugments = o.numAugments
+			progress.NumAugmentTrees = len(o.augmentQueue)
+			progressWriter.Set(progress)
+		} else if !handleWouldBeNoOp(key.ItemType) {
+			o.settledItemQueue.Insert(key)
+		}
 	}
-	o.itemQueue.Insert(keyAndTree{
-		TreeID: tree,
-		Key:    key,
+
+	progress.N = len(queue)
+	progressWriter.Set(progress)
+	progressWriter.Done()
+	return nil
+}
+
+type processItemStats struct {
+	textui.Portion[int]
+	NumAugments     int
+	NumFailures     int
+	NumAugmentTrees int
+}
+
+func (s processItemStats) 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)
+}
+
+// processSettledItemQueue drains o.settledItemQueue, filling o.augmentQueue and o.treeQueue.
+func (o *rebuilder) processSettledItemQueue(ctx context.Context) error {
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items")
+
+	queue := maps.Keys(o.settledItemQueue)
+	o.settledItemQueue = make(containers.Set[keyAndTree])
+	sort.Slice(queue, func(i, j int) bool {
+		return queue[i].Compare(queue[j]) < 0
+	})
+
+	var progress processItemStats
+	progress.D = len(queue)
+	progressWriter := textui.NewProgress[processItemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
+
+	type keyAndBody struct {
+		keyAndTree
+		Body btrfsitem.Item
+	}
+	itemChan := make(chan keyAndBody, textui.Tunable(300)) // average items-per-node≈100; let's have a buffer of ~3 nodes
+	grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{})
+	grp.Go("io", func(ctx context.Context) error {
+		defer close(itemChan)
+		for _, key := range queue {
+			if err := ctx.Err(); err != nil {
+				return err
+			}
+			ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key)
+			item := keyAndBody{
+				keyAndTree: key,
+				Body:       o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key),
+			}
+			select {
+			case itemChan <- item:
+			case <-ctx.Done():
+			}
+		}
+		return nil
+	})
+	grp.Go("cpu", func(ctx context.Context) error {
+		defer progressWriter.Done()
+		o.curKey.Key.OK = true
+		for item := range itemChan {
+			ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.process.item", item.keyAndTree)
+			o.curKey.TreeID = item.TreeID
+			o.curKey.Key.Val = item.Key
+			handleItem(o, ctx, 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
 	})
+	return grp.Wait()
 }
 
-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")
-	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.enqueueRetry()
-		return 0, btrfsitem.Root{}, false
-	}
-	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))
+// processAugmentQueue drains o.augmentQueue, filling o.addedItemQueue.
+func (o *rebuilder) processAugmentQueue(ctx context.Context) error {
+	ctx = dlog.WithField(ctx, "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
+		}
+		ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
+		resolvedAugments[treeID] = o.resolveTreeAugments(ctx, treeID)
+		progress.D += len(resolvedAugments[treeID])
 	}
-	switch itemBody := itemBody.(type) {
-	case *btrfsitem.Root:
-		return btrfsprim.Generation(key.Offset), *itemBody, true
-	case *btrfsitem.Error:
-		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
-		// btrfsitem.Root or btrfsitem.Error without this code also being updated.
-		panic(fmt.Errorf("should not happen: ROOT_ITEM item has unexpected type: %T", itemBody))
+	o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue)
+	o.numAugments = 0
+	o.numAugmentFailures = 0
+	runtime.GC()
+
+	progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
+	for _, treeID := range maps.SortedKeys(resolvedAugments) {
+		ctx := dlog.WithField(ctx, "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)
+			// This will call o.AddedItem as nescessary, which
+			// inserts to o.addedItemQueue.
+			o.rebuilt.Tree(ctx, treeID).AddRoot(ctx, nodeAddr)
+			progress.N++
+		}
 	}
+	progressWriter.Set(progress)
+	progressWriter.Done()
+
+	return nil
 }
 
-func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "resolve parent UUID")
-	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.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key)
-	if !ok {
-		o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key))
-	}
-	switch itemBody := itemBody.(type) {
-	case *btrfsitem.UUIDMap:
-		return itemBody.ObjID, true
-	case *btrfsitem.Error:
-		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
-		// btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated.
-		panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", itemBody))
+func (o *rebuilder) enqueueRetry() {
+	if o.curKey.Key.OK {
+		o.settledItemQueue.Insert(keyAndTree{
+			TreeID: o.curKey.TreeID,
+			Key:    o.curKey.Key.Val,
+		})
+	} else {
+		o.treeQueue.Insert(o.curKey.TreeID)
 	}
 }
 
@@ -458,7 +484,9 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob
 	wantKeys := append(
 		maps.Keys(o.augmentQueue[treeID].single),
 		maps.Keys(o.augmentQueue[treeID].multi)...)
-	sort.Strings(wantKeys)
+	sort.Slice(wantKeys, func(i, j int) bool {
+		return wantKeys[i].Compare(wantKeys[j]) < 0
+	})
 	for _, wantKey := range wantKeys {
 		list, ok := o.augmentQueue[treeID].multi[wantKey]
 		if !ok {
@@ -475,39 +503,26 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob
 	// Free some memory
 	o.augmentQueue[treeID].single = nil
 	o.augmentQueue[treeID].multi = nil
-	o.augmentQueue[treeID].keyBuf.Reset()
 
 	return ret
 }
 
 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
-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 {
+func (queue *treeAugmentQueue) has(wantKey Want) bool {
+	if queue != nil {
+		if queue.zero != nil {
+			if _, ok := queue.zero[wantKey]; ok {
 				return true
 			}
 		}
-		if treeQueue.single != nil {
-			if _, ok := treeQueue.single[wantKey]; ok {
+		if queue.single != nil {
+			if _, ok := queue.single[wantKey]; ok {
 				return true
 			}
 		}
-		if treeQueue.multi != nil {
-			if _, ok := treeQueue.multi[wantKey]; ok {
+		if queue.multi != nil {
+			if _, ok := queue.multi[wantKey]; ok {
 				return true
 			}
 		}
@@ -515,49 +530,40 @@ func (treeQueue *treeAugmentQueue) has(wantKey string) bool {
 	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.
+func (queue *treeAugmentQueue) store(wantKey Want, choices containers.Set[btrfsvol.LogicalAddr]) {
+	if len(choices) == 0 && wantKey.OffsetType > offsetExact {
+		// This wantKey is unlikely to come up again, so it's
+		// not worth the RAM of storing a negative result.
 		return
 	}
-	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{})
+		if queue.zero == nil {
+			queue.zero = make(map[Want]struct{})
 		}
-		treeQueue.zero[wantKey] = struct{}{}
+		queue.zero[wantKey] = struct{}{}
 	case 1:
-		if treeQueue.single == nil {
-			treeQueue.single = make(map[string]btrfsvol.LogicalAddr)
+		if queue.single == nil {
+			queue.single = make(map[Want]btrfsvol.LogicalAddr)
 		}
-		treeQueue.single[wantKey] = choices.TakeOne()
+		queue.single[wantKey] = choices.TakeOne()
 	default:
-		if treeQueue.multi == nil {
-			treeQueue.multi = make(map[string]containers.Set[btrfsvol.LogicalAddr])
+		if queue.multi == nil {
+			queue.multi = make(map[Want]containers.Set[btrfsvol.LogicalAddr])
 		}
-		treeQueue.multi[wantKey] = choices
+		queue.multi[wantKey] = choices
 	}
 }
 
-func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool {
-	return o.augmentQueue[treeID].has(wantKey)
+func (o *rebuilder) hasAugment(wantKey WantWithTree) bool {
+	return o.augmentQueue[wantKey.TreeID].has(wantKey.Key)
 }
 
-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)
+func (o *rebuilder) wantAugment(ctx context.Context, wantKey WantWithTree, choices containers.Set[btrfsvol.LogicalAddr]) {
+	if o.augmentQueue[wantKey.TreeID] == nil {
+		o.augmentQueue[wantKey.TreeID] = new(treeAugmentQueue)
 	}
-	o.augmentQueue[treeID].store(wantKey, choices)
+	o.augmentQueue[wantKey.TreeID].store(wantKey.Key, choices)
 	if len(choices) == 0 {
 		dlog.Error(ctx, "could not find wanted item")
 		o.numAugmentFailures++
@@ -566,372 +572,3 @@ func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wan
 		o.numAugments++
 	}
 }
-
-////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-// fsErr implements rebuildCallbacks.
-func (o *rebuilder) fsErr(ctx context.Context, e error) {
-	dlog.Errorf(ctx, "filesystem error: %v", e)
-}
-
-// 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)
-	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, 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
-	}
-
-	// check if we already have it
-
-	tgt := btrfsprim.Key{
-		ObjectID: objID,
-		ItemType: typ,
-	}
-	if key, _, ok := o.rebuilt.Tree(ctx, treeID).Items(ctx).Search(func(key btrfsprim.Key, _ keyio.ItemPtr) int {
-		key.Offset = 0
-		return tgt.Compare(key)
-	}); ok {
-		return key, true
-	}
-
-	// OK, we need to insert it
-
-	if o.hasAugment(treeID, wantKey) {
-		return btrfsprim.Key{}, false
-	}
-	wants := make(containers.Set[btrfsvol.LogicalAddr])
-	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
-		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Compare(k) },
-		func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
-			wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
-			return true
-		})
-	o.wantAugment(ctx, treeID, wantKey, wants)
-	return btrfsprim.Key{}, false
-}
-
-// wantOff implements rebuildCallbacks.
-func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) {
-	key := btrfsprim.Key{
-		ObjectID: objID,
-		ItemType: typ,
-		Offset:   off,
-	}
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
-	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, 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.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.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
-		func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Compare(k) },
-		func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
-			wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
-			return true
-		})
-	o.wantAugment(ctx, treeID, wantKey, wants)
-	return false
-}
-
-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
-	}
-
-	// check if we already have it
-
-	tgt := btrfsprim.Key{
-		ObjectID: objID,
-		ItemType: typ,
-	}
-	found := false
-	o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange(
-		func(key btrfsprim.Key, _ keyio.ItemPtr) int {
-			key.Offset = 0
-			return tgt.Compare(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.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
-		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Compare(k) },
-		func(k btrfsprim.Key, v keyio.ItemPtr) bool {
-			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.Compare(runKey) < 0:
-				return 1
-			case max.Compare(runKey) > 0:
-				return -1
-			default:
-				return 0
-			}
-		},
-		func(runKey btrfsprim.Key, runPtr keyio.ItemPtr) bool {
-			runSizeAndErr, ok := o.keyIO.Sizes[runPtr]
-			if !ok {
-				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
-			}
-			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
-		})
-}
-
-type gap struct {
-	// range is [Beg,End)
-	Beg, End uint64
-}
-
-// Compare implements containers.Ordered.
-func (a gap) Compare(b gap) int {
-	return containers.NativeCompare(a.Beg, b.Beg)
-}
-
-func (o *rebuilder) _wantRange(
-	ctx context.Context,
-	treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType,
-	beg, end uint64,
-) {
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key",
-		fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ))
-
-	if o.rebuilt.Tree(ctx, treeID) == nil {
-		o.enqueueRetry()
-		return
-	}
-
-	// Step 1: Build a listing of the gaps.
-	//
-	// Start with a gap of the whole range, then subtract each run
-	// from it.
-	gaps := new(containers.RBTree[gap])
-	gaps.Insert(gap{
-		Beg: beg,
-		End: end,
-	})
-	o._walkRange(
-		ctx,
-		o.rebuilt.Tree(ctx, treeID).Items(ctx),
-		treeID, objID, typ, beg, end,
-		func(runKey btrfsprim.Key, _ keyio.ItemPtr, runBeg, runEnd uint64) {
-			var overlappingGaps []*containers.RBNode[gap]
-			gaps.Subrange(
-				func(gap gap) int {
-					switch {
-					case gap.End <= runBeg:
-						return 1
-					case runEnd <= gap.Beg:
-						return -1
-					default:
-						return 0
-					}
-				},
-				func(node *containers.RBNode[gap]) bool {
-					overlappingGaps = append(overlappingGaps, node)
-					return true
-				})
-			if len(overlappingGaps) == 0 {
-				return
-			}
-			gapsBeg := overlappingGaps[0].Value.Beg
-			gapsEnd := overlappingGaps[len(overlappingGaps)-1].Value.End
-			for _, gap := range overlappingGaps {
-				gaps.Delete(gap)
-			}
-			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.Range(func(rbNode *containers.RBNode[gap]) bool {
-		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
-					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))
-				}
-				last = runEnd
-			})
-		if last < gap.End {
-			// log an error
-			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 true
-	})
-}
-
-// func implements rebuildCallbacks.
-//
-// interval is [beg, end)
-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))
-}
-
-// wantFileExt implements rebuildCallbacks.
-func (o *rebuilder) wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) {
-	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason)
-	o._wantRange(ctx, treeID, ino, btrfsprim.EXTENT_DATA_KEY,
-		0, uint64(size))
-}