From a9d6b935eef8124efbcfd2c9569fbccd932051de Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 30 Aug 2022 21:39:00 -0600 Subject: Change how btrfstree.TreePath generations work --- lib/btrfs/btrfstree/ops.go | 80 +++++++++++++++++++-------------------- lib/btrfs/btrfstree/path.go | 35 +++++++++-------- lib/btrfs/btrfstree/readnode.go | 8 ++-- lib/btrfs/btrfstree/types_node.go | 12 +++--- 4 files changed, 65 insertions(+), 70 deletions(-) (limited to 'lib/btrfs/btrfstree') 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 { -- cgit v1.2.3-54-g00ecf