perf, x86: Fixes for v2.6.39

Using ALTERNATIVE() when checking for X86_FEATURE_PERFCTR_CORE avoids an extra pointer chase and data cache hit.

Quoted 2 lines · Robert Richter

Using ALTERNATIVE() when checking for X86_FEATURE_PERFCTR_CORE avoids an extra pointer chase and data cache hit.

Is that really a performance critical path?

Seems more like unnecessary obfuscation to me.

Quoted 5 lines · Andi Kleen

Quoted 2 lines · Robert Richter

Using ALTERNATIVE() when checking for X86_FEATURE_PERFCTR_CORE avoids an extra pointer chase and data cache hit.

Quoted 3 lines

Is that really a performance critical path?

Seems more like unnecessary obfuscation to me.

We hotest path is in perf_pmu_disable(), which happens at least with every task switch when calling the event scheduler.

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.

Quoted 22 lines · Robert Richter

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.

Quoted 7 lines

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 ;-)

I'd also prefer if we first had actual testcases in 'perf test' for all these failures - it took an *awfully* long time to find these regressions (the event scheduler code has been committed for months), while with proper testcases it would only take a second to run 'perf test'.

Quoted 4 lines · Ingo Molnar

I'd also prefer if we first had actual testcases in 'perf test' for all these failures - it took an *awfully* long time to find these regressions (the event scheduler code has been committed for months), while with proper testcases it would only take a second to run 'perf test'.

These cases only exist on AMD F15, I don't think there's many people with such systems around.

Quoted 6 lines · Peter Zijlstra

Quoted 4 lines · Ingo Molnar

I'd also prefer if we first had actual testcases in 'perf test' for all these failures - it took an *awfully* long time to find these regressions (the event scheduler code has been committed for months), while with proper testcases it would only take a second to run 'perf test'.

Quoted 2 lines

These cases only exist on AMD F15, I don't think there's many people with such systems around.

Well, if the trend continues we'll have more twisted constraints and more bugs of this sort, so having a testsuite sure cannot hurt, right?

These cases only exist on AMD F15, I don't think there's many people with such systems around.

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 ;-)

Quoted 5 lines

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.

It wont be more expensive, if there is a solution. But if there is no one we walk all possible ways now which is something like O(n!).

Quoted 6 lines · Robert Richter

Quoted 5 lines

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.

Quoted 2 lines

It wont be more expensive, if there is a solution. But if there is no one we walk all possible ways now which is something like O(n!).

So with 6 counters it would be a loop of 720, with 8 counters a loop of 40320, with 10 counters a loop of 3628800 ... O(n!) is not fun.

Quoted 2 lines · Ingo Molnar

So with 6 counters it would be a loop of 720, with 8 counters a loop of 40320, with 10 counters a loop of 3628800 ... O(n!) is not fun.

Right, and we'll hit this case at least once when scheduling a over-committed system. Intel Sandy Bridge can have 8 counters per core + 3 fixed counters, giving an n=11 situation. You do _NOT_ want to have one 39916800 cycle loop before we determine the PMU isn't schedulable, that's simply unacceptable.

 $ perl counter-scheduling.pl | grep Num
 Number of counters:  2, loops:  10, redos:   4, ratio: 2.5
 Number of counters:  3, loops:  26, redos:   7, ratio: 3.7
 Number of counters:  4, loops:  53, redos:  11, ratio: 4.8

 Number of counters:  5, loops:  89, redos:  15, ratio: 5.9
 Number of counters:  6, loops: 134, redos:  19, ratio: 7.1
 Number of counters:  7, loops: 188, redos:  23, ratio: 8.2
 Number of counters:  8, loops: 251, redos:  27, ratio: 9.3
 Number of counters:  9, loops: 323, redos:  31, ratio: 10.4
 Number of counters: 10, loops: 404, redos:  35, ratio: 11.5
 Number of counters: 11, loops: 494, redos:  39, ratio: 12.7
 Number of counters: 12, loops: 593, redos:  43, ratio: 13.8

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.

