Add Dart stack walker

runtime/vm/profiler.cc

 // Copyright (c) 2013, 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 "platform/utils.h"
 
 #include "vm/allocation.h"
 #include "vm/atomic.h"
 #include "vm/code_patcher.h"
 #include "vm/isolate.h"
@@ skipping 1666 matching lines @@
     if ((sample->fp() & kPageMask) == 0) {
       return;
     }
 #endif
     const uword pc_marker = *(fp + kPcMarkerSlotFromFp);
     sample->set_pc_marker(pc_marker);
   }
 }
 
 
-class ProfilerDartStackWalker : public ValueObject {
+// Given an exit frame, walk the Dart stack.
+class ProfilerDartExitStackWalker : public ValueObject {
  public:
-  ProfilerDartStackWalker(Isolate* isolate, Sample* sample)
+  ProfilerDartExitStackWalker(Isolate* isolate, Sample* sample)
       : sample_(sample),
         frame_iterator_(isolate) {
     ASSERT(sample_ != NULL);
   }
 
-  ProfilerDartStackWalker(Isolate* isolate, Sample* sample, uword fp)
-      : sample_(sample),
-        frame_iterator_(fp, isolate) {
-    ASSERT(sample_ != NULL);
-  }
-
-  int walk() {
+  void walk() {
     intptr_t frame_index = 0;
     StackFrame* frame = frame_iterator_.NextFrame();
     while (frame != NULL) {
       sample_->SetAt(frame_index, frame->pc());
       frame_index++;
       if (frame_index >= FLAG_profile_depth) {
         break;
       }
       frame = frame_iterator_.NextFrame();
     }
-    return frame_index;
   }
 
  private:
   Sample* sample_;
   DartFrameIterator frame_iterator_;
 };
 
 
-// Notes on stack frame walking:
-//
-// The sampling profiler will collect up to Sample::kNumStackFrames stack frames
-// The stack frame walking code uses the frame pointer to traverse the stack.
+// Executing Dart code, walk the stack.
+class ProfilerDartStackWalker : public ValueObject {
+ public:
+  ProfilerDartStackWalker(Isolate* isolate,
+                          Sample* sample,
+                          uword stack_lower,
+                          uword stack_upper,
+                          uword pc,
+                          uword fp,
+                          uword sp)
+      : isolate_(isolate),
+        sample_(sample),
+        stack_upper_(stack_upper),
+        stack_lower_(stack_lower) {
+    ASSERT(sample_ != NULL);
+    pc_ = reinterpret_cast<uword*>(pc);
+    fp_ = reinterpret_cast<uword*>(fp);
+    sp_ = reinterpret_cast<uword*>(sp);
+  }
+
+  void walk() {
+    if (!ValidFramePointer()) {
+      sample_->set_ignore_sample(true);
+      return;
+    }
+    ASSERT(ValidFramePointer());
+    uword return_pc = InitialReturnAddress();
+    if (StubCode::InInvocationStubForIsolate(isolate_, return_pc)) {
+      // Edge case- we have called out from the Invocation Stub but have not
+      // created the stack frame of the callee. Attempt to locate the exit
+      // frame before walking the stack.
+      if (!NextExit() || !ValidFramePointer()) {
+        // Nothing to sample.
+        sample_->set_ignore_sample(true);
+        return;
+      }
+    }
+    for (int i = 0; i < FLAG_profile_depth; i++) {
+      sample_->SetAt(i, reinterpret_cast<uword>(pc_));
+      if (!Next()) {
+        return;
+      }
+    }
+  }
+
+ private:
+  bool Next() {
+    if (!ValidFramePointer()) {
+      return false;
+    }
+    if (StubCode::InInvocationStubForIsolate(isolate_,
+                                             reinterpret_cast<uword>(pc_))) {
+      // In invocation stub.
+      return NextExit();
+    }
+    // In regular Dart frame.
+    uword* new_pc = CallerPC();
+    // Check if we've moved into the invocation stub.
+    if (StubCode::InInvocationStubForIsolate(isolate_,
+                                             reinterpret_cast<uword>(new_pc))) {
+      // New PC is inside invocation stub, skip.
+      return NextExit();
+    }
+    uword* new_fp = CallerFP();
+    if (new_fp <= fp_) {
+      // FP didn't move to a higher address.
+      return false;
+    }
+    // Success, update fp and pc.
+    fp_ = new_fp;
+    pc_ = new_pc;
+    return true;
+  }
+
+  bool NextExit() {
+    if (!ValidFramePointer()) {
+      return false;
+    }
+    uword* new_fp = ExitLink();
+    if (new_fp == NULL) {
+      // No exit link.
+      return false;
+    }
+    if (new_fp <= fp_) {
+      // FP didn't move to a higher address.
+      return false;
+    }
+    if (!ValidFramePointer(new_fp)) {
+      return false;
+    }
+    // Success, update fp and pc.
+    fp_ = new_fp;
+    pc_ = CallerPC();
+    return true;
+  }
+
+  uword InitialReturnAddress() const {
+    ASSERT(sp_ != NULL);
+    return *(sp_);
+  }
+
+  uword* CallerPC() const {
+    ASSERT(fp_ != NULL);
+    return reinterpret_cast<uword*>(*(fp_ + kSavedCallerPcSlotFromFp));
+  }
+
+  uword* CallerFP() const {
+    ASSERT(fp_ != NULL);
+    return reinterpret_cast<uword*>(*(fp_ + kSavedCallerFpSlotFromFp));
+  }
+
+  uword* ExitLink() const {
+    ASSERT(fp_ != NULL);
+    return reinterpret_cast<uword*>(*(fp_ + kExitLinkSlotFromEntryFp));
+  }
+
+  bool ValidFramePointer() const {
+    return ValidFramePointer(fp_);
+  }
+
+  bool ValidFramePointer(uword* fp) const {
+    if (fp == NULL) {
+      return false;
+    }
+    uword cursor = reinterpret_cast<uword>(fp);
+    cursor += sizeof(fp);
+    return (cursor >= stack_lower_) && (cursor < stack_upper_);
+  }
+
+  uword* pc_;
+  uword* fp_;
+  uword* sp_;
+  Isolate* isolate_;
+  Sample* sample_;
+  const uword stack_upper_;
+  uword stack_lower_;
+};
+
+
 // If the VM is compiled without frame pointers (which is the default on
 // recent GCC versions with optimizing enabled) the stack walking code may
-// fail (sometimes leading to a crash).
+// fail.
 //
 class ProfilerNativeStackWalker : public ValueObject {
  public:
   ProfilerNativeStackWalker(Sample* sample,
                             uword stack_lower,
                             uword stack_upper,
                             uword pc,
                             uword fp,
                             uword sp)
       : sample_(sample),
         stack_upper_(stack_upper),
         original_pc_(pc),
         original_fp_(fp),
         original_sp_(sp),
         lower_bound_(stack_lower) {
     ASSERT(sample_ != NULL);
   }
 
-  void walk(Heap* heap) {
+  void walk() {
     const uword kMaxStep = VirtualMemory::PageSize();
 
     sample_->SetAt(0, original_pc_);
 
     uword* pc = reinterpret_cast<uword*>(original_pc_);
     uword* fp = reinterpret_cast<uword*>(original_fp_);
     uword* previous_fp = fp;
 
     uword gap = original_fp_ - original_sp_;
     if (gap >= kMaxStep) {
@@ skipping 150 matching lines @@
   sample->Init(isolate, OS::GetCurrentTimeMicros(), state.tid);
   sample->set_vm_tag(isolate->vm_tag());
   sample->set_user_tag(isolate->user_tag());
   sample->set_sp(state.sp);
   sample->set_fp(state.fp);
   SetPCMarkerIfSafe(sample);
 
   // Walk the call stack.
   if (FLAG_profile_vm) {
     // Always walk the native stack collecting both native and Dart frames.
-    ProfilerNativeStackWalker stackWalker(sample, stack_lower, stack_upper,
-                                          state.pc, state.fp, state.sp);
-    stackWalker.walk(isolate->heap());
+    ProfilerNativeStackWalker stackWalker(sample,
+                                          stack_lower,
+                                          stack_upper,
+                                          state.pc,
+                                          state.fp,
+                                          state.sp);
+    stackWalker.walk();
   } else {
     // Attempt to walk only the Dart call stack, falling back to walking
     // the native stack.
     if ((isolate->stub_code() != NULL) &&
         (isolate->top_exit_frame_info() != 0) &&
         (isolate->vm_tag() != VMTag::kScriptTagId)) {
       // We have a valid exit frame info, use the Dart stack walker.
-      ProfilerDartStackWalker stackWalker(isolate, sample);
+      ProfilerDartExitStackWalker stackWalker(isolate, sample);
+      stackWalker.walk();
+    } else if ((isolate->stub_code() != NULL) &&
+               (isolate->top_exit_frame_info() == 0) &&
+               (isolate->vm_tag() == VMTag::kScriptTagId)) {
+      // We are executing Dart code. We have frame pointers.
+      ProfilerDartStackWalker stackWalker(isolate,
+                                          sample,
+                                          stack_lower,
+                                          stack_upper,
+                                          state.pc,
+                                          state.fp,
+                                          state.sp);
       stackWalker.walk();
     } else {
-      ProfilerNativeStackWalker stackWalker(sample, stack_lower, stack_upper,
-                                            state.pc, state.fp, state.sp);
-      stackWalker.walk(isolate->heap());
+      // Fall back to an extremely conservative stack walker.
+      ProfilerNativeStackWalker stackWalker(sample,
+                                            stack_lower,
+                                            stack_upper,
+                                            state.pc,
+                                            state.fp,
+                                            state.sp);
+      stackWalker.walk();
     }
   }
 }
 
 }  // namespace dart