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.

1 files changed, 9 insertions, 3 deletions

diff --git a/src/test/test_workqueue.c b/src/test/test_workqueue.c
index 8d29d2062d..cc7073850c 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;
+      }
     }
   }