2 * Copyright (c) 2014-2015 ARM Limited
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.
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.
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.
37 * Authors: Kanishk Sugand
40 #include "mem/stack_dist_calc.hh"
42 #include "base/chunk_generator.hh"
43 #include "base/intmath.hh"
44 #include "base/trace.hh"
45 #include "debug/StackDist.hh"
47 StackDistCalc::StackDistCalc(bool verify_stack
)
49 verifyStack(verify_stack
)
51 // Instantiate a new root and leaf layer
52 // Map type variable, representing a layer in the tree
53 IndexNodeMap tree_level
;
55 // Initialize tree count for leaves
56 nextIndex
.push_back(0);
58 // Add the initial leaf layer to the tree
59 tree
.push_back(tree_level
);
61 // Create a root node. Node type variable in the topmost layer
62 Node
* root_node
= new Node();
64 // Initialize tree count for root
65 nextIndex
.push_back(1);
67 // Add the empty root layer to the tree
68 tree
.push_back(tree_level
);
70 // Add the initial root to the tree
71 tree
[1][root_node
->nodeIndex
] = root_node
;
74 StackDistCalc::~StackDistCalc()
76 // Walk through each layer and destroy the nodes
77 for (auto& layer
: tree
) {
78 for (auto& index_node
: layer
) {
79 // each map entry contains an index and a node
80 delete index_node
.second
;
82 // Clear each layer in the tree
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.
99 StackDistCalc::updateSum(Node
* node
, bool from_left
,
100 uint64_t sum_from_below
, uint64_t level
,
101 uint64_t stack_dist
, bool discard_node
)
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
;
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
);
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
);
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.
137 node_sum_l
= sum_from_below
;
138 stack_dist
+= node_sum_r
;
141 node_sum_r
= sum_from_below
;
144 // sum_from_below == 0 can be a leaf discard operation
145 if (discard_node
&& !sum_from_below
) {
147 node_discard_left
= true;
149 node_discard_right
= true;
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
;
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
) {
164 tree
[level
].erase(node_n_index
);
167 // propogate discard_node as false upwards if the
168 // above conditions are not met.
169 discard_node
= false;
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
);
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.
188 StackDistCalc::updateSumsLeavesToRoot(Node
* node
, bool is_new_leaf
)
191 uint64_t stack_dist
= 0;
195 updateSum(node
->parent
,
196 node
->isLeftNode
, node
->sumLeft
,
199 stack_dist
= Infinity
;
202 stack_dist
= updateSum(node
->parent
,
204 level
, stack_dist
, true);
210 // This method is a recursive function which calculates
211 // the node sums till the root.
213 StackDistCalc::getSum(Node
* node
, bool from_left
, uint64_t sum_from_below
,
214 uint64_t stack_dist
, uint64_t level
) const
217 // Variable stack_dist is updated only
218 // when arriving from Left.
220 stack_dist
+= node
->sumRight
;
223 // Recursively call the getSum operation till the
224 // root node is reached
226 stack_dist
= getSum(node
->parent
, node
->isLeftNode
,
227 node
->sumLeft
+ node
->sumRight
,
234 // This function is called by the calcStackDistance function
236 StackDistCalc::getSumsLeavesToRoot(Node
* node
) const
238 return getSum(node
->parent
, node
->isLeftNode
, 0, 0, 0);
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.
250 StackDistCalc::updateTree()
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.
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)
268 // Create a new root node
269 Node
* newRootNode
= new Node();
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
;
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
;
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];
290 // Add intermediate nodes from root till bottom (one layer above the
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
296 if (nextIndex
[i
] % 2 == 0) {
297 newINode
->isLeftNode
= true;
299 newINode
->isLeftNode
= false;
302 newINode
->parent
= tree
[i
+ 1][nextIndex
[i
+ 1] - 1];
303 newINode
->nodeIndex
= ++nextIndex
[i
] - 1;
304 tree
[i
][newINode
->nodeIndex
] = newINode
;
307 // OP2. Addition of intermediate nodes as and when required
308 // and linking them to their parents in the layer above.
310 // At layer 1 a new INode is added whenever index%(2^1)==0
313 // At layer 2 a new INode is added whenever index%(2^2)==0
316 // At layer 3 a new INode is added whenever index%(2^3)==0
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.
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();
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;
337 newINode
->isLeftNode
= false;
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
;
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.
358 std::pair
< uint64_t, bool>
359 StackDistCalc::calcStackDistAndUpdate(const Addr r_address
, bool addNewNode
)
363 auto ai
= aiMap
.lower_bound(r_address
);
365 // Default value of flag indicating as the left or right leaf
367 // Default value of isMarked flag for each node.
369 // By default stackDistacne is treated as infinity
372 // Lookup aiMap by giving address as the key:
373 // If found take address and Lookup in tree
374 // Update tree from leaves by making B(found index) = 0
375 // Add sums to right till root while Updating them
376 // Stack Distance of that address sums to right
377 if (ai
!= aiMap
.end() && !(aiMap
.key_comp()(r_address
, ai
->first
))) {
378 // key already exists
379 // save the index counter value when this address was
380 // encountered before and update it to the current index value
381 uint64_t r_index
= ai
->second
;
384 // Update aiMap aiMap(Address) = current index
387 aiMap
.erase(r_address
);
390 // Call update tree operation on the tree starting with
391 // the r_index value found above. This function would return
392 // the value of the stack distcance.
393 stack_dist
= updateSumsLeavesToRoot(tree
[0][r_index
], false);
394 newLeafNode
= tree
[0][r_index
];
395 // determine if this node was marked earlier
396 _mark
= newLeafNode
->isMarked
;
398 tree
[0].erase(r_index
);
401 // Update aiMap aiMap(Address) = current index
402 aiMap
[r_address
] = index
;
404 // Update infinity bin count
405 // By default stackDistacne is treated as infinity
406 stack_dist
= Infinity
;
410 // If index%2 == 0 then update tree
411 if (index
% 2 == 0) {
414 // At odd values of index counter, a new right-type node is
415 // added to the leaf layer, else a left-type node is added
419 // Add new leaf node in the leaf layer (tree[0])
420 // set n_index = current index
421 newLeafNode
= new Node();
423 newLeafNode
->nodeIndex
=index
;
424 newLeafNode
->isLeftNode
=isLeft
;
425 // Point the parent pointer to the intermediate node above
426 newLeafNode
->parent
= tree
[1][nextIndex
[1] - 1];
427 tree
[0][index
] = newLeafNode
;
428 // call an update operation which would update the tree after
429 // addition of this new leaf node.
430 updateSumsLeavesToRoot(tree
[0][index
], true);
434 // This function checks the sanity of the tree to make sure the
435 // last node in the link of parent pointers is the root node.
436 // It takes a leaf node as an argument and traveses upwards till
437 // the root layer to check if the last parent is null
438 sanityCheckTree(tree
[0][index
]);
440 // Push the same element in debug stack, and check
441 uint64_t verify_stack_dist
= verifyStackDist(r_address
, true);
442 panic_if(verify_stack_dist
!= stack_dist
,
443 "Expected stack-distance for address \
444 %#lx is %#lx but found %#lx",
445 r_address
, verify_stack_dist
, stack_dist
);
449 // The index counter is updated at the end of each transaction
450 // (unique or non-unique)
454 return (std::make_pair(stack_dist
, _mark
));
457 // This function is called everytime to get the stack distance
458 // no new node is added. It can be used to mark a previous access
459 // and inspect the value of the mark flag.
460 std::pair
< uint64_t, bool>
461 StackDistCalc::calcStackDist(const Addr r_address
, bool mark
)
463 // Default value of isMarked flag for each node.
466 auto ai
= aiMap
.lower_bound(r_address
);
468 // By default stackDistacne is treated as infinity
469 uint64_t stack_dist
= 0;
471 // Lookup aiMap by giving address as the key:
472 // If found take address and Lookup in tree
473 // Add sums to right till root
474 // Stack Distance of that address sums to right
475 if (ai
!= aiMap
.end() && !(aiMap
.key_comp()(r_address
, ai
->first
))) {
476 // key already exists
477 // save the index counter value when this address was
478 // encountered before
479 uint64_t r_index
= ai
->second
;
481 // Get the value of mark flag if previously marked
482 _mark
= tree
[0][r_index
]->isMarked
;
483 // Mark the leaf node if required
484 tree
[0][r_index
]->isMarked
= mark
;
486 // Call get sums operation on the tree starting with
487 // the r_index value found above. This function would return
488 // the value of the stack distcance.
489 stack_dist
= getSumsLeavesToRoot(tree
[0][r_index
]);
491 // Update infinity bin count
492 // By default stackDistacne is treated as infinity
493 stack_dist
= Infinity
;
498 // Calculate the SD of the same address in the debug stack
499 uint64_t verify_stack_dist
= verifyStackDist(r_address
);
500 panic_if(verify_stack_dist
!= stack_dist
,
501 "Expected stack-distance for address \
502 %#lx is %#lx but found %#lx",
503 r_address
, verify_stack_dist
, stack_dist
);
508 return std::make_pair(stack_dist
, _mark
);
512 // Simple sanity check for the tree
514 StackDistCalc::sanityCheckTree(const Node
* node
, uint64_t level
) const
516 const Node
* next_up
= node
->parent
;
518 for (uint64_t i
= level
+ 1; i
< getTreeDepth() - level
; ++i
) {
519 next_up
= next_up
->parent
;
520 panic_if(!next_up
, "Sanity check failed for node %ull \n",
524 // At the root layer the parent_ptr should be null
525 panic_if(next_up
->parent
, "Sanity check failed for node %ull \n",
529 // This method can be called to compute the stack distance in a naive
530 // way It can be used to verify the functionality of the stack
531 // distance calculator. It uses std::vector to compute the stack
532 // distance using a naive stack.
534 StackDistCalc::verifyStackDist(const Addr r_address
, bool update_stack
)
537 uint64_t stack_dist
= 0;
538 auto a
= stack
.rbegin();
540 for (; a
!= stack
.rend(); ++a
) {
541 if (*a
== r_address
) {
552 stack
.erase(a
.base());
554 stack_dist
= Infinity
;
558 stack
.push_back(r_address
);
563 // This method is useful to print top n entities in the stack.
565 StackDistCalc::printStack(int n
) const
570 DPRINTF(StackDist
, "Printing last %d entries in tree\n", n
);
572 // Walk through leaf layer to display the last n nodes
573 for (auto it
= tree
[0].rbegin(); (count
< n
) && (it
!= tree
[0].rend());
576 uint64_t r_index
= node
->nodeIndex
;
578 // Lookup aiMap using the index returned by the leaf iterator
579 for (auto ai
= aiMap
.rbegin(); ai
!= aiMap
.rend(); ++ai
) {
580 if (ai
->second
== r_index
) {
581 DPRINTF(StackDist
,"Tree leaves, Rightmost-[%d] = %#lx\n",
588 DPRINTF(StackDist
,"Tree depth = %#ld\n", getTreeDepth());
591 DPRINTF(StackDist
,"Printing Last %d entries in VerifStack \n", n
);
593 for (auto a
= stack
.rbegin(); (count
< n
) && (a
!= stack
.rend());
595 DPRINTF(StackDist
, "Verif Stack, Top-[%d] = %#lx\n", count
, *a
);