270,23 → 270,24 |
</imageobject> |
</mediaobject></para> |
|
<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 |
<para>In the buddy allocator, the memory is broken down into |
power-of-two sized naturally aligned blocks. These blocks are |
organized in an array of lists, in which the list with index i |
contains all unallocated blocks of 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 the list i<mathphrase> </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> |
to satisfy the request from the 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 a larger block from the 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/mm1.png" format="EPS" /--> |
|
305,11 → 306,11 |
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 |
each of its clients is required to implement. When supplied with an |
implementation of this interface, the buddy allocator can use |
specialized external functions to find buddy for a block, split and |
specialized external functions to find a 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 |
available. For precise documentation of this interface, refer to |
<emphasis>"HelenOS Generic Kernel Reference Manual"</emphasis>.</para> |
|
<formalpara> |
324,15 → 325,16 |
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 |
for effective identification of buddies in a 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> |
|
<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 ( |
<para>The buddy allocator always uses the first frame to represent |
the 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 |