summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorLuke Shumaker <lukeshu@lukeshu.com>2022-09-05 12:43:46 -0600
committerLuke Shumaker <lukeshu@lukeshu.com>2022-09-05 12:43:46 -0600
commit7fba10e5be51a3fe565a6f69a946ece9f0e59a67 (patch)
tree91bc89b8d1e5dba3ead0319daeef3181ccc6da4d /lib
parentabdc8394bcb7080f01859cbfe367beecf5aef06f (diff)
Try to uniformly use containers.Set
Diffstat (limited to 'lib')
-rw-r--r--lib/btrfs/btrfsvol/lvm.go2
-rw-r--r--lib/btrfs/io4_fs.go6
-rw-r--r--lib/btrfsprogs/btrfsinspect/mount.go8
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go2
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go14
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go14
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go12
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go12
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go8
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go4
-rw-r--r--lib/containers/rbtree_test.go6
-rw-r--r--lib/containers/set.go19
12 files changed, 65 insertions, 42 deletions
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
}