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     /// 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  */
 533 typedef std::list<AddrRange> AddrRangeList;
 534
 535 inline AddrRange
 536 RangeEx(Addr start, Addr end)
 537 { return AddrRange(start, end - 1); }
 538
 539 inline AddrRange
 540 RangeIn(Addr start, Addr end)
 541 { return AddrRange(start, end); }
 542
 543 inline AddrRange
 544 RangeSize(Addr start, Addr size)
 545 { return AddrRange(start, start + size - 1); }
 546
 547 #endif // __BASE_ADDR_RANGE_HH__