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 // range_map.h: Range maps. 31 // 32 // A range map associates a range of addresses with a specific object. This 33 // is useful when certain objects of variable size are located within an 34 // address space. The range map makes it simple to determine which object is 35 // associated with a specific address, which may be any address within the 36 // range associated with an object. 37 // 38 // Author: Mark Mentovai 39 40 #ifndef PROCESSOR_RANGE_MAP_H__ 41 #define PROCESSOR_RANGE_MAP_H__ 42 43 44 #include <map> 45 46 47 namespace google_breakpad { 48 49 // Forward declarations (for later friend declarations of specialized template). 50 template<class, class> class RangeMapSerializer; 51 52 // Determines what happens when two ranges overlap. 53 enum class MergeRangeStrategy { 54 // When two ranges overlap, the new range fails to be inserted. The default 55 // strategy. 56 kExclusiveRanges, 57 58 // The range with the lower base address will be truncated such that it's 59 // high address is one less than the range above it. 60 kTruncateLower, 61 62 // The range with the greater high address has its range truncated such that 63 // its base address is one higher than the range below it. 64 kTruncateUpper 65 }; 66 67 template<typename AddressType, typename EntryType> 68 class RangeMap { 69 public: RangeMap()70 RangeMap() : merge_strategy_(MergeRangeStrategy::kExclusiveRanges), map_() {} 71 SetMergeStrategy(MergeRangeStrategy strat)72 void SetMergeStrategy(MergeRangeStrategy strat) { merge_strategy_ = strat; } 73 GetMergeStrategy()74 MergeRangeStrategy GetMergeStrategy() const { return merge_strategy_; } 75 76 // Inserts a range into the map. Returns false for a parameter error, 77 // or if the location of the range would conflict with a range already 78 // stored in the map. If enable_shrink_down is true and there is an overlap 79 // between the current range and some other range (already in the map), 80 // shrink down the range which ends at a higher address. 81 bool StoreRange(const AddressType &base, const AddressType &size, 82 const EntryType &entry); 83 84 // Locates the range encompassing the supplied address. If there is no such 85 // range, returns false. entry_base, entry_delta, and entry_size, if 86 // non-NULL, are set to the base, delta, and size of the entry's range. 87 // A positive entry delta (> 0) indicates that there was an overlap and the 88 // entry was shrunk down (original start address was increased by delta). 89 bool RetrieveRange(const AddressType &address, EntryType *entry, 90 AddressType *entry_base, AddressType *entry_delta, 91 AddressType *entry_size) const; 92 93 // Locates the range encompassing the supplied address, if one exists. 94 // If no range encompasses the supplied address, locates the nearest range 95 // to the supplied address that is lower than the address. Returns false 96 // if no range meets these criteria. entry_base, entry_delta, and entry_size, 97 // if non-NULL, are set to the base, delta, and size of the entry's range. 98 // A positive entry delta (> 0) indicates that there was an overlap and the 99 // entry was shrunk down (original start address was increased by delta). 100 bool RetrieveNearestRange(const AddressType &address, EntryType *entry, 101 AddressType *entry_base, AddressType *entry_delta, 102 AddressType *entry_size) const; 103 104 // Treating all ranges as a list ordered by the address spaces that they 105 // occupy, locates the range at the index specified by index. Returns 106 // false if index is larger than the number of ranges stored. entry_base, 107 // entry_delta, and entry_size, if non-NULL, are set to the base, delta, and 108 // size of the entry's range. 109 // A positive entry delta (> 0) indicates that there was an overlap and the 110 // entry was shrunk down (original start address was increased by delta). 111 // 112 // RetrieveRangeAtIndex is not optimized for speedy operation. 113 bool RetrieveRangeAtIndex(int index, EntryType *entry, 114 AddressType *entry_base, AddressType *entry_delta, 115 AddressType *entry_size) const; 116 117 // Returns the number of ranges stored in the RangeMap. 118 int GetCount() const; 119 120 // Empties the range map, restoring it to the state it was when it was 121 // initially created. 122 void Clear(); 123 124 private: 125 // Friend declarations. 126 friend class ModuleComparer; 127 friend class RangeMapSerializer<AddressType, EntryType>; 128 129 // Same a StoreRange() with the only exception that the |delta| can be 130 // passed in. 131 bool StoreRangeInternal(const AddressType &base, const AddressType &delta, 132 const AddressType &size, const EntryType &entry); 133 134 class Range { 135 public: Range(const AddressType & base,const AddressType & delta,const EntryType & entry)136 Range(const AddressType &base, const AddressType &delta, 137 const EntryType &entry) 138 : base_(base), delta_(delta), entry_(entry) {} 139 base()140 AddressType base() const { return base_; } delta()141 AddressType delta() const { return delta_; } entry()142 EntryType entry() const { return entry_; } 143 144 private: 145 // The base address of the range. The high address does not need to 146 // be stored, because RangeMap uses it as the key to the map. 147 const AddressType base_; 148 149 // The delta when the range is shrunk down. 150 const AddressType delta_; 151 152 // The entry corresponding to a range. 153 const EntryType entry_; 154 }; 155 156 // Convenience types. 157 typedef std::map<AddressType, Range> AddressToRangeMap; 158 typedef typename AddressToRangeMap::const_iterator MapConstIterator; 159 typedef typename AddressToRangeMap::value_type MapValue; 160 161 MergeRangeStrategy merge_strategy_; 162 163 // Maps the high address of each range to a EntryType. 164 AddressToRangeMap map_; 165 }; 166 167 168 } // namespace google_breakpad 169 170 171 #endif // PROCESSOR_RANGE_MAP_H__ 172