From 0cb73016818979f0ebf5c6084bbbf5fe2eca287e Mon Sep 17 00:00:00 2001 From: Michel Pollet Date: Sat, 25 Feb 2012 14:45:06 +0000 Subject: [PATCH] cycle_timers: Big rework Removed the old bitfield, implemented a sorted list. Timers get added to the list by (reverse) order of execution do acts as a stack of timers to run and pop out. This considerably simplifies the code, and also makes the code that test for the next timer to run very small and efficient. This should make cycle_timers a lot more scalable, since they are used for many more uses than they were originaly designed for. Signed-off-by: Michel Pollet --- simavr/sim/sim_avr.h | 25 +----- simavr/sim/sim_cycle_timers.c | 141 ++++++++++++++++------------------ simavr/sim/sim_cycle_timers.h | 60 +++++++-------- 3 files changed, 101 insertions(+), 125 deletions(-) diff --git a/simavr/sim/sim_avr.h b/simavr/sim/sim_avr.h index 8e7f8c7..55f0725 100644 --- a/simavr/sim/sim_avr.h +++ b/simavr/sim/sim_avr.h @@ -1,7 +1,7 @@ /* sim_avr.h - Copyright 2008, 2009 Michel Pollet + Copyright 2008-2012 Michel Pollet This file is part of simavr. @@ -22,25 +22,16 @@ #ifndef __SIM_AVR_H__ #define __SIM_AVR_H__ -#include -#include - #ifdef __cplusplus extern "C" { #endif #include "sim_irq.h" - -typedef uint64_t avr_cycle_count_t; -typedef uint16_t avr_io_addr_t; - -// printf() conversion specifier for avr_cycle_count_t -#define PRI_avr_cycle_count PRIu64 +#include "sim_cycle_timers.h" struct avr_t; typedef uint8_t (*avr_io_read_t)(struct avr_t * avr, avr_io_addr_t addr, void * param); typedef void (*avr_io_write_t)(struct avr_t * avr, avr_io_addr_t addr, uint8_t v, void * param); -typedef avr_cycle_count_t (*avr_cycle_timer_t)(struct avr_t * avr, avr_cycle_count_t when, void * param); enum { // SREG bit indexes @@ -231,17 +222,7 @@ typedef struct avr_t { // queue of io modules struct avr_io_t *io_port; - // cycle timers are callbacks that will be called when "when" cycle is reached - // the bitmap allows quick knowledge of whether there is anything to call - // these timers are one shots, then get cleared if the timer function returns zero, - // they get reset if the callback function returns a new cycle number - uint32_t cycle_timer_map; - avr_cycle_count_t next_cycle_timer; - struct { - avr_cycle_count_t when; - avr_cycle_timer_t timer; - void * param; - } cycle_timer[32]; + avr_cycle_timer_pool_t cycle_timers; // interrupt vectors, and their enable/clear registers struct avr_int_vector_t * vector[64]; diff --git a/simavr/sim/sim_cycle_timers.c b/simavr/sim/sim_cycle_timers.c index 3bafa5c..7275b5e 100644 --- a/simavr/sim/sim_cycle_timers.c +++ b/simavr/sim/sim_cycle_timers.c @@ -1,7 +1,7 @@ /* sim_cycle_timers.c - Copyright 2008, 2009 Michel Pollet + Copyright 2008-2012 Michel Pollet This file is part of simavr. @@ -21,28 +21,48 @@ #include #include -#include +#include +#include "sim_avr.h" +#include "sim_time.h" #include "sim_cycle_timers.h" +#define TIMER_COUNT sizeof(cycle_timer) + +// no sanity checks checking here, on purpose +static void avr_cycle_timer_insert(avr_t * avr, avr_cycle_count_t when, avr_cycle_timer_t timer, void * param) +{ + avr_cycle_timer_pool_t * pool = &avr->cycle_timers; + + when += avr->cycle; + + // find it's place int the list + int inserti = 0; + while (inserti < pool->count && pool->timer[inserti].when > when) + inserti++; + // make a hole + int cnt = pool->count - inserti; + if (cnt) + memmove(&pool->timer[inserti + 1], &pool->timer[inserti], + cnt * sizeof(avr_cycle_timer_slot_t)); + + pool->timer[inserti].timer = timer; + pool->timer[inserti].param = param; + pool->timer[inserti].when = when; + pool->count++; +} + void avr_cycle_timer_register(avr_t * avr, avr_cycle_count_t when, avr_cycle_timer_t timer, void * param) { + avr_cycle_timer_pool_t * pool = &avr->cycle_timers; + + // remove it if it was already scheduled avr_cycle_timer_cancel(avr, timer, param); - if (avr->cycle_timer_map == 0xffffffff) { - fprintf(stderr, "avr_cycle_timer_register is full!\n"); + if (pool->count == MAX_CYCLE_TIMERS) { + fprintf(stderr, "%s: pool is full (%d)!\n", __func__, MAX_CYCLE_TIMERS); return; } - when += avr->cycle; - if (when < avr->next_cycle_timer) - avr->next_cycle_timer = when; - for (int i = 0; i < 32; i++) - if (!(avr->cycle_timer_map & (1 << i))) { - avr->cycle_timer[i].timer = timer; - avr->cycle_timer[i].param = param; - avr->cycle_timer[i].when = when; - avr->cycle_timer_map |= (1 << i); - return; - } + avr_cycle_timer_insert(avr, when, timer, param); } void avr_cycle_timer_register_usec(avr_t * avr, uint32_t when, avr_cycle_timer_t timer, void * param) @@ -52,19 +72,15 @@ void avr_cycle_timer_register_usec(avr_t * avr, uint32_t when, avr_cycle_timer_t void avr_cycle_timer_cancel(avr_t * avr, avr_cycle_timer_t timer, void * param) { - if (!avr->cycle_timer_map) - return; - for (int i = 0; i < 32; i++) - if ((avr->cycle_timer_map & (1 << i)) && - avr->cycle_timer[i].timer == timer && - avr->cycle_timer[i].param == param) { - avr->cycle_timer[i].timer = NULL; - avr->cycle_timer[i].param = NULL; - avr->cycle_timer[i].when = 0; - avr->cycle_timer_map &= ~(1 << i); - // no need to reset next_cycle_timer; having too small - // a value there only causes some harmless extra - // computation. + avr_cycle_timer_pool_t * pool = &avr->cycle_timers; + + for (int i = 0; i < pool->count; i++) + if (pool->timer[i].timer == timer && pool->timer[i].param == param) { + int cnt = pool->count - i; + if (cnt) + memmove(&pool->timer[i], &pool->timer[i+1], + cnt * sizeof(avr_cycle_timer_slot_t)); + pool->count--; return; } } @@ -76,16 +92,12 @@ void avr_cycle_timer_cancel(avr_t * avr, avr_cycle_timer_t timer, void * param) avr_cycle_count_t avr_cycle_timer_status(avr_t * avr, avr_cycle_timer_t timer, void * param) { - uint32_t map = avr->cycle_timer_map; + avr_cycle_timer_pool_t * pool = &avr->cycle_timers; - while (map) { - int bit = ffs(map)-1; - if (avr->cycle_timer[bit].timer == timer && - avr->cycle_timer[bit].param == param) { - return 1 + (avr->cycle_timer[bit].when - avr->cycle); + for (int i = 0; i < pool->count; i++) + if (pool->timer[i].timer == timer && pool->timer[i].param == param) { + return 1 + (pool->timer[i].when - avr->cycle); } - map &= ~(1 << bit); - } return 0; } @@ -97,41 +109,24 @@ avr_cycle_timer_status(avr_t * avr, avr_cycle_timer_t timer, void * param) */ avr_cycle_count_t avr_cycle_timer_process(avr_t * avr) { - // If we have previously determined that we don't need to fire - // cycle timers yet, we can do an early exit - if (avr->next_cycle_timer > avr->cycle) - return avr->next_cycle_timer - avr->cycle; - - if (!avr->cycle_timer_map) { - avr->next_cycle_timer = (avr_cycle_count_t)-1; - return (avr_cycle_count_t)-1; - } - - avr_cycle_count_t min = (avr_cycle_count_t)-1; - uint32_t map = avr->cycle_timer_map; - - while (map) { - int bit = ffs(map)-1; - // do it several times, in case we're late - while (avr->cycle_timer[bit].when && avr->cycle_timer[bit].when <= avr->cycle) { - // call it - avr->cycle_timer[bit].when = - avr->cycle_timer[bit].timer(avr, - avr->cycle_timer[bit].when, - avr->cycle_timer[bit].param); - if (avr->cycle_timer[bit].when == 0) { - // clear it - avr->cycle_timer[bit].timer = NULL; - avr->cycle_timer[bit].param = NULL; - avr->cycle_timer[bit].when = 0; - avr->cycle_timer_map &= ~(1 << bit); - break; - } - } - if (avr->cycle_timer[bit].when && avr->cycle_timer[bit].when < min) - min = avr->cycle_timer[bit].when; - map &= ~(1 << bit); - } - avr->next_cycle_timer = min; - return min - avr->cycle; + avr_cycle_timer_pool_t * pool = &avr->cycle_timers; + + if (!pool->count) + return (avr_cycle_count_t)1000; + + do { + avr_cycle_timer_slot_t * timer = &pool->timer[pool->count-1]; + avr_cycle_count_t when = timer->when; + if (when > avr->cycle) + return when - avr->cycle; + do { + when = timer->timer(avr, when, timer->param); + } while (when && when <= avr->cycle); + if (when) + avr_cycle_timer_insert(avr, when - avr->cycle, timer->timer, timer->param); + + pool->count--; + } while (pool->count); + + return (avr_cycle_count_t)1000; } diff --git a/simavr/sim/sim_cycle_timers.h b/simavr/sim/sim_cycle_timers.h index bc4cd14..ce2866c 100644 --- a/simavr/sim/sim_cycle_timers.h +++ b/simavr/sim/sim_cycle_timers.h @@ -19,58 +19,58 @@ along with simavr. If not, see . */ - +/* + * cycle timers are callbacks that will be called when "when" cycle is reached + * these timers are one shots, then get cleared if the timer function returns zero, + * they get reset if the callback function returns a new cycle number + * + * the implementation maintains a list of 'pending' timers, sorted by when they + * should run, it allows very quick comparison with the next timer to run, and + * quick removal of then from the pile once dispatched. + */ #ifndef __SIM_CYCLE_TIMERS_H___ #define __SIM_CYCLE_TIMERS_H___ -#include "sim_avr.h" +#include "sim_avr_types.h" #ifdef __cplusplus extern "C" { #endif -// converts a number of usec to a number of machine cycles, at current speed -static inline avr_cycle_count_t avr_usec_to_cycles(avr_t * avr, uint32_t usec) -{ - return avr->frequency * (avr_cycle_count_t)usec / 1000000; -} - -// converts back a number of cycles to usecs (for usleep) -static inline uint32_t avr_cycles_to_usec(avr_t * avr, avr_cycle_count_t cycles) -{ - return 1000000L * cycles / avr->frequency; -} - -// converts back a number of cycles to nsecs -static inline uint64_t avr_cycles_to_nsec(avr_t * avr, avr_cycle_count_t cycles) -{ - return (uint64_t)1E6 * (uint64_t)cycles / (avr->frequency/1000); -} - -// converts a number of hz (to megahertz etc) to a number of cycle -static inline avr_cycle_count_t avr_hz_to_cycles(avr_t * avr, uint32_t hz) -{ - return avr->frequency / hz; -} +#define MAX_CYCLE_TIMERS 32 + +typedef avr_cycle_count_t (*avr_cycle_timer_t)(struct avr_t * avr, avr_cycle_count_t when, void * param); + +typedef struct avr_cycle_timer_slot_t { + avr_cycle_count_t when; + avr_cycle_timer_t timer; + void * param; +} avr_cycle_timer_slot_t; + +typedef struct avr_cycle_timer_pool_t { + avr_cycle_timer_slot_t timer[MAX_CYCLE_TIMERS]; + uint8_t count; +} avr_cycle_timer_pool_t, *avr_cycle_timer_pool_p; + // register for calling 'timer' in 'when' cycles -void avr_cycle_timer_register(avr_t * avr, avr_cycle_count_t when, avr_cycle_timer_t timer, void * param); +void avr_cycle_timer_register(struct avr_t * avr, avr_cycle_count_t when, avr_cycle_timer_t timer, void * param); // register a timer to call in 'when' usec -void avr_cycle_timer_register_usec(avr_t * avr, uint32_t when, avr_cycle_timer_t timer, void * param); +void avr_cycle_timer_register_usec(struct avr_t * avr, uint32_t when, avr_cycle_timer_t timer, void * param); // cancel a previously set timer -void avr_cycle_timer_cancel(avr_t * avr, avr_cycle_timer_t timer, void * param); +void avr_cycle_timer_cancel(struct avr_t * avr, avr_cycle_timer_t timer, void * param); /* * Check to see if a timer is present, if so, return the number (+1) of * cycles left for it to fire, and if not present, return zero */ avr_cycle_count_t -avr_cycle_timer_status(avr_t * avr, avr_cycle_timer_t timer, void * param); +avr_cycle_timer_status(struct avr_t * avr, avr_cycle_timer_t timer, void * param); // // Private, called from the core // -avr_cycle_count_t avr_cycle_timer_process(avr_t * avr); +avr_cycle_count_t avr_cycle_timer_process(struct avr_t * avr); #ifdef __cplusplus }; -- 2.39.5