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 46namespace google_breakpad { 47 48 49template<typename AddressType, typename EntryType> 50ContainedRangeMap<AddressType, EntryType>::~ContainedRangeMap() { 51 // Clear frees the children pointed to by the map, and frees the map itself. 52 Clear(); 53} 54 55 56template<typename AddressType, typename EntryType> 57bool 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 150template<typename AddressType, typename EntryType> 151bool 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 181template<typename AddressType, typename EntryType> 182void 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