[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..9a4fe3b6916104fcf09acde7a1eaa54342033f1b 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;
   }
@@ -695,172 +716,163 @@ ProfileFunction* ProfileCode::SetFunctionAndName(ProfileFunctionTable* table) {
 }
 
 
-typedef bool (*RangeCompare)(uword pc, uword region_start, uword region_end);
-
-class ProfileCodeTable : public ZoneAllocated {
- public:
-  ProfileCodeTable() : table_(8) {}
+intptr_t ProfileCodeTable::FindCodeIndexForPC(uword pc) const {
+  intptr_t length = table_.length();
+  if (length == 0) {
+    return -1;  // Not found.
+  }
+  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;
+    }
+  }
+  return -1;
+}
 
-  intptr_t length() const { return table_.length(); }
 
-  ProfileCode* At(intptr_t index) const {
-    ASSERT(index >= 0);
-    ASSERT(index < length());
-    return table_[index];
+intptr_t ProfileCodeTable::InsertCode(ProfileCode* new_code) {
+  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 = -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 processing more samples may see
+    // more PCs we didn't previously know belonged to it.)
+    lo_code->ExpandUpper(new_code->end());
+    return lo;
+  }
+
+  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 processing more samples may see
+    // more PCs we didn't previously know belonged to it.)
+    hi_code->ExpandLower(new_code->start());
+    return hi;
+  }
+
+  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;
+}
 
-  // 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;
-    }
-    // Found at index.
-    return index;
-  }
 
-  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;
-    }
-    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);
-      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);
-      return hi;
-    }
-    UNREACHABLE();
-    return -1;
-  }
+void ProfileCodeTable::FindNeighbors(uword pc,
+                                     intptr_t* lo,
+                                     intptr_t* hi,
+                                     ProfileCode** lo_code,
+                                     ProfileCode** hi_code) const {
+  ASSERT(table_.length() >= 1);
 
- 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;
-      }
-    }
-    return first;
-  }
+  intptr_t length = table_.length();
 
-  static bool CompareUpperBound(uword pc, uword start, uword end) {
-    return pc >= end;
+  if (pc < At(0)->start()) {
+    // Lower than any existing code.
+    *lo = -1;
+    *lo_code = NULL;
+    *hi = 0;
+    *hi_code = At(*hi);
+    return;
   }
 
-  static bool CompareLowerBound(uword pc, uword start, uword end) {
-    return end <= pc;
+  if (pc >= At(length - 1)->end()) {
+    // Higher than any existing code.
+    *lo = length - 1;
+    *lo_code = At(*lo);
+    *hi = -1;
+    *hi_code = NULL;
+    return;
   }
 
-  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);
-  }
+  *lo = 0;
+  *lo_code = At(*lo);
+  *hi = length - 1;
+  *hi_code = At(*hi);
 
-  void VerifyOrder() {
-    const intptr_t length = table_.length();
-    if (length == 0) {
-      return;
+  while ((*hi - *lo) > 1) {
+    intptr_t mid = (*hi - *lo + 1) / 2 + *lo;
+    ASSERT(*lo <= mid);
+    ASSERT(*hi >= mid);
+    ProfileCode* code = At(mid);
+    if (code->end() <= pc) {
+      *lo = mid;
+      *lo_code = code;
     }
-    uword last = table_[0]->end();
-    for (intptr_t i = 1; i < length; i++) {
-      ProfileCode* a = table_[i];
-      ASSERT(last <= a->start());
-      last = a->end();
+    if (pc < code->end()) {
+      *hi = mid;
+      *hi_code = code;
     }
   }
+}
+
+
+void ProfileCodeTable::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];
+    ASSERT(last <= a->start());
+    last = a->end();
+  }
+}
 
-  void VerifyOverlap() {
-    const intptr_t length = table_.length();
-    for (intptr_t i = 0; i < length; i++) {
-      ProfileCode* a = table_[i];
-      for (intptr_t j = i + 1; j < length; j++) {
-        ProfileCode* b = table_[j];
-        ASSERT(!a->Contains(b->start()) && !a->Contains(b->end() - 1) &&
-               !b->Contains(a->start()) && !b->Contains(a->end() - 1));
-      }
+void ProfileCodeTable::VerifyOverlap() {
+  const intptr_t length = table_.length();
+  for (intptr_t i = 0; i < length; i++) {
+    ProfileCode* a = table_[i];
+    for (intptr_t j = i + 1; j < length; j++) {
+      ProfileCode* b = table_[j];
+      ASSERT(!a->Contains(b->start()) && !a->Contains(b->end() - 1) &&
+             !b->Contains(a->start()) && !b->Contains(a->end() - 1));
     }
   }
-
-  ZoneGrowableArray<ProfileCode*> table_;
-};
+}
 
 
 ProfileTrieNode::ProfileTrieNode(intptr_t table_index)
@@ -2239,6 +2251,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);