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

7
8
9
10
11
12
/**
 * \file nodelist.c
 *
 * \brief Structures and functions for tracking what we know about the routers
 *   on the Tor network, and correlating information from networkstatus,
 *   routerinfo, and microdescs.
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 *
 * The key structure here is node_t: that's the canonical way to refer
 * to a Tor relay that we might want to build a circuit through.  Every
 * node_t has either a routerinfo_t, or a routerstatus_t from the current
 * networkstatus consensus.  If it has a routerstatus_t, it will also
 * need to have a microdesc_t before you can use it for circuits.
 *
 * The nodelist_t is a global singleton that maps identities to node_t
 * objects.  Access them with the node_get_*() functions.  The nodelist_t
 * is maintained by calls throughout the codebase
 *
 * Generally, other code should not have to reach inside a node_t to
 * see what information it has.  Instead, you should call one of the
 * many accessor functions that works on a generic node_t.  If there
 * isn't one that does what you need, it's better to make such a function,
 * and then use it.
 *
 * For historical reasons, some of the functions that select a node_t
 * from the list of all usable node_t objects are in the routerlist.c
 * module, since they originally selected a routerinfo_t. (TODO: They
 * should move!)
 *
 * (TODO: Perhaps someday we should abstract the remaining ways of
 * talking about a relay to also be node_t instances. Those would be
 * routerstatus_t as used for directory requests, and dir_server_t as
 * used for authorities and fallback directories.)
39
40
 */

41
42
#define NODELIST_PRIVATE

43
#include "core/or/or.h"
44
45
46
#include "app/config/config.h"
#include "core/mainloop/mainloop.h"
#include "core/mainloop/netstatus.h"
47
#include "core/or/address_set.h"
48
49
#include "core/or/policies.h"
#include "core/or/protover.h"
50
#include "feature/client/bridges.h"
51
#include "feature/client/entrynodes.h"
52
#include "feature/control/control.h"
53
#include "feature/dirauth/process_descs.h"
54
#include "feature/dircache/dirserv.h"
55
#include "feature/hs/hs_client.h"
56
57
58
#include "feature/hs/hs_common.h"
#include "feature/nodelist/describe.h"
#include "feature/nodelist/dirlist.h"
59
60
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
61
#include "feature/nodelist/node_select.h"
62
#include "feature/nodelist/nodelist.h"
63
64
65
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "feature/nodelist/torcert.h"
66
#include "feature/rend/rendservice.h"
67
68
#include "lib/encoding/binascii.h"
#include "lib/err/backtrace.h"
69
#include "lib/geoip/geoip.h"
70
#include "lib/net/address.h"
71
72
73

#include <string.h>

74
#include "feature/dirauth/authmode.h"
75

76
77
78
79
80
81
82
#include "feature/dirclient/dir_server_st.h"
#include "feature/nodelist/microdesc_st.h"
#include "feature/nodelist/networkstatus_st.h"
#include "feature/nodelist/node_st.h"
#include "feature/nodelist/routerinfo_st.h"
#include "feature/nodelist/routerlist_st.h"
#include "feature/nodelist/routerstatus_st.h"
83

84
static void nodelist_drop_node(node_t *node, int remove_from_ht);
85
86
87
#define node_free(val) \
  FREE_AND_NULL(node_t, node_free_, (val))
static void node_free_(node_t *node);
88
89
90
91

/** count_usable_descriptors counts descriptors with these flag(s)
 */
typedef enum {
92
93
94
95
96
97
98
99
100
101
102
  /* All descriptors regardless of flags or exit policies */
  USABLE_DESCRIPTOR_ALL         = 0U,
  /* Only count descriptors with an exit policy that allows at least one port
   */
  USABLE_DESCRIPTOR_EXIT_POLICY = 1U << 0,
  /* Only count descriptors for relays that have the exit flag in the
   * consensus */
  USABLE_DESCRIPTOR_EXIT_FLAG   = 1U << 1,
  /* Only count descriptors for relays that have the policy and the flag */
  USABLE_DESCRIPTOR_EXIT_POLICY_AND_FLAG = (USABLE_DESCRIPTOR_EXIT_POLICY |
                                            USABLE_DESCRIPTOR_EXIT_FLAG)
103
104
105
106
107
108
109
110
} usable_descriptor_t;
static void count_usable_descriptors(int *num_present,
                                     int *num_usable,
                                     smartlist_t *descs_out,
                                     const networkstatus_t *consensus,
                                     time_t now,
                                     routerset_t *in_set,
                                     usable_descriptor_t exit_only);
111
static void update_router_have_minimum_dir_info(void);
112
113
static double get_frac_paths_needed_for_circs(const or_options_t *options,
                                              const networkstatus_t *ns);
114
static void node_add_to_address_set(const node_t *node);
115
116
117
118
119
120
121
122
123
124

