[Stackless] For interested - an interlacing compiler for C that allows continuations

Paul Sheer psheer at icon.co.za
Sat Sep 7 12:59:34 CEST 2002


I am busy creating a C compiler that takes normal
C code and compiles into code that supports
continuations.

The output code is strict ANSI C and does not contain
machine dependent instructions.

Below is a proposal submitted for another purpose
(it is quite formal).

I thought the stackless list may be interested.
I am quite a way into the compiler now. I have
only to do "switch" statements "for" loops and
"do..while" loops. "if" and "while" statements
are done. the rest of the C language is also done.

-paul


-----------------------


Draft Proposal
==============

I would like to create a C compiler that compiles an
extended ANSI C language to strict ANSI C. The goal is to
allow a programmer to write C-like code which can run
multiple tasklets, but without requiring operating system
support for threads or processes. This will require the
compiler to textually "unroll" the C program into one that
does not use the native C stack for storage of local
function variables, nor shall it use the C stack for storage
of return addresses of function calls.

The advantages of this approach are:

    - It would allow multi-threaded code to be written,
    that, when compiled into strict ANSI C, would be
    entirely portable across a range of architectures
    regardless of operating support or implementation of
    threads.

    - It would allow support for continuations in C.

    - It would allow an enormous number of tasklets to run
    simultaneously, without the inherent overheads of
    threads. For instance, most operating systems are not
    able to run tens of thousands of simultaneous threads,
    whereas doing so using tasklets would present little
    trouble.

    - Systems that currently support continuations/tasklets
    are mostly scripting languages like (Scheme, Python).
    The remainder require operating system support, or an
    architecture dependent continuation library. Scripting
    languages have a huge speed deficit, whereas the speed
    of the proposed ANSI C code would be in the same order
    as regular compiled code..

    - Procedures for debugging of non-threaded ANSI C
    programs are well established.

    - Programmers would be able to write non-reentrant code,
    and have it still work correctly as tasklet.

    - Issues of locking an concurrent data access are mostly
    eliminated because tasklets would dictate yield to the
    scheduler.

The project idea came from the observation that
multi-threaded applications are difficult to debug and
inefficient. It is also difficult to make assurances about
the reliability of multi-threaded applications. I hope to
substantially corroborate these views in discussions about
locking, concurrent access to data structures, operating
system scheduler overheads, and hardware context switching
overheads.

Appended below represents an example module that precluded
my initial work on a parser to perform the compilation. A
substantial portion of the parser has already been written
using flex and bison (yacc).


Originality
-----------

At present I have no idea if such a compiler has ever been
attempted, or would be considered "novel" in terms of Ph.D.
requirements. I therefore earnestly desire input.


Scope
-----

My thesis would survey the current problems with concurrency
and other possible alternatives, and hence the viability and
benefit of the proposed approach.

A detailed design of the implementation would be explained:
variables with regard to the implementation and the range of
implementation options.

Sufficient example applications will be benchmarked, and
compared to other approaches, both in terms of application
development time, correctness, elegance, and performance.



----------

/*

We desire to translate C modules into modules that may run
as tasklets that do not make use of the C stack for
purposes of flow control and variable storage. Such a
tasklets is similar to a thread, except that it multitasks
cooperatively. A tasklet that blocks waiting for data, and
in the interim allows other tasklet to execute is said to
"yield" to other tasks. A task that allows other all tasks
to run through a single cycle of execution, and does this
explicitly and not because it is waiting for a file
descriptor, is also said to yield. This latter yield is
similar to a continuation in Scheme.

Here a "module" is a single C source file. Because the
translation process requires whole program analyses, the
translation is limited to a one-tasklet-per-C-source-file
approach. This means that all functions called from within
the module (where these called functions may yield), must
also be present in the module, and must be statically
declared.

*/

-- ----source - c-- -- ---------;

/* The following should represent every relevant aspect of
a C program, in terms of compiling a nested program into
one that does not use the C stack. The features supported
are as follows: */

/* External global variable */
extern char global_msg[];

/* Internal static global variable: */
static int n_msgs = 0;

/* external global function: */
void *malloc (int l);

/* Internal static function that cannot yield */
static int min (int a, int b)
{
    return a < b ? a : b;
}

