linux-kernel - Re: [PATCH] perf_events: fix and improve x86 event scheduling

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]

Date:	Thu, 10 Nov 2011 19:52:47 +0100
From:	Peter Zijlstra <peterz@...radead.org>
To:	Robert Richter <robert.richter@....com>
Cc:	Stephane Eranian <eranian@...gle.com>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"mingo@...e.hu" <mingo@...e.hu>,
	"ming.m.lin@...el.com" <ming.m.lin@...el.com>,
	"ak@...ux.intel.com" <ak@...ux.intel.com>
Subject: Re: [PATCH] perf_events: fix and improve x86 event scheduling

On Thu, 2011-11-10 at 19:41 +0100, Peter Zijlstra wrote:
> On Thu, 2011-11-10 at 19:03 +0100, Robert Richter wrote:
> > But this algorithm does not work for all cases and does not solve the
> > problem in general. 
> 
> Yeah, the problem in general is O(n!) no O(n^3) algorithm can compute
> the optimal solution for n>3 or so.
> 
> I think the goal is to keep the 'normal' case O(n^2) but try and suck
> less for the corner cases without degenerating into a full blown O(n!).
> 
> So I think we want an amortized O(n^2) with an upper bound well below
> O(n!).

I don't think its reasonable to require a perfect solver for the generic
problem since O(n!) is well outside sanity.

Practically though, the most challenging problem is the AMD F15 thing,
since those constraints are quite specific it might just be possible to
construct an algorithm that finds optimal solutions well below O(n!) for
that particular constraint set.

IIRC, Robert's proposal limits the rewind stack to 1, which, if my mind
didn't completely stop working, should end up being something like
O(n^3). Now I don't know if Robert's thing is perfect for AMD F15 or if
there's still some odd fail cases, but since he's from AMD I suspect its
good enough in practice.

In fact, I almost merged his code, my only complaint was a lack of
comments and having had to spend several hours to fully understand the
thing a few months ago, I felt it really could use some since I didn't
want to have to spend that amount of effort every time I'd have to look
at the thing.

--
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/