* ========== 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 ============================================
N2_TrieTlb( N2_TrieTlb
&, N2_Tlb
* );
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
);
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
);
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
);
// 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
>
TrieNode
<SIZE_BITS
,PAGE_BITS
,Type
>( const Type
& fail
)
for (int i
= 0; i
< SIZE
; i
++)
TrieNode
<SIZE_BITS
,PAGE_BITS
,Type
>( const TrieNode
<SIZE_BITS
,PAGE_BITS
,Type
>& t
)
for (int i
= 0; i
< SIZE
; 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
)
void insert( SS_Vaddr va
, const Type
& type
)
void remove( uint_t i
, const Type
& fail
)
void remove( SS_Vaddr va
, const Type
& fail
)
TrieNode
<SIZE_BITS
,PAGE_BITS
,Type
>* next
; // Next pointer in free list
SS_Tte
* tte
; // The overlapping bigger TTE
uint_t set_size
; // Number of valid pointers in trie[]
// 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
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
;
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.
// 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
);
*multi_hit
= (p3_tte
!= 0) || (p1_tte
!= 0) || (p0_tte
!= 0);
*multi_hit
= (p1_tte
!= 0) || (p0_tte
!= 0);
*multi_hit
= (p0_tte
!= 0);
void remove( SS_Tte
* tte
);
// demap_trie() demaps the trie either for a given va
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.
return new Node1(fail_node2
);
Node1
* node1
= free_node1
;
free_node1
= free_node1
->next
;
return new Node2(fail_node3
);
Node2
* node2
= free_node2
;
free_node2
= free_node2
->next
;
return new Node3(fail_page5
);
Node3
* node3
= free_node3
;
free_node3
= free_node3
->next
;
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
)
Page5
* page5
= free_page5
;
free_page5
= free_page5
->next
;
return new(page5
) Page5(*p5
);
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
)
Page3
* page3
= free_page3
;
free_page3
= free_page3
->next
;
return new(page3
) Page3(*p3
);
Page1
* page1
= free_page1
;
free_page1
= free_page1
->next
;
return new(page1
) Page1(0);
Page1
* new_page1( 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
;
void del_node2( Node2
* node2
)
node2
->next
= free_node2
;
void del_node3( Node3
* node3
)
node3
->next
= free_node3
;
void del_page5( Page5
* page5
)
page5
->next
= free_page5
;
void del_page3( Page3
* page3
)
page3
->next
= free_page3
;
void del_page1( Page1
* page1
)
page1
->next
= free_page1
;