src/or/dns.c

   1 /* Copyright 2003 Roger Dingledine. */
   2 /* See LICENSE for licensing information */
   3 /* $Id$ */
   4
   5 /* See http://elvin.dstc.com/ListArchive/elvin-dev/archive/2001/09/msg00027.html
   6  * for some approaches to asynchronous dns. We will want to switch once one of
   7  * them becomes more commonly available.
   8  */
   9
  10 #include "or.h"
  11 #include "tree.h"
  12
  13 #define MAX_ADDRESSLEN 256
  14
  15 #define MAX_DNSWORKERS 50
  16 #define MIN_DNSWORKERS 3
  17 #define MAX_IDLE_DNSWORKERS 10
  18
  19 int num_dnsworkers=0;
  20 int num_dnsworkers_busy=0;
  21
  22 static void purge_expired_resolves(uint32_t now);
  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);
  26 static int spawn_dnsworker(void);
  27 static void spawn_enough_dnsworkers(void);
  28
  29 struct pending_connection_t {
  30   struct connection_t *conn;
  31   struct pending_connection_t *next;
  32 };
  33
  34 struct cached_resolve {
  35   SPLAY_ENTRY(cached_resolve) node;
  36   char address[MAX_ADDRESSLEN]; /* the hostname to be resolved */
  37   uint32_t addr; /* in host order. I know I'm horrible for assuming ipv4 */
  38   char state; /* 0 is pending; 1 means answer is valid; 2 means resolve failed */
  39 #define CACHE_STATE_PENDING 0
  40 #define CACHE_STATE_VALID 1
  41 #define CACHE_STATE_FAILED 2
  42   uint32_t expire; /* remove untouched items from cache after some time? */
  43   struct pending_connection_t *pending_connections;
  44   struct cached_resolve *next;
  45 };
  46
  47 static SPLAY_HEAD(cache_tree, cached_resolve) cache_root;
  48
  49 static int compare_cached_resolves(struct cached_resolve *a,
  50                                    struct cached_resolve *b) {
  51   /* make this smarter one day? */
  52   return strncasecmp(a->address, b->address, MAX_ADDRESSLEN);
  53 }
  54
  55 SPLAY_PROTOTYPE(cache_tree, cached_resolve, node, compare_cached_resolves);
  56 SPLAY_GENERATE(cache_tree, cached_resolve, node, compare_cached_resolves);
  57
  58 static void init_cache_tree(void) {
  59   SPLAY_INIT(&cache_root);
  60 }
  61
  62 void dns_init(void) {
  63   init_cache_tree();
  64   spawn_enough_dnsworkers();
  65 }
  66
  67 static struct cached_resolve *oldest_cached_resolve = NULL; /* linked list, */
  68 static struct cached_resolve *newest_cached_resolve = NULL; /* oldest to newest */
  69
  70 static void purge_expired_resolves(uint32_t now) {
  71   struct cached_resolve *resolve;
  72
  73   /* this is fast because the linked list
  74    * oldest_cached_resolve is ordered by when they came in.
  75    */
  76   while(oldest_cached_resolve && (oldest_cached_resolve->expire < now)) {
  77     resolve = oldest_cached_resolve;
  78     log(LOG_DEBUG,"Forgetting old cached resolve (expires %lu)", (unsigned long)resolve->expire);
  79     if(resolve->state == CACHE_STATE_PENDING) {
  80       log_fn(LOG_WARN,"Expiring a dns resolve that's still pending. Forgot to cull it?");
  81       /* XXX if resolve->pending_connections is used, then we're probably
  82        * introducing bugs by closing resolve without notifying those streams.
  83        */
  84     }
  85     oldest_cached_resolve = resolve->next;
  86     if(!oldest_cached_resolve) /* if there are no more, */
  87       newest_cached_resolve = NULL; /* then make sure the list's tail knows that too */
  88     SPLAY_REMOVE(cache_tree, &cache_root, resolve);
  89     free(resolve);
  90   }
  91 }
  92
  93 /* See if we have a cache entry for 'exitconn->address'. if so,
  94  * if resolve valid, put it into exitconn->addr and return 1.
  95  * If resolve failed, return -1.
  96  *
  97  * Else, if seen before and pending, add conn to the pending list,
  98  * and return 0.
  99  *
 100  * Else, if not seen before, add conn to pending list, hand to
 101  * dns farm, and return 0.
 102  */
 103 int dns_resolve(connection_t *exitconn) {
 104   struct cached_resolve *resolve;
 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      resolves in the tree.*/
 112   purge_expired_resolves(now);
 113
 114   /* now check the tree to see if 'address' is already there. */
 115   strncpy(search.address, exitconn->address, MAX_ADDRESSLEN);
 116   search.address[MAX_ADDRESSLEN-1] = 0;
 117   resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
 118   if(resolve) { /* already there */
 119     switch(resolve->state) {
 120       case CACHE_STATE_PENDING:
 121         /* add us to the pending list */
 122         pending_connection = tor_malloc(sizeof(struct pending_connection_t));
 123         pending_connection->conn = exitconn;
 124         pending_connection->next = resolve->pending_connections;
 125         resolve->pending_connections = pending_connection;
 126         log_fn(LOG_DEBUG,"Connection (fd %d) waiting for pending DNS resolve of '%s'",
 127                exitconn->s, exitconn->address);
 128         return 0;
 129       case CACHE_STATE_VALID:
 130         exitconn->addr = resolve->addr;
 131         log_fn(LOG_DEBUG,"Connection (fd %d) found cached answer for '%s'",
 132                exitconn->s, exitconn->address);
 133         return 1;
 134       case CACHE_STATE_FAILED:
 135         return -1;
 136     }
 137     assert(0);
 138   }
 139   /* not there, need to add it */
 140   resolve = tor_malloc_zero(sizeof(struct cached_resolve));
 141   resolve->state = CACHE_STATE_PENDING;
 142   resolve->expire = now + MAX_DNS_ENTRY_AGE;
 143   strncpy(resolve->address, exitconn->address, MAX_ADDRESSLEN);
 144   resolve->address[MAX_ADDRESSLEN-1] = 0;
 145
 146   /* add us to the pending list */
 147   pending_connection = tor_malloc(sizeof(struct pending_connection_t));
 148   pending_connection->conn = exitconn;
 149   pending_connection->next = resolve->pending_connections;
 150   resolve->pending_connections = pending_connection;
 151
 152   /* add us to the linked list of resolves */
 153   if (!oldest_cached_resolve) {
 154     oldest_cached_resolve = resolve;
 155   } else {
 156     newest_cached_resolve->next = resolve;
 157   }
 158   newest_cached_resolve = resolve;
 159
 160   SPLAY_INSERT(cache_tree, &cache_root, resolve);
 161   return assign_to_dnsworker(exitconn);
 162 }
 163
 164 static int assign_to_dnsworker(connection_t *exitconn) {
 165   connection_t *dnsconn;
 166   unsigned char len;
 167
 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) {
 173     log_fn(LOG_WARN,"no idle dns workers. Failing.");
 174     dns_cancel_pending_resolve(exitconn->address);
 175     return -1;
 176   }
 177
 178   log_fn(LOG_DEBUG, "Connection (fd %d) needs to resolve '%s'; assigning to DNSWorker (fd %d)",
 179          exitconn->s, exitconn->address, dnsconn->s);
 180
 181   free(dnsconn->address);
 182   dnsconn->address = tor_strdup(exitconn->address);
 183   dnsconn->state = DNSWORKER_STATE_BUSY;
 184   num_dnsworkers_busy++;
 185
 186   len = strlen(dnsconn->address);
 187   connection_write_to_buf(&len, 1, dnsconn);
 188   connection_write_to_buf(dnsconn->address, len, dnsconn);
 189
 190 //  log_fn(LOG_DEBUG,"submitted '%s'", exitconn->address);
 191   return 0;
 192 }
 193
 194
 195 void connection_dns_remove(connection_t *conn)
 196 {
 197   struct pending_connection_t *pend, *victim;
 198   struct cached_resolve search;
 199   struct cached_resolve *resolve;
 200
 201   strncpy(search.address, conn->address, MAX_ADDRESSLEN);
 202   search.address[MAX_ADDRESSLEN-1] = 0;
 203
 204   resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
 205   if(!resolve) {
 206     log_fn(LOG_WARN,"Address '%s' is not pending. Dropping.", conn->address);
 207     return;
 208   }
 209
 210   assert(resolve->pending_connections);
 211   assert_connection_ok(conn,0);
 212
 213   pend = resolve->pending_connections;
 214
 215   if(pend->conn == conn) {
 216     resolve->pending_connections = pend->next;
 217     free(pend);
 218     log_fn(LOG_DEBUG, "Connection (fd %d) no longer waiting for resolve of '%s'",
 219            conn->s, conn->address);
 220     return;
 221   } else {
 222     for( ; pend->next; pend = pend->next) {
 223       if(pend->next->conn == conn) {
 224         victim = pend->next;
 225         pend->next = victim->next;
 226         free(victim);
 227         log_fn(LOG_DEBUG, "Connection (fd %d) no longer waiting for resolve of '%s'",
 228                conn->s, conn->address);
 229         return; /* more are pending */
 230       }
 231     }
 232     assert(0); /* not reachable unless onlyconn not in pending list */
 233   }
 234 }
 235
 236 /* If onlyconn is NULL, cancel all pending connections. If onlyconn is
 237  * defined, then remove onlyconn from the pending list.  Does not cancel the
 238  * resolve itself, or remove the 'struct cached_resolve' from the cache.
 239  */
 240 void dns_cancel_pending_resolve(char *address) {
 241   struct pending_connection_t *pend;
 242   struct cached_resolve search;
 243   struct cached_resolve *resolve, *tmp;
 244
 245   strncpy(search.address, address, MAX_ADDRESSLEN);
 246   search.address[MAX_ADDRESSLEN-1] = 0;
 247
 248   resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
 249   if(!resolve) {
 250     log_fn(LOG_WARN,"Address '%s' is not pending. Dropping.", address);
 251     return;
 252   }
 253
 254   assert(resolve->pending_connections);
 255
 256   /* mark all pending connections to fail */
 257   log_fn(LOG_DEBUG, "Failing all connections waiting on DNS resolve of '%s'",
 258          address);
 259   while(resolve->pending_connections) {
 260     pend = resolve->pending_connections;
 261     /* This calls dns_cancel_pending_resolve, which removes pend
 262      * from the list, so we don't have to do it.  Beware of
 263      * modify-while-iterating bugs hereabouts! */
 264     connection_mark_for_close(pend->conn, END_STREAM_REASON_MISC);
 265     assert(resolve->pending_connections != pend);
 266   }
 267
 268   /* remove resolve from the linked list */
 269   if(resolve == oldest_cached_resolve) {
 270     oldest_cached_resolve = resolve->next;
 271     if(oldest_cached_resolve == NULL)
 272       newest_cached_resolve = NULL;
 273   } else {
 274     /* FFFF make it a doubly linked list if this becomes too slow */
 275     for(tmp=oldest_cached_resolve; tmp && tmp->next != resolve; tmp=tmp->next) ;
 276     assert(tmp); /* it's got to be in the list, or we screwed up somewhere else */
 277     tmp->next = resolve->next; /* unlink it */
 278
 279     if(newest_cached_resolve == resolve)
 280       newest_cached_resolve = tmp;
 281   }
 282
 283   /* remove resolve from the tree */
 284   SPLAY_REMOVE(cache_tree, &cache_root, resolve);
 285
 286   free(resolve);
 287
 288 }
 289
 290 static void dns_found_answer(char *address, uint32_t addr) {
 291   struct pending_connection_t *pend;
 292   struct cached_resolve search;
 293   struct cached_resolve *resolve;
 294
 295   strncpy(search.address, address, MAX_ADDRESSLEN);
 296   search.address[MAX_ADDRESSLEN-1] = 0;
 297
 298   resolve = SPLAY_FIND(cache_tree, &cache_root, &search);
 299   if(!resolve) {
 300     log_fn(LOG_INFO,"Resolved unasked address '%s'? Dropping.", address);
 301     /* XXX Why drop?  Just because we don't care now doesn't mean we shouldn't
 302      * XXX cache the result for later. */
 303     return;
 304   }
 305
 306   if (resolve->state != CACHE_STATE_PENDING) {
 307     log_fn(LOG_WARN, "Resolved '%s' which was already resolved; ignoring",
 308            address);
 309     return;
 310   }
 311   /* Removed this assertion: in fact, we'll sometimes get a double answer
 312    * to the same question.  This can happen when we ask one worker to resolve
 313    * X.Y.Z., then we cancel the request, and then we ask another worker to
 314    * resolve X.Y.Z. */
 315   /* assert(resolve->state == CACHE_STATE_PENDING); */
 316
 317   resolve->addr = ntohl(addr);
 318   if(resolve->addr)
 319     resolve->state = CACHE_STATE_VALID;
 320   else
 321     resolve->state = CACHE_STATE_FAILED;
 322
 323   while(resolve->pending_connections) {
 324     pend = resolve->pending_connections;
 325     assert_connection_ok(pend->conn,time(NULL));
 326     pend->conn->addr = resolve->addr;
 327     if(resolve->state == CACHE_STATE_FAILED) {
 328       /* This calls dns_cancel_pending_resolve, which removes pend
 329        * from the list, so we don't have to do it.  Beware of
 330        * modify-while-iterating bugs hereabouts! */
 331       connection_mark_for_close(pend->conn, END_STREAM_REASON_RESOLVEFAILED);
 332       assert(resolve->pending_connections != pend);
 333     } else {
 334       connection_exit_connect(pend->conn);
 335       resolve->pending_connections = pend->next;
 336       free(pend);
 337     }
 338   }
 339 }
 340
 341 /******************************************************************/
 342
 343 int connection_dns_finished_flushing(connection_t *conn) {
 344   assert(conn && conn->type == CONN_TYPE_DNSWORKER);
 345   connection_stop_writing(conn);
 346   return 0;
 347 }
 348
 349 int connection_dns_process_inbuf(connection_t *conn) {
 350   uint32_t addr;
 351
 352   assert(conn && conn->type == CONN_TYPE_DNSWORKER);
 353
 354   if(conn->inbuf_reached_eof) {
 355     log_fn(LOG_WARN,"Read eof. Worker dying.");
 356     if(conn->state == DNSWORKER_STATE_BUSY) {
 357       dns_cancel_pending_resolve(conn->address);
 358       num_dnsworkers_busy--;
 359     }
 360     num_dnsworkers--;
 361     connection_mark_for_close(conn,0);
 362     return 0;
 363   }
 364
 365   assert(conn->state == DNSWORKER_STATE_BUSY);
 366   if(buf_datalen(conn->inbuf) < 4) /* entire answer available? */
 367     return 0; /* not yet */
 368   assert(buf_datalen(conn->inbuf) == 4);
 369
 370   connection_fetch_from_buf((char*)&addr,sizeof(addr),conn);
 371
 372   log_fn(LOG_DEBUG, "DNSWorker (fd %d) returned answer for '%s'",
 373          conn->s, conn->address);
 374
 375   dns_found_answer(conn->address, addr);
 376
 377   free(conn->address);
 378   conn->address = tor_strdup("<idle>");
 379   conn->state = DNSWORKER_STATE_IDLE;
 380   num_dnsworkers_busy--;
 381
 382   return 0;
 383 }
 384
 385 int dnsworker_main(void *data) {
 386   char address[MAX_ADDRESSLEN];
 387   unsigned char address_len;
 388   struct hostent *rent;
 389   int *fdarray = data;
 390   int fd;
 391
 392   close(fdarray[0]); /* this is the side of the socketpair the parent uses */
 393   fd = fdarray[1]; /* this side is ours */
 394   connection_free_all(); /* so the child doesn't hold the parent's fd's open */
 395 /* XXX probably don't close all the fd's on MS_WINDOWS? */
 396
 397   for(;;) {
 398
 399     if(read(fd, &address_len, 1) != 1) {
 400       log_fn(LOG_INFO,"read length failed. Child exiting.");
 401       spawn_exit();
 402     }
 403     assert(address_len > 0);
 404
 405     if(read_all(fd, address, address_len) != address_len) {
 406       log_fn(LOG_ERR,"read hostname failed. Child exiting.");
 407       spawn_exit();
 408     }
 409     address[address_len] = 0; /* null terminate it */
 410
 411     rent = gethostbyname(address);
 412     if (!rent) {
 413       log_fn(LOG_INFO,"Could not resolve dest addr %s. Returning nulls.",address);
 414       if(write_all(fd, "\0\0\0\0", 4) != 4) {
 415         log_fn(LOG_ERR,"writing nulls failed. Child exiting.");
 416         spawn_exit();
 417       }
 418     } else {
 419       assert(rent->h_length == 4); /* break to remind us if we move away from ipv4 */
 420       if(write_all(fd, rent->h_addr, 4) != 4) {
 421         log_fn(LOG_INFO,"writing answer failed. Child exiting.");
 422         spawn_exit();
 423       }
 424       log_fn(LOG_INFO,"Resolved address '%s'.",address);
 425     }
 426   }
 427   return 0; /* windows wants this function to return an int */
 428 }
 429
 430 static int spawn_dnsworker(void) {
 431   int fd[2];
 432   connection_t *conn;
 433
 434   if(tor_socketpair(AF_UNIX, SOCK_STREAM, 0, fd) < 0) {
 435     log(LOG_ERR, "Couldn't construct socketpair: %s", strerror(errno));
 436     exit(1);
 437   }
 438
 439   spawn_func(dnsworker_main, (void*)fd);
 440   log_fn(LOG_DEBUG,"just spawned a worker.");
 441   close(fd[1]); /* we don't need the worker's side of the pipe */
 442
 443   conn = connection_new(CONN_TYPE_DNSWORKER);
 444
 445   set_socket_nonblocking(fd[0]);
 446
 447   /* set up conn so it's got all the data we need to remember */
 448   conn->s = fd[0];
 449   conn->address = tor_strdup("<unused>");
 450
 451   if(connection_add(conn) < 0) { /* no space, forget it */
 452     log_fn(LOG_WARN,"connection_add failed. Giving up.");
 453     connection_free(conn); /* this closes fd[0] */
 454     return -1;
 455   }
 456
 457   conn->state = DNSWORKER_STATE_IDLE;
 458   connection_start_reading(conn);
 459
 460   return 0; /* success */
 461 }
 462
 463 static void spawn_enough_dnsworkers(void) {
 464   int num_dnsworkers_needed; /* aim to have 1 more than needed,
 465                            * but no less than min and no more than max */
 466   connection_t *dnsconn;
 467
 468   /* XXX This may not be the best strategy. Maybe we should queue pending
 469    *     requests until the old ones finish or time out: otherwise, if
 470    *     the connection requests come fast enough, we never get any DNS done. -NM
 471    * XXX But if we queue them, then the adversary can pile even more
 472    *     queries onto us, blocking legitimate requests for even longer.
 473    *     Maybe we should compromise and only kill if it's been at it for
 474    *     more than, e.g., 2 seconds. -RD
 475    */
 476   if(num_dnsworkers_busy == MAX_DNSWORKERS) {
 477     /* We always want at least one worker idle.
 478      * So find the oldest busy worker and kill it.
 479      */
 480     dnsconn = connection_get_by_type_state_lastwritten(CONN_TYPE_DNSWORKER,
 481                                                        DNSWORKER_STATE_BUSY);
 482     assert(dnsconn);
 483
 484     log_fn(LOG_WARN, "%d DNS workers are spawned; all are busy. Killing one.",
 485            MAX_DNSWORKERS);
 486
 487     connection_mark_for_close(dnsconn,0);
 488     num_dnsworkers_busy--;
 489     num_dnsworkers--;
 490   }
 491
 492   if(num_dnsworkers_busy >= MIN_DNSWORKERS)
 493     num_dnsworkers_needed = num_dnsworkers_busy+1;
 494   else
 495     num_dnsworkers_needed = MIN_DNSWORKERS;
 496
 497   while(num_dnsworkers < num_dnsworkers_needed) {
 498     if(spawn_dnsworker() < 0) {
 499       log(LOG_WARN,"spawn_enough_dnsworkers(): spawn failed!");
 500       return;
 501     }
 502     num_dnsworkers++;
 503   }
 504
 505   while(num_dnsworkers > num_dnsworkers_busy+MAX_IDLE_DNSWORKERS) { /* too many idle? */
 506     /* cull excess workers */
 507     log_fn(LOG_WARN,"%d of %d dnsworkers are idle. Killing one.",
 508            num_dnsworkers-num_dnsworkers_needed, num_dnsworkers);
 509     dnsconn = connection_get_by_type_state(CONN_TYPE_DNSWORKER, DNSWORKER_STATE_IDLE);
 510     assert(dnsconn);
 511     connection_mark_for_close(dnsconn,0);
 512     num_dnsworkers--;
 513   }
 514 }
 515
 516 /*
 517   Local Variables:
 518   mode:c
 519   indent-tabs-mode:nil
 520   c-basic-offset:2
 521   End:
 522 */