[Libevent-users] [patch] replace linear search in evdns with
hashed list and add support of listening on unix sockets for evhttp
Vsevolod Stakhov
vsevolod at highsecure.ru
Mon Feb 18 10:56:16 EST 2008
Vsevolod Stakhov wrote:
> nickm at freehaven.net wrote:
>> On Fri, Feb 15, 2008 at 07:22:34PM +0300, Vsevolod Stakhov wrote:
>>> Hi,
>>>
>>> We found a problem with list requests_inflight while using evdns on
>>> highly loaded system (about 2000 DNS requests per second). First of
>>> all linear search is slow and second is that this list is not big
>>> enough to handle all requests, so many requests were in
>>> requests_waiting list, that has no limits on length. Due to this
>>> application grows in size constantly and is not able to serve
>>> requests. I've replaced linear list with hashed list, that improves
>>> performance.
>>
>> Hi! This looks pretty good. I'd like to apply it for trunk to apply
>> it to the next release after 1.4. (I want to avoid applying anything
>> but straight bugfixes to 1.4 at this point, so that it can get out of
>> beta soon.) A few comments and questions:
>> ...
I've made some modifications to patch to attract your wishes, thought
I've not tested it in production yet.
-------------- next part --------------
diff -r 2609c564f854 -r d3e5ec3459f9 evdns.c
--- a/evdns.c Mon Feb 18 18:55:03 2008 +0300
+++ b/evdns.c Wed Feb 13 15:31:39 2008 +0300
@@ -231,7 +231,7 @@ struct nameserver {
char write_waiting; /* true if we are waiting for EV_WRITE events */
};
-static struct request **req_head = NULL, *req_waiting_head = NULL;
+static struct request *req_head = NULL, *req_waiting_head = NULL;
static struct nameserver *server_head = NULL;
/* Represents a local port where we're listening for DNS requests. Right now, */
@@ -310,9 +310,7 @@ static int global_requests_inflight = 0;
/* and are counted here */
static int global_requests_waiting = 0;
-static int global_max_requests_inflight = 1024;
-/* numbers of nests in hashed list of pending requests */
-static int global_max_nests = 128;
+static int global_max_requests_inflight = 64;
static struct timeval global_timeout = {5, 0}; /* 5 seconds */
static int global_max_reissues = 1; /* a reissue occurs when we get some errors from the server */
@@ -445,16 +443,13 @@ _evdns_log(int warn, const char *fmt, ..
/* failure */
static struct request *
request_find_from_trans_id(u16 trans_id) {
- struct request *req, *started_at;
- if (req_head) {
- req = req_head[trans_id % global_max_nests];
- started_at = req_head[trans_id % global_max_nests];
- if (req) {
- do {
- if (req->trans_id == trans_id) return req;
- req = req->next;
- } while (req != started_at);
- }
+ struct request *req = req_head, *const started_at = req_head;
+
+ if (req) {
+ do {
+ if (req->trans_id == trans_id) return req;
+ req = req->next;
+ } while (req != started_at);
}
return NULL;
@@ -503,7 +498,6 @@ static void
static void
nameserver_failed(struct nameserver *const ns, const char *msg) {
struct request *req, *started_at;
- int i;
/* if this nameserver has already been marked as failed */
/* then don't do anything */
if (!ns->state) return;
@@ -533,21 +527,19 @@ nameserver_failed(struct nameserver *con
/* if we don't have *any* good nameservers then there's no point */
/* trying to reassign requests to one */
- if (!global_good_nameservers || !req_head) return;
-
- for (i = 0; i < global_max_nests; i ++) {
- req = req_head[i];
- started_at = req_head[i];
- if (req) {
- do {
- if (req->tx_count == 0 && req->ns == ns) {
- /* still waiting to go out, can be moved */
- /* to another server */
- req->ns = nameserver_pick();
- }
- req = req->next;
- } while (req != started_at);
- }
+ if (!global_good_nameservers) return;
+
+ req = req_head;
+ started_at = req_head;
+ if (req) {
+ do {
+ if (req->tx_count == 0 && req->ns == ns) {
+ /* still waiting to go out, can be moved */
+ /* to another server */
+ req->ns = nameserver_pick();
+ }
+ req = req->next;
+ } while (req != started_at);
}
}
@@ -657,10 +649,8 @@ evdns_requests_pump_waiting_queue(void)
req->ns = nameserver_pick();
request_trans_id_set(req, transaction_id_pick());
-
- if (req_head) {
- evdns_request_insert(req, &req_head[req->trans_id % global_max_nests]);
- }
+
+ evdns_request_insert(req, &req_head);
evdns_request_transmit(req);
evdns_transmit();
}
@@ -752,25 +742,19 @@ reply_handle(struct request *const req,
/* a new request was issued so this request is finished and */
/* the user callback will be made when that request (or a */
/* child of it) finishes. */
- if (req_head) {
- request_finished(req, &req_head[req->trans_id % global_max_nests]);
- }
+ request_finished(req, &req_head);
return;
}
}
/* all else failed. Pass the failure up */
reply_callback(req, 0, error, NULL);
- if (req_head) {
- request_finished(req, &req_head[req->trans_id % global_max_nests]);
- }
+ request_finished(req, &req_head);
} else {
/* all ok, tell the user */
reply_callback(req, ttl, 0, reply);
nameserver_up(req->ns);
- if (req_head) {
- request_finished(req, &req_head[req->trans_id % global_max_nests]);
- }
+ request_finished(req, &req_head);
}
}
@@ -1106,14 +1090,12 @@ static u16
static u16
transaction_id_pick(void) {
for (;;) {
- const struct request *req = NULL, *started_at = NULL;
+ const struct request *req = req_head, *started_at;
u16 trans_id = trans_id_function();
if (trans_id == 0xffff) continue;
/* now check to see if that id is already inflight */
- if (req_head) {
- req = started_at = req_head[trans_id % global_max_nests];
- }
+ req = started_at = req_head;
if (req) {
do {
if (req->trans_id == trans_id) break;
@@ -1887,9 +1869,7 @@ evdns_request_timeout_callback(int fd, s
if (req->tx_count >= global_max_retransmits) {
/* this request has failed */
reply_callback(req, 0, DNS_ERR_TIMEOUT, NULL);
- if (req_head) {
- request_finished(req, &req_head[req->trans_id % global_max_nests]);
- }
+ request_finished(req, &req_head);
} else {
/* retransmit it */
evdns_request_transmit(req);
@@ -2001,22 +1981,19 @@ nameserver_send_probe(struct nameserver
/* 1 tried to transmit something */
static int
evdns_transmit(void) {
- int i;
char did_try_to_transmit = 0;
-
- for (i = 0; i < global_max_nests; i ++) {
- if (req_head && req_head[i]) {
- struct request *const started_at = req_head[i], *req = req_head[i];
- /* first transmit all the requests which are currently waiting */
- do {
- if (req->transmit_me) {
- did_try_to_transmit = 1;
- evdns_request_transmit(req);
- }
-
- req = req->next;
- } while (req != started_at);
- }
+
+ if (req_head) {
+ struct request *const started_at = req_head, *req = req_head;
+ /* first transmit all the requests which are currently waiting */
+ do {
+ if (req->transmit_me) {
+ did_try_to_transmit = 1;
+ evdns_request_transmit(req);
+ }
+
+ req = req->next;
+ } while (req != started_at);
}
return did_try_to_transmit;
@@ -2042,8 +2019,7 @@ evdns_clear_nameservers_and_suspend(void
evdns_clear_nameservers_and_suspend(void)
{
struct nameserver *server = server_head, *started_at = server_head;
- struct request *req, *req_started_at;
- int i;
+ struct request *req = req_head, *req_started_at = req_head;
if (!server)
return 0;
@@ -2060,37 +2036,29 @@ evdns_clear_nameservers_and_suspend(void
}
server_head = NULL;
global_good_nameservers = 0;
-
- if (req_head) {
- for (i = 0; i < global_max_nests; i ++) {
- req = req_head[i];
- req_started_at = req;
-
- while (req) {
- struct request *next = req->next;
- req->tx_count = req->reissue_count = 0;
- req->ns = NULL;
- /* ???? What to do about searches? */
- (void) evtimer_del(&req->timeout_event);
- req->trans_id = 0;
- req->transmit_me = 0;
-
- global_requests_waiting++;
- evdns_request_insert(req, &req_waiting_head);
- /* We want to insert these suspended elements at the front of
- * the waiting queue, since they were pending before any of
- * the waiting entries were added. This is a circular list,
- * so we can just shift the start back by one.*/
- req_waiting_head = req_waiting_head->prev;
-
- if (next == req_started_at)
- break;
- req = next;
- }
- req_head[i] = NULL;
- }
- }
-
+
+ while (req) {
+ struct request *next = req->next;
+ req->tx_count = req->reissue_count = 0;
+ req->ns = NULL;
+ /* ???? What to do about searches? */
+ (void) evtimer_del(&req->timeout_event);
+ req->trans_id = 0;
+ req->transmit_me = 0;
+
+ global_requests_waiting++;
+ evdns_request_insert(req, &req_waiting_head);
+ /* We want to insert these suspended elements at the front of
+ * the waiting queue, since they were pending before any of
+ * the waiting entries were added. This is a circular list,
+ * so we can just shift the start back by one.*/
+ req_waiting_head = req_waiting_head->prev;
+
+ if (next == req_started_at)
+ break;
+ req = next;
+ }
+ req_head = NULL;
global_requests_inflight = 0;
return 0;
@@ -2277,9 +2245,7 @@ request_submit(struct request *const req
if (req->ns) {
/* if it has a nameserver assigned then this is going */
/* straight into the inflight queue */
- if (req_head) {
- evdns_request_insert(req, &req_head[req->trans_id % global_max_nests]);
- }
+ evdns_request_insert(req, &req_head);
global_requests_inflight++;
evdns_request_transmit(req);
} else {
@@ -2681,9 +2647,6 @@ evdns_set_option(const char *option, con
log(EVDNS_LOG_DEBUG, "Setting maximum inflight requests to %d",
maxinflight);
global_max_requests_inflight = maxinflight;
- global_max_nests = global_max_requests_inflight / 10;
- req_head = realloc (req_head, global_max_nests * sizeof (req_head[0]));
- if (req_head == NULL) return -1;
} else if (!strncmp(option, "attempts:", 9)) {
int retries = strtoint(val);
if (retries == -1) return -1;
@@ -2751,7 +2714,7 @@ evdns_resolv_conf_parse(int flags, const
u8 *resolv;
char *start;
int err = 0;
-
+
log(EVDNS_LOG_DEBUG, "Parsing resolv.conf file %s", filename);
fd = open(filename, O_RDONLY);
@@ -3003,28 +2966,9 @@ evdns_config_windows_nameservers(void)
#endif
int
-evdns_requests_list_init(void)
-{
- if (req_head == NULL) {
- req_head = malloc (global_max_nests * sizeof (req_head[0]));
- if (req_head == NULL) {
- return 4;
- }
- memset (req_head, 0, global_max_nests * sizeof (req_head[0]));
- }
-
- return 0;
-}
-
-int
evdns_init(void)
{
int res = 0;
-
- res = evdns_requests_list_init();
- if (res != 0) {
- return res;
- }
#ifdef WIN32
res = evdns_config_windows_nameservers();
#else
@@ -3058,14 +3002,11 @@ evdns_shutdown(int fail_requests)
{
struct nameserver *server, *server_next;
struct search_domain *dom, *dom_next;
- int i;
-
- for (i = 0; i < global_max_nests; i ++) {
- while (req_head && req_head[i]) {
- if (fail_requests)
- reply_callback(req_head[i], 0, DNS_ERR_SHUTDOWN, NULL);
- request_finished(req_head[i], &req_head[i]);
- }
+
+ while (req_head) {
+ if (fail_requests)
+ reply_callback(req_head, 0, DNS_ERR_SHUTDOWN, NULL);
+ request_finished(req_head, &req_head);
}
while (req_waiting_head) {
if (fail_requests)
diff -r 2609c564f854 -r d3e5ec3459f9 http.c
--- a/http.c Mon Feb 18 18:55:03 2008 +0300
+++ b/http.c Wed Feb 13 15:31:39 2008 +0300
@@ -78,9 +78,6 @@
#ifdef HAVE_FCNTL_H
#include <fcntl.h>
#endif
-#ifndef WIN32
-#include <sys/un.h>
-#endif
#undef timeout_pending
#undef timeout_initialized
@@ -2352,25 +2349,18 @@ name_from_addr(struct sockaddr *sa, sock
static char ntop[NI_MAXHOST];
static char strport[NI_MAXSERV];
int ni_result;
-
- if (sa->sa_family == PF_UNIX) {
- strncpy (ntop, ((struct sockaddr_un *)sa)->sun_path, NI_MAXHOST - 1);
- strport[0] = '0';
- strport[1] = '\0';
- }
- else {
- if ((ni_result = getnameinfo(sa, salen,
- ntop, sizeof(ntop), strport, sizeof(strport),
- NI_NUMERICHOST|NI_NUMERICSERV)) != 0) {
- if (ni_result == EAI_SYSTEM)
- event_err(1, "getnameinfo failed");
- else
- event_errx(1, "getnameinfo failed: %s", gai_strerror(ni_result));
- }
- }
+
+ if ((ni_result = getnameinfo(sa, salen,
+ ntop, sizeof(ntop), strport, sizeof(strport),
+ NI_NUMERICHOST|NI_NUMERICSERV)) != 0) {
+ if (ni_result == EAI_SYSTEM)
+ event_err(1, "getnameinfo failed");
+ else
+ event_errx(1, "getnameinfo failed: %s", gai_strerror(ni_result));
+ }
+
*phost = ntop;
*pport = strport;
-
#else
/* XXXX */
#endif
diff -r 2609c564f854 -r d3e5ec3459f9 test/regress_dns.c
--- a/test/regress_dns.c Mon Feb 18 18:55:03 2008 +0300
+++ b/test/regress_dns.c Wed Feb 13 15:31:39 2008 +0300
@@ -67,7 +67,6 @@ static int dns_err = 0;
static int dns_err = 0;
void dns_suite(void);
-int evdns_requests_list_init(void);
static void
dns_gethostbyname_cb(int result, char type, int count, int ttl,
@@ -304,11 +303,6 @@ dns_server(void)
dns_ok = 1;
fprintf(stdout, "DNS server support: ");
- if (evdns_requests_list_init() != 0) {
- fprintf(stdout, "Couldn't init dns requests hash list.\n");
- exit(1);
- }
-
/* Add ourself as the only nameserver, and make sure we really are
* the only nameserver. */
evdns_nameserver_ip_add("127.0.0.1:35353");
@@ -372,8 +366,8 @@ dns_suite(void)
dns_suite(void)
{
dns_server(); /* Do this before we call evdns_init. */
+
evdns_init();
-
dns_gethostbyname();
dns_gethostbyname6();
dns_gethostbyaddr();
More information about the Libevent-users
mailing list