[Asterisk-code-review] scheduler: Use stack for allocating sched IDs. (asterisk[certified/13.1])

Mark Michelson asteriskteam at digium.com
Fri Sep 11 11:09:24 CDT 2015


Mark Michelson has uploaded a new change for review.

  https://gerrit.asterisk.org/1257

Change subject: scheduler: Use stack for allocating sched IDs.
......................................................................

scheduler: Use stack for allocating sched IDs.

It has been observed that on long-running busy systems, a scheduler
context can eventually hit INT_MAX for its assigned IDs and end up
overflowing into a very low negative number. When this occurs, this can
result in odd behaviors, because a negative return is interpreted by
callers as being a failure. However, the item actually was successfully
scheduled. The result may be that a freed item remains in the scheduler,
resulting in a crash at some point in the future.

The scheduler can overflow because every time that an item is added to
the scheduler, a counter is bumped and that counter's current value is
assigned as the new item's ID.

This patch introduces a new method for assigning scheduler IDs. Instead
of assigning from a counter, a stack of available IDs is maintained.
When assigning a new ID, an ID is pulled from the stack. When a
scheduler item is released, its ID is pushed back onto the stack. This
way, IDs may be reused when they become available, and the growth of ID
numbers is directly related to concurrent activity within a scheduler
context rather than the uptime of the system.

Change-Id: I532708eef8f669d823457d7fefdad9a6078b99b2
---
M main/sched.c
1 file changed, 93 insertions(+), 19 deletions(-)


  git pull ssh://gerrit.asterisk.org:29418/asterisk refs/changes/57/1257/1

diff --git a/main/sched.c b/main/sched.c
index 173d2c0..c5536af 100644
--- a/main/sched.c
+++ b/main/sched.c
@@ -62,9 +62,25 @@
 
 AST_THREADSTORAGE(last_del_id);
 
+/*!
+ * \brief Scheduler ID holder
+ *
+ * These form a stack on a scheduler context. When a new
+ * scheduled item is created, a sched_id is popped off the
+ * stack and its id is assigned to the new scheduled item.
+ */
+struct sched_id {
+	/*! Immutable ID number that is copied onto the scheduled task */
+	int id;
+	AST_LIST_ENTRY(sched_id) list;
+};
+
 struct sched {
 	AST_LIST_ENTRY(sched) list;
-	int id;                       /*!< ID number of event */
+	/*! Copy of the sched_id's id. */
+	int id;
+	/*! The ID that has been popped off the scheduler context's stack */
+	struct sched_id *sched_id;
 	struct timeval when;          /*!< Absolute time event should take place */
 	int resched;                  /*!< When to reschedule */
 	int variable;                 /*!< Use return value from callback to reschedule */
@@ -99,6 +115,10 @@
 	AST_LIST_HEAD_NOLOCK(, sched) schedc;   /*!< Cache of unused schedule structures and how many */
 	unsigned int schedccnt;
 #endif
+	/*! Stack of scheduler task IDs to assign */
+	AST_LIST_HEAD_NOLOCK(, sched_id) id_stack;
+	/*! The number of IDs in the id_stack */
+	size_t id_stack_size;
 };
 
 static void *sched_run(void *data)
@@ -208,6 +228,8 @@
 	ast_mutex_init(&tmp->lock);
 	tmp->eventcnt = 1;
 
