routerlist.c 184 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Karsten Loesing's avatar
Karsten Loesing committed
4
 * Copyright (c) 2007-2009, The Tor Project, Inc. */
5
6
/* See LICENSE for licensing information */

Roger Dingledine's avatar
Roger Dingledine committed
7
8
/**
 * \file routerlist.c
9
 * \brief Code to
Nick Mathewson's avatar
Nick Mathewson committed
10
11
 * maintain and access the global list of routerinfos for known
 * servers.
Roger Dingledine's avatar
Roger Dingledine committed
12
 **/
Nick Mathewson's avatar
Nick Mathewson committed
13

14
15
#include "or.h"

16
17
// #define DEBUG_ROUTERLIST

18
19
/****************************************************************************/

20
/* static function prototypes */
21
22
static routerstatus_t *router_pick_directory_server_impl(
                                           authority_type_t auth, int flags);
23
static routerstatus_t *router_pick_trusteddirserver_impl(
24
                          authority_type_t auth, int flags, int *n_busy_out);
25
static void mark_all_trusteddirservers_up(void);
26
static int router_nickname_matches(routerinfo_t *router, const char *nickname);
27
static void trusted_dir_server_free(trusted_dir_server_t *ds);
28
29
30
static void launch_router_descriptor_downloads(smartlist_t *downloadable,
                                               time_t now);
static void update_consensus_router_descriptor_downloads(time_t now);
31
static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
32
static void update_router_have_minimum_dir_info(void);
33
34
static const char *signed_descriptor_get_body_impl(signed_descriptor_t *desc,
                                                   int with_annotations);
35
36
static void list_pending_downloads(digestmap_t *result,
                                   int purpose, const char *prefix);
37

38
39
40
DECLARE_TYPED_DIGESTMAP_FNS(sdmap_, digest_sd_map_t, signed_descriptor_t)
DECLARE_TYPED_DIGESTMAP_FNS(rimap_, digest_ri_map_t, routerinfo_t)
DECLARE_TYPED_DIGESTMAP_FNS(eimap_, digest_ei_map_t, extrainfo_t)
41
42
43
44
45
46
47
#define SDMAP_FOREACH(map, keyvar, valvar)                              \
  DIGESTMAP_FOREACH(sdmap_to_digestmap(map), keyvar, signed_descriptor_t *, \
                    valvar)
#define RIMAP_FOREACH(map, keyvar, valvar) \
  DIGESTMAP_FOREACH(rimap_to_digestmap(map), keyvar, routerinfo_t *, valvar)
#define EIMAP_FOREACH(map, keyvar, valvar) \
  DIGESTMAP_FOREACH(eimap_to_digestmap(map), keyvar, extrainfo_t *, valvar)
48

49
/****************************************************************************/
50

51
52
53
/** Global list of a trusted_dir_server_t object for each trusted directory
 * server. */
static smartlist_t *trusted_dir_servers = NULL;
54

55
56
/** List of for a given authority, and download status for latest certificate.
 */
57
58
59
60
61
62
63
64
typedef struct cert_list_t {
  download_status_t dl_status;
  smartlist_t *certs;
} cert_list_t;
/** Map from v3 identity key digest to cert_list_t. */
static digestmap_t *trusted_dir_certs = NULL;
/** True iff any key certificate in at least one member of
 * <b>trusted_dir_certs</b> has changed since we last flushed the
65
 * certificates to disk. */
66
static int trusted_dir_servers_certs_changed = 0;
Nick Mathewson's avatar
Nick Mathewson committed
67

68
/** Global list of all of the routers that we know about. */
Nick Mathewson's avatar
Nick Mathewson committed
69
static routerlist_t *routerlist = NULL;
70

71
72
73
/** List of strings for nicknames we've already warned about and that are
 * still unknown / unavailable. */
static smartlist_t *warned_nicknames = NULL;
74

75
76
77
/** The last time we tried to download any routerdesc, or 0 for "never".  We
 * use this to rate-limit download attempts when the number of routerdescs to
 * download is low. */
78
static time_t last_routerdesc_download_attempted = 0;
79

80
81
82
83
84
85
/** When we last computed the weights to use for bandwidths on directory
 * requests, what were the total weighted bandwidth, and our share of that
 * bandwidth?  Used to determine what fraction of directory requests we should
 * expect to see. */
static uint64_t sl_last_total_weighted_bw = 0,
  sl_last_weighted_bw_of_me = 0;
86

87
88
/** Return the number of directory authorities whose type matches some bit set
 * in <b>type</b>  */
