- tor-commits - lists.torproject.org

[obfsproxy/master] Switch from C-library assert to an obfs_assert/abort that go through the logging system
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 13e30cbac02e24cee9615e35d11fc71ab59fb8d1 Author: Zack Weinberg <zackw(a)panix.com> Date: Mon Jul 18 14:42:19 2011 -0700 Switch from C-library assert to an obfs_assert/abort that go through the logging system --- src/crypt.c | 5 +-- src/network.c | 19 ++++++------- src/protocol.c | 34 ++++++++++++------------ src/protocols/dummy.c | 1 - src/protocols/obfs2.c | 3 +- src/sha256.c | 4 +- src/socks.c | 15 +++++------ src/util.c | 66 ++++++++++++++++++++++++++++++++---------------- src/util.h | 20 +++++++++++++++ 9 files changed, 102 insertions(+), 65 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index 722fc00..9984e24 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -6,7 +6,6 @@ #include "crypt.h" #include "util.h" -#include <assert.h> #include <fcntl.h> #include <limits.h> #include <stdlib.h> @@ -160,7 +159,7 @@ crypt_new(const uchar *key, size_t keylen) { crypt_t *k; - assert(keylen == AES_BLOCK_SIZE); + obfs_assert(keylen == AES_BLOCK_SIZE); k = xzalloc(sizeof(crypt_t)); AES_set_encrypt_key(key, AES_BLOCK_SIZE * CHAR_BIT, &k->key); @@ -173,7 +172,7 @@ crypt_new(const uchar *key, size_t keylen) void crypt_set_iv(crypt_t *key, const uchar *iv, size_t ivlen) { - assert(ivlen == sizeof(key->ivec)); + obfs_assert(ivlen == sizeof(key->ivec)); memcpy(key->ivec, iv, ivlen); } diff --git a/src/network.c b/src/network.c index fb770c9..fcbb45c 100644 --- a/src/network.c +++ b/src/network.c @@ -10,7 +10,6 @@ #include "socks.h" #include "protocol.h" -#include <assert.h> #include <errno.h> #include <stdlib.h> #include <string.h> @@ -96,7 +95,7 @@ close_all_connections(void) conn_t *conn = DOWNCAST(conn_t, dll_node, conn_list.head); conn_free(conn); /* removes it */ } - assert(!n_connections); + obfs_assert(!n_connections); } /** This function spawns a listener configured according to the @@ -226,7 +225,7 @@ simple_listener_cb(struct evconnlistener *evcl, bufferevent_setcb(conn->input, plaintext_read_cb, NULL, input_event_cb, conn); } else { - assert(conn->mode == LSN_SOCKS_CLIENT); + obfs_assert(conn->mode == LSN_SOCKS_CLIENT); bufferevent_setcb(conn->input, socks_read_cb, NULL, input_event_cb, conn); } @@ -303,7 +302,7 @@ conn_free(conn_t *conn) memset(conn, 0x99, sizeof(conn_t)); free(conn); - assert(n_connections>=0); + obfs_assert(n_connections>=0); log_debug("Connection destroyed. " "We currently have %d connections!", n_connections); @@ -336,19 +335,19 @@ socks_read_cb(struct bufferevent *bev, void *arg) conn_t *conn = arg; //struct bufferevent *other; enum socks_ret socks_ret; - assert(bev == conn->input); /* socks must be on the initial bufferevent */ + obfs_assert(bev == conn->input); /* socks must be on the initial bufferevent */ do { enum socks_status_t status = socks_state_get_status(conn->socks_state); if (status == ST_SENT_REPLY) { /* We shouldn't be here. */ - assert(0); + obfs_abort(); } else if (status == ST_HAVE_ADDR) { int af, r, port; const char *addr=NULL; r = socks_state_get_address(conn->socks_state, &af, &addr, &port); - assert(r==0); + obfs_assert(r==0); r = bufferevent_socket_connect_hostname(conn->output, get_evdns_base(), af, addr, port); @@ -461,7 +460,7 @@ static void input_event_cb(struct bufferevent *bev, short what, void *arg) { conn_t *conn = arg; - assert(bev == conn->input); + obfs_assert(bev == conn->input); if (what & (BEV_EVENT_EOF|BEV_EVENT_ERROR)) { log_warn("Got error: %s", @@ -478,7 +477,7 @@ static void output_event_cb(struct bufferevent *bev, short what, void *arg) { conn_t *conn = arg; - assert(bev == conn->output); + obfs_assert(bev == conn->output); /** If we got the BEV_EVENT_ERROR flag *AND* we are in socks mode @@ -532,7 +531,7 @@ output_event_cb(struct bufferevent *bev, short what, void *arg) struct sockaddr_storage ss; struct sockaddr *sa = (struct sockaddr*)&ss; socklen_t slen = sizeof(&ss); - assert(conn->socks_state); + obfs_assert(conn->socks_state); if (getpeername(bufferevent_getfd(bev), sa, &slen) == 0) { /* Figure out where we actually connected to so that we can tell the * socks client */ diff --git a/src/protocol.c b/src/protocol.c index 9aa1f8b..4473a94 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -5,8 +5,8 @@ #include "protocol.h" #include "protocols/obfs2.h" #include "protocols/dummy.h" +#include "util.h" -#include <assert.h> #include <stdlib.h> #include <string.h> @@ -50,7 +50,7 @@ proto_params_init(int n_options, const char *const *options) void proto_params_free(protocol_params_t *params) { - assert(params); + obfs_assert(params); if (params->target_address) free(params->target_address); @@ -70,9 +70,9 @@ proto_params_free(protocol_params_t *params) struct protocol_t * proto_create(protocol_params_t *params) { - assert(params); - assert(params->vtable); - assert(params->vtable->create); + obfs_assert(params); + obfs_assert(params->vtable); + obfs_assert(params->vtable->create); return params->vtable->create(params); } @@ -82,9 +82,9 @@ proto_create(protocol_params_t *params) */ int proto_handshake(struct protocol_t *proto, void *buf) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->handshake); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->handshake); return proto->vtable->handshake(proto, buf); } @@ -93,9 +93,9 @@ proto_handshake(struct protocol_t *proto, void *buf) { */ int proto_send(struct protocol_t *proto, void *source, void *dest) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->send); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->send); return proto->vtable->send(proto, source, dest); } @@ -104,9 +104,9 @@ proto_send(struct protocol_t *proto, void *source, void *dest) { */ enum recv_ret proto_recv(struct protocol_t *proto, void *source, void *dest) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->recv); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->recv); return proto->vtable->recv(proto, source, dest); } @@ -116,8 +116,8 @@ proto_recv(struct protocol_t *proto, void *source, void *dest) { */ void proto_destroy(struct protocol_t *proto) { - assert(proto); - assert(proto->vtable); - assert(proto->vtable->destroy); + obfs_assert(proto); + obfs_assert(proto->vtable); + obfs_assert(proto->vtable->destroy); proto->vtable->destroy(proto); } diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index 61cdf2b..b1493ce 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -6,7 +6,6 @@ #include "../protocol.h" #include "../util.h" -#include <assert.h> #include <stdlib.h> #include <string.h> diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index c42d1c4..5acd09e 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -7,7 +7,6 @@ #include "../util.h" -#include <assert.h> #include <stdlib.h> #include <string.h> @@ -322,7 +321,7 @@ obfs2_handshake(struct protocol_t *s, struct evbuffer *buf) SEED | E_PAD_KEY( UINT32(MAGIC_VALUE) | UINT32(PADLEN) | WR(PADLEN) ) */ - assert(sizeof(magic) == 4); + obfs_assert(sizeof(magic) == 4); /* generate padlen */ if (random_bytes((uchar*)&plength, 4) < 0) diff --git a/src/sha256.c b/src/sha256.c index ff2cf21..d303f5f 100644 --- a/src/sha256.c +++ b/src/sha256.c @@ -5,7 +5,7 @@ have a SHA256. */ #include "sha256.h" -#include <assert.h> +#include "util.h" #include <string.h> #include <arpa/inet.h> /* for htonl/ntohl */ @@ -23,7 +23,7 @@ get_uint32(const void *ptr) memcpy(&val, ptr, 4); return val; } -#define LTC_ARGCHK(x) assert((x)) +#define LTC_ARGCHK(x) obfs_assert(x) #define CRYPT_OK 0 #define CRYPT_NOP -1 diff --git a/src/socks.c b/src/socks.c index b67455f..6bd708f 100644 --- a/src/socks.c +++ b/src/socks.c @@ -7,7 +7,6 @@ #include "util.h" -#include <assert.h> #include <errno.h> #include <stdlib.h> #include <string.h> @@ -189,19 +188,19 @@ socks5_handle_request(struct evbuffer *source, struct parsereq *parsereq) goto err; if (evbuffer_remove(source, destaddr, addrlen) != addrlen) - assert(0); + obfs_abort(); if (evbuffer_remove(source, (char *)&destport, 2) != 2) - assert(0); + obfs_abort(); destaddr[addrlen] = '\0'; if (af == AF_UNSPEC) { - assert(addrlen < sizeof(parsereq->addr)); + obfs_assert(addrlen < sizeof(parsereq->addr)); memcpy(parsereq->addr, destaddr, addrlen+1); } else { char a[16]; - assert(addrlen <= 16); + obfs_assert(addrlen <= 16); memcpy(a, destaddr, addrlen); if (evutil_inet_ntop(af, destaddr, parsereq->addr, sizeof(parsereq->addr)) == NULL) @@ -331,7 +330,7 @@ socks5_handle_negotiation(struct evbuffer *source, } if (evbuffer_remove(source, methods, nmethods) < 0) - assert(0); + obfs_abort(); for (found_noauth=0, i=0; i<nmethods ; i++) { if (methods[i] == SOCKS5_METHOD_NOAUTH) { @@ -477,7 +476,7 @@ handle_socks(struct evbuffer *source, struct evbuffer *dest, } /* ST_SENT_REPLY connections shouldn't be here! */ - assert(socks_state->state != ST_SENT_REPLY && + obfs_assert(socks_state->state != ST_SENT_REPLY && socks_state->state != ST_HAVE_ADDR); if (socks_state->version == 0) { @@ -527,7 +526,7 @@ handle_socks(struct evbuffer *source, struct evbuffer *dest, return SOCKS_CMD_NOT_CONNECT; } else if (r == SOCKS_BROKEN) goto broken; - assert(0); + obfs_abort(); } break; default: diff --git a/src/util.c b/src/util.c index ce25375..231c3a8 100644 --- a/src/util.c +++ b/src/util.c @@ -4,7 +4,6 @@ #include "util.h" -#include <assert.h> #include <errno.h> #include <fcntl.h> #include <limits.h> @@ -28,8 +27,7 @@ static void ATTR_NORETURN die_oom(void) { - log_warn("Memory allocation failed: %s",strerror(errno)); - exit(1); + log_error("Memory allocation failed: %s",strerror(errno)); } void * @@ -37,7 +35,7 @@ xmalloc(size_t size) { void *result; - assert(size < SIZE_T_CEILING); + obfs_assert(size < SIZE_T_CEILING); /* Some malloc() implementations return NULL when the input argument is zero. We don't bother detecting whether the implementation we're @@ -57,7 +55,7 @@ void * xrealloc(void *ptr, size_t size) { void *result; - assert (size < SIZE_T_CEILING); + obfs_assert (size < SIZE_T_CEILING); if (size == 0) size = 1; @@ -217,8 +215,8 @@ obfs_vsnprintf(char *str, size_t size, const char *format, va_list args) static void dll_insert_after(dll_t *list, dll_node_t *node, dll_node_t *new_node) { - assert(node); - assert(new_node); + obfs_assert(node); + obfs_assert(new_node); if (!list) return; @@ -238,8 +236,8 @@ dll_insert_after(dll_t *list, dll_node_t *node, dll_node_t *new_node) static void dll_insert_before(dll_t *list, dll_node_t *node, dll_node_t *new_node) { - assert(node); - assert(new_node); + obfs_assert(node); + obfs_assert(new_node); if (!list) return; @@ -266,7 +264,7 @@ dll_init(dll_t *list) static void dll_insert_beginning(dll_t *list, dll_node_t *node) { - assert(node); + obfs_assert(node); if (!list) return; @@ -288,8 +286,8 @@ dll_insert_beginning(dll_t *list, dll_node_t *node) int dll_append(dll_t *list, dll_node_t *node) { - assert(list); - assert(node); + obfs_assert(list); + obfs_assert(node); if (!list->tail) dll_insert_beginning(list, node); @@ -306,7 +304,7 @@ dll_append(dll_t *list, dll_node_t *node) void dll_remove(dll_t *list, dll_node_t *node) { - assert(node); + obfs_assert(node); if (!list) return; @@ -326,6 +324,10 @@ dll_remove(dll_t *list, dll_node_t *node) off tor. It's basicaly a stripped down version of tor's logging system. Thank you tor. */ +/* Note: obfs_assert and obfs_abort cannot be used anywhere in the + logging system, as they will recurse into the logging system and + cause an infinite loop. We use plain old abort(3) instead. */ + /* Size of maximum log entry, including newline and NULL byte. */ #define MAX_LOG_ENTRY 1024 /* String to append when a log entry doesn't fit in MAX_LOG_ENTRY. */ @@ -335,6 +337,7 @@ dll_remove(dll_t *list, dll_node_t *node) /** Logging severities */ +#define LOG_SEV_ERR 4 #define LOG_SEV_WARN 3 #define LOG_SEV_INFO 2 #define LOG_SEV_DEBUG 1 @@ -351,11 +354,12 @@ static const char * sev_to_string(int severity) { switch (severity) { + case LOG_SEV_ERR: return "error"; case LOG_SEV_WARN: return "warn"; case LOG_SEV_INFO: return "info"; case LOG_SEV_DEBUG: return "debug"; default: - assert(0); return "UNKNOWN"; + abort(); } } @@ -364,6 +368,8 @@ sev_to_string(int severity) static int string_to_sev(const char *string) { + if (!strcasecmp(string, "error")) + return LOG_SEV_ERR; if (!strcasecmp(string, "warn")) return LOG_SEV_WARN; else if (!strcasecmp(string, "info")) @@ -381,7 +387,8 @@ string_to_sev(const char *string) static int sev_is_valid(int severity) { - return (severity == LOG_SEV_WARN || + return (severity == LOG_SEV_ERR || + severity == LOG_SEV_WARN || severity == LOG_SEV_INFO || severity == LOG_SEV_DEBUG); } @@ -473,7 +480,8 @@ log_set_min_severity(const char* sev_string) static void logv(int severity, const char *format, va_list ap) { - assert(sev_is_valid(severity)); + if (!sev_is_valid(severity)) + abort(); if (logging_method == LOG_METHOD_NULL) return; @@ -500,7 +508,8 @@ logv(int severity, const char *format, va_list ap) size_t offset = buflen-TRUNCATED_STR_LEN; r = obfs_snprintf(buf+offset, TRUNCATED_STR_LEN+1, "%s", TRUNCATED_STR); - if (r < 0) assert(0); + if (r < 0) + abort(); } n = buflen; } else @@ -512,24 +521,26 @@ logv(int severity, const char *format, va_list ap) if (logging_method == LOG_METHOD_STDOUT) fprintf(stdout, "%s", buf); else if (logging_method == LOG_METHOD_FILE) { - assert(logging_logfile); + if (!logging_logfile) + abort(); if (write(logging_logfile, buf, strlen(buf)) < 0) - printf("%s(): Terrible write() error!!!\n", __func__); + abort(); } else - assert(0); + abort(); } /**** Public logging API. ****/ void -log_info(const char *format, ...) +log_error(const char *format, ...) { va_list ap; va_start(ap,format); - logv(LOG_SEV_INFO, format, ap); + logv(LOG_SEV_ERR, format, ap); va_end(ap); + exit(1); } void @@ -544,6 +555,17 @@ log_warn(const char *format, ...) } void +log_info(const char *format, ...) +{ + va_list ap; + va_start(ap,format); + + logv(LOG_SEV_INFO, format, ap); + + va_end(ap); +} + +void log_debug(const char *format, ...) { va_list ap; diff --git a/src/util.h b/src/util.h index 0693930..8e5dd77 100644 --- a/src/util.h +++ b/src/util.h @@ -98,6 +98,10 @@ void close_obfsproxy_logfile(void); /** The actual log-emitting functions */ +/** Fatal errors: the program cannot continue and will exit. */ +void log_error(const char *format, ...) + ATTR_PRINTF_1 ATTR_NORETURN; + /** Warn-level severity: for messages that only appear when something has gone wrong. */ void log_warn(const char *format, ...) @@ -113,4 +117,20 @@ void log_info(const char *format, ...) void log_debug(const char *format, ...) ATTR_PRINTF_1; +/** Assertion checking. We don't ever compile assertions out, and we + want precise control over the error messages, so we use our own + assertion macros. */ +#define obfs_assert(expr) \ + do { \ + if (!(expr)) \ + log_error("assertion failure at %s:%d: %s", \ + __FILE__, __LINE__, #expr); \ + } while (0) + +#define obfs_abort() \ + do { \ + log_error("aborted at %s:%d", __FILE__, __LINE__); \ + } while (0) + + #endif

1 0

[obfsproxy/master] Merge branch 'master' of git://git.torproject.org/obfsproxy
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit ab1b016d8a6ca5c3c7c2b79bd915eb2d02859d47 Merge: a3e63ea 17e8cb0 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 09:57:38 2011 -0700 Merge branch 'master' of git://git.torproject.org/obfsproxy

1 0

