Subversion Repositories HelenOS-doc

        <para>The slab allocator is closely modelled after OpenSolaris slab

        <para>The slab allocator is closely modelled after <xref

        spaces in the system. </para>

        spaces in the system.</para>

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

        type as described in the chapter dedicated to <link

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

        linkend="hashtables">data structures</link> earlier in this

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

    <para>Due to the extensive overhead of several extra memory accesses

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

    architectures deploy fast assotiative cache of recelntly used page

    CPU. This memory called TLB stores recently used page table

    mappings. This cache is called TLB - Translation Lookaside Buffer - and is

    entries.</para>

    architectures.</para>

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

      <title>TLB consistency</title>

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

      <para>The operating system is responsible for keeping TLB consistent

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

      with the page tables. Whenever mappings are modified or purged from the

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

      page tables, or when an address space identifier is reused, the kernel

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

      needs to invalidate the respective contents of TLB. Some TLB types

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

      support partial invalidation of their content (e.g. ranges of pages or

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

      address spaces) while other types can be invalidated only entirely. The

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

      invalidation must be done on all processors for there is one TLB per

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

      processor. Maintaining TLB consistency on multiprocessor configurations

      caches, thus invalidate TLB remotely.</para>

      is not as trivial as it might look from the first glance.</para>

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

      <para>The remote TLB invalidation is called TLB shootdown. HelenOS uses

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

      a simplified variant of the algorithm described in <xref

      linkend="Black89" /></para>

      linkend="Black89" />. </para>

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

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

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

        <para>The initiator clears its TLB flag and locks the global TLB

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

        spinlock. The request is then enqueued into all other processors' TLB

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

        shootdown message queues. When the TLB shootdown message queue is full

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

        on any processor, the queue is purged and a single request to

        Then the initiator thread sends an IPI message indicating the TLB

        invalidate the entire TLB is stored there. Once all the TLB shootdown

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

        messages were dispatched, the initiator sends all other processors an

        CPUs confirm TLB invalidating action execution by setting up a special

        interrupt to notify them about the incoming TLB shootdown message. It

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

        then spins until all processors accept the interrupt and clear their

        spinlock, held by the initiator.</para>

        TLB flags.</para>

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

        <para>Except for the initiator, all other processors are spining on

        invalidation action and have indicated their intention to the

        and purge its own TLB. The initiator then unlocks the global TLB

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

        are sequentially granted the spinlock. However, once they manage to

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

        lock it, they immediately release it. Each processor invalidates its

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

        the end, each processor sets its TLB flag and resumes its previous