tor

hs_circuit.c (63569B)

---

/* Copyright (c) 2017-2021, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
* \file hs_circuit.c
**/

#define HS_CIRCUIT_PRIVATE

#include "core/or/or.h"
#include "app/config/config.h"
#include "core/crypto/hs_ntor.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/policies.h"
#include "core/or/relay.h"
#include "core/or/crypt_path.h"
#include "core/or/extendinfo.h"
#include "core/or/congestion_control_common.h"
#include "core/crypto/onion_crypto.h"
#include "feature/client/circpathbias.h"
#include "feature/hs/hs_cell.h"
#include "feature/hs/hs_circuit.h"
#include "feature/hs/hs_common.h"
#include "feature/hs/hs_ob.h"
#include "feature/hs/hs_circuitmap.h"
#include "feature/hs/hs_client.h"
#include "feature/hs/hs_ident.h"
#include "feature/hs/hs_metrics.h"
#include "feature/hs/hs_service.h"
#include "feature/nodelist/describe.h"
#include "feature/nodelist/nodelist.h"
#include "feature/stats/rephist.h"
#include "lib/crypt_ops/crypto_dh.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/crypt_ops/crypto_util.h"
#include "lib/time/compat_time.h"

/* Trunnel. */
#include "trunnel/ed25519_cert.h"
#include "trunnel/hs/cell_establish_intro.h"

#include "core/or/congestion_control_st.h"
#include "core/or/cpath_build_state_st.h"
#include "core/or/crypt_path_st.h"
#include "core/or/extend_info_st.h"
#include "feature/nodelist/node_st.h"
#include "core/or/origin_circuit_st.h"

/** Helper: Free a pending rend object. */
static inline void
free_pending_rend(pending_rend_t *req)
{
 if (!req) {
   return;
 }
 link_specifier_smartlist_free(req->rdv_data.link_specifiers);
 memwipe(req, 0, sizeof(pending_rend_t));
 tor_free(req);
}

/** A circuit is about to become an e2e rendezvous circuit. Check
* <b>circ_purpose</b> and ensure that it's properly set. Return true iff
* circuit purpose is properly set, otherwise return false. */
static int
circuit_purpose_is_correct_for_rend(unsigned int circ_purpose,
                                   int is_service_side)
{
 if (is_service_side) {
   if (circ_purpose != CIRCUIT_PURPOSE_S_CONNECT_REND) {
     log_warn(LD_BUG,
           "HS e2e circuit setup with wrong purpose (%d)", circ_purpose);
     return 0;
   }
 }

 if (!is_service_side) {
   if (circ_purpose != CIRCUIT_PURPOSE_C_REND_READY &&
       circ_purpose != CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED) {
     log_warn(LD_BUG,
           "Client e2e circuit setup with wrong purpose (%d)", circ_purpose);
     return 0;
   }
 }

 return 1;
}

/** Create and return a crypt path for the final hop of a v3 prop224 rendezvous
* circuit. Initialize the crypt path crypto using the output material from the
* ntor key exchange at <b>ntor_key_seed</b>.
*
* If <b>is_service_side</b> is set, we are the hidden service and the final
* hop of the rendezvous circuit is the client on the other side. */
static crypt_path_t *
create_rend_cpath(const uint8_t *ntor_key_seed, size_t seed_len,
                 int is_service_side)
{
 uint8_t keys[HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN];
 crypt_path_t *cpath = NULL;

 /* Do the key expansion */
 if (hs_ntor_circuit_key_expansion(ntor_key_seed, seed_len,
                                   keys, sizeof(keys)) < 0) {
   goto err;
 }

 /* Setup the cpath */
 cpath = tor_malloc_zero(sizeof(crypt_path_t));
 cpath->magic = CRYPT_PATH_MAGIC;

 // TODO CGO: Pick relay cell format based on capabilities.
 cpath->relay_cell_format = RELAY_CELL_FORMAT_V0;
 relay_crypto_alg_t alg = is_service_side ? RELAY_CRYPTO_ALG_TOR1_HSS :
   RELAY_CRYPTO_ALG_TOR1_HSC;

 if (cpath_init_circuit_crypto(alg, cpath, (char*)keys, sizeof(keys)) < 0) {
   tor_free(cpath);
   goto err;
 }

err:
 memwipe(keys, 0, sizeof(keys));
 return cpath;
}

/** Append the final <b>hop</b> to the cpath of the rend <b>circ</b>, and mark
* <b>circ</b> ready for use to transfer HS relay cells. */
static void
finalize_rend_circuit(origin_circuit_t *circ, crypt_path_t *hop,
                     int is_service_side)
{
 tor_assert(circ);
 tor_assert(hop);

 /* Notify the circuit state machine that we are splicing this circuit */
 int new_circ_purpose = is_service_side ?
   CIRCUIT_PURPOSE_S_REND_JOINED : CIRCUIT_PURPOSE_C_REND_JOINED;
 circuit_change_purpose(TO_CIRCUIT(circ), new_circ_purpose);

 /* All is well. Extend the circuit. */
 hop->state = CPATH_STATE_OPEN;
 /* Set the windows to default. */
 hop->package_window = circuit_initial_package_window();
 hop->deliver_window = CIRCWINDOW_START;

 /* If congestion control, transfer ccontrol onto the cpath. */
 if (TO_CIRCUIT(circ)->ccontrol) {
   hop->ccontrol = TO_CIRCUIT(circ)->ccontrol;
   TO_CIRCUIT(circ)->ccontrol = NULL;
 }

 /* Append the hop to the cpath of this circuit */
 cpath_extend_linked_list(&circ->cpath, hop);

 /* Finally, mark circuit as ready to be used for client streams */
 if (!is_service_side) {
   circuit_try_attaching_streams(circ);
 }
}

/** For a given circuit and a service introduction point object, register the
* intro circuit to the circuitmap. */
static void
register_intro_circ(const hs_service_intro_point_t *ip,
                   origin_circuit_t *circ)
{
 tor_assert(ip);
 tor_assert(circ);

 hs_circuitmap_register_intro_circ_v3_service_side(circ,
                                                   &ip->auth_key_kp.pubkey);
}

/** Return the number of opened introduction circuit for the given circuit that
* is matching its identity key. */
static unsigned int
count_opened_desc_intro_point_circuits(const hs_service_t *service,
                                      const hs_service_descriptor_t *desc)
{
 unsigned int count = 0;

 tor_assert(service);
 tor_assert(desc);

 DIGEST256MAP_FOREACH(desc->intro_points.map, key,
                      const hs_service_intro_point_t *, ip) {
   const circuit_t *circ;
   const origin_circuit_t *ocirc = hs_circ_service_get_intro_circ(ip);
   if (ocirc == NULL) {
     continue;
   }
   circ = TO_CIRCUIT(ocirc);
   tor_assert(circ->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO ||
              circ->purpose == CIRCUIT_PURPOSE_S_INTRO);
   /* Having a circuit not for the requested service is really bad. */
   tor_assert(ed25519_pubkey_eq(&service->keys.identity_pk,
                                &ocirc->hs_ident->identity_pk));
   /* Only count opened circuit and skip circuit that will be closed. */
   if (!circ->marked_for_close && circ->state == CIRCUIT_STATE_OPEN) {
     count++;
   }
 } DIGEST256MAP_FOREACH_END;
 return count;
}

