Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/games/volume13/diph/part01

Internet Message Format | 1992-02-10 | 53.2 KB

Path: uunet!zephyr.ens.tek.com!master!saab!billr
From: [e-mail] (Bill Randle)
Newsgroups: comp.sources.games
Subject: v13i026:  diph - the game of dining philosophers, Part01/01
Message-ID: <[e-mail]>
Date: 25 Jan 92 01:33:46 GMT
Sender: [e-mail]
Lines: 2217
Approved: [e-mail]

Submitted-by: [e-mail]
Posting-number: Volume 13, Issue 26
Archive-name: diph/Part01
Environment: BSD Unix

    [Somewhat unusual game in that it is really just a showcase for
     the underlying library routines, but it does work.  -br]

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 1 (of 1)."
# Contents:  README MANIFEST config config/fdsettrouble.h diph.6 diph.c
#   ralloc.c ralloc.h sigsched.3 sigsched.c sigsched.h sod.h timer.c
#   timer.h
# Wrapped by billr@saab on Fri Jan 24 17:31:54 1992
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(741 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
XThey say that to make computer scientists like a multitasking model, you
Xhave to show them how you solve the dining philosophers problem under
Xthat model. Okay, then: the point of this package is to show off my
Xsigsched library, which lets you do signal-schedule programming, aka
Xevent programming, aka non-preemptive threads, on any BSD system. Also
Xincluded here is my timer library, which defines real, virtual, and
Xprofiling time events. Anyway, the dining philosophers simulation here
Xis sufficiently slapstick to deserve being called a game, though not a
Xfantastically deep game. Set the philosophers loose and watch them
Xinteract for a while. No Makefile necessary---just compile all the .c
Xfiles together into diph and run.
X
X---Dan
X
END_OF_FILE
if test 741 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'MANIFEST' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(548 characters\)
sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
X   File Name        Archive #    Description
X-----------------------------------------------------------
X MANIFEST                   1    This shipping list
X README                     1
X config                     1
X config/fdsettrouble.h      1
X diph.6                     1
X diph.c                     1
X ralloc.c                   1
X ralloc.h                   1
X sigsched.3                 1
X sigsched.c                 1
X sigsched.h                 1
X sod.h                      1
X timer.c                    1
X timer.h                    1
END_OF_FILE
if test 548 -ne `wc -c <'MANIFEST'`; then
    echo shar: \"'MANIFEST'\" unpacked with wrong size!
fi
# end of 'MANIFEST'
fi
if test ! -d 'config' ; then
    echo shar: Creating directory \"'config'\"
    mkdir 'config'
fi
if test -f 'config/fdsettrouble.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'config/fdsettrouble.h'\"
else
echo shar: Extracting \"'config/fdsettrouble.h'\" \(180 characters\)
sed "s/^X//" >'config/fdsettrouble.h' <<'END_OF_FILE'
X#ifndef CONFIG_FD_SET_TROUBLE_H
X#define CONFIG_FD_SET_TROUBLE_H
X
X#undef LACKING_FD_ZERO
X#undef DESPERATE_FD_SET
X
X/* sysconf expects lines 4 and 5 */
X
X/* XXX: deprecated */
X
X#endif
END_OF_FILE
if test 180 -ne `wc -c <'config/fdsettrouble.h'`; then
    echo shar: \"'config/fdsettrouble.h'\" unpacked with wrong size!
fi
# end of 'config/fdsettrouble.h'
fi
if test -f 'diph.6' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'diph.6'\"
else
echo shar: Extracting \"'diph.6'\" \(369 characters\)
sed "s/^X//" >'diph.6' <<'END_OF_FILE'
X.TH diph 6
X.SH NAME
Xdiph \- dining philosophers simulation
X.SH SYNTAX
X.B diph
X.SH DESCRIPTION
X.B diph
Xis a somewhat slapstick simulation of the
Xdining philosophers problem.
XInstructions are printed at the beginning of each run.
X.SH VERSION
Xdiph version 1.0, 7/27/91.
X.SH AUTHOR
XPlaced into the public domain by Daniel J. Bernstein.
X.SH "SEE ALSO"
Xsigsched(3),
Xtimer(3)
END_OF_FILE
if test 369 -ne `wc -c <'diph.6'`; then
    echo shar: \"'diph.6'\" unpacked with wrong size!
fi
# end of 'diph.6'
fi
if test -f 'diph.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'diph.c'\"
else
echo shar: Extracting \"'diph.c'\" \(7332 characters\)
sed "s/^X//" >'diph.c' <<'END_OF_FILE'
X/* diph.c: the game of dining philosophers
XDaniel J. Bernstein, [e-mail].
XDepends on sigsched.h, timer.h, ralloc.h.
XRequires UNIX.
X1/8/92: Took advantage of rallocneverfail().
X7/27/91: Baseline. diph 1.0, public domain.
XNo known patent problems.
X
XA colorful implementation of dining philosophers using signal-schedule
Xprogramming. Notice how easy signal-schedule makes synchronization. You
Xdon't have to worry about locks. You don't have to worry about the order
Xof bringing semaphores up and down. All you have to do is make sure that
Xno thread can get into an infinite loop, and that's trivial.
X
XWhen a philosopher wants to eat, if a fork isn't available, he glares at
Xthe neighbor using the fork. When that neighbor finishes eating, he
Xpunches the one who glared at him.
X
XWe use the timer library to schedule eating and end-of-eating in real
Xtime. Each philosopher thinks for 1 to 10 seconds, then eats for 2 to 5
Xseconds, then goes back to thinking.
X
XThe solution really requires only 5 bits of state (though more bits, of
Xcourse, are stored inside sigsched): whether forks are up and down.
XEverything else is added for amusement value.
X
XPhilosophers 0 through 4 have these bits:
X  eating
X  thinking (aka not hungry)
X  glaring to the left
X  glaring to the right
X
XPhilosopher i uses forks i and i + 1. In the program output, forks are
Xdisplayed as the numbers of the philosophers who can use them: 01, 12,
X23, 34, 40.
X
X*/
X
X#include <stdio.h>
X#include <signal.h>
X#include "sigsched.h"
X#include "timer.h"
X#include "ralloc.h" /* just for rcount() statistics */
X
Xint myrandom()
X{
X return getpid() + rand(); /* XXX: good enough for a demonstration program */
X}
X
Xvoid choose_eattime(when)
Xtimer_clock *when;
X{
X timer_clock now;
X timer_clock diff;
X timer_now(TIMER_REAL,&now);
X diff.sec = 1 + (myrandom() % 9);
X diff.usec = 1 + (myrandom() % 1000000);
X timer_sum(&now,&diff,when);
X}
X
Xvoid choose_doneeattime(when)
Xtimer_clock *when;
X{
X timer_clock now;
X timer_clock diff;
X timer_now(TIMER_REAL,&now);
X diff.sec = 2 + (myrandom() % 3);
X diff.usec = 1 + (myrandom() % 1000000);
X timer_sum(&now,&diff,when);
X}
X
X#define next(i) (((i) + 1) % 5)
X#define prev(i) (((i) + 4) % 5)
X
Xint timeseaten[5];
Xint usecseaten[5];
Xint usecshungry[5];
X
Xint eating[5];
Xint thinking[5];
Xint prevglaring[5];
Xint nextglaring[5];
X
Xint forkup[5];
X
Xtimer_sig wakeup[5];
Xtimer_clock when[5];
Xtimer_clock beganeating[5];
X
Xmeasurehungry(i)
Xint i;
X{
X timer_clock diff;
X timer_now(TIMER_REAL,beganeating + i);
X if (timer_diff(beganeating + i,when + i,&diff) < 0)
X   ; /* XXX: aack! timer error! */
X else
X   usecshungry[i] += diff.sec * 1000000 + diff.usec;
X}
X
Xmeasureeating(i)
Xint i;
X{
X timer_clock diff;
X timer_clock now;
X timer_now(TIMER_REAL,&now);
X if (timer_diff(&now,beganeating + i,&diff) < 0)
X   ; /* XXX: aack! time warp! */
X else
X   usecseaten[i] += diff.sec * 1000000 + diff.usec;
X}
X
Xstopthinking(i)
Xint i;
X{
X printf("%d's stomach rumbles.\n",i); fflush(stdout);
X thinking[i] = 0;
X eat(i);
X}
X
Xstopeating(i)
Xint i;
X{
X printf("%d stops eating and lowers forks %d%d and %d%d.\n"
X     ,i,prev(i),i,i,next(i)); fflush(stdout);
X ++timeseaten[i];
X measureeating(i);
X eating[i] = 0;
X forkup[i] = 0;
X forkup[next(i)] = 0;
X if (prevglaring[next(i)])
X   punch(i,next(i));
X if (nextglaring[prev(i)])
X   punch(i,prev(i));
X printf("%d sinks into meditation.\n",i); fflush(stdout);
X thinking[i] = 1;
X choose_eattime(when + i);
X timer_setsig(wakeup + i,TIMER_REAL,when + i);
X ss_schedonce(&(wakeup[i].sig),stopthinking,i);
X}
X
Xstopprevglare(i)
Xint i;
X{
X printf("%d stops glaring at %d.\n",i,prev(i)); fflush(stdout);
X prevglaring[i] = 0;
X}
X
Xstopnextglare(i)
Xint i;
X{
X printf("%d stops glaring at %d.\n",i,next(i)); fflush(stdout);
X nextglaring[i] = 0;
X}
X
Xglareprev(i)
Xint i;
X{
X if (prevglaring[i])
X   printf("%d continues glaring at %d.\n",i,prev(i));
X else
X   printf("%d glares at %d.\n",i,prev(i));
X fflush(stdout);
X prevglaring[i] = 1;
X}
X
Xglarenext(i)
Xint i;
X{
X if (nextglaring[i])
X   printf("%d continues glaring at %d.\n",i,next(i));
X else
X   printf("%d glares at %d.\n",i,next(i));
X fflush(stdout);
X nextglaring[i] = 1;
X}
X
Xeat(i)
Xint i;
X{
X ss_unsched(ss_asap(),eat,i);
X if (!forkup[i] && prevglaring[i])
X   stopprevglare(i);
X if (!forkup[next(i)] && nextglaring[i])
X   stopnextglare(i);
X if (forkup[i])
X   glareprev(i);
X if (forkup[next(i)])
X   glarenext(i);
X if (!forkup[i] && !forkup[next(i)])
X  {
X   printf("%d grabs forks %d%d and %d%d and begins eating.\n"
X     ,i,prev(i),i,i,next(i)); fflush(stdout);
X   measurehungry(i);
X   forkup[i] = 1;
X   forkup[next(i)] = 1;
X   eating[i] = 1;
X   choose_doneeattime(when + i);
X   timer_setsig(wakeup + i,TIMER_REAL,when + i);
X   ss_schedonce(&(wakeup[i].sig),stopeating,i);
X  }
X}
X
Xpunch(i,j)
Xint i;
Xint j;
X{
X printf("%d punches %d.\n",i,j); fflush(stdout);
X ss_unsched(ss_asap(),eat,j);
X ss_schedwait(ss_asap(),eat,j,1);
X}
X
Xstatistics(n)
Xint n;
X{
X int i;
X
X /* Normally, you can't use stdio inside signal handlers. */
X /* Not only could output get awfully intermixed, but */
X /* stdio's internal state could become really fouled up. */
X /* Under sigsched, such worries simply vanish. */
X printf("\n");
X
X printf("These forks are up:");
X for (i = 0;i < 5;++i)
X   if (forkup[i])
X     printf(" %d%d",prev(i),i);
X
X printf("\n");
X for (i = 0;i < 5;++i)
X   if (thinking[i])
X     printf("Philosopher %d is thinking.\n",i);
X   else
X     if (eating[i])
X       printf("Philosopher %d is eating with forks %d%d and %d%d.\n"
X         ,i,prev(i),i,i,next(i));
X     else
X      {
X       printf("Philosopher %d is hungry",i);
X       if (prevglaring[i] && nextglaring[i])
X     printf(", glaring at %d, and glaring at %d",prev(i),next(i));
X       else if (prevglaring[i])
X     printf(" and glaring at %d",prev(i));
X       else if (nextglaring[i])
X     printf(" and glaring at %d",next(i));
X       printf(".\n");
X      }
X
X for (i = 0;i < 5;++i)
X  {
X   printf("Philosopher %d ate %d time",i,timeseaten[i]);
X   if (timeseaten[i] != 1) printf("s");
X   printf(" for %.2f secs avg, %.2f secs avg hungry.\n"
X     ,usecseaten[i] * 0.000001 / (timeseaten[i] + 0.000001)
X     ,usecshungry[i] * 0.000001 / (timeseaten[i] + eating[i] + 0.000001)
X       /* + eating[i] is to count eating in progress */
X       /* 0.000001 is fudge to avoid dividing by 0 */
X    );
X  }
X
X printf("ralloc reports %d memory segments in use.\n",rcount());
X
X printkeys();
X printf("\n");
X fflush(stdout);
X}
X
Xdie(n)
Xint n;
X{
X exit(n);
X}
X
Xvoid outofmem(n)
Xint n;
X{
X printf("Aack! Out of memory.\n");
X printf("The philosophers suddenly forget what they were doing.\n");
X printf("They get up and walk away from the table aimlessly.\n");
X die(2);
X}
X
Xprintkeys()
X{
X printf("(Type ^C for statistics, ^\\ to quit.)\n");
X}
X
Xmain()
X{
X int i;
X
X rallocneverfail(outofmem);
X printkeys();
X timer_init();
X for (i = 0;i < 5;++i)
X   timeseaten[i] = eating[i] = prevglaring[i] = nextglaring[i] = forkup[i] = 0;
X for (i = 0;i < 5;++i)
X   usecseaten[i] = usecshungry[i] = 0;
X for (i = 0;i < 5;++i)
X  {
X   printf("%d grabs a chair, sits down, and thinks.\n",i);
X   fflush(stdout);
X   thinking[i] = 1;
X   choose_eattime(when + i);
X   timer_setsig(wakeup + i,TIMER_REAL,when + i);
X   ss_schedonce(&(wakeup[i].sig),stopthinking,i);
X  }
X ss_addsig(SIGINT);
X ss_addsig(SIGQUIT);
X ss_sched(ss_signal(SIGINT),statistics,0);
X ss_sched(ss_signal(SIGQUIT),die,0);
X ss_exec();
X /* from this there is no return */
X}
END_OF_FILE
if test 7332 -ne `wc -c <'diph.c'`; then
    echo shar: \"'diph.c'\" unpacked with wrong size!
fi
# end of 'diph.c'
fi
if test -f 'ralloc.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'ralloc.c'\"
else
echo shar: Extracting \"'ralloc.c'\" \(3779 characters\)
sed "s/^X//" >'ralloc.c' <<'END_OF_FILE'
X/* ralloc.c, ralloc.h: recovering alloc
XDaniel J. Bernstein, [e-mail].
XDepends on sod.h.
XRequires malloc/free.
X8/26/91: Changed exit() to _exit().
X8/26/91: Made rallocneverfail() overwrite any previous handler.
X7/24/91: Added rallocneverfail().
X7/18/91: Baseline. ralloc 1.0, public domain.
XNo known patent problems.
X
XLots of library routines allocate space for temporary objects: compiled
Xregular expressions, for example. They don't destroy the objects between
Xeach call---wouldn't it be a waste to reallocate and recompile those
Xregular expressions on every single pattern match? But when space gets
Xtight, you don't want all those temporary objects cluttering the heap.
XYou've got to deallocate them as soon as possible. Sure, library X might
Xhave some deallocation routines---but if X is hidden below library Y and
Xseparate library A runs out of space, do you expect A to know about X
Xand call X's routines? Of course not. How can A and X coordinate?
X
XThe solution is ralloc. ralloc works just like malloc, except that when
Xit runs out of memory, it tries to recover space from anyone who's
Xwilling to give a little slack. If f is a deallocation function, you can
Xcall rallocinstall(f), and ralloc(n) will call f() if there aren't n
Xbytes free. f() should return a non-zero integer if it could free some
Xmemory, 0 if not. Several libraries can rallocinstall their deallocation
Xroutines, and ralloc will cycle between all of them. Make sure that f
Xactually frees some memory if it returns non-zero---otherwise ralloc()
Xwill loop, trying f again and again and wondering why malloc() never has
Xenough space. (In a future implementation I might add a loop counter and
Xhave ralloc give up after trying f enough times.)
X
XAccording to John F. Haugh, ralloc is a Bad Thing, because it inherently
Xrequires static variables, hence can't be put into a ``pure'' shared
Xlibrary. Face it, John: ralloc() solves a real problem, and if you can't
Xput it in a shared library, it's not because ralloc() is somehow evil.
XIt's because your shared libraries aren't good enough.
X
X*/
X
X#include "ralloc.h"
X#include "sod.h"
Xextern char *malloc(); /*XXXX*/
Xextern void free();
X
Xtypedef int (*foo)();
X
XSODdecl(funlist,foo);
X
Xstatic funlist funhead = 0;
Xstatic funlist funlast = 0; /* last fun to successfully recover */
X
Xstatic int ralloccount = 0;
X
Xint rcount()
X{
X return ralloccount;
X}
X
Xvoid rfree(s)
Xchar *s;
X{
X /* This is for completeness, and for another reason: so that you only */
X /* have to modify this file if you want a debugging malloc-free. */
X --ralloccount; /* for instance */
X free(s);
X}
X
Xstatic int crit = 0; /* just to be safe */
X
Xstatic int (*neverfail)() = 0;
X
Xstatic void die(n)
Xunsigned n;
X{
X if (neverfail)
X   neverfail(n);
X _exit(1); /*XXX*/
X}
X
Xchar *ralloc(n)
Xunsigned n;
X{
X char *t;
X funlist fun;
X
X if(t = malloc(n))
X  {
X   ++ralloccount;
X   return t;
X  }
X if (crit)
X   if (neverfail)
X     die(n);
X   else
X     return 0;
X if (!funhead)
X   if (neverfail)
X     die(n);
X   else
X     return 0;
X crit = 1;
X fun = (funlast ? SODnext(funlast) : funhead);
X do
X  {
X   if(!fun)
X     fun = funhead;
X   if((*SODdata(fun))()) /* XXX: can we make use of args or return code? */
X     funlast = fun;
X   else
X     if(fun == funlast)
X      {
X       crit = 0;
X       if (neverfail)
X     die(n);
X       else
X         return 0; /* gaack! */
X      }
X   fun = SODnext(fun);
X   t = malloc(n);
X  }
X while(!t);
X ++ralloccount;
X crit = 0;
X return t;
X}
X
Xvoid rallocneverfail(f)
Xint (*f)();
X{
X neverfail = f; /* possibly overwriting previous handler */
X}
X
X#define malloc ralloc
X
Xint rallocinstall(f)
Xint (*f)();
X{
X funlist fun;
X
X fun = SODalloc(funlist,fun,ralloc);
X if(!fun)
X   return -1;
X SODdata(fun) = f;
X SODpush(funhead,fun);
X
X funlast = funhead; /* need to set it to something */
X
X return 0;
X}
END_OF_FILE
if test 3779 -ne `wc -c <'ralloc.c'`; then
    echo shar: \"'ralloc.c'\" unpacked with wrong size!
fi
# end of 'ralloc.c'
fi
if test -f 'ralloc.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'ralloc.h'\"
else
echo shar: Extracting \"'ralloc.h'\" \(257 characters\)
sed "s/^X//" >'ralloc.h' <<'END_OF_FILE'
X#ifndef RALLOC_H
X#define RALLOC_H
X
Xextern char *ralloc();
Xextern void rfree();
Xextern int rcount();
Xextern int rallocinstall();
Xextern void rallocneverfail();
X
X#define RFREE(x) rfree((char *) (x))
X#define RALLOC(t,x) ((t *) ralloc((x) * sizeof(t)))
X
X#endif
END_OF_FILE
if test 257 -ne `wc -c <'ralloc.h'`; then
    echo shar: \"'ralloc.h'\" unpacked with wrong size!
fi
# end of 'ralloc.h'
fi
if test -f 'sigsched.3' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'sigsched.3'\"
else
echo shar: Extracting \"'sigsched.3'\" \(10068 characters\)
sed "s/^X//" >'sigsched.3' <<'END_OF_FILE'
X.TH sigsched 3
X.SH NAME
Xsigsched \- signal-schedule (non-preemptive threads) library
X.SH SYNTAX
X.B #include <sigsched.h>
X
Xss_sig *\fBss_asap()\fR;
X.br
Xss_sig *\fBss_signal(\fIsigno\fB)\fR;
X.br
Xss_sig *\fBss_sigread(\fIfd\fB)\fR;
X.br
Xss_sig *\fBss_sigwrite(\fIfd\fB)\fR;
X.br
Xss_sig *\fBss_sigexcept(\fIfd\fB)\fR;
X
Xint \fBss_addsig(\fIsigno\fB)\fR;
X
Xint \fBss_schedvwait(\fIsig,t,flagi,i,p,wait\fB)\fR;
X.br
Xint \fBss_schedwait(\fIsig,t,i,wait\fB)\fR;
X.br
Xint \fBss_sched(\fIsig,t,i\fB)\fR;
X
Xint \fBss_schedonce(\fIsig,t,i\fB)\fR;
X
Xint \fBss_unschedv(\fIsig,t,flagi,i,p\fB)\fR;
X.br
Xint \fBss_unsched(\fIsig,t,i\fB)\fR;
X
Xvoid \fBss_externsetsig(\fIsig,x\fB)\fR;
X
Xint \fBss_exec()\fR;
X
Xvoid \fBss_forcewait()\fR;
X.br
Xvoid \fBss_unforcewait()\fR;
X
Xss_thread \fI*t\fP;
X.br
Xss_sig \fI*sig\fP;
X.br
Xss_extern \fI*x\fP;
X.br
Xint \fIflagi\fP;
X.br
Xint \fIsigno\fP;
X.br
Xint \fIfd\fP;
X.br
Xss_id \fIi\fP;
X.br
Xss_idptr \fIp\fP;
X.br
Xint \fIwait\fP;
X.SH DESCRIPTION
X.B sigsched
Ximplements the signal-schedule programming model,
Xotherwise known as non-preemptive threads,
Xotherwise known as event-based programming.
XA thread is scheduled to execute upon receipt of a signal
X(occurrence of an event).
XSeparate threads do not interrupt each other.
XAll they can do is schedule more threads.
X
X.B sigsched
Xsupports far more flexible signals than C normally provides
Xunder UNIX.
X``File descriptor 2 is writable'' is a signal, for example.
XFurthermore, threads do not have to be written to handle a
Xsignal at any moment, so code written to use
X.B sigsched
Xcan be fully optimized.
XIn contrast, preemptive thread models (including
XUNIX's usual signal handling) prevent optimizations involving global
Xvariables.
X
XIn general, a ``signal'' is any persistent condition.
XThe ``file descriptor 2 is writable'' signal starts when the pipe
Xis created, persists at least until the next I/O, finishes when the pipe is
Xwritten to capacity, restarts when the pipe is read, and so on.
XUNIX signals are examples of
X.I thread-lowered signals.
XFor example, SIGINT starts (is raised) when some process executes
Xkill(pid,SIGINT),
Xand finishes (is lowered) just before process pid calls the appropriate
Xsignal handler (thread).
XNote that if another process calls
Xkill(pid,SIGINT)
Xbefore the first one is delivered,
Xthe signal merely persists.
XIt is not delivered twice, as after the first delivery the
Xsignal condition has been turned off and can't be redelivered.
XAny number of kill()s may be absorbed into
Xone delivery in this way.
X
XWith
X.B sigsched,
Xthe program can schedule a thread to execute upon receipt of a signal.
X.B ss_schedvwait()
Xand
X.B ss_unschedv()
Xschedule and unschedule threads.
X.B ss_exec()
Xthen executes one scheduled thread after another, as described below.
XIt exits when there are no ``important'' threads left to execute.
X
X.B ss_schedvwait(\fIsig,t,flagi,i,p,wait\fB)
Xschedules the thread
X.I t
Xto execute with integer identifier
X.I i
Xor pointer identifier
X.I p
Xas soon as condition
X.I sig
Xexists.
XThis is an ``important'' thread if
X.I wait
Xis nonzero.
X.I sig
Xis of type
X.B ss_sig *;
Xvarious functions produce signals of this type.
X.I t
Xis of type
X.B ss_thread *,
Xdefined as a function returning void;
Xit is called as
X.I t(i)
Xif
X.I flagi
Xis nonzero,
Xor
X.I t(p)
Xif
X.I flagi
Xis zero.
X.I i
Xis an integer,
Xwhich must be zero if
X.I flagi
Xis;
X.I p
Xis a character pointer,
Xwhich must be a null pointer if
X.I flagi
Xis nonzero.
X.B <sigsched.h>
Xdefines the
X.B ss_sig
Xand
X.B ss_thread
Xtypes;
Xit also abbreviates
Xint as
X.B ss_id
Xand char * as
X.B ss_idptr.
X.B ss_schedvwait
Xnormally returns 0, but will return -1
Xin case of a memory allocation failure.
X
X.B ss_unschedv(\fIsig,t,flagi,i,p\fB)
Xunschedules the thread
X.I t
Xpreviously scheduled to execute with identifier
X.I i
Xor
X.I p
Xas soon as condition
X.I sig
Xexisted.
X.I flagi,
X.I i,
Xand
X.I p
Xmust follow the same rules as above.
X.B ss_unschedv
Xreturns 0 if the unschedule was successful,
X1 if there was no such thread.
XThe effects are currently undefined if a thread is scheduled
Xmore than once for the same signal with the same identifier.
X
X.B ss_exec()
Xexecutes one thread after another, with no interruptions.
XIt calls
X.I t(id)
Xonly if, for some signal
X.I sig,
X(1)
X.I t(id)
Xis scheduled to execute upon
X.I sig;
X(2) condition
X.I sig
Xhas existed sometime between the end of the last call
Xof a thread scheduled upon
X.I sig
Xand the beginning of this call to
X.I t(id).
XIf a
Xthread has just finished executing and
X.B ss_exec
Xcan call one or more
Xthreads under the above restrictions, it will choose one and call that,
Xunless every scheduled thread has a wait value of 0
X(i.e., there are no important threads scheduled).
XIn the latter case
X(including, for example, when there are no threads scheduled at all),
X.B ss_exec()
Ximmediately returns 0.
XIt returns -1 in case of a memory allocation
Xfailure; in that case its internal structures may be permanently
Xcorrupted, and
X.B ss_exec
Xmay not be called again in the same program.
X
XIf no threads can execute at a given moment,
Xbut if some thread is
Xscheduled with a non-zero wait value,
X.B ss_exec
Xhas to wait for a signal
Xto arrive.
XAs an optimization,
Xit will block the process until some
Xthread can execute,
Xrather than actively polling the set of signals.
X
XNote that if several threads are scheduled to execute upon one signal,
Xand the signal suddenly exists, one of the threads will execute.
XIf the
Xsignal turns off before the end of that thread, the other threads
Xscheduled upon the signal will not execute.
XThis is always true for
Xthread-lowered signals.
XThis behavior stands in
Xmarked contrast to the behavior of interrupts---upon an interrupt,
Xall the scheduled threads would be executed.
X
XEach signal provides its own scheduling guarantees.
XFor instance, under
Xthis implementation,
Xany (waiting) thread scheduled on the signal
X.I ss_asap()
Xwill in fact execute at some point, provided that no thread
Xblocks or loops forever.
XThere is no way to keep pushing
X.I ss_asap()
Xfarther and farther into the future by scheduling other threads.
XOn the other hand,
X.I ss_asap()
Xwill never flush out the other builtin signals.
X
X.B sigsched
Xprovides several builtin signals:
X.B ss_asap()
Xreturns a (pointer to a) signal which always exists.
X.B ss_signal(\fIsigno\fB)
Xreturns a thread-lowered signal which is true when UNIX signal
X.I signo
Xis received.
X.B ss_sigread(\fIfd\fB)
Xreturns a signal which is true when
X.I fd
Xis open and readable, as defined by
X.I select();
Xsimilarly for
X.B ss_sigwrite
Xand
X.B ss_sigexcept.
X
XIn order for
X.B sigsched
Xto handle UNIX signal
X.I signo,
Xyou must call
X.B ss_addsig(\fIsigno\fB)
Xbefore calling
X.B ss_exec().
X.B ss_addsig
Xwill discard the old signal handler;
Xlater,
X.B ss_exec
Xwill not restore the handler upon exiting, and may
Xleave the signal blocked or unblocked.
X.B ss_addsig
Xwill return 0 normally,
X-1 if
X.I signo
Xis not in the right range for signals.
XIf another library makes use of
X.B ss_signal
Xwith
X.B sigsched,
Xit should provide a mandatory initialization routine
Xwhich calls
X.B ss_addsig.
X
X.B ss_schedvwait
Xand
X.B ss_unschedv
Xcan be abbreviated in common cases.
X.B ss_schedwait(\fIsig,t,i,wait\fB)
Xis the same as
X.B ss_schedvwait(\fIsig,t,1,i,(ss_idptr)0,wait\fB).
X.B ss_sched(\fIsig,t,i\fB)
Xis the same with
X.I wait
Xset to 0; it is commonly used for
Xhandling user signals.
X.B ss_unsched(\fIsig,t,i\fB)
Xis the same as
X.B ss_unschedv(\fIsig,t,1,i,(ss_idptr)0\fB).
X
X.B ss_schedonce(\fIsig,t,i\fB)
Xis similar to
X.B ss_sched
Xbut is in fact implemented on top of
X.B ss_schedvwait
Xwith an independent mechanism.
XEach call to
X.B ss_schedonce
Xschedules
X.I t
Xupon a new signal which starts when
X.I sig
Xdoes and exists only until
X.I t(i)
Xis executed.
XAfter the first execution the new signal disappears.
XThe new signal cannot be unscheduled.
X
X.B ss_forcewait()
Xtells
X.B sigsched
Xthat something important is going on outside
X.B sigsched
Xand that
X.B ss_exec
Xshould not exit.
X.B ss_unforcewait()
Xnegates a previous
X.B ss_forcewait().
X.B ss_forcewait()
Xand
X.B ss_unforcewait()
Xcontrol a counter, not a flag, so independent
Xlibraries can use them, but each library should
Xbe careful to use as many of one call as of the other.
XThese functions must not be used outside
X.B ss_exec().
X
X.B ss_externsetsig(sig,x)
Xcreates a new signal
Xin the
X.B ss_sig
Xpointed to by
X.I sig.
X.I x
Xpoints to an
X.B ss_extern,
Xwhich is defined as follows in
X.B <sigsched.h>:
X.PP
X.EX
Xtypedef struct {
X  int (*sched)();
X  int (*unsched)();
X  union { int n; char *c; } u;
X} ss_extern;
X.EE
X.PP
X.I sched
Xmust be filled in with a scheduling function,
Xwhich is called as
X.I (*sched)(x,t,flagi,i,p,wait)
Xwhenever
X.B ss_schedvwait(\fIsig,t,flagi,i,p,wait\fB)
Xis called;
Xsimilarly for
X.I unsched.
XUse of
X.I u
Xis up to the caller.
X.I sched
Xand
X.I unsched
Xmust observe the same rules as
X.B ss_schedvwait
Xand
X.B ss_unschedv
Xon any other signals: i.e., they must schedule threads upon
Xa persistent condition, make sure that
X.I ss_exec
Xdoes not exit if
Xany important threads are scheduled, etc.
XNote that
X.B ss_externsetsig
Xrecords
X.I x
Xin
X.I sig,
Xso
X.I x
Xmust point either to static memory or to
Xmemory which remains allocated as long as
Xany thread is scheduled or executing upon
X.I sig.
XMemory management of the
X.I sig
Xstructure itself is up to the caller.
X
XIt is recommended that library
X.I foo
Xdefine a
X.B foo_sig
Xstructure, which contains
X.B ss_sig
X.I sig,
X.B ss_extern
X.I x,
Xand any other necessary information for the signals defined by
X.I foo.
XThen
X.B foo_setsig(\fI&fsig,otherinfo\fB),
Xwhere
X.I fsig
Xis a
X.B foo_sig,
Xshould set up the
X.I otherinfo,
Xset
X.I fsig.x.u.c
Xto
X.I &fsig,
Xset
X.I fsig.x.sched
Xand
X.I fsig.x.unsched
Xappropriately,
Xand
Xfinish with
X.B ss_externsetsig(&fsig.sig,&fsig.x).
XThat way the user can use
X.I &fsig.sig
Xas the signal argument to
X.B sigsched
Xfunctions,
Xand when
X.I foo's
Xscheduling routines are passed
X.I &fsig.x
Xas a first argument,
Xthey can get to
X.I otherinfo
Xthrough
X.I fsig.x.u.c.
X
X.B sigsched
Xuses
X.B ralloc
Xfor all allocation.
X.SH VERSION
Xsigsched 1.1, August 25, 1991.
X.SH AUTHOR
XPlaced into the public domain by Daniel J. Bernstein.
X.SH "SEE ALSO"
Xselect(2),
Xsigvec(2),
Xralloc(3)
X
END_OF_FILE
if test 10068 -ne `wc -c <'sigsched.3'`; then
    echo shar: \"'sigsched.3'\" unpacked with wrong size!
fi
# end of 'sigsched.3'
fi
if test -f 'sigsched.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'sigsched.c'\"
else
echo shar: Extracting \"'sigsched.c'\" \(13289 characters\)
sed "s/^X//" >'sigsched.c' <<'END_OF_FILE'
X/* sigsched.c, sigsched.h: signal-schedule thread library
XDaniel J. Bernstein, [e-mail].
XDepends on ralloc.h, sod.h, config/fdsettrouble.h.
XRequires BSDish environment: reliable signals, sig{vec,block,setmask}, select.
X9/1/91: Added worst-case fdset, FD_ZERO, etc. definitions.
X8/25/91: sigsched 1.1, public domain.
X8/25/91: Fixed bug that sigs[sched->blah].r didn't force instant timeout.
X8/25/91: Fixed bug that if select() returned -1 then fds were still checked.
X7/21/91: Changed forever to a 1-hour wakeup.
X7/19/91: Added isopen() to fix bug in case of bad descriptor.
X7/18/91: Baseline. sigsched 1.0, public domain.
XNo known patent problems.
X
XDocumentation in sigsched.3.
X
XXXX: how well do we clean up upon ss_exec() exit?
X
X*/
X
X#include <sys/types.h>
X#include <sys/param.h>
X#include <sys/time.h>
X#include <signal.h>
X#include <errno.h>
X#include <fcntl.h>
Xextern int errno;
X#include "config/fdsettrouble.h"
X#include "sigsched.h"
X#include "ralloc.h"
X#include "sod.h"
X
X/* XXX: should restore signal set exactly after ss_exec returns */
X
Xtypedef int sigc_set; /*XXX */
X
X#define sigc_ismember(x,i) (*(x) & (1 << ((i) - 1)))
X#define sigc_addset(x,i) (*(x) |= (1 << ((i) - 1)))
X#define sigc_emptyset(x) (*(x) = 0)
X
X/*       sigprocmask(SIG_UNBLOCK,xxxx,(sigc_set *) 0); */
X#define sigc_unblock(x) (sigsetmask(sigblock(0) & ~*(x)))
X/*       sigprocmask(SIG_BLOCK,xxxx,(sigc_set *) 0); */
X#define sigc_block(x) (sigblock(*(x)))
X
X#ifndef NSIG
X#define NSIG 64 /* it's not as if any sane system has more than 32 */
X#endif
X
X#define NUMSIGS NSIG
X
X#ifndef FD_SETSIZE
X#define FD_SETSIZE 256
X#endif
X
X#define NUMFDS FD_SETSIZE /* if select() can't handle it, we can't either */
X
X#ifdef LACKING_FD_ZERO
X#define NFDBITS    (sizeof(fd_mask) * NBBY)
X#define    FD_SET(n,p) ((p)->fds_bits[(n)/NFDBITS] |= (1 << ((n) % NFDBITS)))
X#define    FD_ISSET(n,p) ((p)->fds_bits[(n)/NFDBITS] & (1 << ((n) % NFDBITS)))
X#define FD_ZERO(p) bzero((caddr_t)(p),sizeof(*(p)))
X#endif
X
X#ifdef DESPERATION_FD_SET
X#undef NFDBITS
X#undef FD_SET
X#undef FD_ISSET
X#undef FD_ZERO
X#undef fd_set
X#define fd_set long
X#define FD_SET(n,p) ((*p) |= (1 << (n)))
X#define FD_ISSET(n,p) ((*p) & (1 << (n)))
X#define FD_ZERO(p) (*p = 0L)
X#endif
X
X#define ASAP 1
X#define SIGNAL 2
X#define READ 3
X#define WRITE 4
X#define EXCEPT 5
X#define JUNK 6
X#define EXTERN 7
X
Xtypedef struct { ss_sig s; int r; } ss_sigplus;
X
Xstatic ss_sigplus asap;
Xstatic ss_sigplus sigs[NUMSIGS];
Xstatic ss_sigplus reads[NUMFDS];
Xstatic ss_sigplus writes[NUMFDS];
Xstatic ss_sigplus excepts[NUMFDS];
Xstatic ss_sigplus junk; /* special case for internal use */
X
Xstatic void initsigs()
X{
X int i;
X asap.s.type = ASAP; asap.s.u.n = 0; asap.r = 0;
X for (i = 0;i < NUMSIGS;++i)
X  { sigs[i].s.type = SIGNAL; sigs[i].s.u.n = i; sigs[i].r = 0; }
X for (i = 0;i < NUMFDS;++i)
X  { reads[i].s.type = READ; reads[i].s.u.n = i; reads[i].r = 0; }
X for (i = 0;i < NUMFDS;++i)
X  { writes[i].s.type = WRITE; writes[i].s.u.n = i; writes[i].r = 0; }
X for (i = 0;i < NUMFDS;++i)
X  { excepts[i].s.type = EXCEPT; excepts[i].s.u.n = i; excepts[i].r = 0; }
X junk.s.type = JUNK; junk.s.u.n = 0; junk.r = 0;
X}
X
Xss_sig *ss_asap()
X{ return &(asap.s); }
X#define OKsig(i) ((i >= 0) && (i < NUMSIGS))
Xss_sig *ss_signal(i) int i;
X{ if (!OKsig(i)) return 0; return &(sigs[i].s); }
X#define OKfd(fd) ((fd >= 0) && (fd < NUMFDS))
Xss_sig *ss_sigread(fd) int fd;
X{ if (!OKfd(fd)) return 0; return &(reads[fd].s); }
Xss_sig *ss_sigwrite(fd) int fd;
X{ if (!OKfd(fd)) return 0; return &(writes[fd].s); }
Xss_sig *ss_sigexcept(fd) int fd;
X{ if (!OKfd(fd)) return 0; return &(excepts[fd].s); }
X
Xvoid ss_externsetsig(sig,x)
Xss_sig *sig;
Xss_extern *x;
X{
X sig->type = EXTERN;
X sig->u.c = (char *) x;
X}
X
Xstruct sched
X {
X  ss_sig *sig;
X  ss_thread *t;
X  union { ss_id i; ss_idptr p; } id;
X  int flagi;
X  int wait;
X }
X;
X
XSODdecl(schedlist,struct sched);
X
Xstatic schedlist schedhead = 0;
Xstatic int schednum = 0;
Xstatic int schedjunked = 0;
Xstatic int numwait = 0;
X
Xvoid ss_forcewait()
X{
X ++numwait;
X}
X
Xvoid ss_unforcewait()
X{
X --numwait;
X}
X
Xint ss_schedvwait(sig,t,flagi,i,p,wait)
Xss_sig *sig;
Xss_thread *t;
Xint flagi;
Xss_id i;
Xss_idptr p;
Xint wait;
X{
X schedlist s;
X
X if (sig->type == EXTERN)
X  {
X   ss_extern *x;
X   x = (ss_extern *) sig->u.c;
X   return x->sched(x,t,flagi,i,p,wait);
X  }
X s = SODalloc(schedlist,s,ralloc);
X if (!s)
X   return -1;
X SODdata(s).sig = sig;
X SODdata(s).t = t;
X if (SODdata(s).flagi = flagi)
X   SODdata(s).id.i = i;
X else
X   SODdata(s).id.p = p;
X SODdata(s).wait = wait;
X SODpush(schedhead,s);
X ++schednum;
X if (wait)
X   ++numwait;
X return 0;
X}
X
Xint ss_schedwait(sig,t,i,wait)
Xss_sig *sig;
Xss_thread *t;
Xss_id i;
Xint wait;
X{
X return ss_schedvwait(sig,t,1,i,(ss_idptr) 0,wait);
X}
X
Xint ss_sched(sig,t,i)
Xss_sig *sig;
Xss_thread *t;
Xss_id i;
X{
X return ss_schedvwait(sig,t,1,i,(ss_idptr) 0,0);
X}
X
Xstruct oncestuff { ss_sig *sig; ss_thread *t; ss_id i; } ;
X/* XXX: this is the same as some other struct */
X
Xstatic void once(p)
Xss_idptr p;
X{
X struct oncestuff *os;
X os = (struct oncestuff *) p;
X if (ss_unschedv(os->sig,once,0,0,p) == -1)
X   ; /* impossible */
X os->t(os->i);
X RFREE(os);
X}
X
Xint ss_schedonce(sig,t,i)
Xss_sig *sig;
Xss_thread *t;
Xss_id i;
X{
X struct oncestuff *os;
X
X os = (struct oncestuff *) ralloc(sizeof(struct oncestuff));
X if (!os)
X   return -1;
X os->sig = sig; os->t = t; os->i = i;
X return ss_schedvwait(sig,once,0,0,(ss_idptr) os,1);
X}
X
X/* XXX: could rallocinstall() this, if it has the recvhead() test */
X
Xstatic int schedcleanup()
X{
X schedlist s;
X schedlist t;
X schedlist sprev;
X
X/*  if (recvhead) return 0;  XXX: needs recvhead in scope */
X
X if (!schedjunked)
X   return 0;
X
X sprev = 0;
X s = schedhead;
X while (s)
X  {
X   if (SODdata(s).sig == &(junk.s))
X    {
X     if (sprev)
X      {
X       SODpop(SODnext(sprev),t); /* XXX: not part of official sod interface */
X       s = SODnext(sprev);
X      }
X     else
X      {
X       SODpop(s,t);
X       schedhead = s;
X      }
X     SODfree(t,rfree);
X     --schednum;
X     --schedjunked;
X    }
X   else
X    {
X     sprev = s;
X     s = SODnext(s);
X    }
X  }
X
X/* schednum -= schedjunked; now done dynamically inside loop */
X/* schedjunked = 0; */
X return 1;
X}
X
Xstatic void nothing(id)
Xss_id id;
X{
X ;
X}
X
Xint ss_unschedv(sig,t,flagi,i,p)
Xss_sig *sig;
Xss_thread *t;
Xint flagi;
Xss_id i;
Xss_idptr p;
X{
X schedlist s;
X
X if (sig->type == EXTERN)
X  {
X   ss_extern *x;
X   x = (ss_extern *) sig->u.c;
X   return x->unsched(x,t,flagi,i,p);
X  }
X for (s = schedhead;s;s = SODnext(s))
X   if (SODdata(s).sig == sig && SODdata(s).t == t)
X     if (SODdata(s).flagi == flagi)
X       if (flagi ? (SODdata(s).id.i == i) : (SODdata(s).id.p == p))
X        {
X         SODdata(s).sig = &(junk.s);
X         SODdata(s).t = nothing; /* just in case */
X         if (SODdata(s).wait)
X           --numwait;
X         SODdata(s).wait = 0;
X         ++schedjunked;
X         return 0;
X        }
X return 1;
X}
X
Xint ss_unsched(sig,t,i)
Xss_sig *sig;
Xss_thread *t;
Xss_id i;
X{
X return ss_unschedv(sig,t,1,i,(ss_idptr) 0);
X}
X
Xstatic struct timeval timeout;
Xstatic struct timeval instant = { 0, 0 };
Xstatic struct timeval forever = { 3600, 0 };
X  /* XXX: talk to me */
X
Xstatic void handle(i)
Xint i;
X{
X timeout = instant; /* XXX: structure copying */
X sigs[i].r = 1;
X}
X
Xstatic sigc_set sigstorage;
Xstatic sigc_set *xxxx = 0;
X
Xint ss_addsig(i)
Xint i;
X{
X if (!OKsig(i))
X   return -1;
X if (!xxxx)
X  {
X   xxxx = &sigstorage;
X   sigc_emptyset(xxxx);
X  }
X sigc_addset(xxxx,i);
X return 0;
X}
X
Xstatic int isopen(fd)
Xint fd;
X{
X /* XXX: should call this only if select() fails */
X return fcntl(fd,F_GETFL,0) != -1;
X}
X
XSODdecl(recvlist,schedlist);
X
Xint ss_exec()
X{
X int i;
X struct sigvec sv;
X recvlist recvhead;
X recvlist temp;
X schedlist sch;
X
X initsigs();
X
X if (xxxx)
X  {
X   sigc_block(xxxx);
X
X   sv.sv_handler = handle;
X   sv.sv_mask = *xxxx; /* so handle won't interrupt itself */
X   sv.sv_flags = 0;
X
X   /* XXX: Does anyone but me find it absolutely idiotic that POSIX
X      doesn't provide a way to get each member of a signal set in turn? */
X   for (i = 0;i < NUMSIGS;i++)
X    {
X     if (sigc_ismember(xxxx,i))
X       if (sigvec(i,&sv,(struct sigvec *) 0) == -1) /*XXX: really trash orig? */
X     ; /* not our problem */
X    }
X  }
X
X recvhead = 0;
X
X while (numwait)
X  {
X   if (recvhead)
X    {
X     int w;
X     SODpop(recvhead,temp);
X     sch = SODdata(temp);
X
X/* This is the only section where we call user code. */
X#define DOIT \
Xif (SODdata(sch).flagi) \
X  SODdata(sch).t(SODdata(sch).id.i); \
Xelse \
X  SODdata(sch).t(SODdata(sch).id.p);
X
X     switch(SODdata(sch).sig->type)
X      {
X       case JUNK:
X     break; /* has been unscheduled while waiting on the receive list */
X       case ASAP:
X     DOIT
X     break;
X       case READ:
X     if (reads[w = SODdata(sch).sig->u.n].r)
X       DOIT
X     reads[w].r = 0;
X     break;
X       case WRITE:
X     if (writes[w = SODdata(sch).sig->u.n].r)
X       DOIT
X     writes[w].r = 0;
X     break;
X       case EXCEPT:
X     if (excepts[w = SODdata(sch).sig->u.n].r)
X       DOIT
X     excepts[w].r = 0;
X     break;
X       case SIGNAL:
X     if (sigs[w = SODdata(sch).sig->u.n].r)
X       DOIT
X     sigs[w].r = 0;
X       /* ``after the end of the last...'' */
X     break;
X       case EXTERN:
X     /* by definition, an external library handles this */
X     break;
X       default: /* XXX: huh? */
X     ;
X      }
X     SODfree(temp,rfree);
X    }
X   else
X    {
X     schedlist sp;
X     static fd_set rfds;
X     static fd_set wfds;
X     static fd_set efds;
X     static int maxfd;
X     int r;
X
X     if (schedjunked > 100)
X       if (schednum / schedjunked < 3)
X         (void) schedcleanup(); /* now's as good a time as any */
X
X     timeout = forever;
X     FD_ZERO(&rfds);
X     FD_ZERO(&wfds);
X     FD_ZERO(&efds);
X     maxfd = -1;
X
X     for (sp = schedhead;sp;sp = SODnext(sp))
X      {
X       switch(SODdata(sp).sig->type)
X    {
X     case JUNK:
X       break;
X     case ASAP:
X       timeout = instant;
X       break;
X     case SIGNAL:
X       if (sigs[SODdata(sp).sig->u.n].r)
X         timeout = instant;
X       break;
X     case READ:
X       if (isopen(SODdata(sp).sig->u.n))
X         FD_SET(SODdata(sp).sig->u.n,&rfds);
X       if (SODdata(sp).sig->u.n > maxfd)
X         maxfd = SODdata(sp).sig->u.n;
X       break;
X     case WRITE:
X       if (isopen(SODdata(sp).sig->u.n))
X         FD_SET(SODdata(sp).sig->u.n,&wfds);
X       if (SODdata(sp).sig->u.n > maxfd)
X         maxfd = SODdata(sp).sig->u.n;
X       break;
X     case EXCEPT:
X       if (isopen(SODdata(sp).sig->u.n))
X         FD_SET(SODdata(sp).sig->u.n,&efds);
X       if (SODdata(sp).sig->u.n > maxfd)
X         maxfd = SODdata(sp).sig->u.n;
X       break;
X     case EXTERN:
X       break;
X     default: /*XXX: huh? */
X       break;
X    }
X      }
X
X     if (xxxx)
X       sigc_unblock(xxxx);
X     /* This is the only section where handle() can be called. */
X     /* XXX: If maxfd == -1, this select functions as a pause. */
X     /* XXX: If maxfd == -1 and timeout is instant, should skip select. */
X     /* XXX: Random bug of note: Real BSD systems will say that the
X        fd is writable as soon as a network connect() fails. The first
X    I/O will show the error (though it's rather stupid that you
X    can't find out the error without doing I/O). What does Ultrix
X    4.1 do? It pauses for 75 seconds. Dolts. */
X     r = select(maxfd + 1,&rfds,&wfds,&efds,&timeout);
X       /* XXX: does this necessarily prevent timeout race conditions? */
X     if (xxxx)
X       sigc_block(xxxx);
X
X     if (r == -1)
X      {
X       FD_ZERO(&rfds);
X       FD_ZERO(&wfds);
X       FD_ZERO(&efds);
X       switch(errno)
X        {
X         case EINTR: /* fine, this will happen on any signal */ break;
X         case EBADF: /* who knows? */ break;
X         case EINVAL: /* simply impossible */ break;
X         default: /*XXX*/ ;
X     /* well, that was real useful */
X        }
X      }
X
X     for (sp = schedhead;sp;sp = SODnext(sp))
X      {
X       switch(SODdata(sp).sig->type)
X    {
X     case JUNK:
X       break;
X     case ASAP:
X           temp = SODalloc(recvlist,temp,ralloc);
X           if (!temp)
X             return -1; /*XXX*/
X       SODdata(temp) = sp;
X           SODpush(recvhead,temp);
X       break;
X     case SIGNAL:
X       if (sigs[SODdata(sp).sig->u.n].r)
X        {
X             temp = SODalloc(recvlist,temp,ralloc);
X             if (!temp)
X               return -1; /*XXX*/
X         SODdata(temp) = sp;
X             SODpush(recvhead,temp);
X        }
X       break;
X     case READ:
X       if (FD_ISSET(SODdata(sp).sig->u.n,&rfds))
X        {
X         FD_CLR(SODdata(sp).sig->u.n,&rfds);
X         reads[SODdata(sp).sig->u.n].r = 1;
X             temp = SODalloc(recvlist,temp,ralloc);
X             if (!temp)
X               return -1; /*XXX*/
X         SODdata(temp) = sp;
X             SODpush(recvhead,temp);
X        }
X       break;
X     case WRITE:
X       if (FD_ISSET(SODdata(sp).sig->u.n,&wfds))
X        {
X         FD_CLR(SODdata(sp).sig->u.n,&wfds);
X         writes[SODdata(sp).sig->u.n].r = 1;
X             temp = SODalloc(recvlist,temp,ralloc);
X             if (!temp)
X               return -1; /*XXX*/
X         SODdata(temp) = sp;
X             SODpush(recvhead,temp);
X        }
X       break;
X     case EXCEPT:
X       if (FD_ISSET(SODdata(sp).sig->u.n,&efds))
X        {
X         FD_CLR(SODdata(sp).sig->u.n,&efds);
X         excepts[SODdata(sp).sig->u.n].r = 1;
X             temp = SODalloc(recvlist,temp,ralloc);
X             if (!temp)
X               return -1; /*XXX*/
X         SODdata(temp) = sp;
X             SODpush(recvhead,temp);
X        }
X       break;
X     case EXTERN:
X       break;
X     default:
X       break;
X    }
X      }
X    }
X  }
X if (xxxx)
X   sigc_unblock(xxxx);
X   /* XXX: should put this at other returns as well */
X return 0;
X}
END_OF_FILE
if test 13289 -ne `wc -c <'sigsched.c'`; then
    echo shar: \"'sigsched.c'\" unpacked with wrong size!
fi
# end of 'sigsched.c'
fi
if test -f 'sigsched.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'sigsched.h'\"
else
echo shar: Extracting \"'sigsched.h'\" \(732 characters\)
sed "s/^X//" >'sigsched.h' <<'END_OF_FILE'
X#ifndef SIGSCHED_H
X#define SIGSCHED_H
X
Xtypedef struct
X {
X  int type;
X  union { int n; char *c; } u;
X }
Xss_sig;
X
Xtypedef struct
X {
X  int (*sched)();
X  int (*unsched)();
X  union { int n; char *c; } u;
X }
Xss_extern;
X
Xtypedef void ss_thread();
Xtypedef int ss_id;
Xtypedef char *ss_idptr;
X
Xextern ss_sig *ss_asap();
Xextern ss_sig *ss_signal();
Xextern ss_sig *ss_sigread();
Xextern ss_sig *ss_sigwrite();
Xextern ss_sig *ss_sigexcept();
X
Xextern int ss_addsig();
X
Xextern void ss_externsetsig();
X
Xextern int ss_schedvwait();
Xextern int ss_schedwait();
Xextern int ss_sched();
Xextern int ss_schedonce();
Xextern int ss_unschedv();
Xextern int ss_unsched();
X
Xextern void ss_forcewait();
Xextern void ss_unforcewait();
X
Xextern int ss_exec();
X
X#endif
END_OF_FILE
if test 732 -ne `wc -c <'sigsched.h'`; then
    echo shar: \"'sigsched.h'\" unpacked with wrong size!
fi
# end of 'sigsched.h'
fi
if test -f 'sod.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'sod.h'\"
else
echo shar: Extracting \"'sod.h'\" \(508 characters\)
sed "s/^X//" >'sod.h' <<'END_OF_FILE'
X#ifndef SOD_H
X#define SOD_H
X
X/* a half-hearted attempt at a generic stack library */
X
X#define SODdecl(foostack,foo) \
Xtypedef struct foostack { struct foostack *next; foo data; } *foostack
X  /* note that user must supply semicolon */
X
X#define SODnext(x) ((x)->next)
X#define SODdata(x) ((x)->data)
X#define SODalloc(t,x,ralloc) ((t) ((ralloc)(sizeof(*x))))
X#define SODpush(x,y) ((y)->next = (x),(x) = (y))
X#define SODpop(x,y) ((y) = (x),(x) = (x)->next)
X#define SODfree(u,rfree) ((rfree)((char *)(u)))
X
X#endif
END_OF_FILE
if test 508 -ne `wc -c <'sod.h'`; then
    echo shar: \"'sod.h'\" unpacked with wrong size!
fi
# end of 'sod.h'
fi
if test -f 'timer.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'timer.c'\"
else
echo shar: Extracting \"'timer.c'\" \(7815 characters\)
sed "s/^X//" >'timer.c' <<'END_OF_FILE'
X/* timer.c, timer.h: timer libraries
XDaniel J. Bernstein, [e-mail].
XDepends on sigsched.h, ralloc.h, sod.h.
XRequires BSD (interval timers, PROF and VTALRM signals, gettimeofday, etc.).
X7/27/91: Baseline. timer 1.0, public domain.
XNo known patent problems.
X
XAll signals defined here are thread-lowered signals.
X
XNote that we use timer_clock instead of struct timeval since
Xtimer_clock has at least a prayer of being portable.
XThis implementation, however, is BSD-only.
X*/
X
X#include <sys/types.h>
X#include <sys/time.h>
X#include <sys/times.h>
X#include <signal.h>
Xextern long times();
X#include "sigsched.h"
X#include "sod.h"
X#include "timer.h"
X#include "ralloc.h"
X#ifndef HZ
X#define HZ 60 /*XXX*/
X#endif
X
Xint timer_now(t,result)
Xtimer_type t;
Xtimer_clock *result;
X{
X struct tms tms;
X struct timeval tv;
X
X switch(t)
X  {
X   case TIMER_REAL:
X     if (gettimeofday(&tv,(struct timezone *) 0) == -1)
X       return -1;
X     result->sec = tv.tv_sec;
X     result->usec = tv.tv_usec;
X     break;
X   case TIMER_VIRTUAL:
X     times(&tms);
X     result->sec = tms.tms_utime / HZ;
X     result->usec = ((tms.tms_utime % HZ) * 1000000) / HZ;
X     break;
X   case TIMER_PROF:
X     times(&tms);
X     result->sec = (tms.tms_utime + tms.tms_stime) / HZ;
X     result->usec = (((tms.tms_utime + tms.tms_stime) % HZ) * 1000000) / HZ;
X     break;
X   default:
X     return -1;
X  }
X return 0;
X}
X
Xvoid timer_sum(one,two,result)
Xtimer_clock *one;
Xtimer_clock *two;
Xtimer_clock *result;
X{
X result->sec = one->sec + two->sec;
X if ((result->usec = one->usec + two->usec) >= 1000000)
X  {
X   result->sec += 1;
X   result->usec -= 1000000;
X  }
X}
X
Xint timer_diff(one,two,result)
Xtimer_clock *one;
Xtimer_clock *two;
Xtimer_clock *result;
X{
X if (one->sec > two->sec)
X  {
X   result->sec = one->sec - two->sec;
X   if (one->usec >= two->usec)
X     result->usec = one->usec - two->usec;
X   else
X    { --result->sec; result->usec = 1000000 - (two->usec - one->usec); }
X   return 1;
X  }
X if (one->sec < two->sec)
X  {
X   result->sec = two->sec - one->sec;
X   if (two->usec >= one->usec)
X     result->usec = two->usec - one->usec;
X   else
X    { --result->sec; result->usec = 1000000 - (one->usec - two->usec); }
X   return -1;
X  }
X if (one->usec > two->usec)
X  {
X   result->sec = 0;
X   result->usec = one->usec - two->usec;
X   return 1;
X  }
X if (one->usec < two->usec)
X  {
X   result->sec = 0;
X   result->usec = two->usec - one->usec;
X   return 1;
X  }
X result->sec = 0;
X result->usec = 0;
X return 0;
X}
X
X/* Basic idea: For each kind of timer, keep a list of all scheduled */
X/* events. Set the interval timers to go off at the first events. */
X
Xstruct kaboom { timer_clock when; ss_thread *t; int flagi; ss_id i; ss_idptr p; int wait; } ;
X
XSODdecl(kaboomlist,struct kaboom);
X
X/* XXX: should use priority queues here */
X
Xstatic int numwait = 0;
X
X/* XXX: all these will have to change if TIMER_NUM changes */
Xstatic kaboomlist thead[TIMER_NUM] = { 0, 0, 0 };
Xstatic int tgoing[TIMER_NUM] = { 0, 0, 0 };
Xstatic timer_clock twhen[TIMER_NUM];
Xstatic int t2sig[TIMER_NUM] = { SIGALRM, SIGVTALRM, SIGPROF };
Xstatic int t2it[TIMER_NUM] = { ITIMER_REAL, ITIMER_VIRTUAL, ITIMER_PROF };
X
Xstatic void kaboomcleanup()
X{
X kaboomlist newhead;
X kaboomlist k;
X timer_type i;
X
X for (i = 0;i < TIMER_NUM;++i)
X  {
X   newhead = 0;
X   while (thead[i])
X    {
X     SODpop(thead[i],k);
X     if (SODdata(k).t) SODpush(newhead,k); else SODfree(k,rfree);
X    }
X   thead[i] = newhead;
X  }
X}
X
Xstatic void kaboom(t)
Xtimer_type t;
X{
X kaboomlist k;
X timer_clock dummy;
X ss_thread *thread;
X
X ss_unsched(ss_signal(t2sig[t]),kaboom,t);
X tgoing[t] = 0; /* timer's out */
X for (k = thead[t];k;k = SODnext(k))
X   if (timer_diff(&(SODdata(k).when),twhen + t,&dummy) <= 0)
X    {
X     thread = SODdata(k).t; SODdata(k).t = 0;
X     if (SODdata(k).wait) --numwait; SODdata(k).wait = 0;
X     if (thread)
X       if (SODdata(k).flagi)
X     thread(SODdata(k).i);
X       else
X     thread(SODdata(k).p);
X     /* k may now be invalid. alternative: ss_schedonce(ss_asap(),...) */
X     break; /* important! */
X    }
X kaboomcleanup();
X if (kaboomresched(t) == -1)
X   ; /* XXXXXX: uh-oh */
X}
X
Xstatic int set_it(t,when)
Xtimer_type t;
Xtimer_clock *when;
X{
X struct itimerval it;
X timer_clock now;
X timer_clock diff;
X
X if (timer_now(t,&now) == -1)
X   return -1;
X if (timer_diff(when,&now,&diff) <= 0)
X  {
X   diff.sec = 0;
X   diff.usec = 1;
X  }
X it.it_value.tv_sec = diff.sec; it.it_interval.tv_sec = 0;
X it.it_value.tv_usec = diff.usec; it.it_interval.tv_usec = 0;
X if (setitimer(t2it[t],&it,(struct itimerval *) 0) == -1)
X   return -1;
X return 0;
X}
X
Xstatic int kaboomresched(t) /* XXX: implicit-static */
Xtimer_type t;
X{
X timer_clock dummy;
X kaboomlist k;
X int resched;
X
X if (thead[t])
X  {
X   resched = 0;
X   for (k = thead[t];k;k = SODnext(k))
X     if (SODdata(k).t)
X       if (!tgoing[t] || timer_diff(&SODdata(k).when,twhen + t,&dummy) < 0)
X    {
X     resched = 1;
X     twhen[t] = SODdata(k).when; /*XXX: structure copying*/
X    }
X   if (resched)
X    {
X     if (tgoing[t])
X       ss_unsched(ss_signal(t2sig[t]),kaboom,t);
X     tgoing[t] = 1;
X     if (ss_schedwait(ss_signal(t2sig[t]),kaboom,t,numwait) == -1)
X       return -1; /*XXX*/
X     if (set_it(t,twhen + t) == -1)
X       return -1; /*XXX*/
X    }
X  }
X return 0;
X}
X
Xstatic int timer_sched(x,t,flagi,i,p,wait)
Xss_extern *x;
Xss_thread *t;
Xint flagi;
Xss_id i;
Xss_idptr p;
Xint wait;
X{
X timer_sig *tsig;
X kaboomlist k;
X int resched;
X timer_clock dummy;
X
X k = SODalloc(kaboomlist,k,ralloc);
X if (!k)
X   return -1;
X tsig = (timer_sig *) x->u.c;
X SODdata(k).when.sec = tsig->when.sec;
X SODdata(k).when.usec = tsig->when.usec;
X SODdata(k).t = t;
X SODdata(k).flagi = flagi;
X SODdata(k).i = i;
X SODdata(k).p = p;
X SODdata(k).wait = wait;
X
X resched = 0;
X if (wait)
X   if (!numwait++)
X     resched = 1;
X SODpush(thead[tsig->t],k);
X if (!tgoing[tsig->t] || (timer_diff(&(SODdata(k).when),twhen + tsig->t,&dummy) < 0))
X   resched |= 2;
X if (resched)
X  {
X   if (tgoing[tsig->t])
X     ss_unsched(ss_signal(t2sig[tsig->t]),kaboom,tsig->t);
X   if (ss_schedwait(ss_signal(t2sig[tsig->t]),kaboom,tsig->t,numwait) == -1)
X     return -1;
X   tgoing[tsig->t] = 1;
X   if (resched & 2) twhen[tsig->t] = SODdata(k).when; /*XXX: struct copying*/
X   if (set_it(tsig->t,twhen + tsig->t) == -1)
X     return -1;
X  }
X return 0;
X}
X
Xstatic int timer_unsched(x,t,flagi,i,p)
Xss_extern *x;
Xss_thread *t;
Xint flagi;
Xss_id i;
Xss_idptr p;
X{
X timer_sig *tsig;
X kaboomlist k;
X struct kaboom *sk;
X
X tsig = (timer_sig *) x->u.c;
X for (k = thead[tsig->t];k;k = SODnext(k))
X  {
X   sk = &(SODdata(k));
X   if ((sk->t == t) && (sk->flagi == flagi) && (sk->i == i) && (sk->p == p))
X     if ((sk->when.usec == tsig->when.usec) && (sk->when.sec == tsig->when.usec))
X      {
X       sk->t = 0;
X       if (sk->wait)
X     --numwait;
X       sk->wait = 0;
X      }
X  }
X kaboomcleanup();
X if (kaboomresched(tsig->t) == -1)
X   return -1;
X return 0;
X}
X
Xvoid timer_setsig(tsig,t,when)
Xtimer_sig *tsig;
Xtimer_type t;
Xtimer_clock *when;
X{
X tsig->x.sched = timer_sched;
X tsig->x.unsched = timer_unsched;
X tsig->x.u.c = (char *) tsig; /* my, aren't we the clever ones today */
X tsig->t = t;
X tsig->when.sec = when->sec;
X tsig->when.usec = when->usec;
X ss_externsetsig(&(tsig->sig),&(tsig->x));
X}
X
Xstatic int init = 0;
X
Xint timer_init()
X{
X struct itimerval it;
X it.it_value.tv_sec = 0; it.it_value.tv_usec = 0;
X it.it_interval.tv_sec = 0; it.it_interval.tv_usec = 0;
X if (init)
X   return 0;
X init = 1;
X if (ss_addsig(SIGALRM) == -1)
X   return -1;
X if (setitimer(ITIMER_REAL,&it,(struct itimerval *) 0) == -1)
X   return -1;
X if (ss_addsig(SIGPROF) == -1)
X   return -1;
X if (setitimer(ITIMER_PROF,&it,(struct itimerval *) 0) == -1)
X   return -1;
X if (ss_addsig(SIGVTALRM) == -1)
X   return -1;
X if (setitimer(ITIMER_VIRTUAL,&it,(struct itimerval *) 0) == -1)
X   return -1;
X /* we may end up receiving up to one of each signal, but that's okay */
X return 0;
X}
END_OF_FILE
if test 7815 -ne `wc -c <'timer.c'`; then
    echo shar: \"'timer.c'\" unpacked with wrong size!
fi
# end of 'timer.c'
fi
if test -f 'timer.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'timer.h'\"
else
echo shar: Extracting \"'timer.h'\" \(521 characters\)
sed "s/^X//" >'timer.h' <<'END_OF_FILE'
X#ifndef TIMER_H
X#define TIMER_H
X
X#include "sigsched.h"
X
X#define TIMER_REAL ((timer_type) 0)
X#define TIMER_VIRTUAL ((timer_type) 1)
X#define TIMER_PROF ((timer_type) 2)
X#define TIMER_NUM ((timer_type) 3)
X
Xtypedef int timer_type;
Xtypedef struct { unsigned long sec; unsigned long usec; } timer_clock;
Xtypedef struct { ss_sig sig; ss_extern x; timer_type t; timer_clock when; } timer_sig;
X
Xextern int timer_now();
Xextern void timer_sum();
Xextern int timer_diff();
Xextern void timer_setsig();
Xextern int timer_init();
X
X#endif
END_OF_FILE
if test 521 -ne `wc -c <'timer.h'`; then
    echo shar: \"'timer.h'\" unpacked with wrong size!
fi
# end of 'timer.h'
fi
echo shar: End of archive 1 \(of 1\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have the archive.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0