Subversion Repositories HelenOS-doc

Rev

Rev 17 | Rev 26 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 17 Rev 24
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 
 
- 
 
 8 
 
7 
  <section>
 9 
  <section><!-- VM -->
8 
    <title>Virtual memory management</title>
 10 
    <title>Virtual memory management</title>
9 
 
 11 
 
10 
    <section>
 12 
    <section>
11 
      <title>Address spaces</title>
 13 
      <title>Address spaces</title>
12 
 
 14 
 
13 
      <para></para>
 15 
      <para></para>
14 
    </section>
 16 
    </section>
15 
 
 17 
 
16 
    <section>
 18 
    <section>
17 
      <title>Virtual address translation</title>
 19 
      <title>Virtual address translation</title>
18 
 
 20 
 
19 
      <para></para>
 21 
      <para></para>
20 
    </section>
 22 
    </section>
21 
  </section>
 23 
  </section><!-- End of VM -->
22 
 
 24 
 
- 
 
 25 
 
23 
  <section>
 26 
  <section><!-- Phys mem -->
24 
    <title>Physical memory management</title>
 27 
    <title>Physical memory management</title>
25 
 
 28 
 
- 
 
 29 
 
- 
 
 30 
    <section id="zones_and_frames">
- 
 
 31 
      <title>Zones and frames</title>
- 
 
 32 
    <para>        <graphic fileref="images/mm2.png" /> </para>
- 
 
 33 
 
- 
 
 34 
 
- 
 
 35 
      <para>On some architectures not whole physical memory is available for conventional usage. This limitations
- 
 
 36 
      require from kernel to maintain a table of available and unavailable ranges of physical memory addresses.
- 
 
 37 
      Main idea of zones is in creating memory zone entity, that is a continuous chunk of memory available for allocation.
- 
 
 38 
      If some chunk is not available, we simply do not put it in any zone.
- 
 
 39 
      </para>
- 
 
 40 
     
- 
 
 41 
      <para>
- 
 
 42 
      Zone is also serves for informational purposes, containing information about number of free and busy frames. Physical memory
- 
 
 43 
      allocation is also done inside the certain zone. Allocation of zone frame must be organized by the
- 
 
 44 
      <link linkend="frame_allocator">frame allocator</link> associated with the zone.
- 
 
 45 
      </para>
- 
 
 46 
     
- 
 
 47 
      <para>Some of the architectures (mips32, ppc32) have only one zone, that covers whole
- 
 
 48 
      physical memory, and the others (like ia32) may have multiple zones.  Information about zones on current machine is stored
- 
 
 49 
      in BIOS hardware tables or can be hardcoded into kernel during compile time.</para>
- 
 
 50 
     
- 
 
 51 
    </section>
- 
 
 52 
 
- 
 
 53 
    <section id="frame_allocator">
- 
 
 54 
      <title>Frame allocator</title>
- 
 
 55 
 
- 
 
 56 
    <formalpara>
- 
 
 57 
    <title>Overview</title>
- 
 
 58 
        <para>Frame allocator provides physical memory allocation for the kernel. Because of zonal organization of physical memory,
- 
 
 59 
    frame allocator is always working in context of some zone, thus making impossible to allocate a piece of memory, which lays in different zone, which
- 
 
 60 
    cannot happen, because two adjacent zones can be merged into one. Frame allocator is also being responsible to update information on
- 
 
 61 
    the number of free/busy frames in zone.
- 
 
 62 
    Physical memory allocation inside one <link
- 
 
 63 
        linkend="zones_and_frames">memory zone</link> is being handled by an
- 
 
 64 
        instance of <link linkend="buddy_allocator">buddy allocator</link>
- 
 
 65 
        tailored to allocate blocks of physical memory frames.
- 
 
 66 
    </para>
- 
 
 67 
    </formalpara>
- 
 
 68 
   
- 
 
 69 
   
- 
 
 70 
   
- 
 
 71 
   
- 
 
 72 
    <formalpara>
- 
 
 73 
    <title>Allocation / deallocation</title>
- 
 
 74 
    <para>
- 
 
 75 
    Upon allocation request, frame allocator tries to find first zone, that can satisfy the incoming request (has required amount of free frames to allocate).
- 
 
 76 
    During deallocation, frame allocator needs to find zone, that contain deallocated frame.
- 
 
 77 
   
- 
 
 78 
    This approach could bring up two potential problems:
- 
 
 79 
    <itemizedlist>
- 
 
 80 
        <listitem>
- 
 
 81 
            Linear search of zones does not any good to performance, but number of zones is not expected to be high. And if yes, list of zones can be replaced with more time-efficient B-tree.
