Interrupt handler call serializator [closed]

Question

The question uses C to formulate the problem, but solutions in any language can be accepted. At the end of the question you can find a pythonic version.

As part of a bigger software, we have a C function:

void wrapper(void* p);

Which is a wrapper function around the C function:

void handler(void* p);

wrapper() is triggered by an external effect (hardware interrupt, unix signal, it doesn't matter), which also provides a p as its argument. The triggering can happen after the execution of any CPU instruction, even if wrapper() or handler() is being executed. The triggering happens similarly to the interrupt requests in a cpu, or to the signal handlers in unix: after wrapper() returns, the execution continues from exactly the same CPU state as the triggering found it.

We don't know what does handler(), but we know that it doesn't interact with the triggering mechanism.

As a help, we have

void swap(void **a, void **b);

which swaps the contents of two void* pointers in a single cpu instruction.

The solution of the problem is a wrapper() function, which "serializes" handler(): it makes sure, that handler() never is called in multiple times: every new handler() will be called only after the previous returned.

Trigger can't be lost: for every wrapper(), exactly one handler() must be called. It shouldn't be called from the same wrapper() which was actually triggered, but p can't be lost.

Similar solutions in practical situations often block the triggering for a short period, here it is impossible.

If needed, malloc(), free() and NULL (==(void*)0) can be used, but out of it, no library calls. These functions are considered reentrant (if triggering happens in them, they will work correctly). Especially any direct or indirect usage of any multithreading isn't allowed.

There is no speed criteria for wrapper(), but it must be ready in a finite time. We know, that the triggering won't happen so fast to cause some hardware/stack/etc. overflow. wrapper() must handle any deep of reentrancy.

Any language can be used for the task (incl. asm or interpreted languages), but no language construction or api calls which would make the task essentially easier, as in C.

The handler() calls don't need to happen in the same order as their corresponding wrapper() was triggered.

The solution is an implementation of wrapper().

Analogous problem in Python:

Look for the signal handlers module in python (here). This what this problem is about. Essentially, we have a

def wrapper(p):
  ..the solution...

What is a wrapper around

def handler(p):
  ...we don't know what is here...

The execution of wrapper is triggered by an external event. It means, that it can happen any time, even while we are in wrapper or in handler. If the triggering event happens, wrapper will be called. After it returns, the normal program execution will continue. The task is to implement wrapper in a such way, that handler won't run multiple times in the same moment. I.e. the next handler will be called only after the previous returned, even if the triggering happens while the wrapper(s) of previous trigger(s) run.

No python API call or external module can be used, with the single exeception of a

def swap(a, b):

...which exchanges the values of a and b in a single instruction (equivalent of a tmp = a; a = b; b = tmp, but it does in a single moment, without a triggering would be happened).

Bonus Python problem: the internal Python functions which handles the lists, dicts, etc, they all aren't reentrant. This means, if you call mylist.append(), it is possible that the trigger will happen during the execution of the append() method. If another wrapper() or handler() try to do anything with a such list, your program will segfault and solution won't be accepted. The case is the same for every higher-level language. In short: if you use _any_ higher level language construct, i.e. list/dict/object/etc, you need to make sure that it won't be used by any other wrapper which is triggered meanwhile.

The objective win criterion:

Afaik, this is a hard problem. If anybody can find a solution, is already a big success (to me was it around a week to find one), and on my opinion, there won't be a big difference between the different results. But it is required here to have an "objective winning" criterion, and so, lets say "the shortest solution in bytes" is the winner.

Answer 1

C, 149 bytes

Note: This seems to be a pretty controversial challenge, so I might be treading on thin ice here :) To make things clear, as far as I understand, the OP meant for the problem to be strictly single-threaded, which simplifies matters, since invocations of wrapper() can only interleave in an all-or-nothing fashion; if that's not the case, then this solution is wrong. The so called "interrupts" that trigger wrapper() are assumed to have the same semantics as C signals, as defined by the C standard, except that, as part of the hypothesis of the challenge, malloc() and free() can be called, and swap() can be used to access objects of type void* volatile with static storage duration, during the execution of their handler. (notwithstanding, the golfed version invokes all kinds of UB that aren't directly relevant to this challenge.)

P B;wrapper(p){P c=malloc(8);P b=c,n=c;*c=0;c[1]=p;while(c=n){S;if(b)return*b=c;handler(c[1]);S;n=*c;free(c);}}

Compile with: gcc -c -w -m32 "-DV=volatile" "-DP=int*V*V" "-DS=swap(&b,&B)" wrapper.c.

Look below for a test program to link against.

(The calculated code size is the size of the snippet, and of the three -D... arguments, not including the quotes.)

Ungolfed

We use a queue to store pending handler() invocations. Several queues may exist simultaneously, but at most one may be active at any given time. When wrapper() is invoked, if a queue is already active, we add an item at the back of the queue and return immediately. Otherwise, we start a new queue, and handle all of its items, until it empties; during the handling of a queue item (i.e., during an invocation of handler()), we make the queue active, so that nested invocations of wrapper() don't call handler() themselves; however, while fetching the next item, we deactivate the queue, so that nested invocations of wrapper() start their own queue, instead of modifying the one we're currently inspecting.

