38,32 → 38,92 |
<section id="buddy_allocator"> |
<title>Buddy allocator</title> |
|
<para>Physical memory allocation inside one <link |
linkend="zones_and_frames">memory zone</link> is being handled by buddy |
allocation system. This approach greatly reduces possibility of memory |
fragmentation and helps in allocating bigger continious blocks of |
physical memory aligned to their size.</para> |
<section> |
<title>Overview</title> |
|
<graphic fileref="images/mm1.png" /> |
<para>Physical memory allocation inside one <link |
linkend="zones_and_frames">memory zone</link> is being handled by |
buddy allocation system. This approach greatly reduces possibility of |
outer memory fragmentation and helps in allocating bigger continious |
blocks of physical memory aligned to their size. Problem of inner |
memory fragmentation is being solved by <link linkend="slab">SLAB |
allocation system.</link></para> |
|
<para>Frames are grouped into bigger blocks and blocks of the size i ^ 2 |
are stored in the list indexed with <varname>i</varname> (so called |
order index). If list contains 2 ajacent blocks (of a same size of |
cause) they can be merged into the bigger one and moved into the list |
with higher order index, thus making possible allocation of a bigger |
block.</para> |
<graphic fileref="images/mm1.png" /> |
|
<para>Frames are grouped into bigger blocks and blocks of the size |
<mathphrase>2<superscript>i</superscript></mathphrase> are stored in |
the list indexed with <varname>i</varname> (so called order index). If |
list contains 2 ajacent blocks (of a same size of cause) they can be |
merged into the bigger one and moved into the list with higher order |
index, thus making possible allocation of a bigger block.</para> |
</section> |
|
<section> |
<title>Implementation</title> |
|
<formalpara> |
<title>Data organization</title> |
|
<para>Buddy allocator always uses first frame to represent frame |
block. This frame contains <varname>buddy_order</varname> variable |
to provide information about the block size it actually represents ( |
<mathphrase>2<superscript>buddy_order</superscript></mathphrase> |
frames block). Other frames in block have this value set to magic |
<constant>BUDDY_INNER_BLOCK</constant> that is much greater than |
buddy <varname>max_order</varname> value.</para> |
|
<para>Each <varname>frame_t</varname> also contains pointer member |
to hold frame structure in the linked list inside one order.</para> |
</formalpara> |
|
<formalpara> |
<title>Allocation algorithm</title> |
|
<para>Upon <mathphrase>2<superscript>i</superscript></mathphrase> |
frames block allocation request, allocator checks if there are any |
blocks available at the order list <varname>i</varname>. If yes, |
removes block from order list and returns its address. If no, |
recursively allocates |
<mathphrase>2<superscript>i+1</superscript></mathphrase> frame |
block, splits it into two |
<mathphrase>2<superscript>i</superscript></mathphrase> frame blocks. |
Then adds one of the blocks to the <varname>i</varname> order list |
and returns address of another.</para> |
</formalpara> |
|
<formalpara> |
<title>Deallocation algorithm</title> |
|
<para>Check if block has so called buddy (another free |
<mathphrase>2<superscript>i</superscript></mathphrase> frame block |
that can be linked with freed block into the |
<mathphrase>2<superscript>i+1</superscript></mathphrase> block). |
Technically, buddy is a odd/even block for even/odd block |
respectively. Plus we can put an extra requirement, that resulting |
block must be aligned to its size. This requirement guarantees |
natural block alignment for the blocks coming out the allocation |
system. |
</para> |
|
<para> |
Using direct pointer arithmetics, <varname>frame_t::ref_count</varname> and <varname>frame_t::buddy_order</varname> variables, |
finding buddy is done at constant time. |
</para> |
</formalpara> |
</section> |
</section> |
|
<section> |
<section id="slab"> |
<title>Slab allocator</title> |
|
<para>Kernel memory allocation is handled by slab.</para> |
</section> |
</section> |
|
<section> |
<title>Memory sharing</title> |
<section> |
<title>Memory sharing</title> |
|
<para>Not implemented yet(?)</para> |
<para>Not implemented yet(?)</para> |
</section> |
</section> |
</chapter> |