From 7fba10e5be51a3fe565a6f69a946ece9f0e59a67 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 5 Sep 2022 12:43:46 -0600 Subject: Try to uniformly use containers.Set --- cmd/btrfs-rec/inspect_lstrees.go | 8 ++++---- lib/btrfs/btrfsvol/lvm.go | 2 ++ lib/btrfs/io4_fs.go | 6 +++--- lib/btrfsprogs/btrfsinspect/mount.go | 8 ++++---- .../btrfsinspect/rebuildmappings/blockgroups.go | 2 +- .../btrfsinspect/rebuildnodes/s1_uuidmap.go | 14 +++++++------- .../btrfsinspect/rebuildnodes/s2_classify.go | 14 +++++++------- lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go | 12 ++++++++---- .../btrfsinspect/rebuildnodes/s3_reinit_test.go | 12 ++++++------ .../btrfsinspect/rebuildnodes/s4_reattach.go | 8 ++++---- .../btrfsinspect/rebuildnodes/visualizenodes.go | 4 ++-- lib/containers/rbtree_test.go | 6 +++--- lib/containers/set.go | 19 ++++++++++++++++++- 13 files changed, 69 insertions(+), 46 deletions(-) diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go index a0f4ff3..f97eb2b 100644 --- a/cmd/btrfs-rec/inspect_lstrees.go +++ b/cmd/btrfs-rec/inspect_lstrees.go @@ -64,7 +64,7 @@ func init() { fmt.Fprintf(table, " total items\t% *s\n", numWidth, strconv.Itoa(totalItems)) table.Flush() } - visitedNodes := make(map[btrfsvol.LogicalAddr]struct{}) + visitedNodes := make(containers.Set[btrfsvol.LogicalAddr]) btrfsutil.WalkAllTrees(cmd.Context(), fs, btrfsutil.WalkAllTreesHandler{ PreTree: func(name string, treeID btrfsprim.ObjID) { treeErrCnt = 0 @@ -76,7 +76,7 @@ func init() { }, TreeWalkHandler: btrfstree.TreeWalkHandler{ Node: func(_ btrfstree.TreePath, ref *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - visitedNodes[ref.Addr] = struct{}{} + visitedNodes.Insert(ref.Addr) return nil }, Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { @@ -102,10 +102,10 @@ func init() { sb, _ := fs.Superblock() for _, devResults := range scanResults { for laddr := range devResults.FoundNodes { - if _, visited := visitedNodes[laddr]; visited { + if visitedNodes.Has(laddr) { continue } - visitedNodes[laddr] = struct{}{} + visitedNodes.Insert(laddr) node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, }) diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index 8003466..e12e53e 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -256,6 +256,8 @@ 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) { node := lv.logical2physical.Search(func(chunk chunkMapping) int { return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk) diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 8751078..82d4c87 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -248,13 +248,13 @@ func (ret *Dir) populate() { panic(fmt.Errorf("TODO: handle item type %v", item.Key.ItemType)) } } - entriesWithIndexes := make(map[string]struct{}) + entriesWithIndexes := make(containers.Set[string]) nextIndex := uint64(2) for index, entry := range ret.ChildrenByIndex { if index+1 > nextIndex { nextIndex = index + 1 } - entriesWithIndexes[string(entry.Name)] = struct{}{} + entriesWithIndexes.Insert(string(entry.Name)) if other, exists := ret.ChildrenByName[string(entry.Name)]; !exists { ret.Errs = append(ret.Errs, fmt.Errorf("missing by-name direntry for %q", entry.Name)) ret.ChildrenByName[string(entry.Name)] = entry @@ -264,7 +264,7 @@ func (ret *Dir) populate() { } } for _, name := range maps.SortedKeys(ret.ChildrenByName) { - if _, exists := entriesWithIndexes[name]; !exists { + if !entriesWithIndexes.Has(name) { ret.Errs = append(ret.Errs, fmt.Errorf("missing by-index direntry for %q", name)) ret.ChildrenByIndex[nextIndex] = ret.ChildrenByName[name] nextIndex++ diff --git a/lib/btrfsprogs/btrfsinspect/mount.go b/lib/btrfsprogs/btrfsinspect/mount.go index 5905034..6cf6317 100644 --- a/lib/btrfsprogs/btrfsinspect/mount.go +++ b/lib/btrfsprogs/btrfsinspect/mount.go @@ -112,7 +112,7 @@ type subvolume struct { fileHandles containers.SyncMap[fuseops.HandleID, *fileState] subvolMu sync.Mutex - subvols map[string]struct{} + subvols containers.Set[string] grp *dgroup.Group } @@ -176,11 +176,11 @@ func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error) continue } if sv.subvols == nil { - sv.subvols = make(map[string]struct{}) + sv.subvols = make(containers.Set[string]) } subMountpoint := filepath.Join(abspath, string(entry.Name)) - if _, alreadyMounted := sv.subvols[subMountpoint]; !alreadyMounted { - sv.subvols[subMountpoint] = struct{}{} + if !sv.subvols.Has(subMountpoint) { + sv.subvols.Insert(subMountpoint) workerName := fmt.Sprintf("%d-%s", val.Inode, filepath.Base(subMountpoint)) sv.grp.Go(workerName, func(ctx context.Context) error { subSv := &subvolume{ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go index 91fecbc..a638f7c 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go @@ -21,7 +21,7 @@ type BlockGroup struct { func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) { // Dedup - bgsSet := make(map[BlockGroup]struct{}) + bgsSet := make(map[BlockGroup]struct{}) // Can't use containers.Set because BlockGroup isn't ordered for _, devResults := range scanResults { for _, bg := range devResults.FoundBlockGroups { bgsSet[BlockGroup{ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go index 4122b21..9a2bd89 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go @@ -25,18 +25,18 @@ type uuidMap struct { UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID TreeParent map[btrfsprim.ObjID]btrfsprim.UUID - SeenTrees map[btrfsprim.ObjID]struct{} + SeenTrees containers.Set[btrfsprim.ObjID] } -func (m uuidMap) missingRootItems() map[btrfsprim.ObjID]struct{} { - missing := make(map[btrfsprim.ObjID]struct{}) +func (m uuidMap) missingRootItems() containers.Set[btrfsprim.ObjID] { + missing := make(containers.Set[btrfsprim.ObjID]) for treeID := range m.SeenTrees { if _, ok := m.ObjID2UUID[treeID]; !ok && treeID != btrfsprim.ROOT_TREE_OBJECTID { - missing[treeID] = struct{}{} + missing.Insert(treeID) continue } if _, ok := m.TreeParent[treeID]; !ok && treeID >= btrfsprim.FIRST_FREE_OBJECTID && treeID <= btrfsprim.LAST_FREE_OBJECTID { - missing[treeID] = struct{}{} + missing.Insert(treeID) } } return missing @@ -163,7 +163,7 @@ func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sc UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID), TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID), - SeenTrees: make(map[btrfsprim.ObjID]struct{}), + SeenTrees: make(containers.Set[btrfsprim.ObjID]), } progress() @@ -199,7 +199,7 @@ func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sc } } } - ret.SeenTrees[nodeRef.Data.Head.Owner] = struct{}{} + ret.SeenTrees.Insert(nodeRef.Data.Head.Owner) done++ progress() } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go index 9274a89..6adddc3 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go @@ -32,7 +32,7 @@ type badNode struct { // 2. the list of bad nodes (in no particular order) // 3. tree ancestors thing func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDevicesResult) ( - orphanedNodes map[btrfsvol.LogicalAddr]struct{}, + orphanedNodes containers.Set[btrfsvol.LogicalAddr], badNodes []badNode, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID], err error, @@ -41,7 +41,7 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev lastPct := -1 total := countNodes(scanResults) - visitedNodes := make(map[btrfsvol.LogicalAddr]struct{}) + visitedNodes := make(containers.Set[btrfsvol.LogicalAddr]) progress := func() { done := len(visitedNodes) pct := int(100 * float64(done) / float64(total)) @@ -64,7 +64,7 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev return err } addr := path.Node(-1).ToNodeAddr - visitedNodes[addr] = struct{}{} + visitedNodes.Insert(addr) if potentialRoot != 0 { // lost node if addr != potentialRoot { @@ -84,7 +84,7 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev walkHandler := btrfstree.TreeWalkHandler{ PreNode: func(path btrfstree.TreePath) error { addr := path.Node(-1).ToNodeAddr - if _, alreadyVisited := visitedNodes[addr]; alreadyVisited { + if visitedNodes.Has(addr) { // Can happen because of COW subvolumes; // this is really a DAG not a tree. return iofs.SkipDir @@ -109,11 +109,11 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev // Start with 'orphanedRoots' as a complete set of all orphaned nodes, and then delete // non-root entries from it. - orphanedNodes = make(map[btrfsvol.LogicalAddr]struct{}) + orphanedNodes = make(containers.Set[btrfsvol.LogicalAddr]) for _, devResults := range scanResults { for laddr := range devResults.FoundNodes { - if _, attached := visitedNodes[laddr]; !attached { - orphanedNodes[laddr] = struct{}{} + if !visitedNodes.Has(laddr) { + orphanedNodes.Insert(laddr) } } } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go index 5655eb6..7b43d28 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go @@ -105,10 +105,14 @@ func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btr min, max := spanOfTreePath(fs, path) node := RebuiltNode{ - Errs: containers.Set[string]{badNode.Err: struct{}{}}, - MinKey: min, - MaxKey: max, - InTrees: containers.Set[btrfsprim.ObjID]{path.Node(-1).FromTree: struct{}{}}, + Errs: containers.NewSet[string]( + badNode.Err, + ), + MinKey: min, + MaxKey: max, + InTrees: containers.NewSet[btrfsprim.ObjID]( + path.Node(-1).FromTree, + ), Node: btrfstree.Node{ Size: sb.NodeSize, ChecksumType: sb.ChecksumType, diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go index b361606..badfdfc 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go @@ -21,14 +21,14 @@ import ( func TestEncodeRebuiltNodes(t *testing.T) { dat := map[btrfsvol.LogicalAddr]*rebuildnodes.RebuiltNode{ 100007133184: { - Errs: containers.Set[string]{ - "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025": struct{}{}, - }, + Errs: containers.NewSet[string]( + "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025", + ), MinKey: btrfsprim.Key{}, MaxKey: btrfsprim.Key{}, - InTrees: containers.Set[btrfsprim.ObjID]{ - 257: struct{}{}, - }, + InTrees: containers.NewSet[btrfsprim.ObjID]( + 257, + ), Node: btrfstree.Node{}, }, } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go index 45fcc23..ef7d284 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go @@ -31,7 +31,7 @@ func (a RebuiltNode) ContainsWholeRegion(min, max btrfsprim.Key) int { } } -func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { +func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes containers.Set[btrfsvol.LogicalAddr], rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...") sb, err := fs.Superblock() @@ -91,12 +91,12 @@ func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.Logic trees := make(containers.Set[btrfsprim.ObjID]) tree := foundRef.Data.Head.Owner for { - trees[tree] = struct{}{} + trees.Insert(tree) var ok bool tree, ok = fs.ParentTree(tree) if !ok { // error; accept anything - trees[0] = struct{}{} + trees.Insert(0) break } if tree == 0 { @@ -113,7 +113,7 @@ func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.Logic if parent.Node.Head.Generation < foundRef.Data.Head.Generation { continue } - if !trees.HasIntersection(parent.InTrees) { + if !trees.HasAny(parent.InTrees) { continue } parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go index ffb07c3..38742a0 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go @@ -119,10 +119,10 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe edges.Insert(edge.String()) // Return - if _, alreadyVisited := visitedNodes[addr]; alreadyVisited { + if visitedNodes.Has(addr) { return iofs.SkipDir } - visitedNodes[addr] = struct{}{} + visitedNodes.Insert(addr) return err } diff --git a/lib/containers/rbtree_test.go b/lib/containers/rbtree_test.go index 65cc78d..9841d26 100644 --- a/lib/containers/rbtree_test.go +++ b/lib/containers/rbtree_test.go @@ -49,7 +49,7 @@ func (node *RBNode[V]) asciiArt(w io.Writer, u, m, l string) { node.Left.asciiArt(w, l+" | ", l+" `--", l+" ") } -func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *RBTree[NativeOrdered[K], V]) { +func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet Set[K], tree *RBTree[NativeOrdered[K], V]) { // 1. Every node is either red or black // 2. The root is black. @@ -142,7 +142,7 @@ func FuzzRBTree(f *testing.F) { return NativeOrdered[uint8]{Val: x} }, } - set := make(map[uint8]struct{}) + set := make(Set[uint8]) checkRBTree(t, set, tree) t.Logf("\n%s\n", tree.ASCIIArt()) for _, b := range dat { @@ -151,7 +151,7 @@ func FuzzRBTree(f *testing.F) { if ins { t.Logf("Insert(%v)", val) tree.Insert(val) - set[val] = struct{}{} + set.Insert(val) t.Logf("\n%s\n", tree.ASCIIArt()) node := tree.Lookup(NativeOrdered[uint8]{Val: val}) require.NotNil(t, node) diff --git a/lib/containers/set.go b/lib/containers/set.go index 42e5ad2..1c525ca 100644 --- a/lib/containers/set.go +++ b/lib/containers/set.go @@ -13,6 +13,10 @@ import ( "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{} var ( @@ -45,6 +49,14 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error { }) } +func NewSet[T constraints.Ordered](values ...T) Set[T] { + ret := make(Set[T], len(values)) + for _, value := range values { + ret.Insert(value) + } + return ret +} + func (o Set[T]) Insert(v T) { o[v] = struct{}{} } @@ -79,7 +91,12 @@ func (o Set[T]) TakeOne() T { return zero } -func (small Set[T]) HasIntersection(big Set[T]) bool { +func (o Set[T]) Has(v T) bool { + _, has := o[v] + return has +} + +func (small Set[T]) HasAny(big Set[T]) bool { if len(big) < len(small) { small, big = big, small } -- cgit v1.2.3-2-g168b