From 8387d36fac1f01505b37d90d675609460202310d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:42:32 -0700 Subject: btrfstree: Shuffle things between files --- lib/btrfs/btrfstree/btree.go | 86 +++++++++++++++++++++++++++++++++++++++ lib/btrfs/btrfstree/btree_tree.go | 72 -------------------------------- 2 files changed, 86 insertions(+), 72 deletions(-) create mode 100644 lib/btrfs/btrfstree/btree.go diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go new file mode 100644 index 0000000..2fd7c39 --- /dev/null +++ b/lib/btrfs/btrfstree/btree.go @@ -0,0 +1,86 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "context" + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" +) + +// TreeOperator is an interface for performing basic btree operations. +type TreeOperator interface { + // TreeWalk walks a tree, triggering callbacks for every node, + // key-pointer, and item; as well as for any errors encountered. + // + // If the tree is valid, then everything is walked in key-order; but if + // the tree is broken, then ordering is not guaranteed. + // + // Canceling the Context causes TreeWalk to return early; no + // values from the Context are used. + // + // The lifecycle of callbacks is: + // + // 001 .PreNode() + // 002 (read node) + // 003 .Node() (or .BadNode()) + // for item in node.items: + // if interior: + // 004 .PreKeyPointer() + // 005 (recurse) + // 006 .PostKeyPointer() + // else: + // 004 .Item() (or .BadItem()) + // 007 .PostNode() + TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) + + TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) + TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers + + // If some items are able to be read, but there is an error reading the + // full set, then it might return *both* a list of items and an error. + // + // If no such item is found, an error that is io/fs.ErrNotExist is + // returned. + TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers +} + +type TreeWalkHandler struct { + // Callbacks for entire nodes. + // + // If any of these return an error that is io/fs.SkipDir, the + // node immediately stops getting processed; if PreNode, Node, + // or BadNode return io/fs.SkipDir then key pointers and items + // within the node are not processed. + PreNode func(TreePath) error + Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error + BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error + PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error + // Callbacks for items on interior nodes + PreKeyPointer func(TreePath, KeyPointer) error + PostKeyPointer func(TreePath, KeyPointer) error + // Callbacks for items on leaf nodes + Item func(TreePath, Item) error + BadItem func(TreePath, Item) error +} + +type TreeError struct { + Path TreePath + Err error +} + +func (e *TreeError) Unwrap() error { return e.Err } + +func (e *TreeError) Error() string { + return fmt.Sprintf("%v: %v", e.Path, e.Err) +} + +type NodeSource interface { + Superblock() (*Superblock, error) + ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) +} diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index e75eb0b..afaaf92 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -20,78 +20,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -// TreeOperator is an interface for performing basic btree operations. -type TreeOperator interface { - // TreeWalk walks a tree, triggering callbacks for every node, - // key-pointer, and item; as well as for any errors encountered. - // - // If the tree is valid, then everything is walked in key-order; but if - // the tree is broken, then ordering is not guaranteed. - // - // Canceling the Context causes TreeWalk to return early; no - // values from the Context are used. - // - // The lifecycle of callbacks is: - // - // 001 .PreNode() - // 002 (read node) - // 003 .Node() (or .BadNode()) - // for item in node.items: - // if interior: - // 004 .PreKeyPointer() - // 005 (recurse) - // 006 .PostKeyPointer() - // else: - // 004 .Item() (or .BadItem()) - // 007 .PostNode() - TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) - - TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) - TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers - - // If some items are able to be read, but there is an error reading the - // full set, then it might return *both* a list of items and an error. - // - // If no such item is found, an error that is io/fs.ErrNotExist is - // returned. - TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers -} - -type TreeWalkHandler struct { - // Callbacks for entire nodes. - // - // If any of these return an error that is io/fs.SkipDir, the - // node immediately stops getting processed; if PreNode, Node, - // or BadNode return io/fs.SkipDir then key pointers and items - // within the node are not processed. - PreNode func(TreePath) error - Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error - PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - // Callbacks for items on interior nodes - PreKeyPointer func(TreePath, KeyPointer) error - PostKeyPointer func(TreePath, KeyPointer) error - // Callbacks for items on leaf nodes - Item func(TreePath, Item) error - BadItem func(TreePath, Item) error -} - -type TreeError struct { - Path TreePath - Err error -} - -func (e *TreeError) Unwrap() error { return e.Err } - -func (e *TreeError) Error() string { - return fmt.Sprintf("%v: %v", e.Path, e.Err) -} - -type NodeSource interface { - Superblock() (*Superblock, error) - ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) -} - type TreeOperatorImpl struct { NodeSource } -- cgit v1.1-4-g5e80 From 56e44b0630448d44f7aa7f85b2098007ddbae06f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 15:17:11 -0600 Subject: btrfstree: Distinguish between tree-not-found and item-not-found --- lib/btrfs/btrfstree/btree.go | 5 ++- lib/btrfs/btrfstree/btree_err.go | 32 ++++++++++++++++++ lib/btrfs/btrfstree/btree_err_test.go | 64 +++++++++++++++++++++++++++++++++++ lib/btrfs/btrfstree/btree_forrest.go | 4 +++ lib/btrfs/btrfstree/btree_tree.go | 8 ++--- lib/btrfsutil/old_rebuilt_forrest.go | 5 ++- 6 files changed, 110 insertions(+), 8 deletions(-) create mode 100644 lib/btrfs/btrfstree/btree_err.go create mode 100644 lib/btrfs/btrfstree/btree_err_test.go diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 2fd7c39..7b3721b 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -45,7 +45,10 @@ type TreeOperator interface { // If some items are able to be read, but there is an error reading the // full set, then it might return *both* a list of items and an error. // - // If no such item is found, an error that is io/fs.ErrNotExist is + // If the tree is not found, an error that is ErrNoTree is + // returned. + // + // If no such item is found, an error that is ErrNoItem is // returned. TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers } diff --git a/lib/btrfs/btrfstree/btree_err.go b/lib/btrfs/btrfstree/btree_err.go new file mode 100644 index 0000000..57fb283 --- /dev/null +++ b/lib/btrfs/btrfstree/btree_err.go @@ -0,0 +1,32 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + iofs "io/fs" +) + +// For both ErrNoItem and ErrNoTree, `errors.Is(err, +// io/fs.ErrNotExist)` returns true. +var ( + ErrNoItem = errNotExist("item") + ErrNoTree = errNotExist("tree") +) + +func errNotExist(thing string) error { + return ¬ExistError{thing} +} + +type notExistError struct { + thing string +} + +func (e *notExistError) Error() string { + return e.thing + " does not exist" +} + +func (*notExistError) Is(target error) bool { + return target == iofs.ErrNotExist +} diff --git a/lib/btrfs/btrfstree/btree_err_test.go b/lib/btrfs/btrfstree/btree_err_test.go new file mode 100644 index 0000000..381bd56 --- /dev/null +++ b/lib/btrfs/btrfstree/btree_err_test.go @@ -0,0 +1,64 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree_test + +import ( + "errors" + "fmt" + iofs "io/fs" + "testing" + + "github.com/stretchr/testify/assert" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" +) + +func TestErrs(t *testing.T) { + t.Parallel() + + errItem := fmt.Errorf("my item: %w", btrfstree.ErrNoItem) + errTree := fmt.Errorf("my tree: %w", btrfstree.ErrNoTree) + + // 1. errItem + // 2. errTree + // 3. btrfstree.ErrNoItem + // 4. btrfstree.ErrNoTree + // 5. iofs.ErrNotExist + + // 1 + assert.Equal(t, errors.Is(errItem, errItem), true) + assert.Equal(t, errors.Is(errItem, errTree), false) + assert.Equal(t, errors.Is(errItem, btrfstree.ErrNoItem), true) + assert.Equal(t, errors.Is(errItem, btrfstree.ErrNoTree), false) + assert.Equal(t, errors.Is(errItem, iofs.ErrNotExist), true) + + // 2 + assert.Equal(t, errors.Is(errTree, errItem), false) + assert.Equal(t, errors.Is(errTree, errTree), true) + assert.Equal(t, errors.Is(errTree, btrfstree.ErrNoItem), false) + assert.Equal(t, errors.Is(errTree, btrfstree.ErrNoTree), true) + assert.Equal(t, errors.Is(errTree, iofs.ErrNotExist), true) + + // 3 + assert.Equal(t, errors.Is(btrfstree.ErrNoItem, errItem), false) + assert.Equal(t, errors.Is(btrfstree.ErrNoItem, errTree), false) + assert.Equal(t, errors.Is(btrfstree.ErrNoItem, btrfstree.ErrNoItem), true) + assert.Equal(t, errors.Is(btrfstree.ErrNoItem, btrfstree.ErrNoTree), false) + assert.Equal(t, errors.Is(btrfstree.ErrNoItem, iofs.ErrNotExist), true) + + // 4 + assert.Equal(t, errors.Is(btrfstree.ErrNoTree, errItem), false) + assert.Equal(t, errors.Is(btrfstree.ErrNoTree, errTree), false) + assert.Equal(t, errors.Is(btrfstree.ErrNoTree, btrfstree.ErrNoItem), false) + assert.Equal(t, errors.Is(btrfstree.ErrNoTree, btrfstree.ErrNoTree), true) + assert.Equal(t, errors.Is(btrfstree.ErrNoTree, iofs.ErrNotExist), true) + + // 5 + assert.Equal(t, errors.Is(iofs.ErrNotExist, errItem), false) + assert.Equal(t, errors.Is(iofs.ErrNotExist, errTree), false) + assert.Equal(t, errors.Is(iofs.ErrNotExist, btrfstree.ErrNoItem), false) + assert.Equal(t, errors.Is(iofs.ErrNotExist, btrfstree.ErrNoTree), false) + assert.Equal(t, errors.Is(iofs.ErrNotExist, iofs.ErrNotExist), true) +} diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index 0bab610..625fb30 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -5,6 +5,7 @@ package btrfstree import ( + "errors" "fmt" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" @@ -69,6 +70,9 @@ func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*Tr default: rootItem, err := fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, RootItemSearchFn(treeID)) if err != nil { + if errors.Is(err, ErrNoItem) { + err = ErrNoTree + } return nil, err } switch rootItemBody := rootItem.Body.(type) { diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index afaaf92..c51efa5 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -180,7 +180,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, }} for { if path.Node(-1).ToNodeAddr == 0 { - return nil, nil, iofs.ErrNotExist + return nil, nil, ErrNoItem } node, err := fs.ReadNode(path) if err != nil { @@ -204,7 +204,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, }) if !ok { FreeNodeRef(node) - return nil, nil, iofs.ErrNotExist + return nil, nil, ErrNoItem } toMaxKey := path.Node(-1).ToMaxKey if lastGood+1 < len(node.Data.BodyInterior) { @@ -228,7 +228,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, // // + + + + 0 - - - - // - // Such an item might not exist; in this case, return nil/ErrNotExist. + // Such an item might not exist; in this case, return (nil, ErrNoItem). // Multiple such items might exist; in this case, it does not matter which // is returned. // @@ -238,7 +238,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, }) if !ok { FreeNodeRef(node) - return nil, nil, iofs.ErrNotExist + return nil, nil, ErrNoItem } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index af2643a..4076072 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -7,7 +7,6 @@ package btrfsutil import ( "context" "fmt" - iofs "io/fs" "sync" "github.com/datawire/dlib/derror" @@ -226,7 +225,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfspri return fn(indexItem.Key, indexItem.ItemSize) }) if indexItem == nil { - return btrfstree.Item{}, bt.addErrs(tree, fn, iofs.ErrNotExist) + return btrfstree.Item{}, bt.addErrs(tree, fn, btrfstree.ErrNoItem) } itemPath := bt.arena.Inflate(indexItem.Value.Path) @@ -258,7 +257,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs return true }) if len(indexItems) == 0 { - return nil, bt.addErrs(tree, fn, iofs.ErrNotExist) + return nil, bt.addErrs(tree, fn, btrfstree.ErrNoItem) } ret := make([]btrfstree.Item, len(indexItems)) -- cgit v1.1-4-g5e80 From d7e086766e0f4396f29987d3798cefc1bb675d1c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 15:17:11 -0600 Subject: btrfstree: Have errors include context of what was being searched for --- .../inspect/rebuildtrees/rebuild_wanttyp.go | 1 + lib/btrfs/btrfstree/btree.go | 13 +- lib/btrfs/btrfstree/btree_forrest.go | 17 +- lib/btrfs/btrfstree/btree_searchers.go | 209 +++++++++++++++++++++ lib/btrfs/btrfstree/btree_tree.go | 31 +-- lib/btrfs/csums.go | 14 +- lib/btrfs/io3_btree.go | 8 +- lib/btrfs/io4_fs.go | 6 +- lib/btrfsutil/old_rebuilt_forrest.go | 30 +-- 9 files changed, 256 insertions(+), 73 deletions(-) create mode 100644 lib/btrfs/btrfstree/btree_searchers.go diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go index a517579..4aab669 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go @@ -23,6 +23,7 @@ const ( offsetName ) +// TODO(lukeshu): Delete the 'Want' type in favor of btrfstree.Search. type Want struct { ObjectID btrfsprim.ObjID ItemType btrfsprim.ItemType diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 7b3721b..4c10ffa 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -13,6 +13,15 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) +type TreeSearcher interface { + // How the search should be described in the event of an + // error. + fmt.Stringer + + // size is math.MaxUint32 for key-pointers + Search(key btrfsprim.Key, size uint32) int +} + // TreeOperator is an interface for performing basic btree operations. type TreeOperator interface { // TreeWalk walks a tree, triggering callbacks for every node, @@ -40,7 +49,7 @@ type TreeOperator interface { TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) - TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers + TreeSearch(treeID btrfsprim.ObjID, search TreeSearcher) (Item, error) // If some items are able to be read, but there is an error reading the // full set, then it might return *both* a list of items and an error. @@ -50,7 +59,7 @@ type TreeOperator interface { // // If no such item is found, an error that is ErrNoItem is // returned. - TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers + TreeSearchAll(treeID btrfsprim.ObjID, search TreeSearcher) ([]Item, error) } type TreeWalkHandler struct { diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index 625fb30..0f46d42 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -22,19 +22,6 @@ type TreeRoot struct { Generation btrfsprim.Generation } -func RootItemSearchFn(treeID btrfsprim.ObjID) func(btrfsprim.Key, uint32) int { - return func(key btrfsprim.Key, _ uint32) int { - if key.ObjectID == treeID && key.ItemType == btrfsitem.ROOT_ITEM_KEY { - return 0 - } - return btrfsprim.Key{ - ObjectID: treeID, - ItemType: btrfsitem.ROOT_ITEM_KEY, - Offset: 0, - }.Compare(key) - } -} - // LookupTreeRoot is a utility function to help with implementing the // 'TreeOperator' interface. func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { @@ -68,12 +55,12 @@ func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*Tr Generation: sb.BlockGroupRootGeneration, }, nil default: - rootItem, err := fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, RootItemSearchFn(treeID)) + rootItem, err := fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, SearchRootItem(treeID)) if err != nil { if errors.Is(err, ErrNoItem) { err = ErrNoTree } - return nil, err + return nil, fmt.Errorf("tree %s: %w", treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), err) } switch rootItemBody := rootItem.Body.(type) { case *btrfsitem.Root: diff --git a/lib/btrfs/btrfstree/btree_searchers.go b/lib/btrfs/btrfstree/btree_searchers.go new file mode 100644 index 0000000..6972e43 --- /dev/null +++ b/lib/btrfs/btrfstree/btree_searchers.go @@ -0,0 +1,209 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "fmt" + "strings" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +type SearchItemType int8 + +const ( + ItemTypeAny SearchItemType = iota + ItemTypeExact +) + +type SearchOffset int8 + +const ( + OffsetAny SearchOffset = iota + OffsetExact + OffsetRange // .Search behaves same as OffsetAny (TODO?) + OffsetName // .Search behaves same as OffsetAny +) + +// Search is a fairly generic and reusable implementation of +// TreeSearcher. +type Search struct { + ObjectID btrfsprim.ObjID + + ItemTypeMatching SearchItemType + ItemType btrfsprim.ItemType + + // Offset is totally ignored if .ItemTypeMatching=ItemTypeany. + OffsetMatching SearchOffset + OffsetLow uint64 // only for .OffsetMatching==OffsetExact or .OffsetMatching==OffsetRange + OffsetHigh uint64 // only for .OffsetMatching==OffsetRange + OffsetName string // only for .OffsetMatching==OffsetName +} + +var ( + _ containers.Ordered[Search] = Search{} + _ TreeSearcher = Search{} +) + +// Compare implements containers.Ordered. +func (a Search) Compare(b Search) int { + if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 { + return d + } + if d := containers.NativeCompare(a.ItemType, b.ItemType); d != 0 { + return d + } + if d := containers.NativeCompare(a.OffsetMatching, b.OffsetMatching); d != 0 { + return d + } + if d := containers.NativeCompare(a.OffsetLow, b.OffsetLow); d != 0 { + return d + } + if d := containers.NativeCompare(a.OffsetHigh, b.OffsetHigh); d != 0 { + return d + } + if d := containers.NativeCompare(a.OffsetName, b.OffsetName); d != 0 { + return d + } + return 0 +} + +// String implements fmt.Stringer (and TreeSearcher). +func (o Search) String() string { + var buf strings.Builder + + fmt.Fprintf(&buf, "(%v ", o.ObjectID) + + switch o.ItemTypeMatching { + case ItemTypeAny: + buf.WriteString("? ?)") + return buf.String() + case ItemTypeExact: + fmt.Fprintf(&buf, "%v", o.ItemType) + default: + panic(fmt.Errorf("should not happen: ItemTypeMatching=%#v", o.ItemTypeMatching)) + } + + buf.WriteString(" ") + + switch o.OffsetMatching { + case OffsetAny: + buf.WriteString("?") + case OffsetExact: + fmt.Fprintf(&buf, "%v", o.OffsetLow) + case OffsetRange: + fmt.Fprintf(&buf, "%v-%v", o.OffsetLow, o.OffsetHigh) + case OffsetName: + fmt.Fprintf(&buf, "name=%q", o.OffsetName) + default: + panic(fmt.Errorf("should not happen: OffsetMatching=%#v", o.OffsetMatching)) + } + + buf.WriteString(")") + + return buf.String() +} + +// Search implements TreeSearcher. +func (o Search) Search(k btrfsprim.Key, _ uint32) int { + if d := containers.NativeCompare(o.ObjectID, k.ObjectID); d != 0 { + return d + } + + switch o.ItemTypeMatching { + case ItemTypeAny: + return 0 + case ItemTypeExact: + if d := containers.NativeCompare(o.ItemType, k.ItemType); d != 0 { + return d + } + default: + panic(fmt.Errorf("should not happen: ItemTypeMatching=%#v", o.ItemTypeMatching)) + } + + switch o.OffsetMatching { + case OffsetAny, OffsetRange, OffsetName: + return 0 + case OffsetExact: + return containers.NativeCompare(o.OffsetLow, k.Offset) + default: + panic(fmt.Errorf("should not happen: OffsetMatching=%#v", o.OffsetMatching)) + } +} + +//////////////////////////////////////////////////////////////////////////////// + +// SearchObject returns a Search that searches all items belonging to +// a given object. +func SearchObject(objID btrfsprim.ObjID) Search { + return Search{ + ObjectID: objID, + ItemTypeMatching: ItemTypeAny, + } +} + +// SearchExactKey returns a Search that searches for the exact key. +func SearchExactKey(k btrfsprim.Key) Search { + return Search{ + ObjectID: k.ObjectID, + + ItemTypeMatching: ItemTypeExact, + ItemType: k.ItemType, + + OffsetMatching: OffsetExact, + OffsetLow: k.Offset, + } +} + +// SearchRootItem returns a Search that searches for the root item for +// the given tree. +func SearchRootItem(treeID btrfsprim.ObjID) Search { + return Search{ + ObjectID: treeID, + + ItemTypeMatching: ItemTypeExact, + ItemType: btrfsprim.ROOT_ITEM_KEY, + + OffsetMatching: OffsetAny, + } +} + +type csumSearcher struct { + laddr btrfsvol.LogicalAddr + algSize int +} + +func (s csumSearcher) String() string { return fmt.Sprintf("csum for laddr=%v", s.laddr) } +func (s csumSearcher) Search(key btrfsprim.Key, size uint32) int { + if d := containers.NativeCompare(btrfsprim.EXTENT_CSUM_OBJECTID, key.ObjectID); d != 0 { + return d + } + if d := containers.NativeCompare(btrfsprim.EXTENT_CSUM_KEY, key.ItemType); d != 0 { + return d + } + itemBeg := btrfsvol.LogicalAddr(key.Offset) + numSums := int64(size) / int64(s.algSize) + itemEnd := itemBeg + btrfsvol.LogicalAddr(numSums*btrfssum.BlockSize) + switch { + case itemEnd <= s.laddr: + return 1 + case s.laddr < itemBeg: + return -1 + default: + return 0 + } +} + +// SearchCSum returns a TreeSearcher that searches for a csum-run +// containing the csum for a given LogicalAddress. +func SearchCSum(laddr btrfsvol.LogicalAddr, algSize int) TreeSearcher { + return csumSearcher{ + laddr: laddr, + algSize: algSize, + } +} diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index c51efa5..df58c0c 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -405,7 +405,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } // TreeSearch implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) { +func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { sb, err := fs.Superblock() if err != nil { return Item{}, err @@ -414,9 +414,9 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim. if err != nil { return Item{}, err } - path, node, err := fs.treeSearch(*rootInfo, fn) + path, node, err := fs.treeSearch(*rootInfo, searcher.Search) if err != nil { - return Item{}, err + return Item{}, fmt.Errorf("item with %s: %w", searcher, err) } item := node.Data.BodyLeaf[path.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() @@ -424,24 +424,13 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim. return item, nil } -// KeySearch returns a comparator suitable to be passed to TreeSearch. -func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int { - return func(key btrfsprim.Key, _ uint32) int { - return fn(key) - } -} - // TreeLookup implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { - item, err := fs.TreeSearch(treeID, KeySearch(key.Compare)) - if err != nil { - err = fmt.Errorf("item with key=%v: %w", key, err) - } - return item, err + return fs.TreeSearch(treeID, SearchExactKey(key)) } // TreeSearchAll implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) { +func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { sb, err := fs.Superblock() if err != nil { return nil, err @@ -450,9 +439,9 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if err != nil { return nil, err } - middlePath, middleNode, err := fs.treeSearch(*rootInfo, fn) + middlePath, middleNode, err := fs.treeSearch(*rootInfo, searcher.Search) if err != nil { - return nil, err + return nil, fmt.Errorf("items with %s: %w", searcher, err) } middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemSlot] @@ -469,7 +458,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr break } prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemSlot] - if fn(prevItem.Key, prevItem.BodySize) != 0 { + if searcher.Search(prevItem.Key, prevItem.BodySize) != 0 { break } item := prevItem @@ -482,7 +471,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr middleNode, err = fs.ReadNode(middlePath) if err != nil { FreeNodeRef(middleNode) - return nil, err + return nil, fmt.Errorf("items with %s: %w", searcher, err) } } nextPath, nextNode := middlePath, middleNode @@ -496,7 +485,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr break } nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemSlot] - if fn(nextItem.Key, nextItem.BodySize) != 0 { + if searcher.Search(nextItem.Key, nextItem.BodySize) != 0 { break } item := nextItem diff --git a/lib/btrfs/csums.go b/lib/btrfs/csums.go index 9e0b755..8515d12 100644 --- a/lib/btrfs/csums.go +++ b/lib/btrfs/csums.go @@ -48,19 +48,7 @@ func ChecksumQualifiedPhysical(fs *FS, alg btrfssum.CSumType, paddr btrfsvol.Qua } func LookupCSum(fs btrfstree.TreeOperator, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.SumRun[btrfsvol.LogicalAddr], error) { - item, err := fs.TreeSearch(btrfsprim.CSUM_TREE_OBJECTID, func(key btrfsprim.Key, size uint32) int { - itemBeg := btrfsvol.LogicalAddr(key.Offset) - numSums := int64(size) / int64(alg.Size()) - itemEnd := itemBeg + btrfsvol.LogicalAddr(numSums*btrfssum.BlockSize) - switch { - case itemEnd <= laddr: - return 1 - case laddr < itemBeg: - return -1 - default: - return 0 - } - }) + item, err := fs.TreeSearch(btrfsprim.CSUM_TREE_OBJECTID, btrfstree.SearchCSum(laddr, alg.Size())) if err != nil { return btrfssum.SumRun[btrfsvol.LogicalAddr]{}, err } diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index db4e42c..8d35269 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -92,13 +92,13 @@ func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.I } // TreeSearch implements btrfstree.TreeOperator. -func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) +func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, searcher) } // TreeSearchAll implements btrfstree.TreeOperator. -func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) +func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, searcher) } var _ btrfstree.TreeOperator = (*FS)(nil) diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 749b2de..e146739 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -83,7 +83,7 @@ type Subvolume struct { func (sv *Subvolume) init() { sv.initOnce.Do(func() { - root, err := sv.FS.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, btrfstree.RootItemSearchFn(sv.TreeID)) + root, err := sv.FS.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, btrfstree.SearchRootItem(sv.TreeID)) if err != nil { sv.rootErr = err } else { @@ -152,9 +152,7 @@ func (sv *Subvolume) LoadFullInode(inode btrfsprim.ObjID) (*FullInode, error) { }, XAttrs: make(map[string]string), } - items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key btrfsprim.Key, _ uint32) int { - return containers.NativeCompare(inode, key.ObjectID) - }) + items, err := sv.FS.TreeSearchAll(sv.TreeID, btrfstree.SearchObject(inode)) if err != nil { val.Errs = append(val.Errs, err) if len(items) == 0 { diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 4076072..61a3e35 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -188,11 +188,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old } func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - item, err := bt.TreeSearch(treeID, btrfstree.KeySearch(key.Compare)) - if err != nil { - err = fmt.Errorf("item with key=%v: %w", key, err) - } - return item, err + return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key)) } func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error { @@ -215,24 +211,24 @@ func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, return errs } -func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (btrfstree.Item, error) { +func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { tree := bt.RebuiltTree(treeID) if tree.RootErr != nil { return btrfstree.Item{}, tree.RootErr } indexItem := tree.Items.Search(func(indexItem oldRebuiltTreeValue) int { - return fn(indexItem.Key, indexItem.ItemSize) + return searcher.Search(indexItem.Key, indexItem.ItemSize) }) if indexItem == nil { - return btrfstree.Item{}, bt.addErrs(tree, fn, btrfstree.ErrNoItem) + return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem)) } itemPath := bt.arena.Inflate(indexItem.Value.Path) node, err := bt.inner.ReadNode(itemPath.Parent()) defer btrfstree.FreeNodeRef(node) if err != nil { - return btrfstree.Item{}, bt.addErrs(tree, fn, err) + return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err)) } item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] @@ -243,7 +239,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfspri return item, nil } -func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]btrfstree.Item, error) { +func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) { tree := bt.RebuiltTree(treeID) if tree.RootErr != nil { return nil, tree.RootErr @@ -251,13 +247,15 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs var indexItems []oldRebuiltTreeValue tree.Items.Subrange( - func(indexItem oldRebuiltTreeValue) int { return fn(indexItem.Key, indexItem.ItemSize) }, + func(indexItem oldRebuiltTreeValue) int { + return searcher.Search(indexItem.Key, indexItem.ItemSize) + }, func(node *containers.RBNode[oldRebuiltTreeValue]) bool { indexItems = append(indexItems, node.Value) return true }) if len(indexItems) == 0 { - return nil, bt.addErrs(tree, fn, btrfstree.ErrNoItem) + return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem)) } ret := make([]btrfstree.Item, len(indexItems)) @@ -270,7 +268,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs node, err = bt.inner.ReadNode(itemPath.Parent()) if err != nil { btrfstree.FreeNodeRef(node) - return nil, bt.addErrs(tree, fn, err) + return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err)) } } ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] @@ -278,7 +276,11 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs } btrfstree.FreeNodeRef(node) - return ret, bt.addErrs(tree, fn, nil) + err := bt.addErrs(tree, searcher.Search, nil) + if err != nil { + err = fmt.Errorf("items with %s: %w", searcher, err) + } + return ret, err } func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { -- cgit v1.1-4-g5e80 From dcf7632d5657973f87e17413849521738273fa61 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 18:16:13 -0600 Subject: btrfsutil: OldRebuiltForrest: errors: Show key range instead of path --- lib/btrfsutil/old_rebuilt_forrest.go | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 61a3e35..d49f34e 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -196,10 +196,10 @@ func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, tree.Errors.Subrange( func(k btrfsprim.Key) int { return fn(k, 0) }, func(v oldRebuiltTreeError) bool { - errs = append(errs, &btrfstree.TreeError{ - Path: bt.arena.Inflate(v.Path), - Err: v.Err, - }) + path := bt.arena.Inflate(v.Path) + minKey := path.Node(-1).ToKey + maxKey := path.Node(-1).ToMaxKey + errs = append(errs, fmt.Errorf("keys %v-%v: %w", minKey, maxKey, v.Err)) return true }) if len(errs) == 0 { -- cgit v1.1-4-g5e80 From c42e8ea5d77a39d096d97600359bd91657da2f05 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 21:03:46 -0600 Subject: btrfsprim: Move Key to a separate file --- lib/btrfs/btrfsprim/key.go | 81 +++++++++++++++++++++++++++++++++++++++++++++ lib/btrfs/btrfsprim/misc.go | 71 --------------------------------------- 2 files changed, 81 insertions(+), 71 deletions(-) create mode 100644 lib/btrfs/btrfsprim/key.go diff --git a/lib/btrfs/btrfsprim/key.go b/lib/btrfs/btrfsprim/key.go new file mode 100644 index 0000000..55f7c05 --- /dev/null +++ b/lib/btrfs/btrfsprim/key.go @@ -0,0 +1,81 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim + +import ( + "fmt" + "math" + + "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +type Key struct { + ObjectID ObjID `bin:"off=0x0, siz=0x8"` // Each tree has its own set of Object IDs. + ItemType ItemType `bin:"off=0x8, siz=0x1"` + Offset uint64 `bin:"off=0x9, siz=0x8"` // The meaning depends on the item type. + binstruct.End `bin:"off=0x11"` +} + +// mimics print-tree.c:btrfs_print_key() +func (key Key) Format(tree ObjID) string { + switch tree { + case UUID_TREE_OBJECTID: + return fmt.Sprintf("(%v %v %#08x)", + key.ObjectID.Format(tree), + key.ItemType, + key.Offset) + case ROOT_TREE_OBJECTID, QUOTA_TREE_OBJECTID: + return fmt.Sprintf("(%v %v %v)", + key.ObjectID.Format(tree), + key.ItemType, + ObjID(key.Offset).Format(tree)) + default: + if key.Offset == math.MaxUint64 { + return fmt.Sprintf("(%v %v -1)", + key.ObjectID.Format(tree), + key.ItemType) + } else { + return fmt.Sprintf("(%v %v %v)", + key.ObjectID.Format(tree), + key.ItemType, + key.Offset) + } + } +} + +func (key Key) String() string { + return key.Format(0) +} + +var MaxKey = Key{ + ObjectID: math.MaxUint64, + ItemType: math.MaxUint8, + Offset: math.MaxUint64, +} + +func (key Key) Mm() Key { + switch { + case key.Offset > 0: + key.Offset-- + case key.ItemType > 0: + key.ItemType-- + case key.ObjectID > 0: + key.ObjectID-- + } + return key +} + +func (a Key) Compare(b Key) int { + if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 { + return d + } + if d := containers.NativeCompare(a.ItemType, b.ItemType); d != 0 { + return d + } + return containers.NativeCompare(a.Offset, b.Offset) +} + +var _ containers.Ordered[Key] = Key{} diff --git a/lib/btrfs/btrfsprim/misc.go b/lib/btrfs/btrfsprim/misc.go index ca2e313..38290d6 100644 --- a/lib/btrfs/btrfsprim/misc.go +++ b/lib/btrfs/btrfsprim/misc.go @@ -5,84 +5,13 @@ package btrfsprim import ( - "fmt" - "math" "time" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) type Generation uint64 -type Key struct { - ObjectID ObjID `bin:"off=0x0, siz=0x8"` // Each tree has its own set of Object IDs. - ItemType ItemType `bin:"off=0x8, siz=0x1"` - Offset uint64 `bin:"off=0x9, siz=0x8"` // The meaning depends on the item type. - binstruct.End `bin:"off=0x11"` -} - -// mimics print-tree.c:btrfs_print_key() -func (key Key) Format(tree ObjID) string { - switch tree { - case UUID_TREE_OBJECTID: - return fmt.Sprintf("(%v %v %#08x)", - key.ObjectID.Format(tree), - key.ItemType, - key.Offset) - case ROOT_TREE_OBJECTID, QUOTA_TREE_OBJECTID: - return fmt.Sprintf("(%v %v %v)", - key.ObjectID.Format(tree), - key.ItemType, - ObjID(key.Offset).Format(tree)) - default: - if key.Offset == math.MaxUint64 { - return fmt.Sprintf("(%v %v -1)", - key.ObjectID.Format(tree), - key.ItemType) - } else { - return fmt.Sprintf("(%v %v %v)", - key.ObjectID.Format(tree), - key.ItemType, - key.Offset) - } - } -} - -func (key Key) String() string { - return key.Format(0) -} - -var MaxKey = Key{ - ObjectID: math.MaxUint64, - ItemType: math.MaxUint8, - Offset: math.MaxUint64, -} - -func (key Key) Mm() Key { - switch { - case key.Offset > 0: - key.Offset-- - case key.ItemType > 0: - key.ItemType-- - case key.ObjectID > 0: - key.ObjectID-- - } - return key -} - -func (a Key) Compare(b Key) int { - if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 { - return d - } - if d := containers.NativeCompare(a.ItemType, b.ItemType); d != 0 { - return d - } - return containers.NativeCompare(a.Offset, b.Offset) -} - -var _ containers.Ordered[Key] = Key{} - type Time struct { Sec int64 `bin:"off=0x0, siz=0x8"` // Number of seconds since 1970-01-01T00:00:00Z. NSec uint32 `bin:"off=0x8, siz=0x4"` // Number of nanoseconds since the beginning of the second. -- cgit v1.1-4-g5e80 From 0cc16b8d1da61c0bfb8743c8b68888b0ba73d4bb Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 21:38:56 -0600 Subject: btrfsprim: Add "max" constants for ObjID, ItemType, and offset --- lib/btrfs/Makefile | 7 ++++++- lib/btrfs/btrfsprim/itemtype.go | 7 ++++++- lib/btrfs/btrfsprim/key.go | 2 ++ lib/btrfs/btrfsprim/objid.go | 3 +++ 4 files changed, 17 insertions(+), 2 deletions(-) diff --git a/lib/btrfs/Makefile b/lib/btrfs/Makefile index b98a1b7..2c70363 100644 --- a/lib/btrfs/Makefile +++ b/lib/btrfs/Makefile @@ -74,10 +74,15 @@ btrfsprim/itemtype.go: btrfsitem/items.txt $(MAKEFILE_LIST) echo '// Code generated by Make. DO NOT EDIT.'; \ echo; \ echo 'package $(@D)'; \ - echo 'import "fmt"'; \ + echo 'import ('; \ + echo ' "fmt"'; \ + echo ' "math"'; \ + echo ')'; \ echo 'type ItemType uint8'; \ echo 'const ('; \ sed -E 's,(.*)=([^:]*)(:.*)? (trivial|complex) (.*),\1_KEY ItemType=\2,' $< | uniq; \ + echo; \ + echo 'MAX_KEY ItemType = math.MaxUint8'; \ echo ')'; \ echo 'func (t ItemType) String() string {'; \ echo ' switch t {'; \ diff --git a/lib/btrfs/btrfsprim/itemtype.go b/lib/btrfs/btrfsprim/itemtype.go index f33179a..682fecd 100644 --- a/lib/btrfs/btrfsprim/itemtype.go +++ b/lib/btrfs/btrfsprim/itemtype.go @@ -2,7 +2,10 @@ package btrfsprim -import "fmt" +import ( + "fmt" + "math" +) type ItemType uint8 @@ -39,6 +42,8 @@ const ( UUID_RECEIVED_SUBVOL_KEY ItemType = 252 UUID_SUBVOL_KEY ItemType = 251 XATTR_ITEM_KEY ItemType = 24 + + MAX_KEY ItemType = math.MaxUint8 ) func (t ItemType) String() string { diff --git a/lib/btrfs/btrfsprim/key.go b/lib/btrfs/btrfsprim/key.go index 55f7c05..7a3cc5c 100644 --- a/lib/btrfs/btrfsprim/key.go +++ b/lib/btrfs/btrfsprim/key.go @@ -19,6 +19,8 @@ type Key struct { binstruct.End `bin:"off=0x11"` } +const MaxOffset uint64 = math.MaxUint64 + // mimics print-tree.c:btrfs_print_key() func (key Key) Format(tree ObjID) string { switch tree { diff --git a/lib/btrfs/btrfsprim/objid.go b/lib/btrfs/btrfsprim/objid.go index 1aea030..f364957 100644 --- a/lib/btrfs/btrfsprim/objid.go +++ b/lib/btrfs/btrfsprim/objid.go @@ -6,6 +6,7 @@ package btrfsprim import ( "fmt" + "math" ) type ObjID uint64 @@ -52,6 +53,8 @@ const ( // ??? EMPTY_SUBVOL_DIR_OBJECTID ObjID = 2 + + MAX_OBJECTID ObjID = math.MaxUint64 ) var ( -- cgit v1.1-4-g5e80 From 17833fa13d5a7dcd79ad507fe4abf96b4a4a898b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 21:38:56 -0600 Subject: btrfsprim: Fix Key.Mm(), and add Key.Pp() --- lib/btrfs/btrfsprim/key.go | 18 +++++++++++++ lib/btrfs/btrfsprim/key_test.go | 59 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 77 insertions(+) create mode 100644 lib/btrfs/btrfsprim/key_test.go diff --git a/lib/btrfs/btrfsprim/key.go b/lib/btrfs/btrfsprim/key.go index 7a3cc5c..b07cc8c 100644 --- a/lib/btrfs/btrfsprim/key.go +++ b/lib/btrfs/btrfsprim/key.go @@ -64,8 +64,26 @@ func (key Key) Mm() Key { key.Offset-- case key.ItemType > 0: key.ItemType-- + key.Offset = MaxOffset case key.ObjectID > 0: key.ObjectID-- + key.ItemType = MAX_KEY + key.Offset = MaxOffset + } + return key +} + +func (key Key) Pp() Key { + switch { + case key.Offset < MaxOffset: + key.Offset++ + case key.ItemType < MAX_KEY: + key.ItemType++ + key.Offset = 0 + case key.ObjectID < MAX_OBJECTID: + key.ObjectID++ + key.ItemType = 0 + key.Offset = 0 } return key } diff --git a/lib/btrfs/btrfsprim/key_test.go b/lib/btrfs/btrfsprim/key_test.go new file mode 100644 index 0000000..6274b43 --- /dev/null +++ b/lib/btrfs/btrfsprim/key_test.go @@ -0,0 +1,59 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim + +import ( + "testing" + + "github.com/stretchr/testify/assert" +) + +func k(objID ObjID, typ ItemType, offset uint64) Key { + return Key{ + ObjectID: objID, + ItemType: typ, + Offset: offset, + } +} + +func eq(t *testing.T, act, exp Key) { + t.Helper() + assert.Equal(t, exp, act) +} + +func ppEq(t *testing.T, in, exp Key) { + t.Helper() + eq(t, in.Pp(), exp) + if in != MaxKey { + eq(t, exp.Mm(), in) + } +} + +func mmEq(t *testing.T, in, exp Key) { + t.Helper() + eq(t, in.Mm(), exp) + if in != (Key{}) { + eq(t, exp.Pp(), in) + } +} + +func TestKey(t *testing.T) { + t.Parallel() + + eq(t, MaxKey, k(18446744073709551615, 255, 18446744073709551615)) + + // pp + ppEq(t, k(0, 0, 0), k(0, 0, 1)) + ppEq(t, k(0, 0, 18446744073709551615), k(0, 1, 0)) + ppEq(t, k(0, 255, 0), k(0, 255, 1)) + ppEq(t, k(0, 255, 18446744073709551615), k(1, 0, 0)) + ppEq(t, MaxKey, k(18446744073709551615, 255, 18446744073709551615)) + + // mm + mmEq(t, MaxKey, k(18446744073709551615, 255, 18446744073709551614)) + mmEq(t, k(18446744073709551615, 255, 0), k(18446744073709551615, 254, 18446744073709551615)) + mmEq(t, k(18446744073709551615, 0, 0), k(18446744073709551614, 255, 18446744073709551615)) + mmEq(t, k(0, 0, 0), k(0, 0, 0)) +} -- cgit v1.1-4-g5e80