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

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

15
16
#include "or.h"

17
18
/****************************************************************************/

19
/* static function prototypes */
20
21
22
23
24
static routerinfo_t *router_pick_directory_server_impl(int requireother,
                                                       int fascistfirewall,
                                                       int for_v2_directory);
static trusted_dir_server_t *router_pick_trusteddirserver_impl(
                int need_v1_support, int requireother, int fascistfirewall);
25
static void mark_all_trusteddirservers_up(void);
26
27
static int router_nickname_is_in_list(routerinfo_t *router, const char *list);
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
34
static int routerdesc_digest_is_recognized(const char *identity,
                                           const char *digest);
35
static void routerlist_assert_ok(routerlist_t *rl);
36

37
38
#define MAX_DESCRIPTORS_PER_ROUTER 5

39
/****************************************************************************/
40

41
42
43
/** 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
44

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

48
extern int has_fetched_directory; /* from main.c */
Nick Mathewson's avatar
Nick Mathewson committed
49

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

54
/** Global list of local_routerstatus_t for each router, known or unknown. */
55
static smartlist_t *routerstatus_list = NULL;
56

57
58
/** True iff any member of networkstatus_list has changed since the last time
 * we called routerstatus_list_update_from_networkstatus(). */
59
static int networkstatus_list_has_changed = 0;
60

61
62
/** True iff any element of routerstatus_list has changed since the last
 * time we called routers_update_all_from_networkstatus().*/
63
static int routerstatus_list_has_changed = 0;
64

65
66
67
/** List of strings for nicknames we've already warned about and that are
 * still unknown / unavailable. */
static smartlist_t *warned_nicknames = NULL;
68

69
70
71
/** List of strings for nicknames or fingerprints we've already warned about
 * and that are still conflicted. */
static smartlist_t *warned_conflicts = NULL;
72

73
74
75
/** 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. */
76
static time_t last_routerdesc_download_attempted = 0;
77

78
79
80
/** 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. */
81
82
static time_t last_networkstatus_download_attempted = 0;

83
/* DOCDOC */
84
85
86
87
static int have_warned_about_unverified_status = 0;
static int have_warned_about_old_version = 0;
static int have_warned_about_new_version = 0;

88
89
/** Repopulate our list of network_status_t objects from the list cached on
 * disk.  Return 0 on success, -1 on failure. */
90
91
92
93
94
int
router_reload_networkstatus(void)
{
  char filename[512];
  struct stat st;
95
  smartlist_t *entries;
96
97
98
99
100
101
102
103
104
  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, {
105
106
107
      char buf[DIGEST_LEN];
      if (strlen(fn) != HEX_DIGEST_LEN ||
          base16_decode(buf, sizeof(buf), fn, strlen(fn))) {
108
        info(LD_DIR,
109
110
111
               "Skipping cached-status file with unexpected name \"%s\"",fn);
        continue;
      }
112
113
114
115
116
      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);
117
        if (router_set_networkstatus(s, st.st_mtime, NS_FROM_CACHE, NULL)<0) {
118
          warn(LD_FS, "Couldn't load networkstatus from \"%s\"",filename);
119
120
        }
        tor_free(s);
121
122
      }
    });
123
124
  SMARTLIST_FOREACH(entries, char *, fn, tor_free(fn));
  smartlist_free(entries);
125
  networkstatus_list_clean(time(NULL));
126
  routers_update_all_from_networkstatus();
127
128
129
  return 0;
}

130
131
132
133
/* 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
134
 * "cached-routers.new".
135
136
 *
 * From time to time, we replace "cached-routers" with a new file containing
137
 * only the live, non-superseded descriptors, and clear cached-routers.new.
138
139
140
141
142
143
144
 *
 * 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. */
145
static size_t router_store_len = 0;
146
147
/** Total bytes dropped since last rebuild. */
static size_t router_bytes_dropped = 0;
148

