From 1ba83231195ea3b78ce545f4518f70c74819345b Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 31 Mar 2023 10:28:02 -0600
Subject: btrfsutil: Add a ReadGraph function, rebuildtrees: Clean up scan to
 match

---
 lib/btrfsutil/graph.go | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index fe7fe70..7863e0d 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -12,6 +12,7 @@ import (
 
 	"github.com/datawire/dlib/dlog"
 
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
@@ -283,3 +284,57 @@ func (g Graph) FinalCheck(ctx context.Context, fs btrfstree.NodeSource) error {
 
 	return nil
 }
+
+func ReadGraph(_ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr) (Graph, error) {
+	// read-superblock /////////////////////////////////////////////////////////////
+	ctx := dlog.WithField(_ctx, "btrfs.util.read-graph.step", "read-superblock")
+	dlog.Info(ctx, "Reading superblock...")
+	sb, err := fs.Superblock()
+	if err != nil {
+		return Graph{}, err
+	}
+
+	// read-roots //////////////////////////////////////////////////////////////////
+	ctx = dlog.WithField(_ctx, "btrfs.util.read-graph.step", "read-roots")
+	graph := NewGraph(ctx, *sb)
+
+	// read-nodes //////////////////////////////////////////////////////////////////
+	ctx = dlog.WithField(_ctx, "btrfs.util.read-graph.step", "read-nodes")
+	dlog.Infof(ctx, "Reading node data from FS...")
+	var stats textui.Portion[int]
+	stats.D = len(nodeList)
+	progressWriter := textui.NewProgress[textui.Portion[int]](
+		ctx,
+		dlog.LogLevelInfo,
+		textui.Tunable(1*time.Second))
+	progressWriter.Set(stats)
+	for _, laddr := range nodeList {
+		if err := ctx.Err(); err != nil {
+			return Graph{}, err
+		}
+		node, err := fs.AcquireNode(ctx, laddr, btrfstree.NodeExpectations{
+			LAddr: containers.OptionalValue(laddr),
+		})
+		if err != nil {
+			fs.ReleaseNode(node)
+			return Graph{}, err
+		}
+		graph.InsertNode(node)
+		fs.ReleaseNode(node)
+		stats.N++
+		progressWriter.Set(stats)
+	}
+	if stats.N != stats.D {
+		panic("should not happen")
+	}
+	progressWriter.Done()
+	dlog.Info(ctx, "... done reading node data")
+
+	// check ///////////////////////////////////////////////////////////////////////
+	ctx = dlog.WithField(_ctx, "btrfs.util.read-graph.step", "check")
+	if err := graph.FinalCheck(ctx, fs); err != nil {
+		return Graph{}, err
+	}
+
+	return graph, nil
+}
-- 
cgit v1.2.3-2-g168b


From c1578391cc2089cd224fd8325c333038e0ba7b7b Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 31 Mar 2023 18:01:47 -0600
Subject: maps: Add HasKey and HaveAnyKeysInCommon functions, use them

---
 lib/btrfsutil/graph.go        | 2 +-
 lib/btrfsutil/rebuilt_tree.go | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 7863e0d..db036d8 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -226,7 +226,7 @@ func (g Graph) FinalCheck(ctx context.Context, fs btrfstree.NodeSource) error {
 	stats.D = len(g.EdgesTo)
 	progressWriter.Set(stats)
 	for laddr := range g.EdgesTo {
-		if _, ok := g.Nodes[laddr]; !ok {
+		if !maps.HasKey(g.Nodes, laddr) {
 			node, err := fs.AcquireNode(ctx, laddr, btrfstree.NodeExpectations{
 				LAddr: containers.OptionalValue(laddr),
 			})
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index b996bdb..016bb1d 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -85,7 +85,7 @@ func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAdd
 	if err := ctx.Err(); err != nil {
 		return
 	}
-	if _, done := index[node]; done {
+	if maps.HasKey(index, node) {
 		return
 	}
 	if slices.Contains(node, stack) {
-- 
cgit v1.2.3-2-g168b


From 52143763329ab004ce28d660a8f67eac32fa481c Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 2 Apr 2023 11:24:13 -0600
Subject: btrfsutil: RebuiltTree: Take better advantage of cache pinning

---
 lib/btrfsutil/rebuilt_forrest.go | 11 +++---
 lib/btrfsutil/rebuilt_tree.go    | 76 +++++++++++++++++++++++++---------------
 2 files changed, 54 insertions(+), 33 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index fcfb353..d6e1fbb 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -43,10 +43,11 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
 		ObjectID: tree,
 		ItemType: btrfsprim.ROOT_ITEM_KEY,
 	}
-	itemKey, itemPtr, ok := rootTree.RebuiltItems(ctx).Search(func(key btrfsprim.Key, _ ItemPtr) int {
+	itemKey, itemPtr, ok := rootTree.RebuiltAcquireItems(ctx).Search(func(key btrfsprim.Key, _ ItemPtr) int {
 		key.Offset = 0
 		return tgt.Compare(key)
 	})
+	rootTree.RebuiltReleaseItems()
 	if !ok {
 		return 0, btrfsitem.Root{}, false
 	}
@@ -70,7 +71,8 @@ func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfs
 		return 0, false
 	}
 	tgt := btrfsitem.UUIDToKey(uuid)
-	itemPtr, ok := uuidTree.RebuiltItems(ctx).Load(tgt)
+	itemPtr, ok := uuidTree.RebuiltAcquireItems(ctx).Load(tgt)
+	uuidTree.RebuiltReleaseItems()
 	if !ok {
 		return 0, false
 	}
@@ -118,8 +120,9 @@ func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfs
 //   - 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.
+//     .RebuiltAcquireItems()/.RebuiltReleaseItems() and
+//     .RebuiltAcquirePotentialItems()/.RebuiltReleasePotentialItems()
+//     to compare what's in the tree and what could be in the tree.
 //
 //     .RebuiltLeafToRoots() to map potential items to things that can
 //     be passed to .RebuiltAddRoot().
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 016bb1d..61bbb5e 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -37,19 +37,21 @@ type RebuiltTree struct {
 	// derived from tree.Roots, which is why it's OK if they get
 	// evicted.
 	//
-	//  1. tree.leafToRoots()           = tree.forrest.leafs.Acquire(tree.ID)
-	//  2. tree.RebuiltItems()          = tree.forrest.incItems.Acquire(tree.ID)
-	//  3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Acquire(tree.ID)
+	//  1. tree.acquireLeafToRoots()           = tree.forrest.leafs.Acquire(tree.ID)
+	//  2. tree.RebuiltAcquireItems()          = tree.forrest.incItems.Acquire(tree.ID)
+	//  3. tree.RebuiltAcquirePotentialItems() = tree.forrest.excItems.Acquire(tree.ID)
 }
 
-// evictable member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////
+// evictable member 1: .acquireLeafToRoots() ///////////////////////////////////////////////////////////////////////////
 
-// leafToRoots returns all leafs (lvl=0) in the filesystem that pass
-// .isOwnerOK, whether or not they're in the tree.
-func (tree *RebuiltTree) leafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
-	ret := *tree.forrest.leafs.Acquire(ctx, tree.ID)
+// acquireLeafToRoots returns all leafs (lvl=0) in the filesystem that
+// pass .isOwnerOK, whether or not they're in the tree.
+func (tree *RebuiltTree) acquireLeafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
+	return *tree.forrest.leafs.Acquire(ctx, tree.ID)
+}
+
+func (tree *RebuiltTree) releaseLeafToRoots() {
 	tree.forrest.leafs.Release(tree.ID)
-	return ret
 }
 
 func (tree *RebuiltTree) uncachedLeafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
@@ -133,35 +135,48 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
 	}
 }
 
-// evictable members 2 and 3: .RebuiltItems() and .RebuiltPotentialItems() /////////////////////////////////////////////
+// evictable members 2 and 3: .Rebuilt{Acquire,Release}{Potential,}Items() /////////////////////////////////////////////
 
-// RebuiltItems returns a map of the items contained in this tree.
+// RebuiltAcquireItems 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) RebuiltItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
-	ret := *tree.forrest.incItems.Acquire(ctx, tree.ID)
+//
+// When done with the map, call .RebuiltReleaseItems().
+func (tree *RebuiltTree) RebuiltAcquireItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+	return tree.forrest.incItems.Acquire(ctx, tree.ID)
+}
+
+// RebuiltReleaseItems releases resources after a call to
+// .RebuiltAcquireItems().
+func (tree *RebuiltTree) RebuiltReleaseItems() {
 	tree.forrest.incItems.Release(tree.ID)
-	return ret
 }
 
-// RebuiltPotentialItems returns a map of items that could be added to
-// this tree with .RebuiltAddRoot().
+// RebuiltAcquirePotentialItems 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) RebuiltPotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
-	ret := *tree.forrest.excItems.Acquire(ctx, tree.ID)
+//
+// When done with the map, call .RebuiltReleasePotentialItems().
+func (tree *RebuiltTree) RebuiltAcquirePotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+	return tree.forrest.excItems.Acquire(ctx, tree.ID)
+}
+
+// RebuiltReleasePotentialItems releases resources after a call to
+// .RebuiltAcquirePotentialItems().
+func (tree *RebuiltTree) RebuiltReleasePotentialItems() {
 	tree.forrest.excItems.Release(tree.ID)
-	return ret
 }
 
-func (tree *RebuiltTree) uncachedIncItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) uncachedIncItems(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.Roots.HasAny)
 }
 
