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