sam-t2/sam/cpus/vonk/n2/lib/cpu/src/N2_TrieTlb.h

/*
* ========== Copyright Header Begin ==========================================
*
* OpenSPARC T2 Processor File: N2_TrieTlb.h
* Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
*
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
*
* The above named program is distributed in the hope that it will be
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public
* License along with this work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
*
* ========== Copyright Header End ============================================
*/

#ifndef __N2_TrieTlb_h__
#define __N2_TrieTlb_h__

#include <stdlib.h>
#include "SS_Tte.h"
#include "SS_Strand.h"

class N2_Tlb;

class N2_TrieTlb
{
  public:
    N2_TrieTlb( N2_Tlb* );
    N2_TrieTlb( N2_TrieTlb&, N2_Tlb* );
    ~N2_TrieTlb();

    void insert( SS_Strand* strand, SS_Tte* tte, SS_Tte* rem_tte );

    SS_Tte* lookup( uint_t pid, SS_Vaddr ra, bool* multi_hit )
    {
      SS_Tte* tte = lookup(real[pid]->at(ra)->at(ra)->at(ra),ra,multi_hit);
      return tte;
    }

    SS_Tte* lookup( uint_t pid, uint64_t ctx, SS_Vaddr va, bool* multi_hit )
    {
      SS_Tte* tte = lookup(virt[pid][ctx]->at(va)->at(va)->at(va),va,multi_hit);
      return tte;
    }

    void demap_virt( SS_Strand* strand, uint_t pid, uint_t ctx, SS_Vaddr va );
    void demap_virt( SS_Strand* strand, uint_t pid, uint_t ctx );
    void demap_virt( SS_Strand* strand, uint_t pid );
    void demap_real( SS_Strand* strand, uint_t pid, SS_Vaddr va );
    void demap_real( SS_Strand* strand, uint_t pid );
    void demap_all ( SS_Strand* strand, uint_t pid );

  protected:
    // The Trie uses an address (virtual or real) to create a fast deterministic
    // search path to a TTE representing the translation of that address. The
    // address is chopped into pieces that are used to navigate down a trie.
    // Each node has an array that can be indexed to get to the next level.
    // Each node is represented by a TrieNode<S,P,T>. Here the range P to P+S
    // are the bits taken from the address and used as index to get the next
    // level. T is the Type of the node at the next level.

    template<int SIZE_BITS, int PAGE_BITS, class Type>
    class TrieNode
    {
      public:
        enum
        {
          SIZE = 1 << SIZE_BITS,
          MASK = SIZE - 1
        };

        TrieNode<SIZE_BITS,PAGE_BITS,Type>( const Type& fail )
         :
          next(0),
          tte(0),
          set_size(0)
        {
          for (int i = 0; i < SIZE; i++)
            trie[i] = fail;
        }

        TrieNode<SIZE_BITS,PAGE_BITS,Type>( const TrieNode<SIZE_BITS,PAGE_BITS,Type>& t )
         :
          next(0),
          tte(t.tte),
          set_size(t.set_size)
        {
          for (int i = 0; i < SIZE; i++)
            trie[i] = t.trie[i];
        }

        // fail_node() marks a trie node as being part of the fail
        // path. When if due to an error an insert happens in the fail
        // path then we get an assert.

        void fail_node()        { set_size = SIZE; }

        bool is_empty()         { return (set_size == 0) && (tte == 0); }
        bool is_empty_trie()    { return (set_size == 0); }

        Type& at( SS_Vaddr va ) { return trie[(va >> PAGE_BITS) & MASK]; }
        Type& idx( uint_t i )   { return trie[i]; }

        void insert( uint_t i, const Type& type )
        {
          assert(set_size < SIZE);
          set_size++;
          idx(i) = type;
        }

        void insert( SS_Vaddr va, const Type& type )
        {
          assert(set_size < SIZE);
          set_size++;
          at(va) = type;
        }

        void remove( uint_t i, const Type& fail )
        {
          assert(set_size > 0);
          set_size--;
          idx(i) = fail;
        }

        void remove( SS_Vaddr va, const Type& fail )
        {
          assert(set_size > 0);
          set_size--;
          at(va) = fail;
        }

        TrieNode<SIZE_BITS,PAGE_BITS,Type>* next;       // Next pointer in free list

        SS_Tte* tte;            // The overlapping bigger TTE

      private:
        Type    trie[SIZE];
        uint_t  set_size;       // Number of valid pointers in trie[]
    };

    enum
    {
      PID_SIZE = 1 << 3,
      CTX_SIZE = 1 << 13
    };

    // The 48 virtual address bits are broken into 6 levels;
    // Node1, Node2, Node3, Page5, Page3, and Page1. The Page
    // node are the nodes that hold TTEs with page size 5, 3,
    // and 1 nodes respectively. The childs of Page1 are page
    // size 0 nodes.

    typedef class TrieNode<3,13,SS_Tte*> Page1;
    typedef class TrieNode<6,16,Page1*>  Page3;
    typedef class TrieNode<6,22,Page3*>  Page5;
    typedef class TrieNode<7,28,Page5*>  Node3;
    typedef class TrieNode<7,35,Node3*>  Node2;
    typedef class TrieNode<6,42,Node2*>  Node1;

    N2_Tlb* tlb;

    Node1* virt[PID_SIZE][CTX_SIZE];    // Every context has it's trie,
    Node1* real[PID_SIZE];              // and real is no diffenent.

