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