summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLuke Shumaker <lukeshu@lukeshu.com>2022-08-30 21:39:00 -0600
committerLuke Shumaker <lukeshu@lukeshu.com>2022-08-30 21:39:54 -0600
commita9d6b935eef8124efbcfd2c9569fbccd932051de (patch)
tree24b9681825a6dcc40643f7d3d081c21316ee585e
parent4a52c625fdf68a8693d5b3c6eb80e7faf822cb15 (diff)
Change how btrfstree.TreePath generations work
-rw-r--r--lib/btrfs/btrfstree/ops.go80
-rw-r--r--lib/btrfs/btrfstree/path.go35
-rw-r--r--lib/btrfs/btrfstree/readnode.go8
-rw-r--r--lib/btrfs/btrfstree/types_node.go12
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go6
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,
},
},