Skip to contentSkip to conversation

perf/core: introduce context per CPU event list

PATCH In review [email protected] 4 participants 15 messages Nov 9, 2016 – Jan 4, 2017 1 message not in the archive perf events

lore
Share & tools
lore

[email protected]

author
#0 lore raw

PATCH 1/1 perf/core: introduce context per CPU event list

From: Kan Liang <[email protected]>

The perf per-process monitoring overhead increases rapidly with the increasing of events# and CPU#.

Here is some data from the overhead test on Skylake server which has 64 logical CPU. Elapsed time of AIM7 is used to measure the overhead.
perf record -e $event_list -p $pid #$pid is the pid of AIM7
Elapsed time A: elapsed time of AIM7
Elapsed time B: elapsed time of AIM7 while perf is running in parallel. Overhead = (B - A) / A
Events# Overhead (%)
1 0.45%
2 1.20%
4 3.85%
8 15.82%
16 50.24%

The perf_iterate_ctx contributes to the most of the increased overheads. Because it iterates over the whole rcu list ctx->event_list. ctx->event_list increases rapidly by adding events. By adding one event, CPU# of events will be finally inserted into the event_list. Iterating the whole event list will become a disaster on multi-core systems with large CPU#.

Actually, it doesn't need to iterate the whole rcu list every time. Sometimes, it only needs to output the event on current CPU. A per cpu event list is introduced to divide the big rcu list into small per CPU rcu lists, which significantly reduce the overhead.
Events# Overhead (%)
1 0.15%
2 1.06%
4 1.85%
8 9.99%
16 17.26%

Signed-off-by Kan Liang <[email protected]>
---
 include/linux/perf_event.h |   3 +-
 kernel/events/core.c       | 177 ++++++++++++++++++++++++++++++++++-----------
 2 files changed, 138 insertions(+), 42 deletions(-)
