Merge branch 'lukeshu/fixes'

8 files changed, 119 insertions, 66 deletions

diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go
index 0eb45ba..24622b4 100644
--- a/cmd/btrfs-rec/inspect_lstrees.go
+++ b/cmd/btrfs-rec/inspect_lstrees.go
@@ -79,8 +79,6 @@ func init() {
 						visitedNodes.Insert(node.Head.Addr)
 					},
 					BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
-						nodeAddr, _, _ := path.NodeExpectations(ctx, false)
-						visitedNodes.Insert(nodeAddr)
 						treeErrCnt++
 						return false
 					},
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index ea33be7..fe7fe70 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -23,34 +23,52 @@ import (
 )
 
 type GraphNode struct {
+	Addr       btrfsvol.LogicalAddr
 	Level      uint8
 	Generation btrfsprim.Generation
 	Owner      btrfsprim.ObjID
 	Items      []btrfsprim.Key
 }
 
-func (n GraphNode) MinItem() btrfsprim.Key {
-	if len(n.Items) == 0 {
+func (n GraphNode) NumItems(g Graph) int {
+	switch n.Level {
+	case 0:
+		return len(n.Items)
+	default:
+		return len(g.EdgesFrom[n.Addr])
+	}
+}
+
+func (n GraphNode) MinItem(g Graph) btrfsprim.Key {
+	if n.NumItems(g) == 0 {
 		return btrfsprim.Key{}
 	}
-	return n.Items[0]
+	switch n.Level {
+	case 0:
+		return n.Items[0]
+	default:
+		return g.EdgesFrom[n.Addr][0].ToKey
+	}
 }
 
-func (n GraphNode) MaxItem() btrfsprim.Key {
-	if len(n.Items) == 0 {
+func (n GraphNode) MaxItem(g Graph) btrfsprim.Key {
+	if n.NumItems(g) == 0 {
 		return btrfsprim.Key{}
 	}
-	return n.Items[len(n.Items)-1]
+	switch n.Level {
+	case 0:
+		return n.Items[len(n.Items)-1]
+	default:
+		return g.EdgesFrom[n.Addr][len(g.EdgesFrom[n.Addr])-1].ToKey
+	}
 }
 
 func (n GraphNode) String() string {
 	if reflect.ValueOf(n).IsZero() {
 		return "{}"
 	}
-	return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v, min:(%v,%v,%v), max:(%v,%v,%v)}`,
-		n.Level, n.Generation, n.Owner, len(n.Items),
-		n.MinItem().ObjectID, n.MinItem().ItemType, n.MinItem().Offset,
-		n.MaxItem().ObjectID, n.MaxItem().ItemType, n.MaxItem().Offset)
+	return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v}`,
+		n.Level, n.Generation, n.Owner, len(n.Items))
 }
 
 type GraphEdge struct {
@@ -59,7 +77,7 @@ type GraphEdge struct {
 	// superblock.
 	FromRoot btrfsvol.LogicalAddr
 	FromNode btrfsvol.LogicalAddr
-	FromItem int // only valid if one of FromRoot or FromNode is non-zero
+	FromSlot int // only valid if one of FromRoot or FromNode is non-zero
 
 	FromTree btrfsprim.ObjID
 
@@ -74,10 +92,10 @@ func (kp GraphEdge) String() string {
 	switch {
 	case kp.FromRoot != 0:
 		from = fmt.Sprintf("root@%v[%d]:%v",
-			kp.FromRoot, kp.FromItem, kp.FromTree)
+			kp.FromRoot, kp.FromSlot, kp.FromTree)
 	case kp.FromNode != 0:
 		from = fmt.Sprintf("{node:%v, tree:%v}[%d]",
-			kp.FromNode, kp.FromTree, kp.FromItem)
+			kp.FromNode, kp.FromTree, kp.FromSlot)
 	default:
 		from = fmt.Sprintf("superblock:%v", kp.FromTree)
 	}
@@ -103,8 +121,8 @@ func (g Graph) insertEdge(ptr *GraphEdge) {
 	if ptr.FromRoot != 0 && ptr.FromNode != 0 {
 		panic("kp.FromRoot and kp.FromNode should not both be set")
 	}
-	if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromItem != 0 {
-		panic("kp.FromItem should only be set if either kp.FromRoot or kp.FromItem is set")
+	if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromSlot != 0 {
+		panic("kp.FromSlot should only be set if either kp.FromRoot or kp.FromSlot is set")
 	}
 	g.EdgesFrom[ptr.FromNode] = append(g.EdgesFrom[ptr.FromNode], ptr)
 	g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr)
@@ -150,6 +168,7 @@ func NewGraph(ctx context.Context, sb btrfstree.Superblock) Graph {
 
 func (g Graph) InsertNode(node *btrfstree.Node) {
 	nodeData := GraphNode{
+		Addr:       node.Head.Addr,
 		Level:      node.Head.Level,
 		Generation: node.Head.Generation,
 		Owner:      node.Head.Owner,
@@ -171,7 +190,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) {
 			if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
 				kps = append(kps, GraphEdge{
 					FromRoot:     node.Head.Addr,
-					FromItem:     i,
+					FromSlot:     i,
 					FromTree:     item.Key.ObjectID,
 					ToNode:       itemBody.ByteNr,
 					ToLevel:      itemBody.Level,
@@ -186,7 +205,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) {
 		for i, kp := range node.BodyInterior {
 			kps[i] = GraphEdge{
 				FromNode:     node.Head.Addr,
-				FromItem:     i,
+				FromSlot:     i,
 				FromTree:     node.Head.Owner,
 				ToNode:       kp.BlockPtr,
 				ToLevel:      node.Head.Level - 1,
diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go
index b5690af..2819482 100644
--- a/lib/btrfsutil/graph_loops.go
+++ b/lib/btrfsutil/graph_loops.go
@@ -24,13 +24,13 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
 			fmt.Sprintf(" gen:       %v,", nodeData.Generation),
 			fmt.Sprintf(" num_items: %v,", len(nodeData.Items)),
 			fmt.Sprintf(" min_item:  {%d,%v,%d},",
-				nodeData.MinItem().ObjectID,
-				nodeData.MinItem().ItemType,
-				nodeData.MinItem().Offset),
+				nodeData.MinItem(g).ObjectID,
+				nodeData.MinItem(g).ItemType,
+				nodeData.MinItem(g).Offset),
 			fmt.Sprintf(" max_item:  {%d,%v,%d}}",
-				nodeData.MaxItem().ObjectID,
-				nodeData.MaxItem().ItemType,
-				nodeData.MaxItem().Offset),
+				nodeData.MaxItem(g).ObjectID,
+				nodeData.MaxItem(g).ItemType,
+				nodeData.MaxItem(g).Offset),
 		}
 	} else if nodeErr, ok := g.BadNodes[node]; ok {
 		return []string{
@@ -43,7 +43,7 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
 }
 
 func (g Graph) renderEdge(kp GraphEdge) []string {
-	a := fmt.Sprintf("[%d]={", kp.FromItem)
+	a := fmt.Sprintf("[%d]={", kp.FromSlot)
 	b := strings.Repeat(" ", len(a))
 	ret := []string{
 		a + fmt.Sprintf("ToNode:  %v,", kp.ToNode),
@@ -59,7 +59,7 @@ func (g Graph) renderEdge(kp GraphEdge) []string {
 	if toNode, ok := g.Nodes[kp.ToNode]; !ok {
 		err = g.BadNodes[kp.ToNode]
 	} else {
-		err = checkNodeExpectations(kp, toNode)
+		err = g.loopCheckNodeExpectations(kp, toNode)
 	}
 	if err != nil {
 		c := strings.Repeat(" ", len(a)-1)
@@ -110,7 +110,7 @@ func (g Graph) renderLoop(stack []btrfsvol.LogicalAddr) []string {
 	return lines
 }
 
-func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error {
+func (g Graph) loopCheckNodeExpectations(kp GraphEdge, toNode GraphNode) error {
 	var errs derror.MultiError
 	if toNode.Level != kp.ToLevel {
 		errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v",
@@ -123,9 +123,9 @@ func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error {
 	switch {
 	case len(toNode.Items) == 0:
 		errs = append(errs, fmt.Errorf("node.num_items=0"))
-	case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem() != kp.ToKey:
+	case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem(g) != kp.ToKey:
 		errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
-			kp.ToKey, toNode.MinItem()))
+			kp.ToKey, toNode.MinItem(g)))
 	}
 	if len(errs) > 0 {
 		return errs
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index e6a0399..9035b98 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -346,12 +346,13 @@ func (tree oldRebuiltTree) TreeSubrange(ctx context.Context, min int, searcher b
 	return err
 }
 
-// TreeWalk implements btrfstree.Tree.  It doesn't actually visit
-// nodes or keypointers (just items).
+// TreeWalk implements btrfstree.Tree.  It only visits items and valid
+// leaf nodes (not the superblock, interior nodes, or bad nodes).
 func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
-	if cbs.Item == nil && cbs.BadItem == nil {
+	if cbs.Node == nil && cbs.Item == nil && cbs.BadItem == nil {
 		return
 	}
+	visitedNodes := make(containers.Set[btrfsvol.LogicalAddr])
 	var node *btrfstree.Node
 	tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
 		if ctx.Err() != nil {
@@ -361,34 +362,56 @@ func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkH
 		if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
 			tree.forrest.ReleaseNode(node)
 			node = tree.forrest.readNode(ctx, indexItem.Value.Node)
+			if cbs.Node != nil && !visitedNodes.Has(indexItem.Value.Node.LAddr) {
+				nodePath := btrfstree.Path{
+					btrfstree.PathRoot{
+						Tree:         tree,
+						TreeID:       tree.ID,
+						ToAddr:       indexItem.Value.Node.LAddr,
+						ToGeneration: indexItem.Value.Node.Generation,
+						ToLevel:      indexItem.Value.Node.Level,
+					},
+				}
+				cbs.Node(nodePath, node)
+				if ctx.Err() != nil {
+					return false
+				}
+				visitedNodes.Insert(indexItem.Value.Node.LAddr)
+			}
 		}
-		item := node.BodyLeaf[indexItem.Value.Slot]
-
-		itemPath := btrfstree.Path{
-			btrfstree.PathRoot{
-				Tree:         tree,
-				TreeID:       tree.ID,
-				ToAddr:       indexItem.Value.Node.LAddr,
-				ToGeneration: indexItem.Value.Node.Generation,
-				ToLevel:      indexItem.Value.Node.Level,
-			},
-			btrfstree.PathItem{
-				FromTree: indexItem.Value.Node.Owner,
-				FromSlot: indexItem.Value.Slot,
-				ToKey:    indexItem.Value.Key,
-			},
-		}
-		switch item.Body.(type) {
-		case *btrfsitem.Error:
-			if cbs.BadItem != nil {
-				cbs.BadItem(itemPath, item)
+
+		if cbs.Item != nil || cbs.BadItem != nil {
+			item := node.BodyLeaf[indexItem.Value.Slot]
+			itemPath := btrfstree.Path{
+				btrfstree.PathRoot{
+					Tree:         tree,
+					TreeID:       tree.ID,
+					ToAddr:       indexItem.Value.Node.LAddr,
+					ToGeneration: indexItem.Value.Node.Generation,
+					ToLevel:      indexItem.Value.Node.Level,
+				},
+				btrfstree.PathItem{
+					FromTree: indexItem.Value.Node.Owner,
+					FromSlot: indexItem.Value.Slot,
+					ToKey:    indexItem.Value.Key,
+				},
 			}
-		default:
-			if cbs.Item != nil {
-				cbs.Item(itemPath, item)
+			switch item.Body.(type) {
+			case *btrfsitem.Error:
+				if cbs.BadItem != nil {
+					cbs.BadItem(itemPath, item)
+				}
+			default:
+				if cbs.Item != nil {
+					cbs.Item(itemPath, item)
+				}
+			}
+			if ctx.Err() != nil {
+				return false
 			}
 		}
-		return ctx.Err() == nil
+
+		return true
 	})
 	tree.forrest.ReleaseNode(node)
 }
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 60f3010..fcfb353 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -47,6 +47,9 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 		key.Offset = 0
 		return tgt.Compare(key)
 	})
+	if !ok {
+		return 0, btrfsitem.Root{}, false
+	}
 	itemBody := cb.forrest.readItem(ctx, itemPtr)
 	defer itemBody.Free()
 	switch itemBody := itemBody.(type) {
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index 73dc01e..80a9e4b 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -48,8 +48,8 @@ func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.I
 			}
 			return nil
 		},
-		MinItem: containers.OptionalValue(graphInfo.MinItem()),
-		MaxItem: containers.OptionalValue(graphInfo.MaxItem()),
+		MinItem: containers.OptionalValue(graphInfo.MinItem(ts.graph)),
+		MaxItem: containers.OptionalValue(graphInfo.MaxItem(ts.graph)),
 	})
 	defer ts.file.ReleaseNode(node)
 	if err != nil {
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index e65a3f6..b996bdb 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -33,13 +33,13 @@ type RebuiltTree struct {
 	mu    sync.RWMutex
 	Roots containers.Set[btrfsvol.LogicalAddr]
 	// There are 3 more mutable "members" that are protected by
-	// `mu`; but they live in a shared ARCache.  They are all
+	// `mu`; but they live in a shared Cache.  They are all
 	// derived from tree.Roots, which is why it's OK if they get
 	// evicted.
 	//
-	//  1. tree.leafToRoots()           = tree.forrest.leafs.Load(tree.ID)
-	//  2. tree.RebuiltItems()          = tree.forrest.incItems.Load(tree.ID)
-	//  3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Load(tree.ID)
+	//  1. tree.leafToRoots()           = tree.forrest.leafs.Acquire(tree.ID)
+	//  2. tree.RebuiltItems()          = tree.forrest.incItems.Acquire(tree.ID)
+	//  3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Acquire(tree.ID)
 }
 
 // evictable member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////
@@ -120,7 +120,7 @@ func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAdd
 }
 
 // isOwnerOK returns whether it is permissible for a node with
-// .Head.Owner=owner to be in this tree.
+// .Head.Owner=owner and .Head.Generation=gen to be in this tree.
 func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool {
 	for {
 		if owner == tree.ID {
diff --git a/lib/containers/intervaltree.go b/lib/containers/intervaltree.go
index d2e2732..16a9fdd 100644
--- a/lib/containers/intervaltree.go
+++ b/lib/containers/intervaltree.go
@@ -4,6 +4,10 @@
 
 package containers
 
+import (
+	"fmt"
+)
+
 type interval[K Ordered[K]] struct {
 	Min, Max K
 }
@@ -71,11 +75,17 @@ func (t *IntervalTree[K, V]) Equal(u *IntervalTree[K, V]) bool {
 
 func (t *IntervalTree[K, V]) Insert(val V) {
 	t.init()
+	min := t.MinFn(val)
+	max := t.MaxFn(val)
+	if max.Compare(min) < 0 {
+		panic(fmt.Errorf("containers.IntervalTree.Insert: max < min: [%v, %v]: %v",
+			min, max, val))
+	}
 	t.inner.Insert(intervalValue[K, V]{
 		Val: val,
 		ValSpan: interval[K]{
-			Min: t.MinFn(val),
-			Max: t.MaxFn(val),
+			Min: min,
+			Max: max,
 		},
 	})
 }