routerlist.c 139 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
3
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. */
4
5
/* See LICENSE for licensing information */
/* $Id$ */
6
7
const char routerlist_c_id[] =
  "$Id$";
8

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

16
17
#include "or.h"

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

20
/* static function prototypes */
21
22
23
24
static routerstatus_t *router_pick_directory_server_impl(int requireother,
                                                         int fascistfirewall,
                                                         int for_v2_directory);
static routerstatus_t *router_pick_trusteddirserver_impl(
25
                 authority_type_t type, int requireother, int fascistfirewall);
26
static void mark_all_trusteddirservers_up(void);
27
static int router_nickname_matches(routerinfo_t *router, const char *nickname);
28
static void routerstatus_list_update_from_networkstatus(time_t now);
29
static void local_routerstatus_free(local_routerstatus_t *rs);
30
31
32
static void trusted_dir_server_free(trusted_dir_server_t *ds);
static void update_networkstatus_cache_downloads(time_t now);
static void update_networkstatus_client_downloads(time_t now);
33
static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
34
static void routerlist_assert_ok(routerlist_t *rl);
35
static int have_tried_downloading_all_statuses(int n_failures);
36
37
static routerstatus_t *networkstatus_find_entry(networkstatus_t *ns,
                                                const char *digest);
38
39
40
static local_routerstatus_t *router_get_combined_status_by_nickname(
                                                const char *nickname,
                                                int warn_if_unnamed);
41
42
static void update_router_have_minimum_dir_info(void);
static void router_dir_info_changed(void);
43
44

/****************************************************************************/
45

46
47
48
/** Global list of a trusted_dir_server_t object for each trusted directory
 * server. */
static smartlist_t *trusted_dir_servers = NULL;
Nick Mathewson's avatar
Nick Mathewson committed
49

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

53
/** Global list of all of the current network_status documents that we know
54
 * about.  This list is kept sorted by published_on. */
55
static smartlist_t *networkstatus_list = NULL;
56

57
58
/** Global list of local_routerstatus_t for each router, known or unknown.
 * Kept sorted by digest. */
59
static smartlist_t *routerstatus_list = NULL;
60

61
62
63
/** Map from lowercase nickname to digest of named server, if any. */
static strmap_t *named_server_map = NULL;

64
65
/** True iff any member of networkstatus_list has changed since the last time
 * we called routerstatus_list_update_from_networkstatus(). */
66
static int networkstatus_list_has_changed = 0;
67

68
69
/** True iff any element of routerstatus_list has changed since the last
 * time we called routers_update_all_from_networkstatus().*/
70
static int routerstatus_list_has_changed = 0;
71

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

76
77
78
/** List of strings for nicknames or fingerprints we've already warned about
 * and that are still conflicted. */
static smartlist_t *warned_conflicts = NULL;
79

80
81
82
/** 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. */
83
static time_t last_routerdesc_download_attempted = 0;
84

85
86
87
/** The last time we tried to download a networkstatus, or 0 for "never".  We
 * use this to rate-limit download attempts for directory caches (including
 * mirrors).  Clients don't use this now. */
88
89
static time_t last_networkstatus_download_attempted = 0;

90
/** True iff we have logged a warning about this OR not being valid or
91
 * not being named. */
92
static int have_warned_about_invalid_status = 0;
93
94
/** True iff we have logged a warning about this OR's version being older than
 * listed by the authorities  */
95
static int have_warned_about_old_version = 0;
96
97
/** True iff we have logged a warning about this OR's version being newer than
 * listed by the authorities  */
98
99
static int have_warned_about_new_version = 0;

100
101
102
103
104
105
106
107
108
109
110
111
112
/** Return the number of v2 directory authorities */
static INLINE int
get_n_v2_authorities(void)
{
  int n = 0;
  if (!trusted_dir_servers)
    return 0;
  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
                    if (ds->is_v2_authority)
                      ++n);
  return n;
}

113
114
/** Repopulate our list of network_status_t objects from the list cached on
 * disk.  Return 0 on success, -1 on failure. */
