Matthew Garrett

Many people still install Linux from CDs. But a growing number install from USB. In an ideal world you'd be able to download one image that would let you do either, but it turns out that that's quite difficult. Shockingly enough, it's another situation where the system firmware exists to make your life difficult.

Booting a hard drive is pretty easy. The BIOS reads the first 512 bytes off the drive, copies them to RAM and executes them. That code is then responsible for either starting your bootloader or identifying the currently active partition and jumping to its boot sector, but before too long you're in a happy place where you're executing whatever you want to. Life is good. So you'd think that CDs would work in a similar way. The ISO 9660 format even leaves a whole 32KB at the start of a filesystem, which is enough space for a pretty awesome bootloader. But no. This is not how CDs work. That would be far too easy.

Let's imagine we're back in the 90s. People want to be able to boot off CD without needing a boot floppy to do so. And you're a PC vendor with a BIOS that's been lovingly[1] forced into a tiny piece of flash and which has to execute out of an almost as tiny piece of RAM if you want your users to be able to play any games. Letting boot code read arbitrary content off the CD would mean adding a new set of interrupt hooks, and that's going to be even more complicated because CDs have a sector size of 2K while hard drives are 512 bytes[2] and who's going to pay to implement this and for the extra flash and RAM and look surely there has to be another way?

So, of course, another way was found. The El Torito specification defines a way for shoving a reference to some linear blocks into the ISO 9660 header. The BIOS reads those blocks into memory and then redirects either the floppy or hard drive access interrupts (depending on the El Torito type) to that region. The boot code can then proceed as if it had been read off a floppy without all the trouble of actually putting a floppy in the machine, and the extra code required in the system BIOS is minimal.

USB sticks, however, are treated as hard drives. The BIOS won't look for El Torito images on them. Instead, it'll try to execute a boot sector. That isn't there on a CD image. Sigh.

A few years ago a piece of software called isohybrid popped up and solved this problem nicely. isohybrid is a companion to isolinux, which itself is a bootloader that fits into an El Torito image and can then load your kernel and installer from CD. isohybrid takes an ISO image, adds an x86 boot sector and partition table and does some more fiddling to turn a valid ISO image into one that can be copied directly onto a USB stick and booted. The world suddenly becomes a better place.

But that's BIOS. EFI makes this easier, right? Right?

No. EFI does not make this easier.

Despite EFI being a modern firmware for the modern world[3], EFI implementations are not required to be able to understand ISO 9660. In fact, I've never seen one that does. FAT is all the spec requires, and FAT is typically all you get. Nor will EFI just execute some arbitrary boot code from the start of the CD. So, how does EFI boot off CD?

El Torito. Obviously.

It's not quite as bad as it sounds, merely almost as bad as it sounds. While the typical way of using El Torito for a long time was to use floppy or hard drive emulation, it also supports a "No emulation" mode. It also supports setting a type flag for your media, which means you can distinguish between images intended for BIOS booting and EFI booting. But the fact remains that your CD has to include an embedded FAT partition that then contains a bootloader that's able to read ISO 9660 because your firmware is too inept to handle that itself[4].

How about USB sticks? Thankfully, booting these on EFI doesn't require any boot sectors at all. Instead you just have to have a partition table, a FAT partition and a bootloader in a well known location in that FAT partition. The required partition is, in fact, identical to the one you need in an El Torito image. And so this is where we start introducing some extra hacks.

Like I said earlier, isohybrid fakes up an MBR and adds some boot code that points at the actual bootloader. It needs to do a little more on EFI. The first problem is that the isohybrid MBR partition has to cover the entire ISO 9660 filesystem on the USB stick so that the operating system can access it later, but the El Torito FAT image is inside that partition. A lot of MBR-based code becomes very unhappy if you try to set up a partition that's a subset of another partition. So we can't really use MBR. On to GPT.

GPT, or the GUID Partition Table, is the EFI era's replacement for MBR partitions. It has two main advantages over MBR - firstly it can cover partitions larger than 2TB without having to increase sector size, and secondly it doesn't have the primary/logical partition horror that still makes MBR more difficult than it has any right to be. The format is pretty simple - you have a header block 1 logical block into the media (so 512 bytes on a typical USB stick), and then a pointer to a list of partitions. There's then a secondary table one block from the end of the disk, which points at another list of partitions. Both blocks have multiple CRCs that guarantee that neither the header nor the partition list have been corrupted. It turns out to be a relatively straightforward modification of isohybrid to get it to look for a secondary EFI image and construct a GPT entry pointing at it. This works surprisingly well, and media prepared this way will boot EFI machines if burned to a CD or written to a USB stick.

There's a few quirks. Macs will show two boot icons for these CDs[6], one marked "EFI Boot" and one helpfully marked "Windows"[7], with the latter booting the BIOS El Torito image. That's a little irritating, but not insurmountable. The other issue is that older Macs won't look for boot loaders in the legacy locations. This is where things start getting horrible.

