| # Suspendable Functions (`async`, `async*` and `sync*`) |
| |
| This document describes the implementation of _suspendable_ functions (functions with `async`, |
| `async*` or `sync*` modifier) in Dart VM. The execution of such functions can be suspended in |
| the middle at `await`/`yield`/`yield*` and resumed afterwards. |
| |
| When suspending a function, its local execution state (local variables and temporaries) is saved |
| and the control is returned to the caller of the suspended function. |
| When resuming a function, its local execution state is restored and execution continues within |
| the suspendable function from the point where it was suspended. |
| |
| In order to minimize code size, the implementation is built using a variety of _stubs_ - reusable |
| snippets of machine code generated by the VM/AOT. |
| The high-level Dart logic used to implement suspendable functions (such as managing |
| Futures/Streams/Iterators) is factored into helper Dart methods in core library. |
| |
| The rest of the document is organized as follows: first, general mechanisms for implementation of |
| suspendable functions are described. |
| After that, `async`, `async*` and `sync*` implementations are outlined using the general |
| mechanisms introduced before. |
| |
| # Building blocks common to all suspendable functions |
| |
| ## SuspendState objects |
| |
| SuspendState objects are allocated on the heap and encapsulate the saved state of a suspended |
| function. When suspending a function, its local frame (including local variables, spill slots |
| and expression stack) is copied from the stack to a SuspendState object on the heap. |
| When resuming a function, the frame is recreated and copied back from the SuspendState object |
| into the stack. |
| |
| SuspendState objects have variable size and keep frame in the "payload" following a few fixed |
| fields. |
| |
| In addition to a stack frame, SuspendState records a PC in the code of the suspended function |
| where execution was suspended and can be resumed. |
| The PC is also used by GC to find a stack map and scan through the pointers in the copied frame. |
| |
| SuspendState object also holds data and callbacks specific to a particular kind of suspendable |
| function. |
| |
| SuspendState object is allocated during the first suspension and can be reused for the subsequent |
| suspensions of the same function. |
| |
| For the declaration of SuspendState see [object.h](https://github.com/dart-lang/sdk/blob/main/runtime/vm/object.h#:~:text=class%20SuspendState), |
| UntaggedSuspendState is declared in [raw_object.h](https://github.com/dart-lang/sdk/blob/main/runtime/vm/raw_object.h#:~:text=class%20UntaggedSuspendState). |
| |
| There is also a corresponding Dart class `_SuspendState`, declared in [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart#:~:text=class%20_SuspendState). |
| It contains Dart methods which are used to customize implementation for a particular kind of |
| suspendable function. |
| |
| ## Frame of a suspendable function |
| |
| Suspendable functions are never inlined into other functions, so their local state is not mixed |
| with the state of their callers (but other functions may be inlined into them). |
| |
| In order to have a single contiguous region of memory to copy during suspend/resume, parameters of |
| suspendable functions are always copied into the local frame in the function prologue (see uses of |
| `Function::MakesCopyOfParameters()` predicate). |
| |
| In order to keep and reuse SuspendState object, each suspendable function has an artificial local |
| variable `:suspend_state` (see uses of `ParsedFunction::suspend_state_var()`), which is always |
| allocated at the fixed offset in frame. It occupies the first local variable slot |
| (`SuspendState::kSuspendStateVarIndex`) in case of unoptimized code or the first spill slot |
| in case of optimized code (see `FlowGraphAllocator::AllocateSpillSlotForSuspendState`). |
| The fixed location helps to find this variable in various stubs and runtime. |
| |
| ## Prologue and InitSuspendableFunction stub |
| |
| At the very beginning of a suspendable function `null` is stored into `:suspend_state` variable. |
| This guarantees that `:suspend_state` variable can be accessed any time by GC and exception |
| handling. |
| |
| After checking bounds of type arguments and types of arguments, suspendable functions call |
| InitSuspendableFunction stub. |
| |
| InitSuspendableFunction stub does the following: |
| |
| - It calls a static generic Dart method specific to a particular kind of suspendable function. |
| The argument of the stub is passed as type arguments to that method. |
| Dart method performs initialization specific to a particular kind of suspendable function |
| (for example, it creates `_Future<T>()` for async functions). |
| It returns the instance which is used as a function-specific data. |
| |
| - Stub puts the function-specific data to `:suspend_state` variable, where it can be found by |
| Suspend or Return stubs later. |
| |
| ## Suspend stub |
| |
| Suspend stub is called from a suspendable function when its execution should be suspended. |
| |
| Suspend stub does the following: |
| |
| - It inspects `:suspend_state` variable and checks if it contains an instance of SuspendState. |
| If it doesn't, then stub allocates a new instance with a payload sufficient to hold a frame of |
| the suspendable function. The newly allocated SuspendState is stored into `:suspend_state` |
| variable, and previous value of `:suspend_state` (coming from InitSuspendableFunction stub) is |
| saved to `SuspendState.function_data`. |
| |
| - In JIT mode, size of the frame may vary over time - expression stack depth varies during |
| execution of unoptimized code and frame size may change during deoptimization and OSR. |
| In AOT mode size of the stack frame stays the same. |
| So, if stub finds an existing SuspendState object in JIT mode, it also checks if its frame |
| payload has a sufficient size to hold a frame of the suspendable function. If it is not |
| large enough, suspend stub calls `AllocateSuspendState` runtime entry to allocate a larger |
| SuspendState object. The same runtime entry is called for slow path when allocating |
| SuspendState for the first time. |
| |
| - The return address from Suspend stub to the suspendable function is saved to `SuspendState.pc`. |
| It will be used to resume execution later. |
| |
| - The contents of the stack frame of the suspendable function between FP and SP is copied into |
| SuspendState. |
| |
| - Write barrier: if SuspendState object resides in the old generation, then |
| EnsureRememberedAndMarkingDeferred runtime entry is called. |
| |
| - If implementation of particular kind of suspendable function uses a customized Dart method |
| for the suspension, then that method is called. |
| Suspend stub supports passing one argument to the customization method. |
| The result of the method is returned back to the caller of the suspendable function - it's |
| the result of the suspendable function. |
| If such method is not used, then Suspend stub returns its argument (so suspendable function |
| could customize its return value). |
| |
| - On architectures other than x64/ia32, the frame of the suspendable function is removed and |
| stub returns directly to the caller of the suspendable function. |
| On x64/ia32, in order to maintain call/return balance and avoid performance penalty, |
| Suspend stub returns to the suspendable function which immediately returns to its caller. |
| |
| For more details see `StubCodeCompiler::GenerateSuspendStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateSuspendStub). |
| |
| ## Resume stub |
| |
| Resume stub is tail-called from `_SuspendState._resume` recognized method (which is called |
| from Dart helpers). It is used to resume execution of the previously suspended function. |
| |
| Resume stub does the following: |
| |
| - Allocates Dart frame on the stack, using `SuspendState.frame_size` to calculate its size. |
| |
| - Copies frame contents from SuspendState to the stack. |
| |
| - In JIT mode restores pool pointer (PP). |
| |
| - Checks for the following cases and calls ResumeFrame runtime entry if any of this is true: |
| + If resuming with an exception. |
| + In JIT mode, if Code of the suspendable function is disabled (deoptimized). |
| + In JIT mode, if there is a resumption breakpoint set by debugger. |
| |
| - Otherwise, jumps to `SuspendState.pc` to resume execution of the suspended function. |
| On x64/ia32 the continuation PC is adjusted by adding `SuspendStubABI::kResumePcDistance` |
| to skip over the epilogue which immediately follows the Suspend stub call to maintain |
| call/return balance. |
| |
| ResumeFrame runtime entry is called as if it was called from suspended function at continuation PC. |
| It handles all corner cases by throwing an exception, lazy deoptimizing or calling into |
| the debugger. |
| |
| For more details see `StubCodeCompiler::GenerateResumeStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateResumeStub) |
| and `ResumeFrame` in [runtime_entry.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/runtime_entry.cc#:~:text=ResumeFrame). |
| |
| ## Return stub |
| |
| Suspendable functions can use Return stub if they need to do something when execution of |
| a function ends (for example, complete a Future or close a Stream). In such a case, |
| suspendable function jumps to the Return stub instead of returning. |
| |
| Return stub does the following: |
| |
| - Removes the frame of the suspendable function (as if function epilogue was executed). |
| |
| - Calls a Dart method specific to a particular kind of suspendable function. |
| The customization method takes a value of `:suspend_state` variable and a return value |
| passed from the body of the suspendable function to the stub. |
| |
| - The value returned from the customization method is used as the result of |
| the suspendable function. |
| |
| For more details see `StubCodeCompiler::GenerateReturnStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateReturnStub). |
| |
| ## Exception handling and AsyncExceptionHandler stub |
| |
| Certain kinds of suspendable functions (async and async*) may need to catch all thrown exceptions |
| which are not caught within the function body, and perform certain actions (such as completing |
| the Future with an error). |
| |
| This is implemented by setting `has_async_handler` bit on `ExceptionHandlers` object. |
| When looking for an exception handler, runtime checks if this bit is set and uses |
| AsyncExceptionHandler stub as a handler (see `StackFrame::FindExceptionHandler`). |
| |
| AsyncExceptionHandler stub does the following: |
| |
| - It inspects the value of `:suspend_state` variable. If it is `null` (meaning the prologue has not |
| finished yet), the exception should not be handled and it is rethrown. |
| This makes it possible for argument type checks to throw an exception synchronously |
| instead of completing a Future with an error. |
| |
| - Otherwise, stub removes the frame of the suspendable function (as if function epilogue was |
| executed) and calls `_SuspendState._handleException` Dart method. AsyncExceptionHandler stub |
| does not use separate Dart helper methods for async and async* functions as exception handling is |
| not performance sensitive and currently uses only one bit in `ExceptionHandlers` to select |
| a stub handler for simplicity. |
| |
| - The value returned from `_SuspendState._handleException` is used as the result of the |
| suspendable function. |
| |
| For more details see `StubCodeCompiler::GenerateAsyncExceptionHandlerStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateAsyncExceptionHandlerStub). |
| |
| ## IL instructions |
| |
| When compiling suspendable functions, the following IL instructions are used: |
| |
| - `Call1ArgStub` instruction is used to call one-argument stubs such as InitSuspendableFunction. |
| |
| - `Suspend` instruction is used to call Suspend stub. After calling Suspend stub, |
| on x64/ia32 it also generates an epilogue right after the stub, in order to |
| return to the caller after suspending without disrupting call/return balance. |
| Due to this extra epilogue following the Suspend stub call, the resumption PC is |
| not the same as the return address of the Suspend stub. So `Suspend` instruction |
| uses 2 distinct deopt ids for the Suspend stub call and resumption PC. |
| |
| - `Return` instruction jumps to a Return stub instead of returning for certain kinds |
| of suspendable functions (async and async*). |
| |
| # Combining all pieces together |
| |
| ## Async functions |
| |
| See [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart) for the corresponding Dart source code. |
| |
| Async functions use the following customized stubs: |
| |
| ### InitAsync stub |
| |
| InitAsync = InitSuspendableFunction stub which calls `_SuspendState._initAsync`. |
| |
| `_SuspendState._initAsync` creates a `_Future<T>` instance which is used as the result of |
| the async function. This `_Future<T>` instance is kept in `:suspend_state` variable until |
| `_SuspendState` instance is created during the first `await`, and then kept in |
| `_SuspendState._functionData`. This instance is returned from `_SuspendState._await`, |
| `_SuspendState._returnAsync`, `_SuspendState._returnAsyncNotFuture` and |
| `_SuspendState._handleException` methods to serve as the result of the async function. |
| |
| ### Await stub |
| |
| Await = Suspend stub which calls `_SuspendState._await`. It implements the `await` expression. |
| |
| `_SuspendState._await` allocates 'then' and 'error' callback closures when called for |
| the first time. These callback closures resume execution of the async function via Resume stub. |
| It is possible to create callbacks eagerly in the InitAsync stub, but there is a significant |
| fraction of async functions which don't have `await` at all, so creating callbacks lazily during |
| the first `await` makes those functions more efficient. |
| If an argument of `await` is a Future, then `_SuspendState._await` attaches 'then' and 'error' |
| callbacks to that Future. Otherwise it schedules a micro-task to continue execution of |
| the suspended function later. |
| |
| ### AwaitWithTypeCheck stub |
| |
| AwaitWithTypeCheck is a variant of Await stub which additionally passes type argument `T` |
| and calls `_SuspendState._awaitWithTypeCheck` in order to test if the value has a |
| correct `Future<T>` type before awaiting. |
| |
| This runtime check is needed to maintain soundness in case value is a Future of an |
| incompatible type, for example: |
| |
| ``` |
| final FutureOr<Object> f = Future<Object?>.value(null); |
| Object x = await f; // x == f, not null. |
| ``` |
| |
| ### ReturnAsync stub |
| |
| ReturnAsync stub = Return stub which calls `_SuspendState._returnAsync`. |
| It is used to implement `return` statement (either explicit or implicit when reaching |
| the end of function). |
| |
| `_SuspendState._returnAsync` completes `_Future<T>` which is used as the result of |
| the async function. |
| |
| ### ReturnAsyncNotFuture stub |
| |
| ReturnAsyncNotFuture stub = Return stub which calls `_SuspendState._returnAsyncNotFuture`. |
| |
| ReturnAsyncNotFuture is similar to ReturnAsync, but used when compiler can prove that |
| return value is not a Future. It bypasses the expensive `is Future` test. |
| |
| ### Execution flow in async functions |
| |
| The following diagram depicts how the control is passed in a typical async function: |
| |
| ``` |
| Caller Future<T> foo() async Stubs Dart _SuspendState methods |
| | |
| *-------------------> | |
| (prologue) -------------> InitAsync |
| | |
| *----------> _initAsync |
| (creates _Future<T>) |
| | <--------- |
| | <-----------------------* |
| | |
| | |
| (await) ----------------> AwaitAsync |
| | |
| *----------> _await |
| (setups resumption) |
| (returns _Future<T>) |
| | <--------- |
| | <---------------------------------------------* |
| |
| Awaited Future is completed |
| | |
| *------------------------------------------> Resume |
| | |
| (after await) <---------------* |
| | |
| | |
| (return) ---------------> ReturnAsync/ReturnAsyncNotFuture |
| | |
| *----------> _returnAsync/_returnAsyncNotFuture |
| (completes _Future<T>) |
| (returns _Future<T>) |
| | <--------- |
| | <---------------------------------------------* |
| ``` |
| |
| ## Async* functions |
| |
| See [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart) |
| for the corresponding Dart source code. |
| |
| Async* functions use the following customized stubs: |
| |
| ### InitAsyncStar stub |
| |
| InitAsyncStar = InitSuspendableFunction stub which calls `_SuspendState._initAsyncStar`. |
| |
| `_SuspendState._initAsyncStar` creates `_AsyncStarStreamController<T>` instance which is used |
| to control the Stream returned from the async* function. `_AsyncStarStreamController<T>` is kept |
| in `_SuspendState._functionData` (after the first suspension at the beginning of async* function). |
| |
| ## YieldAsyncStar stub and `yield`/`yield*` |
| |
| YieldAsyncStar = Suspend stub which calls `_SuspendState._yieldAsyncStar`. |
| |
| This stub is used to suspend async* function at the beginning (until listener is attached to |
| the Stream returned from async* function), and at `yield` / `yield*` statements. |
| |
| When `_SuspendState._yieldAsyncStar` is called at the beginning of async* function it creates |
| a callback closure to resume body of the async* function (via Resume stub), creates and |
| returns `Stream`. |
| |
| `yield` / `yield*` statements are implemented in the following way: |
| |
| ``` |
| _AsyncStarStreamController controller = :suspend_state._functionData; |
| if (controller.add/addStream(<expr>)) { |
| return; |
| } |
| if (YieldAsyncStar()) { |
| return; |
| } |
| ``` |
| |
| `_AsyncStarStreamController.add`, `_AsyncStarStreamController.addStream` and YieldAsyncStar stub |
| can return `true` to indicate that Stream doesn't have a listener anymore and execution of |
| async* function should end. |
| |
| Note that YieldAsyncStar stub returns a value passed to a Resume stub when resuming async* |
| function, so the 2nd hasListeners check happens right before the async* function is resumed. |
| |
| See `StreamingFlowGraphBuilder::BuildYieldStatement` for more details about `yield` / `yield*`. |
| |
| ### Await stub |
| |
| Async* functions use the same Await stub which is used by async functions. |
| |
| ### ReturnAsyncStar stub |
| |
| ReturnAsyncStar stub = Return stub which calls `_SuspendState._returnAsyncStar`. |
| |
| `_SuspendState._returnAsyncStar` closes the Stream. |
| |
| ### Execution flow in async* functions |
| |
| The following diagram depicts how the control is passed in a typical async* function: |
| |
| ``` |
| Caller Stream<T> foo() async* Stubs Dart helper methods |
| | |
| *-------------------> | |
| (prologue) -------------> InitAsyncStar |
| | |
| *----------> _SuspendState._initAsyncStar |
| (creates _AsyncStarStreamController<T>) |
| | <--------- |
| | <-----------------------* |
| * ------------------> YieldAsyncStar |
| | |
| *----------> _SuspendState._yieldAsyncStar |
| (setups resumption) |
| (returns _AsyncStarStreamController.stream) |
| | <--------- |
| | <---------------------------------------------* |
| |
| Stream is listened |
| | |
| *------------------------------------------> Resume |
| | |
| (after prologue) <--------------* |
| | |
| | |
| (yield) --------------------------------> _AsyncStarStreamController.add |
| (adds value to Stream) |
| (checks if there are listeners) |
| | <----------------------------------- |
| * ------------------> YieldAsyncStar |
| | |
| *----------> _SuspendState._yieldAsyncStar |
| | <--------- |
| | <---------------------------------------------* |
| |
| Micro-task to run async* body |
| | |
| *----------------------------------------------------------> _AsyncStarStreamController.runBody |
| (checks if there are listeners) |
| Resume <------- |
| | |
| (after yield) <---------------* |
| | |
| | |
| (return) ---------------> ReturnAsyncStar |
| | |
| *----------> _SuspendState._returnAsyncStar |
| (closes _AsyncStarStreamController) |
| | <--------- |
| | <---------------------------------------------* |
| ``` |
| |
| ## Sync* functions |
| |
| See [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart) |
| for the corresponding Dart source code. |
| |
| Sync* functions use the following customized stubs: |
| |
| ### InitSyncStar stub |
| |
| InitSyncStar = InitSuspendableFunction stub which calls `_SuspendState._initSyncStar`. |
| |
| `_SuspendState._initSyncStar` creates a `_SyncStarIterable<T>` instance which is returned |
| from sync* function. |
| |
| ### SuspendSyncStarAtStart stub |
| |
| SuspendSyncStarAtStart = Suspend stub which calls `_SuspendState._suspendSyncStarAtStart`. |
| |
| This stub is used to suspend execution of sync* at the beginning. It is called after |
| InitSyncStar in the sync* function prologue. The body of sync* function doesn't run |
| until Iterator is not obtained from Iterable (`_SyncStarIterable<T>`) which is returned from |
| the sync* function. |
| |
| ### CloneSuspendState stub |
| |
| This stub creates a copy of SuspendState object. It is used to clone state of sync* |
| function (suspended at the beginning) for each Iterator instance obtained from |
| Iterable. |
| |
| See `StubCodeCompiler::GenerateCloneSuspendStateStub`. |
| |
| ### SuspendSyncStarAtYield stub and `yield`/`yield*` |
| |
| SuspendSyncStarAtYield = Suspend stub which doesn't call helper Dart methods. |
| |
| SuspendSyncStarAtYield is used to implement `yield` / `yield*` statements in sync* functions. |
| |
| `yield` / `yield*` statements are implemented in the following way: |
| |
| ``` |
| _SyncStarIterator iterator = :suspend_state._functionData; |
| |
| iterator._current = <expr>; // yield <expr> |
| OR |
| iterator._yieldStarIterable = <expr>; // yield* <expr> |
| |
| SuspendSyncStarAtYield(true); |
| ``` |
| |
| See `StreamingFlowGraphBuilder::BuildYieldStatement` for more details about `yield` / `yield*`. |
| |
| The value passed to SuspendSyncStarAtYield is returned back from the invocation of |
| Resume stub. `true` indicates that iteration can continue. |
| |
| ### Returning from sync* functions. |
| |
| Sync* function do not use Return stubs. Instead, return statements are rewritten to return `false` |
| in order to indicate that iteration is finished. |
| |
| ### Execution flow in sync* functions |
| |
| The following diagram depicts how the control is passed in a typical sync* function: |
| |
| ``` |
| Caller Iterable<T> foo() sync* Stubs Dart helpers |
| | |
| *-------------------> | |
| (prologue) -------------> InitSyncStar |
| | |
| *----------> _SuspendState._initSyncStar |
| (creates _SyncStarIterable<T>) |
| | <--------- |
| | <-----------------------* |
| * ------------------> SuspendSyncStarAtStart |
| | |
| *----------> _SuspendState._suspendSyncStarAtStart |
| (remembers _SuspendState at start) |
| (returns _SyncStarIterable<T>) |
| | <--------- |
| | <---------------------------------------------* |
| |
| Iterable.iterator is called |
| | |
| *----------------------------------------------------------> _SyncStarIterable<T>.iterator |
| (creates _SyncStarIterator<T>) |
| | |
| CloneSuspendState <-------* |
| (makes a copy of _SuspendState at start) |
| | |
| *-----------> | |
| | <------------------------------------------------------- (returns _SyncStarIterator<T>) |
| |
| Iterator.moveNext is called |
| | |
| *----------------------------------------------------------> _SyncStarIterator<T>.moveNext |
| (iterates over the cached yield* iterator, if any) |
| (resumes sync* body to get the next element) |
| Resume <------- |
| | |
| (after prologue) <--------------* |
| | |
| | |
| (yield) ---------------> SuspendSyncStarAtYield(true) |
| | |
| *----------> |
| (the next element is cached in _SyncStarIterator<T>._current) |
| (returns true indicating that the next element is available) |
| | <---------------------------------------------------------- |
| |
| Iterator.moveNext is called |
| | |
| *----------------------------------------------------------> _SyncStarIterator<T>.moveNext |
| (iterates over the cached yield* iterator, if any) |
| (resumes sync* body to get the next element) |
| Resume <------- |
| | |
| (after yield) <-----------------* |
| | |
| | |
| (return false) -----------------------------> |
| (returns false indicating that iteration is finished) |
| | <---------------------------------------------------------- |
| ``` |