3d6d93a6be

docs/internals/SPLAY.md+25 -19

@@ -17,7 +17,7 @@ it automatically rebalances itself in each operation.

	## libcurl use

-	libcurl adds fixed timeout expiry timestamps to the splay tree, and is meant
+	libcurl adds fixed timeout expiry `timediff_t` to the splay tree, and is meant
	to scale up to holding a huge amount of pending timeouts with decent
	performance.

@@ -26,19 +26,25 @@ The splay tree is used to:
	1. figure out the next timeout expiry value closest in time
	2. iterate over timeouts that already have expired

-	This splay tree rebalances itself based on the time value.
+	This splay tree rebalances itself based on the timeout value.

-	Each node in the splay tree points to a `struct Curl_easy`. Each `Curl_easy`
-	struct is represented only once in the tree. To still allow each easy handle
-	to have a large number of timeouts per handle, each handle has a sorted linked
-	list of pending timeouts. Only the handle's timeout that is closest to expire
+	Each node in the splay tree carries a `uint32_t id`. This is set to the
+	`mid`, the unique transfer identifier in a multi handle. Each transfer
+	is added only once in the tree. To still allow each transfer
+	to have a large number of timeouts per handle, each handle has a sorted list
+	of pending timeouts. Only the handle's timeout that is closest to expire
	is the timestamp used for the splay tree node.

	When a specific easy handle's timeout expires, the node gets removed from the
-	splay tree and from the handle's linked list of timeouts. The next timeout for
+	splay tree and from the handle's list of timeouts. The next timeout for
	that handle is then first in line and becomes the new timeout value as the
	node is re-added to the splay.

+	To convert the `timediff_t` is the splay to the correct timestamps, the
+	multi handle carries a "base timestamp", set once when created, and the
+	timeout values are calculated relative to that. This works for about
+	500,000 years of continued operation of a multi handle.
+
	## `Curl_splay`

	~~~c
@@ -50,15 +56,16 @@ Rearranges the tree `t` after the provide time `i`.
	## `Curl_splayinsert`

	~~~c
-	struct Curl_tree *Curl_splayinsert(struct curltime key,
+	struct Curl_tree *Curl_splayinsert(timediff_t key,
	struct Curl_tree *t,
-	struct Curl_tree *node);
+	struct Curl_tree *node,
+	uint32_t id);
	~~~

	This function inserts a new `node` in the tree, using the given `key`
-	timestamp. The `node` struct has a field called `->payload` that can be set to
-	point to anything. libcurl sets this to the `struct Curl_easy` handle that is
-	associated with the timeout value set in `key`.
+	timeout. The `node` struct has a field called `->id` which is set to
+	the passed `id`. libcurl sets this to the transfer's `mid`, the unique
+	identifier in a multi handle.

	The splay insert function does not allocate any memory, it assumes the caller
	has that arranged.
@@ -68,12 +75,12 @@ It returns a pointer to the new tree root.
	## `Curl_splaygetbest`

	~~~c
-	struct Curl_tree *Curl_splaygetbest(struct curltime key,
+	struct Curl_tree *Curl_splaygetbest(timediff_t key,
	struct Curl_tree *tree,
	struct Curl_tree **removed);
	~~~

-	If there is a node in the `tree` that has a time value that is less than the
+	If there is a node in the `tree` that has a timeout that is less than the
	provided `key`, this function removes that node from the tree and provides it
	in the `*removed` pointer (or NULL if there was no match).

@@ -95,17 +102,16 @@ Note that a clean tree without any nodes present implies a NULL pointer.
	## `Curl_splayset`

	~~~c
-	void Curl_splayset(struct Curl_tree node, void payload);
+	void Curl_splayset(struct Curl_tree *node, uint32_t id);
	~~~

-	Set a custom pointer to be stored in the splay node. This pointer is not used
+	Sets the `id` in the splay node. This value is not used
	by the splay code itself and can be retrieved again with `Curl_splayget`.

	## `Curl_splayget`

	~~~c
-	void Curl_splayget(struct Curl_tree node);
+	uint32_t Curl_splayget(struct Curl_tree *node);
	~~~

-	Get the custom pointer from the splay node that was previously set with
-	`Curl_splayset`. If no pointer was set before, it returns NULL.
+	Get the `id` from the splay node that was previously set.

lib/cf-ip-happy.c+1 -1

@@ -902,7 +902,7 @@ static CURLcode cf_ip_happy_connect(struct Curl_cfilter *cf,
	}
	#endif
	cf_ip_happy_ctx_clear(ctx, data);
-	Curl_expire_done(data, EXPIRE_HAPPY_EYEBALLS);
+	Curl_expire_clear(data, EXPIRE_HAPPY_EYEBALLS);
	/* whatever errors were reported by ballers, clear our errorbuf */
	Curl_reset_fail(data);
	data->info.numconnects++; /* to track the # of connections made */

lib/connect.c+1 -1

@@ -121,7 +121,7 @@ void Curl_shutdown_start(struct Curl_easy *data, int sockindex,
	data->set.shutdowntimeout : DEFAULT_SHUTDOWN_TIMEOUT_MS);
	/* Set a timer, unless we operate on the admin handle */
	if(data->mid)
-	Curl_expire_ex(data, conn->shutdown.timeout_ms, EXPIRE_SHUTDOWN);
+	Curl_expire(data, conn->shutdown.timeout_ms, EXPIRE_SHUTDOWN);
	CURL_TRC_M(data, "shutdown start on%s connection",
	sockindex ? " secondary" : "");
	}

lib/cshutdn.c+1 -1

@@ -258,7 +258,7 @@ static void cshutdn_perform(struct cshutdn *cshutdn,
	}

	if(next_expire_ms)
