On computer memory
On memory fragmentation
Fragmentation in general
Slab allocation
The slab allocator does caches of fixed-size objects.
Slab allocation is often used in kernel modules/drivers that are perfectly fine to allocate only uniform-sized and potentially short-lived structures - think task structures, filesystem internals, network buffers.
Fixed size, and often separated for each specific type, makes it easier to write an allocator that guarantees allocation within very small timeframe (by avoiding "hey let me look at RAM and all the allocations currently in there" - you can keep track of slots being taken or not with a simple bitmask, and it cannot fragment).
There may also be arbitrary allocation not for specific data structures but for fixed sizes like 4K, 8K, 32K, 64K, 128K, etc, used for things that have known bounds but not precise sizes, for similar lower-time-overhead allocation at the cost of some wasted RAM.
Upsides:
- Each such cache is easy to handle
- avoids fragmentation because all holes are of the same size,
- that the otherwise-typical buddy system still has
- making slab allocation/free simpler, and thereby a little faster
- easier to fit them to hardware caches better
Limits:
- It still deals with the page allocator under the cover, so deallocation patterns can still mean that pages for the same cache become sparsely filled - which wastes space.
SLAB, SLOB, SLUB:
- SLOB: K&R allocator (1991-1999), aims to allocate as compactly as possible. But fragments faster than various others.
- SLAB: Solaris type allocator (1999-2008), as cache-friendly as possible.
- SLUB: Unqueued allocator (2008-today): Execution-time friendly, not always as cache friendly, does defragmentation (mostly just of pages with few objects)
For some indication of what's happening, look at slabtop and slabinfo
See also:
There are some similar higher-level allocators "I will handle things of the same type" allocation, from some custom allocators in C, to object allocators in certain languages, arguably even just the implementation of certain data structures.