Merge branch 'lukeshu/rebuilt-v2-pt3-errs'

9 files changed, 343 insertions, 63 deletions

diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index b9b9201..b071b7d 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -328,7 +328,8 @@ func (tree *RawTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfspr
 	}
 	parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID))
 	if err != nil {
-		return 0, 0, err
+		return 0, 0, fmt.Errorf("tree %s: failed to look up UUID: %v: %w",
+			tree.ID.Format(btrfsprim.ROOT_TREE_OBJECTID), tree.ParentUUID, err)
 	}
 	switch parentIDBody := parentIDItem.Body.(type) {
 	case *btrfsitem.UUIDMap:
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 327a39b..3fd43c8 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -134,7 +134,7 @@ func (path Path) String() string {
 	return ret.String()
 }
 
-func checkOwner(
+func CheckOwner(
 	ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID,
 	ownerToCheck btrfsprim.ObjID, genToCheck btrfsprim.Generation,
 ) error {
@@ -194,7 +194,7 @@ func (path Path) NodeExpectations(ctx context.Context) (_ btrfsvol.LogicalAddr,
 			Level:      containers.OptionalValue(lastElem.ToLevel),
 			Generation: containers.OptionalValue(lastElem.ToGeneration),
 			Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
-				return checkOwner(ctx, firstElem.Forrest, lastElem.TreeID,
+				return CheckOwner(ctx, firstElem.Forrest, lastElem.TreeID,
 					owner, gen)
 			},
 			MinItem: containers.OptionalValue(btrfsprim.Key{}),
@@ -206,7 +206,7 @@ func (path Path) NodeExpectations(ctx context.Context) (_ btrfsvol.LogicalAddr,
 			Level:      containers.OptionalValue(lastElem.ToLevel),
 			Generation: containers.OptionalValue(lastElem.ToGeneration),
 			Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
-				return checkOwner(ctx, firstElem.Forrest, lastElem.FromTree,
+				return CheckOwner(ctx, firstElem.Forrest, lastElem.FromTree,
 					owner, gen)
 			},
 			MinItem: containers.OptionalValue(lastElem.ToMinKey),
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index c9e1d79..7518561 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -6,7 +6,6 @@ package btrfs
 
 import (
 	"context"
-	"fmt"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
@@ -44,7 +43,7 @@ func (fs *FS) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp bt
 	if nodeEntry.node != nil {
 		if err := exp.Check(nodeEntry.node); err != nil {
 			fs.cacheNodes.Release(addr)
-			return nil, fmt.Errorf("btrfs.FS.AcquireNode: node@%v: %w", addr, err)
+			return nil, err
 		}
 	}
 
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
index 9b70713..1b7837e 100644
--- a/lib/btrfs/io4_fs.go
+++ b/lib/btrfs/io4_fs.go
@@ -423,7 +423,7 @@ func (sv *Subvolume) loadFile(_ context.Context, inode btrfsprim.ObjID, file *Fi
 		if err != nil {
 			file.Errs = append(file.Errs, fmt.Errorf("extent %v: %w", extent.OffsetWithinFile, err))
 		}
-		pos += size
+		pos = extent.OffsetWithinFile + size
 	}
 	if file.InodeItem != nil && pos != file.InodeItem.NumBytes {
 		if file.InodeItem.NumBytes > pos {
diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go
index 0b51d08..b5fbc91 100644
--- a/lib/btrfsutil/rebuilt_callbacks.go
+++ b/lib/btrfsutil/rebuilt_callbacks.go
@@ -16,8 +16,8 @@ import (
 
 type RebuiltForrestCallbacks interface {
 	AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr)
-	LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
-	LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
+	LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error)
+	LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error)
 }
 
 type RebuiltForrestExtendedCallbacks interface {
@@ -32,21 +32,21 @@ type noopRebuiltForrestCallbacks struct {
 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) {
+func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, err error) {
 	rootTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID)
 	if err != nil {
-		return 0, btrfsitem.Root{}, false
+		return 0, btrfsitem.Root{}, err
 	}
 	item, err := rootTree.TreeSearch(ctx, btrfstree.SearchRootItem(tree))
 	if err != nil {
-		return 0, btrfsitem.Root{}, false
+		return 0, btrfsitem.Root{}, err
 	}
 	defer item.Body.Free()
 	switch itemBody := item.Body.(type) {
 	case *btrfsitem.Root:
-		return btrfsprim.Generation(item.Key.Offset), *itemBody, true
+		return btrfsprim.Generation(item.Key.Offset), *itemBody, nil
 	case *btrfsitem.Error:
-		return 0, btrfsitem.Root{}, false
+		return 0, btrfsitem.Root{}, itemBody.Err
 	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.
@@ -54,22 +54,22 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 	}
 }
 
-func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) {
 	uuidTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.UUID_TREE_OBJECTID)
 	if err != nil {
-		return 0, false
+		return 0, err
 	}
 	tgt := btrfsitem.UUIDToKey(uuid)
 	item, err := uuidTree.TreeLookup(ctx, tgt)
 	if err != nil {
-		return 0, false
+		return 0, err
 	}
 	defer item.Body.Free()
 	switch itemBody := item.Body.(type) {
 	case *btrfsitem.UUIDMap:
-		return itemBody.ObjID, true
+		return itemBody.ObjID, nil
 	case *btrfsitem.Error:
-		return 0, false
+		return 0, itemBody.Err
 	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.
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 900e725..79d8beb 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -212,19 +212,24 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI
 		sb, _ := ts.Superblock()
 		ts.trees[treeID].Root = sb.BlockGroupRoot
 	default:
-		rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID)
-		if !ok {
-			ts.trees[treeID].rootErr = btrfstree.ErrNoTree
+		rootOff, rootItem, err := ts.cb.LookupRoot(ctx, treeID)
+		if err != nil {
+			ts.trees[treeID].rootErr = fmt.Errorf("tree %s: %w: %s",
+				treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), btrfstree.ErrNoTree, err)
 			return
 		}
 		ts.trees[treeID].Root = rootItem.ByteNr
 		ts.trees[treeID].UUID = rootItem.UUID
 		if rootItem.ParentUUID != (btrfsprim.UUID{}) {
 			ts.trees[treeID].ParentGen = rootOff
-			parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
-			if !ok {
-				if !ts.laxAncestors {
-					ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID)
+			parentID, err := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
+			if err != nil {
+				err := fmt.Errorf("tree %s: failed to look up UUID: %v: %w",
+					treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), rootItem.ParentUUID, err)
+				if ts.laxAncestors {
+					ts.trees[treeID].parentErr = err
+				} else {
+					ts.trees[treeID].rootErr = err
 				}
 				return
 			}
@@ -235,7 +240,8 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI
 				ts.trees[treeID].ancestorLoop = true
 				return
 			case !ts.laxAncestors && ts.trees[treeID].Parent.rootErr != nil:
-				ts.trees[treeID].rootErr = fmt.Errorf("failed to rebuild parent tree: %v: %w", parentID, ts.trees[treeID].Parent.rootErr)
+				ts.trees[treeID].rootErr = fmt.Errorf("tree %s: failed to rebuild parent: %w",
+					treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), ts.trees[treeID].Parent.rootErr)
 				return
 			}
 		}
diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go
index 8bbb50a..bb7b698 100644
--- a/lib/btrfsutil/rebuilt_forrest_test.go
+++ b/lib/btrfsutil/rebuilt_forrest_test.go
@@ -13,14 +13,15 @@ import (
 
 	"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"
 )
 
 type rebuiltForrestCallbacks struct {
 	addedItem  func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
 	addedRoot  func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr)
-	lookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
-	lookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
+	lookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error)
+	lookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error)
 }
 
 func (cbs rebuiltForrestCallbacks) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
