Introducing a small upgrade to the ast_sched_xxx facility, to keep it from eating...
authorSteve Murphy <murf@digium.com>
Wed, 16 Apr 2008 20:09:39 +0000 (20:09 +0000)
committerSteve Murphy <murf@digium.com>
Wed, 16 Apr 2008 20:09:39 +0000 (20:09 +0000)
git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@114182 65c4cc65-6c06-0410-ace0-fbb531ad65f3

CHANGES
include/asterisk/sched.h
main/sched.c

diff --git a/CHANGES b/CHANGES
index 52f96c2..53accaa 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -615,6 +615,10 @@ Miscellaneous
   * A new option when starting a remote asterisk (rasterisk, asterisk -r) for
      specifying which socket to use to connect to the running Asterisk daemon
      (-s)
+  * Performance enhancements to the sched facility, which is used in
+    the channel drivers, etc. Added hashtabs and doubly-linked lists
+    to speed up deletion; start at the beginning or end of list to
+    speed up insertion.
   * Added Doubly-linked lists after the fashion of linkedlists.h. They are in
     dlinkedlists.h. Doubly-linked lists feature fast deletion times.
     Added regression tests to the tests/ dir, also.
index 3978e32..21a1740 100644 (file)
@@ -27,6 +27,7 @@
 extern "C" {
 #endif
 
+
 /*! \brief Max num of schedule structs
  * \note The max number of schedule structs to keep around
  * for use.  Undefine to disable schedule structure
@@ -64,6 +65,19 @@ extern "C" {
                id = -1; \
        } while (0);
 
+#define AST_SCHED_DEL_UNREF(sched, id, refcall)                        \
+       do { \
+               int _count = 0; \
+               while (id > -1 && ast_sched_del(sched, id) && ++_count < 10) { \
+                       usleep(1); \
+               } \
+               if (_count == 10) \
+                       ast_log(LOG_WARNING, "Unable to cancel schedule ID %d.  This is probably a bug (%s: %s, line %d).\n", id, __FILE__, __PRETTY_FUNCTION__, __LINE__); \
+               if (id > -1) \
+                       refcall; \
+               id = -1; \
+       } while (0);
+
 #define AST_SCHED_REPLACE_VARIABLE(id, sched, when, callback, data, variable) \
        do { \
                int _count = 0; \
@@ -78,6 +92,27 @@ extern "C" {
 #define AST_SCHED_REPLACE(id, sched, when, callback, data) \
                AST_SCHED_REPLACE_VARIABLE(id, sched, when, callback, data, 0)
 
+#define AST_SCHED_REPLACE_VARIABLE_UNREF(id, sched, when, callback, data, variable, unrefcall, addfailcall, refcall) \
+       do { \
+               int _count = 0, _res=1;                                                                                  \
+               void *_data = (void *)ast_sched_find_data(sched, id);                   \
+               while (id > -1 && (_res = ast_sched_del(sched, id) && _count++ < 10)) { \
+                       usleep(1); \
+               } \
+               if (!_res && _data)                                                     \
+                       unrefcall;      /* should ref _data! */         \
+               if (_count == 10) \
+                       ast_log(LOG_WARNING, "Unable to cancel schedule ID %d.  This is probably a bug (%s: %s, line %d).\n", id, __FILE__, __PRETTY_FUNCTION__, __LINE__); \
+               id = ast_sched_add_variable(sched, when, callback, data, variable); \
+               if (id == -1)  \
+                       addfailcall;    \
+               else \
+                       refcall; \
+       } while (0);
+
+#define AST_SCHED_REPLACE_UNREF(id, sched, when, callback, data, unrefcall, addfailcall, refcall) \
+       AST_SCHED_REPLACE_VARIABLE_UNREF(id, sched, when, callback, data, 0, unrefcall, addfailcall, refcall)
+
 struct sched_context;
 
 /*! \brief New schedule context
@@ -101,6 +136,14 @@ void sched_context_destroy(struct sched_context *c);
 typedef int (*ast_sched_cb)(const void *data);
 #define AST_SCHED_CB(a) ((ast_sched_cb)(a))
 
+struct ast_cb_names
+{
+       int numassocs;
+       char *list[10];
+       ast_sched_cb cblist[10];
+};
+char *ast_sched_report(struct sched_context *con, char *buf, int bufsiz, struct ast_cb_names *cbnames);
+               
 /*! \brief Adds a scheduled event
  * Schedule an event to take place at some point in the future.  callback
  * will be called with data as the argument, when milliseconds into the
@@ -155,6 +198,15 @@ int ast_sched_add_variable(struct sched_context *con, int when, ast_sched_cb cal
  */
 int ast_sched_replace_variable(int old_id, struct sched_context *con, int when, ast_sched_cb callback, const void *data, int variable);
 
