From 649278cec7119cdd1bea3d0b710dbb2aa7c650b6 Mon Sep 17 00:00:00 2001 From: Hiroshi Yamauchi Date: Wed, 13 Aug 2014 11:12:22 -0700 Subject: [PATCH] More efficient stack walk in exception throwing. In the exception handling code, we currently walk down the stack twice, once to get the stack height which we use to compute frame IDs (the bottom frame is zero), and once more to find the catch block to jump to. For a deep stack, this could result in very slow exception handling. That is, if have a lot of finally or catch blocks that we end up jumping to in a deep stack, we need to do a lot of catch/rethrow chains. Since we'd need to walk down to the bottom each time to compute frames IDs in each catch/rethrow, we'd need to walk down O(N^2) frames at the worst case. Instead of frames IDs ((the bottom frame is zero), we will use the frame depth (the top frame is zero) and no longer need to walk down the stack just to get the stack height. We walk down O(N) frames. This was what was happening with code.google.gson.functional.CircularReferenceTest. With this change, the test run time went from ~120s down to ~3s on N5 and it no longer crashes due to the thread suspension timeout. Bug: 16800209 Change-Id: Ie815df1e3e8fb9d82e40685d4cc2b8838fd8aa07 --- runtime/quick_exception_handler.cc | 22 +++++++++++----------- runtime/quick_exception_handler.h | 8 ++++---- runtime/stack.h | 4 ++++ 3 files changed, 19 insertions(+), 15 deletions(-) diff --git a/runtime/quick_exception_handler.cc b/runtime/quick_exception_handler.cc index 41d69894d..98eeda726 100644 --- a/runtime/quick_exception_handler.cc +++ b/runtime/quick_exception_handler.cc @@ -29,14 +29,14 @@ namespace art { static constexpr bool kDebugExceptionDelivery = false; -static constexpr size_t kInvalidFrameId = 0xffffffff; +static constexpr size_t kInvalidFrameDepth = 0xffffffff; QuickExceptionHandler::QuickExceptionHandler(Thread* self, bool is_deoptimization) : self_(self), context_(self->GetLongJumpContext()), is_deoptimization_(is_deoptimization), method_tracing_active_(is_deoptimization || Runtime::Current()->GetInstrumentation()->AreExitStubsInstalled()), handler_quick_frame_(nullptr), handler_quick_frame_pc_(0), handler_method_(nullptr), - handler_dex_pc_(0), clear_exception_(false), handler_frame_id_(kInvalidFrameId) { + handler_dex_pc_(0), clear_exception_(false), handler_frame_depth_(kInvalidFrameDepth) { } // Finds catch handler or prepares for deoptimization. @@ -51,7 +51,7 @@ class CatchBlockStackVisitor FINAL : public StackVisitor { bool VisitFrame() OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { mirror::ArtMethod* method = GetMethod(); - exception_handler_->SetHandlerFrameId(GetFrameId()); + exception_handler_->SetHandlerFrameDepth(GetFrameDepth()); if (method == nullptr) { // This is the upcall, we remember the frame and last pc so that we may long jump to them. exception_handler_->SetHandlerQuickFramePc(GetCurrentQuickFramePc()); @@ -177,7 +177,7 @@ class DeoptimizeStackVisitor FINAL : public StackVisitor { } bool VisitFrame() OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { - exception_handler_->SetHandlerFrameId(GetFrameId()); + exception_handler_->SetHandlerFrameDepth(GetFrameDepth()); mirror::ArtMethod* method = GetMethod(); if (method == nullptr) { // This is the upcall, we remember the frame and last pc so that we may long jump to them. @@ -295,17 +295,17 @@ void QuickExceptionHandler::DeoptimizeStack() { // Unwinds all instrumentation stack frame prior to catch handler or upcall. class InstrumentationStackVisitor : public StackVisitor { public: - InstrumentationStackVisitor(Thread* self, bool is_deoptimization, size_t frame_id) + InstrumentationStackVisitor(Thread* self, bool is_deoptimization, size_t frame_depth) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) : StackVisitor(self, nullptr), - self_(self), frame_id_(frame_id), + self_(self), frame_depth_(frame_depth), instrumentation_frames_to_pop_(0) { - CHECK_NE(frame_id_, kInvalidFrameId); + CHECK_NE(frame_depth_, kInvalidFrameDepth); } bool VisitFrame() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { - size_t current_frame_id = GetFrameId(); - if (current_frame_id > frame_id_) { + size_t current_frame_depth = GetFrameDepth(); + if (current_frame_depth < frame_depth_) { CHECK(GetMethod() != nullptr); if (UNLIKELY(GetQuickInstrumentationExitPc() == GetReturnPc())) { ++instrumentation_frames_to_pop_; @@ -323,7 +323,7 @@ class InstrumentationStackVisitor : public StackVisitor { private: Thread* const self_; - const size_t frame_id_; + const size_t frame_depth_; size_t instrumentation_frames_to_pop_; DISALLOW_COPY_AND_ASSIGN(InstrumentationStackVisitor); @@ -331,7 +331,7 @@ class InstrumentationStackVisitor : public StackVisitor { void QuickExceptionHandler::UpdateInstrumentationStack() { if (method_tracing_active_) { - InstrumentationStackVisitor visitor(self_, is_deoptimization_, handler_frame_id_); + InstrumentationStackVisitor visitor(self_, is_deoptimization_, handler_frame_depth_); visitor.WalkStack(true); size_t instrumentation_frames_to_pop = visitor.GetInstrumentationFramesToPop(); diff --git a/runtime/quick_exception_handler.h b/runtime/quick_exception_handler.h index 1d600ed69..b93769cb9 100644 --- a/runtime/quick_exception_handler.h +++ b/runtime/quick_exception_handler.h @@ -77,8 +77,8 @@ class QuickExceptionHandler { clear_exception_ = clear_exception; } - void SetHandlerFrameId(size_t frame_id) { - handler_frame_id_ = frame_id; + void SetHandlerFrameDepth(size_t frame_depth) { + handler_frame_depth_ = frame_depth; } private: @@ -97,8 +97,8 @@ class QuickExceptionHandler { uint32_t handler_dex_pc_; // Should the exception be cleared as the catch block has no move-exception? bool clear_exception_; - // Frame id of the catch handler or the upcall. - size_t handler_frame_id_; + // Frame depth of the catch handler or the upcall. + size_t handler_frame_depth_; DISALLOW_COPY_AND_ASSIGN(QuickExceptionHandler); }; diff --git a/runtime/stack.h b/runtime/stack.h index 578f569c4..e58caeee7 100644 --- a/runtime/stack.h +++ b/runtime/stack.h @@ -553,6 +553,10 @@ class StackVisitor { return num_frames_; } + size_t GetFrameDepth() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + return cur_depth_; + } + // Get the method and dex pc immediately after the one that's currently being visited. bool GetNextMethodAndDexPc(mirror::ArtMethod** next_method, uint32_t* next_dex_pc) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); -- 2.11.0