#include <stddef.h> /* NULL */
#include <stdlib.h> /* malloc(), free() */

void swap(void* volatile*, void* volatile*);
void handler(void* p);

/* Each queue item contains an argument, `p`, for the invocation of `handler()`,
 * and a pointer to the next item. The last item in the queue has a NULL `next`
 * pointer.
 */
struct queue_item {
    struct queue_item* volatile next;
    void* p;
};

/* Points to the last item in the currently active queue, or NULL if there is no
 * active queue.
 */
static void* volatile active_queue_back;

void wrapper(void* p) {
    struct queue_item* current;
    void* back;

    /* We allocate a new queue item for the current invocation of `handler()`.
     */
    current = malloc(sizeof(struct queue_item));
    current->next = NULL;
    current->p = p;

    /* We make the new item the back of the active queue, by assigning it to
     * `active_queue_back`, while at the same time fetching the previous value
     * of `active_queue_back`.
     */
    back = current;
    swap(&back, &active_queue_back);

    /* `back` now holds the previous value of `active_queue_back`. Since the
     * swap is atomic, no two interleaving invocations of `wrapper()` see the
     * same previous value, and no item is lost.
     */

    /* We check if there was an active queue prior to the current invocation of
     * `wrapper()`, that is, if the previous value of `active_queue_back` is not
     * NULL.
     */
    if (back != NULL) {
        /* If there was an active queue, we pass ownership over the new item
         * to the previously active queue (essentially making it active again,)
         * by linking it after the previous back of the queue. The owner of the
         * active queue is now responsible for handling, and disposing of, the
         * item, or, alternatively, for handing it over to someone further down
         * the line.
         */
        ((struct queue_item*) back)->next = current;

        /* Note that any reinvocation of `wrapper()`, following the preceeding
         * swap, will have added a queue item at the back of our newly allocated
         * one, directly or indirectly. Ownership over these items is
         * transitively passed to the owner of the active queue as well.
         */
    } else {
        /* If there was no active queue prior to this invocation, we take over
         * the queue, processing its items until it empties.
         */

        while (1) {
            struct queue_item* next;

            /* At the beginning of each iteration of the loop, we own the active
             * queue, `current` points to the current queue item (which is
             * initially the item created at the beginning of the function), and
             * `back` is NULL.
             */

            /* We can now call `handler()` for the value of `p` associated with
             * the current item. Note that any reinvocation of `wrapper()`,
             * from this point until the following swap, sees an active queue,
             * and therefore will not call `handler()` itself, but will rather
             * add an item at, ultimately, the back of our queue.
             */
            handler(current->p);

            /* In order to safely fetch the next item of the queue, we need to
             * make sure that no one else modifies the queue while we're at it.
             * To do that, we assign NULL to `active_queue_back` (recall that
             * `back` holds NULL at this point,) while fetching its current
             * value into `back`.
             * 
             * Any reinvocation of `wrapper()`, from this point until the
             * following swap, will see no active queue, and hence will start
             * its own independent queue, process it until it empties, and leave
             * `active_queue_back` NULL again, before control returns to the
             * current invocation.
             */
            swap(&back, &active_queue_back);

            /* We free the current item and move on to the next one. If the next
             * item is NULL, we terminate the loop.
             */
            next = current->next;
            free(current);
            if (next == NULL) break;
            else current = next;

            /* We restore the previous value of `active_queue_back`, so that our
             * queue is active again. Recall that `active_queue_back` is NULL at
             * this point, so `back` becomes NULL after the swap.
             */
            swap(&back, &active_queue_back);
        }
    }
}

This program can be compiled with gcc -c -m32 wrapper.c, instead of the golfed version. (Since this version doesn't rely on any shenanigans, unlike the golfed one, it can be compiled without -m32; in this case, don't use -m32 for the test program either.)

Test Program

The following program is a very rudimentary test for wrapper(). It's not meant to be thorough, nor does it rely on completely defined behavior; rather, its main purpose to show wrapper() in action.

Compile with: gcc -m32 -otest wrapper.o test.c, in a POSIX environment.

Run with: ./test.

The program triggers wrapper() upon receipt of SIGINT (usually, Ctrl + C), and has handler() print a message, and sleep for one second (during which SIGINT may be sent again). You can terminate the program by sending it SIGQUIT (usually, Ctrl + \).

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>
#include <signal.h>
#include <unistd.h>

void wrapper(void* p);

void swap(void* volatile* a, void* volatile* b) {
    void* t = *a; *a = *b; *b = t;
}

void handler(void* p) {
    struct timespec tp;

    printf("handler(p = %tu) entered. Sleeping for 1 second...", (uintptr_t) p);
    fflush(stdout);

    tp.tv_sec = 1; tp.tv_nsec = 0;
    while (nanosleep(&tp, &tp));

    printf(" handler(p = %tu) returned.\n", (uintptr_t) p);
    fflush(stdout);
}

static void signal_handler(int signum) {
    static volatile sig_atomic_t n = 0;
    wrapper((void*) ++n);
}

int main() {
    struct sigaction sa = {};
    sa.sa_handler = signal_handler;
    sa.sa_flags = SA_NODEFER;
    sigaction(SIGINT, &sa, NULL);

    while (pause());
}