addr_range.hh revision 10481
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 <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 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 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() 79 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) 80 {} 81 82 AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 83 uint8_t _intlv_bits, uint8_t _intlv_match) 84 : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), 85 intlvBits(_intlv_bits), intlvMatch(_intlv_match) 86 {} 87 88 AddrRange(Addr _start, Addr _end) 89 : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0), 90 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) 100 : _start(1), _end(0), intlvHighBit(0), intlvBits(0), 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; 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; 114 for (std::vector<AddrRange>::const_iterator r = ranges.begin(); 115 r != ranges.end(); ++r) { 116 if (!mergesWith(*r)) 117 fatal("Can only merge ranges with the same start, end " 118 "and interleaving bits\n"); 119 120 if (r->intlvMatch != match) 121 fatal("Expected interleave match %d but got %d when " 122 "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; 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 /** 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 { 185 if (interleaved()) 186 return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end, 187 intlvHighBit, intlvHighBit - intlvBits + 1, 188 intlvMatch); 189 else 190 return csprintf("[%#llx : %#llx]", _start, _end); 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 && 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 266 return a >= _start && a <= _end && 267 (!interleaved() || 268 (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == 269 intlvMatch)); 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__ 315