dirvote.c 68.6 KB
Newer Older
1
2
/* Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3
 * Copyright (c) 2007-2008, The Tor Project, Inc. */
4
5
6
7
8
/* See LICENSE for licensing information */
/* $Id$ */
const char dirvote_c_id[] =
  "$Id$";

9
#define DIRVOTE_PRIVATE
10
11
12
13
#include "or.h"

/**
 * \file dirvote.c
14
 * \brief Functions to compute directory consensus, and schedule voting.
15
16
 **/

17
18
19
static int dirvote_add_signatures_to_pending_consensus(
                       const char *detached_signatures_body,
                       const char **msg_out);
20
static char *list_v3_auth_ids(void);
21
22
static void dirvote_fetch_missing_votes(void);
static void dirvote_fetch_missing_signatures(void);
23
static int dirvote_perform_vote(void);
24
25
26
static void dirvote_clear_votes(int all_votes);
static int dirvote_compute_consensus(void);
static int dirvote_publish_consensus(void);
27

28
/* =====
29
30
 * Voting
 * =====*/
31

Roger Dingledine's avatar
emo teh    
Roger Dingledine committed
32
/** Return a new string containing the string representation of the vote in
33
34
35
36
 * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
 * For v3 authorities. */
char *
format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
37
                          networkstatus_t *v3_ns)
