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

12 files changed, 435 insertions, 575 deletions

diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
index 60303e9..7703078 100644
--- a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
+++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
@@ -53,9 +53,9 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) {
 			dlog.Error(ctx, err)
 		},
 		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.Path, item btrfstree.Item) error {
+			Item: func(_ btrfstree.Path, item btrfstree.Item) {
 				if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY {
-					return nil
+					return
 				}
 				treeName, ok := map[btrfsprim.ObjID]string{
 					btrfsprim.ROOT_TREE_OBJECTID:        "root",
@@ -82,7 +82,6 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) {
 				}
 				textui.Fprintf(out, "%v tree key %v \n", treeName, item.Key.Format(btrfsprim.ROOT_TREE_OBJECTID))
 				printTree(ctx, out, fs, item.Key.ObjectID)
-				return nil
 			},
 		},
 	)
@@ -99,20 +98,19 @@ var nodeHeaderSize = binstruct.StaticSize(btrfstree.NodeHeader{})
 func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfsprim.ObjID) {
 	var itemOffset uint32
 	handlers := btrfstree.TreeWalkHandler{
-		Node: func(path btrfstree.Path, node *btrfstree.Node) error {
+		Node: func(path btrfstree.Path, node *btrfstree.Node) {
 			printHeaderInfo(out, node)
 			itemOffset = node.Size - uint32(nodeHeaderSize)
-			return nil
 		},
-		PreKeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) error {
+		KeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) bool {
 			treeID := path[0].FromTree
 			textui.Fprintf(out, "\tkey %v block %v gen %v\n",
 				item.Key.Format(treeID),
 				item.BlockPtr,
 				item.Generation)
-			return nil
+			return true
 		},
-		Item: func(path btrfstree.Path, item btrfstree.Item) error {
+		Item: func(path btrfstree.Path, item btrfstree.Item) {
 			treeID := path[0].FromTree
 			i := path.Node(-1).FromItemSlot
 			bs, _ := binstruct.Marshal(item.Body)
@@ -359,7 +357,6 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri
 			default:
 				textui.Fprintf(out, "\t\t(error) unhandled item type: %T\n", body)
 			}
-			return nil
 		},
 	}
 	handlers.BadItem = handlers.Item
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
index ada9f6f..3339270 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
@@ -59,7 +59,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA
 	ret := ScanDevicesResult{
 		Superblock: *sb,
 
-		Graph: btrfsutil.NewGraph(*sb),
+		Graph: btrfsutil.NewGraph(ctx, *sb),
 
 		Flags: make(map[btrfsutil.ItemPtr]FlagsAndErr),
 		Names: make(map[btrfsutil.ItemPtr][]byte),
diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go
index cad1a37..1449a21 100644
--- a/cmd/btrfs-rec/inspect_lstrees.go
+++ b/cmd/btrfs-rec/inspect_lstrees.go
@@ -75,19 +75,21 @@ func init() {
 					treeErrCnt++
 				},
 				TreeWalkHandler: btrfstree.TreeWalkHandler{
-					Node: func(path btrfstree.Path, node *btrfstree.Node) error {
+					Node: func(path btrfstree.Path, node *btrfstree.Node) {
 						visitedNodes.Insert(path.Node(-1).ToNodeAddr)
-						return nil
 					},
-					Item: func(_ btrfstree.Path, item btrfstree.Item) error {
+					BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
+						visitedNodes.Insert(path.Node(-1).ToNodeAddr)
+						treeErrCnt++
+						return false
+					},
+					Item: func(_ btrfstree.Path, item btrfstree.Item) {
 						typ := item.Key.ItemType
 						treeItemCnt[typ]++
-						return nil
 					},
-					BadItem: func(_ btrfstree.Path, item btrfstree.Item) error {
+					BadItem: func(_ btrfstree.Path, item btrfstree.Item) {
 						typ := item.Key.ItemType
 						treeItemCnt[typ]++
-						return nil
 					},
 				},
 				PostTree: func(_ string, _ btrfsprim.ObjID) {
diff --git a/cmd/btrfs-rec/inspect_spewitems.go b/cmd/btrfs-rec/inspect_spewitems.go
index b83e989..c3a1e6b 100644
--- a/cmd/btrfs-rec/inspect_spewitems.go
+++ b/cmd/btrfs-rec/inspect_spewitems.go
@@ -34,17 +34,15 @@ func init() {
 					dlog.Error(ctx, err)
 				},
 				TreeWalkHandler: btrfstree.TreeWalkHandler{
-					Item: func(path btrfstree.Path, item btrfstree.Item) error {
+					Item: func(path btrfstree.Path, item btrfstree.Item) {
 						textui.Fprintf(os.Stdout, "%s = ", path)
 						spew.Dump(item)
 						_, _ = os.Stdout.WriteString("\n")
-						return nil
 					},
-					BadItem: func(path btrfstree.Path, item btrfstree.Item) error {
+					BadItem: func(path btrfstree.Path, item btrfstree.Item) {
 						textui.Fprintf(os.Stdout, "%s = ", path)
 						spew.Dump(item)
 						_, _ = os.Stdout.WriteString("\n")
-						return nil
 					},
 				},
 			})
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
 			},
 		},
 	)
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 35848de..39e1cf2 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -111,8 +111,8 @@ func (g Graph) insertEdge(ptr *GraphEdge) {
 	g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr)
 }
 
-func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
-	treeInfo, err := btrfstree.LookupTreeRoot(nil, sb, treeID)
+func (g Graph) insertTreeRoot(ctx context.Context, sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
+	treeInfo, err := btrfstree.LookupTreeRoot(ctx, nil, sb, treeID)
 	if err != nil {
 		// This shouldn't ever happen for treeIDs that are
 		// mentioned directly in the superblock; which are the
@@ -131,7 +131,7 @@ func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
 	})
 }
 
