Subversion Repositories HelenOS-doc

Rev

Rev 17 | Rev 26 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 17 Rev 24
Line 2... Line 2...
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 
 
Line 16... Line 18...
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 -->
- 
 
 24 
 
22 
 
 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>
Line 45... Line 117...
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
Line 82... Line 154...
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 
 
 164 
   
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 
 
 - 
 
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
Line 167... Line 208...
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>
- 
 
 213 
   
172 
      </section>
 214 
      </section>
173 
    </section>
 215 
 
174 
 
 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>
- 
 
 224 
 
180 
 
 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