115
116
117
118
119
int
router_reload_networkstatus(void)
{
  char filename[512];
  struct stat st;
120
  smartlist_t *entries;
121
122
123
124
125
126
127
128
129
  char *s;
  tor_assert(get_options()->DataDirectory);
  if (!networkstatus_list)
    networkstatus_list = smartlist_create();

  tor_snprintf(filename,sizeof(filename),"%s/cached-status",
               get_options()->DataDirectory);
  entries = tor_listdir(filename);
  SMARTLIST_FOREACH(entries, const char *, fn, {
130
131
132
      char buf[DIGEST_LEN];
      if (strlen(fn) != HEX_DIGEST_LEN ||
          base16_decode(buf, sizeof(buf), fn, strlen(fn))) {
133
134
        log_info(LD_DIR,
                 "Skipping cached-status file with unexpected name \"%s\"",fn);
135
136
        continue;
      }
137
138
139
140
141
      tor_snprintf(filename,sizeof(filename),"%s/cached-status/%s",
                   get_options()->DataDirectory, fn);
      s = read_file_to_str(filename, 0);
      if (s) {
        stat(filename, &st);
142
        if (router_set_networkstatus(s, st.st_mtime, NS_FROM_CACHE, NULL)<0) {
143
          log_warn(LD_FS, "Couldn't load networkstatus from \"%s\"",filename);
144
145
        }
        tor_free(s);
146
147
      }
    });
148
149
  SMARTLIST_FOREACH(entries, char *, fn, tor_free(fn));
  smartlist_free(entries);
150
  networkstatus_list_clean(time(NULL));
151
  routers_update_all_from_networkstatus();
152
153
154
  return 0;
}

155
156
157
158
/* Router descriptor storage.
 *
 * Routerdescs are stored in a big file, named "cached-routers".  As new
 * routerdescs arrive, we append them to a journal file named
159
 * "cached-routers.new".
160
161
 *
 * From time to time, we replace "cached-routers" with a new file containing
162
 * only the live, non-superseded descriptors, and clear cached-routers.new.
163
164
165
166
167
168
169
 *
 * On startup, we read both files.
 */

/** The size of the router log, in bytes. */
static size_t router_journal_len = 0;
/** The size of the router store, in bytes. */
170
static size_t router_store_len = 0;
171
172
/** Total bytes dropped since last rebuild. */
static size_t router_bytes_dropped = 0;
173

174
175
/** Helper: return 1 iff the router log is so big we want to rebuild the
 * store. */
176
177
178
179
static int
router_should_rebuild_store(void)
{
  if (router_store_len > (1<<16))
180
181
    return (router_journal_len > router_store_len / 2 ||
            router_bytes_dropped > router_store_len / 2);
182
  else
183
    return router_journal_len > (1<<15);
184
185
}

186
187
/** Add the <b>len</b>-type router descriptor in <b>s</b> to the router
 * journal. */
188
static int
189
router_append_to_journal(signed_descriptor_t *desc)
190
191
192
{
  or_options_t *options = get_options();
  size_t fname_len = strlen(options->DataDirectory)+32;
193
194
195
  char *fname = tor_malloc(fname_len);
  const char *body = signed_descriptor_get_body(desc);
  size_t len = desc->signed_descriptor_len;
196

197
  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
198
199
               options->DataDirectory);

200
  tor_assert(len == strlen(body));
201

202
  if (append_bytes_to_file(fname, body, len, 1)) {
203
    log_warn(LD_FS, "Unable to store router descriptor");
204
205
206
    tor_free(fname);
    return -1;
  }
207
208
  desc->saved_location = SAVED_IN_JOURNAL;
  desc->saved_offset = router_journal_len;
209
210

  tor_free(fname);
211
  router_journal_len += len;
212
213
214
  return 0;
}

215
216
217
218
219
220
221
222
223
224
225
226
227
228
static int
_compare_old_routers_by_age(const void **_a, const void **_b)
{
  const signed_descriptor_t *r1 = *_a, *r2 = *_b;
  return r1->published_on - r2->published_on;
}