/** From a given service, rendezvous cookie and handshake info, create a
* rendezvous point circuit identifier. This can't fail. */
STATIC hs_ident_circuit_t *
create_rp_circuit_identifier(const hs_service_t *service,
                            const uint8_t *rendezvous_cookie,
                            const curve25519_public_key_t *server_pk,
                            const hs_ntor_rend_cell_keys_t *keys)
{
 hs_ident_circuit_t *ident;
 uint8_t handshake_info[CURVE25519_PUBKEY_LEN + DIGEST256_LEN];

 tor_assert(service);
 tor_assert(rendezvous_cookie);
 tor_assert(server_pk);
 tor_assert(keys);

 ident = hs_ident_circuit_new(&service->keys.identity_pk);
 /* Copy the RENDEZVOUS_COOKIE which is the unique identifier. */
 memcpy(ident->rendezvous_cookie, rendezvous_cookie,
        sizeof(ident->rendezvous_cookie));
 /* Build the HANDSHAKE_INFO which looks like this:
  *    SERVER_PK        [32 bytes]
  *    AUTH_INPUT_MAC   [32 bytes]
  */
 memcpy(handshake_info, server_pk->public_key, CURVE25519_PUBKEY_LEN);
 memcpy(handshake_info + CURVE25519_PUBKEY_LEN, keys->rend_cell_auth_mac,
        DIGEST256_LEN);
 tor_assert(sizeof(ident->rendezvous_handshake_info) ==
            sizeof(handshake_info));
 memcpy(ident->rendezvous_handshake_info, handshake_info,
        sizeof(ident->rendezvous_handshake_info));
 /* Finally copy the NTOR_KEY_SEED for e2e encryption on the circuit. */
 tor_assert(sizeof(ident->rendezvous_ntor_key_seed) ==
            sizeof(keys->ntor_key_seed));
 memcpy(ident->rendezvous_ntor_key_seed, keys->ntor_key_seed,
        sizeof(ident->rendezvous_ntor_key_seed));
 return ident;
}

/** From a given service and service intro point, create an introduction point
* circuit identifier. This can't fail. */
static hs_ident_circuit_t *
create_intro_circuit_identifier(const hs_service_t *service,
                               const hs_service_intro_point_t *ip)
{
 hs_ident_circuit_t *ident;

 tor_assert(service);
 tor_assert(ip);

 ident = hs_ident_circuit_new(&service->keys.identity_pk);
 ed25519_pubkey_copy(&ident->intro_auth_pk, &ip->auth_key_kp.pubkey);
 tor_assert_nonfatal(!ed25519_public_key_is_zero(&ident->intro_auth_pk));

 return ident;
}

/** For a given introduction point and an introduction circuit, send the
* ESTABLISH_INTRO cell. The service object is used for logging. This can fail
* and if so, the circuit is closed and the intro point object is flagged
* that the circuit is not established anymore which is important for the
* retry mechanism. */
static void
send_establish_intro(const hs_service_t *service,
                    hs_service_intro_point_t *ip, origin_circuit_t *circ)
{
 ssize_t cell_len;
 uint8_t payload[RELAY_PAYLOAD_SIZE_MAX];

 tor_assert(service);
 tor_assert(ip);
 tor_assert(circ);

 /* Encode establish intro cell. */
 cell_len = hs_cell_build_establish_intro(circ->cpath->prev->rend_circ_nonce,
                                          &service->config, ip, payload);
 if (cell_len < 0) {
   log_warn(LD_REND, "Unable to encode ESTABLISH_INTRO cell for service %s "
                     "on circuit %u. Closing circuit.",
            safe_str_client(service->onion_address),
            TO_CIRCUIT(circ)->n_circ_id);
   goto err;
 }

 /* Send the cell on the circuit. */
 if (relay_send_command_from_edge(CONTROL_CELL_ID, TO_CIRCUIT(circ),
                                  RELAY_COMMAND_ESTABLISH_INTRO,
                                  (char *) payload, cell_len,
                                  circ->cpath->prev) < 0) {
   log_info(LD_REND, "Unable to send ESTABLISH_INTRO cell for service %s "
                     "on circuit %u.",
            safe_str_client(service->onion_address),
            TO_CIRCUIT(circ)->n_circ_id);
   /* On error, the circuit has been closed. */
   goto done;
 }

 /* Record the attempt to use this circuit. */
 pathbias_count_use_attempt(circ);
 goto done;

err:
 circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
done:
 memwipe(payload, 0, sizeof(payload));
}

/** Return a string constant describing the anonymity of service. */
static const char *
get_service_anonymity_string(const hs_service_t *service)
{
 if (service->config.is_single_onion) {
   return "single onion";
 } else {
   return "hidden";
 }
}

/** For a given service, the ntor onion key and a rendezvous cookie, launch a
* circuit to the rendezvous point specified by the link specifiers. On
* success, a circuit identifier is attached to the circuit with the needed
* data. This function will try to open a circuit for a maximum value of
* MAX_REND_FAILURES then it will give up. */
MOCK_IMPL(STATIC void,
launch_rendezvous_point_circuit,(const hs_service_t *service,
                                const ed25519_public_key_t *ip_auth_pubkey,
                                const curve25519_keypair_t *ip_enc_key_kp,
                                const hs_cell_intro_rdv_data_t *rdv_data,
                                time_t now))
{
 int circ_needs_uptime;
 extend_info_t *info = NULL;
 origin_circuit_t *circ;

 tor_assert(service);
 tor_assert(ip_auth_pubkey);
 tor_assert(ip_enc_key_kp);
 tor_assert(rdv_data);

 circ_needs_uptime = hs_service_requires_uptime_circ(service->config.ports);

 /* Get the extend info data structure for the chosen rendezvous point
  * specified by the given link specifiers. */
 info = hs_get_extend_info_from_lspecs(rdv_data->link_specifiers,
                                       &rdv_data->onion_pk,
                                       service->config.is_single_onion);
 if (info == NULL) {
   /* We are done here, we can't extend to the rendezvous point. */
   log_fn(LOG_PROTOCOL_WARN, LD_REND,
          "Not enough info to open a circuit to a rendezvous point for "
          "%s service %s.",
          get_service_anonymity_string(service),
          safe_str_client(service->onion_address));
   goto end;
 }

 for (int i = 0; i < MAX_REND_FAILURES; i++) {
   int circ_flags = CIRCLAUNCH_NEED_CAPACITY | CIRCLAUNCH_IS_INTERNAL;
   if (circ_needs_uptime) {
     circ_flags |= CIRCLAUNCH_NEED_UPTIME;
   }
   /* Firewall and policies are checked when getting the extend info.
    *
    * We only use a one-hop path on the first attempt. If the first attempt
    * fails, we use a 3-hop path for reachability / reliability.
    * See the comment in retry_service_rendezvous_point() for details. */
   if (service->config.is_single_onion && i == 0) {
     circ_flags |= CIRCLAUNCH_ONEHOP_TUNNEL;
   }

   circ = circuit_launch_by_extend_info(CIRCUIT_PURPOSE_S_CONNECT_REND, info,
                                        circ_flags);
   if (circ != NULL) {
     /* Stop retrying, we have a circuit! */
     break;
   }
 }
 if (circ == NULL) {
   log_warn(LD_REND, "Giving up on launching a rendezvous circuit to %s "
                     "for %s service %s",
            safe_str_client(extend_info_describe(info)),
            get_service_anonymity_string(service),
            safe_str_client(service->onion_address));
   goto end;
 }
 /* Update metrics with this new rendezvous circuit launched. */
 hs_metrics_new_rdv(&service->keys.identity_pk);

 log_info(LD_REND, "Rendezvous circuit launched to %s with cookie %s "
                   "for %s service %s",
          safe_str_client(extend_info_describe(info)),
          safe_str_client(hex_str((const char *)
                                  rdv_data->rendezvous_cookie,
                                  REND_COOKIE_LEN)),
          get_service_anonymity_string(service),
          safe_str_client(service->onion_address));
 tor_assert(circ->build_state);
 /* Rendezvous circuit have a specific timeout for the time spent on trying
  * to connect to the rendezvous point. */
 circ->build_state->expiry_time = now + MAX_REND_TIMEOUT;

 /* Create circuit identifier and key material. */
 {
   hs_ntor_rend_cell_keys_t keys;
   curve25519_keypair_t ephemeral_kp;
   /* No need for extra strong, this is only for this circuit life time. This
    * key will be used for the RENDEZVOUS1 cell that will be sent on the
    * circuit once opened. */
   curve25519_keypair_generate(&ephemeral_kp, 0);
   if (hs_ntor_service_get_rendezvous1_keys(ip_auth_pubkey,
                                            ip_enc_key_kp,
                                            &ephemeral_kp,
                                            &rdv_data->client_pk,
                                            &keys) < 0) {
     /* This should not really happened but just in case, don't make tor
      * freak out, close the circuit and move on. */
     log_info(LD_REND, "Unable to get RENDEZVOUS1 key material for "
                       "service %s",
              safe_str_client(service->onion_address));
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
     goto end;
   }
   circ->hs_ident = create_rp_circuit_identifier(service,
                                      rdv_data->rendezvous_cookie,
                                      &ephemeral_kp.pubkey, &keys);
   memwipe(&ephemeral_kp, 0, sizeof(ephemeral_kp));
   memwipe(&keys, 0, sizeof(keys));
   tor_assert(circ->hs_ident);
 }

 /* Remember PoW state if this introduction included a valid proof of work
  * client puzzle extension. */
 if (rdv_data->pow_effort > 0) {
   circ->hs_pow_effort = rdv_data->pow_effort;
   circ->hs_with_pow_circ = 1;
 }

 /* Setup congestion control if asked by the client from the INTRO cell. */
 if (rdv_data->cc_enabled) {
   hs_circ_setup_congestion_control(circ, congestion_control_sendme_inc(),
                                    service->config.is_single_onion);
 }

end:
 extend_info_free(info);
}

