tevent: optimize adding new zero timer events

Such events were used before we had immediate events.
It's likely that there're a lot of this events
and we need to add new ones in fifo order.

The tricky part is that tevent_common_add_timer()
should not use the optimization as it's used
by broken Samba versions, which don't use
tevent_common_loop_timer_delay() in source3/lib/events.c.

Signed-off-by: Stefan Metzmacher <metze@samba.org>
Reviewed-by: Jeremy Allison <jra@samba.org>

6 files changed, 113 insertions, 31 deletions

diff --git a/lib/tevent/tevent.c b/lib/tevent/tevent.c
index 63d5f1536c..be0afd453b 100644
--- a/lib/tevent/tevent.c
+++ b/lib/tevent/tevent.c
@@ -190,6 +190,7 @@ int tevent_common_context_destructor(struct tevent_context *ev)
 		DLIST_REMOVE(ev->fd_events, fd);
 	}
 
+	ev->last_zero_timer = NULL;
 	for (te = ev->timer_events; te; te = tn) {
 		tn = te->next;
 		te->event_ctx = NULL;
diff --git a/lib/tevent/tevent_epoll.c b/lib/tevent/tevent_epoll.c
index 1ec97c5f71..599c190658 100644
--- a/lib/tevent/tevent_epoll.c
+++ b/lib/tevent/tevent_epoll.c
@@ -937,7 +937,7 @@ static const struct tevent_ops epoll_event_ops = {
 	.set_fd_close_fn	= tevent_common_fd_set_close_fn,
 	.get_fd_flags		= tevent_common_fd_get_flags,
 	.set_fd_flags		= epoll_event_set_fd_flags,
-	.add_timer		= tevent_common_add_timer,
+	.add_timer		= tevent_common_add_timer_v2,
 	.schedule_immediate	= tevent_common_schedule_immediate,
 	.add_signal		= tevent_common_add_signal,
 	.loop_once		= epoll_event_loop_once,
diff --git a/lib/tevent/tevent_internal.h b/lib/tevent/tevent_internal.h
index 8433333558..b239e7403a 100644
--- a/lib/tevent/tevent_internal.h
+++ b/lib/tevent/tevent_internal.h
@@ -263,6 +263,13 @@ struct tevent_context {
 		tevent_trace_callback_t callback;
 		void *private_data;
 	} tracing;
+
+	/*
+	 * an optimization pointer into timer_events
+	 * used by used by common code via
+	 * tevent_common_add_timer_v2()
+	 */
+	struct tevent_timer *last_zero_timer;
 };
 
 const struct tevent_ops *tevent_find_ops_byname(const char *name);
@@ -292,6 +299,13 @@ struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev,
 					     void *private_data,
 					     const char *handler_name,
 					     const char *location);
