Subversion Repositories HelenOS-doc

Rev

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>