: perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi

Solution:

cpu indexed trees for perf_event_context::pinned_groups and perf_event_context::flexible_groups lists are introduced. Every tree node keeps a list of groups allocated for the same cpu. A tree references only groups located at the appropriate group list. The tree provides capability to iterate over groups allocated for a specific cpu only, what is exactly required by multiplexing timer interrupt handler. The handler runs per-cpu and enables/disables groups using group_sched_in()/group_sched_out() that call event_filter_match() function filtering out groups allocated for cpus different from the one executing the handler. Additionally for every filtered out group group_sched_out() updates tstamps values to the current interrupt time. This updating work is now done only once by update_context_time() called by ctx_sched_out() before cpu groups iteration. For this trick to work it is required that tstamps of filtered out events would point to perf_event_context::tstamp_data object instead of perf_event::tstamp_data ones, as it is initialized from an event allocation. tstamps references are switched by group_sched_in()/group_sched_out() every time a group is checked for its suitability for currently running cpu. When a thread enters some cpu on a context switch a long run through pinned and flexible groups is performed by perf_event_sched_in(, mux=0) with new parameter mux set to 0

and filtered out groups tstamps are switched to perf_event_context::tstamp_data object. Then a series of multiplexing interrupts happens and the handler rotates the flexible groups calling ctx_sched_out(,mux=1)/perf_event_sched_in(,mux=1) iterating over the cpu tree lists only and avoiding long runs through the complete group lists. This is where speedup comes from. Eventually when the thread leaves the cpu ctx_sched_out(,mux=0) is called restoring tstamps pointers to the events' perf_event::tstamp_data objects.

Added API:

Objects:
1. struct perf_event_tstamp:
- enabled
- running
- stopped
2. struct perf_event:
- group_node
- group_list
- group_list_entry
- tstamp
- tstamp_data
3. struct perf_event_context:
- pinned_tree
- flexible_tree
- tstamp_data

Functions:
1. insert a group into a tree using event->cpu as a key:

	int perf_cpu_tree_insert(struct rb_root *tree,
		struct perf_event *event);
2. delete a group from a tree, if the group is directly attached
   to a tree it also detaches all groups on the groups
   group_list list:
	int perf_cpu_tree_delete(struct rb_root *tree,
		struct perf_event *event);

3. find group_list list by a cpu key:
struct list_head * perf_cpu_tree_find(struct rb_root *tree,
int cpu);
4. enable a pinned group on a cpu:
void ctx_sched_in_flexible_group(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct perf_event *group, int *can_add_hw);
5. enable a flexible group on a cpu; calls ctx_sched_in_flexible_group and updates group->state to ERROR in case of failure:
void ctx_sched_in_pinned_group(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct perf_event *group);
6. enable per-cpu pinned tree's groups on a cpu:
void ctx_pinned_sched_in_groups(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct list_head *groups);
7. enable per-cpu flexible tree's groups on a cpu:

	void ctx_flexible_sched_in_groups(
		struct perf_event_context *ctx,
		struct perf_cpu_context *cpuctx,
		struct list_head *groups);

8. disable per-cpu tree's groups on a cpu:
void ctx_sched_out_groups(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct list_head *groups);
9. get a group tree based on event->attr.pinned attribute value:

	struct rb_root * ctx_cpu_tree(struct perf_event *event,
		struct perf_event_context *ctx);

Modified API:

Objects:
1. struct perf_event
2. struct perf_event_context

Functions:
1. perf_event_alloc()
2. add_event_to_ctx()
3. perf_event_enable_on_exec()
4. __perf_install_in_context()
5. __perf_event_init_context()
6. __perf_event_mark_enabled()
7. __perf_event_enable()
8. __perf_event_task_sched_out()
9. ctx_group_list()
10. list_add_event()
11. list_del_event()
12. perf_event_context_sched_in()
13. cpu_ctx_sched_in()
14. cpu_ctx_sched_out()
15. ctx_sched_in()
16. ctx_sched_out()
17. ctx_resched()
18. ctx_pinned_sched_in()
19. ctx_flexible_sched_in()
20. group_sched_in()
21. event_sched_in()

22. event_sched_out()
23. rotate_ctx()
24. perf_rotate_context()
25. update_context_time()
26. update_event_times()
27. calc_timer_values()
28. perf_cgroup_switch()
29. perf_cgroup_mark_enabled()

Quoted 22 lines · Alexey Budankov

Solution:

cpu indexed trees for perf_event_context::pinned_groups and perf_event_context::flexible_groups lists are introduced. Every tree node keeps a list of groups allocated for the same cpu. A tree references only groups located at the appropriate group list. The tree provides capability to iterate over groups allocated for a specific cpu only, what is exactly required by multiplexing timer interrupt handler. The handler runs per-cpu and enables/disables groups using group_sched_in()/group_sched_out() that call event_filter_match() function filtering out groups allocated for cpus different from the one executing the handler. Additionally for every filtered out group group_sched_out() updates tstamps values to the current interrupt time. This updating work is now done only once by update_context_time() called by ctx_sched_out() before cpu groups iteration. For this trick to work it is required that tstamps of filtered out events would point to perf_event_context::tstamp_data object instead of perf_event::tstamp_data ones, as it is initialized from an event allocation. tstamps references are switched by group_sched_in()/group_sched_out() every time a group is checked for its suitability for currently running cpu. When a thread enters some cpu on a context switch a long run through pinned and flexible groups is performed by perf_event_sched_in(, mux=0) with new parameter mux set to 0

