Now a continuation example using the eg: closure that I had created with the last gist at: https://gist.github.com/1057979

continuation.c

/*
 * A continuation example with closure.
 * To run:
 *
 * gcc -o continuation continuation.c -Wall -g -lpthread
 * ./continuation  
 *  would test with creating 10 continuations each stacking 3 levels of continuations before unwinding
 * ./continuation 20 
 * would test with 20 continuations
 *
 * These principles could be used to create a single threaded async request server.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <assert.h>
#include <pthread.h>
#include "list.h"

#ifndef MAP_32BIT
#error "MAP_32BIT not defined"
#endif

struct scope
{
    void *args;
};

struct thunk
{
    unsigned char push_op;  /* push rdi */
    unsigned char mov_op[2]; /* mov $env, rdi */
    struct scope *scope; 
    unsigned char call_op; /* callq */
    int call_offset; /*$offset => function - address_of_call_offset*/
    unsigned char pop_op; /* popq rdi */
    unsigned char ret_op; /* ret */
} __attribute__((packed));

static struct thunk initialize_thunk = { .push_op =  0x57, .mov_op = {0x48, 0xbf},
                                      .call_op = 0xe8, .call_offset = 0,
                                      .pop_op = 0x5f, .ret_op = 0xc3
};

typedef void (*closure_t)(void);

struct continuation
{
    struct list_head list;
    closure_t thunk;
    int continuation;
};

#define likely(expr) __builtin_expect(!!(expr), 1)
#define unlikely(expr) __builtin_expect(!!(expr), 0)

#define __ALIGN(v, a) ( ( (v) + (a) - 1) & ~( (a) - 1 ) )
#define CONTINUATION_MAP_BITS (1024) /* 1024 simultaneous requests/continuations */
#define CONTINUATION_MAP_BYTES ( __ALIGN(CONTINUATION_MAP_BITS, 8) >>  3 )
#define CONTINUATION_MAP_SIZE  CONTINUATION_MAP_BYTES 
#define CONTINUATION_MAP_WORDS (__ALIGN(CONTINUATION_MAP_SIZE, sizeof(unsigned int)) >> 2 )

struct continuation_map
{
    struct list_head *continuations;
    unsigned int map[CONTINUATION_MAP_WORDS];
};

static struct continuation_map continuation_map = {
    .map = { [0 ... CONTINUATION_MAP_WORDS-1] = 0 },
};

static int __cfz(unsigned int *map, int bit)
{
    if(unlikely(bit >= CONTINUATION_MAP_BITS)) return -1;
    map[bit >> 5] &= ~(1 << (bit & 31));
    return 0;
}

static int __ffz(unsigned int *map, unsigned int size)
{
    int i;
    static int ffz_map[16] = { 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, -1 };
    for(i = 0; i < size; ++i)
    {
        unsigned int offset = 0;
        unsigned int mask = map[i] & 0xffffffffU;
        if(mask == 0xffffffffU) continue;
        if( ( mask & 0xffff ) == 0xffff )
        {
            offset += 16;
            mask >>= 16;
        }
        if( (mask & 0xff) == 0xff)
        {
            offset += 8;
            mask >>= 8;
        }
        if( (mask & 0xf) == 0xf)
        {
            offset += 4;
            mask >>= 4;
        }
        
        offset += ffz_map[ mask & 0xf ];
        map[i] |= ( 1 << offset );
        i = (i << 5) + offset;
        if( unlikely(i >= CONTINUATION_MAP_BITS))
            return -1;
        return i;
    }
    return -1;
}

static __inline__ void init_continuation_map(void)
{
    register int i;
    continuation_map.continuations = calloc(CONTINUATION_MAP_BITS, sizeof(*continuation_map.continuations));
    assert(continuation_map.continuations);
    for(i = 0; i < CONTINUATION_MAP_BITS; ++i)
    {
        LIST_HEAD_INIT(continuation_map.continuations + i);
    }
}

static int get_continuation(struct continuation_map *map)
{
    return __ffz(map->map, sizeof(map->map)/sizeof(map->map[0]));
}

static int clear_continuation(struct continuation_map *map, int continuation)
{
    return __cfz(map->map, continuation);
}

static __inline__ struct list_head *get_continuation_queue(int cont)
{
    if(unlikely(cont >= CONTINUATION_MAP_BITS)) return NULL;
    return continuation_map.continuations + cont;
}

/*
 * Take a scope and the function block to be bound to the scope.
 */
static closure_t make_closure(void *block, void *arg)
{
    struct thunk *thunk = (struct thunk *)mmap(0, sizeof(*thunk) + sizeof(thunk), PROT_READ | PROT_WRITE | PROT_EXEC, 
                                               MAP_PRIVATE | MAP_ANONYMOUS | MAP_32BIT,
                                               -1, 0);
    if((char*)thunk == MAP_FAILED)
        return NULL;
    *thunk = initialize_thunk;
    thunk->scope = calloc(1, sizeof(*thunk->scope));
    if(!thunk->scope)
    {
        goto out_free;
    }
    thunk->scope->args = arg;
    thunk->call_offset = (long)block - (long)&thunk->pop_op;
    return (closure_t)thunk;

    out_free:
    munmap(thunk, sizeof(*thunk));
    return (closure_t)NULL;
}

