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, |
51 const AddressType &size, | 57 const AddressType &size, |
52 const EntryType &entry) { | 58 const EntryType &entry) { |
59 return StoreRangeInternal(base, 0 /* delta */, size, entry); | |
60 } | |
61 | |
62 template<typename AddressType, typename EntryType> | |
63 bool RangeMap<AddressType, EntryType>::StoreRangeInternal( | |
64 const AddressType &base, const AddressType &delta, | |
65 const AddressType &size, const EntryType &entry) { | |
53 AddressType high = base + (size - 1); | 66 AddressType high = base + (size - 1); |
54 | 67 |
55 // Check for undersize or overflow. | 68 // Check for undersize or overflow. |
56 if (size <= 0 || high < base) { | 69 if (size <= 0 || high < base) { |
57 // The processor will hit this case too frequently with common symbol | 70 // 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. | 71 // 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. | 72 // Filter those out since there's no DEBUG channel at the moment. |
60 BPLOG_IF(INFO, size != 0) << "StoreRange failed, " << HexString(base) << | 73 BPLOG_IF(INFO, size != 0) << "StoreRangeInternal failed, " |
61 "+" << HexString(size) << ", " << | 74 << HexString(base) << "+" << HexString(size) |
mmandlis
2016/06/02 23:50:59
should you add the |delta| to the log as well?
ivanpe
2016/06/03 03:56:55
Done.
| |
62 HexString(high); | 75 << ", " << HexString(high); |
63 return false; | 76 return false; |
64 } | 77 } |
65 | 78 |
66 // Ensure that this range does not overlap with another one already in the | 79 // Ensure that this range does not overlap with another one already in the |
mmandlis
2016/06/02 23:50:59
You might want to rephrase the comment "Ensure tha
ivanpe
2016/06/03 03:56:55
By default, shrink-down is off, so in the common c
| |
67 // map. | 80 // map. |
68 MapConstIterator iterator_base = map_.lower_bound(base); | 81 MapConstIterator iterator_base = map_.lower_bound(base); |
69 MapConstIterator iterator_high = map_.lower_bound(high); | 82 MapConstIterator iterator_high = map_.lower_bound(high); |
70 | 83 |
71 if (iterator_base != iterator_high) { | 84 if (iterator_base != iterator_high) { |
72 // Some other range begins in the space used by this range. It may be | 85 // 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. | 86 // contained within the space used by this range, or it may extend lower. |
74 // Regardless, it is an error. | 87 // If enable_shrink_down_ is true, shrink the current range down, otherwise |
75 // The processor hits this case too frequently with common symbol files. | 88 // this is an error. |
76 // This is most appropriate for a DEBUG channel, but since none exists now | 89 if (enable_shrink_down_) { |
77 // simply comment out this logging. | 90 AddressType additional_delta = iterator_base->first - base + 1; |
78 // | 91 return StoreRangeInternal(base + additional_delta, |
mmandlis
2016/06/02 23:50:59
in the comments you explained that the address wit
ivanpe
2016/06/03 03:56:55
Yes, the one that is shrunk can already be in the
| |
79 // AddressType other_base = iterator_base->second.base(); | 92 delta + additional_delta, |
80 // AddressType other_size = iterator_base->first - other_base + 1; | 93 size - additional_delta, entry); |
mmandlis
2016/06/02 23:50:59
is the recursive call really necessary, or could y
ivanpe
2016/06/03 03:56:55
I feel it is cleaner and easier to understand with
| |
81 // BPLOG(INFO) << "StoreRange failed, an existing range is contained by or " | 94 } else { |
82 // "extends lower than the new range: new " << | 95 // AddressType other_base = iterator_base->second.base(); |
mmandlis
2016/06/02 23:50:59
there was originally this comment explaining:
"
//
ivanpe
2016/06/03 03:56:55
Good point. Added it back.
| |
83 // HexString(base) << "+" << HexString(size) << | 96 // AddressType other_size = iterator_base->first - other_base + 1; |
84 // ", existing " << HexString(other_base) << "+" << | 97 // BPLOG(INFO) << "StoreRangeInternal failed, an existing range is " |
85 // HexString(other_size); | 98 // << "overlapping with the new range: new " |
86 | 99 // << HexString(base) << "+" << HexString(size) |
87 return false; | 100 // << ", existing " << HexString(other_base) << "+" |
101 // << HexString(other_size); | |
102 return false; | |
103 } | |
88 } | 104 } |
89 | 105 |
90 if (iterator_high != map_.end()) { | 106 if (iterator_high != map_.end()) { |
91 if (iterator_high->second.base() <= high) { | 107 if (iterator_high->second.base() <= high) { |
92 // The range above this one overlaps with this one. It may fully | 108 // 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 | 109 // contain this range, or it may begin within this range and extend |
94 // higher. Regardless, it's an error. | 110 // higher. If enable_shrink_down_ is true, shrink the other range down, |
95 // The processor hits this case too frequently with common symbol files. | 111 // otherwise this is an error. |
96 // This is most appropriate for a DEBUG channel, but since none exists now | 112 if (enable_shrink_down_ && iterator_high->first > high) { |
97 // simply comment out this logging. | 113 // Shrink the other range down. |
98 // | 114 AddressType other_high = iterator_high->first; |
99 // AddressType other_base = iterator_high->second.base(); | 115 AddressType additional_delta = |
100 // AddressType other_size = iterator_high->first - other_base + 1; | 116 high - iterator_high->second.base() + 1; |
101 // BPLOG(INFO) << "StoreRange failed, an existing range contains or " | 117 EntryType other_entry; |
102 // "extends higher than the new range: new " << | 118 AddressType other_base = AddressType(); |
103 // HexString(base) << "+" << HexString(size) << | 119 AddressType other_size = AddressType(); |
104 // ", existing " << HexString(other_base) << "+" << | 120 AddressType other_delta = AddressType(); |
105 // HexString(other_size); | 121 RetrieveRange(other_high, &other_entry, &other_base, &other_delta, |
106 return false; | 122 &other_size); |
123 map_.erase(iterator_high); | |
124 map_.insert(MapValue(other_high, | |
125 Range(other_base + additional_delta, | |
126 other_delta + additional_delta, | |
127 other_entry))); | |
128 // Retry to store this range. | |
129 return StoreRangeInternal(base, delta, size, entry); | |
130 } else { | |
131 // The processor hits this case too frequently with common symbol files. | |
132 // This is most appropriate for a DEBUG channel, but since none exists | |
133 // now simply comment out this logging. | |
134 // | |
135 // AddressType other_base = iterator_high->second.base(); | |
136 // AddressType other_size = iterator_high->first - other_base + 1; | |
137 // BPLOG(INFO) << "StoreRangeInternal failed, an existing range " | |
138 // << "contains or extends higher than the new range: new " | |
139 // << HexString(base) << "+" << HexString(size) | |
140 // << ", existing " << HexString(other_base) << "+" | |
141 // << HexString(other_size); | |
142 return false; | |
143 } | |
107 } | 144 } |
108 } | 145 } |
109 | 146 |
110 // Store the range in the map by its high address, so that lower_bound can | 147 // 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. | 148 // be used to quickly locate a range by address. |
112 map_.insert(MapValue(high, Range(base, entry))); | 149 map_.insert(MapValue(high, Range(base, delta, entry))); |
113 return true; | 150 return true; |
114 } | 151 } |
115 | 152 |
116 | 153 |
117 template<typename AddressType, typename EntryType> | 154 template<typename AddressType, typename EntryType> |
118 bool RangeMap<AddressType, EntryType>::RetrieveRange( | 155 bool RangeMap<AddressType, EntryType>::RetrieveRange( |
119 const AddressType &address, EntryType *entry, | 156 const AddressType &address, EntryType *entry, AddressType *entry_base, |
120 AddressType *entry_base, AddressType *entry_size) const { | 157 AddressType *entry_delta, AddressType *entry_size) const { |
121 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|"; | 158 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|"; |
122 assert(entry); | 159 assert(entry); |
123 | 160 |
124 MapConstIterator iterator = map_.lower_bound(address); | 161 MapConstIterator iterator = map_.lower_bound(address); |
125 if (iterator == map_.end()) | 162 if (iterator == map_.end()) |
126 return false; | 163 return false; |
127 | 164 |
128 // The map is keyed by the high address of each range, so |address| is | 165 // 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 | 166 // 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 | 167 // 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 | 168 // be below the range's low address, though. When that happens, address |
132 // references something not within any range, so return false. | 169 // references something not within any range, so return false. |
133 if (address < iterator->second.base()) | 170 if (address < iterator->second.base()) |
134 return false; | 171 return false; |
135 | 172 |
136 *entry = iterator->second.entry(); | 173 *entry = iterator->second.entry(); |
137 if (entry_base) | 174 if (entry_base) |
138 *entry_base = iterator->second.base(); | 175 *entry_base = iterator->second.base(); |
176 if (entry_delta) | |
177 *entry_delta = iterator->second.delta(); | |
139 if (entry_size) | 178 if (entry_size) |
140 *entry_size = iterator->first - iterator->second.base() + 1; | 179 *entry_size = iterator->first - iterator->second.base() + 1; |
141 | 180 |
142 return true; | 181 return true; |
143 } | 182 } |
144 | 183 |
145 | 184 |
146 template<typename AddressType, typename EntryType> | 185 template<typename AddressType, typename EntryType> |
147 bool RangeMap<AddressType, EntryType>::RetrieveNearestRange( | 186 bool RangeMap<AddressType, EntryType>::RetrieveNearestRange( |
148 const AddressType &address, EntryType *entry, | 187 const AddressType &address, EntryType *entry, AddressType *entry_base, |
149 AddressType *entry_base, AddressType *entry_size) const { | 188 AddressType *entry_delta, AddressType *entry_size) const { |
150 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|"; | 189 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|"; |
151 assert(entry); | 190 assert(entry); |
152 | 191 |
153 // If address is within a range, RetrieveRange can handle it. | 192 // If address is within a range, RetrieveRange can handle it. |
154 if (RetrieveRange(address, entry, entry_base, entry_size)) | 193 if (RetrieveRange(address, entry, entry_base, entry_delta, entry_size)) |
155 return true; | 194 return true; |
156 | 195 |
157 // upper_bound gives the first element whose key is greater than address, | 196 // 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. | 197 // 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 | 198 // 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 | 199 // points to the beginning of the map - in that case, address is lower than |
161 // the lowest stored key, so return false. | 200 // the lowest stored key, so return false. |
162 MapConstIterator iterator = map_.upper_bound(address); | 201 MapConstIterator iterator = map_.upper_bound(address); |
163 if (iterator == map_.begin()) | 202 if (iterator == map_.begin()) |
164 return false; | 203 return false; |
165 --iterator; | 204 --iterator; |
166 | 205 |
167 *entry = iterator->second.entry(); | 206 *entry = iterator->second.entry(); |
168 if (entry_base) | 207 if (entry_base) |
169 *entry_base = iterator->second.base(); | 208 *entry_base = iterator->second.base(); |
209 if (entry_delta) | |
210 *entry_delta = iterator->second.delta(); | |
170 if (entry_size) | 211 if (entry_size) |
171 *entry_size = iterator->first - iterator->second.base() + 1; | 212 *entry_size = iterator->first - iterator->second.base() + 1; |
172 | 213 |
173 return true; | 214 return true; |
174 } | 215 } |
175 | 216 |
176 | 217 |
177 template<typename AddressType, typename EntryType> | 218 template<typename AddressType, typename EntryType> |
178 bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex( | 219 bool RangeMap<AddressType, EntryType>::RetrieveRangeAtIndex( |
179 int index, EntryType *entry, | 220 int index, EntryType *entry, AddressType *entry_base, |
180 AddressType *entry_base, AddressType *entry_size) const { | 221 AddressType *entry_delta, AddressType *entry_size) const { |
181 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|"; | 222 BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|"; |
182 assert(entry); | 223 assert(entry); |
183 | 224 |
184 if (index >= GetCount()) { | 225 if (index >= GetCount()) { |
185 BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount(); | 226 BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount(); |
186 return false; | 227 return false; |
187 } | 228 } |
188 | 229 |
189 // Walk through the map. Although it's ordered, it's not a vector, so it | 230 // Walk through the map. Although it's ordered, it's not a vector, so it |
190 // can't be addressed directly by index. | 231 // can't be addressed directly by index. |
191 MapConstIterator iterator = map_.begin(); | 232 MapConstIterator iterator = map_.begin(); |
192 for (int this_index = 0; this_index < index; ++this_index) | 233 for (int this_index = 0; this_index < index; ++this_index) |
193 ++iterator; | 234 ++iterator; |
194 | 235 |
195 *entry = iterator->second.entry(); | 236 *entry = iterator->second.entry(); |
196 if (entry_base) | 237 if (entry_base) |
197 *entry_base = iterator->second.base(); | 238 *entry_base = iterator->second.base(); |
239 if (entry_delta) | |
240 *entry_delta = iterator->second.delta(); | |
198 if (entry_size) | 241 if (entry_size) |
199 *entry_size = iterator->first - iterator->second.base() + 1; | 242 *entry_size = iterator->first - iterator->second.base() + 1; |
200 | 243 |
201 return true; | 244 return true; |
202 } | 245 } |
203 | 246 |
204 | 247 |
205 template<typename AddressType, typename EntryType> | 248 template<typename AddressType, typename EntryType> |
206 int RangeMap<AddressType, EntryType>::GetCount() const { | 249 int RangeMap<AddressType, EntryType>::GetCount() const { |
207 return map_.size(); | 250 return map_.size(); |
208 } | 251 } |
209 | 252 |
210 | 253 |
211 template<typename AddressType, typename EntryType> | 254 template<typename AddressType, typename EntryType> |
212 void RangeMap<AddressType, EntryType>::Clear() { | 255 void RangeMap<AddressType, EntryType>::Clear() { |
213 map_.clear(); | 256 map_.clear(); |
214 } | 257 } |
215 | 258 |
216 | 259 |
217 } // namespace google_breakpad | 260 } // namespace google_breakpad |
218 | 261 |
219 | 262 |
220 #endif // PROCESSOR_RANGE_MAP_INL_H__ | 263 #endif // PROCESSOR_RANGE_MAP_INL_H__ |
OLD | NEW |