wip better vol

2 files changed, 249 insertions, 2 deletions

diff --git a/pkg/btrfs/io2_fs.go b/pkg/btrfs/io2_fs.go
index 8b76e2d..fd5f07a 100644
--- a/pkg/btrfs/io2_fs.go
+++ b/pkg/btrfs/io2_fs.go
@@ -13,8 +13,9 @@ import (
 type FS struct {
 	Devices []*Device
 
-	uuid2dev map[UUID]*Device
-	chunks   []SysChunk
+	uuid2dev         map[UUID]*Device
+	logical2physical [][]mapping
+	physical2logical map[UUID][]mapping
 
 	cacheSuperblocks []*util.Ref[PhysicalAddr, Superblock]
 	cacheSuperblock  *util.Ref[PhysicalAddr, Superblock]
@@ -40,6 +41,241 @@ func (fs *FS) Size() (LogicalAddr, error) {
 	return ret, nil
 }
 
+// logical => []physical
+type chunkMapping struct {
+	LAddr  LogicalAddr
+	PAddrs map[QualifiedPhysicalAddr]struct{}
+	Size   AddrDelta
+	Flags  *btrfsitem.BlockGroupFlags
+}
+
+// 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) bool {
+	switch {
+	case a.LAddr+a.Size <= b.LAddr:
+		// 'a' is wholly to the left of 'b'.
+		return -1
+	case b.LAddr+b.Size <= a.LAddr:
+		// 'a' is wholly to the right of 'b'.
+		return 1
+	default:
+		// There is some overlap.
+		return 0
+	}
+}
+
+func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) {
+	// sanity check
+	for _, chunk := range rest {
+		if a.cmpRange(chunk) != 0 {
+			return chunkMapping{}, fmt.Errorf("chunks don't overlap")
+		}
+	}
+	chunks := append([]chunkMapping{a}, rest...)
+	// figure out the logical range (.LAddr and .Size)
+	beg := chunks[0].LAddr
+	end := chunks[0].LAddr.Add(chunks[0].Size)
+	for _, chunk := range chunks {
+		beg = util.Min(beg, chunk.LAddr)
+		end = util.Max(end, chunk.LAddr.Add(chunk.Size))
+	}
+	ret := chunkMapping{
+		LAddr: beg,
+		Size:  end.Sub(beg),
+	}
+	// figure out the physical stripes (.PAddrs)
+	ret.PAddrs = make(map[QualifiedPhysicalAddr]struct{})
+	for _, chunk := range chunks {
+		offsetWithinRet := chunk.LAddr.Sub(ret.Laddr)
+		for stripe := range chunk.PAddrs {
+			ret.PAddrs[QualifiedPhysicalAddr{
+				Dev:  stripe.Dev,
+				Addr: stripe.Addr.Add(-offsetWithinRet),
+			}] = struct{}{}
+		}
+	}
+	// figure out the flags (.Flags)
+	for _, chunk := range chunks {
+		if chunk.Flags == nil {
+			continue
+		}
+		if ret.Flags == nil {
+			val := *chunk.Flags
+			ret.Flags = &val
+		}
+		if *ret.Flags != *chunk.Flags {
+			return ret, fmt.Errorf("mismatch flags: %v != %v", *ret.Flags, *chunk.Flags)
+		}
+	}
+	// done
+	return ret, nil
+}
+
+// physical => logical
+type devextMapping struct {
+	PAddr QualifiedPhysicalAddr
+	LAddr LogicalAddr
+	Size  AddrDelta
+	Flags *btrfsitem.BlockGroupFlags
+}
+
+// return -2 if 'a' and 'b' are on different devices
+// 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) bool {
+	switch {
+	case a.PAddr.Dev != b.PAddr.Dev:
+		// 'a' and 'b' are on different devices.
+		return -2
+	case a.PAddr.Addr+a.Size <= b.PAddr.Addr:
+		// 'a' is wholly to the left of 'b'.
+		return -1
+	case b.PAddr.Addr+b.Size <= a.PAddr.Addr:
+		// 'a' is wholly to the right of 'b'.
+		return 1
+	default:
+		// There is some overlap.
+		return 0
+	}
+}
+
+func (a devextMapping) union(rest ...devextMapping) (devextMapping, error) {
+	// sanity check
+	for _, ext := range rest {
+		if a.cmpRange(ext) != 0 {
+			return devextMapping{}, fmt.Errorf("devexts don't overlap")
+		}
+	}
+	exts := append([]devextMapping{a}, rest...)
+	// figure out the physical range (.PAddr and .Size)
+	beg := exts[0].PAddr.Addr
+	end := beg.Add(exts[0].Size)
+	for _, ext := range exts {
+		beg = util.Min(beg, ext.PAddr.Addr)
+		end = util.Max(end, ext.PAddr.Addr.Add(ext.Size))
+	}
+	ret := devextMapping{
+		PAddr: QualifiedPhysicalAddr{
+			Dev:  exts[0].PAddr.Dev,
+			Addr: beg,
+		},
+		Size: end.Sub(beg),
+	}
+	// figure out the logical range (.LAddr)
+	first := true
+	for _, ext := range exts {
+		offsetWithinRet := ext.PAddr.Addr.Sub(ret.PAddr.Addr)
+		laddr := ext.LAddr.Add(-offsetWithinRet)
+		if first {
+			ret.LAddr = laddr
+		} else if laddr != ret.LAddr {
+			return ret, fmt.Errorf("devexts don't agree on laddr: %v != %v", ret.LAddr, laddr)
+		}
+	}
+	// figure out the flags (.Flags)
+	for _, ext := range exts {
+		if ext.Flags == nil {
+			continue
+		}
+		if ret.Flags == nil {
+			val := *ext.Flags
+			ret.Flags = &val
+		}
+		if *ret.Flags != *ext.Flags {
+			return ret, fmt.Errorf("mismatch flags: %v != %v", *ret.Flags, *ext.Flags)
+		}
+	}
+	// done
+	return ret, nil
+}
+
+func (fs *FS) AddMapping(laddr LogicalAddr, paddr QualifiedPhysicalAddr, size AddrDelta, flags *btrfsitem.BlockGroupFlags) error {
+	// logical2physical
+	newChunk := chunkMapping{
+		LAddr: laddr,
+		PAddr: paddr,
+		Size:  size,
+		Flags: flags,
+	}
+	var logicalOverlaps []chunkMapping
+	for _, chunk := range fs.logical2physical {
+		switch newChunk.cmpRange(chunk) {
+		case 0:
+			logicalOverlaps = append(logicalOverlaps, chunk)
+		case 1:
+			break
+		}
+	}
+	if len(logicalOverlaps) > 0 {
+		var err error
+		newChunk, err = newChunk.union(logicalOverlaps...)
+		if err != nil {
+			return err
+		}
+	}
+
+	// physical2logical
+	newExt := devextMapping{
+		PAddr: paddr,
+		LAddr: laddr,
+		Size:  size,
+		Flags: flags,
+	}
+	var physicalOverlaps []*mapping
+	for _, ext := range fs.physical2logical[m.PAddr.Dev] {
+		switch newExt.cmpPhysicalRange(ext) {
+		case 0:
+			physicalOverlaps = append(physicalOverlaps, ext)
+		case 1:
+			break
+		}
+	}
+	if len(physicalOverlaps) > 0 {
+		var err error
+		newExt, err = newExt.union(physicalOverlaps)
+		if err != nil {
+			return err
+		}
+	}
+
+	// combine
+	if flags == nil {
+		if newChunk.Flags != nil {
+			if newExt.Flags != nil && *newChunk.Flags != *newExt.Flags {
+				return fmt.Errorf("mismatch flags: %v != %v", *newChunk.Flags, *newExt.Flags)
+			}
+			newExt.Flags = newChunk.Flags
+		} else if newExt.Flags != nil {
+			newChunk.Flags = newExt.Flags
+		}
+	}
+
+	// logical2physical
+	for _, chunk := range logicalOverlaps {
+		fs.logical2physical = util.RemoveFromSlice(fs.logical2physical, chunk)
+	}
+	fs.logical2physical = append(fs.logical2physical, newChunk)
+	sort.Slice(fs.logical2physical, func(i, j int) bool {
+		return fs.logical2physical[i].LAddr < fs.logical2physical[j].LAddr
+	})
+
+	// physical2logical
+	for _, ext := range physicalOverlaps {
+		fs.physical2logical[newExt.PAddr.Dev] = util.RemoveFromSlice(fs.physical2logical[newExt.PAddr.Dev], ext)
+	}
+	fs.physical2logical[newExt.PAddr.Dev] = append(fs.physical2logical[newExt.PAddr.Dev], newExt)
+	sort.Slice(fs.physical2logical[newExt.PAddr.Dev], func(i, j int) bool {
+		return fs.physical2logical[newExt.PAddr.Dev][i].LAddr < fs.physical2logical[newExt.PAddr.Dev][j].LAddr
+	})
+
+	// sanity check
+
+	return nil
+}
+
 func (fs *FS) Superblocks() ([]*util.Ref[PhysicalAddr, Superblock], error) {
 	if fs.cacheSuperblocks != nil {
 		return fs.cacheSuperblocks, nil
diff --git a/pkg/util/generic.go b/pkg/util/generic.go
index 79096ab..7ff2445 100644
--- a/pkg/util/generic.go
+++ b/pkg/util/generic.go
@@ -13,6 +13,17 @@ func InSlice[T comparable](needle T, haystack []T) bool {
 	return false
 }
 
+func RemoveFromSlice[T comparable](haystack []T, needle T) []T {
+	for i, straw := range haystack {
+		if needle == straw {
+			return append(
+				haystack[:i],
+				RemoveFromSlice(haystack[i+1], item)...)
+		}
+	}
+	return haystack
+}
+
 func Max[T constraints.Ordered](a, b T) T {
 	if a > b {
 		return a