gem5  v20.1.0.0
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 
68 class AddrRange
69 {
70 
71  private:
72 
78 
85 
87  uint8_t intlvMatch;
88 
89  public:
90 
95  : _start(1), _end(0), intlvMatch(0)
96  {}
97 
129  uint8_t _intlv_match)
130  : _start(_start), _end(_end), masks(_masks),
131  intlvMatch(_intlv_match)
132  {
133  // sanity checks
134  fatal_if(!masks.empty() && _intlv_match >= ULL(1) << masks.size(),
135  "Match value %d does not fit in %d interleaving bits\n",
136  _intlv_match, masks.size());
137  }
138 
165  AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
166  uint8_t _xor_high_bit, uint8_t _intlv_bits,
167  uint8_t _intlv_match)
168  : _start(_start), _end(_end), masks(_intlv_bits),
169  intlvMatch(_intlv_match)
170  {
171  // sanity checks
172  fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits,
173  "Match value %d does not fit in %d interleaving bits\n",
174  _intlv_match, _intlv_bits);
175 
176  // ignore the XOR bits if not interleaving
177  if (_intlv_bits && _xor_high_bit) {
178  if (_xor_high_bit == _intlv_high_bit) {
179  fatal("XOR and interleave high bit must be different\n");
180  } else if (_xor_high_bit > _intlv_high_bit) {
181  if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits)
182  fatal("XOR and interleave high bit must be at least "
183  "%d bits apart\n", _intlv_bits);
184  } else {
185  if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) {
186  fatal("Interleave and XOR high bit must be at least "
187  "%d bits apart\n", _intlv_bits);
188  }
189  }
190  }
191 
192  for (auto i = 0; i < _intlv_bits; i++) {
193  uint8_t bit1 = _intlv_high_bit - i;
194  Addr mask = (1ULL << bit1);
195  if (_xor_high_bit) {
196  uint8_t bit2 = _xor_high_bit - i;
197  mask |= (1ULL << bit2);
198  }
199  masks[_intlv_bits - i - 1] = mask;
200  }
201  }
202 
204  : _start(_start), _end(_end), intlvMatch(0)
205  {}
206 
216  : _start(1), _end(0), intlvMatch(0)
217  {
218  if (!ranges.empty()) {
219  // get the values from the first one and check the others
220  _start = ranges.front()._start;
221  _end = ranges.front()._end;
222  masks = ranges.front().masks;
223  intlvMatch = ranges.front().intlvMatch;
224  }
225  // either merge if got all ranges or keep this equal to the single
226  // interleaved range
227  if (ranges.size() > 1) {
228 
229  if (ranges.size() != (ULL(1) << masks.size()))
230  fatal("Got %d ranges spanning %d interleaving bits\n",
231  ranges.size(), masks.size());
232 
233  uint8_t match = 0;
234  for (const auto& r : ranges) {
235  if (!mergesWith(r))
236  fatal("Can only merge ranges with the same start, end "
237  "and interleaving bits, %s %s\n", to_string(),
238  r.to_string());
239 
240  if (r.intlvMatch != match)
241  fatal("Expected interleave match %d but got %d when "
242  "merging\n", match, r.intlvMatch);
243  ++match;
244  }
245  masks.clear();
246  intlvMatch = 0;
247  }
248  }
249 
257  bool interleaved() const { return masks.size() > 0; }
258 
266  uint64_t granularity() const
267  {
268  if (interleaved()) {
269  auto combined_mask = 0;
270  for (auto mask: masks) {
271  combined_mask |= mask;
272  }
273  const uint8_t lowest_bit = ctz64(combined_mask);
274  return ULL(1) << lowest_bit;
275  } else {
276  return size();
277  }
278  }
279 
288  uint32_t stripes() const { return ULL(1) << masks.size(); }
289 
297  Addr size() const
298  {
299  return (_end - _start) >> masks.size();
300  }
301 
307  bool valid() const { return _start <= _end; }
308 
314  Addr start() const { return _start; }
315 
321  Addr end() const { return _end; }
322 
330  std::string to_string() const
331  {
332  if (interleaved()) {
333  std::string str;
334  for (int i = 0; i < masks.size(); i++) {
335  str += " ";
336  Addr mask = masks[i];
337  while (mask) {
338  auto bit = ctz64(mask);
339  mask &= ~(1ULL << bit);
340  str += csprintf("a[%d]^", bit);
341  }
342  str += csprintf("\b=%d", bits(intlvMatch, i));
343  }
344  return csprintf("[%#llx:%#llx]%s", _start, _end, str);
345  } else {
346  return csprintf("[%#llx:%#llx]", _start, _end);
347  }
348  }
349 
360  bool mergesWith(const AddrRange& r) const
361  {
362  return r._start == _start && r._end == _end &&
363  r.masks == masks;
364  }
365 
376  bool intersects(const AddrRange& r) const
377  {
378  if (_start >= r._end || _end <= r._start)
379  // start with the simple case of no overlap at all,
380  // applicable even if we have interleaved ranges
381  return false;
382  else if (!interleaved() && !r.interleaved())
383  // if neither range is interleaved, we are done
384  return true;
385 
386  // now it gets complicated, focus on the cases we care about
387  if (r.size() == 1)
388  // keep it simple and check if the address is within
389  // this range
390  return contains(r.start());
391  else if (mergesWith(r))
392  // restrict the check to ranges that belong to the
393  // same chunk
394  return intlvMatch == r.intlvMatch;
395  else
396  panic("Cannot test intersection of %s and %s\n",
397  to_string(), r.to_string());
398  }
399 
410  bool isSubset(const AddrRange& r) const
411  {
412  if (interleaved())
413  panic("Cannot test subset of interleaved range %s\n", to_string());
414 
415  // This address range is not interleaved and therefore it
416  // suffices to check the upper bound, the lower bound and
417  // whether it would fit in a continuous segment of the input
418  // addr range.
419  if (r.interleaved()) {
420  return r.contains(_start) && r.contains(_end - 1) &&
421  size() <= r.granularity();
422  } else {
423  return _start >= r._start && _end <= r._end;
424  }
425  }
426 
435  bool contains(const Addr& a) const
436  {
437  // check if the address is in the range and if there is either
438  // no interleaving, or with interleaving also if the selected
439  // bits from the address match the interleaving value
440  bool in_range = a >= _start && a < _end;
441  if (in_range) {
442  auto sel = 0;
443  for (int i = 0; i < masks.size(); i++) {
444  Addr masked = a & masks[i];
445  // The result of an xor operation is 1 if the number
446  // of bits set is odd or 0 othersize, thefore it
447  // suffices to count the number of bits set to
448  // determine the i-th bit of sel.
449  sel |= (popCount(masked) % 2) << i;
450  }
451  return sel == intlvMatch;
452  }
453  return false;
454  }
455 
480  inline Addr removeIntlvBits(Addr a) const
481  {
482  // Get the LSB set from each mask
483  int masks_lsb[masks.size()];
484  for (int i = 0; i < masks.size(); i++) {
485  masks_lsb[i] = ctz64(masks[i]);
486  }
487 
488  // we need to sort the list of bits we will discard as we
489  // discard them one by one starting.
490  std::sort(masks_lsb, masks_lsb + masks.size());
491 
492  for (int i = 0; i < masks.size(); i++) {
493  const int intlv_bit = masks_lsb[i];
494  if (intlv_bit > 0) {
495  // on every iteration we remove one bit from the input
496  // address, and therefore the lowest invtl_bit has
497  // also shifted to the right by i positions.
498  a = insertBits(a >> 1, intlv_bit - i - 1, 0, a);
499  } else {
500  a >>= 1;
501  }
502  }
503  return a;
504  }
505 
512  inline Addr addIntlvBits(Addr a) const
513  {
514  // Get the LSB set from each mask
515  int masks_lsb[masks.size()];
516  for (int i = 0; i < masks.size(); i++) {
517  masks_lsb[i] = ctz64(masks[i]);
518  }
519 
520  // Add bits one-by-one from the LSB side.
521  std::sort(masks_lsb, masks_lsb + masks.size());
522  for (int i = 0; i < masks.size(); i++) {
523  const int intlv_bit = masks_lsb[i];
524  if (intlv_bit > 0) {
525  // on every iteration we add one bit from the input
526  // address, and therefore the lowest invtl_bit has
527  // also shifted to the left by i positions.
528  a = insertBits(a << 1, intlv_bit + i - 1, 0, a);
529  } else {
530  a <<= 1;
531  }
532  }
533 
534  for (int i = 0; i < masks.size(); i++) {
535  const int lsb = ctz64(masks[i]);
536  const Addr intlv_bit = bits(intlvMatch, i);
537  // Calculate the mask ignoring the LSB
538  const Addr masked = a & masks[i] & ~(1 << lsb);
539  // Set the LSB of the mask to whatever satisfies the selector bit
540  a = insertBits(a, lsb, intlv_bit ^ popCount(masked));
541  }
542 
543  return a;
544  }
545 
559  Addr getOffset(const Addr& a) const
560  {
561  bool in_range = a >= _start && a < _end;
562  if (!in_range) {
563  return MaxAddr;
564  }
565  if (interleaved()) {
567  } else {
568  return a - _start;
569  }
570  }
571 
581  bool operator<(const AddrRange& r) const
582  {
583  if (_start != r._start)
584  return _start < r._start;
585  else
586  // for now assume that the end is also the same, and that
587  // we are looking at the same interleaving bits
588  return intlvMatch < r.intlvMatch;
589  }
590 
594  bool operator==(const AddrRange& r) const
595  {
596  if (_start != r._start) return false;
597  if (_end != r._end) return false;
598  if (masks != r.masks) return false;
599  if (intlvMatch != r.intlvMatch) return false;
600 
601  return true;
602  }
603 
607  bool operator!=(const AddrRange& r) const
608  {
609  return !(*this == r);
610  }
611 };
612 
619 
623 inline AddrRange
624 RangeEx(Addr start, Addr end)
625 { return AddrRange(start, end); }
626 
630 inline AddrRange
631 RangeIn(Addr start, Addr end)
632 { return AddrRange(start, end + 1); }
633 
637 inline AddrRange
638 RangeSize(Addr start, Addr size)
639 { return AddrRange(start, start + size); }
640 
641 #endif // __BASE_ADDR_RANGE_HH__
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:165
fatal
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:183
AddrRange::AddrRange
AddrRange()
Definition: addr_range.hh:94
AddrRange::operator==
bool operator==(const AddrRange &r) const
Definition: addr_range.hh:594
ArmISA::i
Bitfield< 7 > i
Definition: miscregs_types.hh:63
AddrRange::interleaved
bool interleaved() const
Determine if the range is interleaved or not.
Definition: addr_range.hh:257
ArmISA::sel
sel
Definition: miscregs_types.hh:644
AddrRange::stripes
uint32_t stripes() const
Determine the number of interleaved address stripes this range is part of.
Definition: addr_range.hh:288
AddrRange::contains
bool contains(const Addr &a) const
Determine if the range contains an address.
Definition: addr_range.hh:435
AddrRange::end
Addr end() const
Get the end address of the range.
Definition: addr_range.hh:321
AddrRange::getOffset
Addr getOffset(const Addr &a) const
Determine the offset of an address within the range.
Definition: addr_range.hh:559
std::vector< Addr >
MaxAddr
const Addr MaxAddr
Definition: types.hh:166
AddrRange::removeIntlvBits
Addr removeIntlvBits(Addr a) const
Remove the interleaving bits from an input address.
Definition: addr_range.hh:480
popCount
int popCount(uint64_t val)
Returns the number of set ones in the provided value.
Definition: bitfield.hh:285
AddrRange::operator!=
bool operator!=(const AddrRange &r) const
Definition: addr_range.hh:607
AddrRange::AddrRange
AddrRange(const std::vector< AddrRange > &ranges)
Create an address range by merging a collection of interleaved ranges.
Definition: addr_range.hh:215
ArmISA::a
Bitfield< 8 > a
Definition: miscregs_types.hh:62
bitfield.hh
AddrRange
The AddrRange class encapsulates an address range, and supports a number of tests to check if two ran...
Definition: addr_range.hh:68
AddrRangeList
std::list< AddrRange > AddrRangeList
Convenience typedef for a collection of address ranges.
Definition: addr_range.hh:618
AddrRange::valid
bool valid() const
Determine if the range is valid.
Definition: addr_range.hh:307
MipsISA::r
r
Definition: pra_constants.hh:95
RangeSize
AddrRange RangeSize(Addr start, Addr size)
Definition: addr_range.hh:638
AddrRange::intlvMatch
uint8_t intlvMatch
The value to compare sel with.
Definition: addr_range.hh:87
AddrRange::_end
Addr _end
Definition: addr_range.hh:77
AddrRange::intersects
bool intersects(const AddrRange &r) const
Determine if another range intersects this one, i.e.
Definition: addr_range.hh:376
cprintf.hh
AddrRange::addIntlvBits
Addr addIntlvBits(Addr a) const
This method adds the interleaving bits removed by removeIntlvBits.
Definition: addr_range.hh:512
Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
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:76
AddrRange::granularity
uint64_t granularity() const
Determing the interleaving granularity of the range.
Definition: addr_range.hh:266
AddrRange::start
Addr start() const
Get the start address of the range.
Definition: addr_range.hh:314
AddrRange::to_string
std::string to_string() const
Get a string representation of the range.
Definition: addr_range.hh:330
ctz64
int ctz64(uint64_t value)
Count trailing zeros in a 64-bit value.
Definition: bitfield.hh:351
types.hh
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:84
AddrRange::AddrRange
AddrRange(Addr _start, Addr _end)
Definition: addr_range.hh:203
insertBits
T insertBits(T val, int first, int last, B bit_val)
Returns val with bits first to last set to the LSBs of bit_val.
Definition: bitfield.hh:147
AddrRange::mergesWith
bool mergesWith(const AddrRange &r) const
Determine if another range merges with the current one, i.e.
Definition: addr_range.hh:360
logging.hh
AddrRange::AddrRange
AddrRange(Addr _start, Addr _end, const std::vector< Addr > &_masks, uint8_t _intlv_match)
Construct an address range.
Definition: addr_range.hh:128
RangeEx
AddrRange RangeEx(Addr start, Addr end)
Definition: addr_range.hh:624
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:581
AddrRange::isSubset
bool isSubset(const AddrRange &r) const
Determine if this range is a subset of another range, i.e.
Definition: addr_range.hh:410
RangeIn
AddrRange RangeIn(Addr start, Addr end)
Definition: addr_range.hh:631
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:219
AddrRange::size
Addr size() const
Get the size of the address range.
Definition: addr_range.hh:297
csprintf
std::string csprintf(const char *format, const Args &...args)
Definition: cprintf.hh:158
ULL
#define ULL(N)
uint64_t constant
Definition: types.hh:50
ArmISA::mask
Bitfield< 28, 24 > mask
Definition: miscregs_types.hh:711
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:171
bits
T bits(T val, int first, int last)
Extract the bitfield from position 'first' to 'last' (inclusive) from 'val' and right justify it.
Definition: bitfield.hh:75

Generated on Wed Sep 30 2020 14:02:07 for gem5 by doxygen 1.8.17