From a433371680b2e01a5fdf05b342c9c4d9f8c3cc20 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 31 Dec 2022 13:15:07 -0700 Subject: rebuildnodes/btrees: Allow leaf-node indexes to be evicted --- .../btrfsinspect/rebuildnodes/btrees/forrest.go | 3 +- .../btrfsinspect/rebuildnodes/btrees/tree.go | 69 ++++++++++++---------- .../btrfsinspect/rebuildnodes/rebuild.go | 8 +-- lib/textui/log.go | 12 ++-- 4 files changed, 49 insertions(+), 43 deletions(-) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 60f922d..de21d9a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -63,6 +63,7 @@ type RebuiltForrest struct { // mutable trees containers.SyncMap[btrfsprim.ObjID, *RebuiltTree] + leafs *containers.LRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]] allItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] } @@ -84,6 +85,7 @@ func NewRebuiltForrest( cbLookupRoot: cbLookupRoot, cbLookupUUID: cbLookupUUID, + leafs: containers.NewLRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](textui.Tunable(8)), allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), } @@ -154,7 +156,6 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s tree.Parent, _ = ts.trees.Load(parentID) } } - tree.indexLeafs(ctx) ts.trees.Store(treeID, tree) if root != 0 { diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 1daeefc..678d25f 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -31,42 +31,44 @@ type RebuiltTree struct { ParentGen btrfsprim.Generation // offset of this tree's root item forrest *RebuiltForrest - // all leafs (lvl=0) that pass .isOwnerOK, whether or not they're in the tree - leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] - // mutable mu sync.Mutex Roots containers.Set[btrfsvol.LogicalAddr] Leafs containers.Set[btrfsvol.LogicalAddr] } -// initializaton (called by `RebuiltForrest.Tree()`) /////////////////////////////////////////////////////////////////// +// .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////////////////// -func (tree *RebuiltTree) indexLeafs(ctx context.Context) { - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep", "index-nodes") +// 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] { + return tree.forrest.leafs.GetOrElse(tree.ID, func() map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-nodes", fmt.Sprintf("tree=%v", tree.ID)) - nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - var stats textui.Portion[int] - stats.D = len(tree.forrest.graph.Nodes) - progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - progress := func() { - stats.N = len(nodeToRoots) - progressWriter.Set(stats) - } + var stats textui.Portion[int] + stats.D = len(tree.forrest.graph.Nodes) + progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + progress := func() { + stats.N = len(nodeToRoots) + progressWriter.Set(stats) + } - progress() - for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) { - tree.indexNode(ctx, node, nodeToRoots, progress, nil) - } - progressWriter.Done() + progress() + for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) { + tree.indexNode(ctx, node, nodeToRoots, progress, nil) + } + progressWriter.Done() - tree.leafToRoots = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - for node, roots := range nodeToRoots { - if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 { - tree.leafToRoots[node] = roots + ret := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + for node, roots := range nodeToRoots { + if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 { + ret[node] = roots + } } - } + return ret + }) } func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) { @@ -145,13 +147,14 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA tree.Roots.Insert(rootNode) var stats rootStats - stats.Leafs.D = len(tree.leafToRoots) + leafToRoots := tree.leafToRoots(ctx) + stats.Leafs.D = len(leafToRoots) progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - for i, leaf := range maps.SortedKeys(tree.leafToRoots) { + for i, leaf := range maps.SortedKeys(leafToRoots) { stats.Leafs.N = i progressWriter.Set(stats) - if tree.Leafs.Has(leaf) || !tree.leafToRoots[leaf].Has(rootNode) { + if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { continue } @@ -165,7 +168,7 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA progressWriter.Set(stats) } } - stats.Leafs.N = len(tree.leafToRoots) + stats.Leafs.N = len(leafToRoots) progressWriter.Set(stats) progressWriter.Done() } @@ -188,7 +191,7 @@ func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsp // RebuiltTree's internal map! func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-all-items", fmt.Sprintf("tree=%v", tree.ID)) - return tree.items(ctx, tree.forrest.allItems, maps.SortedKeys(tree.leafToRoots)) + return tree.items(ctx, tree.forrest.allItems, maps.SortedKeys(tree.leafToRoots(ctx))) } type itemIndex struct { @@ -317,13 +320,15 @@ func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) (item // LeafToRoots returns the list of potential roots (to pass to // .AddRoot) that include a given leaf-node. -func (tree *RebuiltTree) LeafToRoots(leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { +func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { if tree.forrest.graph.Nodes[leaf].Level != 0 { panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf", tree.ID, leaf)) } + tree.mu.Lock() + defer tree.mu.Unlock() ret := make(containers.Set[btrfsvol.LogicalAddr]) - for root := range tree.leafToRoots[leaf] { + for root := range tree.leafToRoots(ctx)[leaf] { if tree.Roots.Has(root) { panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf", tree.ID, leaf, root)) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index cefa668..3696a8a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -447,7 +447,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, func(_ btrfsprim.Key, v keyio.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) + wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node)) return true }) o.wantAugment(ctx, treeID, wants) @@ -484,7 +484,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) }, func(_ btrfsprim.Key, v keyio.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) + wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node)) return true }) o.wantAugment(ctx, treeID, wants) @@ -526,7 +526,7 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, func(k btrfsprim.Key, v keyio.ItemPtr) bool { if fn(v) { - wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) + wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node)) } return true }) @@ -706,7 +706,7 @@ func (o *rebuilder) _wantRange( } wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, gap.Beg, gap.End)) - o.wantAugment(wantCtx, treeID, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(v.Node)) + o.wantAugment(wantCtx, treeID, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node)) last = runEnd return true diff --git a/lib/textui/log.go b/lib/textui/log.go index da303dd..8327b67 100644 --- a/lib/textui/log.go +++ b/lib/textui/log.go @@ -322,17 +322,17 @@ func fieldOrd(key string) int { return -8 case "btrfsinspect.rebuild-nodes.rebuild.add-tree": return -7 - case "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep": - return -6 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key": - return -5 + return -6 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason": - return -4 + return -5 case "btrfsinspect.rebuild-nodes.rebuild.add-root": - return -3 + return -4 case "btrfsinspect.rebuild-nodes.rebuild.index-inc-items": - return -2 + return -3 case "btrfsinspect.rebuild-nodes.rebuild.index-all-items": + return -2 + case "btrfsinspect.rebuild-nodes.rebuild.index-nodes": return -1 // other /////////////////////////////////////////////////////////////// -- cgit v1.1-4-g5e80