Merge remote-tracking branch 'public/benchmark'

8 files changed, 355 insertions, 106 deletions

diff --git a/.gitignore b/.gitignore
index 610965b858..26e9e3808a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -144,6 +144,8 @@
 # /src/test
 /src/test/Makefile
 /src/test/Makefile.in
+/src/test/bench
+/src/test/bench.exe
 /src/test/test
 /src/test/test-child
 /src/test/test.exe
diff --git a/changes/bench b/changes/bench
new file mode 100644
index 0000000000..4479988e61
--- /dev/null
+++ b/changes/bench
@@ -0,0 +1,6 @@
+  o Testing
+    - The long-disabled benchmark tests are now split into their own
+      ./src/test/bench binary.
+    - The benchmarks can now use more accurate timers than gettimeofday
+      when such are available.
+
diff --git a/configure.in b/configure.in
index 17f5c8d5e3..d13b54d93f 100644
--- a/configure.in
+++ b/configure.in
@@ -276,6 +276,7 @@ AC_SEARCH_LIBS(socket, [socket])
 AC_SEARCH_LIBS(gethostbyname, [nsl])
 AC_SEARCH_LIBS(dlopen, [dl])
 AC_SEARCH_LIBS(inet_aton, [resolv])
+AC_SEARCH_LIBS([clock_gettime], [rt], [have_rt=yes])
 
 if test "$enable_threads" = "yes"; then
   AC_SEARCH_LIBS(pthread_create, [pthread])
