summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go51
-rw-r--r--lib/btrfsutil/rebuilt_tree.go58
2 files changed, 61 insertions, 48 deletions
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)
generated by cgit v1.1-4-g5e80 at 2024-07-04 18:52:12 +0000