Merge branch 'lukeshu/api-cleanup'

10 files changed, 340 insertions, 529 deletions

diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 09a17b4..35848de 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -131,8 +131,8 @@ func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
 	})
 }
 
-func NewGraph(sb btrfstree.Superblock) *Graph {
-	g := &Graph{
+func NewGraph(sb btrfstree.Superblock) Graph {
+	g := Graph{
 		Nodes:     make(map[btrfsvol.LogicalAddr]GraphNode),
 		BadNodes:  make(map[btrfsvol.LogicalAddr]error),
 		EdgesFrom: make(map[btrfsvol.LogicalAddr][]*GraphEdge),
@@ -149,29 +149,29 @@ func NewGraph(sb btrfstree.Superblock) *Graph {
 	return g
 }
 
-func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
+func (g Graph) InsertNode(node *btrfstree.Node) {
 	nodeData := GraphNode{
-		Level:      nodeRef.Data.Head.Level,
-		Generation: nodeRef.Data.Head.Generation,
-		Owner:      nodeRef.Data.Head.Owner,
+		Level:      node.Head.Level,
+		Generation: node.Head.Generation,
+		Owner:      node.Head.Owner,
 	}
 
-	if nodeRef.Data.Head.Level == 0 {
+	if node.Head.Level == 0 {
 		cnt := 0
-		for _, item := range nodeRef.Data.BodyLeaf {
+		for _, item := range node.BodyLeaf {
 			if _, ok := item.Body.(*btrfsitem.Root); ok {
 				cnt++
 			}
 		}
 		kps := make([]GraphEdge, 0, cnt)
-		keys := make([]btrfsprim.Key, len(nodeRef.Data.BodyLeaf))
+		keys := make([]btrfsprim.Key, len(node.BodyLeaf))
 		nodeData.Items = keys
-		g.Nodes[nodeRef.Addr] = nodeData
-		for i, item := range nodeRef.Data.BodyLeaf {
+		g.Nodes[node.Head.Addr] = nodeData
+		for i, item := range node.BodyLeaf {
 			keys[i] = item.Key
 			if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
 				kps = append(kps, GraphEdge{
-					FromRoot:     nodeRef.Addr,
+					FromRoot:     node.Head.Addr,
 					FromItem:     i,
 					FromTree:     item.Key.ObjectID,
 					ToNode:       itemBody.ByteNr,
@@ -182,15 +182,15 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No
 			}
 		}
 	} else {
-		g.Nodes[nodeRef.Addr] = nodeData
-		kps := make([]GraphEdge, len(nodeRef.Data.BodyInterior))
-		for i, kp := range nodeRef.Data.BodyInterior {
+		g.Nodes[node.Head.Addr] = nodeData
+		kps := make([]GraphEdge, len(node.BodyInterior))
+		for i, kp := range node.BodyInterior {
 			kps[i] = GraphEdge{
-				FromNode:     nodeRef.Addr,
+				FromNode:     node.Head.Addr,
 				FromItem:     i,
-				FromTree:     nodeRef.Data.Head.Owner,
+				FromTree:     node.Head.Owner,
 				ToNode:       kp.BlockPtr,
-				ToLevel:      nodeRef.Data.Head.Level - 1,
+				ToLevel:      node.Head.Level - 1,
 				ToKey:        kp.Key,
 				ToGeneration: kp.Generation,
 			}
@@ -209,7 +209,7 @@ func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAd
 	for laddr := range g.EdgesTo {
 		if _, ok := g.Nodes[laddr]; !ok {
 			_, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{
-				LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
+				LAddr: containers.OptionalValue(laddr),
 			})
 			if err == nil {
 				progressWriter.Done()
diff --git a/lib/btrfsutil/listnodes.go b/lib/btrfsutil/listnodes.go
index 5505d23..70b647c 100644
--- a/lib/btrfsutil/listnodes.go
+++ b/lib/btrfsutil/listnodes.go
@@ -11,7 +11,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
@@ -44,8 +43,8 @@ func (*nodeScanner) ScanSector(context.Context, *btrfs.Device, btrfsvol.Physical
 	return nil
 }
 
-func (s *nodeScanner) ScanNode(_ context.Context, nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Node]) error {
-	s.nodes.Insert(nodeRef.Data.Head.Addr)
+func (s *nodeScanner) ScanNode(_ context.Context, _ btrfsvol.PhysicalAddr, node *btrfstree.Node) error {
+	s.nodes.Insert(node.Head.Addr)
 	return nil
 }
 
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index d49f34e..abe3329 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -17,7 +17,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 )
 
 type oldRebuiltTree struct {
@@ -27,14 +26,34 @@ type oldRebuiltTree struct {
 }
 
 type oldRebuiltTreeError struct {
-	Path SkinnyPath
-	Err  error
+	Min btrfsprim.Key
+	Max btrfsprim.Key
+	Err error
+}
+
+func (e oldRebuiltTreeError) Error() string {
+	return fmt.Sprintf("keys %v-%v: %v", e.Min, e.Max, e.Err)
+}
+
+func (e oldRebuiltTreeError) Unwrap() error {
+	return e.Err
 }
 
 type oldRebuiltTreeValue struct {
-	Path     SkinnyPath
 	Key      btrfsprim.Key
 	ItemSize uint32
+
+	Node nodeInfo
+	Slot int
+}
+
+type nodeInfo struct {
+	LAddr      btrfsvol.LogicalAddr
+	Level      uint8
+	Generation btrfsprim.Generation
+	Owner      btrfsprim.ObjID
+	MinItem    btrfsprim.Key
+	MaxItem    btrfsprim.Key
 }
 
 // Compare implements containers.Ordered.
@@ -42,15 +61,15 @@ func (a oldRebuiltTreeValue) Compare(b oldRebuiltTreeValue) int {
 	return a.Key.Compare(b.Key)
 }
 
-func newOldRebuiltTree(arena *SkinnyPathArena) oldRebuiltTree {
+func newOldRebuiltTree() oldRebuiltTree {
 	return oldRebuiltTree{
 		Items: new(containers.RBTree[oldRebuiltTreeValue]),
 		Errors: &containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]{
 			MinFn: func(err oldRebuiltTreeError) btrfsprim.Key {
-				return arena.Inflate(err.Path).Node(-1).ToKey
+				return err.Min
 			},
 			MaxFn: func(err oldRebuiltTreeError) btrfsprim.Key {
-				return arena.Inflate(err.Path).Node(-1).ToMaxKey
+				return err.Max
 			},
 		},
 	}
@@ -60,8 +79,6 @@ type OldRebuiltForrest struct {
 	ctx   context.Context //nolint:containedctx // don't have an option while keeping the same API
 	inner *btrfs.FS
 
-	arena *SkinnyPathArena
-
 	// btrfsprim.ROOT_TREE_OBJECTID
 	rootTreeMu sync.Mutex
 	rootTree   *oldRebuiltTree
@@ -98,19 +115,12 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre
 }
 
 func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree {
-	var treeRoot *btrfstree.TreeRoot
-	var sb *btrfstree.Superblock
-	var err error
 	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
 		bt.rootTreeMu.Lock()
 		defer bt.rootTreeMu.Unlock()
 		if bt.rootTree != nil {
 			return *bt.rootTree
 		}
-		sb, err = bt.inner.Superblock()
-		if err == nil {
-			treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID)
-		}
 	} else {
 		bt.treesMu.Lock()
 		defer bt.treesMu.Unlock()
@@ -120,29 +130,13 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 		if cacheEntry, exists := bt.trees[treeID]; exists {
 			return cacheEntry
 		}
-		sb, err = bt.inner.Superblock()
-		if err == nil {
-			treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID)
-		}
-	}
-	if bt.arena == nil {
-		var _sb btrfstree.Superblock
-		if sb != nil {
-			_sb = *sb
-		}
-		bt.arena = &SkinnyPathArena{
-			FS: bt.inner,
-			SB: _sb,
-		}
-	}
-	cacheEntry := newOldRebuiltTree(bt.arena)
-	if err != nil {
-		cacheEntry.RootErr = err
-	} else {
-		dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
-		bt.rawTreeWalk(*treeRoot, cacheEntry, nil)
-		dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
 	}
+
+	cacheEntry := newOldRebuiltTree()
+	dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
+	bt.rawTreeWalk(treeID, &cacheEntry)
+	dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
+
 	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
 		bt.rootTree = &cacheEntry
 	} else {
@@ -151,7 +145,20 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 	return cacheEntry
 }
 
-func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) {
+func discardOK[T any](x T, _ bool) T { return x }
+
+func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
+	sb, err := bt.inner.Superblock()
+	if err != nil {
+		cacheEntry.RootErr = err
+		return
+	}
+	root, err := btrfstree.LookupTreeRoot(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
@@ -159,13 +166,39 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 			panic(fmt.Errorf("TODO: error parsing item: %w", err))
 		}
 		cacheEntry.Errors.Insert(oldRebuiltTreeError{
-			Path: bt.arena.Deflate(err.Path),
-			Err:  err.Err,
+			Min: err.Path.Node(-1).ToKey,
+			Max: err.Path.Node(-1).ToMaxKey,
+			Err: err.Err,
 		})
 	}
 
+	var curNode nodeInfo
 	cbs := btrfstree.TreeWalkHandler{
-		Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+		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
+		},
+		Node: func(path btrfstree.Path, node *btrfstree.Node) error {
+			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 nil
+		},
+		Item: func(path btrfstree.Path, item btrfstree.Item) error {
 			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
@@ -173,33 +206,29 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 				panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
 			}
 			cacheEntry.Items.Insert(oldRebuiltTreeValue{
-				Path:     bt.arena.Deflate(path),
 				Key:      item.Key,
 				ItemSize: item.BodySize,
+
+				Node: curNode,
+				Slot: path.Node(-1).FromItemSlot,
 			})
-			if walked != nil {
-				*walked = append(*walked, item.Key)
-			}
 			return nil
 		},
 	}
 
-	btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, root, errHandle, cbs)
+	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))
 }
 
-func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error {
+func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
 	var errs derror.MultiError
 	tree.Errors.Subrange(
 		func(k btrfsprim.Key) int { return fn(k, 0) },
 		func(v oldRebuiltTreeError) bool {
-			path := bt.arena.Inflate(v.Path)
-			minKey := path.Node(-1).ToKey
-			maxKey := path.Node(-1).ToMaxKey
-			errs = append(errs, fmt.Errorf("keys %v-%v: %w", minKey, maxKey, v.Err))
+			errs = append(errs, v)
 			return true
 		})
 	if len(errs) == 0 {
@@ -211,6 +240,33 @@ func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key,
 	return errs
 }
 
+func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
+	sb, err := bt.inner.Superblock()
+	if err != nil {
+		panic(fmt.Errorf("should not happen: i/o error: %w", err))
+	}
+
+	node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeInfo.LAddr, btrfstree.NodeExpectations{
+		LAddr:      containers.OptionalValue(nodeInfo.LAddr),
+		Level:      containers.OptionalValue(nodeInfo.Level),
+		Generation: containers.OptionalValue(nodeInfo.Generation),
+		Owner: func(treeID btrfsprim.ObjID) error {
+			if treeID != nodeInfo.Owner {
+				return fmt.Errorf("expected owner=%v but claims to have owner=%v",
+					nodeInfo.Owner, treeID)
+			}
+			return nil
+		},
+		MinItem: containers.OptionalValue(nodeInfo.MinItem),
+		MaxItem: containers.OptionalValue(nodeInfo.MaxItem),
+	})
+	if err != nil {
+		panic(fmt.Errorf("should not happen: i/o error: %w", err))
+	}
+
+	return node
+}
+
 func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
 	tree := bt.RebuiltTree(treeID)
 	if tree.RootErr != nil {
@@ -221,21 +277,17 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr
 		return searcher.Search(indexItem.Key, indexItem.ItemSize)
 	})
 	if indexItem == nil {
-		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem))
+		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
 	}
 
-	itemPath := bt.arena.Inflate(indexItem.Value.Path)
-	node, err := bt.inner.ReadNode(itemPath.Parent())
-	defer btrfstree.FreeNodeRef(node)
-	if err != nil {
-		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
-	}
+	node := bt.readNode(indexItem.Value.Node)
+	defer node.Free()
 
-	item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+	item := node.BodyLeaf[indexItem.Value.Slot]
 	item.Body = item.Body.CloneItem()
 
 	// Since we were only asked to return 1 item, it isn't
-	// necessary to augment this `nil` with bt.addErrs().
+	// necessary to augment this `nil` with tree.addErrs().
 	return item, nil
 }
 
