stack_dist_calc.cc (10614:da37aec3ed1a) stack_dist_calc.cc (10995:a114e2712642)
1/*
1/*
2 * Copyright (c) 2014 ARM Limited
2 * Copyright (c) 2014-2015 ARM Limited
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
40#include "mem/stack_dist_calc.hh"
41
42#include "base/chunk_generator.hh"
40#include "base/intmath.hh"
41#include "base/trace.hh"
42#include "debug/StackDist.hh"
43#include "base/intmath.hh"
44#include "base/trace.hh"
45#include "debug/StackDist.hh"
43#include "mem/stack_dist_calc.hh"
44
46
45StackDistCalc::StackDistCalc(const StackDistCalcParams* p) :
46 SimObject(p), index(0), verifyStack(p->verify),
47 disableLinearHists(p->disable_linear_hists),
48 disableLogHists(p->disable_log_hists)
47StackDistCalc::StackDistCalc(bool verify_stack)
48 : index(0),
49 verifyStack(verify_stack)
49{
50 // Instantiate a new root and leaf layer
51 // Map type variable, representing a layer in the tree
52 IndexNodeMap tree_level;
53
54 // Initialize tree count for leaves
55 nextIndex.push_back(0);
56
57 // Add the initial leaf layer to the tree
58 tree.push_back(tree_level);
59
60 // Create a root node. Node type variable in the topmost layer
61 Node* root_node = new Node();
62
63 // Initialize tree count for root
64 nextIndex.push_back(1);
65
66 // Add the empty root layer to the tree
67 tree.push_back(tree_level);
68
69 // Add the initial root to the tree
70 tree[1][root_node->nodeIndex] = root_node;
71}
72
73StackDistCalc::~StackDistCalc()
74{
75 // Walk through each layer and destroy the nodes
76 for (auto& layer : tree) {
77 for (auto& index_node : layer) {
78 // each map entry contains an index and a node
79 delete index_node.second;
80 }
81 // Clear each layer in the tree
82 layer.clear();
83 }
84
85 // Clear the tree
86 tree.clear();
87 aiMap.clear();
88 nextIndex.clear();
89
90 // For verification
91 stack.clear();
92}
93
50{
51 // Instantiate a new root and leaf layer
52 // Map type variable, representing a layer in the tree
53 IndexNodeMap tree_level;
54
55 // Initialize tree count for leaves
56 nextIndex.push_back(0);
57
58 // Add the initial leaf layer to the tree
59 tree.push_back(tree_level);
60
61 // Create a root node. Node type variable in the topmost layer
62 Node* root_node = new Node();
63
64 // Initialize tree count for root
65 nextIndex.push_back(1);
66
67 // Add the empty root layer to the tree
68 tree.push_back(tree_level);
69
70 // Add the initial root to the tree
71 tree[1][root_node->nodeIndex] = root_node;
72}
73
74StackDistCalc::~StackDistCalc()
75{
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;
81 }
82 // Clear each layer in the tree
83 layer.clear();
84 }
85
86 // Clear the tree
87 tree.clear();
88 aiMap.clear();
89 nextIndex.clear();
90
91 // For verification
92 stack.clear();
93}
94
94void
95StackDistCalc::update(const MemCmd& cmd, Addr addr)
96{
97 // only capturing read and write requests (which allocate in the
98 // cache)
99 if (cmd.isRead() || cmd.isWrite()) {
100 auto returnType = calcStackDistAndUpdate(addr);
101
102 uint64_t stackDist = returnType.first;
103
104 if (stackDist != Infinity) {
105 // Sample the stack distance of the address in linear bins
106 if (!disableLinearHists) {
107 if (cmd.isRead())
108 readLinearHist.sample(stackDist);
109 else
110 writeLinearHist.sample(stackDist);
111 }
112
113 if (!disableLogHists) {
114 int stackDistLog2 = stackDist == 0 ? 1 : floorLog2(stackDist);
115
116 // Sample the stack distance of the address in log bins
117 if (cmd.isRead())
118 readLogHist.sample(stackDistLog2);
119 else
120 writeLogHist.sample(stackDistLog2);
121 }
122 }
123 }
124}
125
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}
635
636void
637StackDistCalc::regStats()
638{
639 using namespace Stats;
640
641 readLinearHist
642 .init(params()->linear_hist_bins)
643 .name(name() + ".readLinearHist")
644 .desc("Reads linear distribution")
645 .flags(disableLinearHists ? nozero : pdf);
646
647 readLogHist
648 .init(params()->log_hist_bins)
649 .name(name() + ".readLogHist")
650 .desc("Reads logarithmic distribution")
651 .flags(disableLogHists ? nozero : pdf);
652
653 writeLinearHist
654 .init(params()->linear_hist_bins)
655 .name(name() + ".writeLinearHist")
656 .desc("Writes linear distribution")
657 .flags(disableLinearHists ? nozero : pdf);
658
659 writeLogHist
660 .init(params()->log_hist_bins)
661 .name(name() + ".writeLogHist")
662 .desc("Writes logarithmic distribution")
663 .flags(disableLogHists ? nozero : pdf);
664}
665
666StackDistCalc*
667StackDistCalcParams::create()
668{
669 return new StackDistCalc(this);
670}