9
$\begingroup$

I'm trying to understand how Slab Allocation works and why it is different or better than ordinary paging.

I found this diagram which I believe would be helpful if it had more explanation.

Some questions:

  • What do the 3KB and 7KB items represent? Must they be related somehow? Why are they packaged that way?
  • In the caches column, are the caches the grey boxes, or the white/blue boxes inside the grey boxes? Are the grey boxes a package of caches?
  • Are the slabs just the blue boxes or is the whole "Physical Contiguous Pages" a slab?

I'd really appreciate some help. THanks!

Slab Allocation

$\endgroup$
14
$\begingroup$

I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect.

First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness.

Pages are the typical "unit" of memory operations. When a user-space application allocates memory, or memory-maps a file, or something like that, it typically gets a multiple of the machine page size. There are notable some exceptions; Windows uses 64k as the virtual memory allocation unit no matter what the page size of the CPU is. Nonetheless, let's think of it this way.

On a modern CPU, as far as user-space code is concerned, it has a flat address space. This is actually an illusion provided by the virtual memory system. The OS provides pages from anywhere in RAM (or possibly not in RAM at all, in the case of swapped memory or memory-mapped files) and maps them into a contiguous virtual address space.

The point of all this is that apart from a few special cases for the operating system itself (perhaps DMA buffers, maybe some special data structures set up at boot time, oh and the kernel image itself), the operating system kernel probably never has to manage any block of RAM bigger than a page. This simplifies things enormously, because it means that as far as pages go, every allocation and deallocation is the same size. It also effectively eliminates external fragmentation at the macro level.

However, kernels also need to implement some data structures of their own, and for that, they need a different kind of memory allocator. These data structures can usually be thought of as a collection of individual objects (e.g. an object may be a "thread" or a "mutex"). The size of these objects are typically far smaller than a page in size.

So, for example, an object which represents the security credentials of a process (think of the user id and group id in POSIX, say) might only be 16 bytes or so, whereas a "process" or "thread" might be up to 1kb in size. Clearly you don't want to use a whole page for these small records, so the idea is to implement an allocator on top of pages.

The lower-level allocation system has to satisfy many of the same issues as the page-level allocator: it has to be reasonably fast (including on multicore systems), you want to minimise fragmentation, and so on. But more importantly, it should be tunable and configurable depending on what kind of data structure you're storing.

Some data structures are inherently "cache-like". For example, many operating systems maintain a cache of path names to filesystem objects to avoid long chains of directory lookup (called the "name cache" or "namei cache" in Unix-speak). These objects are only needed for performance, not correctness, so you could (in theory) just forget a whole page full of entries if memory is tight and you need to free a page frame quickly.

Other data structures could be swapped to disk if memory is tight and you don't need them soon. But you don't want to do that with data structures which control swapping or the virtual memory system!

Some data structures can be moved around in memory with no penalty (e.g. if nobody refers to them with a pointer), so could "compact" themselves to avoid fragmentation if needed.

So the main idea of the slab allocator is that a page should only store data structures of the same "type". This ticks all the boxes: each object in a page is the same size, so there's no external fragmentation. Objects of the same "type" have the same performance requirements and the same semantics.

Incidentally, it's a similar story with allocation. For some types of object it's probably okay to wait if there's no memory immediately available to allocate that object. An object which represents an open file might be one example; opening a file is an expensive operation at the best of times, so waiting a little longer won't hurt that much.

For other types of object (e.g. an object which represents a real-time event that must happen a certain time from now), you really don't want to wait. So it makes sense for some types of object to over-allocate (say, have a few free pages in reserve) so that requests can be satisfied without waiting.

What you're basically doing is allowing each type of object to have its own allocator, which can be configured for the needs of that object. These per-object allocators are confusingly called "caches". You allocate one cache per type of object. (Yes, you'd typically implement a "cache of caches" as well.) Each cache only stores objects of the same type (e.g. only thread structures, or only address space structures).

Each cache, in turn, manages "slabs". A slab is a page frame which contains an array of objects of the same type. Slabs may be "full" (all objects in use), "empty" (no objects in use), or "partial" (some objects in use).

Partial slabs are probably the most interesting, since the slab allocator maintains a free list for every partial slab. (Full slabs and empty slabs need no free list.) Objects are allocated from partial slabs first (and probably from the "most full" partial slabs first) to try to avoid allocating pages that aren't needed.

The nice thing about slab allocation is that all of these allocation policy options (as well as the memory semantics) can be tuned for each kind of object. Some caches might retain a pool of empty slabs and some might not. Some might be able to be swapped to secondary storage and some might not.

Linux has has three different kinds of slab allocator, depending on whether or not you need compactness, cache-friendliness, or raw speed. There was a good presentation on this a couple of years ago which explains the tradeoffs well.

The Solaris slab allocator (see the paper for details) has a few more details to squeeze even more performance. For a start, in Solaris, everything is done with slab allocation, including page frame allocation. (This is Solaris' solution for allocating objects that are larger than half a page in size.) It manages smaller objects by nesting slab allocators in slab-allocated space.

Some objects in Solaris require complex and expensive construction and destruction (e.g. objects which have a kernel lock), and so they could be "partly free" (i.e. constructed but not allocated). Solaris also optimises free slab allocation by maintaining free lists on a per-CPU basis, ensuring that some operations are completely wait-free.

To support general-purpose allocation (e.g. for arrays whose size is not known at compile-time), most macrokernel-type operating systems also have caches which represent object sizes rather than object types. FreeBSD, for example, maintains caches for unknown objects whose sizes are powers of 2 bytes, from 4 to 256.

What I hope you can see is that slab allocation is a very flexible framework which can be tuned for the needs of different kinds of data. It doesn't compete with paging, but complements it (although in Solaris, page frames are allocated with slabs).

I hope this helps. Let me know if anything needs clarification.

$\endgroup$
6
$\begingroup$

The idea underneath the slab allocator is that the operating system needs specific but somewhat standard data structures (for example the process PCB, semaphores, file metadata etc) that suggest the memory usage that is necessary for them.

The slab allocator algorithm provides stocks of memory areas whose dimensions and initialization are optimized for these standard data structures. For example, as you can see from the picture, there can exist 3kb objects as well as of 7kb objects. However, we know that the kernel only allocates memory in multiples of the page size.

In order to avoid time and memory waste, the OS keeps in different caches pools of memory areas that can be rapidly allocated upon request, and the cache dimensions are different for every type of object and structure. However, the caches do not directly contain and manage these memory areas, and are not even guaranteed to reside in contiguous memory. They are instead divided in slabs, contiguous pages of memory, whose number is generally chosen to reduce memory fragmentation. It is in the slab that reside the different object instances, whether allocated or free. If a cache is full, new slab is allocated somewhere in the primary memory and it is added to the cache.

To sum up, the things you can see in the picture are examples of objects that the OS knows to be 3-7-whatever kB big. The kernel does not allocate a page memory specifically for them, since that would exponentially increase memory fragmentation, but "redirects" them to a cache (the grey box). In the cache there should be addresses that indicate physically contiguous areas of memory, the slabs (the white/blue sets of boxes) and the objects are finally allocated in an area of the slab (a part that is colored in blue, among free of full analogous memory areas of the same slab).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.