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.