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