[unix-wizards] Re: Setting multiple timers from a single process.

[Don Libes]

Archive-name: bsd-multiple-timers/16-Mar-90
Original-posting-by: libes at cme.nist.gov (Don Libes)
Original-subject: Re: Setting multiple timers from a single process.
Reposted-by: emv at math.lsa.umich.edu (Edward Vielmetti)

[This is an experimental alt.sources re-posting from the newsgroup(s)
comp.unix.wizards. Comments on this service to emv at math.lsa.umich.edu 
(Edward Vielmetti).]


In article <3412 at muffin.cme.nist.gov> libes at cme.nist.gov (Don Libes) writes:
>In article <24200 at uhnix1.uh.edu> rr at cs.uh.edu writes:
>>The subj line says it; I want to set multiple timers from a single
>>process. Using alarm() & catching SIGALARM will permit only a single
>>timer. I need to set different values for the different timers 
>>
>>My solution at the moment; [spawn child processes for each timer]
>
>Simulate them by waiting for the shortest one, and keeping track of
>the others yourself.  I've done exactly this.  Anyone who wants code
>(4.2BSD) can mail me.
>
>Just watch out for things like 1) a timer interrupting your timer
>management code, 2) trying to cancel one this is in the process of
>going off (or will be by the time you return), 3) getting a new timer
>which is shorter than the current one you are waiting for, and 4) the
>possibility of several being scheduled for the same time.


I've had a dozen people ask me for this already, so here is the
source.

If you have already received this by mail, toss it as I've fixed one
error that I inserted while I was trying to add documentation.  I've
also added significantly more documentation.

/*
Here is code to do multiple timers in 4.2BSD.  It was a bitch to
debug.  However, the code is now very robust - we have been using it
for several years.

I never expected to distribute this, so there was no documentation
originally.  I'll give you some right now entered off the top of my
head from what I remember.  You may contact me for nonobvious questions.

You want to do as little as possible from a signal handler.  In fact,
all you want to do is figure out what the SIGALRM was for, and mark it
so we can execute later, when it is safe to do so.

Thus, we declaring a timer as follows:

	_setimr(timeout,event,ast,arg,pname)

"timeout" is a relative time after which "ast" will be called with a
single argument "arg".  (Really, it should be a vararg, but is an
int.)  "pname" is a string to associate with this entry for debugging.

"ast" is not actually called by the signal handler at interrupt time.
What really happens is that "event" is an address that is set to 1 if
the timer has run down.

At your leisure, you can examine all the "event" flags for the
accumulated asts, and execute whichever ones are ready.  In our
implementation, we used a top-level dispatcher which ran continuously
doing this.  Thus, as soon as one ast completed, the next one was
executed, and they never interrupted one another.  (Synchronous
threads were executed this way as well.  The asts were always given
priority to the threads.)

There are two calls that you must supply:

	_dclast(event, ast, arg, pname);
	_canast(event, ast, arg);

_dclast() enters events into your dispatcher, which _canast() removes them.


Sorry for the lack of better documentation.  Hopefully, the rest of
this should be obvious.

You will probably want to cut out some stuff that isn't pertinent to
you.  In particular, this code demanded that the user provide time in
10 millisecond intervals.  That is totally artificial to BSD.

In some ways, the style of these calls are based on VMS.  (Hey, UNIX
never addressed these issues, so shutup.)  To make up for that, the
documentation is in the UNIX style (i.e., the source).  Ha ha!

"nip" in the comments below refers to a "network interface processor"
which ran on a standalone 68k.  Hence the reason for our own
dispatcher.  Someone else wrote the original 68k version, and it was
my job to port it to UNIX.  So I had to do creative hacks like this.
(The I/O was much worse, be glad you aren't seeing that.)

This is also an apology for the coding style.  It was partly his and
partly mine, both from at least 5 years ago.  Nowadays I would never
distribute such code.  (Translated: I still write code the same way,
but now I would never distribute it.)

This code is in the public domain.  Please give credit to the authors
and NIST.

Don Libes          libes at cme.nist.gov      ...!uunet!cme-durer!libes
*/