@@ -288,6 +289,7 @@ dnl exports strlcpy without defining it in a header.
 
 AC_CHECK_FUNCS(
 	accept4 \
+	clock_gettime \
         flock \
         ftime \
         getaddrinfo \
@@ -363,9 +365,6 @@ dnl On Gnu/Linux or any place we require it, we'll add librt to the Libevent
 dnl linking for static builds.
 STATIC_LIBEVENT_FLAGS=""
 if test "$enable_static_libevent" = "yes"; then
-    dnl Determine if we have clock_gettime in librt
-    AC_SEARCH_LIBS([clock_gettime], [rt],
-        [have_rt=yes])
     if test "$have_rt" = yes; then
       STATIC_LIBEVENT_FLAGS=" -lrt "
     fi
diff --git a/src/or/relay.c b/src/or/relay.c
index 51a29a20ee..ac3114bda5 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -11,6 +11,7 @@
  **/
 
 #include <math.h>
+#define RELAY_PRIVATE
 #include "or.h"
 #include "buffers.h"
 #include "circuitbuild.h"
@@ -33,9 +34,6 @@
 #include "routerlist.h"
 #include "routerparse.h"
 
-static int relay_crypt(circuit_t *circ, cell_t *cell,
-                       cell_direction_t cell_direction,
-                       crypt_path_t **layer_hint, char *recognized);
 static edge_connection_t *relay_lookup_conn(circuit_t *circ, cell_t *cell,
                                             cell_direction_t cell_direction,
                                             crypt_path_t *layer_hint);
@@ -297,7 +295,7 @@ circuit_receive_relay_cell(cell_t *cell, circuit_t *circ,
  * Return -1 to indicate that we should mark the circuit for close,
  * else return 0.
  */
-static int
+int
 relay_crypt(circuit_t *circ, cell_t *cell, cell_direction_t cell_direction,
             crypt_path_t **layer_hint, char *recognized)
 {
diff --git a/src/or/relay.h b/src/or/relay.h
index 7fce8edcaf..1cd4008bb9 100644
--- a/src/or/relay.h
+++ b/src/or/relay.h
@@ -66,5 +66,10 @@ void circuit_clear_cell_queue(circuit_t *circ, or_connection_t *orconn);
 
 void tor_gettimeofday_cache_clear(void);
 
+#ifdef RELAY_PRIVATE
+int relay_crypt(circuit_t *circ, cell_t *cell, cell_direction_t cell_direction,
+                crypt_path_t **layer_hint, char *recognized);
+#endif
+
 #endif
 
diff --git a/src/test/Makefile.am b/src/test/Makefile.am
index 301452b4ec..ffe1f942e7 100644
--- a/src/test/Makefile.am
+++ b/src/test/Makefile.am
@@ -1,6 +1,6 @@
 TESTS = test
 
-noinst_PROGRAMS = test test-child
+noinst_PROGRAMS = test test-child bench
 
 AM_CPPFLAGS = -DSHARE_DATADIR="\"$(datadir)\"" \
         -DLOCALSTATEDIR="\"$(localstatedir)\"" \
@@ -23,6 +23,9 @@ test_SOURCES = \
 	test_util.c \
 	tinytest.c
 
+bench_SOURCES = \
+	bench.c
+
 test_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \
         @TOR_LDFLAGS_libevent@
 test_LDADD = ../or/libtor.a ../common/libor.a ../common/libor-crypto.a \
@@ -30,6 +33,13 @@ test_LDADD = ../or/libtor.a ../common/libor.a ../common/libor-crypto.a \
 	@TOR_ZLIB_LIBS@ -lm @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
 	@TOR_LIB_WS32@ @TOR_LIB_GDI@
 
+bench_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \
+        @TOR_LDFLAGS_libevent@
+bench_LDADD = ../or/libtor.a ../common/libor.a ../common/libor-crypto.a \
+	../common/libor-event.a \
+	@TOR_ZLIB_LIBS@ -lm @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
+	@TOR_LIB_WS32@ @TOR_LIB_GDI@
+
 noinst_HEADERS = \
 	tinytest.h \
 	tinytest_macros.h \
diff --git a/src/test/bench.c b/src/test/bench.c
new file mode 100644
index 0000000000..ff2794e7c7
--- /dev/null
+++ b/src/test/bench.c
@@ -0,0 +1,327 @@
+/* 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 */
+
+/* Ordinarily defined in tor_main.c; this bit is just here to provide one
+ * since we're not linking to tor_main.c */
+const char tor_git_revision[] = "";
+
+/**
+ * \file bench.c
+ * \brief Benchmarks for lower level Tor modules.
+ **/
+
+#include "orconfig.h"
+
+#define RELAY_PRIVATE
+
+#include "or.h"
+#include "relay.h"
+
+#if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID)
+static uint64_t nanostart;
+static inline uint64_t
+timespec_to_nsec(const struct timespec *ts)
+{
+  return ((uint64_t)ts->tv_sec)*1000000000 + ts->tv_nsec;
+}
+
+static void
+reset_perftime(void)
+{
+  struct timespec ts;
+  int r;
+  r = clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
+  tor_assert(r == 0);
+  nanostart = timespec_to_nsec(&ts);
+}
+
+static uint64_t
+perftime(void)
+{
+  struct timespec ts;
+  int r;
+  r = clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
+  tor_assert(r == 0);
+  return timespec_to_nsec(&ts) - nanostart;
+}
+
+#else
+static struct timeval tv_start = { 0, 0 };
+static void
+reset_perftime(void)
+{
+  tor_gettimeofday(&tv_start);
+}
+static uint64_t
+perftime(void)
+{
+  struct timeval now, out;
+  tor_gettimeofday(&now);
+  timersub(&now, &tv_start, &out);
+  return ((uint64_t)out.tv_sec)*1000000000 + out.tv_usec*1000;
+}
+#endif
+
+#define NANOCOUNT(start,end,iters) \
+  ( ((double)((end)-(start))) / (iters) )
+
+/** Run AES performance benchmarks. */
+static void
+bench_aes(void)
+{
+  int len, i;
+  char *b1, *b2;
+  crypto_cipher_env_t *c;
+  uint64_t start, end;
+  const int bytes_per_iter = (1<<24);
+  reset_perftime();
+  c = crypto_new_cipher_env();
+  crypto_cipher_generate_key(c);
+  crypto_cipher_encrypt_init_cipher(c);
+  for (len = 1; len <= 8192; len *= 2) {
+    int iters = bytes_per_iter / len;
+    b1 = tor_malloc_zero(len);
+    b2 = tor_malloc_zero(len);
+    start = perftime();
+    for (i = 0; i < iters; ++i) {
+      crypto_cipher_encrypt(c, b1, b2, len);
+    }
+    end = perftime();
+    tor_free(b1);
+    tor_free(b2);
+    printf("%d bytes: %.2f nsec per byte\n", len,
+           NANOCOUNT(start, end, iters*len));
+  }
+  crypto_free_cipher_env(c);
+}
+
+static void
+bench_cell_aes(void)
+{
+  uint64_t start, end;
+  const int len = 509;
+  const int iters = (1<<16);
+  const int max_misalign = 15;
+  char *b = tor_malloc(len+max_misalign);
+  crypto_cipher_env_t *c;
+  int i, misalign;
+
+  c = crypto_new_cipher_env();
+  crypto_cipher_generate_key(c);
+  crypto_cipher_encrypt_init_cipher(c);
+
+  reset_perftime();
+  for (misalign = 0; misalign <= max_misalign; ++misalign) {
+    start = perftime();
+    for (i = 0; i < iters; ++i) {
+      crypto_cipher_crypt_inplace(c, b+misalign, len);
+    }
+    end = perftime();
+    printf("%d bytes, misaligned by %d: %.2f nsec per byte\n", len, misalign,
+           NANOCOUNT(start, end, iters*len));
+  }
+
+  crypto_free_cipher_env(c);
+  tor_free(b);
+}
+
+/** Run digestmap_t performance benchmarks. */
+static void
+bench_dmap(void)
+{
+  smartlist_t *sl = smartlist_create();
+  smartlist_t *sl2 = smartlist_create();
+  uint64_t start, end, pt2, pt3, pt4;
+  int iters = 8192;
+  const int elts = 4000;
+  const int fpostests = 100000;
+  char d[20];
+  int i,n=0, fp = 0;
+  digestmap_t *dm = digestmap_new();
+  digestset_t *ds = digestset_new(elts);
+
+  for (i = 0; i < elts; ++i) {
+    crypto_rand(d, 20);
+    smartlist_add(sl, tor_memdup(d, 20));
+  }
+  for (i = 0; i < elts; ++i) {
+    crypto_rand(d, 20);
+    smartlist_add(sl2, tor_memdup(d, 20));
+  }
+  printf("nbits=%d\n", ds->mask+1);
+
+  reset_perftime();
+
+  start = perftime();
+  for (i = 0; i < iters; ++i) {
+    SMARTLIST_FOREACH(sl, const char *, cp, digestmap_set(dm, cp, (void*)1));
+  }
+  pt2 = perftime();
+  printf("digestmap_set: %.2f ns per element\n",
+         NANOCOUNT(start, pt2, iters*elts));
+
+  for (i = 0; i < iters; ++i) {
+    SMARTLIST_FOREACH(sl, const char *, cp, digestmap_get(dm, cp));
+    SMARTLIST_FOREACH(sl2, const char *, cp, digestmap_get(dm, cp));
+  }
+  pt3 = perftime();
+  printf("digestmap_get: %.2f ns per element\n",
+         NANOCOUNT(pt2, pt3, iters*elts*2));
+
+  for (i = 0; i < iters; ++i) {
+    SMARTLIST_FOREACH(sl, const char *, cp, digestset_add(ds, cp));
+  }
+  pt4 = perftime();
+  printf("digestset_add: %.2f ns per element\n",
+         NANOCOUNT(pt3, pt4, iters*elts));
+
+  for (i = 0; i < iters; ++i) {
+    SMARTLIST_FOREACH(sl, const char *, cp, n += digestset_isin(ds, cp));
+    SMARTLIST_FOREACH(sl2, const char *, cp, n += digestset_isin(ds, cp));
+  }
+  end = perftime();
+  printf("digestset_isin: %.2f ns per element.\n",
+         NANOCOUNT(pt4, end, iters*elts*2));
+  /* We need to use this, or else the whole loop gets optimized out. */
+  printf("Hits == %d\n", n);
+
+  for (i = 0; i < fpostests; ++i) {
+    crypto_rand(d, 20);
+    if (digestset_isin(ds, d)) ++fp;
+  }
+  printf("False positive rate on digestset: %.2f%%\n",
+         (fp/(double)fpostests)*100);
+
+  digestmap_free(dm, NULL);
+  digestset_free(ds);
+  SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
+  SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
+  smartlist_free(sl);
+  smartlist_free(sl2);
+}
+
+static void
+bench_cell_ops(void)
+{
+  const int iters = 1<<16;
+  int i;
+
+  /* benchmarks for cell ops at relay. */
+  or_circuit_t *or_circ = tor_malloc_zero(sizeof(or_circuit_t));
+  cell_t *cell = tor_malloc(sizeof(cell_t));
+  int outbound;
+  uint64_t start, end;
+
+  crypto_rand((char*)cell->payload, sizeof(cell->payload));
+
+  /* Mock-up or_circuit_t */
+  or_circ->_base.magic = OR_CIRCUIT_MAGIC;
+  or_circ->_base.purpose = CIRCUIT_PURPOSE_OR;
+
+  /* Initialize crypto */
+  or_circ->p_crypto = crypto_new_cipher_env();
+  crypto_cipher_generate_key(or_circ->p_crypto);
+  crypto_cipher_encrypt_init_cipher(or_circ->p_crypto);
+  or_circ->n_crypto = crypto_new_cipher_env();
+  crypto_cipher_generate_key(or_circ->n_crypto);
+  crypto_cipher_encrypt_init_cipher(or_circ->n_crypto);
+  or_circ->p_digest = crypto_new_digest_env();
+  or_circ->n_digest = crypto_new_digest_env();
+
+  reset_perftime();
+
+  for (outbound = 0; outbound <= 1; ++outbound) {
+    cell_direction_t d = outbound ? CELL_DIRECTION_OUT : CELL_DIRECTION_IN;
+    start = perftime();
+    for (i = 0; i < iters; ++i) {
+      char recognized = 0;
+      crypt_path_t *layer_hint = NULL;
+      relay_crypt(TO_CIRCUIT(or_circ), cell, d, &layer_hint, &recognized);
+    }
+    end = perftime();
+    printf("%sbound cells: %.2f ns per cell. (%.2f ns per byte of payload)\n",
+           outbound?"Out":" In",
+           NANOCOUNT(start,end,iters),
+           NANOCOUNT(start,end,iters*CELL_PAYLOAD_SIZE));
+  }
+
+  crypto_free_digest_env(or_circ->p_digest);
+  crypto_free_digest_env(or_circ->n_digest);
+  crypto_free_cipher_env(or_circ->p_crypto);
+  crypto_free_cipher_env(or_circ->n_crypto);
+  tor_free(or_circ);
+  tor_free(cell);
+}
+
+typedef void (*bench_fn)(void);
+
+typedef struct benchmark_t {
+  const char *name;
+  bench_fn fn;
+  int enabled;
+} benchmark_t;
+
+#define ENT(s) { #s , bench_##s, 0 }
+
+static struct benchmark_t benchmarks[] = {
+  ENT(dmap),
+  ENT(aes),
+  ENT(cell_aes),
+  ENT(cell_ops),
+  {NULL,NULL,0}
+};
+
+static benchmark_t *
+find_benchmark(const char *name)
+{
+  benchmark_t *b;
+  for (b = benchmarks; b->name; ++b) {
+    if (!strcmp(name, b->name)) {
+      return b;
+    }
+  }
+  return NULL;
+}
+
+/** Main entry point for benchmark code: parse the command line, and run
+ * some benchmarks. */
+int
+main(int argc, const char **argv)
+{
+  int i;
+  int list=0, n_enabled=0;
+  benchmark_t *b;
+
+  tor_threads_init();
+
+  for (i = 1; i < argc; ++i) {
+    if (!strcmp(argv[i], "--list")) {
+      list = 1;
+    } else {
+      benchmark_t *b = find_benchmark(argv[i]);
+      ++n_enabled;
+      if (b) {
+        b->enabled = 1;
+      } else {
+        printf("No such benchmark as %s\n", argv[i]);
+      }
+    }
+  }
+
+  reset_perftime();
+
+  crypto_seed_rng(1);
+
+  for (b = benchmarks; b->name; ++b) {
+    if (b->enabled || n_enabled == 0) {
+      printf("===== %s =====\n", b->name);
+      if (!list)
+        b->fn();
+    }
+  }
+
+  return 0;
+}
+
diff --git a/src/test/test.c b/src/test/test.c
index 185bf5a30c..d4edf1484b 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -1265,102 +1265,6 @@ test_policies(void)
   }
 }
 
-/** Run AES performance benchmarks. */
-static void
-test_bench_aes(void)
-{
-  int len, i;
-  char *b1, *b2;
-  crypto_cipher_env_t *c;
-  struct timeval start, end;
-  const int iters = 100000;
-  uint64_t nsec;
-  c = crypto_new_cipher_env();
-  crypto_cipher_generate_key(c);
-  crypto_cipher_encrypt_init_cipher(c);
-  for (len = 1; len <= 8192; len *= 2) {
-    b1 = tor_malloc_zero(len);
-    b2 = tor_malloc_zero(len);
-    tor_gettimeofday(&start);
-    for (i = 0; i < iters; ++i) {
-      crypto_cipher_encrypt(c, b1, b2, len);
-    }
-    tor_gettimeofday(&end);
-    tor_free(b1);
-    tor_free(b2);
-    nsec = (uint64_t) tv_udiff(&start,&end);
-    nsec *= 1000;
-    nsec /= (iters*len);
-    printf("%d bytes: "U64_FORMAT" nsec per byte\n", len,
-           U64_PRINTF_ARG(nsec));
-  }
-  crypto_free_cipher_env(c);
-}
-
-/** Run digestmap_t performance benchmarks. */
-static void
-test_bench_dmap(void)
-{
-  smartlist_t *sl = smartlist_create();
-  smartlist_t *sl2 = smartlist_create();
-  struct timeval start, end, pt2, pt3, pt4;
-  const int iters = 10000;
-  const int elts = 4000;
-  const int fpostests = 1000000;
-  char d[20];
-  int i,n=0, fp = 0;
-  digestmap_t *dm = digestmap_new();
-  digestset_t *ds = digestset_new(elts);
-
-  for (i = 0; i < elts; ++i) {
-    crypto_rand(d, 20);
-    smartlist_add(sl, tor_memdup(d, 20));
-  }
-  for (i = 0; i < elts; ++i) {
-    crypto_rand(d, 20);
-    smartlist_add(sl2, tor_memdup(d, 20));
-  }
-  printf("nbits=%d\n", ds->mask+1);
-
-  tor_gettimeofday(&start);
-  for (i = 0; i < iters; ++i) {
-    SMARTLIST_FOREACH(sl, const char *, cp, digestmap_set(dm, cp, (void*)1));
-  }
-  tor_gettimeofday(&pt2);
-  for (i = 0; i < iters; ++i) {
-    SMARTLIST_FOREACH(sl, const char *, cp, digestmap_get(dm, cp));
-    SMARTLIST_FOREACH(sl2, const char *, cp, digestmap_get(dm, cp));
-  }
-  tor_gettimeofday(&pt3);
-  for (i = 0; i < iters; ++i) {
-    SMARTLIST_FOREACH(sl, const char *, cp, digestset_add(ds, cp));
-  }
-  tor_gettimeofday(&pt4);
-  for (i = 0; i < iters; ++i) {
-    SMARTLIST_FOREACH(sl, const char *, cp, n += digestset_isin(ds, cp));
-    SMARTLIST_FOREACH(sl2, const char *, cp, n += digestset_isin(ds, cp));
-  }
-  tor_gettimeofday(&end);
-
-  for (i = 0; i < fpostests; ++i) {
-    crypto_rand(d, 20);
-    if (digestset_isin(ds, d)) ++fp;
-  }
-
-  printf("%ld\n",(unsigned long)tv_udiff(&start, &pt2));
-  printf("%ld\n",(unsigned long)tv_udiff(&pt2, &pt3));
-  printf("%ld\n",(unsigned long)tv_udiff(&pt3, &pt4));
-  printf("%ld\n",(unsigned long)tv_udiff(&pt4, &end));
-  printf("-- %d\n", n);
-  printf("++ %f\n", fp/(double)fpostests);
-  digestmap_free(dm, NULL);
-  digestset_free(ds);
-  SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
-  SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
-  smartlist_free(sl);
-  smartlist_free(sl2);
-}
-
 /** Test encoding and parsing of rendezvous service descriptors. */
 static void
 test_rend_fns(void)
@@ -1913,8 +1817,6 @@ static struct testcase_t test_array[] = {
   ENT(geoip),
   FORK(stats),
 
-  DISABLED(bench_aes),
-  DISABLED(bench_dmap),
   END_OF_TESTCASES
 };