GRUB Technical Info

by Erich Boleyn



Several major issues have plagued bootloaders for IBM PC compatibles for a long time, mostly related to compatibility.

For more detail about the operation of standard floppy and hard disk bootloaders, I have a 100K text document version of Hale Landis' How It Works Series, which is about the BIOS, booting, etc., and is very informative, though mildly outdated, and with what seem to be a few errors. I'm looking into getting updated information for flushing it out myself into a real HTML document.

The worst problems and the general way they are solved in GRUB are listed here (some of these have to be cooperatively solved with the OS):

Bootloader Size Limits

Bootloaders have to be very small, typically limited to one or more very small areas on the media in question.

At the start of the process, the BIOS loads the first block off of the boot disk (floppy or hard drive), 512 bytes in size. This one block must be capable of performing all the functions necessary to start up the system, or handing off to another program. On a hard disk, at least 64 bytes are reserved for a partition table, therefore unusable.

Traditionally, if the first block is not enough, at the start of the partition with the OS being booted (or, for a floppy, just at the beginning) is a fixed area, the size (generally from 512 bytes to 8 Kbytes) of which is dependent on the filesystem variety in question.

Most bootloaders are written to fit within this limitation, giving them only room for a very sparse functionality.

GRUB is very large compared to other bootloaders (typically 20 to 30 K). A mechanism is in place which can load all of it's components for different installal methods. The feeling from the author is that this will not be a problem since most of the features pay for themselves both in terms of space (certainly the generic decompression code, for example) and flexibilty to both end-users and experts.

Partitioning Issues

The traditional layout of a floppy on a PC is with the first block being the boot-controller, and the rest of the disk being formatted to some filesystem type.

The traditional layout of a hard disk on a PC is with the first block being the boot-controller, referred to as the MBR (Master Boot Record), with the rest of the disk subdivided into 4 sections (called "partitions"), each of which look either like a logical floppy (boot block + filsystem), or a full hard disk (sort of a recursive definition here, though only one of the partitions can be one of these). Inside one of the recursive hard disk definitions, only one of the 4 partitions can have a filesystem. The pratical result is that an arbitrary number of partitions can be represented. The biggest problem here is that generally only one of the 4 partitions listed directly in the main MBR can be the "active" one, which is the one where any subsidary boot blocks are pulled from.

Most bootloaders don't deal with the "active partition" marker in a very intelligent manner.

GRUB can both PC style partitions (normal and extended DOS-style) and 386BSD/Mach style BSD sub-partitions in a consistent manner, plus it can set the "active partition" marker as desired (he "active partition" marker is currently irrelevant to GRUBs actual behavior, this still needs some work related to default device notations).

Geometry Translation

There are several methods of using the BIOS to access a disk before any kind of driver is active. The only consistent one is the INT 13h interface, which uses an addressing scheme based on the Cylinder, Head, and Sector positions of a block, packed into a value consisting of 10 bits, 8 bits, and 6 bits, respectively.

To attempt to get around this issue, and in the case of SCSI disks, to allow a differential number of sectors in different physical cylinders without confusing the heck out of the software, the concept of Geometry Translation was introduced. Geometry Translation produces a transparent virtual mapping from some phantom number of Cylinders, Sectors and Heads onto the real hardware of the disk, generally trying to increase the space of the disk accessible via the INT 13h interface.

Another problem created from the above is that different controller/BIOS combinations (and possibly even different particular installations of software) can use different geometry translations, and since the bootloaders on the disk depend on the particular numbers, they either have to be carefully updated, or, in some cases, the whole OS must be re-installed when moving the disk to another controller/BIOS combination.

The essential issue is that pretty much all bootloaders prior to GRUB use Cylinder/Head/Sector numbers for the first stage of booting, so if that mapping should change, your OS can't boot, even though the linear mapping is the same, and if you could get it booted somehow, everything work would fine.

GRUB solves this by translating from/to a linear block-number AT ALL TIMES. This turns out to be OK, as the major OS used to test a BIOS translation mechanism, DOS, uses exactly the same mappings.

512MB - 8GB BIOS Translation Size Limits

Related to the Gemetry Translation problem is the problem that in standard INT 13h BIOS interface has a maximum of 24 bits to access the disk with.

The problem is that even presuming a perfectly spanned space, 24 bits is only 16 M blocks, and at 512 bytes each, this is a maximum disk size of 8 GB. Most real systems have limitations of either 512 MB (this is where the IDE limit of 508 MB comes from, I'm pretty sure, as the top 4 bits of the "head" number can't be used in most BIOS IDE interfaces), or 1 GB, though this is changing, moving toward the 8 GB maximum size.

GRUB can't universally solve this problem, as there is no new interface which is used in all machines. At least one newer interface which is present on some machines ("LBA", which is in more and more new ones, supposedly) may be able to be used transparently in place of INT 13h when available. This is still being investigated.