/** Return true iff the given service rendezvous circuit circ is allowed for a
* relaunch to the rendezvous point. */
static int
can_relaunch_service_rendezvous_point(const origin_circuit_t *circ)
{
 tor_assert(circ);
 /* This is initialized when allocating an origin circuit. */
 tor_assert(circ->build_state);
 tor_assert(TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_S_CONNECT_REND);

 /* XXX: Retrying under certain condition. This is related to #22455. */

 /* We check failure_count >= hs_get_service_max_rend_failures()-1 below, and
  * the -1 is because we increment the failure count for our current failure
  * *after* this clause. */
 int max_rend_failures = hs_get_service_max_rend_failures() - 1;

 /* A failure count that has reached maximum allowed or circuit that expired,
  * we skip relaunching. */
 if (circ->build_state->failure_count > max_rend_failures ||
     circ->build_state->expiry_time <= time(NULL)) {
   log_info(LD_REND, "Attempt to build a rendezvous circuit to %s has "
                     "failed with %d attempts and expiry time %ld. "
                     "Giving up building.",
            safe_str_client(
                 extend_info_describe(circ->build_state->chosen_exit)),
            circ->build_state->failure_count,
            (long int) circ->build_state->expiry_time);
   goto disallow;
 }

 /* Allowed to relaunch. */
 return 1;
disallow:
 return 0;
}

/** Retry the rendezvous point of circ by launching a new circuit to it. */
static void
retry_service_rendezvous_point(const origin_circuit_t *circ)
{
 int flags = 0;
 origin_circuit_t *new_circ;
 cpath_build_state_t *bstate;

 tor_assert(circ);
 /* This is initialized when allocating an origin circuit. */
 tor_assert(circ->build_state);
 tor_assert(TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_S_CONNECT_REND);

 /* Ease our life. */
 bstate = circ->build_state;

 log_info(LD_REND, "Retrying rendezvous point circuit to %s",
          safe_str_client(extend_info_describe(bstate->chosen_exit)));

 /* Get the current build state flags for the next circuit. */
 flags |= (bstate->need_uptime) ? CIRCLAUNCH_NEED_UPTIME : 0;
 flags |= (bstate->need_capacity) ? CIRCLAUNCH_NEED_CAPACITY : 0;
 flags |= (bstate->is_internal) ? CIRCLAUNCH_IS_INTERNAL : 0;

 /* We do NOT add the onehop tunnel flag even though it might be a single
  * onion service. The reason is that if we failed once to connect to the RP
  * with a direct connection, we consider that chances are that we will fail
  * again so try a 3-hop circuit and hope for the best. Because the service
  * has no anonymity (single onion), this change of behavior won't affect
  * security directly. */

 new_circ = circuit_launch_by_extend_info(CIRCUIT_PURPOSE_S_CONNECT_REND,
                                          bstate->chosen_exit, flags);
 if (new_circ == NULL) {
   log_warn(LD_REND, "Failed to launch rendezvous circuit to %s",
            safe_str_client(extend_info_describe(bstate->chosen_exit)));

   hs_metrics_failed_rdv(&circ->hs_ident->identity_pk,
                         HS_METRICS_ERR_RDV_RETRY);

   goto done;
 }

 /* Transfer build state information to the new circuit state in part to
  * catch any other failures. */
 new_circ->build_state->failure_count = bstate->failure_count+1;
 new_circ->build_state->expiry_time = bstate->expiry_time;
 new_circ->hs_ident = hs_ident_circuit_dup(circ->hs_ident);

 /* Setup congestion control if asked by the client from the INTRO cell. */
 if (TO_CIRCUIT(circ)->ccontrol) {
   /* As per above, in this case, we are a full 3 hop rend, even if we're a
    * single-onion service. */
   hs_circ_setup_congestion_control(new_circ,
                                    TO_CIRCUIT(circ)->ccontrol->sendme_inc,
                                    false);
 }

done:
 return;
}

/** Using the given descriptor intro point ip, the node of the
* rendezvous point rp_node and the service's subcredential, populate the
* already allocated intro1_data object with the needed key material and link
* specifiers.
*
* Return 0 on success or a negative value if we couldn't properly filled the
* introduce1 data from the RP node. In other word, it means the RP node is
* unusable to use in the introduction. */
static int
setup_introduce1_data(const hs_desc_intro_point_t *ip,
                     const node_t *rp_node,
                     const hs_subcredential_t *subcredential,
                     hs_cell_introduce1_data_t *intro1_data)
{
 int ret = -1;
 smartlist_t *rp_lspecs;

 tor_assert(ip);
 tor_assert(rp_node);
 tor_assert(subcredential);
 tor_assert(intro1_data);

 /* Build the link specifiers from the node at the end of the rendezvous
  * circuit that we opened for this introduction. */
 rp_lspecs = node_get_link_specifier_smartlist(rp_node, 0);
 if (smartlist_len(rp_lspecs) == 0) {
   /* We can't rendezvous without link specifiers. */
   smartlist_free(rp_lspecs);
   goto end;
 }

 /* Populate the introduce1 data object. */
 memset(intro1_data, 0, sizeof(hs_cell_introduce1_data_t));
 intro1_data->auth_pk = &ip->auth_key_cert->signed_key;
 intro1_data->enc_pk = &ip->enc_key;
 intro1_data->subcredential = subcredential;
 intro1_data->link_specifiers = rp_lspecs;
 intro1_data->onion_pk = node_get_curve25519_onion_key(rp_node);
 if (intro1_data->onion_pk == NULL) {
   /* We can't rendezvous without the curve25519 onion key. */
   goto end;
 }

 /* Success, we have valid introduce data. */
 ret = 0;

end:
 return ret;
}

/** Helper: cleanup function for client circuit. This is for every HS version.
* It is called from hs_circ_cleanup_on_close() entry point. */
static void
cleanup_on_close_client_circ(circuit_t *circ)
{
 tor_assert(circ);

 if (circuit_is_hs_v3(circ)) {
   hs_client_circuit_cleanup_on_close(circ);
 }
 /* It is possible the circuit has an HS purpose but no identifier (hs_ident).
  * Thus possible that this passes through. */
}

/** Helper: cleanup function for client circuit. This is for every HS version.
* It is called from hs_circ_cleanup_on_free() entry point. */
static void
cleanup_on_free_client_circ(circuit_t *circ)
{
 tor_assert(circ);

 if (circuit_is_hs_v3(circ)) {
   hs_client_circuit_cleanup_on_free(circ);
 }
 /* It is possible the circuit has an HS purpose but no identifier (hs_ident).
  * Thus possible that this passes through. */
}

/** Return less than 0 if a precedes b, 0 if a equals b and greater than 0 if
* b precedes a. Note that *higher* effort is *earlier* in the pqueue. */
static int
compare_rend_request_by_effort_(const void *_a, const void *_b)
{
 const pending_rend_t *a = _a, *b = _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;
 }
}

