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