Subversion Repositories HelenOS-doc

      all unallocated blocks of size

      empty), the buddy allocator will try to allocate and split a larger

            <listitem>

            </listitem>

    <para>Virtual memory is essential for an operating system because it makes

    several things possible. First, it helps to isolate tasks from each other

    by encapsulating them in their private address spaces. Second, virtual

    memory can give tasks the feeling of more memory available than is

    actually possible. And third, by using virtual memory, there might be

    multiple copies of the same program, linked to the same addresses, running

    in the system. There are at least two known mechanisms for implementing

    virtual memory: segmentation and paging. Even though some processor

    architectures supported by HelenOS<footnote>

        <para>ia32 has full-fledged segmentation.</para>

      </footnote> provide both mechanism, the kernel makes use solely of

    paging.</para>

    <section id="paging">

      <title>VAT subsystem</title>

      <para>In a paged virtual memory, the entire virtual address space is

      divided into small power-of-two sized naturally aligned blocks called

      pages. The processor implements a translation mechanism, that allows the

      operating system to manage mappings between set of pages and set of

      indentically sized and identically aligned pieces of physical memory

      called frames. In a result, references to continuous virtual memory

      areas don't necessarily need to reference continuos area of physical

      memory. Supported page sizes usually range from several kilobytes to

      several megabytes. Each page that takes part in the mapping is

      associated with certain attributes that further desribe the mapping

      (e.g. access rights, dirty and accessed bits and present bit).</para>

      <para>When the processor accesses a page that is not present (i.e. its

      present bit is not set), the operating system is notified through a

      special exception called page fault. It is then up to the operating

      system to service the page fault. In HelenOS, some page faults are fatal

      and result in either task termination or, in the worse case, kernel

      panic<footnote>

          <para>Such a condition would be either caused by a hardware failure

          or a bug in the kernel.</para>

        </footnote>, while other page faults are used to load memory on demand

      or to notify the kernel about certain events.</para>

      <indexterm>

        <primary>page tables</primary>

      </indexterm>

      <para>The set of all page mappings is stored in a memory structure

      called page tables. Some architectures have no hardware support for page

      tables<footnote>

          <para>On mips32, TLB-only model is used and the operating system is

          responsible for managing software defined page tables.</para>

        </footnote> while other processor architectures<footnote>

          <para>Like amd64 and ia32.</para>

        </footnote> understand the whole memory format thereof. Despite all

      the possible differences in page table formats, the HelenOS VAT

      subsystem<footnote>

          <para>Virtual Address Translation subsystem.</para>

        </footnote> unifies the page table operations under one programming

      interface. For all parts of the kernel, three basic functions are

      provided:</para>

      <itemizedlist>

        <listitem>

          <para><code>page_mapping_insert()</code>,</para>

        </listitem>

        <listitem>

          <para><code>page_mapping_find()</code> and</para>

        </listitem>

        <listitem>

          <para><code>page_mapping_remove()</code>.</para>

        </listitem>

      </itemizedlist>

      <para>The <code>page_mapping_insert()</code> function is used to

      introduce a mapping for one virtual memory page belonging to a

      particular address space into the page tables. Once the mapping is in

      the page tables, it can be searched by <code>page_mapping_find()</code>

      and removed by <code>page_mapping_remove()</code>. All of these

      functions internally select the page table mechanism specific functions

      that carry out the self operation.</para>

      <para>There are currently two supported mechanisms: generic 4-level

      hierarchical page tables and global page hash table. Both of the

      mechanisms are generic as they cover several hardware platforms. For

      instance, the 4-level hierarchical page table mechanism is used by

      amd64, ia32, mips32 and ppc32, respectively. These architectures have

      the following page table format: 4-level, 2-level, TLB-only and hardware

      hash table, respectively. On the other hand, the global page hash table

      is used on ia64 that can be TLB-only or use a hardware hash table.

      Although only two mechanisms are currently implemented, other mechanisms

      (e.g. B+tree) can be easily added.</para>

      <section id="page_tables">

        <indexterm>

          <primary>page tables</primary>

          <secondary>- hierarchical</secondary>

        </indexterm>

        <title>Hierarchical 4-level page tables</title>

        <para>Hierarchical 4-level page tables are generalization of the

        frequently used hierarchical model of page tables. In this mechanism,

        each address space has its own page tables. To avoid confusion in

        terminology used by hardware vendors, in HelenOS, the root level page

        table is called PTL0, the two middle levels are called PTL1 and PTL2,

        and, finally, the leaf level is called PTL3. All architectures using

        this mechanism are required to use PTL0 and PTL3. However, the middle

        levels can be left out, depending on the hardware hierachy or

        structure of software-only page tables. The genericity is achieved

        through a set of macros that define transitions from one level to

        another. Unused levels are optimised out by the compiler.</para>

      </section>

        <indexterm>

          <secondary>- hashing</secondary>

        </indexterm>

        <para>Implementation of the global page hash table was encouraged by

        64-bit architectures that can have rather sparse address spaces. The

        hash table contains valid mappings only. Each entry of the hash table

        contains an address space pointer, virtual memory page number (VPN),

        physical memory frame number (PFN) and a set of flags. The pair of the

        address space pointer and the virtual memory page number is used as a

        key for the hash table. One of the major differences between the

        global page hash table and hierarchical 4-level page tables is that

        there is only a single global page hash table in the system while

        hierarchical page tables exist per address space. Thus, the global

        page hash table contains information about mappings of all address

        spaces in the system. </para>

        <para>The global page hash table mechanism uses the generic hash table

        type as described in the chapter about <link linkend="hashtables">data

        structures</link> earlier in this book.</para>

      </section>

    </section>

  </section>

  <section id="tlb">

    <indexterm>

      <primary>TLB</primary>

    </indexterm>

    <title>Translation Lookaside buffer</title>

    <para>Due to the extensive overhead during the page mapping lookup in the

    page tables, all architectures has fast assotiative cache memory built-in

    CPU. This memory called TLB stores recently used page table

    entries.</para>

    <section id="tlb_shootdown">

      <indexterm>

        <primary>TLB</primary>

        <secondary>- TLB shootdown</secondary>

      </indexterm>

      <title>TLB consistency. TLB shootdown algorithm.</title>

      <para>Operating system is responsible for keeping TLB consistent by

      invalidating the contents of TLB, whenever there is some change in page

      tables. Those changes may occur when page or group of pages were

      unmapped, mapping is changed or system switching active address space to

      schedule a new system task. Moreover, this invalidation operation must

      be done an all system CPUs because each CPU has its own independent TLB

      cache. Thus maintaining TLB consistency on SMP configuration as not as

      trivial task as it looks on the first glance. Naive solution would

      assume that is the CPU which wants to invalidate TLB will invalidate TLB

      caches on other CPUs. It is not possible on the most of the

      architectures, because of the simple fact - flushing TLB is allowed only

      on the local CPU and there is no possibility to access other CPUs' TLB

      caches, thus invalidate TLB remotely.</para>

      <para>Technique of remote invalidation of TLB entries is called "TLB

      shootdown". HelenOS uses a variation of the algorithm described by D.

      Black et al., "Translation Lookaside Buffer Consistency: A Software

      Approach," Proc. Third Int'l Conf. Architectural Support for Programming

      Languages and Operating Systems, 1989, pp. 113-122. <xref

      linkend="Black89" /></para>

      <para>As the situation demands, you will want partitial invalidation of

      TLB caches. In case of simple memory mapping change it is necessary to

      invalidate only one or more adjacent pages. In case if the architecture

      is aware of ASIDs, when kernel needs to dump some ASID to use by another

      task, it invalidates only entries from this particular address space.

      Final option of the TLB invalidation is the complete TLB cache

      invalidation, which is the operation that flushes all entries in

      <para>TLB shootdown is performed in two phases.</para>

      <formalpara>

        <title>Phase 1.</title>

        <para>First, initiator locks a global TLB spinlock, then request is

        being put to the local request cache of every other CPU in the system

        protected by its spinlock. In case the cache is full, all requests in

        the cache are replaced by one request, indicating global TLB flush.

        Then the initiator thread sends an IPI message indicating the TLB

        shootdown request to the rest of the CPUs and waits actively until all

        CPUs confirm TLB invalidating action execution by setting up a special

        flag. After setting this flag this thread is blocked on the TLB

        spinlock, held by the initiator.</para>

      </formalpara>

      <formalpara>

        <title>Phase 2.</title>

        <para>All CPUs are waiting on the TLB spinlock to execute TLB

        invalidation action and have indicated their intention to the

        initiator. Initiator continues, cleaning up its TLB and releasing the

        global TLB spinlock. After this all other CPUs gain and immidiately

        release TLB spinlock and perform TLB invalidation actions.</para>

      </formalpara>