/** Return 1 if a request waiting in our service-side pqueue is old
* enough that we should just discard it rather than trying to respond,
* or 0 if we still like it. As a heuristic, choose half of the total
* permitted time interval (so we don't approve trying to respond to
* requests when we will then give up on them a moment later).
*/
static int
queued_rend_request_is_too_old(pending_rend_t *req, time_t now)
{
 if ((req->enqueued_ts + MAX_REND_TIMEOUT/2) < now)
   return 1;
 return 0;
}

/** Our rendezvous request priority queue is too full; keep the first
* pqueue_high_level/2 entries and discard the rest.
*/
static void
trim_rend_pqueue(hs_pow_service_state_t *pow_state, time_t now)
{
 smartlist_t *old_pqueue = pow_state->rend_request_pqueue;
 smartlist_t *new_pqueue = pow_state->rend_request_pqueue = smartlist_new();

 log_info(LD_REND, "Rendezvous request priority queue has "
                   "reached capacity (%d). Discarding the bottom half.",
                   smartlist_len(old_pqueue));

 while (smartlist_len(old_pqueue) &&
        smartlist_len(new_pqueue) < pow_state->pqueue_high_level/2) {
   /* while there are still old ones, and the new one isn't full yet */
   pending_rend_t *req =
     smartlist_pqueue_pop(old_pqueue,
                          compare_rend_request_by_effort_,
                          offsetof(pending_rend_t, idx));
   if (queued_rend_request_is_too_old(req, now)) {
     log_info(LD_REND, "While trimming, rend request has been pending "
                       "for too long; discarding.");

     pow_state->max_trimmed_effort = MAX(pow_state->max_trimmed_effort,
                                         req->rdv_data.pow_effort);

     free_pending_rend(req);
   } else {
     smartlist_pqueue_add(new_pqueue,
                          compare_rend_request_by_effort_,
                          offsetof(pending_rend_t, idx), req);
   }
 }

 /* Ok, we have rescued all the entries we want to keep. The rest are
  * all excess. */
 SMARTLIST_FOREACH_BEGIN(old_pqueue, pending_rend_t *, req) {
   pow_state->max_trimmed_effort = MAX(pow_state->max_trimmed_effort,
                                       req->rdv_data.pow_effort);
   free_pending_rend(req);
 } SMARTLIST_FOREACH_END(req);
 smartlist_free(old_pqueue);
}

/** Count up how many pending outgoing (CIRCUIT_PURPOSE_S_CONNECT_REND)
* circuits there are for this service. Used in the PoW rate limiting
* world to decide whether it's time to launch any new ones.
*/
static int
count_service_rp_circuits_pending(hs_service_t *service)
{
 origin_circuit_t *ocirc = NULL;
 int count = 0;
 while ((ocirc = circuit_get_next_by_purpose(ocirc,
                           CIRCUIT_PURPOSE_S_CONNECT_REND))) {
   /* Count up circuits that are v3 and for this service. */
   if (ocirc->hs_ident != NULL &&
       ed25519_pubkey_eq(&ocirc->hs_ident->identity_pk,
                         &service->keys.identity_pk)) {
     count++;
   }
 }
 return count;
}

/** Peek at the top entry on the pending rend pqueue, which must not be empty.
* If its level of effort is at least what we're suggesting for that service
* right now, return 1, else return 0.
*/
int
top_of_rend_pqueue_is_worthwhile(hs_pow_service_state_t *pow_state)
{
 tor_assert(pow_state->rend_request_pqueue);
 tor_assert(smartlist_len(pow_state->rend_request_pqueue));

 pending_rend_t *req =
   smartlist_get(pow_state->rend_request_pqueue, 0);

 if (req->rdv_data.pow_effort >= pow_state->suggested_effort)
   return 1;

 return 0;
}

/** Abandon and free all pending rend requests, leaving the pqueue empty. */
void
rend_pqueue_clear(hs_pow_service_state_t *pow_state)
{
 tor_assert(pow_state->rend_request_pqueue);
 while (smartlist_len(pow_state->rend_request_pqueue)) {
   pending_rend_t *req = smartlist_pop_last(pow_state->rend_request_pqueue);
   free_pending_rend(req);
 }
}

/** What is the threshold of in-progress (CIRCUIT_PURPOSE_S_CONNECT_REND)
* rendezvous responses above which we won't launch new low-effort rendezvous
* responses? (Intro2 cells with suitable PoW effort are not affected
* by this threshold.) */
#define MAX_CHEAP_REND_CIRCUITS_IN_PROGRESS 16

static void
handle_rend_pqueue_cb(mainloop_event_t *ev, void *arg)
{
 hs_service_t *service = arg;
 hs_pow_service_state_t *pow_state = service->state.pow_state;
 time_t now = time(NULL);
 int in_flight = count_service_rp_circuits_pending(service);

 (void) ev; /* Not using the returned event, make compiler happy. */

 log_info(LD_REND, "Considering launching more rendezvous responses. "
          "%d in-flight, %d pending.",
          in_flight,
          smartlist_len(pow_state->rend_request_pqueue));

 /* Process only one rend request per callback, so that this work will not
  * be prioritized over other event loop callbacks. We may need to retry
  * in order to find one request that's still viable. */
 while (smartlist_len(pow_state->rend_request_pqueue) > 0) {

   /* first, peek at the top result to see if we want to pop it */
   if (in_flight >= MAX_CHEAP_REND_CIRCUITS_IN_PROGRESS &&
       !top_of_rend_pqueue_is_worthwhile(pow_state)) {
     /* We have queued requests, but they are all low priority, and also
      * we have too many in-progress rendezvous responses. Don't launch
      * any more. Schedule ourselves to reassess in a bit. */
     log_info(LD_REND, "Next request to launch is low priority, and "
              "%d in-flight already. Waiting to launch more.", in_flight);
     const struct timeval delay_tv = { 0, 100000 };
     mainloop_event_schedule(pow_state->pop_pqueue_ev, &delay_tv);
     return; /* done here! no cleanup needed. */
   }

   if (pow_state->using_pqueue_bucket) {
     token_bucket_ctr_refill(&pow_state->pqueue_bucket,
                             (uint32_t) monotime_coarse_absolute_sec());

     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,
                          compare_rend_request_by_effort_,
                          offsetof(pending_rend_t, idx));

   hs_metrics_pow_pqueue_rdv(service,
                             smartlist_len(pow_state->rend_request_pqueue));

   log_info(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)) {
     log_info(LD_REND, "Top rend request has been pending for too long; "
                       "discarding and moving to the next one.");
     free_pending_rend(req);
     continue; /* do not increment count, this one's free */
   }

   /* Launch the rendezvous circuit. */
   launch_rendezvous_point_circuit(service, &req->ip_auth_pubkey,
                                   &req->ip_enc_key_kp, &req->rdv_data, now);
   free_pending_rend(req);

   ++pow_state->rend_handled;
   ++in_flight;
   break;
 }

 /* If there are still some pending rendezvous circuits in the pqueue then
  * reschedule the event in order to continue handling them. */
 if (smartlist_len(pow_state->rend_request_pqueue) > 0) {
   mainloop_event_activate(pow_state->pop_pqueue_ev);

   if (smartlist_len(pow_state->rend_request_pqueue) >=
       pow_state->pqueue_low_level) {
     pow_state->had_queue = 1;
   }
 }
}

