rebuildnodes: Refactor the node-graph stuff in to a separate sub-package

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")