/* Copyright 2006-2007 Niels Provos

 * Copyright 2007-2012 Nick Mathewson and Niels Provos

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 3. The name of the author may not be used to endorse or promote products

 *    derived from this software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

/* Based on software by Adam Langly. Adam's original message:

 *

 * Async DNS Library

 * Adam Langley <agl@imperialviolet.org>

 * Public Domain code

 *

 * This software is Public Domain. To view a copy of the public domain dedication,

 * visit http://creativecommons.org/licenses/publicdomain/ or send a letter to

 * Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

 *

 * I ask and expect, but do not require, that all derivative works contain an

 * attribution similar to:

 *  Parts developed by Adam Langley <agl@imperialviolet.org>

 *

 * You may wish to replace the word "Parts" with something else depending on

 * the amount of original code.

 *

 * (Derivative works does not include programs which link against, run or include

 * the source verbatim in their source distributions)

 *

 * Version: 0.1b

 */

#include "event2/event-config.h"

#include "evconfig-private.h"

#include <sys/types.h>

#ifndef _FORTIFY_SOURCE

#define _FORTIFY_SOURCE 3

#endif

#include <string.h>

#include <fcntl.h>

#ifdef EVENT__HAVE_SYS_TIME_H

#include <sys/time.h>

#endif

#ifdef EVENT__HAVE_STDINT_H

#include <stdint.h>

#endif

#include <stdlib.h>

#include <string.h>

#include <errno.h>

#ifdef EVENT__HAVE_UNISTD_H

#include <unistd.h>

#endif

#include <limits.h>

#include <sys/stat.h>

#include <stdio.h>

#include <stdarg.h>

#ifdef _WIN32

#include <winsock2.h>

#include <winerror.h>

#include <ws2tcpip.h>

#ifndef _WIN32_IE

#define _WIN32_IE 0x400

#endif

#include <shlobj.h>

#endif

#include "event2/buffer.h"

#include "event2/bufferevent.h"

#include "event2/dns.h"

#include "event2/dns_struct.h"

#include "event2/dns_compat.h"

#include "event2/util.h"

#include "event2/event.h"

#include "event2/event_struct.h"

#include "event2/listener.h"

#include "event2/thread.h"

#include "defer-internal.h"

#include "log-internal.h"

#include "mm-internal.h"

#include "strlcpy-internal.h"

#include "ipv6-internal.h"

#include "util-internal.h"

#include "evthread-internal.h"

#ifdef _WIN32

#include <ctype.h>

#include <winsock2.h>

#include <windows.h>

#include <iphlpapi.h>

#include <io.h>

#else

#include <sys/socket.h>

#include <netinet/in.h>

#include <arpa/inet.h>

#endif

#ifdef EVENT__HAVE_NETINET_IN6_H

#include <netinet/in6.h>

#endif

#define EVDNS_LOG_DEBUG EVENT_LOG_DEBUG

#define EVDNS_LOG_WARN EVENT_LOG_WARN

#define EVDNS_LOG_MSG EVENT_LOG_MSG

#ifndef EVDNS_NAME_MAX

#define EVDNS_NAME_MAX 255

#endif

#include <stdio.h>

#undef MIN

#undef MAX

#define MIN(a,b) ((a)<(b)?(a):(b))

#define MAX(a,b) ((a)>(b)?(a):(b))

#define ASSERT_VALID_REQUEST(req) \

  EVUTIL_ASSERT((req)->handle && (req)->handle->current_req == (req))

#define u64 ev_uint64_t

#define u32 ev_uint32_t

#define u16 ev_uint16_t

#define u8  ev_uint8_t

/* maximum number of addresses from a single packet */

/* that we bother recording */

#define MAX_V4_ADDRS 32

#define MAX_V6_ADDRS 32

/* Maximum allowable size of a DNS message over UDP without EDNS.*/

#define DNS_MAX_UDP_SIZE 512

/* Maximum allowable size of a DNS message over UDP with EDNS.*/

#define EDNS_MAX_UDP_SIZE 65535

#define EDNS_ENABLED(base) \

  (((base)->global_max_udp_size) > DNS_MAX_UDP_SIZE)

