/*
- * Copyright (c) 2012 ARM Limited
+ * Copyright (c) 2012, 2014, 2017-2019 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * Authors: Nathan Binkert
- * Steve Reinhardt
- * Andreas Hansson
*/
#ifndef __BASE_ADDR_RANGE_HH__
#define __BASE_ADDR_RANGE_HH__
+#include <algorithm>
#include <list>
#include <vector>
#include "base/bitfield.hh"
#include "base/cprintf.hh"
-#include "base/misc.hh"
+#include "base/logging.hh"
#include "base/types.hh"
+/**
+ * The AddrRange class encapsulates an address range, and supports a
+ * number of tests to check if two ranges intersect, if a range
+ * contains a specific address etc. Besides a basic range, the
+ * AddrRange also support interleaved ranges, to stripe across cache
+ * banks, or memory controllers. The interleaving is implemented by
+ * allowing a number of bits of the address, at an arbitrary bit
+ * position, to be used as interleaving bits with an associated
+ * matching value. In addition, to prevent uniformly strided address
+ * patterns from a very biased interleaving, we also allow XOR-based
+ * hashing by specifying a set of bits to XOR with before matching.
+ *
+ * The AddrRange is also able to coalesce a number of interleaved
+ * ranges to a contiguous range.
+ */
class AddrRange
{
private:
/// Private fields for the start and end of the range
- /// Both _start and _end are part of the range.
+ /// _start is the beginning of the range (inclusive).
+ /// _end is not part of the range.
Addr _start;
Addr _end;
- /// The high bit of the slice that is used for interleaving
- uint8_t intlvHighBit;
-
- /// The number of bits used for interleaving, set to 0 to disable
- uint8_t intlvBits;
+ /**
+ * Each mask determines the bits we need to xor to get one bit of
+ * sel. The first (0) mask is used to get the LSB and the last for
+ * the MSB of sel.
+ */
+ std::vector<Addr> masks;
- /// The value to compare the slice addr[high:(high - bits + 1)]
- /// with.
+ /** The value to compare sel with. */
uint8_t intlvMatch;
public:
+ /**
+ * @ingroup api_addr_range
+ */
AddrRange()
- : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
+ : _start(1), _end(0), intlvMatch(0)
{}
+ /**
+ * Construct an address range
+ *
+ * If the user provides a non empty vector of masks then the
+ * address range is interleaved. Each mask determines a set of
+ * bits that are xored to determine one bit of the sel value,
+ * starting from the least significant bit (i.e., masks[0]
+ * determines the least significant bit of sel, ...). If sel
+ * matches the provided _intlv_match then the address a is in the
+ * range.
+ *
+ * For example if the input mask is
+ * _masks = { 1 << 8 | 1 << 11 | 1 << 13,
+ * 1 << 15 | 1 << 17 | 1 << 19}
+ *
+ * Then a belongs to the address range if
+ * _start <= a < _end
+ * and
+ * sel == _intlv_match
+ * where
+ * sel[0] = a[8] ^ a[11] ^ a[13]
+ * sel[1] = a[15] ^ a[17] ^ a[19]
+ *
+ * @param _start The start address of this range
+ * @param _end The end address of this range (not included in the range)
+ * @param _masks The input vector of masks
+ * @param intlv_match The matching value of the xor operations
+ *
+ * @ingroup api_addr_range
+ */
+ AddrRange(Addr _start, Addr _end, const std::vector<Addr> &_masks,
+ uint8_t _intlv_match)
+ : _start(_start), _end(_end), masks(_masks),
+ intlvMatch(_intlv_match)
+ {
+ // sanity checks
+ fatal_if(!masks.empty() && _intlv_match >= ULL(1) << masks.size(),
+ "Match value %d does not fit in %d interleaving bits\n",
+ _intlv_match, masks.size());
+ }
+
+ /**
+ * Legacy constructor of AddrRange
+ *
+ * If the user provides a non-zero value in _intlv_high_bit the
+ * address range is interleaved.
+ *
+ * An address a belongs to the address range if
+ * _start <= a < _end
+ * and
+ * sel == _intlv_match
+ * where
+ * sel = sel1 ^ sel2
+ * sel1 = a[_intlv_low_bit:_intlv_high_bit]
+ * sel2 = a[_xor_low_bit:_xor_high_bit]
+ * _intlv_low_bit = _intlv_high_bit - intv_bits
+ * _xor_low_bit = _xor_high_bit - intv_bits
+ *
+ * @param _start The start address of this range
+ * @param _end The end address of this range (not included in the range)
+ * @param _intlv_high_bit The MSB of the intlv bits (disabled if 0)
+ * @param _xor_high_bit The MSB of the xor bit (disabled if 0)
+ * @param _intlv_bits the size, in bits, of the intlv and xor bits
+ * @param intlv_match The matching value of the xor operations
+ *
+ * @ingroup api_addr_range
+ */
AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
- uint8_t _intlv_bits, uint8_t _intlv_match)
- : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
- intlvBits(_intlv_bits), intlvMatch(_intlv_match)
- {}
+ uint8_t _xor_high_bit, uint8_t _intlv_bits,
+ uint8_t _intlv_match)
+ : _start(_start), _end(_end), masks(_intlv_bits),
+ intlvMatch(_intlv_match)
+ {
+ // sanity checks
+ fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits,
+ "Match value %d does not fit in %d interleaving bits\n",
+ _intlv_match, _intlv_bits);
+
+ // ignore the XOR bits if not interleaving
+ if (_intlv_bits && _xor_high_bit) {
+ if (_xor_high_bit == _intlv_high_bit) {
+ fatal("XOR and interleave high bit must be different\n");
+ } else if (_xor_high_bit > _intlv_high_bit) {
+ if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits)
+ fatal("XOR and interleave high bit must be at least "
+ "%d bits apart\n", _intlv_bits);
+ } else {
+ if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) {
+ fatal("Interleave and XOR high bit must be at least "
+ "%d bits apart\n", _intlv_bits);
+ }
+ }
+ }
+
+ for (auto i = 0; i < _intlv_bits; i++) {
+ uint8_t bit1 = _intlv_high_bit - i;
+ Addr mask = (1ULL << bit1);
+ if (_xor_high_bit) {
+ uint8_t bit2 = _xor_high_bit - i;
+ mask |= (1ULL << bit2);
+ }
+ masks[_intlv_bits - i - 1] = mask;
+ }
+ }
AddrRange(Addr _start, Addr _end)
- : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0),
- intlvMatch(0)
+ : _start(_start), _end(_end), intlvMatch(0)
{}
/**
* ranges.
*
* @param ranges Interleaved ranges to be merged
+ *
+ * @ingroup api_addr_range
*/
AddrRange(const std::vector<AddrRange>& ranges)
- : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
+ : _start(1), _end(0), intlvMatch(0)
{
if (!ranges.empty()) {
// get the values from the first one and check the others
_start = ranges.front()._start;
_end = ranges.front()._end;
- intlvHighBit = ranges.front().intlvHighBit;
- intlvBits = ranges.front().intlvBits;
+ masks = ranges.front().masks;
+ intlvMatch = ranges.front().intlvMatch;
+ }
+ // either merge if got all ranges or keep this equal to the single
+ // interleaved range
+ if (ranges.size() > 1) {
- if (ranges.size() != (ULL(1) << intlvBits))
+ if (ranges.size() != (ULL(1) << masks.size()))
fatal("Got %d ranges spanning %d interleaving bits\n",
- ranges.size(), intlvBits);
+ ranges.size(), masks.size());
uint8_t match = 0;
- for (std::vector<AddrRange>::const_iterator r = ranges.begin();
- r != ranges.end(); ++r) {
- if (!mergesWith(*r))
+ for (const auto& r : ranges) {
+ if (!mergesWith(r))
fatal("Can only merge ranges with the same start, end "
- "and interleaving bits\n");
+ "and interleaving bits, %s %s\n", to_string(),
+ r.to_string());
- if (r->intlvMatch != match)
+ if (r.intlvMatch != match)
fatal("Expected interleave match %d but got %d when "
- "merging\n", match, r->intlvMatch);
+ "merging\n", match, r.intlvMatch);
++match;
}
-
- // our range is complete and we can turn this into a
- // non-interleaved range
- intlvHighBit = 0;
- intlvBits = 0;
+ masks.clear();
+ intlvMatch = 0;
}
}
* Determine if the range is interleaved or not.
*
* @return true if interleaved
+ *
+ * @ingroup api_addr_range
*/
- bool interleaved() const { return intlvBits != 0; }
+ bool interleaved() const { return masks.size() > 0; }
/**
* Determing the interleaving granularity of the range.
*
* @return The size of the regions created by the interleaving bits
+ *
+ * @ingroup api_addr_range
*/
uint64_t granularity() const
{
- return ULL(1) << (intlvHighBit - intlvBits + 1);
+ if (interleaved()) {
+ auto combined_mask = 0;
+ for (auto mask: masks) {
+ combined_mask |= mask;
+ }
+ const uint8_t lowest_bit = ctz64(combined_mask);
+ return ULL(1) << lowest_bit;
+ } else {
+ return size();
+ }
}
/**
* is part of.
*
* @return The number of stripes spanned by the interleaving bits
+ *
+ * @ingroup api_addr_range
*/
- uint32_t stripes() const { return ULL(1) << intlvBits; }
+ uint32_t stripes() const { return ULL(1) << masks.size(); }
/**
* Get the size of the address range. For a case where
* interleaving is used we make the simplifying assumption that
* the size is a divisible by the size of the interleaving slice.
+ *
+ * @ingroup api_addr_range
*/
Addr size() const
{
- return (_end - _start + 1) >> intlvBits;
+ return (_end - _start) >> masks.size();
}
/**
* Determine if the range is valid.
+ *
+ * @ingroup api_addr_range
*/
bool valid() const { return _start <= _end; }
/**
* Get the start address of the range.
+ *
+ * @ingroup api_addr_range
*/
Addr start() const { return _start; }
+ /**
+ * Get the end address of the range.
+ *
+ * @ingroup api_addr_range
+ */
+ Addr end() const { return _end; }
+
/**
* Get a string representation of the range. This could
* alternatively be implemented as a operator<<, but at the moment
* that seems like overkill.
+ *
+ * @ingroup api_addr_range
*/
std::string to_string() const
{
- if (interleaved())
- return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end,
- intlvHighBit, intlvHighBit - intlvBits + 1,
- intlvMatch);
- else
- return csprintf("[%#llx : %#llx]", _start, _end);
+ if (interleaved()) {
+ std::string str;
+ for (int i = 0; i < masks.size(); i++) {
+ str += " ";
+ Addr mask = masks[i];
+ while (mask) {
+ auto bit = ctz64(mask);
+ mask &= ~(1ULL << bit);
+ str += csprintf("a[%d]^", bit);
+ }
+ str += csprintf("\b=%d", bits(intlvMatch, i));
+ }
+ return csprintf("[%#llx:%#llx]%s", _start, _end, str);
+ } else {
+ return csprintf("[%#llx:%#llx]", _start, _end);
+ }
}
/**
*
* @param r Range to evaluate merging with
* @return true if the two ranges would merge
+ *
+ * @ingroup api_addr_range
*/
bool mergesWith(const AddrRange& r) const
{
return r._start == _start && r._end == _end &&
- r.intlvHighBit == intlvHighBit &&
- r.intlvBits == intlvBits;
+ r.masks == masks;
}
/**
*
* @param r Range to intersect with
* @return true if the intersection of the two ranges is not empty
+ *
+ * @ingroup api_addr_range
*/
bool intersects(const AddrRange& r) const
{
- if (!interleaved()) {
- return _start <= r._end && _end >= r._start;
- }
-
- // the current range is interleaved, split the check up in
- // three cases
+ if (_start >= r._end || _end <= r._start)
+ // start with the simple case of no overlap at all,
+ // applicable even if we have interleaved ranges
+ return false;
+ else if (!interleaved() && !r.interleaved())
+ // if neither range is interleaved, we are done
+ return true;
+
+ // now it gets complicated, focus on the cases we care about
if (r.size() == 1)
// keep it simple and check if the address is within
// this range
return contains(r.start());
- else if (!r.interleaved())
- // be conservative and ignore the interleaving
- return _start <= r._end && _end >= r._start;
else if (mergesWith(r))
// restrict the check to ranges that belong to the
// same chunk
return intlvMatch == r.intlvMatch;
else
- panic("Cannot test intersection of interleaved range %s\n",
- to_string());
+ panic("Cannot test intersection of %s and %s\n",
+ to_string(), r.to_string());
}
/**
*
* @param r Range to compare with
* @return true if the this range is a subset of the other one
+ *
+ * @ingroup api_addr_range
*/
bool isSubset(const AddrRange& r) const
{
if (interleaved())
panic("Cannot test subset of interleaved range %s\n", to_string());
- return _start >= r._start && _end <= r._end;
+
+ // This address range is not interleaved and therefore it
+ // suffices to check the upper bound, the lower bound and
+ // whether it would fit in a continuous segment of the input
+ // addr range.
+ if (r.interleaved()) {
+ return r.contains(_start) && r.contains(_end - 1) &&
+ size() <= r.granularity();
+ } else {
+ return _start >= r._start && _end <= r._end;
+ }
}
/**
*
* @param a Address to compare with
* @return true if the address is in the range
+ *
+ * @ingroup api_addr_range
*/
bool contains(const Addr& a) const
{
// check if the address is in the range and if there is either
// no interleaving, or with interleaving also if the selected
// bits from the address match the interleaving value
- return a >= _start && a <= _end &&
- (!interleaved() ||
- (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
- intlvMatch));
+ bool in_range = a >= _start && a < _end;
+ if (in_range) {
+ auto sel = 0;
+ for (int i = 0; i < masks.size(); i++) {
+ Addr masked = a & masks[i];
+ // The result of an xor operation is 1 if the number
+ // of bits set is odd or 0 othersize, thefore it
+ // suffices to count the number of bits set to
+ // determine the i-th bit of sel.
+ sel |= (popCount(masked) % 2) << i;
+ }
+ return sel == intlvMatch;
+ }
+ return false;
}
-/**
- * Keep the operators away from SWIG.
- */
-#ifndef SWIG
+ /**
+ * Remove the interleaving bits from an input address.
+ *
+ * This function returns a new address in a continous range [
+ * start, start + size / intlv_bits). We can achieve this by
+ * discarding the LSB in each mask.
+ *
+ * e.g., if the input address is of the form:
+ * ------------------------------------
+ * | a_high | x1 | a_mid | x0 | a_low |
+ * ------------------------------------
+ * where x0 is the LSB set in masks[0]
+ * and x1 is the LSB set in masks[1]
+ *
+ * this function will return:
+ * ---------------------------------
+ * | 0 | a_high | a_mid | a_low |
+ * ---------------------------------
+ *
+ * @param a the input address
+ * @return the new address, or the input address if not interleaved
+ *
+ * @ingroup api_addr_range
+ */
+ inline Addr removeIntlvBits(Addr a) const
+ {
+ // Directly return the address if the range is not interleaved
+ // to prevent undefined behavior.
+ if (!interleaved()) {
+ return a;
+ }
+
+ // Get the LSB set from each mask
+ int masks_lsb[masks.size()];
+ for (int i = 0; i < masks.size(); i++) {
+ masks_lsb[i] = ctz64(masks[i]);
+ }
+
+ // we need to sort the list of bits we will discard as we
+ // discard them one by one starting.
+ std::sort(masks_lsb, masks_lsb + masks.size());
+
+ for (int i = 0; i < masks.size(); i++) {
+ const int intlv_bit = masks_lsb[i];
+ if (intlv_bit > 0) {
+ // on every iteration we remove one bit from the input
+ // address, and therefore the lowest invtl_bit has
+ // also shifted to the right by i positions.
+ a = insertBits(a >> 1, intlv_bit - i - 1, 0, a);
+ } else {
+ a >>= 1;
+ }
+ }
+ return a;
+ }
+
+ /**
+ * This method adds the interleaving bits removed by
+ * removeIntlvBits.
+ *
+ * @ingroup api_addr_range
+ */
+ inline Addr addIntlvBits(Addr a) const
+ {
+ // Directly return the address if the range is not interleaved
+ // to prevent undefined behavior.
+ if (!interleaved()) {
+ return a;
+ }
+
+ // Get the LSB set from each mask
+ int masks_lsb[masks.size()];
+ for (int i = 0; i < masks.size(); i++) {
+ masks_lsb[i] = ctz64(masks[i]);
+ }
+
+ // Add bits one-by-one from the LSB side.
+ std::sort(masks_lsb, masks_lsb + masks.size());
+ for (int i = 0; i < masks.size(); i++) {
+ const int intlv_bit = masks_lsb[i];
+ if (intlv_bit > 0) {
+ // on every iteration we add one bit from the input
+ // address, but the lowest invtl_bit in the iteration is
+ // always in the right position because they are sorted
+ // increasingly from the LSB
+ a = insertBits(a << 1, intlv_bit - 1, 0, a);
+ } else {
+ a <<= 1;
+ }
+ }
+
+ for (int i = 0; i < masks.size(); i++) {
+ const int lsb = ctz64(masks[i]);
+ const Addr intlv_bit = bits(intlvMatch, i);
+ // Calculate the mask ignoring the LSB
+ const Addr masked = a & masks[i] & ~(1 << lsb);
+ // Set the LSB of the mask to whatever satisfies the selector bit
+ a = insertBits(a, lsb, intlv_bit ^ popCount(masked));
+ }
+
+ return a;
+ }
+
+ /**
+ * Determine the offset of an address within the range.
+ *
+ * This function returns the offset of the given address from the
+ * starting address discarding any bits that are used for
+ * interleaving. This way we can convert the input address to a
+ * new unique address in a continuous range that starts from 0.
+ *
+ * @param the input address
+ * @return the flat offset in the address range
+ *
+ * @ingroup api_addr_range
+ */
+ Addr getOffset(const Addr& a) const
+ {
+ bool in_range = a >= _start && a < _end;
+ if (!in_range) {
+ return MaxAddr;
+ }
+ if (interleaved()) {
+ return removeIntlvBits(a) - removeIntlvBits(_start);
+ } else {
+ return a - _start;
+ }
+ }
/**
* Less-than operator used to turn an STL map into a binary search
*
* @param r Range to compare with
* @return true if the start address is less than that of the other range
+ *
+ * @ingroup api_addr_range
*/
bool operator<(const AddrRange& r) const
{
return intlvMatch < r.intlvMatch;
}
-#endif // SWIG
+ /**
+ * @ingroup api_addr_range
+ */
+ bool operator==(const AddrRange& r) const
+ {
+ if (_start != r._start) return false;
+ if (_end != r._end) return false;
+ if (masks != r.masks) return false;
+ if (intlvMatch != r.intlvMatch) return false;
+
+ return true;
+ }
+
+ /**
+ * @ingroup api_addr_range
+ */
+ bool operator!=(const AddrRange& r) const
+ {
+ return !(*this == r);
+ }
};
/**
* Convenience typedef for a collection of address ranges
+ *
+ * @ingroup api_addr_range
*/
typedef std::list<AddrRange> AddrRangeList;
+/**
+ * @ingroup api_addr_range
+ */
inline AddrRange
RangeEx(Addr start, Addr end)
-{ return AddrRange(start, end - 1); }
+{ return AddrRange(start, end); }
+/**
+ * @ingroup api_addr_range
+ */
inline AddrRange
RangeIn(Addr start, Addr end)
-{ return AddrRange(start, end); }
+{ return AddrRange(start, end + 1); }
+/**
+ * @ingroup api_addr_range
+ */
inline AddrRange
RangeSize(Addr start, Addr size)
-{ return AddrRange(start, start + size - 1); }
+{ return AddrRange(start, start + size); }
#endif // __BASE_ADDR_RANGE_HH__
projects / gem5.git / blobdiff