From 534673fd8b9c6d8f31f5a412746d5671600ad10d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 18 Sep 2022 00:09:56 -0600 Subject: wip --- lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 10 +++++ .../btrfsinspect/rebuildnodes/treeancestors.go | 14 ++++++- .../btrfsinspect/rebuildnodes/uuidmap.go | 27 +++++++++++++- .../btrfsinspect/rebuildnodes/visualizenodes.go | 43 ++++++++++++---------- 4 files changed, 71 insertions(+), 23 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index 5070e7e..e17805e 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -40,6 +40,15 @@ type kpData struct { ToGeneration btrfsprim.Generation } +func (kp kpData) String() string { + return fmt.Sprintf(`{t:%v,n:%v}[%d]->{n:%v,l:%v,g:%v,k:(%d,%v,%d)}`, + kp.FromTree, kp.FromNode, kp.FromItem, + kp.ToNode, kp.ToLevel, kp.ToGeneration, + kp.ToKey.ObjectID, + kp.ToKey.ItemType, + kp.ToKey.Offset) +} + type nodeGraph struct { Nodes map[btrfsvol.LogicalAddr]nodeData BadNodes map[btrfsvol.LogicalAddr]error @@ -170,6 +179,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca Level: nodeRef.Data.Head.Level, Generation: nodeRef.Data.Head.Generation, Owner: nodeRef.Data.Head.Owner, + NumItems: nodeRef.Data.Head.NumItems, MinItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MinItem(); return k }(), MaxItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MaxItem(); return k }(), } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go index 2e1d856..c396a13 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go @@ -5,11 +5,15 @@ package rebuildnodes import ( + "context" + + //"github.com/datawire/dlib/dlog" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) -func getTreeAncestors(scanData scanResult) map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] { +func getTreeAncestors(ctx context.Context, scanData scanResult) map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] { treeAncestors := make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) for laddr, node := range scanData.Nodes { @@ -17,7 +21,13 @@ func getTreeAncestors(scanData scanResult) map[btrfsprim.ObjID]containers.Set[bt treeAncestors[node.Owner] = make(containers.Set[btrfsprim.ObjID]) } for _, edge := range scanData.EdgesTo[laddr] { - treeAncestors[node.Owner].Insert(edge.FromTree) + if edge.FromTree != node.Owner { + if err := checkNodeExpectations(*edge, node); err != nil { + //dlog.Errorf(ctx, "... ignoring keypointer %v because %v", edge.String(), err) + } else { + treeAncestors[node.Owner].Insert(edge.FromTree) + } + } } } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go index c67b7af..4ce90ae 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go @@ -7,6 +7,7 @@ package rebuildnodes import ( "context" "fmt" + "strings" "github.com/datawire/dlib/dlog" @@ -75,14 +76,36 @@ func newFullAncestorLister(uuidMap uuidMap, treeAncestors map[btrfsprim.ObjID]co } } +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(fmt.Errorf("loop involving tree %v", child)) + 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() { @@ -124,7 +147,7 @@ func (m uuidMap) considerAncestors(ctx context.Context, treeAncestors map[btrfsp } potentialParents := make(containers.Set[btrfsprim.ObjID]) potentialParents.InsertFrom(fa.GetFullAncestors(missingRoot)) - for ancestor := range fa.GetFullAncestors(missingRoot) { + for _, ancestor := range maps.SortedKeys(fa.GetFullAncestors(missingRoot)) { potentialParents.DeleteFrom(fa.GetFullAncestors(ancestor)) } if len(potentialParents) == 1 { diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go index 368fafd..0781f3c 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go @@ -54,7 +54,7 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe } dlog.Info(ctx, "Walking trees to rebuild root items...") - treeAncestors := getTreeAncestors(*scanData) + treeAncestors := getTreeAncestors(ctx, *scanData) scanData.considerAncestors(ctx, treeAncestors) //////////////////////////////////////////////////////////////////////////////////////////// @@ -152,24 +152,7 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe if !ok { err = scanData.BadNodes[kp.ToNode] } else { - var errs derror.MultiError - if toNode.Level != kp.ToLevel { - errs = append(errs, fmt.Errorf("node.level=%v != kp.level=%v", - toNode.Level, kp.ToLevel)) - } - if toNode.Generation != kp.ToGeneration { - errs = append(errs, fmt.Errorf("node.generation=%v != kp.generation=%v", - toNode.Generation, kp.ToGeneration)) - } - if toNode.NumItems == 0 { - errs = append(errs, fmt.Errorf("node.num_items=0")) - } else if toNode.MinItem != kp.ToKey { - errs = append(errs, fmt.Errorf("node.items[0].key=%v != kp.key=%v", - toNode.MinItem, kp.ToKey)) - } - if len(errs) > 0 { - err = errs - } + err = checkNodeExpectations(*kp, toNode) } if err != nil { fmt.Fprintf(&buf, `\n\n%s" color=red]`, html.EscapeString(err.Error())) @@ -241,3 +224,25 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe return nil } + +func checkNodeExpectations(kp kpData, toNode nodeData) error { + var errs derror.MultiError + if toNode.Level != kp.ToLevel { + errs = append(errs, fmt.Errorf("node.level=%v != kp.level=%v", + toNode.Level, kp.ToLevel)) + } + if toNode.Generation != kp.ToGeneration { + errs = append(errs, fmt.Errorf("node.generation=%v != kp.generation=%v", + toNode.Generation, kp.ToGeneration)) + } + if toNode.NumItems == 0 { + errs = append(errs, fmt.Errorf("node.num_items=0")) + } else if toNode.MinItem != kp.ToKey { + errs = append(errs, fmt.Errorf("node.items[0].key=%v != kp.key=%v", + toNode.MinItem, kp.ToKey)) + } + if len(errs) > 0 { + return errs + } + return nil +} -- cgit v1.2.3-2-g168b