gem5  v21.1.0.2
addr_range.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012, 2014, 2017-2019 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  * Copyright (c) 2002-2005 The Regents of The University of Michigan
15  * All rights reserved.
16  *
17  * Redistribution and use in source and binary forms, with or without
18  * modification, are permitted provided that the following conditions are
19  * met: redistributions of source code must retain the above copyright
20  * notice, this list of conditions and the following disclaimer;
21  * redistributions in binary form must reproduce the above copyright
22  * notice, this list of conditions and the following disclaimer in the
23  * documentation and/or other materials provided with the distribution;
24  * neither the name of the copyright holders nor the names of its
25  * contributors may be used to endorse or promote products derived from
26  * this software without specific prior written permission.
27  *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39  */
40 
41 #ifndef __BASE_ADDR_RANGE_HH__
42 #define __BASE_ADDR_RANGE_HH__
43 
44 #include <algorithm>
45 #include <list>
46 #include <vector>
47 
48 #include "base/bitfield.hh"
49 #include "base/cprintf.hh"
50 #include "base/logging.hh"
51 #include "base/types.hh"
52 
53 namespace gem5
54 {
55 
71 class AddrRange
72 {
73 
74  private:
75 
81 
88 
90  uint8_t intlvMatch;
91 
92  public:
93 
98  : _start(1), _end(0), intlvMatch(0)
99  {}
100 
132  uint8_t _intlv_match)
133  : _start(_start), _end(_end), masks(_masks),
134  intlvMatch(_intlv_match)
135  {
136  // sanity checks
137  fatal_if(!masks.empty() && _intlv_match >= 1ULL << masks.size(),
138  "Match value %d does not fit in %d interleaving bits\n",
139  _intlv_match, masks.size());
140  }
141 
168  AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
169  uint8_t _xor_high_bit, uint8_t _intlv_bits,
170  uint8_t _intlv_match)
171  : _start(_start), _end(_end), masks(_intlv_bits),
172  intlvMatch(_intlv_match)
173  {
174  // sanity checks
175  fatal_if(_intlv_bits && _intlv_match >= 1ULL << _intlv_bits,
176  "Match value %d does not fit in %d interleaving bits\n",
177  _intlv_match, _intlv_bits);
178 
179  // ignore the XOR bits if not interleaving
180  if (_intlv_bits && _xor_high_bit) {
181  if (_xor_high_bit == _intlv_high_bit) {
182  fatal("XOR and interleave high bit must be different\n");
183  } else if (_xor_high_bit > _intlv_high_bit) {
184  if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits)
185  fatal("XOR and interleave high bit must be at least "
186  "%d bits apart\n", _intlv_bits);
187  } else {
188  if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) {
189  fatal("Interleave and XOR high bit must be at least "
190  "%d bits apart\n", _intlv_bits);
191  }
192  }
193  }
194 
195  for (auto i = 0; i < _intlv_bits; i++) {
196  uint8_t bit1 = _intlv_high_bit - i;
197  Addr mask = (1ULL << bit1);
198  if (_xor_high_bit) {
199  uint8_t bit2 = _xor_high_bit - i;
200  mask |= (1ULL << bit2);
201  }
202  masks[_intlv_bits - i - 1] = mask;
203  }
204  }
205 
207  : _start(_start), _end(_end), intlvMatch(0)
208  {}
209 
219  : _start(1), _end(0), intlvMatch(0)
220  {
221  if (!ranges.empty()) {
222  // get the values from the first one and check the others
223  _start = ranges.front()._start;
224  _end = ranges.front()._end;
225  masks = ranges.front().masks;
226  intlvMatch = ranges.front().intlvMatch;
227  }
228  // either merge if got all ranges or keep this equal to the single
229  // interleaved range
230  if (ranges.size() > 1) {
231 
232  if (ranges.size() != (1ULL << masks.size()))
233  fatal("Got %d ranges spanning %d interleaving bits\n",
234  ranges.size(), masks.size());
235 
236  uint8_t match = 0;
237  for (const auto& r : ranges) {
238  if (!mergesWith(r))
239  fatal("Can only merge ranges with the same start, end "
240  "and interleaving bits, %s %s\n", to_string(),
241  r.to_string());
242 
243  if (r.intlvMatch != match)
244  fatal("Expected interleave match %d but got %d when "
245  "merging\n", match, r.intlvMatch);
246  ++match;
247  }
248  masks.clear();
249  intlvMatch = 0;
250  }
251  }
252 
260  bool interleaved() const { return masks.size() > 0; }
261 
269  uint64_t granularity() const
270  {
271  if (interleaved()) {
272  auto combined_mask = 0;
273  for (auto mask: masks) {
274  combined_mask |= mask;
275  }
276  const uint8_t lowest_bit = ctz64(combined_mask);
277  return 1ULL << lowest_bit;
278  } else {
279  return size();
280  }
281  }
282 
291  uint32_t stripes() const { return 1ULL << masks.size(); }
292 
300  Addr size() const
301  {
302  return (_end - _start) >> masks.size();
303  }
304 
310  bool valid() const { return _start <= _end; }
311 
317  Addr start() const { return _start; }
318 
324  Addr end() const { return _end; }
325 
333  std::string to_string() const
334  {
335  if (interleaved()) {
336  std::string str;
337  for (int i = 0; i < masks.size(); i++) {
338  str += " ";
339  Addr mask = masks[i];
340  while (mask) {
341  auto bit = ctz64(mask);
342  mask &= ~(1ULL << bit);
343  str += csprintf("a[%d]^", bit);
344  }
345  str += csprintf("\b=%d", bits(intlvMatch, i));
346  }
347  return csprintf("[%#llx:%#llx]%s", _start, _end, str);
348  } else {
349  return csprintf("[%#llx:%#llx]", _start, _end);
350  }
351  }
352 
363  bool mergesWith(const AddrRange& r) const
364  {
365  return r._start == _start && r._end == _end &&
366  r.masks == masks;
367  }
368 
379  bool intersects(const AddrRange& r) const
380  {
381  if (_start >= r._end || _end <= r._start)
382  // start with the simple case of no overlap at all,
383  // applicable even if we have interleaved ranges
384  return false;
385  else if (!interleaved() && !r.interleaved())
386  // if neither range is interleaved, we are done
387  return true;
388 
389  // now it gets complicated, focus on the cases we care about
390  if (r.size() == 1)
391  // keep it simple and check if the address is within
392  // this range
393  return contains(r.start());
394  else if (mergesWith(r))
395  // restrict the check to ranges that belong to the
396  // same chunk
397  return intlvMatch == r.intlvMatch;
398  else
399  panic("Cannot test intersection of %s and %s\n",
400  to_string(), r.to_string());
401  }
402 
413  bool isSubset(const AddrRange& r) const
414  {
415  if (interleaved())
416  panic("Cannot test subset of interleaved range %s\n", to_string());
417 
418  // This address range is not interleaved and therefore it
419  // suffices to check the upper bound, the lower bound and
420  // whether it would fit in a continuous segment of the input
421  // addr range.
422  if (r.interleaved()) {
423  return r.contains(_start) && r.contains(_end - 1) &&
424  size() <= r.granularity();
425  } else {
426  return _start >= r._start && _end <= r._end;
427  }
428  }
429 
438  bool contains(const Addr& a) const
439  {
440  // check if the address is in the range and if there is either
441  // no interleaving, or with interleaving also if the selected
442  // bits from the address match the interleaving value
443  bool in_range = a >= _start && a < _end;
444  if (in_range) {
445  auto sel = 0;
446  for (int i = 0; i < masks.size(); i++) {
447  Addr masked = a & masks[i];
448  // The result of an xor operation is 1 if the number
449  // of bits set is odd or 0 othersize, thefore it
450  // suffices to count the number of bits set to
451  // determine the i-th bit of sel.
452  sel |= (popCount(masked) % 2) << i;
453  }
454  return sel == intlvMatch;
455  }
456  return false;
457  }
458 
483  inline Addr removeIntlvBits(Addr a) const
484  {
485  // Directly return the address if the range is not interleaved
486  // to prevent undefined behavior.
487  if (!interleaved()) {
488  return a;
489  }
490 
491  // Get the LSB set from each mask
492  int masks_lsb[masks.size()];
493  for (int i = 0; i < masks.size(); i++) {
494  masks_lsb[i] = ctz64(masks[i]);
495  }
496 
497  // we need to sort the list of bits we will discard as we
498  // discard them one by one starting.
499  std::sort(masks_lsb, masks_lsb + masks.size());
500 
501  for (int i = 0; i < masks.size(); i++) {
502  const int intlv_bit = masks_lsb[i];
503  if (intlv_bit > 0) {
504  // on every iteration we remove one bit from the input
505  // address, and therefore the lowest invtl_bit has
506  // also shifted to the right by i positions.
507  a = insertBits(a >> 1, intlv_bit - i - 1, 0, a);
508  } else {
509  a >>= 1;
510  }
511  }
512  return a;
513  }
514 
521  inline Addr addIntlvBits(Addr a) const
522  {
523  // Directly return the address if the range is not interleaved
524  // to prevent undefined behavior.
525  if (!interleaved()) {
526  return a;
527  }
528 
529  // Get the LSB set from each mask
530  int masks_lsb[masks.size()];
531  for (int i = 0; i < masks.size(); i++) {
532  masks_lsb[i] = ctz64(masks[i]);
533  }
534 
535  // Add bits one-by-one from the LSB side.
536  std::sort(masks_lsb, masks_lsb + masks.size());
537  for (int i = 0; i < masks.size(); i++) {
538  const int intlv_bit = masks_lsb[i];
539  if (intlv_bit > 0) {
540  // on every iteration we add one bit from the input
541  // address, but the lowest invtl_bit in the iteration is
542  // always in the right position because they are sorted
543  // increasingly from the LSB
544  a = insertBits(a << 1, intlv_bit - 1, 0, a);
545  } else {
546  a <<= 1;
547  }
548  }
549 
550  for (int i = 0; i < masks.size(); i++) {
551  const int lsb = ctz64(masks[i]);
552  const Addr intlv_bit = bits(intlvMatch, i);
553  // Calculate the mask ignoring the LSB
554  const Addr masked = a & masks[i] & ~(1 << lsb);
555  // Set the LSB of the mask to whatever satisfies the selector bit
556  a = insertBits(a, lsb, intlv_bit ^ popCount(masked));
557  }
558 
559  return a;
560  }
561 
575  Addr getOffset(const Addr& a) const
576  {
577  bool in_range = a >= _start && a < _end;
578  if (!in_range) {
579  return MaxAddr;
580  }
581  if (interleaved()) {
583  } else {
584  return a - _start;
585  }
586  }
587 
597  bool operator<(const AddrRange& r) const
598  {
599  if (_start != r._start) {
600  return _start < r._start;
601  } else {
602  // For now assume that the end is also the same.
603  // If both regions are interleaved, assume same interleaving,
604  // and compare intlvMatch values.
605  // Otherwise, return true if this address range is interleaved.
606  if (interleaved() && r.interleaved()) {
607  return intlvMatch < r.intlvMatch;
608  } else {
609  return interleaved();
610  }
611  }
612  }
613 
617  bool operator==(const AddrRange& r) const
618  {
619  if (_start != r._start) return false;
620  if (_end != r._end) return false;
621  if (masks != r.masks) return false;
622  if (intlvMatch != r.intlvMatch) return false;
623 
624  return true;
625  }
626 
630  bool operator!=(const AddrRange& r) const
631  {
632  return !(*this == r);
633  }
634 };
635 
642 
646 inline AddrRange
647 RangeEx(Addr start, Addr end)
648 { return AddrRange(start, end); }
649 
653 inline AddrRange
654 RangeIn(Addr start, Addr end)
655 { return AddrRange(start, end + 1); }
656 
660 inline AddrRange
661 RangeSize(Addr start, Addr size)
662 { return AddrRange(start, start + size); }
663 
664 } // namespace gem5
665 
666 #endif // __BASE_ADDR_RANGE_HH__
fatal
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:189
gem5::AddrRange::to_string
std::string to_string() const
Get a string representation of the range.
Definition: addr_range.hh:333
gem5::AddrRange::granularity
uint64_t granularity() const
Determing the interleaving granularity of the range.
Definition: addr_range.hh:269
gem5::AddrRange::start
Addr start() const
Get the start address of the range.
Definition: addr_range.hh:317
gem5::AddrRange::addIntlvBits
Addr addIntlvBits(Addr a) const
This method adds the interleaving bits removed by removeIntlvBits.
Definition: addr_range.hh:521
gem5::AddrRange::AddrRange
AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, uint8_t _xor_high_bit, uint8_t _intlv_bits, uint8_t _intlv_match)
Legacy constructor of AddrRange.
Definition: addr_range.hh:168
gem5::RangeSize
AddrRange RangeSize(Addr start, Addr size)
Definition: addr_range.hh:661
gem5::AddrRangeList
std::list< AddrRange > AddrRangeList
Convenience typedef for a collection of address ranges.
Definition: addr_range.hh:641
gem5::AddrRange::contains
bool contains(const Addr &a) const
Determine if the range contains an address.
Definition: addr_range.hh:438
gem5::ArmISA::a
Bitfield< 8 > a
Definition: misc_types.hh:65
gem5::AddrRange::intersects
bool intersects(const AddrRange &r) const
Determine if another range intersects this one, i.e.
Definition: addr_range.hh:379
std::vector< Addr >
gem5::csprintf
std::string csprintf(const char *format, const Args &...args)
Definition: cprintf.hh:161
gem5::ctz64
constexpr int ctz64(uint64_t value)
Count trailing zeros in a 64-bit value.
Definition: bitfield.hh:409
gem5::AddrRange::isSubset
bool isSubset(const AddrRange &r) const
Determine if this range is a subset of another range, i.e.
Definition: addr_range.hh:413
gem5::AddrRange::_start
Addr _start
Private fields for the start and end of the range _start is the beginning of the range (inclusive).
Definition: addr_range.hh:79
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::RangeIn
AddrRange RangeIn(Addr start, Addr end)
Definition: addr_range.hh:654
gem5::AddrRange::removeIntlvBits
Addr removeIntlvBits(Addr a) const
Remove the interleaving bits from an input address.
Definition: addr_range.hh:483
gem5::AddrRange::operator<
bool operator<(const AddrRange &r) const
Less-than operator used to turn an STL map into a binary search tree of non-overlapping address range...
Definition: addr_range.hh:597
gem5::mask
constexpr uint64_t mask(unsigned nbits)
Generate a 64-bit mask of 'nbits' 1s, right justified.
Definition: bitfield.hh:63
gem5::RangeEx
AddrRange RangeEx(Addr start, Addr end)
Definition: addr_range.hh:647
bitfield.hh
gem5::AddrRange::interleaved
bool interleaved() const
Determine if the range is interleaved or not.
Definition: addr_range.hh:260
gem5::MaxAddr
const Addr MaxAddr
Definition: types.hh:171
gem5::popCount
constexpr int popCount(uint64_t val)
Returns the number of set ones in the provided value.
Definition: bitfield.hh:337
gem5::AddrRange::AddrRange
AddrRange(const std::vector< AddrRange > &ranges)
Create an address range by merging a collection of interleaved ranges.
Definition: addr_range.hh:218
gem5::AddrRange::masks
std::vector< Addr > masks
Each mask determines the bits we need to xor to get one bit of sel.
Definition: addr_range.hh:87
gem5::AddrRange::size
Addr size() const
Get the size of the address range.
Definition: addr_range.hh:300
gem5::AddrRange::end
Addr end() const
Get the end address of the range.
Definition: addr_range.hh:324
gem5::AddrRange::valid
bool valid() const
Determine if the range is valid.
Definition: addr_range.hh:310
cprintf.hh
gem5::insertBits
constexpr T insertBits(T val, unsigned first, unsigned last, B bit_val)
Returns val with bits first to last set to the LSBs of bit_val.
Definition: bitfield.hh:166
gem5::bits
constexpr T bits(T val, unsigned first, unsigned last)
Extract the bitfield from position 'first' to 'last' (inclusive) from 'val' and right justify it.
Definition: bitfield.hh:76
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::AddrRange::operator==
bool operator==(const AddrRange &r) const
Definition: addr_range.hh:617
gem5::AddrRange::AddrRange
AddrRange(Addr _start, Addr _end)
Definition: addr_range.hh:206
gem5::AddrRange::intlvMatch
uint8_t intlvMatch
The value to compare sel with.
Definition: addr_range.hh:90
gem5::AddrRange::mergesWith
bool mergesWith(const AddrRange &r) const
Determine if another range merges with the current one, i.e.
Definition: addr_range.hh:363
gem5::AddrRange::AddrRange
AddrRange()
Definition: addr_range.hh:97
gem5::AddrRange::getOffset
Addr getOffset(const Addr &a) const
Determine the offset of an address within the range.
Definition: addr_range.hh:575
types.hh
logging.hh
gem5::ArmISA::sel
sel
Definition: misc_types.hh:650
gem5::MipsISA::r
r
Definition: pra_constants.hh:98
gem5::AddrRange::operator!=
bool operator!=(const AddrRange &r) const
Definition: addr_range.hh:630
gem5::AddrRange
The AddrRange class encapsulates an address range, and supports a number of tests to check if two ran...
Definition: addr_range.hh:71
std::list< AddrRange >
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:225
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::AddrRange::AddrRange
AddrRange(Addr _start, Addr _end, const std::vector< Addr > &_masks, uint8_t _intlv_match)
Construct an address range.
Definition: addr_range.hh:131
gem5::AddrRange::_end
Addr _end
Definition: addr_range.hh:80
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:177
gem5::AddrRange::stripes
uint32_t stripes() const
Determine the number of interleaved address stripes this range is part of.
Definition: addr_range.hh:291

Generated on Tue Sep 21 2021 12:24:52 for gem5 by doxygen 1.8.17