149
150
/** Helper: return 1 iff the router log is so big we want to rebuild the
 * store. */
151
152
153
154
static int
router_should_rebuild_store(void)
{
  if (router_store_len > (1<<16))
155
156
    return (router_journal_len > router_store_len / 2 ||
            router_bytes_dropped > router_store_len / 2);
157
  else
158
    return router_journal_len > (1<<15);
159
160
}

161
162
/** Add the <b>len</b>-type router descriptor in <b>s</b> to the router
 * journal. */
163
static int
164
router_append_to_journal(const char *s, size_t len)
165
166
167
168
169
{
  or_options_t *options = get_options();
  size_t fname_len = strlen(options->DataDirectory)+32;
  char *fname = tor_malloc(len);

170
  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
171
172
173
174
175
176
               options->DataDirectory);

  if (!len)
    len = strlen(s);

  if (append_bytes_to_file(fname, s, len, 0)) {
177
    warn(LD_FS, "Unable to store router descriptor");
178
179
180
181
182
    tor_free(fname);
    return -1;
  }

  tor_free(fname);
183
  router_journal_len += len;
184
185
186
  return 0;
}

187
188
189
190
/** 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.
 */
191
static int
192
193
194
195
196
197
198
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;
199
  int r = -1, i;
200
201
202
203
204
205

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

206
  /* Don't save deadweight. */
207
  routerlist_remove_old_routers();
208

209
210
211
212
213
214
  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();

215
216
  for (i = 0; i < 2; ++i) {
    smartlist_t *lst = (i == 0) ? routerlist->old_routers : routerlist->routers;
217
    SMARTLIST_FOREACH(lst, void *, ptr,
218
    {
219
220
      signed_descriptor_t *sd = (i==0) ?
        ((signed_descriptor_t*)ptr): &((routerinfo_t*)ptr)->cache_info;
221
      sized_chunk_t *c;
222
223
      if (!sd->signed_descriptor) {
        warn(LD_BUG, "Bug! No descriptor stored for router.");
224
225
226
        goto done;
      }
      c = tor_malloc(sizeof(sized_chunk_t));
227
228
      c->bytes = sd->signed_descriptor;
      c->len = sd->signed_descriptor_len;
229
230
231
      smartlist_add(chunk_list, c);
    });
  }
232
  if (write_chunks_to_file(fname, chunk_list, 0)<0) {
233
    warn(LD_FS, "Error writing router store to disk.");
234
235
236
    goto done;
  }

237
  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
238
239
240
241
242
243
               options->DataDirectory);

  write_str_to_file(fname, "", 0);

  r = 0;
  router_store_len = len;
244
  router_journal_len = 0;
245
  router_bytes_dropped = 0;
246
247
248
249
250
251
252
253
254
 done:
  tor_free(fname);
  if (chunk_list) {
    SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
    smartlist_free(chunk_list);
  }
  return r;
}

255
256
257
/* Load all cached router descriptors from the store. Return 0 on success and
 * -1 on failure.
 */
258
259
260
261
262
263
264
265
266
int
router_reload_router_list(void)
{
  or_options_t *options = get_options();
  size_t fname_len = strlen(options->DataDirectory)+32;
  char *fname = tor_malloc(fname_len);
  struct stat st;
  int j;

267
  if (!routerlist)
268
    router_get_routerlist(); /* mallocs and inits it in place */
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287

  router_journal_len = router_store_len = 0;

  for (j = 0; j < 2; ++j) {
    char *contents;
    tor_snprintf(fname, fname_len,
                 (j==0)?"%s/cached-routers":"%s/cached-routers.new",
                 options->DataDirectory);
    contents = read_file_to_str(fname, 0);
    if (contents) {
      stat(fname, &st);
      if (j==0)
        router_store_len = st.st_size;
      else
        router_journal_len = st.st_size;
      router_load_routers_from_string(contents, 1, NULL);
      tor_free(contents);
    }
  }
Nick Mathewson's avatar
Nick Mathewson committed
288
  tor_free(fname);
289
290

  /* Don't cache expired routers. */
291
  routerlist_remove_old_routers();
292
293
294
295
296
297
298
299

  if (router_journal_len) {
    /* Always clear the journal on startup.*/
    router_rebuild_store(1);
  }
  return 0;
}

