wip: work on rebuildmappings

7 files changed, 142 insertions, 46 deletions

diff --git a/cmd/btrfs-rec/inspect_dbgsums.go b/cmd/btrfs-rec/inspect_dbgsums.go
index b5abf8f..cb4ae1f 100644
--- a/cmd/btrfs-rec/inspect_dbgsums.go
+++ b/cmd/btrfs-rec/inspect_dbgsums.go
@@ -39,7 +39,7 @@ func init() {
 			}
 			dlog.Infof(ctx, "... done reading %q", args[0])
 
-			flattened := rebuildmappings.MapLogicalSums(ctx, scanResults)
+			flattened := rebuildmappings.ExtractLogicalSums(ctx, scanResults)
 			if len(flattened.Runs) == 0 {
 				return fmt.Errorf("no checksums were found in the scan")
 			}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
index bd390e0..91fecbc 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
@@ -19,7 +19,7 @@ type BlockGroup struct {
 	Flags btrfsvol.BlockGroupFlags
 }
 
-func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) ([]BlockGroup, error) {
+func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) {
 	// Dedup
 	bgsSet := make(map[BlockGroup]struct{})
 	for _, devResults := range scanResults {
@@ -47,6 +47,11 @@ func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) ([]BlockGroup,
 		pos = bg.LAddr.Add(bg.Size)
 	}
 
-	// Return
-	return bgsOrdered, nil
+	// 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/lib/btrfsprogs/btrfsinspect/rebuildmappings/csumitems.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
index eaa6f06..3430502 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/csumitems.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
@@ -18,8 +18,8 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
-func MapLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
-	dlog.Info(ctx, "Mapping the logical address space...")
+func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
+	dlog.Info(ctx, "... Mapping the logical address space...")
 	type record struct {
 		Gen btrfs.Generation
 		Sum btrfssum.ShortSum
@@ -52,14 +52,14 @@ func MapLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesRes
 			})
 		}
 	}
-	dlog.Info(ctx, "... done mapping")
+	dlog.Info(ctx, "... ... done mapping")
 
 	var flattened btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]
 	if len(addrspace) == 0 {
 		return flattened
 	}
 
-	dlog.Info(ctx, "Flattening the map ...")
+	dlog.Info(ctx, "... Flattening the map ...")
 	var curAddr btrfsvol.LogicalAddr
 	var curSums strings.Builder
 	for _, laddr := range maps.SortedKeys(addrspace) {
@@ -87,11 +87,54 @@ func MapLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesRes
 	last := flattened.Runs[len(flattened.Runs)-1]
 	end := last.Addr.Add(last.Size())
 	flattened.Size = end.Sub(flattened.Addr)
-	dlog.Info(ctx, "... done flattening")
+	dlog.Info(ctx, "... ... done flattening")
 
 	return flattened
 }
 
