From 502cdc72771de93ce41e2a00bc201fc488603f59 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 26 Jun 2022 19:55:49 -0600 Subject: better volume! --- pkg/btrfs/btrfsvol/chunk.go | 88 ++++++++++++ pkg/btrfs/btrfsvol/devext.go | 80 +++++++++++ pkg/btrfs/btrfsvol/lvm.go | 310 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 478 insertions(+) create mode 100644 pkg/btrfs/btrfsvol/chunk.go create mode 100644 pkg/btrfs/btrfsvol/devext.go create mode 100644 pkg/btrfs/btrfsvol/lvm.go (limited to 'pkg/btrfs/btrfsvol') 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 +} -- cgit v1.2.3-2-g168b