Appendix L — The order in which a machine wakes: booting and bootloaders

chapter 55 asked “who calls main”, and the answer was the operating system. Then who calls the operating system? This appendix follows that question down to the power switch.

The details differ by machine and there is no need to know them all. Hold on to one sentence instead and any machine’s boot can be read. Booting is a chain, and every link does the same work — find the next thing, load it, check it, hand over control.

Figure 105.1 — The chain of booting — the machines differ; the work of each link does not.

When the power comes on#

The CPU wakes knowing nothing. Memory holds rubbish, devices are uninitialised, and the very notion of “a program” does not exist yet. The CPU knows one thing — read a fixed address and start executing there. That is the reset vector seen in the appendix on C without an operating system.

At that fixed place a ROM is usually wired, and the program in it is called firmware. On a PC that is the BIOS or the UEFI firmware; on a small chip it is a boot ROM the manufacturer put there.

The BIOS era — 512 bytes was all there was#

The old PC’s way is startlingly simple. The BIOS loads the first 512-byte sector of the boot device at address 0x7C00, checks that its last two bytes are 0x55 0xAA, and if so jumps there. That is all. Those 512 bytes are the boot sector, and the first sector of the whole disk is the MBR (master boot record).

Building one shows where the space goes. But first, be clear about what is being built.

/* 디스크의 첫 섹터에 무엇이 있는가 --- 직접 만들어 보고, 다시 읽어 본다.

   주의: 이 프로그램은 디스크를 건드리지 않는다. 파일도 장치도 열지 않고, 아무것도 쓰지
   않는다. 기억 속의 배열 하나를 옛 규약 그대로 채운 뒤, 그 배열을 다시 읽어 해독해
   화면에 찍을 뿐이다. 돌리면 글자만 나오고 끝난다.

   여기서 만드는 바이트는 진짜 규칙을 따른다: 512바이트, 0x1BE 의 파티션 표 네 칸,
   그리고 끝의 0x55 0xAA. GPT 를 쓰는 디스크의 첫 섹터(보호 MBR)와 EFI PART 헤더도
   같이 만든다. 이 바이트를 실제 디스크의 0번 섹터에 쓰는 일은 하지 않는다. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

static uint32_t crc32(const void *buf, size_t n)
{
    const unsigned char *p = buf;
    uint32_t c = 0xFFFFFFFFu;
    for (size_t i = 0; i < n; i++) {
        c ^= p[i];
        for (int k = 0; k < 8; k++)
            c = (c >> 1) ^ (0xEDB88320u & (uint32_t)-(int32_t)(c & 1));
    }
    return c ^ 0xFFFFFFFFu;
}

static void put32(unsigned char *p, uint32_t v)
{ p[0] = v & 0xff; p[1] = v >> 8 & 0xff; p[2] = v >> 16 & 0xff; p[3] = v >> 24; }

static void put_part(unsigned char *e, uint8_t boot, uint8_t type,
                     uint32_t lba, uint32_t count)
{
    e[0] = boot;              /* 0x80 이면 「이것으로 부팅」 */
    e[1] = 0xfe; e[2] = 0xff; e[3] = 0xff;   /* 옛 CHS 자리 --- 이제는 채우는 시늉만 한다 */
    e[4] = type;
    e[5] = 0xfe; e[6] = 0xff; e[7] = 0xff;
    put32(e + 8, lba);        /* 시작 --- 이쪽이 진짜로 쓰인다 */
    put32(e + 12, count);
}

static void hexdump(const unsigned char *p, size_t off, size_t n)
{
    for (size_t i = 0; i < n; i += 16) {
        printf("  %04zx  ", off + i);
        for (size_t j = 0; j < 16; j++) printf("%02x%s", p[off + i + j], j == 7 ? "  " : " ");
        printf("\n");
    }
}

