Slab Allocation - Implementation

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 descriptors, file objects etc.
2. Slab: slab represents a contiguous piece of memory, usually made of several physically contiguous pages. A cache consists of one or more slabs. The slab is the actual container of data associated to 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.