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 .

10 files changed, 531 insertions, 89 deletions

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<uint64_t, linked_ptr<const CodeModule> >()) {
+    : 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<const CodeModule> 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<uint64_t, linked_ptr<const CodeModule> >()) {
-}
+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<const CodeModule> 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<const CodeModule> 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 <stddef.h>
+
 #include "google_breakpad/processor/code_modules.h"
+#include "processor/linked_ptr.h"
+#include "processor/range_map.h"
 
 namespace google_breakpad {
 
-template<typename T> class linked_ptr;
-template<typename AddressType, typename EntryType> 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<uint64_t, linked_ptr<const CodeModule> > *map_;
+  RangeMap<uint64_t, linked_ptr<const CodeModule> > 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> 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> 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<const CodeModule> 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, &region_index, NULL, NULL)) {
+  if (!range_map_->RetrieveRange(address, &region_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 <assert.h>
 
 #include "processor/range_map.h"
+#include "processor/linked_ptr.h"
 #include "processor/logging.h"
 
 
 namespace google_breakpad {
 
+template<typename AddressType, typename EntryType>
+void RangeMap<AddressType, EntryType>::SetEnableShrinkDown(
+    bool enable_shrink_down) {
+  enable_shrink_down_ = enable_shrink_down;
+}
 
 template<typename AddressType, typename EntryType>
 bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base,
                                                   const AddressType &size,
                                                   const EntryType &entry) {
+  return StoreRangeInternal(base, 0 /* delta */, size, entry);
+}
+
+template<typename AddressType, typename EntryType>
+bool RangeMap<AddressType, EntryType>::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<AddressType, EntryType>::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<AddressType, EntryType>::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<typename AddressType, typename EntryType>
 bool RangeMap<AddressType, EntryType>::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<AddressType, EntryType>::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<AddressType, EntryType>::RetrieveRange(
 
 template<typename AddressType, typename EntryType>
 bool RangeMap<AddressType, EntryType>::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<AddressType, EntryType>::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<AddressType, EntryType>::RetrieveNearestRange(
 
 template<typename AddressType, typename EntryType>
 bool RangeMap<AddressType, EntryType>::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<AddressType, EntryType>::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, class> class RangeMapSerializer;
 template<typename AddressType, typename EntryType>
 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<AddressType, EntryType>;
 
+  // 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 <limits.h>
+#include <stdio.h>
+
+#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<AddressType, linked_ptr<CountedObject>> TestMap;
+
+// Same range cannot be stored wice.
+TEST(RangeMap, TestShinkDown_SameRange) {
+  TestMap range_map;
+  range_map.SetEnableShrinkDown(true);
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> 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<CountedObject> object_2(new CountedObject(2));
+  EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */,
+                                   object_2));
+  linked_ptr<CountedObject> 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<CountedObject> object_1(new CountedObject(1));
+  EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */,
+                                   object_1));
+  // Larger range is added second.
+  linked_ptr<CountedObject> object_2(new CountedObject(2));
+  EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */,
+                                   object_2));
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> object_2(new CountedObject(2));
+  EXPECT_TRUE(range_map.StoreRange(90 /* base address */, 110 /* size */,
+                                   object_2));
+
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> object_2(new CountedObject(2));
+  EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 70 /* size */,
+                                   object_2));
+
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> 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<CountedObject> object_3(new CountedObject(3));
+  EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 100 /* size */,
+                                   object_3));
+
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> 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<CountedObject> object_3(new CountedObject(3));
+  EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 300 /* size */,
+                                   object_3));
+
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> object_2(new CountedObject(2));
+  EXPECT_TRUE(range_map.StoreRange(110 /* base address */, 90 /* size */,
+                                   object_2));
+
+  linked_ptr<CountedObject> 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<CountedObject> 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<CountedObject> 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;