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 --- .../rebuildnodes/btrees/rebuilt_btrees.go | 16 ++++++++--- .../btrfsinspect/rebuildnodes/keyio/keyio.go | 6 ++++ .../btrfsinspect/rebuildnodes/rebuild.go | 32 ++++++++++++---------- .../btrfsinspect/rebuildnodes/rebuild_graph.go | 10 ++----- 4 files changed, 39 insertions(+), 25 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go index b53a28e..b1ae7be 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go @@ -363,15 +363,23 @@ func (tree *rebuiltTree) indexNode(graph pkggraph.Graph, node btrfsvol.LogicalAd } } +// Resolve a key to a keyio.ItemPtr. +// +// It is not nescessary to call AddTree for that tree first; Resolve will +// call it for you. +func (ts *RebuiltTrees) Resolve(ctx context.Context, treeID btrfsprim.ObjID, key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) { + if !ts.AddTree(ctx, treeID) { + return keyio.ItemPtr{}, false + } + return ts.trees[treeID].Items.Load(key) +} + // Load reads an item from a tree. // // It is not nescessary to call AddTree for that tree first; Load will // call it for you. func (ts *RebuiltTrees) Load(ctx context.Context, treeID btrfsprim.ObjID, key btrfsprim.Key) (item btrfsitem.Item, ok bool) { - if !ts.AddTree(ctx, treeID) { - return nil, false - } - ptr, ok := ts.trees[treeID].Items.Load(key) + ptr, ok := ts.Resolve(ctx, treeID, key) if !ok { return nil, false } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go index 24c3dcf..eb03004 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go @@ -39,6 +39,7 @@ type Handle struct { sb btrfstree.Superblock graph graph.Graph + Names map[ItemPtr][]byte Sizes map[ItemPtr]SizeAndErr cache *containers.LRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]] @@ -49,6 +50,7 @@ func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) rawFile: file, sb: sb, + Names: make(map[ItemPtr][]byte), Sizes: make(map[ItemPtr]SizeAndErr), cache: containers.NewLRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]](textui.Tunable(8)), @@ -62,6 +64,10 @@ func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree. Idx: i, } switch itemBody := item.Body.(type) { + case btrfsitem.DirEntry: + if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY { + o.Names[ptr] = append([]byte(nil), itemBody.Name...) + } case btrfsitem.ExtentCSum: o.Sizes[ptr] = SizeAndErr{ Size: uint64(itemBody.Size()), 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, diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go index bf4c95d..271595e 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go @@ -7,7 +7,6 @@ package rebuildnodes import ( "context" "fmt" - "reflect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" @@ -20,7 +19,7 @@ type rebuildCallbacks interface { fsErr(ctx context.Context, e error) want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) - wantFunc(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) + wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) wantCSum(ctx context.Context, reason string, beg, end btrfsvol.LogicalAddr) // interval is [beg, end) wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) } @@ -65,13 +64,10 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, // siblings switch item.Key.ItemType { case btrfsitem.DIR_ITEM_KEY: - o.wantFunc(ctx, "corresponding DIR_INDEX", + o.wantDirIndex(ctx, "corresponding DIR_INDEX", treeID, item.Key.ObjectID, - btrfsitem.DIR_INDEX_KEY, - func(peerItem btrfsitem.Item) bool { - return reflect.DeepEqual(item, peerItem) - }) + body.Name) case btrfsitem.DIR_INDEX_KEY: o.wantOff(ctx, "corresponding DIR_ITEM", treeID, -- 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') 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') 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 --- .../rebuildnodes/btrees/rebuilt_btrees.go | 9 ++-- .../btrfsinspect/rebuildnodes/rebuild.go | 58 +++++++++++++--------- lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 18 ++++--- 3 files changed, 52 insertions(+), 33 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go index b1ae7be..ffe225a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go @@ -305,7 +305,7 @@ func (tree *rebuiltTree) indexLeafs(ctx context.Context, graph pkggraph.Graph) { progress() for _, node := range maps.SortedKeys(graph.Nodes) { - tree.indexNode(graph, node, nodeToRoots, progress, nil) + tree.indexNode(ctx, graph, node, nodeToRoots, progress, nil) } progressWriter.Done() @@ -317,8 +317,11 @@ func (tree *rebuiltTree) indexLeafs(ctx context.Context, graph pkggraph.Graph) { } } -func (tree *rebuiltTree) indexNode(graph pkggraph.Graph, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) { +func (tree *rebuiltTree) indexNode(ctx context.Context, graph pkggraph.Graph, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) { defer progress() + if err := ctx.Err(); err != nil { + return + } if _, done := index[node]; done { return } @@ -339,7 +342,7 @@ func (tree *rebuiltTree) indexNode(graph pkggraph.Graph, node btrfsvol.LogicalAd return !tree.isOwnerOK(graph.Nodes[kp.FromNode].Owner, graph.Nodes[kp.FromNode].Generation) }) for _, kp := range kps { - tree.indexNode(graph, kp.FromNode, index, progress, stack) + tree.indexNode(ctx, graph, kp.FromNode, index, progress, stack) if len(index[kp.FromNode]) > 0 { if roots == nil { roots = make(containers.Set[btrfsvol.LogicalAddr]) 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++ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index 7e96e29..7e19802 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -20,14 +20,15 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) -func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (graph.Graph, *keyio.Handle, error) { - dlog.Infof(ctx, "Reading node data from FS...") - +func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (btrfstree.Superblock, graph.Graph, *keyio.Handle, error) { + dlog.Info(ctx, "Reading superblock...") sb, err := fs.Superblock() if err != nil { - return graph.Graph{}, nil, err + return btrfstree.Superblock{}, graph.Graph{}, nil, err } + dlog.Infof(ctx, "Reading node data from FS...") + var stats textui.Portion[int] stats.D = countNodes(scanResults) progressWriter := textui.NewProgress[textui.Portion[int]]( @@ -40,11 +41,14 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca progressWriter.Set(stats) for _, devResults := range scanResults { for laddr := range devResults.FoundNodes { + if err := ctx.Err(); err != nil { + return btrfstree.Superblock{}, graph.Graph{}, nil, err + } nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, }) if err != nil { - return graph.Graph{}, nil, err + return btrfstree.Superblock{}, graph.Graph{}, nil, err } nodeGraph.InsertNode(nodeRef) @@ -61,9 +65,9 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca dlog.Info(ctx, "... done reading node data") if err := nodeGraph.FinalCheck(ctx, fs, *sb); err != nil { - return graph.Graph{}, nil, err + return btrfstree.Superblock{}, graph.Graph{}, nil, err } keyIO.SetGraph(*nodeGraph) - return *nodeGraph, keyIO, nil + return *sb, *nodeGraph, keyIO, nil } -- cgit v1.2.3-2-g168b From 6ce1332d3cac5b74d2f049861f04cc2fa282d747 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 29 Dec 2022 23:53:55 -0700 Subject: cmd/btrfs-rec inspect rebuild-nodes: Optimize memory use --- lib/textui/log_memstats.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/textui/log_memstats.go b/lib/textui/log_memstats.go index 6e3c3a1..7ef35da 100644 --- a/lib/textui/log_memstats.go +++ b/lib/textui/log_memstats.go @@ -19,14 +19,14 @@ type LiveMemUse struct { var _ fmt.Stringer = (*LiveMemUse)(nil) -var liveMemUseUpdateInterval = Tunable(1 * time.Second) +var LiveMemUseUpdateInterval = Tunable(1 * time.Second) func (o *LiveMemUse) String() string { o.mu.Lock() // runtime.ReadMemStats() calls stopTheWorld(), so we want to // rate-limit how often we call it. - if now := time.Now(); now.Sub(o.last) > liveMemUseUpdateInterval { + if now := time.Now(); now.Sub(o.last) > LiveMemUseUpdateInterval { runtime.ReadMemStats(&o.stats) o.last = now } -- 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/btrees/forrest.go | 173 ++++++++ .../rebuildnodes/btrees/rebuilt_btrees.go | 482 --------------------- .../btrfsinspect/rebuildnodes/btrees/tree.go | 299 +++++++++++++ .../btrfsinspect/rebuildnodes/rebuild.go | 52 +-- 4 files changed, 498 insertions(+), 508 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go new file mode 100644 index 0000000..791e646 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -0,0 +1,173 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrees + +import ( + "context" + + "github.com/datawire/dlib/dlog" + + "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/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +// RebuiltForrest is an abstraction for rebuilding and accessing +// potentially broken btrees. +// +// It is conceptually a btrfstree.TreeOperator, and adds similar +// broken-tree handling to btrfsutil.BrokenForrest. However, the API +// is different thant btrfstree.TreeOperator, and is much more +// efficient than btrfsutil.BrokenForrest. +// +// The efficiency improvements are possible because of the API +// differences, which are necessary for how it is used in +// rebuildnodes: +// +// - it consumes an already-read graph.Graph instead of reading the +// graph itself +// +// - it does not use `btrfstree.TreePath` +// +// - it does not keep track of errors encountered in a tree +// +// Additionally, it provides some functionality that +// btrfsutil.BrokenForrest does not: +// +// - it provides a .LeafToRoots() method to advise on what +// additional roots should be added +// +// - it provides a .COWDistance() method to compare how related two +// trees are +// +// A zero RebuiltForrest is invalid; it must be initialized with +// NewRebuiltForrest(). +type RebuiltForrest struct { + // static + sb btrfstree.Superblock + graph pkggraph.Graph + keyIO *keyio.Handle + + // static callbacks + cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) + cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) + cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) + + // mutable + trees map[btrfsprim.ObjID]*RebuiltTree +} + +// NewRebuiltForrest returns a new RebuiltForrest instance. All of +// the callbacks must be non-nil. +func NewRebuiltForrest( + sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle, + cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key), + cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool), + cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool), +) *RebuiltForrest { + return &RebuiltForrest{ + sb: sb, + graph: graph, + keyIO: keyIO, + + cbAddedItem: cbAddedItem, + cbLookupRoot: cbLookupRoot, + cbLookupUUID: cbLookupUUID, + + trees: make(map[btrfsprim.ObjID]*RebuiltTree), + } +} + +// Tree returns a given tree, initializing it if nescessary. If it is +// unable to initialize the tree, then nil is returned, and nothing is +// done to the forrest. +// +// The tree is initialized with the normal root node of the tree. +func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree { + if !ts.addTree(ctx, treeID, nil) { + return nil + } + return ts.trees[treeID] +} + +func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) { + if _, ok := ts.trees[treeID]; ok { + return true + } + if slices.Contains(treeID, stack) { + return false + } + stack = append(stack, treeID) + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack) + dlog.Info(ctx, "adding tree...") + + tree := &RebuiltTree{ + ID: treeID, + Roots: make(containers.Set[btrfsvol.LogicalAddr]), + Leafs: make(containers.Set[btrfsvol.LogicalAddr]), + forrest: ts, + } + var root btrfsvol.LogicalAddr + switch treeID { + case btrfsprim.ROOT_TREE_OBJECTID: + root = ts.sb.RootTree + case btrfsprim.CHUNK_TREE_OBJECTID: + root = ts.sb.ChunkTree + case btrfsprim.TREE_LOG_OBJECTID: + root = ts.sb.LogTree + case btrfsprim.BLOCK_GROUP_TREE_OBJECTID: + root = ts.sb.BlockGroupRoot + default: + if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) { + return false + } + rootOff, rootItem, ok := ts.cbLookupRoot(ctx, treeID) + if !ok { + return false + } + root = rootItem.ByteNr + tree.UUID = rootItem.UUID + if rootItem.ParentUUID != (btrfsprim.UUID{}) { + tree.ParentGen = rootOff + if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) { + return false + } + parentID, ok := ts.cbLookupUUID(ctx, rootItem.ParentUUID) + if !ok { + return false + } + if !ts.addTree(ctx, parentID, append(stack, treeID)) { + return false + } + tree.Parent = ts.trees[parentID] + } + } + tree.indexLeafs(ctx) + + ts.trees[treeID] = tree + if root != 0 { + tree.AddRoot(ctx, root) + } + + return true +} + +// ListRoots returns a listing of all initialized trees and their root +// nodes. +// +// Do not mutate the set of roots for a tree; it is a pointer to the +// RebuiltForrest's internal set! +func (ts *RebuiltForrest) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { + ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(ts.trees)) + for treeID := range ts.trees { + ret[treeID] = ts.trees[treeID].Roots + } + return ret +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go deleted file mode 100644 index ffe225a..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go +++ /dev/null @@ -1,482 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrees - -import ( - "context" - "fmt" - "time" - - "github.com/datawire/dlib/dlog" - - "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/btrfstree" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" - "git.lukeshu.com/btrfs-progs-ng/lib/textui" -) - -type rebuiltTree struct { - // static - ID btrfsprim.ObjID - UUID btrfsprim.UUID - Parent *rebuiltTree - ParentGen btrfsprim.Generation // offset of this tree's root item - - // all leafs (lvl=0) that pass .isOwnerOK, even if not in the tree - leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] - keys containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] - - // mutable - Roots containers.Set[btrfsvol.LogicalAddr] - Leafs containers.Set[btrfsvol.LogicalAddr] - Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] -} - -// isOwnerOK returns whether it is permissible for a node with -// .Head.Owner=owner to be in this tree. -func (tree *rebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool { - for { - if owner == tree.ID { - return true - } - if tree.Parent == nil || gen >= tree.ParentGen { - return false - } - tree = tree.Parent - } -} - -// cowDistance returns how many COW-snapshots down the 'tree' is from -// the 'parent'. -func (tree *rebuiltTree) cowDistance(parentID btrfsprim.ObjID) (dist int, ok bool) { - for { - if parentID == tree.ID { - return dist, true - } - if tree.Parent == nil { - return 0, false - } - tree = tree.Parent - dist++ - } -} - -func (tree *rebuiltTree) shouldReplace(graph pkggraph.Graph, oldNode, newNode btrfsvol.LogicalAddr) bool { - oldDist, _ := tree.cowDistance(graph.Nodes[oldNode].Owner) - newDist, _ := tree.cowDistance(graph.Nodes[newNode].Owner) - switch { - case newDist < oldDist: - // Replace the old one with the new lower-dist one. - return true - case newDist > oldDist: - // Retain the old lower-dist one. - return false - default: - oldGen := graph.Nodes[oldNode].Generation - newGen := graph.Nodes[newNode].Generation - switch { - case newGen > oldGen: - // Replace the old one with the new higher-gen one. - return true - case newGen < oldGen: - // Retain the old higher-gen one. - return false - default: - // This is a panic because I'm not really sure what the best way to - // handle this is, and so if this happens I want the program to crash - // and force me to figure out how to handle it. - panic(fmt.Errorf("dup nodes in tree=%v: old=%v=%v ; new=%v=%v", - tree.ID, - oldNode, graph.Nodes[oldNode], - newNode, graph.Nodes[newNode])) - } - } -} - -// RebuiltTrees is an abstraction for rebuilding and accessing -// potentially broken btrees. -// -// It is conceptually a btrfstree.TreeOperator, and adds similar -// broken-tree handling to btrfsutil.BrokenTrees. However, the API is -// different thant btrfstree.TreeOperator, and is much more efficient -// than btrfsutil.BrokenTrees. -// -// The efficiency improvements are possible because of the API -// differences, which are necessary for how it is used in -// rebuildnodes: -// -// - it consumes an already-read graph.Graph instead of reading the -// graph itself -// -// - it does not use `btrfstree.TreePath` -// -// - it does not keep track of errors encountered in a tree -// -// Additionally, it provides some functionality that -// btrfsutil.BrokenTrees does not: -// -// - it provides a .LeafToRoots() method to advise on what -// additional roots should be added -// -// - it provides a .COWDistance() method to compare how related two -// trees are -// -// A zero RebuiltTrees is invalid; it must be initialized with -// NewRebuiltTrees(). -type RebuiltTrees struct { - // static - sb btrfstree.Superblock - graph pkggraph.Graph - keyIO *keyio.Handle - - // static callbacks - cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) - cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) - cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) - - // mutable - trees map[btrfsprim.ObjID]*rebuiltTree -} - -// NewRebuiltTrees returns a new RebuiltTrees instance. All of the -// callbacks must be non-nil. -func NewRebuiltTrees( - sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle, - cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key), - cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool), - cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool), -) *RebuiltTrees { - return &RebuiltTrees{ - sb: sb, - graph: graph, - keyIO: keyIO, - - cbAddedItem: cbAddedItem, - cbLookupRoot: cbLookupRoot, - cbLookupUUID: cbLookupUUID, - - trees: make(map[btrfsprim.ObjID]*rebuiltTree), - } -} - -type rootStats struct { - Leafs textui.Portion[int] - AddedItems int - ReplacedItems int -} - -func (s rootStats) String() string { - return textui.Sprintf("%v (added %v items, replaced %v items)", - s.Leafs, s.AddedItems, s.ReplacedItems) -} - -// AddRoot adds an additional root node to an existing tree. It is -// useful to call .AddRoot() to re-attach part of the tree that has -// been broken off. -// -// It is invalid (panic) to call AddRoot for a tree without having -// called AddTree first. -func (ts *RebuiltTrees) AddRoot(ctx context.Context, treeID btrfsprim.ObjID, rootNode btrfsvol.LogicalAddr) { - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", treeID, rootNode)) - tree := ts.trees[treeID] - tree.Roots.Insert(rootNode) - - var stats rootStats - stats.Leafs.D = len(tree.leafToRoots) - progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - for i, leaf := range maps.SortedKeys(tree.leafToRoots) { - stats.Leafs.N = i - progressWriter.Set(stats) - if tree.Leafs.Has(leaf) || !tree.leafToRoots[leaf].Has(rootNode) { - continue - } - tree.Leafs.Insert(leaf) - for j, itemKey := range ts.graph.Nodes[leaf].Items { - newPtr := keyio.ItemPtr{ - Node: leaf, - Idx: j, - } - if oldPtr, exists := tree.Items.Load(itemKey); !exists { - tree.Items.Store(itemKey, newPtr) - stats.AddedItems++ - } else if tree.shouldReplace(ts.graph, oldPtr.Node, newPtr.Node) { - tree.Items.Store(itemKey, newPtr) - stats.ReplacedItems++ - } - ts.cbAddedItem(ctx, treeID, itemKey) - progressWriter.Set(stats) - } - } - stats.Leafs.N = len(tree.leafToRoots) - progressWriter.Set(stats) - progressWriter.Done() -} - -// AddTree initializes the given tree, returning true if it was able -// to do so, or false if there was a problem and nothing was done. -// The tree is initialized with the normal root node of the tree. -// -// Subsequent calls to AddTree for the same tree are no-ops. -func (ts *RebuiltTrees) AddTree(ctx context.Context, treeID btrfsprim.ObjID) (ok bool) { - return ts.addTree(ctx, treeID, nil) -} - -func (ts *RebuiltTrees) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) { - if _, ok := ts.trees[treeID]; ok { - return true - } - if slices.Contains(treeID, stack) { - return false - } - stack = append(stack, treeID) - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack) - dlog.Info(ctx, "adding tree...") - - tree := &rebuiltTree{ - ID: treeID, - Roots: make(containers.Set[btrfsvol.LogicalAddr]), - Leafs: make(containers.Set[btrfsvol.LogicalAddr]), - } - var root btrfsvol.LogicalAddr - switch treeID { - case btrfsprim.ROOT_TREE_OBJECTID: - root = ts.sb.RootTree - case btrfsprim.CHUNK_TREE_OBJECTID: - root = ts.sb.ChunkTree - case btrfsprim.TREE_LOG_OBJECTID: - root = ts.sb.LogTree - case btrfsprim.BLOCK_GROUP_TREE_OBJECTID: - root = ts.sb.BlockGroupRoot - default: - if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) { - return false - } - rootOff, rootItem, ok := ts.cbLookupRoot(ctx, treeID) - if !ok { - return false - } - root = rootItem.ByteNr - tree.UUID = rootItem.UUID - if rootItem.ParentUUID != (btrfsprim.UUID{}) { - tree.ParentGen = rootOff - if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) { - return false - } - parentID, ok := ts.cbLookupUUID(ctx, rootItem.ParentUUID) - if !ok { - return false - } - if !ts.addTree(ctx, parentID, append(stack, treeID)) { - return false - } - tree.Parent = ts.trees[parentID] - } - } - tree.indexLeafs(ctx, ts.graph) - - ts.trees[treeID] = tree - if root != 0 { - ts.AddRoot(ctx, treeID, root) - } - - return true -} - -func (tree *rebuiltTree) indexLeafs(ctx context.Context, graph pkggraph.Graph) { - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep", "index-nodes") - - nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - - var stats textui.Portion[int] - stats.D = len(graph.Nodes) - progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - progress := func() { - stats.N = len(nodeToRoots) - progressWriter.Set(stats) - } - - progress() - for _, node := range maps.SortedKeys(graph.Nodes) { - tree.indexNode(ctx, graph, node, nodeToRoots, progress, nil) - } - progressWriter.Done() - - tree.leafToRoots = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - for node, roots := range nodeToRoots { - if graph.Nodes[node].Level == 0 && len(roots) > 0 { - tree.leafToRoots[node] = roots - } - } -} - -func (tree *rebuiltTree) indexNode(ctx context.Context, graph pkggraph.Graph, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) { - defer progress() - if err := ctx.Err(); err != nil { - return - } - if _, done := index[node]; done { - return - } - if slices.Contains(node, stack) { - // This is a panic because graph.FinalCheck() should - // have already checked for loops. - panic("loop") - } - if !tree.isOwnerOK(graph.Nodes[node].Owner, graph.Nodes[node].Generation) { - index[node] = nil - return - } - - // tree.leafToRoots - stack = append(stack, node) - var roots containers.Set[btrfsvol.LogicalAddr] - kps := slices.RemoveAllFunc(graph.EdgesTo[node], func(kp *pkggraph.Edge) bool { - return !tree.isOwnerOK(graph.Nodes[kp.FromNode].Owner, graph.Nodes[kp.FromNode].Generation) - }) - for _, kp := range kps { - tree.indexNode(ctx, graph, kp.FromNode, index, progress, stack) - if len(index[kp.FromNode]) > 0 { - if roots == nil { - roots = make(containers.Set[btrfsvol.LogicalAddr]) - } - roots.InsertFrom(index[kp.FromNode]) - } - } - if roots == nil { - roots = containers.NewSet[btrfsvol.LogicalAddr](node) - } - index[node] = roots - - // tree.keys - for i, key := range graph.Nodes[node].Items { - if oldPtr, ok := tree.keys.Load(key); !ok || tree.shouldReplace(graph, oldPtr.Node, node) { - tree.keys.Store(key, keyio.ItemPtr{ - Node: node, - Idx: i, - }) - } - } -} - -// Resolve a key to a keyio.ItemPtr. -// -// It is not nescessary to call AddTree for that tree first; Resolve will -// call it for you. -func (ts *RebuiltTrees) Resolve(ctx context.Context, treeID btrfsprim.ObjID, key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) { - if !ts.AddTree(ctx, treeID) { - return keyio.ItemPtr{}, false - } - return ts.trees[treeID].Items.Load(key) -} - -// Load reads an item from a tree. -// -// It is not nescessary to call AddTree for that tree first; Load will -// call it for you. -func (ts *RebuiltTrees) Load(ctx context.Context, treeID btrfsprim.ObjID, key btrfsprim.Key) (item btrfsitem.Item, ok bool) { - ptr, ok := ts.Resolve(ctx, treeID, key) - if !ok { - return nil, false - } - return ts.keyIO.ReadItem(ctx, ptr) -} - -// Search searches for an item from a tree. -// -// It is not nescessary to call AddTree for that tree first; Search -// will call it for you. -func (ts *RebuiltTrees) Search(ctx context.Context, treeID btrfsprim.ObjID, fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) { - if !ts.AddTree(ctx, treeID) { - return btrfsprim.Key{}, false - } - k, _, ok := ts.trees[treeID].Items.Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int { - return fn(k) - }) - return k, ok -} - -// Search searches for a range of items from a tree. -// -// It is not nescessary to call AddTree for that tree first; SearchAll -// will call it for you. -func (ts *RebuiltTrees) SearchAll(ctx context.Context, treeID btrfsprim.ObjID, fn func(btrfsprim.Key) int) []btrfsprim.Key { - if !ts.AddTree(ctx, treeID) { - return nil - } - kvs := ts.trees[treeID].Items.SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int { - return fn(k) - }) - if len(kvs) == 0 { - return nil - } - ret := make([]btrfsprim.Key, len(kvs)) - for i := range kvs { - ret[i] = kvs[i].K - } - return ret -} - -// LeafToRoots returns the list of potential roots (to pass to -// .AddRoot) that include a given leaf-node. -// -// It is not nescessary to call AddTree for the tree first; -// LeafToRoots will call it for you. -func (ts *RebuiltTrees) LeafToRoots(ctx context.Context, treeID btrfsprim.ObjID, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { - if !ts.AddTree(ctx, treeID) { - return nil - } - if ts.graph.Nodes[leaf].Level != 0 { - panic(fmt.Errorf("should not happen: NodeToRoots(tree=%v, leaf=%v): not a leaf", - treeID, leaf)) - } - ret := make(containers.Set[btrfsvol.LogicalAddr]) - for root := range ts.trees[treeID].leafToRoots[leaf] { - if ts.trees[treeID].Roots.Has(root) { - panic(fmt.Errorf("should not happen: NodeToRoots(tree=%v, leaf=%v): tree contains root=%v but not leaf", - treeID, leaf, root)) - } - ret.Insert(root) - } - if len(ret) == 0 { - return nil - } - return ret -} - -// Keys returns a map of all keys in node that would be valid in this tree. -// -// It is invalid (panic) to call Keys for a tree without having called -// AddTree first. -func (ts *RebuiltTrees) Keys(treeID btrfsprim.ObjID) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { - return &ts.trees[treeID].keys -} - -// COWDistance returns how many COW-snapshots down from the 'child' -// tree is from the 'parent' tree. -// -// It is invalid (panic) to call COWDistance for a tree without having -// called AddTree for the child first. -func (ts *RebuiltTrees) COWDistance(ctx context.Context, childID, parentID btrfsprim.ObjID) (dist int, ok bool) { - return ts.trees[childID].cowDistance(parentID) -} - -// ListRoots returns a listing of all initialized trees and their root -// nodes. -// -// Do not mutate the set of roots for a tree; it is a pointer to the -// RebuiltTrees' internal set! -func (ts *RebuiltTrees) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { - ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(ts.trees)) - for treeID := range ts.trees { - ret[treeID] = ts.trees[treeID].Roots - } - return ret -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go new file mode 100644 index 0000000..1fc1f52 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -0,0 +1,299 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrees + +import ( + "context" + "fmt" + "time" + + "github.com/datawire/dlib/dlog" + + "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/btrfsvol" + pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" + "git.lukeshu.com/btrfs-progs-ng/lib/textui" +) + +type RebuiltTree struct { + // static + ID btrfsprim.ObjID + UUID btrfsprim.UUID + Parent *RebuiltTree + ParentGen btrfsprim.Generation // offset of this tree's root item + forrest *RebuiltForrest + + // all leafs (lvl=0) that pass .isOwnerOK, even if not in the tree + leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] + keys containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] + + // mutable + Roots containers.Set[btrfsvol.LogicalAddr] + Leafs containers.Set[btrfsvol.LogicalAddr] + Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] +} + +// initializaton (called by `RebuiltForrest.Tree()`) /////////////////////////////////////////////////////////////////// + +func (tree *RebuiltTree) indexLeafs(ctx context.Context) { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep", "index-nodes") + + nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + + var stats textui.Portion[int] + stats.D = len(tree.forrest.graph.Nodes) + progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + progress := func() { + stats.N = len(nodeToRoots) + progressWriter.Set(stats) + } + + progress() + for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) { + tree.indexNode(ctx, node, nodeToRoots, progress, nil) + } + progressWriter.Done() + + tree.leafToRoots = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + for node, roots := range nodeToRoots { + if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 { + tree.leafToRoots[node] = roots + } + } +} + +func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) { + defer progress() + if err := ctx.Err(); err != nil { + return + } + if _, done := index[node]; done { + return + } + if slices.Contains(node, stack) { + // This is a panic because tree.forrest.graph.FinalCheck() should + // have already checked for loops. + panic("loop") + } + if !tree.isOwnerOK(tree.forrest.graph.Nodes[node].Owner, tree.forrest.graph.Nodes[node].Generation) { + index[node] = nil + return + } + + // tree.leafToRoots + stack = append(stack, node) + var roots containers.Set[btrfsvol.LogicalAddr] + kps := slices.RemoveAllFunc(tree.forrest.graph.EdgesTo[node], func(kp *pkggraph.Edge) bool { + return !tree.isOwnerOK(tree.forrest.graph.Nodes[kp.FromNode].Owner, tree.forrest.graph.Nodes[kp.FromNode].Generation) + }) + for _, kp := range kps { + tree.indexNode(ctx, kp.FromNode, index, progress, stack) + if len(index[kp.FromNode]) > 0 { + if roots == nil { + roots = make(containers.Set[btrfsvol.LogicalAddr]) + } + roots.InsertFrom(index[kp.FromNode]) + } + } + if roots == nil { + roots = containers.NewSet[btrfsvol.LogicalAddr](node) + } + index[node] = roots + + // tree.keys + for i, key := range tree.forrest.graph.Nodes[node].Items { + if oldPtr, ok := tree.keys.Load(key); !ok || tree.shouldReplace(oldPtr.Node, node) { + tree.keys.Store(key, keyio.ItemPtr{ + Node: node, + Idx: i, + }) + } + } +} + +// isOwnerOK returns whether it is permissible for a node with +// .Head.Owner=owner to be in this tree. +func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool { + for { + if owner == tree.ID { + return true + } + if tree.Parent == nil || gen >= tree.ParentGen { + return false + } + tree = tree.Parent + } +} + +// .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// + +type rootStats struct { + Leafs textui.Portion[int] + AddedItems int + ReplacedItems int +} + +func (s rootStats) String() string { + return textui.Sprintf("%v (added %v items, replaced %v items)", + s.Leafs, s.AddedItems, s.ReplacedItems) +} + +// AddRoot adds an additional root node to the tree. It is useful to +// call .AddRoot() to re-attach part of the tree that has been broken +// off. +func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) + tree.Roots.Insert(rootNode) + + var stats rootStats + stats.Leafs.D = len(tree.leafToRoots) + progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + for i, leaf := range maps.SortedKeys(tree.leafToRoots) { + stats.Leafs.N = i + progressWriter.Set(stats) + if tree.Leafs.Has(leaf) || !tree.leafToRoots[leaf].Has(rootNode) { + continue + } + tree.Leafs.Insert(leaf) + for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + newPtr := keyio.ItemPtr{ + Node: leaf, + Idx: j, + } + if oldPtr, exists := tree.Items.Load(itemKey); !exists { + tree.Items.Store(itemKey, newPtr) + stats.AddedItems++ + } else if tree.shouldReplace(oldPtr.Node, newPtr.Node) { + tree.Items.Store(itemKey, newPtr) + stats.ReplacedItems++ + } + tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) + progressWriter.Set(stats) + } + } + stats.Leafs.N = len(tree.leafToRoots) + progressWriter.Set(stats) + progressWriter.Done() +} + +func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool { + oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner) + newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner) + switch { + case newDist < oldDist: + // Replace the old one with the new lower-dist one. + return true + case newDist > oldDist: + // Retain the old lower-dist one. + return false + default: + oldGen := tree.forrest.graph.Nodes[oldNode].Generation + newGen := tree.forrest.graph.Nodes[newNode].Generation + switch { + case newGen > oldGen: + // Replace the old one with the new higher-gen one. + return true + case newGen < oldGen: + // Retain the old higher-gen one. + return false + default: + // This is a panic because I'm not really sure what the best way to + // handle this is, and so if this happens I want the program to crash + // and force me to figure out how to handle it. + panic(fmt.Errorf("dup nodes in tree=%v: old=%v=%v ; new=%v=%v", + tree.ID, + oldNode, tree.forrest.graph.Nodes[oldNode], + newNode, tree.forrest.graph.Nodes[newNode])) + } + } +} + +// main public API ///////////////////////////////////////////////////////////////////////////////////////////////////// + +// COWDistance returns how many COW-snapshots down the 'tree' is from +// the 'parent'. +func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) { + for { + if parentID == tree.ID { + return dist, true + } + if tree.Parent == nil { + return 0, false + } + tree = tree.Parent + dist++ + } +} + +// Resolve a key to a keyio.ItemPtr. +func (tree *RebuiltTree) Resolve(key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) { + return tree.Items.Load(key) +} + +// Load reads an item from a tree. +func (tree *RebuiltTree) Load(ctx context.Context, key btrfsprim.Key) (item btrfsitem.Item, ok bool) { + ptr, ok := tree.Resolve(key) + if !ok { + return nil, false + } + return tree.forrest.keyIO.ReadItem(ctx, ptr) +} + +// Search searches for an item from a tree. +func (tree *RebuiltTree) Search(fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) { + k, _, ok := tree.Items.Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int { + return fn(k) + }) + return k, ok +} + +// Search searches for a range of items from a tree. +func (tree *RebuiltTree) SearchAll(fn func(btrfsprim.Key) int) []btrfsprim.Key { + kvs := tree.Items.SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int { + return fn(k) + }) + if len(kvs) == 0 { + return nil + } + ret := make([]btrfsprim.Key, len(kvs)) + for i := range kvs { + ret[i] = kvs[i].K + } + return ret +} + +// LeafToRoots returns the list of potential roots (to pass to +// .AddRoot) that include a given leaf-node. +func (tree *RebuiltTree) LeafToRoots(leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { + if tree.forrest.graph.Nodes[leaf].Level != 0 { + panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf", + tree.ID, leaf)) + } + ret := make(containers.Set[btrfsvol.LogicalAddr]) + for root := range tree.leafToRoots[leaf] { + if tree.Roots.Has(root) { + panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf", + tree.ID, leaf, root)) + } + ret.Insert(root) + } + if len(ret) == 0 { + return nil + } + return ret +} + +// Keys returns a map of all keys in node that would be valid in this tree. +// +// Do not mutate the returned map; it is a pointer to the +// RebuiltTree's internal map! +func (tree *RebuiltTree) Keys() *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { + return &tree.keys +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 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 --- .../btrfsinspect/rebuildnodes/btrees/forrest.go | 9 +- .../btrfsinspect/rebuildnodes/btrees/tree.go | 148 +++++++++++++++------ .../btrfsinspect/rebuildnodes/rebuild.go | 20 +-- lib/containers/sortedmap.go | 4 + lib/textui/log.go | 16 ++- 5 files changed, 135 insertions(+), 62 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 791e646..c0b7698 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -17,6 +17,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/slices" + "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) // RebuiltForrest is an abstraction for rebuilding and accessing @@ -61,7 +62,9 @@ type RebuiltForrest struct { cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) // mutable - trees map[btrfsprim.ObjID]*RebuiltTree + trees map[btrfsprim.ObjID]*RebuiltTree + allItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] + incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] } // NewRebuiltForrest returns a new RebuiltForrest instance. All of @@ -81,7 +84,9 @@ func NewRebuiltForrest( cbLookupRoot: cbLookupRoot, cbLookupUUID: cbLookupUUID, - trees: make(map[btrfsprim.ObjID]*RebuiltTree), + trees: make(map[btrfsprim.ObjID]*RebuiltTree), + allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(16)), + incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(16)), } } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 1fc1f52..acc71db 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -30,14 +30,12 @@ type RebuiltTree struct { ParentGen btrfsprim.Generation // offset of this tree's root item forrest *RebuiltForrest - // all leafs (lvl=0) that pass .isOwnerOK, even if not in the tree + // all leafs (lvl=0) that pass .isOwnerOK, whether or not they're in the tree leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] - keys containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] // mutable Roots containers.Set[btrfsvol.LogicalAddr] Leafs containers.Set[btrfsvol.LogicalAddr] - Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] } // initializaton (called by `RebuiltForrest.Tree()`) /////////////////////////////////////////////////////////////////// @@ -106,16 +104,6 @@ func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAdd roots = containers.NewSet[btrfsvol.LogicalAddr](node) } index[node] = roots - - // tree.keys - for i, key := range tree.forrest.graph.Nodes[node].Items { - if oldPtr, ok := tree.keys.Load(key); !ok || tree.shouldReplace(oldPtr.Node, node) { - tree.keys.Store(key, keyio.ItemPtr{ - Node: node, - Idx: i, - }) - } - } } // isOwnerOK returns whether it is permissible for a node with @@ -135,14 +123,14 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati // .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// type rootStats struct { - Leafs textui.Portion[int] - AddedItems int - ReplacedItems int + Leafs textui.Portion[int] + AddedLeafs int + AddedItems int } func (s rootStats) String() string { - return textui.Sprintf("%v (added %v items, replaced %v items)", - s.Leafs, s.AddedItems, s.ReplacedItems) + return textui.Sprintf("%v (added %v leafs, added %v items)", + s.Leafs, s.AddedLeafs, s.AddedItems) } // AddRoot adds an additional root node to the tree. It is useful to @@ -158,29 +146,109 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA for i, leaf := range maps.SortedKeys(tree.leafToRoots) { stats.Leafs.N = i progressWriter.Set(stats) + if tree.Leafs.Has(leaf) || !tree.leafToRoots[leaf].Has(rootNode) { continue } + tree.Leafs.Insert(leaf) + stats.AddedLeafs++ + progressWriter.Set(stats) + + for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) + stats.AddedItems++ + progressWriter.Set(stats) + } + } + stats.Leafs.N = len(tree.leafToRoots) + progressWriter.Set(stats) + progressWriter.Done() +} + +// .Items() and .PotentialItems() ////////////////////////////////////////////////////////////////////////////////////// + +// Items returns a map of the items contained in this tree. +// +// Do not mutate the returned map; it is a pointer to the +// RebuiltTree's internal map! +func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-inc-items", fmt.Sprintf("tree=%v", tree.ID)) + return tree.items(ctx, tree.forrest.incItems, maps.SortedKeys(tree.Leafs)) +} + +// PotentialItems returns a map of items that could be added to this +// tree with .AddRoot(). +// +// Do not mutate the returned map; it is a pointer to the +// RebuiltTree's internal map! +func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-all-items", fmt.Sprintf("tree=%v", tree.ID)) + return tree.items(ctx, tree.forrest.allItems, maps.SortedKeys(tree.leafToRoots)) +} + +type itemIndex struct { + NumDups int + Leafs containers.Set[btrfsvol.LogicalAddr] + Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] +} + +type itemStats struct { + Leafs textui.Portion[int] + NumItems int + NumDups int +} + +func (s itemStats) String() string { + return textui.Sprintf("%v (%v items, %v dups)", + s.Leafs, s.NumItems, s.NumDups) +} + +func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex], leafs []btrfsvol.LogicalAddr) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { + index := cache.GetOrElse(tree.ID, func() *itemIndex { + return &itemIndex{ + Leafs: make(containers.Set[btrfsvol.LogicalAddr]), + } + }) + + var stats itemStats + stats.Leafs.D = len(leafs) + progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + progress := func(doneLeafs int) { + stats.Leafs.N = doneLeafs + stats.NumItems = index.Items.Len() + stats.NumDups = index.NumDups + progressWriter.Set(stats) + } + + for i, leaf := range leafs { + if index.Leafs.Has(leaf) { + continue + } + progress(i) + index.Leafs.Insert(leaf) for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { newPtr := keyio.ItemPtr{ Node: leaf, Idx: j, } - if oldPtr, exists := tree.Items.Load(itemKey); !exists { - tree.Items.Store(itemKey, newPtr) - stats.AddedItems++ - } else if tree.shouldReplace(oldPtr.Node, newPtr.Node) { - tree.Items.Store(itemKey, newPtr) - stats.ReplacedItems++ + if oldPtr, exists := index.Items.Load(itemKey); !exists { + index.Items.Store(itemKey, newPtr) + } else { + index.NumDups++ + if tree.shouldReplace(oldPtr.Node, newPtr.Node) { + index.Items.Store(itemKey, newPtr) + } } - tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) - progressWriter.Set(stats) + progress(i) } } - stats.Leafs.N = len(tree.leafToRoots) - progressWriter.Set(stats) - progressWriter.Done() + if stats.Leafs.N > 0 { + progress(len(leafs)) + progressWriter.Done() + } + + return &index.Items } func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool { @@ -233,13 +301,13 @@ func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok boo } // Resolve a key to a keyio.ItemPtr. -func (tree *RebuiltTree) Resolve(key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) { - return tree.Items.Load(key) +func (tree *RebuiltTree) Resolve(ctx context.Context, key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) { + return tree.Items(ctx).Load(key) } // Load reads an item from a tree. func (tree *RebuiltTree) Load(ctx context.Context, key btrfsprim.Key) (item btrfsitem.Item, ok bool) { - ptr, ok := tree.Resolve(key) + ptr, ok := tree.Resolve(ctx, key) if !ok { return nil, false } @@ -247,16 +315,16 @@ func (tree *RebuiltTree) Load(ctx context.Context, key btrfsprim.Key) (item btrf } // Search searches for an item from a tree. -func (tree *RebuiltTree) Search(fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) { - k, _, ok := tree.Items.Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int { +func (tree *RebuiltTree) Search(ctx context.Context, fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) { + k, _, ok := tree.Items(ctx).Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int { return fn(k) }) return k, ok } // Search searches for a range of items from a tree. -func (tree *RebuiltTree) SearchAll(fn func(btrfsprim.Key) int) []btrfsprim.Key { - kvs := tree.Items.SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int { +func (tree *RebuiltTree) SearchAll(ctx context.Context, fn func(btrfsprim.Key) int) []btrfsprim.Key { + kvs := tree.Items(ctx).SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int { return fn(k) }) if len(kvs) == 0 { @@ -289,11 +357,3 @@ func (tree *RebuiltTree) LeafToRoots(leaf btrfsvol.LogicalAddr) containers.Set[b } return ret } - -// Keys returns a map of all keys in node that would be valid in this tree. -// -// Do not mutate the returned map; it is a pointer to the -// RebuiltTree's internal map! -func (tree *RebuiltTree) Keys() *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { - return &tree.keys -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index b4feacf..85270d7 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -413,7 +413,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr ObjectID: objID, ItemType: typ, } - if key, ok := o.rebuilt.Tree(ctx, treeID).Search(func(key btrfsprim.Key) int { + if key, ok := o.rebuilt.Tree(ctx, treeID).Search(ctx, func(key btrfsprim.Key) int { key.Offset = 0 return tgt.Cmp(key) }); ok { @@ -423,7 +423,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr // OK, we need to insert it wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, treeID).Keys().Subrange( + o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, func(_ btrfsprim.Key, v keyio.ItemPtr) bool { wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) @@ -453,14 +453,14 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, tgt bt // check if we already have it - if _, ok := o.rebuilt.Tree(ctx, treeID).Search(tgt.Cmp); ok { + if _, ok := o.rebuilt.Tree(ctx, treeID).Search(ctx, tgt.Cmp); ok { return true } // OK, we need to insert it wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, treeID).Keys().Subrange( + o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) }, func(_ btrfsprim.Key, v keyio.ItemPtr) bool { wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(v.Node)) @@ -482,12 +482,12 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID ObjectID: objID, ItemType: typ, } - keys := o.rebuilt.Tree(ctx, treeID).SearchAll(func(key btrfsprim.Key) int { + keys := o.rebuilt.Tree(ctx, treeID).SearchAll(ctx, func(key btrfsprim.Key) int { key.Offset = 0 return tgt.Cmp(key) }) for _, itemKey := range keys { - itemPtr, ok := o.rebuilt.Tree(ctx, treeID).Resolve(itemKey) + itemPtr, ok := o.rebuilt.Tree(ctx, treeID).Resolve(ctx, itemKey) if !ok { o.ioErr(ctx, fmt.Errorf("could not resolve previously read item: %v", itemKey)) } @@ -499,7 +499,7 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID // OK, we need to insert it wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, treeID).Keys().Subrange( + o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, func(k btrfsprim.Key, v keyio.ItemPtr) bool { if fn(v) { @@ -536,7 +536,7 @@ func (o *rebuilder) _wantRange( } sizeFn := func(key btrfsprim.Key) (uint64, error) { - ptr, ok := o.rebuilt.Tree(ctx, treeID).Keys().Load(key) + ptr, ok := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Load(key) if !ok { panic(fmt.Errorf("should not happen: could not load key: %v", key)) } @@ -558,7 +558,7 @@ func (o *rebuilder) _wantRange( ItemType: typ, Offset: end - 1, } - runKeys := o.rebuilt.Tree(ctx, treeID).SearchAll(func(key btrfsprim.Key) int { + runKeys := o.rebuilt.Tree(ctx, treeID).SearchAll(ctx, func(key btrfsprim.Key) int { switch { case runMin.Cmp(key) < 0: return 1 @@ -645,7 +645,7 @@ func (o *rebuilder) _wantRange( ItemType: typ, Offset: gap.End - 1, } - o.rebuilt.Tree(ctx, treeID).Keys().Subrange( + o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( func(key btrfsprim.Key, _ keyio.ItemPtr) int { switch { case runMin.Cmp(key) < 0: diff --git a/lib/containers/sortedmap.go b/lib/containers/sortedmap.go index d6d2f9e..52308c9 100644 --- a/lib/containers/sortedmap.go +++ b/lib/containers/sortedmap.go @@ -92,3 +92,7 @@ func (m *SortedMap[K, V]) SearchAll(fn func(K, V) int) []OrderedKV[K, V] { return fn(kv.K, kv.V) }) } + +func (m *SortedMap[K, V]) Len() int { + return m.inner.Len() +} diff --git a/lib/textui/log.go b/lib/textui/log.go index 801e9eb..da303dd 100644 --- a/lib/textui/log.go +++ b/lib/textui/log.go @@ -317,18 +317,22 @@ func fieldOrd(key string) int { return -25 // step=rebuild (any substep) case "btrfsinspect.rebuild-nodes.rebuild.want.key": - return -7 + return -9 case "btrfsinspect.rebuild-nodes.rebuild.want.reason": - return -6 + return -8 case "btrfsinspect.rebuild-nodes.rebuild.add-tree": - return -5 + return -7 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep": - return -4 + return -6 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key": - return -3 + return -5 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason": - return -2 + return -4 case "btrfsinspect.rebuild-nodes.rebuild.add-root": + return -3 + case "btrfsinspect.rebuild-nodes.rebuild.index-inc-items": + return -2 + case "btrfsinspect.rebuild-nodes.rebuild.index-all-items": return -1 // other /////////////////////////////////////////////////////////////// -- 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/btrees/tree.go | 34 +----- .../btrfsinspect/rebuildnodes/rebuild.go | 133 +++++++++++---------- 2 files changed, 72 insertions(+), 95 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index acc71db..ffbaa0f 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -300,43 +300,15 @@ func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok boo } } -// Resolve a key to a keyio.ItemPtr. -func (tree *RebuiltTree) Resolve(ctx context.Context, key btrfsprim.Key) (ptr keyio.ItemPtr, ok bool) { - return tree.Items(ctx).Load(key) -} - -// Load reads an item from a tree. -func (tree *RebuiltTree) Load(ctx context.Context, key btrfsprim.Key) (item btrfsitem.Item, ok bool) { - ptr, ok := tree.Resolve(ctx, key) +// ReadItem reads an item from a tree. +func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) (item btrfsitem.Item, ok bool) { + ptr, ok := tree.Items(ctx).Load(key) if !ok { return nil, false } return tree.forrest.keyIO.ReadItem(ctx, ptr) } -// Search searches for an item from a tree. -func (tree *RebuiltTree) Search(ctx context.Context, fn func(btrfsprim.Key) int) (key btrfsprim.Key, ok bool) { - k, _, ok := tree.Items(ctx).Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int { - return fn(k) - }) - return k, ok -} - -// Search searches for a range of items from a tree. -func (tree *RebuiltTree) SearchAll(ctx context.Context, fn func(btrfsprim.Key) int) []btrfsprim.Key { - kvs := tree.Items(ctx).SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int { - return fn(k) - }) - if len(kvs) == 0 { - return nil - } - ret := make([]btrfsprim.Key, len(kvs)) - for i := range kvs { - ret[i] = kvs[i].K - } - return ret -} - // LeafToRoots returns the list of potential roots (to pass to // .AddRoot) that include a given leaf-node. func (tree *RebuiltTree) LeafToRoots(leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { 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 b1a69c59fdfbdb43de7f8ab949cfed19fcef6387 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 31 Dec 2022 12:03:51 -0700 Subject: textui: Add doc comments for LiveMemUse --- lib/textui/log_memstats.go | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'lib') diff --git a/lib/textui/log_memstats.go b/lib/textui/log_memstats.go index 7ef35da..31d526f 100644 --- a/lib/textui/log_memstats.go +++ b/lib/textui/log_memstats.go @@ -11,6 +11,13 @@ import ( "time" ) +// LiveMemUse is an object that stringifies as the live memory use of +// the program. +// +// It is intended to be used with dlog by attaching it as a field, so +// that all log lines include the current memory use: +// +// ctx = dlog.WithField(ctx, "mem", new(textui.LiveMemUse)) type LiveMemUse struct { mu sync.Mutex stats runtime.MemStats @@ -19,8 +26,13 @@ type LiveMemUse struct { var _ fmt.Stringer = (*LiveMemUse)(nil) +// LiveMemUseUpdateInterval is the shortest interval on which +// LiveMemUse is willing to update; we have this minimum interval +// because it stops the world to collect memory statistics, so we +// don't want to be updating the statistics too often. var LiveMemUseUpdateInterval = Tunable(1 * time.Second) +// String implements fmt.Stringer. func (o *LiveMemUse) String() string { o.mu.Lock() -- cgit v1.2.3-2-g168b From 0e73803c2f951fe9f9f0c09e8c2bf14ac0cd8ef2 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 31 Dec 2022 10:13:00 -0700 Subject: rebuildnodes/btrees: Tune cache sizes --- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index c0b7698..ef6da6f 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -85,8 +85,8 @@ func NewRebuiltForrest( cbLookupUUID: cbLookupUUID, trees: make(map[btrfsprim.ObjID]*RebuiltTree), - allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(16)), - incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(16)), + allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), + incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), } } -- 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/btrees/forrest.go | 23 ++++---- .../btrfsinspect/rebuildnodes/btrees/tree.go | 6 +++ .../btrfsinspect/rebuildnodes/rebuild.go | 63 ++++++++++++++-------- 3 files changed, 60 insertions(+), 32 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index ef6da6f..60f922d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -62,7 +62,7 @@ type RebuiltForrest struct { cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) // mutable - trees map[btrfsprim.ObjID]*RebuiltTree + trees containers.SyncMap[btrfsprim.ObjID, *RebuiltTree] allItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] } @@ -84,7 +84,6 @@ func NewRebuiltForrest( cbLookupRoot: cbLookupRoot, cbLookupUUID: cbLookupUUID, - trees: make(map[btrfsprim.ObjID]*RebuiltTree), allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), } @@ -99,11 +98,12 @@ func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *Reb if !ts.addTree(ctx, treeID, nil) { return nil } - return ts.trees[treeID] + tree, _ := ts.trees.Load(treeID) + return tree } func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) { - if _, ok := ts.trees[treeID]; ok { + if _, ok := ts.trees.Load(treeID); ok { return true } if slices.Contains(treeID, stack) { @@ -151,12 +151,12 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s if !ts.addTree(ctx, parentID, append(stack, treeID)) { return false } - tree.Parent = ts.trees[parentID] + tree.Parent, _ = ts.trees.Load(parentID) } } tree.indexLeafs(ctx) - ts.trees[treeID] = tree + ts.trees.Store(treeID, tree) if root != 0 { tree.AddRoot(ctx, root) } @@ -170,9 +170,10 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s // Do not mutate the set of roots for a tree; it is a pointer to the // RebuiltForrest's internal set! func (ts *RebuiltForrest) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { - ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(ts.trees)) - for treeID := range ts.trees { - ret[treeID] = ts.trees[treeID].Roots - } + ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) + ts.trees.Range(func(treeID btrfsprim.ObjID, tree *RebuiltTree) bool { + ret[treeID] = tree.Roots + return true + }) return ret } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index ffbaa0f..1daeefc 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -7,6 +7,7 @@ package btrees import ( "context" "fmt" + "sync" "time" "github.com/datawire/dlib/dlog" @@ -34,6 +35,7 @@ type RebuiltTree struct { leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] // mutable + mu sync.Mutex Roots containers.Set[btrfsvol.LogicalAddr] Leafs containers.Set[btrfsvol.LogicalAddr] } @@ -137,6 +139,8 @@ func (s rootStats) String() string { // call .AddRoot() to re-attach part of the tree that has been broken // off. func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { + tree.mu.Lock() + defer tree.mu.Unlock() ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) tree.Roots.Insert(rootNode) @@ -205,6 +209,8 @@ func (s itemStats) String() string { } func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex], leafs []btrfsvol.LogicalAddr) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { + tree.mu.Lock() + defer tree.mu.Unlock() index := cache.GetOrElse(tree.ID, func() *itemIndex { return &itemIndex{ Leafs: make(containers.Set[btrfsvol.LogicalAddr]), 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 --- .../btrfsinspect/rebuildnodes/btrees/forrest.go | 3 +- .../btrfsinspect/rebuildnodes/btrees/tree.go | 69 ++++++++++++---------- .../btrfsinspect/rebuildnodes/rebuild.go | 8 +-- lib/textui/log.go | 12 ++-- 4 files changed, 49 insertions(+), 43 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 60f922d..de21d9a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -63,6 +63,7 @@ type RebuiltForrest struct { // mutable trees containers.SyncMap[btrfsprim.ObjID, *RebuiltTree] + leafs *containers.LRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]] allItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] } @@ -84,6 +85,7 @@ func NewRebuiltForrest( cbLookupRoot: cbLookupRoot, cbLookupUUID: cbLookupUUID, + leafs: containers.NewLRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](textui.Tunable(8)), allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), } @@ -154,7 +156,6 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s tree.Parent, _ = ts.trees.Load(parentID) } } - tree.indexLeafs(ctx) ts.trees.Store(treeID, tree) if root != 0 { diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 1daeefc..678d25f 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -31,42 +31,44 @@ type RebuiltTree struct { ParentGen btrfsprim.Generation // offset of this tree's root item forrest *RebuiltForrest - // all leafs (lvl=0) that pass .isOwnerOK, whether or not they're in the tree - leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] - // mutable mu sync.Mutex Roots containers.Set[btrfsvol.LogicalAddr] Leafs containers.Set[btrfsvol.LogicalAddr] } -// initializaton (called by `RebuiltForrest.Tree()`) /////////////////////////////////////////////////////////////////// +// .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////////////////// -func (tree *RebuiltTree) indexLeafs(ctx context.Context) { - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep", "index-nodes") +// leafToRoots returns all leafs (lvl=0) in the filesystem that pass +// .isOwnerOK, whether or not they're in the tree. +func (tree *RebuiltTree) leafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] { + return tree.forrest.leafs.GetOrElse(tree.ID, func() map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] { + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-nodes", fmt.Sprintf("tree=%v", tree.ID)) - nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - var stats textui.Portion[int] - stats.D = len(tree.forrest.graph.Nodes) - progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - progress := func() { - stats.N = len(nodeToRoots) - progressWriter.Set(stats) - } + var stats textui.Portion[int] + stats.D = len(tree.forrest.graph.Nodes) + progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + progress := func() { + stats.N = len(nodeToRoots) + progressWriter.Set(stats) + } - progress() - for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) { - tree.indexNode(ctx, node, nodeToRoots, progress, nil) - } - progressWriter.Done() + progress() + for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) { + tree.indexNode(ctx, node, nodeToRoots, progress, nil) + } + progressWriter.Done() - tree.leafToRoots = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - for node, roots := range nodeToRoots { - if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 { - tree.leafToRoots[node] = roots + ret := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + for node, roots := range nodeToRoots { + if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 { + ret[node] = roots + } } - } + return ret + }) } func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) { @@ -145,13 +147,14 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA tree.Roots.Insert(rootNode) var stats rootStats - stats.Leafs.D = len(tree.leafToRoots) + leafToRoots := tree.leafToRoots(ctx) + stats.Leafs.D = len(leafToRoots) progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - for i, leaf := range maps.SortedKeys(tree.leafToRoots) { + for i, leaf := range maps.SortedKeys(leafToRoots) { stats.Leafs.N = i progressWriter.Set(stats) - if tree.Leafs.Has(leaf) || !tree.leafToRoots[leaf].Has(rootNode) { + if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { continue } @@ -165,7 +168,7 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA progressWriter.Set(stats) } } - stats.Leafs.N = len(tree.leafToRoots) + stats.Leafs.N = len(leafToRoots) progressWriter.Set(stats) progressWriter.Done() } @@ -188,7 +191,7 @@ func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsp // RebuiltTree's internal map! func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-all-items", fmt.Sprintf("tree=%v", tree.ID)) - return tree.items(ctx, tree.forrest.allItems, maps.SortedKeys(tree.leafToRoots)) + return tree.items(ctx, tree.forrest.allItems, maps.SortedKeys(tree.leafToRoots(ctx))) } type itemIndex struct { @@ -317,13 +320,15 @@ func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) (item // LeafToRoots returns the list of potential roots (to pass to // .AddRoot) that include a given leaf-node. -func (tree *RebuiltTree) LeafToRoots(leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { +func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { if tree.forrest.graph.Nodes[leaf].Level != 0 { panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf", tree.ID, leaf)) } + tree.mu.Lock() + defer tree.mu.Unlock() ret := make(containers.Set[btrfsvol.LogicalAddr]) - for root := range tree.leafToRoots[leaf] { + for root := range tree.leafToRoots(ctx)[leaf] { if tree.Roots.Has(root) { panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf", tree.ID, leaf, root)) 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 diff --git a/lib/textui/log.go b/lib/textui/log.go index da303dd..8327b67 100644 --- a/lib/textui/log.go +++ b/lib/textui/log.go @@ -322,17 +322,17 @@ func fieldOrd(key string) int { return -8 case "btrfsinspect.rebuild-nodes.rebuild.add-tree": return -7 - case "btrfsinspect.rebuild-nodes.rebuild.add-tree.substep": - return -6 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.key": - return -5 + return -6 case "btrfsinspect.rebuild-nodes.rebuild.add-tree.want.reason": - return -4 + return -5 case "btrfsinspect.rebuild-nodes.rebuild.add-root": - return -3 + return -4 case "btrfsinspect.rebuild-nodes.rebuild.index-inc-items": - return -2 + return -3 case "btrfsinspect.rebuild-nodes.rebuild.index-all-items": + return -2 + case "btrfsinspect.rebuild-nodes.rebuild.index-nodes": return -1 // other /////////////////////////////////////////////////////////////// -- 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 ++++++++++++--------- lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go | 4 + 2 files changed, 104 insertions(+), 76 deletions(-) (limited to 'lib') 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 }) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go index 8c43dad..9d91f23 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go @@ -25,3 +25,7 @@ func roundDown[T constraints.Integer](n, d T) T { func roundUp[T constraints.Integer](n, d T) T { return ((n + d - 1) / d) * d } + +func discardOK[T any](val T, _ bool) T { + return val +} -- 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') 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') 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') 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 +++++++++++++++++++--- .../btrfsinspect/rebuildnodes/rebuild_graph.go | 10 +++--- 2 files changed, 42 insertions(+), 9 deletions(-) (limited to 'lib') 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. diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go index 271595e..294f391 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go @@ -10,7 +10,6 @@ import ( "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" ) @@ -20,7 +19,7 @@ type rebuildCallbacks interface { want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) - wantCSum(ctx context.Context, reason string, beg, end btrfsvol.LogicalAddr) // interval is [beg, end) + wantCSum(ctx context.Context, reason string, inodeTree, inodeItem btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) // interval is [beg, end) wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) } @@ -165,10 +164,11 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, case btrfsitem.FILE_EXTENT_INLINE: // nothing case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC: - // TODO: Check if inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) + // NB: o.wantCSum checks inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) for us. o.wantCSum(ctx, "data sum", - roundDown(body.BodyExtent.DiskByteNr, btrfssum.BlockSize), - roundUp(body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes), btrfssum.BlockSize)) + treeID, item.Key.ObjectID, + body.BodyExtent.DiskByteNr, + body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes)) default: o.fsErr(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type)) } -- 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') 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') 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') 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') 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 --- .../btrfsinspect/rebuildnodes/rebuild.go | 3 +++ .../btrfsinspect/rebuildnodes/rebuild_graph.go | 22 ++++++++++++++++++++++ 2 files changed, 25 insertions(+) (limited to 'lib') 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, diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go index 294f391..9e40465 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go @@ -23,6 +23,28 @@ type rebuildCallbacks interface { wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) } +// handleWouldBeNoOp returns whether or not a call to handleItem for a +// given item type would be a no-op. +func handleWouldBeNoOp(typ btrfsprim.ItemType) bool { + switch typ { + case // btrfsitem.Dev + btrfsprim.DEV_ITEM_KEY, + // btrfsitem.DevStats + btrfsprim.PERSISTENT_ITEM_KEY, + // btrfsitem.Empty + btrfsprim.ORPHAN_ITEM_KEY, + btrfsprim.TREE_BLOCK_REF_KEY, + btrfsprim.SHARED_BLOCK_REF_KEY, + btrfsprim.FREE_SPACE_EXTENT_KEY, + btrfsprim.QGROUP_RELATION_KEY, + // btrfsite.ExtentCSum + btrfsprim.EXTENT_CSUM_KEY: + return true + default: + return false + } +} + func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, item btrfstree.Item) { // Notionally, just express the relationships shown in // https://btrfs.wiki.kernel.org/index.php/File:References.png (from the page -- cgit v1.2.3-2-g168b From 7ba1804756b43359a8b85e601b3836c8c4aac6cf Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 2 Jan 2023 18:26:51 -0700 Subject: rebuildnodes/btrees: Fix logging of the add-tree stack --- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index de21d9a..6bfa297 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -150,7 +150,7 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s if !ok { return false } - if !ts.addTree(ctx, parentID, append(stack, treeID)) { + if !ts.addTree(ctx, parentID, stack) { return false } tree.Parent, _ = ts.trees.Load(parentID) -- cgit v1.2.3-2-g168b From dcb9dbd93bc45cfce2ca8ca9eebf822a128caa97 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 2 Jan 2023 18:45:57 -0700 Subject: rebuildnodes/btrees: Cache failures to add a tree --- .../btrfsinspect/rebuildnodes/btrees/forrest.go | 15 ++++++++++++--- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go | 9 +++++++++ 2 files changed, 21 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 6bfa297..6f0ac96 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -105,9 +105,16 @@ func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *Reb } func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) { - if _, ok := ts.trees.Load(treeID); ok { - return true + if tree, ok := ts.trees.Load(treeID); ok { + return tree != nil } + defer func() { + if !ok { + // Store a negative cache of this. tree.AddRoot() for the ROOT or UUID + // trees will invalidate the negative cache. + ts.trees.Store(treeID, nil) + } + }() if slices.Contains(treeID, stack) { return false } @@ -173,7 +180,9 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s func (ts *RebuiltForrest) ListRoots() map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) ts.trees.Range(func(treeID btrfsprim.ObjID, tree *RebuiltTree) bool { - ret[treeID] = tree.Roots + if tree != nil { + ret[treeID] = tree.Roots + } return true }) return ret diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 678d25f..c9747ff 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -171,6 +171,15 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA stats.Leafs.N = len(leafToRoots) progressWriter.Set(stats) progressWriter.Done() + + if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { + tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { + if otherTree == nil { + tree.forrest.trees.Delete(otherTreeID) + } + return true + }) + } } // .Items() and .PotentialItems() ////////////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3-2-g168b From 39dfaa5af4b628eee55b4aa583abf72ef5833f32 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 2 Jan 2023 18:52:27 -0700 Subject: rebuildnodes/btrees: Enhance logging around failure to add a tree --- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 6f0ac96..3ed27b6 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -115,12 +115,13 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s ts.trees.Store(treeID, nil) } }() - if slices.Contains(treeID, stack) { - return false - } stack = append(stack, treeID) ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack) dlog.Info(ctx, "adding tree...") + if slices.Contains(treeID, stack[:len(stack)-1]) { + dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack) + return false + } tree := &RebuiltTree{ ID: treeID, @@ -140,10 +141,12 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s root = ts.sb.BlockGroupRoot default: if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) { + dlog.Error(ctx, "failed to add tree: add ROOT_TREE") return false } rootOff, rootItem, ok := ts.cbLookupRoot(ctx, treeID) if !ok { + dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM") return false } root = rootItem.ByteNr @@ -155,9 +158,11 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s } parentID, ok := ts.cbLookupUUID(ctx, rootItem.ParentUUID) if !ok { + dlog.Error(ctx, "failed to add tree: lookup UUID") return false } if !ts.addTree(ctx, parentID, stack) { + dlog.Error(ctx, "failed to add tree: add parent tree") return false } tree.Parent, _ = ts.trees.Load(parentID) -- 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 ++- lib/textui/log.go | 3 ++- lib/textui/log_test.go | 2 +- 3 files changed, 5 insertions(+), 3 deletions(-) (limited to 'lib') 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) } diff --git a/lib/textui/log.go b/lib/textui/log.go index 8327b67..110e1aa 100644 --- a/lib/textui/log.go +++ b/lib/textui/log.go @@ -180,7 +180,7 @@ func (l *logger) log(lvl dlog.LogLevel, writeMsg func(io.Writer)) { // time //////////////////////////////////////////////////////////////// now := time.Now() - const timeFmt = "2006-01-02 15:04:05.0000" + const timeFmt = "15:04:05.0000" logBuf.WriteString(timeFmt) now.AppendFormat(logBuf.Bytes()[:0], timeFmt) @@ -372,6 +372,7 @@ func writeField(w io.Writer, key string, val any) { if strings.HasPrefix(valStr, "/main/") { valStr = strings.TrimPrefix(valStr, "/main") } + valStr = strings.TrimPrefix(valStr, "/") } case strings.HasSuffix(name, ".pass"): fmt.Fprintf(w, "/pass-%s", valStr) diff --git a/lib/textui/log_test.go b/lib/textui/log_test.go index 514d96e..bcd9c39 100644 --- a/lib/textui/log_test.go +++ b/lib/textui/log_test.go @@ -16,7 +16,7 @@ import ( ) func logLineRegexp(inner string) string { - return `[0-9]{4}-[0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}:[0-9]{2}\.[0-9]{4} ` + inner + ` \(from lib/textui/log_test\.go:[0-9]+\)\n` + return `[0-9]{2}:[0-9]{2}:[0-9]{2}\.[0-9]{4} ` + inner + ` \(from lib/textui/log_test\.go:[0-9]+\)\n` } func TestLogFormat(t *testing.T) { -- 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/keyio/keyio.go | 21 ++++++++++-- .../btrfsinspect/rebuildnodes/rebuild.go | 37 +++++++++++----------- 2 files changed, 38 insertions(+), 20 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go index eb03004..64a9828 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go @@ -34,13 +34,19 @@ type SizeAndErr struct { Err error } +type FlagsAndErr struct { + NoDataSum bool + Err error +} + type Handle struct { rawFile diskio.File[btrfsvol.LogicalAddr] sb btrfstree.Superblock graph graph.Graph - Names map[ItemPtr][]byte - Sizes map[ItemPtr]SizeAndErr + Flags map[ItemPtr]FlagsAndErr // INODE_ITEM + Names map[ItemPtr][]byte // DIR_INDEX + Sizes map[ItemPtr]SizeAndErr // EXTENT_CSUM and EXTENT_DATA cache *containers.LRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]] } @@ -50,6 +56,7 @@ func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) rawFile: file, sb: sb, + Flags: make(map[ItemPtr]FlagsAndErr), Names: make(map[ItemPtr][]byte), Sizes: make(map[ItemPtr]SizeAndErr), @@ -64,6 +71,11 @@ func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree. Idx: i, } switch itemBody := item.Body.(type) { + case btrfsitem.Inode: + o.Flags[ptr] = FlagsAndErr{ + NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM), + Err: nil, + } case btrfsitem.DirEntry: if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY { o.Names[ptr] = append([]byte(nil), itemBody.Name...) @@ -81,6 +93,11 @@ func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree. } case btrfsitem.Error: switch item.Key.ItemType { + case btrfsprim.INODE_ITEM_KEY: + o.Flags[ptr] = FlagsAndErr{ + Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w", + ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err), + } case btrfsprim.EXTENT_CSUM_KEY, btrfsprim.EXTENT_DATA_KEY: o.Sizes[ptr] = SizeAndErr{ Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w", 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 6f7a95e0952887c02421431bdd2a879387deebe0 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 19:15:34 -0700 Subject: rebuildnodes/btrees: Touch up a comment --- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index c9747ff..7c64bf0 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -290,9 +290,9 @@ func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bo // Retain the old higher-gen one. return false default: - // This is a panic because I'm not really sure what the best way to - // handle this is, and so if this happens I want the program to crash - // and force me to figure out how to handle it. + // TODO: This is a panic because I'm not really sure what the + // best way to handle this is, and so if this happens I want the + // program to crash and force me to figure out how to handle it. panic(fmt.Errorf("dup nodes in tree=%v: old=%v=%v ; new=%v=%v", tree.ID, oldNode, tree.forrest.graph.Nodes[oldNode], -- cgit v1.2.3-2-g168b From a794062b5391b83e9f932c06f3953964e8e70b68 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 19:22:20 -0700 Subject: rebuildnodes/btrees: Move code up/down in the file, add comments --- .../btrfsinspect/rebuildnodes/btrees/tree.go | 126 +++++++++++---------- 1 file changed, 66 insertions(+), 60 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 7c64bf0..ae4065d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -35,9 +35,15 @@ type RebuiltTree struct { mu sync.Mutex Roots containers.Set[btrfsvol.LogicalAddr] Leafs containers.Set[btrfsvol.LogicalAddr] + // There are 3 more mutable "members" that are protected by + // `mu`; but they live in a shared LRUcache: + // + // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) + // 2. tree.PotentialItems() = tree.forrest.allItems.Load(tree.ID) + // 3. tree.Items() = tree.forrest.incItems.Load(tree.ID) } -// .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////////////////// +// LRU member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////////// // leafToRoots returns all leafs (lvl=0) in the filesystem that pass // .isOwnerOK, whether or not they're in the tree. @@ -124,65 +130,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati } } -// .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// - -type rootStats struct { - Leafs textui.Portion[int] - AddedLeafs int - AddedItems int -} - -func (s rootStats) String() string { - return textui.Sprintf("%v (added %v leafs, added %v items)", - s.Leafs, s.AddedLeafs, s.AddedItems) -} - -// AddRoot adds an additional root node to the tree. It is useful to -// call .AddRoot() to re-attach part of the tree that has been broken -// off. -func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { - tree.mu.Lock() - defer tree.mu.Unlock() - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) - tree.Roots.Insert(rootNode) - - var stats rootStats - leafToRoots := tree.leafToRoots(ctx) - stats.Leafs.D = len(leafToRoots) - progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - for i, leaf := range maps.SortedKeys(leafToRoots) { - stats.Leafs.N = i - progressWriter.Set(stats) - - if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { - continue - } - - tree.Leafs.Insert(leaf) - stats.AddedLeafs++ - progressWriter.Set(stats) - - for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items { - tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) - stats.AddedItems++ - progressWriter.Set(stats) - } - } - stats.Leafs.N = len(leafToRoots) - progressWriter.Set(stats) - progressWriter.Done() - - if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { - tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { - if otherTree == nil { - tree.forrest.trees.Delete(otherTreeID) - } - return true - }) - } -} - -// .Items() and .PotentialItems() ////////////////////////////////////////////////////////////////////////////////////// +// LRU members 2 and 3: .Items() and .PotentialItems() ///////////////////////////////////////////////////////////////// // Items returns a map of the items contained in this tree. // @@ -301,6 +249,64 @@ func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bo } } +// .AddRoot() ////////////////////////////////////////////////////////////////////////////////////////////////////////// + +type rootStats struct { + Leafs textui.Portion[int] + AddedLeafs int + AddedItems int +} + +func (s rootStats) String() string { + return textui.Sprintf("%v (added %v leafs, added %v items)", + s.Leafs, s.AddedLeafs, s.AddedItems) +} + +// AddRoot adds an additional root node to the tree. It is useful to +// call .AddRoot() to re-attach part of the tree that has been broken +// off. +func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) { + tree.mu.Lock() + defer tree.mu.Unlock() + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) + tree.Roots.Insert(rootNode) + + var stats rootStats + leafToRoots := tree.leafToRoots(ctx) + stats.Leafs.D = len(leafToRoots) + progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + for i, leaf := range maps.SortedKeys(leafToRoots) { + stats.Leafs.N = i + progressWriter.Set(stats) + + if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { + continue + } + + tree.Leafs.Insert(leaf) + stats.AddedLeafs++ + progressWriter.Set(stats) + + for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + tree.forrest.cbAddedItem(ctx, tree.ID, itemKey) + stats.AddedItems++ + progressWriter.Set(stats) + } + } + stats.Leafs.N = len(leafToRoots) + progressWriter.Set(stats) + progressWriter.Done() + + if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { + tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { + if otherTree == nil { + tree.forrest.trees.Delete(otherTreeID) + } + return true + }) + } +} + // main public API ///////////////////////////////////////////////////////////////////////////////////////////////////// // COWDistance returns how many COW-snapshots down the 'tree' is from -- cgit v1.2.3-2-g168b From 94e662ff74a23bf579eb2bcf6f2b152b13436a01 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 3 Jan 2023 20:56:20 -0700 Subject: rebuildnodes/btrees: Rework to avoid the .Leafs member Save some memory. --- .../btrfsinspect/rebuildnodes/btrees/forrest.go | 1 - .../btrfsinspect/rebuildnodes/btrees/tree.go | 34 ++++++++++++++++------ 2 files changed, 25 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 3ed27b6..26fa64e 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -126,7 +126,6 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s tree := &RebuiltTree{ ID: treeID, Roots: make(containers.Set[btrfsvol.LogicalAddr]), - Leafs: make(containers.Set[btrfsvol.LogicalAddr]), forrest: ts, } var root btrfsvol.LogicalAddr diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index ae4065d..a25825a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -34,9 +34,10 @@ type RebuiltTree struct { // mutable mu sync.Mutex Roots containers.Set[btrfsvol.LogicalAddr] - Leafs containers.Set[btrfsvol.LogicalAddr] // There are 3 more mutable "members" that are protected by - // `mu`; but they live in a shared LRUcache: + // `mu`; but they live in a shared LRUcache. They are all + // derived from tree.Roots, which is why it's OK if they get + // evicted. // // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) // 2. tree.PotentialItems() = tree.forrest.allItems.Load(tree.ID) @@ -138,7 +139,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati // RebuiltTree's internal map! func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-inc-items", fmt.Sprintf("tree=%v", tree.ID)) - return tree.items(ctx, tree.forrest.incItems, maps.SortedKeys(tree.Leafs)) + return tree.items(ctx, tree.forrest.incItems, tree.Roots.HasAny) } // PotentialItems returns a map of items that could be added to this @@ -148,7 +149,10 @@ func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsp // RebuiltTree's internal map! func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-all-items", fmt.Sprintf("tree=%v", tree.ID)) - return tree.items(ctx, tree.forrest.allItems, maps.SortedKeys(tree.leafToRoots(ctx))) + return tree.items(ctx, tree.forrest.allItems, + func(_ containers.Set[btrfsvol.LogicalAddr]) bool { + return true + }) } type itemIndex struct { @@ -168,9 +172,20 @@ func (s itemStats) String() string { s.Leafs, s.NumItems, s.NumDups) } -func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex], leafs []btrfsvol.LogicalAddr) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { +func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex], + leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool, +) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { tree.mu.Lock() defer tree.mu.Unlock() + + var leafs []btrfsvol.LogicalAddr + for leaf, roots := range tree.leafToRoots(ctx) { + if leafFn(roots) { + leafs = append(leafs, leaf) + } + } + slices.Sort(leafs) + index := cache.GetOrElse(tree.ID, func() *itemIndex { return &itemIndex{ Leafs: make(containers.Set[btrfsvol.LogicalAddr]), @@ -269,21 +284,20 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA tree.mu.Lock() defer tree.mu.Unlock() ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode)) - tree.Roots.Insert(rootNode) - var stats rootStats leafToRoots := tree.leafToRoots(ctx) + + var stats rootStats stats.Leafs.D = len(leafToRoots) progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) for i, leaf := range maps.SortedKeys(leafToRoots) { stats.Leafs.N = i progressWriter.Set(stats) - if tree.Leafs.Has(leaf) || !leafToRoots[leaf].Has(rootNode) { + if tree.Roots.HasAny(leafToRoots[leaf]) || !leafToRoots[leaf].Has(rootNode) { continue } - tree.Leafs.Insert(leaf) stats.AddedLeafs++ progressWriter.Set(stats) @@ -297,6 +311,8 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA progressWriter.Set(stats) progressWriter.Done() + tree.Roots.Insert(rootNode) + if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { if otherTree == nil { -- 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/btrees/forrest.go | 4 ++-- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go | 10 +++++----- lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go | 8 ++++---- 3 files changed, 11 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go index 26fa64e..ff6b1c5 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go @@ -64,8 +64,8 @@ type RebuiltForrest struct { // mutable trees containers.SyncMap[btrfsprim.ObjID, *RebuiltTree] leafs *containers.LRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]] - allItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] + excItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex] } // NewRebuiltForrest returns a new RebuiltForrest instance. All of @@ -86,8 +86,8 @@ func NewRebuiltForrest( cbLookupUUID: cbLookupUUID, leafs: containers.NewLRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](textui.Tunable(8)), - allItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), + excItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)), } } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index a25825a..65f76b2 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -40,8 +40,8 @@ type RebuiltTree struct { // evicted. // // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) - // 2. tree.PotentialItems() = tree.forrest.allItems.Load(tree.ID) - // 3. tree.Items() = tree.forrest.incItems.Load(tree.ID) + // 2. tree.Items() = tree.forrest.incItems.Load(tree.ID) + // 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID) } // LRU member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////////// @@ -149,9 +149,9 @@ func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsp // RebuiltTree's internal map! func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-all-items", fmt.Sprintf("tree=%v", tree.ID)) - return tree.items(ctx, tree.forrest.allItems, - func(_ containers.Set[btrfsvol.LogicalAddr]) bool { - return true + return tree.items(ctx, tree.forrest.excItems, + func(roots containers.Set[btrfsvol.LogicalAddr]) bool { + return !tree.Roots.HasAny(roots) }) } 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 98de12d606765ef21a1aae10abfb4c33a1a9f23b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 5 Jan 2023 00:30:41 -0700 Subject: rebuildnodes/btrees: Rework RebuiltTree.items() to be faster in the happy-path And also have the cache consume less memory. --- .../btrfsinspect/rebuildnodes/btrees/tree.go | 88 ++++++++++------------ 1 file changed, 38 insertions(+), 50 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index 65f76b2..cd05911 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -155,11 +155,7 @@ func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedM }) } -type itemIndex struct { - NumDups int - Leafs containers.Set[btrfsvol.LogicalAddr] - Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] -} +type itemIndex = containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] type itemStats struct { Leafs textui.Portion[int] @@ -178,58 +174,48 @@ func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[b tree.mu.Lock() defer tree.mu.Unlock() - var leafs []btrfsvol.LogicalAddr - for leaf, roots := range tree.leafToRoots(ctx) { - if leafFn(roots) { - leafs = append(leafs, leaf) - } - } - slices.Sort(leafs) - - index := cache.GetOrElse(tree.ID, func() *itemIndex { - return &itemIndex{ - Leafs: make(containers.Set[btrfsvol.LogicalAddr]), + return cache.GetOrElse(tree.ID, func() *itemIndex { + var leafs []btrfsvol.LogicalAddr + for leaf, roots := range tree.leafToRoots(ctx) { + if leafFn(roots) { + leafs = append(leafs, leaf) + } } - }) + slices.Sort(leafs) - var stats itemStats - stats.Leafs.D = len(leafs) - progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - progress := func(doneLeafs int) { - stats.Leafs.N = doneLeafs - stats.NumItems = index.Items.Len() - stats.NumDups = index.NumDups - progressWriter.Set(stats) - } + var stats itemStats + stats.Leafs.D = len(leafs) + progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - for i, leaf := range leafs { - if index.Leafs.Has(leaf) { - continue - } - progress(i) - index.Leafs.Insert(leaf) - for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { - newPtr := keyio.ItemPtr{ - Node: leaf, - Idx: j, - } - if oldPtr, exists := index.Items.Load(itemKey); !exists { - index.Items.Store(itemKey, newPtr) - } else { - index.NumDups++ - if tree.shouldReplace(oldPtr.Node, newPtr.Node) { - index.Items.Store(itemKey, newPtr) + index := new(containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]) + for i, leaf := range leafs { + stats.Leafs.N = i + progressWriter.Set(stats) + for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + newPtr := keyio.ItemPtr{ + Node: leaf, + Idx: j, + } + if oldPtr, exists := index.Load(itemKey); !exists { + index.Store(itemKey, newPtr) + stats.NumItems++ + } else { + if tree.shouldReplace(oldPtr.Node, newPtr.Node) { + index.Store(itemKey, newPtr) + } + stats.NumDups++ } + progressWriter.Set(stats) } - progress(i) } - } - if stats.Leafs.N > 0 { - progress(len(leafs)) - progressWriter.Done() - } + if stats.Leafs.N > 0 { + stats.Leafs.N = len(leafs) + progressWriter.Set(stats) + progressWriter.Done() + } - return &index.Items + return index + }) } func (tree *RebuiltTree) shouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool { @@ -312,6 +298,8 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA progressWriter.Done() tree.Roots.Insert(rootNode) + tree.forrest.incItems.Remove(tree.ID) // force re-gen + tree.forrest.excItems.Remove(tree.ID) // force re-gen if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 { tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool { -- 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') 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') 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') 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') 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 From 3b385f26973e45b4c2e2f3ebf9d52ab0131cff5e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 5 Jan 2023 00:47:18 -0700 Subject: rebuildnodes/btrees: Switch from a sync.Mutex to a sync.RWMutex --- lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go index cd05911..c381274 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go @@ -32,7 +32,7 @@ type RebuiltTree struct { forrest *RebuiltForrest // mutable - mu sync.Mutex + mu sync.RWMutex Roots containers.Set[btrfsvol.LogicalAddr] // There are 3 more mutable "members" that are protected by // `mu`; but they live in a shared LRUcache. They are all @@ -171,8 +171,8 @@ func (s itemStats) String() string { func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex], leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool, ) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { - tree.mu.Lock() - defer tree.mu.Unlock() + tree.mu.RLock() + defer tree.mu.RUnlock() return cache.GetOrElse(tree.ID, func() *itemIndex { var leafs []btrfsvol.LogicalAddr @@ -344,8 +344,8 @@ func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalA panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf", tree.ID, leaf)) } - tree.mu.Lock() - defer tree.mu.Unlock() + tree.mu.RLock() + defer tree.mu.RUnlock() ret := make(containers.Set[btrfsvol.LogicalAddr]) for root := range tree.leafToRoots(ctx)[leaf] { if tree.Roots.Has(root) { -- cgit v1.2.3-2-g168b