better volume!

8 files changed, 581 insertions, 365 deletions

diff --git a/pkg/btrfs/btrfsvol/chunk.go b/pkg/btrfs/btrfsvol/chunk.go
new file mode 100644
index 0000000..112d446
--- /dev/null
+++ b/pkg/btrfs/btrfsvol/chunk.go
@@ -0,0 +1,88 @@
+package btrfsvol
+
+import (
+	"fmt"
+	"sort"
+
+	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
+	"lukeshu.com/btrfs-tools/pkg/util"
+)
+
+// logical => []physical
+type chunkMapping struct {
+	LAddr  LogicalAddr
+	PAddrs []QualifiedPhysicalAddr
+	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) int {
+	switch {
+	case a.LAddr.Add(a.Size) <= b.LAddr:
+		// 'a' is wholly to the left of 'b'.
+		return -1
+	case b.LAddr.Add(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)
+	paddrs := make(map[QualifiedPhysicalAddr]struct{})
+	for _, chunk := range chunks {
+		offsetWithinRet := chunk.LAddr.Sub(ret.LAddr)
+		for _, stripe := range chunk.PAddrs {
+			paddrs[QualifiedPhysicalAddr{
+				Dev:  stripe.Dev,
+				Addr: stripe.Addr.Add(-offsetWithinRet),
+			}] = struct{}{}
+		}
+	}
+	ret.PAddrs = make([]QualifiedPhysicalAddr, 0, len(paddrs))
+	for paddr := range paddrs {
+		ret.PAddrs = append(ret.PAddrs, paddr)
+	}
+	sort.Slice(ret.PAddrs, func(i, j int) bool {
+		return ret.PAddrs[i].Cmp(ret.PAddrs[j]) < 0
+	})
+	// 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
+}
diff --git a/pkg/btrfs/btrfsvol/devext.go b/pkg/btrfs/btrfsvol/devext.go
new file mode 100644
index 0000000..7696624
--- /dev/null
+++ b/pkg/btrfs/btrfsvol/devext.go
@@ -0,0 +1,80 @@
+package btrfsvol
+
+import (
+	"fmt"
+
+	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
+	"lukeshu.com/btrfs-tools/pkg/util"
+)
+
+// physical => logical
+type devextMapping struct {
+	PAddr PhysicalAddr
+	LAddr LogicalAddr
+	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 devextMapping) cmpRange(b devextMapping) int {
+	switch {
+	case a.PAddr.Add(a.Size) <= b.PAddr:
+		// 'a' is wholly to the left of 'b'.
+		return -1
+	case b.PAddr.Add(b.Size) <= a.PAddr:
+		// '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
+	end := beg.Add(exts[0].Size)
+	for _, ext := range exts {
+		beg = util.Min(beg, ext.PAddr)
+		end = util.Max(end, ext.PAddr.Add(ext.Size))
+	}
+	ret := devextMapping{
+		PAddr: beg,
+		Size:  end.Sub(beg),
+	}
+	// figure out the logical range (.LAddr)
+	first := true
+	for _, ext := range exts {
+		offsetWithinRet := ext.PAddr.Sub(ret.PAddr)
+		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
+}
diff --git a/pkg/btrfs/btrfsvol/lvm.go b/pkg/btrfs/btrfsvol/lvm.go
new file mode 100644
index 0000000..dc3bd06
--- /dev/null
+++ b/pkg/btrfs/btrfsvol/lvm.go
@@ -0,0 +1,310 @@
+package btrfsvol
+
+import (
+	"bytes"
+	"fmt"
+	"math"
+	"reflect"
+	"sort"
+
+	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
+	"lukeshu.com/btrfs-tools/pkg/btrfs/internal"
+	"lukeshu.com/btrfs-tools/pkg/util"
+)
+
+type (
+	LogicalAddr           = internal.LogicalAddr
+	PhysicalAddr          = internal.PhysicalAddr
+	AddrDelta             = internal.AddrDelta
+	QualifiedPhysicalAddr = internal.QualifiedPhysicalAddr
+)
+
+type PhysicalVolume = util.File[PhysicalAddr]
+
+type LogicalVolume struct {
+	name string
+
+	uuid2pv map[internal.UUID]PhysicalVolume
+
+	logical2physical []chunkMapping
+	physical2logical map[internal.UUID][]devextMapping
+}
+
+var _ util.File[LogicalAddr] = (*LogicalVolume)(nil)
+
+func (lv *LogicalVolume) SetName(name string) {
+	lv.name = name
+}
+
+func (lv *LogicalVolume) Name() string {
+	return lv.name
+}
+
+func (lv *LogicalVolume) Size() (LogicalAddr, error) {
+	if len(lv.logical2physical) == 0 {
+		return 0, nil
+	}
+	lastChunk := lv.logical2physical[len(lv.logical2physical)-1]
+	return lastChunk.LAddr.Add(lastChunk.Size), nil
+}
+
+func (lv *LogicalVolume) AddPhysicalVolume(uuid internal.UUID, dev PhysicalVolume) error {
+	if lv.uuid2pv == nil {
+		lv.uuid2pv = make(map[internal.UUID]PhysicalVolume)
+	}
+	if other, exists := lv.uuid2pv[uuid]; exists {
+		return fmt.Errorf("(%p).AddPhysicalVolume: cannot add physical volume %q: already have physical volume %q with uuid=%v",
+			lv, dev.Name(), other.Name(), uuid)
+	}
+	lv.uuid2pv[uuid] = dev
+	return nil
+}
+
+func (lv *LogicalVolume) PhysicalVolumes() []PhysicalVolume {
+	uuids := make([]internal.UUID, 0, len(lv.uuid2pv))
+	for uuid := range lv.uuid2pv {
+		uuids = append(uuids, uuid)
+	}
+	sort.Slice(uuids, func(i, j int) bool {
+		return uuids[i].Cmp(uuids[j]) < 0
+	})
+	ret := make([]PhysicalVolume, 0, len(lv.uuid2pv))
+	for _, uuid := range uuids {
+		ret = append(ret, lv.uuid2pv[uuid])
+	}
+	return ret
+}
+
+func (lv *LogicalVolume) ClearMappings() {
+	lv.logical2physical = nil
+	lv.physical2logical = nil
+}
+
+func (lv *LogicalVolume) AddMapping(laddr LogicalAddr, paddr QualifiedPhysicalAddr, size AddrDelta, flags *btrfsitem.BlockGroupFlags) error {
+	// sanity check
+	if _, haveDev := lv.uuid2pv[paddr.Dev]; !haveDev {
+		return fmt.Errorf("(%p).AddMapping: do not have a physical volume with uuid=%v",
+			lv, paddr.Dev)
+	}
+	if lv.physical2logical == nil {
+		lv.physical2logical = make(map[internal.UUID][]devextMapping)
+	}
+
+	// logical2physical
+	newChunk := chunkMapping{
+		LAddr:  laddr,
+		PAddrs: []QualifiedPhysicalAddr{paddr},
+		Size:   size,
+		Flags:  flags,
+	}
+	var logicalOverlaps []chunkMapping
+	for _, chunk := range lv.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 fmt.Errorf("(%p).AddMapping: %w", lv, err)
+		}
+	}
+
+	// physical2logical
+	newExt := devextMapping{
+		PAddr: paddr.Addr,
+		LAddr: laddr,
+		Size:  size,
+		Flags: flags,
+	}
+	var physicalOverlaps []devextMapping
+	for _, ext := range lv.physical2logical[paddr.Dev] {
+		switch newExt.cmpRange(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 fmt.Errorf("(%p).AddMapping: %w", lv, err)
+		}
+	}
+
+	// logical2physical
+	for _, chunk := range logicalOverlaps {
+		lv.logical2physical = util.RemoveAllFromSliceFunc(lv.logical2physical, func(otherChunk chunkMapping) bool {
+			return otherChunk.LAddr == chunk.LAddr
+		})
+	}
+	lv.logical2physical = append(lv.logical2physical, newChunk)
+	sort.Slice(lv.logical2physical, func(i, j int) bool {
+		return lv.logical2physical[i].LAddr < lv.logical2physical[j].LAddr
+	})
+
+	// physical2logical
+	for _, ext := range physicalOverlaps {
+		lv.physical2logical[paddr.Dev] = util.RemoveAllFromSlice(lv.physical2logical[paddr.Dev], ext)
+	}
+	lv.physical2logical[paddr.Dev] = append(lv.physical2logical[paddr.Dev], newExt)
+	sort.Slice(lv.physical2logical[paddr.Dev], func(i, j int) bool {
+		return lv.physical2logical[paddr.Dev][i].PAddr < lv.physical2logical[paddr.Dev][j].PAddr
+	})
+
+	// sanity check
+	//
+	// This is in-theory unnescessary, but that assumes that I
+	// made no mistakes in my algorithm above.
+	if err := lv.fsck(); err != nil {
+		return err
+	}
+
+	// done
+	return nil
+}
+
+func (lv *LogicalVolume) fsck() error {
+	physical2logical := make(map[internal.UUID][]devextMapping)
+	for _, chunk := range lv.logical2physical {
+		for _, stripe := range chunk.PAddrs {
+			if _, devOK := lv.uuid2pv[stripe.Dev]; !devOK {
+				return fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist",
+					lv, stripe.Dev)
+			}
+			physical2logical[stripe.Dev] = append(physical2logical[stripe.Dev], devextMapping{
+				PAddr: stripe.Addr,
+				LAddr: chunk.LAddr,
+				Size:  chunk.Size,
+				Flags: chunk.Flags,
+			})
+		}
+	}
+	for _, exts := range physical2logical {
+		sort.Slice(exts, func(i, j int) bool {
+			return exts[i].PAddr < exts[j].PAddr
+		})
+	}
+
+	if !reflect.DeepEqual(lv.physical2logical, physical2logical) {
+		return fmt.Errorf("(%p).fsck: skew between chunk tree and devext tree",
+			lv)
+	}
+
+	return nil
+}
+
+func (lv *LogicalVolume) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) {
+	paddrs = make(map[QualifiedPhysicalAddr]struct{})
+	maxlen = math.MaxInt64
+
+	for _, chunk := range lv.logical2physical {
+		low := chunk.LAddr
+		high := low.Add(chunk.Size)
+		if low <= laddr && laddr < high {
+			offsetWithinChunk := laddr.Sub(low)
+			maxlen = util.Min(maxlen, chunk.Size-offsetWithinChunk)
+			for _, stripe := range chunk.PAddrs {
+				paddrs[QualifiedPhysicalAddr{
+					Dev:  stripe.Dev,
+					Addr: stripe.Addr.Add(offsetWithinChunk),
+				}] = struct{}{}
+			}
+		}
+	}
+
+	return paddrs, maxlen
+}
+
+func (lv *LogicalVolume) UnResolve(paddr QualifiedPhysicalAddr) LogicalAddr {
+	for _, ext := range lv.physical2logical[paddr.Dev] {
+		low := ext.PAddr
+		high := low.Add(ext.Size)
+		if low <= paddr.Addr && paddr.Addr < high {
+			offsetWithinExt := paddr.Addr.Sub(low)
+			return ext.LAddr.Add(offsetWithinExt)
+		}
+	}
+	return -1
+}
+
+func (lv *LogicalVolume) ReadAt(dat []byte, laddr LogicalAddr) (int, error) {
+	done := 0
+	for done < len(dat) {
+		n, err := lv.maybeShortReadAt(dat[done:], laddr+LogicalAddr(done))
+		done += n
+		if err != nil {
+			return done, err
+		}
+	}
+	return done, nil
+}
+
+func (lv *LogicalVolume) maybeShortReadAt(dat []byte, laddr LogicalAddr) (int, error) {
+	paddrs, maxlen := lv.Resolve(laddr)
+	if len(paddrs) == 0 {
+		return 0, fmt.Errorf("read: could not map logical address %v", laddr)
+	}
+	if AddrDelta(len(dat)) > maxlen {
+		dat = dat[:maxlen]
+	}
+
+	buf := make([]byte, len(dat))
+	first := true
+	for paddr := range paddrs {
+		dev, ok := lv.uuid2pv[paddr.Dev]
+		if !ok {
+			return 0, fmt.Errorf("device=%v does not exist", paddr.Dev)
+		}
+		if _, err := dev.ReadAt(buf, paddr.Addr); err != nil {
+			return 0, fmt.Errorf("read device=%v paddr=%v: %w", paddr.Dev, paddr.Addr, err)
+		}
+		if first {
+			copy(dat, buf)
+		} else {
+			if !bytes.Equal(dat, buf) {
+				return 0, fmt.Errorf("inconsistent stripes at laddr=%v len=%v", laddr, len(dat))
+			}
+		}
+	}
+	return len(dat), nil
+}
+
+func (lv *LogicalVolume) WriteAt(dat []byte, laddr LogicalAddr) (int, error) {
+	done := 0
+	for done < len(dat) {
+		n, err := lv.maybeShortWriteAt(dat[done:], laddr+LogicalAddr(done))
+		done += n
+		if err != nil {
+			return done, err
+		}
+	}
+	return done, nil
+}
+
+func (lv *LogicalVolume) maybeShortWriteAt(dat []byte, laddr LogicalAddr) (int, error) {
+	paddrs, maxlen := lv.Resolve(laddr)
+	if len(paddrs) == 0 {
+		return 0, fmt.Errorf("write: could not map logical address %v", laddr)
+	}
+	if AddrDelta(len(dat)) > maxlen {
+		dat = dat[:maxlen]
+	}
+
+	for paddr := range paddrs {
+		dev, ok := lv.uuid2pv[paddr.Dev]
+		if !ok {
+			return 0, fmt.Errorf("device=%v does not exist", paddr.Dev)
+		}
+		if _, err := dev.WriteAt(dat, paddr.Addr); err != nil {
+			return 0, fmt.Errorf("write device=%v paddr=%v: %w", paddr.Dev, paddr.Addr, err)
+		}
+	}
+	return len(dat), nil
+}
diff --git a/pkg/btrfs/internal.go b/pkg/btrfs/internal.go
index e00e946..ad1e20b 100644
--- a/pkg/btrfs/internal.go
+++ b/pkg/btrfs/internal.go
@@ -15,7 +15,8 @@ type (
 
 	// complex types
 
-	Key  = internal.Key
-	Time = internal.Time
-	UUID = internal.UUID
+	Key                   = internal.Key
+	Time                  = internal.Time
+	UUID                  = internal.UUID
+	QualifiedPhysicalAddr = internal.QualifiedPhysicalAddr
 )