@@ -31,11 +32,11 @@ func (cbs rebuiltForrestCallbacks) AddedRoot(ctx context.Context, tree btrfsprim
 	cbs.addedRoot(ctx, tree, root)
 }
 
-func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) {
 	return cbs.lookupRoot(ctx, tree)
 }
 
-func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) {
 	return cbs.lookupUUID(ctx, uuid)
 }
 
@@ -84,25 +85,25 @@ func TestRebuiltTreeCycles(t *testing.T) {
 		addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
 			// do nothing
 		},
-		lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+		lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) {
 			for _, root := range roots {
 				if root.ID == tree {
 					return root.ParentGen, btrfsitem.Root{
 						Generation: 2000,
 						UUID:       root.UUID,
 						ParentUUID: root.ParentUUID,
-					}, true
+					}, nil
 				}
 			}
-			return 0, btrfsitem.Root{}, false
+			return 0, btrfsitem.Root{}, btrfstree.ErrNoItem
 		},
-		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) {
 			for _, root := range roots {
 				if root.UUID == uuid {
-					return root.ID, true
+					return root.ID, nil
 				}
 			}
-			return 0, false
+			return 0, btrfstree.ErrNoItem
 		},
 	}
 
@@ -193,10 +194,10 @@ func TestRebuiltTreeParentErr(t *testing.T) {
 		addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
 			// do nothing
 		},