@@ -255,28 +307,22 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf
 			return true
 		})
 	if len(indexItems) == 0 {
-		return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem))
+		return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
 	}
 
 	ret := make([]btrfstree.Item, len(indexItems))
-	var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
-	for i := range indexItems {
-		itemPath := bt.arena.Inflate(indexItems[i].Path)
-		if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
-			var err error
-			btrfstree.FreeNodeRef(node)
-			node, err = bt.inner.ReadNode(itemPath.Parent())
-			if err != nil {
-				btrfstree.FreeNodeRef(node)
-				return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
-			}
+	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.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+		ret[i] = node.BodyLeaf[indexItem.Slot]
 		ret[i].Body = ret[i].Body.CloneItem()
 	}
-	btrfstree.FreeNodeRef(node)
+	node.Free()
 
-	err := bt.addErrs(tree, searcher.Search, nil)
+	err := tree.addErrs(searcher.Search, nil)
 	if err != nil {
 		err = fmt.Errorf("items with %s: %w", searcher, err)
 	}
@@ -287,7 +333,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 	tree := bt.RebuiltTree(treeID)
 	if tree.RootErr != nil {
 		errHandle(&btrfstree.TreeError{
-			Path: btrfstree.TreePath{{
+			Path: btrfstree.Path{{
 				FromTree: treeID,
 				ToMaxKey: btrfsprim.MaxKey,
 			}},
@@ -298,7 +344,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 	if cbs.Item == nil {
 		return
 	}
-	var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
+	var node *btrfstree.Node
 	tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
 		if ctx.Err() != nil {
 			return false
@@ -306,24 +352,34 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 		if bt.ctx.Err() != nil {
 			return false
 		}
-		itemPath := bt.arena.Inflate(indexItem.Value.Path)
-		if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
-			var err error
-			btrfstree.FreeNodeRef(node)
-			node, err = bt.inner.ReadNode(itemPath.Parent())
-			if err != nil {
-				btrfstree.FreeNodeRef(node)
-				errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
-				return true
-			}
+		if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
+			node.Free()
+			node = bt.readNode(indexItem.Value.Node)
+		}
+		item := node.BodyLeaf[indexItem.Value.Slot]
+
+		itemPath := btrfstree.Path{
+			{
+				FromTree:         treeID,
+				ToNodeAddr:       indexItem.Value.Node.LAddr,
+				ToNodeGeneration: indexItem.Value.Node.Generation,
+				ToNodeLevel:      indexItem.Value.Node.Level,
+				ToKey:            indexItem.Value.Node.MinItem,
+				ToMaxKey:         indexItem.Value.Node.MaxItem,
+			},
+			{
+				FromTree:     indexItem.Value.Node.Owner,
+				FromItemSlot: indexItem.Value.Slot,
+				ToKey:        indexItem.Value.Key,
+				ToMaxKey:     indexItem.Value.Key,
+			},
 		}
-		item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
 		if err := cbs.Item(itemPath, item); err != nil {
 			errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
 		}
 		return true
 	})
-	btrfstree.FreeNodeRef(node)
+	node.Free()
 }
 
 func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
@@ -333,27 +389,3 @@ func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
 func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
 	return bt.inner.ReadAt(p, off)
 }
-
-func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) {
-	sb, err := bt.Superblock()
-	if err != nil {
-		return nil, err
-	}
-	tree := bt.RebuiltTree(treeID)
-	if tree.RootErr != nil {
-		return nil, tree.RootErr
-	}
-	nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
-	defer btrfstree.FreeNodeRef(nodeRef)
-	if err != nil {
-		return nil, err
-	}
-	var ret []btrfsprim.Key
-	bt.rawTreeWalk(btrfstree.TreeRoot{
-		TreeID:     treeID,
-		RootNode:   nodeAddr,
-		Level:      nodeRef.Data.Head.Level,
-		Generation: nodeRef.Data.Head.Generation,
-	}, tree, &ret)
-	return ret, nil
-}
diff --git a/lib/btrfsutil/print_addrspace.go b/lib/btrfsutil/print_addrspace.go
deleted file mode 100644
index ae2c492..0000000
--- a/lib/btrfsutil/print_addrspace.go
+++ /dev/null
@@ -1,73 +0,0 @@
-// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
-	"io"
-	"sort"
-
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-func PrintLogicalSpace(out io.Writer, fs *btrfs.FS) {
-	mappings := fs.LV.Mappings()
-	var prevBeg, prevEnd btrfsvol.LogicalAddr
-	var sumHole, sumChunk btrfsvol.AddrDelta
-	for _, mapping := range mappings {
-		if mapping.LAddr > prevEnd {
-			size := mapping.LAddr.Sub(prevEnd)
-			textui.Fprintf(out, "logical_hole laddr=%v size=%v\n", prevEnd, size)
-			sumHole += size
-		}
-		if mapping.LAddr != prevBeg {
-			if !mapping.Flags.OK {
-				textui.Fprintf(out, "chunk laddr=%v size=%v flags=(missing)\n",
-					mapping.LAddr, mapping.Size)
-			} else {
-				textui.Fprintf(out, "chunk laddr=%v size=%v flags=%v\n",
-					mapping.LAddr, mapping.Size, mapping.Flags.Val)
-			}
-		}
-		textui.Fprintf(out, "\tstripe dev_id=%v paddr=%v\n",
-			mapping.PAddr.Dev, mapping.PAddr.Addr)
-		sumChunk += mapping.Size
-		prevBeg = mapping.LAddr
-		prevEnd = mapping.LAddr.Add(mapping.Size)
-	}
-	textui.Fprintf(out, "total logical holes      = %v (%d)\n", sumHole, int64(sumHole))
-	textui.Fprintf(out, "total logical chunks     = %v (%d)\n", sumChunk, int64(sumChunk))
-	textui.Fprintf(out, "total logical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
-}
-
-func PrintPhysicalSpace(out io.Writer, fs *btrfs.FS) {
-	mappings := fs.LV.Mappings()
-	sort.Slice(mappings, func(i, j int) bool {
-		return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
-	})
-
-	var prevDev btrfsvol.DeviceID
-	var prevEnd btrfsvol.PhysicalAddr
-	var sumHole, sumExt btrfsvol.AddrDelta
-	for _, mapping := range mappings {
-		if mapping.PAddr.Dev != prevDev {
-			prevDev = mapping.PAddr.Dev
-			prevEnd = 0
-		}
-		if mapping.PAddr.Addr > prevEnd {
-			size := mapping.PAddr.Addr.Sub(prevEnd)
-			textui.Fprintf(out, "physical_hole paddr=%v size=%v\n", prevEnd, size)
-			sumHole += size
-		}
-		textui.Fprintf(out, "devext dev=%v paddr=%v size=%v laddr=%v\n",
-			mapping.PAddr.Dev, mapping.PAddr.Addr, mapping.Size, mapping.LAddr)
-		sumExt += mapping.Size
-		prevEnd = mapping.PAddr.Addr.Add(mapping.Size)
-	}
-	textui.Fprintf(out, "total physical holes      = %v (%d)\n", sumHole, int64(sumHole))
-	textui.Fprintf(out, "total physical extents    = %v (%d)\n", sumExt, int64(sumExt))
-	textui.Fprintf(out, "total physical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
-}
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 70ece13..b5c646d 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -6,6 +6,8 @@ package btrfsutil
 
 import (
 	"context"
+	"fmt"
+	"sync"
 
 	"github.com/datawire/dlib/dlog"
 
@@ -14,6 +16,7 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
@@ -25,13 +28,71 @@ type RebuiltForrestCallbacks interface {
 	LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
 }
 
+type noopRebuiltForrestCallbacks struct {
+	forrest *RebuiltForrest
+}
+
+func (noopRebuiltForrestCallbacks) AddedItem(context.Context, btrfsprim.ObjID, btrfsprim.Key) {}
+func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, btrfsvol.LogicalAddr) {
+}
+
+func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, ok bool) {
+	rootTree := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+	if rootTree == nil {
+		return 0, btrfsitem.Root{}, false
+	}
+	tgt := btrfsprim.Key{
+		ObjectID: tree,
+		ItemType: btrfsprim.ROOT_ITEM_KEY,
+	}
+	itemKey, itemPtr, ok := rootTree.RebuiltItems(ctx).Search(func(key btrfsprim.Key, _ ItemPtr) int {
+		key.Offset = 0
+		return tgt.Compare(key)
+	})
+	itemBody := cb.forrest.readItem(ctx, itemPtr)
+	defer itemBody.Free()
+	switch itemBody := itemBody.(type) {
+	case *btrfsitem.Root:
+		return btrfsprim.Generation(itemKey.Offset), *itemBody, true
+	case *btrfsitem.Error:
+		return 0, btrfsitem.Root{}, false
+	default:
+		// This is a panic because the item decoder should not emit ROOT_ITEM items as anything but
+		// btrfsitem.Root or btrfsitem.Error without this code also being updated.
+		panic(fmt.Errorf("should not happen: ROOT_ITEM item has unexpected type: %T", itemBody))
+	}
+}
+
+func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+	uuidTree := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+	if uuidTree == nil {
+		return 0, false
+	}
+	tgt := btrfsitem.UUIDToKey(uuid)
+	itemPtr, ok := uuidTree.RebuiltItems(ctx).Load(tgt)
+	if !ok {
+		return 0, false
+	}
+	itemBody := cb.forrest.readItem(ctx, itemPtr)
+	defer itemBody.Free()
+	switch itemBody := itemBody.(type) {
+	case *btrfsitem.UUIDMap:
+		return itemBody.ObjID, true
+	case *btrfsitem.Error:
+		return 0, false
+	default:
+		// This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
+		// btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated.
+		panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", itemBody))
+	}
+}
+
 // RebuiltForrest is an abstraction for rebuilding and accessing
 // potentially broken btrees.
 //
