Timeouts are now very fast to look up - almost O(1) when there are few,
otherwise a much shorter list is traversed rather than all of them.
This is achieved by storing the elements by index into a circular array
as the time to expiry modulo the wheel size. Each spoke of the wheel
stores a short queue containing the elements that match the expiry time.
Therefore only timeouts that are set to likely expire at elapsed_ticks
are checked during the clock interrupt, saving unnecessary processing time.
This speeds up boot time noticably and therefore should be faster to run
generally. The thread timers are stored within the thread structures
themselves, so there is no arbitrary limit on their number, however for
legacy timeouts there are NTIMERS == 20 currently allocated statically
for things like comtimer (serial driver) which are in a reusable array.
TESTED: On Hurd i386 UP+apic
---
device/chario.c | 6 +-
device/tty.h | 2 +
i386/i386at/ioapic.c | 2 +-
kern/mach_clock.c | 276 +++++++++++++++++++++++--------------------
kern/mach_clock.h | 37 +++---
kern/sched_prim.c | 4 +-
kern/thread.h | 4 +-
7 files changed, 178 insertions(+), 153 deletions(-)
diff --git a/device/chario.c b/device/chario.c
index efb55867..660468f6 100644
--- a/device/chario.c
+++ b/device/chario.c
@@ -880,7 +880,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
{
@@ -932,7 +932,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);
}
@@ -952,7 +952,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 3f8b2f63..e2239ea5 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 dba8e5e1..6d9e6db9 100644
--- a/i386/i386at/ioapic.c
+++ b/i386/i386at/ioapic.c
@@ -228,7 +228,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 d7858a79..3c12ec39 100644
--- a/kern/mach_clock.c
+++ b/kern/mach_clock.c
@@ -65,12 +65,22 @@
#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 }; /* wallclock time (unadjusted) */
time_value64_t uptime = { 0, 0 }; /* time since bootup */
unsigned long elapsed_ticks = 0; /* ticks elapsed since bootup */
+unsigned long softticks = 0; /* like elapsed_ticks but for
softclock() */
+
+def_simple_lock_irq_data(static, timeout_lock) /* lock for accessing
static list of timeouts */
+def_simple_lock_irq_data(static, twheel_lock) /* lock for accessing
timeoutwheel of timeouts */
+queue_head_t timeoutwheel[TIMEOUT_WHEEL_SIZE]; /* timeoutwheel of timeout
lists */
+static timeout_t nextsoftcheck; /* next timeout to be checked */
int timedelta = 0;
int tickdelta = 0;
@@ -82,6 +92,8 @@ unsigned tickadj = 500 / HZ; /* can adjust 100 usecs
per second */
#endif
unsigned bigadj = 1000000; /* adjust 10*tickadj if adjustment
> bigadj */
+#define NTIMERS 20
+timeout_data_t timeout_timers[NTIMERS] = {0};
/* A high-precision (hardware) clock is taken into account to increase the
* accuracy of the functions used for getting time (e.g. host_get_time64()).
@@ -161,9 +173,6 @@ MACRO_BEGIN
\
time_value64_add_hpc(uptime, _last_hpc); \
MACRO_END
-def_simple_lock_irq_data(static, timer_lock) /* lock for ... */
-timer_elt_data_t timer_head; /* ordered list of timeouts */
- /* (doubles as end-of-list) */
/*
* Handle clock interrupts.
@@ -249,23 +258,20 @@ 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.
+ * timeouts.
*/
- s = simple_lock_irq(&timer_lock);
+ s = simple_lock_irq(&twheel_lock);
elapsed_ticks++;
- telt = (timer_elt_t)queue_first(&timer_head.chain);
- if (telt->ticks <= elapsed_ticks)
- needsoft = TRUE;
- simple_unlock_irq(s, &timer_lock);
+ if (!queue_empty(&timeoutwheel[elapsed_ticks & TIMEOUT_WHEEL_MASK]))
+ needsoft = TRUE;
+ simple_unlock_irq(s, &twheel_lock);
/*
* Increment the time-of-day clock.
@@ -310,122 +316,156 @@ void clock_interrupt(
else {
setsoftclock();
}
+ } else if (softticks + 1 == elapsed_ticks) {
+ ++softticks;
}
}
last_hpc_read = hpclock_read_counter();
}
-/*
- * 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 queue_head_t *spoke;
+ register int steps; /* number of steps taken since we last allowed
interrupts */
+ register unsigned long curticks;
spl_t s;
- timer_elt_t telt;
- void (*fcn)( void * param );
- void *param;
-
- while (TRUE) {
- s = simple_lock_irq(&timer_lock);
- telt = (timer_elt_t) queue_first(&timer_head.chain);
- if (telt->ticks > elapsed_ticks) {
- simple_unlock_irq(s, &timer_lock);
- break;
- }
- fcn = telt->fcn;
- param = telt->param;
-
- remqueue(&timer_head.chain, (queue_entry_t)telt);
- telt->set = TELT_UNSET;
- simple_unlock_irq(s, &timer_lock);
- assert(fcn != 0);
- (*fcn)(param);
+ steps = 0;
+ s = simple_lock_irq(&twheel_lock);
+ while (softticks != elapsed_ticks) {
+ ++softticks;
+ curticks = softticks;
+ spoke = &timeoutwheel[curticks & TIMEOUT_WHEEL_MASK];
+ t = NULL;
+ if (!queue_empty(spoke))
+ t = (timeout_t)queue_next(spoke);
+ while (t) {
+ if (t->t_time != curticks) {
+ /* Cannot check tail via spoke because it's the
wrong list */
+ if (t->chain.next ==
(queue_entry_t)&timeoutwheel[t->t_time & TIMEOUT_WHEEL_MASK])
+ t = NULL;
+ else
+ t = (timeout_t)queue_next(&t->chain);
+
+ if (++steps >= MAX_SOFTCLOCK_STEPS) {
+ nextsoftcheck = t;
+ simple_unlock_irq(s, &twheel_lock); /*
Give hardclock() a chance */
+ s = simple_lock_irq(&twheel_lock);
+ t = nextsoftcheck;
+ steps = 0;
+ }
+ } else {
+ void (*t_fcn)(void *);
+ void *t_arg;
+
+ if (t->chain.next == spoke)
+ nextsoftcheck = NULL;
+ else
+ nextsoftcheck =
(timeout_t)queue_next(&t->chain);
+ queue_remove(spoke, t, timeout_t, chain);
+ t->chain.prev = t->chain.next = NULL;
+ t_fcn = t->fcn;
+ t_arg = t->param;
+ if (t->set & TIMEOUT_ALLOC)
+ t->set = TIMEOUT_ALLOC;
+ else
+ t->set &= ~TIMEOUT_PENDING;
+ simple_unlock_irq(s, &twheel_lock);
+ assert(t_fcn != 0);
+ t_fcn(t_arg); /* call function at elapsed */
+ s = simple_lock_irq(&twheel_lock);
+ steps = 0;
+ t = nextsoftcheck;
+ }
+ }
}
+ nextsoftcheck = NULL;
+ simple_unlock_irq(s, &twheel_lock);
}
/*
* 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;
+ unsigned int index;
+ spl_t s;
- s = simple_lock_irq(&timer_lock);
+ if (t->set & (TIMEOUT_ACTIVE | TIMEOUT_PENDING))
+ reset_timeout(t);
- /* Start counting after next tick, to avoid partial ticks. */
- interval += elapsed_ticks + 1;
+ s = simple_lock_irq(&twheel_lock);
- for (next = (timer_elt_t)queue_first(&timer_head.chain);
- ;
- next = (timer_elt_t)queue_next((queue_entry_t)next)) {
+ if (!interval)
+ interval = 1;
+
+ assert (!(t->set & (TIMEOUT_ACTIVE | TIMEOUT_PENDING)));
+
+ t->set |= TIMEOUT_ACTIVE | TIMEOUT_PENDING;
+ t->t_time = elapsed_ticks + interval;
+ index = t->t_time & TIMEOUT_WHEEL_MASK;
- 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_irq(s, &timer_lock);
+ queue_enter(&timeoutwheel[index], t, timeout_t, chain);
+
+ simple_unlock_irq(s, &twheel_lock);
}
-boolean_t reset_timeout(timer_elt_t telt)
+boolean_t reset_timeout(timeout_t t)
{
- spl_t s;
+ queue_head_t *spoke;
+ spl_t s;
+
+ s = simple_lock_irq(&twheel_lock);
+ if (!(t->set & TIMEOUT_PENDING)) {
+ t->set &= ~TIMEOUT_ACTIVE;
+ simple_unlock_irq(s, &twheel_lock);
+ return FALSE;
+ }
+
+ t->set &= ~(TIMEOUT_PENDING | TIMEOUT_ACTIVE);
- s = simple_lock_irq(&timer_lock);
- if (telt->set) {
- remqueue(&timer_head.chain, (queue_entry_t)telt);
- telt->set = TELT_UNSET;
- simple_unlock_irq(s, &timer_lock);
- return TRUE;
+ spoke = &timeoutwheel[t->t_time & TIMEOUT_WHEEL_MASK];
+
+ if (nextsoftcheck == t) {
+ if (t->chain.next == spoke)
+ nextsoftcheck = NULL;
+ else
+ nextsoftcheck = (timeout_t)queue_next(&t->chain);
}
- else {
- simple_unlock_irq(s, &timer_lock);
- return FALSE;
+
+ if (!queue_empty(spoke)) {
+ queue_remove(spoke, t, timeout_t, chain);
+ t->chain.prev = t->chain.next = NULL;
+ simple_unlock_irq(s, &twheel_lock);
+ return TRUE;
}
+ simple_unlock_irq(s, &twheel_lock);
+ return FALSE;
}
void init_timeout(void)
{
- simple_lock_init_irq(&timer_lock);
- queue_init(&timer_head.chain);
- timer_head.ticks = ~0; /* MAXUINT - sentinel */
+ int i;
+ simple_lock_init_irq(&timeout_lock);
+ simple_lock_init_irq(&twheel_lock);
+ for (i = 0; i < TIMEOUT_WHEEL_SIZE; i++)
+ queue_init(&timeoutwheel[i]);
elapsed_ticks = 0;
+ softticks = 0;
}
/*
@@ -677,10 +717,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.
*
@@ -688,51 +724,39 @@ 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;
-
- s = simple_lock_irq(&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_irq(s, &timer_lock);
-
- set_timeout(elt, (unsigned int)interval);
+ timeout_t t;
+ int i;
+ spl_t s;
+
+ s = simple_lock_irq(&timeout_lock);
+ for (i = 0; i < NTIMERS; i++) {
+ t = &timeout_timers[i];
+ if (!(t->set & TIMEOUT_ACTIVE))
+ break;
+ }
+ if (i == NTIMERS)
+ panic("more than NTIMERS timeouts");
+
+ t->set |= TIMEOUT_ALLOC;
+ t->fcn = fcn;
+ t->param = param;
+ simple_unlock_irq(s, &timeout_lock);
+
+ set_timeout(t, interval);
+
+ 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 = simple_lock_irq(&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_irq(s, &timer_lock);
- return (TRUE);
- }
- }
- simple_unlock_irq(s, &timer_lock);
- return (FALSE);
+ return reset_timeout(t);
}
diff --git a/kern/mach_clock.h b/kern/mach_clock.h
index e83b638c..248aab7c 100644
--- a/kern/mach_clock.h
+++ b/kern/mach_clock.h
@@ -46,20 +46,20 @@ extern time_value64_t uptime; /* time since
bootup */
typedef void timer_func_t(void *);
/* Time-out element. */
-struct timer_elt {
- queue_chain_t chain; /* chain in order of expiration */
+struct timeout {
+ queue_chain_t chain; /* chain of timeouts */
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 elapsed
from boot */
+ unsigned char set; /* active | pending | allocated from
pool */
};
-#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;
+#define TIMEOUT_ALLOC 0x1 /* timeout allocated from pool
*/
+#define TIMEOUT_ACTIVE 0x2 /* timeout active */
+#define TIMEOUT_PENDING 0x4 /* timeout waiting for expiry */
extern void clock_interrupt(
int usec,
@@ -71,19 +71,18 @@ 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) \
+ if ((t)->set & TIMEOUT_ACTIVE) \
reset_timeout((t)); \
MACRO_END
@@ -104,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 bcbfa160..5aa65811 100644
--- a/kern/sched_prim.c
+++ b/kern/sched_prim.c
@@ -67,7 +67,7 @@ unsigned sched_tick;
thread_t sched_thread_id;
-timer_elt_data_t recompute_priorities_timer;
+timeout_data_t recompute_priorities_timer;
/*
* State machine
@@ -185,7 +185,7 @@ static void thread_timeout(
void *_thread)
{
thread_t thread = _thread;
- assert(thread->timer.set == TELT_UNSET);
+ assert(!(thread->timer.set & TIMEOUT_PENDING));
clear_wait(thread, THREAD_TIMED_OUT, FALSE);
}
diff --git a/kern/thread.h b/kern/thread.h
index 0702e1b4..e5128dad 100644
--- a/kern/thread.h
+++ b/kern/thread.h
@@ -212,8 +212,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 */
--
2.45.2
