summaryrefslogtreecommitdiff
path: root/lib/btrfs/btrfsvol
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfs/btrfsvol')
-rw-r--r--lib/btrfs/btrfsvol/addr.go4
-rw-r--r--lib/btrfs/btrfsvol/blockgroupflags.go5
-rw-r--r--lib/btrfs/btrfsvol/chunk.go13
-rw-r--r--lib/btrfs/btrfsvol/devext.go11
-rw-r--r--lib/btrfs/btrfsvol/lvm.go93
5 files changed, 79 insertions, 47 deletions
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 <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// 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/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/chunk.go b/lib/btrfs/btrfsvol/chunk.go
index 5f1baa8..a112fd3 100644
--- a/lib/btrfs/btrfsvol/chunk.go
+++ b/lib/btrfs/btrfsvol/chunk.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
@@ -22,12 +22,15 @@ 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'
// 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 +47,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 +82,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..3324476 100644
--- a/lib/btrfs/btrfsvol/devext.go
+++ b/lib/btrfs/btrfsvol/devext.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
@@ -20,10 +20,15 @@ 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'
-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 +45,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..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,7 +131,13 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro
SizeLocked: m.SizeLocked,
Flags: m.Flags,
}
- logicalOverlaps := lv.logical2physical.SearchRange(newChunk.cmpRange)
+ var logicalOverlaps []chunkMapping
+ numOverlappingStripes := 0
+ 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 {
@@ -158,12 +152,38 @@ 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)
+ 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)
}
+ 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
}
@@ -176,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)
@@ -201,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,
@@ -223,8 +241,9 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error {
Flags: chunk.Flags,
})
}
- return nil
- }); err != nil {
+ return true
+ })
+ if err != nil {
return err
}
@@ -244,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{
@@ -254,14 +273,14 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping {
Flags: chunk.Flags,
})
}
- return nil
+ return true
})
return ret
}
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 +300,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 +310,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
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-26 09:35:06 +0000