store sums in a big ol slice

6 files changed, 462 insertions, 406 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/scanfornodes.go b/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go
index 99009e6..99009e6 100644
--- a/lib/btrfsprogs/btrfsinspect/scanforextents/scanfornodes.go
+++ b/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go
diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/csum.go b/lib/btrfsprogs/btrfsinspect/scanforextents/csum.go
deleted file mode 100644
index ec46833..0000000
--- a/lib/btrfsprogs/btrfsinspect/scanforextents/csum.go
+++ /dev/null
@@ -1,129 +0,0 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package scanforextents
-
-import (
-	"context"
-	"errors"
-	"fmt"
-
-	"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"
-)
-
-const csumBlockSize = 4 * 1024
-
-func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) {
-	var dat [csumBlockSize]byte
-	if _, err := fs.ReadAt(dat[:], laddr); err != nil {
-		return btrfssum.CSum{}, err
-	}
-	return alg.Sum(dat[:])
-}
-
-func ChecksumPhysical(dev *btrfs.Device, alg btrfssum.CSumType, paddr btrfsvol.PhysicalAddr) (btrfssum.CSum, error) {
-	var dat [csumBlockSize]byte
-	if _, err := dev.ReadAt(dat[:], paddr); err != nil {
-		return btrfssum.CSum{}, err
-	}
-	return alg.Sum(dat[:])
-}
-
-func ChecksumQualifiedPhysical(fs *btrfs.FS, alg btrfssum.CSumType, paddr btrfsvol.QualifiedPhysicalAddr) (btrfssum.CSum, error) {
-	dev := fs.LV.PhysicalVolumes()[paddr.Dev]
-	if dev == nil {
-		return btrfssum.CSum{}, fmt.Errorf("no such device_id=%v", paddr.Dev)
-	}
-	return ChecksumPhysical(dev, alg, paddr.Addr)
-}
-
-type shortSum string
-
-func readCSumTree(ctx context.Context, fs btrfs.Trees) map[shortSum][]btrfsvol.LogicalAddr {
-	sb, _ := fs.Superblock()
-
-	sum2laddrs := make(map[shortSum][]btrfsvol.LogicalAddr)
-	var cntUnmapped, cntErr, cntMismatch, cntValid int
-	fs.TreeWalk(ctx, btrfs.CSUM_TREE_OBJECTID,
-		func(err *btrfs.TreeError) {
-			dlog.Error(ctx, err)
-		},
-		btrfs.TreeWalkHandler{
-			Item: func(path btrfs.TreePath, item btrfs.Item) error {
-				if item.Key.ItemType != btrfsitem.EXTENT_CSUM_KEY {
-					return nil
-				}
-				body := item.Body.(btrfsitem.ExtentCSum)
-
-				for i, treeSum := range body.Sums {
-					laddr := btrfsvol.LogicalAddr(item.Key.Offset) + (btrfsvol.LogicalAddr(i) * csumBlockSize)
-					readSum, err := ChecksumLogical(fs, sb.ChecksumType, laddr)
-					if err != nil {
-						if errors.Is(err, btrfsvol.ErrCouldNotMap) {
-							cntUnmapped++
-							treeShortSum := shortSum(treeSum[:body.ChecksumSize])
-							sum2laddrs[treeShortSum] = append(sum2laddrs[treeShortSum], laddr)
-							continue
-						}
-						dlog.Error(ctx, err)
-						cntErr++
-						continue
-					}
-					if readSum != treeSum {
-						dlog.Errorf(ctx, "checksum mismatch at laddr=%v: CSUM_TREE=%v != read=%v",
-							laddr, treeSum, readSum)
-						cntMismatch++
-						continue
-					}
-					cntValid++
-				}
-				return nil
-			},
-		},
-	)
-
-	total := cntErr + cntUnmapped + cntMismatch + cntValid
-	dlog.Infof(ctx, "  checksum errors          : %v", cntErr)
-	dlog.Infof(ctx, "  unmapped checksums       : %v", cntUnmapped)
-	dlog.Infof(ctx, "  mismatched checksums     : %v", cntMismatch)
-	dlog.Infof(ctx, "  valid checksums          : %v", cntValid)
-	dlog.Infof(ctx, "  -------------------------:")
-	dlog.Infof(ctx, "  total checksums          : %v", total)
-	dlog.Infof(ctx, "  distinct unmapped        : %v", len(sum2laddrs))
-
-	return sum2laddrs
-}
-
-func LookupCSum(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (map[btrfsvol.LogicalAddr]btrfssum.CSum, error) {
-	item, err := fs.TreeSearch(btrfs.CSUM_TREE_OBJECTID, func(key btrfs.Key, size uint32) int {
-		itemBeg := btrfsvol.LogicalAddr(key.ObjectID)
-		numSums := int64(size) / int64(alg.Size())
-		itemEnd := itemBeg + btrfsvol.LogicalAddr(numSums*csumBlockSize)
-		switch {
-		case itemEnd <= laddr:
-			return 1
-		case laddr < itemBeg:
-			return -1
-		default:
-			return 0
-		}
-	})
-	if err != nil {
-		return nil, err
-	}
-	body, ok := item.Body.(btrfsitem.ExtentCSum)
-	if !ok {
-		return nil, fmt.Errorf("item body is %T not ExtentCSum", item.Body)
-	}
-	ret := make(map[btrfsvol.LogicalAddr]btrfssum.CSum, len(body.Sums))
-	for i, sum := range body.Sums {
-		ret[btrfsvol.LogicalAddr(item.Key.ObjectID)+(btrfsvol.LogicalAddr(i)*csumBlockSize)] = sum
-	}
-	return ret, nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go b/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go
new file mode 100644
index 0000000..6a42946
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go
@@ -0,0 +1,267 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package scanforextents
+
+import (
+	"context"
+	"encoding/gob"
+	"fmt"
+	"io"
+	"os"
+	"runtime"
+	"strings"
+	"sync"
+
+	"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/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil"
+)
+
+const csumBlockSize = 4 * 1024
+
+type ShortSum string
+
+type LogicalSumRun struct {
+	Addr btrfsvol.LogicalAddr
+	Sums string
+}
+
+type AllSums struct {
+	ChecksumSize int
+	Logical      []LogicalSumRun
+	Physical     map[btrfsvol.DeviceID]string
+}
+
+func ReadAllSums(filename string) (AllSums, error) {
+	fh, err := os.Open(filename)
+	if err != nil {
+		return AllSums{}, err
+	}
+	defer fh.Close()
+	var val AllSums
+	if err := gob.NewDecoder(fh).Decode(&val); err != nil {
+		return AllSums{}, err
+	}
+	return val, nil
+}
+
+func WriteAllSums(w io.Writer, sums AllSums) error {
+	return gob.NewEncoder(w).Encode(sums)
+}
+
+func (as AllSums) SumForPAddr(paddr btrfsvol.QualifiedPhysicalAddr) (ShortSum, bool) {
+	run, ok := as.Physical[paddr.Dev]
+	if !ok {
+		return "", false
+	}
+	off := int(paddr.Addr/csumBlockSize) * as.ChecksumSize
+	if off+as.ChecksumSize > len(run) {
+		return "", false
+	}
+	return ShortSum(run[off : off+as.ChecksumSize]), true
+}
+
+func (as AllSums) SumForLAddr(laddr btrfsvol.LogicalAddr) (ShortSum, bool) {
+	for _, run := range as.Logical {
+		size := btrfsvol.AddrDelta(len(run.Sums)/as.ChecksumSize) * csumBlockSize
+		if run.Addr > laddr {
+			return "", false
+		}
+		if run.Addr.Add(size) <= laddr {
+			continue
+		}
+		off := int(laddr.Sub(run.Addr)/csumBlockSize) * as.ChecksumSize
+		return ShortSum(run.Sums[off : off+as.ChecksumSize]), true
+	}
+	return "", false
+}
+
+func (as AllSums) WalkLogical(fn func(btrfsvol.LogicalAddr, ShortSum) error) error {
+	for _, run := range as.Logical {
+		for laddr, off := run.Addr, 0; off < len(run.Sums); laddr, off = laddr+csumBlockSize, off+as.ChecksumSize {
+			if err := fn(laddr, ShortSum(run.Sums[off:off+as.ChecksumSize])); err != nil {
+				return err
+			}
+		}
+	}
+	return nil
+}
+
+func SumEverything(ctx context.Context, fs *btrfs.FS) (AllSums, error) {
+	var ret AllSums
+
+	// ChecksumSize
+	var alg btrfssum.CSumType
+	if err := func() error {
+		sb, err := fs.Superblock()
+		if err != nil {
+			return err
+		}
+		alg = sb.ChecksumType
+		ret.ChecksumSize = alg.Size()
+		return nil
+	}(); err != nil {
+		return ret, err
+	}
+
+	// Logical
+	dlog.Info(ctx, "Walking CSUM_TREE...")
+	func() {
+		var curAddr btrfsvol.LogicalAddr
+		var curSums strings.Builder
+		btrfsutil.NewBrokenTrees(ctx, fs).TreeWalk(ctx, btrfs.CSUM_TREE_OBJECTID,
+			func(err *btrfs.TreeError) {
+				dlog.Error(ctx, err)
+			},
+			btrfs.TreeWalkHandler{
+				Item: func(path btrfs.TreePath, item btrfs.Item) error {
+					if item.Key.ItemType != btrfsitem.EXTENT_CSUM_KEY {
+						return nil
+					}
+					body := item.Body.(btrfsitem.ExtentCSum)
+
+					for i, sum := range body.Sums {
+						laddr := btrfsvol.LogicalAddr(item.Key.Offset) + (btrfsvol.LogicalAddr(i) * csumBlockSize)
+						if laddr != curAddr {
+							if curSums.Len() > 0 {
+								ret.Logical = append(ret.Logical, LogicalSumRun{
+									Addr: curAddr,
+									Sums: curSums.String(),
+								})
+							}
+							curAddr = laddr
+							curSums.Reset()
+						}
+						curSums.Write(sum[:ret.ChecksumSize])
+					}
+					return nil
+				},
+			},
+		)
+		if curSums.Len() > 0 {
+			ret.Logical = append(ret.Logical, LogicalSumRun{
+				Addr: curAddr,
+				Sums: curSums.String(),
+			})
+		}
+	}()
+	if err := ctx.Err(); err != nil {
+		return ret, err
+	}
+	dlog.Info(ctx, "... done walking")
+	runtime.GC()
+	dlog.Info(ctx, "... GC'd")
+
+	// Physical
+	dlog.Info(ctx, "Summing devices...")
+	if err := func() error {
+		devs := fs.LV.PhysicalVolumes()
+
+		var mu sync.Mutex
+		ret.Physical = make(map[btrfsvol.DeviceID]string, len(devs))
+
+		grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{})
+		for devID, dev := range devs {
+			devID, dev := devID, dev
+			grp.Go(dev.Name(), func(ctx context.Context) error {
+				devSize := dev.Size()
+				numSums := int(devSize / csumBlockSize)
+				sums := make([]byte, numSums*ret.ChecksumSize)
+				lastPct := -1
+				progress := func(curSum int) {
+					pct := int(100 * float64(curSum) / float64(numSums))
+					if pct != lastPct || curSum == numSums {
+						dlog.Infof(ctx, "... dev[%q] summed %v%%",
+							dev.Name(), pct)
+						lastPct = pct
+					}
+				}
+				for i := 0; i < numSums; i++ {
+					if err := ctx.Err(); err != nil {
+						return err
+					}
+					progress(i)
+					sum, err := ChecksumPhysical(dev, alg, btrfsvol.PhysicalAddr(i*csumBlockSize))
+					if err != nil {
+						return err
+					}
+					copy(sums[i*ret.ChecksumSize:], sum[:ret.ChecksumSize])
+				}
+				progress(numSums)
+				sumsStr := string(sums)
+				mu.Lock()
+				ret.Physical[devID] = sumsStr
+				mu.Unlock()
+				return nil
+			})
+		}
+		return grp.Wait()
+	}(); err != nil {
+		return ret, err
+	}
+	dlog.Info(ctx, "... done summing devices")
+	runtime.GC()
+	dlog.Info(ctx, "... GC'd")
+
+	// Return
+	return ret, nil
+}
+
+func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) {
+	var dat [csumBlockSize]byte
+	if _, err := fs.ReadAt(dat[:], laddr); err != nil {
+		return btrfssum.CSum{}, err
+	}
+	return alg.Sum(dat[:])
+}
+
+func ChecksumPhysical(dev *btrfs.Device, alg btrfssum.CSumType, paddr btrfsvol.PhysicalAddr) (btrfssum.CSum, error) {
+	var dat [csumBlockSize]byte
+	if _, err := dev.ReadAt(dat[:], paddr); err != nil {
+		return btrfssum.CSum{}, err
+	}
+	return alg.Sum(dat[:])
+}
+
+func ChecksumQualifiedPhysical(fs *btrfs.FS, alg btrfssum.CSumType, paddr btrfsvol.QualifiedPhysicalAddr) (btrfssum.CSum, error) {
+	dev := fs.LV.PhysicalVolumes()[paddr.Dev]
+	if dev == nil {
+		return btrfssum.CSum{}, fmt.Errorf("no such device_id=%v", paddr.Dev)
+	}
+	return ChecksumPhysical(dev, alg, paddr.Addr)
+}
+
+func LookupCSum(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (map[btrfsvol.LogicalAddr]btrfssum.CSum, error) {
+	item, err := fs.TreeSearch(btrfs.CSUM_TREE_OBJECTID, func(key btrfs.Key, size uint32) int {
+		itemBeg := btrfsvol.LogicalAddr(key.ObjectID)
+		numSums := int64(size) / int64(alg.Size())
+		itemEnd := itemBeg + btrfsvol.LogicalAddr(numSums*csumBlockSize)
+		switch {
+		case itemEnd <= laddr:
+			return 1
+		case laddr < itemBeg:
+			return -1
+		default:
+			return 0
+		}
+	})
+	if err != nil {
+		return nil, err
+	}
+	body, ok := item.Body.(btrfsitem.ExtentCSum)
+	if !ok {
+		return nil, fmt.Errorf("item body is %T not ExtentCSum", item.Body)
+	}
+	ret := make(map[btrfsvol.LogicalAddr]btrfssum.CSum, len(body.Sums))
+	for i, sum := range body.Sums {
+		ret[btrfsvol.LogicalAddr(item.Key.ObjectID)+(btrfsvol.LogicalAddr(i)*csumBlockSize)] = sum
+	}
+	return ret, nil
+}
diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go b/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go
index 90351a5..f67b498 100644
--- a/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go
+++ b/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go
@@ -52,7 +52,7 @@ func roundUp[T constraints.Integer](x, multiple T) T {
 	return ((x + multiple - 1) / multiple) * multiple
 }
 
-func WalkGapsOneDev(ctx context.Context, dev *btrfs.Device,
+func WalkGaps(ctx context.Context,
 	gaps []PhysicalGap, blockSize btrfsvol.PhysicalAddr,
 	progress func(cur, total int64),
 	main func(btrfsvol.PhysicalAddr) error,
diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go b/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go
new file mode 100644
index 0000000..1b04b3c
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go
@@ -0,0 +1,194 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package scanforextents
+
+import (
+	"context"
+	"errors"
+	"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/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
+)
+
+func ScanForExtents(ctx context.Context, fs *btrfs.FS, blockgroups *BlockGroupTree, sums AllSums) error {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return err
+	}
+
+	dlog.Info(ctx, "Reverse-indexing and validating logical sums...")
+	sum2laddrs := make(map[ShortSum][]btrfsvol.LogicalAddr)
+	if err := sums.WalkLogical(func(laddr btrfsvol.LogicalAddr, expShortSum ShortSum) error {
+		if err := ctx.Err(); err != nil {
+			return err
+		}
+		readSum, err := ChecksumLogical(fs, sb.ChecksumType, laddr)
+		if err != nil {
+			if errors.Is(err, btrfsvol.ErrCouldNotMap) {
+				sum2laddrs[expShortSum] = append(sum2laddrs[expShortSum], laddr)
+				return nil
+			}
+			return err
+		}
+		readShortSum := ShortSum(readSum[:sums.ChecksumSize])
+		if readShortSum != expShortSum {
+			return fmt.Errorf("checksum mismatch at laddr=%v: CSUM_TREE=%x != read=%x",
+				laddr, []byte(expShortSum), []byte(readShortSum))
+		}
+		return nil
+	}); err != nil {
+		return err
+	}
+	dlog.Info(ctx, "... done reverse-indexing and validating")
+
+	dlog.Info(ctx, "Cross-referencing sums (and blockgroups) to re-construct mappings...")
+	newMappings := &ExtentMappings{
+		InLV:          &fs.LV,
+		InBlockGroups: blockgroups,
+		InSums:        sums,
+		InReverseSums: sum2laddrs,
+	}
+	devs := fs.LV.PhysicalVolumes()
+	gaps := ListPhysicalGaps(fs)
+	for _, devID := range maps.SortedKeys(gaps) {
+		if err := newMappings.ScanOneDev(ctx,
+			devID, devs[devID].Name(),
+			gaps[devID],
+		); err != nil {
+			return err
+		}
+	}
+	dlog.Info(ctx, "... done cross-referencing")
+
+	dlog.Info(ctx, "Applying those mappings...")
+	for laddr, mappings := range newMappings.OutSum2mappings {
+		if len(mappings) > 1 {
+			dlog.Errorf(ctx, "multiple possibilities for laddr=%v :", laddr)
+			for _, mapping := range mappings {
+				dlog.Errorf(ctx, "  - %#v", *mapping)
+			}
+			continue
+		}
+		if err := fs.LV.AddMapping(*mappings[0]); err != nil {
+			dlog.Error(ctx, err)
+		}
+	}
+	dlog.Info(ctx, "... done applying")
+
+	return nil
+}
+
+type ExtentMappings struct {
+	// input
+	InLV          *btrfsvol.LogicalVolume[*btrfs.Device]
+	InBlockGroups *BlockGroupTree
+	InSums        AllSums
+	InReverseSums map[ShortSum][]btrfsvol.LogicalAddr
+
+	// state
+	internedMappings map[btrfsvol.Mapping]*btrfsvol.Mapping
+
+	// output
+	OutSum2mappings map[ShortSum][]*btrfsvol.Mapping
+}
+
+func (em *ExtentMappings) considerMapping(ctx context.Context, laddr btrfsvol.LogicalAddr, paddr btrfsvol.QualifiedPhysicalAddr) (btrfsvol.Mapping, bool) {
+	blockgroup := LookupBlockGroup(em.InBlockGroups, laddr, csumBlockSize)
+	if blockgroup == nil {
+		return btrfsvol.Mapping{
+			LAddr: laddr,
+			PAddr: paddr,
+			Size:  csumBlockSize,
+		}, true
+	}
+	mapping := btrfsvol.Mapping{
+		LAddr: blockgroup.LAddr,
+		PAddr: btrfsvol.QualifiedPhysicalAddr{
+			Dev:  paddr.Dev,
+			Addr: paddr.Addr.Add(laddr.Sub(blockgroup.LAddr)),
+		},
+		Size:       blockgroup.Size,
+		SizeLocked: true,
+		Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
+			OK:  true,
+			Val: blockgroup.Flags,
+		},
+	}
+	if !em.InLV.CouldAddMapping(mapping) {
+		return btrfsvol.Mapping{}, false
+	}
+
+	for offset := btrfsvol.AddrDelta(0); offset <= mapping.Size; offset += csumBlockSize {
+		expCSum, ok := em.InSums.SumForLAddr(mapping.LAddr.Add(offset))
+		if !ok {
+			continue
+		}
+		actCSum, _ := em.InSums.SumForPAddr(mapping.PAddr.Add(offset))
+		if actCSum != expCSum {
+			return btrfsvol.Mapping{}, false
+		}
+	}
+	return mapping, true
+}
+
+func (em *ExtentMappings) addMapping(sum ShortSum, mapping btrfsvol.Mapping) {
+	interned := em.internedMappings[mapping]
+	if interned == nil {
+		interned = &mapping
+		em.internedMappings[mapping] = interned
+	}
+
+	em.OutSum2mappings[sum] = append(em.OutSum2mappings[sum], interned)
+}
+
+func (em *ExtentMappings) ScanOneDev(
+	ctx context.Context,
+	devID btrfsvol.DeviceID, devName string,
+	gaps []PhysicalGap,
+) error {
+	if em.internedMappings == nil {
+		em.internedMappings = make(map[btrfsvol.Mapping]*btrfsvol.Mapping)
+	}
+	if em.OutSum2mappings == nil {
+		em.OutSum2mappings = make(map[ShortSum][]*btrfsvol.Mapping)
+	}
+
+	dlog.Infof(ctx, "... dev[%q] Scanning for extents...", devName)
+
+	lastProgress := -1
+	potentialMappings := 0
+	return WalkGaps(ctx, gaps, csumBlockSize,
+		func(curBlock, totalBlocks int64) {
+			pct := int(100 * float64(curBlock) / float64(totalBlocks))
+			if pct != lastProgress || curBlock == totalBlocks {
+				dlog.Infof(ctx, "... dev[%q] scanned %v%% (constructed %v potential mappings)",
+					devName, pct, potentialMappings)
+				lastProgress = pct
+			}
+		},
+		func(paddr btrfsvol.PhysicalAddr) error {
+			qpaddr := btrfsvol.QualifiedPhysicalAddr{
+				Dev:  devID,
+				Addr: paddr,
+			}
+			sum, _ := em.InSums.SumForPAddr(qpaddr)
+			for _, laddr := range em.InReverseSums[sum] {
+				mapping, ok := em.considerMapping(ctx, laddr, qpaddr)
+				if !ok {
+					continue
+				}
+				em.addMapping(sum, mapping)
+				potentialMappings++
+			}
+
+			return nil
+		},
+	)
+}
diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go b/lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go
deleted file mode 100644
index 72c9201..0000000
--- a/lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go
+++ /dev/null
@@ -1,276 +0,0 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package scanforextents
-
-import (
-	"context"
-	"runtime"
-	"sync"
-
-	"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/btrfssum"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil"
-	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-)
-
-func ScanForExtents(ctx context.Context, fs *btrfs.FS, blockGroups *BlockGroupTree) error {
-	treeReader := btrfsutil.NewBrokenTrees(ctx, fs)
-
-	dlog.Info(ctx, "Reading checksum tree...")
-	sum2laddrs := readCSumTree(ctx, treeReader)
-	if len(sum2laddrs) == 0 {
-		dlog.Info(ctx, "No unmapped checksums")
-		return nil
-	}
-	runtime.GC()
-	dlog.Info(ctx, "...GC'd")
-
-	devs := fs.LV.PhysicalVolumes()
-	gaps := ListPhysicalGaps(fs)
-
-	newMappings := &ExtentMappings{
-		InFS:          treeReader,
-		InLV:          &fs.LV,
-		InSum2laddrs:  sum2laddrs,
-		InBlockGroups: blockGroups,
-	}
-
-	dlog.Info(ctx, "Scanning devices...")
-	grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{})
-	for devID := range gaps {
-		dev := devs[devID]
-		devGaps := gaps[devID]
-		grp.Go(dev.Name(), func(ctx context.Context) error {
-			return newMappings.ScanOneDev(ctx, dev, devGaps)
-		})
-	}
-	if err := grp.Wait(); err != nil {
-		return err
-	}
-
-	for laddr, mappings := range newMappings.OutSum2mappings {
-		if len(mappings) > 1 {
-			dlog.Errorf(ctx, "multiple possibilities for laddr=%v :", laddr)
-			for _, mapping := range mappings {
-				dlog.Errorf(ctx, "  - %#v", *mapping)
-			}
-			continue
-		}
-		if err := fs.LV.AddMapping(*mappings[0]); err != nil {
-			dlog.Error(ctx, err)
-		}
-	}
-
-	return nil
-}
-
-type csumCacheEntry struct {
-	Sum shortSum
-	Err error
-}
-
-type csumCachePhysKey struct {
-	Dev  *btrfs.Device
-	Addr btrfsvol.PhysicalAddr
-}
-
-type ExtentMappings struct {
-	// input
-	InFS          btrfs.Trees
-	InLV          *btrfsvol.LogicalVolume[*btrfs.Device]
-	InSum2laddrs  map[shortSum][]btrfsvol.LogicalAddr
-	InBlockGroups *BlockGroupTree
-
-	// state
-	initOnce           sync.Once
-	initErr            error
-	alg                btrfssum.CSumType
-	internedMappingsMu sync.Mutex
-	internedMappings   map[btrfsvol.Mapping]*btrfsvol.Mapping
-
-	cacheLogical  containers.LRUCache[btrfsvol.LogicalAddr, csumCacheEntry]
-	cachePhysical containers.LRUCache[csumCachePhysKey, csumCacheEntry]
-
-	// output
-	sum2lock        map[shortSum]*sync.Mutex
-	OutSum2mappings map[shortSum][]*btrfsvol.Mapping
-}
-
-func (em *ExtentMappings) init() error {
-	em.initOnce.Do(func() {
-		sb, err := em.InFS.Superblock()
-		if err != nil {
-			em.initErr = err
-			return
-		}
-		em.alg = sb.ChecksumType
-		em.internedMappings = make(map[btrfsvol.Mapping]*btrfsvol.Mapping)
-		em.sum2lock = make(map[shortSum]*sync.Mutex, len(em.InSum2laddrs))
-		for sum := range em.InSum2laddrs {
-			em.sum2lock[sum] = new(sync.Mutex)
-		}
-		em.OutSum2mappings = make(map[shortSum][]*btrfsvol.Mapping)
-	})
-	return em.initErr
-}
-
-func (em *ExtentMappings) logicalSum(laddr btrfsvol.LogicalAddr) (shortSum, error) {
-	entry, ok := em.cacheLogical.Get(laddr)
-	if !ok {
-		sums, err := LookupCSum(em.InFS, em.alg, laddr)
-		if err != nil {
-			entry.Err = err
-			em.cacheLogical.Add(laddr, entry)
-		} else {
-			for laddr, sum := range sums {
-				entry.Sum = shortSum(sum[:em.alg.Size()])
-				em.cacheLogical.Add(laddr, entry)
-			}
-			sum := sums[laddr]
-			entry.Sum = shortSum(sum[:em.alg.Size()])
-		}
-	}
-	return entry.Sum, entry.Err
-}
-
-func (em *ExtentMappings) physicalSum(dev *btrfs.Device, paddr btrfsvol.PhysicalAddr) (shortSum, error) {
-	key := csumCachePhysKey{
-		Dev:  dev,
-		Addr: paddr,
-	}
-	entry, ok := em.cachePhysical.Get(key)
-	if !ok {
-		sum, err := ChecksumPhysical(dev, em.alg, paddr)
-		entry.Sum = shortSum(sum[:em.alg.Size()])
-		entry.Err = err
-		em.cachePhysical.Add(key, entry)
-	}
-	return entry.Sum, entry.Err
-}
-
-func (em *ExtentMappings) considerMapping(ctx context.Context, dev *btrfs.Device, laddr btrfsvol.LogicalAddr, paddr btrfsvol.QualifiedPhysicalAddr) (btrfsvol.Mapping, bool) {
-	blockgroup := LookupBlockGroup(em.InBlockGroups, laddr, csumBlockSize)
-	if blockgroup == nil {
-		return btrfsvol.Mapping{
-			LAddr: laddr,
-			PAddr: paddr,
-			Size:  csumBlockSize,
-		}, true
-	}
-	mapping := btrfsvol.Mapping{
-		LAddr: blockgroup.LAddr,
-		PAddr: btrfsvol.QualifiedPhysicalAddr{
-			Dev:  paddr.Dev,
-			Addr: paddr.Addr.Add(laddr.Sub(blockgroup.LAddr)),
-		},
-		Size:       blockgroup.Size,
-		SizeLocked: true,
-		Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
-			OK:  true,
-			Val: blockgroup.Flags,
-		},
-	}
-	if !em.InLV.CouldAddMapping(mapping) {
-		return btrfsvol.Mapping{}, false
-	}
-
-	for offset := btrfsvol.AddrDelta(0); offset <= mapping.Size; offset += csumBlockSize {
-		if err := ctx.Err(); err != nil {
-			return btrfsvol.Mapping{}, false
-		}
-		expCSum, err := em.logicalSum(mapping.LAddr.Add(offset))
-		if err != nil {
-			continue
-		}
-		if err := ctx.Err(); err != nil {
-			return btrfsvol.Mapping{}, false
-		}
-		actCSum, err := em.physicalSum(dev, mapping.PAddr.Addr.Add(offset))
-		if err != nil {
-			return btrfsvol.Mapping{}, false
-		}
-		if actCSum != expCSum {
-			return btrfsvol.Mapping{}, false
-		}
-	}
-	return mapping, true
-}
-
-func (em *ExtentMappings) addMapping(sum shortSum, mapping btrfsvol.Mapping) {
-	em.internedMappingsMu.Lock()
-	interned := em.internedMappings[mapping]
-	if interned == nil {
-		interned = &mapping
-		em.internedMappings[mapping] = interned
-	}
-	em.internedMappingsMu.Unlock()
-
-	em.sum2lock[sum].Lock()
-	em.OutSum2mappings[sum] = append(em.OutSum2mappings[sum], interned)
-	em.sum2lock[sum].Unlock()
-}
-
-func (em *ExtentMappings) ScanOneDev(ctx context.Context, dev *btrfs.Device, gaps []PhysicalGap) error {
-	if err := em.init(); err != nil {
-		return err
-	}
-	devID := func() btrfsvol.DeviceID {
-		sb, _ := dev.Superblock()
-		return sb.DevItem.DevID
-	}()
-
-	dlog.Infof(ctx, "... dev[%q] Scanning for extents...", dev.Name())
-
-	sumSize := em.alg.Size()
-
-	lastProgress := -1
-	potentialMappings := 0
-	return WalkGapsOneDev(ctx, dev, gaps, csumBlockSize,
-		func(curBlock, totalBlocks int64) {
-			pct := int(100 * float64(curBlock) / float64(totalBlocks))
-			if pct != lastProgress || curBlock == totalBlocks {
-				dlog.Infof(ctx, "... dev[%q] scanned %v%% (constructed %v potential mappings)",
-					dev.Name(), pct, potentialMappings)
-				lastProgress = pct
-			}
-		},
-		func(paddr btrfsvol.PhysicalAddr) error {
-			if err := ctx.Err(); err != nil {
-				return err
-			}
-			sum, err := ChecksumPhysical(dev, em.alg, paddr)
-			if err != nil {
-				dlog.Errorf(ctx, "... dev[%s] error: checksumming paddr=%v: %v",
-					dev.Name(), paddr, err)
-				return nil
-			}
-			shortSum := shortSum(sum[:sumSize])
-
-			for _, laddr := range em.InSum2laddrs[shortSum] {
-				if err := ctx.Err(); err != nil {
-					return err
-				}
-				mapping, ok := em.considerMapping(ctx, dev, laddr, btrfsvol.QualifiedPhysicalAddr{
-					Dev:  devID,
-					Addr: paddr,
-				})
-				if err := ctx.Err(); err != nil {
-					return err
-				}
-				if !ok {
-					continue
-				}
-				em.addMapping(shortSum, mapping)
-				potentialMappings++
-			}
-
-			return nil
-		},
-	)
-}