89
int
90
get_n_authorities(authority_type_t type)
91
92
93
94
95
{
  int n = 0;
  if (!trusted_dir_servers)
    return 0;
  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
96
                    if (ds->type & type)
97
98
99
100
                      ++n);
  return n;
}

101
102
#define get_n_v2_authorities() get_n_authorities(V2_AUTHORITY)

103
104
/** Helper: Return the cert_list_t for an authority whose authority ID is
 * <b>id_digest</b>, allocating a new list if necessary. */
105
106
107
108
109
110
111
112
113
static cert_list_t *
get_cert_list(const char *id_digest)
{
  cert_list_t *cl;
  if (!trusted_dir_certs)
    trusted_dir_certs = digestmap_new();
  cl = digestmap_get(trusted_dir_certs, id_digest);
  if (!cl) {
    cl = tor_malloc_zero(sizeof(cert_list_t));
114
    cl->dl_status.schedule = DL_SCHED_CONSENSUS;
115
116
117
118
119
120
    cl->certs = smartlist_create();
    digestmap_set(trusted_dir_certs, id_digest, cl);
  }
  return cl;
}

121
122
/** Reload the cached v3 key certificates from the cached-certs file in
 * the data directory. Return 0 on success, -1 on failure. */
123
124
125
int
trusted_dirs_reload_certs(void)
{
126
  char *filename;
127
128
129
  char *contents;
  int r;

130
  filename = get_datadir_fname("cached-certs");
131
  contents = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
132
  tor_free(filename);
133
  if (!contents)
134
    return 0;
135
  r = trusted_dirs_load_certs_from_string(contents, 1, 1);
136
137
138
139
  tor_free(contents);
  return r;
}

140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/** Helper: return true iff we already have loaded the exact cert
 * <b>cert</b>. */
static INLINE int
already_have_cert(authority_cert_t *cert)
{
  cert_list_t *cl = get_cert_list(cert->cache_info.identity_digest);

  SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c,
  {
    if (!memcmp(c->cache_info.signed_descriptor_digest,
                cert->cache_info.signed_descriptor_digest,
                DIGEST_LEN))
      return 1;
  });
  return 0;
}

157
158
/** Load a bunch of new key certificates from the string <b>contents</b>.  If
 * <b>from_store</b> is true, the certificates are from the cache, and we
159
160
161
 * don't need to flush them to disk. If <b>flush</b> is true, we need
 * to flush any changed certificates to disk now.  Return 0 on success, -1
 * if any certs fail to parse. */
162
int
163
164
trusted_dirs_load_certs_from_string(const char *contents, int from_store,
                                    int flush)
165
166
167
{
  trusted_dir_server_t *ds;
  const char *s, *eos;
168
  int failure_code = 0;
169
170
171

  for (s = contents; *s; s = eos) {
    authority_cert_t *cert = authority_cert_parse_from_string(s, &eos);
172
    cert_list_t *cl;
173
174
    if (!cert) {
      failure_code = -1;
175
      break;
176
    }
177
178
    ds = trusteddirserver_get_by_v3_auth_digest(
                                       cert->cache_info.identity_digest);
179
180
    log_debug(LD_DIR, "Parsed certificate for %s",
              ds ? ds->nickname : "unknown authority");
181

182
183
184
185
186
187
    if (already_have_cert(cert)) {
      /* we already have this one. continue. */
      log_info(LD_DIR, "Skipping %s certificate for %s that we "
               "already have.",
               from_store ? "cached" : "downloaded",
               ds ? ds->nickname : "??");
188
189
190
191
192
193
194
195
196
197
198

      /* a duplicate on a download should be treated as a failure, since it
       * probably means we wanted a different secret key or we are trying to
       * replace an expired cert that has not in fact been updated. */
      if (!from_store) {
        log_warn(LD_DIR, "Got a certificate for %s that we already have. "
                 "Maybe they haven't updated it.  Waiting for a while.",
                 ds ? ds->nickname : "??");
        authority_cert_dl_failed(cert->cache_info.identity_digest, 404);
      }

199
      authority_cert_free(cert);
200
      continue;
201
    }
202

203
204
205
206
207
    if (ds) {
      log_info(LD_DIR, "Adding %s certificate for directory authority %s with "
               "signing key %s", from_store ? "cached" : "downloaded",
               ds->nickname, hex_str(cert->signing_key_digest,DIGEST_LEN));
    } else {
208
209
      int adding = directory_caches_dir_info(get_options());
      log_info(LD_DIR, "%s %s certificate for unrecognized directory "
210
               "authority with signing key %s",
211
               adding ? "Adding" : "Not adding",
212
213
               from_store ? "cached" : "downloaded",
               hex_str(cert->signing_key_digest,DIGEST_LEN));
214
215
216
217
      if (!adding) {
        authority_cert_free(cert);
        continue;
      }
218
    }
219

220
    cl = get_cert_list(cert->cache_info.identity_digest);
221
222
    smartlist_add(cl->certs, cert);
    if (ds && cert->cache_info.published_on > ds->addr_current_at) {
223
224
      /* Check to see whether we should update our view of the authority's
       * address. */
225
226
227
      if (cert->addr && cert->dir_port &&
          (ds->addr != cert->addr ||
           ds->dir_port != cert->dir_port)) {
228
        char *a = tor_dup_ip(cert->addr);
229
        log_notice(LD_DIR, "Updating address for directory authority %s "
230
                   "from %s:%d to %s:%d based on certificate.",
231
232
233
234
235
236
237
238
                   ds->nickname, ds->address, (int)ds->dir_port,
                   a, cert->dir_port);
        tor_free(a);
        ds->addr = cert->addr;
        ds->dir_port = cert->dir_port;
      }
      ds->addr_current_at = cert->cache_info.published_on;
    }
239

240
241
242
    if (!from_store)
      trusted_dir_servers_certs_changed = 1;
  }
243

244
245
  if (flush)
    trusted_dirs_flush_certs_to_disk();
246

247
248
  /* call this even if failure_code is <0, since some certs might have
   * succeeded. */
249
  networkstatus_note_certs_arrived();
250
251

  return failure_code;
252
253
}

