dns.c 16.6 KB
Newer Older
1
2
3
4
/* Copyright 2003 Roger Dingledine. */
/* See LICENSE for licensing information */
/* $Id$ */

5
6
7
8
9
/* See http://elvin.dstc.com/ListArchive/elvin-dev/archive/2001/09/msg00027.html
 * for some approaches to asynchronous dns. We will want to switch once one of
 * them becomes more commonly available.
 */

10
#include "or.h"
11
#include "tree.h"
12

13
14
#define MAX_ADDRESSLEN 256

15
16
#define MAX_DNSWORKERS 50
#define MIN_DNSWORKERS 3
17
#define MAX_IDLE_DNSWORKERS 10
18

Roger Dingledine's avatar
Roger Dingledine committed
19
20
int num_dnsworkers=0;
int num_dnsworkers_busy=0;
21

22
static void purge_expired_resolves(uint32_t now);
Roger Dingledine's avatar
Roger Dingledine committed
23
static int assign_to_dnsworker(connection_t *exitconn);
24
static void dns_found_answer(char *address, uint32_t addr);
25
int dnsworker_main(void *data);
Roger Dingledine's avatar
Roger Dingledine committed
26
27
static int spawn_dnsworker(void);
static void spawn_enough_dnsworkers(void);
28
29
30
31
32
33
34
35

struct pending_connection_t {
  struct connection_t *conn;
  struct pending_connection_t *next;
};

struct cached_resolve {
  SPLAY_ENTRY(cached_resolve) node;
36
37
  char address[MAX_ADDRESSLEN]; /* the hostname to be resolved */
  uint32_t addr; /* in host order. I know I'm horrible for assuming ipv4 */
38
39
40
41
42
43
44
45
46
  char state; /* 0 is pending; 1 means answer is valid; 2 means resolve failed */
#define CACHE_STATE_PENDING 0
#define CACHE_STATE_VALID 1
#define CACHE_STATE_FAILED 2
  uint32_t expire; /* remove untouched items from cache after some time? */
  struct pending_connection_t *pending_connections;
  struct cached_resolve *next;
};

47
static SPLAY_HEAD(cache_tree, cached_resolve) cache_root;
48

49
50
static int compare_cached_resolves(struct cached_resolve *a,
                                   struct cached_resolve *b) {
51
  /* make this smarter one day? */
52
  return strncasecmp(a->address, b->address, MAX_ADDRESSLEN);
53
54
55
56
57
}

SPLAY_PROTOTYPE(cache_tree, cached_resolve, node, compare_cached_resolves);
SPLAY_GENERATE(cache_tree, cached_resolve, node, compare_cached_resolves);

58
static void init_cache_tree(void) {
59
60
61
  SPLAY_INIT(&cache_root);
}

62
63
void dns_init(void) {
  init_cache_tree();
Roger Dingledine's avatar
Roger Dingledine committed
64
  spawn_enough_dnsworkers();
65
}
66

67
68
69
static struct cached_resolve *oldest_cached_resolve = NULL; /* linked list, */
static struct cached_resolve *newest_cached_resolve = NULL; /* oldest to newest */

70
71
72
73
74
75
76
77
static void purge_expired_resolves(uint32_t now) {
  struct cached_resolve *resolve;

  /* this is fast because the linked list
   * oldest_cached_resolve is ordered by when they came in.
   */
  while(oldest_cached_resolve && (oldest_cached_resolve->expire < now)) {
    resolve = oldest_cached_resolve;
78
    log(LOG_DEBUG,"Forgetting old cached resolve (expires %lu)", (unsigned long)resolve->expire);
79
80
81
82
83
84
    if(resolve->state == CACHE_STATE_PENDING) {
      log_fn(LOG_WARN,"Expiring a dns resolve that's still pending. Forgot to cull it?");
      /* XXX if resolve->pending_connections is used, then we're probably
       * introducing bugs by closing resolve without notifying those streams.
       */
    }
85
86
87
88
89
90
91
92
    oldest_cached_resolve = resolve->next;
    if(!oldest_cached_resolve) /* if there are no more, */
      newest_cached_resolve = NULL; /* then make sure the list's tail knows that too */
    SPLAY_REMOVE(cache_tree, &cache_root, resolve);
    free(resolve);
  }
}

