Merge branch 'lukeshu/misc'

10 files changed, 263 insertions, 115 deletions

diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go
index 3834345..7ed58a0 100644
--- a/lib/btrfs/btrfsvol/lvm.go
+++ b/lib/btrfs/btrfsvol/lvm.go
@@ -17,6 +17,7 @@ import (
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
 type LogicalVolume[PhysicalVolume diskio.File[PhysicalAddr]] struct {
@@ -41,7 +42,7 @@ func (lv *LogicalVolume[PhysicalVolume]) init() {
 		lv.physical2logical = make(map[DeviceID]*containers.RBTree[devextMapping], len(lv.id2pv))
 	}
 	for devid := range lv.id2pv {
-		if _, ok := lv.physical2logical[devid]; !ok {
+		if !maps.HasKey(lv.physical2logical, devid) {
 			lv.physical2logical[devid] = new(containers.RBTree[devextMapping])
 		}
 	}
@@ -120,7 +121,7 @@ func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error {
 func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) error {
 	lv.init()
 	// sanity check
-	if _, haveDev := lv.id2pv[m.PAddr.Dev]; !haveDev {
+	if !maps.HasKey(lv.id2pv, m.PAddr.Dev) {
 		return fmt.Errorf("(%p).AddMapping: do not have a physical volume with id=%v",
 			lv, m.PAddr.Dev)
 	}
@@ -228,12 +229,12 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error {
 	lv.logical2physical.Range(func(node *containers.RBNode[chunkMapping]) bool {
 		chunk := node.Value
 		for _, stripe := range chunk.PAddrs {
-			if _, devOK := lv.id2pv[stripe.Dev]; !devOK {
+			if !maps.HasKey(lv.id2pv, stripe.Dev) {
 				err = fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist",
 					lv, stripe.Dev)
 				return false
 			}
-			if _, exists := physical2logical[stripe.Dev]; !exists {
+			if !maps.HasKey(physical2logical, stripe.Dev) {
 				physical2logical[stripe.Dev] = new(containers.RBTree[devextMapping])
 			}
 			physical2logical[stripe.Dev].Insert(devextMapping{
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index fe7fe70..8e26c08 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -10,8 +10,10 @@ import (
 	"reflect"
 	"time"
 
+	"github.com/datawire/dlib/derror"
 	"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"
@@ -71,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
@@ -225,7 +268,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),
 			})
@@ -283,3 +326,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
+}
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_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index fcfb353..ba88bbc 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 {
@@ -43,10 +42,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 +70,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 +119,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().
@@ -139,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
@@ -158,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,
@@ -249,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]
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index b996bdb..ffb2e5f 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -37,21 +37,52 @@ 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() //////////////////////////////////////////////////////////////////////////////////
+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]]
+}
 
-// 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)
-	tree.forrest.leafs.Release(tree.ID)
+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
+// 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)
+}
+
 func (tree *RebuiltTree) uncachedLeafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
 	ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-nodes", fmt.Sprintf("tree=%v", tree.ID))
 
@@ -85,7 +116,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) {
@@ -133,72 +164,81 @@ 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)
+	return tree.items(ctx, true)
 }
 
-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 {
-			return !tree.Roots.HasAny(roots)
-		})
+	return tree.items(ctx, false)
 }
 
-type itemIndex = *containers.SortedMap[btrfsprim.Key, ItemPtr]
-
-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)
 }
 
-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.leafToRoots(ctx) {
-		if leafFn(roots) {
+	for leaf, roots := range tree.acquireLeafToRoots(ctx) {
+		if tree.Roots.HasAny(roots) == inc {
 			leafs = append(leafs, leaf)
 		}
 	}
+	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))
 
-	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)
@@ -220,7 +260,7 @@ func (tree *RebuiltTree) items(ctx context.Context, leafFn func(roots containers
 		}
 	}
 	if stats.Leafs.N > 0 {
-		stats.Leafs.N = len(leafs)
+		stats.Leafs.N = stats.Leafs.D
 		progressWriter.Set(stats)
 		progressWriter.Done()
 	}
@@ -262,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)
 }
@@ -282,11 +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...")
 
