tor

commit a575e35c17d49bd830a9a1814ad9a3b122df9f08
parent 13f62582456cc9e7f1e8fd5993dd0e33b7da196b
Author: Roger Dingledine <arma@torproject.org>
Date:   Fri,  1 Jul 2022 16:29:46 -0400

sort pqueue ties by time-added

our pqueue implementation does bizarre unspecified things with
ordering of elements that are equal. it certainly doesn't do any
sort of "first in first out" property that i was expecting.

now make it explicit by saying that "equal-effort, added-earlier" is
higher priority.

Diffstat:
M
src/feature/hs/hs_circuit.c
 | 
7
+++++++

1 file changed, 7 insertions(+), 0 deletions(-)
diff --git a/src/feature/hs/hs_circuit.c b/src/feature/hs/hs_circuit.c
@@ -624,6 +624,11 @@ compare_rend_request_by_effort_(const void *_a, const void *_b)
   if (a->rdv_data.pow_effort > b->rdv_data.pow_effort) {
     return -1;
   } else if (a->rdv_data.pow_effort == b->rdv_data.pow_effort) {
+    /* tie-breaker! use the time it was added to the queue. older better. */
+    if (a->enqueued_ts < b->enqueued_ts)
+      return -1;
+    if (a->enqueued_ts > b->enqueued_ts)
+      return 1;
     return 0;
   } else {
     return 1;
@@ -780,8 +785,10 @@ handle_rend_pqueue_cb(mainloop_event_t *ev, void *arg)
                            offsetof(pending_rend_t, idx));
 
     log_notice(LD_REND, "Dequeued pending rendezvous request with effort: %u. "
+                      "Waited %d. "
                       "Remaining requests: %u",
              req->rdv_data.pow_effort,
+             (int)(now - req->enqueued_ts),
              smartlist_len(pow_state->rend_request_pqueue));
 
     if (queued_rend_request_is_too_old(req, now)) {