[vm/concurrency] Avoid O(n) traversal of isolates to find pending deopt
To avoid a O(n) traversal of isolates in order to find pending deopts,
we'll move the pending deopt state to the Thread. It's really a property
of a thread: when the thread's stack gets unwound - via return or
exceptional flow - we remove pending deopts.
This CL also encapsulates the pending deopt logic into a [PendingDeopts]
class - thereby avoiding logic around manipulating this array being
spread around. It simplifies the already very big [Isolate] class.
TEST=Refactoring of existing code.
Issue https://github.com/dart-lang/sdk/issues/36097
Closes https://github.com/dart-lang/sdk/issues/45168
Change-Id: I5a9b18c577f21a0f2a88332b1bc26641ec39d2af
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/188521
Commit-Queue: Martin Kustermann <kustermann@google.com>
Reviewed-by: Alexander Aprelev <aam@google.com>
diff --git a/runtime/vm/exceptions.cc b/runtime/vm/exceptions.cc
index 306c122..363fd1e 100644
--- a/runtime/vm/exceptions.cc
+++ b/runtime/vm/exceptions.cc
@@ -537,44 +537,8 @@
*handler_fp = frame->fp();
}
-static uword RemapExceptionPCForDeopt(Thread* thread,
- uword program_counter,
- uword frame_pointer) {
- MallocGrowableArray<PendingLazyDeopt>* pending_deopts =
- thread->isolate()->pending_deopts();
- if (pending_deopts->length() > 0) {
- // Check if the target frame is scheduled for lazy deopt.
- for (intptr_t i = 0; i < pending_deopts->length(); i++) {
- if ((*pending_deopts)[i].fp() == frame_pointer) {
- // Deopt should now resume in the catch handler instead of after the
- // call.
- (*pending_deopts)[i].set_pc(program_counter);
-
- // Jump to the deopt stub instead of the catch handler.
- program_counter = StubCode::DeoptimizeLazyFromThrow().EntryPoint();
- if (FLAG_trace_deoptimization) {
- THR_Print("Throwing to frame scheduled for lazy deopt fp=%" Pp "\n",
- frame_pointer);
-
-#if defined(DEBUG)
- // Ensure the frame references optimized code.
- ObjectPtr pc_marker = *(reinterpret_cast<ObjectPtr*>(
- frame_pointer + runtime_frame_layout.code_from_fp * kWordSize));
- Code& code = Code::Handle(Code::RawCast(pc_marker));
- ASSERT(code.is_optimized() && !code.is_force_optimized());
-#endif
- }
- break;
- }
- }
- }
- return program_counter;
-}
-
static void ClearLazyDeopts(Thread* thread, uword frame_pointer) {
- MallocGrowableArray<PendingLazyDeopt>* pending_deopts =
- thread->isolate()->pending_deopts();
- if (pending_deopts->length() > 0) {
+ if (thread->pending_deopts().HasPendingDeopts()) {
// We may be jumping over frames scheduled for lazy deopt. Remove these
// frames from the pending deopt table, but only after unmarking them so
// any stack walk that happens before the stack is unwound will still work.
@@ -596,17 +560,8 @@
ValidateFrames();
#endif
- for (intptr_t i = 0; i < pending_deopts->length(); i++) {
- if ((*pending_deopts)[i].fp() < frame_pointer) {
- if (FLAG_trace_deoptimization) {
- THR_Print(
- "Lazy deopt skipped due to throw for "
- "fp=%" Pp ", pc=%" Pp "\n",
- (*pending_deopts)[i].fp(), (*pending_deopts)[i].pc());
- }
- pending_deopts->RemoveAt(i--);
- }
- }
+ thread->pending_deopts().ClearPendingDeoptsBelow(
+ frame_pointer, PendingDeopts::kClearDueToThrow);
#if defined(DEBUG)
ValidateFrames();
@@ -620,8 +575,8 @@
uword frame_pointer,
const Object& exception_object,
const Object& stacktrace_object) {
- uword remapped_pc =
- RemapExceptionPCForDeopt(thread, program_counter, frame_pointer);
+ uword remapped_pc = thread->pending_deopts().RemapExceptionPCForDeopt(
+ program_counter, frame_pointer);
thread->set_active_exception(exception_object);
thread->set_active_stacktrace(stacktrace_object);
thread->set_resume_pc(remapped_pc);
diff --git a/runtime/vm/heap/weak_code.cc b/runtime/vm/heap/weak_code.cc
index c23372b..c482fe7 100644
--- a/runtime/vm/heap/weak_code.cc
+++ b/runtime/vm/heap/weak_code.cc
@@ -77,15 +77,15 @@
isolate_group->RunWithStoppedMutators([&]() {
Code& code = Code::Handle();
isolate_group->ForEachIsolate([&](Isolate* isolate) {
+ auto mutator_thread = isolate->mutator_thread();
DartFrameIterator iterator(
- isolate->mutator_thread(),
- StackFrameIterator::kAllowCrossThreadIteration);
+ mutator_thread, StackFrameIterator::kAllowCrossThreadIteration);
StackFrame* frame = iterator.NextFrame();
while (frame != nullptr) {
code = frame->LookupDartCode();
if (IsOptimizedCode(code_objects, code)) {
ReportDeoptimization(code);
- DeoptimizeAt(isolate, code, frame);
+ DeoptimizeAt(mutator_thread, code, frame);
}
frame = iterator.NextFrame();
}
diff --git a/runtime/vm/isolate.cc b/runtime/vm/isolate.cc
index 46dfb45..0781a1b 100644
--- a/runtime/vm/isolate.cc
+++ b/runtime/vm/isolate.cc
@@ -1731,7 +1731,6 @@
on_cleanup_callback_(Isolate::CleanupCallback()),
random_(),
mutex_(NOT_IN_PRODUCT("Isolate::mutex_")),
- pending_deopts_(new MallocGrowableArray<PendingLazyDeopt>()),
tag_table_(GrowableObjectArray::null()),
sticky_error_(Error::null()),
spawn_count_monitor_(),
@@ -1776,8 +1775,6 @@
#if defined(USING_SIMULATOR)
delete simulator_;
#endif
- delete pending_deopts_;
- pending_deopts_ = nullptr;
delete message_handler_;
message_handler_ =
nullptr; // Fail fast if we send messages to a dead isolate.
@@ -2857,18 +2854,6 @@
api_state()->VisitWeakHandlesUnlocked(visitor);
}
-uword IsolateGroup::FindPendingDeoptAtSafepoint(uword fp) {
- for (Isolate* isolate : isolates_) {
- for (intptr_t i = 0; i < isolate->pending_deopts_->length(); i++) {
- if ((*isolate->pending_deopts_)[i].fp() == fp) {
- return (*isolate->pending_deopts_)[i].pc();
- }
- }
- }
- FATAL("Missing pending deopt entry");
- return 0;
-}
-
void IsolateGroup::DeferredMarkLiveTemporaries() {
ForEachIsolate(
[&](Isolate* isolate) { isolate->DeferredMarkLiveTemporaries(); },
@@ -2917,42 +2902,6 @@
}
#endif // !defined(PRODUCT)
-void Isolate::AddPendingDeopt(uword fp, uword pc) {
- // GrowableArray::Add is not atomic and may be interrupt by a profiler
- // stack walk.
- MallocGrowableArray<PendingLazyDeopt>* old_pending_deopts = pending_deopts_;
- MallocGrowableArray<PendingLazyDeopt>* new_pending_deopts =
- new MallocGrowableArray<PendingLazyDeopt>(old_pending_deopts->length() +
- 1);
- for (intptr_t i = 0; i < old_pending_deopts->length(); i++) {
- ASSERT((*old_pending_deopts)[i].fp() != fp);
- new_pending_deopts->Add((*old_pending_deopts)[i]);
- }
- PendingLazyDeopt deopt(fp, pc);
- new_pending_deopts->Add(deopt);
-
- pending_deopts_ = new_pending_deopts;
- delete old_pending_deopts;
-}
-
-uword Isolate::FindPendingDeopt(uword fp) const {
- for (intptr_t i = 0; i < pending_deopts_->length(); i++) {
- if ((*pending_deopts_)[i].fp() == fp) {
- return (*pending_deopts_)[i].pc();
- }
- }
- FATAL("Missing pending deopt entry");
- return 0;
-}
-
-void Isolate::ClearPendingDeoptsAtOrBelow(uword fp) const {
- for (intptr_t i = pending_deopts_->length() - 1; i >= 0; i--) {
- if ((*pending_deopts_)[i].fp() <= fp) {
- pending_deopts_->RemoveAt(i);
- }
- }
-}
-
#ifndef PRODUCT
static const char* ExceptionPauseInfoToServiceEnum(Dart_ExceptionPauseInfo pi) {
switch (pi) {
diff --git a/runtime/vm/isolate.h b/runtime/vm/isolate.h
index fc85824..c8217eb 100644
--- a/runtime/vm/isolate.h
+++ b/runtime/vm/isolate.h
@@ -96,18 +96,6 @@
constexpr int kNullSafetyOptionStrong = 2;
extern int FLAG_sound_null_safety;
-class PendingLazyDeopt {
- public:
- PendingLazyDeopt(uword fp, uword pc) : fp_(fp), pc_(pc) {}
- uword fp() { return fp_; }
- uword pc() { return pc_; }
- void set_pc(uword pc) { pc_ = pc; }
-
- private:
- uword fp_;
- uword pc_;
-};
-
class IsolateVisitor {
public:
IsolateVisitor() {}
@@ -776,8 +764,6 @@
RemappingCidsBit::update(value, isolate_group_flags_);
}
- uword FindPendingDeoptAtSafepoint(uword fp);
-
void RememberLiveTemporaries();
void DeferredMarkLiveTemporaries();
@@ -1230,12 +1216,6 @@
ObjectIdRing* EnsureObjectIdRing();
#endif // !defined(PRODUCT)
- void AddPendingDeopt(uword fp, uword pc);
- uword FindPendingDeopt(uword fp) const;
- void ClearPendingDeoptsAtOrBelow(uword fp) const;
- MallocGrowableArray<PendingLazyDeopt>* pending_deopts() const {
- return pending_deopts_;
- }
bool IsDeoptimizing() const { return deopt_context_ != nullptr; }
DeoptContext* deopt_context() const { return deopt_context_; }
void set_deopt_context(DeoptContext* value) {
@@ -1618,7 +1598,6 @@
Mutex mutex_; // Protects compiler stats.
MessageHandler* message_handler_ = nullptr;
intptr_t defer_finalization_count_ = 0;
- MallocGrowableArray<PendingLazyDeopt>* pending_deopts_;
DeoptContext* deopt_context_ = nullptr;
GrowableObjectArrayPtr tag_table_;
diff --git a/runtime/vm/pending_deopts.cc b/runtime/vm/pending_deopts.cc
new file mode 100644
index 0000000..46ae036
--- /dev/null
+++ b/runtime/vm/pending_deopts.cc
@@ -0,0 +1,104 @@
+// Copyright (c) 2021, 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/pending_deopts.h"
+#include "vm/log.h"
+#include "vm/stack_frame.h"
+#include "vm/stub_code.h"
+
+namespace dart {
+
+DECLARE_FLAG(bool, trace_deoptimization);
+
+PendingDeopts::PendingDeopts()
+ : pending_deopts_(new MallocGrowableArray<PendingLazyDeopt>()) {}
+PendingDeopts::~PendingDeopts() {
+ delete pending_deopts_;
+ pending_deopts_ = nullptr;
+}
+
+void PendingDeopts::AddPendingDeopt(uword fp, uword pc) {
+ // GrowableArray::Add is not atomic and may be interrupted by a profiler
+ // stack walk.
+ MallocGrowableArray<PendingLazyDeopt>* old_pending_deopts = pending_deopts_;
+ MallocGrowableArray<PendingLazyDeopt>* new_pending_deopts =
+ new MallocGrowableArray<PendingLazyDeopt>(old_pending_deopts->length() +
+ 1);
+ for (intptr_t i = 0; i < old_pending_deopts->length(); i++) {
+ ASSERT((*old_pending_deopts)[i].fp() != fp);
+ new_pending_deopts->Add((*old_pending_deopts)[i]);
+ }
+ PendingLazyDeopt deopt(fp, pc);
+ new_pending_deopts->Add(deopt);
+
+ pending_deopts_ = new_pending_deopts;
+ delete old_pending_deopts;
+}
+
+uword PendingDeopts::FindPendingDeopt(uword fp) {
+ for (intptr_t i = 0; i < pending_deopts_->length(); i++) {
+ if ((*pending_deopts_)[i].fp() == fp) {
+ return (*pending_deopts_)[i].pc();
+ }
+ }
+ FATAL("Missing pending deopt entry");
+ return 0;
+}
+
+void PendingDeopts::ClearPendingDeoptsBelow(uword fp, ClearReason reason) {
+ for (intptr_t i = pending_deopts_->length() - 1; i >= 0; i--) {
+ if ((*pending_deopts_)[i].fp() < fp) {
+ if (FLAG_trace_deoptimization) {
+ switch (reason) {
+ case kClearDueToThrow:
+ THR_Print(
+ "Lazy deopt skipped due to throw for "
+ "fp=%" Pp ", pc=%" Pp "\n",
+ (*pending_deopts_)[i].fp(), (*pending_deopts_)[i].pc());
+ break;
+ case kClearDueToDeopt:
+ THR_Print("Lazy deopt fp=%" Pp " pc=%" Pp "\n",
+ (*pending_deopts_)[i].fp(), (*pending_deopts_)[i].pc());
+ break;
+ }
+ }
+ pending_deopts_->RemoveAt(i);
+ }
+ }
+}
+
+void PendingDeopts::ClearPendingDeoptsAtOrBelow(uword fp, ClearReason reason) {
+ ClearPendingDeoptsBelow(fp + kWordSize, reason);
+}
+
+uword PendingDeopts::RemapExceptionPCForDeopt(uword program_counter,
+ uword frame_pointer) {
+ // Check if the target frame is scheduled for lazy deopt.
+ for (intptr_t i = 0; i < pending_deopts_->length(); i++) {
+ if ((*pending_deopts_)[i].fp() == frame_pointer) {
+ // Deopt should now resume in the catch handler instead of after the
+ // call.
+ (*pending_deopts_)[i].set_pc(program_counter);
+
+ // Jump to the deopt stub instead of the catch handler.
+ program_counter = StubCode::DeoptimizeLazyFromThrow().EntryPoint();
+ if (FLAG_trace_deoptimization) {
+ THR_Print("Throwing to frame scheduled for lazy deopt fp=%" Pp "\n",
+ frame_pointer);
+
+#if defined(DEBUG)
+ // Ensure the frame references optimized code.
+ ObjectPtr pc_marker = *(reinterpret_cast<ObjectPtr*>(
+ frame_pointer + runtime_frame_layout.code_from_fp * kWordSize));
+ Code& code = Code::Handle(Code::RawCast(pc_marker));
+ ASSERT(code.is_optimized() && !code.is_force_optimized());
+#endif
+ }
+ break;
+ }
+ }
+ return program_counter;
+}
+
+} // namespace dart
diff --git a/runtime/vm/pending_deopts.h b/runtime/vm/pending_deopts.h
new file mode 100644
index 0000000..778dba2
--- /dev/null
+++ b/runtime/vm/pending_deopts.h
@@ -0,0 +1,51 @@
+// Copyright (c) 2021, 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.
+
+#ifndef RUNTIME_VM_PENDING_DEOPTS_H_
+#define RUNTIME_VM_PENDING_DEOPTS_H_
+
+#if defined(SHOULD_NOT_INCLUDE_RUNTIME)
+#error "Should not include runtime"
+#endif
+
+#include "vm/growable_array.h"
+
+namespace dart {
+
+class PendingLazyDeopt {
+ public:
+ PendingLazyDeopt(uword fp, uword pc) : fp_(fp), pc_(pc) {}
+ uword fp() { return fp_; }
+ uword pc() { return pc_; }
+ void set_pc(uword pc) { pc_ = pc; }
+
+ private:
+ uword fp_;
+ uword pc_;
+};
+
+class PendingDeopts {
+ public:
+ enum ClearReason {
+ kClearDueToThrow,
+ kClearDueToDeopt,
+ };
+ PendingDeopts();
+ ~PendingDeopts();
+
+ bool HasPendingDeopts() { return pending_deopts_->length() > 0; }
+
+ void AddPendingDeopt(uword fp, uword pc);
+ uword FindPendingDeopt(uword fp);
+ void ClearPendingDeoptsBelow(uword fp, ClearReason reason);
+ void ClearPendingDeoptsAtOrBelow(uword fp, ClearReason reason);
+ uword RemapExceptionPCForDeopt(uword program_counter, uword frame_pointer);
+
+ private:
+ MallocGrowableArray<PendingLazyDeopt>* pending_deopts_;
+};
+
+} // namespace dart
+
+#endif // RUNTIME_VM_PENDING_DEOPTS_H_
diff --git a/runtime/vm/runtime_entry.cc b/runtime/vm/runtime_entry.cc
index bf4bffa..b3325b0 100644
--- a/runtime/vm/runtime_entry.cc
+++ b/runtime/vm/runtime_entry.cc
@@ -2931,7 +2931,7 @@
}
}
-void DeoptimizeAt(Isolate* isolate,
+void DeoptimizeAt(Thread* mutator_thread,
const Code& optimized_code,
StackFrame* frame) {
ASSERT(optimized_code.is_optimized());
@@ -2974,7 +2974,7 @@
// N.B.: Update the pending deopt table before updating the frame. The
// profiler may attempt a stack walk in between.
- isolate->AddPendingDeopt(frame->fp(), deopt_pc);
+ mutator_thread->pending_deopts().AddPendingDeopt(frame->fp(), deopt_pc);
frame->MarkForLazyDeopt();
if (FLAG_trace_deoptimization) {
@@ -2994,15 +2994,15 @@
isolate_group->RunWithStoppedMutators([&]() {
Code& optimized_code = Code::Handle();
isolate_group->ForEachIsolate([&](Isolate* isolate) {
+ auto mutator_thread = isolate->mutator_thread();
DartFrameIterator iterator(
- isolate->mutator_thread(),
- StackFrameIterator::kAllowCrossThreadIteration);
+ mutator_thread, StackFrameIterator::kAllowCrossThreadIteration);
StackFrame* frame = iterator.NextFrame();
while (frame != nullptr) {
optimized_code = frame->LookupDartCode();
if (optimized_code.is_optimized() &&
!optimized_code.is_force_optimized()) {
- DeoptimizeAt(isolate, optimized_code, frame);
+ DeoptimizeAt(mutator_thread, optimized_code, frame);
}
frame = iterator.NextFrame();
}
@@ -3090,18 +3090,16 @@
}
if (is_lazy_deopt != 0u) {
- uword deopt_pc = isolate->FindPendingDeopt(caller_frame->fp());
- if (FLAG_trace_deoptimization) {
- THR_Print("Lazy deopt fp=%" Pp " pc=%" Pp "\n", caller_frame->fp(),
- deopt_pc);
- }
+ const uword deopt_pc =
+ thread->pending_deopts().FindPendingDeopt(caller_frame->fp());
// N.B.: Update frame before updating pending deopt table. The profiler
// may attempt a stack walk in between.
caller_frame->set_pc(deopt_pc);
ASSERT(caller_frame->pc() == deopt_pc);
ASSERT(optimized_code.ContainsInstructionAt(caller_frame->pc()));
- isolate->ClearPendingDeoptsAtOrBelow(caller_frame->fp());
+ thread->pending_deopts().ClearPendingDeoptsAtOrBelow(
+ caller_frame->fp(), PendingDeopts::kClearDueToDeopt);
} else {
if (FLAG_trace_deoptimization) {
THR_Print("Eager deopt fp=%" Pp " pc=%" Pp "\n", caller_frame->fp(),
diff --git a/runtime/vm/runtime_entry.h b/runtime/vm/runtime_entry.h
index f1171a6..c3468ba 100644
--- a/runtime/vm/runtime_entry.h
+++ b/runtime/vm/runtime_entry.h
@@ -160,7 +160,7 @@
const char* DeoptReasonToCString(ICData::DeoptReasonId deopt_reason);
-void DeoptimizeAt(Isolate* isolate,
+void DeoptimizeAt(Thread* mutator_thread,
const Code& optimized_code,
StackFrame* frame);
void DeoptimizeFunctionsOnStack();
diff --git a/runtime/vm/stack_frame.h b/runtime/vm/stack_frame.h
index 6969642..2275811 100644
--- a/runtime/vm/stack_frame.h
+++ b/runtime/vm/stack_frame.h
@@ -143,7 +143,7 @@
fp() + (kSavedCallerPcSlotFromFp * kWordSize)));
ASSERT(raw_pc != StubCode::DeoptimizeLazyFromThrow().EntryPoint());
if (raw_pc == StubCode::DeoptimizeLazyFromReturn().EntryPoint()) {
- return isolate_group()->FindPendingDeoptAtSafepoint(GetCallerFp());
+ return thread_->pending_deopts().FindPendingDeopt(GetCallerFp());
}
return raw_pc;
}
diff --git a/runtime/vm/thread.h b/runtime/vm/thread.h
index be7244a..5aee930 100644
--- a/runtime/vm/thread.h
+++ b/runtime/vm/thread.h
@@ -20,6 +20,7 @@
#include "vm/handles.h"
#include "vm/heap/pointer_block.h"
#include "vm/os_thread.h"
+#include "vm/pending_deopts.h"
#include "vm/random.h"
#include "vm/runtime_entry_list.h"
#include "vm/thread_stack_resource.h"
@@ -908,6 +909,8 @@
void PrintJSON(JSONStream* stream) const;
#endif
+ PendingDeopts& pending_deopts() { return pending_deopts_; }
+
private:
template <class T>
T* AllocateReusableHandle();
@@ -1012,6 +1015,9 @@
uint16_t deferred_interrupts_;
int32_t stack_overflow_count_;
+ // Deoptimization of stack frames.
+ PendingDeopts pending_deopts_;
+
// Compiler state:
CompilerState* compiler_state_ = nullptr;
HierarchyInfo* hierarchy_info_;
diff --git a/runtime/vm/vm_sources.gni b/runtime/vm/vm_sources.gni
index a142449..a2ed92d 100644
--- a/runtime/vm/vm_sources.gni
+++ b/runtime/vm/vm_sources.gni
@@ -215,6 +215,8 @@
"os_win.cc",
"parser.cc",
"parser.h",
+ "pending_deopts.cc",
+ "pending_deopts.h",
"pointer_tagging.h",
"port.cc",
"port.h",