/* Internal static function that contains a yield;
contains a call to an external function; contains internal
static variables and ordinary local variables; and
contains local variables nested within a scope. In terms
of internal variables, there are those that are
initialized to constant values, that are not initialized;
and that are initialized from the function arguments. */
char *read_all (int fd, int total)
{
    static int count;
    char *buf;
    int done = 0, alloced, _total = total;
    buf = malloc (alloced = 256);
    while (_total > 0) {
	int c;
	wait_on_read (fd);
	c = read (fd, buf + done, min (alloced - done, _total));
	if (c <= 0)
	    break;
	done += c;
	count += c;
	_total -= c;
	if (done == alloced) {
	    alloced += 256;
	    buf = (char *) realloc (buf, alloced);
	}
    }
    n_msgs++;
    buf[done] = '\0';
    return buf;
}

/* Entry point of the module. Contains calls to a local
function with one or more arguments, from which a result
must be returned, and where the local function contains a
block. */
void my_tasklet (void *data)
{
    char *s, *c;
    struct thread_data *d = (struct thread_data *) data;
    s = read_all (d->fd, d->msg_size);
    if (*s == 'C') {
	c = read_all (d->fd, d->next_msg_size);
	strncpy (global_msg, c, MAX_MSG_SIZE);
    }
    tasklet_exit ();
}

/* The compilation of the above tasklet is now shown. */

---------translation-- -- -----;

/* Since the declaratin is global, no translation is
required: */
extern char global_msg[];

/* Since the function is external, it is assumed to not
yield. */
void *malloc (int l);

/* Since there are no yields within this function, no
translation is required: */
static int min (int a, int b)
{
    return a < b ? a : b;
}

/* We have two static variables. One global to the moduel,
and one local to a function. These are treated the same:
*/
struct NAMESPACE {
    int F_read_all_F_count;
    int n_msgs;
};

/* This is how they are initialized: */
void local_namespace_init (struct NAMESPACE *p)
{
    p->F_read_all_F_count = 0;
    p->n_msgs = 0;
}

/* For each function, a namespace is declared that would
normally be pushed onto the stack. All state informatin is
stored here: */
struct NAMESPACE_read_all {
/* The namespace of any functions called by read_all(). In
this case, read_all calls no functions that contain a
yield. There it remains unused: */
    void *FUNCTION_NAMESPACE;
/* Static variables local to the function, and static
variables local to this file. This pointer will be
numerically identically for all function namespaces, since
it is global to the module: */
    struct NAMESPACE *NAMESPACE;
/* Return address of caller to read_all() */
    function *CALLER;
/* Result (to be returned to the caller) of function
read_all() */
    char *FUNCTION_RESULT;
/* Variables local to read_all(): */
    char *buf;
    int done;
    int alloced;
    int c;
    int fd;
    int total;
    int _total;
};

/* Every yieldable function has a function to initialize
the read_all() namesoace. This is analogous to the entry
point of a function (for normal compiled assembly
language), where initial values for variables are pushed
onto the stack. */
void read_all_INIT (struct NAMESPACE_read_all *_o, int fd, int total)
{
/* first we make local copies of the function arguments */
    _o->fd = fd;
    _o->total = total;

    {
	int done = 0;
	int _total = _o->total;
/* now we initialize the variables declared at the top of
the function */
	_o->done = done;
	_o->_total = _total;
    }
}

/* For each conditional jump in the program, we need a
function: */
function *read_all_CODEPOINT_1 (struct NAMESPACE_read_all *_o,
				void **new_o)
{
    _o->buf = malloc (_o->alloced = 256);
    return read_all_CODEPOINT_2;
}

/* The conditional jump point of the while loop */
function *read_all_CODEPOINT_2 (struct NAMESPACE_read_all * _o,
				void **new_o)
{
/*    while (_total > 0) { */
    if (_o->_total > 0)
	return read_all_CODEPOINT_3;
    else
	return read_all_CODEPOINT_5;
}

/* The actual point of yield. Execution is suspended (by
returning NULL), and  a callback (for when readable data
is available) is added to the global select() lopp: */
function *read_all_CODEPOINT_3 (struct NAMESPACE_read_all * _o,
				void **new_o)
{
    add_read_avail_callback (_o->fd, read_all_CODEPOINT_4);
    return NULL;
}

