addr_range.hh revision 10676:f6c168692b20
1/* 2 * Copyright (c) 2012, 2014 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 <list> 49#include <vector> 50 51#include "base/bitfield.hh" 52#include "base/cprintf.hh" 53#include "base/misc.hh" 54#include "base/types.hh" 55 56/** 57 * The AddrRange class encapsulates an address range, and supports a 58 * number of tests to check if two ranges intersect, if a range 59 * contains a specific address etc. Besides a basic range, the 60 * AddrRange also support interleaved ranges, to stripe across cache 61 * banks, or memory controllers. The interleaving is implemented by 62 * allowing a number of bits of the address, at an arbitrary bit 63 * position, to be used as interleaving bits with an associated 64 * matching value. In addition, to prevent uniformly strided address 65 * patterns from a very biased interleaving, we also allow basic 66 * XOR-based hashing by specifying an additional set of bits to XOR 67 * with before matching. 68 * 69 * The AddrRange is also able to coalesce a number of interleaved 70 * ranges to a contiguous range. 71 */ 72class AddrRange 73{ 74 75 private: 76 77 /// Private fields for the start and end of the range 78 /// Both _start and _end are part of the range. 79 Addr _start; 80 Addr _end; 81 82 /// The high bit of the slice that is used for interleaving 83 uint8_t intlvHighBit; 84 85 /// The high bit of the slice used to XOR hash the value we match 86 /// against, set to 0 to disable. 87 uint8_t xorHighBit; 88 89 /// The number of bits used for interleaving, set to 0 to disable 90 uint8_t intlvBits; 91 92 /// The value to compare the slice addr[high:(high - bits + 1)] 93 /// with. 94 uint8_t intlvMatch; 95 96 public: 97 98 AddrRange() 99 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), 100 intlvMatch(0) 101 {} 102 103 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 104 uint8_t _xor_high_bit, uint8_t _intlv_bits, 105 uint8_t _intlv_match) 106 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), 107 xorHighBit(_xor_high_bit), intlvBits(_intlv_bits), 108 intlvMatch(_intlv_match) 109 { 110 // sanity checks 111 fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits, 112 "Match value %d does not fit in %d interleaving bits\n", 113 intlvMatch, intlvBits); 114 115 // ignore the XOR bits if not interleaving 116 if (intlvBits && xorHighBit) { 117 if (xorHighBit == intlvHighBit) { 118 fatal("XOR and interleave high bit must be different\n"); 119 } else if (xorHighBit > intlvHighBit) { 120 if ((xorHighBit - intlvHighBit) < intlvBits) 121 fatal("XOR and interleave high bit must be at least " 122 "%d bits apart\n", intlvBits); 123 } else { 124 if ((intlvHighBit - xorHighBit) < intlvBits) { 125 fatal("Interleave and XOR high bit must be at least " 126 "%d bits apart\n", intlvBits); 127 } 128 } 129 } 130 } 131 132 AddrRange(Addr _start, Addr _end) 133 : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0), 134 intlvBits(0), intlvMatch(0) 135 {} 136 137 /** 138 * Create an address range by merging a collection of interleaved 139 * ranges. 140 * 141 * @param ranges Interleaved ranges to be merged 142 */ 143 AddrRange(const std::vector<AddrRange>& ranges) 144 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), 145 intlvMatch(0) 146 { 147 if (!ranges.empty()) { 148 // get the values from the first one and check the others 149 _start = ranges.front()._start; 150 _end = ranges.front()._end; 151 intlvHighBit = ranges.front().intlvHighBit; 152 xorHighBit = ranges.front().xorHighBit; 153 intlvBits = ranges.front().intlvBits; 154 155 if (ranges.size() != (ULL(1) << intlvBits)) 156 fatal("Got %d ranges spanning %d interleaving bits\n", 157 ranges.size(), intlvBits); 158 159 uint8_t match = 0; 160 for (const auto& r : ranges) { 161 if (!mergesWith(r)) 162 fatal("Can only merge ranges with the same start, end " 163 "and interleaving bits\n"); 164 165 if (r.intlvMatch != match) 166 fatal("Expected interleave match %d but got %d when " 167 "merging\n", match, r.intlvMatch); 168 ++match; 169 } 170 171 // our range is complete and we can turn this into a 172 // non-interleaved range 173 intlvHighBit = 0; 174 xorHighBit = 0; 175 intlvBits = 0; 176 } 177 } 178 179 /** 180 * Determine if the range is interleaved or not. 181 * 182 * @return true if interleaved 183 */ 184 bool interleaved() const { return intlvBits != 0; } 185 186 /** 187 * Determine if the range interleaving is hashed or not. 188 */ 189 bool hashed() const { return interleaved() && xorHighBit != 0; } 190 191 /** 192 * Determing the interleaving granularity of the range. 193 * 194 * @return The size of the regions created by the interleaving bits 195 */ 196 uint64_t granularity() const 197 { 198 return ULL(1) << (intlvHighBit - intlvBits + 1); 199 } 200 201 /** 202 * Determine the number of interleaved address stripes this range 203 * is part of. 204 * 205 * @return The number of stripes spanned by the interleaving bits 206 */ 207 uint32_t stripes() const { return ULL(1) << intlvBits; } 208 209 /** 210 * Get the size of the address range. For a case where 211 * interleaving is used we make the simplifying assumption that 212 * the size is a divisible by the size of the interleaving slice. 213 */ 214 Addr size() const 215 { 216 return (_end - _start + 1) >> intlvBits; 217 } 218 219 /** 220 * Determine if the range is valid. 221 */ 222 bool valid() const { return _start <= _end; } 223 224 /** 225 * Get the start address of the range. 226 */ 227 Addr start() const { return _start; } 228 229 /** 230 * Get a string representation of the range. This could 231 * alternatively be implemented as a operator<<, but at the moment 232 * that seems like overkill. 233 */ 234 std::string to_string() const 235 { 236 if (interleaved()) { 237 if (hashed()) { 238 return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d", 239 _start, _end, 240 intlvHighBit, intlvHighBit - intlvBits + 1, 241 xorHighBit, xorHighBit - intlvBits + 1, 242 intlvMatch); 243 } else { 244 return csprintf("[%#llx : %#llx], [%d : %d] = %d", 245 _start, _end, 246 intlvHighBit, intlvHighBit - intlvBits + 1, 247 intlvMatch); 248 } 249 } else { 250 return csprintf("[%#llx : %#llx]", _start, _end); 251 } 252 } 253 254 /** 255 * Determine if another range merges with the current one, i.e. if 256 * they are part of the same contigous range and have the same 257 * interleaving bits. 258 * 259 * @param r Range to evaluate merging with 260 * @return true if the two ranges would merge 261 */ 262 bool mergesWith(const AddrRange& r) const 263 { 264 return r._start == _start && r._end == _end && 265 r.intlvHighBit == intlvHighBit && 266 r.xorHighBit == xorHighBit && 267 r.intlvBits == intlvBits; 268 } 269 270 /** 271 * Determine if another range intersects this one, i.e. if there 272 * is an address that is both in this range and the other 273 * range. No check is made to ensure either range is valid. 274 * 275 * @param r Range to intersect with 276 * @return true if the intersection of the two ranges is not empty 277 */ 278 bool intersects(const AddrRange& r) const 279 { 280 if (!interleaved()) { 281 return _start <= r._end && _end >= r._start; 282 } 283 284 // the current range is interleaved, split the check up in 285 // three cases 286 if (r.size() == 1) 287 // keep it simple and check if the address is within 288 // this range 289 return contains(r.start()); 290 else if (!r.interleaved()) 291 // be conservative and ignore the interleaving 292 return _start <= r._end && _end >= r._start; 293 else if (mergesWith(r)) 294 // restrict the check to ranges that belong to the 295 // same chunk 296 return intlvMatch == r.intlvMatch; 297 else 298 panic("Cannot test intersection of interleaved range %s\n", 299 to_string()); 300 } 301 302 /** 303 * Determine if this range is a subset of another range, i.e. if 304 * every address in this range is also in the other range. No 305 * check is made to ensure either range is valid. 306 * 307 * @param r Range to compare with 308 * @return true if the this range is a subset of the other one 309 */ 310 bool isSubset(const AddrRange& r) const 311 { 312 if (interleaved()) 313 panic("Cannot test subset of interleaved range %s\n", to_string()); 314 return _start >= r._start && _end <= r._end; 315 } 316 317 /** 318 * Determine if the range contains an address. 319 * 320 * @param a Address to compare with 321 * @return true if the address is in the range 322 */ 323 bool contains(const Addr& a) const 324 { 325 // check if the address is in the range and if there is either 326 // no interleaving, or with interleaving also if the selected 327 // bits from the address match the interleaving value 328 bool in_range = a >= _start && a <= _end; 329 if (!interleaved()) { 330 return in_range; 331 } else if (in_range) { 332 if (!hashed()) { 333 return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == 334 intlvMatch; 335 } else { 336 return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^ 337 bits(a, xorHighBit, xorHighBit - intlvBits + 1)) == 338 intlvMatch; 339 } 340 } 341 return false; 342 } 343 344/** 345 * Keep the operators away from SWIG. 346 */ 347#ifndef SWIG 348 349 /** 350 * Less-than operator used to turn an STL map into a binary search 351 * tree of non-overlapping address ranges. 352 * 353 * @param r Range to compare with 354 * @return true if the start address is less than that of the other range 355 */ 356 bool operator<(const AddrRange& r) const 357 { 358 if (_start != r._start) 359 return _start < r._start; 360 else 361 // for now assume that the end is also the same, and that 362 // we are looking at the same interleaving bits 363 return intlvMatch < r.intlvMatch; 364 } 365 366#endif // SWIG 367}; 368 369/** 370 * Convenience typedef for a collection of address ranges 371 */ 372typedef std::list<AddrRange> AddrRangeList; 373 374inline AddrRange 375RangeEx(Addr start, Addr end) 376{ return AddrRange(start, end - 1); } 377 378inline AddrRange 379RangeIn(Addr start, Addr end) 380{ return AddrRange(start, end); } 381 382inline AddrRange 383RangeSize(Addr start, Addr size) 384{ return AddrRange(start, start + size - 1); } 385 386#endif // __BASE_ADDR_RANGE_HH__ 387