Merge branch 'lukeshu/tree-api-pt0-prep'

5 files changed, 312 insertions, 474 deletions

diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go
index e91fcc1..bc1bac2 100644
--- a/lib/btrfs/btrfstree/btree.go
+++ b/lib/btrfs/btrfstree/btree.go
@@ -22,30 +22,51 @@ type TreeSearcher interface {
 	Search(key btrfsprim.Key, size uint32) int
 }
 
+type TreeWalkHandler struct {
+	BadSuperblock func(error)
+
+	// Callbacks for entire nodes.
+	//
+	// The return value from BadNode is whether to process the
+	// slots in this node or not; if no BadNode function is given,
+	// then it is not processed.
+	Node    func(Path, *Node)
+	BadNode func(Path, *Node, error) bool
+
+	// Callbacks for slots in nodes.
+	//
+	// The return value from KeyPointer is whether to recurse or
+	// not; if no KeyPointer function is given, then it is
+	// recursed.
+	KeyPointer func(Path, KeyPointer) bool
+	Item       func(Path, Item)
+	BadItem    func(Path, Item)
+}
+
 // 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.
+	// 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.
+	// 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()
+	//	000  (read superblock) (maybe cbs.BadSuperblock())
+	//
+	//	001  (read node)
+	//	002  cbs.Node() or cbs.BadNode()
+	//	     if interior:
+	//	       for kp in node.items:
+	//	003a     if cbs.PreKeyPointer == nil || cbs.PreKeyPointer() {
+	//	004b       (recurse)
+	//	     else:
+	//	       for item in node.items:
+	//	003b     cbs.Item() or cbs.BadItem()
 	TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler)
 
 	TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error)
