commit 6c564e6c081514bab56bacec89b1f6f9457a7022 Author: Nick Mathewson <nickm@torproject.org> Date: Wed Nov 12 14:29:05 2014 -0500 Refactor code that matches up routers with the same identity in votes This makes 'routerstatus collation' into a first-class concept, so we can change how that works for prop220. --- src/or/dircollate.c | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/or/dircollate.h | 44 +++++++++++++++++++ src/or/dirvote.c | 98 ++++++++++++++--------------------------- src/or/include.am | 2 + 4 files changed, 200 insertions(+), 66 deletions(-) diff --git a/src/or/dircollate.c b/src/or/dircollate.c new file mode 100644 index 0000000..92f3dcc --- /dev/null +++ b/src/or/dircollate.c @@ -0,0 +1,122 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2014, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file dircollate.c + * + * \brief Collation code for figuring out which identities to vote for in + * the directory voting process. + */ + +#define DIRCOLLATE_PRIVATE +#include "dircollate.h" + +static void dircollator_collate_by_rsa(dircollator_t *dc); + +static void +dircollator_add_routerstatus(dircollator_t *dc, + int vote_num, + networkstatus_t *vote, + vote_routerstatus_t *vrs) +{ + const char *id = vrs->status.identity_digest; + + (void) vote; + vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id); + if (NULL == vrs_lst) { + vrs_lst = tor_calloc(sizeof(vote_routerstatus_t *), dc->n_votes); + digestmap_set(dc->by_rsa_sha1, id, vrs_lst); + } + + tor_assert(vrs_lst[vote_num] == NULL); + vrs_lst[vote_num] = vrs; +} + +dircollator_t * +dircollator_new(int n_votes, int n_authorities) +{ + dircollator_t *dc = tor_malloc_zero(sizeof(dircollator_t)); + + tor_assert(n_votes <= n_authorities); + + dc->n_votes = n_votes; + dc->n_authorities = n_authorities; + + dc->by_rsa_sha1 = digestmap_new(); + + return dc; +} + +void +dircollator_free(dircollator_t *dc) +{ + if (!dc) + return; + + digestmap_free(dc->by_rsa_sha1, tor_free_); + + tor_free(dc); +} + +void +dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) +{ + tor_assert(v->type == NS_TYPE_VOTE); + tor_assert(dc->next_vote_num < dc->n_votes); + tor_assert(!dc->is_collated); + + const int votenum = dc->next_vote_num++; + + SMARTLIST_FOREACH_BEGIN(v->routerstatus_list, vote_routerstatus_t *, vrs) { + dircollator_add_routerstatus(dc, votenum, v, vrs); + } SMARTLIST_FOREACH_END(vrs); +} + +void +dircollator_collate(dircollator_t *dc) +{ + dircollator_collate_by_rsa(dc); +} + +static void +dircollator_collate_by_rsa(dircollator_t *dc) +{ + tor_assert(!dc->is_collated); + + dc->all_rsa_sha1_lst = smartlist_new(); + + const int total_authorities = dc->n_authorities; + + DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { + int n = 0, i; + for (i = 0; i < dc->n_votes; ++i) { + if (vrs_lst[i] != NULL) + ++n; + } + + if (n <= total_authorities / 2) + continue; + + smartlist_add(dc->all_rsa_sha1_lst, (char *)k); + } DIGESTMAP_FOREACH_END; + + smartlist_sort_digests(dc->all_rsa_sha1_lst); + dc->is_collated = 1; +} + +int +dircollator_n_routers(dircollator_t *dc) +{ + return smartlist_len(dc->all_rsa_sha1_lst); +} + +vote_routerstatus_t ** +dircollator_get_votes_for_router(dircollator_t *dc, int idx) +{ + tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst)); + return digestmap_get(dc->by_rsa_sha1, + smartlist_get(dc->all_rsa_sha1_lst, idx)); +} + diff --git a/src/or/dircollate.h b/src/or/dircollate.h new file mode 100644 index 0000000..073b611 --- /dev/null +++ b/src/or/dircollate.h @@ -0,0 +1,44 @@ +/* Copyright (c) 2001 Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2014, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file dirvote.h + * \brief Header file for dirvote.c. + **/ + +#ifndef TOR_DIRCOLLATE_H +#define TOR_DIRCOLLATE_H + +#include "testsupport.h" +#include "or.h" + +typedef struct dircollator_s dircollator_t; + +dircollator_t *dircollator_new(int n_votes, int n_authorities); +void dircollator_free(dircollator_t *obj); +void dircollator_add_vote(dircollator_t *dc, networkstatus_t *v); + +void dircollator_collate(dircollator_t *dc); + +int dircollator_n_routers(dircollator_t *dc); +vote_routerstatus_t **dircollator_get_votes_for_router(dircollator_t *dc, + int idx); + +#ifdef DIRCOLLATE_PRIVATE +struct dircollator_s { + /**DOCDOC */ + int is_collated; + int n_votes; + int n_authorities; + + int next_vote_num; + digestmap_t *by_rsa_sha1; + + smartlist_t *all_rsa_sha1_lst; +}; +#endif + +#endif diff --git a/src/or/dirvote.c b/src/or/dirvote.c index 6c53b3c..6a70c13 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -6,6 +6,7 @@ #define DIRVOTE_PRIVATE #include "or.h" #include "config.h" +#include "dircollate.h" #include "directory.h" #include "dirserv.h" #include "dirvote.h" @@ -782,28 +783,6 @@ networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg, return berr; } -#if 0 -/** DOCDOC */ -static vote_identity_map_t * -networkstatus_compute_identity_mapping(const smartlist_t *votes) -{ - vote_identity_map_t *map = vote_identity_map_new(); - - SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, vote) { - SMARTLIST_FOREACH_BEGIN(vote->routerstatus_list, - vote_routerstatus_t *, vrs) { - vote_identity_map_add(map, vrs->status.identity_digest, - vrs->has_ed25519_listing ? vrs->ed25519_id : NULL, - vote_sl_idx); - } SMARTLIST_FOREACH_END(vrs); - } SMARTLIST_FOREACH_END(vote); - - vote_identity_map_resolve(map); - - return map; -} -#endif - /** * This function computes the bandwidth weights for consensus method 10. * @@ -1161,9 +1140,7 @@ networkstatus_compute_consensus(smartlist_t *votes, char *params = NULL; char *packages = NULL; int added_weights = 0; -#if 0 - vote_identity_map_t *id_map = NULL; -#endif + dircollator_t *collator = NULL; tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC); tor_assert(total_authorities >= smartlist_len(votes)); @@ -1519,16 +1496,24 @@ networkstatus_compute_consensus(smartlist_t *votes, } ); -#if 0 - id_map = networkstatus_compute_identity_mapping(votes); -#endif + /* Populate the collator */ + collator = dircollator_new(smartlist_len(votes), total_authorities); + SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) { + dircollator_add_vote(collator, v); + } SMARTLIST_FOREACH_END(v); + + dircollator_collate(collator); /* Now go through all the votes */ flag_counts = tor_calloc(smartlist_len(flags), sizeof(int)); - while (1) { + const int num_routers = dircollator_n_routers(collator); + for (i = 0; i < num_routers; ++i) { + vote_routerstatus_t **vrs_lst = + dircollator_get_votes_for_router(collator, i); + vote_routerstatus_t *rs; routerstatus_t rs_out; - const char *lowest_id = NULL; + const char *current_rsa_id = NULL; const char *chosen_version; const char *chosen_name = NULL; int exitsummary_disagreement = 0; @@ -1536,23 +1521,9 @@ networkstatus_compute_consensus(smartlist_t *votes, int is_guard = 0, is_exit = 0, is_bad_exit = 0; int naming_conflict = 0; int n_listing = 0; - int i; char microdesc_digest[DIGEST256_LEN]; tor_addr_port_t alt_orport = {TOR_ADDR_NULL, 0}; - /* Of the next-to-be-considered digest in each voter, which is first? */ - SMARTLIST_FOREACH(votes, networkstatus_t *, v, { - if (index[v_sl_idx] < size[v_sl_idx]) { - rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]); - if (!lowest_id || - fast_memcmp(rs->status.identity_digest, - lowest_id, DIGEST_LEN) < 0) - lowest_id = rs->status.identity_digest; - } - }); - if (!lowest_id) /* we're out of routers. */ - break; - memset(flag_counts, 0, sizeof(int)*smartlist_len(flags)); smartlist_clear(matching_descs); smartlist_clear(chosen_flags); @@ -1562,29 +1533,25 @@ networkstatus_compute_consensus(smartlist_t *votes, num_guardfraction_inputs = 0; /* Okay, go through all the entries for this digest. */ - SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) { - if (index[v_sl_idx] >= size[v_sl_idx]) - continue; /* out of entries. */ - rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]); - if (fast_memcmp(rs->status.identity_digest, lowest_id, DIGEST_LEN)) - continue; /* doesn't include this router. */ - /* At this point, we know that we're looking at a routerstatus with - * identity "lowest". - */ - ++index[v_sl_idx]; + for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) { + if (vrs_lst[voter_idx] == NULL) + continue; /* This voter had nothig to say about this entry. */ + rs = vrs_lst[voter_idx]; ++n_listing; + current_rsa_id = rs->status.identity_digest; + smartlist_add(matching_descs, rs); if (rs->version && rs->version[0]) smartlist_add(versions, rs->version); /* Tally up all the flags. */ - for (i = 0; i < n_voter_flags[v_sl_idx]; ++i) { - if (rs->flags & (U64_LITERAL(1) << i)) - ++flag_counts[flag_map[v_sl_idx][i]]; + for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) { + if (rs->flags & (U64_LITERAL(1) << flag)) + ++flag_counts[flag_map[voter_idx][flag]]; } - if (named_flag[v_sl_idx] >= 0 && - (rs->flags & (U64_LITERAL(1) << named_flag[v_sl_idx]))) { + if (named_flag[voter_idx] >= 0 && + (rs->flags & (U64_LITERAL(1) << named_flag[voter_idx]))) { if (chosen_name && strcmp(chosen_name, rs->status.nickname)) { log_notice(LD_DIR, "Conflict on naming for router: %s vs %s", chosen_name, rs->status.nickname); @@ -1605,7 +1572,7 @@ networkstatus_compute_consensus(smartlist_t *votes, if (rs->status.has_bandwidth) bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb; - } SMARTLIST_FOREACH_END(v); + } /* We don't include this router at all unless more than half of * the authorities we believe in list it. */ @@ -1619,8 +1586,9 @@ networkstatus_compute_consensus(smartlist_t *votes, microdesc_digest, &alt_orport); /* Copy bits of that into rs_out. */ memset(&rs_out, 0, sizeof(rs_out)); - tor_assert(fast_memeq(lowest_id, rs->status.identity_digest,DIGEST_LEN)); - memcpy(rs_out.identity_digest, lowest_id, DIGEST_LEN); + tor_assert(fast_memeq(current_rsa_id, + rs->status.identity_digest,DIGEST_LEN)); + memcpy(rs_out.identity_digest, current_rsa_id, DIGEST_LEN); memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest, DIGEST_LEN); rs_out.addr = rs->status.addr; @@ -1644,7 +1612,7 @@ networkstatus_compute_consensus(smartlist_t *votes, const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname); if (!d) { is_named = is_unnamed = 0; - } else if (fast_memeq(d, lowest_id, DIGEST_LEN)) { + } else if (fast_memeq(d, current_rsa_id, DIGEST_LEN)) { is_named = 1; is_unnamed = 0; } else { is_named = 0; is_unnamed = 1; @@ -2010,9 +1978,7 @@ networkstatus_compute_consensus(smartlist_t *votes, done: -#if 0 - vote_identity_map_free(id_map); -#endif + dircollator_free(collator); tor_free(client_versions); tor_free(server_versions); tor_free(packages); diff --git a/src/or/include.am b/src/or/include.am index 68f091b..9245ade 100644 --- a/src/or/include.am +++ b/src/or/include.am @@ -43,6 +43,7 @@ LIBTOR_A_SOURCES = \ src/or/connection_or.c \ src/or/control.c \ src/or/cpuworker.c \ + src/or/dircollate.c \ src/or/directory.c \ src/or/dirserv.c \ src/or/dirvote.c \ @@ -151,6 +152,7 @@ ORHEADERS = \ src/or/connection_or.h \ src/or/control.h \ src/or/cpuworker.h \ + src/or/dircollate.h \ src/or/directory.h \ src/or/dirserv.h \ src/or/dirvote.h \