/** A nodelist_t holds a node_t object for every router we're "willing to use
 * for something".  Specifically, it should hold a node_t for every node that
 * is currently in the routerlist, or currently in the consensus we're using.
 */
typedef struct nodelist_t {
  /* A list of all the nodes. */
  smartlist_t *nodes;
  /* Hash table to map from node ID digest to node. */
  HT_HEAD(nodelist_map, node_t) nodes_by_id;
125
126
127
128
129
130
131
132
  /* Hash table to map from node Ed25519 ID to node.
   *
   * Whenever a node's routerinfo or microdescriptor is about to change,
   * you should remove it from this map with node_remove_from_ed25519_map().
   * Whenever a node's routerinfo or microdescriptor has just chaned,
   * you should add it to this map with node_add_to_ed25519_map().
   */
  HT_HEAD(nodelist_ed_map, node_t) nodes_by_ed_id;
133

134
135
  /* Set of addresses that belong to nodes we believe in. */
  address_set_t *node_addrs;
136
137
138
139
140

  /* The valid-after time of the last live consensus that initialized the
   * nodelist.  We use this to detect outdated nodelists that need to be
   * rebuilt using a newer consensus. */
  time_t live_consensus_valid_after;
141
142
} nodelist_t;

143
static inline unsigned int
144
145
node_id_hash(const node_t *node)
{
146
  return (unsigned) siphash24g(node->identity, DIGEST_LEN);
147
148
}

149
static inline unsigned int
150
151
node_id_eq(const node_t *node1, const node_t *node2)
{
152
  return tor_memeq(node1->identity, node2->identity, DIGEST_LEN);
153
154
}

155
HT_PROTOTYPE(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq)
156
157
HT_GENERATE2(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq,
             0.6, tor_reallocarray_, tor_free_)
158

159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
static inline unsigned int
node_ed_id_hash(const node_t *node)
{
  return (unsigned) siphash24g(node->ed25519_id.pubkey, ED25519_PUBKEY_LEN);
}

static inline unsigned int
node_ed_id_eq(const node_t *node1, const node_t *node2)
{
  return ed25519_pubkey_eq(&node1->ed25519_id, &node2->ed25519_id);
}

HT_PROTOTYPE(nodelist_ed_map, node_t, ed_ht_ent, node_ed_id_hash,
             node_ed_id_eq)
HT_GENERATE2(nodelist_ed_map, node_t, ed_ht_ent, node_ed_id_hash,
             node_ed_id_eq, 0.6, tor_reallocarray_, tor_free_)

176
177
178
179
180
181
182
183
184
185
/** The global nodelist. */
static nodelist_t *the_nodelist=NULL;

/** Create an empty nodelist if we haven't done so already. */
static void
init_nodelist(void)
{
  if (PREDICT_UNLIKELY(the_nodelist == NULL)) {
    the_nodelist = tor_malloc_zero(sizeof(nodelist_t));
    HT_INIT(nodelist_map, &the_nodelist->nodes_by_id);
186
    HT_INIT(nodelist_ed_map, &the_nodelist->nodes_by_ed_id);
187
    the_nodelist->nodes = smartlist_new();
188
189
190
  }
}

191
/** As node_get_by_id, but returns a non-const pointer */
192
193
MOCK_IMPL(node_t *,
node_get_mutable_by_id,(const char *identity_digest))
194
195
196
197
198
199
200
201
202
203
{
  node_t search, *node;
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return NULL;

  memcpy(&search.identity, identity_digest, DIGEST_LEN);
  node = HT_FIND(nodelist_map, &the_nodelist->nodes_by_id, &search);
  return node;
}

204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
/** As node_get_by_ed25519_id, but returns a non-const pointer */
node_t *
node_get_mutable_by_ed25519_id(const ed25519_public_key_t *ed_id)
{
  node_t search, *node;
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return NULL;
  if (BUG(ed_id == NULL) || BUG(ed25519_public_key_is_zero(ed_id)))
    return NULL;

  memcpy(&search.ed25519_id, ed_id, sizeof(search.ed25519_id));
  node = HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, &search);
  return node;
}

219
220
/** Return the node_t whose identity is <b>identity_digest</b>, or NULL
 * if no such node exists. */
221
222
MOCK_IMPL(const node_t *,
node_get_by_id,(const char *identity_digest))
223
224
225
226
{
  return node_get_mutable_by_id(identity_digest);
}

227
228
229
230
231
232
233
234
/** Return the node_t whose ed25519 identity is <b>ed_id</b>, or NULL
 * if no such node exists. */
MOCK_IMPL(const node_t *,
node_get_by_ed25519_id,(const ed25519_public_key_t *ed_id))
{
  return node_get_mutable_by_ed25519_id(ed_id);
}

