Re: [PATCH 4/4] perf, x86: Fix event scheduler to solve complexscheduling problems

From: Stephane Eranian
Date: Sat Apr 16 2011 - 11:53:10 EST

On Fri, Apr 15, 2011 at 5:27 PM, Robert Richter <robert.richter@xxxxxxx> 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
>
I am not sure I understand this failure case. If I recall
the scheduler looks at the weight of each event first:

weight
1) Â Â Â0x043 Â Â Â Â Â PMC[2:0] Â3
   Â0x02E      PMC[3,0]  2
   Â0x003      PMC3    Â1

Then, it schedules in increasing weight order. So it will
schedule weight 1, 2, 3. For weight 1, it will find counter3,
for weight 2, it will take counter0, for weight 3, it will
take counter 1 given 0 is already used.

Or am I reading your example the wrong way?

The fact that counter have overlapping constraints
should not matter. In fact this is what happens with
counters without constraints.

> 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.
>
> Cc: Stephane Eranian <eranian@xxxxxxxxxx>
> Signed-off-by: Robert Richter <robert.richter@xxxxxxx>
> ---
> Âarch/x86/kernel/cpu/perf_event.c | Â 48 +++++++++++++++++++++++++++++++------
> Â1 files changed, 40 insertions(+), 8 deletions(-)
>
> diff --git a/arch/x86/kernel/cpu/perf_event.c b/arch/x86/kernel/cpu/perf_event.c
> index 224a84f..887a500 100644
> --- a/arch/x86/kernel/cpu/perf_event.c
> +++ b/arch/x86/kernel/cpu/perf_event.c
> @@ -770,11 +770,19 @@ static inline int is_x86_event(struct perf_event *event)
> Â Â Â Âreturn event->pmu == &pmu;
> Â}
>
> +struct sched_log
> +{
> +    int   i;
> +    int   w;
> +    int   idx;
> +};
> +
> Âstatic int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
> Â{
> Â Â Â Âstruct event_constraint *c, *constraints[X86_PMC_IDX_MAX];
> Â Â Â Âunsigned long used_mask[BITS_TO_LONGS(X86_PMC_IDX_MAX)];
> - Â Â Â int i, j, w, wmax, num = 0;
> + Â Â Â struct sched_log sched_log[X86_PMC_IDX_MAX];
> + Â Â Â int i, idx, w, wmax, num = 0, scheduled = 0;
> Â Â Â Âstruct hw_perf_event *hwc;
>
> Â Â Â Âbitmap_zero(used_mask, X86_PMC_IDX_MAX);
> @@ -815,6 +823,7 @@ static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
> Â Â Â Â */
>
> Â Â Â Âbitmap_zero(used_mask, X86_PMC_IDX_MAX);
> + Â Â Â memset(&sched_log, 0, sizeof(sched_log));
>
> Â Â Â Â/*
> Â Â Â Â * weight = number of possible counters
> @@ -838,25 +847,48 @@ static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
> Â Â Â Âfor (w = 1, num = n; num && w <= wmax; w++) {
> Â Â Â Â Â Â Â Â/* for each event */
> Â Â Â Â Â Â Â Âfor (i = 0; num && i < n; i++) {
> + Â Â Â Â Â Â Â redo:
> Â Â Â Â Â Â Â Â Â Â Â Âc = constraints[i];
> Â Â Â Â Â Â Â Â Â Â Â Âhwc = &cpuc->event_list[i]->hw;
>
> Â Â Â Â Â Â Â Â Â Â Â Âif (c->weight != w)
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âcontinue;
>
> - Â Â Â Â Â Â Â Â Â Â Â for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (!test_bit(j, used_mask))
> + Â Â Â Â Â Â Â Â Â Â Â idx = sched_log[scheduled].idx;
> + Â Â Â Â Â Â Â Â Â Â Â /* for each bit in idxmsk starting from idx */
> + Â Â Â Â Â Â Â Â Â Â Â while (idx < X86_PMC_IDX_MAX) {
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â idx = find_next_bit(c->idxmsk, X86_PMC_IDX_MAX,
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â idx);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (idx == X86_PMC_IDX_MAX)
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â break;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (!__test_and_set_bit(idx, used_mask))
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âbreak;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â idx++;
> Â Â Â Â Â Â Â Â Â Â Â Â}
>
> - Â Â Â Â Â Â Â Â Â Â Â if (j == X86_PMC_IDX_MAX)
> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â break;
> -
> - Â Â Â Â Â Â Â Â Â Â Â __set_bit(j, used_mask);
> + Â Â Â Â Â Â Â Â Â Â Â if (idx >= X86_PMC_IDX_MAX) {
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* roll back and try next free counter */
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (!scheduled)
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* no free counters anymore */
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â break;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â sched_log[scheduled].idx = 0;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â scheduled--;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â num++;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â clear_bit(sched_log[scheduled].idx, used_mask);
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â i = sched_log[scheduled].i;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â w = sched_log[scheduled].w;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â sched_log[scheduled].idx++;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â goto redo;
> + Â Â Â Â Â Â Â Â Â Â Â }
>
> Â Â Â Â Â Â Â Â Â Â Â Âif (assign)
> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â assign[i] = j;
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â assign[i] = idx;
> +
> Â Â Â Â Â Â Â Â Â Â Â Ânum--;
> + Â Â Â Â Â Â Â Â Â Â Â sched_log[scheduled].i = i;
> + Â Â Â Â Â Â Â Â Â Â Â sched_log[scheduled].w = w;
> + Â Â Â Â Â Â Â Â Â Â Â sched_log[scheduled].idx = idx;
> + Â Â Â Â Â Â Â Â Â Â Â scheduled++;
> Â Â Â Â Â Â Â Â}
> Â Â Â Â}
> Âdone:
> --
> 1.7.3.4
>
>
>
N‹§²æìr¸›yúèšØb²X¬¶ÇvØ^–)Þ{.nÇ+‰·¥Š{±‘êçzX§¶›¡Ü}©ž²ÆzÚ&j:+v‰¨¾«‘êçzZ+€Ê+zf£¢·hšˆ§~†­†Ûiÿûàz¹®w¥¢¸?™¨è­Ú&¢)ßf”ù^jÇy§m…á@A«a¶Úÿ 0¶ìh®å’i