diff --git a/pkg/btrfs/internal/addr.go b/pkg/btrfs/internal/addr.go
index a3f41ed..09618a8 100644
--- a/pkg/btrfs/internal/addr.go
+++ b/pkg/btrfs/internal/addr.go
@@ -31,3 +31,15 @@ func (a LogicalAddr) Sub(b LogicalAddr) AddrDelta   { return AddrDelta(a - b) }
 
 func (a PhysicalAddr) Add(b AddrDelta) PhysicalAddr { return a + PhysicalAddr(b) }
 func (a LogicalAddr) Add(b AddrDelta) LogicalAddr   { return a + LogicalAddr(b) }
+
+type QualifiedPhysicalAddr struct {
+	Dev  UUID
+	Addr PhysicalAddr
+}
+
+func (a QualifiedPhysicalAddr) Cmp(b QualifiedPhysicalAddr) int {
+	if d := a.Dev.Cmp(b.Dev); d != 0 {
+		return d
+	}
+	return int(a.Addr - b.Addr)
+}
diff --git a/pkg/btrfs/internal/uuid.go b/pkg/btrfs/internal/uuid.go
index cb2c800..ebfd247 100644
--- a/pkg/btrfs/internal/uuid.go
+++ b/pkg/btrfs/internal/uuid.go
@@ -21,6 +21,15 @@ func (uuid UUID) String() string {
 	}, "-")
 }
 