235
236
237
238
239
240
241
242
243
244
245
/** Internal: return the node_t whose identity_digest is
 * <b>identity_digest</b>.  If none exists, create a new one, add it to the
 * nodelist, and return it.
 *
 * Requires that the nodelist be initialized.
 */
static node_t *
node_get_or_create(const char *identity_digest)
{
  node_t *node;

246
  if ((node = node_get_mutable_by_id(identity_digest)))
247
248
249
250
251
252
253
254
255
    return node;

  node = tor_malloc_zero(sizeof(node_t));
  memcpy(node->identity, identity_digest, DIGEST_LEN);
  HT_INSERT(nodelist_map, &the_nodelist->nodes_by_id, node);

  smartlist_add(the_nodelist->nodes, node);
  node->nodelist_idx = smartlist_len(the_nodelist->nodes) - 1;

256
257
  node->country = -1;

258
259
260
  return node;
}

261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
/** Remove <b>node</b> from the ed25519 map (if it present), and
 * set its ed25519_id field to zero. */
static int
node_remove_from_ed25519_map(node_t *node)
{
  tor_assert(the_nodelist);
  tor_assert(node);

  if (ed25519_public_key_is_zero(&node->ed25519_id)) {
    return 0;
  }

  int rv = 0;
  node_t *search =
    HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  if (BUG(search != node)) {
    goto clear_and_return;
  }

  search = HT_REMOVE(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  tor_assert(search == node);
  rv = 1;

 clear_and_return:
  memset(&node->ed25519_id, 0, sizeof(node->ed25519_id));
  return rv;
}

289
290
291
292
293
294
295
296
297
298
299
300
301
302
/** Helper function to log details of duplicated ed2559_ids */
static void
node_log_dup_ed_id(const node_t *old, const node_t *node, const char *ed_id)
{
  char *s;
  char *olddesc = tor_strdup(node_describe(old));

  tor_asprintf(&s, "Reused ed25519_id %s: old %s new %s", ed_id,
               olddesc, node_describe(node));
  log_backtrace(LOG_NOTICE, LD_DIR, s);
  tor_free(olddesc);
  tor_free(s);
}

303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
/** If <b>node</b> has an ed25519 id, and it is not already in the ed25519 id
 * map, set its ed25519_id field, and add it to the ed25519 map.
 */
static int
node_add_to_ed25519_map(node_t *node)
{
  tor_assert(the_nodelist);
  tor_assert(node);

  if (! ed25519_public_key_is_zero(&node->ed25519_id)) {
    return 0;
  }

  const ed25519_public_key_t *key = node_get_ed25519_id(node);
  if (!key) {
    return 0;
  }

  node_t *old;
  memcpy(&node->ed25519_id, key, sizeof(node->ed25519_id));
  old = HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
  if (old) {
    char ed_id[BASE32_BUFSIZE(sizeof(key->pubkey))];

    base32_encode(ed_id, sizeof(ed_id), (const char *)key->pubkey,
                  sizeof(key->pubkey));
    if (BUG(old == node)) {
      /* Actual bug: all callers of this function call
       * node_remove_from_ed25519_map first. */
      log_err(LD_BUG,
              "Unexpectedly found deleted node with ed25519_id %s", ed_id);
    } else {
      /* Distinct nodes sharing a ed25519 id, possibly due to relay
       * misconfiguration.  The key pinning might not catch this,
       * possibly due to downloading a missing descriptor during
       * consensus voting. */
      node_log_dup_ed_id(old, node, ed_id);
340
      memset(&node->ed25519_id, 0, sizeof(node->ed25519_id));
341
    }
342
343
344
345
346
347
348
    return 0;
  }

  HT_INSERT(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  return 1;
}

349
350
351
/* For a given <b>node</b> for the consensus <b>ns</b>, set the hsdir index
 * for the node, both current and next if possible. This can only fails if the
 * node_t ed25519 identity key can't be found which would be a bug. */
352
STATIC void
353
354
node_set_hsdir_index(node_t *node, const networkstatus_t *ns)
{
355
  time_t now = approx_time();
356
  const ed25519_public_key_t *node_identity_pk;
357
  uint8_t *fetch_srv = NULL, *store_first_srv = NULL, *store_second_srv = NULL;
358
  uint64_t next_time_period_num, current_time_period_num;
359
  uint64_t fetch_tp, store_first_tp, store_second_tp;
360
361
362
363

  tor_assert(node);
  tor_assert(ns);

364
  if (!networkstatus_is_live(ns, now)) {
365
366
367
    static struct ratelim_t live_consensus_ratelim = RATELIM_INIT(30 * 60);
    log_fn_ratelim(&live_consensus_ratelim, LOG_INFO, LD_GENERAL,
                   "Not setting hsdir index with a non-live consensus.");
368
369
370
    goto done;
  }

371
372
  node_identity_pk = node_get_ed25519_id(node);
  if (node_identity_pk == NULL) {
373
    log_debug(LD_GENERAL, "ed25519 identity public key not found when "
374
                          "trying to build the hsdir indexes for node %s",
375
              node_describe(node));
376
377
378
    goto done;
  }

379
  /* Get the current and next time period number. */
380
381
  current_time_period_num = hs_get_time_period_num(0);
  next_time_period_num = hs_get_next_time_period_num(0);
382

383
384
385
  /* We always use the current time period for fetching descs */
  fetch_tp = current_time_period_num;

386
387
  /* Now extract the needed SRVs and time periods for building hsdir indices */
  if (hs_in_period_between_tp_and_srv(ns, now)) {
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
    fetch_srv = hs_get_current_srv(fetch_tp, ns);

    store_first_tp = hs_get_previous_time_period_num(0);
    store_second_tp = current_time_period_num;
  } else {
    fetch_srv = hs_get_previous_srv(fetch_tp, ns);

    store_first_tp = current_time_period_num;
    store_second_tp = next_time_period_num;
  }

  /* We always use the old SRV for storing the first descriptor and the latest
   * SRV for storing the second descriptor */
  store_first_srv = hs_get_previous_srv(store_first_tp, ns);
  store_second_srv = hs_get_current_srv(store_second_tp, ns);

  /* Build the fetch index. */
  hs_build_hsdir_index(node_identity_pk, fetch_srv, fetch_tp,
406
                       node->hsdir_index.fetch);
407
408
409

  /* If we are in the time segment between SRV#N and TP#N, the fetch index is
     the same as the first store index */
410
  if (!hs_in_period_between_tp_and_srv(ns, now)) {
411
412
    memcpy(node->hsdir_index.store_first, node->hsdir_index.fetch,
           sizeof(node->hsdir_index.store_first));
413
  } else {
414
    hs_build_hsdir_index(node_identity_pk, store_first_srv, store_first_tp,
415
                         node->hsdir_index.store_first);
416
417
  }

418
419
  /* If we are in the time segment between TP#N and SRV#N+1, the fetch index is
     the same as the second store index */
420
  if (hs_in_period_between_tp_and_srv(ns, now)) {
421
422
    memcpy(node->hsdir_index.store_second, node->hsdir_index.fetch,
           sizeof(node->hsdir_index.store_second));
423
  } else {
424
    hs_build_hsdir_index(node_identity_pk, store_second_srv, store_second_tp,
425
                         node->hsdir_index.store_second);
426
427
428
  }

 done:
429
430
431
  tor_free(fetch_srv);
  tor_free(store_first_srv);
  tor_free(store_second_srv);
432
433
434
  return;
}

435
436
437
/** Called when a node's address changes. */
static void
node_addrs_changed(node_t *node)
438
{
439
440
  node->last_reachable = node->last_reachable6 = 0;
  node->country = -1;
441
442
}

443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
/** Add all address information about <b>node</b> to the current address
 * set (if there is one).
 */
static void
node_add_to_address_set(const node_t *node)
{
  if (!the_nodelist || !the_nodelist->node_addrs)
    return;

  /* These various address sources can be redundant, but it's likely faster
   * to add them all than to compare them all for equality. */

  if (node->rs) {
    if (node->rs->addr)
      address_set_add_ipv4h(the_nodelist->node_addrs, node->rs->addr);
    if (!tor_addr_is_null(&node->rs->ipv6_addr))
      address_set_add(the_nodelist->node_addrs, &node->rs->ipv6_addr);
  }
  if (node->ri) {
    if (node->ri->addr)
      address_set_add_ipv4h(the_nodelist->node_addrs, node->ri->addr);
    if (!tor_addr_is_null(&node->ri->ipv6_addr))
      address_set_add(the_nodelist->node_addrs, &node->ri->ipv6_addr);
  }
  if (node->md) {
    if (!tor_addr_is_null(&node->md->ipv6_addr))
      address_set_add(the_nodelist->node_addrs, &node->md->ipv6_addr);
  }
}

/** Return true if <b>addr</b> is the address of some node in the nodelist.
 * If not, probably return false. */
int
nodelist_probably_contains_address(const tor_addr_t *addr)
{
  if (BUG(!addr))
    return 0;

  if (!the_nodelist || !the_nodelist->node_addrs)
    return 0;

  return address_set_probably_contains(the_nodelist->node_addrs, addr);
}

487
488
489
490
/** Add <b>ri</b> to an appropriate node in the nodelist.  If we replace an
 * old routerinfo, and <b>ri_old_out</b> is not NULL, set *<b>ri_old_out</b>
 * to the previous routerinfo.
 */
491
node_t *
492
nodelist_set_routerinfo(routerinfo_t *ri, routerinfo_t **ri_old_out)
493
{
494
495
496
497
  node_t *node;
  const char *id_digest;
  int had_router = 0;
  tor_assert(ri);
498

499
500
501
502
  init_nodelist();
  id_digest = ri->cache_info.identity_digest;
  node = node_get_or_create(id_digest);

503
504
  node_remove_from_ed25519_map(node);

505
506
507
508
509
510
511
  if (node->ri) {
    if (!routers_have_same_or_addrs(node->ri, ri)) {
      node_addrs_changed(node);
    }
    had_router = 1;
    if (ri_old_out)
      *ri_old_out = node->ri;
512
  } else {
513
514
    if (ri_old_out)
      *ri_old_out = NULL;
515
  }
516
  node->ri = ri;
517

518
519
  node_add_to_ed25519_map(node);

520
521
522
  if (node->country == -1)
    node_set_country(node);

523
  if (authdir_mode(get_options()) && !had_router) {
524
    const char *discard=NULL;
525
    uint32_t status = dirserv_router_get_status(ri, &discard, LOG_INFO);
526
527
528
    dirserv_set_node_flags_from_authoritative_status(node, status);
  }

529
530
531
  /* Setting the HSDir index requires the ed25519 identity key which can
   * only be found either in the ri or md. This is why this is called here.
   * Only nodes supporting HSDir=2 protocol version needs this index. */
532
  if (node->rs && node->rs->pv.supports_v3_hsdir) {
533
534
535
536
    node_set_hsdir_index(node,
                         networkstatus_get_latest_consensus());
  }

537
538
  node_add_to_address_set(node);

539
540
541
542
543
544
545
546
547
548
549
550
551
  return node;
}

/** Set the appropriate node_t to use <b>md</b> as its microdescriptor.
 *
 * Called when a new microdesc has arrived and the usable consensus flavor
 * is "microdesc".
 **/
node_t *
nodelist_add_microdesc(microdesc_t *md)
{
  networkstatus_t *ns =
    networkstatus_get_latest_consensus_by_flavor(FLAV_MICRODESC);
552
  const routerstatus_t *rs;
553
554
555
556
557
558
559
560
561
562
  node_t *node;
  if (ns == NULL)
    return NULL;
  init_nodelist();

  /* Microdescriptors don't carry an identity digest, so we need to figure
   * it out by looking up the routerstatus. */
  rs = router_get_consensus_status_by_descriptor_digest(ns, md->digest);
  if (rs == NULL)
    return NULL;
563
  node = node_get_mutable_by_id(rs->identity_digest);
Taylor Yu's avatar
Taylor Yu committed
564
565
566
567
568
569
  if (node == NULL)
    return NULL;

  node_remove_from_ed25519_map(node);
  if (node->md)
    node->md->held_by_nodes--;
570

Taylor Yu's avatar
Taylor Yu committed
571
572
573
574
575
576
577
578
579
  node->md = md;
  md->held_by_nodes++;
  /* Setting the HSDir index requires the ed25519 identity key which can
   * only be found either in the ri or md. This is why this is called here.
   * Only nodes supporting HSDir=2 protocol version needs this index. */
  if (rs->pv.supports_v3_hsdir) {
    node_set_hsdir_index(node, ns);
  }
  node_add_to_ed25519_map(node);
580
581
  node_add_to_address_set(node);

582
583
584
  return node;
}

585
586
587
588
589
590
591
592
593
594
595
/* Default value. */
#define ESTIMATED_ADDRESS_PER_NODE 2

/* Return the estimated number of address per node_t. This is used for the
 * size of the bloom filter in the nodelist (node_addrs). */
MOCK_IMPL(int,
get_estimated_address_per_node, (void))
{
  return ESTIMATED_ADDRESS_PER_NODE;
}

Linus Nordberg's avatar
Linus Nordberg committed
596
/** Tell the nodelist that the current usable consensus is <b>ns</b>.
597
598
599
600
601
602
603
 * This makes the nodelist change all of the routerstatus entries for
 * the nodes, drop nodes that no longer have enough info to get used,
 * and grab microdescriptors into nodes as appropriate.
 */
void
nodelist_set_consensus(networkstatus_t *ns)
{
604
  const or_options_t *options = get_options();
605
  int authdir = authdir_mode_v3(options);
606

607
  init_nodelist();
608
609
  if (ns->flavor == FLAV_MICRODESC)
    (void) get_microdesc_cache(); /* Make sure it exists first. */
610
611
612
613

  SMARTLIST_FOREACH(the_nodelist->nodes, node_t *, node,
                    node->rs = NULL);

614
  /* Conservatively estimate that every node will have 2 addresses. */
615
616
  const int estimated_addresses = smartlist_len(ns->routerstatus_list) *
                                  get_estimated_address_per_node();
617
618
619
  address_set_free(the_nodelist->node_addrs);
  the_nodelist->node_addrs = address_set_new(estimated_addresses);

620
621
622
623
624
  SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
    node_t *node = node_get_or_create(rs->identity_digest);
    node->rs = rs;
    if (ns->flavor == FLAV_MICRODESC) {
      if (node->md == NULL ||
625
          tor_memneq(node->md->digest,rs->descriptor_digest,DIGEST256_LEN)) {
626
        node_remove_from_ed25519_map(node);
627
        if (node->md)
628
          node->md->held_by_nodes--;
629
630
        node->md = microdesc_cache_lookup_by_digest256(NULL,
                                                       rs->descriptor_digest);
631
        if (node->md)
632
          node->md->held_by_nodes++;
633
        node_add_to_ed25519_map(node);
634
635
      }
    }
636

637
    if (rs->pv.supports_v3_hsdir) {
638
639
      node_set_hsdir_index(node, ns);
    }
640
641
642
643
644
    node_set_country(node);

    /* If we're not an authdir, believe others. */
    if (!authdir) {
      node->is_valid = rs->is_valid;
645
      node->is_running = rs->is_flagged_running;
646
647
648
649
650
651
      node->is_fast = rs->is_fast;
      node->is_stable = rs->is_stable;
      node->is_possible_guard = rs->is_possible_guard;
      node->is_exit = rs->is_exit;
      node->is_bad_exit = rs->is_bad_exit;
      node->is_hs_dir = rs->is_hs_dir;
652
      node->ipv6_preferred = 0;
653
      if (fascist_firewall_prefer_ipv6_orport(options) &&
654
655
656
          (tor_addr_is_null(&rs->ipv6_addr) == 0 ||
           (node->md && tor_addr_is_null(&node->md->ipv6_addr) == 0)))
        node->ipv6_preferred = 1;
657
658
    }

659
  } SMARTLIST_FOREACH_END(rs);
660

661
  nodelist_purge();
662

663
664
665
666
667
  /* Now add all the nodes we have to the address set. */
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    node_add_to_address_set(node);
  } SMARTLIST_FOREACH_END(node);

668
669
670
671
672
673
674
675
676
677
678
679
  if (! authdir) {
    SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
      /* We have no routerstatus for this router. Clear flags so we can skip
       * it, maybe.*/
      if (!node->rs) {
        tor_assert(node->ri); /* if it had only an md, or nothing, purge
                               * would have removed it. */
        if (node->ri->purpose == ROUTER_PURPOSE_GENERAL) {
          /* Clear all flags. */
          node->is_valid = node->is_running = node->is_hs_dir =
            node->is_fast = node->is_stable =
            node->is_possible_guard = node->is_exit =
680
            node->is_bad_exit = node->ipv6_preferred = 0;
681
682
683
684
        }
      }
    } SMARTLIST_FOREACH_END(node);
  }