#define TYPE_A         EVDNS_TYPE_A

#define TYPE_CNAME     5

#define TYPE_PTR       EVDNS_TYPE_PTR

#define TYPE_SOA       EVDNS_TYPE_SOA

#define TYPE_AAAA      EVDNS_TYPE_AAAA

#define TYPE_OPT       41

#define CLASS_INET     EVDNS_CLASS_INET

/* Timeout in seconds for idle TCP connections that server keeps alive. */

#define SERVER_IDLE_CONN_TIMEOUT 10

/* Timeout in seconds for idle TCP connections that client keeps alive. */

#define CLIENT_IDLE_CONN_TIMEOUT 5

/* Default maximum number of simultaneous TCP client connections that DNS server can hold. */

#define MAX_CLIENT_CONNECTIONS 10

struct reply {

  unsigned int type;

  unsigned int have_answer : 1;

  u32 rr_count;

  union {

    u32 *a;

    struct in6_addr *aaaa;

    char *ptr_name;

    void *raw;

  } data;

  char *cname;

};

/* Persistent handle.  We keep this separate from 'struct request' since we

 * need some object to last for as long as an evdns_request is outstanding so

 * that it can be canceled, whereas a search request can lead to multiple

 * 'struct request' instances being created over its lifetime. */

struct evdns_request {

  struct request *current_req;

  struct evdns_base *base;

  int pending_cb; /* Waiting for its callback to be invoked; not

       * owned by event base any more. */

  /* data used when fulfilling the callback */

  struct event_callback deferred;

  evdns_callback_type user_callback;

  void *user_pointer;

  u8 request_type;

  u8 have_reply;

  u32 ttl;

  u32 err;

  struct reply reply;

  /* elements used by the searching code */

  int search_index;

  struct search_state *search_state;

  char *search_origname;  /* needs to be free()ed */

  int search_flags;

  u16 tcp_flags;

};

struct request {

  u8 *request;  /* the dns packet data */

  u16 request_size; /* size of memory block stored in request field */

  u8 request_type; /* TYPE_PTR or TYPE_A or TYPE_AAAA */

  unsigned int request_len;

  int reissue_count;

  int tx_count;  /* the number of times that this packet has been sent */

  struct nameserver *ns;  /* the server which we last sent it */

  /* these objects are kept in a circular list */

  /* XXX We could turn this into a CIRCLEQ. */

  struct request *next, *prev;

  struct event timeout_event;

  u16 trans_id;  /* the transaction id */

  unsigned request_appended :1; /* true if the request pointer is data which follows this struct */

  unsigned transmit_me :1;  /* needs to be transmitted */

  unsigned need_cname :1;   /* make a separate callback for CNAME */

  /* XXXX This is a horrible hack. */

  char **put_cname_in_ptr; /* store the cname here if we get one. */

  struct evdns_base *base;

  struct evdns_request *handle;

};

enum tcp_state {

  TS_DISCONNECTED,

  TS_CONNECTING,

  TS_CONNECTED

};

struct tcp_connection {

  struct bufferevent *bev;

  enum tcp_state state;

  u16 awaiting_packet_size;

};

struct evdns_server_port;

struct client_tcp_connection {

  LIST_ENTRY(client_tcp_connection) next;

  struct tcp_connection connection;

  struct evdns_server_port *port;

};

struct nameserver {

  evutil_socket_t socket;  /* a connected UDP socket */

  struct tcp_connection *connection; /* intended for TCP support */

  struct sockaddr_storage address;

  ev_socklen_t addrlen;

  int failed_times;  /* number of times which we have given this server a chance */

  int timedout;  /* number of times in a row a request has timed out */

  struct event event;

  /* these objects are kept in a circular list */

  struct nameserver *next, *prev;

  struct event timeout_event;  /* used to keep the timeout for */

             /* when we next probe this server. */

             /* Valid if state == 0 */

  /* Outstanding probe request for this nameserver, if any */

  struct evdns_request *probe_request;

  char state;  /* zero if we think that this server is down */

  char choked;  /* true if we have an EAGAIN from this server's socket */