-		lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+		lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) {
 			if tree == 304 {
 				// Force a fault.
-				return 0, btrfsitem.Root{}, false
+				return 0, btrfsitem.Root{}, btrfstree.ErrNoItem
 			}
 			for _, root := range roots {
 				if root.ID == tree {
@@ -204,18 +205,18 @@ func TestRebuiltTreeParentErr(t *testing.T) {
 						Generation: 2000,
 						UUID:       root.UUID,
 						ParentUUID: root.ParentUUID,
-					}, true
+					}, nil
 				}
 			}
-			return 0, btrfsitem.Root{}, false
+			return 0, btrfsitem.Root{}, btrfstree.ErrNoItem
 		},
-		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) {
 			for _, root := range roots {
 				if root.UUID == uuid {
-					return root.ID, true
+					return root.ID, nil
 				}
 			}
-			return 0, false
+			return 0, btrfstree.ErrNoItem
 		},
 	}
 
@@ -224,7 +225,7 @@ func TestRebuiltTreeParentErr(t *testing.T) {
 		rfs := NewRebuiltForrest(nil, Graph{}, cbs, false)
 
 		tree, err := rfs.RebuiltTree(ctx, 305)
-		assert.EqualError(t, err, `failed to rebuild parent tree: 304: tree does not exist`)
+		assert.EqualError(t, err, `tree 305: failed to rebuild parent: tree 304: tree does not exist: item does not exist`)
 		assert.Nil(t, tree)
 	})
 
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 3036938..97308a3 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -10,6 +10,7 @@ import (
 	"sync"
 	"time"
 
+	"github.com/datawire/dlib/derror"
 	"github.com/datawire/dlib/dlog"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
@@ -34,6 +35,7 @@ type RebuiltTree struct {
 	Root      btrfsvol.LogicalAddr
 	Parent    *RebuiltTree
 	ParentGen btrfsprim.Generation // offset of this tree's root item
+	parentErr error
 	forrest   *RebuiltForrest
 
 	// mutable
@@ -44,7 +46,7 @@ type RebuiltTree struct {
 
 	Roots containers.Set[btrfsvol.LogicalAddr]
 
-	// There are 3 more mutable "members" that are protected by
+	// There are 4 more mutable "members" that are protected by
 	// `mu`; but they live in a shared Cache.  They are all
 	// derived from tree.Roots, which is why it's OK if they get
 	// evicted.
@@ -52,12 +54,14 @@ type RebuiltTree struct {
 	//  1. tree.acquireNodeIndex()             = tree.forrest.nodeIndex.Acquire(tree.ID)
 	//  2. tree.RebuiltAcquireItems()          = tree.forrest.incItems.Acquire(tree.ID)
 	//  3. tree.RebuiltAcquirePotentialItems() = tree.forrest.excItems.Acquire(tree.ID)
+	//  4. tree.addErrs()                      = tree.forrest.errors.Acquire(tree.ID)
 }
 
 type rebuiltSharedCache struct {
 	nodeIndex containers.Cache[btrfsprim.ObjID, rebuiltNodeIndex]
 	incItems  containers.Cache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]]
 	excItems  containers.Cache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]]
