| /* | |
| * 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); | |
| } | |
| } | |
| } |