From ed491e029999be79967e1b03d44d4c4d6546969d Mon Sep 17 00:00:00 2001 From: Damien Zammit Date: Fri, 28 Jul 2023 21:50:16 +1000 Subject: mach_clock: Use a callwheel structure as per Costello & Varghese 1995 Boots to userspace but netdde freezes trying to bring up eth0 --- device/chario.c | 6 +- device/tty.h | 2 + i386/i386at/ioapic.c | 2 +- kern/mach_clock.c | 303 ++++++++++++++++++++++++++------------------------- kern/mach_clock.h | 44 ++++---- kern/sched_prim.c | 4 +- kern/thread.h | 4 +- 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 +#include #include #include @@ -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 #include +#include #include #include #include @@ -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 */ -- cgit v1.2.3