This patch adds accounting to each runqueue to keep track of the
highest prio task queued on the run queue. We only care about
RT tasks, so if the run queue does not contain any active RT tasks
its priority will be considered MAX_RT_PRIO.

This information will be used for later patches.

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

---
 kernel/sched.c    |    7 +++++++
 kernel/sched_rt.c |   25 +++++++++++++++++++++++++
 2 files changed, 32 insertions(+)

Index: linux-test.git/kernel/sched.c
===================================================================
--- linux-test.git.orig/kernel/sched.c	2007-10-19 12:33:09.000000000 -0400
+++ linux-test.git/kernel/sched.c	2007-10-19 12:34:32.000000000 -0400
@@ -324,6 +324,8 @@ struct rq {
 	int push_cpu;
 	/* cpu of this runqueue: */
 	int cpu;
+	/* highest queued rt task prio */
+	int highest_prio;
 
 	struct task_struct *migration_thread;
 	struct list_head migration_queue;
@@ -972,6 +974,8 @@ static void activate_task(struct rq *rq,
 
 	enqueue_task(rq, p, wakeup);
 	inc_nr_running(p, rq);
+
+	rq_prio_add_task(rq, p);
 }
 
 /*
@@ -984,6 +988,8 @@ static void deactivate_task(struct rq *r
 
 	dequeue_task(rq, p, sleep);
 	dec_nr_running(p, rq);
+
+	rq_prio_remove_task(rq, p);
 }
 
 /**
@@ -6619,6 +6625,7 @@ void __init sched_init(void)
 		rq->cpu = i;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
+		rq->highest_prio = MAX_RT_PRIO;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 
Index: linux-test.git/kernel/sched_rt.c
===================================================================
--- linux-test.git.orig/kernel/sched_rt.c	2007-10-19 12:33:09.000000000 -0400
+++ linux-test.git/kernel/sched_rt.c	2007-10-19 12:33:23.000000000 -0400
@@ -110,6 +110,31 @@ static struct task_struct *pick_next_tas
 	return next;
 }
 
+#ifdef CONFIG_SMP
+static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
+{
+	if (unlikely(rt_task(p)) && p->prio < ...
[ message continues ]

Sorry, I forgot to test this on UP. Seems to be missing a 

#define rq_prio_remove_task(rq, p) do { } while(0)
#define rq_prio_add(rq, p) do { } while(0)

for the !CONFIG_SMP case.

Will fix.

-- Steve


-

[ message continues ]

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=

We are better off doing this in enqueue_task() or PI boosting will fail

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=

<=3D ?

We only need to recalc if the task being removed was the highest prio
(or higher, if that were possible but it shouldnt be).

I think this logic will technically work as-is because every task is
always >=3D highest in a properly accounted system, so you will just
simply recalc for every remove.  But I do like the optimization that you
were trying to add.

So for the paranoid:

				BUG_ON(p->prio < rq->highest_prio);
				if (p->prio =3D=3D rq->highest_prio) {
					/* recalc */
[ message continues ]

--

I thought about that too, but thought it was also too -rt base. But I


That's what I meant to do. (/me had another confusion between > and < for

That wasn't planned. I wanted to only recalc if the priority was >= the
the rq priority, which would have been. p->prio <= rq->highest_prio.
Yes, I thought to myself (that should never be higher!) but I was

I'll add that with a switch to WARN_ON.

-- Steve

-

[ message continues ]

again, could it be moved to 'struct rt_rq' ?
(so we want to cache it as we don't want to trash more per-cpu bytes
calling smth like


(just a few thoughts)

we call sched_find_first_bit() in pick_next_task_rt() in the case when
rt_nr_running != 0.

So if we can tolerate the 'latency' of updating the 'highest_prio' ==
the interval of time between deactivate_task() and pick_next_task() in
schedule() then rq_prio_remove_task() would just need to do a single
thing:

/* No more RT tasks: */
if (!rt_nr_running)
        highest_prio = MAX_RT_PRIO;

and then,

static struct task_struct *pick_next_task_rt(struct rq *rq)
{
        struct rt_prio_array *array = &rq->rt.active;
        struct task_struct *next;
        struct list_head *queue;
        int idx;

-        idx = sched_find_first_bit(array->bitmap);
+       rq->highest_prio = idx = sched_find_first_bit(array->bitmap);

[ ... ]

additionally, if we can tolerate the 'latency' (of updating
highest_prio) == the worst case scheduling latency, then
rq_prio_add_task() is not necessary at all.


-- 
Best regards,
Dmitry Adamushko
-

[ message continues ]

--



In my logging of test runs, having this 'latency' of highest_prio caused
missed migrations. I tried various things to do like what you said, but
they failed the rt-migrate-test program.

Seemed like the only place to modify highest_prio is from the queue and
dequeue.  Othrewise, my tests failed.

Thanks!

-- Steve

-

[ message continues ]