dns.c 55.4 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
  // log_notice(LD_EXIT, "Sending a regular RESOLVED reply: ");
424
  connection_edge_send_command(conn, circuit_get_by_edge_conn(conn),
425
426
427
428
                               RELAY_COMMAND_RESOLVED, buf, buflen,
                               conn->cpath_layer);
}

429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
/** 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;

450
  // log_notice(LD_EXIT, "Sending a reply RESOLVED reply: %s", hostname);
451
452
453
  connection_edge_send_command(conn, circuit_get_by_edge_conn(conn),
                               RELAY_COMMAND_RESOLVED, buf, buflen,
                               conn->cpath_layer);
454
  // log_notice(LD_EXIT, "Sent");
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
}

/** 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. */

479
  memcpy(buf, address, len);
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
  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
499
500
/** 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.
501
 * If resolve failed, unlink exitconn if needed, free it, and return -1.
502
503
504
505
506
507
508
 *
 * 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.
 */
509
int
510
dns_resolve(edge_connection_t *exitconn)
511
{
512
513
514
  cached_resolve_t *resolve;
  cached_resolve_t search;
  pending_connection_t *pending_connection;
515
  circuit_t *circ;
516
  struct in_addr in;
517
  time_t now = time(NULL);
518
  int is_reverse = 0, is_resolve, r;
519
520
  assert_connection_ok(TO_CONN(exitconn), 0);
  tor_assert(exitconn->_base.s == -1);
521

522
523
  assert_cache_ok();

524
  is_resolve = exitconn->_base.purpose == EXIT_PURPOSE_RESOLVE;
525

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

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

540
541
  /* lower-case exitconn->_base.address, so it's in canonical form */
  tor_strlower(exitconn->_base.address);
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
576
  /* 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;
    }
577
578
    //log_notice(LD_EXIT, "Looks like an address %s",
//	exitconn->_base.address);
579
580
  }

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

637
  /* add this connection to the pending list */
638
  pending_connection = tor_malloc_zero(sizeof(pending_connection_t));
Roger Dingledine's avatar
Roger Dingledine committed
639
640
  pending_connection->conn = exitconn;
  resolve->pending_connections = pending_connection;
641
  exitconn->_base.state = EXIT_CONN_STATE_RESOLVING;
Roger Dingledine's avatar
Roger Dingledine committed
642

643
  /* Add this resolve to the cache and priority queue. */
644
  HT_INSERT(cache_map, &cache_root, resolve);
645
  set_expiry(resolve, now + RESOLVE_MAX_TIMEOUT);
646

647
  log_debug(LD_EXIT,"Launching %s.",
648
            escaped_safe_str(exitconn->_base.address));
649
  assert_cache_ok();
650
  return launch_resolve(exitconn);
651
652
}

653
/** Log an error and abort if conn is waiting for a DNS resolve.
654
 */
655
void
656
assert_connection_edge_not_dns_pending(edge_connection_t *conn)
657
{
658
659
  pending_connection_t *pend;
  cached_resolve_t **resolve;
660

661
662
663
664
665
666
  HT_FOREACH(resolve, cache_map, &cache_root) {
    for (pend = (*resolve)->pending_connections;
         pend;
         pend = pend->next) {
      tor_assert(pend->conn != conn);
    }
667
  }
668
}
669

670
671
672
673
674
675
676
/** 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;
677

678
679
680
681
  HT_FOREACH(resolve, cache_map, &cache_root) {
    for (pend = (*resolve)->pending_connections;
         pend;
         pend = pend->next) {
682
683
684
      assert_connection_ok(TO_CONN(pend->conn), 0);
      tor_assert(pend->conn->_base.s == -1);
      tor_assert(!connection_in_array(TO_CONN(pend->conn)));
685
    }
686
687
688
  }
}

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

698
699
  tor_assert(conn->_base.type == CONN_TYPE_EXIT);
  tor_assert(conn->_base.state == EXIT_CONN_STATE_RESOLVING);
700

701
  strlcpy(search.address, conn->_base.address, sizeof(search.address));
702

703
  resolve = HT_FIND(cache_map, &cache_root, &search);
704
  if (!resolve) {
705
    log_notice(LD_BUG, "Address %s is not pending. Dropping.",
706
               escaped_safe_str(conn->_base.address));
707
708
709
    return;
  }

Roger Dingledine's avatar
Roger Dingledine committed
710
  tor_assert(resolve->pending_connections);
711
  assert_connection_ok(TO_CONN(conn),0);
712
713
714

  pend = resolve->pending_connections;

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

Nick Mathewson's avatar
Nick Mathewson committed
738
739
740
/** 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.
741
 */
