From a72c673018d5cc5dbf76aa31680c34360053f868 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 19 Sep 2022 02:32:15 -0600 Subject: find loops? --- cmd/btrfs-rec/inspect_dumpgraph.go | 44 +++++++ lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go | 154 ++++++++++++++++++++++ scripts/main.sh | 3 + 3 files changed, 201 insertions(+) create mode 100644 cmd/btrfs-rec/inspect_dumpgraph.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go diff --git a/cmd/btrfs-rec/inspect_dumpgraph.go b/cmd/btrfs-rec/inspect_dumpgraph.go new file mode 100644 index 0000000..8e803d3 --- /dev/null +++ b/cmd/btrfs-rec/inspect_dumpgraph.go @@ -0,0 +1,44 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package main + +import ( + "bufio" + "os" + + "github.com/datawire/dlib/dlog" + "github.com/datawire/ocibuild/pkg/cliutil" + "github.com/spf13/cobra" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes" +) + +func init() { + inspectors = append(inspectors, subcommand{ + Command: cobra.Command{ + Use: "show-loops NODESCAN.json", + Args: cliutil.WrapPositionalArgs(cobra.ExactArgs(1)), + }, + RunE: func(fs *btrfs.FS, cmd *cobra.Command, args []string) (err error) { + ctx := cmd.Context() + + dlog.Infof(ctx, "Reading %q...", args[0]) + nodeScanResults, err := readScanResults(args[0]) + if err != nil { + return err + } + dlog.Infof(ctx, "... done reading %q", args[0]) + + buffer := bufio.NewWriter(os.Stdout) + defer func() { + if _err := buffer.Flush(); err == nil && _err != nil { + err = _err + } + }() + return rebuildnodes.ShowLoops(ctx, buffer, fs, nodeScanResults) + }, + }) +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go new file mode 100644 index 0000000..fc71558 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go @@ -0,0 +1,154 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "fmt" + "io" + "strings" + + "github.com/datawire/dlib/dlog" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "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" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +func ShowLoops(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, "Collecting orphans...") + orphans := make(containers.Set[btrfsvol.LogicalAddr]) + for node := range scanData.Nodes { + if len(scanData.EdgesTo[node]) == 0 { + orphans.Insert(node) + } + } + + dlog.Info(ctx, "Walking graph...") + loopWalk(out, *scanData, 0) + for _, orphan := range maps.SortedKeys(orphans) { + loopWalk(out, *scanData, orphan) + } + + return nil +} + +func loopWalk(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAddr) { + for _, kp := range scanData.EdgesFrom[stack[len(stack)-1]] { + childStack := append(stack, kp.ToNode) + if slices.Contains(kp.ToNode, stack) { + loopRender(out, scanData, childStack...) + } else { + loopWalk(out, scanData, childStack...) + } + } +} + +func nodeRender(scanData scanResult, node btrfsvol.LogicalAddr) []string { + if node == 0 { + return []string{"root"} + } else if nodeData, ok := scanData.Nodes[node]; ok { + return []string{ + fmt.Sprintf("{addr: %v,", node), + fmt.Sprintf(" level: %v,", nodeData.Level), + fmt.Sprintf(" gen: %v,", nodeData.Generation), + fmt.Sprintf(" num_items: %v,", nodeData.NumItems), + fmt.Sprintf(" min_item: {%d,%v,%d},", + nodeData.MinItem.ObjectID, + nodeData.MinItem.ItemType, + nodeData.MinItem.Offset), + fmt.Sprintf(" max_item: {%d,%v,%d}}", + nodeData.MaxItem.ObjectID, + nodeData.MaxItem.ItemType, + nodeData.MaxItem.Offset), + } + } else if nodeErr, ok := scanData.BadNodes[node]; ok { + return []string{ + fmt.Sprintf("{addr:%v,", node), + fmt.Sprintf(" err:%q}", nodeErr.Error()), + } + } else { + panic("should not happen") + } +} + +func edgeRender(scanData scanResult, kp kpData) []string { + a := fmt.Sprintf("[%d]={", kp.FromItem) + b := strings.Repeat(" ", len(a)) + ret := []string{ + a + fmt.Sprintf("ToNode: %v,", kp.ToNode), + b + fmt.Sprintf("ToLevel: %v,", kp.ToLevel), + b + fmt.Sprintf("ToGen: %v,", kp.ToGeneration), + b + fmt.Sprintf("ToKey: {%d,%v,%d}}", + kp.ToKey.ObjectID, + kp.ToKey.ItemType, + kp.ToKey.Offset), + } + + var err error + if toNode, ok := scanData.Nodes[kp.ToNode]; !ok { + err = scanData.BadNodes[kp.ToNode] + } else { + err = checkNodeExpectations(kp, toNode) + } + if err != nil { + c := strings.Repeat(" ", len(a)-1) + ret = append(ret, + c+"^", + c+"`-err="+strings.ReplaceAll(err.Error(), "\n", "\n"+c+" "), + ) + } + return ret +} + +func loopRender(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAddr) { + var lines []string + add := func(suffixes []string) { + curLen := 0 + for _, line := range lines { + if len(line) > curLen { + curLen = len(line) + } + } + for i, suffix := range suffixes { + if len(lines) <= i { + lines = append(lines, "") + } + if len(lines[i]) < curLen { + if i == 0 { + lines[i] += strings.Repeat("-", curLen-len(lines[i])-1) + ">" + } else { + lines[i] += strings.Repeat(" ", curLen-len(lines[i])) + } + } + lines[i] += suffix + } + } + + for i, node := range stack { + if i > 0 { + for _, kp := range scanData.EdgesTo[node] { + if kp.FromNode == stack[i-1] { + add(edgeRender(scanData, *kp)) + break + } + } + } + add(nodeRender(scanData, node)) + } + + fmt.Fprintln(out, "loop:") + for _, line := range lines { + fmt.Fprintln(out, " "+line) + } +} diff --git a/scripts/main.sh b/scripts/main.sh index dde5671..531bf98 100755 --- a/scripts/main.sh +++ b/scripts/main.sh @@ -26,6 +26,9 @@ gen $b.gen/1.mappings.json \ gen $b.gen/2.nodes.zip \ ./btrfs-rec --pv=$b.img --mappings=$b.gen/1.mappings.json \ inspect visualize-nodes $b.gen/0.scandevices.json +gen $b.gen/2.loops.txt \ + ./btrfs-rec --pv=$b.img --mappings=$b.gen/1.mappings.json \ + inspect show-loops $b.gen/0.scandevices.json # gen $b.gen/2.nodes.json \ # ./btrfs-rec --pv=$b.img --mappings=$b.gen/1.mappings.json \ # inspect rebuild-nodes $b.gen/0.scandevices.json -- cgit v1.2.3-2-g168b