685
686
687
688
689
690

  /* If the consensus is live, note down the consensus valid-after that formed
   * the nodelist. */
  if (networkstatus_is_live(ns, approx_time())) {
    the_nodelist->live_consensus_valid_after = ns->valid_after;
  }
691
692
}

693
694
695
/** Return 1 iff <b>node</b> has Exit flag and no BadExit flag.
 * Otherwise, return 0.
 */
696
697
int
node_is_good_exit(const node_t *node)
698
699
700
701
{
  return node->is_exit && ! node->is_bad_exit;
}

702
/** Helper: return true iff a node has a usable amount of information*/
703
static inline int
704
705
706
707
708
709
710
711
712
713
node_is_usable(const node_t *node)
{
  return (node->rs) || (node->ri);
}

/** Tell the nodelist that <b>md</b> is no longer a microdescriptor for the
 * node with <b>identity_digest</b>. */
void
nodelist_remove_microdesc(const char *identity_digest, microdesc_t *md)
{
714
  node_t *node = node_get_mutable_by_id(identity_digest);
715
  if (node && node->md == md) {
716
    node->md = NULL;
717
    md->held_by_nodes--;
718
719
720
    if (! node_get_ed25519_id(node)) {
      node_remove_from_ed25519_map(node);
    }
721
  }
722
723
724
725
726
727
}