@@ -62,25 +83,6 @@ type TreeOperator interface {
 	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(Path) error
-	Node     func(Path, *Node) error
-	BadNode  func(Path, *Node, error) error
-	PostNode func(Path, *Node) error
-	// Callbacks for items on interior nodes
-	PreKeyPointer  func(Path, KeyPointer) error
-	PostKeyPointer func(Path, KeyPointer) error
-	// Callbacks for items on leaf nodes
-	Item    func(Path, Item) error
-	BadItem func(Path, Item) error
-}
-
 type TreeError struct {
 	Path Path
 	Err  error
diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go
index 0f46d42..8f8e2de 100644
--- a/lib/btrfs/btrfstree/btree_forrest.go
+++ b/lib/btrfs/btrfstree/btree_forrest.go
@@ -5,6 +5,7 @@
 package btrfstree
 
 import (
+	"context"
 	"errors"
 	"fmt"
 
@@ -16,7 +17,7 @@ import (
 // A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by
 // LookupTreeRoot.
 type TreeRoot struct {
-	TreeID     btrfsprim.ObjID
+	ID         btrfsprim.ObjID
 	RootNode   btrfsvol.LogicalAddr
 	Level      uint8
 	Generation btrfsprim.Generation
@@ -24,32 +25,32 @@ type TreeRoot struct {
 
 // LookupTreeRoot is a utility function to help with implementing the
 // 'TreeOperator' interface.
-func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
+func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
 	switch treeID {
 	case btrfsprim.ROOT_TREE_OBJECTID:
 		return &TreeRoot{
-			TreeID:     treeID,
+			ID:         treeID,
 			RootNode:   sb.RootTree,
 			Level:      sb.RootLevel,
 			Generation: sb.Generation, // XXX: same generation as LOG_TREE?
 		}, nil
 	case btrfsprim.CHUNK_TREE_OBJECTID:
 		return &TreeRoot{
-			TreeID:     treeID,
+			ID:         treeID,
 			RootNode:   sb.ChunkTree,
 			Level:      sb.ChunkLevel,
 			Generation: sb.ChunkRootGeneration,
 		}, nil
 	case btrfsprim.TREE_LOG_OBJECTID:
 		return &TreeRoot{
-			TreeID:     treeID,
+			ID:         treeID,
 			RootNode:   sb.LogTree,
 			Level:      sb.LogLevel,
 			Generation: sb.Generation, // XXX: same generation as ROOT_TREE?
 		}, nil
 	case btrfsprim.BLOCK_GROUP_TREE_OBJECTID:
 		return &TreeRoot{
-			TreeID:     treeID,
+			ID:         treeID,
 			RootNode:   sb.BlockGroupRoot,
 			Level:      sb.BlockGroupRootLevel,
 			Generation: sb.BlockGroupRootGeneration,
@@ -65,7 +66,7 @@ func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*Tr
 		switch rootItemBody := rootItem.Body.(type) {
 		case *btrfsitem.Root:
 			return &TreeRoot{
-				TreeID:     treeID,
+				ID:         treeID,
 				RootNode:   rootItemBody.ByteNr,
 				Level:      rootItemBody.Level,
 				Generation: rootItemBody.Generation,
@@ -77,3 +78,70 @@ func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*Tr
 		}
 	}
 }
+
+type TreeOperatorImpl struct {
+	NodeSource
+}
+
+func (fs TreeOperatorImpl) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*RawTree, error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, err
+	}
+	rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID)
+	if err != nil {
+		return nil, err
+	}
+	return &RawTree{
+		Forrest:  fs,
+		TreeRoot: *rootInfo,
+	}, nil
+}
+
+// TreeWalk implements the 'TreeOperator' interface.
+func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
+	tree, err := fs.RawTree(ctx, treeID)
+	if err != nil {
+		errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
+		return
+	}
+	tree.TreeWalk(ctx, cbs)
+}
+
+// TreeLookup implements the 'TreeOperator' interface.
+func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
+	ctx := context.TODO()
+	tree, err := fs.RawTree(ctx, treeID)
+	if err != nil {
+		return Item{}, err
+	}
+	return tree.TreeLookup(ctx, key)
+}
+
+// TreeSearch implements the 'TreeOperator' interface.
+func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) {
+	ctx := context.TODO()
+	tree, err := fs.RawTree(ctx, treeID)
+	if err != nil {
+		return Item{}, err
+	}
+	return tree.TreeSearch(ctx, searcher)
+}
+
+// TreeSearchAll implements the 'TreeOperator' interface.
+func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) {
+	ctx := context.TODO()
+	tree, err := fs.RawTree(ctx, treeID)
+	if err != nil {
+		return nil, err
+	}
+
+	var ret []Item
+	err = tree.TreeSubrange(ctx, 1, searcher, func(item Item) bool {
+		item.Body = item.Body.CloneItem()
+		ret = append(ret, item)
+		return true
+	})
+
+	return ret, err
+}
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index 459f481..a943803 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -6,9 +6,7 @@ package btrfstree
 
 import (
 	"context"
-	"errors"
 	"fmt"
-	iofs "io/fs"
 	"math"
 
 	"github.com/datawire/dlib/derror"
@@ -18,39 +16,24 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
-type TreeOperatorImpl struct {
-	NodeSource
+type RawTree struct {
+	Forrest TreeOperatorImpl
+	TreeRoot
 }
 
-// TreeWalk implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
-	sb, err := fs.Superblock()
-	if err != nil {
-		errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
-	}
-	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
-	if err != nil {
-		errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
-		return
-	}
-	fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs)
-}
-
-// RawTreeWalk is a utility method to help with implementing the
-// 'TreeOperator' interface.
-func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler) {
 	path := Path{{
-		FromTree:         rootInfo.TreeID,
+		FromTree:         tree.ID,
 		FromItemSlot:     -1,
-		ToNodeAddr:       rootInfo.RootNode,
-		ToNodeGeneration: rootInfo.Generation,
-		ToNodeLevel:      rootInfo.Level,
+		ToNodeAddr:       tree.RootNode,
+		ToNodeGeneration: tree.Generation,
+		ToNodeLevel:      tree.Level,
 		ToMaxKey:         btrfsprim.MaxKey,
 	}}
-	fs.treeWalk(ctx, path, errHandle, cbs)
+	tree.walk(ctx, path, cbs)
 }
 
-func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (tree *RawTree) walk(ctx context.Context, path Path, cbs TreeWalkHandler) {
 	if ctx.Err() != nil {
 		return
 	}
@@ -58,442 +41,229 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle fu
 		return
 	}
 
