[tor-commits] [tor/master] Fix the selection of events to cancel in test_workqueue.c

[nickm@xxxxxxxxxxxxxx]

commit 6e3e96d2ff0c1b83bdd3f2059d1b4a2b96a53341
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
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;
+      }
     }
   }
 



_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits