From 6543bbc9ffeaa2ba28b4d1ba5d6db509213b5e5d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 30 Aug 2022 00:30:21 -0600 Subject: wip --- .../btrfsinspect/rebuildnodes/rebuildnodes.go | 14 +-- .../btrfsinspect/rebuildnodes/s2_classify.go | 65 ++-------- .../btrfsinspect/rebuildnodes/s3_reattach.go | 122 ------------------ .../btrfsinspect/rebuildnodes/s3_reinit.go | 137 +++++++++++++++++++++ .../btrfsinspect/rebuildnodes/s4_reattach.go | 123 ++++++++++++++++++ lib/containers/set.go | 13 +- 6 files changed, 290 insertions(+), 184 deletions(-) delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go (limited to 'lib') 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_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go deleted file mode 100644 index 2b18aca..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go +++ /dev/null @@ -1,122 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "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/maps" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" -) - -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...") - - sb, err := fs.Superblock() - if err != nil { - return err - } - - // Index 'rebuiltNodes' for fast lookups. - dlog.Info(ctx, "... indexing rebuilt nodes...") - gaps := make(map[btrfsprim.ObjID]map[uint8][]*RebuiltNode) - maxLevel := make(map[btrfsprim.ObjID]uint8) - for _, node := range rebuiltNodes { - for treeID := range node.InTrees { - maxLevel[treeID] = slices.Max(maxLevel[treeID], node.Head.Level) - if gaps[treeID] == nil { - gaps[treeID] = make(map[uint8][]*RebuiltNode) - } - gaps[treeID][node.Head.Level] = append(gaps[treeID][node.Head.Level], node) - } - } - for _, byTreeID := range gaps { - for _, slice := range byTreeID { - sort.Slice(slice, func(i, j int) bool { - return slice[i].MinKey.Cmp(slice[j].MinKey) < 0 - }) - } - } - dlog.Info(ctx, "... done indexing") - - // Attach orphanedNodes to the gaps. - dlog.Info(ctx, "... attaching nodes...") - lastPct := -1 - progress := func(done int) { - pct := int(100 * float64(done) / float64(len(orphanedNodes))) - if pct != lastPct || done == len(orphanedNodes) { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, len(orphanedNodes)) - lastPct = pct - } - } - numAttached := 0 - for i, foundLAddr := range maps.SortedKeys(orphanedNodes) { - progress(i) - foundRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: foundLAddr}, - }) - if foundRef == nil { - return err - } - foundMinKey, ok := foundRef.Data.MinItem() - if !ok { - continue - } - foundMaxKey, ok := foundRef.Data.MaxItem() - if !ok { - continue - } - treeGaps := gaps[foundRef.Data.Head.Owner] - var attached bool - for level := foundRef.Data.Head.Level + 1; treeGaps != nil && level <= maxLevel[foundRef.Data.Head.Owner] && !attached; level++ { - parentGen, ok := treeGaps[level] - if !ok { - continue - } - parentIdx, ok := slices.Search(parentGen, func(parent *RebuiltNode) int { - switch { - case foundMinKey.Cmp(parent.MinKey) < 0: - // 'parent' is too far right - return -1 - case foundMaxKey.Cmp(parent.MaxKey) > 0: - // 'parent' is too far left - return 1 - default: - // just right - return 0 - } - }) - if !ok { - continue - } - parent := parentGen[parentIdx] - parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ - Key: foundMinKey, - BlockPtr: foundLAddr, - Generation: foundRef.Data.Head.Generation, - }) - attached = true - numAttached++ - } - if !attached { - dlog.Errorf(ctx, "could not find a broken node to attach node to reattach node@%v to", - foundRef.Addr) - } - } - progress(len(orphanedNodes)) - dlog.Info(ctx, "... ... done attaching") - - dlog.Infof(ctx, "... re-attached %d nodes (%v%% success rate)", - numAttached, int(100*float64(numAttached)/float64(len(orphanedNodes)))) - return 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 +// +// 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/s4_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go new file mode 100644 index 0000000..28bd834 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go @@ -0,0 +1,123 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "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/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { + dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...") + + sb, err := fs.Superblock() + if err != nil { + return err + } + + // Index 'rebuiltNodes' for fast lookups. + dlog.Info(ctx, "... indexing rebuilt nodes...") + gaps := make(map[btrfsprim.ObjID]map[uint8][]*RebuiltNode) + maxLevel := make(map[btrfsprim.ObjID]uint8) + for _, node := range rebuiltNodes { + for treeID := range node.InTrees { + maxLevel[treeID] = slices.Max(maxLevel[treeID], node.Head.Level) + if gaps[treeID] == nil { + gaps[treeID] = make(map[uint8][]*RebuiltNode) + } + gaps[treeID][node.Head.Level] = append(gaps[treeID][node.Head.Level], node) + } + } + for _, byTreeID := range gaps { + for _, slice := range byTreeID { + sort.Slice(slice, func(i, j int) bool { + return slice[i].MinKey.Cmp(slice[j].MinKey) < 0 + }) + } + } + dlog.Info(ctx, "... done indexing") + + // Attach orphanedNodes to the gaps. + dlog.Info(ctx, "... attaching nodes...") + lastPct := -1 + progress := func(done int) { + pct := int(100 * float64(done) / float64(len(orphanedNodes))) + if pct != lastPct || done == len(orphanedNodes) { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, len(orphanedNodes)) + lastPct = pct + } + } + numAttached := 0 + for i, foundLAddr := range maps.SortedKeys(orphanedNodes) { + progress(i) + foundRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: foundLAddr}, + }) + if foundRef == nil { + return err + } + foundMinKey, ok := foundRef.Data.MinItem() + if !ok { + continue + } + foundMaxKey, ok := foundRef.Data.MaxItem() + if !ok { + continue + } + treeGaps := gaps[foundRef.Data.Head.Owner] + var attached bool + for level := foundRef.Data.Head.Level + 1; treeGaps != nil && level <= maxLevel[foundRef.Data.Head.Owner] && !attached; level++ { + parentGen, ok := treeGaps[level] + if !ok { + continue + } + parentIdx, ok := slices.Search(parentGen, func(parent *RebuiltNode) int { + switch { + case foundMinKey.Cmp(parent.MinKey) < 0: + // 'parent' is too far right + return -1 + case foundMaxKey.Cmp(parent.MaxKey) > 0: + // 'parent' is too far left + return 1 + default: + // just right + return 0 + } + }) + if !ok { + continue + } + parent := parentGen[parentIdx] + parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ + Key: foundMinKey, + BlockPtr: foundLAddr, + Generation: foundRef.Data.Head.Generation, + }) + parent.Head.Generation = slices.Max(parent.Head.Generation, foundRef.Data.Head.Generation) + attached = true + numAttached++ + } + if !attached { + dlog.Errorf(ctx, "could not find a broken node to attach node to reattach node@%v to", + foundRef.Addr) + } + } + progress(len(orphanedNodes)) + dlog.Info(ctx, "... ... done attaching") + + dlog.Infof(ctx, "... re-attached %d nodes (%v%% success rate)", + numAttached, int(100*float64(numAttached)/float64(len(orphanedNodes)))) + return nil +} diff --git a/lib/containers/set.go b/lib/containers/set.go index e20b5be..4e40894 100644 --- a/lib/containers/set.go +++ b/lib/containers/set.go @@ -46,14 +46,23 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error { } func (o *Set[T]) Insert(v T) { - if o == nil { + if *o == nil { *o = Set[T]{} } (*o)[v] = struct{}{} } +func (o *Set[T]) InsertFrom(p Set[T]) { + if *o == nil { + *o = Set[T]{} + } + for v := range p { + (*o)[v] = struct{}{} + } +} + func (o *Set[T]) Delete(v T) { - if o == nil { + if *o == nil { return } delete(*o, v) -- cgit v1.2.3-2-g168b