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