Quoted 8 lines

and filtered out groups tstamps are switched to perf_event_context::tstamp_data object. Then a series of multiplexing interrupts happens and the handler rotates the flexible groups calling ctx_sched_out(,mux=1)/perf_event_sched_in(,mux=1) iterating over the cpu tree lists only and avoiding long runs through the complete group lists. This is where speedup comes from. Eventually when the thread leaves the cpu ctx_sched_out(,mux=0) is called restoring tstamps pointers to the events' perf_event::tstamp_data objects.

This is unreadable.. Please use whitespace.

Quoted 86 lines

Added API:

Objects:
1. struct perf_event_tstamp:
- enabled
- running
- stopped
2. struct perf_event:
- group_node
- group_list
- group_list_entry
- tstamp
- tstamp_data
3. struct perf_event_context:
- pinned_tree
- flexible_tree
- tstamp_data

Functions:
1. insert a group into a tree using event->cpu as a key:

	int perf_cpu_tree_insert(struct rb_root *tree,
		struct perf_event *event);

2. delete a group from a tree, if the group is directly attached to a tree it also detaches all groups on the groups group_list list:
int perf_cpu_tree_delete(struct rb_root *tree,
struct perf_event *event);
3. find group_list list by a cpu key:
struct list_head * perf_cpu_tree_find(struct rb_root *tree,
int cpu);
4. enable a pinned group on a cpu:
void ctx_sched_in_flexible_group(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct perf_event *group, int *can_add_hw);
5. enable a flexible group on a cpu; calls ctx_sched_in_flexible_group and updates group->state to ERROR in case of failure:
void ctx_sched_in_pinned_group(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct perf_event *group);
6. enable per-cpu pinned tree's groups on a cpu:
void ctx_pinned_sched_in_groups(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct list_head *groups);
7. enable per-cpu flexible tree's groups on a cpu:

	void ctx_flexible_sched_in_groups(
		struct perf_event_context *ctx,
		struct perf_cpu_context *cpuctx,
		struct list_head *groups);

8. disable per-cpu tree's groups on a cpu:
void ctx_sched_out_groups(struct perf_event_context *ctx,
struct perf_cpu_context *cpuctx,
struct list_head *groups);
9. get a group tree based on event->attr.pinned attribute value:

	struct rb_root * ctx_cpu_tree(struct perf_event *event,
		struct perf_event_context *ctx);

Modified API:

Objects:
1. struct perf_event
2. struct perf_event_context

Functions:
1. perf_event_alloc()
2. add_event_to_ctx()
3. perf_event_enable_on_exec()
4. __perf_install_in_context()
5. __perf_event_init_context()
6. __perf_event_mark_enabled()
7. __perf_event_enable()
8. __perf_event_task_sched_out()
9. ctx_group_list()
10. list_add_event()
11. list_del_event()
12. perf_event_context_sched_in()
13. cpu_ctx_sched_in()
14. cpu_ctx_sched_out()
15. ctx_sched_in()
16. ctx_sched_out()
17. ctx_resched()
18. ctx_pinned_sched_in()
19. ctx_flexible_sched_in()
20. group_sched_in()
21. event_sched_in()

Quoted 8 lines

22. event_sched_out()
23. rotate_ctx()
24. perf_rotate_context()
25. update_context_time()
26. update_event_times()
27. calc_timer_values()
28. perf_cgroup_switch()
29. perf_cgroup_mark_enabled()

Yeah, this doesn't go into a changelog. Have you _ever_ seen a changelog with such crud in?

Quoted 32 lines · Peter Zijlstra

Quoted 30 lines · Alexey Budankov

Solution:

cpu indexed trees for perf_event_context::pinned_groups and perf_event_context::flexible_groups lists are introduced. Every tree node keeps a list of groups allocated for the same cpu. A tree references only groups located at the appropriate group list. The tree provides capability to iterate over groups allocated for a specific cpu only, what is exactly required by multiplexing timer interrupt handler. The handler runs per-cpu and enables/disables groups using group_sched_in()/group_sched_out() that call event_filter_match() function filtering out groups allocated for cpus different from the one executing the handler. Additionally for every filtered out group group_sched_out() updates tstamps values to the current interrupt time. This updating work is now done only once by update_context_time() called by ctx_sched_out() before cpu groups iteration. For this trick to work it is required that tstamps of filtered out events would point to perf_event_context::tstamp_data object instead of perf_event::tstamp_data ones, as it is initialized from an event allocation. tstamps references are switched by group_sched_in()/group_sched_out() every time a group is checked for its suitability for currently running cpu. When a thread enters some cpu on a context switch a long run through pinned and flexible groups is performed by perf_event_sched_in(, mux=0) with new parameter mux set to 0 and filtered out groups tstamps are switched to perf_event_context::tstamp_data object. Then a series of multiplexing interrupts happens and the handler rotates the flexible groups calling ctx_sched_out(,mux=1)/perf_event_sched_in(,mux=1) iterating over the cpu tree lists only and avoiding long runs through the complete group lists. This is where speedup comes from. Eventually when the thread leaves the cpu ctx_sched_out(,mux=0) is called restoring tstamps pointers to the events' perf_event::tstamp_data objects.