+	errors    containers.Cache[btrfsprim.ObjID, containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]]
 }
 
 func makeRebuiltSharedCache(forrest *RebuiltForrest) rebuiltSharedCache {
@@ -80,6 +84,12 @@ func makeRebuiltSharedCache(forrest *RebuiltForrest) rebuiltSharedCache {
 			func(ctx context.Context, treeID btrfsprim.ObjID, excItems *containers.SortedMap[btrfsprim.Key, ItemPtr]) {
 				*excItems = forrest.trees[treeID].uncachedExcItems(ctx)
 			}))
+	ret.errors = containers.NewARCache[btrfsprim.ObjID, containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]](
+		textui.Tunable(8),
+		containers.SourceFunc[btrfsprim.ObjID, containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]](
+			func(ctx context.Context, treeID btrfsprim.ObjID, errs *containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]) {
+				*errs = forrest.trees[treeID].uncachedErrors(ctx)
+			}))
 	return ret
 }
 
@@ -386,6 +396,249 @@ func (tree *RebuiltTree) uncachedItems(ctx context.Context, inc bool) containers
 	return index
 }
 
+// evictable member 4: .addErrs() //////////////////////////////////////////////////////////////////////////////////////
+
+type rebuiltTreeError struct {
+	Min  btrfsprim.Key
+	Max  btrfsprim.Key
+	Node btrfsvol.LogicalAddr
+	Err  error
+}
+
+func (e rebuiltTreeError) Error() string {
+	return fmt.Sprintf("keys %v-%v: node@%v: %v", e.Min, e.Max, e.Node, e.Err)
+}
+
+func (e rebuiltTreeError) Unwrap() error {
+	return e.Err
+}
+
+type errorStats struct {
+	Nodes   textui.Portion[int]
+	NumErrs int
+}
+
+func (s errorStats) String() string {
+	return textui.Sprintf("%v (%v errs)",
+		s.Nodes, s.NumErrs)
+}
+
+func (tree *RebuiltTree) uncachedErrors(ctx context.Context) containers.IntervalTree[btrfsprim.Key, rebuiltTreeError] {
+	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-errors", fmt.Sprintf("tree=%v", tree.ID))
+
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+
+	errs := containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]{
+		MinFn: func(err rebuiltTreeError) btrfsprim.Key {
+			return err.Min
+		},
+		MaxFn: func(err rebuiltTreeError) btrfsprim.Key {
+			return err.Max
+		},
+	}
+
+	nodeIndex := tree.acquireNodeIndex(ctx)
+	defer tree.releaseNodeIndex()
+
+	nodesToProcess := make(containers.Set[btrfsvol.LogicalAddr], len(nodeIndex.nodeToRoots))
+	for node := range nodeIndex.nodeToRoots {
+		if !maps.HaveAnyKeysInCommon(nodeIndex.nodeToRoots[node], tree.Roots) {
+			continue
+		}
+		nodesToProcess.Insert(node)
+		for _, kp := range tree.forrest.graph.EdgesFrom[node] {
+			nodesToProcess.Insert(kp.ToNode)
+		}
+	}
+	for root := range tree.Roots {
+		// For BadNodes that are roots.
+		nodesToProcess.Insert(root)
+	}
+
+	var stats errorStats
+	stats.Nodes.D = len(nodesToProcess)
+	progressWriter := textui.NewProgress[errorStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	progressWriter.Set(stats)
+
+	var kps []*GraphEdge
+	for i, node := range maps.SortedKeys(nodesToProcess) {
+		stats.Nodes.N = i
+		progressWriter.Set(stats)
+
+		// `node` may either be in the tree, or just pointed
+		// to by a different node in the tree.  Decide whether
+		// it's in the tree, and gather all of the
+		// key-pointers in the tree that point to it.
+		inTree := maps.HaveAnyKeysInCommon(nodeIndex.nodeToRoots[node], tree.Roots)
+		kps = kps[:0]
+		for _, kp := range tree.forrest.graph.EdgesTo[node] {
+			if !maps.HaveAnyKeysInCommon(nodeIndex.nodeToRoots[kp.FromNode], tree.Roots) {
+				continue
+			}
+			kps = append(kps, kp)
+		}
+
+		// Look at all key-pointers to decide what our
+		// expectations are.
+		var (
+			expLevel  = make(containers.Set[uint8], len(kps))
+			expGen    = make(containers.Set[btrfsprim.Generation], len(kps))
+			expTree   = make(containers.Set[btrfsprim.ObjID], len(kps))
+			loMinItem = btrfsprim.MaxKey // lowest kp.ToKey seen
+			hiMinItem = btrfsprim.Key{}  // highest kp.ToKey seen
+			loMaxItem = btrfsprim.MaxKey // lowest nodeToRoots[node][root] seen
+			hiMaxItem = btrfsprim.Key{}  // highest nodeToRoots[node][root] seen
+		)
+		expTree.Insert(tree.ID)
+		if len(kps) == 0 {
+			// This is a root.
+			loMinItem = btrfsprim.Key{}
+			hiMaxItem = btrfsprim.MaxKey
+		} else {
+			// expLevel, expGen, loMinItem, hiMinItem,
+			for _, kp := range kps {
+				expLevel.Insert(kp.ToLevel)
+				expGen.Insert(kp.ToGeneration)
+				expTree.Insert(kp.FromTree)
+				if kp.ToKey.Compare(loMinItem) < 0 {
+					loMinItem = kp.ToKey
+				}
+				if kp.ToKey.Compare(hiMinItem) > 0 {
+					hiMinItem = kp.ToKey
+				}
+			}
+			// loMaxItem, hiMaxItem
+			if !inTree {
+				for _, kp := range kps {
+					for root, rootInfo := range nodeIndex.nodeToRoots[kp.FromNode] {
+						if !tree.Roots.Has(root) {
+							continue
+						}
+						if kp.FromSlot+1 < len(tree.forrest.graph.EdgesFrom[kp.FromNode]) {
+							rootInfo.loMaxItem = tree.forrest.graph.EdgesFrom[kp.FromNode][kp.FromSlot+1].ToKey.Mm()
+							rootInfo.hiMaxItem = rootInfo.loMaxItem
+						}
+						if loMaxItem.Compare(rootInfo.loMaxItem) > 0 {
+							loMaxItem = rootInfo.loMaxItem
+						}
+						if hiMaxItem.Compare(rootInfo.hiMaxItem) < 0 {
+							hiMaxItem = rootInfo.hiMaxItem
+						}
+					}
+				}
+			} else {
+				// As an optimization, we can look at this node's rootInfo directly.
+				// This should be equivalent to the above loop for `!inTree`, but is
+				// faster.
+				for root, rootInfo := range nodeIndex.nodeToRoots[node] {
+					if !tree.Roots.Has(root) {
+						continue
+					}
+					if loMaxItem.Compare(rootInfo.loMaxItem) > 0 {
+						loMaxItem = rootInfo.loMaxItem
+					}
+					if hiMaxItem.Compare(rootInfo.hiMaxItem) < 0 {
+						hiMaxItem = rootInfo.hiMaxItem
+					}
+				}
+			}
+		}
+
+		// Assemble all of that in to a btrfstree.NodeExpectations.
+		var nodeErrs derror.MultiError
+		exp := btrfstree.NodeExpectations{
+			LAddr:   containers.OptionalValue(node),
+			MinItem: containers.OptionalValue(hiMinItem),
+			MaxItem: containers.OptionalValue(loMaxItem),
+			Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error {
+				byStr := make(map[string]error)
+				for _, kpTree := range maps.SortedKeys(expTree) {
+					if err := btrfstree.CheckOwner(ctx, tree.forrest, kpTree, owner, gen); err != nil {
+						byStr[err.Error()] = err
+					}
+				}
+				if len(byStr) > 0 {
+					byPos := make(derror.MultiError, 0, len(byStr))
+					for _, str := range maps.SortedKeys(byStr) {
+						byPos = append(byPos, byStr[str])
+					}
+					return byPos
+				}
+				return nil
+			},
+		}
+		switch len(expLevel) {
+		case 0:
+			// do nothing
+		case 1:
+			exp.Level = containers.OptionalValue(expLevel.TakeOne())
+		default:
+			nodeErrs = append(nodeErrs,
+				fmt.Errorf("multiple KPs request different node levels: %v (actual: %v)",
+					maps.SortedKeys(expLevel), tree.forrest.graph.Nodes[node].Level))
+		}
+		switch len(expGen) {
+		case 0:
+			// do nothing
+		case 1:
+			exp.Generation = containers.OptionalValue(expGen.TakeOne())
+		default:
+			nodeErrs = append(nodeErrs,
+				fmt.Errorf("multiple KPs request different node generations: %v (actual: %v)",
+					maps.SortedKeys(expGen), tree.forrest.graph.Nodes[node].Generation))
+		}
+
+		// Check those expectations.
+		if hiMaxItem.Compare(loMinItem) < 0 {
+			nodeErrs = append(nodeErrs,
+				fmt.Errorf("loMinItem:%v > hiMaxItem:%v", loMinItem, hiMaxItem))
+			loMinItem = btrfsprim.Key{}
+			hiMaxItem = btrfsprim.MaxKey
+		}
+		if err := tree.forrest.graph.BadNodes[node]; err != nil {
+			nodeErrs = append(nodeErrs, err)
+		} else if err := tree.forrest.graph.Nodes[node].CheckExpectations(tree.forrest.graph, exp); err != nil {
+			nodeErrs = append(nodeErrs, err)
+		}
+
+		if len(nodeErrs) > 0 {
+			errs.Insert(rebuiltTreeError{
+				Min:  loMinItem,
+				Max:  hiMaxItem,
+				Node: node,
+				Err:  nodeErrs,
+			})
+
+			stats.NumErrs++
+			progressWriter.Set(stats)
+		}
+	}
+	stats.Nodes.N = stats.Nodes.D
+	progressWriter.Set(stats)
+	progressWriter.Done()
+
+	return errs
+}
+
+func (tree *RebuiltTree) addErrs(ctx context.Context, fn func(btrfsprim.Key, uint32) int, err error) error {
+	var errs derror.MultiError
+	tree.forrest.errors.Acquire(ctx, tree.ID).Subrange(
+		func(k btrfsprim.Key) int { return fn(k, 0) },
+		func(v rebuiltTreeError) bool {
+			errs = append(errs, v)
+			return true
+		})
+	tree.forrest.errors.Release(tree.ID)
+	if len(errs) == 0 {
+		return err
+	}
+	if err != nil {
+		errs = append(errs, err)
+	}
+	return errs
+}
+
 // main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
 
 func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
