From 00f80af7ff67dd5723ddc53f676536ef926f2791 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 25 Dec 2022 00:48:54 -0700
Subject: rebuildnodes: Integrate loop-checking in to Graph.FinalCheck
---
.../rebuildnodes/btrees/rebuilt_btrees.go | 2 +
.../btrfsinspect/rebuildnodes/graph/graph.go | 75 ++++++++++++++++++++--
.../btrfsinspect/rebuildnodes/graph/loops.go | 54 ++++------------
lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 7 +-
4 files changed, 82 insertions(+), 56 deletions(-)
(limited to 'lib/btrfsprogs')
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
index 50c75a4..ab4b55f 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
@@ -345,6 +345,8 @@ func (tree *rebuiltTree) indexNode(graph pkggraph.Graph, node btrfsvol.LogicalAd
return
}
if slices.Contains(node, stack) {
+ // This is a panic because graph.FinalCheck() should
+ // have already checked for loops.
panic("loop")
}
if !tree.isOwnerOK(graph.Nodes[node].Owner, graph.Nodes[node].Generation) {
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
index 1180b0d..d3dd19a 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
@@ -5,8 +5,12 @@
package graph
import (
+ "context"
"fmt"
"reflect"
+ "time"
+
+ "github.com/datawire/dlib/dlog"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
@@ -14,6 +18,9 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+ "git.lukeshu.com/btrfs-progs-ng/lib/maps"
+ "git.lukeshu.com/btrfs-progs-ng/lib/slices"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
type Node struct {
@@ -131,7 +138,7 @@ func New(sb btrfstree.Superblock) *Graph {
return g
}
-func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
+func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
nodeData := Node{
Level: nodeRef.Data.Head.Level,
Generation: nodeRef.Data.Head.Generation,
@@ -184,23 +191,77 @@ func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N
}
}
-func (g *Graph) FinalCheck(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, progress func(n, d int)) error {
- total := len(g.EdgesTo)
- done := 0
- progress(done, total)
+type progStats struct {
+ textui.Portion[int]
+}
+
+func (s progStats) String() string {
+ return "... " + s.Portion.String()
+}
+
+func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) error {
+ var stats progStats
+
+ dlog.Info(ctx, "Checking keypointers for dead-ends...")
+ progressWriter := textui.NewProgress[progStats](ctx, dlog.LogLevelInfo, 1*time.Second)
+ stats.D = len(g.EdgesTo)
+ progressWriter.Set(stats)
for laddr := range g.EdgesTo {
if _, ok := g.Nodes[laddr]; !ok {
_, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{
LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
})
if err == nil {
+ progressWriter.Done()
return fmt.Errorf("node@%v exists but was not in node scan results", laddr)
}
g.BadNodes[laddr] = err
}
- done++
- progress(done, total)
+ stats.N++
+ progressWriter.Set(stats)
}
+ progressWriter.Done()
+ dlog.Info(ctx, "... done checking keypointers")
+
+ dlog.Info(ctx, "Checking for btree loops...")
+ stats.D = len(g.Nodes)
+ stats.N = 0
+ progressWriter = textui.NewProgress[progStats](ctx, dlog.LogLevelInfo, 1*time.Second)
+ progressWriter.Set(stats)
+ visited := make(containers.Set[btrfsvol.LogicalAddr], len(g.Nodes))
+ numLoops := 0
+ var checkNode func(node btrfsvol.LogicalAddr, stack []btrfsvol.LogicalAddr)
+ checkNode = func(node btrfsvol.LogicalAddr, stack []btrfsvol.LogicalAddr) {
+ defer func() {
+ stats.N = len(visited)
+ progressWriter.Set(stats)
+ }()
+ if visited.Has(node) {
+ return
+ }
+ if slices.Contains(node, stack) {
+ numLoops++
+ dlog.Error(ctx, "loop:")
+ for _, line := range g.renderLoop(append(stack, node)) {
+ dlog.Errorf(ctx, " %s", line)
+ }
+ return
+ }
+ stack = append(stack, node)
+ for _, kp := range g.EdgesTo[node] {
+ checkNode(kp.FromNode, stack)
+ }
+ visited.Insert(node)
+ }
+ for _, node := range maps.SortedKeys(g.Nodes) {
+ checkNode(node, nil)
+ }
+ progressWriter.Done()
+ if numLoops > 0 {
+ return fmt.Errorf("%d btree loops", numLoops)
+ }
+ dlog.Info(ctx, "... done checking for loops")
+
return nil
}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go
index e76985c..0e51805 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go
@@ -6,47 +6,18 @@ package graph
import (
"fmt"
- "io"
"strings"
"github.com/datawire/dlib/derror"
"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/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
-func (g Graph) ShowLoops(out io.Writer) {
- orphans := make(containers.Set[btrfsvol.LogicalAddr])
- for node := range g.Nodes {
- if len(g.EdgesTo[node]) == 0 {
- orphans.Insert(node)
- }
- }
-
- loopWalk(out, g, 0)
- for _, orphan := range maps.SortedKeys(orphans) {
- loopWalk(out, g, orphan)
- }
-}
-
-func loopWalk(out io.Writer, scanData Graph, 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 Graph, node btrfsvol.LogicalAddr) []string {
+func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
if node == 0 {
return []string{"root"}
- } else if nodeData, ok := scanData.Nodes[node]; ok {
+ } else if nodeData, ok := g.Nodes[node]; ok {
return []string{
fmt.Sprintf("{addr: %v,", node),
fmt.Sprintf(" level: %v,", nodeData.Level),
@@ -61,7 +32,7 @@ func nodeRender(scanData Graph, node btrfsvol.LogicalAddr) []string {
nodeData.MaxItem.ItemType,
nodeData.MaxItem.Offset),
}
- } else if nodeErr, ok := scanData.BadNodes[node]; ok {
+ } else if nodeErr, ok := g.BadNodes[node]; ok {
return []string{
fmt.Sprintf("{addr:%v,", node),
fmt.Sprintf(" err:%q}", nodeErr.Error()),
@@ -71,7 +42,7 @@ func nodeRender(scanData Graph, node btrfsvol.LogicalAddr) []string {
}
}
-func edgeRender(scanData Graph, kp Edge) []string {
+func (g Graph) renderEdge(kp Edge) []string {
a := fmt.Sprintf("[%d]={", kp.FromItem)
b := strings.Repeat(" ", len(a))
ret := []string{
@@ -85,8 +56,8 @@ func edgeRender(scanData Graph, kp Edge) []string {
}
var err error
- if toNode, ok := scanData.Nodes[kp.ToNode]; !ok {
- err = scanData.BadNodes[kp.ToNode]
+ if toNode, ok := g.Nodes[kp.ToNode]; !ok {
+ err = g.BadNodes[kp.ToNode]
} else {
err = checkNodeExpectations(kp, toNode)
}
@@ -100,7 +71,7 @@ func edgeRender(scanData Graph, kp Edge) []string {
return ret
}
-func loopRender(out io.Writer, scanData Graph, stack ...btrfsvol.LogicalAddr) {
+func (g Graph) renderLoop(stack []btrfsvol.LogicalAddr) []string {
var lines []string
add := func(suffixes []string) {
curLen := 0
@@ -126,20 +97,17 @@ func loopRender(out io.Writer, scanData Graph, stack ...btrfsvol.LogicalAddr) {
for i, node := range stack {
if i > 0 {
- for _, kp := range scanData.EdgesTo[node] {
+ for _, kp := range g.EdgesTo[node] {
if kp.FromNode == stack[i-1] {
- add(edgeRender(scanData, *kp))
+ add(g.renderEdge(*kp))
break
}
}
}
- add(nodeRender(scanData, node))
+ add(g.renderNode(node))
}
- fmt.Fprintln(out, "loop:")
- for _, line := range lines {
- fmt.Fprintln(out, " "+line)
- }
+ return lines
}
func checkNodeExpectations(kp Edge, toNode Node) error {
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
index 5c2d0fd..cdd5cba 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
@@ -72,14 +72,9 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
progressWriter.Done()
dlog.Info(ctx, "... done reading node data")
- progressWriter = textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, 1*time.Second)
- dlog.Infof(ctx, "Checking keypointers for dead-ends...")
- if err := nodeGraph.FinalCheck(fs, *sb, progress); err != nil {
+ if err := nodeGraph.FinalCheck(ctx, fs, *sb); err != nil {
return graph.Graph{}, nil, err
}
- progressWriter.Done()
- dlog.Info(ctx, "... done checking keypointers")
-
keyIO.SetGraph(*nodeGraph)
return *nodeGraph, keyIO, nil
--
cgit v1.2.3-2-g168b