Memory: from sys_bkr, sys_mmap2 to RAM
- __kfifo - FIFO or queue
- idr - map UID to pointer
- rb_root - red-black tree
- list_head - double linked list
- klist - list_head extension
Kernel Memory AllocationEdit
Slab allocation is a memory management mechanism intended for the efficient memory allocation of kernel objects. It eliminates fragmentation caused by allocations and deallocations. The technique is used to retain allocated memory that contains a data object of a certain type for reuse upon subsequent allocations of objects of the same type. Linux used a Slab allocation as the default allocator since kernel 2.2 until 2.6.23, when SLUB allocation became the default, but it is still available as an option.
A slab can be thought of as an array of objects of certain type or with the same size, spanning through one or more contiguous pages of memory; for example, the slab named "task_struct" holds objects of
struct task_struct type, used by the scheduling subsystem. Other slabs store objects used by other subsystems, and there is also slabs for dynamic allocations inside the kernel, such as the "kmalloc-64" slab that holds up to 64-byte chunks requested via kmalloc() calls. In a slab, each object can be allocated and freed separately.
The primary motivation for slab allocation is that the initialization and destruction of kernel data objects can actually outweigh the cost of allocating memory for them. As object creation and deletion are widely employed by the kernel, overhead costs of initialization can result in significant performance drops. The notion of object caching was therefore introduced in order to avoid the invocation of functions used to initialize object state.
With slab allocation, memory chunks suitable to fit data objects of certain type or size are preallocated. The slab allocator keeps track of these chunks, known as caches, so that when a request to allocate memory for a data object of a certain type is received, it can instantly satisfy the request with an already allocated slot. Destruction of the object does not free up the memory, but only opens a slot which is put in the list of free slots by the slab allocator. The next call to allocate memory of the same size will return the now unused memory slot. This process eliminates the need to search for suitable memory space and greatly alleviates memory fragmentation. In this context, a slab is one or more contiguous pages in the memory containing pre-allocated memory chunks.
Slab allocation provides a kind of front-end to the zoned buddy allocator for those sections of the kernel that require more flexible memory allocation than the standard 4KB page size.
SLAB is the name given to the first slab allocator implemented in the kernel to distinguish it from later allocators that use the same interface. It's heavily based on Jeff Bonwick's paper "The Slab Allocator: An Object-Caching Kernel Memory Allocator" (1994) describing the first slab allocator implemented in the Solaris 5.4 kernel.
SLUB (acronym of "the unqueued slab allocator") is the iteration of the slab allocator that replaced it and became the Linux default allocator since 2.6.23.
Unfortunately, SLAB and SLUB allocators consume a big amount of memory allocating their slabs, which is a serious drawback in small systems with memory constraints, such as embedded systems. To overcome it, the SLOB (Simple List Of Blocks) allocator was designed in January 2006 by Matt Mackall as a simpler method to allocate kernel objects.
SLOB allocator uses a first-fit algorithm, which chooses the first available space for memory. This algorithm reduces memory comsumption, but a major limitation of this method is that it suffers greatly from internal fragmentation.
The SLOB allocator is also used as a fall back by the kernel build system when no slab allocator is defined (when the CONFIG_SLAB flag is disabled).
The SLOB allocator implementation lives in the source file
- Linux Kernel Development, Third Edition (2010) by Robert Love - Chapter 12: Memory Management
- The SLUB allocator
- "SLUB: The unqueued slab allocator V6"
- "slob: introduce the SLOB allocator"
- Anatomy of the Linux slab allocator (Archive.org mirror of the M. Tim Jones' article)
- "Understanding the Linux Virtual Memory Manager" Chapter 8: Slab Allocator by Mel Gorman
- Video "SL[AUO]B: Kernel memory allocator design and philosophy" Christopher Lameter (Linux.conf.au 2015 conference) Slides
- cat /proc/meminfo
- #include <linux/mm.h>
- #include <linux/malloc.h>
- kmalloc, kfree
- #include <linux/vmalloc.h>
- vmalloc, vfree
- #include <asm/io.h>
- ioremap, iounmap
- page at #include <linux/mm.h>
- Understanding the Linux Kernel, Third Edition (2005) by by Daniel P. Bovet and Marco Cesati
- Linux Device Drivers, Third Edition (2005) by Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman - Book under Creative Commons Attribution-ShareAlike 2.0 license 
- Understanding the Linux Virtual Memory Manager Mel Gorman (2007) - Book under Open Publication License
- Linux Kernel 2.4 Internals (2002) 4. Linux Page Cache - from The Linux Documentation Project
- The Linux Kernel (1999) Chapter 3: Memory Management - from The Linux Documentation Project
- Linux Device Drivers, 2nd Edition (2001) by Alessandro Rubini & Jonathan Corbet
- How the Kernel Manages Your Memory
- LWN technical articles about Linux Memory Management (CC-BY-SA 4.0 licensed):