<div dir="ltr"><div>Quite a few words in there! Very solid exposition of a difficult<br>problem.<br><br>Some first thoughts regarding implementation: We can go quite aways<br>with two primitives: <br><br>(thread-raise! thread obj)<br>(begin-atomic body ...)<br><br>thread-raise! is a generalization of thread-abort! that asynchronously<br>raises an exception in the first safe-point for the target thread. A<br>safe point is defined when interrupts are enabled _and_ asynchronous<br>exceptions are not masked by an atomic regions.<br><br>Atomic regions are demarcated with begin-atomic, which acts like begin<br>only its equivalent to incrementing an per-processor atomic state<br>counter for the dynamic extent of the body.  When this counter is > 0,<br>asynchronous exceptions are masked. When the counter is decremented<br>back to zero, a pending asynchronous exception can be raised.<br><br>Wrt to dynamic winds, both the wind and unwind thunks must be considered<br>atomic. Furthermore, if the wind thunk has been evaluated, then the<br>unwind thunk should be guaranteed to be evaluated as well in the presence<br>of asynchronous exceptions in the body thunk. <br><br></div>-- vyzo<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jul 30, 2017 at 10:02 PM, Faré <span dir="ltr"><<a href="mailto:fahree@gmail.com" target="_blank">fahree@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear Marc & Gambiteers,<br>
<br>
I was hoping to write a short email about a simple way to support<br>
asynchronously aborting threads, as per<br>
<a href="https://github.com/gambit/gambit/issues/275" rel="noreferrer" target="_blank">https://github.com/gambit/<wbr>gambit/issues/275</a><br>
Then I realized that the problem was (Faré's PhD thesis)-complete, and<br>
what I ended up writing was a statement of intent for the non-trivial<br>
hacking of Gambit that I need to achieve to complete my thesis at<br>
<a href="https://j.mp/FarePhD" rel="noreferrer" target="_blank">https://j.mp/FarePhD</a><br>
It's all connected, but I'll include copious background, so if you<br>
have time not to skip this message, go grab yourself some<br>
tea/coffee/etc.<br>
<br>
<br>
I'm enjoying actor programming on Gambit Scheme (actually using Gerbil<br>
Scheme as a layer on top of it). But, especially so after I noticed an<br>
actor going crazy and busy looping with 100% of CPU, I realized that I<br>
*really* wanted to be able to develop robust actor systems in the<br>
style of Erlang — except on top of Gambit.<br>
<br>
Erlang allows programmers to build extremely robust systems by being<br>
based on the principle that errors, failures and mistakes WILL happen,<br>
and that the system should as mattter of course easily recover from<br>
them — by killing and restarting the failed subsystems. To elucidate<br>
the paradigm shift in this approach to software, see notably the great<br>
2017 paper by Tomas Petricek "Miscomputation in software Learning to<br>
live with errors" <a href="http://tomasp.net/academic/papers/failures/" rel="noreferrer" target="_blank">http://tomasp.net/academic/<wbr>papers/failures/</a> or his<br>
much shorter 2015 blog post: <a href="http://tomasp.net/blog/2015/failures/" rel="noreferrer" target="_blank">http://tomasp.net/blog/2015/<wbr>failures/</a><br>
<br>
One key mechanism to achieving this very robust style of developing<br>
distributed systems based on actors (that Erlang calls "processes") is<br>
Erlang's ability to safely kill a process at any point in time. There<br>
are many reasons why a process may fail: its execution may hit a<br>
software bug; it may hit a hardware bug; it may be hit by cosmic rays<br>
or outer forces; it may fall victim to some "wrench" thrown by<br>
software like Chaos Monkey<br>
<a href="https://blog.codinghorror.com/working-with-the-chaos-monkey/" rel="noreferrer" target="_blank">https://blog.codinghorror.com/<wbr>working-with-the-chaos-monkey/</a> that<br>
deliberately introduces random failures into the system to ensure that<br>
robustness issues are found and addressed earlier rather than later;<br>
it may be targetted by some denial-of-service attack; it may exceed<br>
some resource threshhold; it may otherwise enter a state where it<br>
fails to correct respond to queries, especially so to semi-random<br>
semi-periodic probing queries by its supervisor. Whatever the reason,<br>
inasmuch as the supervisor can detect failure, it can safely kill the<br>
failing process, and restart a new one to replace it. The process will<br>
be unregistered from whatever service broker it was subscribed to, and<br>
the incoming request traffic will be picked up by its healthy<br>
registered peers until the replacement is fully operational.<br>
<br>
Because interesting services are made of many actors (or "processes"<br>
in Erlang parlance) that act in concert and have mutually-dependent<br>
state, when a process dies (whether of natural or super-natural<br>
causes), all the processes linked to it (parents and children) are in<br>
turn sent a signal to shutdown graciously. They can explicitly catch<br>
and handle this signal if they really care to survive or to cleanup<br>
something before they die; but by default, the linked process just<br>
dies immediately, freeing all its resources; when it dies, so will a<br>
graceful shutdown signal be sent to its own linked processes,<br>
recursively, in a tree of related processes. In Erlang, this ability<br>
to safely kill entire process trees is essential to build an extremely<br>
robust architecture where large services made of many coordinated<br>
actors automatically restart in a coherent way when errors (or regular<br>
system upgrades) happen.<br>
<br>
<br>
I have long dreamed to have this Erlang-style robustness in a Lisp —<br>
rather than building a Lisp on top of Erlang, like LFE, that while<br>
robust would miss a lot of the system programming tradition of Lisp<br>
and its performant compilers. And Gambit is oh so close to it, yet I<br>
realize still so far.<br>
<br>
Importantly, in Erlang, the actor shutdown signal works<br>
asynchronously, at least by default, for regular actors that don't<br>
explicitly catch and handle these signals. This means that a regular<br>
process may die in the middle of whatever the hell it is doing. This<br>
works well in Erlang, because of its programming model where processes<br>
are made of pure functions and communicate exclusively via message<br>
passing. The model ensures by construction that there is precious<br>
little shared state that may be left in an invalid state when an<br>
asynchronous signal happens, only the message mailbox and a shared<br>
buffer extension sometimes used for performance reasons. And the<br>
system implementation ensures that accesses to this shared state are<br>
atomic with respect to asynchronous signal delivery, so the rest of<br>
the process is all private state and can be released without any<br>
resource leak.<br>
<br>
Now, in Scheme (and most other languages, except maybe Haskell), there<br>
can be a LOT more shared state that may be left in disarray if a<br>
thread is interrupted in the middle of random operations. Stateful<br>
data structures are a common thing to use; if anything, making system<br>
calls or using libraries often involves a lot of state; the language<br>
implementation's runtime environment itself has plenty of shared<br>
state, and was never designed to play well with asynchronous<br>
interrupts. Which means that, if an asynchronous interrupt happens (a<br>
signal in Unix parlance), it must be expected that some this shared<br>
data will be in some intermediate state, and that killing the current<br>
thread would leave the program unstable and unable to operate<br>
correctly: a lock may be held that will never be released; the state<br>
protected by that lock may violate necessary invariants to its<br>
operation; some resource borrowed from another thread such as a<br>
handler granted by a server may never be released or otherwise<br>
complete its usage cycle the program may be experience a deadlocked or<br>
livelock; some distributed protocol that was previously initiated<br>
(e.g. voting, partaking in some transaction, etc.) may never complete;<br>
another thread waiting on a spinlock may spin the CPU forever in a<br>
tight loop; if a low-level invariant is broken, the program may crash<br>
in ugly low-level ways, or worst of all, it may return wrong answers<br>
and do the wrong thing to your system — which can conceivably cause<br>
death and/or loss of millions of dollars.<br>
<br>
On the other hand, if you fail to interrupt the thread when it is<br>
failing, then it might keep running in a zombie state that eats all<br>
your CPU or holds onto critical resources (shared data structures,<br>
sheer amount of memory, file handles, etc.) that blocks the other<br>
computations from successfully making progress. Or its known failing<br>
state may lead to corruption of critical data. In this case too,<br>
costly or deadly failure may happen.<br>
<br>
<br>
Therefore, in Scheme, as in most languages, at least at present, the<br>
limited solutions to providing an ersatz of Erlang-style robustness<br>
are as follow:<br>
 1- Do NOT allow for asynchronous killing at all at the Scheme level.<br>