38
{
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  size_t len;
  char *status = NULL;
  const char *client_versions = NULL, *server_versions = NULL;
  char *outp, *endp;
  char fingerprint[FINGERPRINT_LEN+1];
  char ipaddr[INET_NTOA_BUF_LEN];
  char digest[DIGEST_LEN];
  struct in_addr in;
  uint32_t addr;
  routerlist_t *rl = router_get_routerlist();
  char *version_lines = NULL;
  networkstatus_voter_info_t *voter;

  tor_assert(private_signing_key);

  voter = smartlist_get(v3_ns->voters, 0);

  addr = voter->addr;
  in.s_addr = htonl(addr);
  tor_inet_ntoa(&in, ipaddr, sizeof(ipaddr));

  base16_encode(fingerprint, sizeof(fingerprint),
                v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
  client_versions = v3_ns->client_versions;
  server_versions = v3_ns->server_versions;

  if (client_versions || server_versions) {
    size_t v_len = 64;
    char *cp;
    if (client_versions)
      v_len += strlen(client_versions);
70
    if (server_versions)
71
72
73
74
75
76
77
78
79
80
81
82
83
      v_len += strlen(server_versions);
    version_lines = tor_malloc(v_len);
    cp = version_lines;
    if (client_versions) {
      tor_snprintf(cp, v_len-(cp-version_lines),
                   "client-versions %s\n", client_versions);
      cp += strlen(cp);
    }
    if (server_versions)
      tor_snprintf(cp, v_len-(cp-version_lines),
                   "server-versions %s\n", server_versions);
  } else {
    version_lines = tor_strdup("");
84
  }
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

  len = 8192;
  len += strlen(version_lines);
  len += (RS_ENTRY_LEN)*smartlist_len(rl->routers);
  len += v3_ns->cert->cache_info.signed_descriptor_len;

  status = tor_malloc(len);
  {
    char published[ISO_TIME_LEN+1];
    char va[ISO_TIME_LEN+1];
    char fu[ISO_TIME_LEN+1];
    char vu[ISO_TIME_LEN+1];
    char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
    authority_cert_t *cert = v3_ns->cert;
    format_iso_time(published, v3_ns->published);
    format_iso_time(va, v3_ns->valid_after);
    format_iso_time(fu, v3_ns->fresh_until);
    format_iso_time(vu, v3_ns->valid_until);

    tor_assert(cert);
    tor_snprintf(status, len,
                 "network-status-version 3\n"
                 "vote-status vote\n"
108
                 "consensus-methods 1 2 3\n"
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
                 "published %s\n"
                 "valid-after %s\n"
                 "fresh-until %s\n"
                 "valid-until %s\n"
                 "voting-delay %d %d\n"
                 "%s" /* versions */
                 "known-flags %s\n"
                 "dir-source %s %s %s %s %d %d\n"
                 "contact %s\n",
                 published, va, fu, vu,
                 v3_ns->vote_seconds, v3_ns->dist_seconds,
                 version_lines,
                 flags,
                 voter->nickname, fingerprint, voter->address,
                   ipaddr, voter->dir_port, voter->or_port, voter->contact);

    tor_free(flags);
    outp = status + strlen(status);
    endp = status + len;
128
129
130
131
132
133
134
135

    if (!tor_digest_is_zero(voter->legacy_id_digest)) {
      char fpbuf[HEX_DIGEST_LEN+1];
      base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
      tor_snprintf(outp, endp-outp, "legacy-dir-key %s\n", fpbuf);
      outp += strlen(outp);
    }

136
137
138
139
140
    tor_assert(outp + cert->cache_info.signed_descriptor_len < endp);
    memcpy(outp, cert->cache_info.signed_descriptor_body,
           cert->cache_info.signed_descriptor_len);

    outp += cert->cache_info.signed_descriptor_len;
141
  }
142

143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
  SMARTLIST_FOREACH(v3_ns->routerstatus_list, vote_routerstatus_t *, vrs,
  {
    if (routerstatus_format_entry(outp, endp-outp, &vrs->status,
                                  vrs->version, 0) < 0) {
      log_warn(LD_BUG, "Unable to print router status.");
      goto err;
    }
    outp += strlen(outp);
  });

  {
    char signing_key_fingerprint[FINGERPRINT_LEN+1];
    if (tor_snprintf(outp, endp-outp, "directory-signature ")<0) {
      log_warn(LD_BUG, "Unable to start signature line.");
      goto err;
158
    }
159
    outp += strlen(outp);
160

161
162
163
164
165
166
167
168
169
170
171
    if (crypto_pk_get_fingerprint(private_signing_key,
                                  signing_key_fingerprint, 0)<0) {
      log_warn(LD_BUG, "Unable to get fingerprint for signing key");
      goto err;
    }
    if (tor_snprintf(outp, endp-outp, "%s %s\n", fingerprint,
                     signing_key_fingerprint)<0) {
      log_warn(LD_BUG, "Unable to end signature line.");
      goto err;
    }
    outp += strlen(outp);
172
173
  }

174
175
176
177
178
179
180
181
  if (router_get_networkstatus_v3_hash(status, digest)<0)
    goto err;
  note_crypto_pk_op(SIGN_DIR);
  if (router_append_dirobj_signature(outp,endp-outp,digest,
                                     private_signing_key)<0) {
    log_warn(LD_BUG, "Unable to sign networkstatus vote.");
    goto err;
  }
182

183
  {
184
    networkstatus_t *v;
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
    if (!(v = networkstatus_parse_vote_from_string(status, NULL, 1))) {
      log_err(LD_BUG,"Generated a networkstatus vote we couldn't parse: "
              "<<%s>>", status);
      goto err;
    }
    networkstatus_vote_free(v);
  }

  goto done;

 err:
  tor_free(status);
 done:
  tor_free(version_lines);
  return status;
200
201
}

202
203
204
205
/* =====
 * Consensus generation
 * ===== */

206
/** Given a vote <b>vote</b> (not a consensus!), return its associated
207
 * networkstatus_voter_info_t. */
208
static networkstatus_voter_info_t *
209
get_voter(const networkstatus_t *vote)
210
211
212
213
214
215
216
217
{
  tor_assert(vote);
  tor_assert(vote->is_vote);
  tor_assert(vote->voters);
  tor_assert(smartlist_len(vote->voters) == 1);
  return smartlist_get(vote->voters, 0);
}

218
219
220
221
222
223
typedef struct {
  networkstatus_t *v;
  const char *digest;
  int is_legacy;
} dir_src_ent_t;

224
/** Helper for sorting networkstatus_t votes (not consensuses) by the
225
 * hash of their voters' identity digests. */
226
227
228
static int
_compare_votes_by_authority_id(const void **_a, const void **_b)
{
229
  const networkstatus_t *a = *_a, *b = *_b;
230
231
  return memcmp(get_voter(a)->identity_digest,
                get_voter(b)->identity_digest, DIGEST_LEN);
232
233
}

234
235
236
237
238
239
240
241
242
243
244
245
246
static int
_compare_dir_src_ents_by_authority_id(const void **_a, const void **_b)
{
  const dir_src_ent_t *a = *_a, *b = *_b;
  const networkstatus_voter_info_t *a_v = get_voter(a->v),
    *b_v = get_voter(b->v);
  const char *a_id, *b_id;
  a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
  b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;

  return memcmp(a_id, b_id, DIGEST_LEN);
}

247
248
/** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
 * that occurs more than <b>min</b> times. */
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
static void
get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
{
  char *cur = NULL;
  int count = 0;
  SMARTLIST_FOREACH(in, char *, cp,
  {
    if (cur && !strcmp(cp, cur)) {
      ++count;
    } else {
      if (count > min)
        smartlist_add(out, cur);
      cur = cp;
      count = 1;
    }
  });
  if (count > min)
    smartlist_add(out, cur);
}

269
/** Given a sorted list of strings <b>lst</b>, return the member that appears
270
 * most.  Break ties in favor of later-occurring members. */
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
static const char *
get_most_frequent_member(smartlist_t *lst)
{
  const char *most_frequent = NULL;
  int most_frequent_count = 0;

  const char *cur = NULL;
  int count = 0;

  SMARTLIST_FOREACH(lst, const char *, s,
  {
    if (cur && !strcmp(s, cur)) {
      ++count;
    } else {
      if (count >= most_frequent_count) {
        most_frequent = cur;
        most_frequent_count = count;
      }
      cur = s;
      count = 1;
    }
  });
  if (count >= most_frequent_count) {
    most_frequent = cur;
    most_frequent_count = count;
  }
  return most_frequent;
}

300
301
302
/** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
 * that come from the same routerinfo, with the same derived elements.
 */
303
static int
304
compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
305
306
{
  int r;
307
308
309
  if ((r = memcmp(a->status.identity_digest, b->status.identity_digest,
                  DIGEST_LEN)))
    return r;
310
311
312
  if ((r = memcmp(a->status.descriptor_digest, b->status.descriptor_digest,
                  DIGEST_LEN)))
    return r;
313
  if ((r = (int)(b->status.published_on - a->status.published_on)))
314
    return r;
315
316
  if ((r = strcmp(b->status.nickname, a->status.nickname)))
    return r;
317
318
  if ((r = (((int)b->status.addr) - ((int)a->status.addr))))
    return r;
319
320
321
322
323
324
325
  if ((r = (((int)b->status.or_port) - ((int)a->status.or_port))))
    return r;
  if ((r = (((int)b->status.dir_port) - ((int)a->status.dir_port))))
    return r;
  return 0;
}

326
/** Helper for sorting routerlists based on compare_vote_rs. */
327
static int
328
_compare_vote_rs(const void **_a, const void **_b)
329
330
{
  const vote_routerstatus_t *a = *_a, *b = *_b;
331
  return compare_vote_rs(a,b);
332
333
}

334
335
336
337
/** Given a list of vote_routerstatus_t, all for the same router identity,
 * return whichever is most frequent, breaking ties in favor of more
 * recently published vote_routerstatus_t.
 */
338
339
340
341
342
343
344
static vote_routerstatus_t *
compute_routerstatus_consensus(smartlist_t *votes)
{
  vote_routerstatus_t *most = NULL, *cur = NULL;
  int most_n = 0, cur_n = 0;
  time_t most_published = 0;

345
  smartlist_sort(votes, _compare_vote_rs);
346
347
  SMARTLIST_FOREACH(votes, vote_routerstatus_t *, rs,
  {
348
    if (cur && !compare_vote_rs(cur, rs)) {
349
350
351
      ++cur_n;
    } else {
      if (cur_n > most_n ||
352
353
          (cur && cur_n == most_n &&
           cur->status.published_on > most_published)) {
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
        most = cur;
        most_n = cur_n;
        most_published = cur->status.published_on;
      }
      cur_n = 1;
      cur = rs;
    }
  });

  if (cur_n > most_n ||
      (cur && cur_n == most_n && cur->status.published_on > most_published)) {
    most = cur;
    most_n = cur_n;
    most_published = cur->status.published_on;
  }

  tor_assert(most);
  return most;
}

374
375
/** Given a list of strings in <b>lst</b>, set the DIGEST_LEN-byte digest at
 * <b>digest_out</b> to the hash of the concatenation of those strings. */
376
377
378
379
380
381
382
383
384
static void
hash_list_members(char *digest_out, smartlist_t *lst)
{
  crypto_digest_env_t *d = crypto_new_digest_env();
  SMARTLIST_FOREACH(lst, const char *, cp,
                    crypto_digest_add_bytes(d, cp, strlen(cp)));
  crypto_digest_get_digest(d, digest_out, DIGEST_LEN);
  crypto_free_digest_env(d);
}
385

386
387
388
/** Sorting helper: compare two strings based on their values as base-ten
 * positive integers. (Non-integers are treated as prior to all integers, and
 * compared lexically.) */
389
390
391
392
393
394
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);
395
  if (ai<bi) {
396
    return -1;
397
398
399
  } else if (ai==bi) {
    if (ai == 0) /* Parsing failed. */
      return strcmp(a, b);
400
    return 0;
401
  } else {
402
    return 1;
403
  }