-func (tree *RebuiltTree) uncachedExcItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) uncachedExcItems(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,
 		func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
@@ -169,7 +184,7 @@ func (tree *RebuiltTree) uncachedExcItems(ctx context.Context) *containers.Sorte
 		})
 }
 
-type itemIndex = *containers.SortedMap[btrfsprim.Key, ItemPtr]
+type itemIndex = containers.SortedMap[btrfsprim.Key, ItemPtr]
 
 type itemStats struct {
 	Leafs    textui.Portion[int]
@@ -182,23 +197,24 @@ func (s itemStats) String() string {
 		s.Leafs, s.NumItems, s.NumDups)
 }
 
-func (tree *RebuiltTree) items(ctx context.Context, leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) items(ctx context.Context, leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool) containers.SortedMap[btrfsprim.Key, ItemPtr] {
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
 
 	var leafs []btrfsvol.LogicalAddr
-	for leaf, roots := range tree.leafToRoots(ctx) {
+	for leaf, roots := range tree.acquireLeafToRoots(ctx) {
 		if leafFn(roots) {
 			leafs = append(leafs, leaf)
 		}
 	}
+	tree.releaseLeafToRoots()
 	slices.Sort(leafs)
 
 	var stats itemStats
 	stats.Leafs.D = len(leafs)
 	progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
 
-	index := new(containers.SortedMap[btrfsprim.Key, ItemPtr])
+	var index containers.SortedMap[btrfsprim.Key, ItemPtr]
 	for i, leaf := range leafs {
 		stats.Leafs.N = i
 		progressWriter.Set(stats)
@@ -282,9 +298,8 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
 	dlog.Info(ctx, "adding root...")
 
-	leafToRoots := tree.leafToRoots(ctx)
-
 	var stats rootStats
+	leafToRoots := tree.acquireLeafToRoots(ctx)
 	stats.Leafs.D = len(leafToRoots)
 	progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
 	for i, leaf := range maps.SortedKeys(leafToRoots) {
@@ -305,6 +320,7 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 		}
 	}
 	stats.Leafs.N = len(leafToRoots)
+	tree.releaseLeafToRoots()
 	progressWriter.Set(stats)
 	progressWriter.Done()
 
@@ -335,7 +351,8 @@ func (tree *RebuiltTree) RebuiltCOWDistance(parentID btrfsprim.ObjID) (dist int,
 
 // ReadItem reads an item from a tree.
 func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsitem.Item {
-	ptr, ok := tree.RebuiltItems(ctx).Load(key)
+	ptr, ok := tree.RebuiltAcquireItems(ctx).Load(key)
+	tree.RebuiltReleaseItems()
 	if !ok {
 		panic(fmt.Errorf("should not happen: btrfsutil.RebuiltTree.ReadItem called for not-included key: %v", key))
 	}
@@ -352,13 +369,14 @@ func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.L
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
 	ret := make(containers.Set[btrfsvol.LogicalAddr])
-	for root := range tree.leafToRoots(ctx)[leaf] {
+	for root := range tree.acquireLeafToRoots(ctx)[leaf] {
 		if tree.Roots.Has(root) {
 			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)
 	}
+	tree.releaseLeafToRoots()
 	if len(ret) == 0 {
 		return nil
 	}
-- 
cgit v1.2.3-2-g168b


From 3e35c0eb69b0fdae195d8fa372a026977acba737 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 2 Apr 2023 18:57:43 -0600
Subject: btrfsutil: GraphNode: Add a CheckExpectations method

---
 lib/btrfsutil/graph.go | 42 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index db036d8..8e26c08 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -10,6 +10,7 @@ import (
 	"reflect"
 	"time"
 
+	"github.com/datawire/dlib/derror"
 	"github.com/datawire/dlib/dlog"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
@@ -72,6 +73,47 @@ func (n GraphNode) String() string {
 		n.Level, n.Generation, n.Owner, len(n.Items))
 }
 
+func (n GraphNode) CheckExpectations(g Graph, exp btrfstree.NodeExpectations) error {
+	var errs derror.MultiError
+	if exp.LAddr.OK && n.Addr != exp.LAddr.Val {
+		errs = append(errs, fmt.Errorf("read from laddr=%v but claims to be at laddr=%v",
+			exp.LAddr.Val, n.Addr))
+	}
+	if exp.Level.OK && n.Level != exp.Level.Val {
+		errs = append(errs, fmt.Errorf("expected level=%v but claims to be level=%v",
+			exp.Level.Val, n.Level))
+	}
+	if n.Level > btrfstree.MaxLevel {
+		errs = append(errs, fmt.Errorf("maximum level=%v but claims to be level=%v",
+			btrfstree.MaxLevel, n.Level))
+	}
+	if exp.Generation.OK && n.Generation != exp.Generation.Val {
+		errs = append(errs, fmt.Errorf("expected generation=%v but claims to be generation=%v",
+			exp.Generation.Val, n.Generation))
+	}
+	if exp.Owner != nil {
+		if err := exp.Owner(n.Owner, n.Generation); err != nil {
+			errs = append(errs, err)
+		}
+	}
+	if n.NumItems(g) == 0 {
+		errs = append(errs, fmt.Errorf("has no items"))
+	} else {
+		if minItem := n.MinItem(g); exp.MinItem.OK && exp.MinItem.Val.Compare(minItem) > 0 {
+			errs = append(errs, fmt.Errorf("expected minItem>=%v but node has minItem=%v",
+				exp.MinItem.Val, minItem))
+		}
+		if maxItem := n.MaxItem(g); exp.MaxItem.OK && exp.MaxItem.Val.Compare(maxItem) < 0 {
+			errs = append(errs, fmt.Errorf("expected maxItem<=%v but node has maxItem=%v",
+				exp.MaxItem.Val, maxItem))
+		}
+	}
+	if len(errs) > 0 {
+		return errs
+	}
+	return nil
+}
+
 type GraphEdge struct {
 	// It is invalid for both 'FromRoot' and 'FromNode' to be
 	// non-zero.  If both are zero, then the GraphEdge is from the
-- 
cgit v1.2.3-2-g168b


From fe3b3fdcace149b3514df716ea5de363a0c2e0cb Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 2 Apr 2023 20:11:38 -0600
Subject: btrfsutil: RebuiltTree: Have .items() take a bool instead of a func

---
 lib/btrfsutil/rebuilt_tree.go | 11 ++++-------
 1 file changed, 4 insertions(+), 7 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 61bbb5e..836873e 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -173,15 +173,12 @@ func (tree *RebuiltTree) RebuiltReleasePotentialItems() {
 
 func (tree *RebuiltTree) uncachedIncItems(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.Roots.HasAny)
+	return tree.items(ctx, true)
 }
 
 func (tree *RebuiltTree) uncachedExcItems(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,
-		func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
-			return !tree.Roots.HasAny(roots)
-		})
+	return tree.items(ctx, false)
 }
 
 type itemIndex = containers.SortedMap[btrfsprim.Key, ItemPtr]
@@ -197,13 +194,13 @@ func (s itemStats) String() string {
 		s.Leafs, s.NumItems, s.NumDups)
 }
 
-func (tree *RebuiltTree) items(ctx context.Context, leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool) containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedMap[btrfsprim.Key, ItemPtr] {
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
 
 	var leafs []btrfsvol.LogicalAddr
 	for leaf, roots := range tree.acquireLeafToRoots(ctx) {
-		if leafFn(roots) {
+		if tree.Roots.HasAny(roots) == inc {
 			leafs = append(leafs, leaf)
 		}
 	}
-- 
cgit v1.2.3-2-g168b


From bd186dc2fcf4c54d6152d6e3c25775abf77bf1ca Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 2 Apr 2023 22:05:13 -0600
Subject: btrfsutil: Move the shared cache definitions from rebuilt_forrest.go
 to rebuilt_tree.go

---
 lib/btrfsutil/rebuilt_forrest.go | 25 ++++++-------------------
 lib/btrfsutil/rebuilt_tree.go    | 31 +++++++++++++++++++++++++++++--
 2 files changed, 35 insertions(+), 21 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index d6e1fbb..7f239c3 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -16,7 +16,6 @@ import (
 	"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"
-	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
 type RebuiltForrestCallbacks interface {
@@ -142,11 +141,10 @@ type RebuiltForrest struct {
 
 	// mutable
 
-	treesMu  nestedMutex
-	trees    map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
-	leafs    containers.Cache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
-	incItems containers.Cache[btrfsprim.ObjID, itemIndex]
-	excItems containers.Cache[btrfsprim.ObjID, itemIndex]
+	treesMu nestedMutex
+	trees   map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
+
+	rebuiltSharedCache
 }
 
 // NewRebuiltForrest returns a new RebuiltForrest instance.  The
@@ -161,19 +159,8 @@ func NewRebuiltForrest(file btrfstree.NodeSource, sb btrfstree.Superblock, graph
 		trees: make(map[btrfsprim.ObjID]*RebuiltTree),
 	}
 
-	ret.leafs = containers.NewARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](textui.Tunable(8),
-		containers.SourceFunc[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](
-			func(ctx context.Context, treeID btrfsprim.ObjID, leafs *map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) {
-				*leafs = ret.trees[treeID].uncachedLeafToRoots(ctx)
-			}))
-	ret.incItems = containers.NewARCache[btrfsprim.ObjID, itemIndex](textui.Tunable(8),
-		containers.SourceFunc[btrfsprim.ObjID, itemIndex](func(ctx context.Context, treeID btrfsprim.ObjID, incItems *itemIndex) {
-			*incItems = ret.trees[treeID].uncachedIncItems(ctx)
-		}))
-	ret.excItems = containers.NewARCache[btrfsprim.ObjID, itemIndex](textui.Tunable(8),
-		containers.SourceFunc[btrfsprim.ObjID, itemIndex](func(ctx context.Context, treeID btrfsprim.ObjID, excItems *itemIndex) {
-			*excItems = ret.trees[treeID].uncachedExcItems(ctx)
-		}))
+	ret.rebuiltSharedCache = makeRebuiltSharedCache(ret)
+
 	if ret.cb == nil {
 		ret.cb = noopRebuiltForrestCallbacks{
 			forrest: ret,
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 836873e..19b53ce 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -42,6 +42,35 @@ type RebuiltTree struct {
 	//  3. tree.RebuiltAcquirePotentialItems() = tree.forrest.excItems.Acquire(tree.ID)
 }
 
+type rebuiltSharedCache struct {
+	leafs    containers.Cache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
+	incItems containers.Cache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]]
+	excItems containers.Cache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]]
+}
+
+func makeRebuiltSharedCache(forrest *RebuiltForrest) rebuiltSharedCache {
+	var ret rebuiltSharedCache
+	ret.leafs = containers.NewARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](
+		textui.Tunable(8),
+		containers.SourceFunc[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](
+			func(ctx context.Context, treeID btrfsprim.ObjID, leafs *map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) {
+				*leafs = forrest.trees[treeID].uncachedLeafToRoots(ctx)
+			}))
+	ret.incItems = containers.NewARCache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]](
+		textui.Tunable(8),
+		containers.SourceFunc[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]](
+			func(ctx context.Context, treeID btrfsprim.ObjID, incItems *containers.SortedMap[btrfsprim.Key, ItemPtr]) {
+				*incItems = forrest.trees[treeID].uncachedIncItems(ctx)
+			}))
+	ret.excItems = containers.NewARCache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]](
+		textui.Tunable(8),
+		containers.SourceFunc[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]](
+			func(ctx context.Context, treeID btrfsprim.ObjID, excItems *containers.SortedMap[btrfsprim.Key, ItemPtr]) {
+				*excItems = forrest.trees[treeID].uncachedExcItems(ctx)
+			}))
+	return ret
+}
+
 // evictable member 1: .acquireLeafToRoots() ///////////////////////////////////////////////////////////////////////////
 
 // acquireLeafToRoots returns all leafs (lvl=0) in the filesystem that
