Merge branch 'lukeshu/rebuilt-v2-pt2-lax-parents'

8 files changed, 172 insertions, 54 deletions

diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
index 77d56ae..aeb6751 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go
@@ -85,7 +85,7 @@ func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.Logical
 	o := &rebuilder{
 		scan: scanData,
 	}
-	o.rebuilt = btrfsutil.NewRebuiltForrest(fs, scanData.Graph, forrestCallbacks{o})
+	o.rebuilt = btrfsutil.NewRebuiltForrest(fs, scanData.Graph, forrestCallbacks{o}, false)
 	return o, nil
 }
 
diff --git a/cmd/btrfs-rec/main.go b/cmd/btrfs-rec/main.go
index 26857f0..ad768de 100644
--- a/cmd/btrfs-rec/main.go
+++ b/cmd/btrfs-rec/main.go
@@ -224,7 +224,7 @@ func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvo
 				return err
 			}
 
-			rfs = btrfsutil.NewRebuiltForrest(fs, graph, nil)
+			rfs = btrfsutil.NewRebuiltForrest(fs, graph, nil, true)
 		}
 
 		return runE(rfs, nodeList, cmd, args)
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index 6056ae8..b9b9201 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -54,7 +54,7 @@ func (tree *RawTree) walk(ctx context.Context, sb Superblock, path Path, cbs Tre
 	}
 
 	// 001
-	nodeAddr, nodeExp, ok := path.NodeExpectations(ctx, true) // TODO(lukeshu): Consider whether failing open is the right thing here
+	nodeAddr, nodeExp, ok := path.NodeExpectations(ctx)
 	if !ok {
 		return
 	}
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 57669ee..327a39b 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -12,6 +12,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/slices"
 )
 
 // Path is a path from the superblock or a ROOT_ITEM to a node or
