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 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 <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 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 <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 } 149 150 /** 151 * Determine the number of interleaved address stripes this range 152 * is part of. 153 * 154 * @return The number of stripes spanned by the interleaving bits 155 */ 156 uint32_t stripes() const { return ULL(1) << intlvBits; } 157 158 /** 159 * Get the size of the address range. For a case where 160 * interleaving is used we make the simplifying assumption that 161 * the size is a divisible by the size of the interleaving slice. 162 */ 163 Addr size() const 164 { 165 return (_end - _start + 1) >> intlvBits; 166 } 167 168 /** 169 * Determine if the range is valid. 170 */ 171 bool valid() const { return _start <= _end; } 172 173 /** 174 * Get the start address of the range. 175 */ 176 Addr start() const { return _start; } 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 } 200 201 /** 202 * Determine the number of interleaved address stripes this range 203 * is part of. 204 * 205 * @return The number of stripes spanned by the interleaving bits 206 */ 207 uint32_t stripes() const { return ULL(1) << intlvBits; } 208 209 /** 210 * Get the size of the address range. For a case where 211 * interleaving is used we make the simplifying assumption that 212 * the size is a divisible by the size of the interleaving slice. 213 */ 214 Addr size() const 215 { 216 return (_end - _start + 1) >> intlvBits; 217 } 218 219 /** 220 * Determine if the range is valid. 221 */ 222 bool valid() const { return _start <= _end; } 223 224 /** 225 * Get the start address of the range. 226 */ 227 Addr start() const { return _start; } 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 * 213 * @param r Range to intersect with 214 * @return true if the intersection of the two ranges is not empty 215 */ 216 bool intersects(const AddrRange& r) const 217 { 218 if (!interleaved()) { 219 return _start <= r._end && _end >= r._start; 220 } 221 222 // the current range is interleaved, split the check up in 223 // three cases 224 if (r.size() == 1) 225 // keep it simple and check if the address is within 226 // this range 227 return contains(r.start()); 228 else if (!r.interleaved()) 229 // be conservative and ignore the interleaving 230 return _start <= r._end && _end >= r._start; 231 else if (mergesWith(r)) 232 // restrict the check to ranges that belong to the 233 // same chunk 234 return intlvMatch == r.intlvMatch; 235 else 236 panic("Cannot test intersection of interleaved range %s\n", 237 to_string()); 238 } 239 240 /** 241 * Determine if this range is a subset of another range, i.e. if 242 * every address in this range is also in the other range. No 243 * check is made to ensure either range is valid. 244 * 245 * @param r Range to compare with 246 * @return true if the this range is a subset of the other one 247 */ 248 bool isSubset(const AddrRange& r) const 249 { 250 if (interleaved()) 251 panic("Cannot test subset of interleaved range %s\n", to_string()); 252 return _start >= r._start && _end <= r._end; 253 } 254 255 /** 256 * Determine if the range contains an address. 257 * 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 * 275 * @param r Range to intersect with 276 * @return true if the intersection of the two ranges is not empty 277 */ 278 bool intersects(const AddrRange& r) const 279 { 280 if (!interleaved()) { 281 return _start <= r._end && _end >= r._start; 282 } 283 284 // the current range is interleaved, split the check up in 285 // three cases 286 if (r.size() == 1) 287 // keep it simple and check if the address is within 288 // this range 289 return contains(r.start()); 290 else if (!r.interleaved()) 291 // be conservative and ignore the interleaving 292 return _start <= r._end && _end >= r._start; 293 else if (mergesWith(r)) 294 // restrict the check to ranges that belong to the 295 // same chunk 296 return intlvMatch == r.intlvMatch; 297 else 298 panic("Cannot test intersection of interleaved range %s\n", 299 to_string()); 300 } 301 302 /** 303 * Determine if this range is a subset of another range, i.e. if 304 * every address in this range is also in the other range. No 305 * check is made to ensure either range is valid. 306 * 307 * @param r Range to compare with 308 * @return true if the this range is a subset of the other one 309 */ 310 bool isSubset(const AddrRange& r) const 311 { 312 if (interleaved()) 313 panic("Cannot test subset of interleaved range %s\n", to_string()); 314 return _start >= r._start && _end <= r._end; 315 } 316 317 /** 318 * Determine if the range contains an address. 319 * 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 /** 278 * Less-than operator used to turn an STL map into a binary search 279 * tree of non-overlapping address ranges. 280 * 281 * @param r Range to compare with 282 * @return true if the start address is less than that of the other range 283 */ 284 bool operator<(const AddrRange& r) const 285 { 286 if (_start != r._start) 287 return _start < r._start; 288 else 289 // for now assume that the end is also the same, and that 290 // we are looking at the same interleaving bits 291 return intlvMatch < r.intlvMatch; 292 } 293 294#endif // SWIG 295}; 296 297/** 298 * Convenience typedef for a collection of address ranges 299 */ 300typedef std::list<AddrRange> AddrRangeList; 301 302inline AddrRange 303RangeEx(Addr start, Addr end) 304{ return AddrRange(start, end - 1); } 305 306inline AddrRange 307RangeIn(Addr start, Addr end) 308{ return AddrRange(start, end); } 309 310inline AddrRange 311RangeSize(Addr start, Addr size) 312{ return AddrRange(start, start + size - 1); } 313 314#endif // __BASE_ADDR_RANGE_HH__
| 342 } 343 344/** 345 * Keep the operators away from SWIG. 346 */ 347#ifndef SWIG 348 349 /** 350 * Less-than operator used to turn an STL map into a binary search 351 * tree of non-overlapping address ranges. 352 * 353 * @param r Range to compare with 354 * @return true if the start address is less than that of the other range 355 */ 356 bool operator<(const AddrRange& r) const 357 { 358 if (_start != r._start) 359 return _start < r._start; 360 else 361 // for now assume that the end is also the same, and that 362 // we are looking at the same interleaving bits 363 return intlvMatch < r.intlvMatch; 364 } 365 366#endif // SWIG 367}; 368 369/** 370 * Convenience typedef for a collection of address ranges 371 */ 372typedef std::list<AddrRange> AddrRangeList; 373 374inline AddrRange 375RangeEx(Addr start, Addr end) 376{ return AddrRange(start, end - 1); } 377 378inline AddrRange 379RangeIn(Addr start, Addr end) 380{ return AddrRange(start, end); } 381 382inline AddrRange 383RangeSize(Addr start, Addr size) 384{ return AddrRange(start, start + size - 1); } 385 386#endif // __BASE_ADDR_RANGE_HH__
|