Quoted 1 line

This is unreadable.. Please use whitespace.

Do you mean do NOT use whitespaces? Could you explain in more detail what you mean?

Quoted 3 lines

Yeah, this doesn't go into a changelog. Have you _ever_ seen a changelog with such crud in?

I have not. Could you please advise how to format this information to be suitable for changelog, if it's required at all?

Quoted 33 lines · Alexey Budankov

Quoted 32 lines · Peter Zijlstra

Quoted 30 lines · Alexey Budankov

Solution:

cpu indexed trees for perf_event_context::pinned_groups and perf_event_context::flexible_groups lists are introduced. Every tree node keeps a list of groups allocated for the same cpu. A tree references only groups located at the appropriate group list. The tree provides capability to iterate over groups allocated for a specific cpu only, what is exactly required by multiplexing timer interrupt handler. The handler runs per-cpu and enables/disables groups using group_sched_in()/group_sched_out() that call event_filter_match() function filtering out groups allocated for cpus different from the one executing the handler. Additionally for every filtered out group group_sched_out() updates tstamps values to the current interrupt time. This updating work is now done only once by update_context_time() called by ctx_sched_out() before cpu groups iteration. For this trick to work it is required that tstamps of filtered out events would point to perf_event_context::tstamp_data object instead of perf_event::tstamp_data ones, as it is initialized from an event allocation. tstamps references are switched by group_sched_in()/group_sched_out() every time a group is checked for its suitability for currently running cpu. When a thread enters some cpu on a context switch a long run through pinned and flexible groups is performed by perf_event_sched_in(, mux=0) with new parameter mux set to 0 and filtered out groups tstamps are switched to perf_event_context::tstamp_data object. Then a series of multiplexing interrupts happens and the handler rotates the flexible groups calling ctx_sched_out(,mux=1)/perf_event_sched_in(,mux=1) iterating over the cpu tree lists only and avoiding long runs through the complete group lists. This is where speedup comes from. Eventually when the thread leaves the cpu ctx_sched_out(,mux=0) is called restoring tstamps pointers to the events' perf_event::tstamp_data objects.

Quoted 4 lines

Quoted 1 line

This is unreadable.. Please use whitespace.

Do you mean do NOT use whitespaces? Could you explain in more detail what you mean?

No, add _more_ whitespace. Use things like paragraphs and such. Reading a massive blob of text like that is painful. Also use full and complete sentences. For example, the very first sentence:

'cpu indexed trees for perf_event_context::pinned_groups and perf_event_context::flexible_groups lists are introduced.'

feels incomplete and leaves one wondering what for etc.. And it only gets worse.

Quoted 7 lines

Quoted 4 lines

Yeah, this doesn't go into a changelog. Have you _ever_ seen a changelog with such crud in?

I have not. Could you please advise how to format this information to be suitable for changelog, if it's required at all?

Don't include it. It should be fairly obvious from the diff itself what changed after all.

include/linux/perf_event.h +31 -0