/* select() has indicated a change of status. So we
continue from flow point "4": */
function *read_all_CODEPOINT_4 (struct NAMESPACE_read_all * _o,
				void **new_o)
{
/*	c = read (fd, buf + done, min (alloced - done, _total)); */
    _o->c =
	read (_o->fd, _o->buf + _o->done,
	      min (_o->alloced - _o->done, _o->_total));
/*	if (c <= 0) */
/*	    break; */
    if (_o->c <= 0)
	return read_all_CODEPOINT_5;
/* The follow statement block contains only benign
statements. It can be inserted inline: */
    done += c;
    _o->NAMESPACE->count += c;
    _o->_total -= c;
/* The following statement block contains no yields, hence
it also can be inserted inline. */
    if (_o->done == _o->alloced) {
	_o->alloced += 256;
	_o->buf = (char *) realloc (_o->buf, _o->alloced);
    }
/* Now continue at the top of the while loop */
    return read_all_CODEPOINT_2;
}

/* The point after the while loop. */
function *read_all_CODEPOINT_5 (struct NAMESPACE_read_all * _o,
				void **new_o)
{
/* Last operation in function: */
    _o->NAMESPACE->n_msgs++;
    _o->buf[_o->done] = '\0';
/* Return from the function: */
    _o->FUNCTION_RESULT = _o->buf;
    return read_all_RETURN;
}

/* A return is analogous to a C when ordinarily compiled
into assembly language. First, the result is saved, and
then the calling namespace is restored. */
function *read_all_RETURN (struct NAMESPACE_read_all * _o, void **new_o)
{
    *new_o = _o->CALLER_NAMESPACE;
    return _o->CALLER;
}

/* The second function is declared similarly. On of the
only differences is that FUNCTION_RESULT is not needed,
since (besides the fact that this function is the entry
point of the module, and therefore cannot have a return
value) the return value is void. The other difference is
that FUNCTION_NAMESPACE is actually used this time to
perform a call: i.e. the call to read_all() above. */
struct NAMESPACE_my_tasklet {
    void *FUNCTION_NAMESPACE;
    struct NAMESPACE *NAMESPACE;
    function *CALLER;
/*    void FUNCTION_RESULT; no result */
    void *data;
    char *s;
    char *c;
    struct thread_data *d;
};

/* Initialization is similar to the read_all() call above.
*/
void my_tasklet_INIT (struct NAMESPACE_my_tasklet *_o, void *data)
{
    _o->data = data;

    {
	struct thread_data *d = (struct thread_data *) data;
	_o->d = d;
    }
}

/* Here is a function call proper, being the first
action on entering the function my_tasklet(): */
function *my_tasklet_CODEPOINT_1 (struct NAMESPACE_my_tasklet *_o,
				  void **new_o)
{
    struct NAMESPACE_read_all *p;
/* Create a namespace for the function - analogous to
stack space for the functions internal variables: */
    p = malloc (sizeof (struct NAMESPACE_read_all));
    _o->FUNCTION_NAMESPACE = (void *) p;
/* Perform initializatopm of the namespace - analogous to
declarations of values of internal variables: */
    read_all_INIT (p, _o->d->fd, _o->d->msg_size);
/* Store the value of the caller - analogous to pushing
the return address onto the stack: */
    p->CALLER = my_tasklet_CODEPOINT_2;
/* Then of course the current namespace which must be
restored at the end of the call: */
    p->CALLER_NAMESPACE = _o;
/* Set the current namespace of this file (i.e. all static variables) */
    p->NAMESPACE = _o->NAMESPACE;
/* Now set the current namespace to the new namespace */
    *new_o = (void *) p;
/* and return the new point of execution. */
    return read_all_CODEPOINT_1;
}

/* Having completed the function call, the following
restores the namespace, and obtains the function's result:
*/
function *my_tasklet_CODEPOINT_2 (struct NAMESPACE_my_tasklet * _o,
				  void **new_o)
{
/* Get the result of the function call: */
    _o->s =
	((struct NAMESPACE_read_all *) _o->FUNCTION_NAMESPACE)->
	FUNCTION_RESULT;
/* Now free the namespace */
    free (_o->FUNCTION_NAMESPACE);

/* Proceed with execution: the following condition can be
inlined with the retrieval of the result above: */
/*    if (*s == 'C') { */
    if (*_o->s == 'C') {
	return my_tasklet_CODEPOINT_3;
    } else {
	return my_tasklet_CODEPOINT_5;
    }
}

