From 1145f9a47c8e368dd7f83ce19e9f06b9eba7b0ad Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 16 Jul 2022 02:55:58 -0600 Subject: store sums in a big ol slice --- .../btrfsinspect/scanforextents/blockgroups.go | 101 ++++++++ lib/btrfsprogs/btrfsinspect/scanforextents/csum.go | 129 ---------- .../btrfsinspect/scanforextents/csums.go | 267 ++++++++++++++++++++ lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go | 2 +- lib/btrfsprogs/btrfsinspect/scanforextents/scan.go | 194 +++++++++++++++ .../btrfsinspect/scanforextents/scanforextents.go | 276 --------------------- .../btrfsinspect/scanforextents/scanfornodes.go | 101 -------- 7 files changed, 563 insertions(+), 507 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/csum.go create mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/csums.go create mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/scan.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go delete mode 100644 lib/btrfsprogs/btrfsinspect/scanforextents/scanfornodes.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go b/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go new file mode 100644 index 0000000..99009e6 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/scanforextents/blockgroups.go @@ -0,0 +1,101 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package scanforextents + +import ( + "encoding/json" + "fmt" + "os" + + "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" +) + +type NodeScanResults = map[btrfsvol.DeviceID]btrfsinspect.ScanOneDevResult + +func ReadNodeScanResults(fs *btrfs.FS, filename string) (*BlockGroupTree, 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 +} + +type BlockGroup struct { + LAddr btrfsvol.LogicalAddr + Size btrfsvol.AddrDelta + Flags btrfsvol.BlockGroupFlags +} + +type BlockGroupTree = containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], BlockGroup] + +func LookupBlockGroup(tree *BlockGroupTree, laddr btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) *BlockGroup { + a := struct { + LAddr btrfsvol.LogicalAddr + Size btrfsvol.AddrDelta + }{ + LAddr: laddr, + Size: size, + } + node := tree.Search(func(b BlockGroup) int { + switch { + case a.LAddr.Add(a.Size) <= b.LAddr: + // 'a' is wholly to the left of 'b'. + return -1 + case b.LAddr.Add(b.Size) <= a.LAddr: + // 'a' is wholly to the right of 'b'. + return 1 + default: + // There is some overlap. + return 0 + } + }) + if node == nil { + return nil + } + bg := node.Value + return &bg +} + +func ReduceScanResults(fs *btrfs.FS, scanResults NodeScanResults) (*BlockGroupTree, error) { + 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{}{} + } + } + bgTree := &BlockGroupTree{ + KeyFn: func(bg BlockGroup) containers.NativeOrdered[btrfsvol.LogicalAddr] { + return containers.NativeOrdered[btrfsvol.LogicalAddr]{Val: bg.LAddr} + }, + } + for bg := range bgSet { + if laddr, _ := fs.LV.ResolveAny(bg.LAddr, bg.Size); laddr >= 0 { + continue + } + if LookupBlockGroup(bgTree, bg.LAddr, bg.Size) != nil { + return nil, fmt.Errorf("found block groups are inconsistent") + } + bgTree.Insert(bg) + } + return bgTree, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/csum.go b/lib/btrfsprogs/btrfsinspect/scanforextents/csum.go deleted file mode 100644 index ec46833..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/csum.go +++ /dev/null @@ -1,129 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -import ( - "context" - "errors" - "fmt" - - "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" -) - -const csumBlockSize = 4 * 1024 - -func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) { - var dat [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 [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) -} - -type shortSum string - -func readCSumTree(ctx context.Context, fs btrfs.Trees) map[shortSum][]btrfsvol.LogicalAddr { - sb, _ := fs.Superblock() - - sum2laddrs := make(map[shortSum][]btrfsvol.LogicalAddr) - var cntUnmapped, cntErr, cntMismatch, cntValid int - 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, treeSum := range body.Sums { - laddr := btrfsvol.LogicalAddr(item.Key.Offset) + (btrfsvol.LogicalAddr(i) * csumBlockSize) - readSum, err := ChecksumLogical(fs, sb.ChecksumType, laddr) - if err != nil { - if errors.Is(err, btrfsvol.ErrCouldNotMap) { - cntUnmapped++ - treeShortSum := shortSum(treeSum[:body.ChecksumSize]) - sum2laddrs[treeShortSum] = append(sum2laddrs[treeShortSum], laddr) - continue - } - dlog.Error(ctx, err) - cntErr++ - continue - } - if readSum != treeSum { - dlog.Errorf(ctx, "checksum mismatch at laddr=%v: CSUM_TREE=%v != read=%v", - laddr, treeSum, readSum) - cntMismatch++ - continue - } - cntValid++ - } - return nil - }, - }, - ) - - total := cntErr + cntUnmapped + cntMismatch + cntValid - dlog.Infof(ctx, " checksum errors : %v", cntErr) - dlog.Infof(ctx, " unmapped checksums : %v", cntUnmapped) - dlog.Infof(ctx, " mismatched checksums : %v", cntMismatch) - dlog.Infof(ctx, " valid checksums : %v", cntValid) - dlog.Infof(ctx, " -------------------------:") - dlog.Infof(ctx, " total checksums : %v", total) - dlog.Infof(ctx, " distinct unmapped : %v", len(sum2laddrs)) - - return sum2laddrs -} - -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*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)*csumBlockSize)] = sum - } - return ret, nil -} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go b/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go new file mode 100644 index 0000000..6a42946 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/scanforextents/csums.go @@ -0,0 +1,267 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package scanforextents + +import ( + "context" + "encoding/gob" + "fmt" + "io" + "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" +) + +const csumBlockSize = 4 * 1024 + +type ShortSum string + +type LogicalSumRun struct { + Addr btrfsvol.LogicalAddr + Sums string +} + +type AllSums struct { + ChecksumSize int + Logical []LogicalSumRun + Physical map[btrfsvol.DeviceID]string +} + +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 (as AllSums) SumForPAddr(paddr btrfsvol.QualifiedPhysicalAddr) (ShortSum, bool) { + run, ok := as.Physical[paddr.Dev] + if !ok { + return "", false + } + off := int(paddr.Addr/csumBlockSize) * as.ChecksumSize + if off+as.ChecksumSize > len(run) { + return "", false + } + return ShortSum(run[off : off+as.ChecksumSize]), true +} + +func (as AllSums) SumForLAddr(laddr btrfsvol.LogicalAddr) (ShortSum, bool) { + for _, run := range as.Logical { + size := btrfsvol.AddrDelta(len(run.Sums)/as.ChecksumSize) * csumBlockSize + if run.Addr > laddr { + return "", false + } + if run.Addr.Add(size) <= laddr { + continue + } + off := int(laddr.Sub(run.Addr)/csumBlockSize) * as.ChecksumSize + return ShortSum(run.Sums[off : off+as.ChecksumSize]), true + } + return "", false +} + +func (as AllSums) WalkLogical(fn func(btrfsvol.LogicalAddr, ShortSum) error) error { + for _, run := range as.Logical { + for laddr, off := run.Addr, 0; off < len(run.Sums); laddr, off = laddr+csumBlockSize, off+as.ChecksumSize { + if err := fn(laddr, ShortSum(run.Sums[off:off+as.ChecksumSize])); err != nil { + return err + } + } + } + return nil +} + +func SumEverything(ctx context.Context, fs *btrfs.FS) (AllSums, error) { + var ret AllSums + + // ChecksumSize + var alg btrfssum.CSumType + if err := func() error { + sb, err := fs.Superblock() + if err != nil { + return err + } + alg = sb.ChecksumType + ret.ChecksumSize = 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) * csumBlockSize) + if laddr != curAddr { + if curSums.Len() > 0 { + ret.Logical = append(ret.Logical, LogicalSumRun{ + Addr: curAddr, + Sums: curSums.String(), + }) + } + curAddr = laddr + curSums.Reset() + } + curSums.Write(sum[:ret.ChecksumSize]) + } + return nil + }, + }, + ) + if curSums.Len() > 0 { + ret.Logical = append(ret.Logical, LogicalSumRun{ + 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]string, 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 / csumBlockSize) + sums := make([]byte, numSums*ret.ChecksumSize) + 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*csumBlockSize)) + if err != nil { + return err + } + copy(sums[i*ret.ChecksumSize:], sum[:ret.ChecksumSize]) + } + progress(numSums) + sumsStr := string(sums) + mu.Lock() + ret.Physical[devID] = 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 +} + +func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) { + var dat [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 [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*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)*csumBlockSize)] = sum + } + return ret, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go b/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go index 90351a5..f67b498 100644 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go +++ b/lib/btrfsprogs/btrfsinspect/scanforextents/gaps.go @@ -52,7 +52,7 @@ func roundUp[T constraints.Integer](x, multiple T) T { return ((x + multiple - 1) / multiple) * multiple } -func WalkGapsOneDev(ctx context.Context, dev *btrfs.Device, +func WalkGaps(ctx context.Context, gaps []PhysicalGap, blockSize btrfsvol.PhysicalAddr, progress func(cur, total int64), main func(btrfsvol.PhysicalAddr) error, diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go b/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go new file mode 100644 index 0000000..1b04b3c --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/scanforextents/scan.go @@ -0,0 +1,194 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package scanforextents + +import ( + "context" + "errors" + "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/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" +) + +func ScanForExtents(ctx context.Context, fs *btrfs.FS, blockgroups *BlockGroupTree, sums AllSums) error { + sb, err := fs.Superblock() + if err != nil { + return err + } + + dlog.Info(ctx, "Reverse-indexing and validating logical sums...") + sum2laddrs := make(map[ShortSum][]btrfsvol.LogicalAddr) + if err := sums.WalkLogical(func(laddr btrfsvol.LogicalAddr, expShortSum ShortSum) error { + if err := ctx.Err(); err != nil { + return err + } + readSum, err := ChecksumLogical(fs, sb.ChecksumType, laddr) + if err != nil { + if errors.Is(err, btrfsvol.ErrCouldNotMap) { + sum2laddrs[expShortSum] = append(sum2laddrs[expShortSum], laddr) + return nil + } + return err + } + readShortSum := ShortSum(readSum[:sums.ChecksumSize]) + if readShortSum != expShortSum { + return fmt.Errorf("checksum mismatch at laddr=%v: CSUM_TREE=%x != read=%x", + laddr, []byte(expShortSum), []byte(readShortSum)) + } + return nil + }); err != nil { + return err + } + dlog.Info(ctx, "... done reverse-indexing and validating") + + dlog.Info(ctx, "Cross-referencing sums (and blockgroups) to re-construct mappings...") + newMappings := &ExtentMappings{ + InLV: &fs.LV, + InBlockGroups: blockgroups, + InSums: sums, + InReverseSums: sum2laddrs, + } + devs := fs.LV.PhysicalVolumes() + gaps := ListPhysicalGaps(fs) + for _, devID := range maps.SortedKeys(gaps) { + if err := newMappings.ScanOneDev(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, csumBlockSize) + if blockgroup == nil { + return btrfsvol.Mapping{ + LAddr: laddr, + PAddr: paddr, + Size: 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 += 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) ScanOneDev( + 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) + + lastProgress := -1 + potentialMappings := 0 + return WalkGaps(ctx, gaps, csumBlockSize, + func(curBlock, totalBlocks int64) { + pct := int(100 * float64(curBlock) / float64(totalBlocks)) + if pct != lastProgress || curBlock == totalBlocks { + dlog.Infof(ctx, "... dev[%q] scanned %v%% (constructed %v potential mappings)", + devName, pct, potentialMappings) + lastProgress = pct + } + }, + func(paddr btrfsvol.PhysicalAddr) error { + qpaddr := btrfsvol.QualifiedPhysicalAddr{ + Dev: devID, + Addr: paddr, + } + sum, _ := em.InSums.SumForPAddr(qpaddr) + for _, laddr := range em.InReverseSums[sum] { + mapping, ok := em.considerMapping(ctx, laddr, qpaddr) + if !ok { + continue + } + em.addMapping(sum, mapping) + potentialMappings++ + } + + return nil + }, + ) +} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go b/lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go deleted file mode 100644 index 72c9201..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/scanforextents.go +++ /dev/null @@ -1,276 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -import ( - "context" - "runtime" - "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/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/containers" -) - -func ScanForExtents(ctx context.Context, fs *btrfs.FS, blockGroups *BlockGroupTree) error { - treeReader := btrfsutil.NewBrokenTrees(ctx, fs) - - dlog.Info(ctx, "Reading checksum tree...") - sum2laddrs := readCSumTree(ctx, treeReader) - if len(sum2laddrs) == 0 { - dlog.Info(ctx, "No unmapped checksums") - return nil - } - runtime.GC() - dlog.Info(ctx, "...GC'd") - - devs := fs.LV.PhysicalVolumes() - gaps := ListPhysicalGaps(fs) - - newMappings := &ExtentMappings{ - InFS: treeReader, - InLV: &fs.LV, - InSum2laddrs: sum2laddrs, - InBlockGroups: blockGroups, - } - - dlog.Info(ctx, "Scanning devices...") - grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{}) - for devID := range gaps { - dev := devs[devID] - devGaps := gaps[devID] - grp.Go(dev.Name(), func(ctx context.Context) error { - return newMappings.ScanOneDev(ctx, dev, devGaps) - }) - } - if err := grp.Wait(); err != nil { - return err - } - - 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) - } - } - - return nil -} - -type csumCacheEntry struct { - Sum shortSum - Err error -} - -type csumCachePhysKey struct { - Dev *btrfs.Device - Addr btrfsvol.PhysicalAddr -} - -type ExtentMappings struct { - // input - InFS btrfs.Trees - InLV *btrfsvol.LogicalVolume[*btrfs.Device] - InSum2laddrs map[shortSum][]btrfsvol.LogicalAddr - InBlockGroups *BlockGroupTree - - // state - initOnce sync.Once - initErr error - alg btrfssum.CSumType - internedMappingsMu sync.Mutex - internedMappings map[btrfsvol.Mapping]*btrfsvol.Mapping - - cacheLogical containers.LRUCache[btrfsvol.LogicalAddr, csumCacheEntry] - cachePhysical containers.LRUCache[csumCachePhysKey, csumCacheEntry] - - // output - sum2lock map[shortSum]*sync.Mutex - OutSum2mappings map[shortSum][]*btrfsvol.Mapping -} - -func (em *ExtentMappings) init() error { - em.initOnce.Do(func() { - sb, err := em.InFS.Superblock() - if err != nil { - em.initErr = err - return - } - em.alg = sb.ChecksumType - em.internedMappings = make(map[btrfsvol.Mapping]*btrfsvol.Mapping) - em.sum2lock = make(map[shortSum]*sync.Mutex, len(em.InSum2laddrs)) - for sum := range em.InSum2laddrs { - em.sum2lock[sum] = new(sync.Mutex) - } - em.OutSum2mappings = make(map[shortSum][]*btrfsvol.Mapping) - }) - return em.initErr -} - -func (em *ExtentMappings) logicalSum(laddr btrfsvol.LogicalAddr) (shortSum, error) { - entry, ok := em.cacheLogical.Get(laddr) - if !ok { - sums, err := LookupCSum(em.InFS, em.alg, laddr) - if err != nil { - entry.Err = err - em.cacheLogical.Add(laddr, entry) - } else { - for laddr, sum := range sums { - entry.Sum = shortSum(sum[:em.alg.Size()]) - em.cacheLogical.Add(laddr, entry) - } - sum := sums[laddr] - entry.Sum = shortSum(sum[:em.alg.Size()]) - } - } - return entry.Sum, entry.Err -} - -func (em *ExtentMappings) physicalSum(dev *btrfs.Device, paddr btrfsvol.PhysicalAddr) (shortSum, error) { - key := csumCachePhysKey{ - Dev: dev, - Addr: paddr, - } - entry, ok := em.cachePhysical.Get(key) - if !ok { - sum, err := ChecksumPhysical(dev, em.alg, paddr) - entry.Sum = shortSum(sum[:em.alg.Size()]) - entry.Err = err - em.cachePhysical.Add(key, entry) - } - return entry.Sum, entry.Err -} - -func (em *ExtentMappings) considerMapping(ctx context.Context, dev *btrfs.Device, laddr btrfsvol.LogicalAddr, paddr btrfsvol.QualifiedPhysicalAddr) (btrfsvol.Mapping, bool) { - blockgroup := LookupBlockGroup(em.InBlockGroups, laddr, csumBlockSize) - if blockgroup == nil { - return btrfsvol.Mapping{ - LAddr: laddr, - PAddr: paddr, - Size: 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 += csumBlockSize { - if err := ctx.Err(); err != nil { - return btrfsvol.Mapping{}, false - } - expCSum, err := em.logicalSum(mapping.LAddr.Add(offset)) - if err != nil { - continue - } - if err := ctx.Err(); err != nil { - return btrfsvol.Mapping{}, false - } - actCSum, err := em.physicalSum(dev, mapping.PAddr.Addr.Add(offset)) - if err != nil { - return btrfsvol.Mapping{}, false - } - if actCSum != expCSum { - return btrfsvol.Mapping{}, false - } - } - return mapping, true -} - -func (em *ExtentMappings) addMapping(sum shortSum, mapping btrfsvol.Mapping) { - em.internedMappingsMu.Lock() - interned := em.internedMappings[mapping] - if interned == nil { - interned = &mapping - em.internedMappings[mapping] = interned - } - em.internedMappingsMu.Unlock() - - em.sum2lock[sum].Lock() - em.OutSum2mappings[sum] = append(em.OutSum2mappings[sum], interned) - em.sum2lock[sum].Unlock() -} - -func (em *ExtentMappings) ScanOneDev(ctx context.Context, dev *btrfs.Device, gaps []PhysicalGap) error { - if err := em.init(); err != nil { - return err - } - devID := func() btrfsvol.DeviceID { - sb, _ := dev.Superblock() - return sb.DevItem.DevID - }() - - dlog.Infof(ctx, "... dev[%q] Scanning for extents...", dev.Name()) - - sumSize := em.alg.Size() - - lastProgress := -1 - potentialMappings := 0 - return WalkGapsOneDev(ctx, dev, gaps, csumBlockSize, - func(curBlock, totalBlocks int64) { - pct := int(100 * float64(curBlock) / float64(totalBlocks)) - if pct != lastProgress || curBlock == totalBlocks { - dlog.Infof(ctx, "... dev[%q] scanned %v%% (constructed %v potential mappings)", - dev.Name(), pct, potentialMappings) - lastProgress = pct - } - }, - func(paddr btrfsvol.PhysicalAddr) error { - if err := ctx.Err(); err != nil { - return err - } - sum, err := ChecksumPhysical(dev, em.alg, paddr) - if err != nil { - dlog.Errorf(ctx, "... dev[%s] error: checksumming paddr=%v: %v", - dev.Name(), paddr, err) - return nil - } - shortSum := shortSum(sum[:sumSize]) - - for _, laddr := range em.InSum2laddrs[shortSum] { - if err := ctx.Err(); err != nil { - return err - } - mapping, ok := em.considerMapping(ctx, dev, laddr, btrfsvol.QualifiedPhysicalAddr{ - Dev: devID, - Addr: paddr, - }) - if err := ctx.Err(); err != nil { - return err - } - if !ok { - continue - } - em.addMapping(shortSum, mapping) - potentialMappings++ - } - - return nil - }, - ) -} diff --git a/lib/btrfsprogs/btrfsinspect/scanforextents/scanfornodes.go b/lib/btrfsprogs/btrfsinspect/scanforextents/scanfornodes.go deleted file mode 100644 index 99009e6..0000000 --- a/lib/btrfsprogs/btrfsinspect/scanforextents/scanfornodes.go +++ /dev/null @@ -1,101 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package scanforextents - -import ( - "encoding/json" - "fmt" - "os" - - "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" -) - -type NodeScanResults = map[btrfsvol.DeviceID]btrfsinspect.ScanOneDevResult - -func ReadNodeScanResults(fs *btrfs.FS, filename string) (*BlockGroupTree, 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 -} - -type BlockGroup struct { - LAddr btrfsvol.LogicalAddr - Size btrfsvol.AddrDelta - Flags btrfsvol.BlockGroupFlags -} - -type BlockGroupTree = containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], BlockGroup] - -func LookupBlockGroup(tree *BlockGroupTree, laddr btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) *BlockGroup { - a := struct { - LAddr btrfsvol.LogicalAddr - Size btrfsvol.AddrDelta - }{ - LAddr: laddr, - Size: size, - } - node := tree.Search(func(b BlockGroup) int { - switch { - case a.LAddr.Add(a.Size) <= b.LAddr: - // 'a' is wholly to the left of 'b'. - return -1 - case b.LAddr.Add(b.Size) <= a.LAddr: - // 'a' is wholly to the right of 'b'. - return 1 - default: - // There is some overlap. - return 0 - } - }) - if node == nil { - return nil - } - bg := node.Value - return &bg -} - -func ReduceScanResults(fs *btrfs.FS, scanResults NodeScanResults) (*BlockGroupTree, error) { - 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{}{} - } - } - bgTree := &BlockGroupTree{ - KeyFn: func(bg BlockGroup) containers.NativeOrdered[btrfsvol.LogicalAddr] { - return containers.NativeOrdered[btrfsvol.LogicalAddr]{Val: bg.LAddr} - }, - } - for bg := range bgSet { - if laddr, _ := fs.LV.ResolveAny(bg.LAddr, bg.Size); laddr >= 0 { - continue - } - if LookupBlockGroup(bgTree, bg.LAddr, bg.Size) != nil { - return nil, fmt.Errorf("found block groups are inconsistent") - } - bgTree.Insert(bg) - } - return bgTree, nil -} -- cgit v1.2.3-2-g168b