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

Generated on Wed May 4 2022 12:13:54 for gem5 by doxygen 1.8.17