+       
+/*! \brief Find a sched structure and return the data field associated with it. 
+ * \param con scheduling context in which to search fro the matching id
+ * \param id ID of the scheduled item to find
+ * \return the data field from the matching sched struct if found; else return NULL if not found.
+ */
+
+const void *ast_sched_find_data(struct sched_context *con, int id);
+       
 /*! \brief Deletes a scheduled event
  * Remove this event from being run.  A procedure should not remove its own
  * event, but return 0 instead.  In most cases, you should not call this
@@ -164,6 +216,7 @@ int ast_sched_replace_variable(int old_id, struct sched_context *con, int when,
  * \param id ID of the scheduled item to delete
  * \return Returns 0 on success, -1 on failure
  */
+
 int ast_sched_del(struct sched_context *con, int id);
 
 /*! \brief Determines number of seconds until the next outstanding event to take place
index 3aeeb9d..6ef2972 100644 (file)
@@ -43,9 +43,11 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
 #include "asterisk/lock.h"
 #include "asterisk/utils.h"
 #include "asterisk/linkedlists.h"
+#include "asterisk/dlinkedlists.h"
+#include "asterisk/hashtab.h"
 
 struct sched {
-       AST_LIST_ENTRY(sched) list;
+       AST_DLLIST_ENTRY(sched) list;
        int id;                       /*!< ID number of event */
        struct timeval when;          /*!< Absolute time event should take place */
        int resched;                  /*!< When to reschedule */
