1/*
2 * Copyright (c) 2012 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 <vector>
49
50#include "base/bitfield.hh"
51#include "base/cprintf.hh"
52#include "base/misc.hh"
53#include "base/types.hh"
54
55class AddrRange
56{
57
58 private:
59
60 /// Private fields for the start and end of the range
61 Addr _start;
62 Addr _end;
63
64 /// The high bit of the slice that is used for interleaving
65 uint8_t intlvHighBit;
66
67 /// The number of bits used for interleaving, set to 0 to disable
68 uint8_t intlvBits;
69
70 /// The value to compare the slice addr[high:(high - bits + 1)]
71 /// with.
72 uint8_t intlvMatch;
73
74 public:
75
76 AddrRange()
77 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
78 {}
79
80 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
81 uint8_t _intlv_bits, uint8_t _intlv_match)
82 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
83 intlvBits(_intlv_bits), intlvMatch(_intlv_match)
84 {}
85
86 AddrRange(Addr _start, Addr _end)
87 : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0),
88 intlvMatch(0)
89 {}
90
91 /**
92 * Create an address range by merging a collection of interleaved
93 * ranges.
94 *
95 * @param ranges Interleaved ranges to be merged
96 */
97 AddrRange(const std::vector<AddrRange>& ranges)
98 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
99 {
100 if (!ranges.empty()) {
101 // get the values from the first one and check the others
102 _start = ranges.front()._start;
103 _end = ranges.front()._end;
104 intlvHighBit = ranges.front().intlvHighBit;
105 intlvBits = ranges.front().intlvBits;
106
107 if (ranges.size() != (ULL(1) << intlvBits))
108 fatal("Got %d ranges spanning %d interleaving bits\n",
109 ranges.size(), intlvBits);
110
111 uint8_t match = 0;
112 for (std::vector<AddrRange>::const_iterator r = ranges.begin();
113 r != ranges.end(); ++r) {
114 if (!mergesWith(*r))
115 fatal("Can only merge ranges with the same start, end "
116 "and interleaving bits\n");
117
118 if (r->intlvMatch != match)
119 fatal("Expected interleave match %d but got %d when "
120 "merging\n", match, r->intlvMatch);
121 ++match;
122 }
123
124 // our range is complete and we can turn this into a
125 // non-interleaved range
126 intlvHighBit = 0;
127 intlvBits = 0;
128 }
129 }
130
131 /**
132 * Determine if the range is interleaved or not.
133 *
134 * @return true if interleaved
135 */
136 bool interleaved() const { return intlvBits != 0; }
137
138 /**
139 * Determing the interleaving granularity of the range.
140 *
141 * @return The size of the regions created by the interleaving bits
142 */
143 uint64_t granularity() const { return ULL(1) << intlvHighBit; }
144
145 /**
146 * Determine the number of interleaved address stripes this range
147 * is part of.
148 *
149 * @return The number of stripes spanned by the interleaving bits
150 */
151 uint32_t stripes() const { return ULL(1) << intlvBits; }
152
153 /**
154 * Get the size of the address range. For a case where
155 * interleaving is used we make the simplifying assumption that
156 * the size is a divisible by the size of the interleaving slice.
157 */
158 Addr size() const
159 {
160 return (_end - _start + 1) >> intlvBits;
161 }
162
163 /**
164 * Determine if the range is valid.
165 */
166 bool valid() const { return _start < _end; }
167
168 /**
169 * Get the start address of the range.
170 */
171 Addr start() const { return _start; }
172
173 /**
174 * Get a string representation of the range. This could
175 * alternatively be implemented as a operator<<, but at the moment
176 * that seems like overkill.
177 */
178 std::string to_string() const
179 {
180 if (interleaved())
181 return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end,
182 intlvHighBit, intlvHighBit - intlvBits + 1,
183 intlvMatch);
184 else
185 return csprintf("[%#llx : %#llx]", _start, _end);
186 }
187
188 /**
189 * Determine if another range merges with the current one, i.e. if
190 * they are part of the same contigous range and have the same
191 * interleaving bits.
192 *
193 * @param r Range to evaluate merging with
194 * @return true if the two ranges would merge
195 */
196 bool mergesWith(const AddrRange& r) const
197 {
198 return r._start == _start && r._end == _end &&
199 r.intlvHighBit == intlvHighBit &&
200 r.intlvBits == intlvBits;
201 }
202
203 /**
204 * Determine if another range intersects this one, i.e. if there
205 * is an address that is both in this range and the other
206 * range. No check is made to ensure either range is valid.
207 *
208 * @param r Range to intersect with
209 * @return true if the intersection of the two ranges is not empty
210 */
211 bool intersects(const AddrRange& r) const
212 {
213 if (!interleaved()) {
214 return _start <= r._end && _end >= r._start;
215 }
216
217 // the current range is interleaved, split the check up in
218 // three cases
219 if (r.size() == 1)
220 // keep it simple and check if the address is within
221 // this range
222 return contains(r.start());
223 else if (!r.interleaved())
224 // be conservative and ignore the interleaving
225 return _start <= r._end && _end >= r._start;
226 else if (mergesWith(r))
227 // restrict the check to ranges that belong to the
228 // same chunk
229 return intlvMatch == r.intlvMatch;
230 else
231 panic("Cannot test intersection of interleaved range %s\n",
232 to_string());
233 }
234
235 /**
236 * Determine if this range is a subset of another range, i.e. if
237 * every address in this range is also in the other range. No
238 * check is made to ensure either range is valid.
239 *
240 * @param r Range to compare with
241 * @return true if the this range is a subset of the other one
242 */
243 bool isSubset(const AddrRange& r) const
244 {
245 if (interleaved())
246 panic("Cannot test subset of interleaved range %s\n", to_string());
247 return _start >= r._start && _end <= r._end;
248 }
249
250 /**
251 * Determine if the range contains an address.
252 *
253 * @param a Address to compare with
254 * @return true if the address is in the range
255 */
256 bool contains(const Addr& a) const
257 {
258 // check if the address is in the range and if there is either
259 // no interleaving, or with interleaving also if the selected
260 // bits from the address match the interleaving value
261 return a >= _start && a <= _end &&
| 1/*
2 * Copyright (c) 2012 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 <vector>
49
50#include "base/bitfield.hh"
51#include "base/cprintf.hh"
52#include "base/misc.hh"
53#include "base/types.hh"
54
55class AddrRange
56{
57
58 private:
59
60 /// Private fields for the start and end of the range
61 Addr _start;
62 Addr _end;
63
64 /// The high bit of the slice that is used for interleaving
65 uint8_t intlvHighBit;
66
67 /// The number of bits used for interleaving, set to 0 to disable
68 uint8_t intlvBits;
69
70 /// The value to compare the slice addr[high:(high - bits + 1)]
71 /// with.
72 uint8_t intlvMatch;
73
74 public:
75
76 AddrRange()
77 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
78 {}
79
80 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
81 uint8_t _intlv_bits, uint8_t _intlv_match)
82 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
83 intlvBits(_intlv_bits), intlvMatch(_intlv_match)
84 {}
85
86 AddrRange(Addr _start, Addr _end)
87 : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0),
88 intlvMatch(0)
89 {}
90
91 /**
92 * Create an address range by merging a collection of interleaved
93 * ranges.
94 *
95 * @param ranges Interleaved ranges to be merged
96 */
97 AddrRange(const std::vector<AddrRange>& ranges)
98 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
99 {
100 if (!ranges.empty()) {
101 // get the values from the first one and check the others
102 _start = ranges.front()._start;
103 _end = ranges.front()._end;
104 intlvHighBit = ranges.front().intlvHighBit;
105 intlvBits = ranges.front().intlvBits;
106
107 if (ranges.size() != (ULL(1) << intlvBits))
108 fatal("Got %d ranges spanning %d interleaving bits\n",
109 ranges.size(), intlvBits);
110
111 uint8_t match = 0;
112 for (std::vector<AddrRange>::const_iterator r = ranges.begin();
113 r != ranges.end(); ++r) {
114 if (!mergesWith(*r))
115 fatal("Can only merge ranges with the same start, end "
116 "and interleaving bits\n");
117
118 if (r->intlvMatch != match)
119 fatal("Expected interleave match %d but got %d when "
120 "merging\n", match, r->intlvMatch);
121 ++match;
122 }
123
124 // our range is complete and we can turn this into a
125 // non-interleaved range
126 intlvHighBit = 0;
127 intlvBits = 0;
128 }
129 }
130
131 /**
132 * Determine if the range is interleaved or not.
133 *
134 * @return true if interleaved
135 */
136 bool interleaved() const { return intlvBits != 0; }
137
138 /**
139 * Determing the interleaving granularity of the range.
140 *
141 * @return The size of the regions created by the interleaving bits
142 */
143 uint64_t granularity() const { return ULL(1) << intlvHighBit; }
144
145 /**
146 * Determine the number of interleaved address stripes this range
147 * is part of.
148 *
149 * @return The number of stripes spanned by the interleaving bits
150 */
151 uint32_t stripes() const { return ULL(1) << intlvBits; }
152
153 /**
154 * Get the size of the address range. For a case where
155 * interleaving is used we make the simplifying assumption that
156 * the size is a divisible by the size of the interleaving slice.
157 */
158 Addr size() const
159 {
160 return (_end - _start + 1) >> intlvBits;
161 }
162
163 /**
164 * Determine if the range is valid.
165 */
166 bool valid() const { return _start < _end; }
167
168 /**
169 * Get the start address of the range.
170 */
171 Addr start() const { return _start; }
172
173 /**
174 * Get a string representation of the range. This could
175 * alternatively be implemented as a operator<<, but at the moment
176 * that seems like overkill.
177 */
178 std::string to_string() const
179 {
180 if (interleaved())
181 return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end,
182 intlvHighBit, intlvHighBit - intlvBits + 1,
183 intlvMatch);
184 else
185 return csprintf("[%#llx : %#llx]", _start, _end);
186 }
187
188 /**
189 * Determine if another range merges with the current one, i.e. if
190 * they are part of the same contigous range and have the same
191 * interleaving bits.
192 *
193 * @param r Range to evaluate merging with
194 * @return true if the two ranges would merge
195 */
196 bool mergesWith(const AddrRange& r) const
197 {
198 return r._start == _start && r._end == _end &&
199 r.intlvHighBit == intlvHighBit &&
200 r.intlvBits == intlvBits;
201 }
202
203 /**
204 * Determine if another range intersects this one, i.e. if there
205 * is an address that is both in this range and the other
206 * range. No check is made to ensure either range is valid.
207 *
208 * @param r Range to intersect with
209 * @return true if the intersection of the two ranges is not empty
210 */
211 bool intersects(const AddrRange& r) const
212 {
213 if (!interleaved()) {
214 return _start <= r._end && _end >= r._start;
215 }
216
217 // the current range is interleaved, split the check up in
218 // three cases
219 if (r.size() == 1)
220 // keep it simple and check if the address is within
221 // this range
222 return contains(r.start());
223 else if (!r.interleaved())
224 // be conservative and ignore the interleaving
225 return _start <= r._end && _end >= r._start;
226 else if (mergesWith(r))
227 // restrict the check to ranges that belong to the
228 // same chunk
229 return intlvMatch == r.intlvMatch;
230 else
231 panic("Cannot test intersection of interleaved range %s\n",
232 to_string());
233 }
234
235 /**
236 * Determine if this range is a subset of another range, i.e. if
237 * every address in this range is also in the other range. No
238 * check is made to ensure either range is valid.
239 *
240 * @param r Range to compare with
241 * @return true if the this range is a subset of the other one
242 */
243 bool isSubset(const AddrRange& r) const
244 {
245 if (interleaved())
246 panic("Cannot test subset of interleaved range %s\n", to_string());
247 return _start >= r._start && _end <= r._end;
248 }
249
250 /**
251 * Determine if the range contains an address.
252 *
253 * @param a Address to compare with
254 * @return true if the address is in the range
255 */
256 bool contains(const Addr& a) const
257 {
258 // check if the address is in the range and if there is either
259 // no interleaving, or with interleaving also if the selected
260 // bits from the address match the interleaving value
261 return a >= _start && a <= _end &&
|
263 (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
264 intlvMatch));
265 }
266
267/**
268 * Keep the operators away from SWIG.
269 */
270#ifndef SWIG
271
272 /**
273 * Less-than operator used to turn an STL map into a binary search
274 * tree of non-overlapping address ranges.
275 *
276 * @param r Range to compare with
277 * @return true if the start address is less than that of the other range
278 */
279 bool operator<(const AddrRange& r) const
280 {
281 if (_start != r._start)
282 return _start < r._start;
283 else
284 // for now assume that the end is also the same, and that
285 // we are looking at the same interleaving bits
286 return intlvMatch < r.intlvMatch;
287 }
288
289#endif // SWIG
290};
291
292inline AddrRange
293RangeEx(Addr start, Addr end)
294{ return AddrRange(start, end - 1); }
295
296inline AddrRange
297RangeIn(Addr start, Addr end)
298{ return AddrRange(start, end); }
299
300inline AddrRange
301RangeSize(Addr start, Addr size)
302{ return AddrRange(start, start + size - 1); }
303
304#endif // __BASE_ADDR_RANGE_HH__
| 263 (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
264 intlvMatch));
265 }
266
267/**
268 * Keep the operators away from SWIG.
269 */
270#ifndef SWIG
271
272 /**
273 * Less-than operator used to turn an STL map into a binary search
274 * tree of non-overlapping address ranges.
275 *
276 * @param r Range to compare with
277 * @return true if the start address is less than that of the other range
278 */
279 bool operator<(const AddrRange& r) const
280 {
281 if (_start != r._start)
282 return _start < r._start;
283 else
284 // for now assume that the end is also the same, and that
285 // we are looking at the same interleaving bits
286 return intlvMatch < r.intlvMatch;
287 }
288
289#endif // SWIG
290};
291
292inline AddrRange
293RangeEx(Addr start, Addr end)
294{ return AddrRange(start, end - 1); }
295
296inline AddrRange
297RangeIn(Addr start, Addr end)
298{ return AddrRange(start, end); }
299
300inline AddrRange
301RangeSize(Addr start, Addr size)
302{ return AddrRange(start, start + size - 1); }
303
304#endif // __BASE_ADDR_RANGE_HH__
|