aboutsummaryrefslogtreecommitdiff
path: root/bench.c
diff options
context:
space:
mode:
Diffstat (limited to 'bench.c')
-rw-r--r--bench.c495
1 files changed, 495 insertions, 0 deletions
diff --git a/bench.c b/bench.c
new file mode 100644
index 0000000..a38dc93
--- /dev/null
+++ b/bench.c
@@ -0,0 +1,495 @@
1/* This file is part of libbrandt.
2 * Copyright (C) 2016 GNUnet e.V.
3 *
4 * libbrandt is free software: you can redistribute it and/or modify it under
5 * the terms of the GNU General Public License as published by the Free Software
6 * Foundation, either version 3 of the License, or (at your option) any later
7 * version.
8 *
9 * libbrandt is distributed in the hope that it will be useful, but WITHOUT ANY
10 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
11 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License along with
14 * libbrandt. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17/**
18 * @file test_brandt.c
19 * @brief testing API functions.
20 * @author Markus Teich
21 */
22
23#include "platform.h"
24
25#include <gnunet/gnunet_util_lib.h>
26
27#include "brandt.h"
28#include "crypto.h"
29#include "util.h"
30
31#define MIN(A, B) ((A) < (B) ? (A) : (B))
32
33struct msg {
34 uint16_t sender;
35 uint16_t receiver;
36 void *buf;
37 size_t buf_len;
38};
39
40struct testcase {
41 uint16_t n;
42 uint16_t k;
43 uint16_t *bids;
44 uint16_t m;
45 uint16_t outcome_public;
46 uint16_t ret;
47 struct BRANDT_Auction **ad;
48 uint16_t *id;
49 uint16_t *result_called;
50};
51
52
53static struct testcase tcase;
54static struct GNUNET_CRYPTO_EccDlogContext *edc;
55
56
57static struct BRANDT_Result *
58expected_outcome (uint16_t i, uint16_t *rlen)
59{
60 struct BRANDT_Result *ret = NULL;
61 int32_t highest_bidder = -1;
62 int32_t highest_bid = -1;
63 int32_t mpf_highest_bidder;
64 int32_t mpf_highest_bid = -1;
65 int32_t prev_mpf_highest_bidder = -1;
66 uint16_t winners = MIN (tcase.m, tcase.n);
67 uint16_t cur_winner = 0;
68
69 *rlen = 0;
70
71 if (0 == tcase.n)
72 return NULL;
73
74 if (0 == tcase.m)
75 {
76 for (uint16_t h = 0; h < tcase.n; h++)
77 if (tcase.bids[h] > highest_bid)
78 highest_bid = tcase.bids[highest_bidder = h];
79
80 if (!tcase.outcome_public && !(i == highest_bidder || i == tcase.n))
81 return NULL;
82
83 ret = GNUNET_new (struct BRANDT_Result);
84 ret->bidder = highest_bidder;
85 ret->price = highest_bid;
86 ret->status = BRANDT_bidder_won;
87 *rlen = 1;
88 return ret;
89 }
90
91 /* fewer bidders than needed -> everyone wins with lowest price */
92 if (tcase.n <= tcase.m)
93 {
94 if (tcase.outcome_public || i == tcase.n)
95 {
96 ret = GNUNET_new_array ((*rlen = tcase.n), struct BRANDT_Result);
97 for (uint16_t h = 0; h < tcase.n; h++)
98 {
99 ret[h].bidder = h;
100 ret[h].price = 0;
101 ret[h].status = BRANDT_bidder_won;
102 }
103 }
104 else
105 {
106 ret = GNUNET_new (struct BRANDT_Result);
107 ret->bidder = i;
108 ret->price = 0;
109 ret->status = BRANDT_bidder_won;
110 *rlen = 1;
111 }
112 return ret;
113 }
114
115 /* find M+1st highest bidder to determine selling price */
116 for (uint16_t h = 0; h < tcase.n; h++)
117 if (tcase.bids[h] > mpf_highest_bid)
118 mpf_highest_bid = tcase.bids[prev_mpf_highest_bidder = h];
119 for (uint16_t m = 0; m < MIN (tcase.m, tcase.n - 1); m++)
120 {
121 mpf_highest_bidder = -1;
122 mpf_highest_bid = -1;
123 for (uint16_t h = 0; h < tcase.n; h++)
124 {
125 if (tcase.bids[h] > mpf_highest_bid &&
126 (tcase.bids[h] < tcase.bids[prev_mpf_highest_bidder] ||
127 (tcase.bids[h] == tcase.bids[prev_mpf_highest_bidder] &&
128 h > prev_mpf_highest_bidder)))
129 {
130 mpf_highest_bid = tcase.bids[mpf_highest_bidder = h];
131 }
132 }
133 prev_mpf_highest_bidder = mpf_highest_bidder;
134 }
135
136 /* for simplicity always locate the big block if we need to report at
137 * least one winner. with private outcome for losing bidders or winners
138 * only none or one element will be used respectively. */
139 if (tcase.outcome_public || i == tcase.n ||
140 tcase.bids[i] > mpf_highest_bid ||
141 (tcase.bids[i] == mpf_highest_bid && i < mpf_highest_bidder))
142 ret = GNUNET_new_array (winners, struct BRANDT_Result);
143
144 /* report winners */
145 for (uint16_t h = 0; h < tcase.n; h++)
146 {
147 if (((tcase.bids[h] == mpf_highest_bid && h < mpf_highest_bidder) ||
148 tcase.bids[h] > mpf_highest_bid) && /* h is a winner */
149 (tcase.outcome_public || i == h || i == tcase.n)) /* needs report */
150 {
151 if (cur_winner >= winners)
152 {
153 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "got too many winners\n");
154 _exit (1);
155 }
156 ret[cur_winner].bidder = h;
157 ret[cur_winner].price = mpf_highest_bid;
158 ret[cur_winner].status = BRANDT_bidder_won;
159 cur_winner++;
160 }
161 }
162 *rlen = cur_winner;
163 return ret;
164}
165
166
167static void
168bidder_start (void *arg)
169{
170 uint16_t i = *(uint16_t *)arg;
171
172 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "starting bidder %d\n", i);
173 BRANDT_bidder_start (tcase.ad[i], i, tcase.n);
174}
175
176
177static void
178transfer_message (void *arg)
179{
180 struct msg *m = (struct msg *)arg;
181 struct msg_head *h = (struct msg_head *)m->buf;
182
183 GNUNET_log (GNUNET_ERROR_TYPE_INFO, "xfer msg %d %p from %d to %d\n",
184 ntohl (h->msg_type), arg, m->sender, m->receiver);
185 BRANDT_got_message (tcase.ad[m->receiver], m->sender, m->buf, m->buf_len);
186 GNUNET_free (m->buf);
187 GNUNET_free (m);
188}
189
190
191static uint16_t
192cb_start (void *auction_closure)
193{
194 uint16_t *s = (uint16_t *)auction_closure;
195
196 if (tcase.n != *s)
197 {
198 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
199 "start callback called from bidder\n");
200 _exit (1);
201 }
202
203 for (uint16_t i = 0; i < tcase.n; i++)
204 GNUNET_SCHEDULER_add_now (&bidder_start, &tcase.id[i]);
205
206 return tcase.n;
207}
208
209
210static int
211cb_broadcast (void *auction_closure,
212 const void *msg,
213 size_t msg_len)
214{
215 uint16_t *s = (uint16_t *)auction_closure;
216 struct msg *m;
217
218 for (uint16_t i = 0; i <= tcase.n; i++)
219 {
220 if (i == *s)
221 continue;
222 m = GNUNET_new (struct msg);
223 m->sender = *s;
224 m->receiver = i;
225 m->buf = GNUNET_new_array (msg_len, unsigned char);
226 memcpy (m->buf, msg, msg_len);
227 m->buf_len = msg_len;
228 GNUNET_SCHEDULER_add_now (&transfer_message, m);
229 }
230 return 0;
231}
232
233
234static int
235cb_unicast (void *auction_closure,
236 const void *msg,
237 size_t msg_len)
238{
239 uint16_t *s = (uint16_t *)auction_closure;
240 struct msg *m;
241
242 m = GNUNET_new (struct msg);
243 m->sender = *s;
244 m->receiver = tcase.n; /* == seller */
245 m->buf = GNUNET_new_array (msg_len, unsigned char);
246 memcpy (m->buf, msg, msg_len);
247 m->buf_len = msg_len;
248 GNUNET_SCHEDULER_add_now (&transfer_message, m);
249
250 return 0;
251}
252
253
254static void
255cb_result (void *auction_closure,
256 struct BRANDT_Result results[],
257 uint16_t results_len)
258{
259 uint16_t *s = (uint16_t *)auction_closure;
260 uint16_t mustlen = -1;
261 struct BRANDT_Result *must = expected_outcome (*s, &mustlen);
262
263 if (mustlen != results_len)
264 {
265 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
266 "expected result len is: %d\n",
267 mustlen);
268 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
269 "computed result len is: %d (by agent %d)\n",
270 results_len,
271 *s);
272 tcase.ret = 1;
273 goto quit;
274 }
275
276 if (0 == results_len && NULL != must)
277 {
278 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
279 "expected result is: %p\n",
280 (void *)must);
281 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
282 "computed result is: (nil) (by agent %d)\n",
283 *s);
284
285 tcase.ret = 1;
286 }
287
288 for (uint16_t i = 0; i < results_len; i++)
289 {
290 GNUNET_log (
291 GNUNET_ERROR_TYPE_INFO,
292 "expected result is: bidder %d got status %d with price %d\n",
293 must[i].bidder,
294 must[i].status,
295 must[i].price);
296 GNUNET_log (
297 GNUNET_ERROR_TYPE_INFO,
298 "computed result is: bidder %d got status %d with price %d (by agent %d)\n",
299 results[i].bidder,
300 results[i].status,
301 results[i].price,
302 *s);
303
304 if (NULL == must ||
305 must[i].bidder != results[i].bidder ||
306 must[i].status != results[i].status ||
307 must[i].price != results[i].price)
308 tcase.ret = 1;
309 }
310
311quit:
312 tcase.result_called[*s] = 1;
313 if (must)
314 GNUNET_free (must);
315}
316
317
318static void
319run_auction (void *arg)
320{
321 void *desc;
322 size_t desc_len;
323
324 tcase.ad[tcase.n] = BRANDT_new (&cb_result,
325 &cb_broadcast,
326 &cb_start,
327 &tcase.id[tcase.n],
328 &desc,
329 &desc_len,
330 GNUNET_TIME_absolute_get (),
331 GNUNET_TIME_UNIT_MINUTES,
332 tcase.k, /* number of prizes */
333 tcase.m, /* m */
334 tcase.outcome_public, /* outcome public */
335 tcase.outcome_public ? edc : NULL);
336 if (!tcase.ad[tcase.n])
337 {
338 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "BRANDT_new() failed.\n");
339 _exit (1);
340 }
341
342 for (uint16_t i = 0; i < tcase.n; i++)
343 {
344 tcase.ad[i] = BRANDT_join (&cb_result,
345 &cb_broadcast,
346 &cb_unicast,
347 &tcase.id[i],
348 desc,
349 desc_len,
350 tcase.bids[i], /* bid */
351 tcase.outcome_public ? edc : NULL);
352 if (!tcase.ad[i])
353 {
354 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "BRANDT_join() failed.\n");
355 tcase.ret = 1;
356 return;
357 }
358
359 if (tcase.ad[tcase.n]->k != tcase.ad[i]->k ||
360 tcase.ad[tcase.n]->m != tcase.ad[i]->m ||
361 tcase.ad[tcase.n]->outcome_public != tcase.ad[i]->outcome_public ||
362 tcase.ad[tcase.n]->time_start.abs_value_us
363 != tcase.ad[i]->time_start.abs_value_us ||
364 tcase.ad[tcase.n]->time_round.rel_value_us
365 != tcase.ad[i]->time_round.rel_value_us ||
366 !tcase.ad[tcase.n]->seller_mode || /* todo: split out */
367 tcase.ad[i]->seller_mode)
368 {
369 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
370 "error/mismatch in basic auction data\n");
371 tcase.ret = 1;
372 return;
373 }
374 }
375}
376
377
378/**
379 * Test a specific auction setup.
380 *
381 * @param[in] n number of bidders.
382 * @param[in] k number of different prices.
383 * @param[in] bids The bid array. Must contain exactly @a n elements each less
384 * than @a k.
385 * @param[in] m If 0 it's a first price auction, else an M+1st price auction
386 * specifying the M.
387 * @param[in] outcome_public 1 means public outcome, 0 means private outcome.
388 * @return 0 on success, 1 on failure
389 */
390static int
391test_auction (uint16_t n,
392 uint16_t k,
393 uint16_t *bids,
394 uint16_t m,
395 uint16_t outcome_public)
396{
397 tcase.n = n;
398 tcase.k = k;
399 tcase.bids = bids;
400 tcase.m = m;
401 tcase.outcome_public = outcome_public;
402 tcase.ret = 0;
403
404 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
405 "######################################\n");
406 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
407 "testing %s auction with m = %d and %s outcome\n",
408 tcase.m > 0 ? "M+1ST PRICE" : "FIRST PRICE",
409 tcase.m,
410 tcase.outcome_public ? "PUBLIC" : "PRIVATE");
411 /** \todo: output bids */
412 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
413 "######################################\n");
414 tcase.ad = GNUNET_new_array (tcase.n + 1, struct BRANDT_Auction *);
415 tcase.id = GNUNET_new_array (tcase.n + 1, uint16_t);
416 for (uint16_t i = 0; i <= tcase.n; i++)
417 tcase.id[i] = i;
418 tcase.result_called = GNUNET_new_array (tcase.n + 1, uint16_t);
419
420 GNUNET_SCHEDULER_run (&run_auction, NULL);
421
422 for (uint16_t i = 0; i <= tcase.n; i++)
423 {
424 BRANDT_destroy (tcase.ad[i]);
425 if (!tcase.result_called[i])
426 {
427 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
428 "result callback not called for bidder %d\n",
429 i);
430 tcase.ret = 1;
431 }
432 }
433
434 GNUNET_free (tcase.ad);
435 GNUNET_free (tcase.id);
436 GNUNET_free (tcase.result_called);
437
438 return tcase.ret;
439}
440
441
442int
443main (int argc, char *argv[])
444{
445 int ret = 0;
446 uint16_t n;
447 uint16_t k;
448 uint16_t m;
449 uint16_t public;
450 uint16_t *bids = NULL;
451 struct GNUNET_GETOPT_CommandLineOption options[] = {
452 GNUNET_GETOPT_OPTION_HELP ("benchmark a single libbrandt auction"),
453 {'k', "k", "NUMBER",
454 gettext_noop ("number of prices\n"),
455 1, &GNUNET_GETOPT_set_uint, &k},
456 {'n', "n", "NUMBER",
457 gettext_noop ("number of bidders\n"),
458 1, &GNUNET_GETOPT_set_uint, &n},
459 {'m', "m", "NUMBER",
460 gettext_noop ("number of items to sell\n"
461 "0 for first price auction\n"
462 ">0 for vickrey/M+1st price auction"),
463 1, &GNUNET_GETOPT_set_uint, &m},
464 {'p', "public", NULL,
465 gettext_noop ("public auction outcome"),
466 0, &GNUNET_GETOPT_set_one, &public},
467 GNUNET_GETOPT_OPTION_END
468 };
469
470 if (GNUNET_OK != GNUNET_log_setup ("test_brandt", "WARNING", NULL))
471 return 1;
472
473 ret = GNUNET_GETOPT_run ("bench", options, (unsigned int) argc, argv);
474 if ((GNUNET_OK > ret) ||
475 (GNUNET_OK != GNUNET_log_setup ("bench", "WARNING", NULL)))
476 return 1;
477
478 if (n == 0)
479 n = 4;
480 if (k == 0)
481 k = 3;
482
483 if (!(bids = calloc(sizeof(uint16_t), n)))
484 return 1;
485 for (uint16_t i = 0; i < n; i++)
486 bids[i] = (uint16_t)GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, k);
487
488 edc = GNUNET_CRYPTO_ecc_dlog_prepare (1024, 16);
489 BRANDT_init ();
490
491 ret = test_auction (n, k, bids, m, public);
492
493 GNUNET_CRYPTO_ecc_dlog_release (edc);
494 return ret;
495}
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-23 22:13:47 +0000