-// It is conceptually a btrfstree.TreeOperator, and adds similar
-// broken-tree handling to OldRebuiltForrest.  However, the API is
-// different than btrfstree.TreeOperator, and is much more efficient
-// than OldRebuiltForrest.
+// It is conceptually a btrfstree.Forrest, and adds similar
+// broken-tree handling to OldRebuiltForrest.  However, it is much
+// more efficient than OldRebuiltForrest.
 //
 // The efficiency improvements are possible because of the API
 // differences, which are necessary for how it is used in
@@ -40,43 +101,60 @@ type RebuiltForrestCallbacks interface {
 //   - it consumes an already-read Graph instead of reading the graph
 //     itself
 //
-//   - it does not use `btrfstree.TreePath`
+//   - it does not use `btrfstree.Path`
 //
 //   - it does not keep track of errors encountered in a tree
 //
 // Additionally, it provides some functionality that OldRebuiltForrest
 // does not:
 //
-//   - it provides a .LeafToRoots() method to advise on what
-//     additional roots should be added
+//   - it provides a RebuiltForrest.RebuiltListRoots() method for
+//     listing how trees have been repaired.
+//
+//   - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a
+//     tree.
+//
+//   - it provides several RebuiltTree methods that provide advice on
+//     what roots should be added to a tree in order to repair it:
+//
+//     .RebuiltItems() and RebuiltPotentialItems() to compare what's
+//     in the tree and what could be in the tree.
 //
-//   - it provides a .COWDistance() method to compare how related two
-//     trees are
+//     .RebuiltLeafToRoots() to map potential items to things that can
+//     be passed to .RebuiltAddRoot().
+//
+//     .RebuiltCOWDistance() and .RebuiltShouldReplace() to provide
+//     information on deciding on an option from
+//     .RebuiltLeafToRoots().
 //
 // A zero RebuiltForrest is invalid; it must be initialized with
 // NewRebuiltForrest().
 type RebuiltForrest struct {
 	// static
+	file  diskio.File[btrfsvol.LogicalAddr]
 	sb    btrfstree.Superblock
 	graph Graph
-	keyIO *KeyIO
 	cb    RebuiltForrestCallbacks
 
 	// mutable
+
 	treesMu  nestedMutex
 	trees    map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
 	leafs    containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
 	incItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
 	excItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
+
+	nodesMu sync.Mutex
+	nodes   containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]
 }
 
