perf_events: fix and improve x86 event scheduling

Major rewrite of the x86 event scheduling routine. The routine is shared between AMD and Intel.

The existing code had an issue with certain combinations of constraints. As Robert Richter @ AMD demonstrated on AMD Bulldozer:

e0 [3,0]
e1 [2:0]
e2 [2:0]
e3 [2:0]

With this list of events, the existing scheduling algorithm would never schedule e3. That's because it would always choose counter 0 for e0:
e0 -> 0
e1 -> 1
e2 -> 2
e3 -> X

Robert Richter proposed a fix to the algorithm which was based on tagging constraints that overlap. He was using rollbacks to simulate recursion.

We propose an alternate solution which is simpler, faster. This is a small modification to the existing algorithm. It adds some smart in how a counter is chosen for a given event. The first available counter is not systemtically selected. Instead, the

algorithm checks how the constraints between the events overlap. For each counter, it assigns a weight which is the number of events which it can count for the event set. For each event, the algorithm assigns the counter with the smallest weight first.

In the example above, the new algoritm assigns:

e0 -> 3
e1 -> 0
e2 -> 1
e3 -> 2

Because:
counter 0, weight = 4
counter 1, weight = 3
counter 2, weight = 3
counter 3, weight = 1

We maximize PMU usage and ensure all events are measured.

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