742
void
743
dns_cancel_pending_resolve(const char *address)
744
{
745
746
  pending_connection_t *pend;
  cached_resolve_t search;
747
  cached_resolve_t *resolve, *tmp;
748
  edge_connection_t *pendconn;
749
  circuit_t *circ;
750

Nick Mathewson's avatar
Nick Mathewson committed
751
  strlcpy(search.address, address, sizeof(search.address));
752

753
  resolve = HT_FIND(cache_map, &cache_root, &search);
754
  if (!resolve || resolve->state != CACHE_STATE_PENDING) {
755
756
    log_notice(LD_BUG,"Address %s is not pending. Dropping.",
               escaped_safe_str(address));
757
758
759
    return;
  }

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

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

Nick Mathewson's avatar
Nick Mathewson committed
792
  tmp = HT_REMOVE(cache_map, &cache_root, resolve);
793
794
795
  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).",
796
797
            resolve->address, (void*)resolve,
            tmp ? tmp->address : "NULL", (void*)tmp);
798
  }
Nick Mathewson's avatar
Nick Mathewson committed
799
  tor_assert(tmp == resolve);
800
801

  resolve->state = CACHE_STATE_DONE;
802
803
}

804
/** Helper: adds an entry to the DNS cache mapping <b>address</b> to the ipv4
805
806
 * 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
807
808
 * DNS_RESOLVE_{FAILED_TRANSIENT|FAILED_PERMANENT|SUCCEEDED}.
 **/
809
static void
810
811
add_answer_to_cache(const char *address, int is_reverse, uint32_t addr,
                    const char *hostname, char outcome, uint32_t ttl)
812
813
814
815
816
{
  cached_resolve_t *resolve;
  if (outcome == DNS_RESOLVE_FAILED_TRANSIENT)
    return;

817
818
819
820
  //log_notice(LD_EXIT, "Adding to cache: %s -> %s (%lx, %s), %d",
  //           address, is_reverse?"(reverse)":"", (unsigned long)addr,
  //           hostname?hostname:"NULL",(int)outcome);

821
822
823
824
825
  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));
826
  resolve->is_reverse = is_reverse;
827
828
829
830
831
832
833
  if (is_reverse) {
    tor_assert(hostname);
    resolve->result.hostname = tor_strdup(hostname);
  } else {
    tor_assert(!hostname);
    resolve->result.addr = addr;
  }
834
835
836
837
838
839
  resolve->ttl = ttl;
  assert_resolve_ok(resolve);
  HT_INSERT(cache_map, &cache_root, resolve);
  set_expiry(resolve, time(NULL) + dns_get_expiry_ttl(ttl));
}

840
841
842
843
844
/** 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
845
 * DNS_RESOLVE_{FAILED_TRANSIENT|FAILED_PERMANENT|SUCCEEDED}.
846
 */
847
static void
848
849
dns_found_answer(const char *address, int is_reverse, uint32_t addr,
                 const char *hostname, char outcome, uint32_t ttl)
850
{
851
852
  pending_connection_t *pend;
  cached_resolve_t search;
853
  cached_resolve_t *resolve, *removed;
854
  edge_connection_t *pendconn;
855
  circuit_t *circ;
856

857
858
  assert_cache_ok();

Nick Mathewson's avatar
Nick Mathewson committed
859
  strlcpy(search.address, address, sizeof(search.address));
860

861
  resolve = HT_FIND(cache_map, &cache_root, &search);
862
  if (!resolve) {
863
864
    log_info(LD_EXIT,"Resolved unasked address %s; caching anyway.",
             escaped_safe_str(address));
865
    add_answer_to_cache(address, is_reverse, addr, hostname, outcome, ttl);
866
    return;
867
  }
868
  assert_resolve_ok(resolve);
869

870
  if (resolve->state != CACHE_STATE_PENDING) {
871
872
    /* XXXX Maybe update addr? or check addr for consistency? Or let
     * VALID replace FAILED? */
873
874
    log_notice(LD_EXIT, "Resolved %s which was already resolved; ignoring",
               escaped_safe_str(address));
Roger Dingledine's avatar
Roger Dingledine committed
875
    tor_assert(resolve->pending_connections == NULL);
876
877
878
879
880
881
    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
882
  /* tor_assert(resolve->state == CACHE_STATE_PENDING); */
883

884
  while (resolve->pending_connections) {
885
    pend = resolve->pending_connections;
886
887
    pendconn = pend->conn; /* don't pass complex things to the
                              connection_mark_for_close macro */