@@ -181,8 +210,6 @@ func (tree *RebuiltTree) uncachedExcItems(ctx context.Context) containers.Sorted
 	return tree.items(ctx, false)
 }
 
-type itemIndex = containers.SortedMap[btrfsprim.Key, ItemPtr]
-
 type itemStats struct {
 	Leafs    textui.Portion[int]
 	NumItems int
-- 
cgit v1.2.3-2-g168b


From b7e24934c062017fd50fff5d3416b2729c99bc4e Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 2 Apr 2023 22:36:41 -0600
Subject: btrfsutil: RebuiltTree.items: Simplify a touch

---
 lib/btrfsutil/rebuilt_tree.go | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 19b53ce..8e6e32d 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -260,7 +260,7 @@ func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedM
 		}
 	}
 	if stats.Leafs.N > 0 {
-		stats.Leafs.N = len(leafs)
+		stats.Leafs.N = stats.Leafs.D
 		progressWriter.Set(stats)
 		progressWriter.Done()
 	}
-- 
cgit v1.2.3-2-g168b


From 83886d4925e3d1d9c2c5d9cca4dd165597e54864 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Mon, 3 Apr 2023 15:06:31 -0600
Subject: btrfsutil: Rename unexported types to be clearer about which system
 they belong to
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

 - nodeInfo    → oldRebuiltNodeInfo (old_rebuilt_forrest.go)
 - itemStats   → rebuiltItemStats   (rebuilt_tree.go)
 - rootStats   → rebuiltRootStats   (rebuilt_tree.go)
 - nodeScanner → nodeLister         (listnodes.go)
 - nodeStats   → nodeListStats      (listnodes.go)
 - scanStats   → devScanStats       (scan.go)
