aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/time.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/time.c')
-rw-r--r--erts/emulator/beam/time.c571
1 files changed, 571 insertions, 0 deletions
diff --git a/erts/emulator/beam/time.c b/erts/emulator/beam/time.c
new file mode 100644
index 0000000000..a07d6a5327
--- /dev/null
+++ b/erts/emulator/beam/time.c
@@ -0,0 +1,571 @@
+/*
+ * %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
+
+
+#if defined(ERTS_TIMER_THREAD) || 1
+/* I don't yet know why, but using a mutex instead of a spinlock
+ or spin-based rwlock avoids excessive delays at startup. */
+static erts_smp_rwmtx_t tiw_lock;
+#define tiw_read_lock() erts_smp_rwmtx_rlock(&tiw_lock)
+#define tiw_read_unlock() erts_smp_rwmtx_runlock(&tiw_lock)
+#define tiw_write_lock() erts_smp_rwmtx_rwlock(&tiw_lock)
+#define tiw_write_unlock() erts_smp_rwmtx_rwunlock(&tiw_lock)
+#define tiw_init_lock() erts_smp_rwmtx_init(&tiw_lock, "timer_wheel")
+#else
+static erts_smp_rwlock_t tiw_lock;
+#define tiw_read_lock() erts_smp_read_lock(&tiw_lock)
+#define tiw_read_unlock() erts_smp_read_unlock(&tiw_lock)
+#define tiw_write_lock() erts_smp_write_lock(&tiw_lock)
+#define tiw_write_unlock() erts_smp_write_unlock(&tiw_lock)
+#define tiw_init_lock() erts_smp_rwlock_init(&tiw_lock, "timer_wheel")
+#endif
+
+/* 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 */
+
+/* END tiw_lock protected variables */
+
+/* Actual interval time chosen by sys_init_time() */
+static int itime; /* Constant after init */
+
+#if defined(ERTS_TIMER_THREAD)
+static SysTimeval time_start; /* start of current time interval */
+static long ticks_end; /* time_start+ticks_end == time_wakeup */
+static long ticks_latest; /* delta from time_start at latest time update*/
+
+static ERTS_INLINE long time_gettimeofday(SysTimeval *now)
+{
+ long elapsed;
+
+ erts_get_timeval(now);
+ now->tv_usec = 1000 * (now->tv_usec / 1000); /* ms resolution */
+ elapsed = (1000 * (now->tv_sec - time_start.tv_sec) +
+ (now->tv_usec - time_start.tv_usec) / 1000);
+ // elapsed /= CLOCK_RESOLUTION;
+ return elapsed;
+}
+
+static long do_time_update(void)
+{
+ SysTimeval now;
+ long elapsed;
+
+ elapsed = time_gettimeofday(&now);
+ ticks_latest = elapsed;
+ return elapsed;
+}
+
+static ERTS_INLINE long do_time_read(void)
+{
+ return ticks_latest;
+}
+
+static long do_time_reset(void)
+{
+ SysTimeval now;
+ long elapsed;
+
+ elapsed = time_gettimeofday(&now);
+ time_start = now;
+ ticks_end = LONG_MAX;
+ ticks_latest = 0;
+ return elapsed;
+}
+
+static ERTS_INLINE void do_time_init(void)
+{
+ (void)do_time_reset();
+}
+
+#else
+erts_smp_atomic_t do_time; /* set at clock interrupt */
+static ERTS_INLINE long do_time_read(void) { return erts_smp_atomic_read(&do_time); }
+static ERTS_INLINE long do_time_update(void) { return do_time_read(); }
+static ERTS_INLINE void do_time_init(void) { erts_smp_atomic_init(&do_time, 0L); }
+#endif
+
+/* get the time (in units of itime) to the next timeout,
+ or -1 if there are no timeouts */
+
+static int next_time_internal(void) /* PRE: tiw_lock taken by caller */
+{
+ int i, tm, nto;
+ unsigned int min;
+ ErlTimer* p;
+ long dt;
+
+ if (tiw_nto == 0)
+ return -1; /* no timeouts in wheel */
+
+ /* 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();
+ 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;
+ }
+ 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);
+}
+
+#if !defined(ERTS_TIMER_THREAD)
+/* Private export to erl_time_sup.c */
+int next_time(void)
+{
+ int ret;
+
+ tiw_write_lock();
+ (void)do_time_update();
+ ret = next_time_internal();
+ tiw_write_unlock();
+ return ret;
+}
+#endif
+
+static ERTS_INLINE void bump_timer_internal(long dt) /* PRE: tiw_lock is write-locked */
+{
+ Uint keep_pos;
+ Uint count;
+ ErlTimer *p, **prev, *timeout_head, **timeout_tail;
+ Uint dtime = (unsigned long)dt;
+
+ /* no need to bump the position if there aren't any timeouts */
+ if (tiw_nto == 0) {
+ tiw_write_unlock();
+ 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) {
+ if (p->count < count) { /* we have a timeout */
+ *prev = p->next; /* Remove from list */
+ tiw_nto--;
+ p->next = NULL;
+ p->active = 0; /* Make sure cancel callback
+ isn't called */
+ *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;
+
+ tiw_write_unlock();
+
+ /* 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->slot = 0;
+ (*p->timeout)(p->arg);
+ }
+}
+
+#if defined(ERTS_TIMER_THREAD)
+static void timer_thread_bump_timer(void)
+{
+ tiw_write_lock();
+ bump_timer_internal(do_time_reset());
+}
+#else
+void bump_timer(long dt) /* dt is value from do_time */
+{
+ tiw_write_lock();
+ bump_timer_internal(dt);
+}
+#endif
+
+Uint
+erts_timer_wheel_memory_size(void)
+{
+ return (Uint) TIW_SIZE * sizeof(ErlTimer*);
+}
+
+#if defined(ERTS_TIMER_THREAD)
+static struct erts_iwait *timer_thread_iwait;
+
+static int timer_thread_setup_delay(SysTimeval *rem_time)
+{
+ long elapsed;
+ int ticks;
+
+ tiw_write_lock();
+ elapsed = do_time_update();
+ ticks = next_time_internal();
+ if (ticks == -1) /* timer queue empty */
+ ticks = 100*1000*1000;
+ if (elapsed > ticks)
+ elapsed = ticks;
+ ticks -= elapsed;
+ //ticks *= CLOCK_RESOLUTION;
+ rem_time->tv_sec = ticks / 1000;
+ rem_time->tv_usec = 1000 * (ticks % 1000);
+ ticks_end = ticks;
+ tiw_write_unlock();
+ return ticks;
+}
+
+static void *timer_thread_start(void *ignore)
+{
+ SysTimeval delay;
+
+#ifdef ERTS_ENABLE_LOCK_CHECK
+ erts_lc_set_thread_name("timer");
+#endif
+ erts_register_blockable_thread();
+
+ for(;;) {
+ if (timer_thread_setup_delay(&delay)) {
+ erts_smp_activity_begin(ERTS_ACTIVITY_WAIT, NULL, NULL, NULL);
+ ASSERT_NO_LOCKED_LOCKS;
+ erts_iwait_wait(timer_thread_iwait, &delay);
+ ASSERT_NO_LOCKED_LOCKS;
+ erts_smp_activity_end(ERTS_ACTIVITY_WAIT, NULL, NULL, NULL);
+ }
+ else
+ erts_smp_chk_system_block(NULL, NULL, NULL);
+ timer_thread_bump_timer();
+ ASSERT_NO_LOCKED_LOCKS;
+ }
+ /*NOTREACHED*/
+ return NULL;
+}
+
+static ERTS_INLINE void timer_thread_post_insert(Uint ticks)
+{
+ if ((Sint)ticks < ticks_end)
+ erts_iwait_interrupt(timer_thread_iwait);
+}
+
+static void timer_thread_init(void)
+{
+ erts_thr_opts_t opts = ERTS_THR_OPTS_DEFAULT_INITER;
+ erts_tid_t tid;
+
+ opts->detached = 1;
+
+ timer_thread_iwait = erts_iwait_init();
+ erts_thr_create(&tid, timer_thread_start, NULL, &opts);
+}
+
+#else
+static ERTS_INLINE void timer_thread_post_insert(Uint ticks) { }
+static ERTS_INLINE void timer_thread_init(void) { }
+#endif
+
+/* this routine links the time cells into a free list at the start
+ and sets the time queue as empty */
+void
+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();
+
+ tiw_init_lock();
+
+ 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;
+
+ timer_thread_init();
+}
+
+/*
+** 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];
+ tiw[tm] = p;
+ tiw_nto++;
+
+ timer_thread_post_insert(ticks);
+}
+
+void
+erl_set_timer(ErlTimer* p, ErlTimeoutProc timeout, ErlCancelProc cancel,
+ void* arg, Uint t)
+{
+ erts_deliver_time();
+ tiw_write_lock();
+ if (p->active) { /* XXX assert ? */
+ tiw_write_unlock();
+ return;
+ }
+ p->timeout = timeout;
+ p->cancel = cancel;
+ p->arg = arg;
+ p->active = 1;
+ insert_timer(p, t);
+ tiw_write_unlock();
+#if defined(ERTS_SMP) && !defined(ERTS_TIMER_THREAD)
+ if (t <= (Uint) LONG_MAX)
+ erts_sys_schedule_interrupt_timed(1, (long) t);
+#endif
+}
+
+void
+erl_cancel_timer(ErlTimer* p)
+{
+ ErlTimer *tp;
+ ErlTimer **prev;
+
+ tiw_write_lock();
+ if (!p->active) { /* allow repeated cancel (drivers) */
+ tiw_write_unlock();
+ return;
+ }
+ /* find p in linked list at slot p->slot and remove it */
+ prev = &tiw[p->slot];
+ while ((tp = *prev) != NULL) {
+ if (tp == p) {
+ *prev = p->next; /* Remove from list */
+ tiw_nto--;
+ p->next = NULL;
+ p->slot = p->count = 0;
+ p->active = 0;
+ if (p->cancel != NULL) {
+ tiw_write_unlock();
+ (*p->cancel)(p->arg);
+ } else {
+ tiw_write_unlock();
+ }
+ return;
+ } else {
+ prev = &tp->next;
+ }
+ }
+ tiw_write_unlock();
+}
+
+/*
+ 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
+time_left(ErlTimer *p)
+{
+ Uint left;
+ long dt;
+
+ tiw_read_lock();
+
+ if (!p->active) {
+ tiw_read_unlock();
+ 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;
+
+ tiw_read_unlock();
+
+ return left * itime;
+}
+
+#ifdef DEBUG
+
+void p_slpq()
+{
+ int i;
+ ErlTimer* p;
+
+ tiw_read_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);
+ }
+ }
+ }
+
+ tiw_read_unlock();
+}
+
+#endif /* DEBUG */