  char write_waiting;  /* true if we are waiting for EV_WRITE events */

  struct evdns_base *base;

  /* Number of currently inflight requests: used

   * to track when we should add/del the event. */

  int requests_inflight;

};

/* Represents a local port where we're listening for DNS requests. */

struct evdns_server_port {

  evutil_socket_t socket; /* socket we use to read queries and write replies. */

  int refcnt; /* reference count. */

  char choked; /* Are we currently blocked from writing? */

  char closing; /* Are we trying to close this port, pending writes? */

  evdns_request_callback_fn_type user_callback; /* Fn to handle requests */

  void *user_data; /* Opaque pointer passed to user_callback */

  struct event event; /* Read/write event */

  /* circular list of replies that we want to write. */

  struct server_request *pending_replies;

  struct event_base *event_base;

  /* Structures for tcp support */

  struct evconnlistener *listener;

  LIST_HEAD(client_list, client_tcp_connection) client_connections;

  unsigned client_connections_count;

  unsigned max_client_connections;

  struct timeval tcp_idle_timeout;

#ifndef EVENT__DISABLE_THREAD_SUPPORT

  void *lock;

#endif

};

/* Represents part of a reply being built.  (That is, a single RR.) */

struct server_reply_item {

  struct server_reply_item *next; /* next item in sequence. */

  char *name; /* name part of the RR */

  u16 type; /* The RR type */

  u16 class; /* The RR class (usually CLASS_INET) */

  u32 ttl; /* The RR TTL */

  char is_name; /* True iff data is a label */

  u16 datalen; /* Length of data; -1 if data is a label */

  void *data; /* The contents of the RR */

};

/* Represents a request that we've received as a DNS server, and holds */

/* the components of the reply as we're constructing it. */

struct server_request {

  /* Pointers to the next and previous entries on the list of replies */

  /* that we're waiting to write.  Only set if we have tried to respond */

  /* and gotten EAGAIN. */

  struct server_request *next_pending;

  struct server_request *prev_pending;

  u16 trans_id; /* Transaction id. */

  struct evdns_server_port *port; /* Which port received this request on? */

  struct client_tcp_connection *client; /* Equal to NULL in case of UDP connection. */

  struct sockaddr_storage addr; /* Where to send the response in case of UDP. Equal to NULL in case of TCP connection.*/

  ev_socklen_t addrlen; /* length of addr */

  u16 max_udp_reply_size; /* Maximum size of udp reply that client can handle. */

  int n_answer; /* how many answer RRs have been set? */

  int n_authority; /* how many authority RRs have been set? */

  int n_additional; /* how many additional RRs have been set? */

  struct server_reply_item *answer; /* linked list of answer RRs */

  struct server_reply_item *authority; /* linked list of authority RRs */

  struct server_reply_item *additional; /* linked list of additional RRs */

  /* Constructed response.  Only set once we're ready to send a reply. */

  /* Once this is set, the RR fields are cleared, and no more should be set. */

  char *response;

  size_t response_len;

  /* Caller-visible fields: flags, questions. */

  struct evdns_server_request base;

};

struct evdns_base {

  /* An array of n_req_heads circular lists for inflight requests.

   * Each inflight request req is in req_heads[req->trans_id % n_req_heads].

   */

  struct request **req_heads;

  /* A circular list of requests that we're waiting to send, but haven't

   * sent yet because there are too many requests inflight */

  struct request *req_waiting_head;

  /* A circular list of nameservers. */

  struct nameserver *server_head;

  int n_req_heads;

  struct event_base *event_base;

  /* The number of good nameservers that we have */

  int global_good_nameservers;

  /* inflight requests are contained in the req_head list */

  /* and are actually going out across the network */

  int global_requests_inflight;

  /* requests which aren't inflight are in the waiting list */

  /* and are counted here */

  int global_requests_waiting;

  int global_max_requests_inflight;

  struct timeval global_timeout;  /* 5 seconds by default */

  int global_max_reissues;  /* a reissue occurs when we get some errors from the server */

  int global_max_retransmits;  /* number of times we'll retransmit a request which timed out */

