23,40 → 23,99 |
<section> |
<title>Physical memory management</title> |
|
<section id="buddy_allocator"> |
<title>Buddy allocator</title> |
|
<section> |
<title>Overview</title> |
|
<para>In buddy allocator, memory is broken down into power-of-two |
sized naturally aligned blocks. These blocks are organized in an array |
of lists in which list with index i contains all unallocated blocks of |
the size <mathphrase>2<superscript>i</superscript></mathphrase>. The |
index i is called the order of block. Should there be two adjacent |
equally sized blocks in list <mathphrase>i</mathphrase> (i.e. |
buddies), the buddy allocator would coalesce them and put the |
resulting block in list <mathphrase>i + 1</mathphrase>, provided that |
the resulting block would be naturally aligned. Similarily, when the |
allocator is asked to allocate a block of size |
<mathphrase>2<superscript>i</superscript></mathphrase>, it first tries |
to satisfy the request from list with index i. If the request cannot |
be satisfied (i.e. the list i is empty), the buddy allocator will try |
to allocate and split larger block from list with index i + 1. Both of |
these algorithms are recursive. The recursion ends either when there |
are no blocks to coalesce in the former case or when there are no |
blocks that can be split in the latter case.</para> |
|
<graphic fileref="images/buddy_alloc.eps" format="EPS" /> |
|
<para>This approach greatly reduces external fragmentation of memory |
and helps in allocating bigger continuous blocks of memory aligned to |
their size. On the other hand, the buddy allocator suffers increased |
internal fragmentation of memory and is not suitable for general |
kernel allocations. This purpose is better addressed by the <link |
linkend="slab">slab allocator</link>.</para> |
</section> |
|
<section> |
<title>Implementation</title> |
|
<para>The buddy allocator is, in fact, an abstract framework wich can |
be easily specialized to serve one particular task. It knows nothing |
about the nature of memory it helps to allocate. In order to beat the |
lack of this knowledge, the buddy allocator exports an interface that |
each of its clients is required to implement. When supplied an |
implementation of this interface, the buddy allocator can use |
specialized external functions to find buddy for a block, split and |
coalesce blocks, manipulate block order and mark blocks busy or |
available. For precize documentation of this interface, refer to <link |
linkend="???">HelenOS Generic Kernel Reference Manual</link>.</para> |
|
<formalpara> |
<title>Data organization</title> |
|
<para>Each entity allocable by the buddy allocator is required to |
contain space for storing block order number and a link variable |
used to interconnect blocks within the same order.</para> |
|
<para>Whatever entities are allocated by the buddy allocator, the |
first entity within a block is used to represent the entire block. |
The first entity keeps the order of the whole block. Other entities |
within the block are assigned the magic value |
<constant>BUDDY_INNER_BLOCK</constant>. This is especially important |
for effective identification of buddies in one-dimensional array |
because the entity that represents a potential buddy cannot be associated |
with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it is associated |
with <constant>BUDDY_INNER_BLOCK</constant> then it is not a |
buddy).</para> |
</formalpara> |
</section> |
</section> |
|
<section id="zones_and_frames"> |
<title>Zones and frames</title> |
|
<para>Physical memory is divided into zones. Each zone represents |
continuous area of physical memory frames. Allocation of frames is |
handled by the <link linkend="buddy_allocator">buddy allocator</link> |
handled by the <link linkend="frame_allocator">frame allocator</link> |
associated with the zone. Zone also contains information about free and |
occupied frames and its base addresss in the memory. Some of the |
architectures (Mips, PPC) have only one zone, that covers whole physical |
memory. Other architectures (IA32) have multiple zones.</para> |
architectures (mips32, ppc32) have only one zone, that covers whole |
physical memory. Other architectures (ia32) have multiple zones.</para> |
</section> |
|
<section id="buddy_allocator"> |
<title>Buddy allocator</title> |
<section id="frame_allocator"> |
<title>Frame allocator</title> |
|
<section> |
<title>Overview</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 |
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> |
linkend="zones_and_frames">memory zone</link> is being handled by an |
instance of <link linkend="buddy_allocator">buddy allocator</link> |
tailored to allocate blocks of physical memory frames.</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> |
103,13 → 162,12 |
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> |
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> |