# MBR and GPT in linux kernel
###### tags: `mbr` `gpt`

> [name=ztex]

:::info
MBR (Master Boot Record) and GPT (GUID Partition Table) are two different ways of **storing the partitioning information on a drive**. This information includes **where partitions start and begin**, so your operating system knows **which sectors belong to each partition** and **which partition is bootable**. This is why you have to choose MBR or GPT before creating partitions on a drive.
:::

## MBR (Master Boot Record)
:::info
MBR does have its limitations. For starters, MBR only works with disks **up to 2 TB** in size. MBR also only supports **up to four primary partitions**—if you want more, you have to make one of your primary partitions an “extended partition” and create logical partitions inside it. This is a silly little hack and shouldn’t be necessary.
:::
## GPT (GUID Partition Table)
* [gpt spec](https://www.intel.com/content/dam/support/us/en/documents/motherboards/server/sb/gpt_white_paper_1_1.pdf)
* [How can I quickly copy a GPT partition scheme from one hard drive to another?](https://askubuntu.com/questions/57908/how-can-i-quickly-copy-a-gpt-partition-scheme-from-one-hard-drive-to-another)

We can find related code in `linux-4.4.x/block/partitions/efi.h`

In the Newbie program I got two files: `3T_gpt_head` and `3T_gpt_tail`.
You can get from this [link](https://drive.google.com/file/d/1tgR_01PEJAksvYad_v8Eh19qxOSZYYw8/view?usp=sharing)

$> wc -c < 3T_gpt_front
H bytes
$> dd if=3T_gpt_fron of=/dev/sata4 bs=1 count=H

$> wc -c < 3T_gpt_tail
T bytes
$> fdisk -l /dev/sata4
DISKSIZE
$> dd if=3T_gpt_tail of=/dev/sata4 bs=1 count=T seek=DISKSIZE-T


* Primary GPT Header

$> xxd 3T_gpt_front
00000200: 4546 4920 5041 5254 0000 0100 5c00 0000  EFI PART....\...
00000210: daf0 f0b0 0000 0000 0100 0000 0000 0000  ................
00000220: afa3 505d 0100 0000 2200 0000 0000 0000  ..P]....".......
00000230: 8ea3 505d 0100 0000 4965 34ec a00e e744  ..P]....Ie4....D
00000240: 9aec 4c08 b487 8c8d 0200 0000 0000 0000  ..L.............
00000250: 8000 0000 8000 0000 8fc3 e2a1 0000 0000  ................


- [x] 0 (0x00) 8 bytes 4546 4920 5041 5254
- [x] 8 (0x08) 4 bytes 0000 0100 Revision (for GPT version 1.0 (through at least UEFI version 2.7 (May 2017)), the value is 00h 00h 01h 00h)
- [x] 12 (0x0C) 4 bytes 5c00 0000 Header size in little endian (in bytes, usually 5Ch 00h 00h 00h or 92 bytes)
- [ ] 16 (0x10) 4 bytes **daf0 f0b0** CRC32 of header (offset +0 up to header size) in little endian, with this field zeroed during calculation
- [x] 20 (0x14) 4 bytes 0000 0000 Reserved; must be zero
- [x] 24 (0x18) 8 bytes 0100 0000 0000 0000 Current LBA (location of this header copy)
- [x] 32 (0x20) 8 bytes afa3 505d 0100 0000 Backup LBA (location of the other header copy)
- [x] 40 (0x28) 8 bytes 2200 0000 0000 0000 First usable LBA for partitions (primary partition table last LBA + 1)
- [x] 48 (0x30) 8 bytes 8ea3 505d 0100 0000 Last usable LBA (secondary partition table first LBA − 1)
- [x] 56 (0x38) 16 bytes 4965 34ec a00e e744 9aec 4c08 b487 8c8d Disk GUID in mixed endian
- [x] 72 (0x48) 8 bytes 0200 0000 0000 0000 Starting LBA of array of partition entries (always 2 in primary copy)
- [ ] 80 (0x50) 4 bytes 8000 0000 Number of partition entries in array
- [x] 84 (0x54) 4 bytes 8000 0000 Size of a single partition entry (usually 80h or 128)
- [ ] 88 (0x58) 4 bytes 8fc3 e2a1 CRC32 of partition entries array in little endian
- [x] 92 (0x5C) * Reserved; must be zeroes for the rest of the block (420 bytes for a sector size of 512 bytes; but can be more with larger sector sizes)

so the primary GPT header looks check out.

* Secondary GPT header

4546 4920 5041 5254 0000 0100 5c00 0000  EFI PART....\...
42ef e487 0000 0000 afa3 505d 0100 0000  B.........P]....
0100 0000 0000 0000 2200 0000 0000 0000  ........".......
8ea3 505d 0100 0000 4965 34ec a00e e744  ..P]....Ie4....D
9aec 4c08 b487 8c8d 8fa3 505d 0100 0000  ..L.......P]....
8000 0000 8000 0000 8fc3 e2a1 0000 0000  ................