  /* number of timeouts in a row before we consider this server to be down */

  int global_max_nameserver_timeout;

  /* true iff we will use the 0x20 hack to prevent poisoning attacks. */

  int global_randomize_case;

  /* Maximum size of a UDP DNS packet. */

  u16 global_max_udp_size;

  /* The first time that a nameserver fails, how long do we wait before

   * probing to see if it has returned?  */

  struct timeval global_nameserver_probe_initial_timeout;

  /* Combination of DNS_QUERY_USEVC, DNS_QUERY_IGNTC flags

   * to control requests via TCP. */

  u16 global_tcp_flags;

  /* Idle timeout for outgoing TCP connections. */

  struct timeval global_tcp_idle_timeout;

  /** Port to bind to for outgoing DNS packets. */

  struct sockaddr_storage global_outgoing_address;

  /** ev_socklen_t for global_outgoing_address. 0 if it isn't set. */

  ev_socklen_t global_outgoing_addrlen;

  struct timeval global_getaddrinfo_allow_skew;

  int so_rcvbuf;

  int so_sndbuf;

  int getaddrinfo_ipv4_timeouts;

  int getaddrinfo_ipv6_timeouts;

  int getaddrinfo_ipv4_answered;

  int getaddrinfo_ipv6_answered;

  struct search_state *global_search_state;

  TAILQ_HEAD(hosts_list, hosts_entry) hostsdb;

#ifndef EVENT__DISABLE_THREAD_SUPPORT

  void *lock;

#endif

  int disable_when_inactive;

  /* Maximum timeout between two probe packets

   * will change `global_nameserver_probe_initial_timeout`

   * when this value is smaller */

  int ns_max_probe_timeout;

  /* Backoff factor of probe timeout */

  int ns_timeout_backoff_factor;

};

struct hosts_entry {

  TAILQ_ENTRY(hosts_entry) next;

  union {

    struct sockaddr sa;

    struct sockaddr_in sin;

    struct sockaddr_in6 sin6;

  } addr;

  int addrlen;

  char hostname[1];

};

static struct evdns_base *current_base = NULL;

struct evdns_base *

evdns_get_global_base(void)

{

  return current_base;

}

/* Given a pointer to an evdns_server_request, get the corresponding */

/* server_request. */

#define TO_SERVER_REQUEST(base_ptr)         \

  ((struct server_request*)         \

    (((char*)(base_ptr) - evutil_offsetof(struct server_request, base))))

#define REQ_HEAD(base, id) ((base)->req_heads[id % (base)->n_req_heads])

static struct nameserver *nameserver_pick(struct evdns_base *base);

static void evdns_request_insert(struct request *req, struct request **head);

static void evdns_request_remove(struct request *req, struct request **head);

static void nameserver_ready_callback(evutil_socket_t fd, short events, void *arg);

static int evdns_transmit(struct evdns_base *base);

static int evdns_request_transmit(struct request *req);

static void nameserver_send_probe(struct nameserver *const ns);

static void search_request_finished(struct evdns_request *const);

static int search_try_next(struct evdns_request *const req);

static struct request *search_request_new(struct evdns_base *base, struct evdns_request *handle, int type, const char *const name, int flags);

static void evdns_requests_pump_waiting_queue(struct evdns_base *base);

static u16 transaction_id_pick(struct evdns_base *base);

static struct request *request_new(struct evdns_base *base, struct evdns_request *handle, int type, const char *name, int flags);

static struct request *request_clone(struct evdns_base *base, struct request* current);

static void request_submit(struct request *const req);

static int server_request_free(struct server_request *req);

static void server_request_free_answers(struct server_request *req);

static void server_port_free(struct evdns_server_port *port);

static void server_port_ready_callback(evutil_socket_t fd, short events, void *arg);

static int evdns_base_resolv_conf_parse_impl(struct evdns_base *base, int flags, const char *const filename);

static int evdns_base_set_option_impl(struct evdns_base *base,

    const char *option, const char *val, int flags);

static void evdns_base_free_and_unlock(struct evdns_base *base, int fail_requests);

