mach_clock: Use a callwheel structure as per Costello & Varghese 1995callwheel

Boots to userspace but netdde freezes trying to bring up eth0

7 files changed, 188 insertions, 177 deletions

diff --git a/device/chario.c b/device/chario.c
index 64640981..ffb958fc 100644
--- a/device/chario.c
+++ b/device/chario.c
@@ -905,7 +905,7 @@ static void ttypush(void * _tp)
 	    if (state & TS_MIN_TO_RCV)
 	      { /* a character was received */
 		tp->t_state = state & ~TS_MIN_TO_RCV;
-		timeout(ttypush, tp, pdma_timeouts[tp->t_ispeed]);
+		tp->t_timeout = timeout(ttypush, tp, pdma_timeouts[tp->t_ispeed]);
 	      }
 	    else
 	      {
@@ -958,7 +958,7 @@ void ttyinput(
 	   */
 	  if (tp->t_state & TS_MIN_TO) {
 	    tp->t_state &= ~(TS_MIN_TO|TS_MIN_TO_RCV);
-	    untimeout(ttypush, tp);
+	    untimeout(tp->t_timeout);
 	  }
 	  tty_queue_completion(&tp->t_delayed_read);
       }
@@ -978,7 +978,7 @@ void ttyinput(
 	    if ((tp->t_state & TS_MIN_TO) == 0)
 	      {
 		tp->t_state |= TS_MIN_TO;
-		timeout(ttypush, tp, ptime);
+		tp->t_timeout = timeout(ttypush, tp, ptime);
 	      }
 	    else
 	      {
diff --git a/device/tty.h b/device/tty.h
index b0f99cf5..f8bce3fc 100644
--- a/device/tty.h
+++ b/device/tty.h
@@ -34,6 +34,7 @@
 #define	_DEVICE_TTY_H_
 
 #include <kern/lock.h>
+#include <kern/mach_clock.h>
 #include <kern/queue.h>
 #include <mach/port.h>
 
@@ -68,6 +69,7 @@ struct tty {
 	queue_head_t	t_delayed_write;/* pending write requests */
 	queue_head_t	t_delayed_open;	/* pending open requests */
 
+	timeout_t	t_timeout;	/* timeout pointer */
 /*
  * Items beyond this point should be removed to device-specific
  * extension structures.
diff --git a/i386/i386at/ioapic.c b/i386/i386at/ioapic.c
index 73fd216a..7d7a02e8 100644
--- a/i386/i386at/ioapic.c
+++ b/i386/i386at/ioapic.c
@@ -163,7 +163,7 @@ timer_measure_10x_apic_hz(void)
 {
     volatile int done = 0;
     uint32_t start = 0xffffffff;
-    timer_elt_data_t tmp_timer;
+    timeout_data_t tmp_timer;
     tmp_timer.fcn = timer_expiry_callback;
     tmp_timer.param = (void *)&done;
 
diff --git a/kern/mach_clock.c b/kern/mach_clock.c
index 65c38086..bd1c40c0 100644
--- a/kern/mach_clock.c
+++ b/kern/mach_clock.c
@@ -45,6 +45,7 @@
 #include "cpu_number.h"
 #include <kern/debug.h>
 #include <kern/host.h>
+#include <kern/kalloc.h>
 #include <kern/lock.h>
 #include <kern/mach_clock.h>
 #include <kern/mach_host.server.h>
@@ -65,11 +66,19 @@
 #endif
 
 #define MICROSECONDS_IN_ONE_SECOND 1000000
+#define TIMEOUT_WHEEL_BITS 8
+#define TIMEOUT_WHEEL_SIZE (1 << TIMEOUT_WHEEL_BITS)
+#define TIMEOUT_WHEEL_MASK (TIMEOUT_WHEEL_SIZE - 1)
+#define MAX_SOFTCLOCK_STEPS (TIMEOUT_WHEEL_SIZE >> 2)
 
 int		hz = HZ;		/* number of ticks per second */
 int		tick = (MICROSECONDS_IN_ONE_SECOND / HZ);	/* number of usec per tick */
 time_value64_t	time = { 0, 0 };	/* time since bootup (uncorrected) */
 unsigned long	elapsed_ticks = 0;	/* ticks elapsed since bootup */
+unsigned long	softticks = 0;		/* like elapsed_ticks but for softclock() */
+
+timeout_t	timeoutwheel[TIMEOUT_WHEEL_SIZE] = {0}; /* timeoutwheel of timeout pointers */
+static timeout_t nextsoftcheck;		/* next timeout to be checked */
 
 int		timedelta = 0;
 int		tickdelta = 0;
@@ -119,10 +128,6 @@ MACRO_BEGIN								\
 	} while ((time)->seconds != mtime->check_seconds64);	\
 MACRO_END
 
-/* Shall be taken at splsched only */
-def_simple_lock_data(static,	timer_lock)	/* lock for ... */
-timer_elt_data_t	timer_head;	/* ordered list of timeouts */
-					/* (doubles as end-of-list) */
 
 /*
  *	Handle clock interrupts.
@@ -207,27 +212,11 @@ void clock_interrupt(
 	 */
 	if (my_cpu == master_cpu) {
 
-	    spl_t s;
-	    timer_elt_t	telt;
-	    boolean_t	needsoft = FALSE;
-
-
 	    /*
-	     *	Update the tick count since bootup, and handle
-	     *	timeouts.
+	     *	Update the tick count since bootup
 	     */
-
-	    s = splsched();
-	    simple_lock(&timer_lock);
-
 	    elapsed_ticks++;
 
-	    telt = (timer_elt_t)queue_first(&timer_head.chain);
-	    if (telt->ticks <= elapsed_ticks)
-		needsoft = TRUE;
-	    simple_unlock(&timer_lock);
-	    splx(s);
-
 	    /*
 	     *	Increment the time-of-day clock.
 	     */
@@ -260,7 +249,7 @@ void clock_interrupt(
 	    /*
 	     *	Schedule soft-interrupt for timeout if needed
 	     */
-	    if (needsoft) {
+	    if (timeoutwheel[elapsed_ticks & TIMEOUT_WHEEL_MASK]) {
 		if (basepri) {
 		    (void) splsoftclock();
 		    softclock();
@@ -268,128 +257,156 @@ void clock_interrupt(
 		else {
 		    setsoftclock();
 		}
+	    } else if (softticks + 1 == elapsed_ticks) {
+	        ++softticks;
 	    }
 	}
 }
 
-/*
- *	There is a nasty race between softclock and reset_timeout.
- *	For example, scheduling code looks at timer_set and calls
- *	reset_timeout, thinking the timer is set.  However, softclock
- *	has already removed the timer but hasn't called thread_timeout
- *	yet.
- *
- *	Interim solution:  We initialize timers after pulling
- *	them out of the queue, so a race with reset_timeout won't
- *	hurt.  The timeout functions (eg, thread_timeout,
- *	thread_depress_timeout) check timer_set/depress_priority
- *	to see if the timer has been cancelled and if so do nothing.
- *
- *	This still isn't correct.  For example, softclock pulls a
- *	timer off the queue, then thread_go resets timer_set (but
- *	reset_timeout does nothing), then thread_set_timeout puts the
- *	timer back on the queue and sets timer_set, then
- *	thread_timeout finally runs and clears timer_set, then
- *	thread_set_timeout tries to put the timer on the queue again
- *	and corrupts it.
- */
 
 void softclock(void)
 {
 	/*
 	 *	Handle timeouts.
 	 */
+	register timeout_t t;
+	register int steps; /* number of steps taken since we last allowed interrupts */
 	spl_t	s;
-	timer_elt_t	telt;
-	void	(*fcn)( void * param );
-	void	*param;
-
-	while (TRUE) {
-	    s = splsched();
-	    simple_lock(&timer_lock);
-	    telt = (timer_elt_t) queue_first(&timer_head.chain);
-	    if (telt->ticks > elapsed_ticks) {
-		simple_unlock(&timer_lock);
-		splx(s);
-		break;
-	    }
-	    fcn = telt->fcn;
-	    param = telt->param;
 
-	    remqueue(&timer_head.chain, (queue_entry_t)telt);
-	    telt->set = TELT_UNSET;
-	    simple_unlock(&timer_lock);
-	    splx(s);
-
-	    assert(fcn != 0);
-	    (*fcn)(param);
+	s = splsched();
+	steps = 0;
+	while (softticks != elapsed_ticks) {
+		timeout_t timeoutfree = NULL;
+
+		if (++steps >= MAX_SOFTCLOCK_STEPS) {
+			nextsoftcheck = NULL;
+			splx(s); /* Give hardclock() a chance */
+			(void) splsched();
+			steps = 0;
+		}
+		t = timeoutwheel[++softticks & TIMEOUT_WHEEL_MASK];
+		while (t) {
+			if (t->t_time > 0) {
+				--t->t_time;
+				t = t->t_next;
+				if (++steps >= MAX_SOFTCLOCK_STEPS) {
+					nextsoftcheck = t;
+					splx(s); /* Give hardclock() a chance */
+					(void) splsched();
+					t = nextsoftcheck;
+					steps = 0;
+				}
+			} else {
+				if ((nextsoftcheck = *t->t_back = t->t_next)) {
+					nextsoftcheck->t_back = t->t_back;
+				}
+				if (++t->handle.lo == 0) {
+					t->handle.hi += TIMEOUT_WHEEL_SIZE;
+				}
+				splx(s);
+				assert (t->fcn != 0);
+				t->fcn(t->param); /* call function at elapsed */
+				(void) splsched();
+				steps = 0;
+				t->t_next = timeoutfree;
+				timeoutfree = t;
+				t = nextsoftcheck;
+			}
+		}
 	}
+	nextsoftcheck = NULL;
+	splx(s);
 }
 
 /*
  *	Set timeout.
  *
  *	Parameters:
- *		telt	 timer element.  Function and param are already set.
- *		interval time-out interval, in hz.
+ *		t 	 preallocated timeout. Function and param are already set.
+ *		interval time-out interval, in ticks.
  */
 void set_timeout(
-	timer_elt_t	telt,	/* already loaded */
+	timeout_t	t,	/* already loaded */
 	unsigned int	interval)
 {
-	spl_t			s;
-	timer_elt_t		next;
+	timeout_t tmp;
+	spl_t s;
 
-	s = splsched();
-	simple_lock(&timer_lock);
+	timeout_t new_t = (timeout_t)kalloc(sizeof(struct timeout));
 
+	s = splsched();
 	interval += elapsed_ticks;
+	new_t->fcn = t->fcn;
+	new_t->param = t->param;
+	new_t->t_time = interval >> TIMEOUT_WHEEL_BITS;
+	new_t->t_next = NULL;
+	new_t->handle.lo = 0;
+	new_t->handle.hi = interval & TIMEOUT_WHEEL_MASK;
 
-	for (next = (timer_elt_t)queue_first(&timer_head.chain);
-	     ;
-	     next = (timer_elt_t)queue_next((queue_entry_t)next)) {
-
-	    if (next->ticks > interval)
-		break;
-	}
-	telt->ticks = interval;
 	/*
-	 * Insert new timer element before 'next'
-	 * (after 'next'->prev)
+	 * Insert new timeout at the end of the corresponding wheel entry
 	 */
-	insque((queue_entry_t) telt, ((queue_entry_t)next)->prev);
-	telt->set = TELT_SET;
-	simple_unlock(&timer_lock);
+	tmp = timeoutwheel[new_t->handle.hi];
+	if (!tmp) {
+		new_t->t_back = &timeoutwheel[new_t->handle.hi];
+		timeoutwheel[new_t->handle.hi] = new_t;
+		splx(s);
+		return;
+	}
+	while (tmp) {
+		if (!tmp->t_next) {
+			new_t->t_back = &tmp->t_next;
+			tmp->t_next = new_t;
+			splx(s);
+			return;
+		}
+		tmp = tmp->t_next;
+	}
+
 	splx(s);
 }
 
-boolean_t reset_timeout(timer_elt_t telt)
+static inline int timeout_ids_match(struct timeout_handle *h1, struct timeout_handle *h2)
 {
-	spl_t	s;
+	return (h1->lo == h2->lo)
+	     && ((h1->hi & ~TIMEOUT_WHEEL_MASK) == (h2->hi & ~TIMEOUT_WHEEL_MASK));
+}
+
+boolean_t reset_timeout(timeout_t t)
+{
+	spl_t s;
+	timeout_t tmp, tt = t;
 
 	s = splsched();
-	simple_lock(&timer_lock);
-	if (telt->set) {
-	    remqueue(&timer_head.chain, (queue_entry_t)telt);
-	    telt->set = TELT_UNSET;
-	    simple_unlock(&timer_lock);
-	    splx(s);
-	    return TRUE;
-	}
-	else {
-	    simple_unlock(&timer_lock);
-	    splx(s);
-	    return FALSE;
-	}
+	tmp = timeoutwheel[t->handle.hi & TIMEOUT_WHEEL_MASK];
+
+	do {
+		if (tmp && timeout_ids_match(&tmp->handle, &t->handle)) {
+			if (nextsoftcheck == tmp) {
+				nextsoftcheck = tmp->t_next;
+			}
+			/* Remove tmp from timeout list */
+			if ((tt = *tmp->t_back = tmp->t_next)) {
+				tt->t_back = tmp->t_back;
+			}
+			if (++t->handle.lo == 0) {
+				t->handle.hi += TIMEOUT_WHEEL_SIZE;
+			}
+			tmp->t_next = NULL;
+			splx(s);
+			kfree((vm_offset_t)tmp, sizeof(struct timeout));
+			return TRUE;
+		}
+	} while (tmp && (tmp = tmp->t_next));
+
+	splx(s);
+	return FALSE;
 }
 
 void init_timeout(void)
 {
-	simple_lock_init(&timer_lock);
-	queue_init(&timer_head.chain);
-	timer_head.ticks = ~0;	/* MAXUINT - sentinel */
-
 	elapsed_ticks = 0;
+	softticks = 0;
 }
 
 /*
@@ -607,10 +624,6 @@ void timeclose(dev_t dev, int flag)
  *	it can be called from interrupt handlers.
  */
 
-#define NTIMERS		20
-
-timer_elt_data_t timeout_timers[NTIMERS];
-
 /*
  *	Set timeout.
  *
@@ -618,56 +631,54 @@ timer_elt_data_t timeout_timers[NTIMERS];
  *	param:		parameter to pass to function
  *	interval:	timeout interval, in hz.
  */
-void timeout(
+timeout_t timeout(
 	void	(*fcn)(void *param),
 	void *	param,
 	int	interval)
 {
-	spl_t	s;
-	timer_elt_t elt;
+	timeout_t tmp;
+	spl_t s;
+
+	timeout_t t = (timeout_t)kalloc(sizeof(struct timeout));
 
 	s = splsched();
-	simple_lock(&timer_lock);
-	for (elt = &timeout_timers[0]; elt < &timeout_timers[NTIMERS]; elt++)
-	    if (elt->set == TELT_UNSET)
-		break;
-	if (elt == &timeout_timers[NTIMERS])
-	    panic("timeout");
-	elt->fcn = fcn;
-	elt->param = param;
-	elt->set = TELT_ALLOC;
-	simple_unlock(&timer_lock);
-	splx(s);
+	interval += elapsed_ticks;
+	t->fcn = fcn;
+	t->param = param;
+	t->t_time = interval >> TIMEOUT_WHEEL_BITS;
+	t->t_next = NULL;
+	t->handle.lo = 0;
+	t->handle.hi = interval & TIMEOUT_WHEEL_MASK;
+
+	/*
+	 * Insert new timeout at the end of the corresponding wheel entry
+	 */
+	tmp = timeoutwheel[t->handle.hi];
+	if (!tmp) {
+		t->t_back = &timeoutwheel[t->handle.hi];
+		timeoutwheel[t->handle.hi] = t;
+		splx(s);
+		return t;
+	}
+	while (tmp) {
+		if (!tmp->t_next) {
+			t->t_back = &tmp->t_next;
+			tmp->t_next = t;
+			splx(s);
+			return t;
+		}
+		tmp = tmp->t_next;
+	}
 
-	set_timeout(elt, (unsigned int)interval);
+	splx(s);
+	return t;
 }
 
 /*
  * Returns a boolean indicating whether the timeout element was found
  * and removed.
  */
-boolean_t untimeout(void (*fcn)( void * param ), const void *param)
+boolean_t untimeout(timeout_t t)
 {
-	spl_t	s;
-	timer_elt_t elt;
-
-	s = splsched();
-	simple_lock(&timer_lock);
-	queue_iterate(&timer_head.chain, elt, timer_elt_t, chain) {
-
-	    if ((fcn == elt->fcn) && (param == elt->param)) {
-		/*
-		 *	Found it.
-		 */
-		remqueue(&timer_head.chain, (queue_entry_t)elt);
-		elt->set = TELT_UNSET;
-
-		simple_unlock(&timer_lock);
-		splx(s);
-		return (TRUE);
-	    }
-	}
-	simple_unlock(&timer_lock);
-	splx(s);
-	return (FALSE);
+	return reset_timeout(t);
 }
diff --git a/kern/mach_clock.h b/kern/mach_clock.h
index 66903b8a..89fc1891 100644
--- a/kern/mach_clock.h
+++ b/kern/mach_clock.h
@@ -44,20 +44,24 @@ extern time_value64_t	time; 		/* time since bootup (uncorrected) */
 
 typedef void timer_func_t(void *);
 
+struct timeout_handle {
+	unsigned long lo, hi;
+	/* Lowest TIMEOUT_WHEEL_BITS of handle.hi are the
+	 * index into the timeout array of this timeout */
+};
+
 /* Time-out element.  */
-struct timer_elt {
-	queue_chain_t	chain;		/* chain in order of expiration */
+struct timeout {
+	struct timeout *t_next;		/* next timeout in queue */
+	struct timeout **t_back;	/* pointer back to the ptr pointing at this struct */
+	struct timeout_handle handle;	/* handle for this timeout */
 	timer_func_t	*fcn;		/* function to call */
 	void *		param;		/* with this parameter */
-	unsigned long	ticks;		/* expiration time, in ticks */
-	int		set;		/* unset | set | allocated */
+	unsigned long	t_time;		/* expiration time, in ticks >> TIMEOUT_WHEEL_BITS */
 };
-#define	TELT_UNSET	0		/* timer not set */
-#define	TELT_SET	1		/* timer set */
-#define	TELT_ALLOC	2		/* timer allocated from pool */
 
-typedef	struct timer_elt	timer_elt_data_t;
-typedef	struct timer_elt	*timer_elt_t;
+typedef	struct timeout	timeout_data_t;
+typedef	struct timeout	*timeout_t;
 
 
 extern void clock_interrupt(
@@ -70,21 +74,17 @@ extern void softclock (void);
 
 /* For `private' timer elements.  */
 extern void set_timeout(
-   timer_elt_t telt,
+   timeout_t t,
    unsigned int interval);
-extern boolean_t reset_timeout(timer_elt_t telt);
+extern boolean_t reset_timeout(timeout_t t);
 
-#define	set_timeout_setup(telt,fcn,param,interval)	\
-	((telt)->fcn = (fcn),				\
-	 (telt)->param = (param),			\
-	 (telt)->private = TRUE,			\
-	set_timeout((telt), (interval)))
+#define	set_timeout_setup(t,fcn,param,interval)		\
+	((t)->fcn = (fcn),				\
+	 (t)->param = (param),				\
+	set_timeout((t), (interval)))
 
 #define	reset_timeout_check(t)				\
-	MACRO_BEGIN					\
-	if ((t)->set)					\
-	    reset_timeout((t));				\
-	MACRO_END
+	reset_timeout((t))
 
 extern void init_timeout (void);
 
@@ -103,8 +103,8 @@ extern void read_time_stamp (const time_value64_t *stamp, time_value64_t *result
 extern void mapable_time_init (void);
 
 /* For public timer elements.  */
-extern void timeout(timer_func_t *fcn, void *param, int interval);
-extern boolean_t untimeout(timer_func_t *fcn, const void *param);
+extern timeout_t timeout(timer_func_t *fcn, void *param, int interval);
+extern boolean_t untimeout(timeout_t t);
 
 extern int timeopen(dev_t dev, int flag, io_req_t ior);
 extern void timeclose(dev_t dev, int flag);
diff --git a/kern/sched_prim.c b/kern/sched_prim.c
index dd0f492b..aca96038 100644
--- a/kern/sched_prim.c
+++ b/kern/sched_prim.c
@@ -66,7 +66,7 @@ unsigned	sched_tick;
 
 thread_t	sched_thread_id;
 
-timer_elt_data_t recompute_priorities_timer;
+timeout_data_t	recompute_priorities_timer;
 
 /*
  *	State machine
@@ -167,8 +167,6 @@ static void thread_timeout(
 	void *_thread)
 {
 	thread_t thread = _thread;
-	assert(thread->timer.set == TELT_UNSET);
-
 	clear_wait(thread, THREAD_TIMED_OUT, FALSE);
 }
 
diff --git a/kern/thread.h b/kern/thread.h
index 3485f6af..7b96df5d 100644
--- a/kern/thread.h
+++ b/kern/thread.h
@@ -207,8 +207,8 @@ struct thread {
 	time_value64_t	creation_time;
 
 	/* Time-outs */
-	timer_elt_data_t timer;		/* timer for thread */
-	timer_elt_data_t depress_timer;	/* timer for priority depression */
+	timeout_data_t	timer;		/* timer for thread */
+	timeout_data_t	depress_timer;	/* timer for priority depression */
 
 	/* Ast/Halt data structures */
 	/* Defined above */