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