93
/* See if we have a cache entry for 'exitconn->address'. if so,
94
95
 * if resolve valid, put it into exitconn->addr and return 1.
 * If resolve failed, return -1.
96
97
98
99
100
101
102
103
104
 *
 * 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.
 */
int dns_resolve(connection_t *exitconn) {
  struct cached_resolve *resolve;
Roger Dingledine's avatar
   
Roger Dingledine committed
105
  struct cached_resolve search;
106
  struct pending_connection_t *pending_connection;
107
  uint32_t now = time(NULL);
108
  assert_connection_ok(exitconn, 0);
109

110
  /* first take this opportunity to see if there are any expired
111
112
     resolves in the tree.*/
  purge_expired_resolves(now);
113

114
115
  /* now check the tree to see if 'address' is already there. */
  strncpy(search.address, exitconn->address, MAX_ADDRESSLEN);
116
  search.address[MAX_ADDRESSLEN-1] = 0;
Roger Dingledine's avatar
   
Roger Dingledine committed
117
  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
118
  if(resolve) { /* already there */
119
120
121
    switch(resolve->state) {
      case CACHE_STATE_PENDING:
        /* add us to the pending list */
122
        pending_connection = tor_malloc(sizeof(struct pending_connection_t));
123
        pending_connection->conn = exitconn;
Roger Dingledine's avatar
   
Roger Dingledine committed
124
125
        pending_connection->next = resolve->pending_connections;
        resolve->pending_connections = pending_connection;
126
127
        log_fn(LOG_DEBUG,"Connection (fd %d) waiting for pending DNS resolve of '%s'",
               exitconn->s, exitconn->address);
Roger Dingledine's avatar
   
Roger Dingledine committed
128
        return 0;
129
      case CACHE_STATE_VALID:
130
        exitconn->addr = resolve->addr;
131
132
        log_fn(LOG_DEBUG,"Connection (fd %d) found cached answer for '%s'",
               exitconn->s, exitconn->address);
133
        return 1;
134
135
136
      case CACHE_STATE_FAILED:
        return -1;
    }
Roger Dingledine's avatar
Roger Dingledine committed
137
138
139
140
141
    assert(0);
  }
  /* not there, need to add it */
  resolve = tor_malloc_zero(sizeof(struct cached_resolve));
  resolve->state = CACHE_STATE_PENDING;
142
143
  resolve->expire = now + MAX_DNS_ENTRY_AGE;
  strncpy(resolve->address, exitconn->address, MAX_ADDRESSLEN);
144
  resolve->address[MAX_ADDRESSLEN-1] = 0;
Roger Dingledine's avatar
Roger Dingledine committed
145
146
147
148
149
150
151
152
153
154
155
156

  /* add us to the pending list */
  pending_connection = tor_malloc(sizeof(struct pending_connection_t));
  pending_connection->conn = exitconn;
  pending_connection->next = resolve->pending_connections;
  resolve->pending_connections = pending_connection;

  /* add us to the linked list of resolves */
  if (!oldest_cached_resolve) {
    oldest_cached_resolve = resolve;
  } else {
    newest_cached_resolve->next = resolve;
157
  }
Roger Dingledine's avatar
Roger Dingledine committed
158
  newest_cached_resolve = resolve;
159

Roger Dingledine's avatar
Roger Dingledine committed
160
161
  SPLAY_INSERT(cache_tree, &cache_root, resolve);
  return assign_to_dnsworker(exitconn);
162
163
}

