dns.c 13.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

19
20
int num_workers=0;
int num_workers_busy=0;
21

22
static int dns_assign_to_worker(connection_t *exitconn);
23
static void dns_found_answer(char *question, uint32_t answer);
24
25
26
static void dnsworker_main(int fd);
static int dns_spawn_worker(void);
static void spawn_enough_workers(void);
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

struct cached_resolve {
  SPLAY_ENTRY(cached_resolve) node;
  char question[MAX_ADDRESSLEN]; /* the hostname to be resolved */
  uint32_t answer; /* in host order. I know I'm horrible for assuming ipv4 */
  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;
};

SPLAY_HEAD(cache_tree, cached_resolve) cache_root;

static int compare_cached_resolves(struct cached_resolve *a, struct cached_resolve *b) {
  /* make this smarter one day? */
  return strncasecmp(a->question, b->question, MAX_ADDRESSLEN);
}

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

56
static void init_cache_tree(void) {
57
58
59
  SPLAY_INIT(&cache_root);
}

60
61
62
63
void dns_init(void) {
  init_cache_tree();
  spawn_enough_workers();
}
64

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

68
69
70
/* See if the question 'exitconn->address' has been answered. if so,
 * if resolve valid, put it into exitconn->addr and exec to
 * connection_exit_connect. If resolve failed, return -1.
71
72
73
74
75
76
77
78
79
 *
 * 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
80
  struct cached_resolve search;
81
  struct pending_connection_t *pending_connection;
82
  uint32_t now = time(NULL);
83

84
85
86
87
88
89
90
91
92
93
94
95
96
  /* first take this opportunity to see if there are any expired
   * resolves in the tree. 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;
    log(LOG_DEBUG,"Forgetting old cached resolve (expires %d)", resolve->expire);
    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);
  }
97

98
99
  /* now check the tree to see if 'question' is already there. */
  strncpy(search.question, exitconn->address, MAX_ADDRESSLEN);
Roger Dingledine's avatar
   
Roger Dingledine committed
100
  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
101
  if(resolve) { /* already there */
102
103
104
    switch(resolve->state) {
      case CACHE_STATE_PENDING:
        /* add us to the pending list */
105
        pending_connection = tor_malloc(sizeof(struct pending_connection_t));
106
        pending_connection->conn = exitconn;
Roger Dingledine's avatar
   
Roger Dingledine committed
107
108
109
        pending_connection->next = resolve->pending_connections;
        resolve->pending_connections = pending_connection;
        return 0;
110
111
112
113
114
115
      case CACHE_STATE_VALID:
        exitconn->addr = resolve->answer;
        return connection_exit_connect(exitconn);
      case CACHE_STATE_FAILED:
        return -1;
    }
116
  } else { /* need to add it */
117
    resolve = tor_malloc(sizeof(struct cached_resolve));
Roger Dingledine's avatar
   
Roger Dingledine committed
118
119
    memset(resolve, 0, sizeof(struct cached_resolve));
    resolve->state = CACHE_STATE_PENDING;
120
121
    resolve->expire = now + 100; /* XXX for testing. when we're confident, switch it back */
//    resolve->expire = now + 86400; /* now + 1 day */
Roger Dingledine's avatar
   
Roger Dingledine committed
122
    strncpy(resolve->question, exitconn->address, MAX_ADDRESSLEN);
123
124

    /* add us to the pending list */
125
    pending_connection = tor_malloc(sizeof(struct pending_connection_t));
126
    pending_connection->conn = exitconn;
Roger Dingledine's avatar
   
Roger Dingledine committed
127
128
    pending_connection->next = resolve->pending_connections;
    resolve->pending_connections = pending_connection;
129

130
131
132
133
134
135
136
137
    /* add us to the linked list of resolves */
    if (!oldest_cached_resolve) {
      oldest_cached_resolve = resolve;
    } else {
      newest_cached_resolve->next = resolve;
    }
    newest_cached_resolve = resolve;

Roger Dingledine's avatar
   
Roger Dingledine committed
138
    SPLAY_INSERT(cache_tree, &cache_root, resolve);
139
    return dns_assign_to_worker(exitconn);
140
141
142
143
144
145
  }

  assert(0);
  return 0; /* not reached; keep gcc happy */
}