+struct tevent_timer *tevent_common_add_timer_v2(struct tevent_context *ev,
+						TALLOC_CTX *mem_ctx,
+					        struct timeval next_event,
+					        tevent_timer_handler_t handler,
+					        void *private_data,
+					        const char *handler_name,
+					        const char *location);
 struct timeval tevent_common_loop_timer_delay(struct tevent_context *);
 
 void tevent_common_schedule_immediate(struct tevent_immediate *im,
diff --git a/lib/tevent/tevent_poll.c b/lib/tevent/tevent_poll.c
index 0175cae531..92fcc441ac 100644
--- a/lib/tevent/tevent_poll.c
+++ b/lib/tevent/tevent_poll.c
@@ -694,7 +694,7 @@ static const struct tevent_ops poll_event_ops = {
 	.set_fd_close_fn	= tevent_common_fd_set_close_fn,
 	.get_fd_flags		= tevent_common_fd_get_flags,
 	.set_fd_flags		= poll_event_set_fd_flags,
-	.add_timer		= tevent_common_add_timer,
+	.add_timer		= tevent_common_add_timer_v2,
 	.schedule_immediate	= tevent_common_schedule_immediate,
 	.add_signal		= tevent_common_add_signal,
 	.loop_once		= poll_event_loop_once,
@@ -712,7 +712,7 @@ static const struct tevent_ops poll_event_mt_ops = {
 	.set_fd_close_fn	= tevent_common_fd_set_close_fn,
 	.get_fd_flags		= tevent_common_fd_get_flags,
 	.set_fd_flags		= poll_event_set_fd_flags,
-	.add_timer		= tevent_common_add_timer,
+	.add_timer		= tevent_common_add_timer_v2,
 	.schedule_immediate	= poll_event_schedule_immediate,
 	.add_signal		= tevent_common_add_signal,
 	.loop_once		= poll_event_loop_once,
diff --git a/lib/tevent/tevent_select.c b/lib/tevent/tevent_select.c
index 5e26569276..bfce246e22 100644
--- a/lib/tevent/tevent_select.c
+++ b/lib/tevent/tevent_select.c
@@ -264,7 +264,7 @@ static const struct tevent_ops select_event_ops = {
 	.set_fd_close_fn	= tevent_common_fd_set_close_fn,
 	.get_fd_flags		= tevent_common_fd_get_flags,
 	.set_fd_flags		= tevent_common_fd_set_flags,
-	.add_timer		= tevent_common_add_timer,
+	.add_timer		= tevent_common_add_timer_v2,
 	.schedule_immediate	= tevent_common_schedule_immediate,
 	.add_signal		= tevent_common_add_signal,
 	.loop_once		= select_event_loop_once,
diff --git a/lib/tevent/tevent_timed.c b/lib/tevent/tevent_timed.c
index fd954f42d8..920d39fe06 100644
--- a/lib/tevent/tevent_timed.c
+++ b/lib/tevent/tevent_timed.c
@@ -133,13 +133,18 @@ struct timeval tevent_timeval_current_ofs(uint32_t secs, uint32_t usecs)
 */
 static int tevent_common_timed_destructor(struct tevent_timer *te)
 {
+	if (te->event_ctx == NULL) {
+		return 0;
+	}
+
 	tevent_debug(te->event_ctx, TEVENT_DEBUG_TRACE,
 		     "Destroying timer event %p \"%s\"\n",
 		     te, te->handler_name);
 
-	if (te->event_ctx) {
-		DLIST_REMOVE(te->event_ctx->timer_events, te);
+	if (te->event_ctx->last_zero_timer == te) {
+		te->event_ctx->last_zero_timer = DLIST_PREV(te);
 	}
+	DLIST_REMOVE(te->event_ctx->timer_events, te);
 
 	return 0;
 }
@@ -153,12 +158,15 @@ static int tevent_common_timed_deny_destructor(struct tevent_timer *te)
   add a timed event
   return NULL on failure (memory allocation error)
 */
-struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev, TALLOC_CTX *mem_ctx,
-					     struct timeval next_event,
-					     tevent_timer_handler_t handler,
-					     void *private_data,
-					     const char *handler_name,
-					     const char *location)
+static struct tevent_timer *tevent_common_add_timer_internal(
+					struct tevent_context *ev,
+					TALLOC_CTX *mem_ctx,
+					struct timeval next_event,
+					tevent_timer_handler_t handler,
+					void *private_data,
+					const char *handler_name,
+					const char *location,
+					bool optimize_zero)
 {
 	struct tevent_timer *te, *prev_te, *cur_te;
 
@@ -173,32 +181,50 @@ struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev, TALLOC_C
 	te->location		= location;
 	te->additional_data	= NULL;
 
+	if (ev->timer_events == NULL) {
+		ev->last_zero_timer = NULL;
+	}
+
 	/* keep the list ordered */
 	prev_te = NULL;
-	/*
-	 * we traverse the list from the tail
-	 * because it's much more likely that
-	 * timers are added at the end of the list
-	 */
-	for (cur_te = DLIST_TAIL(ev->timer_events);
-	     cur_te != NULL;
-	     cur_te = DLIST_PREV(cur_te))
-	{
-		int ret;
-
+	if (optimize_zero && tevent_timeval_is_zero(&te->next_event)) {
 		/*
-		 * if the new event comes before the current
-		 * we continue searching
+		 * Some callers use zero tevent_timer
+		 * instead of tevent_immediate events.
+		 *
+		 * As these can happen very often,
+		 * we remember the last zero timer
+		 * in the list.
 		 */
-		ret = tevent_timeval_compare(&te->next_event,
-					     &cur_te->next_event);
-		if (ret < 0) {
-			continue;
+		prev_te = ev->last_zero_timer;
+		ev->last_zero_timer = te;
+	} else {
+		/*
+		 * we traverse the list from the tail
+		 * because it's much more likely that
+		 * timers are added at the end of the list
+		 */
+		for (cur_te = DLIST_TAIL(ev->timer_events);
+		     cur_te != NULL;
+		     cur_te = DLIST_PREV(cur_te))
+		{
+			int ret;
+
+			/*
+			 * if the new event comes before the current
+			 * we continue searching
+			 */
+			ret = tevent_timeval_compare(&te->next_event,
+						     &cur_te->next_event);
+			if (ret < 0) {
+				continue;
+			}
+
+			break;
 		}
 
-		break;
+		prev_te = cur_te;
 	}
-	prev_te = cur_te;
 
 	DLIST_ADD_AFTER(ev->timer_events, te, prev_te);
 
@@ -210,6 +236,44 @@ struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev, TALLOC_C
 	return te;
 }
 
+struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev,
+					     TALLOC_CTX *mem_ctx,
+					     struct timeval next_event,
+					     tevent_timer_handler_t handler,
+					     void *private_data,
+					     const char *handler_name,
+					     const char *location)
+{
+	/*
+	 * do not use optimization, there are broken Samba
+	 * versions which use tevent_common_add_timer()
+	 * without using tevent_common_loop_timer_delay(),
+	 * it just uses DLIST_REMOVE(ev->timer_events, te)
+	 * and would leave ev->last_zero_timer behind.
+	 */
+	return tevent_common_add_timer_internal(ev, mem_ctx, next_event,
+						handler, private_data,
+						handler_name, location,
+						false);
+}
+
+struct tevent_timer *tevent_common_add_timer_v2(struct tevent_context *ev,
+						TALLOC_CTX *mem_ctx,
+					        struct timeval next_event,
+					        tevent_timer_handler_t handler,
+					        void *private_data,
+					        const char *handler_name,
+					        const char *location)
+{
+	/*
+	 * Here we turn on last_zero_timer optimization
+	 */
+	return tevent_common_add_timer_internal(ev, mem_ctx, next_event,
+						handler, private_data,
+						handler_name, location,
+						true);
+}
+
 /*
   do a single event loop using the events defined in ev
 
@@ -258,6 +322,9 @@ struct timeval tevent_common_loop_timer_delay(struct tevent_context *ev)
 	/* We need to remove the timer from the list before calling the
 	 * handler because in a semi-async inner event loop called from the
 	 * handler we don't want to come across this event again -- vl */
+	if (ev->last_zero_timer == te) {
+		ev->last_zero_timer = DLIST_PREV(te);
+	}
 	DLIST_REMOVE(ev->timer_events, te);
 
 	tevent_debug(te->event_ctx, TEVENT_DEBUG_TRACE,