static void free_closure(closure_t closure)
{
    struct thunk *thunk = (struct thunk*)closure;
    int err = 0;
    free(thunk->scope);
    err = munmap((void*)closure, sizeof(*thunk) + sizeof(thunk));
    assert(err == 0);
}


/*
 * Stack it into a reclaim list since it could be released in the context of the closure itself.
 * So let it be released async.
 * We cannot write to the header of the thunk for the reclaim list as that contains the closure code.
 * So cannot overwrite ourselves.
 */
static struct thunk *reclaim_list;

static void release_closure(closure_t closure)
{
    struct thunk *thunk = (struct thunk *)closure + 1;
    *(struct thunk**)thunk = reclaim_list;
    reclaim_list = thunk;
}

static void reclaim_closure(void)
{
    struct thunk *iter = reclaim_list;
    struct thunk *next = NULL;
    while(iter)
    {
        struct thunk *thunk = iter - 1;
        next = *(struct thunk**)iter;
        free_closure((closure_t)thunk);
        iter = next;
    }
    reclaim_list = NULL;
}

static int stack_continuation(int cont, void *block, void *args)
{
    struct list_head *queue = get_continuation_queue(cont);
    struct continuation *continuation = NULL;
    int err = -1;
    if(unlikely(!queue)) goto out;
    continuation = calloc(1, sizeof(*continuation));
    assert(continuation);
    continuation->thunk = make_closure(block, args);
    if(unlikely(!continuation->thunk)) goto out_free;
    /*
     * stack the continuation.
     */
    list_add(&continuation->list, queue);
    err = 0;
    goto out;

    out_free:
    free(continuation);

    out:
    return err;
}

static struct continuation *pop_continuation(int cont)
{
    struct list_head *queue = get_continuation_queue(cont);
    struct continuation *continuation;
    if(unlikely(!queue)) return NULL;
    if(LIST_EMPTY(queue)) return NULL;
    continuation = list_entry(queue->next, struct continuation, list);
    list_del(&continuation->list);
    if(LIST_EMPTY(queue))
    {
        clear_continuation(&continuation_map, cont);
    }
    return continuation;
}

static int remove_continuation(int cont)
{
    struct continuation *continuation;
    continuation = pop_continuation(cont);
    if(!continuation) return -1;
    release_closure(continuation->thunk);
    free(continuation);
    return 0;
}

/*
 * Just return the continuation at the top of the list
 */
static struct continuation *peek_continuation(int cont)
{
    struct list_head *queue = get_continuation_queue(cont);
    struct continuation *continuation;
    if(unlikely(queue == NULL)) return NULL;
    if(LIST_EMPTY(queue)) return NULL;
    continuation = list_entry(queue->next, struct continuation, list);
    return continuation;
}

static int run_continuation(int cont)
{
    struct continuation *continuation;
    continuation = peek_continuation(cont);
    if(!continuation) return -1;
    continuation->thunk(); /* run the continuation block*/
    return 0;
}

struct continuation_scope
{
#define WIND (0x1)
#define UNWIND (0x2)
    int continuation;
    int state;
};

static struct continuation_scope *make_scope(int continuation)
{
    struct continuation_scope *scope = calloc(1, sizeof(*scope));
    assert(scope);
    scope->continuation = continuation;
    scope->state |= WIND;
    return scope;
}

#define PRINT_CONTINUATION(cont) do {                                   \
    printf("Inside continuation id [%d] with state [%d] in function [%s]\n", \
           (cont)->continuation, (cont)->state, __FUNCTION__);          \
} while(0)

static void continuation_2(struct scope *scope)
{
    struct continuation_scope *cont = scope->args;
    PRINT_CONTINUATION(cont);
    /*
     * unwind 
     */
    if(cont->state & WIND)
    {
        cont->state &= ~WIND;
        cont->state |= UNWIND;
        remove_continuation(cont->continuation);
    }
}

static void continuation_1(struct scope *scope)
{
    struct continuation_scope *cont = scope->args;
    PRINT_CONTINUATION(cont);
    if(cont->state & WIND)
    {
        stack_continuation(cont->continuation, (void*)continuation_2, (void*)cont);
    }
    else 
    {
        remove_continuation(cont->continuation);
    }
}

static void continuation_0(struct scope *scope)
{
    struct continuation_scope *cont = scope->args;
    PRINT_CONTINUATION(cont);
    if(cont->state & WIND)
    {
        stack_continuation(cont->continuation, (void*)continuation_1, (void*)cont);
    }
    else
    {
        remove_continuation(cont->continuation);
        printf("Continuation unwind for [%d]\n", cont->continuation);
        free(cont); /* last unwind*/
    }
}

