Merge branch 'lukeshu/errs'

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 &notExistError{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 {