commit 6e3e96d2ff0c1b83bdd3f2059d1b4a2b96a53341 Author: Nick Mathewson nickm@torproject.org Date: Sun May 6 21:03:26 2018 -0400

Fix the selection of events to cancel in test_workqueue.c

Our previous algorithm had a nonzero probability of picking no events to cancel, which is of course incorrect. The new code uses Vitter's good old reservoir sampling "algorithm R" from 1985.

Fixes bug 26008; bugfix on 0.2.6.3-alpha. --- changes/ticket26008 | 7 +++++++ src/test/test_workqueue.c | 12 +++++++++--- 2 files changed, 16 insertions(+), 3 deletions(-)

diff --git a/changes/ticket26008 b/changes/ticket26008 new file mode 100644 index 000000000..7550c959e --- /dev/null +++ b/changes/ticket26008 @@ -0,0 +1,7 @@ + o Minor bugfixes (test): + - When testing workqueue event-cancellation, make sure that we actually + cancel an event, and that cancel each event with equal probability. + (It was previously possible, though extremely unlikely, for our + event-canceling test not to cancel any events.) Fixes bug 26008; + bugfix on 0.2.6.3-alpha. + diff --git a/src/test/test_workqueue.c b/src/test/test_workqueue.c index 8d29d2062..cc7073850 100644 --- a/src/test/test_workqueue.c +++ b/src/test/test_workqueue.c @@ -224,7 +224,8 @@ add_n_work_items(threadpool_t *tp, int n) workqueue_entry_t **to_cancel; workqueue_entry_t *ent;

- to_cancel = tor_malloc(sizeof(workqueue_entry_t*) * opt_n_cancel); + // We'll choose randomly which entries to cancel. + to_cancel = tor_calloc(opt_n_cancel, sizeof(workqueue_entry_t*));

while (n_queued++ < n) { ent = add_work(tp); @@ -233,9 +234,14 @@ add_n_work_items(threadpool_t *tp, int n) tor_libevent_exit_loop_after_delay(tor_libevent_get_base(), NULL); return -1; } - if (n_try_cancel < opt_n_cancel && - tor_weak_random_range(&weak_rng, n) < opt_n_cancel) { + + if (n_try_cancel < opt_n_cancel) { to_cancel[n_try_cancel++] = ent; + } else { + int p = tor_weak_random_range(&weak_rng, n_queued); + if (p < n_try_cancel) { + to_cancel[p] = ent; + } } }