Understanding the Linux Boot Process

What is booting???
Booting in simplest terms is the process of starting the operating system whenever the computer is switched on.
Booting an operating system is a very complicated process, since it involves large number of initializations, managing all the procedures within the limited memory available at boot time, etc.

Lets start by taking a very high-level view of the whole process...

Figure below depicts the overall Linux boot process

What the above figure says :-
1) On power-up or reset, the processor executes the code at a well-known location. In PC, this location is the BIOS which is stored in the flash memory on motherboard.

2) BIOS determines which devices are the candidates for booting.

3) When boot-device is found, first stage boot-loader is loaded into RAM and executed.

4) The job of the first stage boot loader is to load the second stage boot-loader.

5) The second stage boot-loader provides the options for loading an operating system from various available options.

6) It then loads the compressed kernel image and the initial RAMdisk image.

7) Once the kernel is up, the init process is the first user space process to start execution, which perform high-level system initialization.

::All of the above steps can be summarized into 2 major steps ::
a) Booting the Linux kernel into memory and passing control to it.
b) Initializing the normal environment.

Now, lets look into what each step actually does.

Phase - 1 : Loading the kernel

This phase involves retrieving the kernel executable and some additional data from some storage media, load them at the right memory location and pass control to the kernel.

(1) System Startup

In PC, booting Linux begins in BIOS at an address 0xFFFF0. The BIOS routine consists of two parts. One is the POST code and other is the runtime services.

BIOS = POST code + Runtime services.

POST stands for Power-on self-test. It performs some preliminary tests. After POST is complete, it is flushed from memory.However, BIOS runtime services remain and are available to the target OS.

To boot an OS,
BIOS runtime services search for the devices that are both active and bootable in the order of preference defined by the CMOS settings. Now this device can be either of the following:

1) Floppy
2) CD-ROM
3) Partition on Hard Disk
4) Device on Network
5) USB flash memory stick

Let us consider the very common scenario i.e. Linux booting from a hard disk, where MBR(Master Boot Record) contains the primary boot.

MBR is a 512-byte sector located in the first sector on disk i.e. sector 1 of cylinder 0 head 0.

Once MBR is loaded into RAM, BIOS passes control to it.

(2) Stage 1 Boot-Loader

Primary boot loader resides in the MBR in 512-byte image. It contains both program code and a small partition table.


The partition table contains a record for each of the 4 primary partitions.

Job of the primary loader is to find and load the secondary boot loader. In order to achieve this, what it does is :
(i) Look through the partition table for active partition.
(ii) When it finds an active partition, it scans remaining partitions to ensure that they are all inactive.
(iii) On verification, active partition's boot record is read from the device into RAM and executed.

(3) Stage 2 Boot-Loader

Its task is to load the Linux kernel and optional RAMdisk. Both the first and second stages are combined called LILO or the GRUB loader in x86 PC environment. (Detailed explanation of boot loaders is a separate topic...coming soon ;) )

Here, i would just mention that the GRUB loader is a file-aware boot loader. i.e. it includes knowledge of Linux file systems.

GRUB can load a linux kernel from a ext2 or ext3 fs instead of raw disk. It does this by making the two-stage boot loader into 3-stage one.

Stage 1(MBR) boots stage 1.5 boot loader that understands the file system containing the Linux kernel image.
eg :
# ls /boot/grub/*stage1_5 -1
/boot/grub/e2fs_stage1_5
/boot/grub/fat_stage1_5
/boot/grub/jfs_stage1_5
/boot/grub/minix_stage1_5
/boot/grub/reiserfs_stage1_5
/boot/grub/xfs_stage1_5

When stage 1.5 is loaded and running, stage 2 can be loaded. With stage 2 loaded, GRUB can display a list of available kernels.This list is defined in /etc/grub.conf.
At this point of time, command line options can be given for booting a specific kernel and also ammendments are possible.

With 2nd stage loader in memory, the FS is consulted and default kernel image and initrd image are loaded into memory. Then Stage 2 loader invokes the kernel image.

Phase 2 - Running the kernel

(1) Kernel Image
Due to various memory limits on i386, the kernel image is actually a compressed image either zImage or bzImage, with some uncompressed code at the head of the image.
The head of the image contains routine that does some minimal amount of network setup and then decompresses the kernel contained within the image and places it into the high memory.
Then calls the kernel.


Following functions are called in the order specified.

a) startup_32
arch/x86/boot/compressed/head_32.S

b) decompress_kernel
arch/x86/boot/compressed/misc.c

c) startup_32
arch/x86/kernel/head_32.S

d) start_kernel
init/main.c

e) Kernel_thread -- (called from rest_init in start_kernel)
arch/x86/kernel/process_32.c
Starts the init function....The first user-space program.

Finally cpu_idle is invoked and scheduler can take control.

(2) initrd
The initrd function allows you to create a small Linux kernel with drivers compiled as loadable modules. These loadable modules give the kernel the means to access disks and the file systems on those disks, as well as drivers for other hardware assets. Because the root file system is a file system on a disk, the initrd function provides a means of bootstrapping to gain access to the disk and mount the real root file system.

It thus serves as temporary root file systems and allows kernel to fully boot without having to mount any physical disks.

Necessary modules to interact with all the peripherals can be a part of the initrs. Thus, kernel can be small.

initrd is mainly designed to allow system startup to occur in two phases,
where the kernel comes up with a minimum set of compiled-in drivers, and
where additional modules are loaded from initrd.

Now once the kernel is booted, the root fs is changed via pivot_root. i.e. root fs is mounted and initrd is removed.

This procedure of pivoting is something like you are standing on a carpet and you wish to replace the carpet underneath you. The solution is you spread the new carpet at the end of the present one and just jump over from old carpet to new carpet ;) .

(3) init
Kernel starts the user-space process. This is the first process executed which is compiled with the standard C library.

Reference :
1) http://www.ibm.com/developerworks/library/l-linuxboot/index.html
Above post is almost the same as the link given but presentation is somewhat different and has a few more points.

2) Almesberger, Werner; "Booting Linux: The History and the Future"
http://www.almesberger.net/cv/papers/ols2k-9.ps.gz

---