-// NewRebuiltForrest returns a new RebuiltForrest instance.  All of
-// the callbacks must be non-nil.
-func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb RebuiltForrestCallbacks) *RebuiltForrest {
-	return &RebuiltForrest{
+// NewRebuiltForrest returns a new RebuiltForrest instance.  The
+// RebuiltForrestCallbacks may be nil.
+func NewRebuiltForrest(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph Graph, cb RebuiltForrestCallbacks) *RebuiltForrest {
+	ret := &RebuiltForrest{
+		file:  file,
 		sb:    sb,
 		graph: graph,
-		keyIO: keyIO,
 		cb:    cb,
 
 		trees: make(map[btrfsprim.ObjID]*RebuiltTree),
@@ -89,15 +167,31 @@ func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb Re
 		excItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{
 			MaxLen: textui.Tunable(8),
 		},
+
+		nodes: containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]{
+			MaxLen: textui.Tunable(8),
+			OnRemove: func(_ btrfsvol.LogicalAddr, node *btrfstree.Node) {
+				node.Free()
+			},
+		},
 	}
+	if ret.cb == nil {
+		ret.cb = noopRebuiltForrestCallbacks{
+			forrest: ret,
+		}
+	}
+	return ret
 }
 
-// Tree returns a given tree, initializing it if nescessary.  If it is
-// unable to initialize the tree, then nil is returned, and nothing is
-// done to the forrest.
+// RebuiltTree returns a given tree, initializing it if nescessary.
+// If it is unable to initialize the tree, then nil is returned, and
+// nothing is done to the forrest.
 //
 // The tree is initialized with the normal root node of the tree.
-func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
+//
+// This is identical to .ForrestLookup(), but returns a concrete type
+// rather than an interface.
+func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
 	ctx = ts.treesMu.Lock(ctx)
 	defer ts.treesMu.Unlock()
 	if !ts.addTree(ctx, treeID, nil) {
@@ -112,8 +206,8 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
 	}
 	defer func() {
 		if !ok {
-			// Store a negative cache of this.  tree.AddRoot() for the ROOT or UUID
-			// trees will call .flushNegativeCache().
+			// Store a negative cache of this.  tree.RebuiltAddRoot() for the ROOT or
+			// UUID trees will call .flushNegativeCache().
 			ts.trees[treeID] = nil
 		}
 	}()
@@ -172,7 +266,7 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
 
 	ts.trees[treeID] = tree
 	if root != 0 {
-		tree.AddRoot(ctx, root)
+		tree.RebuiltAddRoot(ctx, root)
 	}
 
 	return true
@@ -188,12 +282,12 @@ func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
 	}
 }
 
