gem5  v21.1.0.2
address_manager.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017-2020 Advanced Micro Devices, Inc.
3  * All rights reserved.
4  *
5  * For use for simulation and test purposes only
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright notice,
11  * this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright notice,
14  * this list of conditions and the following disclaimer in the documentation
15  * and/or other materials provided with the distribution.
16  *
17  * 3. Neither the name of the copyright holder nor the names of its
18  * contributors may be used to endorse or promote products derived from this
19  * software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  */
33 
35 
36 #include <algorithm>
37 
38 #include "base/intmath.hh"
39 #include "base/logging.hh"
40 #include "base/random.hh"
41 #include "base/trace.hh"
42 
43 namespace gem5
44 {
45 
46 const int AddressManager::INVALID_VALUE = -1;
48 
49 AddressManager::AddressManager(int n_atomic_locs, int n_normal_locs_per_atomic)
50  : numAtomicLocs(n_atomic_locs),
51  numLocsPerAtomic(n_normal_locs_per_atomic)
52 {
53  assert(numAtomicLocs > 0 && numLocsPerAtomic > 0);
55 
56  // generate random address map
58  for (Location i = 0; i < numAtomicLocs + numNormalLocs; ++i) {
59  // all addresses are sizeof(Value) (i.e., 4-byte) aligned
60  randAddressMap[i] = (Addr)((i + 128) << floorLog2(sizeof(Value)));
61  }
62 
63  // randomly shuffle randAddressMap
64  std::random_shuffle(randAddressMap.begin(), randAddressMap.end());
65 
66  // initialize atomic locations
67  // first and last normal location per atomic location
68  Location first, last;
69  for (Location atomic_loc = 0; atomic_loc < numAtomicLocs; ++atomic_loc) {
70  first = numAtomicLocs + numLocsPerAtomic * atomic_loc;
71  last = first + numLocsPerAtomic - 1;
72  atomicStructs.push_back(new AtomicStruct(atomic_loc, first, last));
73  }
74 
75  // initialize log table
76  for (Location loc = 0; loc < numAtomicLocs + numNormalLocs; ++loc) {
77  logTable.push_back(new LastWriter());
78  }
79 }
80 
82 {
83  for (AtomicStruct* atomic_struct : atomicStructs)
84  delete atomic_struct;
85  for (LastWriter* lw : logTable)
86  delete lw;
87 }
88 
89 Addr
91 {
92  assert(loc < numAtomicLocs + numNormalLocs && loc >= 0);
93  return randAddressMap[loc];
94 }
95 
98 {
99  Location ret_atomic_loc = random() % numAtomicLocs;
100  atomicStructs[ret_atomic_loc]->startLocSelection();
101  return ret_atomic_loc;
102 }
103 
106 {
107  assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
108  return atomicStructs[atomic_loc]->getLoadLoc();
109 }
110 
113 {
114  assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
115  return atomicStructs[atomic_loc]->getStoreLoc();
116 }
117 
118 void
120 {
121  assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
122  atomicStructs[atomic_loc]->endLocSelection();
123 }
124 
125 void
127 {
128  assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
129  atomicStructs[atomic_loc]->releaseLoc(loc);
130 }
131 
132 std::string
134 {
135  return logTable[loc]->print();
136 }
137 
138 // ------------------- AtomicStruct --------------------------
140  Location loc_begin,
141  Location loc_end)
142 {
143  // the location range must have at least 1 location
144  assert(loc_begin <= loc_end);
145 
146  atomicLoc = atomic_loc;
147  arraySize = loc_end - loc_begin + 1;
148  locationBase = loc_begin;
149 
150  // allocate an array of arrray_size
151  locArray = new Location[arraySize];
152 
153  // initialize locArray & locProps
154  Location loc;
155  for (int offset = 0; offset < arraySize; ++offset) {
156  loc = locationBase + offset;
157  locArray[offset] = loc;
158  locProps.push_back(LocProperty(offset, 0));
159  }
160 
161  // region (1) and (3) are initially empty
162  firstMark = 0;
164  // no request made at this location so far
165  requestCount = 0;
166 }
167 
169 {
170  delete[] locArray;
171 }
172 
173 void
175 {
176  assert(firstMark >= 0);
177  assert(firstMark <= secondMark);
178  assert(secondMark <= arraySize);
179  // make sure loadStoreMap has been cleared
180  assert(loadStoreMap.empty());
181 
182  // this atomic location is picked for Atomic_ACQ
183  // and Atomic_REL in an episode
184  requestCount += 2;
185  // add two expected values in expectedValues set
186  expectedValues.insert(requestCount - 1);
187  expectedValues.insert(requestCount - 2);
188 }
189 
192 {
193  assert(firstMark >= 0);
194  assert(firstMark <= secondMark);
195  assert(secondMark <= arraySize);
196 
197  if (firstMark == arraySize) {
198  // no location can be picked for a LD now, so return an empty location
199  return INVALID_LOCATION;
200  } else {
201  // we can pick any location btw
202  // locArray [firstMark : arraySize-1]
203  int range_size = arraySize - firstMark;
204  Location ret_loc = locArray[firstMark + random() % range_size];
205 
206  // update loadStoreMap
207  LdStMap::iterator it = loadStoreMap.find(ret_loc);
208 
209  if (it == loadStoreMap.end()) {
210  // insert a new entry to the map b/c the entry is not there yet
211  // to mark this location has been picked for a LD
212  loadStoreMap.insert(std::pair<Location, LdStBits>
213  (ret_loc, LdStBits(true,false)));
214  } else {
215  // otherwise, just update the LD bit
216  (it->second).first = true;
217  }
218 
219  return ret_loc;
220  }
221 }
222 
225 {
226  assert(firstMark >= 0);
227  assert(firstMark <= secondMark);
228  assert(secondMark <= arraySize);
229 
230  if (firstMark == secondMark) {
231  // no location can be picked for a ST now, return an invalid location
232  return INVALID_LOCATION;
233  } else {
234  // we can pick any location btw [firstMark : secondMark-1]
235  int range_size = secondMark - firstMark;
236  Location ret_loc = locArray[firstMark + random() % range_size];
237 
238  // update loadStoreMap
239  LdStMap::iterator it = loadStoreMap.find(ret_loc);
240 
241  if (it == loadStoreMap.end()) {
242  // insert a new entry to the map b/c the entry is not there yet
243  // to mark this location has been picked for a ST
244  loadStoreMap.insert(std::pair<Location, LdStBits>
245  (ret_loc, LdStBits(false,true)));
246  } else {
247  // otherwise, just update the ST bit
248  (it->second).second = true;
249  }
250 
251  return ret_loc;
252  }
253 }
254 
255 // for each entry in loadStoreMap,
256 // if <LD_bit, ST_bit> == <1,0>
257 // - if the location is in (2), then move it to (3)
258 // - if the location is in (3), no move
259 // - otherwise, throw an error
260 // if <LD_bit, ST_bit> == <0,1> or <1,1>
261 // - move it from (2) to (1)
262 void
264 {
265  assert(firstMark >= 0);
266  assert(firstMark <= secondMark);
267  assert(secondMark <= arraySize);
268 
269  for (auto& it : loadStoreMap) {
270  Location loc = it.first;
271  LdStBits p = it.second;
272 
273  assert(loc >= locationBase && loc < locationBase + arraySize);
274  LocProperty& loc_prop = locProps[loc - locationBase];
275 
276  if (p.first && !p.second) {
277  // this location has been picked for LD(s) but not ST
278  // it must be in either region (2) or (3)
279  assert(inSecondRegion(loc_prop.first) ||
280  inThirdRegion(loc_prop.first));
281 
282  if (inSecondRegion(loc_prop.first)) {
283  // there is no owner of this location yet
284  assert(loc_prop.second == 0);
285 
286  // pick the last location in (2) to swap
287  Location swapped_loc = locArray[secondMark - 1];
288  LocProperty& swapped_loc_prop =
289  locProps[swapped_loc - locationBase];
290 
291  // swap loc and swapped_loc
292  swap(loc_prop, swapped_loc_prop);
293 
294  // then, expand (3)
295  secondMark--;
296  }
297 
298  // increment the location's number of owners
299  loc_prop.second++;
300  } else if (p.second) {
301  // this location has been picked for ST(s) and/or LD(s)
302  // it must be in region (2)
303  assert(inSecondRegion(loc_prop.first) && loc_prop.second == 0);
304 
305  // pick the first location in (2) to swap
306  Location swapped_loc = locArray[firstMark];
307  LocProperty& swapped_loc_prop =
308  locProps[swapped_loc - locationBase];
309 
310  // swap loc and swapped_loc
311  swap(loc_prop, swapped_loc_prop);
312 
313  // then, expand (1)
314  firstMark++;
315 
316  // increment the location's number of owners
317  loc_prop.second++;
318  } else {
319  panic("Location in loadStoreMap but wasn't picked in any"
320  " action\n");
321  }
322  }
323 
324  // clear the ld_st_map
325  loadStoreMap.clear();
326 }
327 
328 void
330 {
331  assert(loc >= locationBase && loc < locationBase + arraySize);
332 
333  LocProperty& loc_prop = locProps[loc - locationBase];
334 
335  if (inFirstRegion(loc_prop.first)) {
336  // this location must have exactly 1 owner
337  assert(loc_prop.second == 1);
338 
339  // pick the last location in region 1 to swap
340  Location swapped_loc = locArray[firstMark - 1];
341  LocProperty& swapped_loc_prop = locProps[swapped_loc - locationBase];
342 
343  // swap loc and swapped_loc
344  swap(loc_prop, swapped_loc_prop);
345 
346  // then shrink (1)
347  firstMark--;
348 
349  // reset the location's number of owners
350  loc_prop.second = 0;
351  } else if (inThirdRegion(loc_prop.first)) {
352  // this location must have at least 1 owner
353  assert(loc_prop.second >= 1);
354 
355  if (loc_prop.second == 1) {
356  // pick the first location in region 3 to swap
357  Location swapped_loc = locArray[secondMark];
358  LocProperty& swapped_loc_prop =
359  locProps[swapped_loc - locationBase];
360 
361  // swap loc and swapped_loc
362  swap(loc_prop, swapped_loc_prop);
363 
364  // then shrink (3)
365  secondMark++;
366  }
367  // decrement the loc's number of owners
368  loc_prop.second--;
369  } else {
370  // some one else must already reset this counter
371  assert(inSecondRegion(loc_prop.first) && loc_prop.second == 0);
372  }
373 }
374 
375 bool
377 {
378  ExpectedValueSet::iterator it = expectedValues.find(val);
379 
380  if (it == expectedValues.end()) {
381  std::stringstream exp_val_ss;
382  for (auto& val : expectedValues) {
383  exp_val_ss << " " << val;
384  }
385 
386  warn("Expected return values are:\n\t%s\n", exp_val_ss.str());
387 
388  return false;
389  }
390 
391  // erase this value b/c it's done
392  expectedValues.erase(it);
393 
394  return true;
395 }
396 
397 void
399 {
400  int new_idx_1 = prop_2.first;
401  int new_idx_2 = prop_1.first;
402 
403  // swap the two locations in locArray
404  Location tmp = locArray[prop_1.first];
405  locArray[prop_1.first] = locArray[prop_2.first];
406  locArray[prop_2.first] = tmp;
407 
408  // update their new indices
409  prop_1.first = new_idx_1;
410  prop_2.first = new_idx_2;
411 }
412 
413 // ------------------ log table ---------------------
414 void
415 AddressManager::updateLogTable(Location loc, int thread_id, int episode_id,
416  Value new_value, Tick cur_tick, int cu_id)
417 {
418  assert(loc >= 0 && loc < numAtomicLocs + numNormalLocs);
419  logTable[loc]->update(thread_id, cu_id, episode_id, new_value, cur_tick);
420 }
421 
424 {
425  assert(loc >= 0 && loc < numAtomicLocs + numNormalLocs);
426  return logTable[loc]->getLastStoredValue();
427 }
428 
429 bool
431 {
432  assert(loc >= 0 && loc < numAtomicLocs);
433  return atomicStructs[loc]->isExpectedValue(ret_val);
434 }
435 
436 } // namespace gem5
gem5::AddressManager::AtomicStruct::requestCount
int requestCount
Definition: address_manager.hh:233
gem5::AddressManager::AtomicStruct::AtomicStruct
AtomicStruct(Location atom_loc, Location loc_begin, Location loc_end)
Definition: address_manager.cc:139
gem5::AddressManager::AtomicStruct::~AtomicStruct
~AtomicStruct()
Definition: address_manager.cc:168
gem5::AddressManager::AtomicStruct::secondMark
int secondMark
Definition: address_manager.hh:219
warn
#define warn(...)
Definition: logging.hh:245
gem5::AddressManager::AtomicStruct::firstMark
int firstMark
Definition: address_manager.hh:219
gem5::AddressManager::getLoadLoc
Location getLoadLoc(Location atomic_loc)
Definition: address_manager.cc:105
gem5::AddressManager::getStoreLoc
Location getStoreLoc(Location atomic_loc)
Definition: address_manager.cc:112
gem5::AddressManager::finishLocSelection
void finishLocSelection(Location atomic_loc)
Definition: address_manager.cc:119
gem5::AddressManager::AddressManager
AddressManager(int n_atomic_locs, int numNormalLocsPerAtomic)
Definition: address_manager.cc:49
gem5::AddressManager::AtomicStruct::arraySize
int arraySize
Definition: address_manager.hh:220
random.hh
gem5::AddressManager::numNormalLocs
int numNormalLocs
Definition: address_manager.hh:262
gem5::X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:775
gem5::MipsISA::random
random
Definition: pra_constants.hh:53
gem5::AddressManager::validateAtomicResp
bool validateAtomicResp(Location loc, Value ret_val)
Definition: address_manager.cc:430
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::AddressManager::~AddressManager
~AddressManager()
Definition: address_manager.cc:81
gem5::AddressManager::AtomicStruct::LocProperty
std::pair< int, int > LocProperty
Definition: address_manager.hh:223
gem5::AddressManager::atomicStructs
AtomicStructTable atomicStructs
Definition: address_manager.hh:270
gem5::AddressManager::numLocsPerAtomic
int numLocsPerAtomic
Definition: address_manager.hh:260
gem5::AddressManager::AtomicStruct::locProps
LocPropTable locProps
Definition: address_manager.hh:225
gem5::AddressManager::AtomicStruct::getLoadLoc
Location getLoadLoc()
Definition: address_manager.cc:191
gem5::AddressManager::AtomicStruct::startLocSelection
void startLocSelection()
Definition: address_manager.cc:174
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::Tick
uint64_t Tick
Tick count type.
Definition: types.hh:58
gem5::AddressManager::AtomicStruct::getStoreLoc
Location getStoreLoc()
Definition: address_manager.cc:224
gem5::AddressManager::updateLogTable
void updateLogTable(Location loc, int threadId, int episodeId, Value new_value, Tick curTick, int cuId=-1)
Definition: address_manager.cc:415
gem5::AddressManager::getAtomicLoc
Location getAtomicLoc()
Definition: address_manager.cc:97
gem5::AddressManager::AtomicStruct::isExpectedValue
bool isExpectedValue(Value val)
Definition: address_manager.cc:376
gem5::ArmISA::offset
Bitfield< 23, 0 > offset
Definition: types.hh:144
gem5::AddressManager::Location
int32_t Location
Definition: address_manager.hh:129
gem5::AddressManager::INVALID_VALUE
static const int INVALID_VALUE
Definition: address_manager.hh:153
std::pair
STL pair class.
Definition: stl.hh:58
gem5::AddressManager::AtomicStruct::atomicLoc
Location atomicLoc
Definition: address_manager.hh:214
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::AddressManager::INVALID_LOCATION
static const int INVALID_LOCATION
Definition: address_manager.hh:154
gem5::AddressManager::AtomicStruct::endLocSelection
void endLocSelection()
Definition: address_manager.cc:263
gem5::AddressManager::numAtomicLocs
int numAtomicLocs
Definition: address_manager.hh:258
gem5::AddressManager::Value
int32_t Value
Definition: address_manager.hh:128
gem5::AddressManager::AtomicStruct::locArray
Location * locArray
Definition: address_manager.hh:218
gem5::AddressManager::AtomicStruct::locationBase
Location locationBase
Definition: address_manager.hh:215
address_manager.hh
gem5::floorLog2
static constexpr std::enable_if_t< std::is_integral< T >::value, int > floorLog2(T x)
Definition: intmath.hh:59
logging.hh
gem5::AddressManager::LastWriter
Definition: address_manager.hh:157
gem5::AddressManager::AtomicStruct::swap
void swap(LocProperty &prop_1, LocProperty &prop_2)
Definition: address_manager.cc:398
trace.hh
intmath.hh
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::AddressManager::getLoggedValue
Value getLoggedValue(Location loc) const
Definition: address_manager.cc:423
gem5::AddressManager::logTable
LogTable logTable
Definition: address_manager.hh:274
gem5::AddressManager::AtomicStruct::releaseLoc
void releaseLoc(Location loc)
Definition: address_manager.cc:329
gem5::AddressManager::AtomicStruct
Definition: address_manager.hh:195
gem5::AddressManager::randAddressMap
AddressMap randAddressMap
Definition: address_manager.hh:266
gem5::AddressManager::printLastWriter
std::string printLastWriter(Location loc) const
Definition: address_manager.cc:133
gem5::AddressManager::releaseLocation
void releaseLocation(Location atomic_loc, Location loc)
Definition: address_manager.cc:126
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:177
gem5::AddressManager::getAddress
Addr getAddress(Location loc)
Definition: address_manager.cc:90

Generated on Tue Sep 21 2021 12:25:09 for gem5 by doxygen 1.8.17