addr_range.hh (10481:59fb5779ec6e) addr_range.hh (10676:f6c168692b20)
1/*
1/*
2 * Copyright (c) 2012 ARM Limited
2 * Copyright (c) 2012, 2014 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

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

48#include <list>
49#include <vector>
50
51#include "base/bitfield.hh"
52#include "base/cprintf.hh"
53#include "base/misc.hh"
54#include "base/types.hh"
55
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

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

48#include <list>
49#include <vector>
50
51#include "base/bitfield.hh"
52#include "base/cprintf.hh"
53#include "base/misc.hh"
54#include "base/types.hh"
55
56/**
57 * The AddrRange class encapsulates an address range, and supports a
58 * number of tests to check if two ranges intersect, if a range
59 * contains a specific address etc. Besides a basic range, the
60 * AddrRange also support interleaved ranges, to stripe across cache
61 * banks, or memory controllers. The interleaving is implemented by
62 * allowing a number of bits of the address, at an arbitrary bit
63 * position, to be used as interleaving bits with an associated
64 * matching value. In addition, to prevent uniformly strided address
65 * patterns from a very biased interleaving, we also allow basic
66 * XOR-based hashing by specifying an additional set of bits to XOR
67 * with before matching.
68 *
69 * The AddrRange is also able to coalesce a number of interleaved
70 * ranges to a contiguous range.
71 */
56class AddrRange
57{
58
59 private:
60
61 /// Private fields for the start and end of the range
62 /// Both _start and _end are part of the range.
63 Addr _start;
64 Addr _end;
65
66 /// The high bit of the slice that is used for interleaving
67 uint8_t intlvHighBit;
68
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
82 /// The high bit of the slice that is used for interleaving
83 uint8_t intlvHighBit;
84
85 /// The high bit of the slice used to XOR hash the value we match
86 /// against, set to 0 to disable.
87 uint8_t xorHighBit;
88
69 /// The number of bits used for interleaving, set to 0 to disable
70 uint8_t intlvBits;
71
72 /// The value to compare the slice addr[high:(high - bits + 1)]
73 /// with.
74 uint8_t intlvMatch;
75
76 public:
77
78 AddrRange()
89 /// The number of bits used for interleaving, set to 0 to disable
90 uint8_t intlvBits;
91
92 /// The value to compare the slice addr[high:(high - bits + 1)]
93 /// with.
94 uint8_t intlvMatch;
95
96 public:
97
98 AddrRange()
79 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
99 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
100 intlvMatch(0)
80 {}
81
82 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
101 {}
102
103 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
83 uint8_t _intlv_bits, uint8_t _intlv_match)
104 uint8_t _xor_high_bit, uint8_t _intlv_bits,
105 uint8_t _intlv_match)
84 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
106 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
85 intlvBits(_intlv_bits), intlvMatch(_intlv_match)
86 {}
107 xorHighBit(_xor_high_bit), intlvBits(_intlv_bits),
108 intlvMatch(_intlv_match)
109 {
110 // sanity checks
111 fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits,
112 "Match value %d does not fit in %d interleaving bits\n",
113 intlvMatch, intlvBits);
87
114
115 // ignore the XOR bits if not interleaving
116 if (intlvBits && xorHighBit) {
117 if (xorHighBit == intlvHighBit) {
118 fatal("XOR and interleave high bit must be different\n");
119 } else if (xorHighBit > intlvHighBit) {
120 if ((xorHighBit - intlvHighBit) < intlvBits)
121 fatal("XOR and interleave high bit must be at least "
122 "%d bits apart\n", intlvBits);
123 } else {
124 if ((intlvHighBit - xorHighBit) < intlvBits) {
125 fatal("Interleave and XOR high bit must be at least "
126 "%d bits apart\n", intlvBits);
127 }
128 }
129 }
130 }
131
88 AddrRange(Addr _start, Addr _end)
132 AddrRange(Addr _start, Addr _end)
89 : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0),
90 intlvMatch(0)
133 : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0),
134 intlvBits(0), intlvMatch(0)
91 {}
92
93 /**
94 * Create an address range by merging a collection of interleaved
95 * ranges.
96 *
97 * @param ranges Interleaved ranges to be merged
98 */
99 AddrRange(const std::vector<AddrRange>& ranges)
135 {}
136
137 /**
138 * Create an address range by merging a collection of interleaved
139 * ranges.
140 *
141 * @param ranges Interleaved ranges to be merged
142 */
143 AddrRange(const std::vector<AddrRange>& ranges)
100 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
144 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
145 intlvMatch(0)
101 {
102 if (!ranges.empty()) {
103 // get the values from the first one and check the others
104 _start = ranges.front()._start;
105 _end = ranges.front()._end;
106 intlvHighBit = ranges.front().intlvHighBit;
146 {
147 if (!ranges.empty()) {
148 // get the values from the first one and check the others
149 _start = ranges.front()._start;
150 _end = ranges.front()._end;
151 intlvHighBit = ranges.front().intlvHighBit;
152 xorHighBit = ranges.front().xorHighBit;
107 intlvBits = ranges.front().intlvBits;
108
109 if (ranges.size() != (ULL(1) << intlvBits))
110 fatal("Got %d ranges spanning %d interleaving bits\n",
111 ranges.size(), intlvBits);
112
113 uint8_t match = 0;
153 intlvBits = ranges.front().intlvBits;
154
155 if (ranges.size() != (ULL(1) << intlvBits))
156 fatal("Got %d ranges spanning %d interleaving bits\n",
157 ranges.size(), intlvBits);
158
159 uint8_t match = 0;
114 for (std::vector<AddrRange>::const_iterator r = ranges.begin();
115 r != ranges.end(); ++r) {
116 if (!mergesWith(*r))
160 for (const auto& r : ranges) {
161 if (!mergesWith(r))
117 fatal("Can only merge ranges with the same start, end "
118 "and interleaving bits\n");
119
162 fatal("Can only merge ranges with the same start, end "
163 "and interleaving bits\n");
164
120 if (r->intlvMatch != match)
165 if (r.intlvMatch != match)
121 fatal("Expected interleave match %d but got %d when "
166 fatal("Expected interleave match %d but got %d when "
122 "merging\n", match, r->intlvMatch);
167 "merging\n", match, r.intlvMatch);
123 ++match;
124 }
125
126 // our range is complete and we can turn this into a
127 // non-interleaved range
128 intlvHighBit = 0;
168 ++match;
169 }
170
171 // our range is complete and we can turn this into a
172 // non-interleaved range
173 intlvHighBit = 0;
174 xorHighBit = 0;
129 intlvBits = 0;
130 }
131 }
132
133 /**
134 * Determine if the range is interleaved or not.
135 *
136 * @return true if interleaved
137 */
138 bool interleaved() const { return intlvBits != 0; }
139
140 /**
175 intlvBits = 0;
176 }
177 }
178
179 /**
180 * Determine if the range is interleaved or not.
181 *
182 * @return true if interleaved
183 */
184 bool interleaved() const { return intlvBits != 0; }
185
186 /**
187 * Determine if the range interleaving is hashed or not.
188 */
189 bool hashed() const { return interleaved() && xorHighBit != 0; }
190
191 /**
141 * Determing the interleaving granularity of the range.
142 *
143 * @return The size of the regions created by the interleaving bits
144 */
145 uint64_t granularity() const
146 {
147 return ULL(1) << (intlvHighBit - intlvBits + 1);
148 }

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

177
178 /**
179 * Get a string representation of the range. This could
180 * alternatively be implemented as a operator<<, but at the moment
181 * that seems like overkill.
182 */
183 std::string to_string() const
184 {
192 * Determing the interleaving granularity of the range.
193 *
194 * @return The size of the regions created by the interleaving bits
195 */
196 uint64_t granularity() const
197 {
198 return ULL(1) << (intlvHighBit - intlvBits + 1);
199 }

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

228
229 /**
230 * Get a string representation of the range. This could
231 * alternatively be implemented as a operator<<, but at the moment
232 * that seems like overkill.
233 */
234 std::string to_string() const
235 {
185 if (interleaved())
186 return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end,
187 intlvHighBit, intlvHighBit - intlvBits + 1,
188 intlvMatch);
189 else
236 if (interleaved()) {
237 if (hashed()) {
238 return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d",
239 _start, _end,
240 intlvHighBit, intlvHighBit - intlvBits + 1,
241 xorHighBit, xorHighBit - intlvBits + 1,
242 intlvMatch);
243 } else {
244 return csprintf("[%#llx : %#llx], [%d : %d] = %d",
245 _start, _end,
246 intlvHighBit, intlvHighBit - intlvBits + 1,
247 intlvMatch);
248 }
249 } else {
190 return csprintf("[%#llx : %#llx]", _start, _end);
250 return csprintf("[%#llx : %#llx]", _start, _end);
251 }
191 }
192
193 /**
194 * Determine if another range merges with the current one, i.e. if
195 * they are part of the same contigous range and have the same
196 * interleaving bits.
197 *
198 * @param r Range to evaluate merging with
199 * @return true if the two ranges would merge
200 */
201 bool mergesWith(const AddrRange& r) const
202 {
203 return r._start == _start && r._end == _end &&
204 r.intlvHighBit == intlvHighBit &&
252 }
253
254 /**
255 * Determine if another range merges with the current one, i.e. if
256 * they are part of the same contigous range and have the same
257 * interleaving bits.
258 *
259 * @param r Range to evaluate merging with
260 * @return true if the two ranges would merge
261 */
262 bool mergesWith(const AddrRange& r) const
263 {
264 return r._start == _start && r._end == _end &&
265 r.intlvHighBit == intlvHighBit &&
266 r.xorHighBit == xorHighBit &&
205 r.intlvBits == intlvBits;
206 }
207
208 /**
209 * Determine if another range intersects this one, i.e. if there
210 * is an address that is both in this range and the other
211 * range. No check is made to ensure either range is valid.
212 *

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

258 * @param a Address to compare with
259 * @return true if the address is in the range
260 */
261 bool contains(const Addr& a) const
262 {
263 // check if the address is in the range and if there is either
264 // no interleaving, or with interleaving also if the selected
265 // bits from the address match the interleaving value
267 r.intlvBits == intlvBits;
268 }
269
270 /**
271 * Determine if another range intersects this one, i.e. if there
272 * is an address that is both in this range and the other
273 * range. No check is made to ensure either range is valid.
274 *

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

320 * @param a Address to compare with
321 * @return true if the address is in the range
322 */
323 bool contains(const Addr& a) const
324 {
325 // check if the address is in the range and if there is either
326 // no interleaving, or with interleaving also if the selected
327 // bits from the address match the interleaving value
266 return a >= _start && a <= _end &&
267 (!interleaved() ||
268 (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
269 intlvMatch));
328 bool in_range = a >= _start && a <= _end;
329 if (!interleaved()) {
330 return in_range;
331 } else if (in_range) {
332 if (!hashed()) {
333 return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
334 intlvMatch;
335 } else {
336 return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^
337 bits(a, xorHighBit, xorHighBit - intlvBits + 1)) ==
338 intlvMatch;
339 }
340 }
341 return false;
270 }
271
272/**
273 * Keep the operators away from SWIG.
274 */
275#ifndef SWIG
276
277 /**

--- 37 unchanged lines hidden --- 		342 }
343
344/**
345 * Keep the operators away from SWIG.
346 */
347#ifndef SWIG
348
349 /**

--- 37 unchanged lines hidden ---