From 5590315b11557aa48999d09700631ad9239ce03b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 27 Dec 2022 01:14:34 -0700 Subject: rebuildnodes: Optimize: Try to avoid disk access for DIR_INDEX --- .../btrfsinspect/rebuildnodes/rebuild.go | 32 ++++++++++++---------- 1 file changed, 18 insertions(+), 14 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 7e55732..4f5990e 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -5,6 +5,7 @@ package rebuildnodes import ( + "bytes" "context" "fmt" "sort" @@ -456,12 +457,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt return false } -// wantFunc implements rebuildCallbacks. -func (o *rebuilder) wantFunc(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) { - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason) - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", - fmt.Sprintf("tree=%v key={%v %v ?} +func", treeID, objID, typ)) - +func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) { if !o.rebuilt.AddTree(ctx, treeID) { o.itemQueue = append(o.itemQueue, o.curKey) return @@ -478,11 +474,11 @@ func (o *rebuilder) wantFunc(ctx context.Context, reason string, treeID btrfspri return tgt.Cmp(key) }) for _, itemKey := range keys { - itemBody, ok := o.rebuilt.Load(ctx, treeID, itemKey) + itemPtr, ok := o.rebuilt.Resolve(ctx, treeID, itemKey) if !ok { - o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", itemKey)) + o.ioErr(ctx, fmt.Errorf("could not resolve previously read item: %v", itemKey)) } - if fn(itemBody) { + if fn(itemPtr) { return } } @@ -493,11 +489,7 @@ func (o *rebuilder) wantFunc(ctx context.Context, reason string, treeID btrfspri o.rebuilt.Keys(treeID).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, func(k btrfsprim.Key, v keyio.ItemPtr) bool { - itemBody, ok := o.keyIO.ReadItem(ctx, v) - if !ok { - o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v at %v", k, v)) - } - if fn(itemBody) { + if fn(v) { wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node)) } return true @@ -505,6 +497,18 @@ func (o *rebuilder) wantFunc(ctx context.Context, reason string, treeID btrfspri o.wantAugment(ctx, treeID, wants) } +// wantDirIndex implements rebuildCallbacks. +func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) { + typ := btrfsitem.DIR_INDEX_KEY + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason) + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", + fmt.Sprintf("tree=%v key={%v %v ?} name=%q", treeID, objID, typ, name)) + o._wantFunc(ctx, treeID, objID, typ, func(ptr keyio.ItemPtr) bool { + itemName, ok := o.keyIO.Names[ptr] + return ok && bytes.Equal(itemName, name) + }) +} + func (o *rebuilder) _wantRange( ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, -- cgit v1.2.3-2-g168b From 73b1da4e88e7ce788151f3d263b309f20d7c1824 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 30 Dec 2022 22:12:30 -0700 Subject: rebuildnodes: Optimize: Avoid unnescessary disk access for existence-check --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 4f5990e..7f428f3 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -440,7 +440,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt // check if we already have it - if _, ok := o.rebuilt.Load(ctx, treeID, tgt); ok { + if _, ok := o.rebuilt.Search(ctx, treeID, tgt.Cmp); ok { return true } -- cgit v1.2.3-2-g168b From 52c1eb7a44f425b22f89e63a11aeb089f856a680 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 30 Dec 2022 22:13:47 -0700 Subject: rebuildnodes: Optimize: Rethink queue ordering Hopefully this is more sequential, which should help things. --- .../btrfsinspect/rebuildnodes/rebuild.go | 43 +++++++++++----------- 1 file changed, 22 insertions(+), 21 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 7f428f3..b6c1359 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -33,10 +33,10 @@ type keyAndTree struct { } func (a keyAndTree) Cmp(b keyAndTree) int { - if d := a.Key.Cmp(b.Key); d != 0 { + if d := containers.NativeCmp(a.TreeID, b.TreeID); d != 0 { return d } - return containers.NativeCmp(a.TreeID, b.TreeID) + return a.Key.Cmp(b.Key) } func (o keyAndTree) String() string { @@ -51,8 +51,8 @@ type rebuilder struct { keyIO *keyio.Handle curKey keyAndTree - treeQueue []btrfsprim.ObjID - itemQueue []keyAndTree + treeQueue containers.Set[btrfsprim.ObjID] + itemQueue containers.Set[keyAndTree] augmentQueue map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int } @@ -95,15 +95,16 @@ func (o *rebuilder) ioErr(ctx context.Context, err error) { func (o *rebuilder) rebuild(_ctx context.Context) error { // Initialize + o.itemQueue = make(containers.Set[keyAndTree]) o.augmentQueue = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) // Seed the queue - o.treeQueue = []btrfsprim.ObjID{ + o.treeQueue = containers.NewSet[btrfsprim.ObjID]( btrfsprim.ROOT_TREE_OBJECTID, btrfsprim.CHUNK_TREE_OBJECTID, // btrfsprim.TREE_LOG_OBJECTID, // TODO(lukeshu): Special LOG_TREE handling btrfsprim.BLOCK_GROUP_TREE_OBJECTID, - } + ) for passNum := 0; len(o.treeQueue) > 0 || len(o.itemQueue) > 0 || len(o.augmentQueue) > 0; passNum++ { passCtx := dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.rebuild.pass", passNum) @@ -111,20 +112,20 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { // Add items to the queue (drain o.treeQueue, fill o.itemQueue) stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items") treeQueue := o.treeQueue - o.treeQueue = nil - sort.Slice(treeQueue, func(i, j int) bool { - return treeQueue[i] < treeQueue[j] - }) + o.treeQueue = make(containers.Set[btrfsprim.ObjID]) // Because trees can be wildly different sizes, it's impossible to have a meaningful // progress percentage here. - for _, treeID := range treeQueue { + for _, treeID := range maps.SortedKeys(treeQueue) { o.rebuilt.AddTree(stepCtx, treeID) } // Handle items in the queue (drain o.itemQueue, fill o.augmentQueue and o.treeQueue) stepCtx = dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items") - itemQueue := o.itemQueue - o.itemQueue = nil + itemQueue := maps.Keys(o.itemQueue) + o.itemQueue = make(containers.Set[keyAndTree]) + sort.Slice(itemQueue, func(i, j int) bool { + return itemQueue[i].Cmp(itemQueue[j]) < 0 + }) var progress textui.Portion[int] progress.D = len(itemQueue) progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) @@ -143,7 +144,7 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { Body: itemBody, }) if key.ItemType == btrfsitem.ROOT_ITEM_KEY { - o.treeQueue = append(o.treeQueue, key.ObjectID) + o.treeQueue.Insert(key.ObjectID) } } progress.N = len(itemQueue) @@ -178,7 +179,7 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { } func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { - o.itemQueue = append(o.itemQueue, keyAndTree{ + o.itemQueue.Insert(keyAndTree{ TreeID: tree, Key: key, }) @@ -190,7 +191,7 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off fmt.Sprintf("tree=%v key={%v %v ?}", btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY)) key, ok := o._want(ctx, btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY) if !ok { - o.itemQueue = append(o.itemQueue, o.curKey) + o.itemQueue.Insert(o.curKey) return 0, btrfsitem.Root{}, false } itemBody, ok := o.rebuilt.Load(ctx, btrfsprim.ROOT_TREE_OBJECTID, key) @@ -215,7 +216,7 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "resolve parent UUID") ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: key}) if ok := o._wantOff(ctx, btrfsprim.UUID_TREE_OBJECTID, key); !ok { - o.itemQueue = append(o.itemQueue, o.curKey) + o.itemQueue.Insert(o.curKey) return 0, false } itemBody, ok := o.rebuilt.Load(ctx, btrfsprim.UUID_TREE_OBJECTID, key) @@ -390,7 +391,7 @@ func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.Ob func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) { if !o.rebuilt.AddTree(ctx, treeID) { - o.itemQueue = append(o.itemQueue, o.curKey) + o.itemQueue.Insert(o.curKey) return btrfsprim.Key{}, false } @@ -434,7 +435,7 @@ func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt btrfsprim.Key) (ok bool) { if !o.rebuilt.AddTree(ctx, treeID) { - o.itemQueue = append(o.itemQueue, o.curKey) + o.itemQueue.Insert(o.curKey) return false } @@ -459,7 +460,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) { if !o.rebuilt.AddTree(ctx, treeID) { - o.itemQueue = append(o.itemQueue, o.curKey) + o.itemQueue.Insert(o.curKey) return } @@ -518,7 +519,7 @@ func (o *rebuilder) _wantRange( fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) if !o.rebuilt.AddTree(ctx, treeID) { - o.itemQueue = append(o.itemQueue, o.curKey) + o.itemQueue.Insert(o.curKey) return } -- cgit v1.2.3-2-g168b From 8efc82d0b1a167830970135c78d173667080b116 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 28 Dec 2022 18:49:09 -0700 Subject: rebuildnodes: Support graceful shutdown --- .../btrfsinspect/rebuildnodes/rebuild.go | 58 +++++++++++++--------- 1 file changed, 35 insertions(+), 23 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index b6c1359..26f2a44 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -44,47 +44,38 @@ func (o keyAndTree) String() string { } type rebuilder struct { - sb btrfstree.Superblock - rebuilt *btrees.RebuiltTrees - + sb btrfstree.Superblock graph graph.Graph keyIO *keyio.Handle + rebuilt *btrees.RebuiltTrees + curKey keyAndTree treeQueue containers.Set[btrfsprim.ObjID] itemQueue containers.Set[keyAndTree] augmentQueue map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int } -func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], error) { - _ctx := ctx +type Rebuilder interface { + Rebuild(context.Context) error + ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] +} - ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "read-fs-data") - dlog.Info(ctx, "Reading superblock...") - sb, err := fs.Superblock() - if err != nil { - return nil, err - } - nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging +func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (Rebuilder, error) { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.step", "read-fs-data") + sb, nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging if err != nil { return nil, err } - ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "rebuild") - dlog.Info(ctx, "Rebuilding node tree...") o := &rebuilder{ - sb: *sb, - + sb: sb, graph: nodeGraph, keyIO: keyIO, } - o.rebuilt = btrees.NewRebuiltTrees(*sb, nodeGraph, keyIO, + o.rebuilt = btrees.NewRebuiltTrees(sb, nodeGraph, keyIO, o.cbAddedItem, o.cbLookupRoot, o.cbLookupUUID) - if err := o.rebuild(ctx); err != nil { - return nil, err - } - - return o.rebuilt.ListRoots(), nil + return o, nil } func (o *rebuilder) ioErr(ctx context.Context, err error) { @@ -93,7 +84,13 @@ func (o *rebuilder) ioErr(ctx context.Context, err error) { panic(err) } -func (o *rebuilder) rebuild(_ctx context.Context) error { +func (o *rebuilder) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { + return o.rebuilt.ListRoots() +} + +func (o *rebuilder) Rebuild(_ctx context.Context) error { + _ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "rebuild") + // Initialize o.itemQueue = make(containers.Set[keyAndTree]) o.augmentQueue = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) @@ -116,6 +113,9 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { // Because trees can be wildly different sizes, it's impossible to have a meaningful // progress percentage here. for _, treeID := range maps.SortedKeys(treeQueue) { + if err := _ctx.Err(); err != nil { + return err + } o.rebuilt.AddTree(stepCtx, treeID) } @@ -134,6 +134,10 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key) progress.N = i progressWriter.Set(progress) + if err := _ctx.Err(); err != nil { + progressWriter.Done() + return err + } o.curKey = key itemBody, ok := o.rebuilt.Load(itemCtx, key.TreeID, key.Key) if !ok { @@ -157,6 +161,9 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { progress.N = 0 progress.D = 0 for _, treeID := range maps.SortedKeys(o.augmentQueue) { + if err := _ctx.Err(); err != nil { + return err + } treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, o.augmentQueue[treeID]) progress.D += len(resolvedAugments[treeID]) @@ -167,6 +174,11 @@ func (o *rebuilder) rebuild(_ctx context.Context) error { for _, treeID := range maps.SortedKeys(resolvedAugments) { treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) for _, nodeAddr := range maps.SortedKeys(resolvedAugments[treeID]) { + if err := _ctx.Err(); err != nil { + progressWriter.Set(progress) + progressWriter.Done() + return err + } progressWriter.Set(progress) o.rebuilt.AddRoot(treeCtx, treeID, nodeAddr) progress.N++ -- cgit v1.2.3-2-g168b From 1f8734f894ac5fdaee25bba5b1e3ffd10b31ef4e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 30 Dec 2022 19:45:07 -0700 Subject: rebuildnodes/btrees: Refactor to split the forrest from the trees --- .../btrfsinspect/rebuildnodes/rebuild.go | 52 +++++++++++----------- 1 file changed, 26 insertions(+), 26 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 26f2a44..b4feacf 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -48,7 +48,7 @@ type rebuilder struct { graph graph.Graph keyIO *keyio.Handle - rebuilt *btrees.RebuiltTrees + rebuilt *btrees.RebuiltForrest curKey keyAndTree treeQueue containers.Set[btrfsprim.ObjID] @@ -73,7 +73,7 @@ func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec graph: nodeGraph, keyIO: keyIO, } - o.rebuilt = btrees.NewRebuiltTrees(sb, nodeGraph, keyIO, + o.rebuilt = btrees.NewRebuiltForrest(sb, nodeGraph, keyIO, o.cbAddedItem, o.cbLookupRoot, o.cbLookupUUID) return o, nil } @@ -116,7 +116,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { if err := _ctx.Err(); err != nil { return err } - o.rebuilt.AddTree(stepCtx, treeID) + o.rebuilt.Tree(stepCtx, treeID) } // Handle items in the queue (drain o.itemQueue, fill o.augmentQueue and o.treeQueue) @@ -139,7 +139,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { return err } o.curKey = key - itemBody, ok := o.rebuilt.Load(itemCtx, key.TreeID, key.Key) + itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).Load(itemCtx, key.Key) if !ok { o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -180,7 +180,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { return err } progressWriter.Set(progress) - o.rebuilt.AddRoot(treeCtx, treeID, nodeAddr) + o.rebuilt.Tree(treeCtx, treeID).AddRoot(treeCtx, nodeAddr) progress.N++ } } @@ -206,7 +206,7 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off o.itemQueue.Insert(o.curKey) return 0, btrfsitem.Root{}, false } - itemBody, ok := o.rebuilt.Load(ctx, btrfsprim.ROOT_TREE_OBJECTID, key) + itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.ROOT_TREE_OBJECTID).Load(ctx, key) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -231,7 +231,7 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b o.itemQueue.Insert(o.curKey) return 0, false } - itemBody, ok := o.rebuilt.Load(ctx, btrfsprim.UUID_TREE_OBJECTID, key) + itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.UUID_TREE_OBJECTID).Load(ctx, key) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -376,7 +376,7 @@ func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, cho } choicesWithDist := make(map[btrfsvol.LogicalAddr]int, len(choices)) for choice := range choices { - dist, ok := o.rebuilt.COWDistance(ctx, treeID, o.graph.Nodes[choice].Owner) + dist, ok := o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner) if !ok { panic(fmt.Errorf("should not happen: .wantAugment called for tree=%v with invalid choice=%v", treeID, choice)) } @@ -402,7 +402,7 @@ func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.Ob } func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) { - if !o.rebuilt.AddTree(ctx, treeID) { + if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return btrfsprim.Key{}, false } @@ -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.Search(ctx, treeID, func(key btrfsprim.Key) int { + if key, ok := o.rebuilt.Tree(ctx, treeID).Search(func(key btrfsprim.Key) int { key.Offset = 0 return tgt.Cmp(key) }); ok { @@ -423,10 +423,10 @@ 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.Keys(treeID).Subrange( + o.rebuilt.Tree(ctx, treeID).Keys().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.LeafToRoots(ctx, treeID, v.Node)) + wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) return true }) o.wantAugment(ctx, treeID, wants) @@ -446,24 +446,24 @@ func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim } func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt btrfsprim.Key) (ok bool) { - if !o.rebuilt.AddTree(ctx, treeID) { + if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return false } // check if we already have it - if _, ok := o.rebuilt.Search(ctx, treeID, tgt.Cmp); ok { + if _, ok := o.rebuilt.Tree(ctx, treeID).Search(tgt.Cmp); ok { return true } // OK, we need to insert it wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Keys(treeID).Subrange( + o.rebuilt.Tree(ctx, treeID).Keys().Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) }, func(_ btrfsprim.Key, v keyio.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node)) + wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) return true }) o.wantAugment(ctx, treeID, wants) @@ -471,7 +471,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt } func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) { - if !o.rebuilt.AddTree(ctx, treeID) { + if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return } @@ -482,12 +482,12 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID ObjectID: objID, ItemType: typ, } - keys := o.rebuilt.SearchAll(ctx, treeID, func(key btrfsprim.Key) int { + keys := o.rebuilt.Tree(ctx, treeID).SearchAll(func(key btrfsprim.Key) int { key.Offset = 0 return tgt.Cmp(key) }) for _, itemKey := range keys { - itemPtr, ok := o.rebuilt.Resolve(ctx, treeID, itemKey) + itemPtr, ok := o.rebuilt.Tree(ctx, treeID).Resolve(itemKey) if !ok { o.ioErr(ctx, fmt.Errorf("could not resolve previously read item: %v", itemKey)) } @@ -499,11 +499,11 @@ 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.Keys(treeID).Subrange( + o.rebuilt.Tree(ctx, treeID).Keys().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) { - wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node)) + wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) } return true }) @@ -530,13 +530,13 @@ func (o *rebuilder) _wantRange( ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) - if !o.rebuilt.AddTree(ctx, treeID) { + if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return } sizeFn := func(key btrfsprim.Key) (uint64, error) { - ptr, ok := o.rebuilt.Keys(treeID).Load(key) + ptr, ok := o.rebuilt.Tree(ctx, treeID).Keys().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.SearchAll(ctx, treeID, func(key btrfsprim.Key) int { + runKeys := o.rebuilt.Tree(ctx, treeID).SearchAll(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.Keys(treeID).Subrange( + o.rebuilt.Tree(ctx, treeID).Keys().Subrange( func(key btrfsprim.Key, _ keyio.ItemPtr) int { switch { case runMin.Cmp(key) < 0: @@ -680,7 +680,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.LeafToRoots(ctx, treeID, v.Node)) + o.wantAugment(wantCtx, treeID, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(v.Node)) last = runEnd return true -- cgit v1.2.3-2-g168b From e18c0e92ba35bb863f7375b190b0448d5fa65d33 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 30 Dec 2022 21:52:57 -0700 Subject: rebuildnodes/btrees: Allow item rbtrees to be evicted --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') 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: -- cgit v1.2.3-2-g168b From 3c3ec3e4ebb93b8e09a5a93bd26ace84f271223e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 30 Dec 2022 22:36:05 -0700 Subject: rebuildnodes/btrees.RebuiltTree: Try to remove methods Now that .Items() is public, some of the search methods are superfluous, and in fact all .SearchAll calls would be more efficient as .Items.Subrange calls. And rename .Load to .ReadItem, so that grepping for it doesn't mix up with .Items.Load. --- .../btrfsinspect/rebuildnodes/rebuild.go | 133 +++++++++++---------- 1 file changed, 69 insertions(+), 64 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 85270d7..dcf77b8 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -139,7 +139,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { return err } o.curKey = key - itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).Load(itemCtx, key.Key) + itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).ReadItem(itemCtx, key.Key) if !ok { o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -206,7 +206,7 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off o.itemQueue.Insert(o.curKey) return 0, btrfsitem.Root{}, false } - itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.ROOT_TREE_OBJECTID).Load(ctx, key) + itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.ROOT_TREE_OBJECTID).ReadItem(ctx, key) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -231,7 +231,7 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b o.itemQueue.Insert(o.curKey) return 0, false } - itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.UUID_TREE_OBJECTID).Load(ctx, key) + itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.UUID_TREE_OBJECTID).ReadItem(ctx, key) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -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(ctx, func(key btrfsprim.Key) int { + if key, _, ok := o.rebuilt.Tree(ctx, treeID).Items(ctx).Search(func(key btrfsprim.Key, _ keyio.ItemPtr) int { key.Offset = 0 return tgt.Cmp(key) }); ok { @@ -453,7 +453,7 @@ 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(ctx, tgt.Cmp); ok { + if _, ok := o.rebuilt.Tree(ctx, treeID).Items(ctx).Load(tgt); ok { return true } @@ -482,18 +482,20 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID ObjectID: objID, ItemType: typ, } - 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(ctx, itemKey) - if !ok { - o.ioErr(ctx, fmt.Errorf("could not resolve previously read item: %v", itemKey)) - } - if fn(itemPtr) { - return - } + found := false + o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange( + func(key btrfsprim.Key, _ keyio.ItemPtr) int { + key.Offset = 0 + return tgt.Cmp(key) + }, + func(_ btrfsprim.Key, itemPtr keyio.ItemPtr) bool { + if fn(itemPtr) { + found = true + } + return !found + }) + if found { + return } // OK, we need to insert it @@ -558,16 +560,6 @@ func (o *rebuilder) _wantRange( ItemType: typ, Offset: end - 1, } - runKeys := o.rebuilt.Tree(ctx, treeID).SearchAll(ctx, func(key btrfsprim.Key) int { - switch { - case runMin.Cmp(key) < 0: - return 1 - case runMax.Cmp(key) > 0: - return -1 - default: - return 0 - } - }) // Step 2: Build a listing of the gaps. // @@ -586,50 +578,63 @@ func (o *rebuilder) _wantRange( Beg: beg, End: end, }) - for _, runKey := range runKeys { - runSize, err := sizeFn(runKey) - if err != nil { - o.fsErr(ctx, fmt.Errorf("tree=%v key=%v: %w", treeID, runKey, err)) - } - if runSize == 0 { - continue - } - runBeg := runKey.Offset - runEnd := runBeg + runSize - if runEnd <= beg { - continue - } - overlappingGaps := gaps.SearchRange(func(gap gap) int { + o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange( + func(key btrfsprim.Key, _ keyio.ItemPtr) int { switch { - case gap.End <= runBeg: + case runMin.Cmp(key) < 0: return 1 - case runEnd <= gap.Beg: + case runMax.Cmp(key) > 0: return -1 default: return 0 } - }) - if len(overlappingGaps) == 0 { - continue - } - gapsBeg := overlappingGaps[0].Beg - gapsEnd := overlappingGaps[len(overlappingGaps)-1].End - for _, gap := range overlappingGaps { - gaps.Delete(containers.NativeOrdered[uint64]{Val: gap.Beg}) - } - if gapsBeg < runBeg { - gaps.Insert(gap{ - Beg: gapsBeg, - End: runBeg, - }) - } - if gapsEnd > runEnd { - gaps.Insert(gap{ - Beg: runEnd, - End: gapsEnd, + }, + func(runKey btrfsprim.Key, _ keyio.ItemPtr) bool { + runSize, err := sizeFn(runKey) + if err != nil { + o.fsErr(ctx, fmt.Errorf("tree=%v key=%v: %w", treeID, runKey, err)) + return true + } + if runSize == 0 { + return true + } + runBeg := runKey.Offset + runEnd := runBeg + runSize + if runEnd <= beg { + return true + } + overlappingGaps := gaps.SearchRange(func(gap gap) int { + switch { + case gap.End <= runBeg: + return 1 + case runEnd <= gap.Beg: + return -1 + default: + return 0 + } }) - } - } + if len(overlappingGaps) == 0 { + return true + } + gapsBeg := overlappingGaps[0].Beg + gapsEnd := overlappingGaps[len(overlappingGaps)-1].End + for _, gap := range overlappingGaps { + gaps.Delete(containers.NativeOrdered[uint64]{Val: gap.Beg}) + } + if gapsBeg < runBeg { + gaps.Insert(gap{ + Beg: gapsBeg, + End: runBeg, + }) + } + if gapsEnd > runEnd { + gaps.Insert(gap{ + Beg: runEnd, + End: gapsEnd, + }) + } + return true + }) // Step 2: Fill each gap. _ = gaps.Walk(func(rbNode *containers.RBNode[gap]) error { -- cgit v1.2.3-2-g168b From e1302ac1f2685db057b7ecafe70f57ad17d533dc Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 31 Dec 2022 12:45:16 -0700 Subject: rebuildnodes: Parallelize I/O and CPU --- .../btrfsinspect/rebuildnodes/rebuild.go | 63 ++++++++++++++-------- 1 file changed, 42 insertions(+), 21 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index dcf77b8..cefa668 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -11,6 +11,7 @@ import ( "sort" "time" + "github.com/datawire/dlib/dgroup" "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" @@ -130,30 +131,50 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { progress.D = len(itemQueue) progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) - for i, key := range itemQueue { - itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key) - progress.N = i - progressWriter.Set(progress) - if err := _ctx.Err(); err != nil { - progressWriter.Done() - return err - } - o.curKey = key - itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).ReadItem(itemCtx, key.Key) - if !ok { - o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key)) + type keyAndBody struct { + keyAndTree + Body btrfsitem.Item + } + itemChan := make(chan keyAndBody, textui.Tunable(300)) // average items-per-node≈100; let's have a buffer of ~3 nodes + grp := dgroup.NewGroup(stepCtx, dgroup.GroupConfig{}) + grp.Go("io", func(stepCtx context.Context) error { + defer close(itemChan) + for _, key := range itemQueue { + if err := stepCtx.Err(); err != nil { + return err + } + itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key) + itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).ReadItem(itemCtx, key.Key) + if !ok { + o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key)) + } + itemChan <- keyAndBody{ + keyAndTree: key, + Body: itemBody, + } } - handleItem(o, itemCtx, key.TreeID, btrfstree.Item{ - Key: key.Key, - Body: itemBody, - }) - if key.ItemType == btrfsitem.ROOT_ITEM_KEY { - o.treeQueue.Insert(key.ObjectID) + return nil + }) + grp.Go("cpu", func(stepCtx context.Context) error { + defer progressWriter.Done() + for item := range itemChan { + itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", item.keyAndTree) + o.curKey = item.keyAndTree + handleItem(o, itemCtx, item.TreeID, btrfstree.Item{ + Key: item.Key, + Body: item.Body, + }) + if item.ItemType == btrfsitem.ROOT_ITEM_KEY { + o.treeQueue.Insert(item.ObjectID) + } + progress.N++ + progressWriter.Set(progress) } + return nil + }) + if err := grp.Wait(); err != nil { + return err } - progress.N = len(itemQueue) - progressWriter.Set(progress) - progressWriter.Done() // Apply augments (drain o.augmentQueue, fill o.itemQueue) stepCtx = dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "apply-augments") -- cgit v1.2.3-2-g168b 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 --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') 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 -- cgit v1.2.3-2-g168b From 1bddcbc7760915f4afe0f725612e588c14bb50fb Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 31 Dec 2022 10:14:14 -0700 Subject: rebuildnodes: Don't try to add the same augment twice This should save some memory and some log i/o. --- .../btrfsinspect/rebuildnodes/rebuild.go | 176 ++++++++++++--------- 1 file changed, 100 insertions(+), 76 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 3696a8a..74214af 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -54,7 +54,7 @@ type rebuilder struct { curKey keyAndTree treeQueue containers.Set[btrfsprim.ObjID] itemQueue containers.Set[keyAndTree] - augmentQueue map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int + augmentQueue map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr] } type Rebuilder interface { @@ -94,7 +94,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { // Initialize o.itemQueue = make(containers.Set[keyAndTree]) - o.augmentQueue = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) + o.augmentQueue = make(map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr]) // Seed the queue o.treeQueue = containers.NewSet[btrfsprim.ObjID]( @@ -186,10 +186,10 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { return err } treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) - resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, o.augmentQueue[treeID]) + resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, treeID) progress.D += len(resolvedAugments[treeID]) } - o.augmentQueue = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) + o.augmentQueue = make(map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr]) progressWriter = textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) for _, treeID := range maps.SortedKeys(resolvedAugments) { @@ -220,9 +220,9 @@ func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key b func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "tree Root") - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", - fmt.Sprintf("tree=%v key={%v %v ?}", btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY)) - key, ok := o._want(ctx, btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY) + wantKey := fmt.Sprintf("tree=%v key={%v %v ?}", btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY) + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", wantKey) + key, ok := o._want(ctx, btrfsprim.ROOT_TREE_OBJECTID, wantKey, tree, btrfsitem.ROOT_ITEM_KEY) if !ok { o.itemQueue.Insert(o.curKey) return 0, btrfsitem.Root{}, false @@ -247,8 +247,9 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { key := btrfsitem.UUIDToKey(uuid) ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "resolve parent UUID") - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: key}) - if ok := o._wantOff(ctx, btrfsprim.UUID_TREE_OBJECTID, key); !ok { + wantKey := keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: key}.String() + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", wantKey) + if ok := o._wantOff(ctx, btrfsprim.UUID_TREE_OBJECTID, wantKey, key); !ok { o.itemQueue.Insert(o.curKey) return 0, false } @@ -269,24 +270,33 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b } } -func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances []map[btrfsvol.LogicalAddr]int) containers.Set[btrfsvol.LogicalAddr] { - distances := make(map[btrfsvol.LogicalAddr]int) - generations := make(map[btrfsvol.LogicalAddr]btrfsprim.Generation) - lists := make([]containers.Set[btrfsvol.LogicalAddr], len(listsWithDistances)) - for i, listWithDistances := range listsWithDistances { - lists[i] = make(containers.Set[btrfsvol.LogicalAddr], len(listWithDistances)) - for item, dist := range listWithDistances { - lists[i].Insert(item) - distances[item] = dist - generations[item] = o.graph.Nodes[item].Generation - } - } - +func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.ObjID) containers.Set[btrfsvol.LogicalAddr] { // Define an algorithm that takes several lists of items, and returns a // set of those items such that each input list contains zero or one of // the items from your return set. The same item may appear in multiple // of the input lists. - // + + type ChoiceInfo struct { + Count int + Distance int + Generation btrfsprim.Generation + } + choices := make(map[btrfsvol.LogicalAddr]ChoiceInfo) + for _, list := range o.augmentQueue[treeID] { + for choice := range list { + if old, ok := choices[choice]; ok { + old.Count++ + choices[choice] = old + } else { + choices[choice] = ChoiceInfo{ + Count: 1, + Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)), + Generation: o.graph.Nodes[choice].Generation, + } + } + } + } + // > Example 1: Given the input lists // > // > 0: [A, B] @@ -342,31 +352,24 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances illegal := make(containers.Set[btrfsvol.LogicalAddr]) // cannot-be-accepted and already-accepted accept := func(item btrfsvol.LogicalAddr) { ret.Insert(item) - for _, list := range lists { + for _, list := range o.augmentQueue[treeID] { if list.Has(item) { illegal.InsertFrom(list) } } } - counts := make(map[btrfsvol.LogicalAddr]int) - for _, list := range lists { - for item := range list { - counts[item]++ - } - } - - sortedItems := maps.Keys(distances) + sortedItems := maps.Keys(choices) sort.Slice(sortedItems, func(i, j int) bool { iItem, jItem := sortedItems[i], sortedItems[j] - if counts[iItem] != counts[jItem] { - return counts[iItem] > counts[jItem] // reverse this check; higher counts should sort lower + if choices[iItem].Count != choices[jItem].Count { + return choices[iItem].Count > choices[jItem].Count // reverse this check; higher counts should sort lower } - if distances[iItem] != distances[jItem] { - return distances[iItem] < distances[jItem] + if choices[iItem].Distance != choices[jItem].Distance { + return choices[iItem].Distance < choices[jItem].Distance } - if generations[iItem] != generations[jItem] { - return generations[iItem] > generations[jItem] // reverse this check; higher generations should sort lower + if choices[iItem].Generation != choices[jItem].Generation { + return choices[iItem].Generation > choices[jItem].Generation // reverse this check; higher generations should sort lower } return iItem < jItem // laddr is as good a tiebreaker as anything }) @@ -376,12 +379,13 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances } } - for i, list := range lists { + // Log our result + for wantKey, list := range o.augmentQueue[treeID] { chose := list.Intersection(ret) if len(chose) == 0 { - dlog.Infof(ctx, "lists[%d]: chose (none) from %v", i, maps.SortedKeys(list)) + dlog.Infof(ctx, "lists[%q]: chose (none) from %v", wantKey, maps.SortedKeys(list)) } else { - dlog.Infof(ctx, "lists[%d]: chose %v from %v", i, chose.TakeOne(), maps.SortedKeys(list)) + dlog.Infof(ctx, "lists[%q]: chose %v from %v", wantKey, chose.TakeOne(), maps.SortedKeys(list)) } } @@ -390,21 +394,26 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, choices containers.Set[btrfsvol.LogicalAddr]) { +func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { + treeQueue, ok := o.augmentQueue[treeID] + if !ok { + return false + } + _, ok = treeQueue[wantKey] + return ok +} + +func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { if len(choices) == 0 { + choices = nil dlog.Error(ctx, "could not find wanted item") - return + } else { + dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) } - choicesWithDist := make(map[btrfsvol.LogicalAddr]int, len(choices)) - for choice := range choices { - dist, ok := o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner) - if !ok { - panic(fmt.Errorf("should not happen: .wantAugment called for tree=%v with invalid choice=%v", treeID, choice)) - } - choicesWithDist[choice] = dist + if o.augmentQueue[treeID] == nil { + o.augmentQueue[treeID] = make(map[string]containers.Set[btrfsvol.LogicalAddr]) } - dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choicesWithDist)) - o.augmentQueue[treeID] = append(o.augmentQueue[treeID], choicesWithDist) + o.augmentQueue[treeID][wantKey] = choices } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// @@ -417,12 +426,12 @@ func (o *rebuilder) fsErr(ctx context.Context, e error) { // want implements rebuildCallbacks. func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason) - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", - fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) - o._want(ctx, treeID, objID, typ) + wantKey := fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ) + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey) + o._want(ctx, treeID, wantKey, objID, typ) } -func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) { +func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) { if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return btrfsprim.Key{}, false @@ -443,6 +452,9 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr // OK, we need to insert it + if o.hasAugment(treeID, wantKey) { + return btrfsprim.Key{}, false + } wants := make(containers.Set[btrfsvol.LogicalAddr]) o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, @@ -450,7 +462,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node)) return true }) - o.wantAugment(ctx, treeID, wants) + o.wantAugment(ctx, treeID, wantKey, wants) return btrfsprim.Key{}, false } @@ -462,11 +474,12 @@ func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim Offset: off, } ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason) - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", keyAndTree{TreeID: treeID, Key: key}) - o._wantOff(ctx, treeID, key) + wantKey := keyAndTree{TreeID: treeID, Key: key}.String() + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey) + o._wantOff(ctx, treeID, wantKey, key) } -func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt btrfsprim.Key) (ok bool) { +func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, tgt btrfsprim.Key) (ok bool) { if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return false @@ -480,6 +493,9 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt // OK, we need to insert it + if o.hasAugment(treeID, wantKey) { + return false + } wants := make(containers.Set[btrfsvol.LogicalAddr]) o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) }, @@ -487,11 +503,11 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node)) return true }) - o.wantAugment(ctx, treeID, wants) + o.wantAugment(ctx, treeID, wantKey, wants) return false } -func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) { +func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) { if o.rebuilt.Tree(ctx, treeID) == nil { o.itemQueue.Insert(o.curKey) return @@ -521,6 +537,9 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID // OK, we need to insert it + if o.hasAugment(treeID, wantKey) { + return + } wants := make(containers.Set[btrfsvol.LogicalAddr]) o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, @@ -530,16 +549,16 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID } return true }) - o.wantAugment(ctx, treeID, wants) + o.wantAugment(ctx, treeID, wantKey, wants) } // wantDirIndex implements rebuildCallbacks. func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) { typ := btrfsitem.DIR_INDEX_KEY ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason) - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", - fmt.Sprintf("tree=%v key={%v %v ?} name=%q", treeID, objID, typ, name)) - o._wantFunc(ctx, treeID, objID, typ, func(ptr keyio.ItemPtr) bool { + wantKey := fmt.Sprintf("tree=%v key={%v %v ?} name=%q", treeID, objID, typ, name) + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey) + o._wantFunc(ctx, treeID, wantKey, objID, typ, func(ptr keyio.ItemPtr) bool { itemName, ok := o.keyIO.Names[ptr] return ok && bytes.Equal(itemName, name) }) @@ -700,23 +719,28 @@ func (o *rebuilder) _wantRange( // TODO: This is dumb and greedy. if last < runBeg { // log an error - wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", - fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, last, runBeg)) - o.wantAugment(wantCtx, treeID, nil) + wantKey := fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, last, runBeg) + if !o.hasAugment(treeID, wantKey) { + wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey) + o.wantAugment(wantCtx, treeID, wantKey, nil) + } + } + wantKey := fmt.Sprintf("tree=%v key={%v %v %v-%v}", treeID, objID, typ, gap.Beg, gap.End) + if !o.hasAugment(treeID, wantKey) { + wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey) + o.wantAugment(wantCtx, treeID, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node)) } - 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(wantCtx, v.Node)) last = runEnd return true }) if last < gap.End { // log an error - wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", - fmt.Sprintf("tree=%v key={%v, %v, %v-%v}", - treeID, objID, typ, last, gap.End)) - o.wantAugment(wantCtx, treeID, nil) + wantKey := fmt.Sprintf("tree=%v key={%v, %v, %v-%v}", treeID, objID, typ, last, gap.End) + if !o.hasAugment(treeID, wantKey) { + wantCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", wantKey) + o.wantAugment(wantCtx, treeID, wantKey, nil) + } } return nil }) -- cgit v1.2.3-2-g168b From 9df917f91255ebdc2d5163e1da3fcccb691a928a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 31 Dec 2022 15:48:31 -0700 Subject: rebuildnodes: Strategically scope variables, add runtime.GC() calls "Ignore space change" is probably useful for viewing this diff. --- .../btrfsinspect/rebuildnodes/rebuild.go | 178 +++++++++++---------- 1 file changed, 94 insertions(+), 84 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 74214af..7b3262b 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -8,6 +8,7 @@ import ( "bytes" "context" "fmt" + "runtime" "sort" "time" @@ -108,105 +109,114 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { passCtx := dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.rebuild.pass", passNum) // Add items to the queue (drain o.treeQueue, fill o.itemQueue) - stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items") - treeQueue := o.treeQueue - o.treeQueue = make(containers.Set[btrfsprim.ObjID]) - // Because trees can be wildly different sizes, it's impossible to have a meaningful - // progress percentage here. - for _, treeID := range maps.SortedKeys(treeQueue) { - if err := _ctx.Err(); err != nil { - return err + if true { + stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items") + treeQueue := o.treeQueue + o.treeQueue = make(containers.Set[btrfsprim.ObjID]) + // Because trees can be wildly different sizes, it's impossible to have a meaningful + // progress percentage here. + for _, treeID := range maps.SortedKeys(treeQueue) { + if err := _ctx.Err(); err != nil { + return err + } + o.rebuilt.Tree(stepCtx, treeID) } - o.rebuilt.Tree(stepCtx, treeID) } + runtime.GC() // Handle items in the queue (drain o.itemQueue, fill o.augmentQueue and o.treeQueue) - stepCtx = dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items") - itemQueue := maps.Keys(o.itemQueue) - o.itemQueue = make(containers.Set[keyAndTree]) - sort.Slice(itemQueue, func(i, j int) bool { - return itemQueue[i].Cmp(itemQueue[j]) < 0 - }) - var progress textui.Portion[int] - progress.D = len(itemQueue) - progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) - type keyAndBody struct { - keyAndTree - Body btrfsitem.Item - } - itemChan := make(chan keyAndBody, textui.Tunable(300)) // average items-per-node≈100; let's have a buffer of ~3 nodes - grp := dgroup.NewGroup(stepCtx, dgroup.GroupConfig{}) - grp.Go("io", func(stepCtx context.Context) error { - defer close(itemChan) - for _, key := range itemQueue { - if err := stepCtx.Err(); err != nil { - return err - } - itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key) - itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).ReadItem(itemCtx, key.Key) - if !ok { - o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key)) - } - itemChan <- keyAndBody{ - keyAndTree: key, - Body: itemBody, - } + if true { + stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items") + itemQueue := maps.Keys(o.itemQueue) + o.itemQueue = make(containers.Set[keyAndTree]) + sort.Slice(itemQueue, func(i, j int) bool { + return itemQueue[i].Cmp(itemQueue[j]) < 0 + }) + var progress textui.Portion[int] + progress.D = len(itemQueue) + progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) + type keyAndBody struct { + keyAndTree + Body btrfsitem.Item } - return nil - }) - grp.Go("cpu", func(stepCtx context.Context) error { - defer progressWriter.Done() - for item := range itemChan { - itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", item.keyAndTree) - o.curKey = item.keyAndTree - handleItem(o, itemCtx, item.TreeID, btrfstree.Item{ - Key: item.Key, - Body: item.Body, - }) - if item.ItemType == btrfsitem.ROOT_ITEM_KEY { - o.treeQueue.Insert(item.ObjectID) + itemChan := make(chan keyAndBody, textui.Tunable(300)) // average items-per-node≈100; let's have a buffer of ~3 nodes + grp := dgroup.NewGroup(stepCtx, dgroup.GroupConfig{}) + grp.Go("io", func(stepCtx context.Context) error { + defer close(itemChan) + for _, key := range itemQueue { + if err := stepCtx.Err(); err != nil { + return err + } + itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key) + itemBody, ok := o.rebuilt.Tree(itemCtx, key.TreeID).ReadItem(itemCtx, key.Key) + if !ok { + o.ioErr(itemCtx, fmt.Errorf("could not read previously read item: %v", key)) + } + itemChan <- keyAndBody{ + keyAndTree: key, + Body: itemBody, + } } - progress.N++ - progressWriter.Set(progress) + return nil + }) + grp.Go("cpu", func(stepCtx context.Context) error { + defer progressWriter.Done() + for item := range itemChan { + itemCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.process.item", item.keyAndTree) + o.curKey = item.keyAndTree + handleItem(o, itemCtx, item.TreeID, btrfstree.Item{ + Key: item.Key, + Body: item.Body, + }) + if item.ItemType == btrfsitem.ROOT_ITEM_KEY { + o.treeQueue.Insert(item.ObjectID) + } + progress.N++ + progressWriter.Set(progress) + } + return nil + }) + if err := grp.Wait(); err != nil { + return err } - return nil - }) - if err := grp.Wait(); err != nil { - return err } + runtime.GC() // Apply augments (drain o.augmentQueue, fill o.itemQueue) - stepCtx = dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "apply-augments") - resolvedAugments := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(o.augmentQueue)) - progress.N = 0 - progress.D = 0 - for _, treeID := range maps.SortedKeys(o.augmentQueue) { - if err := _ctx.Err(); err != nil { - return err - } - treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) - resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, treeID) - progress.D += len(resolvedAugments[treeID]) - } - o.augmentQueue = make(map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr]) - progressWriter = textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) - for _, treeID := range maps.SortedKeys(resolvedAugments) { - treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) - for _, nodeAddr := range maps.SortedKeys(resolvedAugments[treeID]) { + if true { + stepCtx := dlog.WithField(passCtx, "btrfsinspect.rebuild-nodes.rebuild.substep", "apply-augments") + resolvedAugments := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(o.augmentQueue)) + var progress textui.Portion[int] + for _, treeID := range maps.SortedKeys(o.augmentQueue) { if err := _ctx.Err(); err != nil { - progressWriter.Set(progress) - progressWriter.Done() return err } - progressWriter.Set(progress) - o.rebuilt.Tree(treeCtx, treeID).AddRoot(treeCtx, nodeAddr) - progress.N++ + treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) + resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, treeID) + progress.D += len(resolvedAugments[treeID]) + } + o.augmentQueue = make(map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr]) + runtime.GC() + progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) + for _, treeID := range maps.SortedKeys(resolvedAugments) { + treeCtx := dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID) + for _, nodeAddr := range maps.SortedKeys(resolvedAugments[treeID]) { + if err := _ctx.Err(); err != nil { + progressWriter.Set(progress) + progressWriter.Done() + return err + } + progressWriter.Set(progress) + o.rebuilt.Tree(treeCtx, treeID).AddRoot(treeCtx, nodeAddr) + progress.N++ + } } + progressWriter.Set(progress) + progressWriter.Done() } - progressWriter.Set(progress) - progressWriter.Done() + runtime.GC() } return nil } -- cgit v1.2.3-2-g168b From 1e93fcdba6918ba609c7a01be3007c409d9b2b86 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 1 Jan 2023 11:43:56 -0700 Subject: rebuildnodes: Optimize storage for single-item augments --- .../btrfsinspect/rebuildnodes/rebuild.go | 75 ++++++++++++++++++---- 1 file changed, 62 insertions(+), 13 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 7b3262b..7113938 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -55,7 +55,12 @@ type rebuilder struct { curKey keyAndTree treeQueue containers.Set[btrfsprim.ObjID] itemQueue containers.Set[keyAndTree] - augmentQueue map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr] + augmentQueue map[btrfsprim.ObjID]*treeAugmentQueue +} + +type treeAugmentQueue struct { + single map[string]btrfsvol.LogicalAddr + multi map[string]containers.Set[btrfsvol.LogicalAddr] } type Rebuilder interface { @@ -95,7 +100,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { // Initialize o.itemQueue = make(containers.Set[keyAndTree]) - o.augmentQueue = make(map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr]) + o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue) // Seed the queue o.treeQueue = containers.NewSet[btrfsprim.ObjID]( @@ -196,7 +201,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { resolvedAugments[treeID] = o.resolveTreeAugments(treeCtx, treeID) progress.D += len(resolvedAugments[treeID]) } - o.augmentQueue = make(map[btrfsprim.ObjID]map[string]containers.Set[btrfsvol.LogicalAddr]) + o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue) runtime.GC() progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) @@ -292,7 +297,22 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob Generation btrfsprim.Generation } choices := make(map[btrfsvol.LogicalAddr]ChoiceInfo) - for _, list := range o.augmentQueue[treeID] { + // o.augmentQueue[treeID].single is optimized storage for + // lists with exactly 1 item. + for _, choice := range o.augmentQueue[treeID].single { + if old, ok := choices[choice]; ok { + old.Count++ + choices[choice] = old + } else { + choices[choice] = ChoiceInfo{ + Count: 1, + Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)), + Generation: o.graph.Nodes[choice].Generation, + } + } + } + // o.augmentQueue[treeID].multi is the main list storage. + for _, list := range o.augmentQueue[treeID].multi { for choice := range list { if old, ok := choices[choice]; ok { old.Count++ @@ -362,7 +382,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob illegal := make(containers.Set[btrfsvol.LogicalAddr]) // cannot-be-accepted and already-accepted accept := func(item btrfsvol.LogicalAddr) { ret.Insert(item) - for _, list := range o.augmentQueue[treeID] { + for _, list := range o.augmentQueue[treeID].multi { if list.Has(item) { illegal.InsertFrom(list) } @@ -390,7 +410,15 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } // Log our result - for wantKey, list := range o.augmentQueue[treeID] { + wantKeys := append( + maps.Keys(o.augmentQueue[treeID].single), + maps.Keys(o.augmentQueue[treeID].multi)...) + sort.Strings(wantKeys) + for _, wantKey := range wantKeys { + list, ok := o.augmentQueue[treeID].multi[wantKey] + if !ok { + list = containers.NewSet[btrfsvol.LogicalAddr](o.augmentQueue[treeID].single[wantKey]) + } chose := list.Intersection(ret) if len(chose) == 0 { dlog.Infof(ctx, "lists[%q]: chose (none) from %v", wantKey, maps.SortedKeys(list)) @@ -399,18 +427,29 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } } + // Free some memory + o.augmentQueue[treeID].single = nil + o.augmentQueue[treeID].multi = nil + return ret } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { - treeQueue, ok := o.augmentQueue[treeID] - if !ok { - return false + if treeQueue, ok := o.augmentQueue[treeID]; ok { + if treeQueue.single != nil { + if _, ok := treeQueue.single[wantKey]; ok { + return true + } + } + if treeQueue.multi != nil { + if _, ok := treeQueue.multi[wantKey]; ok { + return true + } + } } - _, ok = treeQueue[wantKey] - return ok + return false } func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { @@ -421,9 +460,19 @@ func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wan dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) } if o.augmentQueue[treeID] == nil { - o.augmentQueue[treeID] = make(map[string]containers.Set[btrfsvol.LogicalAddr]) + o.augmentQueue[treeID] = new(treeAugmentQueue) + } + if len(choices) == 1 { + if o.augmentQueue[treeID].single == nil { + o.augmentQueue[treeID].single = make(map[string]btrfsvol.LogicalAddr) + } + o.augmentQueue[treeID].single[wantKey] = choices.TakeOne() + } else { + if o.augmentQueue[treeID].multi == nil { + o.augmentQueue[treeID].multi = make(map[string]containers.Set[btrfsvol.LogicalAddr]) + } + o.augmentQueue[treeID].multi[wantKey] = choices } - o.augmentQueue[treeID][wantKey] = choices } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3-2-g168b From f426b1d250f39cfd3595dea1469e95488764156c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 1 Jan 2023 12:35:14 -0700 Subject: rebuildnodes: Tidy up errors and key management --- .../btrfsinspect/rebuildnodes/rebuild.go | 32 +++++++++++++--------- 1 file changed, 19 insertions(+), 13 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 7113938..a3fd0e7 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -235,14 +235,21 @@ func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key b func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "tree Root") - wantKey := fmt.Sprintf("tree=%v key={%v %v ?}", btrfsprim.ROOT_TREE_OBJECTID, tree, btrfsitem.ROOT_ITEM_KEY) + key := keyAndTree{ + TreeID: btrfsprim.ROOT_TREE_OBJECTID, + Key: btrfsprim.Key{ + ObjectID: tree, + ItemType: btrfsitem.ROOT_ITEM_KEY, + }, + } + wantKey := fmt.Sprintf("tree=%v key={%v %v ?}", key.TreeID, key.ObjectID, key.ItemType) ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", wantKey) - key, ok := o._want(ctx, btrfsprim.ROOT_TREE_OBJECTID, wantKey, tree, btrfsitem.ROOT_ITEM_KEY) + key.Key, ok = o._want(ctx, key.TreeID, wantKey, key.ObjectID, key.ItemType) if !ok { o.itemQueue.Insert(o.curKey) return 0, btrfsitem.Root{}, false } - itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.ROOT_TREE_OBJECTID).ReadItem(ctx, key) + itemBody, ok := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -250,7 +257,7 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off case btrfsitem.Root: return btrfsprim.Generation(key.Offset), itemBody, true case btrfsitem.Error: - o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", btrfsprim.ROOT_TREE_OBJECTID, key, itemBody.Err)) + o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", key, itemBody.Err)) return 0, btrfsitem.Root{}, false default: // This is a panic because the item decoder should not emit ROOT_ITEM items as anything but @@ -260,15 +267,14 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off } func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { - key := btrfsitem.UUIDToKey(uuid) ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason", "resolve parent UUID") - wantKey := keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: key}.String() - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", wantKey) - if ok := o._wantOff(ctx, btrfsprim.UUID_TREE_OBJECTID, wantKey, key); !ok { + key := keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: btrfsitem.UUIDToKey(uuid)} + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", key.String()) + if !o._wantOff(ctx, key.TreeID, key.String(), key.Key) { o.itemQueue.Insert(o.curKey) return 0, false } - itemBody, ok := o.rebuilt.Tree(ctx, btrfsprim.UUID_TREE_OBJECTID).ReadItem(ctx, key) + itemBody, ok := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key)) } @@ -276,7 +282,7 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b case btrfsitem.UUIDMap: return itemBody.ObjID, true case btrfsitem.Error: - o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", btrfsprim.UUID_TREE_OBJECTID, key, itemBody.Err)) + o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", key, itemBody.Err)) return 0, false default: // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but @@ -639,7 +645,7 @@ func (o *rebuilder) _wantRange( sizeFn := func(key btrfsprim.Key) (uint64, error) { 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)) + panic(fmt.Errorf("should not happen: could not load key: %v", keyAndTree{TreeID: treeID, Key: key})) } sizeAndErr, ok := o.keyIO.Sizes[ptr] if !ok { @@ -691,7 +697,7 @@ func (o *rebuilder) _wantRange( func(runKey btrfsprim.Key, _ keyio.ItemPtr) bool { runSize, err := sizeFn(runKey) if err != nil { - o.fsErr(ctx, fmt.Errorf("tree=%v key=%v: %w", treeID, runKey, err)) + o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: runKey}, err)) return true } if runSize == 0 { @@ -763,7 +769,7 @@ func (o *rebuilder) _wantRange( func(k btrfsprim.Key, v keyio.ItemPtr) bool { runSize, err := sizeFn(k) if err != nil { - o.fsErr(ctx, fmt.Errorf("tree=%v key=%v: %w", treeID, k, err)) + o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: k}, err)) return true } if runSize == 0 { -- cgit v1.2.3-2-g168b From 05e621c0c47e65665042f1977ec69927c1bbde12 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 1 Jan 2023 12:36:22 -0700 Subject: rebuildnodes: Check for INODE_NODATASUM before looking for csums --- .../btrfsinspect/rebuildnodes/rebuild.go | 41 +++++++++++++++++++--- 1 file changed, 37 insertions(+), 4 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index a3fd0e7..08ab81a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -18,6 +18,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" @@ -814,11 +815,43 @@ func (o *rebuilder) _wantRange( // func implements rebuildCallbacks. // // interval is [beg, end) -func (o *rebuilder) wantCSum(ctx context.Context, reason string, beg, end btrfsvol.LogicalAddr) { +func (o *rebuilder) wantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.reason", reason) - const treeID = btrfsprim.CSUM_TREE_OBJECTID - o._wantRange(ctx, treeID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY, - uint64(beg), uint64(end)) + + inodeKey := keyAndTree{ + TreeID: inodeTree, + Key: btrfsprim.Key{ + ObjectID: inode, + ItemType: btrfsitem.INODE_ITEM_KEY, + Offset: 0, + }, + } + inodeCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", inodeKey.String()) + if !o._wantOff(inodeCtx, inodeKey.TreeID, inodeKey.String(), inodeKey.Key) { + o.itemQueue.Insert(o.curKey) + return + } + inodeBody, ok := o.rebuilt.Tree(inodeCtx, inodeKey.TreeID).ReadItem(inodeCtx, inodeKey.Key) + if !ok { + o.ioErr(inodeCtx, fmt.Errorf("could not read previously read item: %v", inodeKey)) + } + switch inodeBody := inodeBody.(type) { + case btrfsitem.Inode: + if inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) { + return + } + beg = roundDown(beg, btrfssum.BlockSize) + end = roundUp(end, btrfssum.BlockSize) + const treeID = btrfsprim.CSUM_TREE_OBJECTID + o._wantRange(ctx, treeID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY, + uint64(beg), uint64(end)) + case btrfsitem.Error: + o.fsErr(inodeCtx, fmt.Errorf("error decoding item: %v: %w", inodeKey, inodeBody.Err)) + default: + // This is a panic because the item decoder should not emit INODE_ITEM items as anything but + // btrfsitem.Inode or btrfsitem.Error without this code also being updated. + panic(fmt.Errorf("should not happen: INODE_ITEM item has unexpected type: %T", inodeBody)) + } } // wantFileExt implements rebuildCallbacks. -- cgit v1.2.3-2-g168b From b55d2213eb8dec8a6f3852dea8c7053070f10158 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 1 Jan 2023 13:24:14 -0700 Subject: rebuildnodes: Log how many queued augments there are --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 20 ++++++++++++++++++-- 1 file changed, 18 insertions(+), 2 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 08ab81a..0a0aea4 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -57,6 +57,7 @@ type rebuilder struct { treeQueue containers.Set[btrfsprim.ObjID] itemQueue containers.Set[keyAndTree] augmentQueue map[btrfsprim.ObjID]*treeAugmentQueue + numAugments int } type treeAugmentQueue struct { @@ -96,6 +97,17 @@ func (o *rebuilder) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.Logi return o.rebuilt.ListRoots() } +type itemStats struct { + textui.Portion[int] + NumAugments int + NumAugmentTrees int +} + +func (s itemStats) String() string { + return textui.Sprintf("%v (queued %v augments across %v trees)", + s.Portion, s.NumAugments, s.NumAugmentTrees) +} + func (o *rebuilder) Rebuild(_ctx context.Context) error { _ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.step", "rebuild") @@ -138,9 +150,9 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { sort.Slice(itemQueue, func(i, j int) bool { return itemQueue[i].Cmp(itemQueue[j]) < 0 }) - var progress textui.Portion[int] + var progress itemStats progress.D = len(itemQueue) - progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + progressWriter := textui.NewProgress[itemStats](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) type keyAndBody struct { keyAndTree @@ -179,6 +191,8 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { o.treeQueue.Insert(item.ObjectID) } progress.N++ + progress.NumAugments = o.numAugments + progress.NumAugmentTrees = len(o.augmentQueue) progressWriter.Set(progress) } return nil @@ -203,6 +217,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { progress.D += len(resolvedAugments[treeID]) } o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue) + o.numAugments = 0 runtime.GC() progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) @@ -480,6 +495,7 @@ func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wan } o.augmentQueue[treeID].multi[wantKey] = choices } + o.numAugments++ } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3-2-g168b From 9f4b541523989b6fc7a89dcb0c4323841ccf60d7 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 1 Jan 2023 23:08:18 -0700 Subject: rebuildnodes: Fix retrying trees --- .../btrfsinspect/rebuildnodes/rebuild.go | 23 +++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 0a0aea4..2357722 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -137,6 +137,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { if err := _ctx.Err(); err != nil { return err } + o.curKey = keyAndTree{TreeID: treeID} o.rebuilt.Tree(stepCtx, treeID) } } @@ -242,6 +243,14 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { return nil } +func (o *rebuilder) enqueueRetry() { + if o.curKey.Key == (btrfsprim.Key{}) { + o.treeQueue.Insert(o.curKey.TreeID) + } else { + o.itemQueue.Insert(o.curKey) + } +} + func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { o.itemQueue.Insert(keyAndTree{ TreeID: tree, @@ -262,7 +271,7 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", wantKey) key.Key, ok = o._want(ctx, key.TreeID, wantKey, key.ObjectID, key.ItemType) if !ok { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return 0, btrfsitem.Root{}, false } itemBody, ok := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key) @@ -287,7 +296,7 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b key := keyAndTree{TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: btrfsitem.UUIDToKey(uuid)} ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key", key.String()) if !o._wantOff(ctx, key.TreeID, key.String(), key.Key) { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return 0, false } itemBody, ok := o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key) @@ -515,7 +524,7 @@ func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.Ob func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, objID btrfsprim.ObjID, typ btrfsprim.ItemType) (key btrfsprim.Key, ok bool) { if o.rebuilt.Tree(ctx, treeID) == nil { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return btrfsprim.Key{}, false } @@ -563,7 +572,7 @@ func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, tgt btrfsprim.Key) (ok bool) { if o.rebuilt.Tree(ctx, treeID) == nil { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return false } @@ -591,7 +600,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, wantKe func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(keyio.ItemPtr) bool) { if o.rebuilt.Tree(ctx, treeID) == nil { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return } @@ -655,7 +664,7 @@ func (o *rebuilder) _wantRange( fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) if o.rebuilt.Tree(ctx, treeID) == nil { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return } @@ -844,7 +853,7 @@ func (o *rebuilder) wantCSum(ctx context.Context, reason string, inodeTree, inod } inodeCtx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", inodeKey.String()) if !o._wantOff(inodeCtx, inodeKey.TreeID, inodeKey.String(), inodeKey.Key) { - o.itemQueue.Insert(o.curKey) + o.enqueueRetry() return } inodeBody, ok := o.rebuilt.Tree(inodeCtx, inodeKey.TreeID).ReadItem(inodeCtx, inodeKey.Key) -- cgit v1.2.3-2-g168b From 5235e674300942bfbf752799ff0aaad24794cc86 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 2 Jan 2023 16:39:10 -0700 Subject: rebuildnodes: Add optimized storage for nil augments --- .../btrfsinspect/rebuildnodes/rebuild.go | 50 +++++++++++++++------- 1 file changed, 34 insertions(+), 16 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 2357722..d77a4ea 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -53,14 +53,16 @@ type rebuilder struct { rebuilt *btrees.RebuiltForrest - curKey keyAndTree - treeQueue containers.Set[btrfsprim.ObjID] - itemQueue containers.Set[keyAndTree] - augmentQueue map[btrfsprim.ObjID]*treeAugmentQueue - numAugments int + curKey keyAndTree + treeQueue containers.Set[btrfsprim.ObjID] + itemQueue containers.Set[keyAndTree] + augmentQueue map[btrfsprim.ObjID]*treeAugmentQueue + numAugments int + numAugmentFailures int } type treeAugmentQueue struct { + zero map[string]struct{} single map[string]btrfsvol.LogicalAddr multi map[string]containers.Set[btrfsvol.LogicalAddr] } @@ -100,12 +102,13 @@ func (o *rebuilder) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.Logi type itemStats struct { textui.Portion[int] NumAugments int + NumFailures int NumAugmentTrees int } func (s itemStats) String() string { - return textui.Sprintf("%v (queued %v augments across %v trees)", - s.Portion, s.NumAugments, s.NumAugmentTrees) + return textui.Sprintf("%v (queued %v augments and %v failures across %v trees)", + s.Portion, s.NumAugments, s.NumFailures, s.NumAugmentTrees) } func (o *rebuilder) Rebuild(_ctx context.Context) error { @@ -193,6 +196,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { } progress.N++ progress.NumAugments = o.numAugments + progress.NumFailures = o.numAugmentFailures progress.NumAugmentTrees = len(o.augmentQueue) progressWriter.Set(progress) } @@ -219,6 +223,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error { } o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue) o.numAugments = 0 + o.numAugmentFailures = 0 runtime.GC() progressWriter := textui.NewProgress[textui.Portion[int]](stepCtx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) stepCtx = dlog.WithField(stepCtx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress) @@ -328,6 +333,9 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob Generation btrfsprim.Generation } choices := make(map[btrfsvol.LogicalAddr]ChoiceInfo) + // o.augmentQueue[treeID].zero is optimized storage for lists + // with zero items. Go ahead and free that memory up. + o.augmentQueue[treeID].zero = nil // o.augmentQueue[treeID].single is optimized storage for // lists with exactly 1 item. for _, choice := range o.augmentQueue[treeID].single { @@ -469,6 +477,11 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { if treeQueue, ok := o.augmentQueue[treeID]; ok { + if treeQueue.zero != nil { + if _, ok := treeQueue.zero[wantKey]; ok { + return true + } + } if treeQueue.single != nil { if _, ok := treeQueue.single[wantKey]; ok { return true @@ -484,27 +497,32 @@ func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { } func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { - if len(choices) == 0 { - choices = nil - dlog.Error(ctx, "could not find wanted item") - } else { - dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) - } if o.augmentQueue[treeID] == nil { o.augmentQueue[treeID] = new(treeAugmentQueue) } - if len(choices) == 1 { + switch len(choices) { + case 0: + dlog.Error(ctx, "could not find wanted item") + if o.augmentQueue[treeID].zero == nil { + o.augmentQueue[treeID].zero = make(map[string]struct{}) + } + o.augmentQueue[treeID].zero[wantKey] = struct{}{} + o.numAugmentFailures++ + case 1: + dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) if o.augmentQueue[treeID].single == nil { o.augmentQueue[treeID].single = make(map[string]btrfsvol.LogicalAddr) } o.augmentQueue[treeID].single[wantKey] = choices.TakeOne() - } else { + o.numAugments++ + default: + dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) if o.augmentQueue[treeID].multi == nil { o.augmentQueue[treeID].multi = make(map[string]containers.Set[btrfsvol.LogicalAddr]) } o.augmentQueue[treeID].multi[wantKey] = choices + o.numAugments++ } - o.numAugments++ } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3-2-g168b From c3d08003a7fbffea3b2b95600ddbf5a1be4fde83 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 2 Jan 2023 17:17:36 -0700 Subject: rebuildnodes: Compact augment keys to save space --- .../btrfsinspect/rebuildnodes/rebuild.go | 77 +++++++++++++++------- 1 file changed, 55 insertions(+), 22 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index d77a4ea..0116abb 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -10,6 +10,7 @@ import ( "fmt" "runtime" "sort" + "strings" "time" "github.com/datawire/dlib/dgroup" @@ -62,6 +63,7 @@ type rebuilder struct { } type treeAugmentQueue struct { + keyBuf strings.Builder zero map[string]struct{} single map[string]btrfsvol.LogicalAddr multi map[string]containers.Set[btrfsvol.LogicalAddr] @@ -469,26 +471,38 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob // Free some memory o.augmentQueue[treeID].single = nil o.augmentQueue[treeID].multi = nil + o.augmentQueue[treeID].keyBuf.Reset() return ret } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { - if treeQueue, ok := o.augmentQueue[treeID]; ok { +func shortenWantKey(wantKey string) string { + if !strings.HasPrefix(wantKey, "tree=") { + panic("should not happen") + } + sp := strings.IndexByte(wantKey, ' ') + if sp < 0 { + panic("should not happen") + } + return wantKey[sp+1:] +} + +func (treeQueue *treeAugmentQueue) has(wantKey string) bool { + if treeQueue != nil { if treeQueue.zero != nil { - if _, ok := treeQueue.zero[wantKey]; ok { + if _, ok := treeQueue.zero[shortenWantKey(wantKey)]; ok { return true } } if treeQueue.single != nil { - if _, ok := treeQueue.single[wantKey]; ok { + if _, ok := treeQueue.single[shortenWantKey(wantKey)]; ok { return true } } if treeQueue.multi != nil { - if _, ok := treeQueue.multi[wantKey]; ok { + if _, ok := treeQueue.multi[shortenWantKey(wantKey)]; ok { return true } } @@ -496,31 +510,50 @@ func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { return false } -func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { - if o.augmentQueue[treeID] == nil { - o.augmentQueue[treeID] = new(treeAugmentQueue) +func (treeQueue *treeAugmentQueue) store(wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { + wantKey = shortenWantKey(wantKey) + beg := treeQueue.keyBuf.Len() + if treeQueue.keyBuf.Cap()-beg < len(wantKey) { + treeQueue.keyBuf.Reset() + treeQueue.keyBuf.Grow(textui.Tunable(4096)) + beg = 0 } + treeQueue.keyBuf.WriteString(wantKey) + wantKey = treeQueue.keyBuf.String()[beg:] + switch len(choices) { case 0: - dlog.Error(ctx, "could not find wanted item") - if o.augmentQueue[treeID].zero == nil { - o.augmentQueue[treeID].zero = make(map[string]struct{}) + if treeQueue.zero == nil { + treeQueue.zero = make(map[string]struct{}) } - o.augmentQueue[treeID].zero[wantKey] = struct{}{} - o.numAugmentFailures++ + treeQueue.zero[wantKey] = struct{}{} case 1: - dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) - if o.augmentQueue[treeID].single == nil { - o.augmentQueue[treeID].single = make(map[string]btrfsvol.LogicalAddr) + if treeQueue.single == nil { + treeQueue.single = make(map[string]btrfsvol.LogicalAddr) } - o.augmentQueue[treeID].single[wantKey] = choices.TakeOne() - o.numAugments++ + treeQueue.single[wantKey] = choices.TakeOne() default: - dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) - if o.augmentQueue[treeID].multi == nil { - o.augmentQueue[treeID].multi = make(map[string]containers.Set[btrfsvol.LogicalAddr]) + if treeQueue.multi == nil { + treeQueue.multi = make(map[string]containers.Set[btrfsvol.LogicalAddr]) } - o.augmentQueue[treeID].multi[wantKey] = choices + treeQueue.multi[wantKey] = choices + } +} + +func (o *rebuilder) hasAugment(treeID btrfsprim.ObjID, wantKey string) bool { + return o.augmentQueue[treeID].has(wantKey) +} + +func (o *rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { + if o.augmentQueue[treeID] == nil { + o.augmentQueue[treeID] = new(treeAugmentQueue) + } + o.augmentQueue[treeID].store(wantKey, choices) + if len(choices) == 0 { + dlog.Error(ctx, "could not find wanted item") + o.numAugmentFailures++ + } else { + dlog.Infof(ctx, "choices=%v", maps.SortedKeys(choices)) o.numAugments++ } } -- cgit v1.2.3-2-g168b From 06157a3a8259bb0fc5f806aac3bbde79e95a54fd Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 2 Jan 2023 17:32:23 -0700 Subject: rebuildnodes: Avoid i/o reading items for which handleItem is a no-op --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 3 +++ 1 file changed, 3 insertions(+) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 0116abb..80db817 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -259,6 +259,9 @@ func (o *rebuilder) enqueueRetry() { } func (o *rebuilder) cbAddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { + if handleWouldBeNoOp(key.ItemType) { + return + } o.itemQueue.Insert(keyAndTree{ TreeID: tree, Key: key, -- cgit v1.2.3-2-g168b From df62eb5d4c92756914ce57a1b6219b39876331f6 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 10:34:06 -0700 Subject: Try to get log-lines to be shorter --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 80db817..63a0d16 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -109,7 +109,8 @@ type itemStats struct { } func (s itemStats) String() string { - return textui.Sprintf("%v (queued %v augments and %v failures across %v trees)", + // return textui.Sprintf("%v (queued %v augments and %v failures across %v trees)", + return textui.Sprintf("%v (aug:%v fail:%v trees:%v)", s.Portion, s.NumAugments, s.NumFailures, s.NumAugmentTrees) } -- cgit v1.2.3-2-g168b From d696784667e8dd01fee62145d031fd56285d48ae Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 11:21:53 -0700 Subject: rebuildnodes: Track inode flags, to avoid later i/o --- .../btrfsinspect/rebuildnodes/rebuild.go | 37 +++++++++++----------- 1 file changed, 19 insertions(+), 18 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 63a0d16..fbbda26 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -911,27 +911,28 @@ func (o *rebuilder) wantCSum(ctx context.Context, reason string, inodeTree, inod o.enqueueRetry() return } - inodeBody, ok := o.rebuilt.Tree(inodeCtx, inodeKey.TreeID).ReadItem(inodeCtx, inodeKey.Key) + inodePtr, ok := o.rebuilt.Tree(inodeCtx, inodeKey.TreeID).Items(inodeCtx).Load(inodeKey.Key) if !ok { - o.ioErr(inodeCtx, fmt.Errorf("could not read previously read item: %v", inodeKey)) + panic(fmt.Errorf("should not happen: could not load key: %v", inodeKey)) } - switch inodeBody := inodeBody.(type) { - case btrfsitem.Inode: - if inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) { - return - } - beg = roundDown(beg, btrfssum.BlockSize) - end = roundUp(end, btrfssum.BlockSize) - const treeID = btrfsprim.CSUM_TREE_OBJECTID - o._wantRange(ctx, treeID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY, - uint64(beg), uint64(end)) - case btrfsitem.Error: - o.fsErr(inodeCtx, fmt.Errorf("error decoding item: %v: %w", inodeKey, inodeBody.Err)) - default: - // This is a panic because the item decoder should not emit INODE_ITEM items as anything but - // btrfsitem.Inode or btrfsitem.Error without this code also being updated. - panic(fmt.Errorf("should not happen: INODE_ITEM item has unexpected type: %T", inodeBody)) + inodeFlags, ok := o.keyIO.Flags[inodePtr] + if !ok { + panic(fmt.Errorf("should not happen: INODE_ITEM did not have flags recorded")) + } + if inodeFlags.Err != nil { + o.fsErr(inodeCtx, inodeFlags.Err) + return } + + if inodeFlags.NoDataSum { + return + } + + beg = roundDown(beg, btrfssum.BlockSize) + end = roundUp(end, btrfssum.BlockSize) + const treeID = btrfsprim.CSUM_TREE_OBJECTID + o._wantRange(ctx, treeID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY, + uint64(beg), uint64(end)) } // wantFileExt implements rebuildCallbacks. -- cgit v1.2.3-2-g168b From c7d387f5ddd39e2d359c2c0c2ef52536ab650160 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 21:03:25 -0700 Subject: rebuildnodes/btrees: Don't include .Items() in .PotentialItems() Save some memory. --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index fbbda26..4709db2 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -723,8 +723,8 @@ func (o *rebuilder) _wantRange( return } - sizeFn := func(key btrfsprim.Key) (uint64, error) { - ptr, ok := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Load(key) + sizeFn := func(items *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr], key btrfsprim.Key) (uint64, error) { + ptr, ok := items.Load(key) if !ok { panic(fmt.Errorf("should not happen: could not load key: %v", keyAndTree{TreeID: treeID, Key: key})) } @@ -776,7 +776,7 @@ func (o *rebuilder) _wantRange( } }, func(runKey btrfsprim.Key, _ keyio.ItemPtr) bool { - runSize, err := sizeFn(runKey) + runSize, err := sizeFn(o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx), runKey) if err != nil { o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: runKey}, err)) return true @@ -848,7 +848,7 @@ func (o *rebuilder) _wantRange( } }, func(k btrfsprim.Key, v keyio.ItemPtr) bool { - runSize, err := sizeFn(k) + runSize, err := sizeFn(o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx), k) if err != nil { o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: k}, err)) return true -- cgit v1.2.3-2-g168b From 58a6dd12470931a7143c47036e8fde32e43c7e51 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 21:22:16 -0700 Subject: rebuildnodes: Factor out repeated code in _wantRange --- .../btrfsinspect/rebuildnodes/rebuild.go | 142 ++++++++++----------- 1 file changed, 64 insertions(+), 78 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 4709db2..28591dd 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -710,20 +710,14 @@ func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrf }) } -func (o *rebuilder) _wantRange( +func (o *rebuilder) _walkRange( ctx context.Context, - treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, + items *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr], + treeID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, beg, end uint64, + fn func(key btrfsprim.Key, ptr keyio.ItemPtr, beg, end uint64), ) { - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", - fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) - - if o.rebuilt.Tree(ctx, treeID) == nil { - o.enqueueRetry() - return - } - - sizeFn := func(items *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr], key btrfsprim.Key) (uint64, error) { + sizeFn := func(key btrfsprim.Key) (uint64, error) { ptr, ok := items.Load(key) if !ok { panic(fmt.Errorf("should not happen: could not load key: %v", keyAndTree{TreeID: treeID, Key: key})) @@ -735,48 +729,29 @@ func (o *rebuilder) _wantRange( return sizeAndErr.Size, sizeAndErr.Err } - // Step 1: Build a listing of the runs that we do have. - runMin := btrfsprim.Key{ + min := btrfsprim.Key{ ObjectID: objID, ItemType: typ, Offset: 0, // *NOT* `beg` } - runMax := btrfsprim.Key{ + max := btrfsprim.Key{ ObjectID: objID, ItemType: typ, Offset: end - 1, } - - // Step 2: Build a listing of the gaps. - // - // Start with a gap of the whole range, then subtract each run - // from it. - type gap struct { - // range is [Beg,End) - Beg, End uint64 - } - gaps := &containers.RBTree[containers.NativeOrdered[uint64], gap]{ - KeyFn: func(gap gap) containers.NativeOrdered[uint64] { - return containers.NativeOrdered[uint64]{Val: gap.Beg} - }, - } - gaps.Insert(gap{ - Beg: beg, - End: end, - }) - o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange( - func(key btrfsprim.Key, _ keyio.ItemPtr) int { + items.Subrange( + func(runKey btrfsprim.Key, _ keyio.ItemPtr) int { switch { - case runMin.Cmp(key) < 0: + case min.Cmp(runKey) < 0: return 1 - case runMax.Cmp(key) > 0: + case max.Cmp(runKey) > 0: return -1 default: return 0 } }, - func(runKey btrfsprim.Key, _ keyio.ItemPtr) bool { - runSize, err := sizeFn(o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx), runKey) + func(runKey btrfsprim.Key, runPtr keyio.ItemPtr) bool { + runSize, err := sizeFn(runKey) if err != nil { o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: runKey}, err)) return true @@ -789,6 +764,47 @@ func (o *rebuilder) _wantRange( if runEnd <= beg { return true } + + fn(runKey, runPtr, runBeg, runEnd) + return true + }) +} + +func (o *rebuilder) _wantRange( + ctx context.Context, + treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, + beg, end uint64, +) { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.want.key", + fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) + + if o.rebuilt.Tree(ctx, treeID) == nil { + o.enqueueRetry() + return + } + + // Step 1: Build a listing of the gaps. + // + // Start with a gap of the whole range, then subtract each run + // from it. + type gap struct { + // range is [Beg,End) + Beg, End uint64 + } + gaps := &containers.RBTree[containers.NativeOrdered[uint64], gap]{ + KeyFn: func(gap gap) containers.NativeOrdered[uint64] { + return containers.NativeOrdered[uint64]{Val: gap.Beg} + }, + } + gaps.Insert(gap{ + Beg: beg, + End: end, + }) + o._walkRange( + ctx, + o.rebuilt.Tree(ctx, treeID).Items(ctx), + treeID, objID, typ, beg, end, + func(runKey btrfsprim.Key, _ keyio.ItemPtr, runBeg, runEnd uint64) { overlappingGaps := gaps.SearchRange(func(gap gap) int { switch { case gap.End <= runBeg: @@ -800,7 +816,7 @@ func (o *rebuilder) _wantRange( } }) if len(overlappingGaps) == 0 { - return true + return } gapsBeg := overlappingGaps[0].Beg gapsEnd := overlappingGaps[len(overlappingGaps)-1].End @@ -819,49 +835,21 @@ func (o *rebuilder) _wantRange( End: gapsEnd, }) } - return true }) // Step 2: Fill each gap. + if gaps.Len() == 0 { + return + } + potentialItems := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx) _ = gaps.Walk(func(rbNode *containers.RBNode[gap]) error { gap := rbNode.Value last := gap.Beg - runMin := btrfsprim.Key{ - ObjectID: objID, - ItemType: typ, - Offset: 0, // *NOT* `gap.Beg` - } - runMax := btrfsprim.Key{ - ObjectID: objID, - ItemType: typ, - Offset: gap.End - 1, - } - o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( - func(key btrfsprim.Key, _ keyio.ItemPtr) int { - switch { - case runMin.Cmp(key) < 0: - return 1 - case runMax.Cmp(key) > 0: - return -1 - default: - return 0 - } - }, - func(k btrfsprim.Key, v keyio.ItemPtr) bool { - runSize, err := sizeFn(o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx), k) - if err != nil { - o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: k}, err)) - return true - } - if runSize == 0 { - return true - } - runBeg := k.Offset - runEnd := runBeg + runSize - if runEnd <= gap.Beg { - return true - } - + o._walkRange( + ctx, + potentialItems, + treeID, objID, typ, gap.Beg, gap.End, + func(k btrfsprim.Key, v keyio.ItemPtr, runBeg, runEnd uint64) { // TODO: This is dumb and greedy. if last < runBeg { // log an error @@ -877,8 +865,6 @@ func (o *rebuilder) _wantRange( o.wantAugment(wantCtx, treeID, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node)) } last = runEnd - - return true }) if last < gap.End { // log an error -- cgit v1.2.3-2-g168b From 2aa2b9de6c9f967437dacd8f105e5a66c9bdc667 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 21:25:35 -0700 Subject: rebuildnodes: _walkRange: Tidy up --- .../btrfsinspect/rebuildnodes/rebuild.go | 25 +++++++++------------- 1 file changed, 10 insertions(+), 15 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 28591dd..87d9f35 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -717,18 +717,6 @@ func (o *rebuilder) _walkRange( beg, end uint64, fn func(key btrfsprim.Key, ptr keyio.ItemPtr, beg, end uint64), ) { - sizeFn := func(key btrfsprim.Key) (uint64, error) { - ptr, ok := items.Load(key) - if !ok { - panic(fmt.Errorf("should not happen: could not load key: %v", keyAndTree{TreeID: treeID, Key: key})) - } - sizeAndErr, ok := o.keyIO.Sizes[ptr] - if !ok { - panic(fmt.Errorf("should not happen: %v item did not have a size recorded", typ)) - } - return sizeAndErr.Size, sizeAndErr.Err - } - min := btrfsprim.Key{ ObjectID: objID, ItemType: typ, @@ -751,11 +739,18 @@ func (o *rebuilder) _walkRange( } }, func(runKey btrfsprim.Key, runPtr keyio.ItemPtr) bool { - runSize, err := sizeFn(runKey) - if err != nil { - o.fsErr(ctx, fmt.Errorf("get size: %v: %w", keyAndTree{TreeID: treeID, Key: runKey}, err)) + runSizeAndErr, ok := o.keyIO.Sizes[runPtr] + if !ok { + panic(fmt.Errorf("should not happen: %v (%v) did not have a size recorded", + runPtr, keyAndTree{TreeID: treeID, Key: runKey})) + } + if runSizeAndErr.Err != nil { + o.fsErr(ctx, fmt.Errorf("get size: %v (%v): %w", + runPtr, keyAndTree{TreeID: treeID, Key: runKey}, + runSizeAndErr.Err)) return true } + runSize := runSizeAndErr.Size if runSize == 0 { return true } -- cgit v1.2.3-2-g168b From 3a7a736d1a6dd574a03e31ca7bcde2ea60767fd6 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 21:40:38 -0700 Subject: rebuildnodes: Don't store negative results that are unlikely to come up again --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 87d9f35..9a4bfab 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -515,6 +515,10 @@ func (treeQueue *treeAugmentQueue) has(wantKey string) bool { } func (treeQueue *treeAugmentQueue) store(wantKey string, choices containers.Set[btrfsvol.LogicalAddr]) { + if len(choices) == 0 && (strings.Contains(wantKey, " name=") || strings.Contains(wantKey, "-")) { + // This wantKey is unlikely to come up again, so it's not worth storing a negative result. + return + } wantKey = shortenWantKey(wantKey) beg := treeQueue.keyBuf.Len() if treeQueue.keyBuf.Cap()-beg < len(wantKey) { -- cgit v1.2.3-2-g168b From af5f03de8052d144027e7ba99000e3196056adce Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 5 Jan 2023 00:35:48 -0700 Subject: rebuildnodes: Speed up treeAugmentQueue.has() --- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 9a4bfab..ebca2bd 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -495,18 +495,19 @@ func shortenWantKey(wantKey string) string { func (treeQueue *treeAugmentQueue) has(wantKey string) bool { if treeQueue != nil { + wantKey = shortenWantKey(wantKey) if treeQueue.zero != nil { - if _, ok := treeQueue.zero[shortenWantKey(wantKey)]; ok { + if _, ok := treeQueue.zero[wantKey]; ok { return true } } if treeQueue.single != nil { - if _, ok := treeQueue.single[shortenWantKey(wantKey)]; ok { + if _, ok := treeQueue.single[wantKey]; ok { return true } } if treeQueue.multi != nil { - if _, ok := treeQueue.multi[shortenWantKey(wantKey)]; ok { + if _, ok := treeQueue.multi[wantKey]; ok { return true } } -- cgit v1.2.3-2-g168b