Have only synchronous killing at the Scheme level.<br>
 2- Socially enforce a convention that all actors should regularly go<br>
back to the message loop, and that there should never be a deadlock,<br>
live lock, non-terminating computation or runaway code execution<br>
between two consecutive calls home to the message handling loop.<br>
 3- If some algorithm require indefinitely long computations, their<br>
implementation must maintain a discipline of "cooperative<br>
multitasking", like in the bad old days of the 1980s, whereby these<br>
long-lived computations will be specially modified to periodically<br>
"yield" execution and give the message loop process the opportunity to<br>
process any synchronous shutdown message while the program is in a<br>
stable state.<br>
 4- Consider Scheme as a replacement not for Erlang, but for the<br>
lower-level language in which the Erlang VM is implemented (i.e. C),<br>
that has to deal with all the ugly synchronization details, without<br>
being able to fully abstract over them.<br>
 5- Build further abstractions over this lower-level language, and<br>
stick to them by social convention. A regular Scheme cannot enforce<br>
these social conventions and prevent users from breaking the<br>
abstractions and reaching into the implementation details; however,<br>
Gerbil allows you to build and enforce a full abstraction for module,<br>
thanks to its Racket-like #lang feature, that impose global (rather<br>
than merely local) restrictions on what a module can express.<br>
 6- If you really want a group of actors that live and die together,<br>