- 
 
 82 
        </listitem>
- 
 
 83 
        <listitem>
- 
 
 84 
            Quickly find out if zone contains required number of frames to allocate and if this chunk of memory is properly aligned. This issue is perfectly solved bu the buddy allocator.
- 
 
 85 
        </listitem>
- 
 
 86 
    </itemizedlist>
- 
 
 87 
   
- 
 
 88 
   
- 
 
 89 
    </para>
- 
 
 90 
    </formalpara>
- 
 
 91 
   
- 
 
 92 
      </section>
- 
 
 93 
 
- 
 
 94 
    </section>
- 
 
 95 
 
- 
 
 96 
 
- 
 
 97 
 
26 
    <section id="buddy_allocator">
 98 
    <section id="buddy_allocator">
27 
      <title>Buddy allocator</title>
 99 
      <title>Buddy allocator</title>
28 
 
 100 
 
29 
      <section>
 101 
      <section>
30 
        <title>Overview</title>
 102 
        <title>Overview</title>
31 
 
 103 
 
32 
        <para>In buddy allocator, memory is broken down into power-of-two
 104 
        <para>In buddy allocator, memory is broken down into power-of-two
33 
        sized naturally aligned blocks. These blocks are organized in an array
 105 
        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
 106 
        of lists in which list with index i contains all unallocated blocks of
35 
        the size <mathphrase>2<superscript>i</superscript></mathphrase>. The
 107 
        the size <mathphrase>2<superscript>i</superscript></mathphrase>. The
36 
        index i is called the order of block. Should there be two adjacent
 108 
        index i is called the order of block. Should there be two adjacent
37 
        equally sized blocks in list <mathphrase>i</mathphrase> (i.e.
 109 
        equally sized blocks in list <mathphrase>i</mathphrase> (i.e.
38 
        buddies), the buddy allocator would coalesce them and put the
 110 
        buddies), the buddy allocator would coalesce them and put the
39 
        resulting block in list <mathphrase>i + 1</mathphrase>, provided that
 111 
        resulting block in list <mathphrase>i + 1</mathphrase>, provided that
40 
        the resulting block would be naturally aligned. Similarily, when the
 112 
        the resulting block would be naturally aligned. Similarily, when the
41 
        allocator is asked to allocate a block of size
 113 
        allocator is asked to allocate a block of size
42 
        <mathphrase>2<superscript>i</superscript></mathphrase>, it first tries
 114 
        <mathphrase>2<superscript>i</superscript></mathphrase>, it first tries
43 
        to satisfy the request from list with index i. If the request cannot
 115 
        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
 116 
        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
 117 
        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
 118 
        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
 119 
        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>
 120 
        blocks that can be split in the latter case.</para>
49 
 
 121 
 
50 
        <graphic fileref="images/buddy_alloc.eps" format="EPS" />
 122 
        <graphic fileref="images/mm1.png" format="EPS" />
51 
 
 123 
 
52 
        <para>This approach greatly reduces external fragmentation of memory
 124 
        <para>This approach greatly reduces external fragmentation of memory
53 
        and helps in allocating bigger continuous blocks of memory aligned to
 125 
        and helps in allocating bigger continuous blocks of memory aligned to
54 
        their size. On the other hand, the buddy allocator suffers increased
 126 
        their size. On the other hand, the buddy allocator suffers increased
55 
        internal fragmentation of memory and is not suitable for general
 127 
        internal fragmentation of memory and is not suitable for general
56 
        kernel allocations. This purpose is better addressed by the <link
 128 
        kernel allocations. This purpose is better addressed by the <link
57 
        linkend="slab">slab allocator</link>.</para>
 129 
        linkend="slab">slab allocator</link>.</para>
58 
      </section>
 130 
      </section>
59 
 
 131 
 
60 
      <section>
 132 
      <section>
61 
        <title>Implementation</title>
 133 
        <title>Implementation</title>
62 
 
 134 
 
63 
        <para>The buddy allocator is, in fact, an abstract framework wich can
 135 
        <para>The buddy allocator is, in fact, an abstract framework wich can
64 
        be easily specialized to serve one particular task. It knows nothing
 136 
        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
 137 
        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
 138 
        lack of this knowledge, the buddy allocator exports an interface that
67 
        each of its clients is required to implement. When supplied an
 139 
        each of its clients is required to implement. When supplied an
68 
        implementation of this interface, the buddy allocator can use
 140 
        implementation of this interface, the buddy allocator can use
69 
        specialized external functions to find buddy for a block, split and
 141 
        specialized external functions to find buddy for a block, split and
