Merge branch 'lukeshu/containers'

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