static void *continuation_player_thread(void *unused)
{
    register int i;
    for(;;)
    {
        int run = 0;
        /*
         * Walk the bitmap and run the set continuations.  
         * Break when all are cleared.
         */
        for(i = 0; i < CONTINUATION_MAP_WORDS; ++i)
        {
            unsigned int mask = continuation_map.map[i];
            register int j;
            if(!mask) continue;
            for(j = 0; j < 32; ++j)
            {
                if( mask & ( 1 << j) )
                {
                    run = 1;
                    run_continuation((i << 5) + j);
                }
                
            }
        }
        /*
         * Reclaim closures if any.
         */
        reclaim_closure();
        if(!run) 
        {
            fprintf(stderr, "All continuations have been run\n");
            break;
        }
    }
    return NULL;
}

static void continuation_test(int continuations)
{
    int i;
    pthread_attr_t attr;
    pthread_t tid;
    init_continuation_map();
    for(i = 0; i < continuations; ++i)
    {
        int c = get_continuation(&continuation_map);
        assert(c >= 0);
        assert(stack_continuation(c, (void*)continuation_0, make_scope(c)) == 0);
    }
    pthread_attr_init(&attr);
    pthread_create(&tid, &attr, continuation_player_thread, NULL);
    pthread_join(tid, NULL);
}

int main(int argc, char **argv)
{
    int c = 10;
    if(argc > 1)
        c = atoi(argv[1]);
    if(!c) c = 10;
    if(c > CONTINUATION_MAP_BITS) c = CONTINUATION_MAP_BITS;
    continuation_test(c);
    return 0;
}

list.h

#ifndef _LIST_H_
#define _LIST_H_

#include <assert.h>

#ifdef __cplusplus
extern "C "{
#endif

struct list_head
{
    struct list_head *next;
    struct list_head *prev;
};

#define INIT_LIST_HEAD(name) { &(name), &(name) }

#define DECLARE_LIST_HEAD(name)                     \
    struct list_head name = INIT_LIST_HEAD(name)


#define LIST_HEAD_INIT(ptr) do {                \
    (ptr)->next = (ptr)->prev = ptr;        \
} while(0)

#define LIST_EMPTY(list)  ( (list) == (list)->next )

#define __list_add(element,a,b) do {            \
    (element)->next = b;                        \
    (element)->prev = a;                        \
    (a)->next = element;                        \
    (b)->prev = element;                        \
} while(0)

#define __list_del(a,b) do {                    \
    (a)->next = b;                              \
    (b)->prev = a;                              \
} while(0)

static __inline__ void list_head_init(struct list_head *head) {
    LIST_HEAD_INIT(head);
}

static __inline__ void list_add_tail(struct list_head *element,struct list_head *head) {
    struct list_head *tail = head->prev;
    assert(!element->next && !element->prev);
    __list_add(element,tail,head);
}

static __inline__ void list_add(struct list_head *element,struct list_head *head) {
    struct list_head *first = head->next;
    assert(!element->next && !element->prev);
    __list_add(element,head,first);
}

static __inline__ void list_del(struct list_head *element) {
    struct list_head *before = element->prev;
    struct list_head *after  = element->next;
    assert(before && after);
    __list_del(before,after);
    element->next = element->prev = NULL;
}

static __inline__ void list_del_init(struct list_head  *element) { 
    list_del(element); 
    LIST_HEAD_INIT(element);
} 

static __inline__ void list_splice(struct list_head *src,struct list_head *dst) {
    if(!LIST_EMPTY(src) ) {
        struct list_head *dst_first = dst->next;
        struct list_head *src_last  = src->prev;
        dst->next = src->next;
        src->next->prev = dst;   
        src_last->next = dst_first;
        dst_first->prev = src_last;
        LIST_HEAD_INIT(src);
    }
}

#define list_entry(ptr,cast,field)                                      \
    (cast*) ( (unsigned char*)(ptr) - (unsigned long)(&((cast*)0)->field) )

#define list_for_each(list,head)                            \
    for(list = (head)->next; list != (head); list = list->next)

#define list_sort_add(element,head,cast,field, cmp_fn) do { \
    struct list_head *__tmp = NULL;                         \
    __typeof__ (cmp_fn) *fn_ptr = &(cmp_fn);                \
    cast *__reference = list_entry(element,cast,field);     \
    list_for_each(__tmp,head) {                             \
        cast *__node = list_entry(__tmp,cast,field);        \
        if(fn_ptr(__reference,__node) < 0) {                \
            list_add_tail(element,__tmp);                   \
            goto __out;                                     \
        }                                                   \
    }                                                       \
    list_add_tail(element,head);                            \
    __out:                                                  \
    (void)"list";                                           \
}while(0)

#ifdef __cplusplus
}
#endif

#endif