-func NewGraph(sb btrfstree.Superblock) Graph {
+func NewGraph(ctx context.Context, sb btrfstree.Superblock) Graph {
 	g := Graph{
 		Nodes:     make(map[btrfsvol.LogicalAddr]GraphNode),
 		BadNodes:  make(map[btrfsvol.LogicalAddr]error),
@@ -141,10 +141,10 @@ func NewGraph(sb btrfstree.Superblock) Graph {
 
 	// These 4 trees are mentioned directly in the superblock, so
 	// they are always seen.
-	g.insertTreeRoot(sb, btrfsprim.ROOT_TREE_OBJECTID)
-	g.insertTreeRoot(sb, btrfsprim.CHUNK_TREE_OBJECTID)
-	g.insertTreeRoot(sb, btrfsprim.TREE_LOG_OBJECTID)
-	g.insertTreeRoot(sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
+	g.insertTreeRoot(ctx, sb, btrfsprim.ROOT_TREE_OBJECTID)
+	g.insertTreeRoot(ctx, sb, btrfsprim.CHUNK_TREE_OBJECTID)
+	g.insertTreeRoot(ctx, sb, btrfsprim.TREE_LOG_OBJECTID)
+	g.insertTreeRoot(ctx, sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
 
 	return g
 }
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index abe3329..bb5ab59 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -13,6 +13,7 @@ import (
 	"github.com/datawire/dlib/dlog"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
@@ -20,6 +21,10 @@ import (
 )
 
 type oldRebuiltTree struct {
+	forrest *OldRebuiltForrest
+
+	ID btrfsprim.ObjID
+
 	RootErr error
 	Items   *containers.RBTree[oldRebuiltTreeValue]
 	Errors  *containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]
@@ -114,7 +119,9 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre
 	}
 }
 
-func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree {
+// RebuiltTree returns a handle for an individual tree.  An error is
+// indicated by the ret.RootErr member.
+func (bt *OldRebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) oldRebuiltTree {
 	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
 		bt.rootTreeMu.Lock()
 		defer bt.rootTreeMu.Unlock()
@@ -133,9 +140,11 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 	}
 
 	cacheEntry := newOldRebuiltTree()
-	dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
-	bt.rawTreeWalk(treeID, &cacheEntry)
-	dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
+	cacheEntry.forrest = bt
+	cacheEntry.ID = treeID
+	dlog.Infof(ctx, "indexing tree %v...", treeID)
+	bt.rawTreeWalk(ctx, treeID, &cacheEntry)
+	dlog.Infof(ctx, "... done indexing tree %v", treeID)
 
 	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
 		bt.rootTree = &cacheEntry
@@ -147,47 +156,33 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 
 func discardOK[T any](x T, _ bool) T { return x }
 
-func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
+func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
 	sb, err := bt.inner.Superblock()
 	if err != nil {
 		cacheEntry.RootErr = err
 		return
 	}
-	root, err := btrfstree.LookupTreeRoot(bt, *sb, treeID)
+	root, err := btrfstree.LookupTreeRoot(ctx, bt, *sb, treeID)
 	if err != nil {
 		cacheEntry.RootErr = err
 		return
 	}
-
-	errHandle := func(err *btrfstree.TreeError) {
-		if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
-			// This is a panic because on the filesystems I'm working with it more likely
-			// indicates a bug in my item parser than a problem with the filesystem.
-			panic(fmt.Errorf("TODO: error parsing item: %w", err))
-		}
-		cacheEntry.Errors.Insert(oldRebuiltTreeError{
-			Min: err.Path.Node(-1).ToKey,
-			Max: err.Path.Node(-1).ToMaxKey,
-			Err: err.Err,
-		})
+	tree := &btrfstree.RawTree{
+		Forrest:  btrfstree.TreeOperatorImpl{NodeSource: bt.inner},
+		TreeRoot: *root,
 	}
 
 	var curNode nodeInfo
 	cbs := btrfstree.TreeWalkHandler{
-		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) error {
-			if node != nil {
-				curNode = nodeInfo{
-					LAddr:      path.Node(-1).ToNodeAddr,
-					Level:      node.Head.Level,
-					Generation: node.Head.Generation,
-					Owner:      node.Head.Owner,
-					MinItem:    discardOK(node.MinItem()),
-					MaxItem:    discardOK(node.MaxItem()),
-				}
-			}
-			return err
+		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
+			cacheEntry.Errors.Insert(oldRebuiltTreeError{
+				Min: path.Node(-1).ToKey,
+				Max: path.Node(-1).ToMaxKey,
+				Err: err,
+			})
+			return false
 		},
-		Node: func(path btrfstree.Path, node *btrfstree.Node) error {
+		Node: func(path btrfstree.Path, node *btrfstree.Node) {
 			curNode = nodeInfo{
 				LAddr:      path.Node(-1).ToNodeAddr,
 				Level:      node.Head.Level,
@@ -196,14 +191,13 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old
 				MinItem:    discardOK(node.MinItem()),
 				MaxItem:    discardOK(node.MaxItem()),
 			}
-			return nil
 		},
-		Item: func(path btrfstree.Path, item btrfstree.Item) error {
+		Item: func(path btrfstree.Path, item btrfstree.Item) {
 			if cacheEntry.Items.Search(func(v oldRebuiltTreeValue) int { return item.Key.Compare(v.Key) }) != nil {
 				// This is a panic because I'm not really sure what the best way to
 				// handle this is, and so if this happens I want the program to crash
 				// and force me to figure out how to handle it.
-				panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
+				panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, treeID))
 			}
 			cacheEntry.Items.Insert(oldRebuiltTreeValue{
 				Key:      item.Key,
@@ -212,15 +206,11 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old
 				Node: curNode,
 				Slot: path.Node(-1).FromItemSlot,
 			})
-			return nil
 		},
 	}
+	cbs.BadItem = cbs.Item
 
-	btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, *root, errHandle, cbs)
-}
-
-func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
-	return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key))
+	tree.TreeWalk(ctx, cbs)
 }
 
 func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