+int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
+{
+	struct event_constraint **c;
+	struct event_constraint *constraints[X86_PMC_IDX_MAX];
+	struct perf_event *events[X86_PMC_IDX_MAX];
+	unsigned long used_mask[BITS_TO_LONGS(X86_PMC_IDX_MAX)];
+	int i;
+	int num_c = 0, num_u = 0;
+	struct hw_perf_event *hwc;
+
+	/*
+	 * collect event constraints
+	 * separate constrained vs. unconstrained events
+	 *
+	 * map_idx = actual index in event_list and assign arrays
+	 *
+	 * we add constrained events from index 0 to n
+	 * we add unconstrained events from index n - 1 to 0
+	 * that way we save stack memory by not defining two arrays
+	 */
+	for (i = 0; i < n; i++) {
+		constraints[i] =
+		    x86_pmu.get_event_constraints(cpuc, cpuc->event_list[i]);
+		if (constraints[i] != &unconstrained) {
+			events[num_c] = cpuc->event_list[i];
+			events[num_c]->hw.map_idx = i;
+			num_c++;
+		} else {
+			events[n - num_u - 1] = cpuc->event_list[i];
+			events[n - num_u - 1]->hw.map_idx = i;
+			num_u++;
 		}
 	}
+	/*
+	 * fastpath: try to reuse previous assignments
+	 */
+	for (i = 0, c = constraints; i < n; i++, c++) {
+		hwc = &cpuc->event_list[i]->hw;
+
+		/* never assigned, must go to slow path */
+		if (hwc->idx == -1)
+			break;
+
+		/* constraint still honored */
+		if (!test_bit(hwc->idx, (*c)->idxmsk))
+			break;
+
+		/* counter not already used */
+		if (test_bit(hwc->idx, used_mask))
+			break;
+
+		__set_bit(hwc->idx, used_mask);
+		if (assign)
+			assign[i] = hwc->idx;
+	}
+	/* was able to reuse every counter, we're done */
+	if (i == n) {
+		num_u = num_c = 0;
+		goto done;
+	}
+
+	/*
+	 * begin slow path
+	 */
+	bitmap_zero(used_mask, X86_PMC_IDX_MAX);
+
+	/* schedule constrained events */
+	if (num_c)

done:

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

 	/*
 	 * scheduling failed or is just a simulation,
 	 * free resources if necessary
 	 */

/*

include/linux/perf_event.h +0 -0

index 1e9ebe5..2605244 100644

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

+                       /*
+                        * scan all possible counters for this event
+                        * but use the one with the smallest counter weight,
+                        * i.e., give a chance to other less constrained events
+                        */

Quoted 7 lines · Stephane Eranian

+                       /*
+                        * scan all possible counters for this event
+                        * but use the one with the smallest counter weight,
+                        * i.e., give a chance to other less constrained events
+                        */
                        for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {

Quoted 8 lines

+                               if (test_bit(j, used_mask))
+                                       continue; +
+                               if (wcnt[j] < min_wcnt) {
+                                       min_wcnt = wcnt[j];
+                                       wcnt_idx = j;
+                               }
+                       }

The problem with this is that it will typically hit the worst case for Intel fixed-purpose events since the fixed purpose counters have the highest counter index and their constraint masks are the heaviest in the system ensuring we hit the max loop count on the top loop.

Then again, with Robert's approach we have to mark all fixed purpose thingies as redo and we might hit some weird cases there as well, can't seem to get me brain straight on that case though.

But given we limit the number of events to that of counters, we do have O(c^3).

As for the map_idx, it's there to track the position of each event in the initial event list. We shuffle events between constrained and unconstrained. By stashing the map_idx in the hw_perf_event struct we avoid having to pass around yet another array.

Just throwing this out there (hasn't event been compiled etc..).

The idea is to try the fixed counters first so that we don't 'accidentally' fill a GP counter with something that could have lived on the fixed purpose one and then end up under utilizing the PMU that way.

It ought to solve the most common PMU programming fail on Intel thingies.

---
Index: linux-2.6/arch/x86/kernel/cpu/perf_event.c
===================================================================

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

@@ -558,14 +558,22 @@ int x86_schedule_events(struct cpu_hw_ev
                        if (c->weight != w)
                                continue;
 
-                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
+                       if (x86_pmu.num_counters_fixed) {
+                               j = X86_PMC_IDX_FIXED - 1;
+                               for_each_set_bit_cont(j, c->idxmsk, X86_PMC_IDX_MAX) {
+                                       if (!test_bit(k, used_mask))
+                                               goto assign;
+                               }
+                       }
+
+                       for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_FIXED) {
                                if (!test_bit(j, used_mask))
-                                       break;
+                                       goto assign;
                        }
 
-                       if (j == X86_PMC_IDX_MAX)
-                               break;
+                       break;
 
+assign:
                        __set_bit(j, used_mask);
 
                        if (assign)

Index: linux-2.6/include/linux/bitops.h
===================================================================

include/linux/bitops.h +0 -0

@@ -26,6 +26,12 @@ extern unsigned long __sw_hweight64(__u6
             (bit) < (size); \
             (bit) = find_next_bit((addr), (size), (bit) + 1))

Quoted 9 lines · Peter Zijlstra

Just throwing this out there (hasn't event been compiled etc..).

The idea is to try the fixed counters first so that we don't 'accidentally' fill a GP counter with something that could have lived on the fixed purpose one and then end up under utilizing the PMU that way.

It ought to solve the most common PMU programming fail on Intel thingies.

What are the configs for which you have failures on Intel?

I think I can improve my algorithm for fixed counters by treating them separately and trying fixed counters first any supported event.

Quoted 10 lines · Stephane Eranian

Quoted 9 lines · Peter Zijlstra

Just throwing this out there (hasn't event been compiled etc..).

The idea is to try the fixed counters first so that we don't 'accidentally' fill a GP counter with something that could have lived on the fixed purpose one and then end up under utilizing the PMU that way.

It ought to solve the most common PMU programming fail on Intel thingies.

Heh, just looked into doing exactly that here.

Quoted 2 lines

What are the configs for which you have failures on Intel?

Suppose you have 3 fixed event counters and 2 GP counters and 3 event. One can go to one of the fixed counters or any GP, 2 others can be only on GP. If the event that can go to fixed counter will be placed into GP counter then one of the remaining events will fail to be scheduled.

Quoted 11 lines · Gleb Natapov

Quoted 10 lines · Stephane Eranian

Quoted 9 lines · Peter Zijlstra

Just throwing this out there (hasn't event been compiled etc..).

The idea is to try the fixed counters first so that we don't 'accidentally' fill a GP counter with something that could have lived on the fixed purpose one and then end up under utilizing the PMU that way.

It ought to solve the most common PMU programming fail on Intel thingies.

Quoted 9 lines

Heh, just looked into doing exactly that here.

Quoted 2 lines

What are the configs for which you have failures on Intel?

Suppose you have 3 fixed event counters and 2 GP counters and 3 event. One can go to one of the fixed counters or any GP, 2 others can be only on GP. If the event that can go to fixed counter will be placed into GP counter then one of the remaining events will fail to be scheduled.

Yes and the current algorithm does the right thing.
e1 (1 fixed +2 GP) -> weight = 3
e2 (2 GP) -> weight = 2
e3 (2 GP) -> weight = 2

The current algorithm schedules the event from light to heavy weight. Thus, it schedules e2, e3 first on the GPs and then e1 necessarily ends up on the fixed counter.

Do you have a test case where this does not work on Intel?

Quoted 8 lines · Peter Zijlstra

Just throwing this out there (hasn't event been compiled etc..).

The idea is to try the fixed counters first so that we don't 'accidentally' fill a GP counter with something that could have lived on the fixed purpose one and then end up under utilizing the PMU that way.

It ought to solve the most common PMU programming fail on Intel thingies.

What are the configs for which you have failures on Intel?

Major rewrite of the x86 event scheduling routine. The routine is shared between AMD and Intel.

The existing code had an issue with certain combinations of constraints. As Robert Richter @ AMD demonstrated on AMD Bulldozer:

e0 [3,0]
e1 [2:0]
e2 [2:0]
e3 [2:0]

With this list of events, the existing scheduling algorithm would never schedule e3. That's because it would always choose counter 0 for e0:
e0 -> 0
e1 -> 1
e2 -> 2
e3 -> X

Robert Richter proposed a fix to the algorithm which was based on tagging constraints that overlap. He was using rollbacks to simulate recursion.

We propose an alternate solution which is simpler, faster. This is a small modification to the existing algorithm. It adds some smart in how a counter is chosen for a given event. The first

available counter is not systemtically selected. Instead, the algorithm checks how the constraints between the events overlap. For each counter, it assigns a weight which is the number of events which it can count for the event set. For each event, the algorithm assigns the counter with the smallest weight first.

In the example above, the new algoritm assigns:
e0 -> 3
e1 -> 0
e2 -> 1
e3 -> 2

Because:
counter 0, weight = 4
counter 1, weight = 3
counter 2, weight = 3
counter 3, weight = 1

We maximize PMU usage and ensure all events are measured.

The patch also restructures the code to separate scheduling of constrained vs. unconstrained events. An unconstrained event is one that can be programmed into any of the generic counters. For those, we now use the simplest algorihtm possible: use next free counter. There is now a fast path which is beneficial on processors such as AMD64 Fam10h.

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

@@ -553,42 +530,179 @@ int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
 	if (x86_pmu.num_counters_fixed)
 		wmax++;
 
-	for (w = 1, num = n; num && w <= wmax; w++) {
-		/* for each event */
-		for (i = 0; num && i < n; i++) {
-			c = constraints[i];
-			hwc = &cpuc->event_list[i]->hw;
+	/*
+	 * assign from most constrained to least constrained
+	 */
+	for (w = 1, num = num_c; num && w <= wmax; w++) {

include/linux/perf_event.h +0 -0

 		};
 		struct { /* software */
 			struct hrtimer	hrtimer;

But this algorithm does not work for all cases and does not solve the problem in general.

Quoted 2 lines · Robert Richter

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!).

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.

include/linux/bitops.h +0 -1

@@ -22,8 +22,14 @@ extern unsigned long __sw_hweight64(__u64 w);
 #include <asm/bitops.h>
 
 #define for_each_set_bit(bit, addr, size) \
-       for ((bit) = find_first_bit((addr), (size)); \

Quoted 5 lines · Robert Richter

include/linux/bitops.h +0 -1

@@ -22,8 +22,14 @@ extern unsigned long __sw_hweight64(__u64 w);
 #include <asm/bitops.h>
 
 #define for_each_set_bit(bit, addr, size) \
-       for ((bit) = find_first_bit((addr), (size)); \

include/linux/bitops.h extern unsigned long __sw_hweight64(__u64 w); · line 33

Quoted 10 lines

include/linux/bitops.h +8 -1

-            (bit) < (size); \
+       for ((bit) = find_first_bit((addr), (size));            \
+            (bit) < (size);                                    \
+            (bit) = find_next_bit((addr), (size), (bit) + 1))
+
+/* same as for_each_set_bit() but use bit as value to start with */
+#define for_each_set_bit_cont(bit, addr, size) \
+       for ((bit) = find_next_bit((addr), (size), (bit));      \
+            (bit) < (size);                                    \
             (bit) = find_next_bit((addr), (size), (bit) + 1)) 

So my version has the +1 for the first as well, this is from the assumption that the bit passed in has been dealt with and should not be the first. ie. cont _after_ @bit instead of cont _at_ @bit.

This seems consistent with the list_*_continue primitives as well, which will start with the element after (or before for _reverse) the given position.

Thoughts?

Quoted 21 lines · Stephane Eranian

Major rewrite of the x86 event scheduling routine. The routine is shared between AMD and Intel.

The existing code had an issue with certain combinations of constraints. As Robert Richter @ AMD demonstrated on AMD Bulldozer:

e0 [3,0]
e1 [2:0]
e2 [2:0]
e3 [2:0]

With this list of events, the existing scheduling algorithm would never schedule e3. That's because it would always choose counter 0 for e0:
  e0 -> 0
  e1 -> 1
  e2 -> 2
  e3 -> X

Quoted 7 lines

Robert Richter proposed a fix to the algorithm which was based on tagging constraints that overlap. He was using rollbacks to simulate recursion.

We propose an alternate solution which is simpler, faster. This is a small modification to the existing algorithm. It adds some smart in how a counter is chosen for a given event. The first

Posting a link to my patch set for reference:

 https://lkml.org/lkml/2011/9/10/51

What are the reasons to your alternate solution? Is it recursion, code complexity, or a use case it does not fit in? I see recursion as the main concern with my patch set, but its impact is known and limited. Anyway, a algorithm without recursion would be generally better.

Quoted 5 lines

available counter is not systemtically selected. Instead, the algorithm checks how the constraints between the events overlap. For each counter, it assigns a weight which is the number of events which it can count for the event set. For each event, the algorithm assigns the counter with the smallest weight first.

But this algorithm does not work for all cases and does not solve the problem in general. Your idea to have weights for counters might be the right approach.

E.g. the algorithm fails with (all weights are the same):

   c0 c1 c2
 e0 x     x
 e1    x  x
 e2 x  x

... leading to:

 e0 -> c0
 e1 -> C1
 e3 -> X

You basically have to recalculate the weights after you had assigned a counter.

But even if we do this, I am still not sure if that would cover all cases.

Quoted 13 lines

In the example above, the new algoritm assigns:
  e0 -> 3
  e1 -> 0
  e2 -> 1
  e3 -> 2

Because:
  counter 0, weight = 4
  counter 1, weight = 3
  counter 2, weight = 3
  counter 3, weight = 1

Quoted 8 lines

We maximize PMU usage and ensure all events are measured.

The patch also restructures the code to separate scheduling of constrained vs. unconstrained events. An unconstrained event is one that can be programmed into any of the generic counters. For those, we now use the simplest algorihtm possible: use next free counter. There is now a fast path which is beneficial on processors such as AMD64 Fam10h.

I don't see the need for a differentiation between constraint and unconstraint events. If loops are optimized in the constraint path there is not much overhead anymore. This could be done by specifying min and max limits for ranges. Special cases (unconstraint events, fixed counter, etc.) make the code more complex. I don't think a good algorithm will need this.

Quoted 13 lines

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

@@ -553,42 +530,179 @@ int x86_schedule_events(struct cpu_hw_events *cpuc, int n, int *assign)
       if (x86_pmu.num_counters_fixed)
               wmax++;
 
-     for (w = 1, num = n; num && w <= wmax; w++) {
-             /* for each event */
-             for (i = 0; num && i < n; i++) {
-                     c = constraints[i];
-                     hwc = &cpuc->event_list[i]->hw;
+     /*
+      * assign from most constrained to least constrained
+      */
+     for (w = 1, num = num_c; num && w <= wmax; w++) {

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

Quoted 10 lines

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

+             /* for each constrained event */
+             for (i = 0, e = c_events; i < num_c; i++, e++) {
+
+                     map_idx = (*e)->hw.map_idx;
+                     c = constraints[map_idx];
 
                       if (c->weight != w)
                               continue;
 
+                     min_wcnt = INT_MAX;

Should be X86_PMC_IDX_MAX.

include/linux/perf_event.h struct hw_perf_event { · line 567

Quoted 9 lines

include/linux/perf_event.h +1 -0

index 1e9ebe5..2605244 100644
@@ -564,6 +564,7 @@ struct hw_perf_event {
                       int             idx;
                       int             last_cpu;
                       struct hw_perf_event_extra extra_reg;
+                     int             map_idx;

This is not the right place. It is for all architectures but actually locally only used. A local array in x86_schedule_events() would work too.

-Robert

Quoted 4 lines

include/linux/perf_event.h +0 -0

               };

              struct { /* software */
                      struct hrtimer  hrtimer;

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

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.

Quoted 5 lines · Stephane Eranian

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.

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.

Quoted 6 lines · Stephane Eranian

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.

Ah indeed.

So that gives:

 E = e+e*c+c ~= O(c^2); since e<=c
 V = 2+e+c   ~= O(c)

Then going by:

http://en.wikipedia.org/wiki/Maximum_flow_problem

we have to stay away from Edmonds-Karp.

Ford-Fulkerson would end up being O(E * c) = O(c^3), since max |f| is c. Which is pretty much identical to all these O(V^2 E) = O(c^3) as well.

Dinitz blocking flow with dynamic trees looks more interesting at O(c^2 log(c)). Push relabel with dynamic trees looks to be best at O(c^2), since V^2/E ends up being c^2/c^2 = 1.

Creating the graph itself will be O(c^2) as well, due to E.

Quoted 28 lines · Peter Zijlstra

Quoted 6 lines · Stephane Eranian

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.

Ah indeed.

So that gives:

E = e+e*c+c ~= O(c^2); since e<=c
V = 2+e+c ~= O(c)

Then going by:

http://en.wikipedia.org/wiki/Maximum_flow_problem

we have to stay away from Edmonds-Karp.

Ford-Fulkerson would end up being O(E * c) = O(c^3), since max |f| is c. Which is pretty much identical to all these O(V^2 E) = O(c^3) as well.

Dinitz blocking flow with dynamic trees looks more interesting at O(c^2 log(c)). Push relabel with dynamic trees looks to be best at O(c^2), since V^2/E ends up being c^2/c^2 = 1.

Quoted 2 lines

Creating the graph itself will be O(c^2) as well, due to E.

I think we are in the special case of a bi-partite graph with unit capacities, thus the complexity can be reduced even more.

See Special Cases in http://en.wikipedia.org/wiki/Dinic%27s_algorithm

Quoted 29 lines · Stephane Eranian

Quoted 28 lines · Peter Zijlstra

Quoted 6 lines · Stephane Eranian

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.

Ah indeed.

So that gives:

 E = e+e*c+c ~= O(c^2); since e<=c
 V = 2+e+c   ~= O(c)

Then going by:

http://en.wikipedia.org/wiki/Maximum_flow_problem

we have to stay away from Edmonds-Karp.

Ford-Fulkerson would end up being O(E * c) = O(c^3), since max |f| is c. Which is pretty much identical to all these O(V^2 E) = O(c^3) as well.

Dinitz blocking flow with dynamic trees looks more interesting at O(c^2 log(c)). Push relabel with dynamic trees looks to be best at O(c^2), since V^2/E ends up being c^2/c^2 = 1.

Quoted 6 lines

Quoted 2 lines

Creating the graph itself will be O(c^2) as well, due to E.

I think we are in the special case of a bi-partite graph with unit capacities, thus the complexity can be reduced even more.

See Special Cases in http://en.wikipedia.org/wiki/Dinic%27s_algorithm

Yeah, I found that, but that still reduces to O(c^2.5) which is over the O(c^2) of Push relabel with dynamic trees.

I haven't managed to wrap my head around this stuff well enough to even start to have an idea if this constraint (bi-partite and unit capacities) will have any considerable effect on the other algorithms.

Also, we don't need an exhaustive max flow solution, any flow that's high enough to fit the required capacity will do, this too could possibly be used to lower the (average) complexity bound.

I would really really like it to not average to O(n^3), that's just silly expensive.

Also, do you have any objections to me merging Roberts stuff (provided it passes review etc.) while you poke at alternative solutions? We can always replace the stuff again if we find anything that works better.

Also, we don't need an exhaustive max flow solution, any flow that's high enough to fit the required capacity will do, this too could possibly be used to lower the (average) complexity bound.

Quoted 4 lines · Peter Zijlstra

Also, we don't need an exhaustive max flow solution, any flow that's high enough to fit the required capacity will do, this too could possibly be used to lower the (average) complexity bound.

I think that for the typically very dense graphs this in particular could be very helpful in keeping the actual runtime low. For a fully connected e*c it really doesn't matter how you program things, all flows will have the same max and iterating them all is just wasting time.

We just need to figure out which of the many different algorithms are best on average for our particular constraint sets.