404
405
}

406
407
/** Given a list of networkstatus_t votes, determine and return the number of
 * the highest consensus method that is supported by 2/3 of the voters. */
408
409
410
411
412
413
414
415
416
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;
417
  SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
  {
    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;
}

442
/** Return true iff <b>method</b> is a consensus method that we support. */
443
444
445
static int
consensus_method_is_supported(int method)
{
446
  return (method >= 1) && (method <= 3);
447
448
}

449
/** Given a list of vote networkstatus_t in <b>votes</b>, our public
450
451
452
 * 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
 * voting quorum, generate the text of a new v3 consensus vote, and return the
453
454
455
456
 * value in a newly allocated string.
 *
 * Note: this function DOES NOT check whether the votes are from
 * recognized authorities.   (dirvote_add_vote does that.) */
457
char *
458
networkstatus_compute_consensus(smartlist_t *votes,
459
                                int total_authorities,
460
461
                                crypto_pk_env_t *identity_key,
                                crypto_pk_env_t *signing_key)
462
463
{
  smartlist_t *chunks;
464
  char *result = NULL;
465
  int consensus_method;
466
467
468
469
470

  time_t valid_after, fresh_until, valid_until;
  int vote_seconds, dist_seconds;
  char *client_versions = NULL, *server_versions = NULL;
  smartlist_t *flags;
471
  tor_assert(total_authorities >= smartlist_len(votes));
472
473
474
475
476
477
478

  if (!smartlist_len(votes)) {
    log_warn(LD_DIR, "Can't compute a consensus from no votes.");
    return NULL;
  }
  flags = smartlist_create();

479
480
481
482
483
484
485
486
487
488
489
  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;
  }

