From a4aaf906794d9f82710614ba368a36500e8a8254 Mon Sep 17 00:00:00 2001 From: Valentin Bartenev Date: Mon, 22 Oct 2018 16:01:10 +0300 Subject: Re-engineered timers. To optimize rbtree operations, all changes are stored in array and later processed in batches. The previous implementation of this mechanics had a number of design flaws. Each change was saved in a new array entry; until the changes were applied, the timer remained in an intermediate state (NXT_TIMER_CHANGING). This intermediate state didn't allow to identify if time was going to be disabled or enabled. However, the nxt_conn_io_read() function relied on this information; as a result, in some cases the read timeout wasn't set. Also, the nxt_timer_delete() function did not reliably track whether a timer was added to the work queue. It checked the NXT_TIMER_ENQUEUED state of a timer, but this state could be reset to NXT_TIMER_DISABLED by a nxt_timer_disable() call or another nxt_timer_delete() call. Now, instead of keeping the whole history of the timer's changes, the new implementation updates the timer state immediately, and only one operation is added to the array to add or delete timer in the rbtree according to its final state. --- src/nxt_timer.c | 135 ++++++++++++++++++++++---------------------------------- 1 file changed, 53 insertions(+), 82 deletions(-) (limited to 'src/nxt_timer.c') diff --git a/src/nxt_timer.c b/src/nxt_timer.c index f56ddeb6..97807d75 100644 --- a/src/nxt_timer.c +++ b/src/nxt_timer.c @@ -32,6 +32,10 @@ nxt_timers_init(nxt_timers_t *timers, nxt_uint_t mchanges) { nxt_rbtree_init(&timers->tree, nxt_timer_rbtree_compare); + if (mchanges > NXT_TIMER_MAX_CHANGES) { + mchanges = NXT_TIMER_MAX_CHANGES; + } + timers->mchanges = mchanges; timers->changes = nxt_malloc(sizeof(nxt_timer_change_t) * mchanges); @@ -71,66 +75,47 @@ nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer, time = engine->timers.now + timeout; - if (timer->state != NXT_TIMER_CHANGING) { + nxt_debug(timer->task, "timer add: %M %M:%M", timer->time, timeout, time); - if (nxt_timer_is_in_tree(timer)) { + timer->enabled = 1; - diff = nxt_msec_diff(time, timer->time); - /* - * Use the previous timer if difference between it and the - * new timer is less than required precision milliseconds: this - * decreases number of rbtree operations for fast connections. - */ - if (nxt_abs(diff) < timer->precision) { - nxt_debug(timer->task, "timer previous: %M:%d", - time, timer->state); + if (nxt_timer_is_in_tree(timer)) { - timer->state = NXT_TIMER_WAITING; - return; - } + diff = nxt_msec_diff(time, timer->time); + /* + * Use the previous timer if difference between it and the + * new timer is less than required precision milliseconds: this + * decreases number of rbtree operations for fast connections. + */ + if (nxt_abs(diff) < timer->precision) { + nxt_debug(timer->task, "timer previous: %M", time); + + nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0); + return; } } - nxt_debug(timer->task, "timer add: %M:%d %M:%M", - timer->time, timer->state, timeout, time); - nxt_timer_change(engine, timer, NXT_TIMER_ADD, time); } -void -nxt_timer_disable(nxt_event_engine_t *engine, nxt_timer_t *timer) -{ - nxt_debug(timer->task, "timer disable: %M:%d", timer->time, timer->state); - - if (timer->state != NXT_TIMER_CHANGING) { - timer->state = NXT_TIMER_DISABLED; - - } else { - nxt_timer_change(engine, timer, NXT_TIMER_DISABLE, 0); - } -} - - nxt_bool_t nxt_timer_delete(nxt_event_engine_t *engine, nxt_timer_t *timer) { - nxt_bool_t pending; + nxt_debug(timer->task, "timer delete: %M", timer->time); + + timer->enabled = 0; - if (nxt_timer_is_in_tree(timer) || timer->state == NXT_TIMER_CHANGING) { - nxt_debug(timer->task, "timer delete: %M:%d", - timer->time, timer->state); + if (nxt_timer_is_in_tree(timer)) { nxt_timer_change(engine, timer, NXT_TIMER_DELETE, 0); return 1; } - pending = (timer->state == NXT_TIMER_ENQUEUED); - - timer->state = NXT_TIMER_DISABLED; + nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0); - return pending; + return (timer->queued || timer->change != NXT_TIMER_NO_CHANGE); } @@ -143,31 +128,35 @@ nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer, timers = &engine->timers; - if (timers->nchanges >= timers->mchanges) { - nxt_timer_changes_commit(engine); + if (timer->change == NXT_TIMER_NO_CHANGE) { + + if (change == NXT_TIMER_NOPE) { + return; + } + + if (timers->nchanges >= timers->mchanges) { + nxt_timer_changes_commit(engine); + } + + timers->nchanges++; + timer->change = timers->nchanges; } nxt_debug(timer->task, "timer change: %M:%d", time, change); - timer->state = NXT_TIMER_CHANGING; - - ch = &timers->changes[timers->nchanges]; + ch = &timers->changes[timer->change - 1]; ch->change = change; ch->time = time; ch->timer = timer; - - timers->nchanges++; } static void nxt_timer_changes_commit(nxt_event_engine_t *engine) { - int32_t diff; nxt_timer_t *timer; nxt_timers_t *timers; - nxt_timer_state_t state; nxt_timer_change_t *ch, *end; timers = &engine->timers; @@ -178,28 +167,16 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) end = ch + timers->nchanges; while (ch < end) { - state = NXT_TIMER_DISABLED; - timer = ch->timer; switch (ch->change) { + case NXT_TIMER_NOPE: + break; + case NXT_TIMER_ADD: if (nxt_timer_is_in_tree(timer)) { - - diff = nxt_msec_diff(ch->time, timer->time); - /* See the comment in nxt_timer_add(). */ - - if (nxt_abs(diff) < timer->precision) { - nxt_debug(timer->task, "timer rbtree previous: %M:%d", - ch->time, timer->state); - - state = NXT_TIMER_WAITING; - break; - } - - nxt_debug(timer->task, "timer rbtree delete: %M:%d", - timer->time, timer->state); + nxt_debug(timer->task, "timer rbtree delete: %M", timer->time); nxt_rbtree_delete(&timers->tree, &timer->node); } @@ -210,26 +187,19 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) nxt_rbtree_insert(&timers->tree, &timer->node); nxt_timer_in_tree_set(timer); - state = NXT_TIMER_WAITING; break; case NXT_TIMER_DELETE: - if (nxt_timer_is_in_tree(timer)) { - nxt_debug(timer->task, "timer rbtree delete: %M:%d", - timer->time, timer->state); + nxt_debug(timer->task, "timer rbtree delete: %M", timer->time); - nxt_rbtree_delete(&timers->tree, &timer->node); - nxt_timer_in_tree_clear(timer); - } + nxt_rbtree_delete(&timers->tree, &timer->node); + nxt_timer_in_tree_clear(timer); break; - - case NXT_TIMER_DISABLE: - break; } - timer->state = state; + timer->change = NXT_TIMER_NO_CHANGE; ch++; } @@ -270,7 +240,7 @@ nxt_timer_find(nxt_event_engine_t *engine) * return much earlier and the disabled timer can be reactivated. */ - if (timer->state != NXT_TIMER_DISABLED) { + if (timer->enabled) { time = timer->time; timers->minimum = time; @@ -324,14 +294,13 @@ nxt_timer_expire(nxt_event_engine_t *engine, nxt_msec_t now) next = nxt_rbtree_node_successor(tree, node); - nxt_debug(timer->task, "timer expire delete: %M:%d", - timer->time, timer->state); + nxt_debug(timer->task, "timer expire delete: %M", timer->time); nxt_rbtree_delete(tree, &timer->node); nxt_timer_in_tree_clear(timer); - if (timer->state != NXT_TIMER_DISABLED) { - timer->state = NXT_TIMER_ENQUEUED; + if (timer->enabled) { + timer->queued = 1; nxt_work_queue_add(timer->work_queue, nxt_timer_handler, timer->task, timer, NULL); @@ -347,8 +316,10 @@ nxt_timer_handler(nxt_task_t *task, void *obj, void *data) timer = obj; - if (timer->state == NXT_TIMER_ENQUEUED) { - timer->state = NXT_TIMER_DISABLED; + timer->queued = 0; + + if (timer->enabled && timer->change == NXT_TIMER_NO_CHANGE) { + timer->enabled = 0; timer->handler(task, timer, NULL); } -- cgit From b20e995e80d236945ec8388dfee37257ce9e5445 Mon Sep 17 00:00:00 2001 From: Valentin Bartenev Date: Mon, 22 Oct 2018 16:02:14 +0300 Subject: Timers: separation of delete and insert operations on rbtree. Delete/insert operation complexity for a red-black tree is O(log n), where n is the total number of tree elements. If all delete operations are performed before all insert operations, the average number of tree elements during an operation will be lower than in the mixed-operations case. --- src/nxt_timer.c | 30 ++++++++++++++++++++---------- 1 file changed, 20 insertions(+), 10 deletions(-) (limited to 'src/nxt_timer.c') diff --git a/src/nxt_timer.c b/src/nxt_timer.c index 97807d75..0b89dafc 100644 --- a/src/nxt_timer.c +++ b/src/nxt_timer.c @@ -155,7 +155,7 @@ nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer, static void nxt_timer_changes_commit(nxt_event_engine_t *engine) { - nxt_timer_t *timer; + nxt_timer_t *timer, **add, **add_end; nxt_timers_t *timers; nxt_timer_change_t *ch, *end; @@ -166,6 +166,9 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) ch = timers->changes; end = ch + timers->nchanges; + add = (nxt_timer_t **) ch; + add_end = add; + while (ch < end) { timer = ch->timer; @@ -175,20 +178,16 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) break; case NXT_TIMER_ADD: - if (nxt_timer_is_in_tree(timer)) { - nxt_debug(timer->task, "timer rbtree delete: %M", timer->time); - - nxt_rbtree_delete(&timers->tree, &timer->node); - } timer->time = ch->time; - nxt_debug(timer->task, "timer rbtree insert: %M", timer->time); + *add_end++ = timer; - nxt_rbtree_insert(&timers->tree, &timer->node); - nxt_timer_in_tree_set(timer); + if (!nxt_timer_is_in_tree(timer)) { + break; + } - break; + /* Fall through. */ case NXT_TIMER_DELETE: nxt_debug(timer->task, "timer rbtree delete: %M", timer->time); @@ -204,6 +203,17 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) ch++; } + while (add < add_end) { + timer = *add; + + nxt_debug(timer->task, "timer rbtree insert: %M", timer->time); + + nxt_rbtree_insert(&timers->tree, &timer->node); + nxt_timer_in_tree_set(timer); + + add++; + } + timers->nchanges = 0; } -- cgit From da0ef366dc1affa740618eb4f4baa8bbb62f8d70 Mon Sep 17 00:00:00 2001 From: Valentin Bartenev Date: Mon, 22 Oct 2018 16:04:16 +0300 Subject: Handling of timers with bias. Timers that don't require maximum precision (most of them, actually) can be triggered earlier or later within the bias interval. To reduce wakeups by timers, the expire function now triggers not only all timers that fall within the elapsed time, but also those whose bias falls within this interval. --- src/nxt_timer.c | 37 ++++++++++++++++++++++--------------- 1 file changed, 22 insertions(+), 15 deletions(-) (limited to 'src/nxt_timer.c') diff --git a/src/nxt_timer.c b/src/nxt_timer.c index 0b89dafc..cba4755b 100644 --- a/src/nxt_timer.c +++ b/src/nxt_timer.c @@ -75,7 +75,8 @@ nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer, time = engine->timers.now + timeout; - nxt_debug(timer->task, "timer add: %M %M:%M", timer->time, timeout, time); + nxt_debug(timer->task, "timer add: %M±%d %M:%M", + timer->time, timer->bias, timeout, time); timer->enabled = 1; @@ -84,11 +85,12 @@ nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer, diff = nxt_msec_diff(time, timer->time); /* * Use the previous timer if difference between it and the - * new timer is less than required precision milliseconds: this - * decreases number of rbtree operations for fast connections. + * new timer is within bias: this decreases number of rbtree + * operations for fast connections. */ - if (nxt_abs(diff) < timer->precision) { - nxt_debug(timer->task, "timer previous: %M", time); + if (nxt_abs(diff) <= timer->bias) { + nxt_debug(timer->task, "timer previous: %M±%d", + time, timer->bias); nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0); return; @@ -102,7 +104,8 @@ nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer, nxt_bool_t nxt_timer_delete(nxt_event_engine_t *engine, nxt_timer_t *timer) { - nxt_debug(timer->task, "timer delete: %M", timer->time); + nxt_debug(timer->task, "timer delete: %M±%d", + timer->time, timer->bias); timer->enabled = 0; @@ -142,7 +145,8 @@ nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer, timer->change = timers->nchanges; } - nxt_debug(timer->task, "timer change: %M:%d", time, change); + nxt_debug(timer->task, "timer change: %M±%d:%d", + time, timer->bias, change); ch = &timers->changes[timer->change - 1]; @@ -190,7 +194,8 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) /* Fall through. */ case NXT_TIMER_DELETE: - nxt_debug(timer->task, "timer rbtree delete: %M", timer->time); + nxt_debug(timer->task, "timer rbtree delete: %M±%d", + timer->time, timer->bias); nxt_rbtree_delete(&timers->tree, &timer->node); nxt_timer_in_tree_clear(timer); @@ -206,7 +211,8 @@ nxt_timer_changes_commit(nxt_event_engine_t *engine) while (add < add_end) { timer = *add; - nxt_debug(timer->task, "timer rbtree insert: %M", timer->time); + nxt_debug(timer->task, "timer rbtree insert: %M±%d", + timer->time, timer->bias); nxt_rbtree_insert(&timers->tree, &timer->node); nxt_timer_in_tree_set(timer); @@ -252,10 +258,10 @@ nxt_timer_find(nxt_event_engine_t *engine) if (timer->enabled) { time = timer->time; - timers->minimum = time; + timers->minimum = time - timer->bias; - nxt_debug(timer->task, "timer found minimum: %M:%M", - time, timers->now); + nxt_debug(timer->task, "timer found minimum: %M±%d:%M", + time, timer->bias, timers->now); delta = nxt_msec_diff(time, timers->now); @@ -297,14 +303,15 @@ nxt_timer_expire(nxt_event_engine_t *engine, nxt_msec_t now) { timer = (nxt_timer_t *) node; - /* timer->time > now */ - if (nxt_msec_diff(timer->time , now) > 0) { + /* timer->time > now + timer->bias */ + if (nxt_msec_diff(timer->time , now) > (int32_t) timer->bias) { return; } next = nxt_rbtree_node_successor(tree, node); - nxt_debug(timer->task, "timer expire delete: %M", timer->time); + nxt_debug(timer->task, "timer expire delete: %M±%d", + timer->time, timer->bias); nxt_rbtree_delete(tree, &timer->node); nxt_timer_in_tree_clear(timer); -- cgit