300
/** Set *<b>outp</b> to a smartlist containing a list of
301
302
303
 * trusted_dir_server_t * for all known trusted dirservers.  Callers
 * must not modify the list or its contents.
 */
304
305
void
router_get_trusted_dir_servers(smartlist_t **outp)
306
307
308
309
310
311
312
{
  if (!trusted_dir_servers)
    trusted_dir_servers = smartlist_create();

  *outp = trusted_dir_servers;
}

313
/** Try to find a running dirserver. If there are no running dirservers
314
315
316
317
 * 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
318
319
 * 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).
320
 * Other args are as in router_pick_directory_server_impl().
321
 */
322
routerinfo_t *
323
router_pick_directory_server(int requireother,
324
                             int fascistfirewall,
325
                             int for_v2_directory,
326
327
                             int retry_if_no_servers)
{
328
329
  routerinfo_t *choice;

330
  if (!routerlist)
331
    return NULL;
332

333
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
334
                                             for_v2_directory);
335
  if (choice || !retry_if_no_servers)
336
337
    return choice;

338
  info(LD_DIR,"No reachable router entries for dirservers. Trying them all again.");
339
  /* mark all authdirservers as up again */
340
  mark_all_trusteddirservers_up();
341
  /* try again */
342
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
343
                                             for_v2_directory);
344
  if (choice)
345
346
    return choice;

347
  info(LD_DIR,"Still no %s router entries. Reloading and trying again.",
348
         fascistfirewall ? "reachable" : "known");
349
  if (router_reload_router_list()) {
350
    return NULL;
351
  }
352
  /* give it one last try */
353
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
354
                                             for_v2_directory);
355
356
357
  return choice;
}

358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
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;
}

373
374
375
376
377
/** 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.
 * Other args are as in router_pick_trusteddirserver_impl().
 */
378
trusted_dir_server_t *
379
380
router_pick_trusteddirserver(int need_v1_support,
                             int requireother,
381
382
383
                             int fascistfirewall,
                             int retry_if_no_servers)
{
384
385
  trusted_dir_server_t *choice;

386
387
  choice = router_pick_trusteddirserver_impl(need_v1_support,
                                             requireother, fascistfirewall);
388
  if (choice || !retry_if_no_servers)
389
390
    return choice;

391
  info(LD_DIR,"No trusted dirservers are reachable. Trying them all again.");
392
  mark_all_trusteddirservers_up();
393
394
  return router_pick_trusteddirserver_impl(need_v1_support,
                                           requireother, fascistfirewall);
395
396
}

397
398
/** Pick a random running verified directory server/mirror from our
 * routerlist.
399
400
 * If <b>fascistfirewall</b>,
 * make sure the router we pick is allowed by our firewall options.
401
402
403
 * 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.
404
405
 */
static routerinfo_t *
406
router_pick_directory_server_impl(int requireother, int fascistfirewall,
407
                                  int for_v2_directory)
408
{
409
  routerinfo_t *result;
410
  smartlist_t *sl;
411

412
  if (!routerlist)
413
414
    return NULL;

Nick Mathewson's avatar
Nick Mathewson committed
415
  /* Find all the running dirservers we know about. */
416
  sl = smartlist_create();
417
418
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
419
    if (!router->is_running || !router->dir_port || !router->is_verified)
420
      continue;
421
    if (requireother && router_is_me(router))
422
      continue;
423
    if (fascistfirewall) {
424
      if (!fascist_firewall_allows_address(router->addr, router->dir_port))
425
426
        continue;
    }
427
428
429
430
    /* Before 0.1.1.6-alpha, only trusted dirservers served status info.
     * Before 0.1.1.7-alpha, retrieving nonexistent server IDs could bork
     * the directory server.
     */
431
    if (for_v2_directory &&
432
        !(tor_version_as_new_as(router->platform,"0.1.1.7-alpha") ||
433
          router_digest_is_trusted_dir(router->cache_info.identity_digest)))
434
      continue;
435
    smartlist_add(sl, router);
436
  });