/** Tell the nodelist that <b>ri</b> is no longer in the routerlist. */
void
nodelist_remove_routerinfo(routerinfo_t *ri)
{
728
  node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest);
729
730
731
  if (node && node->ri == ri) {
    node->ri = NULL;
    if (! node_is_usable(node)) {
732
      nodelist_drop_node(node, 1);
733
734
735
736
737
738
739
740
      node_free(node);
    }
  }
}

/** Remove <b>node</b> from the nodelist.  (Asserts that it was there to begin
 * with.) */
static void
741
nodelist_drop_node(node_t *node, int remove_from_ht)
742
743
744
{
  node_t *tmp;
  int idx;
745
746
747
748
  if (remove_from_ht) {
    tmp = HT_REMOVE(nodelist_map, &the_nodelist->nodes_by_id, node);
    tor_assert(tmp == node);
  }
749
  node_remove_from_ed25519_map(node);
750
751
752
753
754
755
756
757
758
759
760
761
762

  idx = node->nodelist_idx;
  tor_assert(idx >= 0);

  tor_assert(node == smartlist_get(the_nodelist->nodes, idx));
  smartlist_del(the_nodelist->nodes, idx);
  if (idx < smartlist_len(the_nodelist->nodes)) {
    tmp = smartlist_get(the_nodelist->nodes, idx);
    tmp->nodelist_idx = idx;
  }
  node->nodelist_idx = -1;
}