[obfsproxy/master] Refactor crypt digest logic to reduce code duplication and overhead. Fix memory leaks in unittest_crypt.c and unittest.c.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit fc56b8b449d6be99c47447eea1060e8c2b898dde Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 11:40:20 2011 -0700 Refactor crypt digest logic to reduce code duplication and overhead. Fix memory leaks in unittest_crypt.c and unittest.c. --- src/crypt.c | 55 ++++++++------------------ src/test/unittest.c | 5 ++- src/test/unittest_crypt.c | 96 ++++++++++++++++++++------------------------ 3 files changed, 65 insertions(+), 91 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index e338214..9019fc9 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -70,7 +70,13 @@ cleanup_crypto(void) Digests ===== */ -#ifdef USE_OPENSSL_SHA256 +#ifndef USE_OPENSSL_SHA256 +#define SHA256_CTX sha256_state +#define SHA256_Init(ctx) sha256_init(ctx) +#define SHA256_Update(ctx, buf, len) sha256_process(ctx, buf, len) +#define SHA256_Final(buf, ctx) sha256_done(ctx, buf) +#endif + struct digest_t { SHA256_CTX ctx; }; @@ -102,44 +108,17 @@ digest_update(digest_t *d, const uchar *buf, size_t len) size_t digest_getdigest(digest_t *d, uchar *buf, size_t len) { - uchar tmp[SHA256_LENGTH]; - int n = 32; - SHA256_Final(tmp, &d->ctx); - if (len < 32) - n = len; - memcpy(buf, tmp, n); - memset(tmp, 0, sizeof(tmp)); - return n; -} -#else -struct digest_t { - sha256_state ctx; -}; -digest_t * -digest_new(void) -{ - digest_t *d = xmalloc(sizeof(digest_t)); - sha256_init(&d->ctx); - return d; -} -void -digest_update(digest_t *d, const uchar *buf, size_t len) -{ - sha256_process(&d->ctx, buf, len); -} -size_t -digest_getdigest(digest_t *d, uchar *buf, size_t len) -{ - uchar tmp[SHA256_LENGTH]; - int n = 32; - sha256_done(&d->ctx, tmp); - if (len < 32) - n = len; - memcpy(buf, tmp, n); - memset(tmp, 0, sizeof(tmp)); - return n; + if (len >= SHA256_LENGTH) { + SHA256_Final(buf, &d->ctx); + return SHA256_LENGTH; + } else { + uchar tmp[SHA256_LENGTH]; + SHA256_Final(tmp, &d->ctx); + memcpy(buf, tmp, len); + memset(tmp, 0, SHA256_LENGTH); + return len; + } } -#endif void digest_free(digest_t *d) diff --git a/src/test/unittest.c b/src/test/unittest.c index 8974c87..f872550 100644 --- a/src/test/unittest.c +++ b/src/test/unittest.c @@ -21,6 +21,9 @@ struct testgroup_t groups[] = { int main(int argc, const char **argv) { + int rv; initialize_crypto(); - return tinytest_main(argc, argv, groups); + rv = tinytest_main(argc, argv, groups); + cleanup_crypto(); + return rv; } diff --git a/src/test/unittest_crypt.c b/src/test/unittest_crypt.c index aef4ead..112da20 100644 --- a/src/test/unittest_crypt.c +++ b/src/test/unittest_crypt.c @@ -12,63 +12,55 @@ static void test_crypt_hashvec(void *data) { + struct testvec + { + const char *input; + const char *output; + }; + static const struct testvec testvecs[] = { + /* All test vectors taken from http://csrc.nist.gov/groups/STM/cavp/#03 + Note: code below relies on there being no NUL bytes in any input. */ + /* 0 bits */ + { "", + "\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8\x99\x6f\xb9\x24" + "\x27\xae\x41\xe4\x64\x9b\x93\x4c\xa4\x95\x99\x1b\x78\x52\xb8\x55" }, + /* 256 bits */ + { "\x8c\xf5\x3d\x90\x07\x7d\xf9\xa0\x43\xbf\x8d\x10\xb4\x70\xb1\x44" + "\x78\x44\x11\xc9\x3a\x4d\x50\x45\x56\x83\x4d\xae\x3e\xa4\xa5\xbb", + "\x56\x05\x9e\x8c\xb3\xc2\x97\x8b\x19\x82\x08\xbf\x5c\xa1\xe1\xea" + "\x56\x59\xb7\x37\xa5\x06\x32\x4b\x7c\xec\x75\xb5\xeb\xaf\x05\x7d" }, + /* 1304 bits */ + { "\xeb\xac\xcc\x34\xd6\xd6\xd3\xd2\x1e\xd0\xad\x2b\xa7\xc0\x7c\x21" + "\xd2\x53\xc4\x81\x4f\x4a\xd8\x9d\x32\x36\x92\x37\x49\x7f\x47\xa1" + "\xad\xab\xfa\x23\x98\xdd\xd0\x9d\x76\x9c\xc4\x6d\x3f\xd6\x9c\x93" + "\x03\x25\x1c\x13\xc7\x50\x79\x9b\x8f\x15\x11\x66\xbc\x26\x58\x60" + "\x98\x71\x16\x8b\x30\xa4\xd0\xa1\x62\xf1\x83\xfb\x36\x0f\x99\xb1" + "\x72\x81\x15\x03\x68\x1a\x11\xf8\x13\xc1\x6a\x44\x62\x72\xba\x6f" + "\xd4\x85\x86\x34\x45\x33\xb9\x28\x08\x56\x51\x9c\x35\x70\x59\xc3" + "\x44\xef\x17\x18\xdb\xaf\x86\xfa\xe5\xc1\x07\x99\xe4\x6b\x53\x16" + "\x88\x6f\xb4\xe6\x80\x90\x75\x78\x90\x53\x96\x17\xe4\x03\xc5\x11" + "\xa4\xf7\x8a\x19\xc8\x18\xc2\xea\x2e\x9d\x4e\x2d\xe9\x19\x0c\x9d" + "\xdd\xb8\x06", + "\xc9\x07\x18\x04\x43\xde\xe3\xcb\xcc\xb4\xc3\x13\x28\xe6\x25\x15" + "\x85\x27\xa5\x93\xb8\x78\xde\x1b\x8e\x4b\xa3\x7f\x1d\x69\xfb\x66" }, + { NULL, NULL } + }; + digest_t *d; uchar output[32]; - - /* First SHA256 test vector: - Test for '\x00' */ - d = digest_new(); - digest_update(d, (unsigned char*)"", 0); - digest_getdigest(d, output, 32); - tt_mem_op(output, ==, - "\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8" - "\x99\x6f\xb9\x24\x27\xae\x41\xe4\x64\x9b\x93\x4c" - "\xa4\x95\x99\x1b\x78\x52\xb8\x55", 32); - - /* Second SHA256 test vector: - Test for the 256-bit entry of: - http://csrc.nist.gov/groups/STM/cavp/#03 */ - d = digest_new(); - digest_update(d, - (unsigned char*)"\x8c\xf5\x3d\x90\x07\x7d\xf9\xa0\x43\xbf\x8d" - "\x10\xb4\x70\xb1\x44\x78\x44\x11\xc9\x3a\x4d\x50\x45\x56\x83" - "\x4d\xae\x3e\xa4\xa5\xbb", 32); - digest_getdigest(d, output, 32); - tt_mem_op(output, ==, - "\x56\x05\x9e\x8c\xb3\xc2\x97\x8b\x19\x82\x08\xbf" - "\x5c\xa1\xe1\xea\x56\x59\xb7\x37\xa5\x06\x32\x4b" - "\x7c\xec\x75\xb5\xeb\xaf\x05\x7d", 32); - - /* Third SHA test vector: - Test for the 1304-bit entry of: - http://csrc.nist.gov/groups/STM/cavp/#03 */ - d = digest_new(); - digest_update(d, - (unsigned char*)"\xeb\xac\xcc\x34\xd6\xd6\xd3\xd2\x1e\xd0\xad" - "\x2b\xa7\xc0\x7c\x21\xd2\x53\xc4\x81\x4f\x4a\xd8\x9d\x32\x36" - "\x92\x37\x49\x7f\x47\xa1\xad\xab\xfa\x23\x98\xdd\xd0\x9d\x76" - "\x9c\xc4\x6d\x3f\xd6\x9c\x93\x03\x25\x1c\x13\xc7\x50\x79\x9b" - "\x8f\x15\x11\x66\xbc\x26\x58\x60\x98\x71\x16\x8b\x30\xa4\xd0" - "\xa1\x62\xf1\x83\xfb\x36\x0f\x99\xb1\x72\x81\x15\x03\x68\x1a" - "\x11\xf8\x13\xc1\x6a\x44\x62\x72\xba\x6f\xd4\x85\x86\x34\x45" - "\x33\xb9\x28\x08\x56\x51\x9c\x35\x70\x59\xc3\x44\xef\x17\x18" - "\xdb\xaf\x86\xfa\xe5\xc1\x07\x99\xe4\x6b\x53\x16\x88\x6f\xb4" - "\xe6\x80\x90\x75\x78\x90\x53\x96\x17\xe4\x03\xc5\x11\xa4\xf7" - "\x8a\x19\xc8\x18\xc2\xea\x2e\x9d\x4e\x2d\xe9\x19\x0c\x9d\xdd" - "\xb8\x06", 163); - digest_getdigest(d, output, 32); - tt_mem_op(output, ==, - "\xc9\x07\x18\x04\x43\xde\xe3\xcb\xcc\xb4\xc3\x13" - "\x28\xe6\x25\x15\x85\x27\xa5\x93\xb8\x78\xde\x1b" - "\x8e\x4b\xa3\x7f\x1d\x69\xfb\x66", 32); + int i; + for (i = 0; testvecs[i].input; i++) { + d = digest_new(); + digest_update(d, (unsigned char *) testvecs[i].input, + strlen(testvecs[i].input)); + digest_getdigest(d, output, 32); + digest_free(d); + tt_mem_op(output, ==, testvecs[i].output, 32); + } /* XXX Try doing init, update, update, output. */ - /* XXX add a base16-decode function so we can implement a tt_mem_op or - something */ - end: - if (d) - digest_free(d); + end:; } static void

1 0

[obfsproxy/master] Fix minor memory leaks in protocol-specific option parsing and a major one in obfs2.c:digest_new.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 2dd47ce6624d374932f7c212b1f719ad09143c5e Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 11:56:42 2011 -0700 Fix minor memory leaks in protocol-specific option parsing and a major one in obfs2.c:digest_new. --- src/protocols/dummy.c | 2 +- src/protocols/obfs2.c | 4 +++- 2 files changed, 4 insertions(+), 2 deletions(-) diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index c65f7b5..578182a 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -31,7 +31,7 @@ dummy_init(int n_options, const char *const *options) = xzalloc(sizeof(struct protocol_params_t)); if (parse_and_set_options(n_options, options, params) < 0) { - free(params); + proto_params_free(params); usage(); return NULL; } diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 5c9aedc..6688ebf 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -6,6 +6,7 @@ #define PROTOCOL_OBFS2_PRIVATE #include "obfs2.h" +#include "../protocol.h" #include <stdlib.h> #include <string.h> @@ -37,8 +38,8 @@ obfs2_init(int n_options, const char *const *options) = xzalloc(sizeof(struct protocol_params_t)); if (parse_and_set_options(n_options, options, params) < 0) { + proto_params_free(params); usage(); - free(params); return NULL; } @@ -181,6 +182,7 @@ derive_key(void *s, const char *keytype) d = digest_new(); digest_update(d, buf, sizeof(buf)); digest_getdigest(d, buf, sizeof(buf)); + digest_free(d); } }

1 0