437

438
  result = smartlist_choose(sl);
439
  smartlist_free(sl);
440
  return result;
441
}
442

443
/** Choose randomly from among the trusted dirservers that are up.
444
445
 * If <b>fascistfirewall</b>,
 * make sure the port we pick is allowed by our firewall options.
446
447
 * If <b>requireother</b>, it cannot be us.  If <b>need_v1_support</b>, choose
 * a trusted authority for the v1 directory system.
448
 */
449
static trusted_dir_server_t *
450
451
router_pick_trusteddirserver_impl(int need_v1_support,
                                  int requireother, int fascistfirewall)
452
453
454
455
456
457
{
  smartlist_t *sl;
  routerinfo_t *me;
  trusted_dir_server_t *ds;
  sl = smartlist_create();
  me = router_get_my_routerinfo();
458

459
460
461
  if (!trusted_dir_servers)
    return NULL;

462
463
464
  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
    {
      if (!d->is_running) continue;
465
466
      if (need_v1_support && !d->supports_v1_protocol)
        continue;
467
468
      if (requireother && me && router_digest_is_me(d->digest))
          continue;
469
      if (fascistfirewall) {
470
        if (!fascist_firewall_allows_address(d->addr, d->dir_port))
471
472
473
474
          continue;
      }
      smartlist_add(sl, d);
    });
Nick Mathewson's avatar
Nick Mathewson committed
475

476
477
478
479
480
  ds = smartlist_choose(sl);
  smartlist_free(sl);
  return ds;
}

481
/** Go through and mark the authoritative dirservers as up. */
482
483
484
static void
mark_all_trusteddirservers_up(void)
{
485
  if (routerlist) {
486
    SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
487
488
489
490
       if (router_digest_is_trusted_dir(router->cache_info.identity_digest) &&
         router->dir_port > 0) {
         router->is_running = 1;
       });
491
492
493
  }
  if (trusted_dir_servers) {
    SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
494
495
496
497
    {
      dir->is_running = 1;
      dir->n_networkstatus_failures = 0;
    });
498
  }
499
500
501
502
503
504
505
506
507
  last_networkstatus_download_attempted = 0;
}

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

510
/** Return 0 if \\exists an authoritative dirserver that's currently
511
512
 * thought to be running, else return 1.
 */
513
514
515
int
all_trusted_directory_servers_down(void)
{
516
517
518
519
  if (!trusted_dir_servers)
    return 1;
  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
                    if (dir->is_running) return 0);
520
  return 1;
521
522
}

523
/** Add all the family of <b>router</b> to the smartlist <b>sl</b>.
524
 * This is used to make sure we don't pick siblings in a single path.
525
 */
526
527
528
void
routerlist_add_family(smartlist_t *sl, routerinfo_t *router)
{
529
  routerinfo_t *r;
530
  config_line_t *cl;
531

532
533
  if (!router->declared_family)
    return;
534

535
536
  /* Add every r such that router declares familyness with r, and r
   * declares familyhood with router. */
537
538
  SMARTLIST_FOREACH(router->declared_family, const char *, n,
    {
539
      if (!(r = router_get_by_nickname(n, 0)))
540
541
542
543
544
545
546
547
548
        continue;
      if (!r->declared_family)
        continue;
      SMARTLIST_FOREACH(r->declared_family, const char *, n2,
        {
          if (router_nickname_matches(router, n2))
            smartlist_add(sl, r);
        });
    });
549

550
  /* If the user declared any families locally, honor those too. */
551
  for (cl = get_options()->NodeFamilies; cl; cl = cl->next) {
552
    if (router_nickname_is_in_list(router, cl->value)) {
553
      add_nickname_list_to_smartlist(sl, cl->value, 1, 1);
554
555
    }
  }
556
557
}

