From 0ff1d420f21101a92d8da888d491860cf0cf16cc Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 5 Feb 2023 10:03:08 -0700 Subject: containers: s/Cmp/Compare/ to match the standard library Go 1.18 added net/netip.Addr.Compare, and Go 1.20 added time.Time.Compare. --- lib/btrfs/btrfsvol/addr.go | 4 ++-- lib/btrfs/btrfsvol/chunk.go | 8 ++++---- lib/btrfs/btrfsvol/devext.go | 6 +++--- lib/btrfs/btrfsvol/lvm.go | 10 +++++----- 4 files changed, 14 insertions(+), 14 deletions(-) (limited to 'lib/btrfs/btrfsvol') diff --git a/lib/btrfs/btrfsvol/addr.go b/lib/btrfs/btrfsvol/addr.go index 94320ef..655f4e9 100644 --- a/lib/btrfs/btrfsvol/addr.go +++ b/lib/btrfs/btrfsvol/addr.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -50,7 +50,7 @@ func (a QualifiedPhysicalAddr) Add(b AddrDelta) QualifiedPhysicalAddr { } } -func (a QualifiedPhysicalAddr) Cmp(b QualifiedPhysicalAddr) int { +func (a QualifiedPhysicalAddr) Compare(b QualifiedPhysicalAddr) int { if d := int(a.Dev - b.Dev); d != 0 { return d } diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go index 5f1baa8..08a0b2b 100644 --- a/lib/btrfs/btrfsvol/chunk.go +++ b/lib/btrfs/btrfsvol/chunk.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -27,7 +27,7 @@ type ChunkMapping = chunkMapping // return -1 if 'a' is wholly to the left of 'b' // return 0 if there is some overlap between 'a' and 'b' // return 1 if 'a is wholly to the right of 'b' -func (a chunkMapping) cmpRange(b chunkMapping) int { +func (a chunkMapping) compareRange(b chunkMapping) int { switch { case a.LAddr.Add(a.Size) <= b.LAddr: // 'a' is wholly to the left of 'b'. @@ -44,7 +44,7 @@ func (a chunkMapping) cmpRange(b chunkMapping) int { func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) { // sanity check for _, chunk := range rest { - if a.cmpRange(chunk) != 0 { + if a.compareRange(chunk) != 0 { return chunkMapping{}, fmt.Errorf("chunks don't overlap") } } @@ -79,7 +79,7 @@ func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) { } ret.PAddrs = maps.Keys(paddrs) sort.Slice(ret.PAddrs, func(i, j int) bool { - return ret.PAddrs[i].Cmp(ret.PAddrs[j]) < 0 + return ret.PAddrs[i].Compare(ret.PAddrs[j]) < 0 }) // figure out the flags (.Flags) for _, chunk := range chunks { diff --git a/lib/btrfs/btrfsvol/devext.go b/lib/btrfs/btrfsvol/devext.go index e8e5446..037021c 100644 --- a/lib/btrfs/btrfsvol/devext.go +++ b/lib/btrfs/btrfsvol/devext.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -23,7 +23,7 @@ type devextMapping struct { // return -1 if 'a' is wholly to the left of 'b' // return 0 if there is some overlap between 'a' and 'b' // return 1 if 'a is wholly to the right of 'b' -func (a devextMapping) cmpRange(b devextMapping) int { +func (a devextMapping) compareRange(b devextMapping) int { switch { case a.PAddr.Add(a.Size) <= b.PAddr: // 'a' is wholly to the left of 'b'. @@ -40,7 +40,7 @@ func (a devextMapping) cmpRange(b devextMapping) int { func (a devextMapping) union(rest ...devextMapping) (devextMapping, error) { // sanity check for _, ext := range rest { - if a.cmpRange(ext) != 0 { + if a.compareRange(ext) != 0 { return devextMapping{}, fmt.Errorf("devexts don't overlap") } } diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index 1cb1ded..b83e9cd 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -143,7 +143,7 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - logicalOverlaps := lv.logical2physical.SearchRange(newChunk.cmpRange) + logicalOverlaps := lv.logical2physical.SearchRange(newChunk.compareRange) var err error newChunk, err = newChunk.union(logicalOverlaps...) if err != nil { @@ -158,7 +158,7 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.cmpRange) + physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.compareRange) newExt, err = newExt.union(physicalOverlaps...) if err != nil { return fmt.Errorf("(%p).AddMapping: %w", lv, err) @@ -261,7 +261,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { 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) + return chunkMapping{LAddr: laddr, Size: 1}.compareRange(chunk) }) if node == nil { return nil, 0 @@ -281,7 +281,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs cont func (lv *LogicalVolume[PhysicalVolume]) ResolveAny(laddr LogicalAddr, size AddrDelta) (LogicalAddr, QualifiedPhysicalAddr) { node := lv.logical2physical.Search(func(chunk chunkMapping) int { - return chunkMapping{LAddr: laddr, Size: size}.cmpRange(chunk) + return chunkMapping{LAddr: laddr, Size: size}.compareRange(chunk) }) if node == nil { return -1, QualifiedPhysicalAddr{0, -1} @@ -291,7 +291,7 @@ func (lv *LogicalVolume[PhysicalVolume]) ResolveAny(laddr LogicalAddr, size Addr func (lv *LogicalVolume[PhysicalVolume]) UnResolve(paddr QualifiedPhysicalAddr) LogicalAddr { node := lv.physical2logical[paddr.Dev].Search(func(ext devextMapping) int { - return devextMapping{PAddr: paddr.Addr, Size: 1}.cmpRange(ext) + return devextMapping{PAddr: paddr.Addr, Size: 1}.compareRange(ext) }) if node == nil { return -1 -- cgit v1.2.3-2-g168b From b608e4cf9c9e6e5bf5a333e8d78b2800ffcb0c91 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 5 Feb 2023 10:21:33 -0700 Subject: btrfsvol: Add a sanity check --- lib/btrfs/btrfsvol/blockgroupflags.go | 5 +++++ lib/btrfs/btrfsvol/lvm.go | 26 ++++++++++++++++++++++++++ 2 files changed, 31 insertions(+) (limited to 'lib/btrfs/btrfsvol') diff --git a/lib/btrfs/btrfsvol/blockgroupflags.go b/lib/btrfs/btrfsvol/blockgroupflags.go index 4ca5544..0125664 100644 --- a/lib/btrfs/btrfsvol/blockgroupflags.go +++ b/lib/btrfs/btrfsvol/blockgroupflags.go @@ -23,6 +23,11 @@ const ( BLOCK_GROUP_RAID1C3 BLOCK_GROUP_RAID1C4 + // BLOCK_GROUP_RAID_MASK is the set of bits that mean that + // mean the logical:physical relationship is a one:many + // relationship rather than a one:one relationship. + // + // Notably, this does not include BLOCK_GROUP_RAID0. BLOCK_GROUP_RAID_MASK = (BLOCK_GROUP_RAID1 | BLOCK_GROUP_DUP | BLOCK_GROUP_RAID10 | BLOCK_GROUP_RAID5 | BLOCK_GROUP_RAID6 | BLOCK_GROUP_RAID1C3 | BLOCK_GROUP_RAID1C4) ) diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index b83e9cd..59ca609 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -144,6 +144,10 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro Flags: m.Flags, } logicalOverlaps := lv.logical2physical.SearchRange(newChunk.compareRange) + numOverlappingStripes := 0 + for _, chunk := range logicalOverlaps { + numOverlappingStripes += len(chunk.PAddrs) + } var err error newChunk, err = newChunk.union(logicalOverlaps...) if err != nil { @@ -164,6 +168,28 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro return fmt.Errorf("(%p).AddMapping: %w", lv, err) } + if newChunk.Flags != newExt.Flags { + // If these don't match up, it's a bug in this code. + panic(fmt.Errorf("should not happen: newChunk.Flags:%+v != newExt.Flags:%+v", + newChunk.Flags, newExt.Flags)) + } + switch { + case len(physicalOverlaps) == numOverlappingStripes: + // normal case + case len(physicalOverlaps) < numOverlappingStripes: + // .Flags = DUP or RAID{X} + if newChunk.Flags.OK && newChunk.Flags.Val&BLOCK_GROUP_RAID_MASK == 0 { + return fmt.Errorf("multiple stripes but flags=%v does not allow multiple stripes", + newChunk.Flags.Val) + } + case len(physicalOverlaps) > numOverlappingStripes: + // This should not happen because calling .AddMapping + // should update the two in lockstep; if these don't + // match up, it's a bug in this code. + panic(fmt.Errorf("should not happen: len(physicalOverlaps):%d != numOverlappingStripes:%d", + len(physicalOverlaps), numOverlappingStripes)) + } + if dryRun { return nil } -- cgit v1.2.3-2-g168b From 696a7d192e5eefa53230168a4b200ec0560c8a10 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 5 Feb 2023 00:31:29 -0700 Subject: containers: Rethink the RBTree interface to be simpler --- lib/btrfs/btrfsvol/chunk.go | 5 +++- lib/btrfs/btrfsvol/devext.go | 5 ++++ lib/btrfs/btrfsvol/lvm.go | 67 ++++++++++++++++++++------------------------ 3 files changed, 39 insertions(+), 38 deletions(-) (limited to 'lib/btrfs/btrfsvol') diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go index 08a0b2b..a112fd3 100644 --- a/lib/btrfs/btrfsvol/chunk.go +++ b/lib/btrfs/btrfsvol/chunk.go @@ -22,7 +22,10 @@ type chunkMapping struct { Flags containers.Optional[BlockGroupFlags] } -type ChunkMapping = chunkMapping +// Compare implements containers.Ordered. +func (a chunkMapping) Compare(b chunkMapping) int { + return containers.NativeCompare(a.LAddr, b.LAddr) +} // return -1 if 'a' is wholly to the left of 'b' // return 0 if there is some overlap between 'a' and 'b' diff --git a/lib/btrfs/btrfsvol/devext.go b/lib/btrfs/btrfsvol/devext.go index 037021c..3324476 100644 --- a/lib/btrfs/btrfsvol/devext.go +++ b/lib/btrfs/btrfsvol/devext.go @@ -20,6 +20,11 @@ type devextMapping struct { Flags containers.Optional[BlockGroupFlags] } +// Compare implements containers.Ordered. +func (a devextMapping) Compare(b devextMapping) int { + return containers.NativeCompare(a.PAddr, b.PAddr) +} + // return -1 if 'a' is wholly to the left of 'b' // return 0 if there is some overlap between 'a' and 'b' // return 1 if 'a is wholly to the right of 'b' diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index 59ca609..93ec438 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -22,8 +22,8 @@ type LogicalVolume[PhysicalVolume diskio.File[PhysicalAddr]] struct { id2pv map[DeviceID]PhysicalVolume - logical2physical *containers.RBTree[containers.NativeOrdered[LogicalAddr], chunkMapping] - physical2logical map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping] + logical2physical *containers.RBTree[chunkMapping] + physical2logical map[DeviceID]*containers.RBTree[devextMapping] } var _ diskio.File[LogicalAddr] = (*LogicalVolume[diskio.File[PhysicalAddr]])(nil) @@ -33,22 +33,14 @@ func (lv *LogicalVolume[PhysicalVolume]) init() { lv.id2pv = make(map[DeviceID]PhysicalVolume) } if lv.logical2physical == nil { - lv.logical2physical = &containers.RBTree[containers.NativeOrdered[LogicalAddr], chunkMapping]{ - KeyFn: func(chunk chunkMapping) containers.NativeOrdered[LogicalAddr] { - return containers.NativeOrdered[LogicalAddr]{Val: chunk.LAddr} - }, - } + lv.logical2physical = new(containers.RBTree[chunkMapping]) } if lv.physical2logical == nil { - lv.physical2logical = make(map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping], len(lv.id2pv)) + lv.physical2logical = make(map[DeviceID]*containers.RBTree[devextMapping], len(lv.id2pv)) } for devid := range lv.id2pv { if _, ok := lv.physical2logical[devid]; !ok { - lv.physical2logical[devid] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { - return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} - }, - } + lv.physical2logical[devid] = new(containers.RBTree[devextMapping]) } } } @@ -90,11 +82,7 @@ func (lv *LogicalVolume[PhysicalVolume]) AddPhysicalVolume(id DeviceID, dev Phys lv, dev.Name(), other.Name(), id) } lv.id2pv[id] = dev - lv.physical2logical[id] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { - return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} - }, - } + lv.physical2logical[id] = new(containers.RBTree[devextMapping]) return nil } @@ -143,11 +131,13 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - logicalOverlaps := lv.logical2physical.SearchRange(newChunk.compareRange) + var logicalOverlaps []chunkMapping numOverlappingStripes := 0 - for _, chunk := range logicalOverlaps { - numOverlappingStripes += len(chunk.PAddrs) - } + lv.logical2physical.Subrange(newChunk.compareRange, func(node *containers.RBNode[chunkMapping]) bool { + logicalOverlaps = append(logicalOverlaps, node.Value) + numOverlappingStripes += len(node.Value.PAddrs) + return true + }) var err error newChunk, err = newChunk.union(logicalOverlaps...) if err != nil { @@ -162,7 +152,11 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.compareRange) + var physicalOverlaps []devextMapping + lv.physical2logical[m.PAddr.Dev].Subrange(newExt.compareRange, func(node *containers.RBNode[devextMapping]) bool { + physicalOverlaps = append(physicalOverlaps, node.Value) + return true + }) newExt, err = newExt.union(physicalOverlaps...) if err != nil { return fmt.Errorf("(%p).AddMapping: %w", lv, err) @@ -202,13 +196,13 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro // logical2physical for _, chunk := range logicalOverlaps { - lv.logical2physical.Delete(containers.NativeOrdered[LogicalAddr]{Val: chunk.LAddr}) + lv.logical2physical.Delete(lv.logical2physical.Search(chunk.Compare)) } lv.logical2physical.Insert(newChunk) // physical2logical for _, ext := range physicalOverlaps { - lv.physical2logical[m.PAddr.Dev].Delete(containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}) + lv.physical2logical[m.PAddr.Dev].Delete(lv.physical2logical[m.PAddr.Dev].Search(ext.Compare)) } lv.physical2logical[m.PAddr.Dev].Insert(newExt) @@ -227,20 +221,18 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro } func (lv *LogicalVolume[PhysicalVolume]) fsck() error { - physical2logical := make(map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]) - if err := lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error { + physical2logical := make(map[DeviceID]*containers.RBTree[devextMapping]) + var err error + lv.logical2physical.Range(func(node *containers.RBNode[chunkMapping]) bool { chunk := node.Value for _, stripe := range chunk.PAddrs { if _, devOK := lv.id2pv[stripe.Dev]; !devOK { - return fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist", + err = fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist", lv, stripe.Dev) + return false } if _, exists := physical2logical[stripe.Dev]; !exists { - physical2logical[stripe.Dev] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { - return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} - }, - } + physical2logical[stripe.Dev] = new(containers.RBTree[devextMapping]) } physical2logical[stripe.Dev].Insert(devextMapping{ PAddr: stripe.Addr, @@ -249,8 +241,9 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error { Flags: chunk.Flags, }) } - return nil - }); err != nil { + return true + }) + if err != nil { return err } @@ -270,7 +263,7 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error { func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { var ret []Mapping - _ = lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error { + lv.logical2physical.Range(func(node *containers.RBNode[chunkMapping]) bool { chunk := node.Value for _, slice := range chunk.PAddrs { ret = append(ret, Mapping{ @@ -280,7 +273,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { Flags: chunk.Flags, }) } - return nil + return true }) return ret } -- cgit v1.2.3-2-g168b