1 files changed, 477 insertions, 323 deletions

diff --git a/erts/emulator/beam/time.c b/erts/emulator/beam/time.c
index 2fd8e0cf00..8bffdedb2b 100644
--- a/erts/emulator/beam/time.c
+++ b/erts/emulator/beam/time.c
@@ -76,6 +76,11 @@
 #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)
@@ -83,26 +88,25 @@
 #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.
-*/
+#if 0
+#  define ERTS_TW_DEBUG
+#endif
+#if defined(DEBUG) && !defined(ERTS_TW_DEBUG)
+#  define ERTS_TW_DEBUG
+#endif
 
-#ifdef SMALL_MEMORY
-#define TIW_SIZE 8192
+#undef ERTS_TW_ASSERT
+#if defined(ERTS_TW_DEBUG)
+#  define ERTS_TW_ASSERT(E) ERTS_ASSERT(E)
 #else
-#define TIW_SIZE 65536		/* timing wheel size (should be a power of 2) */
+#  define ERTS_TW_ASSERT(E) ((void) 1)
 #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 */
+#ifdef ERTS_TW_DEBUG
+#  define ERTS_TWHEEL_BUMP_YIELD_LIMIT 5
+#else
+#  define ERTS_TWHEEL_BUMP_YIELD_LIMIT 100
+#endif
 
 /* Actual interval time chosen by sys_init_time() */
 
@@ -114,209 +118,437 @@ 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)
+struct ErtsTimerWheel_ {
+    ErtsTWheelTimer *w[ERTS_TIW_SIZE];
+    ErtsMonotonicTime pos;
+    Uint nto;
+    struct {
+	ErtsTWheelTimer *head;
+	ErtsTWheelTimer *tail;
+	Uint nto;
+    } at_once;
+    int yield_slot;
+    int yield_slots_left;
+    int yield_start_pos;
+    ErtsTWheelTimer sentinel;
+    int true_next_timeout_time;
+    ErtsMonotonicTime next_timeout_time;
+};
+
+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 */
 {
-    return erts_smp_atomic32_read_acqb(&do_time);
-}
-
-static ERTS_INLINE erts_short_time_t do_time_update(void)
-{
-    return do_time_read();
-}
+    int start_ix, tiw_pos_ix;
+    ErtsTWheelTimer *p;
+    int true_min_timeout = 0;
+    ErtsMonotonicTime min_timeout, min_timeout_pos, slot_timeout_pos;
+
+    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 found_next;
+    }
 
-static ERTS_INLINE void do_time_init(void)
-{
-    erts_smp_atomic32_init_nob(&do_time, 0);
-}
+    slot_timeout_pos = min_timeout_pos = tiw->pos;
+    if (search_all)
+	min_timeout_pos += ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY);
+    else
+	min_timeout_pos = ERTS_MONOTONIC_TO_CLKTCKS(curr_time + max_search_time);
 
-/* get the time (in units of TIW_ITIME) to the next timeout,
-   or -1 if there are no timeouts                     */
+    start_ix = tiw_pos_ix = (int) (tiw->pos & (ERTS_TIW_SIZE-1));
 
-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;
+	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;
+		p = p->next;
+	    } while (p != end);
 	}
-	/* 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);
+
+	tiw_pos_ix++;
+	if (tiw_pos_ix == ERTS_TIW_SIZE)
+	    tiw_pos_ix = 0;
+    } while (start_ix != tiw_pos_ix);
+
+found_next:
+
+    min_timeout = ERTS_CLKTCKS_TO_MONOTONIC(min_timeout_pos);
+    tiw->next_timeout_time = min_timeout;
+    tiw->true_next_timeout_time = true_min_timeout;
+
+    return min_timeout;
 }
 
-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;
+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);
+    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;
+    }
+}
 
-    /* last */
-    if (!p->next) {
+static ERTS_INLINE void
+remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p)
+{
+    int slot = p->slot;
+    ERTS_TW_ASSERT(slot != ERTS_TWHEEL_SLOT_INACTIVE);
+
+    if (slot >= 0) {
+	/*
+	 * Timer in wheel or in circular
+	 * list of timers currently beeing
+	 * triggered (referred by sentinel).
+	 */
+	ERTS_TW_ASSERT(slot < ERTS_TIW_SIZE);
+
+	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;
+	}
+    }
+    else {
+	/* Timer in "at once" queue... */
+	ERTS_TW_ASSERT(slot == ERTS_TWHEEL_SLOT_AT_ONCE);
 	if (p->prev)
-	    p->prev->next = NULL;
-    } else {
-	p->next->prev = 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->next = NULL;
-    p->prev = NULL;
-    /* Make sure cancel callback isn't called */
-    p->active = 0;
-    tiw_nto--;
+    p->slot = ERTS_TWHEEL_SLOT_INACTIVE;
+
+    tiw->nto--;
 }
 