763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
/** Return a newly allocated smartlist of the nodes that have <b>md</b> as
 * their microdescriptor. */
smartlist_t *
nodelist_find_nodes_with_microdesc(const microdesc_t *md)
{
  smartlist_t *result = smartlist_new();

  if (the_nodelist == NULL)
    return result;

  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    if (node->md == md) {
      smartlist_add(result, node);
    }
  } SMARTLIST_FOREACH_END(node);

  return result;
}

782
783
/** Release storage held by <b>node</b>  */
static void
784
node_free_(node_t *node)
785
786
787
{
  if (!node)
    return;
788
  if (node->md)
789
    node->md->held_by_nodes--;
790
791
792
793
794
795
796
797
798
799
800
801
802
  tor_assert(node->nodelist_idx == -1);
  tor_free(node);
}

/** Remove all entries from the nodelist that don't have enough info to be
 * usable for anything. */
void
nodelist_purge(void)
{
  node_t **iter;
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return;

803
  /* Remove the non-usable nodes. */
804
805
806
  for (iter = HT_START(nodelist_map, &the_nodelist->nodes_by_id); iter; ) {
    node_t *node = *iter;

807
808
    if (node->md && !node->rs) {
      /* An md is only useful if there is an rs. */
809
      node->md->held_by_nodes--;
810
811
812
      node->md = NULL;
    }

813
814
815
816
    if (node_is_usable(node)) {
      iter = HT_NEXT(nodelist_map, &the_nodelist->nodes_by_id, iter);
    } else {
      iter = HT_NEXT_RMV(nodelist_map, &the_nodelist->nodes_by_id, iter);
817
      nodelist_drop_node(node, 0);
818
819
820
      node_free(node);
    }
  }
821
  nodelist_assert_ok();
822
823
824
825
826
827
828
829
830
831
}

