aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/time.c
diff options
context:
space:
mode:
authorRickard Green <[email protected]>2017-02-06 20:39:02 +0100
committerRickard Green <[email protected]>2017-04-18 12:40:02 +0200
commit0981bfd7afee64c3c1f48db134d81e57c30e31c7 (patch)
tree665048fc25b4295a62a3f1363f95b1accfd130c3 /erts/emulator/beam/time.c
parentd37df80764c9c2e517d7c9a90291d75975a5e9bb (diff)
downloadotp-0981bfd7afee64c3c1f48db134d81e57c30e31c7.tar.gz
otp-0981bfd7afee64c3c1f48db134d81e57c30e31c7.tar.bz2
otp-0981bfd7afee64c3c1f48db134d81e57c30e31c7.zip
Timer wheel divided into a "soon wheel" and a "later wheel"
The old single wheel implementation handled about 65 seconds. The new dual wheel implementation handles more than 37 hours. The dual wheels have also been shrunk compared to the single wheel, so the total memory consumption for timer wheels have been cut in half.
Diffstat (limited to 'erts/emulator/beam/time.c')
-rw-r--r--erts/emulator/beam/time.c810
1 files changed, 627 insertions, 183 deletions
diff --git a/erts/emulator/beam/time.c b/erts/emulator/beam/time.c
index 53896be19e..7b5ff7b992 100644
--- a/erts/emulator/beam/time.c
+++ b/erts/emulator/beam/time.c
@@ -17,57 +17,124 @@
*
* %CopyrightEnd%
*/
+
/*
- * TIMING WHEEL
+ * 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.
*
- * 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.
+ * When a timer is set, it is determined at what Erlang monotonic
+ * time, in clock ticks, it should be triggered.
*
- * 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 '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.
*
- * 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
@@ -90,6 +157,10 @@
#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)
@@ -97,17 +168,48 @@
#endif
#undef ERTS_TW_ASSERT
-#if defined(ERTS_TW_DEBUG)
+#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 5
+# define ERTS_TWHEEL_BUMP_YIELD_LIMIT 500
#else
-# define ERTS_TWHEEL_BUMP_YIELD_LIMIT 100
+# 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() */
@@ -120,7 +222,7 @@ static int tiw_itime; /* Constant after init */
#endif
struct ErtsTimerWheel_ {
- ErtsTWheelTimer *w[ERTS_TIW_SIZE];
+ ErtsTWheelTimer *w[ERTS_TW_SOON_WHEEL_SIZE + ERTS_TW_LATER_WHEEL_SIZE];
ErtsMonotonicTime pos;
Uint nto;
struct {
@@ -128,14 +230,58 @@ struct ErtsTimerWheel_ {
ErtsTWheelTimer *tail;
Uint nto;
} at_once;
+ struct {
+ Uint nto;
+ } soon;
+ struct {
+ ErtsMonotonicTime pos;
+ } later;
int yield_slot;
int yield_slots_left;
- int yield_start_pos;
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,
@@ -143,11 +289,14 @@ find_next_timeout(ErtsSchedulerData *esdp,
ErtsMonotonicTime curr_time, /* When !search_all */
ErtsMonotonicTime max_search_time) /* When !search_all */
{
- int start_ix, tiw_pos_ix;
- ErtsTWheelTimer *p;
+ 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;
@@ -156,58 +305,115 @@ find_next_timeout(ErtsSchedulerData *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;
+ goto done;
}
- slot_timeout_pos = min_timeout_pos = tiw->pos;
if (search_all)
- min_timeout_pos += ERTS_MONOTONIC_TO_CLKTCKS(ERTS_MONOTONIC_DAY);
+ 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);
+ 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;
+ }
+ }
+ }
+ }
- start_ix = tiw_pos_ix = (int) (tiw->pos & (ERTS_TIW_SIZE-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 (++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;
- } while (p != end);
- }
-
- tiw_pos_ix++;
- if (tiw_pos_ix == ERTS_TIW_SIZE)
- tiw_pos_ix = 0;
+ 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);
-found_next:
+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(slot >= 0);
- ERTS_TW_ASSERT(slot < ERTS_TIW_SIZE);
+ 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;
@@ -223,6 +429,10 @@ insert_timer_into_slot(ErtsTimerWheel *tiw, int slot, ErtsTWheelTimer *p)
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
@@ -231,13 +441,13 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p)
int slot = p->slot;
ERTS_TW_ASSERT(slot != ERTS_TWHEEL_SLOT_INACTIVE);
- if (slot >= 0) {
+ 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_TIW_SIZE);
+ ERTS_TW_ASSERT(slot < ERTS_TW_LATER_WHEEL_END_SLOT);
if (p->next == p) {
ERTS_TW_ASSERT(tiw->w[slot] == p);
@@ -249,6 +459,8 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p)
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... */
@@ -270,8 +482,6 @@ remove_timer(ErtsTimerWheel *tiw, ErtsTWheelTimer *p)
}
p->slot = ERTS_TWHEEL_SLOT_INACTIVE;
-
- tiw->nto--;
}
ErtsMonotonicTime
@@ -299,13 +509,13 @@ debug_check_safe_to_skip_to(ErtsTimerWheel *tiw, ErtsMonotonicTime skip_to_pos)
ErtsTWheelTimer *tmr;
ErtsMonotonicTime tmp;
- ix = (int) (tiw->pos & (ERTS_TIW_SIZE-1));
+ ix = soon_slot(tiw->pos);
tmp = skip_to_pos - tiw->pos;
ERTS_TW_ASSERT(tmp >= 0);
- if (tmp < (ErtsMonotonicTime) ERTS_TIW_SIZE)
+ if (tmp < (ErtsMonotonicTime) ERTS_TW_SOON_WHEEL_SIZE)
slots = (int) tmp;
else
- slots = ERTS_TIW_SIZE;
+ slots = ERTS_TW_SOON_WHEEL_SIZE;
while (slots > 0) {
tmr = tiw->w[ix];
@@ -317,10 +527,41 @@ debug_check_safe_to_skip_to(ErtsTimerWheel *tiw, ErtsMonotonicTime skip_to_pos)
} while (tmr != end);
}
ix++;
- if (ix == ERTS_TIW_SIZE)
- ix = 0;
+ 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
@@ -339,8 +580,8 @@ timeout_timer(ErtsTWheelTimer *p)
void
erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
{
- int tiw_pos_ix, slots, yielded_slot_restarted, yield_count;
- ErtsMonotonicTime bump_to, tmp_slots, old_pos;
+ 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;
@@ -350,13 +591,16 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
* where we left off when restarting after a yield.
*/
- if (tiw->yield_slot >= 0) {
+ 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;
- bump_to = tiw->pos;
- old_pos = tiw->yield_start_pos;
- goto restart_yielded_slot;
+ ASSERT(0 <= slots && slots <= ERTS_TW_SOON_WHEEL_SIZE);
+ tiw->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE;
+ goto restart_yielded_soon_slot;
}
do {
@@ -368,8 +612,6 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime 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);
@@ -383,12 +625,12 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
p = tiw->at_once.head;
while (p) {
- if (--yield_count <= 0) {
+ 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);
+ tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to);
ERTS_MSACC_POP_STATE_M_X();
return;
}
@@ -405,6 +647,8 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
timeout_timer(p);
+ yield_count -= ERTS_TW_COST_TIMEOUT;
+
p = tiw->at_once.head;
}
@@ -433,22 +677,34 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
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;
}
}
- 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;
+ {
+ 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;
- while (slots > 0) {
+ /* 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);
@@ -463,18 +719,21 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
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:
+ 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) {
@@ -482,12 +741,11 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
break;
}
- if (--yield_count <= 0) {
+ if (yield_count <= 0) {
tiw->true_next_timeout_time = 1;
- tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(old_pos);
+ tiw->next_timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(bump_to);
tiw->yield_slot = tiw_pos_ix;
tiw->yield_slots_left = slots;
- tiw->yield_start_pos = old_pos;
ERTS_MSACC_POP_STATE_M_X();
return; /* Yield! */
}
@@ -496,16 +754,22 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
p->next->prev = &tiw->sentinel;
}
}
- tiw_pos_ix++;
- if (tiw_pos_ix == ERTS_TIW_SIZE)
- tiw_pos_ix = 0;
- slots--;
+
+ 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->yield_slot = ERTS_TWHEEL_SLOT_INACTIVE;
tiw->true_next_timeout_time = 0;
tiw->next_timeout_time = curr_time + ERTS_MONOTONIC_DAY;
@@ -514,6 +778,119 @@ erts_bump_timers(ErtsTimerWheel *tiw, ErtsMonotonicTime curr_time)
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)
{
@@ -524,11 +901,11 @@ ErtsTimerWheel *
erts_create_timer_wheel(ErtsSchedulerData *esdp)
{
ErtsMonotonicTime mtime;
- int i;
+ 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 = 0; i < ERTS_TIW_SIZE; i++)
+ for(; i < ERTS_TW_LATER_WHEEL_END_SLOT; i++)
tiw->w[i] = NULL;
mtime = erts_get_monotonic_time(esdp);
@@ -537,6 +914,10 @@ erts_create_timer_wheel(ErtsSchedulerData *esdp)
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;
@@ -586,36 +967,40 @@ erts_twheel_set_timer(ErtsTimerWheel *tiw,
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;
+ 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 */
- slot = (int) (timeout_pos & (ERTS_TIW_SIZE-1));
+ 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);
-
- tiw->nto++;
-
- timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos);
- p->timeout_pos = timeout_pos;
+ timeout_time = ERTS_CLKTCKS_TO_MONOTONIC(timeout_pos);
}
if (timeout_time < tiw->next_timeout_time) {
@@ -631,6 +1016,7 @@ 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();
}
}
@@ -658,7 +1044,9 @@ erts_twheel_debug_foreach(ErtsTimerWheel *tiw,
(*func)(arg, tmr->timeout_pos, tmr->arg);
}
- for (ix = 0; ix < ERTS_TIW_SIZE; ix++) {
+ for (ix = ERTS_TW_SOON_WHEEL_FIRST_SLOT;
+ ix < ERTS_TW_LATER_WHEEL_END_SLOT;
+ ix++) {
tmr = tiw->w[ix];
if (tmr) {
do {
@@ -670,36 +1058,92 @@ erts_twheel_debug_foreach(ErtsTimerWheel *tiw,
}
}
-#ifdef ERTS_TW_DEBUG
-void erts_p_slpq(void)
+#ifdef ERTS_TW_HARD_DEBUG
+
+static void
+hrd_dbg_check_wheels(ErtsTimerWheel *tiw, int check_min_tpos)
{
- erts_printf("Not yet implemented...\n");
-#if 0
- ErtsMonotonicTime current_time = erts_get_monotonic_time(NULL);
- int i;
- ErtsTWheelTimer* p;
-
- /* print the whole wheel, starting at the current position */
- 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->w[i]; p != NULL; p = p->next) {
- erts_printf(" (timeout time %bps, slot %d)\n",
- ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos),
- p->slot);
- }
+ 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);
+ }
}
- 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->w[i]; p != NULL; p = p->next) {
- erts_printf(" (timeout time %bps, slot %d)\n",
- ERTS_CLKTCKS_TO_MONOTONIC(p->timeout_pos), p->slot);
- }
- }
+
+ 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);
+ }
}
-#endif
+
+ 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 /* ERTS_TW_DEBUG */
+
+#endif