/* A second function call: */
function *my_tasklet_CODEPOINT_3 (struct NAMESPACE_my_tasklet * _o,
				  void **new_o)
{
    struct NAMESPACE_read_all *p;
    p = malloc (sizeof (struct NAMESPACE_read_all));
    _o->FUNCTION_NAMESPACE = (void *) p;
    read_all_INIT (p, _o->d->fd, _o->d->next_msg_size);
    p->CALLER = my_tasklet_CODEPOINT_4;
    p->CALLER_NAMESPACE = _o;
    p->NAMESPACE = _o->NAMESPACE;
    *new_o = (void *) p;
    return read_all_CODEPOINT_1;
}

/* Once, again, obtain the result, and proceed with
execution: */
function *my_tasklet_CODEPOINT_4 (struct NAMESPACE_my_tasklet * _o,
				  void **new_o)
{
    _o->c =
	((struct NAMESPACE_read_all *) _o->FUNCTION_NAMESPACE)->
	FUNCTION_RESULT;
    free (_o->FUNCTION_NAMESPACE);
    strncpy (global_msg, _o->c, MAX_MSG_SIZE);
    return my_tasklet_CODEPOINT_5;
}

/* This is the exit point of the tasklet: */
function *my_tasklet_CODEPOINT_5 (struct NAMESPACE_my_tasklet * _o,
				  void **new_o)
{
/* These free's parallel the mallocs in my_tasklet() below */
/*    tasklet_exit (); */
    free (_o->NAMESPACE);
    free (_o);
    *new_o = NULL;
    return TASKLET_DONE;

/* Not reached */
    return my_tasklet_RETURN;
}

/* This is the exit point of the function. It is never called: */
function *my_tasklet_RETURN (struct NAMESPACE_my_tasklet * _o,
			     void **new_o)
{
/*    _o->FUNCTION_RESULT = (void); */
    *new_o = _o->CALLER_NAMESPACE;
    return _o->CALLER;
}

/* The entry point for the entire module is defined below.
For convenience this is the same name as the function.
This function is externally callable with
tasklet_start(my_tasklet); */
function *my_tasklet (void **new_o, void *data)
{
    struct NAMESPACE_my_tasklet *p;
/* Create and initialize the local function namespace: */
    p = malloc (sizeof (struct NAMESPACE_my_tasklet));
    my_tasklet_INIT (p, data);
/* Create and initialize namespace of the module: */
    p->NAMESPACE = malloc (sizeof (struct NAMESPACE));
    local_namespace_init (p->NAMESPACE);
/* Return the initial function namespace to the schedular: */
    *new_o = p;
/* Return the starting execution point: */
    return my_tasklet_CODEPOINT_1;
}


/* Now that the "unrolling" of the C language is clearly
defined, above is clearly defined, the associated
scheduler is simple to implement: */

--------scheduler-- -- ------;

struct tasklet {
    function *function;
    function1 *waiting_for_data;
    void *data;
    void *o;			/* namespace */
};

struct {
    struct tasklet *next;
} tasklet_list = {
NULL};

/* Initializing a tasklet can be done by adding the
tasklets current namespace, and current execution point to
the tasklet list. */
struct tasklet *tasklet_start (void (*start_function) (void **, void *),
			       void *data)
{
    function *first;
    void *_o;
    first = (*start_function) (&_o, data);
    return schedular_add_tasklet (first, _o);
}

function *continuation;
struct tasklet *current_tasklet;

struct {
    function *function;
    function *waiting_for_data;
    void *data;
    struct tasklet *tasklet;
    int fd;
} callback[FD_SETSIZE] = { {
0, 0, 0, 0, -1},...};		/* FIXME: initialize to zero. fd = -1 */

/* A tasklet can call one of these five functions to yield
to other tasklets: */
void add_read_avail_callback (int fd, function * f)
{
    callbacks[fd].function = f;
    callbacks[fd].tasklet = current_tasklet;
    callbacks[fd].tasklet->fd = fd;
    FD_SET (fd, &global_read_set);
    global_max_fd = max (fd, global_max_fd);
}

