A safer API for V4

[ConorWilliams]

The problems

With the V3 API, the exception-safe Fibonacci looks like:

auto fib = [](auto fib, int n) -> task<int> { 
  
  if (n < 2) {
    co_return n;
  }

  int a, b;

  co_await fork[&a, fib](n - 1); 

  try {
      co_await call[&b, fib](n - 2);
  } catch (...){
      fib.stash_exception();
  }
    
  co_await join;                    

  co_return a + b;                     
};

Key things I want to improve in future versions of libfork are:

• Remove the requirement of templates in definition (and consequently the first argument).
• Support shallow cancellation.
• Enforce join.
• Clean up exception handling.
• Nested scopes in the same function.
• API change fork[&a, fib](n - 1) -> fork(&a, fib, n - 1)
• If resume(...) requires a context then associate the call with a context!
• Move to a compiled library

Implications of some of these changes are discussed below.

Templates

This will require storing the root/call/fork information dynamically in the promise. This is expected to be a small runtime slowdown for big compile-time gains as well as removing the need for the first argument which will simplify the API. The first argument as a y-combinator is not required in C++23 as lambdas can be recursive.

We may expect runtime gains if the instruction cache can be better re-used.

Finally, this removes our opportunity to specify the return address type. Some flexibility could be returned with this API:

template<typename T, typename I = T *>
class task;

Exceptions and joining

Exceptions are unsafe because:

1. join can easily be missed on the exception path
2. The memory at the return address may be destructed in the case of exceptions

An example of (2):

int a;

// -- x --

co_await fork(a, fun);

throw "ooof";

If the continuation was stolen then the child task may write to the memory location that stored a after a has been destructed, this would be a big-bad for non-trivial types.

Solutions:

• Could allocate a on the heap and store a pointer.
• Could block unwinding at -- x -- via exception.
• Put fork in "safe" library function?

Ideal (language level):

int a, b;

async {
    
    fork[a, fib](n - 1);
    call(b, fib, n - 2);
    
} // <- Exceptions defered to here && implicit join

Scope based

Exploring solution 2, we could introduce a scope:

auto fib(int n) -> task<int> { 
  
  if (n < 2) {
    co_return n;
  }

  int a, b;

  auto scope = co_await scoped(); // scope is immovable

  co_await scope.fork(&a, fib, n - 1); // fork can be noexcept, stash in scope
  co_await scope.call(&b, fib, n - 2); // call can be noexcept, stash in scope
  
  co_await scope.join();
                   
  co_return a + b;                     
};

If the destructor of scope is called before a join we can issue a terminate, the compiler should be able to omit the check on the non-exceptional path. Furthermore the above can be macro'd:

#define ASYNC(scope) for(auto scope = co_await scoped(); scope.joined(); co_await scope.join())

and written:

auto fib(int n) -> task<int> { 
  
  if (n < 2) {
    co_return n;
  }

  int a, b;

  ASYNC(s) {
      co_await s.fork(&a, fib, n - 1);  
      co_await s.call(&b, fib, n - 2);  
  }

  co_return a + b;  

Alternatively, if we introduced a helper that stack allocated some return variables we could achieve full safety:

auto fib(int n) -> task<int> { 
  
  if (n < 2) {
    co_return n;
  }

  auto [a, b, scope] = co_await scoped<int, int>();    // Ensures ~scope() runs before ~a()

  co_await scope.fork(&a, fib, n - 1); 
  co_await scope.call(&b, fib, n - 2); 
  
  co_await scope.join();
                   
  co_return a + b;                     
};

Helping to prevent writing:

auto fib(int n) -> task<int> { 
  
  if (n < 2) {
    co_return n;
  }

   auto scope = co_await scoped();

  int a, b;

  co_await scope.fork(&a, fib, n - 1); 
  
  throw "this will casue UB";
  
  co_await scope.join();
                   
  co_return a + b;                     
};

Nesting scopes

Scopes would allow us to have fork-join regions inside fork-join regions:

auto nest(int n) -> task<> {

  int a, b

  ASYNC(s1) {
    co_await s1.fork(&a, fib, n - 1);  
    
    int c, d;

    ASYNC(s2) {
        co_await s2.fork(&c, fib, n - 2);  
        co_await s2.call(&c, fib, n - 3); 
    }

    co_await s1.call(&b, fib, c + d);  
  }

} 

Cancellation

With the scope based API each scope could be cancelled with APIs like:

auto scope = co_await scoped();

scope.cancel();

auto tok = scope.stop_token();

if (tok.stop_requested()){
    // handle stop case.
}

Implementing V4

In this section we use void* for all pointer-size types.

scope : immovable {
    
    void * stacklet;     // Thread-local written at make_scope().
    void * continuation; // Handle to enclosing coroutine.
   
    uintptr_t tagged; // Tagged ptr: 
                      //     0 -> OK 
                      //     1 -> Cancelled, 
                      //     _ -> Exception pointer, 
    
    uint16_t n_steal; // No atomic operations.
    uint16_t n_joins; // Atomic ops to decrement.
    
    ~scope() {
        if (n_steal != 0) {
            std::terminate();
        }
    }
}

Promise defined such that the synthesized frame looks like:

frame {
    void * __resume;  // Compiler gen - can't touch!
    void * __destroy; // ^
    
    void * ret;    // Return address (templated on T)

    union {
        void * scope // If fork/call
        void * root  // If root
    }
    
    uint8_t type; // Fork/Call/Root
    
    unspecified __frame; // Compiler gen - can't touch
}

A task handle would be a pointer to a scope.

Early testing

I have mocked up some of this API in the experimental branch, initial testing suggests serial performance is on par with the fully templated version.