[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[or-cvs] r12054: Implement code to compute which method to use to compute a c (in tor/trunk: . doc doc/spec src/or)
Author: nickm
Date: 2007-10-19 14:56:30 -0400 (Fri, 19 Oct 2007)
New Revision: 12054
Modified:
tor/trunk/
tor/trunk/ChangeLog
tor/trunk/doc/TODO
tor/trunk/doc/spec/dir-spec.txt
tor/trunk/src/or/dirvote.c
Log:
r15968@catbus: nickm | 2007-10-19 14:39:51 -0400
Implement code to compute which method to use to compute a consensus. Also, fix leak in consensus calculation.
Property changes on: tor/trunk
___________________________________________________________________
svk:merge ticket from /tor/trunk [r15968] on 8246c3cf-6607-4228-993b-4d95d33730f1
Modified: tor/trunk/ChangeLog
===================================================================
--- tor/trunk/ChangeLog 2007-10-19 18:56:28 UTC (rev 12053)
+++ tor/trunk/ChangeLog 2007-10-19 18:56:30 UTC (rev 12054)
@@ -9,6 +9,8 @@
- If the consensus list a router as "Unnamed", the name is assigned
to a different router: do not identify the router by that name.
(Partially implements proposal 122.)
+ - Authorities can now come to a consensus on which method to use to
+ compute the consensus. This gives us forward compatibility.
o Major bugfixes:
- Stop publishing a new server descriptor just because we HUP or
@@ -61,8 +63,8 @@
moria:9031."
- Distinguish between detached signatures for the wrong period, and
detached signatures for a divergent vote.
+ - Fix a small memory leak when computing a consensus.
-
o Minor bugfixes (v3 directory protocol)
- Delete unverified-consensus when the real consensus is set.
- Consider retrying a consensus networkstatus fetch immediately after one
Modified: tor/trunk/doc/TODO
===================================================================
--- tor/trunk/doc/TODO 2007-10-19 18:56:28 UTC (rev 12053)
+++ tor/trunk/doc/TODO 2007-10-19 18:56:30 UTC (rev 12054)
@@ -98,9 +98,10 @@
o Implement voting side
o Set Named and Unnamed sensibly
o Don't reject Unnamed routers.
- - Implement consensus side
- - Generic "pick which voting method to use" code.
- -
+ . Implement consensus side
+ o Generic "pick which voting method to use" code.
+ - When version 2 is set, set the Unnamed flag right.
+ - Mention that we support method 2.
o Implement client side
- Refactoring:
Modified: tor/trunk/doc/spec/dir-spec.txt
===================================================================
--- tor/trunk/doc/spec/dir-spec.txt 2007-10-19 18:56:28 UTC (rev 12053)
+++ tor/trunk/doc/spec/dir-spec.txt 2007-10-19 18:56:30 UTC (rev 12054)
@@ -1083,7 +1083,7 @@
Before generating a consensus, an authority must decide which consensus
method to use. To do this, it looks for the highest version number
- supported by more than 2/3 of the authorities. If it supports this
+ supported by more than 2/3 of the authorities voting. If it supports this
method, then it uses it. Otherwise, it falls back to method 1.
3.5. Detached signatures
Modified: tor/trunk/src/or/dirvote.c
===================================================================
--- tor/trunk/src/or/dirvote.c 2007-10-19 18:56:28 UTC (rev 12053)
+++ tor/trunk/src/or/dirvote.c 2007-10-19 18:56:30 UTC (rev 12054)
@@ -250,6 +250,63 @@
crypto_free_digest_env(d);
}
+/**DOCDOC*/
+static int
+_cmp_int_strings(const void **_a, const void **_b)
+{
+ const char *a = *_a, *b = *_b;
+ int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
+ int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
+ if (ai<bi)
+ return -1;
+ else if (ai==bi)
+ return 0;
+ else
+ return 1;
+}
+
+/**DOCDOC*/
+static int
+compute_consensus_method(smartlist_t *votes)
+{
+ smartlist_t *all_methods = smartlist_create();
+ smartlist_t *acceptable_methods = smartlist_create();
+ smartlist_t *tmp = smartlist_create();
+ int min = (smartlist_len(votes) * 2) / 3;
+ int n_ok;
+ int result;
+ SMARTLIST_FOREACH(votes, networkstatus_vote_t *, vote,
+ {
+ tor_assert(vote->supported_methods);
+ smartlist_add_all(tmp, vote->supported_methods);
+ smartlist_sort(tmp, _cmp_int_strings);
+ smartlist_uniq(tmp, _cmp_int_strings, NULL);
+ smartlist_add_all(all_methods, tmp);
+ smartlist_clear(tmp);
+ });
+
+ smartlist_sort(all_methods, _cmp_int_strings);
+ get_frequent_members(acceptable_methods, all_methods, min);
+ n_ok = smartlist_len(acceptable_methods);
+ if (n_ok) {
+ const char *best = smartlist_get(acceptable_methods, n_ok-1);
+ result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
+ } else {
+ result = 1;
+ }
+ smartlist_free(tmp);
+ smartlist_free(all_methods);
+ smartlist_free(acceptable_methods);
+ return result;
+}
+
+/**DOCDOC*/
+static int
+consensus_method_is_supported(int method)
+{
+ return (method == 1);
+}
+
/** Given a list of vote networkstatus_vote_t in <b>votes</b>, our public
* authority <b>identity_key</b>, our private authority <b>signing_key</b>,
* and the number of <b>total_authorities</b> that we believe exist in our
@@ -266,6 +323,7 @@
{
smartlist_t *chunks;
char *result = NULL;
+ int consensus_method;
time_t valid_after, fresh_until, valid_until;
int vote_seconds, dist_seconds;
@@ -279,6 +337,17 @@
}
flags = smartlist_create();
+ consensus_method = compute_consensus_method(votes);
+ if (consensus_method_is_supported(consensus_method)) {
+ log_info(LD_DIR, "Generating consensus using method %d.",
+ consensus_method);
+ } else {
+ log_warn(LD_DIR, "The other authorities will use consensus method %d, "
+ "which I don't support. Maybe I should upgrade!",
+ consensus_method);
+ consensus_method = 1;
+ }
+
/* Compute medians of time-related things, and figure out how many
* routers we might need to talk about. */
{
@@ -372,9 +441,16 @@
format_iso_time(vu_buf, valid_until);
flaglist = smartlist_join_strings(flags, " ", 0, NULL);
+ smartlist_add(chunks, tor_strdup("network-status-version 3\n"
+ "vote-status consensus\n"));
+
+ if (consensus_method >= 2) {
+ tor_snprintf(buf, sizeof(buf), "consensus-method %d\n",
+ consensus_method);
+ smartlist_add(chunks, tor_strdup(buf));
+ }
+
tor_snprintf(buf, sizeof(buf),
- "network-status-version 3\n"
- "vote-status consensus\n"
"valid-after %s\n"
"fresh-until %s\n"
"valid-until %s\n"
@@ -439,6 +515,7 @@
int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
* is the same flag as votes[j]->known_flags[b]. */
int *named_flag; /* Index of the flag "Named" for votes[j] */
+ int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
index = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
size = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
@@ -446,8 +523,9 @@
n_flag_voters = tor_malloc_zero(sizeof(int) * smartlist_len(flags));
flag_map = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
named_flag = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
+ unnamed_flag = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
for (i = 0; i < smartlist_len(votes); ++i)
- named_flag[i] = -1;
+ unnamed_flag[i] = named_flag[i] = -1;
SMARTLIST_FOREACH(votes, networkstatus_vote_t *, v,
{
flag_map[v_sl_idx] = tor_malloc_zero(
@@ -460,6 +538,8 @@
++n_flag_voters[p];
if (!strcmp(fl, "Named"))
named_flag[v_sl_idx] = fl_sl_idx;
+ if (!strcmp(fl, "Named"))
+ unnamed_flag[v_sl_idx] = fl_sl_idx;
});
n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
size[v_sl_idx] = smartlist_len(v->routerstatus_list);
@@ -598,6 +678,8 @@
tor_free(flag_map[i]);
tor_free(flag_map);
tor_free(flag_counts);
+ tor_free(named_flag);
+ tor_free(unnamed_flag);
smartlist_free(matching_descs);
smartlist_free(chosen_flags);
smartlist_free(versions);