cURL / Mailing Lists / curl-library / Single Mail

curl-library

Busy looping bug in multi_socket interface

From: Christopher Palow <cpalow_at_facebook.com>
Date: Mon, 28 Apr 2008 19:52:20 -0700

Hi all,

I discovered a bug when using the multi socket interface which is pretty
easy to reproduce with a connect timeout of 1 second and trying to access a
site over the Internet.

The timeout splay treešs key, which servers as a queue of timeouts, only has
second granularity. When a timeout (in this case a connection timeout) is
less than a second in the future and less than the time till the next whole
second, Curl_is_connected() will reinsert this connection to the front of
the queue with a call to Curl_expire(). This can cause busy looping of
poll() until a connect() succeeds or wešve busy looped long enough that the
connection timeout expired. Busy looping for up to a second is no fun. We
may also want to bound the number of iterations in the timeout loop of
multi_socket() to detect other possible busy loops.

Gettimeofdays()s removed
     0.000055 socket(PF_INET, SOCK_STREAM, IPPROTO_TCP) = 429
     0.000055 fcntl64(429, F_GETFL) = 0x2 (flags O_RDWR)
     0.000046 fcntl64(429, F_SETFL, O_RDWR|O_NONBLOCK) = 0
     0.000050 connect(429, {sa_family=AF_INET, sin_port=htons(80),
sin_addr=inet_addr("69.63.176.143")}, 16) = -1 EINPROGRESS (Operation now in
progress)
     0.000088 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
     0.000057 epoll_ctl(3, EPOLL_CTL_ADD, 429, {EPOLLOUT|EPOLLERR|EPOLLHUP,
{u32=148080904, u64=148080904}}) = 0
     0.000055 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
     0.000050 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
<snip a bunch>
     0.000084 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
     0.000051 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
     0.000050 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
     0.000076 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0
     0.000050 poll([{fd=429, events=POLLOUT|POLLWRNORM}], 1, 0) = 0

My proposed fix is to make the splay treešs key be in microseconds instead
of seconds. Thoughts?

Thanks,
Chris Palow

Index: multi.c
===================================================================
RCS file: /cvsroot/curl/curl/lib/multi.c,v
retrieving revision 1.167
diff -u -w -p -r1.167 multi.c
--- multi.c 18 Mar 2008 08:14:37 -0000 1.167
+++ multi.c 29 Apr 2008 02:21:57 -0000
@@ -177,7 +177,7 @@ struct Curl_multi {
   /* timer callback and user data pointer for the *socket() API */
   curl_multi_timer_callback timer_cb;
   void *timer_userp;
- time_t timer_lastcall; /* the fixed time for the timeout for the previous
+ int64_t timer_lastcall; /* the fixed time for the timeout for the
previous
                             callback */
 };
 