Roger Dingledine's avatar
Roger Dingledine committed
164
static int assign_to_dnsworker(connection_t *exitconn) {
165
166
  connection_t *dnsconn;
  unsigned char len;
167

Roger Dingledine's avatar
Roger Dingledine committed
168
  spawn_enough_dnsworkers(); /* respawn here, to be sure there are enough */
169

170
  dnsconn = connection_get_by_type_state(CONN_TYPE_DNSWORKER, DNSWORKER_STATE_IDLE);
171
172

  if(!dnsconn) {
Roger Dingledine's avatar
Roger Dingledine committed
173
    log_fn(LOG_WARN,"no idle dns workers. Failing.");
174
    dns_cancel_pending_resolve(exitconn->address);
175
    return -1;
176
177
  }

178
179
180
  log_fn(LOG_DEBUG, "Connection (fd %d) needs to resolve '%s'; assigning to DNSWorker (fd %d)",
         exitconn->s, exitconn->address, dnsconn->s);

Roger Dingledine's avatar
Roger Dingledine committed
181
  free(dnsconn->address);
182
  dnsconn->address = tor_strdup(exitconn->address);
183
  dnsconn->state = DNSWORKER_STATE_BUSY;
Roger Dingledine's avatar
Roger Dingledine committed
184
  num_dnsworkers_busy++;
185

186
  len = strlen(dnsconn->address);
187
188
  connection_write_to_buf(&len, 1, dnsconn);
  connection_write_to_buf(dnsconn->address, len, dnsconn);
189

Roger Dingledine's avatar
Roger Dingledine committed
190
//  log_fn(LOG_DEBUG,"submitted '%s'", exitconn->address);
191
192
193
  return 0;
}

194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
void connection_dns_remove(connection_t *conn)
{
  struct pending_connection_t *pend, *victim;
  struct cached_resolve search;
  struct cached_resolve *resolve;

  strncpy(search.address, conn->address, MAX_ADDRESSLEN);
  search.address[MAX_ADDRESSLEN-1] = 0;

  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
  if(!resolve) {
    log_fn(LOG_WARN,"Address '%s' is not pending. Dropping.", conn->address);
    return;
  }

  assert(resolve->pending_connections);
  assert_connection_ok(conn,0);

  pend = resolve->pending_connections;

  if(pend->conn == conn) {
    resolve->pending_connections = pend->next;
    free(pend);
    log_fn(LOG_DEBUG, "Connection (fd %d) no longer waiting for resolve of '%s'",
           conn->s, conn->address);
    return;
  } else {
    for( ; pend->next; pend = pend->next) {
      if(pend->next->conn == conn) {
        victim = pend->next;
        pend->next = victim->next;
        free(victim);
        log_fn(LOG_DEBUG, "Connection (fd %d) no longer waiting for resolve of '%s'",
               conn->s, conn->address);
        return; /* more are pending */
      }
    }
    assert(0); /* not reachable unless onlyconn not in pending list */
  }
}

Roger Dingledine's avatar
Roger Dingledine committed
235
236
/* Cancel all pending connections. Then cancel the resolve itself,
 * and remove the 'struct cached_resolve' from the cache.
237
 */
