From 74a82894df9bdef19d321611255b7923f9f25aff Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 2 Apr 2023 18:36:11 -0600
Subject: btrfsutil: GraphNode: Have .MinItem and .MaxItem work on interior
 nodes too

---
 lib/btrfsutil/graph.go            | 39 +++++++++++++++++++++++++++++----------
 lib/btrfsutil/graph_loops.go      | 20 ++++++++++----------
 lib/btrfsutil/rebuilt_readitem.go |  4 ++--
 3 files changed, 41 insertions(+), 22 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 090ccf4..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 {
@@ -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,
diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go
index d613481..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{
@@ -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/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 {
-- 
cgit v1.2.3-54-g00ecf