1/*
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
40#include "mem/stack_dist_calc.hh"
41
42#include "base/chunk_generator.hh"
43#include "base/intmath.hh"
44#include "base/trace.hh"
45#include "debug/StackDist.hh"
46
47StackDistCalc::StackDistCalc(bool verify_stack)
48 : index(0),
49 verifyStack(verify_stack)
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
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.
| 1/*
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
40#include "mem/stack_dist_calc.hh"
41
42#include "base/chunk_generator.hh"
43#include "base/intmath.hh"
44#include "base/trace.hh"
45#include "debug/StackDist.hh"
46
47StackDistCalc::StackDistCalc(bool verify_stack)
48 : index(0),
49 verifyStack(verify_stack)
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
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.
|
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
363 auto ai = aiMap.lower_bound(r_address);
364
365 // Default value of flag indicating as the left or right leaf
366 bool isLeft = true;
367 // Default value of isMarked flag for each node.
368 bool _mark = false;
369 // By default stackDistacne is treated as infinity
370 uint64_t stack_dist;
371
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;
382
383 if (addNewNode) {
384 // Update aiMap aiMap(Address) = current index
385 ai->second = index;
386 } else {
387 aiMap.erase(r_address);
388 }
389
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;
397 delete newLeafNode;
398 tree[0].erase(r_index);
399 } else {
400 if (addNewNode) {
401 // Update aiMap aiMap(Address) = current index
402 aiMap[r_address] = index;
403 }
404 // Update infinity bin count
405 // By default stackDistacne is treated as infinity
406 stack_dist = Infinity;
407 }
408
409 if (addNewNode) {
410 // If index%2 == 0 then update tree
411 if (index % 2 == 0) {
412 updateTree();
413 } else {
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
416 isLeft = false;
417 }
418
419 // Add new leaf node in the leaf layer (tree[0])
420 // set n_index = current index
421 newLeafNode = new Node();
422 ++nextIndex[0];
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);
431
432 // For verification
433 if (verifyStack) {
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]);
439
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);
446 printStack();
447 }
448
449 // The index counter is updated at the end of each transaction
450 // (unique or non-unique)
451 ++index;
452 }
453
454 return (std::make_pair(stack_dist, _mark));
455}
456
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.
460std::pair< uint64_t, bool>
461StackDistCalc::calcStackDist(const Addr r_address, bool mark)
462{
463 // Default value of isMarked flag for each node.
464 bool _mark = false;
465
466 auto ai = aiMap.lower_bound(r_address);
467
468 // By default stackDistacne is treated as infinity
469 uint64_t stack_dist = 0;
470
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;
480
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;
485
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]);
490 } else {
491 // Update infinity bin count
492 // By default stackDistacne is treated as infinity
493 stack_dist = Infinity;
494 }
495
496 // For verification
497 if (verifyStack) {
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);
504
505 printStack();
506 }
507
508 return std::make_pair(stack_dist, _mark);
509}
510
511// For verification
512// Simple sanity check for the tree
513void
514StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const
515{
516 const Node* next_up = node->parent;
517
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",
521 node->nodeIndex);
522 }
523
524 // At the root layer the parent_ptr should be null
525 panic_if(next_up->parent, "Sanity check failed for node %ull \n",
526 node->nodeIndex);
527}
528
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.
533uint64_t
534StackDistCalc::verifyStackDist(const Addr r_address, bool update_stack)
535{
536 bool found = false;
537 uint64_t stack_dist = 0;
538 auto a = stack.rbegin();
539
540 for (; a != stack.rend(); ++a) {
541 if (*a == r_address) {
542 found = true;
543 break;
544 } else {
545 ++stack_dist;
546 }
547 }
548
549 if (found) {
550 ++a;
551 if (update_stack)
552 stack.erase(a.base());
553 } else {
554 stack_dist = Infinity;
555 }
556
557 if (update_stack)
558 stack.push_back(r_address);
559
560 return stack_dist;
561}
562
563// This method is useful to print top n entities in the stack.
564void
565StackDistCalc::printStack(int n) const
566{
567 Node* node;
568 int count = 0;
569
570 DPRINTF(StackDist, "Printing last %d entries in tree\n", n);
571
572 // Walk through leaf layer to display the last n nodes
573 for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend());
574 ++it, ++count) {
575 node = it->second;
576 uint64_t r_index = node->nodeIndex;
577
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",
582 count, ai->first);
583 break;
584 }
585 }
586 }
587
588 DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth());
589
590 if (verifyStack) {
591 DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n);
592 count = 0;
593 for (auto a = stack.rbegin(); (count < n) && (a != stack.rend());
594 ++a, ++count) {
595 DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a);
596 }
597 }
598}
| 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
363 auto ai = aiMap.lower_bound(r_address);
364
365 // Default value of flag indicating as the left or right leaf
366 bool isLeft = true;
367 // Default value of isMarked flag for each node.
368 bool _mark = false;
369 // By default stackDistacne is treated as infinity
370 uint64_t stack_dist;
371
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;
382
383 if (addNewNode) {
384 // Update aiMap aiMap(Address) = current index
385 ai->second = index;
386 } else {
387 aiMap.erase(r_address);
388 }
389
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;
397 delete newLeafNode;
398 tree[0].erase(r_index);
399 } else {
400 if (addNewNode) {
401 // Update aiMap aiMap(Address) = current index
402 aiMap[r_address] = index;
403 }
404 // Update infinity bin count
405 // By default stackDistacne is treated as infinity
406 stack_dist = Infinity;
407 }
408
409 if (addNewNode) {
410 // If index%2 == 0 then update tree
411 if (index % 2 == 0) {
412 updateTree();
413 } else {
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
416 isLeft = false;
417 }
418
419 // Add new leaf node in the leaf layer (tree[0])
420 // set n_index = current index
421 newLeafNode = new Node();
422 ++nextIndex[0];
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);
431
432 // For verification
433 if (verifyStack) {
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]);
439
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);
446 printStack();
447 }
448
449 // The index counter is updated at the end of each transaction
450 // (unique or non-unique)
451 ++index;
452 }
453
454 return (std::make_pair(stack_dist, _mark));
455}
456
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.
460std::pair< uint64_t, bool>
461StackDistCalc::calcStackDist(const Addr r_address, bool mark)
462{
463 // Default value of isMarked flag for each node.
464 bool _mark = false;
465
466 auto ai = aiMap.lower_bound(r_address);
467
468 // By default stackDistacne is treated as infinity
469 uint64_t stack_dist = 0;
470
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;
480
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;
485
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]);
490 } else {
491 // Update infinity bin count
492 // By default stackDistacne is treated as infinity
493 stack_dist = Infinity;
494 }
495
496 // For verification
497 if (verifyStack) {
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);
504
505 printStack();
506 }
507
508 return std::make_pair(stack_dist, _mark);
509}
510
511// For verification
512// Simple sanity check for the tree
513void
514StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const
515{
516 const Node* next_up = node->parent;
517
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",
521 node->nodeIndex);
522 }
523
524 // At the root layer the parent_ptr should be null
525 panic_if(next_up->parent, "Sanity check failed for node %ull \n",
526 node->nodeIndex);
527}
528
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.
533uint64_t
534StackDistCalc::verifyStackDist(const Addr r_address, bool update_stack)
535{
536 bool found = false;
537 uint64_t stack_dist = 0;
538 auto a = stack.rbegin();
539
540 for (; a != stack.rend(); ++a) {
541 if (*a == r_address) {
542 found = true;
543 break;
544 } else {
545 ++stack_dist;
546 }
547 }
548
549 if (found) {
550 ++a;
551 if (update_stack)
552 stack.erase(a.base());
553 } else {
554 stack_dist = Infinity;
555 }
556
557 if (update_stack)
558 stack.push_back(r_address);
559
560 return stack_dist;
561}
562
563// This method is useful to print top n entities in the stack.
564void
565StackDistCalc::printStack(int n) const
566{
567 Node* node;
568 int count = 0;
569
570 DPRINTF(StackDist, "Printing last %d entries in tree\n", n);
571
572 // Walk through leaf layer to display the last n nodes
573 for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend());
574 ++it, ++count) {
575 node = it->second;
576 uint64_t r_index = node->nodeIndex;
577
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",
582 count, ai->first);
583 break;
584 }
585 }
586 }
587
588 DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth());
589
590 if (verifyStack) {
591 DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n);
592 count = 0;
593 for (auto a = stack.rbegin(); (count < n) && (a != stack.rend());
594 ++a, ++count) {
595 DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a);
596 }
597 }
598}
|