Change how btrfstree.TreePath generations work

5 files changed, 68 insertions, 73 deletions

diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go
index 02511f5..acbdd23 100644
--- a/lib/btrfs/btrfstree/ops.go
+++ b/lib/btrfs/btrfstree/ops.go
@@ -114,11 +114,11 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID,
 // interface.
 func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	path := TreePath{{
-		FromTree:       rootInfo.TreeID,
-		FromGeneration: rootInfo.Generation,
-		FromItemIdx:    -1,
-		ToNodeAddr:     rootInfo.RootNode,
-		ToNodeLevel:    rootInfo.Level,
+		FromTree:         rootInfo.TreeID,
+		FromItemIdx:      -1,
+		ToNodeAddr:       rootInfo.RootNode,
+		ToNodeGeneration: rootInfo.Generation,
+		ToNodeLevel:      rootInfo.Level,
 	}}
 	fs.treeWalk(ctx, path, errHandle, cbs)
 }
@@ -171,11 +171,11 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 	if node != nil {
 		for i, item := range node.Data.BodyInternal {
 			itemPath := append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    i,
-				ToNodeAddr:     item.BlockPtr,
-				ToNodeLevel:    node.Data.Head.Level - 1,
+				FromTree:         node.Data.Head.Owner,
+				FromItemIdx:      i,
+				ToNodeAddr:       item.BlockPtr,
+				ToNodeGeneration: item.Generation,
+				ToNodeLevel:      node.Data.Head.Level - 1,
 			})
 			if cbs.PreKeyPointer != nil {
 				if err := cbs.PreKeyPointer(itemPath, item); err != nil {
@@ -197,9 +197,8 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 		}
 		for i, item := range node.Data.BodyLeaf {
 			itemPath := append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    i,
+				FromTree:    node.Data.Head.Owner,
+				FromItemIdx: i,
 			})
 			if errBody, isErr := item.Body.(btrfsitem.Error); isErr {
 				if cbs.BadItem == nil {
@@ -236,11 +235,11 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 
 func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
 	path := TreePath{{
-		FromTree:       treeRoot.TreeID,
-		FromGeneration: treeRoot.Generation,
-		FromItemIdx:    -1,
-		ToNodeAddr:     treeRoot.RootNode,
-		ToNodeLevel:    treeRoot.Level,
+		FromTree:         treeRoot.TreeID,
+		FromItemIdx:      -1,
+		ToNodeAddr:       treeRoot.RootNode,
+		ToNodeGeneration: treeRoot.Generation,
+		ToNodeLevel:      treeRoot.Level,
 	}}
 	for {
 		if path.Node(-1).ToNodeAddr == 0 {
@@ -269,11 +268,11 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 				return TreePath{}, nil, iofs.ErrNotExist
 			}
 			path = append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    lastGood,
-				ToNodeAddr:     node.Data.BodyInternal[lastGood].BlockPtr,
-				ToNodeLevel:    node.Data.Head.Level - 1,
+				FromTree:         node.Data.Head.Owner,
+				FromItemIdx:      lastGood,
+				ToNodeAddr:       node.Data.BodyInternal[lastGood].BlockPtr,
+				ToNodeGeneration: node.Data.BodyInternal[lastGood].Generation,
+				ToNodeLevel:      node.Data.Head.Level - 1,
 			})
 		} else {
 			// leaf node
@@ -295,9 +294,8 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 				return TreePath{}, nil, iofs.ErrNotExist
 			}
 			path = append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    idx,
+				FromTree:    node.Data.Head.Owner,
+				FromItemIdx: idx,
 			})
 			return path, node, nil
 		}
@@ -336,17 +334,16 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical
 		}
 		if node.Data.Head.Level > 0 {
 			path = append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    len(node.Data.BodyInternal) - 1,
-				ToNodeAddr:     node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
-				ToNodeLevel:    node.Data.Head.Level - 1,
+				FromTree:         node.Data.Head.Owner,
+				FromItemIdx:      len(node.Data.BodyInternal) - 1,
+				ToNodeAddr:       node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
+				ToNodeGeneration: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Generation,
+				ToNodeLevel:      node.Data.Head.Level - 1,
 			})
 		} else {
 			path = append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    len(node.Data.BodyLeaf) - 1,
+				FromTree:    node.Data.Head.Owner,
+				FromItemIdx: len(node.Data.BodyLeaf) - 1,
 			})
 		}
 	}
