From 7c0e009092f593ca0990a50de8db3f81c112e58e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 18 Dec 2022 00:34:06 -0700 Subject: rebuildnodes: Reduce scope of the orphans set --- lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 51313a9..0ecf852 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -83,13 +83,12 @@ func (s readStats) String() string { } func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( - orphans containers.Set[btrfsvol.LogicalAddr], leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], err error, ) { dlog.Info(ctx, "... counting orphans") - orphans = make(containers.Set[btrfsvol.LogicalAddr]) + orphans := make(containers.Set[btrfsvol.LogicalAddr]) for node := range graph.Nodes { if len(graph.EdgesTo[node]) == 0 { orphans.Insert(node) @@ -145,7 +144,7 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb Level: containers.Optional[uint8]{OK: true, Val: 0}, }) if err != nil { - return nil, nil, nil, err + return nil, nil, err } for _, item := range nodeRef.Data.BodyLeaf { @@ -162,5 +161,5 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb } readProgressWriter.Done() - return orphans, leaf2orphans, key2leaf, nil + return leaf2orphans, key2leaf, nil } -- cgit v1.2.3-2-g168b From 01a9a607b9412f482e0a9784ab9013a7213077a0 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 18 Dec 2022 00:36:05 -0700 Subject: rebuildnodes: Optimize indexing of orphans --- .../btrfsinspect/rebuildnodes/orphans.go | 83 +++++++--------------- 1 file changed, 24 insertions(+), 59 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 0ecf852..5d3f031 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -33,18 +33,6 @@ func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrf return ret } -func walk(graph graph.Graph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) { - if _, ok := graph.Nodes[root]; !ok { - return - } - if !fn(root) { - return - } - for _, kp := range graph.EdgesFrom[root] { - walk(graph, kp.ToNode, fn) - } -} - type keyAndTree struct { btrfsprim.Key TreeID btrfsprim.ObjID @@ -58,17 +46,15 @@ func (a keyAndTree) Cmp(b keyAndTree) int { } type crawlStats struct { - DoneOrphans int - TotalOrphans int - - VisitedNodes int - FoundLeafs int + DoneNodes int + TotalNodes int + FoundLeafs int } func (s crawlStats) String() string { - return fmt.Sprintf("... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes", - int(100*float64(s.DoneOrphans)/float64(s.TotalOrphans)), - s.DoneOrphans, s.TotalOrphans, s.VisitedNodes, s.FoundLeafs) + return fmt.Sprintf("... indexing orphaned leafs %v%% (%v/%v); found %d leaf nodes", + int(100*float64(s.DoneNodes)/float64(s.TotalNodes)), + s.DoneNodes, s.TotalNodes, s.FoundLeafs) } type readStats struct { @@ -87,58 +73,38 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], err error, ) { - dlog.Info(ctx, "... counting orphans") - orphans := make(containers.Set[btrfsvol.LogicalAddr]) - for node := range graph.Nodes { - if len(graph.EdgesTo[node]) == 0 { - orphans.Insert(node) - } - } - leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - visited := make(containers.Set[btrfsvol.LogicalAddr]) - - done := 0 crawlProgressWriter := textui.NewProgress[crawlStats](ctx, dlog.LogLevelInfo, 1*time.Second) - progress := func() { + progress := func(done int) { crawlProgressWriter.Set(crawlStats{ - DoneOrphans: done, - TotalOrphans: len(orphans), - VisitedNodes: len(visited), - FoundLeafs: len(leaf2orphans), + DoneNodes: done, + TotalNodes: len(graph.Nodes), + FoundLeafs: len(leaf2orphans), }) } - progress() - for _, orphan := range maps.SortedKeys(orphans) { - walk(graph, orphan, func(node btrfsvol.LogicalAddr) bool { - if visited.Has(node) { - return false - } - visited.Insert(node) - if graph.Nodes[node].Level == 0 { - if roots := listRoots(graph, node); !roots.Has(0) { - leaf2orphans[node] = roots - } - } - progress() - return true - }) - done++ - progress() + leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + for i, node := range maps.SortedKeys(graph.Nodes) { + progress(i) + if graph.Nodes[node].Level != 0 { + continue + } + if roots := listRoots(graph, node); !roots.Has(0) { + leaf2orphans[node] = roots + } } + progress(len(graph.Nodes)) crawlProgressWriter.Done() key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - done = 0 readProgressWriter := textui.NewProgress[readStats](ctx, dlog.LogLevelInfo, 1*time.Second) - progress = func() { + progress = func(done int) { readProgressWriter.Set(readStats{ DoneLeafNodes: done, TotalLeafNodes: len(leaf2orphans), }) } - progress() - for _, laddr := range maps.SortedKeys(leaf2orphans) { + for i, laddr := range maps.SortedKeys(leaf2orphans) { + progress(i) nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, Level: containers.Optional[uint8]{OK: true, Val: 0}, @@ -156,9 +122,8 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb key2leaf.Store(k, laddr) } } - done++ - progress() } + progress(len(leaf2orphans)) readProgressWriter.Done() return leaf2orphans, key2leaf, nil -- cgit v1.2.3-2-g168b From aebdf099d1b02394debd71a40b18050370ba7416 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 18 Dec 2022 00:58:08 -0700 Subject: rebuildnodes: Optimize memory access when indexing orphans --- lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 5d3f031..89e9ad4 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -22,15 +22,19 @@ import ( ) func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { + ret := make(containers.Set[btrfsvol.LogicalAddr]) + _listRoots(ret, graph, leaf) + return ret +} + +func _listRoots(ret containers.Set[btrfsvol.LogicalAddr], graph graph.Graph, leaf btrfsvol.LogicalAddr) { kps := graph.EdgesTo[leaf] if len(kps) == 0 { - return containers.NewSet(leaf) + ret.Insert(leaf) } - ret := make(containers.Set[btrfsvol.LogicalAddr]) for _, kp := range kps { - ret.InsertFrom(listRoots(graph, kp.FromNode)) + _listRoots(ret, graph, kp.FromNode) } - return ret } type keyAndTree struct { -- cgit v1.2.3-2-g168b From 30be1eacbe4ff253c82c6e6163234dc20b4de550 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 21 Dec 2022 05:30:25 -0700 Subject: rebuildnodes: Refactor existing key-io code in to a sub-package --- .../btrfsinspect/rebuildnodes/orphans.go | 58 +--------------------- 1 file changed, 1 insertion(+), 57 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 89e9ad4..517070d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -11,7 +11,6 @@ import ( "github.com/datawire/dlib/dlog" - "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" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" @@ -37,18 +36,6 @@ func _listRoots(ret containers.Set[btrfsvol.LogicalAddr], graph graph.Graph, lea } } -type keyAndTree struct { - btrfsprim.Key - TreeID btrfsprim.ObjID -} - -func (a keyAndTree) Cmp(b keyAndTree) int { - if d := a.Key.Cmp(b.Key); d != 0 { - return d - } - return containers.NativeCmp(a.TreeID, b.TreeID) -} - type crawlStats struct { DoneNodes int TotalNodes int @@ -61,20 +48,8 @@ func (s crawlStats) String() string { s.DoneNodes, s.TotalNodes, s.FoundLeafs) } -type readStats struct { - DoneLeafNodes int - TotalLeafNodes int -} - -func (s readStats) String() string { - return fmt.Sprintf("... reading leafs %v%% (%v/%v)", - int(100*float64(s.DoneLeafNodes)/float64(s.TotalLeafNodes)), - s.DoneLeafNodes, s.TotalLeafNodes) -} - func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], - key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], err error, ) { @@ -99,36 +74,5 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb progress(len(graph.Nodes)) crawlProgressWriter.Done() - key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - readProgressWriter := textui.NewProgress[readStats](ctx, dlog.LogLevelInfo, 1*time.Second) - progress = func(done int) { - readProgressWriter.Set(readStats{ - DoneLeafNodes: done, - TotalLeafNodes: len(leaf2orphans), - }) - } - for i, laddr := range maps.SortedKeys(leaf2orphans) { - progress(i) - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, - Level: containers.Optional[uint8]{OK: true, Val: 0}, - }) - if err != nil { - return nil, nil, err - } - - for _, item := range nodeRef.Data.BodyLeaf { - k := keyAndTree{ - Key: item.Key, - TreeID: nodeRef.Data.Head.Owner, - } - if cur, ok := key2leaf.Load(k); !ok || graph.Nodes[cur].Generation < nodeRef.Data.Head.Generation { - key2leaf.Store(k, laddr) - } - } - } - progress(len(leaf2orphans)) - readProgressWriter.Done() - - return leaf2orphans, key2leaf, nil + return leaf2orphans, nil } -- cgit v1.2.3-2-g168b From 7620e1948a4d1e17458d8cfc9ed306bb774a3274 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 21 Dec 2022 04:30:56 -0700 Subject: rebuildnodes: Migrate to the new rebuilt-btrees system --- .../btrfsinspect/rebuildnodes/orphans.go | 78 ---------------------- 1 file changed, 78 deletions(-) delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go deleted file mode 100644 index 517070d..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ /dev/null @@ -1,78 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "fmt" - "time" - - "github.com/datawire/dlib/dlog" - - "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/rebuildnodes/graph" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" - "git.lukeshu.com/btrfs-progs-ng/lib/textui" -) - -func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { - ret := make(containers.Set[btrfsvol.LogicalAddr]) - _listRoots(ret, graph, leaf) - return ret -} - -func _listRoots(ret containers.Set[btrfsvol.LogicalAddr], graph graph.Graph, leaf btrfsvol.LogicalAddr) { - kps := graph.EdgesTo[leaf] - if len(kps) == 0 { - ret.Insert(leaf) - } - for _, kp := range kps { - _listRoots(ret, graph, kp.FromNode) - } -} - -type crawlStats struct { - DoneNodes int - TotalNodes int - FoundLeafs int -} - -func (s crawlStats) String() string { - return fmt.Sprintf("... indexing orphaned leafs %v%% (%v/%v); found %d leaf nodes", - int(100*float64(s.DoneNodes)/float64(s.TotalNodes)), - s.DoneNodes, s.TotalNodes, s.FoundLeafs) -} - -func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( - leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], - err error, -) { - - crawlProgressWriter := textui.NewProgress[crawlStats](ctx, dlog.LogLevelInfo, 1*time.Second) - progress := func(done int) { - crawlProgressWriter.Set(crawlStats{ - DoneNodes: done, - TotalNodes: len(graph.Nodes), - FoundLeafs: len(leaf2orphans), - }) - } - leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) - for i, node := range maps.SortedKeys(graph.Nodes) { - progress(i) - if graph.Nodes[node].Level != 0 { - continue - } - if roots := listRoots(graph, node); !roots.Has(0) { - leaf2orphans[node] = roots - } - } - progress(len(graph.Nodes)) - crawlProgressWriter.Done() - - return leaf2orphans, nil -} -- cgit v1.2.3-2-g168b