/* timer.c - This file implements routines for handling timeouts.
 *
 * User calls are:
 *   _clkini() - initialize clock and timers
 *   _setimr() - set a timer
 *   _cantim() - cancel a timer
 *   #disable_interrupts - disable clock and timer interrupts
 *   #enable_interrupts - enable clock and timer interrupts
 *
 *
 * History:
 *     Originally written for standalone MC68000 with MC6840 timer
 *     Ed Barkmeyer, NBS, September 1983
 *
 *     Rewritten for 4.2BSD UNIX with software timer.
 *     Don Libes, NBS, October 1985
 *
 */

#include <stdio.h>
#include <signal.h>
#include <sys/time.h>

#ifndef TRUE
#define TRUE	1
#define FALSE	0
#endif

typedef short int	int2;
typedef int		int4;

#define TIMER_SIGNAL_TYPE	SIGALRM
#define TIMER_INTERVAL_TYPE	ITIMER_REAL
struct itimerval timer_value;

static unsigned timer_set_timestamp;	/* this holds the value of */
					/* current_time() whenever an */
					/* interval timer is started */

/* The following definitions support conversions between the basic unit of
time in the nip (which is tens-of-milliseconds) and time in all the 4.2BSD
system calls (which is seconds and microseconds).
*/
#define USECS_PER_MSEC		1000
#define MSECS_PER_SEC		1000
#define USECS_PER_SEC		1000000
#define MANY_TENS_OF_MSECS	(~0)		/* unsigned, please */
/* useful for converting from 4.2BSD to nip units */
#define USECS_PER_TEN_MSECS	(USECS_PER_MSEC*10)
#define TENS_OF_MSECS_PER_SEC	(MSECS_PER_SEC/10)
/* useful for converting from nip units to 4.2 units */
#define SEC(x)			(x/TENS_OF_MSECS_PER_SEC)
#define USEC(x)			((x*USECS_PER_TEN_MSECS)%USECS_PER_SEC)

/*

A timer wakeup queue should be represented as a data structure that can do
MIN, INSERT, DELETE and TRAVERSE operations in minimal time.  INSERT and
DELETE are necessary to support declaring and cancelling of timers MIN is
necessary to find out who has timed out and to decide what the next interval
to timeout should be.  TRAVERSE is necessary for updating all the timers once
a time period has elapsed.  Unfortunately, I forget what this optimal data
structure is.  Until I remember, we shall use an array.  

The array is used as follows:  Each entry in the array has a timeout.  
We will constantly be waiting for the entry with the shortest timeout.
When that times out, we will subtract from each timer's timeout, the time that
has passed since we first started waiting for the current timer.  

When a timeout occurs, the event flag is set.  A timer is released from
use when the timeout is 0 AND the event flag points to 0.

*/

#define MAX_TIMERS	24
#define timer_inuse(t)	(t->timeout || t->event)

struct timer {
	unsigned int timeout;		/* clock ticks to wait for */
	int2 *event;			/* set to TRUE when time out occurs */
} timerq[MAX_TIMERS];			/* timer queue */
struct timer *next_timer;		/* timer we expect to run down next */
struct timer *shortest_timer();

int oldmask;				/* signal mask */
/* actually these just fiddle with the interrupt from the timer */
#define disable_interrupts()	oldmask = sigblock(1<<(TIMER_SIGNAL_TYPE-1))
#define enable_interrupts()	(void) sigsetmask(oldmask)

/* used when cancelling timers (if that works) */
struct itimerval cancel_timer = {{ 0,0},{0,0}};

void clk_isr();
unsigned int current_time();

void _clkini() {
	struct timer *t;

	/* disable constant interval timing */
	timerclear(&timer_value.it_interval);

	if (signal(TIMER_SIGNAL_TYPE,clk_isr) == BADSIG) {
		perror("_clkini: signal failed\n");
		exit(-1);
	}
	for (t=timerq;t<&timerq[MAX_TIMERS];t++) {
		t->timeout = 0;
		t->event = 0;
	}
}
    
