From a794062b5391b83e9f932c06f3953964e8e70b68 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 19:22:20 -0700 Subject: rebuildnodes/btrees: Move code up/down in the file, add comments --- .../btrfsinspect/rebuildnodes/btrees/tree.go | 126 +++++++++++---------- 1 file changed, 66 insertions(+), 60 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 7c64bf0..ae4065d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -35,9 +35,15 @@ type RebuiltTree struct { mu sync.Mutex Roots containers.Set[btrfsvol.LogicalAddr] Leafs containers.Set[btrfsvol.LogicalAddr] + // There are 3 more mutable "members" that are protected by + // `mu`; but they live in a shared LRUcache: + // + // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) + // 2. tree.PotentialItems() = tree.forrest.allItems.Load(tree.ID) + // 3. tree.Items() = tree.forrest.incItems.Load(tree.ID) } -// .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////////////////// +// LRU member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////////// // leafToRoots returns all leafs (lvl=0) in the filesystem that pass // .isOwnerOK, whether or not they're in the tree. @@ -124,65 +130,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati } } -// .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// - -type rootStats struct { - Leafs textui.Portion[int] - AddedLeafs int - AddedItems int -} - -func (s rootStats) String() string { - return textui.Sprintf("%v (added %v leafs, added %v items)", - s.Leafs, s.AddedLeafs, s.AddedItems) -} - -// AddRoot adds an additional root node to the tree. It is useful to -// call .AddRoot() to re-attach part of the tree that has been broken -// off. -func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { - tree.mu.Lock() - defer tree.mu.Unlock() - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) - tree.Roots.Insert(rootNode) - - var stats rootStats - 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(leafToRoots) { - stats.Leafs.N = i - progressWriter.Set(stats) - - if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { - continue - } - - tree.Leafs.Insert(leaf) - stats.AddedLeafs++ - progressWriter.Set(stats) - - for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items { - tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) - stats.AddedItems++ - progressWriter.Set(stats) - } - } - stats.Leafs.N = len(leafToRoots) - progressWriter.Set(stats) - progressWriter.Done() - - if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { - tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { - if otherTree == nil { - tree.forrest.trees.Delete(otherTreeID) - } - return true - }) - } -} - -// .Items() and .PotentialItems() ////////////////////////////////////////////////////////////////////////////////////// +// LRU members 2 and 3: .Items() and .PotentialItems() ///////////////////////////////////////////////////////////////// // Items returns a map of the items contained in this tree. // @@ -301,6 +249,64 @@ func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bo } } +// .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// + +type rootStats struct { + Leafs textui.Portion[int] + AddedLeafs int + AddedItems int +} + +func (s rootStats) String() string { + return textui.Sprintf("%v (added %v leafs, added %v items)", + s.Leafs, s.AddedLeafs, s.AddedItems) +} + +// AddRoot adds an additional root node to the tree. It is useful to +// call .AddRoot() to re-attach part of the tree that has been broken +// off. +func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { + tree.mu.Lock() + defer tree.mu.Unlock() + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) + tree.Roots.Insert(rootNode) + + var stats rootStats + 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(leafToRoots) { + stats.Leafs.N = i + progressWriter.Set(stats) + + if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { + continue + } + + tree.Leafs.Insert(leaf) + stats.AddedLeafs++ + progressWriter.Set(stats) + + for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) + stats.AddedItems++ + progressWriter.Set(stats) + } + } + stats.Leafs.N = len(leafToRoots) + progressWriter.Set(stats) + progressWriter.Done() + + if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { + tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { + if otherTree == nil { + tree.forrest.trees.Delete(otherTreeID) + } + return true + }) + } +} + // main public API ///////////////////////////////////////////////////////////////////////////////////////////////////// // COWDistance returns how many COW-snapshots down the 'tree' is from -- cgit v1.2.3-2-g168b