/*
* %CopyrightBegin%
*
* Copyright Ericsson AB 1996-2016. All Rights Reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* %CopyrightEnd%
*/
/*
* 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.
*
* When a timer is set, it is determined at what Erlang monotonic
* time, in clock ticks, it should be triggered.
*
* 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.
*
*
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#include "sys.h"
#include "erl_vm.h"
#include "global.h"
#define ERTS_WANT_TIMER_WHEEL_API
#include "erl_time.h"
#define ERTS_MONOTONIC_DAY ERTS_SEC_TO_MONOTONIC(60*60*24)
#define ERTS_CLKTCKS_DAY ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY)
#ifdef ERTS_ENABLE_LOCK_CHECK
#define ASSERT_NO_LOCKED_LOCKS erts_lc_check_exact(NULL, 0)
#else
#define ASSERT_NO_LOCKED_LOCKS
#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)
# define ERTS_TW_DEBUG
#endif
#undef ERTS_TW_ASSERT
#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 500
#else
# 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() */
#if SYS_CLOCK_RESOLUTION == 1
# define TIW_ITIME 1
# define TIW_ITIME_IS_CONSTANT
#else
static int tiw_itime; /* Constant after init */
# define TIW_ITIME tiw_itime
#endif
struct ErtsTimerWheel_ {
ErtsTWheelTimer *w[ERTS_TW_SOON_WHEEL_SIZE + ERTS_TW_LATER_WHEEL_SIZE];
ErtsMonotonicTime pos;
Uint nto;
struct {
ErtsTWheelTimer *head;
ErtsTWheelTimer *tail;
Uint nto;
} at_once;
struct {
Uint nto;
} soon;
struct {
ErtsMonotonicTime pos;
} later;
int yield_slot;
int yield_slots_left;
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,
int search_all,
ErtsMonotonicTime curr_time, /* When !search_all */
ErtsMonotonicTime max_search_time) /* When !search_all */
{
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;
else {
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_DAY);
goto done;
}
if (search_all)
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);
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;
}
}
}
}
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 (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);
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(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;
p->next = p;
p->prev = p;
}
else {
ErtsTWheelTimer *next, *prev;
next = tiw->w[slot];
prev = next->prev;
p->next = next;
p->prev = prev;
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
remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p)
{
int slot = p->slot;
ERTS_TW_ASSERT(slot != ERTS_TWHEEL_SLOT_INACTIVE);
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_TW_LATER_WHEEL_END_SLOT);
if (p->next == p) {
ERTS_TW_ASSERT(tiw->w[slot] == p);
tiw->w[slot] = NULL;
}
else {
if (tiw->w[slot] == p)
tiw->w[slot] = p->next;
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... */
ERTS_TW_ASSERT(slot == ERTS_TWHEEL_SLOT_AT_ONCE);
if (p->prev)
p->prev->next = p->next;
else {
ERTS_TW_ASSERT(tiw->at_once.head == p);
tiw->at_once.head = p->next;
}
if (p->next)
p->next->prev = p->prev;
else {
ERTS_TW_ASSERT(tiw->at_once.tail == p);
tiw->at_once.tail = p->prev;
}
ERTS_TW_ASSERT(tiw->at_once.nto > 0);
tiw->at_once.nto--;
}
p->slot = ERTS_TWHEEL_SLOT_INACTIVE;
}
ErtsMonotonicTime
erts_check_next_timeout_time(ErtsSchedulerData *esdp)
{
ErtsTimerWheel *tiw = esdp->timer_wheel;
ErtsMonotonicTime time;
ERTS_MSACC_DECLARE_CACHE_X();
if (tiw->true_next_timeout_time)
return tiw->next_timeout_time;
ERTS_MSACC_PUSH_AND_SET_STATE_CACHED_X(ERTS_MSACC_STATE_TIMERS);
time = find_next_timeout(esdp, tiw, 1, 0, 0);
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;
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)
{
ErlTimeoutProc timeout;
void *arg;
p->slot = ERTS_TWHEEL_SLOT_INACTIVE;
timeout = p->timeout;
arg = p->arg;
(*timeout)(arg);
ASSERT_NO_LOCKED_LOCKS;
}
void
erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
{
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;
/*
* In order to be fair we always continue with work
* where we left off when restarting after a yield.
*/
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;
ASSERT(0 <= slots && slots <= ERTS_TW_SOON_WHEEL_SIZE);
tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE;
goto restart_yielded_soon_slot;
}
do {
yielded_slot_restarted = 0;
bump_to = ERTS_MONOTONIC_TO_CLKTCKS(curr_time);
while (1) {
ErtsTWheelTimer *p;
if (tiw->nto == 0) {
empty_wheel:
ERTS_DBG_CHK_SAFE_TO_SKIP_TO(tiw, bump_to);
tiw->true_next_timeout_time = 0;
tiw->next_timeout_time = curr_time + ERTS_MONOTONIC_DAY;
tiw->pos = bump_to;
tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE;
ERTS_MSACC_POP_STATE_M_X();
return;
}
p = tiw->at_once.head;
while (p) {
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(bump_to);
ERTS_MSACC_POP_STATE_M_X();
return;
}
ERTS_TW_ASSERT(tiw->nto > 0);
ERTS_TW_ASSERT(tiw->at_once.nto > 0);
tiw->nto--;
tiw->at_once.nto--;
tiw->at_once.head = p->next;
if (p->next)
p->next->prev = NULL;
else
tiw->at_once.tail = NULL;
timeout_timer(p);
yield_count -= ERTS_TW_COST_TIMEOUT;
p = tiw->at_once.head;
}
if (tiw->pos >= bump_to) {
ERTS_MSACC_POP_STATE_M_X();
break;
}
if (tiw->nto == 0)
goto empty_wheel;
if (tiw->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(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);
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;
}
}
{
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;
/* 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);
}
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[tiw_pos_ix] = NULL;
while (1) {
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) {
ERTS_TW_ASSERT(tiw->sentinel.prev == &tiw->sentinel);
break;
}
if (yield_count <= 0) {
tiw->true_next_timeout_time = 1;
tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to);
tiw->yield_slot = tiw_pos_ix;
tiw->yield_slots_left = slots;
ERTS_MSACC_POP_STATE_M_X();
return; /* Yield! */
}
tiw->sentinel.next = p->next;
p->next->prev = &tiw->sentinel;
}
}
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->true_next_timeout_time = 0;
tiw->next_timeout_time = curr_time + ERTS_MONOTONIC_DAY;
/* Search at most two seconds ahead... */
(void) find_next_timeout(NULL, tiw, 0, curr_time, ERTS_SEC_TO_MONOTONIC(2));
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)
{
return sizeof(ErtsTimerWheel)*erts_no_schedulers;
}
ErtsTimerWheel *
erts_create_timer_wheel(ErtsSchedulerData *esdp)
{
ErtsMonotonicTime mtime;
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 < ERTS_TW_LATER_WHEEL_END_SLOT; i++)
tiw->w[i] = NULL;
mtime = erts_get_monotonic_time(esdp);
tiw->pos = ERTS_MONOTONIC_TO_CLKTCKS(mtime);
tiw->nto = 0;
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;
tiw->sentinel.next = &tiw->sentinel;
tiw->sentinel.prev = &tiw->sentinel;
tiw->sentinel.timeout = NULL;
tiw->sentinel.arg = NULL;
return tiw;
}
ErtsNextTimeoutRef
erts_get_next_timeout_reference(ErtsTimerWheel *tiw)
{
return (ErtsNextTimeoutRef) &tiw->next_timeout_time;
}
/* this routine links the time cells into a free list at the start
and sets the time queue as empty */
void
erts_init_time(int time_correction, ErtsTimeWarpMode time_warp_mode)
{
int itime;
/* system dependent init; must be done before do_time_init()
if timer thread is enabled */
itime = erts_init_time_sup(time_correction, time_warp_mode);
#ifdef TIW_ITIME_IS_CONSTANT
if (itime != TIW_ITIME) {
erts_exit(ERTS_ABORT_EXIT, "timer resolution mismatch %d != %d", itime, TIW_ITIME);
}
#else
tiw_itime = itime;
#endif
}
void
erts_twheel_set_timer(ErtsTimerWheel *tiw,
ErtsTWheelTimer *p, ErlTimeoutProc timeout,
void *arg, ErtsMonotonicTime timeout_pos)
{
ErtsMonotonicTime timeout_time;
ERTS_MSACC_PUSH_AND_SET_STATE_M_X(ERTS_MSACC_STATE_TIMERS);
p->timeout = timeout;
p->arg = arg;
ERTS_TW_ASSERT(p->slot == ERTS_TWHEEL_SLOT_INACTIVE);
tiw->nto++;
if (timeout_pos <= tiw->pos) {
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 */
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);
timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos);
}
if (timeout_time < tiw->next_timeout_time) {
tiw->true_next_timeout_time = 1;
tiw->next_timeout_time = timeout_time;
}
ERTS_MSACC_POP_STATE_M_X();
}
void
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();
}
}
void
erts_twheel_debug_foreach(ErtsTimerWheel *tiw,
void (*tclbk)(void *),
void (*func)(void *,
ErtsMonotonicTime,
void *),
void *arg)
{
ErtsTWheelTimer *tmr;
int ix;
tmr = tiw->sentinel.next;
while (tmr != &tiw->sentinel) {
if (tmr->timeout == tclbk)
(*func)(arg, tmr->timeout_pos, tmr->arg);
tmr = tmr->next;
}
for (tmr = tiw->at_once.head; tmr; tmr = tmr->next) {
if (tmr->timeout == tclbk)
(*func)(arg, tmr->timeout_pos, tmr->arg);
}
for (ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT;
ix < ERTS_TW_LATER_WHEEL_END_SLOT;
ix++) {
tmr = tiw->w[ix];
if (tmr) {
do {
if (tmr->timeout == tclbk)
(*func)(arg, tmr->timeout_pos, tmr->arg);
tmr = tmr->next;
} while (tmr != tiw->w[ix]);
}
}
}
#ifdef ERTS_TW_HARD_DEBUG
static void
hrd_dbg_check_wheels(ErtsTimerWheel *tiw, int check_min_tpos)
{
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);
}
}
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);
}
}
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