/** Given the information needed to launch a rendezvous circuit and an
* effort value, enqueue the rendezvous request in the service's PoW priority
* queue with the effort being the priority.
*
* Return 0 if we successfully enqueued the request else -1. */
static int
enqueue_rend_request(const hs_service_t *service, hs_service_intro_point_t *ip,
                    hs_cell_introduce2_data_t *data, time_t now)
{
 hs_pow_service_state_t *pow_state = NULL;
 pending_rend_t *req = NULL;

 tor_assert(service);
 tor_assert(ip);
 tor_assert(data);

 /* Ease our lives */
 pow_state = service->state.pow_state;

 req = tor_malloc_zero(sizeof(pending_rend_t));

 /* Copy over the rendezvous request the needed data to launch a circuit. */
 ed25519_pubkey_copy(&req->ip_auth_pubkey, &ip->auth_key_kp.pubkey);
 memcpy(&req->ip_enc_key_kp, &ip->enc_key_kp, sizeof(req->ip_enc_key_kp));
 memcpy(&req->rdv_data, &data->rdv_data, sizeof(req->rdv_data));
 /* Invalidate the link specifier pointer in the introduce2 data so it
  * doesn't get freed under us. */
 data->rdv_data.link_specifiers = NULL;
 req->idx = -1;
 req->enqueued_ts = now;

 /* Enqueue the rendezvous request. */
 smartlist_pqueue_add(pow_state->rend_request_pqueue,
                      compare_rend_request_by_effort_,
                      offsetof(pending_rend_t, idx), req);

 hs_metrics_pow_pqueue_rdv(service,
                           smartlist_len(pow_state->rend_request_pqueue));

 log_info(LD_REND, "Enqueued rendezvous request with effort: %u. "
                   "Queued requests: %u",
          req->rdv_data.pow_effort,
          smartlist_len(pow_state->rend_request_pqueue));

 /* Initialize the priority queue event if it hasn't been done so already. */
 if (pow_state->pop_pqueue_ev == NULL) {
   pow_state->pop_pqueue_ev =
       mainloop_event_postloop_new(handle_rend_pqueue_cb, (void *)service);
 }

 /* Activate event, we just enqueued a rendezvous request. */
 mainloop_event_activate(pow_state->pop_pqueue_ev);

 /* See if there are so many cells queued that we need to cull. */
 if (smartlist_len(pow_state->rend_request_pqueue) >=
       pow_state->pqueue_high_level) {
   trim_rend_pqueue(pow_state, now);
   hs_metrics_pow_pqueue_rdv(service,
                             smartlist_len(pow_state->rend_request_pqueue));
 }

 return 0;
}

/* ========== */
/* Public API */
/* ========== */

/** Setup on the given circuit congestion control with the given parameters.
*
* This function assumes that congestion control is enabled on the network and
* so it is the caller responsability to make sure of it. */
void
hs_circ_setup_congestion_control(origin_circuit_t *origin_circ,
                                uint8_t sendme_inc, bool is_single_onion)
{
 circuit_t *circ = NULL;
 circuit_params_t circ_params = {0};

 tor_assert(origin_circ);

 /* Ease our lives */
 circ = TO_CIRCUIT(origin_circ);

 circ_params.cc_enabled = true;
 circ_params.sendme_inc_cells = sendme_inc;

 /* It is setup on the circuit in order to indicate that congestion control is
  * enabled. It will be transferred to the RP crypt_path_t once the handshake
  * is finalized in finalize_rend_circuit() for both client and service
  * because the final hop is not available until then. */

 if (is_single_onion) {
   circ->ccontrol = congestion_control_new(&circ_params, CC_PATH_ONION_SOS);
 } else {
   if (get_options()->HSLayer3Nodes) {
     circ->ccontrol = congestion_control_new(&circ_params, CC_PATH_ONION_VG);
   } else {
     circ->ccontrol = congestion_control_new(&circ_params, CC_PATH_ONION);
   }
 }
}

/** Return an introduction point circuit matching the given intro point object.
* NULL is returned is no such circuit can be found. */
origin_circuit_t *
hs_circ_service_get_intro_circ(const hs_service_intro_point_t *ip)
{
 tor_assert(ip);

 return hs_circuitmap_get_intro_circ_v3_service_side(&ip->auth_key_kp.pubkey);
}

/** Return an introduction point established circuit matching the given intro
* point object. The circuit purpose has to be CIRCUIT_PURPOSE_S_INTRO. NULL
* is returned is no such circuit can be found. */
origin_circuit_t *
hs_circ_service_get_established_intro_circ(const hs_service_intro_point_t *ip)
{
 origin_circuit_t *circ;

 tor_assert(ip);

 circ = hs_circuitmap_get_intro_circ_v3_service_side(&ip->auth_key_kp.pubkey);

 /* Only return circuit if it is established. */
 return (circ && TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_S_INTRO) ?
         circ : NULL;
}

/** Called when we fail building a rendezvous circuit at some point other than
* the last hop: launches a new circuit to the same rendezvous point.
*
* We currently relaunch connections to rendezvous points if:
* - A rendezvous circuit timed out before connecting to RP.
* - The rendezvous circuit failed to connect to the RP.
*
* We avoid relaunching a connection to this rendezvous point if:
* - We have already tried MAX_REND_FAILURES times to connect to this RP,
* - We've been trying to connect to this RP for more than MAX_REND_TIMEOUT
*   seconds, or
* - We've already retried this specific rendezvous circuit.
*/
void
hs_circ_retry_service_rendezvous_point(const origin_circuit_t *circ)
{
 tor_assert(circ);
 tor_assert(TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_S_CONNECT_REND);

 /* Check if we are allowed to relaunch to the rendezvous point of circ. */
 if (!can_relaunch_service_rendezvous_point(circ)) {
   goto done;
 }

 /* Legacy services don't have a hidden service ident. */
 if (circ->hs_ident) {
   retry_service_rendezvous_point(circ);
 }

done:
 return;
}

/** For a given service and a service intro point, launch a circuit to the
* extend info ei. If the service is a single onion, and direct_conn is true,
* a one-hop circuit will be requested.
*
* Return 0 if the circuit was successfully launched and tagged
* with the correct identifier. On error, a negative value is returned. */
int
hs_circ_launch_intro_point(hs_service_t *service,
                          const hs_service_intro_point_t *ip,
                          extend_info_t *ei,
                          bool direct_conn)
{
 /* Standard flags for introduction circuit. */
 int ret = -1, circ_flags = CIRCLAUNCH_NEED_UPTIME | CIRCLAUNCH_IS_INTERNAL;
 origin_circuit_t *circ;

 tor_assert(service);
 tor_assert(ip);
 tor_assert(ei);

 /* Update circuit flags in case of a single onion service that requires a
  * direct connection. */
 tor_assert_nonfatal(ip->circuit_retries > 0);
 /* Only single onion services can make direct conns */
 if (BUG(!service->config.is_single_onion && direct_conn)) {
   goto end;
 }
 /* We only use a one-hop path on the first attempt. If the first attempt
  * fails, we use a 3-hop path for reachability / reliability. */
 if (direct_conn && ip->circuit_retries == 1) {
   circ_flags |= CIRCLAUNCH_ONEHOP_TUNNEL;
 }

 log_info(LD_REND, "Launching a circuit to intro point %s for service %s.",
          safe_str_client(extend_info_describe(ei)),
          safe_str_client(service->onion_address));

 /* Note down the launch for the retry period. Even if the circuit fails to
  * be launched, we still want to respect the retry period to avoid stress on
  * the circuit subsystem. */
 service->state.num_intro_circ_launched++;
 circ = circuit_launch_by_extend_info(CIRCUIT_PURPOSE_S_ESTABLISH_INTRO,
                                      ei, circ_flags);
 if (circ == NULL) {
   goto end;
 }

 /* Setup the circuit identifier and attach it to it. */
 circ->hs_ident = create_intro_circuit_identifier(service, ip);
 tor_assert(circ->hs_ident);
 /* Register circuit in the global circuitmap. */
 register_intro_circ(ip, circ);

 /* Success. */
 ret = 0;
end:
 return ret;
}

