Subversion Repositories HelenOS-doc

Rev

Rev 15 | Rev 26 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
9 bondari 1
<?xml version="1.0" encoding="UTF-8"?>
11 bondari 2
<chapter id="mm">
3
  <?dbhtml filename="mm.html"?>
9 bondari 4
 
11 bondari 5
  <title>Memory management</title>
9 bondari 6
 
11 bondari 7
  <section>
8
    <title>Virtual memory management</title>
9 bondari 9
 
10
    <section>
11 bondari 11
      <title>Address spaces</title>
9 bondari 12
 
13
      <para></para>
14
    </section>
15
 
16
    <section>
11 bondari 17
      <title>Virtual address translation</title>
9 bondari 18
 
19
      <para></para>
20
    </section>
11 bondari 21
  </section>
9 bondari 22
 
11 bondari 23
  <section>
24
    <title>Physical memory management</title>
9 bondari 25
 
17 jermar 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
 
11 bondari 95
    <section id="zones_and_frames">
96
      <title>Zones and frames</title>
9 bondari 97
 
11 bondari 98
      <para>Physical memory is divided into zones. Each zone represents
99
      continuous area of physical memory frames. Allocation of frames is
17 jermar 100
      handled by the <link linkend="frame_allocator">frame allocator</link>
11 bondari 101
      associated with the zone. Zone also contains information about free and
102
      occupied frames and its base addresss in the memory. Some of the
17 jermar 103
      architectures (mips32, ppc32) have only one zone, that covers whole
104
      physical memory. Other architectures (ia32) have multiple zones.</para>
11 bondari 105
    </section>
9 bondari 106
 
17 jermar 107
    <section id="frame_allocator">
108
      <title>Frame allocator</title>
9 bondari 109
 
15 bondari 110
      <section>
111
        <title>Overview</title>
9 bondari 112
 
15 bondari 113
        <para>Physical memory allocation inside one <link
17 jermar 114
        linkend="zones_and_frames">memory zone</link> is being handled by an
115
        instance of <link linkend="buddy_allocator">buddy allocator</link>
116
        tailored to allocate blocks of physical memory frames.</para>
11 bondari 117
 
15 bondari 118
        <graphic fileref="images/mm1.png" />
119
      </section>
120
 
121
      <section>
122
        <title>Implementation</title>
123
 
124
        <formalpara>
125
          <title>Data organization</title>
126
 
127
          <para>Buddy allocator always uses first frame to represent frame
128
          block. This frame contains <varname>buddy_order</varname> variable
129
          to provide information about the block size it actually represents (
130
          <mathphrase>2<superscript>buddy_order</superscript></mathphrase>
131
          frames block). Other frames in block have this value set to magic
132
          <constant>BUDDY_INNER_BLOCK</constant> that is much greater than
133
          buddy <varname>max_order</varname> value.</para>
134
 
135
          <para>Each <varname>frame_t</varname> also contains pointer member
136
          to hold frame structure in the linked list inside one order.</para>
137
        </formalpara>
138
 
139
        <formalpara>
140
          <title>Allocation algorithm</title>
141
 
142
          <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase>
143
          frames block allocation request, allocator checks if there are any
144
          blocks available at the order list <varname>i</varname>. If yes,
145
          removes block from order list and returns its address. If no,
146
          recursively allocates
147
          <mathphrase>2<superscript>i+1</superscript></mathphrase> frame
148
          block, splits it into two
149
          <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks.
150
          Then adds one of the blocks to the <varname>i</varname> order list
151
          and returns address of another.</para>
152
        </formalpara>
153
 
154
        <formalpara>
155
          <title>Deallocation algorithm</title>
156
 
157
          <para>Check if block has so called buddy (another free
158
          <mathphrase>2<superscript>i</superscript></mathphrase> frame block
159
          that can be linked with freed block into the
160
          <mathphrase>2<superscript>i+1</superscript></mathphrase> block).
161
          Technically, buddy is a odd/even block for even/odd block
162
          respectively. Plus we can put an extra requirement, that resulting
163
          block must be aligned to its size. This requirement guarantees
164
          natural block alignment for the blocks coming out the allocation
17 jermar 165
          system.</para>
166
 
167
          <para>Using direct pointer arithmetics,
168
          <varname>frame_t::ref_count</varname> and
169
          <varname>frame_t::buddy_order</varname> variables, finding buddy is
170
          done at constant time.</para>
15 bondari 171
        </formalpara>
172
      </section>
9 bondari 173
    </section>
174
 
15 bondari 175
    <section id="slab">
11 bondari 176
      <title>Slab allocator</title>
9 bondari 177
 
11 bondari 178
      <para>Kernel memory allocation is handled by slab.</para>
9 bondari 179
    </section>
180
 
15 bondari 181
    <section>
182
      <title>Memory sharing</title>
9 bondari 183
 
15 bondari 184
      <para>Not implemented yet(?)</para>
185
    </section>
11 bondari 186
  </section>
187
</chapter>