static int
_compare_routers_by_age(const void **_a, const void **_b)
{
  const routerinfo_t *r1 = *_a, *r2 = *_b;
  return r1->cache_info.published_on - r2->cache_info.published_on;
}

229
230
231
232
/** If the journal is too long, or if <b>force</b> is true, then atomically
 * replace the router store with the routers currently in our routerlist, and
 * clear the journal.  Return 0 on success, -1 on failure.
 */
233
static int
234
235
236
237
238
239
240
router_rebuild_store(int force)
{
  size_t len = 0;
  or_options_t *options;
  size_t fname_len;
  smartlist_t *chunk_list = NULL;
  char *fname = NULL;
241
  int r = -1, i;
242
  off_t offset = 0;
243
  smartlist_t *old_routers, *routers;
244
245
246
247
248
249

  if (!force && !router_should_rebuild_store())
    return 0;
  if (!routerlist)
    return 0;

250
  /* Don't save deadweight. */
251
  routerlist_remove_old_routers();
252

253
254
  log_info(LD_DIR, "Rebuilding router descriptor cache");

255
256
257
258
259
260
  options = get_options();
  fname_len = strlen(options->DataDirectory)+32;
  fname = tor_malloc(fname_len);
  tor_snprintf(fname, fname_len, "%s/cached-routers", options->DataDirectory);
  chunk_list = smartlist_create();

261
262
263
264
265
266
  old_routers = smartlist_create();
  smartlist_add_all(old_routers, routerlist->old_routers);
  smartlist_sort(old_routers, _compare_old_routers_by_age);
  routers = smartlist_create();
  smartlist_add_all(routers, routerlist->routers);
  smartlist_sort(routers, _compare_routers_by_age);
267
  for (i = 0; i < 2; ++i) {
268
269
    smartlist_t *lst = smartlist_create();
    /* We sort the routers by age to enhance locality on disk. */
270
271
272
273
    if (i==0)
      lst = old_routers;
    else
      lst = routers;
274
    /* Now, add the appropriate members to chunk_list */
275
    SMARTLIST_FOREACH(lst, void *, ptr,
276
    {
277
278
      signed_descriptor_t *sd = (i==0) ?
        ((signed_descriptor_t*)ptr): &((routerinfo_t*)ptr)->cache_info;
279
      sized_chunk_t *c;
280
281
      const char *body = signed_descriptor_get_body(sd);
      if (!body) {
282
        log_warn(LD_BUG, "Bug! No descriptor available for router.");
283
        smartlist_free(lst);
284
285
286
        goto done;
      }
      c = tor_malloc(sizeof(sized_chunk_t));
287
      c->bytes = body;
288
      c->len = sd->signed_descriptor_len;
289
290
291
      smartlist_add(chunk_list, c);
    });
  }
292
  if (write_chunks_to_file(fname, chunk_list, 1)<0) {
293
    log_warn(LD_FS, "Error writing router store to disk.");
294
295
    goto done;
  }
296
  /* Our mmap is now invalid. */
297
298
299
300
  if (routerlist->mmap_descriptors) {
    tor_munmap_file(routerlist->mmap_descriptors);
    routerlist->mmap_descriptors = tor_mmap_file(fname);
    if (! routerlist->mmap_descriptors)
301
302
303
      log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
  }

304
  offset = 0;
305
  for (i = 0; i < 2; ++i) {
306
    smartlist_t *lst = (i == 0) ? old_routers : routers;
307
308
309
310
311
312
    SMARTLIST_FOREACH(lst, void *, ptr,
    {
      signed_descriptor_t *sd = (i==0) ?
        ((signed_descriptor_t*)ptr): &((routerinfo_t*)ptr)->cache_info;

      sd->saved_location = SAVED_IN_CACHE;
313
314
      if (routerlist->mmap_descriptors) {
        tor_free(sd->signed_descriptor_body); // sets it to null
Roger Dingledine's avatar
Roger Dingledine committed
315
        sd->saved_offset = offset;
316
      }
317
      offset += sd->signed_descriptor_len;
318
      signed_descriptor_get_body(sd);
319
320
    });
  }
321
322
  smartlist_free(old_routers);
  smartlist_free(routers);
323

324
  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
325
326
               options->DataDirectory);

