diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-16 08:29:36 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-16 08:29:36 -0600 |
commit | c0f33186aa7a8903c5e7406024f13fad48cd14e3 (patch) | |
tree | c8361c8278b07839be9af2ccee3507d324a7a216 /lib/btrfs | |
parent | c2925f0f8a5d69369b43de0d2d201291fe5ed9d1 (diff) | |
parent | 17833fa13d5a7dcd79ad507fe4abf96b4a4a898b (diff) |
Merge branch 'lukeshu/errs'
Diffstat (limited to 'lib/btrfs')
-rw-r--r-- | lib/btrfs/Makefile | 7 | ||||
-rw-r--r-- | lib/btrfs/btrfsprim/itemtype.go | 7 | ||||
-rw-r--r-- | lib/btrfs/btrfsprim/key.go | 101 | ||||
-rw-r--r-- | lib/btrfs/btrfsprim/key_test.go | 59 | ||||
-rw-r--r-- | lib/btrfs/btrfsprim/misc.go | 71 | ||||
-rw-r--r-- | lib/btrfs/btrfsprim/objid.go | 3 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/btree.go | 98 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/btree_err.go | 32 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/btree_err_test.go | 64 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/btree_forrest.go | 21 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/btree_searchers.go | 209 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/btree_tree.go | 111 | ||||
-rw-r--r-- | lib/btrfs/csums.go | 14 | ||||
-rw-r--r-- | lib/btrfs/io3_btree.go | 8 | ||||
-rw-r--r-- | lib/btrfs/io4_fs.go | 6 |
15 files changed, 605 insertions, 206 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 new file mode 100644 index 0000000..b07cc8c --- /dev/null +++ b/lib/btrfs/btrfsprim/key.go @@ -0,0 +1,101 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// 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"` +} + +const MaxOffset uint64 = math.MaxUint64 + +// 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-- + 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 +} + +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/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 <lukeshu@lukeshu.com> +// +// 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)) +} 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. 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 ( diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go new file mode 100644 index 0000000..4c10ffa --- /dev/null +++ b/lib/btrfs/btrfstree/btree.go @@ -0,0 +1,98 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// 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" +) + +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, + // 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, 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. + // + // 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, search TreeSearcher) ([]Item, error) +} + +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_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 <lukeshu@lukeshu.com> +// +// 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 <lukeshu@lukeshu.com> +// +// 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..0f46d42 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" @@ -21,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) { @@ -67,9 +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 { - return nil, err + if errors.Is(err, ErrNoItem) { + err = ErrNoTree + } + 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 <lukeshu@lukeshu.com> +// +// 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 e75eb0b..df58c0c 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 } @@ -252,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 { @@ -276,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) { @@ -300,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. // @@ -310,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, @@ -477,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 @@ -486,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() @@ -496,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 @@ -522,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] @@ -541,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 @@ -554,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 @@ -568,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 { |