addr_range.hh (12977:cdc78a6e54d7) addr_range.hh (14047:91279ed7ec5e)
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

--- 47 unchanged lines hidden (view full) ---

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

--- 47 unchanged lines hidden (view full) ---

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 /**

--- 9 unchanged lines hidden (view full) ---

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 /**

--- 9 unchanged lines hidden (view full) ---

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

--- 55 unchanged lines hidden (view full) ---

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

--- 55 unchanged lines hidden (view full) ---

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

--- 29 unchanged lines hidden (view full) ---

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

--- 29 unchanged lines hidden (view full) ---

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};

--- 19 unchanged lines hidden --- 		515 return true;
516 }
517
518 bool operator!=(const AddrRange& r) const
519 {
520 return !(*this == r);
521 }
522};

--- 19 unchanged lines hidden ---