---
 lib/btrfsutil/listnodes.go           | 24 ++++++++++++------------
 lib/btrfsutil/old_rebuilt_forrest.go | 10 +++++-----
 lib/btrfsutil/rebuilt_tree.go        | 16 ++++++++--------
 lib/btrfsutil/scan.go                |  8 ++++----
 4 files changed, 29 insertions(+), 29 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/listnodes.go b/lib/btrfsutil/listnodes.go
index 70b647c..d4572bd 100644
--- a/lib/btrfsutil/listnodes.go
+++ b/lib/btrfsutil/listnodes.go
@@ -15,45 +15,45 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
-type nodeScanner struct {
+type nodeLister struct {
 	nodes containers.Set[btrfsvol.LogicalAddr]
 }
 
-type nodeStats struct {
+type nodeListStats struct {
 	numNodes int
 }
 
-func (s nodeStats) String() string {
+func (s nodeListStats) String() string {
 	return textui.Sprintf("found: %d nodes", s.numNodes)
 }
 
-var _ DeviceScanner[nodeStats, containers.Set[btrfsvol.LogicalAddr]] = (*nodeScanner)(nil)
+var _ DeviceScanner[nodeListStats, containers.Set[btrfsvol.LogicalAddr]] = (*nodeLister)(nil)
 
-func newNodeScanner(context.Context, btrfstree.Superblock, btrfsvol.PhysicalAddr, int) DeviceScanner[nodeStats, containers.Set[btrfsvol.LogicalAddr]] {
-	s := new(nodeScanner)
+func newNodeLister(context.Context, btrfstree.Superblock, btrfsvol.PhysicalAddr, int) DeviceScanner[nodeListStats, containers.Set[btrfsvol.LogicalAddr]] {
+	s := new(nodeLister)
 	s.nodes = make(containers.Set[btrfsvol.LogicalAddr])
 	return s
 }
 
-func (s *nodeScanner) ScanStats() nodeStats {
-	return nodeStats{numNodes: len(s.nodes)}
+func (s *nodeLister) ScanStats() nodeListStats {
+	return nodeListStats{numNodes: len(s.nodes)}
 }
 
-func (*nodeScanner) ScanSector(context.Context, *btrfs.Device, btrfsvol.PhysicalAddr) error {
+func (*nodeLister) ScanSector(context.Context, *btrfs.Device, btrfsvol.PhysicalAddr) error {
 	return nil
 }
 
-func (s *nodeScanner) ScanNode(_ context.Context, _ btrfsvol.PhysicalAddr, node *btrfstree.Node) error {
+func (s *nodeLister) ScanNode(_ context.Context, _ btrfsvol.PhysicalAddr, node *btrfstree.Node) error {
 	s.nodes.Insert(node.Head.Addr)
 	return nil
 }
 
-func (s *nodeScanner) ScanDone(_ context.Context) (containers.Set[btrfsvol.LogicalAddr], error) {
+func (s *nodeLister) ScanDone(_ context.Context) (containers.Set[btrfsvol.LogicalAddr], error) {
 	return s.nodes, nil
 }
 
 func ListNodes(ctx context.Context, fs *btrfs.FS) ([]btrfsvol.LogicalAddr, error) {
-	perDev, err := ScanDevices[nodeStats, containers.Set[btrfsvol.LogicalAddr]](ctx, fs, newNodeScanner)
+	perDev, err := ScanDevices[nodeListStats, containers.Set[btrfsvol.LogicalAddr]](ctx, fs, newNodeLister)
 	if err != nil {
 		return nil, err
 	}
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index c451fb8..0a3106d 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -53,11 +53,11 @@ type oldRebuiltTreeValue struct {
 	Key      btrfsprim.Key
 	ItemSize uint32
 
-	Node nodeInfo
+	Node oldRebuiltNodeInfo
 	Slot int
 }
 
-type nodeInfo struct {
+type oldRebuiltNodeInfo struct {
 	LAddr      btrfsvol.LogicalAddr
 	Level      uint8
 	Generation btrfsprim.Generation
@@ -187,7 +187,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O
 	cacheEntry.ParentUUID = root.ParentUUID
 	cacheEntry.ParentGen = root.ParentGen
 
-	var curNode nodeInfo
+	var curNode oldRebuiltNodeInfo
 	cbs := btrfstree.TreeWalkHandler{
 		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
 			nodeAddr, nodeExp, _ := path.NodeExpectations(ctx, false)
@@ -200,7 +200,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O
 			return false
 		},
 		Node: func(path btrfstree.Path, node *btrfstree.Node) {
-			curNode = nodeInfo{
+			curNode = oldRebuiltNodeInfo{
 				LAddr:      node.Head.Addr,
 				Level:      node.Head.Level,
 				Generation: node.Head.Generation,
@@ -247,7 +247,7 @@ func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error
 	return errs
 }
 
-func (bt *OldRebuiltForrest) readNode(ctx context.Context, nodeInfo nodeInfo) *btrfstree.Node {
+func (bt *OldRebuiltForrest) readNode(ctx context.Context, nodeInfo oldRebuiltNodeInfo) *btrfstree.Node {
 	node, err := bt.AcquireNode(ctx, nodeInfo.LAddr, btrfstree.NodeExpectations{
 		LAddr:      containers.OptionalValue(nodeInfo.LAddr),
 		Level:      containers.OptionalValue(nodeInfo.Level),
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 8e6e32d..ffb2e5f 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -210,13 +210,13 @@ func (tree *RebuiltTree) uncachedExcItems(ctx context.Context) containers.Sorted
 	return tree.items(ctx, false)
 }
 
-type itemStats struct {
+type rebuiltItemStats struct {
 	Leafs    textui.Portion[int]
 	NumItems int
 	NumDups  int
 }
 
-func (s itemStats) String() string {
+func (s rebuiltItemStats) String() string {
 	return textui.Sprintf("%v (%v items, %v dups)",
 		s.Leafs, s.NumItems, s.NumDups)
 }
@@ -234,9 +234,9 @@ func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedM
 	tree.releaseLeafToRoots()
 	slices.Sort(leafs)
 
-	var stats itemStats
+	var stats rebuiltItemStats
 	stats.Leafs.D = len(leafs)
-	progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	progressWriter := textui.NewProgress[rebuiltItemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
 
 	var index containers.SortedMap[btrfsprim.Key, ItemPtr]
 	for i, leaf := range leafs {
@@ -302,13 +302,13 @@ func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalA
 	}
 }
 
-type rootStats struct {
+type rebuiltRootStats struct {
 	Leafs      textui.Portion[int]
 	AddedLeafs int
 	AddedItems int
 }
 
-func (s rootStats) String() string {
+func (s rebuiltRootStats) String() string {
 	return textui.Sprintf("%v (added %v leafs, added %v items)",
 		s.Leafs, s.AddedLeafs, s.AddedItems)
 }
@@ -322,10 +322,10 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
 	dlog.Info(ctx, "adding root...")
 
-	var stats rootStats
+	var stats rebuiltRootStats
 	leafToRoots := tree.acquireLeafToRoots(ctx)
 	stats.Leafs.D = len(leafToRoots)
-	progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	progressWriter := textui.NewProgress[rebuiltRootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
 	for i, leaf := range maps.SortedKeys(leafToRoots) {
 		stats.Leafs.N = i
 		progressWriter.Set(stats)
diff --git a/lib/btrfsutil/scan.go b/lib/btrfsutil/scan.go
index 0e268e5..bf848ee 100644
--- a/lib/btrfsutil/scan.go
+++ b/lib/btrfsutil/scan.go
@@ -33,12 +33,12 @@ type DeviceScanner[Stats comparable, Result any] interface {
 	ScanDone(ctx context.Context) (Result, error)
 }
 
-type scanStats[T comparable] struct {
+type devScanStats[T comparable] struct {
 	portion textui.Portion[btrfsvol.PhysicalAddr]
 	stats   T
 }
 
-func (s scanStats[T]) String() string {
+func (s devScanStats[T]) String() string {
 	return textui.Sprintf("scanned %v (%v)",
 		s.portion, s.stats)
 }
@@ -91,8 +91,8 @@ func ScanOneDevice[Stats comparable, Result any](ctx context.Context, dev *btrfs
 
 	scanner := newScanner(ctx, *sb, numBytes, numSectors)
 
-	progressWriter := textui.NewProgress[scanStats[Stats]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-	var stats scanStats[Stats]
+	progressWriter := textui.NewProgress[devScanStats[Stats]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+	var stats devScanStats[Stats]
 	stats.portion.D = numBytes
 
 	var minNextNode btrfsvol.PhysicalAddr
-- 
cgit v1.2.3-2-g168b


From d7dd6dfd7aeb40f06ff4fbe7f906d8feed64b95f Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Tue, 4 Apr 2023 15:34:01 -0600
Subject: btrfsutil: RebuiltForrest: Include more info when logging failures

---
 lib/btrfsutil/rebuilt_forrest.go | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'lib/btrfsutil')

diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 7f239c3..ba88bbc 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -239,11 +239,11 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
 			}
 			parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
 			if !ok {
-				dlog.Error(ctx, "failed to add tree: lookup UUID")
+				dlog.Errorf(ctx, "failed to add tree: lookup UUID %v", rootItem.ParentUUID)
 				return false
 			}
 			if !ts.addTree(ctx, parentID, stack) {
-				dlog.Error(ctx, "failed to add tree: add parent tree")
+				dlog.Errorf(ctx, "failed to add tree: add parent tree %v", parentID)
 				return false
 			}
 			tree.Parent = ts.trees[parentID]
-- 
cgit v1.2.3-2-g168b