3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Kanishk Sugand 38 */ 39
| 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Kanishk Sugand 38 */ 39
|
126// The updateSum method is a recursive function which updates 127// the node sums till the root. It also deletes the nodes that 128// are not used anymore. 129uint64_t 130StackDistCalc::updateSum(Node* node, bool from_left, 131 uint64_t sum_from_below, uint64_t level, 132 uint64_t stack_dist, bool discard_node) 133{ 134 ++level; 135 136 // Make a copy of the node variables and work on them 137 // as a node may be deleted by this function 138 uint64_t node_sum_l = node->sumLeft; 139 uint64_t node_sum_r = node->sumRight; 140 bool node_left = node->isLeftNode; 141 bool node_discard_left = node->discardLeft; 142 bool node_discard_right = node->discardRight; 143 uint64_t node_n_index = node->nodeIndex; 144 Node* node_parent_ptr = node->parent; 145 146 // For verification 147 if (verifyStack) { 148 // This sanity check makes sure that the left_sum and 149 // right_sum of the node is not greater than the 150 // maximum possible value given by the leaves below it 151 // for example a node in layer 3 (tree[3]) can at most 152 // have 8 leaves (4 to the left and 4 to the right) 153 // thus left_sum and right_sum should be <= 4 154 panic_if(node_sum_l > (1 << (level - 1)), 155 "Error in sum left of level %ul, node index %ull, " 156 "Sum = %ull \n", level, node_n_index, node_sum_l); 157 158 panic_if(node_sum_r > (1 << (level - 1)), 159 "Error in sum right of level %ul, node index %ull, " 160 "Sum = %ull \n", level, node_n_index, node_sum_r); 161 } 162 163 // Update the left sum or the right sum depending on the 164 // from_left flag. Variable stack_dist is updated only 165 // when arriving from Left. 166 if (from_left) { 167 // update sumLeft 168 node_sum_l = sum_from_below; 169 stack_dist += node_sum_r; 170 } else { 171 // update sum_r 172 node_sum_r = sum_from_below; 173 } 174 175 // sum_from_below == 0 can be a leaf discard operation 176 if (discard_node && !sum_from_below) { 177 if (from_left) 178 node_discard_left = true; 179 else 180 node_discard_right = true; 181 } 182 183 // Update the node variables with new values 184 node->nodeIndex = node_n_index; 185 node->sumLeft = node_sum_l; 186 node->sumRight = node_sum_r; 187 node->isLeftNode = node_left; 188 node->discardLeft = node_discard_left; 189 node->discardRight = node_discard_right; 190 191 // Delete the node if it is not required anymore 192 if (node_discard_left && node_discard_right && 193 discard_node && node_parent_ptr && !sum_from_below) { 194 delete node; 195 tree[level].erase(node_n_index); 196 discard_node = true; 197 } else { 198 // propogate discard_node as false upwards if the 199 // above conditions are not met. 200 discard_node = false; 201 } 202 203 // Recursively call the updateSum operation till the 204 // root node is reached 205 if (node_parent_ptr) { 206 stack_dist = updateSum(node_parent_ptr, node_left, 207 node_sum_l + node_sum_r, 208 level, stack_dist, discard_node); 209 } 210 211 return stack_dist; 212} 213 214// This function is called by the calcStackDistAndUpdate function 215// If is_new_leaf is true then a new leaf is added otherwise a leaf 216// removed from the tree. In both cases the tree is updated using 217// the updateSum operation. 218uint64_t 219StackDistCalc::updateSumsLeavesToRoot(Node* node, bool is_new_leaf) 220{ 221 uint64_t level = 0; 222 uint64_t stack_dist = 0; 223 224 if (is_new_leaf) { 225 node->sumLeft = 1; 226 updateSum(node->parent, 227 node->isLeftNode, node->sumLeft, 228 level, 0, false); 229 230 stack_dist = Infinity; 231 } else { 232 node->sumLeft = 0; 233 stack_dist = updateSum(node->parent, 234 node->isLeftNode, 0, 235 level, stack_dist, true); 236 } 237 238 return stack_dist; 239} 240 241// This method is a recursive function which calculates 242// the node sums till the root. 243uint64_t 244StackDistCalc::getSum(Node* node, bool from_left, uint64_t sum_from_below, 245 uint64_t stack_dist, uint64_t level) const 246{ 247 ++level; 248 // Variable stack_dist is updated only 249 // when arriving from Left. 250 if(from_left) { 251 stack_dist += node->sumRight; 252 } 253 254 // Recursively call the getSum operation till the 255 // root node is reached 256 if(node->parent) { 257 stack_dist = getSum(node->parent, node->isLeftNode, 258 node->sumLeft + node->sumRight, 259 stack_dist, level); 260 } 261 262 return stack_dist; 263} 264 265// This function is called by the calcStackDistance function 266uint64_t 267StackDistCalc::getSumsLeavesToRoot(Node* node) const 268{ 269 return getSum(node->parent, node->isLeftNode, 0, 0, 0); 270} 271 272// Update tree is a tree balancing operation which maintains 273// the binary tree structure. This method is called whenever 274// index%2 == 0 (i.e. every alternate cycle) 275// The two main operation are : 276// OP1. moving the root node one layer up if index counter 277// crosses power of 2 278// OP2. Addition of intermediate nodes as and when required 279// and linking them to their parents in the layer above. 280void 281StackDistCalc::updateTree() 282{ 283 uint64_t i; 284 285 if (isPowerOf2(index)) { 286 // OP1. moving the root node one layer up if index counter 287 // crosses power of 2 288 // If index counter crosses a power of 2, then add a 289 // new tree layer above and create a new Root node in it. 290 // After the root is created the old node 291 // in the layer below is updated to point to this 292 // newly created root node. The sum_l of this new root node 293 // becomes the sum_l + sum_r of the old node. 294 // 295 // After this root update operation a chain of intermediate 296 // nodes is created from root layer to tree[1](one layer 297 // above the leaf layer) 298 299 // Create a new root node 300 Node* newRootNode = new Node(); 301 302 // Update its sum_l as the sum_l+sum_r from below 303 newRootNode->sumLeft = tree[getTreeDepth()][0]->sumRight + 304 tree[getTreeDepth()][0]->sumLeft; 305 // Update its discard left flag if the node below has 306 // has both discardLeft and discardRight set. 307 newRootNode->discardLeft = tree[getTreeDepth()][0]->discardLeft && 308 tree[getTreeDepth()][0]->discardRight; 309 310 // Map type variable, representing a layer in the tree 311 IndexNodeMap treeLevel; 312 // Add a new layer to the tree 313 tree.push_back(treeLevel); 314 nextIndex.push_back(1); 315 tree[getTreeDepth()][newRootNode->nodeIndex] = newRootNode; 316 317 // Update the parent pointer at lower layer to 318 // point to newly created root node 319 tree[getTreeDepth() - 1][0]->parent = tree[getTreeDepth()][0]; 320 321 // Add intermediate nodes from root till bottom (one layer above the 322 // leaf layer) 323 for (i = getTreeDepth() - 1; i >= 1; --i) { 324 Node* newINode = new Node(); 325 // newNode is left or right child depending on the number of nodes 326 // in that layer 327 if (nextIndex[i] % 2 == 0) { 328 newINode->isLeftNode = true; 329 } else { 330 newINode->isLeftNode = false; 331 } 332 333 newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; 334 newINode->nodeIndex = ++nextIndex[i] - 1; 335 tree[i][newINode->nodeIndex] = newINode; 336 } 337 } else { 338 // OP2. Addition of intermediate nodes as and when required 339 // and linking them to their parents in the layer above. 340 // 341 // At layer 1 a new INode is added whenever index%(2^1)==0 342 // (multiples of 2) 343 // 344 // At layer 2 a new INode is added whenever index%(2^2)==0 345 // (multiples of 4) 346 // 347 // At layer 3 a new INode is added whenever index%(2^3)==0 348 // (multiples of 8) 349 //... 350 // 351 // At layer N a new INode is added whenever index%(2^N)==0 352 // (multiples of 2^N) 353 for (i = getTreeDepth() - 1; i >= 1; --i) { 354 // Traverse each layer from root to leaves and add a new 355 // intermediate node if required. Link the parent_ptr of 356 // the new node to the parent in the above layer. 357 358 if ((index % (1 << i)) == 0) { 359 // Checks if current (index % 2^treeDepth) == 0 if true 360 // a new node at that layer is created 361 Node* newINode = new Node(); 362 363 // newNode is left or right child depending on the 364 // number of nodes in that layer. 365 if (nextIndex[i] % 2 == 0) { 366 newINode->isLeftNode = true; 367 } else { 368 newINode->isLeftNode = false; 369 } 370 371 // Pointing to its parent in the upper layer 372 newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; 373 newINode->nodeIndex = ++nextIndex[i] - 1; 374 tree[i][newINode->nodeIndex] = newINode; 375 } 376 } 377 } 378} 379 380// This function is called everytime to get the stack distance and add 381// a new node. A feature to mark an old node in the tree is 382// added. This is useful if it is required to see the reuse 383// pattern. For example, BackInvalidates from the lower level (Membus) 384// to L2, can be marked (isMarked flag of Node set to True). And then 385// later if this same address is accessed by L1, the value of the 386// isMarked flag would be True. This would give some insight on how 387// the BackInvalidates policy of the lower level affect the read/write 388// accesses in an application. 389std::pair< uint64_t, bool> 390StackDistCalc::calcStackDistAndUpdate(const Addr r_address, bool addNewNode) 391{ 392 Node* newLeafNode; 393 // Return index if the address was already present in stack 394 uint64_t r_index = index; 395 396 auto ai = aiMap.lower_bound(r_address); 397 398 // Default value of flag indicating as the left or right leaf 399 bool isLeft = true; 400 // Default value of isMarked flag for each node. 401 bool _mark = false; 402 // By default stackDistacne is treated as infinity 403 uint64_t stack_dist; 404 405 // Lookup aiMap by giving address as the key: 406 // If found take address and Lookup in tree 407 // Update tree from leaves by making B(found index) = 0 408 // Add sums to right till root while Updating them 409 // Stack Distance of that address sums to right 410 if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { 411 // key already exists 412 // save the index counter value when this address was 413 // encountered before and update it to the current index value 414 r_index = ai->second; 415 416 if (addNewNode) { 417 // Update aiMap aiMap(Address) = current index 418 ai->second = index; 419 } else { 420 aiMap.erase(r_address); 421 } 422 423 // Call update tree operation on the tree starting with 424 // the r_index value found above. This function would return 425 // the value of the stack distcance. 426 stack_dist = updateSumsLeavesToRoot(tree[0][r_index], false); 427 newLeafNode = tree[0][r_index]; 428 // determine if this node was marked earlier 429 _mark = newLeafNode->isMarked; 430 delete newLeafNode; 431 tree[0].erase(r_index); 432 } else { 433 if (addNewNode) { 434 // Update aiMap aiMap(Address) = current index 435 aiMap[r_address] = index; 436 } 437 // Update infinity bin count 438 // By default stackDistacne is treated as infinity 439 stack_dist = Infinity; 440 } 441 442 if (addNewNode) { 443 // If index%2 == 0 then update tree 444 if (index % 2 == 0) { 445 updateTree(); 446 } else { 447 // At odd values of index counter, a new right-type node is 448 // added to the leaf layer, else a left-type node is added 449 isLeft = false; 450 } 451 452 // Add new leaf node in the leaf layer (tree[0]) 453 // set n_index = current index 454 newLeafNode = new Node(); 455 ++nextIndex[0]; 456 newLeafNode->nodeIndex=index; 457 newLeafNode->isLeftNode=isLeft; 458 // Point the parent pointer to the intermediate node above 459 newLeafNode->parent = tree[1][nextIndex[1] - 1]; 460 tree[0][index] = newLeafNode; 461 // call an update operation which would update the tree after 462 // addition of this new leaf node. 463 updateSumsLeavesToRoot(tree[0][index], true); 464 465 // For verification 466 if (verifyStack) { 467 // This function checks the sanity of the tree to make sure the 468 // last node in the link of parent pointers is the root node. 469 // It takes a leaf node as an argument and traveses upwards till 470 // the root layer to check if the last parent is null 471 sanityCheckTree(tree[0][index]); 472 473 // Push the same element in debug stack, and check 474 uint64_t verify_stack_dist = verifyStackDist(r_address, true); 475 panic_if(verify_stack_dist != stack_dist, 476 "Expected stack-distance for address \ 477 %#lx is %#lx but found %#lx", 478 r_address, verify_stack_dist, stack_dist); 479 printStack(); 480 } 481 482 // The index counter is updated at the end of each transaction 483 // (unique or non-unique) 484 ++index; 485 } 486 487 return (std::make_pair(stack_dist, _mark)); 488} 489 490// This function is called everytime to get the stack distance 491// no new node is added. It can be used to mark a previous access 492// and inspect the value of the mark flag. 493std::pair< uint64_t, bool> 494StackDistCalc::calcStackDist(const Addr r_address, bool mark) 495{ 496 // Return index if the address was already present in stack 497 uint64_t r_index = index; 498 // Default value of isMarked flag for each node. 499 bool _mark = false; 500 501 auto ai = aiMap.lower_bound(r_address); 502 503 // By default stackDistacne is treated as infinity 504 uint64_t stack_dist = 0; 505 506 // Lookup aiMap by giving address as the key: 507 // If found take address and Lookup in tree 508 // Add sums to right till root 509 // Stack Distance of that address sums to right 510 if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { 511 // key already exists 512 // save the index counter value when this address was 513 // encountered before 514 r_index = ai->second; 515 516 // Get the value of mark flag if previously marked 517 _mark = tree[0][r_index]->isMarked; 518 // Mark the leaf node if required 519 tree[0][r_index]->isMarked = mark; 520 521 // Call get sums operation on the tree starting with 522 // the r_index value found above. This function would return 523 // the value of the stack distcance. 524 stack_dist = getSumsLeavesToRoot(tree[0][r_index]); 525 } else { 526 // Update infinity bin count 527 // By default stackDistacne is treated as infinity 528 stack_dist = Infinity; 529 } 530 531 // For verification 532 if (verifyStack) { 533 // Calculate the SD of the same address in the debug stack 534 uint64_t verify_stack_dist = verifyStackDist(r_address); 535 panic_if(verify_stack_dist != stack_dist, 536 "Expected stack-distance for address \ 537 %#lx is %#lx but found %#lx", 538 r_address, verify_stack_dist, stack_dist); 539 540 printStack(); 541 } 542 543 return std::make_pair(stack_dist, _mark); 544} 545 546// For verification 547// Simple sanity check for the tree 548void 549StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const 550{ 551 const Node* next_up = node->parent; 552 553 for (uint64_t i = level + 1; i < getTreeDepth() - level; ++i) { 554 next_up = next_up->parent; 555 panic_if(!next_up, "Sanity check failed for node %ull \n", 556 node->nodeIndex); 557 } 558 559 // At the root layer the parent_ptr should be null 560 panic_if(next_up->parent, "Sanity check failed for node %ull \n", 561 node->nodeIndex); 562} 563 564// This method can be called to compute the stack distance in a naive 565// way It can be used to verify the functionality of the stack 566// distance calculator. It uses std::vector to compute the stack 567// distance using a naive stack. 568uint64_t 569StackDistCalc::verifyStackDist(const Addr r_address, bool update_stack) 570{ 571 bool found = false; 572 uint64_t stack_dist = 0; 573 auto a = stack.rbegin(); 574 575 for (; a != stack.rend(); ++a) { 576 if (*a == r_address) { 577 found = true; 578 break; 579 } else { 580 ++stack_dist; 581 } 582 } 583 584 if (found) { 585 ++a; 586 if (update_stack) 587 stack.erase(a.base()); 588 } else { 589 stack_dist = Infinity; 590 } 591 592 if (update_stack) 593 stack.push_back(r_address); 594 595 return stack_dist; 596} 597 598// This method is useful to print top n entities in the stack. 599void 600StackDistCalc::printStack(int n) const 601{ 602 Node* node; 603 uint64_t r_index; 604 int count = 0; 605 606 DPRINTF(StackDist, "Printing last %d entries in tree\n", n); 607 608 // Walk through leaf layer to display the last n nodes 609 for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend()); 610 ++it, ++count) { 611 node = it->second; 612 r_index = node->nodeIndex; 613 614 // Lookup aiMap using the index returned by the leaf iterator 615 for (auto ai = aiMap.rbegin(); ai != aiMap.rend(); ++ai) { 616 if (ai->second == r_index) { 617 DPRINTF(StackDist,"Tree leaves, Rightmost-[%d] = %#lx\n", 618 count, ai->first); 619 break; 620 } 621 } 622 } 623 624 DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth()); 625 626 if (verifyStack) { 627 DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n); 628 count = 0; 629 for (auto a = stack.rbegin(); (count < n) && (a != stack.rend()); 630 ++a, ++count) { 631 DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a); 632 } 633 } 634}
| 95// The updateSum method is a recursive function which updates 96// the node sums till the root. It also deletes the nodes that 97// are not used anymore. 98uint64_t 99StackDistCalc::updateSum(Node* node, bool from_left, 100 uint64_t sum_from_below, uint64_t level, 101 uint64_t stack_dist, bool discard_node) 102{ 103 ++level; 104 105 // Make a copy of the node variables and work on them 106 // as a node may be deleted by this function 107 uint64_t node_sum_l = node->sumLeft; 108 uint64_t node_sum_r = node->sumRight; 109 bool node_left = node->isLeftNode; 110 bool node_discard_left = node->discardLeft; 111 bool node_discard_right = node->discardRight; 112 uint64_t node_n_index = node->nodeIndex; 113 Node* node_parent_ptr = node->parent; 114 115 // For verification 116 if (verifyStack) { 117 // This sanity check makes sure that the left_sum and 118 // right_sum of the node is not greater than the 119 // maximum possible value given by the leaves below it 120 // for example a node in layer 3 (tree[3]) can at most 121 // have 8 leaves (4 to the left and 4 to the right) 122 // thus left_sum and right_sum should be <= 4 123 panic_if(node_sum_l > (1 << (level - 1)), 124 "Error in sum left of level %ul, node index %ull, " 125 "Sum = %ull \n", level, node_n_index, node_sum_l); 126 127 panic_if(node_sum_r > (1 << (level - 1)), 128 "Error in sum right of level %ul, node index %ull, " 129 "Sum = %ull \n", level, node_n_index, node_sum_r); 130 } 131 132 // Update the left sum or the right sum depending on the 133 // from_left flag. Variable stack_dist is updated only 134 // when arriving from Left. 135 if (from_left) { 136 // update sumLeft 137 node_sum_l = sum_from_below; 138 stack_dist += node_sum_r; 139 } else { 140 // update sum_r 141 node_sum_r = sum_from_below; 142 } 143 144 // sum_from_below == 0 can be a leaf discard operation 145 if (discard_node && !sum_from_below) { 146 if (from_left) 147 node_discard_left = true; 148 else 149 node_discard_right = true; 150 } 151 152 // Update the node variables with new values 153 node->nodeIndex = node_n_index; 154 node->sumLeft = node_sum_l; 155 node->sumRight = node_sum_r; 156 node->isLeftNode = node_left; 157 node->discardLeft = node_discard_left; 158 node->discardRight = node_discard_right; 159 160 // Delete the node if it is not required anymore 161 if (node_discard_left && node_discard_right && 162 discard_node && node_parent_ptr && !sum_from_below) { 163 delete node; 164 tree[level].erase(node_n_index); 165 discard_node = true; 166 } else { 167 // propogate discard_node as false upwards if the 168 // above conditions are not met. 169 discard_node = false; 170 } 171 172 // Recursively call the updateSum operation till the 173 // root node is reached 174 if (node_parent_ptr) { 175 stack_dist = updateSum(node_parent_ptr, node_left, 176 node_sum_l + node_sum_r, 177 level, stack_dist, discard_node); 178 } 179 180 return stack_dist; 181} 182 183// This function is called by the calcStackDistAndUpdate function 184// If is_new_leaf is true then a new leaf is added otherwise a leaf 185// removed from the tree. In both cases the tree is updated using 186// the updateSum operation. 187uint64_t 188StackDistCalc::updateSumsLeavesToRoot(Node* node, bool is_new_leaf) 189{ 190 uint64_t level = 0; 191 uint64_t stack_dist = 0; 192 193 if (is_new_leaf) { 194 node->sumLeft = 1; 195 updateSum(node->parent, 196 node->isLeftNode, node->sumLeft, 197 level, 0, false); 198 199 stack_dist = Infinity; 200 } else { 201 node->sumLeft = 0; 202 stack_dist = updateSum(node->parent, 203 node->isLeftNode, 0, 204 level, stack_dist, true); 205 } 206 207 return stack_dist; 208} 209 210// This method is a recursive function which calculates 211// the node sums till the root. 212uint64_t 213StackDistCalc::getSum(Node* node, bool from_left, uint64_t sum_from_below, 214 uint64_t stack_dist, uint64_t level) const 215{ 216 ++level; 217 // Variable stack_dist is updated only 218 // when arriving from Left. 219 if(from_left) { 220 stack_dist += node->sumRight; 221 } 222 223 // Recursively call the getSum operation till the 224 // root node is reached 225 if(node->parent) { 226 stack_dist = getSum(node->parent, node->isLeftNode, 227 node->sumLeft + node->sumRight, 228 stack_dist, level); 229 } 230 231 return stack_dist; 232} 233 234// This function is called by the calcStackDistance function 235uint64_t 236StackDistCalc::getSumsLeavesToRoot(Node* node) const 237{ 238 return getSum(node->parent, node->isLeftNode, 0, 0, 0); 239} 240 241// Update tree is a tree balancing operation which maintains 242// the binary tree structure. This method is called whenever 243// index%2 == 0 (i.e. every alternate cycle) 244// The two main operation are : 245// OP1. moving the root node one layer up if index counter 246// crosses power of 2 247// OP2. Addition of intermediate nodes as and when required 248// and linking them to their parents in the layer above. 249void 250StackDistCalc::updateTree() 251{ 252 uint64_t i; 253 254 if (isPowerOf2(index)) { 255 // OP1. moving the root node one layer up if index counter 256 // crosses power of 2 257 // If index counter crosses a power of 2, then add a 258 // new tree layer above and create a new Root node in it. 259 // After the root is created the old node 260 // in the layer below is updated to point to this 261 // newly created root node. The sum_l of this new root node 262 // becomes the sum_l + sum_r of the old node. 263 // 264 // After this root update operation a chain of intermediate 265 // nodes is created from root layer to tree[1](one layer 266 // above the leaf layer) 267 268 // Create a new root node 269 Node* newRootNode = new Node(); 270 271 // Update its sum_l as the sum_l+sum_r from below 272 newRootNode->sumLeft = tree[getTreeDepth()][0]->sumRight + 273 tree[getTreeDepth()][0]->sumLeft; 274 // Update its discard left flag if the node below has 275 // has both discardLeft and discardRight set. 276 newRootNode->discardLeft = tree[getTreeDepth()][0]->discardLeft && 277 tree[getTreeDepth()][0]->discardRight; 278 279 // Map type variable, representing a layer in the tree 280 IndexNodeMap treeLevel; 281 // Add a new layer to the tree 282 tree.push_back(treeLevel); 283 nextIndex.push_back(1); 284 tree[getTreeDepth()][newRootNode->nodeIndex] = newRootNode; 285 286 // Update the parent pointer at lower layer to 287 // point to newly created root node 288 tree[getTreeDepth() - 1][0]->parent = tree[getTreeDepth()][0]; 289 290 // Add intermediate nodes from root till bottom (one layer above the 291 // leaf layer) 292 for (i = getTreeDepth() - 1; i >= 1; --i) { 293 Node* newINode = new Node(); 294 // newNode is left or right child depending on the number of nodes 295 // in that layer 296 if (nextIndex[i] % 2 == 0) { 297 newINode->isLeftNode = true; 298 } else { 299 newINode->isLeftNode = false; 300 } 301 302 newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; 303 newINode->nodeIndex = ++nextIndex[i] - 1; 304 tree[i][newINode->nodeIndex] = newINode; 305 } 306 } else { 307 // OP2. Addition of intermediate nodes as and when required 308 // and linking them to their parents in the layer above. 309 // 310 // At layer 1 a new INode is added whenever index%(2^1)==0 311 // (multiples of 2) 312 // 313 // At layer 2 a new INode is added whenever index%(2^2)==0 314 // (multiples of 4) 315 // 316 // At layer 3 a new INode is added whenever index%(2^3)==0 317 // (multiples of 8) 318 //... 319 // 320 // At layer N a new INode is added whenever index%(2^N)==0 321 // (multiples of 2^N) 322 for (i = getTreeDepth() - 1; i >= 1; --i) { 323 // Traverse each layer from root to leaves and add a new 324 // intermediate node if required. Link the parent_ptr of 325 // the new node to the parent in the above layer. 326 327 if ((index % (1 << i)) == 0) { 328 // Checks if current (index % 2^treeDepth) == 0 if true 329 // a new node at that layer is created 330 Node* newINode = new Node(); 331 332 // newNode is left or right child depending on the 333 // number of nodes in that layer. 334 if (nextIndex[i] % 2 == 0) { 335 newINode->isLeftNode = true; 336 } else { 337 newINode->isLeftNode = false; 338 } 339 340 // Pointing to its parent in the upper layer 341 newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; 342 newINode->nodeIndex = ++nextIndex[i] - 1; 343 tree[i][newINode->nodeIndex] = newINode; 344 } 345 } 346 } 347} 348 349// This function is called everytime to get the stack distance and add 350// a new node. A feature to mark an old node in the tree is 351// added. This is useful if it is required to see the reuse 352// pattern. For example, BackInvalidates from the lower level (Membus) 353// to L2, can be marked (isMarked flag of Node set to True). And then 354// later if this same address is accessed by L1, the value of the 355// isMarked flag would be True. This would give some insight on how 356// the BackInvalidates policy of the lower level affect the read/write 357// accesses in an application. 358std::pair< uint64_t, bool> 359StackDistCalc::calcStackDistAndUpdate(const Addr r_address, bool addNewNode) 360{ 361 Node* newLeafNode; 362 // Return index if the address was already present in stack 363 uint64_t r_index = index; 364 365 auto ai = aiMap.lower_bound(r_address); 366 367 // Default value of flag indicating as the left or right leaf 368 bool isLeft = true; 369 // Default value of isMarked flag for each node. 370 bool _mark = false; 371 // By default stackDistacne is treated as infinity 372 uint64_t stack_dist; 373 374 // Lookup aiMap by giving address as the key: 375 // If found take address and Lookup in tree 376 // Update tree from leaves by making B(found index) = 0 377 // Add sums to right till root while Updating them 378 // Stack Distance of that address sums to right 379 if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { 380 // key already exists 381 // save the index counter value when this address was 382 // encountered before and update it to the current index value 383 r_index = ai->second; 384 385 if (addNewNode) { 386 // Update aiMap aiMap(Address) = current index 387 ai->second = index; 388 } else { 389 aiMap.erase(r_address); 390 } 391 392 // Call update tree operation on the tree starting with 393 // the r_index value found above. This function would return 394 // the value of the stack distcance. 395 stack_dist = updateSumsLeavesToRoot(tree[0][r_index], false); 396 newLeafNode = tree[0][r_index]; 397 // determine if this node was marked earlier 398 _mark = newLeafNode->isMarked; 399 delete newLeafNode; 400 tree[0].erase(r_index); 401 } else { 402 if (addNewNode) { 403 // Update aiMap aiMap(Address) = current index 404 aiMap[r_address] = index; 405 } 406 // Update infinity bin count 407 // By default stackDistacne is treated as infinity 408 stack_dist = Infinity; 409 } 410 411 if (addNewNode) { 412 // If index%2 == 0 then update tree 413 if (index % 2 == 0) { 414 updateTree(); 415 } else { 416 // At odd values of index counter, a new right-type node is 417 // added to the leaf layer, else a left-type node is added 418 isLeft = false; 419 } 420 421 // Add new leaf node in the leaf layer (tree[0]) 422 // set n_index = current index 423 newLeafNode = new Node(); 424 ++nextIndex[0]; 425 newLeafNode->nodeIndex=index; 426 newLeafNode->isLeftNode=isLeft; 427 // Point the parent pointer to the intermediate node above 428 newLeafNode->parent = tree[1][nextIndex[1] - 1]; 429 tree[0][index] = newLeafNode; 430 // call an update operation which would update the tree after 431 // addition of this new leaf node. 432 updateSumsLeavesToRoot(tree[0][index], true); 433 434 // For verification 435 if (verifyStack) { 436 // This function checks the sanity of the tree to make sure the 437 // last node in the link of parent pointers is the root node. 438 // It takes a leaf node as an argument and traveses upwards till 439 // the root layer to check if the last parent is null 440 sanityCheckTree(tree[0][index]); 441 442 // Push the same element in debug stack, and check 443 uint64_t verify_stack_dist = verifyStackDist(r_address, true); 444 panic_if(verify_stack_dist != stack_dist, 445 "Expected stack-distance for address \ 446 %#lx is %#lx but found %#lx", 447 r_address, verify_stack_dist, stack_dist); 448 printStack(); 449 } 450 451 // The index counter is updated at the end of each transaction 452 // (unique or non-unique) 453 ++index; 454 } 455 456 return (std::make_pair(stack_dist, _mark)); 457} 458 459// This function is called everytime to get the stack distance 460// no new node is added. It can be used to mark a previous access 461// and inspect the value of the mark flag. 462std::pair< uint64_t, bool> 463StackDistCalc::calcStackDist(const Addr r_address, bool mark) 464{ 465 // Return index if the address was already present in stack 466 uint64_t r_index = index; 467 // Default value of isMarked flag for each node. 468 bool _mark = false; 469 470 auto ai = aiMap.lower_bound(r_address); 471 472 // By default stackDistacne is treated as infinity 473 uint64_t stack_dist = 0; 474 475 // Lookup aiMap by giving address as the key: 476 // If found take address and Lookup in tree 477 // Add sums to right till root 478 // Stack Distance of that address sums to right 479 if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { 480 // key already exists 481 // save the index counter value when this address was 482 // encountered before 483 r_index = ai->second; 484 485 // Get the value of mark flag if previously marked 486 _mark = tree[0][r_index]->isMarked; 487 // Mark the leaf node if required 488 tree[0][r_index]->isMarked = mark; 489 490 // Call get sums operation on the tree starting with 491 // the r_index value found above. This function would return 492 // the value of the stack distcance. 493 stack_dist = getSumsLeavesToRoot(tree[0][r_index]); 494 } else { 495 // Update infinity bin count 496 // By default stackDistacne is treated as infinity 497 stack_dist = Infinity; 498 } 499 500 // For verification 501 if (verifyStack) { 502 // Calculate the SD of the same address in the debug stack 503 uint64_t verify_stack_dist = verifyStackDist(r_address); 504 panic_if(verify_stack_dist != stack_dist, 505 "Expected stack-distance for address \ 506 %#lx is %#lx but found %#lx", 507 r_address, verify_stack_dist, stack_dist); 508 509 printStack(); 510 } 511 512 return std::make_pair(stack_dist, _mark); 513} 514 515// For verification 516// Simple sanity check for the tree 517void 518StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const 519{ 520 const Node* next_up = node->parent; 521 522 for (uint64_t i = level + 1; i < getTreeDepth() - level; ++i) { 523 next_up = next_up->parent; 524 panic_if(!next_up, "Sanity check failed for node %ull \n", 525 node->nodeIndex); 526 } 527 528 // At the root layer the parent_ptr should be null 529 panic_if(next_up->parent, "Sanity check failed for node %ull \n", 530 node->nodeIndex); 531} 532 533// This method can be called to compute the stack distance in a naive 534// way It can be used to verify the functionality of the stack 535// distance calculator. It uses std::vector to compute the stack 536// distance using a naive stack. 537uint64_t 538StackDistCalc::verifyStackDist(const Addr r_address, bool update_stack) 539{ 540 bool found = false; 541 uint64_t stack_dist = 0; 542 auto a = stack.rbegin(); 543 544 for (; a != stack.rend(); ++a) { 545 if (*a == r_address) { 546 found = true; 547 break; 548 } else { 549 ++stack_dist; 550 } 551 } 552 553 if (found) { 554 ++a; 555 if (update_stack) 556 stack.erase(a.base()); 557 } else { 558 stack_dist = Infinity; 559 } 560 561 if (update_stack) 562 stack.push_back(r_address); 563 564 return stack_dist; 565} 566 567// This method is useful to print top n entities in the stack. 568void 569StackDistCalc::printStack(int n) const 570{ 571 Node* node; 572 uint64_t r_index; 573 int count = 0; 574 575 DPRINTF(StackDist, "Printing last %d entries in tree\n", n); 576 577 // Walk through leaf layer to display the last n nodes 578 for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend()); 579 ++it, ++count) { 580 node = it->second; 581 r_index = node->nodeIndex; 582 583 // Lookup aiMap using the index returned by the leaf iterator 584 for (auto ai = aiMap.rbegin(); ai != aiMap.rend(); ++ai) { 585 if (ai->second == r_index) { 586 DPRINTF(StackDist,"Tree leaves, Rightmost-[%d] = %#lx\n", 587 count, ai->first); 588 break; 589 } 590 } 591 } 592 593 DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth()); 594 595 if (verifyStack) { 596 DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n); 597 count = 0; 598 for (auto a = stack.rbegin(); (count < n) && (a != stack.rend()); 599 ++a, ++count) { 600 DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a); 601 } 602 } 603}
|