From 8c8c6c27552f8554ba014c34d684cb90538ef65b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 28 Feb 2023 14:05:27 -0700 Subject: Move files around [ci-skip] --- cmd/btrfs-rec/inspect/rebuildmappings/process.go | 222 +++++++++++++++++++++++ 1 file changed, 222 insertions(+) create mode 100644 cmd/btrfs-rec/inspect/rebuildmappings/process.go (limited to 'cmd/btrfs-rec/inspect/rebuildmappings/process.go') 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 +// +// 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 +} -- cgit v1.2.3-2-g168b From 1be85fecedebe9ea37b910a15a5c45dd2e57649d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 12 Mar 2023 15:17:39 -0600 Subject: Get it to compile with the renamed files #!/bin/bash set -e git ls-files :*.go :!tools/| while read -r file; do pkgname=${file%/*.go} pkgname=${pkgname##*/} if [[ "$pkgname" == btrfs-rec ]]; then pkgname=main fi sed -i "s/^package [^_]*/package ${pkgname}/" "$file" done # btrfsutil #################################################################### gofmt -w -r 'rebuildnodes -> rebuildtrees' cmd lib gofmt -w -r 'btrees -> btrfsutil' cmd lib gofmt -w -r 'keyio -> btrfsutil' cmd lib sed -i 's/func New/func NewGraph/' lib/btrfsutil/graph.go gofmt -w -r 'graph.New -> btrfsutil.NewGraph' cmd lib gofmt -w -r 'graph.Graph -> btrfsutil.Graph' cmd lib sed -i -e '/\/graph"/d' -e 's/pkggraph\.//' lib/btrfsutil/rebuilt_forrest.go gofmt -w -r 'btrfsutil.BrokenForrest -> BrokenForrest ' lib/btrfsutil gofmt -w -r 'btrfsutil.Handle -> Handle ' lib/btrfsutil gofmt -w -r 'btrfsutil.Graph -> Graph ' lib/btrfsutil gofmt -w -r 'btrfsutil.ItemPtr -> ItemPtr ' lib/btrfsutil gofmt -w -r 'Handle -> KeyIO' lib/btrfsutil gofmt -w -r 'btrfsutil.Handle -> btrfsutil.KeyIO' cmd/btrfs-rec/inspect/rebuildtrees/ gofmt -w -r 'NewHandle -> NewKeyIO' cmd lib # rebuildmappings ############################################################## gofmt -w -r 'btrfsinspect.DumpTrees -> dumptrees.DumpTrees' cmd lib gofmt -w -r 'btrfsinspect.MountRO -> mount.MountRO' cmd lib gofmt -w -r 'btrfsinspect.ScanDevices -> rebuildmappings.ScanDevices' cmd lib gofmt -w -r 'btrfsinspect.ScanDevicesResult -> rebuildmappings.ScanDevicesResult' cmd lib gofmt -w -r 'btrfsinspect.SysExtentCSum -> rebuildmappings.SysExtentCSum' cmd lib gofmt -w -r 'rebuildmappings.IndexAll -> IndexAll ' cmd/btrfs-rec/inspect/rebuildmappings gofmt -w -r 'rebuildmappings.ScanDevicesResult -> ScanDevicesResult ' cmd/btrfs-rec/inspect/rebuildmappings gofmt -w -r 'rebuildmappings.SysExtentCSum -> SysExtentCSum ' cmd/btrfs-rec/inspect/rebuildmappings # btrfscheck ################################################################### sed -i -e 's/func handle/func Handle/' lib/btrfscheck/graph.go sed -i 's/handle/btrfscheck.Handle/g' cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go gofmt -w -r 'fsErr -> FSErr ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'want -> Want ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantOff -> WantOff ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantDirIndex -> WantDirIndex ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantCSum -> WantCSum ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantFileExt -> WantFileExt ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees # generic imports ############################################################## replace() { git grep -l "$1"|xargs -r sed -i "s,$1,$2,g" } replace 'lib/btrfsprogs/btrfsinspect/rebuildmappings"' 'cmd/btrfs-rec/inspect/rebuildmappings"' replace 'lib/btrfsprogs/btrfsinspect/rebuildnodes"' 'cmd/btrfs-rec/inspect/rebuildtrees"' replace 'lib/btrfsprogs/btrfsutil"' 'lib/btrfsutil"' goimports -w cmd lib ./tools/bin/golangci-lint run --fix ./... And then touch-up copyright statements by hand. --- cmd/btrfs-rec/inspect/rebuildmappings/process.go | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'cmd/btrfs-rec/inspect/rebuildmappings/process.go') diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go index cdf5e5a..5f41f15 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go @@ -12,7 +12,6 @@ import ( "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" @@ -26,7 +25,7 @@ func getNodeSize(fs *btrfs.FS) (btrfsvol.AddrDelta, error) { return btrfsvol.AddrDelta(sb.NodeSize), nil } -func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) error { +func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesResult) error { nodeSize, err := getNodeSize(fs) if err != nil { return err -- cgit v1.2.3-2-g168b From 84099499feb558a01253bd272563fa1271527a75 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 12 Mar 2023 17:09:51 -0600 Subject: Update identifiers and comments to reflect new file/package names --- cmd/btrfs-rec/inspect/rebuildmappings/process.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'cmd/btrfs-rec/inspect/rebuildmappings/process.go') diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go index 5f41f15..4ef4dac 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go @@ -161,14 +161,14 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR 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 { + if err := matchBlockGroupSumsExact(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 { + if err := matchBlockGroupSumsFuzzy(ctx, fs, bgs, physicalSums, logicalSums); err != nil { return err } dlog.Info(_ctx, "... done searching for fuzzy block groups") -- cgit v1.2.3-2-g168b From e92796fed05143239733d3feec0231a69af2f617 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 12 Mar 2023 17:09:41 -0600 Subject: Update log field names to reflect new file/package names --- cmd/btrfs-rec/inspect/rebuildmappings/process.go | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'cmd/btrfs-rec/inspect/rebuildmappings/process.go') diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go index 4ef4dac..7ce3748 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go @@ -54,7 +54,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR 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") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "1/6") dlog.Infof(_ctx, "1/6: Processing %d chunks...", numChunks) for _, devID := range devIDs { devResults := scanResults[devID] @@ -68,7 +68,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR } dlog.Info(_ctx, "... done processing chunks") - ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "2/6") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "2/6") dlog.Infof(_ctx, "2/6: Processing %d device extents...", numDevExts) for _, devID := range devIDs { devResults := scanResults[devID] @@ -84,7 +84,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR // 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") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "3/6") dlog.Infof(_ctx, "3/6: Processing %d nodes...", numNodes) for _, devID := range devIDs { devResults := scanResults[devID] @@ -109,7 +109,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR // 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") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.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 @@ -157,7 +157,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR // 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") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.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) @@ -166,14 +166,14 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR } dlog.Info(ctx, "... done searching for exact block groups") - ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "6/6") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "6/6") dlog.Infof(_ctx, "6/6: Searching for %d block groups in checksum map (fuzzy)...", len(bgs)) if err := matchBlockGroupSumsFuzzy(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") + ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "report") dlog.Info(_ctx, "report:") unmappedPhysicalRegions := ListUnmappedPhysicalRegions(fs) -- cgit v1.2.3-2-g168b