Move files around [ci-skip]

24 files changed, 3745 insertions, 0 deletions

diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
new file mode 100644
index 0000000..240c72f
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
@@ -0,0 +1,443 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsinspect
+
+import (
+	"context"
+	"io"
+
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"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/diskio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) {
+	superblock, err := fs.Superblock()
+	if err != nil {
+		dlog.Error(ctx, err)
+		return
+	}
+
+	if superblock.RootTree != 0 {
+		textui.Fprintf(out, "root tree\n")
+		printTree(ctx, out, fs, btrfsprim.ROOT_TREE_OBJECTID)
+	}
+	if superblock.ChunkTree != 0 {
+		textui.Fprintf(out, "chunk tree\n")
+		printTree(ctx, out, fs, btrfsprim.CHUNK_TREE_OBJECTID)
+	}
+	if superblock.LogTree != 0 {
+		textui.Fprintf(out, "log root tree\n")
+		printTree(ctx, out, fs, btrfsprim.TREE_LOG_OBJECTID)
+	}
+	if superblock.BlockGroupRoot != 0 {
+		textui.Fprintf(out, "block group tree\n")
+		printTree(ctx, out, fs, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
+	}
+	fs.TreeWalk(
+		ctx,
+		btrfsprim.ROOT_TREE_OBJECTID,
+		func(err *btrfstree.TreeError) {
+			dlog.Error(ctx, err)
+		},
+		btrfstree.TreeWalkHandler{
+			Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+				if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY {
+					return nil
+				}
+				treeName, ok := map[btrfsprim.ObjID]string{
+					btrfsprim.ROOT_TREE_OBJECTID:        "root",
+					btrfsprim.EXTENT_TREE_OBJECTID:      "extent",
+					btrfsprim.CHUNK_TREE_OBJECTID:       "chunk",
+					btrfsprim.DEV_TREE_OBJECTID:         "device",
+					btrfsprim.FS_TREE_OBJECTID:          "fs",
+					btrfsprim.ROOT_TREE_DIR_OBJECTID:    "directory",
+					btrfsprim.CSUM_TREE_OBJECTID:        "checksum",
+					btrfsprim.ORPHAN_OBJECTID:           "orphan",
+					btrfsprim.TREE_LOG_OBJECTID:         "log",
+					btrfsprim.TREE_LOG_FIXUP_OBJECTID:   "log fixup",
+					btrfsprim.TREE_RELOC_OBJECTID:       "reloc",
+					btrfsprim.DATA_RELOC_TREE_OBJECTID:  "data reloc",
+					btrfsprim.EXTENT_CSUM_OBJECTID:      "extent checksum",
+					btrfsprim.QUOTA_TREE_OBJECTID:       "quota",
+					btrfsprim.UUID_TREE_OBJECTID:        "uuid",
+					btrfsprim.FREE_SPACE_TREE_OBJECTID:  "free space",
+					btrfsprim.MULTIPLE_OBJECTIDS:        "multiple",
+					btrfsprim.BLOCK_GROUP_TREE_OBJECTID: "block group",
+				}[item.Key.ObjectID]
+				if !ok {
+					treeName = "file"
+				}
+				textui.Fprintf(out, "%v tree key %v \n", treeName, item.Key.Format(btrfsprim.ROOT_TREE_OBJECTID))
+				printTree(ctx, out, fs, item.Key.ObjectID)
+				return nil
+			},
+		},
+	)
+	textui.Fprintf(out, "total bytes %v\n", superblock.TotalBytes)
+	textui.Fprintf(out, "bytes used %v\n", superblock.BytesUsed)
+	textui.Fprintf(out, "uuid %v\n", superblock.FSUUID)
+}
+
+var nodeHeaderSize = binstruct.StaticSize(btrfstree.NodeHeader{})
+
+// printTree mimics btrfs-progs
+// kernel-shared/print-tree.c:btrfs_print_tree() and
+// kernel-shared/print-tree.c:btrfs_print_leaf()
+func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfsprim.ObjID) {
+	var itemOffset uint32
+	handlers := btrfstree.TreeWalkHandler{
+		Node: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error {
+			printHeaderInfo(out, nodeRef.Data)
+			itemOffset = nodeRef.Data.Size - uint32(nodeHeaderSize)
+			return nil
+		},
+		PreKeyPointer: func(path btrfstree.TreePath, item btrfstree.KeyPointer) error {
+			treeID := path[0].FromTree
+			textui.Fprintf(out, "\tkey %v block %v gen %v\n",
+				item.Key.Format(treeID),
+				item.BlockPtr,
+				item.Generation)
+			return nil
+		},
+		Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+			treeID := path[0].FromTree
+			i := path.Node(-1).FromItemIdx
+			bs, _ := binstruct.Marshal(item.Body)
+			itemSize := uint32(len(bs))
+			itemOffset -= itemSize
+			textui.Fprintf(out, "\titem %v key %v itemoff %v itemsize %v\n",
+				i,
+				item.Key.Format(treeID),
+				itemOffset,
+				itemSize)
+			switch body := item.Body.(type) {
+			case *btrfsitem.FreeSpaceHeader:
+				textui.Fprintf(out, "\t\tlocation key %v\n", body.Location.Format(treeID))
+				textui.Fprintf(out, "\t\tcache generation %v entries %v bitmaps %v\n",
+					body.Generation, body.NumEntries, body.NumBitmaps)
+			case *btrfsitem.Inode:
+				textui.Fprintf(out, ""+
+					"\t\tgeneration %v transid %v size %v nbytes %v\n"+
+					"\t\tblock group %v mode %o links %v uid %v gid %v rdev %v\n"+
+					"\t\tsequence %v flags %v\n",
+					body.Generation, body.TransID, body.Size, body.NumBytes,
+					body.BlockGroup, body.Mode, body.NLink, body.UID, body.GID, body.RDev,
+					body.Sequence, body.Flags)
+				textui.Fprintf(out, "\t\tatime %v\n", fmtTime(body.ATime))
+				textui.Fprintf(out, "\t\tctime %v\n", fmtTime(body.CTime))
+				textui.Fprintf(out, "\t\tmtime %v\n", fmtTime(body.MTime))
+				textui.Fprintf(out, "\t\totime %v\n", fmtTime(body.OTime))
+			case *btrfsitem.InodeRefs:
+				for _, ref := range body.Refs {
+					textui.Fprintf(out, "\t\tindex %v namelen %v name: %s\n",
+						ref.Index, ref.NameLen, ref.Name)
+				}
+			// case btrfsitem.INODE_EXTREF_KEY:
+			// 	// TODO
+			case *btrfsitem.DirEntry:
+				textui.Fprintf(out, "\t\tlocation key %v type %v\n",
+					body.Location.Format(treeID), body.Type)
+				textui.Fprintf(out, "\t\ttransid %v data_len %v name_len %v\n",
+					body.TransID, body.DataLen, body.NameLen)
+				textui.Fprintf(out, "\t\tname: %s\n", body.Name)
+				if len(body.Data) > 0 {
+					textui.Fprintf(out, "\t\tdata %s\n", body.Data)
+				}
+			// case btrfsitem.DIR_LOG_INDEX_KEY, btrfsitem.DIR_LOG_ITEM_KEY:
+			// 	// TODO
+			case *btrfsitem.Root:
+				textui.Fprintf(out, "\t\tgeneration %v root_dirid %v bytenr %d byte_limit %v bytes_used %v\n",
+					body.Generation, body.RootDirID, body.ByteNr, body.ByteLimit, body.BytesUsed)
+				textui.Fprintf(out, "\t\tlast_snapshot %v flags %v refs %v\n",
+					body.LastSnapshot, body.Flags, body.Refs)
+				textui.Fprintf(out, "\t\tdrop_progress key %v drop_level %v\n",
+					body.DropProgress.Format(treeID), body.DropLevel)
+				textui.Fprintf(out, "\t\tlevel %v generation_v2 %v\n",
+					body.Level, body.GenerationV2)
+				if body.Generation == body.GenerationV2 {
+					textui.Fprintf(out, "\t\tuuid %v\n", body.UUID)
+					textui.Fprintf(out, "\t\tparent_uuid %v\n", body.ParentUUID)
+					textui.Fprintf(out, "\t\treceived_uuid %v\n", body.ReceivedUUID)
+					textui.Fprintf(out, "\t\tctransid %v otransid %v stransid %v rtransid %v\n",
+						body.CTransID, body.OTransID, body.STransID, body.RTransID)
+					textui.Fprintf(out, "\t\tctime %v\n", fmtTime(body.CTime))
+					textui.Fprintf(out, "\t\totime %v\n", fmtTime(body.OTime))
+					textui.Fprintf(out, "\t\tstime %v\n", fmtTime(body.STime))
+					textui.Fprintf(out, "\t\trtime %v\n", fmtTime(body.RTime))
+				}
+			case *btrfsitem.RootRef:
+				var tag string
+				switch item.Key.ItemType {
+				case btrfsitem.ROOT_REF_KEY:
+					tag = "ref"
+				case btrfsitem.ROOT_BACKREF_KEY:
+					tag = "backref"
+				default:
+					tag = textui.Sprintf("(error: unhandled RootRef item type: %v)", item.Key.ItemType)
+				}
+				textui.Fprintf(out, "\t\troot %v key dirid %v sequence %v name %s\n",
+					tag, body.DirID, body.Sequence, body.Name)
+			case *btrfsitem.Extent:
+				textui.Fprintf(out, "\t\trefs %v gen %v flags %v\n",
+					body.Head.Refs, body.Head.Generation, body.Head.Flags)
+				if body.Head.Flags.Has(btrfsitem.EXTENT_FLAG_TREE_BLOCK) {
+					textui.Fprintf(out, "\t\ttree block key %v level %v\n",
+						body.Info.Key.Format(treeID), body.Info.Level)
+				}
+				printExtentInlineRefs(out, body.Refs)
+			case *btrfsitem.Metadata:
+				textui.Fprintf(out, "\t\trefs %v gen %v flags %v\n",
+					body.Head.Refs, body.Head.Generation, body.Head.Flags)
+				textui.Fprintf(out, "\t\ttree block skinny level %v\n", item.Key.Offset)
+				printExtentInlineRefs(out, body.Refs)
+			// case btrfsitem.EXTENT_DATA_REF_KEY:
+			// 	// TODO
+			// case btrfsitem.SHARED_DATA_REF_KEY:
+			// 	// TODO
+			case *btrfsitem.ExtentCSum:
+				start := btrfsvol.LogicalAddr(item.Key.Offset)
+				textui.Fprintf(out, "\t\trange start %d end %d length %d",
+					start, start.Add(body.Size()), body.Size())
+				sumsPerLine := slices.Max(1, len(btrfssum.CSum{})/body.ChecksumSize/2)
+
+				i := 0
+				_ = body.Walk(ctx, func(pos btrfsvol.LogicalAddr, sum btrfssum.ShortSum) error {
+					if i%sumsPerLine == 0 {
+						textui.Fprintf(out, "\n\t\t")
+					} else {
+						textui.Fprintf(out, " ")
+					}
+					textui.Fprintf(out, "[%d] 0x%x", pos, sum)
+					i++
+					return nil
+				})
+				textui.Fprintf(out, "\n")
+			case *btrfsitem.FileExtent:
+				textui.Fprintf(out, "\t\tgeneration %v type %v\n",
+					body.Generation, body.Type)
+				switch body.Type {
+				case btrfsitem.FILE_EXTENT_INLINE:
+					textui.Fprintf(out, "\t\tinline extent data size %v ram_bytes %v compression %v\n",
+						len(body.BodyInline), body.RAMBytes, body.Compression)
+				case btrfsitem.FILE_EXTENT_PREALLOC:
+					textui.Fprintf(out, "\t\tprealloc data disk byte %v nr %v\n",
+						body.BodyExtent.DiskByteNr,
+						body.BodyExtent.DiskNumBytes)
+					textui.Fprintf(out, "\t\tprealloc data offset %v nr %v\n",
+						body.BodyExtent.Offset,
+						body.BodyExtent.NumBytes)
+				case btrfsitem.FILE_EXTENT_REG:
+					textui.Fprintf(out, "\t\textent data disk byte %d nr %d\n",
+						body.BodyExtent.DiskByteNr,
+						body.BodyExtent.DiskNumBytes)
+					textui.Fprintf(out, "\t\textent data offset %d nr %d ram %v\n",
+						body.BodyExtent.Offset,
+						body.BodyExtent.NumBytes,
+						body.RAMBytes)
+					textui.Fprintf(out, "\t\textent compression %v\n",
+						body.Compression)
+				default:
+					textui.Fprintf(out, "\t\t(error) unknown file extent type %v", body.Type)
+				}
+			case *btrfsitem.BlockGroup:
+				textui.Fprintf(out, "\t\tblock group used %v chunk_objectid %v flags %v\n",
+					body.Used, body.ChunkObjectID, body.Flags)
+			case *btrfsitem.FreeSpaceInfo:
+				textui.Fprintf(out, "\t\tfree space info extent count %v flags %d\n",
+					body.ExtentCount, body.Flags)
+			case *btrfsitem.FreeSpaceBitmap:
+				textui.Fprintf(out, "\t\tfree space bitmap\n")
+			case *btrfsitem.Chunk:
+				textui.Fprintf(out, "\t\tlength %d owner %d stripe_len %v type %v\n",
+					body.Head.Size, body.Head.Owner, body.Head.StripeLen, body.Head.Type)
+				textui.Fprintf(out, "\t\tio_align %v io_width %v sector_size %v\n",
+					body.Head.IOOptimalAlign, body.Head.IOOptimalWidth, body.Head.IOMinSize)
+				textui.Fprintf(out, "\t\tnum_stripes %v sub_stripes %v\n",
+					body.Head.NumStripes, body.Head.SubStripes)
+				for i, stripe := range body.Stripes {
+					textui.Fprintf(out, "\t\t\tstripe %v devid %d offset %d\n",
+						i, stripe.DeviceID, stripe.Offset)
+					textui.Fprintf(out, "\t\t\tdev_uuid %v\n",
+						stripe.DeviceUUID)
+				}
+			case *btrfsitem.Dev:
+				textui.Fprintf(out, ""+
+					"\t\tdevid %d total_bytes %v bytes_used %v\n"+
+					"\t\tio_align %v io_width %v sector_size %v type %v\n"+
+					"\t\tgeneration %v start_offset %v dev_group %v\n"+
+					"\t\tseek_speed %v bandwidth %v\n"+
+					"\t\tuuid %v\n"+
+					"\t\tfsid %v\n",
+					body.DevID, body.NumBytes, body.NumBytesUsed,
+					body.IOOptimalAlign, body.IOOptimalWidth, body.IOMinSize, body.Type,
+					body.Generation, body.StartOffset, body.DevGroup,
+					body.SeekSpeed, body.Bandwidth,
+					body.DevUUID,
+					body.FSUUID)
+			case *btrfsitem.DevExtent:
+				textui.Fprintf(out, ""+
+					"\t\tdev extent chunk_tree %d\n"+
+					"\t\tchunk_objectid %v chunk_offset %d length %d\n"+
+					"\t\tchunk_tree_uuid %v\n",
+					body.ChunkTree, body.ChunkObjectID, body.ChunkOffset, body.Length,
+					body.ChunkTreeUUID)
+			case *btrfsitem.QGroupStatus:
+				textui.Fprintf(out, ""+
+					"\t\tversion %v generation %v flags %v scan %d\n",
+					body.Version, body.Generation, body.Flags, body.RescanProgress)
+			case *btrfsitem.QGroupInfo:
+				textui.Fprintf(out, ""+
+					"\t\tgeneration %v\n"+
+					"\t\treferenced %d referenced_compressed %d\n"+
+					"\t\texclusive %d exclusive_compressed %d\n",
+					body.Generation,
+					body.ReferencedBytes, body.ReferencedBytesCompressed,
+					body.ExclusiveBytes, body.ExclusiveBytesCompressed)
+			case *btrfsitem.QGroupLimit:
+				textui.Fprintf(out, ""+
+					"\t\tflags %x\n"+
+					"\t\tmax_referenced %d max_exclusive %d\n"+
+					"\t\trsv_referenced %d rsv_exclusive %d\n",
+					uint64(body.Flags),
+					body.MaxReferenced, body.MaxExclusive,
+					body.RsvReferenced, body.RsvExclusive)
+			case *btrfsitem.UUIDMap:
+				textui.Fprintf(out, "\t\tsubvol_id %d\n", body.ObjID)
+			// case btrfsitem.STRING_ITEM_KEY:
+			// 	// TODO
+			case *btrfsitem.DevStats:
+				textui.Fprintf(out, "\t\tpersistent item objectid %v offset %v\n",
+					item.Key.ObjectID.Format(treeID), item.Key.Offset)
+				switch item.Key.ObjectID {
+				case btrfsprim.DEV_STATS_OBJECTID:
+					textui.Fprintf(out, "\t\tdevice stats\n")
+					textui.Fprintf(out, "\t\twrite_errs %v read_errs %v flush_errs %v corruption_errs %v generation %v\n",
+						body.Values[btrfsitem.DEV_STAT_WRITE_ERRS],
+						body.Values[btrfsitem.DEV_STAT_READ_ERRS],
+						body.Values[btrfsitem.DEV_STAT_FLUSH_ERRS],
+						body.Values[btrfsitem.DEV_STAT_CORRUPTION_ERRS],
+						body.Values[btrfsitem.DEV_STAT_GENERATION_ERRS])
+				default:
+					textui.Fprintf(out, "\t\tunknown persistent item objectid %v\n", item.Key.ObjectID)
+				}
+			// case btrfsitem.TEMPORARY_ITEM_KEY:
+			// 	// TODO
+			case *btrfsitem.Empty:
+				switch item.Key.ItemType {
+				case btrfsitem.ORPHAN_ITEM_KEY: // 48
+					textui.Fprintf(out, "\t\torphan item\n")
+				case btrfsitem.TREE_BLOCK_REF_KEY: // 176
+					textui.Fprintf(out, "\t\ttree block backref\n")
+				case btrfsitem.SHARED_BLOCK_REF_KEY: // 182
+					textui.Fprintf(out, "\t\tshared block backref\n")
+				case btrfsitem.FREE_SPACE_EXTENT_KEY: // 199
+					textui.Fprintf(out, "\t\tfree space extent\n")
+				case btrfsitem.QGROUP_RELATION_KEY: // 246
+					// do nothing
+				// case btrfsitem.EXTENT_REF_V0_KEY:
+				// 	textui.Fprintf(out, "\t\textent ref v0 (deprecated)\n")
+				// case btrfsitem.CSUM_ITEM_KEY:
+				// 	textui.Fprintf(out, "\t\tcsum item\n")
+				default:
+					textui.Fprintf(out, "\t\t(error) unhandled empty item type: %v\n", item.Key.ItemType)
+				}
+			case *btrfsitem.Error:
+				textui.Fprintf(out, "\t\t(error) error item: %v\n", body.Err)
+			default:
+				textui.Fprintf(out, "\t\t(error) unhandled item type: %T\n", body)
+			}
+			return nil
+		},
+	}
+	handlers.BadItem = handlers.Item
+	fs.TreeWalk(
+		ctx,
+		treeID,
+		func(err *btrfstree.TreeError) {
+			dlog.Error(ctx, err)
+		},
+		handlers,
+	)
+}
+
+// printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info()
+func printHeaderInfo(out io.Writer, node btrfstree.Node) {
+	var typename string
+	if node.Head.Level > 0 { // internal node
+		typename = "node"
+		textui.Fprintf(out, "node %v level %v items %v free space %v",
+			node.Head.Addr,
+			node.Head.Level,
+			node.Head.NumItems,
+			node.MaxItems()-node.Head.NumItems)
+	} else { // leaf node
+		typename = "leaf"
+		textui.Fprintf(out, "leaf %d items %v free space %v",
+			node.Head.Addr,
+			node.Head.NumItems,
+			node.LeafFreeSpace())
+	}
+	textui.Fprintf(out, " generation %v owner %v\n",
+		node.Head.Generation,
+		node.Head.Owner)
+
+	textui.Fprintf(out, "%v %d flags %v backref revision %v\n",
+		typename,
+		node.Head.Addr,
+		node.Head.Flags,
+		node.Head.BackrefRev)
+
+	textui.Fprintf(out, "checksum stored %v\n", node.Head.Checksum.Fmt(node.ChecksumType))
+	if calcSum, err := node.CalculateChecksum(); err != nil {
+		textui.Fprintf(out, "checksum calced %v\n", err)
+	} else {
+		textui.Fprintf(out, "checksum calced %v\n", calcSum.Fmt(node.ChecksumType))
+	}
+
+	textui.Fprintf(out, "fs uuid %v\n", node.Head.MetadataUUID)
+	textui.Fprintf(out, "chunk uuid %v\n", node.Head.ChunkTreeUUID)
+}
+
+// printExtentInlineRefs mimics part of btrfs-progs kernel-shared/print-tree.c:print_extent_item()
+func printExtentInlineRefs(out io.Writer, refs []btrfsitem.ExtentInlineRef) {
+	for _, ref := range refs {
+		switch subitem := ref.Body.(type) {
+		case nil:
+			switch ref.Type {
+			case btrfsitem.TREE_BLOCK_REF_KEY:
+				textui.Fprintf(out, "\t\ttree block backref root %v\n",
+					btrfsprim.ObjID(ref.Offset))
+			case btrfsitem.SHARED_BLOCK_REF_KEY:
+				textui.Fprintf(out, "\t\tshared block backref parent %v\n",
+					ref.Offset)
+			default:
+				textui.Fprintf(out, "\t\t(error) unexpected empty sub-item type: %v\n", ref.Type)
+			}
+		case *btrfsitem.ExtentDataRef:
+			textui.Fprintf(out, "\t\textent data backref root %v objectid %v offset %v count %v\n",
+				subitem.Root, subitem.ObjectID, subitem.Offset, subitem.Count)
+		case *btrfsitem.SharedDataRef:
+			textui.Fprintf(out, "\t\tshared data backref parent %v count %v\n",
+				ref.Offset, subitem.Count)
+		default:
+			textui.Fprintf(out, "\t\t(error) unexpected sub-item type: %T\n", subitem)
+		}
+	}
+}
+
+func fmtTime(t btrfsprim.Time) string {
+	return textui.Sprintf("%v.%v (%v)",
+		t.Sec, t.NSec, t.ToStd().Format("2006-01-02 15:04:05"))
+}
diff --git a/cmd/btrfs-rec/inspect/mount/mount.go b/cmd/btrfs-rec/inspect/mount/mount.go
new file mode 100644
index 0000000..0ac8497
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/mount/mount.go
@@ -0,0 +1,482 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsinspect
+
+import (
+	"context"
+	"errors"
+	"fmt"
+	"io"
+	"path/filepath"
+	"sync"
+	"sync/atomic"
+	"syscall"
+
+	"git.lukeshu.com/go/typedsync"
+	"github.com/datawire/dlib/dcontext"
+	"github.com/datawire/dlib/dgroup"
+	"github.com/datawire/dlib/dlog"
+	"github.com/jacobsa/fuse"
+	"github.com/jacobsa/fuse/fuseops"
+	"github.com/jacobsa/fuse/fuseutil"
+
+	"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/btrfsprogs/btrfsutil"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+)
+
+func MountRO(ctx context.Context, fs *btrfs.FS, mountpoint string, noChecksums bool) error {
+	pvs := fs.LV.PhysicalVolumes()
+	if len(pvs) < 1 {
+		return errors.New("no devices")
+	}
+
+	deviceName := pvs[maps.SortedKeys(pvs)[0]].Name()
+	if abs, err := filepath.Abs(deviceName); err == nil {
+		deviceName = abs
+	}
+
+	rootSubvol := &subvolume{
+		Subvolume: btrfs.Subvolume{
+			FS:          btrfsutil.NewBrokenTrees(ctx, fs),
+			TreeID:      btrfsprim.FS_TREE_OBJECTID,
+			NoChecksums: noChecksums,
+		},
+		DeviceName: deviceName,
+		Mountpoint: mountpoint,
+	}
+	return rootSubvol.Run(ctx)
+}
+
+func fuseMount(ctx context.Context, mountpoint string, server fuse.Server, cfg *fuse.MountConfig) error {
+	grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{
+		// Allow mountHandle.Join() returning to cause the
+		// "unmount" goroutine to quit.
+		ShutdownOnNonError: true,
+	})
+	mounted := uint32(1)
+	grp.Go("unmount", func(ctx context.Context) error {
+		<-ctx.Done()
+		var err error
+		var gotNil bool
+		// Keep retrying, because the FS might be busy.
+		for atomic.LoadUint32(&mounted) != 0 {
+			if _err := fuse.Unmount(mountpoint); _err == nil {
+				gotNil = true
+			} else if !gotNil {
+				err = _err
+			}
+		}
+		if gotNil {
+			return nil
+		}
+		return err
+	})
+	grp.Go("mount", func(ctx context.Context) error {
+		defer atomic.StoreUint32(&mounted, 0)
+
+		cfg.OpContext = ctx
+		cfg.ErrorLogger = dlog.StdLogger(ctx, dlog.LogLevelError)
+		cfg.DebugLogger = dlog.StdLogger(ctx, dlog.LogLevelDebug)
+
+		mountHandle, err := fuse.Mount(mountpoint, server, cfg)
+		if err != nil {
+			return err
+		}
+		dlog.Infof(ctx, "mounted %q", mountpoint)
+		return mountHandle.Join(dcontext.HardContext(ctx))
+	})
+	return grp.Wait()
+}
+
+type dirState struct {
+	Dir *btrfs.Dir
+}
+
+type fileState struct {
+	File *btrfs.File
+}
+
+type subvolume struct {
+	btrfs.Subvolume
+	DeviceName string
+	Mountpoint string
+
+	fuseutil.NotImplementedFileSystem
+	lastHandle  uint64
+	dirHandles  typedsync.Map[fuseops.HandleID, *dirState]
+	fileHandles typedsync.Map[fuseops.HandleID, *fileState]
+
+	subvolMu sync.Mutex
+	subvols  containers.Set[string]
+	grp      *dgroup.Group
+}
+
+func (sv *subvolume) Run(ctx context.Context) error {
+	sv.grp = dgroup.NewGroup(ctx, dgroup.GroupConfig{})
+	sv.grp.Go("self", func(ctx context.Context) error {
+		cfg := &fuse.MountConfig{
+			FSName:  sv.DeviceName,
+			Subtype: "btrfs",
+
+			ReadOnly: true,
+
+			Options: map[string]string{
+				"allow_other": "",
+			},
+		}
+		return fuseMount(ctx, sv.Mountpoint, fuseutil.NewFileSystemServer(sv), cfg)
+	})
+	return sv.grp.Wait()
+}
+
+func (sv *subvolume) newHandle() fuseops.HandleID {
+	return fuseops.HandleID(atomic.AddUint64(&sv.lastHandle, 1))
+}
+
+func inodeItemToFUSE(itemBody btrfsitem.Inode) fuseops.InodeAttributes {
+	return fuseops.InodeAttributes{
+		Size:  uint64(itemBody.Size),
+		Nlink: uint32(itemBody.NLink),
+		Mode:  uint32(itemBody.Mode),
+		// RDev: itemBody.Rdev, // jacobsa/fuse doesn't expose rdev
+		Atime: itemBody.ATime.ToStd(),
+		Mtime: itemBody.MTime.ToStd(),
+		Ctime: itemBody.CTime.ToStd(),
+		// Crtime: itemBody.OTime,
+		Uid: uint32(itemBody.UID),
+		Gid: uint32(itemBody.GID),
+	}
+}
+
+func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error) {
+	val, err = sv.Subvolume.LoadDir(inode)
+	if val != nil {
+		haveSubvolumes := false
+		for _, index := range maps.SortedKeys(val.ChildrenByIndex) {
+			entry := val.ChildrenByIndex[index]
+			if entry.Location.ItemType == btrfsitem.ROOT_ITEM_KEY {
+				haveSubvolumes = true
+				break
+			}
+		}
+		if haveSubvolumes {
+			abspath, _err := val.AbsPath()
+			if _err != nil {
+				return val, err
+			}
+			sv.subvolMu.Lock()
+			for _, index := range maps.SortedKeys(val.ChildrenByIndex) {
+				entry := val.ChildrenByIndex[index]
+				if entry.Location.ItemType != btrfsitem.ROOT_ITEM_KEY {
+					continue
+				}
+				if sv.subvols == nil {
+					sv.subvols = make(containers.Set[string])
+				}
+				subMountpoint := filepath.Join(abspath, string(entry.Name))
+				if !sv.subvols.Has(subMountpoint) {
+					sv.subvols.Insert(subMountpoint)
+					workerName := fmt.Sprintf("%d-%s", val.Inode, filepath.Base(subMountpoint))
+					sv.grp.Go(workerName, func(ctx context.Context) error {
+						subSv := &subvolume{
+							Subvolume: btrfs.Subvolume{
+								FS:          sv.FS,
+								TreeID:      entry.Location.ObjectID,
+								NoChecksums: sv.NoChecksums,
+							},
+							DeviceName: sv.DeviceName,
+							Mountpoint: filepath.Join(sv.Mountpoint, subMountpoint[1:]),
+						}
+						return subSv.Run(ctx)
+					})
+				}
+			}
+			sv.subvolMu.Unlock()
+		}
+	}
+	return val, err
+}
+
+func (sv *subvolume) StatFS(_ context.Context, op *fuseops.StatFSOp) error {
+	// See linux.git/fs/btrfs/super.c:btrfs_statfs()
+	sb, err := sv.FS.Superblock()
+	if err != nil {
+		return err
+	}
+
+	op.IoSize = sb.SectorSize
+	op.BlockSize = sb.SectorSize
+	op.Blocks = sb.TotalBytes / uint64(sb.SectorSize) // TODO: adjust for RAID type
+	// op.BlocksFree = TODO
+
+	// btrfs doesn't have a fixed number of inodes
+	op.Inodes = 0
+	op.InodesFree = 0
+
+	// jacobsa/fuse doesn't expose namelen, instead hard-coding it
+	// to 255.  Which is fine by us, because that's what it is for
+	// btrfs.
+
+	return nil
+}
+
+func (sv *subvolume) LookUpInode(_ context.Context, op *fuseops.LookUpInodeOp) error {
+	if op.Parent == fuseops.RootInodeID {
+		parent, err := sv.GetRootInode()
+		if err != nil {
+			return err
+		}
+		op.Parent = fuseops.InodeID(parent)
+	}
+
+	dir, err := sv.LoadDir(btrfsprim.ObjID(op.Parent))
+	if err != nil {
+		return err
+	}
+	entry, ok := dir.ChildrenByName[op.Name]
+	if !ok {
+		return syscall.ENOENT
+	}
+	if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY {
+		// Subvolume
+		//
+		// Because each subvolume has its own pool of inodes
+		// (as in 2 different subvolumes can have files with
+		// te same inode number), so to represent that to FUSE
+		// we need to have this be a full separate mountpoint.
+		//
+		// I'd want to return EIO or EINTR or something here,
+		// but both the FUSE userspace tools and the kernel
+		// itself stat the mountpoint before mounting it, so
+		// we've got to return something bogus here to let
+		// that mount happen.
+		op.Entry = fuseops.ChildInodeEntry{
+			Child: 2, // an inode number that a real file will never have
+			Attributes: fuseops.InodeAttributes{
+				Nlink: 1,
+				Mode:  uint32(btrfsitem.ModeFmtDir | 0o700), //nolint:gomnd // TODO
+			},
+		}
+		return nil
+	}
+	bareInode, err := sv.LoadBareInode(entry.Location.ObjectID)
+	if err != nil {
+		return err
+	}
+	op.Entry = fuseops.ChildInodeEntry{
+		Child:      fuseops.InodeID(entry.Location.ObjectID),
+		Generation: fuseops.GenerationNumber(bareInode.InodeItem.Sequence),
+		Attributes: inodeItemToFUSE(*bareInode.InodeItem),
+	}
+	return nil
+}
+
+func (sv *subvolume) GetInodeAttributes(_ context.Context, op *fuseops.GetInodeAttributesOp) error {
+	if op.Inode == fuseops.RootInodeID {
+		inode, err := sv.GetRootInode()
+		if err != nil {
+			return err
+		}
+		op.Inode = fuseops.InodeID(inode)
+	}
+
+	bareInode, err := sv.LoadBareInode(btrfsprim.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+
+	op.Attributes = inodeItemToFUSE(*bareInode.InodeItem)
+	return nil
+}
+
+func (sv *subvolume) OpenDir(_ context.Context, op *fuseops.OpenDirOp) error {
+	if op.Inode == fuseops.RootInodeID {
+		inode, err := sv.GetRootInode()
+		if err != nil {
+			return err
+		}
+		op.Inode = fuseops.InodeID(inode)
+	}
+
+	dir, err := sv.LoadDir(btrfsprim.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+	handle := sv.newHandle()
+	sv.dirHandles.Store(handle, &dirState{
+		Dir: dir,
+	})
+	op.Handle = handle
+	return nil
+}
+
+func (sv *subvolume) ReadDir(_ context.Context, op *fuseops.ReadDirOp) error {
+	state, ok := sv.dirHandles.Load(op.Handle)
+	if !ok {
+		return syscall.EBADF
+	}
+	origOffset := op.Offset
+	for _, index := range maps.SortedKeys(state.Dir.ChildrenByIndex) {
+		if index < uint64(origOffset) {
+			continue
+		}
+		entry := state.Dir.ChildrenByIndex[index]
+		n := fuseutil.WriteDirent(op.Dst[op.BytesRead:], fuseutil.Dirent{
+			Offset: fuseops.DirOffset(index + 1),
+			Inode:  fuseops.InodeID(entry.Location.ObjectID),
+			Name:   string(entry.Name),
+			Type: map[btrfsitem.FileType]fuseutil.DirentType{
+				btrfsitem.FT_UNKNOWN:  fuseutil.DT_Unknown,
+				btrfsitem.FT_REG_FILE: fuseutil.DT_File,
+				btrfsitem.FT_DIR:      fuseutil.DT_Directory,
+				btrfsitem.FT_CHRDEV:   fuseutil.DT_Char,
+				btrfsitem.FT_BLKDEV:   fuseutil.DT_Block,
+				btrfsitem.FT_FIFO:     fuseutil.DT_FIFO,
+				btrfsitem.FT_SOCK:     fuseutil.DT_Socket,
+				btrfsitem.FT_SYMLINK:  fuseutil.DT_Link,
+			}[entry.Type],
+		})
+		if n == 0 {
+			break
+		}
+		op.BytesRead += n
+	}
+	return nil
+}
+
+func (sv *subvolume) ReleaseDirHandle(_ context.Context, op *fuseops.ReleaseDirHandleOp) error {
+	_, ok := sv.dirHandles.LoadAndDelete(op.Handle)
+	if !ok {
+		return syscall.EBADF
+	}
+	return nil
+}
+
+func (sv *subvolume) OpenFile(_ context.Context, op *fuseops.OpenFileOp) error {
+	file, err := sv.LoadFile(btrfsprim.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+	handle := sv.newHandle()
+	sv.fileHandles.Store(handle, &fileState{
+		File: file,
+	})
+	op.Handle = handle
+	op.KeepPageCache = true
+	return nil
+}
+
+func (sv *subvolume) ReadFile(_ context.Context, op *fuseops.ReadFileOp) error {
+	state, ok := sv.fileHandles.Load(op.Handle)
+	if !ok {
+		return syscall.EBADF
+	}
+
+	var dat []byte
+	if op.Dst != nil {
+		size := slices.Min(int64(len(op.Dst)), op.Size)
+		dat = op.Dst[:size]
+	} else {
+		dat = make([]byte, op.Size)
+		op.Data = [][]byte{dat}
+	}
+
+	var err error
+	op.BytesRead, err = state.File.ReadAt(dat, op.Offset)
+	if errors.Is(err, io.EOF) {
+		err = nil
+	}
+
+	return err
+}
+
+func (sv *subvolume) ReleaseFileHandle(_ context.Context, op *fuseops.ReleaseFileHandleOp) error {
+	_, ok := sv.fileHandles.LoadAndDelete(op.Handle)
+	if !ok {
+		return syscall.EBADF
+	}
+	return nil
+}
+
+func (sv *subvolume) ReadSymlink(_ context.Context, op *fuseops.ReadSymlinkOp) error {
+	file, err := sv.LoadFile(btrfsprim.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+	reader := io.NewSectionReader(file, 0, file.InodeItem.Size)
+	tgt, err := io.ReadAll(reader)
+	if err != nil {
+		return err
+	}
+	op.Target = string(tgt)
+	return nil
+}
+
+func (sv *subvolume) ListXattr(_ context.Context, op *fuseops.ListXattrOp) error {
+	if op.Inode == fuseops.RootInodeID {
+		inode, err := sv.GetRootInode()
+		if err != nil {
+			return err
+		}
+		op.Inode = fuseops.InodeID(inode)
+	}
+
+	fullInode, err := sv.LoadFullInode(btrfsprim.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+
+	size := 0
+	for name := range fullInode.XAttrs {
+		size += len(name) + 1
+	}
+	if len(op.Dst) < size {
+		return syscall.ERANGE
+	}
+
+	op.BytesRead = size
+	n := 0
+	for _, name := range maps.SortedKeys(fullInode.XAttrs) {
+		n += copy(op.Dst[n:], name)
+		op.Dst[n] = 0
+		n++
+	}
+	return nil
+}
+
+func (sv *subvolume) GetXattr(_ context.Context, op *fuseops.GetXattrOp) error {
+	if op.Inode == fuseops.RootInodeID {
+		inode, err := sv.GetRootInode()
+		if err != nil {
+			return err
+		}
+		op.Inode = fuseops.InodeID(inode)
+	}
+
+	fullInode, err := sv.LoadFullInode(btrfsprim.ObjID(op.Inode))
+	if err != nil {
+		return err
+	}
+
+	val, ok := fullInode.XAttrs[op.Name]
+	if !ok {
+		return syscall.ENODATA
+	}
+
+	if len(op.Dst) < len(val) {
+		return syscall.ERANGE
+	}
+
+	op.BytesRead = len(val)
+	copy(op.Dst, val)
+	return nil
+}
+
+func (sv *subvolume) Destroy() {}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/kmp.go b/cmd/btrfs-rec/inspect/rebuildmappings/kmp.go
new file mode 100644
index 0000000..20772ba
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/kmp.go
@@ -0,0 +1,113 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"errors"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+type kmpPattern[K ~int64 | ~int, V comparable] interface {
+	PatLen() K
+	// Get the value at 'pos' in the sequence.  Positions start at
+	// 0 and increment naturally.  It is invalid to call Get(pos)
+	// with a pos that is >= Len().  If there is a gap/wildcard at
+	// pos, ok is false.
+	PatGet(pos K) (v V, ok bool)
+}
+
+func kmpSelfEq[K ~int64 | ~int, V comparable](s kmpPattern[K, V], aI K, bI K) bool {
+	aV, aOK := s.PatGet(aI)
+	bV, bOK := s.PatGet(bI)
+	if !aOK || !bOK {
+		return true
+	}
+	return aV == bV
+}
+
+// buildKMPTable takes the string 'substr', and returns a table such
+// that 'table[matchLen-1]' is the largest value 'val' for which 'val < matchLen' and
+// 'substr[:val] == substr[matchLen-val:matchLen]'.
+func buildKMPTable[K ~int64 | ~int, V comparable](substr kmpPattern[K, V]) []K {
+	substrLen := substr.PatLen()
+
+	table := make([]K, substrLen)
+	for j := K(0); j < substrLen; j++ {
+		if j == 0 {
+			// First entry must always be 0 (in order to
+			// satisfy 'val < matchLen').
+			continue
+		}
+		val := table[j-1]
+		// not a match; go back
+		for val > 0 && !kmpSelfEq(substr, j, val) {
+			val = table[val-1]
+		}
+		// is a match; go forward
+		if kmpSelfEq(substr, val, j) {
+			val++
+		}
+		table[j] = val
+	}
+	return table
+}
+
+func kmpEq[K ~int64 | ~int, V comparable](aV V, bS kmpPattern[K, V], bI K) bool {
+	bV, ok := bS.PatGet(bI)
+	if !ok {
+		return true
+	}
+	return aV == bV
+}
+
+// indexAll returns the starting-position of all possibly-overlapping
+// occurrences of 'substr' in the 'str' sequence.
+//
+// Will hop around in 'substr', but will only get the natural sequence
+// [0...) in order from 'str'.
+//
+// Will panic if the length of 'substr' is 0.
+//
+// The 'substr' may include wildcard characters by returning
+// ErrWildcard for a position.
+//
+// Uses the Knuth-Morris-Pratt algorithm.
+func indexAll[K ~int64 | ~int, V comparable](str diskio.Sequence[K, V], substr kmpPattern[K, V]) []K {
+	table := buildKMPTable(substr)
+	substrLen := K(len(table))
+	if substrLen == 0 {
+		panic(errors.New("rebuildmappings.IndexAll: empty substring"))
+	}
+
+	var matches []K
+	var curMatchBeg K
+	var curMatchLen K
+
+	strLen := str.SeqLen()
+	for pos := K(0); pos < strLen; pos++ {
+		chr := str.SeqGet(pos)
+
+		// Consider 'chr'
+		for curMatchLen > 0 && !kmpEq(chr, substr, curMatchLen) { // shorten the match
+			overlap := table[curMatchLen-1]
+			curMatchBeg += curMatchLen - overlap
+			curMatchLen = overlap
+		}
+		if kmpEq(chr, substr, curMatchLen) { // lengthen the match
+			if curMatchLen == 0 {
+				curMatchBeg = pos
+			}
+			curMatchLen++
+			if curMatchLen == substrLen {
+				matches = append(matches, curMatchBeg)
+				overlap := table[curMatchLen-1]
+				curMatchBeg += curMatchLen - overlap
+				curMatchLen = overlap
+			}
+		}
+	}
+	return matches
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/kmp_test.go b/cmd/btrfs-rec/inspect/rebuildmappings/kmp_test.go
new file mode 100644
index 0000000..acec9b8
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/kmp_test.go
@@ -0,0 +1,126 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"bytes"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+type bytePattern[K ~int64 | ~int] []byte
+
+var _ kmpPattern[int, byte] = bytePattern[int]{}
+
+// PatLen implements kmpPattern.
+func (s bytePattern[K]) PatLen() K {
+	return K(len(s))
+}
+
+// PatGet implements kmpPattern.
+func (s bytePattern[K]) PatGet(i K) (byte, bool) {
+	chr := s[int(i)]
+	if chr == '.' {
+		return 0, false
+	}
+	return chr, true
+}
+
+func TestBuildKMPTable(t *testing.T) {
+	t.Parallel()
+	substr := bytePattern[int64]([]byte("ababaa"))
+	table := buildKMPTable[int64, byte](substr)
+	require.Equal(t,
+		[]int64{0, 0, 1, 2, 3, 1},
+		table)
+	for j, val := range table {
+		matchLen := j + 1
+		assert.Equalf(t, substr[:val], substr[matchLen-int(val):matchLen],
+			"for table[%d]=%d", j, val)
+	}
+}
+
+func FuzzBuildKMPTable(f *testing.F) {
+	f.Add([]byte("ababaa"))
+	f.Fuzz(func(t *testing.T, substr []byte) {
+		table := buildKMPTable[int64, byte](bytePattern[int64](substr))
+		require.Equal(t, len(substr), len(table), "length")
+		for j, val := range table {
+			matchLen := j + 1
+			assert.Equalf(t, substr[:val], substr[matchLen-int(val):matchLen],
+				"for table[%d]=%d", j, val)
+		}
+	})
+}
+
+func NaiveIndexAll(str, substr []byte) []int64 {
+	var matches []int64
+	for i := range str {
+		if bytes.HasPrefix(str[i:], substr) {
+			matches = append(matches, int64(i))
+		}
+	}
+	return matches
+}
+
+func FuzzIndexAll(f *testing.F) {
+	f.Fuzz(func(t *testing.T, str, substr []byte) {
+		if len(substr) == 0 {
+			t.Skip()
+		}
+		t.Logf("str   =%q", str)
+		t.Logf("substr=%q", substr)
+		exp := NaiveIndexAll(str, substr)
+		act := indexAll[int64, byte](
+			diskio.SliceSequence[int64, byte](str),
+			bytePattern[int64](substr))
+		assert.Equal(t, exp, act)
+	})
+}
+
+func TestKMPWildcard(t *testing.T) {
+	t.Parallel()
+	type testcase struct {
+		InStr      string
+		InSubstr   string
+		ExpMatches []int64
+	}
+	testcases := map[string]testcase{
+		"trivial-bar": {
+			InStr:      "foo_bar",
+			InSubstr:   "foo.ba.",
+			ExpMatches: []int64{0},
+		},
+		"trival-baz": {
+			InStr:      "foo-baz",
+			InSubstr:   "foo.ba.",
+			ExpMatches: []int64{0},
+		},
+		"suffix": {
+			InStr:      "foobarbaz",
+			InSubstr:   "...baz",
+			ExpMatches: []int64{3},
+		},
+		"overlap": {
+			InStr:      "foobarbar",
+			InSubstr:   "...bar",
+			ExpMatches: []int64{0, 3},
+		},
+	}
+	for tcName, tc := range testcases {
+		tc := tc
+		t.Run(tcName, func(t *testing.T) {
+			t.Parallel()
+			matches := indexAll[int64, byte](
+				diskio.StringSequence[int64](tc.InStr),
+				bytePattern[int64](tc.InSubstr))
+			assert.Equal(t, tc.ExpMatches, matches)
+		})
+	}
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go
new file mode 100644
index 0000000..cdf5e5a
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go
@@ -0,0 +1,222 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"fmt"
+
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+func getNodeSize(fs *btrfs.FS) (btrfsvol.AddrDelta, error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return 0, err
+	}
+	return btrfsvol.AddrDelta(sb.NodeSize), nil
+}
+
+func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) error {
+	nodeSize, err := getNodeSize(fs)
+	if err != nil {
+		return err
+	}
+
+	var numChunks, numDevExts, numBlockGroups, numNodes int
+	devIDs := maps.SortedKeys(scanResults)
+	devices := fs.LV.PhysicalVolumes()
+	for _, devID := range devIDs {
+		if _, ok := devices[devID]; !ok {
+			return fmt.Errorf("device ID %v mentioned in scan results is not part of the filesystem", devID)
+		}
+		devResults := scanResults[devID]
+		numChunks += len(devResults.FoundChunks)
+		numDevExts += len(devResults.FoundDevExtents)
+		numBlockGroups += len(devResults.FoundBlockGroups)
+		for _, paddrs := range devResults.FoundNodes {
+			numNodes += len(paddrs)
+		}
+	}
+	dlog.Infof(ctx, "plan: 1/6 process %d chunks", numChunks)
+	dlog.Infof(ctx, "plan: 2/6 process %d device extents", numDevExts)
+	dlog.Infof(ctx, "plan: 3/6 process %d nodes", numNodes)
+	dlog.Infof(ctx, "plan: 4/6 process %d block groups", numBlockGroups)
+	dlog.Infof(ctx, "plan: 5/6 search for block groups in checksum map (exact)")
+	dlog.Infof(ctx, "plan: 6/6 search for block groups in checksum map (fuzzy)")
+
+	_ctx := ctx
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "1/6")
+	dlog.Infof(_ctx, "1/6: Processing %d chunks...", numChunks)
+	for _, devID := range devIDs {
+		devResults := scanResults[devID]
+		for _, chunk := range devResults.FoundChunks {
+			for _, mapping := range chunk.Chunk.Mappings(chunk.Key) {
+				if err := fs.LV.AddMapping(mapping); err != nil {
+					dlog.Errorf(ctx, "error: adding chunk: %v", err)
+				}
+			}
+		}
+	}
+	dlog.Info(_ctx, "... done processing chunks")
+
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "2/6")
+	dlog.Infof(_ctx, "2/6: Processing %d device extents...", numDevExts)
+	for _, devID := range devIDs {
+		devResults := scanResults[devID]
+		for _, ext := range devResults.FoundDevExtents {
+			if err := fs.LV.AddMapping(ext.DevExt.Mapping(ext.Key)); err != nil {
+				dlog.Errorf(ctx, "error: adding devext: %v", err)
+			}
+		}
+	}
+	dlog.Info(_ctx, "... done processing device extents")
+
+	// Do the nodes "last" to avoid bloating the mappings table
+	// too much.  (Because nodes are numerous and small, while the
+	// others are few and large; so it is likely that many of the
+	// nodes will be subsumed by other things.)
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "3/6")
+	dlog.Infof(_ctx, "3/6: Processing %d nodes...", numNodes)
+	for _, devID := range devIDs {
+		devResults := scanResults[devID]
+		// Sort them so that progress numbers are predictable.
+		for _, laddr := range maps.SortedKeys(devResults.FoundNodes) {
+			for _, paddr := range devResults.FoundNodes[laddr] {
+				if err := fs.LV.AddMapping(btrfsvol.Mapping{
+					LAddr: laddr,
+					PAddr: btrfsvol.QualifiedPhysicalAddr{
+						Dev:  devID,
+						Addr: paddr,
+					},
+					Size:       nodeSize,
+					SizeLocked: false,
+				}); err != nil {
+					dlog.Errorf(ctx, "error: adding node ident: %v", err)
+				}
+			}
+		}
+	}
+	dlog.Info(_ctx, "... done processing nodes")
+
+	// Use block groups to add missing flags (and as a hint to
+	// combine node entries).
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "4/6")
+	dlog.Infof(_ctx, "4/6: Processing %d block groups...", numBlockGroups)
+	// First dedup them, because they change for allocations and
+	// CoW means that they'll bounce around a lot, so you likely
+	// have oodles of duplicates?
+	bgs, err := DedupBlockGroups(scanResults)
+	if err != nil {
+		return err
+	}
+	dlog.Infof(ctx, "... de-duplicated to %d block groups", len(bgs))
+	for _, bgLAddr := range maps.SortedKeys(bgs) {
+		bg := bgs[bgLAddr]
+		otherLAddr, otherPAddr := fs.LV.ResolveAny(bg.LAddr, bg.Size)
+		if otherLAddr < 0 || otherPAddr.Addr < 0 {
+			dlog.Errorf(ctx, "error: could not pair blockgroup laddr=%v (size=%v flags=%v) with a mapping",
+				bg.LAddr, bg.Size, bg.Flags)
+			continue
+		}
+
+		offsetWithinChunk := otherLAddr.Sub(bg.LAddr)
+		mapping := btrfsvol.Mapping{
+			LAddr:      bg.LAddr,
+			PAddr:      otherPAddr.Add(-offsetWithinChunk),
+			Size:       bg.Size,
+			SizeLocked: true,
+			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
+				OK:  true,
+				Val: bg.Flags,
+			},
+		}
+		if err := fs.LV.AddMapping(mapping); err != nil {
+			dlog.Errorf(ctx, "error: adding flags from blockgroup: %v", err)
+			continue
+		}
+		delete(bgs, bgLAddr)
+	}
+	dlog.Info(_ctx, "... done processing block groups")
+
+	// More than once, I've been tempted to get rid of this exact-search step and just have the fuzzy-search step.
+	// After all, looking at the timestamps in the log, it's faster per blockgroup!  For some background, the big-O
+	// for each (per blockgroup) looks like:
+	//
+	//  - exact-search: O(bgSize+physicalBlocks)
+	//  - fuzzy-search: O(bgSize*physicalBlocks) worst-case; O(bgSize*log(physicalBlocks)) expected
+	//
+	// The fuzzy-search is only fast because the exact-search is so good at getting `physicalBlocks` down.
+	// Empirically: if I remove the exact-search step, then the fuzzy-match step is more than an order of magnitude
+	// slower.
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "5/6")
+	dlog.Infof(_ctx, "5/6: Searching for %d block groups in checksum map (exact)...", len(bgs))
+	physicalSums := ExtractPhysicalSums(scanResults)
+	logicalSums := ExtractLogicalSums(ctx, scanResults)
+	if err := matchBlockGroupSums(ctx, fs, bgs, physicalSums, logicalSums); err != nil {
+		return err
+	}
+	dlog.Info(ctx, "... done searching for exact block groups")
+
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "6/6")
+	dlog.Infof(_ctx, "6/6: Searching for %d block groups in checksum map (fuzzy)...", len(bgs))
+	if err := fuzzyMatchBlockGroupSums(ctx, fs, bgs, physicalSums, logicalSums); err != nil {
+		return err
+	}
+	dlog.Info(_ctx, "... done searching for fuzzy block groups")
+
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "report")
+	dlog.Info(_ctx, "report:")
+
+	unmappedPhysicalRegions := ListUnmappedPhysicalRegions(fs)
+	var unmappedPhysical btrfsvol.AddrDelta
+	var numUnmappedPhysical int
+	for _, devRegions := range unmappedPhysicalRegions {
+		numUnmappedPhysical += len(devRegions)
+		for _, region := range devRegions {
+			unmappedPhysical += region.End.Sub(region.Beg)
+		}
+	}
+	dlog.Infof(ctx, "... %d of unmapped physical space (across %d regions)", textui.IEC(unmappedPhysical, "B"), numUnmappedPhysical)
+
+	unmappedLogicalRegions := ListUnmappedLogicalRegions(fs, logicalSums)
+	var unmappedLogical btrfsvol.AddrDelta
+	for _, region := range unmappedLogicalRegions {
+		unmappedLogical += region.Size()
+	}
+	dlog.Infof(ctx, "... %d of unmapped summed logical space (across %d regions)", textui.IEC(unmappedLogical, "B"), len(unmappedLogicalRegions))
+
+	var unmappedBlockGroups btrfsvol.AddrDelta
+	for _, bg := range bgs {
+		unmappedBlockGroups += bg.Size
+	}
+	dlog.Infof(ctx, "... %d of unmapped block groups (across %d groups)", textui.IEC(unmappedBlockGroups, "B"), len(bgs))
+
+	dlog.Info(_ctx, "detailed report:")
+	for _, devID := range maps.SortedKeys(unmappedPhysicalRegions) {
+		for _, region := range unmappedPhysicalRegions[devID] {
+			dlog.Infof(ctx, "... unmapped physical region: dev=%v beg=%v end=%v (size=%v)",
+				devID, region.Beg, region.End, region.End.Sub(region.Beg))
+		}
+	}
+	for _, region := range unmappedLogicalRegions {
+		dlog.Infof(ctx, "... umapped summed logical region:  beg=%v end=%v (size=%v)",
+			region.Addr, region.Addr.Add(region.Size()), region.Size())
+	}
+	for _, laddr := range maps.SortedKeys(bgs) {
+		bg := bgs[laddr]
+		dlog.Infof(ctx, "... umapped block group:            beg=%v end=%v (size=%v) flags=%v",
+			bg.LAddr, bg.LAddr.Add(bg.Size), bg.Size, bg.Flags)
+	}
+
+	return nil
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go
new file mode 100644
index 0000000..0e2d5a0
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go
@@ -0,0 +1,58 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"fmt"
+	"sort"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+)
+
+type BlockGroup struct {
+	LAddr btrfsvol.LogicalAddr
+	Size  btrfsvol.AddrDelta
+	Flags btrfsvol.BlockGroupFlags
+}
+
+func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) {
+	// Dedup
+	bgsSet := make(containers.Set[BlockGroup])
+	for _, devResults := range scanResults {
+		for _, bg := range devResults.FoundBlockGroups {
+			bgsSet.Insert(BlockGroup{
+				LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID),
+				Size:  btrfsvol.AddrDelta(bg.Key.Offset),
+				Flags: bg.BG.Flags,
+			})
+		}
+	}
+
+	// Sort
+	bgsOrdered := maps.Keys(bgsSet)
+	sort.Slice(bgsOrdered, func(i, j int) bool {
+		return bgsOrdered[i].LAddr < bgsOrdered[j].LAddr
+	})
+
+	// Sanity check
+	var pos btrfsvol.LogicalAddr
+	for _, bg := range bgsOrdered {
+		if bg.LAddr < pos || bg.Size < 0 {
+			return nil, fmt.Errorf("found block groups are inconsistent")
+		}
+		pos = bg.LAddr.Add(bg.Size)
+	}
+
+	// Return.  We return a map instead of a slice in order to
+	// facilitate easy deletes.
+	bgsMap := make(map[btrfsvol.LogicalAddr]BlockGroup, len(bgsSet))
+	for bg := range bgsSet {
+		bgsMap[bg.LAddr] = bg
+	}
+	return bgsMap, nil
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go
new file mode 100644
index 0000000..a3e724e
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go
@@ -0,0 +1,78 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+
+	"github.com/datawire/dlib/dlog"
+	"golang.org/x/text/number"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"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/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+)
+
+func matchBlockGroupSums(ctx context.Context,
+	fs *btrfs.FS,
+	blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
+	physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
+	logicalSums SumRunWithGaps[btrfsvol.LogicalAddr],
+) error {
+	regions := ListUnmappedPhysicalRegions(fs)
+	numBlockgroups := len(blockgroups)
+	for i, bgLAddr := range maps.SortedKeys(blockgroups) {
+		blockgroup := blockgroups[bgLAddr]
+		bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size)
+		if len(bgRun.Runs) == 0 {
+			dlog.Errorf(ctx, "(%v/%v) blockgroup[laddr=%v] can't be matched because it has 0 runs",
+				i+1, numBlockgroups, bgLAddr)
+			continue
+		}
+
+		var matches []btrfsvol.QualifiedPhysicalAddr
+		if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
+			rawMatches := indexAll[int, btrfssum.ShortSum](region, bgRun)
+			for _, match := range rawMatches {
+				matches = append(matches, btrfsvol.QualifiedPhysicalAddr{
+					Dev:  devID,
+					Addr: region.Addr + (btrfsvol.PhysicalAddr(match) * btrfssum.BlockSize),
+				})
+			}
+			return nil
+		}); err != nil {
+			return err
+		}
+
+		lvl := dlog.LogLevelError
+		if len(matches) == 1 {
+			lvl = dlog.LogLevelInfo
+		}
+		dlog.Logf(ctx, lvl, "(%v/%v) blockgroup[laddr=%v] has %v matches based on %v coverage from %v runs",
+			i+1, numBlockgroups, bgLAddr, len(matches), number.Percent(bgRun.PctFull()), len(bgRun.Runs))
+		if len(matches) != 1 {
+			continue
+		}
+
+		mapping := btrfsvol.Mapping{
+			LAddr:      blockgroup.LAddr,
+			PAddr:      matches[0],
+			Size:       blockgroup.Size,
+			SizeLocked: true,
+			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
+				OK:  true,
+				Val: blockgroup.Flags,
+			},
+		}
+		if err := fs.LV.AddMapping(mapping); err != nil {
+			dlog.Errorf(ctx, "error: %v", err)
+			continue
+		}
+		delete(blockgroups, bgLAddr)
+	}
+	return nil
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go
new file mode 100644
index 0000000..4724c12
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go
@@ -0,0 +1,159 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"sort"
+
+	"github.com/datawire/dlib/dlog"
+	"golang.org/x/text/number"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"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/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+var minFuzzyPct = textui.Tunable(0.5)
+
+type fuzzyRecord struct {
+	PAddr btrfsvol.QualifiedPhysicalAddr
+	N     int
+}
+
+func (a fuzzyRecord) Compare(b fuzzyRecord) int {
+	switch {
+	case a.N < b.N:
+		return -1
+	case a.N > b.N:
+		return 1
+	default:
+		return 0
+	}
+}
+
+func fuzzyMatchBlockGroupSums(ctx context.Context,
+	fs *btrfs.FS,
+	blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
+	physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
+	logicalSums SumRunWithGaps[btrfsvol.LogicalAddr],
+) error {
+	_ctx := ctx
+
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.substep", "indexing")
+	dlog.Info(ctx, "Indexing physical regions...") // O(m)
+	regions := ListUnmappedPhysicalRegions(fs)
+	physicalIndex := make(map[btrfssum.ShortSum][]btrfsvol.QualifiedPhysicalAddr)
+	if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
+		return region.Walk(ctx, func(paddr btrfsvol.PhysicalAddr, sum btrfssum.ShortSum) error {
+			physicalIndex[sum] = append(physicalIndex[sum], btrfsvol.QualifiedPhysicalAddr{
+				Dev:  devID,
+				Addr: paddr,
+			})
+			return nil
+		})
+	}); err != nil {
+		return err
+	}
+	dlog.Info(ctx, "... done indexing")
+
+	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.substep", "searching")
+	dlog.Info(ctx, "Searching...")
+	numBlockgroups := len(blockgroups)
+	for i, bgLAddr := range maps.SortedKeys(blockgroups) {
+		blockgroup := blockgroups[bgLAddr]
+		bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size)
+
+		d := bgRun.PatLen()
+		matches := make(map[btrfsvol.QualifiedPhysicalAddr]int)
+		if err := bgRun.Walk(ctx, func(laddr btrfsvol.LogicalAddr, sum btrfssum.ShortSum) error { // O(n*…
+			off := laddr.Sub(bgRun.Addr)
+			for _, paddr := range physicalIndex[sum] { // …log(m)) expected but …m) worst
+				key := btrfsvol.QualifiedPhysicalAddr{
+					Dev:  paddr.Dev,
+					Addr: paddr.Addr.Add(-off),
+				}
+				matches[key]++
+			}
+			return nil
+		}); err != nil {
+			return err
+		}
+
+		best := lowestN[fuzzyRecord]{N: 2}
+		for paddr, n := range matches { // O(m)
+			best.Insert(fuzzyRecord{
+				PAddr: paddr,
+				N:     d - n,
+			})
+		}
+
+		var apply bool
+		var matchesStr string
+		switch len(best.Dat) {
+		case 0: // can happen if there are no sums in the run
+			matchesStr = ""
+		case 1: // not sure how this can happen, but whatev
+			pct := float64(d-best.Dat[0].N) / float64(d)
+			matchesStr = textui.Sprintf("%v", number.Percent(pct))
+			apply = pct > minFuzzyPct
+		case 2:
+			pct := float64(d-best.Dat[0].N) / float64(d)
+			pct2 := float64(d-best.Dat[1].N) / float64(d)
+			matchesStr = textui.Sprintf("best=%v secondbest=%v", number.Percent(pct), number.Percent(pct2))
+			apply = pct > minFuzzyPct && pct2 < minFuzzyPct
+		}
+		lvl := dlog.LogLevelError
+		if apply {
+			lvl = dlog.LogLevelInfo
+		}
+		dlog.Logf(ctx, lvl, "(%v/%v) blockgroup[laddr=%v] matches=[%s]; bestpossible=%v (based on %v runs)",
+			i+1, numBlockgroups, bgLAddr, matchesStr, number.Percent(bgRun.PctFull()), len(bgRun.Runs))
+		if !apply {
+			continue
+		}
+
+		mapping := btrfsvol.Mapping{
+			LAddr:      blockgroup.LAddr,
+			PAddr:      best.Dat[0].PAddr,
+			Size:       blockgroup.Size,
+			SizeLocked: true,
+			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
+				OK:  true,
+				Val: blockgroup.Flags,
+			},
+		}
+		if err := fs.LV.AddMapping(mapping); err != nil {
+			dlog.Errorf(ctx, "error: %v", err)
+			continue
+		}
+		delete(blockgroups, bgLAddr)
+	}
+	dlog.Info(ctx, "done searching")
+
+	return nil
+}
+
+type lowestN[T containers.Ordered[T]] struct {
+	N   int
+	Dat []T
+}
+
+func (l *lowestN[T]) Insert(v T) {
+	switch {
+	case len(l.Dat) < l.N:
+		l.Dat = append(l.Dat, v)
+	case v.Compare(l.Dat[0]) < 0:
+		l.Dat[0] = v
+	default:
+		return
+	}
+	sort.Slice(l.Dat, func(i, j int) bool {
+		return l.Dat[i].Compare(l.Dat[j]) < 0
+	})
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go
new file mode 100644
index 0000000..7c02d05
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go
@@ -0,0 +1,249 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"sort"
+	"strings"
+
+	"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/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+)
+
+func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) SumRunWithGaps[btrfsvol.LogicalAddr] {
+	var records []btrfsinspect.SysExtentCSum
+	for _, devResults := range scanResults {
+		records = append(records, devResults.FoundExtentCSums...)
+	}
+	// Sort lower-generation items earlier; then sort by addr.
+	sort.Slice(records, func(i, j int) bool {
+		a, b := records[i], records[j]
+		switch {
+		case a.Generation < b.Generation:
+			return true
+		case a.Generation > b.Generation:
+			return false
+		default:
+			return a.Sums.Addr < b.Sums.Addr
+		}
+	})
+	if len(records) == 0 {
+		return SumRunWithGaps[btrfsvol.LogicalAddr]{}
+	}
+	sumSize := records[0].Sums.ChecksumSize
+
+	// Now build them in to a coherent address space.
+	//
+	// We can't just reverse-sort by generation to avoid mutations, because given
+	//
+	//	gen1 AAAAAAA
+	//      gen2    BBBBBBBB
+	//      gen3          CCCCCCC
+	//
+	// "AAAAAAA" shouldn't be present, and if we just discard "BBBBBBBB"
+	// because it conflicts with "CCCCCCC", then we would erroneously
+	// include "AAAAAAA".
+	addrspace := new(containers.RBTree[btrfsinspect.SysExtentCSum])
+	for _, newRecord := range records {
+		for {
+			conflict := addrspace.Search(func(oldRecord btrfsinspect.SysExtentCSum) int {
+				switch {
+				case newRecord.Sums.Addr.Add(newRecord.Sums.Size()) <= oldRecord.Sums.Addr:
+					// 'newRecord' is wholly to the left of 'oldRecord'.
+					return -1
+				case oldRecord.Sums.Addr.Add(oldRecord.Sums.Size()) <= newRecord.Sums.Addr:
+					// 'oldRecord' is wholly to the left of 'newRecord'.
+					return 1
+				default:
+					// There is some overlap.
+					return 0
+				}
+			})
+			if conflict == nil {
+				// We can insert it
+				addrspace.Insert(newRecord)
+				break
+			}
+			oldRecord := conflict.Value
+			if oldRecord == newRecord {
+				// Duplicates are to be expected.
+				break
+			}
+			if oldRecord.Generation < newRecord.Generation {
+				// Newer generation wins.
+				addrspace.Delete(conflict)
+				// loop around to check for more conflicts
+				continue
+			}
+			if oldRecord.Generation > newRecord.Generation {
+				// We sorted them!  This shouldn't happen.
+				panic("should not happen")
+			}
+			// Since sums are stored multiple times (RAID?), but may
+			// be split between items differently between copies, we
+			// should take the union (after verifying that they
+			// agree on the overlapping part).
+			overlapBeg := slices.Max(
+				oldRecord.Sums.Addr,
+				newRecord.Sums.Addr)
+			overlapEnd := slices.Min(
+				oldRecord.Sums.Addr.Add(oldRecord.Sums.Size()),
+				newRecord.Sums.Addr.Add(newRecord.Sums.Size()))
+
+			oldOverlapBeg := int(overlapBeg.Sub(oldRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
+			oldOverlapEnd := int(overlapEnd.Sub(oldRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
+			oldOverlap := oldRecord.Sums.Sums[oldOverlapBeg:oldOverlapEnd]
+
+			newOverlapBeg := int(overlapBeg.Sub(newRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
+			newOverlapEnd := int(overlapEnd.Sub(newRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
+			newOverlap := newRecord.Sums.Sums[newOverlapBeg:newOverlapEnd]
+
+			if oldOverlap != newOverlap {
+				dlog.Errorf(ctx, "mismatch: {gen:%v, addr:%v, size:%v} conflicts with {gen:%v, addr:%v, size:%v}",
+					oldRecord.Generation, oldRecord.Sums.Addr, oldRecord.Sums.Size(),
+					newRecord.Generation, newRecord.Sums.Addr, newRecord.Sums.Size())
+				break
+			}
+			// OK, we match, so take the union.
+			var prefix, suffix btrfssum.ShortSum
+			switch {
+			case oldRecord.Sums.Addr < overlapBeg:
+				prefix = oldRecord.Sums.Sums[:oldOverlapBeg]
+			case newRecord.Sums.Addr < overlapBeg:
+				prefix = newRecord.Sums.Sums[:newOverlapBeg]
+			}
+			switch {
+			case oldRecord.Sums.Addr.Add(oldRecord.Sums.Size()) > overlapEnd:
+				suffix = oldRecord.Sums.Sums[oldOverlapEnd:]
+			case newRecord.Sums.Addr.Add(newRecord.Sums.Size()) > overlapEnd:
+				suffix = newRecord.Sums.Sums[newOverlapEnd:]
+			}
+			unionRecord := btrfsinspect.SysExtentCSum{
+				Generation: oldRecord.Generation,
+				Sums: btrfsitem.ExtentCSum{
+					SumRun: btrfssum.SumRun[btrfsvol.LogicalAddr]{
+						ChecksumSize: oldRecord.Sums.ChecksumSize,
+						Addr:         slices.Min(oldRecord.Sums.Addr, newRecord.Sums.Addr),
+						Sums:         prefix + oldOverlap + suffix,
+					},
+				},
+			}
+			addrspace.Delete(conflict)
+			newRecord = unionRecord
+			// loop around to check for more conflicts
+		}
+	}
+
+	// Now flatten that RBTree in to a SumRunWithGaps.
+	var flattened SumRunWithGaps[btrfsvol.LogicalAddr]
+	var curAddr btrfsvol.LogicalAddr
+	var curSums strings.Builder
+	addrspace.Range(func(node *containers.RBNode[btrfsinspect.SysExtentCSum]) bool {
+		curEnd := curAddr + (btrfsvol.LogicalAddr(curSums.Len()/sumSize) * btrfssum.BlockSize)
+		if node.Value.Sums.Addr != curEnd {
+			if curSums.Len() > 0 {
+				flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
+					ChecksumSize: sumSize,
+					Addr:         curAddr,
+					Sums:         btrfssum.ShortSum(curSums.String()),
+				})
+			}
+			curAddr = node.Value.Sums.Addr
+			curSums.Reset()
+		}
+		curSums.WriteString(string(node.Value.Sums.Sums))
+		return true
+	})
+	if curSums.Len() > 0 {
+		flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
+			ChecksumSize: sumSize,
+			Addr:         curAddr,
+			Sums:         btrfssum.ShortSum(curSums.String()),
+		})
+	}
+	flattened.Addr = flattened.Runs[0].Addr
+	last := flattened.Runs[len(flattened.Runs)-1]
+	end := last.Addr.Add(last.Size())
+	flattened.Size = end.Sub(flattened.Addr)
+
+	return flattened
+}
+
+func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums SumRunWithGaps[btrfsvol.LogicalAddr]) []btrfssum.SumRun[btrfsvol.LogicalAddr] {
+	// There are a lot of ways this algorithm could be made
+	// faster.
+	var ret []btrfssum.SumRun[btrfsvol.LogicalAddr]
+	var cur struct {
+		Addr btrfsvol.LogicalAddr
+		Size btrfsvol.AddrDelta
+	}
+	for _, run := range logicalSums.Runs {
+		for addr := run.Addr; addr < run.Addr.Add(run.Size()); addr += btrfssum.BlockSize {
+			if _, maxlen := fs.LV.Resolve(addr); maxlen < btrfssum.BlockSize {
+				if cur.Size == 0 {
+					cur.Addr = addr
+					cur.Size = 0
+				}
+				cur.Size += btrfssum.BlockSize
+			} else if cur.Size > 0 {
+				begIdx := int(cur.Addr.Sub(run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+				lenIdx := (int(cur.Size) / btrfssum.BlockSize) * run.ChecksumSize
+				endIdx := begIdx + lenIdx
+				ret = append(ret, btrfssum.SumRun[btrfsvol.LogicalAddr]{
+					ChecksumSize: run.ChecksumSize,
+					Addr:         cur.Addr,
+					Sums:         run.Sums[begIdx:endIdx],
+				})
+				cur.Size = 0
+			}
+		}
+		if cur.Size > 0 {
+			begIdx := int(cur.Addr.Sub(run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+			lenIdx := (int(cur.Size) / btrfssum.BlockSize) * run.ChecksumSize
+			endIdx := begIdx + lenIdx
+			ret = append(ret, btrfssum.SumRun[btrfsvol.LogicalAddr]{
+				ChecksumSize: run.ChecksumSize,
+				Addr:         cur.Addr,
+				Sums:         run.Sums[begIdx:endIdx],
+			})
+			cur.Size = 0
+		}
+	}
+	return ret
+}
+
+func SumsForLogicalRegion(sums SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) SumRunWithGaps[btrfsvol.LogicalAddr] {
+	runs := SumRunWithGaps[btrfsvol.LogicalAddr]{
+		Addr: beg,
+		Size: size,
+	}
+	for laddr := beg; laddr < beg.Add(size); {
+		run, next, ok := sums.RunForAddr(laddr)
+		if !ok {
+			laddr = next
+			continue
+		}
+		off := int((laddr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+		deltaAddr := slices.Min[btrfsvol.AddrDelta](
+			size-laddr.Sub(beg),
+			btrfsvol.AddrDelta((len(run.Sums)-off)/run.ChecksumSize)*btrfssum.BlockSize)
+		deltaOff := int(deltaAddr/btrfssum.BlockSize) * run.ChecksumSize
+		runs.Runs = append(runs.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
+			ChecksumSize: run.ChecksumSize,
+			Addr:         laddr,
+			Sums:         run.Sums[off : off+deltaOff],
+		})
+		laddr = laddr.Add(deltaAddr)
+	}
+	return runs
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go
new file mode 100644
index 0000000..da22fbf
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go
@@ -0,0 +1,89 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"sort"
+
+	"golang.org/x/exp/constraints"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"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"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+)
+
+func ExtractPhysicalSums(scanResults btrfsinspect.ScanDevicesResult) map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr] {
+	ret := make(map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr], len(scanResults))
+	for devID, devResults := range scanResults {
+		ret[devID] = devResults.Checksums
+	}
+	return ret
+}
+
+type PhysicalRegion struct {
+	Beg, End btrfsvol.PhysicalAddr
+}
+
+func ListUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalRegion {
+	regions := make(map[btrfsvol.DeviceID][]PhysicalRegion)
+	pos := make(map[btrfsvol.DeviceID]btrfsvol.PhysicalAddr)
+	mappings := fs.LV.Mappings()
+	sort.Slice(mappings, func(i, j int) bool {
+		return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
+	})
+	for _, mapping := range mappings {
+		if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr {
+			regions[mapping.PAddr.Dev] = append(regions[mapping.PAddr.Dev], PhysicalRegion{
+				Beg: pos[mapping.PAddr.Dev],
+				End: mapping.PAddr.Addr,
+			})
+		}
+		if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr.Add(mapping.Size) {
+			pos[mapping.PAddr.Dev] = mapping.PAddr.Addr.Add(mapping.Size)
+		}
+	}
+	for devID, dev := range fs.LV.PhysicalVolumes() {
+		devSize := dev.Size()
+		if pos[devID] < devSize {
+			regions[devID] = append(regions[devID], PhysicalRegion{
+				Beg: pos[devID],
+				End: devSize,
+			})
+		}
+	}
+	return regions
+}
+
+func roundUp[T constraints.Integer](x, multiple T) T {
+	return ((x + multiple - 1) / multiple) * multiple
+}
+
+func WalkUnmappedPhysicalRegions(ctx context.Context,
+	physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
+	gaps map[btrfsvol.DeviceID][]PhysicalRegion,
+	fn func(btrfsvol.DeviceID, btrfssum.SumRun[btrfsvol.PhysicalAddr]) error,
+) error {
+	for _, devID := range maps.SortedKeys(gaps) {
+		for _, gap := range gaps[devID] {
+			if err := ctx.Err(); err != nil {
+				return err
+			}
+			begAddr := roundUp(gap.Beg, btrfssum.BlockSize)
+			begOff := int(begAddr/btrfssum.BlockSize) * physicalSums[devID].ChecksumSize
+			endOff := int(gap.End/btrfssum.BlockSize) * physicalSums[devID].ChecksumSize
+			if err := fn(devID, btrfssum.SumRun[btrfsvol.PhysicalAddr]{
+				ChecksumSize: physicalSums[devID].ChecksumSize,
+				Addr:         begAddr,
+				Sums:         physicalSums[devID].Sums[begOff:endOff],
+			}); err != nil {
+				return err
+			}
+		}
+	}
+	return nil
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/scan.go b/cmd/btrfs-rec/inspect/rebuildmappings/scan.go
new file mode 100644
index 0000000..d54be71
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/scan.go
@@ -0,0 +1,260 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsinspect
+
+import (
+	"context"
+	"errors"
+	"fmt"
+	"strings"
+	"sync"
+	"time"
+
+	"github.com/datawire/dlib/dgroup"
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"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/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+type ScanDevicesResult map[btrfsvol.DeviceID]ScanOneDeviceResult
+
+func ScanDevices(ctx context.Context, fs *btrfs.FS) (ScanDevicesResult, error) {
+	grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{})
+	var mu sync.Mutex
+	result := make(map[btrfsvol.DeviceID]ScanOneDeviceResult)
+	for id, dev := range fs.LV.PhysicalVolumes() {
+		id := id
+		dev := dev
+		grp.Go(fmt.Sprintf("dev-%d", id), func(ctx context.Context) error {
+			sb, err := dev.Superblock()
+			if err != nil {
+				return err
+			}
+			devResult, err := ScanOneDevice(ctx, dev, *sb)
+			if err != nil {
+				return err
+			}
+			mu.Lock()
+			result[id] = devResult
+			mu.Unlock()
+			return nil
+		})
+	}
+	if err := grp.Wait(); err != nil {
+		return nil, err
+	}
+	return result, nil
+}
+
+type ScanOneDeviceResult struct {
+	Checksums        btrfssum.SumRun[btrfsvol.PhysicalAddr]
+	FoundNodes       map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr
+	FoundChunks      []btrfstree.SysChunk
+	FoundBlockGroups []SysBlockGroup
+	FoundDevExtents  []SysDevExtent
+	FoundExtentCSums []SysExtentCSum
+}
+
+type SysBlockGroup struct {
+	Key btrfsprim.Key
+	BG  btrfsitem.BlockGroup
+}
+
+type SysDevExtent struct {
+	Key    btrfsprim.Key
+	DevExt btrfsitem.DevExtent
+}
+
+type SysExtentCSum struct {
+	Generation btrfsprim.Generation
+	Sums       btrfsitem.ExtentCSum
+}
+
+// Compare implements containers.Ordered.
+func (a SysExtentCSum) Compare(b SysExtentCSum) int {
+	return containers.NativeCompare(a.Sums.Addr, b.Sums.Addr)
+}
+
+type scanStats struct {
+	textui.Portion[btrfsvol.PhysicalAddr]
+
+	NumFoundNodes       int
+	NumFoundChunks      int
+	NumFoundBlockGroups int
+	NumFoundDevExtents  int
+	NumFoundExtentCSums int
+}
+
+func (s scanStats) String() string {
+	return textui.Sprintf("scanned %v (found: %v nodes, %v chunks, %v block groups, %v dev extents, %v sum items)",
+		s.Portion,
+		s.NumFoundNodes,
+		s.NumFoundChunks,
+		s.NumFoundBlockGroups,
+		s.NumFoundDevExtents,
+		s.NumFoundExtentCSums)
+}
+
+var sbSize = btrfsvol.PhysicalAddr(binstruct.StaticSize(btrfstree.Superblock{}))
+
+// ScanOneDevice mostly mimics btrfs-progs
+// cmds/rescue-chunk-recover.c:scan_one_device().
+func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblock) (ScanOneDeviceResult, error) {
+	ctx = dlog.WithField(ctx, "btrfsinspect.scandevices.dev", dev.Name())
+
+	result := ScanOneDeviceResult{
+		FoundNodes: make(map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr),
+	}
+
+	devSize := dev.Size()
+	if sb.NodeSize < sb.SectorSize {
+		return result, fmt.Errorf("node_size(%v) < sector_size(%v)",
+			sb.NodeSize, sb.SectorSize)
+	}
+	if sb.SectorSize != btrfssum.BlockSize {
+		// TODO: probably handle this?
+		return result, fmt.Errorf("sector_size(%v) != btrfssum.BlockSize",
+			sb.SectorSize)
+	}
+	alg := sb.ChecksumType
+	csumSize := alg.Size()
+	numSums := int(devSize / btrfssum.BlockSize)
+	var sums strings.Builder
+	sums.Grow(numSums * csumSize)
+
+	progressWriter := textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	progress := func(pos btrfsvol.PhysicalAddr) {
+		progressWriter.Set(scanStats{
+			Portion: textui.Portion[btrfsvol.PhysicalAddr]{
+				N: pos,
+				D: devSize,
+			},
+			NumFoundNodes:       len(result.FoundNodes),
+			NumFoundChunks:      len(result.FoundChunks),
+			NumFoundBlockGroups: len(result.FoundBlockGroups),
+			NumFoundDevExtents:  len(result.FoundDevExtents),
+			NumFoundExtentCSums: len(result.FoundExtentCSums),
+		})
+	}
+
+	var minNextNode btrfsvol.PhysicalAddr
+	for i := 0; i < numSums; i++ {
+		if ctx.Err() != nil {
+			return result, ctx.Err()
+		}
+		pos := btrfsvol.PhysicalAddr(i * btrfssum.BlockSize)
+		progress(pos)
+
+		sum, err := btrfs.ChecksumPhysical(dev, alg, pos)
+		if err != nil {
+			return result, err
+		}
+		sums.Write(sum[:csumSize])
+
+		checkForNode := pos >= minNextNode && pos+btrfsvol.PhysicalAddr(sb.NodeSize) <= devSize
+		if checkForNode {
+			for _, sbAddr := range btrfs.SuperblockAddrs {
+				if sbAddr <= pos && pos < sbAddr+sbSize {
+					checkForNode = false
+					break
+				}
+			}
+		}
+
+		if checkForNode {
+			nodeRef, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, btrfstree.NodeExpectations{})
+			if err != nil {
+				if !errors.Is(err, btrfstree.ErrNotANode) {
+					dlog.Errorf(ctx, "error: %v", err)
+				}
+			} else {
+				result.FoundNodes[nodeRef.Data.Head.Addr] = append(result.FoundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr)
+				for i, item := range nodeRef.Data.BodyLeaf {
+					switch item.Key.ItemType {
+					case btrfsitem.CHUNK_ITEM_KEY:
+						switch itemBody := item.Body.(type) {
+						case *btrfsitem.Chunk:
+							dlog.Tracef(ctx, "node@%v: item %v: found chunk",
+								nodeRef.Addr, i)
+							result.FoundChunks = append(result.FoundChunks, btrfstree.SysChunk{
+								Key:   item.Key,
+								Chunk: *itemBody,
+							})
+						case *btrfsitem.Error:
+							dlog.Errorf(ctx, "node@%v: item %v: error: malformed CHUNK_ITEM: %v",
+								nodeRef.Addr, i, itemBody.Err)
+						default:
+							panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody))
+						}
+					case btrfsitem.BLOCK_GROUP_ITEM_KEY:
+						switch itemBody := item.Body.(type) {
+						case *btrfsitem.BlockGroup:
+							dlog.Tracef(ctx, "node@%v: item %v: found block group",
+								nodeRef.Addr, i)
+							result.FoundBlockGroups = append(result.FoundBlockGroups, SysBlockGroup{
+								Key: item.Key,
+								BG:  *itemBody,
+							})
+						case *btrfsitem.Error:
+							dlog.Errorf(ctx, "node@%v: item %v: error: malformed BLOCK_GROUP_ITEM: %v",
+								nodeRef.Addr, i, itemBody.Err)
+						default:
+							panic(fmt.Errorf("should not happen: BLOCK_GROUP_ITEM has unexpected item type: %T", itemBody))
+						}
+					case btrfsitem.DEV_EXTENT_KEY:
+						switch itemBody := item.Body.(type) {
+						case *btrfsitem.DevExtent:
+							dlog.Tracef(ctx, "node@%v: item %v: found dev extent",
+								nodeRef.Addr, i)
+							result.FoundDevExtents = append(result.FoundDevExtents, SysDevExtent{
+								Key:    item.Key,
+								DevExt: *itemBody,
+							})
+						case *btrfsitem.Error:
+							dlog.Errorf(ctx, "node@%v: item %v: error: malformed DEV_EXTENT: %v",
+								nodeRef.Addr, i, itemBody.Err)
+						default:
+							panic(fmt.Errorf("should not happen: DEV_EXTENT has unexpected item type: %T", itemBody))
+						}
+					case btrfsitem.EXTENT_CSUM_KEY:
+						switch itemBody := item.Body.(type) {
+						case *btrfsitem.ExtentCSum:
+							dlog.Tracef(ctx, "node@%v: item %v: found csums",
+								nodeRef.Addr, i)
+							result.FoundExtentCSums = append(result.FoundExtentCSums, SysExtentCSum{
+								Generation: nodeRef.Data.Head.Generation,
+								Sums:       *itemBody,
+							})
+						case *btrfsitem.Error:
+							dlog.Errorf(ctx, "node@%v: item %v: error: malformed is EXTENT_CSUM: %v",
+								nodeRef.Addr, i, itemBody.Err)
+						default:
+							panic(fmt.Errorf("should not happen: EXTENT_CSUM has unexpected item type: %T", itemBody))
+						}
+					}
+				}
+				minNextNode = pos + btrfsvol.PhysicalAddr(sb.NodeSize)
+			}
+			btrfstree.FreeNodeRef(nodeRef)
+		}
+	}
+	progress(devSize)
+	progressWriter.Done()
+
+	result.Checksums = btrfssum.SumRun[btrfsvol.PhysicalAddr]{
+		ChecksumSize: csumSize,
+		Sums:         btrfssum.ShortSum(sums.String()),
+	}
+
+	return result, nil
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go b/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go
new file mode 100644
index 0000000..f79e2be
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go
@@ -0,0 +1,167 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"fmt"
+	"io"
+	"math"
+
+	"git.lukeshu.com/go/lowmemjson"
+
+	"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/slices"
+)
+
+type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct {
+	// Store the start address and size, in order to facilitate
+	// leading and trailing gaps.
+	Addr Addr
+	Size btrfsvol.AddrDelta
+
+	Runs []btrfssum.SumRun[Addr]
+}
+
+var (
+	_ lowmemjson.Encodable = SumRunWithGaps[btrfsvol.LogicalAddr]{}
+	_ lowmemjson.Decodable = (*SumRunWithGaps[btrfsvol.LogicalAddr])(nil)
+)
+
+// PatLen implements kmpPattern[int, ShortSum].
+func (sg SumRunWithGaps[Addr]) PatLen() int {
+	return int(sg.Size / btrfssum.BlockSize)
+}
+
+func (sg SumRunWithGaps[Addr]) PctFull() float64 {
+	total := sg.PatLen()
+	var full int
+	for _, run := range sg.Runs {
+		full += run.SeqLen()
+	}
+	return float64(full) / float64(total)
+}
+
+func (sg SumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Addr, bool) {
+	for _, run := range sg.Runs {
+		if run.Addr > addr {
+			return btrfssum.SumRun[Addr]{}, run.Addr, false
+		}
+		if run.Addr.Add(run.Size()) <= addr {
+			continue
+		}
+		return run, 0, true
+	}
+	return btrfssum.SumRun[Addr]{}, math.MaxInt64, false
+}
+
+func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) {
+	if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
+		return "", false
+	}
+	runIdx, ok := slices.Search(sg.Runs, func(run btrfssum.SumRun[Addr]) int {
+		switch {
+		case addr < run.Addr:
+			return -1
+		case addr >= run.Addr.Add(run.Size()):
+			return 1
+		default:
+			return 0
+		}
+	})
+	if !ok {
+		return "", false
+	}
+	run := sg.Runs[runIdx]
+	off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+	return run.Sums[off : off+run.ChecksumSize], true
+}
+
+func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error {
+	for _, run := range sg.Runs {
+		if err := run.Walk(ctx, fn); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
+// PatGet implements kmpPattern[int, ShortSum].
+func (sg SumRunWithGaps[Addr]) PatGet(sumIdx int) (btrfssum.ShortSum, bool) {
+	addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfssum.BlockSize)
+	return sg.SumForAddr(addr)
+}
+
+func (sg SumRunWithGaps[Addr]) EncodeJSON(w io.Writer) error {
+	if _, err := fmt.Fprintf(w, `{"Addr":%d,"Size":%d,"Runs":[`, sg.Addr, sg.Size); err != nil {
+		return err
+	}
+	cur := sg.Addr
+	for i, run := range sg.Runs {
+		if i > 0 {
+			if _, err := w.Write([]byte{','}); err != nil {
+				return err
+			}
+		}
+		switch {
+		case run.Addr < cur:
+			return fmt.Errorf("invalid %T: addr went backwards: %v < %v", sg, run.Addr, cur)
+		case run.Addr > cur:
+			if _, err := fmt.Fprintf(w, `{"Gap":%d},`, run.Addr.Sub(cur)); err != nil {
+				return err
+			}
+			fallthrough
+		default:
+			if err := lowmemjson.NewEncoder(w).Encode(run); err != nil {
+				return err
+			}
+			cur = run.Addr.Add(run.Size())
+		}
+	}
+	end := sg.Addr.Add(sg.Size)
+	switch {
+	case end < cur:
+		return fmt.Errorf("invalid %T: addr went backwards: %v < %v", sg, end, cur)
+	case end > cur:
+		if _, err := fmt.Fprintf(w, `,{"Gap":%d}`, end.Sub(cur)); err != nil {
+			return err
+		}
+	}
+	if _, err := w.Write([]byte("]}")); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (sg *SumRunWithGaps[Addr]) DecodeJSON(r io.RuneScanner) error {
+	*sg = SumRunWithGaps[Addr]{}
+	var name string
+	return lowmemjson.DecodeObject(r,
+		func(r io.RuneScanner) error {
+			return lowmemjson.NewDecoder(r).Decode(&name)
+		},
+		func(r io.RuneScanner) error {
+			switch name {
+			case "Addr":
+				return lowmemjson.NewDecoder(r).Decode(&sg.Addr)
+			case "Size":
+				return lowmemjson.NewDecoder(r).Decode(&sg.Size)
+			case "Runs":
+				return lowmemjson.DecodeArray(r, func(r io.RuneScanner) error {
+					var run btrfssum.SumRun[Addr]
+					if err := lowmemjson.NewDecoder(r).Decode(&run); err != nil {
+						return err
+					}
+					if run.ChecksumSize > 0 {
+						sg.Runs = append(sg.Runs, run)
+					}
+					return nil
+				})
+			default:
+				return fmt.Errorf("unknown key %q", name)
+			}
+		})
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
new file mode 100644
index 0000000..9d14adf
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("0")
+[]byte("1")
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600
new file mode 100644
index 0000000..269f061
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("0")
+[]byte("0")
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60
new file mode 100644
index 0000000..b8f1562
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("0")
+[]byte("")
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738
new file mode 100644
index 0000000..be67506
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("\xde\xdb!")
+[]byte("\xde\xdb")
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d
new file mode 100644
index 0000000..c3bfa37
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("\x10\x10\x15")
+[]byte("\x10\x15")
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
new file mode 100644
index 0000000..cf334a0
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
@@ -0,0 +1,583 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"context"
+	"fmt"
+	"runtime"
+	"sort"
+	"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/btrfstree"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees"
+	"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/textui"
+)
+
+type keyAndTree struct {
+	btrfsprim.Key
+	TreeID btrfsprim.ObjID
+}
+
+func (a keyAndTree) Compare(b keyAndTree) int {
+	if d := containers.NativeCompare(a.TreeID, b.TreeID); d != 0 {
+		return d
+	}
+	return a.Key.Compare(b.Key)
+}
+
+func (o keyAndTree) String() string {
+	return fmt.Sprintf("tree=%v key=%v", o.TreeID, o.Key)
+}
+
+type rebuilder struct {
+	sb    btrfstree.Superblock
+	graph graph.Graph
+	keyIO *keyio.Handle
+
+	rebuilt *btrees.RebuiltForrest
+
+	curKey struct {
+		TreeID btrfsprim.ObjID
+		Key    containers.Optional[btrfsprim.Key]
+	}
+	treeQueue          containers.Set[btrfsprim.ObjID]
+	retryItemQueue     map[btrfsprim.ObjID]containers.Set[keyAndTree]
+	addedItemQueue     containers.Set[keyAndTree]
+	settledItemQueue   containers.Set[keyAndTree]
+	augmentQueue       map[btrfsprim.ObjID]*treeAugmentQueue
+	numAugments        int
+	numAugmentFailures int
+}
+
+type treeAugmentQueue struct {
+	zero   map[Want]struct{}
+	single map[Want]btrfsvol.LogicalAddr
+	multi  map[Want]containers.Set[btrfsvol.LogicalAddr]
+}
+
+type Rebuilder interface {
+	Rebuild(context.Context) error
+	ListRoots(context.Context) 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
+	}
+
+	o := &rebuilder{
+		sb:    sb,
+		graph: nodeGraph,
+		keyIO: keyIO,
+	}
+	o.rebuilt = btrees.NewRebuiltForrest(sb, nodeGraph, keyIO, o)
+	return o, nil
+}
+
+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")
+
+	// Initialize
+	o.retryItemQueue = make(map[btrfsprim.ObjID]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
+	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,
+	)
+
+	// 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()
+
+		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
+			}
+		} 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 (and maybe o.retryItemQueue), fill o.addedItemQueue).
+		if err := o.processAugmentQueue(ctx); err != nil {
+			return err
+		}
+		runtime.GC()
+	}
+
+	return nil
+}
+
+// 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
+}
+
+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)
+		}
+	}
+
+	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,
+			})
+			item.Body.Free()
+			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()
+}
+
+// processAugmentQueue drains o.augmentQueue (and maybe o.retryItemQueue), 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])
+	}
+	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) enqueueRetry(ifTreeID btrfsprim.ObjID) {
+	if o.curKey.Key.OK {
+		if o.retryItemQueue[ifTreeID] == nil {
+			o.retryItemQueue[ifTreeID] = make(containers.Set[keyAndTree])
+		}
+		o.retryItemQueue[ifTreeID].Insert(keyAndTree{
+			TreeID: o.curKey.TreeID,
+			Key:    o.curKey.Key.Val,
+		})
+	} else {
+		o.treeQueue.Insert(o.curKey.TreeID)
+	}
+}
+
+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]
+	// >     2: [A, C]
+	// >
+	// > legal solutions would be `[]`, `[A]`, `[B]`, `[C]`, or `[B, C]`.  It
+	// > would not be legal to return `[A, B]` or `[A, C]`.
+	//
+	// > Example 2: Given the input lists
+	// >
+	// >     1: [A, B]
+	// >     2: [A]
+	// >     3: [B]
+	// >
+	// > legal solution would be `[]`, `[A]` or `[B]`.  It would not be legal
+	// > to return `[A, B]`.
+	//
+	// The algorithm should optimize for the following goals:
+	//
+	//  - We prefer that each input list have an item in the return set.
+	//
+	//    > In Example 1, while `[]`, `[B]`, and `[C]` are permissible
+	//    > solutions, they are not optimal, because one or both of the input
+	//    > lists are not represented.
+	//    >
+	//    > It may be the case that it is not possible to represent all lists
+	//    > in the result; in Example 2, either list 2 or list 3 must be
+	//    > unrepresented.
+	//
+	//  - Each item has a non-negative scalar "distance" score, we prefer
+	//    lower distances.  Distance scores are comparable; 0 is preferred,
+	//    and a distance of 4 is twice as bad as a distance of 2.
+	//
+	//  - Each item has a "generation" score, we prefer higher generations.
+	//    Generation scores should not be treated as a linear scale; the
+	//    magnitude of deltas is meaningless; only the sign of a delta is
+	//    meaningful.
+	//
+	//    > So it would be wrong to say something like
+	//    >
+	//    >     desirability = (-a*distance) + (b*generation)       // for some constants `a` and `b`
+	//    >
+	//    > because `generation` can't be used that way
+	//
+	//  - We prefer items that appear in more lists over items that appear in
+	//    fewer lists.
+	//
+	// The relative priority of these 4 goals is undefined; preferably the
+	// algorithm should be defined in a way that makes it easy to adjust the
+	// relative priorities.
+
+	ret := make(containers.Set[btrfsvol.LogicalAddr])
+	illegal := make(containers.Set[btrfsvol.LogicalAddr]) // cannot-be-accepted and already-accepted
+	accept := func(item btrfsvol.LogicalAddr) {
+		ret.Insert(item)
+		for _, list := range o.augmentQueue[treeID].multi {
+			if list.Has(item) {
+				illegal.InsertFrom(list)
+			}
+		}
+	}
+
+	sortedItems := maps.Keys(choices)
+	sort.Slice(sortedItems, func(i, j int) bool {
+		iItem, jItem := sortedItems[i], sortedItems[j]
+		if choices[iItem].Count != choices[jItem].Count {
+			return choices[iItem].Count > choices[jItem].Count // reverse this check; higher counts should sort lower
+		}
+		if choices[iItem].Distance != choices[jItem].Distance {
+			return choices[iItem].Distance < choices[jItem].Distance
+		}
+		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
+	})
+	for _, item := range sortedItems {
+		if !illegal.Has(item) {
+			accept(item)
+		}
+	}
+
+	// Log our result
+	wantKeys := append(
+		maps.Keys(o.augmentQueue[treeID].single),
+		maps.Keys(o.augmentQueue[treeID].multi)...)
+	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 {
+			list = containers.NewSet[btrfsvol.LogicalAddr](o.augmentQueue[treeID].single[wantKey])
+		}
+		chose := list.Intersection(ret)
+		switch {
+		case len(chose) == 0:
+			dlog.Infof(ctx, "lists[%q]: chose (none) from %v", wantKey, maps.SortedKeys(list))
+		case len(list) > 1:
+			dlog.Infof(ctx, "lists[%q]: chose %v from %v", wantKey, chose.TakeOne(), maps.SortedKeys(list))
+		default:
+			dlog.Debugf(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
+
+	return ret
+}
+
+////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+func (queue *treeAugmentQueue) has(wantKey Want) bool {
+	if queue != nil {
+		if queue.zero != nil {
+			if _, ok := queue.zero[wantKey]; ok {
+				return true
+			}
+		}
+		if queue.single != nil {
+			if _, ok := queue.single[wantKey]; ok {
+				return true
+			}
+		}
+		if queue.multi != nil {
+			if _, ok := queue.multi[wantKey]; ok {
+				return true
+			}
+		}
+	}
+	return false
+}
+
+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
+	}
+	switch len(choices) {
+	case 0:
+		if queue.zero == nil {
+			queue.zero = make(map[Want]struct{})
+		}
+		queue.zero[wantKey] = struct{}{}
+	case 1:
+		if queue.single == nil {
+			queue.single = make(map[Want]btrfsvol.LogicalAddr)
+		}
+		queue.single[wantKey] = choices.TakeOne()
+	default:
+		if queue.multi == nil {
+			queue.multi = make(map[Want]containers.Set[btrfsvol.LogicalAddr])
+		}
+		queue.multi[wantKey] = choices
+	}
+}
+
+func (o *rebuilder) hasAugment(wantKey WantWithTree) bool {
+	return o.augmentQueue[wantKey.TreeID].has(wantKey.Key)
+}
+
+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[wantKey.TreeID].store(wantKey.Key, choices)
+	if len(choices) == 0 {
+		o.numAugmentFailures++
+		dlog.Debug(ctx, "ERR: could not find wanted item")
+	} else {
+		o.numAugments++
+		dlog.Debugf(ctx, "choices=%v", maps.SortedKeys(choices))
+	}
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
new file mode 100644
index 0000000..492436b
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
@@ -0,0 +1,86 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"context"
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+// AddedItem implements btrees.Callbacks.
+func (o *rebuilder) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+	o.addedItemQueue.Insert(keyAndTree{
+		TreeID: tree,
+		Key:    key,
+	})
+}
+
+// AddedRoot implements btrees.Callbacks.
+func (o *rebuilder) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+	if retries := o.retryItemQueue[tree]; retries != nil {
+		o.addedItemQueue.InsertFrom(retries)
+	}
+}
+
+// LookupRoot implements btrees.Callbacks.
+func (o *rebuilder) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+	wantKey := WantWithTree{
+		TreeID: btrfsprim.ROOT_TREE_OBJECTID,
+		Key: Want{
+			ObjectID:   tree,
+			ItemType:   btrfsitem.ROOT_ITEM_KEY,
+			OffsetType: offsetAny,
+		},
+	}
+	ctx = withWant(ctx, logFieldTreeWant, "tree Root", wantKey)
+	foundKey, ok := o._want(ctx, wantKey)
+	if !ok {
+		o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
+		return 0, btrfsitem.Root{}, false
+	}
+	itemBody := o.rebuilt.Tree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey)
+	defer itemBody.Free()
+	switch itemBody := itemBody.(type) {
+	case *btrfsitem.Root:
+		return btrfsprim.Generation(foundKey.Offset), *itemBody, true
+	case *btrfsitem.Error:
+		o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", foundKey, 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))
+	}
+}
+
+// LookupUUID implements btrees.Callbacks.
+func (o *rebuilder) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+	wantKey := WantWithTree{
+		TreeID: btrfsprim.UUID_TREE_OBJECTID,
+		Key:    wantFromKey(btrfsitem.UUIDToKey(uuid)),
+	}
+	ctx = withWant(ctx, logFieldTreeWant, "resolve parent UUID", wantKey)
+	if !o._wantOff(ctx, wantKey) {
+		o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID)
+		return 0, false
+	}
+	itemBody := o.rebuilt.Tree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key())
+	defer itemBody.Free()
+	switch itemBody := itemBody.(type) {
+	case *btrfsitem.UUIDMap:
+		return itemBody.ObjID, true
+	case *btrfsitem.Error:
+		o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", wantKey, 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/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
new file mode 100644
index 0000000..adf3cff
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
@@ -0,0 +1,400 @@
+// 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) {
+	wantKey := WantWithTree{
+		TreeID: treeID,
+		Key: Want{
+			ObjectID:   objID,
+			ItemType:   typ,
+			OffsetType: offsetAny,
+		},
+	}
+	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
+	o._want(ctx, wantKey)
+}
+
+func (o *rebuilder) _want(ctx context.Context, wantKey WantWithTree) (key btrfsprim.Key, ok bool) {
+	if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil {
+		o.enqueueRetry(wantKey.TreeID)
+		return btrfsprim.Key{}, false
+	}
+
+	// check if we already have it
+
+	tgt := wantKey.Key.Key()
+	if key, _, ok := o.rebuilt.Tree(ctx, wantKey.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(wantKey) {
+		return btrfsprim.Key{}, false
+	}
+	wants := make(containers.Set[btrfsvol.LogicalAddr])
+	o.rebuilt.Tree(ctx, wantKey.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, wantKey.TreeID).LeafToRoots(ctx, v.Node))
+			return true
+		})
+	o.wantAugment(ctx, 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) {
+	wantKey := WantWithTree{
+		TreeID: treeID,
+		Key: Want{
+			ObjectID:   objID,
+			ItemType:   typ,
+			OffsetType: offsetExact,
+			OffsetLow:  off,
+		},
+	}
+	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
+	o._wantOff(ctx, wantKey)
+}
+
+func (o *rebuilder) _wantOff(ctx context.Context, wantKey WantWithTree) (ok bool) {
+	if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil {
+		o.enqueueRetry(wantKey.TreeID)
+		return false
+	}
+
+	// check if we already have it
+
+	tgt := wantKey.Key.Key()
+	if _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Load(tgt); ok {
+		return true
+	}
+
+	// OK, we need to insert it
+
+	if o.hasAugment(wantKey) {
+		return false
+	}
+	wants := make(containers.Set[btrfsvol.LogicalAddr])
+	o.rebuilt.Tree(ctx, wantKey.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, wantKey.TreeID).LeafToRoots(ctx, v.Node))
+			return true
+		})
+	o.wantAugment(ctx, wantKey, wants)
+	return false
+}
+
+// wantDirIndex implements rebuildCallbacks.
+func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) {
+	wantKey := WantWithTree{
+		TreeID: treeID,
+		Key: Want{
+			ObjectID:   objID,
+			ItemType:   btrfsitem.DIR_INDEX_KEY,
+			OffsetType: offsetName,
+			OffsetName: string(name),
+		},
+	}
+	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
+
+	if o.rebuilt.Tree(ctx, treeID) == nil {
+		o.enqueueRetry(treeID)
+		return
+	}
+
+	// check if we already have it
+
+	tgt := wantKey.Key.Key()
+	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, ptr keyio.ItemPtr) bool {
+			if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) {
+				found = true
+			}
+			return !found
+		})
+	if found {
+		return
+	}
+
+	// OK, we need to insert it
+
+	if o.hasAugment(wantKey) {
+		return
+	}
+	wants := make(containers.Set[btrfsvol.LogicalAddr])
+	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
+		func(key btrfsprim.Key, _ keyio.ItemPtr) int {
+			key.Offset = 0
+			return tgt.Compare(key)
+		},
+		func(_ btrfsprim.Key, ptr keyio.ItemPtr) bool {
+			if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) {
+				wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, ptr.Node))
+			}
+			return true
+		})
+	o.wantAugment(ctx, wantKey, wants)
+}
+
+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, reason string,
+	treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType,
+	beg, end uint64,
+) {
+	wantKey := WantWithTree{
+		TreeID: treeID,
+		Key: Want{
+			ObjectID:   objID,
+			ItemType:   typ,
+			OffsetType: offsetAny,
+		},
+	}
+	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
+	wantKey.Key.OffsetType = offsetRange
+
+	if o.rebuilt.Tree(ctx, treeID) == nil {
+		o.enqueueRetry(treeID)
+		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.Key.OffsetLow = last
+					wantKey.Key.OffsetHigh = runBeg
+					wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey)
+					o.wantAugment(wantCtx, wantKey, nil)
+				}
+				wantKey.Key.OffsetLow = gap.Beg
+				wantKey.Key.OffsetHigh = gap.End
+				wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey)
+				o.wantAugment(wantCtx, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node))
+				last = runEnd
+			})
+		if last < gap.End {
+			// log an error
+			wantKey.Key.OffsetLow = last
+			wantKey.Key.OffsetHigh = gap.End
+			wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey)
+			o.wantAugment(wantCtx, 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) {
+	inodeWant := WantWithTree{
+		TreeID: inodeTree,
+		Key: Want{
+			ObjectID:   inode,
+			ItemType:   btrfsitem.INODE_ITEM_KEY,
+			OffsetType: offsetExact,
+			OffsetLow:  0,
+		},
+	}
+	inodeCtx := withWant(ctx, logFieldItemWant, reason, inodeWant)
+	if !o._wantOff(inodeCtx, inodeWant) {
+		o.enqueueRetry(inodeTree)
+		return
+	}
+	inodePtr, ok := o.rebuilt.Tree(inodeCtx, inodeTree).Items(inodeCtx).Load(inodeWant.Key.Key())
+	if !ok {
+		panic(fmt.Errorf("should not happen: could not load key: %v", inodeWant))
+	}
+	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
+	}
+
+	o._wantRange(
+		ctx, reason,
+		btrfsprim.CSUM_TREE_OBJECTID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY,
+		uint64(roundDown(beg, btrfssum.BlockSize)), uint64(roundUp(end, btrfssum.BlockSize)))
+}
+
+// wantFileExt implements rebuildCallbacks.
+func (o *rebuilder) wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) {
+	o._wantRange(
+		ctx, reason,
+		treeID, ino, btrfsprim.EXTENT_DATA_KEY,
+		0, uint64(size))
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go
new file mode 100644
index 0000000..2b471fe
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go
@@ -0,0 +1,107 @@
+// 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/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+)
+
+type wantOffsetType int8
+
+const (
+	offsetAny = wantOffsetType(iota)
+	offsetExact
+	offsetRange
+	offsetName
+)
+
+type Want struct {
+	ObjectID   btrfsprim.ObjID
+	ItemType   btrfsprim.ItemType
+	OffsetType wantOffsetType
+	OffsetLow  uint64
+	OffsetHigh uint64
+	OffsetName string
+}
+
+func (a Want) Compare(b Want) int {
+	if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 {
+		return d
+	}
+	if d := containers.NativeCompare(a.ItemType, b.ItemType); d != 0 {
+		return d
+	}
+	if d := containers.NativeCompare(a.OffsetType, b.OffsetType); d != 0 {
+		return d
+	}
+	if d := containers.NativeCompare(a.OffsetLow, b.OffsetLow); d != 0 {
+		return d
+	}
+	if d := containers.NativeCompare(a.OffsetHigh, b.OffsetHigh); d != 0 {
+		return d
+	}
+	if d := containers.NativeCompare(a.OffsetName, b.OffsetName); d != 0 {
+		return d
+	}
+	return 0
+}
+
+func (o Want) Key() btrfsprim.Key {
+	return btrfsprim.Key{
+		ObjectID: o.ObjectID,
+		ItemType: o.ItemType,
+		Offset:   o.OffsetLow,
+	}
+}
+
+func wantFromKey(k btrfsprim.Key) Want {
+	return Want{
+		ObjectID:   k.ObjectID,
+		ItemType:   k.ItemType,
+		OffsetType: offsetExact,
+		OffsetLow:  k.Offset,
+	}
+}
+
+func (o Want) String() string {
+	switch o.OffsetType {
+	case offsetAny:
+		return fmt.Sprintf("{%v %v ?}", o.ObjectID, o.ItemType)
+	case offsetExact:
+		return fmt.Sprintf("{%v %v %v}", o.ObjectID, o.ItemType, o.OffsetLow)
+	case offsetRange:
+		return fmt.Sprintf("{%v %v %v-%v}", o.ObjectID, o.ItemType, o.OffsetLow, o.OffsetHigh)
+	case offsetName:
+		return fmt.Sprintf("{%v %v name=%q}", o.ObjectID, o.ItemType, o.OffsetName)
+	default:
+		panic(fmt.Errorf("should not happen: OffsetType=%#v", o.OffsetType))
+	}
+}
+
+type WantWithTree struct {
+	TreeID btrfsprim.ObjID
+	Key    Want
+}
+
+func (o WantWithTree) String() string {
+	return fmt.Sprintf("tree=%v key=%v", o.TreeID, o.Key)
+}
+
+const (
+	logFieldItemWant = "btrfsinspect.rebuild-nodes.rebuild.want"
+	logFieldTreeWant = "btrfsinspect.rebuild-nodes.rebuild.add-tree.want"
+)
+
+func withWant(ctx context.Context, logField, reason string, wantKey WantWithTree) context.Context {
+	ctx = dlog.WithField(ctx, logField+".reason", reason)
+	ctx = dlog.WithField(ctx, logField+".key", wantKey)
+	return ctx
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
new file mode 100644
index 0000000..17949ab
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
@@ -0,0 +1,77 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"context"
+	"time"
+
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"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"
+	"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/textui"
+)
+
+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 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]](
+		dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.read.substep", "read-nodes"),
+		dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+
+	nodeGraph := graph.New(*sb)
+	keyIO := keyio.NewHandle(fs, *sb)
+
+	progressWriter.Set(stats)
+	for _, devResults := range scanResults {
+		for _, laddr := range maps.SortedKeys(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 {
+				btrfstree.FreeNodeRef(nodeRef)
+				return btrfstree.Superblock{}, graph.Graph{}, nil, err
+			}
+
+			nodeGraph.InsertNode(nodeRef)
+			keyIO.InsertNode(nodeRef)
+
+			btrfstree.FreeNodeRef(nodeRef)
+
+			stats.N++
+			progressWriter.Set(stats)
+		}
+	}
+	if stats.N != stats.D {
+		panic("should not happen")
+	}
+	progressWriter.Done()
+	dlog.Info(ctx, "... done reading node data")
+
+	if err := nodeGraph.FinalCheck(ctx, fs, *sb); err != nil {
+		return btrfstree.Superblock{}, graph.Graph{}, nil, err
+	}
+	keyIO.SetGraph(*nodeGraph)
+
+	return *sb, *nodeGraph, keyIO, nil
+}
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/util.go b/cmd/btrfs-rec/inspect/rebuildtrees/util.go
new file mode 100644
index 0000000..9d91f23
--- /dev/null
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/util.go
@@ -0,0 +1,31 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"golang.org/x/exp/constraints"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
+)
+
+func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int {
+	var cnt int
+	for _, devResults := range nodeScanResults {
+		cnt += len(devResults.FoundNodes)
+	}
+	return cnt
+}
+
+func roundDown[T constraints.Integer](n, d T) T {
+	return (n / d) * d
+}
+
+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/cmd/btrfs-rec/inspect_rebuildnodes.go b/cmd/btrfs-rec/inspect_rebuildtrees.go
index ba1dcab..ba1dcab 100644
--- a/cmd/btrfs-rec/inspect_rebuildnodes.go
+++ b/cmd/btrfs-rec/inspect_rebuildtrees.go