1/*
2 * Copyright (c) 2012, 2014, 2017-2018 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
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.
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
83 /// The high bit of the slice that is used for interleaving
84 uint8_t intlvHighBit;
85
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.
95 uint8_t intlvMatch;
96
97 public:
98
99 AddrRange()
100 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
101 intlvMatch(0)
102 {}
103
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)
107 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
108 xorHighBit(_xor_high_bit), intlvBits(_intlv_bits),
109 intlvMatch(_intlv_match)
110 {
111 // sanity checks
112 fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits,
113 "Match value %d does not fit in %d interleaving bits\n",
114 intlvMatch, intlvBits);
115
116 // ignore the XOR bits if not interleaving
117 if (intlvBits && xorHighBit) {
118 if (xorHighBit == intlvHighBit) {
119 fatal("XOR and interleave high bit must be different\n");
120 } else if (xorHighBit > intlvHighBit) {
121 if ((xorHighBit - intlvHighBit) < intlvBits)
122 fatal("XOR and interleave high bit must be at least "
123 "%d bits apart\n", intlvBits);
124 } else {
125 if ((intlvHighBit - xorHighBit) < intlvBits) {
126 fatal("Interleave and XOR high bit must be at least "
127 "%d bits apart\n", intlvBits);
128 }
129 }
130 }
131 }
132
133 AddrRange(Addr _start, Addr _end)
134 : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0),
135 intlvBits(0), 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)
145 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
146 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;
152 intlvHighBit = ranges.front().intlvHighBit;
153 xorHighBit = ranges.front().xorHighBit;
154 intlvBits = ranges.front().intlvBits;
155
156 if (ranges.size() != (ULL(1) << intlvBits))
157 fatal("Got %d ranges spanning %d interleaving bits\n",
158 ranges.size(), intlvBits);
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 "
164 "and interleaving bits\n");
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 }
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;
177 }
178 }
179
180 /**
181 * Determine if the range is interleaved or not.
182 *
183 * @return true if interleaved
184 */
185 bool interleaved() const { return intlvBits != 0; }
186
187 /**
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()) {
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;
206 }
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 */
218 uint32_t stripes() const { return ULL(1) << intlvBits; }
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 {
227 return (_end - _start + 1) >> intlvBits;
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()) {
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);
264 }
265 } else {
266 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 &&
281 r.intlvHighBit == intlvHighBit &&
282 r.xorHighBit == xorHighBit &&
283 r.intlvBits == intlvBits;
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;
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;
365 }
366 }
367 return false;
368 }
369
370 /**
371 * Remove the interleaving bits from an input address.
372 *
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.
376 *
377 * e.g., if the input address is:
378 * -------------------------------
379 * | prefix | intlvBits | suffix |
380 * -------------------------------
381 * this function will return:
382 * -------------------------------
383 * | 0 | prefix | suffix |
384 * -------------------------------
385 *
386 * @param the input address
387 * @return the address without the interleaved bits
388 */
389 inline Addr removeIntlvBits(const Addr &a) const
390 {
391 const auto intlv_low_bit = intlvHighBit - intlvBits + 1;
392 return insertBits(a >> intlvBits, intlv_low_bit - 1, 0, 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 {
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 }
445 return true;
446 }
447
448 bool operator!=(const AddrRange& r) const
449 {
450 return !(*this == r);
451 }
452};

--- 19 unchanged lines hidden ---