[obfsproxy/master] Import container library from Tor.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit a76f6457e330d14d09d490d2c73f47ac2c7369c6 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 09:56:07 2011 -0700 Import container library from Tor. * src/container.c, src/container.h, src/ht.h, src/test/unittest_container.c: New files. * Makefile.am: Add new files (and some old files that got missed). * src/test/unittest.c: Add test group for container library. * configure.ac: Check size of int. Check for 'inline'. * util.h: Include stdint.h (unconditionally for now). (xstrndup, ui64_log2, ascii_isspace, ascii_strstrip, ascii_strlower): New functions required by container.c. * util.c: Define said new functions. * crypt.h, crypt.c (random_int): Another function needed by container.c. --- Makefile.am | 5 + configure.ac | 18 +- src/container.c | 1441 +++++++++++++++++++++++++++++++++++++++++ src/container.h | 685 ++++++++++++++++++++ src/crypt.c | 24 + src/crypt.h | 5 + src/ht.h | 471 ++++++++++++++ src/test/unittest.c | 2 + src/test/unittest_container.c | 772 ++++++++++++++++++++++ src/util.c | 74 +++ src/util.h | 19 +- 11 files changed, 3514 insertions(+), 2 deletions(-) diff --git a/Makefile.am b/Makefile.am index 521ba24..ff518ad 100644 --- a/Makefile.am +++ b/Makefile.am @@ -9,6 +9,7 @@ noinst_LIBRARIES = libobfsproxy.a noinst_PROGRAMS = unittests libobfsproxy_a_SOURCES = \ + src/container.c \ src/crypt.c \ src/network.c \ src/protocol.c \ @@ -26,12 +27,16 @@ obfsproxy_SOURCES = \ unittests_SOURCES = \ src/test/tinytest.c \ src/test/unittest.c \ + src/test/unittest_container.c \ src/test/unittest_crypt.c \ src/test/unittest_obfs2.c \ src/test/unittest_socks.c noinst_HEADERS = \ + src/container.h \ src/crypt.h \ + src/ht.h \ + src/main.h \ src/network.h \ src/protocol.h \ src/sha256.h \ diff --git a/configure.ac b/configure.ac index 32b7138..fc82507 100644 --- a/configure.ac +++ b/configure.ac @@ -1,13 +1,22 @@ AC_PREREQ([2.61])dnl Possibly earlier will do, but this is what I have AC_INIT([obsproxy], [0.0]) AC_CONFIG_SRCDIR([src/main.c]) - AM_INIT_AUTOMAKE([foreign]) +dnl The stock definition of AC_INCLUDES_DEFAULT performs a whole bunch +dnl of completely unnecessary checks *even if* you override its +dnl mostly-useless default header list at invocation time. +dnl Replace it with a version that does nothing unless requested. +m4_pushdef([AC_INCLUDES_DEFAULT], [$1]) + +### Programs ### + AC_PROG_CC AC_PROG_RANLIB PKG_PROG_PKG_CONFIG +### Libraries ### + PKG_CHECK_MODULES([libevent], [libevent >= 2.0]) # Presently no need for libssl, only libcrypto. PKG_CHECK_MODULES([libcrypto], [libcrypto >= 0.9.7]) @@ -28,6 +37,13 @@ LIBS="$libevent_LIBS $libcrypto_LIBS" AX_LIB_WINSOCK2 LIBS="$save_LIBS" +### C features ### + +AC_C_INLINE +AC_CHECK_SIZEOF(int) + +### Output ### + AC_CONFIG_FILES([Makefile]) AC_CONFIG_HEADERS([config.h]) AC_OUTPUT diff --git a/src/container.c b/src/container.c new file mode 100644 index 0000000..b66a819 --- /dev/null +++ b/src/container.c @@ -0,0 +1,1441 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file container.c + * \brief Implements a smartlist (a resizable array) along + * with helper functions to use smartlists. Also includes + * hash table implementations of a string-to-void* map, and of + * a digest-to-void* map. + **/ + +#include "util.h" +#include "container.h" +#include "crypt.h" +#include "ht.h" + +/** All newly allocated smartlists have this capacity. */ +#define SMARTLIST_DEFAULT_CAPACITY 16 + +/** Allocate and return an empty smartlist. + */ +smartlist_t * +smartlist_create(void) +{ + smartlist_t *sl = xmalloc(sizeof(smartlist_t)); + sl->num_used = 0; + sl->capacity = SMARTLIST_DEFAULT_CAPACITY; + sl->list = xmalloc(sizeof(void *) * sl->capacity); + return sl; +} + +/** Deallocate a smartlist. Does not release storage associated with the + * list's elements. + */ +void +smartlist_free(smartlist_t *sl) +{ + if (!sl) + return; + free(sl->list); + free(sl); +} + +/** Remove all elements from the list. + */ +void +smartlist_clear(smartlist_t *sl) +{ + sl->num_used = 0; +} + +/** Make sure that sl can hold at least size entries. */ +static inline void +smartlist_ensure_capacity(smartlist_t *sl, int size) +{ + if (size > sl->capacity) { + int higher = sl->capacity * 2; + while (size > higher) + higher *= 2; + obfs_assert(higher > 0); /* detect overflow */ + sl->capacity = higher; + sl->list = xrealloc(sl->list, sizeof(void*)*sl->capacity); + } +} + +/** Append element to the end of the list. */ +void +smartlist_add(smartlist_t *sl, void *element) +{ + smartlist_ensure_capacity(sl, sl->num_used+1); + sl->list[sl->num_used++] = element; +} + +/** Append each element from S2 to the end of S1. */ +void +smartlist_add_all(smartlist_t *s1, const smartlist_t *s2) +{ + int new_size = s1->num_used + s2->num_used; + obfs_assert(new_size >= s1->num_used); /* check for overflow. */ + smartlist_ensure_capacity(s1, new_size); + memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*)); + s1->num_used = new_size; +} + +/** Remove all elements E from sl such that E==element. Preserve + * the order of any elements before E, but elements after E can be + * rearranged. + */ +void +smartlist_remove(smartlist_t *sl, const void *element) +{ + int i; + if (element == NULL) + return; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) { + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + } +} + +/** If sl is nonempty, remove and return the final element. Otherwise, + * return NULL. */ +void * +smartlist_pop_last(smartlist_t *sl) +{ + obfs_assert(sl); + if (sl->num_used) + return sl->list[--sl->num_used]; + else + return NULL; +} + +/** Reverse the order of the items in sl. */ +void +smartlist_reverse(smartlist_t *sl) +{ + int i, j; + void *tmp; + obfs_assert(sl); + for (i = 0, j = sl->num_used-1; i < j; ++i, --j) { + tmp = sl->list[i]; + sl->list[i] = sl->list[j]; + sl->list[j] = tmp; + } +} + +/** If there are any strings in sl equal to element, remove and free them. + * Does not preserve order. */ +void +smartlist_string_remove(smartlist_t *sl, const char *element) +{ + int i; + obfs_assert(sl); + obfs_assert(element); + for (i = 0; i < sl->num_used; ++i) { + if (!strcmp(element, sl->list[i])) { + free(sl->list[i]); + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + } + } +} + +/** Return true iff some element E of sl has E==element. + */ +int +smartlist_isin(const smartlist_t *sl, const void *element) +{ + int i; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) + return 1; + return 0; +} + +/** Return true iff sl has some element E such that + * !strcmp(E,element) + */ +int +smartlist_string_isin(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** If element is equal to an element of sl, return that + * element's index. Otherwise, return -1. */ +int +smartlist_string_pos(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return -1; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return i; + return -1; +} + +/** Return true iff sl has some element E such that + * !strcasecmp(E,element) + */ +int +smartlist_string_isin_case(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcasecmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** Return true iff sl has some element E such that E is equal + * to the decimal encoding of num. + */ +int +smartlist_string_num_isin(const smartlist_t *sl, int num) +{ + char buf[32]; /* long enough for 64-bit int, and then some. */ + obfs_snprintf(buf,sizeof(buf),"%d", num); + return smartlist_string_isin(sl, buf); +} + +/** Return true iff the two lists contain the same strings in the same + * order, or if they are both NULL. */ +int +smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2) +{ + if (sl1 == NULL) + return sl2 == NULL; + if (sl2 == NULL) + return 0; + if (smartlist_len(sl1) != smartlist_len(sl2)) + return 0; + SMARTLIST_FOREACH(sl1, const char *, cp1, { + const char *cp2 = smartlist_get(sl2, cp1_sl_idx); + if (strcmp(cp1, cp2)) + return 0; + }); + return 1; +} + +/** Return true iff sl has some element E such that + * !memcmp(E,element,SHA256_LENGTH) + */ +int +smartlist_digest_isin(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (!memcmp((const char*)sl->list[i],element,SHA256_LENGTH)) + return 1; + return 0; +} + +/** Return true iff some element E of sl2 has smartlist_isin(sl1,E). + */ +int +smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + if (smartlist_isin(sl1, sl2->list[i])) + return 1; + return 0; +} + +/** Remove every element E of sl1 such that !smartlist_isin(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl1->num_used; i++) + if (!smartlist_isin(sl2, sl1->list[i])) { + sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + } +} + +/** Remove every element E of sl1 such that smartlist_isin(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + smartlist_remove(sl1, sl2->list[i]); +} + +/** Remove the idxth element of sl; if idx is not the last + * element, swap the last element of sl into the idxth space. + */ +void +smartlist_del(smartlist_t *sl, int idx) +{ + obfs_assert(sl); + obfs_assert(idx>=0); + obfs_assert(idx < sl->num_used); + sl->list[idx] = sl->list[--sl->num_used]; +} + +/** Remove the idxth element of sl; if idx is not the last element, + * moving all subsequent elements back one space. Return the old value + * of the idxth element. + */ +void +smartlist_del_keeporder(smartlist_t *sl, int idx) +{ + obfs_assert(sl); + obfs_assert(idx>=0); + obfs_assert(idx < sl->num_used); + --sl->num_used; + if (idx < sl->num_used) + memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx)); +} + +/** Insert the value val as the new idxth element of + * sl, moving all items previously at idx or later + * forward one space. + */ +void +smartlist_insert(smartlist_t *sl, int idx, void *val) +{ + obfs_assert(sl); + obfs_assert(idx>=0); + obfs_assert(idx <= sl->num_used); + if (idx == sl->num_used) { + smartlist_add(sl, val); + } else { + smartlist_ensure_capacity(sl, sl->num_used+1); + /* Move other elements away */ + if (idx < sl->num_used) + memmove(sl->list + idx + 1, sl->list + idx, + sizeof(void*)*(sl->num_used-idx)); + sl->num_used++; + sl->list[idx] = val; + } +} + +/** + * Split a string str along all occurrences of sep, + * appending the (newly allocated) split strings, in order, to + * sl. Return the number of strings added to sl. + * + * If flags&SPLIT_SKIP_SPACE is true, remove initial and + * trailing space from each entry. + * If flags&SPLIT_IGNORE_BLANK is true, remove any entries + * of length 0. + * If flags&SPLIT_STRIP_SPACE is true, strip spaces from each + * split string. + * + * If max\>0, divide the string into no more than max pieces. If + * sep is NULL, split on any sequence of horizontal space. + */ +int +smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max) +{ + const char *cp, *end, *next; + int n = 0; + + obfs_assert(sl); + obfs_assert(str); + + cp = str; + while (1) { + if (flags&SPLIT_SKIP_SPACE) { + while (ascii_isspace(*cp)) ++cp; + } + + if (max>0 && n == max-1) { + end = strchr(cp,'\0'); + } else if (sep) { + end = strstr(cp,sep); + if (!end) + end = strchr(cp,'\0'); + } else { + for (end = cp; *end && *end != '\t' && *end != ' '; ++end) + ; + } + + obfs_assert(end); + + if (!*end) { + next = NULL; + } else if (sep) { + next = end+strlen(sep); + } else { + next = end+1; + while (*next == '\t' || *next == ' ') + ++next; + } + + if (flags&SPLIT_SKIP_SPACE) { + while (end > cp && ascii_isspace(*(end-1))) + --end; + } + if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) { + char *string = xstrndup(cp, end-cp); + if (flags&SPLIT_STRIP_SPACE) + ascii_strstrip(string, " "); + smartlist_add(sl, string); + ++n; + } + if (!next) + break; + cp = next; + } + + return n; +} + +/** Allocate and return a new string containing the concatenation of + * the elements of sl, in order, separated by join. If + * terminate is true, also terminate the string with join. + * If len_out is not NULL, set len_out to the length of + * the returned string. Requires that every element of sl is + * NUL-terminated string. + */ +char * +smartlist_join_strings(smartlist_t *sl, const char *join, + int terminate, size_t *len_out) +{ + return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out); +} + +/** As smartlist_join_strings, but instead of separating/terminated with a + * NUL-terminated string join, uses the join_len-byte sequence + * at join. (Useful for generating a sequence of NUL-terminated + * strings.) + */ +char * +smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) +{ + int i; + size_t n = 0; + char *r = NULL, *dst, *src; + + obfs_assert(sl); + obfs_assert(join); + + if (terminate) + n = join_len; + + for (i = 0; i < sl->num_used; ++i) { + n += strlen(sl->list[i]); + if (i+1 < sl->num_used) /* avoid double-counting the last one */ + n += join_len; + } + dst = r = xmalloc(n+1); + for (i = 0; i < sl->num_used; ) { + for (src = sl->list[i]; *src; ) + *dst++ = *src++; + if (++i < sl->num_used) { + memcpy(dst, join, join_len); + dst += join_len; + } + } + if (terminate) { + memcpy(dst, join, join_len); + dst += join_len; + } + *dst = '\0'; + + if (len_out) + *len_out = dst-r; + return r; +} + +/** Sort the members of sl into an order defined by + * the ordering function compare, which returns less then 0 if a + * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b. + */ +void +smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) +{ + if (!sl->num_used) + return; + qsort(sl->list, sl->num_used, sizeof(void*), + (int (*)(const void *,const void*))compare); +} + +/** Given a smartlist sl sorted with the function compare, + * return the most frequent member in the list. Break ties in favor of + * later elements. If the list is empty, return NULL. + */ +void * +smartlist_get_most_frequent(const smartlist_t *sl, + int (*compare)(const void **a, const void **b)) +{ + const void *most_frequent = NULL; + int most_frequent_count = 0; + + const void *cur = NULL; + int i, count=0; + + if (!sl->num_used) + return NULL; + for (i = 0; i < sl->num_used; ++i) { + const void *item = sl->list[i]; + if (cur && 0 == compare(&cur, &item)) { + ++count; + } else { + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + cur = item; + count = 1; + } + } + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + return (void*)most_frequent; +} + +/** Given a sorted smartlist sl and the comparison function used to + * sort it, remove all duplicate members. If free_fn is provided, calls + * free_fn on each duplicate. Otherwise, just removes them. Preserves order. + */ +void +smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *a)) +{ + int i; + for (i=1; i < sl->num_used; ++i) { + if (compare((const void **)&(sl->list[i-1]), + (const void **)&(sl->list[i])) == 0) { + if (free_fn) + free_fn(sl->list[i]); + smartlist_del_keeporder(sl, i--); + } + } +} + +/** Return a randomly chosen element of sl; or NULL if sl + * is empty. */ + +void * +smartlist_choose(const smartlist_t *sl) +{ + int len = smartlist_len(sl); + if (len) + return smartlist_get(sl, random_int(len)); + return NULL; /* no elements to choose from */ +} + +/** Scramble the elements of sl into a random order. */ +void +smartlist_shuffle(smartlist_t *sl) +{ + int i; + + /* From the end of the list to the front, choose at random from the + positions we haven't looked at yet, and swap that position into the + current position. Remember to give "no swap" the same probability as + any other swap. */ + for (i = smartlist_len(sl)-1; i > 0; --i) { + int j = random_int(i+1); + smartlist_swap(sl, i, j); + } +} + + +/** Assuming the members of sl are in order, return a pointer to the + * member that matches key. Ordering and matching are defined by a + * compare function that returns 0 on a match; less than 0 if key is + * less than member, and greater than 0 if key is greater then member. + */ +void * +smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) +{ + int found, idx; + idx = smartlist_bsearch_idx(sl, key, compare, &found); + return found ? smartlist_get(sl, idx) : NULL; +} + +/** Assuming the members of sl are in order, return the index of the + * member that matches key. If no member matches, return the index of + * the first member greater than key, or smartlist_len(sl) if no member + * is greater than key. Set found_out to true on a match, to + * false otherwise. Ordering and matching are defined by a compare + * function that returns 0 on a match; less than 0 if key is less than member, + * and greater than 0 if key is greater then member. + */ +int +smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out) +{ + int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid; + + while (lo <= hi) { + mid = (lo + hi) / 2; + cmp = compare(key, (const void**) &(sl->list[mid])); + if (cmp>0) { /* key > sl[mid] */ + lo = mid+1; + } else if (cmp<0) { /* key < sl[mid] */ + hi = mid-1; + } else { /* key == sl[mid] */ + *found_out = 1; + return mid; + } + } + /* lo > hi. */ + { + obfs_assert(lo >= 0); + if (lo < smartlist_len(sl)) { + cmp = compare(key, (const void**) &(sl->list[lo])); + obfs_assert(cmp < 0); + } else if (smartlist_len(sl)) { + cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1])); + obfs_assert(cmp > 0); + } + } + *found_out = 0; + return lo; +} + +/** Helper: compare two const char **s. */ +static int +_compare_string_ptrs(const void **_a, const void **_b) +{ + return strcmp((const char*)*_a, (const char*)*_b); +} + +/** Sort a smartlist sl containing strings into lexically ascending + * order. */ +void +smartlist_sort_strings(smartlist_t *sl) +{ + smartlist_sort(sl, _compare_string_ptrs); +} + +/** Return the most frequent string in the sorted list sl */ +char * +smartlist_get_most_frequent_string(smartlist_t *sl) +{ + return smartlist_get_most_frequent(sl, _compare_string_ptrs); +} + +/** Remove duplicate strings from a sorted list, and free them with free(). + */ +void +smartlist_uniq_strings(smartlist_t *sl) +{ + smartlist_uniq(sl, _compare_string_ptrs, free); +} + +/* Heap-based priority queue implementation for O(lg N) insert and remove. + * Recall that the heap property is that, for every index I, h[I] < + * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]]. + * + * For us to remove items other than the topmost item, each item must store + * its own index within the heap. When calling the pqueue functions, tell + * them about the offset of the field that stores the index within the item. + * + * Example: + * + * typedef struct timer_t { + * struct timeval tv; + * int heap_index; + * } timer_t; + * + * static int compare(const void *p1, const void *p2) { + * const timer_t *t1 = p1, *t2 = p2; + * if (t1->tv.tv_sec < t2->tv.tv_sec) { + * return -1; + * } else if (t1->tv.tv_sec > t2->tv.tv_sec) { + * return 1; + * } else { + * return t1->tv.tv_usec - t2->tv_usec; + * } + * } + * + * void timer_heap_insert(smartlist_t *heap, timer_t *timer) { + * smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index), + * timer); + * } + * + * void timer_heap_pop(smartlist_t *heap) { + * return smartlist_pqueue_pop(heap, compare, + * STRUCT_OFFSET(timer_t, heap_index)); + * } + */ + +/** @{ */ +/** Functions to manipulate heap indices to find a node's parent and children. + * + * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] + * = 2*x + 1. But this is C, so we have to adjust a little. */ +//#define LEFT_CHILD(i) ( ((i)+1)*2 - 1) +//#define RIGHT_CHILD(i) ( ((i)+1)*2 ) +//#define PARENT(i) ( ((i)+1)/2 - 1) +#define LEFT_CHILD(i) ( 2*(i) + 1 ) +#define RIGHT_CHILD(i) ( 2*(i) + 2 ) +#define PARENT(i) ( ((i)-1) / 2 ) +/** }@ */ + +/** @{ */ +/** Helper macros for heaps: Given a local variable idx_field_offset + * set to the offset of an integer index within the heap element structure, + * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to + * where p's index is stored. Given additionally a local smartlist sl, + * UPDATE_IDX(i) sets the index of the element at i to the correct + * value (that is, to i). + */ +#define IDXP(p) ((int*)( ((char*)(p)) + idx_field_offset )) + +#define UPDATE_IDX(i) do { \ + void *updated = sl->list[i]; \ + *IDXP(updated) = i; \ + } while (0) + +#define IDX_OF_ITEM(p) (*IDXP(p)) +/** @} */ + +/** Helper. sl may have at most one violation of the heap property: + * the item at idx may be greater than one or both of its children. + * Restore the heap property. */ +static inline void +smartlist_heapify(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + int idx) +{ + while (1) { + int left_idx = LEFT_CHILD(idx); + int best_idx; + + if (left_idx >= sl->num_used) + return; + if (compare(sl->list[idx],sl->list[left_idx]) < 0) + best_idx = idx; + else + best_idx = left_idx; + if (left_idx+1 < sl->num_used && + compare(sl->list[left_idx+1],sl->list[best_idx]) < 0) + best_idx = left_idx + 1; + + if (best_idx == idx) { + return; + } else { + void *tmp = sl->list[idx]; + sl->list[idx] = sl->list[best_idx]; + sl->list[best_idx] = tmp; + UPDATE_IDX(idx); + UPDATE_IDX(best_idx); + + idx = best_idx; + } + } +} + +/** Insert item into the heap stored in sl, where order is + * determined by compare and the offset of the item in the heap is + * stored in an int-typed field at position idx_field_offset within + * item. + */ +void +smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx; + smartlist_add(sl,item); + UPDATE_IDX(sl->num_used-1); + + for (idx = sl->num_used - 1; idx; ) { + int parent = PARENT(idx); + if (compare(sl->list[idx], sl->list[parent]) < 0) { + void *tmp = sl->list[parent]; + sl->list[parent] = sl->list[idx]; + sl->list[idx] = tmp; + UPDATE_IDX(parent); + UPDATE_IDX(idx); + idx = parent; + } else { + return; + } + } +} + +/** Remove and return the top-priority item from the heap stored in sl, + * where order is determined by compare and the item's position is + * stored at position idx_field_offset within the item. sl must + * not be empty. */ +void * +smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + void *top; + obfs_assert(sl->num_used); + + top = sl->list[0]; + *IDXP(top)=-1; + if (--sl->num_used) { + sl->list[0] = sl->list[sl->num_used]; + UPDATE_IDX(0); + smartlist_heapify(sl, compare, idx_field_offset, 0); + } + return top; +} + +/** Remove the item item from the heap stored in sl, + * where order is determined by compare and the item's position is + * stored at position idx_field_offset within the item. sl must + * not be empty. */ +void +smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx = IDX_OF_ITEM(item); + obfs_assert(idx >= 0); + obfs_assert(sl->list[idx] == item); + --sl->num_used; + *IDXP(item) = -1; + if (idx == sl->num_used) { + return; + } else { + sl->list[idx] = sl->list[sl->num_used]; + UPDATE_IDX(idx); + smartlist_heapify(sl, compare, idx_field_offset, idx); + } +} + +/** Assert that the heap property is correctly maintained by the heap stored + * in sl, where order is determined by compare. */ +void +smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + int i; + for (i = sl->num_used - 1; i >= 0; --i) { + if (i>0) + obfs_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0); + obfs_assert(IDX_OF_ITEM(sl->list[i]) == i); + } +} + +/** Helper: compare two SHA256_LENGTH digests. */ +static int +_compare_digests(const void **_a, const void **_b) +{ + return memcmp((const char*)*_a, (const char*)*_b, SHA256_LENGTH); +} + +/** Sort the list of SHA256_LENGTH-byte digests into ascending order. */ +void +smartlist_sort_digests(smartlist_t *sl) +{ + smartlist_sort(sl, _compare_digests); +} + +/** Remove duplicate digests from a sorted list, and free them with free(). + */ +void +smartlist_uniq_digests(smartlist_t *sl) +{ + smartlist_uniq(sl, _compare_digests, free); +} + +/** Helper: Declare an entry type and a map type to implement a mapping using + * ht.h. The map type will be called maptype. The key part of each + * entry is declared using the C declaration keydecl. All functions + * and types associated with the map get prefixed with prefix */ +#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \ + typedef struct prefix ## entry_t { \ + HT_ENTRY(prefix ## entry_t) node; \ + void *val; \ + keydecl; \ + } prefix ## entry_t; \ + struct maptype { \ + HT_HEAD(prefix ## impl, prefix ## entry_t) head; \ + } + +DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_); +DEFINE_MAP_STRUCTS(digestmap_t, char key[SHA256_LENGTH], digestmap_); + +/** Helper: compare strmap_entry_t objects by key value. */ +static inline int +strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b) +{ + return !strcmp(a->key, b->key); +} + +/** Helper: return a hash value for a strmap_entry_t. */ +static inline unsigned int +strmap_entry_hash(const strmap_entry_t *a) +{ + return ht_string_hash(a->key); +} + +/** Helper: compare digestmap_entry_t objects by key value. */ +static inline int +digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b) +{ + return !memcmp(a->key, b->key, SHA256_LENGTH); +} + +/** Helper: return a hash value for a digest_map_t. */ +static inline unsigned int +digestmap_entry_hash(const digestmap_entry_t *a) +{ +#if SIZEOF_INT != 8 + const uint32_t *p = (const uint32_t*)a->key; + return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]; +#else + const uint64_t *p = (const uint64_t*)a->key; + return p[0] ^ p[1]; +#endif +} + +HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq) +HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq, 0.6, malloc, realloc, free) + +HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq) +HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq, 0.6, malloc, realloc, free) + +/** Constructor to create a new empty map from strings to void*'s. + */ +strmap_t * +strmap_new(void) +{ + strmap_t *result; + result = xmalloc(sizeof(strmap_t)); + HT_INIT(strmap_impl, &result->head); + return result; +} + +/** Constructor to create a new empty map from digests to void*'s. + */ +digestmap_t * +digestmap_new(void) +{ + digestmap_t *result; + result = xmalloc(sizeof(digestmap_t)); + HT_INIT(digestmap_impl, &result->head); + return result; +} + +/** Set the current value for key to val. Returns the previous + * value for key if one was set, or NULL if one was not. + * + * This function makes a copy of key if necessary, but not of + * val. + */ +void * +strmap_set(strmap_t *map, const char *key, void *val) +{ + strmap_entry_t *resolve; + strmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + obfs_assert(val); + search.key = (char*)key; + resolve = HT_FIND(strmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + resolve->val = val; + return oldval; + } else { + resolve = xzalloc(sizeof(strmap_entry_t)); + resolve->key = xstrdup(key); + resolve->val = val; + obfs_assert(!HT_FIND(strmap_impl, &map->head, resolve)); + HT_INSERT(strmap_impl, &map->head, resolve); + return NULL; + } +} + +#define OPTIMIZED_DIGESTMAP_SET + +/** Like strmap_set() above but for digestmaps. */ +void * +digestmap_set(digestmap_t *map, const char *key, void *val) +{ +#ifndef OPTIMIZED_DIGESTMAP_SET + digestmap_entry_t *resolve; +#endif + digestmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + obfs_assert(val); + memcpy(&search.key, key, SHA256_LENGTH); +#ifndef OPTIMIZED_DIGESTMAP_SET + resolve = HT_FIND(digestmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + resolve->val = val; + return oldval; + } else { + resolve = xzalloc(sizeof(digestmap_entry_t)); + memcpy(resolve->key, key, SHA256_LENGTH); + resolve->val = val; + HT_INSERT(digestmap_impl, &map->head, resolve); + return NULL; + } +#else + /* We spend up to 5% of our time in this function, so the code below is + * meant to optimize the check/alloc/set cycle by avoiding the two trips to + * the hash table that we do in the unoptimized code above. (Each of + * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.) + */ + _HT_FIND_OR_INSERT(digestmap_impl, node, digestmap_entry_hash, &(map->head), + digestmap_entry_t, &search, ptr, + { + /* we found an entry. */ + oldval = (*ptr)->val; + (*ptr)->val = val; + return oldval; + }, + { + /* We didn't find the entry. */ + digestmap_entry_t *newent = + xzalloc(sizeof(digestmap_entry_t)); + memcpy(newent->key, key, SHA256_LENGTH); + newent->val = val; + _HT_FOI_INSERT(node, &(map->head), &search, newent, ptr); + return NULL; + }); +#endif +} + +/** Return the current value associated with key, or NULL if no + * value is set. + */ +void * +strmap_get(const strmap_t *map, const char *key) +{ + strmap_entry_t *resolve; + strmap_entry_t search; + obfs_assert(map); + obfs_assert(key); + search.key = (char*)key; + resolve = HT_FIND(strmap_impl, &map->head, &search); + if (resolve) { + return resolve->val; + } else { + return NULL; + } +} + +/** Like strmap_get() above but for digestmaps. */ +void * +digestmap_get(const digestmap_t *map, const char *key) +{ + digestmap_entry_t *resolve; + digestmap_entry_t search; + obfs_assert(map); + obfs_assert(key); + memcpy(&search.key, key, SHA256_LENGTH); + resolve = HT_FIND(digestmap_impl, &map->head, &search); + if (resolve) { + return resolve->val; + } else { + return NULL; + } +} + +/** Remove the value currently associated with key from the map. + * Return the value if one was set, or NULL if there was no entry for + * key. + * + * Note: you must free any storage associated with the returned value. + */ +void * +strmap_remove(strmap_t *map, const char *key) +{ + strmap_entry_t *resolve; + strmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + search.key = (char*)key; + resolve = HT_REMOVE(strmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + free(resolve->key); + free(resolve); + return oldval; + } else { + return NULL; + } +} + +/** Like strmap_remove() above but for digestmaps. */ +void * +digestmap_remove(digestmap_t *map, const char *key) +{ + digestmap_entry_t *resolve; + digestmap_entry_t search; + void *oldval; + obfs_assert(map); + obfs_assert(key); + memcpy(&search.key, key, SHA256_LENGTH); + resolve = HT_REMOVE(digestmap_impl, &map->head, &search); + if (resolve) { + oldval = resolve->val; + free(resolve); + return oldval; + } else { + return NULL; + } +} + +/** Same as strmap_set, but first converts key to lowercase. */ +void * +strmap_set_lc(strmap_t *map, const char *key, void *val) +{ + /* We could be a little faster by using strcasecmp instead, and a separate + * type, but I don't think it matters. */ + void *v; + char *lc_key = xstrdup(key); + ascii_strlower(lc_key); + v = strmap_set(map,lc_key,val); + free(lc_key); + return v; +} + +/** Same as strmap_get, but first converts key to lowercase. */ +void * +strmap_get_lc(const strmap_t *map, const char *key) +{ + void *v; + char *lc_key = xstrdup(key); + ascii_strlower(lc_key); + v = strmap_get(map,lc_key); + free(lc_key); + return v; +} + +/** Same as strmap_remove, but first converts key to lowercase */ +void * +strmap_remove_lc(strmap_t *map, const char *key) +{ + void *v; + char *lc_key = xstrdup(key); + ascii_strlower(lc_key); + v = strmap_remove(map,lc_key); + free(lc_key); + return v; +} + +/** return an iterator pointer to the front of a map. + * + * Iterator example: + * + * \code + * // uppercase values in "map", removing empty values. + * + * strmap_iter_t *iter; + * const char *key; + * void *val; + * char *cp; + * + * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { + * strmap_iter_get(iter, &key, &val); + * cp = (char*)val; + * if (!*cp) { + * iter = strmap_iter_next_rmv(map,iter); + * free(val); + * } else { + * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); + * iter = strmap_iter_next(map,iter); + * } + * } + * \endcode + * + */ +strmap_iter_t * +strmap_iter_init(strmap_t *map) +{ + obfs_assert(map); + return HT_START(strmap_impl, &map->head); +} + +/** Start iterating through map. See strmap_iter_init() for example. */ +digestmap_iter_t * +digestmap_iter_init(digestmap_t *map) +{ + obfs_assert(map); + return HT_START(digestmap_impl, &map->head); +} + +/** Advance the iterator iter for map a single step to the next + * entry, and return its new value. */ +strmap_iter_t * +strmap_iter_next(strmap_t *map, strmap_iter_t *iter) +{ + obfs_assert(map); + obfs_assert(iter); + return HT_NEXT(strmap_impl, &map->head, iter); +} + +/** Advance the iterator iter for map a single step to the next entry, + * and return its new value. */ +digestmap_iter_t * +digestmap_iter_next(digestmap_t *map, digestmap_iter_t *iter) +{ + obfs_assert(map); + obfs_assert(iter); + return HT_NEXT(digestmap_impl, &map->head, iter); +} + +/** Advance the iterator iter a single step to the next entry, removing + * the current entry, and return its new value. + */ +strmap_iter_t * +strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter) +{ + strmap_entry_t *rmv; + obfs_assert(map); + obfs_assert(iter); + obfs_assert(*iter); + rmv = *iter; + iter = HT_NEXT_RMV(strmap_impl, &map->head, iter); + free(rmv->key); + free(rmv); + return iter; +} + +/** Advance the iterator iter a single step to the next entry, removing + * the current entry, and return its new value. + */ +digestmap_iter_t * +digestmap_iter_next_rmv(digestmap_t *map, digestmap_iter_t *iter) +{ + digestmap_entry_t *rmv; + obfs_assert(map); + obfs_assert(iter); + obfs_assert(*iter); + rmv = *iter; + iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter); + free(rmv); + return iter; +} + +/** Set *keyp and *valp to the current entry pointed to by + * iter. */ +void +strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp) +{ + obfs_assert(iter); + obfs_assert(*iter); + obfs_assert(keyp); + obfs_assert(valp); + *keyp = (*iter)->key; + *valp = (*iter)->val; +} + +/** Set *keyp and *valp to the current entry pointed to by + * iter. */ +void +digestmap_iter_get(digestmap_iter_t *iter, const char **keyp, void **valp) +{ + obfs_assert(iter); + obfs_assert(*iter); + obfs_assert(keyp); + obfs_assert(valp); + *keyp = (*iter)->key; + *valp = (*iter)->val; +} + +/** Return true iff iter has advanced past the last entry of + * map. */ +int +strmap_iter_done(strmap_iter_t *iter) +{ + return iter == NULL; +} + +/** Return true iff iter has advanced past the last entry of + * map. */ +int +digestmap_iter_done(digestmap_iter_t *iter) +{ + return iter == NULL; +} + +/** Remove all entries from map, and deallocate storage for those + * entries. If free_val is provided, it is invoked on every value in + * map. + */ +void +strmap_free(strmap_t *map, void (*free_val)(void*)) +{ + strmap_entry_t **ent, **next, *this; + if (!map) + return; + + for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) { + this = *ent; + next = HT_NEXT_RMV(strmap_impl, &map->head, ent); + free(this->key); + if (free_val) + free_val(this->val); + free(this); + } + obfs_assert(HT_EMPTY(&map->head)); + HT_CLEAR(strmap_impl, &map->head); + free(map); +} + +/** Remove all entries from map, and deallocate storage for those + * entries. If free_val is provided, it is invoked on every value in + * map. + */ +void +digestmap_free(digestmap_t *map, void (*free_val)(void*)) +{ + digestmap_entry_t **ent, **next, *this; + if (!map) + return; + for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) { + this = *ent; + next = HT_NEXT_RMV(digestmap_impl, &map->head, ent); + if (free_val) + free_val(this->val); + free(this); + } + obfs_assert(HT_EMPTY(&map->head)); + HT_CLEAR(digestmap_impl, &map->head); + free(map); +} + +/** Fail with an assertion error if anything has gone wrong with the internal + * representation of map. */ +void +strmap_assert_ok(const strmap_t *map) +{ + obfs_assert(!_strmap_impl_HT_REP_IS_BAD(&map->head)); +} +/** Fail with an assertion error if anything has gone wrong with the internal + * representation of map. */ +void +digestmap_assert_ok(const digestmap_t *map) +{ + obfs_assert(!_digestmap_impl_HT_REP_IS_BAD(&map->head)); +} + +/** Return true iff map has no entries. */ +int +strmap_isempty(const strmap_t *map) +{ + return HT_EMPTY(&map->head); +} + +/** Return true iff map has no entries. */ +int +digestmap_isempty(const digestmap_t *map) +{ + return HT_EMPTY(&map->head); +} + +/** Return the number of items in map. */ +int +strmap_size(const strmap_t *map) +{ + return HT_SIZE(&map->head); +} + +/** Return the number of items in map. */ +int +digestmap_size(const digestmap_t *map) +{ + return HT_SIZE(&map->head); +} + +/** Declare a function called funcname that acts as a find_nth_FOO + * function for an array of type elt_t*. + * + * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding + * the kth element of an n-element list can be done in O(n). Then again, this + * implementation is not in critical path, and it is obviously correct. */ +#define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ + static int \ + _cmp_ ## elt_t(const void *_a, const void *_b) \ + { \ + const elt_t *a = _a, *b = _b; \ + if (*a<*b) \ + return -1; \ + else if (*a>*b) \ + return 1; \ + else \ + return 0; \ + } \ + elt_t \ + funcname(elt_t *array, int n_elements, int nth) \ + { \ + obfs_assert(nth >= 0); \ + obfs_assert(nth < n_elements); \ + qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ + return array[nth]; \ + } + +IMPLEMENT_ORDER_FUNC(find_nth_int, int) +IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) +IMPLEMENT_ORDER_FUNC(find_nth_double, double) +IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) +IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t) +IMPLEMENT_ORDER_FUNC(find_nth_long, long) + +/** Return a newly allocated digestset_t, optimized to hold a total of + * max_elements digests with a reasonably low false positive weight. */ +digestset_t * +digestset_new(int max_elements) +{ + /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k + * is the number of hash functions per entry, m is the bits in the array, + * and n is the number of elements inserted. For us, k==4, n<=max_elements, + * and m==n_bits= approximately max_elements*32. This gives + * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019 + * + * It would be more optimal in space vs false positives to get this false + * positive rate by going for k==13, and m==18.5n, but we also want to + * conserve CPU, and k==13 is pretty big. + */ + int n_bits = 1u << (ui64_log2(max_elements)+5); + digestset_t *r = xmalloc(sizeof(digestset_t)); + r->mask = n_bits - 1; + r->ba = bitarray_init_zero(n_bits); + return r; +} + +/** Free all storage held in set. */ +void +digestset_free(digestset_t *set) +{ + if (!set) + return; + bitarray_free(set->ba); + free(set); +} diff --git a/src/container.h b/src/container.h new file mode 100644 index 0000000..e1c1a07 --- /dev/null +++ b/src/container.h @@ -0,0 +1,685 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef CONTAINER_H +#define CONTAINER_H + +#include <stdlib.h> +#include <string.h> +#include <time.h> + +/** A resizeable list of pointers, with associated helpful functionality. + * + * The members of this struct are exposed only so that macros and inlines can + * use them; all access to smartlist internals should go through the functions + * and macros defined here. + **/ +typedef struct smartlist_t { + /** @{ */ + /** list has enough capacity to store exactly capacity elements + * before it needs to be resized. Only the first num_used (\<= + * capacity) elements point to valid data. + */ + void **list; + int num_used; + int capacity; + /** @} */ +} smartlist_t; + +smartlist_t *smartlist_create(void); +void smartlist_free(smartlist_t *sl); +void smartlist_clear(smartlist_t *sl); +void smartlist_add(smartlist_t *sl, void *element); +void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2); +void smartlist_remove(smartlist_t *sl, const void *element); +void *smartlist_pop_last(smartlist_t *sl); +void smartlist_reverse(smartlist_t *sl); +void smartlist_string_remove(smartlist_t *sl, const char *element); +int smartlist_isin(const smartlist_t *sl, const void *element) ATTR_PURE; +int smartlist_string_isin(const smartlist_t *sl, const char *element) + ATTR_PURE; +int smartlist_string_pos(const smartlist_t *, const char *elt) ATTR_PURE; +int smartlist_string_isin_case(const smartlist_t *sl, const char *element) + ATTR_PURE; +int smartlist_string_num_isin(const smartlist_t *sl, int num) ATTR_PURE; +int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2) + ATTR_PURE; +int smartlist_digest_isin(const smartlist_t *sl, const char *element) + ATTR_PURE; +int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) + ATTR_PURE; +void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2); +void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2); + +#ifdef DEBUG_SMARTLIST +/** Return the number of items in sl. + */ +static inline int smartlist_len(const smartlist_t *sl) ATTR_PURE; +static inline int smartlist_len(const smartlist_t *sl) { + tor_assert(sl); + return (sl)->num_used; +} +/** Return the idxth element of sl. + */ +static inline void *smartlist_get(const smartlist_t *sl, int idx) ATTR_PURE; +static inline void *smartlist_get(const smartlist_t *sl, int idx) { + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(sl->num_used > idx); + return sl->list[idx]; +} +static inline void smartlist_set(smartlist_t *sl, int idx, void *val) { + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(sl->num_used > idx); + sl->list[idx] = val; +} +#else +#define smartlist_len(sl) ((sl)->num_used) +#define smartlist_get(sl, idx) ((sl)->list[idx]) +#define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val)) +#endif + +/** Exchange the elements at indices idx1 and idx2 of the + * smartlist sl. */ +static inline void smartlist_swap(smartlist_t *sl, int idx1, int idx2) +{ + if (idx1 != idx2) { + void *elt = smartlist_get(sl, idx1); + smartlist_set(sl, idx1, smartlist_get(sl, idx2)); + smartlist_set(sl, idx2, elt); + } +} + +void smartlist_del(smartlist_t *sl, int idx); +void smartlist_del_keeporder(smartlist_t *sl, int idx); +void smartlist_insert(smartlist_t *sl, int idx, void *val); +void smartlist_sort(smartlist_t *sl, + int (*compare)(const void **a, const void **b)); +void *smartlist_get_most_frequent(const smartlist_t *sl, + int (*compare)(const void **a, const void **b)); +void smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *elt)); + +void smartlist_shuffle(smartlist_t *sl); +void *smartlist_choose(const smartlist_t *sl); + +void smartlist_sort_strings(smartlist_t *sl); +void smartlist_sort_digests(smartlist_t *sl); + +char *smartlist_get_most_frequent_string(smartlist_t *sl); + +void smartlist_uniq_strings(smartlist_t *sl); +void smartlist_uniq_digests(smartlist_t *sl); +void *smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) + ATTR_PURE; +int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out); + +void smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item); +void *smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset); +void smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item); +void smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset); + +#define SPLIT_SKIP_SPACE 0x01 +#define SPLIT_IGNORE_BLANK 0x02 +#define SPLIT_STRIP_SPACE 0x04 +int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max); +char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, + size_t *len_out) ATTR_MALLOC; +char *smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) + ATTR_MALLOC; + +/** Iterate over the items in a smartlist sl, in order. For each item, + * assign it to a new local variable of type type named var, and + * execute the statement cmd. Inside the loop, the loop index can + * be accessed as var_sl_idx and the length of the list can be accessed + * as var_sl_len. + * + * NOTE: Do not change the length of the list while the loop is in progress, + * unless you adjust the _sl_len variable correspondingly. See second example + * below. + * + * Example use: + * <pre> + * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0); + * SMARTLIST_FOREACH(list, char *, cp, + * { + * printf("%d: %s\n", cp_sl_idx, cp); + * free(cp); + * }); + * smartlist_free(list); + * </pre> + * + * Example use (advanced): + * <pre> + * SMARTLIST_FOREACH(list, char *, cp, + * { + * if (!strcmp(cp, "junk")) { + * free(cp); + * SMARTLIST_DEL_CURRENT(list, cp); + * } + * }); + * </pre> + */ +/* Note: these macros use token pasting, and reach into smartlist internals. + * This can make them a little daunting. Here's the approximate unpacking of + * the above examples, for entertainment value: + * + * <pre> + * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0); + * { + * int cp_sl_idx, cp_sl_len = smartlist_len(list); + * char *cp; + * for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) { + * cp = smartlist_get(list, cp_sl_idx); + * printf("%d: %s\n", cp_sl_idx, cp); + * free(cp); + * } + * } + * smartlist_free(list); + * </pre> + * + * <pre> + * { + * int cp_sl_idx, cp_sl_len = smartlist_len(list); + * char *cp; + * for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) { + * cp = smartlist_get(list, cp_sl_idx); + * if (!strcmp(cp, "junk")) { + * free(cp); + * smartlist_del(list, cp_sl_idx); + * --cp_sl_idx; + * --cp_sl_len; + * } + * } + * } + * </pre> + */ +#define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ + do { \ + int var ## _sl_idx, var ## _sl_len=(sl)->num_used; \ + type var; \ + for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len; \ + ++var ## _sl_idx) { \ + var = (sl)->list[var ## _sl_idx]; + +#define SMARTLIST_FOREACH_END(var) \ + var = NULL; \ + } } while (0) + +#define SMARTLIST_FOREACH(sl, type, var, cmd) \ + SMARTLIST_FOREACH_BEGIN(sl,type,var) { \ + cmd; \ + } SMARTLIST_FOREACH_END(var) + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, remove the current element in a way that + * won't confuse the loop. */ +#define SMARTLIST_DEL_CURRENT(sl, var) \ + do { \ + smartlist_del(sl, var ## _sl_idx); \ + --var ## _sl_idx; \ + --var ## _sl_len; \ + } while (0) + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, replace the current element with val. + * Does not deallocate the current value of var. + */ +#define SMARTLIST_REPLACE_CURRENT(sl, var, val) \ + do { \ + smartlist_set(sl, var ## _sl_idx, val); \ + } while (0) + +/* Helper: Given two lists of items, possibly of different types, such that + * both lists are sorted on some common field (as determined by a comparison + * expression cmpexpr), and such that one list (sl1) has no + * duplicates on the common field, loop through the lists in lockstep, and + * execute unmatched_var2 on items in var2 that do not appear in + * var1. + * + * WARNING: It isn't safe to add remove elements from either list while the + * loop is in progress. + * + * Example use: + * SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs, + * routerinfo_list, routerinfo_t *, ri, + * memcmp(rs->identity_digest, ri->identity_digest, 20), + * log_info(LD_GENERAL,"No match for %s", ri->nickname)) { + * log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs); + * } SMARTLIST_FOREACH_JOIN_END(rs, ri); + **/ +/* The example above unpacks (approximately) to: + * int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list); + * int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list); + * int rs_ri_cmp; + * routerstatus_t *rs; + * routerinfo_t *ri; + * for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) { + * ri = smartlist_get(routerinfo_list, ri_sl_idx); + * while (rs_sl_idx < rs_sl_len) { + * rs = smartlist_get(routerstatus_list, rs_sl_idx); + * rs_ri_cmp = memcmp(rs->identity_digest, ri->identity_digest, 20); + * if (rs_ri_cmp > 0) { + * break; + * } else if (rs_ri_cmp == 0) { + * goto matched_ri; + * } else { + * ++rs_sl_idx; + * } + * } + * log_info(LD_GENERAL,"No match for %s", ri->nickname); + * continue; + * matched_ri: { + * log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs); + * } + * } + */ +#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \ + cmpexpr, unmatched_var2) \ + do { \ + int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \ + int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \ + int var1 ## _ ## var2 ## _cmp; \ + type1 var1; \ + type2 var2; \ + for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \ + var2 = (sl2)->list[var2##_sl_idx]; \ + while (var1##_sl_idx < var1##_sl_len) { \ + var1 = (sl1)->list[var1##_sl_idx]; \ + var1##_##var2##_cmp = (cmpexpr); \ + if (var1##_##var2##_cmp > 0) { \ + break; \ + } else if (var1##_##var2##_cmp == 0) { \ + goto matched_##var2; \ + } else { \ + ++var1##_sl_idx; \ + } \ + } \ + /* Ran out of v1, or no match for var2. */ \ + unmatched_var2; \ + continue; \ + matched_##var2: ; \ + +#define SMARTLIST_FOREACH_JOIN_END(var1, var2) \ + } \ + } while (0) + +#define DECLARE_MAP_FNS(maptype, keytype, prefix) \ + typedef struct maptype maptype; \ + typedef struct prefix##entry_t *prefix##iter_t; \ + maptype* prefix##new(void); \ + void* prefix##set(maptype *map, keytype key, void *val); \ + void* prefix##get(const maptype *map, keytype key); \ + void* prefix##remove(maptype *map, keytype key); \ + void prefix##free(maptype *map, void (*free_val)(void*)); \ + int prefix##isempty(const maptype *map); \ + int prefix##size(const maptype *map); \ + prefix##iter_t *prefix##iter_init(maptype *map); \ + prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \ + prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \ + void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \ + int prefix##iter_done(prefix##iter_t *iter); \ + void prefix##assert_ok(const maptype *map) + +/* Map from const char * to void *. Implemented with a hash table. */ +DECLARE_MAP_FNS(strmap_t, const char *, strmap_); +/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */ +DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_); + +#undef DECLARE_MAP_FNS + +/** Iterates over the key-value pairs in a map map in order. + * prefix is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_). + * The map's keys and values are of type keytype and valtype respectively; + * each iteration assigns them to keyvar and valvar. + * + * Example use: + * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { + * // use k and r + * } MAP_FOREACH_END. + */ +/* Unpacks to, approximately: + * { + * digestmap_iter_t *k_iter; + * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); + * k_iter = digestmap_iter_next(m, k_iter)) { + * const char *k; + * void *r_voidp; + * routerinfo_t *r; + * digestmap_iter_get(k_iter, &k, &r_voidp); + * r = r_voidp; + * // use k and r + * } + * } + */ +#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \ + do { \ + prefix##iter_t *keyvar##_iter; \ + for (keyvar##_iter = prefix##iter_init(map); \ + !prefix##iter_done(keyvar##_iter); \ + keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \ + keytype keyvar; \ + void *valvar##_voidp; \ + valtype valvar; \ + prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ + valvar = valvar##_voidp; + +/** As MAP_FOREACH, except allows members to be removed from the map + * during the iteration via MAP_DEL_CURRENT. Example use: + * + * Example use: + * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { + * if (is_very_old(r)) + * MAP_DEL_CURRENT(k); + * } MAP_FOREACH_END. + **/ +/* Unpacks to, approximately: + * { + * digestmap_iter_t *k_iter; + * int k_del=0; + * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); + * k_iter = k_del ? digestmap_iter_next(m, k_iter) + * : digestmap_iter_next_rmv(m, k_iter)) { + * const char *k; + * void *r_voidp; + * routerinfo_t *r; + * k_del=0; + * digestmap_iter_get(k_iter, &k, &r_voidp); + * r = r_voidp; + * if (is_very_old(r)) { + * k_del = 1; + * } + * } + * } + */ +#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \ + do { \ + prefix##iter_t *keyvar##_iter; \ + int keyvar##_del=0; \ + for (keyvar##_iter = prefix##iter_init(map); \ + !prefix##iter_done(keyvar##_iter); \ + keyvar##_iter = keyvar##_del ? \ + prefix##iter_next_rmv(map, keyvar##_iter) : \ + prefix##iter_next(map, keyvar##_iter)) { \ + keytype keyvar; \ + void *valvar##_voidp; \ + valtype valvar; \ + keyvar##_del=0; \ + prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ + valvar = valvar##_voidp; + +/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon + * member of the map. */ +#define MAP_DEL_CURRENT(keyvar) \ + do { \ + keyvar##_del = 1; \ + } while (0) + +/** Used to end a MAP_FOREACH() block. */ +#define MAP_FOREACH_END } while (0) + +/** As MAP_FOREACH, but does not require declaration of prefix or keytype. + * Example use: + * DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) { + * // use k and r + * } DIGESTMAP_FOREACH_END. + */ +#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar) + +/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or + * keytype. + * Example use: + * DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) { + * if (is_very_old(r)) + * MAP_DEL_CURRENT(k); + * } DIGESTMAP_FOREACH_END. + */ +#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar) +/** Used to end a DIGESTMAP_FOREACH() block. */ +#define DIGESTMAP_FOREACH_END MAP_FOREACH_END + +#define STRMAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar) +#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar) +#define STRMAP_FOREACH_END MAP_FOREACH_END + +void* strmap_set_lc(strmap_t *map, const char *key, void *val); +void* strmap_get_lc(const strmap_t *map, const char *key); +void* strmap_remove_lc(strmap_t *map, const char *key); + +#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \ + typedef struct maptype maptype; \ + typedef struct prefix##iter_t prefix##iter_t; \ + static inline maptype* prefix##new(void) \ + { \ + return (maptype*)digestmap_new(); \ + } \ + static inline digestmap_t* prefix##to_digestmap(maptype *map) \ + { \ + return (digestmap_t*)map; \ + } \ + static inline valtype* prefix##get(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_get((digestmap_t*)map, key); \ + } \ + static inline valtype* prefix##set(maptype *map, const char *key, \ + valtype *val) \ + { \ + return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ + } \ + static inline valtype* prefix##remove(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_remove((digestmap_t*)map, key); \ + } \ + static inline void prefix##free(maptype *map, void (*free_val)(void*)) \ + { \ + digestmap_free((digestmap_t*)map, free_val); \ + } \ + static inline int prefix##isempty(maptype *map) \ + { \ + return digestmap_isempty((digestmap_t*)map); \ + } \ + static inline int prefix##size(maptype *map) \ + { \ + return digestmap_size((digestmap_t*)map); \ + } \ + static inline prefix##iter_t *prefix##iter_init(maptype *map) \ + { \ + return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ + } \ + static inline prefix##iter_t *prefix##iter_next(maptype *map, \ + prefix##iter_t *iter) \ + { \ + return (prefix##iter_t*) digestmap_iter_next( \ + (digestmap_t*)map, (digestmap_iter_t*)iter); \ + } \ + static inline prefix##iter_t *prefix##iter_next_rmv(maptype *map, \ + prefix##iter_t *iter) \ + { \ + return (prefix##iter_t*) digestmap_iter_next_rmv( \ + (digestmap_t*)map, (digestmap_iter_t*)iter); \ + } \ + static inline void prefix##iter_get(prefix##iter_t *iter, \ + const char **keyp, \ + valtype **valp) \ + { \ + void *v; \ + digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \ + *valp = v; \ + } \ + static inline int prefix##iter_done(prefix##iter_t *iter) \ + { \ + return digestmap_iter_done((digestmap_iter_t*)iter); \ + } + +#if SIZEOF_INT == 4 +#define BITARRAY_SHIFT 5 +#elif SIZEOF_INT == 8 +#define BITARRAY_SHIFT 6 +#else +#error "int is neither 4 nor 8 bytes. I can't deal with that." +#endif +#define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1) + +/** A random-access array of one-bit-wide elements. */ +typedef unsigned int bitarray_t; +/** Create a new bit array that can hold n_bits bits. */ +static inline bitarray_t * +bitarray_init_zero(unsigned int n_bits) +{ + /* round up to the next int. */ + size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; + return xzalloc(sz*sizeof(unsigned int)); +} +/** Expand ba from holding n_bits_old to n_bits_new, + * clearing all new bits. Returns a possibly changed pointer to the + * bitarray. */ +static inline bitarray_t * +bitarray_expand(bitarray_t *ba, + unsigned int n_bits_old, unsigned int n_bits_new) +{ + size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT; + size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT; + char *ptr; + if (sz_new <= sz_old) + return ba; + ptr = xrealloc(ba, sz_new*sizeof(unsigned int)); + /* This memset does nothing to the older excess bytes. But they were + * already set to 0 by bitarry_init_zero. */ + memset(ptr+sz_old*sizeof(unsigned int), 0, + (sz_new-sz_old)*sizeof(unsigned int)); + return (bitarray_t*) ptr; +} +/** Free the bit array ba. */ +static inline void +bitarray_free(bitarray_t *ba) +{ + free(ba); +} +/** Set the bitth bit in b to 1. */ +static inline void +bitarray_set(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); +} +/** Set the bitth bit in b to 0. */ +static inline void +bitarray_clear(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); +} +/** Return true iff bitth bit in b is nonzero. NOTE: does + * not necessarily return 1 on true. */ +static inline unsigned int +bitarray_is_set(bitarray_t *b, int bit) +{ + return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); +} + +/** A set of digests, implemented as a Bloom filter. */ +typedef struct { + int mask; /**< One less than the number of bits in ba; always one less + * than a power of two. */ + bitarray_t *ba; /**< A bit array to implement the Bloom filter. */ +} digestset_t; + +#define BIT(n) ((n) & set->mask) +/** Add the digest digest to set. */ +static inline void +digestset_add(digestset_t *set, const char *digest) +{ + const uint32_t *p = (const uint32_t *)digest; + const uint32_t d1 = p[0] + (p[1]>>16); + const uint32_t d2 = p[1] + (p[2]>>16); + const uint32_t d3 = p[2] + (p[3]>>16); + const uint32_t d4 = p[3] + (p[0]>>16); + bitarray_set(set->ba, BIT(d1)); + bitarray_set(set->ba, BIT(d2)); + bitarray_set(set->ba, BIT(d3)); + bitarray_set(set->ba, BIT(d4)); +} + +/** If digest is in set, return nonzero. Otherwise, + * probably return zero. */ +static inline int +digestset_isin(const digestset_t *set, const char *digest) +{ + const uint32_t *p = (const uint32_t *)digest; + const uint32_t d1 = p[0] + (p[1]>>16); + const uint32_t d2 = p[1] + (p[2]>>16); + const uint32_t d3 = p[2] + (p[3]>>16); + const uint32_t d4 = p[3] + (p[0]>>16); + return bitarray_is_set(set->ba, BIT(d1)) && + bitarray_is_set(set->ba, BIT(d2)) && + bitarray_is_set(set->ba, BIT(d3)) && + bitarray_is_set(set->ba, BIT(d4)); +} +#undef BIT + +digestset_t *digestset_new(int max_elements); +void digestset_free(digestset_t* set); + +/* These functions, given an array of n_elements, return the + * nth lowest element. nth=0 gives the lowest element; + * n_elements-1 gives the highest; and (n_elements-1) / 2 gives + * the median. As a side effect, the elements of array are sorted. */ +int find_nth_int(int *array, int n_elements, int nth); +time_t find_nth_time(time_t *array, int n_elements, int nth); +double find_nth_double(double *array, int n_elements, int nth); +int32_t find_nth_int32(int32_t *array, int n_elements, int nth); +uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth); +long find_nth_long(long *array, int n_elements, int nth); +static inline int +median_int(int *array, int n_elements) +{ + return find_nth_int(array, n_elements, (n_elements-1)/2); +} +static inline time_t +median_time(time_t *array, int n_elements) +{ + return find_nth_time(array, n_elements, (n_elements-1)/2); +} +static inline double +median_double(double *array, int n_elements) +{ + return find_nth_double(array, n_elements, (n_elements-1)/2); +} +static inline uint32_t +median_uint32(uint32_t *array, int n_elements) +{ + return find_nth_uint32(array, n_elements, (n_elements-1)/2); +} +static inline int32_t +median_int32(int32_t *array, int n_elements) +{ + return find_nth_int32(array, n_elements, (n_elements-1)/2); +} +static inline long +median_long(long *array, int n_elements) +{ + return find_nth_long(array, n_elements, (n_elements-1)/2); +} + +#endif diff --git a/src/crypt.c b/src/crypt.c index e28e061..98516e6 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -211,3 +211,27 @@ random_bytes(uchar *buf, size_t buflen) { return RAND_bytes(buf, buflen) == 1 ? 0 : -1; } + + +/** Return a pseudorandom integer, chosen uniformly from the values + * between 0 and max-1 inclusive. max must be between 1 and + * INT_MAX+1, inclusive. */ +int +random_int(unsigned int max) +{ + unsigned int val; + unsigned int cutoff; + obfs_assert(max <= ((unsigned int)INT_MAX)+1); + obfs_assert(max > 0); /* don't div by 0 */ + + /* We ignore any values that are >= 'cutoff,' to avoid biasing the + * distribution with clipping at the upper end of unsigned int's + * range. + */ + cutoff = UINT_MAX - (UINT_MAX%max); + while (1) { + random_bytes((uchar*)&val, sizeof(val)); + if (val < cutoff) + return val % max; + } +} diff --git a/src/crypt.h b/src/crypt.h index 3f1e4df..beccda6 100644 --- a/src/crypt.h +++ b/src/crypt.h @@ -45,6 +45,11 @@ void crypt_free(crypt_t *); /** Set b to contain n random bytes. */ int random_bytes(uchar *b, size_t n); +/** Return a random integer in the range [0, max). + * 'max' must be between 1 and INT_MAX+1, inclusive. + */ +int random_int(unsigned int max); + #ifdef CRYPT_PRIVATE #include <openssl/aes.h> diff --git a/src/ht.h b/src/ht.h new file mode 100644 index 0000000..8c45db1 --- /dev/null +++ b/src/ht.h @@ -0,0 +1,471 @@ +/* Copyright (c) 2002, Christopher Clark. + * Copyright (c) 2005-2006, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See license at end. */ + +/* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ + +#ifndef HT_H +#define HT_H + +#define HT_HEAD(name, type) \ + struct name { \ + /* The hash table itself. */ \ + struct type **hth_table; \ + /* How long is the hash table? */ \ + unsigned hth_table_length; \ + /* How many elements does the table contain? */ \ + unsigned hth_n_entries; \ + /* How many elements will we allow in the table before resizing it? */ \ + unsigned hth_load_limit; \ + /* Position of hth_table_length in the primes table. */ \ + int hth_prime_idx; \ + } + +#define HT_INITIALIZER() \ + { NULL, 0, 0, 0, -1 } + +#define HT_ENTRY(type) \ + struct { \ + struct type *hte_next; \ + unsigned hte_hash; \ + } + +#define HT_EMPTY(head) \ + ((head)->hth_n_entries == 0) + +/* Helper: alias for the bucket containing 'elm'. */ +#define _HT_BUCKET(head, field, elm) \ + ((head)->hth_table[elm->field.hte_hash % head->hth_table_length]) + +/* How many elements in 'head'? */ +#define HT_SIZE(head) \ + ((head)->hth_n_entries) + +/* Return memory usage for a hashtable (not counting the entries themselves) */ +#define HT_MEM_USAGE(head) \ + (sizeof(*head) + (head)->hth_table_length * sizeof(void*)) + +#define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) +#define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) +#define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) +#define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) +#define HT_START(name, head) name##_HT_START(head) +#define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) +#define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) +#define HT_CLEAR(name, head) name##_HT_CLEAR(head) +#define HT_INIT(name, head) name##_HT_INIT(head) +/* Helper: */ +static inline unsigned +ht_improve_hash(unsigned h) +{ + /* Aim to protect against poor hash functions by adding logic here + * - logic taken from java 1.4 hashtable source */ + h += ~(h << 9); + h ^= ((h >> 14) | (h << 18)); /* >>> */ + h += (h << 4); + h ^= ((h >> 10) | (h << 22)); /* >>> */ + return h; +} + +#if 0 +/** Basic string hash function, from Java standard String.hashCode(). */ +static inline unsigned +ht_string_hash(const char *s) +{ + unsigned h = 0; + int m = 1; + while (*s) { + h += ((signed char)*s++)*m; + m = (m<<5)-1; /* m *= 31 */ + } + return h; +} +#endif + +/** Basic string hash function, from Python's str.__hash__() */ +static inline unsigned +ht_string_hash(const char *s) +{ + unsigned h; + const unsigned char *cp = (const unsigned char *)s; + h = *cp << 7; + while (*cp) { + h = (1000003*h) ^ *cp++; + } + /* This conversion truncates the length of the string, but that's ok. */ + h ^= (unsigned)(cp-(const unsigned char*)s); + return h; +} + +#define _HT_SET_HASH(elm, field, hashfn) \ + (elm)->field.hte_hash = hashfn(elm) + +#define HT_FOREACH(x, name, head) \ + for ((x) = HT_START(name, head); \ + (x) != NULL; \ + (x) = HT_NEXT(name, head, x)) + +#define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ + int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ + void name##_HT_CLEAR(struct name *ht); \ + int _##name##_HT_REP_IS_BAD(const struct name *ht); \ + static inline void \ + name##_HT_INIT(struct name *head) { \ + head->hth_table_length = 0; \ + head->hth_table = NULL; \ + head->hth_n_entries = 0; \ + head->hth_load_limit = 0; \ + head->hth_prime_idx = -1; \ + } \ + /* Helper: returns a pointer to the right location in the table \ + * 'head' to find or insert the element 'elm'. */ \ + static inline struct type ** \ + _##name##_HT_FIND_P(struct name *head, struct type *elm) \ + { \ + struct type **p; \ + if (!head->hth_table) \ + return NULL; \ + p = &_HT_BUCKET(head, field, elm); \ + while (*p) { \ + if (eqfn(*p, elm)) \ + return p; \ + p = &(*p)->field.hte_next; \ + } \ + return p; \ + } \ + /* Return a pointer to the element in the table 'head' matching 'elm', \ + * or NULL if no such element exists */ \ + static inline struct type * \ + name##_HT_FIND(const struct name *head, struct type *elm) \ + { \ + struct type **p; \ + struct name *h = (struct name *) head; \ + _HT_SET_HASH(elm, field, hashfn); \ + p = _##name##_HT_FIND_P(h, elm); \ + return p ? *p : NULL; \ + } \ + /* Insert the element 'elm' into the table 'head'. Do not call this \ + * function if the table might already contain a matching element. */ \ + static inline void \ + name##_HT_INSERT(struct name *head, struct type *elm) \ + { \ + struct type **p; \ + if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ + name##_HT_GROW(head, head->hth_n_entries+1); \ + ++head->hth_n_entries; \ + _HT_SET_HASH(elm, field, hashfn); \ + p = &_HT_BUCKET(head, field, elm); \ + elm->field.hte_next = *p; \ + *p = elm; \ + } \ + /* Insert the element 'elm' into the table 'head'. If there already \ + * a matching element in the table, replace that element and return \ + * it. */ \ + static inline struct type * \ + name##_HT_REPLACE(struct name *head, struct type *elm) \ + { \ + struct type **p, *r; \ + if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ + name##_HT_GROW(head, head->hth_n_entries+1); \ + _HT_SET_HASH(elm, field, hashfn); \ + p = _##name##_HT_FIND_P(head, elm); \ + r = *p; \ + *p = elm; \ + if (r && (r!=elm)) { \ + elm->field.hte_next = r->field.hte_next; \ + r->field.hte_next = NULL; \ + return r; \ + } else { \ + ++head->hth_n_entries; \ + return NULL; \ + } \ + } \ + /* Remove any element matching 'elm' from the table 'head'. If such \ + * an element is found, return it; otherwise return NULL. */ \ + static inline struct type * \ + name##_HT_REMOVE(struct name *head, struct type *elm) \ + { \ + struct type **p, *r; \ + _HT_SET_HASH(elm, field, hashfn); \ + p = _##name##_HT_FIND_P(head,elm); \ + if (!p || !*p) \ + return NULL; \ + r = *p; \ + *p = r->field.hte_next; \ + r->field.hte_next = NULL; \ + --head->hth_n_entries; \ + return r; \ + } \ + /* Invoke the function 'fn' on every element of the table 'head', \ + * using 'data' as its second argument. If the function returns \ + * nonzero, remove the most recently examined element before invoking \ + * the function again. */ \ + static inline void \ + name##_HT_FOREACH_FN(struct name *head, \ + int (*fn)(struct type *, void *), \ + void *data) \ + { \ + unsigned idx; \ + int remove; \ + struct type **p, **nextp, *next; \ + if (!head->hth_table) \ + return; \ + for (idx=0; idx < head->hth_table_length; ++idx) { \ + p = &head->hth_table[idx]; \ + while (*p) { \ + nextp = &(*p)->field.hte_next; \ + next = *nextp; \ + remove = fn(*p, data); \ + if (remove) { \ + --head->hth_n_entries; \ + *p = next; \ + } else { \ + p = nextp; \ + } \ + } \ + } \ + } \ + /* Return a pointer to the first element in the table 'head', under \ + * an arbitrary order. This order is stable under remove operations, \ + * but not under others. If the table is empty, return NULL. */ \ + static inline struct type ** \ + name##_HT_START(struct name *head) \ + { \ + unsigned b = 0; \ + while (b < head->hth_table_length) { \ + if (head->hth_table[b]) \ + return &head->hth_table[b]; \ + ++b; \ + } \ + return NULL; \ + } \ + /* Return the next element in 'head' after 'elm', under the arbitrary \ + * order used by HT_START. If there are no more elements, return \ + * NULL. If 'elm' is to be removed from the table, you must call \ + * this function for the next value before you remove it. \ + */ \ + static inline struct type ** \ + name##_HT_NEXT(struct name *head, struct type **elm) \ + { \ + if ((*elm)->field.hte_next) { \ + return &(*elm)->field.hte_next; \ + } else { \ + unsigned b = ((*elm)->field.hte_hash % head->hth_table_length)+1; \ + while (b < head->hth_table_length) { \ + if (head->hth_table[b]) \ + return &head->hth_table[b]; \ + ++b; \ + } \ + return NULL; \ + } \ + } \ + static inline struct type ** \ + name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ + { \ + unsigned h = (*elm)->field.hte_hash; \ + *elm = (*elm)->field.hte_next; \ + --head->hth_n_entries; \ + if (*elm) { \ + return elm; \ + } else { \ + unsigned b = (h % head->hth_table_length)+1; \ + while (b < head->hth_table_length) { \ + if (head->hth_table[b]) \ + return &head->hth_table[b]; \ + ++b; \ + } \ + return NULL; \ + } \ + } + +#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ + reallocfn, freefn) \ + static unsigned name##_PRIMES[] = { \ + 53, 97, 193, 389, \ + 769, 1543, 3079, 6151, \ + 12289, 24593, 49157, 98317, \ + 196613, 393241, 786433, 1572869, \ + 3145739, 6291469, 12582917, 25165843, \ + 50331653, 100663319, 201326611, 402653189, \ + 805306457, 1610612741 \ + }; \ + static unsigned name##_N_PRIMES = \ + (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \ + /* Expand the internal table of 'head' until it is large enough to \ + * hold 'size' elements. Return 0 on success, -1 on allocation \ + * failure. */ \ + int \ + name##_HT_GROW(struct name *head, unsigned size) \ + { \ + unsigned new_len, new_load_limit; \ + int prime_idx; \ + struct type **new_table; \ + if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \ + return 0; \ + if (head->hth_load_limit > size) \ + return 0; \ + prime_idx = head->hth_prime_idx; \ + do { \ + new_len = name##_PRIMES[++prime_idx]; \ + new_load_limit = (unsigned)(load*new_len); \ + } while (new_load_limit <= size && \ + prime_idx < (int)name##_N_PRIMES); \ + if ((new_table = mallocfn(new_len*sizeof(struct type*)))) { \ + unsigned b; \ + memset(new_table, 0, new_len*sizeof(struct type*)); \ + for (b = 0; b < head->hth_table_length; ++b) { \ + struct type *elm, *next; \ + unsigned b2; \ + elm = head->hth_table[b]; \ + while (elm) { \ + next = elm->field.hte_next; \ + b2 = elm->field.hte_hash % new_len; \ + elm->field.hte_next = new_table[b2]; \ + new_table[b2] = elm; \ + elm = next; \ + } \ + } \ + if (head->hth_table) \ + freefn(head->hth_table); \ + head->hth_table = new_table; \ + } else { \ + unsigned b, b2; \ + new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \ + if (!new_table) return -1; \ + memset(new_table + head->hth_table_length, 0, \ + (new_len - head->hth_table_length)*sizeof(struct type*)); \ + for (b=0; b < head->hth_table_length; ++b) { \ + struct type *e, **pE; \ + for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \ + b2 = e->field.hte_hash % new_len; \ + if (b2 == b) { \ + pE = &e->field.hte_next; \ + } else { \ + *pE = e->field.hte_next; \ + e->field.hte_next = new_table[b2]; \ + new_table[b2] = e; \ + } \ + } \ + } \ + head->hth_table = new_table; \ + } \ + head->hth_table_length = new_len; \ + head->hth_prime_idx = prime_idx; \ + head->hth_load_limit = new_load_limit; \ + return 0; \ + } \ + /* Free all storage held by 'head'. Does not free 'head' itself, or \ + * individual elements. */ \ + void \ + name##_HT_CLEAR(struct name *head) \ + { \ + if (head->hth_table) \ + freefn(head->hth_table); \ + head->hth_table_length = 0; \ + name##_HT_INIT(head); \ + } \ + /* Debugging helper: return false iff the representation of 'head' is \ + * internally consistent. */ \ + int \ + _##name##_HT_REP_IS_BAD(const struct name *head) \ + { \ + unsigned n, i; \ + struct type *elm; \ + if (!head->hth_table_length) { \ + if (!head->hth_table && !head->hth_n_entries && \ + !head->hth_load_limit && head->hth_prime_idx == -1) \ + return 0; \ + else \ + return 1; \ + } \ + if (!head->hth_table || head->hth_prime_idx < 0 || \ + !head->hth_load_limit) \ + return 2; \ + if (head->hth_n_entries > head->hth_load_limit) \ + return 3; \ + if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \ + return 4; \ + if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \ + return 5; \ + for (n = i = 0; i < head->hth_table_length; ++i) { \ + for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ + if (elm->field.hte_hash != hashfn(elm)) \ + return 1000 + i; \ + if ((elm->field.hte_hash % head->hth_table_length) != i) \ + return 10000 + i; \ + ++n; \ + } \ + } \ + if (n != head->hth_n_entries) \ + return 6; \ + return 0; \ + } + +/** Implements an over-optimized "find and insert if absent" block; + * not meant for direct usage by typical code, or usage outside the critical + * path.*/ +#define _HT_FIND_OR_INSERT(name, field, hashfn, head, eltype, elm, var, y, n) \ + { \ + struct name *_##var##_head = head; \ + eltype **var; \ + if (!_##var##_head->hth_table || \ + _##var##_head->hth_n_entries >= _##var##_head->hth_load_limit) \ + name##_HT_GROW(_##var##_head, _##var##_head->hth_n_entries+1); \ + _HT_SET_HASH((elm), field, hashfn); \ + var = _##name##_HT_FIND_P(_##var##_head, (elm)); \ + if (*var) { \ + y; \ + } else { \ + n; \ + } \ + } +#define _HT_FOI_INSERT(field, head, elm, newent, var) \ + { \ + newent->field.hte_hash = (elm)->field.hte_hash; \ + newent->field.hte_next = NULL; \ + *var = newent; \ + ++((head)->hth_n_entries); \ + } + +/* + * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code + * by Christopher Clark, retrofit to allow drop-in memory management, and to + * use the same interface as Niels Provos's HT_H. I'm not sure whether this + * is a derived work any more, but whether it is or not, the license below + * applies. + * + * Copyright (c) 2002, Christopher Clark + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * 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. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "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 COPYRIGHT OWNER + * OR CONTRIBUTORS 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. +*/ + +#endif + diff --git a/src/test/unittest.c b/src/test/unittest.c index 45757e9..8974c87 100644 --- a/src/test/unittest.c +++ b/src/test/unittest.c @@ -5,11 +5,13 @@ #include "tinytest.h" #include "../crypt.h" +extern struct testcase_t container_tests[]; extern struct testcase_t crypt_tests[]; extern struct testcase_t obfs2_tests[]; extern struct testcase_t socks_tests[]; struct testgroup_t groups[] = { + { "container/", container_tests }, { "crypt/", crypt_tests }, { "obfs2/", obfs2_tests }, { "socks/", socks_tests }, diff --git a/src/test/unittest_container.c b/src/test/unittest_container.c new file mode 100644 index 0000000..4731139 --- /dev/null +++ b/src/test/unittest_container.c @@ -0,0 +1,772 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "../util.h" +#include "tinytest_macros.h" + +#include "../container.h" +#include "../crypt.h" + +/** Helper: return a tristate based on comparing the strings in *a and + * *b. */ +static int +_compare_strs(const void **a, const void **b) +{ + const char *s1 = *a, *s2 = *b; + return strcmp(s1, s2); +} + +/** Helper: return a tristate based on comparing the strings in *a and + * *b, excluding a's first character, and ignoring case. */ +static int +_compare_without_first_ch(const void *a, const void **b) +{ + const char *s1 = a, *s2 = *b; + return strcasecmp(s1+1, s2); +} + +/** Run unit tests for basic dynamic-sized array functionality. */ +static void +test_container_smartlist_basic(void *unused) +{ + smartlist_t *sl; + + /* XXXX test sort_digests, uniq_strings, uniq_digests */ + + /* Test smartlist add, del_keeporder, insert, get. */ + sl = smartlist_create(); + smartlist_add(sl, (void*)1); + smartlist_add(sl, (void*)2); + smartlist_add(sl, (void*)3); + smartlist_add(sl, (void*)4); + smartlist_del_keeporder(sl, 1); + smartlist_insert(sl, 1, (void*)22); + smartlist_insert(sl, 0, (void*)0); + smartlist_insert(sl, 5, (void*)555); + tt_ptr_op(smartlist_get(sl,0), ==, (void*)0); + tt_ptr_op(smartlist_get(sl,1), ==, (void*)1); + tt_ptr_op(smartlist_get(sl,2), ==, (void*)22); + tt_ptr_op(smartlist_get(sl,3), ==, (void*)3); + tt_ptr_op(smartlist_get(sl,4), ==, (void*)4); + tt_ptr_op(smartlist_get(sl,5), ==, (void*)555); + /* Try deleting in the middle. */ + smartlist_del(sl, 1); + tt_ptr_op(smartlist_get(sl, 1), ==, (void*)555); + /* Try deleting at the end. */ + smartlist_del(sl, 4); + tt_int_op(smartlist_len(sl), ==, 4); + + /* test isin. */ + tt_assert(smartlist_isin(sl, (void*)3)); + tt_assert(!smartlist_isin(sl, (void*)99)); + + end: + smartlist_free(sl); +} + +/** Run unit tests for smartlist-of-strings functionality. */ +static void +test_container_smartlist_strings(void *unused) +{ + smartlist_t *sl = smartlist_create(); + char *cp=NULL, *cp_alloc=NULL; + size_t sz; + + /* Test split and join */ + tt_int_op(smartlist_len(sl), ==, 0); + smartlist_split_string(sl, "abc", ":", 0, 0); + tt_int_op(smartlist_len(sl), ==, 1); + tt_str_op(smartlist_get(sl, 0), ==, "abc"); + smartlist_split_string(sl, "a::bc::", "::", 0, 0); + tt_int_op(smartlist_len(sl), ==, 4); + tt_str_op(smartlist_get(sl, 1), ==, "a"); + tt_str_op(smartlist_get(sl, 2), ==, "bc"); + tt_str_op(smartlist_get(sl, 3), ==, ""); + cp_alloc = smartlist_join_strings(sl, "", 0, NULL); + tt_str_op(cp_alloc, ==, "abcabc"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "!", 0, NULL); + tt_str_op(cp_alloc, ==, "abc!a!bc!"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL); + tt_str_op(cp_alloc, ==, "abcXYaXYbcXY"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL); + tt_str_op(cp_alloc, ==, "abcXYaXYbcXYXY"); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "", 1, NULL); + tt_str_op(cp_alloc, ==, "abcabc"); + free(cp_alloc); + + smartlist_split_string(sl, "/def/ /ghijk", "/", 0, 0); + tt_int_op(smartlist_len(sl), ==, 8); + tt_str_op(smartlist_get(sl, 4), ==, ""); + tt_str_op(smartlist_get(sl, 5), ==, "def"); + tt_str_op(smartlist_get(sl, 6), ==, " "); + tt_str_op(smartlist_get(sl, 7), ==, "ghijk"); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0); + tt_int_op(smartlist_len(sl), ==, 3); + tt_str_op(smartlist_get(sl,0), ==, "a"); + tt_str_op(smartlist_get(sl,1), ==, "bbd"); + tt_str_op(smartlist_get(sl,2), ==, "cdef"); + smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>", + SPLIT_SKIP_SPACE, 0); + tt_int_op(smartlist_len(sl), ==, 8); + tt_str_op(smartlist_get(sl,3), ==, "z"); + tt_str_op(smartlist_get(sl,4), ==, "zhasd"); + tt_str_op(smartlist_get(sl,5), ==, ""); + tt_str_op(smartlist_get(sl,6), ==, "bnud"); + tt_str_op(smartlist_get(sl,7), ==, ""); + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + smartlist_split_string(sl, " ab\tc \td ef ", NULL, + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 4); + tt_str_op(smartlist_get(sl,0), ==, "ab"); + tt_str_op(smartlist_get(sl,1), ==, "c"); + tt_str_op(smartlist_get(sl,2), ==, "d"); + tt_str_op(smartlist_get(sl,3), ==, "ef"); + smartlist_split_string(sl, "ghi\tj", NULL, + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 6); + tt_str_op(smartlist_get(sl,4), ==, "ghi"); + tt_str_op(smartlist_get(sl,5), ==, "j"); + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL); + tt_str_op(cp_alloc, ==, ""); + free(cp_alloc); + cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL); + tt_str_op(cp_alloc, ==, "XY"); + free(cp_alloc); + + smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 3); + tt_str_op(smartlist_get(sl, 0), ==, "z"); + tt_str_op(smartlist_get(sl, 1), ==, "zhasd"); + tt_str_op(smartlist_get(sl, 2), ==, "bnud"); + smartlist_split_string(sl, " z <> zhasd <> <> bnud<> ", "<>", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2); + tt_int_op(smartlist_len(sl), ==, 5); + tt_str_op(smartlist_get(sl, 3), ==, "z"); + tt_str_op(smartlist_get(sl, 4), ==, "zhasd <> <> bnud<>"); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + smartlist_split_string(sl, "abcd\n", "\n", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 1); + tt_str_op(smartlist_get(sl, 0), ==, "abcd"); + smartlist_split_string(sl, "efgh", "\n", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + tt_int_op(smartlist_len(sl), ==, 2); + tt_str_op(smartlist_get(sl, 1), ==, "efgh"); + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + /* Test swapping, shuffling, and sorting. */ + smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0); + tt_int_op(smartlist_len(sl), ==, 7); + smartlist_sort(sl, _compare_strs); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "and,arma,by,nickm,onion,router,the"); + free(cp_alloc); + smartlist_swap(sl, 1, 5); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "and,router,by,nickm,onion,arma,the"); + free(cp_alloc); + smartlist_shuffle(sl); + tt_int_op(smartlist_len(sl), ==, 7); + tt_assert(smartlist_string_isin(sl, "and")); + tt_assert(smartlist_string_isin(sl, "router")); + tt_assert(smartlist_string_isin(sl, "by")); + tt_assert(smartlist_string_isin(sl, "nickm")); + tt_assert(smartlist_string_isin(sl, "onion")); + tt_assert(smartlist_string_isin(sl, "arma")); + tt_assert(smartlist_string_isin(sl, "the")); + + /* Test bsearch. */ + smartlist_sort(sl, _compare_strs); + tt_str_op(smartlist_bsearch(sl, "zNicKM", + _compare_without_first_ch), ==, "nickm"); + tt_str_op(smartlist_bsearch(sl, " AND", _compare_without_first_ch), ==, "and"); + tt_ptr_op(smartlist_bsearch(sl, " ANz", _compare_without_first_ch), ==, NULL); + + /* Test bsearch_idx */ + { + int f; + tt_int_op(smartlist_bsearch_idx(sl," aaa",_compare_without_first_ch,&f), + ==, 0); + tt_int_op(f, ==, 0); + tt_int_op(smartlist_bsearch_idx(sl," and",_compare_without_first_ch,&f), + ==, 0); + tt_int_op(f, ==, 1); + tt_int_op(smartlist_bsearch_idx(sl," arm",_compare_without_first_ch,&f), + ==, 1); + tt_int_op(f, ==, 0); + tt_int_op(smartlist_bsearch_idx(sl," arma",_compare_without_first_ch,&f), + ==, 1); + tt_int_op(f, ==, 1); + tt_int_op(smartlist_bsearch_idx(sl," armb",_compare_without_first_ch,&f), + ==, 2); + tt_int_op(f, ==, 0); + tt_int_op(smartlist_bsearch_idx(sl," zzzz",_compare_without_first_ch,&f), + ==, 7); + tt_int_op(f, ==, 0); + } + + /* Test reverse() and pop_last() */ + smartlist_reverse(sl); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "the,router,onion,nickm,by,arma,and"); + free(cp_alloc); + cp_alloc = smartlist_pop_last(sl); + tt_str_op(cp_alloc, ==, "and"); + free(cp_alloc); + tt_int_op(smartlist_len(sl), ==, 6); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + cp_alloc = smartlist_pop_last(sl); + tt_ptr_op(cp_alloc, ==, NULL); + + /* Test uniq() */ + smartlist_split_string(sl, + "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50", + ",", 0, 0); + smartlist_sort(sl, _compare_strs); + smartlist_uniq(sl, _compare_strs, free); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "50,a,canal,man,noon,panama,plan,radar"); + free(cp_alloc); + + /* Test string_isin and isin_case and num_isin */ + tt_assert(smartlist_string_isin(sl, "noon")); + tt_assert(!smartlist_string_isin(sl, "noonoon")); + tt_assert(smartlist_string_isin_case(sl, "nOOn")); + tt_assert(!smartlist_string_isin_case(sl, "nooNooN")); + tt_assert(smartlist_string_num_isin(sl, 50)); + tt_assert(!smartlist_string_num_isin(sl, 60)); + + /* Test smartlist_choose */ + { + int i; + int allsame = 1; + int allin = 1; + void *first = smartlist_choose(sl); + tt_assert(smartlist_isin(sl, first)); + for (i = 0; i < 100; ++i) { + void *second = smartlist_choose(sl); + if (second != first) + allsame = 0; + if (!smartlist_isin(sl, second)) + allin = 0; + } + tt_assert(!allsame); + tt_assert(allin); + } + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_clear(sl); + + /* Test string_remove and remove and join_strings2 */ + smartlist_split_string(sl, + "Some say the Earth will end in ice and some in fire", + " ", 0, 0); + cp = smartlist_get(sl, 4); + tt_str_op(cp, ==, "will"); + smartlist_add(sl, cp); + smartlist_remove(sl, cp); + free(cp); + cp_alloc = smartlist_join_strings(sl, ",", 0, NULL); + tt_str_op(cp_alloc, ==, "Some,say,the,Earth,fire,end,in,ice,and,some,in"); + free(cp_alloc); + smartlist_string_remove(sl, "in"); + cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz); + tt_str_op(cp_alloc, ==, "Some+say+the+Earth+fire+end+some+ice+and"); + tt_int_op((int)sz, ==, 40); + + end: + + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_free(sl); + free(cp_alloc); +} + +/** Run unit tests for smartlist set manipulation functions. */ +static void +test_container_smartlist_overlap(void *unused) +{ + smartlist_t *sl = smartlist_create(); + smartlist_t *ints = smartlist_create(); + smartlist_t *odds = smartlist_create(); + smartlist_t *evens = smartlist_create(); + smartlist_t *primes = smartlist_create(); + int i; + for (i=1; i < 10; i += 2) + smartlist_add(odds, (void*)(uintptr_t)i); + for (i=0; i < 10; i += 2) + smartlist_add(evens, (void*)(uintptr_t)i); + + /* add_all */ + smartlist_add_all(ints, odds); + smartlist_add_all(ints, evens); + tt_int_op(smartlist_len(ints), ==, 10); + + smartlist_add(primes, (void*)2); + smartlist_add(primes, (void*)3); + smartlist_add(primes, (void*)5); + smartlist_add(primes, (void*)7); + + /* overlap */ + tt_assert(smartlist_overlap(ints, odds)); + tt_assert(smartlist_overlap(odds, primes)); + tt_assert(smartlist_overlap(evens, primes)); + tt_assert(!smartlist_overlap(odds, evens)); + + /* intersect */ + smartlist_add_all(sl, odds); + smartlist_intersect(sl, primes); + tt_int_op(smartlist_len(sl), ==, 3); + tt_assert(smartlist_isin(sl, (void*)3)); + tt_assert(smartlist_isin(sl, (void*)5)); + tt_assert(smartlist_isin(sl, (void*)7)); + + /* subtract */ + smartlist_add_all(sl, primes); + smartlist_subtract(sl, odds); + tt_int_op(smartlist_len(sl), ==, 1); + tt_assert(smartlist_isin(sl, (void*)2)); + + end: + smartlist_free(odds); + smartlist_free(evens); + smartlist_free(ints); + smartlist_free(primes); + smartlist_free(sl); +} + +/** Run unit tests for smartlist-of-digests functions. */ +static void +test_container_smartlist_digests(void *unused) +{ + smartlist_t *sl = smartlist_create(); + + /* digest_isin. */ + smartlist_add(sl, xmemdup("AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH)); + smartlist_add(sl, xmemdup("\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH)); + smartlist_add(sl, xmemdup("\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH)); + tt_int_op(smartlist_digest_isin(NULL, "AAAAAAAAAAAAAAAAAAAA"), ==, 0); + tt_assert(smartlist_digest_isin(sl, "AAAAAAAAAAAAAAAAAAAA")); + tt_assert(smartlist_digest_isin(sl, "\00090AAB2AAAAaasdAAAAA")); + tt_int_op(smartlist_digest_isin(sl, "\00090AAB2AAABaasdAAAAA"), ==, 0); + + /* sort digests */ + smartlist_sort_digests(sl); + tt_mem_op(smartlist_get(sl, 0), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH); + tt_mem_op(smartlist_get(sl, 1), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH); + tt_mem_op(smartlist_get(sl, 2), ==, "AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH); + tt_int_op(smartlist_len(sl), ==, 3); + + /* uniq_digests */ + smartlist_uniq_digests(sl); + tt_int_op(smartlist_len(sl), ==, 2); + tt_mem_op(smartlist_get(sl, 0), ==, "\00090AAB2AAAAaasdAAAAA", SHA256_LENGTH); + tt_mem_op(smartlist_get(sl, 1), ==, "AAAAAAAAAAAAAAAAAAAA", SHA256_LENGTH); + + end: + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_free(sl); +} + +/** Run unit tests for concatenate-a-smartlist-of-strings functions. */ +static void +test_container_smartlist_join(void *unused) +{ + smartlist_t *sl = smartlist_create(); + smartlist_t *sl2 = smartlist_create(), *sl3 = smartlist_create(), + *sl4 = smartlist_create(); + char *joined=NULL; + /* unique, sorted. */ + smartlist_split_string(sl, + "Abashments Ambush Anchorman Bacon Banks Borscht " + "Bunks Inhumane Insurance Knish Know Manners " + "Maraschinos Stamina Sunbonnets Unicorns Wombats", + " ", 0, 0); + /* non-unique, sorted. */ + smartlist_split_string(sl2, + "Ambush Anchorman Anchorman Anemias Anemias Bacon " + "Crossbowmen Inhumane Insurance Knish Know Manners " + "Manners Maraschinos Wombats Wombats Work", + " ", 0, 0); + SMARTLIST_FOREACH_JOIN(sl, char *, cp1, + sl2, char *, cp2, + strcmp(cp1,cp2), + smartlist_add(sl3, cp2)) { + tt_str_op(cp1, ==, cp2); + smartlist_add(sl4, cp1); + } SMARTLIST_FOREACH_JOIN_END(cp1, cp2); + + SMARTLIST_FOREACH(sl3, const char *, cp, + tt_assert(smartlist_isin(sl2, cp) && + !smartlist_string_isin(sl, cp))); + SMARTLIST_FOREACH(sl4, const char *, cp, + tt_assert(smartlist_isin(sl, cp) && + smartlist_string_isin(sl2, cp))); + joined = smartlist_join_strings(sl3, ",", 0, NULL); + tt_str_op(joined, ==, "Anemias,Anemias,Crossbowmen,Work"); + free(joined); + joined = smartlist_join_strings(sl4, ",", 0, NULL); + tt_str_op(joined, ==, + "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance," + "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats"); + + end: + smartlist_free(sl4); + smartlist_free(sl3); + SMARTLIST_FOREACH(sl2, char *, cp, free(cp)); + smartlist_free(sl2); + SMARTLIST_FOREACH(sl, char *, cp, free(cp)); + smartlist_free(sl); + free(joined); +} + +/** Run unit tests for bitarray code */ +static void +test_container_bitarray(void *unused) +{ + bitarray_t *ba = NULL; + int i, j; + + ba = bitarray_init_zero(1); + tt_assert(ba); + tt_assert(! bitarray_is_set(ba, 0)); + bitarray_set(ba, 0); + tt_assert(bitarray_is_set(ba, 0)); + bitarray_clear(ba, 0); + tt_assert(! bitarray_is_set(ba, 0)); + bitarray_free(ba); + + ba = bitarray_init_zero(1023); + for (i = 1; i < 64; ) { + for (j = 0; j < 1023; ++j) { + if (j % i) + bitarray_set(ba, j); + else + bitarray_clear(ba, j); + } + for (j = 0; j < 1023; ++j) { + tt_bool_op(bitarray_is_set(ba, j), ==, j%i); + } + + if (i < 7) + ++i; + else if (i == 28) + i = 32; + else + i += 7; + } + + end: + if (ba) + bitarray_free(ba); +} + +/** Run unit tests for digest set code (implemented as a hashtable or as a + * bloom filter) */ +static void +test_container_digestset(void *unused) +{ + smartlist_t *included = smartlist_create(); + char d[SHA256_LENGTH]; + int i; + int ok = 1; + int false_positives = 0; + digestset_t *set = NULL; + + for (i = 0; i < 1000; ++i) { + random_bytes((uchar *)d, SHA256_LENGTH); + smartlist_add(included, xmemdup(d, SHA256_LENGTH)); + } + set = digestset_new(1000); + SMARTLIST_FOREACH(included, const char *, cp, + if (digestset_isin(set, cp)) + ok = 0); + tt_assert(ok); + SMARTLIST_FOREACH(included, const char *, cp, + digestset_add(set, cp)); + SMARTLIST_FOREACH(included, const char *, cp, + if (!digestset_isin(set, cp)) + ok = 0); + tt_assert(ok); + for (i = 0; i < 1000; ++i) { + random_bytes((uchar *)d, SHA256_LENGTH); + if (digestset_isin(set, d)) + ++false_positives; + } + tt_assert(false_positives < 50); /* Should be far lower. */ + + end: + if (set) + digestset_free(set); + SMARTLIST_FOREACH(included, char *, cp, free(cp)); + smartlist_free(included); +} + +typedef struct pq_entry_t { + const char *val; + int idx; +} pq_entry_t; + +/** Helper: return a tristate based on comparing two pq_entry_t values. */ +static int +_compare_strings_for_pqueue(const void *p1, const void *p2) +{ + const pq_entry_t *e1=p1, *e2=p2; + return strcmp(e1->val, e2->val); +} + +/** Run unit tests for heap-based priority queue functions. */ +static void +test_container_pqueue(void *unused) +{ + smartlist_t *sl = smartlist_create(); + int (*cmp)(const void *, const void*); + const int offset = offsetof(pq_entry_t, idx); +#define ENTRY(s) pq_entry_t s = { #s, -1 } + ENTRY(cows); + ENTRY(zebras); + ENTRY(fish); + ENTRY(frogs); + ENTRY(apples); + ENTRY(squid); + ENTRY(daschunds); + ENTRY(eggplants); + ENTRY(weissbier); + ENTRY(lobsters); + ENTRY(roquefort); + ENTRY(chinchillas); + ENTRY(fireflies); + +#define OK() smartlist_pqueue_assert_ok(sl, cmp, offset) + + cmp = _compare_strings_for_pqueue; + smartlist_pqueue_add(sl, cmp, offset, &cows); + smartlist_pqueue_add(sl, cmp, offset, &zebras); + smartlist_pqueue_add(sl, cmp, offset, &fish); + smartlist_pqueue_add(sl, cmp, offset, &frogs); + smartlist_pqueue_add(sl, cmp, offset, &apples); + smartlist_pqueue_add(sl, cmp, offset, &squid); + smartlist_pqueue_add(sl, cmp, offset, &daschunds); + smartlist_pqueue_add(sl, cmp, offset, &eggplants); + smartlist_pqueue_add(sl, cmp, offset, &weissbier); + smartlist_pqueue_add(sl, cmp, offset, &lobsters); + smartlist_pqueue_add(sl, cmp, offset, &roquefort); + + OK(); + + tt_int_op(smartlist_len(sl), ==, 11); + tt_ptr_op(smartlist_get(sl, 0), ==, &apples); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &apples); + tt_int_op(smartlist_len(sl), ==, 10); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &cows); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &daschunds); + smartlist_pqueue_add(sl, cmp, offset, &chinchillas); + OK(); + smartlist_pqueue_add(sl, cmp, offset, &fireflies); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &chinchillas); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &eggplants); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fireflies); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fish); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &frogs); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &lobsters); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &roquefort); + OK(); + tt_int_op(smartlist_len(sl), ==, 3); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &squid); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &weissbier); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &zebras); + tt_int_op(smartlist_len(sl), ==, 0); + OK(); + + /* Now test remove. */ + smartlist_pqueue_add(sl, cmp, offset, &cows); + smartlist_pqueue_add(sl, cmp, offset, &fish); + smartlist_pqueue_add(sl, cmp, offset, &frogs); + smartlist_pqueue_add(sl, cmp, offset, &apples); + smartlist_pqueue_add(sl, cmp, offset, &squid); + smartlist_pqueue_add(sl, cmp, offset, &zebras); + tt_int_op(smartlist_len(sl), ==, 6); + OK(); + smartlist_pqueue_remove(sl, cmp, offset, &zebras); + tt_int_op(smartlist_len(sl), ==, 5); + OK(); + smartlist_pqueue_remove(sl, cmp, offset, &cows); + tt_int_op(smartlist_len(sl), ==, 4); + OK(); + smartlist_pqueue_remove(sl, cmp, offset, &apples); + tt_int_op(smartlist_len(sl), ==, 3); + OK(); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &fish); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &frogs); + tt_ptr_op(smartlist_pqueue_pop(sl, cmp, offset), ==, &squid); + tt_int_op(smartlist_len(sl), ==, 0); + OK(); + +#undef OK + + end: + + smartlist_free(sl); +} + +/** Run unit tests for string-to-void* map functions */ +static void +test_container_strmap(void *unused) +{ + strmap_t *map; + strmap_iter_t *iter; + const char *k; + void *v; + char *visited = NULL; + smartlist_t *found_keys = NULL; + + map = strmap_new(); + tt_assert(map); + tt_int_op(strmap_size(map), ==, 0); + tt_assert(strmap_isempty(map)); + v = strmap_set(map, "K1", (void*)99); + tt_ptr_op(v, ==, NULL); + tt_assert(!strmap_isempty(map)); + v = strmap_set(map, "K2", (void*)101); + tt_ptr_op(v, ==, NULL); + v = strmap_set(map, "K1", (void*)100); + tt_int_op((void*)99, ==, v); + tt_ptr_op(strmap_get(map, "K1"), ==, (void*)100); + tt_ptr_op(strmap_get(map, "K2"), ==, (void*)101); + tt_ptr_op(strmap_get(map, "K-not-there"), ==, NULL); + strmap_assert_ok(map); + + v = strmap_remove(map,"K2"); + strmap_assert_ok(map); + tt_ptr_op(v, ==, (void*)101); + tt_ptr_op(strmap_get(map, "K2"), ==, NULL); + tt_ptr_op(strmap_remove(map, "K2"), ==, NULL); + + strmap_set(map, "K2", (void*)101); + strmap_set(map, "K3", (void*)102); + strmap_set(map, "K4", (void*)103); + tt_int_op(strmap_size(map), ==, 4); + strmap_assert_ok(map); + strmap_set(map, "K5", (void*)104); + strmap_set(map, "K6", (void*)105); + strmap_assert_ok(map); + + /* Test iterator. */ + iter = strmap_iter_init(map); + found_keys = smartlist_create(); + while (!strmap_iter_done(iter)) { + strmap_iter_get(iter,&k,&v); + smartlist_add(found_keys, xstrdup(k)); + tt_ptr_op(v, ==, strmap_get(map, k)); + + if (!strcmp(k, "K2")) { + iter = strmap_iter_next_rmv(map,iter); + } else { + iter = strmap_iter_next(map,iter); + } + } + + /* Make sure we removed K2, but not the others. */ + tt_ptr_op(strmap_get(map, "K2"), ==, NULL); + tt_ptr_op(strmap_get(map, "K5"), ==, (void*)104); + /* Make sure we visited everyone once */ + smartlist_sort_strings(found_keys); + visited = smartlist_join_strings(found_keys, ":", 0, NULL); + tt_str_op(visited, ==, "K1:K2:K3:K4:K5:K6"); + + strmap_assert_ok(map); + /* Clean up after ourselves. */ + strmap_free(map, NULL); + map = NULL; + + /* Now try some lc functions. */ + map = strmap_new(); + strmap_set_lc(map,"Ab.C", (void*)1); + tt_ptr_op(strmap_get(map, "ab.c"), ==, (void*)1); + strmap_assert_ok(map); + tt_ptr_op(strmap_get_lc(map, "AB.C"), ==, (void*)1); + tt_ptr_op(strmap_get(map, "AB.C"), ==, NULL); + tt_ptr_op(strmap_remove_lc(map, "aB.C"), ==, (void*)1); + strmap_assert_ok(map); + tt_ptr_op(strmap_get_lc(map, "AB.C"), ==, NULL); + + end: + if (map) + strmap_free(map,NULL); + if (found_keys) { + SMARTLIST_FOREACH(found_keys, char *, cp, free(cp)); + smartlist_free(found_keys); + } + free(visited); +} + +/** Run unit tests for getting the median of a list. */ +static void +test_container_order_functions(void *unused) +{ + int lst[25], n = 0; + // int a=12,b=24,c=25,d=60,e=77; + +#define median() median_int(lst, n) + + lst[n++] = 12; + tt_int_op(median(), ==, 12); /* 12 */ + lst[n++] = 77; + //smartlist_shuffle(sl); + tt_int_op(median(), ==, 12); /* 12, 77 */ + lst[n++] = 77; + //smartlist_shuffle(sl); + tt_int_op(median(), ==, 77); /* 12, 77, 77 */ + lst[n++] = 24; + tt_int_op(median(), ==, 24); /* 12,24,77,77 */ + lst[n++] = 60; + lst[n++] = 12; + lst[n++] = 25; + //smartlist_shuffle(sl); + tt_int_op(median(), ==, 25); /* 12,12,24,25,60,77,77 */ +#undef median + + end: + ; +} + +#define T(name) \ + { #name, test_container_##name, 0, NULL, NULL } + +struct testcase_t container_tests[] = { + T(smartlist_basic), + T(smartlist_strings), + T(smartlist_overlap), + T(smartlist_digests), + T(smartlist_join), + T(bitarray), + T(digestset), + T(strmap), + T(pqueue), + T(order_functions), + END_OF_TESTCASES +}; + diff --git a/src/util.c b/src/util.c index 231c3a8..9b9fa48 100644 --- a/src/util.c +++ b/src/util.c @@ -88,6 +88,55 @@ xstrdup(const char *s) return xmemdup(s, strlen(s) + 1); } +char * +xstrndup(const char *s, size_t maxsize) +{ + char *copy; + size_t size; + /* strnlen is not in any standard :-( */ + for (size = 0; size < maxsize; size++) + if (s[size] == '\0') + break; + + copy = xmalloc(size + 1); + memcpy(copy, s, size); + copy[size] = '\0'; + return copy; +} + +/******************************** Mathematics ********************************/ + +unsigned int +ui64_log2(uint64_t u64) +{ + unsigned int r = 0; + if (u64 >= (((uint64_t)1)<<32)) { + u64 >>= 32; + r = 32; + } + if (u64 >= (((uint64_t)1)<<16)) { + u64 >>= 16; + r += 16; + } + if (u64 >= (((uint64_t)1)<<8)) { + u64 >>= 8; + r += 8; + } + if (u64 >= (((uint64_t)1)<<4)) { + u64 >>= 4; + r += 4; + } + if (u64 >= (((uint64_t)1)<<2)) { + u64 >>= 2; + r += 2; + } + if (u64 >= (((uint64_t)1)<<1)) { + u64 >>= 1; + r += 1; + } + return r; +} + /************************ Obfsproxy Network Routines *************************/ /** @@ -206,6 +255,31 @@ obfs_vsnprintf(char *str, size_t size, const char *format, va_list args) return -1; return r; } +/** Remove from the string s every character which appears in + * strip. */ +void +ascii_strstrip(char *s, const char *strip) +{ + char *read = s; + while (*read) { + if (strchr(strip, *read)) { + ++read; + } else { + *s++ = *read++; + } + } + *s = '\0'; +} + +void +ascii_strlower(char *s) +{ + while (*s) { + if (*s >= 'A' && *s <= 'Z') + *s = *s - 'A' + 'a'; + ++s; + } +} /************************ Doubly Linked List (DLL) ******************/ diff --git a/src/util.h b/src/util.h index d365cbc..e44a711 100644 --- a/src/util.h +++ b/src/util.h @@ -8,6 +8,7 @@ #include "config.h" #include <stdarg.h> /* for va_list */ #include <stddef.h> /* size_t, offsetof, NULL, etc */ +#include <stdint.h> /* intN_t, uintN_t */ #ifndef __GNUC__ #define __attribute__(x) /* nothing */ @@ -34,6 +35,11 @@ void *xzalloc(size_t size) ATTR_MALLOC; /* clears memory */ void *xrealloc(void *ptr, size_t size); void *xmemdup(const void *ptr, size_t size) ATTR_MALLOC; char *xstrdup(const char *s) ATTR_MALLOC; +char *xstrndup(const char *s, size_t maxsize) ATTR_MALLOC; + +/***** Math. *****/ + +unsigned int ui64_log2(uint64_t u64); /***** Network functions stuff. *****/ @@ -48,6 +54,18 @@ int init_evdns_base(struct event_base *base); /***** String functions stuff. *****/ +static inline int ascii_isspace(unsigned char c) +{ + return (c == ' ' || + c == '\t' || + c == '\r' || + c == '\n' || + c == '\v' || + c == '\f'); +} +void ascii_strstrip(char *s, const char *kill); +void ascii_strlower(char *s); + int obfs_vsnprintf(char *str, size_t size, const char *format, va_list args); int obfs_snprintf(char *str, size_t size, @@ -133,5 +151,4 @@ void log_debug(const char *format, ...) log_error("aborted at %s:%d", __FILE__, __LINE__); \ } while (0) - #endif

