diff options
| -rw-r--r-- | erts/emulator/beam/time.c | 499 | ||||
| -rw-r--r-- | erts/etc/unix/etp-commands.in | 75 |
2 files changed, 390 insertions, 184 deletions
diff --git a/erts/emulator/beam/time.c b/erts/emulator/beam/time.c index 16e4328a05..f530ee5de0 100644 --- a/erts/emulator/beam/time.c +++ b/erts/emulator/beam/time.c @@ -141,20 +141,24 @@ * * In order to limit the amount of work needed in order to find * next timeout, we keep track of total amount of timers in the - * wheels, total amount of timers in soon wheel, and the total - * amount of timers in each range of slots. Each slot range - * currently contain 512 slots. + * wheels, total amount of timers in the later wheel, total amount + * of timers in soon wheel, and the total amount of timers in + * each range of slots. Each slot range currently contain 512 + * slots. * - * When next timeout is less than half the soon wheel width away - * we determine the exact timeout. Due to the timer counts of + * When next timeout is less than the soon wheel width away we + * determine the exact timeout. Due to the timer counts of * slot ranges, we currently at most need to search 1024 slots * in the soon wheel. This besides inspecting slot range counts * and two slots in the later wheel which potentially might trigger * timeouts for moving timers from the later wheel to the soon wheel - * earlier than timeouts in the soon wheel. + * earlier than timeouts in the soon wheel. We also keep track + * of latest known minimum timeout position in each wheel which + * makes it possible to avoid scanning from current position + * each time. * - * When next timeout is further away than half the soon wheel - * width we settle for the earliest possible timeout in the first + * When next timeout is further away than the soon wheel width + * we settle for the earliest possible timeout in the first * non-empty slot range. The further away the next timeout is, the * more likely it is that the next timeout change before we * actually get there. That is, a change due to another timer is @@ -176,8 +180,11 @@ #define ERTS_WANT_TIMER_WHEEL_API #include "erl_time.h" -#define ERTS_MONOTONIC_WEEK ERTS_SEC_TO_MONOTONIC(7*60*60*24) -#define ERTS_CLKTCKS_WEEK ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_WEEK) +#define ERTS_MAX_CLKTCKS \ + ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_TIME_MAX) + +#define ERTS_CLKTCKS_WEEK \ + ERTS_MONOTONIC_TO_CLKTCKS(ERTS_SEC_TO_MONOTONIC(7*60*60*24)) #ifdef ERTS_ENABLE_LOCK_CHECK #define ASSERT_NO_LOCKED_LOCKS erts_lc_check_exact(NULL, 0) @@ -265,10 +272,21 @@ static int tiw_itime; /* Constant after init */ # define TIW_ITIME tiw_itime #endif +const int etp_tw_soon_wheel_size = ERTS_TW_SOON_WHEEL_SIZE; +const ErtsMonotonicTime etp_tw_soon_wheel_mask = ERTS_TW_SOON_WHEEL_MASK; +const int etp_tw_soon_wheel_first_slot = ERTS_TW_SOON_WHEEL_FIRST_SLOT; + +const int etp_tw_later_wheel_size = ERTS_TW_LATER_WHEEL_SIZE; +const ErtsMonotonicTime etp_tw_later_wheel_slot_size = ERTS_TW_LATER_WHEEL_SLOT_SIZE; +const int etp_tw_later_wheel_shift = ERTS_TW_LATER_WHEEL_SHIFT; +const ErtsMonotonicTime etp_tw_later_wheel_mask = ERTS_TW_LATER_WHEEL_MASK; +const ErtsMonotonicTime etp_tw_later_wheel_pos_mask = ERTS_TW_LATER_WHEEL_POS_MASK; +const int etp_tw_later_wheel_first_slot = ERTS_TW_LATER_WHEEL_FIRST_SLOT; + struct ErtsTimerWheel_ { ErtsTWheelTimer *slots[1 /* At Once Slot */ + ERTS_TW_SOON_WHEEL_SIZE /* Soon Wheel Slots */ - + ERTS_TW_LATER_WHEEL_SIZE]; /* Later Wheel Slots */ + + ERTS_TW_LATER_WHEEL_SIZE]; /* Later Wheel Slots */ ErtsTWheelTimer **w; Sint scnt[ERTS_TW_SCNT_SIZE]; Sint bump_scnt[ERTS_TW_SCNT_SIZE]; @@ -278,15 +296,20 @@ struct ErtsTimerWheel_ { Uint nto; } at_once; struct { + ErtsMonotonicTime min_tpos; Uint nto; } soon; struct { + ErtsMonotonicTime min_tpos; + int min_tpos_slot; ErtsMonotonicTime pos; + Uint nto; } later; int yield_slot; int yield_slots_left; ErtsTWheelTimer sentinel; int true_next_timeout_time; + ErtsMonotonicTime next_timeout_pos; ErtsMonotonicTime next_timeout_time; }; @@ -297,6 +320,18 @@ struct ErtsTimerWheel_ { static int bump_later_wheel(ErtsTimerWheel *tiw, int *yield_count_p); +#ifdef ERTS_TW_DEBUG +#define ERTS_TW_DBG_VERIFY_EMPTY_SOON_SLOTS(TIW, TO_POS) \ + dbg_verify_empty_soon_slots((TIW), (TO_POS)) +#define ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS(TIW, TO_POS) \ + dbg_verify_empty_later_slots((TIW), (TO_POS)) +void dbg_verify_empty_soon_slots(ErtsTimerWheel *, ErtsMonotonicTime); +void dbg_verify_empty_later_slots(ErtsTimerWheel *, ErtsMonotonicTime); +#else +#define ERTS_TW_DBG_VERIFY_EMPTY_SOON_SLOTS(TIW, TO_POS) +#define ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS(TIW, TO_POS) +#endif + static ERTS_INLINE int scnt_get_ix(int slot) { @@ -434,47 +469,59 @@ static void hrd_dbg_check_wheels(ErtsTimerWheel *tiw, int check_min_tpos); #endif static ErtsMonotonicTime -find_next_timeout(ErtsSchedulerData *esdp, ErtsTimerWheel *tiw, int thorough) +find_next_timeout(ErtsSchedulerData *esdp, ErtsTimerWheel *tiw) { int slot, slots; int true_min_timeout = 0; - ErtsMonotonicTime min_timeout, min_timeout_pos, slot_timeout_pos; + ErtsMonotonicTime min_timeout_pos; + + ERTS_TW_ASSERT(tiw->pos + ERTS_TW_LATER_WHEEL_SLOT_SIZE < tiw->later.pos + && tiw->later.pos <= tiw->pos + ERTS_TW_SOON_WHEEL_SIZE); ERTS_HARD_DBG_CHK_WHEELS(tiw, 0); ERTS_TW_ASSERT(tiw->yield_slot == ERTS_TW_SLOT_INACTIVE); if (tiw->nto == 0) { /* no timeouts in wheel */ - if (!thorough) - min_timeout_pos = tiw->pos; - else { - ErtsMonotonicTime curr_time = erts_get_monotonic_time(esdp); - tiw->pos = min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time); - } - min_timeout_pos += ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_WEEK); + ErtsMonotonicTime curr_time = erts_get_monotonic_time(esdp); + tiw->pos = min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time); + tiw->later.pos = min_timeout_pos + ERTS_TW_SOON_WHEEL_SIZE; + tiw->later.pos &= ERTS_TW_LATER_WHEEL_POS_MASK; + min_timeout_pos += ERTS_CLKTCKS_WEEK; goto done; } - min_timeout_pos = tiw->pos; - if (thorough) - min_timeout_pos += ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_WEEK); - else - min_timeout_pos += ERTS_TW_SOON_WHEEL_SIZE/2; + ERTS_TW_ASSERT(tiw->soon.nto || tiw->later.nto); if (!tiw->soon.nto) { - ErtsMonotonicTime tmp; - /* Select later wheel... */ - slot_timeout_pos = tiw->later.pos; - slot = later_slot(slot_timeout_pos); - /* Pre-timeout for move from later to soon wheel... */ - slot_timeout_pos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; - tmp = min_timeout_pos - slot_timeout_pos; - tmp /= ERTS_TW_LATER_WHEEL_SLOT_SIZE; - tmp++; - if (tmp > ERTS_TW_LATER_WHEEL_SIZE) + ErtsMonotonicTime tpos, min_tpos; + + /* Search later wheel... */ + + min_tpos = tiw->later.min_tpos & ERTS_TW_LATER_WHEEL_POS_MASK; + + if (min_tpos <= tiw->later.pos) { + tpos = tiw->later.pos; slots = ERTS_TW_LATER_WHEEL_SIZE; - else - slots = (int) tmp; + } + else { + ErtsMonotonicTime tmp; + /* Don't inspect slots we know are empty... */ + tmp = min_tpos - tiw->later.pos; + tmp /= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + if (tmp >= ERTS_TW_LATER_WHEEL_SIZE) { + /* Timeout more than one revolution ahead... */ + + /* Pre-timeout for move from later to soon wheel... */ + min_timeout_pos = min_tpos - ERTS_TW_LATER_WHEEL_SLOT_SIZE; + goto done; + } + tpos = min_tpos; + ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS(tiw, min_tpos); + slots = ERTS_TW_LATER_WHEEL_SIZE - ((int) tmp); + } + + slot = later_slot(tpos); /* * We never search for an exact timeout in the @@ -484,13 +531,21 @@ find_next_timeout(ErtsSchedulerData *esdp, ErtsTimerWheel *tiw, int thorough) if (tiw->w[slot]) true_min_timeout = 1; else - scnt_later_wheel_next(&slot, &slots, &slot_timeout_pos, - NULL, tiw->scnt); - min_timeout_pos = slot_timeout_pos; + scnt_later_wheel_next(&slot, &slots, &tpos, NULL, tiw->scnt); + + tiw->later.min_tpos = tpos; + tiw->later.min_tpos_slot = slot; + ERTS_TW_ASSERT(slot == later_slot(tpos)); + + /* Pre-timeout for move from later to soon wheel... */ + tpos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + min_timeout_pos = tpos; } else { - ErtsMonotonicTime tmp; - /* Select soon wheel... */ + ErtsMonotonicTime tpos; + /* Search soon wheel... */ + + min_timeout_pos = tiw->pos + ERTS_TW_SOON_WHEEL_SIZE; /* * Besides inspecting the soon wheel we @@ -498,64 +553,72 @@ find_next_timeout(ErtsSchedulerData *esdp, ErtsTimerWheel *tiw, int thorough) * later wheel which potentially can trigger * timeouts before timeouts in soon wheel... */ - slot_timeout_pos = tiw->later.pos; - slot_timeout_pos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; - if (slot_timeout_pos < min_timeout_pos) { - int fslot = later_slot(tiw->later.pos); - if (tiw->w[fslot]) { - min_timeout_pos = slot_timeout_pos; - true_min_timeout = 1; - } + if (tiw->later.min_tpos > (tiw->later.pos + + 2*ERTS_TW_LATER_WHEEL_SLOT_SIZE)) { + ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS( + tiw, 2*ERTS_TW_LATER_WHEEL_SLOT_SIZE); + } + else { + int fslot; + tpos = tiw->later.pos; + tpos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + fslot = later_slot(tiw->later.pos); + if (tiw->w[fslot]) + min_timeout_pos = tpos; else { - slot_timeout_pos += ERTS_TW_LATER_WHEEL_SLOT_SIZE; - if (slot_timeout_pos < min_timeout_pos) { + tpos += ERTS_TW_LATER_WHEEL_SLOT_SIZE; + if (tpos < min_timeout_pos) { fslot++; if (fslot == ERTS_TW_LATER_WHEEL_END_SLOT) fslot = ERTS_TW_LATER_WHEEL_FIRST_SLOT; - if (tiw->w[fslot]) { - min_timeout_pos = slot_timeout_pos; - true_min_timeout = 1; - } + if (tiw->w[fslot]) + min_timeout_pos = tpos; } } } - slot_timeout_pos = tiw->pos; - slot = soon_slot(tiw->pos); - tmp = min_timeout_pos - slot_timeout_pos; - if (tmp > ERTS_TW_SOON_WHEEL_SIZE) + if (tiw->soon.min_tpos <= tiw->pos) { + tpos = tiw->pos; slots = ERTS_TW_SOON_WHEEL_SIZE; - else - slots = (int) tmp; + } + else { + ErtsMonotonicTime tmp; + /* Don't inspect slots we know are empty... */ + tmp = tiw->soon.min_tpos - tiw->pos; + ERTS_TW_ASSERT(ERTS_TW_SOON_WHEEL_SIZE > tmp); + ERTS_TW_DBG_VERIFY_EMPTY_SOON_SLOTS(tiw, tiw->soon.min_tpos); + slots = ERTS_TW_SOON_WHEEL_SIZE - ((int) tmp); + tpos = tiw->soon.min_tpos; + } - while (slot_timeout_pos < min_timeout_pos) { + slot = soon_slot(tpos); + + /* find next non-empty slot */ + while (tpos < min_timeout_pos) { if (tiw->w[slot]) { - ERTS_TW_ASSERT(tiw->w[slot]->timeout_pos == slot_timeout_pos); - min_timeout_pos = slot_timeout_pos; - true_min_timeout = 1; + ERTS_TW_ASSERT(tiw->w[slot]->timeout_pos == tpos); + min_timeout_pos = tpos; break; } - scnt_soon_wheel_next(&slot, &slots, &slot_timeout_pos, - NULL, tiw->scnt); + scnt_soon_wheel_next(&slot, &slots, &tpos, NULL, tiw->scnt); } - if (slots > 0 && !true_min_timeout) { - /* Find first non-empty range... */ - scnt_soon_wheel_next(&slot, &slots, &slot_timeout_pos, - NULL, tiw->scnt); - min_timeout_pos = slot_timeout_pos; - } + tiw->soon.min_tpos = min_timeout_pos; + true_min_timeout = 1; } -done: +done: { + ErtsMonotonicTime min_timeout; - min_timeout = ERTS_CLKTCKS_TO_MONOTONIC(min_timeout_pos); - tiw->next_timeout_time = min_timeout; - tiw->true_next_timeout_time = true_min_timeout; + min_timeout = ERTS_CLKTCKS_TO_MONOTONIC(min_timeout_pos); + tiw->next_timeout_pos = min_timeout_pos; + tiw->next_timeout_time = min_timeout; + tiw->true_next_timeout_time = true_min_timeout; - ERTS_HARD_DBG_CHK_WHEELS(tiw, 1); + ERTS_HARD_DBG_CHK_WHEELS(tiw, 1); - return min_timeout; + return min_timeout; + } } static ERTS_INLINE void @@ -581,9 +644,20 @@ insert_timer_into_slot(ErtsTimerWheel *tiw, int slot, ErtsTWheelTimer *p) if (slot == ERTS_TW_SLOT_AT_ONCE) tiw->at_once.nto++; else { + ErtsMonotonicTime tpos = p->timeout_pos; if (slot < ERTS_TW_SOON_WHEEL_END_SLOT) { ERTS_TW_ASSERT(p->timeout_pos < tiw->pos + ERTS_TW_SOON_WHEEL_SIZE); tiw->soon.nto++; + if (tiw->soon.min_tpos > tpos) + tiw->soon.min_tpos = tpos; + } + else { + ERTS_TW_ASSERT(p->timeout_pos >= tiw->pos + ERTS_TW_SOON_WHEEL_SIZE); + tiw->later.nto++; + if (tiw->later.min_tpos > tpos) { + tiw->later.min_tpos = tpos; + tiw->later.min_tpos_slot = slot; + } } scnt_inc(tiw->scnt, slot); } @@ -593,6 +667,7 @@ static ERTS_INLINE void remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) { int slot = p->slot; + int empty_slot; ERTS_TW_ASSERT(slot != ERTS_TW_SLOT_INACTIVE); /* @@ -608,21 +683,45 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) /* Cannot be referred by sentinel, i.e. must be referred by slot... */ ERTS_TW_ASSERT(tiw->w[slot] == p); tiw->w[slot] = NULL; + empty_slot = 1; } else { if (tiw->w[slot] == p) tiw->w[slot] = p->next; p->prev->next = p->next; p->next->prev = p->prev; + empty_slot = 0; } if (slot == ERTS_TW_SLOT_AT_ONCE) { ERTS_TW_ASSERT(tiw->at_once.nto > 0); tiw->at_once.nto--; } else { - if (slot < ERTS_TW_SOON_WHEEL_END_SLOT) - tiw->soon.nto--; scnt_dec(tiw->scnt, slot); + if (slot < ERTS_TW_SOON_WHEEL_END_SLOT) { + if (empty_slot + && tiw->true_next_timeout_time + && p->timeout_pos == tiw->next_timeout_pos) { + tiw->true_next_timeout_time = 0; + } + if (--tiw->soon.nto == 0) + tiw->soon.min_tpos = ERTS_MAX_CLKTCKS; + } + else { + if (empty_slot + && tiw->true_next_timeout_time + && tiw->later.min_tpos_slot == slot) { + ErtsMonotonicTime tpos = tiw->later.min_tpos; + tpos &= ERTS_TW_LATER_WHEEL_POS_MASK; + tpos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + if (tpos == tiw->next_timeout_pos) + tiw->true_next_timeout_time = 0; + } + if (--tiw->later.nto == 0) { + tiw->later.min_tpos = ERTS_MAX_CLKTCKS; + tiw->later.min_tpos_slot = ERTS_TW_LATER_WHEEL_END_SLOT; + } + } } p->slot = ERTS_TW_SLOT_INACTIVE; } @@ -633,82 +732,18 @@ erts_check_next_timeout_time(ErtsSchedulerData *esdp) ErtsTimerWheel *tiw = esdp->timer_wheel; ErtsMonotonicTime time; ERTS_MSACC_DECLARE_CACHE_X(); + ERTS_TW_ASSERT(tiw->next_timeout_time + == ERTS_CLKTCKS_TO_MONOTONIC(tiw->next_timeout_pos)); if (tiw->true_next_timeout_time) - return tiw->next_timeout_time; + return tiw->next_timeout_time; /* known timeout... */ + if (tiw->next_timeout_pos > tiw->pos + ERTS_TW_SOON_WHEEL_SIZE) + return tiw->next_timeout_time; /* sufficiently later away... */ ERTS_MSACC_PUSH_AND_SET_STATE_CACHED_X(ERTS_MSACC_STATE_TIMERS); - time = find_next_timeout(esdp, tiw, 1); + time = find_next_timeout(esdp, tiw); ERTS_MSACC_POP_STATE_M_X(); return time; } -#ifndef ERTS_TW_DEBUG -#define ERTS_DBG_CHK_SAFE_TO_SKIP_TO(TIW, TO) ((void) 0) -#else -#define ERTS_DBG_CHK_SAFE_TO_SKIP_TO(TIW, TO) debug_check_safe_to_skip_to((TIW), (TO)) -static void -debug_check_safe_to_skip_to(ErtsTimerWheel *tiw, ErtsMonotonicTime skip_to_pos) -{ - int slots, ix; - ErtsTWheelTimer *tmr; - ErtsMonotonicTime tmp; - - ix = soon_slot(tiw->pos); - tmp = skip_to_pos - tiw->pos; - ERTS_TW_ASSERT(tmp >= 0); - if (tmp < (ErtsMonotonicTime) ERTS_TW_SOON_WHEEL_SIZE) - slots = (int) tmp; - else - slots = ERTS_TW_SOON_WHEEL_SIZE; - - while (slots > 0) { - tmr = tiw->w[ix]; - if (tmr) { - ErtsTWheelTimer *end = tmr; - do { - ERTS_TW_ASSERT(tmr->timeout_pos > skip_to_pos); - tmr = tmr->next; - } while (tmr != end); - } - ix++; - if (ix == ERTS_TW_SOON_WHEEL_END_SLOT) - ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT; - slots--; - } - - ix = later_slot(tiw->later.pos); - tmp = skip_to_pos; - tmp &= ERTS_TW_LATER_WHEEL_POS_MASK; - if (tmp >= tiw->later.pos) { - tmp -= tiw->later.pos; - tmp /= ERTS_TW_LATER_WHEEL_SLOT_SIZE; - tmp++; - ERTS_TW_ASSERT(tmp >= 0); - if (tmp < (ErtsMonotonicTime) ERTS_TW_LATER_WHEEL_SIZE) - slots = (int) tmp; - else - slots = ERTS_TW_LATER_WHEEL_SIZE; - - while (slots > 0) { - tmr = tiw->w[ix]; - if (tmr) { - ErtsMonotonicTime tpos = tmr->timeout_pos; - ErtsTWheelTimer *end = tmr; - do { - tpos &= ERTS_TW_LATER_WHEEL_POS_MASK; - tpos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; - ERTS_TW_ASSERT(tpos > skip_to_pos); - tmr = tmr->next; - } while (tmr != end); - } - ix++; - if (ix == ERTS_TW_LATER_WHEEL_END_SLOT) - ix = ERTS_TW_LATER_WHEEL_FIRST_SLOT; - slots--; - } - } -} -#endif - static ERTS_INLINE void timeout_timer(ErtsTWheelTimer *p) { @@ -758,16 +793,23 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) restarted = 0; bump_to = ERTS_MONOTONIC_TO_CLKTCKS(curr_time); + tiw->true_next_timeout_time = 1; + tiw->next_timeout_pos = bump_to; + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to); while (1) { ErtsTWheelTimer *p; if (tiw->nto == 0) { empty_wheel: - ERTS_DBG_CHK_SAFE_TO_SKIP_TO(tiw, bump_to); + ERTS_TW_DBG_VERIFY_EMPTY_SOON_SLOTS(tiw, bump_to); + ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS(tiw, bump_to); tiw->true_next_timeout_time = 0; - tiw->next_timeout_time = curr_time + ERTS_MONOTONIC_WEEK; + tiw->next_timeout_pos = bump_to + ERTS_CLKTCKS_WEEK; + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(tiw->next_timeout_pos);; tiw->pos = bump_to; + tiw->later.pos = bump_to + ERTS_TW_SOON_WHEEL_SIZE; + tiw->later.pos &= ERTS_TW_LATER_WHEEL_POS_MASK; tiw->yield_slot = ERTS_TW_SLOT_INACTIVE; ERTS_MSACC_POP_STATE_M_X(); return; @@ -811,8 +853,6 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) ERTS_TW_ASSERT(tiw->nto > 0); ERTS_TW_ASSERT(tiw->at_once.nto > 0); tiw->yield_slot = ERTS_TW_SLOT_AT_ONCE; - tiw->true_next_timeout_time = 1; - tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to); ERTS_MSACC_POP_STATE_M_X(); return; /* Yield! */ } @@ -847,28 +887,22 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) sys_memcpy((void *) bump_scnt, (void *) scnt, sizeof(Sint) * ERTS_TW_SCNT_SIZE); - if (tiw->true_next_timeout_time) { - ErtsMonotonicTime skip_until_pos; + if (tiw->soon.min_tpos > tiw->pos) { + ErtsMonotonicTime skip_until_pos = tiw->soon.min_tpos; + /* * No need inspecting slots where we know no timeouts * to trigger should reside. */ - skip_until_pos = ERTS_MONOTONIC_TO_CLKTCKS(tiw->next_timeout_time); if (skip_until_pos > bump_to) skip_until_pos = bump_to; skip_until_pos--; if (skip_until_pos > tiw->pos) { - ERTS_DBG_CHK_SAFE_TO_SKIP_TO(tiw, skip_until_pos); - + ERTS_TW_DBG_VERIFY_EMPTY_SOON_SLOTS(tiw, skip_until_pos); tiw->pos = skip_until_pos; - - skip_until_pos++; - skip_until_pos &= ERTS_TW_LATER_WHEEL_POS_MASK; - if (tiw->later.pos < skip_until_pos) - tiw->later.pos = skip_until_pos; } } @@ -884,6 +918,9 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) slot = soon_slot(tiw->pos+1); tiw->pos = bump_to; + tiw->next_timeout_pos = bump_to; + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to); + scnt_ix = scnt_get_ix(slot); /* Timeout timers in soon wheel */ @@ -910,7 +947,8 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) ERTS_TW_ASSERT(ERTS_TW_SOON_WHEEL_FIRST_SLOT <= p->slot && p->slot < ERTS_TW_SOON_WHEEL_END_SLOT); - tiw->soon.nto--; + if (--tiw->soon.nto == 0) + tiw->soon.min_tpos = ERTS_MAX_CLKTCKS; scnt_ix_dec(scnt, scnt_ix); if (p->timeout_pos <= bump_to) { timeout_timer(p); @@ -933,8 +971,6 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) } if (yield_count <= 0) { - tiw->true_next_timeout_time = 1; - tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to); tiw->yield_slot = slot; tiw->yield_slots_left = slots; ERTS_MSACC_POP_STATE_M_X(); @@ -959,9 +995,9 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) } while (restarted); tiw->true_next_timeout_time = 0; - tiw->next_timeout_time = curr_time + ERTS_MONOTONIC_WEEK; + ERTS_TW_ASSERT(tiw->next_timeout_pos == bump_to); - (void) find_next_timeout(NULL, tiw, 0); + (void) find_next_timeout(NULL, tiw); ERTS_MSACC_POP_STATE_M_X(); } @@ -988,15 +1024,31 @@ bump_later_wheel(ErtsTimerWheel *tiw, int *ycount_p) goto restart_yielded_slot; } else { - ErtsMonotonicTime tmp_slots = cpos; - tmp_slots += ERTS_TW_LATER_WHEEL_SLOT_SIZE; + ErtsMonotonicTime end_later_pos, tmp_slots, min_tpos; + + min_tpos = tiw->later.min_tpos & ERTS_TW_LATER_WHEEL_POS_MASK; + end_later_pos = cpos + ERTS_TW_SOON_WHEEL_SIZE; + end_later_pos &= ERTS_TW_LATER_WHEEL_POS_MASK; + + /* Skip known empty slots... */ + if (min_tpos > later_pos) { + if (min_tpos > end_later_pos) { + later_pos = end_later_pos; + ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS(tiw, later_pos); + goto done; + } + later_pos = min_tpos; + ERTS_TW_DBG_VERIFY_EMPTY_LATER_SLOTS(tiw, later_pos); + } + + tmp_slots = end_later_pos; tmp_slots -= later_pos; tmp_slots /= ERTS_TW_LATER_WHEEL_SLOT_SIZE; - tmp_slots++; if (tmp_slots < ERTS_TW_LATER_WHEEL_SIZE) slots = (int) tmp_slots; else slots = ERTS_TW_LATER_WHEEL_SIZE; + fslot = later_slot(later_pos); scnt_ix = scnt_get_ix(fslot); } @@ -1028,6 +1080,10 @@ bump_later_wheel(ErtsTimerWheel *tiw, int *ycount_p) ERTS_TW_ASSERT(tpos >= later_pos); ERTS_TW_ASSERT(p->slot == fslot); + if (--tiw->later.nto == 0) { + tiw->later.min_tpos = ERTS_MAX_CLKTCKS; + tiw->later.min_tpos_slot = ERTS_TW_LATER_WHEEL_END_SLOT; + } scnt_ix_dec(scnt, scnt_ix); if (tpos >= later_pos + ERTS_TW_LATER_WHEEL_SLOT_SIZE) { @@ -1061,8 +1117,6 @@ bump_later_wheel(ErtsTimerWheel *tiw, int *ycount_p) if (ycount < 0) { tiw->later.pos = later_pos; - tiw->true_next_timeout_time = 1; - tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(cpos); tiw->yield_slot = fslot; tiw->yield_slots_left = slots; *ycount_p = 0; @@ -1078,6 +1132,8 @@ bump_later_wheel(ErtsTimerWheel *tiw, int *ycount_p) scnt_later_wheel_next(&fslot, &slots, &later_pos, &scnt_ix, bump_scnt); } +done: + ERTS_HARD_DBG_CHK_WHEELS(tiw, 0); tiw->later.pos = later_pos; @@ -1129,13 +1185,17 @@ erts_create_timer_wheel(ErtsSchedulerData *esdp) tiw->pos = ERTS_MONOTONIC_TO_CLKTCKS(mtime); tiw->nto = 0; tiw->at_once.nto = 0; + tiw->soon.min_tpos = ERTS_MAX_CLKTCKS; tiw->soon.nto = 0; - tiw->later.pos = tiw->pos; + tiw->later.min_tpos = ERTS_MAX_CLKTCKS; + tiw->later.min_tpos_slot = ERTS_TW_LATER_WHEEL_END_SLOT; + tiw->later.pos = tiw->pos + ERTS_TW_SOON_WHEEL_SIZE; tiw->later.pos &= ERTS_TW_LATER_WHEEL_POS_MASK; - tiw->later.pos += ERTS_TW_LATER_WHEEL_SLOT_SIZE; + tiw->later.nto = 0; tiw->yield_slot = ERTS_TW_SLOT_INACTIVE; tiw->true_next_timeout_time = 0; - tiw->next_timeout_time = mtime + ERTS_MONOTONIC_WEEK; + tiw->next_timeout_pos = tiw->pos + ERTS_CLKTCKS_WEEK; + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(tiw->next_timeout_pos); tiw->sentinel.next = &tiw->sentinel; tiw->sentinel.prev = &tiw->sentinel; tiw->sentinel.timeout = NULL; @@ -1175,7 +1235,6 @@ erts_twheel_set_timer(ErtsTimerWheel *tiw, void *arg, ErtsMonotonicTime timeout_pos) { int slot; - ErtsMonotonicTime timeout_time; ERTS_MSACC_PUSH_AND_SET_STATE_M_X(ERTS_MSACC_STATE_TIMERS); p->timeout = timeout; @@ -1195,6 +1254,8 @@ erts_twheel_set_timer(ErtsTimerWheel *tiw, /* soon wheel */ p->timeout_pos = timeout_pos; slot = soon_slot(timeout_pos); + if (tiw->soon.min_tpos > timeout_pos) + tiw->soon.min_tpos = timeout_pos; } else { /* later wheel */ @@ -1214,11 +1275,13 @@ erts_twheel_set_timer(ErtsTimerWheel *tiw, } insert_timer_into_slot(tiw, slot, p); - timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos); - if (timeout_time < tiw->next_timeout_time) { + if (timeout_pos <= tiw->next_timeout_pos) { tiw->true_next_timeout_time = 1; - tiw->next_timeout_time = timeout_time; + if (timeout_pos < tiw->next_timeout_pos) { + tiw->next_timeout_pos = timeout_pos; + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos); + } } ERTS_MSACC_POP_STATE_M_X(); } @@ -1264,6 +1327,73 @@ erts_twheel_debug_foreach(ErtsTimerWheel *tiw, } } +#ifdef ERTS_TW_DEBUG + +void +dbg_verify_empty_soon_slots(ErtsTimerWheel *tiw, ErtsMonotonicTime to_pos) +{ + int ix; + ErtsMonotonicTime tmp; + + ix = soon_slot(tiw->pos); + tmp = to_pos; + if (tmp > tiw->pos) { + int slots; + tmp -= tiw->pos; + ERTS_TW_ASSERT(tmp > 0); + if (tmp < (ErtsMonotonicTime) ERTS_TW_SOON_WHEEL_SIZE) + slots = (int) tmp; + else + slots = ERTS_TW_SOON_WHEEL_SIZE; + + while (slots > 0) { + ERTS_TW_ASSERT(!tiw->w[ix]); + ix++; + if (ix == ERTS_TW_SOON_WHEEL_END_SLOT) + ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT; + slots--; + } + } +} + +void +dbg_verify_empty_later_slots(ErtsTimerWheel *tiw, ErtsMonotonicTime to_pos) +{ + int ix; + ErtsMonotonicTime tmp; + + ix = later_slot(tiw->later.pos); + tmp = to_pos; + tmp &= ERTS_TW_LATER_WHEEL_POS_MASK; + if (tmp > tiw->later.pos) { + int slots; + tmp -= tiw->later.pos; + tmp /= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + ERTS_TW_ASSERT(tmp > 0); + if (tmp < (ErtsMonotonicTime) ERTS_TW_LATER_WHEEL_SIZE) + slots = (int) tmp; + else + slots = ERTS_TW_LATER_WHEEL_SIZE; + + while (slots > 0) { + ErtsTWheelTimer *tmr = tiw->w[ix]; + if (tmr) { + ErtsTWheelTimer *end = tmr; + do { + ERTS_TW_ASSERT(tmr->timeout_pos > to_pos); + tmr = tmr->next; + } while (tmr != end); + } + ix++; + if (ix == ERTS_TW_LATER_WHEEL_END_SLOT) + ix = ERTS_TW_LATER_WHEEL_FIRST_SLOT; + slots--; + } + } +} + +#endif /* ERTS_TW_DEBUG */ + #ifdef ERTS_TW_HARD_DEBUG static void @@ -1385,10 +1515,11 @@ hrd_dbg_check_wheels(ErtsTimerWheel *tiw, int check_min_tpos) ERTS_TW_ASSERT(tiw->at_once.nto == at_once_tmo); ERTS_TW_ASSERT(tiw->soon.nto == soon_tmo); + ERTS_TW_ASSERT(tiw->later.nto == later_tmo); ERTS_TW_ASSERT(tiw->nto == soon_tmo + later_tmo + at_once_tmo); for (six = 0; six < ERTS_TW_SCNT_SIZE; six++) ERTS_TW_ASSERT(scnt[six] == tiw->scnt[six]); } -#endif +#endif /* ERTS_TW_HARD_DEBUG */ diff --git a/erts/etc/unix/etp-commands.in b/erts/etc/unix/etp-commands.in index c689d495e6..643cfbf323 100644 --- a/erts/etc/unix/etp-commands.in +++ b/erts/etc/unix/etp-commands.in @@ -2871,6 +2871,81 @@ define etp-disasm end end +############################################################################ +# +# Timer Wheel +# + +define etp-timer-wheel +# Args: TimerWheel + if (!erts_initialized) + printf "System not initialized!\n" + else + set $tiw = $arg0 + printf "Number of timers: %d\n", $tiw->nto + printf "Min timeout pos: %d\n", $tiw->next_timeout_pos + printf "\n--- Soon Wheel ---\n" + set $ix = $tiw->pos & etp_tw_soon_wheel_mask + printf "Position: %ld (%d)\n", $tiw->pos, $ix + printf "Min timeout position: %ld (%d)\n", $tiw->soon.min_tpos, $tiw->soon.min_tpos & etp_tw_soon_wheel_mask + printf "Number of timers: %d\n", $tiw->soon.nto + set $slots = etp_tw_soon_wheel_size + while $slots > 0 + set $tmr = $tiw->w[$ix] + if ($tmr != (ErtsTWheelTimer *) 0x0) + printf "---\n" + printf "Slot: %d\n", $ix + printf "\n" + while 1 + printf "- Timeout pos: %ld\n", $tmr->timeout_pos + printf " Pointer: (ErtsTWheelTimer *) %p\n", $tmr + set $tmr = $tmr->next + if ($tmr == $tiw->w[$ix]) + loop_break + end + end + end + set $ix++ + if ($ix == (etp_tw_soon_wheel_first_slot + etp_tw_soon_wheel_size)) + set $ix = etp_tw_soon_wheel_first_slot + end + set $slots-- + end + printf "\n--- Later Wheel ---\n" + set $ix = (($tiw->later.pos >> etp_tw_later_wheel_shift) & etp_tw_later_wheel_mask) + etp_tw_later_wheel_first_slot + printf "Position: %ld (%d)\n", $tiw->later.pos, $ix + printf "Min timeout position: %ld (%d)\n", $tiw->later.min_tpos, (($tiw->later.min_tpos >> etp_tw_later_wheel_shift) & etp_tw_later_wheel_mask) + etp_tw_later_wheel_first_slot + printf "Number of timers: %d\n", $tiw->later.nto + set $slots = etp_tw_later_wheel_size + set $slot_pos = $tiw->later.pos + while $slots > 0 + set $tmr = $tiw->w[$ix] + if ($tmr != (ErtsTWheelTimer *) 0x0) + printf "---\n" + printf "Slot: %d\n", $ix + printf "Slot Range: [%ld, %ld]\n", $slot_pos, $slot_pos + etp_tw_later_wheel_slot_size + printf "Pre timeout pos: %ld\n", $slot_pos - etp_tw_later_wheel_slot_size + printf "\n" + while 1 + printf "- Timeout pos: %ld\n", $tmr->timeout_pos + printf " Pointer: (ErtsTWheelTimer *) %p\n", $tmr + set $tmr = $tmr->next + if ($tmr == $tiw->w[$ix]) + loop_break + end + end + end + set $ix++ + if ($ix == (etp_tw_later_wheel_first_slot + etp_tw_later_wheel_size)) + set $ix = etp_tw_later_wheel_first_slot + end + set $slot_pos = $slot_pos + etp_tw_later_wheel_slot_size + set $slots-- + end + end + printf "---\n" +end + document etp-disasm %--------------------------------------------------------------------------- % etp-disasm StartI EndI |