[BUG] scheduler: fix improper handling of duplicates __task_queue()
The top of a duplicate tree is not where bit == -1 but at the most
negative bit. This was causing tasks to be queued in reverse order
within duplicates. While this is not dramatic, it's incorrect and
might lead to longer than expected duplicate depths under some
circumstances.
diff --git a/include/proto/task.h b/include/proto/task.h
index 9d90b17..86a3c3d 100644
--- a/include/proto/task.h
+++ b/include/proto/task.h
@@ -26,6 +26,7 @@
#include <sys/time.h>
#include <common/config.h>
+#include <common/eb32tree.h>
#include <common/memory.h>
#include <common/mini-clist.h>
#include <common/standard.h>
@@ -80,7 +81,7 @@
extern unsigned int run_queue; /* run queue size */
extern unsigned int niced_tasks; /* number of niced tasks in the run queue */
extern struct pool_head *pool2_task;
-extern struct task *last_timer; /* optimization: last queued timer */
+extern struct eb32_node *last_timer; /* optimization: last queued timer */
/* return 0 if task is in run queue, otherwise non-zero */
static inline int task_in_rq(struct task *t)
@@ -113,7 +114,7 @@
static inline struct task *__task_unlink_wq(struct task *t)
{
eb32_delete(&t->wq);
- if (last_timer == t)
+ if (last_timer == &t->wq)
last_timer = NULL;
return t;
}
diff --git a/src/task.c b/src/task.c
index b46420a..17d825e 100644
--- a/src/task.c
+++ b/src/task.c
@@ -27,7 +27,7 @@
unsigned int run_queue = 0;
unsigned int niced_tasks = 0; /* number of niced tasks in the run queue */
-struct task *last_timer = NULL; /* optimization: last queued timer */
+struct eb32_node *last_timer = NULL; /* optimization: last queued timer */
static struct eb_root timers; /* sorted timers tree */
static struct eb_root rqueue; /* tree constituting the run queue */
@@ -91,19 +91,22 @@
#endif
if (likely(last_timer &&
- last_timer->wq.key == task->wq.key &&
- last_timer->wq.node.bit == -1 &&
- last_timer->wq.node.node_p)) {
+ last_timer->node.bit < 0 &&
+ last_timer->key == task->wq.key &&
+ last_timer->node.node_p)) {
/* Most often, last queued timer has the same expiration date, so
* if it's not queued at the root, let's queue a dup directly there.
- * Note that we can only use dups at the dup tree's root (bit==-1).
+ * Note that we can only use dups at the dup tree's root (most
+ * negative bit).
*/
- eb_insert_dup(&last_timer->wq.node, &task->wq.node);
+ eb_insert_dup(&last_timer->node, &task->wq.node);
+ if (task->wq.node.bit < last_timer->node.bit)
+ last_timer = &task->wq;
return;
}
eb32_insert(&timers, &task->wq);
- if (task->wq.node.bit == -1)
- last_timer = task; /* we only want a dup tree's root */
+ if (!last_timer || (task->wq.node.bit < last_timer->node.bit))
+ last_timer = &task->wq;
return;
}