161,39 → 161,43 |
|
<para>The majority of memory allocation requests in the kernel is for |
small, frequently used data structures. The basic idea behind the slab |
allocator is that deployment of lists of preallocated, commonly used |
objects. Whenever an object is to be allocated, the slab allocator takes |
the first item from the list corresponding to the object type. This |
avoids the overhead of allocating and dellocating commonly used types of |
objects such as threads, B+tree nodes etc. Due to the fact that the |
sizes of the requested and allocated object match, the slab allocator |
significantly eliminates internal fragmentation. Moreover, each list can |
have a constructor and a destructor, which leads to performance gains |
because constructed and then destroyed objects don't need to be |
reinitialized<footnote> |
<para>Provided that the assumption that the destructor leaves the |
object in a consistent state holds.</para> |
</footnote>.</para> |
allocator is that commonly used objects are preallocated in continuous |
areas of physical memory called slabs<footnote> |
<para>Slabs are in fact blocks of physical memory frames allocated |
from the frame allocator.</para> |
</footnote>. Whenever an object is to be allocated, the slab allocator |
returns the first available item from a suitable slab corresponding to |
the object type<footnote> |
<para>The mechanism is rather more complicated, see the next |
paragraph.</para> |
</footnote>. Due to the fact that the sizes of the requested and |
allocated object match, the slab allocator significantly freduces |
internal fragmentation.</para> |
|
<para>In the slab allocator, objects of one type are kept in continuous |
areas of physical memory called slabs. Slabs can span from one to |
several physical memory frames. Slabs of objects of one type are stored |
in slab caches. When the allocator needs to allocate an object, it |
searches available slabs. When the slab does not contain any free |
obejct, a new slab is allocated and added to the cache. Contrary to |
allocation, deallocated objects are returned to their respective slabs. |
Empty slabs are deallocated immediately while empty slab caches are not |
freed until HelenOS runs short of memory.</para> |
<para>Slabs of one object type are organized in a structure called slab |
cache. There are ususally more slabs in the slab cache, depending on |
previous allocations. If the the slab cache runs out of available slabs, |
new slabs are allocated. In order to exploit parallelism and to avoid |
locking of shared spinlocks, slab caches can have variants of |
CPU-private slabs called magazines. Each object begins its life in a |
slab. When it is allocated from there, the slab allocator calls a |
constructor that is registered in the respective slab cache. The |
constructor initializes and brings the object into a known state. The |
object is then used by the user. When the user later frees the object, |
the slab allocator puts it into a CPU-private magazine, from where it |
can be precedently allocated again. Note that allocations satisfied from |
a magazine are already initialized by the constructor.</para> |
|
<para>Should HelenOS run short of memory, it would start deallocating |
objects from magazines, calling slab cache destructor on them and |
putting them back into slabs. When a slab contanins no allocated object, |
it is immediately freed.</para> |
|
<para><figure> |
<mediaobject id="slab_alloc"> |
<imageobject role="html"> |
<imagedata fileref="images/slab_alloc.png" format="PNG" /> |
</imageobject> |
|
<imageobject role="fop"> |
<imagedata fileref="images.vector/slab_alloc.svg" format="SVG" /> |
</imageobject> |
</mediaobject> |
|
<title>Slab allocator scheme.</title> |
200,16 → 204,6 |
</figure></para> |
|
<section> |
<para> |
<termdef /> |
|
|
|
<termdef /> |
</para> |
</section> |
|
<section> |
<title>Implementation</title> |
|
<para>The slab allocator is closely modelled after <ulink |
216,10 → 210,8 |
url="http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/"> |
OpenSolaris slab allocator by Jeff Bonwick and Jonathan Adams </ulink> |
with the following exceptions:<itemizedlist> |
<listitem></listitem> |
|
<listitem> |
empty magazines are deallocated when not needed |
empty magazines are deallocated when not needed |
</listitem> |
</itemizedlist> Following features are not currently supported but |
would be easy to do: <itemizedlist> |