From e6b7c243462b1412390d0048dafe3430d07c05be Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 26 Jun 2022 17:44:10 -0600 Subject: wip better vol --- pkg/btrfs/io2_fs.go | 240 +++++++++++++++++++++++++++++++++++++++++++++++++++- pkg/util/generic.go | 11 +++ 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 -- cgit v1.2.3-2-g168b