-// ListRoots returns a listing of all initialized trees and their root
-// nodes.
+// RebuiltListRoots returns a listing of all initialized trees and
+// their root nodes.
 //
 // Do not mutate the set of roots for a tree; it is a pointer to the
 // RebuiltForrest's internal set!
-func (ts *RebuiltForrest) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
+func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
 	_ = ts.treesMu.Lock(ctx)
 	defer ts.treesMu.Unlock()
 	ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index 016299c..ff919f0 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -7,7 +7,6 @@ package btrfsutil
 import (
 	"context"
 	"fmt"
-	"sync"
 
 	"github.com/datawire/dlib/dlog"
 
@@ -16,8 +15,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
-	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
 type ItemPtr struct {
@@ -29,111 +26,22 @@ func (ptr ItemPtr) String() string {
 	return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot)
 }
 
-type SizeAndErr struct {
-	Size uint64
-	Err  error
-}
-
-type FlagsAndErr struct {
-	NoDataSum bool
-	Err       error
-}
-
-type KeyIO struct {
-	rawFile diskio.File[btrfsvol.LogicalAddr]
-	sb      btrfstree.Superblock
-	graph   Graph
-
-	Flags map[ItemPtr]FlagsAndErr // INODE_ITEM
-	Names map[ItemPtr][]byte      // DIR_INDEX
-	Sizes map[ItemPtr]SizeAndErr  // EXTENT_CSUM and EXTENT_DATA
-
-	mu    sync.Mutex
-	cache containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
-}
-
-func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *KeyIO {
-	return &KeyIO{
-		rawFile: file,
-		sb:      sb,
-
-		Flags: make(map[ItemPtr]FlagsAndErr),
-		Names: make(map[ItemPtr][]byte),
-		Sizes: make(map[ItemPtr]SizeAndErr),
-
-		cache: containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]{
-			MaxLen: textui.Tunable(8),
-			OnRemove: func(_ btrfsvol.LogicalAddr, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
-				btrfstree.FreeNodeRef(nodeRef)
-			},
-		},
-	}
-}
-
-func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
-	for i, item := range nodeRef.Data.BodyLeaf {
-		ptr := ItemPtr{
-			Node: nodeRef.Addr,
-			Slot: i,
-		}
-		switch itemBody := item.Body.(type) {
-		case *btrfsitem.Inode:
-			o.Flags[ptr] = FlagsAndErr{
-				NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM),
-				Err:       nil,
-			}
-		case *btrfsitem.DirEntry:
-			if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY {
-				o.Names[ptr] = append([]byte(nil), itemBody.Name...)
-			}
-		case *btrfsitem.ExtentCSum:
-			o.Sizes[ptr] = SizeAndErr{
-				Size: uint64(itemBody.Size()),
-				Err:  nil,
-			}
-		case *btrfsitem.FileExtent:
-			size, err := itemBody.Size()
-			o.Sizes[ptr] = SizeAndErr{
-				Size: uint64(size),
-				Err:  err,
-			}
-		case *btrfsitem.Error:
-			switch item.Key.ItemType {
-			case btrfsprim.INODE_ITEM_KEY:
-				o.Flags[ptr] = FlagsAndErr{
-					Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
-						ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
-				}
-			case btrfsprim.EXTENT_CSUM_KEY, btrfsprim.EXTENT_DATA_KEY:
-				o.Sizes[ptr] = SizeAndErr{
-					Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
-						ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
-				}
-			}
-		}
-	}
-}
-
-func (o *KeyIO) SetGraph(graph Graph) {
-	o.graph = graph
-}
-
-func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] {
-	if cached, ok := o.cache.Load(laddr); ok {
+func (ts *RebuiltForrest) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *btrfstree.Node {
+	if cached, ok := ts.nodes.Load(laddr); ok {
 		dlog.Tracef(ctx, "cache-hit node@%v", laddr)
 		return cached
 	}
 
-	graphInfo, ok := o.graph.Nodes[laddr]
+	graphInfo, ok := ts.graph.Nodes[laddr]
 	if !ok {
 		panic(fmt.Errorf("should not happen: node@%v is not mentioned in the in-memory graph", laddr))
 	}
 
 	dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr)
-	ref, err := btrfstree.ReadNode(o.rawFile, o.sb, laddr, btrfstree.NodeExpectations{
-		LAddr:      containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
-		Level:      containers.Optional[uint8]{OK: true, Val: graphInfo.Level},
-		Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: graphInfo.Generation},
+	node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](ts.file, ts.sb, laddr, btrfstree.NodeExpectations{
+		LAddr:      containers.OptionalValue(laddr),
+		Level:      containers.OptionalValue(graphInfo.Level),
+		Generation: containers.OptionalValue(graphInfo.Generation),
 		Owner: func(treeID btrfsprim.ObjID) error {
 			if treeID != graphInfo.Owner {
 				return fmt.Errorf("expected owner=%v but claims to have owner=%v",
@@ -141,30 +49,30 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diski
 			}
 			return nil
 		},
-		MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem()},
-		MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem()},
+		MinItem: containers.OptionalValue(graphInfo.MinItem()),
+		MaxItem: containers.OptionalValue(graphInfo.MaxItem()),
 	})
 	if err != nil {
 		panic(fmt.Errorf("should not happen: i/o error: %w", err))
 	}
 
-	o.cache.Store(laddr, ref)
+	ts.nodes.Store(laddr, node)
 
-	return ref
+	return node
 }
 