/** Called when a service introduction point circuit is done building. Given
* the service and intro point object, this function will send the
* ESTABLISH_INTRO cell on the circuit. Return 0 on success. Return 1 if the
* circuit has been repurposed to General because we already have too many
* opened. */
int
hs_circ_service_intro_has_opened(hs_service_t *service,
                                hs_service_intro_point_t *ip,
                                const hs_service_descriptor_t *desc,
                                origin_circuit_t *circ)
{
 int ret = 0;
 unsigned int num_intro_circ, num_needed_circ;

 tor_assert(service);
 tor_assert(ip);
 tor_assert(desc);
 tor_assert(circ);

 /* Count opened circuits that have sent ESTABLISH_INTRO cells or are already
  * established introduction circuits */
 num_intro_circ = count_opened_desc_intro_point_circuits(service, desc);
 num_needed_circ = service->config.num_intro_points;
 if (num_intro_circ > num_needed_circ) {
   /* There are too many opened valid intro circuit for what the service
    * needs so repurpose this one. */

   /* XXX: Legacy code checks options->ExcludeNodes and if not NULL it just
    * closes the circuit. I have NO idea why it does that so it hasn't been
    * added here. I can only assume in case our ExcludeNodes list changes but
    * in that case, all circuit are flagged unusable (config.c). --dgoulet */

   log_info(LD_CIRC | LD_REND, "Introduction circuit just opened but we "
                               "have enough for service %s. Repurposing "
                               "it to general and leaving internal.",
            safe_str_client(service->onion_address));
   tor_assert(circ->build_state->is_internal);
   /* Remove it from the circuitmap. */
   hs_circuitmap_remove_circuit(TO_CIRCUIT(circ));
   /* Cleaning up the hidden service identifier and repurpose. */
   hs_ident_circuit_free(circ->hs_ident);
   circ->hs_ident = NULL;
   if (circuit_should_use_vanguards(TO_CIRCUIT(circ)->purpose))
     circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_HS_VANGUARDS);
   else
     circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_C_GENERAL);

   /* Inform that this circuit just opened for this new purpose. */
   circuit_has_opened(circ);
   /* This return value indicate to the caller that the IP object should be
    * removed from the service because it's corresponding circuit has just
    * been repurposed. */
   ret = 1;
   goto done;
 }

 log_info(LD_REND, "Introduction circuit %u established for service %s.",
          TO_CIRCUIT(circ)->n_circ_id,
          safe_str_client(service->onion_address));
 circuit_log_path(LOG_INFO, LD_REND, circ);

 /* Time to send an ESTABLISH_INTRO cell on this circuit. On error, this call
  * makes sure the circuit gets closed. */
 send_establish_intro(service, ip, circ);

done:
 return ret;
}

/** Called when a service rendezvous point circuit is done building. Given the
* service and the circuit, this function will send a RENDEZVOUS1 cell on the
* circuit using the information in the circuit identifier. If the cell can't
* be sent, the circuit is closed. */
void
hs_circ_service_rp_has_opened(const hs_service_t *service,
                             origin_circuit_t *circ)
{
 size_t payload_len;
 uint8_t payload[RELAY_PAYLOAD_SIZE_MAX] = {0};

 tor_assert(service);
 tor_assert(circ);
 tor_assert(circ->hs_ident);

 /* Some useful logging. */
 log_info(LD_REND, "Rendezvous circuit %u has opened with cookie %s "
                   "for service %s",
          TO_CIRCUIT(circ)->n_circ_id,
          hex_str((const char *) circ->hs_ident->rendezvous_cookie,
                  REND_COOKIE_LEN),
          safe_str_client(service->onion_address));
 circuit_log_path(LOG_INFO, LD_REND, circ);

 /* This can't fail. */
 payload_len = hs_cell_build_rendezvous1(
                       circ->hs_ident->rendezvous_cookie,
                       sizeof(circ->hs_ident->rendezvous_cookie),
                       circ->hs_ident->rendezvous_handshake_info,
                       sizeof(circ->hs_ident->rendezvous_handshake_info),
                       payload);

 /* Pad the payload with random bytes so it matches the size of a legacy cell
  * which is normally always bigger. Also, the size of a legacy cell is
  * always smaller than the RELAY_PAYLOAD_SIZE so this is safe. */
 if (payload_len < HS_LEGACY_RENDEZVOUS_CELL_SIZE) {
   crypto_rand((char *) payload + payload_len,
               HS_LEGACY_RENDEZVOUS_CELL_SIZE - payload_len);
   payload_len = HS_LEGACY_RENDEZVOUS_CELL_SIZE;
 }

 if (relay_send_command_from_edge(CONTROL_CELL_ID, TO_CIRCUIT(circ),
                                  RELAY_COMMAND_RENDEZVOUS1,
                                  (const char *) payload,
                                  payload_len,
                                  circ->cpath->prev) < 0) {
   /* On error, circuit is closed. */
   log_warn(LD_REND, "Unable to send RENDEZVOUS1 cell on circuit %u "
                     "for service %s",
            TO_CIRCUIT(circ)->n_circ_id,
            safe_str_client(service->onion_address));

   hs_metrics_failed_rdv(&service->keys.identity_pk,
                         HS_METRICS_ERR_RDV_RENDEZVOUS1);
   goto done;
 }

 /* Setup end-to-end rendezvous circuit between the client and us. */
 if (hs_circuit_setup_e2e_rend_circ(circ,
                      circ->hs_ident->rendezvous_ntor_key_seed,
                      sizeof(circ->hs_ident->rendezvous_ntor_key_seed),
                      1) < 0) {
   log_warn(LD_GENERAL, "Failed to setup circ");

   hs_metrics_failed_rdv(&service->keys.identity_pk, HS_METRICS_ERR_RDV_E2E);
   goto done;
 }

done:
 memwipe(payload, 0, sizeof(payload));
}

/** Circ has been expecting an INTRO_ESTABLISHED cell that just arrived. Handle
* the INTRO_ESTABLISHED cell payload of length payload_len arriving on the
* given introduction circuit circ. The service is only used for logging
* purposes. Return 0 on success else a negative value. */
int
hs_circ_handle_intro_established(const hs_service_t *service,
                                const hs_service_intro_point_t *ip,
                                origin_circuit_t *circ,
                                const uint8_t *payload, size_t payload_len)
{
 int ret = -1;

 tor_assert(service);
 tor_assert(ip);
 tor_assert(circ);
 tor_assert(payload);

 if (BUG(TO_CIRCUIT(circ)->purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)) {
   goto done;
 }

 /* Try to parse the payload into a cell making sure we do actually have a
  * valid cell. */
 if (hs_cell_parse_intro_established(payload, payload_len) < 0) {
   log_warn(LD_REND, "Unable to parse the INTRO_ESTABLISHED cell on "
                     "circuit %u for service %s",
            TO_CIRCUIT(circ)->n_circ_id,
            safe_str_client(service->onion_address));
   goto done;
 }

 /* Switch the purpose to a fully working intro point. */
 circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_S_INTRO);
 /* Getting a valid INTRODUCE_ESTABLISHED means we've successfully used the
  * circuit so update our pathbias subsystem. */
 pathbias_mark_use_success(circ);
 /* Success. */
 ret = 0;

done:
 return ret;
}

/**
*  Go into <b>data</b> and add the right subcredential to be able to handle
*  this incoming cell.
*
*  <b>desc_subcred</b> is the subcredential of the descriptor that corresponds
*  to the intro point that received this intro request. This subcredential
*  should be used if we are not an onionbalance instance.
*
*  Return 0 if everything went well, or -1 in case of internal error.
*/
static int
get_subcredential_for_handling_intro2_cell(const hs_service_t *service,
                                       hs_cell_introduce2_data_t *data,
                                       const hs_subcredential_t *desc_subcred)
{
 /* Handle the simple case first: We are not an onionbalance instance and we
  * should just use the regular descriptor subcredential */
 if (!hs_ob_service_is_instance(service)) {
   data->n_subcredentials = 1;
   data->subcredentials = desc_subcred;
   return 0;
 }

 /* This should not happen since we should have made onionbalance
  * subcredentials when we created our descriptors. */
 if (BUG(!service->state.ob_subcreds)) {
   return -1;
 }

 /* We are an onionbalance instance: */
 data->n_subcredentials = service->state.n_ob_subcreds;
 data->subcredentials = service->state.ob_subcreds;

 return 0;
}

