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
47namespace google_breakpad {
48
49template<typename AddressType, typename EntryType>
50bool 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
56template<typename AddressType, typename EntryType>
57bool 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
182template<typename AddressType, typename EntryType>
183bool 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
213template<typename AddressType, typename EntryType>
214bool 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
246template<typename AddressType, typename EntryType>
247bool 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
276template<typename AddressType, typename EntryType>
277int RangeMap<AddressType, EntryType>::GetCount() const {
278 return static_cast<int>(map_.size());
279}
280
281
282template<typename AddressType, typename EntryType>
283void RangeMap<AddressType, EntryType>::Clear() {
284 map_.clear();
285}
286
287
288} // namespace google_breakpad
289
290
291#endif // PROCESSOR_RANGE_MAP_INL_H__
292