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 */ 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 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() 99 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), 100 intlvMatch(0) 101 {} 102 103 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 104 uint8_t _xor_high_bit, uint8_t _intlv_bits, 105 uint8_t _intlv_match) 106 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), 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); 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 132 AddrRange(Addr _start, Addr _end) 133 : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0), 134 intlvBits(0), intlvMatch(0) 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) 144 : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), 145 intlvMatch(0) 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; 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; 160 for (const auto& r : ranges) { 161 if (!mergesWith(r)) 162 fatal("Can only merge ranges with the same start, end " 163 "and interleaving bits\n"); 164 165 if (r.intlvMatch != match) 166 fatal("Expected interleave match %d but got %d when " 167 "merging\n", match, r.intlvMatch); 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; 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 /** 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 the end address of the range. 231 */ 232 Addr end() const { return _end; } 233 234 /** 235 * Get a string representation of the range. This could 236 * alternatively be implemented as a operator<<, but at the moment 237 * that seems like overkill. 238 */ 239 std::string to_string() const 240 { 241 if (interleaved()) { 242 if (hashed()) { 243 return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d", 244 _start, _end, 245 intlvHighBit, intlvHighBit - intlvBits + 1, 246 xorHighBit, xorHighBit - intlvBits + 1, 247 intlvMatch); 248 } else { 249 return csprintf("[%#llx : %#llx], [%d : %d] = %d", 250 _start, _end, 251 intlvHighBit, intlvHighBit - intlvBits + 1, 252 intlvMatch); 253 } 254 } else { 255 return csprintf("[%#llx : %#llx]", _start, _end); 256 } 257 } 258 259 /** 260 * Determine if another range merges with the current one, i.e. if 261 * they are part of the same contigous range and have the same 262 * interleaving bits. 263 * 264 * @param r Range to evaluate merging with 265 * @return true if the two ranges would merge 266 */ 267 bool mergesWith(const AddrRange& r) const 268 { 269 return r._start == _start && r._end == _end && 270 r.intlvHighBit == intlvHighBit && 271 r.xorHighBit == xorHighBit && 272 r.intlvBits == intlvBits; 273 } 274 275 /** 276 * Determine if another range intersects this one, i.e. if there 277 * is an address that is both in this range and the other 278 * range. No check is made to ensure either range is valid. 279 * 280 * @param r Range to intersect with 281 * @return true if the intersection of the two ranges is not empty 282 */ 283 bool intersects(const AddrRange& r) const 284 { 285 if (_start > r._end || _end < r._start) 286 // start with the simple case of no overlap at all, 287 // applicable even if we have interleaved ranges 288 return false; 289 else if (!interleaved() && !r.interleaved()) 290 // if neither range is interleaved, we are done 291 return true; 292 293 // now it gets complicated, focus on the cases we care about 294 if (r.size() == 1) 295 // keep it simple and check if the address is within 296 // this range 297 return contains(r.start()); 298 else if (mergesWith(r)) 299 // restrict the check to ranges that belong to the 300 // same chunk 301 return intlvMatch == r.intlvMatch; 302 else 303 panic("Cannot test intersection of %s and %s\n", 304 to_string(), r.to_string()); 305 } 306 307 /** 308 * Determine if this range is a subset of another range, i.e. if 309 * every address in this range is also in the other range. No 310 * check is made to ensure either range is valid. 311 * 312 * @param r Range to compare with 313 * @return true if the this range is a subset of the other one 314 */ 315 bool isSubset(const AddrRange& r) const 316 { 317 if (interleaved()) 318 panic("Cannot test subset of interleaved range %s\n", to_string()); 319 return _start >= r._start && _end <= r._end; 320 } 321 322 /** 323 * Determine if the range contains an address. 324 * 325 * @param a Address to compare with 326 * @return true if the address is in the range 327 */ 328 bool contains(const Addr& a) const 329 { 330 // check if the address is in the range and if there is either 331 // no interleaving, or with interleaving also if the selected 332 // bits from the address match the interleaving value 333 bool in_range = a >= _start && a <= _end; 334 if (!interleaved()) { 335 return in_range; 336 } else if (in_range) { 337 if (!hashed()) { 338 return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == 339 intlvMatch; 340 } else { 341 return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^ 342 bits(a, xorHighBit, xorHighBit - intlvBits + 1)) == 343 intlvMatch; 344 } 345 } 346 return false; 347 } 348 349 /**
|