@@ -407,17 +404,16 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical
 		}
 		if node.Data.Head.Level > 0 {
 			path = append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    0,
-				ToNodeAddr:     node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
-				ToNodeLevel:    node.Data.Head.Level - 1,
+				FromTree:         node.Data.Head.Owner,
+				FromItemIdx:      0,
+				ToNodeAddr:       node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
+				ToNodeGeneration: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Generation,
+				ToNodeLevel:      node.Data.Head.Level - 1,
 			})
 		} else {
 			path = append(path, TreePathElem{
-				FromTree:       node.Data.Head.Owner,
-				FromGeneration: node.Data.Head.Generation,
-				FromItemIdx:    0,
+				FromTree:    node.Data.Head.Owner,
+				FromItemIdx: 0,
 			})
 		}
 	}
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 4a4d66e..212b5df 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -27,53 +27,48 @@ import (
 //
 //	[superblock: tree=B, lvl=3, gen=6]
 //	     |
-//	     | <------------------------------------------ pathElem={from_tree:B, from_gen=6, from_idx=-1,
-//	     |                                                       to_addr:0x01, to_lvl=3}
+//	     | <------------------------------------------ pathElem={from_tree:B, from_idx=-1,
+//	     |                                                       to_addr:0x01, to_gen=6, to_lvl=3}
 //	  +[0x01]-------------+
 //	  | lvl=3 gen=6 own=B |
 //	  +-+-+-+-+-+-+-+-+-+-+
 //	  |0|1|2|3|4|5|6|7|8|9|
 //	  +-+-+-+-+-+-+-+-+-+-+
 //	                 |
-//	                 | <------------------------------ pathElem:{from_tree:B, from_gen:6, from_idx:7,
-//	                 |                                           to_addr:0x02, to_lvl:2}
+//	                 | <------------------------------ pathElem:{from_tree:B, from_idx:7,
+//	                 |                                           to_addr:0x02, to_gen:5, to_lvl:2}
 //	              +[0x02]--------------+
 //	              | lvl=2 gen=5 own=B  |
 //	              +-+-+-+-+-+-+-+-+-+-+
 //	              |0|1|2|3|4|5|6|7|8|9|
 //	              +-+-+-+-+-+-+-+-+-+-+
 //	                           |
-//	                           | <-------------------- pathElem={from_tree:B, from_gen:5, from_idx:6,
-//	                           |                                 to_addr:0x03, to_lvl:1}
+//	                           | <-------------------- pathElem={from_tree:B, from_idx:6,
+//	                           |                                 to_addr:0x03, to_gen:5, to_lvl:1}
 //	                        +[0x03]-------------+
 //	                        | lvl=1 gen=5 own=A |
 //	                        +-+-+-+-+-+-+-+-+-+-+
 //	                        |0|1|2|3|4|5|6|7|8|9|
 //	                        +-+-+-+-+-+-+-+-+-+-+
 //	                               |
-//	                               | <---------------- pathElem={from_tree:A, from_gen:5, from_idx:3,
-//	                               |                             to_addr:0x04, to_lvl:0}
+//	                               | <---------------- pathElem={from_tree:A, from_idx:3,
+//	                               |                             to_addr:0x04, to_gen:2, lvl:0}
 //	                             +[0x04]-------------+
 //	                             | lvl=0 gen=2 own=A |
 //	                             +-+-+-+-+-+-+-+-+-+-+
 //	                             |0|1|2|3|4|5|6|7|8|9|
 //	                             +-+-+-+-+-+-+-+-+-+-+
 //	                                |
-//	                                | <--------------- pathElem={from_tree:A, from_gen:2, from_idx:1,
-//	                                |                            to_addr:0, to_lvl:0}
+//	                                | <--------------- pathElem={from_tree:A, from_idx:1,
+//	                                |                            to_addr:0, to_gen: 0, to_lvl:0}
 //	                              [item]
 type TreePath []TreePathElem
 
-// A TreePathElem essentially represents a KeyPointer.  If there is an
-// error looking up the tree root, everything but FromTree is zero.
+// A TreePathElem essentially represents a KeyPointer.
 type TreePathElem struct {
 	// FromTree is the owning tree ID of the parent node; or the
 	// well-known tree ID if this is the root.
 	FromTree btrfsprim.ObjID
-	// FromGeneration is the generation of the parent node the
-	// parent node; or generation stored in the superblock if this
-	// is the root.
-	FromGeneration btrfsprim.Generation
 	// FromItemIdx is the index of this KeyPointer in the parent
 	// Node; or -1 if this is the root and there is no KeyPointer.
 	FromItemIdx int
@@ -82,7 +77,11 @@ type TreePathElem struct {
 	// points at, or 0 if this is a leaf item and nothing is being
 	// pointed at.
 	ToNodeAddr btrfsvol.LogicalAddr
-	// ToNodeLevel is the expected or actual level of the node at
+	// ToNodeGeneration is the expected generation of the node at
+	// ToNodeAddr, or 0 if this is a leaf item and nothing is
+	// being pointed at.
+	ToNodeGeneration btrfsprim.Generation
+	// ToNodeLevel is the expected level of the node at
 	// ToNodeAddr, or 0 if this is a leaf item and nothing is
 	// being pointed at.
 	ToNodeLevel uint8
@@ -98,7 +97,7 @@ func (path TreePath) String() string {
 	} else {
 		var ret strings.Builder
 		fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsitem.ROOT_ITEM_KEY))
-		if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree}) {
+		if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemIdx: -1}) {
 			ret.WriteString("(empty-path)")
 		} else {
 			path[0].writeNodeTo(&ret)
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
index e363241..a84e7ee 100644
--- a/lib/btrfs/btrfstree/readnode.go
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -63,9 +63,9 @@ func FSReadNode(
 	}
 
 	return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{
-		LAddr:         containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
-		Level:         containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
-		MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration},
-		Owner:         checkOwner,
+		LAddr:      containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
+		Level:      containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
+		Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).ToNodeGeneration},
+		Owner:      checkOwner,
 	})
 }
diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
index dcb6540..59411a0 100644
--- a/lib/btrfs/btrfstree/types_node.go
+++ b/lib/btrfs/btrfstree/types_node.go
@@ -383,9 +383,9 @@ var ErrNotANode = errors.New("does not look like a node")
 type NodeExpectations struct {
 	LAddr containers.Optional[btrfsvol.LogicalAddr]
 	// Things knowable from the parent.
-	Level         containers.Optional[uint8]
-	MaxGeneration containers.Optional[btrfsprim.Generation]
-	Owner         func(btrfsprim.ObjID) error
+	Level      containers.Optional[uint8]
+	Generation containers.Optional[btrfsprim.Generation]
+	Owner      func(btrfsprim.ObjID) error
 }
 
 type NodeError[Addr ~int64] struct {
@@ -481,10 +481,10 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
 		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected level=%v but claims to be level=%v",
 			addr, exp.Level.Val, nodeRef.Data.Head.Level)
 	}
-	if exp.MaxGeneration.OK && nodeRef.Data.Head.Generation > exp.MaxGeneration.Val {
+	if exp.Generation.OK && nodeRef.Data.Head.Generation != exp.Generation.Val {
 		return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr,
-			Err: fmt.Errorf("expected generation<=%v but claims to be generation=%v",
-				exp.MaxGeneration.Val, nodeRef.Data.Head.Generation)}
+			Err: fmt.Errorf("expected generation=%v but claims to be generation=%v",
+				exp.Generation.Val, nodeRef.Data.Head.Generation)}
 	}
 	if exp.Owner != nil {
 		if err := exp.Owner(nodeRef.Data.Head.Owner); err != nil {
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
index fc46d27..5655eb6 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
@@ -74,8 +74,8 @@ func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btr
 	}
 
 	sort.Slice(badNodes, func(i, j int) bool {
-		iGen := badNodes[i].Path.Node(-1).FromGeneration
-		jGen := badNodes[j].Path.Node(-1).FromGeneration
+		iGen := badNodes[i].Path.Node(-1).ToNodeGeneration
+		jGen := badNodes[j].Path.Node(-1).ToNodeGeneration
 		switch {
 		case iGen < jGen:
 			return true
@@ -117,7 +117,7 @@ func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btr
 					Addr:          path.Node(-1).ToNodeAddr,
 					ChunkTreeUUID: chunkTreeUUID,
 					//Owner:      TBD, // see RebuiltNode.InTrees
-					Generation: path.Node(-1).FromGeneration,
+					Generation: path.Node(-1).ToNodeGeneration,
 					Level:      path.Node(-1).ToNodeLevel,
 				},
 			},