static void evdns_request_timeout_callback(evutil_socket_t fd, short events, void *arg);

static int evdns_server_request_format_response(struct server_request *req, int err);

static void incoming_conn_cb(struct evconnlistener *listener, evutil_socket_t fd,

    struct sockaddr *address, int socklen, void *arg);

static int strtoint(const char *const str);

#ifdef EVENT__DISABLE_THREAD_SUPPORT

#define EVDNS_LOCK(base)  EVUTIL_NIL_STMT_

#define EVDNS_UNLOCK(base) EVUTIL_NIL_STMT_

#define ASSERT_LOCKED(base) EVUTIL_NIL_STMT_

#else

#define EVDNS_LOCK(base)      \

  EVLOCK_LOCK((base)->lock, 0)

#define EVDNS_UNLOCK(base)      \

  EVLOCK_UNLOCK((base)->lock, 0)

#define ASSERT_LOCKED(base)     \

  EVLOCK_ASSERT_LOCKED((base)->lock)

#endif

static evdns_debug_log_fn_type evdns_log_fn = NULL;

void

evdns_set_log_fn(evdns_debug_log_fn_type fn)

{

  evdns_log_fn = fn;

}

#ifdef __GNUC__

#define EVDNS_LOG_CHECK  __attribute__ ((format(printf, 2, 3)))

#else

#define EVDNS_LOG_CHECK

#endif

static void evdns_log_(int severity, const char *fmt, ...) EVDNS_LOG_CHECK;

static void

evdns_log_(int severity, const char *fmt, ...)

{

  va_list args;

  va_start(args,fmt);

  if (evdns_log_fn) {

    char buf[512];

    int is_warn = (severity == EVDNS_LOG_WARN);

    evutil_vsnprintf(buf, sizeof(buf), fmt, args);

    evdns_log_fn(is_warn, buf);

  } else {

    event_logv_(severity, NULL, fmt, args);

  }

  va_end(args);

}

#define log evdns_log_

/* Initialize tcp_connection structure. */

static void

init_tcp_connection(struct tcp_connection *conn, struct bufferevent *bev)

{

  memset(conn, 0, sizeof(*conn));

  conn->state = TS_DISCONNECTED;

  conn->bev = bev;

  conn->awaiting_packet_size = 0;

}

/* Disconnect tcp connection. */

static void

evdns_tcp_disconnect(struct tcp_connection *conn)

{

  if (!conn)

    return;

  conn->state = TS_DISCONNECTED;

  conn->awaiting_packet_size = 0;

  if (conn->bev) {

    bufferevent_free(conn->bev);

    conn->bev = NULL;

  }

}

/* Add new tcp client to the list of TCP clients in the TCP DNS server. */

static struct client_tcp_connection*

evdns_add_tcp_client(struct evdns_server_port *port, struct bufferevent *bev)

{

  struct client_tcp_connection *client;

  EVUTIL_ASSERT(port && bev);

  if (port->max_client_connections == port->client_connections_count)

    goto error;

  client = mm_calloc(1, sizeof(*client));

  if (!client)

    goto error;

  init_tcp_connection(&client->connection, bev);

  client->port = port;

  LIST_INSERT_HEAD(&port->client_connections, client, next);

  ++port->client_connections_count;

  /* we need to hold evdns_server_port as long as one connection at least stays alive */

  ++port->refcnt;

  return client;

error:

  return NULL;

}

/* Remove tcp client and free all associated data from the TCP DNS server. */

static int

evdns_remove_tcp_client(struct evdns_server_port *port, struct client_tcp_connection *client)

{

  if (!port || !client)

    goto error;

  evdns_tcp_disconnect(&client->connection);

  LIST_REMOVE(client, next);

  mm_free(client);

  --port->client_connections_count;

  --port->refcnt;

  return 0;

error:

  return -1;

}

/* Remove all tcp clients and free all associated data from the TCP DNS server. */

static void

evdns_remove_all_tcp_clients(struct evdns_server_port *port)

{

  struct client_tcp_connection *client;

  while ((client = LIST_FIRST(&port->client_connections))) {

    evdns_remove_tcp_client(port, client);

  }

}