490
491
492
  /* Compute medians of time-related things, and figure out how many
   * routers we might need to talk about. */
  {
493
494
495
496
497
498
    int n_votes = smartlist_len(votes);
    time_t *va_times = tor_malloc(n_votes * sizeof(time_t));
    time_t *fu_times = tor_malloc(n_votes * sizeof(time_t));
    time_t *vu_times = tor_malloc(n_votes * sizeof(time_t));
    int *votesec_list = tor_malloc(n_votes * sizeof(int));
    int *distsec_list = tor_malloc(n_votes * sizeof(int));
499
500
501
502
    int n_versioning_clients = 0, n_versioning_servers = 0;
    smartlist_t *combined_client_versions = smartlist_create();
    smartlist_t *combined_server_versions = smartlist_create();
    int j;
503
    SMARTLIST_FOREACH(votes, networkstatus_t *, v,
504
    {
505
      tor_assert(v->is_vote);
506
507
508
509
510
      va_times[v_sl_idx] = v->valid_after;
      fu_times[v_sl_idx] = v->fresh_until;
      vu_times[v_sl_idx] = v->valid_until;
      votesec_list[v_sl_idx] = v->vote_seconds;
      distsec_list[v_sl_idx] = v->dist_seconds;
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
      if (v->client_versions) {
        smartlist_t *cv = smartlist_create();
        ++n_versioning_clients;
        smartlist_split_string(cv, v->client_versions, ",",
                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
        sort_version_list(cv, 1);
        smartlist_add_all(combined_client_versions, cv);
        smartlist_free(cv); /* elements get freed later. */
      }
      if (v->server_versions) {
        smartlist_t *sv = smartlist_create();
        ++n_versioning_servers;
        smartlist_split_string(sv, v->server_versions, ",",
                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
        sort_version_list(sv, 1);
        smartlist_add_all(combined_server_versions, sv);
        smartlist_free(sv); /* elements get freed later. */
      }
529
530
      SMARTLIST_FOREACH(v->known_flags, const char *, cp,
                        smartlist_add(flags, tor_strdup(cp)));
531
    });
532
533
534
535
536
    valid_after = median_time(va_times, n_votes);
    fresh_until = median_time(fu_times, n_votes);
    valid_until = median_time(vu_times, n_votes);
    vote_seconds = median_int(votesec_list, n_votes);
    dist_seconds = median_int(distsec_list, n_votes);
537

538
539
540
541
542
    tor_assert(valid_after+MIN_VOTE_INTERVAL <= fresh_until);
    tor_assert(fresh_until+MIN_VOTE_INTERVAL <= valid_until);
    tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
    tor_assert(dist_seconds >= MIN_DIST_SECONDS);

543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
    for (j = 0; j < 2; ++j) {
      smartlist_t *lst =
        j ? combined_server_versions : combined_client_versions;
      int min = (j ? n_versioning_servers : n_versioning_clients) / 2;
      smartlist_t *good = smartlist_create();
      char *res;
      sort_version_list(lst, 0);
      get_frequent_members(good, lst, min);
      res = smartlist_join_strings(good, ",", 0, NULL);
      if (j)
        server_versions = res;
      else
        client_versions = res;
      SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
      smartlist_free(good);
      smartlist_free(lst);
    }

    smartlist_sort_strings(flags);
    smartlist_uniq_strings(flags);

564
565
566
567
568
    tor_free(va_times);
    tor_free(fu_times);
    tor_free(vu_times);
    tor_free(votesec_list);
    tor_free(distsec_list);
569
570
571
572
573
574
575
576
577
578
579
580
581
582
  }

  chunks = smartlist_create();

  {
    char buf[1024];
    char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
      vu_buf[ISO_TIME_LEN+1];
    char *flaglist;
    format_iso_time(va_buf, valid_after);
    format_iso_time(fu_buf, fresh_until);
    format_iso_time(vu_buf, valid_until);
    flaglist = smartlist_join_strings(flags, " ", 0, NULL);

583
584
585
586
587
588
589
590
591
    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));
    }