- [x] 0 (0x00) 8 bytes 4546 4920 5041 5254
- [x] 8 (0x08) 4 bytes 0000 0100 Revision (for GPT version 1.0 (through at least UEFI version 2.7 (May 2017)), the value is 00h 00h 01h 00h)
- [x] 12 (0x0C) 4 bytes 5c00 0000 Header size in little endian (in bytes, usually 5Ch 00h 00h 00h or 92 bytes)
- [ ] 16 (0x10) 4 bytes **42ef e487** CRC32 of header (offset +0 up to header size) in little endian, with this field zeroed during calculation
- [x] 20 (0x14) 4 bytes 0000 0000 Reserved; must be zero
- [x] 24 (0x18) 8 bytes afa3 505d 0100 0000 Current LBA (location of this header copy)
- [x] 32 (0x20) 8 bytes 0100 0000 0000 0000 Backup LBA (location of the other header copy)
- [x] 40 (0x28) 8 bytes 2200 0000 0000 0000 First usable LBA for partitions (primary partition table last LBA + 1)
- [x] 48 (0x30) 8 bytes 8ea3 505d 0100 0000 Last usable LBA (secondary partition table first LBA − 1)
- [x] 56 (0x38) 16 bytes 4965 34ec a00e e744 9aec 4c08 b487 8c8d Disk GUID in mixed endian
- [x] 72 (0x48) 8 bytes 8fa3 505d 0100 0000 Starting LBA of array of partition entries (always 2 in primary copy)
- [x] 80 (0x50) 4 bytes 8000 0000 Number of partition entries in array
- [x] 84 (0x54) 4 bytes 8000 0000 Size of a single partition entry (usually 80h or 128)
- [ ] 88 (0x58) 4 bytes 8fc3 e2a1 CRC32 of partition entries array in little endian
- [x] 92 (0x5C) * Reserved; must be zeroes for the rest of the block (420 bytes for a sector size of 512 bytes; but can be more with larger sector sizes)

> A GUID partition table scheme contains: Protective MBR, primary GPT, alternate(secondary) GPT
> A GPT contains: header, entries
> Primary header is located normally at LBA 0. entries are following after it, start from LBA2. 4 entries in a LBA.
> Each LBA 512 bytes
> Alternate GPT is normally at the end of the disk(not always held though)
> [name=ztex]

> GPT 就是 LBA 0 Protective MBR, LBA 1 一般是 primary GPT, 但還有一個備份, 叫做 alternate GPT(或者 secondary GPT). 一般在 disk 最後啦, 但不一定
> 一個 LBA size 是 512 bytes, 這在傳統上跟 sector size 一致, 但我不確定當初這樣設計是不是因為這樣啦, 不過現在 sector size 未必是 512 bytes 啦, 有些是 4KB 像是 SSD 甚麼的
> GPT header 含有兩個 CRC checksum 一個是用 header 自己的 field 去算的. 另外一個是拿 entries 去算的.
> 開機的時候 /block/partition/efi.c 這邊的邏輯會檢查 GPT, 如果 primary 好的話就用, 不然用 alternate, 真的不行就 fail
> [name=ztex]

* Partition entries (LBA 2–33)

1 Logical block is 512 bytes, contains 4 entries. Gives each entry 128 bytes

00000400: 16e3 c9e3 5c0b b84d 817d f92d f002 15ae  ....\..M.}.-....
00000410: 068d ecee b3c6 1e49 b4ad ac73 862e 3d33  .......I...s..=3
00000420: 2200 0000 0000 0000 2100 0400 0000 0000  ".......!.......
00000430: 0000 0000 0000 0000 4d00 6900 6300 7200  ........M.i.c.r.
00000440: 6f00 7300 6f00 6600 7400 2000 7200 6500  o.s.o.f.t. .r.e.
00000450: 7300 6500 7200 7600 6500 6400 2000 7000  s.e.r.v.e.d. .p.
00000460: 6100 7200 7400 6900 7400 6900 6f00 6e00  a.r.t.i.t.i.o.n.
00000470: 0000 0000 0000 0000 0000 0000 0000 0000  ................

- [ ] 0 (0x00) 16 bytes 16e3 c9e3 5c0b b84d 817d f92d f002 15ae Partition type GUID (mixed endian)
- [ ] 16 (0x10) 16 bytes 068d ecee b3c6 1e49 b4ad ac73 862e 3d33 Unique partition GUID (mixed endian)
- [ ] 32 (0x20) 8 bytes 2200 0000 0000 0000 First LBA (little endian)
- [ ] 40 (0x28) 8 bytes 2100 0400 0000 0000 Last LBA (inclusive, usually odd)
- [ ] 48 (0x30) 8 bytes 0000 0000 0000 0000 Attribute flags (e.g. bit 60 denotes read-only)
- [ ] 56 (0x38) 72 bytes 4d00 6900 6300 7200 6f00 7300 6f00 6600 7400 2000 7200 6500 7300 6500 7200 7600 6500 6400 2000 7000 6100 7200 7400 6900 7400 6900 6f00 6e00 Partition name (36 UTF-16LE code units)

00000480: a2a0 d0eb e5b9 3344 87c0 68b6 b726 99c7  ......3D..h..&..
00000490: 28b5 5ef7 90b1 5c4d a689 cd3b 6876 319b  (.^...\M...;hv1.
000004a0: 0008 0400 0000 0000 ff9f 505d 0100 0000  ..........P]....
000004b0: 0000 0000 0000 0000 4200 6100 7300 6900  ........B.a.s.i.
000004c0: 6300 2000 6400 6100 7400 6100 2000 7000  c. .d.a.t.a. .p.
000004d0: 6100 7200 7400 6900 7400 6900 6f00 6e00  a.r.t.i.t.i.o.n.
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

