1 // Copyright (c) 2010 Google Inc. 2 // All rights reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are 6 // met: 7 // 8 // * Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // * Redistributions in binary form must reproduce the above 11 // copyright notice, this list of conditions and the following disclaimer 12 // in the documentation and/or other materials provided with the 13 // distribution. 14 // * Neither the name of Google Inc. nor the names of its 15 // contributors may be used to endorse or promote products derived from 16 // this software without specific prior written permission. 17 // 18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30 // range_map-inl.h: Range map implementation. 31 // 32 // See range_map.h for documentation. 33 // 34 // Author: Mark Mentovai 35 36 #ifndef PROCESSOR_RANGE_MAP_INL_H__ 37 #define PROCESSOR_RANGE_MAP_INL_H__ 38 39 40 #include <assert.h> 41 42 #include "processor/range_map.h" 43 #include "processor/logging.h" 44 45 46 namespace google_breakpad { 47 48 49 template<typename AddressType, typename EntryType> 50 bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base, 51 const AddressType &size, 52 const EntryType &entry) { 53 AddressType high = base + size - 1; 54 55 // Check for undersize or overflow. 56 if (size <= 0 || high < base) { 57 // The processor will hit this case too frequently with common symbol 58 // files in the size == 0 case, which is more suited to a DEBUG channel. 59 // Filter those out since there's no DEBUG channel at the moment. 60 BPLOG_IF(INFO, size != 0) << "StoreRange failed, " << HexString(base) << 61 "+" << HexString(size) << ", " << 62 HexString(high); 63 return false; 64 } 65 66 // Ensure that this range does not overlap with another one already in the 67 // map. 68 MapConstIterator iterator_base = map_.lower_bound(base); 69 MapConstIterator iterator_high = map_.lower_bound(high); 70 71 if (iterator_base != iterator_high) { 72 // Some other range begins in the space used by this range. It may be 73 // contained within the space used by this range, or it may extend lower. 74 // Regardless, it is an error. 75 // The processor hits this case too frequently with common symbol files. 76 // This is most appropriate for a DEBUG channel, but since none exists now 77 // simply comment out this logging. 78 // 79 // AddressType other_base = iterator_base->second.base(); 80 // AddressType other_size = iterator_base->first - other_base + 1; 81 // BPLOG(INFO) << "StoreRange failed, an existing range is contained by or " 82 // "extends lower than the new range: new " << 83 // HexString(base) << "+" << HexString(size) << 84 // ", existing " << HexString(other_base) << "+" << 85 // HexString(other_size); 86 87 return false; 88 } 89 90 if (iterator_high != map_.end()) { 91 if (iterator_high->second.base() <= high) { 92 // The range above this one overlaps with this one. It may fully 93 // contain this range, or it may begin within this range and extend 94 // higher. Regardless, it's an error. 95 // The processor hits this case too frequently with common symbol files. 96 // This is most appropriate for a DEBUG channel, but since none exists now 97 // simply comment out this logging. 98 // 99 // AddressType other_base = iterator_high->second.base(); 100 // AddressType other_size = iterator_high->first - other_base + 1; 101 // BPLOG(INFO) << "StoreRange failed, an existing range contains or " 102 // "extends higher than the new range: new " << 103 // HexString(base) << "+" << HexString(size) << 104 // ", existing " << HexString(other_base) << "+" << 105 // HexString(other_size); 106 return false; 107 } 108 } 109 110 // Store the range in the map by its high address, so that lower_bound can 111 // be used to quickly locate a range by address. 112 map_.insert(MapValue(high, Range(base, entry))); 113 return true; 114 } 115 116 117 template<typename AddressType, typename EntryType> 118 bool RangeMap<AddressType, EntryType>::RetrieveRange( 119 const AddressType &address, EntryType *entry, 120 AddressType *entry_base, AddressType *entry_size) const { 121 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|"; 122 assert(entry); 123 124 MapConstIterator iterator = map_.lower_bound(address); 125 if (iterator == map_.end()) 126 return false; 127 128 // The map is keyed by the high address of each range, so |address| is 129 // guaranteed to be lower than the range's high address. If |range| is 130 // not directly preceded by another range, it's possible for address to 131 // be below the range's low address, though. When that happens, address 132 // references something not within any range, so return false. 133 if (address < iterator->second.base()) 134 return false; 135 136 *entry = iterator->second.entry(); 137 if (entry_base) 138 *entry_base = iterator->second.base(); 139 if (entry_size) 140 *entry_size = iterator->first - iterator->second.base() + 1; 141 142 return true; 143 } 144 145 146 template<typename AddressType, typename EntryType> 147 bool RangeMap<AddressType, EntryType>::RetrieveNearestRange( 148 const AddressType &address, EntryType *entry, 149 AddressType *entry_base, AddressType *entry_size) const { 150 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|"; 151 assert(entry); 152 153 // If address is within a range, RetrieveRange can handle it. 154 if (RetrieveRange(address, entry, entry_base, entry_size)) 155 return true; 156 157 // upper_bound gives the first element whose key is greater than address, 158 // but we want the first element whose key is less than or equal to address. 159 // Decrement the iterator to get there, but not if the upper_bound already 160 // points to the beginning of the map - in that case, address is lower than 161 // the lowest stored key, so return false. 162 MapConstIterator iterator = map_.upper_bound(address); 163 if (iterator == map_.begin()) 164 return false; 165 --iterator; 166 167 *entry = iterator->second.entry(); 168 if (entry_base) 169 *entry_base = iterator->second.base(); 170 if (entry_size) 171 *entry_size = iterator->first - iterator->second.base() + 1; 172 173 return true; 174 } 175 176 177 template<typename AddressType, typename EntryType> 178 bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex( 179 int index, EntryType *entry, 180 AddressType *entry_base, AddressType *entry_size) const { 181 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|"; 182 assert(entry); 183 184 if (index >= GetCount()) { 185 BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount(); 186 return false; 187 } 188 189 // Walk through the map. Although it's ordered, it's not a vector, so it 190 // can't be addressed directly by index. 191 MapConstIterator iterator = map_.begin(); 192 for (int this_index = 0; this_index < index; ++this_index) 193 ++iterator; 194 195 *entry = iterator->second.entry(); 196 if (entry_base) 197 *entry_base = iterator->second.base(); 198 if (entry_size) 199 *entry_size = iterator->first - iterator->second.base() + 1; 200 201 return true; 202 } 203 204 205 template<typename AddressType, typename EntryType> 206 int RangeMap<AddressType, EntryType>::GetCount() const { 207 return map_.size(); 208 } 209 210 211 template<typename AddressType, typename EntryType> 212 void RangeMap<AddressType, EntryType>::Clear() { 213 map_.clear(); 214 } 215 216 217 } // namespace google_breakpad 218 219 220 #endif // PROCESSOR_RANGE_MAP_INL_H__ 221