592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
    tor_snprintf(buf, sizeof(buf),
                 "valid-after %s\n"
                 "fresh-until %s\n"
                 "valid-until %s\n"
                 "voting-delay %d %d\n"
                 "client-versions %s\n"
                 "server-versions %s\n"
                 "known-flags %s\n",
                 va_buf, fu_buf, vu_buf,
                 vote_seconds, dist_seconds,
                 client_versions, server_versions, flaglist);
    smartlist_add(chunks, tor_strdup(buf));

    tor_free(flaglist);
  }

  /* Sort the votes. */
  smartlist_sort(votes, _compare_votes_by_authority_id);
  /* Add the authority sections. */
  {
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
    smartlist_t *dir_sources = smartlist_create();
    SMARTLIST_FOREACH(votes, networkstatus_t *, v,
    {
      dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
      e->v = v;
      e->digest = get_voter(v)->identity_digest;
      e->is_legacy = 0;
      smartlist_add(dir_sources, e);
      if (consensus_method >= 3 &&
          !tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
        dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
        e_legacy->v = v;
        e_legacy->digest = get_voter(v)->legacy_id_digest;
        e_legacy->is_legacy = 1;
        smartlist_add(dir_sources, e);
      }
    });
    smartlist_sort(dir_sources, _compare_dir_src_ents_by_authority_id);
630

631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
    SMARTLIST_FOREACH(dir_sources, const dir_src_ent_t *, e,
    {
      char buf[1024];
      struct in_addr in;
      char ip[INET_NTOA_BUF_LEN];
      char fingerprint[HEX_DIGEST_LEN+1];
      char votedigest[HEX_DIGEST_LEN+1];
      networkstatus_t *v = e->v;
      networkstatus_voter_info_t *voter = get_voter(v);

      if (e->is_legacy)
        tor_assert(consensus_method >= 2);

      in.s_addr = htonl(voter->addr);
      tor_inet_ntoa(&in, ip, sizeof(ip));
      base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
      base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
                    DIGEST_LEN);

      tor_snprintf(buf, sizeof(buf),
                   "dir-source %s%s %s %s %s %d %d\n",
                   voter->nickname, e->is_legacy ? "-legacy" : "",
                   fingerprint, voter->address, ip,
                   voter->dir_port,
                   voter->or_port);
      smartlist_add(chunks, tor_strdup(buf));
      if (! e->is_legacy) {
        tor_snprintf(buf, sizeof(buf),
                     "contact %s\n"
                     "vote-digest %s\n",
                     voter->contact,
                     votedigest);
        smartlist_add(chunks, tor_strdup(buf));
      }
    });
    SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
    smartlist_free(dir_sources);
  }
