[fuchsia] Make profile processing resilient to bogus overlaps from dladdr.

runtime/vm/profiler_service.cc

 // Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/profiler_service.h"
 
 #include "vm/growable_array.h"
 #include "vm/hash_map.h"
 #include "vm/log.h"
 #include "vm/malloc_hooks.h"
@@ skipping 284 matching lines @@
       inclusive_ticks_(0),
       inclusive_serial_(-1),
       code_(code),
       name_(NULL),
       compile_timestamp_(0),
       function_(NULL),
       code_table_index_(-1),
       address_ticks_(0) {}
 
 
-void ProfileCode::AdjustExtent(uword start, uword end) {
+void ProfileCode::TruncateLower(uword start) {
+  if (start > start_) {
+    start_ = start;
+  }
+  ASSERT(start_ < end_);
+}
+
+
+void ProfileCode::TruncateUpper(uword end) {
+  if (end < end_) {
+    end_ = end;
+  }
+  ASSERT(start_ < end_);
+}
+
+
+void ProfileCode::ExpandLower(uword start) {
   if (start < start_) {
     start_ = start;
   }
+  ASSERT(start_ < end_);
+}
+
+
+void ProfileCode::ExpandUpper(uword end) {
   if (end > end_) {
     end_ = end;
   }
   ASSERT(start_ < end_);
 }
 
 
 bool ProfileCode::Overlaps(const ProfileCode* other) const {
   ASSERT(other != NULL);
   return other->Contains(start_) || other->Contains(end_ - 1) ||
@@ skipping 371 matching lines @@
 
   function->AddProfileCode(code_table_index());
 
   function_ = function;
   return function_;
 }
 
 
 typedef bool (*RangeCompare)(uword pc, uword region_start, uword region_end);
 
 class ProfileCodeTable : public ZoneAllocated {

[zra, 2017/06/14 05:00:05]

Could you add unit tests for this class? If you move the declaration of this
class to the header file, you can add unit tests for it in profiler_test.cc.

[rmacnak, 2017/06/14 17:32:14]

Done. Adjusted neighbor test to compare end instead of start to avoid a
degenerate truncation.

  public:
   ProfileCodeTable() : table_(8) {}
 
   intptr_t length() const { return table_.length(); }
 
   ProfileCode* At(intptr_t index) const {
     ASSERT(index >= 0);
     ASSERT(index < length());
     return table_[index];
   }
 
   // Find the table index to the ProfileCode containing pc.
   // Returns < 0 if not found.
   intptr_t FindCodeIndexForPC(uword pc) const {
-    intptr_t index = FindCodeIndex(pc, &CompareLowerBound);
-    if (index == length()) {
-      // Not present.
-      return -1;
+    intptr_t length = table_.length();
+    if (length == 0) {
+      return -1;  // No found.

[zra, 2017/06/14 05:00:05]

Not

[rmacnak, 2017/06/14 17:32:14]

Done.

     }
-    const ProfileCode* code = At(index);
-    if (!code->Contains(pc)) {
-      // Not present.
-      return -1;
+    intptr_t lo = 0;
+    intptr_t hi = length - 1;
+    while (lo <= hi) {
+      intptr_t mid = (hi - lo + 1) / 2 + lo;
+      ASSERT(mid >= lo);
+      ASSERT(mid <= hi);
+      ProfileCode* code = At(mid);
+      if (code->Contains(pc)) {
+        return mid;
+      } else if (pc < code->start()) {
+        hi = mid - 1;
+      } else {
+        lo = mid + 1;
+      }
     }
-    // Found at index.
-    return index;
+    return -1;
   }
 
   ProfileCode* FindCodeForPC(uword pc) const {
     intptr_t index = FindCodeIndexForPC(pc);
     if (index < 0) {
       return NULL;
     }
     return At(index);
   }
 
   // Insert |new_code| into the table. Returns the table index where |new_code|
   // was inserted. Will merge with an overlapping ProfileCode if one is present.
   intptr_t InsertCode(ProfileCode* new_code) {
-    const uword start = new_code->start();
-    const uword end = new_code->end();
     const intptr_t length = table_.length();
     if (length == 0) {
       table_.Add(new_code);
       return length;
     }
+
     // Determine the correct place to insert or merge |new_code| into table.
-    intptr_t lo = FindCodeIndex(start, &CompareLowerBound);
-    intptr_t hi = FindCodeIndex(end - 1, &CompareUpperBound);
-    // TODO(johnmccutchan): Simplify below logic.
-    if ((lo == length) && (hi == length)) {
-      lo = length - 1;
+    intptr_t lo = -1;
+    intptr_t hi = -1;
+    ProfileCode* lo_code = NULL;
+    ProfileCode* hi_code = NULL;
+    const uword pc = new_code->end() - 1;
+    FindNeighbors(pc, &lo, &hi, &lo_code, &hi_code);
+    ASSERT((lo_code != NULL) || (hi_code != NULL));
+
+    if (lo != -1) {
+      // Has left neighbor.
+      new_code->TruncateLower(lo_code->end());
+      ASSERT(!new_code->Overlaps(lo_code));
     }
-    if (lo == length) {
-      ProfileCode* code = At(hi);
-      if (code->Overlaps(new_code)) {
-        HandleOverlap(code, new_code, start, end);
-        return hi;
-      }
-      table_.Add(new_code);
-      return length;
-    } else if (hi == length) {
-      ProfileCode* code = At(lo);
-      if (code->Overlaps(new_code)) {
-        HandleOverlap(code, new_code, start, end);
-        return lo;
-      }
-      table_.Add(new_code);
-      return length;
-    } else if (lo == hi) {
-      ProfileCode* code = At(lo);
-      if (code->Overlaps(new_code)) {
-        HandleOverlap(code, new_code, start, end);
-        return lo;
-      }
-      table_.InsertAt(lo, new_code);
+    if (hi != -1) {
+      // Has right neighbor.
+      new_code->TruncateUpper(hi_code->start());
+      ASSERT(!new_code->Overlaps(hi_code));
+    }
+
+    if ((lo != -1) && (lo_code->kind() == ProfileCode::kNativeCode) &&
+        (new_code->kind() == ProfileCode::kNativeCode) &&
+        (lo_code->end() == new_code->start())) {
+      // Adjacent left neighbor of the same kind: merge.
+      // (dladdr doesn't give us symbol size so we may new PCs we didn't

[zra, 2017/06/14 05:00:05]

may see new PCs

[rmacnak, 2017/06/14 17:32:14]

Done.

+      // previously know belonged to it.)
+      lo_code->ExpandUpper(new_code->end());
       return lo;
-    } else {
-      ProfileCode* code = At(lo);
-      if (code->Overlaps(new_code)) {
-        HandleOverlap(code, new_code, start, end);
-        return lo;
-      }
-      code = At(hi);
-      if (code->Overlaps(new_code)) {
-        HandleOverlap(code, new_code, start, end);
-        return hi;
-      }
-      table_.InsertAt(hi, new_code);
+    }
+
+    if ((hi != -1) && (hi_code->kind() == ProfileCode::kNativeCode) &&
+        (new_code->kind() == ProfileCode::kNativeCode) &&
+        (new_code->end() == hi_code->start())) {
+      // Adjacent right neighbor of the same kind: merge.
+      // (dladdr doesn't give us symbol size so we may new PCs we didn't

[zra, 2017/06/14 05:00:05]

may see new PCs

[rmacnak, 2017/06/14 17:32:14]

Done.

+      // previously know belonged to it.)
+      hi_code->ExpandLower(new_code->start());
       return hi;
     }
-    UNREACHABLE();
-    return -1;
+
+    intptr_t insert;
+    if (lo == -1) {
+      insert = 0;
+    } else if (hi == -1) {
+      insert = length;
+    } else {
+      insert = lo + 1;
+    }
+    table_.InsertAt(insert, new_code);
+    return insert;
   }
 
  private:
-  intptr_t FindCodeIndex(uword pc, RangeCompare comparator) const {
-    ASSERT(comparator != NULL);
-    intptr_t count = table_.length();
-    intptr_t first = 0;
-    while (count > 0) {
-      intptr_t it = first;
-      intptr_t step = count / 2;
-      it += step;
-      const ProfileCode* code = At(it);
-      if (comparator(pc, code->start(), code->end())) {
-        first = ++it;
-        count -= (step + 1);
-      } else {
-        count = step;
+  void FindNeighbors(uword pc,
+                     intptr_t* lo,
+                     intptr_t* hi,
+                     ProfileCode** lo_code,
+                     ProfileCode** hi_code) const {
+    ASSERT(table_.length() >= 1);
+
+    intptr_t length = table_.length();
+
+    if (pc < At(0)->start()) {
+      // Lower than any existing code.
+      *lo = -1;
+      *lo_code = NULL;
+      *hi = 0;
+      *hi_code = At(*hi);
+      return;
+    }
+
+    if (pc >= At(length - 1)->end()) {
+      // Higher than any existing code.
+      *lo = length - 1;
+      *lo_code = At(*lo);
+      *hi = -1;
+      *hi_code = NULL;
+      return;
+    }
+
+    *lo = 0;
+    *lo_code = At(*lo);
+    *hi = length - 1;
+    *hi_code = At(*hi);
+
+    while ((*hi - *lo) > 1) {
+      intptr_t mid = (*hi - *lo + 1) / 2 + *lo;
+      ASSERT(*lo <= mid);
+      ASSERT(*hi >= mid);
+      ProfileCode* code = At(mid);
+      if (code->start() <= pc) {
+        *lo = mid;
+        *lo_code = code;
+      }
+      if (pc < code->end()) {
+        *hi = mid;
+        *hi_code = code;
       }
     }
-    return first;
-  }
-
-  static bool CompareUpperBound(uword pc, uword start, uword end) {
-    return pc >= end;
-  }
-
-  static bool CompareLowerBound(uword pc, uword start, uword end) {
-    return end <= pc;
-  }
-
-  void HandleOverlap(ProfileCode* existing,
-                     ProfileCode* code,
-                     uword start,
-                     uword end) {
-    // We should never see overlapping Dart code regions.
-    ASSERT(existing->kind() != ProfileCode::kDartCode);
-    // We should never see overlapping Tag code regions.
-    ASSERT(existing->kind() != ProfileCode::kTagCode);
-    // When code regions overlap, they should be of the same kind.
-    ASSERT(existing->kind() == code->kind());
-    existing->AdjustExtent(start, end);
   }
 
   void VerifyOrder() {
     const intptr_t length = table_.length();
     if (length == 0) {
       return;
     }
     uword last = table_[0]->end();
     for (intptr_t i = 1; i < length; i++) {
       ProfileCode* a = table_[i];
@@ skipping 1387 matching lines @@
       // Failed to find a native symbol for pc.
       native_start = pc;
     }
 
 #if defined(HOST_ARCH_ARM)
     // The symbol for a Thumb function will be xxx1, but we may have samples
     // at function entry which will have pc xxx0.
     native_start &= ~1;
 #endif
 
+    if (native_start > pc) {
+      // Bogus lookup result.
+      if (native_name != NULL) {
+        NativeSymbolResolver::FreeSymbolName(native_name);
+        native_name = NULL;
+      }
+      native_start = pc;
+    }
+    if ((pc - native_start) > (32 * KB)) {
+      // Suspect lookup result. More likely dladdr going off the rails than a
+      // jumbo function.
+      if (native_name != NULL) {
+        NativeSymbolResolver::FreeSymbolName(native_name);
+        native_name = NULL;
+      }
+      native_start = pc;
+    }
+
     ASSERT(pc >= native_start);
     profile_code = new ProfileCode(ProfileCode::kNativeCode, native_start,
                                    pc + 1, 0, code);
     if (native_name != NULL) {
       profile_code->SetName(native_name);
       NativeSymbolResolver::FreeSymbolName(native_name);
     }
 
     RegisterLiveProfileCode(profile_code);
     return profile_code;
@@ skipping 596 matching lines @@
   // Disable thread interrupts while processing the buffer.
   DisableThreadInterruptsScope dtis(thread);
 
   ClearProfileVisitor clear_profile(isolate);
   sample_buffer->VisitSamples(&clear_profile);
 }
 
 #endif  // !PRODUCT
 
 }  // namespace dart