btrfsutil: RebuiltForrest.RebuiltTree(): Return errors

8 files changed, 281 insertions, 66 deletions

diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
index d1ccfac..7e2e49f 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
@@ -159,7 +159,7 @@ func (o *rebuilder) processTreeQueue(ctx context.Context) error {
 		}
 		// This will call o.AddedItem as nescessary, which
 		// inserts to o.addedItemQueue.
-		_ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID)
+		_, _ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID)
 	}
 
 	return nil
@@ -197,7 +197,7 @@ func (o *rebuilder) processAddedItemQueue(ctx context.Context) error {
 
 	for _, key := range queue {
 		ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.settle.item", key)
-		tree := o.rebuilt.RebuiltTree(ctx, key.TreeID)
+		tree := discardErr(o.rebuilt.RebuiltTree(ctx, key.TreeID))
 		incPtr, ok := tree.RebuiltAcquireItems(ctx).Load(key.Key)
 		tree.RebuiltReleaseItems()
 		if !ok {
@@ -333,9 +333,8 @@ func (o *rebuilder) sortSettledItemQueue(ctx context.Context, unorderedQueue con
 	// EXTENT_TREE; if that fails, then there can't be any items
 	// in the EXTENT_TREE for us to have to handle special, and
 	// all of the following code will fall through common-path.
-	extentTree := o.rebuilt.RebuiltTree(ctx, btrfsprim.EXTENT_TREE_OBJECTID)
 	var extentItems *containers.SortedMap[btrfsprim.Key, btrfsutil.ItemPtr]
-	if extentTree != nil {
+	if extentTree, err := o.rebuilt.RebuiltTree(ctx, btrfsprim.EXTENT_TREE_OBJECTID); err == nil {
 		extentItems = extentTree.RebuiltAcquireItems(ctx)
 		defer extentTree.RebuiltReleaseItems()
 	}
@@ -416,7 +415,7 @@ func (o *rebuilder) processSettledItemQueue(ctx context.Context) error {
 			ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.process.item", key)
 			item := keyAndBody{
 				itemToVisit: key,
-				Body:        o.rebuilt.RebuiltTree(ctx, key.TreeID).ReadItem(ctx, key.Key),
+				Body:        discardErr(o.rebuilt.RebuiltTree(ctx, key.TreeID)).ReadItem(ctx, key.Key),
 			}
 			if key.TreeID == btrfsprim.EXTENT_TREE_OBJECTID &&
 				(key.ItemType == btrfsprim.EXTENT_ITEM_KEY || key.ItemType == btrfsprim.METADATA_ITEM_KEY) {
@@ -503,7 +502,7 @@ func (o *rebuilder) processAugmentQueue(ctx context.Context) error {
 			}
 			// This will call o.AddedItem as nescessary, which
 			// inserts to o.addedItemQueue.
-			o.rebuilt.RebuiltTree(ctx, treeID).RebuiltAddRoot(ctx, nodeAddr)
+			discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltAddRoot(ctx, nodeAddr)
 			progress.N++
 			progressWriter.Set(progress)
 		}
@@ -550,7 +549,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob
 		} else {
 			choices[choice] = ChoiceInfo{
 				Count:      1,
-				Distance:   discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
+				Distance:   discardOK(discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
 				Generation: o.scan.Graph.Nodes[choice].Generation,
 			}
 		}
@@ -564,7 +563,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob
 			} else {
 				choices[choice] = ChoiceInfo{
 					Count:      1,
-					Distance:   discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
+					Distance:   discardOK(discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)),
 					Generation: o.scan.Graph.Nodes[choice].Generation,
 				}
 			}
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
index 0c52556..e227cc7 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
@@ -51,7 +51,7 @@ func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID)
 		o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
 		return 0, btrfsitem.Root{}, false
 	}
-	itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey)
+	itemBody := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).ReadItem(ctx, foundKey)
 	defer itemBody.Free()
 	switch itemBody := itemBody.(type) {
 	case *btrfsitem.Root:
@@ -77,7 +77,7 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
 		o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID)
 		return 0, false
 	}