put them in a same Operating System level process (and either use OS<br>
process groups to implement trees of related processes, or implement<br>
yourself that notion using some kind of supervisor process). Then you<br>
can kill and restart the entire process (or set of processes). Unlike<br>
Erlang processes or Gambit threads, It's heavy weight; but it works,<br>
and sometimes that's what's exactly needed.<br>
 7- In general, as much as possible, use pure functional style and/or<br>
restrict side-effects to local state that is private (not shared),<br>
thus reducing issues related to shared state for processes that use<br>
this style. However, because the Scheme implementation's runtime and<br>
the available libraries were never designed for asynchronous<br>
interrupts, their own use of shared resources can still cause<br>
catastrophic failures in case of asynchronous aborts.<br>
<br>
This strategy of course works, but leads to code that is awkward,<br>
inefficient, not modular, tiresome and error-prone to write,<br>
impractical except at a small scale, and still fragile. It is not<br>
satisfactory to only provide fragile constructs that will explode if<br>
users fail to respect non-trivial coding conventions and maintain them<br>
as the software evolves. This issue really calls for some robust<br>
abstraction mechanism that will automatically enforce any invariant<br>
though coherent automated code generation rather than manual<br>
discipline. Well, at least, Scheme is not worst than any other random<br>
language. The only languages that stand out for their robustness are<br>
those based on the Erlang VM, BEAM, i.e. Erlang itself, Elixier, LFE,<br>
Efene, Joxa, and whatever Erlang flavor of the day.<br>
<br>
<br>
Now, what I would really like is to enhance Gambit Scheme with basic<br>
mechanisms to really allow safe asynchronous killing of threads. I<br>
told vyzo and he opened issue<br>
<a href="https://github.com/gambit/gambit/issues/275" rel="noreferrer" target="_blank">https://github.com/gambit/<wbr>gambit/issues/275</a> on asynchronous aborts. My<br>
first reflex was to think that if you somehow have a notion of<br>
pseudo-atomic code blocks and you can ensure that asynchronous signals<br>
are deferred until the end of current code block, then everything will<br>
be fine. Cleanup forms in "finally" clauses or dynamic-wind forms may<br>
have to be considered atomic, or at least start with interrupts<br>
disabled. But otherwise, it should be pretty much a straightforward<br>
extension of what the GVM already supports for the sake of e.g.<br>
garbage collection, right? Nope.<br>
<br>
It actually takes a whole lot to make proper asynchronous interrupts<br>
work in presence of shared state. After thinking about the issue a bit<br>
more, I realized that it's actually the very same problem that plagued<br>
me for years, and that I have solved in theory my (incomplete) PhD<br>
thesis, but that still requires a practical implementation. And I also<br>
realized that my thesis has a solid argument why there is no shortcut<br>
to the complete solution proposed in my thesis, of a general protocol<br>
for declaring "observability" of computations.<br>
<br>
Indeed, for each level of abstraction that you (or your users) care<br>
about, there will be high-level invariants on the shared state that,<br>
if broken, leave the entire program unable to make progress at that<br>
level of abstraction, even though the state may be perfectly fine at<br>
lower-levels of abstractions. Solving the problem at a low-level of<br>
abstraction can never be enough to solve the issue at higher levels of<br>
abstraction, that the lower-levels are only a means to support. Thus,<br>
you can never safely kill any thread in any existing language, with<br>
the exception of Erlang.<br>
<br>
Yet, Erlang does it for all programs. And if you look carefully,<br>
you'll see that each and every programming language with preemptive<br>
user-level threads or a garbage collector supports pseudo-atomic<br>
blocks and properly deferred asynchronous signal delivery to suitable<br>
"safe points", so the invariants of its own virtual machine are<br>
enforced before a context switch may proceed without the asynchronous<br>
signal handler interfering with low-level implementation details of<br>
the language's virtual machine. In the case of Gambit, quite<br>
remarkably, asynchronous signal handling by the system is compatible<br>
since 2015 with migrating processes from one GVM to another, e.g. C to<br>
JS to PHP — by making sure the signal to migrate is only processed at<br>
safe points relative to the GVM.<br>
<br>
<br>
To find a general solution to the issue, you must first step back and<br>
look at the bigger picture: software can be seen as a "semantic<br>
tower", where each layer is the implementation of some more abstract<br>
computation A using some more concrete computation C. For instance,<br>
your program implements a user abstraction U on top of your<br>
programming language abstraction P; the compiler you use implement<br>
this abstraction P in terms of a lower-level virtual machine V. Then a<br>
lower layer expresses V in terms of a low-level view O of the system<br>
as provided by the operating system. The operating system itself<br>
implements O in terms of the documented CPU and chipset semantics C. C<br>
may include microcode that realize the CPU abstraction in terms of a<br>
digital circuit D. D is implemented as transistors in terms of analog<br>
electrical circuits E. E is implemented in terms of quantum mechanics<br>
Q. Q is implemented by God in terms of his own digital physics<br>
computer a la Ed Fredkin. Many more abstraction levels may exist<br>
above, below, or in the middle, that were omitted in this list, yet<br>
may be added when observing the semantic tower from a wider point of<br>
view or with a finer resolution of details.<br>
<br>
>From this point of view, the issue of asynchronous signal handling is<br>
then that at each layer of implementation, a low-level asynchronous<br>
interrupt signals may be received at a safe point for the lower level<br>
of abstraction, but that the implementation may want to deliver a<br>
higher-level asynchronous signal, to be handled at a safe point for<br>
the higher level of abstraction. Each level of abstraction thus has<br>
its own notion of safe point, with its own restrictive invariants,<br>
that its implementation must express in terms of the lower<br>
abstraction's level of safe-point, using the language in which it is<br>
written, that is expressed in terms of that lower abstraction's state<br>
and its laxer invariants. The general architecture of this semantic<br>
tower must therefore support "lifting" the notion of safe point, so<br>
that a higher-level safe point may be recovered from a lower-level<br>
safe point. In my thesis I call the corresponding property of<br>
implementations that can lift this notion of safe-point<br>
"observability". The developer in charge of providing an abstraction<br>
level must make sure it can never be caught "with its pants down" (to<br>
reuse the metaphor by ITS hackers, as narrated by Alan Bawden in his<br>
great article on PCLSRing, an early documented instance of the notion<br>
of observability, in an 1960s operating system). And he must for that<br>
use on the lower-level system provided by the programming language he<br>
uses, that he may hopefully rely on itself never being caught with<br>
their pants down, but only observed in stable states.<br>
<br>
Therefore, when an asynchronous signal is received for which a handler<br>
is registered at a given level of abstraction A, the system must<br>
somehow synchronize to a safe point for A before to run the handler,<br>
and in general this level may be higher than that of Gambit's virtual<br>
machine. Furthermore, in the case of aborting a thread, this level of<br>
abstraction is the highest at which this thread matters to anyone<br>
(user, or supervisor program that knows how to rebuild higher<br>
abstractions).<br>
<br>
In simple cases, recovering a safe point for a level of abstraction A<br>
is simply a case of letting the code run, and checking at each safe<br>
point reached whether an interrupt was received that requires<br>
processing at that level of abstraction (or one below). But for many<br>
reasons may require to support less simple cases: there may be ongoing<br>
transactions that need to be rolled back (aborted) or rolled forward<br>
(eagerly completed, or maybe partially completed but with some clean<br>
stable state register that will cause a follow up transaction); the<br>
abstract state may be a composite of the states of several concurrent<br>
systems, that may each have to be stopped and synchronized to an<br>
observable state; performance may require shortcuts to be taken in the<br>
regular case that have to be compensated for when an interrupt is<br>
caught. In the most general case, whichever programmer is specifying<br>
the abstraction level A is himself using a programming language<br>
providing a more concrete level of abstraction C. When specifying a<br>
handler of asynchronous signals to recover a stable state at level A,<br>
the programmer necessarily needs to express it the language he is<br>
using, in terms of the state at level C. Therefore, for that handler<br>
to run and synchronize to a safe point for A, the platform should<br>
first be able not just to synchronize to a safe point for C, but also<br>
to let the handler observe (recover, extract, reconstruct, inspect)<br>
the state at level C. Now, since there may be an even higher<br>
abstraction level H on top of A, it is not enough to synchronize to a<br>
safe point for A, the platform must also support observing (recoving,<br>
extracting, reconstructing, inspecting) the state at the level A so<br>
the handler of the implementation of H with A can itself specify how<br>
to synchronize to a safe point for H and let yet higher levels of<br>
abstractions observe the state at level H.<br>
<br>
Now, a naive understanding of "recovering the state at level A" can be<br>
expensive: you don't want to serialize the entire state of the virtual<br>
machine (potentially gigabytes of memory or more) every time you<br>
process an asynchronous interrupt handler. You want this recovery to<br>
be lazy, so only the bits of state actually required by the handler<br>
need to be partially reified at the required level of abstraction. A<br>
naive implementation of safe points would create a closure to express<br>
this recovery, at every safe point. A slightly less naive<br>
implementation would only create that closure *if* an interrupt was<br>
caught at that safe point. Therefore, the general protocol for a safe<br>
point is therefore to have some kind of special form (safe-point level<br>
state), where level is some kind of object identifying the level of<br>
abstraction of the safe point (if possible known at compile-time,<br>
usually implicit when discussing safe points of a well-identified<br>
layer of the semantic tower), and state is a form only evaluated when<br>
an interrupt is caught at said level, that permits recovery of the<br>
state at specified abstraction level, if possible lazily.<br>
<br>
The compiler hopefully knows how to merge safe-points between levels<br>
of abstractions, so that tests for asynchronous interrupts at higher<br>
level safe-point and creation of corresponding higher-level state<br>
objects only happen if an asynchronous interrupt was already caught at<br>
the corresponding lower-level safe-point, yet wasn't handled already<br>
by a lower-level handler. An even better compiler would eliminate<br>
redundant consecutive safe point checking, so e.g. check points are<br>
only checked at the beginning of functions or loops (just like the<br>
implementation already does for its own lower-level checkpoints).<br>
<br>
Now, it is not enough to have compiler support. The runtime library<br>
must also be written in a way that supports asynchronous interrupts,<br>
and the programming language must provide suitable abstractions.<br>
Notably, when allocating *any* kind of resource that an asynchronous<br>
interrupt may necessitate to release, the atomic operation with<br>
respect to interrupts should be not merely allocating the resource,<br>
but allocating it AND atomically binding some variable to it; only<br>
then may a "finally" clause properly release the resource without a<br>
leak should an asynchronous abort be received. (The "finally" clause<br>
will also handle synchronous exceptions or regular exit). Potentially<br>
long-running library functions, and especially higher-order functions,<br>
may also have their own issues with respect to declaring safe-points<br>
for higher levels of abstraction within the dynamic extent of their<br>
function call. When an abstraction level reexports such functionality<br>
from lower levels, it may have to subtly wrap this functionality in<br>
variants that suitably handle safe-points. And the compiler may have<br>
to be able to suitably optimize away most wrappers.<br>
<br>
There is also the case when a thread receives a further asynchronous<br>
abort in the middle of processing an existing one; or when it gets<br>
stuck while executing cleanup forms in general. My understanding is<br>
that asynchronous aborts are specified with a target level of<br>
abstraction. By default, an abort signal (as a Unix kill -TERM) works<br>
at the highest level of abstraction that the programmer cares about,<br>
and should run all the cleanup forms. If the operator gets impatient,<br>
he may send signals with lower levels of target abstraction (down to a<br>
Unix kill -KILL), at which point levels of abstractions higher than<br>
the target level are invalidated, their cleanup forms are eschewed,<br>
and all linked processes at this level of abstraction are killed (and<br>
hopefully restarted by their supervisor). It is therefore possible to<br>
"lose" a layer of abstraction -- if there was a bug in the<br>
implementation of this layer of abstraction, at which point, well,<br>
that is exactly what "having a bug" means.<br>
<br>
All in all, it's a lot of non-trivial work, especially since I need to<br>
modify the Gambit compiler to itself follow the protocol for the<br>
layers between Scheme and the GVM (it already follows it for the<br>
layers below the GVM, yay Marc!). But the result might be worth it,<br>
because, as I argue in my thesis (incomplete, but you can already read<br>
141 pages worth of it), successfully enforcing this protocol unlocks<br>
an entire world of further cool features. I solved it all in theory.<br>
But since this is computing, not mathematics, theory is not enough and<br>
now I need to work on the implementation.<br>
<br>
—♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• <a href="http://fare.tunes.org" rel="noreferrer" target="_blank">http://fare.tunes.org</a><br>
Happiness is a journey, not a destination; happiness is to be found along the<br>
way not at the end of the road, for then the journey is over and it's too<br>
late. The time for happiness is today not tomorrow.  — Paul H. Dunn<br>
______________________________<wbr>_________________<br>
Gambit-list mailing list<br>
<a href="mailto:Gambit-list@iro.umontreal.ca">Gambit-list@iro.umontreal.ca</a><br>
<a href="https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list" rel="noreferrer" target="_blank">https://webmail.iro.umontreal.<wbr>ca/mailman/listinfo/gambit-<wbr>list</a><br>
</blockquote></div><br></div>