## Partition Table in linux
see: `block/partitions/efi.c` in linux (https://elixir.bootlin.com/linux/latest/source/block/partitions/efi.c)

Here is part of its description:

 * EFI GUID Partition Table handling
 *
 * http://www.uefi.org/specs/
 * http://www.intel.com/technology/efi/
 *
 * efi.[ch] by Matt Domsch <[e-mail]>
 *   Copyright 2000,2001,2002,2004 Dell Inc.

Here I'll go through some function:

Here is a simple call stack (it's not complete!)
|caller|function name|
|-----|--------|
|efi_partition|is_pte_valid|
| | |
|find_valid_gpt|is_gpt_valid|
|efi_partition|find_valid_gpt|
| | |
|**entry point**|efi_partition|

`efi_partition`

int efi_partition(struct parsed_partitions *state)
{
	gpt_header *gpt = NULL;
	gpt_entry *ptes = NULL;
	u32 i;
	unsigned ssz = bdev_logical_block_size(state->bdev) / 512;

	if (!find_valid_gpt(state, &gpt, &ptes) || !gpt || !ptes) {
		kfree(gpt);
		kfree(ptes);
		return 0;
	}

	pr_debug("GUID Partition Table is valid!  Yea!\n");

	for (i = 0; i < le32_to_cpu(gpt->num_partition_entries) && i < state->limit-1; i++) {
		struct partition_meta_info *info;
		unsigned label_max;
		u64 start = le64_to_cpu(ptes[i].starting_lba);
		u64 size = le64_to_cpu(ptes[i].ending_lba) -
			   le64_to_cpu(ptes[i].starting_lba) + 1ULL;

		if (!is_pte_valid(&ptes[i], last_lba(state->bdev)))
			continue;

		put_partition(state, i+1, start * ssz, size * ssz);
...
	}
	kfree(ptes);
	kfree(gpt);
...
	return 1;
}

> 這邊先調用 `find_valid_gpt` 找看看有沒有 valid gpt (primary 或者 alternate) 有的話 fill 到 `gpt` 跟 `ptes`. (對應的 structure 定義在 `efi.h`).
> 再來這個 `for loop` traverse 整個 entries, `is_pte_valid` 檢查三個:
> > 1. GUID type 是不是 NULL, 就是全部都零
> > 2. First LBA 有沒有超過 last lba
> > 3. Last LBA 有沒有超過 last lba
>
>

> [name=ztex]

* use `find_valid_gpt` to find a valid GPT (primary or alternate), if any one of them is valid, success, otherwise return.
* if GUID Partition Table is valid, the for loop goes through every parition entry and check with `is_pte_valid`:
* GUID type
* start lba
* end lba
* any one above is wrong, ignore that entry, continue

`find_valid_gpt`

static int find_valid_gpt(struct parsed_partitions *state, gpt_header **gpt,
			  gpt_entry **ptes)
{
	int good_pgpt = 0, good_agpt = 0, good_pmbr = 0;
	gpt_header *pgpt = NULL, *agpt = NULL;
	gpt_entry *pptes = NULL, *aptes = NULL;
	legacy_mbr *legacymbr;
	sector_t total_sectors = i_size_read(state->bdev->bd_inode) >> 9;
	u64 lastlba;

	if (!ptes)
		return 0;

	lastlba = last_lba(state->bdev);
        if (!force_gpt) {
		/* This will be added to the EFI Spec. per Intel after v1.02. */
		legacymbr = kzalloc(sizeof(*legacymbr), GFP_KERNEL);
		if (!legacymbr)
			goto fail;

		read_lba(state, 0, (u8 *)legacymbr, sizeof(*legacymbr));
		good_pmbr = is_pmbr_valid(legacymbr, total_sectors);
		kfree(legacymbr);

		if (!good_pmbr)
			goto fail;

		pr_debug("Device has a %s MBR\n",
			 good_pmbr == GPT_MBR_PROTECTIVE ?
						"protective" : "hybrid");
	}

	good_pgpt = is_gpt_valid(state, GPT_PRIMARY_PARTITION_TABLE_LBA,
				 &pgpt, &pptes);
        if (good_pgpt)
		good_agpt = is_gpt_valid(state,
					 le64_to_cpu(pgpt->alternate_lba),
					 &agpt, &aptes);
        if (!good_agpt && force_gpt)
                good_agpt = is_gpt_valid(state, lastlba, &agpt, &aptes);

        /* The obviously unsuccessful case */
        if (!good_pgpt && !good_agpt)
                goto fail;

        compare_gpts(pgpt, agpt, lastlba);

        /* The good cases */
        if (good_pgpt) {
                *gpt  = pgpt;
                *ptes = pptes;
                kfree(agpt);
                kfree(aptes);
		if (!good_agpt)
                        pr_warn("Alternate GPT is invalid, using primary GPT.\n");
                return 1;
        }
        else if (good_agpt) {
                *gpt  = agpt;
                *ptes = aptes;
                kfree(pgpt);
                kfree(pptes);
		pr_warn("Primary GPT is invalid, using alternate GPT.\n");
                return 1;
        }

 fail:
        kfree(pgpt);
        kfree(agpt);
        kfree(pptes);
        kfree(aptes);
        *gpt = NULL;
        *ptes = NULL;
        return 0;
}

Here use `is_gpt_valid` to verify primary header and alternate header.
If primary header is valid, take `pgpt` and `pptes` as used header and entries, free `agpt` and `aptes` and return. otherwise, reverse. If success the `*gpt` and `*ptes` would not be `NULL`

> 用 `is_gpt_valid` 來檢查 primary 跟 alternate GPT header
> 在該函式中 allocate header entries 資料結構 (`gpt_header`, `gpt_entry`)
> `pgpt` 表示 primary gpt, `agpt` 表示 alternate gpt
> 把最後 valid 的 gpt, entry fill 進 `gpt` `ptes` (對照 Line 50, 51; Line 59, 60)
> [name=ztex]
>

`is_gpt_valid`

/**
 * is_gpt_valid() - tests one GPT header and PTEs for validity
 * @state: disk parsed partitions
 * @lba: logical block address of the GPT header to test
 * @gpt: GPT header ptr, filled on return.
 * @ptes: PTEs ptr, filled on return.
 *
 * Description: returns 1 if valid,  0 on error.
 * If valid, returns pointers to newly allocated GPT header and PTEs.
 */
static int is_gpt_valid(struct parsed_partitions *state, u64 lba,
			gpt_header **gpt, gpt_entry **ptes)
{
	u32 crc, origcrc;
	u64 lastlba, pt_size;

	if (!ptes)
		return 0;
	if (!(*gpt = alloc_read_gpt_header(state, lba)))
		return 0;

	/* Check the GUID Partition Table signature */
	if (le64_to_cpu((*gpt)->signature) != GPT_HEADER_SIGNATURE) {
		pr_debug("GUID Partition Table Header signature is wrong:"
			 "%lld != %lld\n",
			 (unsigned long long)le64_to_cpu((*gpt)->signature),
			 (unsigned long long)GPT_HEADER_SIGNATURE);
		goto fail;
	}

	/* Check the GUID Partition Table header size is too big */
	if (le32_to_cpu((*gpt)->header_size) >
			bdev_logical_block_size(state->bdev)) {
		pr_debug("GUID Partition Table Header size is too large: %u > %u\n",
			le32_to_cpu((*gpt)->header_size),
			bdev_logical_block_size(state->bdev));
		goto fail;
	}

	/* Check the GUID Partition Table header size is too small */
	if (le32_to_cpu((*gpt)->header_size) < sizeof(gpt_header)) {
		pr_debug("GUID Partition Table Header size is too small: %u < %zu\n",
			le32_to_cpu((*gpt)->header_size),
			sizeof(gpt_header));
		goto fail;
	}

	/* Check the GUID Partition Table CRC */
	origcrc = le32_to_cpu((*gpt)->header_crc32);
	(*gpt)->header_crc32 = 0;
	crc = efi_crc32((const unsigned char *) (*gpt), le32_to_cpu((*gpt)->header_size));

	if (crc != origcrc) {
		pr_debug("GUID Partition Table Header CRC is wrong: %x != %x\n",
			 crc, origcrc);
		goto fail;
	}
	(*gpt)->header_crc32 = cpu_to_le32(origcrc);

	/* Check that the my_lba entry points to the LBA that contains
	 * the GUID Partition Table */
	if (le64_to_cpu((*gpt)->my_lba) != lba) {
		pr_debug("GPT my_lba incorrect: %lld != %lld\n",
			 (unsigned long long)le64_to_cpu((*gpt)->my_lba),
			 (unsigned long long)lba);
		goto fail;
	}

	/* Check the first_usable_lba and last_usable_lba are
	 * within the disk.
	 */
	lastlba = last_lba(state->bdev);
	if (le64_to_cpu((*gpt)->first_usable_lba) > lastlba) {
		pr_debug("GPT: first_usable_lba incorrect: %lld > %lld\n",
			 (unsigned long long)le64_to_cpu((*gpt)->first_usable_lba),
			 (unsigned long long)lastlba);
		goto fail;
	}
	if (le64_to_cpu((*gpt)->last_usable_lba) > lastlba) {
		pr_debug("GPT: last_usable_lba incorrect: %lld > %lld\n",
			 (unsigned long long)le64_to_cpu((*gpt)->last_usable_lba),
			 (unsigned long long)lastlba);
		goto fail;
	}
	if (le64_to_cpu((*gpt)->last_usable_lba) < le64_to_cpu((*gpt)->first_usable_lba)) {
		pr_debug("GPT: last_usable_lba incorrect: %lld > %lld\n",
			 (unsigned long long)le64_to_cpu((*gpt)->last_usable_lba),
			 (unsigned long long)le64_to_cpu((*gpt)->first_usable_lba));
		goto fail;
	}
	/* Check that sizeof_partition_entry has the correct value */
	if (le32_to_cpu((*gpt)->sizeof_partition_entry) != sizeof(gpt_entry)) {
		pr_debug("GUID Partitition Entry Size check failed.\n");
		goto fail;
	}

	/* Sanity check partition table size */
	pt_size = (u64)le32_to_cpu((*gpt)->num_partition_entries) *
		le32_to_cpu((*gpt)->sizeof_partition_entry);
	if (pt_size > KMALLOC_MAX_SIZE) {
		pr_debug("GUID Partition Table is too large: %llu > %lu bytes\n",
			 (unsigned long long)pt_size, KMALLOC_MAX_SIZE);
		goto fail;
	}

	if (!(*ptes = alloc_read_gpt_entries(state, *gpt)))
		goto fail;

	/* Check the GUID Partition Entry Array CRC */
	crc = efi_crc32((const unsigned char *) (*ptes), pt_size);

	if (crc != le32_to_cpu((*gpt)->partition_entry_array_crc32)) {
		pr_debug("GUID Partitition Entry Array CRC check failed.\n");
		goto fail_ptes;
	}

	/* We're done, all's well */
	return 1;

 fail_ptes:
	kfree(*ptes);
	*ptes = NULL;
 fail:
	kfree(*gpt);
	*gpt = NULL;
	return 0;
}

`alloc_read_gpt_header` calls `read_lba` to read primary header and alternate header.
`alloc_read_gpt_entries` also calls `read_lba` to read entries.

several things are checked
* Signature
* size
* CRC
* ...

note that `le32_to_cpu` and `le64_to_cpu` transform little endian form to cpu(whatever your platform is, this macro takes care). Also, `cpu_to_le32` and `cpu_to_le64` do the reverse thing.

> 這邊都用 read_lba 來讀硬碟資料
> Primary 就是對 lba 1, 這個定義在 `efi.h` Line 41.
> 因為 GPT spec 說了 little endian 形式, 所以我們用 `le{32/64}_to_cpu` `cpu_to_le{32/64}` 幫我們對到 CPU形式 (搞不好 CPU 用 big endian) 那就G了
> [name=ztex]

`read_lba`

/**
 * read_lba(): Read bytes from disk, starting at given LBA
 * @state: disk parsed partitions
 * @lba: the Logical Block Address of the partition table
 * @buffer: destination buffer
 * @count: bytes to read
 *
 * Description: Reads @count bytes from @state->bdev into @buffer.
 * Returns number of bytes read on success, 0 on error.
 */
static size_t read_lba(struct parsed_partitions *state,
		       u64 lba, u8 *buffer, size_t count)
{
	size_t totalreadcount = 0;
	struct block_device *bdev = state->bdev;
	sector_t n = lba * (bdev_logical_block_size(bdev) / 512);

	if (!buffer || lba > last_lba(bdev))
                return 0;

	while (count) {
		int copied = 512;
		Sector sect;
		unsigned char *data = read_part_sector(state, n++, &sect);
		if (!data)
			break;
		if (copied > count)
			copied = count;
		memcpy(buffer, data, copied);
		put_dev_sector(sect);
		buffer += copied;
		totalreadcount +=copied;
		count -= copied;
	}
	return totalreadcount;
}

`bdev_logical_block_size` gives the block size of the device.
see: https://elixir.bootlin.com/linux/latest/source/include/linux/blkdev.h#L1329
(default: 512)

so the `n` is the sector the lba is located at.

call `read_part_sector` to get the virtual memory mapped to the sector.
see: (read_part_sector)https://elixir.bootlin.com/linux/latest/source/block/partitions/core.c#L762
also see: (read_dev_sector)https://elixir.bootlin.com/linux/v4.20.17/source/block/partition-generic.c#L659

> `bdev_logical_block_size ` 給出 block size, 沒意外的話是 512 byte 但其實現在很多裝置不是..
> `read_part_sector` 回傳對應的 virtual memory, 這裡面的程式很短, 但很有趣
> [name=ztex]
>

## :memo: Fix GPT

### :timer_clock: When to fix?

in `find_valid_gpt`, I put

else if (good_agpt) {
		/* alterative gpt is good, but primary is not, so write agpt to pgpt*/
                *gpt  = agpt;
                *ptes = aptes;

		pr_warn("[ZTEX][RECOVER] [%s] Try to recover from alternate GPT\n", state->name);

		kfree(pgpt);
		kfree(pptes);
		pgpt = NULL;
		pptes = NULL;
		ret = pgpt_recover(state, &pgpt, &pptes, &agpt, &aptes);
		if (ret) {
			pr_warn("[ZTEX][RECOVER]Write recoverd GPT back to lba %d\n", GPT_PRIMARY_PARTITION_TABLE_LBA);
			if(write_gpt_header(state, pgpt, GPT_PRIMARY_PARTITION_TABLE_LBA) == NULL) {
			    pr_warn("Fail to recover the primary gpt from alterative gpt\n");
                            kfree(pgpt);
                            kfree(pptes);
                            pr_warn("[ZTEX][RECOVER]After trying to fix primary, fail, use alternate GPT.\n");
                            return 1;
			}
                        else {
                            *gpt = pgpt;
                            *ptes = pptes;
                            return 1;
                        }
		}

		kfree(pgpt);
		kfree(pptes);
                return 1;
        }

When Primary went wrong, but alternate be held. Try to fix the primary header with alternate header. see `pgpt_recover`

### :sandwich: recover logic? `pgpt_recover`

/**
 * pgpt_recover() - Try to recover primary GPT header
 * @state: disk parsed partitions
 * @pgpt: primary GPT header ptr, filled on return.
 * @pptes: primary PTEs ptr, filled on return.
 * @agpt: alternate GPT header ptr, filled on return.
 * @aptes: alternae PTEs ptr, filled on return.
 *
 * Description: returns 1 if valid,  0 on error.
 * If valid, returns pointers to newly allocated GPT header and PTEs.
 */
static int pgpt_recover(struct parsed_partitions *state, gpt_header **pgpt, gpt_entry **pptes, gpt_header **agpt, gpt_entry **aptes)
{
	u32 crc, origcrc;
	u64 lastlba;

	if (!(*agpt) || !pptes || !aptes) {
		pr_warn("[ZTEX][RECOVER] NULL pointer\n");
		return 0;
	}

	if (!(*pgpt = alloc_read_gpt_header(state, GPT_PRIMARY_PARTITION_TABLE_LBA))) {
		pr_warn("[ZTEX][RECOVER] GUID Partition Table Header Read fail.\n");
		return 0;
	}

	/* Recover the GUID Partition Table signature */
	if (le64_to_cpu((*pgpt)->signature) != GPT_HEADER_SIGNATURE) {
		pr_warn("[ZTEX][RECOVER]GUID Partition Table Header signature\n");
		(*pgpt)->signature = cpu_to_le64(GPT_HEADER_SIGNATURE);
	}

	/* Recover the GUID Partition Table CRC */
	origcrc = le32_to_cpu((*pgpt)->header_crc32);
	(*pgpt)->header_crc32 = 0;
	crc = efi_crc32((const unsigned char *) (*pgpt), le32_to_cpu((*pgpt)->header_size));

	pr_warn("[ZTEX][RECOVER]The right GUID Partition Table Header CRC is %x, and we have %x\n", crc, origcrc);
	if (crc != origcrc) {
		pr_warn("[ZTEX][RECOVER]GUID Partition Table Header CRC is wrong: %x != %x\n",
			 crc, origcrc);
		(*pgpt)->header_crc32 = cpu_to_le32(crc);
	}

	/* Recover that the my_lba entry points to the LBA that contains
	 * the GUID Partition Table */
	if (le64_to_cpu((*pgpt)->my_lba) != GPT_PRIMARY_PARTITION_TABLE_LBA) {
		pr_warn("[ZTEX][RECOVER]GPT my_lba incorrect: %lld != %lld\n",
			 (unsigned long long)le64_to_cpu((*pgpt)->my_lba),
			 (unsigned long long)GPT_PRIMARY_PARTITION_TABLE_LBA);
		(*pgpt)->my_lba = cpu_to_le64(GPT_PRIMARY_PARTITION_TABLE_LBA);
	}

	/* Check the first_usable_lba and last_usable_lba are
	 * within the disk.
	 */
	lastlba = last_lba(state->bdev);
	if (le64_to_cpu((*pgpt)->first_usable_lba) > lastlba) {
		pr_warn("[ZTEX][RECOVER]GPT: first_usable_lba incorrect: %lld > %lld\n",
			 (unsigned long long)le64_to_cpu((*pgpt)->first_usable_lba),
			 (unsigned long long)lastlba);
		(*pgpt)->first_usable_lba = (*agpt)->first_usable_lba;
	}
	if (le64_to_cpu((*pgpt)->last_usable_lba) > lastlba) {
		pr_warn("[ZTEX][RECOVER]GPT: last_usable_lba incorrect: %lld > %lld\n",
			 (unsigned long long)le64_to_cpu((*pgpt)->last_usable_lba),
			 (unsigned long long)lastlba);
		(*pgpt)->last_usable_lba = (*agpt)->last_usable_lba;
	}

	/* Recover that sizeof_partition_entry has the correct value */
	if (le32_to_cpu((*pgpt)->sizeof_partition_entry) != sizeof(gpt_entry)) {
		pr_warn("[ZTEX][RECOVER]GUID Partitition Entry Size check failed.\n");
		(*pgpt)->sizeof_partition_entry = cpu_to_le32(sizeof(gpt_entry));
	}


	if (!(*pptes = alloc_read_gpt_entries(state, *pgpt))) {
		pr_warn("[ZTEX][RECOVER] GUID Partition Entry read fail.\n");
		kfree(*pgpt);
		*pgpt = NULL;
		return 0;
	}
	/* Recover the GUID Partition Entry Array CRC */
	crc = efi_crc32((const unsigned char *) (*pptes),
			le32_to_cpu((*pgpt)->num_partition_entries) *
			le32_to_cpu((*pgpt)->sizeof_partition_entry));

	pr_warn("[ZTEX][RECOVER]The right GUID Partitition Entry Array CRC: %x, and we have %x\n", 
			crc, le32_to_cpu((*pgpt)->partition_entry_array_crc32));
	if (crc != le32_to_cpu((*pgpt)->partition_entry_array_crc32)) {
		pr_warn("[ZTEX][RECOVER]GUID Partitition Entry Array CRC check failed. %x != %x\n",
				crc, le32_to_cpu((*pgpt)->partition_entry_array_crc32));
		(*pgpt)->partition_entry_array_crc32 = cpu_to_le32(crc);
	}

	/* We're done, all's well */
	return 1;
}

basically `is_gpt_valid` but write the right thing back.

### :pencil: How to write it back to disk? `write_gpt_header` `write_lba`

/**
 * write_lba(): Write bytes from disk, starting at given LBA
 * @state: disk parsed partitions
 * @lba: the Logical Block Address of the partition table
 * @buffer: resource buffer
 * @count: bytes to write
 *
 * Description: Write @count bytes from buffer into @@state->bdev.
 * Returns number of bytes read on success, 0 on error.
 */
static size_t write_lba(struct parsed_partitions *state,
		       u64 lba, u8 *buffer, size_t count)
{
	size_t totalreadcount = 0;
	struct block_device *bdev = state->bdev;
	struct bio *bio;
	struct page *page;
	struct address_space *mapping = bdev->bd_inode->i_mapping;

	sector_t n = lba * (bdev_logical_block_size(bdev) / 512);

	if (!buffer || lba > last_lba(bdev))
                return 0;

	while (count) {
		int copied = 512;
		Sector sect;
		unsigned char *data = read_part_sector(state, n, &sect);
		if (!data)
			break;
		if (copied > count)
			copied = count;
		memcpy(data, buffer, copied);

		bio = bio_alloc(GFP_NOIO, 1);
		bio_get(bio);
		bio->bi_bdev = bdev;
		bio->bi_iter.bi_sector = n;

		if (n >= get_capacity(state->bdev->bd_disk)) {
			state->access_beyond_eod = true;
			pr_warn("[ZTEX] write_lba access_beyond eod");
			return -1;
		}

		page = read_mapping_page(mapping,
				(pgoff_t)(n >> (PAGE_SHIFT - 9)), NULL);
		if (PageError(page))
			put_page(page);

		//bio_add_page(bio, page, PAGE_SIZE, 0);
                pr_warn("[ZTEX][WRITE_LBA] lba: %llu; sector: %llu; offset: %llu\n",
                        (unsigned long long )lba, (unsigned long long)n, (unsigned long long)SECTOR_TO_PAGE_OFFSET(n));
		bio_add_page(bio, page, copied, SECTOR_TO_PAGE_OFFSET(n));
		submit_bio(WRITE_FLUSH_FUA, bio);

		put_dev_sector(sect);
		buffer += copied;
		totalreadcount +=copied;
		count -= copied;
		n++;
		bio_put(bio);
	}
	return totalreadcount;
}

call `read_part_sector` and get the virtual memory, `memcpy` copy the content of gpt to the memory space. At this point, the data is still in memory and not in disk.

adopt `bio`, aka block IO, write the page back to disk.

/*
bio_alloc() allocate bio
see: https://elixir.bootlin.com/linux/v4.20.17/source/include/linux/bio.h#L203

always bio_get() and bio_put(), like

 * get a reference to a bio, so it won't disappear. the intended use is
 * something like:
 *
 * bio_get(bio);
 * submit_bio(rw, bio);
 * if (bio->bi_flags ...)
 *	do_something
 * bio_put(bio);
 *
 * without the bio_get(), it could potentially complete I/O before submit_bio
 * returns. and then bio would be freed memory when if (bio->bi_flags ...)
 * runs
 
bio->bi_bdev is the block device
bio->bi_iter.bi_sector is associate sector
bio_add_page() add page to a bio in a new segment, see: https://elixir.bootlin.com/linux/v4.20.17/source/block/bio.c#L792
submit_bio() submit a bio to the block device layer for I/O
see: https://elixir.bootlin.com/linux/latest/source/block/blk-core.c#L1223

 * submit_bio - submit a bio to the block device layer for I/O
 * @bio: The &struct bio which describes the I/O
 *
 * submit_bio() is used to submit I/O requests to block devices.  It is passed a
 * fully set up &struct bio that describes the I/O that needs to be done.  The
 * bio will be send to the device described by the bi_disk and bi_partno fields.
 *
 * The success/failure status of the request, along with notification of
 * completion, is delivered asynchronously through the ->bi_end_io() callback
 * in @bio.  The bio must NOT be touched by thecaller until ->bi_end_io() has
 * been called.

*/

Here I want to mention the `SECTOR_TO_PAGE_OFFSET(n)`, this return the offset of the page give a sector.

#define SECTOR_TO_PAGE_OFFSET(n) ((n & ((1 << (PAGE_SHIFT - 9)) - 1)) << 9)

in `read_dev_sector`

page = read_mapping_page(mapping, (pgoff_t)(n >> (PAGE_SHIFT-9)), NULL);
...
return (unsigned char *)page_address(page) +  ((n & ((1 << (PAGE_SHIFT - 9)) - 1)) << 9);
...

also `read_part_sector`

page = read_mapping_page(mapping,
		(pgoff_t)(n >> (PAGE_SHIFT - 9)), NULL);
...
return (unsigned char *)page_address(page) +
		((n & ((1 << (PAGE_SHIFT - 9)) - 1)) << SECTOR_SHIFT)
...

What does this mean?

Firstly we know that `PAGE_SHIFT` is 12 in `x86`, which can be found in https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/page_types.h#L10. This shows the a page size is 4KB($2^{12}$) in `x86`.

Secondly `n >> 3` means that sector = 0 ~ 7($2^{3}$-1) are all in the same page. As the result, each page contains 8 sectors.

Make sense, each sector has 512 bytes. 512 * 8 = 4KB.

So the question now is: Given a sector, how to figure out the offset of the sector in a page?

OK, we know that the last 3 bits of the sector do nothing to determine which page the sector is.

However, to get the offset, the last three bits are everything we need to know.

So, just keep the last three and mask the remaining bits. We need something like `n & 0b......xxx` this gives `(n & ((1 << 3) - 1))` which is literaly `(n & ((1 << (PAGE_SHIFT - 9)) - 1)`.

Now we've transfromed sector number to the number of sector in a page. To get the offset, recall the sector size is 512 = $2^9$, `* 512` = `<< 9` = `<< SECTOR_SHIFT`.

Combine all together, we get `((n & ((1 << (PAGE_SHIFT - 9)) - 1)) << 9)`.

> 一個 page size 是 4KB (x86 上), 一個 sector 512 bytes.
> 所以, 一個 page 有 8 個 sector, 也就是說 0~7(0000-0111) 在一張 page, 8~15(1000-1111) 另一張, 最後三個 bit 跟這個 sector 哪張 page 沒有關係.
> 所以我們 `n & 0000...111` 就可以知道, 這個 sector 在這對應的 page 上是第幾個 sector, 比如: sector 9, 9 = 0b1001 所以他在第 1 張 page 上, 是第 1 個 sector (從 0 開始數)
> 所以 `n & 0000...111` = `(n & ((1 << (PAGE_SHIFT - 9)) - 1)`
> sector 512 bytes 所以 `<< SECTOR_SHIFT`
> 最後得到 `((n & ((1 << (PAGE_SHIFT - 9)) - 1)) << 9)`
> [name=ztex]
>

### :microscope: Check CRC again

Because after `find_valid_gpt` we traverse entries and wipe out invalid entries. This change the crc so we got the check again.

/**
 * gpt_crc_corretion() - Re-calculate crc
 * @state: disk parsed partitions
 * @gpt: GPT header ptr, filled on return.
 * @ptes: PTEs ptr, filled on return.
 *
 * Description: returns 1 if modify,  0 otherwise.
 *
 */
static int gpt_crc_correction(struct parsed_partitions *state, gpt_header **gpt, gpt_entry **ptes)
{
	u32 crc, origcrc;
        int ret = 0;

	if (!(*gpt) || !ptes) {
		pr_warn("[ZTEX][CRC] NULL pointer\n");
		return 0;
	}

	/* verify the GUID Partition Table CRC */
	origcrc = le32_to_cpu((*gpt)->header_crc32);
	(*gpt)->header_crc32 = 0;
	crc = efi_crc32((const unsigned char *) (*gpt), le32_to_cpu((*gpt)->header_size));

	pr_warn("[ZTEX][CRC]The right GUID Partition Table Header CRC is %x, and we have %x\n", crc, origcrc);
	if (crc != origcrc) {
		pr_warn("[ZTEX][CRC]GUID Partition Table Header CRC is wrong: %x != %x\n",
			 crc, origcrc);
		(*gpt)->header_crc32 = cpu_to_le32(crc);
                ret = 1;
	}
        else {
            (*gpt)->header_crc32 = cpu_to_le32(origcrc);
        }

	/* Recover the GUID Partition Entry Array CRC */
	crc = efi_crc32((const unsigned char *) (*ptes),
			le32_to_cpu((*gpt)->num_partition_entries) *
			le32_to_cpu((*gpt)->sizeof_partition_entry));

	pr_warn("[ZTEX][CRC]The right GUID Partitition Entry Array CRC: %x, and we have %x\n", 
			crc, le32_to_cpu((*gpt)->partition_entry_array_crc32));
	if (crc != le32_to_cpu((*gpt)->partition_entry_array_crc32)) {
		pr_warn("[ZTEX][RECOVER]GUID Partitition Entry Array CRC check failed. %x != %x\n",
				crc, le32_to_cpu((*gpt)->partition_entry_array_crc32));
		(*gpt)->partition_entry_array_crc32 = cpu_to_le32(crc);
                ret = 1;
	}

	/* We're done,*/
	return ret;
}

### :checkered_flag: RESULT

root@SynologyNAS:~# fdisk -l /dev/sata1
Disk /dev/sata1: 2.7 TiB, 3000592982016 bytes, 5860533168 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: gpt
Disk identifier: EC346549-0EA0-44E7-9AEC-4C08B4878C8D

Device        Start        End    Sectors  Size Type
/dev/sata1p1     34     262177     262144  128M Microsoft reserved
/dev/sata1p2 264192 5860532223 5860268032  2.7T Microsoft basic data

Partition 1 does not start on physical sector boundary.

The message `does not start on physical sector boundary.` is related to `lba_is_phy_aligned` (here https://github.com/karelzak/util-linux/blob/83fdb880b953164fec7cc603c4ece11cb78762db/libfdisk/src/alignment.c).

also see: https://www.thomas-krenn.com/en/wiki/Partition_Alignment_detailed_explanation#fdisk_.28Older_Versions.29

If the partition is aligned with physical sector, the read/write efficiency is better.