Subversion Repositories HelenOS-doc

<?xml version="1.0" encoding="UTF-8"?>
<chapter id="mm">
  <?dbhtml filename="mm.html"?>

  <title>Memory management</title>

  <section>
    <title>Virtual memory management</title>

    <section>
      <title>Address spaces</title>

      <para></para>
    </section>

    <section>
      <title>Virtual address translation</title>

      <para></para>
    </section>
  </section>

  <section>
    <title>Physical memory management</title>

    <section id="zones_and_frames">
      <title>Zones and frames</title>

      <para>Physical memory is divided into zones. Each zone represents
      continuous area of physical memory frames. Allocation of frames is
      handled by the <link linkend="buddy_allocator">buddy allocator</link>
      associated with the zone. Zone also contains information about free and
      occupied frames and its base addresss in the memory. Some of the
      architectures (Mips, PPC) have only one zone, that covers whole physical
      memory. Other architectures (IA32) have multiple zones.</para>
    </section>

    <section id="buddy_allocator">
      <title>Buddy allocator</title>

      <section>
        <title>Overview</title>

        <para>Physical memory allocation inside one <link
        linkend="zones_and_frames">memory zone</link> is being handled by
        buddy allocation system. This approach greatly reduces possibility of
        outer memory fragmentation and helps in allocating bigger continious
        blocks of physical memory aligned to their size. Problem of inner
        memory fragmentation is being solved by <link linkend="slab">SLAB
        allocation system.</link></para>

        <graphic fileref="images/mm1.png" />

        <para>Frames are grouped into bigger blocks and blocks of the size
        <mathphrase>2<superscript>i</superscript></mathphrase> are stored in
        the list indexed with <varname>i</varname> (so called order index). If
        list contains 2 ajacent blocks (of a same size of cause) they can be
        merged into the bigger one and moved into the list with higher order
        index, thus making possible allocation of a bigger block.</para>
      </section>

      <section>
        <title>Implementation</title>

        <formalpara>
          <title>Data organization</title>

          <para>Buddy allocator always uses first frame to represent frame
          block. This frame contains <varname>buddy_order</varname> variable
          to provide information about the block size it actually represents (
          <mathphrase>2<superscript>buddy_order</superscript></mathphrase>
          frames block). Other frames in block have this value set to magic
          <constant>BUDDY_INNER_BLOCK</constant> that is much greater than
          buddy <varname>max_order</varname> value.</para>

          <para>Each <varname>frame_t</varname> also contains pointer member
          to hold frame structure in the linked list inside one order.</para>
        </formalpara>

        <formalpara>
          <title>Allocation algorithm</title>

          <para>Upon <mathphrase>2<superscript>i</superscript></mathphrase>
          frames block allocation request, allocator checks if there are any
          blocks available at the order list <varname>i</varname>. If yes,
          removes block from order list and returns its address. If no,
          recursively allocates
          <mathphrase>2<superscript>i+1</superscript></mathphrase> frame
          block, splits it into two
          <mathphrase>2<superscript>i</superscript></mathphrase> frame blocks.
          Then adds one of the blocks to the <varname>i</varname> order list
          and returns address of another.</para>
        </formalpara>

        <formalpara>
          <title>Deallocation algorithm</title>

          <para>Check if block has so called buddy (another free
          <mathphrase>2<superscript>i</superscript></mathphrase> frame block
          that can be linked with freed block into the
          <mathphrase>2<superscript>i+1</superscript></mathphrase> block).
          Technically, buddy is a odd/even block for even/odd block
          respectively. Plus we can put an extra requirement, that resulting
          block must be aligned to its size. This requirement guarantees
          natural block alignment for the blocks coming out the allocation
          system.
      </para>
      
      <para>
      Using direct pointer arithmetics, <varname>frame_t::ref_count</varname> and <varname>frame_t::buddy_order</varname> variables,
      finding buddy is done at constant time.
      </para>
        </formalpara>
      </section>
    </section>

    <section id="slab">
      <title>Slab allocator</title>

      <para>Kernel memory allocation is handled by slab.</para>
    </section>

    <section>
      <title>Memory sharing</title>

      <para>Not implemented yet(?)</para>
    </section>
  </section>
</chapter>