diff options
Diffstat (limited to 'erts/emulator/beam/time.c')
-rw-r--r-- | erts/emulator/beam/time.c | 477 |
1 files changed, 293 insertions, 184 deletions
diff --git a/erts/emulator/beam/time.c b/erts/emulator/beam/time.c index 2fd8e0cf00..c9f8b68bca 100644 --- a/erts/emulator/beam/time.c +++ b/erts/emulator/beam/time.c @@ -83,6 +83,10 @@ #define ASSERT_NO_LOCKED_LOCKS #endif +#define ERTS_MONOTONIC_DAY ERTS_SEC_TO_MONOTONIC(60*60*24) +#define ERTS_CLKTCKS_DAY ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY) + +static erts_smp_atomic32_t is_bumping; static erts_smp_mtx_t tiw_lock; @@ -91,18 +95,20 @@ static erts_smp_mtx_t tiw_lock; ** The individual timer cells in tiw are also protected by the same mutex. */ +/* timing wheel size NEED to be a power of 2 */ #ifdef SMALL_MEMORY -#define TIW_SIZE 8192 +#define TIW_SIZE (1 << 13) #else -#define TIW_SIZE 65536 /* timing wheel size (should be a power of 2) */ +#define TIW_SIZE (1 << 20) #endif static ErlTimer** tiw; /* the timing wheel, allocated in init_time() */ -static Uint tiw_pos; /* current position in wheel */ +static ErtsMonotonicTime tiw_pos; /* current position in wheel */ static Uint tiw_nto; /* number of timeouts in wheel */ -static Uint tiw_min; -static ErlTimer *tiw_min_ptr; - -/* END tiw_lock protected variables */ +static struct { + ErlTimer *head; + ErlTimer **tail; + Uint nto; +} tiw_at_once; /* Actual interval time chosen by sys_init_time() */ @@ -114,77 +120,97 @@ static int tiw_itime; /* Constant after init */ # define TIW_ITIME tiw_itime #endif -erts_smp_atomic32_t do_time; /* set at clock interrupt */ -static ERTS_INLINE erts_short_time_t do_time_read(void) -{ - return erts_smp_atomic32_read_acqb(&do_time); -} +static int true_next_timeout_time; +static ErtsMonotonicTime next_timeout_time; +erts_atomic64_t erts_next_timeout__; -static ERTS_INLINE erts_short_time_t do_time_update(void) +static ERTS_INLINE void +init_next_timeout(ErtsMonotonicTime time) { - return do_time_read(); + erts_atomic64_init_nob(&erts_next_timeout__, + (erts_aint64_t) time); } -static ERTS_INLINE void do_time_init(void) +static ERTS_INLINE void +set_next_timeout(ErtsMonotonicTime time, int true_timeout) { - erts_smp_atomic32_init_nob(&do_time, 0); + true_next_timeout_time = true_timeout; + next_timeout_time = time; + erts_atomic64_set_relb(&erts_next_timeout__, + (erts_aint64_t) time); } /* get the time (in units of TIW_ITIME) to the next timeout, or -1 if there are no timeouts */ -static erts_short_time_t next_time_internal(void) /* PRE: tiw_lock taken by caller */ +static ERTS_INLINE ErtsMonotonicTime +find_next_timeout(ErtsMonotonicTime curr_time, + ErtsMonotonicTime max_search_time) { - int i, tm, nto; - Uint32 min; - ErlTimer* p; - erts_short_time_t dt; - - if (tiw_nto == 0) - return -1; /* no timeouts in wheel */ + int start_ix, tiw_pos_ix; + ErlTimer *p; + int true_min_timeout; + ErtsMonotonicTime min_timeout, min_timeout_pos, slot_timeout_pos, timeout_limit; - if (tiw_min_ptr) { - min = tiw_min; - dt = do_time_read(); - return ((min >= dt) ? (min - dt) : 0); + ERTS_SMP_LC_ASSERT(erts_smp_lc_mtx_is_locked(&tiw_lock)); + + if (true_next_timeout_time) + return next_timeout_time; + + /* We never set next timeout beyond timeout_limit */ + timeout_limit = curr_time + ERTS_MONOTONIC_DAY; + + if (tiw_nto == 0) { /* no timeouts in wheel */ + true_min_timeout = true_next_timeout_time = 0; + min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(timeout_limit); + goto found_next; } - - /* start going through wheel to find next timeout */ - tm = nto = 0; - min = (Uint32) -1; /* max Uint32 */ - i = tiw_pos; + + /* + * Don't want others entering trying to bump + * timers while we are checking... + */ + set_next_timeout(timeout_limit, 0); + + true_min_timeout = 1; + slot_timeout_pos = tiw_pos; + min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time + max_search_time); + + start_ix = tiw_pos_ix = (int) (tiw_pos & (TIW_SIZE-1)); + do { - p = tiw[i]; - while (p != NULL) { - nto++; - if (p->count == 0) { - /* found next timeout */ - dt = do_time_read(); - /* p->count is zero */ - tiw_min_ptr = p; - tiw_min = tm; - return ((tm >= dt) ? (tm - dt) : 0); - } else { - /* keep shortest time in 'min' */ - if (tm + p->count*TIW_SIZE < min) { - min = tm + p->count*TIW_SIZE; - tiw_min_ptr = p; - tiw_min = min; - } + slot_timeout_pos++; + if (slot_timeout_pos >= min_timeout_pos) { + true_min_timeout = 0; + break; + } + + p = tiw[tiw_pos_ix]; + + while (p) { + ErtsMonotonicTime timeout_pos; + ASSERT(p != p->next); + timeout_pos = p->timeout_pos; + if (min_timeout_pos > timeout_pos) { + min_timeout_pos = timeout_pos; + if (min_timeout_pos <= slot_timeout_pos) + goto found_next; } p = p->next; } - /* when we have found all timeouts the shortest time will be in min */ - if (nto == tiw_nto) break; - tm++; - i = (i + 1) % TIW_SIZE; - } while (i != tiw_pos); - dt = do_time_read(); - if (min <= (Uint32) dt) - return 0; - if ((min - (Uint32) dt) > (Uint32) ERTS_SHORT_TIME_T_MAX) - return ERTS_SHORT_TIME_T_MAX; - return (erts_short_time_t) (min - (Uint32) dt); + + tiw_pos_ix++; + if (tiw_pos_ix == TIW_SIZE) + tiw_pos_ix = 0; + } while (start_ix != tiw_pos_ix); + +found_next: + + min_timeout = ERTS_CLKTCKS_TO_MONOTONIC(min_timeout_pos); + if (min_timeout != next_timeout_time) + set_next_timeout(min_timeout, true_min_timeout); + + return min_timeout; } static void remove_timer(ErlTimer *p) { @@ -212,72 +238,153 @@ static void remove_timer(ErlTimer *p) { tiw_nto--; } -/* Private export to erl_time_sup.c */ -erts_short_time_t erts_next_time(void) +ErtsMonotonicTime +erts_check_next_timeout_time(ErtsMonotonicTime max_search_time) { - erts_short_time_t ret; + ErtsMonotonicTime next, curr; + + curr = erts_get_monotonic_time(); erts_smp_mtx_lock(&tiw_lock); - (void)do_time_update(); - ret = next_time_internal(); + + next = find_next_timeout(curr, max_search_time); + erts_smp_mtx_unlock(&tiw_lock); - return ret; + + return next; } -static ERTS_INLINE void bump_timer_internal(erts_short_time_t dt) /* PRE: tiw_lock is write-locked */ +#ifndef DEBUG +#define ERTS_DBG_CHK_SAFE_TO_SKIP_TO(TO) ((void) 0) +#else +#define ERTS_DBG_CHK_SAFE_TO_SKIP_TO(TO) debug_check_safe_to_skip_to((TO)) +static void +debug_check_safe_to_skip_to(ErtsMonotonicTime skip_to_pos) { - Uint keep_pos; - Uint count; - ErlTimer *p, **prev, *timeout_head, **timeout_tail; - Uint dtime = (Uint) dt; + int slots, ix; + ErlTimer *tmr; + ErtsMonotonicTime tmp; + + ix = (int) (tiw_pos & (TIW_SIZE-1)); + tmp = skip_to_pos - tiw_pos; + ASSERT(tmp >= 0); + if (tmp < (ErtsMonotonicTime) TIW_SIZE) + slots = (int) tmp; + else + slots = TIW_SIZE; + + while (slots > 0) { + tmr = tiw[ix]; + while (tmr) { + ASSERT(tmr->timeout_pos > skip_to_pos); + tmr = tmr->next; + } + ix++; + if (ix == TIW_SIZE) + ix = 0; + slots--; + } +} +#endif + +void erts_bump_timers(ErtsMonotonicTime curr_time) +{ + int tiw_pos_ix, slots; + ErlTimer *p, *timeout_head, **timeout_tail; + ErtsMonotonicTime bump_to, tmp_slots; + + if (erts_smp_atomic32_cmpxchg_nob(&is_bumping, 1, 0) != 0) + return; /* Another thread is currently bumping... */ + + bump_to = ERTS_MONOTONIC_TO_CLKTCKS(curr_time); + + erts_smp_mtx_lock(&tiw_lock); + + if (tiw_pos >= bump_to) { + timeout_head = NULL; + goto done; + } + + /* Don't want others here while we are bumping... */ + set_next_timeout(curr_time + ERTS_MONOTONIC_DAY, 0); + + if (!tiw_at_once.head) { + timeout_head = NULL; + timeout_tail = &timeout_head; + } + else { + ASSERT(tiw_nto >= tiw_at_once.nto); + timeout_head = tiw_at_once.head; + timeout_tail = tiw_at_once.tail; + tiw_nto -= tiw_at_once.nto; + tiw_at_once.head = NULL; + tiw_at_once.tail = &tiw_at_once.head; + tiw_at_once.nto = 0; + } - /* no need to bump the position if there aren't any timeouts */ if (tiw_nto == 0) { - erts_smp_mtx_unlock(&tiw_lock); - return; + ERTS_DBG_CHK_SAFE_TO_SKIP_TO(bump_to); + tiw_pos = bump_to; + goto done; } - /* if do_time > TIW_SIZE we want to go around just once */ - count = (Uint)(dtime / TIW_SIZE) + 1; - keep_pos = (tiw_pos + dtime) % TIW_SIZE; - if (dtime > TIW_SIZE) dtime = TIW_SIZE; - - timeout_head = NULL; - timeout_tail = &timeout_head; - while (dtime > 0) { - /* this is to decrease the counters with the right amount */ - /* when dtime >= TIW_SIZE */ - if (tiw_pos == keep_pos) count--; - prev = &tiw[tiw_pos]; - while ((p = *prev) != NULL) { - ASSERT( p != p->next); - if (p->count < count) { /* we have a timeout */ - /* remove min time */ - if (tiw_min_ptr == p) { - tiw_min_ptr = NULL; - tiw_min = 0; - } + if (true_next_timeout_time) { + ErtsMonotonicTime skip_until_pos; + /* + * No need inspecting slots where we know no timeouts + * to trigger should reside. + */ + skip_until_pos = ERTS_MONOTONIC_TO_CLKTCKS(next_timeout_time); + if (skip_until_pos > bump_to) + skip_until_pos = bump_to; + + ERTS_DBG_CHK_SAFE_TO_SKIP_TO(skip_until_pos); + ASSERT(skip_until_pos > tiw_pos); + + tiw_pos = skip_until_pos - 1; + } + + tiw_pos_ix = (int) ((tiw_pos+1) & (TIW_SIZE-1)); + tmp_slots = (bump_to - tiw_pos); + if (tmp_slots < (ErtsMonotonicTime) TIW_SIZE) + slots = (int) tmp_slots; + else + slots = TIW_SIZE; + + while (slots > 0) { + p = tiw[tiw_pos_ix]; + while (p) { + ErlTimer *next = p->next; + ASSERT(p != next); + if (p->timeout_pos <= bump_to) { /* we have a timeout */ /* Remove from list */ remove_timer(p); *timeout_tail = p; /* Insert in timeout queue */ timeout_tail = &p->next; } - else { - /* no timeout, just decrease counter */ - p->count -= count; - prev = &p->next; - } + p = next; } - tiw_pos = (tiw_pos + 1) % TIW_SIZE; - dtime--; + tiw_pos_ix++; + if (tiw_pos_ix == TIW_SIZE) + tiw_pos_ix = 0; + slots--; } - tiw_pos = keep_pos; - if (tiw_min_ptr) - tiw_min -= dt; - + + ASSERT(tmp_slots >= (ErtsMonotonicTime) TIW_SIZE + || tiw_pos_ix == (int) ((bump_to+1) & (TIW_SIZE-1))); + + tiw_pos = bump_to; + + /* Search at most two seconds ahead... */ + (void) find_next_timeout(curr_time, ERTS_SEC_TO_MONOTONIC(2)); + +done: + erts_smp_mtx_unlock(&tiw_lock); + erts_smp_atomic32_set_nob(&is_bumping, 0); + /* Call timedout timers callbacks */ while (timeout_head) { p = timeout_head; @@ -288,6 +395,7 @@ static ERTS_INLINE void bump_timer_internal(erts_short_time_t dt) /* PRE: tiw_lo * accesses any field until the ->timeout * callback is called. */ + ASSERT(p->timeout_pos <= bump_to); p->next = NULL; p->prev = NULL; p->slot = 0; @@ -295,12 +403,6 @@ static ERTS_INLINE void bump_timer_internal(erts_short_time_t dt) /* PRE: tiw_lo } } -void erts_bump_timer(erts_short_time_t dt) /* dt is value from do_time */ -{ - erts_smp_mtx_lock(&tiw_lock); - bump_timer_internal(dt); -} - Uint erts_timer_wheel_memory_size(void) { @@ -310,13 +412,14 @@ erts_timer_wheel_memory_size(void) /* this routine links the time cells into a free list at the start and sets the time queue as empty */ void -erts_init_time(void) +erts_init_time(int time_correction, ErtsTimeWarpMode time_warp_mode) { + ErtsMonotonicTime mtime; int i, itime; /* system dependent init; must be done before do_time_init() if timer thread is enabled */ - itime = erts_init_time_sup(); + itime = erts_init_time_sup(time_correction, time_warp_mode); #ifdef TIW_ITIME_IS_CONSTANT if (itime != TIW_ITIME) { erl_exit(ERTS_ABORT_EXIT, "timer resolution mismatch %d != %d", itime, TIW_ITIME); @@ -325,16 +428,23 @@ erts_init_time(void) tiw_itime = itime; #endif + erts_smp_atomic32_init_nob(&is_bumping, 0); erts_smp_mtx_init(&tiw_lock, "timer_wheel"); tiw = (ErlTimer**) erts_alloc(ERTS_ALC_T_TIMER_WHEEL, TIW_SIZE * sizeof(ErlTimer*)); for(i = 0; i < TIW_SIZE; i++) tiw[i] = NULL; - do_time_init(); - tiw_pos = tiw_nto = 0; - tiw_min_ptr = NULL; - tiw_min = 0; + + mtime = erts_get_monotonic_time(); + tiw_pos = ERTS_MONOTONIC_TO_CLKTCKS(mtime); + tiw_nto = 0; + tiw_at_once.head = NULL; + tiw_at_once.tail = &tiw_at_once.head; + tiw_at_once.nto = 0; + init_next_timeout(mtime + ERTS_MONOTONIC_DAY); + + erts_late_init_time_sup(); } @@ -343,58 +453,62 @@ erts_init_time(void) /* ** Insert a process into the time queue, with a timeout 't' */ -static void -insert_timer(ErlTimer* p, Uint t) +static ErtsMonotonicTime +insert_timer(ErlTimer* p, ErtsMonotonicTime curr_time, ErtsMonotonicTime to) { - Uint tm; - Uint64 ticks; + ErtsMonotonicTime timeout_time, timeout_pos; - /* The current slot (tiw_pos) in timing wheel is the next slot to be - * be processed. Hence no extra time tick is needed. - * - * (x + y - 1)/y is precisely the "number of bins" formula. - */ - ticks = (t + (TIW_ITIME - 1)) / TIW_ITIME; + if (to == 0) { + timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time); + tiw_nto++; + tiw_at_once.nto++; + *tiw_at_once.tail = p; + p->next = NULL; + p->timeout_pos = timeout_pos; + timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos); + } + else { + int tm; + ErtsMonotonicTime ticks; - /* - * Ticks must be a Uint64, or the addition may overflow here, - * resulting in an incorrect value for p->count below. - */ - ticks += do_time_update(); /* Add backlog of unprocessed time */ - - /* calculate slot */ - tm = (ticks + tiw_pos) % TIW_SIZE; - p->slot = (Uint) tm; - p->count = (Uint) (ticks / TIW_SIZE); + ticks = ERTS_MSEC_TO_CLKTCKS(to); + timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time - 1) + 1 + ticks; + + /* calculate slot */ + tm = (int) (timeout_pos & (TIW_SIZE-1)); + p->slot = (Uint) tm; - /* insert at head of list at slot */ - p->next = tiw[tm]; - p->prev = NULL; - if (p->next != NULL) - p->next->prev = p; - tiw[tm] = p; + /* insert at head of list at slot */ + p->next = tiw[tm]; + p->prev = NULL; + if (p->next != NULL) + p->next->prev = p; + tiw[tm] = p; + tiw_nto++; - /* insert min time */ - if ((tiw_nto == 0) || ((tiw_min_ptr != NULL) && (ticks < tiw_min))) { - tiw_min = ticks; - tiw_min_ptr = p; - } - if ((tiw_min_ptr == p) && (ticks > tiw_min)) { - /* some other timer might be 'min' now */ - tiw_min = 0; - tiw_min_ptr = NULL; + timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos); + p->timeout_pos = timeout_pos; + + ASSERT(ERTS_MSEC_TO_MONOTONIC(to) <= timeout_time - curr_time); + ASSERT(timeout_time - curr_time + < ERTS_MSEC_TO_MONOTONIC(to) + ERTS_CLKTCKS_TO_MONOTONIC(1)); } - tiw_nto++; + if (timeout_time < next_timeout_time) + set_next_timeout(timeout_time, 1); + + return timeout_time; } void erts_set_timer(ErlTimer* p, ErlTimeoutProc timeout, ErlCancelProc cancel, void* arg, Uint t) { - - erts_deliver_time(); +#ifdef ERTS_SMP + ErtsMonotonicTime timeout_time; +#endif + ErtsMonotonicTime current_time = erts_get_monotonic_time(); erts_smp_mtx_lock(&tiw_lock); if (p->active) { /* XXX assert ? */ erts_smp_mtx_unlock(&tiw_lock); @@ -404,11 +518,15 @@ erts_set_timer(ErlTimer* p, ErlTimeoutProc timeout, ErlCancelProc cancel, p->cancel = cancel; p->arg = arg; p->active = 1; - insert_timer(p, t); +#ifdef ERTS_SMP + timeout_time = +#else + (void) +#endif + insert_timer(p, current_time, (ErtsMonotonicTime) t); erts_smp_mtx_unlock(&tiw_lock); #if defined(ERTS_SMP) - if (t <= (Uint) ERTS_SHORT_TIME_T_MAX) - erts_sys_schedule_interrupt_timed(1, (erts_short_time_t) t); + erts_sys_schedule_interrupt_timed(1, timeout_time); #endif } @@ -421,14 +539,8 @@ erts_cancel_timer(ErlTimer* p) return; } - /* is it the 'min' timer, remove min */ - if (p == tiw_min_ptr) { - tiw_min_ptr = NULL; - tiw_min = 0; - } - remove_timer(p); - p->slot = p->count = 0; + p->slot = 0; if (p->cancel != NULL) { erts_smp_mtx_unlock(&tiw_lock); @@ -447,8 +559,7 @@ erts_cancel_timer(ErlTimer* p) Uint erts_time_left(ErlTimer *p) { - Uint left; - erts_short_time_t dt; + ErtsMonotonicTime current_time, timeout_time; erts_smp_mtx_lock(&tiw_lock); @@ -457,45 +568,43 @@ erts_time_left(ErlTimer *p) return 0; } - if (p->slot < tiw_pos) - left = (p->count + 1) * TIW_SIZE + p->slot - tiw_pos; - else - left = p->count * TIW_SIZE + p->slot - tiw_pos; - dt = do_time_read(); - if (left < dt) - left = 0; - else - left -= dt; + timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos); erts_smp_mtx_unlock(&tiw_lock); - return (Uint) left * TIW_ITIME; + current_time = erts_get_monotonic_time(); + if (timeout_time <= current_time) + return 0; + return (Uint) ERTS_MONOTONIC_TO_MSEC(timeout_time - current_time); } #ifdef DEBUG void erts_p_slpq(void) { + ErtsMonotonicTime current_time = erts_get_monotonic_time(); int i; ErlTimer* p; erts_smp_mtx_lock(&tiw_lock); /* print the whole wheel, starting at the current position */ - erts_printf("\ntiw_pos = %d tiw_nto %d\n", tiw_pos, tiw_nto); + erts_printf("\ncurrent time = %bps tiw_pos = %d tiw_nto %d\n", + current_time, tiw_pos, tiw_nto); i = tiw_pos; if (tiw[i] != NULL) { erts_printf("%d:\n", i); for(p = tiw[i]; p != NULL; p = p->next) { - erts_printf(" (count %d, slot %d)\n", - p->count, p->slot); + erts_printf(" (timeout time %bps, slot %d)\n", + ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos), + p->slot); } } - for(i = (i+1)%TIW_SIZE; i != tiw_pos; i = (i+1)%TIW_SIZE) { + for(i = ((i+1) & (TIW_SIZE-1)); i != (tiw_pos & (TIW_SIZE-1)); i = ((i+1) & (TIW_SIZE-1))) { if (tiw[i] != NULL) { erts_printf("%d:\n", i); for(p = tiw[i]; p != NULL; p = p->next) { - erts_printf(" (count %d, slot %d)\n", - p->count, p->slot); + erts_printf(" (timeout time %bps, slot %d)\n", + ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos), p->slot); } } } |