Back in the old days, Apple boot media used to have a special "blessed" folder. Attempting to boot would involve the firmware looking for such a folder and then using that to start itself up. Any folder in the filesystem could be blessed. Modern hardware doesn't use boot folders, but does use boot files. For an HFS+ filesystem, the inode of the bootloader is written to a specific offset in the filesystem superblock and the firmware simply finds that inode and executes it. And this appears to be all that older Macs support.

So, having written a small tool to bless an HFS+ partition, I tried the obvious first step of burning a CD with three El Torito images (one BIOS, one FAT, one HFS+). It failed. While Refit could see the bootloader in the HFS+ image, the firmware appeared to have no interest at all in booting off it. Yet Apple install media would boot. What was the difference?

The difference, obviously, was that these earlier Macs don't appear to support El Torito booting. The Apple install media contained an Apple partition map.

The Apple partition map (APM) is Apple's legacy partition table format. Apple mostly dropped it when they went to x86, where it's retained for two purposes. The first is for drives that need to be shared between Intel Macs and PPC ones. The second seems to be for their install DVDs. Some further playing revealed that burning a CD with an APM entry pointing at the HFS+ filesystem on the CD gave me a boot icon. Problem solved?

Not really. Remember how I earlier mentioned that ISO 9660 leaves 32KB at the start of the image, and that an isohybrid image then writes an MBR and boot sector in the first 512 bytes of that, and the GPT header starts 512 bytes into a drive? That means that it's easy to produce an ISO that has both a boot sector, MBR partition table and GPT. None of them overlap. APM, on the other hand, has a header that's located at byte 0 of the media, overlapping with the boot sector. And it has a partition listing that's located at sector 1, overlapping with the GPT. Is all lost?

No. Merely sanity.

The first thing to remember is that the boot sector is just raw assembler. It's a byte stream that's executed by the CPU. And there's a lot of things you can tell a CPU to do that result in nothing happening. Peter Jones pointed out that the only bits of the AFP header you actually need are the letters "ER", followed by the sector size as a two byte big endian integer. These disassemble to harmless instructions, so we can simply move the boot code down a little and stick these at the beginning. A PC that executes it will read straight through the bizarre (but harmless) Apple bytes and then execute the real boot code.

The second thing that's important here is that we were just given the opportunity to specify the sector size. The GPT is only relevant when the image is written to a USB stick, so assumes a sector size of 512 bytes. So when the GPT starts one sector into the drive, it's actually starting 512 bytes into the drive. APM also starts one sector into the drive, but we can simply put a different sector size into the header and suddenly we're able to choose where that's going to be. 2K seems like a good choice, and so the firmware will now look for the header at byte 2048.

That's still in them middle of the GPT partition listing, though. Except we can avoid that as well. GPT lets you specify where the partition listing starts and doesn't require it to be immediately after the header. So we can offset the partition listing to, say, byte 8192 and leave a hole for the Apple partition map.

And, shockingly, this works. Setting up a CD this way gives a boot icon on old Macs. On new Macs, it gives three - one for legacy boot, one for EFI boot via FAT and one for EFI boot via HFS. Less than ideal, but eh. The one remaining problem is that this doesn't work for USB sticks (the firmware sees the GPT and ignores the APM), so we also need to add a GPT entry for the HFS+ partition. Job done.

So, it is possible to produce install media that will work if burned to CD or written to a USB stick. It's even possible to produce a version that will work on Macs, as long as you're willing to put up with three partition tables and an x86 boot sector that doubles as an APM header. And patches to isohybrid to do all of this will be turning up as soon as I tidy the code to the point where it works without having to hack in offsets by hand.

[1] Insert some other adverb here if you feel like it
[2] Why yes, 15 years later BIOSes still tend to assume 512 bytes. Which is why your 4K sector disk is much harder to work with than you'd like it to be.
[3] Ever noticed how the modern world involves a great deal of suffering, misery and death? EFI fits into that world perfectly.
[4] Obviously if you want your media to be bootable via both BIOS and EFI you need to produce a CD with two El Torito images. BIOS systems should ignore the image that says it's for EFI, and EFI systems should ignore the BIOS one. Some especially creative BIOS authors[5] have decided that users shouldn't have their choices limited in such a way, and so pop up a screen that says:

1.

2.

Select CD-ROM boot type:

and wait for the user to press a key. The lack of labels after the numbers is not a typographical error on my part.
[5] Older (pre-2009, and some 2009 models) Apple hardware has this bug if a dual-El Torito CD is booted via the BIOS compatibility layer. This is especially unfortunate because said machines often fail to provide a working keyboard emulation at this stage, resulting in you being stuck forever at an impressively unhelpful screen. This isn't a Linux bug, since it's happening before we've run any of our code at all. It's not even limited to Linux. 64-bit install media for Vista SP1, Windows 7 and Server 2008 all have similar El Torito layout and all trigger the same bug on Apple hardware. Apple's aware of this, and has resolved the issue by declaring that these machines don't support 64 bit Windows.
[6] Even further investigation reveals that Apple will show you as many icons as there are El Torito images, which is a rare example of Apple giving the user the freedom to brutally butcher their extremities if they so desire
[7] "Windows" is Apple code for "Booting via BIOS compatibility". The Apple boot menu will call any filesystem with a BIOS boot sector Windows.