Slab allocation


Slab allocation is a memory management mechanism intended for the efficient memory allocation of objects. Compared to earlier mechanisms, it reduces 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. It is analogous to an object pool, but only applies to memory, not other resources.
Slab allocation was first introduced in the Solaris 2.4 kernel by Jeff Bonwick. It is now widely used by many Unix and Unix-like operating systems including FreeBSD and Linux.

Basis

The primary motivation for slab allocation is that the cost of initialization and destruction of kernel data objects can outweigh the cost of allocating memory for them. As the kernel creates and deletes objects often, overhead costs of initialization can result in significant performance drops. Object caching leads to less frequent invocation of functions that initialize object state: when a slab-allocated object is released after use, the slab allocation system typically keeps it cached ready for re-use next time an object of that type is needed.
With slab allocation, a cache for a certain type or size of data object has a number of pre-allocated "slabs" of memory; within each slab there are memory chunks of fixed size suitable for the objects. The slab allocator keeps track of these chunks, so that when it receives a request to allocate memory for a data object of a certain type, usually it can satisfy the request with a free slot from an existing slab. When the allocator is asked to free the object's memory, it just adds the slot to the containing slab's list of free slots. The next call to create an object of the same type will return that memory slot and remove it from the list of free slots. 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.

Implementation

Understanding the slab allocation algorithm requires defining and explaining some terms:
  1. Cache: cache represents a small amount of very fast memory. A cache is a storage for a specific type of object, such as semaphores, process s, file objects, etc.
  2. Slab: slab represents a contiguous piece of memory, usually made of several physically contiguous pages. The slab is the actual container of data associated with objects of the specific kind of the containing cache.
When a program sets up a cache, it allocates a number of objects to the slabs associated with that cache. This number depends on the size of the associated slabs.
Slabs may exist in one of the following states :
  1. empty – all objects on a slab marked as free
  2. partial – slab consists of both used and free objects
  3. full – all objects on a slab marked as used
Initially, the system marks each slab as "empty". When the process calls for a new kernel object, the system tries to find a free location for that object on a partial slab in a cache for that type of object. If no such location exists, the system allocates a new slab from contiguous physical pages and assigns it to a cache. The new object gets allocated from this slab, and its location becomes marked as "partial".
The allocation takes place quickly, because the system builds the objects in advance and readily allocates them from a slab.

Slabs

A slab is the amount by which a cache can grow or shrink. It represents one memory allocation to the cache from the machine, and whose size is customarily a multiple of the page size. A slab must contain a list of free buffers, as well as a list of the bufctls that have been allocated.

Large slabs

These are for caches that store objects that are at least 1/8 of the page size for a given machine. The reason for the large slabs having a different layout from the small slabs is that it allows large slabs to pack better into page-size units, which helps with fragmentation. The slab contains a list of bufctls, which are simply controllers for each buffer that can be allocated.

Small slabs

The small slabs contain objects that are less than 1/8 of the page size for a given machine. These small slabs need to be optimized further from the logical layout, by avoiding using bufctls. A small slab is exactly one page, and has a defined structure that allows bufctls to be avoided. The last part of the page contains the 'slab header', which is the information needed to retain the slab. Starting at the first address of that page, there are as many buffers as can be allocated without running into the slab header at the end of the page.
Instead of using bufctls, we use the buffers themselves to retain the free list links. This allows the small slab's bufctl to be bypassed.

Systems using slab allocation