Roger Dingledine's avatar
Roger Dingledine committed
558
/** Given a comma-and-whitespace separated list of nicknames, see which
Nick Mathewson's avatar
Nick Mathewson committed
559
560
 * nicknames in <b>list</b> name routers in our routerlist that are
 * currently running.  Add the routerinfos for those routers to <b>sl</b>.
Nick Mathewson's avatar
Nick Mathewson committed
561
 */
562
void
563
add_nickname_list_to_smartlist(smartlist_t *sl, const char *list, int warn_if_down, int warn_if_unnamed)
564
{
565
  routerinfo_t *router;
566
  smartlist_t *nickname_list;
567

568
  if (!list)
569
    return; /* nothing to do */
Roger Dingledine's avatar
Roger Dingledine committed
570
  tor_assert(sl);
571

572
  nickname_list = smartlist_create();
573
574
  if (!warned_nicknames)
    warned_nicknames = smartlist_create();
575

576
577
578
579
  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);

  SMARTLIST_FOREACH(nickname_list, const char *, nick, {
580
    int warned;
581
    if (!is_legal_nickname_or_hexdigest(nick)) {
582
      warn(LD_CONFIG, "Nickname %s is misformed; skipping", nick);
583
584
      continue;
    }
585
    router = router_get_by_nickname(nick, warn_if_unnamed);
586
    warned = smartlist_string_isin(warned_nicknames, nick);
587
    if (router) {
588
      if (router->is_running) {
589
        smartlist_add(sl,router);
590
591
592
593
        if (warned)
          smartlist_string_remove(warned_nicknames, nick);
      } else {
        if (!warned) {
594
          log_fn(warn_if_down ? LOG_WARN : LOG_DEBUG, LD_CONFIG,
595
596
597
598
599
600
                 "Nickname list includes '%s' which is known but down.",nick);
          smartlist_add(warned_nicknames, tor_strdup(nick));
        }
      }
    } else {
      if (!warned) {
601
        log_fn(has_fetched_directory ? LOG_WARN : LOG_INFO, LD_CONFIG,
602
603
604
605
               "Nickname list includes '%s' which isn't a known router.",nick);
        smartlist_add(warned_nicknames, tor_strdup(nick));
      }
    }
606
607
608
  });
  SMARTLIST_FOREACH(nickname_list, char *, nick, tor_free(nick));
  smartlist_free(nickname_list);
609
610
}

611
612
613
/** Return 1 iff any member of the comma-separated list <b>list</b> is an
 * acceptable nickname or hexdigest for <b>router</b>.  Else return 0.
 */
614
static int
615
616
617
618
619
router_nickname_is_in_list(routerinfo_t *router, const char *list)
{
  smartlist_t *nickname_list;
  int v = 0;

620
  if (!list)
621
    return 0; /* definitely not */
622
623
624
625
626
  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
627
  SMARTLIST_FOREACH(nickname_list, const char *, cp,
628
                    if (router_nickname_matches(router, cp)) {v=1;break;});
Nick Mathewson's avatar
Nick Mathewson committed
629
630
  SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
  smartlist_free(nickname_list);
631
632
633
  return v;
}

Nick Mathewson's avatar
Nick Mathewson committed
634
635
/** Add every router from our routerlist that is currently running to
 * <b>sl</b>.
Nick Mathewson's avatar
Nick Mathewson committed
636
 */
637
static void
638
router_add_running_routers_to_smartlist(smartlist_t *sl, int allow_unverified,
639
                                        int need_uptime, int need_capacity)
