dns.c 54.9 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
/* Copyright 2003-2004 Roger Dingledine.
Roger Dingledine's avatar
Roger Dingledine committed
2
 * Copyright 2004-2006 Roger Dingledine, Nick Mathewson. */
3
4
/* See LICENSE for licensing information */
/* $Id$ */
5
6
const char dns_c_id[] =
  "$Id$";
7

Roger Dingledine's avatar
Roger Dingledine committed
8
9
/**
 * \file dns.c
10
 * \brief Implements a local cache for DNS results for Tor servers.
11
 * We provide two asynchronous backend implementations:
12
13
14
15
16
17
 *   1) A farm of 'DNS worker' threads or processes to perform DNS lookups for
 *      onion routers and cache the results.
 *   2) A wrapper around Adam Langley's eventdns.c code, to send requests
 *      to the nameservers asynchronously.
 * (We can't just use gethostbyname() and friends because we really need to
 * be nonblocking.)
Roger Dingledine's avatar
Roger Dingledine committed
18
 **/
19

20
#include "or.h"
21
#include "../common/ht.h"
22
23
24
#ifdef USE_EVENTDNS
#include "eventdns.h"
#endif
25

Roger Dingledine's avatar
Roger Dingledine committed
26
/** Longest hostname we're willing to resolve. */
27
28
#define MAX_ADDRESSLEN 256

Roger Dingledine's avatar
Roger Dingledine committed
29
/** Maximum DNS processes to spawn. */
30
#define MAX_DNSWORKERS 100
Roger Dingledine's avatar
Roger Dingledine committed
31
/** Minimum DNS processes to spawn. */
32
#define MIN_DNSWORKERS 3
33

Roger Dingledine's avatar
Roger Dingledine committed
34
/** If more than this many processes are idle, shut down the extras. */
35
#define MAX_IDLE_DNSWORKERS 10
36

37
38
/** How long will we wait for an answer from the resolver before we decide
 * that the resolver is wedged? */
39
40
#define RESOLVE_MAX_TIMEOUT 300

Roger Dingledine's avatar
Roger Dingledine committed
41
/** Possible outcomes from hostname lookup: permanent failure,
42
 * transient (retryable) failure, and success. */
43
44
45
46
#define DNS_RESOLVE_FAILED_TRANSIENT 1
#define DNS_RESOLVE_FAILED_PERMANENT 2
#define DNS_RESOLVE_SUCCEEDED 3

47
#ifndef USE_EVENTDNS
48
/** How many dnsworkers we have running right now. */
49
static int num_dnsworkers=0;
50
/** How many of the running dnsworkers have an assigned task right now. */
51
52
53
static int num_dnsworkers_busy=0;
/** When did we last rotate the dnsworkers? */
static time_t last_rotation_time=0;
54
55
56
57
58
59
60
61
62
#else
/** Have we currently configured nameservers with eventdns? */
static int nameservers_configured = 0;
/** What was the resolv_conf fname we last used when configuring the
 * nameservers? Used to check whether we need to reconfigure. */
static char *resolv_conf_fname = NULL;
/** What was the mtime on the resolv.conf file we last used when configuring
 * the nameservers?  Used to check whether we need to reconfigure. */
static time_t resolv_conf_mtime = 0;
63
#endif
64

Roger Dingledine's avatar
Roger Dingledine committed
65
/** Linked list of connections waiting for a DNS answer. */
66
typedef struct pending_connection_t {
67
  edge_connection_t *conn;
68
  struct pending_connection_t *next;
69
} pending_connection_t;
70

71
72
#define CACHED_RESOLVE_MAGIC 0x1234F00D

73
74
75
76
77
78
79
/* Possible states for a cached resolve_t */
/** We are waiting for the resolver system to tell us an answer here.
 * When we get one, or when we time out, the state of this cached_resolve_t
 * will become "DONE" and we'll possibly add a CACHED_VALID or a CACHED_FAILED
 * entry. This cached_resolve_t will be in the hash table so that we will
 * know not to launch more requests for this addr, but rather to add more
 * connections to the pending list for the addr. */
80
#define CACHE_STATE_PENDING 0
81
82
83
/** This used to be a pending cached_resolve_t, and we got an answer for it.
 * Now we're waiting for this cached_resolve_t to expire.  This should
 * have no pending connections, and should not appear in the hash table. */
84
#define CACHE_STATE_DONE 1
85
86
/** We are caching an answer for this address. This should have no pending
 * connections, and should appear in the hash table. */
87
#define CACHE_STATE_CACHED_VALID 2
88
89
/** We are caching a failure for this address. This should have no pending
 * connections, and should appear in the hash table */
90
91
#define CACHE_STATE_CACHED_FAILED 3

Roger Dingledine's avatar
Roger Dingledine committed
92
/** A DNS request: possibly completed, possibly pending; cached_resolve
93
 * structs are stored at the OR side in a hash table, and as a linked
94
95
 * list from oldest to newest.
 */