+	AST_LIST_HEAD_INIT_NOLOCK(&tmp->id_stack);
+
 	if (!(tmp->sched_heap = ast_heap_create(8, sched_time_cmp,
 			offsetof(struct sched, __heap_index)))) {
 		ast_sched_context_destroy(tmp);
@@ -219,6 +241,7 @@
 
 static void sched_free(struct sched *task)
 {
+	ast_free(task->sched_id);
 	ast_cond_destroy(&task->cond);
 	ast_free(task);
 }
@@ -226,6 +249,7 @@
 void ast_sched_context_destroy(struct ast_sched_context *con)
 {
 	struct sched *s;
+	struct sched_id *sid;
 
 	sched_thread_destroy(con);
 	con->sched_thread = NULL;
@@ -246,10 +270,72 @@
 		con->sched_heap = NULL;
 	}
 
+	while ((sid = AST_LIST_REMOVE_HEAD(&con->id_stack, list))) {
+		ast_free(sid);
+	}
+
 	ast_mutex_unlock(&con->lock);
 	ast_mutex_destroy(&con->lock);
 
 	ast_free(con);
+}
+
+#define ID_STACK_INCREMENT 16
+
+static int add_ids(struct ast_sched_context *con)
+{
+	size_t new_size;
+	int i;
+
+	/* So we don't go overboard with the mallocs here, we'll just up
+	 * the size of the list by a fixed amount each time instead of
+	 * multiplying the size by any particular factor
+	 */
+	new_size = con->id_stack_size + ID_STACK_INCREMENT;
+	for (i = con->id_stack_size; i < new_size; ++i) {
+		struct sched_id *new_id;
+
+		new_id = ast_calloc(1, sizeof(*new_id));
+		if (!new_id) {
+			return -1;
+		}
+		new_id->id = i;
+		AST_LIST_INSERT_TAIL(&con->id_stack, new_id, list);
+	}
+	con->id_stack_size = new_size;
+
+	return 0;
+}
+
+static int set_sched_id(struct ast_sched_context *con, struct sched *new_sched) {
+	if (AST_LIST_EMPTY(&con->id_stack) && add_ids(con)) {
+		return -1;
+	}
+
+	new_sched->sched_id = AST_LIST_REMOVE_HEAD(&con->id_stack, list);
+	new_sched->id = new_sched->sched_id->id;
+	return 0;
+}
+
+static void sched_release(struct ast_sched_context *con, struct sched *tmp)
+{
+	/*
+	 * Add to the cache, or just free() if we
+	 * already have too many cache entries
+	 */
+
+	if (tmp->sched_id) {
+		AST_LIST_INSERT_HEAD(&con->id_stack, tmp->sched_id, list);
+		tmp->sched_id = NULL;
+	}
+
+#ifdef SCHED_MAX_CACHE
+	if (con->schedccnt < SCHED_MAX_CACHE) {
+		AST_LIST_INSERT_HEAD(&con->schedc, tmp, list);
+		con->schedccnt++;
+	} else
+#endif
+		sched_free(tmp);
 }
 
 static struct sched *sched_alloc(struct ast_sched_context *con)
@@ -263,30 +349,18 @@
 #ifdef SCHED_MAX_CACHE
 	if ((tmp = AST_LIST_REMOVE_HEAD(&con->schedc, list))) {
 		con->schedccnt--;
-	} else 
+	} else
 #endif
 	{
 		tmp = ast_calloc(1, sizeof(*tmp));
 		ast_cond_init(&tmp->cond, NULL);
 	}
 
+	if (set_sched_id(con, tmp)) {
+		sched_release(con, tmp);
+	}
+
 	return tmp;
-}
-
-static void sched_release(struct ast_sched_context *con, struct sched *tmp)
-{
-	/*
-	 * Add to the cache, or just free() if we
-	 * already have too many cache entries
-	 */
-
-#ifdef SCHED_MAX_CACHE
-	if (con->schedccnt < SCHED_MAX_CACHE) {
-		AST_LIST_INSERT_HEAD(&con->schedc, tmp, list);
-		con->schedccnt++;
-	} else
-#endif
-		sched_free(tmp);
 }
 
 /*! \brief
@@ -368,7 +442,7 @@
 
 	ast_mutex_lock(&con->lock);
 	if ((tmp = sched_alloc(con))) {
-		tmp->id = con->eventcnt++;
+		con->eventcnt++;
 		tmp->callback = callback;
 		tmp->data = data;
 		tmp->resched = when;

-- 
To view, visit https://gerrit.asterisk.org/1257
To unsubscribe, visit https://gerrit.asterisk.org/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: I532708eef8f669d823457d7fefdad9a6078b99b2
Gerrit-PatchSet: 1
Gerrit-Project: asterisk
Gerrit-Branch: certified/13.1
Gerrit-Owner: Mark Michelson <mmichelson at digium.com>



More information about the asterisk-code-review mailing list