Document dircollate.c (and remove an unused global)

2 files changed, 87 insertions, 7 deletions

diff --git a/src/or/dircollate.c b/src/or/dircollate.c
index f56aea8c64..eeb0c24008 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 cd1e8ac96d..d7f17ef757 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