1/* 2 * Copyright (c) 2012, 2014, 2017-2019 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 <algorithm> 49#include <list> 50#include <vector> 51 52#include "base/bitfield.hh" 53#include "base/cprintf.hh" 54#include "base/logging.hh" 55#include "base/types.hh" 56 57/** 58 * The AddrRange class encapsulates an address range, and supports a 59 * number of tests to check if two ranges intersect, if a range 60 * contains a specific address etc. Besides a basic range, the 61 * AddrRange also support interleaved ranges, to stripe across cache 62 * banks, or memory controllers. The interleaving is implemented by 63 * allowing a number of bits of the address, at an arbitrary bit 64 * position, to be used as interleaving bits with an associated 65 * matching value. In addition, to prevent uniformly strided address 66 * patterns from a very biased interleaving, we also allow XOR-based 67 * hashing by specifying a set of bits to XOR 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 /** 83 * Each mask determines the bits we need to xor to get one bit of 84 * sel. The first (0) mask is used to get the LSB and the last for 85 * the MSB of sel. 86 */ 87 std::vector<Addr> masks; 88 89 /** The value to compare sel with. */ 90 uint8_t intlvMatch; 91 92 public: 93 94 AddrRange() 95 : _start(1), _end(0), intlvMatch(0) 96 {} 97 98 /** 99 * Construct an address range 100 * 101 * If the user provides a non empty vector of masks then the 102 * address range is interleaved. Each mask determines a set of 103 * bits that are xored to determine one bit of the sel value, 104 * starting from the least significant bit (i.e., masks[0] 105 * determines the least significant bit of sel, ...). If sel 106 * matches the provided _intlv_match then the address a is in the 107 * range. 108 * 109 * For example if the input mask is 110 * _masks = { 1 << 8 | 1 << 11 | 1 << 13, 111 * 1 << 15 | 1 << 17 | 1 << 19} 112 * 113 * Then a belongs to the address range if 114 * _start <= a < _end 115 * and 116 * sel == _intlv_match 117 * where 118 * sel[0] = a[8] ^ a[11] ^ a[13] 119 * sel[1] = a[15] ^ a[17] ^ a[19] 120 * 121 * @param _start The start address of this range 122 * @param _end The end address of this range (not included in the range) 123 * @param _masks The input vector of masks 124 * @param intlv_math The matching value of the xor operations 125 */ 126 AddrRange(Addr _start, Addr _end, const std::vector<Addr> &_masks, 127 uint8_t _intlv_match) 128 : _start(_start), _end(_end), masks(_masks), 129 intlvMatch(_intlv_match) 130 { 131 // sanity checks 132 fatal_if(!masks.empty() && _intlv_match >= ULL(1) << masks.size(), 133 "Match value %d does not fit in %d interleaving bits\n", 134 _intlv_match, masks.size()); 135 } 136 137 /** 138 * Legacy constructor of AddrRange 139 * 140 * If the user provides a non-zero value in _intlv_high_bit the 141 * address range is interleaved. 142 * 143 * An address a belongs to the address range if 144 * _start <= a < _end 145 * and 146 * sel == _intlv_match 147 * where 148 * sel = sel1 ^ sel2 149 * sel1 = a[_intlv_low_bit:_intlv_high_bit] 150 * sel2 = a[_xor_low_bit:_xor_high_bit] 151 * _intlv_low_bit = _intlv_high_bit - intv_bits 152 * _xor_low_bit = _xor_high_bit - intv_bits 153 * 154 * @param _start The start address of this range 155 * @param _end The end address of this range (not included in the range) 156 * @param _intlv_high_bit The MSB of the intlv bits (disabled if 0) 157 * @param _xor_high_bit The MSB of the xor bit (disabled if 0) 158 * @param intlv_math The matching value of the xor operations 159 */ 160 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 161 uint8_t _xor_high_bit, uint8_t _intlv_bits, 162 uint8_t _intlv_match) 163 : _start(_start), _end(_end), masks(_intlv_bits), 164 intlvMatch(_intlv_match) 165 { 166 // sanity checks 167 fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits, 168 "Match value %d does not fit in %d interleaving bits\n", 169 _intlv_match, _intlv_bits); 170 171 // ignore the XOR bits if not interleaving 172 if (_intlv_bits && _xor_high_bit) { 173 if (_xor_high_bit == _intlv_high_bit) { 174 fatal("XOR and interleave high bit must be different\n"); 175 } else if (_xor_high_bit > _intlv_high_bit) { 176 if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits) 177 fatal("XOR and interleave high bit must be at least " 178 "%d bits apart\n", _intlv_bits); 179 } else { 180 if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) { 181 fatal("Interleave and XOR high bit must be at least " 182 "%d bits apart\n", _intlv_bits); 183 } 184 } 185 } 186 187 for (auto i = 0; i < _intlv_bits; i++) { 188 uint8_t bit1 = _intlv_high_bit - i; 189 Addr mask = (1ULL << bit1); 190 if (_xor_high_bit) { 191 uint8_t bit2 = _xor_high_bit - i; 192 mask |= (1ULL << bit2); 193 } 194 masks[_intlv_bits - i - 1] = mask; 195 } 196 } 197 198 AddrRange(Addr _start, Addr _end) 199 : _start(_start), _end(_end), intlvMatch(0) 200 {} 201 202 /** 203 * Create an address range by merging a collection of interleaved 204 * ranges. 205 * 206 * @param ranges Interleaved ranges to be merged 207 */ 208 AddrRange(const std::vector<AddrRange>& ranges) 209 : _start(1), _end(0), intlvMatch(0) 210 { 211 if (!ranges.empty()) { 212 // get the values from the first one and check the others 213 _start = ranges.front()._start; 214 _end = ranges.front()._end; 215 masks = ranges.front().masks; 216 intlvMatch = ranges.front().intlvMatch; 217 } 218 // either merge if got all ranges or keep this equal to the single 219 // interleaved range 220 if (ranges.size() > 1) { 221 222 if (ranges.size() != (ULL(1) << masks.size())) 223 fatal("Got %d ranges spanning %d interleaving bits\n", 224 ranges.size(), masks.size()); 225 226 uint8_t match = 0; 227 for (const auto& r : ranges) { 228 if (!mergesWith(r)) 229 fatal("Can only merge ranges with the same start, end " 230 "and interleaving bits, %s %s\n", to_string(), 231 r.to_string()); 232 233 if (r.intlvMatch != match) 234 fatal("Expected interleave match %d but got %d when " 235 "merging\n", match, r.intlvMatch); 236 ++match; 237 } 238 masks.clear(); 239 intlvMatch = 0; 240 } 241 } 242 243 /** 244 * Determine if the range is interleaved or not. 245 * 246 * @return true if interleaved 247 */ 248 bool interleaved() const { return masks.size() > 0; } 249 250 /** 251 * Determing the interleaving granularity of the range. 252 * 253 * @return The size of the regions created by the interleaving bits 254 */ 255 uint64_t granularity() const 256 { 257 if (interleaved()) { 258 auto combined_mask = 0; 259 for (auto mask: masks) { 260 combined_mask |= mask; 261 } 262 const uint8_t lowest_bit = ctz64(combined_mask); 263 return ULL(1) << lowest_bit; 264 } else { 265 return size(); 266 } 267 } 268 269 /** 270 * Determine the number of interleaved address stripes this range 271 * is part of. 272 * 273 * @return The number of stripes spanned by the interleaving bits 274 */ 275 uint32_t stripes() const { return ULL(1) << masks.size(); } 276 277 /** 278 * Get the size of the address range. For a case where 279 * interleaving is used we make the simplifying assumption that 280 * the size is a divisible by the size of the interleaving slice. 281 */ 282 Addr size() const 283 { 284 return (_end - _start + 1) >> masks.size(); 285 } 286 287 /** 288 * Determine if the range is valid. 289 */ 290 bool valid() const { return _start <= _end; } 291 292 /** 293 * Get the start address of the range. 294 */ 295 Addr start() const { return _start; } 296 297 /** 298 * Get the end address of the range. 299 */ 300 Addr end() const { return _end; } 301 302 /** 303 * Get a string representation of the range. This could 304 * alternatively be implemented as a operator<<, but at the moment 305 * that seems like overkill. 306 */ 307 std::string to_string() const 308 { 309 if (interleaved()) { 310 std::string str; 311 for (int i = 0; i < masks.size(); i++) { 312 str += " "; 313 Addr mask = masks[i]; 314 while (mask) { 315 auto bit = ctz64(mask); 316 mask &= ~(1ULL << bit); 317 str += csprintf("a[%d]^", bit); 318 } 319 str += csprintf("\b=%d", bits(intlvMatch, i)); 320 } 321 return csprintf("[%#llx:%#llx]%s", _start, _end, str); 322 } else { 323 return csprintf("[%#llx:%#llx]", _start, _end); 324 } 325 } 326 327 /** 328 * Determine if another range merges with the current one, i.e. if 329 * they are part of the same contigous range and have the same 330 * interleaving bits. 331 * 332 * @param r Range to evaluate merging with 333 * @return true if the two ranges would merge 334 */ 335 bool mergesWith(const AddrRange& r) const 336 { 337 return r._start == _start && r._end == _end && 338 r.masks == masks; 339 } 340 341 /** 342 * Determine if another range intersects this one, i.e. if there 343 * is an address that is both in this range and the other 344 * range. No check is made to ensure either range is valid. 345 * 346 * @param r Range to intersect with 347 * @return true if the intersection of the two ranges is not empty 348 */ 349 bool intersects(const AddrRange& r) const 350 { 351 if (_start > r._end || _end < r._start) 352 // start with the simple case of no overlap at all, 353 // applicable even if we have interleaved ranges 354 return false; 355 else if (!interleaved() && !r.interleaved()) 356 // if neither range is interleaved, we are done 357 return true; 358 359 // now it gets complicated, focus on the cases we care about 360 if (r.size() == 1) 361 // keep it simple and check if the address is within 362 // this range 363 return contains(r.start()); 364 else if (mergesWith(r)) 365 // restrict the check to ranges that belong to the 366 // same chunk 367 return intlvMatch == r.intlvMatch; 368 else 369 panic("Cannot test intersection of %s and %s\n", 370 to_string(), r.to_string()); 371 } 372 373 /** 374 * Determine if this range is a subset of another range, i.e. if 375 * every address in this range is also in the other range. No 376 * check is made to ensure either range is valid. 377 * 378 * @param r Range to compare with 379 * @return true if the this range is a subset of the other one 380 */ 381 bool isSubset(const AddrRange& r) const 382 { 383 if (interleaved()) 384 panic("Cannot test subset of interleaved range %s\n", to_string()); 385 386 // This address range is not interleaved and therefore it 387 // suffices to check the upper bound, the lower bound and 388 // whether it would fit in a continuous segment of the input 389 // addr range. 390 if (r.interleaved()) { 391 return r.contains(_start) && r.contains(_end) && 392 size() <= r.granularity(); 393 } else { 394 return _start >= r._start && _end <= r._end; 395 } 396 } 397 398 /** 399 * Determine if the range contains an address. 400 * 401 * @param a Address to compare with 402 * @return true if the address is in the range 403 */ 404 bool contains(const Addr& a) const 405 { 406 // check if the address is in the range and if there is either 407 // no interleaving, or with interleaving also if the selected 408 // bits from the address match the interleaving value 409 bool in_range = a >= _start && a <= _end; 410 if (in_range) { 411 auto sel = 0; 412 for (int i = 0; i < masks.size(); i++) { 413 Addr masked = a & masks[i]; 414 // The result of an xor operation is 1 if the number 415 // of bits set is odd or 0 othersize, thefore it 416 // suffices to count the number of bits set to 417 // determine the i-th bit of sel. 418 sel |= (popCount(masked) % 2) << i; 419 } 420 return sel == intlvMatch; 421 } 422 return false; 423 } 424 425 /** 426 * Remove the interleaving bits from an input address. 427 * 428 * This function returns a new address in a continous range [ 429 * start, start + size / intlv_bits). We can achieve this by 430 * discarding the LSB in each mask. 431 * 432 * e.g., if the input address is of the form: 433 * ------------------------------------ 434 * | a_high | x1 | a_mid | x0 | a_low | 435 * ------------------------------------ 436 * where x0 is the LSB set in masks[0] 437 * and x1 is the LSB set in masks[1] 438 * 439 * this function will return: 440 * --------------------------------- 441 * | 0 | a_high | a_mid | a_low | 442 * --------------------------------- 443 * 444 * @param the input address 445 * @return the new address 446 */ 447 inline Addr removeIntlvBits(Addr a) const 448 { 449 // Get the LSB set from each mask 450 int masks_lsb[masks.size()]; 451 for (int i = 0; i < masks.size(); i++) { 452 masks_lsb[i] = ctz64(masks[i]); 453 } 454 455 // we need to sort the list of bits we will discard as we 456 // discard them one by one starting. 457 std::sort(masks_lsb, masks_lsb + masks.size()); 458 459 for (int i = 0; i < masks.size(); i++) { 460 const int intlv_bit = masks_lsb[i]; 461 if (intlv_bit > 0) { 462 // on every iteration we remove one bit from the input 463 // address, and therefore the lowest invtl_bit has 464 // also shifted to the right by i positions. 465 a = insertBits(a >> 1, intlv_bit - i - 1, 0, a); 466 } else { 467 a >>= 1; 468 } 469 } 470 return a; 471 } 472 473 /** 474 * Determine the offset of an address within the range. 475 * 476 * This function returns the offset of the given address from the 477 * starting address discarding any bits that are used for 478 * interleaving. This way we can convert the input address to a 479 * new unique address in a continuous range that starts from 0. 480 * 481 * @param the input address 482 * @return the flat offset in the address range 483 */ 484 Addr getOffset(const Addr& a) const 485 { 486 bool in_range = a >= _start && a <= _end; 487 if (!in_range) { 488 return MaxAddr; 489 } 490 if (interleaved()) { 491 return removeIntlvBits(a) - removeIntlvBits(_start); 492 } else { 493 return a - _start; 494 } 495 } 496 497 /** 498 * Less-than operator used to turn an STL map into a binary search 499 * tree of non-overlapping address ranges. 500 * 501 * @param r Range to compare with 502 * @return true if the start address is less than that of the other range 503 */ 504 bool operator<(const AddrRange& r) const 505 { 506 if (_start != r._start) 507 return _start < r._start; 508 else 509 // for now assume that the end is also the same, and that 510 // we are looking at the same interleaving bits 511 return intlvMatch < r.intlvMatch; 512 } 513 514 bool operator==(const AddrRange& r) const 515 { 516 if (_start != r._start) return false; 517 if (_end != r._end) return false; 518 if (masks != r.masks) return false; 519 if (intlvMatch != r.intlvMatch) return false; 520 521 return true; 522 } 523 524 bool operator!=(const AddrRange& r) const 525 { 526 return !(*this == r); 527 } 528}; 529 530/** 531 * Convenience typedef for a collection of address ranges 532 */ 533typedef std::list<AddrRange> AddrRangeList; 534 535inline AddrRange 536RangeEx(Addr start, Addr end) 537{ return AddrRange(start, end - 1); } 538 539inline AddrRange 540RangeIn(Addr start, Addr end) 541{ return AddrRange(start, end); } 542 543inline AddrRange 544RangeSize(Addr start, Addr size) 545{ return AddrRange(start, start + size - 1); } 546 547#endif // __BASE_ADDR_RANGE_HH__ 548