640
{
641
  if (!routerlist)
642
    return;
643

644
645
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
646
    if (router->is_running &&
647
648
        (router->is_verified ||
        (allow_unverified &&
649
         !router_is_unreliable(router, need_uptime, need_capacity)))) {
650
651
652
      /* If it's running, and either it's verified or we're ok picking
       * unverified routers and this one is suitable.
       */
653
      smartlist_add(sl, router);
654
    }
655
  });
656
657
}

658
659
/** Look through the routerlist until we find a router that has my key.
 Return it. */
660
routerinfo_t *
661
662
routerlist_find_my_routerinfo(void)
{
663
  if (!routerlist)
664
665
    return NULL;

666
667
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
668
    if (router_is_me(router))
669
      return router;
670
  });
671
672
673
  return NULL;
}

674
675
676
677
678
/** 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 *
679
680
router_find_exact_exit_enclave(const char *address, uint16_t port)
{
681
682
683
684
685
686
687
  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);

688
689
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
690
691
692
693
694
    if (router->is_running &&
        router->addr == addr &&
        router_compare_addr_to_addr_policy(addr, port, router->exit_policy) ==
          ADDR_POLICY_ACCEPTED)
      return router;
695
  });
696
697
698
  return NULL;
}

699
700
701
702
703
/** 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.
 */
704
int
705
router_is_unreliable(routerinfo_t *router, int need_uptime, int need_capacity)
706
{
707
  if (need_uptime && router->uptime < ROUTER_REQUIRED_MIN_UPTIME)
708
    return 1;
709
  if (need_capacity && router->bandwidthcapacity < ROUTER_REQUIRED_MIN_BANDWIDTH)
710
711
712
    return 1;
  return 0;
}
713

714
/** Remove from routerlist <b>sl</b> all routers who have a low uptime. */
715
716
717
718
719
720
721
722
static void
routerlist_sl_remove_unreliable_routers(smartlist_t *sl)
{
  int i;
  routerinfo_t *router;

  for (i = 0; i < smartlist_len(sl); ++i) {
    router = smartlist_get(sl, i);
723
    if (router_is_unreliable(router, 1, 0)) {
Roger Dingledine's avatar
Roger Dingledine committed
724
725
//      log(LOG_DEBUG, "Router '%s' has insufficient uptime; deleting.",
 //         router->nickname);
726
727
728
729
730
      smartlist_del(sl, i--);
    }
  }
}

731
732
733
734
735
#define MAX_BELIEVABLE_BANDWIDTH 2000000 /* 2 MB/sec */

/** Choose a random element of router list <b>sl</b>, weighted by
 * the advertised bandwidth of each router.
 */
736
routerinfo_t *
737
738
739
740
741
742
743
744
routerlist_sl_choose_by_bandwidth(smartlist_t *sl)
{
  int i;
  routerinfo_t *router;
  smartlist_t *bandwidths;
  uint32_t this_bw, tmp, total_bw=0, rand_bw;
  uint32_t *p;

745
746
  /* First count the total bandwidth weight, and make a smartlist
   * of each value. */
747
748
749
  bandwidths = smartlist_create();
  for (i = 0; i < smartlist_len(sl); ++i) {
    router = smartlist_get(sl, i);
750
751
    this_bw = (router->bandwidthcapacity < router->bandwidthrate) ?
               router->bandwidthcapacity : router->bandwidthrate;
752
753
754
    /* if they claim something huge, don't believe it */
    if (this_bw > MAX_BELIEVABLE_BANDWIDTH)
      this_bw = MAX_BELIEVABLE_BANDWIDTH;
755
756
757
758
759
    p = tor_malloc(sizeof(uint32_t));
    *p = this_bw;
    smartlist_add(bandwidths, p);
    total_bw += this_bw;
  }
Roger Dingledine's avatar
Roger Dingledine committed
760
761
762
  if (!total_bw) {
    SMARTLIST_FOREACH(bandwidths, uint32_t*, p, tor_free(p));
    smartlist_free(bandwidths);
763
    return smartlist_choose(sl);
Roger Dingledine's avatar
Roger Dingledine committed
764
  }
765
  /* Second, choose a random value from the bandwidth weights. */
766
  rand_bw = crypto_rand_int(total_bw);
767
  /* Last, count through sl until we get to the element we picked */
768
  tmp = 0;
769
  for (i=0; ; i++) {
770
771
772
    tor_assert(i < smartlist_len(sl));
    p = smartlist_get(bandwidths, i);
    tmp += *p;
773
    if (tmp >= rand_bw)
774
775
776
777
      break;
  }
  SMARTLIST_FOREACH(bandwidths, uint32_t*, p, tor_free(p));
  smartlist_free(bandwidths);
778
  return (routerinfo_t *)smartlist_get(sl, i);
779
780
}