-func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
-	o.mu.Lock()
-	defer o.mu.Unlock()
-	if o.graph.Nodes[ptr.Node].Level != 0 {
-		panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for non-leaf node@%v", ptr.Node))
+func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
+	ts.nodesMu.Lock()
+	defer ts.nodesMu.Unlock()
+	if ts.graph.Nodes[ptr.Node].Level != 0 {
+		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for non-leaf node@%v", ptr.Node))
 	}
 	if ptr.Slot < 0 {
-		panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item slot: %v", ptr.Slot))
+		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for negative item slot: %v", ptr.Slot))
 	}
-	items := o.readNode(ctx, ptr.Node).Data.BodyLeaf
+	items := ts.readNode(ctx, ptr.Node).BodyLeaf
 	if ptr.Slot >= len(items) {
-		panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item slot: slot=%v len=%v",
+		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for out-of-bounds item slot: slot=%v len=%v",
 			ptr.Slot, len(items)))
 	}
 	return items[ptr.Slot].Body.CloneItem()
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 3133a9e..3fff9b2 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -37,9 +37,9 @@ type RebuiltTree struct {
 	// derived from tree.Roots, which is why it's OK if they get
 	// evicted.
 	//
-	//  1. tree.leafToRoots()    = tree.forrest.leafs.Load(tree.ID)
-	//  2. tree.Items()          = tree.forrest.incItems.Load(tree.ID)
-	//  3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID)
+	//  1. tree.leafToRoots()           = tree.forrest.leafs.Load(tree.ID)
+	//  2. tree.RebuiltItems()          = tree.forrest.incItems.Load(tree.ID)
+	//  3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Load(tree.ID)
 }
 
 // evictable member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////
