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
46namespace google_breakpad {
47
48
49template<typename AddressType, typename EntryType>
50bool 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
117template<typename AddressType, typename EntryType>
118bool 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
146template<typename AddressType, typename EntryType>
147bool 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
177template<typename AddressType, typename EntryType>
178bool 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
205template<typename AddressType, typename EntryType>
206int RangeMap<AddressType, EntryType>::GetCount() const {
207  return map_.size();
208}
209
210
211template<typename AddressType, typename EntryType>
212void RangeMap<AddressType, EntryType>::Clear() {
213  map_.clear();
214}
215
216
217}  // namespace google_breakpad
218
219
220#endif  // PROCESSOR_RANGE_MAP_INL_H__
221