addr_range.hh revision 9581
12SN/A/* 29235Sandreas.hansson@arm.com * Copyright (c) 2012 ARM Limited 39235Sandreas.hansson@arm.com * All rights reserved 49235Sandreas.hansson@arm.com * 59235Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 69235Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 79235Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 89235Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 99235Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 109235Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 119235Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 129235Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 139235Sandreas.hansson@arm.com * 141762SN/A * Copyright (c) 2002-2005 The Regents of The University of Michigan 152SN/A * All rights reserved. 162SN/A * 172SN/A * Redistribution and use in source and binary forms, with or without 182SN/A * modification, are permitted provided that the following conditions are 192SN/A * met: redistributions of source code must retain the above copyright 202SN/A * notice, this list of conditions and the following disclaimer; 212SN/A * redistributions in binary form must reproduce the above copyright 222SN/A * notice, this list of conditions and the following disclaimer in the 232SN/A * documentation and/or other materials provided with the distribution; 242SN/A * neither the name of the copyright holders nor the names of its 252SN/A * contributors may be used to endorse or promote products derived from 262SN/A * this software without specific prior written permission. 272SN/A * 282SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392665SN/A * 402665SN/A * Authors: Nathan Binkert 412665SN/A * Steve Reinhardt 429235Sandreas.hansson@arm.com * Andreas Hansson 432SN/A */ 442SN/A 459235Sandreas.hansson@arm.com#ifndef __BASE_ADDR_RANGE_HH__ 469235Sandreas.hansson@arm.com#define __BASE_ADDR_RANGE_HH__ 472SN/A 489412Sandreas.hansson@arm.com#include <vector> 499412Sandreas.hansson@arm.com 509411Sandreas.hansson@arm.com#include "base/bitfield.hh" 519405Sandreas.hansson@arm.com#include "base/cprintf.hh" 529411Sandreas.hansson@arm.com#include "base/misc.hh" 539235Sandreas.hansson@arm.com#include "base/types.hh" 549235Sandreas.hansson@arm.com 559235Sandreas.hansson@arm.comclass AddrRange 562SN/A{ 572SN/A 589405Sandreas.hansson@arm.com private: 599405Sandreas.hansson@arm.com 609411Sandreas.hansson@arm.com /// Private fields for the start and end of the range 619405Sandreas.hansson@arm.com Addr _start; 629405Sandreas.hansson@arm.com Addr _end; 639405Sandreas.hansson@arm.com 649411Sandreas.hansson@arm.com /// The high bit of the slice that is used for interleaving 659411Sandreas.hansson@arm.com uint8_t intlvHighBit; 669411Sandreas.hansson@arm.com 679411Sandreas.hansson@arm.com /// The number of bits used for interleaving, set to 0 to disable 689411Sandreas.hansson@arm.com uint8_t intlvBits; 699411Sandreas.hansson@arm.com 709411Sandreas.hansson@arm.com /// The value to compare the slice addr[high:(high - bits + 1)] 719411Sandreas.hansson@arm.com /// with. 729411Sandreas.hansson@arm.com uint8_t intlvMatch; 739411Sandreas.hansson@arm.com 749235Sandreas.hansson@arm.com public: 752SN/A 769235Sandreas.hansson@arm.com AddrRange() 779411Sandreas.hansson@arm.com : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) 789411Sandreas.hansson@arm.com {} 799411Sandreas.hansson@arm.com 809411Sandreas.hansson@arm.com AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 819411Sandreas.hansson@arm.com uint8_t _intlv_bits, uint8_t _intlv_match) 829411Sandreas.hansson@arm.com : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), 839411Sandreas.hansson@arm.com intlvBits(_intlv_bits), intlvMatch(_intlv_match) 849235Sandreas.hansson@arm.com {} 859235Sandreas.hansson@arm.com 869235Sandreas.hansson@arm.com AddrRange(Addr _start, Addr _end) 879411Sandreas.hansson@arm.com : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0), 889411Sandreas.hansson@arm.com intlvMatch(0) 899235Sandreas.hansson@arm.com {} 909235Sandreas.hansson@arm.com 919405Sandreas.hansson@arm.com /** 929412Sandreas.hansson@arm.com * Create an address range by merging a collection of interleaved 939412Sandreas.hansson@arm.com * ranges. 949412Sandreas.hansson@arm.com * 959412Sandreas.hansson@arm.com * @param ranges Interleaved ranges to be merged 969412Sandreas.hansson@arm.com */ 979412Sandreas.hansson@arm.com AddrRange(const std::vector<AddrRange>& ranges) 989412Sandreas.hansson@arm.com : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) 999412Sandreas.hansson@arm.com { 1009412Sandreas.hansson@arm.com if (!ranges.empty()) { 1019412Sandreas.hansson@arm.com // get the values from the first one and check the others 1029412Sandreas.hansson@arm.com _start = ranges.front()._start; 1039412Sandreas.hansson@arm.com _end = ranges.front()._end; 1049412Sandreas.hansson@arm.com intlvHighBit = ranges.front().intlvHighBit; 1059412Sandreas.hansson@arm.com intlvBits = ranges.front().intlvBits; 1069412Sandreas.hansson@arm.com 1079412Sandreas.hansson@arm.com if (ranges.size() != (ULL(1) << intlvBits)) 1089412Sandreas.hansson@arm.com fatal("Got %d ranges spanning %d interleaving bits\n", 1099412Sandreas.hansson@arm.com ranges.size(), intlvBits); 1109412Sandreas.hansson@arm.com 1119412Sandreas.hansson@arm.com uint8_t match = 0; 1129412Sandreas.hansson@arm.com for (std::vector<AddrRange>::const_iterator r = ranges.begin(); 1139412Sandreas.hansson@arm.com r != ranges.end(); ++r) { 1149412Sandreas.hansson@arm.com if (!mergesWith(*r)) 1159412Sandreas.hansson@arm.com fatal("Can only merge ranges with the same start, end " 1169412Sandreas.hansson@arm.com "and interleaving bits\n"); 1179412Sandreas.hansson@arm.com 1189412Sandreas.hansson@arm.com if (r->intlvMatch != match) 1199412Sandreas.hansson@arm.com fatal("Expected interleave match %d but got %d when " 1209412Sandreas.hansson@arm.com "merging\n", match, r->intlvMatch); 1219412Sandreas.hansson@arm.com ++match; 1229412Sandreas.hansson@arm.com } 1239412Sandreas.hansson@arm.com 1249412Sandreas.hansson@arm.com // our range is complete and we can turn this into a 1259412Sandreas.hansson@arm.com // non-interleaved range 1269412Sandreas.hansson@arm.com intlvHighBit = 0; 1279412Sandreas.hansson@arm.com intlvBits = 0; 1289412Sandreas.hansson@arm.com } 1299412Sandreas.hansson@arm.com } 1309412Sandreas.hansson@arm.com 1319412Sandreas.hansson@arm.com /** 1329411Sandreas.hansson@arm.com * Determine if the range is interleaved or not. 1339411Sandreas.hansson@arm.com * 1349411Sandreas.hansson@arm.com * @return true if interleaved 1359411Sandreas.hansson@arm.com */ 1369411Sandreas.hansson@arm.com bool interleaved() const { return intlvBits != 0; } 1379411Sandreas.hansson@arm.com 1389411Sandreas.hansson@arm.com /** 1399411Sandreas.hansson@arm.com * Determing the interleaving granularity of the range. 1409411Sandreas.hansson@arm.com * 1419411Sandreas.hansson@arm.com * @return The size of the regions created by the interleaving bits 1429411Sandreas.hansson@arm.com */ 1439581Sandreas.hansson@arm.com uint64_t granularity() const 1449581Sandreas.hansson@arm.com { 1459581Sandreas.hansson@arm.com return ULL(1) << (intlvHighBit - intlvBits); 1469581Sandreas.hansson@arm.com } 1479411Sandreas.hansson@arm.com 1489411Sandreas.hansson@arm.com /** 1499411Sandreas.hansson@arm.com * Determine the number of interleaved address stripes this range 1509411Sandreas.hansson@arm.com * is part of. 1519411Sandreas.hansson@arm.com * 1529411Sandreas.hansson@arm.com * @return The number of stripes spanned by the interleaving bits 1539411Sandreas.hansson@arm.com */ 1549411Sandreas.hansson@arm.com uint32_t stripes() const { return ULL(1) << intlvBits; } 1559411Sandreas.hansson@arm.com 1569411Sandreas.hansson@arm.com /** 1579405Sandreas.hansson@arm.com * Get the size of the address range. For a case where 1589411Sandreas.hansson@arm.com * interleaving is used we make the simplifying assumption that 1599411Sandreas.hansson@arm.com * the size is a divisible by the size of the interleaving slice. 1609405Sandreas.hansson@arm.com */ 1619411Sandreas.hansson@arm.com Addr size() const 1629411Sandreas.hansson@arm.com { 1639411Sandreas.hansson@arm.com return (_end - _start + 1) >> intlvBits; 1649411Sandreas.hansson@arm.com } 165532SN/A 1669405Sandreas.hansson@arm.com /** 1679405Sandreas.hansson@arm.com * Determine if the range is valid. 1689405Sandreas.hansson@arm.com */ 1699405Sandreas.hansson@arm.com bool valid() const { return _start < _end; } 1709405Sandreas.hansson@arm.com 1719405Sandreas.hansson@arm.com /** 1729405Sandreas.hansson@arm.com * Get the start address of the range. 1739405Sandreas.hansson@arm.com */ 1749405Sandreas.hansson@arm.com Addr start() const { return _start; } 1759405Sandreas.hansson@arm.com 1769405Sandreas.hansson@arm.com /** 1779405Sandreas.hansson@arm.com * Get a string representation of the range. This could 1789405Sandreas.hansson@arm.com * alternatively be implemented as a operator<<, but at the moment 1799405Sandreas.hansson@arm.com * that seems like overkill. 1809405Sandreas.hansson@arm.com */ 1819405Sandreas.hansson@arm.com std::string to_string() const 1829405Sandreas.hansson@arm.com { 1839411Sandreas.hansson@arm.com if (interleaved()) 1849411Sandreas.hansson@arm.com return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end, 1859411Sandreas.hansson@arm.com intlvHighBit, intlvHighBit - intlvBits + 1, 1869411Sandreas.hansson@arm.com intlvMatch); 1879411Sandreas.hansson@arm.com else 1889411Sandreas.hansson@arm.com return csprintf("[%#llx : %#llx]", _start, _end); 1899411Sandreas.hansson@arm.com } 1909411Sandreas.hansson@arm.com 1919411Sandreas.hansson@arm.com /** 1929411Sandreas.hansson@arm.com * Determine if another range merges with the current one, i.e. if 1939411Sandreas.hansson@arm.com * they are part of the same contigous range and have the same 1949411Sandreas.hansson@arm.com * interleaving bits. 1959411Sandreas.hansson@arm.com * 1969411Sandreas.hansson@arm.com * @param r Range to evaluate merging with 1979411Sandreas.hansson@arm.com * @return true if the two ranges would merge 1989411Sandreas.hansson@arm.com */ 1999411Sandreas.hansson@arm.com bool mergesWith(const AddrRange& r) const 2009411Sandreas.hansson@arm.com { 2019411Sandreas.hansson@arm.com return r._start == _start && r._end == _end && 2029411Sandreas.hansson@arm.com r.intlvHighBit == intlvHighBit && 2039411Sandreas.hansson@arm.com r.intlvBits == intlvBits; 2049405Sandreas.hansson@arm.com } 2059279Sandreas.hansson@arm.com 2069279Sandreas.hansson@arm.com /** 2079279Sandreas.hansson@arm.com * Determine if another range intersects this one, i.e. if there 2089279Sandreas.hansson@arm.com * is an address that is both in this range and the other 2099279Sandreas.hansson@arm.com * range. No check is made to ensure either range is valid. 2109279Sandreas.hansson@arm.com * 2119279Sandreas.hansson@arm.com * @param r Range to intersect with 2129279Sandreas.hansson@arm.com * @return true if the intersection of the two ranges is not empty 2139279Sandreas.hansson@arm.com */ 2149279Sandreas.hansson@arm.com bool intersects(const AddrRange& r) const 2159279Sandreas.hansson@arm.com { 2169411Sandreas.hansson@arm.com if (!interleaved()) { 2179411Sandreas.hansson@arm.com return _start <= r._end && _end >= r._start; 2189411Sandreas.hansson@arm.com } 2199411Sandreas.hansson@arm.com 2209411Sandreas.hansson@arm.com // the current range is interleaved, split the check up in 2219411Sandreas.hansson@arm.com // three cases 2229411Sandreas.hansson@arm.com if (r.size() == 1) 2239411Sandreas.hansson@arm.com // keep it simple and check if the address is within 2249411Sandreas.hansson@arm.com // this range 2259411Sandreas.hansson@arm.com return contains(r.start()); 2269411Sandreas.hansson@arm.com else if (!r.interleaved()) 2279411Sandreas.hansson@arm.com // be conservative and ignore the interleaving 2289411Sandreas.hansson@arm.com return _start <= r._end && _end >= r._start; 2299411Sandreas.hansson@arm.com else if (mergesWith(r)) 2309411Sandreas.hansson@arm.com // restrict the check to ranges that belong to the 2319411Sandreas.hansson@arm.com // same chunk 2329411Sandreas.hansson@arm.com return intlvMatch == r.intlvMatch; 2339411Sandreas.hansson@arm.com else 2349411Sandreas.hansson@arm.com panic("Cannot test intersection of interleaved range %s\n", 2359411Sandreas.hansson@arm.com to_string()); 2369279Sandreas.hansson@arm.com } 2379279Sandreas.hansson@arm.com 2389279Sandreas.hansson@arm.com /** 2399279Sandreas.hansson@arm.com * Determine if this range is a subset of another range, i.e. if 2409279Sandreas.hansson@arm.com * every address in this range is also in the other range. No 2419279Sandreas.hansson@arm.com * check is made to ensure either range is valid. 2429279Sandreas.hansson@arm.com * 2439279Sandreas.hansson@arm.com * @param r Range to compare with 2449279Sandreas.hansson@arm.com * @return true if the this range is a subset of the other one 2459279Sandreas.hansson@arm.com */ 2469279Sandreas.hansson@arm.com bool isSubset(const AddrRange& r) const 2479279Sandreas.hansson@arm.com { 2489411Sandreas.hansson@arm.com if (interleaved()) 2499411Sandreas.hansson@arm.com panic("Cannot test subset of interleaved range %s\n", to_string()); 2509405Sandreas.hansson@arm.com return _start >= r._start && _end <= r._end; 2519279Sandreas.hansson@arm.com } 2529405Sandreas.hansson@arm.com 2539405Sandreas.hansson@arm.com /** 2549405Sandreas.hansson@arm.com * Determine if the range contains an address. 2559405Sandreas.hansson@arm.com * 2569405Sandreas.hansson@arm.com * @param a Address to compare with 2579405Sandreas.hansson@arm.com * @return true if the address is in the range 2589405Sandreas.hansson@arm.com */ 2599405Sandreas.hansson@arm.com bool contains(const Addr& a) const 2609405Sandreas.hansson@arm.com { 2619411Sandreas.hansson@arm.com // check if the address is in the range and if there is either 2629411Sandreas.hansson@arm.com // no interleaving, or with interleaving also if the selected 2639411Sandreas.hansson@arm.com // bits from the address match the interleaving value 2649411Sandreas.hansson@arm.com return a >= _start && a <= _end && 2659541Sandreas.hansson@arm.com (!interleaved() || 2669411Sandreas.hansson@arm.com (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == 2679411Sandreas.hansson@arm.com intlvMatch)); 2689405Sandreas.hansson@arm.com } 2692SN/A 270531SN/A/** 2719235Sandreas.hansson@arm.com * Keep the operators away from SWIG. 272531SN/A */ 2739235Sandreas.hansson@arm.com#ifndef SWIG 2742SN/A 2759405Sandreas.hansson@arm.com /** 2769405Sandreas.hansson@arm.com * Less-than operator used to turn an STL map into a binary search 2779405Sandreas.hansson@arm.com * tree of non-overlapping address ranges. 2789405Sandreas.hansson@arm.com * 2799405Sandreas.hansson@arm.com * @param r Range to compare with 2809405Sandreas.hansson@arm.com * @return true if the start address is less than that of the other range 2819405Sandreas.hansson@arm.com */ 2829405Sandreas.hansson@arm.com bool operator<(const AddrRange& r) const 2839405Sandreas.hansson@arm.com { 2849411Sandreas.hansson@arm.com if (_start != r._start) 2859411Sandreas.hansson@arm.com return _start < r._start; 2869411Sandreas.hansson@arm.com else 2879411Sandreas.hansson@arm.com // for now assume that the end is also the same, and that 2889411Sandreas.hansson@arm.com // we are looking at the same interleaving bits 2899411Sandreas.hansson@arm.com return intlvMatch < r.intlvMatch; 2909405Sandreas.hansson@arm.com } 291531SN/A 2929405Sandreas.hansson@arm.com#endif // SWIG 2939405Sandreas.hansson@arm.com}; 2942SN/A 2959235Sandreas.hansson@arm.cominline AddrRange 2969235Sandreas.hansson@arm.comRangeEx(Addr start, Addr end) 2979405Sandreas.hansson@arm.com{ return AddrRange(start, end - 1); } 2982SN/A 2999235Sandreas.hansson@arm.cominline AddrRange 3009235Sandreas.hansson@arm.comRangeIn(Addr start, Addr end) 3019405Sandreas.hansson@arm.com{ return AddrRange(start, end); } 3022SN/A 3039235Sandreas.hansson@arm.cominline AddrRange 3049235Sandreas.hansson@arm.comRangeSize(Addr start, Addr size) 3059405Sandreas.hansson@arm.com{ return AddrRange(start, start + size - 1); } 3062SN/A 3079235Sandreas.hansson@arm.com#endif // __BASE_ADDR_RANGE_HH__ 308