146
static int dns_assign_to_worker(connection_t *exitconn) {
147
148
  connection_t *dnsconn;
  unsigned char len;
149
150

  spawn_enough_workers(); /* respawn here, to be sure there are enough */
151

152
  dnsconn = connection_get_by_type_state(CONN_TYPE_DNSWORKER, DNSWORKER_STATE_IDLE);
153
154

  if(!dnsconn) {
155
    log(LOG_INFO,"dns_assign_to_worker(): no idle dns workers. Failing.");
156
    dns_cancel_pending_resolve(exitconn->address, NULL);
157
    return -1;
158
159
  }

160
161
162
  dnsconn->address = strdup(exitconn->address);
  dnsconn->state = DNSWORKER_STATE_BUSY;
  num_workers_busy++;
163

164
165
166
167
168
169
  len = strlen(dnsconn->address);
  /* FFFF we should have it retry if the first worker bombs out */
  if(connection_write_to_buf(&len, 1, dnsconn) < 0 ||
     connection_write_to_buf(dnsconn->address, len, dnsconn) < 0) {
    log(LOG_NOTICE,"dns_assign_to_worker(): Write failed. Closing worker and failing resolve.");
    dnsconn->marked_for_close = 1;
170
    dns_cancel_pending_resolve(exitconn->address, NULL);
171
172
173
    return -1;
  }

174
//  log(LOG_DEBUG,"dns_assign_to_worker(): submitted '%s'", exitconn->address);
175
176
177
  return 0;
}

178
179
180
181
182
183
/* if onlyconn is NULL, cancel the whole thing. if onlyconn is defined,
 * then remove onlyconn from the pending list, and if the pending list
 * is now empty, cancel the whole thing.
 */
void dns_cancel_pending_resolve(char *question, connection_t *onlyconn) {
  struct pending_connection_t *pend, *victim;
184
185
186
187
188
189
190
  struct cached_resolve search;
  struct cached_resolve *resolve, *tmp;

  strncpy(search.question, question, MAX_ADDRESSLEN);

  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
  if(!resolve) {
191
    log_fn(LOG_INFO,"Answer to unasked question '%s'? Dropping.", question);
192
193
194
195
    return;
  }

  assert(resolve->state == CACHE_STATE_PENDING);
196
  assert(resolve->pending_connections);
197

198
  if(onlyconn) {
199
    pend = resolve->pending_connections;
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
    if(pend->conn == onlyconn) {
      resolve->pending_connections = pend->next;
      free(pend);
      if(resolve->pending_connections) /* more pending, don't cancel it */
        return;
    } else {
      for( ; pend->next; pend = pend->next) {
        if(pend->next->conn == onlyconn) {
          victim = pend->next;
          pend->next = victim->next;
          free(victim);
          return; /* more are pending */
        }
      }
      assert(0); /* not reachable unless onlyconn not in pending list */
    }
  } else {
    /* mark all pending connections to fail */
    while(resolve->pending_connections) {
      pend = resolve->pending_connections;
      pend->conn->marked_for_close = 1;
      resolve->pending_connections = pend->next;
      free(pend);
    }
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
  }

  /* 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;
  } else {
    /* 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;
  }

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

  free(resolve);
}

static void dns_found_answer(char *question, uint32_t answer) {
248
249
250
251
252
253
254
255
  struct pending_connection_t *pend;
  struct cached_resolve search;
  struct cached_resolve *resolve;

  strncpy(search.question, question, MAX_ADDRESSLEN);

  resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
  if(!resolve) {
256
    log_fn(LOG_INFO,"Answer to unasked question '%s'? Dropping.", question);
257
    return;
258
259
  }

260
  assert(resolve->state == CACHE_STATE_PENDING);
261

262
  resolve->answer = ntohl(answer);
263
  if(resolve->answer)
264
265
266
267
268
269
    resolve->state = CACHE_STATE_VALID;
  else
    resolve->state = CACHE_STATE_FAILED;

  while(resolve->pending_connections) {
    pend = resolve->pending_connections;
270
    pend->conn->addr = resolve->answer;
271
272
273
274
275
276
277
278
    if(resolve->state == CACHE_STATE_FAILED || connection_exit_connect(pend->conn) < 0) {
      pend->conn->marked_for_close = 1;
    }
    resolve->pending_connections = pend->next;
    free(pend);
  }
}

279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
/******************************************************************/

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) {
  uint32_t answer;

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

  if(conn->inbuf_reached_eof) {
    log(LOG_ERR,"connection_dnsworker_process_inbuf(): Read eof. Worker dying.");
294
    if(conn->state == DNSWORKER_STATE_BUSY)
295
      dns_cancel_pending_resolve(conn->address, NULL);
296
297
298
299
300
301
302
303
    return -1;
  }

  assert(conn->state == DNSWORKER_STATE_BUSY);
  if(conn->inbuf_datalen < 4) /* entire answer available? */
    return 0; /* not yet */
  assert(conn->inbuf_datalen == 4);

304
  connection_fetch_from_buf((char*)&answer,sizeof(answer),conn);
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384

  dns_found_answer(conn->address, answer);

  free(conn->address);
  conn->address = NULL;
  conn->state = DNSWORKER_STATE_IDLE;
  num_workers_busy--;

  return 0;
}

