Rev 11 | Rev 17 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 11 | Rev 15 | ||
---|---|---|---|
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="zones_and_frames"> |
26 | <section id="zones_and_frames"> |
27 | <title>Zones and frames</title> |
27 | <title>Zones and frames</title> |
28 | 28 | ||
29 | <para>Physical memory is divided into zones. Each zone represents |
29 | <para>Physical memory is divided into zones. Each zone represents |
30 | continuous area of physical memory frames. Allocation of frames is |
30 | continuous area of physical memory frames. Allocation of frames is |
31 | handled by the <link linkend="buddy_allocator">buddy allocator</link> |
31 | handled by the <link linkend="buddy_allocator">buddy allocator</link> |
32 | associated with the zone. Zone also contains information about free and |
32 | associated with the zone. Zone also contains information about free and |
33 | occupied frames and its base addresss in the memory. Some of the |
33 | occupied frames and its base addresss in the memory. Some of the |
34 | architectures (Mips, PPC) have only one zone, that covers whole physical |
34 | architectures (Mips, PPC) have only one zone, that covers whole physical |
35 | memory. Other architectures (IA32) have multiple zones.</para> |
35 | memory. Other architectures (IA32) have multiple zones.</para> |
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> |