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

runtime/vm/profiler_service.cc

Index: runtime/vm/profiler_service.cc
diff --git a/runtime/vm/profiler_service.cc b/runtime/vm/profiler_service.cc
index f245ed5f29657d2f5ac8d176c217fdc1f26b4ba9..b89ca0a4549b0eab428e230965ab8c7aa3be26d9 100644
--- a/runtime/vm/profiler_service.cc
+++ b/runtime/vm/profiler_service.cc
@@ -302,10 +302,31 @@ ProfileCode::ProfileCode(Kind kind,
       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;
   }
@@ -712,18 +733,26 @@ class ProfileCodeTable : public ZoneAllocated {
   // 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;
-    }
-    const ProfileCode* code = At(index);
-    if (!code->Contains(pc)) {
-      // 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.

+    }
+    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 {
@@ -737,101 +766,111 @@ class ProfileCodeTable : public ZoneAllocated {
   // 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;
-    }
-    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);
+    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 (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;
     }
-    return first;
-  }
 
-  static bool CompareUpperBound(uword pc, uword start, uword end) {
-    return pc >= end;
-  }
+    if (pc >= At(length - 1)->end()) {
+      // Higher than any existing code.
+      *lo = length - 1;
+      *lo_code = At(*lo);
+      *hi = -1;
+      *hi_code = NULL;
+      return;
+    }
 
-  static bool CompareLowerBound(uword pc, uword start, uword end) {
-    return end <= pc;
-  }
+    *lo = 0;
+    *lo_code = At(*lo);
+    *hi = length - 1;
+    *hi_code = At(*hi);
 
-  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);
+    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;
+      }
+    }
   }
 
   void VerifyOrder() {
@@ -2239,6 +2278,24 @@ class ProfileBuilder : public ValueObject {
     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);