patternMajor
Can someone explain this diagram about Slab Allocation?
Viewed 0 times
thiscansomeonediagramslababoutexplainallocation
Problem
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:
I'd really appreciate some help. THanks!
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!
Solution
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 al
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 al
Context
StackExchange Computer Science Q#45159, answer score: 23
Revisions (0)
No revisions yet.