summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/btrfs/btrfstree/ops.go25
-rw-r--r--lib/btrfs/btrfstree/path.go6
-rw-r--r--lib/btrfs/btrfstree/readnode.go54
-rw-r--r--lib/btrfs/btrfstree/root.go2
-rw-r--r--lib/btrfs/btrfstree/types_node.go10
-rw-r--r--lib/btrfs/io3_btree.go64
-rw-r--r--lib/btrfs/io4_fs.go2
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go30
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go94
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go107
-rw-r--r--lib/btrfsprogs/btrfsutil/broken_btree.go6
-rw-r--r--lib/btrfsprogs/btrfsutil/walk.go3
12 files changed, 325 insertions, 78 deletions
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 <lukeshu@lukeshu.com>
+//
+// 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 <lukeshu@lukeshu.com>
+//
+// 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 <lukeshu@lukeshu.com>
+//
+// 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 {
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2024-07-15 10:56:55 +0000