diff options
| -rw-r--r-- | changes/bug9841 | 7 | ||||
| -rw-r--r-- | src/or/circuitlist.c | 164 | ||||
| -rw-r--r-- | src/or/circuitlist.h | 6 | ||||
| -rw-r--r-- | src/or/or.h | 33 | ||||
| -rw-r--r-- | src/or/rendmid.c | 14 | ||||
| -rw-r--r-- | src/test/test_circuitlist.c | 90 |
6 files changed, 275 insertions, 39 deletions
diff --git a/changes/bug9841 b/changes/bug9841 new file mode 100644 index 000000000..8b40dda0c --- /dev/null +++ b/changes/bug9841 @@ -0,0 +1,7 @@ + o Minor features (performance): + + - Faster server-side lookups of rendezvous and introduction point + circuits by using hashtables instead of linear searches over all + the circuits. These functions previously accounted between 3 and + 7% of CPU usage on some busy relays. + diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index b03b590aa..87270037c 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -32,6 +32,7 @@ #include "rephist.h" #include "routerlist.h" #include "routerset.h" + #include "ht.h" /********* START VARIABLES **********/ @@ -45,6 +46,9 @@ static smartlist_t *circuits_pending_chans = NULL; static void circuit_free_cpath_node(crypt_path_t *victim); static void cpath_ref_decref(crypt_path_reference_t *cpath_ref); +//static void circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ, +// const uint8_t *token); +static void circuit_clear_rend_token(or_circuit_t *circ); /********* END VARIABLES ************/ @@ -756,6 +760,8 @@ circuit_free(circuit_t *circ) crypto_cipher_free(ocirc->n_crypto); crypto_digest_free(ocirc->n_digest); + circuit_clear_rend_token(ocirc); + if (ocirc->rend_splice) { or_circuit_t *other = ocirc->rend_splice; tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC); @@ -1229,43 +1235,167 @@ circuit_get_next_by_pk_and_purpose(origin_circuit_t *start, return NULL; } -/** Return the first OR circuit in the global list whose purpose is - * <b>purpose</b>, and whose rend_token is the <b>len</b>-byte - * <b>token</b>. */ +/** Map from rendezvous cookie to or_circuit_t */ +static digestmap_t *rend_cookie_map = NULL; + +/** Map from introduction point digest to or_circuit_t */ +static digestmap_t *intro_digest_map = NULL; + +/** Return the OR circuit whose purpose is <b>purpose</b>, and whose + * rend_token is the REND_TOKEN_LEN-byte <b>token</b>. If <b>is_rend_circ</b>, + * look for rendezvous point circuits; otherwise look for introduction point + * circuits. */ static or_circuit_t * -circuit_get_by_rend_token_and_purpose(uint8_t purpose, const char *token, - size_t len) +circuit_get_by_rend_token_and_purpose(uint8_t purpose, int is_rend_circ, + const char *token) { - circuit_t *circ; - TOR_LIST_FOREACH(circ, &global_circuitlist, head) { - if (! circ->marked_for_close && - circ->purpose == purpose && - tor_memeq(TO_OR_CIRCUIT(circ)->rend_token, token, len)) - return TO_OR_CIRCUIT(circ); + or_circuit_t *circ; + digestmap_t *map = is_rend_circ ? rend_cookie_map : intro_digest_map; + + if (!map) + return NULL; + + circ = digestmap_get(map, token); + if (!circ || + circ->base_.purpose != purpose || + circ->base_.marked_for_close) + return NULL; + + if (!circ->rendinfo || + ! bool_eq(circ->rendinfo->is_rend_circ, is_rend_circ) || + tor_memneq(circ->rendinfo->rend_token, token, REND_TOKEN_LEN)) { + char *t = tor_strdup(hex_str(token, REND_TOKEN_LEN)); + log_warn(LD_BUG, "Wanted a circuit with %s:%d, but lookup returned %s:%d", + safe_str(t), is_rend_circ, + safe_str(hex_str(circ->rendinfo->rend_token, REND_TOKEN_LEN)), + (int)circ->rendinfo->is_rend_circ); + tor_free(t); + return NULL; } - return NULL; + + return circ; +} + +/** Clear the rendezvous cookie or introduction point key digest that's + * configured on <b>circ</b>, if any, and remove it from any such maps. */ +static void +circuit_clear_rend_token(or_circuit_t *circ) +{ + or_circuit_t *found_circ; + digestmap_t *map; + + if (!circ || !circ->rendinfo) + return; + + map = circ->rendinfo->is_rend_circ ? rend_cookie_map : intro_digest_map; + + if (!map) { + log_warn(LD_BUG, "Tried to clear rend token on circuit, but found no map"); + return; + } + + found_circ = digestmap_get(map, circ->rendinfo->rend_token); + if (found_circ == circ) { + /* Great, this is the right one. */ + digestmap_remove(map, circ->rendinfo->rend_token); + } else if (found_circ) { + log_warn(LD_BUG, "Tried to clear rend token on circuit, but " + "it was already replaced in the map."); + } else { + log_warn(LD_BUG, "Tried to clear rend token on circuit, but " + "it not in the map at all."); + } + + tor_free(circ->rendinfo); /* Sets it to NULL too */ +} + +/** Set the rendezvous cookie (if is_rend_circ), or the introduction point + * digest (if ! is_rend_circ) of <b>circ</b> to the REND_TOKEN_LEN-byte value + * in <b>token</b>, and add it to the appropriate map. If it previously had a + * token, clear it. If another circuit previously had the same + * cookie/intro-digest, mark that circuit and remove it from the map. */ +static void +circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ, + const uint8_t *token) +{ + digestmap_t **map_p, *map; + or_circuit_t *found_circ; + + /* Find the right map, creating it as needed */ + map_p = is_rend_circ ? &rend_cookie_map : &intro_digest_map; + + if (!*map_p) + *map_p = digestmap_new(); + + map = *map_p; + + /* If this circuit already has a token, we need to remove that. */ + if (circ->rendinfo) + circuit_clear_rend_token(circ); + + if (token == NULL) { + /* We were only trying to remove this token, not set a new one. */ + return; + } + + found_circ = digestmap_get(map, (const char *)token); + if (found_circ) { + tor_assert(found_circ != circ); + circuit_clear_rend_token(found_circ); + if (! found_circ->base_.marked_for_close) { + circuit_mark_for_close(TO_CIRCUIT(found_circ), END_CIRC_REASON_FINISHED); + if (is_rend_circ) { + log_fn(LOG_PROTOCOL_WARN, LD_REND, + "Duplicate rendezvous cookie (%s...) used on two circuits", + hex_str((const char*)token, 4)); /* only log first 4 chars */ + } + } + } + + /* Now set up the rendinfo */ + circ->rendinfo = tor_malloc(sizeof(*circ->rendinfo)); + memcpy(circ->rendinfo->rend_token, token, REND_TOKEN_LEN); + circ->rendinfo->is_rend_circ = is_rend_circ ? 1 : 0; + + digestmap_set(map, (const char *)token, circ); } /** Return the circuit waiting for a rendezvous with the provided cookie. * Return NULL if no such circuit is found. */ or_circuit_t * -circuit_get_rendezvous(const char *cookie) +circuit_get_rendezvous(const uint8_t *cookie) { return circuit_get_by_rend_token_and_purpose( CIRCUIT_PURPOSE_REND_POINT_WAITING, - cookie, REND_COOKIE_LEN); + 1, (const char*)cookie); } /** Return the circuit waiting for intro cells of the given digest. * Return NULL if no such circuit is found. */ or_circuit_t * -circuit_get_intro_point(const char *digest) +circuit_get_intro_point(const uint8_t *digest) { return circuit_get_by_rend_token_and_purpose( - CIRCUIT_PURPOSE_INTRO_POINT, digest, - DIGEST_LEN); + CIRCUIT_PURPOSE_INTRO_POINT, 0, + (const char *)digest); +} + +/** Set the rendezvous cookie of <b>circ</b> to <b>cookie</b>. If another + * circuit previously had that cookie, mark it. */ +void +circuit_set_rendezvous_cookie(or_circuit_t *circ, const uint8_t *cookie) +{ + circuit_set_rend_token(circ, 1, cookie); +} + +/** Set the intro point key digest of <b>circ</b> to <b>cookie</b>. If another + * circuit previously had that intro point digest, mark it. */ +void +circuit_set_intro_point_digest(or_circuit_t *circ, const uint8_t *digest) +{ + circuit_set_rend_token(circ, 0, digest); } /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL, diff --git a/src/or/circuitlist.h b/src/or/circuitlist.h index 54a7ef42f..2bbd20b83 100644 --- a/src/or/circuitlist.h +++ b/src/or/circuitlist.h @@ -46,8 +46,10 @@ origin_circuit_t *circuit_get_ready_rend_circ_by_rend_data( const rend_data_t *rend_data); origin_circuit_t *circuit_get_next_by_pk_and_purpose(origin_circuit_t *start, const char *digest, uint8_t purpose); -or_circuit_t *circuit_get_rendezvous(const char *cookie); -or_circuit_t *circuit_get_intro_point(const char *digest); +or_circuit_t *circuit_get_rendezvous(const uint8_t *cookie); +or_circuit_t *circuit_get_intro_point(const uint8_t *digest); +void circuit_set_rendezvous_cookie(or_circuit_t *circ, const uint8_t *cookie); +void circuit_set_intro_point_digest(or_circuit_t *circ, const uint8_t *digest); origin_circuit_t *circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, int flags); void circuit_mark_all_unused_circs(void); diff --git a/src/or/or.h b/src/or/or.h index 1b35c1f99..e17b5816a 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -3174,20 +3174,8 @@ typedef struct or_circuit_t { * is not marked for close. */ struct or_circuit_t *rend_splice; -#if REND_COOKIE_LEN >= DIGEST_LEN -#define REND_TOKEN_LEN REND_COOKIE_LEN -#else -#define REND_TOKEN_LEN DIGEST_LEN -#endif + struct or_circuit_rendinfo_s *rendinfo; - /** A hash of location-hidden service's PK if purpose is INTRO_POINT, or a - * rendezvous cookie if purpose is REND_POINT_WAITING. Filled with zeroes - * otherwise. - * ???? move to a subtype or adjunct structure? Wastes 20 bytes. -NM - */ - char rend_token[REND_TOKEN_LEN]; - - /* ???? move to a subtype or adjunct structure? Wastes 20 bytes -NM */ /** Stores KH for the handshake. */ char rend_circ_nonce[DIGEST_LEN];/* KH in tor-spec.txt */ @@ -3214,6 +3202,25 @@ typedef struct or_circuit_t { uint32_t max_middle_cells; } or_circuit_t; +typedef struct or_circuit_rendinfo_s { + +#if REND_COOKIE_LEN != DIGEST_LEN +#error "The REND_TOKEN_LEN macro assumes REND_COOKIE_LEN == DIGEST_LEN" +#endif +#define REND_TOKEN_LEN DIGEST_LEN + + /** A hash of location-hidden service's PK if purpose is INTRO_POINT, or a + * rendezvous cookie if purpose is REND_POINT_WAITING. Filled with zeroes + * otherwise. + */ + char rend_token[REND_TOKEN_LEN]; + + /** True if this is a rendezvous point circuit; false if this is an + * introduction point. */ + unsigned is_rend_circ; + +} or_circuit_rendinfo_t; + /** Convert a circuit subtype to a circuit_t. */ #define TO_CIRCUIT(x) (&((x)->base_)) diff --git a/src/or/rendmid.c b/src/or/rendmid.c index c68f6da59..110381680 100644 --- a/src/or/rendmid.c +++ b/src/or/rendmid.c @@ -94,7 +94,7 @@ rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request, /* Close any other intro circuits with the same pk. */ c = NULL; - while ((c = circuit_get_intro_point(pk_digest))) { + while ((c = circuit_get_intro_point((const uint8_t *)pk_digest))) { log_info(LD_REND, "Replacing old circuit for service %s", safe_str(serviceid)); circuit_mark_for_close(TO_CIRCUIT(c), END_CIRC_REASON_FINISHED); @@ -111,7 +111,7 @@ rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request, /* Now, set up this circuit. */ circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_INTRO_POINT); - memcpy(circ->rend_token, pk_digest, DIGEST_LEN); + circuit_set_intro_point_digest(circ, (uint8_t *)pk_digest); log_info(LD_REND, "Established introduction point on circuit %u for service %s", @@ -165,7 +165,7 @@ rend_mid_introduce(or_circuit_t *circ, const uint8_t *request, (char*)request, REND_SERVICE_ID_LEN); /* The first 20 bytes are all we look at: they have a hash of Bob's PK. */ - intro_circ = circuit_get_intro_point((char*)request); + intro_circ = circuit_get_intro_point((const uint8_t*)request); if (!intro_circ) { log_info(LD_REND, "No intro circ found for INTRODUCE1 cell (%s) from circuit %u; " @@ -236,7 +236,7 @@ rend_mid_establish_rendezvous(or_circuit_t *circ, const uint8_t *request, goto err; } - if (circuit_get_rendezvous((char*)request)) { + if (circuit_get_rendezvous(request)) { log_warn(LD_PROTOCOL, "Duplicate rendezvous cookie in ESTABLISH_RENDEZVOUS."); goto err; @@ -252,7 +252,7 @@ rend_mid_establish_rendezvous(or_circuit_t *circ, const uint8_t *request, } circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_REND_POINT_WAITING); - memcpy(circ->rend_token, request, REND_COOKIE_LEN); + circuit_set_rendezvous_cookie(circ, request); base16_encode(hexid,9,(char*)request,4); @@ -300,7 +300,7 @@ rend_mid_rendezvous(or_circuit_t *circ, const uint8_t *request, "Got request for rendezvous from circuit %u to cookie %s.", (unsigned)circ->p_circ_id, hexid); - rend_circ = circuit_get_rendezvous((char*)request); + rend_circ = circuit_get_rendezvous(request); if (!rend_circ) { log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL, "Rejecting RENDEZVOUS1 cell with unrecognized rendezvous cookie %s.", @@ -328,7 +328,7 @@ rend_mid_rendezvous(or_circuit_t *circ, const uint8_t *request, circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_REND_ESTABLISHED); circuit_change_purpose(TO_CIRCUIT(rend_circ), CIRCUIT_PURPOSE_REND_ESTABLISHED); - memset(circ->rend_token, 0, REND_COOKIE_LEN); + circuit_set_rendezvous_cookie(circ, NULL); rend_circ->rend_splice = circ; circ->rend_splice = rend_circ; diff --git a/src/test/test_circuitlist.c b/src/test/test_circuitlist.c index 54aa51d3c..54c0c03ca 100644 --- a/src/test/test_circuitlist.c +++ b/src/test/test_circuitlist.c @@ -161,8 +161,98 @@ test_clist_maps(void *arg) UNMOCK(circuitmux_detach_circuit); } +static void +test_rend_token_maps(void *arg) +{ + or_circuit_t *c1, *c2, *c3, *c4; + const uint8_t tok1[REND_TOKEN_LEN] = "The cat can't tell y"; + const uint8_t tok2[REND_TOKEN_LEN] = "ou its name, and it "; + const uint8_t tok3[REND_TOKEN_LEN] = "doesn't really care."; + /* -- Adapted from a quote by Fredrik Lundh. */ + + (void)arg; + (void)tok1; //xxxx + c1 = or_circuit_new(0, NULL); + c2 = or_circuit_new(0, NULL); + c3 = or_circuit_new(0, NULL); + c4 = or_circuit_new(0, NULL); + + tt_int_op(strlen((char*)tok1), ==, REND_TOKEN_LEN); + + /* No maps; nothing there. */ + tt_ptr_op(NULL, ==, circuit_get_rendezvous(tok1)); + tt_ptr_op(NULL, ==, circuit_get_intro_point(tok1)); + + circuit_set_rendezvous_cookie(c1, tok1); + circuit_set_intro_point_digest(c2, tok2); + + tt_ptr_op(NULL, ==, circuit_get_rendezvous(tok3)); + tt_ptr_op(NULL, ==, circuit_get_intro_point(tok3)); + tt_ptr_op(NULL, ==, circuit_get_rendezvous(tok2)); + tt_ptr_op(NULL, ==, circuit_get_intro_point(tok1)); + + /* Without purpose set, we don't get the circuits */ + tt_ptr_op(NULL, ==, circuit_get_rendezvous(tok1)); + tt_ptr_op(NULL, ==, circuit_get_intro_point(tok2)); + + c1->base_.purpose = CIRCUIT_PURPOSE_REND_POINT_WAITING; + c2->base_.purpose = CIRCUIT_PURPOSE_INTRO_POINT; + + /* Okay, make sure they show up now. */ + tt_ptr_op(c1, ==, circuit_get_rendezvous(tok1)); + tt_ptr_op(c2, ==, circuit_get_intro_point(tok2)); + + /* Two items at the same place with the same token. */ + c3->base_.purpose = CIRCUIT_PURPOSE_REND_POINT_WAITING; + circuit_set_rendezvous_cookie(c3, tok2); + tt_ptr_op(c2, ==, circuit_get_intro_point(tok2)); + tt_ptr_op(c3, ==, circuit_get_rendezvous(tok2)); + + /* Marking a circuit makes it not get returned any more */ + circuit_mark_for_close(TO_CIRCUIT(c1), END_CIRC_REASON_FINISHED); + tt_ptr_op(NULL, ==, circuit_get_rendezvous(tok1)); + circuit_free(TO_CIRCUIT(c1)); + c1 = NULL; + + /* Freeing a circuit makes it not get returned any more. */ + circuit_free(TO_CIRCUIT(c2)); + c2 = NULL; + tt_ptr_op(NULL, ==, circuit_get_intro_point(tok2)); + + /* c3 -- are you still there? */ + tt_ptr_op(c3, ==, circuit_get_rendezvous(tok2)); + /* Change its cookie. This never happens in Tor per se, but hey. */ + c3->base_.purpose = CIRCUIT_PURPOSE_INTRO_POINT; + circuit_set_intro_point_digest(c3, tok3); + + tt_ptr_op(NULL, ==, circuit_get_rendezvous(tok2)); + tt_ptr_op(c3, ==, circuit_get_intro_point(tok3)); + + /* Now replace c3 with c4. */ + c4->base_.purpose = CIRCUIT_PURPOSE_INTRO_POINT; + circuit_set_intro_point_digest(c4, tok3); + + tt_ptr_op(c4, ==, circuit_get_intro_point(tok3)); + + tt_ptr_op(c3->rendinfo, ==, NULL); + tt_ptr_op(c4->rendinfo, !=, NULL); + test_mem_op(c4->rendinfo, ==, tok3, REND_TOKEN_LEN); + + /* Now clear c4's cookie. */ + circuit_set_intro_point_digest(c4, NULL); + tt_ptr_op(c4->rendinfo, ==, NULL); + tt_ptr_op(NULL, ==, circuit_get_intro_point(tok3)); + + done: + circuit_free(TO_CIRCUIT(c1)); + circuit_free(TO_CIRCUIT(c2)); + circuit_free(TO_CIRCUIT(c3)); + circuit_free(TO_CIRCUIT(c4)); +} + struct testcase_t circuitlist_tests[] = { { "maps", test_clist_maps, TT_FORK, NULL, NULL }, + { "rend_token_maps", test_rend_token_maps, TT_FORK, NULL, NULL }, END_OF_TESTCASES }; |