summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarkus Teich <markus.teich@stusta.mhn.de>2017-02-14 13:36:54 +0100
committerMarkus Teich <markus.teich@stusta.mhn.de>2017-02-14 13:36:54 +0100
commit0ba069aeaed8fb8e8e888b586cbc03bd7402daf3 (patch)
tree1ea1b30c78481fa9b82dc22efabc15a8937bb418
parent1b29de8ebed6a619d840f0e11cf010ff79683b00 (diff)
add benchmarking tool
-rw-r--r--Makefile.am6
-rw-r--r--bench.c495
2 files changed, 501 insertions, 0 deletions
diff --git a/Makefile.am b/Makefile.am
index b4f41d1..d3cd53e 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -18,6 +18,12 @@ libbrandt_la_LIBADD = \
libbrandt_la_LDFLAGS = \
-version-info 0:0:0
+noinst_PROGRAMS = \
+ bench
+
+bench_SOURCES = bench.c
+bench_LDADD = libbrandt.la -lgcrypt -lgpg-error -lgnunetutil
+
check_PROGRAMS = \
test_crypto \
test_brandt
diff --git a/bench.c b/bench.c
new file mode 100644
index 0000000..a38dc93
--- /dev/null
+++ b/bench.c
@@ -0,0 +1,495 @@
+/* This file is part of libbrandt.
+ * Copyright (C) 2016 GNUnet e.V.
+ *
+ * libbrandt is free software: you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later
+ * version.
+ *
+ * libbrandt is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * libbrandt. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file test_brandt.c
+ * @brief testing API functions.
+ * @author Markus Teich
+ */
+
+#include "platform.h"
+
+#include <gnunet/gnunet_util_lib.h>
+
+#include "brandt.h"
+#include "crypto.h"
+#include "util.h"
+
+#define MIN(A, B) ((A) < (B) ? (A) : (B))
+
+struct msg {
+ uint16_t sender;
+ uint16_t receiver;
+ void *buf;
+ size_t buf_len;
+};
+
+struct testcase {
+ uint16_t n;
+ uint16_t k;
+ uint16_t *bids;
+ uint16_t m;
+ uint16_t outcome_public;
+ uint16_t ret;
+ struct BRANDT_Auction **ad;
+ uint16_t *id;
+ uint16_t *result_called;
+};
+
+
+static struct testcase tcase;
+static struct GNUNET_CRYPTO_EccDlogContext *edc;
+
+
+static struct BRANDT_Result *
+expected_outcome (uint16_t i, uint16_t *rlen)
+{
+ struct BRANDT_Result *ret = NULL;
+ int32_t highest_bidder = -1;
+ int32_t highest_bid = -1;
+ int32_t mpf_highest_bidder;
+ int32_t mpf_highest_bid = -1;
+ int32_t prev_mpf_highest_bidder = -1;
+ uint16_t winners = MIN (tcase.m, tcase.n);
+ uint16_t cur_winner = 0;
+
+ *rlen = 0;
+
+ if (0 == tcase.n)
+ return NULL;
+
+ if (0 == tcase.m)
+ {
+ for (uint16_t h = 0; h < tcase.n; h++)
+ if (tcase.bids[h] > highest_bid)
+ highest_bid = tcase.bids[highest_bidder = h];
+
+ if (!tcase.outcome_public && !(i == highest_bidder || i == tcase.n))
+ return NULL;
+
+ ret = GNUNET_new (struct BRANDT_Result);
+ ret->bidder = highest_bidder;
+ ret->price = highest_bid;
+ ret->status = BRANDT_bidder_won;
+ *rlen = 1;
+ return ret;
+ }
+
+ /* fewer bidders than needed -> everyone wins with lowest price */
+ if (tcase.n <= tcase.m)
+ {
+ if (tcase.outcome_public || i == tcase.n)
+ {
+ ret = GNUNET_new_array ((*rlen = tcase.n), struct BRANDT_Result);
+ for (uint16_t h = 0; h < tcase.n; h++)
+ {
+ ret[h].bidder = h;
+ ret[h].price = 0;
+ ret[h].status = BRANDT_bidder_won;
+ }
+ }
+ else
+ {
+ ret = GNUNET_new (struct BRANDT_Result);
+ ret->bidder = i;
+ ret->price = 0;
+ ret->status = BRANDT_bidder_won;
+ *rlen = 1;
+ }
+ return ret;
+ }
+
+ /* find M+1st highest bidder to determine selling price */
+ for (uint16_t h = 0; h < tcase.n; h++)
+ if (tcase.bids[h] > mpf_highest_bid)
+ mpf_highest_bid = tcase.bids[prev_mpf_highest_bidder = h];
+ for (uint16_t m = 0; m < MIN (tcase.m, tcase.n - 1); m++)
+ {
+ mpf_highest_bidder = -1;
+ mpf_highest_bid = -1;
+ for (uint16_t h = 0; h < tcase.n; h++)
+ {
+ if (tcase.bids[h] > mpf_highest_bid &&
+ (tcase.bids[h] < tcase.bids[prev_mpf_highest_bidder] ||
+ (tcase.bids[h] == tcase.bids[prev_mpf_highest_bidder] &&
+ h > prev_mpf_highest_bidder)))
+ {
+ mpf_highest_bid = tcase.bids[mpf_highest_bidder = h];
+ }
+ }
+ prev_mpf_highest_bidder = mpf_highest_bidder;
+ }
+
+ /* for simplicity always locate the big block if we need to report at
+ * least one winner. with private outcome for losing bidders or winners
+ * only none or one element will be used respectively. */
+ if (tcase.outcome_public || i == tcase.n ||
+ tcase.bids[i] > mpf_highest_bid ||
+ (tcase.bids[i] == mpf_highest_bid && i < mpf_highest_bidder))
+ ret = GNUNET_new_array (winners, struct BRANDT_Result);
+
+ /* report winners */
+ for (uint16_t h = 0; h < tcase.n; h++)
+ {
+ if (((tcase.bids[h] == mpf_highest_bid && h < mpf_highest_bidder) ||
+ tcase.bids[h] > mpf_highest_bid) && /* h is a winner */
+ (tcase.outcome_public || i == h || i == tcase.n)) /* needs report */
+ {
+ if (cur_winner >= winners)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "got too many winners\n");
+ _exit (1);
+ }
+ ret[cur_winner].bidder = h;
+ ret[cur_winner].price = mpf_highest_bid;
+ ret[cur_winner].status = BRANDT_bidder_won;
+ cur_winner++;
+ }
+ }
+ *rlen = cur_winner;
+ return ret;
+}
+
+
+static void
+bidder_start (void *arg)
+{
+ uint16_t i = *(uint16_t *)arg;
+
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO, "starting bidder %d\n", i);
+ BRANDT_bidder_start (tcase.ad[i], i, tcase.n);
+}
+
+
+static void
+transfer_message (void *arg)
+{
+ struct msg *m = (struct msg *)arg;
+ struct msg_head *h = (struct msg_head *)m->buf;
+
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO, "xfer msg %d %p from %d to %d\n",
+ ntohl (h->msg_type), arg, m->sender, m->receiver);
+ BRANDT_got_message (tcase.ad[m->receiver], m->sender, m->buf, m->buf_len);
+ GNUNET_free (m->buf);
+ GNUNET_free (m);
+}
+
+
+static uint16_t
+cb_start (void *auction_closure)
+{
+ uint16_t *s = (uint16_t *)auction_closure;
+
+ if (tcase.n != *s)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "start callback called from bidder\n");
+ _exit (1);
+ }
+
+ for (uint16_t i = 0; i < tcase.n; i++)
+ GNUNET_SCHEDULER_add_now (&bidder_start, &tcase.id[i]);
+
+ return tcase.n;
+}
+
+
+static int
+cb_broadcast (void *auction_closure,
+ const void *msg,
+ size_t msg_len)
+{
+ uint16_t *s = (uint16_t *)auction_closure;
+ struct msg *m;
+
+ for (uint16_t i = 0; i <= tcase.n; i++)
+ {
+ if (i == *s)
+ continue;
+ m = GNUNET_new (struct msg);
+ m->sender = *s;
+ m->receiver = i;
+ m->buf = GNUNET_new_array (msg_len, unsigned char);
+ memcpy (m->buf, msg, msg_len);
+ m->buf_len = msg_len;
+ GNUNET_SCHEDULER_add_now (&transfer_message, m);
+ }
+ return 0;
+}
+
+
+static int
+cb_unicast (void *auction_closure,
+ const void *msg,
+ size_t msg_len)
+{
+ uint16_t *s = (uint16_t *)auction_closure;
+ struct msg *m;
+
+ m = GNUNET_new (struct msg);
+ m->sender = *s;
+ m->receiver = tcase.n; /* == seller */
+ m->buf = GNUNET_new_array (msg_len, unsigned char);
+ memcpy (m->buf, msg, msg_len);
+ m->buf_len = msg_len;
+ GNUNET_SCHEDULER_add_now (&transfer_message, m);
+
+ return 0;
+}
+
+
+static void
+cb_result (void *auction_closure,
+ struct BRANDT_Result results[],
+ uint16_t results_len)
+{
+ uint16_t *s = (uint16_t *)auction_closure;
+ uint16_t mustlen = -1;
+ struct BRANDT_Result *must = expected_outcome (*s, &mustlen);
+
+ if (mustlen != results_len)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+ "expected result len is: %d\n",
+ mustlen);
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+ "computed result len is: %d (by agent %d)\n",
+ results_len,
+ *s);
+ tcase.ret = 1;
+ goto quit;
+ }
+
+ if (0 == results_len && NULL != must)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+ "expected result is: %p\n",
+ (void *)must);
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+ "computed result is: (nil) (by agent %d)\n",
+ *s);
+
+ tcase.ret = 1;
+ }
+
+ for (uint16_t i = 0; i < results_len; i++)
+ {
+ GNUNET_log (
+ GNUNET_ERROR_TYPE_INFO,
+ "expected result is: bidder %d got status %d with price %d\n",
+ must[i].bidder,
+ must[i].status,
+ must[i].price);
+ GNUNET_log (
+ GNUNET_ERROR_TYPE_INFO,
+ "computed result is: bidder %d got status %d with price %d (by agent %d)\n",
+ results[i].bidder,
+ results[i].status,
+ results[i].price,
+ *s);
+
+ if (NULL == must ||
+ must[i].bidder != results[i].bidder ||
+ must[i].status != results[i].status ||
+ must[i].price != results[i].price)
+ tcase.ret = 1;
+ }
+
+quit:
+ tcase.result_called[*s] = 1;
+ if (must)
+ GNUNET_free (must);
+}
+
+
+static void
+run_auction (void *arg)
+{
+ void *desc;
+ size_t desc_len;
+
+ tcase.ad[tcase.n] = BRANDT_new (&cb_result,
+ &cb_broadcast,
+ &cb_start,
+ &tcase.id[tcase.n],
+ &desc,
+ &desc_len,
+ GNUNET_TIME_absolute_get (),
+ GNUNET_TIME_UNIT_MINUTES,
+ tcase.k, /* number of prizes */
+ tcase.m, /* m */
+ tcase.outcome_public, /* outcome public */
+ tcase.outcome_public ? edc : NULL);
+ if (!tcase.ad[tcase.n])
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "BRANDT_new() failed.\n");
+ _exit (1);
+ }
+
+ for (uint16_t i = 0; i < tcase.n; i++)
+ {
+ tcase.ad[i] = BRANDT_join (&cb_result,
+ &cb_broadcast,
+ &cb_unicast,
+ &tcase.id[i],
+ desc,
+ desc_len,
+ tcase.bids[i], /* bid */
+ tcase.outcome_public ? edc : NULL);
+ if (!tcase.ad[i])
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "BRANDT_join() failed.\n");
+ tcase.ret = 1;
+ return;
+ }
+
+ if (tcase.ad[tcase.n]->k != tcase.ad[i]->k ||
+ tcase.ad[tcase.n]->m != tcase.ad[i]->m ||
+ tcase.ad[tcase.n]->outcome_public != tcase.ad[i]->outcome_public ||
+ tcase.ad[tcase.n]->time_start.abs_value_us
+ != tcase.ad[i]->time_start.abs_value_us ||
+ tcase.ad[tcase.n]->time_round.rel_value_us
+ != tcase.ad[i]->time_round.rel_value_us ||
+ !tcase.ad[tcase.n]->seller_mode || /* todo: split out */
+ tcase.ad[i]->seller_mode)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "error/mismatch in basic auction data\n");
+ tcase.ret = 1;
+ return;
+ }
+ }
+}
+
+
+/**
+ * Test a specific auction setup.
+ *
+ * @param[in] n number of bidders.
+ * @param[in] k number of different prices.
+ * @param[in] bids The bid array. Must contain exactly @a n elements each less
+ * than @a k.
+ * @param[in] m If 0 it's a first price auction, else an M+1st price auction
+ * specifying the M.
+ * @param[in] outcome_public 1 means public outcome, 0 means private outcome.
+ * @return 0 on success, 1 on failure
+ */
+static int
+test_auction (uint16_t n,
+ uint16_t k,
+ uint16_t *bids,
+ uint16_t m,
+ uint16_t outcome_public)
+{
+ tcase.n = n;
+ tcase.k = k;
+ tcase.bids = bids;
+ tcase.m = m;
+ tcase.outcome_public = outcome_public;
+ tcase.ret = 0;
+
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+ "######################################\n");
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+ "testing %s auction with m = %d and %s outcome\n",
+ tcase.m > 0 ? "M+1ST PRICE" : "FIRST PRICE",
+ tcase.m,
+ tcase.outcome_public ? "PUBLIC" : "PRIVATE");
+ /** \todo: output bids */
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+ "######################################\n");
+ tcase.ad = GNUNET_new_array (tcase.n + 1, struct BRANDT_Auction *);
+ tcase.id = GNUNET_new_array (tcase.n + 1, uint16_t);
+ for (uint16_t i = 0; i <= tcase.n; i++)
+ tcase.id[i] = i;
+ tcase.result_called = GNUNET_new_array (tcase.n + 1, uint16_t);
+
+ GNUNET_SCHEDULER_run (&run_auction, NULL);
+
+ for (uint16_t i = 0; i <= tcase.n; i++)
+ {
+ BRANDT_destroy (tcase.ad[i]);
+ if (!tcase.result_called[i])
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "result callback not called for bidder %d\n",
+ i);
+ tcase.ret = 1;
+ }
+ }
+
+ GNUNET_free (tcase.ad);
+ GNUNET_free (tcase.id);
+ GNUNET_free (tcase.result_called);
+
+ return tcase.ret;
+}
+
+
+int
+main (int argc, char *argv[])
+{
+ int ret = 0;
+ uint16_t n;
+ uint16_t k;
+ uint16_t m;
+ uint16_t public;
+ uint16_t *bids = NULL;
+ struct GNUNET_GETOPT_CommandLineOption options[] = {
+ GNUNET_GETOPT_OPTION_HELP ("benchmark a single libbrandt auction"),
+ {'k', "k", "NUMBER",
+ gettext_noop ("number of prices\n"),
+ 1, &GNUNET_GETOPT_set_uint, &k},
+ {'n', "n", "NUMBER",
+ gettext_noop ("number of bidders\n"),
+ 1, &GNUNET_GETOPT_set_uint, &n},
+ {'m', "m", "NUMBER",
+ gettext_noop ("number of items to sell\n"
+ "0 for first price auction\n"
+ ">0 for vickrey/M+1st price auction"),
+ 1, &GNUNET_GETOPT_set_uint, &m},
+ {'p', "public", NULL,
+ gettext_noop ("public auction outcome"),
+ 0, &GNUNET_GETOPT_set_one, &public},
+ GNUNET_GETOPT_OPTION_END
+ };
+
+ if (GNUNET_OK != GNUNET_log_setup ("test_brandt", "WARNING", NULL))
+ return 1;
+
+ ret = GNUNET_GETOPT_run ("bench", options, (unsigned int) argc, argv);
+ if ((GNUNET_OK > ret) ||
+ (GNUNET_OK != GNUNET_log_setup ("bench", "WARNING", NULL)))
+ return 1;
+
+ if (n == 0)
+ n = 4;
+ if (k == 0)
+ k = 3;
+
+ if (!(bids = calloc(sizeof(uint16_t), n)))
+ return 1;
+ for (uint16_t i = 0; i < n; i++)
+ bids[i] = (uint16_t)GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, k);
+
+ edc = GNUNET_CRYPTO_ecc_dlog_prepare (1024, 16);
+ BRANDT_init ();
+
+ ret = test_auction (n, k, bids, m, public);
+
+ GNUNET_CRYPTO_ecc_dlog_release (edc);
+ return ret;
+}