| 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
| ||
|
Date: Thu, 15 May 2014 13:52:22 +0200
From: Juri Lelli <juri.lelli@...il.com>
To: Peter Zijlstra <peterz@...radead.org>
Cc: Tejun Heo <tj@...nel.org>, Ingo Molnar <mingo@...hat.com>,
linux-kernel@...r.kernel.org, Johannes Weiner <hannes@...xchg.org>,
"Rafael J. Wysocki" <rjw@...ysocki.net>
Subject: Re: [REGRESSION] funny sched_domain build failure during resume
On Thu, 15 May 2014 10:51:56 +0200
Peter Zijlstra <peterz@...radead.org> wrote:
> On Thu, May 15, 2014 at 10:40:55AM +0200, Juri Lelli wrote:
> > Hi,
> >
> > > @@ -37,10 +38,7 @@ static inline int dl_time_before(u64 a, u64 b)
> > >
> > > static void cpudl_exchange(struct cpudl *cp, int a, int b)
> > > {
> > > - int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;
> > > -
> > > swap(cp->elements[a], cp->elements[b]);
> > > - swap(cp->cpu_to_idx[cpu_a], cp->cpu_to_idx[cpu_b]);
> > > }
> > >
> >
> > I think there is a problem here. Your patch "embeds" cpu_to_idx array
> > in elements array, but here the swap operates differently on the two.
>
> <snip>
>
> > Sorry for this long reply, but I had to convince also myself...
>
> Glad you explained it before I tried to untangle that code myself.
>
> > So, I think that having just one dynamic array is nicer and better, but
> > we still need to swap things separately. Something like (on top of
> > yours):
> >
> > diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> > index 60ad0af..10dc7ab 100644
> > --- a/kernel/sched/cpudeadline.c
> > +++ b/kernel/sched/cpudeadline.c
> > @@ -36,9 +36,31 @@ static inline int dl_time_before(u64 a, u64 b)
> > return (s64)(a - b) < 0;
> > }
> >
> > +static inline void swap_element(struct cpudl *cp, int a, int b)
> > +{
> > + int cpu_tmp = cp->elements[a].cpu;
> > + u64 dl_tmp = cp->elements[a].dl;
> > +
> > + cp->elements[a].cpu = cp->elements[b].cpu;
> > + cp->elements[a].dl = cp->elements[b].dl;
> > + cp->elements[b].cpu = cpu_tmp;
> > + cp->elements[b].dl = dl_tmp;
>
> You could've just written:
>
> swap(cp->elements[a].cpu, cp->elements[b].cpu);
> swap(cp->elements[a].dl , cp->elements[b].dl );
>
> The swap macro does the tmp var for you.
>
> > +}
> > +
> > +static inline void swap_idx(struct cpudl *cp, int a, int b)
> > +{
> > + int idx_tmp = cp->elements[a].idx;
> > +
> > + cp->elements[a].idx = cp->elements[b].idx;
> > + cp->elements[b].idx = idx_tmp;
>
> swap(cp->elements[a].idx, cp->elements[b].idx);
>
> > +}
> > +
> > static void cpudl_exchange(struct cpudl *cp, int a, int b)
> > {
> > - swap(cp->elements[a], cp->elements[b]);
> > + int cpu_a = cp->elements[a].cpu, cpu_b = cp->elements[b].cpu;
> > +
> > + swap_element(cp, a, b);
> > + swap_idx(cp, cpu_a, cpu_b);
>
> Or just skip the lot and put the 3 swap() stmts here.
>
Ah, yes, sure!
Maybe we could add in cpudeadline.c also a comment explaining a bit how
the thing works. Something along the line of cpupri.c:
/*
* kernel/sched/cpudeadline.c
*
* Global CPU deadline management
*
* Author: Juri Lelli <juri.lelli@...il.com>
*
* This code tracks the deadline of each CPU (i.e., the deadline of
* current on the CPU) so that global migration decisions are easy
* to calculate. Each CPU can be in a state as follows:
*
* (INVALID), WITH_DL_TASK(S)
*
* The system maintains this state with a max-heap implemented as
* a simple array. To efficiently handle updates on intermediate nodes
* the array can be thought as splitted in two parts, one that contains
* heap nodes, and the other that keeps track of where nodes reside in
* the first part. From kernel/sched/cpudeadline.h we conceptually
* have:
*
* struct cpudl_item {
* u64 dl;
* int cpu;
* -------------------
* int idx;
* }
*
* Moreover, we keep track of CPUs in the INVALID state with a cpumask
* (no need to use the array if some CPU is free).
*
* Let's clarify this with a simple example. Suppose at a certain
* instant of time we have this situation (4CPUs box):
*
* CPU 1
* DL 50
* / \
* / \
* CPU 2 CPU 0
* DL 30 DL 40
* /
* /
* CPU 3
* DL 25
*
* In this case the state is mantained as:
*
* elements[dl/cpu] | 50/1 | 30/2 | 40/0 | 25/3 |
* ^ ^ ^ ^
* | +-----|-+ |
* +---------+ | | |
* +--------|------+ | |
* elements[idx] | 2 | 0 | 1 | 3 |
*
* Operations on the heap (e.g., node updates) must thus handle
* the two parts of elements array separately, see cpudl_set()
* and cpudl_exchange() for details.
*
* 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; version 2
* of the License.
*/
Thanks,
- Juri
> > }
> >
> > static void cpudl_heapify(struct cpudl *cp, int idx)
> > ---
> >
> > But, I don't know if this is too ugly and we better go with two arrays
> > (or a better solution, as this is the fastest thing I could come up
> > with :)).
>
> Thanks for looking at it, and sorry for breaking it.
--
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/
Powered by blists - more mailing lists