Message-ID: <20170615195618.GA8807@leverpostej>
Date:   Thu, 15 Jun 2017 20:56:18 +0100
From:   Mark Rutland <mark.rutland@....com>
To:     Alexey Budankov <alexey.budankov@...ux.intel.com>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        Ingo Molnar <mingo@...hat.com>,
        Arnaldo Carvalho de Melo <acme@...nel.org>,
        Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
        Andi Kleen <ak@...ux.intel.com>,
        Kan Liang <kan.liang@...el.com>,
        Dmitri Prokhorov <Dmitry.Prohorov@...el.com>,
        Valery Cherepennikov <valery.cherepennikov@...el.com>,
        David Carrillo-Cisneros <davidcc@...gle.com>,
        Stephane Eranian <eranian@...gle.com>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3 1/n] perf/core: addressing 4x slowdown during
 per-process profiling of STREAM benchmark on Intel Xeon Phi

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.

> 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?

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,

> 
> Signed-off-by: Alexey Budankov <alexey.budankov@...ux.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

> ---
>  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.

> +	/*
>  	 * 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.

> +
>  	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.

> +
> +	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?

I don't think this is what Peter meant when he suggested a threaded rb
tree.

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.

> +		}
> +	}
> +
> +	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?

>  	}
> 
>  	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?

Thanks,
Mark.

Powered by blists - more mailing lists