327
  write_str_to_file(fname, "", 1);
328
329
330

  r = 0;
  router_store_len = len;
331
  router_journal_len = 0;
332
  router_bytes_dropped = 0;
333
334
335
336
337
338
339
340
341
 done:
  tor_free(fname);
  if (chunk_list) {
    SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
    smartlist_free(chunk_list);
  }
  return r;
}

342
343
344
/* Load all cached router descriptors from the store. Return 0 on success and
 * -1 on failure.
 */
345
346
347
348
349
int
router_reload_router_list(void)
{
  or_options_t *options = get_options();
  size_t fname_len = strlen(options->DataDirectory)+32;
350
  char *fname = tor_malloc(fname_len), *contents;
351
352
  struct stat st;

353
  if (!routerlist)
354
    router_get_routerlist(); /* mallocs and inits it in place */
355
356
357

  router_journal_len = router_store_len = 0;

358
  tor_snprintf(fname, fname_len, "%s/cached-routers", options->DataDirectory);
359
360
361
362

  if (routerlist->mmap_descriptors) /* get rid of it first */
    tor_munmap_file(routerlist->mmap_descriptors);

363
  routerlist->mmap_descriptors = tor_mmap_file(fname);
364
  if (routerlist->mmap_descriptors) {
365
366
    router_store_len = routerlist->mmap_descriptors->size;
    router_load_routers_from_string(routerlist->mmap_descriptors->data,
367
                                    SAVED_IN_CACHE, NULL);
368
  }
369
370
371

  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
               options->DataDirectory);
372
  contents = read_file_to_str(fname, 1);
373
374
375
376
  if (contents) {
    stat(fname, &st);
    router_load_routers_from_string(contents,
                                    SAVED_IN_JOURNAL, NULL);
377
    tor_free(contents);
378
379
  }

Nick Mathewson's avatar
Nick Mathewson committed
380
  tor_free(fname);
381
382
383
384

  if (router_journal_len) {
    /* Always clear the journal on startup.*/
    router_rebuild_store(1);
385
386
387
388
  } else {
    /* Don't cache expired routers. (This is in an else because
     * router_rebuild_store() also calls remove_old_routers().) */
    routerlist_remove_old_routers();
389
  }
390

391
392
393
  return 0;
}

394
395
396
/** 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.
397
 */
398
399
smartlist_t *
router_get_trusted_dir_servers(void)
400
401
402
403
{
  if (!trusted_dir_servers)
    trusted_dir_servers = smartlist_create();

404
  return trusted_dir_servers;
405
406
}

407
/** Try to find a running dirserver. If there are no running dirservers
408
409
410
411
 * in our routerlist and <b>retry_if_no_servers</b> is non-zero,
 * set all the authoritative ones as running again, and pick one;
 * if there are then no dirservers at all in our routerlist,
 * reload the routerlist and try one last time. If for_runningrouters is
412
413
 * true, then only pick a dirserver that can answer runningrouters queries
 * (that is, a trusted dirserver, or one running 0.0.9rc5-cvs or later).
414
 * Don't pick an authority if any non-authority is viable.
415
 * Other args are as in router_pick_directory_server_impl().
416
 */
417
routerstatus_t *
418
router_pick_directory_server(int requireother,
419
                             int fascistfirewall,
420
                             int for_v2_directory,
421
422
                             int retry_if_no_servers)
{
423
  routerstatus_t *choice;
424

425
  if (!routerlist)
426
    return NULL;
427

428
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
429
                                             for_v2_directory);
430
  if (choice || !retry_if_no_servers)
431
432
    return choice;

433
434
435
  log_info(LD_DIR,
           "No reachable router entries for dirservers. "
           "Trying them all again.");
436
  /* mark all authdirservers as up again */
437
  mark_all_trusteddirservers_up();
438
  /* try again */
439
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
440
                                             for_v2_directory);
441
  if (choice)
442
443
    return choice;

444
445
  log_info(LD_DIR,"Still no %s router entries. Reloading and trying again.",
           fascistfirewall ? "reachable" : "known");
