Skip to content

Commit 95c5bf8

Browse files
bnoordhuisbnoordhuis
committed
unix,win: merge timers implementation
Merge src/unix/timer.c and src/win/timer.c into src/timer.c. This changes the Windows implementation from a binary tree to a binary heap for generally better performance. PR-URL: #1882 Reviewed-By: Bartosz Sosnowski <[email protected]> Reviewed-By: Colin Ihrig <[email protected]>
1 parent e1f505f commit 95c5bf8

11 files changed

Lines changed: 51 additions & 230 deletions

File tree

‎CMakeLists.txt‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ set(uv_sources
1515
src/fs-poll.c
1616
src/inet.c
1717
src/threadpool.c
18+
src/timer.c
1819
src/uv-common.c
1920
src/uv-data-getter-setters.c
2021
src/version.c)
@@ -197,7 +198,6 @@ if(WIN32)
197198
src/win/stream.c
198199
src/win/tcp.c
199200
src/win/tty.c
200-
src/win/timer.c
201201
src/win/udp.c
202202
src/win/util.c
203203
src/win/winapi.c
@@ -223,7 +223,6 @@ else()
223223
src/unix/stream.c
224224
src/unix/tcp.c
225225
src/unix/thread.c
226-
src/unix/timer.c
227226
src/unix/tty.c
228227
src/unix/udp.c)
229228
list(APPEND uv_test_sources test/runner-unix.c)

‎Makefile.am‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ libuv_la_SOURCES = src/fs-poll.c \
3232
src/inet.c \
3333
src/queue.h \
3434
src/threadpool.c \
35+
src/timer.c \
3536
src/uv-data-getter-setters.c \
3637
src/uv-common.c \
3738
src/uv-common.h \
@@ -74,7 +75,6 @@ libuv_la_SOURCES += src/win/async.c \
7475
src/win/stream-inl.h \
7576
src/win/tcp.c \
7677
src/win/thread.c \
77-
src/win/timer.c \
7878
src/win/tty.c \
7979
src/win/udp.c \
8080
src/win/util.c \
@@ -105,7 +105,6 @@ libuv_la_SOURCES += src/unix/async.c \
105105
src/unix/stream.c \
106106
src/unix/tcp.c \
107107
src/unix/thread.c \
108-
src/unix/timer.c \
109108
src/unix/tty.c \
110109
src/unix/udp.c
111110

‎include/uv/win.h‎

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -308,8 +308,6 @@ typedef struct {
308308
char* errmsg;
309309
} uv_lib_t;
310310

311-
RB_HEAD(uv_timer_tree_s, uv_timer_s);
312-
313311
#define UV_LOOP_PRIVATE_FIELDS \
314312
/* The loop's I/O completion port */ \
315313
HANDLE iocp; \
@@ -321,8 +319,8 @@ RB_HEAD(uv_timer_tree_s, uv_timer_s);
321319
uv_req_t* pending_reqs_tail; \
322320
/* Head of a single-linked list of closed handles */ \
323321
uv_handle_t* endgame_handles; \
324-
/* The head of the timers tree */ \
325-
struct uv_timer_tree_s timers; \
322+
/* TODO(bnoordhuis) Stop heap-allocating |timer_heap| in libuv v2.x. */ \
323+
void* timer_heap; \
326324
/* Lists of active loop (prepare / check / idle) watchers */ \
327325
uv_prepare_t* prepare_handles; \
328326
uv_check_t* check_handles; \
@@ -529,8 +527,9 @@ RB_HEAD(uv_timer_tree_s, uv_timer_s);
529527
unsigned char events;
530528

531529
#define UV_TIMER_PRIVATE_FIELDS \
532-
RB_ENTRY(uv_timer_s) tree_entry; \
533-
uint64_t due; \
530+
void* heap_node[3]; \
531+
int unused; \
532+
uint64_t timeout; \
534533
uint64_t repeat; \
535534
uint64_t start_id; \
536535
uv_timer_cb timer_cb;

src/unix/timer.c renamed to src/timer.c

