- tor-commits - lists.torproject.org

[tor/master] Merge branch 'feature15588_squashed'
by nickm＠torproject.org 09 May '16

09 May '16

commit 33d3572a1d61d81cd3f26778cd137eb2271f5e3c Merge: 6938003 162aa14e Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon May 9 14:41:36 2016 -0400 Merge branch 'feature15588_squashed' src/or/connection_edge.c | 4 +- src/or/control.c | 173 +++++++++++++++++++++++++++++++++++++++------ src/or/control.h | 2 + src/or/or.h | 4 +- src/or/rendclient.c | 34 ++------- src/or/rendcommon.c | 127 +++++++++++++++++++++++++++++++++ src/or/rendcommon.h | 9 +++ src/or/rendservice.c | 86 +++++++++++----------- src/or/rendservice.h | 5 ++ src/or/routerparse.c | 31 +++----- src/test/test_controller.c | 51 +++++++++++++ src/test/test_hs.c | 63 +++++++++++++++++ 12 files changed, 469 insertions(+), 120 deletions(-) diff --cc src/or/rendcommon.c index b927486,dfa6c1e..56c49fe --- a/src/or/rendcommon.c +++ b/src/or/rendcommon.c @@@ -906,38 -952,113 +922,149 @@@ rend_data_client_create(const char *oni return NULL; } +/** Determine the routers that are responsible for id (binary) and + * add pointers to those routers' routerstatus_t to responsible_dirs. + * Return -1 if we're returning an empty smartlist, else return 0. + */ +int +hid_serv_get_responsible_directories(smartlist_t *responsible_dirs, + const char *id) +{ + int start, found, n_added = 0, i; + networkstatus_t *c = networkstatus_get_latest_consensus(); + if (!c || !smartlist_len(c->routerstatus_list)) { + log_warn(LD_REND, "We don't have a consensus, so we can't perform v2 " + "rendezvous operations."); + return -1; + } + tor_assert(id); + start = networkstatus_vote_find_entry_idx(c, id, &found); + if (start == smartlist_len(c->routerstatus_list)) start = 0; + i = start; + do { + routerstatus_t *r = smartlist_get(c->routerstatus_list, i); + if (r->is_hs_dir) { + smartlist_add(responsible_dirs, r); + if (++n_added == REND_NUMBER_OF_CONSECUTIVE_REPLICAS) + return 0; + } + if (++i == smartlist_len(c->routerstatus_list)) + i = 0; + } while (i != start); + + /* Even though we don't have the desired number of hidden service + * directories, be happy if we got any. */ + return smartlist_len(responsible_dirs) ? 0 : -1; +} + + /* Length of the 'extended' auth cookie used to encode auth type before + * base64 encoding. */ + #define REND_DESC_COOKIE_LEN_EXT (REND_DESC_COOKIE_LEN + 1) + /* Length of the zero-padded auth cookie when base64 encoded. These two + * padding bytes always (A=) are stripped off of the returned cookie. */ + #define REND_DESC_COOKIE_LEN_EXT_BASE64 (REND_DESC_COOKIE_LEN_BASE64 + 2) + + /** Encode a client authorization descriptor cookie. + * The result of this function is suitable for use in the HidServAuth + * option. The trailing padding characters are removed, and the + * auth type is encoded into the cookie. + * + * Returns a new base64-encoded cookie. This function cannot fail. + * The caller is responsible for freeing the returned value. + */ + char * + rend_auth_encode_cookie(const uint8_t *cookie_in, rend_auth_type_t auth_type) + { + uint8_t extended_cookie[REND_DESC_COOKIE_LEN_EXT]; + char *cookie_out = tor_malloc_zero(REND_DESC_COOKIE_LEN_EXT_BASE64 + 1); + int re; + + tor_assert(cookie_in); + + memcpy(extended_cookie, cookie_in, REND_DESC_COOKIE_LEN); + extended_cookie[REND_DESC_COOKIE_LEN] = ((int)auth_type - 1) << 4; + re = base64_encode(cookie_out, REND_DESC_COOKIE_LEN_EXT_BASE64 + 1, + (const char *) extended_cookie, REND_DESC_COOKIE_LEN_EXT, + 0); + tor_assert(re == REND_DESC_COOKIE_LEN_EXT_BASE64); + + /* Remove the trailing 'A='. Auth type is encoded in the high bits + * of the last byte, so the last base64 character will always be zero + * (A). This is subtly different behavior from base64_encode_nopad. */ + cookie_out[REND_DESC_COOKIE_LEN_BASE64] = '\0'; + memwipe(extended_cookie, 0, sizeof(extended_cookie)); + return cookie_out; + } + + /** Decode a base64-encoded client authorization descriptor cookie. + * The descriptor_cookie can be truncated to REND_DESC_COOKIE_LEN_BASE64 + * characters (as given to clients), or may include the two padding + * characters (as stored by the service). + * + * The result is stored in REND_DESC_COOKIE_LEN bytes of cookie_out. + * The rend_auth_type_t decoded from the cookie is stored in the + * optional auth_type_out parameter. + * + * Return 0 on success, or -1 on error. The caller is responsible for + * freeing the returned err_msg. + */ + int + rend_auth_decode_cookie(const char *cookie_in, uint8_t *cookie_out, + rend_auth_type_t *auth_type_out, char **err_msg_out) + { + uint8_t descriptor_cookie_decoded[REND_DESC_COOKIE_LEN_EXT + 1] = { 0 }; + char descriptor_cookie_base64ext[REND_DESC_COOKIE_LEN_EXT_BASE64 + 1]; + const char *descriptor_cookie = cookie_in; + char *err_msg = NULL; + int auth_type_val = 0; + int res = -1; + int decoded_len; + + size_t len = strlen(descriptor_cookie); + if (len == REND_DESC_COOKIE_LEN_BASE64) { + /* Add a trailing zero byte to make base64-decoding happy. */ + tor_snprintf(descriptor_cookie_base64ext, + sizeof(descriptor_cookie_base64ext), + "%sA=", descriptor_cookie); + descriptor_cookie = descriptor_cookie_base64ext; + } else if (len != REND_DESC_COOKIE_LEN_EXT_BASE64) { + tor_asprintf(&err_msg, "Authorization cookie has wrong length: %s", + escaped(cookie_in)); + goto err; + } + + decoded_len = base64_decode((char *) descriptor_cookie_decoded, + sizeof(descriptor_cookie_decoded), + descriptor_cookie, + REND_DESC_COOKIE_LEN_EXT_BASE64); + if (decoded_len != REND_DESC_COOKIE_LEN && + decoded_len != REND_DESC_COOKIE_LEN_EXT) { + tor_asprintf(&err_msg, "Authorization cookie has invalid characters: %s", + escaped(cookie_in)); + goto err; + } + + if (auth_type_out) { + auth_type_val = (descriptor_cookie_decoded[REND_DESC_COOKIE_LEN] >> 4) + 1; + if (auth_type_val < 1 || auth_type_val > 2) { + tor_asprintf(&err_msg, "Authorization cookie type is unknown: %s", + escaped(cookie_in)); + goto err; + } + *auth_type_out = auth_type_val == 1 ? REND_BASIC_AUTH : REND_STEALTH_AUTH; + } + + memcpy(cookie_out, descriptor_cookie_decoded, REND_DESC_COOKIE_LEN); + res = 0; + err: + if (err_msg_out) { + *err_msg_out = err_msg; + } else { + tor_free(err_msg); + } + memwipe(descriptor_cookie_decoded, 0, sizeof(descriptor_cookie_decoded)); + memwipe(descriptor_cookie_base64ext, 0, sizeof(descriptor_cookie_base64ext)); + return res; + } + ++

1 0

[tor/master] Move rend client name checks to one function
by nickm＠torproject.org 09 May '16

09 May '16

