Alternative cancellation and data escape mechanisms for transactions

What is cancellation?

In what follows, I will describe cancellation and data escape mechanisms for transactions as specified by the current draft specification and the changes summarized in N3589. These are supposed to replace the cancellation mechanisms in the current draft (i.e., the __transaction_cancel keyword and the cancel-and-throw functionality); they are compatible with the minimal exceptions proposal described in N3589. The data escape mechanisms allow transaction to communicate data out of cancelled transactions (i.e, the data escapes the transaction's atomicity). Also, whenever I refer to transactions, this always means atomic transactions, not the relaxed transaction variant.

The cancellation mechanisms described here are supposed to serve as a foundation for higher-level features that make use of cancellation, such as composable forms of error recovery or more focused kinds of speculative execution. They also try to provide cancellation with no language extensions or changes (besides a minor extension to the syntax of transaction statements); most of the functionality can be expressed as library features. Likewise, it can be implemented in just the TM-specific implementation parts.

Cancellation vs. exceptions

In a nutshell, I think that the best mental model of cancellation is to understand it as a local expression of a failure that does not necessarily specify a certain failure recovery or failure handling scheme. In short, the transactions gives up, and doesn't execute further. The part of the program that started the transaction is then responsible for ensuring forward progress: It can retry the transaction, choose another potential execution path, or fail. Note that a cancellation "failure" does not need to be something fatal; it can also be a component that just states that it does not think that it is worthwhile to continue execution (i.e., it fails to achieve its purpose). For example, with speculative execution, a transaction can execute as long as it thinks that this might be beneficial; if it assumes that another path might be more efficient, it can cancel itself, and the other path can then be tried to be executed.

In contrast, exceptions are an error propagation mechanism with very precise rules how the failure should be propagated, and which parts of the program get to handle the failure first. Catching an exception is a way to stop this propagation at a specific point in the program. Error handling schemes that align well with this kind of propagation also work well with exceptions, but handling/recovery schemes that do not have this call-chain-unwinding structure are harder to implement.

With exceptions, the program defines what happens when an exception is thrown (i.e., defines what destructors execute during unwinding), and the invariants that the program needs or establishes during unwinding are only known to the program. In particular, the extent to which programs roll back changes when handling exceptions can vary. Exceptions are sometimes used as means for non-local control flow, in which case rolling back all changes during unwinding is not the desired behavior. However, often it is desired to clean up after incompletely executed operations, so as to ensure invariants. Programming this cleanup code can be tedious, and it is less likely to be well-tested code.

Transactions and cancellation simplify such cleanup because of the atomicity guarantees that they give: when a transaction is canceled, all its operations get rolled back. However, this also shows that we can't simply replace exceptions in legacy code with cancellation because we do not know in general which program state is supposed to be rolled back. In turn, this also means that we cannot treat all exceptions in transactions as cancellation events; instead, we would need programmers to specify that this is safe and does not roll back more state than expected.

Similarly, we cannot easily express cancellation as exceptions because cancellation is supposed to stop execution immediately, whereas exceptions are supposed to propagate. If cancellation would be a normal exception, it could be intercepted by surrounding catch(...) blocks, which could prevent the transaction from being actually cancelled.

Thus, exceptions and cancellation have differences, and one cannot easily substitute one for the other. It could perhaps be possible to express cancellation with extensions to existing exception handling semantics, but I do not see this to yield a large benefit. SG5 has discussed proposals that tried to make cancellation look like exceptions, and this rather lead to confusion than ease-of-use because it seemed to make people believe that cancellation would always behave like exceptions (see N3591). Therefore, I think that it is better to provide cancellation as a separate mechanism. This ensures that exceptions behave in a transactional context in the same way they would in a nontransactional context, which should make it easier to use existing code in transactions.

Hans Boehm has pointed out in discussions on the SG5 reflector that explicit cancellation, for example if in the form of a separate mechanism, can by-pass existing exception handling code. There is concern that the existing exception handling code could be the only way to make forward progress (e.g., because only it contains a fallback execution path), and that cancellation would thus not be safe to use in callbacks called from library code, and that in turn cancellation would be too error-prone. I and other SG5 members do not share this concern. It is certainly possible for programmers to misuse cancellation, but there are simple rules under which using cancellation is safe. First, cancellation obviously needs to execute in a transactional context, and thus needs to be associated with some transaction. Second, if the code that executes this transaction can make forward progress without this transaction (e.g., as in the case of speculative execution), then cancellation is safe because forward progress can be guaranteed by just the caller of the transaction. However, if this transaction needs to finish execution, then using cancellation might not be safe. In such a case, cancellation would cause similar problems as throwing an exception of a wrong type (i.e., so that certain exception handlers do not execute).

Please note that the above is not a comprehensive discussion of cancellation vs. exceptions, but a more detailed discussion would exceed the scope and purpose of this paper (which is to specify library-based cancellation and data escape mechanisms).

Letting data escape from canceled transactions

We cannot just use existing copy constructors or similar under the covers because we do not know in general which of the memory writes that they execute should actually escape (e.g., reference counting or copy-on-write schemes won't work). Instead, programmers must specify this, and there are different ways to do that (see this thread on the SG5 reflector for further discussion). For example, one could provide an escape mechanism only for certain types (e.g., standard exception types); but which ones do we pick, and are they sufficient in practice? Instead, I think it is best to provide both a low-level and high-level mechanism, as explained next.

The low-level approach: a special escaping memcpy

void* escaping_memcpy(void *dest, const void *src, size_t n);

• They are not guaranteed to be part of a transaction (so this should target thread-private memory, for example). Concurrent accesses by other threads to *dest are a data race.
• They are guaranteed to have executed before a cancellation handler runs (see below), so before cancellation of the transaction has taken place.
• If the transaction aborts before it has been canceled explicitly, then any prior writes to *dest will be undone before the transaction restarts.
• The TM implementation must ensure that *dest can be read transactionally by the current transaction during its whole execution. (We could also require separation between *dest and *src, but the former is straight-forward to implement at least in STMs, and required for the high-level mechanism discussed next.)
• Any transactional writes to *dest by this transaction result in undefined behavior.

The allocation-based approach

What we need is a concise way for programmers to specify which data should escape. One possible way to do this is to let programmers assert that all writes to memory allocated with a special allocator escape, and only those writes. We could either expose this special allocator and expect programmers to use it as necessary, or let the TM implementation provide two library functions that temporarily replace the default allocator in the current transaction with the special allocator:

std::escape_allocations_begin();
// All allocations with the default allocator will now use the special escape allocator.
Foo* escaping_copy = new Foo(src);
std::escape_allocations_end();
// Now we're not using the special allocator anymore.

The additional implementation complexity compared to escaping_memcpy should typically be modest. There are different implementation possibilities for STMs, which do not add overhead to the transactional load/store fast paths; virtually replacing the default allocators is also simple and will not affect other threads because the allocators have to be wrapped anyway for STM transactions by the TM (and cancellable transactions need to run instrumented code anyway). HTMs that do not support data escape have to fall back to STM execution anyway on cancellation. HTMs that do support data escape (e.g., nonspeculative writes) can implement this with additional copying, for example.

Finally, the previous discussion assumed that the data should escape to the nontransactional context (i.e., escape from the outermost transaction). This can be extended to support escaping to enclosing transactions as well by requiring a cancellation handler (see below) to be provided as an additional parameter on calls to the three library functions; the cancellation handler would then specify which transaction the data should escape from.

Expressing cancellation

1. the part of the program that started the transaction needs to be notified that the transaction was canceled,
2. when canceling a transaction, the program needs to be able to select which transaction from among all enclosing transactions should be canceled (i.e., if there are nested transactions), and
3. we (optionally) need to be able to let information escape from a canceled transaction.

Both (1) and (2) are based on something that I call cancellation handlers, which are function objects that can be attached to transactions. They get executed instead of a canceled transaction, and also serve as IDs for transactions. For (3), we can use the data escape mechanism presented previously.

Extended syntax for cancellable transactions

__transaction_atomic { /* Cannot be canceled. */ }
__transaction_atomic (CH) { /* Can be canceled. */ }

Informally, CH is a function or lambda returning void that takes no arguments. Iff the transaction is canceled, it will be executed after the transaction has been rolled back. Thus, CH appears to execute instead of the transaction; because we are dealing with an atomic transaction, no side effects of it remain after it has been rolled back, so we are virtually back at the program state before executing the transaction. Another way to imagine this construct is it being equivalent to something like:

if (next_transaction_canceled_oracle())
  CH();
else
  __transaction_atomic { /* Can be canceled. */ }

CH can be a pointer to a function object or function of suitable type, in which case the pointer also serves as the ID of the transaction (see below for how this ID is used). Alternatively, the programmer can also supply a lambda directly (and then the ID of the transaction will not be known to the program).

New library features for cancellation

__transaction_atomic ([]() { std::terminate() })
{
  f1();
  if (flag)
    std::transaction_cancel(); // Cancels the transaction.
                               // Does not return.
  f2();
}

This simple form of cancellation will cancel the nearest enclosing transaction (in terms of transaction nesting levels) that is cancellable (i.e., has a cancellation handler attached). Outside of any transaction, trying to cancel will terminate the program. In the following example adapted from the previous one, the program will not terminate even if flag is true:

__transaction_atomic ([]() { std::terminate() })
{
  f1();
  if (flag)
    __transaction_atomic ([]() { /* Ignore cancellation. */ })
    {
      __transaction_atomic { // Non-cancellable transaction.
        std::transaction_cancel(); // Cancels the 2nd transaction.
      }
    }
  f2();
}

std::function<void()> outermost_ch = []() { std::terminate() };
__transaction_atomic (&outermost_ch)
{
  f1();
  if (flag)
    __transaction_atomic ([]() { /* Ignore cancellation. */ })
    {
      __transaction_atomic { // Non-cancellable transaction.
        // Cancels the outermost transaction.
        std::transaction_cancel(&outermost_ch);
      }
    }
  f2();
}

If the program needs to let data escape from a canceled transaction (e.g., to describe an error, as discussed previously), it can use the escape mechanism directly:

bool canceled = false;
__transaction_atomic ([]() { /* Ignore cancellation. */ })
{
  bool f = true;
  std::escaping_memcpy(&canceled, &f, sizeof(bool));
  std::transaction_cancel(&outermost_ch);
}
if (canceled)
  ...;

int i = 0;
__transaction_atomic ([&]() { i += 1; })
{
  std::transaction_cancel([&](std::function<void()>& ch)
    {
      i = 2;
      ch(); // Calls the cancellation handler, which increments i.
    });
}

This allows the part of the transaction that cancels it to customize or replace the cancellation handler; also, it is a convenient way to let data escape and have this data drive what happens after cancellation (e.g., compared to the prior example, no external variable such as canceled is required; i is just used for illustrative purposes). Note that other variants would be possible too (e.g., the cancellation handler could get the opportunity to call a lambda provided during cancellation); nonetheless, I hope that this shows the basic idea.

Finally, we can offer a variant of cancellation that allows the escaping lambda to communicate directly with the cancellation handler, thus allowing for customizable communication across cancellation:

template <class R, class... ArgTypes>
void transaction_cancel(
  function<void(function<R(ArgTypes...)>& ch)> cancel_lambda,
  function<R(ArgTypes...)>& transaction // The cancellation handler that
                                        // identifies the transaction.
);

std::function handler = [&](int input) { i = input + 1; };
__transaction_atomic (&handler)
{
  std::transaction_cancel([&](std::function<void(int)>& ch)
    {
      ch(2); // Calls the cancellation handler with input.
    },
    &handler ); // Select transaction explicitly.
}

Alternatives for expressing cancellation

First, programmers can use simple flags to check whether a transaction was canceled or not:

bool canceled = true;
__transaction_atomic
{
  canceled = false;
  ...;
}
if (canceled) 
  std::terminate();

While this works in principle, it seems like too much of a low-level mechanism, and is probably error-prone (e.g., it's easy to forget to check canceled, and transactions without this checking can be canceled too, leading to silent errors). Second, cancelled transactions could throw special exceptions to signal that they have been canceled, instead of executing a cancellation handler:

try {
  __transaction_atomic
  {
    f1();
    __transaction_atomic {
      if (flag1) std::transaction_cancel();
    }
    if (flag2) std::transaction_cancel();
  }
}
catch (transaction_canceled_exception ex) {
  // One of the two transactions was canceled.
  std::terminate();
}

Furthermore, because this does not use cancellation handlers anymore, this also does not allow for selecting which transaction to cancel using the handlers. Nor can the implementation easily detect at compile time when it could use flat nesting.

Finally, one drawback of using exceptions is that it does not allow compatibility with C. In contrast, the cancellation handler approach can also be extended to function pointers and perhaps additional arguments, which would allow C code to make use of this feature and would make this C code usable in a C++ context too.

Third, the cancellation handler could be set using a library call instead of as an argument to the transaction. However, this seems to be an inferior approach because it makes it less clear which transaction can be cancelled, and has to rely on some concept of the "next" transaction.

Example uses

Cancellation when exceptions escape from transactions

__transaction_atomic (std::cancel_on_escape()) {
  try {
    ...; // Transaction body, might throw an exception.
  }
  catch(...) {
    std::transaction_cancel([](std::function<void()>& ch) {
      // After rollback of the transaction, a special exception will be thrown.
      // (N3589 does not provide a general data escape mechanism.)
      throw canceled_transaction_exception;
    },
    std::cancel_on_escape()); // Picks the nearest enclosing cancel-on-escape
                              // transaction.
  }
}

Composable recovery mechanisms

One could implement something similar with exceptions, but it would probably require strong exception guarantees everywhere and quite a bit of extra program logic. In the end, we would probably end up with something similar to transactions anyway (without the concurrency control). Thus, while composable error recovery mechanism based on transactional language constructs are clearly future work (see pages 113--141 of this PDF for further details), I think that the cancellation mechanisms I presented should be a viable foundation for such more advanced uses.

Acknowledgements