@@ -129,23 +129,23 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
 	}
 }
 
-// evictable members 2 and 3: .Items() and .PotentialItems() ///////////////////////////////////////////////////////////
+// evictable members 2 and 3: .RebuiltItems() and .RebuiltPotentialItems() /////////////////////////////////////////////
 
-// Items returns a map of the items contained in this tree.
+// RebuiltItems returns a map of the items contained in this tree.
 //
 // Do not mutate the returned map; it is a pointer to the
 // RebuiltTree's internal map!
-func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) RebuiltItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-inc-items", fmt.Sprintf("tree=%v", tree.ID))
 	return tree.items(ctx, &tree.forrest.incItems, tree.Roots.HasAny)
 }
 
-// PotentialItems returns a map of items that could be added to this
-// tree with .AddRoot().
+// RebuiltPotentialItems returns a map of items that could be added to
+// this tree with .RebuiltAddRoot().
 //
 // Do not mutate the returned map; it is a pointer to the
 // RebuiltTree's internal map!
-func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) RebuiltPotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-exc-items", fmt.Sprintf("tree=%v", tree.ID))
 	return tree.items(ctx, &tree.forrest.excItems,
 		func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
@@ -198,7 +198,7 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr
 					index.Store(itemKey, newPtr)
 					stats.NumItems++
 				} else {
-					if tree.ShouldReplace(oldPtr.Node, newPtr.Node) {
+					if tree.RebuiltShouldReplace(oldPtr.Node, newPtr.Node) {
 						index.Store(itemKey, newPtr)
 					}
 					stats.NumDups++
@@ -216,9 +216,11 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr
 	})
 }
 
-func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
-	oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
-	newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner)
+// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
+
+func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
+	oldDist, _ := tree.RebuiltCOWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
+	newDist, _ := tree.RebuiltCOWDistance(tree.forrest.graph.Nodes[newNode].Owner)
 	switch {
 	case newDist < oldDist:
 		// Replace the old one with the new lower-dist one.
@@ -248,8 +250,6 @@ func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bo
 	}
 }
 
-// .AddRoot() //////////////////////////////////////////////////////////////////////////////////////////////////////////
-
 type rootStats struct {
 	Leafs      textui.Portion[int]
 	AddedLeafs int
@@ -261,10 +261,10 @@ func (s rootStats) String() string {
 		s.Leafs, s.AddedLeafs, s.AddedItems)
 }
 
-// AddRoot adds an additional root node to the tree.  It is useful to
-// call .AddRoot() to re-attach part of the tree that has been broken
-// off.
-func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
+// RebuiltAddRoot adds an additional root node to the tree.  It is
+// useful to call .RebuiltAddRoot() to re-attach part of the tree that
+// has been broken off.
+func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
 	tree.mu.Lock()
 	defer tree.mu.Unlock()
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
@@ -306,11 +306,9 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA
 	tree.forrest.cb.AddedRoot(ctx, tree.ID, rootNode)
 }
 
-// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
-
-// COWDistance returns how many COW-snapshots down the 'tree' is from
-// the 'parent'.
-func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
+// RebuiltCOWDistance returns how many COW-snapshots down the 'tree'
+// is from the 'parent'.
+func (tree *RebuiltTree) RebuiltCOWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
 	for {
 		if parentID == tree.ID {
 			return dist, true
@@ -325,18 +323,18 @@ func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok boo
 
 // ReadItem reads an item from a tree.
 func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsitem.Item {
-	ptr, ok := tree.Items(ctx).Load(key)
+	ptr, ok := tree.RebuiltItems(ctx).Load(key)
 	if !ok {
 		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltTree.ReadItem called for not-included key: %v", key))
 	}
-	return tree.forrest.keyIO.ReadItem(ctx, ptr)
+	return tree.forrest.readItem(ctx, ptr)
 }
 
-// LeafToRoots returns the list of potential roots (to pass to
-// .AddRoot) that include a given leaf-node.
-func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
+// RebuiltLeafToRoots returns the list of potential roots (to pass to
+// .RebuiltAddRoot) that include a given leaf-node.
+func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
 	if tree.forrest.graph.Nodes[leaf].Level != 0 {
-		panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf",
+		panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): not a leaf",
 			tree.ID, leaf))
 	}
 	tree.mu.RLock()
@@ -344,7 +342,7 @@ func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalA
 	ret := make(containers.Set[btrfsvol.LogicalAddr])
 	for root := range tree.leafToRoots(ctx)[leaf] {
 		if tree.Roots.Has(root) {
-			panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf",
+			panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): tree contains root=%v but not leaf",
 				tree.ID, leaf, root))
 		}
 		ret.Insert(root)
diff --git a/lib/btrfsutil/scan.go b/lib/btrfsutil/scan.go
index 97220aa..05b27d5 100644
--- a/lib/btrfsutil/scan.go
+++ b/lib/btrfsutil/scan.go
@@ -19,7 +19,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
@@ -30,7 +29,7 @@ type DeviceScannerFactory[Stats comparable, Result any] func(ctx context.Context
 type DeviceScanner[Stats comparable, Result any] interface {
 	ScanStats() Stats
 	ScanSector(ctx context.Context, dev *btrfs.Device, paddr btrfsvol.PhysicalAddr) error
-	ScanNode(ctx context.Context, nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Node]) error
+	ScanNode(ctx context.Context, addr btrfsvol.PhysicalAddr, node *btrfstree.Node) error
 	ScanDone(ctx context.Context) (Result, error)
 }
 
