commit 6182e3462875d81dc3501bf0f1ad04fb658c2838 Author: Nick Mathewson <nickm@torproject.org> Date: Mon Feb 22 10:39:42 2016 -0500 Document dircollate.c (and remove an unused global) --- src/or/dircollate.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++--- src/or/dircollate.h | 24 +++++++++++++++--- 2 files changed, 87 insertions(+), 7 deletions(-) diff --git a/src/or/dircollate.c b/src/or/dircollate.c index f56aea8..eeb0c24 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -17,20 +17,24 @@ 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 i'th member of this array corresponds to the vote_routerstatus_t (if + * any) received for this digest pair from the n'th voter. */ vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; } ddmap_entry_t; -double_digest_map_t *by_both_ids; - +/** 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) { @@ -50,6 +54,8 @@ 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, @@ -63,6 +69,10 @@ 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, @@ -99,6 +109,8 @@ dircollator_add_routerstatus(dircollator_t *dc, 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) { @@ -115,6 +127,7 @@ dircollator_new(int n_votes, int n_authorities) return dc; } +/** Release all storage held by <b>dc</b>. */ void dircollator_free(dircollator_t *dc) { @@ -139,6 +152,10 @@ dircollator_free(dircollator_t *dc) 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) { @@ -153,6 +170,9 @@ dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) } 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) { @@ -168,6 +188,15 @@ dircollator_collate(dircollator_t *dc, int consensus_method) 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) { @@ -189,6 +218,20 @@ dircollator_collate_by_rsa(dircollator_t *dc) 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) { @@ -197,6 +240,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc) 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; @@ -205,9 +249,13 @@ dircollator_collate_by_ed25519(dircollator_t *dc) ++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); @@ -220,13 +268,17 @@ dircollator_collate_by_ed25519(dircollator_t *dc) } } + /* 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; + continue; /* We already included this RSA digest */ int n = 0, i; for (i = 0; i < dc->n_votes; ++i) { @@ -235,7 +287,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc) } if (n <= total_authorities / 2) - continue; + continue; /* Not enough votes */ digestmap_set(rsa_digests, k, vrs_lst); smartlist_add(dc->all_rsa_sha1_lst, (char *)k); @@ -244,12 +296,22 @@ dircollator_collate_by_ed25519(dircollator_t *dc) 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) { 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) { diff --git a/src/or/dircollate.h b/src/or/dircollate.h index cd1e8ac..d7f17ef 100644 --- a/src/or/dircollate.h +++ b/src/or/dircollate.h @@ -5,8 +5,8 @@ /* See LICENSE for licensing information */ /** - * \file dirvote.h - * \brief Header file for dirvote.c. + * \file dircollate.h + * \brief Header file for dircollate.c. **/ #ifndef TOR_DIRCOLLATE_H @@ -30,18 +30,36 @@ vote_routerstatus_t **dircollator_get_votes_for_router(dircollator_t *dc, #ifdef DIRCOLLATE_PRIVATE struct ddmap_entry_s; typedef HT_HEAD(double_digest_map, ddmap_entry_s) double_digest_map_t; +/** A dircollator keeps track of all the routerstatus entries in a + * set of networkstatus votes, and matches them by an appropriate rule. */ struct dircollator_s { - /**DOCDOC */ + /** True iff we have run the collation algorithm. */ int is_collated; + /** The total number of votes that we received. */ int n_votes; + /** The total number of authorities we acknowledge. */ int n_authorities; + /** The index which the next vote to be added to this collator should + * receive. */ int next_vote_num; + /** Map from RSA-SHA1 identity digest to an array of <b>n_votes</b> + * vote_routerstatus_t* pointers, such that the i'th member of the + * array is the i'th vote's entry for that RSA-SHA1 ID.*/ digestmap_t *by_rsa_sha1; + /** Map from <ed, RSA-SHA1> pair to an array similar to that used in + * by_rsa_sha1 above. We include <NULL,RSA-SHA1> entries for votes that + * say that there is no Ed key. */ struct double_digest_map by_both_ids; + /** One of two outputs created by collation: a map from RSA-SHA1 + * identity digest to an array of the vote_routerstatus_t objects. Entries + * only exist in this map for identities that we should include in the + * consensus. */ digestmap_t *by_collated_rsa_sha1; + /** One of two outputs created by collation: a sorted array of RSA-SHA1 + * identity digests .*/ smartlist_t *all_rsa_sha1_lst; }; #endif