-	Curl_expire_ex(admin, next_expire_ms, EXPIRE_SHUTDOWN);
+	Curl_expire(admin, next_expire_ms, EXPIRE_SHUTDOWN);
	}

	static void cshutdn_terminate_all(struct cshutdn *cshutdn,

lib/curl_trc.c+4 -3

@@ -339,14 +339,15 @@ void Curl_trc_timer(struct Curl_easy data, int tid, const char fmt, ...)

	void Curl_trc_easy_timers(struct Curl_easy *data)
	{
-	if(CURL_TRC_TIMER_is_verbose(data)) {
+	if(CURL_TRC_TIMER_is_verbose(data) && data->multi) {
	if(data->state.timeouts.first < EXPIRE_LAST) {
	struct expire_timers *timeouts = &data->state.timeouts;
-	const struct curltime *pnow = Curl_pgrs_now(data);
+	timediff_t base_us =
+	Curl_timeouts_offset_us(&data->multi->timeouts, Curl_pgrs_now(data));
	expire_id eid = data->state.timeouts.first;
	for(; eid < EXPIRE_LAST; eid = timeouts->next[eid]) {
	CURL_TRC_TIMER(data, eid, "expires in %" FMT_TIMEDIFF_T "us",
-	curlx_ptimediff_us(&timeouts->time[eid], pnow));
+	timeouts->offset_us[eid] - base_us);
	}
	}
	}

lib/curlx/timeval.c+5 -0

@@ -216,6 +216,11 @@ timediff_t curlx_timediff_ceil_ms(struct curltime newer,
	return (diff * 1000) + ((newer.tv_usec - older.tv_usec + 999) / 1000);
	}

+	timediff_t curlx_us_to_ceil_ms(timediff_t us)
+	{
+	return (us / 1000) + ((us > 0) && (us % 1000));
+	}
+
	/*
	* Returns: time difference in number of microseconds. For too large diffs it
	* returns max value.

lib/curlx/timeval.h+3 -0

@@ -59,6 +59,9 @@ timediff_t curlx_ptimediff_ms(const struct curltime *newer,
	timediff_t curlx_timediff_ceil_ms(struct curltime newer,
	struct curltime older);

+	/* Returns milliseconds from microseconds, rounded up. */
+	timediff_t curlx_us_to_ceil_ms(timediff_t us);
+
	/*
	* Make sure that the first argument (newer) is the more recent time and older
	* is the older time, as otherwise you get a weird negative time-diff back...

lib/http.c+2 -2

@@ -1486,7 +1486,7 @@ static void http_exp100_continue(struct Curl_easy *data,
	struct cr_exp100_ctx *ctx = reader->ctx;
	if(ctx->state > EXP100_SEND_DATA) {
	ctx->state = EXP100_SEND_DATA;
-	Curl_expire_done(data, EXPIRE_100_TIMEOUT);
+	Curl_expire_clear(data, EXPIRE_100_TIMEOUT);
	}
	}

@@ -1546,7 +1546,7 @@ static void cr_exp100_done(struct Curl_easy *data,
	{
	struct cr_exp100_ctx *ctx = reader->ctx;
	ctx->state = premature ? EXP100_FAILED : EXP100_SEND_DATA;
-	Curl_expire_done(data, EXPIRE_100_TIMEOUT);
+	Curl_expire_clear(data, EXPIRE_100_TIMEOUT);
	}

	static const struct Curl_crtype cr_exp100 = {

lib/multi.c+98 -172

@@ -76,7 +76,7 @@ static CURLMcode add_next_timeout(const struct curltime *pnow,
	struct Curl_multi *multi,
	struct Curl_easy *data);
	static void multi_timeout(struct Curl_multi *multi,
-	struct curltime *expire_time,
+	timediff_t *pexire_offset_us,
	int *timeout_ms);
	static void multi_schedule_pending(struct Curl_multi *multi);
	static void multi_xfer_bufs_free(struct Curl_multi *multi);
@@ -143,7 +143,7 @@ static void mstate_enter_completed(struct Curl_easy *data,
	/* Important: reset the conn pointer so that we do not point to memory
	that could be freed anytime */
	Curl_detach_connection(data);
-	Curl_expire_clear(data); /* stop all timers */
+	Curl_expire_clear_all(data); /* stop all timers */
	}

	/* always use this function to change state, to make debugging easier */
@@ -235,6 +235,8 @@ struct Curl_multi *Curl_multi_handle(uint32_t xfer_table_size,

	multi->magic = CURLMULTI_MAGIC_NUMBER;

+	curlx_pnow(&multi->now);
+	Curl_timeouts_init(&multi->timeouts, &multi->now);
	Curl_dnscache_init(&multi->dnscache, dnssize);
	Curl_mntfy_init(multi);
	Curl_multi_ev_init(multi, ev_hashsize);
@@ -800,7 +802,7 @@ CURLMcode Curl_multi_remove_handle(struct Curl_multi *multi,
	/* The timer must be shut down before data->multi is set to NULL, else
	data's splaynode would remain in the splay tree after curl_easy_cleanup is
	called. Do it after multi_done() in case that sets another time! */
-	Curl_expire_clear(data);
+	Curl_expire_clear_all(data);

	/* If in `msgsent`, it was deducted from `multi->xfers_alive` already. */
	if(!Curl_uint32_bset_contains(&multi->msgsent, data->mid))
@@ -1542,7 +1544,6 @@ static CURLMcode multi_wait(struct Curl_multi *multi,
	bool extrawait) /* when no socket, wait */
	{
	size_t i;
-	struct curltime expire_time;
	int timeout_internal;
	int nevents = 0;
	struct easy_pollset ps;
@@ -1621,7 +1622,7 @@ static CURLMcode multi_wait(struct Curl_multi *multi,
	* Use the shorter one of the internal and the caller requested timeout.
	* If we are called with `!extrawait` and multi_timeout() reports no
	* timeouts exist, do not wait. */
-	multi_timeout(multi, &expire_time, &timeout_internal);
+	multi_timeout(multi, NULL, &timeout_internal);
	if((timeout_internal >= 0) && (timeout_internal < timeout_ms))
	timeout_ms = timeout_internal;

@@ -2929,25 +2930,22 @@ static CURLMcode multi_perform(struct Curl_multi *multi,
	* then and then we risk this loop to remove timers that actually have not
	* been handled!
	*/
-	if(multi->timetree) {
-	struct Curl_tree *t = NULL;
-	do {
-	multi->timetree = Curl_splaygetbest(&start, multi->timetree, &t);
-	if(t) {
-	/* the removed may have another timeout in queue */
-	struct Curl_easy *data = Curl_splayget(t);
-	data->state.timeouts.registered = FALSE;
-	(void)add_next_timeout(&start, multi, data);
-	if(data->mstate == MSTATE_PENDING) {
-	bool stream_unused;
-	CURLcode result_unused;
-	if(multi_handle_timeout(data, &stream_unused, &result_unused)) {
-	infof(data, "PENDING handle timeout");
-	move_pending_to_connect(multi, data);
-	}
-	}
+	while(Curl_timeouts_remove_expired(&multi->timeouts, &start, &mid)) {
+	/* the removed may have another timeout in queue */
+	struct Curl_easy *data = Curl_multi_get_easy(multi, mid);
+	if(!data) {
+	DEBUGASSERT(0);
+	continue;
+	}
+	(void)add_next_timeout(&start, multi, data);
+	if(data->mstate == MSTATE_PENDING) {
+	bool stream_unused;
+	CURLcode result_unused;
+	if(multi_handle_timeout(data, &stream_unused, &result_unused)) {
+	infof(data, "PENDING handle timeout");
+	move_pending_to_connect(multi, data);
	}
-	} while(t);
+	}
	}

	if(running_handles) {
@@ -3130,12 +3128,10 @@ void Curl_multi_will_close(struct Curl_easy *data, curl_socket_t s)
	static void multi_timeouts_init(struct Curl_easy *data)
	{
	data->state.timeouts.first = EXPIRE_LAST;
-	data->state.timeouts.registered = FALSE;
+	data->state.timeouts.splaynode.registered = FALSE;
	}

	/*
-	* add_next_timeout()
-	*
	* Each Curl_easy has a list of timeouts. The add_next_timeout() is called
	* when it has been removed from the splay tree because the timeout has
	* expired. This function is then to advance in the list to pick the next
@@ -3150,11 +3146,10 @@ static CURLMcode add_next_timeout(const struct curltime *pnow,
	struct Curl_easy *data)
	{
	struct expire_timers *timeouts = &data->state.timeouts;
+	timediff_t now_us = Curl_timeouts_offset_us(&multi->timeouts, pnow);

-	DEBUGASSERT(!timeouts->registered);
	while(timeouts->first < EXPIRE_LAST) {
-	timediff_t us = curlx_ptimediff_us(&timeouts->time[timeouts->first], pnow);
-	if(us <= 0) /* remove already expired timer */
+	if(timeouts->offset_us[timeouts->first] <= now_us) /* already expired */
	timeouts->first = timeouts->next[timeouts->first];
	else /* timeouts are sorted, first is first in the future now */
	break;
@@ -3163,10 +3158,8 @@ static CURLMcode add_next_timeout(const struct curltime *pnow,
	if(timeouts->first < EXPIRE_LAST) {
	/* Insert this node again into the splay. Keep the timer in the list in
	case we need to recompute future timers. */
-	Curl_splayset(&timeouts->splaynode, data);
-	multi->timetree = Curl_splayinsert(&timeouts->time[timeouts->first],
-	multi->timetree, &timeouts->splaynode);
-	timeouts->registered = TRUE;
+	Curl_timeouts_add(&multi->timeouts, data,
+	timeouts->offset_us[timeouts->first]);
	}
	return CURLM_OK;
	}
@@ -3175,24 +3168,21 @@ static void multi_mark_expired_as_dirty(struct Curl_multi *multi,
	const struct curltime *ts)
	{
	struct Curl_easy *data = NULL;
-	struct Curl_tree *t = NULL;
+	uint32_t mid;

	/*
	* The loop following here will go on as long as there are expire-times left
	* to process (compared to `ts`) in the splay and 'data' will be
	* re-assigned for every expired handle we deal with.
	*/
-	while(1) {
+	while(Curl_timeouts_remove_expired(&multi->timeouts, ts, &mid)) {
	/* Check if there is one (more) expired timer to deal with! This function
	extracts a matching node if there is one */
-	multi->timetree = Curl_splaygetbest(ts, multi->timetree, &t);
-	if(!t)
-	return;
-
-	data = Curl_splayget(t); /* assign this for next loop */
-	if(!data)
+	data = Curl_multi_get_easy(multi, mid);
+	if(!data) {
+	DEBUGASSERT(0);
	continue;
-	data->state.timeouts.registered = FALSE;
+	}
	#ifdef CURLVERBOSE
	if(CURL_TRC_TIMER_is_verbose(data)) {
	if(data->state.timeouts.first < EXPIRE_LAST) {
@@ -3281,7 +3271,7 @@ static CURLMcode multi_socket(struct Curl_multi *multi,
	if the same timeout is still the one to run after this call. That
	handles the case when the application asks libcurl to run the timeout
	prematurely. */
-	memset(&multi->last_expire_ts, 0, sizeof(multi->last_expire_ts));
+	multi->last_expire_offset_us = 0;

	/* Applications may set `socket_cb` after having added transfers
	* first. Then kick off processing with a
@@ -3513,62 +3503,40 @@ static bool multi_has_dirties(struct Curl_multi *multi)
	}

	static void multi_timeout(struct Curl_multi *multi,
-	struct curltime *expire_time,
+	timediff_t *pexire_offset_us,
	int *timeout_ms)
	{
-	static const struct curltime tv_zero = { 0, 0 };
-	VERBOSE(struct Curl_easy *data = NULL);
-
	if(multi->dead) {
-	*expire_time = tv_zero;
+	if(pexire_offset_us)
+	*pexire_offset_us = 0;
	*timeout_ms = 0;
	return;
	}

	if(multi_has_dirties(multi)) {
-	expire_time = multi_now(multi);
+	if(pexire_offset_us)
+	*pexire_offset_us = Curl_timeouts_offset_us(&multi->timeouts,
+	multi_now(multi));
	*timeout_ms = 0;
	return;
	}
-	else if(multi->timetree) {
-	const struct curltime *pnow = multi_now(multi);
-	/* splay the lowest to the bottom */
-	multi->timetree = Curl_splay(&tv_zero, multi->timetree);
-	/* this will not return NULL from a non-empty tree, but some compilers
-	* are not convinced of that. Analyzers are hard. */
-	*expire_time = multi->timetree ? multi->timetree->key : tv_zero;
-
-	/* 'multi->timetree' will be non-NULL here but the compilers sometimes
-	yell at us if we assume so */
-	if(multi->timetree &&
-	curlx_ptimediff_us(&multi->timetree->key, pnow) > 0) {
-	/* some time left before expiration */
-	timediff_t diff_ms =
-	curlx_timediff_ceil_ms(multi->timetree->key, *pnow);
-	VERBOSE(data = Curl_splayget(multi->timetree));
-	if(diff_ms > INT_MAX)
-	diff_ms = INT_MAX;
-	*timeout_ms = (int)diff_ms;
-	}
-	else {
-	if(multi->timetree)
-	VERBOSE(data = Curl_splayget(multi->timetree));
-	/* 0 means immediately */
-	*timeout_ms = 0;
-	}
-	}
	else {
-	*expire_time = tv_zero;
-	*timeout_ms = -1;
-	}
+	const struct curltime *pnow = multi_now(multi);
+	uint32_t mid;

+	*timeout_ms = Curl_timeouts_next_ms(&multi->timeouts, pnow,
+	pexire_offset_us, &mid);
	#ifdef CURLVERBOSE
-	if(CURL_TRC_TIMER_is_verbose(data) &&
-	(data->state.timeouts.first < EXPIRE_LAST)) {
-	CURL_TRC_TIMER(data, data->state.timeouts.first,
-	"gives multi timeout in %dms", *timeout_ms);
-	}
+	if(mid != UINT32_MAX) {
+	struct Curl_easy *data = Curl_multi_get_easy(multi, mid);
+	if(data && CURL_TRC_TIMER_is_verbose(data) &&
+	(data->state.timeouts.first < EXPIRE_LAST)) {
+	CURL_TRC_TIMER(data, data->state.timeouts.first,
+	"gives multi timeout in %dms", *timeout_ms);
+	}
+	}
	#endif
+	}
	}

	CURLMcode curl_multi_timeout(CURLM *m,
@@ -3578,10 +3546,9 @@ CURLMcode curl_multi_timeout(CURLM *m,
	CURLMcode mresult;

	if(CURL_MAPI_ENTER(&guard, m, multi_timeout, &mresult)) {
-	struct curltime expire_time;
	int itimeout_ms;

-	multi_timeout(m, &expire_time, &itimeout_ms);
+	multi_timeout(m, NULL, &itimeout_ms);
	*timeout_ms = (long)itimeout_ms;
	mresult = CURLM_OK;
	}
@@ -3595,14 +3562,14 @@ CURLMcode curl_multi_timeout(CURLM *m,
	*/
	CURLMcode Curl_update_timer(struct Curl_multi *multi)
	{
-	struct curltime expire_ts = { 0, 0 };
+	timediff_t timeouts_offset_us = 0;
	int timeout_ms;
	int rc;
	bool set_value = FALSE;

	if(!multi->timer_cb \|\| multi->dead)
	return CURLM_OK;
-	multi_timeout(multi, &expire_ts, &timeout_ms);
+	multi_timeout(multi, &timeouts_offset_us, &timeout_ms);

	if(timeout_ms < 0 && multi->last_timeout_ms < 0) {
	/* nothing to do */
@@ -3617,7 +3584,7 @@ CURLMcode Curl_update_timer(struct Curl_multi *multi)
	CURL_TRC_M(multi->admin, "[TIMER] set %dms, none before", timeout_ms);
	set_value = TRUE;
	}
-	else if(curlx_ptimediff_us(&multi->last_expire_ts, &expire_ts)) {
+	else if(multi->last_expire_offset_us != timeouts_offset_us) {
	/* We had a timeout before and have one now, the absolute timestamp
	* differs. The relative timeout_ms may be the same, but the starting
	* point differs. Let the application restart its timer. */
@@ -3634,7 +3601,7 @@ CURLMcode Curl_update_timer(struct Curl_multi *multi)
	if(set_value) {
	struct Curl_mapi_guard guard;

-	multi->last_expire_ts = expire_ts;
+	multi->last_expire_offset_us = timeouts_offset_us;
	multi->last_timeout_ms = timeout_ms;
	CURL_CBAPI_MULTI_START(&guard, multi, multi_timer_cb);
	rc = multi->timer_cb(multi, timeout_ms, multi->timer_userp);
@@ -3663,8 +3630,7 @@ static bool multi_timeouts_check(struct Curl_easy *data)
	return FALSE;
	}
	if((timeouts->next[eid] < EXPIRE_LAST) &&
-	(curlx_ptimediff_ms(&timeouts->time[eid],
-	&timeouts->time[timeouts->next[eid]]) > 0)) {
+	(timeouts->offset_us[eid] > timeouts->offset_us[timeouts->next[eid]])) {
	failf(data, "expire timeouts not sorted: %d happens after %d but "
	"is listed before", (int)eid, (int)timeouts->next[eid]);
	return FALSE;
@@ -3675,11 +3641,9 @@ static bool multi_timeouts_check(struct Curl_easy *data)
	#endif

	/*
-	* multi_deltimeout()
-	*
	* Remove a given timestamp from the list of timeouts.
	*/
-	static void multi_deltimeout(struct Curl_easy *data, expire_id eid)
+	static void multi_clear_timeout(struct Curl_easy *data, expire_id eid)
	{
	struct expire_timers *timeouts = &data->state.timeouts;
	expire_id orig_first = timeouts->first;
@@ -3693,9 +3657,8 @@ static void multi_deltimeout(struct Curl_easy *data, expire_id eid)
	anchor = &timeouts->next[*anchor];
	}
	DEBUGASSERT(multi_timeouts_check(data));
-	if(timeouts->registered) {
+	if(Curl_timeouts_has(data)) {
	struct Curl_multi *multi = data->multi;
-	int rc;

	if(!multi) {
	DEBUGASSERT(0);
@@ -3703,31 +3666,22 @@ static void multi_deltimeout(struct Curl_easy *data, expire_id eid)
	}
	if((timeouts->first >= EXPIRE_LAST) \|\| /* no more timeouts */
	(timeouts->first != orig_first)) { /* active timeout changed */
-	rc = Curl_splayremove(multi->timetree, &timeouts->splaynode,
-	&multi->timetree);
-	if(rc)
-	infof(data, "Internal error removing splay node = %d", rc);
-	timeouts->registered = FALSE;
+	Curl_timeouts_remove(&multi->timeouts, data);
	}
-	if((timeouts->first < EXPIRE_LAST) && !timeouts->registered) {
-	multi->timetree = Curl_splayinsert(&timeouts->time[timeouts->first],
-	multi->timetree,
-	&timeouts->splaynode);
-	timeouts->registered = TRUE;
+	if((timeouts->first < EXPIRE_LAST) && !Curl_timeouts_has(data)) {
+	Curl_timeouts_add(&multi->timeouts, data,
+	timeouts->offset_us[timeouts->first]);
	}
	}
	}

	/*
-	* multi_addtimeout()
-	*
	* Add a timestamp to the list of timeouts. Keep the list sorted so that head
	* of list is always the timeout nearest in time.
-	*
	*/
-	static CURLMcode multi_addtimeout(struct Curl_easy *data,
-	struct curltime *stamp,
-	expire_id eid)
+	static CURLMcode multi_set_timeout(struct Curl_easy *data,
+	const struct curltime *stamp,
+	expire_id eid)
	{
	struct expire_timers *timeouts = &data->state.timeouts;
	expire_id *anchor = &timeouts->first;
@@ -3737,11 +3691,12 @@ static CURLMcode multi_addtimeout(struct Curl_easy *data,
	return CURLM_BAD_FUNCTION_ARGUMENT;
	}
	/* remove from list, store time and re-insert */
-	multi_deltimeout(data, eid);
-	memcpy(&timeouts->time[eid], stamp, sizeof(*stamp));
+	multi_clear_timeout(data, eid);
+	timeouts->offset_us[eid] =
+	Curl_timeouts_offset_us(&data->multi->timeouts, stamp);
+
	while(*anchor < EXPIRE_LAST) {
-	timediff_t ms = curlx_ptimediff_ms(&timeouts->time[*anchor], stamp);
-	if(ms > 0) /* anchor's time is after eid's time /
+	if(timeouts->offset_us[*anchor] > timeouts->offset_us[eid])
	break;
	anchor = &timeouts->next[*anchor];
	}
@@ -3754,8 +3709,17 @@ static CURLMcode multi_addtimeout(struct Curl_easy *data,
	return CURLM_OK;
	}

-	void Curl_expire_ex(struct Curl_easy *data,
-	timediff_t milli, expire_id eid)
+	/*
+	* given a number of milliseconds from now to use to set the 'act before
+	* this'-time for the transfer, to be extracted by curl_multi_timeout()
+	*
+	* The timeout will be added to a queue of timeouts if it defines a moment in
+	* time that is later than the current head of queue.
+	*
+	* Expire replaces a former timeout using the same id if already set.
+	*/
+	void Curl_expire(struct Curl_easy *data,
+	timediff_t milli, expire_id eid)
	{
	struct Curl_multi *multi = data->multi;
	struct expire_timers *timeouts = &data->state.timeouts;
@@ -3775,96 +3739,58 @@ void Curl_expire_ex(struct Curl_easy *data,
	set = *Curl_pgrs_now(data);
	set.tv_sec += (time_t)(milli / 1000); /* may be a 64 to 32-bit conversion */
	set.tv_usec += (int)(milli % 1000) * 1000;
-
	if(set.tv_usec >= 1000000) {
	set.tv_sec++;
	set.tv_usec -= 1000000;
	}

	/* Add the timeout, will replace any previous value for this timer. */
-	multi_addtimeout(data, &set, eid);
+	multi_set_timeout(data, &set, eid);
	DEBUGASSERT(timeouts->first < EXPIRE_LAST);

-	if(timeouts->registered) {
-	int rc;
-	/* timeouts->splaynode is in splay tree already. If the first timer
+	if(Curl_timeouts_has(data)) {
+	/* data has already a timeout registered. If the first timer
	* was NOT the one we just set AND is still the first one,
-	* nothing changed from the splay tree's point of view. The
-	* set timer triggers after the one already in the tree. Leave. */
+	* nothing changed from the timeouts point of view. The
+	* set timer triggers after the one already registered. Leave. */
	if((prev_id != eid) && (prev_id == timeouts->first))
	return;

-	/* Since this is an updated time, we must remove the previous entry from
-	the splay tree first and then re-add the new value */
-	rc = Curl_splayremove(multi->timetree, &timeouts->splaynode,
-	&multi->timetree);
-	if(rc)
-	infof(data, "Internal error removing splay node = %d", rc);
+	/* Since this is an updated time, we must remove data from
+	* timeouts and then add it again. */
+	Curl_timeouts_remove(&multi->timeouts, data);
	}

-	/* Indicate that we are in the splay tree and insert the new timer expiry
-	value since it is our local minimum. */
-	Curl_splayset(&timeouts->splaynode, data);
-	multi->timetree = Curl_splayinsert(&timeouts->time[timeouts->first],
-	multi->timetree, &timeouts->splaynode);
-	timeouts->registered = TRUE;
+	/* Insert the new timer expiry since it is our local minimum. */
+	Curl_timeouts_add(&multi->timeouts, data,
+	timeouts->offset_us[timeouts->first]);
	}

	/*
-	* Curl_expire()
-	*
-	* given a number of milliseconds from now to use to set the 'act before
-	* this'-time for the transfer, to be extracted by curl_multi_timeout()
-	*
-	* The timeout will be added to a queue of timeouts if it defines a moment in
-	* time that is later than the current head of queue.
-	*
-	* Expire replaces a former timeout using the same id if already set.
-	*/
-	void Curl_expire(struct Curl_easy *data, timediff_t milli, expire_id id)
-	{
-	Curl_expire_ex(data, milli, id);
-	}
-
-	/*
-	* Curl_expire_done()
-	*
	* Removes the expire timer. Marks it as done.
-	*
	*/
-	void Curl_expire_done(struct Curl_easy *data, expire_id id)
+	void Curl_expire_clear(struct Curl_easy *data, expire_id id)
	{
	/* remove the timer, if there */
-	multi_deltimeout(data, id);
+	multi_clear_timeout(data, id);
	CURL_TRC_TIMER(data, id, "cleared");
	}

	/*
-	* Curl_expire_clear()
-	*
	* Clear ALL timeout values for this handle.
	*/
-	void Curl_expire_clear(struct Curl_easy *data)
+	void Curl_expire_clear_all(struct Curl_easy *data)
	{
	struct Curl_multi *multi = data->multi;
-	struct expire_timers *timeouts = &data->state.timeouts;

	/* this is only interesting while there is still an associated multi struct
	remaining! */
	if(!multi)
	return;

-	if(timeouts->registered) {
+	if(Curl_timeouts_remove(&multi->timeouts, data)) {
	/* Since this is an cleared time, we must remove the previous entry from
	the splay tree */
-	int rc;
-
-	rc = Curl_splayremove(multi->timetree, &timeouts->splaynode,
-	&multi->timetree);
-	if(rc)
-	infof(data, "Internal error clearing splay node = %d", rc);
-
-	/* clear the timeouts */
	multi_timeouts_init(data);

	if(data->id >= 0)

lib/multihandle.h+4 -4

@@ -32,6 +32,7 @@
	#include "multi_ntfy.h"
	#include "psl.h"
	#include "socketpair.h"
+	#include "splay.h"
	#include "uint-bset.h"
	#include "uint-spbset.h"
	#include "uint-table.h"
@@ -132,9 +133,8 @@ struct Curl_multi {

	/* current time for transfers running in this multi handle */
	struct curltime now;
-	/* timetree points to the splay-tree of time nodes to figure out expire
-	times of all currently set timers */
-	struct Curl_tree *timetree;
+	/* expiration times for all attached easy handles */
+	struct Curl_timeouts timeouts;

	/* buffer used for transfer data, lazy initialized */
	char xfer_buf; / the actual buffer */
@@ -161,7 +161,7 @@ struct Curl_multi {

	struct cshutdn cshutdn; /* connection shutdown handling */
	struct cpool cpool; /* connection pool (bundles) */
-	struct curltime last_expire_ts; /* timestamp of last expiry */
+	timediff_t last_expire_offset_us; /* times offset of last expiry */

	size_t max_host_connections; /* if >0, a fixed limit of the maximum number
	of connections per host */

lib/multiif.h+3 -5

@@ -27,11 +27,9 @@
	* Prototypes for library-wide functions provided by multi.c
	*/

-	void Curl_expire(struct Curl_easy *data, timediff_t milli, expire_id id);
-	void Curl_expire_ex(struct Curl_easy *data,
-	timediff_t milli, expire_id eid);
-	void Curl_expire_clear(struct Curl_easy *data);
-	void Curl_expire_done(struct Curl_easy *data, expire_id id);
+	void Curl_expire(struct Curl_easy *data, timediff_t milli, expire_id eid);
+	void Curl_expire_clear(struct Curl_easy *data, expire_id id);
+	void Curl_expire_clear_all(struct Curl_easy *data);
	CURLMcode Curl_update_timer(struct Curl_multi *multi) WARN_UNUSED_RESULT;
	void Curl_attach_connection(struct Curl_easy *data,
	struct connectdata *conn,

lib/splay.c+236 -150

@@ -23,173 +23,267 @@
	***************************************************************************/
	#include "curl_setup.h"

+	#include "urldata.h"
	#include "splay.h"

-	/*
-	* This macro compares two node keys i and j and returns:
-	*
-	* negative value: when i is smaller than j
-	* zero : when i is equal to j
-	* positive when : when i is larger than j
-	*/
-	#define splay_compare(i, j) curlx_ptimediff_us(i, j)
+
+	void Curl_timeouts_init(struct Curl_timeouts *timeouts,
+	const struct curltime *ptime_base)
+	{
+	timeouts->tree = NULL;
+	timeouts->time_base = ptime_base ? *ptime_base : curlx_now();
+	}
+
+	bool Curl_timeouts_has(struct Curl_easy *data)
+	{
+	struct Curl_tree *node = data ? &data->state.timeouts.splaynode : NULL;
+	return node && node->registered;
+	}
+
+	timediff_t Curl_timeouts_offset_us(struct Curl_timeouts *timeouts,
+	const struct curltime *pts)
+	{
+	return curlx_ptimediff_us(pts, &timeouts->time_base);
+	}
+
+	int Curl_timeouts_next_ms(struct Curl_timeouts *timeouts,
+	const struct curltime *pnow,
+	timediff_t *pexpire_offset_us,
+	uint32_t *pmid)
+	{
+	if(timeouts->tree) { /* splay the lowest key to the root */
+	timeouts->tree = Curl_splay(TIMEDIFF_T_MIN, timeouts->tree);
+	}
+
+	if(timeouts->tree) {
+	timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, pnow);
+	timediff_t delta_us = timeouts->tree->key - elapsed_us;
+	if(pmid)
+	*pmid = timeouts->tree->id;
+	if(pexpire_offset_us)
+	*pexpire_offset_us = timeouts->tree->key;
+	if(delta_us > 0) { /* expires in the future */
+	timediff_t ms = curlx_us_to_ceil_ms(delta_us);
+	return (ms > INT_MAX) ? INT_MAX : (int)ms;
+	}
+	else /* has expired */
+	return 0;
+	}
+	if(pmid)
+	*pmid = UINT32_MAX;
+	if(pexpire_offset_us)
+	*pexpire_offset_us = 0;
+	return -1;
+	}
+
+	bool Curl_timeouts_remove_expired(struct Curl_timeouts *timeouts,
+	const struct curltime *ts,
+	uint32_t *pmid)
+	{
+	if(timeouts->tree) {
+	struct Curl_tree *t = NULL;
+	timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, ts);
+	timeouts->tree = Curl_splaygetbest(elapsed_us, timeouts->tree, &t);
+	if(t) {
+	*pmid = t->id;
+	return TRUE;
+	}
+	}
+	*pmid = UINT32_MAX;
+	return FALSE;
+	}
+
+	void Curl_timeouts_add(struct Curl_timeouts *timeouts,
+	struct Curl_easy *data,
+	timediff_t offset_us)
+	{
+	struct Curl_tree *node = &data->state.timeouts.splaynode;
+	DEBUGASSERT(!node->registered);
+	timeouts->tree = Curl_splayinsert(offset_us, timeouts->tree,
+	node, data->mid);
+	}
+
+	bool Curl_timeouts_remove(struct Curl_timeouts *timeouts,
+	struct Curl_easy *data)
+	{
+	struct Curl_tree *node = &data->state.timeouts.splaynode;
+	if(node->registered) {
+	int rc = Curl_splayremove(timeouts->tree, node, &timeouts->tree);
+	#ifdef DEBUGBUILD
+	if(rc)
+	curl_mfprintf(stderr, "Internal error removing splay node = %d\n", rc);
+	#else
+	(void)rc;
+	#endif
+	return TRUE;
+	}
+	return FALSE;
+	}

	/*
-	* Splay using the key i (which may or may not be in the tree.) The starting
-	* root is t.
+	* Splay using the key i (which may or may not be in the tree).
+	* This rotates the tree, so:
+	* - root->smaller has all nodes smaller than `key`
+	* - root->larger has all nodes larger than `key`
+	* - root->key may equal `key` or not
+	* <https://en.wikipedia.org/wiki/Splay_tree>
	*/
-	struct Curl_tree Curl_splay(const struct curltime pkey,
-	struct Curl_tree *t)
+	struct Curl_tree *Curl_splay(timediff_t key,
+	struct Curl_tree *root)
	{
	struct Curl_tree N, l, r, *y;

-	if(!t)
+	if(!root)
	return NULL;
	N.smaller = N.larger = NULL;
	l = r = &N;

	for(;;) {
-	timediff_t comp = splay_compare(pkey, &t->key);
-	if(comp < 0) {
-	if(!t->smaller)
+	if(key < root->key) {
+	/* key is somewhere in root->smaller branch */
+	if(!root->smaller) /* which is empty, done */
	break;
-	if(splay_compare(pkey, &t->smaller->key) < 0) {
-	y = t->smaller; /* rotate smaller */
-	t->smaller = y->larger;
-	y->larger = t;
-	t = y;
-	if(!t->smaller)
+	if(key < root->smaller->key) {
+	/* key is somewhere in root->smaller->smaller, make a "Zig step" */
+	y = root->smaller;
+	root->smaller = y->larger;
+	y->larger = root;
+	root = y;
+	if(!root->smaller)
	break;
	}
-	r->smaller = t; /* link smaller */
-	r = t;
-	t = t->smaller;
+	/* Making root->smaller the new root, the old root is no longer
+	* referenced. Remember it in the N tree's `r`ight/larger side.
+	* Everything in old root is smaller than what the right side
+	* of N already has, so it gets added to r->smaller. */
+	r->smaller = root;
+	r = root;
+	root = root->smaller;
	}
-	else if(comp > 0) {
-	if(!t->larger)
+	else if(key > root->key) {
+	/* key is somewhere in root->larger branch */
+	if(!root->larger) /* which is empty, done */
	break;
-	if(splay_compare(pkey, &t->larger->key) > 0) {
-	y = t->larger; /* rotate larger */
-	t->larger = y->smaller;
-	y->smaller = t;
-	t = y;
-	if(!t->larger)
+	if(key > root->larger->key) {
+	/* key is somewhere in root->larger->larger, make a "Zig step" */
+	y = root->larger;
+	root->larger = y->smaller;
+	y->smaller = root;
+	root = y;
+	if(!root->larger)
	break;
	}
-	l->larger = t; /* link larger */
-	l = t;
-	t = t->larger;
+	/* Making root->larger the new root, the old root is no longer
+	* referenced. Remember it in the N tree's `l`eft/smaller side.
+	* Everything in old root is larger than what the left side
+	* of N already has, so it gets added to l->larger. */
+	l->larger = root;
+	l = root;
+	root = root->larger;
	}
-	else
+	else /* exact match, root is key, done */
	break;
	}

-	l->larger = t->smaller; /* assemble */
-	r->smaller = t->larger;
-	t->smaller = N.larger;
-	t->larger = N.smaller;
+	/* Put it all together again.
+	* root->smaller has everything larger than current `l`.
+	* root->larger has everything smaller than current `r`. */
+	l->larger = root->smaller;
+	r->smaller = root->larger;
+	root->smaller = N.larger;
+	root->larger = N.smaller;

-	return t;
+	return root;
	}

-	static const struct curltime SPLAY_SUBNODE = {
-	~0, -1
-	};
-
	/* Insert key i into the tree t. Return a pointer to the resulting tree or
	* NULL if something went wrong.
	*
	* @unittest: 1309
	*/
-	struct Curl_tree Curl_splayinsert(const struct curltime pkey,
-	struct Curl_tree *t,
-	struct Curl_tree *node)
+	struct Curl_tree *Curl_splayinsert(timediff_t key,
+	struct Curl_tree *root,
+	struct Curl_tree *node,
+	uint32_t id)
	{
	DEBUGASSERT(node);

-	if(t) {
-	t = Curl_splay(pkey, t);
-	DEBUGASSERT(t);
-	if(splay_compare(pkey, &t->key) == 0) {
-	/* There already exists a node in the tree with the same key. Build a
-	doubly-linked circular list of nodes. We add the new 'node' struct to
-	the end of this list. */
-
-	node->key = SPLAY_SUBNODE; /* identify this node as a subnode */
-	node->samen = t;
-	node->samep = t->samep;
-	t->samep->samen = node;
-	t->samep = node;
-
-	return t; /* the root node always stays the same */
+	node->key = key;
+	node->id = id;
+	node->same = NULL;
+	node->registered = TRUE;
+	if(root) {
+	root = Curl_splay(key, root);
+	DEBUGASSERT(root);
+	if(key == root->key) {
+	/* There already exists a node in the tree with the same key.
+	Append the new node to the `same` list. */
+	struct Curl_tree **panchor = &root->same;
+	while(*panchor)
+	panchor = &(*panchor)->same;
+	*panchor = node;
+	return root; /* the root node always stays the same */
	}
	}

-	if(!t) {
+	/* node becomes the new root. Insert old root as sub-branch. */
+	if(!root) {
	node->smaller = node->larger = NULL;
	}
-	else if(splay_compare(pkey, &t->key) < 0) {
-	node->smaller = t->smaller;
-	node->larger = t;
-	t->smaller = NULL;
+	else if(key < root->key) {
+	node->smaller = root->smaller;
+	node->larger = root;
+	root->smaller = NULL;
	}
	else {
-	node->larger = t->larger;
-	node->smaller = t;
-	t->larger = NULL;
+	node->larger = root->larger;
+	node->smaller = root;
+	root->larger = NULL;
	}
-	node->key = *pkey;

-	/* no identical nodes (yet), we are the only one in the list of nodes */
-	node->samen = node;
-	node->samep = node;
	return node;
	}

	/* Finds and deletes the best-fit node from the tree. Return a pointer to the
	resulting tree. best-fit means the smallest node if it is not larger than
	the key */
-	struct Curl_tree Curl_splaygetbest(const struct curltime pkey,
-	struct Curl_tree *t,
+	struct Curl_tree *Curl_splaygetbest(timediff_t key,
+	struct Curl_tree *root,
	struct Curl_tree **removed)
	{
-	static const struct curltime tv_zero = { 0, 0 };
	struct Curl_tree *x;

-	if(!t) {
+	if(!root) {
	removed = NULL; / none removed since there was no root */
	return NULL;
	}

	/* find smallest */
-	t = Curl_splay(&tv_zero, t);
-	DEBUGASSERT(t);
-	if(splay_compare(pkey, &t->key) < 0) {
+	root = Curl_splay(TIMEDIFF_T_MIN, root);
+	DEBUGASSERT(root);
+	if(key < root->key) {
	/* even the smallest is too big */
	*removed = NULL;
-	return t;
+	return root;
	}

	/* FIRST! Check if there is a list with identical keys */
-	x = t->samen;
-	if(x != t) {
-	/* there is, pick one from the list */
-
-	/* 'x' is the new root node */
-
-	x->key = t->key;
-	x->larger = t->larger;
-	x->smaller = t->smaller;
-	x->samep = t->samep;
-	t->samep->samen = x;
-
-	*removed = t;
+	if(root->same) {
+	x = root->same;
+	DEBUGASSERT(x->key == root->key);
+	/* 'x' becomes the new root node */
+	x->larger = root->larger;
+	x->smaller = root->smaller;
+	root->same = NULL;
+	root->registered = FALSE;
+	*removed = root;
	return x; /* new root */
	}

	/* we splayed the tree to the smallest element, there is no smaller */
-	x = t->larger;
-	*removed = t;
+	x = root->larger;
+	root->registered = FALSE;
+	*removed = root;

	return x;
	}
@@ -205,87 +299,79 @@ struct Curl_tree Curl_splaygetbest(const struct curltime pkey,
	*
	* @unittest: 1309
	*/
-	int Curl_splayremove(struct Curl_tree *t,
+	int Curl_splayremove(struct Curl_tree *root,
	struct Curl_tree *removenode,
	struct Curl_tree **newroot)
	{
	struct Curl_tree *x;

-	if(!t)
+	if(!root)
	return 1;

	DEBUGASSERT(removenode);
+	if(!removenode->registered)
+	return 2;

-	if(splay_compare(&SPLAY_SUBNODE, &removenode->key) == 0) {
-	/* It is a subnode within a 'same' linked list and thus we can unlink it
-	easily. */
-	DEBUGASSERT(removenode->samen != removenode);
-	if(removenode->samen == removenode)
-	/* A non-subnode should never be set to SPLAY_SUBNODE */
-	return 3;
-
-	removenode->samep->samen = removenode->samen;
-	removenode->samen->samep = removenode->samep;
-
-	/* Ensures that double-remove gets caught. */
-	removenode->samen = removenode;
-
-	newroot = t; / return the same root */
-	return 0;
-	}
-
-	t = Curl_splay(&removenode->key, t);
-	DEBUGASSERT(t);
+	root = Curl_splay(removenode->key, root);
+	DEBUGASSERT(root);

-	/* First make sure that we got the same root node as the one we want
+	/* First make sure that we got the same root key as the one we want
	to remove, as otherwise we might be trying to remove a node that
-	is not actually in the tree.
-
-	We cannot compare the keys here as a double remove in quick
-	succession of a node with key != SPLAY_SUBNODE && same != NULL
-	could return the same key but a different node. */
-	DEBUGASSERT(t == removenode);
-	if(t != removenode)
+	is not actually in the tree. */
+	if(root->key != removenode->key) {
+	DEBUGASSERT(0);
	return 2;
+	}

-	/* Check if there is a list with identical sizes, as then we are trying to
-	remove the root node of a list of nodes with identical keys. */
-	x = t->samen;
-	if(x != t) {
+	if(root != removenode) {
+	/* Should be in the root->same list then */
+	struct Curl_tree **panchor;
+	for(panchor = &root->same; panchor; panchor = &(panchor)->same) {
+	if(*panchor == removenode) {
+	*panchor = removenode->same;
+	removenode->same = NULL;
+	removenode->registered = FALSE;
+	*newroot = root;
+	return 0;
+	}
+	}
+	/* not found in same list, error */
+	DEBUGASSERT(0);
+	return 2;
+	}
+	/* removing the root node */
+	if(root->same) {
	/* 'x' is the new root node, we make it use the root node's
	smaller/larger links */
-
-	x->key = t->key;
-	x->larger = t->larger;
-	x->smaller = t->smaller;
-	x->samep = t->samep;
-	t->samep->samen = x;
+	x = root->same;
+	x->larger = root->larger;
+	x->smaller = root->smaller;
+	root->same = NULL;
	}
	else {
	/* Remove the root node */
-	if(!t->smaller)
-	x = t->larger;
+	if(!root->smaller)
+	x = root->larger;
	else {
-	x = Curl_splay(&removenode->key, t->smaller);
+	x = Curl_splay(removenode->key, root->smaller);
	DEBUGASSERT(x);
-	x->larger = t->larger;
+	x->larger = root->larger;
	}
	}
-
-	newroot = x; / store new root pointer */
-
+	removenode->registered = FALSE;
+	newroot = x; / return new root */
	return 0;
	}

	/* set and get the custom payload for this tree node */
-	void Curl_splayset(struct Curl_tree node, void payload)
+	void Curl_splayset(struct Curl_tree *node, uint32_t id)
	{
	DEBUGASSERT(node);
-	node->ptr = payload;
+	node->id = id;
	}

-	void Curl_splayget(struct Curl_tree node)
+	uint32_t Curl_splayget(struct Curl_tree *node)
	{
	DEBUGASSERT(node);
-	return node->ptr;
+	return node->id;
	}

lib/splay.h+47 -14

@@ -27,33 +27,66 @@

	#include "curlx/timeval.h"

+	struct Curl_easy;
+
	/* only use function calls to access this struct */
	struct Curl_tree {
	struct Curl_tree smaller; / smaller node */
	struct Curl_tree larger; / larger node */
-	struct Curl_tree samen; / points to the next node with identical key */
-	struct Curl_tree samep; / points to the prev node with identical key */
-	struct curltime key; /* this node's "sort" key */
-	void ptr; / data the splay code does not care about */
+	struct Curl_tree same; / points to the next node with identical key */
+	timediff_t key; /* this node's "sort" key */
+	uint32_t id; /* provided id for this node */
+	BIT(registered); /* node is registered in splay tree */
+	};
+
+	struct Curl_timeouts {
+	struct Curl_tree *tree;
+	struct curltime time_base;
	};

-	struct Curl_tree Curl_splay(const struct curltime pkey,
-	struct Curl_tree *t);
+	void Curl_timeouts_init(struct Curl_timeouts *timeouts,
+	const struct curltime *ptime_base);
+
+	bool Curl_timeouts_has(struct Curl_easy *data);
+
+	timediff_t Curl_timeouts_offset_us(struct Curl_timeouts *timeouts,
+	const struct curltime *pts);
+
+	int Curl_timeouts_next_ms(struct Curl_timeouts *timeouts,
+	const struct curltime *pnow,
+	timediff_t *pexpire_offset_us,
+	uint32_t *pmid);
+
+	bool Curl_timeouts_remove_expired(struct Curl_timeouts *timeouts,
+	const struct curltime *ts,
+	uint32_t *pmid);
+
+	void Curl_timeouts_add(struct Curl_timeouts *timeouts,
+	struct Curl_easy *data,
+	timediff_t offset_us);
+
+	/* Returns TRUE if data was registered in timeouts before */
+	bool Curl_timeouts_remove(struct Curl_timeouts *timeouts,
+	struct Curl_easy *data);
+
+	struct Curl_tree *Curl_splay(timediff_t key,
+	struct Curl_tree *root);

-	struct Curl_tree Curl_splayinsert(const struct curltime pkey,
-	struct Curl_tree *t,
-	struct Curl_tree *node);
+	struct Curl_tree *Curl_splayinsert(timediff_t key,
+	struct Curl_tree *root,
+	struct Curl_tree *node,
+	uint32_t id);

-	struct Curl_tree Curl_splaygetbest(const struct curltime pkey,
-	struct Curl_tree *t,
+	struct Curl_tree *Curl_splaygetbest(timediff_t key,
+	struct Curl_tree *root,
	struct Curl_tree **removed);

-	int Curl_splayremove(struct Curl_tree *t,
+	int Curl_splayremove(struct Curl_tree *root,
	struct Curl_tree *removenode,
	struct Curl_tree **newroot);

	/* set and get the custom payload for this tree node */
-	void Curl_splayset(struct Curl_tree node, void payload);
-	void Curl_splayget(struct Curl_tree node);
+	void Curl_splayset(struct Curl_tree *node, uint32_t id);
+	uint32_t Curl_splayget(struct Curl_tree *node);

	#endif /* HEADER_CURL_SPLAY_H */

lib/url.c+1 -1

@@ -228,7 +228,7 @@ CURLcode Curl_close(struct Curl_easy **datap)
	}
	DEBUGASSERT(!data->conn \|\| data->state.internal);

-	Curl_expire_clear(data); /* shut off any timers left */
+	Curl_expire_clear_all(data); /* shut off any timers left */

	if(data->state.rangestringalloc)
	curlx_free(data->state.range);

lib/urldata.h+2 -2

@@ -514,10 +514,10 @@ typedef enum {

	struct expire_timers {
	struct Curl_tree splaynode; /* for the splay stuff */
-	struct curltime time[EXPIRE_LAST];
+	/* microsecond offset from Curl_timeouts base timestamp */
+	timediff_t offset_us[EXPIRE_LAST];
	expire_id next[EXPIRE_LAST];
	expire_id first;
-	BIT(registered); /* timeout node is registered in splay tree */
	};

	/* individual pieces of the URL */

lib/vdns/asyn-thrdd.c+1 -1

@@ -862,7 +862,7 @@ CURLcode Curl_async_take_result(struct Curl_easy *data,
	if(result)
	return result;

-	Curl_expire_done(data, EXPIRE_ASYNC_NAME);
+	Curl_expire_clear(data, EXPIRE_ASYNC_NAME);

	/* A failure is an authoritative negative answer, eligible for
	negative caching, only when every A/AAAA query performed came

tests/data/test1309+105 -50

@@ -121,7 +121,7 @@ Tree look:
	0.49[15]
	0.39[14]
	0.0[15]
-	remove pointer 7, payload 718
+	remove node 7, payload 718
	Tree look:
	0.1013[5]
	0.1003[4]
@@ -172,7 +172,7 @@ Tree look:
	0.49[15]
	0.39[14]
	0.0[15]
-	remove pointer 8, payload 236
+	remove node 8, payload 236
	Tree look:
	0.1013[7]
	0.1003[6]
@@ -222,7 +222,7 @@ Tree look:
	0.49[7]
	0.39[6]
	0.0[7]
-	remove pointer 9, payload 777
+	remove node 9, payload 777
	Tree look:
	0.1013[6]
	0.1003[5]
@@ -271,7 +271,7 @@ Tree look:
	0.49[10]
	0.39[9]
	0.0[10]
-	remove pointer 10, payload 295
+	remove node 10, payload 295
	Tree look:
	0.1013[8]
	0.1003[7]
@@ -319,7 +319,7 @@ Tree look:
	0.49[8]
	0.39[7]
	0.0[8]
-	remove pointer 11, payload 836
+	remove node 11, payload 836
	Tree look:
	0.1013[5]
	0.1003[4]
@@ -366,7 +366,7 @@ Tree look:
	0.49[11]
	0.39[10]
	0.0[11]
-	remove pointer 12, payload 354
+	remove node 12, payload 354
	Tree look:
	0.1013[7]
	0.1003[6]
@@ -412,7 +412,7 @@ Tree look:
	0.49[10]
	0.39[9]
	0.0[10]
-	remove pointer 13, payload 895
+	remove node 13, payload 895
	Tree look:
	0.1013[4]
	0.1003[3]
@@ -457,7 +457,7 @@ Tree look:
	0.49[13]
	0.39[12]
	0.0[13]
-	remove pointer 14, payload 413
+	remove node 14, payload 413
	Tree look:
	0.1013[6]
	0.1003[5]
@@ -501,7 +501,7 @@ Tree look:
	0.49[11]
	0.39[10]
	0.0[11]
-	remove pointer 15, payload 954
+	remove node 15, payload 954
	Tree look:
	0.1013[2]
	0.1003[1]
@@ -544,7 +544,7 @@ Tree look:
	0.49[14]
	0.39[13]
	0.0[14]
-	remove pointer 16, payload 472
+	remove node 16, payload 472
	Tree look:
	0.1013[4]
	0.1003[3]
@@ -586,7 +586,7 @@ Tree look:
	0.49[12]
	0.39[11]
	0.0[12]
-	remove pointer 17, payload 1013
+	remove node 17, payload 1013
	Tree look:
	0.1003[0]
	0.944[2]
@@ -627,7 +627,7 @@ Tree look:
	0.49[14]
	0.39[13]
	0.0[14]
-	remove pointer 18, payload 531
+	remove node 18, payload 531
	Tree look:
	0.1003[2]
	0.944[3]
@@ -667,7 +667,7 @@ Tree look:
	0.49[13]
	0.39[12]
	0.0[13]
-	remove pointer 19, payload 49
+	remove node 19, payload 49
	Tree look:
	0.1003[4]
	0.944[5]
@@ -706,7 +706,7 @@ Tree look:
	0.59[6]
	0.39[0]
	0.0[1]
-	remove pointer 20, payload 590
+	remove node 20, payload 590
	Tree look:
	0.1003[2]
	0.944[3]
@@ -744,7 +744,7 @@ Tree look:
	0.59[8]
	0.39[3]
	0.0[4]
-	remove pointer 21, payload 108
+	remove node 21, payload 108
	Tree look:
	0.1003[4]
	0.944[5]
@@ -781,7 +781,7 @@ Tree look:
	0.59[2]
	0.39[1]
	0.0[2]
-	remove pointer 22, payload 649
+	remove node 22, payload 649
	Tree look:
	0.1003[3]
	0.944[4]
@@ -817,7 +817,7 @@ Tree look:
	0.59[5]
	0.39[4]
	0.0[5]
-	remove pointer 23, payload 167
+	remove node 23, payload 167
	Tree look:
	0.1003[5]
	0.944[6]
@@ -852,7 +852,7 @@ Tree look:
	0.59[4]
	0.39[3]
	0.0[4]
-	remove pointer 24, payload 708
+	remove node 24, payload 708
	Tree look:
	0.1003[3]
	0.944[4]
@@ -886,7 +886,7 @@ Tree look:
	0.59[7]
	0.39[6]
	0.0[7]
-	remove pointer 25, payload 226
+	remove node 25, payload 226
	Tree look:
	0.1003[5]
	0.944[6]
@@ -919,7 +919,7 @@ Tree look:
	0.59[5]
	0.39[4]
	0.0[5]
-	remove pointer 26, payload 767
+	remove node 26, payload 767
	Tree look:
	0.1003[2]
	0.944[3]
@@ -951,7 +951,7 @@ Tree look:
	0.59[8]
	0.39[7]
	0.0[8]
-	remove pointer 27, payload 285
+	remove node 27, payload 285
	Tree look:
	0.1003[4]
	0.944[5]
@@ -982,7 +982,7 @@ Tree look:
	0.59[6]
	0.39[5]
	0.0[6]
-	remove pointer 28, payload 826
+	remove node 28, payload 826
	Tree look:
	0.1003[2]
	0.944[3]
@@ -1012,7 +1012,7 @@ Tree look:
	0.59[9]
	0.39[8]
	0.0[9]
-	remove pointer 29, payload 344
+	remove node 29, payload 344
	Tree look:
	0.1003[4]
	0.944[5]
@@ -1041,7 +1041,7 @@ Tree look:
	0.59[7]
	0.39[6]
	0.0[7]
-	remove pointer 30, payload 885
+	remove node 30, payload 885
	Tree look:
	0.1003[2]
	0.944[3]
@@ -1069,7 +1069,7 @@ Tree look:
	0.59[10]
	0.39[9]
	0.0[10]
-	remove pointer 31, payload 403
+	remove node 31, payload 403
	Tree look:
	0.1003[4]
	0.944[5]
@@ -1096,7 +1096,7 @@ Tree look:
	0.59[8]
	0.39[7]
	0.0[8]
-	remove pointer 32, payload 944
+	remove node 32, payload 944
	Tree look:
	0.1003[1]
	0.934[0]
@@ -1122,7 +1122,7 @@ Tree look:
	0.59[10]
	0.39[9]
	0.0[10]
-	remove pointer 33, payload 462
+	remove node 33, payload 462
	Tree look:
	0.1003[3]
	0.934[2]
@@ -1147,7 +1147,7 @@ Tree look:
	0.59[8]
	0.39[7]
	0.0[8]
-	remove pointer 34, payload 1003
+	remove node 34, payload 1003
	Tree look:
	0.934[0]
	0.875[2]
@@ -1171,7 +1171,7 @@ Tree look:
	0.59[10]
	0.39[9]
	0.0[10]
-	remove pointer 35, payload 521
+	remove node 35, payload 521
	Tree look:
	0.934[2]
	0.875[3]
@@ -1194,7 +1194,7 @@ Tree look:
	0.59[8]
	0.39[7]
	0.0[8]
-	remove pointer 36, payload 39
+	remove node 36, payload 39
	Tree look:
	0.934[4]
	0.875[5]
@@ -1216,7 +1216,7 @@ Tree look:
	0.98[4]
	0.59[5]
	0.0[0]
-	remove pointer 37, payload 580
+	remove node 37, payload 580
	Tree look:
	0.934[2]
	0.875[3]
@@ -1237,7 +1237,7 @@ Tree look:
	0.98[6]
	0.59[7]
	0.0[3]
-	remove pointer 38, payload 98
+	remove node 38, payload 98
	Tree look:
	0.934[4]
	0.875[5]
@@ -1257,7 +1257,7 @@ Tree look:
	0.118[3]
	0.59[0]
	0.0[1]
-	remove pointer 39, payload 639
+	remove node 39, payload 639
	Tree look:
	0.934[3]
	0.875[4]
@@ -1276,7 +1276,7 @@ Tree look:
	0.118[5]
	0.59[3]
	0.0[4]
-	remove pointer 40, payload 157
+	remove node 40, payload 157
	Tree look:
	0.934[5]
	0.875[6]
@@ -1294,7 +1294,7 @@ Tree look:
	0.118[0]
	0.59[1]
	0.0[2]
-	remove pointer 41, payload 698
+	remove node 41, payload 698
	Tree look:
	0.934[3]
	0.875[4]
@@ -1311,7 +1311,7 @@ Tree look:
	0.118[3]
	0.59[4]
	0.0[5]
-	remove pointer 42, payload 216
+	remove node 42, payload 216
	Tree look:
	0.934[5]
	0.875[6]
@@ -1327,7 +1327,7 @@ Tree look:
	0.118[1]
	0.59[2]
	0.0[3]
-	remove pointer 43, payload 757
+	remove node 43, payload 757
	Tree look:
	0.934[2]
	0.875[3]
@@ -1342,7 +1342,7 @@ Tree look:
	0.118[3]
	0.59[4]
	0.0[5]
-	remove pointer 44, payload 275
+	remove node 44, payload 275
	Tree look:
	0.934[4]
	0.875[5]
@@ -1356,7 +1356,7 @@ Tree look:
	0.118[1]
	0.59[2]
	0.0[3]
-	remove pointer 45, payload 816
+	remove node 45, payload 816
	Tree look:
	0.934[1]
	0.875[2]
@@ -1369,7 +1369,7 @@ Tree look:
	0.118[3]
	0.59[4]
	0.0[5]
-	remove pointer 46, payload 334
+	remove node 46, payload 334
	Tree look:
	0.934[3]
	0.875[4]
@@ -1381,7 +1381,7 @@ Tree look:
	0.118[1]
	0.59[2]
	0.0[3]
-	remove pointer 47, payload 875
+	remove node 47, payload 875
	Tree look:
	0.934[1]
	0.659[0]
@@ -1392,7 +1392,7 @@ Tree look:
	0.118[3]
	0.59[4]
	0.0[5]
-	remove pointer 48, payload 393
+	remove node 48, payload 393
	Tree look:
	0.934[3]
	0.659[2]
@@ -1402,7 +1402,7 @@ Tree look:
	0.118[1]
	0.59[2]
	0.0[3]
-	remove pointer 49, payload 934
+	remove node 49, payload 934
	Tree look:
	0.659[0]
	0.600[1]
@@ -1411,7 +1411,7 @@ Tree look:
	0.118[3]
	0.59[4]
	0.0[5]
-	remove pointer 0, payload 0
+	remove node 0, payload 0
	Tree look:
	0.659[1]
	0.600[0]
@@ -1419,32 +1419,32 @@ Tree look:
	0.177[2]
	0.118[1]
	0.59[2]
-	remove pointer 1, payload 541
+	remove node 1, payload 541
	Tree look:
	0.659[2]
	0.600[1]
	0.177[0]
	0.118[1]
	0.59[2]
-	remove pointer 2, payload 59
+	remove node 2, payload 59
	Tree look:
	0.659[3]
	0.600[2]
	0.177[1]
	0.118[0]
-	remove pointer 3, payload 600
+	remove node 3, payload 600
	Tree look:
	0.659[1]
	0.177[0]
	0.118[1]
-	remove pointer 4, payload 118
+	remove node 4, payload 118
	Tree look:
	0.659[1]
	0.177[0]
-	remove pointer 5, payload 659
+	remove node 5, payload 659
	Tree look:
	0.177[0]
-	remove pointer 6, payload 177
+	remove node 6, payload 177
	Removing nodes not larger than 0
	removed payload 0[0]
	Removing nodes not larger than 100
@@ -1556,6 +1556,61 @@ removed payload 1003[1]
	removed payload 1013[0]
	removed payload 1013[1]
	removed payload 1013[2]
+	Removing nodes not larger than 0
+	removed payload 0[timeout=0]
+	Removing nodes not larger than 32
+	removed payload 31[timeout=3]
+	removed payload 9[timeout=5]
+	removed payload 40[timeout=8]
+	removed payload 18[timeout=10]
+	removed payload 49[timeout=13]
+	removed payload 27[timeout=15]
+	removed payload 5[timeout=17]
+	removed payload 36[timeout=20]
+	removed payload 14[timeout=22]
+	removed payload 45[timeout=25]
+	removed payload 23[timeout=27]
+	removed payload 1[timeout=29]
+	removed payload 32[timeout=32]
+	Removing nodes not larger than 64
+	removed payload 10[timeout=34]
+	removed payload 41[timeout=37]
+	removed payload 19[timeout=39]
+	removed payload 28[timeout=44]
+	removed payload 6[timeout=46]
+	removed payload 37[timeout=49]
+	removed payload 15[timeout=51]
+	removed payload 46[timeout=54]
+	removed payload 24[timeout=56]
+	removed payload 2[timeout=58]
+	removed payload 33[timeout=61]
+	removed payload 11[timeout=63]
+	Removing nodes not larger than 96
+	removed payload 42[timeout=66]
+	removed payload 20[timeout=68]
+	removed payload 29[timeout=73]
+	removed payload 7[timeout=75]
+	removed payload 38[timeout=78]
+	removed payload 16[timeout=80]
+	removed payload 47[timeout=83]
+	removed payload 25[timeout=85]
+	removed payload 3[timeout=87]
+	removed payload 34[timeout=90]
+	removed payload 12[timeout=92]
+	removed payload 43[timeout=95]
+	Removing nodes not larger than 128
+	removed payload 21[timeout=97]
+	removed payload 30[timeout=102]
+	removed payload 8[timeout=104]
+	removed payload 39[timeout=107]
+	removed payload 17[timeout=109]
+	removed payload 48[timeout=112]
+	removed payload 26[timeout=114]
+	removed payload 4[timeout=116]
+	removed payload 35[timeout=119]
+	removed payload 13[timeout=121]
+	removed payload 44[timeout=124]
+	removed payload 22[timeout=126]
	</stdout>
	</verify>
	</testcase>

tests/unit/unit1309.c+57 -28

@@ -38,10 +38,10 @@ static void splayprint(struct Curl_tree *t, int d, char output)
	curl_mprintf(" ");

	if(output) {
-	curl_mprintf("%ld.%ld[%d]", (long)t->key.tv_sec, (long)t->key.tv_usec, i);
+	curl_mprintf("0.%ld[%d]", (long)t->key, i);
	}

-	for(count = 0, node = t->samen; node != t; node = node->samen, count++)
+	for(count = 0, node = t->same; node; node = node->same, count++)
	;

	if(output) {
@@ -63,67 +63,96 @@ static CURLcode test_unit1309(const char *arg)

	struct Curl_tree root, removed;
	struct Curl_tree nodes[NUM_NODES * 3];
-	size_t storage[NUM_NODES * 3];
	int rc;
-	int i, j;
-	struct curltime tv_now = { 0, 0 };
+	size_t i, j;
+	timediff_t tv_now = 0, timeout_last;
	root = NULL; /* the empty tree */

	/* add nodes */
	for(i = 0; i < NUM_NODES; i++) {
-	struct curltime key;
+	timediff_t key;

-	key.tv_sec = 0;
-	key.tv_usec = (541 * i) % 1023;
-	storage[i] = key.tv_usec;
-	Curl_splayset(&nodes[i], &storage[i]);
-	root = Curl_splayinsert(&key, root, &nodes[i]);
+	key = (541 * i) % 1023;
+	root = Curl_splayinsert(key, root, &nodes[i], (uint32_t)key);
+	fail_unless(nodes[i].registered, "node should have been registered");
	}

	puts("Result:");
	splayprint(root, 0, 1);

	for(i = 0; i < NUM_NODES; i++) {
-	int rem = (i + 7) % NUM_NODES;
+	size_t rem = (i + 7) % NUM_NODES;
	curl_mprintf("Tree look:\n");
	splayprint(root, 0, 1);
-	curl_mprintf("remove pointer %d, payload %zu\n", rem,
-	(size_t )Curl_splayget(&nodes[rem]));
+	curl_mprintf("remove node %d, payload %u\n", (int)rem,
+	Curl_splayget(&nodes[rem]));
	rc = Curl_splayremove(root, &nodes[rem], &root);
	if(rc) {
	/* failed! */
-	curl_mprintf("remove %d failed!\n", rem);
+	curl_mprintf("remove %d failed!\n", (int)rem);
	fail("remove");
	}
+	fail_unless(!nodes[rem].registered, "node should not be registered");
+	rc = Curl_splayremove(root, &nodes[rem], &root);
+	if(!rc) {
+	/* failed! */
+	curl_mprintf("double remove %d did not fail!\n", (int)rem);
+	fail("double remove");
+	}
	}

	fail_unless(!root, "tree not empty after removing all nodes");

	/* rebuild tree */
	for(i = 0; i < NUM_NODES; i++) {
-	struct curltime key;
+	timediff_t key;

-	key.tv_sec = 0;
-	key.tv_usec = (541 * i) % 1023;
+	key = (541 * i) % 1023;

	/* add some nodes with the same key */
	for(j = 0; j <= i % 3; j++) {
-	storage[(i * 3) + j] = (key.tv_usec * 10) + j;
-	Curl_splayset(&nodes[(i * 3) + j], &storage[(i * 3) + j]);
-	root = Curl_splayinsert(&key, root, &nodes[(i * 3) + j]);
+	root = Curl_splayinsert(key, root, &nodes[(i * 3) + j],
+	(uint32_t)(key * 10 + j));
	}
	}

	removed = NULL;
	for(i = 0; i <= 1100; i += 100) {
-	curl_mprintf("Removing nodes not larger than %d\n", i);
-	tv_now.tv_usec = i;
-	root = Curl_splaygetbest(&tv_now, root, &removed);
+	curl_mprintf("Removing nodes not larger than %d\n", (int)i);
+	tv_now = i;
+	root = Curl_splaygetbest(tv_now, root, &removed);
+	while(removed) {
+	curl_mprintf("removed payload %u[%u]\n",
+	Curl_splayget(removed) / 10,
+	Curl_splayget(removed) % 10);
+	root = Curl_splaygetbest(tv_now, root, &removed);
+	}
+	}
+
+	fail_unless(!root, "tree not empty when it should be");
+
+	/* rebuild tree with duplicate values */
+	for(i = 0; i < NUM_NODES; i++) {
+	timediff_t key = (541 * i) % 128;
+	root = Curl_splayinsert(key, root, &nodes[i], (uint32_t)i);
+	}
+
+	removed = NULL;
+	timeout_last = -1;
+	for(i = 0; i <= 128; i += 32) {
+	curl_mprintf("Removing nodes not larger than %d\n", (int)i);
+	root = Curl_splaygetbest(i, root, &removed);
	while(removed) {
-	curl_mprintf("removed payload %zu[%zu]\n",
-	(size_t )Curl_splayget(removed) / 10,
-	(size_t )Curl_splayget(removed) % 10);
-	root = Curl_splaygetbest(&tv_now, root, &removed);
+	curl_mprintf("removed payload %u[timeout=%d]\n",
+	Curl_splayget(removed), (int)removed->key);
+	if(removed->key < timeout_last) {
+	/* failed! */
+	curl_mprintf("remove timeout %d is smaller than last %d!\n",
+	(int)removed->key, (int)timeout_last);
+	fail("wrong timeout order");
+	}
+	timeout_last = removed->key;
+	root = Curl_splaygetbest(i, root, &removed);
	}
	}

tests/unit/unit3214.c+1 -1

@@ -48,7 +48,7 @@ static void checksize(const char *name, size_t size, size_t allowed)
	These sizes were chosen with platforms with 64-bit pointers in mind. */
	#define MAX_CURL_EASY 5370
	#define MAX_CONNECTDATA 1300
-	#define MAX_CURL_MULTI 920
+	#define MAX_CURL_MULTI 928
	#define MAX_CURL_HTTPPOST 112
	#define MAX_CURL_SLIST 16
	#define MAX_CURL_KHKEY 24

Subject

Binary

Architecture & Compiler Flags

Build Log

Commit Diff GitHub →