addr_range.hh revision 10435
1/* 2 * Copyright (c) 2012 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2002-2005 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Nathan Binkert 41 * Steve Reinhardt 42 * Andreas Hansson 43 */ 44 45#ifndef __BASE_ADDR_RANGE_HH__ 46#define __BASE_ADDR_RANGE_HH__ 47 48#include <vector> 49 50#include "base/bitfield.hh" 51#include "base/cprintf.hh" 52#include "base/misc.hh" 53#include "base/types.hh" 54 55class AddrRange 56{ 57 58 private: 59 60 /// Private fields for the start and end of the range 61 /// Both _start and _end are part of the range. 62 Addr _start; 63 Addr _end; 64 65 /// The high bit of the slice that is used for interleaving 66 uint8_t intlvHighBit; 67 68 /// The number of bits used for interleaving, set to 0 to disable 69 uint8_t intlvBits; 70 71 /// The value to compare the slice addr[high:(high - bits + 1)] 72 /// with. 73 uint8_t intlvMatch; 74 75 public: 76 77 AddrRange() 78 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) 79 {} 80 81 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 82 uint8_t _intlv_bits, uint8_t _intlv_match) 83 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), 84 intlvBits(_intlv_bits), intlvMatch(_intlv_match) 85 {} 86 87 AddrRange(Addr _start, Addr _end) 88 : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0), 89 intlvMatch(0) 90 {} 91 92 /** 93 * Create an address range by merging a collection of interleaved 94 * ranges. 95 * 96 * @param ranges Interleaved ranges to be merged 97 */ 98 AddrRange(const std::vector<AddrRange>& ranges) 99 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) 100 { 101 if (!ranges.empty()) { 102 // get the values from the first one and check the others 103 _start = ranges.front()._start; 104 _end = ranges.front()._end; 105 intlvHighBit = ranges.front().intlvHighBit; 106 intlvBits = ranges.front().intlvBits; 107 108 if (ranges.size() != (ULL(1) << intlvBits)) 109 fatal("Got %d ranges spanning %d interleaving bits\n", 110 ranges.size(), intlvBits); 111 112 uint8_t match = 0; 113 for (std::vector<AddrRange>::const_iterator r = ranges.begin(); 114 r != ranges.end(); ++r) { 115 if (!mergesWith(*r)) 116 fatal("Can only merge ranges with the same start, end " 117 "and interleaving bits\n"); 118 119 if (r->intlvMatch != match) 120 fatal("Expected interleave match %d but got %d when " 121 "merging\n", match, r->intlvMatch); 122 ++match; 123 } 124 125 // our range is complete and we can turn this into a 126 // non-interleaved range 127 intlvHighBit = 0; 128 intlvBits = 0; 129 } 130 } 131 132 /** 133 * Determine if the range is interleaved or not. 134 * 135 * @return true if interleaved 136 */ 137 bool interleaved() const { return intlvBits != 0; } 138 139 /** 140 * Determing the interleaving granularity of the range. 141 * 142 * @return The size of the regions created by the interleaving bits 143 */ 144 uint64_t granularity() const 145 { 146 return ULL(1) << (intlvHighBit - intlvBits + 1); 147 } 148 149 /** 150 * Determine the number of interleaved address stripes this range 151 * is part of. 152 * 153 * @return The number of stripes spanned by the interleaving bits 154 */ 155 uint32_t stripes() const { return ULL(1) << intlvBits; } 156 157 /** 158 * Get the size of the address range. For a case where 159 * interleaving is used we make the simplifying assumption that 160 * the size is a divisible by the size of the interleaving slice. 161 */ 162 Addr size() const 163 { 164 return (_end - _start + 1) >> intlvBits; 165 } 166 167 /** 168 * Determine if the range is valid. 169 */ 170 bool valid() const { return _start <= _end; } 171 172 /** 173 * Get the start address of the range. 174 */ 175 Addr start() const { return _start; } 176 177 /** 178 * Get a string representation of the range. This could 179 * alternatively be implemented as a operator<<, but at the moment 180 * that seems like overkill. 181 */ 182 std::string to_string() const 183 { 184 if (interleaved()) 185 return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end, 186 intlvHighBit, intlvHighBit - intlvBits + 1, 187 intlvMatch); 188 else 189 return csprintf("[%#llx : %#llx]", _start, _end); 190 } 191 192 /** 193 * Determine if another range merges with the current one, i.e. if 194 * they are part of the same contigous range and have the same 195 * interleaving bits. 196 * 197 * @param r Range to evaluate merging with 198 * @return true if the two ranges would merge 199 */ 200 bool mergesWith(const AddrRange& r) const 201 { 202 return r._start == _start && r._end == _end && 203 r.intlvHighBit == intlvHighBit && 204 r.intlvBits == intlvBits; 205 } 206 207 /** 208 * Determine if another range intersects this one, i.e. if there 209 * is an address that is both in this range and the other 210 * range. No check is made to ensure either range is valid. 211 * 212 * @param r Range to intersect with 213 * @return true if the intersection of the two ranges is not empty 214 */ 215 bool intersects(const AddrRange& r) const 216 { 217 if (!interleaved()) { 218 return _start <= r._end && _end >= r._start; 219 } 220 221 // the current range is interleaved, split the check up in 222 // three cases 223 if (r.size() == 1) 224 // keep it simple and check if the address is within 225 // this range 226 return contains(r.start()); 227 else if (!r.interleaved()) 228 // be conservative and ignore the interleaving 229 return _start <= r._end && _end >= r._start; 230 else if (mergesWith(r)) 231 // restrict the check to ranges that belong to the 232 // same chunk 233 return intlvMatch == r.intlvMatch; 234 else 235 panic("Cannot test intersection of interleaved range %s\n", 236 to_string()); 237 } 238 239 /** 240 * Determine if this range is a subset of another range, i.e. if 241 * every address in this range is also in the other range. No 242 * check is made to ensure either range is valid. 243 * 244 * @param r Range to compare with 245 * @return true if the this range is a subset of the other one 246 */ 247 bool isSubset(const AddrRange& r) const 248 { 249 if (interleaved()) 250 panic("Cannot test subset of interleaved range %s\n", to_string()); 251 return _start >= r._start && _end <= r._end; 252 } 253 254 /** 255 * Determine if the range contains an address. 256 * 257 * @param a Address to compare with 258 * @return true if the address is in the range 259 */ 260 bool contains(const Addr& a) const 261 { 262 // check if the address is in the range and if there is either 263 // no interleaving, or with interleaving also if the selected 264 // bits from the address match the interleaving value 265 return a >= _start && a <= _end && 266 (!interleaved() || 267 (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == 268 intlvMatch)); 269 } 270 271/** 272 * Keep the operators away from SWIG. 273 */ 274#ifndef SWIG 275 276 /** 277 * Less-than operator used to turn an STL map into a binary search 278 * tree of non-overlapping address ranges. 279 * 280 * @param r Range to compare with 281 * @return true if the start address is less than that of the other range 282 */ 283 bool operator<(const AddrRange& r) const 284 { 285 if (_start != r._start) 286 return _start < r._start; 287 else 288 // for now assume that the end is also the same, and that 289 // we are looking at the same interleaving bits 290 return intlvMatch < r.intlvMatch; 291 } 292 293#endif // SWIG 294}; 295 296inline AddrRange 297RangeEx(Addr start, Addr end) 298{ return AddrRange(start, end - 1); } 299 300inline AddrRange 301RangeIn(Addr start, Addr end) 302{ return AddrRange(start, end); } 303 304inline AddrRange 305RangeSize(Addr start, Addr size) 306{ return AddrRange(start, start + size - 1); } 307 308#endif // __BASE_ADDR_RANGE_HH__ 309