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