669
670
671

  /* Add the actual router entries. */
  {
672
673
674
675
    int *index; /* index[j] is the current index into votes[j]. */
    int *size; /* size[j] is the number of routerstatuses in votes[j]. */
    int *flag_counts; /* The number of voters that list flag[j] for the
                       * currently considered router. */
676
677
678
679
680
681
682
683
684
685
686
    int i;
    smartlist_t *matching_descs = smartlist_create();
    smartlist_t *chosen_flags = smartlist_create();
    smartlist_t *versions = smartlist_create();

    int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
                         * votes[j] knows about. */
    int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
                         * about flags[f]. */
    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]. */
687
    int *named_flag; /* Index of the flag "Named" for votes[j] */
688
    int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
689
690
691
692
693
694
695
    int chosen_named_idx, chosen_unnamed_idx;

    strmap_t *name_to_id_map = strmap_new();
    char conflict[DIGEST_LEN];
    char unknown[DIGEST_LEN];
    memset(conflict, 0, sizeof(conflict));
    memset(unknown, 0xff, sizeof(conflict));
696
697
698
699
700
701

    index = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
    size = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
    n_voter_flags = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    n_flag_voters = tor_malloc_zero(sizeof(int) * smartlist_len(flags));
    flag_map = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
702
703
    named_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    unnamed_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
704
    for (i = 0; i < smartlist_len(votes); ++i)
705
      unnamed_flag[i] = named_flag[i] = -1;
706
707
708
709
    chosen_named_idx = smartlist_string_pos(flags, "Named");
    chosen_unnamed_idx = smartlist_string_pos(flags, "Unnamed");

    /* Build the flag index. */
710
    SMARTLIST_FOREACH(votes, networkstatus_t *, v,
711
    {
712
713
      flag_map[v_sl_idx] = tor_malloc_zero(
                           sizeof(int)*smartlist_len(v->known_flags));
714
715
716
      SMARTLIST_FOREACH(v->known_flags, const char *, fl,
      {
        int p = smartlist_string_pos(flags, fl);
717
        tor_assert(p >= 0);
718
        flag_map[v_sl_idx][fl_sl_idx] = p;
719
        ++n_flag_voters[p];
720
721
        if (!strcmp(fl, "Named"))
          named_flag[v_sl_idx] = fl_sl_idx;
722
        if (!strcmp(fl, "Unnamed"))
723
          unnamed_flag[v_sl_idx] = fl_sl_idx;
724
725
      });
      n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
726
727
728
      size[v_sl_idx] = smartlist_len(v->routerstatus_list);
    });

729
730
    /* Named and Unnamed get treated specially */
    if (consensus_method >= 2) {
731
      SMARTLIST_FOREACH(votes, networkstatus_t *, v,
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
      {
        uint64_t nf;
        if (named_flag[v_sl_idx]<0)
          continue;
        nf = U64_LITERAL(1) << named_flag[v_sl_idx];
        SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
        {
          if ((rs->flags & nf) != 0) {
            const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
            if (!d) {
              /* We have no name officially mapped to this digest. */
              strmap_set_lc(name_to_id_map, rs->status.nickname,
                            rs->status.identity_digest);
            } else if (d != conflict &&
                memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
              /* Authorities disagree about this nickname. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
            } else {
              /* It's already a conflict, or it's already this ID. */
            }
          }
        });
      });
