hs_pow: Rate limited dequeue

This adds a token bucket ratelimiter on the dequeue side
of hs_pow's priority queue. It adds config options and docs
for those options. (HiddenServicePoWQueueRate/Burst)

I'm testing this as a way to limit the overhead of circuit
creation when we're experiencing a flood of rendezvous requests.

Signed-off-by: Micah Elizabeth Scott <beth@torproject.org>

8 files changed, 72 insertions, 1 deletions

diff --git a/doc/man/tor.1.txt b/doc/man/tor.1.txt
index a62c7c7d82..2ac6a8471c 100644
--- a/doc/man/tor.1.txt
+++ b/doc/man/tor.1.txt
@@ -3099,6 +3099,19 @@ The following options are per onion service:
     entirely when the service is not overloaded.
     (Default: 0)
 
+[[HiddenServicePoWQueueRate]] **HiddenServicePoWQueueRate** __NUM__::
+
+    The sustained rate of rendezvous requests to dispatch per second from
+    the priority queue. Has no effect when proof-of-work is disabled.
+    If this is set to 0 there's no explicit limit and we will process
+    requests as quickly as possible.
+    (Default: 250)
+
+[[HiddenServicePoWQueueBurst]] **HiddenServicePoWQueueBurst** __NUM__::
+
+    The maximum burst size for rendezvous requests handled from the
+    priority queue at once. (Default: 2500)
+
 
 == DIRECTORY AUTHORITY SERVER OPTIONS
 
diff --git a/src/app/config/config.c b/src/app/config/config.c
index e035c6d6f3..0618622db9 100644
--- a/src/app/config/config.c
+++ b/src/app/config/config.c
@@ -509,6 +509,8 @@ static const config_var_t option_vars_[] = {
   VAR("HiddenServiceOnionBalanceInstance",
       LINELIST_S, RendConfigLines, NULL),
   VAR("HiddenServicePoWDefensesEnabled", LINELIST_S, RendConfigLines, NULL),
+  VAR("HiddenServicePoWQueueRate", LINELIST_S, RendConfigLines, NULL),
+  VAR("HiddenServicePoWQueueBurst", LINELIST_S, RendConfigLines, NULL),
   VAR("HiddenServiceStatistics", BOOL, HiddenServiceStatistics_option, "1"),
   V(ClientOnionAuthDir,          FILENAME, NULL),
   OBSOLETE("CloseHSClientCircuitsImmediatelyOnTimeout"),
diff --git a/src/feature/hs/hs_circuit.c b/src/feature/hs/hs_circuit.c
index 3684def697..55b992ee28 100644
--- a/src/feature/hs/hs_circuit.c
+++ b/src/feature/hs/hs_circuit.c
@@ -785,6 +785,20 @@ handle_rend_pqueue_cb(mainloop_event_t *ev, void *arg)
       return; /* done here! no cleanup needed. */
     }
 
+    if (pow_state->using_pqueue_bucket) {
+      token_bucket_ctr_refill(&pow_state->pqueue_bucket,
+                              (uint32_t) approx_time());
+
+      if (token_bucket_ctr_get(&pow_state->pqueue_bucket) > 0) {
+        token_bucket_ctr_dec(&pow_state->pqueue_bucket, 1);
+      } else {
+        /* Waiting for pqueue rate limit to refill, come back later */
+        const struct timeval delay_tv = { 0, 100000 };
+        mainloop_event_schedule(pow_state->pop_pqueue_ev, &delay_tv);
+        return;
+      }
+    }
+
     /* Pop next request by effort. */
     pending_rend_t *req =
       smartlist_pqueue_pop(pow_state->rend_request_pqueue,
@@ -816,6 +830,11 @@ handle_rend_pqueue_cb(mainloop_event_t *ev, void *arg)
     ++pow_state->rend_handled;
     ++in_flight;
 
+    if (pow_state->using_pqueue_bucket &&
+        token_bucket_ctr_get(&pow_state->pqueue_bucket) < 1) {
+      break;
+    }
+
     if (++count == MAX_REND_REQUEST_PER_MAINLOOP) {
       break;
     }
diff --git a/src/feature/hs/hs_config.c b/src/feature/hs/hs_config.c
index 4561bd3e48..0f5a8cf49a 100644
--- a/src/feature/hs/hs_config.c
+++ b/src/feature/hs/hs_config.c
@@ -320,6 +320,13 @@ config_validate_service(const hs_service_config_t *config)
              config->intro_dos_burst_per_sec, config->intro_dos_rate_per_sec);
     goto invalid;
   }
+  if (config->has_pow_defenses_enabled &&
+      (config->pow_queue_burst < config->pow_queue_rate)) {
+    log_warn(LD_CONFIG, "Hidden service PoW queue burst (%" PRIu32 ") can "
+                        "not be smaller than the rate value (%" PRIu32 ").",
+             config->pow_queue_burst, config->pow_queue_rate);
+    goto invalid;
+  }
 
   /* Valid. */
   return 0;