+func (a UUID) Cmp(b UUID) int {
+	for i := range a {
+		if d := int(a[i]) - int(b[i]); d != 0 {
+			return d
+		}
+	}
+	return 0
+}
+
 func (uuid UUID) Format(f fmt.State, verb rune) {
 	util.FormatByteArrayStringer(uuid, uuid[:], f, verb)
 }
diff --git a/pkg/btrfs/io2_fs.go b/pkg/btrfs/io2_fs.go
index fd5f07a..208ef2c 100644
--- a/pkg/btrfs/io2_fs.go
+++ b/pkg/btrfs/io2_fs.go
@@ -1,279 +1,70 @@
 package btrfs
 
 import (
-	"bytes"
 	"fmt"
-	"math"
 	"reflect"
 
 	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
+	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol"
 	"lukeshu.com/btrfs-tools/pkg/util"
 )
 
 type FS struct {
-	Devices []*Device
-
-	uuid2dev         map[UUID]*Device
-	logical2physical [][]mapping
-	physical2logical map[UUID][]mapping
+	lv btrfsvol.LogicalVolume
 
 	cacheSuperblocks []*util.Ref[PhysicalAddr, Superblock]
 	cacheSuperblock  *util.Ref[PhysicalAddr, Superblock]
 }
 
+var _ util.File[LogicalAddr] = (*FS)(nil)
+
+func (fs *FS) AddDevice(dev *Device) error {
+	sb, err := dev.Superblock()
+	if err != nil {
+		return err
+	}
+	return fs.lv.AddPhysicalVolume(sb.Data.DevItem.DevUUID, dev)
+}
+
 func (fs *FS) Name() string {
+	if name := fs.lv.Name(); name != "" {
+		return name
+	}
 	sb, err := fs.Superblock()
 	if err != nil {
 		return fmt.Sprintf("fs_uuid=%v", "(unreadable)")
 	}
-	return fmt.Sprintf("fs_uuid=%v", sb.Data.FSUUID)
+	name := fmt.Sprintf("fs_uuid=%v", sb.Data.FSUUID)
+	fs.lv.SetName(name)
+	return name
 }
 
 func (fs *FS) Size() (LogicalAddr, error) {
-	var ret LogicalAddr
-	for _, dev := range fs.Devices {
-		sz, err := dev.Size()
-		if err != nil {
-			return 0, fmt.Errorf("file %q: %w", dev.Name(), err)
-		}
-		ret += LogicalAddr(sz)
-	}
-	return ret, nil
+	return fs.lv.Size()
 }
 
