OLD | NEW |
---|---|
1 // Copyright (c) 2010 Google Inc. | 1 // Copyright (c) 2010 Google Inc. |
2 // All rights reserved. | 2 // All rights reserved. |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted provided that the following conditions are | 5 // modification, are permitted provided that the following conditions are |
6 // met: | 6 // met: |
7 // | 7 // |
8 // * Redistributions of source code must retain the above copyright | 8 // * Redistributions of source code must retain the above copyright |
9 // notice, this list of conditions and the following disclaimer. | 9 // notice, this list of conditions and the following disclaimer. |
10 // * Redistributions in binary form must reproduce the above | 10 // * Redistributions in binary form must reproduce the above |
(...skipping 22 matching lines...) Expand all Loading... | |
33 // | 33 // |
34 // Author: Mark Mentovai | 34 // Author: Mark Mentovai |
35 | 35 |
36 #ifndef PROCESSOR_RANGE_MAP_INL_H__ | 36 #ifndef PROCESSOR_RANGE_MAP_INL_H__ |
37 #define PROCESSOR_RANGE_MAP_INL_H__ | 37 #define PROCESSOR_RANGE_MAP_INL_H__ |
38 | 38 |
39 | 39 |
40 #include <assert.h> | 40 #include <assert.h> |
41 | 41 |
42 #include "processor/range_map.h" | 42 #include "processor/range_map.h" |
43 #include "processor/linked_ptr.h" | |
43 #include "processor/logging.h" | 44 #include "processor/logging.h" |
44 | 45 |
45 | 46 |
46 namespace google_breakpad { | 47 namespace google_breakpad { |
47 | 48 |
49 template<typename AddressType, typename EntryType> | |
50 void RangeMap<AddressType, EntryType>::SetEnableShrinkDown( | |
51 bool enable_shrink_down) { | |
52 enable_shrink_down_ = enable_shrink_down; | |
53 } | |
48 | 54 |
49 template<typename AddressType, typename EntryType> | 55 template<typename AddressType, typename EntryType> |
50 bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base, | 56 bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base, |
57 const AddressType &delta, | |
51 const AddressType &size, | 58 const AddressType &size, |
52 const EntryType &entry) { | 59 const EntryType &entry) { |
53 AddressType high = base + (size - 1); | 60 AddressType high = base + (size - 1); |
54 | 61 |
55 // Check for undersize or overflow. | 62 // Check for undersize or overflow. |
56 if (size <= 0 || high < base) { | 63 if (size <= 0 || high < base) { |
57 // The processor will hit this case too frequently with common symbol | 64 // 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. | 65 // 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. | 66 // Filter those out since there's no DEBUG channel at the moment. |
60 BPLOG_IF(INFO, size != 0) << "StoreRange failed, " << HexString(base) << | 67 BPLOG_IF(INFO, size != 0) << "StoreRange failed, " << HexString(base) |
61 "+" << HexString(size) << ", " << | 68 << "+" << HexString(size) << ", " |
62 HexString(high); | 69 << HexString(high); |
63 return false; | 70 return false; |
64 } | 71 } |
65 | 72 |
66 // Ensure that this range does not overlap with another one already in the | 73 // Ensure that this range does not overlap with another one already in the |
67 // map. | 74 // map. |
68 MapConstIterator iterator_base = map_.lower_bound(base); | 75 MapConstIterator iterator_base = map_.lower_bound(base); |
69 MapConstIterator iterator_high = map_.lower_bound(high); | 76 MapConstIterator iterator_high = map_.lower_bound(high); |
70 | 77 |
71 if (iterator_base != iterator_high) { | 78 if (iterator_base != iterator_high) { |
72 // Some other range begins in the space used by this range. It may be | 79 // 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. | 80 // contained within the space used by this range, or it may extend lower. |
74 // Regardless, it is an error. | 81 // If enable_shrink_down_ is true, shrink the current range down, otherwise |
75 // The processor hits this case too frequently with common symbol files. | 82 // this is an error. |
76 // This is most appropriate for a DEBUG channel, but since none exists now | 83 if (enable_shrink_down_) { |
77 // simply comment out this logging. | 84 AddressType additional_delta = iterator_base->first - base + 1; |
78 // | 85 return StoreRange(base + additional_delta, delta + additional_delta, |
79 // AddressType other_base = iterator_base->second.base(); | 86 size - additional_delta, entry); |
80 // AddressType other_size = iterator_base->first - other_base + 1; | 87 } else { |
81 // BPLOG(INFO) << "StoreRange failed, an existing range is contained by or " | 88 // AddressType other_base = iterator_base->second.base(); |
82 // "extends lower than the new range: new " << | 89 // AddressType other_size = iterator_base->first - other_base + 1; |
83 // HexString(base) << "+" << HexString(size) << | 90 // BPLOG(INFO) << "StoreRange failed, an existing range is overlapping " |
84 // ", existing " << HexString(other_base) << "+" << | 91 // << "with the new range: new " << HexString(base) |
85 // HexString(other_size); | 92 // << "+" << HexString(size) << ", existing " |
86 | 93 // << HexString(other_base) << "+" << HexString(other_size); |
87 return false; | 94 return false; |
95 } | |
88 } | 96 } |
89 | 97 |
90 if (iterator_high != map_.end()) { | 98 if (iterator_high != map_.end()) { |
91 if (iterator_high->second.base() <= high) { | 99 if (iterator_high->second.base() <= high) { |
92 // The range above this one overlaps with this one. It may fully | 100 // 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 | 101 // contain this range, or it may begin within this range and extend |
94 // higher. Regardless, it's an error. | 102 // higher. If enable_shrink_down_ is true, shrink the other range down, |
95 // The processor hits this case too frequently with common symbol files. | 103 // otherwise this is an error. |
96 // This is most appropriate for a DEBUG channel, but since none exists now | 104 if (enable_shrink_down_ && iterator_high->first > high) { |
97 // simply comment out this logging. | 105 // Shrink the other range down. |
98 // | 106 AddressType other_high = iterator_high->first; |
99 // AddressType other_base = iterator_high->second.base(); | 107 AddressType additional_delta = |
100 // AddressType other_size = iterator_high->first - other_base + 1; | 108 high - iterator_high->second.base() + 1; |
101 // BPLOG(INFO) << "StoreRange failed, an existing range contains or " | 109 EntryType other_entry; |
102 // "extends higher than the new range: new " << | 110 AddressType other_base = AddressType(); |
103 // HexString(base) << "+" << HexString(size) << | 111 AddressType other_size = AddressType(); |
104 // ", existing " << HexString(other_base) << "+" << | 112 AddressType other_delta = AddressType(); |
105 // HexString(other_size); | 113 RetrieveRange(other_high, &other_entry, &other_base, &other_delta, |
106 return false; | 114 &other_size); |
115 map_.erase(iterator_high); | |
116 map_.insert(MapValue(other_high, | |
117 Range(other_base + additional_delta, | |
118 other_delta + additional_delta, | |
119 other_entry))); | |
120 // Retry to store this range. | |
121 return StoreRange(base, delta, size, entry); | |
122 } else { | |
123 // The processor hits this case too frequently with common symbol files. | |
124 // This is most appropriate for a DEBUG channel, but since none exists n ow | |
Mark Mentovai
2016/06/02 21:43:53
Rewrap this comment.
ivanpe
2016/06/02 22:54:02
Done.
| |
125 // simply comment out this logging. | |
126 // | |
127 // AddressType other_base = iterator_high->second.base(); | |
128 // AddressType other_size = iterator_high->first - other_base + 1; | |
129 // BPLOG(INFO) << "StoreRange failed, an existing range contains or " | |
130 // "extends higher than the new range: new " << | |
131 // HexString(base) << "+" << HexString(size) << | |
132 // ", existing " << HexString(other_base) << "+" << | |
133 // HexString(other_size); | |
134 return false; | |
135 } | |
107 } | 136 } |
108 } | 137 } |
109 | 138 |
110 // Store the range in the map by its high address, so that lower_bound can | 139 // 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. | 140 // be used to quickly locate a range by address. |
112 map_.insert(MapValue(high, Range(base, entry))); | 141 map_.insert(MapValue(high, Range(base, delta, entry))); |
113 return true; | 142 return true; |
114 } | 143 } |
115 | 144 |
116 | 145 |
117 template<typename AddressType, typename EntryType> | 146 template<typename AddressType, typename EntryType> |
118 bool RangeMap<AddressType, EntryType>::RetrieveRange( | 147 bool RangeMap<AddressType, EntryType>::RetrieveRange( |
119 const AddressType &address, EntryType *entry, | 148 const AddressType &address, EntryType *entry, AddressType *entry_base, |
120 AddressType *entry_base, AddressType *entry_size) const { | 149 AddressType *entry_delta, AddressType *entry_size) const { |
121 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|"; | 150 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|"; |
122 assert(entry); | 151 assert(entry); |
123 | 152 |
124 MapConstIterator iterator = map_.lower_bound(address); | 153 MapConstIterator iterator = map_.lower_bound(address); |
125 if (iterator == map_.end()) | 154 if (iterator == map_.end()) |
126 return false; | 155 return false; |
127 | 156 |
128 // The map is keyed by the high address of each range, so |address| is | 157 // 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 | 158 // 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 | 159 // 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 | 160 // be below the range's low address, though. When that happens, address |
132 // references something not within any range, so return false. | 161 // references something not within any range, so return false. |
133 if (address < iterator->second.base()) | 162 if (address < iterator->second.base()) |
134 return false; | 163 return false; |
135 | 164 |
136 *entry = iterator->second.entry(); | 165 *entry = iterator->second.entry(); |
137 if (entry_base) | 166 if (entry_base) |
138 *entry_base = iterator->second.base(); | 167 *entry_base = iterator->second.base(); |
168 if (entry_delta) | |
169 *entry_delta = iterator->second.delta(); | |
139 if (entry_size) | 170 if (entry_size) |
140 *entry_size = iterator->first - iterator->second.base() + 1; | 171 *entry_size = iterator->first - iterator->second.base() + 1; |
141 | 172 |
142 return true; | 173 return true; |
143 } | 174 } |
144 | 175 |
145 | 176 |
146 template<typename AddressType, typename EntryType> | 177 template<typename AddressType, typename EntryType> |
147 bool RangeMap<AddressType, EntryType>::RetrieveNearestRange( | 178 bool RangeMap<AddressType, EntryType>::RetrieveNearestRange( |
148 const AddressType &address, EntryType *entry, | 179 const AddressType &address, EntryType *entry, AddressType *entry_base, |
149 AddressType *entry_base, AddressType *entry_size) const { | 180 AddressType *entry_delta, AddressType *entry_size) const { |
150 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|"; | 181 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|"; |
151 assert(entry); | 182 assert(entry); |
152 | 183 |
153 // If address is within a range, RetrieveRange can handle it. | 184 // If address is within a range, RetrieveRange can handle it. |
154 if (RetrieveRange(address, entry, entry_base, entry_size)) | 185 if (RetrieveRange(address, entry, entry_base, entry_delta, entry_size)) |
155 return true; | 186 return true; |
156 | 187 |
157 // upper_bound gives the first element whose key is greater than address, | 188 // 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. | 189 // 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 | 190 // 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 | 191 // points to the beginning of the map - in that case, address is lower than |
161 // the lowest stored key, so return false. | 192 // the lowest stored key, so return false. |
162 MapConstIterator iterator = map_.upper_bound(address); | 193 MapConstIterator iterator = map_.upper_bound(address); |
163 if (iterator == map_.begin()) | 194 if (iterator == map_.begin()) |
164 return false; | 195 return false; |
165 --iterator; | 196 --iterator; |
166 | 197 |
167 *entry = iterator->second.entry(); | 198 *entry = iterator->second.entry(); |
168 if (entry_base) | 199 if (entry_base) |
169 *entry_base = iterator->second.base(); | 200 *entry_base = iterator->second.base(); |
201 if (entry_delta) | |
202 *entry_delta = iterator->second.delta(); | |
170 if (entry_size) | 203 if (entry_size) |
171 *entry_size = iterator->first - iterator->second.base() + 1; | 204 *entry_size = iterator->first - iterator->second.base() + 1; |
172 | 205 |
173 return true; | 206 return true; |
174 } | 207 } |
175 | 208 |
176 | 209 |
177 template<typename AddressType, typename EntryType> | 210 template<typename AddressType, typename EntryType> |
178 bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex( | 211 bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex( |
179 int index, EntryType *entry, | 212 int index, EntryType *entry, AddressType *entry_base, |
180 AddressType *entry_base, AddressType *entry_size) const { | 213 AddressType *entry_delta, AddressType *entry_size) const { |
181 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|"; | 214 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|"; |
182 assert(entry); | 215 assert(entry); |
183 | 216 |
184 if (index >= GetCount()) { | 217 if (index >= GetCount()) { |
185 BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount(); | 218 BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount(); |
186 return false; | 219 return false; |
187 } | 220 } |
188 | 221 |
189 // Walk through the map. Although it's ordered, it's not a vector, so it | 222 // Walk through the map. Although it's ordered, it's not a vector, so it |
190 // can't be addressed directly by index. | 223 // can't be addressed directly by index. |
191 MapConstIterator iterator = map_.begin(); | 224 MapConstIterator iterator = map_.begin(); |
192 for (int this_index = 0; this_index < index; ++this_index) | 225 for (int this_index = 0; this_index < index; ++this_index) |
193 ++iterator; | 226 ++iterator; |
194 | 227 |
195 *entry = iterator->second.entry(); | 228 *entry = iterator->second.entry(); |
196 if (entry_base) | 229 if (entry_base) |
197 *entry_base = iterator->second.base(); | 230 *entry_base = iterator->second.base(); |
231 if (entry_delta) | |
232 *entry_delta = iterator->second.delta(); | |
198 if (entry_size) | 233 if (entry_size) |
199 *entry_size = iterator->first - iterator->second.base() + 1; | 234 *entry_size = iterator->first - iterator->second.base() + 1; |
200 | 235 |
201 return true; | 236 return true; |
202 } | 237 } |
203 | 238 |
204 | 239 |
205 template<typename AddressType, typename EntryType> | 240 template<typename AddressType, typename EntryType> |
206 int RangeMap<AddressType, EntryType>::GetCount() const { | 241 int RangeMap<AddressType, EntryType>::GetCount() const { |
207 return map_.size(); | 242 return map_.size(); |
208 } | 243 } |
209 | 244 |
210 | 245 |
211 template<typename AddressType, typename EntryType> | 246 template<typename AddressType, typename EntryType> |
212 void RangeMap<AddressType, EntryType>::Clear() { | 247 void RangeMap<AddressType, EntryType>::Clear() { |
213 map_.clear(); | 248 map_.clear(); |
214 } | 249 } |
215 | 250 |
216 | 251 |
217 } // namespace google_breakpad | 252 } // namespace google_breakpad |
218 | 253 |
219 | 254 |
220 #endif // PROCESSOR_RANGE_MAP_INL_H__ | 255 #endif // PROCESSOR_RANGE_MAP_INL_H__ |
256 | |
OLD | NEW |