wip

4 files changed, 71 insertions, 23 deletions

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
+}