254
/** Save all v3 key certificates to the cached-certs file. */
255
256
257
void
trusted_dirs_flush_certs_to_disk(void)
{
258
  char *filename;
259
260
  smartlist_t *chunks;

261
  if (!trusted_dir_servers_certs_changed || !trusted_dir_certs)
262
263
264
    return;

  chunks = smartlist_create();
265
266
  DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
    SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
267
268
269
270
271
272
          {
            sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
            c->bytes = cert->cache_info.signed_descriptor_body;
            c->len = cert->cache_info.signed_descriptor_len;
            smartlist_add(chunks, c);
          });
273
  } DIGESTMAP_FOREACH_END;
274

275
  filename = get_datadir_fname("cached-certs");
276
277
278
  if (write_chunks_to_file(filename, chunks, 0)) {
    log_warn(LD_FS, "Error writing certificates to disk.");
  }
279
  tor_free(filename);
280
281
282
283
284
285
  SMARTLIST_FOREACH(chunks, sized_chunk_t *, c, tor_free(c));
  smartlist_free(chunks);

  trusted_dir_servers_certs_changed = 0;
}

286
287
288
289
/** Remove all v3 authority certificates that have been superseded for more
 * than 48 hours.  (If the most recent cert was published more than 48 hours
 * ago, then we aren't going to get any consensuses signed with older
 * keys.) */
290
291
292
static void
trusted_dirs_remove_old_certs(void)
{
293
294
295
  time_t now = time(NULL);
#define DEAD_CERT_LIFETIME (2*24*60*60)
#define OLD_CERT_LIFETIME (7*24*60*60)
296
297
298
299
300
301
  if (!trusted_dir_certs)
    return;

  DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
    authority_cert_t *newest = NULL;
    SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
302
303
304
          if (!newest || (cert->cache_info.published_on >
                          newest->cache_info.published_on))
            newest = cert);
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
    if (newest) {
      const time_t newest_published = newest->cache_info.published_on;
      SMARTLIST_FOREACH_BEGIN(cl->certs, authority_cert_t *, cert) {
        int expired;
        time_t cert_published;
        if (newest == cert)
          continue;
        expired = ftime_definitely_after(now, cert->expires);
        cert_published = cert->cache_info.published_on;
        /* Store expired certs for 48 hours after a newer arrives;
         */
        if (expired ?
            (newest_published + DEAD_CERT_LIFETIME < now) :
            (cert_published + OLD_CERT_LIFETIME < newest_published)) {
          SMARTLIST_DEL_CURRENT(cl->certs, cert);
          authority_cert_free(cert);
          trusted_dir_servers_certs_changed = 1;
        }
      } SMARTLIST_FOREACH_END(cert);
    }
325
  } DIGESTMAP_FOREACH_END;
326
327
328
329
330
#undef OLD_CERT_LIFETIME

  trusted_dirs_flush_certs_to_disk();
}

331
332
333
/** Return the newest v3 authority certificate whose v3 authority identity key
 * has digest <b>id_digest</b>.  Return NULL if no such authority is known,
 * or it has no certificate. */
