addr_range.hh revision 10676:f6c168692b20
12068SN/A/*
22068SN/A * Copyright (c) 2012, 2014 ARM Limited
32188SN/A * All rights reserved
42068SN/A *
52068SN/A * The license below extends only to copyright in the software and shall
62068SN/A * not be construed as granting a license to any other intellectual
72068SN/A * property including but not limited to intellectual property relating
82068SN/A * to a hardware implementation of the functionality of the software
92068SN/A * licensed hereunder.  You may use the software subject to the license
102068SN/A * terms below provided that you ensure that this notice is replicated
112068SN/A * unmodified and in its entirety in all distributions of the software,
122068SN/A * modified or unmodified, in source code or in binary form.
132068SN/A *
142068SN/A * Copyright (c) 2002-2005 The Regents of The University of Michigan
152068SN/A * All rights reserved.
162068SN/A *
172068SN/A * Redistribution and use in source and binary forms, with or without
182068SN/A * modification, are permitted provided that the following conditions are
192068SN/A * met: redistributions of source code must retain the above copyright
202068SN/A * notice, this list of conditions and the following disclaimer;
212068SN/A * redistributions in binary form must reproduce the above copyright
222068SN/A * notice, this list of conditions and the following disclaimer in the
232068SN/A * documentation and/or other materials provided with the distribution;
242068SN/A * neither the name of the copyright holders nor the names of its
252068SN/A * contributors may be used to endorse or promote products derived from
262068SN/A * this software without specific prior written permission.
272068SN/A *
282665Ssaidi@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
292665Ssaidi@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
302068SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
312649Ssaidi@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
322649Ssaidi@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
332649Ssaidi@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
342649Ssaidi@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
352649Ssaidi@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
362068SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
372068SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
382068SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
392068SN/A *
402068SN/A * Authors: Nathan Binkert
412068SN/A *          Steve Reinhardt
422068SN/A *          Andreas Hansson
432068SN/A */
442075SN/A
452075SN/A#ifndef __BASE_ADDR_RANGE_HH__
462075SN/A#define __BASE_ADDR_RANGE_HH__
472075SN/A
482075SN/A#include <list>
492075SN/A#include <vector>
502735Sktlim@umich.edu
512069SN/A#include "base/bitfield.hh"
522069SN/A#include "base/cprintf.hh"
532075SN/A#include "base/misc.hh"
542735Sktlim@umich.edu#include "base/types.hh"
552068SN/A
562068SN/A/**
572068SN/A * The AddrRange class encapsulates an address range, and supports a
582075SN/A * number of tests to check if two ranges intersect, if a range
592075SN/A * contains a specific address etc. Besides a basic range, the
602068SN/A * AddrRange also support interleaved ranges, to stripe across cache
612068SN/A * banks, or memory controllers. The interleaving is implemented by
622075SN/A * allowing a number of bits of the address, at an arbitrary bit
632075SN/A * position, to be used as interleaving bits with an associated
642068SN/A * matching value. In addition, to prevent uniformly strided address
652068SN/A * patterns from a very biased interleaving, we also allow basic
662068SN/A * XOR-based hashing by specifying an additional set of bits to XOR
672075SN/A * with before matching.
682075SN/A *
692075SN/A * The AddrRange is also able to coalesce a number of interleaved
702075SN/A * ranges to a contiguous range.
712075SN/A */
722075SN/Aclass AddrRange
732075SN/A{
742735Sktlim@umich.edu
752069SN/A  private:
762069SN/A
772075SN/A    /// Private fields for the start and end of the range
782735Sktlim@umich.edu    /// Both _start and _end are part of the range.
792068SN/A    Addr _start;
802068SN/A    Addr _end;
812068SN/A
822075SN/A    /// The high bit of the slice that is used for interleaving
832068SN/A    uint8_t intlvHighBit;
842069SN/A
852068SN/A    /// The high bit of the slice used to XOR hash the value we match
862068SN/A    /// against, set to 0 to disable.
872336SN/A    uint8_t xorHighBit;
882075SN/A
892068SN/A    /// The number of bits used for interleaving, set to 0 to disable
902069SN/A    uint8_t intlvBits;
912068SN/A
922068SN/A    /// The value to compare the slice addr[high:(high - bits + 1)]
932068SN/A    /// with.
942068SN/A    uint8_t intlvMatch;
952068SN/A
962068SN/A  public:
972068SN/A
982068SN/A    AddrRange()
992336SN/A        : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
1002068SN/A          intlvMatch(0)
1012068SN/A    {}
1022068SN/A
1032068SN/A    AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
1042068SN/A              uint8_t _xor_high_bit, uint8_t _intlv_bits,
1052068SN/A              uint8_t _intlv_match)
1062068SN/A        : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
1072068SN/A          xorHighBit(_xor_high_bit), intlvBits(_intlv_bits),
1082068SN/A          intlvMatch(_intlv_match)
1092068SN/A    {
1102068SN/A        // sanity checks
1112068SN/A        fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits,
1122147SN/A                 "Match value %d does not fit in %d interleaving bits\n",
1132068SN/A                 intlvMatch, intlvBits);
1142068SN/A
1152068SN/A        // ignore the XOR bits if not interleaving
1162068SN/A        if (intlvBits && xorHighBit) {
1172068SN/A            if (xorHighBit == intlvHighBit) {
1182068SN/A                fatal("XOR and interleave high bit must be different\n");
1192068SN/A            }  else if (xorHighBit > intlvHighBit) {
1202068SN/A                if ((xorHighBit - intlvHighBit) < intlvBits)
1212068SN/A                    fatal("XOR and interleave high bit must be at least "
1222068SN/A                          "%d bits apart\n", intlvBits);
1232068SN/A            } else {
1242147SN/A                if ((intlvHighBit - xorHighBit) < intlvBits) {
1252068SN/A                    fatal("Interleave and XOR high bit must be at least "
1262068SN/A                          "%d bits apart\n", intlvBits);
1272068SN/A                }
1282068SN/A            }
1292068SN/A        }
1302068SN/A    }
1312068SN/A
1322068SN/A    AddrRange(Addr _start, Addr _end)
1332068SN/A        : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0),
1342068SN/A          intlvBits(0), intlvMatch(0)
1352068SN/A    {}
1362068SN/A
1372068SN/A    /**
1382147SN/A     * Create an address range by merging a collection of interleaved
1392068SN/A     * ranges.
1402068SN/A     *
1412068SN/A     * @param ranges Interleaved ranges to be merged
1422068SN/A     */
1432068SN/A    AddrRange(const std::vector<AddrRange>& ranges)
1442068SN/A        : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
1452068SN/A          intlvMatch(0)
1462068SN/A    {
1472068SN/A        if (!ranges.empty()) {
1482068SN/A            // get the values from the first one and check the others
1492068SN/A            _start = ranges.front()._start;
1502068SN/A            _end = ranges.front()._end;
1512068SN/A            intlvHighBit = ranges.front().intlvHighBit;
1522147SN/A            xorHighBit = ranges.front().xorHighBit;
1532068SN/A            intlvBits = ranges.front().intlvBits;
1542068SN/A
1552068SN/A            if (ranges.size() != (ULL(1) << intlvBits))
1562068SN/A                fatal("Got %d ranges spanning %d interleaving bits\n",
1572068SN/A                      ranges.size(), intlvBits);
1582068SN/A
1592068SN/A            uint8_t match = 0;
1602068SN/A            for (const auto& r : ranges) {
1612068SN/A                if (!mergesWith(r))
1622068SN/A                    fatal("Can only merge ranges with the same start, end "
1632068SN/A                          "and interleaving bits\n");
1642068SN/A
1652068SN/A                if (r.intlvMatch != match)
1662068SN/A                    fatal("Expected interleave match %d but got %d when "
1672068SN/A                          "merging\n", match, r.intlvMatch);
1682068SN/A                ++match;
1692068SN/A            }
1702068SN/A
1712068SN/A            // our range is complete and we can turn this into a
1722068SN/A            // non-interleaved range
1732068SN/A            intlvHighBit = 0;
1742068SN/A            xorHighBit = 0;
1752068SN/A            intlvBits = 0;
1762068SN/A        }
1772068SN/A    }
1782068SN/A
1792068SN/A    /**
1802068SN/A     * Determine if the range is interleaved or not.
1812068SN/A     *
1822068SN/A     * @return true if interleaved
1832068SN/A     */
1842068SN/A    bool interleaved() const { return intlvBits != 0; }
1852068SN/A
1862068SN/A    /**
1872068SN/A     * Determine if the range interleaving is hashed or not.
1882068SN/A     */
1892068SN/A    bool hashed() const { return interleaved() && xorHighBit != 0; }
1902068SN/A
1912068SN/A    /**
1922068SN/A     * Determing the interleaving granularity of the range.
1932068SN/A     *
1942068SN/A     * @return The size of the regions created by the interleaving bits
1952068SN/A     */
1962068SN/A    uint64_t granularity() const
1972068SN/A    {
1982068SN/A        return ULL(1) << (intlvHighBit - intlvBits + 1);
1992068SN/A    }
2002068SN/A
2012068SN/A    /**
2022068SN/A     * Determine the number of interleaved address stripes this range
2032068SN/A     * is part of.
2042068SN/A     *
2052068SN/A     * @return The number of stripes spanned by the interleaving bits
2062068SN/A     */
2072068SN/A    uint32_t stripes() const { return ULL(1) << intlvBits; }
2082068SN/A
2092068SN/A    /**
2102068SN/A     * Get the size of the address range. For a case where
2112068SN/A     * interleaving is used we make the simplifying assumption that
2122068SN/A     * the size is a divisible by the size of the interleaving slice.
2132068SN/A     */
2142068SN/A    Addr size() const
2152068SN/A    {
2162068SN/A        return (_end - _start + 1) >> intlvBits;
2172068SN/A    }
2182068SN/A
2192068SN/A    /**
2202068SN/A     * Determine if the range is valid.
2212068SN/A     */
2222068SN/A    bool valid() const { return _start <= _end; }
2232068SN/A
2242068SN/A    /**
2252068SN/A     * Get the start address of the range.
2262068SN/A     */
2272068SN/A    Addr start() const { return _start; }
2282068SN/A
2292068SN/A    /**
2302068SN/A     * Get a string representation of the range. This could
2312068SN/A     * alternatively be implemented as a operator<<, but at the moment
2322068SN/A     * that seems like overkill.
2332068SN/A     */
2342068SN/A    std::string to_string() const
2352068SN/A    {
2362068SN/A        if (interleaved()) {
2372068SN/A            if (hashed()) {
2382068SN/A                return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d",
2392068SN/A                                _start, _end,
2402068SN/A                                intlvHighBit, intlvHighBit - intlvBits + 1,
2412068SN/A                                xorHighBit, xorHighBit - intlvBits + 1,
2422068SN/A                                intlvMatch);
2432068SN/A            } else {
2442068SN/A                return csprintf("[%#llx : %#llx], [%d : %d] = %d",
2452068SN/A                                _start, _end,
2462068SN/A                                intlvHighBit, intlvHighBit - intlvBits + 1,
2472068SN/A                                intlvMatch);
2482068SN/A            }
2492068SN/A        } else {
2502068SN/A            return csprintf("[%#llx : %#llx]", _start, _end);
2512068SN/A        }
2522068SN/A    }
2532068SN/A
2542068SN/A    /**
2552068SN/A     * Determine if another range merges with the current one, i.e. if
2562068SN/A     * they are part of the same contigous range and have the same
2572068SN/A     * interleaving bits.
2582068SN/A     *
2592068SN/A     * @param r Range to evaluate merging with
2602068SN/A     * @return true if the two ranges would merge
2612068SN/A     */
2622068SN/A    bool mergesWith(const AddrRange& r) const
2632068SN/A    {
2642068SN/A        return r._start == _start && r._end == _end &&
2652068SN/A            r.intlvHighBit == intlvHighBit &&
2662068SN/A            r.xorHighBit == xorHighBit &&
2672068SN/A            r.intlvBits == intlvBits;
2682068SN/A    }
2692068SN/A
2702068SN/A    /**
2712068SN/A     * Determine if another range intersects this one, i.e. if there
2722068SN/A     * is an address that is both in this range and the other
2732068SN/A     * range. No check is made to ensure either range is valid.
2742068SN/A     *
2752068SN/A     * @param r Range to intersect with
2762068SN/A     * @return true if the intersection of the two ranges is not empty
2772068SN/A     */
2782068SN/A    bool intersects(const AddrRange& r) const
2792068SN/A    {
2802068SN/A        if (!interleaved()) {
2812068SN/A            return _start <= r._end && _end >= r._start;
2822068SN/A        }
2832068SN/A
2842068SN/A        // the current range is interleaved, split the check up in
2852068SN/A        // three cases
2862068SN/A        if (r.size() == 1)
2872068SN/A            // keep it simple and check if the address is within
2882068SN/A            // this range
2892068SN/A            return contains(r.start());
2902068SN/A        else if (!r.interleaved())
2912068SN/A            // be conservative and ignore the interleaving
2922068SN/A            return _start <= r._end && _end >= r._start;
2932068SN/A        else if (mergesWith(r))
2942068SN/A            // restrict the check to ranges that belong to the
2952068SN/A            // same chunk
2962068SN/A            return intlvMatch == r.intlvMatch;
2972068SN/A        else
2982068SN/A            panic("Cannot test intersection of interleaved range %s\n",
2992068SN/A                  to_string());
3002068SN/A    }
3012068SN/A
3022068SN/A    /**
3032068SN/A     * Determine if this range is a subset of another range, i.e. if
3042068SN/A     * every address in this range is also in the other range. No
3052068SN/A     * check is made to ensure either range is valid.
3062068SN/A     *
3072068SN/A     * @param r Range to compare with
3082068SN/A     * @return true if the this range is a subset of the other one
3092068SN/A     */
3102068SN/A    bool isSubset(const AddrRange& r) const
3112068SN/A    {
3122068SN/A        if (interleaved())
3132147SN/A            panic("Cannot test subset of interleaved range %s\n", to_string());
3142068SN/A        return _start >= r._start && _end <= r._end;
3152068SN/A    }
3162068SN/A
3172068SN/A    /**
3182068SN/A     * Determine if the range contains an address.
3192068SN/A     *
3202068SN/A     * @param a Address to compare with
3212068SN/A     * @return true if the address is in the range
3222068SN/A     */
3232068SN/A    bool contains(const Addr& a) const
3242147SN/A    {
3252068SN/A        // check if the address is in the range and if there is either
3262068SN/A        // no interleaving, or with interleaving also if the selected
3272068SN/A        // bits from the address match the interleaving value
3282068SN/A        bool in_range = a >= _start && a <= _end;
3292068SN/A        if (!interleaved()) {
3302068SN/A            return in_range;
3312068SN/A        } else if (in_range) {
3322068SN/A            if (!hashed()) {
3332068SN/A                return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
3342068SN/A                    intlvMatch;
3352068SN/A            } else {
3362068SN/A                return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^
3372068SN/A                        bits(a, xorHighBit, xorHighBit - intlvBits + 1)) ==
3382068SN/A                    intlvMatch;
3392068SN/A            }
3402068SN/A        }
3412068SN/A        return false;
3422068SN/A    }
3432068SN/A
3442068SN/A/**
3452068SN/A * Keep the operators away from SWIG.
3462068SN/A */
3472068SN/A#ifndef SWIG
3482068SN/A
3492068SN/A    /**
3502068SN/A     * Less-than operator used to turn an STL map into a binary search
3512068SN/A     * tree of non-overlapping address ranges.
3522068SN/A     *
3532068SN/A     * @param r Range to compare with
3542068SN/A     * @return true if the start address is less than that of the other range
3552068SN/A     */
3562068SN/A    bool operator<(const AddrRange& r) const
3572068SN/A    {
3582068SN/A        if (_start != r._start)
3592068SN/A            return _start < r._start;
3602068SN/A        else
3612068SN/A            // for now assume that the end is also the same, and that
3622068SN/A            // we are looking at the same interleaving bits
3632068SN/A            return intlvMatch < r.intlvMatch;
3642068SN/A    }
3652068SN/A
3662068SN/A#endif // SWIG
3672068SN/A};
3682068SN/A
3692068SN/A/**
3702068SN/A * Convenience typedef for a collection of address ranges
3712068SN/A */
3722068SN/Atypedef std::list<AddrRange> AddrRangeList;
3732068SN/A
3742068SN/Ainline AddrRange
3752068SN/ARangeEx(Addr start, Addr end)
3762068SN/A{ return AddrRange(start, end - 1); }
3772068SN/A
3782068SN/Ainline AddrRange
3792068SN/ARangeIn(Addr start, Addr end)
3802068SN/A{ return AddrRange(start, end); }
3812068SN/A
3822068SN/Ainline AddrRange
3832068SN/ARangeSize(Addr start, Addr size)
3842068SN/A{ return AddrRange(start, start + size - 1); }
3852068SN/A
3862068SN/A#endif // __BASE_ADDR_RANGE_HH__
3872068SN/A