linux-kernel - Re: [patch 2/8] track highest prio queued on runqueue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <b647ffbd0710201114g7fb37652r1e28dddbc7e879f4@mail.gmail.com>
Date:	Sat, 20 Oct 2007 20:14:29 +0200
From:	"Dmitry Adamushko" <dmitry.adamushko@...il.com>
To:	"Steven Rostedt" <rostedt@...dmis.org>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	RT <linux-rt-users@...r.kernel.org>,
	"Linus Torvalds" <torvalds@...ux-foundation.org>,
	"Andrew Morton" <akpm@...ux-foundation.org>,
	"Ingo Molnar" <mingo@...e.hu>,
	"Thomas Gleixner" <tglx@...utronix.de>,
	"Gregory Haskins" <ghaskins@...ell.com>,
	"Peter Zijlstra" <a.p.zijlstra@...llo.nl>
Subject: Re: [patch 2/8] track highest prio queued on runqueue

On 19/10/2007, Steven Rostedt <rostedt@...dmis.org> wrote:
> [ ... ]
>
===================================================================
> --- 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;

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
if (!rt_nr_running) sched_find_first_bit() from other CPUs)


> @@ -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);
>  }

{enqueue,dequeue}_task_rt() would be more appropriate places.


> +static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
> +{
> +       if (unlikely(rt_task(p)) && p->prio < rq->highest_prio)
> +               rq->highest_prio = p->prio;
> +}
> +
> +static inline void rq_prio_remove_task(struct rq *rq, struct task_struct *p)
> +{
> +       struct rt_prio_array *array;
> +
> +       if (unlikely(rt_task(p))) {
> +               if (rq->rt_nr_running) {
> +                       if (p->prio >= rq->highest_prio) {
> +                               /* recalculate */
> +                               array = &rq->rt.active;
> +                               rq->highest_prio =
> +                                       sched_find_first_bit(array->bitmap);
> +                       } /* otherwise leave rq->highest prio alone */
> +               } else
> +                       rq->highest_prio = MAX_RT_PRIO;
> +       }
> +}
> +#endif /* CONFIG_SMP */
> +

(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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/