334
335
336
authority_cert_t *
authority_cert_get_newest_by_id(const char *id_digest)
{
337
  cert_list_t *cl;
338
  authority_cert_t *best = NULL;
339
340
  if (!trusted_dir_certs ||
      !(cl = digestmap_get(trusted_dir_certs, id_digest)))
341
    return NULL;
342

343
  SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
344
345
346
347
348
349
350
  {
    if (!best || cert->cache_info.published_on > best->cache_info.published_on)
      best = cert;
  });
  return best;
}

351
/** Return the newest v3 authority certificate whose directory signing key has
352
 * digest <b>sk_digest</b>. Return NULL if no such certificate is known.
353
 */
354
355
356
authority_cert_t *
authority_cert_get_by_sk_digest(const char *sk_digest)
{
357
  authority_cert_t *c;
358
  if (!trusted_dir_certs)
359
    return NULL;
360

361
362
363
364
365
366
367
  if ((c = get_my_v3_authority_cert()) &&
      !memcmp(c->signing_key_digest, sk_digest, DIGEST_LEN))
    return c;
  if ((c = get_my_v3_legacy_cert()) &&
      !memcmp(c->signing_key_digest, sk_digest, DIGEST_LEN))
    return c;

368
369
  DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
    SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
370
371
372
373
    {
      if (!memcmp(cert->signing_key_digest, sk_digest, DIGEST_LEN))
        return cert;
    });
374
  } DIGESTMAP_FOREACH_END;
375
376
377
  return NULL;
}

378
379
380
/** Return the v3 authority certificate with signing key matching
 * <b>sk_digest</b>, for the authority with identity digest <b>id_digest</b>.
 * Return NULL if no such authority is known. */
381
382
383
384
authority_cert_t *
authority_cert_get_by_digests(const char *id_digest,
                              const char *sk_digest)
{
385
  cert_list_t *cl;
386
387
  if (!trusted_dir_certs ||
      !(cl = digestmap_get(trusted_dir_certs, id_digest)))
388
    return NULL;
389
  SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
390
391
    if (!memcmp(cert->signing_key_digest, sk_digest, DIGEST_LEN))
      return cert; );
392

393
  return NULL;
394
395
}

396
/** Add every known authority_cert_t to <b>certs_out</b>. */
397
398
399
void
authority_cert_get_all(smartlist_t *certs_out)
{
400
  tor_assert(certs_out);
401
402
403
404
405
406
  if (!trusted_dir_certs)
    return;

  DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
    SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c,
                      smartlist_add(certs_out, c));
407
  } DIGESTMAP_FOREACH_END;
408
409
}

410
411
412
/** Called when an attempt to download a certificate with the authority with
 * ID <b>id_digest</b> fails with HTTP response code <b>status</b>: remember
 * the failure, so we don't try again immediately. */
413
414
415
416
void
authority_cert_dl_failed(const char *id_digest, int status)
{
  cert_list_t *cl;
417
418
  if (!trusted_dir_certs ||
      !(cl = digestmap_get(trusted_dir_certs, id_digest)))
419
420
421
422
423
    return;

  download_status_failed(&cl->dl_status, status);
}

424
425
426
/** How many times will we try to fetch a certificate before giving up? */
#define MAX_CERT_DL_FAILURES 8

427
428
429
430
431
432
/** Try to download any v3 authority certificates that we may be missing.  If
 * <b>status</b> is provided, try to get all the ones that were used to sign
 * <b>status</b>.  Additionally, try to have a non-expired certificate for
 * every V3 authority in trusted_dir_servers.  Don't fetch certificates we
 * already have.
 **/
