From 6c03becc595c9938644e767c852a2627d4a265d3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 17 Oct 2022 00:31:38 -0600 Subject: rebuildnodes: wip: New rebuild-nodes implementation --- .../btrfsinspect/rebuildnodes/orphans.go | 102 +++++++++++++++++++++ 1 file changed, 102 insertions(+) create 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 new file mode 100644 index 0000000..3d375f0 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -0,0 +1,102 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "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/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" +) + +func listRoots(graph nodeGraph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { + kps := graph.EdgesTo[leaf] + if len(kps) == 0 { + return containers.NewSet(leaf) + } + ret := make(containers.Set[btrfsvol.LogicalAddr]) + for _, kp := range kps { + ret.InsertFrom(listRoots(graph, kp.FromNode)) + } + return ret +} + +func walk(graph nodeGraph, 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 +} + +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) +} + +func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph nodeGraph) ( + orphans containers.Set[btrfsvol.LogicalAddr], + leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], + key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], + err error, +) { + 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]) + for orphan := range 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 + } + } + return true + }) + } + + key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) + for laddr := range leaf2orphans { + 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, 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) + } + } + } + return orphans, leaf2orphans, key2leaf, nil +} -- cgit v1.2.3-2-g168b From 77046dcf26687fd74df0f7966d7d469f6b6de717 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 27 Nov 2022 16:41:44 -0700 Subject: rebuildnodes: Refactor the node-graph stuff in to a separate sub-package --- lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go | 7 ++++--- 1 file changed, 4 insertions(+), 3 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 3d375f0..70bd128 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -8,11 +8,12 @@ import ( "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" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) -func listRoots(graph nodeGraph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { +func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { kps := graph.EdgesTo[leaf] if len(kps) == 0 { return containers.NewSet(leaf) @@ -24,7 +25,7 @@ func listRoots(graph nodeGraph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsv return ret } -func walk(graph nodeGraph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) { +func walk(graph graph.Graph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) { if _, ok := graph.Nodes[root]; !ok { return } @@ -48,7 +49,7 @@ func (a keyAndTree) Cmp(b keyAndTree) int { return containers.NativeCmp(a.TreeID, b.TreeID) } -func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph nodeGraph) ( +func indexOrphans(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], -- cgit v1.2.3-2-g168b From 0ba5538b7faba51474c7fd4c5512f795e05a787c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 11 Dec 2022 22:29:05 -0700 Subject: rebuildnodes: Improve logging --- .../btrfsinspect/rebuildnodes/orphans.go | 43 ++++++++++++++++++++-- 1 file changed, 40 insertions(+), 3 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 70bd128..55cf95b 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -5,12 +5,17 @@ package rebuildnodes import ( + "context" + + "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" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { @@ -49,12 +54,13 @@ func (a keyAndTree) Cmp(b keyAndTree) int { return containers.NativeCmp(a.TreeID, b.TreeID) } -func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( +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]) for node := range graph.Nodes { if len(graph.EdgesTo[node]) == 0 { @@ -64,7 +70,22 @@ func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) visited := make(containers.Set[btrfsvol.LogicalAddr]) - for orphan := range orphans { + + lastPct, lastVisited, lastLeafs := -1, 0, 0 + total := len(orphans) + done := 0 + progress := func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || (len(visited) != lastVisited && len(visited)%500 == 0) || len(leaf2orphans) != lastLeafs || done == total { + dlog.Infof(ctx, "... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes", + pct, done, total, len(visited), len(leaf2orphans)) + lastPct = pct + lastVisited = len(visited) + lastLeafs = len(leaf2orphans) + } + } + progress() + for _, orphan := range maps.SortedKeys(orphans) { walk(graph, orphan, func(node btrfsvol.LogicalAddr) bool { if visited.Has(node) { return false @@ -75,12 +96,26 @@ func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, leaf2orphans[node] = roots } } + progress() return true }) + done++ + progress() } key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - for laddr := range leaf2orphans { + total = len(leaf2orphans) + done = 0 + progress = func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || done == total { + dlog.Infof(ctx, "... reading leafs %v%% (%v/%v)", + pct, done, total) + lastPct = pct + } + } + progress() + for _, laddr := range maps.SortedKeys(leaf2orphans) { 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}, @@ -98,6 +133,8 @@ func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, key2leaf.Store(k, laddr) } } + done++ + progress() } return orphans, leaf2orphans, key2leaf, nil } -- cgit v1.2.3-2-g168b From 94a86a763157327ac969c98e19d7770db477a6a3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 14 Dec 2022 16:19:07 -0700 Subject: Migrate existing progress logs to textui.NewProgress --- .../btrfsinspect/rebuildnodes/orphans.go | 60 ++++++++++++++++------ 1 file changed, 43 insertions(+), 17 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 55cf95b..51313a9 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -6,6 +6,8 @@ package rebuildnodes import ( "context" + "fmt" + "time" "github.com/datawire/dlib/dlog" @@ -16,6 +18,7 @@ import ( "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] { @@ -54,6 +57,31 @@ func (a keyAndTree) Cmp(b keyAndTree) int { return containers.NativeCmp(a.TreeID, b.TreeID) } +type crawlStats struct { + DoneOrphans int + TotalOrphans int + + VisitedNodes 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) +} + +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) ( orphans containers.Set[btrfsvol.LogicalAddr], leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], @@ -71,18 +99,15 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) visited := make(containers.Set[btrfsvol.LogicalAddr]) - lastPct, lastVisited, lastLeafs := -1, 0, 0 - total := len(orphans) done := 0 + crawlProgressWriter := textui.NewProgress[crawlStats](ctx, dlog.LogLevelInfo, 1*time.Second) progress := func() { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || (len(visited) != lastVisited && len(visited)%500 == 0) || len(leaf2orphans) != lastLeafs || done == total { - dlog.Infof(ctx, "... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes", - pct, done, total, len(visited), len(leaf2orphans)) - lastPct = pct - lastVisited = len(visited) - lastLeafs = len(leaf2orphans) - } + crawlProgressWriter.Set(crawlStats{ + DoneOrphans: done, + TotalOrphans: len(orphans), + VisitedNodes: len(visited), + FoundLeafs: len(leaf2orphans), + }) } progress() for _, orphan := range maps.SortedKeys(orphans) { @@ -102,17 +127,16 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb done++ progress() } + crawlProgressWriter.Done() key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - total = len(leaf2orphans) done = 0 + readProgressWriter := textui.NewProgress[readStats](ctx, dlog.LogLevelInfo, 1*time.Second) progress = func() { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... reading leafs %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } + readProgressWriter.Set(readStats{ + DoneLeafNodes: done, + TotalLeafNodes: len(leaf2orphans), + }) } progress() for _, laddr := range maps.SortedKeys(leaf2orphans) { @@ -136,5 +160,7 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb done++ progress() } + readProgressWriter.Done() + return orphans, leaf2orphans, key2leaf, nil } -- cgit v1.2.3-2-g168b