96
typedef struct cached_resolve_t {
97
  HT_ENTRY(cached_resolve_t) node;
98
  uint32_t magic;
99
  char address[MAX_ADDRESSLEN]; /**< The hostname to be resolved. */
100
101
102
103
  union {
    uint32_t addr;  /**< IPv4 addr for <b>address</b>. */
    char *hostname; /**< Hostname for <b>address</b> (if a reverse lookup) */
  } result;
104
  uint8_t state; /**< Is this cached entry pending/done/valid/failed? */
105
  uint8_t is_reverse; /**< Is this a reverse (addr-to-hostname) lookup? */
106
  time_t expire; /**< Remove items from cache after this time. */
107
  uint32_t ttl; /**< What TTL did the nameserver tell us? */
108
  /** Connections that want to know when we get an answer for this resolve. */
109
110
  pending_connection_t *pending_connections;
} cached_resolve_t;
111

112
static void purge_expired_resolves(time_t now);
113
114
static void dns_found_answer(const char *address, int is_reverse,
                             uint32_t addr, const char *hostname, char outcome,
115
                             uint32_t ttl);
116
static void send_resolved_cell(edge_connection_t *conn, uint8_t answer_type);
117
static int launch_resolve(edge_connection_t *exitconn);
118
#ifndef USE_EVENTDNS
119
static void dnsworkers_rotate(void);
120
static void dnsworker_main(void *data);
121
static int spawn_dnsworker(void);
122
static int spawn_enough_dnsworkers(void);
123
#else
124
static int configure_nameservers(int force);
125
static int answer_is_wildcarded(const char *ip);
126
#endif
127
#ifdef DEBUG_DNS_CACHE
128
static void _assert_cache_ok(void);
129
130
#define assert_cache_ok() _assert_cache_ok()
#else
131
#define assert_cache_ok() do {} while (0)
132
#endif
133
static void assert_resolve_ok(cached_resolve_t *resolve);
134

135
136
/** Hash table of cached_resolve objects. */
static HT_HEAD(cache_map, cached_resolve_t) cache_root;
137

Roger Dingledine's avatar
Roger Dingledine committed
138
/** Function to compare hashed resolves on their addresses; used to
139
 * implement hash tables. */
140
141
static INLINE int
cached_resolves_eq(cached_resolve_t *a, cached_resolve_t *b)
142
{
143
  /* make this smarter one day? */
144
  assert_resolve_ok(a); // Not b; b may be just a search.
145
146
147
  return !strncmp(a->address, b->address, MAX_ADDRESSLEN);
}

148
/** Hash function for cached_resolve objects */
149
150
151
152
static INLINE unsigned int
cached_resolve_hash(cached_resolve_t *a)
{
  return ht_string_hash(a->address);
153
154
}

155
HT_PROTOTYPE(cache_map, cached_resolve_t, node, cached_resolve_hash,
156
             cached_resolves_eq);
157
HT_GENERATE(cache_map, cached_resolve_t, node, cached_resolve_hash,
158
            cached_resolves_eq, 0.6, malloc, realloc, free);
159

160
/** Initialize the DNS cache. */
161
static void
162
init_cache_map(void)
163
{
164
  HT_INIT(&cache_root);
165
166
}

167
#ifdef USE_EVENTDNS
168
/** Helper: called by eventdns when eventdns wants to log something. */
169
static void
170
eventdns_log_cb(int warn, const char *msg)
171
{
172
173
174
175
  if (!strcmpstart(msg, "Resolve requested for") &&
      get_options()->SafeLogging) {
    log(LOG_INFO, LD_EXIT, "eventdns: Resolve requested.");
    return;
176
177
  } else if (!strcmpstart(msg, "Search: ")) {
    return;
178
  }
179
  log(warn?LOG_WARN:LOG_INFO, LD_EXIT, "eventdns: %s", msg);
180
181
182
}
#endif

Roger Dingledine's avatar
Roger Dingledine committed
183
/** Initialize the DNS subsystem; called by the OR process. */
184
int
185
186
dns_init(void)
{
187
  init_cache_map();
188
#ifdef USE_EVENTDNS
189
  if (server_mode(get_options()))
190
191
192
    return configure_nameservers(1);
#else
  dnsworkers_rotate();
193
#endif
194
  return 0;
195
}
196

197
/** Called when DNS-related options change (or may have changed) */
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
void
dns_reset(void)
{
#ifdef USE_EVENTDNS
  or_options_t *options = get_options();
  if (! server_mode(options)) {
    eventdns_clear_nameservers_and_suspend();
    eventdns_search_clear();
    nameservers_configured = 0;
    tor_free(resolv_conf_fname);
    resolv_conf_mtime = 0;
  } else {
    if (configure_nameservers(0) < 0)
      /* XXXX */
      return;
  }
#else
  dnsworkers_rotate();
#endif
}

219
220
/** Helper: Given a TTL from a DNS response, determine what TTL to give the
 * OP that asked us to resolve it. */
221
222
223
224
225
226
227
228
229
230
231
uint32_t
dns_clip_ttl(uint32_t ttl)
{
  if (ttl < MIN_DNS_TTL)
    return MIN_DNS_TTL;
  else if (ttl > MAX_DNS_TTL)
    return MAX_DNS_TTL;
  else
    return ttl;
}

