[VM/AOT] Fixes incorrect deserialization of catch entry moves
The catch entry moves are serialized in a space-efficient manner using a
suffix tree. The deserialization logic was not always correctly reading
the right catch entry moves which can cause incorrect stack frame on
catch entries and therefore can cause crashes.
Change-Id: Ic0eda8924f80262f5477ed5606eb6f74c55242c3
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/96104
Commit-Queue: Martin Kustermann <kustermann@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
Reviewed-by: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/vm/catch_entry_moves_test.cc b/runtime/vm/catch_entry_moves_test.cc
new file mode 100644
index 0000000..faa41f6
--- /dev/null
+++ b/runtime/vm/catch_entry_moves_test.cc
@@ -0,0 +1,198 @@
+// Copyright (c) 2019, 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 <functional>
+#include <utility>
+
+#include "platform/assert.h"
+#include "vm/code_descriptors.h"
+#include "vm/exceptions.h"
+#include "vm/unit_test.h"
+
+namespace dart {
+
+static CatchEntryMove NewMove(intptr_t src, intptr_t dst) {
+ return CatchEntryMove::FromSlot(CatchEntryMove::SourceKind::kTaggedSlot, src,
+ dst);
+}
+const auto kA = NewMove(1, 10);
+const auto kB = NewMove(2, 20);
+const auto kC = NewMove(3, 30);
+const auto kD = NewMove(4, 40);
+const auto kE = NewMove(5, 50);
+const auto kX = NewMove(-1, -10);
+
+const CatchEntryMove abcde[] = {kA, kB, kC, kD, kE};
+const CatchEntryMove abcdx[] = {kA, kB, kC, kD, kX};
+const CatchEntryMove xbcde[] = {kX, kB, kC, kD, kE};
+const CatchEntryMove abxde[] = {kA, kB, kX, kD, kE};
+const CatchEntryMove ab[] = {kA, kB};
+const CatchEntryMove de[] = {kD, kE};
+
+struct TestCaseMoves {
+ const CatchEntryMove* moves;
+ const intptr_t count;
+};
+
+void RunTestCaseWithPermutations(const TestCaseMoves* mapping,
+ intptr_t* insert_permutation,
+ intptr_t count) {
+ CatchEntryMovesMapBuilder b;
+
+ for (intptr_t i = 0; i < count; ++i) {
+ auto expected_moves = mapping[insert_permutation[i]];
+ b.NewMapping(/*pc_offset=*/insert_permutation[i]);
+ for (intptr_t j = 0; j < expected_moves.count; ++j) {
+ b.Append(expected_moves.moves[j]);
+ }
+ b.EndMapping();
+ }
+
+ const auto& bytes = TypedData::Handle(b.FinalizeCatchEntryMovesMap());
+ CatchEntryMovesMapReader reader(bytes);
+
+ for (intptr_t i = 0; i < count; ++i) {
+ auto expected_moves = mapping[i];
+ auto read_moves = reader.ReadMovesForPcOffset(i);
+ EXPECT_EQ(expected_moves.count, read_moves->count());
+ for (intptr_t j = 0; j < expected_moves.count; ++j) {
+ EXPECT(expected_moves.moves[j] == read_moves->At(j));
+ }
+ free(read_moves);
+ }
+}
+
+void RunTestCase(const TestCaseMoves* mapping, intptr_t count) {
+ std::unique_ptr<intptr_t[]> permutation(new intptr_t[count]);
+ for (intptr_t i = 0; i < count; ++i) {
+ permutation[i] = i;
+ }
+
+ std::function<void(intptr_t)> run_all_permutations = [&](intptr_t offset) {
+ if (offset == count) {
+ RunTestCaseWithPermutations(mapping, &permutation[0], count);
+ } else {
+ for (intptr_t i = offset; i < count; ++i) {
+ const intptr_t start = permutation[offset];
+ const intptr_t replacement = permutation[i];
+
+ permutation[offset] = replacement;
+ permutation[i] = start;
+
+ run_all_permutations(offset + 1);
+
+ permutation[offset] = start;
+ permutation[i] = replacement;
+ }
+ }
+ };
+
+ run_all_permutations(0);
+}
+
+ISOLATE_UNIT_TEST_CASE(CatchEntryMoves) {
+ // Common prefix.
+ const TestCaseMoves test1[] = {
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ abcdx,
+ ARRAY_SIZE(abcdx),
+ },
+ };
+ RunTestCase(test1, ARRAY_SIZE(test1));
+
+ // Common suffix.
+ const TestCaseMoves test2[] = {
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ xbcde,
+ ARRAY_SIZE(xbcde),
+ },
+ };
+ RunTestCase(test2, ARRAY_SIZE(test2));
+
+ // Common prefix and suffix.
+ const TestCaseMoves test3[] = {
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ abxde,
+ ARRAY_SIZE(abxde),
+ },
+ };
+ RunTestCase(test3, ARRAY_SIZE(test3));
+
+ // Subset of suffix.
+ const TestCaseMoves test4[] = {
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ de,
+ ARRAY_SIZE(de),
+ },
+ };
+ RunTestCase(test4, ARRAY_SIZE(test4));
+
+ // Subset of prefix.
+ const TestCaseMoves test5[] = {
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ ab,
+ ARRAY_SIZE(ab),
+ },
+ };
+ RunTestCase(test5, ARRAY_SIZE(test5));
+
+ // All moves (with duplicates).
+ const TestCaseMoves test6[] = {
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ abcde,
+ ARRAY_SIZE(abcde),
+ },
+ TestCaseMoves{
+ abcdx,
+ ARRAY_SIZE(abcdx),
+ },
+ TestCaseMoves{
+ xbcde,
+ ARRAY_SIZE(xbcde),
+ },
+ TestCaseMoves{
+ abxde,
+ ARRAY_SIZE(abxde),
+ },
+ TestCaseMoves{
+ ab,
+ ARRAY_SIZE(ab),
+ },
+ TestCaseMoves{
+ de,
+ ARRAY_SIZE(de),
+ },
+ TestCaseMoves{
+ de,
+ ARRAY_SIZE(de),
+ },
+ };
+ RunTestCase(test6, ARRAY_SIZE(test6));
+}
+
+} // namespace dart
diff --git a/runtime/vm/exceptions.cc b/runtime/vm/exceptions.cc
index 487b22a..d310c00 100644
--- a/runtime/vm/exceptions.cc
+++ b/runtime/vm/exceptions.cc
@@ -301,58 +301,12 @@
#if defined(DART_PRECOMPILED_RUNTIME) || defined(DART_PRECOMPILER)
void ReadCompressedCatchEntryMoves() {
- intptr_t pc_offset = pc_ - code_->PayloadStart();
- const TypedData& td = TypedData::Handle(code_->catch_entry_moves_maps());
- NoSafepointScope no_safepoint;
- ReadStream stream(static_cast<uint8_t*>(td.DataAddr(0)), td.Length());
+ const intptr_t pc_offset = pc_ - code_->PayloadStart();
+ const auto& td = TypedData::Handle(code_->catch_entry_moves_maps());
- intptr_t prefix_length = 0, suffix_length = 0, suffix_offset = 0;
- while (stream.PendingBytes() > 0) {
- intptr_t target_pc_offset = Reader::Read(&stream);
- prefix_length = Reader::Read(&stream);
- suffix_length = Reader::Read(&stream);
- suffix_offset = Reader::Read(&stream);
- if (pc_offset == target_pc_offset) {
- break;
- }
-
- // Skip the moves.
- for (intptr_t j = 0; j < prefix_length; j++) {
- CatchEntryMove::ReadFrom(&stream);
- }
- }
- ASSERT((stream.PendingBytes() > 0) || (prefix_length == 0));
-
- CatchEntryMoves* moves =
- CatchEntryMoves::Allocate(prefix_length + suffix_length);
- for (int j = 0; j < prefix_length; j++) {
- moves->At(j) = CatchEntryMove::ReadFrom(&stream);
- }
- ReadCompressedCatchEntryMovesSuffix(&stream, suffix_offset, suffix_length,
- moves, prefix_length);
- catch_entry_moves_ = moves;
+ CatchEntryMovesMapReader reader(td);
+ catch_entry_moves_ = reader.ReadMovesForPcOffset(pc_offset);
}
-
- void ReadCompressedCatchEntryMovesSuffix(ReadStream* stream,
- intptr_t offset,
- intptr_t length,
- CatchEntryMoves* moves,
- intptr_t moves_offset) {
- stream->SetPosition(offset);
- Reader::Read(stream); // skip pc_offset
- Reader::Read(stream); // skip variables
- intptr_t suffix_length = Reader::Read(stream);
- intptr_t suffix_offset = Reader::Read(stream);
- intptr_t to_read = length - suffix_length;
- for (int j = 0; j < to_read; j++) {
- moves->At(moves_offset + j) = CatchEntryMove::ReadFrom(stream);
- }
- if (suffix_length > 0) {
- ReadCompressedCatchEntryMovesSuffix(stream, suffix_offset, suffix_length,
- moves, moves_offset + to_read);
- }
- }
-
#else
void GetCatchEntryMovesFromDeopt(intptr_t num_vars, StackFrame* frame) {
Isolate* isolate = thread_->isolate();
@@ -415,6 +369,79 @@
}
#endif
+CatchEntryMoves* CatchEntryMovesMapReader::ReadMovesForPcOffset(
+ intptr_t pc_offset) {
+ NoSafepointScope no_safepoint;
+
+ ReadStream stream(static_cast<uint8_t*>(bytes_.DataAddr(0)), bytes_.Length());
+
+ intptr_t position = 0;
+ intptr_t length = 0;
+ FindEntryForPc(&stream, pc_offset, &position, &length);
+
+ return ReadCompressedCatchEntryMovesSuffix(&stream, position, length);
+}
+
+void CatchEntryMovesMapReader::FindEntryForPc(ReadStream* stream,
+ intptr_t pc_offset,
+ intptr_t* position,
+ intptr_t* length) {
+ using Reader = ReadStream::Raw<sizeof(intptr_t), intptr_t>;
+
+ while (stream->PendingBytes() > 0) {
+ const intptr_t stream_position = stream->Position();
+ const intptr_t target_pc_offset = Reader::Read(stream);
+ const intptr_t prefix_length = Reader::Read(stream);
+ const intptr_t suffix_length = Reader::Read(stream);
+ Reader::Read(stream); // Skip suffix_offset
+ if (pc_offset == target_pc_offset) {
+ *position = stream_position;
+ *length = prefix_length + suffix_length;
+ return;
+ }
+
+ // Skip the prefix moves.
+ for (intptr_t j = 0; j < prefix_length; j++) {
+ CatchEntryMove::ReadFrom(stream);
+ }
+ }
+
+ UNREACHABLE();
+}
+
+CatchEntryMoves* CatchEntryMovesMapReader::ReadCompressedCatchEntryMovesSuffix(
+ ReadStream* stream,
+ intptr_t offset,
+ intptr_t length) {
+ using Reader = ReadStream::Raw<sizeof(intptr_t), intptr_t>;
+
+ CatchEntryMoves* moves = CatchEntryMoves::Allocate(length);
+
+ intptr_t remaining_length = length;
+
+ intptr_t moves_offset = 0;
+ while (remaining_length > 0) {
+ stream->SetPosition(offset);
+ Reader::Read(stream); // skip pc_offset
+ Reader::Read(stream); // skip prefix length
+ const intptr_t suffix_length = Reader::Read(stream);
+ const intptr_t suffix_offset = Reader::Read(stream);
+ const intptr_t to_read = remaining_length - suffix_length;
+ if (to_read > 0) {
+ for (int j = 0; j < to_read; j++) {
+ // The prefix is written from the back.
+ moves->At(moves_offset + to_read - j - 1) =
+ CatchEntryMove::ReadFrom(stream);
+ }
+ remaining_length -= to_read;
+ moves_offset += to_read;
+ }
+ offset = suffix_offset;
+ }
+
+ return moves;
+}
+
static void FindErrorHandler(uword* handler_pc,
uword* handler_sp,
uword* handler_fp) {
diff --git a/runtime/vm/exceptions.h b/runtime/vm/exceptions.h
index d43201f..894f374 100644
--- a/runtime/vm/exceptions.h
+++ b/runtime/vm/exceptions.h
@@ -27,6 +27,7 @@
class WriteStream;
class String;
class Thread;
+class TypedData;
class Exceptions : AllStatic {
public:
@@ -190,7 +191,7 @@
(dest_slot() == src_slot());
}
- bool operator==(const CatchEntryMove& rhs) {
+ bool operator==(const CatchEntryMove& rhs) const {
return src_ == rhs.src_ && dest_and_kind_ == rhs.dest_and_kind_;
}
@@ -253,6 +254,30 @@
// Followed by CatchEntryMove[count_]
};
+// Used for reading the [CatchEntryMoves] from the compressed form.
+class CatchEntryMovesMapReader : public ValueObject {
+ public:
+ explicit CatchEntryMovesMapReader(const TypedData& bytes) : bytes_(bytes) {}
+
+ // The returned [CatchEntryMoves] must be freed by the caller via [free].
+ CatchEntryMoves* ReadMovesForPcOffset(intptr_t pc_offset);
+
+ private:
+ // Given the [pc_offset] this function will find the [position] at which to
+ // read the catch entries and the [length] of the catch entry moves array.
+ void FindEntryForPc(ReadStream* stream,
+ intptr_t pc_offset,
+ intptr_t* position,
+ intptr_t* length);
+
+ // Reads the [length] catch entry moves from [offset] in the [stream].
+ CatchEntryMoves* ReadCompressedCatchEntryMovesSuffix(ReadStream* stream,
+ intptr_t offset,
+ intptr_t length);
+
+ const TypedData& bytes_;
+};
+
// A simple reference counting wrapper for CatchEntryMoves.
//
// TODO(vegorov) switch this to intrusive reference counting.
diff --git a/runtime/vm/vm_sources.gni b/runtime/vm/vm_sources.gni
index 717b50c..4081d35 100644
--- a/runtime/vm/vm_sources.gni
+++ b/runtime/vm/vm_sources.gni
@@ -373,6 +373,7 @@
"bitfield_test.cc",
"bitmap_test.cc",
"boolfield_test.cc",
+ "catch_entry_moves_test.cc",
"class_finalizer_test.cc",
"code_descriptors_test.cc",
"code_patcher_arm64_test.cc",
