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/logging.h"
44
45
46 namespace google_breakpad {
47
48
49 template<typename AddressType, typename EntryType>
StoreRange(const AddressType & base,const AddressType & size,const EntryType & entry)50 bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base,
51 const AddressType &size,
52 const EntryType &entry) {
53 AddressType high = base + size - 1;
54
55 // Check for undersize or overflow.
56 if (size <= 0 || high < base) {
57 // The processor will hit this case too frequently with common symbol
58 // files in the size == 0 case, which is more suited to a DEBUG channel.
59 // Filter those out since there's no DEBUG channel at the moment.
60 BPLOG_IF(INFO, size != 0) << "StoreRange failed, " << HexString(base) <<
61 "+" << HexString(size) << ", " <<
62 HexString(high);
63 return false;
64 }
65
66 // Ensure that this range does not overlap with another one already in the
67 // map.
68 MapConstIterator iterator_base = map_.lower_bound(base);
69 MapConstIterator iterator_high = map_.lower_bound(high);
70
71 if (iterator_base != iterator_high) {
72 // Some other range begins in the space used by this range. It may be
73 // contained within the space used by this range, or it may extend lower.
74 // Regardless, it is an error.
75 // The processor hits this case too frequently with common symbol files.
76 // This is most appropriate for a DEBUG channel, but since none exists now
77 // simply comment out this logging.
78 //
79 // AddressType other_base = iterator_base->second.base();
80 // AddressType other_size = iterator_base->first - other_base + 1;
81 // BPLOG(INFO) << "StoreRange failed, an existing range is contained by or "
82 // "extends lower than the new range: new " <<
83 // HexString(base) << "+" << HexString(size) <<
84 // ", existing " << HexString(other_base) << "+" <<
85 // HexString(other_size);
86
87 return false;
88 }
89
90 if (iterator_high != map_.end()) {
91 if (iterator_high->second.base() <= high) {
92 // The range above this one overlaps with this one. It may fully
93 // contain this range, or it may begin within this range and extend
94 // higher. Regardless, it's an error.
95 // The processor hits this case too frequently with common symbol files.
96 // This is most appropriate for a DEBUG channel, but since none exists now
97 // simply comment out this logging.
98 //
99 // AddressType other_base = iterator_high->second.base();
100 // AddressType other_size = iterator_high->first - other_base + 1;
101 // BPLOG(INFO) << "StoreRange failed, an existing range contains or "
102 // "extends higher than the new range: new " <<
103 // HexString(base) << "+" << HexString(size) <<
104 // ", existing " << HexString(other_base) << "+" <<
105 // HexString(other_size);
106 return false;
107 }
108 }
109
110 // Store the range in the map by its high address, so that lower_bound can
111 // be used to quickly locate a range by address.
112 map_.insert(MapValue(high, Range(base, entry)));
113 return true;
114 }
115
116
117 template<typename AddressType, typename EntryType>
RetrieveRange(const AddressType & address,EntryType * entry,AddressType * entry_base,AddressType * entry_size)118 bool RangeMap<AddressType, EntryType>::RetrieveRange(
119 const AddressType &address, EntryType *entry,
120 AddressType *entry_base, AddressType *entry_size) const {
121 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|";
122 assert(entry);
123
124 MapConstIterator iterator = map_.lower_bound(address);
125 if (iterator == map_.end())
126 return false;
127
128 // The map is keyed by the high address of each range, so |address| is
129 // guaranteed to be lower than the range's high address. If |range| is
130 // not directly preceded by another range, it's possible for address to
131 // be below the range's low address, though. When that happens, address
132 // references something not within any range, so return false.
133 if (address < iterator->second.base())
134 return false;
135
136 *entry = iterator->second.entry();
137 if (entry_base)
138 *entry_base = iterator->second.base();
139 if (entry_size)
140 *entry_size = iterator->first - iterator->second.base() + 1;
141
142 return true;
143 }
144
145
146 template<typename AddressType, typename EntryType>
RetrieveNearestRange(const AddressType & address,EntryType * entry,AddressType * entry_base,AddressType * entry_size)147 bool RangeMap<AddressType, EntryType>::RetrieveNearestRange(
148 const AddressType &address, EntryType *entry,
149 AddressType *entry_base, AddressType *entry_size) const {
150 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|";
151 assert(entry);
152
153 // If address is within a range, RetrieveRange can handle it.
154 if (RetrieveRange(address, entry, entry_base, entry_size))
155 return true;
156
157 // upper_bound gives the first element whose key is greater than address,
158 // but we want the first element whose key is less than or equal to address.
159 // Decrement the iterator to get there, but not if the upper_bound already
160 // points to the beginning of the map - in that case, address is lower than
161 // the lowest stored key, so return false.
162 MapConstIterator iterator = map_.upper_bound(address);
163 if (iterator == map_.begin())
164 return false;
165 --iterator;
166
167 *entry = iterator->second.entry();
168 if (entry_base)
169 *entry_base = iterator->second.base();
170 if (entry_size)
171 *entry_size = iterator->first - iterator->second.base() + 1;
172
173 return true;
174 }
175
176
177 template<typename AddressType, typename EntryType>
RetrieveRangeAtIndex(int index,EntryType * entry,AddressType * entry_base,AddressType * entry_size)178 bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex(
179 int index, EntryType *entry,
180 AddressType *entry_base, AddressType *entry_size) const {
181 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|";
182 assert(entry);
183
184 if (index >= GetCount()) {
185 BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount();
186 return false;
187 }
188
189 // Walk through the map. Although it's ordered, it's not a vector, so it
190 // can't be addressed directly by index.
191 MapConstIterator iterator = map_.begin();
192 for (int this_index = 0; this_index < index; ++this_index)
193 ++iterator;
194
195 *entry = iterator->second.entry();
196 if (entry_base)
197 *entry_base = iterator->second.base();
198 if (entry_size)
199 *entry_size = iterator->first - iterator->second.base() + 1;
200
201 return true;
202 }
203
204
205 template<typename AddressType, typename EntryType>
GetCount()206 int RangeMap<AddressType, EntryType>::GetCount() const {
207 return map_.size();
208 }
209
210
211 template<typename AddressType, typename EntryType>
Clear()212 void RangeMap<AddressType, EntryType>::Clear() {
213 map_.clear();
214 }
215
216
217 } // namespace google_breakpad
218
219
220 #endif // PROCESSOR_RANGE_MAP_INL_H__
221