From 87b11decd105d620b3ad6f56c45b9bf1cf86a1b3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 23 Oct 2022 21:18:15 -0600 Subject: containers: Add a 'SortedMap' type --- lib/containers/sortedmap.go | 76 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 76 insertions(+) create mode 100644 lib/containers/sortedmap.go (limited to 'lib/containers') diff --git a/lib/containers/sortedmap.go b/lib/containers/sortedmap.go new file mode 100644 index 0000000..b759fa3 --- /dev/null +++ b/lib/containers/sortedmap.go @@ -0,0 +1,76 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package containers + +import ( + "errors" +) + +type orderedKV[K Ordered[K], V any] struct { + K K + V V +} + +type SortedMap[K Ordered[K], V any] struct { + inner RBTree[K, orderedKV[K, V]] +} + +func (m *SortedMap[K, V]) init() { + if m.inner.KeyFn == nil { + m.inner.KeyFn = m.keyFn + } +} + +func (m *SortedMap[K, V]) keyFn(kv orderedKV[K, V]) K { + return kv.K +} + +func (m *SortedMap[K, V]) Delete(key K) { + m.init() + m.inner.Delete(key) +} + +func (m *SortedMap[K, V]) Load(key K) (value V, ok bool) { + m.init() + node := m.inner.Lookup(key) + if node == nil { + var zero V + return zero, false + } + return node.Value.V, true +} + +var errStop = errors.New("stop") + +func (m *SortedMap[K, V]) Range(f func(key K, value V) bool) { + m.init() + _ = m.inner.Walk(func(node *RBNode[orderedKV[K, V]]) error { + if f(node.Value.K, node.Value.V) { + return nil + } else { + return errStop + } + }) +} + +func (m *SortedMap[K, V]) Subrange(rangeFn func(K, V) int, handleFn func(K, V) bool) { + m.init() + kvs := m.inner.SearchRange(func(kv orderedKV[K, V]) int { + return rangeFn(kv.K, kv.V) + }) + for _, kv := range kvs { + if !handleFn(kv.K, kv.V) { + break + } + } +} + +func (m *SortedMap[K, V]) Store(key K, value V) { + m.init() + m.inner.Insert(orderedKV[K, V]{ + K: key, + V: value, + }) +} -- cgit v1.2.3-54-g00ecf From 85169c799b4a0d4ba7d39347c07690dc0b49a1d1 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 7 Dec 2022 22:08:51 -0700 Subject: containers.Set: Don't use constraints.Ordered --- lib/btrfs/btrfsvol/chunk.go | 4 +- lib/btrfs/btrfsvol/lvm.go | 8 ++- .../btrfsinspect/rebuildmappings/blockgroups.go | 7 +-- lib/containers/ordered.go | 4 +- lib/containers/set.go | 57 +++++++++++++++++++--- 5 files changed, 62 insertions(+), 18 deletions(-) (limited to 'lib/containers') diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go index 8a2d439..5f1baa8 100644 --- a/lib/btrfs/btrfsvol/chunk.go +++ b/lib/btrfs/btrfsvol/chunk.go @@ -70,11 +70,11 @@ func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) { } } // figure out the physical stripes (.PAddrs) - paddrs := make(map[QualifiedPhysicalAddr]struct{}) + paddrs := make(containers.Set[QualifiedPhysicalAddr]) for _, chunk := range chunks { offsetWithinRet := chunk.LAddr.Sub(ret.LAddr) for _, stripe := range chunk.PAddrs { - paddrs[stripe.Add(-offsetWithinRet)] = struct{}{} + paddrs.Insert(stripe.Add(-offsetWithinRet)) } } ret.PAddrs = maps.Keys(paddrs) diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index e12e53e..c7551fc 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -256,9 +256,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { return ret } -// paddrs isn't a containers.Set because QualifiedPhysicalAddr is not -// an ordered type. -func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) { +func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs containers.Set[QualifiedPhysicalAddr], maxlen AddrDelta) { node := lv.logical2physical.Search(func(chunk chunkMapping) int { return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk) }) @@ -269,10 +267,10 @@ func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[ chunk := node.Value offsetWithinChunk := laddr.Sub(chunk.LAddr) - paddrs = make(map[QualifiedPhysicalAddr]struct{}) + paddrs = make(containers.Set[QualifiedPhysicalAddr]) maxlen = chunk.Size - offsetWithinChunk for _, stripe := range chunk.PAddrs { - paddrs[stripe.Add(offsetWithinChunk)] = struct{}{} + paddrs.Insert(stripe.Add(offsetWithinChunk)) } return paddrs, maxlen diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go index a638f7c..0e2d5a0 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go @@ -10,6 +10,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) @@ -21,14 +22,14 @@ type BlockGroup struct { func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) { // Dedup - bgsSet := make(map[BlockGroup]struct{}) // Can't use containers.Set because BlockGroup isn't ordered + bgsSet := make(containers.Set[BlockGroup]) for _, devResults := range scanResults { for _, bg := range devResults.FoundBlockGroups { - bgsSet[BlockGroup{ + bgsSet.Insert(BlockGroup{ LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID), Size: btrfsvol.AddrDelta(bg.Key.Offset), Flags: bg.BG.Flags, - }] = struct{}{} + }) } } diff --git a/lib/containers/ordered.go b/lib/containers/ordered.go index 038edf8..d918149 100644 --- a/lib/containers/ordered.go +++ b/lib/containers/ordered.go @@ -8,10 +8,12 @@ import ( "golang.org/x/exp/constraints" ) -type Ordered[T interface{ Cmp(T) int }] interface { +type _Ordered[T any] interface { Cmp(T) int } +type Ordered[T _Ordered[T]] _Ordered[T] + type NativeOrdered[T constraints.Ordered] struct { Val T } diff --git a/lib/containers/set.go b/lib/containers/set.go index 1c525ca..d3f8ca7 100644 --- a/lib/containers/set.go +++ b/lib/containers/set.go @@ -5,27 +5,70 @@ package containers import ( + "fmt" "io" + "sort" "git.lukeshu.com/go/lowmemjson" - "golang.org/x/exp/constraints" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) // Set[T] is an unordered set of T. -// -// Despite Set[T] being unordered, T is required to be an ordered type -// in order that a Set[T] have a deterministic JSON representation. -type Set[T constraints.Ordered] map[T]struct{} +type Set[T comparable] map[T]struct{} var ( _ lowmemjson.Encodable = Set[int]{} _ lowmemjson.Decodable = (*Set[int])(nil) ) +func cast[T any](x any) T { return x.(T) } + func (o Set[T]) EncodeJSON(w io.Writer) error { - return lowmemjson.Encode(w, maps.SortedKeys(o)) + var less func(a, b T) bool + var zero T + switch (any(zero)).(type) { + case _Ordered[T]: + less = func(a, b T) bool { return cast[_Ordered[T]](a).Cmp(b) < 0 } + // This is the constraints.Ordered list + case string: + less = func(a, b T) bool { return cast[string](a) < cast[string](b) } + case int: + less = func(a, b T) bool { return cast[int](a) < cast[int](b) } + case int8: + less = func(a, b T) bool { return cast[int8](a) < cast[int8](b) } + case int16: + less = func(a, b T) bool { return cast[int16](a) < cast[int16](b) } + case int32: + less = func(a, b T) bool { return cast[int32](a) < cast[int32](b) } + case int64: + less = func(a, b T) bool { return cast[int64](a) < cast[int64](b) } + case uint: + less = func(a, b T) bool { return cast[uint](a) < cast[uint](b) } + case uint8: + less = func(a, b T) bool { return cast[uint8](a) < cast[uint8](b) } + case uint16: + less = func(a, b T) bool { return cast[uint16](a) < cast[uint16](b) } + case uint32: + less = func(a, b T) bool { return cast[uint32](a) < cast[uint32](b) } + case uint64: + less = func(a, b T) bool { return cast[uint64](a) < cast[uint64](b) } + case uintptr: + less = func(a, b T) bool { return cast[uintptr](a) < cast[uintptr](b) } + case float32: + less = func(a, b T) bool { return cast[float32](a) < cast[float32](b) } + case float64: + less = func(a, b T) bool { return cast[float64](a) < cast[float64](b) } + default: + less = func(a, b T) bool { return fmt.Sprint(a) < fmt.Sprint(b) } + } + + keys := maps.Keys(o) + sort.Slice(keys, func(i, j int) bool { + return less(keys[i], keys[j]) + }) + + return lowmemjson.Encode(w, keys) } func (o *Set[T]) DecodeJSON(r io.RuneScanner) error { @@ -49,7 +92,7 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error { }) } -func NewSet[T constraints.Ordered](values ...T) Set[T] { +func NewSet[T comparable](values ...T) Set[T] { ret := make(Set[T], len(values)) for _, value := range values { ret.Insert(value) -- cgit v1.2.3-54-g00ecf 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 ++++++++++++++++++++-- .../btrfsinspect/rebuildnodes/rebuild.go | 14 ++++++- lib/containers/set.go | 13 +++++++ 3 files changed, 66 insertions(+), 4 deletions(-) (limited to 'lib/containers') 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 } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index be2834b..5dc4fa6 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -65,7 +65,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } dlog.Info(ctx, "Indexing orphans...") - orphans, leaf2orphans, key2leaf, err := indexOrphans(fs, *sb, *scanData.nodeGraph) + orphans, leaf2orphans, key2leaf, err := indexOrphans(ctx, fs, *sb, *scanData.nodeGraph) if err != nil { return nil, err } @@ -93,6 +93,8 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } func (o *Rebuilder) rebuild(ctx context.Context) error { + passNum := 0 + dlog.Infof(ctx, "... pass %d: scanning for implied items", passNum) o.pendingAugments = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) btrfsutil.WalkAllTrees(ctx, o.inner, btrfsutil.WalkAllTreesHandler{ Err: func(*btrfsutil.WalkError) {}, @@ -105,8 +107,10 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { }) for len(o.pendingAugments) > 0 { // Apply the augments, keeping track of what keys are added to what tree. + dlog.Infof(ctx, "... pass %d: augmenting trees to add implied items", passNum) newKeys := make(map[btrfsprim.ObjID][]btrfsprim.Key) for _, treeID := range maps.SortedKeys(o.pendingAugments) { + dlog.Infof(ctx, "... ... augmenting tree %v:", treeID) treeAugments := o.resolveTreeAugments(ctx, o.pendingAugments[treeID]) for _, nodeAddr := range maps.SortedKeys(treeAugments) { added, err := o.inner.Augment(treeID, nodeAddr) @@ -126,7 +130,9 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { } // Clear the list of pending augments. o.pendingAugments = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) + passNum++ // Call handleItem() for each of the added keys. + dlog.Infof(ctx, "... pass %d: scanning for implied items", passNum) for _, treeID := range maps.SortedKeys(newKeys) { for _, key := range newKeys[treeID] { item, err := o.inner.TreeLookup(treeID, key) @@ -247,6 +253,11 @@ func (o *Rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances accept(item) } } + + for i, list := range lists { + dlog.Infof(ctx, "... ... ... %d: %v: %v", i, list.Intersection(ret).TakeOne(), maps.SortedKeys(list)) + } + return ret } @@ -287,6 +298,7 @@ func (o *Rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, cho } } if len(choicesWithDist) > 0 { + dlog.Infof(ctx, "augment(tree=%v): %v", treeID, maps.SortedKeys(choicesWithDist)) o.pendingAugments[treeID] = append(o.pendingAugments[treeID], choicesWithDist) } } diff --git a/lib/containers/set.go b/lib/containers/set.go index d3f8ca7..67ba7ac 100644 --- a/lib/containers/set.go +++ b/lib/containers/set.go @@ -150,3 +150,16 @@ func (small Set[T]) HasAny(big Set[T]) bool { } return false } + +func (small Set[T]) Intersection(big Set[T]) Set[T] { + if len(big) < len(small) { + small, big = big, small + } + ret := make(Set[T]) + for v := range small { + if _, ok := big[v]; ok { + ret.Insert(v) + } + } + return ret +} -- cgit v1.2.3-54-g00ecf From 88cad1bad73897b38de4c0628ace8c99efbc421c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 13 Dec 2022 23:12:37 -0700 Subject: containers: rbtree.go: Track size of the tree --- lib/containers/rbtree.go | 7 +++++++ lib/containers/rbtree_test.go | 1 + 2 files changed, 8 insertions(+) (limited to 'lib/containers') diff --git a/lib/containers/rbtree.go b/lib/containers/rbtree.go index ab79a26..e2d8f8a 100644 --- a/lib/containers/rbtree.go +++ b/lib/containers/rbtree.go @@ -37,6 +37,11 @@ type RBTree[K Ordered[K], V any] struct { KeyFn func(V) K AttrFn func(*RBNode[V]) root *RBNode[V] + len int +} + +func (t *RBTree[K, V]) Len() int { + return t.len } func (t *RBTree[K, V]) Walk(fn func(*RBNode[V]) error) error { @@ -324,6 +329,7 @@ func (t *RBTree[K, V]) Insert(val V) { exact.Value = val return } + t.len++ node := &RBNode[V]{ Color: Red, @@ -394,6 +400,7 @@ func (t *RBTree[K, V]) Delete(key K) { if nodeToDelete == nil { return } + t.len-- // This is closely based on the algorithm presented in CLRS // 3e. diff --git a/lib/containers/rbtree_test.go b/lib/containers/rbtree_test.go index 9841d26..a487c52 100644 --- a/lib/containers/rbtree_test.go +++ b/lib/containers/rbtree_test.go @@ -112,6 +112,7 @@ func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet Set[K], return nil })) require.Equal(t, expectedOrder, actOrder) + require.Equal(t, tree.Len(), len(expectedSet)) } func FuzzRBTree(f *testing.F) { -- cgit v1.2.3-54-g00ecf From c93fbf4918b18606e50385c577ee9d6be701f370 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 13 Dec 2022 23:12:52 -0700 Subject: containers: intervaltree_test.go: Touch up logging --- lib/containers/intervaltree_test.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/containers') diff --git a/lib/containers/intervaltree_test.go b/lib/containers/intervaltree_test.go index 7a4689b..88c3003 100644 --- a/lib/containers/intervaltree_test.go +++ b/lib/containers/intervaltree_test.go @@ -56,7 +56,7 @@ func TestIntervalTree(t *testing.T) { tree.Insert(SimpleInterval{6, 10}) tree.Insert(SimpleInterval{19, 20}) - t.Log(tree.ASCIIArt()) + t.Log("\n" + tree.ASCIIArt()) // find intervals that touch [9,20] intervals := tree.SearchAll(func(k NativeOrdered[int]) int { -- cgit v1.2.3-54-g00ecf