1 0

[obfsproxy/master] Fix a memory leak in obfs2.c:derive_padding_key (and be scrupulous about tearing down everything at shutdown time, too)
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit d4c299eeb58772fa9a76b8195ba8b803988f9938 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 11:08:52 2011 -0700 Fix a memory leak in obfs2.c:derive_padding_key (and be scrupulous about tearing down everything at shutdown time, too) --- src/crypt.c | 4 ++-- src/main.c | 19 +++++++++++++++++-- src/protocols/obfs2.c | 10 ++-------- 3 files changed, 21 insertions(+), 12 deletions(-) diff --git a/src/crypt.c b/src/crypt.c index 98516e6..e338214 100644 --- a/src/crypt.c +++ b/src/crypt.c @@ -26,7 +26,7 @@ #endif /** - Initializes the obfs2 crypto subsystem. + Initializes the crypto subsystem. */ int initialize_crypto(void) @@ -58,7 +58,7 @@ initialize_crypto(void) } /** - Cleans up the obfs2 crypto subsystem. + Cleans up the crypto subsystem. */ void cleanup_crypto(void) diff --git a/src/main.c b/src/main.c index cf811fa..254be94 100644 --- a/src/main.c +++ b/src/main.c @@ -4,6 +4,7 @@ #include "util.h" +#include "crypt.h" #include "network.h" #include "protocol.h" @@ -14,6 +15,7 @@ #include <string.h> #include <event2/event.h> +#include <event2/dns.h> /* The character that seperates multiple listeners in the cli */ #define SEPARATOR "+" @@ -305,6 +307,12 @@ main(int argc, const char **argv) WSAStartup(0x101, &wsaData); #endif + /* Initialize crypto */ + if (initialize_crypto() < 0) { + log_warn("Can't initialize crypto; failing"); + return 1; + } + /* Initialize libevent */ the_event_base = event_base_new(); if (!the_event_base) { @@ -365,14 +373,21 @@ main(int argc, const char **argv) "%d survived.", n_protocols, actual_protocols,n_listeners); - /* run the event loop if at least a listener was created. */ + /* run the event loop if at least one listener was created. */ if (n_listeners) event_base_dispatch(the_event_base); log_info("Exiting."); - close_obfsproxy_logfile(); free_all_listeners(); + evdns_base_free(get_evdns_base(), 0); + event_free(sig_int); + event_free(sig_term); + event_base_free(the_event_base); + + cleanup_crypto(); + + close_obfsproxy_logfile(); free(protocol_options); free(n_options_array); free(protocols); diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index f17af90..5c9aedc 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -27,7 +27,6 @@ downcast(struct protocol_t *proto) /* This function parses 'options' and fills the protocol parameters structure 'params'. - It then fills the obfs2 vtable and initializes the crypto subsystem. Returns 0 on success, -1 on fail. */ @@ -43,12 +42,6 @@ obfs2_init(int n_options, const char *const *options) return NULL; } - if (initialize_crypto() < 0) { - log_warn("Can't initialize crypto; failing"); - free(params); - return NULL; - } - return params; } @@ -219,6 +212,7 @@ derive_padding_key(void *s, const uchar *seed, digest_update(c, state->secret_seed, OBFUSCATE_SEED_LENGTH); digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); + digest_free(c); if (seed_nonzero(state->secret_seed)) { digest_t *d; @@ -227,13 +221,13 @@ derive_padding_key(void *s, const uchar *seed, d = digest_new(); digest_update(d, buf, sizeof(buf)); digest_getdigest(d, buf, sizeof(buf)); + digest_free(d); } } cryptstate = crypt_new(buf, 16); crypt_set_iv(cryptstate, buf+16, 16); memset(buf, 0, 16); - digest_free(c); return cryptstate; }