446
  if (router_reload_router_list()) {
447
    return NULL;
448
  }
449
  /* give it one last try */
450
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
451
                                             for_v2_directory);
452
453
454
  return choice;
}

455
456
457
/** Return the trusted_dir_server_t for the directory authority whose identity
 * key hashes to <b>digest</b>, or NULL if no such authority is known.
 */
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
trusted_dir_server_t *
router_get_trusteddirserver_by_digest(const char *digest)
{
  if (!trusted_dir_servers)
    return NULL;

  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
     {
       if (!memcmp(ds->digest, digest, DIGEST_LEN))
         return ds;
     });

  return NULL;
}

473
474
475
/** Try to find a running trusted dirserver. If there are no running
 * trusted dirservers and <b>retry_if_no_servers</b> is non-zero,
 * set them all as running again, and try again.
476
477
 * If <b>need_v1_authority</b> is set, return only trusted servers
 * that are authorities for the V1 directory protocol.
478
479
 * Other args are as in router_pick_trusteddirserver_impl().
 */
480
routerstatus_t *
481
router_pick_trusteddirserver(authority_type_t type,
482
                             int requireother,
483
484
485
                             int fascistfirewall,
                             int retry_if_no_servers)
{
486
  routerstatus_t *choice;
487

488
  choice = router_pick_trusteddirserver_impl(type,
489
                                             requireother, fascistfirewall);
490
  if (choice || !retry_if_no_servers)
491
492
    return choice;

493
494
  log_info(LD_DIR,
           "No trusted dirservers are reachable. Trying them all again.");
495
  mark_all_trusteddirservers_up();
496
  return router_pick_trusteddirserver_impl(type,
497
                                           requireother, fascistfirewall);
498
499
}

500
/** Pick a random running valid directory server/mirror from our
501
 * routerlist.  Don't pick an authority if any non-authorities are viable.
502
503
 * If <b>fascistfirewall</b>,
 * make sure the router we pick is allowed by our firewall options.
504
505
506
 * If <b>requireother</b>, it cannot be us.  If <b>for_v2_directory</b>,
 * choose a directory server new enough to support the v2 directory
 * functionality.
507
 */
508
static routerstatus_t *
509
router_pick_directory_server_impl(int requireother, int fascistfirewall,
510
                                  int for_v2_directory)
511
{
512
  routerstatus_t *result;
513
  smartlist_t *sl;
514
  smartlist_t *trusted;
515

516
  if (!routerstatus_list)
517
518
    return NULL;

Nick Mathewson's avatar
Nick Mathewson committed
519
  /* Find all the running dirservers we know about. */
520
  sl = smartlist_create();
521
  trusted = smartlist_create();
522
  SMARTLIST_FOREACH(routerstatus_list, local_routerstatus_t *, _local_status,
523
  {
524
    routerstatus_t *status = &(_local_status->status);
525
    int is_trusted;
526
    if (!status->is_running || !status->dir_port || !status->is_valid)
527
      continue;
528
    if (requireother && router_digest_is_me(status->identity_digest))
529
      continue;
530
    if (fascistfirewall) {
531
      if (!fascist_firewall_allows_address_dir(status->addr, status->dir_port))
532
533
        continue;
    }
534
535
    is_trusted = router_digest_is_trusted_dir(status->identity_digest);
    if (for_v2_directory && !(status->is_v2_dir || is_trusted))
536
      continue;
537
    smartlist_add(is_trusted ? trusted : sl, status);
538
  });
539

540
541
542
543
  if (smartlist_len(sl))
    result = smartlist_choose(sl);
  else
    result = smartlist_choose(trusted);
544
  smartlist_free(sl);
545
  smartlist_free(trusted);
546
  return result;
547
}
548

549
550
551
552
553
/** Choose randomly from among the trusted dirservers that are up.  If
 * <b>fascistfirewall</b>, make sure the port we pick is allowed by our
 * firewall options.  If <b>requireother</b>, it cannot be us.  If
 * <b>need_v1_authority</b>, choose a trusted authority for the v1 directory
 * system.
554
 */