-// 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 (fs *FS) ReadAt(p []byte, off LogicalAddr) (int, error) {
+	return fs.lv.ReadAt(p, off)
 }
-
-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
+func (fs *FS) WriteAt(p []byte, off LogicalAddr) (int, error) {
+	return fs.lv.WriteAt(p, off)
 }
 
-// physical => logical
-type devextMapping struct {
-	PAddr QualifiedPhysicalAddr
-	LAddr LogicalAddr
-	Size  AddrDelta
-	Flags *btrfsitem.BlockGroupFlags
+func (fs *FS) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) {
+	return fs.lv.Resolve(laddr)
 }
 
-// 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 (fs *FS) UnResolve(paddr QualifiedPhysicalAddr) LogicalAddr {
+	return fs.lv.UnResolve(paddr)
 }
 
-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)
-		}
+func (fs *FS) Devices() []*Device {
+	untyped := fs.lv.PhysicalVolumes()
+	typed := make([]*Device, len(untyped))
+	for i := range untyped {
+		typed[i] = untyped[i].(*Device)
 	}
-	// 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
+	return typed
 }
 
 func (fs *FS) Superblocks() ([]*util.Ref[PhysicalAddr, Superblock], error) {
@@ -281,8 +72,8 @@ func (fs *FS) Superblocks() ([]*util.Ref[PhysicalAddr, Superblock], error) {
 		return fs.cacheSuperblocks, nil
 	}
 	var ret []*util.Ref[PhysicalAddr, Superblock]
-	for _, dev := range fs.Devices {
-		sbs, err := dev.Superblocks()
+	for _, dev := range fs.lv.PhysicalVolumes() {
+		sbs, err := dev.(*Device).Superblocks()
 		if err != nil {
 			return nil, fmt.Errorf("file %q: %w", dev.Name(), err)
 		}
@@ -330,10 +121,9 @@ func (fs *FS) Superblock() (*util.Ref[PhysicalAddr, Superblock], error) {
 }
 
 func (fs *FS) Init() error {
-	fs.uuid2dev = make(map[UUID]*Device, len(fs.Devices))
-	fs.chunks = nil
-	for _, dev := range fs.Devices {
-		sbs, err := dev.Superblocks()
+	fs.lv.ClearMappings()
+	for _, dev := range fs.lv.PhysicalVolumes() {
+		sbs, err := dev.(*Device).Superblocks()
 		if err != nil {
 			return fmt.Errorf("file %q: %w", dev.Name(), err)
 		}
@@ -351,27 +141,44 @@ func (fs *FS) Init() error {
 			}
 		}
 		sb := sbs[0]
-		if other, exists := fs.uuid2dev[sb.Data.DevItem.DevUUID]; exists {
-			return fmt.Errorf("file %q and file %q have the same device ID: %v",
-				other.Name(), dev.Name(), sb.Data.DevItem.DevUUID)
-		}
-		fs.uuid2dev[sb.Data.DevItem.DevUUID] = dev
 		syschunks, err := sb.Data.ParseSysChunkArray()
 		if err != nil {
 			return fmt.Errorf("file %q: %w", dev.Name(), err)
 		}
 		for _, chunk := range syschunks {
-			fs.chunks = append(fs.chunks, chunk)
+			for _, stripe := range chunk.Chunk.Stripes {
+				if err := fs.lv.AddMapping(
+					LogicalAddr(chunk.Key.Offset),
+					QualifiedPhysicalAddr{
+						Dev:  stripe.DeviceUUID,
+						Addr: stripe.Offset,
+					},
+					chunk.Chunk.Head.Size,
+					&chunk.Chunk.Head.Type,
+				); err != nil {
+					return fmt.Errorf("file %q: %w", dev.Name(), err)
+				}
+			}
 		}
 		if err := fs.WalkTree(sb.Data.ChunkTree, WalkTreeHandler{
 			Item: func(_ WalkTreePath, item Item) error {
 				if item.Head.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY {
 					return nil
 				}
-				fs.chunks = append(fs.chunks, SysChunk{
-					Key:   item.Head.Key,
-					Chunk: item.Body.(btrfsitem.Chunk),
-				})
+				body := item.Body.(btrfsitem.Chunk)
+				for _, stripe := range body.Stripes {
+					if err := fs.lv.AddMapping(
+						LogicalAddr(item.Head.Key.Offset),
+						QualifiedPhysicalAddr{
+							Dev:  stripe.DeviceUUID,
+							Addr: stripe.Offset,
+						},
+						body.Head.Size,
+						&body.Head.Type,
+					); err != nil {
+						return fmt.Errorf("file %q: %w", dev.Name(), err)
+					}
+				}
 				return nil
 			},
 		}); err != nil {
@@ -380,105 +187,3 @@ func (fs *FS) Init() error {
 	}
 	return nil
 }
-
-type QualifiedPhysicalAddr struct {
-	Dev  UUID
-	Addr PhysicalAddr
-}
-
-func (fs *FS) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) {
-	paddrs = make(map[QualifiedPhysicalAddr]struct{})
-	maxlen = math.MaxInt64
-
-	for _, chunk := range fs.chunks {
-		low := LogicalAddr(chunk.Key.Offset)
-		high := low.Add(chunk.Chunk.Head.Size)
-		if low <= laddr && laddr < high {
-			offsetWithinChunk := laddr.Sub(low)
-			maxlen = util.Min(maxlen, chunk.Chunk.Head.Size-offsetWithinChunk)
-			for _, stripe := range chunk.Chunk.Stripes {
-				paddrs[QualifiedPhysicalAddr{
-					Dev:  stripe.DeviceUUID,
-					Addr: stripe.Offset.Add(offsetWithinChunk),
-				}] = struct{}{}
-			}
-		}
-	}
-
-	return paddrs, maxlen
-}
-
-func (fs *FS) ReadAt(dat []byte, laddr LogicalAddr) (int, error) {
-	done := 0
-	for done < len(dat) {
-		n, err := fs.maybeShortReadAt(dat[done:], laddr+LogicalAddr(done))
-		done += n
-		if err != nil {
-			return done, err
-		}
-	}
-	return done, nil
-}
-
-func (fs *FS) maybeShortReadAt(dat []byte, laddr LogicalAddr) (int, error) {
-	paddrs, maxlen := fs.Resolve(laddr)
-	if len(paddrs) == 0 {
-		return 0, fmt.Errorf("read: could not map logical address %v", laddr)
-	}
-	if AddrDelta(len(dat)) > maxlen {
-		dat = dat[:maxlen]
-	}
-
-	buf := make([]byte, len(dat))
-	first := true
-	for paddr := range paddrs {
-		dev, ok := fs.uuid2dev[paddr.Dev]
-		if !ok {
-			return 0, fmt.Errorf("device=%v does not exist", paddr.Dev)
-		}
-		if _, err := dev.ReadAt(buf, paddr.Addr); err != nil {
-			return 0, fmt.Errorf("read device=%v paddr=%v: %w", paddr.Dev, paddr.Addr, err)
-		}
-		if first {
-			copy(dat, buf)
-		} else {
-			if !bytes.Equal(dat, buf) {
-				return 0, fmt.Errorf("inconsistent stripes at laddr=%v len=%v", laddr, len(dat))
-			}
-		}
-	}
-	return len(dat), nil
-}
-
-func (fs *FS) WriteAt(dat []byte, laddr LogicalAddr) (int, error) {
-	done := 0
-	for done < len(dat) {
-		n, err := fs.maybeShortWriteAt(dat[done:], laddr+LogicalAddr(done))
-		done += n
-		if err != nil {
-			return done, err
-		}
-	}
-	return done, nil
-}
-
-func (fs *FS) maybeShortWriteAt(dat []byte, laddr LogicalAddr) (int, error) {
-	paddrs, maxlen := fs.Resolve(laddr)
-	if len(paddrs) == 0 {
-		return 0, fmt.Errorf("write: could not map logical address %v", laddr)
-	}
-	if AddrDelta(len(dat)) > maxlen {
-		dat = dat[:maxlen]
-	}
-
-	for paddr := range paddrs {
-		dev, ok := fs.uuid2dev[paddr.Dev]
-		if !ok {
-			return 0, fmt.Errorf("device=%v does not exist", paddr.Dev)
-		}
-		if _, err := dev.WriteAt(dat, paddr.Addr); err != nil {
-			return 0, fmt.Errorf("write device=%v paddr=%v: %w", paddr.Dev, paddr.Addr, err)
-		}
-	}
-	return len(dat), nil
-}
diff --git a/pkg/util/generic.go b/pkg/util/generic.go
index 7ff2445..520d94e 100644
--- a/pkg/util/generic.go
+++ b/pkg/util/generic.go
@@ -13,12 +13,23 @@ func InSlice[T comparable](needle T, haystack []T) bool {
 	return false
 }
 
-func RemoveFromSlice[T comparable](haystack []T, needle T) []T {
+func RemoveAllFromSlice[T comparable](haystack []T, needle T) []T {
 	for i, straw := range haystack {
 		if needle == straw {
 			return append(
 				haystack[:i],
-				RemoveFromSlice(haystack[i+1], item)...)
+				RemoveAllFromSlice(haystack[i+1:], needle)...)
+		}
+	}
+	return haystack
+}
+
+func RemoveAllFromSliceFunc[T any](haystack []T, f func(T) bool) []T {
+	for i, straw := range haystack {
+		if f(straw) {
+			return append(
+				haystack[:i],
+				RemoveAllFromSliceFunc(haystack[i+1:], f)...)
 		}
 	}
 	return haystack