433
void
434
authority_certs_fetch_missing(networkstatus_t *status, time_t now)
435
{
436
  digestmap_t *pending;
437
  authority_cert_t *cert;
438
  smartlist_t *missing_digests;
439
  char *resource = NULL;
440
441
  cert_list_t *cl;
  const int cache = directory_caches_dir_info(get_options());
442

443
444
445
  if (should_delay_dir_fetches(get_options()))
    return;

446
447
448
  pending = digestmap_new();
  missing_digests = smartlist_create();

449
  list_pending_downloads(pending, DIR_PURPOSE_FETCH_CERTIFICATE, "fp/");
450
  if (status) {
451
452
453
454
455
456
457
458
459
460
    SMARTLIST_FOREACH_BEGIN(status->voters, networkstatus_voter_info_t *,
                            voter) {
      if (!smartlist_len(voter->sigs))
        continue; /* This authority never signed this consensus, so don't
                   * go looking for a cert with key digest 0000000000. */
      if (!cache &&
          !trusteddirserver_get_by_v3_auth_digest(voter->identity_digest))
        continue; /* We are not a cache, and we don't know this authority.*/
      cl = get_cert_list(voter->identity_digest);
      SMARTLIST_FOREACH_BEGIN(voter->sigs, document_signature_t *, sig) {
461
        cert = authority_cert_get_by_digests(voter->identity_digest,
462
                                             sig->signing_key_digest);
463
464
465
        if (cert) {
          if (now < cert->expires)
            download_status_reset(&cl->dl_status);
466
467
          continue;
        }
468
        if (download_status_is_ready(&cl->dl_status, now,
469
470
                                     MAX_CERT_DL_FAILURES) &&
            !digestmap_get(pending, voter->identity_digest)) {
471
472
          log_notice(LD_DIR, "We're missing a certificate from authority "
                     "with signing key %s: launching request.",
473
474
                     hex_str(sig->signing_key_digest, DIGEST_LEN));
          smartlist_add(missing_digests, sig->identity_digest);
475
        }
476
477
      } SMARTLIST_FOREACH_END(sig);
    } SMARTLIST_FOREACH_END(voter);
478
  }
479
480
481
482
483
484
485
486
487
488
489
490
491
492
  SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, ds) {
    int found = 0;
    if (!(ds->type & V3_AUTHORITY))
      continue;
    if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest))
      continue;
    cl = get_cert_list(ds->v3_identity_digest);
    SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, {
      if (!ftime_definitely_after(now, cert->expires)) {
        /* It's not expired, and we weren't looking for something to
         * verify a consensus with.  Call it done. */
        download_status_reset(&cl->dl_status);
        found = 1;
        break;
493
      }
494
    });
495
496
497
498
499
500
501
502
    if (!found &&
        download_status_is_ready(&cl->dl_status, now,MAX_CERT_DL_FAILURES) &&
        !digestmap_get(pending, ds->v3_identity_digest)) {
      log_notice(LD_DIR, "No current certificate known for authority %s; "
                 "launching request.", ds->nickname);
        smartlist_add(missing_digests, ds->v3_identity_digest);
    }
  } SMARTLIST_FOREACH_END(ds);
503

504
505
506
  if (!smartlist_len(missing_digests)) {
    goto done;
  } else {
507
    smartlist_t *fps = smartlist_create();
508
    smartlist_add(fps, tor_strdup("fp/"));
509
    SMARTLIST_FOREACH(missing_digests, const char *, d, {
510
511
512
513
        char *fp;
        if (digestmap_get(pending, d))
          continue;
        fp = tor_malloc(HEX_DIGEST_LEN+2);
514
        base16_encode(fp, HEX_DIGEST_LEN+1, d, DIGEST_LEN);
515
516
        fp[HEX_DIGEST_LEN] = '+';
        fp[HEX_DIGEST_LEN+1] = '\0';
517
518
        smartlist_add(fps, fp);
      });
519
520
521
522
523
524
    if (smartlist_len(fps) == 1) {
      /* we didn't add any: they were all pending */
      SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
      smartlist_free(fps);
      goto done;
    }
525
526
    resource = smartlist_join_strings(fps, "", 0, NULL);
    resource[strlen(resource)-1] = '\0';
527
528
529
530
    SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
    smartlist_free(fps);
  }
  directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE, 0,
531
                               resource, PDS_RETRY_IF_NO_SERVERS);
532
533

 done:
534
  tor_free(resource);
535
  smartlist_free(missing_digests);
536
  digestmap_free(pending, NULL);
537
538
}

539
540
/* Router descriptor storage.
 *
541
 * Routerdescs are stored in a big file, named "cached-descriptors".  As new
542
 * routerdescs arrive, we append them to a journal file named
543
 * "cached-descriptors.new".
544
 *
545
546
547
 * From time to time, we replace "cached-descriptors" with a new file
 * containing only the live, non-superseded descriptors, and clear
 * cached-routers.new.
548
549
550
551
552
553
 *
 * On startup, we read both files.
 */

/** Helper: return 1 iff the router log is so big we want to rebuild the
 * store. */
554
static int
555
556
557
558
559
560
561
562
563
router_should_rebuild_store(desc_store_t *store)
{
  if (store->store_len > (1<<16))
    return (store->journal_len > store->store_len / 2 ||
            store->bytes_dropped > store->store_len / 2);
  else
    return store->journal_len > (1<<15);
}

564
565
/** Return the desc_store_t in <b>rl</b> that should be used to store
 * <b>sd</b>. */