238
239
void dns_cancel_pending_resolve(char *address) {
  struct pending_connection_t *pend;
240
241
242
  struct cached_resolve search;
  struct cached_resolve *resolve, *tmp;

243
  strncpy(search.address, address, MAX_ADDRESSLEN);
244
  search.address[MAX_ADDRESSLEN-1] = 0;
245
246
247

  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
  if(!resolve) {
248
    log_fn(LOG_WARN,"Address '%s' is not pending. Dropping.", address);
249
250
251
    return;
  }

252
  assert(resolve->pending_connections);
253

254
255
256
257
  /* mark all pending connections to fail */
  log_fn(LOG_DEBUG, "Failing all connections waiting on DNS resolve of '%s'",
         address);
  while(resolve->pending_connections) {
258
    pend = resolve->pending_connections;
259
260
261
262
263
264
265
266
267
268
269
270
    /* This calls dns_cancel_pending_resolve, which removes pend
     * from the list, so we don't have to do it.  Beware of
     * modify-while-iterating bugs hereabouts! */
    connection_mark_for_close(pend->conn, END_STREAM_REASON_MISC);
    assert(resolve->pending_connections != pend);
  }

  /* remove resolve from the linked list */
  if(resolve == oldest_cached_resolve) {
    oldest_cached_resolve = resolve->next;
    if(oldest_cached_resolve == NULL)
      newest_cached_resolve = NULL;
271
  } else {
272
273
274
275
276
277
278
    /* FFFF make it a doubly linked list if this becomes too slow */
    for(tmp=oldest_cached_resolve; tmp && tmp->next != resolve; tmp=tmp->next) ;
    assert(tmp); /* it's got to be in the list, or we screwed up somewhere else */
    tmp->next = resolve->next; /* unlink it */

    if(newest_cached_resolve == resolve)
      newest_cached_resolve = tmp;
279
  }
280
281
282
283
284

  /* remove resolve from the tree */
  SPLAY_REMOVE(cache_tree, &cache_root, resolve);

  free(resolve);
285
286
}

