summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go9
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go148
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go20
-rw-r--r--lib/containers/sortedmap.go4
-rw-r--r--lib/textui/log.go16
5 files changed, 135 insertions, 62 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
index 791e646..c0b7698 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
@@ -17,6 +17,7 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
// RebuiltForrest is an abstraction for rebuilding and accessing
@@ -61,7 +62,9 @@ type RebuiltForrest struct {
cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
// mutable
- trees map[btrfsprim.ObjID]*RebuiltTree
+ trees map[btrfsprim.ObjID]*RebuiltTree
+ allItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex]
+ incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex]
}
// NewRebuiltForrest returns a new RebuiltForrest instance. All of
@@ -81,7 +84,9 @@ func NewRebuiltForrest(
cbLookupRoot: cbLookupRoot,
cbLookupUUID: cbLookupUUID,
- trees: make(map[btrfsprim.ObjID]*RebuiltTree),
+ trees: make(map[btrfsprim.ObjID]*RebuiltTree),
+ allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(16)),
+ incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(16)),
}
}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
index 1fc1f52..acc71db 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
@@ -30,14 +30,12 @@ type RebuiltTree struct {
ParentGen btrfsprim.Generation // offset of this tree's root item
forrest *RebuiltForrest
- // all leafs (lvl=0) that pass .isOwnerOK, even if not in the tree
+ // all leafs (lvl=0) that pass .isOwnerOK, whether or not they're in the tree
leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]
- keys containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
// mutable
Roots containers.Set[btrfsvol.LogicalAddr]
Leafs containers.Set[btrfsvol.LogicalAddr]
- Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
}
// initializaton (called by `RebuiltForrest.Tree()`) ///////////////////////////////////////////////////////////////////
@@ -106,16 +104,6 @@ func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAdd
roots = containers.NewSet[btrfsvol.LogicalAddr](node)
}
index[node] = roots
-
- // tree.keys
- for i, key := range tree.forrest.graph.Nodes[node].Items {
- if oldPtr, ok := tree.keys.Load(key); !ok || tree.shouldReplace(oldPtr.Node, node) {
- tree.keys.Store(key, keyio.ItemPtr{
- Node: node,
- Idx: i,
- })
- }
- }
}
// isOwnerOK returns whether it is permissible for a node with
@@ -135,14 +123,14 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
// .AddRoot() //////////////////////////////////////////////////////////////////////////////////////////////////////////
type rootStats struct {
- Leafs textui.Portion[int]
- AddedItems int
- ReplacedItems int
+ Leafs textui.Portion[int]
+ AddedLeafs int
+ AddedItems int
}
func (s rootStats) String() string {
- return textui.Sprintf("%v (added %v items, replaced %v items)",
- s.Leafs, s.AddedItems, s.ReplacedItems)
+ 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
@@ -158,29 +146,109 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA
for i, leaf := range maps.SortedKeys(tree.leafToRoots) {
stats.Leafs.N = i
progressWriter.Set(stats)
+
if tree.Leafs.Has(leaf) || !tree.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(tree.leafToRoots)
+ progressWriter.Set(stats)
+ progressWriter.Done()
+}
+
+// .Items() and .PotentialItems() //////////////////////////////////////////////////////////////////////////////////////
+
+// Items 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, keyio.ItemPtr] {
+ ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-inc-items", fmt.Sprintf("tree=%v", tree.ID))
+ return tree.items(ctx, tree.forrest.incItems, maps.SortedKeys(tree.Leafs))
+}
+
+// PotentialItems returns a map of items that could be added to this
+// tree with .AddRoot().
+//
+// 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, 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))
+}
+
+type itemIndex struct {
+ NumDups int
+ Leafs containers.Set[btrfsvol.LogicalAddr]
+ Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
+}
+
+type itemStats struct {
+ Leafs textui.Portion[int]
+ NumItems int
+ NumDups int
+}
+
+func (s itemStats) String() string {
+ return textui.Sprintf("%v (%v items, %v dups)",
+ s.Leafs, s.NumItems, s.NumDups)
+}
+
+func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex], leafs []btrfsvol.LogicalAddr) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
+ index := cache.GetOrElse(tree.ID, func() *itemIndex {
+ return &itemIndex{
+ Leafs: make(containers.Set[btrfsvol.LogicalAddr]),
+ }
+ })
+
+ var stats itemStats
+ stats.Leafs.D = len(leafs)
+ progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+ progress := func(doneLeafs int) {
+ stats.Leafs.N = doneLeafs
+ stats.NumItems = index.Items.Len()
+ stats.NumDups = index.NumDups
+ progressWriter.Set(stats)
+ }
+
+ for i, leaf := range leafs {
+ if index.Leafs.Has(leaf) {
+ continue
+ }
+ progress(i)
+ index.Leafs.Insert(leaf)
for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
newPtr := keyio.ItemPtr{
Node: leaf,
Idx: j,
}
- if oldPtr, exists := tree.Items.Load(itemKey); !exists {
- tree.Items.Store(itemKey, newPtr)
- stats.AddedItems++
- } else if tree.shouldReplace(oldPtr.Node, newPtr.Node) {
- tree.Items.Store(itemKey, newPtr)
- stats.ReplacedItems++
+ if oldPtr, exists := index.Items.Load(itemKey); !exists {
+ index.Items.Store(itemKey, newPtr)
+ } else {
+ index.NumDups++
+ if tree.shouldReplace(oldPtr.Node, newPtr.Node) {
+ index.Items.Store(itemKey, newPtr)
+ }
}
- tree.forrest.cbAddedItem(ctx, tree.ID, itemKey)
- progressWriter.Set(stats)
+ progress(i)
}
}
- stats.Leafs.N = len(tree.leafToRoots)
- progressWriter.Set(stats)
- progressWriter.Done()
+ if stats.Leafs.N > 0 {
+ progress(len(leafs))
+ progressWriter.Done()
+ }
+
+ return &index.Items
}
func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
@@ -233,13 +301,13 @@ func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok boo
}
// Resolve a key to a keyio.ItemPtr.
-func (tree *RebuiltTree) Resolve(key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) {
- return tree.Items.Load(key)
+func (tree *RebuiltTree) Resolve(ctx context.Context, key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) {
+ return tree.Items(ctx).Load(key)
}
// Load reads an item from a tree.
func (tree *RebuiltTree) Load(ctx context.Context, key btrfsprim.Key) (item btrfsitem.Item, ok bool) {
- ptr, ok := tree.Resolve(key)
+ ptr, ok := tree.Resolve(ctx, key)
if !ok {
return nil, false
}
@@ -247,16 +315,16 @@ func (tree *RebuiltTree) Load(ctx context.Context, key btrfsprim.Key) (item btrf
}
// Search searches for an item from a tree.
-func (tree *RebuiltTree) Search(fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) {
- k, _, ok := tree.Items.Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int {
+func (tree *RebuiltTree) Search(ctx context.Context, fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) {
+ k, _, ok := tree.Items(ctx).Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int {
return fn(k)
})
return k, ok
}
// Search searches for a range of items from a tree.
-func (tree *RebuiltTree) SearchAll(fn func(btrfsprim.Key) int) []btrfsprim.Key {
- kvs := tree.Items.SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int {
+func (tree *RebuiltTree) SearchAll(ctx context.Context, fn func(btrfsprim.Key) int) []btrfsprim.Key {
+ kvs := tree.Items(ctx).SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int {
return fn(k)
})
if len(kvs) == 0 {
@@ -289,11 +357,3 @@ func (tree *RebuiltTree) LeafToRoots(leaf btrfsvol.LogicalAddr) containers.Set[b
}
return ret
}
-
-// Keys returns a map of all keys in node that would be valid in this tree.
-//
-// Do not mutate the returned map; it is a pointer to the
-// RebuiltTree's internal map!
-func (tree *RebuiltTree) Keys() *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
- return &tree.keys
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
index b4feacf..85270d7 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
@@ -413,7 +413,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr
ObjectID: objID,
ItemType: typ,
}
- if key, ok := o.rebuilt.Tree(ctx, treeID).Search(func(key btrfsprim.Key) int {
+ if key, ok := o.rebuilt.Tree(ctx, treeID).Search(ctx, func(key btrfsprim.Key) int {
key.Offset = 0
return tgt.Cmp(key)
}); ok {
@@ -423,7 +423,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr
// OK, we need to insert it
wants := make(containers.Set[btrfsvol.LogicalAddr])
- o.rebuilt.Tree(ctx, treeID).Keys().Subrange(
+ 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))
@@ -453,14 +453,14 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt
// check if we already have it
- if _, ok := o.rebuilt.Tree(ctx, treeID).Search(tgt.Cmp); ok {
+ if _, ok := o.rebuilt.Tree(ctx, treeID).Search(ctx, tgt.Cmp); ok {
return true
}
// OK, we need to insert it
wants := make(containers.Set[btrfsvol.LogicalAddr])
- o.rebuilt.Tree(ctx, treeID).Keys().Subrange(
+ 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))
@@ -482,12 +482,12 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID
ObjectID: objID,
ItemType: typ,
}
- keys := o.rebuilt.Tree(ctx, treeID).SearchAll(func(key btrfsprim.Key) int {
+ keys := o.rebuilt.Tree(ctx, treeID).SearchAll(ctx, func(key btrfsprim.Key) int {
key.Offset = 0
return tgt.Cmp(key)
})
for _, itemKey := range keys {
- itemPtr, ok := o.rebuilt.Tree(ctx, treeID).Resolve(itemKey)
+ itemPtr, ok := o.rebuilt.Tree(ctx, treeID).Resolve(ctx, itemKey)
if !ok {
o.ioErr(ctx, fmt.Errorf("could not resolve previously read item: %v", itemKey))
}
@@ -499,7 +499,7 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID
// OK, we need to insert it
wants := make(containers.Set[btrfsvol.LogicalAddr])
- o.rebuilt.Tree(ctx, treeID).Keys().Subrange(
+ o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
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) {
@@ -536,7 +536,7 @@ func (o *rebuilder) _wantRange(
}
sizeFn := func(key btrfsprim.Key) (uint64, error) {
- ptr, ok := o.rebuilt.Tree(ctx, treeID).Keys().Load(key)
+ ptr, ok := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Load(key)
if !ok {
panic(fmt.Errorf("should not happen: could not load key: %v", key))
}
@@ -558,7 +558,7 @@ func (o *rebuilder) _wantRange(
ItemType: typ,
Offset: end - 1,
}
- runKeys := o.rebuilt.Tree(ctx, treeID).SearchAll(func(key btrfsprim.Key) int {
+ runKeys := o.rebuilt.Tree(ctx, treeID).SearchAll(ctx, func(key btrfsprim.Key) int {
switch {
case runMin.Cmp(key) < 0:
return 1
@@ -645,7 +645,7 @@ func (o *rebuilder) _wantRange(
ItemType: typ,
Offset: gap.End - 1,
}
- o.rebuilt.Tree(ctx, treeID).Keys().Subrange(
+ o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
func(key btrfsprim.Key, _ keyio.ItemPtr) int {
switch {
case runMin.Cmp(key) < 0:
diff --git a/lib/containers/sortedmap.go b/lib/containers/sortedmap.go
index d6d2f9e..52308c9 100644
--- a/lib/containers/sortedmap.go
+++ b/lib/containers/sortedmap.go
@@ -92,3 +92,7 @@ func (m *SortedMap[K, V]) SearchAll(fn func(K, V) int) []OrderedKV[K, V] {
return fn(kv.K, kv.V)
})
}
+
+func (m *SortedMap[K, V]) Len() int {
+ return m.inner.Len()
+}
diff --git a/lib/textui/log.go b/lib/textui/log.go
index 801e9eb..da303dd 100644
--- a/lib/textui/log.go
+++ b/lib/textui/log.go
@@ -317,18 +317,22 @@ func fieldOrd(key string) int {
return -25
// step=rebuild (any substep)
case "btrfsinspect.rebuild-nodes.rebuild.want.key":
- return -7
+ return -9
case "btrfsinspect.rebuild-nodes.rebuild.want.reason":
- return -6
+ return -8
case "btrfsinspect.rebuild-nodes.rebuild.add-tree":
- return -5
+ return -7
case "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep":
- return -4
+ return -6
case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key":
- return -3
+ return -5
case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason":
- return -2
+ return -4
case "btrfsinspect.rebuild-nodes.rebuild.add-root":
+ return -3
+ case "btrfsinspect.rebuild-nodes.rebuild.index-inc-items":
+ return -2
+ case "btrfsinspect.rebuild-nodes.rebuild.index-all-items":
return -1
// other ///////////////////////////////////////////////////////////////
generated by cgit v1.1-4-g5e80 at 2024-06-28 10:48:30 +0000