781
/** Return a random running router from the routerlist.  If any node
782
783
784
785
786
 * named in <b>preferred</b> is available, pick one of those.  Never
 * pick a node named in <b>excluded</b>, or whose routerinfo is in
 * <b>excludedsmartlist</b>, even if they are the only nodes
 * available.  If <b>strict</b> is true, never pick any node besides
 * those in <b>preferred</b>.
787
788
789
790
 * If <b>need_uptime</b> is non-zero, don't return a router with less
 * than a minimum uptime.
 * If <b>need_capacity</b> is non-zero, weight your choice by the
 * advertised capacity of each router.
791
 */
792
793
794
795
796
797
routerinfo_t *
router_choose_random_node(const char *preferred,
                          const char *excluded,
                          smartlist_t *excludedsmartlist,
                          int need_uptime, int need_capacity,
                          int allow_unverified, int strict)
798
799
800
801
802
{
  smartlist_t *sl, *excludednodes;
  routerinfo_t *choice;

  excludednodes = smartlist_create();
803
  add_nickname_list_to_smartlist(excludednodes,excluded,0,1);
804

805
806
  /* Try the preferred nodes first. Ignore need_uptime and need_capacity,
   * since the user explicitly asked for these nodes. */
807
  sl = smartlist_create();
808
  add_nickname_list_to_smartlist(sl,preferred,1,1);
809
  smartlist_subtract(sl,excludednodes);
810
  if (excludedsmartlist)
811
    smartlist_subtract(sl,excludedsmartlist);
812
  choice = smartlist_choose(sl);
813
  smartlist_free(sl);
814
  if (!choice && !strict) {
815
816
    /* Then give up on our preferred choices: any node
     * will do that has the required attributes. */
817
    sl = smartlist_create();
818
    router_add_running_routers_to_smartlist(sl, allow_unverified,
819
                                            need_uptime, need_capacity);
820
    smartlist_subtract(sl,excludednodes);
821
    if (excludedsmartlist)
822
      smartlist_subtract(sl,excludedsmartlist);
823
    if (need_uptime)
824
      routerlist_sl_remove_unreliable_routers(sl);
825
    if (need_capacity)
826
      choice = routerlist_sl_choose_by_bandwidth(sl);
827
828
    else
      choice = smartlist_choose(sl);
829
830
831
    smartlist_free(sl);
  }
  smartlist_free(excludednodes);
832
  if (!choice)
833
    warn(LD_CIRC,"No available nodes when trying to choose node. Failing.");
834
835
836
  return choice;
}

Nick Mathewson's avatar
Nick Mathewson committed
837
838
839
840
/** Return true iff the digest of <b>router</b>'s identity key,
 * encoded in hexadecimal, matches <b>hexdigest</b> (which is
 * optionally prefixed with a single dollar sign).  Return false if
 * <b>hexdigest</b> is malformed, or it doesn't match.  */
