/* * %CopyrightBegin% * * Copyright Ericsson AB 1996-2009. 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() */ static int itime; /* Constant after init */ erts_smp_atomic_t do_time; /* set at clock interrupt */ static ERTS_INLINE erts_aint_t do_time_read(void) { return erts_smp_atomic_read(&do_time); } static ERTS_INLINE erts_aint_t do_time_update(void) { return do_time_read(); } static ERTS_INLINE void do_time_init(void) { erts_smp_atomic_init(&do_time, 0L); } /* get the time (in units of itime) to the next timeout, or -1 if there are no timeouts */ static erts_aint_t next_time_internal(void) /* PRE: tiw_lock taken by caller */ { int i, tm, nto; unsigned int min; ErlTimer* p; erts_aint_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 = (unsigned int) -1; /* max unsigned int */ 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(); return ((min >= dt) ? (min - dt) : 0); } 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_aint_t erts_next_time(void) { erts_aint_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_aint_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_aint_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; /* system dependent init; must be done before do_time_init() if timer thread is enabled */ itime = erts_init_time_sup(); 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 + itime - 1) / 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) LONG_MAX) erts_sys_schedule_interrupt_timed(1, (long) 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_aint_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 * itime; } #ifdef DEBUG void erts_p_slpq() { 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 */