1 0

[obfsproxy/master] Merge branch 'master' into more-protocols
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit ac44ea9d975b6a87a0c4646a867e6daa22089d9a Merge: a76f645 ab1b016 Author: Zack Weinberg <zackw(a)panix.com> Date: Tue Jul 19 09:58:57 2011 -0700 Merge branch 'master' into more-protocols

1 0

[obfsproxy/master] whitespace and typos
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit 9d2f727fe26a74cd2cb43c49bed107f4e60e752e Author: Zack Weinberg <zackw(a)panix.com> Date: Fri Jul 22 16:58:32 2011 -0700 whitespace and typos --- src/network.c | 4 ++-- src/socks.c | 10 +++++----- src/test/integration_test/int_test.sh | 4 ++-- src/test/unittest_socks.c | 30 +++++++++++++++--------------- 4 files changed, 24 insertions(+), 24 deletions(-) diff --git a/src/network.c b/src/network.c index 4a85478..7d05b91 100644 --- a/src/network.c +++ b/src/network.c @@ -399,8 +399,8 @@ plaintext_read_cb(struct bufferevent *bev, void *arg) } /** - This callback is responsible for handling obfusacted - traffic -- traffic that has already been obfuscated + This callback is responsible for handling obfuscated + traffic -- traffic that has already been obfuscated by our protocol. */ static void diff --git a/src/socks.c b/src/socks.c index 333c787..f1eada4 100644 --- a/src/socks.c +++ b/src/socks.c @@ -106,14 +106,14 @@ socks_errno_to_reply(socks_state_t *state, int error) /** Takes a SOCKS5 command request from 'source', it evaluates it and if it's legit it parses it into 'parsereq'. - + It returns SOCKS_GOOD if everything went fine. It returns SOCKS_INCOMPLETE if we need more data from the client. It returns SOCKS_BROKEN if we didn't like something. It returns SOCKS_CMD_NOT_CONNECT if the client asked for something else other than CONNECT. If that's the case we should send a reply back to the client telling him that we don't support it. - + */ enum socks_ret socks5_handle_request(struct evbuffer *source, struct parsereq *parsereq) @@ -345,11 +345,11 @@ socks5_handle_negotiation(struct evbuffer *source, /** Takes a SOCKS4/SOCKS4a command request from 'source', it evaluates it and if it's legit it parses it into 'parsereq'. - + It returns SOCKS_GOOD if everything went fine. It returns SOCKS_INCOMPLETE if we need more data from the client. It returns SOCKS_BROKEN if we didn't like something. -*/ +*/ /* XXXX rename to socks4_handle_request or something. */ enum socks_ret @@ -552,7 +552,7 @@ socks_state_get_status(const socks_state_t *state) If we have previously parsed a SOCKS CONNECT request, this function places the corresponding address/port to 'af_out', 'addr_out' and 'port_out'. - + It returns 0 on success and -1 if it was called unnecessarily. */ int diff --git a/src/test/integration_test/int_test.sh b/src/test/integration_test/int_test.sh index d97a7f7..9aa37ac 100644 --- a/src/test/integration_test/int_test.sh +++ b/src/test/integration_test/int_test.sh @@ -36,7 +36,7 @@ sleep 2 if cmp -s alpha $FILE1 then echo "GREAT SUCCESS 1!" ; rm $FILE1 else echo "GREAT FAIL 1!" -fi +fi kill -9 $ncat1_pid kill -9 $obfsproxy_pid @@ -66,7 +66,7 @@ sleep 2 if cmp -s alpha $FILE2 then echo "GREAT SUCCESS 2!" ; rm $FILE2 else echo "GREAT FAIL 2!" -fi +fi kill -9 $ncat1_pid kill -9 $obfsproxy_pid diff --git a/src/test/unittest_socks.c b/src/test/unittest_socks.c index c6039af..d213a80 100644 --- a/src/test/unittest_socks.c +++ b/src/test/unittest_socks.c @@ -299,7 +299,7 @@ test_socks_socks5_request(void *data) evbuffer_add(s->source, "\x05", 1); evbuffer_add(s->source, req8, 9); - /* '-2' means that we don't support the requested command. */ + /* '-2' means that we don't support the requested command. */ tt_int_op(SOCKS_CMD_NOT_CONNECT, ==, socks5_handle_request(s->source,&pr1)); end:; @@ -340,16 +340,16 @@ test_socks_socks5_request_reply(void *data) tt_int_op(0, ==, evbuffer_drain(s->dest, buffer_len)); /* Second test: - We ask the server to send us a reply on an IPv6 request with + We ask the server to send us a reply on an IPv6 request with succesful status. */ s->state->parsereq.af = AF_INET6; strcpy(s->state->parsereq.addr, "d:1:5:e:a:5:e:0"); - + socks5_send_reply(s->dest,s->state, SOCKS5_SUCCESS); uchar rep2[255]; evbuffer_remove(s->dest,rep2,255); - + tt_assert(rep2[3] = SOCKS5_ATYP_IPV6); /* Test returned address against inet_pton(d:1:5:e:a:5:e:0) */ tt_mem_op(rep2+4, ==, @@ -381,11 +381,11 @@ test_socks_socks5_request_reply(void *data) /* check port */ tt_mem_op(rep3+5+strlen(fqdn), ==, "\x1c\xbd",2); - /* Fourth test: + /* Fourth test: We ask the server while having an empty parsereq and with a - SOCKS5_FAILED_UNSUPPORTED status. */ + SOCKS5_FAILED_UNSUPPORTED status. */ memset(&s->state->parsereq,'\x00',sizeof(struct parsereq)); - + socks5_send_reply(s->dest,s->state, SOCKS5_FAILED_UNSUPPORTED); uchar rep4[255]; evbuffer_remove(s->dest,rep4,255); @@ -393,13 +393,13 @@ test_socks_socks5_request_reply(void *data) tt_assert(rep4[3] == SOCKS5_ATYP_IPV4); tt_mem_op(rep4+4, ==, "\x00\x00\x00\x00",4); tt_mem_op(rep4+4+4, ==, "\x00\x00", 2); - + end:; } /** This function tests the 'Server reply' phase of the SOCKS4 - *and* SOCKS4a protocol. + *and* SOCKS4a protocol. It sends broken client request packets and it verifies that the SOCKS server detected the errors. It also sends some correct packets and it expects the server to like them. @@ -440,7 +440,7 @@ test_socks_socks4_request(void *data) memcpy(req2+1,&port,2); memcpy(req2+3,&addr,4); strcpy(req2+7,"KO"); - + evbuffer_add(s->source,req2,9); tt_int_op(SOCKS_INCOMPLETE, ==, socks4_read_request(s->source,s->state)); @@ -448,7 +448,7 @@ test_socks_socks4_request(void *data) /* emptying source buffer before next test */ buffer_len = evbuffer_get_length(s->source); tt_int_op(0, ==, evbuffer_drain(s->source, buffer_len)); - + /* Third test: Correct SOCKS4 req packet with optional field. */ char req3[16]; @@ -476,7 +476,7 @@ test_socks_socks4_request(void *data) memcpy(req4+3,&addr_4a,4); strcpy(req4+7,"iamalive"); strcpy(req4+16, "www.test.example"); - + evbuffer_add(s->source,req4,33); tt_int_op(SOCKS_GOOD, ==, socks4_read_request(s->source,s->state)); @@ -495,7 +495,7 @@ test_socks_socks4_request(void *data) memcpy(req5+3,&addr_4a,4); strcpy(req5+7,"iamalive"); strcpy(req5+16, "www.test.example"); - + /* Don't send it all. */ evbuffer_add(s->source,req5,28); @@ -516,7 +516,7 @@ test_socks_socks4_request(void *data) strcpy(req6+7,"iamalive"); memset(req6+16,'2', HUGE); req6[16+HUGE] = '\x00'; - + evbuffer_add(s->source,req6,16+HUGE+1); tt_int_op(SOCKS_BROKEN, ==, socks4_read_request(s->source,s->state)); @@ -545,7 +545,7 @@ test_socks_socks4_request_reply(void *data) We ask the server to send us a reply on an IPv4 request with succesful status. */ socks4_send_reply(s->dest,s->state, SOCKS4_SUCCESS); - + uchar rep1[255]; evbuffer_remove(s->dest,rep1,255); /* yes, this is dirty */

1 0

[obfsproxy/master] Return an evutil_addrinfo from resolve_address_port rather than copying out the address.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit b06baa42832cd05576dc32b9d113aef31d3c9b55 Author: Zack Weinberg <zackw(a)panix.com> Date: Sun Jul 24 13:03:34 2011 -0700 Return an evutil_addrinfo from resolve_address_port rather than copying out the address. --- src/network.c | 14 +++++++------- src/protocol.c | 8 ++++---- src/protocol.h | 9 +++------ src/protocols/dummy.c | 7 ++----- src/protocols/obfs2.c | 10 ++++------ src/util.c | 47 ++++++++++++++++++++++++----------------------- src/util.h | 9 ++++----- 7 files changed, 48 insertions(+), 56 deletions(-) diff --git a/src/network.c b/src/network.c index 7d05b91..75d90ef 100644 --- a/src/network.c +++ b/src/network.c @@ -117,11 +117,10 @@ listener_new(struct event_base *base, lsn->proto_params = proto_params; - lsn->listener = evconnlistener_new_bind(base, simple_listener_cb, lsn, - flags, - -1, - proto_params->listen_address, - proto_params->listen_address_len); + lsn->listener = + evconnlistener_new_bind(base, simple_listener_cb, lsn, flags, -1, + proto_params->listen_addr->ai_addr, + proto_params->listen_addr->ai_addrlen); if (!lsn->listener) { log_warn("Failed to create listener!"); @@ -246,8 +245,9 @@ simple_listener_cb(struct evconnlistener *evcl, if (conn->mode == LSN_SIMPLE_SERVER || conn->mode == LSN_SIMPLE_CLIENT) { /* Launch the connect attempt. */ if (bufferevent_socket_connect(conn->output, - lsn->proto_params->target_address, - lsn->proto_params->target_address_len)<0) + lsn->proto_params->target_addr->ai_addr, + lsn->proto_params->target_addr->ai_addrlen) + < 0) goto err; bufferevent_enable(conn->output, EV_READ|EV_WRITE); diff --git a/src/protocol.c b/src/protocol.c index 6abf7f1..8cd069e 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -53,10 +53,10 @@ proto_params_free(protocol_params_t *params) { obfs_assert(params); - if (params->target_address) - free(params->target_address); - if (params->listen_address) - free(params->listen_address); + if (params->target_addr) + evutil_freeaddrinfo(params->target_addr); + if (params->listen_addr) + evutil_freeaddrinfo(params->listen_addr); if (params->shared_secret) free(params->shared_secret); free(params); diff --git a/src/protocol.h b/src/protocol.h index 06dec08..6fa3eb4 100644 --- a/src/protocol.h +++ b/src/protocol.h @@ -5,11 +5,10 @@ #ifndef PROTOCOL_H #define PROTOCOL_H -#include <stddef.h> /* for size_t */ #include "network.h" /* for recv_ret */ +#include <event2/util.h> /* for evutil_addrinfo */ struct evbuffer; -struct sockaddr; /** This struct defines parameters of a protocol on a per-listener basis. @@ -20,12 +19,10 @@ struct sockaddr; */ typedef struct protocol_params_t { const struct protocol_vtable *vtable; - struct sockaddr *target_address; - struct sockaddr *listen_address; + struct evutil_addrinfo *target_addr; + struct evutil_addrinfo *listen_addr; char *shared_secret; size_t shared_secret_len; - size_t target_address_len; - size_t listen_address_len; int mode; } protocol_params_t; diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index 578182a..c12fe01 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -63,12 +63,9 @@ parse_and_set_options(int n_options, const char *const *options, } else return -1; - if (resolve_address_port(options[1], 1, 1, - &params->listen_address, - &params->listen_address_len, defport) < 0) { - log_warn("addr"); + params->listen_addr = resolve_address_port(options[1], 1, 1, defport); + if (!params->listen_addr) return -1; - } params->vtable = &dummy_vtable; return 0; diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 88d750f..42d30c1 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -67,9 +67,8 @@ parse_and_set_options(int n_options, const char *const *options, if (!strncmp(*options,"--dest=",7)) { if (got_dest) return -1; - if (resolve_address_port(*options+7, 1, 0, - &params->target_address, - &params->target_address_len, NULL) < 0) + params->target_addr = resolve_address_port(*options+7, 1, 0, NULL); + if (!params->target_addr) return -1; got_dest=1; } else if (!strncmp(*options,"--shared-secret=",16)) { @@ -102,9 +101,8 @@ parse_and_set_options(int n_options, const char *const *options, } options++; - if (resolve_address_port(*options, 1, 1, - &params->listen_address, - &params->listen_address_len, defport) < 0) + params->listen_addr = resolve_address_port(*options, 1, 1, defport); + if (!params->listen_addr) return -1; /* Validate option selection. */ diff --git a/src/util.c b/src/util.c index a4801a0..87087c2 100644 --- a/src/util.c +++ b/src/util.c @@ -141,7 +141,7 @@ ui64_log2(uint64_t u64) /** Accepts a string 'address' of the form ADDRESS:PORT and attempts to - parse it into 'addr_out' and put it's length into 'addrlen_out'. + parse it into an 'evutil_addrinfo' structure. If 'nodns' is set it means that 'address' was an IP address. If 'passive' is set it means that the address is destined for @@ -150,16 +150,13 @@ ui64_log2(uint64_t u64) If no port was given in 'address', we set 'default_port' as the port. */ -int -resolve_address_port(const char *address, - int nodns, int passive, - struct sockaddr **addr_out, - size_t *addrlen_out, +struct evutil_addrinfo * +resolve_address_port(const char *address, int nodns, int passive, const char *default_port) { struct evutil_addrinfo *ai = NULL; struct evutil_addrinfo ai_hints; - int result = -1, ai_res; + int ai_res, ai_errno; char *a = xstrdup(address), *cp; const char *portstr; @@ -170,7 +167,8 @@ resolve_address_port(const char *address, portstr = default_port; } else { log_debug("Error in address %s: port required.", address); - goto done; + free(a); + return NULL; } memset(&ai_hints, 0, sizeof(ai_hints)); @@ -182,24 +180,27 @@ resolve_address_port(const char *address, if (nodns) ai_hints.ai_flags |= EVUTIL_AI_NUMERICHOST; - if ((ai_res = evutil_getaddrinfo(a, portstr, &ai_hints, &ai))) { - log_warn("Error resolving %s (%s) (%s): %s", - address, a, portstr, evutil_gai_strerror(ai_res)); - goto done; - } - if (ai == NULL) { + ai_res = evutil_getaddrinfo(a, portstr, &ai_hints, &ai); + ai_errno = errno; + + free(a); + + if (ai_res) { + if (ai_res == EAI_SYSTEM) + log_warn("Error resolving %s: %s [%s]", + address, evutil_gai_strerror(ai_res), strerror(ai_errno)); + else + log_warn("Error resolving %s: %s", address, evutil_gai_strerror(ai_res)); + + if (ai) { + evutil_freeaddrinfo(ai); + ai = NULL; + } + } else if (ai == NULL) { log_warn("No result for address %s", address); - goto done; } - *addrlen_out = ai->ai_addrlen; - *addr_out = xmemdup(ai->ai_addr, ai->ai_addrlen); - result = 0; - done: - free(a); - if (ai) - evutil_freeaddrinfo(ai); - return result; + return ai; } static struct evdns_base *the_evdns_base = NULL; diff --git a/src/util.h b/src/util.h index a88d06c..cb98fbd 100644 --- a/src/util.h +++ b/src/util.h @@ -9,6 +9,7 @@ #include <stdarg.h> /* va_list */ #include <stddef.h> /* size_t, ptrdiff_t, offsetof, NULL */ #include <stdint.h> /* intN_t, uintN_t */ +#include <event2/util.h> /* evutil_addrinfo */ struct sockaddr; struct event_base; @@ -50,11 +51,9 @@ unsigned int ui64_log2(uint64_t u64); /***** Network functions. *****/ -int resolve_address_port(const char *address, - int nodns, int passive, - struct sockaddr **addr_out, - size_t *addrlen_out, - const char *default_port); +struct evutil_addrinfo *resolve_address_port(const char *address, + int nodns, int passive, + const char *default_port); struct evdns_base *get_evdns_base(void); int init_evdns_base(struct event_base *base);

1 0

[obfsproxy/master] Allow protocols to allocate extra state for their protocol_params_t as well as their protocol_t. Use this to remove the obfs2 shared secret from the generic protocol_params_t.
by nickm＠torproject.org 09 Sep '11

09 Sep '11

commit ebd15e8027e89ca3027c2ffc2c629a8a552cb772 Author: Zack Weinberg <zackw(a)panix.com> Date: Sun Jul 24 13:49:51 2011 -0700 Allow protocols to allocate extra state for their protocol_params_t as well as their protocol_t. Use this to remove the obfs2 shared secret from the generic protocol_params_t. --- src/protocol.c | 15 ++++-- src/protocol.h | 62 +++++++++++------------ src/protocols/dummy.c | 7 +++ src/protocols/obfs2.c | 131 ++++++++++++++++++++++++++---------------------- src/protocols/obfs2.h | 6 ++- 5 files changed, 122 insertions(+), 99 deletions(-) diff --git a/src/protocol.c b/src/protocol.c index 8cd069e..212ddaa 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -52,14 +52,19 @@ void proto_params_free(protocol_params_t *params) { obfs_assert(params); + obfs_assert(params->vtable); + obfs_assert(params->vtable->fini); - if (params->target_addr) + if (params->target_addr) { evutil_freeaddrinfo(params->target_addr); - if (params->listen_addr) + params->target_addr = NULL; + } + if (params->listen_addr) { evutil_freeaddrinfo(params->listen_addr); - if (params->shared_secret) - free(params->shared_secret); - free(params); + params->listen_addr = NULL; + } + + params->vtable->fini(params); } /** diff --git a/src/protocol.h b/src/protocol.h index 6fa3eb4..c1189ea 100644 --- a/src/protocol.h +++ b/src/protocol.h @@ -11,39 +11,28 @@ struct evbuffer; /** - This struct defines parameters of a protocol on a per-listener basis. - - By 'per-listener basis' I mean that the parameters defined here will - be inherited by *all* connections opened from the listener_t that - owns this protocol_params_t. -*/ + This struct defines the protocol-specific state for all connections + opened from a particular listener. Each protocol may extend this + structure with additional private data by embedding it as the first + member of a larger structure (standard fake-inheritance-in-C + technique). + */ typedef struct protocol_params_t { const struct protocol_vtable *vtable; struct evutil_addrinfo *target_addr; struct evutil_addrinfo *listen_addr; - char *shared_secret; - size_t shared_secret_len; int mode; } protocol_params_t; /** - This protocol specific struct defines the state of the protocol - on a per-connection basis. - - By 'protocol specific' I mean that every protocol has its own - state struct. (for example, obfs2 has obfs2_state_t). A protocol_t - struct is always the first member of this struct, and vtable->create - returns that member (standard fake-inheritance-in-C technique). - All data other than the vtable is hidden from everything but the - protocol implementation. - - By 'per-connection basis' I mean that the every connection has a - different protocol_t struct, and that's precisely the reason that - this struct is owned by the conn_t struct. + This struct defines the protocol-specific state for a particular + connection. Again, each protocol may extend this structure with + additional private data by embedding it as the first member of a + larger structure. */ -struct protocol_t { +typedef struct protocol_t { const struct protocol_vtable *vtable; -}; +} protocol_t; /** This struct defines a protocol and its methods; note that not all @@ -58,23 +47,29 @@ typedef struct protocol_vtable /** The short name of this protocol. */ const char *name; - /** Initialization function: Allocate a 'protocol_params_t' object - and fill it in from the provided 'options' array. */ - struct protocol_params_t *(*init)(int n_options, - const char *const *options); + /** Initialization: Allocate a 'protocol_params_t' object and fill + it in from the provided 'options' array. */ + protocol_params_t *(*init)(int n_options, const char *const *options); + + /** Finalization: Destroy the provided 'protocol_params_t' object. + This function is responsible for deallocating any data that the + protocol's extended structure points to, and deallocating the + object itself. But it is *not* responsible for deallocating the + data pointed to by the generic 'protocol_params_t'; that's + already been done. */ + void (*fini)(protocol_params_t *params); /** Constructor: Allocates per-connection, protocol-specific state. */ - struct protocol_t *(*create)(struct protocol_params_t *params); + protocol_t *(*create)(protocol_params_t *params); /** Destructor: Destroys per-connection, protocol-specific state. */ - void (*destroy)(struct protocol_t *state); + void (*destroy)(protocol_t *state); /** Perform a connection handshake. Not all protocols have a handshake. */ - int (*handshake)(struct protocol_t *state, - struct evbuffer *buf); + int (*handshake)(protocol_t *state, struct evbuffer *buf); /** Send data coming downstream from 'source' along to 'dest'. */ - int (*send)(struct protocol_t *state, + int (*send)(protocol_t *state, struct evbuffer *source, struct evbuffer *dest); @@ -93,7 +88,8 @@ typedef struct protocol_vtable #define DEFINE_PROTOCOL_VTABLE(name) \ const struct protocol_vtable name##_vtable = { \ #name, \ - name##_init, name##_create, name##_destroy, \ + name##_init, name##_fini, \ + name##_create, name##_destroy, \ name##_handshake, name##_send, name##_recv \ } diff --git a/src/protocols/dummy.c b/src/protocols/dummy.c index c12fe01..ae45d9c 100644 --- a/src/protocols/dummy.c +++ b/src/protocols/dummy.c @@ -29,6 +29,7 @@ dummy_init(int n_options, const char *const *options) { struct protocol_params_t *params = xzalloc(sizeof(struct protocol_params_t)); + params->vtable = &dummy_vtable; if (parse_and_set_options(n_options, options, params) < 0) { proto_params_free(params); @@ -87,6 +88,12 @@ usage(void) "\tobfsproxy dummy socks 127.0.0.1:5000"); } +static void +dummy_fini(struct protocol_params_t *params) +{ + free(params); +} + /* This is called everytime we get a connection for the dummy protocol. diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 42d30c1..f7862fe 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -16,13 +16,22 @@ static void usage(void); static int parse_and_set_options(int n_options, const char *const *options, - struct protocol_params_t *params); + obfs2_params_t *params); -static inline obfs2_protocol_t * -downcast(struct protocol_t *proto) +/** Return true iff the OBFUSCATE_SEED_LENGTH-byte seed in 'seed' is nonzero */ +static inline int +seed_nonzero(const uchar *seed) { - return (obfs2_protocol_t *) - ((char *)proto - offsetof(obfs2_protocol_t, super)); + static const uchar OBFUSCATE_ZERO_SEED[OBFUSCATE_SEED_LENGTH] = {0}; + return memcmp(seed, OBFUSCATE_ZERO_SEED, OBFUSCATE_SEED_LENGTH) != 0; +} + +/** Return true iff the SHARED_SECRET_LENGTH-byte seed in 'seed' is nonzero */ +static inline int +shared_seed_nonzero(const uchar *seed) +{ + static const uchar SHARED_ZERO_SEED[SHARED_SECRET_LENGTH] = {0}; + return memcmp(seed, SHARED_ZERO_SEED, SHARED_SECRET_LENGTH) != 0; } /* @@ -31,19 +40,19 @@ downcast(struct protocol_t *proto) Returns 0 on success, -1 on fail. */ -static struct protocol_params_t * +static protocol_params_t * obfs2_init(int n_options, const char *const *options) { - struct protocol_params_t *params - = xzalloc(sizeof(struct protocol_params_t)); + obfs2_params_t *params = xzalloc(sizeof(obfs2_params_t)); + params->super.vtable = &obfs2_vtable; if (parse_and_set_options(n_options, options, params) < 0) { - proto_params_free(params); + proto_params_free(&params->super); usage(); return NULL; } - return params; + return &params->super; } /** @@ -51,7 +60,7 @@ obfs2_init(int n_options, const char *const *options) */ int parse_and_set_options(int n_options, const char *const *options, - struct protocol_params_t *params) + obfs2_params_t *params) { int got_dest=0; int got_ss=0; @@ -67,17 +76,23 @@ parse_and_set_options(int n_options, const char *const *options, if (!strncmp(*options,"--dest=",7)) { if (got_dest) return -1; - params->target_addr = resolve_address_port(*options+7, 1, 0, NULL); - if (!params->target_addr) + params->super.target_addr = + resolve_address_port(*options+7, 1, 0, NULL); + if (!params->super.target_addr) return -1; got_dest=1; } else if (!strncmp(*options,"--shared-secret=",16)) { + digest_t *c; if (got_ss) return -1; - /* this is freed in proto_params_free() */ - params->shared_secret_len = strlen(*options+16); - params->shared_secret = xmemdup(*options+16, - params->shared_secret_len + 1); + + /* ASN we must say in spec that we hash command line shared + secret. */ + c = digest_new(); + digest_update(c, (uchar*)*options+16, strlen(*options+16)); + digest_getdigest(c, params->shared_secret, SHARED_SECRET_LENGTH); + digest_free(c); + got_ss=1; } else { log_warn("obfs2: Unknown argument."); @@ -88,37 +103,36 @@ parse_and_set_options(int n_options, const char *const *options, if (!strcmp(*options, "client")) { defport = "48988"; /* bf5c */ - params->mode = LSN_SIMPLE_CLIENT; + params->super.mode = LSN_SIMPLE_CLIENT; } else if (!strcmp(*options, "socks")) { defport = "23548"; /* 5bf5 */ - params->mode = LSN_SOCKS_CLIENT; + params->super.mode = LSN_SOCKS_CLIENT; } else if (!strcmp(*options, "server")) { defport = "11253"; /* 2bf5 */ - params->mode = LSN_SIMPLE_SERVER; + params->super.mode = LSN_SIMPLE_SERVER; } else { log_warn("obfs2: only client/socks/server modes supported."); return -1; } options++; - params->listen_addr = resolve_address_port(*options, 1, 1, defport); - if (!params->listen_addr) + params->super.listen_addr = resolve_address_port(*options, 1, 1, defport); + if (!params->super.listen_addr) return -1; /* Validate option selection. */ - if (got_dest && (params->mode == LSN_SOCKS_CLIENT)) { + if (got_dest && (params->super.mode == LSN_SOCKS_CLIENT)) { log_warn("obfs2: You can't be on socks mode and have --dest."); return -1; } - if (!got_dest && (params->mode != LSN_SOCKS_CLIENT)) { + if (!got_dest && (params->super.mode != LSN_SOCKS_CLIENT)) { log_warn("obfs2: client/server mode needs --dest."); return -1; } log_debug("obfs2: Parsed options nicely!"); - params->vtable = &obfs2_vtable; return 0; } @@ -142,13 +156,6 @@ usage(void) "\tobfs2 server 127.0.0.1:1026"); } -/** Return true iff the OBFUSCATE_SEED_LENGTH-byte seed in 'seed' is nonzero */ -static int -seed_nonzero(const uchar *seed) -{ - return memcmp(seed, OBFUSCATE_ZERO_SEED, OBFUSCATE_SEED_LENGTH) != 0; -} - /** Derive and return key of type 'keytype' from the seeds currently set in 'state'. @@ -166,12 +173,12 @@ derive_key(void *s, const char *keytype) digest_update(c, state->initiator_seed, OBFUSCATE_SEED_LENGTH); if (seed_nonzero(state->responder_seed)) digest_update(c, state->responder_seed, OBFUSCATE_SEED_LENGTH); - if (seed_nonzero(state->secret_seed)) + if (shared_seed_nonzero(state->secret_seed)) digest_update(c, state->secret_seed, SHARED_SECRET_LENGTH); digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); - if (seed_nonzero(state->secret_seed)) { + if (shared_seed_nonzero(state->secret_seed)) { digest_t *d; int i; for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { @@ -206,13 +213,13 @@ derive_padding_key(void *s, const uchar *seed, digest_update(c, (uchar*)keytype, strlen(keytype)); if (seed_nonzero(seed)) digest_update(c, seed, OBFUSCATE_SEED_LENGTH); - if (seed_nonzero(state->secret_seed)) + if (shared_seed_nonzero(state->secret_seed)) digest_update(c, state->secret_seed, OBFUSCATE_SEED_LENGTH); digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); digest_free(c); - if (seed_nonzero(state->secret_seed)) { + if (shared_seed_nonzero(state->secret_seed)) { digest_t *d; int i; for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { @@ -230,22 +237,32 @@ derive_padding_key(void *s, const uchar *seed, } /** + Frees obfs2 parameters 'p' + */ +static void +obfs2_fini(protocol_params_t *p) +{ + obfs2_params_t *params = DOWNCAST(obfs2_params_t, super, p); + /* wipe out keys */ + memset(params, 0x99, sizeof(obfs2_params_t)); + free(params); +} + + +/** This is called everytime we get a connection for the obfs2 protocol. - - It sets up the protocol vtable in 'proto_struct' and then attempts - to create and return a protocol state according to the protocol - parameters 'params'. */ -static struct protocol_t * -obfs2_create(protocol_params_t *params) +static protocol_t * +obfs2_create(protocol_params_t *p) { + obfs2_params_t *params = DOWNCAST(obfs2_params_t, super, p); obfs2_protocol_t *proto = xzalloc(sizeof(obfs2_protocol_t)); uchar *seed; const char *send_pad_type; proto->state = ST_WAIT_FOR_KEY; - proto->we_are_initiator = (params->mode != LSN_SIMPLE_SERVER); + proto->we_are_initiator = (params->super.mode != LSN_SIMPLE_SERVER); if (proto->we_are_initiator) { send_pad_type = INITIATOR_PAD_TYPE; seed = proto->initiator_seed; @@ -255,19 +272,13 @@ obfs2_create(protocol_params_t *params) } /* Generate our seed */ + memcpy(proto->secret_seed, params->shared_secret, SHARED_SECRET_LENGTH); + if (random_bytes(seed, OBFUSCATE_SEED_LENGTH) < 0) { free(proto); return NULL; } - if (params->shared_secret) { - /* ASN we must say in spec that we hash command line shared secret. */ - digest_t *c = digest_new(); - digest_update(c, (uchar*)params->shared_secret, params->shared_secret_len); - digest_getdigest(c, proto->secret_seed, SHARED_SECRET_LENGTH); - digest_free(c); - } - /* Derive the key for what we're sending */ proto->send_padding_crypto = derive_padding_key(proto, seed, send_pad_type); proto->super.vtable = &obfs2_vtable; @@ -278,9 +289,9 @@ obfs2_create(protocol_params_t *params) Frees obfs2 state 's' */ static void -obfs2_destroy(struct protocol_t *s) +obfs2_destroy(protocol_t *s) { - obfs2_protocol_t *state = downcast(s); + obfs2_protocol_t *state = DOWNCAST(obfs2_protocol_t, super, s); if (state->send_crypto) crypt_free(state->send_crypto); if (state->send_padding_crypto) @@ -301,9 +312,9 @@ obfs2_destroy(struct protocol_t *s) the evbuffer 'buf'. Return 0 on success, -1 on failure. */ static int -obfs2_handshake(struct protocol_t *s, struct evbuffer *buf) +obfs2_handshake(protocol_t *s, struct evbuffer *buf) { - obfs2_protocol_t *state = downcast(s); + obfs2_protocol_t *state = DOWNCAST(obfs2_protocol_t, super, s); uint32_t magic = htonl(OBFUSCATE_MAGIC_VALUE), plength, send_plength; uchar msg[OBFUSCATE_MAX_PADDING + OBFUSCATE_SEED_LENGTH + 8]; @@ -367,10 +378,10 @@ obfs2_crypt_and_transmit(crypt_t *crypto, using the state in 'state'. Returns 0 on success, -1 on failure. */ static int -obfs2_send(struct protocol_t *s, - struct evbuffer *source, struct evbuffer *dest) +obfs2_send(protocol_t *s, + struct evbuffer *source, struct evbuffer *dest) { - obfs2_protocol_t *state = downcast(s); + obfs2_protocol_t *state = DOWNCAST(obfs2_protocol_t, super, s); if (state->send_crypto) { /* First of all, send any data that we've been waiting to send. */ @@ -440,10 +451,10 @@ init_crypto(void *s) * our callers that they must call obfs2_send() immediately. */ static enum recv_ret -obfs2_recv(struct protocol_t *s, struct evbuffer *source, +obfs2_recv(protocol_t *s, struct evbuffer *source, struct evbuffer *dest) { - obfs2_protocol_t *state = downcast(s); + obfs2_protocol_t *state = DOWNCAST(obfs2_protocol_t, super, s); enum recv_ret r=0; if (state->state == ST_WAIT_FOR_KEY) { diff --git a/src/protocols/obfs2.h b/src/protocols/obfs2.h index e93fbcd..eb55a9f 100644 --- a/src/protocols/obfs2.h +++ b/src/protocols/obfs2.h @@ -25,7 +25,6 @@ extern const struct protocol_vtable obfs2_vtable; #define OBFUSCATE_MAGIC_VALUE 0x2BF5CA7E #define OBFUSCATE_SEED_LENGTH 16 #define OBFUSCATE_MAX_PADDING 8192 -#define OBFUSCATE_ZERO_SEED "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" #define OBFUSCATE_HASH_ITERATIONS 100000 #define INITIATOR_PAD_TYPE "Initiator obfuscation padding" @@ -35,6 +34,11 @@ extern const struct protocol_vtable obfs2_vtable; #define SHARED_SECRET_LENGTH SHA256_LENGTH +typedef struct obfs2_params_t { + protocol_params_t super; + uchar shared_secret[SHARED_SECRET_LENGTH]; +} obfs2_params_t; + typedef struct obfs2_protocol_t { struct protocol_t super;

1 0