-	itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key())
+	itemBody := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).ReadItem(ctx, wantKey.Key.Key())
 	defer itemBody.Free()
 	switch itemBody := itemBody.(type) {
 	case *btrfsitem.UUIDMap:
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
index 0526e93..382d88b 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go
@@ -43,8 +43,8 @@ func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfspri
 }
 
 func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsprim.Key, ok bool) {
-	tree := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
+	if err != nil {
 		o.enqueueRetry(wantKey.TreeID)
 		return btrfsprim.Key{}, false
 	}
@@ -98,8 +98,8 @@ func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfs
 }
 
 func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool) {
-	tree := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)
+	if err != nil {
 		o.enqueueRetry(wantKey.TreeID)
 		return false
 	}
@@ -144,8 +144,8 @@ func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID
 	}
 	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
 
-	tree := o.rebuilt.RebuiltTree(ctx, treeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, treeID)
+	if err != nil {
 		o.enqueueRetry(treeID)
 		return
 	}
@@ -273,8 +273,8 @@ func (o graphCallbacks) _wantRange(
 	ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
 	wantKey.Key.OffsetType = offsetRange
 
-	tree := o.rebuilt.RebuiltTree(ctx, treeID)
-	if tree == nil {
+	tree, err := o.rebuilt.RebuiltTree(ctx, treeID)
+	if err != nil {
 		o.enqueueRetry(treeID)
 		return
 	}
@@ -389,7 +389,7 @@ func (o graphCallbacks) WantCSum(ctx context.Context, reason string, inodeTree,
 		o.enqueueRetry(inodeTree)
 		return
 	}
-	tree := o.rebuilt.RebuiltTree(inodeCtx, inodeTree)
+	tree := discardErr(o.rebuilt.RebuiltTree(inodeCtx, inodeTree))
 	inodePtr, ok := tree.RebuiltAcquireItems(inodeCtx).Load(inodeWant.Key.Key())
 	tree.RebuiltReleaseItems()
 	if !ok {
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/util.go b/cmd/btrfs-rec/inspect/rebuildtrees/util.go
index 842fb55..ee06394 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/util.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/util.go
@@ -19,3 +19,7 @@ func roundUp[T constraints.Integer](n, d T) T {
 func discardOK[T any](val T, _ bool) T {
 	return val
 }
+
+func discardErr[T any](val T, _ error) T {
+	return val
+}
diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go
index 41fe7f1..fdc826c 100644
--- a/lib/btrfsutil/rebuilt_callbacks.go
+++ b/lib/btrfsutil/rebuilt_callbacks.go
@@ -32,8 +32,8 @@ func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, b
 }
 
 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 {
+	rootTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+	if err != nil {
 		return 0, btrfsitem.Root{}, false
 	}
 	tgt := btrfsprim.Key{
@@ -63,8 +63,8 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 }
 
 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 {
+	uuidTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+	if err != nil {
 		return 0, false
 	}
 	tgt := btrfsitem.UUIDToKey(uuid)
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 4249396..a4ae727 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -6,6 +6,7 @@ package btrfsutil
 
 import (
 	"context"
+	"fmt"
 
 	"github.com/datawire/dlib/dlog"
 
@@ -13,6 +14,7 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
@@ -98,42 +100,57 @@ func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallba
 }
 
 // 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.
 //
 // 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 {
+func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) (*RebuiltTree, error) {
 	ctx = ts.treesMu.Lock(ctx)
 	defer ts.treesMu.Unlock()
-	if !ts.addTree(ctx, treeID, nil) {
-		return nil
+	ts.rebuildTree(ctx, treeID, nil)
+	tree := ts.trees[treeID]
+	if tree.ancestorLoop && tree.rootErr == nil {
+		var loop []btrfsprim.ObjID
+		for ancestor := tree; true; ancestor = ancestor.Parent {
+			loop = append(loop, ancestor.ID)
+			if slices.Contains(ancestor.ID, loop[:len(loop)-1]) {
+				break
+			}
+		}
+		tree.rootErr = fmt.Errorf("loop detected: %v", loop)
 	}
-	return ts.trees[treeID]
+	if tree.rootErr != nil {
+		return nil, tree.rootErr
+	}
+	return tree, nil
 }
 
-func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
-	if tree, ok := ts.trees[treeID]; ok {
-		return tree != nil
+func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) {
+	loop := false
+	if maps.HasKey(ts.trees, treeID) {
+		loop = slices.Contains(treeID, stack)
+		if !loop {
+			return
+		}
 	}
+
+	stack = append(stack, treeID)
+	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack)
 	defer func() {
-		if !ok {
-			// Store a negative cache of this.  tree.RebuiltAddRoot() for the ROOT or
-			// UUID trees will call .flushNegativeCache().
-			ts.trees[treeID] = nil
+		if ts.trees[treeID].rootErr != nil {
+			dlog.Errorf(ctx, "failed to add tree: %v", ts.trees[treeID].rootErr)
 		}
 	}()
-	stack = append(stack, treeID)
-	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack)
 	dlog.Info(ctx, "adding tree...")
-	if slices.Contains(treeID, stack[:len(stack)-1]) {
-		dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack)
-		return false
+
+	if loop {
+		ts.trees[treeID].ancestorLoop = true
+		dlog.Error(ctx, "loop detected")
+		return
 	}
 
-	tree := &RebuiltTree{
+	ts.trees[treeID] = &RebuiltTree{
 		ID:      treeID,
 		Roots:   make(containers.Set[btrfsvol.LogicalAddr]),
 		forrest: ts,
@@ -153,48 +170,43 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
 		sb, _ := ts.inner.Superblock()
 		root = sb.BlockGroupRoot
 	default:
-		if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) {
-			dlog.Error(ctx, "failed to add tree: add ROOT_TREE")
-			return false
-		}
 		rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID)
 		if !ok {
-			dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM")
-			return false
+			ts.trees[treeID].rootErr = fmt.Errorf("failed to look up ROOT_ITEM")
+			return
 		}
 		root = rootItem.ByteNr
-		tree.UUID = rootItem.UUID
+		ts.trees[treeID].UUID = rootItem.UUID
 		if rootItem.ParentUUID != (btrfsprim.UUID{}) {
-			tree.ParentGen = rootOff
-			if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
-				return false
-			}
+			ts.trees[treeID].ParentGen = rootOff
 			parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
 			if !ok {
-				dlog.Errorf(ctx, "failed to add tree: lookup UUID %v", rootItem.ParentUUID)
-				return false
+				ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID)
+				return
 			}
-			if !ts.addTree(ctx, parentID, stack) {
-				dlog.Errorf(ctx, "failed to add tree: add parent tree %v", parentID)
-				return false
+			ts.rebuildTree(ctx, parentID, stack)
+			ts.trees[treeID].Parent = ts.trees[parentID]
+			switch {
+			case ts.trees[treeID].Parent.ancestorLoop:
+				ts.trees[treeID].ancestorLoop = true
+				return
+			case 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)
+				return
 			}
-			tree.Parent = ts.trees[parentID]
 		}
 	}
 
-	ts.trees[treeID] = tree
 	if root != 0 {
-		tree.RebuiltAddRoot(ctx, root)
+		ts.trees[treeID].RebuiltAddRoot(ctx, root)
 	}
-
-	return true
 }
 
 func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
 	_ = ts.treesMu.Lock(ctx)
 	defer ts.treesMu.Unlock()
 	for treeID, tree := range ts.trees {
-		if tree == nil {
+		if tree.rootErr != nil || tree.ancestorLoop {
 			delete(ts.trees, treeID)
 		}
 	}
@@ -210,7 +222,7 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob
 	defer ts.treesMu.Unlock()
 	ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
 	for treeID, tree := range ts.trees {
-		if tree != nil && len(tree.Roots) > 0 {
+		if len(tree.Roots) > 0 {
 			ret[treeID] = tree.Roots
 		}
 	}
diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go
new file mode 100644
index 0000000..6f80eff
--- /dev/null
+++ b/lib/btrfsutil/rebuilt_forrest_test.go
@@ -0,0 +1,193 @@
+// Copyright (C) 2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsutil
+
+import (
+	"context"
+	"testing"
+
+	"github.com/datawire/dlib/dlog"
+	"github.com/stretchr/testify/assert"
+
+	"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/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)
+}
+
+func (cbs rebuiltForrestCallbacks) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+	cbs.addedItem(ctx, tree, key)
+}
+
+func (cbs rebuiltForrestCallbacks) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+	cbs.addedRoot(ctx, tree, root)
+}
+
+func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+	return cbs.lookupRoot(ctx, tree)
+}
+
+func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+	return cbs.lookupUUID(ctx, uuid)
+}
+
+func TestRebuiltTreeCycles(t *testing.T) {
+	t.Parallel()
+
+	ctx := dlog.NewTestContext(t, true)
+
+	type mockRoot struct {
+		ID         btrfsprim.ObjID
+		UUID       btrfsprim.UUID
+		ParentUUID btrfsprim.UUID
+		ParentGen  btrfsprim.Generation
+	}
+	roots := []mockRoot{
+		{
+			ID:         306,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000006"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentGen:  1005,
+		},
+		{
+			ID:         305,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+			ParentGen:  1004,
+		},
+		{
+			ID:         304,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"),
+			ParentGen:  1003,
+		},
+		{
+			ID:         303,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentGen:  1002,
+		},
+	}
+
+	cbs := rebuiltForrestCallbacks{
+		addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+			// do nothing
+		},
+		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) {
+			for _, root := range roots {
+				if root.ID == tree {
+					return root.ParentGen, btrfsitem.Root{
+						Generation: 2000,
+						UUID:       root.UUID,
+						ParentUUID: root.ParentUUID,
+					}, true
+				}
+			}
+			return 0, btrfsitem.Root{}, false
+		},
+		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+			for _, root := range roots {
+				if root.UUID == uuid {
+					return root.ID, true
+				}
+			}
+			return 0, false
+		},
+	}
+
+	rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+
+	tree, err := rfs.RebuiltTree(ctx, 306)
+	assert.EqualError(t, err, `loop detected: [306 305 304 303 305]`)
+	assert.Nil(t, tree)
+
+	assert.NotNil(t, rfs.trees[305])
+	tree, err = rfs.RebuiltTree(ctx, 305)
+	assert.EqualError(t, err, `loop detected: [305 304 303 305]`)
+	assert.Nil(t, tree)
+
+	assert.NotNil(t, rfs.trees[304])
+	tree, err = rfs.RebuiltTree(ctx, 304)
+	assert.EqualError(t, err, `loop detected: [304 303 305 304]`)
+	assert.Nil(t, tree)
+
+	assert.NotNil(t, rfs.trees[303])
+	tree, err = rfs.RebuiltTree(ctx, 303)
+	assert.EqualError(t, err, `loop detected: [303 305 304 303]`)
+	assert.Nil(t, tree)
+}
+
+func TestRebuiltTreeParentErr(t *testing.T) {
+	t.Parallel()
+
+	ctx := dlog.NewTestContext(t, true)
+
+	type mockRoot struct {
+		ID         btrfsprim.ObjID
+		UUID       btrfsprim.UUID
+		ParentUUID btrfsprim.UUID
+		ParentGen  btrfsprim.Generation
+	}
+	roots := []mockRoot{
+		{
+			ID:         305,
+			UUID:       btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+			ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+			ParentGen:  1004,
+		},
+		{
+			ID:   304,
+			UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+		},
+	}
+
+	cbs := rebuiltForrestCallbacks{
+		addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+			// do nothing
+		},
+		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) {
+			if tree == 304 {
+				// Force a fault.
+				return 0, btrfsitem.Root{}, false
+			}
+			for _, root := range roots {
+				if root.ID == tree {
+					return root.ParentGen, btrfsitem.Root{
+						Generation: 2000,
+						UUID:       root.UUID,
+						ParentUUID: root.ParentUUID,
+					}, true
+				}
+			}
+			return 0, btrfsitem.Root{}, false
+		},
+		lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+			for _, root := range roots {
+				if root.UUID == uuid {
+					return root.ID, true
+				}
+			}
+			return 0, false
+		},
+	}
+
+	rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+
+	tree, err := rfs.RebuiltTree(ctx, 305)
+	assert.EqualError(t, err, `failed to rebuild parent tree: 304: failed to look up ROOT_ITEM`)
+	assert.Nil(t, tree)
+}
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index e507851..5d38bb1 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -23,6 +23,10 @@ import (
 
 type RebuiltTree struct {
 	// static
+
+	rootErr      error
+	ancestorLoop bool
+
 	ID        btrfsprim.ObjID
 	UUID      btrfsprim.UUID
 	Parent    *RebuiltTree
@@ -30,8 +34,11 @@ type RebuiltTree struct {
 	forrest   *RebuiltForrest
 
 	// mutable
-	mu    sync.RWMutex
+
+	mu sync.RWMutex
+
 	Roots containers.Set[btrfsvol.LogicalAddr]
+
 	// There are 3 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