566
567
static INLINE desc_store_t *
desc_get_store(routerlist_t *rl, signed_descriptor_t *sd)
568
{
569
570
  if (sd->is_extrainfo)
    return &rl->extrainfo_store;
571
  else
572
573
574
    return &rl->desc_store;
}

575
/** Add the signed_descriptor_t in <b>desc</b> to the router
Roger Dingledine's avatar
Roger Dingledine committed
576
 * journal; change its saved_location to SAVED_IN_JOURNAL and set its
577
 * offset appropriately. */
578
static int
579
signed_desc_append_to_journal(signed_descriptor_t *desc,
580
                              desc_store_t *store)
581
{
582
  char *fname = get_datadir_fname_suffix(store->fname_base, ".new");
583
584
  const char *body = signed_descriptor_get_body_impl(desc,1);
  size_t len = desc->signed_descriptor_len + desc->annotations_len;
585

586
  tor_assert(len == strlen(body));
587

588
  if (append_bytes_to_file(fname, body, len, 1)) {
589
    log_warn(LD_FS, "Unable to store router descriptor");
590
591
592
    tor_free(fname);
    return -1;
  }
593
  desc->saved_location = SAVED_IN_JOURNAL;
594
  tor_free(fname);
595

596
597
  desc->saved_offset = store->journal_len;
  store->journal_len += len;
598

599
600
601
  return 0;
}

602
603
/** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
 * signed_descriptor_t* in *<b>a</b> is older, the same age as, or newer than
Roger Dingledine's avatar
Roger Dingledine committed
604
 * the signed_descriptor_t* in *<b>b</b>. */
605
static int
606
_compare_signed_descriptors_by_age(const void **_a, const void **_b)
607
608
{
  const signed_descriptor_t *r1 = *_a, *r2 = *_b;
609
  return (int)(r1->published_on - r2->published_on);
610
611
}

612
613
614
#define RRS_FORCE 1
#define RRS_DONT_REMOVE_OLD 2

615
616
617
618
619
/** If the journal of <b>store</b> is too long, or if RRS_FORCE is set in
 * <b>flags</b>, then atomically replace the saved router store with the
 * routers currently in our routerlist, and clear the journal.  Unless
 * RRS_DONT_REMOVE_OLD is set in <b>flags</b>, delete expired routers before
 * rebuilding the store.  Return 0 on success, -1 on failure.
620
 */
621
static int
622
router_rebuild_store(int flags, desc_store_t *store)
623
624
{
  smartlist_t *chunk_list = NULL;
625
  char *fname = NULL, *fname_tmp = NULL;
626
  int r = -1;
627
  off_t offset = 0;
628
  smartlist_t *signed_descriptors = NULL;
629
  int nocache=0;
630
631
  size_t total_expected_len = 0;
  int had_any;
632
  int force = flags & RRS_FORCE;
633

634
635
636
637
638
639
640
641
  if (!force && !router_should_rebuild_store(store)) {
    r = 0;
    goto done;
  }
  if (!routerlist) {
    r = 0;
    goto done;
  }
642

643
644
645
646
647
  if (store->type == EXTRAINFO_STORE)
    had_any = !eimap_isempty(routerlist->extra_info_map);
  else
    had_any = (smartlist_len(routerlist->routers)+
               smartlist_len(routerlist->old_routers))>0;
648

649
  /* Don't save deadweight. */
650
651
  if (!(flags & RRS_DONT_REMOVE_OLD))
    routerlist_remove_old_routers();
652

653
  log_info(LD_DIR, "Rebuilding %s cache", store->description);
654

655
656
  fname = get_datadir_fname(store->fname_base);
  fname_tmp = get_datadir_fname_suffix(store->fname_base, ".tmp");
657

658
659
  chunk_list = smartlist_create();

660
  /* We sort the routers by age to enhance locality on disk. */
661
  signed_descriptors = smartlist_create();
662
  if (store->type == EXTRAINFO_STORE) {
663
664
665
666
    eimap_iter_t *iter;
    for (iter = eimap_iter_init(routerlist->extra_info_map);
         !eimap_iter_done(iter);
         iter = eimap_iter_next(routerlist->extra_info_map, iter)) {
667
668
      const char *key;
      extrainfo_t *ei;
669
      eimap_iter_get(iter, &key, &ei);
670
671
672
      smartlist_add(signed_descriptors, &ei->cache_info);
    }
  } else {
673
    SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
674
                      smartlist_add(signed_descriptors, sd));
675
    SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
676
                      smartlist_add(signed_descriptors, &ri->cache_info));
677
678
679
680
681
682
  }

  smartlist_sort(signed_descriptors, _compare_signed_descriptors_by_age);

  /* Now, add the appropriate members to chunk_list */
  SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