-	leafToRoots := tree.leafToRoots(ctx)
-
-	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)
@@ -305,6 +344,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 +375,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 +393,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
 	}
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
diff --git a/lib/containers/set.go b/lib/containers/set.go
index 074d126..af13d50 100644
--- a/lib/containers/set.go
+++ b/lib/containers/set.go
@@ -138,20 +138,11 @@ func (o Set[T]) TakeOne() T {
 }
 
 func (o Set[T]) Has(v T) bool {
-	_, has := o[v]
-	return has
+	return maps.HasKey(o, v)
 }
 
-func (small Set[T]) HasAny(big Set[T]) bool {
-	if len(big) < len(small) {
-		small, big = big, small
-	}
-	for v := range small {
-		if _, ok := big[v]; ok {
-			return true
-		}
-	}
-	return false
+func (a Set[T]) HasAny(b Set[T]) bool {
+	return maps.HaveAnyKeysInCommon(a, b)
 }
 
 func (small Set[T]) Intersection(big Set[T]) Set[T] {
@@ -160,7 +151,7 @@ func (small Set[T]) Intersection(big Set[T]) Set[T] {
 	}
 	ret := make(Set[T])
 	for v := range small {
-		if _, ok := big[v]; ok {
+		if maps.HasKey(big, v) {
 			ret.Insert(v)
 		}
 	}
diff --git a/lib/maps/maputil.go b/lib/maps/maputil.go
index d409e70..63e52a0 100644
--- a/lib/maps/maputil.go
+++ b/lib/maps/maputil.go
@@ -25,3 +25,20 @@ func SortedKeys[K constraints.Ordered, V any](m map[K]V) []K {
 	slices.Sort(ret)
 	return ret
 }
+
+func HasKey[K comparable, V any](m map[K]V, k K) bool {
+	_, has := m[k]
+	return has
+}
+
+func HaveAnyKeysInCommon[K comparable, V1, V2 any](small map[K]V1, big map[K]V2) bool {
+	if len(big) < len(small) {
+		return HaveAnyKeysInCommon(big, small)
+	}
+	for v := range small {
+		if _, ok := big[v]; ok {
+			return true
+		}
+	}
+	return false
+}
diff --git a/lib/textui/log.go b/lib/textui/log.go
index 9aff364..e5d3f60 100644
--- a/lib/textui/log.go
+++ b/lib/textui/log.go
@@ -26,6 +26,8 @@ import (
 	"git.lukeshu.com/go/typedsync"
 	"github.com/datawire/dlib/dlog"
 	"github.com/spf13/pflag"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
 type LogLevelFlag struct {
@@ -201,7 +203,7 @@ func (l *logger) log(lvl dlog.LogLevel, writeMsg func(io.Writer)) {
 	fields := make(map[string]any)
 	var fieldKeys []string
 	for f := l; f.parent != nil; f = f.parent {
-		if _, exists := fields[f.fieldKey]; exists {
+		if maps.HasKey(fields, f.fieldKey) {
 			continue
 		}
 		fields[f.fieldKey] = f.fieldVal
@@ -328,6 +330,10 @@ func fieldOrd(key string) int {
 	case "btrfs.inspect.rebuild-trees.rebuild.want.reason":
 		return -8
 
+	// btrfsutil.Graph /////////////////////////////////////////////////////
+	case "btrfs.util.read-graph.step":
+		return -1
+
 	// btrfsutil.RebuiltForrest ////////////////////////////////////////////
 	case "btrfs.util.rebuilt-forrest.add-tree":
 		return -7
@@ -426,10 +432,14 @@ func writeField(w io.Writer, key string, val any) {
 					name = strings.TrimPrefix(name, "rebuild.")
 				}
 			}
-		case strings.HasPrefix(name, "util.rebuilt-forrest."):
-			name = strings.TrimPrefix(name, "util.rebuilt-forrest.")
-		case strings.HasPrefix(name, "util.rebuilt-tree."):
-			name = strings.TrimPrefix(name, "util.rebuilt-tree.")
+		case strings.HasPrefix(name, "util."):
+			name = strings.TrimPrefix(name, "util.")
+			switch {
+			case strings.HasPrefix(name, "rebuilt-forrest."):
+				name = strings.TrimPrefix(name, "rebuilt-forrest.")
+			case strings.HasPrefix(name, "rebuilt-tree."):
+				name = strings.TrimPrefix(name, "rebuilt-tree.")
+			}
 		}
 	}