[MAJOR] replaced rbtree with ul2tree.
The rbtree-based wait queue consumes a lot of CPU. Use the ul2tree
instead. Lots of cleanups and code reorganizations made it possible
to reduce the task struct and simplify the code a bit.
diff --git a/include/proto/task.h b/include/proto/task.h
index 8bd973a..424a46c 100644
--- a/include/proto/task.h
+++ b/include/proto/task.h
@@ -2,7 +2,7 @@
include/proto/task.h
Functions for task management.
- Copyright (C) 2000-2006 Willy Tarreau - w@1wt.eu
+ Copyright (C) 2000-2007 Willy Tarreau - w@1wt.eu
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
@@ -27,42 +27,66 @@
#include <common/config.h>
#include <common/memory.h>
+#include <common/mini-clist.h>
+#include <common/standard.h>
+
#include <types/task.h>
+extern void *run_queue;
+
+/* needed later */
+void *tree_delete(void *node);
/* puts the task <t> in run queue <q>, and returns <t> */
-static inline struct task *task_wakeup(struct task **q, struct task *t)
+static inline struct task *task_wakeup(struct task *t)
{
if (t->state == TASK_RUNNING)
return t;
- else {
- t->rqnext = *q;
- t->state = TASK_RUNNING;
- return *q = t;
+
+ if (t->qlist.p != NULL)
+ DLIST_DEL(&t->qlist);
+
+ DLIST_ADD(run_queue, &t->qlist);
+ t->state = TASK_RUNNING;
+
+ if (likely(t->wq)) {
+ tree_delete(t->wq);
+ t->wq = NULL;
}
+
+ return t;
}
-/* removes the task <t> from the queue <q>
- * <s> MUST be <q>'s first task.
- * set the run queue to point to the next one, and return it
+/* removes the task <t> from the run queue if it was in it.
+ * returns <t>.
*/
-static inline struct task *task_sleep(struct task **q, struct task *t)
+static inline struct task *task_sleep(struct task *t)
{
if (t->state == TASK_RUNNING) {
- *q = t->rqnext;
- t->state = TASK_IDLE; /* tell that s has left the run queue */
+ DLIST_DEL(&t->qlist);
+ t->qlist.p = NULL;
+ t->state = TASK_IDLE;
}
- return *q; /* return next running task */
+ return t;
}
/*
- * removes the task <t> from its wait queue. It must have already been removed
- * from the run queue. A pointer to the task itself is returned.
+ * unlinks the task from wherever it is queued :
+ * - eternity_queue, run_queue
+ * - wait queue : wq not null => remove carrier node too
+ * A pointer to the task itself is returned.
*/
static inline struct task *task_delete(struct task *t)
{
- rb_erase(&t->rb_node, t->wq);
- t->wq = NULL;
+ if (t->qlist.p != NULL) {
+ DLIST_DEL(&t->qlist);
+ t->qlist.p = NULL;
+ }
+
+ if (t->wq) {
+ tree_delete(t->wq);
+ t->wq = NULL;
+ }
return t;
}
diff --git a/include/types/task.h b/include/types/task.h
index d09efae..1fd78be 100644
--- a/include/types/task.h
+++ b/include/types/task.h
@@ -25,7 +25,8 @@
#include <sys/time.h>
#include <common/config.h>
-#include <common/rbtree.h>
+#include <common/mini-clist.h>
+#include <import/tree.h>
/* values for task->state */
#define TASK_IDLE 0
@@ -33,10 +34,9 @@
/* The base for all tasks */
struct task {
- struct rb_node rb_node;
- struct rb_root *wq;
- struct task *rqnext; /* chaining in run queue ... */
- int state; /* task state : IDLE or RUNNING */
+ struct list qlist; /* chaining in the same queue; bidirectionnal but not circular */
+ struct ultree *wq; /* NULL if unqueued, or back ref to the carrier node in the WQ */
+ int state; /* task state : IDLE or RUNNING */
struct timeval expire; /* next expiration time for this task, use only for fast sorting */
int (*process)(struct task *t); /* the function which processes the task */
void *context; /* the task's context */
@@ -45,10 +45,6 @@
#define sizeof_task sizeof(struct task)
extern void **pool_task;
-extern struct rb_root wait_queue[2];
-extern struct task *rq;
-
-
#endif /* _TYPES_TASK_H */
/*