diff options
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect')
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 } } |