Memory size determination

Various OS's do this differently. Some rely on their bootloader, and some perform the probe themselves. Most are limited to detecting a maximum of 64MB on a PC, in any case. Kludges where a hard-coded portion telling the machine how much RAM is installed, or even compiling it in, have been made for many OSes.

Since this is both once-only code and only involves the BIOS, the solution which Multiboot and GRUB uses is to perform the probe in the bootloader. Look at the bulleted item "Detects all Installed RAM" in the section Features below.

Specifications and other Goals

The primary requirement for GRUB is that it be compliant with the Multiboot Standard.

The other goals, listed in approximate order of importance, are:

Except for specific compatibility modes (chain-loading and the Linux 'piggyback' format), all kernels will be started in much the same state as in the Multiboot Standard listed above. Only kernels being loaded at 1 megabyte or above are presently supported. Any attempt to load below that boundary will simply result in immediate failure and an error message reporting the problem.


In addition to the requirements in the previous section, GRUB has the following features (note that the Multiboot Standard doesn't explicitly require everything listed in it, but GRUB will support all options):

Future directions might include an internal programming language for supporting richer sets of boot options with control statements (it becomes a boot-script at that point), and possibly support for non-IBM PC-compatible machines.

One definite path for future work is how to fairly transparently get around the 8 GB geometry translation limitation.

Other Implementation Details

GRUB can completely replace the primary bootloader on a hard disk or floppy disk. On a hard disk, it can also be run after some other bootloader capable of chain-loading.

GRUB is broken into 2 distinct components, or stages, which are loaded at different times in the boot process. The Stage 1 has to know where to find Stage 2, and the Stage 2 has to know where to find it's configuration file (if Stage 2 doesn't have a config file, it drops into the command-line interface and waits for a user command).

Here is a memory map of the various components:

      0       to    4K-1 :   Interrupt & BIOS area.

      down  from    8K-1 :   16-bit stack area.

      8K   to  (ebss1.5) :   Stage-1.5 (optionally) loaded here by Stage-1.

      0x7c00  to  0x7dff :   Stage-1 loaded here by the BIOS.
      0x7e00  to  0x7e08 :   scratch space used by Stage-1.

      32K    to  (ebss2) :   Stage-2 loaded here by Stage-1.5 or Stage-1.

        (middle area)    :   heap used for random memory allocation.

      down  from  416K-1 :   32-bit stack area.

      416K    to  448K-1 :   Filesystem info buffer (when reading a filesys).
      448K  to  479.5K-1 :   BIOS track read buffer.
      479.5K  to  480K-1 :   512 byte fixed SCRATCH area.

      480K    to  511K-1 :   general storage heap.

Description of GRUB's major components (and some of the boot sequence):

Stage 1

Stage 1 is only used to load Stage 2. If Stage 2 can be loaded in some other manner in a compatible fashion, then Stage 1 is unnecessary, and doesn't need to be used.

Stage 1 "knows" where Stage 2 is by entries in a block-list loading table embedded in it. It loads the lists of blocks off of the booting drive, then jumps to a specified CS:IP in 16-bit real mode. These are described in the page on embedded data. It queries the BIOS for the disk geometry, and maps the linear block numbers there to C:H:S addresses used by the INT 13h BIOS interface.

See the Installation Guide for details on how to set up loading Stage 2 from Stage 1.

OPTIONAL Stage 1.5

Since the Stage 2 is so large (typically 30K or larger in size), a special stripped down version of the Stage 2 code, sort of a Stage 1.5, can be used because it might fit into one of the fixed areas of the disk. The idea is to have the Stage 1.5 look for a certain file and attempt to execute it as a Stage 2 (this allows changing Stage 2 easily, while leaving it a normal file in the filesystem).

This is actually the case for the BSD FFS filesystem. There is a fixed area 7K in size at the beginning of the partition which is reserved for the bootloader. The Stage 1.5 with BSD FFS filesystem support is about 6.5 K in size when compiled in a.out format, and fits nicely, allowing the Stage 2 to be a normal file in the "/boot/grub" directory of the install partition.

This same technique can in principle be applied to other filesystems, but the problem here is that the fixed area available to bootloaders is generally quite small (0.5 to 3 K), and a Stage 1.5 wouldn't fit.

It contains embedded data on where to look for the install partition and the Stage 2 (it uses what would be the "configuration file" entry in the Stage 2 for this purpose).

Stage 2

This component is the GRUB proper.

It gets most of the information about the machine and the boot state from the BIOS and information passed into it at starting time, except that it contains embedded data on where to look for the install partition and the configuration file.

The first action of the Stage 2 is to look for it's configuration file. If one is not found, then it drops into the command-line interface. If one is found, the full menu interface is activated containing whatever entries were found in the file (the command-line is still available via a command from the menu interface).