diff options
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect/rebuildmappings')
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go | 11 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go (renamed from lib/btrfsprogs/btrfsinspect/rebuildmappings/csumitems.go) | 53 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go (renamed from lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go) | 50 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go (renamed from lib/btrfsprogs/btrfsinspect/rebuildmappings/unmappedregions.go) | 9 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go | 60 |
5 files changed, 138 insertions, 45 deletions
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 } |