Merge branch 'rbtree'
diff --git a/Makefile b/Makefile
index 48f4775..1d89457 100644
--- a/Makefile
+++ b/Makefile
@@ -197,7 +197,7 @@
src/time.o src/fd.o src/regex.o src/cfgparse.o src/server.o \
src/checks.o src/queue.o src/capture.o src/client.o src/proxy.o \
src/proto_http.o src/stream_sock.o src/appsession.o src/backend.o \
- src/session.o src/hdr_idx.o
+ src/session.o src/hdr_idx.o src/rbtree.o
haproxy: $(OBJS)
$(LD) $(LDFLAGS) -o $@ $^ $(LIBS)
diff --git a/Makefile.bsd b/Makefile.bsd
index 7cde194..40229fa 100644
--- a/Makefile.bsd
+++ b/Makefile.bsd
@@ -87,7 +87,7 @@
src/time.o src/fd.o src/regex.o src/cfgparse.o src/server.o \
src/checks.o src/queue.o src/capture.o src/client.o src/proxy.o \
src/proto_http.o src/stream_sock.o src/appsession.o src/backend.o \
- src/session.o src/hdr_idx.o
+ src/session.o src/hdr_idx.o src/rbtree.o
all: haproxy
diff --git a/include/common/rbtree.h b/include/common/rbtree.h
new file mode 100644
index 0000000..107e8d2
--- /dev/null
+++ b/include/common/rbtree.h
@@ -0,0 +1,150 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ Some example of insert and search follows here. The search is a plain
+ normal search over an ordered tree. The insert instead must be implemented
+ int two steps: as first thing the code must insert the element in
+ order as a red leaf in the tree, then the support library function
+ rb_insert_color() must be called. Such function will do the
+ not trivial work to rebalance the rbtree if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+ unsigned long offset)
+{
+ struct rb_node * n = inode->i_rb_page_cache.rb_node;
+ struct page * page;
+
+ while (n)
+ {
+ page = rb_entry(n, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ n = n->rb_left;
+ else if (offset > page->offset)
+ n = n->rb_right;
+ else
+ return page;
+ }
+ return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+ struct rb_node * parent = NULL;
+ struct page * page;
+
+ while (*p)
+ {
+ parent = *p;
+ page = rb_entry(parent, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ p = &(*p)->rb_left;
+ else if (offset > page->offset)
+ p = &(*p)->rb_right;
+ else
+ return page;
+ }
+
+ rb_link_node(node, parent, p);
+
+ return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct page * ret;
+ if ((ret = __rb_insert_page_cache(inode, offset, node)))
+ goto out;
+ rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+ return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+/*
+#include <linux/kernel.h>
+#include <linux/stddef.h>
+*/
+
+struct rb_node
+{
+ struct rb_node *rb_parent;
+ int rb_color;
+#define RB_RED 0
+#define RB_BLACK 1
+ struct rb_node *rb_right;
+ struct rb_node *rb_left;
+};
+
+struct rb_root
+{
+ struct rb_node *rb_node;
+};
+
+// Copy from linux kernel 2.6 source (kernel.h, stddef.h)
+#define container_of(ptr, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (ptr); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+extern void rb_insert_color(struct rb_node *, struct rb_root *);
+extern void rb_erase(struct rb_node *, struct rb_root *);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next(struct rb_node *);
+extern struct rb_node *rb_prev(struct rb_node *);
+extern struct rb_node *rb_first(struct rb_root *);
+extern struct rb_node *rb_last(struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
+
+static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
+ struct rb_node ** rb_link)
+{
+ node->rb_parent = parent;
+ node->rb_color = RB_RED;
+ node->rb_left = node->rb_right = NULL;
+
+ *rb_link = node;
+}
+
+#endif /* _LINUX_RBTREE_H */
diff --git a/include/proto/task.h b/include/proto/task.h
index 70abb82..8bd973a 100644
--- a/include/proto/task.h
+++ b/include/proto/task.h
@@ -61,8 +61,8 @@
*/
static inline struct task *task_delete(struct task *t)
{
- t->prev->next = t->next;
- t->next->prev = t->prev;
+ rb_erase(&t->rb_node, t->wq);
+ t->wq = NULL;
return t;
}
diff --git a/include/types/task.h b/include/types/task.h
index 6b1df22..d09efae 100644
--- a/include/types/task.h
+++ b/include/types/task.h
@@ -25,6 +25,7 @@
#include <sys/time.h>
#include <common/config.h>
+#include <common/rbtree.h>
/* values for task->state */
#define TASK_IDLE 0
@@ -32,9 +33,9 @@
/* The base for all tasks */
struct task {
- struct task *next, *prev; /* chaining ... */
+ struct rb_node rb_node;
+ struct rb_root *wq;
struct task *rqnext; /* chaining in run queue ... */
- struct task *wq; /* the wait queue this task is in */
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 */
@@ -44,7 +45,7 @@
#define sizeof_task sizeof(struct task)
extern void **pool_task;
-extern struct task wait_queue[2];
+extern struct rb_root wait_queue[2];
extern struct task *rq;
diff --git a/src/appsession.c b/src/appsession.c
index a63116d..62b096f 100644
--- a/src/appsession.c
+++ b/src/appsession.c
@@ -113,8 +113,8 @@
if (!initialized) {
if ((t = pool_alloc(task)) == NULL)
return -1;
- t->next = t->prev = t->rqnext = NULL;
- t->wq = LIST_HEAD(wait_queue[0]);
+ t->wq = NULL;
+ t->rqnext = NULL;
t->state = TASK_IDLE;
t->context = NULL;
tv_delayfrom(&t->expire, &now, TBLCHKINT);
diff --git a/src/cfgparse.c b/src/cfgparse.c
index 8b6e94d..c49ce21 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -2297,8 +2297,8 @@
return -1;
}
- t->next = t->prev = t->rqnext = NULL; /* task not in run queue yet */
- t->wq = LIST_HEAD(wait_queue[1]); /* already assigned to the eternity queue */
+ t->rqnext = NULL;
+ t->wq = NULL;
t->state = TASK_IDLE;
t->process = process_srv_queue;
t->context = newsrv;
@@ -2344,8 +2344,8 @@
return -1;
}
- t->next = t->prev = t->rqnext = NULL; /* task not in run queue yet */
- t->wq = LIST_HEAD(wait_queue[0]); /* but already has a wait queue assigned */
+ t->wq = NULL;
+ t->rqnext = NULL;
t->state = TASK_IDLE;
t->process = process_chk;
t->context = newsrv;
diff --git a/src/client.c b/src/client.c
index f0e698d..a8aad8e 100644
--- a/src/client.c
+++ b/src/client.c
@@ -150,8 +150,8 @@
if (p->options & PR_O_TCP_CLI_KA)
setsockopt(cfd, SOL_SOCKET, SO_KEEPALIVE, (char *) &one, sizeof(one));
- t->next = t->prev = t->rqnext = NULL; /* task not in run queue yet */
- t->wq = LIST_HEAD(wait_queue[0]); /* but already has a wait queue assigned */
+ t->wq = NULL;
+ t->rqnext = NULL;
t->state = TASK_IDLE;
t->process = process_session;
t->context = s;
diff --git a/src/haproxy.c b/src/haproxy.c
index 19fffd9..84ee209 100644
--- a/src/haproxy.c
+++ b/src/haproxy.c
@@ -259,12 +259,13 @@
void dump(int sig)
{
- struct task *t, *tnext;
+ struct task *t;
struct session *s;
+ struct rb_node *node;
- tnext = ((struct task *)LIST_HEAD(wait_queue[0]))->next;
- while ((t = tnext) != LIST_HEAD(wait_queue[0])) { /* we haven't looped ? */
- tnext = t->next;
+ for(node = rb_first(&wait_queue[0]);
+ node != NULL; node = rb_next(node)) {
+ t = rb_entry(node, struct task, rb_node);
s = t->context;
qfprintf(stderr,"[dump] wq: task %p, still %ld ms, "
"cli=%d, srv=%d, cr=%d, cw=%d, sr=%d, sw=%d, "
diff --git a/src/rbtree.c b/src/rbtree.c
new file mode 100644
index 0000000..86b21ba
--- /dev/null
+++ b/src/rbtree.c
@@ -0,0 +1,399 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+
+/*
+#include <linux/rbtree.h>
+#include <linux/module.h>
+*/
+
+#include <stdlib.h>
+#include <common/rbtree.h>
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *right = node->rb_right;
+
+ if ((node->rb_right = right->rb_left))
+ right->rb_left->rb_parent = node;
+ right->rb_left = node;
+
+ if ((right->rb_parent = node->rb_parent))
+ {
+ if (node == node->rb_parent->rb_left)
+ node->rb_parent->rb_left = right;
+ else
+ node->rb_parent->rb_right = right;
+ }
+ else
+ root->rb_node = right;
+ node->rb_parent = right;
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *left = node->rb_left;
+
+ if ((node->rb_left = left->rb_right))
+ left->rb_right->rb_parent = node;
+ left->rb_right = node;
+
+ if ((left->rb_parent = node->rb_parent))
+ {
+ if (node == node->rb_parent->rb_right)
+ node->rb_parent->rb_right = left;
+ else
+ node->rb_parent->rb_left = left;
+ }
+ else
+ root->rb_node = left;
+ node->rb_parent = left;
+}
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *parent, *gparent;
+
+ while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
+ {
+ gparent = parent->rb_parent;
+
+ if (parent == gparent->rb_left)
+ {
+ {
+ register struct rb_node *uncle = gparent->rb_right;
+ if (uncle && uncle->rb_color == RB_RED)
+ {
+ uncle->rb_color = RB_BLACK;
+ parent->rb_color = RB_BLACK;
+ gparent->rb_color = RB_RED;
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_right == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_left(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ parent->rb_color = RB_BLACK;
+ gparent->rb_color = RB_RED;
+ __rb_rotate_right(gparent, root);
+ } else {
+ {
+ register struct rb_node *uncle = gparent->rb_left;
+ if (uncle && uncle->rb_color == RB_RED)
+ {
+ uncle->rb_color = RB_BLACK;
+ parent->rb_color = RB_BLACK;
+ gparent->rb_color = RB_RED;
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_left == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_right(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ parent->rb_color = RB_BLACK;
+ gparent->rb_color = RB_RED;
+ __rb_rotate_left(gparent, root);
+ }
+ }
+
+ root->rb_node->rb_color = RB_BLACK;
+}
+// EXPORT_SYMBOL(rb_insert_color);
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+ struct rb_root *root)
+{
+ struct rb_node *other;
+
+ while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
+ {
+ if (parent->rb_left == node)
+ {
+ other = parent->rb_right;
+ if (other->rb_color == RB_RED)
+ {
+ other->rb_color = RB_BLACK;
+ parent->rb_color = RB_RED;
+ __rb_rotate_left(parent, root);
+ other = parent->rb_right;
+ }
+ if ((!other->rb_left ||
+ other->rb_left->rb_color == RB_BLACK)
+ && (!other->rb_right ||
+ other->rb_right->rb_color == RB_BLACK))
+ {
+ other->rb_color = RB_RED;
+ node = parent;
+ parent = node->rb_parent;
+ }
+ else
+ {
+ if (!other->rb_right ||
+ other->rb_right->rb_color == RB_BLACK)
+ {
+ register struct rb_node *o_left;
+ if ((o_left = other->rb_left))
+ o_left->rb_color = RB_BLACK;
+ other->rb_color = RB_RED;
+ __rb_rotate_right(other, root);
+ other = parent->rb_right;
+ }
+ other->rb_color = parent->rb_color;
+ parent->rb_color = RB_BLACK;
+ if (other->rb_right)
+ other->rb_right->rb_color = RB_BLACK;
+ __rb_rotate_left(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ else
+ {
+ other = parent->rb_left;
+ if (other->rb_color == RB_RED)
+ {
+ other->rb_color = RB_BLACK;
+ parent->rb_color = RB_RED;
+ __rb_rotate_right(parent, root);
+ other = parent->rb_left;
+ }
+ if ((!other->rb_left ||
+ other->rb_left->rb_color == RB_BLACK)
+ && (!other->rb_right ||
+ other->rb_right->rb_color == RB_BLACK))
+ {
+ other->rb_color = RB_RED;
+ node = parent;
+ parent = node->rb_parent;
+ }
+ else
+ {
+ if (!other->rb_left ||
+ other->rb_left->rb_color == RB_BLACK)
+ {
+ register struct rb_node *o_right;
+ if ((o_right = other->rb_right))
+ o_right->rb_color = RB_BLACK;
+ other->rb_color = RB_RED;
+ __rb_rotate_left(other, root);
+ other = parent->rb_left;
+ }
+ other->rb_color = parent->rb_color;
+ parent->rb_color = RB_BLACK;
+ if (other->rb_left)
+ other->rb_left->rb_color = RB_BLACK;
+ __rb_rotate_right(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ }
+ if (node)
+ node->rb_color = RB_BLACK;
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *child, *parent;
+ int color;
+
+ if (!node->rb_left)
+ child = node->rb_right;
+ else if (!node->rb_right)
+ child = node->rb_left;
+ else
+ {
+ struct rb_node *old = node, *left;
+
+ node = node->rb_right;
+ while ((left = node->rb_left) != NULL)
+ node = left;
+ child = node->rb_right;
+ parent = node->rb_parent;
+ color = node->rb_color;
+
+ if (child)
+ child->rb_parent = parent;
+ if (parent)
+ {
+ if (parent->rb_left == node)
+ parent->rb_left = child;
+ else
+ parent->rb_right = child;
+ }
+ else
+ root->rb_node = child;
+
+ if (node->rb_parent == old)
+ parent = node;
+ node->rb_parent = old->rb_parent;
+ node->rb_color = old->rb_color;
+ node->rb_right = old->rb_right;
+ node->rb_left = old->rb_left;
+
+ if (old->rb_parent)
+ {
+ if (old->rb_parent->rb_left == old)
+ old->rb_parent->rb_left = node;
+ else
+ old->rb_parent->rb_right = node;
+ } else
+ root->rb_node = node;
+
+ old->rb_left->rb_parent = node;
+ if (old->rb_right)
+ old->rb_right->rb_parent = node;
+ goto color;
+ }
+
+ parent = node->rb_parent;
+ color = node->rb_color;
+
+ if (child)
+ child->rb_parent = parent;
+ if (parent)
+ {
+ if (parent->rb_left == node)
+ parent->rb_left = child;
+ else
+ parent->rb_right = child;
+ }
+ else
+ root->rb_node = child;
+
+ color:
+ if (color == RB_BLACK)
+ __rb_erase_color(child, parent, root);
+}
+// EXPORT_SYMBOL(rb_erase);
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_left)
+ n = n->rb_left;
+ return n;
+}
+// EXPORT_SYMBOL(rb_first);
+
+struct rb_node *rb_last(struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_right)
+ n = n->rb_right;
+ return n;
+}
+// EXPORT_SYMBOL(rb_last);
+
+struct rb_node *rb_next(struct rb_node *node)
+{
+ /* If we have a right-hand child, go down and then left as far
+ as we can. */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return node;
+ }
+
+ /* No right-hand children. Everything down and left is
+ smaller than us, so any 'next' node must be in the general
+ direction of our parent. Go up the tree; any time the
+ ancestor is a right-hand child of its parent, keep going
+ up. First time it's a left-hand child of its parent, said
+ parent is our 'next' node. */
+ while (node->rb_parent && node == node->rb_parent->rb_right)
+ node = node->rb_parent;
+
+ return node->rb_parent;
+}
+// EXPORT_SYMBOL(rb_next);
+
+struct rb_node *rb_prev(struct rb_node *node)
+{
+ /* If we have a left-hand child, go down and then right as far
+ as we can. */
+ if (node->rb_left) {
+ node = node->rb_left;
+ while (node->rb_right)
+ node=node->rb_right;
+ return node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while (node->rb_parent && node == node->rb_parent->rb_left)
+ node = node->rb_parent;
+
+ return node->rb_parent;
+}
+// EXPORT_SYMBOL(rb_prev);
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = victim->rb_parent;
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (parent) {
+ if (victim == parent->rb_left)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else {
+ root->rb_node = new;
+ }
+ if (victim->rb_left)
+ victim->rb_left->rb_parent = new;
+ if (victim->rb_right)
+ victim->rb_right->rb_parent = new;
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
+// EXPORT_SYMBOL(rb_replace_node);
diff --git a/src/task.c b/src/task.c
index 1f567b9..beddb27 100644
--- a/src/task.c
+++ b/src/task.c
@@ -22,112 +22,86 @@
void **pool_task= NULL;
struct task *rq = NULL; /* global run queue */
-struct task wait_queue[2] = { /* global wait queue */
- {
- prev:LIST_HEAD(wait_queue[0]), /* expirable tasks */
- next:LIST_HEAD(wait_queue[0]),
- },
- {
- prev:LIST_HEAD(wait_queue[1]), /* non-expirable tasks */
- next:LIST_HEAD(wait_queue[1]),
- },
+
+struct rb_root wait_queue[2] = {
+ RB_ROOT,
+ RB_ROOT,
};
-/* inserts <task> into its assigned wait queue, where it may already be. In this case, it
- * may be only moved or left where it was, depending on its timing requirements.
- * <task> is returned.
- */
+static inline void __rb_insert_task_queue(struct task *newtask)
+{
+ struct rb_node **p = &newtask->wq->rb_node;
+ struct rb_node *parent = NULL;
+ struct task * task;
+
+ while (*p)
+ {
+ parent = *p;
+ task = rb_entry(parent, struct task, rb_node);
+ if (tv_cmp2(&task->expire, &newtask->expire) >= 0)
+ p = &(*p)->rb_left;
+ else
+ p = &(*p)->rb_right;
+ }
+ rb_link_node(&newtask->rb_node, parent, p);
+}
+
+static inline void rb_insert_task_queue(struct task *newtask)
+{
+ __rb_insert_task_queue(newtask);
+ rb_insert_color(&newtask->rb_node, newtask->wq);
+}
+
+
struct task *task_queue(struct task *task)
{
- struct task *list = task->wq;
- struct task *start_from;
+ struct rb_node *node;
+ struct task *next, *prev;
- /* This is a very dirty hack to queue non-expirable tasks in another queue
- * in order to avoid pulluting the tail of the standard queue. This will go
- * away with the new O(log(n)) scheduler anyway.
- */
if (tv_iseternity(&task->expire)) {
- /* if the task was queued in the standard wait queue, we must dequeue it */
- if (task->prev) {
- if (task->wq == LIST_HEAD(wait_queue[1]))
+ if (task->wq) {
+ if (task->wq == &wait_queue[1])
return task;
- else {
+ else
task_delete(task);
- task->prev = NULL;
- }
}
- list = task->wq = LIST_HEAD(wait_queue[1]);
+ task->wq = &wait_queue[1];
+ rb_insert_task_queue(task);
+ return task;
} else {
- /* if the task was queued in the eternity queue, we must dequeue it */
- if (task->prev && (task->wq == LIST_HEAD(wait_queue[1]))) {
- task_delete(task);
- task->prev = NULL;
- list = task->wq = LIST_HEAD(wait_queue[0]);
- }
- }
-
- /* next, test if the task was already in a list */
- if (task->prev == NULL) {
- // start_from = list;
- start_from = list->prev;
- /* insert the unlinked <task> into the list, searching back from the last entry */
- while (start_from != list && tv_cmp2(&task->expire, &start_from->expire) < 0) {
- start_from = start_from->prev;
- }
-
- // while (start_from->next != list && tv_cmp2(&task->expire, &start_from->next->expire) > 0) {
- // start_from = start_from->next;
- // stats_tsk_nsrch++;
- // }
- }
- else if (task->prev == list ||
- tv_cmp2(&task->expire, &task->prev->expire) >= 0) { /* walk right */
- start_from = task->next;
- if (start_from == list || tv_cmp2(&task->expire, &start_from->expire) <= 0) {
- return task; /* it's already in the right place */
+ if (task->wq != &wait_queue[0]) {
+ if (task->wq)
+ task_delete(task);
+ task->wq = &wait_queue[0];
+ rb_insert_task_queue(task);
+ return task;
}
- /* if the task is not at the right place, there's little chance that
- * it has only shifted a bit, and it will nearly always be queued
- * at the end of the list because of constant timeouts
- * (observed in real case).
- */
-#ifndef WE_REALLY_THINK_THAT_THIS_TASK_MAY_HAVE_SHIFTED
- start_from = list->prev; /* assume we'll queue to the end of the list */
- while (start_from != list && tv_cmp2(&task->expire, &start_from->expire) < 0) {
- start_from = start_from->prev;
- }
-#else /* WE_REALLY_... */
- /* insert the unlinked <task> into the list, searching after position <start_from> */
- while (start_from->next != list && tv_cmp2(&task->expire, &start_from->next->expire) > 0) {
- start_from = start_from->next;
+ // check whether task should be re insert
+ node = rb_prev(&task->rb_node);
+ if (node) {
+ prev = rb_entry(node, struct task, rb_node);
+ if (tv_cmp2(&prev->expire, &task->expire) >= 0) {
+ task_delete(task);
+ task->wq = &wait_queue[0];
+ rb_insert_task_queue(task);
+ return task;
+ }
}
-#endif /* WE_REALLY_... */
- /* we need to unlink it now */
- task_delete(task);
- }
- else { /* walk left. */
-#ifdef LEFT_TO_TOP /* not very good */
- start_from = list;
- while (start_from->next != list && tv_cmp2(&task->expire, &start_from->next->expire) > 0) {
- start_from = start_from->next;
- }
-#else
- start_from = task->prev->prev; /* valid because of the previous test above */
- while (start_from != list && tv_cmp2(&task->expire, &start_from->expire) < 0) {
- start_from = start_from->prev;
+ node = rb_next(&task->rb_node);
+ if (node) {
+ next = rb_entry(node, struct task, rb_node);
+ if (tv_cmp2(&task->expire, &next->expire) > 0) {
+ task_delete(task);
+ task->wq = &wait_queue[0];
+ rb_insert_task_queue(task);
+ return task;
+ }
}
-#endif
- /* we need to unlink it now */
- task_delete(task);
+ return task;
}
- task->prev = start_from;
- task->next = start_from->next;
- task->next->prev = task;
- start_from->next = task;
- return task;
}
/*
@@ -136,37 +110,26 @@
* - call all runnable tasks
* - call maintain_proxies() to enable/disable the listeners
* - return the delay till next event in ms, -1 = wait indefinitely
- * Note: this part should be rewritten with the O(ln(n)) scheduler.
*
*/
-
int process_runnable_tasks()
{
int next_time;
int time2;
- struct task *t, *tnext;
+ struct task *t;
+ struct rb_node *node;
- next_time = TIME_ETERNITY; /* set the timer to wait eternally first */
-
- /* look for expired tasks and add them to the run queue.
- */
- tnext = ((struct task *)LIST_HEAD(wait_queue[0]))->next;
- while ((t = tnext) != LIST_HEAD(wait_queue[0])) { /* we haven't looped ? */
- tnext = t->next;
+ next_time = TIME_ETERNITY;
+ for (node = rb_first(&wait_queue[0]);
+ node != NULL; node = rb_next(node)) {
+ t = rb_entry(node, struct task, rb_node);
if (t->state & TASK_RUNNING)
continue;
-
if (tv_iseternity(&t->expire))
continue;
-
- /* wakeup expired entries. It doesn't matter if they are
- * already running because of a previous event
- */
if (tv_cmp_ms(&t->expire, &now) <= 0) {
task_wakeup(&rq, t);
- }
- else {
- /* first non-runnable task. Use its expiration date as an upper bound */
+ } else {
int temp_time = tv_remain(&now, &t->expire);
if (temp_time)
next_time = temp_time;
@@ -177,7 +140,7 @@
/* process each task in the run queue now. Each task may be deleted
* since we only use the run queue's head. Note that any task can be
* woken up by any other task and it will be processed immediately
- * after as it will be queued on the run queue's head.
+ * after as it will be queued on the run queue's head !
*/
while ((t = rq) != NULL) {
int temp_time;
@@ -186,13 +149,14 @@
temp_time = t->process(t);
next_time = MINTIME(temp_time, next_time);
}
-
- /* maintain all proxies in a consistent state. This should quickly become a task */
+
+ /* maintain all proxies in a consistent state. This should quickly
+ * become a task because it becomes expensive when there are huge
+ * numbers of proxies. */
time2 = maintain_proxies();
return MINTIME(time2, next_time);
}
-
/*
* Local variables:
* c-indent-level: 8