From 5d25e2449110ca37eb1f0f5b0290f2868c21ac2a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 14:02:16 -0700 Subject: rebuildnodes/btrees: Rename methods to make API structure clearer --- lib/btrfsutil/rebuilt_forrest.go | 51 ++++++++++++++++++++++------------- lib/btrfsutil/rebuilt_tree.go | 58 +++++++++++++++++++--------------------- 2 files changed, 61 insertions(+), 48 deletions(-) (limited to 'lib/btrfsutil') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 25d953b..de18080 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -30,10 +30,9 @@ type RebuiltForrestCallbacks interface { // RebuiltForrest is an abstraction for rebuilding and accessing // potentially broken btrees. // -// It is conceptually a btrfstree.TreeOperator, and adds similar -// broken-tree handling to OldRebuiltForrest. However, the API is -// different than btrfstree.TreeOperator, and is much more efficient -// than OldRebuiltForrest. +// It is conceptually a btrfstree.Forrest, and adds similar +// broken-tree handling to OldRebuiltForrest. However, it is much +// more efficient than OldRebuiltForrest. // // The efficiency improvements are possible because of the API // differences, which are necessary for how it is used in @@ -49,11 +48,24 @@ type RebuiltForrestCallbacks interface { // Additionally, it provides some functionality that OldRebuiltForrest // does not: // -// - it provides a .LeafToRoots() method to advise on what -// additional roots should be added +// - it provides a RebuiltForrest.RebuiltListRoots() method for +// listing how trees have been repaired. // -// - it provides a .COWDistance() method to compare how related two -// trees are +// - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a +// tree. +// +// - 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. +// +// .RebuiltLeafToRoots() to map potential items to things that can +// be passed to .RebuiltAddRoot(). +// +// .RebuiltCOWDistance() and .RebuiltShouldReplace() to provide +// information on deciding on an option from +// .RebuiltLeafToRoots(). // // A zero RebuiltForrest is invalid; it must be initialized with // NewRebuiltForrest(). @@ -105,12 +117,15 @@ func NewRebuiltForrest(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Supe } } -// Tree returns a given tree, initializing it if nescessary. If it is -// unable to initialize the tree, then nil is returned, and nothing is -// done to the forrest. +// RebuiltTree returns a given tree, initializing it if nescessary. +// If it is unable to initialize the tree, then nil is returned, and +// nothing is done to the forrest. // // The tree is initialized with the normal root node of the tree. -func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree { +// +// This is identical to .ForrestLookup(), but returns a concrete type +// rather than an interface. +func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree { ctx = ts.treesMu.Lock(ctx) defer ts.treesMu.Unlock() if !ts.addTree(ctx, treeID, nil) { @@ -125,8 +140,8 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s } defer func() { if !ok { - // Store a negative cache of this. tree.AddRoot() for the ROOT or UUID - // trees will call .flushNegativeCache(). + // Store a negative cache of this. tree.RebuiltAddRoot() for the ROOT or + // UUID trees will call .flushNegativeCache(). ts.trees[treeID] = nil } }() @@ -185,7 +200,7 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s ts.trees[treeID] = tree if root != 0 { - tree.AddRoot(ctx, root) + tree.RebuiltAddRoot(ctx, root) } return true @@ -201,12 +216,12 @@ func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) { } } -// ListRoots returns a listing of all initialized trees and their root -// nodes. +// RebuiltListRoots returns a listing of all initialized trees and +// their root nodes. // // Do not mutate the set of roots for a tree; it is a pointer to the // RebuiltForrest's internal set! -func (ts *RebuiltForrest) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { +func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { _ = ts.treesMu.Lock(ctx) defer ts.treesMu.Unlock() ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 820913e..3fff9b2 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -37,9 +37,9 @@ type RebuiltTree struct { // derived from tree.Roots, which is why it's OK if they get // evicted. // - // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) - // 2. tree.Items() = tree.forrest.incItems.Load(tree.ID) - // 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID) + // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) + // 2. tree.RebuiltItems() = tree.forrest.incItems.Load(tree.ID) + // 3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Load(tree.ID) } // evictable member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////// @@ -129,23 +129,23 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati } } -// evictable members 2 and 3: .Items() and .PotentialItems() /////////////////////////////////////////////////////////// +// evictable members 2 and 3: .RebuiltItems() and .RebuiltPotentialItems() ///////////////////////////////////////////// -// Items returns a map of the items contained in this tree. +// RebuiltItems 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) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] { +func (tree *RebuiltTree) RebuiltItems(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.forrest.incItems, tree.Roots.HasAny) } -// PotentialItems returns a map of items that could be added to this -// tree with .AddRoot(). +// RebuiltPotentialItems 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) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] { +func (tree *RebuiltTree) RebuiltPotentialItems(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, &tree.forrest.excItems, func(roots containers.Set[btrfsvol.LogicalAddr]) bool { @@ -198,7 +198,7 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr index.Store(itemKey, newPtr) stats.NumItems++ } else { - if tree.ShouldReplace(oldPtr.Node, newPtr.Node) { + if tree.RebuiltShouldReplace(oldPtr.Node, newPtr.Node) { index.Store(itemKey, newPtr) } stats.NumDups++ @@ -216,9 +216,11 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr }) } -func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool { - oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner) - newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner) +// main public API ///////////////////////////////////////////////////////////////////////////////////////////////////// + +func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool { + oldDist, _ := tree.RebuiltCOWDistance(tree.forrest.graph.Nodes[oldNode].Owner) + newDist, _ := tree.RebuiltCOWDistance(tree.forrest.graph.Nodes[newNode].Owner) switch { case newDist < oldDist: // Replace the old one with the new lower-dist one. @@ -248,8 +250,6 @@ func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bo } } -// .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// - type rootStats struct { Leafs textui.Portion[int] AddedLeafs int @@ -261,10 +261,10 @@ func (s rootStats) String() string { 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) { +// 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. +func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { tree.mu.Lock() defer tree.mu.Unlock() ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) @@ -306,11 +306,9 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA tree.forrest.cb.AddedRoot(ctx, tree.ID, rootNode) } -// main public API ///////////////////////////////////////////////////////////////////////////////////////////////////// - -// COWDistance returns how many COW-snapshots down the 'tree' is from -// the 'parent'. -func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) { +// RebuiltCOWDistance returns how many COW-snapshots down the 'tree' +// is from the 'parent'. +func (tree *RebuiltTree) RebuiltCOWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) { for { if parentID == tree.ID { return dist, true @@ -325,18 +323,18 @@ func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok boo // ReadItem reads an item from a tree. func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsitem.Item { - ptr, ok := tree.Items(ctx).Load(key) + ptr, ok := tree.RebuiltItems(ctx).Load(key) if !ok { panic(fmt.Errorf("should not happen: btrfsutil.RebuiltTree.ReadItem called for not-included key: %v", key)) } return tree.forrest.readItem(ctx, ptr) } -// LeafToRoots returns the list of potential roots (to pass to -// .AddRoot) that include a given leaf-node. -func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { +// RebuiltLeafToRoots returns the list of potential roots (to pass to +// .RebuiltAddRoot) that include a given leaf-node. +func (tree *RebuiltTree) RebuiltLeafToRoots(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", + panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): not a leaf", tree.ID, leaf)) } tree.mu.RLock() @@ -344,7 +342,7 @@ func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalA ret := make(containers.Set[btrfsvol.LogicalAddr]) 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", + 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) -- cgit v1.2.3-2-g168b