/* * Copyright (c) 2014-2015 ARM Limited * All rights reserved * * The license below extends only to copyright in the software and shall * not be construed as granting a license to any other intellectual * property including but not limited to intellectual property relating * to a hardware implementation of the functionality of the software * licensed hereunder. You may use the software subject to the license * terms below provided that you ensure that this notice is replicated * unmodified and in its entirety in all distributions of the software, * modified or unmodified, in source code or in binary form. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer; * redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution; * neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * Authors: Kanishk Sugand */ #include "mem/stack_dist_calc.hh" #include "base/chunk_generator.hh" #include "base/intmath.hh" #include "base/trace.hh" #include "debug/StackDist.hh" StackDistCalc::StackDistCalc(bool verify_stack) : index(0), verifyStack(verify_stack) { // Instantiate a new root and leaf layer // Map type variable, representing a layer in the tree IndexNodeMap tree_level; // Initialize tree count for leaves nextIndex.push_back(0); // Add the initial leaf layer to the tree tree.push_back(tree_level); // Create a root node. Node type variable in the topmost layer Node* root_node = new Node(); // Initialize tree count for root nextIndex.push_back(1); // Add the empty root layer to the tree tree.push_back(tree_level); // Add the initial root to the tree tree[1][root_node->nodeIndex] = root_node; } StackDistCalc::~StackDistCalc() { // Walk through each layer and destroy the nodes for (auto& layer : tree) { for (auto& index_node : layer) { // each map entry contains an index and a node delete index_node.second; } // Clear each layer in the tree layer.clear(); } // Clear the tree tree.clear(); aiMap.clear(); nextIndex.clear(); // For verification stack.clear(); } // The updateSum method is a recursive function which updates // the node sums till the root. It also deletes the nodes that // are not used anymore. uint64_t StackDistCalc::updateSum(Node* node, bool from_left, uint64_t sum_from_below, uint64_t level, uint64_t stack_dist, bool discard_node) { ++level; // Make a copy of the node variables and work on them // as a node may be deleted by this function uint64_t node_sum_l = node->sumLeft; uint64_t node_sum_r = node->sumRight; bool node_left = node->isLeftNode; bool node_discard_left = node->discardLeft; bool node_discard_right = node->discardRight; uint64_t node_n_index = node->nodeIndex; Node* node_parent_ptr = node->parent; // For verification if (verifyStack) { // This sanity check makes sure that the left_sum and // right_sum of the node is not greater than the // maximum possible value given by the leaves below it // for example a node in layer 3 (tree[3]) can at most // have 8 leaves (4 to the left and 4 to the right) // thus left_sum and right_sum should be <= 4 panic_if(node_sum_l > (1 << (level - 1)), "Error in sum left of level %ul, node index %ull, " "Sum = %ull \n", level, node_n_index, node_sum_l); panic_if(node_sum_r > (1 << (level - 1)), "Error in sum right of level %ul, node index %ull, " "Sum = %ull \n", level, node_n_index, node_sum_r); } // Update the left sum or the right sum depending on the // from_left flag. Variable stack_dist is updated only // when arriving from Left. if (from_left) { // update sumLeft node_sum_l = sum_from_below; stack_dist += node_sum_r; } else { // update sum_r node_sum_r = sum_from_below; } // sum_from_below == 0 can be a leaf discard operation if (discard_node && !sum_from_below) { if (from_left) node_discard_left = true; else node_discard_right = true; } // Update the node variables with new values node->nodeIndex = node_n_index; node->sumLeft = node_sum_l; node->sumRight = node_sum_r; node->isLeftNode = node_left; node->discardLeft = node_discard_left; node->discardRight = node_discard_right; // Delete the node if it is not required anymore if (node_discard_left && node_discard_right && discard_node && node_parent_ptr && !sum_from_below) { delete node; tree[level].erase(node_n_index); discard_node = true; } else { // propogate discard_node as false upwards if the // above conditions are not met. discard_node = false; } // Recursively call the updateSum operation till the // root node is reached if (node_parent_ptr) { stack_dist = updateSum(node_parent_ptr, node_left, node_sum_l + node_sum_r, level, stack_dist, discard_node); } return stack_dist; } // This function is called by the calcStackDistAndUpdate function // If is_new_leaf is true then a new leaf is added otherwise a leaf // removed from the tree. In both cases the tree is updated using // the updateSum operation. uint64_t StackDistCalc::updateSumsLeavesToRoot(Node* node, bool is_new_leaf) { uint64_t level = 0; uint64_t stack_dist = 0; if (is_new_leaf) { node->sumLeft = 1; updateSum(node->parent, node->isLeftNode, node->sumLeft, level, 0, false); stack_dist = Infinity; } else { node->sumLeft = 0; stack_dist = updateSum(node->parent, node->isLeftNode, 0, level, stack_dist, true); } return stack_dist; } // This method is a recursive function which calculates // the node sums till the root. uint64_t StackDistCalc::getSum(Node* node, bool from_left, uint64_t sum_from_below, uint64_t stack_dist, uint64_t level) const { ++level; // Variable stack_dist is updated only // when arriving from Left. if (from_left) { stack_dist += node->sumRight; } // Recursively call the getSum operation till the // root node is reached if (node->parent) { stack_dist = getSum(node->parent, node->isLeftNode, node->sumLeft + node->sumRight, stack_dist, level); } return stack_dist; } // This function is called by the calcStackDistance function uint64_t StackDistCalc::getSumsLeavesToRoot(Node* node) const { return getSum(node->parent, node->isLeftNode, 0, 0, 0); } // Update tree is a tree balancing operation which maintains // the binary tree structure. This method is called whenever // index%2 == 0 (i.e. every alternate cycle) // The two main operation are : // OP1. moving the root node one layer up if index counter // crosses power of 2 // OP2. Addition of intermediate nodes as and when required // and linking them to their parents in the layer above. void StackDistCalc::updateTree() { uint64_t i; if (isPowerOf2(index)) { // OP1. moving the root node one layer up if index counter // crosses power of 2 // If index counter crosses a power of 2, then add a // new tree layer above and create a new Root node in it. // After the root is created the old node // in the layer below is updated to point to this // newly created root node. The sum_l of this new root node // becomes the sum_l + sum_r of the old node. // // After this root update operation a chain of intermediate // nodes is created from root layer to tree[1](one layer // above the leaf layer) // Create a new root node Node* newRootNode = new Node(); // Update its sum_l as the sum_l+sum_r from below newRootNode->sumLeft = tree[getTreeDepth()][0]->sumRight + tree[getTreeDepth()][0]->sumLeft; // Update its discard left flag if the node below has // has both discardLeft and discardRight set. newRootNode->discardLeft = tree[getTreeDepth()][0]->discardLeft && tree[getTreeDepth()][0]->discardRight; // Map type variable, representing a layer in the tree IndexNodeMap treeLevel; // Add a new layer to the tree tree.push_back(treeLevel); nextIndex.push_back(1); tree[getTreeDepth()][newRootNode->nodeIndex] = newRootNode; // Update the parent pointer at lower layer to // point to newly created root node tree[getTreeDepth() - 1][0]->parent = tree[getTreeDepth()][0]; // Add intermediate nodes from root till bottom (one layer above the // leaf layer) for (i = getTreeDepth() - 1; i >= 1; --i) { Node* newINode = new Node(); // newNode is left or right child depending on the number of nodes // in that layer if (nextIndex[i] % 2 == 0) { newINode->isLeftNode = true; } else { newINode->isLeftNode = false; } newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; newINode->nodeIndex = ++nextIndex[i] - 1; tree[i][newINode->nodeIndex] = newINode; } } else { // OP2. Addition of intermediate nodes as and when required // and linking them to their parents in the layer above. // // At layer 1 a new INode is added whenever index%(2^1)==0 // (multiples of 2) // // At layer 2 a new INode is added whenever index%(2^2)==0 // (multiples of 4) // // At layer 3 a new INode is added whenever index%(2^3)==0 // (multiples of 8) //... // // At layer N a new INode is added whenever index%(2^N)==0 // (multiples of 2^N) for (i = getTreeDepth() - 1; i >= 1; --i) { // Traverse each layer from root to leaves and add a new // intermediate node if required. Link the parent_ptr of // the new node to the parent in the above layer. if ((index % (1 << i)) == 0) { // Checks if current (index % 2^treeDepth) == 0 if true // a new node at that layer is created Node* newINode = new Node(); // newNode is left or right child depending on the // number of nodes in that layer. if (nextIndex[i] % 2 == 0) { newINode->isLeftNode = true; } else { newINode->isLeftNode = false; } // Pointing to its parent in the upper layer newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; newINode->nodeIndex = ++nextIndex[i] - 1; tree[i][newINode->nodeIndex] = newINode; } } } } // This function is called everytime to get the stack distance and add // a new node. A feature to mark an old node in the tree is // added. This is useful if it is required to see the reuse // pattern. For example, BackInvalidates from the lower level (Membus) // to L2, can be marked (isMarked flag of Node set to True). And then // later if this same address is accessed by L1, the value of the // isMarked flag would be True. This would give some insight on how // the BackInvalidates policy of the lower level affect the read/write // accesses in an application. std::pair< uint64_t, bool> StackDistCalc::calcStackDistAndUpdate(const Addr r_address, bool addNewNode) { Node* newLeafNode; auto ai = aiMap.lower_bound(r_address); // Default value of flag indicating as the left or right leaf bool isLeft = true; // Default value of isMarked flag for each node. bool _mark = false; // By default stackDistacne is treated as infinity uint64_t stack_dist; // Lookup aiMap by giving address as the key: // If found take address and Lookup in tree // Update tree from leaves by making B(found index) = 0 // Add sums to right till root while Updating them // Stack Distance of that address sums to right if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { // key already exists // save the index counter value when this address was // encountered before and update it to the current index value uint64_t r_index = ai->second; if (addNewNode) { // Update aiMap aiMap(Address) = current index ai->second = index; } else { aiMap.erase(r_address); } // Call update tree operation on the tree starting with // the r_index value found above. This function would return // the value of the stack distcance. stack_dist = updateSumsLeavesToRoot(tree[0][r_index], false); newLeafNode = tree[0][r_index]; // determine if this node was marked earlier _mark = newLeafNode->isMarked; delete newLeafNode; tree[0].erase(r_index); } else { if (addNewNode) { // Update aiMap aiMap(Address) = current index aiMap[r_address] = index; } // Update infinity bin count // By default stackDistacne is treated as infinity stack_dist = Infinity; } if (addNewNode) { // If index%2 == 0 then update tree if (index % 2 == 0) { updateTree(); } else { // At odd values of index counter, a new right-type node is // added to the leaf layer, else a left-type node is added isLeft = false; } // Add new leaf node in the leaf layer (tree[0]) // set n_index = current index newLeafNode = new Node(); ++nextIndex[0]; newLeafNode->nodeIndex=index; newLeafNode->isLeftNode=isLeft; // Point the parent pointer to the intermediate node above newLeafNode->parent = tree[1][nextIndex[1] - 1]; tree[0][index] = newLeafNode; // call an update operation which would update the tree after // addition of this new leaf node. updateSumsLeavesToRoot(tree[0][index], true); // For verification if (verifyStack) { // This function checks the sanity of the tree to make sure the // last node in the link of parent pointers is the root node. // It takes a leaf node as an argument and traveses upwards till // the root layer to check if the last parent is null sanityCheckTree(tree[0][index]); // Push the same element in debug stack, and check uint64_t verify_stack_dist = verifyStackDist(r_address, true); panic_if(verify_stack_dist != stack_dist, "Expected stack-distance for address \ %#lx is %#lx but found %#lx", r_address, verify_stack_dist, stack_dist); printStack(); } // The index counter is updated at the end of each transaction // (unique or non-unique) ++index; } return (std::make_pair(stack_dist, _mark)); } // This function is called everytime to get the stack distance // no new node is added. It can be used to mark a previous access // and inspect the value of the mark flag. std::pair< uint64_t, bool> StackDistCalc::calcStackDist(const Addr r_address, bool mark) { // Default value of isMarked flag for each node. bool _mark = false; auto ai = aiMap.lower_bound(r_address); // By default stackDistacne is treated as infinity uint64_t stack_dist = 0; // Lookup aiMap by giving address as the key: // If found take address and Lookup in tree // Add sums to right till root // Stack Distance of that address sums to right if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { // key already exists // save the index counter value when this address was // encountered before uint64_t r_index = ai->second; // Get the value of mark flag if previously marked _mark = tree[0][r_index]->isMarked; // Mark the leaf node if required tree[0][r_index]->isMarked = mark; // Call get sums operation on the tree starting with // the r_index value found above. This function would return // the value of the stack distcance. stack_dist = getSumsLeavesToRoot(tree[0][r_index]); } else { // Update infinity bin count // By default stackDistacne is treated as infinity stack_dist = Infinity; } // For verification if (verifyStack) { // Calculate the SD of the same address in the debug stack uint64_t verify_stack_dist = verifyStackDist(r_address); panic_if(verify_stack_dist != stack_dist, "Expected stack-distance for address \ %#lx is %#lx but found %#lx", r_address, verify_stack_dist, stack_dist); printStack(); } return std::make_pair(stack_dist, _mark); } // For verification // Simple sanity check for the tree void StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const { const Node* next_up = node->parent; for (uint64_t i = level + 1; i < getTreeDepth() - level; ++i) { next_up = next_up->parent; panic_if(!next_up, "Sanity check failed for node %ull \n", node->nodeIndex); } // At the root layer the parent_ptr should be null panic_if(next_up->parent, "Sanity check failed for node %ull \n", node->nodeIndex); } // This method can be called to compute the stack distance in a naive // way It can be used to verify the functionality of the stack // distance calculator. It uses std::vector to compute the stack // distance using a naive stack. uint64_t StackDistCalc::verifyStackDist(const Addr r_address, bool update_stack) { bool found = false; uint64_t stack_dist = 0; auto a = stack.rbegin(); for (; a != stack.rend(); ++a) { if (*a == r_address) { found = true; break; } else { ++stack_dist; } } if (found) { ++a; if (update_stack) stack.erase(a.base()); } else { stack_dist = Infinity; } if (update_stack) stack.push_back(r_address); return stack_dist; } // This method is useful to print top n entities in the stack. void StackDistCalc::printStack(int n) const { Node* node; int count = 0; DPRINTF(StackDist, "Printing last %d entries in tree\n", n); // Walk through leaf layer to display the last n nodes for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend()); ++it, ++count) { node = it->second; uint64_t r_index = node->nodeIndex; // Lookup aiMap using the index returned by the leaf iterator for (auto ai = aiMap.rbegin(); ai != aiMap.rend(); ++ai) { if (ai->second == r_index) { DPRINTF(StackDist,"Tree leaves, Rightmost-[%d] = %#lx\n", count, ai->first); break; } } } DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth()); if (verifyStack) { DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n); count = 0; for (auto a = stack.rbegin(); (count < n) && (a != stack.rend()); ++a, ++count) { DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a); } } }