@@ -134,9 +135,10 @@ func (path Path) String() string {
 }
 
 func checkOwner(
-	ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID, failOpen bool,
+	ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID,
 	ownerToCheck btrfsprim.ObjID, genToCheck btrfsprim.Generation,
 ) error {
+	var stack []btrfsprim.ObjID
 	for {
 		if ownerToCheck == treeID {
 			return nil
@@ -144,22 +146,22 @@ func checkOwner(
 
 		tree, err := forrest.ForrestLookup(ctx, treeID)
 		if err != nil {
-			if failOpen {
-				return nil
-			}
 			return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
 				ownerToCheck, genToCheck, err)
 		}
 
 		parentID, parentGen, err := tree.TreeParentID(ctx)
 		if err != nil {
-			if failOpen {
-				return nil
-			}
 			return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w",
 				ownerToCheck, genToCheck, err)
 		}
 
+		stack = append(stack, treeID)
+		if slices.Contains(parentID, stack) {
+			// Don't get stuck in an infinite loop if there's a cycle.
+			parentID = 0
+		}
+
 		if parentID == 0 && parentGen == 0 {
 			return fmt.Errorf("owner=%v is not acceptable in this tree",
 				ownerToCheck)
@@ -177,7 +179,7 @@ func checkOwner(
 //
 // `ok` is false if the path is empty or if this Path points to an
 // item rather than a node.
-func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) {
+func (path Path) NodeExpectations(ctx context.Context) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) {
 	if len(path) == 0 {
 		return 0, NodeExpectations{}, false
 	}
@@ -192,7 +194,7 @@ func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvo
 			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, failOpen,
+				return checkOwner(ctx, firstElem.Forrest, lastElem.TreeID,
 					owner, gen)
 			},
 			MinItem: containers.OptionalValue(btrfsprim.Key{}),
@@ -204,7 +206,7 @@ func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvo
 			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, failOpen,
+				return checkOwner(ctx, firstElem.Forrest, lastElem.FromTree,
 					owner, gen)
 			},
 			MinItem: containers.OptionalValue(lastElem.ToMinKey),
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index b03ddc2..a23278c 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -190,7 +190,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O
 	var curNode oldRebuiltNodeInfo
 	cbs := btrfstree.TreeWalkHandler{
 		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
-			nodeAddr, nodeExp, _ := path.NodeExpectations(ctx, false)
+			nodeAddr, nodeExp, _ := path.NodeExpectations(ctx)
 			cacheEntry.Errors.Insert(oldRebuiltTreeError{
 				Min:  nodeExp.MinItem.Val,
 				Max:  nodeExp.MaxItem.Val,
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 019d824..900e725 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -7,6 +7,7 @@ package btrfsutil
 import (
 	"context"
 	"fmt"
+	"sync"
 
 	"github.com/datawire/dlib/dlog"
 
@@ -64,14 +65,18 @@ import (
 // NewRebuiltForrest().
 type RebuiltForrest struct {
 	// static
-	inner btrfs.ReadableFS
-	graph Graph
-	cb    RebuiltForrestCallbacks
+	inner        btrfs.ReadableFS
+	graph        Graph
+	cb           RebuiltForrestCallbacks
+	laxAncestors bool
 
 	// mutable
 
-	treesMu nestedMutex
-	trees   map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
+	treesMu         nestedMutex
+	trees           map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
+	commitTreesOnce sync.Once
+	treesCommitted  bool // must hold .treesMu to access
+	treesCommitter  btrfsprim.ObjID
 
 	rebuiltSharedCache
 }
@@ -81,11 +86,23 @@ type RebuiltForrest struct {
 // The `cb` RebuiltForrestCallbacks may be nil.  If `cb` also
 // implements RebuiltForrestExtendedCallbacks, then a series of
 // .AddedItem() calls will be made before each call to .AddedRoot().
-func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallbacks) *RebuiltForrest {
+//
+// `laxAncestors` is whether or not an error instantiating an ancestor
+// tree should prevent instantiating an descendant tree (lax=false
+// prevents it, lax=true allows it).
+//
+//   - `laxAncestors` inhibits calls to
+//     RebuiltForrestExtendedCallbacks.AddedItem().
+//
+//   - `laxAncestors` causes a call to RebuiltTree.RebuiltAddRoot on
+//     the ROOT_TREE or the UUID_TREE to panic if a tree other than the
+//     ROOT_TREE or the UUID_TREE has been read from.
+func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallbacks, laxAncestors bool) *RebuiltForrest {
 	ret := &RebuiltForrest{
-		inner: fs,
-		graph: graph,
-		cb:    cb,
+		inner:        fs,
+		graph:        graph,
+		cb:           cb,
+		laxAncestors: laxAncestors,
 
 		trees: make(map[btrfsprim.ObjID]*RebuiltTree),
 	}
@@ -100,6 +117,26 @@ func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallba
 	return ret
 }
 
+func (ts *RebuiltForrest) commitTrees(ctx context.Context, treeID btrfsprim.ObjID) {
+	if treeID == btrfsprim.ROOT_TREE_OBJECTID || treeID == btrfsprim.UUID_TREE_OBJECTID {
+		return
+	}
+	ts.commitTreesOnce.Do(func() {
+		if !ts.laxAncestors {
+			return
+		}
+		ctx = ts.treesMu.Lock(ctx)
+		if !ts.treesCommitted {
+			// Make sure ROOT_TREE and UUID_TREE are ready for reading.
+			_, _ = ts.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+			_, _ = ts.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+			ts.treesCommitted = true
+			ts.treesCommitter = treeID
+		}
+		ts.treesMu.Unlock()
+	})
+}
+
 // RebuiltTree returns a given tree, initializing it if nescessary.
 //
 // The tree is initialized with the normal root node of the tree.
@@ -111,7 +148,7 @@ func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjI
 	defer ts.treesMu.Unlock()
 	ts.rebuildTree(ctx, treeID, nil)
 	tree := ts.trees[treeID]
-	if tree.ancestorLoop && tree.rootErr == nil {
+	if tree.ancestorLoop && tree.rootErr == nil && tree.ancestorRoot == 0 {
 		var loop []btrfsprim.ObjID
 		for ancestor := tree; true; ancestor = ancestor.Parent {
 			loop = append(loop, ancestor.ID)
@@ -119,7 +156,11 @@ func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjI
 				break
 			}
 		}
-		tree.rootErr = fmt.Errorf("loop detected: %v", loop)
+		if ts.laxAncestors {
+			tree.ancestorRoot = loop[len(loop)-2]
+		} else {
+			tree.rootErr = fmt.Errorf("loop detected: %v", loop)
+		}
 	}
 	if tree.rootErr != nil {
 		return nil, tree.rootErr
@@ -182,7 +223,9 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI
 			ts.trees[treeID].ParentGen = rootOff
 			parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
 			if !ok {
-				ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID)
+				if !ts.laxAncestors {
+					ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID)
+				}
 				return
 			}
 			ts.rebuildTree(ctx, parentID, stack)
@@ -191,7 +234,7 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI
 			case ts.trees[treeID].Parent.ancestorLoop:
 				ts.trees[treeID].ancestorLoop = true
 				return
-			case ts.trees[treeID].Parent.rootErr != nil:
+			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)
 				return
 			}
diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go
index 96749c4..8bbb50a 100644
--- a/lib/btrfsutil/rebuilt_forrest_test.go
+++ b/lib/btrfsutil/rebuilt_forrest_test.go
@@ -106,26 +106,60 @@ func TestRebuiltTreeCycles(t *testing.T) {
 		},
 	}
 
-	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)
+	t.Run("strict", func(t *testing.T) {
+		t.Parallel()
+		rfs := NewRebuiltForrest(nil, Graph{}, cbs, false)
+
+		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)
+	})
+	t.Run("lax", func(t *testing.T) {
+		t.Parallel()
+		rfs := NewRebuiltForrest(nil, Graph{}, cbs, true)
+
+		tree, err := rfs.RebuiltTree(ctx, 306)
+		assert.NoError(t, err)
+		assert.NotNil(t, tree)
+		assert.True(t, tree.ancestorLoop)
+		assert.Equal(t, btrfsprim.ObjID(303), tree.ancestorRoot)
+
+		assert.NotNil(t, rfs.trees[305])
+		tree, err = rfs.RebuiltTree(ctx, 305)
+		assert.NoError(t, err)
+		assert.NotNil(t, tree)
+		assert.True(t, tree.ancestorLoop)
+		assert.Equal(t, btrfsprim.ObjID(303), tree.ancestorRoot)
+
+		assert.NotNil(t, rfs.trees[304])
+		tree, err = rfs.RebuiltTree(ctx, 304)
+		assert.NoError(t, err)
+		assert.NotNil(t, tree)
+		assert.True(t, tree.ancestorLoop)
+		assert.Equal(t, btrfsprim.ObjID(305), tree.ancestorRoot)
+
+		assert.NotNil(t, rfs.trees[303])
+		tree, err = rfs.RebuiltTree(ctx, 303)
+		assert.NoError(t, err)
+		assert.NotNil(t, tree)
+		assert.True(t, tree.ancestorLoop)
+		assert.Equal(t, btrfsprim.ObjID(304), tree.ancestorRoot)
+	})
 }
 
 func TestRebuiltTreeParentErr(t *testing.T) {
@@ -185,9 +219,21 @@ func TestRebuiltTreeParentErr(t *testing.T) {
 		},
 	}
 
