| 1 | /* |
| 2 | * ========== Copyright Header Begin ========================================== |
| 3 | * |
| 4 | * OpenSPARC T2 Processor File: N2_TrieTlb.h |
| 5 | * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. |
| 6 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES. |
| 7 | * |
| 8 | * The above named program is free software; you can redistribute it and/or |
| 9 | * modify it under the terms of the GNU General Public |
| 10 | * License version 2 as published by the Free Software Foundation. |
| 11 | * |
| 12 | * The above named program is distributed in the hope that it will be |
| 13 | * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 15 | * General Public License for more details. |
| 16 | * |
| 17 | * You should have received a copy of the GNU General Public |
| 18 | * License along with this work; if not, write to the Free Software |
| 19 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. |
| 20 | * |
| 21 | * ========== Copyright Header End ============================================ |
| 22 | */ |
| 23 | |
| 24 | #ifndef __N2_TrieTlb_h__ |
| 25 | #define __N2_TrieTlb_h__ |
| 26 | |
| 27 | #include <stdlib.h> |
| 28 | #include "SS_Tte.h" |
| 29 | #include "SS_Strand.h" |
| 30 | |
| 31 | class N2_Tlb; |
| 32 | |
| 33 | class N2_TrieTlb |
| 34 | { |
| 35 | public: |
| 36 | N2_TrieTlb( N2_Tlb* ); |
| 37 | N2_TrieTlb( N2_TrieTlb&, N2_Tlb* ); |
| 38 | ~N2_TrieTlb(); |
| 39 | |
| 40 | void insert( SS_Strand* strand, SS_Tte* tte, SS_Tte* rem_tte ); |
| 41 | |
| 42 | SS_Tte* lookup( uint_t pid, SS_Vaddr ra, bool* multi_hit ) |
| 43 | { |
| 44 | SS_Tte* tte = lookup(real[pid]->at(ra)->at(ra)->at(ra),ra,multi_hit); |
| 45 | return tte; |
| 46 | } |
| 47 | |
| 48 | SS_Tte* lookup( uint_t pid, uint64_t ctx, SS_Vaddr va, bool* multi_hit ) |
| 49 | { |
| 50 | SS_Tte* tte = lookup(virt[pid][ctx]->at(va)->at(va)->at(va),va,multi_hit); |
| 51 | return tte; |
| 52 | } |
| 53 | |
| 54 | void demap_virt( SS_Strand* strand, uint_t pid, uint_t ctx, SS_Vaddr va ); |
| 55 | void demap_virt( SS_Strand* strand, uint_t pid, uint_t ctx ); |
| 56 | void demap_virt( SS_Strand* strand, uint_t pid ); |
| 57 | void demap_real( SS_Strand* strand, uint_t pid, SS_Vaddr va ); |
| 58 | void demap_real( SS_Strand* strand, uint_t pid ); |
| 59 | void demap_all ( SS_Strand* strand, uint_t pid ); |
| 60 | |
| 61 | protected: |
| 62 | // The Trie uses an address (virtual or real) to create a fast deterministic |
| 63 | // search path to a TTE representing the translation of that address. The |
| 64 | // address is chopped into pieces that are used to navigate down a trie. |
| 65 | // Each node has an array that can be indexed to get to the next level. |
| 66 | // Each node is represented by a TrieNode<S,P,T>. Here the range P to P+S |
| 67 | // are the bits taken from the address and used as index to get the next |
| 68 | // level. T is the Type of the node at the next level. |
| 69 | |
| 70 | template<int SIZE_BITS, int PAGE_BITS, class Type> |
| 71 | class TrieNode |
| 72 | { |
| 73 | public: |
| 74 | enum |
| 75 | { |
| 76 | SIZE = 1 << SIZE_BITS, |
| 77 | MASK = SIZE - 1 |
| 78 | }; |
| 79 | |
| 80 | TrieNode<SIZE_BITS,PAGE_BITS,Type>( const Type& fail ) |
| 81 | : |
| 82 | next(0), |
| 83 | tte(0), |
| 84 | set_size(0) |
| 85 | { |
| 86 | for (int i = 0; i < SIZE; i++) |
| 87 | trie[i] = fail; |
| 88 | } |
| 89 | |
| 90 | TrieNode<SIZE_BITS,PAGE_BITS,Type>( const TrieNode<SIZE_BITS,PAGE_BITS,Type>& t ) |
| 91 | : |
| 92 | next(0), |
| 93 | tte(t.tte), |
| 94 | set_size(t.set_size) |
| 95 | { |
| 96 | for (int i = 0; i < SIZE; i++) |
| 97 | trie[i] = t.trie[i]; |
| 98 | } |
| 99 | |
| 100 | // fail_node() marks a trie node as being part of the fail |
| 101 | // path. When if due to an error an insert happens in the fail |
| 102 | // path then we get an assert. |
| 103 | |
| 104 | void fail_node() { set_size = SIZE; } |
| 105 | |
| 106 | bool is_empty() { return (set_size == 0) && (tte == 0); } |
| 107 | bool is_empty_trie() { return (set_size == 0); } |
| 108 | |
| 109 | Type& at( SS_Vaddr va ) { return trie[(va >> PAGE_BITS) & MASK]; } |
| 110 | Type& idx( uint_t i ) { return trie[i]; } |
| 111 | |
| 112 | void insert( uint_t i, const Type& type ) |
| 113 | { |
| 114 | assert(set_size < SIZE); |
| 115 | set_size++; |
| 116 | idx(i) = type; |
| 117 | } |
| 118 | |
| 119 | void insert( SS_Vaddr va, const Type& type ) |
| 120 | { |
| 121 | assert(set_size < SIZE); |
| 122 | set_size++; |
| 123 | at(va) = type; |
| 124 | } |
| 125 | |
| 126 | void remove( uint_t i, const Type& fail ) |
| 127 | { |
| 128 | assert(set_size > 0); |
| 129 | set_size--; |
| 130 | idx(i) = fail; |
| 131 | } |
| 132 | |
| 133 | void remove( SS_Vaddr va, const Type& fail ) |
| 134 | { |
| 135 | assert(set_size > 0); |
| 136 | set_size--; |
| 137 | at(va) = fail; |
| 138 | } |
| 139 | |
| 140 | TrieNode<SIZE_BITS,PAGE_BITS,Type>* next; // Next pointer in free list |
| 141 | |
| 142 | SS_Tte* tte; // The overlapping bigger TTE |
| 143 | |
| 144 | private: |
| 145 | Type trie[SIZE]; |
| 146 | uint_t set_size; // Number of valid pointers in trie[] |
| 147 | }; |
| 148 | |
| 149 | enum |
| 150 | { |
| 151 | PID_SIZE = 1 << 3, |
| 152 | CTX_SIZE = 1 << 13 |
| 153 | }; |
| 154 | |
| 155 | // The 48 virtual address bits are broken into 6 levels; |
| 156 | // Node1, Node2, Node3, Page5, Page3, and Page1. The Page |
| 157 | // node are the nodes that hold TTEs with page size 5, 3, |
| 158 | // and 1 nodes respectively. The childs of Page1 are page |
| 159 | // size 0 nodes. |
| 160 | |
| 161 | typedef class TrieNode<3,13,SS_Tte*> Page1; |
| 162 | typedef class TrieNode<6,16,Page1*> Page3; |
| 163 | typedef class TrieNode<6,22,Page3*> Page5; |
| 164 | typedef class TrieNode<7,28,Page5*> Node3; |
| 165 | typedef class TrieNode<7,35,Node3*> Node2; |
| 166 | typedef class TrieNode<6,42,Node2*> Node1; |
| 167 | |
| 168 | N2_Tlb* tlb; |
| 169 | |
| 170 | Node1* virt[PID_SIZE][CTX_SIZE]; // Every context has it's trie, |
| 171 | Node1* real[PID_SIZE]; // and real is no diffenent. |
| 172 | |
| 173 | // All the trie nodes point to valid trie nodes. We use special |
| 174 | // fail nodes to represent paths in the tree that bare no TTEs. |
| 175 | |
| 176 | Node1* fail_node1; |
| 177 | Node2* fail_node2; |
| 178 | Node3* fail_node3; |
| 179 | Page5* fail_page5; |
| 180 | Page3* fail_page3; |
| 181 | Page1* fail_page1; |
| 182 | |
| 183 | Node1* free_node1; |
| 184 | Node2* free_node2; |
| 185 | Node3* free_node3; |
| 186 | Page5* free_page5; |
| 187 | Page3* free_page3; |
| 188 | Page1* free_page1; |
| 189 | |
| 190 | // lookup() does a TLB lookup for a given va. The lookup |
| 191 | // has to work while an insert or a demap is going on |
| 192 | // concurrently. The N2_Tlb lookup ensure only one |
| 193 | // insert or demap can overlap this lookup. |
| 194 | |
| 195 | SS_Tte* lookup( Page5* p5, SS_Vaddr addr, bool* multi_hit ) |
| 196 | { |
| 197 | // Look for a TTE. If page size 5, 3, or 1 has a TTE then |
| 198 | // check for the presence of a smaller TTE that also translates |
| 199 | // addr. If there is one (when there is a child node) then |
| 200 | // we set the multi hit flag. Else there is no multi hit |
| 201 | // and the flag is cleared. |
| 202 | |
| 203 | Page3* p3 = p5->at(addr); |
| 204 | Page1* p1 = p3->at(addr); |
| 205 | |
| 206 | SS_Tte* p5_tte = p5->tte; |
| 207 | SS_Tte* p3_tte = p3->tte; |
| 208 | SS_Tte* p1_tte = p1->tte; |
| 209 | SS_Tte* p0_tte = p1->at(addr); |
| 210 | |
| 211 | if (p5_tte) |
| 212 | { |
| 213 | *multi_hit = (p3_tte != 0) || (p1_tte != 0) || (p0_tte != 0); |
| 214 | return p5_tte; |
| 215 | } |
| 216 | if (p3_tte) |
| 217 | { |
| 218 | *multi_hit = (p1_tte != 0) || (p0_tte != 0); |
| 219 | return p3_tte; |
| 220 | } |
| 221 | if (p1_tte) |
| 222 | { |
| 223 | *multi_hit = (p0_tte != 0); |
| 224 | return p1_tte; |
| 225 | } |
| 226 | *multi_hit = false; |
| 227 | return p0_tte; |
| 228 | } |
| 229 | |
| 230 | |
| 231 | void remove( SS_Tte* tte ); |
| 232 | |
| 233 | Node1* copy( Node1* ); |
| 234 | |
| 235 | // demap_trie() demaps the trie either for a given va |
| 236 | // or from a given node. |
| 237 | |
| 238 | bool demap_trie( SS_Strand* strand, Node1* n1, SS_Vaddr va ); |
| 239 | void demap_trie( SS_Strand* strand, Node1* n1 ); |
| 240 | void demap_trie( SS_Strand* strand, Node2* n2 ); |
| 241 | void demap_trie( SS_Strand* strand, Node3* n3 ); |
| 242 | void demap_trie( SS_Strand* strand, Page5* p5 ); |
| 243 | void demap_trie( SS_Strand* strand, Page3* p3 ); |
| 244 | void demap_trie( SS_Strand* strand, Page1* p1 ); |
| 245 | |
| 246 | // new_node1(), new_node2(), new_node3(), |
| 247 | // new_page5(), new_page3(), new_page1 get new trie |
| 248 | // nodes for the corresponding free lists. |
| 249 | |
| 250 | Node1* new_node1() |
| 251 | { |
| 252 | if (free_node1 == 0) |
| 253 | return new Node1(fail_node2); |
| 254 | Node1* node1 = free_node1; |
| 255 | free_node1 = free_node1->next; |
| 256 | return node1; |
| 257 | } |
| 258 | |
| 259 | Node2* new_node2() |
| 260 | { |
| 261 | if (free_node2 == 0) |
| 262 | return new Node2(fail_node3); |
| 263 | Node2* node2 = free_node2; |
| 264 | free_node2 = free_node2->next; |
| 265 | return node2; |
| 266 | } |
| 267 | |
| 268 | Node3* new_node3() |
| 269 | { |
| 270 | if (free_node3 == 0) |
| 271 | return new Node3(fail_page5); |
| 272 | Node3* node3 = free_node3; |
| 273 | free_node3 = free_node3->next; |
| 274 | return node3; |
| 275 | } |
| 276 | |
| 277 | Page5* new_page5() |
| 278 | { |
| 279 | if (free_page5 == 0) |
| 280 | return new Page5(fail_page3); |
| 281 | Page5* page5 = free_page5; |
| 282 | free_page5 = free_page5->next; |
| 283 | return new(page5) Page5(fail_page3); |
| 284 | } |
| 285 | |
| 286 | Page5* new_page5( Page5* p5 ) |
| 287 | { |
| 288 | if (free_page5 == 0) |
| 289 | return new Page5(*p5); |
| 290 | Page5* page5 = free_page5; |
| 291 | free_page5 = free_page5->next; |
| 292 | return new(page5) Page5(*p5); |
| 293 | } |
| 294 | |
| 295 | Page3* new_page3() |
| 296 | { |
| 297 | if (free_page3 == 0) |
| 298 | return new Page3(fail_page1); |
| 299 | Page3* page3 = free_page3; |
| 300 | free_page3 = free_page3->next; |
| 301 | return new(page3) Page3(fail_page1); |
| 302 | } |
| 303 | |
| 304 | Page3* new_page3( Page3* p3 ) |
| 305 | { |
| 306 | if (free_page3 == 0) |
| 307 | return new Page3(*p3); |
| 308 | Page3* page3 = free_page3; |
| 309 | free_page3 = free_page3->next; |
| 310 | return new(page3) Page3(*p3); |
| 311 | } |
| 312 | |
| 313 | Page1* new_page1() |
| 314 | { |
| 315 | if (free_page1 == 0) |
| 316 | return new Page1(0); |
| 317 | Page1* page1 = free_page1; |
| 318 | free_page1 = free_page1->next; |
| 319 | return new(page1) Page1(0); |
| 320 | } |
| 321 | |
| 322 | Page1* new_page1( Page1* p1 ) |
| 323 | { |
| 324 | if (free_page1 == 0) |
| 325 | return new Page1(*p1); |
| 326 | Page1* page1 = free_page1; |
| 327 | free_page1 = free_page1->next; |
| 328 | return new(page1) Page1(*p1); |
| 329 | } |
| 330 | |
| 331 | // del_node1(), del_node2(), del_node3(), del_page5(), |
| 332 | // del_page3(), del_page1() free up a trie node and put |
| 333 | // it on the corresponding free list. |
| 334 | |
| 335 | void del_node1( Node1* node1 ) |
| 336 | { |
| 337 | node1->next = free_node1; |
| 338 | free_node1 = node1; |
| 339 | } |
| 340 | |
| 341 | void del_node2( Node2* node2 ) |
| 342 | { |
| 343 | node2->next = free_node2; |
| 344 | free_node2 = node2; |
| 345 | } |
| 346 | |
| 347 | void del_node3( Node3* node3 ) |
| 348 | { |
| 349 | node3->next = free_node3; |
| 350 | free_node3 = node3; |
| 351 | } |
| 352 | |
| 353 | void del_page5( Page5* page5 ) |
| 354 | { |
| 355 | page5->next = free_page5; |
| 356 | free_page5 = page5; |
| 357 | } |
| 358 | |
| 359 | void del_page3( Page3* page3 ) |
| 360 | { |
| 361 | page3->next = free_page3; |
| 362 | free_page3 = page3; |
| 363 | } |
| 364 | |
| 365 | void del_page1( Page1* page1 ) |
| 366 | { |
| 367 | page1->next = free_page1; |
| 368 | free_page1 = page1; |
| 369 | } |
| 370 | |
| 371 | }; |
| 372 | |
| 373 | #endif |