From 5411e6b88bdccff020c4de25c065a0ba4710589c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 29 Aug 2022 23:18:26 -0600 Subject: wip --- .../btrfsinspect/rebuildnodes/rebuildnodes.go | 9 +- .../btrfsinspect/rebuildnodes/s2_classify.go | 166 +++++++++++++++++++++ .../btrfsinspect/rebuildnodes/s2_lostandfound.go | 116 -------------- .../btrfsinspect/rebuildnodes/s3_reattach.go | 122 +++++++++++++++ .../btrfsinspect/rebuildnodes/s3_reinit.go | 126 ---------------- .../btrfsinspect/rebuildnodes/s4_reattach.go | 122 --------------- 6 files changed, 290 insertions(+), 371 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go delete 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 941ea4c..a9ff24d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go @@ -31,17 +31,12 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec uuidMap: uuidMap, } - foundRoots, err := lostAndFoundNodes(ctx, nfs, nodeScanResults) + orphanedNodes, rebuiltNodes, err := classifyNodes(ctx, nfs, nodeScanResults) if err != nil { return nil, err } - rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, nodeScanResults, foundRoots) - if err != nil { - return nil, err - } - - if err := reAttachNodes(ctx, nfs, foundRoots, rebuiltNodes); err != nil { + if err := reAttachNodes(ctx, nfs, orphanedNodes, rebuiltNodes); err != nil { return nil, err } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go new file mode 100644 index 0000000..9fb5bf5 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go @@ -0,0 +1,166 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +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" +) + +// 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. +func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDevicesResult) ( + orphanedNodes map[btrfsvol.LogicalAddr]struct{}, + rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode, + 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{}) + progress := func() { + done := len(visitedNodes) + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || done == total { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, total) + lastPct = pct + } + } + + rebuiltNodes = make(map[btrfsvol.LogicalAddr]*RebuiltNode) + walkHandler := btrfstree.TreeWalkHandler{ + PreNode: func(path btrfstree.TreePath) error { + addr := path.Node(-1).ToNodeAddr + if _, alreadyVisited := visitedNodes[addr]; alreadyVisited { + // Can happen because of COW subvolumes; + // this is really a DAG not a tree. + return iofs.SkipDir + } + return nil + }, + Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { + addr := path.Node(-1).ToNodeAddr + visitedNodes[addr] = struct{}{} + progress() + 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, + } + } + return err + }, + } + + btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ + TreeWalkHandler: walkHandler, + Err: func(err *btrfsutil.WalkError) { + // do nothing + if !errors.Is(err, btrfstree.ErrNotANode) && !strings.Contains(err.Error(), "read: could not map logical address") { + dlog.Errorf(ctx, "dbg walk err: %v", err) + } + }, + }) + + // Start with 'orphanedRoots' as a complete set of all orphaned nodes, and then delete + // non-root entries from it. + orphanedNodes = make(map[btrfsvol.LogicalAddr]struct{}) + for _, devResults := range scanResults { + for laddr := range devResults.FoundNodes { + if _, attached := visitedNodes[laddr]; !attached { + orphanedNodes[laddr] = struct{}{} + } + } + } + if len(visitedNodes)+len(orphanedNodes) != total { + panic("should not happen") + } + dlog.Infof(ctx, + "... (finished processing %v attached nodes, proceeding to process %v lost nodes, for a total of %v)", + len(visitedNodes), len(orphanedNodes), len(visitedNodes)+len(orphanedNodes)) + for _, potentialRoot := range maps.SortedKeys(orphanedNodes) { + walkHandler.Node = func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { + addr := path.Node(-1).ToNodeAddr + if addr != potentialRoot { + delete(orphanedNodes, addr) + } + visitedNodes[addr] = struct{}{} + progress() + return nil + } + walkFromNode(ctx, fs, potentialRoot, + func(err *btrfstree.TreeError) { + // do nothing + }, + walkHandler, + ) + } + + if len(visitedNodes) != total { + panic("should not happen") + } + + dlog.Infof(ctx, "... identified %d orphaned nodes and re-built %d nodes", len(orphanedNodes), len(rebuiltNodes)) + return orphanedNodes, rebuiltNodes, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go deleted file mode 100644 index 4efaeab..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go +++ /dev/null @@ -1,116 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "errors" - iofs "io/fs" - "strings" - - "github.com/datawire/dlib/dlog" - - "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/diskio" -) - -// lostAndFoundNodes returns the set of nodes don't have another node -// claiming it as a child. -func lostAndFoundNodes(ctx context.Context, fs _FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]struct{}, error) { - dlog.Info(ctx, "Identifying lost+found nodes...") - - lastPct := -1 - total := countNodes(nodeScanResults) - progress := func(done int) { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } - } - - visitedNodes := make(map[btrfsvol.LogicalAddr]struct{}) - btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: btrfstree.TreeWalkHandler{ - // Don't use `PreNode` because we don't want to run this on bad nodes. - Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - addr := path.Node(-1).ToNodeAddr - if _, alreadyVisited := visitedNodes[addr]; alreadyVisited { - // Can happen because of COW subvolumes; - // this is really a DAG not a tree. - return iofs.SkipDir - } - visitedNodes[addr] = struct{}{} - progress(len(visitedNodes)) - return nil - }, - }, - Err: func(err *btrfsutil.WalkError) { - // do nothing - if !errors.Is(err, btrfstree.ErrNotANode) && !strings.Contains(err.Error(), "read: could not map logical address") { - dlog.Errorf(ctx, "dbg walk err: %v", err) - } - }, - }) - - orphanedNodes := make(map[btrfsvol.LogicalAddr]int) - for _, devResults := range nodeScanResults { - for laddr := range devResults.FoundNodes { - if _, attached := visitedNodes[laddr]; !attached { - orphanedNodes[laddr] = 0 - } - } - } - if len(visitedNodes)+len(orphanedNodes) != total { - panic("should not happen") - } - dlog.Infof(ctx, - "... (finished processing %v attached nodes, proceeding to process %v lost nodes, for a total of %v)", - len(visitedNodes), len(orphanedNodes), len(visitedNodes)+len(orphanedNodes)) - - // 'orphanedRoots' is a subset of 'orphanedNodes'; start with - // it as the complete orphanedNodes, and then remove entries. - orphanedRoots := make(map[btrfsvol.LogicalAddr]struct{}, len(orphanedNodes)) - for node := range orphanedNodes { - orphanedRoots[node] = struct{}{} - } - for potentialRoot := range orphanedNodes { - if orphanedNodes[potentialRoot] > 1 { - continue - } - walkFromNode(ctx, fs, potentialRoot, - func(err *btrfstree.TreeError) { - // do nothing - }, - btrfstree.TreeWalkHandler{ - // Don't use `PreNode` because we don't want to run this on bad - // nodes (it'd screw up `len(visitedNodes)`). - Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - addr := path.Node(-1).ToNodeAddr - if addr != potentialRoot { - delete(orphanedRoots, addr) - } - if _, alreadyVisited := visitedNodes[addr]; alreadyVisited { - return iofs.SkipDir - } - visitedNodes[addr] = struct{}{} - progress(len(visitedNodes)) - return nil - }, - }, - ) - } - - if len(visitedNodes) != total { - panic("should not happen") - } - - dlog.Infof(ctx, "... identified %d lost+found nodes", len(orphanedRoots)) - return orphanedRoots, nil -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go new file mode 100644 index 0000000..2b18aca --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go @@ -0,0 +1,122 @@ +// 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 deleted file mode 100644 index 49bc989..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go +++ /dev/null @@ -1,126 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "fmt" - iofs "io/fs" - "reflect" - - "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" -) - -func reInitBrokenNodes(ctx context.Context, fs _FS, nodeScanResults btrfsinspect.ScanDevicesResult, foundRoots map[btrfsvol.LogicalAddr]struct{}) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { - dlog.Info(ctx, "Initializing nodes to re-build...") - - 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") - } - - lastPct := -1 - total := countNodes(nodeScanResults) - progress := func(done int) { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } - } - - rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode) - visitedNodes := make(map[btrfsvol.LogicalAddr]struct{}) - walkHandler := btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - addr := path.Node(-1).ToNodeAddr - if _, alreadyVisited := visitedNodes[addr]; alreadyVisited { - // Can happen because of COW subvolumes; - // this is really a DAG not a tree. - return iofs.SkipDir - } - visitedNodes[addr] = struct{}{} - progress(len(visitedNodes)) - 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, - } - } - return err - }, - } - - // We use WalkAllTrees instead of just iterating over - // nodeScanResults so that we don't need to specifically check - // if any of the root nodes referenced directly by the - // superblock are dead. - progress(len(visitedNodes)) - btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - Err: func(err *btrfsutil.WalkError) { - // do nothing - }, - TreeWalkHandler: walkHandler, - }) - for foundRoot := range foundRoots { - walkFromNode(ctx, fs, foundRoot, - func(err *btrfstree.TreeError) { - // do nothing - }, - walkHandler) - } - - if len(visitedNodes) != total { - panic("should not happen") - } - - 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 deleted file mode 100644 index 32269fc..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_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, foundRoots 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 foundRoots to the gaps. - dlog.Info(ctx, "... attaching nodes...") - lastPct := -1 - progress := func(done int) { - pct := int(100 * float64(done) / float64(len(foundRoots))) - if pct != lastPct || done == len(foundRoots) { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, len(foundRoots)) - lastPct = pct - } - } - numAttached := 0 - for i, foundLAddr := range maps.SortedKeys(foundRoots) { - 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(foundRoots)) - dlog.Info(ctx, "... ... done attaching") - - dlog.Infof(ctx, "... re-attached %d nodes (%v%% success rate)", - numAttached, int(100*float64(numAttached)/float64(len(foundRoots)))) - return nil -} -- cgit v1.2.3-2-g168b