683
684
    {
      sized_chunk_t *c;
685
      const char *body = signed_descriptor_get_body_impl(sd, 1);
686
      if (!body) {
687
        log_warn(LD_BUG, "No descriptor available for router.");
688
689
        goto done;
      }
690
691
      if (sd->do_not_cache) {
        ++nocache;
692
        continue;
693
      }
694
      c = tor_malloc(sizeof(sized_chunk_t));
695
      c->bytes = body;
696
      c->len = sd->signed_descriptor_len + sd->annotations_len;
697
      total_expected_len += c->len;
698
699
      smartlist_add(chunk_list, c);
    });
700

701
  if (write_chunks_to_file(fname_tmp, chunk_list, 1)<0) {
702
    log_warn(LD_FS, "Error writing router store to disk.");
703
704
    goto done;
  }
705

706
  /* Our mmap is now invalid. */
707
708
709
  if (store->mmap) {
    tor_munmap_file(store->mmap);
    store->mmap = NULL;
710
  }
711

712
  if (replace_file(fname_tmp, fname)<0) {
713
    log_warn(LD_FS, "Error replacing old router store: %s", strerror(errno));
714
715
716
    goto done;
  }

717
  errno = 0;
718
  store->mmap = tor_mmap_file(fname);
719
  if (! store->mmap) {
720
721
722
723
724
725
    if (errno == ERANGE) {
      /* empty store.*/
      if (total_expected_len) {
        log_warn(LD_FS, "We wrote some bytes to a new descriptor file at '%s',"
                 " but when we went to mmap it, it was empty!", fname);
      } else if (had_any) {
726
727
728
        log_info(LD_FS, "We just removed every descriptor in '%s'.  This is "
                 "okay if we're just starting up after a long time. "
                 "Otherwise, it's a bug.", fname);
729
730
731
732
      }
    } else {
      log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
    }
733
  }
734

735
736
  log_info(LD_DIR, "Reconstructing pointers into cache");

737
  offset = 0;
738
  SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
739
    {
740
      if (sd->do_not_cache)
741
        continue;
742
      sd->saved_location = SAVED_IN_CACHE;
743
      if (store->mmap) {
744
        tor_free(sd->signed_descriptor_body); // sets it to null
Roger Dingledine's avatar
Roger Dingledine committed
745
        sd->saved_offset = offset;
746
      }
747
      offset += sd->signed_descriptor_len + sd->annotations_len;
748
      signed_descriptor_get_body(sd); /* reconstruct and assert */
749
    });
750

751
752
  tor_free(fname);
  fname = get_datadir_fname_suffix(store->fname_base, ".new");
753
  write_str_to_file(fname, "", 1);
754
755

  r = 0;
756
757
758
  store->store_len = (size_t) offset;
  store->journal_len = 0;
  store->bytes_dropped = 0;
759
 done:
760
761
  if (signed_descriptors)
    smartlist_free(signed_descriptors);
762
  tor_free(fname);
763
  tor_free(fname_tmp);
764
765
766
767
  if (chunk_list) {
    SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
    smartlist_free(chunk_list);
  }
768

769
770
771
  return r;
}

772
773
774
/** Helper: Reload a cache file and its associated journal, setting metadata
 * appropriately.  If <b>extrainfo</b> is true, reload the extrainfo store;
 * else reload the router descriptor store. */