70 
        coalesce blocks, manipulate block order and mark blocks busy or
 142 
        coalesce blocks, manipulate block order and mark blocks busy or
71 
        available. For precize documentation of this interface, refer to <link
 143 
        available. For precize documentation of this interface, refer to <link
72 
        linkend="???">HelenOS Generic Kernel Reference Manual</link>.</para>
 144 
        linkend="???">HelenOS Generic Kernel Reference Manual</link>.</para>
73 
 
 145 
 
74 
        <formalpara>
 146 
        <formalpara>
75 
          <title>Data organization</title>
 147 
          <title>Data organization</title>
76 
 
 148 
 
77 
          <para>Each entity allocable by the buddy allocator is required to
 149 
          <para>Each entity allocable by the buddy allocator is required to
78 
          contain space for storing block order number and a link variable
 150 
          contain space for storing block order number and a link variable
79 
          used to interconnect blocks within the same order.</para>
 151 
          used to interconnect blocks within the same order.</para>
80 
 
 152 
 
81 
          <para>Whatever entities are allocated by the buddy allocator, the
 153 
          <para>Whatever entities are allocated by the buddy allocator, the
82 
          first entity within a block is used to represent the entire block.
 154 
          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
 155 
          The first entity keeps the order of the whole block. Other entities
84 
          within the block are assigned the magic value
 156 
          within the block are assigned the magic value
85 
          <constant>BUDDY_INNER_BLOCK</constant>. This is especially important
 157 
          <constant>BUDDY_INNER_BLOCK</constant>. This is especially important
86 
          for effective identification of buddies in one-dimensional array
 158 
          for effective identification of buddies in one-dimensional array
87 
      because the entity that represents a potential buddy cannot be associated
 159 
          because the entity that represents a potential buddy cannot be
88 
      with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it is associated
 160 
          associated with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it
89 
          with <constant>BUDDY_INNER_BLOCK</constant> then it is not a
 161 
          is associated with <constant>BUDDY_INNER_BLOCK</constant> then it is
90 
          buddy).</para>
 162 
          not a buddy).</para>
91 
        </formalpara>
 163 
        </formalpara>
92 
      </section>
 - 
 
93 
    </section>
 - 
 
94 
 
 - 
 
95 
    <section id="zones_and_frames">
 - 
 
96 
      <title>Zones and frames</title>
 - 
 
97 
 
 - 
 
98 
      <para>Physical memory is divided into zones. Each zone represents
 - 
 
99 
      continuous area of physical memory frames. Allocation of frames is
 - 
 
100 
      handled by the <link linkend="frame_allocator">frame allocator</link>
 - 
 
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
 - 
 
103 
      architectures (mips32, ppc32) have only one zone, that covers whole
 - 
 
104 
      physical memory. Other architectures (ia32) have multiple zones.</para>
 - 
 
105 
    </section>
 - 
 
106 
 
 - 
 
107 
    <section id="frame_allocator">
 - 
 
108 
      <title>Frame allocator</title>
 - 
 
109 
 
 - 
 
110 
      <section>
 - 
 
111 
        <title>Overview</title>
 - 
 
112 
 
 - 
 
113 
        <para>Physical memory allocation inside one <link
 - 
 
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>
 - 
 
117 
 
 - 
 
118 
        <graphic fileref="images/mm1.png" />
 - 
 
119 
      </section>
 - 
 
120 
 
 - 
 
121 
      <section>
 - 
 
122 
        <title>Implementation</title>
 - 
 
123 
 
 164 
   
124 
        <formalpara>
 165 
        <formalpara>
125 
          <title>Data organization</title>
 166 
          <title>Data organization</title>
126 
 
 167 
 
127 
          <para>Buddy allocator always uses first frame to represent frame
 168 
          <para>Buddy allocator always uses first frame to represent frame
128 
          block. This frame contains <varname>buddy_order</varname> variable
 169 
          block. This frame contains <varname>buddy_order</varname> variable
129 
          to provide information about the block size it actually represents (
 170 
          to provide information about the block size it actually represents (
130 
          <mathphrase>2<superscript>buddy_order</superscript></mathphrase>
 171 
          <mathphrase>2<superscript>buddy_order</superscript></mathphrase>
131 
          frames block). Other frames in block have this value set to magic
 172 
          frames block). Other frames in block have this value set to magic
132 
          <constant>BUDDY_INNER_BLOCK</constant> that is much greater than
 173 
          <constant>BUDDY_INNER_BLOCK</constant> that is much greater than
