perf: Various event scheduling improvements
cover perf: Various event scheduling improvements
Hi,
These patches bring (I hope) a bit more scalability and fairness to the perf events scheduling.
But this is only an introduction as there is still some work to do, like ensuring all pinned events have been scheduled before flexible ones (for now we schedule in order cpu pinned, cpu flexible, task pinned, task flexible), among other improvements.
Frederic Weisbecker (6):
perf/core: Split context's event group list into pinned and non-pinned lists
list: Introduce list_rotate_left()
perf: Round robin groups of events using list_rotate_left()
perf: Export software-only event group characteristic as a flag
perf: Don't rotate pinned groups
perf: Increase round-robin fairness of flexible events
include/linux/list.h | 14 +++ include/linux/perf_event.h | 8 +- kernel/perf_event.c | 262 +++++++++++++++++++++++++++----------------- 3 files changed, 184 insertions(+), 100 deletions(-)
PATCH v2 1/6 perf/core: Split context's event group list into pinned and non-pinned lists
Split-up struct perf_event_context::group_list into pinned_groups and flexible_groups (non-pinned).
This first appears to be useless as it duplicates various loops around the group list handlings.
But it scales better in the fast-path in perf_sched_in(). We don't anymore iterate twice through the entire list to separate pinned and non-pinned scheduling. Instead we interate through two distinct lists.
The another desired effect is that it makes easier to define distinct scheduling rules on both.
Changes in v2:
- Respectively rename pinned_grp_list and volatile_grp_list into pinned_groups and flexible_groups as per Ingo suggestion.
- Various cleanups
--- include/linux/perf_event.h | 3 +- kernel/perf_event.c | 227 +++++++++++++++++++++++++++++--------------- 2 files changed, 153 insertions(+), 77 deletions(-)
include/linux/perf_event.h +2 -1
@@ -683,7 +683,8 @@ struct perf_event_context {*/ struct mutex mutex; -struct list_head group_list; +struct list_head pinned_groups; +struct list_head flexible_groups;struct list_head event_list;int nr_events;int nr_active;
kernel/perf_event.c +151 -76
350 lines not on this page · raw message
Signature · 1 line
1.6.2.3
PATCH 2/6 list: Introduce list_rotate_left()
In reply to Frederic WeisbeckerBring a new list_rotate_left() helper that rotates a list to the left. This is useful for codes that need to round roubin elements which queue priority increases from tail to head.
--- include/linux/list.h | 14 ++++++++++++++ 1 files changed, 14 insertions(+), 0 deletions(-)
include/linux/list.h +14 -0
@@ -206,6 +206,20 @@ static inline int list_empty_careful(const struct list_head *head) }/** +* list_rotate_left - rotate the list to the left +* @head: the head of the list +*/ +static inline void list_rotate_left (struct list_head *head) +{ +struct list_head *first; + +if (!list_empty (head)) { + first = head->next; +list_move_tail (first, head); + } +} + +/** * list_is_singular - tests whether a list has just one entry. * @head: the list to test. */
Signature · 1 line
1.6.2.3
PATCH 3/6 perf: Round robin groups of events using list_rotate_left()
In reply to Frederic WeisbeckerThis is more proper that doing it through a list_for_each_entry() that breaks after the first entry.
--- kernel/perf_event.c | 13 +++---------- 1 files changed, 3 insertions(+), 10 deletions(-)
kernel/perf_event.c +3 -10
@@ -1454,8 +1454,6 @@ static void perf_ctx_adjust_freq(struct perf_event_context *ctx)*/ static void rotate_ctx (struct perf_event_context *ctx) { -struct perf_event *event; -if (!ctx->nr_events)return ;
@@ -1464,15 +1462,10 @@ static void rotate_ctx(struct perf_event_context *ctx)* Rotate the first entry last (works just fine for group events too): */ perf_disable (); -list_for_each_entry (event, &ctx->pinned_groups, group_entry) { -list_move_tail (&event->group_entry, &ctx->pinned_groups); -break ; - } -list_for_each_entry (event, &ctx->flexible_groups, group_entry) { -list_move_tail (&event->group_entry, &ctx->flexible_groups); -break ; - } +list_rotate_left (&ctx->pinned_groups); +list_rotate_left (&ctx->flexible_groups); +perf_enable ();raw_spin_unlock (&ctx->lock);
Signature · 1 line
1.6.2.3
Peter Zijlstra
maintainerRe: [PATCH 3/6] perf: Round robin groups of events using list_rotate_left()
kernel/perf_event.c static void rotate_ctx(struct perf_event_context *ctx) · line 1467
Quoted 11 lines · Frederic Weisbecker
This is more proper that doing it through a
list_for_each_entry()that breaks after the first entry.Signed-off-by Frederic Weisbecker <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Arnaldo Carvalho de Melo <[email protected]>Cc Paul Mackerras <[email protected]>---
kernel/perf_event.c +2
-0+list_rotate_left (&ctx->pinned_groups); +list_rotate_left (&ctx->flexible_groups);
Just wondering, pinned events were supposed to be on the pmu at all times, right?
Re: [PATCH 3/6] perf: Round robin groups of events using list_rotate_left()
Quoted 10 lines · Peter Zijlstra
Quoted 8 lines · Frederic Weisbecker
This is more proper that doing it through a
list_for_each_entry()that breaks after the first entry.Signed-off-by Frederic Weisbecker <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Arnaldo Carvalho de Melo <[email protected]>Cc Paul Mackerras <[email protected]>---
Quoted 5 lines
kernel/perf_event.c static void rotate_ctx(struct perf_event_context *ctx) · line 1467
Quoted 2 lines
kernel/perf_event.c +2
-0+list_rotate_left (&ctx->pinned_groups); +list_rotate_left (&ctx->flexible_groups);Just wondering, pinned events were supposed to be on the pmu at all times, right?
Yeah, but the previous version that was using a global list rotated the whole. So, somehow to keep the same bahaviour, I also rotate the pinned group, even if it makes no sense :-)
But there is a subsequent patch in the same set that removes the rotating of pinned groups.
Peter Zijlstra
maintainerRe: [PATCH 3/6] perf: Round robin groups of events using list_rotate_left()
Quoted 3 lines · Frederic Weisbecker
But there is a subsequent patch in the same set
that removes the rotating of pinned groups.
ok, let me read on ;-)
PATCH 4/6 perf: Export software-only event group characteristic as a flag
In reply to Frederic WeisbeckerBefore scheduling an event group, we first check if a group can go on. We first check if the group is made of software only events first, in which case it is enough to know if the group can be scheduled in.
For that purpose, we iterate through the whole group, which is wasteful as we could do this check when we add/delete an event to a group.
So we create a group_flags field in perf event that can host characteristics from a group of events, starting with a first PERF_GROUP_SOFTWARE flag that reduces the check on the fast path.
--- include/linux/perf_event.h | 5 +++++ kernel/perf_event.c | 30 +++++++++++------------------- 2 files changed, 16 insertions(+), 19 deletions(-)
include/linux/perf_event.h +5 -0
@@ -565,6 +565,10 @@ typedef void (*perf_overflow_handler_t)(struct perf_event *, int, struct perf_sample_data *, struct pt_regs *regs); +enum perf_group_flag { +PERF_GROUP_SOFTWARE =0x1 , +}; +/** * struct perf_event - performance event kernel representation: */
@@ -574,6 +578,7 @@ struct perf_event {struct list_head event_entry;struct list_head sibling_list;int nr_siblings; +int group_flags;struct perf_event *group_leader;struct perf_event *output;const struct pmu *pmu;
kernel/perf_event.c +11 -19
@@ -315,9 +315,16 @@ list_add_event(struct perf_event *event, struct perf_event_context *ctx)if (group_leader == event) {struct list_head *list; +if (is_software_event (event)) + event->group_flags |=PERF_GROUP_SOFTWARE ; + list =ctx_group_list (event, ctx);list_add_tail (&event->group_entry, list); }else { +if (group_leader->group_flags &PERF_GROUP_SOFTWARE && + !is_software_event (event)) + group_leader->group_flags &= ~PERF_GROUP_SOFTWARE ; +list_add_tail (&event->group_entry, &group_leader->sibling_list); group_leader->nr_siblings++; }
@@ -372,6 +379,9 @@ list_del_event(struct perf_event *event, struct perf_event_context *ctx) list =ctx_group_list (event, ctx);list_move_tail (&sibling->group_entry, list); sibling->group_leader = sibling; + +/* Inherit group flags from the previous leader */ + sibling->group_flags = event->group_flags; } }
@@ -700,24 +710,6 @@ group_error: }/* -* Return 1 for a group consisting entirely of software events, -* 0 if the group contains any hardware events. -*/ -static int is_software_only_group (struct perf_event *leader) -{ -struct perf_event *event; - -if (!is_software_event (leader)) -return 0 ; - -list_for_each_entry (event, &leader->sibling_list, group_entry) -if (!is_software_event (event)) -return 0 ; - -return 1 ; -} - -/* * Work out whether we can put this event group on the CPU now. */ static int group_can_go_on(struct perf_event *event,
@@ -727,7 +719,7 @@ static int group_can_go_on(struct perf_event *event,/* * Groups consisting entirely of software events can always go on. */ -if (is_software_only_group (event)) +if (event->group_flags &PERF_GROUP_SOFTWARE )return 1 ;/* * If an exclusive group is already on, no other hardware
Signature · 1 line
1.6.2.3
PATCH 5/6 perf: Don't rotate pinned groups
In reply to Frederic WeisbeckerWe round-robin pinned groups, which means we make them behaving just like non-pinned groups. Currently, and in practice, the almost only difference between pinned and non-pinned events is that the formers are scheduled before the latters. And the latters also stop scheduling non-software-only groups once one couldn't make it.
Anyway, pinned groups don't need to be round-robined because if a pinned group can't be scheduled, it is going to be put in an error state, following the pinned logic: it is always or never scheduled in a context.
--- kernel/perf_event.c | 3 +-- 1 files changed, 1 insertions(+), 2 deletions(-)
kernel/perf_event.c +1 -2
@@ -1451,11 +1451,10 @@ static void rotate_ctx(struct perf_event_context *ctx)raw_spin_lock (&ctx->lock);/* -* Rotate the first entry last (works just fine for group events too): +* Rotate the first entry last of non-pinned groups */ perf_disable (); -list_rotate_left (&ctx->pinned_groups);list_rotate_left (&ctx->flexible_groups);perf_enable ();
Signature · 1 line
1.6.2.3
PATCH 6/6 perf: Increase round-robin fairness of flexible events
In reply to Frederic WeisbeckerGroup of flexible events are round-robined in each tick so that each group has its chance to be scheduled. But the fairness per group granularity doesn't propagate inside the groups themselves.
If only the first events of each groups have a chance to make their way, the remaining ones will never be scheduled.
Hence this patch propagates the round-robin to the events inside the groups.
--- kernel/perf_event.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-)
kernel/perf_event.c +5 -0
@@ -1446,16 +1446,21 @@ static void perf_ctx_adjust_freq(struct perf_event_context *ctx)*/ static void rotate_ctx (struct perf_event_context *ctx) { +struct perf_event *leader; +if (!ctx->nr_events)return ;raw_spin_lock (&ctx->lock);/* * Rotate the first entry last of non-pinned groups +* and events inside these groups */ perf_disable ();list_rotate_left (&ctx->flexible_groups); +list_for_each_entry (leader, &ctx->flexible_groups, group_entry) +list_rotate_left (&leader->sibling_list);perf_enable ();
Signature · 1 line
1.6.2.3
Re: [PATCH 6/6] perf: Increase round-robin fairness of flexible events
Frederic,
Nice to see someone working on the event scheduling in perf.
But I don't think this patch makes sense:
Quoted 10 lines
Group of flexible events are round-robined in each tick so that each group has its chance to be scheduled. But the fairness per group granularity doesn't propagate inside the groups themselves.
If only the first events of each groups have a chance to make their way, the remaining ones will never be scheduled.
Hence this patch propagates the round-robin to the events inside the groups.
The semantic of a group is that either all of the events in the group are scheduled in, or none of them are. So it doesn't make sense to talk about fairness within a group, and I don't see any point to rotating the elements of the sibling_list. Or have I misunderstood what you're aiming at?
Paul.
Re: [PATCH 6/6] perf: Increase round-robin fairness of flexible events
Quoted 14 lines · Paul Mackerras
Frederic,
Nice to see someone working on the event scheduling in perf.
But I don't think this patch makes sense:
Quoted 8 lines
Group of flexible events are round-robined in each tick so that each group has its chance to be scheduled. But the fairness per group granularity doesn't propagate inside the groups themselves.
If only the first events of each groups have a chance to make their way, the remaining ones will never be scheduled.
Quoted 8 lines
Quoted 2 lines
Hence this patch propagates the round-robin to the events inside the groups.
The semantic of a group is that either all of the events in the group are scheduled in, or none of them are. So it doesn't make sense to talk about fairness within a group, and I don't see any point to rotating the elements of the
sibling_list. Or have I misunderstood what you're aiming at?
You're right. I forgot that a group that is only partially scheduled will have its scheduled events cancelled.
But is it a sane behaviour considering the nature on non-pinned events?
Let's take an example. In x86 we have 4 breakpoint registers available.
We have 3 pinned breakpoint events in one group, and say, 2 groups of flexible breakpoints:
Pinned Flexible0 Flexible1
| | | Bp1 Bp4 Bp6 Bp2 Bp5 Bp7
Bp3
The flexible ones will never get scheduled because we only have 4 available slots and we need 5. And if we try to schedule Flexible0, Bp4 will make it, but not Bp5, so Bp4 get cancelled, and so on.
But the semantics of non-pinned counters is about time-sharing them.
If we don't cancel partially-only scheduled flexible groups and if we round robin inside flexible groups, then these will all make it.
I think the constraint of "either every or none get scheduled in a group" makes a lot of sense for pinned groups.
But I don't see the point in applying this rule inside flexible groups because the nature of flexible events implies these have been created to fight against a limited resource. So if this fight is done only between groups, this is like raising a voluntary starvation.
Or..or..May be I just realize too late that the semantic of a group implies that all events inside must be always counted simultaneously? In which case I agree with you, this patch makes no sense and must be dropped.
Re: [PATCH 6/6] perf: Increase round-robin fairness of flexible events
Quoted 11 lines · Frederic Weisbecker
I think the constraint of "either every or none get scheduled in a group" makes a lot of sense for pinned groups.
But I don't see the point in applying this rule inside flexible groups because the nature of flexible events implies these have been created to fight against a limited resource. So if this fight is done only between groups, this is like raising a voluntary starvation.
Quoted 4 lines
Or..or..May be I just realize too late that the semantic of a group implies that all events inside must be always counted simultaneously? In which case I agree with you, this patch makes no sense and must be dropped.
The original idea of the groups was for situations where you want to take the difference or ratio of two counts. For example, if you want to measure cache hits but the hardware can only count cache accesses and cache misses. In that situation you want to compute accesses minus misses, but if the counters for accesses and for misses are independently scheduled, statistical fluctuations can mean there is a lot of noise in the result, and it might even be negative. Putting the two counters into one group means that you can meaningfully compute the difference or ratio since the two counter values relate to the same set of instructions (even if that isn't the whole execution of the program).
The default situation is that each event is in its own group, so the starvation you talk about won't arise. If the user has gone to the trouble of putting two events into one group, then they are saying that they need the events to be scheduled on and off together, and if that leads to starvation, that's unfortunate but we can't do any better within the limitations of the hardware.
Paul.
Re: [PATCH 6/6] perf: Increase round-robin fairness of flexible events
Quoted 30 lines · Paul Mackerras
Quoted 11 lines · Frederic Weisbecker
I think the constraint of "either every or none get scheduled in a group" makes a lot of sense for pinned groups.
But I don't see the point in applying this rule inside flexible groups because the nature of flexible events implies these have been created to fight against a limited resource. So if this fight is done only between groups, this is like raising a voluntary starvation.
Quoted 4 lines
Or..or..May be I just realize too late that the semantic of a group implies that all events inside must be always counted simultaneously? In which case I agree with you, this patch makes no sense and must be dropped.
The original idea of the groups was for situations where you want to take the difference or ratio of two counts. For example, if you want to measure cache hits but the hardware can only count cache accesses and cache misses. In that situation you want to compute accesses minus misses, but if the counters for accesses and for misses are independently scheduled, statistical fluctuations can mean there is a lot of noise in the result, and it might even be negative. Putting the two counters into one group means that you can meaningfully compute the difference or ratio since the two counter values relate to the same set of instructions (even if that isn't the whole execution of the program).
Quoted 6 lines
The default situation is that each event is in its own group, so the starvation you talk about won't arise. If the user has gone to the trouble of putting two events into one group, then they are saying that they need the events to be scheduled on and off together, and if that leads to starvation, that's unfortunate but we can't do any better within the limitations of the hardware.
Agreed. This patch came from my misunderstanding of the purpose of groups.
Peter Zijlstra
maintainerQuoted 9 lines · Frederic Weisbecker
Hi,
These patches bring (I hope) a bit more scalability and fairness to the perf events scheduling.
But this is only an introduction as there is still some work to do, like ensuring all pinned events have been scheduled before flexible ones (for now we schedule in order cpu pinned, cpu flexible, task pinned, task flexible), among other improvements.
Right, so 1-5 look fine (although I'd have folded 5 into 3), thanks!
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Frederic Weisbecker
Hi,
These patches bring (I hope) a bit more scalability and fairness to the perf events scheduling.
Quoted 6 lines
Quoted 4 lines
But this is only an introduction as there is still some work to do, like ensuring all pinned events have been scheduled before flexible ones (for now we schedule in order cpu pinned, cpu flexible, task pinned, task flexible), among other improvements.
Right, so 1-5 look fine (although I'd have folded 5 into 3), thanks!
Ok, I'll merge 5 into 3 and send it as a pull request to Ingo with your ack.
Thanks.