int main(void)
{
    unsigned char mbr[512] = { 0 };

    /* (1) 부트스트랩 자리 --- 446바이트. 진짜 부트로더의 첫 조각이 여기 들어간다. */
    memcpy(mbr, "\xfa\x31\xc0\x8e\xd8\x8e\xd0\xbc\x00\x7c", 10);  /* cli; 세그먼트·스택 차리기 */
    printf("how the first sector divides up\n");
    printf("  0x000 - 0x1bd : bootstrap code, %d bytes\n", 0x1be);
    printf("  0x1be - 0x1fd : partition table --- 16 bytes x 4 entries\n");
    printf("  0x1fe - 0x1ff : signature 0x55 0xaa\n\n");

    /* (2) 파티션 표 --- 흔한 배치 하나를 적어 둔다 */
    put_part(mbr + 0x1be, 0x80, 0x83, 2048, 1024000);   /* 부팅 가능, 리눅스 */
    put_part(mbr + 0x1ce, 0x00, 0x82, 1026048, 262144); /* 리눅스 스왑 */
    mbr[510] = 0x55; mbr[511] = 0xaa;

    printf("the partition table (from 0x1be)\n");
    hexdump(mbr, 0x1be, 32);
    printf("\n  entry 1: bootable %s · type 0x%02x (Linux) · start LBA %u · %u sectors (%u MiB)\n",
           mbr[0x1be] == 0x80 ? "yes" : "no", mbr[0x1be + 4],
           2048u, 1024000u, 1024000u / 2048u);
    printf("  entry 2: bootable %s · type 0x%02x (swap) · start LBA %u\n\n",
           mbr[0x1ce] == 0x80 ? "yes" : "no", mbr[0x1ce + 4], 1026048u);

    printf("the last two bytes: %02x %02x --- %s\n\n", mbr[510], mbr[511],
           (mbr[510] == 0x55 && mbr[511] == 0xaa)
           ? "the BIOS accepts this as a boot sector only with these" : "not a boot sector");

    /* (3) GPT 를 쓰는 디스크의 첫 섹터 --- 보호 MBR */
    unsigned char pmbr[512] = { 0 };
    put_part(pmbr + 0x1be, 0x00, 0xee, 1, 0xffffffffu);  /* 0xEE = 「여기부터 끝까지 남의 것」 */
    pmbr[510] = 0x55; pmbr[511] = 0xaa;
    printf("the protective MBR (first sector of a GPT disk)\n");
    printf("  partition type 0x%02x --- it tells old tools the disk is fully used\n",
           pmbr[0x1be + 4]);
    printf("  the reason: to stop a tool that does not know GPT taking it for empty\n\n");

    /* (4) 진짜 지도는 두 번째 섹터(LBA 1)에 있다 --- GPT 헤더 */
    unsigned char gpt[92] = { 0 };
    memcpy(gpt, "EFI PART", 8);
    put32(gpt + 8, 0x00010000u);      /* 개정 1.0 */
    put32(gpt + 12, 92);              /* 헤더 크기 */
    put32(gpt + 16, 0);               /* CRC 자리는 0 으로 두고 계산한다 */
    put32(gpt + 16, crc32(gpt, 92));

    printf("the GPT header (LBA 1)\n");
    printf("  signature : %.8s\n", gpt);
    printf("  header CRC32: 0x%08x --- it checks itself (this field is zero while computing)\n",
           (unsigned)(gpt[16] | gpt[17] << 8 | gpt[18] << 16 | (uint32_t)gpt[19] << 24));
    printf("  and the same table exists once more at the very end of the disk, to survive damage\n");
    return 0;
}

how the first sector divides up
  0x000 - 0x1bd : bootstrap code, 446 bytes
  0x1be - 0x1fd : partition table --- 16 bytes x 4 entries
  0x1fe - 0x1ff : signature 0x55 0xaa

the partition table (from 0x1be)
  01be  80 fe ff ff 83 fe ff ff  00 08 00 00 00 a0 0f 00 
  01ce  00 fe ff ff 82 fe ff ff  00 a8 0f 00 00 00 04 00 

  entry 1: bootable yes · type 0x83 (Linux) · start LBA 2048 · 1024000 sectors (500 MiB)
  entry 2: bootable no · type 0x82 (swap) · start LBA 1026048

the last two bytes: 55 aa --- the BIOS accepts this as a boot sector only with these

the protective MBR (first sector of a GPT disk)
  partition type 0xee --- it tells old tools the disk is fully used
  the reason: to stop a tool that does not know GPT taking it for empty

the GPT header (LBA 1)
  signature : EFI PART
  header CRC32: 0x36425678 --- it checks itself (this field is zero while computing)
  and the same table exists once more at the very end of the disk, to survive damage

The demonstration goes in four steps.

1. It declares the space. It prints the 512 bytes divided as 446 + 16×4 + 2. The ten bytes at the front (fa 31 c0 8e d8 … — disabling interrupts and setting up segments and the stack) are there to show what the beginning of a real bootloader usually looks like; it is not a working bootloader.
2. It writes two partition entries by the convention. The boot flag 0x80, the types 0x83 (Linux) and 0x82 (swap), the starting LBA and the sector count as four little-endian bytes. The old CHS fields are filled with fe ff ff as is customary — the idiomatic value meaning “a size CHS cannot express”. And 55 aa goes into bytes 510 and 511.
3. It reads back what it wrote. It prints those 64 bytes in hex and recovers “bootable, type 0x83, starting LBA 2048, 500 MiB” from the same bytes. Whether writing and reading use the same convention shows up on the spot.
4. It builds the GPT side the same way. A protective MBR covering the disk with a single type 0xEE partition, and a 92-byte header carrying the EFI PART signature whose CRC32 is computed with the CRC field zeroed and then written into that field — exactly as the specification says. The 0x36425678 in the output is that genuinely computed value. The GUIDs and LBA fields are zero, though, so it is a specimen of the shape, not a usable GPT header.

What you get from this is not “which field is at which byte”. It is one number: 446 bytes. That narrow space explains everything that follows.

Code that loads an operating system cannot possibly fit in 446 bytes. So every old bootloader was split into several stages — the first piece knows only where the second is, the second knows how to read a filesystem, and the one after that loads the kernel.

