Everyday millions of Linux users all over the world switch on their computers, wait for a few seconds (or minutes depending on their CPU speeds) to see their favorite operating system booting, and finally get the "login" prompt. That's it. It causes immense pleasure just to log into your favorite operating system and work. Doesn't it? Well, as for me, surely it does. (Though I need to switch on my own computer after every two months, cause I let it run all the time!).
As many of the readers must have noticed, when the computer is bootstrapping itself, a lot of messages come up on the screen. These can be viewed later by issuing the command: cat /var/log/dmesg | more (cause it usually produces a lot of output). Now, the question is: Hey, what do these messages mean in reality? That's easy to answer: Look into any Linux textbook, and you will find it's mentioned something like this: "it refers to the Kernel Boot messages" and so on. But, is that all? And what is meant by "Kernel Boot messages"?
Life has taught me a lot of things. Patience is one of them. And to understand the internal workings of Linux requires a lot of patience and sacrifice cause it requires the proper understanding of the "Linux Kernel Architecture". Most Linux users don't have either that much time to understand the "Linux Kernel Architecture", or maybe are not that much interested in it, while some may have other important things to do in life.
I am NOT going to explain the "Linux Kernel Architecture" in this article cause it would require a whole book to do so. Rather, in this article, I explain in detail one of the most fundamental concepts of a computer-system - Bootstrapping a computer running Linux. In other words, I would explain (at least try to do so) the entire process from the time one switches on the computer till the "login" prompt appears on the screen (assuming he/she is using CLI mode). In short, we would see how the Linux Kernel, and thus the whole system, is "bootstrapped".
1. Bootstrapping. What's that?
Traditionally, the term "bootstrap" refers to a person who tries to stand up (usually while lying down cause he was tired!) by pulling his/her own boots. In operating systems, the term refers to the process in which a part of the operating system is brought into the Main Memory, with the processor executing it. The internal data structures of the Linux Kernel are also initialized, values are set to the constituent variable(s), and processes are created (that usually spawn other significant processes later). Computer bootstrapping is a long and complicated task, cause when the computer is switched on, all the hardware devices are in a unpredictable state, while the RAM is inactive and in a random state. Thus, the thing to be kept in mind is, the process called "bootstrapping" is highly dependent on the computer architecture.
2. BIOS. What's that? What does it do?
When a computer is powered on, initially, it's practically useless. Cause the RAM chips contain random data, aren't initialized, and there's no operating system present. To begin the "bootstrapping", a special hardware circuit raises the logical value of the RESET pin of the CPU. Then, some CPU registers, which include registers like cs (a Segmentation Register - code segment register, which points to a segment containing program instructions) and eip ( when a processor-detected exception is generated by the CPU, that is, in other words, an exception raised by the CPU when the CPU detects an anomalous condition while executing an instruction, they are further of three types, namely "faults", "traps" and "aborts", depending on the value of the eip register that is saved on the Kernel Mode stack when the CPU control unit raises the exception.) are set to fixed values. Then, the code found at physical address 0xfffffff0 is executed. This address is mapped by the hardware to some read-only, permanent memory-chip, a special kind of memory which is usually called ROM (Read-Only Memory). BIOS (Basic Input/Output System) is a set of programs that is stored in ROM. It consists of several interrupt-driven low-level procedures used by various operating systems to handle the hardware devices that constitute the computer-system. Microsoft DOS is one such OS.
The question that now comes up is: Then, does Linux use the BIOS to initialize the hardware devices attached to the computer system? Or, is it anything else that performs the same task? If yes, what's it? Well, the answer is not that simple, cause the answer needs to be understood carefully. Starting with the 80386 model, Intel microprocessors perform address translation (from Logical Address --> Linear Address --> Physical Address) in two different ways called the "Real mode" and "Protected mode". Real mode exists mainly to maintain processor compatibility with older models. In fact, all BIOS procedures are executed in Real mode. But, the Linux Kernel executes in the Protected mode and NOT in the Real mode. Thus, once initialized, Linux does NOT make any use of BIOS but provides its own device drivers for every hardware device on the computer.
The question that now comes up is: When Linux uses "Protected mode", why can't BIOS use the same mode? BIOS uses the Real mode, cause it utilizes Real mode addresses for its operation, and Real mode addresses are the only ones available when the computer is switched on. A Real mode address is a seg segment and an off offset; thus the corresponding physical address is given by seg*(2*8)+off. (Please note: Since a Segment Descriptor is 8 bytes long, its relative address inside the GDT or the LDT is obtained by multiplying the most significant 13 bits of the Segment Selector by 8).
So, does this mean Linux never uses BIOS during the entire process of "bootstrapping"? Well, the answer is No, Linux is forced to use BIOS in the bootstrapping phase when it has to retrieve the Kernel image from disk or some other external device.
To sum up this section, let's look closely at the main operations that the BIOS performs during the bootstrapping sequence. They are as follows:
3. Boot Loader. What's that? What does it do?
The BIOS invokes (note: NOT executes) a special program whose main (rather only) task is to load the image of an operating system Kernel into RAM. This program is called the Boot Loader. Before we proceed any further, let's take a brief look in the different ways a system can be booted:
1. Booting Linux from a Floppy disk : When booting from a floppy disk, the instructions stored in the first sector of the floppy disk is loaded in RAM and executed. These instructions then copy all the remaining sectors containing the Kernel image into RAM.
2. Booting Linux from a Hard disk : When booting from the hard disk, the booting procedure is different. The first sector of the hard disk, called the Mater Boot Record (MBR) includes the partition table and a small program. This program loads the first sector of the partition containing the operating system to be started. Linux is highly flexible and sophisticated piece of software, thus it replaces this small program in the MBR with a sophisticated program called LILO (LInux boot LOader). LILO allows users to select the operating system to be booted.
Now, let's take a more deeper and detailed look into these 2 different ways of booting a system.
4. Booting Linux from Floppy Disk.
The Linux Kernel fits into a single 1.44-MB floppy disk. (In fact, there exists a type of Red Hat Linux installation known as "stripped-off" type, which requires approx. 2 MB physical RAM and approx. 1.44 MB hard disk space for running a Red Hat Linux system. That's what Linux is all about, after all. Isn't it?) But the only way to store a Linux Kernel on a single floppy disk is to compress the "Linux Kernel Image". The point to remember here is that, compressing is done at compile time, while decompressing is done at boot time by the loader.
When you're booting Linux from a floppy disk, the boot loader in case of booting Linux from a floppy disk is very simple. It has been coded in the assembly-language file /usr/src/linux-2.4.2/arch/i386/boot/bootsect.S. When we compile the Linux Kernel source, and obtain a new kernel image, the executable code yielded by this assembly language file is place at the beginning of the Kernel image file. This makes it easy to produce a floppy disk containing the Linux Kernel.
Copying the kernel image starting from the first sector of the disk can create the floppy. When the BIOS loads the first sector of the floppy disk, it actually copies the code of the boot loader. The boot loader, which is invoked by BIOS (by jumping to the physical address 0x00007c00) performs the following operations:
5. Booting Linux from Hard Disk.
The Linux Kernel is mostly loaded from the hard disk. This requires a two-stage boot loader. On Intel systems, the most commonly used Linux boot loader is named LILO. For other architectures, other Linux boot loaders exist. LILO may either be installed on the MBR (Please note: During Red Hat Linux Installation there comes a step where the user has to either write LILO to the MBR or put it in the boot sector) or in the boot sector of an active disk partition.
LILO is broken into 2 parts, otherwise it would be too large to fit into the MBR. The MBR or the disk partition boot sector includes a small boot loader, which is loaded into RAM starting from address 0x00007c00 by the BIOS. This small program moves itself to the address 0x0009a000, then sets up the Real Mode stack, and then finally loads the second part of the LILO boot loader. (Please note: The Real Mode stack ranges from 0x0009b000 to 0x0009a200).
The second part of LILO reads all the available operating systems from disk and offers the user a prompt so that he/she can choose any one of them from that available list. After the user has chosen any one Kernel (on my system, one can opt for any 1 Linux Kernel out of 8 Custom Kernels!) to be loaded, the boot loader may either copy the boot sector of the corresponding partition into RAM and execute it or directly copy the Kernel image into RAM.
Since the Linux Kernel image must be booted, the Linux boot loader performs essentially the same operations as the boot loader integrated into the Kernel image. The boot loader, which is invoked by BIOS (by jumping to the physical address 0x00007c00) performs the following operations:
6. The setup( ) function. What does it do?
Now, time has come to take a deeper look into some of the essential assembly language functions that are indispensable for the "bootstrapping" process. Here we look at the setup( ) function.
The setup( ) function can be found in the file /usr/src/linux-2.4.2/arch/i386/boot/setup.S. The code of the setup( ) assembly language function is placed by the linker immediately after the integrated boot loader of the Kernel, that is, at offset 0x200 of the Kernel Image file. This allows the boot loader to locate the code easily and copy it onto the RAM starting from the physical address 0x00090200.
Now the question that comes up is: What does this setup( ) function do? As its name suggests, it's supposed to set up something. But what? And how?
As we all know, for the kernel to operate properly, all the hardware devices in the computer must be detected, and then initialized in an orderly fashion. What the setup( ) function does is initialize all the hardware devices and thus creates an environment for the Kernel to operate in.
But, hang on a second. Didn't we see a few minutes earlier, that the BIOS was supposed to do all this stuff? Yeah, you are right. 100%. Although the BIOS already initialized most hardware, the Linux Kernel does NOT rely on it and initializes all of the hardware in its own fashion. But, if someone asks, well, why does Linux operate in such a way? The answer to this question is both very easy yet extremely difficult to explain. The Linux Kernel had been so designed to enhance portability and robustness. This is one of the many features that makes the Linux Kernel the best out of all the Unix and Unix-like Kernels available and makes it unique in so many ways. A proper understanding of why and exactly how the Linux Kernel implements this feature is beyond the scope of this topic and would require an extremely detailed coverage of the essential features of the Linux Kernel Architecture.
The setup( ) code mainly performs the following tasks:
Now from here on, the going gets a bit tougher as the "bootstrap" process gets a bit more complicated. I hope you put aside everything and carefully try to understand from here on.
7. The startup_32( ) function - 1st function. What does it do?
Okay, let's get to the confusing point straight away. There exist two functions called startup_32(). Although both these two startup_32() functions are assembly language functions and are required for "bootstrap" process, they are totally different functions. The one we refer to here is coded in /usr/src/linux-2.4.2/arch/i386/boot/compressed/head.S file. After setup() code is executed, the function has been moved either to physical address 0x00100000 or to physical address 0x00001000, depending on whether the Kernel Image was loaded "high" or "low" in RAM.
This function when executes, performs the following operations:
Now, after the 4th operation (as mentioned above is over), code execution is taken over by the other startup_32( ) function. In other words, the second one takes over the bootstrapping process.
8. The startup_32( ) function - 2nd function. What does it do?
The decompressed Linux kernel image begins with another startup_32( ) function. This function exists in /usr/src/linux-2.4.2/arch/i386/kernel/head.S file.
The question that must come up here is: Hey, using two different functions having the same name Doesn't this cause problem? The answer is: Well, no it doesn't at all. Cause both functions are executed by jumping to their initial physical addresses and hence they are executed in their own execution environments. No problem at all!
Now, let's look at the second startup_32( ) function functionality. What does it do? This function when executes, it essentially sets up the execution environment for the first Linux process (process 0). The function performs the following operations:
9. The start_kernel( ) function. What does it do?
The start_kernel( ) function completes the "initialization" of the Linux Kernel. All the essential Kernel components are initialized when this function executes. And this in fact is the last step of the entire "bootstrapping" process.
The following takes place when this function executes:
The "Linux version 2.4.2 " message is displayed right after the beginning of start_kernel( ). Many other messages are displayed also. At the very end, the very familiar login prompt appears on the console. This tells the user that the Linux Kernel is up and running, and just raring to go . And dominate the world!
This sums up our long and tedious journey of the entire "bootstrapping" process of a Linux system, or in other words, of a computer system running Linux operating system. As the readers would rightly note, I have NOT explained most of the other components and terms that I have had used. A few include IDT, GDT, eip register, cs register and so on. The full explanation of all these terms would make it impossible to complete the article in just a few pages, and would make the entire topic rather very boring. So, I really hope the readers would understand the fact that in this article I provide everyone with a glimpse of the processes and other various things that take place when a Linux system boots. In depth coverage of all the associated functions like paging_init( ) and mem_init( ) is beyond the scope of this topic.