mostly svg!

4 files changed, 136 insertions, 80 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
index e17805e..c32ae8e 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
@@ -58,12 +58,25 @@ type nodeGraph struct {
 
 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, _ := btrfstree.LookupTreeRoot(nil, sb, treeID)
+	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,
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go
index c396a13..42228ae 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go
@@ -4,6 +4,7 @@
 
 package rebuildnodes
 
+/*
 import (
 	"context"
 
@@ -33,3 +34,43 @@ func getTreeAncestors(ctx context.Context, scanData scanResult) map[btrfsprim.Ob
 
 	return treeAncestors
 }
+
+func (m uuidMap) considerAncestors(ctx context.Context, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) {
+	if missing := m.missingRootItems(); len(missing) == 0 {
+		return
+	} else {
+		dlog.Infof(ctx, "Rebuilding %d root items...", len(missing))
+	}
+
+	fa := newFullAncestorLister(m, treeAncestors)
+
+	for _, missingRoot := range maps.SortedKeys(m.missingRootItems()) {
+		if _, ok := m.TreeParent[missingRoot]; ok {
+			// This one is incomplete because it doesn't have a UUID, not
+			// because it doesn't have a parent.
+			continue
+		}
+		potentialParents := make(containers.Set[btrfsprim.ObjID])
+		potentialParents.InsertFrom(fa.GetFullAncestors(missingRoot))
+		for _, ancestor := range maps.SortedKeys(fa.GetFullAncestors(missingRoot)) {
+			potentialParents.DeleteFrom(fa.GetFullAncestors(ancestor))
+		}
+		if len(potentialParents) == 1 {
+			parent := potentialParents.TakeOne()
+			dlog.Infof(ctx, "... the parent of %v is %v", missingRoot, parent)
+			parentUUID, ok := m.ObjID2UUID[parent]
+			if !ok {
+				dlog.Errorf(ctx, "... but can't synthesize a root item because UUID of %v is unknown", parent)
+				continue
+			}
+			m.TreeParent[missingRoot] = parentUUID
+		}
+	}
+
+	if missing := m.missingRootItems(); len(missing) > 0 {
+		dlog.Errorf(ctx, "... could not rebuild root items for %d trees: %v", len(missing), maps.SortedKeys(missing))
+	} else {
+		dlog.Info(ctx, "... rebuilt all root items")
+	}
+}
+*/
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go
index 4ce90ae..7be903a 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go
@@ -5,12 +5,9 @@
 package rebuildnodes
 
 import (
-	"context"
 	"fmt"
 	"strings"
 
-	"github.com/datawire/dlib/dlog"
-
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
@@ -129,42 +126,3 @@ func (fa fullAncestorLister) GetFullAncestors(child btrfsprim.ObjID) containers.
 	}
 	return ret
 }
-
-func (m uuidMap) considerAncestors(ctx context.Context, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) {
-	if missing := m.missingRootItems(); len(missing) == 0 {
-		return
-	} else {
-		dlog.Infof(ctx, "Rebuilding %d root items...", len(missing))
-	}
-
-	fa := newFullAncestorLister(m, treeAncestors)
-
-	for _, missingRoot := range maps.SortedKeys(m.missingRootItems()) {
-		if _, ok := m.TreeParent[missingRoot]; ok {
-			// This one is incomplete because it doesn't have a UUID, not
-			// because it doesn't have a parent.
-			continue
-		}
-		potentialParents := make(containers.Set[btrfsprim.ObjID])
-		potentialParents.InsertFrom(fa.GetFullAncestors(missingRoot))
-		for _, ancestor := range maps.SortedKeys(fa.GetFullAncestors(missingRoot)) {
-			potentialParents.DeleteFrom(fa.GetFullAncestors(ancestor))
-		}
-		if len(potentialParents) == 1 {
-			parent := potentialParents.TakeOne()
-			dlog.Infof(ctx, "... the parent of %v is %v", missingRoot, parent)
-			parentUUID, ok := m.ObjID2UUID[parent]
-			if !ok {
-				dlog.Errorf(ctx, "... but can't synthesize a root item because UUID of %v is unknown", parent)
-				continue
-			}
-			m.TreeParent[missingRoot] = parentUUID
-		}
-	}
-
-	if missing := m.missingRootItems(); len(missing) > 0 {
-		dlog.Errorf(ctx, "... could not rebuild root items for %d trees: %v", len(missing), maps.SortedKeys(missing))
-	} else {
-		dlog.Info(ctx, "... rebuilt all root items")
-	}
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
index 0781f3c..e253a47 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
@@ -22,10 +22,12 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
-func getCliques(uuidMap uuidMap, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID] {
+func getCliques(scanData scanResult) map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID] {
 	cliques := make(map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID])
-	lister := newFullAncestorLister(uuidMap, treeAncestors)
-	for _, treeID := range maps.SortedKeys(uuidMap.SeenTrees) {
+
+	// UUID map
+	lister := newFullAncestorLister(scanData.uuidMap, map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]{})
+	for _, treeID := range maps.SortedKeys(scanData.uuidMap.SeenTrees) {
 		clique := ptrTo(make(containers.Set[btrfsprim.ObjID]))
 		clique.Insert(treeID)
 		clique.InsertFrom(lister.GetFullAncestors(treeID))
@@ -36,6 +38,21 @@ func getCliques(uuidMap uuidMap, treeAncestors map[btrfsprim.ObjID]containers.Se
 			cliques[id] = clique
 		}
 	}
+
+	// node graph
+	for _, laddr := range maps.SortedKeys(scanData.nodeGraph.Nodes) {
+		clique := ptrTo(make(containers.Set[btrfsprim.ObjID]))
+		clique.Insert(scanData.nodeGraph.Nodes[laddr].Owner)
+		for _, edge := range scanData.nodeGraph.EdgesTo[laddr] {
+			clique.Insert(edge.FromTree)
+		}
+		for _, id := range maps.SortedKeys(*clique) {
+			if existingClique, ok := cliques[id]; ok {
+				clique.InsertFrom(*existingClique)
+			}
+			cliques[id] = clique
+		}
+	}
 	return cliques
 }
 