commit 162aa14eef69bc97233d6b2c47bc1317e30f9364 Author: John Brooks <john.brooks(a)dereferenced.net> Date: Fri Feb 19 16:32:25 2016 -0700 Move rend client name checks to one function --- src/or/rendcommon.c | 16 ++++++++++++++++ src/or/rendcommon.h | 1 + src/or/rendservice.c | 18 ++++-------------- src/or/routerparse.c | 9 +++------ 4 files changed, 24 insertions(+), 20 deletions(-) diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c index a9fdf84..dfa6c1e 100644 --- a/src/or/rendcommon.c +++ b/src/or/rendcommon.c @@ -750,6 +750,22 @@ rend_valid_descriptor_id(const char *query) return 0; } +/** Return true iff client_name is a syntactically valid name + * for rendezvous client authentication. */ +int +rend_valid_client_name(const char *client_name) +{ + size_t len = strlen(client_name); + if (len < 1 || len > REND_CLIENTNAME_MAX_LEN) { + return 0; + } + if (strspn(client_name, REND_LEGAL_CLIENTNAME_CHARACTERS) != len) { + return 0; + } + + return 1; +} + /** Called when we get a rendezvous-related relay cell on circuit * circ. Dispatch on rendezvous relay command. */ void diff --git a/src/or/rendcommon.h b/src/or/rendcommon.h index 983cd73..f0a740b 100644 --- a/src/or/rendcommon.h +++ b/src/or/rendcommon.h @@ -45,6 +45,7 @@ void rend_intro_point_free(rend_intro_point_t *intro); int rend_valid_service_id(const char *query); int rend_valid_descriptor_id(const char *query); +int rend_valid_client_name(const char *client_name); int rend_encode_v2_descriptors(smartlist_t *descs_out, rend_service_descriptor_t *desc, time_t now, uint8_t period, rend_auth_type_t auth_type, diff --git a/src/or/rendservice.c b/src/or/rendservice.c index 5b93209..030c836 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -672,27 +672,17 @@ rend_config_services(const or_options_t *options, int validate_only) SMARTLIST_FOREACH_BEGIN(clients, const char *, client_name) { rend_authorized_client_t *client; - size_t len = strlen(client_name); - if (len < 1 || len > REND_CLIENTNAME_MAX_LEN) { + if (!rend_valid_client_name(client_name)) { log_warn(LD_CONFIG, "HiddenServiceAuthorizeClient contains an " - "illegal client name: '%s'. Length must be " - "between 1 and %d characters.", + "illegal client name: '%s'. Names must be " + "between 1 and %d characters and contain " + "only [A-Za-z0-9+_-].", client_name, REND_CLIENTNAME_MAX_LEN); SMARTLIST_FOREACH(clients, char *, cp, tor_free(cp)); smartlist_free(clients); rend_service_free(service); return -1; } - if (strspn(client_name, REND_LEGAL_CLIENTNAME_CHARACTERS) != len) { - log_warn(LD_CONFIG, "HiddenServiceAuthorizeClient contains an " - "illegal client name: '%s'. Valid " - "characters are [A-Za-z0-9+_-].", - client_name); - SMARTLIST_FOREACH(clients, char *, cp, tor_free(cp)); - smartlist_free(clients); - rend_service_free(service); - return -1; - } client = tor_malloc_zero(sizeof(rend_authorized_client_t)); client->client_name = tor_strdup(client_name); smartlist_add(service->clients, client); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index 35f76cd..b1ac3df 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -5300,7 +5300,6 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) current_entry = eat_whitespace(ckstr); while (!strcmpstart(current_entry, "client-name ")) { rend_authorized_client_t *parsed_entry; - size_t len; /* Determine end of string. */ const char *eos = strstr(current_entry, "\nclient-name "); if (!eos) @@ -5329,12 +5328,10 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) tor_assert(tok == smartlist_get(tokens, 0)); tor_assert(tok->n_args == 1); - len = strlen(tok->args[0]); - if (len < 1 || len > 19 || - strspn(tok->args[0], REND_LEGAL_CLIENTNAME_CHARACTERS) != len) { + if (!rend_valid_client_name(tok->args[0])) { log_warn(LD_CONFIG, "Illegal client name: %s. (Length must be " - "between 1 and 19, and valid characters are " - "[A-Za-z0-9+-_].)", tok->args[0]); + "between 1 and %d, and valid characters are " + "[A-Za-z0-9+-_].)", tok->args[0], REND_CLIENTNAME_MAX_LEN); goto err; } /* Check if client name is duplicate. */

1 0

[translation/whisperback_completed] Update translations for whisperback_completed
by translation＠torproject.org 09 May '16

09 May '16

commit d25cd1367c2d89b00cde988c8e93ebce3530b466 Author: Translation commit bot <translation(a)torproject.org> Date: Mon May 9 18:15:14 2016 +0000 Update translations for whisperback_completed --- ca/ca.po | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/ca/ca.po b/ca/ca.po index c1ed08e..a7b389e 100644 --- a/ca/ca.po +++ b/ca/ca.po @@ -11,7 +11,7 @@ msgstr "" "Project-Id-Version: The Tor Project\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2015-12-16 19:54+0100\n" -"PO-Revision-Date: 2016-05-09 11:59+0000\n" +"PO-Revision-Date: 2016-05-09 18:04+0000\n" "Last-Translator: laia_\n" "Language-Team: Catalan (http://www.transifex.com/otf/torproject/language/ca/)\n" "MIME-Version: 1.0\n" @@ -82,20 +82,20 @@ msgid "" "The bug report could not be sent, likely due to network problems. Please try to reconnect to the network and click send again.\n" "\n" "If it does not work, you will be offered to save the bug report." -msgstr "\n\nEl report d'error no s'ha eviat per problemes de connexió. Intentau de reconnectar a la xarxa i clicau a enviar.\n\nSi això no funciona, podreu desar el report." +msgstr "\n\nEl registre d'error no s'ha enviat per problemes de connexió. Intenteu tornar a connectar-vos a la xarxa i cliqueu envia.\n\nSi això no funciona, podreu desar el registre." #: ../whisperBack/gui.py:269 msgid "Your message has been sent." -msgstr "El teu missatge s'ha enviat." +msgstr "El missatge s'ha enviat." #: ../whisperBack/gui.py:276 msgid "An error occured during encryption." -msgstr "Ha aparegut t un error durant l'encriptació." +msgstr "hi ha hagut un error durant l'encriptació." #: ../whisperBack/gui.py:296 #, python-format msgid "Unable to save %s." -msgstr "Incapaç de desar: %s." +msgstr "No es pot desar: %s." #: ../whisperBack/gui.py:319 #, python-format

1 0

[translation/whisperback] Update translations for whisperback
by translation＠torproject.org 09 May '16

09 May '16

commit d90000faaf223d79b388d8e3ae13b68f5c61b49c Author: Translation commit bot <translation(a)torproject.org> Date: Mon May 9 18:15:11 2016 +0000 Update translations for whisperback --- ca/ca.po | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/ca/ca.po b/ca/ca.po index c1ed08e..a7b389e 100644 --- a/ca/ca.po +++ b/ca/ca.po @@ -11,7 +11,7 @@ msgstr "" "Project-Id-Version: The Tor Project\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2015-12-16 19:54+0100\n" -"PO-Revision-Date: 2016-05-09 11:59+0000\n" +"PO-Revision-Date: 2016-05-09 18:04+0000\n" "Last-Translator: laia_\n" "Language-Team: Catalan (http://www.transifex.com/otf/torproject/language/ca/)\n" "MIME-Version: 1.0\n" @@ -82,20 +82,20 @@ msgid "" "The bug report could not be sent, likely due to network problems. Please try to reconnect to the network and click send again.\n" "\n" "If it does not work, you will be offered to save the bug report." -msgstr "\n\nEl report d'error no s'ha eviat per problemes de connexió. Intentau de reconnectar a la xarxa i clicau a enviar.\n\nSi això no funciona, podreu desar el report." +msgstr "\n\nEl registre d'error no s'ha enviat per problemes de connexió. Intenteu tornar a connectar-vos a la xarxa i cliqueu envia.\n\nSi això no funciona, podreu desar el registre." #: ../whisperBack/gui.py:269 msgid "Your message has been sent." -msgstr "El teu missatge s'ha enviat." +msgstr "El missatge s'ha enviat." #: ../whisperBack/gui.py:276 msgid "An error occured during encryption." -msgstr "Ha aparegut t un error durant l'encriptació." +msgstr "hi ha hagut un error durant l'encriptació." #: ../whisperBack/gui.py:296 #, python-format msgid "Unable to save %s." -msgstr "Incapaç de desar: %s." +msgstr "No es pot desar: %s." #: ../whisperBack/gui.py:319 #, python-format

1 0

[tor/master] Add timeouts to libor-event.a
by nickm＠torproject.org 09 May '16

09 May '16

commit 05499b6ded25b5cbc8b16916fa9c0a39407ab10f Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 13 09:12:39 2016 -0400 Add timeouts to libor-event.a --- src/common/include.am | 3 ++- src/ext/include.am | 7 ++----- 2 files changed, 4 insertions(+), 6 deletions(-) diff --git a/src/common/include.am b/src/common/include.am index f978eee..e61ed68 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -96,7 +96,8 @@ LIBOR_CRYPTO_A_SOURCES = \ LIBOR_EVENT_A_SOURCES = \ src/common/compat_libevent.c \ - src/common/procmon.c + src/common/procmon.c \ + src/ext/timeouts/timeout.c src_common_libor_a_SOURCES = $(LIBOR_A_SOURCES) src_common_libor_crypto_a_SOURCES = $(LIBOR_CRYPTO_A_SOURCES) diff --git a/src/ext/include.am b/src/ext/include.am index b4281b9..42a38f1 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -166,10 +166,7 @@ EXTRA_DIST += \ timeouts/lua/timeout-lua.c \ timeouts/Makefile \ timeouts/Rules.shrc \ - timeouts/test-timeout.c + timeouts/test-timeout.c \ + timeouts/timeout-bitops.c -# XXXX Once we use timeouts, include this in an actual library. -EXTRA_DIST += \ - timeouts/timeout-bitops.c \ - timeout.c

1 0

[tor/master] Import timeouts.c directly from William Ahern's git.
by nickm＠torproject.org 09 May '16

09 May '16

commit 32e80ea3d32d5fd8207d16f9e5b26defa0d98a7c Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 13 08:58:43 2016 -0400 Import timeouts.c directly from William Ahern's git. Imported from here: https://github.com/wahern/timeout Imported as of upstream e5a9e8bfaa9c631bdc54002181795931b65bdc1a. All sources unmodified. --- src/ext/README | 4 + src/ext/include.am | 25 ++ src/ext/timeouts/Makefile | 68 +++ src/ext/timeouts/Rules.shrc | 40 ++ src/ext/timeouts/bench/Rules.mk | 49 +++ src/ext/timeouts/bench/bench-add.lua | 30 ++ src/ext/timeouts/bench/bench-aux.lua | 30 ++ src/ext/timeouts/bench/bench-del.lua | 25 ++ src/ext/timeouts/bench/bench-expire.lua | 29 ++ src/ext/timeouts/bench/bench-heap.c | 236 ++++++++++ src/ext/timeouts/bench/bench-llrb.c | 425 ++++++++++++++++++ src/ext/timeouts/bench/bench-wheel.c | 81 ++++ src/ext/timeouts/bench/bench.c | 293 +++++++++++++ src/ext/timeouts/bench/bench.h | 11 + src/ext/timeouts/bench/bench.plt | 19 + src/ext/timeouts/lua/Rules.mk | 20 + src/ext/timeouts/lua/timeout-lua.c | 396 +++++++++++++++++ src/ext/timeouts/test-timeout.c | 530 +++++++++++++++++++++++ src/ext/timeouts/timeout-bitops.c | 249 +++++++++++ src/ext/timeouts/timeout-debug.h | 77 ++++ src/ext/timeouts/timeout.c | 744 ++++++++++++++++++++++++++++++++ src/ext/timeouts/timeout.h | 253 +++++++++++ 22 files changed, 3634 insertions(+) diff --git a/src/ext/README b/src/ext/README index 7ce1bc3..c180927 100644 --- a/src/ext/README +++ b/src/ext/README @@ -73,3 +73,7 @@ readpassphrase.[ch] Portable readpassphrase implementation from OpenSSH portable, version 6.8p1. + +timeouts/ + + William Ahern's hierarchical timer-wheel implementation. MIT license. diff --git a/src/ext/include.am b/src/ext/include.am index bf678f2..b4281b9 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -10,6 +10,8 @@ EXTHEADERS = \ src/ext/tor_readpassphrase.h \ src/ext/strlcat.c \ src/ext/strlcpy.c \ + src/ext/timeouts/timeout.h \ + src/ext/timeouts/timeout-debug.h \ src/ext/tinytest_macros.h \ src/ext/tor_queue.h \ src/ext/siphash.h @@ -148,3 +150,26 @@ noinst_HEADERS += $(LIBKECCAK_TINY_HDRS) LIBKECCAK_TINY=src/ext/keccak-tiny/libkeccak-tiny.a noinst_LIBRARIES += $(LIBKECCAK_TINY) +EXTRA_DIST += \ + timeouts/bench/bench-add.lua \ + timeouts/bench/bench-aux.lua \ + timeouts/bench/bench.c \ + timeouts/bench/bench-del.lua \ + timeouts/bench/bench-expire.lua \ + timeouts/bench/bench.h \ + timeouts/bench/bench-heap.c \ + timeouts/bench/bench-llrb.c \ + timeouts/bench/bench.plt \ + timeouts/bench/bench-wheel.c \ + timeouts/bench/Rules.mk \ + timeouts/lua/Rules.mk \ + timeouts/lua/timeout-lua.c \ + timeouts/Makefile \ + timeouts/Rules.shrc \ + timeouts/test-timeout.c + +# XXXX Once we use timeouts, include this in an actual library. +EXTRA_DIST += \ + timeouts/timeout-bitops.c \ + timeout.c + diff --git a/src/ext/timeouts/Makefile b/src/ext/timeouts/Makefile new file mode 100644 index 0000000..554ebb9 --- /dev/null +++ b/src/ext/timeouts/Makefile @@ -0,0 +1,68 @@ +# NOTE: GNU Make 3.81 won't export MAKEFLAGS if .POSIX is specified, but +# Solaris make won't export MAKEFLAGS unless .POSIX is specified. +$(firstword ignore).POSIX: + +.DEFAULT_GOAL = all + +.SUFFIXES: + +all: + +# +# USER-MODIFIABLE MACROS +# +top_srcdir = . +top_builddir = . + +CFLAGS = -O2 -march=native -g -Wall -Wextra -Wno-unused-parameter -Wno-unused-function +SOFLAGS = $$(auto_soflags) +LIBS = $$(auto_libs) + +ALL_CPPFLAGS = -I$(top_srcdir) -DWHEEL_BIT=$(WHEEL_BIT) -DWHEEL_NUM=$(WHEEL_NUM) $(CPPFLAGS) +ALL_CFLAGS = $(CFLAGS) +ALL_SOFLAGS = $(SOFLAGS) +ALL_LDFLAGS = $(LDFLAGS) +ALL_LIBS = $(LIBS) + +LUA_API = 5.3 +LUA = lua +LUA51_CPPFLAGS = $(LUA_CPPFLAGS) +LUA52_CPPFLAGS = $(LUA_CPPFLAGS) +LUA53_CPPFLAGS = $(LUA_CPPFLAGS) + +WHEEL_BIT = 6 +WHEEL_NUM = 4 + +RM = rm -f + +# END MACROS + +SHRC = \ + top_srcdir="$(top_srcdir)"; \ + top_builddir="$(top_builddir)"; \ + . "$${top_srcdir}/Rules.shrc" + +LUA_APIS = 5.1 5.2 5.3 + +include $(top_srcdir)/lua/Rules.mk +include $(top_srcdir)/bench/Rules.mk + +all: test-timeout + +timeout.o: $(top_srcdir)/timeout.c +test-timeout.o: $(top_srcdir)/test-timeout.c + +timeout.o test-timeout.o: + @$(SHRC); echo_cmd $(CC) $(ALL_CFLAGS) -c -o $@ $${top_srcdir}/$(@F:%.o=%.c) $(ALL_CPPFLAGS) + +test-timeout: timeout.o test-timeout.o + @$(SHRC); echo_cmd $(CC) $(ALL_CPPFLAGS) $(ALL_CFLAGS) -o $@ timeout.o test-timeout.o + +.PHONY: clean clean~ + +clean: + $(RM) $(top_builddir)/test-timeout $(top_builddir)/*.o + $(RM) -r $(top_builddir)/*.dSYM + +clean~: + find $(top_builddir) $(top_srcdir) -name "*~" -exec $(RM) -- {} "+" diff --git a/src/ext/timeouts/Rules.shrc b/src/ext/timeouts/Rules.shrc new file mode 100644 index 0000000..ece75d4 --- /dev/null +++ b/src/ext/timeouts/Rules.shrc @@ -0,0 +1,40 @@ +# convert to absolute paths +top_srcdir="$(cd "${top_srcdir}" && pwd -L)" +top_builddir="$(cd "${top_builddir}" && pwd -L)" + +# Paths for Lua modules (benchmarks and installed modules) +export LUA_CPATH="${top_builddir}/lua/5.1/?.so;${top_builddir}/bench/?.so;;" +export LUA_PATH="${top_srcdir}/lua/?.lua;${top_srcdir}/bench/?.lua;;" +export LUA_CPATH_5_2="${top_builddir}/lua/5.2/?.so;${top_builddir}/bench/?.so;;" +export LUA_PATH_5_2="${top_srcdir}/lua/?.lua;${top_srcdir}/bench/?.lua;;" +export LUA_CPATH_5_3="${top_builddir}/lua/5.3/?.so;${top_builddir}/bench/?.so;;" +export LUA_PATH_5_3="${top_srcdir}/lua/?.lua;${top_srcdir}/bench/?.lua;;" + +# preserve stdout so we can print commands to terminal +exec 9>&1; +echo_cmd() { + printf "%s\n" "$*" >&9; + "$@"; +} + +auto_soflags() { + case "$(uname -s)" in + Darwin) + printf -- "-bundle -undefined dynamic_lookup" + ;; + *) + printf -- "-fPIC -shared" + ;; + esac +} + +auto_libs() { + case "$(uname -s)" in + Linux) + printf -- "-lrt" + ;; + *) + ;; + esac +} + diff --git a/src/ext/timeouts/bench/Rules.mk b/src/ext/timeouts/bench/Rules.mk new file mode 100644 index 0000000..3ee72f3 --- /dev/null +++ b/src/ext/timeouts/bench/Rules.mk @@ -0,0 +1,49 @@ +BENCH_MODS = bench.so $(BENCH_ALGOS:%=bench-%.so) +BENCH_ALGOS = wheel heap llrb +BENCH_OPS = add del expire + +$(top_builddir)/bench/bench.so: $(top_srcdir)/bench/bench.c +$(top_builddir)/bench/bench-wheel.so: $(top_srcdir)/bench/bench-wheel.c +$(top_builddir)/bench/bench-heap.so: $(top_srcdir)/bench/bench-heap.c +$(top_builddir)/bench/bench-llrb.so: $(top_srcdir)/bench/bench-llrb.c + +$(BENCH_MODS:%=$(top_builddir)/bench/%): $(top_srcdir)/timeout.h $(top_srcdir)/timeout.c $(top_srcdir)/bench/bench.h + mkdir -p $(@D) + @$(SHRC); echo_cmd $(CC) -o $@ $(top_srcdir)/bench/$(@F:%.so=%.c) $(ALL_CPPFLAGS) $(ALL_CFLAGS) $(ALL_SOFLAGS) $(ALL_LDFLAGS) $(ALL_LIBS) + +$(BENCH_OPS:%=$(top_builddir)/bench/wheel-%.dat): $(top_builddir)/bench/bench-wheel.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua +$(BENCH_OPS:%=$(top_builddir)/bench/heap-%.dat): $(top_builddir)/bench/bench-heap.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua +$(BENCH_OPS:%=$(top_builddir)/bench/llrb-%.dat): $(top_builddir)/bench/bench-llrb.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua + +$(BENCH_ALGOS:%=$(top_builddir)/bench/%-add.dat): $(top_srcdir)/bench/bench-add.lua + @$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-add.lua $${top_builddir}/bench/bench-$(@F:%-add.dat=%).so > $((a)F).tmp + mv $@.tmp $@ + +$(BENCH_ALGOS:%=$(top_builddir)/bench/%-del.dat): $(top_srcdir)/bench/bench-del.lua + @$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-del.lua $${top_builddir}/bench/bench-$(@F:%-del.dat=%).so > $((a)F).tmp + mv $@.tmp $@ + +$(BENCH_ALGOS:%=$(top_builddir)/bench/%-expire.dat): $(top_srcdir)/bench/bench-expire.lua + @$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-expire.lua $${top_builddir}/bench/bench-$(@F:%-expire.dat=%).so > $((a)F).tmp + mv $@.tmp $@ + +$(top_builddir)/bench/bench.eps: \ + $(BENCH_OPS:%=$(top_builddir)/bench/wheel-%.dat) \ + $(BENCH_OPS:%=$(top_builddir)/bench/heap-%.dat) +# $(BENCH_OPS:%=$(top_builddir)/bench/llrb-%.dat) + +$(top_builddir)/bench/bench.eps: $(top_srcdir)/bench/bench.plt + @$(SHRC); echo_cmd cd $(@D) && echo_cmd gnuplot $${top_srcdir}/bench/bench.plt > $((a)F).tmp + mv $@.tmp $@ + +$(top_builddir)/bench/bench.pdf: $(top_builddir)/bench/bench.eps + @$(SHRC); echo_cmd ps2pdf $${top_builddir}/bench/bench.eps $@ + +bench-mods: $(BENCH_MODS:%=$(top_builddir)/bench/%) + +bench-all: $(top_builddir)/bench/bench.pdf + +bench-clean: + $(RM) -r $(top_builddir)/bench/*.so $(top_builddir)/bench/*.dSYM + $(RM) $(top_builddir)/bench/*.dat $(top_builddir)/bench/*.tmp + $(RM) $(top_builddir)/bench/bench.{eps,pdf} diff --git a/src/ext/timeouts/bench/bench-add.lua b/src/ext/timeouts/bench/bench-add.lua new file mode 100755 index 0000000..64a921d --- /dev/null +++ b/src/ext/timeouts/bench/bench-add.lua @@ -0,0 +1,30 @@ +#!/usr/bin/env lua + +local bench = require"bench" +local aux = require"bench-aux" + +local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so") +local limit = tonumber(aux.optenv("BENCH_N", 1000000)) +local step = tonumber(aux.optenv("BENCH_S", limit / 100)) +local exp_step = tonumber(aux.optenv("BENCH_E", 1.0)) +local verbose = aux.toboolean(os.getenv("BENCH_V", false)) + +local B = bench.new(lib, count, nil, verbose) +local fill_count, fill_last = B:fill(limit) + +for i=0,limit,step do + local exp_elapsed, fill_elapsed, fill_rate + + -- expire all timeouts + --exp_elapsed = aux.time(B.expire, B, fill_count, fill_last * exp_step) + exp_elapsed = aux.time(B.del, B, 0, fill_count) + assert(B:empty()) + + -- add i timeouts + fill_elapsed, fill_count, fill_last = aux.time(B.fill, B, i) + assert(fill_count == i) + fill_rate = fill_elapsed > 0 and (fill_count / fill_elapsed) or 0 + + local fmt = verbose and "%d\t%f\t(%d/s)\t(exp:%f)" or "%d\t%f" + aux.say(fmt, i, fill_elapsed, fill_rate, exp_elapsed) +end diff --git a/src/ext/timeouts/bench/bench-aux.lua b/src/ext/timeouts/bench/bench-aux.lua new file mode 100644 index 0000000..6321247 --- /dev/null +++ b/src/ext/timeouts/bench/bench-aux.lua @@ -0,0 +1,30 @@ +local bench = require"bench" +local clock = bench.clock + +local aux = {} + +local function time_return(begun, ...) + local duration = clock() - begun + return duration, ... +end + +function aux.time(f, ...) + local begun = clock() + return time_return(begun, f(...)) +end + +function aux.say(...) + print(string.format(...)) +end + +function aux.toboolean(s) + return tostring(s):match("^[1TtYy]") and true or false +end + +function aux.optenv(k, def) + local s = os.getenv(k) + + return (s and #s > 0 and s) or def +end + +return aux diff --git a/src/ext/timeouts/bench/bench-del.lua b/src/ext/timeouts/bench/bench-del.lua new file mode 100755 index 0000000..4306745 --- /dev/null +++ b/src/ext/timeouts/bench/bench-del.lua @@ -0,0 +1,25 @@ +#!/usr/bin/env lua + +local bench = require"bench" +local aux = require"bench-aux" + +local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so") +local limit = tonumber(aux.optenv("BENCH_N", 1000000)) +local step = tonumber(aux.optenv("BENCH_S", limit / 100)) +local verbose = aux.toboolean(os.getenv("BENCH_V", false)) + +local B = bench.new(lib, count) + +for i=0,limit,step do + -- add i timeouts + local fill_elapsed, fill_count = aux.time(B.fill, B, i, 60 * 1000000) + assert(i == fill_count) + + --- delete i timeouts + local del_elapsed = aux.time(B.del, B, 0, fill_count) + assert(B:empty()) + local del_rate = i > 0 and i / del_elapsed or 0 + + local fmt = verbose and "%d\t%f\t(%d/s)\t(fill:%f)" or "%d\t%f" + aux.say(fmt, i, del_elapsed, del_rate, fill_elapsed) +end diff --git a/src/ext/timeouts/bench/bench-expire.lua b/src/ext/timeouts/bench/bench-expire.lua new file mode 100755 index 0000000..3e6374e --- /dev/null +++ b/src/ext/timeouts/bench/bench-expire.lua @@ -0,0 +1,29 @@ +#!/usr/bin/env lua + +local bench = require"bench" +local aux = require"bench-aux" + +local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so") +local limit = tonumber(aux.optenv("BENCH_N", 1000000)) +local step = tonumber(aux.optenv("BENCH_S", limit / 100)) +-- expire 1/1000 * #timeouts per clock update +local exp_step = tonumber(aux.optenv("BENCH_E", 0.0001)) +local verbose = aux.toboolean(os.getenv("BENCH_V", false)) + +local B = require"bench".new(lib, count) + +for i=0,limit,step do + -- add i timeouts + local fill_elapsed, fill_count, fill_last = aux.time(B.fill, B, i) + + -- expire timeouts by iteratively updating clock. exp_step is the + -- approximate number of timeouts (as a fraction of the total number + -- of timeouts) that will expire per update. + local exp_elapsed, exp_count = aux.time(B.expire, B, fill_count, math.floor(fill_last * exp_step)) + assert(exp_count == i) + assert(B:empty()) + local exp_rate = i > 0 and i / exp_elapsed or 0 + + local fmt = verbose and "%d\t%f\t(%d/s)\t(fill:%f)" or "%d\t%f" + aux.say(fmt, i, exp_elapsed, exp_rate, fill_elapsed) +end diff --git a/src/ext/timeouts/bench/bench-heap.c b/src/ext/timeouts/bench/bench-heap.c new file mode 100644 index 0000000..f1166a4 --- /dev/null +++ b/src/ext/timeouts/bench/bench-heap.c @@ -0,0 +1,236 @@ +/* + * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin(a)gmail.com> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef _MIN_HEAP_H_ +#define _MIN_HEAP_H_ + +#include <stdlib.h> +#include <err.h> +#include "timeout.h" +#include "bench.h" + +#define min_heap_idx interval + +typedef timeout_t min_heap_idx_t; + +typedef struct min_heap +{ + struct timeout** p; + unsigned n, a; + timeout_t curtime; +} min_heap_t; + +static inline void min_heap_ctor(min_heap_t* s); +static inline void min_heap_dtor(min_heap_t* s); +static inline void min_heap_elem_init(struct timeout* e); +static inline int min_heap_elem_greater(struct timeout *a, struct timeout *b); +static inline int min_heap_empty(min_heap_t* s); +static inline unsigned min_heap_size(min_heap_t* s); +static inline struct timeout* min_heap_top(min_heap_t* s); +static inline int min_heap_reserve(min_heap_t* s, unsigned n); +static inline int min_heap_push(min_heap_t* s, struct timeout* e); +static inline struct timeout* min_heap_pop(min_heap_t* s); +static inline int min_heap_erase(min_heap_t* s, struct timeout* e); +static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e); +static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e); + +int min_heap_elem_greater(struct timeout *a, struct timeout *b) +{ + return a->expires > b->expires; +} + +void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } +void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); } +void min_heap_elem_init(struct timeout* e) { e->min_heap_idx = -1; } +int min_heap_empty(min_heap_t* s) { return 0u == s->n; } +unsigned min_heap_size(min_heap_t* s) { return s->n; } +struct timeout* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; } + +int min_heap_push(min_heap_t* s, struct timeout* e) +{ + if(min_heap_reserve(s, s->n + 1)) + return -1; + min_heap_shift_up_(s, s->n++, e); + return 0; +} + +struct timeout* min_heap_pop(min_heap_t* s) +{ + if(s->n) + { + struct timeout* e = *s->p; + min_heap_shift_down_(s, 0u, s->p[--s->n]); + e->min_heap_idx = -1; + return e; + } + return 0; +} + +int min_heap_erase(min_heap_t* s, struct timeout* e) +{ + if(((min_heap_idx_t)-1) != e->min_heap_idx) + { + struct timeout *last = s->p[--s->n]; + unsigned parent = (e->min_heap_idx - 1) / 2; + /* we replace e with the last element in the heap. We might need to + shift it upward if it is less than its parent, or downward if it is + greater than one or both its children. Since the children are known + to be less than the parent, it can't need to shift both up and + down. */ + if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) + min_heap_shift_up_(s, e->min_heap_idx, last); + else + min_heap_shift_down_(s, e->min_heap_idx, last); + e->min_heap_idx = -1; + return 0; + } + return -1; +} + +int min_heap_reserve(min_heap_t* s, unsigned n) +{ + if(s->a < n) + { + struct timeout** p; + unsigned a = s->a ? s->a * 2 : 8; + if(a < n) + a = n; + if(!(p = (struct timeout**)realloc(s->p, a * sizeof *p))) + return -1; + s->p = p; + s->a = a; + } + return 0; +} + +void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e) +{ + unsigned parent = (hole_index - 1) / 2; + while(hole_index && min_heap_elem_greater(s->p[parent], e)) + { + (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index; + hole_index = parent; + parent = (hole_index - 1) / 2; + } + (s->p[hole_index] = e)->min_heap_idx = hole_index; +} + +void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e) +{ + unsigned min_child = 2 * (hole_index + 1); + while(min_child <= s->n) + { + min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); + if(!(min_heap_elem_greater(e, s->p[min_child]))) + break; + (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index; + hole_index = min_child; + min_child = 2 * (hole_index + 1); + } + min_heap_shift_up_(s, hole_index, e); +} + +#endif /* _MIN_HEAP_H_ */ + + +static void *init(struct timeout *timeout, size_t count, int verbose) { + min_heap_t *H; + size_t i; + + H = calloc(1, sizeof *H); + + min_heap_ctor(H); + if (0 != min_heap_reserve(H, count)) + err(1, "realloc"); + + for (i = 0; i < count; i++) { + min_heap_elem_init(&timeout[i]); + } + + return H; +} /* init() */ + + +static void add(void *ctx, struct timeout *to, timeout_t expires) { + min_heap_t *H = ctx; + min_heap_erase(H, to); + to->expires = H->curtime + expires; + if (0 != min_heap_push(H, to)) + err(1, "realloc"); +} /* add() */ + + +static void del(void *ctx, struct timeout *to) { + min_heap_erase(ctx, to); +} /* del() */ + + +static struct timeout *get(void *ctx) { + min_heap_t *H = ctx; + struct timeout *to; + + if ((to = min_heap_top(H)) && to->expires <= H->curtime) + return min_heap_pop(H); + + return NULL; +} /* get() */ + + +static void update(void *ctx, timeout_t ts) { + min_heap_t *H = ctx; + H->curtime = ts; +} /* update() */ + + +static void check(void *ctx) { + return; +} /* check() */ + + +static int empty(void *ctx) { + min_heap_t *H = ctx; + + return (NULL == min_heap_top(H)); +} /* empty() */ + + +static void destroy(void *H) { + free(H); + return; +} /* destroy() */ + + +const struct benchops benchops = { + .init = &init, + .add = &add, + .del = &del, + .get = &get, + .update = &update, + .check = &check, + .empty = &empty, + .destroy = &destroy, +}; + diff --git a/src/ext/timeouts/bench/bench-llrb.c b/src/ext/timeouts/bench/bench-llrb.c new file mode 100644 index 0000000..bdb02f0 --- /dev/null +++ b/src/ext/timeouts/bench/bench-llrb.c @@ -0,0 +1,425 @@ +/* ========================================================================== + * llrb.h - Iterative Left-leaning Red-Black Tree. + * -------------------------------------------------------------------------- + * Copyright (c) 2011, 2013 William Ahern <william(a)25thandClement.com> + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * -------------------------------------------------------------------------- + * CREDITS: + * o Algorithm courtesy of Robert Sedgewick, "Left-leaning Red-Black + * Trees" (September 2008); and Robert Sedgewick and Kevin Wayne, + * Algorithms (4th ed. 2011). + * + * Sedgewick touts the simplicity of the recursive implementation, + * but at least for the 2-3 tree variant the iterative approach is + * almost line-for-line identical. The magic of C pointers helps; + * it'd be uglier with Java. + * + * A couple of missing NULL checks were added to Sedgewick's deletion + * example, and insert was optimized to short-circuit rotations when + * walking up the tree. + * + * o Code implemented in the fashion of Niels Provos' excellent *BSD + * sys/tree.h pre-processor library. + * + * Regarding relative performance, I've refrained from sharing my own + * benchmarks. Differences in run-time speed were too correlated to + * compiler options and other external factors. + * + * Provos' delete implementation doesn't need to start at the root of + * the tree. However, RB_REMOVE must be passed the actual node to be + * removed. LLRB_REMOVE merely requires a key, much like + * RB_FIND/LLRB_FIND. + * ========================================================================== + */ +#ifndef LLRB_H +#define LLRB_H + +#define LLRB_VENDOR "william(a)25thandClement.com" +#define LLRB_VERSION 0x20130925 + +#ifndef LLRB_STATIC +#ifdef __GNUC__ +#define LLRB_STATIC __attribute__((__unused__)) static +#else +#define LLRB_STATIC static +#endif +#endif + +#define LLRB_HEAD(name, type) \ +struct name { struct type *rbh_root; } + +#define LLRB_INITIALIZER(root) { 0 } + +#define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0) + +#define LLRB_BLACK 0 +#define LLRB_RED 1 + +#define LLRB_ENTRY(type) \ +struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; } + +#define LLRB_LEFT(elm, field) (elm)->field.rbe_left +#define LLRB_RIGHT(elm, field) (elm)->field.rbe_right +#define LLRB_PARENT(elm, field) (elm)->field.rbe_parent +#define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field)) +#define LLRB_COLOR(elm, field) (elm)->field.rbe_color +#define LLRB_ROOT(head) (head)->rbh_root +#define LLRB_EMPTY(head) ((head)->rbh_root == 0) +#define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED) + +#define LLRB_PROTOTYPE(name, type, field, cmp) \ + LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,) +#define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \ + LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC) +#define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ +attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \ +attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \ +attr struct type *name##_LLRB_FIND(struct name *, struct type *); \ +attr struct type *name##_LLRB_MIN(struct type *); \ +attr struct type *name##_LLRB_MAX(struct type *); \ +attr struct type *name##_LLRB_NEXT(struct type *); + +#define LLRB_GENERATE(name, type, field, cmp) \ + LLRB_GENERATE_INTERNAL(name, type, field, cmp,) +#define LLRB_GENERATE_STATIC(name, type, field, cmp) \ + LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC) +#define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ +static inline void name##_LLRB_ROTL(struct type **pivot) { \ + struct type *a = *pivot; \ + struct type *b = LLRB_RIGHT(a, field); \ + if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \ + LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \ + LLRB_LEFT(b, field) = a; \ + LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \ + LLRB_COLOR(a, field) = LLRB_RED; \ + LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \ + LLRB_PARENT(a, field) = b; \ + *pivot = b; \ +} \ +static inline void name##_LLRB_ROTR(struct type **pivot) { \ + struct type *b = *pivot; \ + struct type *a = LLRB_LEFT(b, field); \ + if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \ + LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \ + LLRB_RIGHT(a, field) = b; \ + LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \ + LLRB_COLOR(b, field) = LLRB_RED; \ + LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \ + LLRB_PARENT(b, field) = a; \ + *pivot = a; \ +} \ +static inline void name##_LLRB_FLIP(struct type *root) { \ + LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \ + LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \ + LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \ +} \ +static inline void name##_LLRB_FIXUP(struct type **root) { \ + if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \ + name##_LLRB_ROTL(root); \ + if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \ + name##_LLRB_ROTR(root); \ + if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \ + name##_LLRB_FLIP(*root); \ +} \ +attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \ + struct type **root = &LLRB_ROOT(head); \ + struct type *parent = 0; \ + while (*root) { \ + int comp = (cmp)((elm), (*root)); \ + parent = *root; \ + if (comp < 0) \ + root = &LLRB_LEFT(*root, field); \ + else if (comp > 0) \ + root = &LLRB_RIGHT(*root, field); \ + else \ + return *root; \ + } \ + LLRB_LEFT((elm), field) = 0; \ + LLRB_RIGHT((elm), field) = 0; \ + LLRB_COLOR((elm), field) = LLRB_RED; \ + LLRB_PARENT((elm), field) = parent; \ + *root = (elm); \ + while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \ + root = LLRB_EDGE(head, parent, field); \ + parent = LLRB_PARENT(parent, field); \ + name##_LLRB_FIXUP(root); \ + } \ + LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \ + return 0; \ +} \ +static inline void name##_LLRB_MOVL(struct type **pivot) { \ + name##_LLRB_FLIP(*pivot); \ + if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \ + name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \ + name##_LLRB_ROTL(pivot); \ + name##_LLRB_FLIP(*pivot); \ + } \ +} \ +static inline void name##_LLRB_MOVR(struct type **pivot) { \ + name##_LLRB_FLIP(*pivot); \ + if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \ + name##_LLRB_ROTR(pivot); \ + name##_LLRB_FLIP(*pivot); \ + } \ +} \ +static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \ + struct type **pivot = root, *deleted, *parent; \ + while (LLRB_LEFT(*pivot, field)) { \ + if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \ + name##_LLRB_MOVL(pivot); \ + pivot = &LLRB_LEFT(*pivot, field); \ + } \ + deleted = *pivot; \ + parent = LLRB_PARENT(*pivot, field); \ + *pivot = 0; \ + while (root != pivot) { \ + pivot = LLRB_EDGE(head, parent, field); \ + parent = LLRB_PARENT(parent, field); \ + name##_LLRB_FIXUP(pivot); \ + } \ + return deleted; \ +} \ +attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \ + struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \ + int comp; \ + while (*root) { \ + parent = LLRB_PARENT(*root, field); \ + comp = (cmp)(elm, *root); \ + if (comp < 0) { \ + if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \ + name##_LLRB_MOVL(root); \ + root = &LLRB_LEFT(*root, field); \ + } else { \ + if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \ + name##_LLRB_ROTR(root); \ + comp = (cmp)(elm, *root); \ + } \ + if (!comp && !LLRB_RIGHT(*root, field)) { \ + deleted = *root; \ + *root = 0; \ + break; \ + } \ + if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \ + name##_LLRB_MOVR(root); \ + comp = (cmp)(elm, *root); \ + } \ + if (!comp) { \ + struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \ + LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \ + LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \ + if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \ + LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \ + if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \ + LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \ + deleted = *root; \ + *root = orphan; \ + parent = *root; \ + break; \ + } else \ + root = &LLRB_RIGHT(*root, field); \ + } \ + } \ + while (parent) { \ + root = LLRB_EDGE(head, parent, field); \ + parent = LLRB_PARENT(parent, field); \ + name##_LLRB_FIXUP(root); \ + } \ + if (LLRB_ROOT(head)) \ + LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \ + return deleted; \ +} \ +attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \ + struct type *elm = LLRB_ROOT(head); \ + while (elm) { \ + int comp = (cmp)(key, elm); \ + if (comp < 0) \ + elm = LLRB_LEFT(elm, field); \ + else if (comp > 0) \ + elm = LLRB_RIGHT(elm, field); \ + else \ + return elm; \ + } \ + return 0; \ +} \ +attr struct type *name##_LLRB_MIN(struct type *elm) { \ + while (elm && LLRB_LEFT(elm, field)) \ + elm = LLRB_LEFT(elm, field); \ + return elm; \ +} \ +attr struct type *name##_LLRB_MAX(struct type *elm) { \ + while (elm && LLRB_RIGHT(elm, field)) \ + elm = LLRB_RIGHT(elm, field); \ + return elm; \ +} \ +attr struct type *name##_LLRB_NEXT(struct type *elm) { \ + if (LLRB_RIGHT(elm, field)) { \ + return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \ + } else if (LLRB_PARENT(elm, field)) { \ + if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \ + return LLRB_PARENT(elm, field); \ + while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \ + elm = LLRB_PARENT(elm, field); \ + return LLRB_PARENT(elm, field); \ + } else return 0; \ +} + +#define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm)) +#define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm)) +#define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm)) +#define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm)) +#define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head))) +#define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head))) +#define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm)) + +#define LLRB_FOREACH(elm, name, head) \ +for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm))) + +#endif /* LLRB_H */ + + +#include <stdlib.h> + +#include "timeout.h" +#include "bench.h" + + +struct rbtimeout { + timeout_t expires; + + int pending; + + LLRB_ENTRY(rbtimeout) rbe; +}; + +struct rbtimeouts { + timeout_t curtime; + LLRB_HEAD(tree, rbtimeout) tree; +}; + + +static int timeoutcmp(struct rbtimeout *a, struct rbtimeout *b) { + if (a->expires < b->expires) { + return -1; + } else if (a->expires > b->expires) { + return 1; + } else if (a < b) { + return -1; + } else if (a > b) { + return 1; + } else { + return 0; + } +} /* timeoutcmp() */ + +LLRB_GENERATE_STATIC(tree, rbtimeout, rbe, timeoutcmp) + +static void *init(struct timeout *timeout, size_t count, int verbose) { + struct rbtimeouts *T; + size_t i; + + T = malloc(sizeof *T); + T->curtime = 0; + LLRB_INIT(&T->tree); + + for (i = 0; i < count; i++) { + struct rbtimeout *to = (void *)&timeout[i]; + to->expires = 0; + to->pending = 0; + } + + return T; +} /* init() */ + + +static void add(void *ctx, struct timeout *_to, timeout_t expires) { + struct rbtimeouts *T = ctx; + struct rbtimeout *to = (void *)_to; + + if (to->pending) + LLRB_REMOVE(tree, &T->tree, to); + + to->expires = T->curtime + expires; + LLRB_INSERT(tree, &T->tree, to); + to->pending = 1; +} /* add() */ + + +static void del(void *ctx, struct timeout *_to) { + struct rbtimeouts *T = ctx; + struct rbtimeout *to = (void *)_to; + + LLRB_REMOVE(tree, &T->tree, to); + to->pending = 0; + to->expires = 0; +} /* del() */ + + +static struct timeout *get(void *ctx) { + struct rbtimeouts *T = ctx; + struct rbtimeout *to; + + if ((to = LLRB_MIN(tree, &T->tree)) && to->expires <= T->curtime) { + LLRB_REMOVE(tree, &T->tree, to); + to->pending = 0; + to->expires = 0; + + return (void *)to; + } + + return NULL; +} /* get() */ + + +static void update(void *ctx, timeout_t ts) { + struct rbtimeouts *T = ctx; + T->curtime = ts; +} /* update() */ + + +static void check(void *ctx) { + return; +} /* check() */ + + +static int empty(void *ctx) { + struct rbtimeouts *T = ctx; + + return LLRB_EMPTY(&T->tree); +} /* empty() */ + + +static void destroy(void *ctx) { + free(ctx); + return; +} /* destroy() */ + + +const struct benchops benchops = { + .init = &init, + .add = &add, + .del = &del, + .get = &get, + .update = &update, + .check = &check, + .empty = &empty, + .destroy = &destroy, +}; + diff --git a/src/ext/timeouts/bench/bench-wheel.c b/src/ext/timeouts/bench/bench-wheel.c new file mode 100644 index 0000000..0cba1af --- /dev/null +++ b/src/ext/timeouts/bench/bench-wheel.c @@ -0,0 +1,81 @@ +#include <stdlib.h> + +#define TIMEOUT_PUBLIC static + +#include "timeout.h" +#include "timeout.c" +#include "bench.h" + + +static void *init(struct timeout *timeout, size_t count, int verbose) { + struct timeouts *T; + size_t i; + int error; + + T = timeouts_open(TIMEOUT_mHZ, &error); + + for (i = 0; i < count; i++) { + timeout_init(&timeout[i], 0); + } + +#if TIMEOUT_DEBUG - 0 + timeout_debug = verbose; +#endif + + return T; +} /* init() */ + + +static void add(void *T, struct timeout *to, timeout_t expires) { + timeouts_add(T, to, expires); +} /* add() */ + + +static void del(void *T, struct timeout *to) { + timeouts_del(T, to); +} /* del() */ + + +static struct timeout *get(void *T) { + return timeouts_get(T); +} /* get() */ + + +static void update(void *T, timeout_t ts) { + timeouts_update(T, ts); +} /* update() */ + + +static void (check)(void *T) { + if (!timeouts_check(T, stderr)) + _Exit(1); +} /* check() */ + + +static int empty(void *T) { + return !(timeouts_pending(T) || timeouts_expired(T)); +} /* empty() */ + + +static struct timeout *next(void *T, struct timeouts_it *it) { + return timeouts_next(T, it); +} /* next() */ + + +static void destroy(void *T) { + timeouts_close(T); +} /* destroy() */ + + +const struct benchops benchops = { + .init = &init, + .add = &add, + .del = &del, + .get = &get, + .update = &update, + .check = &check, + .empty = &empty, + .next = &next, + .destroy = &destroy +}; + diff --git a/src/ext/timeouts/bench/bench.c b/src/ext/timeouts/bench/bench.c new file mode 100644 index 0000000..0d4cee4 --- /dev/null +++ b/src/ext/timeouts/bench/bench.c @@ -0,0 +1,293 @@ +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <errno.h> +#include <unistd.h> +#include <dlfcn.h> + +#if __APPLE__ +#include <mach/mach_time.h> +#endif + +#include <lua.h> +#include <lualib.h> +#include <lauxlib.h> + +#include "timeout.h" +#include "bench.h" + +#if LUA_VERSION_NUM < 502 +static int lua_absindex(lua_State *L, int idx) { + return (idx > 0 || idx <= LUA_REGISTRYINDEX)? idx : lua_gettop(L) + idx + 1; +} /* lua_absindex() */ + +static void luaL_setfuncs(lua_State *L, const luaL_Reg *l, int nup) { + int i, t = lua_absindex(L, -1 - nup); + + for (; l->name; l++) { + for (i = 0; i < nup; i++) + lua_pushvalue(L, -nup); + lua_pushcclosure(L, l->func, nup); + lua_setfield(L, t, l->name); + } + + lua_pop(L, nup); +} /* luaL_setfuncs() */ + +#define luaL_newlibtable(L, l) \ + lua_createtable(L, 0, (sizeof (l) / sizeof *(l)) - 1) + +#define luaL_newlib(L, l) \ + (luaL_newlibtable((L), (l)), luaL_setfuncs((L), (l), 0)) +#endif + +#ifndef MAX +#define MAX(a, b) (((a) > (b))? (a) : (b)) +#endif + + +struct bench { + const char *path; + void *solib; + size_t count; + timeout_t timeout_max; + int verbose; + + void *state; + struct timeout *timeout; + struct benchops ops; + timeout_t curtime; +}; /* struct bench */ + + +#if __APPLE__ +static mach_timebase_info_data_t timebase; +#endif + + +static int long long monotime(void) { +#if __APPLE__ + unsigned long long abt; + + abt = mach_absolute_time(); + abt = abt * timebase.numer / timebase.denom; + + return abt / 1000LL; +#else + struct timespec ts; + + clock_gettime(CLOCK_MONOTONIC, &ts); + + return (ts.tv_sec * 1000000L) + (ts.tv_nsec / 1000L); +#endif +} /* monotime() */ + + +static int bench_clock(lua_State *L) { + lua_pushnumber(L, (double)monotime() / 1000000L); + + return 1; +} /* bench_clock() */ + + +static int bench_new(lua_State *L) { + const char *path = luaL_checkstring(L, 1); + size_t count = luaL_optinteger(L, 2, 1000000); + timeout_t timeout_max = luaL_optinteger(L, 3, 300 * 1000000L); + int verbose = (lua_isnone(L, 4))? 0 : lua_toboolean(L, 4); + struct bench *B; + struct benchops *ops; + + B = lua_newuserdata(L, sizeof *B); + memset(B, 0, sizeof *B); + + luaL_getmetatable(L, "BENCH*"); + lua_setmetatable(L, -2); + + B->count = count; + B->timeout_max = timeout_max; + B->verbose = verbose; + + if (!(B->timeout = calloc(count, sizeof *B->timeout))) + return luaL_error(L, "%s", strerror(errno)); + + if (!(B->solib = dlopen(path, RTLD_NOW|RTLD_LOCAL))) + return luaL_error(L, "%s: %s", path, dlerror()); + + if (!(ops = dlsym(B->solib, "benchops"))) + return luaL_error(L, "%s: %s", path, dlerror()); + + B->ops = *ops; + B->state = B->ops.init(B->timeout, B->count, B->verbose); + + return 1; +} /* bench_new() */ + + +static int bench_add(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + unsigned i; + timeout_t t; + + i = (lua_isnoneornil(L, 2))? random() % B->count : (unsigned)luaL_checkinteger(L, 2); + t = (lua_isnoneornil(L, 3))? random() % B->timeout_max : (unsigned)luaL_checkinteger(L, 3); + + B->ops.add(B->state, &B->timeout[i], t); + + return 0; +} /* bench_add() */ + + +static int bench_del(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + size_t i = luaL_optinteger(L, 2, random() % B->count); + size_t j = luaL_optinteger(L, 3, i); + + while (i <= j && i < B->count) { + B->ops.del(B->state, &B->timeout[i]); + ++i; + } + + return 0; +} /* bench_del() */ + + +static int bench_fill(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + size_t count = luaL_optinteger(L, 2, B->count); + long timeout_inc = luaL_optinteger(L, 3, -1), timeout_max = 0, timeout; + size_t i; + + if (timeout_inc < 0) { + for (i = 0; i < count; i++) { + timeout = random() % B->timeout_max; + B->ops.add(B->state, &B->timeout[i], timeout); + timeout_max = MAX(timeout, timeout_max); + } + } else { + for (i = 0; i < count; i++) { + timeout = timeout_inc + i; + B->ops.add(B->state, &B->timeout[i], timeout_inc + i); + timeout_max = MAX(timeout, timeout_max); + } + } + + lua_pushinteger(L, (lua_Integer)count); + lua_pushinteger(L, (lua_Integer)timeout_max); + + return 2; +} /* bench_fill() */ + + +static int bench_expire(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + unsigned count = luaL_optinteger(L, 2, B->count); + unsigned step = luaL_optinteger(L, 3, 300000); + size_t i = 0; + + while (i < count && !B->ops.empty(B->state)) { + B->curtime += step; + B->ops.update(B->state, B->curtime); + + while (B->ops.get(B->state)) + i++; + } + + lua_pushinteger(L, (lua_Integer)i); + + return 1; +} /* bench_expire() */ + + +static int bench_empty(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + + lua_pushboolean(L, B->ops.empty(B->state)); + + return 1; +} /* bench_empty() */ + + +static int bench__next(lua_State *L) { + struct bench *B = lua_touserdata(L, lua_upvalueindex(1)); + struct timeouts_it *it = lua_touserdata(L, lua_upvalueindex(2)); + struct timeout *to; + + if (!B->ops.next || !(to = B->ops.next(B->state, it))) + return 0; + + lua_pushinteger(L, luaL_optinteger(L, 2, 0) + 1); + + lua_newtable(L); + lua_pushinteger(L, to->expires); + lua_setfield(L, -2, "expires"); + + return 2; +} /* bench__next() */ + +static int bench__pairs(lua_State *L) { + struct timeouts_it *it; + + lua_settop(L, 1); + + it = lua_newuserdata(L, sizeof *it); + TIMEOUTS_IT_INIT(it, TIMEOUTS_ALL); + + lua_pushcclosure(L, &bench__next, 2); + lua_pushvalue(L, 1); + lua_pushinteger(L, 0); + + return 3; +} /* bench__pairs() */ + + +static int bench__gc(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + + if (B->state) { + B->ops.destroy(B->state); + B->state = NULL; + } + + return 0; +} /* bench__gc() */ + + +static const luaL_Reg bench_methods[] = { + { "add", &bench_add }, + { "del", &bench_del }, + { "fill", &bench_fill }, + { "expire", &bench_expire }, + { "empty", &bench_empty }, + { "close", &bench__gc }, + { NULL, NULL } +}; + +static const luaL_Reg bench_metatable[] = { + { "__pairs", &bench__pairs }, + { "__gc", &bench__gc }, + { NULL, NULL } +}; + +static const luaL_Reg bench_globals[] = { + { "new", &bench_new }, + { "clock", &bench_clock }, + { NULL, NULL } +}; + +int luaopen_bench(lua_State *L) { +#if __APPLE__ + mach_timebase_info(&timebase); +#endif + + if (luaL_newmetatable(L, "BENCH*")) { + luaL_setfuncs(L, bench_metatable, 0); + luaL_newlib(L, bench_methods); + lua_setfield(L, -2, "__index"); + } + + luaL_newlib(L, bench_globals); + + return 1; +} /* luaopen_bench() */ + diff --git a/src/ext/timeouts/bench/bench.h b/src/ext/timeouts/bench/bench.h new file mode 100644 index 0000000..bc1f7cf --- /dev/null +++ b/src/ext/timeouts/bench/bench.h @@ -0,0 +1,11 @@ +struct benchops { + void *(*init)(struct timeout *, size_t, int); + void (*add)(void *, struct timeout *, timeout_t); + void (*del)(void *, struct timeout *); + struct timeout *(*get)(void *); + void (*update)(void *, timeout_t); + void (*check)(void *); + int (*empty)(void *); + struct timeout *(*next)(void *, struct timeouts_it *); + void (*destroy)(void *); +}; /* struct benchops() */ diff --git a/src/ext/timeouts/bench/bench.plt b/src/ext/timeouts/bench/bench.plt new file mode 100644 index 0000000..6e143c6 --- /dev/null +++ b/src/ext/timeouts/bench/bench.plt @@ -0,0 +1,19 @@ +set terminal postscript color + +set key top left +set xlabel "Number of timeouts" +set ylabel "Time\n(microseconds)" +#set logscale x + +set title "Time spent installing timeouts" font ",20" +plot 'heap-add.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \ + 'wheel-add.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green" + +set title "Time spent deleting timeouts" font ",20" +plot 'heap-del.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \ + 'wheel-del.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green" + +set title "Time spent expiring timeouts\n(by iteratively updating clock ~1000 times)" font ",20" +plot 'heap-expire.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \ + 'wheel-expire.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green" + diff --git a/src/ext/timeouts/lua/Rules.mk b/src/ext/timeouts/lua/Rules.mk new file mode 100644 index 0000000..0f06fce --- /dev/null +++ b/src/ext/timeouts/lua/Rules.mk @@ -0,0 +1,20 @@ +$(LUA_APIS:%=$(top_builddir)/lua/%/timeout.so): $(top_srcdir)/lua/timeout-lua.c $(top_srcdir)/timeout.h $(top_srcdir)/timeout.c + mkdir -p $(@D) + @$(SHRC); echo_cmd $(CC) -o $@ $(top_srcdir)/lua/timeout-lua.c -I$(top_srcdir) -DWHEEL_BIT=$(WHEEL_BIT) -DWHEEL_NUM=$(WHEEL_NUM) $(LUA53_CPPFLAGS) $(ALL_CPPFLAGS) $(ALL_CFLAGS) $(ALL_SOFLAGS) $(ALL_LDFLAGS) $(ALL_LIBS) + +$(top_builddir)/lua/5.1/timeouts.so: $(top_builddir)/lua/5.1/timeout.so +$(top_builddir)/lua/5.2/timeouts.so: $(top_builddir)/lua/5.2/timeout.so +$(top_builddir)/lua/5.3/timeouts.so: $(top_builddir)/lua/5.3/timeout.so + +$(LUA_APIS:%=$(top_builddir)/lua/%/timeouts.so): + cd $(@D) && ln -fs timeout.so timeouts.so + +lua-5.1: $(top_builddir)/lua/5.1/timeout.so $(top_builddir)/lua/5.1/timeouts.so +lua-5.2: $(top_builddir)/lua/5.2/timeout.so $(top_builddir)/lua/5.2/timeouts.so +lua-5.3: $(top_builddir)/lua/5.3/timeout.so $(top_builddir)/lua/5.3/timeouts.so + +lua-clean: + $(RM) -r $(top_builddir)/lua/5.? + +clean: lua-clean + diff --git a/src/ext/timeouts/lua/timeout-lua.c b/src/ext/timeouts/lua/timeout-lua.c new file mode 100644 index 0000000..4d4e54c --- /dev/null +++ b/src/ext/timeouts/lua/timeout-lua.c @@ -0,0 +1,396 @@ +#include <assert.h> +#include <string.h> + +#include <lua.h> +#include <lualib.h> +#include <lauxlib.h> + +#if LUA_VERSION_NUM != 503 +#error only Lua 5.3 supported +#endif + +#define TIMEOUT_PUBLIC static +#include "timeout.h" +#include "timeout.c" + +#define TIMEOUT_METANAME "struct timeout" +#define TIMEOUTS_METANAME "struct timeouts*" + +static struct timeout * +to_checkudata(lua_State *L, int index) +{ + return luaL_checkudata(L, index, TIMEOUT_METANAME); +} + +static struct timeouts * +tos_checkudata(lua_State *L, int index) +{ + return *(struct timeouts **)luaL_checkudata(L, index, TIMEOUTS_METANAME); +} + +static void +tos_bind(lua_State *L, int tos_index, int to_index) +{ + lua_getuservalue(L, tos_index); + lua_pushlightuserdata(L, to_checkudata(L, to_index)); + lua_pushvalue(L, to_index); + lua_rawset(L, -3); + lua_pop(L, 1); +} + +static void +tos_unbind(lua_State *L, int tos_index, int to_index) +{ + lua_getuservalue(L, tos_index); + lua_pushlightuserdata(L, to_checkudata(L, to_index)); + lua_pushnil(L); + lua_rawset(L, -3); + lua_pop(L, 1); +} + +static int +to__index(lua_State *L) +{ + struct timeout *to = to_checkudata(L, 1); + + if (lua_type(L, 2 == LUA_TSTRING)) { + const char *key = lua_tostring(L, 2); + + if (!strcmp(key, "flags")) { + lua_pushinteger(L, to->flags); + + return 1; + } else if (!strcmp(key, "expires")) { + lua_pushinteger(L, to->expires); + + return 1; + } + } + + if (LUA_TNIL != lua_getuservalue(L, 1)) { + lua_pushvalue(L, 2); + if (LUA_TNIL != lua_rawget(L, -2)) + return 1; + } + + lua_pushvalue(L, 2); + if (LUA_TNIL != lua_rawget(L, lua_upvalueindex(1))) + return 1; + + return 0; +} + +static int +to__newindex(lua_State *L) +{ + if (LUA_TNIL == lua_getuservalue(L, 1)) { + lua_newtable(L); + lua_pushvalue(L, -1); + lua_setuservalue(L, 1); + } + + lua_pushvalue(L, 2); + lua_pushvalue(L, 3); + lua_rawset(L, -3); + + return 0; +} + +static int +to__gc(lua_State *L) +{ + struct timeout *to = to_checkudata(L, 1); + + /* + * NB: On script exit it's possible for a timeout to still be + * associated with a timeouts object, particularly when the timeouts + * object was created first. + */ + timeout_del(to); + + return 0; +} + +static int +to_new(lua_State *L) +{ + int flags = luaL_optinteger(L, 1, 0); + struct timeout *to; + + to = lua_newuserdata(L, sizeof *to); + timeout_init(to, flags); + luaL_setmetatable(L, TIMEOUT_METANAME); + + return 1; +} + +static const luaL_Reg to_methods[] = { + { NULL, NULL }, +}; + +static const luaL_Reg to_metatable[] = { + { "__index", &to__index }, + { "__newindex", &to__newindex }, + { "__gc", &to__gc }, + { NULL, NULL }, +}; + +static const luaL_Reg to_globals[] = { + { "new", &to_new }, + { NULL, NULL }, +}; + +static void +to_newmetatable(lua_State *L) +{ + if (luaL_newmetatable(L, TIMEOUT_METANAME)) { + /* + * fill metamethod table, capturing the methods table as an + * upvalue for use by __index metamethod + */ + luaL_newlib(L, to_methods); + luaL_setfuncs(L, to_metatable, 1); + } +} + +int +luaopen_timeout(lua_State *L) +{ + to_newmetatable(L); + + luaL_newlib(L, to_globals); + lua_pushinteger(L, TIMEOUT_INT); + lua_setfield(L, -2, "INT"); + lua_pushinteger(L, TIMEOUT_ABS); + lua_setfield(L, -2, "ABS"); + + return 1; +} + +static int +tos_update(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + lua_Number n = luaL_checknumber(L, 2); + + timeouts_update(T, timeouts_f2i(T, n)); + + lua_pushvalue(L, 1); + + return 1; +} + +static int +tos_step(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + lua_Number n = luaL_checknumber(L, 2); + + timeouts_step(T, timeouts_f2i(T, n)); + + lua_pushvalue(L, 1); + + return 1; +} + +static int +tos_timeout(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushnumber(L, timeouts_i2f(T, timeouts_timeout(T))); + + return 1; +} + +static int +tos_add(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + struct timeout *to = to_checkudata(L, 2); + lua_Number timeout = luaL_checknumber(L, 3); + + tos_bind(L, 1, 2); + timeouts_addf(T, to, timeout); + + return lua_pushvalue(L, 1), 1; +} + +static int +tos_del(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + struct timeout *to = to_checkudata(L, 2); + + timeouts_del(T, to); + tos_unbind(L, 1, 2); + + return lua_pushvalue(L, 1), 1; +} + +static int +tos_get(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + struct timeout *to; + + if (!(to = timeouts_get(T))) + return 0; + + lua_getuservalue(L, 1); + lua_rawgetp(L, -1, to); + + if (!timeout_pending(to)) + tos_unbind(L, 1, lua_absindex(L, -1)); + + return 1; +} + +static int +tos_pending(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushboolean(L, timeouts_pending(T)); + + return 1; +} + +static int +tos_expired(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushboolean(L, timeouts_expired(T)); + + return 1; +} + +static int +tos_check(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushboolean(L, timeouts_check(T, NULL)); + + return 1; +} + +static int +tos__next(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, lua_upvalueindex(1)); + struct timeouts_it *it = lua_touserdata(L, lua_upvalueindex(2)); + struct timeout *to; + + if (!(to = timeouts_next(T, it))) + return 0; + + lua_getuservalue(L, lua_upvalueindex(1)); + lua_rawgetp(L, -1, to); + + return 1; +} + +static int +tos_timeouts(lua_State *L) +{ + int flags = luaL_checkinteger(L, 2); + struct timeouts_it *it; + + tos_checkudata(L, 1); + lua_pushvalue(L, 1); + it = lua_newuserdata(L, sizeof *it); + TIMEOUTS_IT_INIT(it, flags); + lua_pushcclosure(L, &tos__next, 2); + + return 1; +} + +static int +tos__gc(lua_State *L) +{ + struct timeouts **tos = luaL_checkudata(L, 1, TIMEOUTS_METANAME); + struct timeout *to; + + TIMEOUTS_FOREACH(to, *tos, TIMEOUTS_ALL) { + timeouts_del(*tos, to); + } + + timeouts_close(*tos); + *tos = NULL; + + return 0; +} + +static int +tos_new(lua_State *L) +{ + timeout_t hz = luaL_optinteger(L, 1, 0); + struct timeouts **T; + int error; + + T = lua_newuserdata(L, sizeof *T); + luaL_setmetatable(L, TIMEOUTS_METANAME); + + lua_newtable(L); + lua_setuservalue(L, -2); + + if (!(*T = timeouts_open(hz, &error))) + return luaL_error(L, "%s", strerror(error)); + + return 1; +} + +static const luaL_Reg tos_methods[] = { + { "update", &tos_update }, + { "step", &tos_step }, + { "timeout", &tos_timeout }, + { "add", &tos_add }, + { "del", &tos_del }, + { "get", &tos_get }, + { "pending", &tos_pending }, + { "expired", &tos_expired }, + { "check", &tos_check }, + { "timeouts", &tos_timeouts }, + { NULL, NULL }, +}; + +static const luaL_Reg tos_metatable[] = { + { "__gc", &tos__gc }, + { NULL, NULL }, +}; + +static const luaL_Reg tos_globals[] = { + { "new", &tos_new }, + { NULL, NULL }, +}; + +static void +tos_newmetatable(lua_State *L) +{ + if (luaL_newmetatable(L, TIMEOUTS_METANAME)) { + luaL_setfuncs(L, tos_metatable, 0); + luaL_newlib(L, tos_methods); + lua_setfield(L, -2, "__index"); + } +} + +int +luaopen_timeouts(lua_State *L) +{ + to_newmetatable(L); + tos_newmetatable(L); + + luaL_newlib(L, tos_globals); + lua_pushinteger(L, TIMEOUTS_PENDING); + lua_setfield(L, -2, "PENDING"); + lua_pushinteger(L, TIMEOUTS_EXPIRED); + lua_setfield(L, -2, "EXPIRED"); + lua_pushinteger(L, TIMEOUTS_ALL); + lua_setfield(L, -2, "ALL"); + lua_pushinteger(L, TIMEOUTS_CLEAR); + lua_setfield(L, -2, "CLEAR"); + + return 1; +} diff --git a/src/ext/timeouts/test-timeout.c b/src/ext/timeouts/test-timeout.c new file mode 100644 index 0000000..8077129 --- /dev/null +++ b/src/ext/timeouts/test-timeout.c @@ -0,0 +1,530 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> +#include <limits.h> + +#include "timeout.h" + +#define THE_END_OF_TIME ((timeout_t)-1) + +static int check_misc(void) { + if (TIMEOUT_VERSION != timeout_version()) + return 1; + if (TIMEOUT_V_REL != timeout_v_rel()) + return 1; + if (TIMEOUT_V_API != timeout_v_api()) + return 1; + if (TIMEOUT_V_ABI != timeout_v_abi()) + return 1; + if (strcmp(timeout_vendor(), TIMEOUT_VENDOR)) + return 1; + return 0; +} + +static int check_open_close(timeout_t hz_set, timeout_t hz_expect) { + int err=0; + struct timeouts *tos = timeouts_open(hz_set, &err); + if (!tos) + return 1; + if (err) + return 1; + if (hz_expect != timeouts_hz(tos)) + return 1; + timeouts_close(tos); + return 0; +} + +/* Not very random */ +static timeout_t random_to(timeout_t min, timeout_t max) +{ + if (max <= min) + return min; + /* Not actually all that random, but should exercise the code. */ + timeout_t rand64 = random() * (timeout_t)INT_MAX + random(); + return min + (rand64 % (max-min)); +} + +/* configuration for check_randomized */ +struct rand_cfg { + /* When creating timeouts, smallest possible delay */ + timeout_t min_timeout; + /* When creating timeouts, largest possible delay */ + timeout_t max_timeout; + /* First time to start the clock at. */ + timeout_t start_at; + /* Do not advance the clock past this time. */ + timeout_t end_at; + /* Number of timeouts to create and monitor. */ + int n_timeouts; + /* Advance the clock by no more than this each step. */ + timeout_t max_step; + /* Use relative timers and stepping */ + int relative; + /* Every time the clock ticks, try removing this many timeouts at + * random. */ + int try_removing; + /* When we're done, advance the clock to the end of time. */ + int finalize; +}; + +static int check_randomized(const struct rand_cfg *cfg) +{ +#define FAIL() do { \ + printf("Failure on line %d\n", __LINE__); \ + goto done; \ + } while (0) + + int i, err; + int rv = 1; + struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout)); + timeout_t *timeouts = calloc(cfg->n_timeouts, sizeof(timeout_t)); + uint8_t *fired = calloc(cfg->n_timeouts, sizeof(uint8_t)); + uint8_t *found = calloc(cfg->n_timeouts, sizeof(uint8_t)); + uint8_t *deleted = calloc(cfg->n_timeouts, sizeof(uint8_t)); + struct timeouts *tos = timeouts_open(0, &err); + timeout_t now = cfg->start_at; + int n_added_pending = 0, cnt_added_pending = 0; + int n_added_expired = 0, cnt_added_expired = 0; + struct timeouts_it it_p, it_e, it_all; + int p_done = 0, e_done = 0, all_done = 0; + struct timeout *to = NULL; + const int rel = cfg->relative; + + if (!t || !timeouts || !tos || !fired || !found || !deleted) + FAIL(); + timeouts_update(tos, cfg->start_at); + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (&t[i] != timeout_init(&t[i], rel ? 0 : TIMEOUT_ABS)) + FAIL(); + if (timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + + timeouts[i] = random_to(cfg->min_timeout, cfg->max_timeout); + + timeouts_add(tos, &t[i], timeouts[i] - (rel ? now : 0)); + if (timeouts[i] <= cfg->start_at) { + if (timeout_pending(&t[i])) + FAIL(); + if (! timeout_expired(&t[i])) + FAIL(); + ++n_added_expired; + } else { + if (! timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + ++n_added_pending; + } + } + + if (!!n_added_pending != timeouts_pending(tos)) + FAIL(); + if (!!n_added_expired != timeouts_expired(tos)) + FAIL(); + + /* Test foreach, interleaving a few iterators. */ + TIMEOUTS_IT_INIT(&it_p, TIMEOUTS_PENDING); + TIMEOUTS_IT_INIT(&it_e, TIMEOUTS_EXPIRED); + TIMEOUTS_IT_INIT(&it_all, TIMEOUTS_ALL); + while (! (p_done && e_done && all_done)) { + if (!p_done) { + to = timeouts_next(tos, &it_p); + if (to) { + i = to - &t[0]; + ++found[i]; + ++cnt_added_pending; + } else { + p_done = 1; + } + } + if (!e_done) { + to = timeouts_next(tos, &it_e); + if (to) { + i = to - &t[0]; + ++found[i]; + ++cnt_added_expired; + } else { + e_done = 1; + } + } + if (!all_done) { + to = timeouts_next(tos, &it_all); + if (to) { + i = to - &t[0]; + ++found[i]; + } else { + all_done = 1; + } + } + } + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (found[i] != 2) + FAIL(); + } + if (cnt_added_expired != n_added_expired) + FAIL(); + if (cnt_added_pending != n_added_pending) + FAIL(); + + while (NULL != (to = timeouts_get(tos))) { + i = to - &t[0]; + assert(&t[i] == to); + if (timeouts[i] > cfg->start_at) + FAIL(); /* shouldn't have happened yet */ + + --n_added_expired; /* drop expired timeouts. */ + ++fired[i]; + } + + if (n_added_expired != 0) + FAIL(); + + while (now < cfg->end_at) { + int n_fired_this_time = 0; + timeout_t first_at = timeouts_timeout(tos) + now; + + timeout_t oldtime = now; + timeout_t step = random_to(1, cfg->max_step); + int another; + now += step; + if (rel) + timeouts_step(tos, step); + else + timeouts_update(tos, now); + + for (i = 0; i < cfg->try_removing; ++i) { + int idx = random() % cfg->n_timeouts; + if (! fired[idx]) { + timeout_del(&t[idx]); + ++deleted[idx]; + } + } + + another = (timeouts_timeout(tos) == 0); + + while (NULL != (to = timeouts_get(tos))) { + if (! another) + FAIL(); /* Thought we saw the last one! */ + i = to - &t[0]; + assert(&t[i] == to); + if (timeouts[i] > now) + FAIL(); /* shouldn't have happened yet */ + if (timeouts[i] <= oldtime) + FAIL(); /* should have happened already */ + if (timeouts[i] < first_at) + FAIL(); /* first_at should've been earlier */ + fired[i]++; + n_fired_this_time++; + another = (timeouts_timeout(tos) == 0); + } + if (n_fired_this_time && first_at > now) + FAIL(); /* first_at should've been earlier */ + if (another) + FAIL(); /* Huh? We think there are more? */ + if (!timeouts_check(tos, stderr)) + FAIL(); + } + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (fired[i] > 1) + FAIL(); /* Nothing fired twice. */ + if (timeouts[i] <= now) { + if (!(fired[i] || deleted[i])) + FAIL(); + } else { + if (fired[i]) + FAIL(); + } + if (fired[i] && deleted[i]) + FAIL(); + if (cfg->finalize > 1) { + if (!fired[i]) + timeout_del(&t[i]); + } + } + + /* Now nothing more should fire between now and the end of time. */ + if (cfg->finalize) { + timeouts_update(tos, THE_END_OF_TIME); + if (cfg->finalize > 1) { + if (timeouts_get(tos)) + FAIL(); + TIMEOUTS_FOREACH(to, tos, TIMEOUTS_ALL) + FAIL(); + } + } + rv = 0; + + done: + if (tos) timeouts_close(tos); + if (t) free(t); + if (timeouts) free(timeouts); + if (fired) free(fired); + if (found) free(found); + if (deleted) free(deleted); + return rv; +} + +struct intervals_cfg { + const timeout_t *timeouts; + int n_timeouts; + timeout_t start_at; + timeout_t end_at; + timeout_t skip; +}; + +int +check_intervals(struct intervals_cfg *cfg) +{ + int i, err; + int rv = 1; + struct timeout *to; + struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout)); + unsigned *fired = calloc(cfg->n_timeouts, sizeof(unsigned)); + struct timeouts *tos = timeouts_open(0, &err); + + timeout_t now = cfg->start_at; + if (!t || !tos || !fired) + FAIL(); + + timeouts_update(tos, now); + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (&t[i] != timeout_init(&t[i], TIMEOUT_INT)) + FAIL(); + if (timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + + timeouts_add(tos, &t[i], cfg->timeouts[i]); + if (! timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + } + + while (now < cfg->end_at) { + timeout_t delay = timeouts_timeout(tos); + if (cfg->skip && delay < cfg->skip) + delay = cfg->skip; + timeouts_step(tos, delay); + now += delay; + + while (NULL != (to = timeouts_get(tos))) { + i = to - &t[0]; + assert(&t[i] == to); + fired[i]++; + if (0 != (to->expires - cfg->start_at) % cfg->timeouts[i]) + FAIL(); + if (to->expires <= now) + FAIL(); + if (to->expires > now + cfg->timeouts[i]) + FAIL(); + } + if (!timeouts_check(tos, stderr)) + FAIL(); + } + + timeout_t duration = now - cfg->start_at; + for (i = 0; i < cfg->n_timeouts; ++i) { + if (cfg->skip) { + if (fired[i] > duration / cfg->timeouts[i]) + FAIL(); + } else { + if (fired[i] != duration / cfg->timeouts[i]) + FAIL(); + } + if (!timeout_pending(&t[i])) + FAIL(); + } + + rv = 0; + done: + if (t) free(t); + if (fired) free(fired); + if (tos) free(tos); + return rv; +} + +int +main(int argc, char **argv) +{ + int j; + int n_failed = 0; +#define DO(fn) do { \ + printf("."); fflush(stdout); \ + if (fn) { \ + ++n_failed; \ + printf("%s failed\n", #fn); \ + } \ + } while (0) + +#define DO_N(n, fn) do { \ + for (j = 0; j < (n); ++j) { \ + DO(fn); \ + } \ + } while (0) + + DO(check_misc()); + DO(check_open_close(1000, 1000)); + DO(check_open_close(0, TIMEOUT_mHZ)); + + struct rand_cfg cfg1 = { + .min_timeout = 1, + .max_timeout = 100, + .start_at = 5, + .end_at = 1000, + .n_timeouts = 1000, + .max_step = 10, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(300,check_randomized(&cfg1)); + + struct rand_cfg cfg2 = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 2, + }; + DO_N(300,check_randomized(&cfg2)); + + struct rand_cfg cfg2b = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 1, + }; + DO_N(300,check_randomized(&cfg2b)); + + struct rand_cfg cfg2c = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 0, + }; + DO_N(300,check_randomized(&cfg2c)); + + struct rand_cfg cfg3 = { + .min_timeout = 2000, + .max_timeout = ((uint64_t)1) << 50, + .start_at = 100, + .end_at = ((uint64_t)1) << 49, + .n_timeouts = 1000, + .max_step = 1<<31, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg3)); + + struct rand_cfg cfg3b = { + .min_timeout = ((uint64_t)1) << 50, + .max_timeout = ((uint64_t)1) << 52, + .start_at = 100, + .end_at = ((uint64_t)1) << 53, + .n_timeouts = 1000, + .max_step = ((uint64_t)1)<<48, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg3b)); + + struct rand_cfg cfg4 = { + .min_timeout = 2000, + .max_timeout = ((uint64_t)1) << 30, + .start_at = 100, + .end_at = ((uint64_t)1) << 26, + .n_timeouts = 10000, + .max_step = 1<<16, + .relative = 0, + .try_removing = 3, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg4)); + + const timeout_t primes[] = { + 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53, + 59,61,67,71,73,79,83,89,97 + }; + const timeout_t factors_of_1337[] = { + 1, 7, 191, 1337 + }; + const timeout_t multiples_of_five[] = { + 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 + }; + + struct intervals_cfg icfg1 = { + .timeouts = primes, + .n_timeouts = sizeof(primes)/sizeof(timeout_t), + .start_at = 50, + .end_at = 5322, + .skip = 0, + }; + DO(check_intervals(&icfg1)); + + struct intervals_cfg icfg2 = { + .timeouts = factors_of_1337, + .n_timeouts = sizeof(factors_of_1337)/sizeof(timeout_t), + .start_at = 50, + .end_at = 50000, + .skip = 0, + }; + DO(check_intervals(&icfg2)); + + struct intervals_cfg icfg3 = { + .timeouts = multiples_of_five, + .n_timeouts = sizeof(multiples_of_five)/sizeof(timeout_t), + .start_at = 49, + .end_at = 5333, + .skip = 0, + }; + DO(check_intervals(&icfg3)); + + struct intervals_cfg icfg4 = { + .timeouts = primes, + .n_timeouts = sizeof(primes)/sizeof(timeout_t), + .start_at = 50, + .end_at = 5322, + .skip = 16, + }; + DO(check_intervals(&icfg4)); + + if (n_failed) { + puts("\nFAIL"); + } else { + puts("\nOK"); + } + return !!n_failed; +} + +/* TODO: + + * Solve PR#3. + + * Investigate whether any untaken branches are possible. + + */ diff --git a/src/ext/timeouts/timeout-bitops.c b/src/ext/timeouts/timeout-bitops.c new file mode 100644 index 0000000..d8325db --- /dev/null +++ b/src/ext/timeouts/timeout-bitops.c @@ -0,0 +1,249 @@ +#include <stdint.h> +#ifdef _MSC_VER +#include <intrin.h> /* _BitScanForward, _BitScanReverse */ +#endif + +/* First define ctz and clz functions; these are compiler-dependent if + * you want them to be fast. */ +#if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS) + +/* On GCC and clang and some others, we can use __builtin functions. They + * are not defined for n==0, but timeout.s never calls them with n==0. */ + +#define ctz64(n) __builtin_ctzll(n) +#define clz64(n) __builtin_clzll(n) +#if LONG_BITS == 32 +#define ctz32(n) __builtin_ctzl(n) +#define clz32(n) __builtin_clzl(n) +#else +#define ctz32(n) __builtin_ctz(n) +#define clz32(n) __builtin_clz(n) +#endif + +#elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS) + +/* On MSVC, we have these handy functions. We can ignore their return + * values, since we will never supply val == 0. */ + +static __inline int ctz32(unsigned long val) +{ + DWORD zeros = 0; + _BitScanForward(&zeros, val); + return zeros; +} +static __inline int clz32(unsigned long val) +{ + DWORD zeros = 0; + _BitScanReverse(&zeros, val); + return zeros; +} +#ifdef _WIN64 +/* According to the documentation, these only exist on Win64. */ +static __inline int ctz64(uint64_t val) +{ + DWORD zeros = 0; + _BitScanForward64(&zeros, val); + return zeros; +} +static __inline int clz64(uint64_t val) +{ + DWORD zeros = 0; + _BitScanReverse64(&zeros, val); + return zeros; +} +#else +static __inline int ctz64(uint64_t val) +{ + uint32_t lo = (uint32_t) val; + uint32_t hi = (uint32_t) (val >> 32); + return lo ? ctz32(lo) : 32 + ctz32(hi); +} +static __inline int clz64(uint64_t val) +{ + uint32_t lo = (uint32_t) val; + uint32_t hi = (uint32_t) (val >> 32); + return hi ? clz32(hi) : 32 + clz32(lo); +} +#endif + +/* End of MSVC case. */ + +#else + +/* TODO: There are more clever ways to do this in the generic case. */ + + +#define process_(one, cz_bits, bits) \ + if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; } + +#define process64(bits) process_((UINT64_C(1)), 64, (bits)) +static inline int clz64(uint64_t x) +{ + int rv = 0; + + process64(32); + process64(16); + process64(8); + process64(4); + process64(2); + process64(1); + return rv; +} +#define process32(bits) process_((UINT32_C(1)), 32, (bits)) +static inline int clz32(uint32_t x) +{ + int rv = 0; + + process32(16); + process32(8); + process32(4); + process32(2); + process32(1); + return rv; +} + +#undef process_ +#undef process32 +#undef process64 +#define process_(one, bits) \ + if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; } + +#define process64(bits) process_((UINT64_C(1)), bits) +static inline int ctz64(uint64_t x) +{ + int rv = 0; + + process64(32); + process64(16); + process64(8); + process64(4); + process64(2); + process64(1); + return rv; +} + +#define process32(bits) process_((UINT32_C(1)), bits) +static inline int ctz32(uint32_t x) +{ + int rv = 0; + + process32(16); + process32(8); + process32(4); + process32(2); + process32(1); + return rv; +} + +#undef process32 +#undef process64 +#undef process_ + +/* End of generic case */ + +#endif /* End of defining ctz */ + +#ifdef TEST_BITOPS +#include <stdio.h> +#include <stdlib.h> + +static uint64_t testcases[] = { + 13371337 * 10, + 100, + 385789752, + 82574, + (((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101 +}; + +static int +naive_clz(int bits, uint64_t v) +{ + int r = 0; + uint64_t bit = ((uint64_t)1) << (bits-1); + while (bit && 0 == (v & bit)) { + r++; + bit >>= 1; + } + /* printf("clz(%d,%lx) -> %d\n", bits, v, r); */ + return r; +} + +static int +naive_ctz(int bits, uint64_t v) +{ + int r = 0; + uint64_t bit = 1; + while (bit && 0 == (v & bit)) { + r++; + bit <<= 1; + if (r == bits) + break; + } + /* printf("ctz(%d,%lx) -> %d\n", bits, v, r); */ + return r; +} + +static int +check(uint64_t vv) +{ + uint32_t v32 = (uint32_t) vv; + + if (vv == 0) + return 1; /* c[tl]z64(0) is undefined. */ + + if (ctz64(vv) != naive_ctz(64, vv)) { + printf("mismatch with ctz64: %d\n", ctz64(vv)); + exit(1); + return 0; + } + if (clz64(vv) != naive_clz(64, vv)) { + printf("mismatch with clz64: %d\n", clz64(vv)); + exit(1); + return 0; + } + + if (v32 == 0) + return 1; /* c[lt]z(0) is undefined. */ + + if (ctz32(v32) != naive_ctz(32, v32)) { + printf("mismatch with ctz32: %d\n", ctz32(v32)); + exit(1); + return 0; + } + if (clz32(v32) != naive_clz(32, v32)) { + printf("mismatch with clz32: %d\n", clz32(v32)); + exit(1); + return 0; + } + return 1; +} + +int +main(int c, char **v) +{ + unsigned int i; + const unsigned int n = sizeof(testcases)/sizeof(testcases[0]); + int result = 0; + + for (i = 0; i <= 63; ++i) { + uint64_t x = 1 << i; + if (!check(x)) + result = 1; + --x; + if (!check(x)) + result = 1; + } + + for (i = 0; i < n; ++i) { + if (! check(testcases[i])) + result = 1; + } + if (result) { + puts("FAIL"); + } else { + puts("OK"); + } + return result; +} +#endif + diff --git a/src/ext/timeouts/timeout-debug.h b/src/ext/timeouts/timeout-debug.h new file mode 100644 index 0000000..fc727a6 --- /dev/null +++ b/src/ext/timeouts/timeout-debug.h @@ -0,0 +1,77 @@ +/* + * D E B U G R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if TIMEOUT_DEBUG - 0 +#include <stdlib.h> +#include <stdio.h> + +#undef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 1 +#define DEBUG_LEVEL timeout_debug + +static int timeout_debug; + +#define SAYit_(lvl, fmt, ...) do { \ + if (DEBUG_LEVEL >= (lvl)) \ + fprintf(stderr, fmt "%s", __FILE__, __LINE__, __func__, __VA_ARGS__); \ +} while (0) + +#define SAYit(lvl, ...) SAYit_((lvl), "%s:%d:%s: " __VA_ARGS__, "\n") + +#define PANIC(...) do { \ + SAYit(0, __VA_ARGS__); \ + _Exit(EXIT_FAILURE); \ +} while (0) +#else +#undef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 0 +#define DEBUG_LEVEL 0 + +#define SAYit(...) (void)0 +#endif + +#define SAY(...) SAYit(1, __VA_ARGS__) +#define HAI SAY("HAI") + + +static inline char *fmt_(char *buf, uint64_t ts, int wheel_bit, int wheel_num) { + char *p = buf; + int wheel, n, i; + + for (wheel = wheel_num - 2; wheel >= 0; wheel--) { + n = ((1 << wheel_bit) - 1) & (ts >> (wheel * WHEEL_BIT)); + + for (i = wheel_bit - 1; i >= 0; i--) { + *p++ = '0' + !!(n & (1 << i)); + } + + if (wheel != 0) + *p++ = ':'; + } + + *p = 0; + + return buf; +} /* fmt_() */ + +#define fmt(ts) fmt_(((char[((1 << WHEEL_BIT) * WHEEL_NUM) + WHEEL_NUM + 1]){ 0 }), (ts), WHEEL_BIT, WHEEL_NUM) + + +static inline char *bin64_(char *buf, uint64_t n, int wheel_bit) { + char *p = buf; + int i; + + for (i = 0; i < (1 << wheel_bit); i++) { + *p++ = "01"[0x1 & (n >> (((1 << wheel_bit) - 1) - i))]; + } + + *p = 0; + + return buf; +} /* bin64_() */ + +#define bin64(ts) bin64_(((char[((1 << WHEEL_BIT) * WHEEL_NUM) + 1]){ 0 }), (ts), WHEEL_BIT) + + diff --git a/src/ext/timeouts/timeout.c b/src/ext/timeouts/timeout.c new file mode 100644 index 0000000..e78f57d --- /dev/null +++ b/src/ext/timeouts/timeout.c @@ -0,0 +1,744 @@ +/* ========================================================================== + * timeout.c - Tickless hierarchical timing wheel. + * -------------------------------------------------------------------------- + * Copyright (c) 2013, 2014 William Ahern + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * ========================================================================== + */ +#include <limits.h> /* CHAR_BIT */ + +#include <stddef.h> /* NULL */ +#include <stdlib.h> /* malloc(3) free(3) */ +#include <stdio.h> /* FILE fprintf(3) */ + +#include <inttypes.h> /* UINT64_C uint64_t */ + +#include <string.h> /* memset(3) */ + +#include <errno.h> /* errno */ + +#include <sys/queue.h> /* TAILQ(3) */ + +#include "timeout.h" + +#if TIMEOUT_DEBUG - 0 +#include "timeout-debug.h" +#endif + +#ifdef TIMEOUT_DISABLE_RELATIVE_ACCESS +#define TO_SET_TIMEOUTS(to, T) ((void)0) +#else +#define TO_SET_TIMEOUTS(to, T) ((to)->timeouts = (T)) +#endif + +/* + * A N C I L L A R Y R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#define abstime_t timeout_t /* for documentation purposes */ +#define reltime_t timeout_t /* "" */ + +#if !defined countof +#define countof(a) (sizeof (a) / sizeof *(a)) +#endif + +#if !defined endof +#define endof(a) (&(a)[countof(a)]) +#endif + +#if !defined MIN +#define MIN(a, b) (((a) < (b))? (a) : (b)) +#endif + +#if !defined MAX +#define MAX(a, b) (((a) > (b))? (a) : (b)) +#endif + +#if !defined TAILQ_CONCAT +#define TAILQ_CONCAT(head1, head2, field) do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ +} while (0) +#endif + +#if !defined TAILQ_FOREACH_SAFE +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST(head); \ + (var) && ((tvar) = TAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) +#endif + + +/* + * B I T M A N I P U L A T I O N R O U T I N E S + * + * The macros and routines below implement wheel parameterization. The + * inputs are: + * + * WHEEL_BIT - The number of value bits mapped in each wheel. The + * lowest-order WHEEL_BIT bits index the lowest-order (highest + * resolution) wheel, the next group of WHEEL_BIT bits the + * higher wheel, etc. + * + * WHEEL_NUM - The number of wheels. WHEEL_BIT * WHEEL_NUM = the number of + * value bits used by all the wheels. For the default of 6 and + * 4, only the low 24 bits are processed. Any timeout value + * larger than this will cycle through again. + * + * The implementation uses bit fields to remember which slot in each wheel + * is populated, and to generate masks of expiring slots according to the + * current update interval (i.e. the "tickless" aspect). The slots to + * process in a wheel are (populated-set & interval-mask). + * + * WHEEL_BIT cannot be larger than 6 bits because 2^6 -> 64 is the largest + * number of slots which can be tracked in a uint64_t integer bit field. + * WHEEL_BIT cannot be smaller than 3 bits because of our rotr and rotl + * routines, which only operate on all the value bits in an integer, and + * there's no integer smaller than uint8_t. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if !defined WHEEL_BIT +#define WHEEL_BIT 6 +#endif + +#if !defined WHEEL_NUM +#define WHEEL_NUM 4 +#endif + +#define WHEEL_LEN (1U << WHEEL_BIT) +#define WHEEL_MAX (WHEEL_LEN - 1) +#define WHEEL_MASK (WHEEL_LEN - 1) +#define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1) + +#include "timeout-bitops.c" + +#if WHEEL_BIT == 6 +#define ctz(n) ctz64(n) +#define clz(n) clz64(n) +#define fls(n) ((int)(64 - clz64(n))) +#else +#define ctz(n) ctz32(n) +#define clz(n) clz32(n) +#define fls(n) ((int)(32 - clz32(n))) +#endif + +#if WHEEL_BIT == 6 +#define WHEEL_C(n) UINT64_C(n) +#define WHEEL_PRIu PRIu64 +#define WHEEL_PRIx PRIx64 + +typedef uint64_t wheel_t; + +#elif WHEEL_BIT == 5 + +#define WHEEL_C(n) UINT32_C(n) +#define WHEEL_PRIu PRIu32 +#define WHEEL_PRIx PRIx32 + +typedef uint32_t wheel_t; + +#elif WHEEL_BIT == 4 + +#define WHEEL_C(n) UINT16_C(n) +#define WHEEL_PRIu PRIu16 +#define WHEEL_PRIx PRIx16 + +typedef uint16_t wheel_t; + +#elif WHEEL_BIT == 3 + +#define WHEEL_C(n) UINT8_C(n) +#define WHEEL_PRIu PRIu8 +#define WHEEL_PRIx PRIx8 + +typedef uint8_t wheel_t; + +#else +#error invalid WHEEL_BIT value +#endif + + +static inline wheel_t rotl(const wheel_t v, int c) { + if (!(c &= (sizeof v * CHAR_BIT - 1))) + return v; + + return (v << c) | (v >> (sizeof v * CHAR_BIT - c)); +} /* rotl() */ + + +static inline wheel_t rotr(const wheel_t v, int c) { + if (!(c &= (sizeof v * CHAR_BIT - 1))) + return v; + + return (v >> c) | (v << (sizeof v * CHAR_BIT - c)); +} /* rotr() */ + + +/* + * T I M E R R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TAILQ_HEAD(timeout_list, timeout); + +struct timeouts { + struct timeout_list wheel[WHEEL_NUM][WHEEL_LEN], expired; + + wheel_t pending[WHEEL_NUM]; + + timeout_t curtime; + timeout_t hertz; +}; /* struct timeouts */ + + +static struct timeouts *timeouts_init(struct timeouts *T, timeout_t hz) { + unsigned i, j; + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TAILQ_INIT(&T->wheel[i][j]); + } + } + + TAILQ_INIT(&T->expired); + + for (i = 0; i < countof(T->pending); i++) { + T->pending[i] = 0; + } + + T->curtime = 0; + T->hertz = (hz)? hz : TIMEOUT_mHZ; + + return T; +} /* timeouts_init() */ + + +TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t hz, int *error) { + struct timeouts *T; + + if ((T = malloc(sizeof *T))) + return timeouts_init(T, hz); + + *error = errno; + + return NULL; +} /* timeouts_open() */ + + +static void timeouts_reset(struct timeouts *T) { + struct timeout_list reset; + struct timeout *to; + unsigned i, j; + + TAILQ_INIT(&reset); + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe); + } + } + + TAILQ_CONCAT(&reset, &T->expired, tqe); + + TAILQ_FOREACH(to, &reset, tqe) { + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + } +} /* timeouts_reset() */ + + +TIMEOUT_PUBLIC void timeouts_close(struct timeouts *T) { + /* + * NOTE: Delete installed timeouts so timeout_pending() and + * timeout_expired() worked as expected. + */ + timeouts_reset(T); + + free(T); +} /* timeouts_close() */ + + +TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) { + return T->hertz; +} /* timeouts_hz() */ + + +TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) { + if (to->pending) { + TAILQ_REMOVE(to->pending, to, tqe); + + if (to->pending != &T->expired && TAILQ_EMPTY(to->pending)) { + ptrdiff_t index = to->pending - &T->wheel[0][0]; + int wheel = index / WHEEL_LEN; + int slot = index % WHEEL_LEN; + + T->pending[wheel] &= ~(WHEEL_C(1) << slot); + } + + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + } +} /* timeouts_del() */ + + +static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) { + return to->expires - T->curtime; +} /* timeout_rem() */ + + +static inline int timeout_wheel(timeout_t timeout) { + /* must be called with timeout != 0, so fls input is nonzero */ + return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT; +} /* timeout_wheel() */ + + +static inline int timeout_slot(int wheel, timeout_t expires) { + return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel); +} /* timeout_slot() */ + + +static void timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires) { + timeout_t rem; + int wheel, slot; + + timeouts_del(T, to); + + to->expires = expires; + + TO_SET_TIMEOUTS(to, T); + + if (expires > T->curtime) { + rem = timeout_rem(T, to); + + /* rem is nonzero since: + * rem == timeout_rem(T,to), + * == to->expires - T->curtime + * and above we have expires > T->curtime. + */ + wheel = timeout_wheel(rem); + slot = timeout_slot(wheel, to->expires); + + to->pending = &T->wheel[wheel][slot]; + TAILQ_INSERT_TAIL(to->pending, to, tqe); + + T->pending[wheel] |= WHEEL_C(1) << slot; + } else { + to->pending = &T->expired; + TAILQ_INSERT_TAIL(to->pending, to, tqe); + } +} /* timeouts_sched() */ + + +#ifndef TIMEOUT_DISABLE_INTERVALS +static void timeouts_readd(struct timeouts *T, struct timeout *to) { + to->expires += to->interval; + + if (to->expires <= T->curtime) { + /* If we've missed the next firing of this timeout, reschedule + * it to occur at the next multiple of its interval after + * the last time that it fired. + */ + timeout_t n = T->curtime - to->expires; + timeout_t r = n % to->interval; + to->expires = T->curtime + (to->interval - r); + } + + timeouts_sched(T, to, to->expires); +} /* timeouts_readd() */ +#endif + + +TIMEOUT_PUBLIC void timeouts_add(struct timeouts *T, struct timeout *to, timeout_t timeout) { +#ifndef TIMEOUT_DISABLE_INTERVALS + if (to->flags & TIMEOUT_INT) + to->interval = MAX(1, timeout); +#endif + + if (to->flags & TIMEOUT_ABS) + timeouts_sched(T, to, timeout); + else + timeouts_sched(T, to, T->curtime + timeout); +} /* timeouts_add() */ + + +TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) { + timeout_t elapsed = curtime - T->curtime; + struct timeout_list todo; + int wheel; + + TAILQ_INIT(&todo); + + /* + * There's no avoiding looping over every wheel. It's best to keep + * WHEEL_NUM smallish. + */ + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + wheel_t pending; + + /* + * Calculate the slots expiring in this wheel + * + * If the elapsed time is greater than the maximum period of + * the wheel, mark every position as expiring. + * + * Otherwise, to determine the expired slots fill in all the + * bits between the last slot processed and the current + * slot, inclusive of the last slot. We'll bitwise-AND this + * with our pending set below. + * + * If a wheel rolls over, force a tick of the next higher + * wheel. + */ + if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) { + pending = (wheel_t)~WHEEL_C(0); + } else { + wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT)); + int oslot, nslot; + + /* + * TODO: It's likely that at least one of the + * following three bit fill operations is redundant + * or can be replaced with a simpler operation. + */ + oslot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT)); + pending = rotl(((UINT64_C(1) << _elapsed) - 1), oslot); + + nslot = WHEEL_MASK & (curtime >> (wheel * WHEEL_BIT)); + pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot), _elapsed); + pending |= WHEEL_C(1) << nslot; + } + + while (pending & T->pending[wheel]) { + /* ctz input cannot be zero: loop condition. */ + int slot = ctz(pending & T->pending[wheel]); + TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe); + T->pending[wheel] &= ~(UINT64_C(1) << slot); + } + + if (!(0x1 & pending)) + break; /* break if we didn't wrap around end of wheel */ + + /* if we're continuing, the next wheel must tick at least once */ + elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT))); + } + + T->curtime = curtime; + + while (!TAILQ_EMPTY(&todo)) { + struct timeout *to = TAILQ_FIRST(&todo); + + TAILQ_REMOVE(&todo, to, tqe); + to->pending = NULL; + + timeouts_sched(T, to, to->expires); + } + + return; +} /* timeouts_update() */ + + +TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) { + timeouts_update(T, T->curtime + elapsed); +} /* timeouts_step() */ + + +TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *T) { + wheel_t pending = 0; + int wheel; + + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + pending |= T->pending[wheel]; + } + + return !!pending; +} /* timeouts_pending() */ + + +TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *T) { + return !TAILQ_EMPTY(&T->expired); +} /* timeouts_expired() */ + + +/* + * Calculate the interval before needing to process any timeouts pending on + * any wheel. + * + * (This is separated from the public API routine so we can evaluate our + * wheel invariant assertions irrespective of the expired queue.) + * + * This might return a timeout value sooner than any installed timeout if + * only higher-order wheels have timeouts pending. We can only know when to + * process a wheel, not precisely when a timeout is scheduled. Our timeout + * accuracy could be off by 2^(N*M)-1 units where N is the wheel number and + * M is WHEEL_BIT. Only timeouts which have fallen through to wheel 0 can be + * known exactly. + * + * We should never return a timeout larger than the lowest actual timeout. + */ +static timeout_t timeouts_int(struct timeouts *T) { + timeout_t timeout = ~TIMEOUT_C(0), _timeout; + timeout_t relmask; + int wheel, slot; + + relmask = 0; + + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + if (T->pending[wheel]) { + slot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT)); + + /* ctz input cannot be zero: T->pending[wheel] is + * nonzero, so rotr() is nonzero. */ + _timeout = (ctz(rotr(T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT); + /* +1 to higher order wheels as those timeouts are one rotation in the future (otherwise they'd be on a lower wheel or expired) */ + + _timeout -= relmask & T->curtime; + /* reduce by how much lower wheels have progressed */ + + timeout = MIN(_timeout, timeout); + } + + relmask <<= WHEEL_BIT; + relmask |= WHEEL_MASK; + } + + return timeout; +} /* timeouts_int() */ + + +/* + * Calculate the interval our caller can wait before needing to process + * events. + */ +TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) { + if (!TAILQ_EMPTY(&T->expired)) + return 0; + + return timeouts_int(T); +} /* timeouts_timeout() */ + + +TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) { + if (!TAILQ_EMPTY(&T->expired)) { + struct timeout *to = TAILQ_FIRST(&T->expired); + + TAILQ_REMOVE(&T->expired, to, tqe); + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + +#ifndef TIMEOUT_DISABLE_INTERVALS + if ((to->flags & TIMEOUT_INT) && to->interval > 0) + timeouts_readd(T, to); +#endif + + return to; + } else { + return 0; + } +} /* timeouts_get() */ + + +/* + * Use dumb looping to locate the earliest timeout pending on the wheel so + * our invariant assertions can check the result of our optimized code. + */ +static struct timeout *timeouts_min(struct timeouts *T) { + struct timeout *to, *min = NULL; + unsigned i, j; + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TAILQ_FOREACH(to, &T->wheel[i][j], tqe) { + if (!min || to->expires < min->expires) + min = to; + } + } + } + + return min; +} /* timeouts_min() */ + + +/* + * Check some basic algorithm invariants. If these invariants fail then + * something is definitely broken. + */ +#define report(...) do { \ + if ((fp)) \ + fprintf(fp, __VA_ARGS__); \ +} while (0) + +#define check(expr, ...) do { \ + if (!(expr)) { \ + report(__VA_ARGS__); \ + return 0; \ + } \ +} while (0) + +TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *T, FILE *fp) { + timeout_t timeout; + struct timeout *to; + + if ((to = timeouts_min(T))) { + check(to->expires > T->curtime, "missed timeout (expires:%" TIMEOUT_PRIu " <= curtime:%" TIMEOUT_PRIu ")\n", to->expires, T->curtime); + + timeout = timeouts_int(T); + check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime); + + timeout = timeouts_timeout(T); + check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime); + } else { + timeout = timeouts_timeout(T); + + if (!TAILQ_EMPTY(&T->expired)) + check(timeout == 0, "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, TIMEOUT_C(0)); + else + check(timeout == ~TIMEOUT_C(0), "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, ~TIMEOUT_C(0)); + } + + return 1; +} /* timeouts_check() */ + + +#define ENTER \ + do { \ + static const int pc0 = __LINE__; \ + switch (pc0 + it->pc) { \ + case __LINE__: (void)0 + +#define SAVE_AND_DO(do_statement) \ + do { \ + it->pc = __LINE__ - pc0; \ + do_statement; \ + case __LINE__: (void)0; \ + } while (0) + +#define YIELD(rv) \ + SAVE_AND_DO(return (rv)) + +#define LEAVE \ + SAVE_AND_DO(break); \ + } \ + } while (0) + +TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *T, struct timeouts_it *it) { + struct timeout *to; + + ENTER; + + if (it->flags & TIMEOUTS_EXPIRED) { + if (it->flags & TIMEOUTS_CLEAR) { + while ((to = timeouts_get(T))) { + YIELD(to); + } + } else { + TAILQ_FOREACH_SAFE(to, &T->expired, tqe, it->to) { + YIELD(to); + } + } + } + + if (it->flags & TIMEOUTS_PENDING) { + for (it->i = 0; it->i < countof(T->wheel); it->i++) { + for (it->j = 0; it->j < countof(T->wheel[it->i]); it->j++) { + TAILQ_FOREACH_SAFE(to, &T->wheel[it->i][it->j], tqe, it->to) { + YIELD(to); + } + } + } + } + + LEAVE; + + return NULL; +} /* timeouts_next */ + +#undef LEAVE +#undef YIELD +#undef SAVE_AND_DO +#undef ENTER + + +/* + * T I M E O U T R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) { + memset(to, 0, sizeof *to); + + to->flags = flags; + + return to; +} /* timeout_init() */ + + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS +TIMEOUT_PUBLIC bool timeout_pending(struct timeout *to) { + return to->pending && to->pending != &to->timeouts->expired; +} /* timeout_pending() */ + + +TIMEOUT_PUBLIC bool timeout_expired(struct timeout *to) { + return to->pending && to->pending == &to->timeouts->expired; +} /* timeout_expired() */ + + +TIMEOUT_PUBLIC void timeout_del(struct timeout *to) { + timeouts_del(to->timeouts, to); +} /* timeout_del() */ +#endif + + +/* + * V E R S I O N I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TIMEOUT_PUBLIC int timeout_version(void) { + return TIMEOUT_VERSION; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC const char *timeout_vendor(void) { + return TIMEOUT_VENDOR; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_rel(void) { + return TIMEOUT_V_REL; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_abi(void) { + return TIMEOUT_V_ABI; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_api(void) { + return TIMEOUT_V_API; +} /* timeout_version() */ + diff --git a/src/ext/timeouts/timeout.h b/src/ext/timeouts/timeout.h new file mode 100644 index 0000000..3ef76e9 --- /dev/null +++ b/src/ext/timeouts/timeout.h @@ -0,0 +1,253 @@ +/* ========================================================================== + * timeout.h - Tickless hierarchical timing wheel. + * -------------------------------------------------------------------------- + * Copyright (c) 2013, 2014 William Ahern + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * ========================================================================== + */ +#ifndef TIMEOUT_H +#define TIMEOUT_H + +#include <stdbool.h> /* bool */ +#include <stdio.h> /* FILE */ + +#include <inttypes.h> /* PRIu64 PRIx64 PRIX64 uint64_t */ + +#include <sys/queue.h> /* TAILQ(3) */ + + +/* + * V E R S I O N I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if !defined TIMEOUT_PUBLIC +#define TIMEOUT_PUBLIC +#endif + +#define TIMEOUT_VERSION TIMEOUT_V_REL +#define TIMEOUT_VENDOR "william(a)25thandClement.com" + +#define TIMEOUT_V_REL 0x20160226 +#define TIMEOUT_V_ABI 0x20160224 +#define TIMEOUT_V_API 0x20160226 + +TIMEOUT_PUBLIC int timeout_version(void); + +TIMEOUT_PUBLIC const char *timeout_vendor(void); + +TIMEOUT_PUBLIC int timeout_v_rel(void); + +TIMEOUT_PUBLIC int timeout_v_abi(void); + +TIMEOUT_PUBLIC int timeout_v_api(void); + + +/* + * I N T E G E R T Y P E I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#define TIMEOUT_C(n) UINT64_C(n) +#define TIMEOUT_PRIu PRIu64 +#define TIMEOUT_PRIx PRIx64 +#define TIMEOUT_PRIX PRIX64 + +#define TIMEOUT_mHZ TIMEOUT_C(1000) +#define TIMEOUT_uHZ TIMEOUT_C(1000000) +#define TIMEOUT_nHZ TIMEOUT_C(1000000000) + +typedef uint64_t timeout_t; + +#define timeout_error_t int /* for documentation purposes */ + + +/* + * C A L L B A C K I N T E R F A C E + * + * Callback function parameters unspecified to make embedding into existing + * applications easier. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#ifndef TIMEOUT_CB_OVERRIDE +struct timeout_cb { + void (*fn)(); + void *arg; +}; /* struct timeout_cb */ +#endif + +/* + * T I M E O U T I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#ifndef TIMEOUT_DISABLE_INTERVALS +#define TIMEOUT_INT 0x01 /* interval (repeating) timeout */ +#endif +#define TIMEOUT_ABS 0x02 /* treat timeout values as absolute */ + +#define TIMEOUT_INITIALIZER(flags) { (flags) } + +#define timeout_setcb(to, fn, arg) do { \ + (to)->callback.fn = (fn); \ + (to)->callback.arg = (arg); \ +} while (0) + +struct timeout { + int flags; + + timeout_t expires; + /* absolute expiration time */ + + struct timeout_list *pending; + /* timeout list if pending on wheel or expiry queue */ + + TAILQ_ENTRY(timeout) tqe; + /* entry member for struct timeout_list lists */ + +#ifndef TIMEOUT_DISABLE_CALLBACKS + struct timeout_cb callback; + /* optional callback information */ +#endif + +#ifndef TIMEOUT_DISABLE_INTERVALS + timeout_t interval; + /* timeout interval if periodic */ +#endif + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS + struct timeouts *timeouts; + /* timeouts collection if member of */ +#endif +}; /* struct timeout */ + + +TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int); +/* initialize timeout structure (same as TIMEOUT_INITIALIZER) */ + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS +TIMEOUT_PUBLIC bool timeout_pending(struct timeout *); +/* true if on timing wheel, false otherwise */ + +TIMEOUT_PUBLIC bool timeout_expired(struct timeout *); +/* true if on expired queue, false otherwise */ + +TIMEOUT_PUBLIC void timeout_del(struct timeout *); +/* remove timeout from any timing wheel (okay if not member of any) */ +#endif + +/* + * T I M I N G W H E E L I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +struct timeouts; + +TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *); +/* open a new timing wheel, setting optional HZ (for float conversions) */ + +TIMEOUT_PUBLIC void timeouts_close(struct timeouts *); +/* destroy timing wheel */ + +TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *); +/* return HZ setting (for float conversions) */ + +TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t); +/* update timing wheel with current absolute time */ + +TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t); +/* step timing wheel by relative time */ + +TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *); +/* return interval to next required update */ + +TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t); +/* add timeout to timing wheel */ + +TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *); +/* remove timeout from any timing wheel or expired queue (okay if on neither) */ + +TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *); +/* return any expired timeout (caller should loop until NULL-return) */ + +TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *); +/* return true if any timeouts pending on timing wheel */ + +TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *); +/* return true if any timeouts on expired queue */ + +TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *, FILE *); +/* return true if invariants hold. describes failures to optional file handle. */ + +#define TIMEOUTS_PENDING 0x10 +#define TIMEOUTS_EXPIRED 0x20 +#define TIMEOUTS_ALL (TIMEOUTS_PENDING|TIMEOUTS_EXPIRED) +#define TIMEOUTS_CLEAR 0x40 + +#define TIMEOUTS_IT_INITIALIZER(flags) { (flags), 0, 0, 0, 0 } + +#define TIMEOUTS_IT_INIT(cur, _flags) do { \ + (cur)->flags = (_flags); \ + (cur)->pc = 0; \ +} while (0) + +struct timeouts_it { + int flags; + unsigned pc, i, j; + struct timeout *to; +}; /* struct timeouts_it */ + +TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *, struct timeouts_it *); +/* return next timeout in pending wheel or expired queue. caller can delete + * the returned timeout, but should not otherwise manipulate the timing + * wheel. in particular, caller SHOULD NOT delete any other timeout as that + * could invalidate cursor state and trigger a use-after-free. + */ + +#define TIMEOUTS_FOREACH(var, T, flags) \ + struct timeouts_it _it = TIMEOUTS_IT_INITIALIZER((flags)); \ + while (((var) = timeouts_next((T), &_it))) + + +/* + * B O N U S W H E E L I N T E R F A C E S + * + * I usually use floating point timeouts in all my code, but it's cleaner to + * separate it to keep the core algorithmic code simple. + * + * Using macros instead of static inline routines where <math.h> routines + * might be used to keep -lm linking optional. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#include <math.h> /* ceil(3) */ + +#define timeouts_f2i(T, f) \ + ((timeout_t)ceil((f) * timeouts_hz((T)))) /* prefer late expiration over early */ + +#define timeouts_i2f(T, i) \ + ((double)(i) / timeouts_hz((T))) + +#define timeouts_addf(T, to, timeout) \ + timeouts_add((T), (to), timeouts_f2i((T), (timeout))) + +#endif /* TIMEOUT_H */

1 0

[tor/master] Fix compilation of timeout.c with our flags and warnings.
by nickm＠torproject.org 09 May '16

09 May '16

commit 9d6c530015e4eefd7b333885eaeca1f9fcbc6578 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 13 09:13:33 2016 -0400 Fix compilation of timeout.c with our flags and warnings. --- src/ext/timeouts/timeout-bitops.c | 7 ++++++- src/ext/timeouts/timeout.c | 7 +++++++ src/ext/timeouts/timeout.h | 2 +- 3 files changed, 14 insertions(+), 2 deletions(-) diff --git a/src/ext/timeouts/timeout-bitops.c b/src/ext/timeouts/timeout-bitops.c index d8325db..a018f33 100644 --- a/src/ext/timeouts/timeout-bitops.c +++ b/src/ext/timeouts/timeout-bitops.c @@ -1,4 +1,5 @@ #include <stdint.h> +#include <limits.h> #ifdef _MSC_VER #include <intrin.h> /* _BitScanForward, _BitScanReverse */ #endif @@ -7,12 +8,16 @@ * you want them to be fast. */ #if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS) +#ifndef LONG_BIT +#define LONG_BIT (SIZEOF_LONG*CHAR_BIT) +#endif + /* On GCC and clang and some others, we can use __builtin functions. They * are not defined for n==0, but timeout.s never calls them with n==0. */ #define ctz64(n) __builtin_ctzll(n) #define clz64(n) __builtin_clzll(n) -#if LONG_BITS == 32 +#if LONG_BIT == 32 #define ctz32(n) __builtin_ctzl(n) #define clz32(n) __builtin_clzl(n) #else diff --git a/src/ext/timeouts/timeout.c b/src/ext/timeouts/timeout.c index e78f57d..70bc0eb 100644 --- a/src/ext/timeouts/timeout.c +++ b/src/ext/timeouts/timeout.c @@ -23,6 +23,9 @@ * USE OR OTHER DEALINGS IN THE SOFTWARE. * ========================================================================== */ +#ifdef HAVE_CONFIG_H +#include "orconfig.h" +#endif #include <limits.h> /* CHAR_BIT */ #include <stddef.h> /* NULL */ @@ -39,6 +42,10 @@ #include "timeout.h" +#ifndef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 0 +#endif + #if TIMEOUT_DEBUG - 0 #include "timeout-debug.h" #endif diff --git a/src/ext/timeouts/timeout.h b/src/ext/timeouts/timeout.h index 3ef76e9..6d7359a 100644 --- a/src/ext/timeouts/timeout.h +++ b/src/ext/timeouts/timeout.h @@ -90,7 +90,7 @@ typedef uint64_t timeout_t; #ifndef TIMEOUT_CB_OVERRIDE struct timeout_cb { - void (*fn)(); + void (*fn)(void); void *arg; }; /* struct timeout_cb */ #endif

1 0

[tor/master] Quick function to find out the timeout object's view of "now"
by nickm＠torproject.org 09 May '16

09 May '16

commit c77cf8825a33d902c5827f0b4f0a71cec97a3a85 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 13 11:10:36 2016 -0400 Quick function to find out the timeout object's view of "now" --- src/ext/timeouts/timeout.c | 3 +++ src/ext/timeouts/timeout.h | 3 +++ 2 files changed, 6 insertions(+) diff --git a/src/ext/timeouts/timeout.c b/src/ext/timeouts/timeout.c index 70bc0eb..dbc24fa 100644 --- a/src/ext/timeouts/timeout.c +++ b/src/ext/timeouts/timeout.c @@ -467,6 +467,9 @@ TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) { return; } /* timeouts_update() */ +TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *T) { + return T->curtime; +} /* timeouts_get_curtime() */ TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) { timeouts_update(T, T->curtime + elapsed); diff --git a/src/ext/timeouts/timeout.h b/src/ext/timeouts/timeout.h index 6d7359a..3b08f19 100644 --- a/src/ext/timeouts/timeout.h +++ b/src/ext/timeouts/timeout.h @@ -177,6 +177,9 @@ TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t); TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t); /* step timing wheel by relative time */ +TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *); +/* Return the current tick. */ + TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *); /* return interval to next required update */

1 0

[tor/master] Add wrappers to tie the new timeouts into libevent.
by nickm＠torproject.org 09 May '16

09 May '16

commit dcf948da0652ca13f5b44f0e15e062f1ff3f8993 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 13 11:11:35 2016 -0400 Add wrappers to tie the new timeouts into libevent. --- src/common/include.am | 2 + src/common/timers.c | 276 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/common/timers.h | 22 ++++ src/ext/include.am | 12 +-- 4 files changed, 306 insertions(+), 6 deletions(-) diff --git a/src/common/include.am b/src/common/include.am index e61ed68..0450268 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -97,6 +97,7 @@ LIBOR_CRYPTO_A_SOURCES = \ LIBOR_EVENT_A_SOURCES = \ src/common/compat_libevent.c \ src/common/procmon.c \ + src/common/timers.c \ src/ext/timeouts/timeout.c src_common_libor_a_SOURCES = $(LIBOR_A_SOURCES) @@ -136,6 +137,7 @@ COMMONHEADERS = \ src/common/procmon.h \ src/common/sandbox.h \ src/common/testsupport.h \ + src/common/timers.h \ src/common/torgzip.h \ src/common/torint.h \ src/common/torlog.h \ diff --git a/src/common/timers.c b/src/common/timers.c new file mode 100644 index 0000000..5f42cd4 --- /dev/null +++ b/src/common/timers.c @@ -0,0 +1,276 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file timers.c + * \brief Wrapper around William Ahern's fast hierarchical timer wheel + * implementation, to tie it in with a libevent backend. + * + * Only use these functions from the main thread. + * + * The main advantage of tor_timer_t over using libevent's timers is that + * they're way more efficient if we need to have thousands or millions of + * them. For more information, see + * http://www.25thandclement.com/~william/projects/timeout.c.html + * + * Periodic timers are available in the backend, but I've turned them off. + * We can turn them back on if needed. + */ + +/* Notes: + * + * The use of tor_gettimeofday_cached_monotonic() is kind of ugly. It would + * be neat to fix it. + * + * Having a way to free all timers on shutdown would free people from the + * need to track them. Not sure if that's clever though. + * + * In an ideal world, Libevent would just switch to use this backend, and we + * could throw this file away. But even if Libevent does switch, we'll be + * stuck with legacy libevents for some time. + */ + +#include "orconfig.h" + +#include "compat.h" +#include "compat_libevent.h" +#include "timers.h" +#include "torlog.h" +#include "util.h" + +#ifdef HAVE_EVENT2_EVENT_H +#include <event2/event.h> +#else +#include <event.h> +#endif + +struct timeout_cb { + timer_cb_fn_t cb; + void *arg; +}; + +/* + * These definitions are for timeouts.c and timeouts.h. + */ +#ifdef __GNUC__ +/* We're not exposing any of the functions outside this file. */ +#define TIMEOUT_PUBLIC __attribute__((__unused__)) static +#else +/* We're not exposing any of the functions outside this file. */ +#define TIMEOUT_PUBLIC static +#endif +/* We're not using periodic events. */ +#define TIMEOUT_DISABLE_INTERVALS +/* We always know the global_timeouts object, so we don't need each timeout + * to keep a pointer to it. */ +#define TIMEOUT_DISABLE_RELATIVE_ACCESS +/* We're providing our own struct timeout_cb. */ +#define TIMEOUT_CB_OVERRIDE +/* We're going to support timers that are pretty far out in advance. Making + * this big can be inefficient, but having a significant number of timers + * above TIMEOUT_MAX can also be super-inefficent. Choosing 5 here sets + * timeout_max to 2^30 ticks, or 29 hours with our value for USEC_PER_TICK */ +#define WHEEL_NUM 5 +#include "src/ext/timeouts/timeout.c" + +static struct timeouts *global_timeouts = NULL; +static struct event *global_timer_event = NULL; + +/** We need to choose this value carefully. Because we're using timer wheels, + * it actually costs us to have extra resolution we don't use. So for now, + * I'm going to define our resolution as .1 msec, and hope that's good enough. + */ +#define USEC_PER_TICK 100 + +/** One million microseconds in a second */ +#define USEC_PER_SEC 1000000 + +/** + * Convert the timeval in tv to a timeout_t, and return it. + * + * The output resolution is set by USEC_PER_TICK, and the time corresponding + * to 0 is the same as the time corresponding to 0 from + * tor_gettimeofday_cached_monotonic(). + */ +static timeout_t +tv_to_timeout(const struct timeval *tv) +{ + uint64_t usec = tv->tv_usec; + usec += ((uint64_t)USEC_PER_SEC) * tv->tv_sec; + return usec / USEC_PER_TICK; +} + +/** + * Convert the timeout in t to a timeval in tv_out + */ +static void +timeout_to_tv(timeout_t t, struct timeval *tv_out) +{ + t *= USEC_PER_TICK; + tv_out->tv_usec = (int)(t % USEC_PER_SEC); + tv_out->tv_sec = (time_t)(t / USEC_PER_SEC); +} + +/** + * Update the timer tv to the current time in tv. + */ +static void +timer_advance_to_cur_time(const struct timeval *tv) +{ + timeout_t cur_tick = tv_to_timeout(tv); + if (BUG(cur_tick < timeouts_get_curtime(global_timeouts))) { + cur_tick = timeouts_get_curtime(global_timeouts); // LCOV_EXCL_LINE + } + timeouts_update(global_timeouts, cur_tick); +} + +/** + * Adjust the time at which the libevent timer should fire based on + * the next-expiring time in global_timeouts + */ +static void +libevent_timer_reschedule(void) +{ + struct timeval now; + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + const timeout_t delay = timeouts_timeout(global_timeouts); + struct timeval d; + timeout_to_tv(delay, &d); + event_add(global_timer_event, &d); +} + +/** + * Invoked when the libevent timer has expired: see which tor_timer_t events + * have fired, activate their callbacks, and reschedule the libevent timer. + */ +static void +libevent_timer_callback(evutil_socket_t fd, short what, void *arg) +{ + (void)fd; + (void)what; + (void)arg; + + struct timeval now; + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + tor_timer_t *t; + while ((t = timeouts_get(global_timeouts))) { + t->callback.cb(t, t->callback.arg, &now); + } + + tor_gettimeofday_cache_clear(); + libevent_timer_reschedule(); +} + +/** + * Initialize the timers subsystem. Requires that libevent has already been + * initialized. + */ +void +timers_initialize(void) +{ + if (global_timeouts) + return; + + timeout_error_t err; + global_timeouts = timeouts_open(0, &err); + if (!global_timeouts) { + log_err(LD_BUG, "Unable to open timer backend: %s", strerror(err)); + tor_assert(0); + } + + struct event *timer_event; + timer_event = tor_event_new(tor_libevent_get_base(), + -1, 0, libevent_timer_callback, NULL); + tor_assert(timer_event); + global_timer_event = timer_event; +} + +/** + * Release all storage held in the timers subsystem. Does not fire timers. + */ +void +timers_shutdown(void) +{ + if (global_timer_event) { + tor_event_free(global_timer_event); + global_timer_event = NULL; + } + if (global_timeouts) { + timeouts_close(global_timeouts); + global_timeouts = NULL; + } +} + +/** + * Allocate and return a new timer, with given callback and argument. + */ +tor_timer_t * +timer_new(timer_cb_fn_t cb, void *arg) +{ + tor_timer_t *t = tor_malloc(sizeof(tor_timer_t)); + timeout_init(t, 0); + timer_set_cb(t, cb, arg); + return t; +} + +/** + * Release all storage held by t, and unschedule it if was already + * scheduled. + */ +void +timer_free(tor_timer_t *t) +{ + if (! t) + return; + + timeouts_del(global_timeouts, t); + tor_free(t); +} + +/** + * Change the callback and argument associated with a timer t. + */ +void +timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg) +{ + t->callback.cb = cb; + t->callback.arg = arg; +} + +/** + * Schedule the timer t to fire at the current time plus a delay of tv. + * All times are relative to tor_gettimeofday_cached_monotonic. + */ +void +timer_schedule(tor_timer_t *t, const struct timeval *tv) +{ + const timeout_t when = tv_to_timeout(tv); + struct timeval now; + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + timeouts_add(global_timeouts, t, when); + + /* Should we update the libevent timer? */ + if (to <= when) { + return; /* we're already going to fire before this timer would trigger. */ + + libevent_timer_reschedule(); +} + +/** + * Cancel the timer t if it is currently scheduled. (It's okay to call + * this on an unscheduled timer. + */ +void +timer_disable(tor_timer_t *t) +{ + timeouts_del(global_timeouts, t); + /* We don't reschedule the libevent timer here, since it's okay if it fires + * early. */ +} + diff --git a/src/common/timers.h b/src/common/timers.h new file mode 100644 index 0000000..594cf38 --- /dev/null +++ b/src/common/timers.h @@ -0,0 +1,22 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_TIMERS_H +#define TOR_TIMERS_H + +#include "orconfig.h" +#include "testsupport.h" + +typedef struct timeout tor_timer_t; +typedef void (*timer_cb_fn_t)(tor_timer_t *, void *, const struct timeval *); +tor_timer_t *timer_new(timer_cb_fn_t cb, void *arg); +void timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg); +void timer_schedule(tor_timer_t *t, const struct timeval *delay); +void timer_disable(tor_timer_t *t); +void timer_free(tor_timer_t *t); + +void timers_initialize(void); +void timers_shutdown(void); + +#endif + diff --git a/src/ext/include.am b/src/ext/include.am index 42a38f1..d1a3b47 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -10,11 +10,13 @@ EXTHEADERS = \ src/ext/tor_readpassphrase.h \ src/ext/strlcat.c \ src/ext/strlcpy.c \ - src/ext/timeouts/timeout.h \ - src/ext/timeouts/timeout-debug.h \ src/ext/tinytest_macros.h \ src/ext/tor_queue.h \ - src/ext/siphash.h + src/ext/siphash.h \ + src/ext/timeouts/timeout.h \ + src/ext/timeouts/timeout-debug.h \ + src/ext/timeouts/timeout-bitops.c \ + src/ext/timeouts/timeout.c noinst_HEADERS+= $(EXTHEADERS) @@ -166,7 +168,5 @@ EXTRA_DIST += \ timeouts/lua/timeout-lua.c \ timeouts/Makefile \ timeouts/Rules.shrc \ - timeouts/test-timeout.c \ - timeouts/timeout-bitops.c - + timeouts/test-timeout.c

1 0

[tor/master] Quick-and-dirty test for timers code.
by nickm＠torproject.org 09 May '16

09 May '16

commit 118556e4b32c30d91c2d132c5f8d3cb8e551fafc Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 13 15:30:59 2016 -0400 Quick-and-dirty test for timers code. --- .gitignore | 2 + src/common/timers.c | 23 ++++++++++- src/test/include.am | 16 +++++++- src/test/test-timers.c | 101 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 139 insertions(+), 3 deletions(-) diff --git a/.gitignore b/.gitignore index b141e80..7900141 100644 --- a/.gitignore +++ b/.gitignore @@ -180,6 +180,7 @@ uptime-*.json /src/test/test-memwipe /src/test/test-ntor-cl /src/test/test-switch-id +/src/test/test-timers /src/test/test_workqueue /src/test/test.exe /src/test/test-slow.exe @@ -188,6 +189,7 @@ uptime-*.json /src/test/test-ntor-cl.exe /src/test/test-memwipe.exe /src/test/test-switch-id.exe +/src/test/test-timers.exe /src/test/test_workqueue.exe /src/test/test_zero_length_keys.sh /src/test/test_ntor.sh diff --git a/src/common/timers.c b/src/common/timers.c index 5f42cd4..58981b9 100644 --- a/src/common/timers.c +++ b/src/common/timers.c @@ -79,12 +79,23 @@ static struct event *global_timer_event = NULL; /** We need to choose this value carefully. Because we're using timer wheels, * it actually costs us to have extra resolution we don't use. So for now, * I'm going to define our resolution as .1 msec, and hope that's good enough. + * + * Note that two of the most popular libevent backends (epoll without timerfd, + * and windows select), simply can't support sub-millisecond resolution, + * do this is optimistic for a lot of users. */ #define USEC_PER_TICK 100 /** One million microseconds in a second */ #define USEC_PER_SEC 1000000 +/** Check at least once every N seconds. */ +#define MIN_CHECK_SECONDS 3600 + +/** Check at least once every N ticks. */ +#define MIN_CHECK_TICKS \ + (((timeout_t)MIN_CHECK_SECONDS) * (1000000 / USEC_PER_TICK)) + /** * Convert the timeval in tv to a timeout_t, and return it. * @@ -135,8 +146,10 @@ libevent_timer_reschedule(void) tor_gettimeofday_cached_monotonic(&now); timer_advance_to_cur_time(&now); - const timeout_t delay = timeouts_timeout(global_timeouts); + timeout_t delay = timeouts_timeout(global_timeouts); struct timeval d; + if (delay > MIN_CHECK_TICKS) + delay = MIN_CHECK_TICKS; timeout_to_tv(delay, &d); event_add(global_timer_event, &d); } @@ -153,6 +166,7 @@ libevent_timer_callback(evutil_socket_t fd, short what, void *arg) (void)arg; struct timeval now; + tor_gettimeofday_cache_clear(); tor_gettimeofday_cached_monotonic(&now); timer_advance_to_cur_time(&now); @@ -187,6 +201,8 @@ timers_initialize(void) -1, 0, libevent_timer_callback, NULL); tor_assert(timer_event); global_timer_event = timer_event; + + libevent_timer_reschedule(); } /** @@ -253,12 +269,15 @@ timer_schedule(tor_timer_t *t, const struct timeval *tv) tor_gettimeofday_cached_monotonic(&now); timer_advance_to_cur_time(&now); + /* Take the old timeout value. */ + timeout_t to = timeouts_timeout(global_timeouts); + timeouts_add(global_timeouts, t, when); /* Should we update the libevent timer? */ if (to <= when) { return; /* we're already going to fire before this timer would trigger. */ - + } libevent_timer_reschedule(); } diff --git a/src/test/include.am b/src/test/include.am index 7d80fdf..174bcda 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -17,6 +17,7 @@ endif TESTS += src/test/test src/test/test-slow src/test/test-memwipe \ src/test/test_workqueue src/test/test_keygen.sh \ + src/test/test-timers \ $(TESTSCRIPTS) # These flavors are run using automake's test-driver and test-network.sh @@ -40,7 +41,8 @@ noinst_PROGRAMS+= \ src/test/test-memwipe \ src/test/test-child \ src/test/test_workqueue \ - src/test/test-switch-id + src/test/test-switch-id \ + src/test/test-timers endif src_test_AM_CPPFLAGS = -DSHARE_DATADIR="\"$(datadir)\"" \ @@ -127,6 +129,8 @@ src_test_test_slow_SOURCES = \ src_test_test_memwipe_SOURCES = \ src/test/test-memwipe.c +src_test_test_timers_SOURCES = \ + src/test/test-timers.c src_test_test_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) @@ -190,6 +194,16 @@ src_test_test_workqueue_LDADD = src/or/libtor-testing.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ @TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ +src_test_test_timers_CPPFLAGS = $(src_test_test_CPPFLAGS) +src_test_test_timers_CFLAGS = $(src_test_test_CFLAGS) +src_test_test_timers_LDADD = \ + src/common/libor-event-testing.a \ + src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \ + src/common/libor-testing.a \ + @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ + @TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ +src_test_test_timers_LDFLAGS = $(src_test_test_LDFLAGS) + noinst_HEADERS+= \ src/test/fakechans.h \ src/test/log_test_helpers.h \ diff --git a/src/test/test-timers.c b/src/test/test-timers.c new file mode 100644 index 0000000..83a5e1b --- /dev/null +++ b/src/test/test-timers.c @@ -0,0 +1,101 @@ +/* Copyright 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" + +#include <math.h> +#include <stdio.h> +#include <string.h> + +#ifdef HAVE_EVENT2_EVENT_H +#include <event2/event.h> +#else +#include <event.h> +#endif + +#include "compat.h" +#include "compat_libevent.h" +#include "crypto.h" +#include "timers.h" +#include "util.h" + +#define N_TIMERS 1000 +#define MAX_DURATION 30 + +static struct timeval fire_at[N_TIMERS] = {{0,0}}; +static int fired[N_TIMERS] = {0}; +static struct timeval difference[N_TIMERS] = {{0,0}}; +static tor_timer_t *timers[N_TIMERS] = {NULL}; + +static int n_fired = 0; + +static void +timer_cb(tor_timer_t *t, void *arg, const struct timeval *now) +{ + tor_timer_t **t_ptr = arg; + tor_assert(*t_ptr == t); + int idx = (int) (t_ptr - timers); + ++fired[idx]; + timersub(now, &fire_at[idx], &difference[idx]); + ++n_fired; + // printf("%d / %d\n",n_fired, N_TIMERS); + if (n_fired == N_TIMERS) { + event_base_loopbreak(tor_libevent_get_base()); + } +} + +int +main(int argc, char **argv) +{ + (void)argc; + (void)argv; + tor_libevent_cfg cfg; + memset(&cfg, 0, sizeof(cfg)); + tor_libevent_initialize(&cfg); + timers_initialize(); + + int i; + struct timeval now; + tor_gettimeofday(&now); + for (i = 0; i < N_TIMERS; ++i) { + struct timeval delay; + delay.tv_sec = crypto_rand_int_range(0,MAX_DURATION); + delay.tv_usec = crypto_rand_int_range(0,1000000); + timeradd(&now, &delay, &fire_at[i]); + timers[i] = timer_new(timer_cb, &timers[i], 0); + timer_schedule(timers[i], &delay); + } + + event_base_loop(tor_libevent_get_base(), 0); + + uint64_t total_difference = 0; + uint64_t total_square_difference = 0; + tor_assert(n_fired == N_TIMERS); + for (i = 0; i < N_TIMERS; ++i) { + tor_assert(fired[i] == 1); + uint64_t diff = difference[i].tv_usec + difference[i].tv_sec * 1000000; + total_difference += diff; + total_square_difference += diff*diff; + } + const uint64_t mean_diff = total_difference / N_TIMERS; + printf("mean difference: "U64_FORMAT" usec\n", + U64_PRINTF_ARG(mean_diff)); + + const double mean_sq = ((double)total_square_difference) / N_TIMERS; + const double sq_mean = mean_diff * mean_diff; + const double stddev = sqrt(mean_sq - sq_mean); + printf("standard deviation: %lf usec\n", stddev); + + if (mean_diff > 500*1000 || stddev > 500*1000) { + printf("Either your system is under ridiculous load, or the " + "timer backend is broken.\n"); + return 1; + } else if (mean_diff > 2000 || stddev > 2000) { + printf("Either your system is a bit slow or the " + "timer backend is odd.\n"); + return 0; + } else { + printf("Looks good enough.\n"); + } + return 0; +}

1 0