/** We just received an INTRODUCE2 cell on the established introduction circuit
* circ.  Handle the INTRODUCE2 payload of size payload_len for the given
* circuit and service. This cell is associated with the intro point object ip
* and the subcredential. Return 0 on success else a negative value. */
int
hs_circ_handle_introduce2(const hs_service_t *service,
                         const origin_circuit_t *circ,
                         hs_service_intro_point_t *ip,
                         const hs_subcredential_t *subcredential,
                         const uint8_t *payload, size_t payload_len)
{
 int ret = -1;
 time_t elapsed;
 hs_cell_introduce2_data_t data;
 time_t now = time(NULL);

 tor_assert(service);
 tor_assert(circ);
 tor_assert(ip);
 tor_assert(subcredential);
 tor_assert(payload);

 /* Populate the data structure with everything we need for the cell to be
  * parsed, decrypted and key material computed correctly. */
 data.auth_pk = &ip->auth_key_kp.pubkey;
 data.enc_kp = &ip->enc_key_kp;
 data.payload = payload;
 data.payload_len = payload_len;
 data.replay_cache = ip->replay_cache;
 data.rdv_data.link_specifiers = smartlist_new();
 data.rdv_data.cc_enabled = 0;
 data.rdv_data.pow_effort = 0;

 if (get_subcredential_for_handling_intro2_cell(service, &data,
                                                subcredential)) {
   hs_metrics_reject_intro_req(service,
                               HS_METRICS_ERR_INTRO_REQ_SUBCREDENTIAL);
   goto done;
 }

 if (hs_cell_parse_introduce2(&data, circ, service, ip) < 0) {
   hs_metrics_reject_intro_req(service, HS_METRICS_ERR_INTRO_REQ_INTRODUCE2);
   goto done;
 }

 /* Check whether we've seen this REND_COOKIE before to detect repeats. */
 if (replaycache_add_test_and_elapsed(
          service->state.replay_cache_rend_cookie,
          data.rdv_data.rendezvous_cookie,
          sizeof(data.rdv_data.rendezvous_cookie),
          &elapsed)) {
   /* A Tor client will send a new INTRODUCE1 cell with the same REND_COOKIE
    * as its previous one if its intro circ times out while in state
    * CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT. If we received the first
    * INTRODUCE1 cell (the intro-point relay converts it into an INTRODUCE2
    * cell), we are already trying to connect to that rend point (and may
    * have already succeeded); drop this cell. */
   log_info(LD_REND, "We received an INTRODUCE2 cell with same REND_COOKIE "
                     "field %ld seconds ago. Dropping cell.",
            (long int) elapsed);
   hs_metrics_reject_intro_req(service,
                               HS_METRICS_ERR_INTRO_REQ_INTRODUCE2_REPLAY);
   goto done;
 }

 /* At this point, we just confirmed that the full INTRODUCE2 cell is valid
  * so increment our counter that we've seen one on this intro point. */
 ip->introduce2_count++;

 /* Add the rendezvous request to the priority queue if PoW defenses are
  * enabled, otherwise rendezvous as usual. */
 if (have_module_pow() && service->config.has_pow_defenses_enabled) {
   log_info(LD_REND,
            "Adding introduction request to pqueue with effort: %u",
            data.rdv_data.pow_effort);
   if (enqueue_rend_request(service, ip, &data, now) < 0) {
     goto done;
   }

   /* Track the total effort in valid requests received this period */
   service->state.pow_state->total_effort += data.rdv_data.pow_effort;

   /* Successfully added rend circuit to priority queue. */
   ret = 0;
   goto done;
 }

 /* Launch rendezvous circuit with the onion key and rend cookie. */
 launch_rendezvous_point_circuit(service, &ip->auth_key_kp.pubkey,
                                 &ip->enc_key_kp, &data.rdv_data, now);
 /* Success. */
 ret = 0;

done:
 /* Note that if PoW defenses are enabled, this is NULL. */
 link_specifier_smartlist_free(data.rdv_data.link_specifiers);
 memwipe(&data, 0, sizeof(data));
 return ret;
}

/** Circuit <b>circ</b> just finished the rend ntor key exchange. Use the key
* exchange output material at <b>ntor_key_seed</b> and setup <b>circ</b> to
* serve as a rendezvous end-to-end circuit between the client and the
* service. If <b>is_service_side</b> is set, then we are the hidden service
* and the other side is the client.
*
* Return 0 if the operation went well; in case of error return -1. */
int
hs_circuit_setup_e2e_rend_circ(origin_circuit_t *circ,
                              const uint8_t *ntor_key_seed, size_t seed_len,
                              int is_service_side)
{
 if (BUG(!circuit_purpose_is_correct_for_rend(TO_CIRCUIT(circ)->purpose,
                                       is_service_side))) {
   return -1;
 }

 crypt_path_t *hop = create_rend_cpath(ntor_key_seed, seed_len,
                                       is_service_side);
 if (!hop) {
   log_warn(LD_REND, "Couldn't get v3 %s cpath!",
            is_service_side ? "service-side" : "client-side");
   return -1;
 }

 finalize_rend_circuit(circ, hop, is_service_side);

 return 0;
}

/** Given the introduction circuit intro_circ, the rendezvous circuit
* rend_circ, a descriptor intro point object ip and the service's
* subcredential, send an INTRODUCE1 cell on intro_circ.
*
* This will also setup the circuit identifier on rend_circ containing the key
* material for the handshake and e2e encryption. Return 0 on success else
* negative value. Because relay_send_command_from_edge() closes the circuit
* on error, it is possible that intro_circ is closed on error. */
int
hs_circ_send_introduce1(origin_circuit_t *intro_circ,
                       origin_circuit_t *rend_circ,
                       const hs_desc_intro_point_t *ip,
                       const hs_subcredential_t *subcredential,
                       const hs_pow_solution_t *pow_solution)
{
 int ret = -1;
 ssize_t payload_len;
 uint8_t payload[RELAY_PAYLOAD_SIZE_MAX] = {0};
 hs_cell_introduce1_data_t intro1_data;

 tor_assert(intro_circ);
 tor_assert(rend_circ);
 tor_assert(ip);
 tor_assert(subcredential);

 /* It is undefined behavior in hs_cell_introduce1_data_clear() if intro1_data
  * has been declared on the stack but not initialized. Here, we set it to 0.
  */
 memset(&intro1_data, 0, sizeof(hs_cell_introduce1_data_t));

 /* This takes various objects in order to populate the introduce1 data
  * object which is used to build the content of the cell. */
 const node_t *exit_node = build_state_get_exit_node(rend_circ->build_state);
 if (exit_node == NULL) {
   log_info(LD_REND, "Unable to get rendezvous point for circuit %u. "
            "Failing.", TO_CIRCUIT(intro_circ)->n_circ_id);
   goto done;
 }

 /* We should never select an invalid rendezvous point in theory but if we
  * do, this function will fail to populate the introduce data. */
 if (setup_introduce1_data(ip, exit_node, subcredential, &intro1_data) < 0) {
   log_info(LD_REND, "Unable to setup INTRODUCE1 data. The chosen rendezvous "
                     "point is unusable. Closing circuit.");
   goto close;
 }

 /* Set the PoW solution if any. */
 intro1_data.pow_solution = pow_solution;

 /* If the rend circ was set up for congestion control, add that to the
  * intro data, to signal it in an extension */
 if (TO_CIRCUIT(rend_circ)->ccontrol) {
   intro1_data.cc_enabled = 1;
 }

 /* Final step before we encode a cell, we setup the circuit identifier which
  * will generate both the rendezvous cookie and client keypair for this
  * connection. Those are put in the ident. */
 intro1_data.rendezvous_cookie = rend_circ->hs_ident->rendezvous_cookie;
 intro1_data.client_kp = &rend_circ->hs_ident->rendezvous_client_kp;

 memcpy(intro_circ->hs_ident->rendezvous_cookie,
        rend_circ->hs_ident->rendezvous_cookie,
        sizeof(intro_circ->hs_ident->rendezvous_cookie));

 /* From the introduce1 data object, this will encode the INTRODUCE1 cell
  * into payload which is then ready to be sent as is. */
 payload_len = hs_cell_build_introduce1(&intro1_data, payload);
 if (BUG(payload_len < 0)) {
   goto close;
 }

 if (relay_send_command_from_edge(CONTROL_CELL_ID, TO_CIRCUIT(intro_circ),
                                  RELAY_COMMAND_INTRODUCE1,
                                  (const char *) payload, payload_len,
                                  intro_circ->cpath->prev) < 0) {
   /* On error, circuit is closed. */
   log_warn(LD_REND, "Unable to send INTRODUCE1 cell on circuit %u.",
            TO_CIRCUIT(intro_circ)->n_circ_id);
   goto done;
 }

 /* Success. */
 ret = 0;
 goto done;

close:
 circuit_mark_for_close(TO_CIRCUIT(rend_circ), END_CIRC_REASON_INTERNAL);
done:
 hs_cell_introduce1_data_clear(&intro1_data);
 memwipe(payload, 0, sizeof(payload));
 return ret;
}