232
233
/** Helper: Given a TTL from a DNS response, determine how long to hold it in
 * our cache. */
234
235
236
237
238
239
240
241
242
243
244
static uint32_t
dns_get_expiry_ttl(uint32_t ttl)
{
  if (ttl < MIN_DNS_TTL)
    return MIN_DNS_TTL;
  else if (ttl > MAX_DNS_ENTRY_AGE)
    return MAX_DNS_ENTRY_AGE;
  else
    return ttl;
}

245
/** Helper: free storage held by an entry in the DNS cache. */
246
static void
247
_free_cached_resolve(cached_resolve_t *r)
248
{
Nick Mathewson's avatar
Nick Mathewson committed
249
  while (r->pending_connections) {
250
    pending_connection_t *victim = r->pending_connections;
251
252
253
    r->pending_connections = victim->next;
    tor_free(victim);
  }
254
255
  if (r->is_reverse)
    tor_free(r->result.hostname);
256
  r->magic = 0xFF00FF00;
257
258
259
  tor_free(r);
}

260
261
262
/** Compare two cached_resolve_t pointers by expiry time, and return
 * less-than-zero, zero, or greater-than-zero as appropriate. Used for
 * the priority queue implementation. */
263
static int
264
_compare_cached_resolves_by_expiry(const void *_a, const void *_b)
265
{
266
  const cached_resolve_t *a = _a, *b = _b;
267
  return a->expire - b->expire;
268
269
}

270
271
/** Priority queue of cached_resolve_t objects to let us know when they
 * will expire. */
272
273
static smartlist_t *cached_resolve_pqueue = NULL;

274
275
/** Set an expiry time for a cached_resolve_t, and add it to the expiry
 * priority queue */
276
277
278
279
static void
set_expiry(cached_resolve_t *resolve, time_t expires)
{
  tor_assert(resolve && resolve->expire == 0);
280
281
  if (!cached_resolve_pqueue)
    cached_resolve_pqueue = smartlist_create();
282
283
284
285
286
287
  resolve->expire = expires;
  smartlist_pqueue_add(cached_resolve_pqueue,
                       _compare_cached_resolves_by_expiry,
                       resolve);
}

288
/** Free all storage held in the DNS cache and related structures. */
289
290
291
void
dns_free_all(void)
{
292
  cached_resolve_t **ptr, **next, *item;
293
  for (ptr = HT_START(cache_map, &cache_root); ptr != NULL; ptr = next) {
294
    item = *ptr;
295
    next = HT_NEXT_RMV(cache_map, &cache_root, ptr);
296
    _free_cached_resolve(item);
297
  }
298
  HT_CLEAR(cache_map, &cache_root);
299
300
  if (cached_resolve_pqueue)
    smartlist_free(cached_resolve_pqueue);
301
  cached_resolve_pqueue = NULL;
302
303
304
#ifdef USE_EVENTDNS
  tor_free(resolv_conf_fname);
#endif
305
306
}

Nick Mathewson's avatar
Nick Mathewson committed
307
/** Remove every cached_resolve whose <b>expire</b> time is before <b>now</b>
308
 * from the cache. */
