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