/*
* Copyright (c) 2012 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 <vector>
#include "base/bitfield.hh"
#include "base/cprintf.hh"
#include "base/misc.hh"
#include "base/types.hh"
class AddrRange
{
private:
/// Private fields for the start and end 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;
/// The value to compare the slice addr[high:(high - bits + 1)]
/// with.
uint8_t intlvMatch;
public:
AddrRange()
: _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
{}
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)
{}
AddrRange(Addr _start, Addr _end)
: _start(_start), _end(_end), intlvHighBit(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), 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;
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 (std::vector<AddrRange>::const_iterator r = ranges.begin();
r != ranges.end(); ++r) {
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;
intlvBits = 0;
}
}
/**
* Determine if the range is interleaved or not.
*
* @return true if interleaved
*/
bool interleaved() const { return intlvBits != 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 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())
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.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 (!interleaved()) {
return _start <= r._end && _end >= r._start;
}
// the current range is interleaved, split the check up in
// three cases
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());
}
/**
* 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
return a >= _start && a <= _end &&
(!interleaved() ||
(bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
intlvMatch));
}
/**
* Keep the operators away from SWIG.
*/
#ifndef SWIG
/**
* 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;
}
#endif // SWIG
};
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__