1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/crashreporter/google-breakpad/src/processor/contained_range_map-inl.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,197 @@
1.4 +// Copyright (c) 2006, Google Inc.
1.5 +// All rights reserved.
1.6 +//
1.7 +// Redistribution and use in source and binary forms, with or without
1.8 +// modification, are permitted provided that the following conditions are
1.9 +// met:
1.10 +//
1.11 +// * Redistributions of source code must retain the above copyright
1.12 +// notice, this list of conditions and the following disclaimer.
1.13 +// * Redistributions in binary form must reproduce the above
1.14 +// copyright notice, this list of conditions and the following disclaimer
1.15 +// in the documentation and/or other materials provided with the
1.16 +// distribution.
1.17 +// * Neither the name of Google Inc. nor the names of its
1.18 +// contributors may be used to endorse or promote products derived from
1.19 +// this software without specific prior written permission.
1.20 +//
1.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.22 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.23 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.24 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.25 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.26 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.27 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.28 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.29 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.30 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.31 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.32 +
1.33 +// contained_range_map-inl.h: Hierarchically-organized range map implementation.
1.34 +//
1.35 +// See contained_range_map.h for documentation.
1.36 +//
1.37 +// Author: Mark Mentovai
1.38 +
1.39 +#ifndef PROCESSOR_CONTAINED_RANGE_MAP_INL_H__
1.40 +#define PROCESSOR_CONTAINED_RANGE_MAP_INL_H__
1.41 +
1.42 +#include "processor/contained_range_map.h"
1.43 +
1.44 +#include <assert.h>
1.45 +
1.46 +#include "common/logging.h"
1.47 +
1.48 +
1.49 +namespace google_breakpad {
1.50 +
1.51 +
1.52 +template<typename AddressType, typename EntryType>
1.53 +ContainedRangeMap<AddressType, EntryType>::~ContainedRangeMap() {
1.54 + // Clear frees the children pointed to by the map, and frees the map itself.
1.55 + Clear();
1.56 +}
1.57 +
1.58 +
1.59 +template<typename AddressType, typename EntryType>
1.60 +bool ContainedRangeMap<AddressType, EntryType>::StoreRange(
1.61 + const AddressType &base, const AddressType &size, const EntryType &entry) {
1.62 + AddressType high = base + size - 1;
1.63 +
1.64 + // Check for undersize or overflow.
1.65 + if (size <= 0 || high < base) {
1.66 + //TODO(nealsid) We are commenting this out in order to prevent
1.67 + // excessive logging. We plan to move to better logging as this
1.68 + // failure happens quite often and is expected(see comment in
1.69 + // basic_source_line_resolver.cc:671).
1.70 + // BPLOG(INFO) << "StoreRange failed, " << HexString(base) << "+"
1.71 + // << HexString(size) << ", " << HexString(high);
1.72 + return false;
1.73 + }
1.74 +
1.75 + if (!map_)
1.76 + map_ = new AddressToRangeMap();
1.77 +
1.78 + MapIterator iterator_base = map_->lower_bound(base);
1.79 + MapIterator iterator_high = map_->lower_bound(high);
1.80 + MapIterator iterator_end = map_->end();
1.81 +
1.82 + if (iterator_base == iterator_high && iterator_base != iterator_end &&
1.83 + base >= iterator_base->second->base_) {
1.84 + // The new range is entirely within an existing child range.
1.85 +
1.86 + // If the new range's geometry is exactly equal to an existing child
1.87 + // range's, it violates the containment rules, and an attempt to store
1.88 + // it must fail. iterator_base->first contains the key, which was the
1.89 + // containing child's high address.
1.90 + if (iterator_base->second->base_ == base && iterator_base->first == high) {
1.91 + // TODO(nealsid): See the TODO above on why this is commented out.
1.92 +// BPLOG(INFO) << "StoreRange failed, identical range is already "
1.93 +// "present: " << HexString(base) << "+" << HexString(size);
1.94 + return false;
1.95 + }
1.96 +
1.97 + // Pass the new range on to the child to attempt to store.
1.98 + return iterator_base->second->StoreRange(base, size, entry);
1.99 + }
1.100 +
1.101 + // iterator_high might refer to an irrelevant range: one whose base address
1.102 + // is higher than the new range's high address. Set contains_high to true
1.103 + // only if iterator_high refers to a range that is at least partially
1.104 + // within the new range.
1.105 + bool contains_high = iterator_high != iterator_end &&
1.106 + high >= iterator_high->second->base_;
1.107 +
1.108 + // If the new range encompasses any existing child ranges, it must do so
1.109 + // fully. Partial containment isn't allowed.
1.110 + if ((iterator_base != iterator_end && base > iterator_base->second->base_) ||
1.111 + (contains_high && high < iterator_high->first)) {
1.112 + // TODO(mmentovai): Some symbol files will trip this check frequently
1.113 + // on STACK lines. Too many messages will be produced. These are more
1.114 + // suitable for a DEBUG channel than an INFO channel.
1.115 + // BPLOG(INFO) << "StoreRange failed, new range partially contains "
1.116 + // "existing range: " << HexString(base) << "+" <<
1.117 + // HexString(size);
1.118 + return false;
1.119 + }
1.120 +
1.121 + // When copying and erasing contained ranges, the "end" iterator needs to
1.122 + // point one past the last item of the range to copy. If contains_high is
1.123 + // false, the iterator's already in the right place; the increment is safe
1.124 + // because contains_high can't be true if iterator_high == iterator_end.
1.125 + if (contains_high)
1.126 + ++iterator_high;
1.127 +
1.128 + // Optimization: if the iterators are equal, no child ranges would be
1.129 + // moved. Create the new child range with a NULL map to conserve space
1.130 + // in leaf nodes, of which there will be many.
1.131 + AddressToRangeMap *child_map = NULL;
1.132 +
1.133 + if (iterator_base != iterator_high) {
1.134 + // The children of this range that are contained by the new range must
1.135 + // be transferred over to the new range. Create the new child range map
1.136 + // and copy the pointers to range maps it should contain into it.
1.137 + child_map = new AddressToRangeMap(iterator_base, iterator_high);
1.138 +
1.139 + // Remove the copied child pointers from this range's map of children.
1.140 + map_->erase(iterator_base, iterator_high);
1.141 + }
1.142 +
1.143 + // Store the new range in the map by its high address. Any children that
1.144 + // the new child range contains were formerly children of this range but
1.145 + // are now this range's grandchildren. Ownership of these is transferred
1.146 + // to the new child range.
1.147 + map_->insert(MapValue(high,
1.148 + new ContainedRangeMap(base, entry, child_map)));
1.149 + return true;
1.150 +}
1.151 +
1.152 +
1.153 +template<typename AddressType, typename EntryType>
1.154 +bool ContainedRangeMap<AddressType, EntryType>::RetrieveRange(
1.155 + const AddressType &address, EntryType *entry) const {
1.156 + BPLOG_IF(ERROR, !entry) << "ContainedRangeMap::RetrieveRange requires "
1.157 + "|entry|";
1.158 + assert(entry);
1.159 +
1.160 + // If nothing was ever stored, then there's nothing to retrieve.
1.161 + if (!map_)
1.162 + return false;
1.163 +
1.164 + // Get an iterator to the child range whose high address is equal to or
1.165 + // greater than the supplied address. If the supplied address is higher
1.166 + // than all of the high addresses in the range, then this range does not
1.167 + // contain a child at address, so return false. If the supplied address
1.168 + // is lower than the base address of the child range, then it is not within
1.169 + // the child range, so return false.
1.170 + MapConstIterator iterator = map_->lower_bound(address);
1.171 + if (iterator == map_->end() || address < iterator->second->base_)
1.172 + return false;
1.173 +
1.174 + // The child in iterator->second contains the specified address. Find out
1.175 + // if it has a more-specific descendant that also contains it. If it does,
1.176 + // it will set |entry| appropriately. If not, set |entry| to the child.
1.177 + if (!iterator->second->RetrieveRange(address, entry))
1.178 + *entry = iterator->second->entry_;
1.179 +
1.180 + return true;
1.181 +}
1.182 +
1.183 +
1.184 +template<typename AddressType, typename EntryType>
1.185 +void ContainedRangeMap<AddressType, EntryType>::Clear() {
1.186 + if (map_) {
1.187 + MapConstIterator end = map_->end();
1.188 + for (MapConstIterator child = map_->begin(); child != end; ++child)
1.189 + delete child->second;
1.190 +
1.191 + delete map_;
1.192 + map_ = NULL;
1.193 + }
1.194 +}
1.195 +
1.196 +
1.197 +} // namespace google_breakpad
1.198 +
1.199 +
1.200 +#endif // PROCESSOR_CONTAINED_RANGE_MAP_INL_H__