@@ -123,19 +122,19 @@ func ScanOneDevice[Stats comparable, Result any](ctx context.Context, dev *btrfs
 		}
 
 		if checkForNode {
-			nodeRef, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, *sb, pos, btrfstree.NodeExpectations{})
+			node, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, *sb, pos, btrfstree.NodeExpectations{})
 			if err != nil {
 				if !errors.Is(err, btrfstree.ErrNotANode) {
 					dlog.Errorf(ctx, "error: %v", err)
 				}
 			} else {
-				if err := scanner.ScanNode(ctx, nodeRef); err != nil {
+				if err := scanner.ScanNode(ctx, pos, node); err != nil {
 					var zero Result
 					return zero, err
 				}
 				minNextNode = pos + btrfsvol.PhysicalAddr(sb.NodeSize)
 			}
-			btrfstree.FreeNodeRef(nodeRef)
+			node.Free()
 		}
 	}
 
diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go
deleted file mode 100644
index adf539b..0000000
--- a/lib/btrfsutil/skinny_paths.go
+++ /dev/null
@@ -1,146 +0,0 @@
-// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
-	"fmt"
-
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
-	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type skinnyItem struct {
-	Node btrfsvol.LogicalAddr
-	Item int
-}
-
-type SkinnyPath struct {
-	Root  btrfsvol.LogicalAddr
-	Items []int
-}
-
-type SkinnyPathArena struct {
-	FS diskio.File[btrfsvol.LogicalAddr]
-	SB btrfstree.Superblock
-
-	fatRoots map[btrfsvol.LogicalAddr]btrfstree.TreePathElem
-	fatItems containers.ARCache[skinnyItem, btrfstree.TreePathElem]
-}
-
-func (a *SkinnyPathArena) init() {
-	if a.fatRoots == nil {
-		a.fatRoots = make(map[btrfsvol.LogicalAddr]btrfstree.TreePathElem)
-		a.fatItems.MaxLen = textui.Tunable(128 * 1024)
-	}
-}
-
-func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrfstree.TreePathElem, error) {
-	if itemSlot < 0 {
-		panic("should not happen")
-	}
-
-	a.init()
-
-	ret, ok := a.fatItems.Load(skinnyItem{
-		Node: parent.Node(-1).ToNodeAddr,
-		Item: itemSlot,
-	})
-	if ok {
-		return ret, nil
-	}
-
-	node, err := btrfstree.ReadNode(a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{})
-	defer btrfstree.FreeNodeRef(node)
-	if err != nil {
-		return btrfstree.TreePathElem{}, err
-	}
-	if node.Data.Head.Level > 0 {
-		if itemSlot >= len(node.Data.BodyInterior) {
-			panic("should not happen")
-		}
-		for i, item := range node.Data.BodyInterior {
-			toMaxKey := parent.Node(-1).ToMaxKey
-			if i+1 < len(node.Data.BodyInterior) {
-				toMaxKey = node.Data.BodyInterior[i+1].Key.Mm()
-			}
-			elem := btrfstree.TreePathElem{
-				FromTree:         node.Data.Head.Owner,
-				FromItemSlot:     i,
-				ToNodeAddr:       item.BlockPtr,
-				ToNodeGeneration: item.Generation,
-				ToNodeLevel:      node.Data.Head.Level - 1,
-				ToKey:            item.Key,
-				ToMaxKey:         toMaxKey,
-			}
-			a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
-			if i == itemSlot {
-				ret = elem
-			}
-		}
-	} else {
-		if itemSlot >= len(node.Data.BodyLeaf) {
-			panic("should not happen")
-		}
-		for i, item := range node.Data.BodyLeaf {
-			elem := btrfstree.TreePathElem{
-				FromTree:     node.Data.Head.Owner,
-				FromItemSlot: i,
-				ToKey:        item.Key,
-				ToMaxKey:     item.Key,
-			}
-			a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
-			if i == itemSlot {
-				ret = elem
-			}
-		}
-	}
-
-	return ret, nil
-}
-
-func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath {
-	a.init()
-
-	var ret SkinnyPath
-
-	var prevNode btrfsvol.LogicalAddr
-	for i, elem := range fat {
-		if i == 0 {
-			a.fatRoots[elem.ToNodeAddr] = elem
-			ret.Root = elem.ToNodeAddr
-		} else {
-			a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemSlot}, elem)
-			ret.Items = append(ret.Items, elem.FromItemSlot)
-		}
-		prevNode = elem.ToNodeAddr
-	}
-	return ret
-}
-
-func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath {
-	a.init()
-
-	ret := make(btrfstree.TreePath, 0, 1+len(skinny.Items))
-
-	root, ok := a.fatRoots[skinny.Root]
-	if !ok {
-		panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for root->%v",
-			skinny.Root))
-	}
-	ret = append(ret, root)
-
-	for _, itemSlot := range skinny.Items {
-		elem, err := a.getItem(ret, itemSlot)
-		if err != nil {
-			panic(err)
-		}
-		ret = append(ret, elem)
-	}
-
-	return ret
-}
diff --git a/lib/btrfsutil/walk.go b/lib/btrfsutil/walk.go
index 355976a..bbdf992 100644
--- a/lib/btrfsutil/walk.go
+++ b/lib/btrfsutil/walk.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
@@ -61,7 +61,7 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre
 		},
 	}
 	origItem := cbs.Item
-	cbs.Item = func(path btrfstree.TreePath, item btrfstree.Item) error {
+	cbs.Item = func(path btrfstree.Path, item btrfstree.Item) error {
 		if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
 			trees = append(trees, struct {
 				Name string