Previously, processing a large batch of timeouts was O(n^2) in the number of

outstanding queries, and processing a DNS response packet was O(n) in the
number of outstanding queries. To speed things up in Google, we added a few circular,
doubly-linked lists of queries that are hash-bucketed based on
the attributes we care about, so most important operations are now O(1).

It might be that the number of buckets are higher than most people would need,
but on a quick calculation it should only be 100kB or so even on a 64-bit
system, so I've let it stay as-is.

1 files changed, 107 insertions, 5 deletions

diff --git a/ares_private.h b/ares_private.h
index e6ecaa2..34e4692 100644
--- a/ares_private.h
+++ b/ares_private.h
@@ -84,6 +84,15 @@
 
 #include "ares_ipv6.h"
 
+struct query;
+
+/* Node definition for circular, doubly-linked list */
+struct list_node {
+  struct list_node *prev;
+  struct list_node *next;
+  void* data;
+};
+
 struct send_request {
   /* Remaining data to send */
   const unsigned char *data;
@@ -122,17 +131,35 @@ struct server_state {
    * re-send. */
   int tcp_connection_generation;
 
+  /* Circular, doubly-linked list of outstanding queries to this server */
+  struct list_node queries_to_server;
+
+  /* Link back to owning channel */
+  ares_channel channel;
+
   /* Is this server broken? We mark connections as broken when a
    * request that is queued for sending times out.
    */
   int is_broken;
 };
 
+/* State to represent a DNS query */
 struct query {
   /* Query ID from qbuf, for faster lookup, and current timeout */
   unsigned short qid;
   time_t timeout;
 
+  /*
+   * Links for the doubly-linked lists in which we insert a query.
+   * These circular, doubly-linked lists that are hash-bucketed based
+   * the attributes we care about, help making most important
+   * operations O(1).
+   */
+  struct list_node queries_by_qid;    /* hopefully in same cache line as qid */
+  struct list_node queries_by_timeout;
+  struct list_node queries_to_server;
+  struct list_node all_queries;
+
   /* Query buf with length at beginning, for TCP transmission */
   unsigned char *tcpbuf;
   int tcplen;
@@ -149,9 +176,6 @@ struct query {
   struct query_server_info *server_info;   /* per-server state */
   int using_tcp;
   int error_status;
-
-  /* Next query in chain */
-  struct query *next;
   int timeouts; /* number of timeouts we saw for this request */
 };
 
@@ -216,8 +240,18 @@ struct ares_channeldata {
   /* Generation number to use for the next TCP socket open/close */
   int tcp_connection_generation;
 
-  /* Active queries */
-  struct query *queries;
+  /* The time at which we last called process_timeouts() */
+  time_t last_timeout_processed;
+
+  /* Circular, doubly-linked list of queries, bucketed various ways.... */
+  /* All active queries in a single list: */
+  struct list_node all_queries;
+  /* Queries bucketed by qid, for quickly dispatching DNS responses: */
+#define ARES_QID_TABLE_SIZE 2048
+  struct list_node queries_by_qid[ARES_QID_TABLE_SIZE];
+  /* Queries bucketed by timeout, for quickly handling timeouts: */
+#define ARES_TIMEOUT_TABLE_SIZE 1024
+  struct list_node queries_by_timeout[ARES_TIMEOUT_TABLE_SIZE];
 
   ares_sock_state_cb sock_state_cb;
   void *sock_state_cb_data;
@@ -228,8 +262,76 @@ void ares__send_query(ares_channel channel, struct query *query, time_t now);
 void ares__close_sockets(ares_channel channel, struct server_state *server);
 int ares__get_hostent(FILE *fp, int family, struct hostent **host);
 int ares__read_line(FILE *fp, char **buf, int *bufsize);
+void ares__free_query(struct query *query);
 short ares__generate_new_id(rc4_key* key);
 
+
+/* Routines for managing doubly-linked circular linked lists with a
+ * dummy head.
+ */
+
+/* Initialize a new head node */
+static inline void ares__init_list_head(struct list_node* head) {
+  head->prev = head;
+  head->next = head;
+  head->data = NULL;
+}
+
+/* Initialize a list node */
+static inline void ares__init_list_node(struct list_node* node, void* d) {
+  node->prev = NULL;
+  node->next = NULL;
+  node->data = d;
+}
+
+/* Returns true iff the given list is empty */
+static inline int ares__is_list_empty(struct list_node* head) {
+  return ((head->next == head) && (head->prev == head));
+}
+
+/* Inserts new_node before old_node */
+static inline void ares__insert_in_list(struct list_node* new_node,
+                                        struct list_node* old_node) {
+  new_node->next = old_node;
+  new_node->prev = old_node->prev;
+  old_node->prev->next = new_node;
+  old_node->prev = new_node;
+}
+
+/* Removes the node from the list it's in, if any */
+static inline void ares__remove_from_list(struct list_node* node) {
+  if (node->next != NULL) {
+    node->prev->next = node->next;
+    node->next->prev = node->prev;
+    node->prev = NULL;
+    node->next = NULL;
+  }
+}
+
+/* Swap the contents of two lists */
+static inline void ares__swap_lists(struct list_node* head_a,
+                                    struct list_node* head_b) {
+  int is_a_empty = ares__is_list_empty(head_a);
+  int is_b_empty = ares__is_list_empty(head_b);
+  struct list_node old_a = *head_a;
+  struct list_node old_b = *head_b;
+
+  if (is_a_empty) {
+    ares__init_list_head(head_b);
+  } else {
+    *head_b = old_a;
+    old_a.next->prev = head_b;
+    old_a.prev->next = head_b;
+  }
+  if (is_b_empty) {
+    ares__init_list_head(head_a);
+  } else {
+    *head_a = old_b;
+    old_b.next->prev = head_a;
+    old_b.prev->next = head_a;
+  }
+}
+
 #define ARES_SWAP_BYTE(a,b) \
   { unsigned char swapByte = *(a);  *(a) = *(b);  *(b) = swapByte; }