From abdc8394bcb7080f01859cbfe367beecf5aef06f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 5 Sep 2022 10:03:03 -0600 Subject: Add ToKey to TreePaths; MinItem and MaxItem to NodeExpectations --- lib/btrfs/btrfstree/ops.go | 8 ++++++++ lib/btrfs/btrfstree/path.go | 4 ++++ lib/btrfs/btrfstree/readnode.go | 1 + lib/btrfs/btrfstree/types_node.go | 37 ++++++++++++++++++++++++++++--------- 4 files changed, 41 insertions(+), 9 deletions(-) (limited to 'lib/btrfs') diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go index acbdd23..d7db225 100644 --- a/lib/btrfs/btrfstree/ops.go +++ b/lib/btrfs/btrfstree/ops.go @@ -176,6 +176,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl ToNodeAddr: item.BlockPtr, ToNodeGeneration: item.Generation, ToNodeLevel: node.Data.Head.Level - 1, + ToKey: item.Key, }) if cbs.PreKeyPointer != nil { if err := cbs.PreKeyPointer(itemPath, item); err != nil { @@ -199,6 +200,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: i, + ToKey: item.Key, }) if errBody, isErr := item.Body.(btrfsitem.Error); isErr { if cbs.BadItem == nil { @@ -273,6 +275,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, ToNodeAddr: node.Data.BodyInternal[lastGood].BlockPtr, ToNodeGeneration: node.Data.BodyInternal[lastGood].Generation, ToNodeLevel: node.Data.Head.Level - 1, + ToKey: node.Data.BodyInternal[lastGood].Key, }) } else { // leaf node @@ -296,6 +299,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: idx, + ToKey: node.Data.BodyLeaf[idx].Key, }) return path, node, nil } @@ -339,11 +343,13 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical 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, + ToKey: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Key, }) } else { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: len(node.Data.BodyLeaf) - 1, + ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, }) } } @@ -409,11 +415,13 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical 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, + ToKey: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Key, }) } else { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: 0, + ToKey: node.Data.BodyInternal[0].Key, }) } } diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index 212b5df..b40c7ed 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -85,6 +85,10 @@ type TreePathElem struct { // ToNodeAddr, or 0 if this is a leaf item and nothing is // being pointed at. ToNodeLevel uint8 + // ToKey is btrfprim.Key{} this is the root node being pointed + // to, the KeyPointer.Key if this is a non-root node being + // pointed to, or the key of the leaf item being bointed to. + ToKey btrfsprim.Key } func (elem TreePathElem) writeNodeTo(w io.Writer) { diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go index a84e7ee..1c5dd21 100644 --- a/lib/btrfs/btrfstree/readnode.go +++ b/lib/btrfs/btrfstree/readnode.go @@ -67,5 +67,6 @@ func FSReadNode( 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, + MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: path.Node(-1).ToKey}, }) } diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index 59411a0..299c433 100644 --- a/lib/btrfs/btrfstree/types_node.go +++ b/lib/btrfs/btrfstree/types_node.go @@ -9,6 +9,8 @@ import ( "errors" "fmt" + "github.com/datawire/dlib/derror" + "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" @@ -386,6 +388,9 @@ type NodeExpectations struct { Level containers.Optional[uint8] Generation containers.Optional[btrfsprim.Generation] Owner func(btrfsprim.ObjID) error + MinItem containers.Optional[btrfsprim.Key] + // Things knowable from the structure of the tree. + MaxItem containers.Optional[btrfsprim.Key] } type NodeError[Addr ~int64] struct { @@ -472,24 +477,38 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N // sanity checking (that doesn't prevent parsing) + var errs derror.MultiError if exp.LAddr.OK && nodeRef.Data.Head.Addr != exp.LAddr.Val { - return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, - Err: fmt.Errorf("read from laddr=%v but claims to be at laddr=%v", - exp.LAddr.Val, nodeRef.Data.Head.Addr)} + errs = append(errs, fmt.Errorf("read from laddr=%v but claims to be at laddr=%v", + exp.LAddr.Val, nodeRef.Data.Head.Addr)) } if exp.Level.OK && nodeRef.Data.Head.Level != exp.Level.Val { - 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) + errs = append(errs, fmt.Errorf("expected level=%v but claims to be level=%v", + exp.Level.Val, nodeRef.Data.Head.Level)) } 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.Generation.Val, nodeRef.Data.Head.Generation)} + errs = append(errs, 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 { - return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err} + errs = append(errs, err) + } + } + if nodeRef.Data.Head.NumItems == 0 { + errs = append(errs, fmt.Errorf("has no items")) + } else { + if minItem, _ := nodeRef.Data.MinItem(); exp.MinItem.OK && exp.MinItem.Val.Cmp(minItem) > 0 { + errs = append(errs, fmt.Errorf("expected minItem>=%v but node has minItem=%v", + exp.MinItem, minItem)) } + if maxItem, _ := nodeRef.Data.MaxItem(); exp.MaxItem.OK && exp.MaxItem.Val.Cmp(maxItem) < 0 { + errs = append(errs, fmt.Errorf("expected maxItem<=%v but node has maxItem=%v", + exp.MaxItem, maxItem)) + } + } + if len(errs) > 0 { + return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: errs} } // return -- cgit v1.2.3-2-g168b