1// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/relocation.h"
6
7#include "vm/code_patcher.h"
8#include "vm/heap/pages.h"
9#include "vm/instructions.h"
10#include "vm/object_store.h"
11#include "vm/stub_code.h"
12
13namespace dart {
14
15#if defined(DART_PRECOMPILER) && !defined(TARGET_ARCH_IA32)
16
17// Only for testing.
18DEFINE_FLAG(bool,
19 always_generate_trampolines_for_testing,
20 false,
21 "Generate always trampolines (for testing purposes).");
22
23const intptr_t kTrampolineSize =
24 Utils::RoundUp(PcRelativeTrampolineJumpPattern::kLengthInBytes,
25 ImageWriter::kBareInstructionsAlignment);
26
27CodeRelocator::CodeRelocator(Thread* thread,
28 GrowableArray<CodePtr>* code_objects,
29 GrowableArray<ImageWriterCommand>* commands)
30 : StackResource(thread),
31 thread_(thread),
32 code_objects_(code_objects),
33 commands_(commands),
34 kind_type_and_offset_(Smi::Handle(thread->zone())),
35 target_(Object::Handle(thread->zone())),
36 destination_(Code::Handle(thread->zone())) {}
37
38void CodeRelocator::Relocate(bool is_vm_isolate) {
39 Zone* zone = Thread::Current()->zone();
40 auto& current_caller = Code::Handle(zone);
41 auto& call_targets = Array::Handle(zone);
42
43 // Do one linear pass over all code objects and determine:
44 //
45 // * the maximum instruction size
46 // * the maximum number of calls
47 // * the maximum offset into a target instruction
48 //
49 FindInstructionAndCallLimits();
50
51 // Emit all instructions and do relocations on the way.
52 for (intptr_t i = 0; i < code_objects_->length(); ++i) {
53 current_caller = (*code_objects_)[i];
54
55 const intptr_t code_text_offset = next_text_offset_;
56 if (!AddInstructionsToText(current_caller.raw())) {
57 continue;
58 }
59
60 call_targets = current_caller.static_calls_target_table();
61 ScanCallTargets(current_caller, call_targets, code_text_offset);
62
63 // Any unresolved calls to this instruction can be fixed now.
64 ResolveUnresolvedCallsTargeting(current_caller.instructions());
65
66 // If we have forward/backwards calls which are almost out-of-range, we'll
67 // create trampolines now.
68 BuildTrampolinesForAlmostOutOfRangeCalls();
69 }
70
71 // We're guaranteed to have all calls resolved, since
72 // * backwards calls are resolved eagerly
73 // * forward calls are resolved once the target is written
74 ASSERT(all_unresolved_calls_.IsEmpty());
75 ASSERT(unresolved_calls_by_destination_.IsEmpty());
76
77 // Any trampolines we created must be patched with the right offsets.
78 auto it = trampolines_by_destination_.GetIterator();
79 while (true) {
80 auto entry = it.Next();
81 if (entry == nullptr) break;
82
83 UnresolvedTrampolineList* trampoline_list = entry->value;
84 while (!trampoline_list->IsEmpty()) {
85 auto unresolved_trampoline = trampoline_list->RemoveFirst();
86 ResolveTrampoline(unresolved_trampoline);
87 delete unresolved_trampoline;
88 }
89 delete trampoline_list;
90 }
91 trampolines_by_destination_.Clear();
92
93 // We're done now, so we clear out the targets tables.
94 auto& caller = Code::Handle(zone);
95 if (!is_vm_isolate) {
96 for (intptr_t i = 0; i < code_objects_->length(); ++i) {
97 caller = (*code_objects_)[i];
98 caller.set_static_calls_target_table(Array::empty_array());
99 }
100 }
101}
102
103void CodeRelocator::FindInstructionAndCallLimits() {
104 auto zone = thread_->zone();
105 auto& current_caller = Code::Handle(zone);
106 auto& call_targets = Array::Handle(zone);
107
108 for (intptr_t i = 0; i < code_objects_->length(); ++i) {
109 current_caller = (*code_objects_)[i];
110 const intptr_t size =
111 ImageWriter::SizeInSnapshot(current_caller.instructions());
112 if (size > max_instructions_size_) {
113 max_instructions_size_ = size;
114 }
115
116 call_targets = current_caller.static_calls_target_table();
117 if (!call_targets.IsNull()) {
118 intptr_t num_calls = 0;
119 StaticCallsTable calls(call_targets);
120 for (auto call : calls) {
121 kind_type_and_offset_ = call.Get<Code::kSCallTableKindAndOffset>();
122 const auto kind =
123 Code::KindField::decode(kind_type_and_offset_.Value());
124 const auto return_pc_offset =
125 Code::OffsetField::decode(kind_type_and_offset_.Value());
126 const auto call_entry_point =
127 Code::EntryPointField::decode(kind_type_and_offset_.Value());
128
129 if (kind == Code::kCallViaCode) {
130 continue;
131 }
132
133 destination_ = GetTarget(call);
134 num_calls++;
135
136 // A call site can decide to jump not to the beginning of a function but
137 // rather jump into it at a certain (positive) offset.
138 int32_t offset_into_target = 0;
139 if (kind == Code::kPcRelativeCall || kind == Code::kPcRelativeTTSCall) {
140 const intptr_t call_instruction_offset =
141 return_pc_offset - PcRelativeCallPattern::kLengthInBytes;
142 PcRelativeCallPattern call(current_caller.PayloadStart() +
143 call_instruction_offset);
144 ASSERT(call.IsValid());
145 offset_into_target = call.distance();
146 } else {
147 ASSERT(kind == Code::kPcRelativeTailCall);
148 const intptr_t call_instruction_offset =
149 return_pc_offset - PcRelativeTailCallPattern::kLengthInBytes;
150 PcRelativeTailCallPattern call(current_caller.PayloadStart() +
151 call_instruction_offset);
152 ASSERT(call.IsValid());
153 offset_into_target = call.distance();
154 }
155
156 const uword destination_payload = destination_.PayloadStart();
157 const uword entry_point = call_entry_point == Code::kUncheckedEntry
158 ? destination_.UncheckedEntryPoint()
159 : destination_.EntryPoint();
160
161 offset_into_target += (entry_point - destination_payload);
162
163 if (offset_into_target > max_offset_into_target_) {
164 max_offset_into_target_ = offset_into_target;
165 }
166 }
167
168 if (num_calls > max_calls_) {
169 max_calls_ = num_calls;
170 }
171 }
172 }
173}
174
175bool CodeRelocator::AddInstructionsToText(CodePtr code) {
176 InstructionsPtr instructions = Code::InstructionsOf(code);
177
178 // If two [Code] objects point to the same [Instructions] object, we'll just
179 // use the first one (they are equivalent for all practical purposes).
180 if (text_offsets_.HasKey(instructions)) {
181 return false;
182 }
183 text_offsets_.Insert({instructions, next_text_offset_});
184 commands_->Add(ImageWriterCommand(next_text_offset_, code));
185 next_text_offset_ += ImageWriter::SizeInSnapshot(instructions);
186
187 return true;
188}
189
190UnresolvedTrampoline* CodeRelocator::FindTrampolineFor(
191 UnresolvedCall* unresolved_call) {
192 auto destination = Code::InstructionsOf(unresolved_call->callee);
193 auto entry = trampolines_by_destination_.Lookup(destination);
194 if (entry != nullptr) {
195 UnresolvedTrampolineList* trampolines = entry->value;
196 ASSERT(!trampolines->IsEmpty());
197
198 // For the destination of [unresolved_call] we might have multiple
199 // trampolines. The trampolines are sorted according to insertion order,
200 // which guarantees increasing text_offset's. So we go from the back of the
201 // list as long as we have trampolines that are in-range and then check
202 // whether the target offset matches.
203 auto it = trampolines->End();
204 --it;
205 do {
206 UnresolvedTrampoline* trampoline = *it;
207 if (!IsTargetInRangeFor(unresolved_call, trampoline->text_offset)) {
208 break;
209 }
210 if (trampoline->offset_into_target ==
211 unresolved_call->offset_into_target) {
212 return trampoline;
213 }
214 --it;
215 } while (it != trampolines->Begin());
216 }
217 return nullptr;
218}
219
220void CodeRelocator::AddTrampolineToText(InstructionsPtr destination,
221 uint8_t* trampoline_bytes,
222 intptr_t trampoline_length) {
223 commands_->Add(ImageWriterCommand(next_text_offset_, trampoline_bytes,
224 trampoline_length));
225 next_text_offset_ += trampoline_length;
226}
227
228void CodeRelocator::ScanCallTargets(const Code& code,
229 const Array& call_targets,
230 intptr_t code_text_offset) {
231 if (call_targets.IsNull()) {
232 return;
233 }
234 StaticCallsTable calls(call_targets);
235 for (auto call : calls) {
236 kind_type_and_offset_ = call.Get<Code::kSCallTableKindAndOffset>();
237 const auto kind = Code::KindField::decode(kind_type_and_offset_.Value());
238 const auto return_pc_offset =
239 Code::OffsetField::decode(kind_type_and_offset_.Value());
240 const auto call_entry_point =
241 Code::EntryPointField::decode(kind_type_and_offset_.Value());
242
243 if (kind == Code::kCallViaCode) {
244 continue;
245 }
246
247 destination_ = GetTarget(call);
248
249 // A call site can decide to jump not to the beginning of a function but
250 // rather jump into it at a certain offset.
251 int32_t offset_into_target = 0;
252 bool is_tail_call;
253 intptr_t call_instruction_offset;
254 if (kind == Code::kPcRelativeCall || kind == Code::kPcRelativeTTSCall) {
255 call_instruction_offset =
256 return_pc_offset - PcRelativeCallPattern::kLengthInBytes;
257 PcRelativeCallPattern call(code.PayloadStart() + call_instruction_offset);
258 ASSERT(call.IsValid());
259 offset_into_target = call.distance();
260 is_tail_call = false;
261 } else {
262 ASSERT(kind == Code::kPcRelativeTailCall);
263 call_instruction_offset =
264 return_pc_offset - PcRelativeTailCallPattern::kLengthInBytes;
265 PcRelativeTailCallPattern call(code.PayloadStart() +
266 call_instruction_offset);
267 ASSERT(call.IsValid());
268 offset_into_target = call.distance();
269 is_tail_call = true;
270 }
271
272 const uword destination_payload = destination_.PayloadStart();
273 const uword entry_point = call_entry_point == Code::kUncheckedEntry
274 ? destination_.UncheckedEntryPoint()
275 : destination_.EntryPoint();
276
277 offset_into_target += (entry_point - destination_payload);
278
279 const intptr_t text_offset =
280 code_text_offset + AdjustPayloadOffset(call_instruction_offset);
281
282 UnresolvedCall unresolved_call(code.raw(), call_instruction_offset,
283 text_offset, destination_.raw(),
284 offset_into_target, is_tail_call);
285 if (!TryResolveBackwardsCall(&unresolved_call)) {
286 EnqueueUnresolvedCall(new UnresolvedCall(unresolved_call));
287 }
288 }
289}
290
291void CodeRelocator::EnqueueUnresolvedCall(UnresolvedCall* unresolved_call) {
292 // Add it to the min-heap by .text offset.
293 all_unresolved_calls_.Append(unresolved_call);
294
295 // Add it to callers of destination.
296 InstructionsPtr destination = Code::InstructionsOf(unresolved_call->callee);
297 if (!unresolved_calls_by_destination_.HasKey(destination)) {
298 unresolved_calls_by_destination_.Insert(
299 {destination, new SameDestinationUnresolvedCallsList()});
300 }
301 unresolved_calls_by_destination_.LookupValue(destination)
302 ->Append(unresolved_call);
303}
304
305void CodeRelocator::EnqueueUnresolvedTrampoline(
306 UnresolvedTrampoline* unresolved_trampoline) {
307 auto destination = Code::InstructionsOf(unresolved_trampoline->callee);
308 auto entry = trampolines_by_destination_.Lookup(destination);
309
310 UnresolvedTrampolineList* trampolines = nullptr;
311 if (entry == nullptr) {
312 trampolines = new UnresolvedTrampolineList();
313 trampolines_by_destination_.Insert({destination, trampolines});
314 } else {
315 trampolines = entry->value;
316 }
317 trampolines->Append(unresolved_trampoline);
318}
319
320bool CodeRelocator::TryResolveBackwardsCall(UnresolvedCall* unresolved_call) {
321 auto callee = Code::InstructionsOf(unresolved_call->callee);
322 auto map_entry = text_offsets_.Lookup(callee);
323 if (map_entry == nullptr) return false;
324
325 ResolveCall(unresolved_call);
326 return true;
327}
328
329void CodeRelocator::ResolveUnresolvedCallsTargeting(
330 const InstructionsPtr instructions) {
331 if (unresolved_calls_by_destination_.HasKey(instructions)) {
332 SameDestinationUnresolvedCallsList* calls =
333 unresolved_calls_by_destination_.LookupValue(instructions);
334 auto it = calls->Begin();
335 while (it != calls->End()) {
336 UnresolvedCall* unresolved_call = *it;
337 ++it;
338 ASSERT(Code::InstructionsOf(unresolved_call->callee) == instructions);
339 ResolveCall(unresolved_call);
340
341 // Remove the call from both lists.
342 calls->Remove(unresolved_call);
343 all_unresolved_calls_.Remove(unresolved_call);
344
345 delete unresolved_call;
346 }
347 ASSERT(calls->IsEmpty());
348 delete calls;
349 bool ok = unresolved_calls_by_destination_.Remove(instructions);
350 ASSERT(ok);
351 }
352}
353
354void CodeRelocator::ResolveCall(UnresolvedCall* unresolved_call) {
355 const intptr_t destination_text =
356 FindDestinationInText(Code::InstructionsOf(unresolved_call->callee),
357 unresolved_call->offset_into_target);
358
359 ResolveCallToDestination(unresolved_call, destination_text);
360}
361
362void CodeRelocator::ResolveCallToDestination(UnresolvedCall* unresolved_call,
363 intptr_t destination_text) {
364 const intptr_t call_text_offset = unresolved_call->text_offset;
365 const intptr_t call_offset = unresolved_call->call_offset;
366
367 const int32_t distance = destination_text - call_text_offset;
368 {
369 auto const caller = unresolved_call->caller;
370 uword addr = Code::PayloadStartOf(caller) + call_offset;
371 if (FLAG_write_protect_code) {
372 addr -= OldPage::Of(Code::InstructionsOf(caller))->AliasOffset();
373 }
374 if (unresolved_call->is_tail_call) {
375 PcRelativeTailCallPattern call(addr);
376 ASSERT(call.IsValid());
377 call.set_distance(static_cast<int32_t>(distance));
378 ASSERT(call.distance() == distance);
379 } else {
380 PcRelativeCallPattern call(addr);
381 ASSERT(call.IsValid());
382 call.set_distance(static_cast<int32_t>(distance));
383 ASSERT(call.distance() == distance);
384 }
385 }
386
387 unresolved_call->caller = nullptr;
388 unresolved_call->callee = nullptr;
389}
390
391void CodeRelocator::ResolveTrampoline(
392 UnresolvedTrampoline* unresolved_trampoline) {
393 const intptr_t trampoline_text_offset = unresolved_trampoline->text_offset;
394 const uword trampoline_start =
395 reinterpret_cast<uword>(unresolved_trampoline->trampoline_bytes);
396
397 auto callee = Code::InstructionsOf(unresolved_trampoline->callee);
398 auto destination_text =
399 FindDestinationInText(callee, unresolved_trampoline->offset_into_target);
400 const int32_t distance = destination_text - trampoline_text_offset;
401
402 PcRelativeTrampolineJumpPattern pattern(trampoline_start);
403 pattern.Initialize();
404 pattern.set_distance(distance);
405 ASSERT(pattern.distance() == distance);
406}
407
408bool CodeRelocator::IsTargetInRangeFor(UnresolvedCall* unresolved_call,
409 intptr_t target_text_offset) {
410 const auto forward_distance =
411 target_text_offset - unresolved_call->text_offset;
412 if (unresolved_call->is_tail_call) {
413 return PcRelativeTailCallPattern::kLowerCallingRange < forward_distance &&
414 forward_distance < PcRelativeTailCallPattern::kUpperCallingRange;
415 } else {
416 return PcRelativeCallPattern::kLowerCallingRange < forward_distance &&
417 forward_distance < PcRelativeCallPattern::kUpperCallingRange;
418 }
419}
420
421CodePtr CodeRelocator::GetTarget(const StaticCallsTableEntry& call) {
422 // The precompiler should have already replaced all function entries
423 // with code entries.
424 ASSERT(call.Get<Code::kSCallTableFunctionTarget>() == Function::null());
425
426 target_ = call.Get<Code::kSCallTableCodeOrTypeTarget>();
427 if (target_.IsAbstractType()) {
428 target_ = AbstractType::Cast(target_).type_test_stub();
429 destination_ = Code::Cast(target_).raw();
430
431 // The AssertAssignableInstr will emit pc-relative calls to the TTS iff
432 // dst_type is instantiated. If we happened to not install an optimized
433 // TTS but rather a default one, it will live in the vm-isolate (to
434 // which we cannot make pc-relative calls).
435 // Though we have "equivalent" isolate-specific stubs we can use as
436 // targets instead.
437 //
438 // (We could make the AOT compiler install isolate-specific stubs
439 // into the types directly, but that does not work for types which
440 // live in the "vm-isolate" - such as `Type::dynamic_type()`).
441 if (destination_.InVMIsolateHeap()) {
442 auto object_store = thread_->isolate()->object_store();
443 if (destination_.raw() == StubCode::DefaultTypeTest().raw()) {
444 destination_ = object_store->default_tts_stub();
445 } else if (destination_.raw() ==
446 StubCode::DefaultNullableTypeTest().raw()) {
447 destination_ = object_store->default_nullable_tts_stub();
448 } else if (destination_.raw() == StubCode::TopTypeTypeTest().raw()) {
449 destination_ = object_store->top_type_tts_stub();
450 } else if (destination_.raw() == StubCode::UnreachableTypeTest().raw()) {
451 destination_ = object_store->unreachable_tts_stub();
452 } else if (destination_.raw() == StubCode::SlowTypeTest().raw()) {
453 destination_ = object_store->slow_tts_stub();
454 } else {
455 UNREACHABLE();
456 }
457 }
458 } else {
459 ASSERT(target_.IsCode());
460 destination_ = Code::Cast(target_).raw();
461 }
462 ASSERT(!destination_.InVMIsolateHeap());
463 return destination_.raw();
464}
465
466void CodeRelocator::BuildTrampolinesForAlmostOutOfRangeCalls() {
467 while (!all_unresolved_calls_.IsEmpty()) {
468 UnresolvedCall* unresolved_call = all_unresolved_calls_.First();
469
470 // If we can emit another instructions object without causing the unresolved
471 // forward calls to become out-of-range, we'll not resolve it yet (maybe the
472 // target function will come very soon and we don't need a trampoline at
473 // all).
474 const intptr_t future_boundary =
475 next_text_offset_ + max_instructions_size_ +
476 kTrampolineSize *
477 (unresolved_calls_by_destination_.Length() + max_calls_);
478 if (IsTargetInRangeFor(unresolved_call, future_boundary) &&
479 !FLAG_always_generate_trampolines_for_testing) {
480 break;
481 }
482
483 // We have a "critical" [unresolved_call] we have to resolve. If an
484 // existing trampoline is in range, we use that otherwise we create a new
485 // trampoline.
486
487 // In the worst case we'll make a new trampoline here, in which case the
488 // current text offset must be in range for the "critical"
489 // [unresolved_call].
490 ASSERT(IsTargetInRangeFor(unresolved_call, next_text_offset_));
491
492 // See if there is already a trampoline we could use.
493 intptr_t trampoline_text_offset = -1;
494 auto callee = Code::InstructionsOf(unresolved_call->callee);
495
496 if (!FLAG_always_generate_trampolines_for_testing) {
497 auto old_trampoline_entry = FindTrampolineFor(unresolved_call);
498 if (old_trampoline_entry != nullptr) {
499 trampoline_text_offset = old_trampoline_entry->text_offset;
500 }
501 }
502
503 // If there is no trampoline yet, we'll create a new one.
504 if (trampoline_text_offset == -1) {
505 // The ownership of the trampoline bytes will be transferred to the
506 // [ImageWriter], which will eventually write out the bytes and delete the
507 // buffer.
508 auto trampoline_bytes = new uint8_t[kTrampolineSize];
509 ASSERT((kTrampolineSize % compiler::target::kWordSize) == 0);
510 for (uint8_t* cur = trampoline_bytes;
511 cur < trampoline_bytes + kTrampolineSize;
512 cur += compiler::target::kWordSize) {
513 *reinterpret_cast<compiler::target::uword*>(cur) =
514 kBreakInstructionFiller;
515 }
516 auto unresolved_trampoline = new UnresolvedTrampoline{
517 unresolved_call->callee,
518 unresolved_call->offset_into_target,
519 trampoline_bytes,
520 next_text_offset_,
521 };
522 AddTrampolineToText(callee, trampoline_bytes, kTrampolineSize);
523 EnqueueUnresolvedTrampoline(unresolved_trampoline);
524 trampoline_text_offset = unresolved_trampoline->text_offset;
525 }
526
527 // Let the unresolved call to [destination] jump to the trampoline
528 // instead.
529 auto destination = Code::InstructionsOf(unresolved_call->callee);
530 ResolveCallToDestination(unresolved_call, trampoline_text_offset);
531
532 // Remove this unresolved call from the global list and the per-destination
533 // list.
534 auto calls = unresolved_calls_by_destination_.LookupValue(destination);
535 calls->Remove(unresolved_call);
536 all_unresolved_calls_.Remove(unresolved_call);
537 delete unresolved_call;
538
539 // If this destination has no longer any unresolved calls, remove it.
540 if (calls->IsEmpty()) {
541 unresolved_calls_by_destination_.Remove(destination);
542 delete calls;
543 }
544 }
545}
546
547intptr_t CodeRelocator::FindDestinationInText(const InstructionsPtr destination,
548 intptr_t offset_into_target) {
549 auto const destination_offset = text_offsets_.LookupValue(destination);
550 return destination_offset + AdjustPayloadOffset(offset_into_target);
551}
552
553intptr_t CodeRelocator::AdjustPayloadOffset(intptr_t payload_offset) {
554 if (FLAG_precompiled_mode && FLAG_use_bare_instructions) {
555 return payload_offset;
556 }
557 return compiler::target::Instructions::HeaderSize() + payload_offset;
558}
559
560#endif // defined(DART_PRECOMPILER) && !defined(TARGET_ARCH_IA32)
561
562} // namespace dart
563