diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/heap.c | 113 | ||||
| -rw-r--r-- | lib/heap.h | 46 | ||||
| -rw-r--r-- | lib/qtime.c | 122 | ||||
| -rw-r--r-- | lib/qtime.h | 24 | ||||
| -rw-r--r-- | lib/qtimers.c | 100 | ||||
| -rw-r--r-- | lib/qtimers.h | 30 |
6 files changed, 283 insertions, 152 deletions
@@ -60,7 +60,7 @@ * ---------------------------- * Comparison function for heap. * - * int heap_cmp(...** a, ...**) ... + * int heap_cmp(...** a, ...** b) ... * * Must return -1, 0, +1 : where -1 => a < b, 0 => a == b & +1 => a > b * @@ -90,6 +90,9 @@ heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp, * * ... = heap_new_init_simple(NULL, 0, (heap_cmp*)my_cmp) * + * See: #define heap_init_new_simple(h, size, cmp) + * #define heap_init_new_backlinked(h, size, cmp, offset) + * * NB: when initialising an existing heap structure it is ESSENTIAL that * any previous heap and its contents have been released, because this * function simply discards whatever was there before. (This function may @@ -107,15 +110,17 @@ heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp, * a field of type heap_backlink_t in the item structure, and it is the * offset of that which must be initialised here, eg: * - * ... = heap_new_init_backlink(NULL, 0, (heap_cmp*)my_cmp, + * ... = heap_new_init_backlinked(NULL, 0, (heap_cmp*)my_cmp, * offset_of(struct xxx_heap_item, backlink)) ; * * This adds a little extra work to every change in the heap -- keeping the * backlink of any moved item up to date. But avoids a linear search for * every heap_delete_item or heap_update_item. + * + * Returns the heap which has been initialised. */ heap -heap_init_new(heap h, vector_index size, heap_cmp* cmp, +heap_init_new(heap h, unsigned int size, heap_cmp* cmp, int with_backlink, unsigned int backlink_offset) { if (h == NULL) @@ -126,16 +131,21 @@ heap_init_new(heap h, vector_index size, heap_cmp* cmp, return heap_setup(h, 1, size, cmp, with_backlink, backlink_offset) ; } ; -/* Re-Initialize heap (or create a new one, if h == NULL). +/* Reinitialise heap (or create a new one, if h == NULL). * * Allocates heap structure if none given -- allocating vector if size != 0. * Otherwise, re-initialise the heap and any vector (reusing its memory). * - * NB: when re-initialising an existing heap it is the caller's + * See: #define heap_re_init_simple(h, size, cmp) + * #define heap_re_init_backlinked(h, size, cmp, offset) + * + * NB: when reinitialising an existing heap it is the caller's * responsibility to release any item values *before* doing this. + * + * Returns the heap that has been reinitialised. */ heap -heap_re_init(heap h, vector_index size, heap_cmp* cmp, +heap_re_init(heap h, unsigned int size, heap_cmp* cmp, int with_backlink, unsigned int backlink_offset) { if (h == NULL) @@ -147,7 +157,7 @@ heap_re_init(heap h, vector_index size, heap_cmp* cmp, /* Release heap contents (underlying vector), and (if required) release the * heap structure. * - * Return NULL if releases heap, otherwise the address of the heap. + * Returns NULL if releases heap, otherwise the reset heap. * * If does not release the heap, it retains the comparison function and any * backlink setting -- so heap can be reused without reinitialising it. @@ -158,7 +168,7 @@ heap_re_init(heap h, vector_index size, heap_cmp* cmp, heap heap_reset(heap h, int free_structure) { - vector_reset(&h->v, 0) ; + vector_reset_keep(&h->v) ; /* vector structure is embedded in the heap */ if (free_structure) XFREE(MTYPE_VECTOR, h) ; /* sets h = NULL */ @@ -169,7 +179,7 @@ heap_reset(heap h, int free_structure) /* Common set-up for heap_init_new() & heap_reset(). */ static heap -heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp, +heap_setup(heap h, int new_vector, unsigned int size, heap_cmp* cmp, int with_backlink, unsigned int backlink_offset) { assert(cmp != NULL) ; /* or there will be tears */ @@ -191,9 +201,12 @@ heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp, * If heap is empty, release the underlying vector, and (if required) release * the heap structure. * + * See: #define heap_ream_free(h) heap_ream(h, 1) + * #define heap_ream_keep(h) heap_ream(h, 0) + * * Useful for emptying out and resetting/discarding a heap: * - * while ((p_v = heap_ream(h, 1))) + * while ((p_v = heap_ream_free(h))) * ... do what's required to release the item p_v * * Returns NULL when heap is empty (and structure has been freed, if required). @@ -226,7 +239,7 @@ heap_ream(heap h, int free_structure) /* Pop item off the heap. * - * Returns NULL if heap is empty. + * Returns the popped value, which is NULL if the heap was (and still is) empty. */ p_vector_item heap_pop_item(heap h) @@ -247,9 +260,9 @@ heap_pop_item(heap h) /* Pop one item off the heap and promptly push another. * - * In this combination the pop is essentially free. + * In this combination, the pop is essentially free. * - * Returns NULL if heap was empty. + * Returns the popped value, which is NULL if the heap was (and still is) empty. */ p_vector_item heap_pop_push_item(heap h, p_vector_item p_v) @@ -285,15 +298,13 @@ heap_delete_item(heap h, p_vector_item p_v) p_vector_item p_x ; vector_index i ; - i = heap_find_item(h, p_v) ; - - p_x = vector_pop_item(&h->v) ; /* extract last item, if any */ + i = heap_find_item(h, p_v) ; /* index of item to be deleted */ - if (i == h->v.end) - return ; /* stop now if deleting last item */ + p_x = vector_pop_item(&h->v) ; /* extract last item, if any */ - heap_bubble(h, i, p_x) ; /* move what was last into position */ - /* updating any backlink */ + if (i < h->v.end) /* if not deleting the last item... */ + heap_bubble(h, i, p_x) ; /* ...reinsert what was last, at the delete */ + /* position, updating any backlink */ } ; /*============================================================================== @@ -303,7 +314,10 @@ heap_delete_item(heap h, p_vector_item p_v) /* Push entire vector onto heap copying or moving items as required. * * Copy or move vector to end of heap's vector, then move each - * (non-NULL) item into heap order. + * (non-NULL) item into heap order (discarding any NULL items). + * + * See: #define heap_push_vector_copy(h, v) + * #define heap_push_vector_move(h, v) */ void heap_push_vector(heap h, vector v, int move_vector) @@ -311,6 +325,7 @@ heap_push_vector(heap h, vector v, int move_vector) vector_index i = h->v.end ; vector_index e ; vector_index n = v->end ; + p_vector_item p_v ; if (move_vector) vector_move_append(&h->v, v) ; @@ -319,7 +334,7 @@ heap_push_vector(heap h, vector v, int move_vector) e = i ; /* old end of the heap. */ while (n--) { - p_vector_item p_v = h->v.p_items[i++] ; + p_v = h->v.p_items[i++] ; if (p_v != NULL) heap_bubble_up(h, e++, p_v) ; /* move new item into position in heap */ /* setting any backlink */ @@ -334,6 +349,9 @@ heap_push_vector(heap h, vector v, int move_vector) * * Moves or copies the contents of the heap. * + * See: #define heap_pop_vector_copy(v, h) + * #define heap_pop_vector_move(v, h) + * * NB: when creating new vector, will be exactly the required size. * * NB: if re-initialising existing vector, it is the caller's responsibility @@ -406,18 +424,23 @@ heap_bubble(heap h, vector_index i, p_vector_item p_v) private void heap_bubble_up(heap h, vector_index i, p_vector_item p_v) { - p_vector_item* ha = h->v.p_items ; /* underlying array */ + p_vector_item* ha = h->v.p_items ; /* underlying array */ + vector_index ip ; /* index of parent */ + p_vector_item p_p ; /* pointer to parent item */ + dassert(ha != NULL) ; while (i != 0) { - vector_index ip = HEAP_UP(i) ; - p_vector_item p_p = &ha[ip] ; /* pointer to parent */ + ip = HEAP_UP(i) ; + p_p = &ha[ip] ; /* get parent */ + + if (h->cmp(&p_v, &p_p) >= 0) + break ; /* stop when value >= parent */ - if (h->cmp(&p_p, &p_v) <= 0) - break ; /* stop when parent is <= us */ ha[i] = p_p ; /* move parent down... */ heap_set_backlink(h, p_p, i) ; /* ...updating any backlink */ + i = ip ; /* move up the heap */ } ; @@ -433,38 +456,40 @@ heap_bubble_up(heap h, vector_index i, p_vector_item p_v) private void heap_bubble_down(heap h, vector_index i, p_vector_item p_v) { - vector_index e = h->v.end ; /* end of heap */ - p_vector_item* ha = h->v.p_items ; /* underlying array */ + vector_index e = h->v.end ; /* end of heap */ + vector_index ic ; /* index of child */ + vector_index is ; /* index of sibling */ + p_vector_item p_c ; /* pointer to child */ + p_vector_item p_s ; /* pointer to sibling */ + + p_vector_item* ha = h->v.p_items ; /* underlying array */ dassert(ha != NULL) ; while (1) { - vector_index ic ; /* index of child */ - vector_index is ; /* index of sibling */ - p_vector_item p_c ; /* pointer to child */ - p_vector_item p_s ; /* pointer to sibling */ - ic = HEAP_DOWN(i) ; if (ic >= e) - break ; /* Quit if run out of heap ! */ - p_c = &ha[ic] ; + break ; /* Quit if run out of heap ! */ + p_c = &ha[ic] ; /* get left hand child */ is = ic + 1 ; - if (is < e) + if (is < e) /* is there a right hand child ? */ { - p_s = &ha[is] ; + p_s = &ha[is] ; /* get right hand child */ if (h->cmp(&p_s, &p_c) < 0) { - ic = is ; /* select smaller sibling */ + ic = is ; /* select smaller sibling */ p_c = p_s ; } ; } ; if (h->cmp(&p_v, &p_c) <= 0) - break ; /* stop when we are <= both children */ - ha[i] = p_c ; /* move smaller child up */ - heap_set_backlink(h, p_c, i) ; /* ...updating any backlink */ - i = ic ; /* move down the heap */ + break ; /* stop when <= both children */ + + ha[i] = p_c ; /* move smaller child up */ + heap_set_backlink(h, p_c, i) ; /* ...updating any backlink */ + + i = ic ; /* move down the heap */ } ; ha[i] = p_v ; /* place in new position... */ @@ -483,7 +508,7 @@ heap_find_item(heap h, p_vector_item p_v) { for (i = 0 ; i < h->v.end ; ++i) if (h->v.p_items[i] == p_v) - break ; + return i ; } ; assert((i < h->v.end) && (h->v.p_items[i] == p_v)) ; @@ -24,11 +24,19 @@ #define Inline static inline #endif +/*============================================================================== + * Data structures etc. + */ + typedef int heap_cmp(p_vector_item* a, p_vector_item*) ; enum heap_state { Heap_Has_Backlink = 0x01, /* Set if backlink set */ -}; +} ; + +typedef vector_index heap_backlink_t ; + +typedef struct heap* heap ; struct heap { @@ -38,39 +46,37 @@ struct heap unsigned int backlink_offset ; struct vector v ; -}; - -typedef struct heap* heap; - -typedef vector_index heap_backlink_t ; +} ; -/* Prototypes. */ +/*============================================================================== + * Prototypes. + */ -extern heap heap_init_new(heap h, vector_index size, heap_cmp* cmp, +extern heap heap_init_new(heap h, unsigned int size, heap_cmp* cmp, int with_backlink, unsigned int backlink_offset) ; #define heap_init_new_simple(h, size, cmp) \ heap_init_new(h, size, cmp, 0, 0) -#define heap_init_new_backlinked(h, size, cmp, off) \ - heap_init_new(h, size, cmp, 1, off) +#define heap_init_new_backlinked(h, size, cmp, offset) \ + heap_init_new(h, size, cmp, 1, offset) -extern heap heap_re_init(heap h, vector_index size, heap_cmp* cmp, +extern heap heap_re_init(heap h, unsigned int size, heap_cmp* cmp, int with_backlink, unsigned int backlink_offset) ; #define heap_re_init_simple(h, size, cmp) \ heap_re_init(h, size, cmp, 0, 0) -#define heap_re_init_backlinked(h, size, cmp, off) \ - heap_re_init(h, size, cmp, 1, off) +#define heap_re_init_backlinked(h, size, cmp, offset) \ + heap_re_init(h, size, cmp, 1, offset) extern heap heap_reset(heap h, int free_structure) ; extern p_vector_item heap_ream(heap h, int free_structure) ; /* Reset heap and free the heap structure. */ -#define heap_reset_free(h) heap_reset(h, 1) ; +#define heap_reset_free(h) heap_reset(h, 1) /* Reset heap but keep the heap structure. */ -#define heap_reset_keep(h) heap_reset(h, 0) ; +#define heap_reset_keep(h) heap_reset(h, 0) /* Ream out heap and free the heap structure. */ -#define heap_ream_free(h) heap_ream(h, 1) ; +#define heap_ream_free(h) heap_ream(h, 1) /* Ream out heap but keep the heap structure. */ -#define heap_ream_keep(h) heap_ream(h, 0) ; +#define heap_ream_keep(h) heap_ream(h, 0) Inline void heap_push_item(heap h, p_vector_item p_v) ; extern p_vector_item heap_pop_item(heap h) ; @@ -92,8 +98,6 @@ extern vector heap_pop_vector(vector v, heap h, int move_heap) ; #define heap_pop_vector_move(v, h) \ heap_pop_vector(v, h, 1) -extern vector heap_vector(heap h, int unset_heap_order) ; - /*============================================================================== * This are extern only for use in Inline and other friends */ @@ -146,10 +150,8 @@ heap_update_top_item(heap h) } ; /* Update heap to reflect new value of given item. - * - * See notes on backlink, above. */ -void +Inline void heap_update_item(heap h, p_vector_item p_v) { heap_bubble(h, heap_find_item(h, p_v), p_v) ; diff --git a/lib/qtime.c b/lib/qtime.c index 3e1e8269..413abefd 100644 --- a/lib/qtime.c +++ b/lib/qtime.c @@ -1,4 +1,4 @@ -/* Quagga Realtime Clock handling -- functions +/* Quagga realtime and monotonic clock handling -- functions * Copyright (C) 2009 Chris Hall (GMCH), Highwayman * * This file is part of GNU Zebra. @@ -28,6 +28,11 @@ /*============================================================================== * This is a collection of functions and (in qtime.h) macros and inline * functions which support system time and a monotonic clock. + * + * TODO: introduce mutex for crafted monotonic time, and initialisation + * routine for that: which can preset the various variables... but + * unless is guaranteed to be called, must leave the on-the-fly + * initialisation... could also start a watchdog at that point. */ /*============================================================================== @@ -41,29 +46,54 @@ * is measured in units of sysconf(_SC_CLK_TCK) ticks per second. * * The only tricky bit is that the value returned (of type clock_t) is a - * signed integer, which may wrap round. It is not defined exactly how it - * does this... but it is generally assumed that this_sample - last_sample will - * give the time between the samples. + * signed integer, which can overflow. It is not defined exactly how it + * does this... This code assumes that the system will wrap around in some + * obvious way. The base of the time for this clock may be when the *system* + * started... so when it overflows may depend on how long the system has been + * up... which suggests that some sensible wrap around is likely (?). * * The qtime_t value is in nano-seconds. * * The result from times() is in units of sysconf(_SC_CLK_TCK) ticks per second. * - * NB: it is assumed that qt_craft_monotonic will be called often enough to - * ensure that it is not fooled by the clock wrapping round. + * If clock_t is a signed 32-bit integer, which is kept +ve, then the clock + * overflows/wraps round in 2^31 ticks which is: + * + * at 100 ticks/sec: > 248 days + * at 1,000 ticks/sec: > 24 days + * at 10,000 ticks/sec: > 59 hours + * + * For safety, this asserts that sysconf(_SC_CLK_TCK) <= 1,000,000 for + * sizeof(clock_t) > 4, but <= 1,000 for sizeof(clock_t) == 4. + * + * (It appears that 60, 100, 250 and 1,000 ticks/sec. are popular options.) + * + * If sizeof(clock_t) > 4, it is assumed large enough never to wrap around. + * + * When clock_t is a 32-bit integer must be at least ready for wrap around. + * There are two cases: + * + * * +ve wrap around. new < old value, and new >= 0 + * + * step = (INT32_MAX - old + 1) + new * - * Assuming that clock_t is a signed 32-bit integer, which is kept +ve, - * then the clock wraps round in 2^31 ticks which is: + * * -ve wrap around. new < old value, and new < 0 (and old > 0) * - * at 1,000 ticks/sec: > 24 days ! - * at 1,000,000 ticks/sec: > 35 minutes + * step = (INT32_MAX - old + 1) - (INT32_MIN - new) * - * So this should be a safe assumption -- particularly as 60, 100, 250 and - * 1000 ticks per second appear to be the popular options. + * In any event, a step > 24 hours is taken to means that something has gone + * very, very badly wrong. * - * For safety, this asserts that sysconf(_SC_CLK_TCK) <= 1,000,000. + * NB: it is assumed that qt_craft_monotonic will be called often enough to + * ensure that the check on the step size will not be triggered ! + * + * NB: it is assumed that times() does not simply stick if it overflows. + * + * TODO: Add a watchdog to monitor the behaviour of this clock ? */ +CONFIRM((sizeof(clock_t) >= 4) && (sizeof(clock_t) <= 8)) ; + #ifdef GNU_LINUX #define TIMES_TAKES_NULL 1 #else @@ -71,7 +101,9 @@ #endif static uint64_t monotonic = 0 ; /* monotonic clock in _SC_CLK_TCK's */ -static uint64_t last_times_sample = 0 ; /* last value returned by times() */ +static int64_t last_times_sample = 0 ; /* last value returned by times() */ + +static uint64_t step_limit = 0 ; /* for sanity check */ static int64_t times_clk_tcks = 0 ; /* sysconf(_SC_CLK_TCK) */ static qtime_t times_scale_q = 0 ; /* 10**9 / times_clk_tcks */ @@ -80,7 +112,26 @@ static qtime_t times_scale_r = 0 ; /* 10**9 % times_clk_tcks */ qtime_t qt_craft_monotonic(void) { struct tms dummy ; - uint64_t this_times_sample ; + int64_t this_times_sample ; + uint64_t step ; + + /* Set up times_scale_q & times_scale_q if not yet done. */ + if (times_clk_tcks == 0) /* Is zero until it's initialized */ + { + ldiv_t qr ; + confirm(sizeof(qtime_t) <= sizeof(long int)) ; + + times_clk_tcks = sysconf(_SC_CLK_TCK) ; + passert((times_clk_tcks > 0) && + (times_clk_tcks <= (sizeof(clock_t) > 4) ? 1000000 + : 1000)) ; + + qr = ldiv(QTIME_SECOND, times_clk_tcks) ; + times_scale_q = qr.quot ; + times_scale_r = qr.rem ; + + step_limit = (uint64_t)24 * 60 * 60 * times_clk_tcks ; + } ; /* No errors are defined for times(), but a return of -1 is defined */ /* to indicate an error condition, with errno saying what it is ! */ @@ -94,7 +145,7 @@ qt_craft_monotonic(void) { this_times_sample = times(&dummy) ; #endif - if (this_times_sample == (uint64_t)-1) /* deal with theoretical error */ + if (this_times_sample == -1) /* deal with theoretical error */ { errno = 0 ; this_times_sample = times(&dummy) ; @@ -102,24 +153,37 @@ qt_craft_monotonic(void) { zabort_errno("times() failed") ; } ; - /* Advance the monotonic clock in sysconf(_SC_CLK_TCK) units. */ - monotonic += (this_times_sample - last_times_sample) ; + /* Calculate the step and verify sensible. */ + /* */ + /* Watch out for huge jumps and/or time going backwards. */ + /* For 32-bit clock_t, look out for wrap-around. */ - /* Set up times_scale_q & times_scale_q if not yet done */ - if (times_clk_tcks == 0) /* Is zero until it's initialized */ + if ((sizeof(clock_t) > 4) || (this_times_sample > last_times_sample)) + /* time going backwards will appear as HUGE step forwards. */ + step = (uint64_t)(this_times_sample - last_times_sample) ; + else { - lldiv_t qr ; - confirm(sizeof(qtime_t) <= sizeof(long long int)) ; + if (this_times_sample > 0) + /* both samples +ve => +ve wrap around. */ + step = (uint64_t)( ((int64_t)INT32_MAX - last_times_sample + 1) + + this_times_sample ) ; + else + /* this sample -ve and last sample +ve => -ve wrap round */ + /* this sample -ve and last sample -ve => time gone backwards */ + /* (which appears as a HUGE step forwards). */ + step = (uint64_t)( ((int64_t)INT32_MAX - last_times_sample + 1) + - ((int64_t)INT32_MIN - this_times_sample) ) ; + } ; - times_clk_tcks = sysconf(_SC_CLK_TCK) ; - passert((times_clk_tcks > 0) && (times_clk_tcks <= 1000000)) ; + /* TODO: better error messaging for large clock jumps. */ + if (step > step_limit) + zabort("Sudden large monotonic clock jump") ; - qr = lldiv(QTIME_SECOND, times_clk_tcks) ; - times_scale_q = qr.quot ; - times_scale_r = qr.rem ; + /* Advance the monotonic clock in sysconf(_SC_CLK_TCK) units. */ + monotonic += step ; - last_times_sample = this_times_sample ; - } ; + /* Remember what we got, for next time. */ + last_times_sample = this_times_sample ; /* Scale to qtime_t units. */ if (times_scale_r == 0) diff --git a/lib/qtime.h b/lib/qtime.h index 4cfdd1fb..3f089f53 100644 --- a/lib/qtime.h +++ b/lib/qtime.h @@ -1,4 +1,4 @@ -/* Quagga Realtime Clock handling -- header +/* Quagga realtime and monotonic clock handling -- header * Copyright (C) 2009 Chris Hall (GMCH), Highwayman * * This file is part of GNU Zebra. @@ -47,8 +47,8 @@ * tv_usecs micro-seconds * * Given a 64-bit integer it is much easier to do operations on a 64 bit - * (signed) nano-second value. That gives 34 bits for the seconds count, which - * is > 290 years. + * (signed) nano-second value. That gives > 34 bits for the seconds count, + * and counts from zero to > 290 years. */ typedef int64_t qtime_t ; @@ -92,10 +92,10 @@ qtime2timeval(struct timeval* p_tv, qtime_t qt) ; */ Inline qtime_t -qt_get_realtime(void) ; /* clock_gettime(CLOCK_REALTIME, &ts) */ +qt_get_realtime(void) ; /* clock_gettime(CLOCK_REALTIME, ...) */ Inline qtime_t -qt_get_monotonic(void) ; /* clock_gettime(CLOCK_MONOTONIC, &ts */ +qt_get_monotonic(void) ; /* clock_gettime(CLOCK_MONOTONIC, ...) */ /* OR equivalent using times() */ Inline qtime_t /* monotonic time from CLOCK_REALTIME */ @@ -181,7 +181,8 @@ qtime2timeval(struct timeval* p_tv, qtime_t qt) /* Read given clock & return a qtime_t value. * - * Crunch, zabbort_errno, if fails: cannot continue with broken time value ! + * While possibility of error is essentially theoretical, must treat it as a + * FATAL error -- cannot continue with broken time value ! */ Inline qtime_t @@ -205,9 +206,10 @@ qt_get_timeofday(void) return timeval2qtime(&tv) ; } -/* clock_gettime(CLOCK_REALTIME, &ts) -- returning qtime_t value +/* clock_gettime(CLOCK_REALTIME, ...) -- returning qtime_t value * - * Crunch, zabbort_errno, if fails: cannot continue with broken time value ! + * While possibility of error is essentially theoretical, must treat it as a + * FATAL error -- cannot continue with broken time value ! */ Inline qtime_t qt_get_realtime(void) @@ -215,10 +217,11 @@ qt_get_realtime(void) return qt_clock_gettime(CLOCK_REALTIME) ; } ; -/* clock_gettime(CLOCK_MONOTONIC, &ts) OR qt_craft_monotonic() +/* clock_gettime(CLOCK_MONOTONIC, ...) OR qt_craft_monotonic() * -- returning qtime_t value * - * Crunch, zabbort_errno, if fails: cannot continue with broken time value ! + * While possibility of error is essentially theoretical, must treat it as a + * FATAL error -- cannot continue with broken time value ! */ Inline qtime_t qt_get_monotonic(void) @@ -232,7 +235,6 @@ qt_get_monotonic(void) /*============================================================================== * Conversion between realtime/timeofday and monotonic - * */ /* Convert a CLOCK_REALTIME time to our local monotonic time. */ diff --git a/lib/qtimers.c b/lib/qtimers.c index 6d3932fc..f4959983 100644 --- a/lib/qtimers.c +++ b/lib/qtimers.c @@ -44,8 +44,8 @@ * Timers are triggered by calling qtimer_dispatch_next(). This is given the * current qtimer time (see below), and it dispatches the first timer whose * time has come (or been passed). Dispatching a timer means calling its - * action function (see below). Each call of qtimer_dispatch_next triggers at - * most one timer. + * action function (see below). Each call of qtimer_dispatch_next() triggers + * at most one timer. * * Time Base * --------- @@ -65,7 +65,8 @@ * timer (which may, or may not, be the current qtimer time). * * During an action function timers may be set/unset, actions changed, and so - * on... there are no restrictions. + * on... there are no restrictions EXCEPT that the qtimer structure may NOT be + * freed. */ static int @@ -92,7 +93,7 @@ qtimer_pile_init_new(qtimer_pile qtp) if (qtp == NULL) qtp = XCALLOC(MTYPE_QTIMER_PILE, sizeof(struct qtimer_pile)) ; else - memset(qtp, 0, sizeof(struct qtimer_pile)) ; + memset(qtp, 0, sizeof(struct qtimer_pile)) ; /* Zeroising has initialised: * @@ -109,6 +110,23 @@ qtimer_pile_init_new(qtimer_pile qtp) return qtp ; } ; +/* Get the timer time for the first timer due to go off in the given pile. + * + * The caller must provide a maximum acceptable time. If the qtimer pile is + * empty, or the top entry times out after the maximum time, then the maximum + * is returned. + */ +qtime_t +qtimer_pile_top_time(qtimer_pile qtp, qtime_t max_time) +{ + qtimer qtr = heap_top_item(&qtp->timers) ; + + if ((qtr == NULL) || (qtr->time >= max_time)) + return max_time ; + else + return qtr->time ; +} ; + /* Dispatch the next timer whose time is <= the given "upto" time. * * The upto time must be a qtimer time (!) -- see qtimer_time_now(). @@ -124,18 +142,15 @@ qtimer_pile_dispatch_next(qtimer_pile qtp, qtime_t upto) { qtimer qtr ; - if (qtp->unset_pending != NULL) - qtimer_unset(qtp->unset_pending) ; /* just in case recurse through here */ - qtr = heap_top_item(&qtp->timers) ; if ((qtr != NULL) && (qtr->time <= upto)) { - qtp->unset_pending = qtr ; /* delay unset of top item, pro tem...*/ + qtr->state = qtr_state_unset_pending ; qtr->action(qtr, qtr->timer_info, upto) ; - if (qtp->unset_pending != NULL) /* ...now must unset if not yet done */ - qtimer_unset(qtp->unset_pending) ; + if (qtr->state == qtr_state_unset_pending) + qtimer_unset(qtr) ; return 1 ; } @@ -147,9 +162,12 @@ qtimer_pile_dispatch_next(qtimer_pile qtp, qtime_t upto) * * If pile is empty, release the qtimer_pile structure, if required. * + * See: #define qtimer_pile_ream_free(qtp) + * #define qtimer_pile_ream_keep(qtp) + * * Useful for emptying out and discarding a pile of timers: * - * while ((p_qtr = qtimer_pile_ream(qtp, 1))) + * while ((p_qtr = qtimer_pile_ream_free(qtp))) * ... do what's required to release the item p_qtr * * Returns NULL when timer pile is empty (and has been released, if required). @@ -166,15 +184,10 @@ qtimer_pile_ream(qtimer_pile qtp, int free_structure) qtr = heap_ream_keep(&qtp->timers) ; /* ream, keeping the heap structure */ if (qtr != NULL) - qtr->active = 0 ; /* already removed from pile */ + qtr->state = qtr_state_inactive ; /* has been removed from pile */ else - { - if (free_structure) - XFREE(MTYPE_QTIMER_PILE, qtp) ; - else - qtp->unset_pending = NULL ; /* heap is empty, so this is last thing */ - /* to be tidied up. */ - } ; + if (free_structure) /* pile is empty, may now free it */ + XFREE(MTYPE_QTIMER_PILE, qtp) ; return qtr ; } ; @@ -186,7 +199,7 @@ qtimer_pile_ream(qtimer_pile qtp, int free_structure) /* Initialise qtimer structure -- allocating one if required. * * Associates qtimer with the given pile of timers, and sets up the action and - * the timer_info ready for use. + * the timer_info. * * Once initialised, the timer may be set. * @@ -199,20 +212,22 @@ qtimer_init_new(qtimer qtr, qtimer_pile qtp, if (qtr == NULL) qtr = XCALLOC(MTYPE_QTIMER, sizeof(struct qtimer)) ; else - memset(qtr, 0, sizeof(struct qtimer)) ; + memset(qtr, 0, sizeof(struct qtimer)) ; /* Zeroising has initialised: * * pile -- NULL -- not in any pile (yet) * backlink -- unset * - * active -- not active + * state -- not active * * time -- unset * action -- NULL -- no action set (yet) * timer_info -- NULL -- no timer info set (yet) */ + confirm(qtr_state_inactive == 0) ; + qtr->pile = qtp ; qtr->action = action ; qtr->timer_info = timer_info ; @@ -223,11 +238,15 @@ qtimer_init_new(qtimer qtr, qtimer_pile qtp, /* Free given timer. * * Unsets it first if it is active. + * + * The timer MAY NOT be currently the subject of qtimer_pile_dispatch_next(). */ void qtimer_free(qtimer qtr) { - if (qtr->active) + assert(qtr->state != qtr_state_unset_pending) ; + + if (qtr->state != qtr_state_inactive) qtimer_unset(qtr) ; XFREE(MTYPE_QTIMER, qtr) ; @@ -241,7 +260,7 @@ qtimer_free(qtimer qtr) void qtimer_set_pile(qtimer qtr, qtimer_pile qtp) { - if ((qtr->active) && (qtr->pile != qtp)) + if (qtr_is_active(qtr) && (qtr->pile != qtp)) qtimer_unset(qtr) ; qtr->pile = qtp ; } @@ -266,12 +285,17 @@ qtimer_set_info(qtimer qtr, void* timer_info) * * Setting a -ve time => qtimer_unset. * + * Sets any given action -- if the action given is NULL, retains previously set + * action. + * * If the timer is already active, sets the new time & updates pile. * * Otherwise, sets the time and adds to pile -- making timer active. + * + * It is an error to set a timer which has a NULL action. */ void -qtimer_set(qtimer qtr, qtime_t when) +qtimer_set(qtimer qtr, qtime_t when, qtimer_action* action) { qtimer_pile qtp ; @@ -283,17 +307,17 @@ qtimer_set(qtimer qtr, qtime_t when) qtr->time = when ; - if (qtr->active) - { - heap_update_item(&qtp->timers, qtr) ; /* update in heap */ - if (qtr == qtp->unset_pending) - qtp->unset_pending = NULL ; /* dealt with. */ - } + if (qtr_is_active(qtr)) + heap_update_item(&qtp->timers, qtr) ; /* update in heap */ else - { - heap_push_item(&qtp->timers, qtr) ; /* add to heap */ - qtr->active = 1 ; - } ; + heap_push_item(&qtp->timers, qtr) ; /* add to heap */ + + qtr->state = qtr_state_active ; /* overrides any unset pending */ + + if (action != NULL) + qtr->action = action ; + else + dassert(qtr->action != NULL) ; } ; /* Unset given timer @@ -303,15 +327,13 @@ qtimer_set(qtimer qtr, qtime_t when) void qtimer_unset(qtimer qtr) { - if (qtr->active) + if (qtr_is_active(qtr)) { qtimer_pile qtp = qtr->pile ; dassert(qtp != NULL) ; heap_delete_item(&qtp->timers, qtr) ; - if (qtr == qtp->unset_pending) - qtp->unset_pending = NULL ; - qtr->active = 0 ; + qtr->state = qtr_state_inactive ; /* overrides any unset pending */ } ; } ; diff --git a/lib/qtimers.h b/lib/qtimers.h index 65154a7a..37f55d89 100644 --- a/lib/qtimers.h +++ b/lib/qtimers.h @@ -46,12 +46,22 @@ typedef struct qtimer_pile* qtimer_pile ; typedef void (qtimer_action)(qtimer qtr, void* timer_info, qtime_t when) ; +enum qtimer_state { + qtr_state_inactive = 0, + qtr_state_active = 1, /* timer is active in its pile */ + qtr_state_unset_pending = 3 /* timer is active, but unset is pending */ +} ; + +#define qtr_is_active(qtr) ((qtr)->state != qtr_state_inactive) + +typedef enum qtimer_state qtimer_state_t ; + struct qtimer { qtimer_pile pile ; heap_backlink_t backlink ; - int active ; /* timer is active in the current pile. */ + qtimer_state_t state ; qtime_t time ; qtimer_action* action ; @@ -61,8 +71,6 @@ struct qtimer struct qtimer_pile { struct heap timers ; - - qtimer unset_pending ; } ; /*============================================================================== @@ -75,9 +83,17 @@ qtimer_pile_init_new(qtimer_pile qtp) ; int qtimer_pile_dispatch_next(qtimer_pile qtp, qtime_t upto) ; +qtime_t +qtimer_pile_top_time(qtimer_pile qtp, qtime_t max_time) ; + qtimer qtimer_pile_ream(qtimer_pile qtp, int free_structure) ; +/* Ream out qtimer pile and free the qtimer structure. */ +#define qtimer_pile_ream_free(qtp) qtimer_pile_ream(qtp, 1) +/* Ream out qtimer pile but keep the qtimer structure. */ +#define qtimer_pile_ream_keep(qtp) qtimer_pile_ream(qtp, 0) + Inline qtime_t qtimer_time_now() ; @@ -106,13 +122,13 @@ void qtimer_free(qtimer qtr) ; void -qtimer_set(qtimer qtr, qtime_t when) ; +qtimer_set(qtimer qtr, qtime_t when, qtimer_action* action) ; void qtimer_unset(qtimer qtr) ; Inline void -qtimer_add(qtimer qtr, qtime_t interval) ; +qtimer_add(qtimer qtr, qtime_t interval, qtimer_action* action) ; Inline qtime_t qtimer_get(qtimer qtr) ; @@ -156,9 +172,9 @@ qtimer_time_from_timeofday(qtime_t timeofday) /* Set given timer to given time later than *its* current time. */ Inline void -qtimer_add(qtimer qtr, qtime_t interval) +qtimer_add(qtimer qtr, qtime_t interval, qtimer_action* action) { - qtimer_set(qtr, qtimer_get(qtr) + interval); + qtimer_set(qtr, qtimer_get(qtr) + interval, action); } ; /* Get the given timer's time. |