linux-kernel - Re: [PATCH 4/4] perf, x86: Fix event scheduler to solve complex scheduling problems

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 for Android: free password hash cracker in your pocket

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

Message-ID: <1302943877.32491.9.camel@twins>
Date:	Sat, 16 Apr 2011 10:51:17 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Robert Richter <robert.richter@....com>
Cc:	Ingo Molnar <mingo@...e.hu>, Stephane Eranian <eranian@...gle.com>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 4/4] perf, x86: Fix event scheduler to solve complex
 scheduling problems

On Sat, 2011-04-16 at 02:27 +0200, Robert Richter wrote:
> The current x86 event scheduler fails to resolve scheduling problems
> of certain combinations of events and constraints. This happens esp.
> for events with complex constraints such as those of the AMD family
> 15h pmu. The scheduler does not find then an existing solution.
> Examples are:
> 
>         event code      counter         failure         possible
> solution
> 
> 1)      0x043           PMC[2:0]        0               1
>         0x02E           PMC[3,0]        3               0
>         0x003           PMC3            FAIL            3
> 
> 2)      0x02E           PMC[3,0]        0               3
>         0x043           PMC[2:0]        1               0
>         0x045           PMC[2:0]        2               1
>         0x046           PMC[2:0]        FAIL            2
> 
> Scheduling events on counters is a Hamiltonian path problem. To find a
> possible solution we must traverse all existing paths. This patch
> implements this.
> 
> We need to save all states of already walked paths. If we fail to
> schedule an event we now rollback the previous state and try to use
> another free counter until we have analysed all paths.
> 
> We might consider to later remove the constraint weight implementation
> completely, but I left this out as this is a much bigger and more
> risky change than this fix. 

Argh, crap. That's because AMD is now the first with overlapping
constraints. Be sure to let your hardware guys know that they went from
top to bottom om my appreciation list. AMD used to have no constraints
and now they have the absolute worst.

I'd really prefer not to do this for .39, and I'll have to sit down and
actually read this code. It looks like we went from O(n^2) to O(n!) or
somesuch, also not much of an improvement. I'll have to analyze the
solver to see what it does for 'simple' constraints set to see if it
will indeed be more expensive than the O(n^2) solver we had.

Also, I think this code could do with a tiny bit of comments ;-)
--
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/