include/linux/perf_event.h +2 -1
index 4741ecd..1222a33 100644
@@ -734,7 +734,8 @@ struct perf_event_context {
 	struct list_head		active_ctx_list;
 	struct list_head		pinned_groups;
 	struct list_head		flexible_groups;
-	struct list_head		event_list;
+	struct list_head		*__percpu event_list;
+
 	int				nr_events;
 	int				nr_active;
 	int				is_active;
kernel/events/core.c +136 -41

360 lines not on this page · raw message

Signature · 1 line
2.5.5
maintainer
#1 lore raw

Yes this is a problem, but no this cannot be done. We can't have per-cpu storage per task. That rapidly explodes.

Mark is looking at replacing this stuff with an rb-tree for big-little, that would also allow improving this I think.

reviewer
#2 lore raw

Hi,

Quoted 5 lines · Peter Zijlstra

Yes this is a problem, but no this cannot be done. We can't have per-cpu storage per task. That rapidly explodes.

Mark is looking at replacing this stuff with an rb-tree for big-little, that would also allow improving this I think.

Unfortunately I've not had the chance to look at that since returning from Plumbers. Also, I was leaning towards the alternative approach we discussed, with a perf_event_task_contexts container, as that also solved some other issues with the way we used perf_event_context::pmu in big.LITTLE systems.

Looking at the way perf_iterate_ctx is used, it seems that we're just trying to iterate over the active events for a context (i.e. those programmed into the HW at this point in time). Though I'm missing some subtlety, since we check event->state < PERF_EVENT_STATE_INACTIVE.

We have a similar issue with perf_event_task_tick() needing to know the relevant contexts, and for that we have the active_ctx_list. Can't we do something similar and add an active_events_list to perf_event_context?

Thanks,
Mark.

maintainer
#3 lore raw
Quoted 15 lines · Mark Rutland

Hi,

Quoted 5 lines · Peter Zijlstra

Yes this is a problem, but no this cannot be done. We can't have per-cpu storage per task. That rapidly explodes.

Mark is looking at replacing this stuff with an rb-tree for big-little, that would also allow improving this I think.

Unfortunately I've not had the chance to look at that since returning from Plumbers. Also, I was leaning towards the alternative approach we discussed, with a perf_event_task_contexts container, as that also solved some other issues with the way we used perf_event_context::pmu in big.LITTLE systems.

Quoted 8 lines

Looking at the way perf_iterate_ctx is used, it seems that we're just trying to iterate over the active events for a context (i.e. those programmed into the HW at this point in time). Though I'm missing some subtlety, since we check event->state < PERF_EVENT_STATE_INACTIVE.

We have a similar issue with perf_event_task_tick() needing to know the relevant contexts, and for that we have the active_ctx_list. Can't we do something similar and add an active_events_list to perf_event_context?

So the problem is finding which events are active when.

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we can, fairly easily, find the relevant subtree and limit the iteration. Esp. if we use a threaded tree.

reviewer
#4 lore raw
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Mark Rutland
Quoted 5 lines · Peter Zijlstra

Yes this is a problem, but no this cannot be done. We can't have per-cpu storage per task. That rapidly explodes.

Mark is looking at replacing this stuff with an rb-tree for big-little, that would also allow improving this I think.

Unfortunately I've not had the chance to look at that since returning from Plumbers. Also, I was leaning towards the alternative approach we discussed, with a perf_event_task_contexts container, as that also solved some other issues with the way we used perf_event_context::pmu in big.LITTLE systems.

Looking at the way perf_iterate_ctx is used, it seems that we're just trying to iterate over the active events for a context (i.e. those programmed into the HW at this point in time). Though I'm missing some subtlety, since we check event->state < PERF_EVENT_STATE_INACTIVE.

Quoted 5 lines
Quoted 3 lines

We have a similar issue with perf_event_task_tick() needing to know the relevant contexts, and for that we have the active_ctx_list. Can't we do something similar and add an active_events_list to perf_event_context?

So the problem is finding which events are active when.

Sure.

If we only care about PERF_EVENT_STATE_ACTIVE, then I think we can fairly easily maintain a perf_event_context::active_event_list at event_sched_{in,out}() time (or somewhere close to that).

If we need PERF_EVENT_STATE_INACTIVE events, then that doesn't work, since we can give up early and not schedule some eligible events.

Quoted 3 lines

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we can, fairly easily, find the relevant subtree and limit the iteration. Esp. if we use a threaded tree.

That would cater for big.LITTLE, certainly, but I'm not sure I follow how that helps to find active events -- you'll still have to iterate through the whole PMU subtree to find which are active, no?

Thanks,
Mark.

maintainer
#5 lore raw
Quoted 13 lines · Mark Rutland
Quoted 1 line · Peter Zijlstra

So the problem is finding which events are active when.

Sure.

If we only care about PERF_EVENT_STATE_ACTIVE, then I think we can fairly easily maintain a perf_event_context::active_event_list at event_sched_{in,out}() time (or somewhere close to that).

If we need PERF_EVENT_STATE_INACTIVE events, then that doesn't work, since we can give up early and not schedule some eligible events.

Quoted 7 lines
Quoted 3 lines

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we can, fairly easily, find the relevant subtree and limit the iteration. Esp. if we use a threaded tree.

That would cater for big.LITTLE, certainly, but I'm not sure I follow how that helps to find active events -- you'll still have to iterate through the whole PMU subtree to find which are active, no?

Ah, so the tree would in fact only contain 'INACTIVE' events :-)

That is, when no events are on the hardware, all events (if there are any) are INACTIVE.

Then on sched-in, we find the relevant subtree, and linearly try and program all events from that subtree onto the PMU. Once adding an event fails programming, we stop (like we do now).

These programmed events transition from INACTIVE to ACTIVE, and we take them out of the tree.

Then on sched-out, we remove all events from the hardware, increase the events their runtime value by however long they were ACTIVE, flip them to INACTIVE and stuff them back in the tree.

(I'm can't quite recall if we can easily find ACTIVE events from a PMU, but if not, we can easily track those on a separate list).

reviewer
#6 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Mark Rutland
Quoted 5 lines · Peter Zijlstra

So the problem is finding which events are active when.

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we can, fairly easily, find the relevant subtree and limit the iteration. Esp. if we use a threaded tree.

Quoted 5 lines
Quoted 3 lines

That would cater for big.LITTLE, certainly, but I'm not sure I follow how that helps to find active events -- you'll still have to iterate through the whole PMU subtree to find which are active, no?

Ah, so the tree would in fact only contain 'INACTIVE' events :-)