@@ -58,7 +60,9 @@ struct sched_context {
        ast_mutex_t lock;
        unsigned int eventcnt;                  /*!< Number of events processed */
        unsigned int schedcnt;                  /*!< Number of outstanding schedule events */
-       AST_LIST_HEAD_NOLOCK(, sched) schedq;   /*!< Schedule entry and main queue */
+       unsigned int highwater;                                 /*!< highest count so far */
+       AST_DLLIST_HEAD_NOLOCK(, sched) schedq;   /*!< Schedule entry and main queue */
+       struct ast_hashtab *schedq_ht;             /*!< hash table for fast searching */
 
 #ifdef SCHED_MAX_CACHE
        AST_LIST_HEAD_NOLOCK(, sched) schedc;   /*!< Cache of unused schedule structures and how many */
@@ -66,6 +70,23 @@ struct sched_context {
 #endif
 };
 
+
+/* hash routines for sched */
+
+static int sched_cmp(const void *a, const void *b)
+{
+       const struct sched *as = a;
+       const struct sched *bs = b;
+       return as->id != bs->id; /* return 0 on a match like strcmp would */
+}
+
+static unsigned int sched_hash(const void *obj)
+{
+       const struct sched *s = obj;
+       unsigned int h = s->id;
+       return h;
+}
+
 struct sched_context *sched_context_create(void)
 {
        struct sched_context *tmp;
@@ -76,6 +97,8 @@ struct sched_context *sched_context_create(void)
        ast_mutex_init(&tmp->lock);
        tmp->eventcnt = 1;
        
+       tmp->schedq_ht = ast_hashtab_create(23, sched_cmp, ast_hashtab_resize_java, ast_hashtab_newsize_java, sched_hash, 1);
+       
        return tmp;
 }
 
@@ -92,8 +115,11 @@ void sched_context_destroy(struct sched_context *con)
 #endif
 
        /* And the queue */
-       while ((s = AST_LIST_REMOVE_HEAD(&con->schedq, list)))
+       while ((s = AST_DLLIST_REMOVE_HEAD(&con->schedq, list)))
                ast_free(s);
+
+       ast_hashtab_destroy(con->schedq_ht, NULL);
+       con->schedq_ht = NULL;
        
        /* And the context */
        ast_mutex_unlock(&con->lock);
@@ -146,10 +172,10 @@ int ast_sched_wait(struct sched_context *con)
        DEBUG(ast_debug(1, "ast_sched_wait()\n"));
 
        ast_mutex_lock(&con->lock);
-       if (AST_LIST_EMPTY(&con->schedq)) {
+       if (AST_DLLIST_EMPTY(&con->schedq)) {
                ms = -1;
        } else {
-               ms = ast_tvdiff_ms(AST_LIST_FIRST(&con->schedq)->when, ast_tvnow());
+               ms = ast_tvdiff_ms(AST_DLLIST_FIRST(&con->schedq)->when, ast_tvnow());
                if (ms < 0)
                        ms = 0;
        }
@@ -166,20 +192,42 @@ int ast_sched_wait(struct sched_context *con)
  */
 static void schedule(struct sched_context *con, struct sched *s)
 {
-        
        struct sched *cur = NULL;
-       
-       AST_LIST_TRAVERSE_SAFE_BEGIN(&con->schedq, cur, list) {
-               if (ast_tvcmp(s->when, cur->when) == -1) {
-                       AST_LIST_INSERT_BEFORE_CURRENT(s, list);
-                       break;
+       int ret;
+       int df = 0;
+       int de = 0;
+       struct sched *first = AST_DLLIST_FIRST(&con->schedq);
+       struct sched *last = AST_DLLIST_LAST(&con->schedq);
+       if (first)
+               df = ast_tvdiff_us(s->when, first->when);
+       if (last)
+               de = ast_tvdiff_us(s->when, last->when);
+       if (df < 0)
+               df = -df;
+       if (de < 0)
+               de = -de;
+       if (df < de)
+               AST_DLLIST_TRAVERSE(&con->schedq, cur, list) {
+                       if (ast_tvcmp(s->when, cur->when) == -1) {
+                               AST_DLLIST_INSERT_BEFORE(&con->schedq, cur, s, list);
+                               break;
+                       }
+               }
+       else
+               AST_DLLIST_TRAVERSE_BACKWARDS(&con->schedq, cur, list) {
+                       if (ast_tvcmp(s->when, cur->when) == 1) {
+                               AST_DLLIST_INSERT_AFTER(&con->schedq, cur, s, list);
+                               break;
+                       }
                }
-       }
-       AST_LIST_TRAVERSE_SAFE_END;
        if (!cur)
-               AST_LIST_INSERT_TAIL(&con->schedq, s, list);
-       
+               AST_DLLIST_INSERT_TAIL(&con->schedq, s, list);
+       ret = ast_hashtab_insert_safe(con->schedq_ht, s);
+       if (!ret)
+               ast_log(LOG_WARNING,"Schedule Queue entry %d is already in table!\n",s->id);
        con->schedcnt++;
+       if (con->schedcnt > con->highwater)
+               con->highwater = con->schedcnt;
 }
 
 /*! \brief
@@ -257,6 +305,16 @@ int ast_sched_add(struct sched_context *con, int when, ast_sched_cb callback, co
        return ast_sched_add_variable(con, when, callback, data, 0);
 }
 
+const void *ast_sched_find_data(struct sched_context *con, int id)
+{
+       struct sched tmp,*res;
+       tmp.id = id;
+       res = ast_hashtab_lookup(con->schedq_ht, &tmp);
+       if (res)
+               return res->data;
+       return NULL;
+}
+       
 /*! \brief
  * Delete the schedule entry with number
  * "id".  It's nearly impossible that there
@@ -265,21 +323,34 @@ int ast_sched_add(struct sched_context *con, int when, ast_sched_cb callback, co
  */
 int ast_sched_del(struct sched_context *con, int id)
 {
-       struct sched *s;
+       struct sched *s, tmp;
 
-       DEBUG(ast_debug(1, "ast_sched_del()\n"));
+       DEBUG(ast_debug(1, "ast_sched_del(%d)\n", id));
        
        ast_mutex_lock(&con->lock);
-       AST_LIST_TRAVERSE_SAFE_BEGIN(&con->schedq, s, list) {
-               if (s->id == id) {
-                       AST_LIST_REMOVE_CURRENT(list);
-                       con->schedcnt--;
-                       sched_release(con, s);
-                       break;
-               }
-       }
-       AST_LIST_TRAVERSE_SAFE_END;
 
+       /* OK, this is the heart of the sched performance upgrade.
+          If we have 4700 peers, we can have 4700+ entries in the
+          schedq list. searching this would take time. So, I add a 
+          hashtab to the context to keep track of each entry, by id.
+          I also leave the linked list alone, almost, --  I implement
+       a doubly-linked list instead, because it would do little good
+          to look up the id in a hashtab, and then have to run thru 
+          a couple thousand entries to remove it from the schedq list! */
+       tmp.id = id;
+       s = ast_hashtab_lookup(con->schedq_ht, &tmp);
+       if (s) {
+               struct sched *x = AST_DLLIST_REMOVE(&con->schedq, s, list);
+               
+               if (!x)
+                       ast_log(LOG_WARNING,"sched entry %d not in the schedq list?\n", s->id);
+
+               if (!ast_hashtab_remove_this_object(con->schedq_ht, s))
+                       ast_log(LOG_WARNING,"Found sched entry %d, then couldn't remove it?\n", s->id);
+               con->schedcnt--;
+               sched_release(con, s);
+       }
+       
 #ifdef DUMP_SCHEDULER
        /* Dump contents of the context while we have the lock so nothing gets screwed up by accident. */
        if (option_debug)
@@ -298,21 +369,57 @@ int ast_sched_del(struct sched_context *con, int id)
        return 0;
 }
 
+
+char *ast_sched_report(struct sched_context *con, char *buf, int bufsiz, struct ast_cb_names *cbnames)
+{
+       int *countlist,i;
+       struct sched *cur;
+       char buf2[1200];
+       ast_sched_cb xxx = NULL;
+       
+       buf[0] = 0;
+       sprintf(buf, " Highwater = %d\n schedcnt = %d\n", con->highwater, con->schedcnt);
+       countlist = ast_calloc(sizeof(int),cbnames->numassocs+1);
+       
+       AST_DLLIST_TRAVERSE(&con->schedq, cur, list) {
+               /* match the callback to the cblist */
+               for (i=0;i<cbnames->numassocs;i++) {
+                       if (cur->callback == cbnames->cblist[i])
+                               break;
+               }
+               if (i < cbnames->numassocs)
+                       countlist[i]++;
+               else {
+                       xxx = cur->callback;
+                       countlist[cbnames->numassocs]++;
+               }
+       }
+       for (i=0;i<cbnames->numassocs;i++) {
+               sprintf(buf2,"    %s : %d\n", cbnames->list[i], countlist[i]);
+               strcat(buf, buf2);
+       }
+       sprintf(buf2,"   <unknown:%p> : %d\n", xxx, countlist[cbnames->numassocs]);
+       strcat( buf, buf2);
+       return buf;
+}
+
+
+       
 /*! \brief Dump the contents of the scheduler to LOG_DEBUG */
 void ast_sched_dump(const struct sched_context *con)
 {
        struct sched *q;
        struct timeval tv = ast_tvnow();
 #ifdef SCHED_MAX_CACHE
-       ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d Cache)\n", con->schedcnt, con->eventcnt - 1, con->schedccnt);
+       ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d Cache, %d high-water)\n", con->schedcnt, con->eventcnt - 1, con->schedccnt, con->highwater);
 #else
-       ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total)\n", con->schedcnt, con->eventcnt - 1);
+       ast_debug(1, "Asterisk Schedule Dump (%d in Q, %d Total, %d high-water)\n", con->schedcnt, con->eventcnt - 1, con->highwater);
 #endif
 
        ast_debug(1, "=============================================================\n");
        ast_debug(1, "|ID    Callback          Data              Time  (sec:ms)   |\n");
        ast_debug(1, "+-----+-----------------+-----------------+-----------------+\n");
-       AST_LIST_TRAVERSE(&con->schedq, q, list) {
+       AST_DLLIST_TRAVERSE(&con->schedq, q, list) {
                struct timeval delta = ast_tvsub(q->when, tv);
 
                ast_debug(1, "|%.4d | %-15p | %-15p | %.6ld : %.6ld |\n", 
@@ -323,6 +430,7 @@ void ast_sched_dump(const struct sched_context *con)
                        (long int)delta.tv_usec);
        }
        ast_debug(1, "=============================================================\n");
+       
 }
 
 /*! \brief
@@ -339,17 +447,20 @@ int ast_sched_runq(struct sched_context *con)
                
        ast_mutex_lock(&con->lock);
 
-       for (numevents = 0; !AST_LIST_EMPTY(&con->schedq); numevents++) {
+       for (numevents = 0; !AST_DLLIST_EMPTY(&con->schedq); numevents++) {
                /* schedule all events which are going to expire within 1ms.
                 * We only care about millisecond accuracy anyway, so this will
                 * help us get more than one event at one time if they are very
                 * close together.
                 */
                tv = ast_tvadd(ast_tvnow(), ast_tv(0, 1000));
-               if (ast_tvcmp(AST_LIST_FIRST(&con->schedq)->when, tv) != -1)
+               if (ast_tvcmp(AST_DLLIST_FIRST(&con->schedq)->when, tv) != -1)
                        break;
                
-               current = AST_LIST_REMOVE_HEAD(&con->schedq, list);
+               current = AST_DLLIST_REMOVE_HEAD(&con->schedq, list);
+               if (!ast_hashtab_remove_this_object(con->schedq_ht, current))
+                       ast_log(LOG_ERROR,"Sched entry %d was in the schedq list but not in the hashtab???\n", current->id);
+
                con->schedcnt--;
 
                /*
@@ -387,15 +498,16 @@ int ast_sched_runq(struct sched_context *con)
 
 long ast_sched_when(struct sched_context *con,int id)
 {
-       struct sched *s;
+       struct sched *s, tmp;
        long secs = -1;
        DEBUG(ast_debug(1, "ast_sched_when()\n"));
 
        ast_mutex_lock(&con->lock);
-       AST_LIST_TRAVERSE(&con->schedq, s, list) {
-               if (s->id == id)
-                       break;
-       }
+       
+       /* these next 2 lines replace a lookup loop */
+       tmp.id = id;
+       s = ast_hashtab_lookup(con->schedq_ht, &tmp);
+       
        if (s) {
                struct timeval now = ast_tvnow();
                secs = s->when.tv_sec - now.tv_sec;