Rev 11 | Rev 17 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 11 | Rev 15 | ||
|---|---|---|---|
| Line 36... | Line 36... | ||
| 36 | </section> |
36 | </section> |
| 37 | 37 | ||
| 38 | <section id="buddy_allocator"> |
38 | <section id="buddy_allocator"> |
| 39 | <title>Buddy allocator</title> |
39 | <title>Buddy allocator</title> |
| 40 | 40 | ||
| - | 41 | <section> |
|
| - | 42 | <title>Overview</title> |
|
| - | 43 | ||
| 41 | <para>Physical memory allocation inside one <link |
44 | <para>Physical memory allocation inside one <link |
| 42 | linkend="zones_and_frames">memory zone</link> is being handled by buddy |
45 | linkend="zones_and_frames">memory zone</link> is being handled by |
| 43 | allocation system. This approach greatly reduces possibility of memory |
46 | buddy allocation system. This approach greatly reduces possibility of |
| 44 | fragmentation and helps in allocating bigger continious blocks of |
47 | outer memory fragmentation and helps in allocating bigger continious |
| 45 | physical memory aligned to their size.</para> |
48 | blocks of physical memory aligned to their size. Problem of inner |
| - | 49 | memory fragmentation is being solved by <link linkend="slab">SLAB |
|
| - | 50 | allocation system.</link></para> |
|
| 46 | 51 | ||
| 47 | <graphic fileref="images/mm1.png" /> |
52 | <graphic fileref="images/mm1.png" /> |
| 48 | 53 | ||
| 49 | <para>Frames are grouped into bigger blocks and blocks of the size i ^ 2 |
54 | <para>Frames are grouped into bigger blocks and blocks of the size |
| - | 55 | <mathphrase>2<superscript>i</superscript></mathphrase> are stored in |
|
| 50 | are stored in the list indexed with <varname>i</varname> (so called |
56 | the list indexed with <varname>i</varname> (so called order index). If |
| 51 | order index). If list contains 2 ajacent blocks (of a same size of |
57 | list contains 2 ajacent blocks (of a same size of cause) they can be |
| 52 | cause) they can be merged into the bigger one and moved into the list |
58 | merged into the bigger one and moved into the list with higher order |
| 53 | with higher order index, thus making possible allocation of a bigger |
59 | index, thus making possible allocation of a bigger block.</para> |
| - | 60 | </section> |
|
| - | 61 | ||
| - | 62 | <section> |
|
| - | 63 | <title>Implementation</title> |
|
| - | 64 | ||
| - | 65 | <formalpara> |
|
| - | 66 | <title>Data organization</title> |
|
| - | 67 | ||
| - | 68 | <para>Buddy allocator always uses first frame to represent frame |
|
| - | 69 | block. This frame contains <varname>buddy_order</varname> variable |
|
| - | 70 | to provide information about the block size it actually represents ( |
|
| - | 71 | <mathphrase>2<superscript>buddy_order</superscript></mathphrase> |
|
| - | 72 | frames block). Other frames in block have this value set to magic |
|
| - | 73 | <constant>BUDDY_INNER_BLOCK</constant> that is much greater than |
|
| - | 74 | buddy <varname>max_order</varname> value.</para> |
|
| - | 75 | ||
| - | 76 | <para>Each <varname>frame_t</varname> also contains pointer member |
|
| - | 77 | to hold frame structure in the linked list inside one order.</para> |
|
| - | 78 | </formalpara> |
|
| - | 79 | ||
| 54 | block.</para> |
80 | <formalpara> |
| - | 81 | <title>Allocation algorithm</title> |
|
| - | 82 | ||
| - | 83 | <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase> |
|
| - | 84 | frames block allocation request, allocator checks if there are any |
|
| - | 85 | blocks available at the order list <varname>i</varname>. If yes, |
|
| - | 86 | removes block from order list and returns its address. If no, |
|
| - | 87 | recursively allocates |
|
| - | 88 | <mathphrase>2<superscript>i+1</superscript></mathphrase> frame |
|
| - | 89 | block, splits it into two |
|
| - | 90 | <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks. |
|
| - | 91 | Then adds one of the blocks to the <varname>i</varname> order list |
|
| - | 92 | and returns address of another.</para> |
|
| - | 93 | </formalpara> |
|
| - | 94 | ||
| - | 95 | <formalpara> |
|
| - | 96 | <title>Deallocation algorithm</title> |
|
| - | 97 | ||
| - | 98 | <para>Check if block has so called buddy (another free |
|
| - | 99 | <mathphrase>2<superscript>i</superscript></mathphrase> frame block |
|
| - | 100 | that can be linked with freed block into the |
|
| - | 101 | <mathphrase>2<superscript>i+1</superscript></mathphrase> block). |
|
| - | 102 | Technically, buddy is a odd/even block for even/odd block |
|
| - | 103 | respectively. Plus we can put an extra requirement, that resulting |
|
| - | 104 | block must be aligned to its size. This requirement guarantees |
|
| - | 105 | natural block alignment for the blocks coming out the allocation |
|
| - | 106 | system. |
|
| - | 107 | </para> |
|
| - | 108 | ||
| - | 109 | <para> |
|
| - | 110 | Using direct pointer arithmetics, <varname>frame_t::ref_count</varname> and <varname>frame_t::buddy_order</varname> variables, |
|
| - | 111 | finding buddy is done at constant time. |
|
| - | 112 | </para> |
|
| - | 113 | </formalpara> |
|
| - | 114 | </section> |
|
| 55 | </section> |
115 | </section> |
| 56 | 116 | ||
| 57 | <section> |
117 | <section id="slab"> |
| 58 | <title>Slab allocator</title> |
118 | <title>Slab allocator</title> |
| 59 | 119 | ||
| 60 | <para>Kernel memory allocation is handled by slab.</para> |
120 | <para>Kernel memory allocation is handled by slab.</para> |
| 61 | </section> |
121 | </section> |
| 62 | </section> |
- | |
| 63 | 122 | ||
| 64 | <section> |
123 | <section> |
| 65 | <title>Memory sharing</title> |
124 | <title>Memory sharing</title> |
| 66 | 125 | ||
| 67 | <para>Not implemented yet(?)</para> |
126 | <para>Not implemented yet(?)</para> |
| - | 127 | </section> |
|
| 68 | </section> |
128 | </section> |
| 69 | </chapter> |
129 | </chapter> |
| 70 | 130 | ||