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, 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(-)

1. introduced group_node, group_list, group_list_entry into perf_event type;

2. introduced perf_event_groups type for pinned and flexible groups; new type objects combine rb tree and list for safe whole tree iterations;

3. introduced new functions:

get_event_groups()
add_event_to_groups()
del_event_from_groups()

perf_event_groups_empty()
perf_event_groups_init()
perf_event_groups_insert()
perf_event_groups_delete()
perf_event_groups_rotate(..., int cpu)
perf_event_groups_iterate_cpu(..., int cpu)
perf_event_groups_iterate()

struct group_sched_params; group_sched_out_callback(, struct group_sched_params*)

struct inherit_task_group_params; inherit_task_group_callback(, struct inherit_task_group_params*)

see comments in the patch for more details;

4. removed functions:

ctx_group_list()

5. functions changed to adopt new API:

perf_event_alloc(),
perf_event_init_context(),
__perf_event_init_context(),
list_add_event(),
list_del_event(),
ctx_sched_in(),
ctx_sched_out(),
perf_event_context_sched_in(),
inherit_task_group(),
rotate_ctx(),
ctx_pinned_sched_in(),
ctx_flexible_sched_in()

index 24a6358..dcedfd7 100644
@@ -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;