Slab allocation

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Slab allocator. (Discuss)

In computer science, the slab allocation algorithm manages memory in such a way as to solve the problem of internal memory fragmentation. Internal memory fragmentation results from allocating a block of memory much larger than the requested memory (see Buddy memory allocation). Both the slab allocation algorithm and buddy memory allocation occur in kernel memory-allocation.

[edit] Implementation

Understanding the slab allocation algorithm requires defining and explaining some terms:

Cache: cache represents a small amount of very fast memory. Here we use cache as storage for objects such as semaphores, process descriptors, file objects etc. Every cache represents storage for only one type of object.
Slab: slab represents a contiguous piece of memory, usually made of several physically contiguous pages. A cache consists of one or more slabs.

When a program sets up a cache, it allocates a number of objects to that cache. This number depends on the size of the associated slabs.

Slabs may exist in one of the following states :

empty - all objects on a slab marked as free
partial - slab consists of both used and free objects
full - all objects on a slab marked as used

Initially, the system marks each object as "free". When the process calls for a new kernel object, the system tries to find a free location for that object in a corresponding cache on a partial slab. If no such location exists, the system allocates a new slab from contiguous physical pages and assigned it to a cache. The new object gets allocated from this slab, and its location becomes marked as "used".

The slab allocation algorithm has as its principal benefit that memory gets allocated in exactly the same size as requested, thus no internal memory fragmentation exists. The allocation takes place quickly, because the system builds the objects in advance and readily allocates them from a slab.