diff options
-rw-r--r-- | cmd/btrfs-dbg/main.go | 16 | ||||
-rw-r--r-- | cmd/btrfs-dump-tree/main.go | 11 | ||||
-rw-r--r-- | cmd/btrfs-fsck/main.go | 10 | ||||
-rw-r--r-- | cmd/btrfs-fsck/pass1.go | 4 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/chunk.go | 88 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/devext.go | 80 | ||||
-rw-r--r-- | pkg/btrfs/btrfsvol/lvm.go | 310 | ||||
-rw-r--r-- | pkg/btrfs/internal.go | 7 | ||||
-rw-r--r-- | pkg/btrfs/internal/addr.go | 12 | ||||
-rw-r--r-- | pkg/btrfs/internal/uuid.go | 9 | ||||
-rw-r--r-- | pkg/btrfs/io2_fs.go | 425 | ||||
-rw-r--r-- | pkg/util/generic.go | 15 |
12 files changed, 599 insertions, 388 deletions
diff --git a/cmd/btrfs-dbg/main.go b/cmd/btrfs-dbg/main.go index 62b005c..3f30915 100644 --- a/cmd/btrfs-dbg/main.go +++ b/cmd/btrfs-dbg/main.go @@ -32,15 +32,15 @@ func Main(imgfilename string) (err error) { defer func() { maybeSetErr(fh.Close()) }() - fs := &btrfs.FS{ - Devices: []*btrfs.Device{ - { - File: fh, - }, - }, + dev := &btrfs.Device{ + File: fh, + } + fs := new(btrfs.FS) + if err := fs.AddDevice(dev); err != nil { + return err } - superblocks, err := fs.Devices[0].Superblocks() + superblocks, err := fs.Superblocks() if err != nil { return err } @@ -61,7 +61,7 @@ func Main(imgfilename string) (err error) { } spew.Dump(syschunks) - if err := btrfsmisc.ScanForNodes(fs.Devices[0], superblocks[0].Data, func(nodeRef *util.Ref[btrfs.PhysicalAddr, btrfs.Node], err error) { + if err := btrfsmisc.ScanForNodes(dev, superblocks[0].Data, func(nodeRef *util.Ref[btrfs.PhysicalAddr, btrfs.Node], err error) { if err != nil { fmt.Println(err) } else { diff --git a/cmd/btrfs-dump-tree/main.go b/cmd/btrfs-dump-tree/main.go index 3c7bcda..9c8e4c5 100644 --- a/cmd/btrfs-dump-tree/main.go +++ b/cmd/btrfs-dump-tree/main.go @@ -32,14 +32,11 @@ func Main(imgfilename string) (err error) { defer func() { maybeSetErr(fh.Close()) }() - fs := &btrfs.FS{ - Devices: []*btrfs.Device{ - { - File: fh, - }, - }, - } + fs := new(btrfs.FS) + if err := fs.AddDevice(&btrfs.Device{File: fh}); err != nil { + return err + } if err := fs.Init(); err != nil { fmt.Printf("(error) %v\n", err) } diff --git a/cmd/btrfs-fsck/main.go b/cmd/btrfs-fsck/main.go index c4bfc75..0083bd9 100644 --- a/cmd/btrfs-fsck/main.go +++ b/cmd/btrfs-fsck/main.go @@ -28,12 +28,10 @@ func Main(imgfilename string) (err error) { defer func() { maybeSetErr(fh.Close()) }() - fs := &btrfs.FS{ - Devices: []*btrfs.Device{ - { - File: fh, - }, - }, + + fs := new(btrfs.FS) + if err := fs.AddDevice(&btrfs.Device{File: fh}); err != nil { + return err } superblock, err := pass0(fs) diff --git a/cmd/btrfs-fsck/pass1.go b/cmd/btrfs-fsck/pass1.go index 4507313..734ee40 100644 --- a/cmd/btrfs-fsck/pass1.go +++ b/cmd/btrfs-fsck/pass1.go @@ -44,7 +44,7 @@ func pass1(fs *btrfs.FS, superblock *util.Ref[btrfs.PhysicalAddr, btrfs.Superblo Size btrfs.AddrDelta Stripes []btrfsitem.ChunkStripe }) - for _, dev := range fs.Devices { + for _, dev := range fs.Devices() { fmt.Printf("Pass 1: ... dev[%q] scanning for nodes...\n", dev.Name()) devResult, err := pass1ScanOneDev(dev, superblock.Data) if err != nil { @@ -505,7 +505,7 @@ func pass1WriteReconstructedChunks( }, } - for _, dev := range fs.Devices { + for _, dev := range fs.Devices() { superblock, _ := dev.Superblock() reconstructedNode.Data.BodyLeaf = append(reconstructedNode.Data.BodyLeaf, btrfs.Item{ Head: btrfs.ItemHeader{ 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 |