Lines changed: 14 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -19,13 +19,22 @@
1919
*/
2020

2121
#include "uv.h"
22-
#include "internal.h"
22+
#include "uv-common.h"
2323
#include "heap-inl.h"
2424

2525
#include <assert.h>
2626
#include <limits.h>
2727

2828

29+
static struct heap *timer_heap(const uv_loop_t* loop) {
30+
#ifdef _WIN32
31+
return (struct heap*) loop->timer_heap;
32+
#else
33+
return (struct heap*) &loop->timer_heap;
34+
#endif
35+
}
36+
37+
2938
static int timer_less_than(const struct heap_node* ha,
3039
const struct heap_node* hb) {
3140
const uv_timer_t* a;
@@ -81,7 +90,7 @@ int uv_timer_start(uv_timer_t* handle,
8190
/* start_id is the second index to be compared in uv__timer_cmp() */
8291
handle->start_id = handle->loop->timer_counter++;
8392

84-
heap_insert((struct heap*) &handle->loop->timer_heap,
93+
heap_insert(timer_heap(handle->loop),
8594
(struct heap_node*) &handle->heap_node,
8695
timer_less_than);
8796
uv__handle_start(handle);
@@ -94,7 +103,7 @@ int uv_timer_stop(uv_timer_t* handle) {
94103
if (!uv__is_active(handle))
95104
return 0;
96105

97-
heap_remove((struct heap*) &handle->loop->timer_heap,
106+
heap_remove(timer_heap(handle->loop),
98107
(struct heap_node*) &handle->heap_node,
99108
timer_less_than);
100109
uv__handle_stop(handle);
@@ -131,7 +140,7 @@ int uv__next_timeout(const uv_loop_t* loop) {
131140
const uv_timer_t* handle;
132141
uint64_t diff;
133142

134-
heap_node = heap_min((const struct heap*) &loop->timer_heap);
143+
heap_node = heap_min(timer_heap(loop));
135144
if (heap_node == NULL)
136145
return -1; /* block indefinitely */
137146

@@ -152,7 +161,7 @@ void uv__run_timers(uv_loop_t* loop) {
152161
uv_timer_t* handle;
153162

154163
for (;;) {
155-
heap_node = heap_min((struct heap*) &loop->timer_heap);
164+
heap_node = heap_min(timer_heap(loop));
156165
if (heap_node == NULL)
157166
break;
158167

‎src/unix/internal.h‎

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -252,10 +252,6 @@ int uv__tcp_keepalive(int fd, int on, unsigned int delay);
252252
/* pipe */
253253
int uv_pipe_listen(uv_pipe_t* handle, int backlog, uv_connection_cb cb);
254254

255-
/* timer */
256-
void uv__run_timers(uv_loop_t* loop);
257-
int uv__next_timeout(const uv_loop_t* loop);
258-
259255
/* signal */
260256
void uv__signal_close(uv_signal_t* handle);
261257
void uv__signal_global_once_init(void);
@@ -280,7 +276,6 @@ void uv__prepare_close(uv_prepare_t* handle);
280276
void uv__process_close(uv_process_t* handle);
281277
void uv__stream_close(uv_stream_t* handle);
282278
void uv__tcp_close(uv_tcp_t* handle);
283-
void uv__timer_close(uv_timer_t* handle);
284279
void uv__udp_close(uv_udp_t* handle);
285280
void uv__udp_finish_close(uv_udp_t* handle);
286281
uv_handle_type uv__handle_type(int fd);

‎src/uv-common.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -132,6 +132,10 @@ int uv__socket_sockopt(uv_handle_t* handle, int optname, int* value);
132132

133133
void uv__fs_scandir_cleanup(uv_fs_t* req);
134134

135+
int uv__next_timeout(const uv_loop_t* loop);
136+
void uv__run_timers(uv_loop_t* loop);
137+
void uv__timer_close(uv_timer_t* handle);
138+
135139
#define uv__has_active_reqs(loop) \
136140
((loop)->active_reqs.count > 0)
137141

‎src/win/core.c‎

Lines changed: 23 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,7 @@
3333
#include "internal.h"
3434
#include "queue.h"
3535
#include "handle-inl.h"
36+
#include "heap-inl.h"
3637
#include "req-inl.h"
3738

3839
/* uv_once initialization guards */
@@ -221,6 +222,7 @@ static void uv_init(void) {
221222

222223

223224
int uv_loop_init(uv_loop_t* loop) {
225+
struct heap* timer_heap;
224226
int err;
225227

226228
/* Initialize libuv itself first */
@@ -246,7 +248,11 @@ int uv_loop_init(uv_loop_t* loop) {
246248

247249
loop->endgame_handles = NULL;
248250

249-
RB_INIT(&loop->timers);
251+
loop->timer_heap = timer_heap = uv__malloc(sizeof(*timer_heap));
252+
if (timer_heap == NULL)
253+
goto fail_timers_alloc;
254+
255+
heap_init(timer_heap);
250256

251257
loop->check_handles = NULL;
252258
loop->prepare_handles = NULL;
@@ -285,13 +291,24 @@ int uv_loop_init(uv_loop_t* loop) {
285291
uv_mutex_destroy(&loop->wq_mutex);
286292

287293
fail_mutex_init:
294+
uv__free(timer_heap);
295+
loop->timer_heap = NULL;
296+
297+
fail_timers_alloc:
288298
CloseHandle(loop->iocp);
289299
loop->iocp = INVALID_HANDLE_VALUE;
290300

291301
return err;
292302
}
293303

294304

305+
void uv_update_time(uv_loop_t* loop) {
306+
uint64_t new_time = uv__hrtime(1000);
307+
assert(new_time >= loop->time);
308+
loop->time = new_time;
309+
}
310+
311+
295312
void uv__once_init(void) {
296313
uv_once(&uv_init_guard_, uv_init);
297314
}
@@ -320,6 +337,9 @@ void uv__loop_close(uv_loop_t* loop) {
320337
uv_mutex_unlock(&loop->wq_mutex);
321338
uv_mutex_destroy(&loop->wq_mutex);
322339

340+
uv__free(loop->timer_heap);
341+
loop->timer_heap = NULL;
342+
323343
CloseHandle(loop->iocp);
324344
}
325345

@@ -441,7 +461,7 @@ int uv_run(uv_loop_t *loop, uv_run_mode mode) {
441461

442462
while (r != 0 && loop->stop_flag == 0) {
443463
uv_update_time(loop);
444-
uv_process_timers(loop);
464+
uv__run_timers(loop);
445465

446466
ran_pending = uv_process_reqs(loop);
447467
uv_idle_invoke(loop);
@@ -465,7 +485,7 @@ int uv_run(uv_loop_t *loop, uv_run_mode mode) {
465485
* UV_RUN_NOWAIT makes no guarantees about progress so it's omitted from
466486
* the check.
467487
*/
468-
uv_process_timers(loop);
488+
uv__run_timers(loop);
469489
}
470490

471491
r = uv__loop_alive(loop);

‎src/win/handle-inl.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -126,7 +126,8 @@ INLINE static void uv_process_endgames(uv_loop_t* loop) {
126126
break;
127127

128128
case UV_TIMER:
129-
uv_timer_endgame(loop, (uv_timer_t*) handle);
129+
uv__timer_close((uv_timer_t*) handle);
130+
uv__handle_close(handle);
130131
break;
131132

132133
case UV_PREPARE:

‎src/win/internal.h‎

Lines changed: 0 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -246,15 +246,6 @@ int uv_poll_close(uv_loop_t* loop, uv_poll_t* handle);
246246
void uv_poll_endgame(uv_loop_t* loop, uv_poll_t* handle);
247247

248248

249-
/*
250-
* Timers
251-
*/
252-
void uv_timer_endgame(uv_loop_t* loop, uv_timer_t* handle);
253-
254-
DWORD uv__next_timeout(const uv_loop_t* loop);
255-
void uv_process_timers(uv_loop_t* loop);
256-
257-
258249
/*
259250
* Loop watchers
260251
*/

0 commit comments

Comments
 (0)