diff options
-rw-r--r-- | Makefile.am | 6 | ||||
-rw-r--r-- | bench.c | 495 |
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 = \ | |||
18 | libbrandt_la_LDFLAGS = \ | 18 | libbrandt_la_LDFLAGS = \ |
19 | -version-info 0:0:0 | 19 | -version-info 0:0:0 |
20 | 20 | ||
21 | noinst_PROGRAMS = \ | ||
22 | bench | ||
23 | |||
24 | bench_SOURCES = bench.c | ||
25 | bench_LDADD = libbrandt.la -lgcrypt -lgpg-error -lgnunetutil | ||
26 | |||
21 | check_PROGRAMS = \ | 27 | check_PROGRAMS = \ |
22 | test_crypto \ | 28 | test_crypto \ |
23 | test_brandt | 29 | test_brandt |
@@ -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 | |||
33 | struct msg { | ||
34 | uint16_t sender; | ||
35 | uint16_t receiver; | ||
36 | void *buf; | ||
37 | size_t buf_len; | ||
38 | }; | ||
39 | |||
40 | struct 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 | |||
53 | static struct testcase tcase; | ||
54 | static struct GNUNET_CRYPTO_EccDlogContext *edc; | ||
55 | |||
56 | |||
57 | static struct BRANDT_Result * | ||
58 | expected_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 | |||
167 | static void | ||
168 | bidder_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 | |||
177 | static void | ||
178 | transfer_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 | |||
191 | static uint16_t | ||
192 | cb_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 | |||
210 | static int | ||
211 | cb_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 | |||
234 | static int | ||
235 | cb_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 | |||
254 | static void | ||
255 | cb_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 | |||
311 | quit: | ||
312 | tcase.result_called[*s] = 1; | ||
313 | if (must) | ||
314 | GNUNET_free (must); | ||
315 | } | ||
316 | |||
317 | |||
318 | static void | ||
319 | run_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 | */ | ||
390 | static int | ||
391 | test_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 | |||
442 | int | ||
443 | main (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 | } | ||