@@ -267,8 +257,22 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
 	return node
 }
 
+// TreeLookup implements btrfstree.TreeOperator.
+func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
+	return bt.RebuiltTree(bt.ctx, treeID).treeLookup(bt.ctx, key)
+}
+
+func (tree oldRebuiltTree) treeLookup(ctx context.Context, key btrfsprim.Key) (btrfstree.Item, error) {
+	return tree.treeSearch(ctx, btrfstree.SearchExactKey(key))
+}
+
+// TreeSearch implements btrfstree.TreeOperator.
 func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
-	tree := bt.RebuiltTree(treeID)
+	return bt.RebuiltTree(bt.ctx, treeID).treeSearch(bt.ctx, searcher)
+}
+
+// TreeSearch implements btrfstree.Tree.
+func (tree oldRebuiltTree) treeSearch(_ context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
 	if tree.RootErr != nil {
 		return btrfstree.Item{}, tree.RootErr
 	}
@@ -280,7 +284,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr
 		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
 	}
 
-	node := bt.readNode(indexItem.Value.Node)
+	node := tree.forrest.readNode(indexItem.Value.Node)
 	defer node.Free()
 
 	item := node.BodyLeaf[indexItem.Value.Slot]
@@ -291,46 +295,55 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr
 	return item, nil
 }
 