int _setimr(timeout, event, ast, arg, pname)
unsigned int timeout;		/* time to wait in 10msec ticks */
int2 *event;			/* event flag to set on runout */
void (*ast)();			/* routine to be called on runout or 0 */
int4 arg;			/* argument to be provided to timeout ast */
char *pname;
{
	struct timer *free_timer;	/* pointer to unused timer entry */
	struct timer *t;

	*event = 0;
	
	/* if it has an associated ast, set it up */
	if (ast) _dclast(event, ast, arg, pname);

	if (timeout == 0) { /* no time, so enable it and don't put on queue */
		*event = TRUE;
		return(TRUE);
	}

	disable_interrupts();

	for (t=timerq;t<&timerq[MAX_TIMERS];t++) {
		if (!timer_inuse(t)) {
			free_timer = t;
			break;
		}
	}
	if (t == &timerq[MAX_TIMERS]) {
		fprintf(stderr,"_setimr: out of timers\n");
		exit(-1);
	}

	/* install new timer */
	/* cannot initialize free timer here, because cancel_itimer() will */
	/* munge with it, so push it into the branches of the the if */
	if (!next_timer) {
		/* no timers set at all, so this is shortest */
		free_timer->event = event;
		free_timer->timeout = timeout;
		start_timer(free_timer);
	} else if ((timeout + current_time()) < 
		(next_timer->timeout + timer_set_timestamp)) {
		/* new timer is shorter than current one, so */
		/* cancel current timer and set up new one */
		/* not sure if the next setitimer() is actually necessary */
		/* probably not, but I haven't tested to make sure */
		cancel_itimer();
		free_timer->event = event;
		free_timer->timeout = timeout;
		start_timer(free_timer);
	} else {
		/* new timer is longer, than current one */
		free_timer->event = event;
		free_timer->timeout = timeout;
	}
	enable_interrupts();
	return(TRUE);
}

int _cantim(event, rtn, arg)
int2 *event;
void (*rtn)();
int4 arg;
{
	struct timer *t;

	if (rtn) _canast(event, rtn, arg);
	disable_interrupts();

	for (t=timerq;t<&timerq[MAX_TIMERS];t++) {
		if (t->event == event) {
			t->timeout = 0;
			t->event = 0;
			/* check if we were waiting on this one */
			if (t == next_timer) {
				cancel_itimer();
				start_timer(shortest_timer());
			}
			enable_interrupts();
			return(TRUE);
		}
	}
	enable_interrupts();
	return(FALSE);
}

/* clock interrupt handler */
/* this routine is executed when an alarm signal occurs */
void clk_isr() {
	/* the following condition could be set up, 
	if the interrupt was delivered while we were in cantim, cancelling
	the last timer */

	if (next_timer == 0) return;

	update_all_timers_by(current_time() - timer_set_timestamp);
	
	/* start timer for next shortest guy if one exists */
	start_timer(shortest_timer());
}

/* subtract time from all timers, enabling any that run out along the way */
update_all_timers_by(time)
unsigned int time;
{
	struct timer *t;

	for (t=timerq;t<&timerq[MAX_TIMERS];t++) {
		if (t->timeout) {
			if (time < t->timeout) {
				t->timeout -= time;
			} else {
				t->timeout = 0;
				/* if this has forced a timeout on */
				/* anyone else, enable it */
				*t->event = TRUE;
				t->event = 0;	/* remove timer */
			}
		}
	}
}

struct timer *
shortest_timer()
{
	struct timer *t, *s_t;	/* shortest_timer */
	unsigned int old_timer = MANY_TENS_OF_MSECS;

	for (s_t = 0,t=timerq;t<&timerq[MAX_TIMERS];t++) {
		if (t->timeout > 0 && t->timeout < old_timer) {
			old_timer = t->timeout;
			s_t = t;
		}
	}
	return(s_t);
}

start_timer(t)
struct timer *t;
{
	next_timer = t;		/* remember for _cantim and _setimr */
	if (!t) return;

	timer_set_timestamp = current_time();

	timer_value.it_value.tv_sec = SEC(next_timer->timeout);
	timer_value.it_value.tv_usec = USEC(next_timer->timeout);
	if (-1 == setitimer(TIMER_INTERVAL_TYPE,&timer_value,
					(struct itimerval *)0)) {
		perror("start_timer: setitimer");
		exit(-1);
	}
}

/* return time in tens of milliseconds */
unsigned int
current_time()
{
	struct timeval tp;

	(void) gettimeofday(&tp,(struct timezone *)0);
	/* ignore overflow */
	return(tp.tv_sec*TENS_OF_MSECS_PER_SEC
		+ tp.tv_usec/USECS_PER_TEN_MSECS);
}

cancel_itimer()
{
	if (-1 == setitimer(TIMER_INTERVAL_TYPE,&cancel_timer,
				       (struct itimerval *)0)) {
		perror("_setimr: setitimer failed");
		exit(-1);
	}
	update_all_timers_by(current_time() - timer_set_timestamp);
}