755
      SMARTLIST_FOREACH(votes, networkstatus_t *, v,
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
      {
        uint64_t uf;
        if (unnamed_flag[v_sl_idx]<0)
          continue;
        uf = U64_LITERAL(1) << unnamed_flag[v_sl_idx];
        SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
        {
          if ((rs->flags & uf) != 0) {
            const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
            if (d == conflict || d == unknown) {
              /* Leave it alone; we know what it is. */
            } else if (!d) {
              /* We have no name officially mapped to this digest. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
            } else if (!memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
              /* Authorities disagree about this nickname. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
            } else {
              /* It's mapped to a different name. */
            }
          }
        });
      });
    }

781
782
783
784
785
786
787
    /* Now go through all the votes */
    flag_counts = tor_malloc(sizeof(int) * smartlist_len(flags));
    while (1) {
      vote_routerstatus_t *rs;
      routerstatus_t rs_out;
      const char *lowest_id = NULL;
      const char *chosen_version;
788
      const char *chosen_name = NULL;
789
      int is_named = 0, is_unnamed = 0;
790
      int naming_conflict = 0;
791
792
793
794
      int n_listing = 0;
      int i;
      char buf[256];

795
      /* Of the next-to-be-considered digest in each voter, which is first? */
796
      SMARTLIST_FOREACH(votes, networkstatus_t *, v, {
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
        if (index[v_sl_idx] < size[v_sl_idx]) {
          rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
          if (!lowest_id ||
              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);
      smartlist_clear(versions);

      /* Okay, go through all the entries for this digest. */
813
      SMARTLIST_FOREACH(votes, networkstatus_t *, v, {
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
        if (index[v_sl_idx] >= size[v_sl_idx])
          continue; /* out of entries. */
        rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
        if (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 routersatus with
         * identity "lowest".
         */
        ++index[v_sl_idx];
        ++n_listing;

        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]];
        }
834
        if (rs->flags & (U64_LITERAL(1) << named_flag[v_sl_idx])) {
835
836
837
838
839
          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);
            naming_conflict = 1;
          }
840
841
          chosen_name = rs->status.nickname;
        }
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
      });

      /* We don't include this router at all unless more than half of
       * the authorities we believe in list it. */
      if (n_listing <= total_authorities/2)
        continue;

      /* Figure out the most popular opinion of what the most recent
       * routerinfo and its contents are. */
      rs = compute_routerstatus_consensus(matching_descs);
      /* Copy bits of that into rs_out. */
      tor_assert(!memcmp(lowest_id, rs->status.identity_digest, DIGEST_LEN));
      memcpy(rs_out.identity_digest, lowest_id, DIGEST_LEN);
      memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
             DIGEST_LEN);
857
      rs_out.addr = rs->status.addr;
858
859
860
861
      rs_out.published_on = rs->status.published_on;
      rs_out.dir_port = rs->status.dir_port;
      rs_out.or_port = rs->status.or_port;

862
863
864
865
866
867
      if (chosen_name && !naming_conflict) {
        strlcpy(rs_out.nickname, chosen_name, sizeof(rs_out.nickname));
      } else {
        strlcpy(rs_out.nickname, rs->status.nickname, sizeof(rs_out.nickname));
      }

868
869
870
871
872
873
874
875
876
877
878
879
880
881
      if (consensus_method == 1) {
        is_named = chosen_named_idx >= 0 &&
          (!naming_conflict && flag_counts[chosen_named_idx]);
      } else {
        const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname);
        if (!d) {
          is_named = is_unnamed = 0;
        } else if (!memcmp(d, lowest_id, DIGEST_LEN)) {
          is_named = 1; is_unnamed = 0;
        } else {
          is_named = 0; is_unnamed = 1;
        }
      }