+// TreeSearchAll implements btrfstree.TreeOperator.
 func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) {
-	tree := bt.RebuiltTree(treeID)
+	tree := bt.RebuiltTree(bt.ctx, treeID)
 	if tree.RootErr != nil {
 		return nil, tree.RootErr
 	}
 
-	var indexItems []oldRebuiltTreeValue
+	var ret []btrfstree.Item
+	err := tree.treeSubrange(bt.ctx, 1, searcher, func(item btrfstree.Item) bool {
+		item.Body = item.Body.CloneItem()
+		ret = append(ret, item)
+		return true
+	})
+
+	return ret, err
+}
+
+func (tree oldRebuiltTree) treeSubrange(_ context.Context, min int, searcher btrfstree.TreeSearcher, handleFn func(btrfstree.Item) bool) error {
+	var node *btrfstree.Node
+	var cnt int
 	tree.Items.Subrange(
 		func(indexItem oldRebuiltTreeValue) int {
 			return searcher.Search(indexItem.Key, indexItem.ItemSize)
 		},
-		func(node *containers.RBNode[oldRebuiltTreeValue]) bool {
-			indexItems = append(indexItems, node.Value)
-			return true
+		func(rbNode *containers.RBNode[oldRebuiltTreeValue]) bool {
+			cnt++
+			if node == nil || node.Head.Addr != rbNode.Value.Node.LAddr {
+				node.Free()
+				node = tree.forrest.readNode(rbNode.Value.Node)
+			}
+			return handleFn(node.BodyLeaf[rbNode.Value.Slot])
 		})
-	if len(indexItems) == 0 {
-		return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
-	}
-
-	ret := make([]btrfstree.Item, len(indexItems))
-	var node *btrfstree.Node
-	for i, indexItem := range indexItems {
-		if node == nil || node.Head.Addr != indexItem.Node.LAddr {
-			node.Free()
-			node = bt.readNode(indexItem.Node)
-		}
-		ret[i] = node.BodyLeaf[indexItem.Slot]
-		ret[i].Body = ret[i].Body.CloneItem()
-	}
 	node.Free()
 
-	err := tree.addErrs(searcher.Search, nil)
+	var err error
+	if cnt < min {
+		err = btrfstree.ErrNoItem
+	}
+	err = tree.addErrs(searcher.Search, err)
 	if err != nil {
 		err = fmt.Errorf("items with %s: %w", searcher, err)
 	}
-	return ret, err
+	return err
 }
 
+// TreeWalk implements btrfstree.TreeOperator.  It doesn't actually
+// visit nodes or keypointers (just items).
 func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
-	tree := bt.RebuiltTree(treeID)
+	tree := bt.RebuiltTree(ctx, treeID)
 	if tree.RootErr != nil {
 		errHandle(&btrfstree.TreeError{
 			Path: btrfstree.Path{{
@@ -341,7 +354,11 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 		})
 		return
 	}
-	if cbs.Item == nil {
+	tree.treeWalk(ctx, cbs)
+}
+
+func (tree oldRebuiltTree) treeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
+	if cbs.Item == nil && cbs.BadItem == nil {
 		return
 	}
 	var node *btrfstree.Node
@@ -349,18 +366,18 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 		if ctx.Err() != nil {
 			return false
 		}
-		if bt.ctx.Err() != nil {
+		if tree.forrest.ctx.Err() != nil {
 			return false
 		}
 		if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
 			node.Free()
-			node = bt.readNode(indexItem.Value.Node)
+			node = tree.forrest.readNode(indexItem.Value.Node)
 		}
 		item := node.BodyLeaf[indexItem.Value.Slot]
 
 		itemPath := btrfstree.Path{
 			{
-				FromTree:         treeID,
+				FromTree:         tree.ID,
 				ToNodeAddr:       indexItem.Value.Node.LAddr,
 				ToNodeGeneration: indexItem.Value.Node.Generation,
 				ToNodeLevel:      indexItem.Value.Node.Level,
@@ -374,18 +391,27 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 				ToMaxKey:     indexItem.Value.Key,
 			},
 		}
-		if err := cbs.Item(itemPath, item); err != nil {
-			errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
+		switch item.Body.(type) {
+		case *btrfsitem.Error:
+			if cbs.BadItem != nil {
+				cbs.BadItem(itemPath, item)
+			}
+		default:
+			if cbs.Item != nil {
+				cbs.Item(itemPath, item)
+			}
 		}
-		return true
+		return ctx.Err() == nil
 	})
 	node.Free()
 }
 
+// Superblock implements btrfs.ReadableFS.
 func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
 	return bt.inner.Superblock()
 }
 
+// ReadAt implements diskio.ReaderAt (and btrfs.ReadableFS).
 func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
 	return bt.inner.ReadAt(p, off)
 }
diff --git a/lib/btrfsutil/walk.go b/lib/btrfsutil/walk.go
index bbdf992..b05218c 100644
--- a/lib/btrfsutil/walk.go
+++ b/lib/btrfsutil/walk.go
@@ -61,7 +61,7 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre
 		},
 	}
 	origItem := cbs.Item
-	cbs.Item = func(path btrfstree.Path, item btrfstree.Item) error {
+	cbs.Item = func(path btrfstree.Path, item btrfstree.Item) {
 		if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
 			trees = append(trees, struct {
 				Name string
@@ -73,9 +73,8 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre
 			})
 		}
 		if origItem != nil {
-			return origItem(path, item)
+			origItem(path, item)
 		}
-		return nil
 	}
 
 	for i := 0; i < len(trees); i++ {