tor-commits
Threads by month
- ----- 2025 -----
- July
- June
- May
- April
- March
- February
- January
- ----- 2024 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2023 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2022 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2021 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2020 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2019 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2018 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2017 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2016 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2015 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2014 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2013 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2012 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
- January
- ----- 2011 -----
- December
- November
- October
- September
- August
- July
- June
- May
- April
- March
- February
September 2011
- 19 participants
- 865 discussions

[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
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
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
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 <b>sl</b> can hold at least <b>size</b> 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 <b>sl</b> 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 <b>sl</b>. */
+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 <b>sl</b> has some element E such that
+ * !strcmp(E,<b>element</b>)
+ */
+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 <b>element</b> is equal to an element of <b>sl</b>, 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 <b>sl</b> has some element E such that
+ * !strcasecmp(E,<b>element</b>)
+ */
+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 <b>sl</b> has some element E such that E is equal
+ * to the decimal encoding of <b>num</b>.
+ */
+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 <b>sl</b> has some element E such that
+ * !memcmp(E,<b>element</b>,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 <b>idx</b>th element of sl; if idx is not the last
+ * element, swap the last element of sl into the <b>idx</b>th 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 <b>idx</b>th element of sl; if idx is not the last element,
+ * moving all subsequent elements back one space. Return the old value
+ * of the <b>idx</b>th 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 <b>val</b> as the new <b>idx</b>th element of
+ * <b>sl</b>, moving all items previously at <b>idx</b> 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 <b>str</b> along all occurrences of <b>sep</b>,
+ * appending the (newly allocated) split strings, in order, to
+ * <b>sl</b>. Return the number of strings added to <b>sl</b>.
+ *
+ * If <b>flags</b>&SPLIT_SKIP_SPACE is true, remove initial and
+ * trailing space from each entry.
+ * If <b>flags</b>&SPLIT_IGNORE_BLANK is true, remove any entries
+ * of length 0.
+ * If <b>flags</b>&SPLIT_STRIP_SPACE is true, strip spaces from each
+ * split string.
+ *
+ * If <b>max</b>\>0, divide the string into no more than <b>max</b> pieces. If
+ * <b>sep</b> 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 <b>sl</b>, in order, separated by <b>join</b>. If
+ * <b>terminate</b> is true, also terminate the string with <b>join</b>.
+ * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
+ * the returned string. Requires that every element of <b>sl</b> 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 <b>join</b>, uses the <b>join_len</b>-byte sequence
+ * at <b>join</b>. (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 <b>sl</b> into an order defined by
+ * the ordering function <b>compare</b>, 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 <b>sl</b> sorted with the function <b>compare</b>,
+ * 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 <b>sl</b> 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 <b>sl</b>; or NULL if <b>sl</b>
+ * 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 <b>sl</b> 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 <b>sl</b> are in order, return a pointer to the
+ * member that matches <b>key</b>. Ordering and matching are defined by a
+ * <b>compare</b> 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 <b>sl</b> are in order, return the index of the
+ * member that matches <b>key</b>. If no member matches, return the index of
+ * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
+ * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to
+ * false otherwise. Ordering and matching are defined by a <b>compare</b>
+ * 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 <b>sl</b> 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 <b>sl</b> */
+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 <b>idx_field_offset</b>
+ * 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 <b>sl</b>,
+ * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
+ * value (that is, to <b>i</b>).
+ */
+#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. <b>sl</b> may have at most one violation of the heap property:
+ * the item at <b>idx</b> 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 <b>item</b> into the heap stored in <b>sl</b>, where order is
+ * determined by <b>compare</b> and the offset of the item in the heap is
+ * stored in an int-typed field at position <b>idx_field_offset</b> 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 <b>sl</b>,
+ * where order is determined by <b>compare</b> and the item's position is
+ * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> 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 <b>item</b> from the heap stored in <b>sl</b>,
+ * where order is determined by <b>compare</b> and the item's position is
+ * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> 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 <b>sl</b>, where order is determined by <b>compare</b>. */
+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 <b>maptype</b>. The key part of each
+ * entry is declared using the C declaration <b>keydecl</b>. All functions
+ * and types associated with the map get prefixed with <b>prefix</b> */
+#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 <b>key</b> to <b>val</b>. Returns the previous
+ * value for <b>key</b> if one was set, or NULL if one was not.
+ *
+ * This function makes a copy of <b>key</b> if necessary, but not of
+ * <b>val</b>.
+ */
+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 <b>key</b>, 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 <b>key</b> from the map.
+ * Return the value if one was set, or NULL if there was no entry for
+ * <b>key</b>.
+ *
+ * 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 <b>key</b> 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 <b>key</b> 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 <b>key</b> 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 <b>iterator</b> 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 <b>map</b>. 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 <b>iter</b> for <b>map</b> 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 <b>iter</b> 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 <b>iter</b> 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 <b>iter</b> 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 *<b>keyp</b> and *<b>valp</b> 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 *<b>keyp</b> and *<b>valp</b> 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 <b>iter</b> has advanced past the last entry of
+ * <b>map</b>. */
+int
+strmap_iter_done(strmap_iter_t *iter)
+{
+ return iter == NULL;
+}
+
+/** Return true iff <b>iter</b> has advanced past the last entry of
+ * <b>map</b>. */
+int
+digestmap_iter_done(digestmap_iter_t *iter)
+{
+ return iter == NULL;
+}
+
+/** Remove all entries from <b>map</b>, and deallocate storage for those
+ * entries. If free_val is provided, it is invoked on every value in
+ * <b>map</b>.
+ */
+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 <b>map</b>, and deallocate storage for those
+ * entries. If free_val is provided, it is invoked on every value in
+ * <b>map</b>.
+ */
+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 <b>map</b>. */
+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 <b>map</b>. */
+void
+digestmap_assert_ok(const digestmap_t *map)
+{
+ obfs_assert(!_digestmap_impl_HT_REP_IS_BAD(&map->head));
+}
+
+/** Return true iff <b>map</b> has no entries. */
+int
+strmap_isempty(const strmap_t *map)
+{
+ return HT_EMPTY(&map->head);
+}
+
+/** Return true iff <b>map</b> has no entries. */
+int
+digestmap_isempty(const digestmap_t *map)
+{
+ return HT_EMPTY(&map->head);
+}
+
+/** Return the number of items in <b>map</b>. */
+int
+strmap_size(const strmap_t *map)
+{
+ return HT_SIZE(&map->head);
+}
+
+/** Return the number of items in <b>map</b>. */
+int
+digestmap_size(const digestmap_t *map)
+{
+ return HT_SIZE(&map->head);
+}
+
+/** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
+ * function for an array of type <b>elt_t</b>*.
+ *
+ * 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
+ * <b>max_elements</b> 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 <b>set</b>. */
+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 {
+ /** @{ */
+ /** <b>list</b> has enough capacity to store exactly <b>capacity</b> elements
+ * before it needs to be resized. Only the first <b>num_used</b> (\<=
+ * 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 <b>idx</b>th 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 <b>idx1</b> and <b>idx2</b> of the
+ * smartlist <b>sl</b>. */
+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 <b>sl</b>, in order. For each item,
+ * assign it to a new local variable of type <b>type</b> named <b>var</b>, and
+ * execute the statement <b>cmd</b>. Inside the loop, the loop index can
+ * be accessed as <b>var</b>_sl_idx and the length of the list can be accessed
+ * as <b>var</b>_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 <b>sl</b> indexed
+ * with the variable <b>var</b>, 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 <b>sl</b> indexed
+ * with the variable <b>var</b>, replace the current element with <b>val</b>.
+ * Does not deallocate the current value of <b>var</b>.
+ */
+#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 <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no
+ * duplicates on the common field, loop through the lists in lockstep, and
+ * execute <b>unmatched_var2</b> 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 <b>map</b> in order.
+ * <b>prefix</b> 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 <b>n_bits</b> 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 <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>,
+ * 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 <b>ba</b>. */
+static inline void
+bitarray_free(bitarray_t *ba)
+{
+ free(ba);
+}
+/** Set the <b>bit</b>th bit in <b>b</b> to 1. */
+static inline void
+bitarray_set(bitarray_t *b, int bit)
+{
+ b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
+}
+/** Set the <b>bit</b>th bit in <b>b</b> to 0. */
+static inline void
+bitarray_clear(bitarray_t *b, int bit)
+{
+ b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
+}
+/** Return true iff <b>bit</b>th bit in <b>b</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 <b>ba</b>; 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 <b>digest</b> to <b>set</b>. */
+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 <b>digest</b> is in <b>set</b>, return nonzero. Otherwise,
+ * <em>probably</em> 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 <b>array</b> of <b>n_elements</b>, return the
+ * <b>nth</b> lowest element. <b>nth</b>=0 gives the lowest element;
+ * <b>n_elements</b>-1 gives the highest; and (<b>n_elements</b>-1) / 2 gives
+ * the median. As a side effect, the elements of <b>array</b> 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 <b>max</b>-1 inclusive. <b>max</b> 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 *<b>a</b> and
+ * *<b>b</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 *<b>a</b> and
+ * *<b>b</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 <b>s</b> every character which appears in
+ * <b>strip</b>. */
+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
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

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
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
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,
- ¶ms->listen_address,
- ¶ms->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,
- ¶ms->target_address,
- ¶ms->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,
- ¶ms->listen_address,
- ¶ms->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
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(¶ms->super);
usage();
return NULL;
}
- return params;
+ return ¶ms->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

[obfsproxy/master] Use smartlist instead of dll for the connections and listeners lists.
by nickm@torproject.org 09 Sep '11
by nickm@torproject.org 09 Sep '11
09 Sep '11
commit ec5edc941ef13787f1baae0e741a05536d374571
Author: Zack Weinberg <zackw(a)panix.com>
Date: Tue Jul 19 10:46:23 2011 -0700
Use smartlist instead of dll for the connections and listeners lists.
---
src/main.c | 5 +--
src/network.c | 141 ++++++++++++++++++++++++++++-----------------------------
src/network.h | 3 +-
src/util.c | 112 ---------------------------------------------
src/util.h | 49 +++++++-------------
5 files changed, 88 insertions(+), 222 deletions(-)
diff --git a/src/main.c b/src/main.c
index a7aa298..cf811fa 100644
--- a/src/main.c
+++ b/src/main.c
@@ -372,10 +372,7 @@ main(int argc, const char **argv)
log_info("Exiting.");
close_obfsproxy_logfile();
-
- free_all_listeners(); /* free all listeners in our listener dll */
-
- /* We are exiting. Clean everything. */
+ free_all_listeners();
free(protocol_options);
free(n_options_array);
free(protocols);
diff --git a/src/network.c b/src/network.c
index 35e4eaf..4a85478 100644
--- a/src/network.c
+++ b/src/network.c
@@ -7,6 +7,7 @@
#define NETWORK_PRIVATE
#include "network.h"
+#include "container.h"
#include "main.h"
#include "socks.h"
#include "protocol.h"
@@ -24,19 +25,16 @@
#include <ws2tcpip.h> /* socklen_t */
#endif
-/** Doubly linked list holding all our listeners. */
-static dll_t listener_list = DLL_INIT();
+/** All our listeners. */
+static smartlist_t *listeners;
struct listener_t {
- dll_node_t dll_node;
struct evconnlistener *listener;
protocol_params_t *proto_params;
};
-/** Doubly linked list holding all connections. */
-static dll_t conn_list = DLL_INIT();
-/** Active connection counter */
-static int n_connections=0;
+/** All active connections. */
+static smartlist_t *connections;
/** Flag toggled when obfsproxy is shutting down. It blocks new
connections and shutdowns when the last connection is closed. */
@@ -64,7 +62,7 @@ static void output_event_cb(struct bufferevent *bev, short what, void *arg);
If 'barbaric' is set, we forcefully close all open connections and
finish shutdown.
-
+
(Only called by signal handlers)
*/
void
@@ -73,31 +71,32 @@ start_shutdown(int barbaric)
if (!shutting_down)
shutting_down=1;
- if (!n_connections) {
- finish_shutdown();
- return;
- }
+ if (barbaric)
+ close_all_connections();
- if (barbaric) {
- if (n_connections)
- close_all_connections();
- return;
+ if (connections && smartlist_len(connections) == 0) {
+ smartlist_free(connections);
+ connections = NULL;
}
-}
+
+ if (!connections)
+ finish_shutdown();
+}
/**
Closes all open connections.
-*/
+*/
static void
close_all_connections(void)
{
- /** Traverse the dll and close all connections */
- while (conn_list.head) {
- conn_t *conn = DOWNCAST(conn_t, dll_node, conn_list.head);
- conn_free(conn); /* removes it */
- }
- obfs_assert(!n_connections);
+ if (!connections)
+ return;
+ SMARTLIST_FOREACH(connections, conn_t *, conn,
+ { conn_free(conn); });
+ smartlist_free(connections);
+ connections = NULL;
}
+
/**
This function spawns a listener configured according to the
provided 'protocol_params_t' object'. Returns the listener on
@@ -107,7 +106,6 @@ close_all_connections(void)
protocol_params_t object provided; if it fails, the protocol_params_t
object is deallocated.
*/
-
listener_t *
listener_new(struct event_base *base,
protocol_params_t *proto_params)
@@ -127,12 +125,15 @@ listener_new(struct event_base *base,
if (!lsn->listener) {
log_warn("Failed to create listener!");
- listener_free(lsn);
+ proto_params_free(lsn->proto_params);
+ free(lsn);
return NULL;
}
- /** If we don't have a connection dll, create one now. */
- dll_append(&listener_list, &lsn->dll_node);
+ /* If we don't have a listener list, create one now. */
+ if (!listeners)
+ listeners = smartlist_create();
+ smartlist_add(listeners, lsn);
return lsn;
}
@@ -140,17 +141,13 @@ listener_new(struct event_base *base,
/**
Deallocates listener_t 'lsn'.
*/
-void
+static void
listener_free(listener_t *lsn)
{
if (lsn->listener)
evconnlistener_free(lsn->listener);
if (lsn->proto_params)
proto_params_free(lsn->proto_params);
-
- dll_remove(&listener_list, &lsn->dll_node);
-
- memset(lsn, 0xb0, sizeof(listener_t));
free(lsn);
}
@@ -160,20 +157,14 @@ listener_free(listener_t *lsn)
void
free_all_listeners(void)
{
- static int called_already=0;
-
- if (called_already)
+ if (!listeners)
return;
-
log_info("Closing all listeners.");
- /* Iterate listener doubly linked list and free them all. */
- while (listener_list.head) {
- listener_t *listener = DOWNCAST(listener_t, dll_node, listener_list.head);
- listener_free(listener);
- }
-
- called_already++;
+ SMARTLIST_FOREACH(listeners, listener_t *, lsn,
+ { listener_free(lsn); });
+ smartlist_free(listeners);
+ listeners = NULL;
}
/**
@@ -184,17 +175,13 @@ free_all_listeners(void)
*/
static void
simple_listener_cb(struct evconnlistener *evcl,
- evutil_socket_t fd, struct sockaddr *sourceaddr,
+ evutil_socket_t fd, struct sockaddr *sourceaddr,
int socklen, void *arg)
{
listener_t *lsn = arg;
struct event_base *base;
conn_t *conn = xzalloc(sizeof(conn_t));
- n_connections++; /* If we call conn_free() later on error, it will decrement
- * n_connections. Therefore, we had better increment it at
- * the start. */
-
log_debug("Got a connection attempt.");
conn->mode = lsn->proto_params->mode;
@@ -266,14 +253,15 @@ simple_listener_cb(struct evconnlistener *evcl,
bufferevent_enable(conn->output, EV_READ|EV_WRITE);
}
- /* add conn to the linked list of connections */
- if (dll_append(&conn_list, &conn->dll_node)<0)
- goto err;
+ /* add conn to the connection list */
+ if (!connections)
+ connections = smartlist_create();
+ smartlist_add(connections, conn);
log_debug("Connection setup completed. "
- "We currently have %d connections!", n_connections);
-
+ "We currently have %d connections!", smartlist_len(connections));
return;
+
err:
if (conn)
conn_free(conn);
@@ -296,39 +284,48 @@ conn_free(conn_t *conn)
if (conn->output)
bufferevent_free(conn->output);
- /* remove conn from the linked list of connections */
- dll_remove(&conn_list, &conn->dll_node);
- n_connections--;
-
memset(conn, 0x99, sizeof(conn_t));
free(conn);
+}
- obfs_assert(n_connections>=0);
+/**
+ Closes a fully open connection.
+*/
+static void
+close_conn(conn_t *conn)
+{
+ obfs_assert(connections);
+ smartlist_remove(connections, conn);
+ conn_free(conn);
log_debug("Connection destroyed. "
- "We currently have %d connections!", n_connections);
+ "We currently have %d connections!", smartlist_len(connections));
/** If this was the last connection AND we are shutting down,
finish shutdown. */
- if (!n_connections && shutting_down) {
- finish_shutdown();
+ if (smartlist_len(connections) == 0) {
+ smartlist_free(connections);
+ connections = NULL;
}
+
+ if (!connections && shutting_down)
+ finish_shutdown();
}
/**
Closes associated connection if the output evbuffer of 'bev' is
empty.
-*/
+*/
static void
close_conn_on_flush(struct bufferevent *bev, void *arg)
{
conn_t *conn = arg;
- if (0 == evbuffer_get_length(bufferevent_get_output(bev)))
- conn_free(conn);
+ if (evbuffer_get_length(bufferevent_get_output(bev)) == 0)
+ close_conn(conn);
}
-/**
- This callback is responsible for handling SOCKS traffic.
+/**
+ This callback is responsible for handling SOCKS traffic.
*/
static void
socks_read_cb(struct bufferevent *bev, void *arg)
@@ -357,7 +354,7 @@ socks_read_cb(struct bufferevent *bev, void *arg)
if (r < 0) {
/* XXXX send socks reply */
- conn_free(conn);
+ close_conn(conn);
return;
}
bufferevent_disable(conn->input, EV_READ|EV_WRITE);
@@ -372,7 +369,7 @@ socks_read_cb(struct bufferevent *bev, void *arg)
if (socks_ret == SOCKS_INCOMPLETE)
return; /* need to read more data. */
else if (socks_ret == SOCKS_BROKEN)
- conn_free(conn); /* XXXX maybe send socks reply */
+ close_conn(conn); /* XXXX maybe send socks reply */
else if (socks_ret == SOCKS_CMD_NOT_CONNECT) {
bufferevent_enable(bev, EV_WRITE);
bufferevent_disable(bev, EV_READ);
@@ -398,7 +395,7 @@ plaintext_read_cb(struct bufferevent *bev, void *arg)
if (proto_send(conn->proto,
bufferevent_get_input(bev),
bufferevent_get_output(other)) < 0)
- conn_free(conn);
+ close_conn(conn);
}
/**
@@ -420,7 +417,7 @@ obfuscated_read_cb(struct bufferevent *bev, void *arg)
bufferevent_get_output(other));
if (r == RECV_BAD)
- conn_free(conn);
+ close_conn(conn);
else if (r == RECV_SEND_PENDING)
proto_send(conn->proto,
bufferevent_get_input(conn->input),
@@ -439,7 +436,7 @@ error_or_eof(conn_t *conn,
if (conn->flushing || ! conn->is_open ||
0 == evbuffer_get_length(bufferevent_get_output(bev_flush))) {
- conn_free(conn);
+ close_conn(conn);
return;
}
diff --git a/src/network.h b/src/network.h
index e631697..7ba9afc 100644
--- a/src/network.h
+++ b/src/network.h
@@ -32,7 +32,6 @@ typedef struct listener_t listener_t;
listener_t *listener_new(struct event_base *base,
struct protocol_params_t *params);
-void listener_free(listener_t *listener);
void free_all_listeners(void);
void start_shutdown(int barbaric);
@@ -44,7 +43,6 @@ struct socks_state_t;
struct protocol_t;
typedef struct conn_t {
- dll_node_t dll_node;
struct socks_state_t *socks_state;
struct protocol_t *proto; /* ASN Do we like this here? We probably don't.
But it's so convenient!! So convenient! */
@@ -54,6 +52,7 @@ typedef struct conn_t {
unsigned int flushing : 1;
unsigned int is_open : 1;
} conn_t;
+
#endif
#endif
diff --git a/src/util.c b/src/util.c
index 9b9fa48..a4801a0 100644
--- a/src/util.c
+++ b/src/util.c
@@ -281,118 +281,6 @@ ascii_strlower(char *s)
}
}
-/************************ Doubly Linked List (DLL) ******************/
-
-/**
- Insert 'new_node' after 'node' in the doubly linked list 'list'.
-*/
-static void
-dll_insert_after(dll_t *list, dll_node_t *node, dll_node_t *new_node)
-{
- obfs_assert(node);
- obfs_assert(new_node);
-
- if (!list)
- return;
-
- new_node->prev = node;
- new_node->next = node->next;
- if (!node->next)
- list->tail = new_node;
- else
- node->next->prev = new_node;
- node->next = new_node;
-}
-
-/**
- Insert 'new_node' before 'node' in the doubly linked list 'list'.
-*/
-static void
-dll_insert_before(dll_t *list, dll_node_t *node, dll_node_t *new_node)
-{
- obfs_assert(node);
- obfs_assert(new_node);
-
- if (!list)
- return;
-
- new_node->prev = node->prev;
- new_node->next = node;
- if (!node->prev)
- list->head = new_node;
- else
- node->prev->next = new_node;
- node->prev = new_node;
-}
-
-/** Initialize <b>list</b> as an empty list. */
-void
-dll_init(dll_t *list)
-{
- list->head = list->tail = NULL;
-}
-
-/**
- Insert 'node' in the beginning of the doubly linked 'list'.
-*/
-static void
-dll_insert_beginning(dll_t *list, dll_node_t *node)
-{
- obfs_assert(node);
-
- if (!list)
- return;
-
- if (!list->head) {
- list->head = node;
- list->tail = node;
- node->prev = NULL;
- node->next = NULL;
- } else {
- dll_insert_before(list, list->head, node);
- }
-}
-
-/**
- Appends 'data' to the end of the doubly linked 'list'.
- Returns 1 on success, -1 on fail.
-*/
-int
-dll_append(dll_t *list, dll_node_t *node)
-{
- obfs_assert(list);
- obfs_assert(node);
-
- if (!list->tail)
- dll_insert_beginning(list, node);
- else
- dll_insert_after(list, list->tail, node);
-
- return 1;
-}
-
-/**
- Removes 'node' from the doubly linked list 'list'.
- It frees the list node, but leaves its data intact.
-*/
-void
-dll_remove(dll_t *list, dll_node_t *node)
-{
- obfs_assert(node);
-
- if (!list)
- return;
-
- if (!node->prev)
- list->head = node->next;
- else
- node->prev->next = node->next;
- if (!node->next)
- list->tail = node->prev;
- else
- node->next->prev = node->prev;
-}
-
/************************ Logging Subsystem *************************/
/** The code of this section was to a great extent shamelessly copied
off tor. It's basicaly a stripped down version of tor's logging
diff --git a/src/util.h b/src/util.h
index e44a711..a88d06c 100644
--- a/src/util.h
+++ b/src/util.h
@@ -6,10 +6,16 @@
#define UTIL_H
#include "config.h"
-#include <stdarg.h> /* for va_list */
-#include <stddef.h> /* size_t, offsetof, NULL, etc */
+#include <stdarg.h> /* va_list */
+#include <stddef.h> /* size_t, ptrdiff_t, offsetof, NULL */
#include <stdint.h> /* intN_t, uintN_t */
+struct sockaddr;
+struct event_base;
+struct evdns_base;
+
+/***** Type annotations. *****/
+
#ifndef __GNUC__
#define __attribute__(x) /* nothing */
#endif
@@ -19,10 +25,6 @@
#define ATTR_PRINTF_3 __attribute__((format(printf, 3, 4)))
#define ATTR_PURE __attribute__((pure))
-struct sockaddr;
-struct event_base;
-struct evdns_base;
-
/***** Memory allocation. *****/
/* Because this isn't Tor and functions named "tor_whatever" would be
@@ -37,11 +39,16 @@ 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;
+/***** Pseudo-inheritance. *****/
+
+#define DOWNCAST(container_type, element, ptr) \
+ (container_type*)( ((char*)ptr) - offsetof(container_type, element) )
+
/***** Math. *****/
unsigned int ui64_log2(uint64_t u64);
-/***** Network functions stuff. *****/
+/***** Network functions. *****/
int resolve_address_port(const char *address,
int nodns, int passive,
@@ -52,7 +59,7 @@ int resolve_address_port(const char *address,
struct evdns_base *get_evdns_base(void);
int init_evdns_base(struct event_base *base);
-/***** String functions stuff. *****/
+/***** String functions. *****/
static inline int ascii_isspace(unsigned char c)
{
@@ -72,31 +79,9 @@ int obfs_snprintf(char *str, size_t size,
const char *format, ...)
ATTR_PRINTF_3;
-/***** Doubly Linked List stuff. *****/
-
-#define DOWNCAST(container_type, element, ptr) \
- (container_type*)( ((char*)ptr) - offsetof(container_type, element) )
-
-/** A doubly linked list node.
- [algorithms ripped off Wikipedia (Doubly_linked_list) ] */
-typedef struct dll_node_t {
- struct dll_node_t *next, *prev;
-} dll_node_t;
-
-/** A doubly linked list. */
-typedef struct dll_t {
- struct dll_node_t *head;
- struct dll_node_t *tail;
-} dll_t;
-
-void dll_init(dll_t *list);
-int dll_append(dll_t *list, dll_node_t *node);
-void dll_remove(dll_t *list, dll_node_t *node);
-#define DLL_INIT() { NULL, NULL }
-
-/***** Logging subsystem stuff. *****/
+/***** Logging. *****/
-/** Logging methods */
+/** Log destinations */
/** Spit log messages on stdout. */
#define LOG_METHOD_STDOUT 1
1
0
commit 4e90322f70ceaeebc4308d0412262df2e714333b
Author: Zack Weinberg <zackw(a)panix.com>
Date: Wed Jul 20 15:14:12 2011 -0700
Add unit test for dummy protocol
---
Makefile.am | 5 +-
src/test/unittest.c | 6 +-
src/test/unittest_dummy.c | 200 +++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 207 insertions(+), 4 deletions(-)
diff --git a/Makefile.am b/Makefile.am
index ff518ad..fe47256 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -29,8 +29,9 @@ unittests_SOURCES = \
src/test/unittest.c \
src/test/unittest_container.c \
src/test/unittest_crypt.c \
- src/test/unittest_obfs2.c \
- src/test/unittest_socks.c
+ src/test/unittest_socks.c \
+ src/test/unittest_dummy.c \
+ src/test/unittest_obfs2.c
noinst_HEADERS = \
src/container.h \
diff --git a/src/test/unittest.c b/src/test/unittest.c
index f872550..6ff938e 100644
--- a/src/test/unittest.c
+++ b/src/test/unittest.c
@@ -7,14 +7,16 @@
extern struct testcase_t container_tests[];
extern struct testcase_t crypt_tests[];
-extern struct testcase_t obfs2_tests[];
extern struct testcase_t socks_tests[];
+extern struct testcase_t dummy_tests[];
+extern struct testcase_t obfs2_tests[];
struct testgroup_t groups[] = {
{ "container/", container_tests },
{ "crypt/", crypt_tests },
- { "obfs2/", obfs2_tests },
{ "socks/", socks_tests },
+ { "dummy/", dummy_tests },
+ { "obfs2/", obfs2_tests },
END_OF_GROUPS
};
diff --git a/src/test/unittest_dummy.c b/src/test/unittest_dummy.c
new file mode 100644
index 0000000..1739e1f
--- /dev/null
+++ b/src/test/unittest_dummy.c
@@ -0,0 +1,200 @@
+/* Copyright 2011 Nick Mathewson, George Kadianakis
+ See LICENSE for other credits and copying information
+*/
+
+#include "../util.h"
+#include "../protocol.h"
+#include "tinytest_macros.h"
+
+#include <event2/buffer.h>
+
+static void
+test_dummy_option_parsing(void *unused)
+{
+ struct option_parsing_case {
+ struct protocol_params_t *result;
+ short should_succeed;
+ short n_opts;
+ const char *const opts[4];
+ };
+ static struct option_parsing_case cases[] = {
+ /* wrong number of options */
+ { 0, 0, 1, {"dummy"} },
+ { 0, 0, 2, {"dummy", "client"} },
+ { 0, 0, 4, {"dummy", "client", "127.0.0.1:5552", "oops"} },
+ { 0, 0, 4, {"dummy", "--frobozz", "client", "127.0.0.1:5552"} },
+ /* unrecognized mode */
+ { 0, 0, 3, {"dummy", "floodcontrol", "127.0.0.1:5552" } },
+ /* bad address */
+ { 0, 0, 3, {"dummy", "client", "@:5552"} },
+ { 0, 0, 3, {"dummy", "client", "127.0.0.1:notanumber"} },
+ /* should succeed */
+ { 0, 1, 3, {"dummy", "client", "127.0.0.1:5552" } },
+ { 0, 1, 3, {"dummy", "client", "127.0.0.1" } },
+ { 0, 1, 3, {"dummy", "server", "127.0.0.1:5552" } },
+ { 0, 1, 3, {"dummy", "socks", "127.0.0.1:5552" } },
+
+ { 0, 0, 0, {0} }
+ };
+
+ /* Suppress logs for the duration of this function. */
+ log_set_method(LOG_METHOD_NULL, NULL);
+
+ struct option_parsing_case *c;
+ for (c = cases; c->n_opts; c++) {
+ c->result = proto_params_init(c->n_opts, c->opts);
+ if (c->should_succeed)
+ tt_ptr_op(c->result, !=, NULL);
+ else
+ tt_ptr_op(c->result, ==, NULL);
+ }
+
+ end:
+ for (c = cases; c->n_opts; c++)
+ if (c->result)
+ proto_params_free(c->result);
+
+ /* Unsuspend logging */
+ log_set_method(LOG_METHOD_STDOUT, NULL);
+}
+
+/* All the tests below use this test environment: */
+struct test_dummy_state
+{
+ struct protocol_params_t *proto_params_client;
+ struct protocol_params_t *proto_params_server;
+ struct protocol_t *client_proto;
+ struct protocol_t *server_proto;
+ struct evbuffer *output_buffer;
+ struct evbuffer *dummy_buffer;
+};
+
+static int
+cleanup_dummy_state(const struct testcase_t *unused, void *state)
+{
+ struct test_dummy_state *s = (struct test_dummy_state *)state;
+
+ if (s->client_proto)
+ proto_destroy(s->client_proto);
+ if (s->server_proto)
+ proto_destroy(s->server_proto);
+
+ if (s->proto_params_client)
+ proto_params_free(s->proto_params_client);
+ if (s->proto_params_server)
+ proto_params_free(s->proto_params_server);
+
+ if (s->output_buffer)
+ evbuffer_free(s->output_buffer);
+ if (s->dummy_buffer)
+ evbuffer_free(s->dummy_buffer);
+
+ free(state);
+ return 1;
+}
+
+#define ALEN(x) (sizeof x/sizeof x[0])
+
+static const char *const options_client[] =
+ {"dummy", "socks", "127.0.0.1:1800"};
+
+static const char *const options_server[] =
+ {"dummy", "server", "127.0.0.1:1800"};
+
+static void *
+setup_dummy_state(const struct testcase_t *unused)
+{
+ struct test_dummy_state *s = xzalloc(sizeof(struct test_dummy_state));
+
+ s->proto_params_client =
+ proto_params_init(ALEN(options_client), options_client);
+ tt_assert(s->proto_params_client);
+
+ s->proto_params_server =
+ proto_params_init(ALEN(options_server), options_server);
+ tt_assert(s->proto_params_server);
+
+ s->client_proto = proto_create(s->proto_params_client);
+ tt_assert(s->client_proto);
+
+ s->server_proto = proto_create(s->proto_params_server);
+ tt_assert(s->server_proto);
+
+ s->output_buffer = evbuffer_new();
+ tt_assert(s->output_buffer);
+
+ s->dummy_buffer = evbuffer_new();
+ tt_assert(s->dummy_buffer);
+
+ return s;
+
+ end:
+ cleanup_dummy_state(NULL, s);
+ return NULL;
+}
+
+static const struct testcase_setup_t dummy_fixture =
+ { setup_dummy_state, cleanup_dummy_state };
+
+static void
+test_dummy_transfer(void *state)
+{
+ struct test_dummy_state *s = (struct test_dummy_state *)state;
+ int n;
+ struct evbuffer_iovec v[2];
+
+ /* Call the handshake method to satisfy the high-level contract,
+ even though dummy doesn't use a handshake */
+ tt_int_op(proto_handshake(s->client_proto, s->output_buffer), >=, 0);
+
+ /* That should have put nothing into the output buffer */
+ tt_int_op(evbuffer_get_length(s->output_buffer), ==, 0);
+
+ /* Ditto on the server side */
+ tt_int_op(proto_handshake(s->server_proto, s->output_buffer), >=, 0);
+ tt_int_op(evbuffer_get_length(s->output_buffer), ==, 0);
+
+ const char *msg1 = "this is a 54-byte message passed from client to server";
+ const char *msg2 = "this is a 55-byte message passed from server to client!";
+
+ /* client -> server */
+ evbuffer_add(s->dummy_buffer, msg1, 54);
+ proto_send(s->client_proto, s->dummy_buffer, s->output_buffer);
+
+ tt_assert(RECV_GOOD == proto_recv(s->server_proto, s->output_buffer,
+ s->dummy_buffer));
+
+ n = evbuffer_peek(s->dummy_buffer, -1, NULL, &v[0], 2);
+ tt_int_op(n, ==, 1); /* expect contiguous data */
+ tt_int_op(0, ==, strncmp(msg1, v[0].iov_base, 54));
+
+ /* emptying dummy_buffer before next test */
+ size_t buffer_len = evbuffer_get_length(s->dummy_buffer);
+ tt_int_op(0, ==, evbuffer_drain(s->dummy_buffer, buffer_len));
+
+ /* client <- server */
+ evbuffer_add(s->dummy_buffer, msg2, 55);
+ tt_int_op(0, <=, proto_send(s->server_proto, s->dummy_buffer,
+ s->output_buffer));
+
+ tt_assert(RECV_GOOD == proto_recv(s->client_proto, s->output_buffer,
+ s->dummy_buffer));
+
+ n = evbuffer_peek(s->dummy_buffer, -1, NULL, &v[1], 2);
+ tt_int_op(n, ==, 1); /* expect contiguous data */
+ tt_int_op(0, ==, strncmp(msg2, v[1].iov_base, 55));
+
+ end:;
+}
+
+#define T(name) \
+ { #name, test_dummy_##name, 0, NULL, NULL }
+
+#define TF(name) \
+ { #name, test_dummy_##name, 0, &dummy_fixture, NULL }
+
+struct testcase_t dummy_tests[] = {
+ T(option_parsing),
+ TF(transfer),
+ END_OF_TESTCASES
+};
1
0