[VM] Bare instructions - Part 3: Add support for building a PC -> Code mapping table
This CL adds a [ReversePcLookupCache] which, based on a list of code
objects, builds up a binary searchable table for mapping PCs to Code
objects (where all the metadata is available, like stackmaps, ...).
This CL also adds stack walking support for "bare instruction" frames.
In a later part we will start emitting the sorted list of code objects
(via the new field in the object store) under a flag.
Issue https://github.com/dart-lang/sdk/issues/33274
Change-Id: I3c06c12bc0fb266dc1bd843a4a11b5208773151d
Reviewed-on: https://dart-review.googlesource.com/c/85746
Commit-Queue: Martin Kustermann <kustermann@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
diff --git a/runtime/vm/isolate.cc b/runtime/vm/isolate.cc
index 47d3b8e..f3a9979 100644
--- a/runtime/vm/isolate.cc
+++ b/runtime/vm/isolate.cc
@@ -36,6 +36,7 @@
#include "vm/port.h"
#include "vm/profiler.h"
#include "vm/reusable_handles.h"
+#include "vm/reverse_pc_lookup_cache.h"
#include "vm/service.h"
#include "vm/service_event.h"
#include "vm/service_isolate.h"
@@ -946,7 +947,8 @@
handler_info_cache_(),
catch_entry_moves_cache_(),
embedder_entry_points_(NULL),
- obfuscation_map_(NULL) {
+ obfuscation_map_(NULL),
+ reverse_pc_lookup_cache_(nullptr) {
FlagsCopyFrom(api_flags);
SetErrorsFatal(true);
set_compilation_allowed(true);
@@ -974,6 +976,9 @@
// RELEASE_ASSERT(reload_context_ == NULL);
#endif // !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME)
+ delete reverse_pc_lookup_cache_;
+ reverse_pc_lookup_cache_ = nullptr;
+
delete background_compiler_;
background_compiler_ = NULL;
diff --git a/runtime/vm/isolate.h b/runtime/vm/isolate.h
index 25dc8dc..c07bf00 100644
--- a/runtime/vm/isolate.h
+++ b/runtime/vm/isolate.h
@@ -64,6 +64,7 @@
class RawFloat32x4;
class RawInt32x4;
class RawUserTag;
+class ReversePcLookupCache;
class SafepointHandler;
class SampleBuffer;
class SendPort;
@@ -704,6 +705,17 @@
void set_obfuscation_map(const char** map) { obfuscation_map_ = map; }
const char** obfuscation_map() const { return obfuscation_map_; }
+ // Returns the pc -> code lookup cache object for this isolate.
+ ReversePcLookupCache* reverse_pc_lookup_cache() const {
+ return reverse_pc_lookup_cache_;
+ }
+
+ // Sets the pc -> code lookup cache object for this isolate.
+ void set_reverse_pc_lookup_cache(ReversePcLookupCache* table) {
+ ASSERT(reverse_pc_lookup_cache_ == nullptr);
+ reverse_pc_lookup_cache_ = table;
+ }
+
// Isolate-specific flag handling.
static void FlagsInitialize(Dart_IsolateFlags* api_flags);
void FlagsCopyTo(Dart_IsolateFlags* api_flags) const;
@@ -1006,6 +1018,8 @@
Dart_QualifiedFunctionName* embedder_entry_points_;
const char** obfuscation_map_;
+ ReversePcLookupCache* reverse_pc_lookup_cache_;
+
static Dart_IsolateCreateCallback create_callback_;
static Dart_IsolateShutdownCallback shutdown_callback_;
static Dart_IsolateCleanupCallback cleanup_callback_;
diff --git a/runtime/vm/object.h b/runtime/vm/object.h
index 967a2fa..110bf5c 100644
--- a/runtime/vm/object.h
+++ b/runtime/vm/object.h
@@ -7947,6 +7947,8 @@
return memcmp(a->ptr()->data(), b->ptr()->data(), kWordSize * length) == 0;
}
+ static RawObject** DataOf(RawArray* array) { return array->ptr()->data(); }
+
RawObject* At(intptr_t index) const { return *ObjectAddr(index); }
void SetAt(intptr_t index, const Object& value) const {
// TODO(iposva): Add storing NoSafepointScope.
diff --git a/runtime/vm/object_store.h b/runtime/vm/object_store.h
index cd760de..6b9695d 100644
--- a/runtime/vm/object_store.h
+++ b/runtime/vm/object_store.h
@@ -124,6 +124,7 @@
RW(Array, unique_dynamic_targets) \
RW(GrowableObjectArray, megamorphic_cache_table) \
RW(Code, build_method_extractor_code) \
+ RW(Array, code_order_table) \
R_(Code, megamorphic_miss_code) \
R_(Function, megamorphic_miss_function) \
RW(Array, obfuscation_map) \
diff --git a/runtime/vm/reverse_pc_lookup_cache.cc b/runtime/vm/reverse_pc_lookup_cache.cc
new file mode 100644
index 0000000..325d98f
--- /dev/null
+++ b/runtime/vm/reverse_pc_lookup_cache.cc
@@ -0,0 +1,56 @@
+// Copyright (c) 2018, 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/reverse_pc_lookup_cache.h"
+
+#include "vm/isolate.h"
+
+namespace dart {
+
+#if defined(DART_PRECOMPILED_RUNTIME)
+
+static uword BeginPcFromCode(const RawCode* code) {
+ auto instr = Code::InstructionsOf(code);
+ return Instructions::PayloadStart(instr);
+}
+
+static uword EndPcFromCode(const RawCode* code) {
+ auto instr = Code::InstructionsOf(code);
+ return Instructions::PayloadStart(instr) + Instructions::Size(instr);
+}
+
+void ReversePcLookupCache::BuildAndAttachToIsolate(Isolate* isolate) {
+ auto object_store = isolate->object_store();
+ auto& array = Array::Handle(object_store->code_order_table());
+ if (!array.IsNull()) {
+ const intptr_t length = array.Length();
+ {
+ NoSafepointScope no_safepoint_scope;
+
+ const uword begin =
+ BeginPcFromCode(reinterpret_cast<RawCode*>(array.At(0)));
+ const uword end =
+ EndPcFromCode(reinterpret_cast<RawCode*>(array.At(length - 1)));
+
+ auto pc_array = new uint32_t[length];
+ for (intptr_t i = 0; i < length; i++) {
+ const auto end_pc =
+ EndPcFromCode(reinterpret_cast<RawCode*>(array.At(i)));
+ pc_array[i] = end_pc - begin;
+ }
+#if defined(DEBUG)
+ for (intptr_t i = 1; i < length; i++) {
+ ASSERT(pc_array[i - 1] <= pc_array[i]);
+ }
+#endif // defined(DEBUG)
+ auto cache =
+ new ReversePcLookupCache(isolate, pc_array, length, begin, end);
+ isolate->set_reverse_pc_lookup_cache(cache);
+ }
+ }
+}
+
+#endif // defined(DART_PRECOMPILED_RUNTIME)
+
+} // namespace dart
diff --git a/runtime/vm/reverse_pc_lookup_cache.h b/runtime/vm/reverse_pc_lookup_cache.h
new file mode 100644
index 0000000..8300b62
--- /dev/null
+++ b/runtime/vm/reverse_pc_lookup_cache.h
@@ -0,0 +1,126 @@
+// Copyright (c) 2018, 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_REVERSE_PC_LOOKUP_CACHE_H_
+#define RUNTIME_VM_REVERSE_PC_LOOKUP_CACHE_H_
+
+#include "vm/allocation.h"
+#include "vm/growable_array.h"
+#include "vm/object.h"
+#include "vm/object_store.h"
+
+namespace dart {
+
+class Isolate;
+
+#if defined(DART_PRECOMPILED_RUNTIME)
+
+// A cache for looking up a Code object based on pc (currently the cache is
+// implemented as a binary-searchable uint32 array)
+//
+// If an AOT snapshot was created with --use_bare_instructions the isolate's
+// object store will contain a `code_order_table` - which is a sorted array
+// of [Code] objects. The order is based on addresses of the code's
+// instructions in memory.
+//
+// For a binary search we would need to touch O(log(array-size)) array entries,
+// code objects and instruction objects.
+//
+// To avoid this we make another uint32 array which is initialized from the end
+// PCs of the instructions (relative to the start pc of the first instruction
+// object).
+//
+// We have the following invariants:
+//
+// BeginPcFromCode(code_array[0]) <= pc_array[0]
+// pc_array[i] == EndPcFromCode(code_array[i])
+// pc_array[i] <= pc_array[i+1]
+//
+// The lookup will then do a binary search in pc_array. The index can then be
+// used in the `code_order_table` of the object store.
+//
+// WARNING: This class cannot do memory allocation or handle allocation!
+class ReversePcLookupCache {
+ public:
+ ReversePcLookupCache(Isolate* isolate,
+ uint32_t* pc_array,
+ intptr_t length,
+ uword first_absolute_pc,
+ uword last_absolute_pc)
+ : isolate_(isolate),
+ pc_array_(pc_array),
+ length_(length),
+ first_absolute_pc_(first_absolute_pc),
+ last_absolute_pc_(last_absolute_pc) {}
+ ~ReversePcLookupCache() { delete[] pc_array_; }
+
+ // Builds a [ReversePcLookupCache] and attaches it to the isolate (if
+ // `code_order_table` is non-`null`).
+ static void BuildAndAttachToIsolate(Isolate* isolate);
+
+ // Returns `true` if the given [pc] contains can be mapped to a [Code] object
+ // using this cache.
+ inline bool Contains(uword pc) {
+ return first_absolute_pc_ <= pc && pc <= last_absolute_pc_;
+ }
+
+ // Looks up the [Code] object from a given [pc].
+ inline RawCode* Lookup(uword pc) {
+ NoSafepointScope no_safepoint_scope;
+
+ intptr_t left = 0;
+ intptr_t right = length_ - 1;
+
+ ASSERT(first_absolute_pc_ <= pc && pc < last_absolute_pc_);
+ uint32_t pc_offset = static_cast<uint32_t>(pc - first_absolute_pc_);
+
+ while (left < right) {
+ intptr_t middle = left + (right - left) / 2;
+
+ uword middle_pc = pc_array_[middle];
+ if (middle_pc < pc_offset) {
+ left = middle + 1;
+ } else {
+ right = middle;
+ }
+ }
+
+ auto code_array = isolate_->object_store()->code_order_table();
+ auto raw_code = reinterpret_cast<RawCode*>(Array::DataOf(code_array)[left]);
+
+#if defined(DEBUG)
+ ASSERT(raw_code->GetClassIdMayBeSmi() == kCodeCid);
+ ASSERT(Code::ContainsInstructionAt(raw_code, pc));
+#endif
+
+ return raw_code;
+ }
+
+ private:
+ Isolate* isolate_;
+ uint32_t* pc_array_;
+ intptr_t length_;
+ uword first_absolute_pc_;
+ uword last_absolute_pc_;
+};
+
+#else // defined(DART_PRECOMPILED_RUNTIME
+
+class ReversePcLookupCache {
+ public:
+ ReversePcLookupCache() {}
+ ~ReversePcLookupCache() {}
+
+ static void BuildAndAttachToIsolate(Isolate* isolate) {}
+
+ inline bool Contains(uword pc) { return false; }
+
+ inline RawCode* Lookup(uword pc) { UNREACHABLE(); }
+};
+
+#endif // defined(DART_PRECOMPILED_RUNTIME
+
+} // namespace dart
+
+#endif // RUNTIME_VM_REVERSE_PC_LOOKUP_CACHE_H_
diff --git a/runtime/vm/stack_frame.cc b/runtime/vm/stack_frame.cc
index 09a452c..cc94c15 100644
--- a/runtime/vm/stack_frame.cc
+++ b/runtime/vm/stack_frame.cc
@@ -15,6 +15,7 @@
#include "vm/parser.h"
#include "vm/raw_object.h"
#include "vm/reusable_handles.h"
+#include "vm/reverse_pc_lookup_cache.h"
#include "vm/scopes.h"
#include "vm/stub_code.h"
#include "vm/visitor.h"
@@ -65,16 +66,100 @@
runtime_frame_layout = default_frame_layout;
}
+Isolate* StackFrame::IsolateOfBareInstructionsFrame() const {
+ auto isolate = this->isolate();
+
+ if (isolate->object_store()->code_order_table() != Object::null()) {
+ auto rct = isolate->reverse_pc_lookup_cache();
+ if (rct->Contains(pc())) return isolate;
+ }
+
+ isolate = Dart::vm_isolate();
+ if (isolate->object_store()->code_order_table() != Object::null()) {
+ auto rct = isolate->reverse_pc_lookup_cache();
+ if (rct->Contains(pc())) return isolate;
+ }
+
+ return nullptr;
+}
+
+bool StackFrame::IsBareInstructionsDartFrame() const {
+ NoSafepointScope no_safepoint;
+
+ if (auto isolate = IsolateOfBareInstructionsFrame()) {
+ Code code;
+ auto rct = isolate->reverse_pc_lookup_cache();
+ code = rct->Lookup(pc());
+
+ // All stub codes have a `null` owner except for the megamorphic miss
+ // stub. So if it's neither of those, we are know it must be a
+ // precompiled dart frame.
+ RawObject* owner = code.owner();
+ if (owner != Object::null()) {
+ if (code.raw() ==
+ Isolate::Current()->object_store()->megamorphic_miss_code()) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool StackFrame::IsBareInstructionsStubFrame() const {
+ NoSafepointScope no_safepoint;
+
+ if (auto isolate = IsolateOfBareInstructionsFrame()) {
+ Code code;
+ auto rct = isolate->reverse_pc_lookup_cache();
+ code = rct->Lookup(pc());
+
+ // All stub codes have a `null` owner except for the megamorphic miss stub.
+ // So if it's either of those, we are know it must be a precompiled stub
+ // frame.
+ RawObject* owner = code.owner();
+ if (owner == Object::null()) {
+ return true;
+ }
+
+ if (code.raw() ==
+ Isolate::Current()->object_store()->megamorphic_miss_code()) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool StackFrame::IsDartFrame(bool validate) const {
+ ASSERT(!validate || IsValid());
+
+ if (IsEntryFrame() || IsExitFrame()) return false;
+
+ // Even though the megamorphic miss stub is a stub, we consider it as a
+ // dart frame for all practical purposes.
+ const bool is_megamorphic_miss_stub = Code::ContainsInstructionAt(
+ thread_->isolate()->object_store()->megamorphic_miss_code(), pc_);
+
+ if (is_megamorphic_miss_stub) return true;
+
+ return !IsStubFrame();
+}
+
bool StackFrame::IsStubFrame() const {
if (is_interpreted()) {
return false;
}
+
+ if (IsBareInstructionsStubFrame()) {
+ return true;
+ }
+
ASSERT(!(IsEntryFrame() || IsExitFrame()));
#if !defined(HOST_OS_WINDOWS) && !defined(HOST_OS_FUCHSIA)
// On Windows and Fuchsia, the profiler calls this from a separate thread
// where Thread::Current() is NULL, so we cannot create a NoSafepointScope.
NoSafepointScope no_safepoint;
#endif
+
RawCode* code = GetCodeObject();
ASSERT(code != Object::null());
const intptr_t cid = code->ptr()->owner_->GetClassId();
@@ -172,21 +257,27 @@
// be able to reuse the handle based code and avoid having to add
// helper functions to the raw object interface.
NoSafepointScope no_safepoint;
- RawObject* pc_marker = *(reinterpret_cast<RawObject**>(
- fp() + ((is_interpreted() ? kKBCPcMarkerSlotFromFp
- : runtime_frame_layout.code_from_fp) *
- kWordSize)));
- // May forward raw code. Note we don't just visit the pc marker slot first
- // because the visitor's forwarding might not be idempotent.
- visitor->VisitPointer(&pc_marker);
Code code;
- if (pc_marker->IsHeapObject() && (pc_marker->GetClassId() == kCodeCid)) {
- code ^= pc_marker;
+
+ if (auto isolate = IsolateOfBareInstructionsFrame()) {
+ code = isolate->reverse_pc_lookup_cache()->Lookup(pc());
} else {
- ASSERT(pc_marker == Object::null() ||
- (is_interpreted() && (!pc_marker->IsHeapObject() ||
- (pc_marker->GetClassId() == kBytecodeCid))));
+ RawObject* pc_marker = *(reinterpret_cast<RawObject**>(
+ fp() + ((is_interpreted() ? kKBCPcMarkerSlotFromFp
+ : runtime_frame_layout.code_from_fp) *
+ kWordSize)));
+ // May forward raw code. Note we don't just visit the pc marker slot first
+ // because the visitor's forwarding might not be idempotent.
+ visitor->VisitPointer(&pc_marker);
+ if (pc_marker->IsHeapObject() && (pc_marker->GetClassId() == kCodeCid)) {
+ code ^= pc_marker;
+ } else {
+ ASSERT(pc_marker == Object::null() ||
+ (is_interpreted() && (!pc_marker->IsHeapObject() ||
+ (pc_marker->GetClassId() == kBytecodeCid))));
+ }
}
+
if (!code.IsNull()) {
// Optimized frames have a stack map. We need to visit the frame based
// on the stack map.
@@ -328,6 +419,10 @@
// where Thread::Current() is NULL, so we cannot create a NoSafepointScope.
NoSafepointScope no_safepoint;
#endif
+ if (auto isolate = IsolateOfBareInstructionsFrame()) {
+ return isolate->reverse_pc_lookup_cache()->Lookup(pc());
+ }
+
RawCode* code = GetCodeObject();
if ((code != Code::null()) &&
(code->ptr()->owner_->GetClassId() == kFunctionCid)) {
@@ -338,11 +433,15 @@
RawCode* StackFrame::GetCodeObject() const {
ASSERT(!is_interpreted());
- RawObject* pc_marker = *(reinterpret_cast<RawObject**>(
- fp() + runtime_frame_layout.code_from_fp * kWordSize));
- ASSERT((pc_marker == Object::null()) ||
- (pc_marker->GetClassId() == kCodeCid));
- return reinterpret_cast<RawCode*>(pc_marker);
+ if (auto isolate = IsolateOfBareInstructionsFrame()) {
+ return isolate->reverse_pc_lookup_cache()->Lookup(pc());
+ } else {
+ RawObject* pc_marker = *(reinterpret_cast<RawObject**>(
+ fp() + runtime_frame_layout.code_from_fp * kWordSize));
+ ASSERT((pc_marker == Object::null()) ||
+ (pc_marker->GetClassId() == kCodeCid));
+ return reinterpret_cast<RawCode*>(pc_marker);
+ }
}
RawBytecode* StackFrame::LookupDartBytecode() const {
diff --git a/runtime/vm/stack_frame.h b/runtime/vm/stack_frame.h
index 85ba367..9b6b67a 100644
--- a/runtime/vm/stack_frame.h
+++ b/runtime/vm/stack_frame.h
@@ -152,14 +152,24 @@
// Check validity of a frame, used for assertion purposes.
virtual bool IsValid() const;
+ // Returns the isolate containing the bare instructions of the current frame.
+ //
+ // If the frame does not belong to a bare instructions snapshot, it will
+ // return nullptr.
+ Isolate* IsolateOfBareInstructionsFrame() const;
+
+ // Returns true iff the current frame is a bare instructions dart frame.
+ bool IsBareInstructionsDartFrame() const;
+
+ // Returns true iff the current frame is a bare instructions stub frame.
+ bool IsBareInstructionsStubFrame() const;
+
// Frame type.
- virtual bool IsDartFrame(bool validate = true) const {
- ASSERT(!validate || IsValid());
- return !(IsEntryFrame() || IsExitFrame() || IsStubFrame());
- }
+ virtual bool IsDartFrame(bool validate = true) const;
virtual bool IsStubFrame() const;
virtual bool IsEntryFrame() const { return false; }
virtual bool IsExitFrame() const { return false; }
+
virtual bool is_interpreted() const { return is_interpreted_; }
RawFunction* LookupDartFunction() const;
@@ -180,7 +190,9 @@
// Name of the frame, used for generic frame printing functionality.
virtual const char* GetName() const {
- return IsStubFrame() ? "stub" : "dart";
+ if (IsBareInstructionsStubFrame()) return "bare-stub";
+ if (IsStubFrame()) return "stub";
+ return IsBareInstructionsDartFrame() ? "bare-dart" : "dart";
}
Isolate* isolate() const { return thread_->isolate(); }
diff --git a/runtime/vm/vm_sources.gni b/runtime/vm/vm_sources.gni
index a9b02fc..593b76d 100644
--- a/runtime/vm/vm_sources.gni
+++ b/runtime/vm/vm_sources.gni
@@ -239,6 +239,8 @@
"resolver.cc",
"resolver.h",
"reusable_handles.h",
+ "reverse_pc_lookup_cache.cc",
+ "reverse_pc_lookup_cache.h",
"ring_buffer.h",
"runtime_entry.cc",
"runtime_entry.h",