/** Release all storage held by the nodelist. */
void
nodelist_free_all(void)
{
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return;

  HT_CLEAR(nodelist_map, &the_nodelist->nodes_by_id);
832
  HT_CLEAR(nodelist_ed_map, &the_nodelist->nodes_by_ed_id);
833
834
835
836
837
838
839
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    node->nodelist_idx = -1;
    node_free(node);
  } SMARTLIST_FOREACH_END(node);

  smartlist_free(the_nodelist->nodes);

840
841
842
  address_set_free(the_nodelist->node_addrs);
  the_nodelist->node_addrs = NULL;

843
844
845
846
847
848
849
850
851
852
853
  tor_free(the_nodelist);
}

/** Check that the nodelist is internally consistent, and consistent with
 * the directory info it's derived from.
 */
void
nodelist_assert_ok(void)
{
  routerlist_t *rl = router_get_routerlist();
  networkstatus_t *ns = networkstatus_get_latest_consensus();
854
  digestmap_t *dm;
855
856
857
858

  if (!the_nodelist)
    return;

859
860
  dm = digestmap_new();

861
862
863
  /* every routerinfo in rl->routers should be in the nodelist. */
  if (rl) {
    SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) {
864
      const node_t *node = node_get_by_id(ri->cache_info.identity_digest);
865
      tor_assert(node && node->ri == ri);
866
      tor_assert(fast_memeq(ri->cache_info.identity_digest,
867
868
                             node->identity, DIGEST_LEN));
      tor_assert(! digestmap_get(dm, node->identity));
869
      digestmap_set(dm, node->identity, (void*)node);
870
871
872
873
874
875
    } SMARTLIST_FOREACH_END(ri);
  }

  /* every routerstatus in ns should be in the nodelist */
  if (ns) {
    SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
876
      const node_t *node = node_get_by_id(rs->identity_digest);
877
      tor_assert(node && node->rs == rs);
878
      tor_assert(fast_memeq(rs->identity_digest, node->identity, DIGEST_LEN));
879
      digestmap_set(dm, node->identity, (void*)node);
880
      if (ns->flavor == FLAV_MICRODESC) {
881
882
        /* If it's a microdesc consensus, every entry that has a
         * microdescriptor should be in the nodelist.
883
884
885
886
         */
        microdesc_t *md =
          microdesc_cache_lookup_by_digest256(NULL, rs->descriptor_digest);
        tor_assert(md == node->md);
887
        if (md)
888
          tor_assert(md->held_by_nodes >= 1);
889
890
891
892
893
894
895
896
897
898
899
      }
    } SMARTLIST_FOREACH_END(rs);
  }

  /* The nodelist should have no other entries, and its entries should be
   * well-formed. */
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    tor_assert(digestmap_get(dm, node->identity) != NULL);
    tor_assert(node_sl_idx == node->nodelist_idx);
  } SMARTLIST_FOREACH_END(node);

