1 // Copyright (c) 2006, 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 // contained_range_map-inl.h: Hierarchically-organized range map implementation. 31 // 32 // See contained_range_map.h for documentation. 33 // 34 // Author: Mark Mentovai 35 36 #ifndef PROCESSOR_CONTAINED_RANGE_MAP_INL_H__ 37 #define PROCESSOR_CONTAINED_RANGE_MAP_INL_H__ 38 39 #include "processor/contained_range_map.h" 40 41 #include <assert.h> 42 43 #include "processor/logging.h" 44 45 46 namespace google_breakpad { 47 48 49 template<typename AddressType, typename EntryType> 50 ContainedRangeMap<AddressType, EntryType>::~ContainedRangeMap() { 51 // Clear frees the children pointed to by the map, and frees the map itself. 52 Clear(); 53 } 54 55 56 template<typename AddressType, typename EntryType> 57 bool ContainedRangeMap<AddressType, EntryType>::StoreRange( 58 const AddressType &base, const AddressType &size, const EntryType &entry) { 59 AddressType high = base + size - 1; 60 61 // Check for undersize or overflow. 62 if (size <= 0 || high < base) { 63 //TODO(nealsid) We are commenting this out in order to prevent 64 // excessive logging. We plan to move to better logging as this 65 // failure happens quite often and is expected(see comment in 66 // basic_source_line_resolver.cc:671). 67 // BPLOG(INFO) << "StoreRange failed, " << HexString(base) << "+" 68 // << HexString(size) << ", " << HexString(high); 69 return false; 70 } 71 72 if (!map_) 73 map_ = new AddressToRangeMap(); 74 75 MapIterator iterator_base = map_->lower_bound(base); 76 MapIterator iterator_high = map_->lower_bound(high); 77 MapIterator iterator_end = map_->end(); 78 79 if (iterator_base == iterator_high && iterator_base != iterator_end && 80 base >= iterator_base->second->base_) { 81 // The new range is entirely within an existing child range. 82 83 // If the new range's geometry is exactly equal to an existing child 84 // range's, it violates the containment rules, and an attempt to store 85 // it must fail. iterator_base->first contains the key, which was the 86 // containing child's high address. 87 if (iterator_base->second->base_ == base && iterator_base->first == high) { 88 // TODO(nealsid): See the TODO above on why this is commented out. 89 // BPLOG(INFO) << "StoreRange failed, identical range is already " 90 // "present: " << HexString(base) << "+" << HexString(size); 91 return false; 92 } 93 94 // Pass the new range on to the child to attempt to store. 95 return iterator_base->second->StoreRange(base, size, entry); 96 } 97 98 // iterator_high might refer to an irrelevant range: one whose base address 99 // is higher than the new range's high address. Set contains_high to true 100 // only if iterator_high refers to a range that is at least partially 101 // within the new range. 102 bool contains_high = iterator_high != iterator_end && 103 high >= iterator_high->second->base_; 104 105 // If the new range encompasses any existing child ranges, it must do so 106 // fully. Partial containment isn't allowed. 107 if ((iterator_base != iterator_end && base > iterator_base->second->base_) || 108 (contains_high && high < iterator_high->first)) { 109 // TODO(mmentovai): Some symbol files will trip this check frequently 110 // on STACK lines. Too many messages will be produced. These are more 111 // suitable for a DEBUG channel than an INFO channel. 112 // BPLOG(INFO) << "StoreRange failed, new range partially contains " 113 // "existing range: " << HexString(base) << "+" << 114 // HexString(size); 115 return false; 116 } 117 118 // When copying and erasing contained ranges, the "end" iterator needs to 119 // point one past the last item of the range to copy. If contains_high is 120 // false, the iterator's already in the right place; the increment is safe 121 // because contains_high can't be true if iterator_high == iterator_end. 122 if (contains_high) 123 ++iterator_high; 124 125 // Optimization: if the iterators are equal, no child ranges would be 126 // moved. Create the new child range with a NULL map to conserve space 127 // in leaf nodes, of which there will be many. 128 AddressToRangeMap *child_map = NULL; 129 130 if (iterator_base != iterator_high) { 131 // The children of this range that are contained by the new range must 132 // be transferred over to the new range. Create the new child range map 133 // and copy the pointers to range maps it should contain into it. 134 child_map = new AddressToRangeMap(iterator_base, iterator_high); 135 136 // Remove the copied child pointers from this range's map of children. 137 map_->erase(iterator_base, iterator_high); 138 } 139 140 // Store the new range in the map by its high address. Any children that 141 // the new child range contains were formerly children of this range but 142 // are now this range's grandchildren. Ownership of these is transferred 143 // to the new child range. 144 map_->insert(MapValue(high, 145 new ContainedRangeMap(base, entry, child_map))); 146 return true; 147 } 148 149 150 template<typename AddressType, typename EntryType> 151 bool ContainedRangeMap<AddressType, EntryType>::RetrieveRange( 152 const AddressType &address, EntryType *entry) const { 153 BPLOG_IF(ERROR, !entry) << "ContainedRangeMap::RetrieveRange requires " 154 "|entry|"; 155 assert(entry); 156 157 // If nothing was ever stored, then there's nothing to retrieve. 158 if (!map_) 159 return false; 160 161 // Get an iterator to the child range whose high address is equal to or 162 // greater than the supplied address. If the supplied address is higher 163 // than all of the high addresses in the range, then this range does not 164 // contain a child at address, so return false. If the supplied address 165 // is lower than the base address of the child range, then it is not within 166 // the child range, so return false. 167 MapConstIterator iterator = map_->lower_bound(address); 168 if (iterator == map_->end() || address < iterator->second->base_) 169 return false; 170 171 // The child in iterator->second contains the specified address. Find out 172 // if it has a more-specific descendant that also contains it. If it does, 173 // it will set |entry| appropriately. If not, set |entry| to the child. 174 if (!iterator->second->RetrieveRange(address, entry)) 175 *entry = iterator->second->entry_; 176 177 return true; 178 } 179 180 181 template<typename AddressType, typename EntryType> 182 void ContainedRangeMap<AddressType, EntryType>::Clear() { 183 if (map_) { 184 MapConstIterator end = map_->end(); 185 for (MapConstIterator child = map_->begin(); child != end; ++child) 186 delete child->second; 187 188 delete map_; 189 map_ = NULL; 190 } 191 } 192 193 194 } // namespace google_breakpad 195 196 197 #endif // PROCESSOR_CONTAINED_RANGE_MAP_INL_H__ 198
