| /* | |
| * Copyright (c) 2012, 2014, 2017 ARM Limited | |
| * All rights reserved | |
| * | |
| * The license below extends only to copyright in the software and shall | |
| * not be construed as granting a license to any other intellectual | |
| * property including but not limited to intellectual property relating | |
| * to a hardware implementation of the functionality of the software | |
| * licensed hereunder. You may use the software subject to the license | |
| * terms below provided that you ensure that this notice is replicated | |
| * unmodified and in its entirety in all distributions of the software, | |
| * modified or unmodified, in source code or in binary form. | |
| * | |
| * Copyright (c) 2002-2005 The Regents of The University of Michigan | |
| * All rights reserved. | |
| * | |
| * Redistribution and use in source and binary forms, with or without | |
| * modification, are permitted provided that the following conditions are | |
| * met: redistributions of source code must retain the above copyright | |
| * notice, this list of conditions and the following disclaimer; | |
| * redistributions in binary form must reproduce the above copyright | |
| * notice, this list of conditions and the following disclaimer in the | |
| * documentation and/or other materials provided with the distribution; | |
| * neither the name of the copyright holders nor the names of its | |
| * contributors may be used to endorse or promote products derived from | |
| * this software without specific prior written permission. | |
| * | |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| * 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 <list> | |
| #include <vector> | |
| #include "base/bitfield.hh" | |
| #include "base/cprintf.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 basic | |
| * XOR-based hashing by specifying an additional 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. | |
| Addr _start; | |
| Addr _end; | |
| /// The high bit of the slice that is used for interleaving | |
| uint8_t intlvHighBit; | |
| /// The high bit of the slice used to XOR hash the value we match | |
| /// against, set to 0 to disable. | |
| uint8_t xorHighBit; | |
| /// The number of bits used for interleaving, set to 0 to disable | |
| uint8_t intlvBits; | |
| /// The value to compare the slice addr[high:(high - bits + 1)] | |
| /// with. | |
| uint8_t intlvMatch; | |
| public: | |
| AddrRange() | |
| : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), | |
| intlvMatch(0) | |
| {} | |
| AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, | |
| uint8_t _xor_high_bit, uint8_t _intlv_bits, | |
| uint8_t _intlv_match) | |
| : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), | |
| xorHighBit(_xor_high_bit), intlvBits(_intlv_bits), | |
| intlvMatch(_intlv_match) | |
| { | |
| // sanity checks | |
| fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits, | |
| "Match value %d does not fit in %d interleaving bits\n", | |
| intlvMatch, intlvBits); | |
| // ignore the XOR bits if not interleaving | |
| if (intlvBits && xorHighBit) { | |
| if (xorHighBit == intlvHighBit) { | |
| fatal("XOR and interleave high bit must be different\n"); | |
| } else if (xorHighBit > intlvHighBit) { | |
| if ((xorHighBit - intlvHighBit) < intlvBits) | |
| fatal("XOR and interleave high bit must be at least " | |
| "%d bits apart\n", intlvBits); | |
| } else { | |
| if ((intlvHighBit - xorHighBit) < intlvBits) { | |
| fatal("Interleave and XOR high bit must be at least " | |
| "%d bits apart\n", intlvBits); | |
| } | |
| } | |
| } | |
| } | |
| AddrRange(Addr _start, Addr _end) | |
| : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0), | |
| intlvBits(0), intlvMatch(0) | |
| {} | |
| /** | |
| * Create an address range by merging a collection of interleaved | |
| * ranges. | |
| * | |
| * @param ranges Interleaved ranges to be merged | |
| */ | |
| AddrRange(const std::vector<AddrRange>& ranges) | |
| : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(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; | |
| xorHighBit = ranges.front().xorHighBit; | |
| intlvBits = ranges.front().intlvBits; | |
| if (ranges.size() != (ULL(1) << intlvBits)) | |
| fatal("Got %d ranges spanning %d interleaving bits\n", | |
| ranges.size(), intlvBits); | |
| uint8_t match = 0; | |
| for (const auto& r : ranges) { | |
| if (!mergesWith(r)) | |
| fatal("Can only merge ranges with the same start, end " | |
| "and interleaving bits\n"); | |
| if (r.intlvMatch != match) | |
| fatal("Expected interleave match %d but got %d when " | |
| "merging\n", match, r.intlvMatch); | |
| ++match; | |
| } | |
| // our range is complete and we can turn this into a | |
| // non-interleaved range | |
| intlvHighBit = 0; | |
| xorHighBit = 0; | |
| intlvBits = 0; | |
| } | |
| } | |
| /** | |
| * Determine if the range is interleaved or not. | |
| * | |
| * @return true if interleaved | |
| */ | |
| bool interleaved() const { return intlvBits != 0; } | |
| /** | |
| * Determine if the range interleaving is hashed or not. | |
| */ | |
| bool hashed() const { return interleaved() && xorHighBit != 0; } | |
| /** | |
| * Determing the interleaving granularity of the range. | |
| * | |
| * @return The size of the regions created by the interleaving bits | |
| */ | |
| uint64_t granularity() const | |
| { | |
| return ULL(1) << (intlvHighBit - intlvBits + 1); | |
| } | |
| /** | |
| * Determine the number of interleaved address stripes this range | |
| * is part of. | |
| * | |
| * @return The number of stripes spanned by the interleaving bits | |
| */ | |
| uint32_t stripes() const { return ULL(1) << intlvBits; } | |
| /** | |
| * 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. | |
| */ | |
| Addr size() const | |
| { | |
| return (_end - _start + 1) >> intlvBits; | |
| } | |
| /** | |
| * Determine if the range is valid. | |
| */ | |
| bool valid() const { return _start <= _end; } | |
| /** | |
| * Get the start address of the range. | |
| */ | |
| Addr start() const { return _start; } | |
| /** | |
| * Get the end address of the 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. | |
| */ | |
| std::string to_string() const | |
| { | |
| if (interleaved()) { | |
| if (hashed()) { | |
| return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d", | |
| _start, _end, | |
| intlvHighBit, intlvHighBit - intlvBits + 1, | |
| xorHighBit, xorHighBit - intlvBits + 1, | |
| intlvMatch); | |
| } else { | |
| return csprintf("[%#llx : %#llx], [%d : %d] = %d", | |
| _start, _end, | |
| intlvHighBit, intlvHighBit - intlvBits + 1, | |
| intlvMatch); | |
| } | |
| } else { | |
| return csprintf("[%#llx : %#llx]", _start, _end); | |
| } | |
| } | |
| /** | |
| * Determine if another range merges with the current one, i.e. if | |
| * they are part of the same contigous range and have the same | |
| * interleaving bits. | |
| * | |
| * @param r Range to evaluate merging with | |
| * @return true if the two ranges would merge | |
| */ | |
| bool mergesWith(const AddrRange& r) const | |
| { | |
| return r._start == _start && r._end == _end && | |
| r.intlvHighBit == intlvHighBit && | |
| r.xorHighBit == xorHighBit && | |
| r.intlvBits == intlvBits; | |
| } | |
| /** | |
| * Determine if another range intersects this one, i.e. if there | |
| * is an address that is both in this range and the other | |
| * range. No check is made to ensure either range is valid. | |
| * | |
| * @param r Range to intersect with | |
| * @return true if the intersection of the two ranges is not empty | |
| */ | |
| bool intersects(const AddrRange& r) const | |
| { | |
| 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 (mergesWith(r)) | |
| // restrict the check to ranges that belong to the | |
| // same chunk | |
| return intlvMatch == r.intlvMatch; | |
| else | |
| panic("Cannot test intersection of %s and %s\n", | |
| to_string(), r.to_string()); | |
| } | |
| /** | |
| * Determine if this range is a subset of another range, i.e. if | |
| * every address in this range is also in the other range. No | |
| * check is made to ensure either range is valid. | |
| * | |
| * @param r Range to compare with | |
| * @return true if the this range is a subset of the other one | |
| */ | |
| 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; | |
| } | |
| /** | |
| * Determine if the range contains an address. | |
| * | |
| * @param a Address to compare with | |
| * @return true if the address is in the 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 | |
| bool in_range = a >= _start && a <= _end; | |
| if (!interleaved()) { | |
| return in_range; | |
| } else if (in_range) { | |
| if (!hashed()) { | |
| return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == | |
| intlvMatch; | |
| } else { | |
| return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^ | |
| bits(a, xorHighBit, xorHighBit - intlvBits + 1)) == | |
| intlvMatch; | |
| } | |
| } | |
| return false; | |
| } | |
| /** | |
| * Remove the interleaving bits from an input address. | |
| * | |
| * This function returns a new address that doesn't have the bits | |
| * that are use to determine which of the interleaved ranges it | |
| * belongs to. | |
| * | |
| * e.g., if the input address is: | |
| * ------------------------------- | |
| * | prefix | intlvBits | suffix | | |
| * ------------------------------- | |
| * this function will return: | |
| * ------------------------------- | |
| * | 0 | prefix | suffix | | |
| * ------------------------------- | |
| * | |
| * @param the input address | |
| * @return the address without the interleaved bits | |
| */ | |
| inline Addr removeIntlvBits(const Addr &a) const | |
| { | |
| const auto intlv_low_bit = intlvHighBit - intlvBits + 1; | |
| return insertBits(a >> intlvBits, intlv_low_bit - 1, 0, 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 | |
| */ | |
| 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 | |
| * tree of non-overlapping address ranges. | |
| * | |
| * @param r Range to compare with | |
| * @return true if the start address is less than that of the other range | |
| */ | |
| bool operator<(const AddrRange& r) const | |
| { | |
| if (_start != r._start) | |
| return _start < r._start; | |
| else | |
| // for now assume that the end is also the same, and that | |
| // we are looking at the same interleaving bits | |
| return intlvMatch < r.intlvMatch; | |
| } | |
| bool operator==(const AddrRange& r) const | |
| { | |
| if (_start != r._start) return false; | |
| if (_end != r._end) return false; | |
| if (intlvBits != r.intlvBits) return false; | |
| if (intlvBits != 0) { | |
| if (intlvHighBit != r.intlvHighBit) return false; | |
| if (intlvMatch != r.intlvMatch) return false; | |
| } | |
| return true; | |
| } | |
| bool operator!=(const AddrRange& r) const | |
| { | |
| return !(*this == r); | |
| } | |
| }; | |
| /** | |
| * Convenience typedef for a collection of address ranges | |
| */ | |
| typedef std::list<AddrRange> AddrRangeList; | |
| inline AddrRange | |
| RangeEx(Addr start, Addr end) | |
| { return AddrRange(start, end - 1); } | |
| inline AddrRange | |
| RangeIn(Addr start, Addr end) | |
| { return AddrRange(start, end); } | |
| inline AddrRange | |
| RangeSize(Addr start, Addr size) | |
| { return AddrRange(start, start + size - 1); } | |
| #endif // __BASE_ADDR_RANGE_HH__ |