1. Doing Power-On Self-Test (POST)

2. Initialize the hardware devices. Specifically for PCI on setting IRQ for hardware not to conflict.

3. Searching OS to boot. BIOS does this by selecting apropriate boot device order. When valid device is found, copies the contents of its first sector (512 bytes) into RAM, starting from physical address 0x00007c00 then jump and execute those code. This code usually a bootsector or a bootloader.

The makefile flows like this (all relative to the linux root source code).

1. bzImage [arch/i386/tools/build.c]
	    
	    [arch/i386/boot/Makefile] {
	      tools/build -b bbootsect bsetup compressed/bvmlinux.out CURRENT > bzImage
	    }
	    
	    2. arch/i386/boot/bbootsect.o
	    2. arch/i386/boot/bsetup.o
	    2. arch/i386/boot/compressed/bvmlinux.out
	        
		[arch/i386/boot/Makefile] {
		  objcopy -O binary -R .note -R .comment -S \
		  arch/i386/boot/compressed/bvmlinux arch/i386/boot/compressed/bvmlinux.out
		}
		
		3. arch/i386/boot/compressed/bvmlinux
		    
		    [arch/i386/boot/compressed/Makefile] {
		      ld -m elf_i386 -Ttext 0x100000 -e startup_32 -o bvmlinux head.o misc.o piggy.o
		    }
		    
		    4. arch/i386/boot/compressed/head.o
		    4. arch/i386/boot/compressed/misc.o
		    4. arch/i386/boot/compressed/piggy.o
		        
			[arch/i386/boot/compressed/Makefile] {
			  objcopy -O binary -R .note -R .comment -S vmlinux $tmppiggy;
			  gzip -f -9 < $tmppiggy > $tmppiggy.gz;
			  echo "
			    SECTIONS { 
			      .data : { 
			        input_len = .;
				LONG(input_data_end - input_data) input_data = .;
				*(.data) input_data_end = .;
			      }
			    }" > $tmppiggy.lnk;
			  ld -m elf_i386 -r -o piggy.o -b binary $tmppiggy.gz -b elf32-i386 -T $tmppiggy.lnk;
			}
			
			5. vmlinux
			    
			    [linux/Makefile] {
			      ld -m elf_i386 -T arch/i386/vmlinux.lds -e stext \
			      arch/i386/kernel/head.o \
			      arch/i386/kernel/init_task.o \
			      init/main.o \
			      init/version.o \
			      init/do_mounts.o \
			      --start-group \
			        arch/i386/kernel/kernel.o \
				arch/i386/mm/mm.o \
				kernel/kernel.o \
				mm/mm.o \
				fs/fs.o \
				ipc/ipc.o \
				drivers/char/char.o \
				drivers/block/block.o \
				drivers/misc/misc.o \
				drivers/net/net.o \
				drivers/media/media.o \
				net/network.o \
				arch/i386/lib/lib.a \
				lib/lib.a \
				arch/i386/lib/lib.a \
			      --end-group \
			      -o vmlinux
			    }
			    
			    6. arch/i386/kernel/*
			    6. arch/i386/lib/*
			    6. arch/i386/math-emu/*
			    6. arch/i386/mm/*
			    6. drivers/*
			    6. fs/*
			    6. init/*
			    6. ipc/*
			    6. kernel/*
			    6. lib/*
			    6. mm/*
			    net/*

This code is invoked by BIOS. Particulary the size is not only 512 bytes, but rest of code is loaded by this first sector afterwards.

Linux Kernel is compressed, so size is matter when we'd like to boot from floppy. Compression is done at compile time then decompression is done by the loader. The code is arch/i386/boot/bootsect.S. After this code is compiled, the size is 512 bytes. After kernel image is already compiled, the bootsect code is placed at the begining of this kernel image. When BIOS fetch first sector on floppy, actually this bootsect code is fetched by BIOS. Here it is what the bootsect does:

1. Moves itself from 0x00007c00 to 0x00090000

2. Set real mode stack from address 0x00003ff4. This stack grows toward lower address.

3. Sets up disk parameter table, used by the BIOS to handle the floppy device driver.

4. Invokes a BIOS procedure to display a "Loading" message.

5. Invokes a BIOS procedure to load setup() code of the kernel image from floppy and puts this setup() code in RAM starting from address 0x00090200.

6. Invokes a BIOS procedure to load the rest of the kernel image from floppy and puts the image in RAM starting from either low address 0x00010000 (zImage) or high address 0x00100000 (bzImage).

7. Jumps to setup() code.

Wellknown boot loader in linux are LILO and GRUB. Basically all boot loader performs the same operation. It manages its own bussiness then at last taking care the image. Typically they copy the integrated boot loader of the kernel image to address 0x00090000, then the setup() code to address 0x00090200, and the rest of the kernel image to address 0x00010000 or 0x00100000. Then jumps to setup() code.

It is placed at offset 0x200 of the kernel image by the linker, immediately after the integrated boot loader (that's why the loader easily locate the code and copy the code into RAM, starting from physical address 0x00090200). setup() function initialize the hardware device in the computer and set up the environment for the execution of the kernel program. The kernel does not rely on BIOS, to enhance portability and robustness. Here it is what setup() function performs:

1. Invokes a BIOS procedure to find out the amount of RAM on system.

2. Sets the keyboard repeat delay and rate.

3. Initializes the video adapter.

4. Reinitializes the disk controller and determines the hard disk parameters

5. Checks for an IBM Micro Channel bus (MCA).

6. Checks for a PS/2 pointing device (bus mouse).

7. Checks for Advanced Power Management (APM) BIOS support.

8. If the kernel was loaded low in RAM (at physical address 0x00010000), moves it to physical address 0x00001000. Conversely if it was loaded high, keep it just the way it was. This step is necessary because kernel image is compressed, and the decompression routine needs some free space to use as a temporary buffer following the kernel image in RAM.

   The decision of loaded high or low is based on code32_start variable in the header of setup.S. This is decided by __BIG_KERNEL__ preprocessor macro that has a correlation with the compilation process:

    

    gcc -E -D__KERNEL__ -I/usr/src/linux-2.4.20/include -D__BIG_KERNEL__ -D__ASSEMBLY__ -traditional -DSVGA_MODE=NORMAL_VGA setup.S -o bsetup.s; as -o bsetup.o bsetup.s;

9. You see there... the "-D__BIG_KERNEL__". Now you've should got the idea.

10. Sets up a provisional IDT and GDT.

11. Resets FPU, if any.

12. Reprograms the PIC and maps the 16 hardware interrupts (IRQ lines) to the range of vectors from 32 to 47. We need to perform this because BIOS erroneously maps the IRQs in the range from 0 to 15, which is already used for CPU exceptions.

13. Switches the CPU to Protected Mode by setting PE in the cr0 status register. Until here, the PG bit in cr0 register is still cleared, so paging is still disabled.

14. Jumps to startup_32() function

There are 2 startup_32() functions:

1. startup_32() function in arch/i386/boot/compressed/head.S. After setup() terminates, we have been moved either to physical address 0x00100000 or 0x00001000. This function does:

   1. Initializes the segment registers and a provisional stack.

   2. Fills the area of uninitialized data of the kernel identified by the _edata and _end symbols with zeros.

   3. Invokes the decompress_kernel() function to decompress the kernel image. The "Uncompressing Linux..." message is displayed first. Then after decompression is done, the "OK, booting the kernel." message is shown. if the kernel image was loaded low, the decompressed kernel is placed at physical address 0x00100000. Otherwise, if the kernel image was loaded high, the decompressed kernel is placed in temporary buffer located after the compressed image. The decompressed image is then moved into its final position, which starts at physical address 0x00100000.

   4. Jumps to physical address 0x00100000.

2. startup_32() function in arch/i386/kernel/head.S. This function is the begin of decompressed kernel at 0x00100000 (similiar name does not create any problems becouse both functions are executed by jumping to their initial physical address). This second startup_32() function sets up the execution environment for the first linux process (process 0 / swapper). This is what it does:

   1. Initializes the segment registers with their final values.

   2. Sets up the kernel mode stack for process 0.

   3. Initializes the provisional kernel page tables contained in swapper_pg_dir and pg0 to identically map linear addresses to the same physical addresses.

   4. Stores the address of the Page Global Directory (PGD) in the cr3 register, and enables paging by setting the PG bit in the cr0 register.

   5. Fills the bss segment of the kernel with zeros.

   6. Invokes setup_idt() to fill the IDT with null interrupt handlers.

   7. Puts the system parameters obtained from the BIOS and the paramaters passed to the OS into the first page frame.

   8. Identifies the model of the processor.

   9. Loads the gdtr and idtr registers with the address of the GDT and IDT tables.

   10. Jumps to the start_kernel() function.

This function completes the initialization of the kernel. Almost all rest kernel component is initialized by this function. For example:

• Page tables are initialized by calling paging_init() function.

• Page descriptors are initialized by calling kmem_init(), free_area_init(), and mem_init() functions.

• Final initialization of the IDT is performed by invoking trap_init() and init_IRQ().

• Slab allocator is initialized by calling kmem_cache_init() and kmem_cache_sizes_init() functions.

• System date and time are initialized by time_init() function.

• Kernel thread for process 1 is created by invoking kernel_thread() function. In turn this kernel thread creates the other kernel threads and executes the /sbin/init program.

Besides the "Linux version 2.4..." message, which is displayed right after the beginning of start_kernel(), many others are displayed along with this last phase, both by the init functions and by the kernel threads. At the end shows up login prompt.

This is just an emphasize to the detail of previous step. I'll skip the arch/i386/boot/bootsect.S, because this code is rather obsolete.

setup() is located at physical address 0x00090200. setup.S is responsible for getting the system data from the BIOS and putting them into appropriate places in system memory.

Other boot loaders, like GNU GRUB and LILO, can load bzImage too. Such boot loaders should load bzImage into memory and setup "real-mode kernel header", esp. type_of_loader, then pass control to bsetup directly. setup.S assumes:

• bsetup or setup may not be loaded at SETUPSEG:0, i.e. CS may not be equal to SETUPSEG when control is passed to setup.S.

• The first 4 sectors of setup are loaded right after bootsect. The reset may be loaded at SYSSEG:0, preceding vmlinux. This assumption does not apply to bsetup.

The arch/i386/boot/setup.S contains:

1. Header and another important variable.

2. Checking code integrity. As setup.S code may not be contiguous, we should check code integrity by checking the signature.

3. Checking loader type. Check if the loader is compatible with the image.

4. Getting memory size. Try three different memory detection schemes to get the extended memory size (above 1 MB) in KB. First, try e820h, which lets us assemble a memory map. Then try e801h, which returns a 32-bit memory size. And finally 88h, which returns 0-64 MB.

5. Checking hardware support. Check hardware support, like keyboard, video adapter (calling arch/i386/boot/video.S), hard disk, MCA bus and pointing device.

6. Check BIOS APM support

7. Prepare for Protected Mode

8. Enable A20

9. Switch to Protected Mode

10. Jump to arch/i386/boot/compressed/head.S:startup_32

We are in bvmlinux now! With the help of misc.c:decompress_kernel(), we are going to decompress piggy.o to get the resident kernel image linux/vmlinux. This file is of pure 32-bit startup code. After decompression succeed, the piggy.o has been unzipped (vmlinux) and control is passed to __KERNEL_CS:100000, i.e. linux/arch/i386/kernel/head.S:startup_32().

The decompressed kernel code is just a normal code that flowing down.

      |startup_32 --- [arch/i386/kernel/head.S]:
         |start_kernel --- [init/main.c]
	 |lock_kernel --- [include/asm/smplock.h]
	 |setup_arch --- [arch/i386/kernel/setup.c]
	 |trap_init --- [arch/i386/kernel/traps.c]
	 |init_IRQ --- [arch/i386/kernel/i8259.c]
	 |sched_init --- [kernel/sched.c]
	 |softirq_init --- [kernel/softirq.c]
	 |time_init --- [arch/i386/kernel/time.c]
	 |console_init --- [drivers/char/tty_io.c]
	 
	 #ifdef CONFIG_MODULES 
	   |init_modules --- [kernel/module.c]
	 #endif 
	 
	 |kmem_cache_init --- [mm/slab.c]
	 |sti --- [include/asm/system.h]
	 |calibrate_delay --- [init/main.c]
	 |mem_init --- [arch/i386/mm/init.c]
	 |kmem_cache_sizes_init --- [mm/slab.c]
	 |pgtable_cache_init --- [arch/i386/mm/init.c]
	 |fork_init --- [kernel/fork.c]
	 |proc_caches_init --- [kernel/fork.c]
	 |vfs_caches_init --- [fs/dcache.c]
	 |buffer_init --- [fs/buffer.c]
	 |page_cache_init --- [mm/filemap.c]
	 |signals_init --- [kernel/signal.c]
	 
	 #ifdef CONFIG_PROC_FS 
	   |proc_root_init --- [fs/proc/root.c]
	 #endif 
	 
	 #if defined(CONFIG_SYSVIPC) 
	   |ipc_init --- [ipc/util.c]
	 #endif 
	 
	 |check_bugs --- [include/asm/bugs.h]
	 |smp_init --- [init/main.c]
	 |rest_init --- [init/main.c]
	   |kernel_thread --- [arch/i386/kernel/process.c]
	   |unlock_kernel --- [include/asm/smplock.h]
	   |cpu_idle --- [arch/i386/kernel/process.c]

The rest_init() does the following:

1. Launches the kernel thread "init".

2. Calls unlock_kernel().

3. Makes the kernel run cpu_idle() routine, that will be the idle loop executing when nothing is scheduled.

In fact the start_kernel procedure never ends. It will execute cpu_idle routine endlessly. The "init", the first kernel thread, does:

      |init --- [init/main.c]
        |lock_kernel --- [include/asm/smplock.h]
	|do_basic_setup --- [init/main.c]
	  |mtrr_init --- [arch/i386/kernel/mtrr.c]
	  |sysctl_init --- [kernel/sysctl.c]
	  |pci_init --- [drivers/pci/pci.c]
	  |sock_init --- [net/socket.c]
	  |start_context_thread --- [kernel/context.c]
	  |do_initcalls --- [init/main.c]
	    |(*call())-> kswapd_init --- [mm/vmscan.c]
	|prepare_namespace --- [init/do_mounts.c]
	|free_initmem --- [arch/i386/mm/init.c]
	|unlock_kernel --- [include/asm/smplock.h]
	|execve --- [include/asm/unistd.h]

Linux-Init-HOWTO.html

Linux-i386-Boot-Code-HOWTO

KernelAnalysis-HOWTO

- d