From 240ed57ee1ac6a87b91526b8331717d494801826 Mon Sep 17 00:00:00 2001 From: Ivan Penkov Date: Sun, 5 Jun 2016 22:41:10 -0700 Subject: Adding support for overlapping ranges to RangeMap. When enabled, adding of a new range that overlaps with an existing one can be a successful operation. The range which ends at the higher address will be shrunk down by moving its start position to a higher address so that it does not overlap anymore. This change is required to fix http://crbug/611824. The actual fix will come in a separate CL. R=mmandlis@chromium.org Review URL: https://codereview.chromium.org/2029953003 . --- src/processor/basic_code_modules.cc | 19 +- src/processor/basic_code_modules.h | 9 +- src/processor/basic_source_line_resolver.cc | 17 +- src/processor/microdump.cc | 2 +- src/processor/minidump.cc | 13 +- src/processor/processor.gyp | 3 +- src/processor/range_map-inl.h | 123 +++++--- src/processor/range_map.h | 66 +++-- src/processor/range_map_shrink_down_unittest.cc | 355 ++++++++++++++++++++++++ src/processor/range_map_unittest.cc | 13 +- 10 files changed, 531 insertions(+), 89 deletions(-) create mode 100644 src/processor/range_map_shrink_down_unittest.cc (limited to 'src/processor') diff --git a/src/processor/basic_code_modules.cc b/src/processor/basic_code_modules.cc index 40b45a8b..00dc6fcb 100644 --- a/src/processor/basic_code_modules.cc +++ b/src/processor/basic_code_modules.cc @@ -46,8 +46,7 @@ namespace google_breakpad { BasicCodeModules::BasicCodeModules(const CodeModules *that) - : main_address_(0), - map_(new RangeMap >()) { + : main_address_(0), map_() { BPLOG_IF(ERROR, !that) << "BasicCodeModules::BasicCodeModules requires " "|that|"; assert(that); @@ -66,30 +65,27 @@ BasicCodeModules::BasicCodeModules(const CodeModules *that) // GetModuleAtSequence. linked_ptr module( that->GetModuleAtIndex(module_sequence)->Copy()); - if (!map_->StoreRange(module->base_address(), module->size(), module)) { + if (!map_.StoreRange(module->base_address(), module->size(), module)) { BPLOG(ERROR) << "Module " << module->code_file() << " could not be stored"; } } } -BasicCodeModules::BasicCodeModules() - : main_address_(0), - map_(new RangeMap >()) { -} +BasicCodeModules::BasicCodeModules() : main_address_(0), map_() { } BasicCodeModules::~BasicCodeModules() { - delete map_; } unsigned int BasicCodeModules::module_count() const { - return map_->GetCount(); + return map_.GetCount(); } const CodeModule* BasicCodeModules::GetModuleForAddress( uint64_t address) const { linked_ptr module; - if (!map_->RetrieveRange(address, &module, NULL, NULL)) { + if (!map_.RetrieveRange(address, &module, NULL /* base */, NULL /* delta */, + NULL /* size */)) { BPLOG(INFO) << "No module at " << HexString(address); return NULL; } @@ -104,7 +100,8 @@ const CodeModule* BasicCodeModules::GetMainModule() const { const CodeModule* BasicCodeModules::GetModuleAtSequence( unsigned int sequence) const { linked_ptr module; - if (!map_->RetrieveRangeAtIndex(sequence, &module, NULL, NULL)) { + if (!map_.RetrieveRangeAtIndex(sequence, &module, NULL /* base */, + NULL /* delta */, NULL /* size */)) { BPLOG(ERROR) << "RetrieveRangeAtIndex failed for sequence " << sequence; return NULL; } diff --git a/src/processor/basic_code_modules.h b/src/processor/basic_code_modules.h index ace569b8..97579b4d 100644 --- a/src/processor/basic_code_modules.h +++ b/src/processor/basic_code_modules.h @@ -41,13 +41,14 @@ #ifndef PROCESSOR_BASIC_CODE_MODULES_H__ #define PROCESSOR_BASIC_CODE_MODULES_H__ +#include + #include "google_breakpad/processor/code_modules.h" +#include "processor/linked_ptr.h" +#include "processor/range_map.h" namespace google_breakpad { -template class linked_ptr; -template class RangeMap; - class BasicCodeModules : public CodeModules { public: // Creates a new BasicCodeModules object given any existing CodeModules @@ -75,7 +76,7 @@ class BasicCodeModules : public CodeModules { // The map used to contain each CodeModule, keyed by each CodeModule's // address range. - RangeMap > *map_; + RangeMap > map_; private: // Disallow copy constructor and assignment operator. diff --git a/src/processor/basic_source_line_resolver.cc b/src/processor/basic_source_line_resolver.cc index 10dcb276..d0855a30 100644 --- a/src/processor/basic_source_line_resolver.cc +++ b/src/processor/basic_source_line_resolver.cc @@ -203,15 +203,16 @@ void BasicSourceLineResolver::Module::LookupAddress(StackFrame *frame) const { MemAddr function_base; MemAddr function_size; MemAddr public_address; - if (functions_.RetrieveNearestRange(address, &func, - &function_base, &function_size) && + if (functions_.RetrieveNearestRange(address, &func, &function_base, + NULL /* delta */, &function_size) && address >= function_base && address - function_base < function_size) { frame->function_name = func->name; frame->function_base = frame->module->base_address() + function_base; linked_ptr line; MemAddr line_base; - if (func->lines.RetrieveRange(address, &line, &line_base, NULL)) { + if (func->lines.RetrieveRange(address, &line, &line_base, NULL /* delta */, + NULL /* size */)) { FileMap::const_iterator it = files_.find(line->source_file_id); if (it != files_.end()) { frame->source_file_name = files_.find(line->source_file_id)->second; @@ -256,8 +257,8 @@ WindowsFrameInfo *BasicSourceLineResolver::Module::FindWindowsFrameInfo( // comparison in an overflow-friendly way. linked_ptr function; MemAddr function_base, function_size; - if (functions_.RetrieveNearestRange(address, &function, - &function_base, &function_size) && + if (functions_.RetrieveNearestRange(address, &function, &function_base, + NULL /* delta */, &function_size) && address >= function_base && address - function_base < function_size) { result->parameter_size = function->parameter_size; result->valid |= WindowsFrameInfo::VALID_PARAMETER_SIZE; @@ -286,8 +287,8 @@ CFIFrameInfo *BasicSourceLineResolver::Module::FindCFIFrameInfo( // provides an initial set of register recovery rules. Then, walk // forward from the initial rule's starting address to frame's // instruction address, applying delta rules. - if (!cfi_initial_rules_.RetrieveRange(address, &initial_rules, - &initial_base, &initial_size)) { + if (!cfi_initial_rules_.RetrieveRange(address, &initial_rules, &initial_base, + NULL /* delta */, &initial_size)) { return NULL; } @@ -595,7 +596,7 @@ bool SymbolParseHelper::ParsePublicSymbol(char *public_line, *stack_param_size < 0) { return false; } - *name = tokens[2]; + *name = tokens[2]; return true; } diff --git a/src/processor/microdump.cc b/src/processor/microdump.cc index 45bc8784..9073fe10 100644 --- a/src/processor/microdump.cc +++ b/src/processor/microdump.cc @@ -104,7 +104,7 @@ namespace google_breakpad { void MicrodumpModules::Add(const CodeModule* module) { linked_ptr module_ptr(module); - if (!map_->StoreRange(module->base_address(), module->size(), module_ptr)) { + if (!map_.StoreRange(module->base_address(), module->size(), module_ptr)) { BPLOG(ERROR) << "Module " << module->code_file() << " could not be stored"; } diff --git a/src/processor/minidump.cc b/src/processor/minidump.cc index 84f013d0..81c3d11a 100644 --- a/src/processor/minidump.cc +++ b/src/processor/minidump.cc @@ -2672,7 +2672,8 @@ const MinidumpModule* MinidumpModuleList::GetModuleForAddress( } unsigned int module_index; - if (!range_map_->RetrieveRange(address, &module_index, NULL, NULL)) { + if (!range_map_->RetrieveRange(address, &module_index, NULL /* base */, + NULL /* delta */, NULL /* size */)) { BPLOG(INFO) << "MinidumpModuleList has no module at " << HexString(address); return NULL; @@ -2708,7 +2709,9 @@ const MinidumpModule* MinidumpModuleList::GetModuleAtSequence( } unsigned int module_index; - if (!range_map_->RetrieveRangeAtIndex(sequence, &module_index, NULL, NULL)) { + if (!range_map_->RetrieveRangeAtIndex(sequence, &module_index, + NULL /* base */, NULL /* delta */, + NULL /* size */)) { BPLOG(ERROR) << "MinidumpModuleList has no module at sequence " << sequence; return NULL; } @@ -2923,7 +2926,8 @@ MinidumpMemoryRegion* MinidumpMemoryList::GetMemoryRegionForAddress( } unsigned int region_index; - if (!range_map_->RetrieveRange(address, ®ion_index, NULL, NULL)) { + if (!range_map_->RetrieveRange(address, ®ion_index, NULL /* base */, + NULL /* delta */, NULL /* size */)) { BPLOG(INFO) << "MinidumpMemoryList has no memory region at " << HexString(address); return NULL; @@ -4027,7 +4031,8 @@ const MinidumpMemoryInfo* MinidumpMemoryInfoList::GetMemoryInfoForAddress( } unsigned int info_index; - if (!range_map_->RetrieveRange(address, &info_index, NULL, NULL)) { + if (!range_map_->RetrieveRange(address, &info_index, NULL /* base */, + NULL /* delta */, NULL /* size */)) { BPLOG(INFO) << "MinidumpMemoryInfoList has no memory info at " << HexString(address); return NULL; diff --git a/src/processor/processor.gyp b/src/processor/processor.gyp index 3ef23d51..083a3237 100644 --- a/src/processor/processor.gyp +++ b/src/processor/processor.gyp @@ -77,7 +77,7 @@ 'pathname_stripper.h', 'postfix_evaluator-inl.h', 'postfix_evaluator.h', - 'proc_maps_linux.cc', + 'proc_maps_linux.cc', 'process_state.cc', 'range_map-inl.h', 'range_map.h', @@ -154,6 +154,7 @@ 'minidump_unittest.cc', 'pathname_stripper_unittest.cc', 'postfix_evaluator_unittest.cc', + 'range_map_shrink_down_unittest.cc', 'range_map_unittest.cc', 'stackwalker_address_list_unittest.cc', 'stackwalker_amd64_unittest.cc', diff --git a/src/processor/range_map-inl.h b/src/processor/range_map-inl.h index 25604080..082733e1 100644 --- a/src/processor/range_map-inl.h +++ b/src/processor/range_map-inl.h @@ -40,16 +40,29 @@ #include #include "processor/range_map.h" +#include "processor/linked_ptr.h" #include "processor/logging.h" namespace google_breakpad { +template +void RangeMap::SetEnableShrinkDown( + bool enable_shrink_down) { + enable_shrink_down_ = enable_shrink_down; +} template bool RangeMap::StoreRange(const AddressType &base, const AddressType &size, const EntryType &entry) { + return StoreRangeInternal(base, 0 /* delta */, size, entry); +} + +template +bool RangeMap::StoreRangeInternal( + const AddressType &base, const AddressType &delta, + const AddressType &size, const EntryType &entry) { AddressType high = base + (size - 1); // Check for undersize or overflow. @@ -57,9 +70,10 @@ bool RangeMap::StoreRange(const AddressType &base, // The processor will hit this case too frequently with common symbol // files in the size == 0 case, which is more suited to a DEBUG channel. // Filter those out since there's no DEBUG channel at the moment. - BPLOG_IF(INFO, size != 0) << "StoreRange failed, " << HexString(base) << - "+" << HexString(size) << ", " << - HexString(high); + BPLOG_IF(INFO, size != 0) << "StoreRangeInternal failed, " + << HexString(base) << "+" << HexString(size) + << ", " << HexString(high) + << ", delta: " << HexString(delta); return false; } @@ -71,53 +85,80 @@ bool RangeMap::StoreRange(const AddressType &base, if (iterator_base != iterator_high) { // Some other range begins in the space used by this range. It may be // contained within the space used by this range, or it may extend lower. - // Regardless, it is an error. - // The processor hits this case too frequently with common symbol files. - // This is most appropriate for a DEBUG channel, but since none exists now - // simply comment out this logging. - // - // AddressType other_base = iterator_base->second.base(); - // AddressType other_size = iterator_base->first - other_base + 1; - // BPLOG(INFO) << "StoreRange failed, an existing range is contained by or " - // "extends lower than the new range: new " << - // HexString(base) << "+" << HexString(size) << - // ", existing " << HexString(other_base) << "+" << - // HexString(other_size); - - return false; + // If enable_shrink_down_ is true, shrink the current range down, otherwise + // this is an error. + if (enable_shrink_down_) { + AddressType additional_delta = iterator_base->first - base + 1; + return StoreRangeInternal(base + additional_delta, + delta + additional_delta, + size - additional_delta, entry); + } else { + // The processor hits this case too frequently with common symbol files. + // This is most appropriate for a DEBUG channel, but since none exists + // now simply comment out this logging. + // AddressType other_base = iterator_base->second.base(); + // AddressType other_size = iterator_base->first - other_base + 1; + // BPLOG(INFO) << "StoreRangeInternal failed, an existing range is " + // << "overlapping with the new range: new " + // << HexString(base) << "+" << HexString(size) + // << ", existing " << HexString(other_base) << "+" + // << HexString(other_size); + return false; + } } if (iterator_high != map_.end()) { if (iterator_high->second.base() <= high) { // The range above this one overlaps with this one. It may fully // contain this range, or it may begin within this range and extend - // higher. Regardless, it's an error. - // The processor hits this case too frequently with common symbol files. - // This is most appropriate for a DEBUG channel, but since none exists now - // simply comment out this logging. - // - // AddressType other_base = iterator_high->second.base(); - // AddressType other_size = iterator_high->first - other_base + 1; - // BPLOG(INFO) << "StoreRange failed, an existing range contains or " - // "extends higher than the new range: new " << - // HexString(base) << "+" << HexString(size) << - // ", existing " << HexString(other_base) << "+" << - // HexString(other_size); - return false; + // higher. If enable_shrink_down_ is true, shrink the other range down, + // otherwise this is an error. + if (enable_shrink_down_ && iterator_high->first > high) { + // Shrink the other range down. + AddressType other_high = iterator_high->first; + AddressType additional_delta = + high - iterator_high->second.base() + 1; + EntryType other_entry; + AddressType other_base = AddressType(); + AddressType other_size = AddressType(); + AddressType other_delta = AddressType(); + RetrieveRange(other_high, &other_entry, &other_base, &other_delta, + &other_size); + map_.erase(iterator_high); + map_.insert(MapValue(other_high, + Range(other_base + additional_delta, + other_delta + additional_delta, + other_entry))); + // Retry to store this range. + return StoreRangeInternal(base, delta, size, entry); + } else { + // The processor hits this case too frequently with common symbol files. + // This is most appropriate for a DEBUG channel, but since none exists + // now simply comment out this logging. + // + // AddressType other_base = iterator_high->second.base(); + // AddressType other_size = iterator_high->first - other_base + 1; + // BPLOG(INFO) << "StoreRangeInternal failed, an existing range " + // << "contains or extends higher than the new range: new " + // << HexString(base) << "+" << HexString(size) + // << ", existing " << HexString(other_base) << "+" + // << HexString(other_size); + return false; + } } } // Store the range in the map by its high address, so that lower_bound can // be used to quickly locate a range by address. - map_.insert(MapValue(high, Range(base, entry))); + map_.insert(MapValue(high, Range(base, delta, entry))); return true; } template bool RangeMap::RetrieveRange( - const AddressType &address, EntryType *entry, - AddressType *entry_base, AddressType *entry_size) const { + const AddressType &address, EntryType *entry, AddressType *entry_base, + AddressType *entry_delta, AddressType *entry_size) const { BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRange requires |entry|"; assert(entry); @@ -136,6 +177,8 @@ bool RangeMap::RetrieveRange( *entry = iterator->second.entry(); if (entry_base) *entry_base = iterator->second.base(); + if (entry_delta) + *entry_delta = iterator->second.delta(); if (entry_size) *entry_size = iterator->first - iterator->second.base() + 1; @@ -145,13 +188,13 @@ bool RangeMap::RetrieveRange( template bool RangeMap::RetrieveNearestRange( - const AddressType &address, EntryType *entry, - AddressType *entry_base, AddressType *entry_size) const { + const AddressType &address, EntryType *entry, AddressType *entry_base, + AddressType *entry_delta, AddressType *entry_size) const { BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveNearestRange requires |entry|"; assert(entry); // If address is within a range, RetrieveRange can handle it. - if (RetrieveRange(address, entry, entry_base, entry_size)) + if (RetrieveRange(address, entry, entry_base, entry_delta, entry_size)) return true; // upper_bound gives the first element whose key is greater than address, @@ -167,6 +210,8 @@ bool RangeMap::RetrieveNearestRange( *entry = iterator->second.entry(); if (entry_base) *entry_base = iterator->second.base(); + if (entry_delta) + *entry_delta = iterator->second.delta(); if (entry_size) *entry_size = iterator->first - iterator->second.base() + 1; @@ -176,8 +221,8 @@ bool RangeMap::RetrieveNearestRange( template bool RangeMap::RetrieveRangeAtIndex( - int index, EntryType *entry, - AddressType *entry_base, AddressType *entry_size) const { + int index, EntryType *entry, AddressType *entry_base, + AddressType *entry_delta, AddressType *entry_size) const { BPLOG_IF(ERROR, !entry) << "RangeMap::RetrieveRangeAtIndex requires |entry|"; assert(entry); @@ -195,6 +240,8 @@ bool RangeMap::RetrieveRangeAtIndex( *entry = iterator->second.entry(); if (entry_base) *entry_base = iterator->second.base(); + if (entry_delta) + *entry_delta = iterator->second.delta(); if (entry_size) *entry_size = iterator->first - iterator->second.base() + 1; diff --git a/src/processor/range_map.h b/src/processor/range_map.h index 2572e492..985d992f 100644 --- a/src/processor/range_map.h +++ b/src/processor/range_map.h @@ -52,40 +52,55 @@ template class RangeMapSerializer; template class RangeMap { public: - RangeMap() : map_() {} + RangeMap() : enable_shrink_down_(false), map_() {} + + // |enable_shrink_down| tells whether overlapping ranges can be shrunk down. + // If true, then adding a new range that overlaps with an existing one can + // be a successful operation. The range which ends at the higher address + // will be shrunk down by moving its start position to a higher address so + // that it does not overlap anymore. + void SetEnableShrinkDown(bool enable_shrink_down); // Inserts a range into the map. Returns false for a parameter error, // or if the location of the range would conflict with a range already - // stored in the map. - bool StoreRange(const AddressType &base, - const AddressType &size, + // stored in the map. If enable_shrink_down is true and there is an overlap + // between the current range and some other range (already in the map), + // shrink down the range which ends at a higher address. + bool StoreRange(const AddressType &base, const AddressType &size, const EntryType &entry); - // Locates the range encompassing the supplied address. If there is - // no such range, returns false. entry_base and entry_size, if non-NULL, - // are set to the base and size of the entry's range. + // Locates the range encompassing the supplied address. If there is no such + // range, returns false. entry_base, entry_delta, and entry_size, if + // non-NULL, are set to the base, delta, and size of the entry's range. + // A positive entry delta (> 0) indicates that there was an overlap and the + // entry was shrunk down (original start address was increased by delta). bool RetrieveRange(const AddressType &address, EntryType *entry, - AddressType *entry_base, AddressType *entry_size) const; + AddressType *entry_base, AddressType *entry_delta, + AddressType *entry_size) const; // Locates the range encompassing the supplied address, if one exists. // If no range encompasses the supplied address, locates the nearest range // to the supplied address that is lower than the address. Returns false - // if no range meets these criteria. entry_base and entry_size, if - // non-NULL, are set to the base and size of the entry's range. + // if no range meets these criteria. entry_base, entry_delta, and entry_size, + // if non-NULL, are set to the base, delta, and size of the entry's range. + // A positive entry delta (> 0) indicates that there was an overlap and the + // entry was shrunk down (original start address was increased by delta). bool RetrieveNearestRange(const AddressType &address, EntryType *entry, - AddressType *entry_base, AddressType *entry_size) - const; + AddressType *entry_base, AddressType *entry_delta, + AddressType *entry_size) const; // Treating all ranges as a list ordered by the address spaces that they // occupy, locates the range at the index specified by index. Returns - // false if index is larger than the number of ranges stored. entry_base - // and entry_size, if non-NULL, are set to the base and size of the entry's - // range. + // false if index is larger than the number of ranges stored. entry_base, + // entry_delta, and entry_size, if non-NULL, are set to the base, delta, and + // size of the entry's range. + // A positive entry delta (> 0) indicates that there was an overlap and the + // entry was shrunk down (original start address was increased by delta). // // RetrieveRangeAtIndex is not optimized for speedy operation. bool RetrieveRangeAtIndex(int index, EntryType *entry, - AddressType *entry_base, AddressType *entry_size) - const; + AddressType *entry_base, AddressType *entry_delta, + AddressType *entry_size) const; // Returns the number of ranges stored in the RangeMap. int GetCount() const; @@ -99,12 +114,19 @@ class RangeMap { friend class ModuleComparer; friend class RangeMapSerializer; + // Same a StoreRange() with the only exception that the |delta| can be + // passed in. + bool StoreRangeInternal(const AddressType &base, const AddressType &delta, + const AddressType &size, const EntryType &entry); + class Range { public: - Range(const AddressType &base, const EntryType &entry) - : base_(base), entry_(entry) {} + Range(const AddressType &base, const AddressType &delta, + const EntryType &entry) + : base_(base), delta_(delta), entry_(entry) {} AddressType base() const { return base_; } + AddressType delta() const { return delta_; } EntryType entry() const { return entry_; } private: @@ -112,6 +134,9 @@ class RangeMap { // be stored, because RangeMap uses it as the key to the map. const AddressType base_; + // The delta when the range is shrunk down. + const AddressType delta_; + // The entry corresponding to a range. const EntryType entry_; }; @@ -121,6 +146,9 @@ class RangeMap { typedef typename AddressToRangeMap::const_iterator MapConstIterator; typedef typename AddressToRangeMap::value_type MapValue; + // Whether overlapping ranges can be shrunk down. + bool enable_shrink_down_; + // Maps the high address of each range to a EntryType. AddressToRangeMap map_; }; diff --git a/src/processor/range_map_shrink_down_unittest.cc b/src/processor/range_map_shrink_down_unittest.cc new file mode 100644 index 00000000..8dd0e709 --- /dev/null +++ b/src/processor/range_map_shrink_down_unittest.cc @@ -0,0 +1,355 @@ +// Copyright (c) 2016, Google Inc. +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE + +// range_map_shrink_down_unittest.cc: Unit tests for RangeMap that specifically +// test shrink down when ranges overlap. +// +// Author: Ivan Penkov + +#include +#include + +#include "processor/range_map-inl.h" + +#include "breakpad_googletest_includes.h" +#include "common/scoped_ptr.h" +#include "processor/linked_ptr.h" +#include "processor/logging.h" + +namespace { + +using google_breakpad::linked_ptr; +using google_breakpad::scoped_ptr; +using google_breakpad::RangeMap; + +// A CountedObject holds an int. A global (not thread safe!) count of +// allocated CountedObjects is maintained to help test memory management. +class CountedObject { + public: + explicit CountedObject(int id) : id_(id) { ++count_; } + ~CountedObject() { --count_; } + + static int count() { return count_; } + int id() const { return id_; } + + private: + static int count_; + int id_; +}; + +int CountedObject::count_; + +typedef int AddressType; +typedef RangeMap> TestMap; + +// Same range cannot be stored wice. +TEST(RangeMap, TestShinkDown_SameRange) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, + object_1)); + + // Same range cannot be stored wice. + linked_ptr object_2(new CountedObject(2)); + EXPECT_FALSE(range_map.StoreRange(0 /* base address */, 100 /* size */, + object_2)); +} + +// If a range is completely contained by another range, then the larger range +// should be shrinked down. +TEST(RangeMap, TestShinkDown_CompletelyContained) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + // Larger range is added first. + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, + object_1)); + // Smaller (contained) range is added second. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */, + object_2)); + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The first range contains the second, so the first range should have been + // shrunk to [90, 99]. Range [0, 9] should be free. + EXPECT_FALSE(range_map.RetrieveRange(0, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_FALSE(range_map.RetrieveRange(9, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_TRUE(range_map.RetrieveRange(90, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(90, retrieved_base); + EXPECT_EQ(90, retrieved_delta); + EXPECT_EQ(10, retrieved_size); + // Validate the properties of the smaller range (should be untouched). + EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(10, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(80, retrieved_size); +} + +// Same as the previous test, however the larger range is added second. +TEST(RangeMap, TestShinkDown_CompletelyContained_LargerAddedSecond) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + // Smaller (contained) range is added first. + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */, + object_1)); + // Larger range is added second. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, + object_2)); + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The second range contains the first, so the second range should have been + // shrunk to [90, 99]. Range [0, 9] should be free. + EXPECT_FALSE(range_map.RetrieveRange(0, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_FALSE(range_map.RetrieveRange(9, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_TRUE(range_map.RetrieveRange(90, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(90, retrieved_base); + EXPECT_EQ(90, retrieved_delta); + EXPECT_EQ(10, retrieved_size); + // Validate the properties of the smaller range (should be untouched). + EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(10, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(80, retrieved_size); +} + +TEST(RangeMap, TestShinkDown_PartialOverlap_AtBeginning) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, + object_1)); + + // Partial overlap at the beginning of the new range. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(90 /* base address */, 110 /* size */, + object_2)); + + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The second range is supposed to be shrunk down so the following address + // should resize in the first range. + EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(0, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(100, retrieved_size); + // Validate the properties of the shrunk down range. + EXPECT_TRUE(range_map.RetrieveRange(100, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(100, retrieved_base); + EXPECT_EQ(10, retrieved_delta); + EXPECT_EQ(100, retrieved_size); +} + +TEST(RangeMap, TestShinkDown_PartialOverlap_AtEnd) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 50 /* size */, + object_1)); + + // Partial overlap at the end of the new range. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 70 /* size */, + object_2)); + + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The first range is supposed to be shrunk down so the following address + // should resize in the first range. + EXPECT_TRUE(range_map.RetrieveRange(69, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(0, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(70, retrieved_size); + // Validate the properties of the shrunk down range. + EXPECT_TRUE(range_map.RetrieveRange(70, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(70, retrieved_base); + EXPECT_EQ(20, retrieved_delta); + EXPECT_EQ(30, retrieved_size); +} + +// A new range is overlapped at both ends. The new range and the range +// that overlaps at the end should be shrink. The range that overlaps at the +// beginning should be left untouched. +TEST(RangeMap, TestShinkDown_OverlapAtBothEnds) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + // This should overlap object_3 at the beginning. + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, + object_1)); + + // This should overlap object_3 at the end. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(100 /* base address */, 100 /* size */, + object_2)); + + // This should be overlapped on both ends by object_1 and object_2. + linked_ptr object_3(new CountedObject(3)); + EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 100 /* size */, + object_3)); + + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The first range should be intact. + EXPECT_TRUE(range_map.RetrieveRange(0, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(0, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(100, retrieved_size); + // The second range should be shrunk down by 50. + EXPECT_TRUE(range_map.RetrieveRange(150, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(150, retrieved_base); + EXPECT_EQ(50, retrieved_delta); + EXPECT_EQ(50, retrieved_size); + // The third range (in the middle) should be shrunk down by 50. + EXPECT_TRUE(range_map.RetrieveRange(100, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(3, object->id()); + EXPECT_EQ(100, retrieved_base); + EXPECT_EQ(50, retrieved_delta); + EXPECT_EQ(50, retrieved_size); +} + +TEST(RangeMap, TestShinkDown_MultipleConflicts) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + // This should overlap with object_3. + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 90 /* size */, + object_1)); + + // This should also overlap with object_3 but after object_1. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(100 /* base address */, 100 /* size */, + object_2)); + + // This should be overlapped on both object_1 and object_2. Since + // object_3 ends with the higher address it must be shrunk. + linked_ptr object_3(new CountedObject(3)); + EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 300 /* size */, + object_3)); + + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The first range should be intact. + EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(10, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(90, retrieved_size); + // The second range should be intact. + EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(100, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(100, retrieved_size); + // The third range should be shrunk down by 200. + EXPECT_TRUE(range_map.RetrieveRange(299, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(3, object->id()); + EXPECT_EQ(200, retrieved_base); + EXPECT_EQ(200, retrieved_delta); + EXPECT_EQ(100, retrieved_size); +} + +// Adding two ranges without overlap should succeed and the ranges should +// be left intact. +TEST(RangeMap, TestShinkDown_NoConflicts) { + TestMap range_map; + range_map.SetEnableShrinkDown(true); + // Adding range 1. + linked_ptr object_1(new CountedObject(1)); + EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 90 /* size */, + object_1)); + + // Adding range 2 - no overlap with range 1. + linked_ptr object_2(new CountedObject(2)); + EXPECT_TRUE(range_map.StoreRange(110 /* base address */, 90 /* size */, + object_2)); + + linked_ptr object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_delta = AddressType(); + AddressType retrieved_size = AddressType(); + // The first range should be intact. + EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(1, object->id()); + EXPECT_EQ(10, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(90, retrieved_size); + // The second range should be intact. + EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base, + &retrieved_delta, &retrieved_size)); + EXPECT_EQ(2, object->id()); + EXPECT_EQ(110, retrieved_base); + EXPECT_EQ(0, retrieved_delta); + EXPECT_EQ(90, retrieved_size); +} + +} // namespace diff --git a/src/processor/range_map_unittest.cc b/src/processor/range_map_unittest.cc index bf9b7279..31b89e5d 100644 --- a/src/processor/range_map_unittest.cc +++ b/src/processor/range_map_unittest.cc @@ -166,8 +166,10 @@ static bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) { linked_ptr object; AddressType retrieved_base = AddressType(); AddressType retrieved_size = AddressType(); + AddressType retrieved_delta = AddressType(); bool retrieved = range_map->RetrieveRange(address, &object, &retrieved_base, + &retrieved_delta, &retrieved_size); bool observed_result = retrieved && object->id() == range_test->id; @@ -209,10 +211,12 @@ static bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) { linked_ptr nearest_object; AddressType nearest_base = AddressType(); + AddressType nearest_delta = AddressType(); AddressType nearest_size = AddressType(); bool retrieved_nearest = range_map->RetrieveNearestRange(address, &nearest_object, &nearest_base, + &nearest_delta, &nearest_size); // When checking one greater than the high side, RetrieveNearestRange @@ -274,7 +278,8 @@ static bool RetrieveIndexTest(TestMap *range_map, int set) { int object_count = range_map->GetCount(); for (int object_index = 0; object_index < object_count; ++object_index) { AddressType base; - if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) { + if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, + NULL /* delta */, NULL /* size */)) { fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " "expected success, observed failure\n", set, object_index); @@ -314,7 +319,8 @@ static bool RetrieveIndexTest(TestMap *range_map, int set) { // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that // are too high. - if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL, NULL)) { + if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL /* base */, + NULL /* delta */, NULL /* size */)) { fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), " "expected failure, observed success\n", set, object_count); @@ -343,7 +349,8 @@ static bool RetriveAtIndexTest2() { int object_count = range_map->GetCount(); for (int object_index = 0; object_index < object_count; ++object_index) { AddressType base; - if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) { + if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, + NULL /* delta */, NULL /* size */)) { fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, " "expected success, observed failure\n", object_index); return false; -- cgit v1.2.1