static void dnsworker_main(int fd) {
  char question[MAX_ADDRESSLEN];
  unsigned char question_len;
  struct hostent *rent;

  for(;;) {

    if(read(fd, &question_len, 1) != 1) {
      log(LOG_INFO,"dnsworker_main(): read length failed. Exiting.");
      exit(0);
    }
    assert(question_len > 0);

    if(read(fd, question, question_len) != question_len) {
      log(LOG_INFO,"dnsworker_main(): read hostname failed. Exiting.");
      exit(0);
    }
    question[question_len] = 0; /* null terminate it */

    rent = gethostbyname(question);
    if (!rent) {
      log(LOG_INFO,"dnsworker_main(): Could not resolve dest addr %s. Returning nulls.",question);
      /* XXX it's conceivable write could return 1 through 3. but that's never gonna happen, right? */
      if(write(fd, "\0\0\0\0", 4) != 4) {
        log(LOG_INFO,"dnsworker_main(): writing nulls failed. Exiting.");
        exit(0);
      }
    } else {
      assert(rent->h_length == 4); /* break to remind us if we move away from ipv4 */
      if(write(fd, rent->h_addr, 4) != 4) {
        log(LOG_INFO,"dnsworker_main(): writing answer failed. Exiting.");
        exit(0);
      }
      log(LOG_INFO,"dnsworker_main(): Answered question '%s'.",question);
    }
  }
}

static int dns_spawn_worker(void) {
  pid_t pid;
  int fd[2];
  connection_t *conn;

  if(socketpair(AF_UNIX, SOCK_STREAM, 0, fd) < 0) {
    perror("socketpair");
    exit(1);
  }

  pid = fork();
  if(pid < 0) {
    perror("fork");
    exit(1);
  }
  if(pid == 0) { /* i'm the child */
    close(fd[0]);
    dnsworker_main(fd[1]);
    assert(0); /* never gets here */
  }

  /* i'm the parent */
  log(LOG_DEBUG,"dns_spawn_worker(): just spawned a worker.");
  close(fd[1]);

  conn = connection_new(CONN_TYPE_DNSWORKER);
  if(!conn) {
    close(fd[0]);
    return -1;
  }

385
  set_socket_nonblocking(fd[0]);
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406

  /* set up conn so it's got all the data we need to remember */
  conn->receiver_bucket = -1; /* non-cell connections don't do receiver buckets */
  conn->bandwidth = -1;
  conn->s = fd[0];

  if(connection_add(conn) < 0) { /* no space, forget it */
    log(LOG_INFO,"dns_spawn_worker(): connection_add failed. Giving up.");
    connection_free(conn); /* this closes fd[0] */
    return -1;
  }

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

  return 0; /* success */
}

static void spawn_enough_workers(void) {
  int num_workers_needed; /* aim to have 1 more than needed,
                           * but no less than min and no more than max */
407
408
409
410
411
412
  connection_t *dnsconn;

  if(num_workers_busy == MAX_DNSWORKERS) {
    /* We always want at least one worker idle.
     * So find the oldest busy worker and kill it.
     */
413
414
415
416
    dnsconn = connection_get_by_type_state_lastwritten(CONN_TYPE_DNSWORKER, DNSWORKER_STATE_BUSY);
    assert(dnsconn);

    /* tell the exit connection that it's failed */
417
    dns_cancel_pending_resolve(dnsconn->address, NULL);
418

419
420
    dnsconn->marked_for_close = 1;
    num_workers_busy--;
421
  }
422
423
424
425
426
427
428
429
430
431
432
433
434
435

  if(num_workers_busy >= MIN_DNSWORKERS)
    num_workers_needed = num_workers_busy+1;
  else
    num_workers_needed = MIN_DNSWORKERS;

  while(num_workers < num_workers_needed) {
    if(dns_spawn_worker() < 0) {
      log(LOG_ERR,"spawn_enough_workers(): spawn failed!");
      return;
    }
    num_workers++;
  }

436
437
438
439
440
441
442
  while(num_workers > num_workers_needed+MAX_IDLE_DNSWORKERS) { /* too many idle? */
    /* cull excess workers */
    dnsconn = connection_get_by_type_state(CONN_TYPE_DNSWORKER, DNSWORKER_STATE_IDLE);
    assert(dnsconn);
    dnsconn->marked_for_close = 1;
    num_workers--;
  }
443
444
}

445
446
447
448
449
450
451
/*
  Local Variables:
  mode:c
  indent-tabs-mode:nil
  c-basic-offset:2
  End:
*/