309
static void
310
purge_expired_resolves(time_t now)
311
{
Nick Mathewson's avatar
Nick Mathewson committed
312
  cached_resolve_t *resolve, *removed;
313
  pending_connection_t *pend;
314
  edge_connection_t *pendconn;
315

Nick Mathewson's avatar
Nick Mathewson committed
316
  assert_cache_ok();
317
318
319
320
321
322
323
324
325
326
  if (!cached_resolve_pqueue)
    return;

  while (smartlist_len(cached_resolve_pqueue)) {
    resolve = smartlist_get(cached_resolve_pqueue, 0);
    if (resolve->expire > now)
      break;
    smartlist_pqueue_pop(cached_resolve_pqueue,
                         _compare_cached_resolves_by_expiry);

327
    if (resolve->state == CACHE_STATE_PENDING) {
328
      log_debug(LD_EXIT,
329
330
                "Expiring a dns resolve %s that's still pending. Forgot to "
                "cull it? DNS resolve didn't tell us about the timeout?",
331
332
333
334
335
336
337
338
339
340
341
                escaped_safe_str(resolve->address));
    } else if (resolve->state == CACHE_STATE_CACHED_VALID ||
               resolve->state == CACHE_STATE_CACHED_FAILED) {
      log_debug(LD_EXIT,
                "Forgetting old cached resolve (address %s, expires %lu)",
                escaped_safe_str(resolve->address),
                (unsigned long)resolve->expire);
      tor_assert(!resolve->pending_connections);
    } else {
      tor_assert(resolve->state == CACHE_STATE_DONE);
      tor_assert(!resolve->pending_connections);
342
    }
343

344
    if (resolve->pending_connections) {
345
      log_debug(LD_EXIT,
346
                "Closing pending connections on timed-out DNS resolve!");
347
      tor_fragile_assert();
348
349
350
351
      while (resolve->pending_connections) {
        pend = resolve->pending_connections;
        resolve->pending_connections = pend->next;
        /* Connections should only be pending if they have no socket. */
352
        tor_assert(pend->conn->_base.s == -1);
353
        pendconn = pend->conn;
354
        connection_edge_end(pendconn, END_STREAM_REASON_TIMEOUT,
355
                            pendconn->cpath_layer);
356
        circuit_detach_stream(circuit_get_by_edge_conn(pendconn), pendconn);
357
        connection_free(TO_CONN(pendconn));
358
359
        tor_free(pend);
      }
360
    }
361

362
363
364
365
366
367
368
    if (resolve->state == CACHE_STATE_CACHED_VALID ||
        resolve->state == CACHE_STATE_CACHED_FAILED ||
        resolve->state == CACHE_STATE_PENDING) {
      removed = HT_REMOVE(cache_map, &cache_root, resolve);
      if (removed != resolve) {
        log_err(LD_BUG, "The expired resolve we purged didn't match any in"
                " the cache. Tried to purge %s (%p); instead got %s (%p).",
369
370
                resolve->address, (void*)resolve,
                removed ? removed->address : "NULL", (void*)remove);
371
372
      }
      tor_assert(removed == resolve);
373
374
      if (resolve->is_reverse)
        tor_free(resolve->result.hostname);
375
376
377
      resolve->magic = 0xF0BBF0BB;
      tor_free(resolve);
    } else {
378
      /* This should be in state DONE. Make sure it's not in the cache. */
379
380
      cached_resolve_t *tmp = HT_FIND(cache_map, &cache_root, resolve);
      tor_assert(tmp != resolve);
381
    }
382
  }
383

Nick Mathewson's avatar
Nick Mathewson committed
384
  assert_cache_ok();
385
386
}

Roger Dingledine's avatar
Roger Dingledine committed
387
/** Send a response to the RESOLVE request of a connection. answer_type must
388
389
 *  be one of RESOLVED_TYPE_(IPV4|ERROR|ERROR_TRANSIENT) */
static void
390
send_resolved_cell(edge_connection_t *conn, uint8_t answer_type)
391
392
{
  char buf[RELAY_PAYLOAD_SIZE];
393
  size_t buflen;
394
  uint32_t ttl;
395
396

  buf[0] = answer_type;
397
  ttl = dns_clip_ttl(conn->address_ttl);
398
399
400
401
402

  switch (answer_type)
    {
    case RESOLVED_TYPE_IPV4:
      buf[1] = 4;
403
      set_uint32(buf+2, htonl(conn->_base.addr));
404
      set_uint32(buf+6, htonl(ttl));
405
      buflen = 10;
406
407
408
      break;
    case RESOLVED_TYPE_ERROR_TRANSIENT:
    case RESOLVED_TYPE_ERROR:
409
410
411
      {
        const char *errmsg = "Error resolving hostname";
        int msglen = strlen(errmsg);
412

413
414
        buf[1] = msglen;
        strlcpy(buf+2, errmsg, sizeof(buf)-2);
415
        set_uint32(buf+2+msglen, htonl(ttl));
416
417
418
        buflen = 6+msglen;
        break;
      }
419
420
    default:
      tor_assert(0);
421
      return;
422
    }
423
  connection_edge_send_command(conn, circuit_get_by_edge_conn(conn),
424
425
426
427
                               RELAY_COMMAND_RESOLVED, buf, buflen,
                               conn->cpath_layer);
}

428
429
430
431
432
433
434
435
436
437
438
439
440
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
487
488
489
490
491
492
493
494
495
/** Send a response to the RESOLVE request of a connection for an in-addr.arpa
 * address on connection <b>conn</b> which yielded the result <b>hostname</b>.
 * The answer type will be RESOLVED_HOSTNAME.
 */
static void
send_resolved_hostname_cell(edge_connection_t *conn, const char *hostname)
{
  char buf[RELAY_PAYLOAD_SIZE];
  size_t buflen;
  uint32_t ttl;
  size_t namelen = strlen(hostname);

  tor_assert(namelen < 256);
  ttl = dns_clip_ttl(conn->address_ttl);

  buf[0] = RESOLVED_TYPE_HOSTNAME;
  buf[1] = (uint8_t)namelen;
  memcpy(buf+2, hostname, namelen);
  set_uint32(buf+2+namelen, htonl(ttl));
  buflen = 2+namelen+4;

  connection_edge_send_command(conn, circuit_get_by_edge_conn(conn),
                               RELAY_COMMAND_RESOLVED, buf, buflen,
                               conn->cpath_layer);
}

/** Given a lower-case <b>address</b>, check to see whether it's a
 * 1.2.3.4.in-addr.arpa address used for reverse lookups.  If so,
 * parse it and place the address in <b>in</b> if present. Return 1 on success;
 * 0 if the address is not in in-addr.arpa format, and -1 if the address is
 * malformed. */