-	rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+	t.Run("strict", func(t *testing.T) {
+		t.Parallel()
+		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.Nil(t, tree)
+		tree, err := rfs.RebuiltTree(ctx, 305)
+		assert.EqualError(t, err, `failed to rebuild parent tree: 304: tree does not exist`)
+		assert.Nil(t, tree)
+	})
+
+	t.Run("lax", func(t *testing.T) {
+		t.Parallel()
+		rfs := NewRebuiltForrest(nil, Graph{}, cbs, true)
+
+		tree, err := rfs.RebuiltTree(ctx, 305)
+		assert.NoError(t, err)
+		assert.NotNil(t, tree)
+	})
 }
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 8d5921b..3036938 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -27,6 +27,7 @@ type RebuiltTree struct {
 
 	rootErr      error
 	ancestorLoop bool
+	ancestorRoot btrfsprim.ObjID
 
 	ID        btrfsprim.ObjID
 	UUID      btrfsprim.UUID
@@ -127,6 +128,9 @@ func (tree *RebuiltTree) uncachedNodeIndex(ctx context.Context) rebuiltNodeIndex
 	}
 	for ancestor := tree; ancestor != nil; ancestor = ancestor.Parent {
 		indexer.idToTree[ancestor.ID] = ancestor
+		if ancestor.ID == tree.ancestorRoot {
+			break
+		}
 	}
 
 	ret := rebuiltNodeIndex{
@@ -261,11 +265,12 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
 	// the "false"/failure case.  It will be called lots of times
 	// in a tight loop for both values that pass and values that
 	// fail.
+	root := tree.ancestorRoot
 	for {
 		if owner == tree.ID {
 			return true
 		}
-		if tree.Parent == nil || gen > tree.ParentGen {
+		if tree.Parent == nil || gen > tree.ParentGen || tree.ID == root {
 			return false
 		}
 		tree = tree.Parent
@@ -282,6 +287,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
 //
 // When done with the map, call .RebuiltReleaseItems().
 func (tree *RebuiltTree) RebuiltAcquireItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+	tree.forrest.commitTrees(ctx, tree.ID)
 	tree.initRoots(ctx)
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
@@ -303,6 +309,7 @@ func (tree *RebuiltTree) RebuiltReleaseItems() {
 //
 // When done with the map, call .RebuiltReleasePotentialItems().
 func (tree *RebuiltTree) RebuiltAcquirePotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+	tree.forrest.commitTrees(ctx, tree.ID)
 	tree.initRoots(ctx)
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
@@ -427,6 +434,15 @@ func (s rebuiltRootStats) String() string {
 // 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.
+//
+// If the RebuiltForrest has laxAncestors=false, then:
+//
+//   - calls to RebuiltForrestExtendedCallbacks.AddedItem() are
+//     inhibited.
+//
+//   - calling RebuiltAddRoot on the ROOT_TREE or the UUID_TREE will
+//     panic if a tree other than the ROOT_TREE or UUID_TREE has been
+//     read from.
 func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
 	tree.mu.Lock()
 	defer tree.mu.Unlock()
@@ -436,7 +452,16 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 
 	shouldFlush := tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID
 
-	if extCB, ok := tree.forrest.cb.(RebuiltForrestExtendedCallbacks); ok {
+	if tree.forrest.laxAncestors && shouldFlush {
+		_ = tree.forrest.treesMu.Lock(ctx)
+		if tree.forrest.treesCommitted {
+			panic(fmt.Errorf("RebuiltTree(%v).RebuiltAddRoot called after a non-ROOT, non-UUID tree (%v) has been read from",
+				tree.ID, tree.forrest.treesCommitter))
+		}
+		tree.forrest.treesMu.Unlock()
+	}
+
+	if extCB, ok := tree.forrest.cb.(RebuiltForrestExtendedCallbacks); ok && !tree.forrest.laxAncestors {
 		var stats rebuiltRootStats
 		nodeToRoots := tree.acquireNodeIndex(ctx).nodeToRoots
 		stats.Nodes.D = len(nodeToRoots)
@@ -501,6 +526,7 @@ func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.L
 			tree.ID, leaf))
 	}
 
+	tree.forrest.commitTrees(ctx, tree.ID)
 	tree.initRoots(ctx)
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
@@ -601,6 +627,7 @@ func (tree *RebuiltTree) TreeSubrange(ctx context.Context,
 
 // TreeWalk implements btrfstree.Tree.
 func (tree *RebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
+	tree.forrest.commitTrees(ctx, tree.ID)
 	tree.initRoots(ctx)
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
@@ -660,7 +687,7 @@ func (walker *rebuiltWalker) walk(ctx context.Context, path btrfstree.Path) {
 	}
 
 	// 001
-	nodeAddr, nodeExp, ok := path.NodeExpectations(ctx, false)
+	nodeAddr, nodeExp, ok := path.NodeExpectations(ctx)
 	if !ok {
 		panic(fmt.Errorf("should not happen: btrfsutil.rebuiltWalker.walk called with non-node path: %v",
 			path))