882
883
884
885
      /* Set the flags. */
      smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */
      SMARTLIST_FOREACH(flags, const char *, fl,
      {
886
887
888
889
890
        if (!strcmp(fl, "Named")) {
          if (is_named)
            smartlist_add(chosen_flags, (char*)fl);
        } else if (!strcmp(fl, "Unnamed") && consensus_method >= 2) {
          if (is_unnamed)
891
892
            smartlist_add(chosen_flags, (char*)fl);
        } else {
893
894
          if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2)
            smartlist_add(chosen_flags, (char*)fl);
895
        }
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
      });

      /* Pick the version. */
      if (smartlist_len(versions)) {
        sort_version_list(versions, 0);
        chosen_version = get_most_frequent_member(versions);
      } else {
        chosen_version = NULL;
      }

      /* Okay!! Now we can write the descriptor... */
      /*     First line goes into "buf". */
      routerstatus_format_entry(buf, sizeof(buf), &rs_out, NULL, 1);
      smartlist_add(chunks, tor_strdup(buf));
      /*     Second line is all flags.  The "\n" is missing. */
      smartlist_add(chunks,
                    smartlist_join_strings(chosen_flags, " ", 0, NULL));
      /*     Now the version line. */
      if (chosen_version) {
915
916
        smartlist_add(chunks, tor_strdup("\nv "));
        smartlist_add(chunks, tor_strdup(chosen_version));
917
      }
918
      smartlist_add(chunks, tor_strdup("\n"));
919
920
921
922
923
924
925
926
927
928
929
930

      /* And the loop is over and we move on to the next router */
    }

    tor_free(index);
    tor_free(size);
    tor_free(n_voter_flags);
    tor_free(n_flag_voters);
    for (i = 0; i < smartlist_len(votes); ++i)
      tor_free(flag_map[i]);
    tor_free(flag_map);
    tor_free(flag_counts);
931
932
    tor_free(named_flag);
    tor_free(unnamed_flag);
933
    strmap_free(name_to_id_map, NULL);
934
935
936
937
938
939
    smartlist_free(matching_descs);
    smartlist_free(chosen_flags);
    smartlist_free(versions);
  }

  /* Add a signature. */
940
941
942
  {
    char digest[DIGEST_LEN];
    char fingerprint[HEX_DIGEST_LEN+1];
943
944
    char signing_key_fingerprint[HEX_DIGEST_LEN+1];

945
946
947
948
949
950
    char buf[4096];
    smartlist_add(chunks, tor_strdup("directory-signature "));

    /* Compute the hash of the chunks. */
    hash_list_members(digest, chunks);

951
    /* Get the fingerprints */
952
    crypto_pk_get_fingerprint(identity_key, fingerprint, 0);
953
    crypto_pk_get_fingerprint(signing_key, signing_key_fingerprint, 0);
954
955

    /* add the junk that will go at the end of the line. */
956
957
    tor_snprintf(buf, sizeof(buf), "%s %s\n", fingerprint,
                 signing_key_fingerprint);
958
    /* And the signature. */
959
960
961
962
963
    if (router_append_dirobj_signature(buf, sizeof(buf), digest,
                                       signing_key)) {
      log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
      return NULL; /* This leaks, but it should never happen. */
    }
964
    smartlist_add(chunks, tor_strdup(buf));
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980

    if (get_options()->V3AuthUseLegacyKey && consensus_method >= 3) {
      crypto_pk_env_t *legacy_key = get_my_v3_legacy_signing_key();
      authority_cert_t *legacy_cert = get_my_v3_legacy_cert();
      smartlist_add(chunks, tor_strdup("directory-signature "));
      crypto_pk_get_fingerprint(legacy_cert->identity_key, fingerprint, 0);
      crypto_pk_get_fingerprint(legacy_key, signing_key_fingerprint, 0);
      tor_snprintf(buf, sizeof(buf), "%s %s\n", fingerprint,
                   signing_key_fingerprint);
      if (router_append_dirobj_signature(buf, sizeof(buf), digest,
                                         signing_key)) {
        log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
        return NULL; /* This leaks, but it should never happen. */
      }
      smartlist_add(chunks, tor_strdup(buf));
    }
981
  }
982

983
  result = smartlist_join_strings(chunks, "", 0, NULL);
984
985
986

  tor_free(client_versions);
  tor_free(server_versions);
987
988
989
  smartlist_free(flags);
  SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  smartlist_free(chunks);
990

991
  {
992
    networkstatus_t *c;
993
    if (!(c = networkstatus_parse_vote_from_string(result, NULL, 0))) {
994
995
996
997
998
999
1000
      log_err(LD_BUG,"Generated a networkstatus consensus we couldn't "
              "parse.");
      tor_free(result);
      return NULL;
    }
    networkstatus_vote_free(c);
  }
For faster browsing, not all history is shown. View entire blame