From 3825cf60fd652f22acc438d50028701d27a7402d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 1 Jun 2022 01:27:19 -0600 Subject: wow --- pkg/btrfs/Makefile | 47 +++++ pkg/btrfs/btrfsitem/item_chunk.go | 62 +++++++ pkg/btrfs/btrfsitem/item_dev.go | 29 +++ pkg/btrfs/btrfsitem/item_devextent.go | 15 ++ pkg/btrfs/btrfsitem/item_empty.go | 9 + pkg/btrfs/btrfsitem/item_inode.go | 27 +++ pkg/btrfs/btrfsitem/item_inoderef.go | 12 ++ pkg/btrfs/btrfsitem/item_orphan.go | 9 + pkg/btrfs/btrfsitem/item_persistent.go | 19 ++ pkg/btrfs/btrfsitem/item_root.go | 50 +++++ pkg/btrfs/btrfsitem/item_uuid.go | 39 ++++ pkg/btrfs/btrfsitem/items.go | 20 ++ pkg/btrfs/btrfsitem/items.go.bak | 193 +++++++++++++++++++ pkg/btrfs/btrfsitem/items.txt | 12 ++ pkg/btrfs/btrfstyp/misc.go | 31 ++++ pkg/btrfs/btrfstyp/objid.go | 145 +++++++++++++++ pkg/btrfs/btrfstyp/uuid.go | 24 +++ pkg/btrfs/fsck.go | 3 +- pkg/btrfs/internal/itemtype.go | 41 +++++ pkg/btrfs/io1_device.go | 76 ++++++++ pkg/btrfs/io2_fs.go | 274 +++++++++++++++++++++++++++ pkg/btrfs/io_device.go | 73 -------- pkg/btrfs/io_fs.go | 326 --------------------------------- pkg/btrfs/io_ref.go | 29 --- pkg/btrfs/types_bitfields.go | 120 ------------ pkg/btrfs/types_btree.go | 163 +++++++++++++++++ pkg/btrfs/types_item.go | 274 --------------------------- pkg/btrfs/types_objid.go | 144 --------------- pkg/btrfs/types_structs.go | 283 ---------------------------- pkg/btrfs/types_superblock.go | 216 ++++++++++++++++++++++ pkg/btrfs/types_uuid.go | 24 --- pkg/btrfs/util.go | 11 ++ 32 files changed, 1526 insertions(+), 1274 deletions(-) create mode 100644 pkg/btrfs/Makefile create mode 100644 pkg/btrfs/btrfsitem/item_chunk.go create mode 100644 pkg/btrfs/btrfsitem/item_dev.go create mode 100644 pkg/btrfs/btrfsitem/item_devextent.go create mode 100644 pkg/btrfs/btrfsitem/item_empty.go create mode 100644 pkg/btrfs/btrfsitem/item_inode.go create mode 100644 pkg/btrfs/btrfsitem/item_inoderef.go create mode 100644 pkg/btrfs/btrfsitem/item_orphan.go create mode 100644 pkg/btrfs/btrfsitem/item_persistent.go create mode 100644 pkg/btrfs/btrfsitem/item_root.go create mode 100644 pkg/btrfs/btrfsitem/item_uuid.go create mode 100644 pkg/btrfs/btrfsitem/items.go create mode 100644 pkg/btrfs/btrfsitem/items.go.bak create mode 100644 pkg/btrfs/btrfsitem/items.txt create mode 100644 pkg/btrfs/btrfstyp/misc.go create mode 100644 pkg/btrfs/btrfstyp/objid.go create mode 100644 pkg/btrfs/btrfstyp/uuid.go create mode 100644 pkg/btrfs/internal/itemtype.go create mode 100644 pkg/btrfs/io1_device.go create mode 100644 pkg/btrfs/io2_fs.go delete mode 100644 pkg/btrfs/io_device.go delete mode 100644 pkg/btrfs/io_fs.go delete mode 100644 pkg/btrfs/io_ref.go delete mode 100644 pkg/btrfs/types_bitfields.go create mode 100644 pkg/btrfs/types_btree.go delete mode 100644 pkg/btrfs/types_item.go delete mode 100644 pkg/btrfs/types_objid.go delete mode 100644 pkg/btrfs/types_structs.go create mode 100644 pkg/btrfs/types_superblock.go delete mode 100644 pkg/btrfs/types_uuid.go (limited to 'pkg/btrfs') diff --git a/pkg/btrfs/Makefile b/pkg/btrfs/Makefile new file mode 100644 index 0000000..cf3a911 --- /dev/null +++ b/pkg/btrfs/Makefile @@ -0,0 +1,47 @@ +.DEFAULT_GOAL = all +.SECONDARY: +.DELETE_ON_ERROR: + +internal: + mkdir $@ +btrfsitem/items.txt: btrfsitem $(wildcard btrfsitem/item_*.go) $(MAKEFILE_LIST) + sed -En 's,^type (\S+) .* // (.*=.*),\1 \2,p' $(filter btrfsitem/item_%.go,$^) | while read -r typ keys; do for key in $$keys; do echo "$$key" "$$typ"; done; done >$@ +files += btrfsitem/items.txt + +btrfsitem/items.go: btrfsitem/items.txt $(MAKEFILE_LIST) + { \ + echo 'package $(@D)'; \ + echo 'import "lukeshu.com/btrfs-tools/pkg/btrfs/internal"'; \ + echo 'type Type = internal.ItemType'; \ + echo 'const ('; \ + sed -E 's,(.*)=(.*) (.*),\1_KEY=internal.\1_KEY,' $<; \ + echo ')'; \ + } | gofmt >$@ +files += btrfsitem/items.go + +internal/itemtype.go: btrfsitem/items.txt $(MAKEFILE_LIST) + { \ + echo 'package $(@D)'; \ + echo 'import "fmt"'; \ + echo 'type ItemType uint8'; \ + echo 'const ('; \ + sed -E 's,(.*)=(.*) (.*),\1_KEY=ItemType(\2),' $<; \ + echo ')'; \ + echo 'func (t ItemType) String() string {'; \ + echo ' names := map[ItemType]string{'; \ + sed -E 's@(.*)=(.*) (.*)@\1_KEY: "\1",@' $<; \ + echo ' }'; \ + echo ' if name, ok := names[t]; ok {'; \ + echo ' return name'; \ + echo ' }'; \ + echo ' return fmt.Sprintf("%d", t)'; \ + echo '}'; \ + } | gofmt >$@ +files += internal/itemtype.go + +all: $(files) +.PHONY: all + +clean: + rm -f -- $(files) +.PHONY: all diff --git a/pkg/btrfs/btrfsitem/item_chunk.go b/pkg/btrfs/btrfsitem/item_chunk.go new file mode 100644 index 0000000..41706c3 --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_chunk.go @@ -0,0 +1,62 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" +) + +type Chunk struct { // CHUNK_ITEM=228 + // Maps logical address to physical. + Size uint64 `bin:"off=0x0, siz=0x8"` // size of chunk (bytes) + Owner btrfstyp.ObjID `bin:"off=0x8, siz=0x8"` // root referencing this chunk (2) + StripeLen uint64 `bin:"off=0x10, siz=0x8"` // stripe length + Type uint64 `bin:"off=0x18, siz=0x8"` // type (same as flags for block group?) + IOOptimalAlign uint32 `bin:"off=0x20, siz=0x4"` // optimal io alignment + IOOptimalWidth uint32 `bin:"off=0x24, siz=0x4"` // optimal io width + IoMinSize uint32 `bin:"off=0x28, siz=0x4"` // minimal io size (sector size) + NumStripes uint16 `bin:"off=0x2c, siz=0x2"` // number of stripes + SubStripes uint16 `bin:"off=0x2e, siz=0x2"` // sub stripes + binstruct.End `bin:"off=0x30"` + Stripes []ChunkStripe `bin:"-"` +} + +type ChunkStripe struct { + // Stripes follow (for each number of stripes): + DeviceID btrfstyp.ObjID `bin:"off=0, siz=8"` // device ID + Offset uint64 `bin:"off=8, siz=8"` // offset + DeviceUUID btrfstyp.UUID `bin:"off=10, siz=10"` // device UUID + binstruct.End `bin:"off=20"` +} + +func (chunk *Chunk) UnmarshalBinary(dat []byte) (int, error) { + n, err := binstruct.UnmarshalWithoutInterface(dat, chunk) + if err != nil { + return n, err + } + for i := 0; i < int(chunk.NumStripes); i++ { + var stripe ChunkStripe + _n, err := binstruct.Unmarshal(dat[n:], &stripe) + n += _n + if err != nil { + return n, err + } + chunk.Stripes = append(chunk.Stripes, stripe) + } + return n, nil +} + +func (chunk Chunk) MarshalBinary() ([]byte, error) { + chunk.NumStripes = uint16(len(chunk.Stripes)) + ret, err := binstruct.MarshalWithoutInterface(chunk) + if err != nil { + return ret, err + } + for _, stripe := range chunk.Stripes { + _ret, err := binstruct.Marshal(stripe) + ret = append(ret, _ret...) + if err != nil { + return ret, err + } + } + return ret, nil +} diff --git a/pkg/btrfs/btrfsitem/item_dev.go b/pkg/btrfs/btrfsitem/item_dev.go new file mode 100644 index 0000000..f474156 --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_dev.go @@ -0,0 +1,29 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" +) + +type Dev struct { // DEV_ITEM=216 + DeviceID btrfstyp.ObjID `bin:"off=0x0, siz=0x8"` // device ID + + NumBytes uint64 `bin:"off=0x8, siz=0x8"` // number of bytes + NumBytesUsed uint64 `bin:"off=0x10, siz=0x8"` // number of bytes used + + IOOptimalAlign uint32 `bin:"off=0x18, siz=0x4"` // optimal I/O align + IOOptimalWidth uint32 `bin:"off=0x1c, siz=0x4"` // optimal I/O width + IOMinSize uint32 `bin:"off=0x20, siz=0x4"` // minimal I/O size (sector size) + + Type uint64 `bin:"off=0x24, siz=0x8"` // type + Generation btrfstyp.Generation `bin:"off=0x2c, siz=0x8"` // generation + StartOffset uint64 `bin:"off=0x34, siz=0x8"` // start offset + DevGroup uint32 `bin:"off=0x3c, siz=0x4"` // dev group + SeekSpeed uint8 `bin:"off=0x40, siz=0x1"` // seek speed + Bandwidth uint8 `bin:"off=0x41, siz=0x1"` // bandwidth + + DevUUID btrfstyp.UUID `bin:"off=0x42, siz=0x10"` // device UUID + FSUUID btrfstyp.UUID `bin:"off=0x52, siz=0x10"` // FS UUID + + binstruct.End `bin:"off=0x62"` +} diff --git a/pkg/btrfs/btrfsitem/item_devextent.go b/pkg/btrfs/btrfsitem/item_devextent.go new file mode 100644 index 0000000..4bdd1c3 --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_devextent.go @@ -0,0 +1,15 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" +) + +type DevExtent struct { // DEV_EXTENT=204 + ChunkTree int64 `bin:"off=0, siz=8"` + ChunkObjectID btrfstyp.ObjID `bin:"off=8, siz=8"` + ChunkOffset int64 `bin:"off=16, siz=8"` + Length int64 `bin:"off=24, siz=8"` + ChunkTreeUUID btrfstyp.UUID `bin:"off=32, siz=16"` + binstruct.End `bin:"off=48"` +} diff --git a/pkg/btrfs/btrfsitem/item_empty.go b/pkg/btrfs/btrfsitem/item_empty.go new file mode 100644 index 0000000..ed0f66f --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_empty.go @@ -0,0 +1,9 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" +) + +type Empty struct { // UNTYPED=0, QGROUP_RELATION=246 + binstruct.End `bin:"off=48"` +} diff --git a/pkg/btrfs/btrfsitem/item_inode.go b/pkg/btrfs/btrfsitem/item_inode.go new file mode 100644 index 0000000..0c7600e --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_inode.go @@ -0,0 +1,27 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" +) + +type Inode struct { // INODE_ITEM=1 + Generation int64 `bin:"off=0x0, siz=0x8"` + TransID int64 `bin:"off=0x8, siz=0x8"` + Size int64 `bin:"off=0x10, siz=0x8"` + NumBytes int64 `bin:"off=0x18, siz=0x8"` + BlockGroup int64 `bin:"off=0x20, siz=0x8"` + NLink int32 `bin:"off=0x28, siz=0x4"` + UID int32 `bin:"off=0x2C, siz=0x4"` + GID int32 `bin:"off=0x30, siz=0x4"` + Mode int32 `bin:"off=0x34, siz=0x4"` + RDev int64 `bin:"off=0x38, siz=0x8"` + Flags uint64 `bin:"off=0x40, siz=0x8"` + Sequence int64 `bin:"off=0x48, siz=0x8"` + Reserved [4]int64 `bin:"off=0x50, siz=0x20"` + ATime btrfstyp.Time `bin:"off=0x70, siz=0xc"` + CTime btrfstyp.Time `bin:"off=0x7c, siz=0xc"` + MTime btrfstyp.Time `bin:"off=0x88, siz=0xc"` + OTime btrfstyp.Time `bin:"off=0x94, siz=0xc"` + binstruct.End `bin:"off=0xa0"` +} diff --git a/pkg/btrfs/btrfsitem/item_inoderef.go b/pkg/btrfs/btrfsitem/item_inoderef.go new file mode 100644 index 0000000..5a271ae --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_inoderef.go @@ -0,0 +1,12 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" +) + +type InodeRef struct { // INODE_REF=12 + Index int64 `bin:"off=0x0, siz=0x8"` + NameLen int16 `bin:"off=0x8, siz=0x2"` + binstruct.End `bin:"off=0xa"` + Name []byte `bin:"-"` +} diff --git a/pkg/btrfs/btrfsitem/item_orphan.go b/pkg/btrfs/btrfsitem/item_orphan.go new file mode 100644 index 0000000..6cf29b0 --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_orphan.go @@ -0,0 +1,9 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" +) + +type Orphan struct { // ORPHAN_ITEM=48 + binstruct.End `bin:"off=0"` +} diff --git a/pkg/btrfs/btrfsitem/item_persistent.go b/pkg/btrfs/btrfsitem/item_persistent.go new file mode 100644 index 0000000..3221800 --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_persistent.go @@ -0,0 +1,19 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" +) + +const ( + DEV_STAT_WRITE_ERRS = iota + DEV_STAT_READ_ERRS + DEV_STAT_FLUSH_ERRS + DEV_STAT_CORRUPTION_ERRS + DEV_STAT_GENERATION_ERRS + DEV_STAT_VALUES_MAX +) + +type DevStats struct { // PERSISTENT_ITEM=249 + Values [DEV_STAT_VALUES_MAX]int64 `bin:"off=0, siz=40"` + binstruct.End `bin:"off=40"` +} diff --git a/pkg/btrfs/btrfsitem/item_root.go b/pkg/btrfs/btrfsitem/item_root.go new file mode 100644 index 0000000..c87a49b --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_root.go @@ -0,0 +1,50 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" + "lukeshu.com/btrfs-tools/pkg/util" +) + +type Root struct { // ROOT_ITEM=132 + Inode Inode `bin:"off=0x0, siz=0xa0"` + Generation int64 `bin:"off=0xa0, siz=0x8"` + RootDirID int64 `bin:"off=0xa8, siz=0x8"` + ByteNr btrfstyp.LogicalAddr `bin:"off=0xb0, siz=0x8"` + ByteLimit int64 `bin:"off=0xb8, siz=0x8"` + BytesUsed int64 `bin:"off=0xc0, siz=0x8"` + LastSnapshot int64 `bin:"off=0xc8, siz=0x8"` + Flags RootFlags `bin:"off=0xd0, siz=0x8"` + Refs int32 `bin:"off=0xd8, siz=0x4"` + DropProgress btrfstyp.Key `bin:"off=0xdc, siz=0x11"` + DropLevel uint8 `bin:"off=0xed, siz=0x1"` + Level uint8 `bin:"off=0xee, siz=0x1"` + GenerationV2 int64 `bin:"off=0xef, siz=0x8"` + UUID btrfstyp.UUID `bin:"off=0xF7, siz=0x10"` + ParentUUID btrfstyp.UUID `bin:"off=0x107, siz=0x10"` + ReceivedUUID btrfstyp.UUID `bin:"off=0x117, siz=0x10"` + CTransID int64 `bin:"off=0x127, siz=0x8"` + OTransID int64 `bin:"off=0x12f, siz=0x8"` + STransID int64 `bin:"off=0x137, siz=0x8"` + RTransID int64 `bin:"off=0x13f, siz=0x8"` + CTime btrfstyp.Time `bin:"off=0x147, siz=0xc"` + OTime btrfstyp.Time `bin:"off=0x153, siz=0xc"` + STime btrfstyp.Time `bin:"off=0x15F, siz=0xc"` + RTime btrfstyp.Time `bin:"off=0x16b, siz=0xc"` + GlobalTreeID btrfstyp.ObjID `bin:"off=0x177, siz=0x8"` + Reserved [7]int64 `bin:"off=0x17f, siz=0x38"` + binstruct.End `bin:"off=0x1b7"` +} + +type RootFlags uint64 + +const ( + BTRFS_ROOT_SUBVOL_RDONLY = RootFlags(1 << iota) +) + +var rootItemFlagNames = []string{ + "SUBVOL_RDONLY", +} + +func (f RootFlags) Has(req RootFlags) bool { return f&req == req } +func (f RootFlags) String() string { return util.BitfieldString(f, rootItemFlagNames) } diff --git a/pkg/btrfs/btrfsitem/item_uuid.go b/pkg/btrfs/btrfsitem/item_uuid.go new file mode 100644 index 0000000..315dd70 --- /dev/null +++ b/pkg/btrfs/btrfsitem/item_uuid.go @@ -0,0 +1,39 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" +) + +// The Key for this item is a UUID, and the item is a list of +// subvolume IDs (ObjectIDs) that that UUID maps to. +type UUIDMap struct { // UUID_SUBVOL=251 UUID_RECEIVED_SUBVOL=252 + SubvolIDs []btrfstyp.ObjID +} + +func (o *UUIDMap) UnmarshalBinary(dat []byte) (int, error) { + o.SubvolIDs = nil + var n int + for len(dat) > n { + var subvolID btrfstyp.ObjID + _n, err := binstruct.Unmarshal(dat[n:], &subvolID) + n += _n + if err != nil { + return n, err + } + o.SubvolIDs = append(o.SubvolIDs, subvolID) + } + return n, nil +} + +func (o UUIDMap) MarshalBinary() ([]byte, error) { + var ret []byte + for _, subvolID := range o.SubvolIDs { + bs, err := binstruct.Marshal(subvolID) + ret = append(ret, bs...) + if err != nil { + return ret, err + } + } + return ret, nil +} diff --git a/pkg/btrfs/btrfsitem/items.go b/pkg/btrfs/btrfsitem/items.go new file mode 100644 index 0000000..e9e03b8 --- /dev/null +++ b/pkg/btrfs/btrfsitem/items.go @@ -0,0 +1,20 @@ +package btrfsitem + +import "lukeshu.com/btrfs-tools/pkg/btrfs/internal" + +type Type = internal.ItemType + +const ( + CHUNK_ITEM_KEY = internal.CHUNK_ITEM_KEY + DEV_ITEM_KEY = internal.DEV_ITEM_KEY + DEV_EXTENT_KEY = internal.DEV_EXTENT_KEY + UNTYPED_KEY = internal.UNTYPED_KEY + QGROUP_RELATION_KEY = internal.QGROUP_RELATION_KEY + INODE_ITEM_KEY = internal.INODE_ITEM_KEY + INODE_REF_KEY = internal.INODE_REF_KEY + ORPHAN_ITEM_KEY = internal.ORPHAN_ITEM_KEY + PERSISTENT_ITEM_KEY = internal.PERSISTENT_ITEM_KEY + ROOT_ITEM_KEY = internal.ROOT_ITEM_KEY + UUID_SUBVOL_KEY = internal.UUID_SUBVOL_KEY + UUID_RECEIVED_SUBVOL_KEY = internal.UUID_RECEIVED_SUBVOL_KEY +) diff --git a/pkg/btrfs/btrfsitem/items.go.bak b/pkg/btrfs/btrfsitem/items.go.bak new file mode 100644 index 0000000..9a91d97 --- /dev/null +++ b/pkg/btrfs/btrfsitem/items.go.bak @@ -0,0 +1,193 @@ +package btrfsitem + +import ( + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" +) + +type Type = btrfstyp.ItemType + +const ( + BTRFS_UNTYPED_KEY = btrfstyp.ItemType(0) + + // inode items have the data typically returned from stat and store other + // info about object characteristics. There is one for every file and dir in + // the FS + BTRFS_INODE_ITEM_KEY = btrfstyp.ItemType(1) + BTRFS_INODE_REF_KEY = btrfstyp.ItemType(12) + BTRFS_INODE_EXTREF_KEY = btrfstyp.ItemType(13) + BTRFS_XATTR_ITEM_KEY = btrfstyp.ItemType(24) + + BTRFS_VERITY_DESC_ITEM_KEY = btrfstyp.ItemType(36) // new + BTRFS_VERITY_MERKLE_ITEM_KEY = btrfstyp.ItemType(37) // new + + BTRFS_ORPHAN_ITEM_KEY = btrfstyp.ItemType(48) + + BTRFS_DIR_LOG_ITEM_KEY = btrfstyp.ItemType(60) + BTRFS_DIR_LOG_INDEX_KEY = btrfstyp.ItemType(72) + // dir items are the name -> inode pointers in a directory. There is one + // for every name in a directory. + BTRFS_DIR_ITEM_KEY = btrfstyp.ItemType(84) + BTRFS_DIR_INDEX_KEY = btrfstyp.ItemType(96) + + // extent data is for file data + BTRFS_EXTENT_DATA_KEY = btrfstyp.ItemType(108) + + // csum items have the checksums for data in the extents + BTRFS_CSUM_ITEM_KEY = btrfstyp.ItemType(120) // new + // extent csums are stored in a separate tree and hold csums for + // an entire extent on disk. + BTRFS_EXTENT_CSUM_KEY = btrfstyp.ItemType(128) + + // root items point to tree roots. There are typically in the root + // tree used by the super block to find all the other trees + BTRFS_ROOT_ITEM_KEY = btrfstyp.ItemType(132) + + // root backrefs tie subvols and snapshots to the directory entries that + // reference them + BTRFS_ROOT_BACKREF_KEY = btrfstyp.ItemType(144) + + // root refs make a fast index for listing all of the snapshots and + // subvolumes referenced by a given root. They point directly to the + // directory item in the root that references the subvol + BTRFS_ROOT_REF_KEY = btrfstyp.ItemType(156) + + // extent items are in the extent map tree. These record which blocks + // are used, and how many references there are to each block + BTRFS_EXTENT_ITEM_KEY = btrfstyp.ItemType(168) + + // The same as the BTRFS_EXTENT_ITEM_KEY, except it's metadata we already know + // the length, so we save the level in key->offset instead of the length. + BTRFS_METADATA_ITEM_KEY = btrfstyp.ItemType(169) // new + + BTRFS_TREE_BLOCK_REF_KEY = btrfstyp.ItemType(176) + + BTRFS_EXTENT_DATA_REF_KEY = btrfstyp.ItemType(178) + + // old style extent backrefs + BTRFS_EXTENT_REF_V0_KEY = btrfstyp.ItemType(180) + + BTRFS_SHARED_BLOCK_REF_KEY = btrfstyp.ItemType(182) + + BTRFS_SHARED_DATA_REF_KEY = btrfstyp.ItemType(184) + + // block groups give us hints into the extent allocation trees. Which + // blocks are free etc etc + BTRFS_BLOCK_GROUP_ITEM_KEY = btrfstyp.ItemType(192) + + // Every block group is represented in the free space tree by a free space info + // item, which stores some accounting information. It is keyed on + // (block_group_start, FREE_SPACE_INFO, block_group_length). + BTRFS_FREE_SPACE_INFO_KEY = btrfstyp.ItemType(198) // new + + // A free space extent tracks an extent of space that is free in a block group. + // It is keyed on (start, FREE_SPACE_EXTENT, length). + BTRFS_FREE_SPACE_EXTENT_KEY = btrfstyp.ItemType(199) // new + + // When a block group becomes very fragmented, we convert it to use bitmaps + // instead of extents. A free space bitmap is keyed on + // (start, FREE_SPACE_BITMAP, length); the corresponding item is a bitmap with + // (length / sectorsize) bits. + BTRFS_FREE_SPACE_BITMAP_KEY = btrfstyp.ItemType(200) // new + + BTRFS_DEV_EXTENT_KEY = btrfstyp.ItemType(204) + BTRFS_DEV_ITEM_KEY = btrfstyp.ItemType(216) + BTRFS_CHUNK_ITEM_KEY = btrfstyp.ItemType(228) + + // quota groups + BTRFS_QGROUP_STATUS_KEY = btrfstyp.ItemType(240) // new + BTRFS_QGROUP_INFO_KEY = btrfstyp.ItemType(242) // new + BTRFS_QGROUP_LIMIT_KEY = btrfstyp.ItemType(244) // new + BTRFS_QGROUP_RELATION_KEY = btrfstyp.ItemType(246) // new + + // The key type for tree items that are stored persistently, but do not need to + // exist for extended period of time. The items can exist in any tree. + // + // [subtype, BTRFS_TEMPORARY_ITEM_KEY, data] + // + // Existing items: + // + // - balance status item + // (BTRFS_BALANCE_OBJECTID, BTRFS_TEMPORARY_ITEM_KEY, 0) + BTRFS_TEMPORARY_ITEM_KEY = btrfstyp.ItemType(248) // new + + // The key type for tree items that are stored persistently and usually exist + // for a long period, eg. filesystem lifetime. The item kinds can be status + // information, stats or preference values. The item can exist in any tree. + // + // [subtype, BTRFS_PERSISTENT_ITEM_KEY, data] + // + // Existing items: + // + // - device statistics, store IO stats in the device tree, one key for all + // stats + // (BTRFS_DEV_STATS_OBJECTID, BTRFS_DEV_STATS_KEY, 0) + BTRFS_PERSISTENT_ITEM_KEY = btrfstyp.ItemType(249) // new + + // Persistently stores the device replace state in the device tree. + // The key is built like this: (0, BTRFS_DEV_REPLACE_KEY, 0). + BTRFS_DEV_REPLACE_KEY = btrfstyp.ItemType(250) + + // Stores items that allow to quickly map UUIDs to something else. + // These items are part of the filesystem UUID tree. + // The key is built like this: + // (UUID_upper_64_bits, BTRFS_UUID_KEY*, UUID_lower_64_bits). + BTRFS_UUID_KEY_SUBVOL = btrfstyp.ItemType(251) // for UUIDs assigned to subvols // new + BTRFS_UUID_KEY_RECEIVED_SUBVOL = btrfstyp.ItemType(252) // for UUIDs assigned to received subvols // new + + // string items are for debugging. They just store a short string of + // data in the FS + BTRFS_STRING_ITEM_KEY = btrfstyp.ItemType(253) +) + +/* +func (t btrfstyp.ItemType) String() string { + names := map[btrfstyp.ItemType]string{ + BTRFS_UNTYPED_KEY: "UNTYPED", + BTRFS_INODE_ITEM_KEY: "INODE_ITEM", + BTRFS_INODE_REF_KEY: "INODE_REF", + BTRFS_INODE_EXTREF_KEY: "INODE_EXTREF", + BTRFS_XATTR_ITEM_KEY: "XATTR_ITEM", + BTRFS_VERITY_DESC_ITEM_KEY: "VERITY_DESC_ITEM", + BTRFS_VERITY_MERKLE_ITEM_KEY: "VERITY_MERKLE_ITEM", + BTRFS_ORPHAN_ITEM_KEY: "ORPHAN_ITEM", + BTRFS_DIR_LOG_ITEM_KEY: "DIR_LOG_ITEM", + BTRFS_DIR_LOG_INDEX_KEY: "DIR_LOG_INDEX", + BTRFS_DIR_ITEM_KEY: "DIR_ITEM", + BTRFS_DIR_INDEX_KEY: "DIR_INDEX", + BTRFS_EXTENT_DATA_KEY: "EXTENT_DATA", + BTRFS_CSUM_ITEM_KEY: "CSUM_ITEM", + BTRFS_EXTENT_CSUM_KEY: "EXTENT_CSUM", + BTRFS_ROOT_ITEM_KEY: "ROOT_ITEM", + BTRFS_ROOT_BACKREF_KEY: "ROOT_BACKREF", + BTRFS_ROOT_REF_KEY: "ROOT_REF", + BTRFS_EXTENT_ITEM_KEY: "EXTENT_ITEM", + BTRFS_METADATA_ITEM_KEY: "METADATA_ITEM", + BTRFS_TREE_BLOCK_REF_KEY: "TREE_BLOCK_REF", + BTRFS_EXTENT_DATA_REF_KEY: "EXTENT_DATA_REF", + BTRFS_EXTENT_REF_V0_KEY: "EXTENT_REF_V0", + BTRFS_SHARED_BLOCK_REF_KEY: "SHARED_BLOCK_REF", + BTRFS_SHARED_DATA_REF_KEY: "SHARED_DATA_REF", + BTRFS_BLOCK_GROUP_ITEM_KEY: "BLOCK_GROUP_ITEM", + BTRFS_FREE_SPACE_INFO_KEY: "FREE_SPACE_INFO", + BTRFS_FREE_SPACE_EXTENT_KEY: "FREE_SPACE_EXTENT", + BTRFS_FREE_SPACE_BITMAP_KEY: "FREE_SPACE_BITMAP", + BTRFS_DEV_EXTENT_KEY: "DEV_EXTENT", + BTRFS_DEV_ITEM_KEY: "DEV_ITEM", + BTRFS_CHUNK_ITEM_KEY: "CHUNK_ITEM", + BTRFS_QGROUP_STATUS_KEY: "QGROUP_STATUS", + BTRFS_QGROUP_INFO_KEY: "QGROUP_INFO", + BTRFS_QGROUP_LIMIT_KEY: "QGROUP_LIMIT", + BTRFS_QGROUP_RELATION_KEY: "QGROUP_RELATION", + BTRFS_TEMPORARY_ITEM_KEY: "TEMPORARY_ITEM", + BTRFS_PERSISTENT_ITEM_KEY: "PERSISTENT_ITEM", + BTRFS_DEV_REPLACE_KEY: "DEV_REPLACE", + BTRFS_UUID_KEY_SUBVOL: "UUID_KEY_SUBVOL", + BTRFS_UUID_KEY_RECEIVED_SUBVOL: "UUID_KEY_RECEIVED_SUBVOL", + BTRFS_STRING_ITEM_KEY: "STRING_ITEM", + } + if name, ok := names[t]; ok { + return name + } + return fmt.Sprintf("%d", t) +} +*/ diff --git a/pkg/btrfs/btrfsitem/items.txt b/pkg/btrfs/btrfsitem/items.txt new file mode 100644 index 0000000..02c1d24 --- /dev/null +++ b/pkg/btrfs/btrfsitem/items.txt @@ -0,0 +1,12 @@ +CHUNK_ITEM=228 Chunk +DEV_ITEM=216 Dev +DEV_EXTENT=204 DevExtent +UNTYPED=0, Empty +QGROUP_RELATION=246 Empty +INODE_ITEM=1 Inode +INODE_REF=12 InodeRef +ORPHAN_ITEM=48 Orphan +PERSISTENT_ITEM=249 DevStats +ROOT_ITEM=132 Root +UUID_SUBVOL=251 UUIDMap +UUID_RECEIVED_SUBVOL=252 UUIDMap diff --git a/pkg/btrfs/btrfstyp/misc.go b/pkg/btrfs/btrfstyp/misc.go new file mode 100644 index 0000000..b0847f8 --- /dev/null +++ b/pkg/btrfs/btrfstyp/misc.go @@ -0,0 +1,31 @@ +package btrfstyp + +import ( + "time" + + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/internal" +) + +type ( + PhysicalAddr int64 + LogicalAddr int64 + Generation uint64 +) + +type Key struct { + ObjectID ObjID `bin:"off=0, siz=8"` // Each tree has its own set of Object IDs. + ItemType internal.ItemType `bin:"off=8, siz=1"` + Offset uint64 `bin:"off=9, siz=8"` // The meaning depends on the item type. + binstruct.End `bin:"off=11"` +} + +type Time struct { + Sec int64 `bin:"off=0, siz=8"` // Number of seconds since 1970-01-01T00:00:00Z. + NSec uint32 `bin:"off=8, siz=4"` // Number of nanoseconds since the beginning of the second. + binstruct.End `bin:"off=c"` +} + +func (t Time) ToStd() time.Time { + return time.Unix(t.Sec, int64(t.NSec)) +} diff --git a/pkg/btrfs/btrfstyp/objid.go b/pkg/btrfs/btrfstyp/objid.go new file mode 100644 index 0000000..dce8c18 --- /dev/null +++ b/pkg/btrfs/btrfstyp/objid.go @@ -0,0 +1,145 @@ +package btrfstyp + +import ( + "fmt" + + "lukeshu.com/btrfs-tools/pkg/btrfs/internal" + "lukeshu.com/btrfs-tools/pkg/util" +) + +type ObjID uint64 + +const ( + // The IDs of the various trees + BTRFS_ROOT_TREE_OBJECTID = ObjID(1) // holds pointers to all of the tree roots + BTRFS_EXTENT_TREE_OBJECTID = ObjID(2) // stores information about which extents are in use, and reference counts + BTRFS_CHUNK_TREE_OBJECTID = ObjID(3) // chunk tree stores translations from logical -> physical block numbering + BTRFS_DEV_TREE_OBJECTID = ObjID(4) // stores info about which areas of a given device are in use; one per device + BTRFS_FS_TREE_OBJECTID = ObjID(5) // one per subvolume, storing files and directories + BTRFS_ROOT_TREE_DIR_OBJECTID = ObjID(6) // directory objectid inside the root tree + BTRFS_CSUM_TREE_OBJECTID = ObjID(7) // holds checksums of all the data extents + BTRFS_QUOTA_TREE_OBJECTID = ObjID(8) + BTRFS_UUID_TREE_OBJECTID = ObjID(9) // for storing items that use the BTRFS_UUID_*_KEY + BTRFS_FREE_SPACE_TREE_OBJECTID = ObjID(10) // tracks free space in block groups. + BTRFS_BLOCK_GROUP_TREE_OBJECTID = ObjID(11) // hold the block group items. + + // Objects in the DEV_TREE + BTRFS_DEV_STATS_OBJECTID = ObjID(0) // device stats in the device tree + + // ??? + BTRFS_BALANCE_OBJECTID = ObjID(util.MaxUint64pp - 4) // for storing balance parameters in the root tree + BTRFS_ORPHAN_OBJECTID = ObjID(util.MaxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files + BTRFS_TREE_LOG_OBJECTID = ObjID(util.MaxUint64pp - 6) // does write ahead logging to speed up fsyncs + BTRFS_TREE_LOG_FIXUP_OBJECTID = ObjID(util.MaxUint64pp - 7) + BTRFS_TREE_RELOC_OBJECTID = ObjID(util.MaxUint64pp - 8) // space balancing + BTRFS_DATA_RELOC_TREE_OBJECTID = ObjID(util.MaxUint64pp - 9) + BTRFS_EXTENT_CSUM_OBJECTID = ObjID(util.MaxUint64pp - 10) // extent checksums all have this objectid + BTRFS_FREE_SPACE_OBJECTID = ObjID(util.MaxUint64pp - 11) // For storing free space cache + BTRFS_FREE_INO_OBJECTID = ObjID(util.MaxUint64pp - 12) // stores the inode number for the free-ino cache + + BTRFS_MULTIPLE_OBJECTIDS = ObjID(util.MaxUint64pp - 255) // dummy objectid represents multiple objectids + + // All files have objectids in this range. + BTRFS_FIRST_FREE_OBJECTID = ObjID(256) + BTRFS_LAST_FREE_OBJECTID = ObjID(util.MaxUint64pp - 256) + + BTRFS_FIRST_CHUNK_TREE_OBJECTID = ObjID(256) + + // Objects in the CHUNK_TREE + BTRFS_DEV_ITEMS_OBJECTID = ObjID(1) + + // ??? + BTRFS_EMPTY_SUBVOL_DIR_OBJECTID = ObjID(2) +) + +func (id ObjID) Format(typ internal.ItemType) string { + switch typ { + case internal.PERSISTENT_ITEM_KEY: + names := map[ObjID]string{ + BTRFS_DEV_STATS_OBJECTID: "DEV_STATS", + } + if name, ok := names[id]; ok { + return name + } + return fmt.Sprintf("%d", int64(id)) + case internal.DEV_EXTENT_KEY: + return fmt.Sprintf("%d", int64(id)) + case internal.QGROUP_RELATION_KEY: + return fmt.Sprintf("%d/%d", + uint64(id)>>48, + uint64(id)&((1<<48)-1)) + case internal.UUID_SUBVOL_KEY, internal.UUID_RECEIVED_SUBVOL_KEY: + return fmt.Sprintf("0x%016x", uint64(id)) + case internal.DEV_ITEM_KEY: + names := map[ObjID]string{ + 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", + + BTRFS_DEV_ITEMS_OBJECTID: "DEV_ITEMS", + } + if name, ok := names[id]; ok { + return name + } + return fmt.Sprintf("%d", int64(id)) + case internal.CHUNK_ITEM_KEY: + names := map[ObjID]string{ + 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", + + BTRFS_FIRST_CHUNK_TREE_OBJECTID: "FIRST_CHUNK_TREE", + } + if name, ok := names[id]; ok { + return name + } + return fmt.Sprintf("%d", int64(id)) + default: + names := map[ObjID]string{ + 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", + + 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[id]; ok { + return name + } + return fmt.Sprintf("%d", int64(id)) + } +} + +func (id ObjID) String() string { + return id.Format(internal.UNTYPED_KEY) +} diff --git a/pkg/btrfs/btrfstyp/uuid.go b/pkg/btrfs/btrfstyp/uuid.go new file mode 100644 index 0000000..8b0c92e --- /dev/null +++ b/pkg/btrfs/btrfstyp/uuid.go @@ -0,0 +1,24 @@ +package btrfstyp + +import ( + "bytes" + "encoding/hex" + "strings" +) + +type UUID [16]byte + +func (uuid UUID) String() string { + str := hex.EncodeToString(uuid[:]) + return strings.Join([]string{ + str[:8], + str[8:12], + str[12:16], + str[16:20], + str[20:32], + }, "-") +} + +func (a UUID) Equal(b UUID) bool { + return bytes.Equal(a[:], b[:]) +} diff --git a/pkg/btrfs/fsck.go b/pkg/btrfs/fsck.go index b6c80e5..3220a12 100644 --- a/pkg/btrfs/fsck.go +++ b/pkg/btrfs/fsck.go @@ -4,6 +4,7 @@ import ( "fmt" "lukeshu.com/btrfs-tools/pkg/binstruct" + . "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" ) // ScanForNodes mimics btrfs-progs @@ -30,7 +31,7 @@ func ScanForNodes(dev *Device, sb Superblock) error { return fmt.Errorf("sector@%d: %w", pos, err) } var nodeHeader NodeHeader - if err := binstruct.Unmarshal(nodeBuf, &nodeHeader); err != nil { + if _, err := binstruct.Unmarshal(nodeBuf, &nodeHeader); err != nil { return fmt.Errorf("sector@%d: %w", pos, err) } if !nodeHeader.MetadataUUID.Equal(sb.EffectiveMetadataUUID()) { diff --git a/pkg/btrfs/internal/itemtype.go b/pkg/btrfs/internal/itemtype.go new file mode 100644 index 0000000..d780b60 --- /dev/null +++ b/pkg/btrfs/internal/itemtype.go @@ -0,0 +1,41 @@ +package internal + +import "fmt" + +type ItemType uint8 + +const ( + CHUNK_ITEM_KEY = ItemType(228) + DEV_ITEM_KEY = ItemType(216) + DEV_EXTENT_KEY = ItemType(204) + UNTYPED_KEY = ItemType(0) + QGROUP_RELATION_KEY = ItemType(246) + INODE_ITEM_KEY = ItemType(1) + INODE_REF_KEY = ItemType(12) + ORPHAN_ITEM_KEY = ItemType(48) + PERSISTENT_ITEM_KEY = ItemType(249) + ROOT_ITEM_KEY = ItemType(132) + UUID_SUBVOL_KEY = ItemType(251) + UUID_RECEIVED_SUBVOL_KEY = ItemType(252) +) + +func (t ItemType) String() string { + names := map[ItemType]string{ + CHUNK_ITEM_KEY: "CHUNK_ITEM", + DEV_ITEM_KEY: "DEV_ITEM", + DEV_EXTENT_KEY: "DEV_EXTENT", + UNTYPED_KEY: "UNTYPED", + QGROUP_RELATION_KEY: "QGROUP_RELATION", + INODE_ITEM_KEY: "INODE_ITEM", + INODE_REF_KEY: "INODE_REF", + ORPHAN_ITEM_KEY: "ORPHAN_ITEM", + PERSISTENT_ITEM_KEY: "PERSISTENT_ITEM", + ROOT_ITEM_KEY: "ROOT_ITEM", + UUID_SUBVOL_KEY: "UUID_SUBVOL", + UUID_RECEIVED_SUBVOL_KEY: "UUID_RECEIVED_SUBVOL", + } + if name, ok := names[t]; ok { + return name + } + return fmt.Sprintf("%d", t) +} diff --git a/pkg/btrfs/io1_device.go b/pkg/btrfs/io1_device.go new file mode 100644 index 0000000..ed418a0 --- /dev/null +++ b/pkg/btrfs/io1_device.go @@ -0,0 +1,76 @@ +package btrfs + +import ( + "fmt" + "os" + + . "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" + "lukeshu.com/btrfs-tools/pkg/util" +) + +type Device struct { + *os.File +} + +func (dev Device) Size() (PhysicalAddr, error) { + fi, err := dev.Stat() + if err != nil { + return 0, err + } + return PhysicalAddr(fi.Size()), nil +} + +var superblockAddrs = []PhysicalAddr{ + 0x00_0001_0000, // 64KiB + 0x00_0400_0000, // 64MiB + 0x40_0000_0000, // 256GiB +} + +func (dev *Device) ReadAt(dat []byte, paddr PhysicalAddr) (int, error) { + return dev.File.ReadAt(dat, int64(paddr)) +} + +func (dev *Device) Superblocks() ([]util.Ref[PhysicalAddr, Superblock], error) { + const superblockSize = 0x1000 + + sz, err := dev.Size() + if err != nil { + return nil, err + } + + var ret []util.Ref[PhysicalAddr, Superblock] + for i, addr := range superblockAddrs { + if addr+superblockSize <= sz { + superblock := util.Ref[PhysicalAddr, Superblock]{ + File: dev, + Addr: addr, + } + if err := superblock.Read(); err != nil { + return nil, fmt.Errorf("superblock %d: %w", i, err) + } + ret = append(ret, superblock) + } + } + if len(ret) == 0 { + return nil, fmt.Errorf("no superblocks") + } + return ret, nil +} + +func (dev *Device) Superblock() (ret util.Ref[PhysicalAddr, Superblock], err error) { + sbs, err := dev.Superblocks() + if err != nil { + return ret, err + } + for i, sb := range sbs { + if err := sb.Data.ValidateChecksum(); err != nil { + return ret, fmt.Errorf("superblock %d: %w", i, err) + } + if i > 0 { + if !sb.Data.Equal(sbs[0].Data) { + return ret, fmt.Errorf("superblock %d and superblock %d disagree", 0, i) + } + } + } + return sbs[0], nil +} diff --git a/pkg/btrfs/io2_fs.go b/pkg/btrfs/io2_fs.go new file mode 100644 index 0000000..9b1e717 --- /dev/null +++ b/pkg/btrfs/io2_fs.go @@ -0,0 +1,274 @@ +package btrfs + +import ( + "bytes" + "fmt" + "reflect" + + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + . "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" + "lukeshu.com/btrfs-tools/pkg/util" +) + +type FS struct { + Devices []*Device + + initErr error + uuid2dev map[UUID]*Device + 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() ([]util.Ref[PhysicalAddr, Superblock], error) { + var ret []util.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 util.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 + } + fs.uuid2dev = make(map[UUID]*Device, len(fs.Devices)) + for _, dev := range fs.Devices { + sbs, err := dev.Superblocks() + if err != nil { + fs.initErr = fmt.Errorf("file %q: %w", dev.Name(), err) + return fs.initErr + } + + a := sbs[0].Data + a.Checksum = CSum{} + a.Self = 0 + for i, sb := range sbs[1:] { + b := sb.Data + b.Checksum = CSum{} + b.Self = 0 + if !reflect.DeepEqual(a, b) { + fs.initErr = fmt.Errorf("file %q: superblock %d disagrees with superblock 0", + dev.Name(), i+1) + return fs.initErr + } + } + sb := sbs[0] + if other, exists := fs.uuid2dev[sb.Data.DevItem.DevUUID]; exists { + fs.initErr = fmt.Errorf("file %q and file %q have the same device ID: %v", + other.Name(), dev.Name(), sb.Data.DevItem.DevUUID) + return fs.initErr + } + fs.uuid2dev[sb.Data.DevItem.DevUUID] = dev + syschunks, err := sb.Data.ParseSysChunkArray() + if err != nil { + fs.initErr = fmt.Errorf("file %q: %w", dev.Name(), err) + return fs.initErr + } + for _, chunk := range syschunks { + fs.chunks = append(fs.chunks, chunk) + } + if err := fs.WalkTree(sb.Data.ChunkTree, func(key Key, dat []byte) error { + if key.ItemType != btrfsitem.CHUNK_ITEM_KEY { + return nil + } + pair := SysChunk{ + Key: key, + } + if _, err := binstruct.Unmarshal(dat, &pair.Chunk); err != nil { + return err + } + fs.chunks = append(fs.chunks, pair) + return nil + }); err != nil { + fs.initErr = err + return fs.initErr + } + } + return nil +} + +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) { + type physicalAddr struct { + Dev UUID + Addr PhysicalAddr + } + + paddrs := make(map[physicalAddr]struct{}) + + for _, chunk := range fs.chunks { + if chunk.Offset <= uint64(laddr) && uint64(laddr) < chunk.Offset+uint64(chunk.Chunk.Size) { + offsetWithinChunk := uint64(laddr) - chunk.Offset + if offsetWithinChunk+uint64(len(dat)) > chunk.Chunk.Size { + dat = dat[:chunk.Chunk.Size-offsetWithinChunk] + } + for _, stripe := range chunk.Chunk.Stripes { + paddrs[physicalAddr{ + Dev: stripe.DeviceUUID, + Addr: PhysicalAddr(stripe.Offset + offsetWithinChunk), + }] = struct{}{} + } + } + } + + if len(paddrs) == 0 { + return 0, fmt.Errorf("could not map logical address %v", laddr) + } + + buf := make([]byte, len(dat)) + first := true + for paddr := range paddrs { + dev, ok := fs.uuid2dev[paddr.Dev] + if !ok { + return 0, fmt.Errorf("device=%s does not exist", paddr.Dev) + } + 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 { + copy(dat, buf) + } else { + if !bytes.Equal(dat, buf) { + return 0, fmt.Errorf("inconsistent stripes at laddr=%v len=%d", laddr, len(dat)) + } + } + } + return len(dat), nil +} + +func (fs *FS) ReadNode(addr LogicalAddr) (util.Ref[LogicalAddr, Node], error) { + var ret util.Ref[LogicalAddr, Node] + + sb, err := fs.Superblock() + if err != nil { + return ret, err + } + + nodeBuf := make([]byte, sb.Data.NodeSize) + if _, err := fs.ReadAt(nodeBuf, addr); err != nil { + return ret, err + } + + var node Node + node.Size = sb.Data.NodeSize + + if _, err := node.UnmarshalBinary(nodeBuf); err != nil { + return ret, fmt.Errorf("node@%d: %w", addr, err) + } + + // sanity checking + + if !node.Head.MetadataUUID.Equal(sb.Data.EffectiveMetadataUUID()) { + return ret, fmt.Errorf("node@%d: does not look like a node", addr) + } + + if node.Head.Addr != addr { + return ret, fmt.Errorf("node@%d: read from laddr=%d but claims to be at laddr=%d", + addr, addr, node.Head.Addr) + } + + stored := node.Head.Checksum + calced := CRC32c(nodeBuf[binstruct.StaticSize(CSum{}):]) + if !calced.Equal(stored) { + return ret, fmt.Errorf("node@%d: checksum mismatch: stored=%s calculated=%s", + addr, stored, calced) + } + + // return + + return util.Ref[LogicalAddr, Node]{ + File: fs, + Addr: addr, + Data: node, + }, nil +} + +func (fs *FS) WalkTree(nodeAddr LogicalAddr, fn func(Key, []byte) error) error { + if nodeAddr == 0 { + return nil + } + node, err := fs.ReadNode(nodeAddr) + if err != nil { + return err + } + for _, item := range node.Data.BodyInternal { + // fn(item.Data.Key, TODO) + if err := fs.WalkTree(item.BlockPtr, fn); err != nil { + return err + } + } + for _, item := range node.Data.BodyLeaf { + if err := fn(item.Head.Key, item.Body); err != nil { + return err + } + } + return nil +} diff --git a/pkg/btrfs/io_device.go b/pkg/btrfs/io_device.go deleted file mode 100644 index 042c9f2..0000000 --- a/pkg/btrfs/io_device.go +++ /dev/null @@ -1,73 +0,0 @@ -package btrfs - -import ( - "fmt" - "os" -) - -type Device struct { - *os.File -} - -func (dev Device) Size() (PhysicalAddr, error) { - fi, err := dev.Stat() - if err != nil { - return 0, err - } - return PhysicalAddr(fi.Size()), nil -} - -var superblockAddrs = []PhysicalAddr{ - 0x00_0001_0000, // 64KiB - 0x00_0400_0000, // 64MiB - 0x40_0000_0000, // 256GiB -} - -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() - if err != nil { - return nil, err - } - - var ret []Ref[PhysicalAddr, Superblock] - for i, addr := range superblockAddrs { - if addr+superblockSize <= sz { - superblock := Ref[PhysicalAddr, Superblock]{ - File: dev, - Addr: addr, - } - if err := superblock.Read(); err != nil { - return nil, fmt.Errorf("superblock %d: %w", i, err) - } - ret = append(ret, superblock) - } - } - if len(ret) == 0 { - return nil, fmt.Errorf("no superblocks") - } - return ret, nil -} - -func (dev *Device) Superblock() (ret Ref[PhysicalAddr, Superblock], err error) { - sbs, err := dev.Superblocks() - if err != nil { - return ret, err - } - for i, sb := range sbs { - if err := sb.Data.ValidateChecksum(); err != nil { - return ret, fmt.Errorf("superblock %d: %w", i, err) - } - if i > 0 { - if !sb.Data.Equal(sbs[0].Data) { - return ret, fmt.Errorf("superblock %d and superblock %d disagree", 0, i) - } - } - } - return sbs[0], nil -} diff --git a/pkg/btrfs/io_fs.go b/pkg/btrfs/io_fs.go deleted file mode 100644 index 4f52d86..0000000 --- a/pkg/btrfs/io_fs.go +++ /dev/null @@ -1,326 +0,0 @@ -package btrfs - -import ( - "bytes" - "fmt" - "reflect" - - "lukeshu.com/btrfs-tools/pkg/binstruct" -) - -type FS struct { - Devices []*Device - - initErr error - uuid2dev map[UUID]*Device - 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 - } - fs.uuid2dev = make(map[UUID]*Device, len(fs.Devices)) - for _, dev := range fs.Devices { - sbs, err := dev.Superblocks() - if err != nil { - fs.initErr = fmt.Errorf("file %q: %w", dev.Name(), err) - return fs.initErr - } - - a := sbs[0].Data - a.Checksum = CSum{} - a.Self = 0 - for i, sb := range sbs[1:] { - b := sb.Data - b.Checksum = CSum{} - b.Self = 0 - if !reflect.DeepEqual(a, b) { - fs.initErr = fmt.Errorf("file %q: superblock %d disagrees with superblock 0", - dev.Name(), i+1) - return fs.initErr - } - } - sb := sbs[0] - if other, exists := fs.uuid2dev[sb.Data.DevItem.DevUUID]; exists { - fs.initErr = fmt.Errorf("file %q and file %q have the same device ID: %v", - other.Name(), dev.Name(), sb.Data.DevItem.DevUUID) - return fs.initErr - } - fs.uuid2dev[sb.Data.DevItem.DevUUID] = dev - syschunks, err := sb.Data.ParseSysChunkArray() - if err != nil { - fs.initErr = fmt.Errorf("file %q: %w", dev.Name(), err) - return fs.initErr - } - for _, chunk := range syschunks { - fs.chunks = append(fs.chunks, chunk) - } - if err := fs.WalkTree(sb.Data.ChunkTree, func(key Key, dat []byte) error { - pair := SysChunk{ - Key: key, - } - if err := binstruct.Unmarshal(dat, &pair.Chunk); err != nil { - return err - } - dat = dat[0x30:] - for i := 0; i < int(pair.Chunk.NumStripes); i++ { - var stripe Stripe - if err := binstruct.Unmarshal(dat, &stripe); err != nil { - return err - } - pair.Chunk.Stripes = append(pair.Chunk.Stripes, stripe) - dat = dat[0x20:] - } - fs.chunks = append(fs.chunks, pair) - return nil - }); err != nil { - fs.initErr = err - return fs.initErr - } - } - return nil -} - -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) { - type physicalAddr struct { - Dev UUID - Addr PhysicalAddr - } - - paddrs := make(map[physicalAddr]struct{}) - - for _, chunk := range fs.chunks { - if chunk.Offset <= uint64(laddr) && uint64(laddr) < chunk.Offset+uint64(chunk.Chunk.Size) { - offsetWithinChunk := uint64(laddr) - chunk.Offset - if offsetWithinChunk+uint64(len(dat)) > chunk.Chunk.Size { - dat = dat[:chunk.Chunk.Size-offsetWithinChunk] - } - for _, stripe := range chunk.Chunk.Stripes { - paddrs[physicalAddr{ - Dev: stripe.DeviceUUID, - Addr: PhysicalAddr(stripe.Offset + offsetWithinChunk), - }] = struct{}{} - } - } - } - - if len(paddrs) == 0 { - return 0, fmt.Errorf("could not map logical address %v", laddr) - } - - buf := make([]byte, len(dat)) - first := true - for paddr := range paddrs { - dev, ok := fs.uuid2dev[paddr.Dev] - if !ok { - return 0, fmt.Errorf("device=%s does not exist", paddr.Dev) - } - 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 { - copy(dat, buf) - } else { - if !bytes.Equal(dat, buf) { - return 0, fmt.Errorf("inconsistent stripes at laddr=%v len=%d", laddr, len(dat)) - } - } - } - 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) - } - - if nodeHeader.Addr != addr { - return nil, fmt.Errorf("node@%d: read from laddr=%d but claims to be at laddr=%d", - addr, addr, nodeHeader.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 - } -} - -func (fs *FS) WalkTree(nodeAddr LogicalAddr, fn func(Key, []byte) error) error { - if nodeAddr == 0 { - return nil - } - node, err := fs.ReadNode(nodeAddr) - if err != nil { - return err - } - switch node := node.(type) { - case *InternalNode: - for _, item := range node.Body { - // fn(item.Data.Key, TODO) - if err := fs.WalkTree(item.Data.BlockPtr, fn); err != nil { - return err - } - } - case *LeafNode: - for _, item := range node.Body { - if err := fn(item.Data.Key, item.Data.Data.Data); err != nil { - return err - } - } - } - return nil -} diff --git a/pkg/btrfs/io_ref.go b/pkg/btrfs/io_ref.go deleted file mode 100644 index a91b691..0000000 --- a/pkg/btrfs/io_ref.go +++ /dev/null @@ -1,29 +0,0 @@ -package btrfs - -import ( - "lukeshu.com/btrfs-tools/pkg/binstruct" -) - -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[A, T]) Read() error { - size, err := binstruct.Size(r.Data) - if err != nil { - return err - } - buf := make([]byte, size) - 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 deleted file mode 100644 index 391ac15..0000000 --- a/pkg/btrfs/types_bitfields.go +++ /dev/null @@ -1,120 +0,0 @@ -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 { - var out strings.Builder - fmt.Fprintf(&out, "0x%0X", uint64(bitfield)) - if bitfield == 0 { - out.WriteString("(none)") - } else { - rest := bitfield - sep := '(' - for i := 0; rest != 0; i++ { - if rest&(1< 0 { + return bodyBytes / uint32(binstruct.StaticSize(KeyPointer{})) + } else { + return bodyBytes / uint32(binstruct.StaticSize(ItemHeader{})) + } +} + +func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error) { + n, err := binstruct.Unmarshal(nodeBuf, &node.Head) + if err != nil { + return n, err + } + if node.Head.Level > 0 { + // internal node + for i := uint32(0); i < node.Head.NumItems; i++ { + var item KeyPointer + _n, err := binstruct.Unmarshal(nodeBuf[n:], &item) + n += _n + if err != nil { + return n, fmt.Errorf("(internal): item %d: %w", i, err) + } + node.BodyInternal = append(node.BodyInternal, item) + } + return n, nil + } else { + // leaf node + lastRead := 0 + for i := uint32(0); i < node.Head.NumItems; i++ { + var item Item + _n, err := binstruct.Unmarshal(nodeBuf[n:], &item.Head) + n += _n + if err != nil { + return n, fmt.Errorf("(leaf): item %d: %w", i, err) + } + + dataOff := binstruct.StaticSize(NodeHeader{}) + int(item.Head.DataOffset) + dataSize := int(item.Head.DataSize) + if dataOff+dataSize > len(nodeBuf) { + return max(n, lastRead), fmt.Errorf("(leaf): item references byte %d, but node only has %d bytes", + dataOff+dataSize, len(nodeBuf)) + } + lastRead = max(lastRead, dataOff+dataSize) + item.Body = nodeBuf[dataOff : dataOff+dataSize] + + node.BodyLeaf = append(node.BodyLeaf, item) + } + return max(n, lastRead), nil + } +} + +func (node Node) MarshalBinary() ([]byte, error) { + panic("TODO") +} + +func (node *Node) LeafFreeSpace() uint32 { + if node.Head.Level > 0 { + panic(fmt.Errorf("Node.LeafFreeSpace: not a leaf node")) + } + freeSpace := node.Size + freeSpace -= uint32(binstruct.StaticSize(NodeHeader{})) + for _, item := range node.BodyLeaf { + freeSpace -= uint32(binstruct.StaticSize(ItemHeader{})) + freeSpace -= item.Head.DataSize + } + return freeSpace +} diff --git a/pkg/btrfs/types_item.go b/pkg/btrfs/types_item.go deleted file mode 100644 index 828ba02..0000000 --- a/pkg/btrfs/types_item.go +++ /dev/null @@ -1,274 +0,0 @@ -package btrfs - -import ( - "fmt" - - "lukeshu.com/btrfs-tools/pkg/binstruct" -) - -type ItemType uint8 - -const ( - BTRFS_UNTYPED_KEY = ItemType(0) - - // inode items have the data typically returned from stat and store other - // info about object characteristics. There is one for every file and dir in - // the FS - BTRFS_INODE_ITEM_KEY = ItemType(1) - BTRFS_INODE_REF_KEY = ItemType(12) - BTRFS_INODE_EXTREF_KEY = ItemType(13) - BTRFS_XATTR_ITEM_KEY = ItemType(24) - - BTRFS_VERITY_DESC_ITEM_KEY = ItemType(36) // new - BTRFS_VERITY_MERKLE_ITEM_KEY = ItemType(37) // new - - BTRFS_ORPHAN_ITEM_KEY = ItemType(48) - - BTRFS_DIR_LOG_ITEM_KEY = ItemType(60) - BTRFS_DIR_LOG_INDEX_KEY = ItemType(72) - // dir items are the name -> inode pointers in a directory. There is one - // for every name in a directory. - BTRFS_DIR_ITEM_KEY = ItemType(84) - BTRFS_DIR_INDEX_KEY = ItemType(96) - - // extent data is for file data - BTRFS_EXTENT_DATA_KEY = ItemType(108) - - // csum items have the checksums for data in the extents - BTRFS_CSUM_ITEM_KEY = ItemType(120) // new - // extent csums are stored in a separate tree and hold csums for - // an entire extent on disk. - BTRFS_EXTENT_CSUM_KEY = ItemType(128) - - // root items point to tree roots. There are typically in the root - // tree used by the super block to find all the other trees - BTRFS_ROOT_ITEM_KEY = ItemType(132) - - // root backrefs tie subvols and snapshots to the directory entries that - // reference them - BTRFS_ROOT_BACKREF_KEY = ItemType(144) - - // root refs make a fast index for listing all of the snapshots and - // subvolumes referenced by a given root. They point directly to the - // directory item in the root that references the subvol - BTRFS_ROOT_REF_KEY = ItemType(156) - - // extent items are in the extent map tree. These record which blocks - // are used, and how many references there are to each block - BTRFS_EXTENT_ITEM_KEY = ItemType(168) - - // The same as the BTRFS_EXTENT_ITEM_KEY, except it's metadata we already know - // the length, so we save the level in key->offset instead of the length. - BTRFS_METADATA_ITEM_KEY = ItemType(169) // new - - BTRFS_TREE_BLOCK_REF_KEY = ItemType(176) - - BTRFS_EXTENT_DATA_REF_KEY = ItemType(178) - - // old style extent backrefs - BTRFS_EXTENT_REF_V0_KEY = ItemType(180) - - BTRFS_SHARED_BLOCK_REF_KEY = ItemType(182) - - BTRFS_SHARED_DATA_REF_KEY = ItemType(184) - - // block groups give us hints into the extent allocation trees. Which - // blocks are free etc etc - BTRFS_BLOCK_GROUP_ITEM_KEY = ItemType(192) - - // Every block group is represented in the free space tree by a free space info - // item, which stores some accounting information. It is keyed on - // (block_group_start, FREE_SPACE_INFO, block_group_length). - BTRFS_FREE_SPACE_INFO_KEY = ItemType(198) // new - - // A free space extent tracks an extent of space that is free in a block group. - // It is keyed on (start, FREE_SPACE_EXTENT, length). - BTRFS_FREE_SPACE_EXTENT_KEY = ItemType(199) // new - - // When a block group becomes very fragmented, we convert it to use bitmaps - // instead of extents. A free space bitmap is keyed on - // (start, FREE_SPACE_BITMAP, length); the corresponding item is a bitmap with - // (length / sectorsize) bits. - BTRFS_FREE_SPACE_BITMAP_KEY = ItemType(200) // new - - BTRFS_DEV_EXTENT_KEY = ItemType(204) - BTRFS_DEV_ITEM_KEY = ItemType(216) - BTRFS_CHUNK_ITEM_KEY = ItemType(228) - - // quota groups - BTRFS_QGROUP_STATUS_KEY = ItemType(240) // new - BTRFS_QGROUP_INFO_KEY = ItemType(242) // new - BTRFS_QGROUP_LIMIT_KEY = ItemType(244) // new - BTRFS_QGROUP_RELATION_KEY = ItemType(246) // new - - // The key type for tree items that are stored persistently, but do not need to - // exist for extended period of time. The items can exist in any tree. - // - // [subtype, BTRFS_TEMPORARY_ITEM_KEY, data] - // - // Existing items: - // - // - balance status item - // (BTRFS_BALANCE_OBJECTID, BTRFS_TEMPORARY_ITEM_KEY, 0) - BTRFS_TEMPORARY_ITEM_KEY = ItemType(248) // new - - // The key type for tree items that are stored persistently and usually exist - // for a long period, eg. filesystem lifetime. The item kinds can be status - // information, stats or preference values. The item can exist in any tree. - // - // [subtype, BTRFS_PERSISTENT_ITEM_KEY, data] - // - // Existing items: - // - // - device statistics, store IO stats in the device tree, one key for all - // stats - // (BTRFS_DEV_STATS_OBJECTID, BTRFS_DEV_STATS_KEY, 0) - BTRFS_PERSISTENT_ITEM_KEY = ItemType(249) // new - - // Persistently stores the device replace state in the device tree. - // The key is built like this: (0, BTRFS_DEV_REPLACE_KEY, 0). - BTRFS_DEV_REPLACE_KEY = ItemType(250) - - // Stores items that allow to quickly map UUIDs to something else. - // These items are part of the filesystem UUID tree. - // The key is built like this: - // (UUID_upper_64_bits, BTRFS_UUID_KEY*, UUID_lower_64_bits). - BTRFS_UUID_KEY_SUBVOL = ItemType(251) // for UUIDs assigned to subvols // new - BTRFS_UUID_KEY_RECEIVED_SUBVOL = ItemType(252) // for UUIDs assigned to received subvols // new - - // string items are for debugging. They just store a short string of - // data in the FS - BTRFS_STRING_ITEM_KEY = ItemType(253) -) - -func (t ItemType) String() string { - names := map[ItemType]string{ - BTRFS_UNTYPED_KEY: "UNTYPED", - BTRFS_INODE_ITEM_KEY: "INODE_ITEM", - BTRFS_INODE_REF_KEY: "INODE_REF", - BTRFS_INODE_EXTREF_KEY: "INODE_EXTREF", - BTRFS_XATTR_ITEM_KEY: "XATTR_ITEM", - BTRFS_VERITY_DESC_ITEM_KEY: "VERITY_DESC_ITEM", - BTRFS_VERITY_MERKLE_ITEM_KEY: "VERITY_MERKLE_ITEM", - BTRFS_ORPHAN_ITEM_KEY: "ORPHAN_ITEM", - BTRFS_DIR_LOG_ITEM_KEY: "DIR_LOG_ITEM", - BTRFS_DIR_LOG_INDEX_KEY: "DIR_LOG_INDEX", - BTRFS_DIR_ITEM_KEY: "DIR_ITEM", - BTRFS_DIR_INDEX_KEY: "DIR_INDEX", - BTRFS_EXTENT_DATA_KEY: "EXTENT_DATA", - BTRFS_CSUM_ITEM_KEY: "CSUM_ITEM", - BTRFS_EXTENT_CSUM_KEY: "EXTENT_CSUM", - BTRFS_ROOT_ITEM_KEY: "ROOT_ITEM", - BTRFS_ROOT_BACKREF_KEY: "ROOT_BACKREF", - BTRFS_ROOT_REF_KEY: "ROOT_REF", - BTRFS_EXTENT_ITEM_KEY: "EXTENT_ITEM", - BTRFS_METADATA_ITEM_KEY: "METADATA_ITEM", - BTRFS_TREE_BLOCK_REF_KEY: "TREE_BLOCK_REF", - BTRFS_EXTENT_DATA_REF_KEY: "EXTENT_DATA_REF", - BTRFS_EXTENT_REF_V0_KEY: "EXTENT_REF_V0", - BTRFS_SHARED_BLOCK_REF_KEY: "SHARED_BLOCK_REF", - BTRFS_SHARED_DATA_REF_KEY: "SHARED_DATA_REF", - BTRFS_BLOCK_GROUP_ITEM_KEY: "BLOCK_GROUP_ITEM", - BTRFS_FREE_SPACE_INFO_KEY: "FREE_SPACE_INFO", - BTRFS_FREE_SPACE_EXTENT_KEY: "FREE_SPACE_EXTENT", - BTRFS_FREE_SPACE_BITMAP_KEY: "FREE_SPACE_BITMAP", - BTRFS_DEV_EXTENT_KEY: "DEV_EXTENT", - BTRFS_DEV_ITEM_KEY: "DEV_ITEM", - BTRFS_CHUNK_ITEM_KEY: "CHUNK_ITEM", - BTRFS_QGROUP_STATUS_KEY: "QGROUP_STATUS", - BTRFS_QGROUP_INFO_KEY: "QGROUP_INFO", - BTRFS_QGROUP_LIMIT_KEY: "QGROUP_LIMIT", - BTRFS_QGROUP_RELATION_KEY: "QGROUP_RELATION", - BTRFS_TEMPORARY_ITEM_KEY: "TEMPORARY_ITEM", - BTRFS_PERSISTENT_ITEM_KEY: "PERSISTENT_ITEM", - BTRFS_DEV_REPLACE_KEY: "DEV_REPLACE", - BTRFS_UUID_KEY_SUBVOL: "UUID_KEY_SUBVOL", - BTRFS_UUID_KEY_RECEIVED_SUBVOL: "UUID_KEY_RECEIVED_SUBVOL", - BTRFS_STRING_ITEM_KEY: "STRING_ITEM", - } - if name, ok := names[t]; ok { - return name - } - return fmt.Sprintf("%d", t) -} - -type DevItem struct { - DeviceID ObjID `bin:"off=0, siz=8"` // device ID - - NumBytes uint64 `bin:"off=8, siz=8"` // number of bytes - NumBytesUsed uint64 `bin:"off=10, siz=8"` // number of bytes used - - IOOptimalAlign uint32 `bin:"off=18, siz=4"` // optimal I/O align - IOOptimalWidth uint32 `bin:"off=1c, siz=4"` // optimal I/O width - IOMinSize uint32 `bin:"off=20, siz=4"` // minimal I/O size (sector size) - - Type uint64 `bin:"off=24, siz=8"` // type - Generation Generation `bin:"off=2c, siz=8"` // generation - StartOffset uint64 `bin:"off=34, siz=8"` // start offset - DevGroup uint32 `bin:"off=3c, siz=4"` // dev group - SeekSpeed uint8 `bin:"off=40, siz=1"` // seek speed - Bandwidth uint8 `bin:"off=41, siz=1"` // bandwidth - - DevUUID UUID `bin:"off=42, siz=10"` // device UUID - FSUUID UUID `bin:"off=52, siz=10"` // FS UUID - - binstruct.End `bin:"off=62"` -} - -type InodeRefItem struct { - Index int64 `bin:"off=0, siz=8"` - NameLen int16 `bin:"off=8, siz=2"` - binstruct.End `bin:"off=a"` - Name []byte `bin:"-"` -} - -type InodeItem struct { - Generation int64 `bin:"off=0, siz=8"` - TransID int64 `bin:"off=8, siz=8"` - Size int64 `bin:"off=10, siz=8"` - NumBytes int64 `bin:"off=18, siz=8"` - BlockGroup int64 `bin:"off=20, siz=8"` - NLink int32 `bin:"off=28, siz=4"` - UID int32 `bin:"off=2C, siz=4"` - GID int32 `bin:"off=30, siz=4"` - Mode int32 `bin:"off=34, siz=4"` - RDev int64 `bin:"off=38, siz=8"` - Flags uint64 `bin:"off=40, siz=8"` - Sequence int64 `bin:"off=48, siz=8"` - Reserved [4]int64 `bin:"off=50, siz=20"` - ATime Time `bin:"off=70, siz=c"` - CTime Time `bin:"off=7c, siz=c"` - MTime Time `bin:"off=88, siz=c"` - OTime Time `bin:"off=94, siz=c"` - binstruct.End `bin:"off=a0"` -} - -type RootItem struct { - Inode InodeItem `bin:"off=0, siz=a0"` - Generation int64 `bin:"off=a0, siz=8"` - RootDirID int64 `bin:"off=a8, siz=8"` - ByteNr LogicalAddr `bin:"off=b0, siz=8"` - ByteLimit int64 `bin:"off=b8, siz=8"` - BytesUsed int64 `bin:"off=c0, siz=8"` - LastSnapshot int64 `bin:"off=c8, siz=8"` - Flags RootItemFlags `bin:"off=d0, siz=8"` - Refs int32 `bin:"off=d8, siz=4"` - DropProgress Key `bin:"off=dc, siz=11"` - DropLevel uint8 `bin:"off=ed, siz=1"` - Level uint8 `bin:"off=ee, siz=1"` - GenerationV2 int64 `bin:"off=ef, siz=8"` - UUID UUID `bin:"off=F7, siz=10"` - ParentUUID UUID `bin:"off=107, siz=10"` - ReceivedUUID UUID `bin:"off=117, siz=10"` - CTransID int64 `bin:"off=127, siz=8"` - OTransID int64 `bin:"off=12f, siz=8"` - STransID int64 `bin:"off=137, siz=8"` - RTransID int64 `bin:"off=13f, siz=8"` - CTime Time `bin:"off=147, siz=c"` - OTime Time `bin:"off=153, siz=c"` - STime Time `bin:"off=15F, siz=c"` - RTime Time `bin:"off=16b, siz=c"` - GlobalTreeID ObjID `bin:"off=177, siz=8"` - Reserved [7]int64 `bin:"off=17f, siz=38"` - binstruct.End `bin:"off=1b7"` -} diff --git a/pkg/btrfs/types_objid.go b/pkg/btrfs/types_objid.go deleted file mode 100644 index bcaac9a..0000000 --- a/pkg/btrfs/types_objid.go +++ /dev/null @@ -1,144 +0,0 @@ -package btrfs - -import ( - "fmt" -) - -type ObjID uint64 - -const MaxUint64pp = 0x1_00000000_00000000 - -const ( - // The IDs of the various trees - BTRFS_ROOT_TREE_OBJECTID = ObjID(1) // holds pointers to all of the tree roots - BTRFS_EXTENT_TREE_OBJECTID = ObjID(2) // stores information about which extents are in use, and reference counts - BTRFS_CHUNK_TREE_OBJECTID = ObjID(3) // chunk tree stores translations from logical -> physical block numbering - BTRFS_DEV_TREE_OBJECTID = ObjID(4) // stores info about which areas of a given device are in use; one per device - BTRFS_FS_TREE_OBJECTID = ObjID(5) // one per subvolume, storing files and directories - BTRFS_ROOT_TREE_DIR_OBJECTID = ObjID(6) // directory objectid inside the root tree - BTRFS_CSUM_TREE_OBJECTID = ObjID(7) // holds checksums of all the data extents - BTRFS_QUOTA_TREE_OBJECTID = ObjID(8) - BTRFS_UUID_TREE_OBJECTID = ObjID(9) // for storing items that use the BTRFS_UUID_KEY* - BTRFS_FREE_SPACE_TREE_OBJECTID = ObjID(10) // tracks free space in block groups. - BTRFS_BLOCK_GROUP_TREE_OBJECTID = ObjID(11) // hold the block group items. - - // Objects in the DEV_TREE - BTRFS_DEV_STATS_OBJECTID = ObjID(0) // device stats in the device tree - - // ??? - BTRFS_BALANCE_OBJECTID = ObjID(MaxUint64pp - 4) // for storing balance parameters in the root tree - BTRFS_ORPHAN_OBJECTID = ObjID(MaxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files - BTRFS_TREE_LOG_OBJECTID = ObjID(MaxUint64pp - 6) // does write ahead logging to speed up fsyncs - BTRFS_TREE_LOG_FIXUP_OBJECTID = ObjID(MaxUint64pp - 7) - BTRFS_TREE_RELOC_OBJECTID = ObjID(MaxUint64pp - 8) // space balancing - BTRFS_DATA_RELOC_TREE_OBJECTID = ObjID(MaxUint64pp - 9) - BTRFS_EXTENT_CSUM_OBJECTID = ObjID(MaxUint64pp - 10) // extent checksums all have this objectid - BTRFS_FREE_SPACE_OBJECTID = ObjID(MaxUint64pp - 11) // For storing free space cache - BTRFS_FREE_INO_OBJECTID = ObjID(MaxUint64pp - 12) // stores the inode number for the free-ino cache - - BTRFS_MULTIPLE_OBJECTIDS = ObjID(MaxUint64pp - 255) // dummy objectid represents multiple objectids - - // All files have objectids in this range. - BTRFS_FIRST_FREE_OBJECTID = ObjID(256) - BTRFS_LAST_FREE_OBJECTID = ObjID(MaxUint64pp - 256) - - BTRFS_FIRST_CHUNK_TREE_OBJECTID = ObjID(256) - - // Objects in the CHUNK_TREE - BTRFS_DEV_ITEMS_OBJECTID = ObjID(1) - - // ??? - BTRFS_EMPTY_SUBVOL_DIR_OBJECTID = ObjID(2) -) - -func (id ObjID) Format(typ ItemType) string { - switch typ { - case BTRFS_PERSISTENT_ITEM_KEY: - names := map[ObjID]string{ - BTRFS_DEV_STATS_OBJECTID: "DEV_STATS", - } - if name, ok := names[id]; ok { - return name - } - return fmt.Sprintf("%d", int64(id)) - case BTRFS_DEV_EXTENT_KEY: - return fmt.Sprintf("%d", int64(id)) - case BTRFS_QGROUP_RELATION_KEY: - return fmt.Sprintf("%d/%d", - uint64(id)>>48, - uint64(id)&((1<<48)-1)) - case BTRFS_UUID_KEY_SUBVOL, BTRFS_UUID_KEY_RECEIVED_SUBVOL: - return fmt.Sprintf("0x%016x", uint64(id)) - case BTRFS_DEV_ITEM_KEY: - names := map[ObjID]string{ - 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", - - BTRFS_DEV_ITEMS_OBJECTID: "DEV_ITEMS", - } - if name, ok := names[id]; ok { - return name - } - return fmt.Sprintf("%d", int64(id)) - case BTRFS_CHUNK_ITEM_KEY: - names := map[ObjID]string{ - 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", - - BTRFS_FIRST_CHUNK_TREE_OBJECTID: "FIRST_CHUNK_TREE", - } - if name, ok := names[id]; ok { - return name - } - return fmt.Sprintf("%d", int64(id)) - default: - names := map[ObjID]string{ - 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", - - 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[id]; ok { - return name - } - return fmt.Sprintf("%d", int64(id)) - } -} - -func (id ObjID) String() string { - return id.Format(BTRFS_UNTYPED_KEY) -} diff --git a/pkg/btrfs/types_structs.go b/pkg/btrfs/types_structs.go deleted file mode 100644 index bfaa0e6..0000000 --- a/pkg/btrfs/types_structs.go +++ /dev/null @@ -1,283 +0,0 @@ -package btrfs - -import ( - "fmt" - "reflect" - "time" - - "lukeshu.com/btrfs-tools/pkg/binstruct" -) - -type ( - PhysicalAddr int64 - LogicalAddr int64 - Generation uint64 -) - -type Key struct { - ObjectID ObjID `bin:"off=0, siz=8"` // Each tree has its own set of Object IDs. - ItemType ItemType `bin:"off=8, siz=1"` - Offset uint64 `bin:"off=9, siz=8"` // The meaning depends on the item type. - binstruct.End `bin:"off=11"` -} - -type Time struct { - Sec int64 `bin:"off=0, siz=8"` // Number of seconds since 1970-01-01T00:00:00Z. - NSec uint32 `bin:"off=8, siz=4"` // Number of nanoseconds since the beginning of the second. - binstruct.End `bin:"off=c"` -} - -func (t Time) ToStd() time.Time { - return time.Unix(t.Sec, int64(t.NSec)) -} - -type Superblock struct { - Checksum CSum `bin:"off=0, siz=20"` // Checksum of everything past this field (from 20 to 1000) - FSUUID UUID `bin:"off=20, siz=10"` // FS UUID - Self PhysicalAddr `bin:"off=30, siz=8"` // physical address of this block (different for mirrors) - Flags uint64 `bin:"off=38, siz=8"` // flags - Magic [8]byte `bin:"off=40, siz=8"` // magic ('_BHRfS_M') - Generation Generation `bin:"off=48, siz=8"` - - RootTree LogicalAddr `bin:"off=50, siz=8"` // logical address of the root tree root - ChunkTree LogicalAddr `bin:"off=58, siz=8"` // logical address of the chunk tree root - LogTree LogicalAddr `bin:"off=60, siz=8"` // logical address of the log tree root - - LogRootTransID uint64 `bin:"off=68, siz=8"` // log_root_transid - TotalBytes uint64 `bin:"off=70, siz=8"` // total_bytes - BytesUsed uint64 `bin:"off=78, siz=8"` // bytes_used - RootDirObjectID ObjID `bin:"off=80, siz=8"` // root_dir_objectid (usually 6) - NumDevices uint64 `bin:"off=88, siz=8"` // num_devices - - SectorSize uint32 `bin:"off=90, siz=4"` - NodeSize uint32 `bin:"off=94, siz=4"` - LeafSize uint32 `bin:"off=98, siz=4"` // unused; must be the same as NodeSize - StripeSize uint32 `bin:"off=9c, siz=4"` - SysChunkArraySize uint32 `bin:"off=a0, siz=4"` - - ChunkRootGeneration Generation `bin:"off=a4, siz=8"` - CompatFlags uint64 `bin:"off=ac, siz=8"` // compat_flags - CompatROFlags uint64 `bin:"off=b4, siz=8"` // compat_ro_flags - only implementations that support the flags can write to the filesystem - IncompatFlags IncompatFlags `bin:"off=bc, siz=8"` // incompat_flags - only implementations that support the flags can use the filesystem - ChecksumType uint16 `bin:"off=c4, siz=2"` // csum_type - Btrfs currently uses the CRC32c little-endian hash function with seed -1. - - RootLevel uint8 `bin:"off=c6, siz=1"` // root_level - ChunkLevel uint8 `bin:"off=c7, siz=1"` // chunk_root_level - LogLevel uint8 `bin:"off=c8, siz=1"` // log_root_level - - DevItem DevItem `bin:"off=c9, siz=62"` // DEV_ITEM data for this device - Label [0x100]byte `bin:"off=12b, siz=100"` // label (may not contain '/' or '\\') - CacheGeneration Generation `bin:"off=22b, siz=8"` - UUIDTreeGeneration uint64 `bin:"off=233, siz=8"` // uuid_tree_generation - - // FeatureIncompatMetadataUUID - MetadataUUID UUID `bin:"off=23b, siz=10"` - - // FeatureIncompatExtentTreeV2 - NumGlobalRoots uint64 `bin:"off=24b, siz=8"` - - // FeatureIncompatExtentTreeV2 - 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 - - SysChunkArray [0x800]byte `bin:"off=32b, siz=800"` // sys_chunk_array:(n bytes valid) Contains (KEY . CHUNK_ITEM) pairs for all SYSTEM chunks. This is needed to bootstrap the mapping from logical addresses to physical. - SuperRoots [4]RootBackup `bin:"off=b2b, siz=2a0"` - - // Padded to 4096 bytes - Padding [565]byte `bin:"off=dcb, siz=235"` - binstruct.End `bin:"off=1000"` -} - -func (sb Superblock) CalculateChecksum() (CSum, error) { - data, err := binstruct.Marshal(sb) - if err != nil { - return CSum{}, err - } - return CRC32c(data[0x20:]), nil -} - -func (sb Superblock) ValidateChecksum() error { - stored := sb.Checksum - calced, err := sb.CalculateChecksum() - if err != nil { - return err - } - if !calced.Equal(stored) { - return fmt.Errorf("superblock checksum mismatch: stored=%s calculated=%s", - stored, calced) - } - return nil -} - -func (a Superblock) Equal(b Superblock) bool { - a.Checksum = CSum{} - a.Self = 0 - - b.Checksum = CSum{} - b.Self = 0 - - return reflect.DeepEqual(a, b) -} - -func (sb Superblock) EffectiveMetadataUUID() UUID { - if !sb.IncompatFlags.Has(FeatureIncompatMetadataUUID) { - return sb.FSUUID - } - return sb.MetadataUUID -} - -type SysChunk struct { - Key `bin:"off=0, siz=11"` - Chunk `bin:"off=11, siz=30"` - binstruct.End `bin:"off=41"` -} - -func (sb Superblock) ParseSysChunkArray() ([]SysChunk, error) { - dat := sb.SysChunkArray[:sb.SysChunkArraySize] - var ret []SysChunk - for len(dat) > 0 { - var pair SysChunk - if err := binstruct.Unmarshal(dat, &pair); err != nil { - return nil, err - } - dat = dat[0x41:] - - for i := 0; i < int(pair.Chunk.NumStripes); i++ { - var stripe Stripe - if err := binstruct.Unmarshal(dat, &stripe); err != nil { - return nil, err - } - pair.Chunk.Stripes = append(pair.Chunk.Stripes, stripe) - dat = dat[0x20:] - } - - ret = append(ret, pair) - } - return ret, nil -} - -type RootBackup struct { - TreeRoot ObjID `bin:"off=0, siz=8"` - TreeRootGen Generation `bin:"off=8, siz=8"` - - ChunkRoot ObjID `bin:"off=10, siz=8"` - ChunkRootGen Generation `bin:"off=18, siz=8"` - - ExtentRoot ObjID `bin:"off=20, siz=8"` - ExtentRootGen Generation `bin:"off=28, siz=8"` - - FSRoot ObjID `bin:"off=30, siz=8"` - FSRootGen Generation `bin:"off=38, siz=8"` - - DevRoot ObjID `bin:"off=40, siz=8"` - DevRootGen Generation `bin:"off=48, siz=8"` - - ChecksumRoot ObjID `bin:"off=50, siz=8"` - ChecksumRootGen Generation `bin:"off=58, siz=8"` - - TotalBytes uint64 `bin:"off=60, siz=8"` - BytesUsed uint64 `bin:"off=68, siz=8"` - NumDevices uint64 `bin:"off=70, siz=8"` - - Unused [8 * 4]byte `bin:"off=78, siz=20"` - - TreeRootLevel uint8 `bin:"off=98, siz=1"` - ChunkRootLevel uint8 `bin:"off=99, siz=1"` - ExtentRootLevel uint8 `bin:"off=9a, siz=1"` - FSRootLevel uint8 `bin:"off=9b, siz=1"` - DevRootLevel uint8 `bin:"off=9c, siz=1"` - ChecksumRootLevel uint8 `bin:"off=9d, siz=1"` - - Padding [10]byte `bin:"off=9e, siz=a"` - 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 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 ObjID `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 { - Header Ref[LogicalAddr, NodeHeader] - Body []Ref[LogicalAddr, KeyPointer] -} - -func (in *InternalNode) GetNodeHeader() Ref[LogicalAddr, NodeHeader] { - return in.Header -} - -type KeyPointer struct { - Key Key `bin:"off=0, siz=11"` - BlockPtr LogicalAddr `bin:"off=11, siz=8"` - Generation Generation `bin:"off=19, siz=8"` - binstruct.End `bin:"off=21"` -} - -type LeafNode struct { - 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 { - Key Key `bin:"off=0, siz=11"` - 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 Chunk struct { - // Maps logical address to physical. - Size uint64 `bin:"off=0, siz=8"` // size of chunk (bytes) - Owner ObjID `bin:"off=8, siz=8"` // root referencing this chunk (2) - StripeLen uint64 `bin:"off=10, siz=8"` // stripe length - Type uint64 `bin:"off=18, siz=8"` // type (same as flags for block group?) - IOOptimalAlign uint32 `bin:"off=20, siz=4"` // optimal io alignment - IOOptimalWidth uint32 `bin:"off=24, siz=4"` // optimal io width - IoMinSize uint32 `bin:"off=28, siz=4"` // minimal io size (sector size) - NumStripes uint16 `bin:"off=2c, siz=2"` // number of stripes - SubStripes uint16 `bin:"off=2e, siz=2"` // sub stripes - binstruct.End `bin:"off=30"` - Stripes []Stripe `bin:"-"` -} - -type Stripe struct { - // Stripes follow (for each number of stripes): - DeviceID ObjID `bin:"off=0, siz=8"` // device ID - Offset uint64 `bin:"off=8, siz=8"` // offset - DeviceUUID UUID `bin:"off=10, siz=10"` // device UUID - binstruct.End `bin:"off=20"` -} diff --git a/pkg/btrfs/types_superblock.go b/pkg/btrfs/types_superblock.go new file mode 100644 index 0000000..1b69c03 --- /dev/null +++ b/pkg/btrfs/types_superblock.go @@ -0,0 +1,216 @@ +package btrfs + +import ( + "fmt" + "reflect" + + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + . "lukeshu.com/btrfs-tools/pkg/btrfs/btrfstyp" + "lukeshu.com/btrfs-tools/pkg/util" +) + +type Superblock struct { + Checksum CSum `bin:"off=0, siz=20"` // Checksum of everything past this field (from 20 to 1000) + FSUUID UUID `bin:"off=20, siz=10"` // FS UUID + Self PhysicalAddr `bin:"off=30, siz=8"` // physical address of this block (different for mirrors) + Flags uint64 `bin:"off=38, siz=8"` // flags + Magic [8]byte `bin:"off=40, siz=8"` // magic ('_BHRfS_M') + Generation Generation `bin:"off=48, siz=8"` + + RootTree LogicalAddr `bin:"off=50, siz=8"` // logical address of the root tree root + ChunkTree LogicalAddr `bin:"off=58, siz=8"` // logical address of the chunk tree root + LogTree LogicalAddr `bin:"off=60, siz=8"` // logical address of the log tree root + + LogRootTransID uint64 `bin:"off=68, siz=8"` // log_root_transid + TotalBytes uint64 `bin:"off=70, siz=8"` // total_bytes + BytesUsed uint64 `bin:"off=78, siz=8"` // bytes_used + RootDirObjectID ObjID `bin:"off=80, siz=8"` // root_dir_objectid (usually 6) + NumDevices uint64 `bin:"off=88, siz=8"` // num_devices + + SectorSize uint32 `bin:"off=90, siz=4"` + NodeSize uint32 `bin:"off=94, siz=4"` + LeafSize uint32 `bin:"off=98, siz=4"` // unused; must be the same as NodeSize + StripeSize uint32 `bin:"off=9c, siz=4"` + SysChunkArraySize uint32 `bin:"off=a0, siz=4"` + + ChunkRootGeneration Generation `bin:"off=a4, siz=8"` + CompatFlags uint64 `bin:"off=ac, siz=8"` // compat_flags + CompatROFlags uint64 `bin:"off=b4, siz=8"` // compat_ro_flags - only implementations that support the flags can write to the filesystem + IncompatFlags IncompatFlags `bin:"off=bc, siz=8"` // incompat_flags - only implementations that support the flags can use the filesystem + ChecksumType uint16 `bin:"off=c4, siz=2"` // csum_type - Btrfs currently uses the CRC32c little-endian hash function with seed -1. + + RootLevel uint8 `bin:"off=c6, siz=1"` // root_level + ChunkLevel uint8 `bin:"off=c7, siz=1"` // chunk_root_level + LogLevel uint8 `bin:"off=c8, siz=1"` // log_root_level + + DevItem btrfsitem.Dev `bin:"off=c9, siz=62"` // DEV_ITEM data for this device + Label [0x100]byte `bin:"off=12b, siz=100"` // label (may not contain '/' or '\\') + CacheGeneration Generation `bin:"off=22b, siz=8"` + UUIDTreeGeneration uint64 `bin:"off=233, siz=8"` // uuid_tree_generation + + // FeatureIncompatMetadataUUID + MetadataUUID UUID `bin:"off=23b, siz=10"` + + // FeatureIncompatExtentTreeV2 + NumGlobalRoots uint64 `bin:"off=24b, siz=8"` + + // FeatureIncompatExtentTreeV2 + 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 + + SysChunkArray [0x800]byte `bin:"off=32b, siz=800"` // sys_chunk_array:(n bytes valid) Contains (KEY . CHUNK_ITEM) pairs for all SYSTEM chunks. This is needed to bootstrap the mapping from logical addresses to physical. + SuperRoots [4]RootBackup `bin:"off=b2b, siz=2a0"` + + // Padded to 4096 bytes + Padding [565]byte `bin:"off=dcb, siz=235"` + binstruct.End `bin:"off=1000"` +} + +func (sb Superblock) CalculateChecksum() (CSum, error) { + data, err := binstruct.Marshal(sb) + if err != nil { + return CSum{}, err + } + return CRC32c(data[0x20:]), nil +} + +func (sb Superblock) ValidateChecksum() error { + stored := sb.Checksum + calced, err := sb.CalculateChecksum() + if err != nil { + return err + } + if !calced.Equal(stored) { + return fmt.Errorf("superblock checksum mismatch: stored=%s calculated=%s", + stored, calced) + } + return nil +} + +func (a Superblock) Equal(b Superblock) bool { + a.Checksum = CSum{} + a.Self = 0 + + b.Checksum = CSum{} + b.Self = 0 + + return reflect.DeepEqual(a, b) +} + +func (sb Superblock) EffectiveMetadataUUID() UUID { + if !sb.IncompatFlags.Has(FeatureIncompatMetadataUUID) { + return sb.FSUUID + } + return sb.MetadataUUID +} + +type SysChunk struct { + Key `bin:"off=0, siz=11"` + btrfsitem.Chunk `bin:"off=11, siz=30"` + binstruct.End `bin:"off=41"` +} + +func (sb Superblock) ParseSysChunkArray() ([]SysChunk, error) { + dat := sb.SysChunkArray[:sb.SysChunkArraySize] + var ret []SysChunk + for len(dat) > 0 { + var pair SysChunk + n, err := binstruct.Unmarshal(dat, &pair) + dat = dat[n:] + if err != nil { + return nil, err + } + + for i := 0; i < int(pair.Chunk.NumStripes); i++ { + var stripe btrfsitem.ChunkStripe + n, err := binstruct.Unmarshal(dat, &stripe) + dat = dat[n:] + if err != nil { + return nil, err + } + pair.Chunk.Stripes = append(pair.Chunk.Stripes, stripe) + } + + ret = append(ret, pair) + } + return ret, nil +} + +type RootBackup struct { + TreeRoot ObjID `bin:"off=0, siz=8"` + TreeRootGen Generation `bin:"off=8, siz=8"` + + ChunkRoot ObjID `bin:"off=10, siz=8"` + ChunkRootGen Generation `bin:"off=18, siz=8"` + + ExtentRoot ObjID `bin:"off=20, siz=8"` + ExtentRootGen Generation `bin:"off=28, siz=8"` + + FSRoot ObjID `bin:"off=30, siz=8"` + FSRootGen Generation `bin:"off=38, siz=8"` + + DevRoot ObjID `bin:"off=40, siz=8"` + DevRootGen Generation `bin:"off=48, siz=8"` + + ChecksumRoot ObjID `bin:"off=50, siz=8"` + ChecksumRootGen Generation `bin:"off=58, siz=8"` + + TotalBytes uint64 `bin:"off=60, siz=8"` + BytesUsed uint64 `bin:"off=68, siz=8"` + NumDevices uint64 `bin:"off=70, siz=8"` + + Unused [8 * 4]byte `bin:"off=78, siz=20"` + + TreeRootLevel uint8 `bin:"off=98, siz=1"` + ChunkRootLevel uint8 `bin:"off=99, siz=1"` + ExtentRootLevel uint8 `bin:"off=9a, siz=1"` + FSRootLevel uint8 `bin:"off=9b, siz=1"` + DevRootLevel uint8 `bin:"off=9c, siz=1"` + ChecksumRootLevel uint8 `bin:"off=9d, siz=1"` + + Padding [10]byte `bin:"off=9e, siz=a"` + binstruct.End `bin:"off=a8"` +} + +type IncompatFlags uint64 + +const ( + FeatureIncompatMixedBackref = IncompatFlags(1 << iota) + FeatureIncompatDefaultSubvol + FeatureIncompatMixedGroups + FeatureIncompatCompressLZO + FeatureIncompatCompressZSTD + FeatureIncompatBigMetadata // buggy + FeatureIncompatExtendedIRef + FeatureIncompatRAID56 + FeatureIncompatSkinnyMetadata + FeatureIncompatNoHoles + FeatureIncompatMetadataUUID + FeatureIncompatRAID1C34 + FeatureIncompatZoned + FeatureIncompatExtentTreeV2 +) + +var incompatFlagNames = []string{ + "FeatureIncompatMixedBackref", + "FeatureIncompatDefaultSubvol", + "FeatureIncompatMixedGroups", + "FeatureIncompatCompressLZO", + "FeatureIncompatCompressZSTD", + "FeatureIncompatBigMetadata ", + "FeatureIncompatExtendedIRef", + "FeatureIncompatRAID56", + "FeatureIncompatSkinnyMetadata", + "FeatureIncompatNoHoles", + "FeatureIncompatMetadataUUID", + "FeatureIncompatRAID1C34", + "FeatureIncompatZoned", + "FeatureIncompatExtentTreeV2", +} + +func (f IncompatFlags) Has(req IncompatFlags) bool { return f&req == req } +func (f IncompatFlags) String() string { return util.BitfieldString(f, incompatFlagNames) } diff --git a/pkg/btrfs/types_uuid.go b/pkg/btrfs/types_uuid.go deleted file mode 100644 index b9e3e0c..0000000 --- a/pkg/btrfs/types_uuid.go +++ /dev/null @@ -1,24 +0,0 @@ -package btrfs - -import ( - "bytes" - "encoding/hex" - "strings" -) - -type UUID [16]byte - -func (uuid UUID) String() string { - str := hex.EncodeToString(uuid[:]) - return strings.Join([]string{ - str[:8], - str[8:12], - str[12:16], - str[16:20], - str[20:32], - }, "-") -} - -func (a UUID) Equal(b UUID) bool { - return bytes.Equal(a[:], b[:]) -} diff --git a/pkg/btrfs/util.go b/pkg/btrfs/util.go index 04462f8..312ec75 100644 --- a/pkg/btrfs/util.go +++ b/pkg/btrfs/util.go @@ -1,5 +1,9 @@ package btrfs +import ( + "golang.org/x/exp/constraints" +) + func inSlice[T comparable](needle T, haystack []T) bool { for _, straw := range haystack { if needle == straw { @@ -8,3 +12,10 @@ func inSlice[T comparable](needle T, haystack []T) bool { } return false } + +func max[T constraints.Ordered](a, b T) T { + if a > b { + return a + } + return b +} -- cgit v1.2.3-2-g168b