555
static routerstatus_t *
556
router_pick_trusteddirserver_impl(authority_type_t type,
557
                                  int requireother, int fascistfirewall)
558
559
560
{
  smartlist_t *sl;
  routerinfo_t *me;
561
  routerstatus_t *rs;
562
563
  sl = smartlist_create();
  me = router_get_my_routerinfo();
564

565
566
567
  if (!trusted_dir_servers)
    return NULL;

568
569
570
  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
    {
      if (!d->is_running) continue;
571
572
573
574
575
      if (type == V1_AUTHORITY && !d->is_v1_authority)
        continue;
      if (type == V2_AUTHORITY && !d->is_v2_authority)
        continue;
      if (type == HIDSERV_AUTHORITY && !d->is_hidserv_authority)
576
        continue;
577
578
      if (requireother && me && router_digest_is_me(d->digest))
          continue;
579
      if (fascistfirewall) {
580
        if (!fascist_firewall_allows_address_dir(d->addr, d->dir_port))
581
582
          continue;
      }
583
      smartlist_add(sl, &d->fake_status);
584
    });
Nick Mathewson's avatar
Nick Mathewson committed
585

586
  rs = smartlist_choose(sl);
587
  smartlist_free(sl);
588
  return rs;
589
590
}

591
/** Go through and mark the authoritative dirservers as up. */
592
593
594
static void
mark_all_trusteddirservers_up(void)
{
595
  if (routerlist) {
596
    SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
597
598
599
600
       if (router_digest_is_trusted_dir(router->cache_info.identity_digest) &&
         router->dir_port > 0) {
         router->is_running = 1;
       });
601
602
603
  }
  if (trusted_dir_servers) {
    SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
604
    {
605
      local_routerstatus_t *rs;
606
607
      dir->is_running = 1;
      dir->n_networkstatus_failures = 0;
608
609
610
      rs = router_get_combined_status_by_digest(dir->digest);
      if (rs)
        rs->status.is_running = 1;
611
    });
612
  }
613
  last_networkstatus_download_attempted = 0;
614
  router_dir_info_changed();
615
616
617
618
619
620
621
622
}

/** Reset all internal variables used to count failed downloads of network
 * status objects. */
void
router_reset_status_download_failures(void)
{
  mark_all_trusteddirservers_up();
623
624
}

625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
/** Look through the routerlist and identify routers that
 * advertise the same /16 network address as <b>router</b>.
 * Add each of them to <b>sl</b>.
 */
static void
routerlist_add_network_family(smartlist_t *sl, routerinfo_t *router)
{
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
  {
    if (router != r &&
        (router->addr & 0xffff0000) == (r->addr & 0xffff0000))
      smartlist_add(sl, r);
  });
}

640
/** Add all the family of <b>router</b> to the smartlist <b>sl</b>.
641
 * This is used to make sure we don't pick siblings in a single path.
642
 */
643
644
645
void
routerlist_add_family(smartlist_t *sl, routerinfo_t *router)
{
646
  routerinfo_t *r;
647
  config_line_t *cl;
648
  or_options_t *options = get_options();
649

650
651
  /* First, add any routers with similar network addresses.
   * XXX It's possible this will be really expensive; we'll see. */
652
653
  if (options->EnforceDistinctSubnets)
    routerlist_add_network_family(sl, router);
654

655
656
  if (!router->declared_family)
    return;
657

658
659
  /* Add every r such that router declares familyness with r, and r
   * declares familyhood with router. */
660
661
  SMARTLIST_FOREACH(router->declared_family, const char *, n,
    {
662
      if (!(r = router_get_by_nickname(n, 0)))
663
664
665
666
667
668
669
670
671
        continue;
      if (!r->declared_family)
        continue;
      SMARTLIST_FOREACH(r->declared_family, const char *, n2,
        {
          if (router_nickname_matches(router, n2))
            smartlist_add(sl, r);
        });
    });
672

673
  /* If the user declared any families locally, honor those too. */
674
  for (cl = get_options()->NodeFamilies; cl; cl = cl->next) {
675
    if (router_nickname_is_in_list(router, cl->value)) {
676
      add_nickname_list_to_smartlist(sl, cl->value, 0, 1, 1);
677
678
    }
  }
679
680
}