@@ -1442,7 +1442,7 @@ CURLMcode curl_multi_perform(CURLM *mult
    */
   do {
     struct timeval now = Curl_tvnow();
- int key = now.tv_sec; /* drop the usec part */
+ int64_t key = now.tv_sec * 1000000 + now.tv_usec;
 
     multi->timetree = Curl_splaygetbest(key, multi->timetree, &t);
     if(t) {
@@ -1742,7 +1742,7 @@ static CURLMcode multi_socket(struct Cur
    * handle we deal with.
    */
   do {
- int key;
+ int64_t key;
     struct timeval now;
 
     /* the first loop lap 'data' can be NULL */
@@ -1759,7 +1759,7 @@ static CURLMcode multi_socket(struct Cur
        extracts a matching node if there is one */
 
     now = Curl_tvnow();
- key = now.tv_sec; /* drop the usec part */
+ key = now.tv_sec * 1000000 + now.tv_usec;
 
     multi->timetree = Curl_splaygetbest(key, multi->timetree, &t);
     if(t) {
@@ -1851,8 +1851,8 @@ CURLMcode curl_multi_socket_all(CURLM *m
   return result;
 }
 
-static CURLMcode multi_timeout(struct Curl_multi *multi,
- long *timeout_ms)
+static CURLMcode multi_timeout_usec(struct Curl_multi *multi,
+ long *timeout_us)
 {
   if(multi->timetree) {
     /* we have a tree of expire times */
@@ -1861,15 +1861,31 @@ static CURLMcode multi_timeout(struct Cu
     /* splay the lowest to the bottom */
     multi->timetree = Curl_splay(0, multi->timetree);
 
- /* At least currently, the splay key is a time_t for the expire time */
- *timeout_ms = (multi->timetree->key - now.tv_sec) * 1000 -
- now.tv_usec/1000;
- if(*timeout_ms < 0)
+ /* At least currently, the splay key is the microseconds of the expire
time */
+ *timeout_us = multi->timetree->key - (now.tv_sec * 1000000 +
now.tv_usec);
+
+ if(*timeout_us < 0)
       /* 0 means immediately */
- *timeout_ms = 0;
+ *timeout_us = 0;
   }
   else
- *timeout_ms = -1;
+ *timeout_us = -1;
+
+ return CURLM_OK;
+}
+
+
+static CURLMcode multi_timeout(struct Curl_multi *multi,
+ long *timeout_ms)
+{
+ long timeout_us;
+
+ multi_timeout_usec(multi, &timeout_us);
+
+ if(timeout_us > 0) /* convert to milliseconds */
+ *timeout_ms=timeout_us/1000;
+ else /* immediately or error condition */
+ *timeout_ms=timeout_us;
 
   return CURLM_OK;
 }
@@ -2014,6 +2030,7 @@ void Curl_expire(struct SessionHandle *d
   else {
     struct timeval set;
     int rest;
+ int64_t key;
 
     set = Curl_tvnow();
     set.tv_sec += milli/1000;
@@ -2050,8 +2067,8 @@ void Curl_expire(struct SessionHandle *d
           (long)nowp->tv_sec, (long)nowp->tv_usec, milli);
 #endif
     data->state.timenode.payload = data;
- multi->timetree = Curl_splayinsert((int)nowp->tv_sec,
- multi->timetree,
+ key = nowp->tv_sec * 1000000 + nowp->tv_usec;
+ multi->timetree = Curl_splayinsert(key, multi->timetree,
                                        &data->state.timenode);
   }
 #if 0
Index: splay.c
===================================================================
RCS file: /cvsroot/curl/curl/lib/splay.c,v
retrieving revision 1.8
diff -u -w -p -r1.8 splay.c
--- splay.c 5 Nov 2007 09:45:09 -0000 1.8
+++ splay.c 29 Apr 2008 02:21:58 -0000
@@ -37,10 +37,10 @@
  * Splay using the key i (which may or may not be in the tree.) The
starting
  * root is t.
  */
-struct Curl_tree *Curl_splay(int i, struct Curl_tree *t)
+struct Curl_tree *Curl_splay(int64_t i, struct Curl_tree *t)
 {
   struct Curl_tree N, *l, *r, *y;
- int comp;
+ int64_t comp;
 
   if(t == NULL)
     return t;
@@ -93,7 +93,7 @@ struct Curl_tree *Curl_splay(int i, stru
 
 /* Insert key i into the tree t. Return a pointer to the resulting tree or
    NULL if something went wrong. */
-struct Curl_tree *Curl_splayinsert(int i,
+struct Curl_tree *Curl_splayinsert(int64_t i,
                                    struct Curl_tree *t,
                                    struct Curl_tree *node)
 {
@@ -149,7 +149,7 @@ struct Curl_tree *Curl_splayinsert(int i
 
    Function not used in libcurl.
 */
-struct Curl_tree *Curl_splayremove(int i, struct Curl_tree *t,
+struct Curl_tree *Curl_splayremove(int64_t i, struct Curl_tree *t,
                                    struct Curl_tree **removed)
 {
   struct Curl_tree *x;
@@ -194,7 +194,7 @@ struct Curl_tree *Curl_splayremove(int i
 
 /* Finds and deletes the best-fit node from the tree. Return a pointer to
the
    resulting tree. best-fit means the node with the given or lower number
*/
-struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t,
+struct Curl_tree *Curl_splaygetbest(int64_t i, struct Curl_tree *t,
                                     struct Curl_tree **removed)
 {
   struct Curl_tree *x;
Index: splay.h
===================================================================
RCS file: /cvsroot/curl/curl/lib/splay.h,v
retrieving revision 1.4
diff -u -w -p -r1.4 splay.h
--- splay.h 27 Sep 2007 01:45:23 -0000 1.4
+++ splay.h 29 Apr 2008 02:21:58 -0000
@@ -27,19 +27,19 @@ struct Curl_tree {
   struct Curl_tree *smaller; /* smaller node */
   struct Curl_tree *larger; /* larger node */
   struct Curl_tree *same; /* points to a node with identical key */
- int key; /* the "sort" key */
+ int64_t key; /* the "sort" key */
   void *payload; /* data the splay code doesn't care about */
 };
 
-struct Curl_tree *Curl_splay(int i, struct Curl_tree *t);
-struct Curl_tree *Curl_splayinsert(int key, struct Curl_tree *t,
+struct Curl_tree *Curl_splay(int64_t i, struct Curl_tree *t);
+struct Curl_tree *Curl_splayinsert(int64_t key, struct Curl_tree *t,
                                    struct Curl_tree *newnode);
 #if 0
-struct Curl_tree *Curl_splayremove(int key, struct Curl_tree *t,
+struct Curl_tree *Curl_splayremove(int64_t key, struct Curl_tree *t,
                                    struct Curl_tree **removed);
 #endif
 
-struct Curl_tree *Curl_splaygetbest(int key, struct Curl_tree *t,
+struct Curl_tree *Curl_splaygetbest(int64_t key, struct Curl_tree *t,
                                     struct Curl_tree **removed);
 int Curl_splayremovebyaddr(struct Curl_tree *t,
                            struct Curl_tree *removenode,
Received on 2008-04-29