[gambit-list] Asynchronous Interrupts

Dimitris Vyzovitis vyzo at hackzen.org
Sun Jul 30 16:06:12 EDT 2017


> ...only its equivalent to incrementing an per-processor atomic state ...

this should be per-thread.

-- vyzo



On Sun, Jul 30, 2017 at 11:04 PM, Dimitris Vyzovitis <vyzo at hackzen.org>
wrote:

> 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://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20170730/72412d05/attachment.htm>


More information about the Gambit-list mailing list