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:
 69    RangeMap() : merge_strategy_(MergeRangeStrategy::kExclusiveRanges), map_() {}
 70  
 71    void SetMergeStrategy(MergeRangeStrategy strat) { merge_strategy_ = strat; }
 72  
 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:
135      Range(const AddressType& base, const AddressType& delta,
136            const EntryType& entry)
137          : base_(base), delta_(delta), entry_(entry) {}
138  
139      AddressType base() const { return base_; }
140      AddressType delta() const { return delta_; }
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__