static int
parse_inaddr_arpa_address(const char *address, struct in_addr *in)
{
  char buf[INET_NTOA_BUF_LEN];
  char *cp;
  size_t len;
  struct in_addr inaddr;

  cp = strstr(address, ".in-addr.arpa");
  if (!cp || *(cp+strlen(".in-addr.arpa")))
    return 0; /* not an .in-addr.arpa address  */

  len = cp - address;

  if (len >= INET_NTOA_BUF_LEN)
    return -1; /* Too long. */

  memcpy(buf, cp, len);
  buf[len] = '\0';
  if (tor_inet_aton(buf, &inaddr) == 0)
    return -1; /* malformed. */

  if (in) {
    uint32_t a;
    /* reverse the bytes */
    a = (  ((inaddr.s_addr & 0x000000fful) << 24)
          |((inaddr.s_addr & 0x0000ff00ul) << 8)
          |((inaddr.s_addr & 0x00ff0000ul) >> 8)
          |((inaddr.s_addr & 0xff000000ul) >> 24));
    inaddr.s_addr = a;

    memcpy(in, &inaddr, sizeof(inaddr));
  }

  return 1;
}

Nick Mathewson's avatar
Nick Mathewson committed
496
497
/** See if we have a cache entry for <b>exitconn</b>-\>address. if so,
 * if resolve valid, put it into <b>exitconn</b>-\>addr and return 1.
498
 * If resolve failed, unlink exitconn if needed, free it, and return -1.
499
500
501
502
503
504
505
 *
 * Else, if seen before and pending, add conn to the pending list,
 * and return 0.
 *
 * Else, if not seen before, add conn to pending list, hand to
 * dns farm, and return 0.
 */
