: perf/core: use rb trees for pinned/flexible groups
PATCH v5 1/4 : perf/core: use rb trees for pinned/flexible groups
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, so that our hrtimer can skip to the current CPU's list and ignore everything else.
As a step towards that, this patch introduces rb tree for group lists.
--- include/linux/perf_event.h | 33 +++- kernel/events/core.c | 458 +++++++++++++++++++++++++++++++++++---------- 2 files changed, 395 insertions(+), 96 deletions(-)
include/linux/perf_event.h +31 -2
@@ -572,6 +572,26 @@ struct perf_event {*/ struct list_head group_entry;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; +/* +* Entry into the group_list list above; +* the entry may be attached to the self group_list list above +* in case the event is directly attached to the tree; +*/ +struct list_head group_list_entry;/* * We need storage to track the entries in perf_pmu_migrate_context; we
@@ -721,6 +741,15 @@ struct perf_event {#endif /* CONFIG_PERF_EVENTS */ }; +/* +* event groups keep group leader events arranged as an rb tree with +* event->cpu key and as a list for the whole tree iterations; +*/ +struct perf_event_groups { +struct list_head list; +struct rb_root tree; +}; +/** * struct perf_event_context - event context structure *
@@ -741,8 +770,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 perf_event_groups pinned_groups; +struct perf_event_groups flexible_groups;struct list_head event_list;int nr_events;int nr_active;
kernel/events/core.c +364 -94
633 lines not on this page · raw message
Alexander Shishkin
reviewerkernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1609
Quoted 7 lines · Alexey Budankov
kernel/events/core.c +7
-0+static void +perf_event_groups_rotate (struct perf_event_groups *groups,int cpu) +{ +struct rb_node *node; +struct perf_event *node_event; + +WARN_ON_ONCE (!groups);
This seems redundant.
Quoted 12 lines
kernel/events/core.c +12
-0+ +list_rotate_left (&groups->list); + +/* will replace rotation above in patch v5 3/4 + +node = groups->tree.rb_node; + +while (node) { +node_event = container_of(node, +struct perf_event, group_node); + +if (cpu < node_event->cpu) {
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1631
Quoted 10 lines
kernel/events/core.c +10
-0+node = node->rb_left; +} else if (cpu > node_event->cpu) { +node = node->rb_right; +} else { +list_rotate_left(&node_event->group_list); +break; +} +} + +*/
Please don't do this, it doesn't add clarity.
Quoted 20 lines
kernel/events/core.c +20
-0+static int +perf_event_groups_iterate (struct perf_event_groups *groups, +perf_event_groups_iterate_f callback,void *data) +{ +int ret =0 ; +struct perf_event *event; + +WARN_ON_ONCE (!groups); + +list_for_each_entry (event, &groups->list, group_list_entry) { + ret =callback (event, data); +if (ret) +break ; + } + +/* will replace itration above in patch v5 4/4 + +for (node = rb_first(groups); node; node = rb_next(node)) { +node_event = container_of(node, struct perf_event, group_node); +list_for_each_entry(event, &node_event->group_list,
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1702
Quoted 10 lines
kernel/events/core.c +10
-0+group_list_entry) { +WARN_ON_ONCE(!(event->cpu == node_event->cpu)); +ret = callback(event, data); +if (ret) { +return ret; +} +} +} + +*/
Ditto.
Regards,
--
Alex
Hi,
Quoted 11 lines · Alexander Shishkin
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1609
Quoted 7 lines · Alexey Budankov
kernel/events/core.c +7
-0+static void +perf_event_groups_rotate (struct perf_event_groups *groups,int cpu) +{ +struct rb_node *node; +struct perf_event *node_event; + +WARN_ON_ONCE (!groups);This seems redundant.
Used that for debugging.
Quoted 17 lines
Quoted 17 lines
kernel/events/core.c +16
-0+ +list_rotate_left (&groups->list); + +/* will replace rotation above in patch v5 3/4 + +node = groups->tree.rb_node; + +while (node) { +node_event = container_of(node, +struct perf_event, group_node); + +if (cpu < node_event->cpu) { +node = node->rb_left; +} else if (cpu > node_event->cpu) { +node = node->rb_right; +} else {
Quoted 8 lines
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1631
Quoted 6 lines
kernel/events/core.c +6
-0+list_rotate_left(&node_event->group_list); +break; +} +} + +*/ Please don't do this, it doesn't add clarity.
Accepted. Put it here just for review process simplification.
Quoted 34 lines
Quoted 21 lines
kernel/events/core.c +20
-0+static int +perf_event_groups_iterate (struct perf_event_groups *groups, +perf_event_groups_iterate_f callback,void *data) +{ +int ret =0 ; +struct perf_event *event; + +WARN_ON_ONCE (!groups); + +list_for_each_entry (event, &groups->list, group_list_entry) { + ret =callback (event, data); +if (ret) +break ; + } + +/* will replace itration above in patch v5 4/4 + +for (node = rb_first(groups); node; node = rb_next(node)) { +node_event = container_of(node, struct perf_event, group_node); +list_for_each_entry(event, &node_event->group_list, kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1702
Quoted 10 lines
kernel/events/core.c +10
-0+group_list_entry) { +WARN_ON_ONCE(!(event->cpu == node_event->cpu)); +ret = callback(event, data); +if (ret) { +return ret; +} +} +} + +*/ Ditto.
Quoted 4 lines
Regards,
--
Alex
Thanks,
Alexey
Alexander Shishkin
reviewerkernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1514
Quoted 8 lines · Alexey Budankov
kernel/events/core.c +8
-0+/* +* Helper function to test if event groups are empty; +*/ +static int +perf_event_groups_empty (struct perf_event_groups *groups) +{ +return list_empty (&groups->list); +}
This doesn't seem useful, it's only used once. Also, it's not clear how access to groups->list is serialized here, but it is in the caller.
I'm assuming you will use this helper after the linked lists are done away with, but I'll have to go fishing for that patch to make sure.
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1539
Quoted 9 lines
kernel/events/core.c +9
-0+static void +perf_event_groups_insert (struct perf_event_groups *groups, +struct perf_event *event) +{ +struct rb_node **node; +struct rb_node *parent; +struct perf_event *node_event; + +WARN_ON_ONCE (!groups || !event);
I'm pretty sure neither of these is plausible.
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1540
Quoted 1 line
kernel/events/core.c +1
-0+WARN_ON_ONCE (!list_empty (&event->group_list_entry));
So ctx::lock is held here, right? That could be a useful assert and/or comment at least for review purposes. Now I see that it's called from list_add_event().
Regards,
--
Alex
Hi,
Quoted 13 lines · Alexander Shishkin
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1514
Quoted 8 lines · Alexey Budankov
kernel/events/core.c +8
-0+/* +* Helper function to test if event groups are empty; +*/ +static int +perf_event_groups_empty (struct perf_event_groups *groups) +{ +return list_empty (&groups->list); +}This doesn't seem useful, it's only used once. Also, it's not clear how access to
groups->listis serialized here, but it is in the caller.
Acepted. That API is removed in the final patch where list is replaced by rbtree.
Quoted 4 lines
I'm assuming you will use this helper after the linked lists are done away with, but I'll have to go fishing for that patch to make sure.
Quoted 11 lines
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1539
Quoted 9 lines
kernel/events/core.c +9
-0+static void +perf_event_groups_insert (struct perf_event_groups *groups, +struct perf_event *event) +{ +struct rb_node **node; +struct rb_node *parent; +struct perf_event *node_event; + +WARN_ON_ONCE (!groups || !event);I'm pretty sure neither of these is plausible.
Used that for debugging. Does it affect performance somehow?
Quoted 6 lines
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1540
Quoted 2 lines
kernel/events/core.c +1
-0+WARN_ON_ONCE (!list_empty (&event->group_list_entry));So
ctx::lockis held here, right? That could be a useful assert and/or comment at least for review purposes. Now I see that it's called fromlist_add_event().
Agree.
Quoted 5 lines
Regards,
--
Alex
Thanks,
Alexey
Alexander Shishkin
reviewerQuoted 12 lines · Alexey Budankov
Quoted 11 lines
kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1539
Quoted 9 lines
kernel/events/core.c +9
-0+static void +perf_event_groups_insert (struct perf_event_groups *groups, +struct perf_event *event) +{ +struct rb_node **node; +struct rb_node *parent; +struct perf_event *node_event; + +WARN_ON_ONCE (!groups || !event);I'm pretty sure neither of these is plausible.
Quoted 1 line
Used that for debugging.
It's a bad practice to keep leftovers of debugging code in the patches. In this particular case, as with most WARN*s that I've seen in this patchset, it is completely useless, because the code goes ahead and dereferences the pointers right after the assert, so there'd be an oops and we'd see it anyway.
Normally, you'd use these assertions if you're actually handling the undesired scenario, like
/* Can't happen because XXX */
if (WARN_ON_ONCE(!groups))
return -EINVAL;Also a comment justifying the WARN* is a good thing to have.
Quoted 1 line
Does it affect performance somehow?
It doesn't matter. Generally, we don't need an reason to remove code, we need a reason to add code.
Regards,
--
Alex