681
682
683
684
685
686
/** Given a (possibly NULL) comma-and-whitespace separated list of nicknames,
 * see which nicknames in <b>list</b> name routers in our routerlist, and add
 * the routerinfos for those routers to <b>sl</b>.  If <b>must_be_running</b>,
 * only include routers that we think are running.  If <b>warn_if_down</b>,
 * warn if some included routers aren't running.  If <b>warn_if_unnamed</b>,
 * warn if any non-Named routers are specified by nickname.
Nick Mathewson's avatar
Nick Mathewson committed
687
 */
688
void
689
add_nickname_list_to_smartlist(smartlist_t *sl, const char *list,
690
                               int must_be_running,
691
                               int warn_if_down, int warn_if_unnamed)
692
{
693
  routerinfo_t *router;
694
  smartlist_t *nickname_list;
695
  int have_dir_info = router_have_minimum_dir_info();
696

697
  if (!list)
698
    return; /* nothing to do */
Roger Dingledine's avatar
Roger Dingledine committed
699
  tor_assert(sl);
700

701
  nickname_list = smartlist_create();
702
703
  if (!warned_nicknames)
    warned_nicknames = smartlist_create();
704

705
706
707
708
  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);

  SMARTLIST_FOREACH(nickname_list, const char *, nick, {
709
    int warned;
710
    if (!is_legal_nickname_or_hexdigest(nick)) {
711
      log_warn(LD_CONFIG, "Nickname '%s' is misformed; skipping", nick);
712
713
      continue;
    }
714
    router = router_get_by_nickname(nick, warn_if_unnamed);
715
    warned = smartlist_string_isin(warned_nicknames, nick);
716
    if (router) {
717
      if (!must_be_running || router->is_running) {
718
        smartlist_add(sl,router);
719
720
721
722
        if (warned)
          smartlist_string_remove(warned_nicknames, nick);
      } else {
        if (!warned) {
723
          log_fn(warn_if_down ? LOG_WARN : LOG_DEBUG, LD_CONFIG,
724
725
726
727
                 "Nickname list includes '%s' which is known but down.",nick);
          smartlist_add(warned_nicknames, tor_strdup(nick));
        }
      }
Nick Mathewson's avatar
Nick Mathewson committed
728
    } else if (!router_get_combined_status_by_nickname(nick,warn_if_unnamed)) {
729
      if (!warned) {
730
        log_fn(have_dir_info ? LOG_WARN : LOG_INFO, LD_CONFIG,
731
732
733
734
               "Nickname list includes '%s' which isn't a known router.",nick);
        smartlist_add(warned_nicknames, tor_strdup(nick));
      }
    }
735
736
737
  });
  SMARTLIST_FOREACH(nickname_list, char *, nick, tor_free(nick));
  smartlist_free(nickname_list);
738
739
}

740
741
742
/** Return 1 iff any member of the (possibly NULL) comma-separated list
 * <b>list</b> is an acceptable nickname or hexdigest for <b>router</b>.  Else
 * return 0.
743
 */
744
int
745
746
747
748
749
router_nickname_is_in_list(routerinfo_t *router, const char *list)
{
  smartlist_t *nickname_list;
  int v = 0;

750
  if (!list)
751
    return 0; /* definitely not */
752
753
754
755
756
  tor_assert(router);

  nickname_list = smartlist_create();
  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
Nick Mathewson's avatar
Nick Mathewson committed
757
  SMARTLIST_FOREACH(nickname_list, const char *, cp,
758
                    if (router_nickname_matches(router, cp)) {v=1;break;});
Nick Mathewson's avatar
Nick Mathewson committed
759
760
  SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
  smartlist_free(nickname_list);
761
762
763
  return v;
}

Nick Mathewson's avatar
Nick Mathewson committed
764
/** Add every router from our routerlist that is currently running to
765
 * <b>sl</b>, so that we can pick a node for a circuit.
Nick Mathewson's avatar
Nick Mathewson committed
766
 */
