On Wed, 17 May 2006, Xavier Bouchoux wrote:

> ok, I got some more time to debug it.

Goodie. I believe this is last remaining issue before I can release 7.15.4.

> so, the culprit (that turns a nice tree into a recursive one) is the
> last call to
> multi->timetree = Curl_splayinsert((int)nowp->tv_sec,
> multi->timetree,
> &data->state.timenode);
> in Curl_expire()
>
> I don't really know what splay trees are, but in Curl_splayinsert()
> I think the case /* it already exists one of this size */
> will produce the situation if t = Curl_splay(i,t) is the same as area.

I'll do a quick explain what the splays are and why the code is there and
what's it supposed to do.

Splay trees are basically a tree instead of a simple linked list. In the splay
tree each node is added to the tree with a value (the actual expire time) and
"bigger" and "smaller" branch. So, walking through the tree to find a specific
value is a lot quicker compared to using plain linked lists.

The Curl_expire() logic is there to make a multi handle keep a tree of expire
timers (one for each easy handle) so that Curl_multi_timeout() can return the
lowest number on the demand.

So, when Curl_expire() is called to set a (new) expire time it sets a relative
time from now, like expire in N milliseconds:
  1. The relative time is converted to an absolute time
  2. See if the new time is earlier than the already set time for this handle,
     or else we just return
  3. remove the existing node for this handle from the splay tree
  4. add a new node to the splay tree with the new expire time

> in anycase, the end of the log looks like this:
> ("before the 2nd call to splay in function xxx" --> SPLAY xxx<<< ,
> after --> SPLAY xxx>>>)
>
> SPLAY curl_expire3<<<
> 1147883470[0]
> SPLAY curl_expire3>>>
> 1147883470[0] [+]
> SPLAY curl_expire2<<<
> 1147883470[0] [+]
> SPLAY curl_expire2>>>
> 1147883470[0]
> SPLAY curl_expire3<<<
> 1147883470[0]
> SPLAY curl_expire3>>>
> 1147883470[0] [+]
> SPLAY curl_expire1<<<
> 1147883470[0] [+]
> SPLAY curl_expire1>>>
> 1147883470[0]
> SPLAY curl_expire1<<<
> 1147883470[0] [+]
> SPLAY curl_expire1>>>
> 1147883470[0]
> SPLAY curl_expire3<<<
> 1147883470[0]
> SPLAY curl_expire3>>>
> 1147883471[0]
> 1147883471[1]
> 1147883471[2]
> 1147883471[3]
> 1147883471[4]

With how many easy handles in use? Is this repeatable with a source code you
can share with us?

It certainly looks wrong that all nodes use the same key (expire time) and
even that they are in a tree when they're identical (the [+] is used for nodes
using the same key (time) as then they are all linked to that single node).

> I don't really know what splay trees are, but in Curl_splayinsert()
> I think the case /* it already exists one of this size */
> will produce the situation if t = Curl_splay(i,t) is the same as area.

Yeah, that would cause problems. But given the explanation above, t and area
should never be the same since 'area' would be a totally new node that is not
already existing.

If it already exists, it indicates a problem in the Curl_splayremovebyaddr()
call done previous to the Curl_splayinsert() function in
multi.c:Curl_expire(). Can you print the splay tree immediately before and
after the remove call too and verify that there actually is a node removed?

-- 
  Commercial curl and libcurl Technical Support: http://haxx.se/curl.html