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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CABPqkBSc-o+ysZEVx72acE7+AY8fLR8sqFDedKBwh8H60Z77cQ@mail.gmail.com>
Date:	Mon, 14 Nov 2011 15:26:02 +0100
From:	Stephane Eranian <eranian@...gle.com>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Robert Richter <robert.richter@....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

Let's take Robert's example:
   c0 c1 c2
 e0 x     x
 e1    x  x
 e2 x  x

The nodes in the graph:

- S (starting point)
- T (the ending point)
- e0, e1, e2 (the events)
- c0, c1, c2 (the counters)

There is an edge from the source to all the events.
There is an edge from all the counters to the sync.
There is an edge between an event and a counter, if
it can count the event.

The capacity of any edge is 1.

The max flow algorithm returns the maximum number of
events that can be measured together. If max_flow ==
number of events, we maxed out.

To find the assignment, we simply need to inspect the
outgoing edges from events and use the only edge which
has a flow == 1.

If we list all the edges for the example above, we have:
S -> e0
S -> e1
S -> e2
e0 -> c0
e0 -> c2
e1 -> c1
e1 -> c2
e2 -> c0
e2 -> c1
c0 -> T
c1 -> T
c2 -> T

then we do max_flow(S, T), Here we find 3.

Given the capacity is either 0 or 1, I think we could use
bitmasks to describe the edges.

On Mon, Nov 14, 2011 at 3:12 PM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Mon, 2011-11-14 at 13:55 +0100, Stephane Eranian wrote:
>> I have been talking with co-workers experts in operational research
>> about our problem. They all pointed to me to the max flow algorithm from
>> Ford-Fulkerson (search for it on Wikipedia). I think it solves the complexity
>> and recursion problems. My understanding is that the complexity is also
>> more under control.
>
> How would you apply this algorithm to the problem at hand? I'm probably
> missing the obvious thing here, but if we want the flow to be the number
> of assigned counter then we end up with nodes being the various
> permutations of assignments or so, which isn't helpful since that'd be
> n! nodes.
>
>
>
--
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/