rebuildnodes: Split rebuild.go in to separate files

3 files changed, 462 insertions, 431 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
index a088d84..902d810 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
@@ -5,7 +5,6 @@
 package rebuildnodes
 
 import (
-	"bytes"
 	"context"
 	"fmt"
 	"runtime"
@@ -19,7 +18,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"
@@ -272,66 +270,6 @@ func (o *rebuilder) enqueueRetry() {
 	}
 }
 
-func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
-	if handleWouldBeNoOp(key.ItemType) {
-		return
-	}
-	o.itemQueue.Insert(keyAndTree{
-		TreeID: tree,
-		Key:    key,
-	})
-}
-
-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
-	}
-	switch itemBody := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key).(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))
-	}
-}
-
-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
-	}
-	switch itemBody := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key).(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) 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
@@ -571,372 +509,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))
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go
new file mode 100644
index 0000000..7266777
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go
@@ -0,0 +1,75 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"context"
+	"fmt"
+
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+)
+
+func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+	if handleWouldBeNoOp(key.ItemType) {
+		return
+	}
+	o.itemQueue.Insert(keyAndTree{
+		TreeID: tree,
+		Key:    key,
+	})
+}
+
+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
+	}
+	switch itemBody := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key).(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))
+	}
+}
+
+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
+	}
+	switch itemBody := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key).(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))
+	}
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go
new file mode 100644
index 0000000..7ea9c85
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go
@@ -0,0 +1,387 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"bytes"
+	"context"
+	"fmt"
+
+	"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/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+)
+
+// 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))
+}