src/base/addr_range.hh

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