diff options
Diffstat (limited to 'pkg/btrfs/btrfsvol')
-rw-r--r-- | pkg/btrfs/btrfsvol/addr.go | 47 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/addr_test.go | 36 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/blockgroupflags.go | 51 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/chunk.go | 96 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/devext.go | 89 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/lvm.go | 355 |
6 files changed, 0 insertions, 674 deletions
diff --git a/pkg/btrfs/btrfsvol/addr.go b/pkg/btrfs/btrfsvol/addr.go deleted file mode 100644 index b426611..0000000 --- a/pkg/btrfs/btrfsvol/addr.go +++ /dev/null @@ -1,47 +0,0 @@ -package btrfsvol - -import ( - "fmt" - - "lukeshu.com/btrfs-tools/pkg/util" -) - -type ( - PhysicalAddr int64 - LogicalAddr int64 - AddrDelta int64 -) - -func formatAddr(addr int64, f fmt.State, verb rune) { - switch verb { - case 'v', 's', 'q': - str := fmt.Sprintf("%#016x", addr) - fmt.Fprintf(f, util.FmtStateString(f, verb), str) - default: - fmt.Fprintf(f, util.FmtStateString(f, verb), addr) - } -} - -func (a PhysicalAddr) Format(f fmt.State, verb rune) { formatAddr(int64(a), f, verb) } -func (a LogicalAddr) Format(f fmt.State, verb rune) { formatAddr(int64(a), f, verb) } -func (d AddrDelta) Format(f fmt.State, verb rune) { formatAddr(int64(d), f, verb) } - -func (a PhysicalAddr) Sub(b PhysicalAddr) AddrDelta { return AddrDelta(a - b) } -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 DeviceID uint64 - -type QualifiedPhysicalAddr struct { - Dev DeviceID - Addr PhysicalAddr -} - -func (a QualifiedPhysicalAddr) Cmp(b QualifiedPhysicalAddr) int { - if d := int(a.Dev - b.Dev); d != 0 { - return d - } - return int(a.Addr - b.Addr) -} diff --git a/pkg/btrfs/btrfsvol/addr_test.go b/pkg/btrfs/btrfsvol/addr_test.go deleted file mode 100644 index cfc5053..0000000 --- a/pkg/btrfs/btrfsvol/addr_test.go +++ /dev/null @@ -1,36 +0,0 @@ -package btrfsvol_test - -import ( - "fmt" - "testing" - - "github.com/stretchr/testify/assert" - - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" -) - -func TestAddrFormat(t *testing.T) { - t.Parallel() - type TestCase struct { - InputAddr btrfsvol.LogicalAddr - InputFmt string - Output string - } - addr := btrfsvol.LogicalAddr(0x3a41678000) - testcases := map[string]TestCase{ - "v": {InputAddr: addr, InputFmt: "%v", Output: "0x0000003a41678000"}, - "s": {InputAddr: addr, InputFmt: "%s", Output: "0x0000003a41678000"}, - "q": {InputAddr: addr, InputFmt: "%q", Output: `"0x0000003a41678000"`}, - "x": {InputAddr: addr, InputFmt: "%x", Output: "3a41678000"}, - "d": {InputAddr: addr, InputFmt: "%d", Output: "250205405184"}, - "neg": {InputAddr: -1, InputFmt: "%v", Output: "-0x000000000000001"}, - } - for tcName, tc := range testcases { - tc := tc - t.Run(tcName, func(t *testing.T) { - t.Parallel() - actual := fmt.Sprintf(tc.InputFmt, tc.InputAddr) - assert.Equal(t, tc.Output, actual) - }) - } -} diff --git a/pkg/btrfs/btrfsvol/blockgroupflags.go b/pkg/btrfs/btrfsvol/blockgroupflags.go deleted file mode 100644 index ba1610b..0000000 --- a/pkg/btrfs/btrfsvol/blockgroupflags.go +++ /dev/null @@ -1,51 +0,0 @@ -package btrfsvol - -import ( - "lukeshu.com/btrfs-tools/pkg/util" -) - -type BlockGroupFlags uint64 - -const ( - BLOCK_GROUP_DATA = BlockGroupFlags(1 << iota) - BLOCK_GROUP_SYSTEM - BLOCK_GROUP_METADATA - BLOCK_GROUP_RAID0 - BLOCK_GROUP_RAID1 - BLOCK_GROUP_DUP - BLOCK_GROUP_RAID10 - BLOCK_GROUP_RAID5 - BLOCK_GROUP_RAID6 - BLOCK_GROUP_RAID1C3 - BLOCK_GROUP_RAID1C4 - - 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) -) - -var blockGroupFlagNames = []string{ - "DATA", - "SYSTEM", - "METADATA", - - "RAID0", - "RAID1", - "DUP", - "RAID10", - "RAID5", - "RAID6", - "RAID1C3", - "RAID1C4", -} - -func (f BlockGroupFlags) Has(req BlockGroupFlags) bool { return f&req == req } -func (f BlockGroupFlags) String() string { - ret := util.BitfieldString(f, blockGroupFlagNames, util.HexNone) - if f&BLOCK_GROUP_RAID_MASK == 0 { - if ret == "" { - ret = "single" - } else { - ret += "|single" - } - } - return ret -} diff --git a/pkg/btrfs/btrfsvol/chunk.go b/pkg/btrfs/btrfsvol/chunk.go deleted file mode 100644 index 8e5c4db..0000000 --- a/pkg/btrfs/btrfsvol/chunk.go +++ /dev/null @@ -1,96 +0,0 @@ -package btrfsvol - -import ( - "fmt" - "sort" - - "lukeshu.com/btrfs-tools/pkg/util" -) - -// logical => []physical -type chunkMapping struct { - LAddr LogicalAddr - PAddrs []QualifiedPhysicalAddr - Size AddrDelta - SizeLocked bool - Flags *BlockGroupFlags -} - -type ChunkMapping = chunkMapping - -// 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), - } - for _, chunk := range chunks { - if chunk.SizeLocked { - ret.SizeLocked = true - if ret.Size != chunk.Size { - return chunkMapping{}, fmt.Errorf("member chunk has locked size=%v, but union would have size=%v", - chunk.Size, ret.Size) - } - } - } - // 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 = util.MapKeys(paddrs) - 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 deleted file mode 100644 index 8a69c7e..0000000 --- a/pkg/btrfs/btrfsvol/devext.go +++ /dev/null @@ -1,89 +0,0 @@ -package btrfsvol - -import ( - "fmt" - - "lukeshu.com/btrfs-tools/pkg/util" -) - -// physical => logical -type devextMapping struct { - PAddr PhysicalAddr - LAddr LogicalAddr - Size AddrDelta - SizeLocked bool - Flags *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), - } - for _, ext := range exts { - if ext.SizeLocked { - ret.SizeLocked = true - if ret.Size != ext.Size { - return devextMapping{}, fmt.Errorf("member devext has locked size=%v, but union would have size=%v", - ext.Size, ret.Size) - } - } - } - // 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 deleted file mode 100644 index c05b9dd..0000000 --- a/pkg/btrfs/btrfsvol/lvm.go +++ /dev/null @@ -1,355 +0,0 @@ -package btrfsvol - -import ( - "bytes" - "fmt" - "os" - "reflect" - - "lukeshu.com/btrfs-tools/pkg/rbtree" - "lukeshu.com/btrfs-tools/pkg/util" -) - -type LogicalVolume[PhysicalVolume util.File[PhysicalAddr]] struct { - name string - - id2pv map[DeviceID]PhysicalVolume - - logical2physical *rbtree.Tree[LogicalAddr, chunkMapping] - physical2logical map[DeviceID]*rbtree.Tree[PhysicalAddr, devextMapping] -} - -var _ util.File[LogicalAddr] = (*LogicalVolume[util.File[PhysicalAddr]])(nil) - -func (lv *LogicalVolume[PhysicalVolume]) init() { - if lv.id2pv == nil { - lv.id2pv = make(map[DeviceID]PhysicalVolume) - } - if lv.logical2physical == nil { - lv.logical2physical = &rbtree.Tree[LogicalAddr, chunkMapping]{ - KeyFn: func(chunk chunkMapping) LogicalAddr { - return chunk.LAddr - }, - } - } - if lv.physical2logical == nil { - lv.physical2logical = make(map[DeviceID]*rbtree.Tree[PhysicalAddr, devextMapping], len(lv.id2pv)) - } - for devid := range lv.id2pv { - if _, ok := lv.physical2logical[devid]; !ok { - lv.physical2logical[devid] = &rbtree.Tree[PhysicalAddr, devextMapping]{ - KeyFn: func(ext devextMapping) PhysicalAddr { - return ext.PAddr - }, - } - } - } -} - -func (lv *LogicalVolume[PhysicalVolume]) SetName(name string) { - lv.name = name -} - -func (lv *LogicalVolume[PhysicalVolume]) Name() string { - return lv.name -} - -func (lv *LogicalVolume[PhysicalVolume]) Size() (LogicalAddr, error) { - lv.init() - lastChunk := lv.logical2physical.Max() - if lastChunk == nil { - return 0, nil - } - return lastChunk.Value.LAddr.Add(lastChunk.Value.Size), nil -} - -func (lv *LogicalVolume[PhysicalVolume]) AddPhysicalVolume(id DeviceID, dev PhysicalVolume) error { - lv.init() - if other, exists := lv.id2pv[id]; exists { - return fmt.Errorf("(%p).AddPhysicalVolume: cannot add physical volume %q: already have physical volume %q with id=%v", - lv, dev.Name(), other.Name(), id) - } - lv.id2pv[id] = dev - lv.physical2logical[id] = &rbtree.Tree[PhysicalAddr, devextMapping]{ - KeyFn: func(ext devextMapping) PhysicalAddr { - return ext.PAddr - }, - } - return nil -} - -func (lv *LogicalVolume[PhysicalVolume]) PhysicalVolumes() map[DeviceID]PhysicalVolume { - dup := make(map[DeviceID]PhysicalVolume, len(lv.id2pv)) - for k, v := range lv.id2pv { - dup[k] = v - } - return dup -} - -func (lv *LogicalVolume[PhysicalVolume]) ClearMappings() { - lv.logical2physical = nil - lv.physical2logical = nil -} - -type Mapping struct { - LAddr LogicalAddr - PAddr QualifiedPhysicalAddr - Size AddrDelta - SizeLocked bool - Flags *BlockGroupFlags -} - -func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error { - lv.init() - // sanity check - if _, haveDev := lv.id2pv[m.PAddr.Dev]; !haveDev { - return fmt.Errorf("(%p).AddMapping: do not have a physical volume with id=%v", - lv, m.PAddr.Dev) - } - - // logical2physical - newChunk := chunkMapping{ - LAddr: m.LAddr, - PAddrs: []QualifiedPhysicalAddr{m.PAddr}, - Size: m.Size, - SizeLocked: m.SizeLocked, - Flags: m.Flags, - } - logicalOverlaps := lv.logical2physical.SearchRange(newChunk.cmpRange) - var err error - newChunk, err = newChunk.union(logicalOverlaps...) - if err != nil { - return fmt.Errorf("(%p).AddMapping: %w", lv, err) - } - - // physical2logical - newExt := devextMapping{ - PAddr: m.PAddr.Addr, - LAddr: m.LAddr, - Size: m.Size, - SizeLocked: m.SizeLocked, - Flags: m.Flags, - } - physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.cmpRange) - newExt, err = newExt.union(physicalOverlaps...) - if err != nil { - return fmt.Errorf("(%p).AddMapping: %w", lv, err) - } - - // optimize - if len(logicalOverlaps) == 1 && reflect.DeepEqual(newChunk, logicalOverlaps[0]) && - len(physicalOverlaps) == 1 && reflect.DeepEqual(newExt, physicalOverlaps[0]) { - return nil - } - - // logical2physical - for _, chunk := range logicalOverlaps { - lv.logical2physical.Delete(chunk.LAddr) - } - lv.logical2physical.Insert(newChunk) - - // physical2logical - for _, ext := range physicalOverlaps { - lv.physical2logical[m.PAddr.Dev].Delete(ext.PAddr) - } - lv.physical2logical[m.PAddr.Dev].Insert(newExt) - - // sanity check - // - // This is in-theory unnescessary, but that assumes that I - // made no mistakes in my algorithm above. - if os.Getenv("PARANOID") != "" { - if err := lv.fsck(); err != nil { - return err - } - } - - // done - return nil -} - -func (lv *LogicalVolume[PhysicalVolume]) fsck() error { - physical2logical := make(map[DeviceID]*rbtree.Tree[PhysicalAddr, devextMapping]) - if err := lv.logical2physical.Walk(func(node *rbtree.Node[chunkMapping]) error { - 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", - lv, stripe.Dev) - } - if _, exists := physical2logical[stripe.Dev]; !exists { - physical2logical[stripe.Dev] = &rbtree.Tree[PhysicalAddr, devextMapping]{ - KeyFn: func(ext devextMapping) PhysicalAddr { - return ext.PAddr - }, - } - } - physical2logical[stripe.Dev].Insert(devextMapping{ - PAddr: stripe.Addr, - LAddr: chunk.LAddr, - Size: chunk.Size, - Flags: chunk.Flags, - }) - } - return nil - }); err != nil { - return err - } - - if len(lv.physical2logical) != len(physical2logical) { - return fmt.Errorf("(%p).fsck: skew between chunk tree and devext tree", - lv) - } - for devid := range lv.physical2logical { - if !lv.physical2logical[devid].Equal(physical2logical[devid]) { - return fmt.Errorf("(%p).fsck: skew between chunk tree and devext tree", - lv) - } - } - - return nil -} - -func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { - var ret []Mapping - _ = lv.logical2physical.Walk(func(node *rbtree.Node[chunkMapping]) error { - chunk := node.Value - var flags *BlockGroupFlags - if chunk.Flags != nil { - val := *chunk.Flags - flags = &val - } - for _, slice := range chunk.PAddrs { - ret = append(ret, Mapping{ - LAddr: chunk.LAddr, - PAddr: slice, - Size: chunk.Size, - Flags: flags, - }) - } - return nil - }) - return ret -} - -func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) { - node := lv.logical2physical.Search(func(chunk chunkMapping) int { - return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk) - }) - if node == nil { - return nil, 0 - } - - chunk := node.Value - - offsetWithinChunk := laddr.Sub(chunk.LAddr) - paddrs = make(map[QualifiedPhysicalAddr]struct{}) - 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[PhysicalVolume]) ResolveAny(laddr LogicalAddr, size AddrDelta) (LogicalAddr, QualifiedPhysicalAddr) { - node := lv.logical2physical.Search(func(chunk chunkMapping) int { - return chunkMapping{LAddr: laddr, Size: size}.cmpRange(chunk) - }) - if node == nil { - return -1, QualifiedPhysicalAddr{0, -1} - } - return node.Value.LAddr, node.Value.PAddrs[0] -} - -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) - }) - if node == nil { - return -1 - } - - ext := node.Value - - offsetWithinExt := paddr.Addr.Sub(ext.PAddr) - return ext.LAddr.Add(offsetWithinExt) -} - -func (lv *LogicalVolume[PhysicalVolume]) 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[PhysicalVolume]) 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.id2pv[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[PhysicalVolume]) 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[PhysicalVolume]) 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.id2pv[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 -} |