gem5  v22.1.0.0
addr_range.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012, 2014, 2017-2019, 2021 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 <iterator>
46 #include <list>
47 #include <vector>
48 
49 #include "base/bitfield.hh"
50 #include "base/cprintf.hh"
51 #include "base/logging.hh"
52 #include "base/types.hh"
53 
54 namespace gem5
55 {
56 
57 class AddrRange;
58 
65 
81 class AddrRange
82 {
83 
84  private:
85 
91 
98 
100  uint8_t intlvMatch;
101 
102  protected:
103  struct Dummy {};
104 
105  // The dummy parameter Dummy distinguishes this from the other two argument
106  // constructor which takes two Addrs.
107  template <class Iterator>
108  AddrRange(Dummy, Iterator begin_it, Iterator end_it)
109  : _start(1), _end(0), intlvMatch(0)
110  {
111  if (begin_it != end_it) {
112  // get the values from the first one and check the others
113  _start = begin_it->_start;
114  _end = begin_it->_end;
115  masks = begin_it->masks;
116  intlvMatch = begin_it->intlvMatch;
117  }
118 
119  auto count = std::distance(begin_it, end_it);
120  // either merge if got all ranges or keep this equal to the single
121  // interleaved range
122  if (count > 1) {
123  fatal_if(count != (1ULL << masks.size()),
124  "Got %d ranges spanning %d interleaving bits.",
125  count, masks.size());
126 
127  uint8_t match = 0;
128  for (auto it = begin_it; it != end_it; it++) {
129  fatal_if(!mergesWith(*it),
130  "Can only merge ranges with the same start, end "
131  "and interleaving bits, %s %s.", to_string(),
132  it->to_string());
133 
134  fatal_if(it->intlvMatch != match,
135  "Expected interleave match %d but got %d when "
136  "merging.", match, it->intlvMatch);
137  ++match;
138  }
139  masks.clear();
140  intlvMatch = 0;
141  }
142  }
143 
144  public:
145 
150  : _start(1), _end(0), intlvMatch(0)
151  {}
152 
184  uint8_t _intlv_match)
185  : _start(_start), _end(_end), masks(_masks),
186  intlvMatch(_intlv_match)
187  {
188  // sanity checks
189  fatal_if(!masks.empty() && _intlv_match >= 1ULL << masks.size(),
190  "Match value %d does not fit in %d interleaving bits\n",
191  _intlv_match, masks.size());
192  }
193 
220  AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
221  uint8_t _xor_high_bit, uint8_t _intlv_bits,
222  uint8_t _intlv_match)
223  : _start(_start), _end(_end), masks(_intlv_bits),
224  intlvMatch(_intlv_match)
225  {
226  // sanity checks
227  fatal_if(_intlv_bits && _intlv_match >= 1ULL << _intlv_bits,
228  "Match value %d does not fit in %d interleaving bits\n",
229  _intlv_match, _intlv_bits);
230 
231  // ignore the XOR bits if not interleaving
232  if (_intlv_bits && _xor_high_bit) {
233  if (_xor_high_bit == _intlv_high_bit) {
234  fatal("XOR and interleave high bit must be different\n");
235  } else if (_xor_high_bit > _intlv_high_bit) {
236  if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits)
237  fatal("XOR and interleave high bit must be at least "
238  "%d bits apart\n", _intlv_bits);
239  } else {
240  if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) {
241  fatal("Interleave and XOR high bit must be at least "
242  "%d bits apart\n", _intlv_bits);
243  }
244  }
245  }
246 
247  for (auto i = 0; i < _intlv_bits; i++) {
248  uint8_t bit1 = _intlv_high_bit - i;
249  Addr mask = (1ULL << bit1);
250  if (_xor_high_bit) {
251  uint8_t bit2 = _xor_high_bit - i;
252  mask |= (1ULL << bit2);
253  }
254  masks[_intlv_bits - i - 1] = mask;
255  }
256  }
257 
259  : _start(_start), _end(_end), intlvMatch(0)
260  {}
261 
271  : AddrRange(Dummy{}, ranges.begin(), ranges.end())
272  {}
274  : AddrRange(Dummy{}, ranges.begin(), ranges.end())
275  {}
276 
284  bool interleaved() const { return masks.size() > 0; }
285 
293  uint64_t
294  granularity() const
295  {
296  if (interleaved()) {
297  auto combined_mask = 0;
298  for (auto mask: masks) {
299  combined_mask |= mask;
300  }
301  const uint8_t lowest_bit = ctz64(combined_mask);
302  return 1ULL << lowest_bit;
303  } else {
304  return size();
305  }
306  }
307 
316  uint32_t stripes() const { return 1ULL << masks.size(); }
317 
325  Addr
326  size() const
327  {
328  return (_end - _start) >> masks.size();
329  }
330 
336  bool valid() const { return _start <= _end; }
337 
343  Addr start() const { return _start; }
344 
350  Addr end() const { return _end; }
351 
359  std::string
360  to_string() const
361  {
362  if (interleaved()) {
363  std::string str;
364  for (unsigned int i = 0; i < masks.size(); i++) {
365  str += " ";
366  Addr mask = masks[i];
367  while (mask) {
368  auto bit = ctz64(mask);
369  mask &= ~(1ULL << bit);
370  str += csprintf("a[%d]^", bit);
371  }
372  str += csprintf("\b=%d", bits(intlvMatch, i));
373  }
374  return csprintf("[%#llx:%#llx]%s", _start, _end, str);
375  } else {
376  return csprintf("[%#llx:%#llx]", _start, _end);
377  }
378  }
379 
390  bool
391  mergesWith(const AddrRange& r) const
392  {
393  return r._start == _start && r._end == _end &&
394  r.masks == masks;
395  }
396 
407  bool
408  intersects(const AddrRange& r) const
409  {
410  if (_start >= r._end || _end <= r._start) {
411  // start with the simple case of no overlap at all,
412  // applicable even if we have interleaved ranges
413  return false;
414  } else if (!interleaved() && !r.interleaved()) {
415  // if neither range is interleaved, we are done
416  return true;
417  }
418 
419  // now it gets complicated, focus on the cases we care about
420  if (r.size() == 1) {
421  // keep it simple and check if the address is within
422  // this range
423  return contains(r.start());
424  } else if (mergesWith(r)) {
425  // restrict the check to ranges that belong to the
426  // same chunk
427  return intlvMatch == r.intlvMatch;
428  } else {
429  panic("Cannot test intersection of %s and %s\n",
430  to_string(), r.to_string());
431  }
432  }
433 
444  bool
445  isSubset(const AddrRange& r) const
446  {
447  if (interleaved())
448  panic("Cannot test subset of interleaved range %s\n", to_string());
449 
450  // This address range is not interleaved and therefore it
451  // suffices to check the upper bound, the lower bound and
452  // whether it would fit in a continuous segment of the input
453  // addr range.
454  if (r.interleaved()) {
455  return r.contains(_start) && r.contains(_end - 1) &&
456  size() <= r.granularity();
457  } else {
458  return _start >= r._start && _end <= r._end;
459  }
460  }
461 
470  bool
471  contains(const Addr& a) const
472  {
473  // check if the address is in the range and if there is either
474  // no interleaving, or with interleaving also if the selected
475  // bits from the address match the interleaving value
476  bool in_range = a >= _start && a < _end;
477  if (in_range) {
478  auto sel = 0;
479  for (unsigned int i = 0; i < masks.size(); i++) {
480  Addr masked = a & masks[i];
481  // The result of an xor operation is 1 if the number
482  // of bits set is odd or 0 othersize, thefore it
483  // suffices to count the number of bits set to
484  // determine the i-th bit of sel.
485  sel |= (popCount(masked) % 2) << i;
486  }
487  return sel == intlvMatch;
488  }
489  return false;
490  }
491 
516  inline Addr
518  {
519  // Directly return the address if the range is not interleaved
520  // to prevent undefined behavior.
521  if (!interleaved()) {
522  return a;
523  }
524 
525  // Get the LSB set from each mask
526  int masks_lsb[masks.size()];
527  for (unsigned int i = 0; i < masks.size(); i++) {
528  masks_lsb[i] = ctz64(masks[i]);
529  }
530 
531  // we need to sort the list of bits we will discard as we
532  // discard them one by one starting.
533  std::sort(masks_lsb, masks_lsb + masks.size());
534 
535  for (unsigned int i = 0; i < masks.size(); i++) {
536  const int intlv_bit = masks_lsb[i];
537  if (intlv_bit > 0) {
538  // on every iteration we remove one bit from the input
539  // address, and therefore the lowest invtl_bit has
540  // also shifted to the right by i positions.
541  a = insertBits(a >> 1, intlv_bit - i - 1, 0, a);
542  } else {
543  a >>= 1;
544  }
545  }
546  return a;
547  }
548 
555  inline Addr
557  {
558  // Directly return the address if the range is not interleaved
559  // to prevent undefined behavior.
560  if (!interleaved()) {
561  return a;
562  }
563 
564  // Get the LSB set from each mask
565  int masks_lsb[masks.size()];
566  for (unsigned int i = 0; i < masks.size(); i++) {
567  masks_lsb[i] = ctz64(masks[i]);
568  }
569 
570  // Add bits one-by-one from the LSB side.
571  std::sort(masks_lsb, masks_lsb + masks.size());
572  for (unsigned int i = 0; i < masks.size(); i++) {
573  const int intlv_bit = masks_lsb[i];
574  if (intlv_bit > 0) {
575  // on every iteration we add one bit from the input
576  // address, but the lowest invtl_bit in the iteration is
577  // always in the right position because they are sorted
578  // increasingly from the LSB
579  a = insertBits(a << 1, intlv_bit - 1, 0, a);
580  } else {
581  a <<= 1;
582  }
583  }
584 
585  for (unsigned int i = 0; i < masks.size(); i++) {
586  const int lsb = ctz64(masks[i]);
587  const Addr intlv_bit = bits(intlvMatch, i);
588  // Calculate the mask ignoring the LSB
589  const Addr masked = a & masks[i] & ~(1 << lsb);
590  // Set the LSB of the mask to whatever satisfies the selector bit
591  a = insertBits(a, lsb, intlv_bit ^ popCount(masked));
592  }
593 
594  return a;
595  }
596 
610  Addr
611  getOffset(const Addr& a) const
612  {
613  bool in_range = a >= _start && a < _end;
614  if (!in_range) {
615  return MaxAddr;
616  }
617  if (interleaved()) {
619  } else {
620  return a - _start;
621  }
622  }
623 
639  exclude(const AddrRangeList &exclude_ranges) const
640  {
641  assert(!interleaved());
642 
643  auto sorted_ranges = exclude_ranges;
644  sorted_ranges.sort();
645 
646  std::list<AddrRange> ranges;
647 
648  Addr next_start = start();
649  for (const auto &e : sorted_ranges) {
650  assert(!e.interleaved());
651  if (!intersects(e)) {
652  continue;
653  }
654 
655  if (e.start() <= next_start) {
656  if (e.end() < end()) {
657  if (next_start < e.end()) {
658  next_start = e.end();
659  }
660  } else {
661  return ranges;
662  }
663  } else {
664  ranges.push_back(AddrRange(next_start, e.start()));
665  if (e.end() < end()) {
666  next_start = e.end();
667  } else {
668  return ranges;
669  }
670  }
671  }
672 
673  if (next_start < end()) {
674  ranges.push_back(AddrRange(next_start, end()));
675  }
676 
677  return ranges;
678  }
679 
681  exclude(const AddrRange &excluded_range) const
682  {
683  return exclude(AddrRangeList{excluded_range});
684  }
685 
695  bool
696  operator<(const AddrRange& r) const
697  {
698  if (_start != r._start) {
699  return _start < r._start;
700  } else {
701  // For now assume that the end is also the same.
702  // If both regions are interleaved, assume same interleaving,
703  // and compare intlvMatch values.
704  // Otherwise, return true if this address range is interleaved.
705  if (interleaved() && r.interleaved()) {
706  return intlvMatch < r.intlvMatch;
707  } else {
708  return interleaved();
709  }
710  }
711  }
712 
716  bool
717  operator==(const AddrRange& r) const
718  {
719  if (_start != r._start) return false;
720  if (_end != r._end) return false;
721  if (masks != r.masks) return false;
722  if (intlvMatch != r.intlvMatch) return false;
723 
724  return true;
725  }
726 
730  bool
731  operator!=(const AddrRange& r) const
732  {
733  return !(*this == r);
734  }
735 };
736 
737 static inline AddrRangeList
738 operator-(const AddrRange &range, const AddrRangeList &to_exclude)
739 {
740  return range.exclude(to_exclude);
741 }
742 
743 static inline AddrRangeList
744 operator-(const AddrRange &range, const AddrRange &to_exclude)
745 {
746  return range.exclude(to_exclude);
747 }
748 
749 static inline AddrRangeList
751 {
752  to_exclude.sort();
753 
754  AddrRangeList ret;
755  for (const auto &range: base)
756  ret.splice(ret.end(), range.exclude(to_exclude));
757 
758  return ret;
759 }
760 
761 static inline AddrRangeList
762 exclude(const AddrRangeList &base, const AddrRange &to_exclude)
763 {
764  return exclude(base, AddrRangeList{to_exclude});
765 }
766 
767 static inline AddrRangeList
768 operator-(const AddrRangeList &base, const AddrRangeList &to_exclude)
769 {
770  return exclude(base, to_exclude);
771 }
772 
773 static inline AddrRangeList
775 {
776  base = base - to_exclude;
777  return base;
778 }
779 
780 static inline AddrRangeList
781 operator-(const AddrRangeList &base, const AddrRange &to_exclude)
782 {
783  return exclude(base, to_exclude);
784 }
785 
786 static inline AddrRangeList
788 {
789  base = base - to_exclude;
790  return base;
791 }
792 
796 inline AddrRange
797 RangeEx(Addr start, Addr end)
798 {
799  return AddrRange(start, end);
800 }
801 
805 inline AddrRange
806 RangeIn(Addr start, Addr end)
807 {
808  return AddrRange(start, end + 1);
809 }
810 
814 inline AddrRange
815 RangeSize(Addr start, Addr size)
816 {
817  return AddrRange(start, start + size);
818 }
819 
820 } // namespace gem5
821 
822 #endif // __BASE_ADDR_RANGE_HH__
Defines global host-dependent types: Counter, Tick, and (indirectly) {int,uint}{8,...
The AddrRange class encapsulates an address range, and supports a number of tests to check if two ran...
Definition: addr_range.hh:82
uint8_t intlvMatch
The value to compare sel with.
Definition: addr_range.hh:100
AddrRange(Addr _start, Addr _end)
Definition: addr_range.hh:258
AddrRange(std::list< AddrRange > ranges)
Definition: addr_range.hh:273
AddrRangeList exclude(const AddrRange &excluded_range) const
Definition: addr_range.hh:681
AddrRange(Dummy, Iterator begin_it, Iterator end_it)
Definition: addr_range.hh:108
std::vector< Addr > masks
Each mask determines the bits we need to xor to get one bit of sel.
Definition: addr_range.hh:97
Addr _start
Private fields for the start and end of the range _start is the beginning of the range (inclusive).
Definition: addr_range.hh:89
bool interleaved() const
Determine if the range is interleaved or not.
Definition: addr_range.hh:284
bool operator!=(const AddrRange &r) const
Definition: addr_range.hh:731
bool isSubset(const AddrRange &r) const
Determine if this range is a subset of another range, i.e.
Definition: addr_range.hh:445
AddrRange RangeEx(Addr start, Addr end)
Definition: addr_range.hh:797
AddrRange RangeSize(Addr start, Addr size)
Definition: addr_range.hh:815
Addr removeIntlvBits(Addr a) const
Remove the interleaving bits from an input address.
Definition: addr_range.hh:517
AddrRange(Addr _start, Addr _end, const std::vector< Addr > &_masks, uint8_t _intlv_match)
Construct an address range.
Definition: addr_range.hh:183
uint64_t granularity() const
Determing the interleaving granularity of the range.
Definition: addr_range.hh:294
AddrRange(std::vector< AddrRange > ranges)
Create an address range by merging a collection of interleaved ranges.
Definition: addr_range.hh:270
AddrRange RangeIn(Addr start, Addr end)
Definition: addr_range.hh:806
std::list< AddrRange > AddrRangeList
Convenience typedef for a collection of address ranges.
Definition: addr_range.hh:57
AddrRangeList exclude(const AddrRangeList &exclude_ranges) const
Subtract a list of intervals from the range and return the resulting collection of ranges,...
Definition: addr_range.hh:639
uint32_t stripes() const
Determine the number of interleaved address stripes this range is part of.
Definition: addr_range.hh:316
bool valid() const
Determine if the range is valid.
Definition: addr_range.hh:336
bool contains(const Addr &a) const
Determine if the range contains an address.
Definition: addr_range.hh:471
Addr getOffset(const Addr &a) const
Determine the offset of an address within the range.
Definition: addr_range.hh:611
bool intersects(const AddrRange &r) const
Determine if another range intersects this one, i.e.
Definition: addr_range.hh:408
Addr end() const
Get the end address of the range.
Definition: addr_range.hh:350
bool mergesWith(const AddrRange &r) const
Determine if another range merges with the current one, i.e.
Definition: addr_range.hh:391
Addr start() const
Get the start address of the range.
Definition: addr_range.hh:343
Addr size() const
Get the size of the address range.
Definition: addr_range.hh:326
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:696
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:220
std::string to_string() const
Get a string representation of the range.
Definition: addr_range.hh:360
Addr addIntlvBits(Addr a) const
This method adds the interleaving bits removed by removeIntlvBits.
Definition: addr_range.hh:556
bool operator==(const AddrRange &r) const
Definition: addr_range.hh:717
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
constexpr int popCount(uint64_t val)
Returns the number of set ones in the provided value.
Definition: bitfield.hh:334
constexpr uint64_t mask(unsigned nbits)
Generate a 64-bit mask of 'nbits' 1s, right justified.
Definition: bitfield.hh:63
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
constexpr int ctz64(uint64_t value)
Count trailing zeros in a 64-bit value.
Definition: bitfield.hh:406
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:178
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:226
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:190
Bitfield< 7 > i
Definition: misc_types.hh:67
Bitfield< 9 > e
Definition: misc_types.hh:65
Bitfield< 8 > a
Definition: misc_types.hh:66
Bitfield< 5 > r
Definition: pagetable.hh:60
Bitfield< 51, 12 > base
Definition: pagetable.hh:141
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
static AddrRangeList exclude(const AddrRangeList &base, AddrRangeList to_exclude)
Definition: addr_range.hh:750
std::string csprintf(const char *format, const Args &...args)
Definition: cprintf.hh:161
static AddrRangeList operator-=(AddrRangeList &base, const AddrRangeList &to_exclude)
Definition: addr_range.hh:774
const Addr MaxAddr
Definition: types.hh:171
static AddrRangeList operator-(const AddrRange &range, const AddrRangeList &to_exclude)
Definition: addr_range.hh:738

Generated on Wed Dec 21 2022 10:22:28 for gem5 by doxygen 1.9.1