info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
cheesy multithreading hack in C
3 views
Skip to first unread message
Will Ware
Sep 19, 2001, 9:41:56 AM9/19/01
to
/*****************************************************
* This is the beginnings of a threading system
* for C programs running on x86 Linux boxes with
* current versions of gcc. When finished, it
* should support thousands of threads pretty
* easily. The only bummer is that threading is
* not preemptive; you must populate your code
* with "context_switch()" calls to yield the
* processor to other threads.
*
* It's important that swap_sp() must not be
* inlined, because of the special tinkering it
* does with the stack. If you go for optimization
* of "-O3" or above, you must use "-fno-inline"
* to avoid this.
*
* gcc -Wall -O3 -fno-inline -o foo foo.c
*****************************************************/
* This is the beginnings of a threading system
* for C programs running on x86 Linux boxes with
* current versions of gcc. When finished, it
* should support thousands of threads pretty
* easily. The only bummer is that threading is
* not preemptive; you must populate your code
* with "context_switch()" calls to yield the
* processor to other threads.
*
* It's important that swap_sp() must not be
* inlined, because of the special tinkering it
* does with the stack. If you go for optimization
* of "-O3" or above, you must use "-fno-inline"
* to avoid this.
*
* gcc -Wall -O3 -fno-inline -o foo foo.c
*****************************************************/
#include <stdio.h>
/* We may want plenty of stack. Here is how to get
* it while keeping gcc happy. It appears possible
* to set this thing to be huge: it doesn't seem
* to mind 32 MB!
*/
asm(".section .bss");
asm(".align 4");
asm(".globl mystackspace");
asm("mystackspace: .space 4096"); /* 1024 ints */
/* asm("mystackspace: .space 32000000"); */
/* Store the old stack pointer from the previous
* context, and swap in a new stack pointer.
*/
void swap_sp(int *newsp, int **oldsp)
{
asm("movl 8(%esp), %eax");
asm("movl 12(%esp), %ecx");
asm("movl %esp, (%ecx)");
asm("movl %eax, %esp");
asm("popl %ebp");
asm("ret");
}
/*****************************************************
* Right now we just maintain two contexts, one
* for main() and one for child(), so the 'phase'
* variable just ping-pongs back and forth between
* them. Later we'll want many thousands of
* contexts running at once and we'll need a
* fancier control mechanism, and we'll need to
* track lots of stack pointers, not just these
* two.
*****************************************************/
int phase = 0;
int *main_sp, *extra_sp;
void context_switch(void)
{
phase = 1 - phase;
if (phase)
swap_sp(extra_sp, &main_sp);
else
swap_sp(main_sp, &extra_sp);
}
/*****************************************************
* Here are the two functions that will represent
* the two threads.
*****************************************************/
void child(int x, int y)
{
printf("child %d %d: step 1\n", x, y);
context_switch();
printf("child %d %d: step 2\n", x, y);
context_switch();
printf("child %d %d: step 3\n", x, y);
context_switch();
}
/* This causes a segfault on completion, I dunno why.
* My guess is that allocating space for 'i' somehow
* messes up my assumptions about stack usage, or I've
* hopelessly abused the ebp register.
*/
void _child(int x, int y)
{
int i;
for (i = 0; i < 3; i++)
{
printf("child %d %d: step %d\n", x, y, i);
context_switch();
}
}
int main(void)
{
extern int mystackspace[];
extra_sp = mystackspace + 1024;
*(--extra_sp) = 5; /* second arg: y */
*(--extra_sp) = 2; /* first arg: x */
*(--extra_sp) = 0; /* ??????? */
*(--extra_sp) = (int) child;
*(--extra_sp) = 0; /* fake %ebp register */
/**********************************************
* Using a for loop here causes a segfault on
* the first context switch. Why the heck is
* that?
*********************************************/
printf("main: step 1\n");
context_switch();
printf("main: step 2\n");
context_switch();
printf("main: step 3\n");
context_switch();
printf("main: step 4\n");
return 0;
}
Will Ware
Sep 19, 2001, 3:04:00 PM9/19/01
to
/*****************************************************
* This is the beginnings of a threading system
* for C programs running on x86 Linux boxes with
* current versions of gcc. When finished, it
* should support thousands of threads pretty
* easily. The only bummer is that threading is
* not preemptive; you must populate your code
* with "context_switch()" calls to yield the
* processor to other threads.
*
* I decided to simplify my life by just making* This is the beginnings of a threading system
* for C programs running on x86 Linux boxes with
* current versions of gcc. When finished, it
* should support thousands of threads pretty
* easily. The only bummer is that threading is
* not preemptive; you must populate your code
* with "context_switch()" calls to yield the
* processor to other threads.
*
* the assumption that no optimization is done at
* all, no "-O", "-O2", "-O3".
*
* gcc -Wall -o foo foo.c
*****************************************************/
#include <stdio.h>
/* We may want plenty of stack. Here is how to get
* it while keeping gcc happy. It appears possible
* to set this thing to be huge: it doesn't seem
* to mind 32 MB!
*/
asm(".section .bss");
asm(".align 4");
asm(".globl mystackspace");
asm("mystackspace: .space 4096"); /* 1024 ints */
/* asm("mystackspace: .space 32000000"); */
/*****************************************************
* Right now we just maintain two contexts, one
* for main() and one for child(), so the 'phase'
* variable just ping-pongs back and forth between
* them. Later we'll want many thousands of
* contexts running at once and we'll need a
* fancier control mechanism, and we'll need to
* track lots of stack pointers, not just these
* two.
*****************************************************/
int phase = 0;
int *main_sp, *extra_sp;
void context_switch(void)
{
phase = 1 - phase;
if (phase)
{
/* save current stack pointer in main_sp,
fetch new stack pointer from extra_sp */
asm("movl extra_sp, %eax");
asm("movl $main_sp, %ecx");
asm("movl %esp, (%ecx)");
asm("movl %eax, %esp");
asm("popl %ebp");
asm("ret");
}
else
{
/* save current stack pointer in extra_sp,
fetch new stack pointer from main_sp */
asm("movl main_sp, %eax");
asm("movl $extra_sp, %ecx");
asm("movl %esp, (%ecx)");
asm("movl %eax, %esp");
asm("popl %ebp");
asm("ret");
}
}
/*****************************************************
* Here are the two functions that will represent
* the two threads.
*****************************************************/
void child(int x, int y)
{
int i;
for (i = 0; i < 4; i++)
{
printf("child %d %d: step %d\n", x, y, i);
context_switch();
}
while (1)
context_switch();
}
int main(void)
{
extern int mystackspace[];
extra_sp = mystackspace + 1024;
*(--extra_sp) = 5; /* second arg: y */
*(--extra_sp) = 2; /* first arg: x */
*(--extra_sp) = 0; /* ????? */
*(--extra_sp) = (int) child;
*(--extra_sp) = 0; /* fake %ebp register */
{
int i;
for (i = 0; i < 4; i++)
{
printf("main: step %d\n", i);
context_switch();
}
printf("main: step %d\n", i);
}
return 0;
}
Will Ware
Sep 20, 2001, 9:18:28 AM9/20/01
to
/*****************************************************
* This is the beginnings of a threading system
* for C programs running on x86 Linux boxes with
* current versions of gcc. When finished, it
* should support thousands of threads pretty
* easily. The only bummer is that threading is
* not preemptive; you must populate your code
* with "context_switch()" calls to yield the
* processor to other threads.
*
* I decided to simplify my life: NO OPTIMIZATION!* This is the beginnings of a threading system
* for C programs running on x86 Linux boxes with
* current versions of gcc. When finished, it
* should support thousands of threads pretty
* easily. The only bummer is that threading is
* not preemptive; you must populate your code
* with "context_switch()" calls to yield the
* processor to other threads.
*
* No "-O", "-O2", "-O3". The stack effects are
* too unpredictable. Just type:
*
* gcc -Wall -o foo foo.c
*****************************************************/
#include <stdio.h>
#include <stdlib.h>
void context_switch_helper(int *newsp, int **oldsp)
{
/************************************************
* GCC automatically does this at the beginning:
* pushl %ebp
* movl %esp, %ebp
*
* At this point, the stack looks like this:
* (%ebp) 4(%ebp) 8(%ebp) 12(%ebp)
* caller_ebp, return_vector, newsp, oldsp
************************************************/
asm("movl 12(%ebp), %ecx"); /* store away old stack pointer */
asm("movl %esp, (%ecx)");
asm("movl 8(%ebp), %esp"); /* establish new stack pointer */
/************************************************
* GCC automatically does this at the end:
* popl %ebp
* ret
***********************************************/
}
/*****************************************************
* Right now we just maintain two contexts, one for main()
* and one for child(), so the 'phase' variable just
* ping-pongs back and forth between them. Later we'll want
* many thousands of contexts running at once and we'll need
* a fancier control mechanism, and we'll need to track lots
* of stack pointers, not just these two.
*****************************************************/
int phase = 0;
int *main_sp, *extra_sp;
void context_switch(void)
{
phase = 1 - phase;
if (phase)
context_switch_helper(extra_sp, &main_sp);
else
context_switch_helper(main_sp, &extra_sp);
}
void child(int x, double y)
{
int i;
for (i = 0; i < 4; i++)
{
printf("child %d %f: step %d\n", x, y, i);
context_switch();
}
}
void caller(void)
{
/* This just hides the messiness of setting up the args
* for child. If done explicitly, it's a horror show.
*/
child(4, 2.71828);
while (1)
context_switch();
}
#define NUMTHREADS 2000
#define STACKSIZE 4096
int stackbunch[NUMTHREADS][STACKSIZE];
int main(void)
{
int i;
extra_sp = stackbunch[0] + STACKSIZE;
*(--extra_sp) = (int) caller;
*(--extra_sp) = 0;
for (i = 0; i < 10; i++)
Will Ware
Sep 23, 2001, 10:20:16 AM9/23/01
to
#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.2.1).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `!/bin/sh' line above, then type `sh FILE'.
#
# Made on 2001-09-23 10:19 EDT by <ww...@localhost.localdomain>.
# Source directory was `/home/wware/mmt2'.
#
# Existing files will *not* be overwritten unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 2362 -r--r--r-- README
# 711 -r--r--r-- Makefile
# 911 -r--r--r-- simple.c
# 2396 -r--r--r-- conway.c
# 11217 -r-xr-xr-x process.py
# 2773 -r--r--r-- thr.c
# 778 -r--r--r-- thr.h
#
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
if test "$gettext_dir" = FAILED && test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
set `$dir/gettext --version 2>&1`
if test "$3" = GNU
then
gettext_dir=$dir
fi
fi
if test "$locale_dir" = FAILED && test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
echo=echo
else
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
if touch -am -t 200112312359.59 $$.touch >/dev/null 2>&1 && test ! -f 200112312359.59 -a -f $$.touch; then
shar_touch='touch -am -t $1$2$3$4$5$6.$7 "$8"'
elif touch -am 123123592001.59 $$.touch >/dev/null 2>&1 && test ! -f 123123592001.59 -a ! -f 123123592001.5 -a -f $$.touch; then
shar_touch='touch -am $3$4$5$6$1$2.$7 "$8"'
elif touch -am 1231235901 $$.touch >/dev/null 2>&1 && test ! -f 1231235901 -a -f $$.touch; then
shar_touch='touch -am $3$4$5$6$2 "$8"'
else
shar_touch=:
echo
$echo 'WARNING: not restoring timestamps. Consider getting and'
$echo "installing GNU \`touch', distributed in GNU File Utilities..."
echo
fi
rm -f 200112312359.59 123123592001.59 123123592001.5 1231235901 $$.touch
#
if mkdir _sh15408; then
$echo 'x -' 'creating lock directory'
else
$echo 'failed to create lock directory'
exit 1
fi
# ============= README ==============
if test -f 'README' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'README' '(file already exists)'
else
$echo 'x -' extracting 'README' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'README' &&
This is a massive-multithreading system for C programs. It makes it
easy to write programs running huge numbers of threads. This can be
useful for games, simulations, and webservers.
X
The source file 'simple.c' shows a simple example of how to use this
system. The "#pragma par on" and "#pragma par_off" statements indicate
which functions should be parallelized. The parallelized functions
look pretty normal in simple.c; you don't need to change your source
code very much to make it work.
X
But you _do_ need to explicitly say where you want context switches to
happen, which is done with the "CSW" marker. This sounds like a
horrible thing, but there is a freedom in placing context switches
yourself. You therefore can say with certainty when will _not_ happen,
and that allows you to assume certain kinds of stability in certain
regions of your code.
X
Your code is processed by process.py, a Python script that translates
the C source file into a second C source file, where each parallelized
function has been turned into a sort of state machine, with each state
representing the code between a pair of context switches. To permit
one parallelized function to call another, and to keep the state
machines fully reentrant, there are frames that maintain the state of
each thread at each function call level. Every frame links to its
caller, and to its thread.
X
'simple.c' sets up 100,000 threads all running the same couple
function. Any thread that gets erroneous results will cause an error
message. All the threads succeed, so you get an "All is well" message
at the end.
X
The new_thread() function creates a new thread with a function. There
is presently no really clean way to pass arguments into a thread. The
'conway.c' example shows an ugly way to pass in arguments.
X
The step_thread() function advances the whole collection of threads
by a number of steps. Each step represents one thread's progress from
one context switch to the next one. Threads take turns in a circular
fashion, each taking a step. step_thread() returns 1 when all the
threads have finished running.
X
The 'conway.c' example illustrates Conway's game of life, which is a
cellular automaton. This system is more general than you need for a
CA, as each thread in this system can be running a different program
or at a different point in the same program as all the other threads.
SHAR_EOF
(set 20 01 09 23 00 08 37 'README'; eval "$shar_touch") &&
chmod 0444 'README' ||
$echo 'restore of' 'README' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'README:' 'MD5 check failed'
0cacc428bdf4867caa40cd3433d14fb3 README
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'README'`"
test 2362 -eq "$shar_count" ||
$echo 'README:' 'original size' '2362,' 'current size' "$shar_count!"
fi
fi
# ============= Makefile ==============
if test -f 'Makefile' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'Makefile' '(file already exists)'
else
$echo 'x -' extracting 'Makefile' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'Makefile' &&
CC = gcc
# CFLAGS = -Wall -g
CFLAGS = -Wall -O3
X
all: quux
X
clean:
X rm -rf *~ *.o quux* foo* core zz
X
###################################
X
thr.o: thr.c thr.h
X
###################################
X
quux.c: simple.c process.py
X ./process.py < simple.c > quux.c
X
quux: quux.c thr.o thr.h
X $(CC) $(CFLAGS) -o quux quux.c thr.o
X
###################################
X
foo.c: conway.c process.py
X ./process.py < conway.c > foo.c
X
foo: foo.c thr.o thr.h
X $(CC) $(CFLAGS) -o foo foo.c thr.o
X
########################################
X
wiki:
X ./towiki.py README Makefile simple.c conway.c \
X process.py thr.c thr.h towiki.py > zz
X
shar:
X /usr/bin/shar README Makefile simple.c conway.c \
X process.py thr.c thr.h > zz.shar
SHAR_EOF
(set 20 01 09 23 10 19 01 'Makefile'; eval "$shar_touch") &&
chmod 0444 'Makefile' ||
$echo 'restore of' 'Makefile' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'Makefile:' 'MD5 check failed'
01a8a8e903340658b98bfef03b053931 Makefile
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'Makefile'`"
test 711 -eq "$shar_count" ||
$echo 'Makefile:' 'original size' '711,' 'current size' "$shar_count!"
fi
fi
# ============= simple.c ==============
if test -f 'simple.c' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'simple.c' '(file already exists)'
else
$echo 'x -' extracting 'simple.c' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'simple.c' &&
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
X
#include "thr.h"
X
#pragma par_on
X
int add (int x, int y)
{
X int z;
X z = x + y;
X CSW;
X return z;
}
X
void caller (void)
{
X int result;
X int i, plugh[8];
X /* Make sure arrays work, and context switches don't
X * break for-loops.
X */
X for (i = 0; i < 8; i++)
X {
X plugh[i] = 0xdeadbeef;
X CSW;
X }
X /* Test calls to other parallelized functions. */
X result = add(4, 3) * add(5, 6);
X CSW;
X result += i;
X CSW;
X /* Complain if anything goes unexpectedly. */
X if (result != (4 + 3) * (5 + 6) + 8 ||
X plugh[5] != 0xdeadbeef)
X {
X fprintf(stderr, "Yikes!\n");
X exit(1);
X }
}
X
#pragma par_off
X
#define NUMTHREADS 100000
X
int
main (void)
{
X int i;
X for (i = 0; i < NUMTHREADS; i++)
X new_thread(caller, sizeof(struct caller_frame));
X while (step_thread(1000) == 0);
X printf("All is well\n");
X return 0;
}
SHAR_EOF
(set 20 01 09 22 23 11 03 'simple.c'; eval "$shar_touch") &&
chmod 0444 'simple.c' ||
$echo 'restore of' 'simple.c' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'simple.c:' 'MD5 check failed'
d54cd853c245daa95325b0cb6f441423 simple.c
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'simple.c'`"
test 911 -eq "$shar_count" ||
$echo 'simple.c:' 'original size' '911,' 'current size' "$shar_count!"
fi
fi
# ============= conway.c ==============
if test -f 'conway.c' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'conway.c' '(file already exists)'
else
$echo 'x -' extracting 'conway.c' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'conway.c' &&
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
X
#include "thr.h"
X
#define NUMROWS 30
#define NUMCOLS 40
X
int conway_board[NUMCOLS][NUMROWS];
X
#pragma par_on
X
void conway_behavior(void)
{
X int nextstatus, sum;
X int row, col; /* we'll initialize these from main() */
X int row1, col1;
X
X while (1)
X {
X /* These threads are all in lock-step, so we let them alternate.
X * First they all compute their sums and the next statuses, and
X * then they context switch, and then they each update their
X * entry in conway_board. Then they context switch again, so that
X * the values in conway_board are stable while everybody is doing
X * their sums.
X */
X sum = 0;
X for (row1 = row - 1; row1 < row + 2; row1++)
X for (col1 = col - 1; col1 < col + 2; col1++)
X {
X if (!(row1 == row && col1 == col) &&
X row1 >= 0 && row1 < NUMROWS &&
X col1 >= 0 && col1 < NUMCOLS)
X sum += conway_board[col1][row1];
X }
X if ((sum == 2 && conway_board[col][row]) || sum == 3)
X nextstatus = 1;
X else
X nextstatus = 0;
X CSW;
X conway_board[col][row] = nextstatus;
X CSW;
X }
}
X
#pragma par_off
X
int main(int argc, char *argv[])
{
X int i, j;
X struct thread *thr;
X struct conway_behavior_frame *frame;
X
X /* set up a thread for each pixel */
X for (j = 0; j < NUMROWS; j++)
X for (i = 0; i < NUMCOLS; i++)
X {
X thr = new_thread(conway_behavior,
X sizeof(struct conway_behavior_frame));
X frame = (struct conway_behavior_frame *) thr->frame;
X frame->col = i;
X frame->row = j;
X }
X
X /* make a glider */
X conway_board[2][1] = 1;
X conway_board[3][2] = 1;
X conway_board[1][3] = 1;
X conway_board[2][3] = 1;
X conway_board[3][3] = 1;
X
X /* make a traffic light */
X conway_board[10][2] = 1;
X conway_board[11][2] = 1;
X conway_board[12][2] = 1;
X
X while (1)
X {
X if (argc == 1)
X {
X /* display pixels normally */
X for (j = 0; j < NUMROWS; j++)
X {
X for (i = 0; i < NUMCOLS; i++)
X printf("%c", ".*"[conway_board[i][j]]);
X printf("\n");
X }
X printf("---------------\n");
X }
X else
X {
X /* Print a 'g' for each generation. This is only good
X * for showing that generations are quick.
X */
X printf("g");
X fflush(stdout);
X }
X step_thread(2 * NUMROWS * NUMCOLS);
X }
X
X return 0;
}
SHAR_EOF
(set 20 01 09 22 23 12 34 'conway.c'; eval "$shar_touch") &&
chmod 0444 'conway.c' ||
$echo 'restore of' 'conway.c' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'conway.c:' 'MD5 check failed'
ab4dfadf38eae36c060df6204e6dd309 conway.c
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'conway.c'`"
test 2396 -eq "$shar_count" ||
$echo 'conway.c:' 'original size' '2396,' 'current size' "$shar_count!"
fi
fi
# ============= process.py ==============
if test -f 'process.py' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'process.py' '(file already exists)'
else
$echo 'x -' extracting 'process.py' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'process.py' &&
#!/usr/bin/python
X
import re, sys, os, string, random
X
def __LINE__():
X try:
X raise "Hack"
X except:
X return sys.exc_info()[2].tb_frame.f_back.f_lineno
X
R = sys.stdin.read()
X
par_on = re.compile("#pragma par_on").search
par_off = re.compile("#pragma par_off").search
X
a, b = par_on(R).regs[0]
c, d = par_off(R).regs[0]
X
R1 = R[:a]
R2 = R[b:c]
R3 = R[d:]
X
# We'll process R2, where functions are parallelized, and leave
# R1 and R3 alone. First let's strip comments.
X
one_line_comment = re.compile("//.*\n").search
comment_start = re.compile("/\*").search
comment_finish = re.compile("\*/").search
X
R2new = ""
while R2:
X try:
X a, b = one_line_comment(R2).regs[0]
X x, R2 = R2[:a] + "\n", R2[b:]
X R2new = R2new + x
X except AttributeError:
X break
R2 = R2new + R2
X
R2new = ""
while R2:
X try:
X a, b = comment_start(R2).regs[0]
X c, d = comment_finish(R2).regs[0]
X x, R2 = R2[:a], R2[d:]
X R2new = R2new + x
X except AttributeError:
X break
R2 = R2new + R2
X
# Now we want to identify the function prototypes. Each function has
# a return type, a name, and a list of 2-tuples for arguments, the
# tuples each having a type and a name. Let's generously assume that
# there are no global variables, structs, or other stuff in R2 except
# the functions we want. We'll also ignore "extern", "static",
# "volatile", or anything else similarly tricky.
X
class CThing:
X def __init__(self, str):
X x = string.split(str)
X self.name = x.pop()
X if len(x) == 0: x = [ 'int' ]
X self.type = string.join(x, ' ')
X while self.name[0] == '*':
X self.name = self.name[1:]
X self.type = self.type + " *"
X
X def __repr__(self):
X r = "<CThing %s, type: %s" % (self.name, self.type)
X for k in self.__dict__.keys():
X if k != "name" and k != "type":
X r = r + "\n%s: %s" % (k, self.__dict__[k])
X return r + ">"
X
X def trim_ws(self, x,
X start = re.compile("^[ \t\n]+").search,
X finish = re.compile("[ \t\n]+$").search):
X try:
X a, b = start(x).regs[0]
X x = x[b:]
X except AttributeError:
X pass
X try:
X a, b = finish(x).regs[0]
X x = x[:a]
X except AttributeError:
X pass
X return x
X
X def consume_until(self, x, str):
X try:
X a, b = re.search(str, x).regs[0]
X return x[:a], x[a:b], x[b:]
X except AttributeError:
X return None, None, x
X
X
class NoMoreFunctions(Exception):
X pass
X
X
call_string = ("\n { struct %(name)s_frame *p = (struct %(name)s_frame *)\n " +
X "new_frame (%(name)s, sizeof(struct %(name)s_frame), context);\n")
call_string2 = " p->retval = &%(result)s; CSW; }"
struct_string = """struct %(name)s_frame
{
X int (*func) (struct thread *);
X int tag;
X struct generic_frame *caller;
X struct thread *context;
"""
X
class Function(CThing):
X
X def __init__(self, R):
X x, discard, R = self.consume_until(R, "\(")
X if x == None:
X raise NoMoreFunctions
X CThing.__init__(self, x)
X arglist = [ ]
X funclocals = [ ]
X if self.type != "void":
X funclocals.append(CThing(self.type + " *return_value"))
X x, discard, R = self.consume_until(R, "\)")
X for arg in string.split(x, ','):
X if arg != "void":
X arglist.append(CThing(arg))
X self.args = arglist
X
X # Now we're going to scan for the outermost { } brackets that
X # enclose the body of this function. We can get into trouble
X # here if the function body includes a string with unmatched
X # brackets in it, because I'm not going to go out of my mind
X # trying to parse C strings. So be warned, users, do not put
X # brackets in strings unless they match.
X funcbody = ""
X x, discard, R = self.consume_until(R, '{')
X assert len(self.trim_ws(x)) == 0
X bracketlevel = 1
X while 1:
X x, y, R = self.consume_until(R, '[{}]')
X assert x != None
X funcbody = funcbody + x
X if y == '{':
X funcbody = funcbody + y
X bracketlevel = bracketlevel + 1
X elif y == '}':
X bracketlevel = bracketlevel - 1
X if bracketlevel == 0:
X break # leave the while 1 loop
X funcbody = funcbody + y
X
X # Pull out declarations of local variables
X typelist = ["int", "long", "float", "double", "char",
X "struct", "enum", "unsigned"]
X while (len(funcbody) > 0 and
X string.split(funcbody)[0] in typelist):
X x, y, funcbody = self.consume_until(funcbody, ';')
X assert x != None
X x = string.split(x, ',') # handle multiple declarations
X firstvar = string.split(x[0])
X vartype, varname = string.join(firstvar[:-1], ' '), firstvar[-1]
X # if there's a "*" for a pointer, it will apply only to the
X # first of the multiple declarations
X if vartype[-1] == '*':
X vartype, varname = vartype[:-1], '*' + varname
X funclocals.append(CThing(vartype + ' ' + varname))
X for varname in x[1:]:
X funclocals.append(CThing(vartype + ' ' + varname))
X
X self.body = funcbody
X self.locals = funclocals
X self.results = [ ]
X self._remains = R
X
X def remains(self):
X R = self._remains
X del self._remains
X return R
X
X def handle_function_call(self, func):
X body = self.body
X srch1 = re.compile(func.name + '[ \t\n]*\(').search
X srch2 = re.compile('\)').search
X start_here = 0
X while 1:
X try:
X a, b = srch1(body[start_here:]).regs[0]
X except AttributeError:
X break
X # Having identified a function call, I need to back
X # up to the previous statement (the ';' just prior to
X # the function call) and insert my special call statement
X # there. What a mess.
X before = body[:a+start_here]
X remains = body[b+start_here:]
X start_here = start_here + b
X a, b = srch2(remains).regs[0]
X args = string.split(remains[:a], ',')
X after = remains[b:]
X # Now search backwards for ';' or '}'
X i = len(before) - 1
X while i > 0:
X if before[i] == ';' or before[i] == '}':
X i = i + 1
X break
X i = i - 1
X before, statement_preamble = before[:i], before[i:]
X result_var, func_call = self.setup_func_call(func, args)
X self.results.append(result_var)
X x = (before + func_call +
X statement_preamble + result_var.name)
X start_here = len(x)
X body = x + after
X self.body = body
X
X def setup_func_call(self, func, arglist):
X resultname = '_' + `int(100000000 * random.random())`
X result = CThing(func.type + " " + resultname)
X assignments = ""
X assert len(arglist) == len(func.args)
X for x, y in map(None, func.args, arglist):
X assert hasattr(x, 'name')
X assignments = (assignments +
X " p->%s = %s;\n" % (x.name, y))
X D = {'name': func.name, 'result': resultname}
X return result, ((call_string + assignments +
X "p->return_value = &%(result)s; CSW; }") % D)
X
X def frame_struct(self):
X r = struct_string % {'name': self.name}
X for arg in self.args:
X r = r + " %s %s;\n" % (arg.type, arg.name)
X for local in self.locals:
X r = r + " %s %s;\n" % (local.type, local.name)
X for result in self.results:
X r = r + " %s %s;\n" % (result.type, result.name)
X return r + '};\n'
X
X def process_variables(self):
X varlist = [ ]
X for v in self.args + self.locals + self.results:
X s = re.search("\[[^]]*\]", v.name)
X if s:
X varname = v.name[:s.regs[0][0]]
X else:
X varname = v.name
X varlist.append(varname)
X name_search = re.compile("[_a-zA-Z][_a-zA-Z0-9]*").search
X body, newbody = self.body, ""
X while 1:
X try:
X a, b = name_search(body).regs[0]
X except AttributeError:
X break
X x, y, body = body[:a], body[a:b], body[b:]
X newbody = newbody + x
X if y in varlist:
X newbody = newbody + "(frame->" + y + ")"
X else:
X newbody = newbody + y
X self.body = newbody + body
X
X def process_context_switches(self):
X csw_count = 0
X body = 'CSW;\n' + self.body
X srch = re.compile("CSW").search
X while 1:
X try:
X a, b = srch(body).regs[0]
X except AttributeError:
X break
X body = (body[:a] +
X ("{ frame->tag = %d; return 0; L%d: ; }"
X % (csw_count, csw_count)) + body[b:])
X csw_count = csw_count + 1
X switchstmt = "switch (frame->tag) {\n"
X for i in range(csw_count):
X switchstmt = switchstmt + "case %d: goto L%d;\n" % (i, i)
X self.body = switchstmt + "}\n" + body
X
X def process_returns(self):
X body = self.body
X srch1 = re.compile("return").search
X srch2 = re.compile(";").search
X start_here = 0
X while 1:
X try:
X a, b = srch1(body[start_here:]).regs[0]
X a = a + start_here
X b = b + start_here
X start_here = b
X if body[b:b+6] == "_value":
X raise AttributeError
X except AttributeError:
X break
X c, d = srch2(body[b:]).regs[0]
X c = c + b
X d = d + b
X x = (body[:a] +"*return_value =" + body[b:c] +
X "; return 1;")
X start_here = len(x)
X body = x + body[d:]
X self.body = body
X
X def dumpfunc(self):
X name = self.name
X R = "int %s (struct thread *context)\n{\n" % name
X R = (R +
X ("struct %s_frame *frame = (struct %s_frame *) context->frame;"
X % (name, name)))
X return R + self.body + " return 1;}\n"
X
##############################################
X
functions = [ ]
X
while 1:
X try:
X f = Function(R2)
X R2 = f.remains()
X functions.append(f)
X except NoMoreFunctions:
X break
X
for g in functions:
X for f in functions:
X f.handle_function_call(g)
X
for f in functions:
X f.process_returns()
X f.process_variables()
X f.process_context_switches()
X
###############################################
X
outf = os.popen("indent -", "w")
X
outf.write(R1 + '\n')
X
for f in functions:
X outf.write(f.frame_struct())
X
outf.write('\n')
X
for f in functions:
X outf.write(f.dumpfunc())
X
outf.write('\n' + R3)
outf.close()
SHAR_EOF
(set 20 01 09 22 23 11 10 'process.py'; eval "$shar_touch") &&
chmod 0555 'process.py' ||
$echo 'restore of' 'process.py' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'process.py:' 'MD5 check failed'
4ce96d762dbfd75a0e88b60447e63e1d process.py
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'process.py'`"
test 11217 -eq "$shar_count" ||
$echo 'process.py:' 'original size' '11217,' 'current size' "$shar_count!"
fi
fi
# ============= thr.c ==============
if test -f 'thr.c' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'thr.c' '(file already exists)'
else
$echo 'x -' extracting 'thr.c' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'thr.c' &&
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "thr.h"
X
static struct thread *current_thread = NULL;
X
struct generic_frame *new_frame (int (*func) (struct thread *),
X int framesize,
X struct thread *context)
{
X struct generic_frame *p;
X p = malloc(framesize);
X if (p == NULL)
X {
X fprintf(stderr, "ouch, out of memory\n");
X exit(1);
X }
X p->func = func;
X p->tag = 0;
X ASSERT(context);
X p->context = context;
X p->caller = context->frame;
X context->frame = p;
X return p;
}
X
X
struct thread * new_thread(int (*func) (struct thread *),
X int framesize)
{
X struct thread *r;
X r = malloc(sizeof(struct thread));
X if (r == NULL)
X {
X fprintf(stderr, "ouch, out of memory\n");
X exit(1);
X }
X if (current_thread == NULL)
X {
X r->prev = r->next = r;
X r->frame = NULL;
X current_thread = r;
X }
X else
X {
X ASSERT(current_thread);
X ASSERT(current_thread->next);
X r->prev = current_thread;
X r->next = current_thread->next;
X current_thread->next->prev = r;
X current_thread->next = r;
X }
X r->frame = NULL;
X r->frame = new_frame (func, framesize, r);
X ASSERT(r->frame);
X return r;
}
X
X
static int one_step(void)
{
X int r, just_one;
X if (current_thread == NULL)
X return 1;
X just_one = (current_thread == current_thread->next);
X if (current_thread->frame != NULL)
X {
X r = (current_thread->frame->func) (current_thread);
X if (r)
X {
X struct generic_frame *old_frame;
X old_frame = current_thread->frame;
X current_thread->frame = current_thread->frame->caller;
X free(old_frame);
X }
X if (current_thread->frame == NULL)
X {
X struct thread *before, *after, *oldthread;
X if (just_one)
X {
X free(current_thread);
X current_thread = NULL;
X return 1;
X }
X oldthread = current_thread;
X before = current_thread->prev;
X after = current_thread->next;
X ASSERT(before);
X ASSERT(after);
X before->next = after;
X after->prev = before;
X current_thread = after;
X free(oldthread);
X just_one = (current_thread == current_thread->next);
X }
X }
X return 0;
}
X
int step_thread(int n)
{
X ASSERT(current_thread);
X while (n--)
X {
X if (one_step())
X return 1;
X ASSERT(current_thread);
X current_thread = current_thread->next;
X }
X return 0;
}
X
int step_thread_noisy(int n)
{
X ASSERT(current_thread);
X while (n--)
X {
X /* Threads have about 1 chance in 32 of missing a
X * step. This can be used to model random variations
X * in clock speed or the like.
X */
X if (rand() & 0x01F)
X if (one_step())
X return 1;
X ASSERT(current_thread);
X current_thread = current_thread->next;
X }
X return 0;
}
SHAR_EOF
(set 20 01 09 22 22 53 00 'thr.c'; eval "$shar_touch") &&
chmod 0444 'thr.c' ||
$echo 'restore of' 'thr.c' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'thr.c:' 'MD5 check failed'
4ba1f7cf811f8aeed63a5deba9f3cfe3 thr.c
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'thr.c'`"
test 2773 -eq "$shar_count" ||
$echo 'thr.c:' 'original size' '2773,' 'current size' "$shar_count!"
fi
fi
# ============= thr.h ==============
if test -f 'thr.h' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'thr.h' '(file already exists)'
else
$echo 'x -' extracting 'thr.h' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'thr.h' &&
#define DEBUG 1
X
#if DEBUG
#define ASSERT(c) if (!(c)) \
X { fprintf(stderr,"Assertion failed at line %d:\n%s\n", __LINE__, #c); exit(1); }
#define MARK() fprintf(stderr,"Line %d\n", __LINE__)
#else
#define ASSERT(c)
#define MARK()
#endif
X
struct thread
{
X struct generic_frame *frame;
X struct thread *prev, *next;
};
X
struct generic_frame
{
X /* all frames should start with these same fields in the
X * exact same order
X */
X int (*func) (struct thread *);
X int tag;
X struct generic_frame *caller;
X struct thread *context;
};
X
struct generic_frame *new_frame(int (*func)(struct thread *),
X int framesize, struct thread *context);
struct thread * new_thread(int (*func) (struct thread *),
X int framesize);
int step_thread(int n);
int step_thread_noisy(int n);
SHAR_EOF
(set 20 01 09 22 22 53 31 'thr.h'; eval "$shar_touch") &&
chmod 0444 'thr.h' ||
$echo 'restore of' 'thr.h' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'thr.h:' 'MD5 check failed'
2a84bfc290fda4225d4fc1d2581ce8d2 thr.h
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'thr.h'`"
test 778 -eq "$shar_count" ||
$echo 'thr.h:' 'original size' '778,' 'current size' "$shar_count!"
fi
fi
rm -fr _sh15408
exit 0
# This is a shell archive (produced by GNU sharutils 4.2.1).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `!/bin/sh' line above, then type `sh FILE'.
#
# Made on 2001-09-23 10:19 EDT by <ww...@localhost.localdomain>.
# Source directory was `/home/wware/mmt2'.
#
# Existing files will *not* be overwritten unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 2362 -r--r--r-- README
# 711 -r--r--r-- Makefile
# 911 -r--r--r-- simple.c
# 2396 -r--r--r-- conway.c
# 11217 -r-xr-xr-x process.py
# 2773 -r--r--r-- thr.c
# 778 -r--r--r-- thr.h
#
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
if test "$gettext_dir" = FAILED && test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
set `$dir/gettext --version 2>&1`
if test "$3" = GNU
then
gettext_dir=$dir
fi
fi
if test "$locale_dir" = FAILED && test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
echo=echo
else
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
if touch -am -t 200112312359.59 $$.touch >/dev/null 2>&1 && test ! -f 200112312359.59 -a -f $$.touch; then
shar_touch='touch -am -t $1$2$3$4$5$6.$7 "$8"'
elif touch -am 123123592001.59 $$.touch >/dev/null 2>&1 && test ! -f 123123592001.59 -a ! -f 123123592001.5 -a -f $$.touch; then
shar_touch='touch -am $3$4$5$6$1$2.$7 "$8"'
elif touch -am 1231235901 $$.touch >/dev/null 2>&1 && test ! -f 1231235901 -a -f $$.touch; then
shar_touch='touch -am $3$4$5$6$2 "$8"'
else
shar_touch=:
echo
$echo 'WARNING: not restoring timestamps. Consider getting and'
$echo "installing GNU \`touch', distributed in GNU File Utilities..."
echo
fi
rm -f 200112312359.59 123123592001.59 123123592001.5 1231235901 $$.touch
#
if mkdir _sh15408; then
$echo 'x -' 'creating lock directory'
else
$echo 'failed to create lock directory'
exit 1
fi
# ============= README ==============
if test -f 'README' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'README' '(file already exists)'
else
$echo 'x -' extracting 'README' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'README' &&
This is a massive-multithreading system for C programs. It makes it
easy to write programs running huge numbers of threads. This can be
useful for games, simulations, and webservers.
X
The source file 'simple.c' shows a simple example of how to use this
system. The "#pragma par on" and "#pragma par_off" statements indicate
which functions should be parallelized. The parallelized functions
look pretty normal in simple.c; you don't need to change your source
code very much to make it work.
X
But you _do_ need to explicitly say where you want context switches to
happen, which is done with the "CSW" marker. This sounds like a
horrible thing, but there is a freedom in placing context switches
yourself. You therefore can say with certainty when will _not_ happen,
and that allows you to assume certain kinds of stability in certain
regions of your code.
X
Your code is processed by process.py, a Python script that translates
the C source file into a second C source file, where each parallelized
function has been turned into a sort of state machine, with each state
representing the code between a pair of context switches. To permit
one parallelized function to call another, and to keep the state
machines fully reentrant, there are frames that maintain the state of
each thread at each function call level. Every frame links to its
caller, and to its thread.
X
'simple.c' sets up 100,000 threads all running the same couple
function. Any thread that gets erroneous results will cause an error
message. All the threads succeed, so you get an "All is well" message
at the end.
X
The new_thread() function creates a new thread with a function. There
is presently no really clean way to pass arguments into a thread. The
'conway.c' example shows an ugly way to pass in arguments.
X
The step_thread() function advances the whole collection of threads
by a number of steps. Each step represents one thread's progress from
one context switch to the next one. Threads take turns in a circular
fashion, each taking a step. step_thread() returns 1 when all the
threads have finished running.
X
The 'conway.c' example illustrates Conway's game of life, which is a
cellular automaton. This system is more general than you need for a
CA, as each thread in this system can be running a different program
or at a different point in the same program as all the other threads.
SHAR_EOF
(set 20 01 09 23 00 08 37 'README'; eval "$shar_touch") &&
chmod 0444 'README' ||
$echo 'restore of' 'README' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'README:' 'MD5 check failed'
0cacc428bdf4867caa40cd3433d14fb3 README
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'README'`"
test 2362 -eq "$shar_count" ||
$echo 'README:' 'original size' '2362,' 'current size' "$shar_count!"
fi
fi
# ============= Makefile ==============
if test -f 'Makefile' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'Makefile' '(file already exists)'
else
$echo 'x -' extracting 'Makefile' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'Makefile' &&
CC = gcc
# CFLAGS = -Wall -g
CFLAGS = -Wall -O3
X
all: quux
X
clean:
X rm -rf *~ *.o quux* foo* core zz
X
###################################
X
thr.o: thr.c thr.h
X
###################################
X
quux.c: simple.c process.py
X ./process.py < simple.c > quux.c
X
quux: quux.c thr.o thr.h
X $(CC) $(CFLAGS) -o quux quux.c thr.o
X
###################################
X
foo.c: conway.c process.py
X ./process.py < conway.c > foo.c
X
foo: foo.c thr.o thr.h
X $(CC) $(CFLAGS) -o foo foo.c thr.o
X
########################################
X
wiki:
X ./towiki.py README Makefile simple.c conway.c \
X process.py thr.c thr.h towiki.py > zz
X
shar:
X /usr/bin/shar README Makefile simple.c conway.c \
X process.py thr.c thr.h > zz.shar
SHAR_EOF
(set 20 01 09 23 10 19 01 'Makefile'; eval "$shar_touch") &&
chmod 0444 'Makefile' ||
$echo 'restore of' 'Makefile' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'Makefile:' 'MD5 check failed'
01a8a8e903340658b98bfef03b053931 Makefile
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'Makefile'`"
test 711 -eq "$shar_count" ||
$echo 'Makefile:' 'original size' '711,' 'current size' "$shar_count!"
fi
fi
# ============= simple.c ==============
if test -f 'simple.c' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'simple.c' '(file already exists)'
else
$echo 'x -' extracting 'simple.c' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'simple.c' &&
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
X
#include "thr.h"
X
#pragma par_on
X
int add (int x, int y)
{
X int z;
X z = x + y;
X CSW;
X return z;
}
X
void caller (void)
{
X int result;
X int i, plugh[8];
X /* Make sure arrays work, and context switches don't
X * break for-loops.
X */
X for (i = 0; i < 8; i++)
X {
X plugh[i] = 0xdeadbeef;
X CSW;
X }
X /* Test calls to other parallelized functions. */
X result = add(4, 3) * add(5, 6);
X CSW;
X result += i;
X CSW;
X /* Complain if anything goes unexpectedly. */
X if (result != (4 + 3) * (5 + 6) + 8 ||
X plugh[5] != 0xdeadbeef)
X {
X fprintf(stderr, "Yikes!\n");
X exit(1);
X }
}
X
#pragma par_off
X
#define NUMTHREADS 100000
X
int
main (void)
{
X int i;
X for (i = 0; i < NUMTHREADS; i++)
X new_thread(caller, sizeof(struct caller_frame));
X while (step_thread(1000) == 0);
X printf("All is well\n");
X return 0;
}
SHAR_EOF
(set 20 01 09 22 23 11 03 'simple.c'; eval "$shar_touch") &&
chmod 0444 'simple.c' ||
$echo 'restore of' 'simple.c' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'simple.c:' 'MD5 check failed'
d54cd853c245daa95325b0cb6f441423 simple.c
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'simple.c'`"
test 911 -eq "$shar_count" ||
$echo 'simple.c:' 'original size' '911,' 'current size' "$shar_count!"
fi
fi
# ============= conway.c ==============
if test -f 'conway.c' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'conway.c' '(file already exists)'
else
$echo 'x -' extracting 'conway.c' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'conway.c' &&
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
X
#include "thr.h"
X
#define NUMROWS 30
#define NUMCOLS 40
X
int conway_board[NUMCOLS][NUMROWS];
X
#pragma par_on
X
void conway_behavior(void)
{
X int nextstatus, sum;
X int row, col; /* we'll initialize these from main() */
X int row1, col1;
X
X while (1)
X {
X /* These threads are all in lock-step, so we let them alternate.
X * First they all compute their sums and the next statuses, and
X * then they context switch, and then they each update their
X * entry in conway_board. Then they context switch again, so that
X * the values in conway_board are stable while everybody is doing
X * their sums.
X */
X sum = 0;
X for (row1 = row - 1; row1 < row + 2; row1++)
X for (col1 = col - 1; col1 < col + 2; col1++)
X {
X if (!(row1 == row && col1 == col) &&
X row1 >= 0 && row1 < NUMROWS &&
X col1 >= 0 && col1 < NUMCOLS)
X sum += conway_board[col1][row1];
X }
X if ((sum == 2 && conway_board[col][row]) || sum == 3)
X nextstatus = 1;
X else
X nextstatus = 0;
X CSW;
X conway_board[col][row] = nextstatus;
X CSW;
X }
}
X
#pragma par_off
X
int main(int argc, char *argv[])
{
X int i, j;
X struct thread *thr;
X struct conway_behavior_frame *frame;
X
X /* set up a thread for each pixel */
X for (j = 0; j < NUMROWS; j++)
X for (i = 0; i < NUMCOLS; i++)
X {
X thr = new_thread(conway_behavior,
X sizeof(struct conway_behavior_frame));
X frame = (struct conway_behavior_frame *) thr->frame;
X frame->col = i;
X frame->row = j;
X }
X
X /* make a glider */
X conway_board[2][1] = 1;
X conway_board[3][2] = 1;
X conway_board[1][3] = 1;
X conway_board[2][3] = 1;
X conway_board[3][3] = 1;
X
X /* make a traffic light */
X conway_board[10][2] = 1;
X conway_board[11][2] = 1;
X conway_board[12][2] = 1;
X
X while (1)
X {
X if (argc == 1)
X {
X /* display pixels normally */
X for (j = 0; j < NUMROWS; j++)
X {
X for (i = 0; i < NUMCOLS; i++)
X printf("%c", ".*"[conway_board[i][j]]);
X printf("\n");
X }
X printf("---------------\n");
X }
X else
X {
X /* Print a 'g' for each generation. This is only good
X * for showing that generations are quick.
X */
X printf("g");
X fflush(stdout);
X }
X step_thread(2 * NUMROWS * NUMCOLS);
X }
X
X return 0;
}
SHAR_EOF
(set 20 01 09 22 23 12 34 'conway.c'; eval "$shar_touch") &&
chmod 0444 'conway.c' ||
$echo 'restore of' 'conway.c' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'conway.c:' 'MD5 check failed'
ab4dfadf38eae36c060df6204e6dd309 conway.c
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'conway.c'`"
test 2396 -eq "$shar_count" ||
$echo 'conway.c:' 'original size' '2396,' 'current size' "$shar_count!"
fi
fi
# ============= process.py ==============
if test -f 'process.py' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'process.py' '(file already exists)'
else
$echo 'x -' extracting 'process.py' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'process.py' &&
#!/usr/bin/python
X
import re, sys, os, string, random
X
def __LINE__():
X try:
X raise "Hack"
X except:
X return sys.exc_info()[2].tb_frame.f_back.f_lineno
X
R = sys.stdin.read()
X
par_on = re.compile("#pragma par_on").search
par_off = re.compile("#pragma par_off").search
X
a, b = par_on(R).regs[0]
c, d = par_off(R).regs[0]
X
R1 = R[:a]
R2 = R[b:c]
R3 = R[d:]
X
# We'll process R2, where functions are parallelized, and leave
# R1 and R3 alone. First let's strip comments.
X
one_line_comment = re.compile("//.*\n").search
comment_start = re.compile("/\*").search
comment_finish = re.compile("\*/").search
X
R2new = ""
while R2:
X try:
X a, b = one_line_comment(R2).regs[0]
X x, R2 = R2[:a] + "\n", R2[b:]
X R2new = R2new + x
X except AttributeError:
X break
R2 = R2new + R2
X
R2new = ""
while R2:
X try:
X a, b = comment_start(R2).regs[0]
X c, d = comment_finish(R2).regs[0]
X x, R2 = R2[:a], R2[d:]
X R2new = R2new + x
X except AttributeError:
X break
R2 = R2new + R2
X
# Now we want to identify the function prototypes. Each function has
# a return type, a name, and a list of 2-tuples for arguments, the
# tuples each having a type and a name. Let's generously assume that
# there are no global variables, structs, or other stuff in R2 except
# the functions we want. We'll also ignore "extern", "static",
# "volatile", or anything else similarly tricky.
X
class CThing:
X def __init__(self, str):
X x = string.split(str)
X self.name = x.pop()
X if len(x) == 0: x = [ 'int' ]
X self.type = string.join(x, ' ')
X while self.name[0] == '*':
X self.name = self.name[1:]
X self.type = self.type + " *"
X
X def __repr__(self):
X r = "<CThing %s, type: %s" % (self.name, self.type)
X for k in self.__dict__.keys():
X if k != "name" and k != "type":
X r = r + "\n%s: %s" % (k, self.__dict__[k])
X return r + ">"
X
X def trim_ws(self, x,
X start = re.compile("^[ \t\n]+").search,
X finish = re.compile("[ \t\n]+$").search):
X try:
X a, b = start(x).regs[0]
X x = x[b:]
X except AttributeError:
X pass
X try:
X a, b = finish(x).regs[0]
X x = x[:a]
X except AttributeError:
X pass
X return x
X
X def consume_until(self, x, str):
X try:
X a, b = re.search(str, x).regs[0]
X return x[:a], x[a:b], x[b:]
X except AttributeError:
X return None, None, x
X
X
class NoMoreFunctions(Exception):
X pass
X
X
call_string = ("\n { struct %(name)s_frame *p = (struct %(name)s_frame *)\n " +
X "new_frame (%(name)s, sizeof(struct %(name)s_frame), context);\n")
call_string2 = " p->retval = &%(result)s; CSW; }"
struct_string = """struct %(name)s_frame
{
X int (*func) (struct thread *);
X int tag;
X struct generic_frame *caller;
X struct thread *context;
"""
X
class Function(CThing):
X
X def __init__(self, R):
X x, discard, R = self.consume_until(R, "\(")
X if x == None:
X raise NoMoreFunctions
X CThing.__init__(self, x)
X arglist = [ ]
X funclocals = [ ]
X if self.type != "void":
X funclocals.append(CThing(self.type + " *return_value"))
X x, discard, R = self.consume_until(R, "\)")
X for arg in string.split(x, ','):
X if arg != "void":
X arglist.append(CThing(arg))
X self.args = arglist
X
X # Now we're going to scan for the outermost { } brackets that
X # enclose the body of this function. We can get into trouble
X # here if the function body includes a string with unmatched
X # brackets in it, because I'm not going to go out of my mind
X # trying to parse C strings. So be warned, users, do not put
X # brackets in strings unless they match.
X funcbody = ""
X x, discard, R = self.consume_until(R, '{')
X assert len(self.trim_ws(x)) == 0
X bracketlevel = 1
X while 1:
X x, y, R = self.consume_until(R, '[{}]')
X assert x != None
X funcbody = funcbody + x
X if y == '{':
X funcbody = funcbody + y
X bracketlevel = bracketlevel + 1
X elif y == '}':
X bracketlevel = bracketlevel - 1
X if bracketlevel == 0:
X break # leave the while 1 loop
X funcbody = funcbody + y
X
X # Pull out declarations of local variables
X typelist = ["int", "long", "float", "double", "char",
X "struct", "enum", "unsigned"]
X while (len(funcbody) > 0 and
X string.split(funcbody)[0] in typelist):
X x, y, funcbody = self.consume_until(funcbody, ';')
X assert x != None
X x = string.split(x, ',') # handle multiple declarations
X firstvar = string.split(x[0])
X vartype, varname = string.join(firstvar[:-1], ' '), firstvar[-1]
X # if there's a "*" for a pointer, it will apply only to the
X # first of the multiple declarations
X if vartype[-1] == '*':
X vartype, varname = vartype[:-1], '*' + varname
X funclocals.append(CThing(vartype + ' ' + varname))
X for varname in x[1:]:
X funclocals.append(CThing(vartype + ' ' + varname))
X
X self.body = funcbody
X self.locals = funclocals
X self.results = [ ]
X self._remains = R
X
X def remains(self):
X R = self._remains
X del self._remains
X return R
X
X def handle_function_call(self, func):
X body = self.body
X srch1 = re.compile(func.name + '[ \t\n]*\(').search
X srch2 = re.compile('\)').search
X start_here = 0
X while 1:
X try:
X a, b = srch1(body[start_here:]).regs[0]
X except AttributeError:
X break
X # Having identified a function call, I need to back
X # up to the previous statement (the ';' just prior to
X # the function call) and insert my special call statement
X # there. What a mess.
X before = body[:a+start_here]
X remains = body[b+start_here:]
X start_here = start_here + b
X a, b = srch2(remains).regs[0]
X args = string.split(remains[:a], ',')
X after = remains[b:]
X # Now search backwards for ';' or '}'
X i = len(before) - 1
X while i > 0:
X if before[i] == ';' or before[i] == '}':
X i = i + 1
X break
X i = i - 1
X before, statement_preamble = before[:i], before[i:]
X result_var, func_call = self.setup_func_call(func, args)
X self.results.append(result_var)
X x = (before + func_call +
X statement_preamble + result_var.name)
X start_here = len(x)
X body = x + after
X self.body = body
X
X def setup_func_call(self, func, arglist):
X resultname = '_' + `int(100000000 * random.random())`
X result = CThing(func.type + " " + resultname)
X assignments = ""
X assert len(arglist) == len(func.args)
X for x, y in map(None, func.args, arglist):
X assert hasattr(x, 'name')
X assignments = (assignments +
X " p->%s = %s;\n" % (x.name, y))
X D = {'name': func.name, 'result': resultname}
X return result, ((call_string + assignments +
X "p->return_value = &%(result)s; CSW; }") % D)
X
X def frame_struct(self):
X r = struct_string % {'name': self.name}
X for arg in self.args:
X r = r + " %s %s;\n" % (arg.type, arg.name)
X for local in self.locals:
X r = r + " %s %s;\n" % (local.type, local.name)
X for result in self.results:
X r = r + " %s %s;\n" % (result.type, result.name)
X return r + '};\n'
X
X def process_variables(self):
X varlist = [ ]
X for v in self.args + self.locals + self.results:
X s = re.search("\[[^]]*\]", v.name)
X if s:
X varname = v.name[:s.regs[0][0]]
X else:
X varname = v.name
X varlist.append(varname)
X name_search = re.compile("[_a-zA-Z][_a-zA-Z0-9]*").search
X body, newbody = self.body, ""
X while 1:
X try:
X a, b = name_search(body).regs[0]
X except AttributeError:
X break
X x, y, body = body[:a], body[a:b], body[b:]
X newbody = newbody + x
X if y in varlist:
X newbody = newbody + "(frame->" + y + ")"
X else:
X newbody = newbody + y
X self.body = newbody + body
X
X def process_context_switches(self):
X csw_count = 0
X body = 'CSW;\n' + self.body
X srch = re.compile("CSW").search
X while 1:
X try:
X a, b = srch(body).regs[0]
X except AttributeError:
X break
X body = (body[:a] +
X ("{ frame->tag = %d; return 0; L%d: ; }"
X % (csw_count, csw_count)) + body[b:])
X csw_count = csw_count + 1
X switchstmt = "switch (frame->tag) {\n"
X for i in range(csw_count):
X switchstmt = switchstmt + "case %d: goto L%d;\n" % (i, i)
X self.body = switchstmt + "}\n" + body
X
X def process_returns(self):
X body = self.body
X srch1 = re.compile("return").search
X srch2 = re.compile(";").search
X start_here = 0
X while 1:
X try:
X a, b = srch1(body[start_here:]).regs[0]
X a = a + start_here
X b = b + start_here
X start_here = b
X if body[b:b+6] == "_value":
X raise AttributeError
X except AttributeError:
X break
X c, d = srch2(body[b:]).regs[0]
X c = c + b
X d = d + b
X x = (body[:a] +"*return_value =" + body[b:c] +
X "; return 1;")
X start_here = len(x)
X body = x + body[d:]
X self.body = body
X
X def dumpfunc(self):
X name = self.name
X R = "int %s (struct thread *context)\n{\n" % name
X R = (R +
X ("struct %s_frame *frame = (struct %s_frame *) context->frame;"
X % (name, name)))
X return R + self.body + " return 1;}\n"
X
##############################################
X
functions = [ ]
X
while 1:
X try:
X f = Function(R2)
X R2 = f.remains()
X functions.append(f)
X except NoMoreFunctions:
X break
X
for g in functions:
X for f in functions:
X f.handle_function_call(g)
X
for f in functions:
X f.process_returns()
X f.process_variables()
X f.process_context_switches()
X
###############################################
X
outf = os.popen("indent -", "w")
X
outf.write(R1 + '\n')
X
for f in functions:
X outf.write(f.frame_struct())
X
outf.write('\n')
X
for f in functions:
X outf.write(f.dumpfunc())
X
outf.write('\n' + R3)
outf.close()
SHAR_EOF
(set 20 01 09 22 23 11 10 'process.py'; eval "$shar_touch") &&
chmod 0555 'process.py' ||
$echo 'restore of' 'process.py' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'process.py:' 'MD5 check failed'
4ce96d762dbfd75a0e88b60447e63e1d process.py
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'process.py'`"
test 11217 -eq "$shar_count" ||
$echo 'process.py:' 'original size' '11217,' 'current size' "$shar_count!"
fi
fi
# ============= thr.c ==============
if test -f 'thr.c' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'thr.c' '(file already exists)'
else
$echo 'x -' extracting 'thr.c' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'thr.c' &&
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "thr.h"
X
static struct thread *current_thread = NULL;
X
struct generic_frame *new_frame (int (*func) (struct thread *),
X int framesize,
X struct thread *context)
{
X struct generic_frame *p;
X p = malloc(framesize);
X if (p == NULL)
X {
X fprintf(stderr, "ouch, out of memory\n");
X exit(1);
X }
X p->func = func;
X p->tag = 0;
X ASSERT(context);
X p->context = context;
X p->caller = context->frame;
X context->frame = p;
X return p;
}
X
X
struct thread * new_thread(int (*func) (struct thread *),
X int framesize)
{
X struct thread *r;
X r = malloc(sizeof(struct thread));
X if (r == NULL)
X {
X fprintf(stderr, "ouch, out of memory\n");
X exit(1);
X }
X if (current_thread == NULL)
X {
X r->prev = r->next = r;
X r->frame = NULL;
X current_thread = r;
X }
X else
X {
X ASSERT(current_thread);
X ASSERT(current_thread->next);
X r->prev = current_thread;
X r->next = current_thread->next;
X current_thread->next->prev = r;
X current_thread->next = r;
X }
X r->frame = NULL;
X r->frame = new_frame (func, framesize, r);
X ASSERT(r->frame);
X return r;
}
X
X
static int one_step(void)
{
X int r, just_one;
X if (current_thread == NULL)
X return 1;
X just_one = (current_thread == current_thread->next);
X if (current_thread->frame != NULL)
X {
X r = (current_thread->frame->func) (current_thread);
X if (r)
X {
X struct generic_frame *old_frame;
X old_frame = current_thread->frame;
X current_thread->frame = current_thread->frame->caller;
X free(old_frame);
X }
X if (current_thread->frame == NULL)
X {
X struct thread *before, *after, *oldthread;
X if (just_one)
X {
X free(current_thread);
X current_thread = NULL;
X return 1;
X }
X oldthread = current_thread;
X before = current_thread->prev;
X after = current_thread->next;
X ASSERT(before);
X ASSERT(after);
X before->next = after;
X after->prev = before;
X current_thread = after;
X free(oldthread);
X just_one = (current_thread == current_thread->next);
X }
X }
X return 0;
}
X
int step_thread(int n)
{
X ASSERT(current_thread);
X while (n--)
X {
X if (one_step())
X return 1;
X ASSERT(current_thread);
X current_thread = current_thread->next;
X }
X return 0;
}
X
int step_thread_noisy(int n)
{
X ASSERT(current_thread);
X while (n--)
X {
X /* Threads have about 1 chance in 32 of missing a
X * step. This can be used to model random variations
X * in clock speed or the like.
X */
X if (rand() & 0x01F)
X if (one_step())
X return 1;
X ASSERT(current_thread);
X current_thread = current_thread->next;
X }
X return 0;
}
SHAR_EOF
(set 20 01 09 22 22 53 00 'thr.c'; eval "$shar_touch") &&
chmod 0444 'thr.c' ||
$echo 'restore of' 'thr.c' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'thr.c:' 'MD5 check failed'
4ba1f7cf811f8aeed63a5deba9f3cfe3 thr.c
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'thr.c'`"
test 2773 -eq "$shar_count" ||
$echo 'thr.c:' 'original size' '2773,' 'current size' "$shar_count!"
fi
fi
# ============= thr.h ==============
if test -f 'thr.h' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'thr.h' '(file already exists)'
else
$echo 'x -' extracting 'thr.h' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'thr.h' &&
#define DEBUG 1
X
#if DEBUG
#define ASSERT(c) if (!(c)) \
X { fprintf(stderr,"Assertion failed at line %d:\n%s\n", __LINE__, #c); exit(1); }
#define MARK() fprintf(stderr,"Line %d\n", __LINE__)
#else
#define ASSERT(c)
#define MARK()
#endif
X
struct thread
{
X struct generic_frame *frame;
X struct thread *prev, *next;
};
X
struct generic_frame
{
X /* all frames should start with these same fields in the
X * exact same order
X */
X int (*func) (struct thread *);
X int tag;
X struct generic_frame *caller;
X struct thread *context;
};
X
struct generic_frame *new_frame(int (*func)(struct thread *),
X int framesize, struct thread *context);
struct thread * new_thread(int (*func) (struct thread *),
X int framesize);
int step_thread(int n);
int step_thread_noisy(int n);
SHAR_EOF
(set 20 01 09 22 22 53 31 'thr.h'; eval "$shar_touch") &&
chmod 0444 'thr.h' ||
$echo 'restore of' 'thr.h' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'thr.h:' 'MD5 check failed'
2a84bfc290fda4225d4fc1d2581ce8d2 thr.h
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'thr.h'`"
test 778 -eq "$shar_count" ||
$echo 'thr.h:' 'original size' '778,' 'current size' "$shar_count!"
fi
fi
rm -fr _sh15408
exit 0
0 new messages