Ah. :)

That explains some of the magic, but...

Quoted 7 lines

That is, when no events are on the hardware, all events (if there are any) are INACTIVE.

Then on sched-in, we find the relevant subtree, and linearly try and program all events from that subtree onto the PMU. Once adding an event fails programming, we stop (like we do now).

Quoted 6 lines

These programmed events transition from INACTIVE to ACTIVE, and we take them out of the tree.

Then on sched-out, we remove all events from the hardware, increase the events their runtime value by however long they were ACTIVE, flip them to INACTIVE and stuff them back in the tree.

... per the above, won't the tree also contain 'OFF' events (and 'ERROR', etc)?

... or do we keep them somewhere else (another list or sub-tree)?

If not, we still have to walk all of those in perf_iterate_ctx().

Quoted 2 lines

(I'm can't quite recall if we can easily find ACTIVE events from a PMU, but if not, we can easily track those on a separate list).

I think we just iterate the perf_event_context::event list and look at the state. Regardless, adding lists is fairly simple.

Thanks,
Mark.

maintainer
#7 lore raw
Quoted 18 lines · Mark Rutland
Quoted 1 line · Peter Zijlstra

Ah, so the tree would in fact only contain 'INACTIVE' events :-)

Ah. :)

That explains some of the magic, but...

Quoted 10 lines

That is, when no events are on the hardware, all events (if there are any) are INACTIVE.

Then on sched-in, we find the relevant subtree, and linearly try and program all events from that subtree onto the PMU. Once adding an event fails programming, we stop (like we do now).

These programmed events transition from INACTIVE to ACTIVE, and we take them out of the tree.

Quoted 8 lines
Quoted 3 lines

Then on sched-out, we remove all events from the hardware, increase the events their runtime value by however long they were ACTIVE, flip them to INACTIVE and stuff them back in the tree.

... per the above, won't the tree also contain 'OFF' events (and 'ERROR', etc)?

... or do we keep them somewhere else (another list or sub-tree)?

I don't think those need be tracked at all, they're immaterial for actual scheduling. Once we ioctl() them back to life we can insert them into the tree.

Quoted 10 lines

If not, we still have to walk all of those in perf_iterate_ctx().

Quoted 2 lines

(I'm can't quite recall if we can easily find ACTIVE events from a PMU, but if not, we can easily track those on a separate list).

I think we just iterate the perf_event_context::event list and look at the state. Regardless, adding lists is fairly simple.

Thanks,
Mark.

reviewer
#8 lore raw
Quoted 23 lines · Peter Zijlstra
Quoted 22 lines · Mark Rutland
Quoted 1 line · Peter Zijlstra

Ah, so the tree would in fact only contain 'INACTIVE' events :-)

Ah. :)

That explains some of the magic, but...

Quoted 13 lines

That is, when no events are on the hardware, all events (if there are any) are INACTIVE.

Then on sched-in, we find the relevant subtree, and linearly try and program all events from that subtree onto the PMU. Once adding an event fails programming, we stop (like we do now).

These programmed events transition from INACTIVE to ACTIVE, and we take them out of the tree.

Then on sched-out, we remove all events from the hardware, increase the events their runtime value by however long they were ACTIVE, flip them to INACTIVE and stuff them back in the tree.

Quoted 8 lines
Quoted 4 lines

... per the above, won't the tree also contain 'OFF' events (and 'ERROR', etc)?

... or do we keep them somewhere else (another list or sub-tree)?

I don't think those need be tracked at all, they're immaterial for actual scheduling. Once we ioctl() them back to life we can insert them into the tree.

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Thanks,
Mark.

author
#9 lore raw
Quoted 6 lines
Quoted 5 lines

I don't think those need be tracked at all, they're immaterial for actual scheduling. Once we ioctl() them back to life we can insert them into the tree.

Quoted 8 lines

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Yes, if we can sort the tree by event->cpu, we can minimize the iteration in the perf_iterate_ctx. That should help on reducing the overhead.

Thanks,
Kan

maintainer
#10 lore raw
In reply to Mark Rutland
Quoted 9 lines · Mark Rutland

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Quoted 1 line · A few emails back up I
Quoted 1 line

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we

