lkml.org 
[lkml]   [2017]   [Jun]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH v3 1/n] perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi
From
Date
On 16.06.2017 1:10, Alexey Budankov wrote:
> Hi,
>
> On 15.06.2017 22:56, Mark Rutland wrote:
>> Hi,
>>
>> On Thu, Jun 15, 2017 at 08:41:42PM +0300, Alexey Budankov wrote:
>>> This series of patches continues v2 and addresses captured comments.
>>
>> As a general note, please keep any change log stuff out of the commit
>> message, and mvoe that just before the diff. It generally doesn't maek
>> sense for that to go in the commit message.
>
> Accepted.
>
>>
>>> Specifically this patch replaces pinned_groups and flexible_groups
>>> lists of perf_event_context by red-black cpu indexed trees avoiding
>>> data structures duplication and introducing possibility to iterate
>>> event groups for a specific CPU only.
>>
>> If you use --per-thread, I take it the overhead is significantly
>> lowered?
>
> Please ask more.
>
>>
>> As another general thing, please aim to write the commit message so that
>> it'll make sense in N years' time, in the git history. Describe the
>> whole problem, and the intended solution.
>>
>> I had to go diving into mail archives to understand the problem you're
>> trying to solve, and I shouldn't have to.
>>
>> For example, this commit message could be something like:
>>
>> 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
>> event list and trying to schedule each in turn. We skip events whose
>> cpu filter doesn't match. So when we get unlucky, we can walk N *
>> (NR_CPUS - 1) events 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
>> sub-tree, and ignore everything else.
>>
>> As a step towards that, this patch replaces our event lists with rb
>> trees.
>> ... which hopefully makes sense now, and will in 2, 5, 10 years' time,
>>
>
> Accepted. Thanks.
>
>>>
>>> Signed-off-by: Alexey Budankov <alexey.budankov@linux.intel.com>
>>
>> Have you thrown Vince's perf fuzzer at this?
>>
>> If you haven't, please do. It can be found in the fuzzer directory of:
>>
>> https://github.com/deater/perf_event_tests
>>
>
> Accepted.

I run the test suite and it revealed no additional regressions in
comparison to what I have on the clean kernel.

However the fuzzer constantly reports some strange stacks that are not
seen on the clean kernel and I have no idea how that might be caused by
the patches.