506
int
507
dns_resolve(edge_connection_t *exitconn)
508
{
509
510
511
  cached_resolve_t *resolve;
  cached_resolve_t search;
  pending_connection_t *pending_connection;
512
  circuit_t *circ;
513
  struct in_addr in;
514
  time_t now = time(NULL);
515
  int is_reverse = 0, is_resolve, r;
516
517
  assert_connection_ok(TO_CONN(exitconn), 0);
  tor_assert(exitconn->_base.s == -1);
518

519
520
  assert_cache_ok();

521
522
  is_resolve = exitconn->_base.purpose = EXIT_PURPOSE_RESOLVE;

523
  /* first check if exitconn->_base.address is an IP. If so, we already
524
   * know the answer. */
525
526
  if (tor_inet_aton(exitconn->_base.address, &in) != 0) {
    exitconn->_base.addr = ntohl(in.s_addr);
527
    exitconn->address_ttl = DEFAULT_DNS_TTL;
528
    if (is_resolve)
529
      send_resolved_cell(exitconn, RESOLVED_TYPE_IPV4);
530
    return 1;
531
532
533
  }

  /* then take this opportunity to see if there are any expired
534
   * resolves in the hash table. */
535
  purge_expired_resolves(now);
536

537
538
  /* lower-case exitconn->_base.address, so it's in canonical form */
  tor_strlower(exitconn->_base.address);
539

540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
  /* Check whether this is a reverse lookup.  If it's malformed, or it's a
   * .in-addr.arpa address but this isn't a resolve request, kill the
   * connecction.
   */
  if ((r = parse_inaddr_arpa_address(exitconn->_base.address, NULL)) != 0) {
    if (r == 1)
      is_reverse = 1;

#ifdef USE_EVENTDNS
    if (!is_reverse || !is_resolve) {
      if (!is_reverse)
        log_info(LD_EXIT, "Bad .in-addr.arpa address \"%s\"; sending error.",
                 escaped_safe_str(exitconn->_base.address));
      else if (!is_resolve)
        log_info(LD_EXIT,
                 "Attempt to connect to a .in-addr.arpa address \"%s\"; "
                 "sending error.",
                 escaped_safe_str(exitconn->_base.address));
#else
    if (1) {
      log_info(LD_PROTOCOL, "Dnsworker code does not support in-addr.arpa "
               "domain, but received a request for \"%s\"; sending error.",
               escaped_safe_str(exitconn->_base.address));
#endif

      if (exitconn->_base.purpose == EXIT_PURPOSE_RESOLVE)
        send_resolved_cell(exitconn, RESOLVED_TYPE_ERROR);
      circ = circuit_get_by_edge_conn(exitconn);
      if (circ)
        circuit_detach_stream(circ, exitconn);
      if (!exitconn->_base.marked_for_close)
        connection_free(TO_CONN(exitconn));
      return -1;
    }
  }

576
  /* now check the hash table to see if 'address' is already there. */
577
  strlcpy(search.address, exitconn->_base.address, sizeof(search.address));
578
  resolve = HT_FIND(cache_map, &cache_root, &search);
579
  if (resolve && resolve->expire > now) { /* already there */
580
    switch (resolve->state) {
581
582
      case CACHE_STATE_PENDING:
        /* add us to the pending list */
583
        pending_connection = tor_malloc_zero(
584
                                      sizeof(pending_connection_t));
585
        pending_connection->conn = exitconn;
Roger Dingledine's avatar
   
Roger Dingledine committed
586
587
        pending_connection->next = resolve->pending_connections;
        resolve->pending_connections = pending_connection;
588
        log_debug(LD_EXIT,"Connection (fd %d) waiting for pending DNS "
589
590
                  "resolve of %s", exitconn->_base.s,
                  escaped_safe_str(exitconn->_base.address));
591
        exitconn->_base.state = EXIT_CONN_STATE_RESOLVING;
Roger Dingledine's avatar
   
Roger Dingledine committed
592
        return 0;
593
      case CACHE_STATE_CACHED_VALID:
594
        log_debug(LD_EXIT,"Connection (fd %d) found cached answer for %s",
595
                  exitconn->_base.s,
596
597
598
599
600
601
602
603
604
605
                  escaped_safe_str(resolve->address));
        exitconn->address_ttl = resolve->ttl;
        if (resolve->is_reverse) {
          tor_assert(is_resolve);
          send_resolved_hostname_cell(exitconn, resolve->result.hostname);
        } else {
          exitconn->_base.addr = resolve->result.addr;
          if (is_resolve)
            send_resolved_cell(exitconn, RESOLVED_TYPE_IPV4);
        }
606
        return 1;
607
      case CACHE_STATE_CACHED_FAILED:
608
        log_debug(LD_EXIT,"Connection (fd %d) found cached error for %s",
609
610
                  exitconn->_base.s,
                  escaped_safe_str(exitconn->_base.address));
611
        if (is_resolve)
612
          send_resolved_cell(exitconn, RESOLVED_TYPE_ERROR);
613
        circ = circuit_get_by_edge_conn(exitconn);
614
615
        if (circ)
          circuit_detach_stream(circ, exitconn);
616
617
        if (!exitconn->_base.marked_for_close)
          connection_free(TO_CONN(exitconn));
618
        return -1;
619
620
621
      case CACHE_STATE_DONE:
        log_err(LD_BUG, "Found a 'DONE' dns resolve still in the cache.");
        tor_fragile_assert();
622
    }
Roger Dingledine's avatar
Roger Dingledine committed
623
    tor_assert(0);
Roger Dingledine's avatar
Roger Dingledine committed
624
625
  }
  /* not there, need to add it */
626
  resolve = tor_malloc_zero(sizeof(cached_resolve_t));
627
  resolve->magic = CACHED_RESOLVE_MAGIC;
Roger Dingledine's avatar
Roger Dingledine committed
628
  resolve->state = CACHE_STATE_PENDING;
629
  resolve->is_reverse = is_reverse;
630
  strlcpy(resolve->address, exitconn->_base.address, sizeof(resolve->address));
Roger Dingledine's avatar
Roger Dingledine committed
631

632
  /* add this connection to the pending list */
633
  pending_connection = tor_malloc_zero(sizeof(pending_connection_t));
Roger Dingledine's avatar
Roger Dingledine committed
634
635
  pending_connection->conn = exitconn;
  resolve->pending_connections = pending_connection;
636
  exitconn->_base.state = EXIT_CONN_STATE_RESOLVING;
Roger Dingledine's avatar
Roger Dingledine committed
637

638
  /* Add this resolve to the cache and priority queue. */
639
  HT_INSERT(cache_map, &cache_root, resolve);
640
  set_expiry(resolve, now + RESOLVE_MAX_TIMEOUT);
641

642
  log_debug(LD_EXIT,"Launching %s.",
643
            escaped_safe_str(exitconn->_base.address));
644
  assert_cache_ok();
645
  return launch_resolve(exitconn);
646
647
}

648
/** Log an error and abort if conn is waiting for a DNS resolve.
649
 */
650
void
651
assert_connection_edge_not_dns_pending(edge_connection_t *conn)
652
{
653
654
  pending_connection_t *pend;
  cached_resolve_t **resolve;
655

656
657
658
659
660
661
  HT_FOREACH(resolve, cache_map, &cache_root) {
    for (pend = (*resolve)->pending_connections;
         pend;
         pend = pend->next) {
      tor_assert(pend->conn != conn);
    }
662
  }
663
}
664

665
666
667
668
669
670
671
/** Log an error and abort if any connection waiting for a DNS resolve is
 * corrupted. */
void
assert_all_pending_dns_resolves_ok(void)
{
  pending_connection_t *pend;
  cached_resolve_t **resolve;
672

673
674
675
676
  HT_FOREACH(resolve, cache_map, &cache_root) {
    for (pend = (*resolve)->pending_connections;
         pend;
         pend = pend->next) {
677
678
679
      assert_connection_ok(TO_CONN(pend->conn), 0);
      tor_assert(pend->conn->_base.s == -1);
      tor_assert(!connection_in_array(TO_CONN(pend->conn)));
680
    }
681
682
683
  }
}

Nick Mathewson's avatar
Nick Mathewson committed
684
/** Remove <b>conn</b> from the list of connections waiting for conn-\>address.
685
 */
686
void
687
connection_dns_remove(edge_connection_t *conn)
688
{
689
690
691
  pending_connection_t *pend, *victim;
  cached_resolve_t search;
  cached_resolve_t *resolve;
692

693
694
  tor_assert(conn->_base.type == CONN_TYPE_EXIT);
  tor_assert(conn->_base.state == EXIT_CONN_STATE_RESOLVING);
695

696
  strlcpy(search.address, conn->_base.address, sizeof(search.address));
697

698
  resolve = HT_FIND(cache_map, &cache_root, &search);
699
  if (!resolve) {
700
    log_notice(LD_BUG, "Address %s is not pending. Dropping.",
701
               escaped_safe_str(conn->_base.address));
702
703
704
    return;
  }

Roger Dingledine's avatar
Roger Dingledine committed
705
  tor_assert(resolve->pending_connections);
706
  assert_connection_ok(TO_CONN(conn),0);
707
708
709

  pend = resolve->pending_connections;

710
  if (pend->conn == conn) {
711
    resolve->pending_connections = pend->next;
712
    tor_free(pend);
713
    log_debug(LD_EXIT, "First connection (fd %d) no longer waiting "
714
              "for resolve of %s",
715
              conn->_base.s, escaped_safe_str(conn->_base.address));
716
717
    return;
  } else {
718
719
    for ( ; pend->next; pend = pend->next) {
      if (pend->next->conn == conn) {
720
721
        victim = pend->next;
        pend->next = victim->next;
722
        tor_free(victim);
723
        log_debug(LD_EXIT,
724
                  "Connection (fd %d) no longer waiting for resolve of %s",
725
                  conn->_base.s, escaped_safe_str(conn->_base.address));
726
727
728
        return; /* more are pending */
      }
    }
Roger Dingledine's avatar
Roger Dingledine committed
729
    tor_assert(0); /* not reachable unless onlyconn not in pending list */
730
731
732
  }
}

Nick Mathewson's avatar
Nick Mathewson committed
733
734
735
/** Mark all connections waiting for <b>address</b> for close.  Then cancel
 * the resolve for <b>address</b> itself, and remove any cached results for
 * <b>address</b> from the cache.
736
 */
737
void
738
dns_cancel_pending_resolve(const char *address)
739
{
740
741
  pending_connection_t *pend;
  cached_resolve_t search;
742
  cached_resolve_t *resolve, *tmp;
743
  edge_connection_t *pendconn;
744
  circuit_t *circ;
745

Nick Mathewson's avatar
Nick Mathewson committed
746
  strlcpy(search.address, address, sizeof(search.address));
747

748
  resolve = HT_FIND(cache_map, &cache_root, &search);
749
  if (!resolve || resolve->state != CACHE_STATE_PENDING) {
750
751
    log_notice(LD_BUG,"Address %s is not pending. Dropping.",
               escaped_safe_str(address));
752
753
754
    return;
  }

755
756
  if (!resolve->pending_connections) {
    /* XXX this should never trigger, but sometimes it does */
757
    log_warn(LD_BUG,
758
759
             "Bug: Address %s is pending but has no pending connections!",
             escaped_safe_str(address));
760
    tor_fragile_assert();
761
762
    return;
  }
Roger Dingledine's avatar
Roger Dingledine committed
763
  tor_assert(resolve->pending_connections);
764

765
  /* mark all pending connections to fail */
766
  log_debug(LD_EXIT,
767
768
             "Failing all connections waiting on DNS resolve of %s",
             escaped_safe_str(address));
769
  while (resolve->pending_connections) {
770
    pend = resolve->pending_connections;
771
    pend->conn->_base.state = EXIT_CONN_STATE_RESOLVEFAILED;
772
    pendconn = pend->conn;
773
774
775
    assert_connection_ok(TO_CONN(pendconn), 0);
    tor_assert(pendconn->_base.s == -1);
    if (!pendconn->_base.marked_for_close) {
776
777
      connection_edge_end(pendconn, END_STREAM_REASON_RESOURCELIMIT,
                          pendconn->cpath_layer);
778
    }
779
    circ = circuit_get_by_edge_conn(pendconn);
780
781
    if (circ)
      circuit_detach_stream(circ, pendconn);
782
    connection_free(TO_CONN(pendconn));
783
784
    resolve->pending_connections = pend->next;
    tor_free(pend);
785
786
  }

Nick Mathewson's avatar
Nick Mathewson committed
787
  tmp = HT_REMOVE(cache_map, &cache_root, resolve);
788
789
790
  if (tmp != resolve) {
    log_err(LD_BUG, "The cancelled resolve we purged didn't match any in"
            " the cache. Tried to purge %s (%p); instead got %s (%p).",
791
792
            resolve->address, (void*)resolve,
            tmp ? tmp->address : "NULL", (void*)tmp);
793
  }
Nick Mathewson's avatar
Nick Mathewson committed
794
  tor_assert(tmp == resolve);
795
796

  resolve->state = CACHE_STATE_DONE;
797
798
}

799
/** Helper: adds an entry to the DNS cache mapping <b>address</b> to the ipv4
800
801
 * address <b>addr</b> (if is_reverse is 0) or the hostname <b>hostname</b> if
 * (is_reverse is 1).  <b>ttl</b> is a cache ttl; <b>outcome</b> is one of
802
803
 * DNS_RESOLVE_{FAILED_TRANSIENT|FAILED_PERMANENT|SUCCEEDED}.
 **/
804
static void
805
806
add_answer_to_cache(const char *address, int is_reverse, uint32_t addr,
                    const char *hostname, char outcome, uint32_t ttl)
807
808
809
810
811
812
813
814
815
816
{
  cached_resolve_t *resolve;
  if (outcome == DNS_RESOLVE_FAILED_TRANSIENT)
    return;

  resolve = tor_malloc_zero(sizeof(cached_resolve_t));
  resolve->magic = CACHED_RESOLVE_MAGIC;
  resolve->state = (outcome == DNS_RESOLVE_SUCCEEDED) ?
    CACHE_STATE_CACHED_VALID : CACHE_STATE_CACHED_FAILED;
  strlcpy(resolve->address, address, sizeof(resolve->address));
817
818
819
820
821
822
823
  if (is_reverse) {
    tor_assert(hostname);
    resolve->result.hostname = tor_strdup(hostname);
  } else {
    tor_assert(!hostname);
    resolve->result.addr = addr;
  }
824
825
826
827
828
829
  resolve->ttl = ttl;
  assert_resolve_ok(resolve);
  HT_INSERT(cache_map, &cache_root, resolve);
  set_expiry(resolve, time(NULL) + dns_get_expiry_ttl(ttl));
}

830
831
832
833
834
/** Called on the OR side when a DNS worker or the eventdns library tells us
 * the outcome of a DNS resolve: tell all pending connections about the result
 * of the lookup, and cache the value.  (<b>address</b> is a NUL-terminated
 * string containing the address to look up; <b>addr</b> is an IPv4 address in
 * host order; <b>outcome</b> is one of
Nick Mathewson's avatar
Nick Mathewson committed
835
 * DNS_RESOLVE_{FAILED_TRANSIENT|FAILED_PERMANENT|SUCCEEDED}.
836
 */
837
static void
838
839
dns_found_answer(const char *address, int is_reverse, uint32_t addr,
                 const char *hostname, char outcome, uint32_t ttl)
840
{
841
842
  pending_connection_t *pend;
  cached_resolve_t search;
843
  cached_resolve_t *resolve, *removed;
844
  edge_connection_t *pendconn;
845
  circuit_t *circ;
846

847
848
  assert_cache_ok();

Nick Mathewson's avatar
Nick Mathewson committed
849
  strlcpy(search.address, address, sizeof(search.address));
850

851
  resolve = HT_FIND(cache_map, &cache_root, &search);
852
  if (!resolve) {
853
854
    log_info(LD_EXIT,"Resolved unasked address %s; caching anyway.",
             escaped_safe_str(address));
855
    add_answer_to_cache(address, is_reverse, addr, hostname, outcome, ttl);
856
    return;
857
  }
858
  assert_resolve_ok(resolve);
859

860
  if (resolve->state != CACHE_STATE_PENDING) {
861
862
    /* XXXX Maybe update addr? or check addr for consistency? Or let
     * VALID replace FAILED? */
863
864
    log_notice(LD_EXIT, "Resolved %s which was already resolved; ignoring",
               escaped_safe_str(address));
Roger Dingledine's avatar
Roger Dingledine committed
865
    tor_assert(resolve->pending_connections == NULL);
866
867
868
869
870
871
    return;
  }
  /* Removed this assertion: in fact, we'll sometimes get a double answer
   * to the same question.  This can happen when we ask one worker to resolve
   * X.Y.Z., then we cancel the request, and then we ask another worker to
   * resolve X.Y.Z. */
Roger Dingledine's avatar
Roger Dingledine committed
872
  /* tor_assert(resolve->state == CACHE_STATE_PENDING); */
873

874
  while (resolve->pending_connections) {
875
    pend = resolve->pending_connections;
876
877
    pendconn = pend->conn; /* don't pass complex things to the
                              connection_mark_for_close macro */
878
    assert_connection_ok(TO_CONN(pendconn),time(NULL));
879
880
    pendconn->_base.addr = addr;
    pendconn->address_ttl = ttl;
881

882
    if (outcome != DNS_RESOLVE_SUCCEEDED) {
883
      /* prevent double-remove. */
884
885
      pendconn->_base.state = EXIT_CONN_STATE_RESOLVEFAILED;
      if (pendconn->_base.purpose == EXIT_PURPOSE_CONNECT) {
886
887
        connection_edge_end(pendconn, END_STREAM_REASON_RESOLVEFAILED,
                            pendconn->cpath_layer);
888
        /* This detach must happen after we send the end cell. */
889
        circuit_detach_stream(circuit_get_by_edge_conn(pendconn), pendconn);
890
      } else {
891
        send_resolved_cell(pendconn, RESOLVED_TYPE_ERROR);