/** Send an ESTABLISH_RENDEZVOUS cell along the rendezvous circuit circ. On
* success, 0 is returned else -1 and the circuit is marked for close. */
int
hs_circ_send_establish_rendezvous(origin_circuit_t *circ)
{
 ssize_t cell_len = 0;
 uint8_t cell[RELAY_PAYLOAD_SIZE_MAX] = {0};

 tor_assert(circ);
 tor_assert(TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND);

 log_info(LD_REND, "Send an ESTABLISH_RENDEZVOUS cell on circuit %u",
          TO_CIRCUIT(circ)->n_circ_id);

 /* Set timestamp_dirty, because circuit_expire_building expects it,
  * and the rend cookie also means we've used the circ. */
 TO_CIRCUIT(circ)->timestamp_dirty = time(NULL);

 /* We've attempted to use this circuit. Probe it if we fail */
 pathbias_count_use_attempt(circ);

 /* Generate the RENDEZVOUS_COOKIE and place it in the identifier so we can
  * complete the handshake when receiving the acknowledgement. */
 crypto_rand((char *) circ->hs_ident->rendezvous_cookie, HS_REND_COOKIE_LEN);
 /* Generate the client keypair. No need to be extra strong, not long term */
 curve25519_keypair_generate(&circ->hs_ident->rendezvous_client_kp, 0);

 cell_len =
   hs_cell_build_establish_rendezvous(circ->hs_ident->rendezvous_cookie,
                                      cell);
 if (BUG(cell_len < 0)) {
   goto err;
 }

 if (relay_send_command_from_edge(CONTROL_CELL_ID, TO_CIRCUIT(circ),
                                  RELAY_COMMAND_ESTABLISH_RENDEZVOUS,
                                  (const char *) cell, cell_len,
                                  circ->cpath->prev) < 0) {
   /* Circuit has been marked for close */
   log_warn(LD_REND, "Unable to send ESTABLISH_RENDEZVOUS cell on "
                     "circuit %u", TO_CIRCUIT(circ)->n_circ_id);
   memwipe(cell, 0, cell_len);
   goto err;
 }

 memwipe(cell, 0, cell_len);
 return 0;
err:
 return -1;
}

/** Circuit cleanup strategy:
*
*  What follows is a series of functions that notifies the HS subsystem of 3
*  different circuit cleanup phase: close, free and repurpose.
*
*  Tor can call any of those in any orders so they have to be safe between
*  each other. In other words, the free should never depend on close to be
*  called before.
*
*  The "on_close()" is called from circuit_mark_for_close() which is
*  considered the tor fast path and thus as little work as possible should
*  done in that function. Currently, we only remove the circuit from the HS
*  circuit map and move on.
*
*  The "on_free()" is called from circuit circuit_free_() and it is very
*  important that at the end of the function, no state or objects related to
*  this circuit remains alive.
*
*  The "on_repurpose()" is called from circuit_change_purpose() for which we
*  simply remove it from the HS circuit map. We do not have other cleanup
*  requirements after that.
*
*  NOTE: The onion service code, specifically the service code, cleans up
*  lingering objects or state if any of its circuit disappear which is why
*  our cleanup strategy doesn't involve any service specific actions. As long
*  as the circuit is removed from the HS circuit map, it won't be used.
*/

/** We are about to close this <b>circ</b>. Clean it up from any related HS
* data structures. This function can be called multiple times safely for the
* same circuit. */
void
hs_circ_cleanup_on_close(circuit_t *circ)
{
 tor_assert(circ);

 if (circuit_purpose_is_hs_client(circ->purpose)) {
   cleanup_on_close_client_circ(circ);
 }

 if (circuit_purpose_is_hs_service(circ->purpose)) {
   if (circuit_is_hs_v3(circ)) {
     hs_service_circuit_cleanup_on_close(circ);
   }
 }

 /* On close, we simply remove it from the circuit map. It can not be used
  * anymore. We keep this code path fast and lean. */

 if (circ->hs_token) {
   hs_circuitmap_remove_circuit(circ);
 }
}

/** We are about to free this <b>circ</b>. Clean it up from any related HS
* data structures. This function can be called multiple times safely for the
* same circuit. */
void
hs_circ_cleanup_on_free(circuit_t *circ)
{
 tor_assert(circ);

 /* NOTE: Bulk of the work of cleaning up a circuit is done here. */

 if (circuit_purpose_is_hs_client(circ->purpose)) {
   cleanup_on_free_client_circ(circ);
 }

 /* We have no assurance that the given HS circuit has been closed before and
  * thus removed from the HS map. This actually happens in unit tests. */
 if (circ->hs_token) {
   hs_circuitmap_remove_circuit(circ);
 }
}

/** We are about to repurpose this <b>circ</b>. Clean it up from any related
* HS data structures. This function can be called multiple times safely for
* the same circuit. */
void
hs_circ_cleanup_on_repurpose(circuit_t *circ)
{
 tor_assert(circ);

 /* On repurpose, we simply remove it from the circuit map but we do not do
  * the on_free actions since we don't treat a repurpose as something we need
  * to report in the client cache failure. */

 if (circ->hs_token) {
   hs_circuitmap_remove_circuit(circ);
 }

 switch (circ->purpose) {
 case CIRCUIT_PURPOSE_S_CONNECT_REND:
   /* This circuit was connecting to a rendezvous point but it is being
    * repurposed so we need to relaunch an attempt else the client will be
    * left hanging waiting for the rendezvous. */
   hs_circ_retry_service_rendezvous_point(TO_ORIGIN_CIRCUIT(circ));
   break;
 default:
   break;
 }
}

/** Return true iff the given established client rendezvous circuit was sent
* into the INTRODUCE1 cell. This is called so we can take a decision on
* expiring or not the circuit.
*
* The caller MUST make sure the circuit is an established client rendezvous
* circuit (purpose: CIRCUIT_PURPOSE_C_REND_READY).
*
* This function supports all onion service versions. */
bool
hs_circ_is_rend_sent_in_intro1(const origin_circuit_t *circ)
{
 tor_assert(circ);
 /* This can only be called for a rendezvous circuit that is an established
  * confirmed rendezsvous circuit but without an introduction ACK. */
 tor_assert(TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_C_REND_READY);

 /* When the INTRODUCE1 cell is sent, the introduction encryption public
  * key is copied in the rendezvous circuit hs identifier. If it is a valid
  * key, we know that this circuit is waiting the ACK on the introduction
  * circuit. We want to _not_ spare the circuit if the key was never set. */

 if (circ->hs_ident) {
   /* v3. */
   if (curve25519_public_key_is_ok(&circ->hs_ident->intro_enc_pk)) {
     return true;
   }
 } else {
   /* A circuit with an HS purpose without an hs_ident in theory can not
    * happen. In case, scream loudly and return false to the caller that the
    * rendezvous was not sent in the INTRO1 cell. */
   tor_assert_nonfatal_unreached();
 }

 /* The rendezvous has not been specified in the INTRODUCE1 cell. */
 return false;
}