summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLuke Shumaker <lukeshu@lukeshu.com>2022-09-18 03:12:04 -0600
committerLuke Shumaker <lukeshu@lukeshu.com>2022-09-18 03:14:05 -0600
commit4b0f7972047e08416eada9d09cc01aeecfd56244 (patch)
tree30b0ccbb4d717e55fdbf0165eb79e050e7f836dd
parent534673fd8b9c6d8f31f5a412746d5671600ad10d (diff)
mostly svg!
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go15
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go41
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go42
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go118
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
}
}