/*
* %CopyrightBegin%
*
* Copyright Ericsson AB 1996-2011. All Rights Reserved.
*
* The contents of this file are subject to the Erlang Public License,
* Version 1.1, (the "License"); you may not use this file except in
* compliance with the License. You should have received a copy of the
* Erlang Public License along with this software. If not, it can be
* retrieved online at http://www.erlang.org/.
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
* the License for the specific language governing rights and limitations
* under the License.
*
* %CopyrightEnd%
*/
/*
* TIMING WHEEL
*
* 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.
*
* 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 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
# include "config.h"
#endif
#include "sys.h"
#include "erl_vm.h"
#include "global.h"
#ifdef ERTS_ENABLE_LOCK_CHECK
#define ASSERT_NO_LOCKED_LOCKS erts_lc_check_exact(NULL, 0)
#else
#define ASSERT_NO_LOCKED_LOCKS
#endif
static erts_smp_mtx_t tiw_lock;
/* BEGIN tiw_lock protected variables
**
** The individual timer cells in tiw are also protected by the same mutex.
*/
#ifdef SMALL_MEMORY
#define TIW_SIZE 8192
#else
#define TIW_SIZE 65536 /* timing wheel size (should be a power of 2) */
#endif
static ErlTimer** tiw; /* the timing wheel, allocated in init_time() */
static Uint 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 */
/* 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
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 ERTS_INLINE erts_short_time_t do_time_update(void)
{
return do_time_read();
}
static ERTS_INLINE void do_time_init(void)
{
erts_smp_atomic32_init_nob(&do_time, 0);
}
/* 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 */
{
int i, tm, nto;
Uint32 min;
ErlTimer* p;
erts_short_time_t dt;
if (tiw_nto == 0)
return -1; /* no timeouts in wheel */
if (tiw_min_ptr) {
min = tiw_min;
dt = do_time_read();
return ((min >= dt) ? (min - dt) : 0);
}
/* start going through wheel to find next timeout */
tm = nto = 0;
min = (Uint32) -1; /* max Uint32 */
i = tiw_pos;
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;
}
}
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);
}
static void remove_timer(ErlTimer *p) {
/* first */
if (!p->prev) {
tiw[p->slot] = p->next;
if(p->next)
p->next->prev = NULL;
} else {
p->prev->next = p->next;
}
/* last */
if (!p->next) {
if (p->prev)
p->prev->next = NULL;
} else {
p->next->prev = p->prev;
}
p->next = NULL;
p->prev = NULL;
/* Make sure cancel callback isn't called */
p->active = 0;
tiw_nto--;
}
/* Private export to erl_time_sup.c */
erts_short_time_t erts_next_time(void)
{
erts_short_time_t ret;
erts_smp_mtx_lock(&tiw_lock);
(void)do_time_update();
ret = next_time_internal();
erts_smp_mtx_unlock(&tiw_lock);
return ret;
}
static ERTS_INLINE void bump_timer_internal(erts_short_time_t dt) /* PRE: tiw_lock is write-locked */
{
Uint keep_pos;
Uint count;
ErlTimer *p, **prev, *timeout_head, **timeout_tail;
Uint dtime = (Uint) dt;
/* no need to bump the position if there aren't any timeouts */
if (tiw_nto == 0) {
erts_smp_mtx_unlock(&tiw_lock);
return;
}
/* 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;
}
/* 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;
}
}
tiw_pos = (tiw_pos + 1) % TIW_SIZE;
dtime--;
}
tiw_pos = keep_pos;
if (tiw_min_ptr)
tiw_min -= dt;
erts_smp_mtx_unlock(&tiw_lock);
/* Call timedout timers callbacks */
while (timeout_head) {
p = timeout_head;
timeout_head = p->next;
/* Here comes hairy use of the timer fields!
* They are reset without having the lock.
* It is assumed that no code but this will
* accesses any field until the ->timeout
* callback is called.
*/
p->next = NULL;
p->prev = NULL;
p->slot = 0;
(*p->timeout)(p->arg);
}
}
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)
{
return (Uint) TIW_SIZE * sizeof(ErlTimer*);
}
/* 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)
{
int i, itime;
/* system dependent init; must be done before do_time_init()
if timer thread is enabled */
itime = erts_init_time_sup();
#ifdef TIW_ITIME_IS_CONSTANT
if (itime != TIW_ITIME) {
erl_exit(ERTS_ABORT_EXIT, "timer resolution mismatch %d != %d", itime, TIW_ITIME);
}
#else
tiw_itime = itime;
#endif
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;
}
/*
** Insert a process into the time queue, with a timeout 't'
*/
static void
insert_timer(ErlTimer* p, Uint t)
{
Uint tm;
Uint64 ticks;
/* 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;
/*
* 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);
/* 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 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;
}
tiw_nto++;
}
void
erts_set_timer(ErlTimer* p, ErlTimeoutProc timeout, ErlCancelProc cancel,
void* arg, Uint t)
{
erts_deliver_time();
erts_smp_mtx_lock(&tiw_lock);
if (p->active) { /* XXX assert ? */
erts_smp_mtx_unlock(&tiw_lock);
return;
}
p->timeout = timeout;
p->cancel = cancel;
p->arg = arg;
p->active = 1;
insert_timer(p, 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);
#endif
}
void
erts_cancel_timer(ErlTimer* p)
{
erts_smp_mtx_lock(&tiw_lock);
if (!p->active) { /* allow repeated cancel (drivers) */
erts_smp_mtx_unlock(&tiw_lock);
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;
if (p->cancel != NULL) {
erts_smp_mtx_unlock(&tiw_lock);
(*p->cancel)(p->arg);
return;
}
erts_smp_mtx_unlock(&tiw_lock);
}
/*
Returns the amount of time left in ms until the timer 'p' is triggered.
0 is returned if 'p' isn't active.
0 is returned also if the timer is overdue (i.e., would have triggered
immediately if it hadn't been cancelled).
*/
Uint
erts_time_left(ErlTimer *p)
{
Uint left;
erts_short_time_t dt;
erts_smp_mtx_lock(&tiw_lock);
if (!p->active) {
erts_smp_mtx_unlock(&tiw_lock);
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;
erts_smp_mtx_unlock(&tiw_lock);
return (Uint) left * TIW_ITIME;
}
#ifdef DEBUG
void erts_p_slpq(void)
{
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);
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);
}
}
for(i = (i+1)%TIW_SIZE; i != tiw_pos; i = (i+1)%TIW_SIZE) {
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_smp_mtx_unlock(&tiw_lock);
}
#endif /* DEBUG */