Cc Stephane Eranian <[email protected]>

Signed-off-by Robert Richter <[email protected]>

---
 arch/x86/kernel/cpu/perf_event.c |   48 +++++++++++++++++++++++++++++++------

 1 files changed, 40 insertions(+), 8 deletions(-)

arch/x86/kernel/cpu/perf_event.c +40 -8

index 224a84f..887a500 100644
@@ -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

Quoted 6 lines · Robert Richter

       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.

Quoted 16 lines · Stephane Eranian

Quoted 6 lines · Robert Richter

       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

Quoted 6 lines

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?

No, I have to admit this one was taken out of my mind and I picked a wrong example for the special problem I was thinking about. The above works as you described because of the constraint's weights.

I don't have an example with existing constraints, but consider the following (theoretical) one:

counter: 3210           Failure:        Solution:

e1         xx             xo              ox
e2        xx             xo              ox
e3       x x            o x             o x
e4       x  x           x  F            x  o

The special with the above is that two events (e1 and e2) must be rescheduled to schedule e4. This means that swapping counters of only one already scheduled event is not sufficient. A counter of a third event must be freed, this counter is then taken by the second event.

Quoted 3 lines

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

An event set containing constraints with following conditions is problematic:

 (c1->weight <= c2->weight && (c1->cmask & c2->cmask != c1->cmask))

Basically this means both constraints do not overlap completly. You can't select then the correct counter without knowing the events with higher weights that will be scheduled later.

-Robert

--
Advanced Micro Devices, Inc.
Operating System Research Center

From cd70a579995fa7da885ec25db8ebe04ba4a0c30e Mon Sep 17 00:00:00 2001

arch/x86/kernel/cpu/perf_event.c static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign) · line 906

Quoted 3 lines · Robert Richter

arch/x86/kernel/cpu/perf_event.c +3 -0

+				if (!state)
+					/* no events to reschedule */
+					goto done;

Hm, that's 5 levels of indentation. Would it be possible to factor out the gist of the logic into a helper and such? My eyes would be much happier!

Quoted 9 lines · Ingo Molnar

arch/x86/kernel/cpu/perf_event.c static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign) · line 906

Quoted 3 lines · Robert Richter

arch/x86/kernel/cpu/perf_event.c +3 -0

+				if (!state)
+					/* no events to reschedule */
+					goto done;

Hm, that's 5 levels of indentation. Would it be possible to factor out the gist of the logic into a helper and such? My eyes would be much happier!

Hmm, I was thinking about this too, but it is not easy since we control also the loops with goto's and updates of the loop states. Refactoring out the inner block would mean to update state varables via pointers and to introduce return codes which contains control flow information. Don't think this will become easier.

We could probably merge both for-loops in one while-loop but also on costs of code readability.

arch/x86/kernel/cpu/perf_event.c +4 -2

+                               if (idx == X86_PMC_IDX_MAX)
                                        break;
+                               if (!__test_and_set_bit(idx, used_mask))
+                                       break;
+                               idx++;
                        }
 
-                       if (j == X86_PMC_IDX_MAX)
-                               break;

arch/x86/kernel/cpu/perf_event.c +15 -1

+                               idx++;
+                               goto redo;
+                       }
 
                        if (assign)
-                               assign[i] = j;
+                               assign[i] = idx;
+
                        num--;
+
+                       if (c->redo && state < SCHED_STATES_MAX) {
+                               /* store scheduler state: */
+                               sched_state[state].i = i;
+                               sched_state[state].w = w;
+                               sched_state[state].idx = idx;
+                               sched_state[state].num = num;
+                               bitmap_copy(sched_state[state].used, used_mask, n);
+                               state++;
+                       }
                }
        } 

arch/x86/kernel/cpu/perf_event.c static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign) · line 891

Quoted 9 lines

                        if (c->weight != w)
                                continue;

arch/x86/kernel/cpu/perf_event.c +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

I'd be mighty tempted to ignore that 80 column rule here ;-)

Quoted 10 lines · Peter Zijlstra

