Thanks Jens.  I think writing another paper would subsume the preceding draft, which focused on allocation.  One concern I have is that I don't really know the right style/tone/level of detail for such a paper for this audience.  Do you know of any examples that I might be able to reference?

- Mike

On Wed, Oct 21, 2020 at 4:48 PM Jens Maurer <Jens.Maurer@gmx.net> wrote:
On 21/10/2020 15.54, Michael Spear via SG5 wrote:
> If an implementation protects all transactions with a single, global, reentrant lock, then there are three pieces to the implementation.  
> - The first is modifying the parser to support the new syntax.  This is common to any implementation, so whatever effort it entails is really a fixed cost for the TS.  
> - The second is some kind of run-time library that maps the beginning and end of a lexically scoped transaction to operations for lock acquire and lock release.  This is quite simple.

Agreed so far.

> - The third is whatever static analysis is needed to warn programmers when their atomic blocks do something forbidden.  This may be difficult, depending on how we specify things.  For example, if the compiler *must* warn when an exception escapes a transaction, then if the compiler does not have access to definition of a function that might throw, how could it give such a warning?
>
> My guess is that the third piece is going to be "best effort" by the compiler writer.  Surely some things should produce warnings, but with an understanding that there might be false negatives (e.g., we miss a warning for a transaction that has undefined behavior, because the transaction spans TUs and in some other TU, it uses std::cout or a std::atomic variable, or opens a socket, or does something else that can legally constitute inter-thread communication).

My guess is there will be close to zero warnings.
As you correctly observe, there are implementability concerns
for required warnings on e.g. exceptions escaping an atomic
block.  As a consequence, no warnings will be required.
(And if we could require warnings, we'd make them errors,
because if we can say for sure that bad code is executed,
we'd better refuse to compile.)

> In the case of throw, the expression of exceptions in the intermediate representation is via function calls or intrinsics (cxa_throw, cxa_catch, LLVM landing pads, etc).  The implementation of these is dependent on the OS and architecture.  For example, IIRC on Linux targets they traverse DWARF tables within the binary itself.  So, again, making assumptions about these is not portable, and correct programs cannot assume anything more than the high-level specified behavior.  That behavior is little more than "nonlocal jump, with destruction of everything on the popped part of the run-time stack".  Note: if I am wrong, and the behavior of stack unwinding is more carefully defined, and that definition includes the possibility of stack unwinding being a legal form of inter-thread communication, then my whole argument is invalid.  Hopefully someone more knowledgeable about exceptions in C++ can confirm or refute my claim.

Stack unwinding is properly defined, but it does not have inter-thread
impact per se.  Something like std::lock_guard's destructor unlocks a
mutex, of course, but these inter-thread communication mechanisms should
not be allowed in an atomic block regardless.

> In the original TMTS, exceptions are tricky because there need to be writes to the exception object, and these writes need to be instrumented in a special way, because these writes can escape the transaction even if the transaction gets undone.  In the proposed TMTS, exceptions cannot escape a transaction (and the transaction doesn't ever have to get undone), which means that STM can fall back to a single lock whenever it encounters a throw.  This is easy to do, because the STM instrumentation pass simply says "here's a function for which I don't have a definition... I guess I'll just serialize the transaction here".  cxa_throw is no different than a multi-TU transaction.

Agreed.

> If we *wanted* to specify commit-on-exception-escape, it would be trivial to support in a reasonable TM implementation.  I don't think we want to, and I'm in favor of forbidding exceptions from escaping transactions.  However, the use of exceptions within a transaction does not appear to pose an implementation challenge, nor does it appear to pose a correctness challenge.
>
> So, in summary, I do not see implementation issues with supporting throw+catch inside a transaction, or allocation inside a transaction.  As the minutes state, this will open up a huge portion of the standard library to transactions (perhaps only threads, coroutines, mutexes, atomics, and iostreams would still be forbidden?).

Sounds about right.

As I said in the call, that's a rather sharp departure from the previous
approach "limited standard library functions are allowed", so needs an
accompanying rationale paper, stating approximately what's in your
e-mail, above.

Jens