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