Adding support for overlapping ranges to RangeMap.

src/processor/range_map-inl.h

 // Copyright (c) 2010 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
@@ skipping 22 matching lines @@
 //
 // Author: Mark Mentovai
 
 #ifndef PROCESSOR_RANGE_MAP_INL_H__
 #define PROCESSOR_RANGE_MAP_INL_H__
 
 
 #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.
   if (size <= 0 || high < 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)

[mmandlis, 2016/06/02 23:50:59]

should you add the |delta| to the log as well?

[ivanpe, 2016/06/03 03:56:55]

Done.

+                              << ", " << HexString(high);
     return false;
   }
 
   // Ensure that this range does not overlap with another one already in the

[mmandlis, 2016/06/02 23:50:59]

You might want to rephrase the comment "Ensure that this range does not overlap"
- ensure doesn't sound quire right anymore.

[ivanpe, 2016/06/03 03:56:55]

By default, shrink-down is off, so in the common case this is still valid.  The
comments that follow provide more details about the cases where shrink-down is
on. 

   // map.
   MapConstIterator iterator_base = map_.lower_bound(base);
   MapConstIterator iterator_high = map_.lower_bound(high);
 
   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,

[mmandlis, 2016/06/02 23:50:59]

in the comments you explained that the address with the highest end address will
be shrunk. is it always the one that is being saved? can it be another entry
that is already in the map?

[ivanpe, 2016/06/03 03:56:55]

Yes, the one that is shrunk can already be in the map.

+                                delta + additional_delta,
+                                size - additional_delta, entry);

[mmandlis, 2016/06/02 23:50:59]

is the recursive call really necessary, or could you just use updated local
variables base, delta and size? or can there be more than one level of
recursion? if yes, can you give an example of addresses it would happen for?

thanks.

[ivanpe, 2016/06/03 03:56:55]

I feel it is cleaner and easier to understand with recursion.  You may have
multiple ranges that overlap the beginning of the new range in whcih case you
may need to shrink several times in a row until all the conflicts are resolved.

I added a test case to specifically cover this this scenario (the last test
case).

+    } else {
+      // AddressType other_base = iterator_base->second.base();

[mmandlis, 2016/06/02 23:50:59]

there was originally this comment explaining:
"
// The processor hits this case too frequently with common symbol files.	      
// this is an error.
// This is most appropriate for a DEBUG channel, but since none exists now	     
 // simply comment out this logging."

it got removed with your change. Without it, it is not clear why we are keeping
these commented-out lines.

[ivanpe, 2016/06/03 03:56:55]

Good point.  Added it back.

+      // 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);
 
   MapConstIterator iterator = map_.lower_bound(address);
   if (iterator == map_.end())
     return false;
 
   // The map is keyed by the high address of each range, so |address| is
   // guaranteed to be lower than the range's high address.  If |range| is
   // not directly preceded by another range, it's possible for address to
   // be below the range's low address, though.  When that happens, address
   // references something not within any range, so return false.
   if (address < iterator->second.base())
     return false;
 
   *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;
 
   return true;
 }
 
 
 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,
   // but we want the first element whose key is less than or equal to address.
   // Decrement the iterator to get there, but not if the upper_bound already
   // points to the beginning of the map - in that case, address is lower than
   // the lowest stored key, so return false.
   MapConstIterator iterator = map_.upper_bound(address);
   if (iterator == map_.begin())
     return false;
   --iterator;
 
   *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;
 
   return true;
 }
 
 
 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);
 
   if (index >= GetCount()) {
     BPLOG(ERROR) << "Index out of range: " << index << "/" << GetCount();
     return false;
   }
 
   // Walk through the map.  Although it's ordered, it's not a vector, so it
   // can't be addressed directly by index.
   MapConstIterator iterator = map_.begin();
   for (int this_index = 0; this_index < index; ++this_index)
     ++iterator;
 
   *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;
 
   return true;
 }
 
 
 template<typename AddressType, typename EntryType>
 int RangeMap<AddressType, EntryType>::GetCount() const {
   return map_.size();
 }
 
 
 template<typename AddressType, typename EntryType>
 void RangeMap<AddressType, EntryType>::Clear() {
   map_.clear();
 }
 
 
 }  // namespace google_breakpad
 
 
 #endif  // PROCESSOR_RANGE_MAP_INL_H__