775
static int
776
router_reload_router_list_impl(desc_store_t *store)
777
{
778
  char *fname = NULL, *altname = NULL, *contents = NULL;
779
  struct stat st;
780
  int read_from_old_location = 0;
781
  int extrainfo = (store->type == EXTRAINFO_STORE);
782
  time_t now = time(NULL);
783
  store->journal_len = store->store_len = 0;
784

785
786
787
  fname = get_datadir_fname(store->fname_base);
  if (store->fname_alt_base)
    altname = get_datadir_fname(store->fname_alt_base);
788

789
790
791
  if (store->mmap) /* get rid of it first */
    tor_munmap_file(store->mmap);
  store->mmap = NULL;
792

793
  store->mmap = tor_mmap_file(fname);
794
795
796
797
798
799
800
  if (!store->mmap && altname && file_status(altname) == FN_FILE) {
    read_from_old_location = 1;
    log_notice(LD_DIR, "Couldn't read %s; trying to load routers from old "
               "location %s.", fname, altname);
    if ((store->mmap = tor_mmap_file(altname)))
      read_from_old_location = 1;
  }
801
802
803
  if (altname && !read_from_old_location) {
    remove_file_if_very_old(altname, now);
  }
804
805
  if (store->mmap) {
    store->store_len = store->mmap->size;
806
    if (extrainfo)
807
808
      router_load_extrainfo_from_string(store->mmap->data,
                                        store->mmap->data+store->mmap->size,
809
                                        SAVED_IN_CACHE, NULL, 0);
810
    else
811
812
      router_load_routers_from_string(store->mmap->data,
                                      store->mmap->data+store->mmap->size,
813
                                      SAVED_IN_CACHE, NULL, 0, NULL);
814
  }
815

816
817
  tor_free(fname);
  fname = get_datadir_fname_suffix(store->fname_base, ".new");
818
  if (file_status(fname) == FN_FILE)
819
    contents = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
820
  if (read_from_old_location) {
821
822
    tor_free(altname);
    altname = get_datadir_fname_suffix(store->fname_alt_base, ".new");
823
824
825
826
    if (!contents)
      contents = read_file_to_str(altname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
    else
      remove_file_if_very_old(altname, now);
827
  }
828
  if (contents) {
829
    if (extrainfo)
830
831
      router_load_extrainfo_from_string(contents, NULL,SAVED_IN_JOURNAL,
                                        NULL, 0);
832
    else
833
      router_load_routers_from_string(contents, NULL, SAVED_IN_JOURNAL,
834
                                      NULL, 0, NULL);
835
    store->journal_len = (size_t) st.st_size;
836
    tor_free(contents);
837
838
  }

Nick Mathewson's avatar
Nick Mathewson committed
839
  tor_free(fname);
840
  tor_free(altname);
841

842
  if (store->journal_len || read_from_old_location) {
843
    /* Always clear the journal on startup.*/
844
    router_rebuild_store(RRS_FORCE, store);
845
  } else if (!extrainfo) {
846
847
848
    /* Don't cache expired routers. (This is in an else because
     * router_rebuild_store() also calls remove_old_routers().) */
    routerlist_remove_old_routers();
849
  }
850

851
852
853
  return 0;
}

854
855
856
857
858
859
/** Load all cached router descriptors and extra-info documents from the
 * store. Return 0 on success and -1 on failure.
 */
int
router_reload_router_list(void)
{
860
861
  routerlist_t *rl = router_get_routerlist();
  if (router_reload_router_list_impl(&rl->desc_store))
862
    return -1;
863
  if (router_reload_router_list_impl(&rl->extrainfo_store))
864
    return -1;
865
866
867
  return 0;
}

868
869
870
/** Return a smartlist containing a list of trusted_dir_server_t * for all
 * known trusted dirservers.  Callers must not modify the list or its
 * contents.
871
 */
872
873
smartlist_t *
router_get_trusted_dir_servers(void)
874
875
876
877
{
  if (!trusted_dir_servers)
    trusted_dir_servers = smartlist_create();

878
  return trusted_dir_servers;
879
880
}

881
/** Try to find a running dirserver that supports operations of <b>type</b>.
882
 *
883
884
885
886
887
888
889
890
 * If there are no running dirservers in our routerlist and the
 * <b>PDS_RETRY_IF_NO_SERVERS</b> flag is set, set all the authoritative ones
 * as running again, and pick one.
 *
 * If the <b>PDS_IGNORE_FASCISTFIREWALL</b> flag is set, then include
 * dirservers that we can't reach.
 *
 * If the <b>PDS_ALLOW_SELF</b> flag is not set, then don't include ourself
Roger Dingledine's avatar
Roger Dingledine committed
891
 * (if we're a dirserver).
892
893
894
 *
 * Don't pick an authority if any non-authority is viable; try to avoid using
 * servers that have returned 503 recently.
895
 */
896
routerstatus_t *
897
router_pick_directory_server(authority_type_t type, int flags)
898
{
899
  routerstatus_t *choice;
900
901
  if (get_options()->PreferTunneledDirConns)
    flags |= _PDS_PREFER_TUNNELED_DIR_CONNS;
902

903
  if (!routerlist)
904
    return NULL;
905

906
907
  choice = router_pick_directory_server_impl(type, flags);
  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
908
909
    return choice;

910
911
912
  log_info(LD_DIR,
           "No reachable router entries for dirservers. "
           "Trying them all again.");
913
  /* mark all authdirservers as up again */
914
  mark_all_trusteddirservers_up();
915
  /* try again */
916
  choice = router_pick_directory_server_impl(type, flags);
917
918
919
  return choice;
}

Nick Mathewson's avatar
Nick Mathewson committed
920
/** Try to determine which fraction of v2 and v3 directory requests aimed at