+func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums btrfssum.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 btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
 	runs := btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]{
 		Addr: beg,
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
index 69b783d..6126820 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
@@ -6,7 +6,6 @@ package rebuildmappings
 
 import (
 	"context"
-	"errors"
 
 	"github.com/datawire/dlib/dlog"
 
@@ -18,13 +17,13 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
-func ScanForExtents(ctx context.Context,
+func matchBlockGroupSums(ctx context.Context,
 	fs *btrfs.FS,
 	blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
 	physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
 	logicalSums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr],
 ) error {
-	dlog.Info(ctx, "Pairing up blockgroups and sums...")
+	dlog.Info(ctx, "... Pairing up blockgroups and sums...")
 	bgSums := make(map[btrfsvol.LogicalAddr]btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr])
 	for i, bgLAddr := range maps.SortedKeys(blockgroups) {
 		blockgroup := blockgroups[bgLAddr]
@@ -33,10 +32,10 @@ func ScanForExtents(ctx context.Context,
 		dlog.Infof(ctx, "... (%v/%v) blockgroup[laddr=%v] has %v runs covering %v%%",
 			i+1, len(blockgroups), bgLAddr, len(runs.Runs), int(100*runs.PctFull()))
 	}
-	dlog.Info(ctx, "... done pairing")
+	dlog.Info(ctx, "... ... done pairing")
 
-	dlog.Info(ctx, "Searching for unmapped blockgroups in unmapped regions...")
-	gaps := ListUnmappedPhysicalRegions(fs)
+	dlog.Info(ctx, "... Searching for unmapped blockgroups in unmapped physical regions...")
+	regions := ListUnmappedPhysicalRegions(fs)
 	bgMatches := make(map[btrfsvol.LogicalAddr][]btrfsvol.QualifiedPhysicalAddr)
 	for i, bgLAddr := range maps.SortedKeys(blockgroups) {
 		bgRun := bgSums[bgLAddr]
@@ -46,15 +45,15 @@ func ScanForExtents(ctx context.Context,
 			continue
 		}
 
-		if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, gaps, func(devID btrfsvol.DeviceID, gap btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
-			matches, err := diskio.IndexAll[int64, btrfssum.ShortSum](gap, bgRun)
+		if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
+			matches, err := diskio.IndexAll[int64, btrfssum.ShortSum](region, bgRun)
 			if err != nil {
 				return err
 			}
 			for _, match := range matches {
 				bgMatches[bgLAddr] = append(bgMatches[bgLAddr], btrfsvol.QualifiedPhysicalAddr{
 					Dev:  devID,
-					Addr: gap.Addr + (btrfsvol.PhysicalAddr(match) * btrfssum.BlockSize),
+					Addr: region.Addr + (btrfsvol.PhysicalAddr(match) * btrfssum.BlockSize),
 				})
 			}
 			return nil
@@ -69,9 +68,9 @@ func ScanForExtents(ctx context.Context,
 		dlog.Logf(ctx, lvl, "... (%v/%v) blockgroup[laddr=%v] has %v matches based on %v%% coverage",
 			i+1, len(bgSums), bgLAddr, len(bgMatches[bgLAddr]), int(100*bgRun.PctFull()))
 	}
-	dlog.Info(ctx, "... done searching")
+	dlog.Info(ctx, "... ... done searching")
 
-	dlog.Info(ctx, "Applying those mappings...")
+	dlog.Info(ctx, "... Applying those mappings...")
 	for _, bgLAddr := range maps.SortedKeys(bgMatches) {
 		matches := bgMatches[bgLAddr]
 		if len(matches) != 1 {
@@ -89,10 +88,17 @@ func ScanForExtents(ctx context.Context,
 			},
 		}
 		if err := fs.LV.AddMapping(mapping); err != nil {
-			dlog.Error(ctx, err)
+			dlog.Errorf(ctx, "... error: %v", err)
+			continue
 		}
+		delete(blockgroups, bgLAddr)
 	}
-	dlog.Info(ctx, "... done applying")
+	dlog.Info(ctx, "... ... done applying")
+
+	return nil
+}
+
+/* TODO
 
 	dlog.Info(ctx, "Reverse-indexing remaining unmapped logical sums...")
 	sum2laddrs := make(map[btrfssum.ShortSum][]btrfsvol.LogicalAddr)
@@ -114,8 +120,6 @@ func ScanForExtents(ctx context.Context,
 	dlog.Infof(ctx, "... done reverse-indexing; %v still unmapped logical sums",
 		numUnmappedBlocks)
 
-	/* TODO
-
 	dlog.Info(ctx, "Cross-referencing sums to re-construct mappings...")
 	newMappings := &ExtentMappings{
 		InLV:          &fs.LV,
@@ -123,11 +127,11 @@ func ScanForExtents(ctx context.Context,
 		InSums:        sums,
 		InReverseSums: sum2laddrs,
 	}
-	gaps := ListPhysicalGaps(fs)
-	for _, devID := range maps.SortedKeys(gaps) {
+	regions := ListPhysicalRegions(fs)
+	for _, devID := range maps.SortedKeys(regions) {
 		if err := newMappings.ScanOneDevice(ctx,
 			devID, devs[devID].Name(),
-			gaps[devID],
+			regions[devID],
 		); err != nil {
 			return err
 		}
@@ -149,13 +153,9 @@ func ScanForExtents(ctx context.Context,
 	}
 	dlog.Info(ctx, "... done applying")
 
-	*/
-
 	return nil
 }
 
-/*
-
 type ExtentMappings struct {
 	// input
 	InLV          *btrfsvol.LogicalVolume[*btrfs.Device]
@@ -222,7 +222,7 @@ func (em *ExtentMappings) addMapping(sum ShortSum, mapping btrfsvol.Mapping) {
 func (em *ExtentMappings) ScanOneDevice(
 	ctx context.Context,
 	devID btrfsvol.DeviceID, devName string,
-	gaps []PhysicalGap,
+	regions []PhysicalRegion,
 ) error {
 	if em.internedMappings == nil {
 		em.internedMappings = make(map[btrfsvol.Mapping]*btrfsvol.Mapping)
@@ -234,7 +234,7 @@ func (em *ExtentMappings) ScanOneDevice(
 	dlog.Infof(ctx, "... dev[%q] Scanning for extents...", devName)
 
 	var totalMappings int
-	_ = WalkGaps(ctx, gaps, btrfssum.BlockSize,
+	_ = WalkRegions(ctx, regions, btrfssum.BlockSize,
 		func(_, _ int64) {},
 		func(paddr btrfsvol.PhysicalAddr) error {
 			qpaddr := btrfsvol.QualifiedPhysicalAddr{
@@ -258,7 +258,7 @@ func (em *ExtentMappings) ScanOneDevice(
 			lastProgress = pct
 		}
 	}
-	return WalkGaps(ctx, gaps, btrfssum.BlockSize,
+	return WalkRegions(ctx, regions, btrfssum.BlockSize,
 		func(_, _ int64) {
 			progress()
 		},
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/unmappedregions.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
index 1bac127..0806a63 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/unmappedregions.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
@@ -13,9 +13,18 @@ import (
 	"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
 }
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
index 05aff72..09b2185 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
@@ -46,13 +46,14 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect
 			numNodes += len(paddrs)
 		}
 	}
-	dlog.Infof(ctx, "plan: 1/5 process %d chunks", numChunks)
-	dlog.Infof(ctx, "plan: 2/5 process %d device extents", numDevExts)
-	dlog.Infof(ctx, "plan: 3/5 process %d nodes", numNodes)
-	dlog.Infof(ctx, "plan: 4/5 process %d block groups", numBlockGroups)
-	dlog.Infof(ctx, "plan: 5/5 process sums")
+	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 process sums of block groups")
+	dlog.Infof(ctx, "plan: 6/6 process remaining sums")
 
-	dlog.Infof(ctx, "1/5: Processing %d chunks...", numChunks)
+	dlog.Infof(ctx, "1/6: Processing %d chunks...", numChunks)
 	for _, devID := range devIDs {
 		devResults := scanResults[devID]
 		for _, chunk := range devResults.FoundChunks {
@@ -65,7 +66,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect
 	}
 	dlog.Info(ctx, "... done processing chunks")
 
-	dlog.Infof(ctx, "2/5: Processing %d device extents...", numDevExts)
+	dlog.Infof(ctx, "2/6: Processing %d device extents...", numDevExts)
 	for _, devID := range devIDs {
 		devResults := scanResults[devID]
 		for _, ext := range devResults.FoundDevExtents {
@@ -80,7 +81,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect
 	// 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.)
-	dlog.Infof(ctx, "3/5: Processing %d nodes...", numNodes)
+	dlog.Infof(ctx, "3/6: Processing %d nodes...", numNodes)
 	for _, devID := range devIDs {
 		devResults := scanResults[devID]
 		// Sort them so that progress numbers are predictable.
@@ -104,15 +105,17 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect
 
 	// Use block groups to add missing flags (and as a hint to
 	// combine node entries).
-	dlog.Infof(ctx, "4/5: Processing %d block groups...", numBlockGroups)
+	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?
-	bgsOrdered, err := DedupBlockGroups(scanResults)
+	bgs, err := DedupBlockGroups(scanResults)
 	if err != nil {
 		return err
 	}
-	for _, bg := range bgsOrdered {
+	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",
@@ -133,10 +136,43 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect
 		}
 		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")
 
-	dlog.Infof(ctx, "5/5: Processing sums: TODO")
+	dlog.Infof(ctx, "5/6: Processing sums of %d block groups", len(bgs))
+	physicalSums := ExtractPhysicalSums(scanResults)
+	logicalSums := ExtractLogicalSums(ctx, scanResults)
+	if err := matchBlockGroupSums(ctx, fs, bgs, physicalSums, logicalSums); err != nil {
+		return err
+	}
+
+	dlog.Infof(ctx, "6/6: process remaining sums: TODO")
+
+	dlog.Infof(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 KiB of unmapped physical space (across %d regions)", unmappedPhysical/1024, numUnmappedPhysical)
+	unmappedLogicalRegions := ListUnmappedLogicalRegions(fs, logicalSums)
+	var unmappedLogical btrfsvol.AddrDelta
+	for _, region := range unmappedLogicalRegions {
+		unmappedLogical += region.Size()
+	}
+	dlog.Infof(ctx, "... %d KiB of unmapped summed logical space (across %d regions)", unmappedLogical/1024, len(unmappedLogicalRegions))
+	var unmappedBlockGroups btrfsvol.AddrDelta
+	for _, bg := range bgs {
+		unmappedBlockGroups += bg.Size
+	}
+	dlog.Infof(ctx, "... %d KiB of unmapped block groups (across %d groups)", unmappedBlockGroups/1024, len(bgs))
+
 	return nil
 }
diff --git a/scripts/main.sh b/scripts/main.sh
index a403100..9020d4f 100755
--- a/scripts/main.sh
+++ b/scripts/main.sh
@@ -23,6 +23,9 @@ gen $b.gen/0.scandevices.json \
 gen $b.gen/1.dbgsums.json \
     ./btrfs-rec --pv=$b.img \
     inspect dbgsums $b.gen/0.scandevices.json
+gen $b.gen/1.mappings.json \
+    ./btrfs-rec --pv=$b.img \
+    inspect rebuild-mappings $b.gen/0.scandevices.json
 # gen $b.gen/1.mappings.json \
 #     ./btrfs-rec --pv=$b.img \
 #     inspect rebuild-mappings $b.gen/0.scan-for-nodes.json