1 // Copyright 2006 Google LLC 2 // 3 // Redistribution and use in source and binary forms, with or without 4 // modification, are permitted provided that the following conditions are 5 // met: 6 // 7 // * Redistributions of source code must retain the above copyright 8 // notice, this list of conditions and the following disclaimer. 9 // * Redistributions in binary form must reproduce the above 10 // copyright notice, this list of conditions and the following disclaimer 11 // in the documentation and/or other materials provided with the 12 // distribution. 13 // * Neither the name of Google LLC nor the names of its 14 // contributors may be used to endorse or promote products derived from 15 // this software without specific prior written permission. 16 // 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 29 // range_map.h: Range maps. 30 // 31 // A range map associates a range of addresses with a specific object. This 32 // is useful when certain objects of variable size are located within an 33 // address space. The range map makes it simple to determine which object is 34 // associated with a specific address, which may be any address within the 35 // range associated with an object. 36 // 37 // Author: Mark Mentovai 38 39 #ifndef PROCESSOR_RANGE_MAP_H__ 40 #define PROCESSOR_RANGE_MAP_H__ 41 42 43 #include <map> 44 45 46 namespace google_breakpad { 47 48 // Forward declarations (for later friend declarations of specialized template). 49 template<class, class> class RangeMapSerializer; 50 51 // Determines what happens when two ranges overlap. 52 enum class MergeRangeStrategy { 53 // When two ranges overlap, the new range fails to be inserted. The default 54 // strategy. 55 kExclusiveRanges, 56 57 // The range with the lower base address will be truncated such that it's 58 // high address is one less than the range above it. 59 kTruncateLower, 60 61 // The range with the greater high address has its range truncated such that 62 // its base address is one higher than the range below it. 63 kTruncateUpper 64 }; 65 66 template<typename AddressType, typename EntryType> 67 class RangeMap { 68 public: RangeMap()69 RangeMap() : merge_strategy_(MergeRangeStrategy::kExclusiveRanges), map_() {} 70 SetMergeStrategy(MergeRangeStrategy strat)71 void SetMergeStrategy(MergeRangeStrategy strat) { merge_strategy_ = strat; } 72 GetMergeStrategy()73 MergeRangeStrategy GetMergeStrategy() const { return merge_strategy_; } 74 75 // Inserts a range into the map. Returns false for a parameter error, 76 // or if the location of the range would conflict with a range already 77 // stored in the map. If enable_shrink_down is true and there is an overlap 78 // between the current range and some other range (already in the map), 79 // shrink down the range which ends at a higher address. 80 bool StoreRange(const AddressType& base, const AddressType& size, 81 const EntryType& entry); 82 83 // Locates the range encompassing the supplied address. If there is no such 84 // range, returns false. entry_base, entry_delta, and entry_size, if 85 // non-NULL, are set to the base, delta, and size of the entry's range. 86 // A positive entry delta (> 0) indicates that there was an overlap and the 87 // entry was shrunk down (original start address was increased by delta). 88 bool RetrieveRange(const AddressType& address, EntryType* entry, 89 AddressType* entry_base, AddressType* entry_delta, 90 AddressType* entry_size) const; 91 92 // Locates the range encompassing the supplied address, if one exists. 93 // If no range encompasses the supplied address, locates the nearest range 94 // to the supplied address that is lower than the address. Returns false 95 // if no range meets these criteria. entry_base, entry_delta, and entry_size, 96 // if non-NULL, are set to the base, delta, and size of the entry's range. 97 // A positive entry delta (> 0) indicates that there was an overlap and the 98 // entry was shrunk down (original start address was increased by delta). 99 bool RetrieveNearestRange(const AddressType& address, EntryType* entry, 100 AddressType* entry_base, AddressType* entry_delta, 101 AddressType* entry_size) const; 102 103 // Treating all ranges as a list ordered by the address spaces that they 104 // occupy, locates the range at the index specified by index. Returns 105 // false if index is larger than the number of ranges stored. entry_base, 106 // entry_delta, and entry_size, if non-NULL, are set to the base, delta, and 107 // size of the entry's range. 108 // A positive entry delta (> 0) indicates that there was an overlap and the 109 // entry was shrunk down (original start address was increased by delta). 110 // 111 // RetrieveRangeAtIndex is not optimized for speedy operation. 112 bool RetrieveRangeAtIndex(int index, EntryType* entry, 113 AddressType* entry_base, AddressType* entry_delta, 114 AddressType* entry_size) const; 115 116 // Returns the number of ranges stored in the RangeMap. 117 int GetCount() const; 118 119 // Empties the range map, restoring it to the state it was when it was 120 // initially created. 121 void Clear(); 122 123 private: 124 // Friend declarations. 125 friend class ModuleComparer; 126 friend class RangeMapSerializer<AddressType, EntryType>; 127 128 // Same a StoreRange() with the only exception that the |delta| can be 129 // passed in. 130 bool StoreRangeInternal(const AddressType& base, const AddressType& delta, 131 const AddressType& size, const EntryType& entry); 132 133 class Range { 134 public: Range(const AddressType & base,const AddressType & delta,const EntryType & entry)135 Range(const AddressType& base, const AddressType& delta, 136 const EntryType& entry) 137 : base_(base), delta_(delta), entry_(entry) {} 138 base()139 AddressType base() const { return base_; } delta()140 AddressType delta() const { return delta_; } entry()141 EntryType entry() const { return entry_; } 142 143 private: 144 // The base address of the range. The high address does not need to 145 // be stored, because RangeMap uses it as the key to the map. 146 const AddressType base_; 147 148 // The delta when the range is shrunk down. 149 const AddressType delta_; 150 151 // The entry corresponding to a range. 152 const EntryType entry_; 153 }; 154 155 // Convenience types. 156 typedef std::map<AddressType, Range> AddressToRangeMap; 157 typedef typename AddressToRangeMap::const_iterator MapConstIterator; 158 typedef typename AddressToRangeMap::value_type MapValue; 159 160 MergeRangeStrategy merge_strategy_; 161 162 // Maps the high address of each range to a EntryType. 163 AddressToRangeMap map_; 164 }; 165 166 167 } // namespace google_breakpad 168 169 170 #endif // PROCESSOR_RANGE_MAP_H__ 171