/* Create new tcp connection structure for DNS client. */

static struct tcp_connection *

new_tcp_connecton(struct bufferevent *bev)

{

  struct tcp_connection *conn;

  if (!bev)

    return NULL;

  conn = mm_calloc(1, sizeof(*conn));

  if (!conn)

    return NULL;

  init_tcp_connection(conn, bev);

  return conn;

}

/* Disconnect and free all associated data for the tcp connection in DNS client. */

static void

disconnect_and_free_connection(struct tcp_connection *conn)

{

  if (!conn)

    return;

  evdns_tcp_disconnect(conn);

  mm_free(conn);

}

/* This walks the list of inflight requests to find the */

/* one with a matching transaction id. Returns NULL on */

/* failure */

static struct request *

request_find_from_trans_id(struct evdns_base *base, u16 trans_id) {

  struct request *req = REQ_HEAD(base, trans_id);

  struct request *const started_at = req;

  ASSERT_LOCKED(base);

  if (req) {

    do {

      if (req->trans_id == trans_id) return req;

      req = req->next;

    } while (req != started_at);

  }

  return NULL;

}

/* a libevent callback function which is called when a nameserver */

/* has gone down and we want to test if it has came back to life yet */

static void

nameserver_prod_callback(evutil_socket_t fd, short events, void *arg) {

  struct nameserver *const ns = (struct nameserver *) arg;

  (void)fd;

  (void)events;

  EVDNS_LOCK(ns->base);

  nameserver_send_probe(ns);

  EVDNS_UNLOCK(ns->base);

}

/* a libevent callback which is called when a nameserver probe (to see if */

/* it has come back to life) times out. We increment the count of failed_times */

/* and wait longer to send the next probe packet. */

static void

nameserver_probe_failed(struct nameserver *const ns) {

  struct timeval timeout;

  int i;

  ASSERT_LOCKED(ns->base);

  (void) evtimer_del(&ns->timeout_event);

  if (ns->state == 1) {

    /* This can happen if the nameserver acts in a way which makes us mark */

    /* it as bad and then starts sending good replies. */

    return;

  }

  memcpy(&timeout, &ns->base->global_nameserver_probe_initial_timeout,

      sizeof(struct timeval));

  for (i = ns->failed_times; i > 0 && timeout.tv_sec < ns->base->ns_max_probe_timeout; --i) {

    timeout.tv_sec *= ns->base->ns_timeout_backoff_factor;

    timeout.tv_usec *= ns->base->ns_timeout_backoff_factor;

    if (timeout.tv_usec > 1000000) {

      timeout.tv_sec += timeout.tv_usec / 1000000;

      timeout.tv_usec %= 1000000;

    }

  }

  if (timeout.tv_sec > ns->base->ns_max_probe_timeout) {

    timeout.tv_sec = ns->base->ns_max_probe_timeout;

    timeout.tv_usec = 0;

  }

  ns->failed_times++;

  if (evtimer_add(&ns->timeout_event, &timeout) < 0) {

    char addrbuf[128];

    log(EVDNS_LOG_WARN,

        "Error from libevent when adding timer event for %s",

        evutil_format_sockaddr_port_(

          (struct sockaddr *)&ns->address,

          addrbuf, sizeof(addrbuf)));

  }

}

static void

request_swap_ns(struct request *req, struct nameserver *ns) {

  if (ns && req->ns != ns) {

    EVUTIL_ASSERT(req->ns->requests_inflight > 0);

    req->ns->requests_inflight--;

    ns->requests_inflight++;

    req->ns = ns;

  }

}

/* called when a nameserver has been deemed to have failed. For example, too */

/* many packets have timed out etc */

static void

