rebuildnodes: Optimize indexing of orphans

1 files changed, 24 insertions, 59 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go
index 0ecf852..5d3f031 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go
@@ -33,18 +33,6 @@ func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrf
 	return ret
 }
 
-func walk(graph graph.Graph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) {
-	if _, ok := graph.Nodes[root]; !ok {
-		return
-	}
-	if !fn(root) {
-		return
-	}
-	for _, kp := range graph.EdgesFrom[root] {
-		walk(graph, kp.ToNode, fn)
-	}
-}
-
 type keyAndTree struct {
 	btrfsprim.Key
 	TreeID btrfsprim.ObjID
@@ -58,17 +46,15 @@ func (a keyAndTree) Cmp(b keyAndTree) int {
 }
 
 type crawlStats struct {
-	DoneOrphans  int
-	TotalOrphans int
-
-	VisitedNodes int
-	FoundLeafs   int
+	DoneNodes  int
+	TotalNodes int
+	FoundLeafs int
 }
 
 func (s crawlStats) String() string {
-	return fmt.Sprintf("... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes",
-		int(100*float64(s.DoneOrphans)/float64(s.TotalOrphans)),
-		s.DoneOrphans, s.TotalOrphans, s.VisitedNodes, s.FoundLeafs)
+	return fmt.Sprintf("... indexing orphaned leafs %v%% (%v/%v); found %d leaf nodes",
+		int(100*float64(s.DoneNodes)/float64(s.TotalNodes)),
+		s.DoneNodes, s.TotalNodes, s.FoundLeafs)
 }
 
 type readStats struct {
@@ -87,58 +73,38 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb
 	key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr],
 	err error,
 ) {
-	dlog.Info(ctx, "... counting orphans")
-	orphans := make(containers.Set[btrfsvol.LogicalAddr])
-	for node := range graph.Nodes {
-		if len(graph.EdgesTo[node]) == 0 {
-			orphans.Insert(node)
-		}
-	}
 
-	leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
-	visited := make(containers.Set[btrfsvol.LogicalAddr])
-
-	done := 0
 	crawlProgressWriter := textui.NewProgress[crawlStats](ctx, dlog.LogLevelInfo, 1*time.Second)
-	progress := func() {
+	progress := func(done int) {
 		crawlProgressWriter.Set(crawlStats{
-			DoneOrphans:  done,
-			TotalOrphans: len(orphans),
-			VisitedNodes: len(visited),
-			FoundLeafs:   len(leaf2orphans),
+			DoneNodes:  done,
+			TotalNodes: len(graph.Nodes),
+			FoundLeafs: len(leaf2orphans),
 		})
 	}
-	progress()
-	for _, orphan := range maps.SortedKeys(orphans) {
-		walk(graph, orphan, func(node btrfsvol.LogicalAddr) bool {
-			if visited.Has(node) {
-				return false
-			}
-			visited.Insert(node)
-			if graph.Nodes[node].Level == 0 {
-				if roots := listRoots(graph, node); !roots.Has(0) {
-					leaf2orphans[node] = roots
-				}
-			}
-			progress()
-			return true
-		})
-		done++
-		progress()
+	leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
+	for i, node := range maps.SortedKeys(graph.Nodes) {
+		progress(i)
+		if graph.Nodes[node].Level != 0 {
+			continue
+		}
+		if roots := listRoots(graph, node); !roots.Has(0) {
+			leaf2orphans[node] = roots
+		}
 	}
+	progress(len(graph.Nodes))
 	crawlProgressWriter.Done()
 
 	key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr])
-	done = 0
 	readProgressWriter := textui.NewProgress[readStats](ctx, dlog.LogLevelInfo, 1*time.Second)
-	progress = func() {
+	progress = func(done int) {
 		readProgressWriter.Set(readStats{
 			DoneLeafNodes:  done,
 			TotalLeafNodes: len(leaf2orphans),
 		})
 	}
-	progress()
-	for _, laddr := range maps.SortedKeys(leaf2orphans) {
+	for i, laddr := range maps.SortedKeys(leaf2orphans) {
+		progress(i)
 		nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{
 			LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
 			Level: containers.Optional[uint8]{OK: true, Val: 0},
@@ -156,9 +122,8 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb
 				key2leaf.Store(k, laddr)
 			}
 		}
-		done++
-		progress()
 	}
+	progress(len(leaf2orphans))
 	readProgressWriter.Done()
 
 	return leaf2orphans, key2leaf, nil