Slab allocation

Key takeaways

Slab allocation belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Slab allocation to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Slab allocation from memory before moving on to harder problems.

Reference excerpt

Slab allocation is a memory management mechanism intended for the efficient memory allocation of objects. In comparison with earlier mechanisms, it reduces fragmentation caused by allocations and deallocations. This technique is used for retaining allocated memory containing 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. Bonwick claims the name "Slab" comes from a Kellogg's cereal commercial catchphrase rhyme, "grab a slab". Slab allocation is now widely used by many Unix and Unix-like operating systems including FreeBSD and Linux, both in the SLAB allocator and its replacement, SLUB.

Basis Slab allocation significantly reduces the frequency of computationally costly initialization and destruction of kernel data-objects, which can outweigh the cost of allocating memory for them. When 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 which initialize object state: when a slab-allocated object is released after use, the slab allocation system typically keeps it cached (rather than doing the work of destroying it) ready for re-use next time an object of that type is needed (thus avoiding the work of constructing and initializing a new object). 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 (chunk) 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 (unused) slots. The next call to create an object of the same type (or allocate memory of the same size) will return that memory slot (or some other free 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 The slab allocation algorithm defines the following terms:

Cache: A cache is a small amount of very fast memory. Caches are storage for the specific type of object bound to this slab, such as semaphores, process descriptors, file objects, etc. This is not to be confused with the CPU cache. Slab: A slab is a contiguous piece of memory, usually made of several virtually 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:

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 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 virtual 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.

Implementation techniques

Free lists A slab represents one memory allocation to the cache from the machine, and whose size is customarily a multiple of the page size. The slab will be divided into a number of entries, which will then be requested by the cache as the client code requests memory for new objects. It is necessary then to keep track of which parts of the slab are free to use and which ones were already occupied. This is generally done using "free lists": lists of free entries in the slab ready to store new objects. The free list may be a separate data structure, such as an array of indices indicating which entries of the slab are free, or it may be embedded within the slab. The Linux SLUB allocator keeps the free list as a linked list of pointers, each of which is stored directly in the free memory area of the slab they represent.

Slab sizes Operating systems may use different slab sizes and internal layouts depending on the size of the objects to be stored. 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. For example, objects that are at least 1/8 of the page size for a given machine may benefit from a "large slab" size, with explicit free lists, while smaller objects may use a "small slab" setup, embed the free list tracking. Bonwick's original presentation of the slab allocator already made the distinction of layouts for large and small slabs.

Systems using slab allocation AmigaOS (introduced in AmigaOS 4) DragonFly BSD (introduced in release 1.0) FreeBSD (introduced in 5.0) GNU Mach Haiku (introduced in alpha 2) Horizon (Nintendo Switch microkernel) HP-UX (introduced in 11i) Linux (introduced in 2.1.23) NetBSD (introduced in 4.0) Solaris (introduced in 2.4) The Perl 5 compiler uses a slab allocator for internal memory management Memcached uses slab allocation for memory management illumos

See also Fixed-size blocks allocation Memory pool

Notes

External links FreeBSD uma(9) manual page The SLUB allocator comment about management of slabs in Linux by two different allocators: SLUB allocator and SLAB allocator Memory Compaction v7 (a Linux patch set from Mel Gorman dealing with SLAB fragmentation and compaction issues, 2 April 2010) Detecting kernel memory leaks Jonathan Corbet, Linux Weekly News, 2006; includes user comments on garbage collection Linux performance: is Linux becoming just too slow and bloated? On SLAB and SLUB. Free software magazine 2010.

Worked examples

Example 1 — a first encounter with Slab allocation

Start with the simplest possible case. Write down what Slab allocation claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Slab allocation before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Slab allocation ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Slab allocation

In research: Slab allocation appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Slab allocation in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Slab allocation is common in secondary-school and first-year university syllabi. It links to neighbouring topics Memory management algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Slab allocation outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Slab allocation in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Slab allocation means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Slab allocation out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Slab allocation in simple terms?

Slab allocation is a memory management mechanism intended for the efficient memory allocation of objects. In comparison with earlier mechanisms, it reduces fragmentation caused by allocations and deallocations.

Why does Slab allocation matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Slab allocation?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Slab allocation.