nameserver_failed(struct nameserver *const ns, const char *msg, int err) {

  struct request *req, *started_at;

  struct evdns_base *base = ns->base;

  int i;

  char addrbuf[128];

  ASSERT_LOCKED(base);

  /* if this nameserver has already been marked as failed */

  /* then don't do anything */

  if (!ns->state) return;

  log(EVDNS_LOG_MSG, "Nameserver %s has failed: %s",

      evutil_format_sockaddr_port_(

        (struct sockaddr *)&ns->address,

        addrbuf, sizeof(addrbuf)),

      msg);

  base->global_good_nameservers--;

  EVUTIL_ASSERT(base->global_good_nameservers >= 0);

  if (base->global_good_nameservers == 0) {

    log(EVDNS_LOG_MSG, "All nameservers have failed");

  }

  ns->state = 0;

  ns->failed_times = 1;

  if (ns->connection) {

    disconnect_and_free_connection(ns->connection);

    ns->connection = NULL;

  } else if (err == ENOTCONN) {

    /* XXX: If recvfrom results in ENOTCONN, the socket remains readable

     * which triggers another recvfrom. The observed behavior is 100% CPU use.

     * This occurs on iOS (kqueue) after the process has been backgrounded

     * for a long time (~300 seconds) and then resumed.

     * All sockets, TCP and UDP, seem to get ENOTCONN and must be closed.

     * https://github.com/libevent/libevent/issues/265 */

    const struct sockaddr *address = (const struct sockaddr *)&ns->address;

    evutil_closesocket(ns->socket);

    ns->socket = evutil_socket_(address->sa_family,

      SOCK_DGRAM | EVUTIL_SOCK_NONBLOCK | EVUTIL_SOCK_CLOEXEC, 0);

    if (base->global_outgoing_addrlen &&

      !evutil_sockaddr_is_loopback_(address)) {

      if (bind(ns->socket,

          (struct sockaddr *)&base->global_outgoing_address,

          base->global_outgoing_addrlen) < 0) {

        log(EVDNS_LOG_WARN, "Couldn't bind to outgoing address");

      }

    }

    event_del(&ns->event);

    event_assign(&ns->event, ns->base->event_base, ns->socket,

      EV_READ | (ns->write_waiting ? EV_WRITE : 0) | EV_PERSIST,

      nameserver_ready_callback, ns);

    if (!base->disable_when_inactive && event_add(&ns->event, NULL) < 0) {

      log(EVDNS_LOG_WARN, "Couldn't add %s event",

        ns->write_waiting ? "rw": "read");

    }

  }

  if (evtimer_add(&ns->timeout_event,

    &base->global_nameserver_probe_initial_timeout) < 0) {

    log(EVDNS_LOG_WARN,

        "Error from libevent when adding timer event for %s",

        evutil_format_sockaddr_port_(

          (struct sockaddr *)&ns->address,

          addrbuf, sizeof(addrbuf)));

    /* ???? Do more? */

  }

  /* walk the list of inflight requests to see if any can be reassigned to */

  /* a different server. Requests in the waiting queue don't have a */

  /* nameserver assigned yet */

  /* if we don't have *any* good nameservers then there's no point */

  /* trying to reassign requests to one */

  if (!base->global_good_nameservers) return;

  for (i = 0; i < base->n_req_heads; ++i) {

    req = started_at = base->req_heads[i];

    if (req) {

      do {

        if (req->tx_count == 0 && req->ns == ns) {

          /* still waiting to go out, can be moved */

          /* to another server */

          request_swap_ns(req, nameserver_pick(base));

        }

        req = req->next;

      } while (req != started_at);

    }

  }

}

static void

nameserver_up(struct nameserver *const ns)

{

  char addrbuf[128];

  ASSERT_LOCKED(ns->base);

  if (ns->state) return;

  log(EVDNS_LOG_MSG, "Nameserver %s is back up",

      evutil_format_sockaddr_port_(

        (struct sockaddr *)&ns->address,

        addrbuf, sizeof(addrbuf)));

  evtimer_del(&ns->timeout_event);

  if (ns->probe_request) {

    evdns_cancel_request(ns->base, ns->probe_request);

    ns->probe_request = NULL;

  }

  ns->state = 1;

  ns->failed_times = 0;

  ns->timedout = 0;

  ns->base->global_good_nameservers++;

}

static void

request_trans_id_set(struct request *const req, const u16 trans_id) {

  req->trans_id = trans_id;

  *((u16 *) req->request) = htons(trans_id);

}