Looking at the code there's also cgroup muck, not entirely sure where in the sort order that should go if at all.

But having pmu and cpu in there would cure the big-little and per-task-per-cpu event issues.

reviewer
#11 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Mark Rutland

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

Quoted 6 lines
Quoted 2 lines

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Quoted 1 line · A few emails back up I
Quoted 1 line

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we

Ah, sorry. Clearly I wouldn't pass a reading comprehension test today.

Quoted 5 lines

Looking at the code there's also cgroup muck, not entirely sure where in the sort order that should go if at all.

But having pmu and cpu in there would cure the big-little and per-task-per-cpu event issues.

Yup, that all makes sense to me now (modulo the cgroup stuff I also haven't considered yet).

Thanks,
Mark.

A message that is not in the archive (sent off-list or not yet received): [email protected]

#13 lore raw
Quoted 21 lines · David Carrillo-Cisneros

From: Mark Rutland <[email protected]>

Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Mark Rutland

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

Quoted 6 lines
Quoted 2 lines

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Quoted 1 line · A few emails back up I
Quoted 1 line

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we

Ah, sorry. Clearly I wouldn't pass a reading comprehension test today.

Quoted 8 lines
Quoted 5 lines

Looking at the code there's also cgroup muck, not entirely sure where in the sort order that should go if at all.

But having pmu and cpu in there would cure the big-little and per-task-per-cpu event issues.

Yup, that all makes sense to me now (modulo the cgroup stuff I also haven't considered yet).

cgroup events are stored in each pmu's cpuctx, so they wouldn't benefit from a pmu,cpu sort order. Yet the RB-tree would help if it could use cgroup as key for cpu contexts.

Is there a reason to have runtime as part of the RB-tree? Couldn't a FIFO list work just fine? A node could have an ACTIVE and an INACTIVE FIFO list and just move the events in out the tree in ioctl and to/from ACTIVE from/to INACTIVE on sched in/out.
This would speed up both sched in and sched out.

The node would be something like this:

struct ctx_rbnode {
        struct rb_node node;
        struct list_head active_events;
        struct list_head inactive_events;
};

And the insertion order would be {pmu, cpu} for task contexts (cpu == -1 for events without fixed cpu) and {cgroup} for cpuctxs (CPU events would have NULL cgrp).

Am I interested on getting this to work as part of the cgroup context switch optimization that CQM/CMT needs. See discussion in:

https://patchwork.kernel.org/patch/9478617/

Is anyone actively working on it?

Thanks,
David

reviewer
#14 lore raw
Quoted 29 lines · David Carrillo-Cisneros
Quoted 27 lines · David Carrillo-Cisneros

From: Mark Rutland <[email protected]>

Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Mark Rutland

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

Quoted 6 lines
Quoted 2 lines

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Quoted 1 line · A few emails back up I
Quoted 1 line

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we

Ah, sorry. Clearly I wouldn't pass a reading comprehension test today.

Quoted 5 lines

Looking at the code there's also cgroup muck, not entirely sure where in the sort order that should go if at all.

But having pmu and cpu in there would cure the big-little and per-task-per-cpu event issues.

Quoted 8 lines
Quoted 2 lines

Yup, that all makes sense to me now (modulo the cgroup stuff I also haven't considered yet).

cgroup events are stored in each pmu's cpuctx, so they wouldn't benefit from a pmu,cpu sort order. Yet the RB-tree would help if it could use cgroup as key for cpu contexts.

Is there a reason to have runtime as part of the RB-tree?

Fairer scheduling of the events, especially where cross-group conflicts for PMU resources are non-trivial to solve. IIRC this is the major reason Peter wanted the RB tree in the first place.

Quoted 13 lines

Couldn't a FIFO list work just fine? A node could have an ACTIVE and an INACTIVE FIFO list and just move the events in out the tree in ioctl and to/from ACTIVE from/to INACTIVE on sched in/out.
This would speed up both sched in and sched out.

The node would be something like this:

struct ctx_rbnode {
        struct rb_node node;
        struct list_head active_events;
        struct list_head inactive_events;
};
Quoted 3 lines

And the insertion order would be {pmu, cpu} for task contexts (cpu == -1 for events without fixed cpu) and {cgroup} for cpuctxs (CPU events would have NULL cgrp).

The problem with using a list rather than a tree is that we have to perform a linear walk of the list every time we want to find the relevant sub-list (e.g. scheduling, insertion). Using a tree makes finding the relevant portion much cheaper.

Quoted 6 lines

Am I interested on getting this to work as part of the cgroup context switch optimization that CQM/CMT needs. See discussion in:

https://patchwork.kernel.org/patch/9478617/

Is anyone actively working on it?

Unfortunately I have too much on my plate at the moment; I'm not actively working on this.

I'm happy to review and test patches, though!

Thanks,
Mark.

#15 lore raw
Quoted 37 lines · Mark Rutland
Quoted 36 lines · David Carrillo-Cisneros
Quoted 21 lines · David Carrillo-Cisneros

From: Mark Rutland <[email protected]>

Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Mark Rutland

Sure, that sounds fine for scheduling (including big.LITTLE).

I might still be misunderstanding something, but I don't think that helps Kan's case: since INACTIVE events which will fail their filters (including the CPU check) will still be in the tree, they will still have to be iterated over.

Quoted 6 lines
Quoted 2 lines

That is, unless we also sort the tree by event->cpu, or if in those cases we only care about ACTIVE events and can use an active list.

Quoted 1 line · A few emails back up I
Quoted 1 line

If we stick all events in an RB-tree sorted on: {pmu,cpu,runtime} we

Ah, sorry. Clearly I wouldn't pass a reading comprehension test today.

Quoted 8 lines
Quoted 5 lines

Looking at the code there's also cgroup muck, not entirely sure where in the sort order that should go if at all.

But having pmu and cpu in there would cure the big-little and per-task-per-cpu event issues.

Yup, that all makes sense to me now (modulo the cgroup stuff I also haven't considered yet).

cgroup events are stored in each pmu's cpuctx, so they wouldn't benefit from a pmu,cpu sort order. Yet the RB-tree would help if it could use cgroup as key for cpu contexts.

Quoted 5 lines
Quoted 1 line

Is there a reason to have runtime as part of the RB-tree?

Fairer scheduling of the events, especially where cross-group conflicts for PMU resources are non-trivial to solve. IIRC this is the major reason Peter wanted the RB tree in the first place.

I see, so we want to be able to reinsert conflicting groups efficiently. It makes
sense.

Quoted 14 lines
Quoted 14 lines

Couldn't a FIFO list work just fine? A node could have an ACTIVE and an INACTIVE FIFO list and just move the events in out the tree in ioctl and to/from ACTIVE from/to INACTIVE on sched in/out.
This would speed up both sched in and sched out.

The node would be something like this:

struct ctx_rbnode {
        struct rb_node node;
        struct list_head active_events;
        struct list_head inactive_events;
};
Quoted 8 lines
Quoted 3 lines

And the insertion order would be {pmu, cpu} for task contexts (cpu == -1 for events without fixed cpu) and {cgroup} for cpuctxs (CPU events would have NULL cgrp).

The problem with using a list rather than a tree is that we have to perform a linear walk of the list every time we want to find the relevant sub-list (e.g. scheduling, insertion). Using a tree makes finding the relevant portion much cheaper.

Then we could extend the per data that each pmu allocates in perf_pmu_register to something like:

struct pmu_percpu_data {
        struct perf_cpu_context;         /* what it currently allocates */
        struct list_head active_events_list;
        struct rb_root inactive_events_rbtree;
};

The events in the inactive rbtree can be sorted by the time they've been waiting to be scheduled.

The closer I can find to a per PMU list of active events are the intel lists existing
in RAPL and uncore pmus. They use perf_event::active_entry. This could be moved to generic code and maintain active_event_list for all {pmus,cpus}.

Quoted 4 lines
Quoted 4 lines

Am I interested on getting this to work as part of the cgroup context switch optimization that CQM/CMT needs. See discussion in:

Quoted 8 lines
Quoted 3 lines

https://patchwork.kernel.org/patch/9478617/

Is anyone actively working on it?

Unfortunately I have too much on my plate at the moment; I'm not actively working on this.

I'm happy to review and test patches, though!

I'll be happy to give this a try then!

Thanks,
David

Quoted 3 lines

Thanks,
Mark.