summaryrefslogtreecommitdiff
path: root/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go')
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go135
1 files changed, 9 insertions, 126 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
index c32ae8e..40ace46 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
@@ -6,7 +6,6 @@ package rebuildnodes
import (
"context"
- "fmt"
"github.com/datawire/dlib/dlog"
@@ -16,78 +15,14 @@ import (
"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/btrfsinspect/rebuildnodes/graph"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
"git.lukeshu.com/btrfs-progs-ng/lib/maps"
)
-type nodeData struct {
- Level uint8
- Generation btrfsprim.Generation
- Owner btrfsprim.ObjID
- NumItems uint32
- MinItem btrfsprim.Key
- MaxItem btrfsprim.Key
-}
-
-type kpData struct {
- FromTree btrfsprim.ObjID
- FromNode btrfsvol.LogicalAddr
- FromItem int
-
- ToNode btrfsvol.LogicalAddr
- ToLevel uint8
- ToKey btrfsprim.Key
- ToGeneration btrfsprim.Generation
-}
-
-func (kp kpData) String() string {
- return fmt.Sprintf(`{t:%v,n:%v}[%d]->{n:%v,l:%v,g:%v,k:(%d,%v,%d)}`,
- kp.FromTree, kp.FromNode, kp.FromItem,
- kp.ToNode, kp.ToLevel, kp.ToGeneration,
- kp.ToKey.ObjectID,
- kp.ToKey.ItemType,
- kp.ToKey.Offset)
-}
-
-type nodeGraph struct {
- Nodes map[btrfsvol.LogicalAddr]nodeData
- BadNodes map[btrfsvol.LogicalAddr]error
- EdgesFrom map[btrfsvol.LogicalAddr][]*kpData
- EdgesTo map[btrfsvol.LogicalAddr][]*kpData
-}
-
-func (g nodeGraph) insertEdge(kp kpData) {
- ptr := &kp
- if kp.ToNode == 0 {
- panic("kp.ToNode should not be zero")
- }
- g.EdgesFrom[kp.FromNode] = append(g.EdgesFrom[kp.FromNode], ptr)
- g.EdgesTo[kp.ToNode] = append(g.EdgesTo[kp.ToNode], ptr)
-}
-
-func (g nodeGraph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
- treeInfo, err := btrfstree.LookupTreeRoot(nil, sb, treeID)
- if err != nil {
- // This shouldn't ever happen for treeIDs that are
- // mentioned directly in the superblock; which are the
- // only trees for which we should call
- // .insertTreeRoot().
- panic(fmt.Errorf("LookupTreeRoot(%v): %w", treeID, err))
- }
- if treeInfo.RootNode == 0 {
- return
- }
- g.insertEdge(kpData{
- FromTree: treeID,
- ToNode: treeInfo.RootNode,
- ToLevel: treeInfo.Level,
- ToGeneration: treeInfo.Generation,
- })
-}
-
type scanResult struct {
uuidMap
- nodeGraph
+ nodeGraph *graph.Graph
}
func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (*scanResult, error) {
@@ -101,7 +36,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
lastPct := -1
total := countNodes(scanResults)
done := 0
- progress := func() {
+ progress := func(done, total int) {
pct := int(100 * float64(done) / float64(total))
if pct != lastPct || done == total {
dlog.Infof(ctx, "... %v%% (%v/%v)",
@@ -118,31 +53,17 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
SeenTrees: make(containers.Set[btrfsprim.ObjID]),
},
- nodeGraph: nodeGraph{
- Nodes: make(map[btrfsvol.LogicalAddr]nodeData),
- BadNodes: make(map[btrfsvol.LogicalAddr]error),
- EdgesFrom: make(map[btrfsvol.LogicalAddr][]*kpData),
- EdgesTo: make(map[btrfsvol.LogicalAddr][]*kpData),
- },
+ nodeGraph: graph.New(*sb),
}
// These 4 trees are mentioned directly in the superblock, so
// they are always seen.
- //
- // 1
ret.SeenTrees.Insert(btrfsprim.ROOT_TREE_OBJECTID)
- ret.insertTreeRoot(*sb, btrfsprim.ROOT_TREE_OBJECTID)
- // 2
ret.SeenTrees.Insert(btrfsprim.CHUNK_TREE_OBJECTID)
- ret.insertTreeRoot(*sb, btrfsprim.CHUNK_TREE_OBJECTID)
- // 3
ret.SeenTrees.Insert(btrfsprim.TREE_LOG_OBJECTID)
- ret.insertTreeRoot(*sb, btrfsprim.TREE_LOG_OBJECTID)
- // 4
ret.SeenTrees.Insert(btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
- ret.insertTreeRoot(*sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
- progress()
+ progress(done, total)
for _, devResults := range scanResults {
for laddr := range devResults.FoundNodes {
nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
@@ -168,13 +89,6 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
return nil, err
}
ret.SeenTrees.Insert(item.Key.ObjectID)
- // graph building
- ret.insertEdge(kpData{
- FromTree: item.Key.ObjectID,
- ToNode: itemBody.ByteNr,
- ToLevel: itemBody.Level,
- ToGeneration: itemBody.Generation,
- })
case btrfsitem.UUIDMap:
uuid := btrfsitem.KeyToUUID(item.Key)
if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, itemBody.ObjID, uuid); err != nil {
@@ -188,28 +102,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
ret.SeenTrees.Insert(nodeRef.Data.Head.Owner)
// graph building
- ret.Nodes[laddr] = nodeData{
- Level: nodeRef.Data.Head.Level,
- Generation: nodeRef.Data.Head.Generation,
- Owner: nodeRef.Data.Head.Owner,
- NumItems: nodeRef.Data.Head.NumItems,
- MinItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MinItem(); return k }(),
- MaxItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MaxItem(); return k }(),
- }
- for i, kp := range nodeRef.Data.BodyInternal {
- ret.insertEdge(kpData{
- FromTree: nodeRef.Data.Head.Owner,
- FromNode: laddr,
- FromItem: i,
- ToNode: kp.BlockPtr,
- ToLevel: nodeRef.Data.Head.Level - 1,
- ToKey: kp.Key,
- ToGeneration: kp.Generation,
- })
- }
+ ret.nodeGraph.InsertNode(nodeRef)
done++
- progress()
+ progress(done, total)
}
}
@@ -225,21 +121,8 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
dlog.Info(ctx, "... done reading node data")
dlog.Infof(ctx, "Checking keypointers for dead-ends...")
- total = len(ret.EdgesTo)
- done = 0
- progress()
- for laddr := range ret.EdgesTo {
- if _, ok := ret.Nodes[laddr]; !ok {
- _, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
- })
- if err == nil {
- return nil, fmt.Errorf("node@%v exists but was not in node scan results", laddr)
- }
- ret.BadNodes[laddr] = err
- }
- done++
- progress()
+ if err := ret.nodeGraph.FinalCheck(fs, *sb, progress); err != nil {
+ return nil, err
}
dlog.Info(ctx, "... done checking keypointers")
generated by cgit v1.1-4-g5e80 at 2024-07-04 17:59:56 +0000