>
>>> ---
>>> include/linux/perf_event.h | 34 +++-
>>> kernel/events/core.c | 386
>>> +++++++++++++++++++++++++++++++++------------
>>> 2 files changed, 315 insertions(+), 105 deletions(-)
>>
>> <changelog goes here>
>>
>>>
>>> diff --git a/include/linux/perf_event.h b/include/linux/perf_event.h
>>> index 24a6358..2c1dcf1 100644
>>> --- a/include/linux/perf_event.h
>>> +++ b/include/linux/perf_event.h
>>> @@ -574,6 +574,27 @@ 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;
>>> + /*
>>> + * 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 pinned or
>>> + * flexible tree;
>>> + */
>>> + struct list_head group_list_entry;
>>
>> We already have group_entry for threading the RB tree. i don't see why
>> we need two new lists heads.
>
> Ok. For a group leader event its group_entry may be used instead of new
> group_list_entry.
>
>>
>>> + /*
>>> * 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 +762,17 @@ struct perf_event_context {
>>> struct mutex mutex;
>>>
>>> struct list_head active_ctx_list;
>>> - struct list_head pinned_groups;
>>> - struct list_head flexible_groups;
>>> + /*
>>> + * RB tree for pinned groups; keeps event's group_node
>>> + * nodes of attached pinned groups;
>>> + */
>>> + struct rb_root pinned_tree;
>>> + /*
>>> + * RB tree for flexible groups; keeps event's group_node
>>> + * nodes of attached flexible groups;
>>> + */
>>> + struct rb_root flexible_tree;
>>
>> We didn't need these commesnts before, and I don't think we need them
>> now.
>>
>> Any reason not to stick with the existing names?
>>
>> The existing {pinned,flexible}_groups names are fine regardless of
>> whether a list or tree is used, and makes it clear that the elements are
>> the group leaders, not all events.
>
> Yes, makes sense. Just changing the type of data structures.
>
>>
>>> +
>>> struct list_head event_list;
>>> int nr_events;
>>> int nr_active;
>>> diff --git a/kernel/events/core.c b/kernel/events/core.c
>>> index bc63f8d..a3531f9 100644
>>> --- a/kernel/events/core.c
>>> +++ b/kernel/events/core.c
>>> @@ -1458,13 +1458,142 @@ static enum event_type_t
>>> get_event_type(struct perf_event *event)
>>> return event_type;
>>> }
>>>
>>> -static struct list_head *
>>> -ctx_group_list(struct perf_event *event, struct perf_event_context
>>> *ctx)
>>> +static struct rb_root *
>>> +ctx_group_cpu_tree(struct perf_event *event, struct
>>> perf_event_context *ctx)
>>> {
>>> if (event->attr.pinned)
>>> - return &ctx->pinned_groups;
>>> + return &ctx->pinned_tree;
>>> else
>>> - return &ctx->flexible_groups;
>>> + return &ctx->flexible_tree;
>>> +}
>>> +
>>> +/*
>>> + * Insert a group into a tree using event->cpu as a key. If
>>> event->cpu node
>>> + * is already attached to the tree then the event is added to the
>>> attached
>>> + * group's group_list list.
>>> + */
>>> +static void
>>> +perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
>>> +{
>>> + struct rb_node **node;
>>> + struct rb_node *parent;
>>> +
>>> + WARN_ON_ONCE(!tree || !event);
>>> +
>>> + node = &tree->rb_node;
>>> + parent = *node;
>>
>> The first iteration of the loop handles this, so it can go.
>
> If tree is empty parent will be uninitialized what is harmful.
>
>>
>>> +
>>> + while (*node) {
>>> + struct perf_event *node_event = container_of(*node,
>>> + struct perf_event, group_node);
>>> +
>>> + parent = *node;
>>> +
>>> + if (event->cpu < node_event->cpu) {
>>> + node = &parent->rb_left;
>>> + } else if (event->cpu > node_event->cpu) {
>>> + node = &parent->rb_right;
>>> + } else {
>>> + list_add_tail(&event->group_list_entry,
>>> + &node_event->group_list);
>>> + return;
>>
>> Why aren't we putting all group leaders into the tree?
>
> Because we index a tree by cpu only and if two groups share cpu we link
> them into the group_list of the group directly attached to the tree via
> group_node.
>
>>
>> I don't think this is what Peter meant when he suggested a threaded rb
>> tree.
>
> Yes, that's right. This implements cpu indexed rb trees with linked
> lists attached to every tree's node. The lists contain event groups
> allocated for the same cpu only.
>
>>
>> My understanding was that every group leader should be in the rb tree,
>> and every group leader should be in the same list that threads the whole
>> tree. Both the rb tree and list have to be maintained with the same
>> order.
>>
>> Thus, you can walk the rb tree to find the first event in the sub-list
>> that you care about, then walk that sub-list.
>>
>> Note that this means we need to shuffle the list and rb tree to rotate
>> events in each sub-tree.
>
> Now we also rotate a list but only containing groups for the appropriate
> cpu and we don't touch the tree.
>
>>
>>> + }
>>> + }
>>> +
>>> + list_add_tail(&event->group_list_entry, &event->group_list);
>>> +
>>> + rb_link_node(&event->group_node, parent, node);
>>> + rb_insert_color(&event->group_node, tree);
>>> +}
>>> +
>>> +/*
>>> + * Delete a group from a tree. If the group is directly attached to
>>> the tree
>>> + * it also detaches all groups on the group's group_list list.
>>> + */
>>> +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)) {
>>> + list_del_init(&event->group_list_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_list_entry)
>>> + list_del_init(&list_event->group_list_entry);
>>
>> At this point, all the other group leaders withthe same filter are gone
>> from the rb tree, since we didn't insert any of them into the rb tree in
>> place of the leader we deleted.
>> >> + }
>>> +}
>>> +
>>> +/*
>>> + * Find group_list list by a cpu key and call provided callback for
>>> every
>>> + * group on the list. Iteration stops if the callback returns non zero.
>>> + */
>>> +
>>> +typedef int (*perf_cpu_tree_callback_t)(struct perf_event *, void *);
>>> +
>>> +static int
>>> +perf_cpu_tree_iterate_cpu(struct rb_root *tree, int cpu,
>>> + perf_cpu_tree_callback_t callback, void *data)
>>> +{
>>> + int ret = 0;
>>> + struct rb_node *node;
>>> + struct perf_event *event;
>>> +
>>> + WARN_ON_ONCE(!tree);
>>> +
>>> + node = tree->rb_node;
>>> +
>>> + while (node) {
>>> + struct perf_event *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 {
>>> + list_for_each_entry(event, &node_event->group_list,
>>> + group_list_entry) {
>>> + ret = callback(event, data);
>>> + if (ret)
>>> + return ret;
>>> + }
>>> + }
>>> + }
>>> +
>>> + return 0;
>>> +}
>>> +
>>> +/*
>>> + * Iterate a tree and call provided callback for every group in the
>>> tree.
>>> + * Iteration stops if the callback returns non zero.
>>> + */
>>> +static int
>>> +perf_cpu_tree_iterate(struct rb_root *tree,
>>> + perf_cpu_tree_callback_t callback, void *data)
>>> +{
>>> + int ret = 0;
>>> + struct rb_node *node;
>>> + struct perf_event *event;
>>> +
>>> + WARN_ON_ONCE(!tree);
>>> +
>>> + for (node = rb_first(tree); node; node = rb_next(node)) {
>>> + struct perf_event *node_event = container_of(node,
>>> + struct perf_event, group_node);
>>> +
>>> + list_for_each_entry(event, &node_event->group_list,
>>> + group_list_entry) {
>>> + ret = callback(event, data);
>>> + if (ret)
>>> + return ret;
>>> + }
>>> + }
>>> +
>>> + return 0;
>>> }
>>
>> If you need to iterate over every event, you can use the list that
>> threads the whole tree.
>>
>>>
>>> /*
>>> @@ -1485,12 +1614,12 @@ list_add_event(struct perf_event *event,
>>> struct perf_event_context *ctx)
>>> * perf_group_detach can, at all times, locate all siblings.
>>> */
>>> if (event->group_leader == event) {
>>> - struct list_head *list;
>>> + struct rb_root *tree;
>>>
>>> event->group_caps = event->event_caps;
>>>
>>> - list = ctx_group_list(event, ctx);
>>> - list_add_tail(&event->group_entry, list);
>>> + tree = ctx_group_cpu_tree(event, ctx);
>>> + perf_cpu_tree_insert(tree, event);
>>
>> Can we wrap this in a helper so that finds the sub-tree and performs
>> the insert?
>
> Ok. add_to_groups().
>
>>
>>> }
>>>
>>> list_update_cgroup_event(event, ctx, true);
>>> @@ -1680,8 +1809,12 @@ list_del_event(struct perf_event *event,
>>> struct perf_event_context *ctx)
>>>
>>> list_del_rcu(&event->event_entry);
>>>
>>> - if (event->group_leader == event)
>>> - list_del_init(&event->group_entry);
>>> + if (event->group_leader == event) {
>>> + struct rb_root *tree;
>>> +
>>> + tree = ctx_group_cpu_tree(event, ctx);
>>> + perf_cpu_tree_delete(tree, event);
>>
>> ... likewise?
>
> Ok. del_from_groups().
>
>>
>> Thanks,
>> Mark.
>>
>
> Thanks,
> Alexey
>

\
 
 \ /
  Last update: 2017-06-19 15:08    [W:0.279 / U:1.036 seconds]
©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site