900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
  /* Every node listed with an ed25519 identity should be listed by that
   * identity.
   */
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    if (!ed25519_public_key_is_zero(&node->ed25519_id)) {
      tor_assert(node == node_get_by_ed25519_id(&node->ed25519_id));
    }
  } SMARTLIST_FOREACH_END(node);

  node_t **idx;
  HT_FOREACH(idx, nodelist_ed_map, &the_nodelist->nodes_by_ed_id) {
    node_t *node = *idx;
    tor_assert(node == node_get_by_ed25519_id(&node->ed25519_id));
  }

915
916
917
  tor_assert((long)smartlist_len(the_nodelist->nodes) ==
             (long)HT_SIZE(&the_nodelist->nodes_by_id));

918
919
920
  tor_assert((long)smartlist_len(the_nodelist->nodes) >=
             (long)HT_SIZE(&the_nodelist->nodes_by_ed_id));

921
922
923
  digestmap_free(dm, NULL);
}

924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
/** Ensure that the nodelist has been created with the most recent consensus.
 *  If that's not the case, make it so.  */
void
nodelist_ensure_freshness(networkstatus_t *ns)
{
  tor_assert(ns);

  /* We don't even have a nodelist: this is a NOP. */
  if (!the_nodelist) {
    return;
  }

  if (the_nodelist->live_consensus_valid_after != ns->valid_after) {
    log_info(LD_GENERAL, "Nodelist was not fresh: rebuilding. (%d / %d)",
             (int) the_nodelist->live_consensus_valid_after,
             (int) ns->valid_after);
    nodelist_set_consensus(ns);
  }
}
943
944
945
/** Return a list of a node_t * for every node we know about.  The caller
 * MUST NOT modify the list. (You can set and clear flags in the nodes if
 * you must, but you must not add or remove nodes.) */
946
947
MOCK_IMPL(smartlist_t *,
nodelist_get_list,(void))
948
949
950
951
952
{
  init_nodelist();
  return the_nodelist->nodes;
}

Nick Mathewson's avatar
Nick Mathewson committed
953
954
955
/** Given a hex-encoded nickname of the format DIGEST, $DIGEST, $DIGEST=name,
 * or $DIGEST~name, return the node with the matching identity digest and
 * nickname (if any).  Return NULL if no such node exists, or if <b>hex_id</b>
956
 * is not well-formed. DOCDOC flags */
957
const node_t *
958
node_get_by_hex_id(const char *hex_id, unsigned flags)
959
960
961
962
963
{
  char digest_buf[DIGEST_LEN];
  char nn_buf[MAX_NICKNAME_LEN+1];
  char nn_char='\0';

964
965
  (void) flags; // XXXX

Nick Mathewson's avatar
Nick Mathewson committed
966
  if (hex_digest_nickname_decode(hex_id, digest_buf, &nn_char, nn_buf)==0) {
967
968
969
    const node_t *node = node_get_by_id(digest_buf);
    if (!node)
      return NULL;
970
971
972
    if (nn_char == '=') {
      /* "=" indicates a Named relay, but there aren't any of those now. */
      return NULL;
973
974
975
976
    }
    return node;
  }

Nick Mathewson's avatar
Nick Mathewson committed
977
978
979
980
  return NULL;
}

/** Given a nickname (possibly verbose, possibly a hexadecimal digest), return
981
982
983
 * the corresponding node_t, or NULL if none exists. Warn the user if they
 * have specified a router by nickname, unless the NNF_NO_WARN_UNNAMED bit is
 * set in <b>flags</b>. */
984
MOCK_IMPL(const node_t *,
985
node_get_by_nickname,(const char *nickname, unsigned flags))
Nick Mathewson's avatar
Nick Mathewson committed
986
{
987
988
  const int warn_if_unnamed = !(flags & NNF_NO_WARN_UNNAMED);

Nick Mathewson's avatar
Nick Mathewson committed
989
990
991
992
  if (!the_nodelist)
    return NULL;

  /* Handle these cases: DIGEST, $DIGEST, $DIGEST=name, $DIGEST~name. */
993
994
  {
    const node_t *node;
995
    if ((node = node_get_by_hex_id(nickname, flags)) != NULL)
Nick Mathewson's avatar
Nick Mathewson committed
996
      return node;
997
  }
Nick Mathewson's avatar
Nick Mathewson committed
998

999
1000
  if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME))
    return NULL;
For faster browsing, not all history is shown. View entire blame