-/* Private export to erl_time_sup.c */
-erts_short_time_t erts_next_time(void)
+ErtsMonotonicTime
+erts_check_next_timeout_time(ErtsSchedulerData *esdp)
 {
-    erts_short_time_t ret;
+    ErtsTimerWheel *tiw = esdp->timer_wheel;
+    if (tiw->true_next_timeout_time)
+	return tiw->next_timeout_time;
+    return find_next_timeout(esdp, tiw, 1, 0, 0);
+}
 
-    erts_smp_mtx_lock(&tiw_lock);
-    (void)do_time_update();
-    ret = next_time_internal();
-    erts_smp_mtx_unlock(&tiw_lock);
-    return ret;
+#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 = (int) (tiw->pos & (ERTS_TIW_SIZE-1));
+    tmp = skip_to_pos - tiw->pos;
+    ERTS_TW_ASSERT(tmp >= 0);
+    if (tmp < (ErtsMonotonicTime) ERTS_TIW_SIZE)
+	slots = (int) tmp;
+    else
+	slots = ERTS_TIW_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_TIW_SIZE)
+	     ix = 0;
+	 slots--;
+    }
+}
+#endif
+
+static ERTS_INLINE void
+timeout_timer(ErtsTWheelTimer *p)
+{
+    ErlTimeoutProc timeout;
+    void *arg;
+    p->slot = ERTS_TWHEEL_SLOT_INACTIVE;
+    timeout = p->u.func.timeout;
+    arg = p->u.func.arg;
+    (*timeout)(arg);
+    ASSERT_NO_LOCKED_LOCKS;
 }
 
-static ERTS_INLINE void bump_timer_internal(erts_short_time_t dt) /* PRE: tiw_lock is write-locked */
+void
+erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
 {
-    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;
+    int tiw_pos_ix, slots, yielded_slot_restarted, yield_count;
+    ErtsMonotonicTime bump_to, tmp_slots, old_pos;
+
+    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 >= 0) {
+	yielded_slot_restarted = 1;
+	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;
     }
 
-    /* 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;
+    do {
+
+	yielded_slot_restarted = 0;
+
+	bump_to = ERTS_MONOTONIC_TO_CLKTCKS(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);
+		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;
+		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(old_pos);
+		    return;
 		}
 
-		/* Remove from list */
-		remove_timer(p);
-		*timeout_tail = p;	/* Insert in timeout queue */
-		timeout_tail = &p->next;
+		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);
+
+		p = tiw->at_once.head;
 	    }
-	    else {
-		/* no timeout, just decrease counter */
-		p->count -= count;
-		prev = &p->next;
+
+	    if (tiw->pos >= bump_to)
+		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;
+		}
+	    }
+
+	    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;
+
+	    tiw->pos = bump_to;
+
+	    while (slots > 0) {
+
+		p = tiw->w[tiw_pos_ix];
+		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[tiw_pos_ix] = NULL;
+
+		    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:
+
+			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(old_pos);
+			    tiw->yield_slot = tiw_pos_ix;
+			    tiw->yield_slots_left = slots;
+			    tiw->yield_start_pos = old_pos;
+			    return; /* Yield! */
+			}
+
+			tiw->sentinel.next = p->next;
+			p->next->prev = &tiw->sentinel;
+		    }
+		}
+		tiw_pos_ix++;
+		if (tiw_pos_ix == ERTS_TIW_SIZE)
+		    tiw_pos_ix = 0;
+		slots--;
 	    }
 	}
-	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);
+    } 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;
+
+    /* Search at most two seconds ahead... */
+    (void) find_next_timeout(NULL, tiw, 0, curr_time, ERTS_SEC_TO_MONOTONIC(2));
 }
 
 Uint
 erts_timer_wheel_memory_size(void)
 {
-    return (Uint) TIW_SIZE * sizeof(ErlTimer*);
+    return sizeof(ErtsTimerWheel)*erts_no_schedulers;
 }
 
