diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2022-08-30 00:30:21 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2022-08-30 21:29:22 -0600 |
commit | 6543bbc9ffeaa2ba28b4d1ba5d6db509213b5e5d (patch) | |
tree | 614eaebbbe9b5ffa29f4373c677a0800bb78a303 /lib/btrfsprogs/btrfsinspect/rebuildnodes | |
parent | 5411e6b88bdccff020c4de25c065a0ba4710589c (diff) |
wip
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes')
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go | 14 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go | 65 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go | 137 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go (renamed from lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go) | 3 |
4 files changed, 158 insertions, 61 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go index a9ff24d..173529e 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go @@ -31,7 +31,12 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec uuidMap: uuidMap, } - orphanedNodes, rebuiltNodes, err := classifyNodes(ctx, nfs, nodeScanResults) + orphanedNodes, badNodes, err := classifyNodes(ctx, nfs, nodeScanResults) + if err != nil { + return nil, err + } + + rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, badNodes) if err != nil { return nil, err } @@ -138,10 +143,3 @@ func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) { }) return ret, retOK } - -type RebuiltNode struct { - Err string - MinKey, MaxKey btrfsprim.Key - InTrees containers.Set[btrfsprim.ObjID] - btrfstree.Node -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go index 9fb5bf5..36e5395 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go @@ -7,43 +7,35 @@ package rebuildnodes import ( "context" "errors" - "fmt" iofs "io/fs" - "reflect" "strings" "github.com/datawire/dlib/dlog" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "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/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 badNode struct { + Err string + Path btrfstree.TreePath +} + // classifyNodes returns // // 1. the set of nodes don't have another node claiming it as a child, and -// 2. the set of bad-nodes, with reconstructed headers filled in. +// 2. the list of bad nodes (in no particular order) func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDevicesResult) ( orphanedNodes map[btrfsvol.LogicalAddr]struct{}, - rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode, + badNodes []badNode, err error, ) { dlog.Info(ctx, "Walking trees to identify orphan and broken nodes...") - sb, err := fs.Superblock() - if err != nil { - return nil, nil, err - } - chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs) - if !ok { - return nil, nil, fmt.Errorf("could not look up chunk tree UUID") - } - lastPct := -1 total := countNodes(scanResults) visitedNodes := make(map[btrfsvol.LogicalAddr]struct{}) @@ -57,7 +49,6 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev } } - rebuiltNodes = make(map[btrfsvol.LogicalAddr]*RebuiltNode) walkHandler := btrfstree.TreeWalkHandler{ PreNode: func(path btrfstree.TreePath) error { addr := path.Node(-1).ToNodeAddr @@ -75,40 +66,10 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev return nil }, BadNode: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error { - node := btrfstree.Node{ - Size: sb.NodeSize, - ChecksumType: sb.ChecksumType, - Head: btrfstree.NodeHeader{ - MetadataUUID: sb.EffectiveMetadataUUID(), - Addr: path.Node(-1).ToNodeAddr, - ChunkTreeUUID: chunkTreeUUID, - //Owner: TBD, // see RebuiltNode.InTrees - Generation: path.Node(-1).FromGeneration, - Level: path.Node(-1).ToNodeLevel, - }, - } - min, max := spanOfTreePath(fs, path) - if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok { - if !reflect.DeepEqual(other.Node, node) { - dlog.Errorf(ctx, "... mismatch: %v != %v", node, other.Node) - return err - } - if min.Cmp(other.MinKey) > 0 { // if min > other.MinKey { - other.MinKey = min // take the max of the two - } - if max.Cmp(other.MaxKey) < 0 { // if max < other.MaxKey { - other.MaxKey = max // take the min of the two - } - other.InTrees.Insert(path.Node(-1).FromTree) - } else { - rebuiltNodes[path.Node(-1).ToNodeAddr] = &RebuiltNode{ - Err: err.Error(), - MinKey: min, - MaxKey: max, - InTrees: containers.Set[btrfsprim.ObjID]{path.Node(-1).FromTree: struct{}{}}, - Node: node, - } - } + badNodes = append(badNodes, badNode{ + Err: err.Error(), + Path: path.DeepCopy(), + }) return err }, } @@ -161,6 +122,6 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev panic("should not happen") } - dlog.Infof(ctx, "... identified %d orphaned nodes and re-built %d nodes", len(orphanedNodes), len(rebuiltNodes)) - return orphanedNodes, rebuiltNodes, nil + dlog.Infof(ctx, "... identified %d orphaned nodes and %d bad nodes", len(orphanedNodes), len(badNodes)) + return orphanedNodes, badNodes, nil } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go new file mode 100644 index 0000000..a4b8f0f --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go @@ -0,0 +1,137 @@ +// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "fmt" + "reflect" + "sort" + + "github.com/datawire/dlib/dlog" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +type RebuiltNode struct { + Err string + MinKey, MaxKey btrfsprim.Key + InTrees containers.Set[btrfsprim.ObjID] + btrfstree.Node +} + +func (a RebuiltNode) Compat(b RebuiltNode) bool { + a.Node.Head.Generation = b.Node.Head.Generation + return reflect.DeepEqual(a.Node, b.Node) +} + +func (a RebuiltNode) Merge(b RebuiltNode) (RebuiltNode, error) { + if !a.Compat(b) { + switch { + case a.Node.Head.Generation > b.Node.Head.Generation: + return a, nil + case a.Node.Head.Generation < b.Node.Head.Generation: + return b, nil + default: + return a, fmt.Errorf("mismatch: %v != %v", a, b) + } + } + + // take the broadest region + if a.MinKey.Cmp(b.MinKey) > 0 { // if a.MinKey > b.MinKey { + a.MinKey = b.MinKey // take the min of the two + } + if a.MaxKey.Cmp(b.MaxKey) < 0 { // if a.MaxKey < b.MaxKey { + a.MaxKey = b.MaxKey // take the min of the two + } + + // take the highest generation + a.Node.Head.Generation = slices.Max(a.Node.Head.Generation, b.Node.Head.Generation) + + // take the union + a.InTrees.InsertFrom(b.InTrees) + + return a, nil +} + +func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { + dlog.Info(ctx, "Re-initializing bad nodes...") + + sb, err := fs.Superblock() + if err != nil { + return nil, err + } + chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs) + if !ok { + return nil, fmt.Errorf("could not look up chunk tree UUID") + } + + sort.Slice(badNodes, func(i, j int) bool { + iGen := badNodes[i].Path.Node(-1).FromGeneration + jGen := badNodes[j].Path.Node(-1).FromGeneration + switch { + case iGen < jGen: + return true + case iGen > jGen: + return false + default: + iAddr := badNodes[i].Path.Node(-1).ToNodeAddr + jAddr := badNodes[j].Path.Node(-1).ToNodeAddr + return iAddr < jAddr + } + }) + + lastPct := -1 + progress := func(done int) { + pct := int(100 * float64(done) / float64(len(badNodes))) + if pct != lastPct || done == len(badNodes) { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, len(badNodes)) + lastPct = pct + } + } + + rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode) + for i, badNode := range badNodes { + progress(i) + path := badNode.Path + + min, max := spanOfTreePath(fs, path) + node := RebuiltNode{ + Err: err.Error(), + MinKey: min, + MaxKey: max, + InTrees: containers.Set[btrfsprim.ObjID]{path.Node(-1).FromTree: struct{}{}}, + Node: btrfstree.Node{ + Size: sb.NodeSize, + ChecksumType: sb.ChecksumType, + Head: btrfstree.NodeHeader{ + MetadataUUID: sb.EffectiveMetadataUUID(), + Addr: path.Node(-1).ToNodeAddr, + ChunkTreeUUID: chunkTreeUUID, + //Owner: TBD, // see RebuiltNode.InTrees + Generation: path.Node(-1).FromGeneration, + Level: path.Node(-1).ToNodeLevel, + }, + }, + } + if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok { + *other, err = other.Merge(node) + if err != nil { + dlog.Errorf(ctx, "... %v", err) + } + } else { + rebuiltNodes[path.Node(-1).ToNodeAddr] = &node + } + } + progress(len(badNodes)) + + dlog.Infof(ctx, "... initialized %d nodes", len(rebuiltNodes)) + return rebuiltNodes, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go index 2b18aca..28bd834 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go @@ -19,7 +19,7 @@ import ( ) func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { - dlog.Info(ctx, "Attaching lost+found nodes to rebuilt nodes...") + dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...") sb, err := fs.Superblock() if err != nil { @@ -105,6 +105,7 @@ func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.Logic BlockPtr: foundLAddr, Generation: foundRef.Data.Head.Generation, }) + parent.Head.Generation = slices.Max(parent.Head.Generation, foundRef.Data.Head.Generation) attached = true numAttached++ } |