A brief intro to Linux Cache Structure

there are many algorithms for memory allocation, but none of them have a net gain of benefit, all makes a trade off. the basic memory allocation algorithms are heap allocation, which the kernel divides cache into blocks that fit to the requested size, and de-allocate them after use. the algorithm is efficient in cache usage, but causes significant fragmentation.

the buddy allocation combines blocks of cache together after deallocation if neighborhood memory blocks are also free. and it allocates memory by the best fit approach. this is better than heap, but require more processing.

the linux kernel uses SunOS cache allocation algorithm the "slab allocation". its basic structure looks like this:
the kernel memory cache is listed as a chain, it is then subdivided into slabs, catagorized into slab full, slab partial, slab empty, and each slab contains a page of memory, each page is composed of objects being allocated.

the idea is that kernel takes much longer time to initilize objects than to allocate and deallocate memory, using slab caching, kernel can reuse the previously allocated memory, without initialize it, for reuse.

full tutorial can be found here.

linux booting process summary

just a summary of how linux boots up from the ground:

5 steps

1. PC loads BIOS from flash memory. BIOS sets up hardware configuration, and read from special registry to use a device as the booting device, usually the hard disk. if it is hard disk, it loads the first sector of 512 bytes into memory.

2. the 512 bytes contains executable code for boot loader, the first ~400 bytes are executable code, then follows with 64 bytes of 4 primary partition information, including starting sector, ending sector, size etc, and then a 2 byte magic code 0xAA55 as boot sector validity checker. It loads the chosen booting partition (and mark other partitions not booted) and loads the second part of the boot loader.

3. the second part of the boot loader reads the partition loads the file system of the volumn, and reads the bootloader entirely and prompt the user to load the kernel. it put kernel into memory and transfers control to the kernel

4. the kernel executes and creates the real root system, loads up modules to control the hardware etc, and starts the init process which is for user processies

5. the init initializes the user processies, this is where the terminal starts up, or the log screen starts up

4. the rest of the bootloader locates the