    // All the trie nodes point to valid trie nodes. We use special
    // fail nodes to represent paths in the tree that bare no TTEs.

    Node1* fail_node1;
    Node2* fail_node2;
    Node3* fail_node3;
    Page5* fail_page5;
    Page3* fail_page3;
    Page1* fail_page1;

    Node1* free_node1;
    Node2* free_node2;
    Node3* free_node3;
    Page5* free_page5;
    Page3* free_page3;
    Page1* free_page1;

    // lookup() does a TLB lookup for a given va. The lookup
    // has to work while an insert or a demap is going on
    // concurrently. The N2_Tlb lookup ensure only one
    // insert or demap can overlap this lookup.

    SS_Tte* lookup( Page5* p5, SS_Vaddr addr, bool* multi_hit )
    {
      // Look for a TTE. If page size 5, 3, or 1 has a TTE then
      // check for the presence of a smaller TTE that also translates
      // addr. If there is one (when there is a child node) then
      // we set the multi hit flag. Else there is no multi hit
      // and the flag is cleared.

      Page3*  p3 = p5->at(addr);
      Page1*  p1 = p3->at(addr);

      SS_Tte* p5_tte = p5->tte;
      SS_Tte* p3_tte = p3->tte;
      SS_Tte* p1_tte = p1->tte;
      SS_Tte* p0_tte = p1->at(addr);

      if (p5_tte)
      {
        *multi_hit = (p3_tte != 0) || (p1_tte != 0) || (p0_tte != 0);
        return p5_tte;
      }
      if (p3_tte)
      {
        *multi_hit = (p1_tte != 0) || (p0_tte != 0);
        return p3_tte;
      }
      if (p1_tte)
      {
        *multi_hit = (p0_tte != 0);
        return p1_tte;
      }
      *multi_hit = false;
      return p0_tte;
    }


    void remove( SS_Tte* tte );

    Node1* copy( Node1* );

    // demap_trie() demaps the trie either for a given va
    // or from a given node.

    bool demap_trie( SS_Strand* strand, Node1* n1, SS_Vaddr va );
    void demap_trie( SS_Strand* strand, Node1* n1 );
    void demap_trie( SS_Strand* strand, Node2* n2 );
    void demap_trie( SS_Strand* strand, Node3* n3 );
    void demap_trie( SS_Strand* strand, Page5* p5 );
    void demap_trie( SS_Strand* strand, Page3* p3 );
    void demap_trie( SS_Strand* strand, Page1* p1 );

    // new_node1(), new_node2(), new_node3(),
    // new_page5(), new_page3(), new_page1 get new trie
    // nodes for the corresponding free lists.

    Node1* new_node1()
    {
      if (free_node1 == 0)
        return new Node1(fail_node2);
      Node1* node1 = free_node1;
      free_node1 = free_node1->next;
      return node1;
    }

    Node2* new_node2()
    {
      if (free_node2 == 0)
        return new Node2(fail_node3);
      Node2* node2 = free_node2;
      free_node2 = free_node2->next;
      return node2;
    }

    Node3* new_node3()
    {
      if (free_node3 == 0)
        return new Node3(fail_page5);
      Node3* node3 = free_node3;
      free_node3 = free_node3->next;
      return node3;
    }

    Page5* new_page5()
    {
      if (free_page5 == 0)
        return new Page5(fail_page3);
      Page5* page5 = free_page5;
      free_page5 = free_page5->next;
      return new(page5) Page5(fail_page3);
    }

    Page5* new_page5( Page5* p5 )
    {
      if (free_page5 == 0)
        return new Page5(*p5);
      Page5* page5 = free_page5;
      free_page5 = free_page5->next;
      return new(page5) Page5(*p5);
    }

    Page3* new_page3()
    {
      if (free_page3 == 0)
        return new Page3(fail_page1);
      Page3* page3 = free_page3;
      free_page3 = free_page3->next;
      return new(page3) Page3(fail_page1);
    }

    Page3* new_page3( Page3* p3 )
    {
      if (free_page3 == 0)
        return new Page3(*p3);
      Page3* page3 = free_page3;
      free_page3 = free_page3->next;
      return new(page3) Page3(*p3);
    }

    Page1* new_page1()
    {
      if (free_page1 == 0)
        return new Page1(0);
      Page1* page1 = free_page1;
      free_page1 = free_page1->next;
      return new(page1) Page1(0);
    }

    Page1* new_page1( Page1* p1 )
    {
      if (free_page1 == 0)
        return new Page1(*p1);
      Page1* page1 = free_page1;
      free_page1 = free_page1->next;
      return new(page1) Page1(*p1);
    }

    // del_node1(), del_node2(), del_node3(), del_page5(),
    // del_page3(), del_page1() free up a trie node and put
    // it on the corresponding free list.

    void del_node1( Node1* node1 )
    {
      node1->next = free_node1;
      free_node1 = node1;
    }

    void del_node2( Node2* node2 )
    {
      node2->next = free_node2;
      free_node2 = node2;
    }

    void del_node3( Node3* node3 )
    {
      node3->next = free_node3;
      free_node3 = node3;
    }

    void del_page5( Page5* page5 )
    {
      page5->next = free_page5;
      free_page5 = page5;
    }

    void del_page3( Page3* page3 )
    {
      page3->next = free_page3;
      free_page3 = page3;
    }

    void del_page1( Page1* page1 )
    {
      page1->next = free_page1;
      free_page1 = page1;
    }

};

#endif