better volume!

1 files changed, 65 insertions, 360 deletions

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
-}