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)
 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.
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__