Timeouts are now very fast to look up, at the expense of more memory, a much shorter list is traversed rather than all of them. See [1]. Timeouts that are stopped before expiry are now faster to remove, and inserting a timeout is faster.
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 [1] Costello & Varghese 1995: https://doi.org/10.7936/K7VM49H5 --- device/chario.c | 8 +- device/tty.h | 2 + i386/i386at/ioapic.c | 2 +- kern/mach_clock.c | 273 ++++++++++++++++++++++--------------------- kern/mach_clock.h | 36 +++--- kern/sched_prim.c | 4 +- kern/thread.h | 4 +- 7 files changed, 171 insertions(+), 158 deletions(-) diff --git a/device/chario.c b/device/chario.c index efb55867..9f00e240 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); + reset_timeout(tp->t_timeout); } tty_queue_completion(&tp->t_delayed_read); } @@ -943,7 +943,7 @@ void ttyinput( * Otherwise set the character received during timeout interval * flag. * One alternative approach would be just to reset the timeout - * into the future, but this involves making a timeout/untimeout + * into the future, but this involves making a timeout/reset_timeout * call on every character. */ int ptime = pdma_timeouts[tp->t_ispeed]; @@ -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..38e3114e 100644 --- a/kern/mach_clock.c +++ b/kern/mach_clock.c @@ -66,11 +66,33 @@ #define MICROSECONDS_IN_ONE_SECOND 1000000 +/* See Costello & Varghese 1995: https://doi.org/10.7936/K7VM49H5 */ + +#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) +#define TIMEOUT_WHEEL_QUEUE(ticks) (&timeoutwheel[ticks & TIMEOUT_WHEEL_MASK]) + 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; /* last tick we have checked for timers */ + +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 */ + +/* Timeouts are now very fast to look up - dividing the complexity by up to + * TIMEOUT_WHEEL_SIZE, at the expense of TIMEOUT_WHEEL_SIZE times more storage. + * + * 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. + * Each element per queue is inserted at the end, so not necessarily sorted by expiry. */ +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 +104,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 +185,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,7 +270,6 @@ void clock_interrupt( if (my_cpu == master_cpu) { spl_t s; - timer_elt_t telt; boolean_t needsoft = FALSE; @@ -258,14 +278,13 @@ void clock_interrupt( * 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) + if (!queue_empty(TIMEOUT_WHEEL_QUEUE(elapsed_ticks))) needsoft = TRUE; - simple_unlock_irq(s, &timer_lock); + simple_unlock_irq(s, &twheel_lock); /* * Increment the time-of-day clock. @@ -310,122 +329,141 @@ void clock_interrupt( else { setsoftclock(); } + } else if (softticks + 1 == elapsed_ticks) { + /* When there are no timers expiring in this tick + * we catch up softticks so it does not fall behind */ + ++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. */ + timeout_t t; + queue_head_t *spoke; + int steps; /* number of reinterrupts of hardclock during this softclock */ + 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 = TIMEOUT_WHEEL_QUEUE(curticks); + t = (timeout_t)queue_next(spoke); + /* Iterate over all elements within spoke checking that we did not wrap back to a spoke */ + while (! ((t >= (timeout_t)&timeoutwheel[0]) + && (t < (timeout_t)&timeoutwheel[TIMEOUT_WHEEL_SIZE])) ) { + if (t->t_time != curticks) { + t = (timeout_t)queue_next(&t->chain); + + if (++steps >= MAX_SOFTCLOCK_STEPS) { + nextsoftcheck = t; + /* Give hardclock() a chance, so that we don't delay the clock interrupts */ + simple_unlock_irq(s, &twheel_lock); + s = simple_lock_irq(&twheel_lock); + t = nextsoftcheck; + steps = 0; + } + } else { + void (*t_fcn)(void *); + void *t_arg; + + 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; + spl_t s; + + if (t->set & (TIMEOUT_ACTIVE | TIMEOUT_PENDING)) + reset_timeout(t); + + s = simple_lock_irq(&twheel_lock); - s = simple_lock_irq(&timer_lock); + assert (!(t->set & (TIMEOUT_ACTIVE | TIMEOUT_PENDING))); + + t->set |= TIMEOUT_ACTIVE | TIMEOUT_PENDING; /* Start counting after next tick, to avoid partial ticks. */ - interval += elapsed_ticks + 1; + t->t_time = elapsed_ticks + interval + 1; - for (next = (timer_elt_t)queue_first(&timer_head.chain); - ; - next = (timer_elt_t)queue_next((queue_entry_t)next)) { + /* Insert new timeout at the end of the corresponding wheel entry. */ + queue_enter(TIMEOUT_WHEEL_QUEUE(t->t_time), t, timeout_t, chain); - if (next->ticks > interval) - break; - } - telt->ticks = interval; - /* - * Insert new timer element before 'next' - * (after 'next'->prev) - */ - insque((queue_entry_t) telt, ((queue_entry_t)next)->prev); - telt->set = TELT_SET; - simple_unlock_irq(s, &timer_lock); + simple_unlock_irq(s, &twheel_lock); } -boolean_t reset_timeout(timer_elt_t telt) +boolean_t reset_timeout(timeout_t t) { - spl_t s; - - 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; - } - else { - simple_unlock_irq(s, &timer_lock); - return FALSE; + 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); + + spoke = TIMEOUT_WHEEL_QUEUE(t->t_time); + + if (nextsoftcheck == t) + nextsoftcheck = (timeout_t)queue_next(&t->chain); + + assert (!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; } 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 +715,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 +722,30 @@ 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); -} - -/* - * Returns a boolean indicating whether the timeout element was found - * and removed. - */ -boolean_t untimeout(void (*fcn)( void * param ), const void *param) -{ - spl_t s; - timer_elt_t elt; + 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"); - s = simple_lock_irq(&timer_lock); - queue_iterate(&timer_head.chain, elt, timer_elt_t, chain) { + t->set |= TIMEOUT_ALLOC; + t->fcn = fcn; + t->param = param; + simple_unlock_irq(s, &timeout_lock); - if ((fcn == elt->fcn) && (param == elt->param)) { - /* - * Found it. - */ - remqueue(&timer_head.chain, (queue_entry_t)elt); - elt->set = TELT_UNSET; + set_timeout(t, interval); - simple_unlock_irq(s, &timer_lock); - return (TRUE); - } - } - simple_unlock_irq(s, &timer_lock); - return (FALSE); + return t; } diff --git a/kern/mach_clock.h b/kern/mach_clock.h index e83b638c..5cd6ded3 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, we do not sort by expiry to save time */ 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,7 @@ 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 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