@@ -394,8 +401,17 @@ config_service_v3(const hs_opts_t *hs_opts,
 
   /* Are the PoW anti-DoS defenses enabled? */
   config->has_pow_defenses_enabled = hs_opts->HiddenServicePoWDefensesEnabled;
-  log_info(LD_REND, "Service PoW defenses are %s.",
+  config->pow_queue_rate = hs_opts->HiddenServicePoWQueueRate;
+  config->pow_queue_burst = hs_opts->HiddenServicePoWQueueBurst;
+
+  log_info(LD_REND, "Service PoW defenses are %s",
            config->has_pow_defenses_enabled ? "enabled" : "disabled");
+  if (config->has_pow_defenses_enabled) {
+    log_info(LD_REND, "Service PoW queue rate set to: %" PRIu32,
+             config->pow_queue_rate);
+    log_info(LD_REND, "Service PoW queue burst set to: %" PRIu32,
+             config->pow_queue_burst);
+  }
 
   /* We do not load the key material for the service at this stage. This is
    * done later once tor can confirm that it is in a running state. */
diff --git a/src/feature/hs/hs_options.inc b/src/feature/hs/hs_options.inc
index 2eb76db40f..4ec62d592b 100644
--- a/src/feature/hs/hs_options.inc
+++ b/src/feature/hs/hs_options.inc
@@ -32,5 +32,7 @@ CONF_VAR(HiddenServiceEnableIntroDoSRatePerSec, POSINT, 0, "25")
 CONF_VAR(HiddenServiceEnableIntroDoSBurstPerSec, POSINT, 0, "200")
 CONF_VAR(HiddenServiceOnionBalanceInstance, BOOL, 0, "0")
 CONF_VAR(HiddenServicePoWDefensesEnabled, BOOL, 0, "0")
+CONF_VAR(HiddenServicePoWQueueRate, POSINT, 0, "250")
+CONF_VAR(HiddenServicePoWQueueBurst, POSINT, 0, "2500")
 
 END_CONF_STRUCT(hs_opts_t)
diff --git a/src/feature/hs/hs_pow.h b/src/feature/hs/hs_pow.h
index 587cae6155..4eb9c5faa6 100644
--- a/src/feature/hs/hs_pow.h
+++ b/src/feature/hs/hs_pow.h
@@ -15,6 +15,7 @@ typedef unsigned __int128 uint128_t;
 #include "ext/equix/include/equix.h"
 
 #include "lib/evloop/compat_libevent.h"
+#include "lib/evloop/token_bucket.h"
 #include "lib/smartlist_core/smartlist_core.h"
 
 #define HS_POW_SUGGESTED_EFFORT_DEFAULT 20 // HRPR TODO 5000
@@ -70,6 +71,9 @@ typedef struct hs_pow_service_state_t {
    * the service's priority queue; higher effort is higher priority. */
   mainloop_event_t *pop_pqueue_ev;
 
+  /* Token bucket for rate limiting the priority queue */
+  token_bucket_ctr_t pqueue_bucket;
+
   /* The current seed being used in the PoW defenses. */
   uint8_t seed_current[HS_POW_SEED_LEN];
 
@@ -99,8 +103,12 @@ typedef struct hs_pow_service_state_t {
   time_t next_effort_update;
   /* Sum of effort of all valid requests received since the last update. */
   uint64_t total_effort;
+
   /* Did we have elements waiting in the queue during this period? */
   bool had_queue;
+  /* Are we using pqueue_bucket to rate limit the pqueue? */
+  bool using_pqueue_bucket;
+
 } hs_pow_service_state_t;
 
 /* Struct to store a solution to the PoW challenge. */
diff --git a/src/feature/hs/hs_service.c b/src/feature/hs/hs_service.c
index fda0162958..dd360d3659 100644
--- a/src/feature/hs/hs_service.c
+++ b/src/feature/hs/hs_service.c
@@ -279,6 +279,15 @@ initialize_pow_defenses(hs_service_t *service)
   pow_state->rend_request_pqueue = smartlist_new();
   pow_state->pop_pqueue_ev = NULL;
 
+  if (service->config.pow_queue_rate > 0 &&
+      service->config.pow_queue_burst >= service->config.pow_queue_rate) {
+    pow_state->using_pqueue_bucket = 1;
+    token_bucket_ctr_init(&pow_state->pqueue_bucket,
+                          service->config.pow_queue_rate,
+                          service->config.pow_queue_burst,
+                          (uint32_t) approx_time());
+  }
+
   pow_state->min_effort = service->config.pow_min_effort;
 
   /* We recalculate and update the suggested effort every HS_UPDATE_PERIOD
diff --git a/src/feature/hs/hs_service.h b/src/feature/hs/hs_service.h
index 465d9fba80..37984bd6c8 100644
--- a/src/feature/hs/hs_service.h
+++ b/src/feature/hs/hs_service.h
@@ -265,6 +265,8 @@ typedef struct hs_service_config_t {
   /** True iff PoW anti-DoS defenses are enabled. */
   unsigned int has_pow_defenses_enabled : 1;
   uint32_t pow_min_effort;
+  uint32_t pow_queue_rate;
+  uint32_t pow_queue_burst;
 
   /** If set, contains the Onion Balance master ed25519 public key (taken from
    * an .onion addresses) that this tor instance serves as backend. */