void add_readoob_avail_callback (int fd, function * f)
{
    callbacks[fd].function = f;
    callbacks[fd].tasklet = current_tasklet;
    callbacks[fd].tasklet->fd = fd;
    FD_SET (fd, &global_oob_set);
    global_max_fd = max (fd, global_max_fd);
}

void add_write_space_callback (int fd, function * f)
{
    callbacks[fd].function = f;
    callbacks[fd].tasklet = current_tasklet;
    callbacks[fd].tasklet->fd = fd;
    FD_SET (fd, &global_write_set);
    global_max_fd = max (fd, global_max_fd);
}

/* And explicit yield is done by returning NULL, preceded
by the yield() call. */
void yield (int fd, function * f)
{
    continuation = f;
}

/* And wait_for_data is done by returning NULL, preceded
by the wait_for_data() call. This is like a genuine
continuation. The caller can awaken the task by passing a
struct cast to (void *). */
void wait_for_data (int fd, function1 * f)
{
    current_tasklet->waiting_for_data = f;
    current_tasklet->data = NULL;
}

/* This is the parent half of wait_for_data(): */
void awaken_tasklet (struct tasklet *t, void *data)
{
    if (!t->waiting_for_data) {
	fprintf (stderr,
		 "attempt to awaken thread that is not waiting for data\n");
	abort ();
    }
    t->data = data;
}

/* A single loop of the scheduler: */
void schedular_run (void)
{
    int r, fd;
    struct timeval tv;
    fd_set rd, wr, ob;
    int at_least_one_continuation = 0;
    struct tasklet *p;
    continuation = NULL;
    for (p = (struct tasklet *) &tasklet_list; p->next;) {
	struct tasklet *t;
	t = p->next;
	current_tasklet = t;
/* A pause that is waiting for the tasklet to be passed some data */
	if (t->waiting_for_data && t->data) {
	    t->function = (*t->waiting_for_data) (t->o, &t->o, t->data);
	    t->data = NULL;
	    t->waiting_for_data = NULL;
	}
/* Run task until it "blocks" by returning NULL: */
	while (t->function && !t->killed) {
	    t->function = (*t->function) (t->o, &t->o);
	    if (t->function == TASKLET_DONE)
		t->killed = 1;
	}
/* The task has either asked for a wait on fd read/write,
OR it has merely yielded to other tasks. In the latter
case, "continuation" would have been set: */
	if (continuation) {
	    t->function = continuation;
	    continuation = NULL;
	    at_least_one_continuation = 1;
	}
	if (t->killed) {
	    callbacks[t->fd]->tasklet = 0;
	    callbacks[t->fd]->function = 0;
	    p->next = p->next->next;
	    free (t);
	} else {
	    p = p->next;
	}
    }
    tv.tv_usec = 0;
    tv.tv_sec = 0;
    copy_global_fd_sets (&rd, &wr, &ob);
    r = select (global_max_fd + 1, &rd, &wr, &ob,
		at_least_one_continuation ? &tv : 0);
    assert (r >= 0);
    if (!r)
	zero_fd_sets (&rd, &wr, &ob);
    for_all_set_fds (&rd, fd) {
	callbacks[fd].tasklet->function = callbacks[fd].function;
	callbacks[fd].tasklet->fd = -1;
	callbacks[fd].function = NULL;
	FD_CLR (fd, &global_read_set);
    }
    for_all_set_fds (&wr, fd) {
	callbacks[fd].tasklet->function = callbacks[fd].function;
	callbacks[fd].tasklet->fd = -1;
	callbacks[fd].function = NULL;
	FD_CLR (fd, &global_write_set);
    }
    for_all_set_fds (&ob, fd) {
	callbacks[fd].tasklet->function = callbacks[fd].function;
	callbacks[fd].tasklet->fd = -1;
	callbacks[fd].function = NULL;
	FD_CLR (fd, &global_oob_set);
    }
}




Paul Sheer Consulting IT Services . . Tel . . . +27 (0)21 6869634
Email . . . psheer at icon.co.za . . . . . . Pager . . . 088 0057245
Linux development, cryptography, recruitment,  support,  training
http://www.icon.co.za/~psheer . . . . http://rute.sourceforge.net
L I N U X . . . . . . . . . . . .  The Choice of a GNU Generation

_______________________________________________
Stackless mailing list
Stackless at www.tismer.com
http://www.tismer.com/mailman/listinfo/stackless



More information about the Stackless mailing list