diff options
Diffstat (limited to 'src')
84 files changed, 5203 insertions, 294 deletions
diff --git a/src/common/address.c b/src/common/address.c index 793a40effc..a6e0f3f491 100644 --- a/src/common/address.c +++ b/src/common/address.c @@ -1172,7 +1172,7 @@ tor_addr_hash(const tor_addr_t *addr) /** Return a newly allocated string with a representation of <b>addr</b>. */ char * -tor_dup_addr(const tor_addr_t *addr) +tor_addr_to_str_dup(const tor_addr_t *addr) { char buf[TOR_ADDR_BUF_LEN]; if (tor_addr_to_str(buf, addr, sizeof(buf), 0)) { diff --git a/src/common/address.h b/src/common/address.h index 53712bde02..3de67e1c74 100644 --- a/src/common/address.h +++ b/src/common/address.h @@ -179,7 +179,7 @@ tor_addr_eq_ipv4h(const tor_addr_t *a, uint32_t u) #define TOR_ADDR_BUF_LEN 48 int tor_addr_lookup(const char *name, uint16_t family, tor_addr_t *addr_out); -char *tor_dup_addr(const tor_addr_t *addr) ATTR_MALLOC; +char *tor_addr_to_str_dup(const tor_addr_t *addr) ATTR_MALLOC; /** Wrapper function of fmt_addr_impl(). It does not decorate IPv6 * addresses. */ diff --git a/src/common/compat.h b/src/common/compat.h index 8cf84580c6..b6ee4106db 100644 --- a/src/common/compat.h +++ b/src/common/compat.h @@ -430,7 +430,7 @@ typedef int socklen_t; #ifdef _WIN32 /* XXX Actually, this should arguably be SOCKET; we use intptr_t here so that - * any inadvertant checks for the socket being <= 0 or > 0 will probably + * any inadvertent checks for the socket being <= 0 or > 0 will probably * still work. */ #define tor_socket_t intptr_t #define TOR_SOCKET_T_FORMAT INTPTR_T_FORMAT diff --git a/src/common/crypto.c b/src/common/crypto.c index d2a42698cb..65a575ebea 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -134,7 +134,7 @@ crypto_get_rsa_padding_overhead(int padding) switch (padding) { case RSA_PKCS1_OAEP_PADDING: return PKCS1_OAEP_PADDING_OVERHEAD; - default: tor_assert(0); return -1; + default: tor_assert(0); return -1; // LCOV_EXCL_LINE } } @@ -146,7 +146,7 @@ crypto_get_rsa_padding(int padding) switch (padding) { case PK_PKCS1_OAEP_PADDING: return RSA_PKCS1_OAEP_PADDING; - default: tor_assert(0); return -1; + default: tor_assert(0); return -1; // LCOV_EXCL_LINE } } @@ -1739,8 +1739,8 @@ crypto_digest_algorithm_get_length(digest_algorithm_t alg) case DIGEST_SHA3_512: return DIGEST512_LEN; default: - tor_assert(0); - return 0; /* Unreachable */ + tor_assert(0); // LCOV_EXCL_LINE + return 0; /* Unreachable */ // LCOV_EXCL_LINE } } @@ -1783,8 +1783,8 @@ crypto_digest_alloc_bytes(digest_algorithm_t alg) case DIGEST_SHA3_512: return END_OF_FIELD(d.sha3); default: - tor_assert(0); - return 0; + tor_assert(0); // LCOV_EXCL_LINE + return 0; // LCOV_EXCL_LINE } #undef END_OF_FIELD #undef STRUCT_FIELD_SIZE @@ -1914,6 +1914,7 @@ crypto_digest_get_digest(crypto_digest_t *digest, case DIGEST_SHA512: SHA512_Final(r, &tmpenv.d.sha512); break; +//LCOV_EXCL_START case DIGEST_SHA3_256: /* FALLSTHROUGH */ case DIGEST_SHA3_512: log_warn(LD_BUG, "Handling unexpected algorithm %d", digest->algorithm); @@ -1921,6 +1922,7 @@ crypto_digest_get_digest(crypto_digest_t *digest, default: tor_assert(0); /* Unreachable. */ break; +//LCOV_EXCL_STOP } memcpy(out, r, out_len); memwipe(r, 0, sizeof(r)); @@ -2382,8 +2384,6 @@ tor_check_dh_key(int severity, BIGNUM *bn) return -1; } -#undef MIN -#define MIN(a,b) ((a)<(b)?(a):(b)) /** Given a DH key exchange object, and our peer's value of g^y (as a * <b>pubkey_len</b>-byte value in <b>pubkey</b>) generate * <b>secret_bytes_out</b> bytes of shared key material and write them @@ -2760,10 +2760,12 @@ crypto_strongest_rand(uint8_t *out, size_t out_len) while (out_len) { crypto_rand((char*) inp, DLEN); if (crypto_strongest_rand_raw(inp+DLEN, DLEN) < 0) { + // LCOV_EXCL_START log_err(LD_CRYPTO, "Failed to load strong entropy when generating an " "important key. Exiting."); /* Die with an assertion so we get a stack trace. */ tor_assert(0); + // LCOV_EXCL_STOP } if (out_len >= DLEN) { SHA512(inp, sizeof(inp), out); diff --git a/src/common/crypto_s2k.c b/src/common/crypto_s2k.c index a9140c7553..149c39344c 100644 --- a/src/common/crypto_s2k.c +++ b/src/common/crypto_s2k.c @@ -57,7 +57,8 @@ #define SCRYPT_KEY_LEN 32 /** Given an algorithm ID (one of S2K_TYPE_*), return the length of the - * specifier part of it, without the prefix type byte. */ + * specifier part of it, without the prefix type byte. Return -1 if it is not + * a valid algorithm ID. */ static int secret_to_key_spec_len(uint8_t type) { @@ -86,7 +87,8 @@ secret_to_key_key_len(uint8_t type) case S2K_TYPE_SCRYPT: return DIGEST256_LEN; default: - return -1; + tor_fragile_assert(); // LCOV_EXCL_LINE + return -1; // LCOV_EXCL_LINE } } diff --git a/src/common/handles.h b/src/common/handles.h new file mode 100644 index 0000000000..1ee2322579 --- /dev/null +++ b/src/common/handles.h @@ -0,0 +1,153 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file handles.h + * \brief Macros for C weak-handle implementation. + * + * A 'handle' is a pointer to an object that is allowed to go away while + * the handle stays alive. When you dereference the handle, you might get + * the object, or you might get "NULL". + * + * Use this pattern when an object has a single obvious lifespan, so you don't + * want to use reference counting, but when other objects might need to refer + * to the first object without caring about its lifetime. + * + * To enable a type to have handles, add a HANDLE_ENTRY() field in its + * definition, as in: + * + * struct walrus { + * HANDLE_ENTRY(wlr, walrus); + * // ... + * }; + * + * And invoke HANDLE_DECL(wlr, walrus, [static]) to declare the handle + * manipulation functions (typically in a header): + * + * // opaque handle to walrus. + * typedef struct wlr_handle_t wlr_handle_t; + * + * // make a new handle + * struct wlr_handle_t *wlr_handle_new(struct walrus *); + * + * // release a handle + * void wlr_handle_free(wlr_handle_t *); + * + * // return the pointed-to walrus, or NULL. + * struct walrus *wlr_handle_get(wlr_handle_t *). + * + * // call this function when you're about to free the walrus; + * // it invalidates all handles. (IF YOU DON'T, YOU WILL HAVE + * // DANGLING REFERENCES) + * void wlr_handles_clear(struct walrus *); + * + * Finally, use HANDLE_IMPL() to define the above functions in some + * appropriate C file: HANDLE_IMPL(wlr, walrus, [static]) + * + **/ + +#ifndef TOR_HANDLE_H +#define TOR_HANDLE_H + +#include "orconfig.h" +#include "tor_queue.h" +#include "util.h" + +#define HANDLE_ENTRY(name, structname) \ + struct name ## _handle_head_t *handle_head + +#define HANDLE_DECL(name, structname, linkage) \ + typedef struct name ## _handle_t name ## _handle_t; \ + linkage name ## _handle_t *name ## _handle_new(struct structname *object); \ + linkage void name ## _handle_free(name ## _handle_t *); \ + linkage struct structname *name ## _handle_get(name ## _handle_t *); \ + linkage void name ## _handles_clear(struct structname *object); + +/* + * Implementation notes: there are lots of possible implementations here. We + * could keep a linked list of handles, each with a backpointer to the object, + * and set all of their backpointers to NULL when the object is freed. Or we + * could have the clear function invalidate the object, but not actually let + * the object get freed until the all the handles went away. We could even + * have a hash-table mapping unique identifiers to objects, and have each + * handle be a copy of the unique identifier. (We'll want to build that last + * one eventually if we want cross-process handles.) + * + * But instead we're opting for a single independent 'head' that knows how + * many handles there are, and where the object is (or isn't). This makes + * all of our functions O(1), and most as fast as a single pointer access. + * + * The handles themselves are opaque structures holding a pointer to the head. + * We could instead have each foo_handle_t* be identical to foo_handle_head_t + * *, and save some allocations ... but doing so would make handle leaks + * harder to debug. As it stands, every handle leak is a memory leak, and + * existing memory debugging tools should help with those. We can revisit + * this decision if handles are too slow. + */ + +#define HANDLE_IMPL(name, structname, linkage) \ + /* The 'head' object for a handle-accessible type. This object */ \ + /* persists for as long as the object, or any handles, exist. */ \ + typedef struct name ## _handle_head_t { \ + struct structname *object; /* pointed-to object, or NULL */ \ + unsigned int references; /* number of existing handles */ \ + } name ## _handle_head_t; \ + \ + struct name ## _handle_t { \ + struct name ## _handle_head_t *head; /* reference to the 'head'. */ \ + }; \ + \ + linkage struct name ## _handle_t * \ + name ## _handle_new(struct structname *object) \ + { \ + tor_assert(object); \ + name ## _handle_head_t *head = object->handle_head; \ + if (PREDICT_UNLIKELY(head == NULL)) { \ + head = object->handle_head = tor_malloc_zero(sizeof(*head)); \ + head->object = object; \ + } \ + name ## _handle_t *new_ref = tor_malloc_zero(sizeof(*new_ref)); \ + new_ref->head = head; \ + ++head->references; \ + return new_ref; \ + } \ + \ + linkage void \ + name ## _handle_free(struct name ## _handle_t *ref) \ + { \ + if (! ref) return; \ + name ## _handle_head_t *head = ref->head; \ + tor_assert(head); \ + --head->references; \ + tor_free(ref); \ + if (head->object == NULL && head->references == 0) { \ + tor_free(head); \ + return; \ + } \ + } \ + \ + linkage struct structname * \ + name ## _handle_get(struct name ## _handle_t *ref) \ + { \ + tor_assert(ref); \ + name ## _handle_head_t *head = ref->head; \ + tor_assert(head); \ + return head->object; \ + } \ + \ + linkage void \ + name ## _handles_clear(struct structname *object) \ + { \ + tor_assert(object); \ + name ## _handle_head_t *head = object->handle_head; \ + if (! head) \ + return; \ + object->handle_head = NULL; \ + head->object = NULL; \ + if (head->references == 0) { \ + tor_free(head); \ + } \ + } + +#endif /* TOR_HANDLE_H */ + diff --git a/src/common/include.am b/src/common/include.am index 5afb30da6a..bae90ad977 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -68,12 +68,12 @@ LIBOR_A_SOURCES = \ src/common/log.c \ src/common/memarea.c \ src/common/util.c \ + src/common/util_bug.c \ src/common/util_format.c \ src/common/util_process.c \ src/common/sandbox.c \ src/common/workqueue.c \ src/ext/csiphash.c \ - src/ext/trunnel/trunnel.c \ $(libor_extra_source) \ $(threads_impl_source) \ $(readpassphrase_source) @@ -89,13 +89,14 @@ LIBOR_CRYPTO_A_SOURCES = \ src/common/crypto_format.c \ src/common/torgzip.c \ src/common/tortls.c \ - src/trunnel/pwbox.c \ src/common/crypto_curve25519.c \ src/common/crypto_ed25519.c LIBOR_EVENT_A_SOURCES = \ src/common/compat_libevent.c \ - src/common/procmon.c + src/common/procmon.c \ + src/common/timers.c \ + src/ext/timeouts/timeout.c src_common_libor_a_SOURCES = $(LIBOR_A_SOURCES) src_common_libor_crypto_a_SOURCES = $(LIBOR_CRYPTO_A_SOURCES) @@ -129,16 +130,19 @@ COMMONHEADERS = \ src/common/crypto_pwbox.h \ src/common/crypto_s2k.h \ src/common/di_ops.h \ + src/common/handles.h \ src/common/memarea.h \ src/common/linux_syscalls.inc \ 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 \ src/common/tortls.h \ src/common/util.h \ + src/common/util_bug.h \ src/common/util_format.h \ src/common/util_process.h \ src/common/workqueue.h diff --git a/src/common/memarea.c b/src/common/memarea.c index 0a3fd009b0..61117288c3 100644 --- a/src/common/memarea.c +++ b/src/common/memarea.c @@ -132,7 +132,7 @@ alloc_chunk(size_t sz) /** Release <b>chunk</b> from a memarea. */ static void -chunk_free_unchecked(memarea_chunk_t *chunk) +memarea_chunk_free_unchecked(memarea_chunk_t *chunk) { CHECK_SENTINEL(chunk); tor_free(chunk); @@ -155,7 +155,7 @@ memarea_drop_all(memarea_t *area) memarea_chunk_t *chunk, *next; for (chunk = area->first; chunk; chunk = next) { next = chunk->next_chunk; - chunk_free_unchecked(chunk); + memarea_chunk_free_unchecked(chunk); } area->first = NULL; /*fail fast on */ tor_free(area); @@ -171,7 +171,7 @@ memarea_clear(memarea_t *area) if (area->first->next_chunk) { for (chunk = area->first->next_chunk; chunk; chunk = next) { next = chunk->next_chunk; - chunk_free_unchecked(chunk); + memarea_chunk_free_unchecked(chunk); } area->first->next_chunk = NULL; } diff --git a/src/common/timers.c b/src/common/timers.c new file mode 100644 index 0000000000..5d8d1feafd --- /dev/null +++ b/src/common/timers.c @@ -0,0 +1,297 @@ +/* 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. + * + * 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 <b>tv</b> 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 <b>t</b> to a timeval in <b>tv_out</b> + */ +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 <b>tv</b> to the current time in <b>tv</b>. + */ +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 <b>global_timeouts</b> + */ +static void +libevent_timer_reschedule(void) +{ + struct timeval now; + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + 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); +} + +/** + * 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_cache_clear(); + 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 (BUG(global_timeouts)) + return; // LCOV_EXCL_LINE + + timeout_error_t err; + global_timeouts = timeouts_open(0, &err); + if (!global_timeouts) { + // LCOV_EXCL_START -- this can only fail on malloc failure. + log_err(LD_BUG, "Unable to open timer backend: %s", strerror(err)); + tor_assert(0); + // LCOV_EXCL_STOP + } + + 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; + + libevent_timer_reschedule(); +} + +/** + * 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 <b>t</b>, 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 <b>t</b>. + */ +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 <b>tv</b>. + * 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); + + /* 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(); +} + +/** + * Cancel the timer <b>t</b> 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 0000000000..594cf38a64 --- /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/common/util.c b/src/common/util.c index 008c682b3b..fa2953cc30 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -105,23 +105,6 @@ #endif /* ===== - * Assertion helper. - * ===== */ -/** Helper for tor_assert: report the assertion failure. */ -void -tor_assertion_failed_(const char *fname, unsigned int line, - const char *func, const char *expr) -{ - char buf[256]; - log_err(LD_BUG, "%s:%u: %s: Assertion %s failed; aborting.", - fname, line, func, expr); - tor_snprintf(buf, sizeof(buf), - "Assertion %s failed in %s at %s:%u", - expr, func, fname, line); - log_backtrace(LOG_ERR, LD_BUG, buf); -} - -/* ===== * Memory management * ===== */ #ifdef USE_DMALLOC diff --git a/src/common/util.h b/src/common/util.h index ebcf88b32d..814c8622a2 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -22,6 +22,7 @@ /* for the correct alias to struct stat */ #include <sys/stat.h> #endif +#include "util_bug.h" #ifndef O_BINARY #define O_BINARY 0 @@ -33,41 +34,6 @@ #define O_NOFOLLOW 0 #endif -/* Replace assert() with a variant that sends failures to the log before - * calling assert() normally. - */ -#ifdef NDEBUG -/* Nobody should ever want to build with NDEBUG set. 99% of our asserts will - * be outside the critical path anyway, so it's silly to disable bug-checking - * throughout the entire program just because a few asserts are slowing you - * down. Profile, optimize the critical path, and keep debugging on. - * - * And I'm not just saying that because some of our asserts check - * security-critical properties. - */ -#error "Sorry; we don't support building with NDEBUG." -#endif - -/* Sometimes we don't want to use assertions during branch coverage tests; it - * leads to tons of unreached branches which in reality are only assertions we - * didn't hit. */ -#if defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) -#define tor_assert(a) STMT_BEGIN \ - (void)(a); \ - STMT_END -#else -/** Like assert(3), but send assertion failures to the log as well as to - * stderr. */ -#define tor_assert(expr) STMT_BEGIN \ - if (PREDICT_UNLIKELY(!(expr))) { \ - tor_assertion_failed_(SHORT_FILE__, __LINE__, __func__, #expr); \ - abort(); \ - } STMT_END -#endif - -void tor_assertion_failed_(const char *fname, unsigned int line, - const char *func, const char *expr); - /* If we're building with dmalloc, we want all of our memory allocation * functions to take an extra file/line pair of arguments. If not, not. * We define DMALLOC_PARAMS to the extra parameters to insert in the @@ -81,11 +47,6 @@ void tor_assertion_failed_(const char *fname, unsigned int line, #define DMALLOC_ARGS #endif -/** Define this if you want Tor to crash when any problem comes up, - * so you can get a coredump and track things down. */ -// #define tor_fragile_assert() tor_assert(0) -#define tor_fragile_assert() - /* Memory management */ void *tor_malloc_(size_t size DMALLOC_PARAMS) ATTR_MALLOC; void *tor_malloc_zero_(size_t size DMALLOC_PARAMS) ATTR_MALLOC; diff --git a/src/common/util_bug.c b/src/common/util_bug.c new file mode 100644 index 0000000000..e3e1d6df90 --- /dev/null +++ b/src/common/util_bug.c @@ -0,0 +1,53 @@ +/* Copyright (c) 2003, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file util_bug.c + **/ + +#include "orconfig.h" +#include "util_bug.h" +#include "torlog.h" +#include "backtrace.h" + +/** Helper for tor_assert: report the assertion failure. */ +void +tor_assertion_failed_(const char *fname, unsigned int line, + const char *func, const char *expr) +{ + char buf[256]; + log_err(LD_BUG, "%s:%u: %s: Assertion %s failed; aborting.", + fname, line, func, expr); + tor_snprintf(buf, sizeof(buf), + "Assertion %s failed in %s at %s:%u", + expr, func, fname, line); + log_backtrace(LOG_ERR, LD_BUG, buf); +} + +/** Helper for tor_assert_nonfatal: report the assertion failure. */ +void +tor_bug_occurred_(const char *fname, unsigned int line, + const char *func, const char *expr, + int once) +{ + char buf[256]; + const char *once_str = once ? + " (Future instances of this warning will be silenced.)": ""; + if (! expr) { + log_warn(LD_BUG, "%s:%u: %s: This line should not have been reached.%s", + fname, line, func, once_str); + tor_snprintf(buf, sizeof(buf), + "Line unexpectedly reached at %s at %s:%u", + func, fname, line); + } else { + log_warn(LD_BUG, "%s:%u: %s: Non-fatal assertion %s failed.%s", + fname, line, func, expr, once_str); + tor_snprintf(buf, sizeof(buf), + "Non-fatal assertion %s failed in %s at %s:%u", + expr, func, fname, line); + } + log_backtrace(LOG_WARN, LD_BUG, buf); +} + diff --git a/src/common/util_bug.h b/src/common/util_bug.h new file mode 100644 index 0000000000..36056aa4bd --- /dev/null +++ b/src/common/util_bug.h @@ -0,0 +1,150 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file util_bug.h + **/ + +#ifndef TOR_UTIL_BUG_H +#define TOR_UTIL_BUG_H + +#include "orconfig.h" +#include "compat.h" +#include "testsupport.h" + +/* Replace assert() with a variant that sends failures to the log before + * calling assert() normally. + */ +#ifdef NDEBUG +/* Nobody should ever want to build with NDEBUG set. 99% of our asserts will + * be outside the critical path anyway, so it's silly to disable bug-checking + * throughout the entire program just because a few asserts are slowing you + * down. Profile, optimize the critical path, and keep debugging on. + * + * And I'm not just saying that because some of our asserts check + * security-critical properties. + */ +#error "Sorry; we don't support building with NDEBUG." +#endif + +/* Sometimes we don't want to use assertions during branch coverage tests; it + * leads to tons of unreached branches which in reality are only assertions we + * didn't hit. */ +#if defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) +#define tor_assert(a) STMT_BEGIN \ + (void)(a); \ + STMT_END +#else +/** Like assert(3), but send assertion failures to the log as well as to + * stderr. */ +#define tor_assert(expr) STMT_BEGIN \ + if (PREDICT_UNLIKELY(!(expr))) { \ + tor_assertion_failed_(SHORT_FILE__, __LINE__, __func__, #expr); \ + abort(); \ + } STMT_END +#endif + +#define tor_assert_unreached() tor_assert(0) + +/* Non-fatal bug assertions. The "unreached" variants mean "this line should + * never be reached." The "once" variants mean "Don't log a warning more than + * once". + * + * The 'BUG' macro checks a boolean condition and logs an error message if it + * is true. Example usage: + * if (BUG(x == NULL)) + * return -1; + */ + +#ifdef ALL_BUGS_ARE_FATAL +#define tor_assert_nonfatal_unreached() tor_assert(0) +#define tor_assert_nonfatal(cond) tor_assert((cond)) +#define tor_assert_nonfatal_unreached_once() tor_assert(0) +#define tor_assert_nonfatal_once(cond) tor_assert((cond)) +#define BUG(cond) \ + (PREDICT_UNLIKELY(cond) ? \ + (tor_assertion_failed_(SHORT_FILE__,__LINE__,__func__,#cond), abort(), 1) \ + : 0) +#elif defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) +#define tor_assert_nonfatal_unreached() STMT_NIL +#define tor_assert_nonfatal(cond) ((void)(cond)) +#define tor_assert_nonfatal_unreached_once() STMT_NIL +#define tor_assert_nonfatal_once(cond) ((void)(cond)) +#define BUG(cond) (PREDICT_UNLIKELY(cond) ? 1 : 0) +#else /* Normal case, !ALL_BUGS_ARE_FATAL, !DISABLE_ASSERTS_IN_UNIT_TESTS */ +#define tor_assert_nonfatal_unreached() STMT_BEGIN \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, NULL, 0); \ + STMT_END +#define tor_assert_nonfatal(cond) STMT_BEGIN \ + if (PREDICT_UNLIKELY(!(cond))) { \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 0); \ + } \ + STMT_END +#define tor_assert_nonfatal_unreached_once() STMT_BEGIN \ + static int warning_logged__ = 0; \ + if (!warning_logged__) { \ + warning_logged__ = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, NULL, 1); \ + } \ + STMT_END +#define tor_assert_nonfatal_once(cond) STMT_BEGIN \ + static int warning_logged__ = 0; \ + if (!warning_logged__ && PREDICT_UNLIKELY(!(cond))) { \ + warning_logged__ = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1); \ + } \ + STMT_END +#define BUG(cond) \ + (PREDICT_UNLIKELY(cond) ? \ + (tor_bug_occurred_(SHORT_FILE__,__LINE__,__func__,#cond,0), 1) \ + : 0) +#endif + +#ifdef __GNUC__ +#define IF_BUG_ONCE__(cond,var) \ + if (({ \ + static int var = 0; \ + int bool_result = (cond); \ + if (PREDICT_UNLIKELY(bool_result) && !var) { \ + var = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1); \ + } \ + PREDICT_UNLIKELY(bool_result); })) +#else +#define IF_BUG_ONCE__(cond,var) \ + static int var = 0; \ + if (PREDICT_UNLIKELY(cond)) ? \ + (var ? 1 : \ + (var=1, \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1), \ + 1)) \ + : 0) +#endif +#define IF_BUG_ONCE_VARNAME_(a) \ + warning_logged_on_ ## a ## __ +#define IF_BUG_ONCE_VARNAME__(a) \ + IF_BUG_ONCE_VARNAME_(a) + +/** This macro behaves as 'if (bug(x))', except that it only logs its + * warning once, no matter how many times it triggers. + */ + +#define IF_BUG_ONCE(cond) \ + IF_BUG_ONCE__((cond), \ + IF_BUG_ONCE_VARNAME__(__LINE__)) + +/** Define this if you want Tor to crash when any problem comes up, + * so you can get a coredump and track things down. */ +// #define tor_fragile_assert() tor_assert_unreached(0) +#define tor_fragile_assert() tor_assert_nonfatal_unreached_once() + +void tor_assertion_failed_(const char *fname, unsigned int line, + const char *func, const char *expr); +void tor_bug_occurred_(const char *fname, unsigned int line, + const char *func, const char *expr, + int once); + +#endif + diff --git a/src/config/torrc.minimal.in-staging b/src/config/torrc.minimal.in-staging index 248cb5cf02..d4dfd5f6bb 100644 --- a/src/config/torrc.minimal.in-staging +++ b/src/config/torrc.minimal.in-staging @@ -98,6 +98,8 @@ # OutboundBindAddress 10.0.0.5 ## A handle for your relay, so people don't have to refer to it by key. +## Nicknames must be between 1 and 19 characters inclusive, and must +## contain only the characters [a-zA-Z0-9]. #Nickname ididnteditheconfig ## Define these to limit how much relayed traffic you will allow. Your diff --git a/src/config/torrc.sample.in b/src/config/torrc.sample.in index 248cb5cf02..d4dfd5f6bb 100644 --- a/src/config/torrc.sample.in +++ b/src/config/torrc.sample.in @@ -98,6 +98,8 @@ # OutboundBindAddress 10.0.0.5 ## A handle for your relay, so people don't have to refer to it by key. +## Nicknames must be between 1 and 19 characters inclusive, and must +## contain only the characters [a-zA-Z0-9]. #Nickname ididnteditheconfig ## Define these to limit how much relayed traffic you will allow. Your diff --git a/src/ext/README b/src/ext/README index 7ce1bc3b74..c180927b86 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/ed25519/donna/ed25519_tor.c b/src/ext/ed25519/donna/ed25519_tor.c index 52b259dfe1..07f6a0f23a 100644 --- a/src/ext/ed25519/donna/ed25519_tor.c +++ b/src/ext/ed25519/donna/ed25519_tor.c @@ -44,7 +44,8 @@ typedef unsigned char ed25519_signature[64]; typedef unsigned char ed25519_public_key[32]; typedef unsigned char ed25519_secret_key[32]; -static void gettweak(unsigned char *out, const unsigned char *param); +static void ed25519_donna_gettweak(unsigned char *out, + const unsigned char *param); static int ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen, const ed25519_public_key pk, const ed25519_signature RS); @@ -242,7 +243,7 @@ ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen, } static void -gettweak(unsigned char *out, const unsigned char *param) +ed25519_donna_gettweak(unsigned char *out, const unsigned char *param) { static const char str[] = "Derive temporary signing key"; ed25519_hash_context ctx; @@ -266,7 +267,7 @@ ed25519_donna_blind_secret_key(unsigned char *out, const unsigned char *inp, ed25519_hash_context ctx; bignum256modm ALIGN(16) sk, t; - gettweak(tweak, param); + ed25519_donna_gettweak(tweak, param); expand256_modm(t, tweak, 32); expand256_modm(sk, inp, 32); @@ -297,7 +298,7 @@ ed25519_donna_blind_public_key(unsigned char *out, const unsigned char *inp, ge25519 ALIGN(16) A, Aprime; bignum256modm ALIGN(16) t; - gettweak(tweak, param); + ed25519_donna_gettweak(tweak, param); expand256_modm(t, tweak, 32); /* No "ge25519_unpack", negate the public key. */ diff --git a/src/ext/ed25519/ref10/blinding.c b/src/ext/ed25519/ref10/blinding.c index 4d9a9cbbe7..ee3e8666fa 100644 --- a/src/ext/ed25519/ref10/blinding.c +++ b/src/ext/ed25519/ref10/blinding.c @@ -10,7 +10,7 @@ #include "crypto.h" static void -gettweak(unsigned char *out, const unsigned char *param) +ed25519_ref10_gettweak(unsigned char *out, const unsigned char *param) { const char str[] = "Derive temporary signing key"; crypto_hash_sha512_2(out, (const unsigned char*)str, strlen(str), param, 32); @@ -26,7 +26,7 @@ int ed25519_ref10_blind_secret_key(unsigned char *out, const char str[] = "Derive temporary signing key hash input"; unsigned char tweak[64]; unsigned char zero[32]; - gettweak(tweak, param); + ed25519_ref10_gettweak(tweak, param); memset(zero, 0, 32); sc_muladd(out, inp, tweak, zero); @@ -50,7 +50,7 @@ int ed25519_ref10_blind_public_key(unsigned char *out, ge_p3 A; ge_p2 Aprime; - gettweak(tweak, param); + ed25519_ref10_gettweak(tweak, param); memset(zero, 0, sizeof(zero)); /* Not the greatest implementation of all of this. I wish I had diff --git a/src/ext/include.am b/src/ext/include.am index bf678f2c9d..d1a3b47a63 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -12,7 +12,11 @@ EXTHEADERS = \ src/ext/strlcpy.c \ 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) @@ -148,3 +152,21 @@ 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 + diff --git a/src/ext/timeouts/Makefile b/src/ext/timeouts/Makefile new file mode 100644 index 0000000000..554ebb9ddd --- /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 0000000000..ece75d42d4 --- /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 0000000000..3ee72f3eff --- /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 > $(@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 > $(@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 > $(@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 > $(@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 0000000000..64a921d3de --- /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 0000000000..6321247421 --- /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 0000000000..4306745f21 --- /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 0000000000..3e6374ed52 --- /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 0000000000..f1166a4d7e --- /dev/null +++ b/src/ext/timeouts/bench/bench-heap.c @@ -0,0 +1,236 @@ +/* + * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@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 0000000000..bdb02f0704 --- /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@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@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 0000000000..0cba1af83e --- /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 0000000000..0d4cee44a0 --- /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 0000000000..bc1f7cf177 --- /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 0000000000..6e143c65e1 --- /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 0000000000..0f06fce30b --- /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 0000000000..4d4e54cba6 --- /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 0000000000..8077129376 --- /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 0000000000..a018f33b95 --- /dev/null +++ b/src/ext/timeouts/timeout-bitops.c @@ -0,0 +1,254 @@ +#include <stdint.h> +#include <limits.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) + +#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_BIT == 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 0000000000..fc727a6b42 --- /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 0000000000..f528576ffb --- /dev/null +++ b/src/ext/timeouts/timeout.c @@ -0,0 +1,754 @@ +/* ========================================================================== + * 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. + * ========================================================================== + */ +#ifdef HAVE_CONFIG_H +#include "orconfig.h" +#endif +#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" + +#ifndef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 0 +#endif + +#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 = (int) (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), (int)_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 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); +} /* 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 0000000000..3b08f19255 --- /dev/null +++ b/src/ext/timeouts/timeout.h @@ -0,0 +1,256 @@ +/* ========================================================================== + * 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@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); + 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_get_curtime(struct timeouts *); +/* Return the current tick. */ + +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 */ diff --git a/src/or/buffers.c b/src/or/buffers.c index f93cc48f33..cdc71ab9db 100644 --- a/src/or/buffers.c +++ b/src/or/buffers.c @@ -107,7 +107,7 @@ chunk_repack(chunk_t *chunk) /** Keep track of total size of allocated chunks for consistency asserts */ static size_t total_bytes_allocated_in_chunks = 0; static void -chunk_free_unchecked(chunk_t *chunk) +buf_chunk_free_unchecked(chunk_t *chunk) { if (!chunk) return; @@ -228,7 +228,7 @@ buf_pullup(buf_t *buf, size_t bytes) dest->next = src->next; if (buf->tail == src) buf->tail = dest; - chunk_free_unchecked(src); + buf_chunk_free_unchecked(src); } else { memcpy(CHUNK_WRITE_PTR(dest), src->data, n); dest->datalen += n; @@ -274,7 +274,7 @@ buf_remove_from_front(buf_t *buf, size_t n) buf->head = victim->next; if (buf->tail == victim) buf->tail = NULL; - chunk_free_unchecked(victim); + buf_chunk_free_unchecked(victim); } } check(); @@ -314,7 +314,7 @@ buf_clear(buf_t *buf) buf->datalen = 0; for (chunk = buf->head; chunk; chunk = next) { next = chunk->next; - chunk_free_unchecked(chunk); + buf_chunk_free_unchecked(chunk); } buf->head = buf->tail = NULL; } diff --git a/src/or/channel.c b/src/or/channel.c index 5f69a0864b..f3939399b0 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -3510,7 +3510,7 @@ channel_dump_statistics, (channel_t *chan, int severity)) have_remote_addr = channel_get_addr_if_possible(chan, &remote_addr); if (have_remote_addr) { char *actual = tor_strdup(channel_get_actual_remote_descr(chan)); - remote_addr_str = tor_dup_addr(&remote_addr); + remote_addr_str = tor_addr_to_str_dup(&remote_addr); tor_log(severity, LD_GENERAL, " * Channel " U64_FORMAT " says its remote address" " is %s, and gives a canonical description of \"%s\" and an " diff --git a/src/or/channel.h b/src/or/channel.h index 129c0c2013..a8c337e107 100644 --- a/src/or/channel.h +++ b/src/or/channel.h @@ -18,7 +18,7 @@ typedef void (*channel_cell_handler_fn_ptr)(channel_t *, cell_t *); typedef void (*channel_var_cell_handler_fn_ptr)(channel_t *, var_cell_t *); struct cell_queue_entry_s; -TOR_SIMPLEQ_HEAD(chan_cell_queue, cell_queue_entry_s) incoming_queue; +TOR_SIMPLEQ_HEAD(chan_cell_queue, cell_queue_entry_s); typedef struct chan_cell_queue chan_cell_queue_t; /** diff --git a/src/or/channeltls.c b/src/or/channeltls.c index c65af5d040..2128b0924d 100644 --- a/src/or/channeltls.c +++ b/src/or/channeltls.c @@ -554,7 +554,7 @@ channel_tls_get_remote_descr_method(channel_t *chan, int flags) break; case GRD_FLAG_ORIGINAL: /* Actual address with port */ - addr_str = tor_dup_addr(&(tlschan->conn->real_addr)); + addr_str = tor_addr_to_str_dup(&(tlschan->conn->real_addr)); tor_snprintf(buf, MAX_DESCR_LEN + 1, "%s:%u", addr_str, conn->port); tor_free(addr_str); @@ -567,7 +567,7 @@ channel_tls_get_remote_descr_method(channel_t *chan, int flags) break; case GRD_FLAG_ORIGINAL|GRD_FLAG_ADDR_ONLY: /* Actual address, no port */ - addr_str = tor_dup_addr(&(tlschan->conn->real_addr)); + addr_str = tor_addr_to_str_dup(&(tlschan->conn->real_addr)); strlcpy(buf, addr_str, sizeof(buf)); tor_free(addr_str); answer = buf; diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index a5a933e6b0..e6fe3f0c37 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -47,10 +47,6 @@ #include "routerset.h" #include "crypto.h" -#ifndef MIN -#define MIN(a,b) ((a)<(b)?(a):(b)) -#endif - static channel_t * channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port, const char *id_digest); diff --git a/src/or/circuituse.c b/src/or/circuituse.c index 31003ea095..b5959944f1 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -1067,7 +1067,7 @@ circuit_predict_and_launch_new(void) if (rep_hist_get_predicted_internal(now, &hidserv_needs_uptime, &hidserv_needs_capacity) && ((num_uptime_internal<2 && hidserv_needs_uptime) || - num_internal<2) + num_internal<3) && router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN) { if (hidserv_needs_uptime) flags |= CIRCLAUNCH_NEED_UPTIME; diff --git a/src/or/config.c b/src/or/config.c index 5d938d101a..2e14ba69dc 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -2796,7 +2796,8 @@ options_validate(or_options_t *old_options, or_options_t *options, } else { if (!is_legal_nickname(options->Nickname)) { tor_asprintf(msg, - "Nickname '%s' is wrong length or contains illegal characters.", + "Nickname '%s', nicknames must be between 1 and 19 characters " + "inclusive, and must contain only the characters [a-zA-Z0-9].", options->Nickname); return -1; } diff --git a/src/or/connection.c b/src/or/connection.c index 118e239176..1bd1a92e39 100644 --- a/src/or/connection.c +++ b/src/or/connection.c @@ -665,9 +665,7 @@ connection_free,(connection_t *conn)) return; tor_assert(!connection_is_on_closeable_list(conn)); tor_assert(!connection_in_array(conn)); - if (conn->linked_conn) { - log_err(LD_BUG, "Called with conn->linked_conn still set."); - tor_fragile_assert(); + if (BUG(conn->linked_conn)) { conn->linked_conn->linked_conn = NULL; if (! conn->linked_conn->marked_for_close && conn->linked_conn->reading_from_linked_conn) @@ -1564,7 +1562,7 @@ connection_handle_listener_read(connection_t *conn, int new_type) /* remember the remote address */ tor_addr_copy(&newconn->addr, &addr); newconn->port = port; - newconn->address = tor_dup_addr(&addr); + newconn->address = tor_addr_to_str_dup(&addr); if (new_type == CONN_TYPE_AP && conn->socket_family != AF_UNIX) { log_info(LD_NET, "New SOCKS connection opened from %s.", @@ -2538,7 +2536,7 @@ retry_listener_ports(smartlist_t *old_conns, real_port, listensockaddr, sizeof(struct sockaddr_storage)); - address = tor_dup_addr(&port->addr); + address = tor_addr_to_str_dup(&port->addr); } if (listensockaddr) { @@ -3644,7 +3642,7 @@ connection_read_to_buf(connection_t *conn, ssize_t *max_to_read, * take us over our read allotment, but really we shouldn't be * believing that SSL bytes are the same as TCP bytes anyway. */ int r2 = read_to_buf_tls(or_conn->tls, pending, conn->inbuf); - if (r2<0) { + if (BUG(r2<0)) { log_warn(LD_BUG, "apparently, reading pending bytes can fail."); return -1; } diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index 754e9762ea..e58d32e7a5 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -1691,7 +1691,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn, rend_service_authorization_t *client_auth = rend_client_lookup_service_authorization(socks->address); - const char *cookie = NULL; + const uint8_t *cookie = NULL; rend_auth_type_t auth_type = REND_NO_AUTH; if (client_auth) { log_info(LD_REND, "Using previously configured client authorization " @@ -1703,7 +1703,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn, /* Fill in the rend_data field so we can start doing a connection to * a hidden service. */ rend_data_t *rend_data = ENTRY_TO_EDGE_CONN(conn)->rend_data = - rend_data_client_create(socks->address, NULL, cookie, auth_type); + rend_data_client_create(socks->address, NULL, (char *) cookie, auth_type); if (rend_data == NULL) { return -1; } @@ -2433,7 +2433,7 @@ connection_ap_handshake_send_resolve(entry_connection_t *ap_conn) if (!base_conn->address) { /* This might be unnecessary. XXXX */ - base_conn->address = tor_dup_addr(&base_conn->addr); + base_conn->address = tor_addr_to_str_dup(&base_conn->addr); } base_conn->state = AP_CONN_STATE_RESOLVE_WAIT; log_info(LD_APP,"Address sent for resolve, ap socket "TOR_SOCKET_T_FORMAT diff --git a/src/or/connection_or.c b/src/or/connection_or.c index ea49bdba77..f8be763792 100644 --- a/src/or/connection_or.c +++ b/src/or/connection_or.c @@ -934,7 +934,7 @@ connection_or_init_conn_from_address(or_connection_t *conn, } conn->nickname = tor_strdup(node_get_nickname(r)); tor_free(conn->base_.address); - conn->base_.address = tor_dup_addr(&node_ap.addr); + conn->base_.address = tor_addr_to_str_dup(&node_ap.addr); } else { conn->nickname = tor_malloc(HEX_DIGEST_LEN+2); conn->nickname[0] = '$'; @@ -942,7 +942,7 @@ connection_or_init_conn_from_address(or_connection_t *conn, conn->identity_digest, DIGEST_LEN); tor_free(conn->base_.address); - conn->base_.address = tor_dup_addr(addr); + conn->base_.address = tor_addr_to_str_dup(addr); } /* @@ -1281,11 +1281,9 @@ connection_or_connect, (const tor_addr_t *_addr, uint16_t port, switch (connection_connect(TO_CONN(conn), conn->base_.address, &addr, port, &socket_error)) { case -1: - /* If the connection failed immediately, and we're using - * a proxy, our proxy is down. Don't blame the Tor server. */ - if (conn->base_.proxy_state == PROXY_INFANT) - entry_guard_register_connect_status(conn->identity_digest, - 0, 1, time(NULL)); + /* We failed to establish a connection probably because of a local + * error. No need to blame the guard in this case. Notify the networking + * system of this failure. */ connection_or_connect_failed(conn, errno_to_orconn_end_reason(socket_error), tor_socket_strerror(socket_error)); diff --git a/src/or/control.c b/src/or/control.c index e06d7d28a2..862c836e40 100644 --- a/src/or/control.c +++ b/src/or/control.c @@ -3788,14 +3788,18 @@ handle_control_add_onion(control_connection_t *conn, * the other arguments are malformed. */ smartlist_t *port_cfgs = smartlist_new(); + smartlist_t *auth_clients = NULL; + smartlist_t *auth_created_clients = NULL; int discard_pk = 0; int detach = 0; int max_streams = 0; int max_streams_close_circuit = 0; + rend_auth_type_t auth_type = REND_NO_AUTH; for (size_t i = 1; i < arg_len; i++) { static const char *port_prefix = "Port="; static const char *flags_prefix = "Flags="; static const char *max_s_prefix = "MaxStreams="; + static const char *auth_prefix = "ClientAuth="; const char *arg = smartlist_get(args, i); if (!strcasecmpstart(arg, port_prefix)) { @@ -3826,10 +3830,12 @@ handle_control_add_onion(control_connection_t *conn, * connection. * * 'MaxStreamsCloseCircuit' - Close the circuit if MaxStreams is * exceeded. + * * 'BasicAuth' - Client authorization using the 'basic' method. */ static const char *discard_flag = "DiscardPK"; static const char *detach_flag = "Detach"; static const char *max_s_close_flag = "MaxStreamsCloseCircuit"; + static const char *basicauth_flag = "BasicAuth"; smartlist_t *flags = smartlist_new(); int bad = 0; @@ -3848,6 +3854,8 @@ handle_control_add_onion(control_connection_t *conn, detach = 1; } else if (!strcasecmp(flag, max_s_close_flag)) { max_streams_close_circuit = 1; + } else if (!strcasecmp(flag, basicauth_flag)) { + auth_type = REND_BASIC_AUTH; } else { connection_printf_to_buf(conn, "512 Invalid 'Flags' argument: %s\r\n", @@ -3860,6 +3868,42 @@ handle_control_add_onion(control_connection_t *conn, smartlist_free(flags); if (bad) goto out; + } else if (!strcasecmpstart(arg, auth_prefix)) { + char *err_msg = NULL; + int created = 0; + rend_authorized_client_t *client = + add_onion_helper_clientauth(arg + strlen(auth_prefix), + &created, &err_msg); + if (!client) { + if (err_msg) { + connection_write_str_to_buf(err_msg, conn); + tor_free(err_msg); + } + goto out; + } + + if (auth_clients != NULL) { + int bad = 0; + SMARTLIST_FOREACH_BEGIN(auth_clients, rend_authorized_client_t *, ac) { + if (strcmp(ac->client_name, client->client_name) == 0) { + bad = 1; + break; + } + } SMARTLIST_FOREACH_END(ac); + if (bad) { + connection_printf_to_buf(conn, + "512 Duplicate name in ClientAuth\r\n"); + rend_authorized_client_free(client); + goto out; + } + } else { + auth_clients = smartlist_new(); + auth_created_clients = smartlist_new(); + } + smartlist_add(auth_clients, client); + if (created) { + smartlist_add(auth_created_clients, client); + } } else { connection_printf_to_buf(conn, "513 Invalid argument\r\n"); goto out; @@ -3868,6 +3912,18 @@ handle_control_add_onion(control_connection_t *conn, if (smartlist_len(port_cfgs) == 0) { connection_printf_to_buf(conn, "512 Missing 'Port' argument\r\n"); goto out; + } else if (auth_type == REND_NO_AUTH && auth_clients != NULL) { + connection_printf_to_buf(conn, "512 No auth type specified\r\n"); + goto out; + } else if (auth_type != REND_NO_AUTH && auth_clients == NULL) { + connection_printf_to_buf(conn, "512 No auth clients specified\r\n"); + goto out; + } else if ((auth_type == REND_BASIC_AUTH && + smartlist_len(auth_clients) > 512) || + (auth_type == REND_STEALTH_AUTH && + smartlist_len(auth_clients) > 16)) { + connection_printf_to_buf(conn, "512 Too many auth clients\r\n"); + goto out; } /* Parse the "keytype:keyblob" argument. */ @@ -3888,35 +3944,21 @@ handle_control_add_onion(control_connection_t *conn, } tor_assert(!err_msg); - /* Create the HS, using private key pk, and port config port_cfg. + /* Create the HS, using private key pk, client authentication auth_type, + * the list of auth_clients, and port config port_cfg. * rend_service_add_ephemeral() will take ownership of pk and port_cfg, * regardless of success/failure. */ char *service_id = NULL; int ret = rend_service_add_ephemeral(pk, port_cfgs, max_streams, max_streams_close_circuit, + auth_type, auth_clients, &service_id); port_cfgs = NULL; /* port_cfgs is now owned by the rendservice code. */ + auth_clients = NULL; /* so is auth_clients */ switch (ret) { case RSAE_OKAY: { - char *buf = NULL; - tor_assert(service_id); - if (key_new_alg) { - tor_assert(key_new_blob); - tor_asprintf(&buf, - "250-ServiceID=%s\r\n" - "250-PrivateKey=%s:%s\r\n" - "250 OK\r\n", - service_id, - key_new_alg, - key_new_blob); - } else { - tor_asprintf(&buf, - "250-ServiceID=%s\r\n" - "250 OK\r\n", - service_id); - } if (detach) { if (!detached_onion_services) detached_onion_services = smartlist_new(); @@ -3927,9 +3969,26 @@ handle_control_add_onion(control_connection_t *conn, smartlist_add(conn->ephemeral_onion_services, service_id); } - connection_write_str_to_buf(buf, conn); - memwipe(buf, 0, strlen(buf)); - tor_free(buf); + tor_assert(service_id); + connection_printf_to_buf(conn, "250-ServiceID=%s\r\n", service_id); + if (key_new_alg) { + tor_assert(key_new_blob); + connection_printf_to_buf(conn, "250-PrivateKey=%s:%s\r\n", + key_new_alg, key_new_blob); + } + if (auth_created_clients) { + SMARTLIST_FOREACH(auth_created_clients, rend_authorized_client_t *, ac, { + char *encoded = rend_auth_encode_cookie(ac->descriptor_cookie, + auth_type); + tor_assert(encoded); + connection_printf_to_buf(conn, "250-ClientAuth=%s:%s\r\n", + ac->client_name, encoded); + memwipe(encoded, 0, strlen(encoded)); + tor_free(encoded); + }); + } + + connection_printf_to_buf(conn, "250 OK\r\n"); break; } case RSAE_BADPRIVKEY: @@ -3941,6 +4000,9 @@ handle_control_add_onion(control_connection_t *conn, case RSAE_BADVIRTPORT: connection_printf_to_buf(conn, "512 Invalid VIRTPORT/TARGET\r\n"); break; + case RSAE_BADAUTH: + connection_printf_to_buf(conn, "512 Invalid client authorization\r\n"); + break; case RSAE_INTERNAL: /* FALLSTHROUGH */ default: connection_printf_to_buf(conn, "551 Failed to add Onion Service\r\n"); @@ -3957,6 +4019,16 @@ handle_control_add_onion(control_connection_t *conn, smartlist_free(port_cfgs); } + if (auth_clients) { + SMARTLIST_FOREACH(auth_clients, rend_authorized_client_t *, ac, + rend_authorized_client_free(ac)); + smartlist_free(auth_clients); + } + if (auth_created_clients) { + // Do not free entries; they are the same as auth_clients + smartlist_free(auth_created_clients); + } + SMARTLIST_FOREACH(args, char *, cp, { memwipe(cp, 0, strlen(cp)); tor_free(cp); @@ -4065,6 +4137,65 @@ add_onion_helper_keyarg(const char *arg, int discard_pk, return pk; } +/** Helper function to handle parsing a ClientAuth argument to the + * ADD_ONION command. Return a new rend_authorized_client_t, or NULL + * and an optional control protocol error message on failure. The + * caller is responsible for freeing the returned auth_client and err_msg. + * + * If 'created' is specified, it will be set to 1 when a new cookie has + * been generated. + */ +STATIC rend_authorized_client_t * +add_onion_helper_clientauth(const char *arg, int *created, char **err_msg) +{ + int ok = 0; + + tor_assert(arg); + tor_assert(created); + tor_assert(err_msg); + *err_msg = NULL; + + smartlist_t *auth_args = smartlist_new(); + rend_authorized_client_t *client = + tor_malloc_zero(sizeof(rend_authorized_client_t)); + smartlist_split_string(auth_args, arg, ":", 0, 0); + if (smartlist_len(auth_args) < 1 || smartlist_len(auth_args) > 2) { + *err_msg = tor_strdup("512 Invalid ClientAuth syntax\r\n"); + goto err; + } + client->client_name = tor_strdup(smartlist_get(auth_args, 0)); + if (smartlist_len(auth_args) == 2) { + char *decode_err_msg = NULL; + if (rend_auth_decode_cookie(smartlist_get(auth_args, 1), + client->descriptor_cookie, + NULL, &decode_err_msg) < 0) { + tor_assert(decode_err_msg); + tor_asprintf(err_msg, "512 %s\r\n", decode_err_msg); + tor_free(decode_err_msg); + goto err; + } + *created = 0; + } else { + crypto_rand((char *) client->descriptor_cookie, REND_DESC_COOKIE_LEN); + *created = 1; + } + + if (!rend_valid_client_name(client->client_name)) { + *err_msg = tor_strdup("512 Invalid name in ClientAuth\r\n"); + goto err; + } + + ok = 1; + err: + SMARTLIST_FOREACH(auth_args, char *, arg, tor_free(arg)); + smartlist_free(auth_args); + if (!ok) { + rend_authorized_client_free(client); + client = NULL; + } + return client; +} + /** Called when we get a DEL_ONION command; parse the body, and remove * the existing ephemeral Onion Service. */ static int diff --git a/src/or/control.h b/src/or/control.h index 008bfb1c3b..b3902e64bd 100644 --- a/src/or/control.h +++ b/src/or/control.h @@ -259,6 +259,8 @@ STATIC crypto_pk_t *add_onion_helper_keyarg(const char *arg, int discard_pk, const char **key_new_alg_out, char **key_new_blob_out, char **err_msg_out); +STATIC rend_authorized_client_t * +add_onion_helper_clientauth(const char *arg, int *created, char **err_msg_out); #endif #endif diff --git a/src/or/directory.c b/src/or/directory.c index 8dc018a662..7d1bbf0c8c 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -1181,7 +1181,7 @@ directory_initiate_command_rend(const tor_addr_port_t *or_addr_port, /* set up conn so it's got all the data we need to remember */ tor_addr_copy(&conn->base_.addr, &addr); conn->base_.port = port; - conn->base_.address = tor_dup_addr(&addr); + conn->base_.address = tor_addr_to_str_dup(&addr); memcpy(conn->identity_digest, digest, DIGEST_LEN); conn->base_.purpose = dir_purpose; @@ -3703,7 +3703,7 @@ connection_dir_would_close_consensus_conn_helper(void) * consensus, and we are still bootstrapping (that is, we have no usable * consensus), we don't want to close any until one starts downloading. */ if (!networkstatus_consensus_is_downloading_usable_flavor() - && networkstatus_consensus_is_boostrapping(time(NULL))) { + && networkstatus_consensus_is_bootstrapping(time(NULL))) { return 0; } @@ -3737,7 +3737,7 @@ connection_dir_avoid_extra_connection_for_purpose(unsigned int purpose) * bootstrapping (that is, we have no usable consensus), we can be sure that * any further connections would be excess. */ if (networkstatus_consensus_is_downloading_usable_flavor() - && networkstatus_consensus_is_boostrapping(time(NULL))) { + && networkstatus_consensus_is_bootstrapping(time(NULL))) { return 1; } @@ -3778,12 +3778,12 @@ connection_dir_close_consensus_conn_if_extra(dir_connection_t *conn) return 0; } - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( time(NULL)); /* We don't want to check other connections to see if they are downloading, * as this is prone to race-conditions. So leave it for - * connection_dir_consider_close_extra_consensus_conns() to clean up. + * connection_dir_close_extra_consensus_conns(() to clean up. * * But if conn has just started connecting, or we have a consensus already, * we can be sure it's not needed any more. */ @@ -3823,7 +3823,7 @@ connection_dir_close_extra_consensus_conns(void) return; } - int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( time(NULL)); const char *usable_resource = networkstatus_get_flavor_name( @@ -3932,7 +3932,7 @@ find_dl_schedule(download_status_t *dls, const or_options_t *options) const int dir_server = dir_server_mode(options); const int multi_d = networkstatus_consensus_can_use_multiple_directories( options); - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( time(NULL)); const int use_fallbacks = networkstatus_consensus_can_use_extra_fallbacks( options); diff --git a/src/or/dirserv.c b/src/or/dirserv.c index a045f3ac55..f012b7bf64 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2200,7 +2200,7 @@ set_routerstatus_from_routerinfo(routerstatus_t *rs, rs->is_valid = node->is_valid; - if (node->is_fast && + if (node->is_fast && node->is_stable && ((options->AuthDirGuardBWGuarantee && routerbw_kb >= options->AuthDirGuardBWGuarantee/1000) || routerbw_kb >= MIN(guard_bandwidth_including_exits_kb, diff --git a/src/or/dnsserv.c b/src/or/dnsserv.c index 74f17ce78c..edca50f6f9 100644 --- a/src/or/dnsserv.c +++ b/src/or/dnsserv.c @@ -130,7 +130,7 @@ evdns_server_callback(struct evdns_server_request *req, void *data_) tor_addr_copy(&TO_CONN(conn)->addr, &tor_addr); TO_CONN(conn)->port = port; - TO_CONN(conn)->address = tor_dup_addr(&tor_addr); + TO_CONN(conn)->address = tor_addr_to_str_dup(&tor_addr); if (q->type == EVDNS_TYPE_A || q->type == EVDNS_TYPE_AAAA || q->type == EVDNS_QTYPE_ALL) { @@ -205,7 +205,7 @@ dnsserv_launch_request(const char *name, int reverse, tor_addr_copy(&TO_CONN(conn)->addr, &control_conn->base_.addr); #ifdef AF_UNIX /* - * The control connection can be AF_UNIX and if so tor_dup_addr will + * The control connection can be AF_UNIX and if so tor_addr_to_str_dup will * unhelpfully say "<unknown address type>"; say "(Tor_internal)" * instead. */ @@ -214,11 +214,11 @@ dnsserv_launch_request(const char *name, int reverse, TO_CONN(conn)->address = tor_strdup("(Tor_internal)"); } else { TO_CONN(conn)->port = control_conn->base_.port; - TO_CONN(conn)->address = tor_dup_addr(&control_conn->base_.addr); + TO_CONN(conn)->address = tor_addr_to_str_dup(&control_conn->base_.addr); } #else TO_CONN(conn)->port = control_conn->base_.port; - TO_CONN(conn)->address = tor_dup_addr(&control_conn->base_.addr); + TO_CONN(conn)->address = tor_addr_to_str_dup(&control_conn->base_.addr); #endif if (reverse) diff --git a/src/or/ext_orport.c b/src/or/ext_orport.c index aa1b3e26fe..8ba3c6afa3 100644 --- a/src/or/ext_orport.c +++ b/src/or/ext_orport.c @@ -461,8 +461,8 @@ connection_ext_or_handle_cmd_useraddr(connection_t *conn, return -1; { /* do some logging */ - char *old_address = tor_dup_addr(&conn->addr); - char *new_address = tor_dup_addr(&addr); + char *old_address = tor_addr_to_str_dup(&conn->addr); + char *new_address = tor_addr_to_str_dup(&addr); log_debug(LD_NET, "Received USERADDR." "We rewrite our address from '%s:%u' to '%s:%u'.", @@ -478,7 +478,7 @@ connection_ext_or_handle_cmd_useraddr(connection_t *conn, if (conn->address) { tor_free(conn->address); } - conn->address = tor_dup_addr(&addr); + conn->address = tor_addr_to_str_dup(&addr); return 0; } diff --git a/src/or/hibernate.c b/src/or/hibernate.c index 9408925d96..3666abbcf4 100644 --- a/src/or/hibernate.c +++ b/src/or/hibernate.c @@ -28,6 +28,7 @@ hibernating, phase 2: #include "config.h" #include "connection.h" #include "connection_edge.h" +#include "control.h" #include "hibernate.h" #include "main.h" #include "router.h" @@ -111,11 +112,34 @@ static int cfg_start_day = 0, cfg_start_min = 0; /** @} */ +static const char *hibernate_state_to_string(hibernate_state_t state); static void reset_accounting(time_t now); static int read_bandwidth_usage(void); static time_t start_of_accounting_period_after(time_t now); static time_t start_of_accounting_period_containing(time_t now); static void accounting_set_wakeup_time(void); +static void on_hibernate_state_change(hibernate_state_t prev_state); + +/** + * Return the human-readable name for the hibernation state <b>state</b> + */ +static const char * +hibernate_state_to_string(hibernate_state_t state) +{ + static char buf[64]; + switch (state) { + case HIBERNATE_STATE_EXITING: return "EXITING"; + case HIBERNATE_STATE_LOWBANDWIDTH: return "SOFT"; + case HIBERNATE_STATE_DORMANT: return "HARD"; + case HIBERNATE_STATE_INITIAL: + case HIBERNATE_STATE_LIVE: + return "AWAKE"; + default: + log_warn(LD_BUG, "unknown hibernate state %d", state); + tor_snprintf(buf, sizeof(buf), "unknown [%d]", state); + return buf; + } +} /* ************ * Functions for bandwidth accounting. @@ -935,6 +959,7 @@ consider_hibernation(time_t now) { int accounting_enabled = get_options()->AccountingMax != 0; char buf[ISO_TIME_LEN+1]; + hibernate_state_t prev_state = hibernate_state; /* If we're in 'exiting' mode, then we just shut down after the interval * elapses. */ @@ -990,6 +1015,10 @@ consider_hibernation(time_t now) hibernate_end_time_elapsed(now); } } + + /* Dispatch a controller event if the hibernation state changed. */ + if (hibernate_state != prev_state) + on_hibernate_state_change(prev_state); } /** Helper function: called when we get a GETINFO request for an @@ -1007,12 +1036,8 @@ getinfo_helper_accounting(control_connection_t *conn, if (!strcmp(question, "accounting/enabled")) { *answer = tor_strdup(accounting_is_enabled(get_options()) ? "1" : "0"); } else if (!strcmp(question, "accounting/hibernating")) { - if (hibernate_state == HIBERNATE_STATE_DORMANT) - *answer = tor_strdup("hard"); - else if (hibernate_state == HIBERNATE_STATE_LOWBANDWIDTH) - *answer = tor_strdup("soft"); - else - *answer = tor_strdup("awake"); + *answer = tor_strdup(hibernate_state_to_string(hibernate_state)); + tor_strlower(*answer); } else if (!strcmp(question, "accounting/bytes")) { tor_asprintf(answer, U64_FORMAT" "U64_FORMAT, U64_PRINTF_ARG(n_bytes_read_in_interval), @@ -1062,6 +1087,20 @@ getinfo_helper_accounting(control_connection_t *conn, return 0; } +/** + * Helper function: called when the hibernation state changes, and sends a + * SERVER_STATUS event to notify interested controllers of the accounting + * state change. + */ +static void +on_hibernate_state_change(hibernate_state_t prev_state) +{ + (void)prev_state; /* Should we do something with this? */ + control_event_server_status(LOG_NOTICE, + "HIBERNATION_STATUS STATUS=%s", + hibernate_state_to_string(hibernate_state)); +} + #ifdef TOR_UNIT_TESTS /** * Manually change the hibernation state. Private; used only by the unit diff --git a/src/or/main.c b/src/or/main.c index a2cf5b1101..fba9799a60 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -1643,8 +1643,8 @@ rotate_x509_certificate_callback(time_t now, const or_options_t *options) * TLS context. */ log_info(LD_GENERAL,"Rotating tls context."); if (router_initialize_tls_context() < 0) { - log_warn(LD_BUG, "Error reinitializing TLS context"); - tor_assert(0); + log_err(LD_BUG, "Error reinitializing TLS context"); + tor_assert_unreached(); } /* We also make sure to rotate the TLS connections themselves if they've @@ -1917,7 +1917,7 @@ fetch_networkstatus_callback(time_t now, const or_options_t *options) /* How often do we check whether we should download network status * documents? */ - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( now); const int prefer_mirrors = !directory_fetches_from_authorities( get_options()); @@ -2563,9 +2563,7 @@ run_main_loop_once(void) return -1; #endif } else { - if (ERRNO_IS_EINPROGRESS(e)) - log_warn(LD_BUG, - "libevent call returned EINPROGRESS? Please report."); + tor_assert_nonfatal_once(! ERRNO_IS_EINPROGRESS(e)); log_debug(LD_NET,"libevent call interrupted."); /* You can't trust the results of this poll(). Go back to the * top of the big for loop. */ diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index 3967f56edd..51c985e85e 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -819,7 +819,7 @@ update_consensus_networkstatus_downloads(time_t now) { int i; const or_options_t *options = get_options(); - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( now); const int use_multi_conn = networkstatus_consensus_can_use_multiple_directories(options); @@ -875,12 +875,13 @@ update_consensus_networkstatus_downloads(time_t now) resource, DIR_CONN_STATE_CONNECTING); - if (i == usable_consensus_flavor() - && connect_consens_conn_count < consens_conn_count) { + /* If not all connections are "connecting", then some are + * downloading. We want to have at most one downloading at a time. */ + if (connect_consens_conn_count < consens_conn_count) { continue; } - /* Make multiple connections for a bootstrap consensus download */ + /* Make multiple connections for a bootstrap consensus download. */ update_consensus_bootstrap_multiple_downloads(now, options, we_are_bootstrapping); } else { @@ -954,7 +955,7 @@ update_consensus_bootstrap_attempt_downloads( * connections. * Only call when bootstrapping, and when we want to make additional * connections. Only nodes that satisfy - * networkstatus_consensus_can_use_multiple_directories make additonal + * networkstatus_consensus_can_use_multiple_directories make additional * connections. */ static void @@ -969,7 +970,7 @@ update_consensus_bootstrap_multiple_downloads(time_t now, return; } - /* If we've managed to validate a usable consensus, don't make additonal + /* If we've managed to validate a usable consensus, don't make additional * connections. */ if (!we_are_bootstrapping) { return; @@ -1277,7 +1278,7 @@ networkstatus_get_reasonably_live_consensus(time_t now, int flavor) * only using the authorities and fallback directory mirrors to download the * consensus flavour we'll use. */ int -networkstatus_consensus_is_boostrapping(time_t now) +networkstatus_consensus_is_bootstrapping(time_t now) { /* If we don't have a consensus, we must still be bootstrapping */ return !networkstatus_get_reasonably_live_consensus( @@ -1327,7 +1328,7 @@ networkstatus_consensus_can_use_extra_fallbacks(const or_options_t *options) * return value of this function to see if a client could make multiple * bootstrap connections. Use * networkstatus_consensus_can_use_multiple_directories() - * and networkstatus_consensus_is_boostrapping(). */ + * and networkstatus_consensus_is_bootstrapping(). */ int networkstatus_consensus_has_excess_connections(void) { diff --git a/src/or/networkstatus.h b/src/or/networkstatus.h index 9bbb9a389e..f2f8af5c6b 100644 --- a/src/or/networkstatus.h +++ b/src/or/networkstatus.h @@ -70,7 +70,7 @@ MOCK_DECL(networkstatus_t *,networkstatus_get_latest_consensus_by_flavor, networkstatus_t *networkstatus_get_live_consensus(time_t now); networkstatus_t *networkstatus_get_reasonably_live_consensus(time_t now, int flavor); -int networkstatus_consensus_is_boostrapping(time_t now); +int networkstatus_consensus_is_bootstrapping(time_t now); int networkstatus_consensus_can_use_multiple_directories( const or_options_t *options); int networkstatus_consensus_can_use_extra_fallbacks( diff --git a/src/or/onion.c b/src/or/onion.c index d6ef3673dd..4bed7ae226 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -527,7 +527,7 @@ onion_skin_server_handshake(int type, * <b>rend_authenticator_out</b> to the "KH" field that can be used to * establish introduction points at this hop, and return 0. On failure, * return -1, and set *msg_out to an error message if this is worth - * complaining to the usre about. */ + * complaining to the user about. */ int onion_skin_client_handshake(int type, const onion_handshake_state_t *handshake_state, diff --git a/src/or/or.h b/src/or/or.h index 6694bb4ece..86664d470d 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -784,7 +784,7 @@ typedef enum rend_auth_type_t { /** Client-side configuration of authorization for a hidden service. */ typedef struct rend_service_authorization_t { - char descriptor_cookie[REND_DESC_COOKIE_LEN]; + uint8_t descriptor_cookie[REND_DESC_COOKIE_LEN]; char onion_address[REND_SERVICE_ADDRESS_LEN+1]; rend_auth_type_t auth_type; } rend_service_authorization_t; @@ -1294,21 +1294,26 @@ typedef struct connection_t { time_t timestamp_created; /**< When was this connection_t created? */ - /* XXXX_IP6 make this IPv6-capable */ int socket_family; /**< Address family of this connection's socket. Usually - * AF_INET, but it can also be AF_UNIX, or in the future - * AF_INET6 */ - tor_addr_t addr; /**< IP of the other side of the connection; used to - * identify routers, along with port. */ - uint16_t port; /**< If non-zero, port on the other end - * of the connection. */ + * AF_INET, but it can also be AF_UNIX, or AF_INET6 */ + tor_addr_t addr; /**< IP that socket "s" is directly connected to; + * may be the IP address for a proxy or pluggable transport, + * see "address" for the address of the final destination. + */ + uint16_t port; /**< If non-zero, port that socket "s" is directly connected + * to; may be the port for a proxy or pluggable transport, + * see "address" for the port at the final destination. */ uint16_t marked_for_close; /**< Should we close this conn on the next * iteration of the main loop? (If true, holds * the line number where this connection was * marked.) */ const char *marked_for_close_file; /**< For debugging: in which file were * we marked for close? */ - char *address; /**< FQDN (or IP) of the other end. + char *address; /**< FQDN (or IP) and port of the final destination for this + * connection; this is always the remote address, it is + * passed to a proxy or pluggable transport if one in use. + * See "addr" and "port" for the address that socket "s" is + * directly connected to. * strdup into this, because free_connection() frees it. */ /** Another connection that's connected to this one in lieu of a socket. */ struct connection_t *linked_conn; @@ -5034,7 +5039,7 @@ typedef enum { /** Hidden-service side configuration of client authorization. */ typedef struct rend_authorized_client_t { char *client_name; - char descriptor_cookie[REND_DESC_COOKIE_LEN]; + uint8_t descriptor_cookie[REND_DESC_COOKIE_LEN]; crypto_pk_t *client_key; } rend_authorized_client_t; diff --git a/src/or/policies.c b/src/or/policies.c index f9718b6a95..2703d7edef 100644 --- a/src/or/policies.c +++ b/src/or/policies.c @@ -103,7 +103,7 @@ policy_expand_private(smartlist_t **policy) if (tor_addr_parse_mask_ports(private_nets[i], 0, &newpolicy.addr, &newpolicy.maskbits, &port_min, &port_max)<0) { - tor_assert(0); + tor_assert_unreached(); } smartlist_add(tmp, addr_policy_get_canonical_entry(&newpolicy)); } diff --git a/src/or/rendclient.c b/src/or/rendclient.c index 609c45c71d..c119d86adf 100644 --- a/src/or/rendclient.c +++ b/src/or/rendclient.c @@ -1466,12 +1466,10 @@ rend_parse_service_authorization(const or_options_t *options, strmap_t *parsed = strmap_new(); smartlist_t *sl = smartlist_new(); rend_service_authorization_t *auth = NULL; - char descriptor_cookie_tmp[REND_DESC_COOKIE_LEN+2]; - char descriptor_cookie_base64ext[REND_DESC_COOKIE_LEN_BASE64+2+1]; + char *err_msg = NULL; for (line = options->HidServAuth; line; line = line->next) { char *onion_address, *descriptor_cookie; - int auth_type_val = 0; auth = NULL; SMARTLIST_FOREACH(sl, char *, c, tor_free(c);); smartlist_clear(sl); @@ -1500,31 +1498,13 @@ rend_parse_service_authorization(const or_options_t *options, } /* Parse descriptor cookie. */ descriptor_cookie = smartlist_get(sl, 1); - if (strlen(descriptor_cookie) != REND_DESC_COOKIE_LEN_BASE64) { - log_warn(LD_CONFIG, "Authorization cookie has wrong length: '%s'", - descriptor_cookie); + if (rend_auth_decode_cookie(descriptor_cookie, auth->descriptor_cookie, + &auth->auth_type, &err_msg) < 0) { + tor_assert(err_msg); + log_warn(LD_CONFIG, "%s", err_msg); + tor_free(err_msg); goto err; } - /* Add trailing zero bytes (AA) to make base64-decoding happy. */ - tor_snprintf(descriptor_cookie_base64ext, - REND_DESC_COOKIE_LEN_BASE64+2+1, - "%sAA", descriptor_cookie); - if (base64_decode(descriptor_cookie_tmp, sizeof(descriptor_cookie_tmp), - descriptor_cookie_base64ext, - strlen(descriptor_cookie_base64ext)) < 0) { - log_warn(LD_CONFIG, "Decoding authorization cookie failed: '%s'", - descriptor_cookie); - goto err; - } - auth_type_val = (((uint8_t)descriptor_cookie_tmp[16]) >> 4) + 1; - if (auth_type_val < 1 || auth_type_val > 2) { - log_warn(LD_CONFIG, "Authorization cookie has unknown authorization " - "type encoded."); - goto err; - } - auth->auth_type = auth_type_val == 1 ? REND_BASIC_AUTH : REND_STEALTH_AUTH; - memcpy(auth->descriptor_cookie, descriptor_cookie_tmp, - REND_DESC_COOKIE_LEN); if (strmap_get(parsed, auth->onion_address)) { log_warn(LD_CONFIG, "Duplicate authorization for the same hidden " "service."); @@ -1547,8 +1527,6 @@ rend_parse_service_authorization(const or_options_t *options, } else { strmap_free(parsed, rend_service_authorization_strmap_item_free); } - memwipe(descriptor_cookie_tmp, 0, sizeof(descriptor_cookie_tmp)); - memwipe(descriptor_cookie_base64ext, 0, sizeof(descriptor_cookie_base64ext)); return res; } diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c index 438fbc4d9a..56c49fee47 100644 --- a/src/or/rendcommon.c +++ b/src/or/rendcommon.c @@ -211,7 +211,7 @@ rend_encode_v2_intro_points(char **encoded, rend_service_descriptor_t *desc) goto done; } /* Assemble everything for this introduction point. */ - address = tor_dup_addr(&info->addr); + address = tor_addr_to_str_dup(&info->addr); res = tor_snprintf(unenc + unenc_written, unenc_len - unenc_written, "introduction-point %s\n" "ip-address %s\n" @@ -720,6 +720,22 @@ rend_valid_descriptor_id(const char *query) return 0; } +/** Return true iff <b>client_name</b> 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 * <b>circ</b>. Dispatch on rendezvous relay command. */ void @@ -941,3 +957,114 @@ hid_serv_get_responsible_directories(smartlist_t *responsible_dirs, 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; +} + + diff --git a/src/or/rendcommon.h b/src/or/rendcommon.h index d67552e405..88cf512f4a 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, @@ -68,5 +69,13 @@ rend_data_t *rend_data_service_create(const char *onion_address, const char *pk_digest, const uint8_t *cookie, rend_auth_type_t auth_type); + +char *rend_auth_encode_cookie(const uint8_t *cookie_in, + rend_auth_type_t auth_type); +int rend_auth_decode_cookie(const char *cookie_in, + uint8_t *cookie_out, + rend_auth_type_t *auth_type_out, + char **err_msg_out); + #endif diff --git a/src/or/rendmid.c b/src/or/rendmid.c index a33ad92966..ca0ad7b0d4 100644 --- a/src/or/rendmid.c +++ b/src/or/rendmid.c @@ -309,7 +309,7 @@ rend_mid_rendezvous(or_circuit_t *circ, const uint8_t *request, goto err; } - if (request_len != REND_COOKIE_LEN+DH_KEY_LEN+DIGEST_LEN) { + if (request_len < REND_COOKIE_LEN) { log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL, "Rejecting RENDEZVOUS1 cell with bad length (%d) on circuit %u.", (int)request_len, (unsigned)circ->p_circ_id); diff --git a/src/or/rendservice.c b/src/or/rendservice.c index 39e5831589..21ac70a39b 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -183,14 +183,15 @@ num_rend_services(void) } /** Helper: free storage held by a single service authorized client entry. */ -static void +void rend_authorized_client_free(rend_authorized_client_t *client) { if (!client) return; if (client->client_key) crypto_pk_free(client->client_key); - memwipe(client->client_name, 0, strlen(client->client_name)); + if (client->client_name) + memwipe(client->client_name, 0, strlen(client->client_name)); tor_free(client->client_name); memwipe(client->descriptor_cookie, 0, sizeof(client->descriptor_cookie)); tor_free(client); @@ -671,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); @@ -827,14 +818,17 @@ rend_config_services(const or_options_t *options, int validate_only) return 0; } -/** Add the ephemeral service <b>pk</b>/<b>ports</b> if possible, with +/** Add the ephemeral service <b>pk</b>/<b>ports</b> if possible, using + * client authorization <b>auth_type</b> and an optional list of + * rend_authorized_client_t in <b>auth_clients</b>, with * <b>max_streams_per_circuit</b> streams allowed per rendezvous circuit, * and circuit closure on max streams being exceeded set by * <b>max_streams_close_circuit</b>. * - * Regardless of sucess/failure, callers should not touch pk/ports after - * calling this routine, and may assume that correct cleanup has been done - * on failure. + * Ownership of pk, ports, and auth_clients is passed to this routine. + * Regardless of success/failure, callers should not touch these values + * after calling this routine, and may assume that correct cleanup has + * been done on failure. * * Return an appropriate rend_service_add_ephemeral_status_t. */ @@ -843,6 +837,8 @@ rend_service_add_ephemeral(crypto_pk_t *pk, smartlist_t *ports, int max_streams_per_circuit, int max_streams_close_circuit, + rend_auth_type_t auth_type, + smartlist_t *auth_clients, char **service_id_out) { *service_id_out = NULL; @@ -852,7 +848,8 @@ rend_service_add_ephemeral(crypto_pk_t *pk, rend_service_t *s = tor_malloc_zero(sizeof(rend_service_t)); s->directory = NULL; /* This indicates the service is ephemeral. */ s->private_key = pk; - s->auth_type = REND_NO_AUTH; + s->auth_type = auth_type; + s->clients = auth_clients; s->ports = ports; s->intro_period_started = time(NULL); s->n_intro_points_wanted = NUM_INTRO_POINTS_DEFAULT; @@ -868,6 +865,12 @@ rend_service_add_ephemeral(crypto_pk_t *pk, rend_service_free(s); return RSAE_BADVIRTPORT; } + if (s->auth_type != REND_NO_AUTH && + (!s->clients || smartlist_len(s->clients) == 0)) { + log_warn(LD_CONFIG, "At least one authorized client must be specified."); + rend_service_free(s); + return RSAE_BADAUTH; + } /* Enforcing pk/id uniqueness should be done by rend_service_load_keys(), but * it's not, see #14828. @@ -1156,7 +1159,6 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) strmap_t *parsed_clients = strmap_new(); FILE *cfile, *hfile; open_file_t *open_cfile = NULL, *open_hfile = NULL; - char extended_desc_cookie[REND_DESC_COOKIE_LEN+1]; char desc_cook_out[3*REND_DESC_COOKIE_LEN_BASE64+1]; char service_id[16+1]; char buf[1500]; @@ -1208,10 +1210,12 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) memcpy(client->descriptor_cookie, parsed->descriptor_cookie, REND_DESC_COOKIE_LEN); } else { - crypto_rand(client->descriptor_cookie, REND_DESC_COOKIE_LEN); + crypto_rand((char *) client->descriptor_cookie, REND_DESC_COOKIE_LEN); } + /* For compatibility with older tor clients, this does not + * truncate the padding characters, unlike rend_auth_encode_cookie. */ if (base64_encode(desc_cook_out, 3*REND_DESC_COOKIE_LEN_BASE64+1, - client->descriptor_cookie, + (char *) client->descriptor_cookie, REND_DESC_COOKIE_LEN, 0) < 0) { log_warn(LD_BUG, "Could not base64-encode descriptor cookie."); goto err; @@ -1272,6 +1276,8 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) log_warn(LD_BUG, "Could not write client entry."); goto err; } + } else { + strlcpy(service_id, s->service_id, sizeof(service_id)); } if (fputs(buf, cfile) < 0) { @@ -1280,27 +1286,18 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) goto err; } - /* Add line to hostname file. */ - if (s->auth_type == REND_BASIC_AUTH) { - /* Remove == signs (newline has been removed above). */ - desc_cook_out[strlen(desc_cook_out)-2] = '\0'; - tor_snprintf(buf, sizeof(buf),"%s.onion %s # client: %s\n", - s->service_id, desc_cook_out, client->client_name); - } else { - memcpy(extended_desc_cookie, client->descriptor_cookie, - REND_DESC_COOKIE_LEN); - extended_desc_cookie[REND_DESC_COOKIE_LEN] = - ((int)s->auth_type - 1) << 4; - if (base64_encode(desc_cook_out, 3*REND_DESC_COOKIE_LEN_BASE64+1, - extended_desc_cookie, - REND_DESC_COOKIE_LEN+1, 0) < 0) { - log_warn(LD_BUG, "Could not base64-encode descriptor cookie."); - goto err; - } - desc_cook_out[strlen(desc_cook_out)-2] = '\0'; /* Remove A=. */ - tor_snprintf(buf, sizeof(buf),"%s.onion %s # client: %s\n", - service_id, desc_cook_out, client->client_name); + /* Add line to hostname file. This is not the same encoding as in + * client_keys. */ + char *encoded_cookie = rend_auth_encode_cookie(client->descriptor_cookie, + s->auth_type); + if (!encoded_cookie) { + log_warn(LD_BUG, "Could not base64-encode descriptor cookie."); + goto err; } + tor_snprintf(buf, sizeof(buf), "%s.onion %s # client: %s\n", + service_id, encoded_cookie, client->client_name); + memwipe(encoded_cookie, 0, strlen(encoded_cookie)); + tor_free(encoded_cookie); if (fputs(buf, hfile)<0) { log_warn(LD_FS, "Could not append host entry to file: %s", @@ -1332,7 +1329,6 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) memwipe(buf, 0, sizeof(buf)); memwipe(desc_cook_out, 0, sizeof(desc_cook_out)); memwipe(service_id, 0, sizeof(service_id)); - memwipe(extended_desc_cookie, 0, sizeof(extended_desc_cookie)); return r; } diff --git a/src/or/rendservice.h b/src/or/rendservice.h index 101b37e18d..4966cb0302 100644 --- a/src/or/rendservice.h +++ b/src/or/rendservice.h @@ -106,8 +106,11 @@ rend_service_port_config_t *rend_service_parse_port_config(const char *string, char **err_msg_out); void rend_service_port_config_free(rend_service_port_config_t *p); +void rend_authorized_client_free(rend_authorized_client_t *client); + /** Return value from rend_service_add_ephemeral. */ typedef enum { + RSAE_BADAUTH = -5, /**< Invalid auth_type/auth_clients */ RSAE_BADVIRTPORT = -4, /**< Invalid VIRTPORT/TARGET(s) */ RSAE_ADDREXISTS = -3, /**< Onion address collision */ RSAE_BADPRIVKEY = -2, /**< Invalid public key */ @@ -118,6 +121,8 @@ rend_service_add_ephemeral_status_t rend_service_add_ephemeral(crypto_pk_t *pk, smartlist_t *ports, int max_streams_per_circuit, int max_streams_close_circuit, + rend_auth_type_t auth_type, + smartlist_t *auth_clients, char **service_id_out); int rend_service_del_ephemeral(const char *service_id); diff --git a/src/or/rephist.c b/src/or/rephist.c index fe0ca91c25..b94ad29650 100644 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@ -3214,7 +3214,7 @@ rep_hist_free_all(void) rep_hist_desc_stats_term(); total_descriptor_downloads = 0; - tor_assert(rephist_total_alloc == 0); - tor_assert(rephist_total_num == 0); + tor_assert_nonfatal(rephist_total_alloc == 0); + tor_assert_nonfatal_once(rephist_total_num == 0); } diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 1c275a68c3..7f805f15b1 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -4276,7 +4276,7 @@ dir_server_new(int is_authority, return NULL; if (!hostname) - hostname_ = tor_dup_addr(addr); + hostname_ = tor_addr_to_str_dup(addr); else hostname_ = tor_strdup(hostname); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index cec10c8f24..600d55294f 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -5371,6 +5371,7 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) directory_token_t *tok; const char *current_entry = NULL; memarea_t *area = NULL; + char *err_msg = NULL; if (!ckstr || strlen(ckstr) == 0) return -1; tokens = smartlist_new(); @@ -5380,8 +5381,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; - char descriptor_cookie_tmp[REND_DESC_COOKIE_LEN+2]; /* Determine end of string. */ const char *eos = strstr(current_entry, "\nclient-name "); if (!eos) @@ -5410,12 +5409,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. */ @@ -5437,23 +5434,13 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) /* Parse descriptor cookie. */ tok = find_by_keyword(tokens, C_DESCRIPTOR_COOKIE); tor_assert(tok->n_args == 1); - if (strlen(tok->args[0]) != REND_DESC_COOKIE_LEN_BASE64 + 2) { - log_warn(LD_REND, "Descriptor cookie has illegal length: %s", - escaped(tok->args[0])); - goto err; - } - /* The size of descriptor_cookie_tmp needs to be REND_DESC_COOKIE_LEN+2, - * because a base64 encoding of length 24 does not fit into 16 bytes in all - * cases. */ - if (base64_decode(descriptor_cookie_tmp, sizeof(descriptor_cookie_tmp), - tok->args[0], strlen(tok->args[0])) - != REND_DESC_COOKIE_LEN) { - log_warn(LD_REND, "Descriptor cookie contains illegal characters: " - "%s", escaped(tok->args[0])); + if (rend_auth_decode_cookie(tok->args[0], parsed_entry->descriptor_cookie, + NULL, &err_msg) < 0) { + tor_assert(err_msg); + log_warn(LD_REND, "%s", err_msg); + tor_free(err_msg); goto err; } - memcpy(parsed_entry->descriptor_cookie, descriptor_cookie_tmp, - REND_DESC_COOKIE_LEN); } result = strmap_size(parsed_clients); goto done; diff --git a/src/test/include.am b/src/test/include.am index 7d80fdf152..991b24963a 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)\"" \ @@ -86,6 +88,7 @@ src_test_test_SOURCES = \ src/test/test_guardfraction.c \ src/test/test_extorport.c \ src/test/test_hs.c \ + src/test/test_handles.c \ src/test/test_introduce.c \ src/test/test_keypin.c \ src/test/test_link_handshake.c \ @@ -127,6 +130,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 +195,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-memwipe.c b/src/test/test-memwipe.c index 5d4fcec664..5e89534db6 100644 --- a/src/test/test-memwipe.c +++ b/src/test/test-memwipe.c @@ -6,9 +6,6 @@ #include "crypto.h" #include "compat.h" -#undef MIN -#define MIN(a,b) ( ((a)<(b)) ? (a) : (b) ) - static unsigned fill_a_buffer_memset(void) __attribute__((noinline)); static unsigned fill_a_buffer_memwipe(void) __attribute__((noinline)); static unsigned fill_a_buffer_nothing(void) __attribute__((noinline)); diff --git a/src/test/test-timers.c b/src/test/test-timers.c new file mode 100644 index 0000000000..8f5ba7b78a --- /dev/null +++ b/src/test/test-timers.c @@ -0,0 +1,133 @@ +/* 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 +#define N_DISABLE 5 + +static struct timeval fire_at[N_TIMERS] = {{0,0}}; +static int is_disabled[N_TIMERS] = {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_active_timers = 0; +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_active_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; + int ret; + 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]); + timer_schedule(timers[i], &delay); + ++n_active_timers; + } + + /* Disable some; we'll make sure they don't trigger. */ + for (i = 0; i < N_DISABLE; ++i) { + int idx = crypto_rand_int_range(0, N_TIMERS); + if (is_disabled[idx]) + continue; + is_disabled[idx] = 1; + timer_disable(timers[idx]); + --n_active_timers; + } + + event_base_loop(tor_libevent_get_base(), 0); + + int64_t total_difference = 0; + uint64_t total_square_difference = 0; + tor_assert(n_fired == n_active_timers); + for (i = 0; i < N_TIMERS; ++i) { + if (is_disabled[i]) { + tor_assert(fired[i] == 0); + continue; + } + tor_assert(fired[i] == 1); + int64_t diff = difference[i].tv_usec + difference[i].tv_sec * 1000000; + total_difference += diff; + total_square_difference += diff*diff; + } + const int64_t mean_diff = total_difference / n_active_timers; + printf("mean difference: "U64_FORMAT" usec\n", + U64_PRINTF_ARG(mean_diff)); + + const double mean_sq = ((double)total_square_difference)/ n_active_timers; + const double sq_mean = mean_diff * mean_diff; + const double stddev = sqrt(mean_sq - sq_mean); + printf("standard deviation: %lf usec\n", stddev); + +#define MAX_DIFF_USEC (500*1000) +#define MAX_STDDEV_USEC (500*1000) +#define ODD_DIFF_USEC (2000) +#define ODD_STDDEV_USEC (2000) + + if (mean_diff < 0 || mean_diff > MAX_DIFF_USEC || stddev > MAX_STDDEV_USEC) { + printf("Either your system is under ridiculous load, or the " + "timer backend is broken.\n"); + ret = 1; + } else if (mean_diff > ODD_DIFF_USEC || stddev > ODD_STDDEV_USEC) { + printf("Either your system is a bit slow or the " + "timer backend is odd.\n"); + ret = 0; + } else { + printf("Looks good enough.\n"); + ret = 0; + } + + timer_free(NULL); + + for (i = 0; i < N_TIMERS; ++i) { + timer_free(timers[i]); + } + timers_shutdown(); + return ret; +} diff --git a/src/test/test.c b/src/test/test.c index ed167a3e67..3519dcadb0 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -1177,6 +1177,7 @@ extern struct testcase_t util_tests[]; extern struct testcase_t util_format_tests[]; extern struct testcase_t util_process_tests[]; extern struct testcase_t dns_tests[]; +extern struct testcase_t handle_tests[]; struct testgroup_t testgroups[] = { { "", test_array }, @@ -1231,6 +1232,7 @@ struct testgroup_t testgroups[] = { { "util/logging/", logging_tests }, { "util/process/", util_process_tests }, { "util/thread/", thread_tests }, + { "util/handle/", handle_tests }, { "dns/", dns_tests }, END_OF_GROUPS }; diff --git a/src/test/test.h b/src/test/test.h index e618ce1224..153b7cae00 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -73,7 +73,7 @@ {print_ = (I64_PRINTF_TYPE) value_;}, {}, TT_EXIT_TEST_FUNCTION) const char *get_fname(const char *name); -crypto_pk_t *pk_generate(int idx); +struct crypto_pk_t *pk_generate(int idx); #define US2_CONCAT_2__(a, b) a ## __ ## b #define US_CONCAT_2__(a, b) a ## _ ## b diff --git a/src/test/test_bt.sh b/src/test/test_bt.sh index 033acac955..83fa3ff24b 100755 --- a/src/test/test_bt.sh +++ b/src/test/test_bt.sh @@ -4,7 +4,7 @@ exitcode=0 "${builddir:-.}/src/test/test-bt-cl" backtraces || exit $? -"${builddir:-.}/src/test/test-bt-cl" assert | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" -"${builddir:-.}/src/test/test-bt-cl" crash | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" +"${builddir:-.}/src/test/test-bt-cl" assert 2>&1 | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" +"${builddir:-.}/src/test/test-bt-cl" crash 2>&1 | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" exit ${exitcode} diff --git a/src/test/test_connection.c b/src/test/test_connection.c index 15ae973f00..6f7aef879c 100644 --- a/src/test/test_connection.c +++ b/src/test/test_connection.c @@ -705,7 +705,7 @@ test_conn_download_status(void *arg) /* now try closing the one that isn't downloading: * these tests won't work unless tor thinks it is bootstrapping */ - tt_assert(networkstatus_consensus_is_boostrapping(time(NULL))); + tt_assert(networkstatus_consensus_is_bootstrapping(time(NULL))); tt_assert(connection_dir_count_by_purpose_and_resource( TEST_CONN_RSRC_PURPOSE, diff --git a/src/test/test_controller.c b/src/test/test_controller.c index 7f9db4312f..b276e06787 100644 --- a/src/test/test_controller.c +++ b/src/test/test_controller.c @@ -154,10 +154,61 @@ test_rend_service_parse_port_config(void *arg) tor_free(err_msg); } +static void +test_add_onion_helper_clientauth(void *arg) +{ + rend_authorized_client_t *client = NULL; + char *err_msg = NULL; + int created = 0; + + (void)arg; + + /* Test "ClientName" only. */ + client = add_onion_helper_clientauth("alice", &created, &err_msg); + tt_assert(client); + tt_assert(created); + tt_assert(!err_msg); + rend_authorized_client_free(client); + + /* Test "ClientName:Blob" */ + client = add_onion_helper_clientauth("alice:475hGBHPlq7Mc0cRZitK/B", + &created, &err_msg); + tt_assert(client); + tt_assert(!created); + tt_assert(!err_msg); + rend_authorized_client_free(client); + + /* Test invalid client names */ + client = add_onion_helper_clientauth("no*asterisks*allowed", &created, + &err_msg); + tt_assert(!client); + tt_assert(err_msg); + tor_free(err_msg); + + /* Test invalid auth cookie */ + client = add_onion_helper_clientauth("alice:12345", &created, &err_msg); + tt_assert(!client); + tt_assert(err_msg); + tor_free(err_msg); + + /* Test invalid syntax */ + client = add_onion_helper_clientauth(":475hGBHPlq7Mc0cRZitK/B", &created, + &err_msg); + tt_assert(!client); + tt_assert(err_msg); + tor_free(err_msg); + + done: + rend_authorized_client_free(client); + tor_free(err_msg); +} + struct testcase_t controller_tests[] = { { "add_onion_helper_keyarg", test_add_onion_helper_keyarg, 0, NULL, NULL }, { "rend_service_parse_port_config", test_rend_service_parse_port_config, 0, NULL, NULL }, + { "add_onion_helper_clientauth", test_add_onion_helper_clientauth, 0, NULL, + NULL }, END_OF_TESTCASES }; diff --git a/src/test/test_handles.c b/src/test/test_handles.c new file mode 100644 index 0000000000..8aaae13845 --- /dev/null +++ b/src/test/test_handles.c @@ -0,0 +1,95 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" +#include "test.h" + +#include "util.h" +#include "handles.h" + +typedef struct demo_t { + HANDLE_ENTRY(demo, demo_t); + int val; +} demo_t; + +HANDLE_DECL(demo, demo_t, static); +HANDLE_IMPL(demo, demo_t, static); + +static demo_t * +demo_new(int val) +{ + demo_t *d = tor_malloc_zero(sizeof(demo_t)); + d->val = val; + return d; +} + +static void +demo_free(demo_t *d) +{ + if (d == NULL) + return; + demo_handles_clear(d); + tor_free(d); +} + +static void +test_handle_basic(void *arg) +{ + (void) arg; + demo_t *d1 = NULL, *d2 = NULL; + demo_handle_t *wr1 = NULL, *wr2 = NULL, *wr3 = NULL, *wr4 = NULL; + + d1 = demo_new(9000); + d2 = demo_new(9009); + + wr1 = demo_handle_new(d1); + wr2 = demo_handle_new(d1); + wr3 = demo_handle_new(d1); + wr4 = demo_handle_new(d2); + + tt_assert(wr1); + tt_assert(wr2); + tt_assert(wr3); + tt_assert(wr4); + + tt_ptr_op(demo_handle_get(wr1), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr2), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr3), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_handle_free(wr1); + wr1 = NULL; + tt_ptr_op(demo_handle_get(wr2), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr3), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_free(d1); + d1 = NULL; + tt_ptr_op(demo_handle_get(wr2), OP_EQ, NULL); + tt_ptr_op(demo_handle_get(wr3), OP_EQ, NULL); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_handle_free(wr2); + wr2 = NULL; + tt_ptr_op(demo_handle_get(wr3), OP_EQ, NULL); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_handle_free(wr3); + wr3 = NULL; + done: + demo_handle_free(wr1); + demo_handle_free(wr2); + demo_handle_free(wr3); + demo_handle_free(wr4); + demo_free(d1); + demo_free(d2); +} + +#define HANDLE_TEST(name, flags) \ + { #name, test_handle_ ##name, (flags), NULL, NULL } + +struct testcase_t handle_tests[] = { + HANDLE_TEST(basic, 0), + END_OF_TESTCASES +}; + diff --git a/src/test/test_hs.c b/src/test/test_hs.c index 49939a53cf..1daa1552e9 100644 --- a/src/test/test_hs.c +++ b/src/test/test_hs.c @@ -435,6 +435,67 @@ test_hs_rend_data(void *arg) rend_data_free(client_dup); } +/* Test encoding and decoding service authorization cookies */ +static void +test_hs_auth_cookies(void *arg) +{ +#define TEST_COOKIE_RAW ((const uint8_t *) "abcdefghijklmnop") +#define TEST_COOKIE_ENCODED "YWJjZGVmZ2hpamtsbW5vcA" +#define TEST_COOKIE_ENCODED_STEALTH "YWJjZGVmZ2hpamtsbW5vcB" +#define TEST_COOKIE_ENCODED_INVALID "YWJjZGVmZ2hpamtsbW5vcD" + + char *encoded_cookie; + uint8_t raw_cookie[REND_DESC_COOKIE_LEN]; + rend_auth_type_t auth_type; + char *err_msg; + int re; + + (void)arg; + + /* Test that encoding gives the expected result */ + encoded_cookie = rend_auth_encode_cookie(TEST_COOKIE_RAW, REND_BASIC_AUTH); + tt_str_op(encoded_cookie, OP_EQ, TEST_COOKIE_ENCODED); + tor_free(encoded_cookie); + + encoded_cookie = rend_auth_encode_cookie(TEST_COOKIE_RAW, REND_STEALTH_AUTH); + tt_str_op(encoded_cookie, OP_EQ, TEST_COOKIE_ENCODED_STEALTH); + tor_free(encoded_cookie); + + /* Decoding should give the original value */ + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED, raw_cookie, &auth_type, + &err_msg); + tt_assert(!re); + tt_assert(!err_msg); + tt_mem_op(raw_cookie, OP_EQ, TEST_COOKIE_RAW, REND_DESC_COOKIE_LEN); + tt_int_op(auth_type, OP_EQ, REND_BASIC_AUTH); + memset(raw_cookie, 0, sizeof(raw_cookie)); + + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED_STEALTH, raw_cookie, + &auth_type, &err_msg); + tt_assert(!re); + tt_assert(!err_msg); + tt_mem_op(raw_cookie, OP_EQ, TEST_COOKIE_RAW, REND_DESC_COOKIE_LEN); + tt_int_op(auth_type, OP_EQ, REND_STEALTH_AUTH); + memset(raw_cookie, 0, sizeof(raw_cookie)); + + /* Decoding with padding characters should also work */ + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED "==", raw_cookie, NULL, + &err_msg); + tt_assert(!re); + tt_assert(!err_msg); + tt_mem_op(raw_cookie, OP_EQ, TEST_COOKIE_RAW, REND_DESC_COOKIE_LEN); + + /* Decoding with an unknown type should fail */ + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED_INVALID, raw_cookie, + &auth_type, &err_msg); + tt_int_op(re, OP_LT, 0); + tt_assert(err_msg); + tor_free(err_msg); + + done: + return; +} + struct testcase_t hs_tests[] = { { "hs_rend_data", test_hs_rend_data, TT_FORK, NULL, NULL }, @@ -445,6 +506,8 @@ struct testcase_t hs_tests[] = { { "pick_bad_tor2web_rendezvous_node", test_pick_bad_tor2web_rendezvous_node, TT_FORK, NULL, NULL }, + { "hs_auth_cookies", test_hs_auth_cookies, TT_FORK, + NULL, NULL }, END_OF_TESTCASES }; diff --git a/src/test/test_options.c b/src/test/test_options.c index 4f24757a85..20e8dd563a 100644 --- a/src/test/test_options.c +++ b/src/test/test_options.c @@ -513,8 +513,9 @@ test_options_validate__nickname(void *ignored) ret = options_validate(tdata->old_opt, tdata->opt, tdata->def_opt, 0, &msg); tt_int_op(ret, OP_EQ, -1); tt_str_op(msg, OP_EQ, - "Nickname 'ThisNickNameIsABitTooLong' is wrong length or" - " contains illegal characters."); + "Nickname 'ThisNickNameIsABitTooLong', nicknames must be between " + "1 and 19 characters inclusive, and must contain only the " + "characters [a-zA-Z0-9]."); tor_free(msg); free_options_test_data(tdata); diff --git a/src/win32/orconfig.h b/src/win32/orconfig.h index 67d023dd8d..9469245ba7 100644 --- a/src/win32/orconfig.h +++ b/src/win32/orconfig.h @@ -229,7 +229,7 @@ #define USING_TWOS_COMPLEMENT /* Version number of package */ -#define VERSION "0.2.8.2-alpha-dev" +#define VERSION "0.2.9.0-alpha-dev" |