2 * Copyright (c) 2012, 2014, 2017-2019 ARM Limited
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.
14 * Copyright (c) 2002-2005 The Regents of The University of Michigan
15 * All rights reserved.
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.
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.
41 #ifndef __BASE_ADDR_RANGE_HH__
42 #define __BASE_ADDR_RANGE_HH__
48 #include "base/bitfield.hh"
49 #include "base/cprintf.hh"
50 #include "base/logging.hh"
51 #include "base/types.hh"
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.
65 * The AddrRange is also able to coalesce a number of interleaved
66 * ranges to a contiguous range.
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.
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
84 std::vector<Addr> masks;
86 /** The value to compare sel with. */
92 * @ingroup api_addr_range
95 : _start(1), _end(0), intlvMatch(0)
99 * Construct an address range
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
109 * For example if the input mask is
110 * _masks = { 1 << 8 | 1 << 11 | 1 << 13,
111 * 1 << 15 | 1 << 17 | 1 << 19}
113 * Then a belongs to the address range if
116 * sel == _intlv_match
118 * sel[0] = a[8] ^ a[11] ^ a[13]
119 * sel[1] = a[15] ^ a[17] ^ a[19]
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
126 * @ingroup api_addr_range
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)
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());
140 * Legacy constructor of AddrRange
142 * If the user provides a non-zero value in _intlv_high_bit the
143 * address range is interleaved.
145 * An address a belongs to the address range if
148 * sel == _intlv_match
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
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
163 * @ingroup api_addr_range
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)
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);
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);
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);
192 for (auto i = 0; i < _intlv_bits; i++) {
193 uint8_t bit1 = _intlv_high_bit - i;
194 Addr mask = (1ULL << bit1);
196 uint8_t bit2 = _xor_high_bit - i;
197 mask |= (1ULL << bit2);
199 masks[_intlv_bits - i - 1] = mask;
203 AddrRange(Addr _start, Addr _end)
204 : _start(_start), _end(_end), intlvMatch(0)
208 * Create an address range by merging a collection of interleaved
211 * @param ranges Interleaved ranges to be merged
213 * @ingroup api_addr_range
215 AddrRange(const std::vector<AddrRange>& ranges)
216 : _start(1), _end(0), intlvMatch(0)
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;
225 // either merge if got all ranges or keep this equal to the single
227 if (ranges.size() > 1) {
229 if (ranges.size() != (ULL(1) << masks.size()))
230 fatal("Got %d ranges spanning %d interleaving bits\n",
231 ranges.size(), masks.size());
234 for (const auto& r : ranges) {
236 fatal("Can only merge ranges with the same start, end "
237 "and interleaving bits, %s %s\n", to_string(),
240 if (r.intlvMatch != match)
241 fatal("Expected interleave match %d but got %d when "
242 "merging\n", match, r.intlvMatch);
251 * Determine if the range is interleaved or not.
253 * @return true if interleaved
255 * @ingroup api_addr_range
257 bool interleaved() const { return masks.size() > 0; }
260 * Determing the interleaving granularity of the range.
262 * @return The size of the regions created by the interleaving bits
264 * @ingroup api_addr_range
266 uint64_t granularity() const
269 auto combined_mask = 0;
270 for (auto mask: masks) {
271 combined_mask |= mask;
273 const uint8_t lowest_bit = ctz64(combined_mask);
274 return ULL(1) << lowest_bit;
281 * Determine the number of interleaved address stripes this range
284 * @return The number of stripes spanned by the interleaving bits
286 * @ingroup api_addr_range
288 uint32_t stripes() const { return ULL(1) << masks.size(); }
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.
295 * @ingroup api_addr_range
299 return (_end - _start) >> masks.size();
303 * Determine if the range is valid.
305 * @ingroup api_addr_range
307 bool valid() const { return _start <= _end; }
310 * Get the start address of the range.
312 * @ingroup api_addr_range
314 Addr start() const { return _start; }
317 * Get the end address of the range.
319 * @ingroup api_addr_range
321 Addr end() const { return _end; }
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.
328 * @ingroup api_addr_range
330 std::string to_string() const
334 for (int i = 0; i < masks.size(); i++) {
336 Addr mask = masks[i];
338 auto bit = ctz64(mask);
339 mask &= ~(1ULL << bit);
340 str += csprintf("a[%d]^", bit);
342 str += csprintf("\b=%d", bits(intlvMatch, i));
344 return csprintf("[%#llx:%#llx]%s", _start, _end, str);
346 return csprintf("[%#llx:%#llx]", _start, _end);
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
355 * @param r Range to evaluate merging with
356 * @return true if the two ranges would merge
358 * @ingroup api_addr_range
360 bool mergesWith(const AddrRange& r) const
362 return r._start == _start && r._end == _end &&
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.
371 * @param r Range to intersect with
372 * @return true if the intersection of the two ranges is not empty
374 * @ingroup api_addr_range
376 bool intersects(const AddrRange& r) const
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
382 else if (!interleaved() && !r.interleaved())
383 // if neither range is interleaved, we are done
386 // now it gets complicated, focus on the cases we care about
388 // keep it simple and check if the address is within
390 return contains(r.start());
391 else if (mergesWith(r))
392 // restrict the check to ranges that belong to the
394 return intlvMatch == r.intlvMatch;
396 panic("Cannot test intersection of %s and %s\n",
397 to_string(), r.to_string());
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.
405 * @param r Range to compare with
406 * @return true if the this range is a subset of the other one
408 * @ingroup api_addr_range
410 bool isSubset(const AddrRange& r) const
413 panic("Cannot test subset of interleaved range %s\n", to_string());
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
419 if (r.interleaved()) {
420 return r.contains(_start) && r.contains(_end - 1) &&
421 size() <= r.granularity();
423 return _start >= r._start && _end <= r._end;
428 * Determine if the range contains an address.
430 * @param a Address to compare with
431 * @return true if the address is in the range
433 * @ingroup api_addr_range
435 bool contains(const Addr& a) const
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;
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;
451 return sel == intlvMatch;
457 * Remove the interleaving bits from an input address.
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.
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]
470 * this function will return:
471 * ---------------------------------
472 * | 0 | a_high | a_mid | a_low |
473 * ---------------------------------
475 * @param a the input address
476 * @return the new address, or the input address if not interleaved
478 * @ingroup api_addr_range
480 inline Addr removeIntlvBits(Addr a) const
482 // Directly return the address if the range is not interleaved
483 // to prevent undefined behavior.
484 if (!interleaved()) {
488 // Get the LSB set from each mask
489 int masks_lsb[masks.size()];
490 for (int i = 0; i < masks.size(); i++) {
491 masks_lsb[i] = ctz64(masks[i]);
494 // we need to sort the list of bits we will discard as we
495 // discard them one by one starting.
496 std::sort(masks_lsb, masks_lsb + masks.size());
498 for (int i = 0; i < masks.size(); i++) {
499 const int intlv_bit = masks_lsb[i];
501 // on every iteration we remove one bit from the input
502 // address, and therefore the lowest invtl_bit has
503 // also shifted to the right by i positions.
504 a = insertBits(a >> 1, intlv_bit - i - 1, 0, a);
513 * This method adds the interleaving bits removed by
516 * @ingroup api_addr_range
518 inline Addr addIntlvBits(Addr a) const
520 // Directly return the address if the range is not interleaved
521 // to prevent undefined behavior.
522 if (!interleaved()) {
526 // Get the LSB set from each mask
527 int masks_lsb[masks.size()];
528 for (int i = 0; i < masks.size(); i++) {
529 masks_lsb[i] = ctz64(masks[i]);
532 // Add bits one-by-one from the LSB side.
533 std::sort(masks_lsb, masks_lsb + masks.size());
534 for (int i = 0; i < masks.size(); i++) {
535 const int intlv_bit = masks_lsb[i];
537 // on every iteration we add one bit from the input
538 // address, but the lowest invtl_bit in the iteration is
539 // always in the right position because they are sorted
540 // increasingly from the LSB
541 a = insertBits(a << 1, intlv_bit - 1, 0, a);
547 for (int i = 0; i < masks.size(); i++) {
548 const int lsb = ctz64(masks[i]);
549 const Addr intlv_bit = bits(intlvMatch, i);
550 // Calculate the mask ignoring the LSB
551 const Addr masked = a & masks[i] & ~(1 << lsb);
552 // Set the LSB of the mask to whatever satisfies the selector bit
553 a = insertBits(a, lsb, intlv_bit ^ popCount(masked));
560 * Determine the offset of an address within the range.
562 * This function returns the offset of the given address from the
563 * starting address discarding any bits that are used for
564 * interleaving. This way we can convert the input address to a
565 * new unique address in a continuous range that starts from 0.
567 * @param the input address
568 * @return the flat offset in the address range
570 * @ingroup api_addr_range
572 Addr getOffset(const Addr& a) const
574 bool in_range = a >= _start && a < _end;
579 return removeIntlvBits(a) - removeIntlvBits(_start);
586 * Less-than operator used to turn an STL map into a binary search
587 * tree of non-overlapping address ranges.
589 * @param r Range to compare with
590 * @return true if the start address is less than that of the other range
592 * @ingroup api_addr_range
594 bool operator<(const AddrRange& r) const
596 if (_start != r._start)
597 return _start < r._start;
599 // for now assume that the end is also the same, and that
600 // we are looking at the same interleaving bits
601 return intlvMatch < r.intlvMatch;
605 * @ingroup api_addr_range
607 bool operator==(const AddrRange& r) const
609 if (_start != r._start) return false;
610 if (_end != r._end) return false;
611 if (masks != r.masks) return false;
612 if (intlvMatch != r.intlvMatch) return false;
618 * @ingroup api_addr_range
620 bool operator!=(const AddrRange& r) const
622 return !(*this == r);
627 * Convenience typedef for a collection of address ranges
629 * @ingroup api_addr_range
631 typedef std::list<AddrRange> AddrRangeList;
634 * @ingroup api_addr_range
637 RangeEx(Addr start, Addr end)
638 { return AddrRange(start, end); }
641 * @ingroup api_addr_range
644 RangeIn(Addr start, Addr end)
645 { return AddrRange(start, end + 1); }
648 * @ingroup api_addr_range
651 RangeSize(Addr start, Addr size)
652 { return AddrRange(start, start + size); }
654 #endif // __BASE_ADDR_RANGE_HH__