Slab allocator

Situation:
Traditional memory allocators have always seen memory as a sequence of bytes available for use. From the layers point of view, memory allocators are below the 'Object' layer and so they have no idea on what kind of object is going to use the memory. In a way it is good, as the implementation of memory allocator becomes simpler. However, it also has a drawback. There are some object whose basic structure doesn't get changed in the course of the execution and so can be reused instead of them going through creation/destruction cycle repeatedly. Also, when the object's initialization becomes very costly, they should be reused as far as possible.

Object caching:
It makes sense for a memory allocator to understand the concept of objects so that memory can be allocated in a better way. So let us introduce a new layer above the usual memory allocator layer which is an object cache. Each type of object has its own cache. When the client requests a cache to allocate an object, the cache checks whether there are any free objects and if there are none, it asks the VM to allocate memory and creates an object and returns it. From the next time on, when the same object becomes free (i.e. when the client releases the object), object creation/initialization part is avoided and the same object is reused from the cache. If the memory manager asks the cache to free up some memory so that it can be reused by other systems, deallocate some objects and return some memory to it. On a cautious note, the object cache layer shouldn't waste memory and should return any unwanted memory to the underlying memory manager when memory manager asks for it.

Client and the central allocator:
Let us call the object caching pool the central allocator. We can split the system up into a client layer which should understand the object completely (including its name, size, how it should be constructed and destructed, its alignment etc) and requests the cache to create an object. The central allocator should take care of the underlying memory management and object caching thereby simplifying the interface for the clients.

Slab allocator:
The central allocator grows or shrinks by 1 slab size. A slab can be visualized as a contiguous memory split into equal-size chunks with a reference count on how many of those chunks are in use right now. To allocate/free a memory, just update the reference count, and return memory from the slab that has extra space. If the reference count goes to zero, the cache can shrink itself by the size of one slab. Slab allocator also reduces internal and external fragmentation issues as it already knows the size of the object it is always going to allocate.

Architecture:
A cache is always going to have similar objects only. It grows or shrinks by the size of a slab. So the cache maintains a circular doubly linked list to go to all slabs it manages right now (the node is called kmem_slab also has a reference count so that it can be deallocated later). Internally a slab is a contiguous memory whose size might span across pages. To know which objects are free to use right now, each slab maintains an additional free-list (the node is called kmem_bufctl which has the buffer address and a back pointer to the kmem_slab node). When the object size becomes very small, maintaining a free-list becomes an overhead as it occupies a lot of memory. So the kmem_slab and kmem_bufctl are all maintained at the end of the slab memory itself. Also kmem_bufctl wont be a linked list anymore but just bit vector showing whether an object in slab is in use or not.

Working of a Slab allocator:
The slabs are arranged in a particular order based on its usage; i.e. all free slabs are maintained at the end of the cache's DLL before which comes the partially used slab. The cache internally has a free-list pointer pointing to the first non-empty slab from which it can start allocating objects whenever a client places a request (remember, it also updates the reference count of the slab). The non-empty slab will then return the object from its buffer.
When an object is being returned by the client, if the reference count of the corresponding slab becomes zero, it is appended to the tail of the cache's free list. When the system runs low on memory, it will demand the slab allocator to release some memory. The slab allocator in turn releases some of its free slabs which have not been used recently. It doesn't release all free lists to avoid thrashing.

Usage:

Slab allocator are being used by many operating systems including Linux and Solaris, as it has been proven to work very efficiently. Memcached also uses this to avoid internal fragmentation.