1 | // Copyright (c) 2010 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 | // range_map-inl.h: Range map implementation. |
31 | // |
32 | // See range_map.h for documentation. |
33 | // |
34 | // Author: Mark Mentovai |
35 | |
36 | #ifndef PROCESSOR_RANGE_MAP_INL_H__ |
37 | #define PROCESSOR_RANGE_MAP_INL_H__ |
38 | |
39 | |
40 | #include <assert.h> |
41 | |
42 | #include "processor/range_map.h" |
43 | #include "processor/linked_ptr.h" |
44 | #include "processor/logging.h" |
45 | |
46 | |
47 | namespace google_breakpad { |
48 | |
49 | template<typename AddressType, typename EntryType> |
50 | bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType& base, |
51 | const AddressType& size, |
52 | const EntryType& entry) { |
53 | return StoreRangeInternal(base, 0 /* delta */, size, entry); |
54 | } |
55 | |
56 | template<typename AddressType, typename EntryType> |
57 | bool RangeMap<AddressType, EntryType>::StoreRangeInternal( |
58 | const AddressType& base, const AddressType& delta, |
59 | const AddressType& size, const EntryType& entry) { |
60 | AddressType high = base + (size - 1); |
61 | |
62 | // Check for undersize or overflow. |
63 | if (size <= 0 || high < base) { |
64 | // The processor will hit this case too frequently with common symbol |
65 | // files in the size == 0 case, which is more suited to a DEBUG channel. |
66 | // Filter those out since there's no DEBUG channel at the moment. |
67 | BPLOG_IF(INFO, size != 0) << "StoreRangeInternal failed, " |
68 | << HexString(base) << "+" << HexString(size) |
69 | << ", " << HexString(high) |
70 | << ", delta: " << HexString(delta); |
71 | return false; |
72 | } |
73 | |
74 | // Ensure that this range does not overlap with another one already in the |
75 | // map. |
76 | MapConstIterator iterator_base = map_.lower_bound(base); |
77 | MapConstIterator iterator_high = map_.lower_bound(high); |
78 | |
79 | if (iterator_base != iterator_high) { |
80 | // Some other range ends in the space used by this range. It may be |
81 | // contained within the space used by this range, or it may extend lower. |
82 | if (merge_strategy_ == MergeRangeStrategy::kTruncateLower) { |
83 | // kTruncate the range with the lower base address. |
84 | AddressType other_base = iterator_base->second.base(); |
85 | if (base < other_base) { |
86 | return StoreRangeInternal(base, delta, other_base - base, entry); |
87 | } else if (other_base < base) { |
88 | EntryType other_entry; |
89 | AddressType other_high, other_size, other_delta; |
90 | other_high = iterator_base->first; |
91 | RetrieveRange(other_high, &other_entry, &other_base, &other_delta, |
92 | &other_size); |
93 | map_.erase(iterator_base); |
94 | map_.insert( |
95 | MapValue(base - 1, Range(other_base, other_delta, other_entry))); |
96 | return StoreRangeInternal(base, delta, size, entry); |
97 | } else { |
98 | return false; |
99 | } |
100 | } else if (merge_strategy_ == MergeRangeStrategy::kTruncateUpper) { |
101 | // Truncate the lower portion of this range. |
102 | AddressType additional_delta = iterator_base->first - base + 1; |
103 | return StoreRangeInternal(base + additional_delta, |
104 | delta + additional_delta, |
105 | size - additional_delta, entry); |
106 | } else { |
107 | // The processor hits this case too frequently with common symbol files. |
108 | // This is most appropriate for a DEBUG channel, but since none exists |
109 | // now simply comment out this logging. |
110 | // AddressType other_base = iterator_base->second.base(); |
111 | // AddressType other_size = iterator_base->first - other_base + 1; |
112 | // BPLOG(INFO) << "StoreRangeInternal failed, an existing range is " |
113 | // << "overlapping with the new range: new " |
114 | // << HexString(base) << "+" << HexString(size) |
115 | // << ", existing " << HexString(other_base) << "+" |
116 | // << HexString(other_size); |
117 | return false; |
118 | } |
119 | } |
120 | |
121 | if (iterator_high != map_.end() && iterator_high->second.base() <= high) { |
122 | // The range above this one overlaps with this one. It may fully |
123 | // contain this range, or it may begin within this range and extend |
124 | // higher. |
125 | if (merge_strategy_ == MergeRangeStrategy::kTruncateLower) { |
126 | AddressType other_base = iterator_high->second.base(); |
127 | if (base < other_base) { |
128 | return StoreRangeInternal(base, delta, other_base - base, entry); |
129 | } else if (other_base < base) { |
130 | EntryType other_entry; |
131 | AddressType other_high, other_size, other_delta; |
132 | other_high = iterator_high->first; |
133 | RetrieveRange(other_high, &other_entry, &other_base, &other_delta, |
134 | &other_size); |
135 | map_.erase(iterator_high); |
136 | map_.insert( |
137 | MapValue(base - 1, Range(other_base, other_delta, other_entry))); |
138 | return StoreRangeInternal(base, delta, size, entry); |
139 | } else { |
140 | return false; |
141 | } |
142 | } else if (merge_strategy_ == MergeRangeStrategy::kTruncateUpper && |
143 | iterator_high->first > high) { |
144 | // Shrink the other range down. |
145 | AddressType other_high = iterator_high->first; |
146 | AddressType additional_delta = high - iterator_high->second.base() + 1; |
147 | EntryType other_entry; |
148 | AddressType other_base = AddressType(); |
149 | AddressType other_size = AddressType(); |
150 | AddressType other_delta = AddressType(); |
151 | RetrieveRange(other_high, &other_entry, &other_base, &other_delta, |
152 | &other_size); |
153 | map_.erase(iterator_high); |
154 | map_.insert(MapValue(other_high, |
155 | Range(other_base + additional_delta, |
156 | other_delta + additional_delta, other_entry))); |
157 | // Retry to store this range. |
158 | return StoreRangeInternal(base, delta, size, entry); |
159 | } else { |
160 | // The processor hits this case too frequently with common symbol files. |
161 | // This is most appropriate for a DEBUG channel, but since none exists |
162 | // now simply comment out this logging. |
163 | // |
164 | // AddressType other_base = iterator_high->second.base(); |
165 | // AddressType other_size = iterator_high->first - other_base + 1; |
166 | // BPLOG(INFO) << "StoreRangeInternal failed, an existing range " |
167 | // << "contains or extends higher than the new range: new " |
168 | // << HexString(base) << "+" << HexString(size) |
169 | // << ", existing " << HexString(other_base) << "+" |
170 | // << HexString(other_size); |
171 | return false; |
172 | } |
173 | } |
174 | |
175 | // Store the range in the map by its high address, so that lower_bound can |
176 | // be used to quickly locate a range by address. |
177 | map_.insert(MapValue(high, Range(base, delta, entry))); |
178 | return true; |
179 | } |
180 | |
181 | |
182 | template<typename AddressType, typename EntryType> |
183 | bool RangeMap<AddressType, EntryType>::RetrieveRange( |
184 | const AddressType& address, EntryType* entry, AddressType* entry_base, |
185 | AddressType* entry_delta, AddressType* entry_size) const { |
186 | BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|" ; |
187 | assert(entry); |
188 | |
189 | MapConstIterator iterator = map_.lower_bound(address); |
190 | if (iterator == map_.end()) |
191 | return false; |
192 | |
193 | // The map is keyed by the high address of each range, so |address| is |
194 | // guaranteed to be lower than the range's high address. If |range| is |
195 | // not directly preceded by another range, it's possible for address to |
196 | // be below the range's low address, though. When that happens, address |
197 | // references something not within any range, so return false. |
198 | if (address < iterator->second.base()) |
199 | return false; |
200 | |
201 | *entry = iterator->second.entry(); |
202 | if (entry_base) |
203 | *entry_base = iterator->second.base(); |
204 | if (entry_delta) |
205 | *entry_delta = iterator->second.delta(); |
206 | if (entry_size) |
207 | *entry_size = iterator->first - iterator->second.base() + 1; |
208 | |
209 | return true; |
210 | } |
211 | |
212 | |
213 | template<typename AddressType, typename EntryType> |
214 | bool RangeMap<AddressType, EntryType>::RetrieveNearestRange( |
215 | const AddressType& address, EntryType* entry, AddressType* entry_base, |
216 | AddressType* entry_delta, AddressType* entry_size) const { |
217 | BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|" ; |
218 | assert(entry); |
219 | |
220 | // If address is within a range, RetrieveRange can handle it. |
221 | if (RetrieveRange(address, entry, entry_base, entry_delta, entry_size)) |
222 | return true; |
223 | |
224 | // upper_bound gives the first element whose key is greater than address, |
225 | // but we want the first element whose key is less than or equal to address. |
226 | // Decrement the iterator to get there, but not if the upper_bound already |
227 | // points to the beginning of the map - in that case, address is lower than |
228 | // the lowest stored key, so return false. |
229 | MapConstIterator iterator = map_.upper_bound(address); |
230 | if (iterator == map_.begin()) |
231 | return false; |
232 | --iterator; |
233 | |
234 | *entry = iterator->second.entry(); |
235 | if (entry_base) |
236 | *entry_base = iterator->second.base(); |
237 | if (entry_delta) |
238 | *entry_delta = iterator->second.delta(); |
239 | if (entry_size) |
240 | *entry_size = iterator->first - iterator->second.base() + 1; |
241 | |
242 | return true; |
243 | } |
244 | |
245 | |
246 | template<typename AddressType, typename EntryType> |
247 | bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex( |
248 | int index, EntryType* entry, AddressType* entry_base, |
249 | AddressType* entry_delta, AddressType* entry_size) const { |
250 | BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|" ; |
251 | assert(entry); |
252 | |
253 | if (index >= GetCount()) { |
254 | BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount(); |
255 | return false; |
256 | } |
257 | |
258 | // Walk through the map. Although it's ordered, it's not a vector, so it |
259 | // can't be addressed directly by index. |
260 | MapConstIterator iterator = map_.begin(); |
261 | for (int this_index = 0; this_index < index; ++this_index) |
262 | ++iterator; |
263 | |
264 | *entry = iterator->second.entry(); |
265 | if (entry_base) |
266 | *entry_base = iterator->second.base(); |
267 | if (entry_delta) |
268 | *entry_delta = iterator->second.delta(); |
269 | if (entry_size) |
270 | *entry_size = iterator->first - iterator->second.base() + 1; |
271 | |
272 | return true; |
273 | } |
274 | |
275 | |
276 | template<typename AddressType, typename EntryType> |
277 | int RangeMap<AddressType, EntryType>::GetCount() const { |
278 | return static_cast<int>(map_.size()); |
279 | } |
280 | |
281 | |
282 | template<typename AddressType, typename EntryType> |
283 | void RangeMap<AddressType, EntryType>::Clear() { |
284 | map_.clear(); |
285 | } |
286 | |
287 | |
288 | } // namespace google_breakpad |
289 | |
290 | |
291 | #endif // PROCESSOR_RANGE_MAP_INL_H__ |
292 | |