m/p/gpt: add GPT package
This introduces our own GPT package. It will be used for provisioning
and Metropolis images.
Change-Id: I905cd5d540673fd4b69c01d8975f98b88e24edd4
Reviewed-on: https://review.monogon.dev/c/monogon/+/956
Tested-by: Jenkins CI
Reviewed-by: Sergiusz Bazanski <serge@monogon.tech>
diff --git a/metropolis/pkg/gpt/gpt.go b/metropolis/pkg/gpt/gpt.go
new file mode 100644
index 0000000..5660237
--- /dev/null
+++ b/metropolis/pkg/gpt/gpt.go
@@ -0,0 +1,727 @@
+// Package gpt implements reading and writing GUID Partition Tables as specified
+// in the UEFI Specification. It only implements up to 128 partitions per table
+// (same as most other implementations) as more would require a dynamic table
+// size, significantly complicating the code for little gain.
+package gpt
+
+import (
+ "bytes"
+ "encoding/binary"
+ "errors"
+ "fmt"
+ "hash/crc32"
+ "io"
+ "sort"
+ "strings"
+ "unicode/utf16"
+
+ "github.com/google/uuid"
+)
+
+var gptSignature = [8]byte{'E', 'F', 'I', ' ', 'P', 'A', 'R', 'T'}
+var gptRevision uint32 = 0x00010000 // First 2 bytes major, second 2 bytes minor
+
+// See UEFI Specification 2.9 Table 5-5
+type header struct {
+ Signature [8]byte
+ Revision uint32
+ HeaderSize uint32
+ HeaderCRC32 uint32
+ _ [4]byte
+
+ HeaderBlock uint64
+ AlternateHeaderBlock uint64
+ FirstUsableBlock uint64
+ LastUsableBlock uint64
+
+ ID [16]byte
+
+ PartitionEntriesStartBlock uint64
+ PartitionEntryCount uint32
+ PartitionEntrySize uint32
+ PartitionEntriesCRC32 uint32
+}
+
+// See UEFI Specification 2.9 Table 5-6
+type partition struct {
+ Type [16]byte
+ ID [16]byte
+ FirstBlock uint64
+ LastBlock uint64
+ Attributes uint64
+ Name [36]uint16
+}
+
+var (
+ PartitionTypeEFISystem = uuid.MustParse("C12A7328-F81F-11D2-BA4B-00A0C93EC93B")
+)
+
+var zeroUUID = [16]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
+
+// Attribute is a bitfield of attributes set on a partition. Bits 0 to 47 are
+// reserved for UEFI specification use and all current assignments are in the
+// following const block. Bits 48 to 64 are available for per-Type use by
+// the organization controlling the partition Type.
+type Attribute uint64
+
+const (
+ // AttrRequiredPartition indicates that this partition is required for the
+ // platform to function. Mostly used by vendors to mark things like recovery
+ // partitions.
+ AttrRequiredPartition = 1 << 0
+ // AttrNoBlockIOProto indicates that EFI firmware must not provide an EFI
+ // block device (EFI_BLOCK_IO_PROTOCOL) for this partition.
+ AttrNoBlockIOProto = 1 << 1
+ // AttrLegacyBIOSBootable indicates to special-purpose software outside of
+ // UEFI that this partition can be booted using a traditional PC BIOS.
+ // Don't use this unless you know that you need it specifically.
+ AttrLegacyBIOSBootable = 1 << 2
+)
+
+// PerTypeAttrs returns the top 24 bits which are reserved for custom per-Type
+// attributes. The top 8 bits of the returned uint32 are always 0.
+func (a Attribute) PerTypeAttrs() uint32 {
+ return uint32(a >> 48)
+}
+
+// SetPerTypeAttrs sets the top 24 bits which are reserved for custom per-Type
+// attributes. It does not touch the lower attributes which are specified by the
+// UEFI specification. The top 8 bits of v are silently discarded.
+func (a *Attribute) SetPerTypeAttrs(v uint32) {
+ *a &= 0x000000FF_FFFFFFFF
+ *a |= Attribute(v) << 48
+}
+
+type Partition struct {
+ // Name of the partition, will be truncated if it expands to more than 36
+ // UTF-16 code points. Not all systems can display non-BMP code points.
+ Name string
+ // Type is the type of Table partition, can either be one of the predefined
+ // constants by the UEFI specification or a custom type identifier.
+ // Note that the all-zero UUID denotes an empty partition slot, so this
+ // MUST be set to something, otherwise it is not treated as a partition.
+ Type uuid.UUID
+ // ID is a unique identifier for this specific partition. It should be
+ // changed when cloning the partition.
+ ID uuid.UUID
+ // The first logical block of the partition (inclusive)
+ FirstBlock uint64
+ // The last logical block of the partition (inclusive)
+ LastBlock uint64
+ // Bitset of attributes of this partition.
+ Attributes Attribute
+}
+
+// SizeBlocks returns the size of the partition in blocks
+func (p *Partition) SizeBlocks() uint64 {
+ return 1 + p.LastBlock - p.FirstBlock
+}
+
+// IsUnused checks if the partition is unused, i.e. it is nil or its type is
+// the null UUID.
+func (p *Partition) IsUnused() bool {
+ if p == nil {
+ return true
+ }
+ return p.Type == zeroUUID
+}
+
+type Table struct {
+ // ID is the unique identifier of this specific disk / GPT.
+ // If this is left uninitialized/all-zeroes a new random ID is automatically
+ // generated when writing.
+ ID uuid.UUID
+
+ // Data put at the start of the very first block. Gets loaded and executed
+ // by a legacy BIOS bootloader. This can be used to make GPT-partitioned
+ // disks bootable by legacy systems or display a nice error message.
+ // Maximum length is 440 bytes, if that is exceeded Write returns an error.
+ // Should be left empty if the device is not bootable and/or compatibility
+ // with BIOS booting is not required. Only useful on x86 systems.
+ BootCode []byte
+
+ // BlockSize contains the logical block size of the block device. It must
+ // be a power of two equal to or larger than 512.
+ BlockSize int64
+ // BlockCount contains the number of logical blocks on the block device.
+ // BlockCount times BlockSize is the size of the block device in bytes.
+ BlockCount int64
+
+ // Partitions contains the list of partitions in this table. This is
+ // artificially limited to 128 partitions.
+ Partitions []*Partition
+}
+type addOptions struct {
+ preferEnd bool
+ keepEmptyEntries bool
+ alignment int64
+}
+
+// AddOption is a bitset controlling various
+type AddOption func(*addOptions)
+
+// WithPreferEnd tries to put the partition as close to the end as possible
+// instead of as close to the start.
+func WithPreferEnd() AddOption {
+ return func(options *addOptions) {
+ options.preferEnd = true
+ }
+}
+
+// WithKeepEmptyEntries does not fill up empty entries which are followed by
+// filled ones. It always appends the partition after the last used entry.
+// Without this flag, the partition is placed in the first empty entry.
+func WithKeepEmptyEntries() AddOption {
+ return func(options *addOptions) {
+ options.keepEmptyEntries = true
+ }
+}
+
+// WithAlignment allows aligning the partition start block to a non-default
+// value. By default, these are aligned to 1MiB.
+// Only use this flag if you are certain you need it, it can cause quite severe
+// performance degradation under certain conditions.
+func WithAlignment(alignmenet int64) AddOption {
+ return func(options *addOptions) {
+ options.alignment = alignmenet
+ }
+}
+
+// AddPartition takes a pointer to a partition and adds it, placing it into
+// the first (or last using WithPreferEnd) continuous free space which fits it.
+// It writes the placement information (FirstBlock, LastBlock) back to p.
+// By default, AddPartition aligns FirstBlock to 1MiB boundaries, but this can
+// be overridden using WithAlignment.
+func (g *Table) AddPartition(p *Partition, size int64, options ...AddOption) error {
+ if g.BlockSize < 512 {
+ return errors.New("block size is smaller than 512 bytes, this is unsupported")
+ }
+ var opts addOptions
+ // Align to 1MiB or the block size, whichever is bigger
+ opts.alignment = 1 * 1024 * 1024
+ if g.BlockSize > opts.alignment {
+ opts.alignment = g.BlockSize
+ }
+ for _, o := range options {
+ o(&opts)
+ }
+ if opts.alignment%g.BlockSize != 0 {
+ return fmt.Errorf("requested alignment (%d bytes) is not an integer multiple of the block size (%d), unable to align", opts.alignment, g.BlockSize)
+ }
+ // Number of blocks the partition should occupy, rounded up.
+ blocks := (size + g.BlockSize - 1) / g.BlockSize
+ fs, _, err := g.GetFreeSpaces()
+ if err != nil {
+ return fmt.Errorf("unable to determine free space: %v", err)
+ }
+ if opts.preferEnd {
+ // Reverse fs slice to start iteration at the end
+ for i, j := 0, len(fs)-1; i < j; i, j = i+1, j-1 {
+ fs[i], fs[j] = fs[j], fs[i]
+ }
+ }
+ var maxFreeBlocks int64
+ for _, freeInt := range fs {
+ start := freeInt[0]
+ end := freeInt[1]
+ freeBlocks := end - start
+ // Align start properly
+ paddingBlocks := (-start) % (opts.alignment / g.BlockSize)
+ freeBlocks -= paddingBlocks
+ start += paddingBlocks
+ if maxFreeBlocks < freeBlocks {
+ maxFreeBlocks = freeBlocks
+ }
+ if freeBlocks >= blocks {
+ if !opts.preferEnd {
+ p.FirstBlock = uint64(start)
+ p.LastBlock = uint64(start + blocks)
+ } else {
+ // Realign FirstBlock. This will always succeed as
+ // there is enough space to align to the start.
+ moveLeft := (end - blocks - 1) % (opts.alignment / g.BlockSize)
+ p.FirstBlock = uint64(end - (blocks + 1 + moveLeft))
+ p.LastBlock = uint64(end - (1 + moveLeft))
+ }
+ newPartPos := -1
+ if !opts.keepEmptyEntries {
+ for i, part := range g.Partitions {
+ if part.IsUnused() {
+ newPartPos = i
+ break
+ }
+ }
+ }
+ if newPartPos == -1 {
+ g.Partitions = append(g.Partitions, p)
+ } else {
+ g.Partitions[newPartPos] = p
+ }
+ return nil
+ }
+ }
+
+ return fmt.Errorf("no space for partition of %d blocks, largest continuous free space after alignment is %d blocks", blocks, maxFreeBlocks)
+}
+
+// FirstUsableBlock returns the first usable (i.e. a partition can start there)
+// block.
+func (g *Table) FirstUsableBlock() int64 {
+ partitionEntryBlocks := (16384 + g.BlockSize - 1) / g.BlockSize
+ return 2 + partitionEntryBlocks
+}
+
+// LastUsableBlock returns the last usable (i.e. a partition can end there)
+// block. This block is inclusive.
+func (g *Table) LastUsableBlock() int64 {
+ partitionEntryBlocks := (16384 + g.BlockSize - 1) / g.BlockSize
+ return g.BlockCount - (2 + partitionEntryBlocks)
+}
+
+// GetFreeSpaces returns a slice of tuples, each containing a half-closed
+// interval of logical blocks not occupied by the GPT itself or any partition.
+// The returned intervals are always in ascending order as well as
+// non-overlapping. It also returns if it detected any overlaps between
+// partitions or partitions and the GPT. It returns an error if and only if any
+// partition has its FirstBlock before the LastBlock or exceeds the amount of
+// blocks on the block device.
+//
+// Note that the most common use cases for this function are covered by
+// AddPartition, you're encouraged to use it instead.
+func (g *Table) GetFreeSpaces() ([][2]int64, bool, error) {
+ // This implements an efficient algorithm for finding free intervals given
+ // a set of potentially overlapping occupying intervals. It uses O(n*log n)
+ // time for n being the amount of intervals, i.e. partitions. It uses O(n)
+ // additional memory. This makes it de facto infinitely scalable in the
+ // context of partition tables as the size of the block device is not part
+ // of its cyclomatic complexity and O(n*log n) is tiny for even very big
+ // partition tables.
+
+ // startBlocks contains the start blocks (inclusive) of all occupied
+ // intervals.
+ var startBlocks []int64
+ // endBlocks contains the end blocks (exclusive!) of all occupied intervals.
+ // The interval at index i is given by [startBlock[i], endBlock[i]).
+ var endBlocks []int64
+
+ // Reserve the primary GPT interval including the protective MBR.
+ startBlocks = append(startBlocks, 0)
+ endBlocks = append(endBlocks, g.FirstUsableBlock())
+
+ // Reserve the alternate GPT interval (needs +1 for exclusive interval)
+ startBlocks = append(startBlocks, g.LastUsableBlock()+1)
+ endBlocks = append(endBlocks, g.BlockCount)
+
+ for i, part := range g.Partitions {
+ if part.IsUnused() {
+ continue
+ }
+ // Bail if partition does not contain a valid interval. These are open
+ // intervals, thus part.FirstBlock == part.LastBlock denotes a valid
+ // partition with a size of one block.
+ if part.FirstBlock > part.LastBlock {
+ return nil, false, fmt.Errorf("partition %d has a LastBlock smaller than its FirstBlock, its interval is [%d, %d]", i, part.FirstBlock, part.LastBlock)
+ }
+ if part.FirstBlock >= uint64(g.BlockCount) || part.LastBlock >= uint64(g.BlockCount) {
+ return nil, false, fmt.Errorf("partition %d exceeds the block count of the block device", i)
+ }
+ startBlocks = append(startBlocks, int64(part.FirstBlock))
+ // Algorithm needs open-closed intervals, thus add +1 to the end.
+ endBlocks = append(endBlocks, int64(part.LastBlock)+1)
+ }
+ // Sort both sets of blocks independently in ascending order. Note that it
+ // is now no longer possible to extract the original intervals. Integers
+ // have no identity thus it doesn't matter if the sort is stable or not.
+ sort.Slice(startBlocks, func(i, j int) bool { return startBlocks[i] < startBlocks[j] })
+ sort.Slice(endBlocks, func(i, j int) bool { return endBlocks[i] < endBlocks[j] })
+
+ var freeSpaces [][2]int64
+
+ // currentIntervals contains the number of intervals which contain the
+ // position currently being iterated over. If currentIntervals is ever
+ // bigger than 1, there is overlap within the given intervals.
+ currentIntervals := 0
+ var hasOverlap bool
+
+ // Iterate for as long as there are interval boundaries to be processed.
+ for len(startBlocks) != 0 || len(endBlocks) != 0 {
+ // Short-circuit boundary processing. If an interval ends at x and the
+ // next one starts at x (this is using half-open intervals), it would
+ // otherwise perform useless processing as well as create an empty free
+ // interval which would then need to be filtered back out.
+ if len(startBlocks) != 0 && len(endBlocks) != 0 && startBlocks[0] == endBlocks[0] {
+ startBlocks = startBlocks[1:]
+ endBlocks = endBlocks[1:]
+ continue
+ }
+ // Pick the lowest boundary from either startBlocks or endBlocks,
+ // preferring endBlocks if they are equal. Don't try to pick from empty
+ // slices.
+ if (len(startBlocks) != 0 && len(endBlocks) != 0 && startBlocks[0] < endBlocks[0]) || len(endBlocks) == 0 {
+ // If currentIntervals == 0 a free space region ends here.
+ // Since this algorithm creates the free space interval at the end
+ // of an occupied interval, for the first interval there is no free
+ // space entry. But in this case it's fine to just ignore it as the
+ // first interval always starts at 0 because of the GPT.
+ if currentIntervals == 0 && len(freeSpaces) != 0 {
+ freeSpaces[len(freeSpaces)-1][1] = startBlocks[0]
+ }
+ // This is the start of an interval, increase the number of active
+ // intervals.
+ currentIntervals++
+ hasOverlap = hasOverlap || currentIntervals > 1
+ // Drop processed startBlock from slice.
+ startBlocks = startBlocks[1:]
+ } else {
+ // This is the end of an interval, decrease the number of active
+ // intervals.
+ currentIntervals--
+ // If currentIntervals == 0 a free space region starts here.
+ // Same as with the startBlocks, ignore a potential free block after
+ // the final range as the GPT occupies the last blocks anyway.
+ if currentIntervals == 0 && len(startBlocks) != 0 {
+ freeSpaces = append(freeSpaces, [2]int64{endBlocks[0], 0})
+ }
+ endBlocks = endBlocks[1:]
+ }
+ }
+ return freeSpaces, hasOverlap, nil
+}
+
+// Overhead returns the number of blocks the GPT partitioning itself consumes,
+// i.e. aren't usable for user data.
+func Overhead(blockSize int64) int64 {
+ // 3 blocks + 2x 16384 bytes (partition entry space)
+ partitionEntryBlocks := (16384 + blockSize - 1) / blockSize
+ return 3 + (2 * partitionEntryBlocks)
+}
+
+// Write writes a list of GPT partitions with a protective MBR to the given
+// WriteSeeker. It must have a defined end, i.e. w.Seek(-x, io.SeekEnd) must
+// seek to x bytes before the end of the disk. If gpt.ID or any of the
+// partition IDs are the all-zero UUID, a new random one is generated and
+// written back. If the output is supposed to be reproducible, generate the
+// UUIDs beforehand.
+func Write(w io.WriteSeeker, gpt *Table) error {
+ if gpt.BlockSize < 512 {
+ return errors.New("block size is smaller than 512 bytes, this is unsupported")
+ }
+ // Layout looks as follows:
+ // Block 0: Protective MBR
+ // Block 1: GPT Header
+ // Block 2-(16384 bytes): GPT partition entries
+ // Block (16384 bytes)-n: GPT partition entries alternate copy
+ // Block n: GPT Header alternate copy
+ if len(gpt.Partitions) > 128 {
+ return errors.New("Bigger-than default GPTs (>128 partitions) are unimplemented")
+ }
+
+ partitionEntryBlocks := (16384 + gpt.BlockSize - 1) / gpt.BlockSize
+ if gpt.BlockCount < 3+(2*partitionEntryBlocks) {
+ return errors.New("not enough blocks to write GPT")
+ }
+
+ if gpt.ID == zeroUUID {
+ gpt.ID = uuid.New()
+ }
+
+ partSize := binary.Size(partition{})
+ slotCount := 128
+
+ var partitionEntriesData bytes.Buffer
+ for i := 0; i < slotCount; i++ {
+ if len(gpt.Partitions) <= i || gpt.Partitions[i] == nil {
+ partitionEntriesData.Write(make([]byte, partSize))
+ continue
+ }
+ p := gpt.Partitions[i]
+ if p.ID == zeroUUID {
+ p.ID = uuid.New()
+ }
+ rawP := partition{
+ Type: mangleUUID(p.Type),
+ ID: mangleUUID(p.ID),
+ FirstBlock: p.FirstBlock,
+ LastBlock: p.LastBlock,
+ Attributes: uint64(p.Attributes),
+ }
+ nameUTF16 := utf16.Encode([]rune(p.Name))
+ // copy will automatically truncate if target is too short
+ copy(rawP.Name[:], nameUTF16)
+ binary.Write(&partitionEntriesData, binary.LittleEndian, rawP)
+ }
+
+ hdr := header{
+ Signature: gptSignature,
+ Revision: gptRevision,
+ HeaderSize: uint32(binary.Size(&header{})),
+ ID: mangleUUID(gpt.ID),
+
+ PartitionEntryCount: uint32(slotCount),
+ PartitionEntrySize: uint32(partSize),
+
+ FirstUsableBlock: uint64(2 + partitionEntryBlocks),
+ LastUsableBlock: uint64(gpt.BlockCount - (2 + partitionEntryBlocks)),
+ }
+ hdr.PartitionEntriesCRC32 = crc32.ChecksumIEEE(partitionEntriesData.Bytes())
+
+ hdrChecksum := crc32.NewIEEE()
+
+ // Write alternate header first, as otherwise resizes are unsafe. If the
+ // alternate is currently not at the end of the block device, it cannot
+ // be found. Thus if the write operation is aborted abnormally, the
+ // primary GPT is corrupted and the alternate cannot be found because it
+ // is not at its canonical location. Rewriting the alternate first avoids
+ // this problem.
+
+ // Alternate header
+ if _, err := w.Seek((gpt.LastUsableBlock()+1)*gpt.BlockSize, io.SeekStart); err != nil {
+ return fmt.Errorf("failed to seek to end of block device: %w", err)
+ }
+ hdr.HeaderBlock = uint64(gpt.BlockCount - 1)
+ hdr.AlternateHeaderBlock = 1
+ hdr.PartitionEntriesStartBlock = uint64(gpt.BlockCount - (1 + partitionEntryBlocks))
+
+ hdrChecksum.Reset()
+ hdr.HeaderCRC32 = 0
+ binary.Write(hdrChecksum, binary.LittleEndian, &hdr)
+ hdr.HeaderCRC32 = hdrChecksum.Sum32()
+
+ if _, err := w.Write(partitionEntriesData.Bytes()); err != nil {
+ return fmt.Errorf("failed to write alternate partition entries: %w", err)
+ }
+ if _, err := w.Seek((gpt.BlockCount-1)*gpt.BlockSize, io.SeekStart); err != nil {
+ return fmt.Errorf("failed to seek to end of block device: %w", err)
+ }
+
+ if err := binary.Write(w, binary.LittleEndian, &hdr); err != nil {
+ return fmt.Errorf("failed to write alternate header: %w", err)
+ }
+ if _, err := w.Write(make([]byte, gpt.BlockSize-int64(binary.Size(hdr)))); err != nil {
+ return fmt.Errorf("failed to write padding: %v", err)
+ }
+
+ // Primary header
+ if _, err := w.Seek(0, io.SeekStart); err != nil {
+ return fmt.Errorf("failed to seek to end of block device: %w", err)
+ }
+ hdr.HeaderBlock = 1
+ hdr.AlternateHeaderBlock = uint64(gpt.BlockCount - 1)
+ hdr.PartitionEntriesStartBlock = 2
+
+ hdrChecksum.Reset()
+ hdr.HeaderCRC32 = 0
+ binary.Write(hdrChecksum, binary.LittleEndian, &hdr)
+ hdr.HeaderCRC32 = hdrChecksum.Sum32()
+
+ if err := makeProtectiveMBR(w, gpt.BlockCount, gpt.BootCode); err != nil {
+ return fmt.Errorf("failed to write first block: %w", err)
+ }
+
+ if err := binary.Write(w, binary.LittleEndian, &hdr); err != nil {
+ return fmt.Errorf("failed to write primary header: %w", err)
+ }
+ if _, err := w.Write(make([]byte, gpt.BlockSize-int64(binary.Size(hdr)))); err != nil {
+ return fmt.Errorf("failed to write padding: %v", err)
+ }
+ if _, err := w.Write(partitionEntriesData.Bytes()); err != nil {
+ return fmt.Errorf("failed to write primary partition entries: %w", err)
+ }
+ return nil
+}
+
+// Read reads a Table from a block device given its block size and count.
+func Read(r io.ReadSeeker, blockSize int64, blockCount int64) (*Table, error) {
+ if Overhead(blockSize) > blockCount {
+ return nil, errors.New("disk cannot contain a GPT as the block count is too small to store one")
+ }
+ if _, err := r.Seek(0, io.SeekStart); err != nil {
+ return nil, fmt.Errorf("failed to seek to block 0: %w", err)
+ }
+ zeroBlock := make([]byte, blockSize)
+ if _, err := io.ReadFull(r, zeroBlock); err != nil {
+ return nil, fmt.Errorf("failed to read first two blocks: %w", err)
+ }
+
+ var m mbr
+ if err := binary.Read(bytes.NewReader(zeroBlock[:512]), binary.LittleEndian, &m); err != nil {
+ panic(err) // Read is from memory and with enough data
+ }
+ // The UEFI standard says that the only acceptable MBR for a GPT-partitioned
+ // device is a pure protective MBR with one partition of type 0xEE covering
+ // the entire disk. But reality is sadly not so simple. People have come up
+ // with hacks like Hybrid MBR which is basically a way to expose partitions
+ // as both GPT partitions and MBR partitions. There are also GPTs without
+ // any MBR at all.
+ // Following the standard strictly when reading means that this library
+ // would fail to read valid GPT disks where such schemes are employed.
+ // On the other hand just looking at the GPT signature is also dangerous
+ // as not all tools clear the second block where the GPT resides when
+ // writing an MBR, which results in reading a wrong/obsolete GPT.
+ // As a pragmatic solution this library treats any disk as GPT-formatted if
+ // the first block does not contain an MBR signature or at least one MBR
+ // partition has type 0xEE (GPT). It does however not care in which slot
+ // this partition is or if it begins at the start of the disk.
+ //
+ // Note that the block signatures for MBR and FAT are shared. This is a
+ // historical artifact from DOS. It is not reliably possible to
+ // differentiate the two as either has boot code where the other has meta-
+ // data and both lack any checksums. Because the MBR partition table is at
+ // the very end of the FAT bootcode section the following code always
+ // assumes that it is dealing with an MBR. This is both more likely and
+ // the 0xEE marker is rarer and thus more specific than FATs 0x00, 0x80 and
+ // 0x02.
+ var bootCode []byte
+ hasDOSBootSig := m.Signature == mbrSignature
+ if hasDOSBootSig {
+ var isGPT bool
+ for _, p := range m.PartitionRecords {
+ if p.Type == 0xEE {
+ isGPT = true
+ }
+ }
+ // Note that there is a small but non-zero chance that isGPT is true
+ // for a raw FAT filesystem if the bootcode contains a "valid" MBR.
+ // The next error message mentions that possibility.
+ if !isGPT {
+ return nil, errors.New("block device contains an MBR table without a GPT marker or a raw FAT filesystem")
+ }
+ // Trim right zeroes away as they are padded back when writing. This
+ // makes BootCode empty when it is all-zeros, making it easier to work
+ // with while still round-tripping correctly.
+ bootCode = bytes.TrimRight(m.BootCode[:], "\x00")
+ }
+ // Read the primary GPT. If it is damaged and/or broken, read the alternate.
+ primaryGPT, err := readSingleGPT(r, blockSize, blockCount, 1)
+ if err != nil {
+ alternateGPT, err2 := readSingleGPT(r, blockSize, blockCount, blockCount-1)
+ if err2 != nil {
+ return nil, fmt.Errorf("failed to read both GPTs: primary GPT (%v), secondary GPT (%v)", err, err2)
+ }
+ alternateGPT.BootCode = bootCode
+ return alternateGPT, nil
+ }
+ primaryGPT.BootCode = bootCode
+ return primaryGPT, nil
+}
+
+func readSingleGPT(r io.ReadSeeker, blockSize int64, blockCount int64, headerBlockPos int64) (*Table, error) {
+ if _, err := r.Seek(blockSize*headerBlockPos, io.SeekStart); err != nil {
+ return nil, fmt.Errorf("failed to seek to block %d: %w", headerBlockPos, err)
+ }
+ hdrBlock := make([]byte, blockSize)
+ if _, err := io.ReadFull(r, hdrBlock); err != nil {
+ return nil, fmt.Errorf("failed to read GPT header block: %w", err)
+ }
+ hdrBlockReader := bytes.NewReader(hdrBlock)
+ var hdr header
+ if err := binary.Read(hdrBlockReader, binary.LittleEndian, &hdr); err != nil {
+ panic(err) // Read from memory with enough bytes, should not fail
+ }
+ if hdr.Signature != gptSignature {
+ return nil, errors.New("no GPT signature found")
+ }
+ if hdr.HeaderSize < uint32(binary.Size(hdr)) {
+ return nil, fmt.Errorf("GPT header size is too small, likely corrupted")
+ }
+ if int64(hdr.HeaderSize) > blockSize {
+ return nil, fmt.Errorf("GPT header size is bigger than block size, likely corrupted")
+ }
+ // Use reserved bytes to hash, but do not expose them to the user.
+ // If someone has a need to process them, they should extend this library
+ // with whatever an updated UEFI specification contains.
+ // It has been considered to store these in the user-exposed GPT struct to
+ // be able to round-trip them cleanly, but there is significant complexity
+ // and risk involved in doing so.
+ reservedBytes := hdrBlock[binary.Size(hdr):hdr.HeaderSize]
+ hdrExpectedCRC := hdr.HeaderCRC32
+ hdr.HeaderCRC32 = 0
+ hdrCRC := crc32.NewIEEE()
+ binary.Write(hdrCRC, binary.LittleEndian, &hdr)
+ hdrCRC.Write(reservedBytes)
+ if hdrCRC.Sum32() != hdrExpectedCRC {
+ return nil, fmt.Errorf("GPT header checksum mismatch, probably corrupted")
+ }
+ if hdr.HeaderBlock != uint64(headerBlockPos) {
+ return nil, errors.New("GPT header indicates wrong block")
+ }
+ if hdr.PartitionEntrySize < uint32(binary.Size(partition{})) {
+ return nil, errors.New("partition entry size too small")
+ }
+ if hdr.PartitionEntriesStartBlock > uint64(blockCount) {
+ return nil, errors.New("partition entry start block is out of range")
+ }
+ // Sanity-check total size of the partition entry area. Otherwise, this is a
+ // trivial DoS as it could cause allocation of gigabytes of memory.
+ // 4MiB is equivalent to around 45k partitions at the current size.
+ // I know of no operating system which would handle even a fraction of this.
+ if uint64(hdr.PartitionEntryCount)*uint64(hdr.PartitionEntrySize) > 4*1024*1024 {
+ return nil, errors.New("partition entry area bigger than 4MiB, refusing to read")
+ }
+ partitionEntryData := make([]byte, hdr.PartitionEntrySize*hdr.PartitionEntryCount)
+ if _, err := r.Seek(blockSize*int64(hdr.PartitionEntriesStartBlock), io.SeekStart); err != nil {
+ return nil, fmt.Errorf("failed to seek to partition entry start block: %w", err)
+ }
+ if _, err := io.ReadFull(r, partitionEntryData); err != nil {
+ return nil, fmt.Errorf("failed to read partition entries: %w", err)
+ }
+ if crc32.ChecksumIEEE(partitionEntryData) != hdr.PartitionEntriesCRC32 {
+ return nil, errors.New("GPT partition entry table checksum mismatch")
+ }
+ var g Table
+ g.ID = unmangleUUID(hdr.ID)
+ g.BlockSize = blockSize
+ g.BlockCount = blockCount
+ for i := uint32(0); i < hdr.PartitionEntryCount; i++ {
+ entryReader := bytes.NewReader(partitionEntryData[i*hdr.PartitionEntrySize : (i+1)*hdr.PartitionEntrySize])
+ var part partition
+ if err := binary.Read(entryReader, binary.LittleEndian, &part); err != nil {
+ panic(err) // Should not happen
+ }
+ // If the partition type is the all-zero UUID, this slot counts as
+ // unused.
+ if part.Type == zeroUUID {
+ g.Partitions = append(g.Partitions, nil)
+ continue
+ }
+ g.Partitions = append(g.Partitions, &Partition{
+ ID: unmangleUUID(part.ID),
+ Type: unmangleUUID(part.Type),
+ Name: strings.TrimRight(string(utf16.Decode(part.Name[:])), "\x00"),
+ FirstBlock: part.FirstBlock,
+ LastBlock: part.LastBlock,
+ Attributes: Attribute(part.Attributes),
+ })
+ }
+ // Remove long list of nils at the end as it's inconvenient to work with
+ // (append doesn't work, debug prints are very long) and it round-trips
+ // correctly even without it as it gets zero-padded when writing anyway.
+ var maxValidPartition int
+ for i, p := range g.Partitions {
+ if !p.IsUnused() {
+ maxValidPartition = i
+ }
+ }
+ g.Partitions = g.Partitions[:maxValidPartition+1]
+ return &g, nil
+}
+
+var mixedEndianTranspose = []int{3, 2, 1, 0, 5, 4, 7, 6, 8, 9, 10, 11, 12, 13, 14, 15}
+
+// mangleUUID encodes a normal UUID into a "mixed-endian" UUID. This just means
+// shuffling the bytes around in a specific way. Thank Microsoft for this
+// idiosyncrasy.
+func mangleUUID(u uuid.UUID) (o [16]byte) {
+ for dest, from := range mixedEndianTranspose {
+ o[dest] = u[from]
+ }
+ return
+}
+
+// unmangleUUID does the reverse transformation of mangleUUID
+func unmangleUUID(i [16]byte) (o uuid.UUID) {
+ for from, dest := range mixedEndianTranspose {
+ o[dest] = i[from]
+ }
+ return
+}