diff options
Diffstat (limited to 'src/or/dircollate.c')
| -rw-r--r-- | src/or/dircollate.c | 327 |
1 files changed, 327 insertions, 0 deletions
diff --git a/src/or/dircollate.c b/src/or/dircollate.c new file mode 100644 index 0000000000..3f9d78f02d --- /dev/null +++ b/src/or/dircollate.c @@ -0,0 +1,327 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2016, 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" +#include "dirvote.h" + +static void dircollator_collate_by_rsa(dircollator_t *dc); +static void dircollator_collate_by_ed25519(dircollator_t *dc); + +/** Hashtable entry mapping a pair of digests (actually an ed25519 key and an + * RSA SHA1 digest) to an array of vote_routerstatus_t. */ +typedef struct ddmap_entry_s { + HT_ENTRY(ddmap_entry_s) node; + uint8_t d[DIGEST_LEN + DIGEST256_LEN]; + /* The nth member of this array corresponds to the vote_routerstatus_t (if + * any) received for this digest pair from the nth voter. */ + vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; +} ddmap_entry_t; + +/** Release all storage held by e. */ +static void +ddmap_entry_free(ddmap_entry_t *e) +{ + tor_free(e); +} + +/** Return a new empty ddmap_entry, with <b>n_votes</b> elements in + * vrs_list. */ +static ddmap_entry_t * +ddmap_entry_new(int n_votes) +{ + return tor_malloc_zero(STRUCT_OFFSET(ddmap_entry_t, vrs_lst) + + sizeof(vote_routerstatus_t *) * n_votes); +} + +static unsigned +ddmap_entry_hash(const ddmap_entry_t *ent) +{ + return (unsigned) siphash24g(ent->d, sizeof(ent->d)); +} + +static unsigned +ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b) +{ + return fast_memeq(a->d, b->d, sizeof(a->d)); +} + +/** Record the RSA identity of <b>ent</b> as <b>rsa_sha1</b>, and the + * ed25519 identity as <b>ed25519</b>. */ +static void +ddmap_entry_set_digests(ddmap_entry_t *ent, + const uint8_t *rsa_sha1, + const uint8_t *ed25519) +{ + memcpy(ent->d, rsa_sha1, DIGEST_LEN); + memcpy(ent->d + DIGEST_LEN, ed25519, DIGEST256_LEN); +} + +HT_PROTOTYPE(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, + ddmap_entry_eq); +HT_GENERATE2(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, + ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_); + +/** Helper: add a single vote_routerstatus_t <b>vrs</b> to the collator + * <b>dc</b>, indexing it by its RSA key digest, and by the 2-tuple of + * its RSA key digest and Ed25519 key. */ +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; + + vrs->ed25519_reflects_consensus = 0; + + (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; + + const uint8_t *ed = vrs->ed25519_id; + + if (! vrs->has_ed25519_listing) + return; + + ddmap_entry_t search, *found; + memset(&search, 0, sizeof(search)); + ddmap_entry_set_digests(&search, (const uint8_t *)id, ed); + found = HT_FIND(double_digest_map, &dc->by_both_ids, &search); + if (NULL == found) { + found = ddmap_entry_new(dc->n_votes); + ddmap_entry_set_digests(found, (const uint8_t *)id, ed); + HT_INSERT(double_digest_map, &dc->by_both_ids, found); + } + vrs_lst = found->vrs_lst; + tor_assert(vrs_lst[vote_num] == NULL); + vrs_lst[vote_num] = vrs; +} + +/** Create and return a new dircollator object to use when collating + * <b>n_votes</b> out of a total of <b>n_authorities</b>. */ +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(); + HT_INIT(double_digest_map, &dc->by_both_ids); + + return dc; +} + +/** Release all storage held by <b>dc</b>. */ +void +dircollator_free(dircollator_t *dc) +{ + if (!dc) + return; + + if (dc->by_collated_rsa_sha1 != dc->by_rsa_sha1) + digestmap_free(dc->by_collated_rsa_sha1, NULL); + + digestmap_free(dc->by_rsa_sha1, tor_free_); + smartlist_free(dc->all_rsa_sha1_lst); + + ddmap_entry_t **e, **next, *this; + for (e = HT_START(double_digest_map, &dc->by_both_ids); + e != NULL; e = next) { + this = *e; + next = HT_NEXT_RMV(double_digest_map, &dc->by_both_ids, e); + ddmap_entry_free(this); + } + HT_CLEAR(double_digest_map, &dc->by_both_ids); + + tor_free(dc); +} + +/** Add a single vote <b>v</b> to a dircollator <b>dc</b>. This function must + * be called exactly once for each vote to be used in the consensus. It may + * only be called before dircollator_collate(). + */ +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); +} + +/** Sort the entries in <b>dc</b> according to <b>consensus_method</b>, so + * that the consensus process can iterate over them with + * dircollator_n_routers() and dircollator_get_votes_for_router(). */ +void +dircollator_collate(dircollator_t *dc, int consensus_method) +{ + tor_assert(!dc->is_collated); + dc->all_rsa_sha1_lst = smartlist_new(); + + if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING) + dircollator_collate_by_rsa(dc); + else + dircollator_collate_by_ed25519(dc); + + smartlist_sort_digests(dc->all_rsa_sha1_lst); + dc->is_collated = 1; +} + +/** + * Collation function for RSA-only consensuses: collate the votes for each + * entry in <b>dc</b> by their RSA keys. + * + * The rule is: + * If an RSA identity key is listed by more than half of the authorities, + * include that identity, and treat all descriptors with that RSA identity + * as describing the same router. + */ +static void +dircollator_collate_by_rsa(dircollator_t *dc) +{ + 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; + + dc->by_collated_rsa_sha1 = dc->by_rsa_sha1; +} + +/** + * Collation function for ed25519 consensuses: collate the votes for each + * entry in <b>dc</b> by ed25519 key and by RSA key. + * + * The rule is, approximately: + * If a (ed,rsa) identity is listed by more than half of authorities, + * include it. And include all (rsa)-only votes about that node as + * matching. + * + * Otherwise, if an (*,rsa) or (rsa) identity is listed by more than + * half of the authorities, and no (ed,rsa) pair for the same RSA key + * has been already been included based on the rule above, include + * that RSA identity. + */ +static void +dircollator_collate_by_ed25519(dircollator_t *dc) +{ + const int total_authorities = dc->n_authorities; + digestmap_t *rsa_digests = digestmap_new(); + + ddmap_entry_t **iter; + + /* Go over all <ed,rsa> pairs */ + HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) { + ddmap_entry_t *ent = *iter; + int n = 0, i; + for (i = 0; i < dc->n_votes; ++i) { + if (ent->vrs_lst[i] != NULL) + ++n; + } + + /* If not enough authorties listed this exact <ed,rsa> pair, + * don't include it. */ + if (n <= total_authorities / 2) + continue; + + /* Now consider whether there are any other entries with the same + * RSA key (but with possibly different or missing ed value). */ + vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1, + (char*)ent->d); + tor_assert(vrs_lst2); + + for (i = 0; i < dc->n_votes; ++i) { + if (ent->vrs_lst[i] != NULL) { + ent->vrs_lst[i]->ed25519_reflects_consensus = 1; + } else if (vrs_lst2[i] && ! vrs_lst2[i]->has_ed25519_listing) { + ent->vrs_lst[i] = vrs_lst2[i]; + } + } + + /* Record that we have seen this RSA digest. */ + digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst); + smartlist_add(dc->all_rsa_sha1_lst, ent->d); + } + + /* Now look over all entries with an RSA digest, looking for RSA digests + * we didn't put in yet. + */ + DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { + if (digestmap_get(rsa_digests, k) != NULL) + continue; /* We already included this RSA digest */ + + int n = 0, i; + for (i = 0; i < dc->n_votes; ++i) { + if (vrs_lst[i] != NULL) + ++n; + } + + if (n <= total_authorities / 2) + continue; /* Not enough votes */ + + digestmap_set(rsa_digests, k, vrs_lst); + smartlist_add(dc->all_rsa_sha1_lst, (char *)k); + } DIGESTMAP_FOREACH_END; + + dc->by_collated_rsa_sha1 = rsa_digests; +} + +/** Return the total number of collated router entries. This function may + * only be called after dircollator_collate. */ +int +dircollator_n_routers(dircollator_t *dc) +{ + tor_assert(dc->is_collated); + return smartlist_len(dc->all_rsa_sha1_lst); +} + +/** Return an array of vote_routerstatus_t entries for the <b>idx</b>th router + * in the collation order. Each array contains n_votes elements, where the + * nth element of the array is the vote_routerstatus_t from the nth voter for + * this identity (or NULL if there is no such entry). + * + * The maximum value for <b>idx</b> is dircollator_n_routers(). + * + * This function may only be called after dircollator_collate. */ +vote_routerstatus_t ** +dircollator_get_votes_for_router(dircollator_t *dc, int idx) +{ + tor_assert(dc->is_collated); + tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst)); + return digestmap_get(dc->by_collated_rsa_sha1, + smartlist_get(dc->all_rsa_sha1_lst, idx)); +} + |