diff options
Diffstat (limited to 'erts/emulator/beam/time.c')
| -rw-r--r-- | erts/emulator/beam/time.c | 810 |
1 files changed, 627 insertions, 183 deletions
diff --git a/erts/emulator/beam/time.c b/erts/emulator/beam/time.c index 53896be19e..7b5ff7b992 100644 --- a/erts/emulator/beam/time.c +++ b/erts/emulator/beam/time.c @@ -17,57 +17,124 @@ * * %CopyrightEnd% */ + /* - * TIMING WHEEL + * TIMER WHEEL + * + * + * The time scale used for timers is Erlang monotonic time. The + * time unit used is ERTS specific clock ticks. A clock tick is + * currently defined to 1 millisecond. That is, the resolution of + * timers triggered by the runtime system is 1 millisecond. * - * Timeouts kept in an wheel. A timeout is measured relative to the - * current slot (tiw_pos) in the wheel, and inserted at slot - * (tiw_pos + timeout) % TIW_SIZE. Each timeout also has a count - * equal to timeout/TIW_SIZE, which is needed since the time axis - * is wrapped arount the wheel. + * When a timer is set, it is determined at what Erlang monotonic + * time, in clock ticks, it should be triggered. * - * Several slots may be processed in one operation. If the number of - * slots is greater that the wheel size, the wheel is only traversed - * once, + * The 'pos' field of the wheel corresponds to current time of + * the wheel. That is, it corresponds to Erlang monotonic time in + * clock tick time unit. The 'pos' field of the wheel is + * monotonically increased when erts_bump_timers() is called. All + * timers in the wheel that have a time less than or equal to + * 'pos' are triggered by the bump operation. The bump operation + * may however be spread over multiple calls to erts_bump_timers() + * if there are a lots of timers to trigger. + * + * Each scheduler thread maintains its own timer wheel. The timer + * wheel of a scheduler, however, actually consists of two wheels. + * A soon wheel and a later wheel. + * + * + * -- The Soon Wheel -- + * + * The soon wheel contain timers that should be triggered soon. + * That is, they are soon to be triggered. Each slot in the soon + * wheel is 1 clock tick wide. The number of slots in the soon + * wheel is currently 2¹⁴. That is, it contains timers in the + * range ('pos', 'pos' + 2¹⁴] which corresponds to a bit more + * than 16 seconds. + * + * When the bump operation is started, 'pos' is moved forward to a + * position that corresponds to current Erlang monotonic time. Then + * all timers that are in the range (old 'pos', new 'pos'] are + * triggered. During a bump operation, the soon wheel may contain + * timers in the two, possibly overlapping, ranges (old 'pos', + * old 'pos' + 2¹⁴], and (new 'pos', new 'pos' + 2¹⁴]. This may + * occur even if the bump operation doesn't yield, due to timeout + * callbacks inserting new timers. + * + * + * -- The Later Wheel -- + * + * The later wheel contain timers that are further away from 'pos' + * than the width of the soon timer wheel. That is, currently + * timers further away from 'pos' than 2¹⁴ clock ticks. The width + * of each slot in the later wheel is half the width of the soon + * wheel. That is, each slot is currently 2¹³ clock ticks wide + * which corresponds to about 8 seconds. If three timers of the + * times 'pos' + 17000, 'pos' + 18000, and 'pos' + 19000 are + * inserted, they will all end up in the same slot in the later + * wheel. + * + * The number of slots in the later wheel is currently the same as + * in the soon wheel, i.e. 2¹⁴. That is, one revolution of the later + * wheel currently corresponds to 2¹⁴×2¹³ clock ticks which is + * almost 37 ½ hour. Timers even further away than that are put in + * the later slot identified by their time modulo the size of the later + * wheel. Such timers are however very uncommon. Most timers used + * by the runtime system will utilize the high level timer API. + * The high level timer implementation will not insert timers + * further away then one revolution into the later wheel. It will + * instead keep such timers in a tree of very long timers. The + * high level timer implementation utilize one timer wheel timer + * for the management of this tree of timers. This timer is set to + * the closest timeout in the tree. This timer may however be + * further away than one revolution in the later wheel. + * + * The 'later.pos' field identifies next position in the later wheel. + * 'later.pos' is always increased by the width of a later wheel slot. + * That is, currently 2¹³ clock ticks. When 'pos' is moved (during + * a bump operation) closer to 'later.pos' than the width of a later + * wheel slot, i.e. currently when 'pos' + 2¹³ ≥ 'later.pos', we + * inspect the slot identified by 'later.pos' and then move 'later.pos' + * forward. When inspecting the later slot we move all timers in the + * slot, that are in the soon wheel range, from the later wheel to + * the soon wheel. Timers one or more revolutions of the later wheel + * away are kept in the slot. + * + * During normal operation, timers originally located in the later + * wheel will currently be moved into the soon wheel about 8 to + * 16 seconds before they should be triggered. During extremely + * heavy load, the scheduler might however be heavily delayed, so + * the code must be prepared for situations where time for + * triggering the timer has passed when we inspect the later wheel + * slot, and then trigger the timer immediately. We must also be + * prepared to inspect multiple later wheel slots at once due to the + * delay. + * + * + * -- Slot Management -- + * + * All timers of a slot are placed in a circular double linked + * list. This makes insertion and removal of a timer O(1). + * + * While bumping timers in a slot, we move the circular list + * away from the slot, and refer to it from the 'sentinel' + * field. The list will stay there until we are done with it + * even if the bump operation should yield. The cancel operation + * can remove the timer from this position as well as from the + * slot position by just removing it from the circular double + * linked list that it is in. + * + * -- At Once List -- + * + * If a timer is set that has a time earlier or equal to 'pos', + * it is not inserted into the wheel. It is instead inserted, + * into a list referred to by the 'at_once' field. When the + * bump operation is performed thise timers will be triggered + * at once. * - * The following example shows a time axis where there is one timeout - * at each "tick", and where 1, 2, 3 ... wheel slots are released in - * one operation. The notation "<x" means "release all items with - * counts less than x". * - * Size of wheel: 4 - * - * --|----|----|----|----|----|----|----|----|----|----|----|----|---- - * 0.0 0.1 0.2 0.3 1.0 1.1 1.2 1.3 2.0 2.1 2.2 2.3 3.0 - * - * 1 [ ) - * <1 0.1 0.2 0.3 0.0 1.1 1.2 1.3 1.0 2.1 2.2 2.3 2.0 - * - * 2 [ ) - * <1 <1 0.2 0.3 0.0 0.1 1.2 1.3 1.0 1.1 2.2 2.3 2.0 - * - * 3 [ ) - * <1 <1 <1 0.3 0.0 0.1 0.2 1.3 1.0 1.1 1.2 2.3 2.0 - * - * 4 [ ) - * <1 <1 <1 <1 0.0 0.1 0.2 0.3 1.0 1.1 1.2 1.3 2.0 - * - * 5 [ ) - * <2 <1 <1 <1. 0.1 0.2 0.3 0.0 1.1 1.2 1.3 1.0 - * - * 6 [ ) - * <2 <2 <1 <1. 0.2 0.3 0.0 0.1 1.2 1.3 1.0 - * - * 7 [ ) - * <2 <2 <2 <1. 0.3 0.0 0.1 0.2 1.3 1.0 - * - * 8 [ ) - * <2 <2 <2 <2. 0.0 0.1 0.2 0.3 1.0 - * - * 9 [ ) - * <3 <2 <2 <2. 0.1 0.2 0.3 0.0 - * */ #ifdef HAVE_CONFIG_H @@ -90,6 +157,10 @@ #endif #if 0 +# define ERTS_TW_HARD_DEBUG +#endif + +#if defined(ERTS_TW_HARD_DEBUG) && !defined(ERTS_TW_DEBUG) # define ERTS_TW_DEBUG #endif #if defined(DEBUG) && !defined(ERTS_TW_DEBUG) @@ -97,17 +168,48 @@ #endif #undef ERTS_TW_ASSERT -#if defined(ERTS_TW_DEBUG) +#if defined(ERTS_TW_DEBUG) # define ERTS_TW_ASSERT(E) ERTS_ASSERT(E) #else # define ERTS_TW_ASSERT(E) ((void) 1) #endif #ifdef ERTS_TW_DEBUG -# define ERTS_TWHEEL_BUMP_YIELD_LIMIT 5 +# define ERTS_TWHEEL_BUMP_YIELD_LIMIT 500 #else -# define ERTS_TWHEEL_BUMP_YIELD_LIMIT 100 +# define ERTS_TWHEEL_BUMP_YIELD_LIMIT 10000 #endif +#define ERTS_TW_COST_SLOT 1 +#define ERTS_TW_COST_SLOT_MOVE 5 +#define ERTS_TW_COST_TIMEOUT 100 + +/* + * Every slot in the soon wheel is a clock tick (as defined + * by ERTS) wide. A clock tick is currently 1 milli second. + */ + +#define ERTS_TW_SOON_WHEEL_FIRST_SLOT 0 +#define ERTS_TW_SOON_WHEEL_END_SLOT \ + (ERTS_TW_SOON_WHEEL_FIRST_SLOT + ERTS_TW_SOON_WHEEL_SIZE) + +#define ERTS_TW_SOON_WHEEL_MASK (ERTS_TW_SOON_WHEEL_SIZE-1) + +/* + * Every slot in the later wheel is as wide as half the size + * of the soon wheel. + */ + +#define ERTS_TW_LATER_WHEEL_SHIFT (ERTS_TW_SOON_WHEEL_BITS - 1) +#define ERTS_TW_LATER_WHEEL_SLOT_SIZE \ + ((ErtsMonotonicTime) (1 << ERTS_TW_LATER_WHEEL_SHIFT)) +#define ERTS_TW_LATER_WHEEL_POS_MASK \ + (~((ErtsMonotonicTime) (1 << ERTS_TW_LATER_WHEEL_SHIFT)-1)) + +#define ERTS_TW_LATER_WHEEL_FIRST_SLOT ERTS_TW_SOON_WHEEL_SIZE +#define ERTS_TW_LATER_WHEEL_END_SLOT \ + (ERTS_TW_LATER_WHEEL_FIRST_SLOT + ERTS_TW_LATER_WHEEL_SIZE) + +#define ERTS_TW_LATER_WHEEL_MASK (ERTS_TW_LATER_WHEEL_SIZE-1) /* Actual interval time chosen by sys_init_time() */ @@ -120,7 +222,7 @@ static int tiw_itime; /* Constant after init */ #endif struct ErtsTimerWheel_ { - ErtsTWheelTimer *w[ERTS_TIW_SIZE]; + ErtsTWheelTimer *w[ERTS_TW_SOON_WHEEL_SIZE + ERTS_TW_LATER_WHEEL_SIZE]; ErtsMonotonicTime pos; Uint nto; struct { @@ -128,14 +230,58 @@ struct ErtsTimerWheel_ { ErtsTWheelTimer *tail; Uint nto; } at_once; + struct { + Uint nto; + } soon; + struct { + ErtsMonotonicTime pos; + } later; int yield_slot; int yield_slots_left; - int yield_start_pos; ErtsTWheelTimer sentinel; int true_next_timeout_time; ErtsMonotonicTime next_timeout_time; }; +#define ERTS_TW_BUMP_LATER_WHEEL(TIW) \ + ((tiw)->pos + ERTS_TW_LATER_WHEEL_SLOT_SIZE >= (TIW)->later.pos) + +static int bump_later_wheel(ErtsTimerWheel *tiw, int *yield_count_p); + +static ERTS_INLINE int +soon_slot(ErtsMonotonicTime soon_pos) +{ + ErtsMonotonicTime slot = soon_pos; + slot &= ERTS_TW_SOON_WHEEL_MASK; + + ERTS_TW_ASSERT(ERTS_TW_SOON_WHEEL_FIRST_SLOT <= slot); + ERTS_TW_ASSERT(slot < ERTS_TW_SOON_WHEEL_END_SLOT); + + return (int) slot; +} + +static ERTS_INLINE int +later_slot(ErtsMonotonicTime later_pos) +{ + ErtsMonotonicTime slot = later_pos; + slot >>= ERTS_TW_LATER_WHEEL_SHIFT; + slot &= ERTS_TW_LATER_WHEEL_MASK; + slot += ERTS_TW_LATER_WHEEL_FIRST_SLOT; + + ERTS_TW_ASSERT(ERTS_TW_LATER_WHEEL_FIRST_SLOT <= slot); + ERTS_TW_ASSERT(slot < ERTS_TW_LATER_WHEEL_END_SLOT); + + return (int) slot; +} + +#ifdef ERTS_TW_HARD_DEBUG +#define ERTS_HARD_DBG_CHK_WHEELS(TIW, CHK_MIN_TPOS) \ + hrd_dbg_check_wheels((TIW), (CHK_MIN_TPOS)) +static void hrd_dbg_check_wheels(ErtsTimerWheel *tiw, int check_min_tpos); +#else +#define ERTS_HARD_DBG_CHK_WHEELS(TIW, CHK_MIN_TPOS) +#endif + static ERTS_INLINE ErtsMonotonicTime find_next_timeout(ErtsSchedulerData *esdp, ErtsTimerWheel *tiw, @@ -143,11 +289,14 @@ find_next_timeout(ErtsSchedulerData *esdp, ErtsMonotonicTime curr_time, /* When !search_all */ ErtsMonotonicTime max_search_time) /* When !search_all */ { - int start_ix, tiw_pos_ix; - ErtsTWheelTimer *p; + int start_ix, tiw_pos_ix, pos_inc, wheel_start_ix, wheel_end_ix; int true_min_timeout = 0; ErtsMonotonicTime min_timeout, min_timeout_pos, slot_timeout_pos; + ERTS_HARD_DBG_CHK_WHEELS(tiw, 0); + + ERTS_TW_ASSERT(tiw->yield_slot == ERTS_TWHEEL_SLOT_INACTIVE); + if (tiw->nto == 0) { /* no timeouts in wheel */ if (!search_all) min_timeout_pos = tiw->pos; @@ -156,58 +305,115 @@ find_next_timeout(ErtsSchedulerData *esdp, tiw->pos = min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time); } min_timeout_pos += ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY); - goto found_next; + goto done; } - slot_timeout_pos = min_timeout_pos = tiw->pos; if (search_all) - min_timeout_pos += ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY); + min_timeout_pos = tiw->pos + ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY); else - min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time + max_search_time); + min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time + max_search_time); + + if (!tiw->soon.nto) { + /* Select later wheel... */ + slot_timeout_pos = tiw->later.pos; + start_ix = tiw_pos_ix = later_slot(slot_timeout_pos); + pos_inc = ERTS_TW_LATER_WHEEL_SLOT_SIZE; + wheel_start_ix = ERTS_TW_LATER_WHEEL_FIRST_SLOT; + wheel_end_ix = ERTS_TW_LATER_WHEEL_END_SLOT; + /* Pre-timeout for move from later to soon wheel... */ + slot_timeout_pos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + } + else { + /* Select soon wheel... */ + + /* + * Besides inspecting the soon wheel we + * may also have to inspect two slots in the + * 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; + } + else { + slot_timeout_pos += ERTS_TW_LATER_WHEEL_SLOT_SIZE; + if (slot_timeout_pos < 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; + } + } + } + } - start_ix = tiw_pos_ix = (int) (tiw->pos & (ERTS_TIW_SIZE-1)); + slot_timeout_pos = tiw->pos; + start_ix = tiw_pos_ix = soon_slot(tiw->pos); + pos_inc = 1; + wheel_start_ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT; + wheel_end_ix = ERTS_TW_SOON_WHEEL_END_SLOT; + } + /* + * Scan selected wheel... + */ do { - if (++slot_timeout_pos >= min_timeout_pos) - break; - - p = tiw->w[tiw_pos_ix]; - - if (p) { - ErtsTWheelTimer *end = p; - - do { - ErtsMonotonicTime timeout_pos; - timeout_pos = p->timeout_pos; - if (min_timeout_pos > timeout_pos) { - true_min_timeout = 1; - min_timeout_pos = timeout_pos; - if (min_timeout_pos <= slot_timeout_pos) - goto found_next; - } - p = p->next; - } while (p != end); - } - - tiw_pos_ix++; - if (tiw_pos_ix == ERTS_TIW_SIZE) - tiw_pos_ix = 0; + if (tiw->w[tiw_pos_ix]) { + min_timeout_pos = slot_timeout_pos; + true_min_timeout = 1; + break; + } + + slot_timeout_pos += pos_inc; + if (slot_timeout_pos >= min_timeout_pos) + break; + + tiw_pos_ix++; + if (tiw_pos_ix == wheel_end_ix) + tiw_pos_ix = wheel_start_ix; } while (start_ix != tiw_pos_ix); -found_next: +done: min_timeout = ERTS_CLKTCKS_TO_MONOTONIC(min_timeout_pos); tiw->next_timeout_time = min_timeout; tiw->true_next_timeout_time = true_min_timeout; + ERTS_HARD_DBG_CHK_WHEELS(tiw, 1); + return min_timeout; } static ERTS_INLINE void +insert_timer_into_at_once_list(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) +{ + tiw->at_once.nto++; + p->next = NULL; + p->prev = tiw->at_once.tail; + if (tiw->at_once.tail) { + ERTS_TW_ASSERT(tiw->at_once.head); + tiw->at_once.tail->next = p; + } + else { + ERTS_TW_ASSERT(!tiw->at_once.head); + tiw->at_once.head = p; + } + tiw->at_once.tail = p; + p->slot = ERTS_TWHEEL_SLOT_AT_ONCE; +} + +static ERTS_INLINE void insert_timer_into_slot(ErtsTimerWheel *tiw, int slot, ErtsTWheelTimer *p) { - ERTS_TW_ASSERT(slot >= 0); - ERTS_TW_ASSERT(slot < ERTS_TIW_SIZE); + ERTS_TW_ASSERT(ERTS_TW_SOON_WHEEL_FIRST_SLOT <= slot); + ERTS_TW_ASSERT(slot < ERTS_TW_LATER_WHEEL_END_SLOT); p->slot = slot; if (!tiw->w[slot]) { tiw->w[slot] = p; @@ -223,6 +429,10 @@ insert_timer_into_slot(ErtsTimerWheel *tiw, int slot, ErtsTWheelTimer *p) prev->next = p; next->prev = p; } + if (slot < ERTS_TW_SOON_WHEEL_END_SLOT) { + ERTS_TW_ASSERT(p->timeout_pos < tiw->pos + ERTS_TW_SOON_WHEEL_SIZE); + tiw->soon.nto++; + } } static ERTS_INLINE void @@ -231,13 +441,13 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) int slot = p->slot; ERTS_TW_ASSERT(slot != ERTS_TWHEEL_SLOT_INACTIVE); - if (slot >= 0) { + if (slot >= ERTS_TW_SOON_WHEEL_FIRST_SLOT) { /* * Timer in wheel or in circular * list of timers currently beeing * triggered (referred by sentinel). */ - ERTS_TW_ASSERT(slot < ERTS_TIW_SIZE); + ERTS_TW_ASSERT(slot < ERTS_TW_LATER_WHEEL_END_SLOT); if (p->next == p) { ERTS_TW_ASSERT(tiw->w[slot] == p); @@ -249,6 +459,8 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) p->prev->next = p->next; p->next->prev = p->prev; } + if (slot < ERTS_TW_SOON_WHEEL_END_SLOT) + tiw->soon.nto--; } else { /* Timer in "at once" queue... */ @@ -270,8 +482,6 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) } p->slot = ERTS_TWHEEL_SLOT_INACTIVE; - - tiw->nto--; } ErtsMonotonicTime @@ -299,13 +509,13 @@ debug_check_safe_to_skip_to(ErtsTimerWheel *tiw, ErtsMonotonicTime skip_to_pos) ErtsTWheelTimer *tmr; ErtsMonotonicTime tmp; - ix = (int) (tiw->pos & (ERTS_TIW_SIZE-1)); + ix = soon_slot(tiw->pos); tmp = skip_to_pos - tiw->pos; ERTS_TW_ASSERT(tmp >= 0); - if (tmp < (ErtsMonotonicTime) ERTS_TIW_SIZE) + if (tmp < (ErtsMonotonicTime) ERTS_TW_SOON_WHEEL_SIZE) slots = (int) tmp; else - slots = ERTS_TIW_SIZE; + slots = ERTS_TW_SOON_WHEEL_SIZE; while (slots > 0) { tmr = tiw->w[ix]; @@ -317,10 +527,41 @@ debug_check_safe_to_skip_to(ErtsTimerWheel *tiw, ErtsMonotonicTime skip_to_pos) } while (tmr != end); } ix++; - if (ix == ERTS_TIW_SIZE) - ix = 0; + 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; + 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 @@ -339,8 +580,8 @@ timeout_timer(ErtsTWheelTimer *p) void erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) { - int tiw_pos_ix, slots, yielded_slot_restarted, yield_count; - ErtsMonotonicTime bump_to, tmp_slots, old_pos; + int tiw_pos_ix, yielded_slot_restarted, yield_count, slots; + ErtsMonotonicTime bump_to; ERTS_MSACC_PUSH_AND_SET_STATE_M_X(ERTS_MSACC_STATE_TIMERS); yield_count = ERTS_TWHEEL_BUMP_YIELD_LIMIT; @@ -350,13 +591,16 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) * where we left off when restarting after a yield. */ - if (tiw->yield_slot >= 0) { + if (tiw->yield_slot >= ERTS_TW_SOON_WHEEL_FIRST_SLOT) { yielded_slot_restarted = 1; + bump_to = tiw->pos; + if (tiw->yield_slot >= ERTS_TW_LATER_WHEEL_FIRST_SLOT) + goto restart_yielded_later_slot; tiw_pos_ix = tiw->yield_slot; slots = tiw->yield_slots_left; - bump_to = tiw->pos; - old_pos = tiw->yield_start_pos; - goto restart_yielded_slot; + ASSERT(0 <= slots && slots <= ERTS_TW_SOON_WHEEL_SIZE); + tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE; + goto restart_yielded_soon_slot; } do { @@ -368,8 +612,6 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) while (1) { ErtsTWheelTimer *p; - old_pos = tiw->pos; - if (tiw->nto == 0) { empty_wheel: ERTS_DBG_CHK_SAFE_TO_SKIP_TO(tiw, bump_to); @@ -383,12 +625,12 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) p = tiw->at_once.head; while (p) { - if (--yield_count <= 0) { + if (yield_count <= 0) { ERTS_TW_ASSERT(tiw->nto > 0); ERTS_TW_ASSERT(tiw->at_once.nto > 0); tiw->yield_slot = ERTS_TWHEEL_SLOT_AT_ONCE; tiw->true_next_timeout_time = 1; - tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(old_pos); + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to); ERTS_MSACC_POP_STATE_M_X(); return; } @@ -405,6 +647,8 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) timeout_timer(p); + yield_count -= ERTS_TW_COST_TIMEOUT; + p = tiw->at_once.head; } @@ -433,22 +677,34 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) ERTS_DBG_CHK_SAFE_TO_SKIP_TO(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; } } - tiw_pos_ix = (int) ((tiw->pos+1) & (ERTS_TIW_SIZE-1)); - tmp_slots = (bump_to - tiw->pos); - if (tmp_slots < (ErtsMonotonicTime) ERTS_TIW_SIZE) - slots = (int) tmp_slots; - else - slots = ERTS_TIW_SIZE; + { + ErtsMonotonicTime tmp_slots = bump_to - tiw->pos; + tmp_slots = (bump_to - tiw->pos); + if (tmp_slots < ERTS_TW_SOON_WHEEL_SIZE) + slots = (int) tmp_slots; + else + slots = ERTS_TW_SOON_WHEEL_SIZE; + } + tiw_pos_ix = soon_slot(tiw->pos+1); tiw->pos = bump_to; - while (slots > 0) { + /* Timeout timers in soon wheel */ + while (slots) { + + yield_count -= ERTS_TW_COST_SLOT; p = tiw->w[tiw_pos_ix]; if (p) { + /* timeout callback need tiw->pos to be up to date */ if (p->next == p) { ERTS_TW_ASSERT(tiw->sentinel.next == &tiw->sentinel); ERTS_TW_ASSERT(tiw->sentinel.prev == &tiw->sentinel); @@ -463,18 +719,21 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) while (1) { - if (p->timeout_pos > bump_to) { - /* Very unusual case... */ - ++yield_count; - insert_timer_into_slot(tiw, tiw_pos_ix, p); - } - else { - /* Normal case... */ - timeout_timer(p); - tiw->nto--; - } - - restart_yielded_slot: + ERTS_TW_ASSERT(ERTS_TW_SOON_WHEEL_FIRST_SLOT <= p->slot + && p->slot < ERTS_TW_SOON_WHEEL_END_SLOT); + tiw->soon.nto--; + if (p->timeout_pos <= bump_to) { + timeout_timer(p); + tiw->nto--; + yield_count -= ERTS_TW_COST_TIMEOUT; + } + else { + /* uncommon case */ + insert_timer_into_slot(tiw, tiw_pos_ix, p); + yield_count -= ERTS_TW_COST_SLOT_MOVE; + } + + restart_yielded_soon_slot: p = tiw->sentinel.next; if (p == &tiw->sentinel) { @@ -482,12 +741,11 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) break; } - if (--yield_count <= 0) { + if (yield_count <= 0) { tiw->true_next_timeout_time = 1; - tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(old_pos); + tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to); tiw->yield_slot = tiw_pos_ix; tiw->yield_slots_left = slots; - tiw->yield_start_pos = old_pos; ERTS_MSACC_POP_STATE_M_X(); return; /* Yield! */ } @@ -496,16 +754,22 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) p->next->prev = &tiw->sentinel; } } - tiw_pos_ix++; - if (tiw_pos_ix == ERTS_TIW_SIZE) - tiw_pos_ix = 0; - slots--; + + tiw_pos_ix++; + if (tiw_pos_ix == ERTS_TW_SOON_WHEEL_END_SLOT) + tiw_pos_ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT; + slots--; } + + if (ERTS_TW_BUMP_LATER_WHEEL(tiw)) { + restart_yielded_later_slot: + if (bump_later_wheel(tiw, &yield_count)) + return; /* Yield! */ + } } } while (yielded_slot_restarted); - tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE; tiw->true_next_timeout_time = 0; tiw->next_timeout_time = curr_time + ERTS_MONOTONIC_DAY; @@ -514,6 +778,119 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time) ERTS_MSACC_POP_STATE_M_X(); } +static int +bump_later_wheel(ErtsTimerWheel *tiw, int *ycount_p) +{ + ErtsMonotonicTime cpos = tiw->pos; + ErtsMonotonicTime later_pos = tiw->later.pos; + int ycount = *ycount_p; + int slots, fslot; + + ERTS_HARD_DBG_CHK_WHEELS(tiw, 0); + + if (tiw->yield_slot >= ERTS_TW_LATER_WHEEL_FIRST_SLOT) { + fslot = tiw->yield_slot; + slots = tiw->yield_slots_left; + ASSERT(0 <= slots && slots <= ERTS_TW_LATER_WHEEL_SIZE); + tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE; + goto restart_yielded_slot; + } + else { + ErtsMonotonicTime tmp_slots = cpos; + tmp_slots += ERTS_TW_LATER_WHEEL_SLOT_SIZE; + tmp_slots -= later_pos; + tmp_slots /= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + if (tmp_slots < ERTS_TW_LATER_WHEEL_SIZE) + slots = (int) tmp_slots; + else + slots = ERTS_TW_LATER_WHEEL_SIZE; + } + + while (slots >= 0) { + ErtsTWheelTimer *p; + + fslot = later_slot(later_pos); + + ycount -= ERTS_TW_COST_SLOT; + + p = tiw->w[fslot]; + + if (p) { + + if (p->next == p) { + ERTS_TW_ASSERT(tiw->sentinel.next == &tiw->sentinel); + ERTS_TW_ASSERT(tiw->sentinel.prev == &tiw->sentinel); + } + else { + tiw->sentinel.next = p->next; + tiw->sentinel.prev = p->prev; + tiw->sentinel.next->prev = &tiw->sentinel; + tiw->sentinel.prev->next = &tiw->sentinel; + } + tiw->w[fslot] = NULL; + + while (1) { + ErtsMonotonicTime tpos = p->timeout_pos; + + ERTS_TW_ASSERT(tpos >= later_pos); + ERTS_TW_ASSERT(p->slot == fslot); + + if (tpos >= later_pos + ERTS_TW_LATER_WHEEL_SLOT_SIZE) { + /* keep in later slot; very uncommon... */ + insert_timer_into_slot(tiw, fslot, p); + ycount -= ERTS_TW_COST_SLOT_MOVE; + } + else { + ERTS_TW_ASSERT(tpos < cpos + ERTS_TW_SOON_WHEEL_SIZE); + if (tpos > cpos) { + /* move into soon wheel */ + insert_timer_into_slot(tiw, soon_slot(tpos), p); + ycount -= ERTS_TW_COST_SLOT_MOVE; + } + else { + /* trigger at once */ + timeout_timer(p); + tiw->nto--; + ycount -= ERTS_TW_COST_TIMEOUT; + } + } + + restart_yielded_slot: + + p = tiw->sentinel.next; + if (p == &tiw->sentinel) { + ERTS_TW_ASSERT(tiw->sentinel.prev == &tiw->sentinel); + break; + } + + 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; + ERTS_HARD_DBG_CHK_WHEELS(tiw, 0); + return 1; /* Yield! */ + } + + tiw->sentinel.next = p->next; + p->next->prev = &tiw->sentinel; + } + } + slots--; + later_pos += ERTS_TW_LATER_WHEEL_SLOT_SIZE; + } + + ERTS_HARD_DBG_CHK_WHEELS(tiw, 0); + + tiw->later.pos = later_pos; + + *ycount_p = ycount; + + return 0; +} + Uint erts_timer_wheel_memory_size(void) { @@ -524,11 +901,11 @@ ErtsTimerWheel * erts_create_timer_wheel(ErtsSchedulerData *esdp) { ErtsMonotonicTime mtime; - int i; + int i = ERTS_TW_SOON_WHEEL_FIRST_SLOT; ErtsTimerWheel *tiw; tiw = erts_alloc_permanent_cache_aligned(ERTS_ALC_T_TIMER_WHEEL, sizeof(ErtsTimerWheel)); - for(i = 0; i < ERTS_TIW_SIZE; i++) + for(; i < ERTS_TW_LATER_WHEEL_END_SLOT; i++) tiw->w[i] = NULL; mtime = erts_get_monotonic_time(esdp); @@ -537,6 +914,10 @@ erts_create_timer_wheel(ErtsSchedulerData *esdp) tiw->at_once.head = NULL; tiw->at_once.tail = NULL; tiw->at_once.nto = 0; + tiw->soon.nto = 0; + tiw->later.pos = tiw->pos; + tiw->later.pos &= ERTS_TW_LATER_WHEEL_POS_MASK; + tiw->later.pos += ERTS_TW_LATER_WHEEL_SLOT_SIZE; tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE; tiw->true_next_timeout_time = 0; tiw->next_timeout_time = mtime + ERTS_MONOTONIC_DAY; @@ -586,36 +967,40 @@ erts_twheel_set_timer(ErtsTimerWheel *tiw, ERTS_TW_ASSERT(p->slot == ERTS_TWHEEL_SLOT_INACTIVE); + tiw->nto++; if (timeout_pos <= tiw->pos) { - tiw->nto++; - tiw->at_once.nto++; - p->next = NULL; - p->prev = tiw->at_once.tail; - if (tiw->at_once.tail) { - ERTS_TW_ASSERT(tiw->at_once.head); - tiw->at_once.tail->next = p; - } - else { - ERTS_TW_ASSERT(!tiw->at_once.head); - tiw->at_once.head = p; - } - tiw->at_once.tail = p; - p->timeout_pos = tiw->pos; - p->slot = ERTS_TWHEEL_SLOT_AT_ONCE; + p->timeout_pos = tiw->pos; + insert_timer_into_at_once_list(tiw, p); timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(tiw->pos); } else { int slot; + p->timeout_pos = timeout_pos; + /* calculate slot */ - slot = (int) (timeout_pos & (ERTS_TIW_SIZE-1)); + if (timeout_pos < tiw->pos + ERTS_TW_SOON_WHEEL_SIZE) { + /* soon wheel */ + slot = soon_slot(timeout_pos); + } + else { + /* later wheel */ + slot = later_slot(timeout_pos); + + /* + * Next timeout due to this timeout + * should be in good time before the + * actual timeout (one later wheel slot + * size). This, in order to move it + * from the later wheel to the soon + * wheel. + */ + timeout_pos &= ERTS_TW_LATER_WHEEL_POS_MASK; + timeout_pos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + } insert_timer_into_slot(tiw, slot, p); - - tiw->nto++; - - timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos); - p->timeout_pos = timeout_pos; + timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos); } if (timeout_time < tiw->next_timeout_time) { @@ -631,6 +1016,7 @@ erts_twheel_cancel_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p) if (p->slot != ERTS_TWHEEL_SLOT_INACTIVE) { ERTS_MSACC_PUSH_AND_SET_STATE_M_X(ERTS_MSACC_STATE_TIMERS); remove_timer(tiw, p); + tiw->nto--; ERTS_MSACC_POP_STATE_M_X(); } } @@ -658,7 +1044,9 @@ erts_twheel_debug_foreach(ErtsTimerWheel *tiw, (*func)(arg, tmr->timeout_pos, tmr->arg); } - for (ix = 0; ix < ERTS_TIW_SIZE; ix++) { + for (ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT; + ix < ERTS_TW_LATER_WHEEL_END_SLOT; + ix++) { tmr = tiw->w[ix]; if (tmr) { do { @@ -670,36 +1058,92 @@ erts_twheel_debug_foreach(ErtsTimerWheel *tiw, } } -#ifdef ERTS_TW_DEBUG -void erts_p_slpq(void) +#ifdef ERTS_TW_HARD_DEBUG + +static void +hrd_dbg_check_wheels(ErtsTimerWheel *tiw, int check_min_tpos) { - erts_printf("Not yet implemented...\n"); -#if 0 - ErtsMonotonicTime current_time = erts_get_monotonic_time(NULL); - int i; - ErtsTWheelTimer* p; - - /* print the whole wheel, starting at the current position */ - erts_printf("\ncurrent time = %bps tiw_pos = %d tiw_nto %d\n", - current_time, tiw->pos, tiw->nto); - i = tiw->pos; - if (tiw->w[i] != NULL) { - erts_printf("%d:\n", i); - for(p = tiw->w[i]; p != NULL; p = p->next) { - erts_printf(" (timeout time %bps, slot %d)\n", - ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos), - p->slot); - } + int ix, soon_tmo, later_tmo, at_once_tmo; + ErtsMonotonicTime min_tpos; + + min_tpos = ERTS_MONOTONIC_TO_CLKTCKS(tiw->next_timeout_time); + + soon_tmo = 0; + for (ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT; + ix < ERTS_TW_SOON_WHEEL_END_SLOT; + ix++) { + ErtsTWheelTimer *p; + + p = tiw->w[ix]; + if (p) { + ErtsTWheelTimer *first = p; + do { + ErtsMonotonicTime tpos = p->timeout_pos; + ERTS_TW_ASSERT(p->slot == ix); + soon_tmo++; + ERTS_TW_ASSERT(ix == soon_slot(tpos)); + ERTS_TW_ASSERT(p->timeout_pos < tiw->pos + ERTS_TW_SOON_WHEEL_SIZE); + ERTS_TW_ASSERT(!check_min_tpos || tpos >= min_tpos); + ERTS_TW_ASSERT(p->next->prev == p); + p = p->next; + } while (p != first); + } } - for(i = ((i+1) & (ERTS_TIW_SIZE-1)); i != (tiw->pos & (ERTS_TIW_SIZE-1)); i = ((i+1) & (ERTS_TIW_SIZE-1))) { - if (tiw->w[i] != NULL) { - erts_printf("%d:\n", i); - for(p = tiw->w[i]; p != NULL; p = p->next) { - erts_printf(" (timeout time %bps, slot %d)\n", - ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos), p->slot); - } - } + + later_tmo = 0; + for (ix = ERTS_TW_LATER_WHEEL_FIRST_SLOT; + ix < ERTS_TW_LATER_WHEEL_END_SLOT; + ix++) { + ErtsTWheelTimer *p; + + p = tiw->w[ix]; + if (p) { + ErtsTWheelTimer *first = p; + do { + ErtsMonotonicTime tpos = p->timeout_pos; + ERTS_TW_ASSERT(p->slot == ix); + later_tmo++; + ERTS_TW_ASSERT(later_slot(tpos) == ix); + tpos &= ERTS_TW_LATER_WHEEL_POS_MASK; + tpos -= ERTS_TW_LATER_WHEEL_SLOT_SIZE; + ERTS_TW_ASSERT(!check_min_tpos || tpos >= min_tpos); + ERTS_TW_ASSERT(p->next->prev == p); + p = p->next; + } while (p != first); + } } -#endif + + if (tiw->yield_slot >= 0) { + ErtsTWheelTimer *p = tiw->sentinel.next; + while (p != &tiw->sentinel) { + ErtsMonotonicTime tpos = p->timeout_pos; + if (tiw->yield_slot >= ERTS_TW_SOON_WHEEL_SIZE) { + later_tmo++; + ERTS_TW_ASSERT(p->slot == later_slot(tpos)); + } + else { + soon_tmo++; + ERTS_TW_ASSERT(p->slot == (tpos & ERTS_TW_SOON_WHEEL_MASK)); + ERTS_TW_ASSERT(tpos < tiw->pos + ERTS_TW_SOON_WHEEL_SIZE); + } + p = p->next; + } + } + + at_once_tmo = 0; + if (tiw->at_once.head) { + ErtsTWheelTimer *p = tiw->at_once.head; + while (p) { + ErtsMonotonicTime tpos = p->timeout_pos; + at_once_tmo++; + ERTS_TW_ASSERT(tpos <= tiw->pos); + p = p->next; + } + } + + ERTS_TW_ASSERT(tiw->at_once.nto == at_once_tmo); + ERTS_TW_ASSERT(tiw->soon.nto == soon_tmo); + ERTS_TW_ASSERT(tiw->nto == soon_tmo + later_tmo + at_once_tmo); } -#endif /* ERTS_TW_DEBUG */ + +#endif |