From 8aea2c35c9475293c89293a148134c0e6d5c4e7b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 28 Aug 2022 16:55:06 -0600 Subject: wip --- lib/btrfs/btrfstree/ops.go | 25 ++--- lib/btrfs/btrfstree/path.go | 6 +- lib/btrfs/btrfstree/readnode.go | 54 +++++++++++ lib/btrfs/btrfstree/root.go | 2 +- lib/btrfs/btrfstree/types_node.go | 10 +- lib/btrfs/io3_btree.go | 64 ++++-------- lib/btrfs/io4_fs.go | 2 +- .../btrfsinspect/rebuildnodes/rebuildnodes.go | 30 ++++-- .../btrfsinspect/rebuildnodes/rebuilttrees.go | 94 ++++++++++++++++++ .../btrfsinspect/rebuildnodes/uuidmap.go | 107 +++++++++++++++++++++ lib/btrfsprogs/btrfsutil/broken_btree.go | 6 +- lib/btrfsprogs/btrfsutil/walk.go | 3 +- 12 files changed, 325 insertions(+), 78 deletions(-) create mode 100644 lib/btrfs/btrfstree/readnode.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go index 83c08c4..02511f5 100644 --- a/lib/btrfs/btrfstree/ops.go +++ b/lib/btrfs/btrfstree/ops.go @@ -20,7 +20,8 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -type Trees interface { +// TreeOperator is an interface for performing basic btree operations. +type TreeOperator interface { // TreeWalk walks a tree, triggering callbacks for every node, // key-pointer, and item; as well as for any errors encountered. // @@ -91,12 +92,12 @@ type NodeSource interface { ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) } -type TreesImpl struct { +type TreeOperatorImpl struct { NodeSource } // TreeWalk implements the 'Trees' interface. -func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { sb, err := fs.Superblock() if err != nil { errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err}) @@ -109,9 +110,9 @@ func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHan fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) } -// TreeWalk is a utility function to help with implementing the 'Trees' +// TreeWalk is a utility method to help with implementing the 'Trees'. // interface. -func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := TreePath{{ FromTree: rootInfo.TreeID, FromGeneration: rootInfo.Generation, @@ -122,7 +123,7 @@ func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandl fs.treeWalk(ctx, path, errHandle, cbs) } -func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) { if ctx.Err() != nil { return } @@ -233,7 +234,7 @@ func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func( } } -func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { +func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { path := TreePath{{ FromTree: treeRoot.TreeID, FromGeneration: treeRoot.Generation, @@ -303,7 +304,7 @@ func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) } } -func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { +func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { var err error path = path.DeepCopy() @@ -359,7 +360,7 @@ func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, N return path, node, nil } -func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { +func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { var err error path = path.DeepCopy() @@ -431,7 +432,7 @@ func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, N } // TreeSearch implements the 'Trees' interface. -func (fs TreesImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) { +func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) { sb, err := fs.Superblock() if err != nil { return Item{}, err @@ -455,7 +456,7 @@ func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int { } // TreeLookup implements the 'Trees' interface. -func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { +func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp)) if err != nil { err = fmt.Errorf("item with key=%v: %w", key, err) @@ -464,7 +465,7 @@ func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, } // TreeSearchAll implements the 'Trees' interface. -func (fs TreesImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) { +func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) { sb, err := fs.Superblock() if err != nil { return nil, err diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index 99461a4..4a4d66e 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -14,7 +14,11 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" ) -// - The first element will always have an ItemIdx of -1. +// TreePath is a path from the superblock (i.e. the root of the btrfs +// system) to the a node or item within one of the btrees in the +// system. +// +// - The first element will always have an ItemIdx of -1. // // - For .Item() callbacks, the last element will always have a // NodeAddr of 0. diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go new file mode 100644 index 0000000..bb80d20 --- /dev/null +++ b/lib/btrfs/btrfstree/readnode.go @@ -0,0 +1,54 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "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" +) + +// FSReadNode is a utility function to help with implementing the +// 'NodeSource' interface. +func FSReadNode( + fs interface { + diskio.File[btrfsvol.LogicalAddr] + Superblock() (*Superblock, error) + ParentTree(btrfsprim.ObjID) (btrfsprim.ObjID, bool) + }, + path TreePath, +) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) { + sb, err := fs.Superblock() + if err != nil { + return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err) + } + + var treeParents []btrfsprim.ObjID + checkOwner := func(owner btrfsprim.ObjID) error { + exp := path.Node(-1).FromTree + for { + if owner == exp { + return nil + } + treeParents = append(treeParents, exp) + var ok bool + exp, ok = fs.ParentTree(exp) + if !ok { + return fmt.Errorf("expected owner in %v but claims to have owner=%v", + treeParents, owner) + } + } + } + + return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr}, + Level: containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel}, + MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration}, + Owner: checkOwner, + }) +} diff --git a/lib/btrfs/btrfstree/root.go b/lib/btrfs/btrfstree/root.go index 41aac69..a233ef0 100644 --- a/lib/btrfs/btrfstree/root.go +++ b/lib/btrfs/btrfstree/root.go @@ -23,7 +23,7 @@ type TreeRoot struct { // LookupTreeRoot is a utility function to help with implementing the 'Trees' // interface. -func LookupTreeRoot(fs Trees, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { +func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { switch treeID { case btrfsprim.ROOT_TREE_OBJECTID: return &TreeRoot{ diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index aecdf9c..6718fbe 100644 --- a/lib/btrfs/btrfstree/types_node.go +++ b/lib/btrfs/btrfstree/types_node.go @@ -17,7 +17,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) type NodeFlags uint64 @@ -386,7 +385,7 @@ type NodeExpectations struct { // Things knowable from the parent. Level containers.Optional[uint8] MaxGeneration containers.Optional[btrfsprim.Generation] - Owner []btrfsprim.ObjID + Owner func(btrfsprim.ObjID) error } func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) { @@ -437,9 +436,10 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected generation<=%v but claims to be generation=%v", addr, exp.MaxGeneration.Val, nodeRef.Data.Head.Generation) } - if len(exp.Owner) > 0 && !slices.Contains(nodeRef.Data.Head.Owner, exp.Owner) { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected owner in %v but claims to have owner=%v", - addr, exp.Owner, nodeRef.Data.Head.Owner) + if exp.Owner != nil { + if err := exp.Owner(nodeRef.Data.Head.Owner); err != nil { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) + } } // parse (main) diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 31cf857..8455eee 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -6,7 +6,6 @@ package btrfs import ( "context" - "fmt" "github.com/datawire/dlib/dlog" @@ -14,24 +13,23 @@ import ( "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/diskio" ) func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - btrfstree.TreesImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) + btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) } func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - return btrfstree.TreesImpl{NodeSource: fs}.TreeLookup(treeID, key) + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) } func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { - return btrfstree.TreesImpl{NodeSource: fs}.TreeSearch(treeID, fn) + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) } func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { - return btrfstree.TreesImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) } -var _ btrfstree.Trees = (*FS)(nil) +var _ btrfstree.TreeOperator = (*FS)(nil) func (fs *FS) populateTreeUUIDs(ctx context.Context) { if fs.cacheObjID2UUID == nil || fs.cacheUUID2ObjID == nil || fs.cacheTreeParent == nil { @@ -59,44 +57,24 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) { } } -var noParents = make(map[btrfsprim.ObjID]struct{}) - -func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { - sb, err := fs.Superblock() - if err != nil { - return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err) +func (fs *FS) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { + ctx := context.TODO() + if tree < btrfsprim.FIRST_FREE_OBJECTID { + return 0, false } - - potentialOwners := []btrfsprim.ObjID{ - path.Node(-1).FromTree, + fs.populateTreeUUIDs(ctx) + parentUUID := fs.cacheTreeParent[tree] + if parentUUID == (btrfsprim.UUID{}) { + return 0, false } - if potentialOwners[0] >= btrfsprim.FIRST_FREE_OBJECTID { - ctx := context.TODO() - fs.populateTreeUUIDs(ctx) - for potentialOwners[len(potentialOwners)-1] >= btrfsprim.FIRST_FREE_OBJECTID { - objID := potentialOwners[len(potentialOwners)-1] - parentUUID := fs.cacheTreeParent[objID] - if parentUUID == (btrfsprim.UUID{}) { - if _, already := noParents[objID]; !already { - dlog.Infof(ctx, "dbg: objID=%v has no parent", objID) - noParents[objID] = struct{}{} - } - break - } - dlog.Infof(ctx, "dbg: parent of objID=%v is %v", objID, parentUUID) - parentObjID, ok := fs.cacheUUID2ObjID[parentUUID] - if !ok { - dlog.Errorf(ctx, "dbg: could not resolve parentUUID=%v to an ObjID", parentUUID) - break - } - potentialOwners = append(potentialOwners, parentObjID) - } + parentObjID, ok := fs.cacheUUID2ObjID[parentUUID] + if !ok { + dlog.Errorf(ctx, "dbg: could not resolve parentUUID=%v to an ObjID", parentUUID) + return 0, false } + return parentObjID, true +} - return btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr}, - Level: containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel}, - MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration}, - Owner: potentialOwners, - }) +func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { + return btrfstree.FSReadNode(fs, path) } diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 7bfcc00..8751078 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -61,7 +61,7 @@ type File struct { type Subvolume struct { FS interface { - btrfstree.Trees + btrfstree.TreeOperator Superblock() (*btrfstree.Superblock, error) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go index cac9483..5afa783 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go @@ -27,22 +27,32 @@ import ( ) func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { + uuidMap, err := buildTreeUUIDMap(ctx, fs, nodeScanResults) + if err != nil { + return nil, err + } + + nfs := &RebuiltTrees{ + inner: fs, + uuidMap: uuidMap, + } + dlog.Info(ctx, "Identifying lost+found nodes...") - foundRoots, err := lostAndFoundNodes(ctx, fs, nodeScanResults) + foundRoots, err := lostAndFoundNodes(ctx, nfs, nodeScanResults) if err != nil { return nil, err } dlog.Infof(ctx, "... identified %d lost+found nodes", len(foundRoots)) dlog.Info(ctx, "Initializing nodes to re-build...") - rebuiltNodes, err := reInitBrokenNodes(ctx, fs, nodeScanResults, foundRoots) + rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, nodeScanResults, foundRoots) if err != nil { return nil, err } dlog.Infof(ctx, "Initialized %d nodes", len(rebuiltNodes)) dlog.Info(ctx, "Attaching lost+found nodes to rebuilt nodes...") - if err := reAttachNodes(ctx, fs, foundRoots, rebuiltNodes); err != nil { + if err := reAttachNodes(ctx, nfs, foundRoots, rebuiltNodes); err != nil { return nil, err } dlog.Info(ctx, "... done attaching") @@ -68,7 +78,7 @@ func keyMm(key btrfsprim.Key) btrfsprim.Key { return key } -func spanOfTreePath(fs *btrfs.FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { +func spanOfTreePath(fs _FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { // tree root error if len(path) == 0 { return btrfsprim.Key{}, maxKey @@ -100,7 +110,7 @@ func spanOfTreePath(fs *btrfs.FS, path btrfstree.TreePath) (btrfsprim.Key, btrfs return low, high } -func walkFromNode(ctx context.Context, fs *btrfs.FS, nodeAddr btrfsvol.LogicalAddr, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { +func walkFromNode(ctx context.Context, fs _FS, nodeAddr btrfsvol.LogicalAddr, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { sb, _ := fs.Superblock() nodeRef, _ := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, nodeAddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: nodeAddr}, @@ -114,7 +124,7 @@ func walkFromNode(ctx context.Context, fs *btrfs.FS, nodeAddr btrfsvol.LogicalAd Level: nodeRef.Data.Head.Level, Generation: nodeRef.Data.Head.Generation, } - btrfstree.TreesImpl{NodeSource: fs}.RawTreeWalk(ctx, treeInfo, errHandle, cbs) + btrfstree.TreeOperatorImpl{NodeSource: fs}.RawTreeWalk(ctx, treeInfo, errHandle, cbs) } func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { @@ -125,7 +135,7 @@ func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { return cnt } -func lostAndFoundNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]struct{}, error) { +func lostAndFoundNodes(ctx context.Context, fs _FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]struct{}, error) { lastPct := -1 total := countNodes(nodeScanResults) progress := func(done int) { @@ -210,7 +220,7 @@ func lostAndFoundNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi return orphanedRoots, nil } -func getChunkTreeUUID(ctx context.Context, fs *btrfs.FS) (btrfsprim.UUID, bool) { +func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) { ctx, cancel := context.WithCancel(ctx) var ret btrfsprim.UUID var retOK bool @@ -237,7 +247,7 @@ type RebuiltNode struct { btrfstree.Node } -func reInitBrokenNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult, foundRoots map[btrfsvol.LogicalAddr]struct{}) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { +func reInitBrokenNodes(ctx context.Context, fs _FS, nodeScanResults btrfsinspect.ScanDevicesResult, foundRoots map[btrfsvol.LogicalAddr]struct{}) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { sb, err := fs.Superblock() if err != nil { return nil, err @@ -317,7 +327,7 @@ func reInitBrokenNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi return rebuiltNodes, nil } -func reAttachNodes(ctx context.Context, fs *btrfs.FS, foundRoots map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { +func reAttachNodes(ctx context.Context, fs _FS, foundRoots map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { // Index 'rebuiltNodes' for fast lookups. gaps := make(map[btrfsprim.ObjID]map[uint8][]*RebuiltNode) maxLevel := make(map[btrfsprim.ObjID]uint8) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go new file mode 100644 index 0000000..17116c6 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go @@ -0,0 +1,94 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "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/diskio" +) + +type RebuiltTrees struct { + inner *btrfs.FS + uuidMap treeUUIDMap + nodes map[btrfsvol.LogicalAddr]*RebuiltNode +} + +type _FS interface { + diskio.File[btrfsvol.LogicalAddr] + ParentTree(btrfsprim.ObjID) (btrfsprim.ObjID, bool) + btrfstree.NodeSource + btrfstree.TreeOperator +} + +// diskio.File + +func (fs *RebuiltTrees) Name() string { return fs.inner.Name() } +func (fs *RebuiltTrees) Size() btrfsvol.LogicalAddr { return fs.inner.Size() } +func (fs *RebuiltTrees) Close() error { return fs.inner.Close() } +func (fs *RebuiltTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { + sb, err := fs.Superblock() + if err != nil { + return 0, err + } + if rebuilt, ok := fs.nodes[off]; ok && len(p) == int(sb.NodeSize) { + bs, err := rebuilt.Node.MarshalBinary() + if err != nil { + panic(fmt.Errorf("should not happen: %w", err)) + } + if len(p) != len(bs) { + panic(fmt.Errorf("should not happen: sb.NodeSize=%v but node marshaled to %v", sb.NodeSize, len(bs))) + } + return copy(p, bs), nil + } + return fs.inner.ReadAt(p, off) +} +func (fs *RebuiltTrees) WriteAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { + return fs.inner.WriteAt(p, off) +} + +// btrfstree.NodeSource backend + +func (fs *RebuiltTrees) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { + if tree < btrfsprim.FIRST_FREE_OBJECTID { + return 0, false + } + parentUUID := fs.uuidMap.TreeParent[tree] + if parentUUID == (btrfsprim.UUID{}) { + return 0, false + } + parentObjID, ok := fs.uuidMap.UUID2ObjID[parentUUID] + if !ok { + panic(fmt.Errorf("should not happen: could not resolve parentUUID=%v to an ObjID", parentUUID)) + } + return parentObjID, true +} + +// btrfstree.NodeSource + +func (fs *RebuiltTrees) Superblock() (*btrfstree.Superblock, error) { return fs.inner.Superblock() } +func (fs *RebuiltTrees) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { + return btrfstree.FSReadNode(fs, path) +} + +// btrfstree.TreeOperator + +func (fs *RebuiltTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { + btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) +} +func (fs *RebuiltTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) +} +func (fs *RebuiltTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) +} +func (fs *RebuiltTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go new file mode 100644 index 0000000..0179a6e --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go @@ -0,0 +1,107 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "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/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/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" +) + +type treeUUIDMap struct { + ObjID2UUID map[btrfsprim.ObjID]btrfsprim.UUID + UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID + TreeParent map[btrfsprim.ObjID]btrfsprim.UUID +} + +func maybeSet[K, V comparable](m map[K]V, k K, v V) error { + if other, conflict := m[k]; conflict && other != v { + return fmt.Errorf("conflict: %v can't have both %v and %v", k, other, v) + } + m[k] = v + return nil +} + +func buildTreeUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (treeUUIDMap, error) { + dlog.Infof(ctx, "Building table of tree ObjID←→UUID...") + + sb, err := fs.Superblock() + if err != nil { + return treeUUIDMap{}, nil + } + + lastPct := -1 + total := countNodes(scanResults) + done := 0 + progress := func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || done == total { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, total) + lastPct = pct + } + } + + ret := treeUUIDMap{ + ObjID2UUID: make(map[btrfsprim.ObjID]btrfsprim.UUID), + UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID), + TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID), + } + treeIDs := make(map[btrfsprim.ObjID]struct{}) + + progress() + for _, devResults := range scanResults { + for laddr := range devResults.FoundNodes { + nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, + }) + if err != nil { + return treeUUIDMap{}, nil + } + for _, item := range nodeRef.Data.BodyLeaf { + itemBody, ok := item.Body.(btrfsitem.Root) + if !ok { + continue + } + if err := maybeSet(ret.ObjID2UUID, item.Key.ObjectID, itemBody.UUID); err != nil { + return treeUUIDMap{}, err + } + if err := maybeSet(ret.TreeParent, item.Key.ObjectID, itemBody.ParentUUID); err != nil { + return treeUUIDMap{}, err + } + if err := maybeSet(ret.UUID2ObjID, itemBody.UUID, item.Key.ObjectID); err != nil { + return treeUUIDMap{}, err + } + } + treeIDs[nodeRef.Data.Head.Owner] = struct{}{} + done++ + progress() + } + } + progress() + + missing := make(map[btrfsprim.ObjID]struct{}) + for treeID := range treeIDs { + if _, ok := ret.ObjID2UUID[treeID]; !ok { + missing[treeID] = struct{}{} + } + } + if len(missing) > 0 { + return treeUUIDMap{}, fmt.Errorf("could not find root items for trees %v", maps.SortedKeys(missing)) + } + + dlog.Info(ctx, ".. done building table") + return ret, nil +} diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index 6afaceb..7341d94 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -102,7 +102,7 @@ type brokenTrees struct { treeIndexes map[btrfsprim.ObjID]cachedIndex } -var _ btrfstree.Trees = (*brokenTrees)(nil) +var _ btrfstree.TreeOperator = (*brokenTrees)(nil) // NewBrokenTrees wraps a *btrfs.FS to support looking up information // from broken trees. @@ -123,7 +123,7 @@ var _ btrfstree.Trees = (*brokenTrees)(nil) // tree, and re-implements TreeLookup, TreeSearch, and TreeSearchAll // using that index. func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) interface { - btrfstree.Trees + btrfstree.TreeOperator Superblock() (*btrfstree.Superblock, error) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) } { @@ -171,7 +171,7 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) cachedIndex { KeyFn: func(iv indexValue) btrfsprim.Key { return iv.Key }, } dlog.Infof(bt.ctx, "indexing tree %v...", treeID) - btrfstree.TreesImpl{NodeSource: bt.inner}.RawTreeWalk( + btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk( bt.ctx, *treeRoot, func(err *btrfstree.TreeError) { diff --git a/lib/btrfsprogs/btrfsutil/walk.go b/lib/btrfsprogs/btrfsutil/walk.go index 2809737..355976a 100644 --- a/lib/btrfsprogs/btrfsutil/walk.go +++ b/lib/btrfsprogs/btrfsutil/walk.go @@ -8,7 +8,6 @@ import ( "context" "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/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" @@ -37,7 +36,7 @@ type WalkAllTreesHandler struct { // WalkAllTrees walks all trees in a *btrfs.FS. Rather than returning // an error, it calls errCb each time an error is encountered. The // error will always be of type WalkError. -func WalkAllTrees(ctx context.Context, fs *btrfs.FS, cbs WalkAllTreesHandler) { +func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTreesHandler) { var treeName string trees := []struct { -- cgit v1.2.3-54-g00ecf