/* Called to remove a request from a list and dealloc it. */

/* head is a pointer to the head of the list it should be */

/* removed from or NULL if the request isn't in a list. */

/* when free_handle is one, free the handle as well. */

static void

request_finished(struct request *const req, struct request **head, int free_handle) {

  struct evdns_base *base = req->base;

  int was_inflight = (head != &base->req_waiting_head);

  EVDNS_LOCK(base);

  ASSERT_VALID_REQUEST(req);

  if (head)

    evdns_request_remove(req, head);

  log(EVDNS_LOG_DEBUG, "Removing timeout for request %p", (void *)req);

  if (was_inflight) {

    evtimer_del(&req->timeout_event);

    base->global_requests_inflight--;

    req->ns->requests_inflight--;

  } else {

    base->global_requests_waiting--;

  }

  /* it was initialized during request_new / evtimer_assign */

  event_debug_unassign(&req->timeout_event);

  if (req->ns &&

      req->ns->requests_inflight == 0 &&

      req->base->disable_when_inactive) {

    event_del(&req->ns->event);

    evtimer_del(&req->ns->timeout_event);

  }

  if (!req->request_appended) {

    /* need to free the request data on it's own */

    mm_free(req->request);

  } else {

    /* the request data is appended onto the header */

    /* so everything gets free()ed when we: */

  }

  if (req->handle) {

    EVUTIL_ASSERT(req->handle->current_req == req);

    if (free_handle) {

      search_request_finished(req->handle);

      req->handle->current_req = NULL;

      if (! req->handle->pending_cb) {

        /* If we're planning to run the callback,

         * don't free the handle until later. */

        mm_free(req->handle);

      }

      req->handle = NULL; /* If we have a bug, let's crash

               * early */

    } else {

      req->handle->current_req = NULL;

    }

  }

  mm_free(req);

  evdns_requests_pump_waiting_queue(base);

  EVDNS_UNLOCK(base);

}

/* This is called when a server returns a funny error code. */

/* We try the request again with another server. */

/* */

/* return: */

/*   0 ok */

/*   1 failed/reissue is pointless */

static int

request_reissue(struct request *req) {

  const struct nameserver *const last_ns = req->ns;

  ASSERT_LOCKED(req->base);

  ASSERT_VALID_REQUEST(req);

  /* the last nameserver should have been marked as failing */

  /* by the caller of this function, therefore pick will try */

  /* not to return it */

  request_swap_ns(req, nameserver_pick(req->base));

  if (req->ns == last_ns) {

    /* ... but pick did return it */

    /* not a lot of point in trying again with the */

    /* same server */

    return 1;

  }

  req->reissue_count++;

  req->tx_count = 0;

  req->transmit_me = 1;

  return 0;

}

/* this function looks for space on the inflight queue and promotes */

/* requests from the waiting queue if it can. */

/* */

/* TODO: */

/* add return code, see at nameserver_pick() and other functions. */

static void

evdns_requests_pump_waiting_queue(struct evdns_base *base) {

  ASSERT_LOCKED(base);

  while (base->global_requests_inflight < base->global_max_requests_inflight &&

       base->global_requests_waiting) {

    struct request *req;

    EVUTIL_ASSERT(base->req_waiting_head);

    req = base->req_waiting_head;

    req->ns = nameserver_pick(base);

    if (!req->ns)

      return;

    /* move a request from the waiting queue to the inflight queue */

    req->ns->requests_inflight++;

    evdns_request_remove(req, &base->req_waiting_head);

    base->global_requests_waiting--;

    base->global_requests_inflight++;

    request_trans_id_set(req, transaction_id_pick(base));

    evdns_request_insert(req, &REQ_HEAD(base, req->trans_id));

    evdns_request_transmit(req);

    evdns_transmit(base);

  }

}

static void

reply_run_callback(struct event_callback *d, void *user_pointer)

{

  struct evdns_request *handle =

      EVUTIL_UPCAST(d, struct evdns_request, deferred);

  switch (handle->request_type) {

  case TYPE_A:

    if (handle->have_reply) {