133 
          buddy <varname>max_order</varname> value.</para>
 174 
          buddy <varname>max_order</varname> value.</para>
134 
 
 175 
 
135 
          <para>Each <varname>frame_t</varname> also contains pointer member
 176 
          <para>Each <varname>frame_t</varname> also contains pointer member
136 
          to hold frame structure in the linked list inside one order.</para>
 177 
          to hold frame structure in the linked list inside one order.</para>
137 
        </formalpara>
 178 
        </formalpara>
138 
 
 179 
 
139 
        <formalpara>
 180 
        <formalpara>
140 
          <title>Allocation algorithm</title>
 181 
          <title>Allocation algorithm</title>
141 
 
 182 
 
142 
          <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase>
 183 
          <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase>
143 
          frames block allocation request, allocator checks if there are any
 184 
          frames block allocation request, allocator checks if there are any
144 
          blocks available at the order list <varname>i</varname>. If yes,
 185 
          blocks available at the order list <varname>i</varname>. If yes,
145 
          removes block from order list and returns its address. If no,
 186 
          removes block from order list and returns its address. If no,
146 
          recursively allocates
 187 
          recursively allocates
147 
          <mathphrase>2<superscript>i+1</superscript></mathphrase> frame
 188 
          <mathphrase>2<superscript>i+1</superscript></mathphrase> frame
148 
          block, splits it into two
 189 
          block, splits it into two
149 
          <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks.
 190 
          <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks.
150 
          Then adds one of the blocks to the <varname>i</varname> order list
 191 
          Then adds one of the blocks to the <varname>i</varname> order list
151 
          and returns address of another.</para>
 192 
          and returns address of another.</para>
152 
        </formalpara>
 193 
        </formalpara>
153 
 
 194 
 
154 
        <formalpara>
 195 
        <formalpara>
155 
          <title>Deallocation algorithm</title>
 196 
          <title>Deallocation algorithm</title>
156 
 
 197 
 
157 
          <para>Check if block has so called buddy (another free
 198 
          <para>Check if block has so called buddy (another free
158 
          <mathphrase>2<superscript>i</superscript></mathphrase> frame block
 199 
          <mathphrase>2<superscript>i</superscript></mathphrase> frame block
159 
          that can be linked with freed block into the
 200 
          that can be linked with freed block into the
160 
          <mathphrase>2<superscript>i+1</superscript></mathphrase> block).
 201 
          <mathphrase>2<superscript>i+1</superscript></mathphrase> block).
161 
          Technically, buddy is a odd/even block for even/odd block
 202 
          Technically, buddy is a odd/even block for even/odd block
162 
          respectively. Plus we can put an extra requirement, that resulting
 203 
          respectively. Plus we can put an extra requirement, that resulting
163 
          block must be aligned to its size. This requirement guarantees
 204 
          block must be aligned to its size. This requirement guarantees
164 
          natural block alignment for the blocks coming out the allocation
 205 
          natural block alignment for the blocks coming out the allocation
165 
          system.</para>
 206 
          system.</para>
166 
 
 207 
 
167 
          <para>Using direct pointer arithmetics,
 208 
          <para>Using direct pointer arithmetics,
168 
          <varname>frame_t::ref_count</varname> and
 209 
          <varname>frame_t::ref_count</varname> and
169 
          <varname>frame_t::buddy_order</varname> variables, finding buddy is
 210 
          <varname>frame_t::buddy_order</varname> variables, finding buddy is
170 
          done at constant time.</para>
 211 
          done at constant time.</para>
171 
        </formalpara>
 212 
        </formalpara>
172 
      </section>
 213 
   
173 
    </section>
 214 
      </section>
174 
 
 215 
 
- 
 
 216 
 
175 
    <section id="slab">
 217 
    <section id="slab">
176 
      <title>Slab allocator</title>
 218 
      <title>Slab allocator</title>
177 
 
 219 
 
178 
      <para>Kernel memory allocation is handled by slab.</para>
 220 
      <para>Kernel memory allocation is handled by slab.</para>
- 
 
 221 
    </section><!-- End of Physmem -->
- 
 
 222 
 
179 
    </section>
 223 
  </section>
180 
 
 224 
 
- 
 
 225 
 
181 
    <section>
 226 
    <section>
182 
      <title>Memory sharing</title>
 227 
      <title>Memory sharing</title>
183 
 
 228 
 
184 
      <para>Not implemented yet(?)</para>
 229 
      <para>Not implemented yet(?)</para>
185 
    </section>
 230 
    </section>
186 
  </section>
 - 
 
187 
</chapter>
 231 
</chapter>
188 

            232