The layout of the disk — from MBR to GPT#

Four partitions and a 32-bit LBA (the 2 TiB limit) soon grew tight. GPT (the GUID Partition Table) took that place, and the latter half of the demonstration above is that story.

• The first sector still holds an MBR. Only now a single partition of type 0xEE covers the whole disk — the protective MBR. It exists to stop old tools that do not know GPT from taking the disk for empty and overwriting it.
• The real layout is in the GPT header in the second sector (LBA 1). Its signature is EFI PART, it carries a CRC32 of itself, and a second copy of the same table sits at the very end of the disk.

The individual fields of both schemes, and the filesystems inside the partitions, are covered in tables in the appendix on how a disk is divided. Here we look only as far as the chain story needs.

★ The difference between the old way and the new comes down to two words: checking and copies. A CRC takes over the “is this right” that two bytes of 0x55 0xAA used to do, and a table that existed once now exists twice. Reliability design is largely a repetition of those two.

UEFI — the firmware reads a filesystem#

UEFI removes the “512 bytes” constraint altogether. The firmware knows how to read a FAT filesystem, finds an executable in one partition of the disk (the ESP, the EFI System Partition), and simply runs it.

Here the previous appendix joins on. That executable is in PE format — the same clothes as a Windows executable, with only the subsystem field in the header saying “UEFI application”. The filename is agreed too: with no configuration at all, the firmware looks for \EFI\BOOT\BOOTX64.EFI.

What a bootloader actually does#

The names vary; the work is the latter part of Table 105.1. How that “same work” gets done differs quite a lot between ways, though, and most of the trouble met in practice comes from those differences. Let me open them one at a time.

Why several stages — the shadow of 446 bytes#

In the old BIOS way the first piece is allowed 446 bytes — what is left of 512 after the partition table and the signature (the full layout table is in the disk appendix). Code that reads a filesystem cannot fit there. So the bootloader splits.

★ The second row is the point. boot.img cannot find the next piece by filename — it knows no filesystem. It embeds a sector number instead. Which is why there must be “empty space outside any filesystem” for core.img to sit in.

The UEFI path — found by name and by variable#

In UEFI all this indirection disappears. Because the firmware can read FAT, the bootloader is simply a file (see the ESP entry in the disk appendix).

★ So on a UEFI machine, “the boot order vanished” means the variables on the mainboard were cleared, not anything on the disk. That is why the fallback name exists — and it is that agreement that lets one USB stick boot any machine.

Without a bootloader — the Linux EFI stub#

A Linux kernel image can be built as a PE executable in its own right. Then the firmware runs the kernel directly. Thin and fast, at a price — there is no menu, and who supplies the command line and the initramfs becomes a question (embedded in a firmware variable, or built into the kernel).

Embedded — U-Boot and MCUboot#

On a small machine you start from a place where there is not even RAM yet.

What is handed over at the handover#

Each link of the chain leaves luggage for the next before it disappears. The list of that luggage is the contract.

★ Look closely at ExitBootServices in the UEFI row. Until that call the firmware handles disk, screen and network on your behalf. After it those services are all gone and only a copy of the memory table remains. “The moment the operating system takes over the machine” is pinned down exactly, by one function call.

When it will not boot — telling links apart by symptom#

By operating system — what happens after that#

MS-DOS#

The boot sector reads IO.SYS, which loads MSDOS.SYS (the kernel proper), then CONFIG.SYS is read to load device drivers, and finally COMMAND.COM starts. Then AUTOEXEC.BAT runs. The chain is laid bare as filenames, which is why users of that era could edit their boot process.

Windows#

What changed is where “choosing” lives. A text file (boot.ini) became a binary store (BCD), and it became a .efi executable. What did not change is the shape of the chain.

Linux#

1. The bootloader loads the kernel image (vmlinuz) and the initramfs into memory and hands over a command line.
2. The front of the kernel image is code that unpacks itself. It decompresses and jumps to the real kernel.
3. The kernel builds its own data structures and takes the initramfs as a temporary root filesystem.
4. /init inside the initramfs loads the drivers needed to find the real root.
5. Having switched to the real root (switch_root), it runs init (usually systemd these days) as PID 1.

RTOSes and small machines#

Small machines usually have no stage that “loads an operating system”, because the kernel is linked together with the application into one image. FreeRTOS, Zephyr and NuttX are like this. Startup code runs from the reset vector, main is called, and starting the scheduler there sets the tasks running.

That does not mean there is no bootloader. If anything, a bootloader’s original job is clearest here.

The chain is a chain of trust#

Each link checks the next, it was said. Make that check a signature and the whole chain becomes a chain of trust — the firmware checks the bootloader’s signature, the bootloader the kernel’s, the kernel the modules’. Secure boot and embedded signed boot are the same story.

★ One property of this structure is worth stating. A chain can only create trust at its head. The first link (code inside ROM) must be unchangeable, which is why that place is called the root of trust. Shake the root and every check behind it means nothing — the checking code itself could have been swapped.

What to take from this#