From ff28ac9487ceb162bdef47f0639ce9a6c0cc7c28 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 17 Aug 2022 20:48:50 -0600 Subject: rename: Move some files around --- .../btrfsinspect/rebuildmappings/blockgroups.go | 78 ++++++ .../btrfsinspect/rebuildmappings/gaps.go | 80 ++++++ .../btrfsinspect/rebuildmappings/scan.go | 310 +++++++++++++++++++++ 3 files changed, 468 insertions(+) create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/gaps.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go (limited to 'lib/btrfsprogs/btrfsinspect/rebuildmappings') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go new file mode 100644 index 0000000..15df6da --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go @@ -0,0 +1,78 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildmappings + +import ( + "encoding/json" + "fmt" + "os" + "sort" + + "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/maps" +) + +type NodeScanResults = map[btrfsvol.DeviceID]btrfsinspect.ScanOneDeviceResult + +type BlockGroup struct { + LAddr btrfsvol.LogicalAddr + Size btrfsvol.AddrDelta + Flags btrfsvol.BlockGroupFlags +} + +func ReadNodeScanResults(fs *btrfs.FS, filename string) (map[btrfsvol.LogicalAddr]BlockGroup, error) { + scanResultsBytes, err := os.ReadFile(filename) + if err != nil { + return nil, err + } + + var scanResults NodeScanResults + if err := json.Unmarshal(scanResultsBytes, &scanResults); err != nil { + return nil, err + } + + bgTree, err := ReduceScanResults(fs, scanResults) + if err != nil { + return nil, err + } + + return bgTree, nil +} + +func ReduceScanResults(fs *btrfs.FS, scanResults NodeScanResults) (map[btrfsvol.LogicalAddr]BlockGroup, error) { + // Reduce + bgSet := make(map[BlockGroup]struct{}) + for _, found := range scanResults { + for _, bg := range found.FoundBlockGroups { + bgSet[BlockGroup{ + LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID), + Size: btrfsvol.AddrDelta(bg.Key.Offset), + Flags: bg.BG.Flags, + }] = struct{}{} + } + } + + // Sanity check + bgList := maps.Keys(bgSet) + sort.Slice(bgList, func(i, j int) bool { + return bgList[i].LAddr < bgList[j].LAddr + }) + var pos btrfsvol.LogicalAddr + for _, bg := range bgList { + if bg.LAddr < pos || bg.Size < 0 { + return nil, fmt.Errorf("found block groups are inconsistent") + } + pos = bg.LAddr.Add(bg.Size) + } + + // Return + bgMap := make(map[btrfsvol.LogicalAddr]BlockGroup, len(bgSet)) + for bg := range bgSet { + bgMap[bg.LAddr] = bg + } + return bgMap, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/gaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/gaps.go new file mode 100644 index 0000000..f5fb27a --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/gaps.go @@ -0,0 +1,80 @@ +// Copyright (C) 2022 Luke Shumaker +// +// 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/btrfsitem" + "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" +) + +type PhysicalGap struct { + Beg, End btrfsvol.PhysicalAddr +} + +func ListPhysicalGaps(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalGap { + gaps := make(map[btrfsvol.DeviceID][]PhysicalGap) + pos := make(map[btrfsvol.DeviceID]btrfsvol.PhysicalAddr) + mappings := fs.LV.Mappings() + sort.Slice(mappings, func(i, j int) bool { + return mappings[i].PAddr.Cmp(mappings[j].PAddr) < 0 + }) + for _, mapping := range mappings { + if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr { + gaps[mapping.PAddr.Dev] = append(gaps[mapping.PAddr.Dev], PhysicalGap{ + 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 { + gaps[devID] = append(gaps[devID], PhysicalGap{ + Beg: pos[devID], + End: devSize, + }) + } + } + return gaps +} + +func roundUp[T constraints.Integer](x, multiple T) T { + return ((x + multiple - 1) / multiple) * multiple +} + +func WalkGaps(ctx context.Context, + sums btrfsinspect.AllSums, gaps map[btrfsvol.DeviceID][]PhysicalGap, + fn func(btrfsvol.DeviceID, btrfsinspect.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, btrfsitem.CSumBlockSize) + begOff := int(begAddr/btrfsitem.CSumBlockSize) * sums.Physical[devID].ChecksumSize + endOff := int(gap.End/btrfsitem.CSumBlockSize) * sums.Physical[devID].ChecksumSize + if err := fn(devID, btrfsinspect.SumRun[btrfsvol.PhysicalAddr]{ + ChecksumSize: sums.Physical[devID].ChecksumSize, + Addr: begAddr, + Sums: sums.Physical[devID].Sums[begOff:endOff], + }); err != nil { + return err + } + } + } + return nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go new file mode 100644 index 0000000..83c4a31 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/scan.go @@ -0,0 +1,310 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildmappings + +import ( + "context" + "errors" + + "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/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/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +func ScanForExtents(ctx context.Context, fs *btrfs.FS, blockgroups map[btrfsvol.LogicalAddr]BlockGroup, sums btrfsinspect.AllSums) error { + dlog.Info(ctx, "Pairing up blockgroups and sums...") + bgSums := make(map[btrfsvol.LogicalAddr]btrfsinspect.SumRunWithGaps[btrfsvol.LogicalAddr]) + for i, bgLAddr := range maps.SortedKeys(blockgroups) { + blockgroup := blockgroups[bgLAddr] + runs := btrfsinspect.SumRunWithGaps[btrfsvol.LogicalAddr]{ + Addr: blockgroup.LAddr, + Size: blockgroup.Size, + } + for laddr := blockgroup.LAddr; laddr < blockgroup.LAddr.Add(blockgroup.Size); { + run, next, ok := sums.RunForLAddr(laddr) + if !ok { + laddr = next + continue + } + off := int((laddr-run.Addr)/btrfsitem.CSumBlockSize) * run.ChecksumSize + deltaAddr := slices.Min[btrfsvol.AddrDelta]( + blockgroup.Size-laddr.Sub(blockgroup.LAddr), + btrfsvol.AddrDelta((len(run.Sums)-off)/run.ChecksumSize)*btrfsitem.CSumBlockSize) + deltaOff := int(deltaAddr/btrfsitem.CSumBlockSize) * run.ChecksumSize + runs.Runs = append(runs.Runs, btrfsinspect.SumRun[btrfsvol.LogicalAddr]{ + ChecksumSize: run.ChecksumSize, + Addr: laddr, + Sums: run.Sums[off : off+deltaOff], + }) + laddr = laddr.Add(deltaAddr) + } + bgSums[blockgroup.LAddr] = runs + 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, "Searching for unmapped blockgroups in unmapped regions...") + gaps := ListPhysicalGaps(fs) + bgMatches := make(map[btrfsvol.LogicalAddr][]btrfsvol.QualifiedPhysicalAddr) + for i, bgLAddr := range maps.SortedKeys(blockgroups) { + bgRun := bgSums[bgLAddr] + if len(bgRun.Runs) == 0 { + dlog.Errorf(ctx, "... (%v/%v) blockgroup[laddr=%v] can't be matched because it has 0 runs", + i+1, len(bgSums), bgLAddr) + continue + } + + if err := WalkGaps(ctx, sums, gaps, func(devID btrfsvol.DeviceID, gap btrfsinspect.SumRun[btrfsvol.PhysicalAddr]) error { + matches, err := diskio.IndexAll[int64, btrfsinspect.ShortSum](gap, 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) * btrfsitem.CSumBlockSize), + }) + } + return nil + }); err != nil { + return err + } + + lvl := dlog.LogLevelInfo + if len(bgMatches[bgLAddr]) == 0 { + lvl = dlog.LogLevelError + } + 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, "Applying those mappings...") + for _, bgLAddr := range maps.SortedKeys(bgMatches) { + matches := bgMatches[bgLAddr] + if len(matches) != 1 { + continue + } + blockgroup := blockgroups[bgLAddr] + 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.Error(ctx, err) + } + } + dlog.Info(ctx, "... done applying") + + dlog.Info(ctx, "Reverse-indexing remaining unmapped logical sums...") + sum2laddrs := make(map[btrfsinspect.ShortSum][]btrfsvol.LogicalAddr) + var numUnmappedBlocks int64 + if err := sums.WalkLogical(ctx, func(laddr btrfsvol.LogicalAddr, sum btrfsinspect.ShortSum) error { + var dat [btrfsitem.CSumBlockSize]byte + if _, err := fs.ReadAt(dat[:], laddr); err != nil { + if errors.Is(err, btrfsvol.ErrCouldNotMap) { + sum2laddrs[sum] = append(sum2laddrs[sum], laddr) + numUnmappedBlocks++ + return nil + } + return err + } + return nil + }); err != nil { + return err + } + 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, + InBlockGroups: blockgroups, + InSums: sums, + InReverseSums: sum2laddrs, + } + gaps := ListPhysicalGaps(fs) + for _, devID := range maps.SortedKeys(gaps) { + if err := newMappings.ScanOneDevice(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, btrfsitem.CSumBlockSize) + if blockgroup == nil { + return btrfsvol.Mapping{ + LAddr: laddr, + PAddr: paddr, + Size: btrfsitem.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 += btrfsitem.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) ScanOneDevice( + 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) + + var totalMappings int + _ = WalkGaps(ctx, gaps, btrfsitem.CSumBlockSize, + func(_, _ int64) {}, + func(paddr btrfsvol.PhysicalAddr) error { + qpaddr := btrfsvol.QualifiedPhysicalAddr{ + Dev: devID, + Addr: paddr, + } + sum, _ := em.InSums.SumForPAddr(qpaddr) + totalMappings += len(em.InReverseSums[sum]) + return nil + }, + ) + + lastProgress := -1 + considered := 0 + accepted := 0 + progress := func() { + pct := int(100 * 10000 * float64(considered) / float64(totalMappings)) + if pct != lastProgress || considered == totalMappings { + dlog.Infof(ctx, "... dev[%q] scanned %v%% (considered %v/%v pairings, accepted %v)", + devName, float64(pct)/10000.0, considered, totalMappings, accepted) + lastProgress = pct + } + } + return WalkGaps(ctx, gaps, btrfsitem.CSumBlockSize, + func(_, _ int64) { + progress() + }, + func(paddr btrfsvol.PhysicalAddr) error { + qpaddr := btrfsvol.QualifiedPhysicalAddr{ + Dev: devID, + Addr: paddr, + } + sum, _ := em.InSums.SumForPAddr(qpaddr) + for i, laddr := range em.InReverseSums[sum] { + if i%100 == 0 { + if err := ctx.Err(); err != nil { + return err + } + } + mapping, ok := em.considerMapping(ctx, laddr, qpaddr) + considered++ + if !ok { + continue + } + em.addMapping(sum, mapping) + accepted++ + progress() + } + + return nil + }, + ) +} + +*/ -- cgit v1.2.3-2-g168b