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 // contained_range_map.h: Hierarchically-organized range maps. 30 // 31 // A contained range map is similar to a standard range map, except it allows 32 // objects to be organized hierarchically. A contained range map allows 33 // objects to contain other objects. It is not sensitive to the order that 34 // objects are added to the map: larger, more general, containing objects 35 // may be added either before or after smaller, more specific, contained 36 // ones. 37 // 38 // Contained range maps guarantee that each object may only contain smaller 39 // objects than itself, and that a parent object may only contain child 40 // objects located entirely within the parent's address space. Attempts 41 // to introduce objects (via StoreRange) that violate these rules will fail. 42 // Retrieval (via RetrieveRange) always returns the most specific (smallest) 43 // object that contains the address being queried. Note that while it is 44 // not possible to insert two objects into a map that have exactly the same 45 // geometry (base address and size), it is possible to completely mask a 46 // larger object by inserting smaller objects that entirely fill the larger 47 // object's address space. 48 // 49 // Internally, contained range maps are implemented as a tree. Each tree 50 // node except for the root node describes an object in the map. Each node 51 // maintains its list of children in a map similar to a standard range map, 52 // keyed by the highest address that each child occupies. Each node's 53 // children occupy address ranges entirely within the node. The root node 54 // is the only node directly accessible to the user, and represents the 55 // entire address space. 56 // 57 // Author: Mark Mentovai 58 59 #ifndef PROCESSOR_CONTAINED_RANGE_MAP_H__ 60 #define PROCESSOR_CONTAINED_RANGE_MAP_H__ 61 62 63 #include <map> 64 #include <vector> 65 66 67 namespace google_breakpad { 68 69 // Forward declarations (for later friend declarations of specialized template). 70 template<class, class> class ContainedRangeMapSerializer; 71 72 template<typename AddressType, typename EntryType> 73 class ContainedRangeMap { 74 public: 75 // The default constructor creates a ContainedRangeMap with no geometry 76 // and no entry, and as such is only suitable for the root node of a 77 // ContainedRangeMap tree. 78 explicit ContainedRangeMap(bool allow_equal_range = false) base_()79 : base_(), entry_(), map_(NULL), allow_equal_range_(allow_equal_range) {} 80 81 ~ContainedRangeMap(); 82 83 // Inserts a range into the map. If the new range is encompassed by 84 // an existing child range, the new range is passed into the child range's 85 // StoreRange method. If the new range encompasses any existing child 86 // ranges, those child ranges are moved to the new range, becoming 87 // grandchildren of this ContainedRangeMap. Returns false for a 88 // parameter error, or if the ContainedRangeMap hierarchy guarantees 89 // would be violated. 90 bool StoreRange(const AddressType& base, 91 const AddressType& size, 92 const EntryType& entry); 93 94 // Retrieves the most specific (smallest) descendant range encompassing 95 // the specified address. This method will only return entries held by 96 // child ranges, and not the entry contained by |this|. This is necessary 97 // to support a sparsely-populated root range. If no descendant range 98 // encompasses the address, returns false. 99 bool RetrieveRange(const AddressType& address, EntryType* entries) const; 100 101 // Retrieves the vector of entries encompassing the specified address from the 102 // innermost entry to the outermost entry. 103 bool RetrieveRanges(const AddressType& address, 104 std::vector<const EntryType*>& entries) const; 105 106 // Removes all children. Note that Clear only removes descendants, 107 // leaving the node on which it is called intact. Because the only 108 // meaningful things contained by a root node are descendants, this 109 // is sufficient to restore an entire ContainedRangeMap to its initial 110 // empty state when called on the root node. 111 void Clear(); 112 113 private: 114 friend class ContainedRangeMapSerializer<AddressType, EntryType>; 115 friend class ModuleComparer; 116 117 // AddressToRangeMap stores pointers. This makes reparenting simpler in 118 // StoreRange, because it doesn't need to copy entire objects. 119 typedef std::map<AddressType, ContainedRangeMap*> AddressToRangeMap; 120 typedef typename AddressToRangeMap::const_iterator MapConstIterator; 121 typedef typename AddressToRangeMap::iterator MapIterator; 122 typedef typename AddressToRangeMap::value_type MapValue; 123 124 // Creates a new ContainedRangeMap with the specified base address, entry, 125 // and initial child map, which may be NULL. This is only used internally 126 // by ContainedRangeMap when it creates a new child. ContainedRangeMap(const AddressType & base,const EntryType & entry,AddressToRangeMap * map,bool allow_equal_range)127 ContainedRangeMap(const AddressType& base, 128 const EntryType& entry, 129 AddressToRangeMap* map, 130 bool allow_equal_range) 131 : base_(base), 132 entry_(entry), 133 map_(map), 134 allow_equal_range_(allow_equal_range) {} 135 136 // The base address of this range. The high address does not need to 137 // be stored, because it is used as the key to an object in its parent's 138 // map, and all ContainedRangeMaps except for the root range are contained 139 // within maps. The root range does not actually contain an entry, so its 140 // base_ field is meaningless, and the fact that it has no parent and thus 141 // no key is unimportant. For this reason, the base_ field should only be 142 // is accessed on child ContainedRangeMap objects, and never on |this|. 143 const AddressType base_; 144 145 // The entry corresponding to this range. The root range does not 146 // actually contain an entry, so its entry_ field is meaningless. For 147 // this reason, the entry_ field should only be accessed on child 148 // ContainedRangeMap objects, and never on |this|. 149 const EntryType entry_; 150 151 // The map containing child ranges, keyed by each child range's high 152 // address. This is a pointer to avoid allocating map structures for 153 // leaf nodes, where they are not needed. 154 AddressToRangeMap* map_; 155 156 // Whether or not we allow storing an entry into a range that equals to 157 // existing range in the map. Default is false. 158 // If this is true, the newly added range will become a child of existing 159 // innermost range which has same base and size. 160 bool allow_equal_range_; 161 }; 162 163 164 } // namespace google_breakpad 165 166 167 #endif // PROCESSOR_CONTAINED_RANGE_MAP_H__ 168