perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi
PATCH RESEND v3 1/1 perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi
perf/core: use rb trees for pinned/flexible groups
By default, the userspace perf tool opens per-cpu task-bound events when sampling, so for N logical events requested by the user, the tool will open N * NR_CPUS events.
In the kernel, we mux events with a hrtimer, periodically rotating the
flexible group list and trying to schedule each group in turn. We skip groups whose cpu filter doesn't match. So when we get unlucky, we can walk N * (NR_CPUS - 1) groups pointlessly for each hrtimer invocation.
This has been observed to result in significant overhead when running the STREAM benchmark on 272 core Xeon Phi systems.
One way to avoid this is to place our events into an rb tree sorted by CPU filter, so that our hrtimer can skip to the current CPU's list and ignore everything else.
As a step towards that, this patch replaces event group lists with rb trees.
--- include/linux/perf_event.h | 18 ++- kernel/events/core.c | 393 +++++++++++++++++++++++++++++++++------------ 2 files changed, 307 insertions(+), 104 deletions(-)
Addressed Mark Rutland's comments from the previous patch version.
include/linux/perf_event.h +16 -2
@@ -574,6 +574,20 @@ struct perf_event {struct list_head sibling_list;/* +* Node on the pinned or flexible tree located at the event context; +* the node may be empty in case its event is not directly attached +* to the tree but to group_list list of the event directly +* attached to the tree; +*/ +struct rb_node group_node; +/* +* List keeps groups allocated for the same cpu; +* the list may be empty in case its event is not directly +* attached to the tree but to group_list list of the event directly +* attached to the tree; +*/ +struct list_head group_list; +/* * We need storage to track the entries in perf_pmu_migrate_context; we * cannot use the event_entry because of RCU and we want to keep the * group in tact which avoids us using the other two entries.
@@ -741,8 +755,8 @@ struct perf_event_context {struct mutex mutex;struct list_head active_ctx_list; -struct list_head pinned_groups; -struct list_head flexible_groups; +struct rb_root pinned_groups; +struct rb_root flexible_groups;struct list_head event_list;int nr_events;int nr_active;
kernel/events/core.c +291 -102
538 lines not on this page · raw message
Mark Rutland
reviewerQuoted 22 lines · Alexey Budankov
perf/core: use rb trees for pinned/flexible groups
By default, the userspace perf tool opens per-cpu task-bound events when sampling, so for N logical events requested by the user, the tool will open N *
NR_CPUSevents.In the kernel, we mux events with a hrtimer, periodically rotating the flexible group list and trying to schedule each group in turn. We skip groups whose cpu filter doesn't match. So when we get unlucky, we can walk N * (
NR_CPUS- 1) groups pointlessly for each hrtimer invocation.This has been observed to result in significant overhead when running the STREAM benchmark on 272 core Xeon Phi systems.
One way to avoid this is to place our events into an rb tree sorted by CPU filter, so that our hrtimer can skip to the current CPU's list and ignore everything else.
As a step towards that, this patch replaces event group lists with rb trees.
Quoted 8 lines
Signed-off-by Alexey Budankov <[email protected]>--- include/linux/perf_event.h | 18 ++- kernel/events/core.c | 393 +++++++++++++++++++++++++++++++++------------ 2 files changed, 307 insertions(+), 104 deletions(-)Addressed Mark Rutland's comments from the previous patch version.
... then this should be v4, no?
Which comments? Could you pelase write a changelog in future?
In future, please send patches as a series, with a known upper-bound rather than N. It's really painful to find them when they're sent separately, without a known upper bound.
[...]
Quoted 11 lines
+/*
+ * Delete a group from a tree. If the group is directly attached to the tree
+ * it also detaches all groups on the group'sgroup_listlist.
+ */kernel/events/core.c +6
-0+static void +perf_cpu_tree_delete (struct rb_root *tree,struct perf_event *event) +{ +WARN_ON_ONCE (!tree || !event); + +if (RB_EMPTY_NODE (&event->group_node)) {
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1528
Quoted 10 lines
kernel/events/core.c +10
-0+list_del_init (&event->group_entry); + }else { +struct perf_event *list_event, *list_next; + +rb_erase (&event->group_node, tree); +list_for_each_entry_safe (list_event, list_next, + &event->group_list, group_entry) +list_del_init (&list_event->group_entry); + } +}
As I commented on the last version, this means that all groups which were (incidentally) hanging off of this one are removed, and can no longer be reached via the tree.
Surely one of the remaining groups should be added to the tree?
I don't beleive that is correct.
I beleive it would be simpler to reason about a threaded rb-tree here, since that special case wouldn't exist.
Thanks,
Mark.
Quoted 30 lines · Mark Rutland
Quoted 29 lines · Alexey Budankov
perf/core: use rb trees for pinned/flexible groups
By default, the userspace perf tool opens per-cpu task-bound events when sampling, so for N logical events requested by the user, the tool will open N *
NR_CPUSevents.In the kernel, we mux events with a hrtimer, periodically rotating the flexible group list and trying to schedule each group in turn. We skip groups whose cpu filter doesn't match. So when we get unlucky, we can walk N * (
NR_CPUS- 1) groups pointlessly for each hrtimer invocation.This has been observed to result in significant overhead when running the STREAM benchmark on 272 core Xeon Phi systems.
One way to avoid this is to place our events into an rb tree sorted by CPU filter, so that our hrtimer can skip to the current CPU's list and ignore everything else.
As a step towards that, this patch replaces event group lists with rb trees.
Signed-off-by Alexey Budankov <[email protected]>--- include/linux/perf_event.h | 18 ++- kernel/events/core.c | 393 +++++++++++++++++++++++++++++++++------------ 2 files changed, 307 insertions(+), 104 deletions(-)
Quoted 5 lines
Quoted 1 line
Addressed Mark Rutland's comments from the previous patch version.
... then this should be v4, no?
Which comments? Could you pelase write a changelog in future?
Changes are:
1. changed type of pinned_groups/flexible_groups to rb_tree;
2. removed group_list_entry and reused group_entry for that purposes;
3. added add_to_groups()/del_from_groups() helper functions;
Quoted 4 lines
In future, please send patches as a series, with a known upper-bound rather than N. It's really painful to find them when they're sent separately, without a known upper bound.
Accepted.
Quoted 29 lines
[...]
Quoted 11 lines
+/*
+ * Delete a group from a tree. If the group is directly attached to the tree
+ * it also detaches all groups on the group'sgroup_listlist.
+ */kernel/events/core.c +6
-0+static void +perf_cpu_tree_delete (struct rb_root *tree,struct perf_event *event) +{ +WARN_ON_ONCE (!tree || !event); + +if (RB_EMPTY_NODE (&event->group_node)) {kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1528
Quoted 10 lines
kernel/events/core.c +10
-0+list_del_init (&event->group_entry); + }else { +struct perf_event *list_event, *list_next; + +rb_erase (&event->group_node, tree); +list_for_each_entry_safe (list_event, list_next, + &event->group_list, group_entry) +list_del_init (&list_event->group_entry); + } +}As I commented on the last version, this means that all groups which were (incidentally) hanging off of this one are removed, and can no longer be reached via the tree.
Quoted 1 line
Surely one of the remaining groups should be added to the tree?
Aww, I see. That needs to implemented. Thanks.
Quoted 9 lines
I don't beleive that is correct.
I beleive it would be simpler to reason about a threaded rb-tree here, since that special case wouldn't exist.
Thanks,
Mark.
Mark Rutland
reviewerQuoted 35 lines · Alexey Budankov
Quoted 34 lines · Mark Rutland
Quoted 22 lines · Alexey Budankov
perf/core: use rb trees for pinned/flexible groups
By default, the userspace perf tool opens per-cpu task-bound events when sampling, so for N logical events requested by the user, the tool will open N *
NR_CPUSevents.In the kernel, we mux events with a hrtimer, periodically rotating the flexible group list and trying to schedule each group in turn. We skip groups whose cpu filter doesn't match. So when we get unlucky, we can walk N * (
NR_CPUS- 1) groups pointlessly for each hrtimer invocation.This has been observed to result in significant overhead when running the STREAM benchmark on 272 core Xeon Phi systems.
One way to avoid this is to place our events into an rb tree sorted by CPU filter, so that our hrtimer can skip to the current CPU's list and ignore everything else.
As a step towards that, this patch replaces event group lists with rb trees.
Quoted 8 lines
Signed-off-by Alexey Budankov <[email protected]>--- include/linux/perf_event.h | 18 ++- kernel/events/core.c | 393 +++++++++++++++++++++++++++++++++------------ 2 files changed, 307 insertions(+), 104 deletions(-)Addressed Mark Rutland's comments from the previous patch version.
... then this should be v4, no?
Quoted 7 lines
Quoted 1 line
Which comments? Could you pelase write a changelog in future?
Changes are:
1. changed type of pinned_groups/flexible_groups to
rb_tree;
2. removedgroup_list_entryand reusedgroup_entryfor that purposes;
3. added add_to_groups()/del_from_groups() helper functions;
Thanks; the new changelog is much appreciated.
Mark.
Quoted 79 lines · Alexey Budankov
Quoted 30 lines · Mark Rutland
Quoted 29 lines · Alexey Budankov
perf/core: use rb trees for pinned/flexible groups
By default, the userspace perf tool opens per-cpu task-bound events when sampling, so for N logical events requested by the user, the tool will open N *
NR_CPUSevents.In the kernel, we mux events with a hrtimer, periodically rotating the flexible group list and trying to schedule each group in turn. We skip groups whose cpu filter doesn't match. So when we get unlucky, we can walk N * (
NR_CPUS- 1) groups pointlessly for each hrtimer invocation.This has been observed to result in significant overhead when running the STREAM benchmark on 272 core Xeon Phi systems.
One way to avoid this is to place our events into an rb tree sorted by CPU filter, so that our hrtimer can skip to the current CPU's list and ignore everything else.
As a step towards that, this patch replaces event group lists with rb trees.
Signed-off-by Alexey Budankov <[email protected]>--- include/linux/perf_event.h | 18 ++- kernel/events/core.c | 393 +++++++++++++++++++++++++++++++++------------ 2 files changed, 307 insertions(+), 104 deletions(-)Quoted 5 lines
Quoted 1 line
Addressed Mark Rutland's comments from the previous patch version.
... then this should be v4, no?
Which comments? Could you pelase write a changelog in future?
Changes are:
1. changed type of pinned_groups/flexible_groups to
rb_tree;
2. removedgroup_list_entryand reusedgroup_entryfor that purposes;
3. added add_to_groups()/del_from_groups() helper functions;Quoted 4 lines
In future, please send patches as a series, with a known upper-bound rather than N. It's really painful to find them when they're sent separately, without a known upper bound.
Accepted.
Quoted 29 lines
[...]
Quoted 11 lines
+/*
+ * Delete a group from a tree. If the group is directly attached to the tree
+ * it also detaches all groups on the group'sgroup_listlist.
+ */kernel/events/core.c +6
-0+static void +perf_cpu_tree_delete (struct rb_root *tree,struct perf_event *event) +{ +WARN_ON_ONCE (!tree || !event); + +if (RB_EMPTY_NODE (&event->group_node)) {kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1528
Quoted 10 lines
kernel/events/core.c +10
-0+list_del_init (&event->group_entry); + }else { +struct perf_event *list_event, *list_next; + +rb_erase (&event->group_node, tree); +list_for_each_entry_safe (list_event, list_next, + &event->group_list, group_entry) +list_del_init (&list_event->group_entry); + } +}As I commented on the last version, this means that all groups which were (incidentally) hanging off of this one are removed, and can no longer be reached via the tree.
Quoted 3 lines
Quoted 1 line
Surely one of the remaining groups should be added to the tree?
Aww, I see. That needs to implemented. Thanks.
Addressing that inconsistency like this:
static voidperf_cpu_tree_delete(struct rb_root *tree, struct perf_event *event)
{
struct perf_event *next;
WARN_ON_ONCE(!tree || !event);
list_del_init(&event->group_entry);
if (!RB_EMPTY_NODE(&event->group_node)) {
if (!list_empty(&event->group_list)) {
next = list_first_entry(&event->group_list,
struct perf_event, group_entry);
list_replace_init(&event->group_list,
&next->group_list);
rb_replace_node(&event->group_node,
&next->group_node, tree);
} else {
rb_erase(&event->group_node, tree);
}
RB_CLEAR_NODE(&event->group_node);
}
}solves list_del corruption:
list_del corruption. prev->next should be ffff88c2c4654010, but was ffff88c31eb0c020
[ 607.632813] ------------[ cut here ]------------ [ 607.632816] kernel BUG at lib/list_debug.c:53!
[ 607.635531] Call Trace: [ 607.635583] list_del_event+0x1d7/0x210
and x86_pmu_start warning:
[ 484.804737] WARNING: CPU: 15 PID: 31168 at arch/x86/events/core.c:1257 x86_pmu_start+0x8f/0xb0
[ 484.804938] RIP: 0010:x86_pmu_start+0x8f/0xb0 [ 484.804971] Call Trace: [ 484.804976] <IRQ> [ 484.804984] x86_pmu_enable+0x27f/0x2f0
Quoted 12 lines
Quoted 10 lines
I don't beleive that is correct.
I beleive it would be simpler to reason about a threaded rb-tree here, since that special case wouldn't exist.
Thanks,
Mark.