@@ -571,6 +587,27 @@ struct perf_event {
 	 * either sufficies for read.
 	 */
 	struct list_head		group_entry;
+	/*
+	 * 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;
 	struct list_head		sibling_list;
 
 	/*

@@ -742,7 +772,17 @@ struct perf_event_context {
 
 	struct list_head		active_ctx_list;
 	struct list_head		pinned_groups;
+	/*
+	 * Cpu tree for pinned groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			pinned_tree;
 	struct list_head		flexible_groups;
+	/*
+	 * Cpu tree for flexible groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			flexible_tree;
 	struct list_head		event_list;
 	int				nr_events;
 	int				nr_active;

Quoted 53 lines · Alexey Budankov

include/linux/perf_event.h +32 -0

@@ -571,6 +587,27 @@ struct perf_event {
  	 * either sufficies for read.
  	 */
  	struct list_head		group_entry;
+	/*
+	 * 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;
  	struct list_head		sibling_list;
 
  	/*

@@ -742,7 +772,17 @@ struct perf_event_context {
 
  	struct list_head		active_ctx_list;
  	struct list_head		pinned_groups;
+	/*
+	 * Cpu tree for pinned groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			pinned_tree;
  	struct list_head		flexible_groups;
+	/*
+	 * Cpu tree for flexible groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			flexible_tree;
  	struct list_head		event_list;
  	int				nr_events;
  	int				nr_active;

@@ -758,6 +798,7 @@ struct perf_event_context {
  	 */
  	u64				time;
  	u64				timestamp;
+	struct perf_event_tstamp	tstamp_data;
 

include/linux/perf_event.h struct perf_event_context { · line 804

Quoted 2 lines

include/linux/perf_event.h +0 -0

  	/*
  	 * These fields let us detect when two contexts have both

So why do we now have a list _and_ a tree for the same entries?

Quoted 26 lines · Peter Zijlstra

Quoted 24 lines · Alexey Budankov

include/linux/perf_event.h +11 -0

@@ -742,7 +772,17 @@ struct perf_event_context {
 
  	struct list_head		active_ctx_list;
  	struct list_head		pinned_groups;
+	/*
+	 * Cpu tree for pinned groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			pinned_tree;
  	struct list_head		flexible_groups;
+	/*
+	 * Cpu tree for flexible groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			flexible_tree;
  	struct list_head		event_list;
  	int				nr_events;
  	int				nr_active;

@@ -758,6 +798,7 @@ struct perf_event_context {
  	 */
  	u64				time;
  	u64				timestamp;
+	struct perf_event_tstamp	tstamp_data;
 

Quoted 5 lines

include/linux/perf_event.h struct perf_event_context { · line 804

Quoted 2 lines

include/linux/perf_event.h +0 -0

  	/*
  	 * These fields let us detect when two contexts have both

So why do we now have a list _and_ a tree for the same entries?

We need groups list to iterate through all groups configured for collection and we need the tree to quickly iterate through the groups allocated for a particular CPU only.

Quoted 32 lines · Alexey Budankov

Quoted 31 lines · Peter Zijlstra

Quoted 19 lines · Alexey Budankov

include/linux/perf_event.h +10 -0

@@ -742,7 +772,17 @@ struct perf_event_context {
 
   	struct list_head		active_ctx_list;
   	struct list_head		pinned_groups;
+	/*
+	 * Cpu tree for pinned groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			pinned_tree;
   	struct list_head		flexible_groups;
+	/*
+	 * Cpu tree for flexible groups; keeps event's group_node nodes
+	 * of attached flexible groups;
+	 */
+	struct rb_root			flexible_tree;
   	struct list_head		event_list;
   	int				nr_events;
   	int				nr_active;

include/linux/perf_event.h struct perf_event_context { · line 804

Quoted 7 lines

include/linux/perf_event.h +1 -0

@@ -758,6 +798,7 @@ struct perf_event_context {
   	 */
   	u64				time;
   	u64				timestamp;
+	struct perf_event_tstamp	tstamp_data;
 
   	/*
   	 * These fields let us detect when two contexts have both

So why do we now have a list _and_ a tree for the same entries?

Quoted 3 lines

We need groups list to iterate through all groups configured for collection and we need the tree to quickly iterate through the groups allocated for a particular CPU only.

*confused*, what?

Why can't the tree do both?

Quoted 2 lines · Peter Zijlstra

Why can't the tree do both?

Well, indeed, the tree provides such capability too. However switching to the full tree iteration in cases where we now go through _groups lists will enlarge the patch, what is probably is not a big deal. Do you think it is worth implementing the switch?

Quoted 5 lines · Alexey Budankov

Quoted 2 lines · Peter Zijlstra

Why can't the tree do both?

Quoted 4 lines

Well, indeed, the tree provides such capability too. However switching to the full tree iteration in cases where we now go through _groups lists will enlarge the patch, what is probably is not a big deal. Do you think it is worth implementing the switch?

Do it as a series of patches, where patch 1 introduces the tree, patches 2 through n convert the list users into tree users, and patch n+1 removes the list.

I think its good to not have duplicate data structures if we can avoid it.

Quoted 11 lines · Peter Zijlstra

Quoted 9 lines · Alexey Budankov

Quoted 2 lines · Peter Zijlstra

Why can't the tree do both?

Well, indeed, the tree provides such capability too. However switching to the full tree iteration in cases where we now go through _groups lists will enlarge the patch, what is probably is not a big deal. Do you think it is worth implementing the switch?

Quoted 3 lines

Do it as a series of patches, where patch 1 introduces the tree, patches 2 through n convert the list users into tree users, and patch n+1 removes the list.

Well ok, let's do that additionally but please expect delay in delivery (I am OOO till Jun 14).

Quoted 5 lines

I think its good to not have duplicate data structures if we can avoid it.

yeah, makes sense.

Quoted 12 lines · Alexey Budankov

Quoted 11 lines · Peter Zijlstra

Quoted 9 lines · Alexey Budankov

Quoted 2 lines · Peter Zijlstra

Why can't the tree do both?

Well, indeed, the tree provides such capability too. However switching to the full tree iteration in cases where we now go through _groups lists will enlarge the patch, what is probably is not a big deal. Do you think it is worth implementing the switch?

Quoted 5 lines

Quoted 3 lines

Do it as a series of patches, where patch 1 introduces the tree, patches 2 through n convert the list users into tree users, and patch n+1 removes the list.

Well ok, let's do that additionally but please expect delay in delivery (I am OOO till Jun 14).

addressed in v3.

Quoted 10 lines

Quoted 5 lines

I think its good to not have duplicate data structures if we can avoid it.

yeah, makes sense.

Hi,

Quoted 13 lines · Alexey Budankov

Quoted 12 lines · Alexey Budankov

Quoted 11 lines · Peter Zijlstra

Quoted 9 lines · Alexey Budankov

Quoted 2 lines · Peter Zijlstra

Why can't the tree do both?

Well, indeed, the tree provides such capability too. However switching to the full tree iteration in cases where we now go through _groups lists will enlarge the patch, what is probably is not a big deal. Do you think it is worth implementing the switch?

Quoted 20 lines

Quoted 5 lines

Quoted 3 lines

Do it as a series of patches, where patch 1 introduces the tree, patches 2 through n convert the list users into tree users, and patch n+1 removes the list.

Well ok, let's do that additionally but please expect delay in delivery (I am OOO till Jun 14).

addressed in v3.

Quoted 10 lines

Quoted 5 lines

I think its good to not have duplicate data structures if we can avoid it.

yeah, makes sense.

After straightforward switch from struct list_head to struct rb_tree for flexible_groups I now get dmesg dumps on rb tree corruptions. That happens when iterating thru tree instead of thru list. No additional synchronization for the tree access was added. It looks like there are
some assumptions on the list_head type in the implementation itself.

Are there any ideas on why that corruptions may happen?

I still suggest isolating event groups into a separate object (please see patch v4-1/4):

struct perf_event_groups {
    struct rb_root     tree;
    struct list_head list;
};

struct perf_event_context {
...
struct perf_event_groups pinned_groups;
struct perf_event_groups flexible_groups;

and implementing new API for the object:

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

so that perf_event_groups_iterate() would go thru list but leaving the opportunity of iteration thru tree for a separate patch because complete transition to rb trees may incur synchronization overhead in runtime.

Thanks,
Alexey

Motivation:

The issue manifests like 4x slowdown when profiling single thread STREAM benchmark on Intel Xeon Phi running RHEL7.2 (Intel MPSS distribution). Perf profiling is done in per-process mode and involves about 30 core events. In case the benchmark is OpenMP based and runs under profiling in 272 threads the overhead becomes even more dramatic: 512.144s against 36.192s (with this patch).

different from the one executing the handler. Additionally for every filtered out group group_sched_out() updates tstamps values to the current interrupt time. This updating work is now done only once by update_context_time() called by ctx_sched_out() before cpu groups iteration.

static u64 perf_event_time(struct perf_event *event)

kernel/events/core.c +1 -2

@@ -1424,16 +1428,16 @@ static void update_event_times(struct perf_event
 *event)
        else if (ctx->is_active)
                run_end = ctx->time;
        else
-               run_end = event->tstamp_stopped;
+               run_end = event->tstamp->stopped;
 
-       event->total_time_enabled = run_end - event->tstamp_enabled;

kernel/events/core.c +2 -2

 }

@@ -3051,9 +3277,9 @@ void __perf_event_task_sched_out(struct task_struct
 *task,
  * Called with IRQs disabled
  */
 static void cpu_ctx_sched_out(struct perf_cpu_context *cpuctx,
-                             enum event_type_t event_type)
+                             enum event_type_t event_type, int mux)
 {
-       ctx_sched_out(&cpuctx->ctx, cpuctx, event_type);
+       ctx_sched_out(&cpuctx->ctx, cpuctx, event_type, mux);
 }
 

static void

kernel/events/core.c +2 -18

-
-               /* may need to reset tstamp_enabled */
-               if (is_cgroup_event(event))
-                       perf_cgroup_mark_enabled(event, ctx);
-
-               if (group_can_go_on(event, cpuctx, 1))
-                       group_sched_in(event, cpuctx, ctx);
-
-               /*
-                * If this pinned group hasn't been scheduled,
-                * put it in error state.
-                */
-               if (event->state == PERF_EVENT_STATE_INACTIVE) {
-                       update_group_times(event);
-                       event->state = PERF_EVENT_STATE_ERROR;
-               }
-       }
+       list_for_each_entry(event, &ctx->pinned_groups, group_entry)
+               ctx_sched_in_pinned_group(ctx, cpuctx, event);
 }
 
 static void

@@ -3092,37 +3297,19 @@ ctx_flexible_sched_in(struct perf_event_context
 *ctx,
 {
        struct perf_event *event;
        int can_add_hw = 1;
-

Quoted 8 lines · Alexey Budankov

Motivation:

The issue manifests like 4x slowdown when profiling single thread STREAM benchmark on Intel Xeon Phi running RHEL7.2 (Intel MPSS distribution). Perf profiling is done in per-process mode and involves about 30 core events. In case the benchmark is OpenMP based and runs under profiling in 272 threads the overhead becomes even more dramatic: 512.144s against 36.192s (with this patch).

How long does it take without any perf monitoring? Could you provide more details about the benchmark? how many CPUs are being monitored?

SNIP

Quoted 5 lines

different from the one executing the handler. Additionally for every filtered out group group_sched_out() updates tstamps values to the current interrupt time. This updating work is now done only once by update_context_time() called by ctx_sched_out() before cpu groups iteration.

I don't see this. e.g.:

in your patch task_ctx_sched_out calls ctx_sched_out with mux == 0, that path does the exact same thing as before your patch. > I understand why you want to move the event's times to a different structure and keep a pointer in the event, but I don't see that you are avoiding the update of the times of unscheduled events.

Quoted 11 lines

static u64 perf_event_time(struct perf_event *event)

kernel/events/core.c +1 -2

@@ -1424,16 +1428,16 @@ static void update_event_times(struct perf_event
 *event)
         else if (ctx->is_active)
                 run_end = ctx->time;
         else
-               run_end = event->tstamp_stopped;
+               run_end = event->tstamp->stopped;
 
-       event->total_time_enabled = run_end - event->tstamp_enabled;

kernel/events/core.c static void update_event_times(struct perf_event · line 1441

Quoted 10 lines

kernel/events/core.c +3 -2

+       event->total_time_enabled = run_end - event->tstamp->enabled;
 
         if (event->state == PERF_EVENT_STATE_INACTIVE)
-               run_end = event->tstamp_stopped;
+               run_end = event->tstamp->stopped;
         else
                 run_end = perf_event_time(event);
 
-       event->total_time_running = run_end - event->tstamp_running;
+       event->total_time_running = run_end - event->tstamp->running;

FWICT, this is run for ALL events in context with matching CPU.

SNIP

Quoted 13 lines

kernel/events/core.c +2 -2

  }

@@ -3051,9 +3277,9 @@ void __perf_event_task_sched_out(struct task_struct
 *task,
   * Called with IRQs disabled
   */
  static void cpu_ctx_sched_out(struct perf_cpu_context *cpuctx,
-                             enum event_type_t event_type)
+                             enum event_type_t event_type, int mux)
  {
-       ctx_sched_out(&cpuctx->ctx, cpuctx, event_type);
+       ctx_sched_out(&cpuctx->ctx, cpuctx, event_type, mux);
  }
 

kernel/events/core.c ctx_pinned_sched_in(struct perf_event_context *ctx, · line 3069

Quoted 11 lines

static void

kernel/events/core.c +0 -6

@@ -3061,29 +3287,8 @@ ctx_pinned_sched_in(struct perf_event_context *ctx,
                     struct perf_cpu_context *cpuctx)
  {
         struct perf_event *event;
-
-       list_for_each_entry(event, &ctx->pinned_groups, group_entry) {
-               if (event->state <= PERF_EVENT_STATE_OFF)
-                       continue;
-               if (!event_filter_match(event))
-                       continue;

Could we remove or simplify the tests in event_filter_match since the rb-tree filters by cpu?

Quoted 29 lines

kernel/events/core.c +2 -18

-
-               /* may need to reset tstamp_enabled */
-               if (is_cgroup_event(event))
-                       perf_cgroup_mark_enabled(event, ctx);
-
-               if (group_can_go_on(event, cpuctx, 1))
-                       group_sched_in(event, cpuctx, ctx);
-
-               /*
-                * If this pinned group hasn't been scheduled,
-                * put it in error state.
-                */
-               if (event->state == PERF_EVENT_STATE_INACTIVE) {
-                       update_group_times(event);
-                       event->state = PERF_EVENT_STATE_ERROR;
-               }
-       }
+       list_for_each_entry(event, &ctx->pinned_groups, group_entry)
+               ctx_sched_in_pinned_group(ctx, cpuctx, event);
  }
 
  static void

@@ -3092,37 +3297,19 @@ ctx_flexible_sched_in(struct perf_event_context
 *ctx,
  {
         struct perf_event *event;
         int can_add_hw = 1;
-

kernel/events/core.c ctx_flexible_sched_in(struct perf_event_context · line 3106

Quoted 10 lines

kernel/events/core.c +0 -10

-       list_for_each_entry(event, &ctx->flexible_groups, group_entry) {
-               /* Ignore events in OFF or ERROR state */
-               if (event->state <= PERF_EVENT_STATE_OFF)
-                       continue;
-               /*
-                * Listen to the 'cpu' scheduling filter constraint
-                * of events:
-                */
-               if (!event_filter_match(event))
-                       continue;

same as before.

Alexey Budankov <[email protected]> writes:

Here (above the function) you could include a comment describing what happens when this is called, locking considerations, etc.

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1486

Quoted 9 lines

kernel/events/core.c +8 -0

+static int
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+	struct rb_node **node;
+	struct rb_node *parent;
+
+	if (!tree || !event)
+		return 0;

I don't think this should be happening, should it? And either way you probably don't want to return 0 here, unless you're using !0 for success.

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1498

Quoted 13 lines

kernel/events/core.c +12 -0

+
+	node = &tree->rb_node;
+	parent = *node;
+
+	while (*node) {
+		struct perf_event *node_event =	container_of(*node,
+				struct perf_event, group_node);
+
+		parent = *node;
+
+		if (event->cpu < node_event->cpu) {
+			node = &((*node)->rb_left);

this would be the same as node = &parent->rb_left, right?

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 6 lines

kernel/events/core.c +5 -0

+		} else if (event->cpu > node_event->cpu) {
+			node = &((*node)->rb_right);
+		} else {
+			list_add_tail(&event->group_list_entry,
+					&node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Also,

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1504

Quoted 1 line

kernel/events/core.c +1 -0

+			return 2;

2?

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1513

Quoted 10 lines

kernel/events/core.c +9 -0

+		}
+	}
+
+	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);
+
+	return 1;

Oh, you are using !0 for success. I guess it's a good thing you're not actually checking its return code at the call site.

Regards,
--
Alex

Quoted 10 lines · Alexander Shishkin

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 5 lines · Alexey Budankov

kernel/events/core.c +5 -0

+		} else if (event->cpu > node_event->cpu) {
+			node = &((*node)->rb_right);
+		} else {
+			list_add_tail(&event->group_list_entry,
+					&node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Good question. Choice of data structure and layout depends on the operations applied to the data so keeping groups as a tree simplifies and improves the implementation in terms of scalability and performance. Please ask more if any.

Quoted 12 lines · Alexey Budankov

Quoted 10 lines · Alexander Shishkin

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 5 lines · Alexey Budankov

kernel/events/core.c +5 -0

+		} else if (event->cpu > node_event->cpu) {
+			node = &((*node)->rb_right);
+		} else {
+			list_add_tail(&event->group_list_entry,
+					&node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Quoted 4 lines

Good question. Choice of data structure and layout depends on the operations applied to the data so keeping groups as a tree simplifies and improves the implementation in terms of scalability and performance. Please ask more if any.

Since these lists are per context, and each task can have a context, you'd end up with per-task-per-cpu memory, which is something we'd like to avoid (some archs have very limited per-cpu memory space etc..).

Also, we'd like to have that tree for other reasons, like for instance that heterogeneous PMU crud ARM has. Also, with a tree we can easier do time based round-robin scheduling,

Quoted 13 lines · Peter Zijlstra

Quoted 12 lines · Alexey Budankov

Quoted 10 lines · Alexander Shishkin

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 5 lines · Alexey Budankov

kernel/events/core.c +5 -0

+		} else if (event->cpu > node_event->cpu) {
+			node = &((*node)->rb_right);
+		} else {
+			list_add_tail(&event->group_list_entry,
+					&node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Quoted 8 lines

Quoted 4 lines

Good question. Choice of data structure and layout depends on the operations applied to the data so keeping groups as a tree simplifies and improves the implementation in terms of scalability and performance. Please ask more if any.

Since these lists are per context, and each task can have a context, you'd end up with per-task-per-cpu memory, which is something we'd like to avoid (some archs have very limited per-cpu memory space etc..).

Quoted 5 lines

Also, we'd like to have that tree for other reasons, like for instance that heterogeneous PMU crud ARM has. Also, with a tree we can easier do time based round-robin scheduling,

Oh and in general multi-PMU stuff, aside from hetero PMU becomes much easier.

Quoted 4 lines · Alexander Shishkin

Alexey Budankov <[email protected]> writes:

Here (above the function) you could include a comment describing what happens when this is called, locking considerations, etc.

I can put the short description from the initial thread message here. Would it be sufficient?

Quoted 14 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1486

Quoted 10 lines

kernel/events/core.c +8 -0

+static int
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+	struct rb_node **node;
+	struct rb_node *parent;
+
+	if (!tree || !event)
+		return 0;

I don't think this should be happening, should it? And either way you probably don't want to return 0 here, unless you're using !0 for success.

As you might notice already, currently return codes of the tree API are not checked all other the implementation. I suggest replacing that int error code by void and simplify the stuff.

Quoted 16 lines

Quoted 4 lines

kernel/events/core.c +2 -0

+
+	node = &tree->rb_node;

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1498

Quoted 10 lines

kernel/events/core.c +10 -0

+	parent = *node;
+
+	while (*node) {
+		struct perf_event *node_event =	container_of(*node,
+				struct perf_event, group_node);
+
+		parent = *node;
+
+		if (event->cpu < node_event->cpu) {
+			node = &((*node)->rb_left);

this would be the same as node = &parent->rb_left, right?

Please ask more.

node is the leaf node and parent is the parent of the
node at the end of cycle. We need the both to insert a new node into a tree.

Quoted 10 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 7 lines

kernel/events/core.c +5 -0

+		} else if (event->cpu > node_event->cpu) {
+			node = &((*node)->rb_right);
+		} else {
+			list_add_tail(&event->group_list_entry,
+					&node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Good question. Choice of data structure and layout depends on the operations applied to the data so keeping groups as a tree simplifies and improves the implementation in terms of scalability and performance. Please ask more if any.

Quoted 8 lines · Alexey Budankov

Quoted 4 lines · Alexander Shishkin

Alexey Budankov <[email protected]> writes:

Here (above the function) you could include a comment describing what happens when this is called, locking considerations, etc.

I can put the short description from the initial thread message here. Would it be sufficient?

Sure, this is where API descriptions fit better than in commit messages.

Quoted 15 lines

Quoted 14 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1486

Quoted 10 lines

kernel/events/core.c +8 -0

+static int
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+	struct rb_node **node;
+	struct rb_node *parent;
+
+	if (!tree || !event)
+		return 0;

I don't think this should be happening, should it? And either way you probably don't want to return 0 here, unless you're using !0 for success.

Quoted 3 lines

As you might notice already, currently return codes of the tree API are not checked all other the implementation. I suggest replacing that int error code by void and simplify the stuff.

Your call. But I'd still either drop the redundant checks or wrap them in WARN_ON_ONCE().

Quoted 17 lines

Quoted 17 lines

Quoted 5 lines

kernel/events/core.c +2 -0

+
+	node = &tree->rb_node;

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1498

Quoted 10 lines

kernel/events/core.c +10 -0

+	parent = *node;
+
+	while (*node) {
+		struct perf_event *node_event =	container_of(*node,
+				struct perf_event, group_node);
+
+		parent = *node;
+
+		if (event->cpu < node_event->cpu) {
+			node = &((*node)->rb_left);

this would be the same as node = &parent->rb_left, right?

Quoted 2 lines

Please ask more.

Side note: between commit message, comments and the actual code, in an ideal situation one doesn't have to 'ask' anything, because everything is already clear. Not the case here.

Quoted 3 lines

node is the leaf node and parent is the parent of the
node at the end of cycle. We need the both to insert a new node into a tree.

Not sure I understand. You'd still have both.

Quoted 11 lines

Quoted 10 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 7 lines

kernel/events/core.c +5 -0

+		} else if (event->cpu > node_event->cpu) {
+			node = &((*node)->rb_right);
+		} else {
+			list_add_tail(&event->group_list_entry,
+					&node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Quoted 4 lines

Good question. Choice of data structure and layout depends on the operations applied to the data so keeping groups as a tree simplifies and improves the implementation in terms of scalability and performance. Please ask more if any.

Please be more specific on how scalability and performance are improved. In general, try to avoid vagues statements like "this is better for performance".

Thanks,
--
Alex

Quoted 5 lines · Alexander Shishkin

Quoted 3 lines · Alexey Budankov

Quoted 2 lines · Alexander Shishkin

Alexey Budankov <[email protected]> writes:

Quoted 7 lines

Quoted 5 lines

Quoted 2 lines

Here (above the function) you could include a comment describing what happens when this is called, locking considerations, etc.

I can put the short description from the initial thread message here. Would it be sufficient?

Sure, this is where API descriptions fit better than in commit messages.

Quoted 16 lines

Quoted 16 lines

Quoted 15 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1486

Quoted 11 lines

kernel/events/core.c +8 -0

+static int
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+    struct rb_node **node;
+    struct rb_node *parent;
+
+    if (!tree || !event)
+        return 0;

I don't think this should be happening, should it? And either way you probably don't want to return 0 here, unless you're using !0 for success.

Quoted 6 lines

Quoted 3 lines

As you might notice already, currently return codes of the tree API are not checked all other the implementation. I suggest replacing that int error code by void and simplify the stuff.

Your call. But I'd still either drop the redundant checks or wrap them in WARN_ON_ONCE().

Ok. WARN_ON_ONCE() then.

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 14 lines

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

kernel/events/core.c +6 -0

+
+    node = &tree->rb_node;
+    parent = *node;
+
+    while (*node) {
+        struct perf_event *node_event =    container_of(*node,

Quoted 8 lines

Quoted 8 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1498

Quoted 6 lines

kernel/events/core.c +6 -0

+                struct perf_event, group_node);
+
+        parent = *node;
+
+        if (event->cpu < node_event->cpu) {
+            node = &((*node)->rb_left);

this would be the same as node = &parent->rb_left, right?

Yes, that is right.

Quoted 25 lines

Quoted 3 lines

Please ask more.

Side note: between commit message, comments and the actual code, in an ideal situation one doesn't have to 'ask' anything, because everything is already clear. Not the case here.

Quoted 3 lines

node is the leaf node and parent is the parent of the
node at the end of cycle. We need the both to insert a new node into a tree.

Not sure I understand. You'd still have both.

Quoted 11 lines

Quoted 10 lines

kernel/events/core.c ctx_group_list(struct perf_event *event, struct perf_event_context *ctx) · line 1503

Quoted 7 lines

kernel/events/core.c +5 -0

+        } else if (event->cpu > node_event->cpu) {
+            node = &((*node)->rb_right);
+        } else {
+            list_add_tail(&event->group_list_entry,
+                    &node_event->group_list);

So why is this better than simply having per-cpu event lists plus one for per-thread events?

Quoted 8 lines

Quoted 4 lines

Good question. Choice of data structure and layout depends on the operations applied to the data so keeping groups as a tree simplifies and improves the implementation in terms of scalability and performance. Please ask more if any.

Please be more specific on how scalability and performance are improved. In general, try to avoid vagues statements like "this is better for performance".

Accepted. Peter already provided more specifics on this. Thanks.

Quoted 5 lines

Thanks,

Signature · 1 line

Alex