From 01704502c27f6247523f4d227c94f9311ec4acb4 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 25 May 2022 12:18:03 -0600 Subject: wip --- pkg/binstruct/l1.go | 18 +++-- pkg/btrfs/fsck.go | 4 +- pkg/btrfs/io_device.go | 22 +++--- pkg/btrfs/io_fs.go | 172 ++++++++++++++++++++++++++++++++++++++++--- pkg/btrfs/io_ref.go | 16 ++-- pkg/btrfs/types_bitfields.go | 66 ++++++++++++++--- pkg/btrfs/types_objid.go | 42 +++++------ pkg/btrfs/types_structs.go | 43 +++++++++-- 8 files changed, 311 insertions(+), 72 deletions(-) (limited to 'pkg') diff --git a/pkg/binstruct/l1.go b/pkg/binstruct/l1.go index d90ecba..367dd28 100644 --- a/pkg/binstruct/l1.go +++ b/pkg/binstruct/l1.go @@ -7,9 +7,13 @@ import ( ) type Marshaler interface { + BinarySize() int64 MarshalBinary() []byte +} + +type Unmarshaler interface { + Marshaler UnmarshalBinary([]byte) - BinarySize() int64 } type handler interface { @@ -26,9 +30,9 @@ func (_ extHandler) Marshal(val interface{}) []byte { return val.(Marshaler).MarshalBinary() } func (e extHandler) Unmarshal(dat []byte) interface{} { - val := reflect.New(e.typ).Elem().Interface().(Marshaler) - val.UnmarshalBinary(dat) - return val + valPtr := reflect.New(e.typ).Interface().(Unmarshaler) + valPtr.UnmarshalBinary(dat) + return reflect.ValueOf(valPtr).Elem().Interface() } func (e extHandler) Size() int64 { val := reflect.New(e.typ).Elem().Interface().(Marshaler) @@ -53,7 +57,9 @@ func convert[T any](in interface{}) T { } func genHandler(typ reflect.Type) (handler, error) { - if _, ok := reflect.New(typ).Elem().Interface().(Marshaler); ok { + _, marOK := reflect.New(typ).Elem().Interface().(Marshaler) + _, unmarOK := reflect.New(typ).Interface().(Unmarshaler) + if marOK && unmarOK { return extHandler{ typ: typ, }, nil @@ -112,7 +118,7 @@ func genHandler(typ reflect.Type) (handler, error) { case reflect.Int8: return primitive{ unmarshal: func(dat []byte) interface{} { return int8(dat[0]) }, - marshal: func(val interface{}) []byte { return []byte{uint8(convert[int8](val))}}, + marshal: func(val interface{}) []byte { return []byte{uint8(convert[int8](val))} }, size: 1, }, nil case reflect.Int16: diff --git a/pkg/btrfs/fsck.go b/pkg/btrfs/fsck.go index d31735e..b6c80e5 100644 --- a/pkg/btrfs/fsck.go +++ b/pkg/btrfs/fsck.go @@ -21,7 +21,7 @@ func ScanForNodes(dev *Device, sb Superblock) error { } nodeBuf := make([]byte, sb.NodeSize) - for pos := int64(0); pos+int64(sb.SectorSize) < devSize; pos += int64(sb.SectorSize) { + for pos := PhysicalAddr(0); pos+PhysicalAddr(sb.SectorSize) < devSize; pos += PhysicalAddr(sb.SectorSize) { if inSlice(pos, superblockAddrs) { fmt.Printf("sector@%d is a superblock\n", pos) continue @@ -45,7 +45,7 @@ func ScanForNodes(dev *Device, sb Superblock) error { fmt.Printf("node@%d: physical_addr=0x%0X logical_addr=0x%0X generation=%d owner=%v level=%d\n", pos, pos, nodeHeader.Addr, nodeHeader.Generation, nodeHeader.Owner, nodeHeader.Level) - pos += int64(sb.NodeSize) - int64(sb.SectorSize) + pos += PhysicalAddr(sb.NodeSize) - PhysicalAddr(sb.SectorSize) } return nil diff --git a/pkg/btrfs/io_device.go b/pkg/btrfs/io_device.go index 26450b7..042c9f2 100644 --- a/pkg/btrfs/io_device.go +++ b/pkg/btrfs/io_device.go @@ -9,21 +9,25 @@ type Device struct { *os.File } -func (dev Device) Size() (int64, error) { +func (dev Device) Size() (PhysicalAddr, error) { fi, err := dev.Stat() if err != nil { return 0, err } - return fi.Size(), nil + return PhysicalAddr(fi.Size()), nil } -var superblockAddrs = []int64{ +var superblockAddrs = []PhysicalAddr{ 0x00_0001_0000, // 64KiB 0x00_0400_0000, // 64MiB 0x40_0000_0000, // 256GiB } -func (dev *Device) Superblocks() ([]Ref[Superblock], error) { +func (dev *Device) ReadAt(dat []byte, paddr PhysicalAddr) (int, error) { + return dev.File.ReadAt(dat, int64(paddr)) +} + +func (dev *Device) Superblocks() ([]Ref[PhysicalAddr, Superblock], error) { const superblockSize = 0x1000 sz, err := dev.Size() @@ -31,12 +35,12 @@ func (dev *Device) Superblocks() ([]Ref[Superblock], error) { return nil, err } - var ret []Ref[Superblock] + var ret []Ref[PhysicalAddr, Superblock] for i, addr := range superblockAddrs { if addr+superblockSize <= sz { - superblock := Ref[Superblock]{ - dev: dev, - addr: addr, + superblock := Ref[PhysicalAddr, Superblock]{ + File: dev, + Addr: addr, } if err := superblock.Read(); err != nil { return nil, fmt.Errorf("superblock %d: %w", i, err) @@ -50,7 +54,7 @@ func (dev *Device) Superblocks() ([]Ref[Superblock], error) { return ret, nil } -func (dev *Device) superblock() (ret Ref[Superblock], err error) { +func (dev *Device) Superblock() (ret Ref[PhysicalAddr, Superblock], err error) { sbs, err := dev.Superblocks() if err != nil { return ret, err diff --git a/pkg/btrfs/io_fs.go b/pkg/btrfs/io_fs.go index 52f742a..5dee6dc 100644 --- a/pkg/btrfs/io_fs.go +++ b/pkg/btrfs/io_fs.go @@ -4,6 +4,8 @@ import ( "bytes" "fmt" "reflect" + + "lukeshu.com/btrfs-tools/pkg/binstruct" ) type FS struct { @@ -14,6 +16,71 @@ type FS struct { chunks []SysChunk } +func (fs *FS) Name() string { + sb, err := fs.Superblock() + if err != nil { + return fmt.Sprintf("fs_uuid=%s", "(unreadable)") + } + return fmt.Sprintf("fs_uuid=%s", sb.Data.FSUUID) +} + +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 +} + +func (fs *FS) Superblocks() ([]Ref[PhysicalAddr, Superblock], error) { + var ret []Ref[PhysicalAddr, Superblock] + for _, dev := range fs.Devices { + sbs, err := dev.Superblocks() + if err != nil { + return nil, fmt.Errorf("file %q: %w", dev.Name(), err) + } + ret = append(ret, sbs...) + } + return ret, nil +} + +func (fs *FS) Superblock() (ret Ref[PhysicalAddr, Superblock], err error) { + sbs, err := fs.Superblocks() + if err != nil { + return ret, err + } + + fname := "" + sbi := 0 + for i, sb := range sbs { + if sb.File.Name() != fname { + fname = sb.File.Name() + sbi = 0 + } else { + sbi++ + } + + if err := sb.Data.ValidateChecksum(); err != nil { + return ret, fmt.Errorf("file %q superblock %d: %w", sb.File.Name(), sbi, err) + } + if i > 0 { + // This is probably wrong, but lots of my + // multi-device code is probably wrong. + if !sb.Data.Equal(sbs[0].Data) { + return ret, fmt.Errorf("file %q superblock %d and file %q superblock %d disagree", + sbs[0].File.Name(), 0, + sb.File.Name(), sbi) + } + } + } + + return sbs[0], nil +} + func (fs *FS) init() error { if fs.uuid2dev != nil { return fs.initErr @@ -58,19 +125,19 @@ func (fs *FS) init() error { return nil } -func (fs *FS) ReadLogicalFull(laddr LogicalAddr, dat []byte) error { - done := LogicalAddr(0) - for done < LogicalAddr(len(dat)) { - n, err := fs.readLogicalMaybeShort(laddr+done, dat[done:]) +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 err + return done, err } - done += LogicalAddr(n) } - return nil + return done, nil } -func (fs *FS) readLogicalMaybeShort(laddr LogicalAddr, dat []byte) (int, error) { +func (fs *FS) maybeShortReadAt(dat []byte, laddr LogicalAddr) (int, error) { if err := fs.init(); err != nil { return 0, err } @@ -108,7 +175,7 @@ func (fs *FS) readLogicalMaybeShort(laddr LogicalAddr, dat []byte) (int, error) if !ok { return 0, fmt.Errorf("device=%s does not exist", paddr.Dev) } - if _, err := dev.ReadAt(buf, int64(paddr.Addr)); err != nil { + if _, err := dev.ReadAt(buf, paddr.Addr); err != nil { return 0, fmt.Errorf("read device=%s paddr=%v: %w", paddr.Dev, paddr.Addr, err) } if first { @@ -121,3 +188,90 @@ func (fs *FS) readLogicalMaybeShort(laddr LogicalAddr, dat []byte) (int, error) } return len(dat), nil } + +func (fs *FS) ReadNode(addr LogicalAddr) (Node, error) { + sb, err := fs.Superblock() + if err != nil { + return nil, err + } + + nodeBuf := make([]byte, sb.Data.NodeSize) + if _, err := fs.ReadAt(nodeBuf, addr); err != nil { + return nil, err + } + + var nodeHeader NodeHeader + if err := binstruct.Unmarshal(nodeBuf, &nodeHeader); err != nil { + return nil, fmt.Errorf("node@%d: %w", addr, err) + } + + if !nodeHeader.MetadataUUID.Equal(sb.Data.EffectiveMetadataUUID()) { + return nil, fmt.Errorf("node@%d: does not look like a node", addr) + } + + stored := nodeHeader.Checksum + calced := CRC32c(nodeBuf[0x20:]) + if !calced.Equal(stored) { + return nil, fmt.Errorf("node@%d: checksum mismatch: stored=%s calculated=%s", + addr, stored, calced) + } + + nodeHeader.Size = sb.Data.NodeSize + + if nodeHeader.Level > 0 { + // internal node + nodeHeader.MaxItems = (sb.Data.NodeSize - 0x65) / 0x21 + ret := &InternalNode{ + Header: Ref[LogicalAddr, NodeHeader]{ + File: fs, + Addr: addr, + Data: nodeHeader, + }, + Body: nil, + } + for i := uint32(0); i < nodeHeader.NumItems; i++ { + itemOff := 0x65 + (0x21 * int(i)) + var item KeyPointer + if err := binstruct.Unmarshal(nodeBuf[itemOff:], &item); err != nil { + return nil, fmt.Errorf("node@%d (internal): item %d: %w", addr, i, err) + } + ret.Body = append(ret.Body, Ref[LogicalAddr, KeyPointer]{ + File: fs, + Addr: addr + LogicalAddr(itemOff), + Data: item, + }) + } + return ret, nil + } else { + // leaf node + nodeHeader.MaxItems = (sb.Data.NodeSize - 0x65) / 0x19 + ret := &LeafNode{ + Header: Ref[LogicalAddr, NodeHeader]{ + File: fs, + Addr: addr, + Data: nodeHeader, + }, + Body: nil, + } + for i := uint32(0); i < nodeHeader.NumItems; i++ { + itemOff := 0x65 + (0x19 * int(i)) + var item Item + if err := binstruct.Unmarshal(nodeBuf[itemOff:], &item); err != nil { + return nil, fmt.Errorf("node@%d (leaf): item %d: %w", addr, i, err) + } + dataOff := 0x65 + int(item.DataOffset) + dataSize := int(item.DataSize) + item.Data = Ref[LogicalAddr, []byte]{ + File: fs, + Addr: addr + LogicalAddr(dataOff), + Data: nodeBuf[dataOff : dataOff+dataSize], + } + ret.Body = append(ret.Body, Ref[LogicalAddr, Item]{ + File: fs, + Addr: addr + LogicalAddr(itemOff), + Data: item, + }) + } + return ret, nil + } +} diff --git a/pkg/btrfs/io_ref.go b/pkg/btrfs/io_ref.go index aa37fee..a91b691 100644 --- a/pkg/btrfs/io_ref.go +++ b/pkg/btrfs/io_ref.go @@ -4,19 +4,25 @@ import ( "lukeshu.com/btrfs-tools/pkg/binstruct" ) -type Ref[T any] struct { - dev *Device - addr int64 +type File[A ~int64] interface { + Name() string + Size() (A, error) + ReadAt(p []byte, off A) (n int, err error) +} + +type Ref[A ~int64, T any] struct { + File File[A] + Addr A Data T } -func (r *Ref[T]) Read() error { +func (r *Ref[A, T]) Read() error { size, err := binstruct.Size(r.Data) if err != nil { return err } buf := make([]byte, size) - if _, err := r.dev.ReadAt(buf, r.addr); err != nil { + if _, err := r.File.ReadAt(buf, r.Addr); err != nil { return err } return binstruct.Unmarshal(buf, &r.Data) diff --git a/pkg/btrfs/types_bitfields.go b/pkg/btrfs/types_bitfields.go index ead4b0f..5c09b0a 100644 --- a/pkg/btrfs/types_bitfields.go +++ b/pkg/btrfs/types_bitfields.go @@ -1,8 +1,11 @@ package btrfs import ( + "encoding/binary" "fmt" "strings" + + "lukeshu.com/btrfs-tools/pkg/binstruct" ) func bitfieldString[T ~uint8 | ~uint16 | ~uint32 | ~uint64](bitfield T, bitnames []string) string { @@ -10,20 +13,25 @@ func bitfieldString[T ~uint8 | ~uint16 | ~uint32 | ~uint64](bitfield T, bitnames return "0" } var out strings.Builder - fmt.Fprintf(&out, "(0x%0X)", uint64(bitfield)) - rest := bitfield - sep := ' ' - for i := 0; rest != 0; i++ { - if rest&(1< BTRFS_LAST_FREE_OBJECTID { names := map[ObjID]string{ - BTRFS_BALANCE_OBJECTID: "BTRFS_BALANCE_OBJECTID", - BTRFS_ORPHAN_OBJECTID: "BTRFS_ORPHAN_OBJECTID", - BTRFS_TREE_LOG_OBJECTID: "BTRFS_TREE_LOG_OBJECTID", - BTRFS_TREE_LOG_FIXUP_OBJECTID: "BTRFS_TREE_LOG_FIXUP_OBJECTID", - BTRFS_TREE_RELOC_OBJECTID: "BTRFS_TREE_RELOC_OBJECTID", - BTRFS_DATA_RELOC_TREE_OBJECTID: "BTRFS_DATA_RELOC_TREE_OBJECTID", - BTRFS_EXTENT_CSUM_OBJECTID: "BTRFS_EXTENT_CSUM_OBJECTID", - BTRFS_FREE_SPACE_OBJECTID: "BTRFS_FREE_SPACE_OBJECTID", - BTRFS_FREE_INO_OBJECTID: "BTRFS_FREE_INO_OBJECTID", - BTRFS_MULTIPLE_OBJECTIDS: "BTRFS_MULTIPLE_OBJECTIDS", + BTRFS_BALANCE_OBJECTID: "BALANCE", + BTRFS_ORPHAN_OBJECTID: "ORPHAN", + BTRFS_TREE_LOG_OBJECTID: "TREE_LOG", + BTRFS_TREE_LOG_FIXUP_OBJECTID: "TREE_LOG_FIXUP", + BTRFS_TREE_RELOC_OBJECTID: "TREE_RELOC", + BTRFS_DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE", + BTRFS_EXTENT_CSUM_OBJECTID: "EXTENT_CSUM", + BTRFS_FREE_SPACE_OBJECTID: "FREE_SPACE", + BTRFS_FREE_INO_OBJECTID: "FREE_INO", + BTRFS_MULTIPLE_OBJECTIDS: "MULTIPLE", } if name, ok := names[id]; ok { return name @@ -77,17 +77,17 @@ type TreeObjID ObjID func (id TreeObjID) String() string { names := map[ObjID]string{ - BTRFS_ROOT_TREE_OBJECTID: "BTRFS_ROOT_TREE_OBJECTID", - BTRFS_EXTENT_TREE_OBJECTID: "BTRFS_EXTENT_TREE_OBJECTID", - BTRFS_CHUNK_TREE_OBJECTID: "BTRFS_CHUNK_TREE_OBJECTID", - BTRFS_DEV_TREE_OBJECTID: "BTRFS_DEV_TREE_OBJECTID", - BTRFS_FS_TREE_OBJECTID: "BTRFS_FS_TREE_OBJECTID", - BTRFS_ROOT_TREE_DIR_OBJECTID: "BTRFS_ROOT_TREE_DIR_OBJECTID", - BTRFS_CSUM_TREE_OBJECTID: "BTRFS_CSUM_TREE_OBJECTID", - BTRFS_QUOTA_TREE_OBJECTID: "BTRFS_QUOTA_TREE_OBJECTID", - BTRFS_UUID_TREE_OBJECTID: "BTRFS_UUID_TREE_OBJECTID", - BTRFS_FREE_SPACE_TREE_OBJECTID: "BTRFS_FREE_SPACE_TREE_OBJECTID", - BTRFS_BLOCK_GROUP_TREE_OBJECTID: "BTRFS_BLOCK_GROUP_TREE_OBJECTID", + BTRFS_ROOT_TREE_OBJECTID: "ROOT_TREE", + BTRFS_EXTENT_TREE_OBJECTID: "EXTENT_TREE", + BTRFS_CHUNK_TREE_OBJECTID: "CHUNK_TREE", + BTRFS_DEV_TREE_OBJECTID: "DEV_TREE", + BTRFS_FS_TREE_OBJECTID: "FS_TREE", + BTRFS_ROOT_TREE_DIR_OBJECTID: "ROOT_TREE_DIR", + BTRFS_CSUM_TREE_OBJECTID: "CSUM_TREE", + BTRFS_QUOTA_TREE_OBJECTID: "QUOTA_TREE", + BTRFS_UUID_TREE_OBJECTID: "UUID_TREE", + BTRFS_FREE_SPACE_TREE_OBJECTID: "FREE_SPACE_TREE", + BTRFS_BLOCK_GROUP_TREE_OBJECTID: "BLOCK_GROUP_TREE", } if name, ok := names[ObjID(id)]; ok { return name diff --git a/pkg/btrfs/types_structs.go b/pkg/btrfs/types_structs.go index 6ab3b93..5063d86 100644 --- a/pkg/btrfs/types_structs.go +++ b/pkg/btrfs/types_structs.go @@ -77,9 +77,9 @@ type Superblock struct { NumGlobalRoots uint64 `bin:"off=24b, siz=8"` // FeatureIncompatExtentTreeV2 - BlockGroupRoot ObjID `bin:"off=253, siz=8"` - BlockGroupRootGeneration Generation `bin:"off=25b, siz=8"` - BlockGroupRootLevel uint8 `bin:"off=263, siz=1"` + BlockGroupRoot LogicalAddr `bin:"off=253, siz=8"` + BlockGroupRootGeneration Generation `bin:"off=25b, siz=8"` + BlockGroupRootLevel uint8 `bin:"off=263, siz=1"` Reserved [199]byte `bin:"off=264, siz=c7"` // future expansion @@ -195,22 +195,34 @@ type RootBackup struct { binstruct.End `bin:"off=a8"` } +type Node interface { + GetNodeHeader() Ref[LogicalAddr, NodeHeader] +} + type NodeHeader struct { Checksum CSum `bin:"off=0, siz=20"` // Checksum of everything after this field (from 20 to the end of the node) MetadataUUID UUID `bin:"off=20, siz=10"` // FS UUID Addr LogicalAddr `bin:"off=30, siz=8"` // Logical address of this node - Flags uint64 `bin:"off=38, siz=8"` // Flags + Flags NodeFlags `bin:"off=38, siz=7"` + BackrefRev uint8 `bin:"off=3f, siz=1"` ChunkTreeUUID UUID `bin:"off=40, siz=10"` // Chunk tree UUID Generation Generation `bin:"off=50, siz=8"` // Generation Owner TreeObjID `bin:"off=58, siz=8"` // The ID of the tree that contains this node NumItems uint32 `bin:"off=60, siz=4"` // Number of items Level uint8 `bin:"off=64, siz=1"` // Level (0 for leaf nodes) binstruct.End `bin:"off=65"` + + Size uint32 `bin:"-"` // superblock.NodeSize + MaxItems uint32 `bin:"-"` // Maximum possible value of NumItems } type InternalNode struct { - NodeHeader - Body []KeyPointer + Header Ref[LogicalAddr, NodeHeader] + Body []Ref[LogicalAddr, KeyPointer] +} + +func (in *InternalNode) GetNodeHeader() Ref[LogicalAddr, NodeHeader] { + return in.Header } type KeyPointer struct { @@ -221,8 +233,22 @@ type KeyPointer struct { } type LeafNode struct { - NodeHeader - Body []Item + Header Ref[LogicalAddr, NodeHeader] + Body []Ref[LogicalAddr, Item] +} + +func (ln *LeafNode) GetNodeHeader() Ref[LogicalAddr, NodeHeader] { + return ln.Header +} + +func (ln *LeafNode) FreeSpace() uint32 { + freeSpace := ln.Header.Data.Size + freeSpace -= 0x65 + for _, item := range ln.Body { + freeSpace -= 0x19 + freeSpace -= item.Data.DataSize + } + return freeSpace } type Item struct { @@ -230,6 +256,7 @@ type Item struct { DataOffset uint32 `bin:"off=11, siz=4"` // relative to the end of the header (0x65) DataSize uint32 `bin:"off=15, siz=4"` binstruct.End `bin:"off=19"` + Data Ref[LogicalAddr, []byte] `bin:"-"` } type DevItem struct { -- cgit v1.2.3-2-g168b