@@ -53,44 +70,56 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 		return err
 	}
 
-	dlog.Info(ctx, "Walking trees to rebuild root items...")
-	treeAncestors := getTreeAncestors(ctx, *scanData)
-	scanData.considerAncestors(ctx, treeAncestors)
-
 	////////////////////////////////////////////////////////////////////////////////////////////
 
-	cliques := getCliques(scanData.uuidMap, treeAncestors)
+	dlog.Info(ctx, "Building cliques...")
+	cliques := getCliques(*scanData)
+	cliqueIDs := make(containers.Set[btrfsprim.ObjID])
+	for treeID := range cliques {
+		cliqueIDs.Insert(getCliqueID(cliques, treeID))
+	}
+	dlog.Infof(ctx, "... built %d cliques of %d trees", len(cliqueIDs), len(cliques))
 
-	dlog.Info(ctx, "Building graphviz graph...")
+	////////////////////////////////////////////////////////////////////////////////////////////
+
+	dlog.Info(ctx, "Building graphviz graphs...")
 
 	type graph struct {
 		nodes    map[btrfsprim.ObjID]containers.Set[string] // keyed by treeID
 		badNodes containers.Set[string]
 		edges    containers.Set[string]
 	}
-	graphs := make(map[btrfsprim.ObjID]graph) // keyed by cliqueID
+	graphs := make(map[btrfsprim.ObjID]graph, len(cliques)) // keyed by cliqueID
+	for cliqueID := range cliqueIDs {
+		graphs[cliqueID] = graph{
+			nodes:    make(map[btrfsprim.ObjID]containers.Set[string]),
+			badNodes: make(containers.Set[string]),
+			edges:    make(containers.Set[string]),
+		}
+	}
+
+	dlog.Infof(ctx, "... processing %d nodes...", len(scanData.Nodes))
 
 	for _, laddr := range maps.SortedKeys(scanData.Nodes) {
 		nodeData := scanData.Nodes[laddr]
 		cliqueID := getCliqueID(cliques, nodeData.Owner)
 		graph, ok := graphs[cliqueID]
 		if !ok {
-			graph.nodes = make(map[btrfsprim.ObjID]containers.Set[string])
-			graph.badNodes = make(containers.Set[string])
-			graph.edges = make(containers.Set[string])
+			panic(cliqueID)
 		}
 		if graph.nodes[nodeData.Owner] == nil {
 			graph.nodes[nodeData.Owner] = make(containers.Set[string])
 		}
 
 		var buf strings.Builder
-		fmt.Fprintf(&buf, `n%d [shape=record label="%v\ngen=%v\nlvl=%v|{`,
+		fmt.Fprintf(&buf, `n%d [shape=record label="{laddr=%v\lgen=%v\llvl=%v\litems=%v\l|{`,
 			laddr,
 			laddr,
 			nodeData.Generation,
-			nodeData.Level)
-		if nodeData.NumItems == 0 {
-			buf.WriteString("(no items)")
+			nodeData.Level,
+			nodeData.NumItems)
+		if nodeData.Level == 0 {
+			buf.WriteString("leaf")
 		} else {
 			for i := uint32(0); i < nodeData.NumItems; i++ {
 				if i == 0 {
@@ -100,7 +129,7 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 				}
 			}
 		}
-		buf.WriteString(`}"]`)
+		buf.WriteString(`}}"]`)
 		graph.nodes[nodeData.Owner].Insert(buf.String())
 
 		if len(scanData.EdgesTo[laddr]) == 0 {
@@ -110,6 +139,8 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 		graphs[cliqueID] = graph
 	}
 
+	dlog.Infof(ctx, "... processing %d bad nodes...", len(scanData.BadNodes))
+
 	for _, laddr := range maps.SortedKeys(scanData.BadNodes) {
 		cliqueIDs := make(containers.Set[btrfsprim.ObjID])
 		for _, edge := range scanData.EdgesTo[laddr] {
@@ -121,43 +152,54 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 		}
 
 		cliqueID := cliqueIDs.TakeOne()
-		graph := graphs[cliqueID]
+		graph, ok := graphs[cliqueID]
+		if !ok {
+			panic(cliqueID)
+		}
 		graph.badNodes.Insert(fmt.Sprintf(`n%d [shape=star color=red label="%v"]`, laddr, laddr))
 		graphs[cliqueID] = graph
 	}
 
+	numEdges := 0
+	for _, kps := range scanData.EdgesFrom {
+		numEdges += (len(kps))
+	}
+	dlog.Infof(ctx, "... processing %d keypointers...", numEdges)
+
 	for _, laddr := range maps.SortedKeys(scanData.EdgesFrom) {
 		for _, kp := range scanData.EdgesFrom[laddr] {
 			cliqueID := getCliqueID(cliques, kp.FromTree)
-			graph := graphs[cliqueID]
+			graph, ok := graphs[cliqueID]
+			if !ok {
+				panic(cliqueID)
+			}
 
 			var buf strings.Builder
 			if kp.FromNode == 0 {
-				graph.nodes[kp.FromTree].Insert(fmt.Sprintf(`t%d [label="%s"]`, kp.FromTree, html.EscapeString(kp.FromTree.String())))
+				if graph.nodes[kp.FromTree] == nil {
+					graph.nodes[kp.FromTree] = make(containers.Set[string])
+				}
+				graph.nodes[kp.FromTree].Insert(fmt.Sprintf(`t%d [label="root of %s"]`, kp.FromTree, html.EscapeString(kp.FromTree.String())))
 				fmt.Fprintf(&buf, "t%d", kp.FromTree)
 			} else {
-				fmt.Fprintf(&buf, "n%d", kp.FromNode)
+				fmt.Fprintf(&buf, "n%d:p%d", kp.FromNode, kp.FromItem)
 			}
-			fmt.Fprintf(&buf, ` -> n%d [label="%d: key=(%d,%v,%d) gen=%v`,
-				// dst node
-				kp.ToNode,
-				// label
-				kp.FromItem,
-				kp.ToKey.ObjectID,
-				kp.ToKey.ItemType,
-				kp.ToKey.Offset,
-				kp.ToGeneration)
-			toNode, ok := scanData.Nodes[kp.ToNode]
+			fmt.Fprintf(&buf, ` -> n%d`, kp.ToNode)
+
 			var err error
+			toNode, ok := scanData.Nodes[kp.ToNode]
 			if !ok {
 				err = scanData.BadNodes[kp.ToNode]
 			} else {
 				err = checkNodeExpectations(*kp, toNode)
 			}
 			if err != nil {
-				fmt.Fprintf(&buf, `\n\n%s" color=red]`, html.EscapeString(err.Error()))
-			} else {
-				buf.WriteString(`"]`)
+				fmt.Fprintf(&buf, ` [label="key=(%d,%v,%d) gen=%v\l\l%s" color=red]`,
+					kp.ToKey.ObjectID,
+					kp.ToKey.ItemType,
+					kp.ToKey.Offset,
+					kp.ToGeneration,
+					strings.ReplaceAll(strings.ReplaceAll(html.EscapeString(err.Error())+"\n", "\n", `\l`), `\n`, `\l`))
 			}
 
 			graph.edges.Insert(buf.String())
@@ -181,7 +223,9 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 			if _, err := fmt.Fprintf(buf, "strict digraph clique%d {\n", cliqueID); err != nil {
 				return err
 			}
-
+			if _, err := fmt.Fprintf(buf, "rankdir=LR;\n  nodesep=0.1;\n  ranksep=25;\n  splines=line;\n"); err != nil {
+				return err
+			}
 			for _, treeID := range maps.SortedKeys(graph.nodes) {
 				nodes := graph.nodes[treeID]
 
@@ -198,7 +242,7 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 				}
 			}
 			for _, node := range maps.SortedKeys(graph.badNodes) {
-				if _, err := fmt.Fprintf(buf, "   %s;\n", node); err != nil {
+				if _, err := fmt.Fprintf(buf, "  %s;\n", node); err != nil {
 					return err
 				}
 			}