blob: 6912486782838d802d7b8fedc27d62cd4f8969ae [file] [log] [blame]
/*
* 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.
*/
#include "mem/stack_dist_calc.hh"
#include "base/chunk_generator.hh"
#include "base/intmath.hh"
#include "base/logging.hh"
#include "base/trace.hh"
#include "debug/StackDist.hh"
namespace gem5
{
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);
}
}
}
} // namespace gem5