Rev 15 | Rev 24 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 15 | Rev 17 | ||
---|---|---|---|
1 | <?xml version="1.0" encoding="UTF-8"?> |
1 | <?xml version="1.0" encoding="UTF-8"?> |
2 | <chapter id="mm"> |
2 | <chapter id="mm"> |
3 | <?dbhtml filename="mm.html"?> |
3 | <?dbhtml filename="mm.html"?> |
4 | 4 | ||
5 | <title>Memory management</title> |
5 | <title>Memory management</title> |
6 | 6 | ||
7 | <section> |
7 | <section> |
8 | <title>Virtual memory management</title> |
8 | <title>Virtual memory management</title> |
9 | 9 | ||
10 | <section> |
10 | <section> |
11 | <title>Address spaces</title> |
11 | <title>Address spaces</title> |
12 | 12 | ||
13 | <para></para> |
13 | <para></para> |
14 | </section> |
14 | </section> |
15 | 15 | ||
16 | <section> |
16 | <section> |
17 | <title>Virtual address translation</title> |
17 | <title>Virtual address translation</title> |
18 | 18 | ||
19 | <para></para> |
19 | <para></para> |
20 | </section> |
20 | </section> |
21 | </section> |
21 | </section> |
22 | 22 | ||
23 | <section> |
23 | <section> |
24 | <title>Physical memory management</title> |
24 | <title>Physical memory management</title> |
25 | 25 | ||
- | 26 | <section id="buddy_allocator"> |
|
- | 27 | <title>Buddy allocator</title> |
|
- | 28 | ||
- | 29 | <section> |
|
- | 30 | <title>Overview</title> |
|
- | 31 | ||
- | 32 | <para>In buddy allocator, memory is broken down into power-of-two |
|
- | 33 | sized naturally aligned blocks. These blocks are organized in an array |
|
- | 34 | of lists in which list with index i contains all unallocated blocks of |
|
- | 35 | the size <mathphrase>2<superscript>i</superscript></mathphrase>. The |
|
- | 36 | index i is called the order of block. Should there be two adjacent |
|
- | 37 | equally sized blocks in list <mathphrase>i</mathphrase> (i.e. |
|
- | 38 | buddies), the buddy allocator would coalesce them and put the |
|
- | 39 | resulting block in list <mathphrase>i + 1</mathphrase>, provided that |
|
- | 40 | the resulting block would be naturally aligned. Similarily, when the |
|
- | 41 | allocator is asked to allocate a block of size |
|
- | 42 | <mathphrase>2<superscript>i</superscript></mathphrase>, it first tries |
|
- | 43 | to satisfy the request from list with index i. If the request cannot |
|
- | 44 | be satisfied (i.e. the list i is empty), the buddy allocator will try |
|
- | 45 | to allocate and split larger block from list with index i + 1. Both of |
|
- | 46 | these algorithms are recursive. The recursion ends either when there |
|
- | 47 | are no blocks to coalesce in the former case or when there are no |
|
- | 48 | blocks that can be split in the latter case.</para> |
|
- | 49 | ||
- | 50 | <graphic fileref="images/buddy_alloc.eps" format="EPS" /> |
|
- | 51 | ||
- | 52 | <para>This approach greatly reduces external fragmentation of memory |
|
- | 53 | and helps in allocating bigger continuous blocks of memory aligned to |
|
- | 54 | their size. On the other hand, the buddy allocator suffers increased |
|
- | 55 | internal fragmentation of memory and is not suitable for general |
|
- | 56 | kernel allocations. This purpose is better addressed by the <link |
|
- | 57 | linkend="slab">slab allocator</link>.</para> |
|
- | 58 | </section> |
|
- | 59 | ||
- | 60 | <section> |
|
- | 61 | <title>Implementation</title> |
|
- | 62 | ||
- | 63 | <para>The buddy allocator is, in fact, an abstract framework wich can |
|
- | 64 | be easily specialized to serve one particular task. It knows nothing |
|
- | 65 | about the nature of memory it helps to allocate. In order to beat the |
|
- | 66 | lack of this knowledge, the buddy allocator exports an interface that |
|
- | 67 | each of its clients is required to implement. When supplied an |
|
- | 68 | implementation of this interface, the buddy allocator can use |
|
- | 69 | specialized external functions to find buddy for a block, split and |
|
- | 70 | coalesce blocks, manipulate block order and mark blocks busy or |
|
- | 71 | available. For precize documentation of this interface, refer to <link |
|
- | 72 | linkend="???">HelenOS Generic Kernel Reference Manual</link>.</para> |
|
- | 73 | ||
- | 74 | <formalpara> |
|
- | 75 | <title>Data organization</title> |
|
- | 76 | ||
- | 77 | <para>Each entity allocable by the buddy allocator is required to |
|
- | 78 | contain space for storing block order number and a link variable |
|
- | 79 | used to interconnect blocks within the same order.</para> |
|
- | 80 | ||
- | 81 | <para>Whatever entities are allocated by the buddy allocator, the |
|
- | 82 | first entity within a block is used to represent the entire block. |
|
- | 83 | The first entity keeps the order of the whole block. Other entities |
|
- | 84 | within the block are assigned the magic value |
|
- | 85 | <constant>BUDDY_INNER_BLOCK</constant>. This is especially important |
|
- | 86 | for effective identification of buddies in one-dimensional array |
|
- | 87 | because the entity that represents a potential buddy cannot be associated |
|
- | 88 | with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it is associated |
|
- | 89 | with <constant>BUDDY_INNER_BLOCK</constant> then it is not a |
|
- | 90 | buddy).</para> |
|
- | 91 | </formalpara> |
|
- | 92 | </section> |
|
- | 93 | </section> |
|
- | 94 | ||
26 | <section id="zones_and_frames"> |
95 | <section id="zones_and_frames"> |
27 | <title>Zones and frames</title> |
96 | <title>Zones and frames</title> |
28 | 97 | ||
29 | <para>Physical memory is divided into zones. Each zone represents |
98 | <para>Physical memory is divided into zones. Each zone represents |
30 | continuous area of physical memory frames. Allocation of frames is |
99 | continuous area of physical memory frames. Allocation of frames is |
31 | handled by the <link linkend="buddy_allocator">buddy allocator</link> |
100 | handled by the <link linkend="frame_allocator">frame allocator</link> |
32 | associated with the zone. Zone also contains information about free and |
101 | associated with the zone. Zone also contains information about free and |
33 | occupied frames and its base addresss in the memory. Some of the |
102 | occupied frames and its base addresss in the memory. Some of the |
34 | architectures (Mips, PPC) have only one zone, that covers whole physical |
103 | architectures (mips32, ppc32) have only one zone, that covers whole |
35 | memory. Other architectures (IA32) have multiple zones.</para> |
104 | physical memory. Other architectures (ia32) have multiple zones.</para> |
36 | </section> |
105 | </section> |
37 | 106 | ||
38 | <section id="buddy_allocator"> |
107 | <section id="frame_allocator"> |
39 | <title>Buddy allocator</title> |
108 | <title>Frame allocator</title> |
40 | 109 | ||
41 | <section> |
110 | <section> |
42 | <title>Overview</title> |
111 | <title>Overview</title> |
43 | 112 | ||
44 | <para>Physical memory allocation inside one <link |
113 | <para>Physical memory allocation inside one <link |
45 | linkend="zones_and_frames">memory zone</link> is being handled by |
114 | linkend="zones_and_frames">memory zone</link> is being handled by an |
46 | buddy allocation system. This approach greatly reduces possibility of |
- | |
47 | outer memory fragmentation and helps in allocating bigger continious |
115 | instance of <link linkend="buddy_allocator">buddy allocator</link> |
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> |
116 | tailored to allocate blocks of physical memory frames.</para> |
51 | 117 | ||
52 | <graphic fileref="images/mm1.png" /> |
118 | <graphic fileref="images/mm1.png" /> |
53 | - | ||
54 | <para>Frames are grouped into bigger blocks and blocks of the size |
- | |
55 | <mathphrase>2<superscript>i</superscript></mathphrase> are stored in |
- | |
56 | the list indexed with <varname>i</varname> (so called order index). If |
- | |
57 | list contains 2 ajacent blocks (of a same size of cause) they can be |
- | |
58 | merged into the bigger one and moved into the list with higher order |
- | |
59 | index, thus making possible allocation of a bigger block.</para> |
- | |
60 | </section> |
119 | </section> |
61 | 120 | ||
62 | <section> |
121 | <section> |
63 | <title>Implementation</title> |
122 | <title>Implementation</title> |
64 | 123 | ||
65 | <formalpara> |
124 | <formalpara> |
66 | <title>Data organization</title> |
125 | <title>Data organization</title> |
67 | 126 | ||
68 | <para>Buddy allocator always uses first frame to represent frame |
127 | <para>Buddy allocator always uses first frame to represent frame |
69 | block. This frame contains <varname>buddy_order</varname> variable |
128 | block. This frame contains <varname>buddy_order</varname> variable |
70 | to provide information about the block size it actually represents ( |
129 | to provide information about the block size it actually represents ( |
71 | <mathphrase>2<superscript>buddy_order</superscript></mathphrase> |
130 | <mathphrase>2<superscript>buddy_order</superscript></mathphrase> |
72 | frames block). Other frames in block have this value set to magic |
131 | frames block). Other frames in block have this value set to magic |
73 | <constant>BUDDY_INNER_BLOCK</constant> that is much greater than |
132 | <constant>BUDDY_INNER_BLOCK</constant> that is much greater than |
74 | buddy <varname>max_order</varname> value.</para> |
133 | buddy <varname>max_order</varname> value.</para> |
75 | 134 | ||
76 | <para>Each <varname>frame_t</varname> also contains pointer member |
135 | <para>Each <varname>frame_t</varname> also contains pointer member |
77 | to hold frame structure in the linked list inside one order.</para> |
136 | to hold frame structure in the linked list inside one order.</para> |
78 | </formalpara> |
137 | </formalpara> |
79 | 138 | ||
80 | <formalpara> |
139 | <formalpara> |
81 | <title>Allocation algorithm</title> |
140 | <title>Allocation algorithm</title> |
82 | 141 | ||
83 | <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase> |
142 | <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase> |
84 | frames block allocation request, allocator checks if there are any |
143 | frames block allocation request, allocator checks if there are any |
85 | blocks available at the order list <varname>i</varname>. If yes, |
144 | blocks available at the order list <varname>i</varname>. If yes, |
86 | removes block from order list and returns its address. If no, |
145 | removes block from order list and returns its address. If no, |
87 | recursively allocates |
146 | recursively allocates |
88 | <mathphrase>2<superscript>i+1</superscript></mathphrase> frame |
147 | <mathphrase>2<superscript>i+1</superscript></mathphrase> frame |
89 | block, splits it into two |
148 | block, splits it into two |
90 | <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks. |
149 | <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks. |
91 | Then adds one of the blocks to the <varname>i</varname> order list |
150 | Then adds one of the blocks to the <varname>i</varname> order list |
92 | and returns address of another.</para> |
151 | and returns address of another.</para> |
93 | </formalpara> |
152 | </formalpara> |
94 | 153 | ||
95 | <formalpara> |
154 | <formalpara> |
96 | <title>Deallocation algorithm</title> |
155 | <title>Deallocation algorithm</title> |
97 | 156 | ||
98 | <para>Check if block has so called buddy (another free |
157 | <para>Check if block has so called buddy (another free |
99 | <mathphrase>2<superscript>i</superscript></mathphrase> frame block |
158 | <mathphrase>2<superscript>i</superscript></mathphrase> frame block |
100 | that can be linked with freed block into the |
159 | that can be linked with freed block into the |
101 | <mathphrase>2<superscript>i+1</superscript></mathphrase> block). |
160 | <mathphrase>2<superscript>i+1</superscript></mathphrase> block). |
102 | Technically, buddy is a odd/even block for even/odd block |
161 | Technically, buddy is a odd/even block for even/odd block |
103 | respectively. Plus we can put an extra requirement, that resulting |
162 | respectively. Plus we can put an extra requirement, that resulting |
104 | block must be aligned to its size. This requirement guarantees |
163 | block must be aligned to its size. This requirement guarantees |
105 | natural block alignment for the blocks coming out the allocation |
164 | natural block alignment for the blocks coming out the allocation |
106 | system. |
165 | system.</para> |
107 | </para> |
- | |
108 | 166 | ||
109 | <para> |
167 | <para>Using direct pointer arithmetics, |
- | 168 | <varname>frame_t::ref_count</varname> and |
|
110 | Using direct pointer arithmetics, <varname>frame_t::ref_count</varname> and <varname>frame_t::buddy_order</varname> variables, |
169 | <varname>frame_t::buddy_order</varname> variables, finding buddy is |
111 | finding buddy is done at constant time. |
170 | done at constant time.</para> |
112 | </para> |
- | |
113 | </formalpara> |
171 | </formalpara> |
114 | </section> |
172 | </section> |
115 | </section> |
173 | </section> |
116 | 174 | ||
117 | <section id="slab"> |
175 | <section id="slab"> |
118 | <title>Slab allocator</title> |
176 | <title>Slab allocator</title> |
119 | 177 | ||
120 | <para>Kernel memory allocation is handled by slab.</para> |
178 | <para>Kernel memory allocation is handled by slab.</para> |
121 | </section> |
179 | </section> |
122 | 180 | ||
123 | <section> |
181 | <section> |
124 | <title>Memory sharing</title> |
182 | <title>Memory sharing</title> |
125 | 183 | ||
126 | <para>Not implemented yet(?)</para> |
184 | <para>Not implemented yet(?)</para> |
127 | </section> |
185 | </section> |
128 | </section> |
186 | </section> |
129 | </chapter> |
187 | </chapter> |