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 --- cmd/btrfs-rec/inspect_dumpsums.go | 6 +- cmd/btrfs-rec/inspect_scanforextents.go | 9 +- lib/btrfsprogs/btrfsinspect/csums.go | 316 +++++++++++++++++++++ .../btrfsinspect/rebuildmappings/blockgroups.go | 78 +++++ .../btrfsinspect/rebuildmappings/gaps.go | 80 ++++++ .../btrfsinspect/rebuildmappings/scan.go | 310 ++++++++++++++++++++ lib/btrfsprogs/btrfsinspect/recoverchunks.go | 225 --------------- lib/btrfsprogs/btrfsinspect/scan.go | 57 ++++ lib/btrfsprogs/btrfsinspect/scandevices.go | 224 +++++++++++++++ .../btrfsinspect/scanforextents/blockgroups.go | 78 ----- .../btrfsinspect/scanforextents/csums.go | 316 --------------------- .../btrfsinspect/scanforextents/csums_raw.go | 66 ----- lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go | 79 ------ lib/btrfsprogs/btrfsinspect/scanforextents/scan.go | 309 -------------------- lib/btrfsprogs/btrfsutil/csums.go | 66 +++++ lib/btrfsprogs/btrfsutil/scan.go | 57 ---- 16 files changed, 1139 insertions(+), 1137 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/csums.go 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 delete mode 100644 lib/btrfsprogs/btrfsinspect/recoverchunks.go create mode 100644 lib/btrfsprogs/btrfsinspect/scan.go create mode 100644 lib/btrfsprogs/btrfsinspect/scandevices.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/csums.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/csums_raw.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/scan.go create mode 100644 lib/btrfsprogs/btrfsutil/csums.go delete mode 100644 lib/btrfsprogs/btrfsutil/scan.go diff --git a/cmd/btrfs-rec/inspect_dumpsums.go b/cmd/btrfs-rec/inspect_dumpsums.go index ae159d1..3d0da39 100644 --- a/cmd/btrfs-rec/inspect_dumpsums.go +++ b/cmd/btrfs-rec/inspect_dumpsums.go @@ -12,7 +12,7 @@ import ( "github.com/spf13/cobra" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/scanforextents" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" ) func init() { @@ -24,12 +24,12 @@ func init() { }, RunE: func(fs *btrfs.FS, cmd *cobra.Command, _ []string) error { ctx := cmd.Context() - sums, err := scanforextents.SumEverything(ctx, fs) + sums, err := btrfsinspect.SumEverything(ctx, fs) if err != nil { return err } dlog.Info(ctx, "Writing sums as gob to stdout...") - return scanforextents.WriteAllSums(os.Stdout, sums) + return btrfsinspect.WriteAllSums(os.Stdout, sums) }, }) } diff --git a/cmd/btrfs-rec/inspect_scanforextents.go b/cmd/btrfs-rec/inspect_scanforextents.go index 5f763d9..ac23e6d 100644 --- a/cmd/btrfs-rec/inspect_scanforextents.go +++ b/cmd/btrfs-rec/inspect_scanforextents.go @@ -13,7 +13,8 @@ import ( "github.com/spf13/cobra" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/scanforextents" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildmappings" ) func init() { @@ -26,7 +27,7 @@ func init() { ctx := cmd.Context() dlog.Infof(ctx, "Reading %q...", args[0]) - bgs, err := scanforextents.ReadNodeScanResults(fs, args[0]) + bgs, err := rebuildmappings.ReadNodeScanResults(fs, args[0]) if err != nil { return err } @@ -34,13 +35,13 @@ func init() { dlog.Infof(ctx, "... done reading %q", args[0]) dlog.Infof(ctx, "Reading %q...", args[1]) - sums, err := scanforextents.ReadAllSums(args[1]) + sums, err := btrfsinspect.ReadAllSums(args[1]) if err != nil { return err } dlog.Infof(ctx, "... done reading %q", args[1]) - if err := scanforextents.ScanForExtents(ctx, fs, bgs, sums); err != nil { + if err := rebuildmappings.ScanForExtents(ctx, fs, bgs, sums); err != nil { return err } diff --git a/lib/btrfsprogs/btrfsinspect/csums.go b/lib/btrfsprogs/btrfsinspect/csums.go new file mode 100644 index 0000000..a062a77 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/csums.go @@ -0,0 +1,316 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsinspect + +import ( + "context" + "encoding/gob" + "io" + "math" + "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" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" +) + +// ShortSum ////////////////////////////////////////////////////////// + +type ShortSum string + +// SumRun //////////////////////////////////////////////////////////// + +type SumRun[Addr btrfsvol.IntAddr[Addr]] struct { + // How big a ShortSum is in this Run. + ChecksumSize int + // Base address where this run starts. + Addr Addr + // All of the ShortSums in this run, concatenated together. + // + // This is a 'string' rather than a 'ShortSum' to make it hard + // to accidentally use it as a single sum. + Sums string +} + +func (run SumRun[Addr]) NumSums() int { + return len(run.Sums) / run.ChecksumSize +} + +func (run SumRun[Addr]) Size() btrfsvol.AddrDelta { + return btrfsvol.AddrDelta(run.NumSums()) * btrfsitem.CSumBlockSize +} + +// Get implements diskio.Sequence[int, ShortSum] +func (run SumRun[Addr]) Get(sumIdx int64) (ShortSum, error) { + if sumIdx < 0 || int(sumIdx) >= run.NumSums() { + return "", io.EOF + } + off := int(sumIdx) * run.ChecksumSize + return ShortSum(run.Sums[off : off+run.ChecksumSize]), nil +} + +func (run SumRun[Addr]) SumForAddr(addr Addr) (ShortSum, bool) { + if addr < run.Addr || addr >= run.Addr.Add(run.Size()) { + return "", false + } + off := int((addr-run.Addr)/btrfsitem.CSumBlockSize) * run.ChecksumSize + return ShortSum(run.Sums[off : off+run.ChecksumSize]), true +} + +func (run SumRun[Addr]) Walk(ctx context.Context, fn func(Addr, ShortSum) error) error { + for addr, off := run.Addr, 0; off < len(run.Sums); addr, off = addr+btrfsitem.CSumBlockSize, off+run.ChecksumSize { + if err := ctx.Err(); err != nil { + return err + } + if err := fn(addr, ShortSum(run.Sums[off:off+run.ChecksumSize])); err != nil { + return err + } + } + return nil +} + +// SumRunWithGaps //////////////////////////////////////////////////// + +type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct { + Addr Addr + Size btrfsvol.AddrDelta + Runs []SumRun[Addr] +} + +func (sg SumRunWithGaps[Addr]) NumSums() int { + return int(sg.Size / btrfsitem.CSumBlockSize) +} + +func (sg SumRunWithGaps[Addr]) PctFull() float64 { + total := sg.NumSums() + var full int + for _, run := range sg.Runs { + full += run.NumSums() + } + return float64(full) / float64(total) +} + +func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (ShortSum, error) { + if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) { + return "", io.EOF + } + for _, run := range sg.Runs { + if run.Addr > addr { + return "", diskio.ErrWildcard + } + if run.Addr.Add(run.Size()) <= addr { + continue + } + off := int((addr-run.Addr)/btrfsitem.CSumBlockSize) * run.ChecksumSize + return ShortSum(run.Sums[off : off+run.ChecksumSize]), nil + } + return "", diskio.ErrWildcard +} + +// Get implements diskio.Sequence[int, ShortSum] +func (sg SumRunWithGaps[Addr]) Get(sumIdx int64) (ShortSum, error) { + addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfsitem.CSumBlockSize) + return sg.SumForAddr(addr) +} + +// AllSums /////////////////////////////////////////////////////////// + +type AllSums struct { + Logical []SumRun[btrfsvol.LogicalAddr] + Physical map[btrfsvol.DeviceID]SumRun[btrfsvol.PhysicalAddr] +} + +func (as AllSums) SumForPAddr(paddr btrfsvol.QualifiedPhysicalAddr) (ShortSum, bool) { + run, ok := as.Physical[paddr.Dev] + if !ok { + return "", false + } + return run.SumForAddr(paddr.Addr) +} + +func (as AllSums) RunForLAddr(laddr btrfsvol.LogicalAddr) (SumRun[btrfsvol.LogicalAddr], btrfsvol.LogicalAddr, bool) { + for _, run := range as.Logical { + if run.Addr > laddr { + return SumRun[btrfsvol.LogicalAddr]{}, run.Addr, false + } + if run.Addr.Add(run.Size()) <= laddr { + continue + } + return run, 0, true + } + return SumRun[btrfsvol.LogicalAddr]{}, math.MaxInt64, false +} + +func (as AllSums) SumForLAddr(laddr btrfsvol.LogicalAddr) (ShortSum, bool) { + run, _, ok := as.RunForLAddr(laddr) + if !ok { + return "", false + } + return run.SumForAddr(laddr) +} + +func (as AllSums) WalkLogical(ctx context.Context, fn func(btrfsvol.LogicalAddr, ShortSum) error) error { + for _, run := range as.Logical { + if err := run.Walk(ctx, fn); err != nil { + return err + } + } + return nil +} + +// Read/Write AllSums //////////////////////////////////////////////// + +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 SumEverything(ctx context.Context, fs *btrfs.FS) (AllSums, error) { + var ret AllSums + + // ChecksumSize + var alg btrfssum.CSumType + var csumSize int + if err := func() error { + sb, err := fs.Superblock() + if err != nil { + return err + } + alg = sb.ChecksumType + csumSize = 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) * btrfsitem.CSumBlockSize) + if laddr != curAddr+(btrfsvol.LogicalAddr(curSums.Len()/csumSize)*btrfsitem.CSumBlockSize) { + if curSums.Len() > 0 { + ret.Logical = append(ret.Logical, SumRun[btrfsvol.LogicalAddr]{ + ChecksumSize: csumSize, + Addr: curAddr, + Sums: curSums.String(), + }) + } + curAddr = laddr + curSums.Reset() + } + curSums.Write(sum[:csumSize]) + } + return nil + }, + }, + ) + if curSums.Len() > 0 { + ret.Logical = append(ret.Logical, SumRun[btrfsvol.LogicalAddr]{ + ChecksumSize: csumSize, + 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]SumRun[btrfsvol.PhysicalAddr], 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 / btrfsitem.CSumBlockSize) + sums := make([]byte, numSums*csumSize) + 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 := btrfsutil.ChecksumPhysical(dev, alg, btrfsvol.PhysicalAddr(i*btrfsitem.CSumBlockSize)) + if err != nil { + return err + } + copy(sums[i*csumSize:], sum[:csumSize]) + } + progress(numSums) + sumsStr := string(sums) + mu.Lock() + ret.Physical[devID] = SumRun[btrfsvol.PhysicalAddr]{ + ChecksumSize: csumSize, + Addr: 0, + Sums: 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 +} 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 + }, + ) +} + +*/ diff --git a/lib/btrfsprogs/btrfsinspect/recoverchunks.go b/lib/btrfsprogs/btrfsinspect/recoverchunks.go deleted file mode 100644 index b3abf75..0000000 --- a/lib/btrfsprogs/btrfsinspect/recoverchunks.go +++ /dev/null @@ -1,225 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfsinspect - -import ( - "context" - "sort" - - "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/btrfsutil" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" -) - -type ScanOneDeviceResult struct { - FoundNodes map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr - FoundChunks []btrfs.SysChunk - FoundBlockGroups []SysBlockGroup - FoundDevExtents []SysDevExtent -} - -type SysBlockGroup struct { - Key btrfs.Key - BG btrfsitem.BlockGroup -} - -type SysDevExtent struct { - Key btrfs.Key - DevExt btrfsitem.DevExtent -} - -func (found ScanOneDeviceResult) AddToLV(ctx context.Context, fs *btrfs.FS, dev *btrfs.Device) { - sb, _ := dev.Superblock() - - total := len(found.FoundChunks) + len(found.FoundDevExtents) - for _, paddrs := range found.FoundNodes { - total += len(paddrs) - } - lastProgress := -1 - done := 0 - printProgress := func() { - pct := int(100 * float64(done) / float64(total)) - if pct != lastProgress || done == total { - dlog.Infof(ctx, "... dev[%q] added %v%% of the mappings (%v/%v=>%v)", - dev.Name(), pct, done, total, len(fs.LV.Mappings())) - lastProgress = pct - } - } - printProgress() - - for _, chunk := range found.FoundChunks { - for _, mapping := range chunk.Chunk.Mappings(chunk.Key) { - if err := fs.LV.AddMapping(mapping); err != nil { - dlog.Errorf(ctx, "... dev[%q] error: adding chunk: %v", - dev.Name(), err) - } - done++ - printProgress() - } - } - - for _, ext := range found.FoundDevExtents { - if err := fs.LV.AddMapping(ext.DevExt.Mapping(ext.Key)); err != nil { - dlog.Errorf(ctx, "... dev[%q] error: adding devext: %v", - dev.Name(), err) - } - done++ - printProgress() - } - - // 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.) - // - // Sort them so that progress numbers are predictable. - for _, laddr := range maps.SortedKeys(found.FoundNodes) { - for _, paddr := range found.FoundNodes[laddr] { - if err := fs.LV.AddMapping(btrfsvol.Mapping{ - LAddr: laddr, - PAddr: btrfsvol.QualifiedPhysicalAddr{ - Dev: sb.DevItem.DevID, - Addr: paddr, - }, - Size: btrfsvol.AddrDelta(sb.NodeSize), - SizeLocked: false, - }); err != nil { - dlog.Errorf(ctx, "... dev[%q] error: adding node ident: %v", - dev.Name(), err) - } - done++ - printProgress() - } - } - - // Use block groups to add missing flags (and as a hint to - // combine node entries). - // - // 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? - type blockgroup struct { - LAddr btrfsvol.LogicalAddr - Size btrfsvol.AddrDelta - Flags btrfsvol.BlockGroupFlags - } - bgsSet := make(map[blockgroup]struct{}) - for _, bg := range found.FoundBlockGroups { - bgsSet[blockgroup{ - LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID), - Size: btrfsvol.AddrDelta(bg.Key.Offset), - Flags: bg.BG.Flags, - }] = struct{}{} - } - bgsOrdered := maps.Keys(bgsSet) - sort.Slice(bgsOrdered, func(i, j int) bool { - return bgsOrdered[i].LAddr < bgsOrdered[j].LAddr - }) - for _, bg := range bgsOrdered { - otherLAddr, otherPAddr := fs.LV.ResolveAny(bg.LAddr, bg.Size) - if otherLAddr < 0 || otherPAddr.Addr < 0 { - dlog.Errorf(ctx, "... dev[%q] error: could not pair blockgroup laddr=%v (size=%v flags=%v) with a mapping", - dev.Name(), 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, "... dev[%q] error: adding flags from blockgroup: %v", - dev.Name(), err) - } - } -} - -// ScanOneDevice mostly mimics btrfs-progs -// cmds/rescue-chunk-recover.c:scan_one_device(). -func ScanOneDevice(ctx context.Context, dev *btrfs.Device, superblock btrfs.Superblock) (ScanOneDeviceResult, error) { - result := ScanOneDeviceResult{ - FoundNodes: make(map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr), - } - - devSize := dev.Size() - lastProgress := -1 - - err := btrfsutil.ScanForNodes(ctx, dev, superblock, func(nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfs.Node], err error) { - if err != nil { - dlog.Infof(ctx, "... dev[%q] error: %v", dev.Name(), err) - return - } - result.FoundNodes[nodeRef.Data.Head.Addr] = append(result.FoundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr) - for i, item := range nodeRef.Data.BodyLeaf { - switch item.Key.ItemType { - case btrfsitem.CHUNK_ITEM_KEY: - chunk, ok := item.Body.(btrfsitem.Chunk) - if !ok { - dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is CHUNK_ITEM_KEY, but struct is %T", - dev.Name(), nodeRef.Addr, i, item.Body) - continue - } - //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found chunk", - // dev.Name(), nodeRef.Addr, i) - result.FoundChunks = append(result.FoundChunks, btrfs.SysChunk{ - Key: item.Key, - Chunk: chunk, - }) - case btrfsitem.BLOCK_GROUP_ITEM_KEY: - bg, ok := item.Body.(btrfsitem.BlockGroup) - if !ok { - dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is BLOCK_GROUP_ITEM_KEY, but struct is %T", - dev.Name(), nodeRef.Addr, i, item.Body) - continue - } - //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found block group", - // dev.Name(), nodeRef.Addr, i) - result.FoundBlockGroups = append(result.FoundBlockGroups, SysBlockGroup{ - Key: item.Key, - BG: bg, - }) - case btrfsitem.DEV_EXTENT_KEY: - devext, ok := item.Body.(btrfsitem.DevExtent) - if !ok { - dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is DEV_EXTENT_KEY, but struct is %T", - dev.Name(), nodeRef.Addr, i, item.Body) - continue - } - //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found dev extent", - // dev.Name(), nodeRef.Addr, i) - result.FoundDevExtents = append(result.FoundDevExtents, SysDevExtent{ - Key: item.Key, - DevExt: devext, - }) - } - } - }, func(pos btrfsvol.PhysicalAddr) { - pct := int(100 * float64(pos) / float64(devSize)) - if pct != lastProgress || pos == devSize { - dlog.Infof(ctx, "... dev[%q] scanned %v%% (found: %v nodes, %v chunks, %v block groups, %v dev extents)", - dev.Name(), pct, - len(result.FoundNodes), - len(result.FoundChunks), - len(result.FoundBlockGroups), - len(result.FoundDevExtents)) - lastProgress = pct - } - }) - - return result, err -} diff --git a/lib/btrfsprogs/btrfsinspect/scan.go b/lib/btrfsprogs/btrfsinspect/scan.go new file mode 100644 index 0000000..ef1079f --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/scan.go @@ -0,0 +1,57 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsinspect + +import ( + "context" + "errors" + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +// ScanForNodes mimics btrfs-progs +// cmds/rescue-chunk-recover.c:scan_one_device(), except rather than +// doing something itself when it finds a node, it simply calls a +// callback function. +func ScanForNodes(ctx context.Context, dev *btrfs.Device, sb btrfs.Superblock, fn func(*diskio.Ref[btrfsvol.PhysicalAddr, btrfs.Node], error), prog func(btrfsvol.PhysicalAddr)) error { + devSize := dev.Size() + + if sb.NodeSize < sb.SectorSize { + return fmt.Errorf("node_size(%v) < sector_size(%v)", + sb.NodeSize, sb.SectorSize) + } + + for pos := btrfsvol.PhysicalAddr(0); pos+btrfsvol.PhysicalAddr(sb.NodeSize) < devSize; pos += btrfsvol.PhysicalAddr(sb.SectorSize) { + if ctx.Err() != nil { + return ctx.Err() + } + if slices.Contains(pos, btrfs.SuperblockAddrs) { + //fmt.Printf("sector@%v is a superblock\n", pos) + continue + } + + if prog != nil { + prog(pos) + } + + nodeRef, err := btrfs.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, nil) + if err != nil && errors.Is(err, btrfs.ErrNotANode) { + continue + } + fn(nodeRef, err) + + pos += btrfsvol.PhysicalAddr(sb.NodeSize) - btrfsvol.PhysicalAddr(sb.SectorSize) + } + + if prog != nil { + prog(devSize) + } + + return nil +} diff --git a/lib/btrfsprogs/btrfsinspect/scandevices.go b/lib/btrfsprogs/btrfsinspect/scandevices.go new file mode 100644 index 0000000..13c5d60 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/scandevices.go @@ -0,0 +1,224 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsinspect + +import ( + "context" + "sort" + + "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/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" +) + +type ScanOneDeviceResult struct { + FoundNodes map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr + FoundChunks []btrfs.SysChunk + FoundBlockGroups []SysBlockGroup + FoundDevExtents []SysDevExtent +} + +type SysBlockGroup struct { + Key btrfs.Key + BG btrfsitem.BlockGroup +} + +type SysDevExtent struct { + Key btrfs.Key + DevExt btrfsitem.DevExtent +} + +func (found ScanOneDeviceResult) AddToLV(ctx context.Context, fs *btrfs.FS, dev *btrfs.Device) { + sb, _ := dev.Superblock() + + total := len(found.FoundChunks) + len(found.FoundDevExtents) + for _, paddrs := range found.FoundNodes { + total += len(paddrs) + } + lastProgress := -1 + done := 0 + printProgress := func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastProgress || done == total { + dlog.Infof(ctx, "... dev[%q] added %v%% of the mappings (%v/%v=>%v)", + dev.Name(), pct, done, total, len(fs.LV.Mappings())) + lastProgress = pct + } + } + printProgress() + + for _, chunk := range found.FoundChunks { + for _, mapping := range chunk.Chunk.Mappings(chunk.Key) { + if err := fs.LV.AddMapping(mapping); err != nil { + dlog.Errorf(ctx, "... dev[%q] error: adding chunk: %v", + dev.Name(), err) + } + done++ + printProgress() + } + } + + for _, ext := range found.FoundDevExtents { + if err := fs.LV.AddMapping(ext.DevExt.Mapping(ext.Key)); err != nil { + dlog.Errorf(ctx, "... dev[%q] error: adding devext: %v", + dev.Name(), err) + } + done++ + printProgress() + } + + // 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.) + // + // Sort them so that progress numbers are predictable. + for _, laddr := range maps.SortedKeys(found.FoundNodes) { + for _, paddr := range found.FoundNodes[laddr] { + if err := fs.LV.AddMapping(btrfsvol.Mapping{ + LAddr: laddr, + PAddr: btrfsvol.QualifiedPhysicalAddr{ + Dev: sb.DevItem.DevID, + Addr: paddr, + }, + Size: btrfsvol.AddrDelta(sb.NodeSize), + SizeLocked: false, + }); err != nil { + dlog.Errorf(ctx, "... dev[%q] error: adding node ident: %v", + dev.Name(), err) + } + done++ + printProgress() + } + } + + // Use block groups to add missing flags (and as a hint to + // combine node entries). + // + // 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? + type blockgroup struct { + LAddr btrfsvol.LogicalAddr + Size btrfsvol.AddrDelta + Flags btrfsvol.BlockGroupFlags + } + bgsSet := make(map[blockgroup]struct{}) + for _, bg := range found.FoundBlockGroups { + bgsSet[blockgroup{ + LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID), + Size: btrfsvol.AddrDelta(bg.Key.Offset), + Flags: bg.BG.Flags, + }] = struct{}{} + } + bgsOrdered := maps.Keys(bgsSet) + sort.Slice(bgsOrdered, func(i, j int) bool { + return bgsOrdered[i].LAddr < bgsOrdered[j].LAddr + }) + for _, bg := range bgsOrdered { + otherLAddr, otherPAddr := fs.LV.ResolveAny(bg.LAddr, bg.Size) + if otherLAddr < 0 || otherPAddr.Addr < 0 { + dlog.Errorf(ctx, "... dev[%q] error: could not pair blockgroup laddr=%v (size=%v flags=%v) with a mapping", + dev.Name(), 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, "... dev[%q] error: adding flags from blockgroup: %v", + dev.Name(), err) + } + } +} + +// ScanOneDevice mostly mimics btrfs-progs +// cmds/rescue-chunk-recover.c:scan_one_device(). +func ScanOneDevice(ctx context.Context, dev *btrfs.Device, superblock btrfs.Superblock) (ScanOneDeviceResult, error) { + result := ScanOneDeviceResult{ + FoundNodes: make(map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr), + } + + devSize := dev.Size() + lastProgress := -1 + + err := ScanForNodes(ctx, dev, superblock, func(nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfs.Node], err error) { + if err != nil { + dlog.Infof(ctx, "... dev[%q] error: %v", dev.Name(), err) + return + } + result.FoundNodes[nodeRef.Data.Head.Addr] = append(result.FoundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr) + for i, item := range nodeRef.Data.BodyLeaf { + switch item.Key.ItemType { + case btrfsitem.CHUNK_ITEM_KEY: + chunk, ok := item.Body.(btrfsitem.Chunk) + if !ok { + dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is CHUNK_ITEM_KEY, but struct is %T", + dev.Name(), nodeRef.Addr, i, item.Body) + continue + } + //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found chunk", + // dev.Name(), nodeRef.Addr, i) + result.FoundChunks = append(result.FoundChunks, btrfs.SysChunk{ + Key: item.Key, + Chunk: chunk, + }) + case btrfsitem.BLOCK_GROUP_ITEM_KEY: + bg, ok := item.Body.(btrfsitem.BlockGroup) + if !ok { + dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is BLOCK_GROUP_ITEM_KEY, but struct is %T", + dev.Name(), nodeRef.Addr, i, item.Body) + continue + } + //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found block group", + // dev.Name(), nodeRef.Addr, i) + result.FoundBlockGroups = append(result.FoundBlockGroups, SysBlockGroup{ + Key: item.Key, + BG: bg, + }) + case btrfsitem.DEV_EXTENT_KEY: + devext, ok := item.Body.(btrfsitem.DevExtent) + if !ok { + dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is DEV_EXTENT_KEY, but struct is %T", + dev.Name(), nodeRef.Addr, i, item.Body) + continue + } + //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found dev extent", + // dev.Name(), nodeRef.Addr, i) + result.FoundDevExtents = append(result.FoundDevExtents, SysDevExtent{ + Key: item.Key, + DevExt: devext, + }) + } + } + }, func(pos btrfsvol.PhysicalAddr) { + pct := int(100 * float64(pos) / float64(devSize)) + if pct != lastProgress || pos == devSize { + dlog.Infof(ctx, "... dev[%q] scanned %v%% (found: %v nodes, %v chunks, %v block groups, %v dev extents)", + dev.Name(), pct, + len(result.FoundNodes), + len(result.FoundChunks), + len(result.FoundBlockGroups), + len(result.FoundDevExtents)) + lastProgress = pct + } + }) + + return result, err +} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go b/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go deleted file mode 100644 index d8e8844..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go +++ /dev/null @@ -1,78 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -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/scanforextents/csums.go b/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go deleted file mode 100644 index 0fb4818..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go +++ /dev/null @@ -1,316 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -import ( - "context" - "encoding/gob" - "io" - "math" - "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" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" -) - -// ShortSum ////////////////////////////////////////////////////////// - -type ShortSum string - -// SumRun //////////////////////////////////////////////////////////// - -type SumRun[Addr btrfsvol.IntAddr[Addr]] struct { - // How big a ShortSum is in this Run. - ChecksumSize int - // Base address where this run starts. - Addr Addr - // All of the ShortSums in this run, concatenated together. - // - // This is a 'string' rather than a 'ShortSum' to make it hard - // to accidentally use it as a single sum. - Sums string -} - -func (run SumRun[Addr]) NumSums() int { - return len(run.Sums) / run.ChecksumSize -} - -func (run SumRun[Addr]) Size() btrfsvol.AddrDelta { - return btrfsvol.AddrDelta(run.NumSums()) * btrfsitem.CSumBlockSize -} - -// Get implements diskio.Sequence[int, ShortSum] -func (run SumRun[Addr]) Get(sumIdx int64) (ShortSum, error) { - if sumIdx < 0 || int(sumIdx) >= run.NumSums() { - return "", io.EOF - } - off := int(sumIdx) * run.ChecksumSize - return ShortSum(run.Sums[off : off+run.ChecksumSize]), nil -} - -func (run SumRun[Addr]) SumForAddr(addr Addr) (ShortSum, bool) { - if addr < run.Addr || addr >= run.Addr.Add(run.Size()) { - return "", false - } - off := int((addr-run.Addr)/btrfsitem.CSumBlockSize) * run.ChecksumSize - return ShortSum(run.Sums[off : off+run.ChecksumSize]), true -} - -func (run SumRun[Addr]) Walk(ctx context.Context, fn func(Addr, ShortSum) error) error { - for addr, off := run.Addr, 0; off < len(run.Sums); addr, off = addr+btrfsitem.CSumBlockSize, off+run.ChecksumSize { - if err := ctx.Err(); err != nil { - return err - } - if err := fn(addr, ShortSum(run.Sums[off:off+run.ChecksumSize])); err != nil { - return err - } - } - return nil -} - -// SumRunWithGaps //////////////////////////////////////////////////// - -type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct { - Addr Addr - Size btrfsvol.AddrDelta - Runs []SumRun[Addr] -} - -func (sg SumRunWithGaps[Addr]) NumSums() int { - return int(sg.Size / btrfsitem.CSumBlockSize) -} - -func (sg SumRunWithGaps[Addr]) PctFull() float64 { - total := sg.NumSums() - var full int - for _, run := range sg.Runs { - full += run.NumSums() - } - return float64(full) / float64(total) -} - -func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (ShortSum, error) { - if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) { - return "", io.EOF - } - for _, run := range sg.Runs { - if run.Addr > addr { - return "", diskio.ErrWildcard - } - if run.Addr.Add(run.Size()) <= addr { - continue - } - off := int((addr-run.Addr)/btrfsitem.CSumBlockSize) * run.ChecksumSize - return ShortSum(run.Sums[off : off+run.ChecksumSize]), nil - } - return "", diskio.ErrWildcard -} - -// Get implements diskio.Sequence[int, ShortSum] -func (sg SumRunWithGaps[Addr]) Get(sumIdx int64) (ShortSum, error) { - addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfsitem.CSumBlockSize) - return sg.SumForAddr(addr) -} - -// AllSums /////////////////////////////////////////////////////////// - -type AllSums struct { - Logical []SumRun[btrfsvol.LogicalAddr] - Physical map[btrfsvol.DeviceID]SumRun[btrfsvol.PhysicalAddr] -} - -func (as AllSums) SumForPAddr(paddr btrfsvol.QualifiedPhysicalAddr) (ShortSum, bool) { - run, ok := as.Physical[paddr.Dev] - if !ok { - return "", false - } - return run.SumForAddr(paddr.Addr) -} - -func (as AllSums) RunForLAddr(laddr btrfsvol.LogicalAddr) (SumRun[btrfsvol.LogicalAddr], btrfsvol.LogicalAddr, bool) { - for _, run := range as.Logical { - if run.Addr > laddr { - return SumRun[btrfsvol.LogicalAddr]{}, run.Addr, false - } - if run.Addr.Add(run.Size()) <= laddr { - continue - } - return run, 0, true - } - return SumRun[btrfsvol.LogicalAddr]{}, math.MaxInt64, false -} - -func (as AllSums) SumForLAddr(laddr btrfsvol.LogicalAddr) (ShortSum, bool) { - run, _, ok := as.RunForLAddr(laddr) - if !ok { - return "", false - } - return run.SumForAddr(laddr) -} - -func (as AllSums) WalkLogical(ctx context.Context, fn func(btrfsvol.LogicalAddr, ShortSum) error) error { - for _, run := range as.Logical { - if err := run.Walk(ctx, fn); err != nil { - return err - } - } - return nil -} - -// Read/Write AllSums //////////////////////////////////////////////// - -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 SumEverything(ctx context.Context, fs *btrfs.FS) (AllSums, error) { - var ret AllSums - - // ChecksumSize - var alg btrfssum.CSumType - var csumSize int - if err := func() error { - sb, err := fs.Superblock() - if err != nil { - return err - } - alg = sb.ChecksumType - csumSize = 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) * btrfsitem.CSumBlockSize) - if laddr != curAddr+(btrfsvol.LogicalAddr(curSums.Len()/csumSize)*btrfsitem.CSumBlockSize) { - if curSums.Len() > 0 { - ret.Logical = append(ret.Logical, SumRun[btrfsvol.LogicalAddr]{ - ChecksumSize: csumSize, - Addr: curAddr, - Sums: curSums.String(), - }) - } - curAddr = laddr - curSums.Reset() - } - curSums.Write(sum[:csumSize]) - } - return nil - }, - }, - ) - if curSums.Len() > 0 { - ret.Logical = append(ret.Logical, SumRun[btrfsvol.LogicalAddr]{ - ChecksumSize: csumSize, - 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]SumRun[btrfsvol.PhysicalAddr], 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 / btrfsitem.CSumBlockSize) - sums := make([]byte, numSums*csumSize) - 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*btrfsitem.CSumBlockSize)) - if err != nil { - return err - } - copy(sums[i*csumSize:], sum[:csumSize]) - } - progress(numSums) - sumsStr := string(sums) - mu.Lock() - ret.Physical[devID] = SumRun[btrfsvol.PhysicalAddr]{ - ChecksumSize: csumSize, - Addr: 0, - Sums: 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 -} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/csums_raw.go b/lib/btrfsprogs/btrfsinspect/scanforextents/csums_raw.go deleted file mode 100644 index eae1c4d..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/csums_raw.go +++ /dev/null @@ -1,66 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -import ( - "fmt" - - "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" -) - -func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) { - var dat [btrfsitem.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 [btrfsitem.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*btrfsitem.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)*btrfsitem.CSumBlockSize)] = sum - } - return ret, nil -} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go b/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go deleted file mode 100644 index be6ee06..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go +++ /dev/null @@ -1,79 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -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/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 AllSums, gaps map[btrfsvol.DeviceID][]PhysicalGap, - fn func(btrfsvol.DeviceID, 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, 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/scanforextents/scan.go b/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go deleted file mode 100644 index e980e9c..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go +++ /dev/null @@ -1,309 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -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/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 AllSums) error { - dlog.Info(ctx, "Pairing up blockgroups and sums...") - bgSums := make(map[btrfsvol.LogicalAddr]SumRunWithGaps[btrfsvol.LogicalAddr]) - for i, bgLAddr := range maps.SortedKeys(blockgroups) { - blockgroup := blockgroups[bgLAddr] - runs := 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, 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 SumRun[btrfsvol.PhysicalAddr]) error { - matches, err := diskio.IndexAll[int64, 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[ShortSum][]btrfsvol.LogicalAddr) - var numUnmappedBlocks int64 - if err := sums.WalkLogical(ctx, func(laddr btrfsvol.LogicalAddr, sum 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 - }, - ) -} - -*/ diff --git a/lib/btrfsprogs/btrfsutil/csums.go b/lib/btrfsprogs/btrfsutil/csums.go new file mode 100644 index 0000000..aad1b45 --- /dev/null +++ b/lib/btrfsprogs/btrfsutil/csums.go @@ -0,0 +1,66 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +import ( + "fmt" + + "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" +) + +func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) { + var dat [btrfsitem.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 [btrfsitem.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*btrfsitem.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)*btrfsitem.CSumBlockSize)] = sum + } + return ret, nil +} diff --git a/lib/btrfsprogs/btrfsutil/scan.go b/lib/btrfsprogs/btrfsutil/scan.go deleted file mode 100644 index d5d3d8d..0000000 --- a/lib/btrfsprogs/btrfsutil/scan.go +++ /dev/null @@ -1,57 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfsutil - -import ( - "context" - "errors" - "fmt" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" -) - -// ScanForNodes mimics btrfs-progs -// cmds/rescue-chunk-recover.c:scan_one_device(), except rather than -// doing something itself when it finds a node, it simply calls a -// callback function. -func ScanForNodes(ctx context.Context, dev *btrfs.Device, sb btrfs.Superblock, fn func(*diskio.Ref[btrfsvol.PhysicalAddr, btrfs.Node], error), prog func(btrfsvol.PhysicalAddr)) error { - devSize := dev.Size() - - if sb.NodeSize < sb.SectorSize { - return fmt.Errorf("node_size(%v) < sector_size(%v)", - sb.NodeSize, sb.SectorSize) - } - - for pos := btrfsvol.PhysicalAddr(0); pos+btrfsvol.PhysicalAddr(sb.NodeSize) < devSize; pos += btrfsvol.PhysicalAddr(sb.SectorSize) { - if ctx.Err() != nil { - return ctx.Err() - } - if slices.Contains(pos, btrfs.SuperblockAddrs) { - //fmt.Printf("sector@%v is a superblock\n", pos) - continue - } - - if prog != nil { - prog(pos) - } - - nodeRef, err := btrfs.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, nil) - if err != nil && errors.Is(err, btrfs.ErrNotANode) { - continue - } - fn(nodeRef, err) - - pos += btrfsvol.PhysicalAddr(sb.NodeSize) - btrfsvol.PhysicalAddr(sb.SectorSize) - } - - if prog != nil { - prog(devSize) - } - - return nil -} -- cgit v1.2.3-2-g168b