767
static void
768
router_add_running_routers_to_smartlist(smartlist_t *sl, int allow_invalid,
769
770
                                        int need_uptime, int need_capacity,
                                        int need_guard)
771
{
772
  if (!routerlist)
773
    return;
774

775
776
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
777
    if (router->is_running &&
778
        router->purpose == ROUTER_PURPOSE_GENERAL &&
779
        (router->is_valid ||
780
/* XXX this next part is wrong and should be fixed one day -RD */
781
        (allow_invalid &&
782
783
         !router_is_unreliable(router, need_uptime,
                               need_capacity, need_guard)))) {
784
785
      /* If it's running, and either it's valid or we're ok picking
       * invalid routers and this one is suitable.
786
       */
787
      smartlist_add(sl, router);
788
    }
789
  });
790
791
}

792
793
/** Look through the routerlist until we find a router that has my key.
 Return it. */
794
routerinfo_t *
795
796
routerlist_find_my_routerinfo(void)
{
797
  if (!routerlist)
798
799
    return NULL;

800
801
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
802
    if (router_is_me(router))
803
      return router;
804
  });
805
806
807
  return NULL;
}

808
809
810
811
812
/** Find a router that's up, that has this IP address, and
 * that allows exit to this address:port, or return NULL if there
 * isn't a good one.
 */
routerinfo_t *
813
814
router_find_exact_exit_enclave(const char *address, uint16_t port)
{
815
816
817
818
819
820
821
  uint32_t addr;
  struct in_addr in;

  if (!tor_inet_aton(address, &in))
    return NULL; /* it's not an IP already */
  addr = ntohl(in.s_addr);

822
823
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
824
825
    if (router->is_running &&
        router->addr == addr &&
826
        compare_addr_to_addr_policy(addr, port, router->exit_policy) ==
827
828
          ADDR_POLICY_ACCEPTED)
      return router;
829
  });
830
831
832
  return NULL;
}

833
834
835
836
837
/** Return 1 if <b>router</b> is not suitable for these parameters, else 0.
 * If <b>need_uptime</b> is non-zero, we require a minimum uptime.
 * If <b>need_capacity</b> is non-zero, we require a minimum advertised
 * bandwidth.
 */
838
int
839
840
router_is_unreliable(routerinfo_t *router, int need_uptime,
                     int need_capacity, int need_guard)
841
{
842
  if (need_uptime && !router->is_stable)
843
    return 1;
844
  if (need_capacity && !router->is_fast)
845
    return 1;
846
847
  if (need_guard && !router->is_possible_guard)
    return 1;
848
849
  return 0;
}
850

851
852
/** Remove from routerlist <b>sl</b> all routers that are not
 * sufficiently stable. */
853
static void
854
855
routerlist_sl_remove_unreliable_routers(smartlist_t *sl, int need_uptime,
                                        int need_capacity, int need_guard)
856
857
858
859
860
861
{
  int i;
  routerinfo_t *router;

  for (i = 0; i < smartlist_len(sl); ++i) {
    router = smartlist_get(sl, i);
862
863
    if (router_is_unreliable(router, need_uptime,
                             need_capacity, need_guard)) {
Roger Dingledine's avatar
Roger Dingledine committed
864
865
//      log(LOG_DEBUG, "Router '%s' has insufficient uptime; deleting.",
 //         router->nickname);
866
867
868
869
870
      smartlist_del(sl, i--);
    }
  }
}

871
872
873
874
875
876
877
878
879
880
/** Return the smaller of the router's configured BandwidthRate
 * and its advertised capacity. */
uint32_t
router_get_advertised_bandwidth(routerinfo_t *router)
{
  if (router->bandwidthcapacity < router->bandwidthrate)
    return router->bandwidthcapacity;
  return router->bandwidthrate;
}

881
#define MAX_BELIEVABLE_BANDWIDTH 1500000 /* 1.5 MB/sec */
882
883
884
885

/** Choose a random element of router list <b>sl</b>, weighted by
 * the advertised bandwidth of each router.
 */
Roger Dingledine's avatar