[gambit-list] Asynchronous Interrupts

Dimitris Vyzovitis vyzo at hackzen.org
Sun Jul 30 16:04:11 EDT 2017


Quite a few words in there! Very solid exposition of a difficult
problem.

Some first thoughts regarding implementation: We can go quite aways
with two primitives:

(thread-raise! thread obj)
(begin-atomic body ...)

thread-raise! is a generalization of thread-abort! that asynchronously
raises an exception in the first safe-point for the target thread. A
safe point is defined when interrupts are enabled _and_ asynchronous
exceptions are not masked by an atomic regions.

Atomic regions are demarcated with begin-atomic, which acts like begin
only its equivalent to incrementing an per-processor atomic state
counter for the dynamic extent of the body.  When this counter is > 0,
asynchronous exceptions are masked. When the counter is decremented
back to zero, a pending asynchronous exception can be raised.

Wrt to dynamic winds, both the wind and unwind thunks must be considered
atomic. Furthermore, if the wind thunk has been evaluated, then the
unwind thunk should be guaranteed to be evaluated as well in the presence
of asynchronous exceptions in the body thunk.

-- vyzo

On Sun, Jul 30, 2017 at 10:02 PM, Faré <fahree at gmail.com> wrote:

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


More information about the Gambit-list mailing list