+ErtsTimerWheel *
+erts_create_timer_wheel(ErtsSchedulerData *esdp)
+{
+    ErtsMonotonicTime mtime;
+    int i;
+    ErtsTimerWheel *tiw;
+    tiw = erts_alloc_permanent_cache_aligned(ERTS_ALC_T_TIMER_WHEEL,
+					     sizeof(ErtsTimerWheel));
+    for(i = 0; i < ERTS_TIW_SIZE; 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->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;
+    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(void)
+erts_init_time(int time_correction, ErtsTimeWarpMode time_warp_mode)
 {
-    int i, itime;
+    int itime;
 
     /* system dependent init; must be done before do_time_init()
        if timer thread is enabled */
-    itime = erts_init_time_sup();
+    itime = erts_init_time_sup(time_correction, time_warp_mode);
 #ifdef TIW_ITIME_IS_CONSTANT 
     if (itime != TIW_ITIME) {
 	erl_exit(ERTS_ABORT_EXIT, "timer resolution mismatch %d != %d", itime, TIW_ITIME);
@@ -324,182 +556,104 @@ erts_init_time(void)
 #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)
+void
+erts_twheel_set_timer(ErtsTimerWheel *tiw,
+		      ErtsTWheelTimer *p, ErlTimeoutProc timeout,
+		      ErlCancelProc cancel, void *arg,
+		      ErtsMonotonicTime timeout_pos)
 {
-    Uint tm;
-    Uint64 ticks;
+    ErtsMonotonicTime timeout_time;
 
-    /* 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;
+    p->u.func.timeout = timeout;
+    p->u.func.cancel = cancel;
+    p->u.func.arg = arg;
 
-    /* 
-     * 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;
-    }
+    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;
+	timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(tiw->pos);
+    }
+    else {
+	int slot;
 
-void
-erts_set_timer(ErlTimer* p, ErlTimeoutProc timeout, ErlCancelProc cancel,
-	      void* arg, Uint t)
-{
+	/* calculate slot */
+	slot = (int) (timeout_pos & (ERTS_TIW_SIZE-1));
 
-    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
-}
+	insert_timer_into_slot(tiw, slot, p);
 
-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;
-    }
+	tiw->nto++;
 
-    /* is it the 'min' timer, remove min */
-    if (p == tiw_min_ptr) {
-	tiw_min_ptr = NULL;
-	tiw_min     = 0;
+	timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos);
+	p->timeout_pos = timeout_pos;
     }
 
-    remove_timer(p);
-    p->slot = p->count = 0;
-
-    if (p->cancel != NULL) {
-	erts_smp_mtx_unlock(&tiw_lock);
-	(*p->cancel)(p->arg);
-	return;
+    if (timeout_time < tiw->next_timeout_time) {
+	tiw->true_next_timeout_time = 1;
+	tiw->next_timeout_time = timeout_time;
     }
-    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)
+void
+erts_twheel_cancel_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *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 != ERTS_TWHEEL_SLOT_INACTIVE) {
+	ErlCancelProc cancel;
+	void *arg;
+	remove_timer(tiw, p);
+	cancel = p->u.func.cancel;
+	arg = p->u.func.arg;
+	if (cancel)
+	    (*cancel)(arg);
     }
-
-    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
+#ifdef ERTS_TW_DEBUG
 void erts_p_slpq(void)
 {
+    erts_printf("Not yet implemented...\n");
+#if 0
+    ErtsMonotonicTime current_time = erts_get_monotonic_time(NULL);
     int i;
-    ErlTimer* p;
+    ErtsTWheelTimer* 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("\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[i]; p != NULL; p = p->next) {
-	    erts_printf(" (count %d, slot %d)\n",
-			p->count, p->slot);
+	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);
 	}
     }
-    for(i = (i+1)%TIW_SIZE; i != tiw_pos; i = (i+1)%TIW_SIZE) {
-	if (tiw[i] != NULL) {
+    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[i]; p != NULL; p = p->next) {
-		erts_printf(" (count %d, slot %d)\n",
-			    p->count, p->slot);
+	    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);
 	    }
 	}
     }
-
-    erts_smp_mtx_unlock(&tiw_lock);
+#endif
 }
-#endif /* DEBUG */
+#endif /* ERTS_TW_DEBUG */