diff options
Diffstat (limited to 'lib/btrfsprogs')
4 files changed, 24 insertions, 377 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go index fc71558..8ee53d2 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go @@ -10,9 +10,11 @@ import ( "io" "strings" + "github.com/datawire/dlib/derror" "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "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/containers" @@ -152,3 +154,25 @@ func loopRender(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAdd fmt.Fprintln(out, " "+line) } } + +func checkNodeExpectations(kp kpData, toNode nodeData) error { + var errs derror.MultiError + if toNode.Level != kp.ToLevel { + errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", + kp.ToLevel, toNode.Level)) + } + if toNode.Generation != kp.ToGeneration { + errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", + kp.ToGeneration, toNode.Generation)) + } + if toNode.NumItems == 0 { + errs = append(errs, fmt.Errorf("node.num_items=0")) + } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { + errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", + kp.ToKey, toNode.MinItem)) + } + if len(errs) > 0 { + return errs + } + return nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go index 7e0eab1..f1033e6 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go @@ -10,10 +10,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" ) -func ptrTo[T any](x T) *T { - return &x -} - func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { if other, conflict := m[k]; conflict && other != v { return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go index 7be903a..4d93916 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go @@ -5,12 +5,8 @@ package rebuildnodes import ( - "fmt" - "strings" - "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" ) type uuidMap struct { @@ -57,72 +53,3 @@ func (m uuidMap) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { } return parentObjID, true } - -type fullAncestorLister struct { - uuidMap uuidMap - treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] - - memos map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] -} - -func newFullAncestorLister(uuidMap uuidMap, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) fullAncestorLister { - return fullAncestorLister{ - uuidMap: uuidMap, - treeAncestors: treeAncestors, - memos: make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]), - } -} - -type loopError []btrfsprim.ObjID - -func (le loopError) Error() string { - var buf strings.Builder - buf.WriteString("loop: ") - for i, treeID := range le { - if i > 0 { - buf.WriteString("->") - } - fmt.Fprintf(&buf, "%d", treeID) - } - return buf.String() -} - -func (fa fullAncestorLister) GetFullAncestors(child btrfsprim.ObjID) containers.Set[btrfsprim.ObjID] { - if memoized, ok := fa.memos[child]; ok { - if memoized == nil { - panic(loopError{child}) - } - return memoized - } - fa.memos[child] = nil - defer func() { - if r := recover(); r != nil { - if le, ok := r.(loopError); ok { - r = append(loopError{child}, le...) - } - panic(r) - } - }() - - ret := make(containers.Set[btrfsprim.ObjID]) - defer func() { - fa.memos[child] = ret - }() - - // Try to use '.uuidMap' instead of '.treeAncestors' if possible. - knownAncestors := make(containers.Set[btrfsprim.ObjID]) - if parent, ok := fa.uuidMap.ParentTree(child); ok { - if parent == 0 { - return ret - } - knownAncestors.Insert(parent) - } else { - knownAncestors.InsertFrom(fa.treeAncestors[child]) - } - - for _, ancestor := range maps.SortedKeys(knownAncestors) { - ret.Insert(ancestor) - ret.InsertFrom(fa.GetFullAncestors(ancestor)) - } - return ret -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go deleted file mode 100644 index fc9d19b..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go +++ /dev/null @@ -1,300 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "archive/zip" - "context" - "fmt" - "html" - "io" - "strings" - - "github.com/datawire/dlib/derror" - "github.com/datawire/dlib/dlog" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" -) - -func getCliques(scanData scanResult) map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID] { - cliques := make(map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID]) - - // 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)) - for _, id := range maps.SortedKeys(*clique) { - if existingClique, ok := cliques[id]; ok { - clique.InsertFrom(*existingClique) - } - 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 -} - -func getCliqueID(cliques map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID], treeID btrfsprim.ObjID) btrfsprim.ObjID { - clique, ok := cliques[treeID] - if !ok { - panic(fmt.Errorf("tree ID %v was not in .SeenTrees", treeID)) - } - return maps.SortedKeys(*clique)[0] -} - -func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) error { - scanData, err := ScanDevices(ctx, fs, nodeScanResults) - if err != nil { - return err - } - - //////////////////////////////////////////////////////////////////////////////////////////// - - 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 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, 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 { - 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="{laddr=%v\lgen=%v\llvl=%v\litems=%v\l|{`, - laddr, - laddr, - nodeData.Generation, - nodeData.Level, - nodeData.NumItems) - if nodeData.Level == 0 { - buf.WriteString("leaf") - } else { - for i := uint32(0); i < nodeData.NumItems; i++ { - if i == 0 { - fmt.Fprintf(&buf, "<p%[1]d>%[1]d", i) - } else { - fmt.Fprintf(&buf, "|<p%[1]d>%[1]d", i) - } - } - } - buf.WriteString(`}}"]`) - graph.nodes[nodeData.Owner].Insert(buf.String()) - - if len(scanData.EdgesTo[laddr]) == 0 { - graph.edges.Insert(fmt.Sprintf("orphanRoot -> n%d", laddr)) - } - - 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] { - cliqueIDs.Insert(getCliqueID(cliques, edge.FromTree)) - } - if len(cliqueIDs) != 1 { - dlog.Errorf(ctx, "couldn't assign bad node@%v to a clique: %v", laddr, maps.SortedKeys(cliqueIDs)) - continue - } - - cliqueID := cliqueIDs.TakeOne() - graph, ok := graphs[cliqueID] - if !ok { - panic(cliqueID) - } - graph.badNodes.Insert(fmt.Sprintf(`n%d [shape=star color=red label="%v\l\lerr=%s"]`, - laddr, laddr, gvEscape(scanData.BadNodes[laddr].Error()+"\n"))) - 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, ok := graphs[cliqueID] - if !ok { - panic(cliqueID) - } - - var buf strings.Builder - if kp.FromNode == 0 { - 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, gvEscape(kp.FromTree.String()))) - fmt.Fprintf(&buf, "t%d", kp.FromTree) - } else { - fmt.Fprintf(&buf, "n%d:p%d", kp.FromNode, kp.FromItem) - } - 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, ` [label="key=(%d,%v,%d) gen=%v\l\lerr=%s" color=red]`, - kp.ToKey.ObjectID, - kp.ToKey.ItemType, - kp.ToKey.Offset, - kp.ToGeneration, - gvEscape(err.Error()+"\n")) - } - - graph.edges.Insert(buf.String()) - graphs[cliqueID] = graph - } - } - - //////////////////////////////////////////////////////////////////////////////////////////// - - dlog.Info(ctx, "Writing graphviz output...") - - zw := zip.NewWriter(out) - for _, cliqueID := range maps.SortedKeys(graphs) { - if err := func() (err error) { - graph := graphs[cliqueID] - - buf, err := zw.Create(fmt.Sprintf("%d.dot", cliqueID)) - if err != nil { - return err - } - 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] - - if _, err := fmt.Fprintf(buf, " subgraph cluster_tree%d {\n", treeID); err != nil { - return err - } - for _, node := range maps.SortedKeys(nodes) { - if _, err := fmt.Fprintf(buf, " %s;\n", node); err != nil { - return err - } - } - if _, err := fmt.Fprintln(buf, " }"); err != nil { - return err - } - } - for _, node := range maps.SortedKeys(graph.badNodes) { - if _, err := fmt.Fprintf(buf, " %s;\n", node); err != nil { - return err - } - } - for _, edge := range maps.SortedKeys(graph.edges) { - if _, err := fmt.Fprintf(buf, " %s;\n", edge); err != nil { - return err - } - } - - if _, err := fmt.Fprintln(buf, "}"); err != nil { - return err - } - return nil - }(); err != nil { - return err - } - } - if err := zw.Close(); err != nil { - return err - } - - dlog.Info(ctx, "... done writing") - - return nil -} - -func gvEscape(str string) string { - str = html.EscapeString(str) - str = strings.ReplaceAll(str, "\n", `\l`) - str = strings.ReplaceAll(str, `\n`, `\l`) - return str -} - -func checkNodeExpectations(kp kpData, toNode nodeData) error { - var errs derror.MultiError - if toNode.Level != kp.ToLevel { - errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", - kp.ToLevel, toNode.Level)) - } - if toNode.Generation != kp.ToGeneration { - errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", - kp.ToGeneration, toNode.Generation)) - } - if toNode.NumItems == 0 { - errs = append(errs, fmt.Errorf("node.num_items=0")) - } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { - errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", - kp.ToKey, toNode.MinItem)) - } - if len(errs) > 0 { - return errs - } - return nil -} |