@@ -496,6 +749,7 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 	tree.Roots.Insert(rootNode)
 	tree.forrest.incItems.Delete(tree.ID) // force re-gen
 	tree.forrest.excItems.Delete(tree.ID) // force re-gen
+	tree.forrest.errors.Delete(tree.ID)   // force re-gen
 
 	if shouldFlush {
 		tree.forrest.flushNegativeCache(ctx)
@@ -506,11 +760,12 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 // RebuiltCOWDistance returns how many COW-snapshots down the 'tree'
 // is from the 'parent'.
 func (tree *RebuiltTree) RebuiltCOWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
+	root := tree.ancestorRoot
 	for {
 		if parentID == tree.ID {
 			return dist, true
 		}
-		if tree.Parent == nil {
+		if tree.Parent == nil || tree.ID == root {
 			return 0, false
 		}
 		tree = tree.Parent
@@ -552,15 +807,17 @@ var _ btrfstree.Tree = (*RebuiltTree)(nil)
 
 // TreeParentID implements btrfstree.Tree.
 func (tree *RebuiltTree) TreeParentID(_ context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) {
-	if tree.Parent == nil {
+	switch {
+	case tree.parentErr != nil:
+		return 0, 0, tree.parentErr
+	case tree.Parent == nil:
 		return 0, 0, nil
+	default:
+		return tree.Parent.ID, tree.ParentGen, nil
 	}
-	return tree.Parent.ID, tree.ParentGen, nil
 }
 
 // TreeLookup implements btrfstree.Tree.
-//
-// BUG(lukeshu): Errors in the tree are not ever returned.
 func (tree *RebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btrfstree.Item, error) {
 	return tree.TreeSearch(ctx, btrfstree.SearchExactKey(key))
 }
@@ -568,16 +825,19 @@ func (tree *RebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btr
 // TreeSearch implements btrfstree.Tree.  It is a thin wrapper around
 // tree.RebuiltItems(ctx).Search (to do the search) and
 // tree.TreeLookup (to read item bodies).
-//
-// BUG(lukeshu): Errors in the tree are not ever returned.
 func (tree *RebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
+	tree.forrest.commitTrees(ctx, tree.ID)
+	tree.initRoots(ctx)
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+
 	_, ptr, ok := tree.RebuiltAcquireItems(ctx).Search(func(_ btrfsprim.Key, ptr ItemPtr) int {
 		straw := tree.forrest.graph.Nodes[ptr.Node].Items[ptr.Slot]
 		return searcher.Search(straw.Key, straw.Size)
 	})
 	tree.RebuiltReleaseItems()
 	if !ok {
-		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, btrfstree.ErrNoItem)
+		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(ctx, searcher.Search, btrfstree.ErrNoItem))
 	}
 	return tree.forrest.readItem(ctx, ptr), nil
 }
@@ -585,26 +845,32 @@ func (tree *RebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.Tree
 // TreeRange implements btrfstree.Tree.  It is a thin wrapper around
 // tree.RebuiltItems(ctx).Range (to do the iteration) and
 // tree.TreeLookup (to read item bodies).
-//
-// BUG(lukeshu): Errors in the tree are not ever returned.
 func (tree *RebuiltTree) TreeRange(ctx context.Context, handleFn func(btrfstree.Item) bool) error {
+	tree.forrest.commitTrees(ctx, tree.ID)
+	tree.initRoots(ctx)
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+
 	tree.RebuiltAcquireItems(ctx).Range(func(_ btrfsprim.Key, ptr ItemPtr) bool {
 		return handleFn(tree.forrest.readItem(ctx, ptr))
 	})
 	tree.RebuiltReleaseItems()
-	return nil
+	return tree.addErrs(ctx, func(btrfsprim.Key, uint32) int { return 0 }, nil)
 }
 
 // TreeSubrange implements btrfstree.Tree.  It is a thin wrapper
 // around tree.RebuiltItems(ctx).Subrange (to do the iteration) and
 // tree.TreeLookup (to read item bodies).
-//
-// BUG(lukeshu): Errors in the tree are not ever returned.
 func (tree *RebuiltTree) TreeSubrange(ctx context.Context,
 	min int,
 	searcher btrfstree.TreeSearcher,
 	handleFn func(btrfstree.Item) bool,
 ) error {
+	tree.forrest.commitTrees(ctx, tree.ID)
+	tree.initRoots(ctx)
+	tree.mu.RLock()
+	defer tree.mu.RUnlock()
+
 	var cnt int
 	tree.RebuiltAcquireItems(ctx).Subrange(
 		func(_ btrfsprim.Key, ptr ItemPtr) int {
@@ -618,8 +884,13 @@ func (tree *RebuiltTree) TreeSubrange(ctx context.Context,
 	)
 	tree.RebuiltReleaseItems()
 
+	var err error
 	if cnt < min {
-		return btrfstree.ErrNoItem
+		err = btrfstree.ErrNoItem
+	}
+	err = tree.addErrs(ctx, searcher.Search, err)
+	if err != nil {
+		return fmt.Errorf("items with %s: %w", searcher, err)
 	}
 
 	return nil
diff --git a/lib/textui/log.go b/lib/textui/log.go
index 25bb4be..a26dd5f 100644
--- a/lib/textui/log.go
+++ b/lib/textui/log.go
@@ -338,12 +338,14 @@ func fieldOrd(key string) int {
 
 	// btrfsutil.RebuiltForrest ////////////////////////////////////////////
 	case "btrfs.util.rebuilt-forrest.add-tree":
-		return -7
+		return -8
 	case "btrfs.util.rebuilt-forrest.add-tree.want.key":
-		return -6
+		return -7
 	case "btrfs.util.rebuilt-forrest.add-tree.want.reason":
-		return -5
+		return -6
 	case "btrfs.util.rebuilt-tree.add-root":
+		return -5
+	case "btrfs.util.rebuilt-tree.index-errors":
 		return -4
 	case "btrfs.util.rebuilt-tree.index-inc-items":
 		return -3