287
static void dns_found_answer(char *address, uint32_t addr) {
288
289
290
291
  struct pending_connection_t *pend;
  struct cached_resolve search;
  struct cached_resolve *resolve;

292
  strncpy(search.address, address, MAX_ADDRESSLEN);
293
  search.address[MAX_ADDRESSLEN-1] = 0;
294
295
296

  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
  if(!resolve) {
297
    log_fn(LOG_INFO,"Resolved unasked address '%s'? Dropping.", address);
298
299
    /* XXX Why drop?  Just because we don't care now doesn't mean we shouldn't
     * XXX cache the result for later. */
300
    return;
301
302
  }

303
  if (resolve->state != CACHE_STATE_PENDING) {
304
305
    log_fn(LOG_WARN, "Resolved '%s' which was already resolved; ignoring",
           address);
306
307
308
309
310
311
312
    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. */
  /* assert(resolve->state == CACHE_STATE_PENDING); */
313

314
315
  resolve->addr = ntohl(addr);
  if(resolve->addr)
316
317
318
319
320
321
    resolve->state = CACHE_STATE_VALID;
  else
    resolve->state = CACHE_STATE_FAILED;

  while(resolve->pending_connections) {
    pend = resolve->pending_connections;
322
    assert_connection_ok(pend->conn,time(NULL));
323
    pend->conn->addr = resolve->addr;
324
    if(resolve->state == CACHE_STATE_FAILED) {
325
326
327
      /* This calls dns_cancel_pending_resolve, which removes pend
       * from the list, so we don't have to do it.  Beware of
       * modify-while-iterating bugs hereabouts! */
328
      connection_mark_for_close(pend->conn, END_STREAM_REASON_RESOLVEFAILED);
329
      assert(resolve->pending_connections != pend);
Roger Dingledine's avatar
Roger Dingledine committed
330
    } else {
331
      connection_exit_connect(pend->conn);
332
333
      resolve->pending_connections = pend->next;
      free(pend);
Roger Dingledine's avatar
Roger Dingledine committed
334
    }
335
336
337
  }
}

338
339
340
341
342
343
344
345
346
/******************************************************************/

int connection_dns_finished_flushing(connection_t *conn) {
  assert(conn && conn->type == CONN_TYPE_DNSWORKER);
  connection_stop_writing(conn);
  return 0;
}

int connection_dns_process_inbuf(connection_t *conn) {
347
  uint32_t addr;
348
349
350
351

  assert(conn && conn->type == CONN_TYPE_DNSWORKER);

  if(conn->inbuf_reached_eof) {
Roger Dingledine's avatar
Roger Dingledine committed
352
    log_fn(LOG_WARN,"Read eof. Worker dying.");
353
    if(conn->state == DNSWORKER_STATE_BUSY) {
354
      dns_cancel_pending_resolve(conn->address);
Roger Dingledine's avatar
Roger Dingledine committed
355
      num_dnsworkers_busy--;
356
    }
Roger Dingledine's avatar
Roger Dingledine committed
357
    num_dnsworkers--;
358
359
    connection_mark_for_close(conn,0);
    return 0;
360
361
362
  }

  assert(conn->state == DNSWORKER_STATE_BUSY);
363
  if(buf_datalen(conn->inbuf) < 4) /* entire answer available? */
364
    return 0; /* not yet */
365
  assert(buf_datalen(conn->inbuf) == 4);
366

367
  connection_fetch_from_buf((char*)&addr,sizeof(addr),conn);
368

369
370
371
  log_fn(LOG_DEBUG, "DNSWorker (fd %d) returned answer for '%s'",
         conn->s, conn->address);

372
  dns_found_answer(conn->address, addr);
373
374

  free(conn->address);
375
  conn->address = tor_strdup("<idle>");
376
  conn->state = DNSWORKER_STATE_IDLE;
Roger Dingledine's avatar
Roger Dingledine committed
377
  num_dnsworkers_busy--;
378
379
380
381

  return 0;
}

382
int dnsworker_main(void *data) {
383
384
  char address[MAX_ADDRESSLEN];
  unsigned char address_len;
385
  struct hostent *rent;
386
  int *fdarray = data;
Roger Dingledine's avatar
Roger Dingledine committed
387
  int fd;
388
389
390

  close(fdarray[0]); /* this is the side of the socketpair the parent uses */
  fd = fdarray[1]; /* this side is ours */
391
  connection_free_all(); /* so the child doesn't hold the parent's fd's open */
392
/* XXX probably don't close all the fd's on MS_WINDOWS? */
393
394
395

  for(;;) {

396
    if(read(fd, &address_len, 1) != 1) {
397
      log_fn(LOG_INFO,"read length failed. Child exiting.");
398
      spawn_exit();
399
    }
400
    assert(address_len > 0);
401

402
    if(read_all(fd, address, address_len) != address_len) {
403
      log_fn(LOG_ERR,"read hostname failed. Child exiting.");
404
      spawn_exit();
405
    }
406
    address[address_len] = 0; /* null terminate it */
407

408
    rent = gethostbyname(address);
409
    if (!rent) {
410
      log_fn(LOG_INFO,"Could not resolve dest addr %s. Returning nulls.",address);
Roger Dingledine's avatar
Roger Dingledine committed
411
      if(write_all(fd, "\0\0\0\0", 4) != 4) {
412
        log_fn(LOG_ERR,"writing nulls failed. Child exiting.");
413
        spawn_exit();
414
415
416
      }
    } else {
      assert(rent->h_length == 4); /* break to remind us if we move away from ipv4 */
Roger Dingledine's avatar
Roger Dingledine committed
417
      if(write_all(fd, rent->h_addr, 4) != 4) {
418
        log_fn(LOG_INFO,"writing answer failed. Child exiting.");
419
        spawn_exit();
420
      }
421
      log_fn(LOG_INFO,"Resolved address '%s'.",address);
422
423
    }
  }
424
  return 0; /* windows wants this function to return an int */
425
426
}

Roger Dingledine's avatar
Roger Dingledine committed
427
static int spawn_dnsworker(void) {
428
429
430
  int fd[2];
  connection_t *conn;

431
  if(tor_socketpair(AF_UNIX, SOCK_STREAM, 0, fd) < 0) {
432
    log(LOG_ERR, "Couldn't construct socketpair: %s", strerror(errno));
433
434
435
    exit(1);
  }

436
  spawn_func(dnsworker_main, (void*)fd);
Roger Dingledine's avatar
Roger Dingledine committed
437
  log_fn(LOG_DEBUG,"just spawned a worker.");
438
  close(fd[1]); /* we don't need the worker's side of the pipe */
439
440
441

  conn = connection_new(CONN_TYPE_DNSWORKER);

442
  set_socket_nonblocking(fd[0]);
443
444
445

  /* set up conn so it's got all the data we need to remember */
  conn->s = fd[0];
Roger Dingledine's avatar
Roger Dingledine committed
446
  conn->address = tor_strdup("<unused>");
447
448

  if(connection_add(conn) < 0) { /* no space, forget it */
Roger Dingledine's avatar
Roger Dingledine committed
449
    log_fn(LOG_WARN,"connection_add failed. Giving up.");
450
451
452
453
454
455
456
457
458
459
    connection_free(conn); /* this closes fd[0] */
    return -1;
  }

  conn->state = DNSWORKER_STATE_IDLE;
  connection_start_reading(conn);

  return 0; /* success */
}

Roger Dingledine's avatar
Roger Dingledine committed
460
461
static void spawn_enough_dnsworkers(void) {
  int num_dnsworkers_needed; /* aim to have 1 more than needed,
462
                           * but no less than min and no more than max */
463
464
  connection_t *dnsconn;

465
  /* XXX This may not be the best strategy. Maybe we should queue pending
466
467
468
469
470
471
   *     requests until the old ones finish or time out: otherwise, if
   *     the connection requests come fast enough, we never get any DNS done. -NM
   * XXX But if we queue them, then the adversary can pile even more
   *     queries onto us, blocking legitimate requests for even longer.
   *     Maybe we should compromise and only kill if it's been at it for
   *     more than, e.g., 2 seconds. -RD
472
   */
Roger Dingledine's avatar
Roger Dingledine committed
473
  if(num_dnsworkers_busy == MAX_DNSWORKERS) {
474
475
476
    /* We always want at least one worker idle.
     * So find the oldest busy worker and kill it.
     */
477
478
    dnsconn = connection_get_by_type_state_lastwritten(CONN_TYPE_DNSWORKER,
                                                       DNSWORKER_STATE_BUSY);
479
480
    assert(dnsconn);

481
482
    log_fn(LOG_WARN, "%d DNS workers are spawned; all are busy. Killing one.",
           MAX_DNSWORKERS);
483

484
    connection_mark_for_close(dnsconn,0);
Roger Dingledine's avatar
Roger Dingledine committed
485
    num_dnsworkers_busy--;
486
    num_dnsworkers--;
487
  }
488

Roger Dingledine's avatar
Roger Dingledine committed
489
490
  if(num_dnsworkers_busy >= MIN_DNSWORKERS)
    num_dnsworkers_needed = num_dnsworkers_busy+1;
491
  else
Roger Dingledine's avatar
Roger Dingledine committed
492
    num_dnsworkers_needed = MIN_DNSWORKERS;
493

Roger Dingledine's avatar
Roger Dingledine committed
494
495
  while(num_dnsworkers < num_dnsworkers_needed) {
    if(spawn_dnsworker() < 0) {
Roger Dingledine's avatar
Roger Dingledine committed
496
      log(LOG_WARN,"spawn_enough_dnsworkers(): spawn failed!");
497
498
      return;
    }
Roger Dingledine's avatar
Roger Dingledine committed
499
    num_dnsworkers++;
500
501
  }

502
  while(num_dnsworkers > num_dnsworkers_busy+MAX_IDLE_DNSWORKERS) { /* too many idle? */
503
    /* cull excess workers */
504
505
    log_fn(LOG_WARN,"%d of %d dnsworkers are idle. Killing one.",
           num_dnsworkers-num_dnsworkers_needed, num_dnsworkers);
506
507
    dnsconn = connection_get_by_type_state(CONN_TYPE_DNSWORKER, DNSWORKER_STATE_IDLE);
    assert(dnsconn);
508
    connection_mark_for_close(dnsconn,0);
Roger Dingledine's avatar
Roger Dingledine committed
509
    num_dnsworkers--;
510
  }
511
512
}

513
514
515
516
517
518
519
/*
  Local Variables:
  mode:c
  indent-tabs-mode:nil
  c-basic-offset:2
  End:
*/