Quoted 9 lines

                        if (c->weight != w)
                                continue;

arch/x86/kernel/cpu/perf_event.c +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

Quoted 1 line

I'd be mighty tempted to ignore that 80 column rule here ;-)

Please put the body of the loop into a helper function, the function is large and there are countless col80 uglinesses in it!

Quoted 12 lines · Ingo Molnar

Quoted 10 lines · Peter Zijlstra

Quoted 9 lines

                        if (c->weight != w)
                                continue;

arch/x86/kernel/cpu/perf_event.c +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

Quoted 4 lines

Quoted 1 line

I'd be mighty tempted to ignore that 80 column rule here ;-)

Please put the body of the loop into a helper function, the function is large and there are countless col80 uglinesses in it!

I just tried that, its real ugly due to the amount of state you need to pass around.

Quoted 12 lines · Ingo Molnar

Quoted 10 lines · Peter Zijlstra

Quoted 9 lines

                        if (c->weight != w)
                                continue;

arch/x86/kernel/cpu/perf_event.c +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

Quoted 4 lines

Quoted 1 line

I'd be mighty tempted to ignore that 80 column rule here ;-)

Please put the body of the loop into a helper function, the function is large and there are countless col80 uglinesses in it!

I just tried that, its real ugly due to the amount of state you need to pass around.

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Ingo Molnar

Quoted 11 lines · Peter Zijlstra

arch/x86/kernel/cpu/perf_event.c static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign) · line 891

Quoted 9 lines

                        if (c->weight != w)
                                continue;

arch/x86/kernel/cpu/perf_event.c +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

I'd be mighty tempted to ignore that 80 column rule here ;-)

Quoted 5 lines

Quoted 2 lines

Please put the body of the loop into a helper function, the function is large and there are countless col80 uglinesses in it!

I just tried that, its real ugly due to the amount of state you need to pass around.

Does it help if you put that state into a helper structure?

Thanks,

Ingo

Quoted 20 lines · Ingo Molnar

Quoted 18 lines · Peter Zijlstra

Quoted 16 lines · Ingo Molnar

Quoted 11 lines · Peter Zijlstra

arch/x86/kernel/cpu/perf_event.c static int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign) · line 891

Quoted 9 lines

                        if (c->weight != w)
                                continue;

arch/x86/kernel/cpu/perf_event.c +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

I'd be mighty tempted to ignore that 80 column rule here ;-)

Please put the body of the loop into a helper function, the function is large and there are countless col80 uglinesses in it!

Quoted 4 lines

Quoted 2 lines

I just tried that, its real ugly due to the amount of state you need to pass around.

Does it help if you put that state into a helper structure?

Yes, this is what I have in mind too. We could iterate on such a state stucture instead of a couple of single variables. Storing and restoring the state will then just copying the structure.

Quoted 21 lines · Robert Richter

Quoted 20 lines · Ingo Molnar

Quoted 18 lines · Peter Zijlstra

Quoted 16 lines · Ingo Molnar

Quoted 11 lines · Peter Zijlstra

Review

Quoted 9 lines

                        if (c->weight != w)
                                continue;

(quoted diff) +4 -2

-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
-                               if (!test_bit(j, used_mask))
+                       /* 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);

I'd be mighty tempted to ignore that 80 column rule here ;-)

Please put the body of the loop into a helper function, the function is large and there are countless col80 uglinesses in it!

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

I just tried that, its real ugly due to the amount of state you need to pass around.

Does it help if you put that state into a helper structure?

Yes, this is what I have in mind too. We could iterate on such a state stucture instead of a couple of single variables. Storing and restoring the state will then just copying the structure.

Any word on this work? I just noticed we actually need this for Intel too, the fixed purpose events have overlapping but non-identical constraint masks.

Now we could optimize the Intel case by always iterating from the top down, but it won't cure all cases. For example, suppose one counter (that could be on a FP reg) previously got scheduled on a GP register and we take the fast-path, in that case we would still end up under-utilized.

Will try to post an updated version
next week. Ok?