841
842
static INLINE int
router_hex_digest_matches(routerinfo_t *router, const char *hexdigest)
Nick Mathewson's avatar
Nick Mathewson committed
843
844
845
846
847
848
{
  char digest[DIGEST_LEN];
  tor_assert(hexdigest);
  if (hexdigest[0] == '$')
    ++hexdigest;

849
  /* XXXXNM Any place that uses this inside a loop could probably do better. */
Nick Mathewson's avatar
Nick Mathewson committed
850
851
  if (strlen(hexdigest) != HEX_DIGEST_LEN ||
      base16_decode(digest, DIGEST_LEN, hexdigest, HEX_DIGEST_LEN)<0)
Nick Mathewson's avatar
Nick Mathewson committed
852
    return 0;
853
  return (!memcmp(digest, router->cache_info.identity_digest, DIGEST_LEN));
Nick Mathewson's avatar
Nick Mathewson committed
854
855
}

856
/** Return true if <b>router</b>'s nickname matches <b>nickname</b>
Nick Mathewson's avatar
Nick Mathewson committed
857
858
 * (case-insensitive), or if <b>router's</b> identity key digest
 * matches a hexadecimal value stored in <b>nickname</b>.  Return
859
860
 * false otherwise. */
static int
861
router_nickname_matches(routerinfo_t *router, const char *nickname)
Nick Mathewson's avatar
Nick Mathewson committed
862
863
864
{
  if (nickname[0]!='$' && !strcasecmp(router->nickname, nickname))
    return 1;
865
  return router_hex_digest_matches(router, nickname);
Nick Mathewson's avatar
Nick Mathewson committed
866
867
}

868
869
870
/** Return the router in our routerlist whose (case-insensitive)
 * nickname or (case-sensitive) hexadecimal key digest is
 * <b>nickname</b>.  Return NULL if no such router is known.
Nick Mathewson's avatar
Nick Mathewson committed
871
 */
872
routerinfo_t *
873
router_get_by_nickname(const char *nickname, int warn_if_unnamed)
874
{
875
  int maybedigest;
876
  char digest[DIGEST_LEN];
877
878
  routerinfo_t *best_match=NULL;
  int n_matches = 0;
879

880
  tor_assert(nickname);
881
882
  if (!routerlist)
    return NULL;
Nick Mathewson's avatar
Nick Mathewson committed
883
884
  if (nickname[0] == '$')
    return router_get_by_hexdigest(nickname);
885
886
887
  if (server_mode(get_options()) &&
      !strcasecmp(nickname, get_options()->Nickname))
    return router_get_my_routerinfo();
Nick Mathewson's avatar
Nick Mathewson committed
888

889
890
891
  maybedigest = (strlen(nickname) == HEX_DIGEST_LEN) &&
    (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0);

892
893
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
894
895
896
897
898
899
900
901
    if (!strcasecmp(router->nickname, nickname)) {
      if (router->is_named)
        return router;
      else {
        ++n_matches;
        best_match = router;
      }
    } else if (maybedigest &&
902
               !memcmp(digest, router->cache_info.identity_digest, DIGEST_LEN)) {
903
      return router;
904
    }
905
  });
906

907
  if (best_match) {
908
    if (warn_if_unnamed && n_matches > 1) {
909
910
911
912
913
914
915
916
917
918
      smartlist_t *fps = smartlist_create();
      int any_unwarned = 0;
      SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
        {
          local_routerstatus_t *rs;
          char *desc;
          size_t dlen;
          char fp[HEX_DIGEST_LEN+1];
          if (strcasecmp(router->nickname, nickname))
            continue;
919
          rs=router_get_combined_status_by_digest(router->cache_info.identity_digest);
920
921
922
923
          if (!rs->name_lookup_warned) {
            rs->name_lookup_warned = 1;
            any_unwarned = 1;
          }
924
          base16_encode(fp, sizeof(fp), router->cache_info.identity_digest, DIGEST_LEN);