-	if cbs.PreNode != nil {
-		if err := cbs.PreNode(path); err != nil {
-			if errors.Is(err, iofs.SkipDir) {
-				return
-			}
-			errHandle(&TreeError{Path: path, Err: err})
+	// 001
+	node, err := tree.Forrest.ReadNode(path)
+	defer node.Free()
+	if ctx.Err() != nil {
+		return
+	}
+
+	// 002
+	switch {
+	case err == nil:
+		if cbs.Node != nil {
+			cbs.Node(path, node)
 		}
-		if ctx.Err() != nil {
+	default:
+		process := cbs.BadNode != nil && cbs.BadNode(path, node, err)
+		if !process {
 			return
 		}
 	}
-	node, err := fs.ReadNode(path)
-	defer node.Free()
 	if ctx.Err() != nil {
 		return
 	}
-	if err != nil && node != nil && cbs.BadNode != nil {
-		// opportunity to fix the node
-		err = cbs.BadNode(path, node, err)
-		if errors.Is(err, iofs.SkipDir) {
+
+	// 003-004
+	if node == nil {
+		return
+	}
+	// branch a (interior)
+	for i, item := range node.BodyInterior {
+		toMaxKey := path.Node(-1).ToMaxKey
+		if i+1 < len(node.BodyInterior) {
+			toMaxKey = node.BodyInterior[i+1].Key.Mm()
+		}
+		itemPath := append(path, PathElem{
+			FromTree:         node.Head.Owner,
+			FromItemSlot:     i,
+			ToNodeAddr:       item.BlockPtr,
+			ToNodeGeneration: item.Generation,
+			ToNodeLevel:      node.Head.Level - 1,
+			ToKey:            item.Key,
+			ToMaxKey:         toMaxKey,
+		})
+		// 003a
+		recurse := cbs.KeyPointer == nil || cbs.KeyPointer(itemPath, item)
+		if ctx.Err() != nil {
 			return
 		}
-	}
-	if err != nil {
-		errHandle(&TreeError{Path: path, Err: err})
-	} else if cbs.Node != nil {
-		if err := cbs.Node(path, node); err != nil {
-			if errors.Is(err, iofs.SkipDir) {
+		// 004a
+		if recurse {
+			tree.walk(ctx, itemPath, cbs)
+			if ctx.Err() != nil {
 				return
 			}
-			errHandle(&TreeError{Path: path, Err: err})
 		}
 	}
-	if ctx.Err() != nil {
+	// branch b (leaf)
+	if cbs.Item == nil && cbs.BadItem == nil {
 		return
 	}
-	if node != nil {
-		for i, item := range node.BodyInterior {
-			toMaxKey := path.Node(-1).ToMaxKey
-			if i+1 < len(node.BodyInterior) {
-				toMaxKey = node.BodyInterior[i+1].Key.Mm()
-			}
-			itemPath := append(path, PathElem{
-				FromTree:         node.Head.Owner,
-				FromItemSlot:     i,
-				ToNodeAddr:       item.BlockPtr,
-				ToNodeGeneration: item.Generation,
-				ToNodeLevel:      node.Head.Level - 1,
-				ToKey:            item.Key,
-				ToMaxKey:         toMaxKey,
-			})
-			if cbs.PreKeyPointer != nil {
-				if err := cbs.PreKeyPointer(itemPath, item); err != nil {
-					errHandle(&TreeError{Path: itemPath, Err: err})
-				}
-				if ctx.Err() != nil {
-					return
-				}
+	for i, item := range node.BodyLeaf {
+		itemPath := append(path, PathElem{
+			FromTree:     node.Head.Owner,
+			FromItemSlot: i,
+			ToKey:        item.Key,
+			ToMaxKey:     item.Key,
+		})
+		// 003b
+		switch item.Body.(type) {
+		case *btrfsitem.Error:
+			if cbs.BadItem != nil {
+				cbs.BadItem(itemPath, item)
 			}
-			fs.treeWalk(ctx, itemPath, errHandle, cbs)
-			if cbs.PostKeyPointer != nil {
-				if err := cbs.PostKeyPointer(itemPath, item); err != nil {
-					errHandle(&TreeError{Path: itemPath, Err: err})
-				}
-				if ctx.Err() != nil {
-					return
-				}
+		default:
+			if cbs.Item != nil {
+				cbs.Item(itemPath, item)
 			}
 		}
-		for i, item := range node.BodyLeaf {
-			itemPath := append(path, PathElem{
-				FromTree:     node.Head.Owner,
-				FromItemSlot: i,
-				ToKey:        item.Key,
-				ToMaxKey:     item.Key,
-			})
-			if errBody, isErr := item.Body.(*btrfsitem.Error); isErr {
-				if cbs.BadItem == nil {
-					errHandle(&TreeError{Path: itemPath, Err: errBody.Err})
-				} else {
-					if err := cbs.BadItem(itemPath, item); err != nil {
-						errHandle(&TreeError{Path: itemPath, Err: err})
-					}
-					if ctx.Err() != nil {
-						return
-					}
-				}
-			} else {
-				if cbs.Item != nil {
-					if err := cbs.Item(itemPath, item); err != nil {
-						errHandle(&TreeError{Path: itemPath, Err: err})
-					}
-					if ctx.Err() != nil {
-						return
-					}
-				}
-			}
+		if ctx.Err() != nil {
+			return
 		}
 	}
-	if cbs.PostNode != nil {
-		if err := cbs.PostNode(path, node); err != nil {
-			if errors.Is(err, iofs.SkipDir) {
-				return
-			}
-			errHandle(&TreeError{Path: path, Err: err})
-		}
+}
+
+// searchKP takes a sorted list of KeyPointers, and finds the
+//
+//   - left-most member for which `searchFn(member.Key, math.MaxUint32) == 0`; or else the
+//   - right-most member for which `searchFn(member.Key, math.MaxUint32) == 1`; or else
+//   - zero
+//
+// This assumes that `haystack` is sorted such that the return values from searchFn look like:
+//
+//   - + + 0 0 0 - - -
+func searchKP(haystack []KeyPointer, searchFn func(key btrfsprim.Key, size uint32) int) (_ KeyPointer, ok bool) {
+	if leftZero, ok := slices.SearchLowest(haystack, func(kp KeyPointer) int {
+		return searchFn(kp.Key, math.MaxUint32)
+	}); ok {
+		return haystack[leftZero], true
+	}
+	if rightPos, ok := slices.SearchHighest(haystack, func(kp KeyPointer) int {
+		return slices.Min(searchFn(kp.Key, math.MaxUint32), 0)
+	}); ok {
+		return haystack[rightPos], true
 	}
+	return KeyPointer{}, false
 }
 
-func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) {
-	path := Path{{
-		FromTree:         treeRoot.TreeID,
-		FromItemSlot:     -1,
-		ToNodeAddr:       treeRoot.RootNode,
-		ToNodeGeneration: treeRoot.Generation,
-		ToNodeLevel:      treeRoot.Level,
-		ToMaxKey:         btrfsprim.MaxKey,
-	}}
-	for {
-		if path.Node(-1).ToNodeAddr == 0 {
-			return nil, nil, ErrNoItem
-		}
-		node, err := fs.ReadNode(path)
-		if err != nil {
-			node.Free()
-			return nil, nil, err
+func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) {
+	ctx, cancel := context.WithCancel(ctx)
+	var retErr error
+	setErr := func(err error) {
+		if retErr == nil && err != nil {
+			retErr = fmt.Errorf("item with %s: %w", searcher, err)
 		}
+		cancel()
+	}
 
-		switch {
-		case node.Head.Level > 0:
-			// interior node
-
-			// Search for the right-most node.BodyInterior item for which
-			// `fn(item.Key) >= 0`.
-			//
-			//    + + + + 0 - - - -
-			//
-			// There may or may not be a value that returns '0'.
-			//
-			// i.e. find the highest value that isn't too high.
-			lastGood, ok := slices.SearchHighest(node.BodyInterior, func(kp KeyPointer) int {
-				return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low"
-			})
-			if !ok {
-				node.Free()
-				return nil, nil, ErrNoItem
-			}
-			toMaxKey := path.Node(-1).ToMaxKey
-			if lastGood+1 < len(node.BodyInterior) {
-				toMaxKey = node.BodyInterior[lastGood+1].Key.Mm()
+	var ret Item
+	var selKP KeyPointer
+	tree.TreeWalk(ctx, TreeWalkHandler{
+		Node: func(_ Path, node *Node) {
+			if node.Head.Level > 0 { // interior node
+				kp, ok := searchKP(node.BodyInterior, searcher.Search)
+				if !ok {
+					setErr(ErrNoItem)
+					return
+				}
+				selKP = kp
+			} else { // leaf node
+				slot, ok := slices.Search(node.BodyLeaf, func(item Item) int {
+					return searcher.Search(item.Key, item.BodySize)
+				})
+				if !ok {
+					setErr(ErrNoItem)
+					return
+				}
+				ret = node.BodyLeaf[slot]
+				ret.Body = ret.Body.CloneItem()
 			}
-			path = append(path, PathElem{
-				FromTree:         node.Head.Owner,
-				FromItemSlot:     lastGood,
-				ToNodeAddr:       node.BodyInterior[lastGood].BlockPtr,
-				ToNodeGeneration: node.BodyInterior[lastGood].Generation,
-				ToNodeLevel:      node.Head.Level - 1,
-				ToKey:            node.BodyInterior[lastGood].Key,
-				ToMaxKey:         toMaxKey,
-			})
-			node.Free()
-		default:
-			// leaf node
+		},
+		BadNode: func(path Path, _ *Node, err error) bool {
+			setErr(fmt.Errorf("%v: %w", path, err))
+			return false
+		},
+		KeyPointer: func(_ Path, kp KeyPointer) bool {
+			return kp == selKP
+		},
+	})
 
-			// Search for a member of node.BodyLeaf for which
-			// `fn(item.Head.Key) == 0`.
-			//
-			//    + + + + 0 - - - -
-			//
-			// 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.
-			//
-			// Implement this search as a binary search.
-			slot, ok := slices.Search(node.BodyLeaf, func(item Item) int {
-				return fn(item.Key, item.BodySize)
-			})
-			if !ok {
-				node.Free()
-				return nil, nil, ErrNoItem
-			}
-			path = append(path, PathElem{
-				FromTree:     node.Head.Owner,
-				FromItemSlot: slot,
-				ToKey:        node.BodyLeaf[slot].Key,
-				ToMaxKey:     node.BodyLeaf[slot].Key,
-			})
-			return path, node, nil
-		}
-	}
+	return ret, retErr
 }
 
-func (fs TreeOperatorImpl) prev(path Path, node *Node) (Path, *Node, error) {
-	var err error
-	path = path.DeepCopy()
-
-	// go up
-	for path.Node(-1).FromItemSlot < 1 {
-		path = path.Parent()
-		if len(path) == 0 {
-			return nil, nil, nil
-		}
-	}
-	// go left
-	path.Node(-1).FromItemSlot--
-	if path.Node(-1).ToNodeAddr != 0 {
-		if node.Head.Addr != path.Node(-2).ToNodeAddr {
-			node.Free()
-			node, err = fs.ReadNode(path.Parent())
-			if err != nil {
-				node.Free()
-				return nil, nil, err
-			}
-			path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
-		}
-	}
-	// go down
-	for path.Node(-1).ToNodeAddr != 0 {
-		if node.Head.Addr != path.Node(-1).ToNodeAddr {
-			node.Free()
-			node, err = fs.ReadNode(path)
-			if err != nil {
-				node.Free()
-				return nil, nil, err
-			}
-		}
-		if node.Head.Level > 0 {
-			path = append(path, PathElem{
-				FromTree:         node.Head.Owner,
-				FromItemSlot:     len(node.BodyInterior) - 1,
-				ToNodeAddr:       node.BodyInterior[len(node.BodyInterior)-1].BlockPtr,
-				ToNodeGeneration: node.BodyInterior[len(node.BodyInterior)-1].Generation,
-				ToNodeLevel:      node.Head.Level - 1,
-				ToKey:            node.BodyInterior[len(node.BodyInterior)-1].Key,
-				ToMaxKey:         path.Node(-1).ToMaxKey,
-			})
-		} else {
-			path = append(path, PathElem{
-				FromTree:     node.Head.Owner,
-				FromItemSlot: len(node.BodyLeaf) - 1,
-				ToKey:        node.BodyLeaf[len(node.BodyLeaf)-1].Key,
-				ToMaxKey:     node.BodyLeaf[len(node.BodyLeaf)-1].Key,
-			})
-		}
-	}
-	// return
-	if node.Head.Addr != path.Node(-2).ToNodeAddr {
-		node.Free()
-		node, err = fs.ReadNode(path.Parent())
-		if err != nil {
-			node.Free()
-			return nil, nil, err
-		}
-	}
-	return path, node, nil
+func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) {
+	return tree.TreeSearch(ctx, SearchExactKey(key))
 }
 
-func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) {
-	var err error
-	path = path.DeepCopy()
+func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSearcher, handleFn func(Item) bool) error {
+	ctx, cancel := context.WithCancel(ctx)
+	var errs derror.MultiError
 
-	// go up
-	if node.Head.Addr != path.Node(-2).ToNodeAddr {
-		node.Free()
-		node, err = fs.ReadNode(path.Parent())
-		if err != nil {
-			node.Free()
-			return nil, nil, err
-		}
-		path.Node(-2).ToNodeLevel = node.Head.Level
-	}
-	for path.Node(-1).FromItemSlot+1 >= int(node.Head.NumItems) {
-		path = path.Parent()
-		if len(path) == 1 {
-			return nil, nil, nil
-		}
-		if node.Head.Addr != path.Node(-2).ToNodeAddr {
-			node.Free()
-			node, err = fs.ReadNode(path.Parent())
-			if err != nil {
-				node.Free()
-				return nil, nil, err
+	var minKP btrfsprim.Key
+	var cnt int
+	tree.TreeWalk(ctx, TreeWalkHandler{
+		Node: func(_ Path, node *Node) {
+			// Only bother for interior nodes.
+			if node.Head.Level == 0 {
+				return
 			}
-			path.Node(-2).ToNodeLevel = node.Head.Level
-		}
-	}
-	// go right
-	path.Node(-1).FromItemSlot++
-	if path.Node(-1).ToNodeAddr != 0 {
-		if node.Head.Addr != path.Node(-2).ToNodeAddr {
-			node.Free()
-			node, err = fs.ReadNode(path.Parent())
-			if err != nil {
-				node.Free()
-				return nil, nil, err
+			kp, ok := searchKP(node.BodyInterior, searcher.Search)
+			if !ok {
+				cancel()
+				return
 			}
-			path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
-		}
-	}
-	// go down
-	for path.Node(-1).ToNodeAddr != 0 {
-		if node.Head.Addr != path.Node(-1).ToNodeAddr {
-			node.Free()
-			node, err = fs.ReadNode(path)
-			if err != nil {
-				node.Free()
-				return nil, nil, err
+			minKP = kp.Key
+		},
+		BadNode: func(path Path, _ *Node, err error) bool {
+			errs = append(errs, fmt.Errorf("%v: %w", path, err))
+			return false
+		},
+		KeyPointer: func(_ Path, kp KeyPointer) bool {
+			if searcher.Search(kp.Key, math.MaxUint32) < 0 {
+				cancel()
+				return false
 			}
-			path.Node(-1).ToNodeLevel = node.Head.Level
-		}
-		if node.Head.Level > 0 {
-			toMaxKey := path.Node(-1).ToMaxKey
-			if len(node.BodyInterior) > 1 {
-				toMaxKey = node.BodyInterior[1].Key.Mm()
+			if kp.Key.Compare(minKP) > 0 {
+				return false
 			}
-			path = append(path, PathElem{
-				FromTree:         node.Head.Owner,
-				FromItemSlot:     0,
-				ToNodeAddr:       node.BodyInterior[0].BlockPtr,
-				ToNodeGeneration: node.BodyInterior[0].Generation,
-				ToNodeLevel:      node.Head.Level - 1,
-				ToKey:            node.BodyInterior[0].Key,
-				ToMaxKey:         toMaxKey,
-			})
-		} else {
-			path = append(path, PathElem{
-				FromTree:     node.Head.Owner,
-				FromItemSlot: 0,
-				ToKey:        node.BodyInterior[0].Key,
-				ToMaxKey:     node.BodyInterior[0].Key,
-			})
-		}
-	}
-	// return
-	if node.Head.Addr != path.Node(-2).ToNodeAddr {
-		node.Free()
-		node, err = fs.ReadNode(path.Parent())
-		if err != nil {
-			node.Free()
-			return nil, nil, err
-		}
-	}
-	return path, node, nil
-}
-
-// TreeSearch implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) {
-	sb, err := fs.Superblock()
-	if err != nil {
-		return Item{}, err
-	}
-	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
-	if err != nil {
-		return Item{}, err
-	}
-	path, node, err := fs.treeSearch(*rootInfo, searcher.Search)
-	if err != nil {
-		return Item{}, fmt.Errorf("item with %s: %w", searcher, err)
-	}
-	item := node.BodyLeaf[path.Node(-1).FromItemSlot]
-	item.Body = item.Body.CloneItem()
-	node.Free()
-	return item, nil
-}
-
-// TreeLookup implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
-	return fs.TreeSearch(treeID, SearchExactKey(key))
-}
-
-// TreeSearchAll implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) {
-	sb, err := fs.Superblock()
-	if err != nil {
-		return nil, err
-	}
-	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
-	if err != nil {
-		return nil, err
-	}
-	middlePath, middleNode, err := fs.treeSearch(*rootInfo, searcher.Search)
-	if err != nil {
-		return nil, fmt.Errorf("items with %s: %w", searcher, err)
-	}
-	middleItem := middleNode.BodyLeaf[middlePath.Node(-1).FromItemSlot]
+			return true
+		},
+		Item: func(_ Path, item Item) {
+			d := searcher.Search(item.Key, item.BodySize)
+			switch {
+			case d > 1:
+				// do nothing
+			case d == 0:
+				cnt++
+				if !handleFn(item) {
+					cancel()
+				}
+			case d < 1:
+				cancel()
+			}
+		},
+		BadItem: func(_ Path, item Item) {
+			d := searcher.Search(item.Key, item.BodySize)
+			switch {
+			case d > 1:
+				// do nothing
+			case d == 0:
+				cnt++
+				if !handleFn(item) {
+					cancel()
+				}
+			case d < 1:
+				cancel()
+			}
+		},
+	})
 
-	ret := []Item{middleItem}
-	var errs derror.MultiError
-	prevPath, prevNode := middlePath, middleNode
-	for {
-		prevPath, prevNode, err = fs.prev(prevPath, prevNode)
-		if err != nil {
-			errs = append(errs, err)
-			break
-		}
-		if len(prevPath) == 0 {
-			break
-		}
-		prevItem := prevNode.BodyLeaf[prevPath.Node(-1).FromItemSlot]
-		if searcher.Search(prevItem.Key, prevItem.BodySize) != 0 {
-			break
-		}
-		item := prevItem
-		item.Body = item.Body.CloneItem()
-		ret = append(ret, item)
-	}
-	slices.Reverse(ret)
-	if prevNode.Head.Addr != middlePath.Node(-1).ToNodeAddr {
-		prevNode.Free()
-		middleNode, err = fs.ReadNode(middlePath)
-		if err != nil {
-			middleNode.Free()
-			return nil, fmt.Errorf("items with %s: %w", searcher, err)
-		}
-	}
-	nextPath, nextNode := middlePath, middleNode
-	for {
-		nextPath, nextNode, err = fs.next(nextPath, nextNode)
-		if err != nil {
-			errs = append(errs, err)
-			break
-		}
-		if len(nextPath) == 0 {
-			break
-		}
-		nextItem := nextNode.BodyLeaf[nextPath.Node(-1).FromItemSlot]
-		if searcher.Search(nextItem.Key, nextItem.BodySize) != 0 {
-			break
-		}
-		item := nextItem
-		item.Body = item.Body.CloneItem()
-		ret = append(ret, item)
+	if cnt < min {
+		errs = append(errs, ErrNoItem)
 	}
-	nextNode.Free()
-	if errs != nil {
-		err = errs
+	if len(errs) > 0 {
+		return fmt.Errorf("items with %s: %w", searcher, errs)
 	}
-	return ret, err
+	return nil
 }
diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go
index d05d51f..9f4e53f 100644
--- a/lib/btrfs/io2_lv.go
+++ b/lib/btrfs/io2_lv.go
@@ -168,15 +168,15 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error {
 			errs = append(errs, err)
 		},
 		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.Path, item btrfstree.Item) error {
+			Item: func(_ btrfstree.Path, item btrfstree.Item) {
 				if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY {
-					return nil
+					return
 				}
 				switch itemBody := item.Body.(type) {
 				case *btrfsitem.Chunk:
 					for _, mapping := range itemBody.Mappings(item.Key) {
 						if err := fs.LV.AddMapping(mapping); err != nil {
-							return err
+							errs = append(errs, err)
 						}
 					}
 				case *btrfsitem.Error:
@@ -187,7 +187,6 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error {
 					// updated.
 					panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody))
 				}
-				return nil
 			},
 		},
 	)
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 80ab10f..6df88f5 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -37,15 +37,14 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) {
 			// do nothing
 		},
 		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.Path, item btrfstree.Item) error {
+			Item: func(_ btrfstree.Path, item btrfstree.Item) {
 				itemBody, ok := item.Body.(*btrfsitem.Root)
 				if !ok {
-					return nil
+					return
 				}
 				fs.cacheObjID2UUID[item.Key.ObjectID] = itemBody.UUID
 				fs.cacheTreeParent[item.Key.ObjectID] = itemBody.ParentUUID
 				fs.cacheUUID2ObjID[itemBody.UUID] = item.Key.ObjectID
-				return nil
 			},
 		},
 	)