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

This series of patches continues v2 and addresses captured comments.

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.

Signed-off-by Alexey Budankov <[email protected]>

---
 include/linux/perf_event.h |  34 +++-
 kernel/events/core.c       | 386
+++++++++++++++++++++++++++++++++------------
 2 files changed, 315 insertions(+), 105 deletions(-)

include/linux/perf_event.h +10 -0

index 24a6358..2c1dcf1 100644
@@ -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

include/linux/perf_event.h +1 -2

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

include/linux/perf_event.h +1 -0

+
 	struct list_head		event_list;
 	int				nr_events;
 	int				nr_active;

kernel/events/core.c +11 -4

index bc63f8d..a3531f9 100644
@@ -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.
+ */

kernel/events/core.c +5 -0

+
+	while (*node) {
+		struct perf_event *node_event =	container_of(*node,
+				struct perf_event, group_node);
+

kernel/events/core.c +11 -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);
+}
+
+/*
+ * 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.
+ */

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_delete(struct rb_root *tree, struct perf_event *event)
+{
+	WARN_ON_ONCE(!tree || !event);

kernel/events/core.c +61 -0

+	}
+}
+
+/*
+ * 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);
+

/*

kernel/events/core.c +0 -0

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

kernel/events/core.c +0 -0

 	}
 

kernel/events/core.c +0 -0

 	list_update_cgroup_event(event, ctx, true);

@@ -1680,8 +1809,12 @@ list_del_event(struct perf_event *event,
 struct perf_event_context *ctx)

Hi,

Quoted 1 line · Alexey Budankov

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.

Quoted 5 lines

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,

Quoted 2 lines

Signed-off-by Alexey Budankov <[email protected]>

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

Quoted 5 lines

---
  include/linux/perf_event.h |  34 +++-
  kernel/events/core.c       | 386
+++++++++++++++++++++++++++++++++------------
  2 files changed, 315 insertions(+), 105 deletions(-)

<changelog goes here>

Quoted 24 lines

include/linux/perf_event.h +15 -0

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

include/linux/perf_event.h struct perf_event { · line 596

Quoted 5 lines

include/linux/perf_event.h +5 -0

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

Quoted 11 lines

include/linux/perf_event.h +1 -2

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

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

Quoted 10 lines

include/linux/perf_event.h +10 -0

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

Quoted 37 lines

include/linux/perf_event.h +1 -0

+
  	struct list_head		event_list;
  	int				nr_events;
  	int				nr_active;

kernel/events/core.c +15 -4

index bc63f8d..a3531f9 100644
@@ -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;

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1484

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 10 lines

kernel/events/core.c +9 -0

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

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1499

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 19 lines

kernel/events/core.c +11 -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);
+}
+
+/*
+ * 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.
+ */

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_delete(struct rb_root *tree, struct perf_event *event)
+{
+	WARN_ON_ONCE(!tree || !event);

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1526

Quoted 10 lines

kernel/events/core.c +10 -0

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

Quoted 61 lines

Quoted 1 line

(quoted diff) +1 -0

+	}

kernel/events/core.c +60 -0

+}
+
+/*
+ * 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);
+

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 10 lines

kernel/events/core.c +9 -0

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

Quoted 12 lines

/*

kernel/events/core.c +1 -1

@@ -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;
 

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

Quoted 4 lines

kernel/events/core.c +2 -2

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

Quoted 9 lines

kernel/events/core.c +0 -0

  	}
 

  	list_update_cgroup_event(event, ctx, true);

kernel/events/core.c +0 -0

@@ -1680,8 +1809,12 @@ list_del_event(struct perf_event *event,
 struct perf_event_context *ctx)
 
  	list_del_rcu(&event->event_entry);
 

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

Quoted 7 lines

kernel/events/core.c +5 -2

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

Quoted 8 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

Quoted 2 lines

If you use --per-thread, I take it the overhead is significantly lowered?

Please ask more.

Quoted 4 lines

Quoted 4 lines

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+	struct rb_node **node;

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1484

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 9 lines · Alexey Budankov

Quoted 8 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

Quoted 4 lines

Quoted 2 lines

If you use --per-thread, I take it the overhead is significantly lowered?

Please ask more.

IIUC, you're seeing the slowdown when using perf record, correct?

There's a --per-thread option to ask perf record to not duplicate the event per-cpu.

If you use that, what amount of slowdown do you see?

It might be preferable to not open task-bound per-cpu events on systems with large cpu counts, and it would be good to know what the trade-off looks like for this case.

Quoted 13 lines

Quoted 4 lines

Quoted 4 lines

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+	struct rb_node **node;

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1484

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 1 line

If tree is empty parent will be uninitialized what is harmful.

Sorry; my bad.

Thanks,
Mark.

Quoted 10 lines · Mark Rutland

Quoted 9 lines · Alexey Budankov

Quoted 8 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

If you use --per-thread, I take it the overhead is significantly lowered?

Please ask more.

IIUC, you're seeing the slowdown when using perf record, correct?

Correct. Specifically in per-process mode - without -a option.

Quoted 5 lines

There's a --per-thread option to ask perf record to not duplicate the event per-cpu.

If you use that, what amount of slowdown do you see?

Quoted 25 lines

It might be preferable to not open task-bound per-cpu events on systems with large cpu counts, and it would be good to know what the trade-off looks like for this case.

Quoted 13 lines

Quoted 4 lines

Quoted 4 lines

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+    struct rb_node **node;

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1484

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 1 line

If tree is empty parent will be uninitialized what is harmful.

Sorry; my bad.

Thanks,
Mark.

Quoted 11 lines · Alexey Budankov

Quoted 10 lines · Mark Rutland

Quoted 9 lines · Alexey Budankov

Quoted 8 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

Quoted 14 lines

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

If you use --per-thread, I take it the overhead is significantly lowered?

Please ask more.

IIUC, you're seeing the slowdown when using perf record, correct?

Correct. Specifically in per-process mode - without -a option.

Quoted 5 lines

There's a --per-thread option to ask perf record to not duplicate the event per-cpu.

If you use that, what amount of slowdown do you see?

After applying all three patches:

- system-wide collection:

[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 303.795 MB perf.data (~13272985 samples) ] 2162.08user 176.24system 0:12.97elapsed 18021%CPU (0avgtext+0avgdata 1187208maxresident)k
0inputs+622624outputs (0major+1360285minor)pagefaults 0swaps

- per-process collection:

[ perf record: Woken up 5 times to write data ]
[ perf record: Captured and wrote 1.079 MB perf.data (~47134 samples) ] 2102.39user 153.88system 0:12.78elapsed 17645%CPU (0avgtext+0avgdata 1187156maxresident)k
0inputs+2272outputs (0major+1181660minor)pagefaults 0swaps

Elapsed times look similar. Data file sizes differ significantly.

Quoted 19 lines · Alexey Budankov

Quoted 5 lines · Alexey Budankov

Quoted 4 lines · Mark Rutland

There's a --per-thread option to ask perf record to not duplicate the event per-cpu.

If you use that, what amount of slowdown do you see?

After applying all three patches:

- system-wide collection:

[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 303.795 MB perf.data (~13272985 samples) ] 2162.08user 176.24system 0:12.97elapsed 18021%CPU (0avgtext+0avgdata 1187208maxresident)k
0inputs+622624outputs (0major+1360285minor)pagefaults 0swaps

- per-process collection:

Quoted 7 lines

[ perf record: Woken up 5 times to write data ]
[ perf record: Captured and wrote 1.079 MB perf.data (~47134 samples) ] 2102.39user 153.88system 0:12.78elapsed 17645%CPU (0avgtext+0avgdata 1187156maxresident)k
0inputs+2272outputs (0major+1181660minor)pagefaults 0swaps

Elapsed times look similar. Data file sizes differ significantly.

Interesting. I wonder if that's because we're losing samples due to hammering the rb, or if that's a side-effect of this patch.

Does perf report describe any lost chunks?

For comparison, can you give --per-thread a go prior to these patches being applied?

Quoted 28 lines · Mark Rutland

Quoted 19 lines · Alexey Budankov

Quoted 5 lines · Alexey Budankov

Quoted 4 lines · Mark Rutland

There's a --per-thread option to ask perf record to not duplicate the event per-cpu.

If you use that, what amount of slowdown do you see?

After applying all three patches:

- system-wide collection:

[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 303.795 MB perf.data (~13272985 samples) ] 2162.08user 176.24system 0:12.97elapsed 18021%CPU (0avgtext+0avgdata 1187208maxresident)k
0inputs+622624outputs (0major+1360285minor)pagefaults 0swaps

- per-process collection:

Quoted 7 lines

[ perf record: Woken up 5 times to write data ]
[ perf record: Captured and wrote 1.079 MB perf.data (~47134 samples) ] 2102.39user 153.88system 0:12.78elapsed 17645%CPU (0avgtext+0avgdata 1187156maxresident)k
0inputs+2272outputs (0major+1181660minor)pagefaults 0swaps

Elapsed times look similar. Data file sizes differ significantly.

Quoted 7 lines

Interesting. I wonder if that's because we're losing samples due to hammering the rb, or if that's a side-effect of this patch.

Does perf report describe any lost chunks?

For comparison, can you give --per-thread a go prior to these patches being applied?

FWIW, I had a go with (an old) perf record on an arm64 system using --per-thread, and I see that no samples are recorded, which seems like a bug.

With --per-thread, the slwodown was ~20%, whereas with the defaults it was > 400%.

Thanks,
Mark.

Quoted 2 lines

For comparison, can you give --per-thread a go prior to these patches being applied?

FWIW, I had a go with (an old) perf record on an arm64 system using --per-thread, and I see that no samples are recorded, which seems like a bug.

With --per-thread, the slwodown was ~20%, whereas with the defaults it was > 400%.

Quoted 7 lines

Quoted 2 lines

For comparison, can you give --per-thread a go prior to these patches being applied?

FWIW, I had a go with (an old) perf record on an arm64 system using --per-thread, and I see that no samples are recorded, which seems like a bug.

Quoted 2 lines

With --per-thread, the slwodown was ~20%, whereas with the defaults it was > 400%.

I'm not sure what the point of the experiment is? It has to work with reasonable overead even without --per-thread.

FWIW Alexey already root caused the problem, so there's no need to restart the debugging.

I was trying to get a feel for how that compares to what we can do today. For other reasons (e.g. fd exhaustion), opening NR_CPUS * n

events might not be a great idea on systems with a huge number of CPUs. We might want a heuristic in the perf tool regardless.

Quoted 2 lines

I was trying to get a feel for how that compares to what we can do today. For other reasons (e.g. fd exhaustion), opening NR_CPUS * n

You just have to increase the fd limit. The 1024 fd default is just archaic for larger systems and doesn't really make any sense because it only controls very small amounts of kernel memory.

Quoted 2 lines

events might not be a great idea on systems with a huge number of CPUs. We might want a heuristic in the perf tool regardless.

But there's no alternative: we have to measure all CPUs with all events.

Quoted 7 lines · Andi Kleen

Quoted 2 lines

I was trying to get a feel for how that compares to what we can do today. For other reasons (e.g. fd exhaustion), opening NR_CPUS * n

You just have to increase the fd limit. The 1024 fd default is just archaic for larger systems and doesn't really make any sense because it only controls very small amounts of kernel memory.

Quoted 4 lines

Quoted 2 lines

events might not be a great idea on systems with a huge number of CPUs. We might want a heuristic in the perf tool regardless.

But there's no alternative: we have to measure all CPUs with all events.

You can measure the process on all CPUs by using 1 event without a CPU filter, rather than NR_CPUS events.

Quoted 11 lines · Mark Rutland

Quoted 10 lines · Andi Kleen

Quoted 2 lines

I was trying to get a feel for how that compares to what we can do today. For other reasons (e.g. fd exhaustion), opening NR_CPUS * n

You just have to increase the fd limit. The 1024 fd default is just archaic for larger systems and doesn't really make any sense because it only controls very small amounts of kernel memory.

Quoted 2 lines

events might not be a great idea on systems with a huge number of CPUs. We might want a heuristic in the perf tool regardless.

Quoted 4 lines

Quoted 1 line

But there's no alternative: we have to measure all CPUs with all events.

You can measure the process on all CPUs by using 1 event without a CPU filter, rather than NR_CPUS events.

That wouldn't measure all threads, at least not with current perf core.

Hi,

Quoted 8 lines · Mark Rutland

Hi,

Quoted 1 line · Alexey Budankov

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.

Quoted 8 lines

Quoted 5 lines

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.

Quoted 27 lines

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.

Quoted 9 lines

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.

Quoted 3 lines

Quoted 2 lines

Signed-off-by Alexey Budankov <[email protected]>

Quoted 6 lines

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.

Quoted 35 lines

Quoted 6 lines

---
  include/linux/perf_event.h |  34 +++-
  kernel/events/core.c       | 386
+++++++++++++++++++++++++++++++++------------
  2 files changed, 315 insertions(+), 105 deletions(-)

<changelog goes here>

Quoted 26 lines

include/linux/perf_event.h +10 -0

index 24a6358..2c1dcf1 100644
@@ -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

include/linux/perf_event.h +5 -0

+     * attached to the tree;
+     */
+    struct list_head        group_list;
+    /*
+     * Entry into the group_list list above;

Quoted 8 lines

include/linux/perf_event.h struct perf_event { · line 596

Quoted 5 lines

include/linux/perf_event.h +5 -0

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

Quoted 27 lines

Quoted 13 lines

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

include/linux/perf_event.h +0 -2

@@ -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;

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

Quoted 10 lines

include/linux/perf_event.h +10 -0

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

Quoted 5 lines

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.

Quoted 40 lines

Quoted 40 lines

include/linux/perf_event.h +1 -0

+
      struct list_head        event_list;
      int                nr_events;
      int                nr_active;

kernel/events/core.c +8 -4

index bc63f8d..a3531f9 100644
@@ -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.
+ */

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_insert(struct rb_root *tree, struct perf_event *event)
+{
+    struct rb_node **node;

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1484

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 10 lines

Quoted 10 lines

kernel/events/core.c +9 -0

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

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1499

Quoted 6 lines

kernel/events/core.c +6 -0

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

Quoted 3 lines

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.

Quoted 11 lines

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.

Quoted 122 lines

Quoted 19 lines

kernel/events/core.c +11 -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);
+}
+
+/*
+ * 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.
+ */

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_delete(struct rb_root *tree, struct perf_event *event)
+{
+    WARN_ON_ONCE(!tree || !event);

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1526

Quoted 10 lines

kernel/events/core.c +10 -0

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

Quoted 63 lines

Quoted 1 line

+ }

kernel/events/core.c +4 -0

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

kernel/events/core.c +38 -0

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

kernel/events/core.c +14 -0

+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);
+

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 10 lines

kernel/events/core.c +9 -0

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

Quoted 12 lines

/*

kernel/events/core.c +1 -1

@@ -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;
 

Quoted 7 lines

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

Quoted 4 lines

kernel/events/core.c +2 -2

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

Quoted 9 lines

Quoted 9 lines

kernel/events/core.c +0 -0

      }
 

      list_update_cgroup_event(event, ctx, true);

kernel/events/core.c +0 -0

@@ -1680,8 +1809,12 @@ list_del_event(struct perf_event *event,
 struct perf_event_context *ctx)
 
      list_del_rcu(&event->event_entry);
 

Quoted 9 lines

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

Quoted 7 lines

kernel/events/core.c +5 -2

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

Quoted 4 lines

Thanks,
Mark.

Thanks,
Alexey

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 1 line

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.

Quoted 16 lines · Alexey Budankov

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 8 lines

Quoted 1 line

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.

Ok; that was the kind of thing I was concerned about.

What you say "strange stacks", what do you mean exactly?

I take it the kernel spewing backtraces in dmesg?

Can you dump those?

Thanks,
Mark.

Quoted 26 lines · Mark Rutland

Quoted 16 lines · Alexey Budankov

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 8 lines

Quoted 1 line

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.

Quoted 7 lines

Ok; that was the kind of thing I was concerned about.

What you say "strange stacks", what do you mean exactly?

I take it the kernel spewing backtraces in dmesg?

Can you dump those?

Here it is:

list_del corruption. prev->next should be ffff88c2c4654010, but was ffff88c31eb0c020

[  607.632813] ------------[ cut here ]------------
[  607.632816] kernel BUG at lib/list_debug.c:53!
[  607.632825] invalid opcode: 0000 [#1] SMP
[  607.632898] Modules linked in: fuse xt_CHECKSUM iptable_mangle ipt_MASQUERADE nf_nat_masquerade_ipv4 iptable_nat nf_nat_ipv4 nf_nat nf_conntrack_ipv4 nf_defrag_ipv4 xt_conntrack nf_conntrack libcrc32c tun bridge stp llc ebtable_filter ebtables ip6table_filter ip6_tables nfsv3 rpcsec_gss_krb5 nfsv4 arc4 md4 nls_utf8 cifs nfs ccm dns_resolver fscache rpcrdma ib_isert iscsi_target_mod ib_iser libiscsi scsi_transport_iscsi ib_srpt target_core_mod ib_srp scsi_transport_srp ib_ipoib rdma_ucm ib_ucm ib_uverbs ib_umad rdma_cm ib_cm iw_cm intel_rapl sb_edac x86_pkg_temp_thermal intel_powerclamp hfi1 coretemp crct10dif_pclmul crc32_pclmul ghash_clmulni_intel intel_cstate iTCO_wdt intel_uncore iTCO_vendor_support joydev rdmavt intel_rapl_perf i2c_i801 ib_core ipmi_ssif mei_me mei ipmi_si ipmi_devintf tpm_tis
[  607.633954]  lpc_ich pcspkr ipmi_msghandler acpi_pad tpm_tis_core shpchp tpm wmi acpi_power_meter nfsd auth_rpcgss nfs_acl lockd grace sunrpc mgag200 drm_kms_helper ttm drm igb crc32c_intel ptp pps_core dca i2c_algo_bit
[  607.634262] CPU: 271 PID: 28944 Comm: perf_fuzzer Not tainted 4.12.0-rc4+ #22
[  607.634363] Hardware name: Intel Corporation S7200AP/S7200AP, BIOS S72C610.86B.01.01.0190.080520162104 08/05/2016
[  607.634505] task: ffff88c2d5714000 task.stack: ffffa6f9352c8000
[  607.634597] RIP: 0010:__list_del_entry_valid+0x7b/0x90
[  607.634670] RSP: 0000:ffffa6f9352cbad0 EFLAGS: 00010046
[  607.634746] RAX: 0000000000000054 RBX: ffff88c2c4654000 RCX: 0000000000000000
[  607.634845] RDX: 0000000000000000 RSI: ffff88c33fdce168 RDI: ffff88c33fdce168
[  607.634944] RBP: ffffa6f9352cbad0 R08: 00000000fffffffe R09: 0000000000000600
[  607.635042] R10: 0000000000000005 R11: 0000000000000000 R12: ffff88c2e71ab200
[  607.635140] R13: ffff88c2c4654010 R14: 0000000000000001 R15: 0000000000000001
[  607.635240] FS:  0000000000000000(0000) GS:ffff88c33fdc0000(0000) knlGS:0000000000000000
[  607.635351] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  607.635431] CR2: 00000000026be1e4 CR3: 0000002488e09000 CR4: 00000000001407e0
[  607.635531] Call Trace:
[  607.635583]  list_del_event+0x1d7/0x210
[  607.635646]  ? perf_cgroup_attach+0x70/0x70
[  607.635711]  __perf_remove_from_context+0x3e/0x90
[  607.635783]  ? event_sched_out.isra.90+0x300/0x300
[  607.635854]  event_function_call+0xbf/0xf0
[  607.635918]  ? event_sched_out.isra.90+0x300/0x300
[  607.635991]  perf_remove_from_context+0x25/0x70
[  607.636060]  perf_event_release_kernel+0xda/0x250
[  607.636132]  ? __dentry_kill+0x10e/0x160
[  607.636192]  perf_release+0x10/0x20
[  607.636249]  __fput+0xdf/0x1e0
[  607.636299]  ____fput+0xe/0x10
[  607.636350]  task_work_run+0x83/0xb0
[  607.636408]  do_exit+0x2bc/0xbc0
[  607.636460]  ? page_add_file_rmap+0xaf/0x200
[  607.636526]  ? alloc_set_pte+0x115/0x4f0
[  607.636587]  do_group_exit+0x3f/0xb0
[  607.636644]  get_signal+0x1cc/0x5c0
[  607.636703]  do_signal+0x37/0x6a0
[  607.636758]  ? __perf_sw_event+0x4f/0x80
[  607.636821]  ? __do_page_fault+0x2e1/0x4d0
[  607.636885]  exit_to_usermode_loop+0x4c/0x92
[  607.636953]  prepare_exit_to_usermode+0x40/0x50
[  607.637023]  retint_user+0x8/0x13
[  607.640312] RIP: 0033:0x40f4a9
[  607.643500] RSP: 002b:00007ffc62d00668 EFLAGS: 00000206 ORIG_RAX: ffffffffffffff02
[  607.646678] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 000000000001100a
[  607.649777] RDX: 00007fd5dd25bae0 RSI: 00007fd5dd259760 RDI: 00007fd5dd25a640
[  607.652791] RBP: 00007ffc62d00680 R08: 00007fd5dd45e740 R09: 0000000000000000
[  607.655709] R10: 00007fd5dd45ea10 R11: 0000000000000246 R12: 0000000000401980
[  607.658530] R13: 00007ffc62d02a80 R14: 0000000000000000 R15: 0000000000000000
[  607.661249] Code: e8 3a f7 d8 ff 0f 0b 48 89 fe 31 c0 48 c7 c7 20 66 cb ac e8 27 f7 d8 ff 0f 0b 48 89 fe 31 c0 48 c7 c7 e0 65 cb ac e8 14 f7 d8 ff <0f> 0b 48 89 fe 31 c0 48 c7 c7 a8 65 cb ac e8 01 f7 d8 ff 0f 0b
[  607.666819] RIP: __list_del_entry_valid+0x7b/0x90 RSP: ffffa6f9352cbad0
[  607.683316] ---[ end trace 34244c35550e0713 ]---
[  607.691830] Fixing recursive fault but reboot is needed!

2:

[  467.942059] unchecked MSR access error: WRMSR to 0x711 (tried to write 0x00000000e8cc0055) at rIP: 0xffffffffac05fbd4 (native_write_msr+0x4/0x30)
[  467.942068] Call Trace:
[  467.942073]  <IRQ>
[  467.942094]  ? snbep_uncore_msr_enable_event+0x54/0x60 [intel_uncore]
[  467.942107]  uncore_pmu_event_start+0x9b/0x100 [intel_uncore]
[  467.942119]  uncore_pmu_event_add+0x235/0x3a0 [intel_uncore]
[  467.942126]  ? sched_clock+0xb/0x10
[  467.942132]  ? sched_clock_cpu+0x11/0xb0
[  467.942140]  event_sched_in.isra.100+0xdf/0x250
[  467.942145]  sched_in_group+0x210/0x390
[  467.942150]  ? sched_in_group+0x390/0x390
[  467.942155]  group_sched_in_flexible_callback+0x17/0x20
[  467.942160]  perf_cpu_tree_iterate+0x45/0x75
[  467.942165]  ctx_sched_in+0x97/0x110
[  467.942169]  perf_event_sched_in+0x77/0x80
[  467.942174]  ctx_resched+0x69/0xb0
[  467.942179]  __perf_event_enable+0x208/0x250
[  467.942184]  event_function+0x93/0xe0
[  467.942188]  remote_function+0x3b/0x50
[  467.942194]  flush_smp_call_function_queue+0x71/0x120
[  467.942200]  generic_smp_call_function_single_interrupt+0x13/0x30
[  467.942206]  smp_call_function_single_interrupt+0x27/0x40
[  467.942212]  call_function_single_interrupt+0x93/0xa0
[  467.942217] RIP: 0010:native_restore_fl+0x6/0x10
[  467.942220] RSP: 0000:ffff88c33ba03e00 EFLAGS: 00000206 ORIG_RAX: ffffffffffffff04
[  467.942224] RAX: ffff88c33c8dca08 RBX: ffff88c33c8dc928 RCX: 0000000000000017
[  467.942227] RDX: 0000000000000000 RSI: 0000000000000206 RDI: 0000000000000206
[  467.942229] RBP: ffff88c33ba03e00 R08: 0000000000000001 R09: 0000000000007151
[  467.942232] R10: 0000000000000000 R11: 000000000000005d R12: ffff88c33c8dca08
[  467.942234] R13: ffff88c33c8dc140 R14: 0000000000000001 R15: 00000000000001d8
[  467.942241]  _raw_spin_unlock_irqrestore+0x16/0x20
[  467.942245]  update_blocked_averages+0x2cf/0x4a0
[  467.942251]  rebalance_domains+0x4b/0x2b0
[  467.942256]  run_rebalance_domains+0x1d7/0x210
[  467.942260]  __do_softirq+0xd1/0x27f
[  467.942267]  irq_exit+0xe9/0x100
[  467.942271]  scheduler_ipi+0x8f/0x140
[  467.942275]  smp_reschedule_interrupt+0x29/0x30
[  467.942280]  reschedule_interrupt+0x93/0xa0
[  467.942284] RIP: 0010:native_safe_halt+0x6/0x10
[  467.942286] RSP: 0000:fffffffface03de0 EFLAGS: 00000246 ORIG_RAX: ffffffffffffff02
[  467.942291] RAX: 0000000000000000 RBX: fffffffface104c0 RCX: 0000000000000000
[  467.942293] RDX: 0000000000000000 RSI: 0000000000000000 RDI: 0000000000000000
[  467.942295] RBP: fffffffface03de0 R08: 0000006d2c5efae3 R09: 0000000000000000
[  467.942298] R10: 0000000000000201 R11: 0000000000000930 R12: 0000000000000000
[  467.942300] R13: fffffffface104c0 R14: 0000000000000000 R15: 0000000000000000
[  467.942302]  </IRQ>
[  467.942308]  default_idle+0x20/0x100
[  467.942313]  arch_cpu_idle+0xf/0x20
[  467.942317]  default_idle_call+0x2c/0x40
[  467.942321]  do_idle+0x158/0x1e0

[  467.942325]  cpu_startup_entry+0x71/0x80
[  467.942330]  rest_init+0x77/0x80
[  467.942338]  start_kernel+0x4a7/0x4c8
[  467.942342]  ? set_init_arg+0x5a/0x5a
[  467.942348]  ? early_idt_handler_array+0x120/0x120
[  467.942352]  x86_64_start_reservations+0x29/0x2b
[  467.942357]  x86_64_start_kernel+0x151/0x174
[  467.942363]  secondary_startup_64+0x9f/0x9f

Quoted 4 lines

Thanks,
Mark.

One more:

Quoted 1 line

One more:

It may help if you run with KASAN enabled. That often finds problems earlier.

Also could use ftrace and use ftrace_dump_on_oops to see the sequence (but that has a lot of overhead and sometimes hides problems)

-Andi

Quoted 8 lines · Andi Kleen

Quoted 1 line

One more:

It may help if you run with KASAN enabled. That often finds problems earlier.

Also could use ftrace and use ftrace_dump_on_oops to see the sequence (but that has a lot of overhead and sometimes hides problems)

Ok. Will try. Thanks.

Quoted 5 lines

-Andi

Quoted 146 lines · Alexey Budankov

Quoted 26 lines · Mark Rutland

Quoted 16 lines · Alexey Budankov

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 8 lines

Quoted 1 line

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.

Quoted 7 lines

Ok; that was the kind of thing I was concerned about.

What you say "strange stacks", what do you mean exactly?

I take it the kernel spewing backtraces in dmesg?

Can you dump those?

Here it is:

list_del corruption. prev->next should be ffff88c2c4654010, but was ffff88c31eb0c020

[  607.632813] ------------[ cut here ]------------
[  607.632816] kernel BUG at lib/list_debug.c:53!
[  607.632825] invalid opcode: 0000 [#1] SMP
[  607.632898] Modules linked in: fuse xt_CHECKSUM iptable_mangle ipt_MASQUERADE nf_nat_masquerade_ipv4 iptable_nat nf_nat_ipv4 nf_nat nf_conntrack_ipv4 nf_defrag_ipv4 xt_conntrack nf_conntrack libcrc32c tun bridge stp llc ebtable_filter ebtables ip6table_filter ip6_tables nfsv3 rpcsec_gss_krb5 nfsv4 arc4 md4 nls_utf8 cifs nfs ccm dns_resolver fscache rpcrdma ib_isert iscsi_target_mod ib_iser libiscsi scsi_transport_iscsi ib_srpt target_core_mod ib_srp scsi_transport_srp ib_ipoib rdma_ucm ib_ucm ib_uverbs ib_umad rdma_cm ib_cm iw_cm intel_rapl sb_edac x86_pkg_temp_thermal intel_powerclamp hfi1 coretemp crct10dif_pclmul crc32_pclmul ghash_clmulni_intel intel_cstate iTCO_wdt intel_uncore iTCO_vendor_support joydev rdmavt intel_rapl_perf i2c_i801 ib_core ipmi_ssif mei_me mei ipmi_si ipmi_devintf tpm_tis
[  607.633954]  lpc_ich pcspkr ipmi_msghandler acpi_pad tpm_tis_core shpchp tpm wmi acpi_power_meter nfsd auth_rpcgss nfs_acl lockd grace sunrpc mgag200 drm_kms_helper ttm drm igb crc32c_intel ptp pps_core dca i2c_algo_bit
[  607.634262] CPU: 271 PID: 28944 Comm: perf_fuzzer Not tainted 4.12.0-rc4+ #22
[  607.634363] Hardware name: Intel Corporation S7200AP/S7200AP, BIOS S72C610.86B.01.01.0190.080520162104 08/05/2016
[  607.634505] task: ffff88c2d5714000 task.stack: ffffa6f9352c8000
[  607.634597] RIP: 0010:__list_del_entry_valid+0x7b/0x90
[  607.634670] RSP: 0000:ffffa6f9352cbad0 EFLAGS: 00010046
[  607.634746] RAX: 0000000000000054 RBX: ffff88c2c4654000 RCX: 0000000000000000
[  607.634845] RDX: 0000000000000000 RSI: ffff88c33fdce168 RDI: ffff88c33fdce168
[  607.634944] RBP: ffffa6f9352cbad0 R08: 00000000fffffffe R09: 0000000000000600
[  607.635042] R10: 0000000000000005 R11: 0000000000000000 R12: ffff88c2e71ab200
[  607.635140] R13: ffff88c2c4654010 R14: 0000000000000001 R15: 0000000000000001
[  607.635240] FS:  0000000000000000(0000) GS:ffff88c33fdc0000(0000) knlGS:0000000000000000
[  607.635351] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  607.635431] CR2: 00000000026be1e4 CR3: 0000002488e09000 CR4: 00000000001407e0
[  607.635531] Call Trace:
[  607.635583]  list_del_event+0x1d7/0x210
[  607.635646]  ? perf_cgroup_attach+0x70/0x70
[  607.635711]  __perf_remove_from_context+0x3e/0x90
[  607.635783]  ? event_sched_out.isra.90+0x300/0x300
[  607.635854]  event_function_call+0xbf/0xf0
[  607.635918]  ? event_sched_out.isra.90+0x300/0x300
[  607.635991]  perf_remove_from_context+0x25/0x70
[  607.636060]  perf_event_release_kernel+0xda/0x250
[  607.636132]  ? __dentry_kill+0x10e/0x160
[  607.636192]  perf_release+0x10/0x20
[  607.636249]  __fput+0xdf/0x1e0
[  607.636299]  ____fput+0xe/0x10
[  607.636350]  task_work_run+0x83/0xb0
[  607.636408]  do_exit+0x2bc/0xbc0
[  607.636460]  ? page_add_file_rmap+0xaf/0x200
[  607.636526]  ? alloc_set_pte+0x115/0x4f0
[  607.636587]  do_group_exit+0x3f/0xb0
[  607.636644]  get_signal+0x1cc/0x5c0
[  607.636703]  do_signal+0x37/0x6a0
[  607.636758]  ? __perf_sw_event+0x4f/0x80
[  607.636821]  ? __do_page_fault+0x2e1/0x4d0
[  607.636885]  exit_to_usermode_loop+0x4c/0x92
[  607.636953]  prepare_exit_to_usermode+0x40/0x50
[  607.637023]  retint_user+0x8/0x13
[  607.640312] RIP: 0033:0x40f4a9
[  607.643500] RSP: 002b:00007ffc62d00668 EFLAGS: 00000206 ORIG_RAX: ffffffffffffff02
[  607.646678] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 000000000001100a
[  607.649777] RDX: 00007fd5dd25bae0 RSI: 00007fd5dd259760 RDI: 00007fd5dd25a640
[  607.652791] RBP: 00007ffc62d00680 R08: 00007fd5dd45e740 R09: 0000000000000000
[  607.655709] R10: 00007fd5dd45ea10 R11: 0000000000000246 R12: 0000000000401980
[  607.658530] R13: 00007ffc62d02a80 R14: 0000000000000000 R15: 0000000000000000
[  607.661249] Code: e8 3a f7 d8 ff 0f 0b 48 89 fe 31 c0 48 c7 c7 20 66 cb ac e8 27 f7 d8 ff 0f 0b 48 89 fe 31 c0 48 c7 c7 e0 65 cb ac e8 14 f7 d8 ff <0f> 0b 48 89 fe 31 c0 48 c7 c7 a8 65 cb ac e8 01 f7 d8 ff 0f 0b
[  607.666819] RIP: __list_del_entry_valid+0x7b/0x90 RSP: ffffa6f9352cbad0
[  607.683316] ---[ end trace 34244c35550e0713 ]---
[  607.691830] Fixing recursive fault but reboot is needed!

2:

[  467.942059] unchecked MSR access error: WRMSR to 0x711 (tried to write 0x00000000e8cc0055) at rIP: 0xffffffffac05fbd4 (native_write_msr+0x4/0x30)
[  467.942068] Call Trace:
[  467.942073]  <IRQ>
[  467.942094]  ? snbep_uncore_msr_enable_event+0x54/0x60 [intel_uncore]
[  467.942107]  uncore_pmu_event_start+0x9b/0x100 [intel_uncore]
[  467.942119]  uncore_pmu_event_add+0x235/0x3a0 [intel_uncore]
[  467.942126]  ? sched_clock+0xb/0x10
[  467.942132]  ? sched_clock_cpu+0x11/0xb0
[  467.942140]  event_sched_in.isra.100+0xdf/0x250
[  467.942145]  sched_in_group+0x210/0x390
[  467.942150]  ? sched_in_group+0x390/0x390
[  467.942155]  group_sched_in_flexible_callback+0x17/0x20
[  467.942160]  perf_cpu_tree_iterate+0x45/0x75
[  467.942165]  ctx_sched_in+0x97/0x110
[  467.942169]  perf_event_sched_in+0x77/0x80
[  467.942174]  ctx_resched+0x69/0xb0
[  467.942179]  __perf_event_enable+0x208/0x250
[  467.942184]  event_function+0x93/0xe0
[  467.942188]  remote_function+0x3b/0x50
[  467.942194]  flush_smp_call_function_queue+0x71/0x120
[  467.942200]  generic_smp_call_function_single_interrupt+0x13/0x30
[  467.942206]  smp_call_function_single_interrupt+0x27/0x40
[  467.942212]  call_function_single_interrupt+0x93/0xa0
[  467.942217] RIP: 0010:native_restore_fl+0x6/0x10
[  467.942220] RSP: 0000:ffff88c33ba03e00 EFLAGS: 00000206 ORIG_RAX: ffffffffffffff04
[  467.942224] RAX: ffff88c33c8dca08 RBX: ffff88c33c8dc928 RCX: 0000000000000017
[  467.942227] RDX: 0000000000000000 RSI: 0000000000000206 RDI: 0000000000000206
[  467.942229] RBP: ffff88c33ba03e00 R08: 0000000000000001 R09: 0000000000007151
[  467.942232] R10: 0000000000000000 R11: 000000000000005d R12: ffff88c33c8dca08
[  467.942234] R13: ffff88c33c8dc140 R14: 0000000000000001 R15: 00000000000001d8
[  467.942241]  _raw_spin_unlock_irqrestore+0x16/0x20
[  467.942245]  update_blocked_averages+0x2cf/0x4a0
[  467.942251]  rebalance_domains+0x4b/0x2b0
[  467.942256]  run_rebalance_domains+0x1d7/0x210
[  467.942260]  __do_softirq+0xd1/0x27f
[  467.942267]  irq_exit+0xe9/0x100
[  467.942271]  scheduler_ipi+0x8f/0x140
[  467.942275]  smp_reschedule_interrupt+0x29/0x30
[  467.942280]  reschedule_interrupt+0x93/0xa0
[  467.942284] RIP: 0010:native_safe_halt+0x6/0x10
[  467.942286] RSP: 0000:fffffffface03de0 EFLAGS: 00000246 ORIG_RAX: ffffffffffffff02
[  467.942291] RAX: 0000000000000000 RBX: fffffffface104c0 RCX: 0000000000000000
[  467.942293] RDX: 0000000000000000 RSI: 0000000000000000 RDI: 0000000000000000
[  467.942295] RBP: fffffffface03de0 R08: 0000006d2c5efae3 R09: 0000000000000000
[  467.942298] R10: 0000000000000201 R11: 0000000000000930 R12: 0000000000000000
[  467.942300] R13: fffffffface104c0 R14: 0000000000000000 R15: 0000000000000000
[  467.942302]  </IRQ>
[  467.942308]  default_idle+0x20/0x100
[  467.942313]  arch_cpu_idle+0xf/0x20
[  467.942317]  default_idle_call+0x2c/0x40
[  467.942321]  do_idle+0x158/0x1e0

Quoted 10 lines

[  467.942325]  cpu_startup_entry+0x71/0x80
[  467.942330]  rest_init+0x77/0x80
[  467.942338]  start_kernel+0x4a7/0x4c8
[  467.942342]  ? set_init_arg+0x5a/0x5a
[  467.942348]  ? early_idt_handler_array+0x120/0x120
[  467.942352]  x86_64_start_reservations+0x29/0x2b
[  467.942357]  x86_64_start_kernel+0x151/0x174
[  467.942363]  secondary_startup_64+0x9f/0x9f

One more:

[  484.804717] ------------[ cut here ]------------
[  484.804737] WARNING: CPU: 15 PID: 31168 at arch/x86/events/core.c:1257 x86_pmu_start+0x8f/0xb0
[  484.804739] Modules linked in: btrfs xor raid6_pq ufs hfsplus hfs minix vfat msdos fat jfs xfs reiserfs binfmt_misc xt_CHECKSUM iptable_mangle fuse ipt_MASQUERADE nf_nat_masquerade_ipv4 iptable_nat nf_nat_ipv4 nf_nat nf_conntrack_ipv4 nf_defrag_ipv4 xt_conntrack nf_conntrack libcrc32c tun bridge stp llc ebtable_filter ebtables ip6table_filter nfsv3 ip6_tables arc4 md4 nls_utf8 rpcsec_gss_krb5 cifs nfsv4 nfs ccm dns_resolver fscache rpcrdma ib_isert iscsi_target_mod ib_iser libiscsi scsi_transport_iscsi ib_srpt target_core_mod ib_srp scsi_transport_srp ib_ipoib rdma_ucm ib_ucm ib_uverbs ib_umad rdma_cm ib_cm iw_cm intel_rapl sb_edac x86_pkg_temp_thermal intel_powerclamp hfi1 coretemp crct10dif_pclmul crc32_pclmul rdmavt ghash_clmulni_intel intel_cstate joydev iTCO_wdt intel_uncore ib_core iTCO_vendor_support
[  484.804868]  tpm_tis intel_rapl_perf ipmi_ssif tpm_tis_core ipmi_si mei_me tpm ipmi_devintf shpchp acpi_pad lpc_ich ipmi_msghandler pcspkr mei i2c_i801 nfsd acpi_power_meter wmi auth_rpcgss nfs_acl lockd grace sunrpc mgag200 drm_kms_helper ttm drm igb crc32c_intel ptp pps_core dca i2c_algo_bit
[  484.804927] CPU: 15 PID: 31168 Comm: perf_fuzzer Tainted: G        W      4.12.0-rc4+ #24
[  484.804930] Hardware name: Intel Corporation S7200AP/S7200AP, BIOS S72C610.86B.01.01.0190.080520162104 08/05/2016
[  484.804933] task: ffff8c4699c10000 task.stack: ffff9ad8b5900000
[  484.804938] RIP: 0010:x86_pmu_start+0x8f/0xb0
[  484.804941] RSP: 0000:ffff8c46fbdc3e58 EFLAGS: 00010046
[  484.804945] RAX: 0000000000000000 RBX: ffff8c468068f000 RCX: 0000000000000002
[  484.804948] RDX: 000000000000000e RSI: 0000000000000002 RDI: ffff8c468068f000
[  484.804950] RBP: ffff8c46fbdc3e70 R08: 0000000000000000 R09: 00000000000004c1
[  484.804952] R10: ffff8c46fbdcaaa0 R11: ffff8c46fbdc3b58 R12: ffff8c46fbdca380
[  484.804955] R13: 0000000000000000 R14: ffff8c46fbdca5a4 R15: 0000000000000001
[  484.804958] FS:  00007f1625c4c740(0000) GS:ffff8c46fbdc0000(0000) knlGS:0000000000000000
[  484.804961] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  484.804964] CR2: 000000000061b218 CR3: 0000002f2184f000 CR4: 00000000001407e0
[  484.804967] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[  484.804969] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000600
[  484.804971] Call Trace:
[  484.804976]  <IRQ>
[  484.804984]  x86_pmu_enable+0x27f/0x2f0
[  484.804992]  perf_pmu_enable+0x22/0x30
[  484.804997]  ctx_resched+0x72/0xb0
[  484.805003]  __perf_event_enable+0x208/0x250
[  484.805008]  event_function+0x93/0xe0
[  484.805012]  remote_function+0x3b/0x50
[  484.805018]  flush_smp_call_function_queue+0x71/0x120
[  484.805024]  generic_smp_call_function_single_interrupt+0x13/0x30
[  484.805030]  smp_trace_call_function_single_interrupt+0x2d/0xd0
[  484.805036]  trace_call_function_single_interrupt+0x93/0xa0
[  484.805040] RIP: 0033:0x40f4a9
[  484.805042] RSP: 002b:00007ffe26fde668 EFLAGS: 00000202 ORIG_RAX: ffffffffffffff04
[  484.805047] RAX: 00000000000028a1 RBX: 0000000000000000 RCX: 0000000000067f43

[  484.805049] RDX: 00007f1625a49ae0 RSI: 00007f1625a47760 RDI: 00007f1625a48640
[  484.805052] RBP: 00007ffe26fde680 R08: 00007f1625c4c740 R09: 0000000000000000
[  484.805054] R10: 00007ffe26fde3f0 R11: 0000000000000246 R12: 0000000000401980
[  484.805056] R13: 00007ffe26fe0a80 R14: 0000000000000000 R15: 0000000000000000
[  484.805058]  </IRQ>
[  484.805062] Code: 0f ab 02 49 81 c4 08 02 00 00 49 0f ab 04 24 48 89 df ff 15 9c ca 03 01 48 89 df e8 0c 05 1b 00 5b 41 5c 41 5d 5d c3 0f ff eb f5 <0f> ff eb f1 0f ff 66 66 2e 0f 1f 84 00 00 00 00 00 eb a0 66 66
[  484.805161] ---[ end trace dcc4ce8c0a8781e1 ]---
[  508.895507] NMI watchdog: enabled on all CPUs, permanently consumes one hw-PMU counter.

Quoted 8 lines

Quoted 6 lines

Thanks,
Mark.

Quoted 26 lines · Mark Rutland

Quoted 16 lines · Alexey Budankov

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 8 lines

Quoted 1 line

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.

Quoted 7 lines

Ok; that was the kind of thing I was concerned about.

What you say "strange stacks", what do you mean exactly?

I take it the kernel spewing backtraces in dmesg?

Can you dump those?

Here it is:

list_del corruption. prev->next should be ffff88c2c4654010, but was ffff88c31eb0c020

[  607.632813] ------------[ cut here ]------------
[  607.632816] kernel BUG at lib/list_debug.c:53!

[  607.635531] Call Trace:
[  607.635583]  list_del_event+0x1d7/0x210

Quoted 37 lines · Alexey Budankov

Quoted 26 lines · Mark Rutland

Quoted 16 lines · Alexey Budankov

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 8 lines

Quoted 1 line

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.

Quoted 7 lines

Ok; that was the kind of thing I was concerned about.

What you say "strange stacks", what do you mean exactly?

I take it the kernel spewing backtraces in dmesg?

Can you dump those?

Here it is:

Quoted 7 lines

list_del corruption. prev->next should be ffff88c2c4654010, but was ffff88c31eb0c020

[  607.632813] ------------[ cut here ]------------
[  607.632816] kernel BUG at lib/list_debug.c:53!

[  607.635531] Call Trace:
[  607.635583]  list_del_event+0x1d7/0x210

Given this patch changes how list_{del,add}_event() works, it's possible that this is a new bug.

I was going to try to test this on arm64, but I couldn't get the patch to apply. I had a go with v4.12-rc5, tip/perf/core, and tip/perf/urgent.

Which branch should I be using as the base?

Thanks,
Mark

Quoted 26 lines · Mark Rutland

Quoted 16 lines · Alexey Budankov

Quoted 15 lines · Alexey Budankov

Quoted 13 lines · Mark Rutland

Quoted 6 lines · Alexey Budankov

This series of patches continues v2 and addresses captured comments.

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.

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

Quoted 8 lines

Quoted 1 line

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.

Quoted 7 lines

Ok; that was the kind of thing I was concerned about.

What you say "strange stacks", what do you mean exactly?

I take it the kernel spewing backtraces in dmesg?

Can you dump those?

Here it is:

list_del corruption. prev->next should be ffff88c2c4654010, but was ffff88c31eb0c020

[  607.632813] ------------[ cut here ]------------
[  607.632816] kernel BUG at lib/list_debug.c:53!
[  607.632825] invalid opcode: 0000 [#1] SMP
[  607.632898] Modules linked in: fuse xt_CHECKSUM iptable_mangle ipt_MASQUERADE nf_nat_masquerade_ipv4 iptable_nat nf_nat_ipv4 nf_nat nf_conntrack_ipv4 nf_defrag_ipv4 xt_conntrack nf_conntrack libcrc32c tun bridge stp llc ebtable_filter ebtables ip6table_filter ip6_tables nfsv3 rpcsec_gss_krb5 nfsv4 arc4 md4 nls_utf8 cifs nfs ccm dns_resolver fscache rpcrdma ib_isert iscsi_target_mod ib_iser libiscsi scsi_transport_iscsi ib_srpt target_core_mod ib_srp scsi_transport_srp ib_ipoib rdma_ucm ib_ucm ib_uverbs ib_umad rdma_cm ib_cm iw_cm intel_rapl sb_edac x86_pkg_temp_thermal intel_powerclamp hfi1 coretemp crct10dif_pclmul crc32_pclmul ghash_clmulni_intel intel_cstate iTCO_wdt intel_uncore iTCO_vendor_support joydev rdmavt intel_rapl_perf i2c_i801 ib_core ipmi_ssif mei_me mei ipmi_si ipmi_devintf tpm_tis
[  607.633954]  lpc_ich pcspkr ipmi_msghandler acpi_pad tpm_tis_core shpchp tpm wmi acpi_power_meter nfsd auth_rpcgss nfs_acl lockd grace sunrpc mgag200 drm_kms_helper ttm drm igb crc32c_intel ptp pps_core dca i2c_algo_bit
[  607.634262] CPU: 271 PID: 28944 Comm: perf_fuzzer Not tainted 4.12.0-rc4+ #22
[  607.634363] Hardware name: Intel Corporation S7200AP/S7200AP, BIOS S72C610.86B.01.01.0190.080520162104 08/05/2016
[  607.634505] task: ffff88c2d5714000 task.stack: ffffa6f9352c8000
[  607.634597] RIP: 0010:__list_del_entry_valid+0x7b/0x90
[  607.634670] RSP: 0000:ffffa6f9352cbad0 EFLAGS: 00010046
[  607.634746] RAX: 0000000000000054 RBX: ffff88c2c4654000 RCX: 0000000000000000
[  607.634845] RDX: 0000000000000000 RSI: ffff88c33fdce168 RDI: ffff88c33fdce168
[  607.634944] RBP: ffffa6f9352cbad0 R08: 00000000fffffffe R09: 0000000000000600
[  607.635042] R10: 0000000000000005 R11: 0000000000000000 R12: ffff88c2e71ab200
[  607.635140] R13: ffff88c2c4654010 R14: 0000000000000001 R15: 0000000000000001
[  607.635240] FS:  0000000000000000(0000) GS:ffff88c33fdc0000(0000) knlGS:0000000000000000
[  607.635351] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  607.635431] CR2: 00000000026be1e4 CR3: 0000002488e09000 CR4: 00000000001407e0
[  607.635531] Call Trace:
[  607.635583]  list_del_event+0x1d7/0x210
[  607.635646]  ? perf_cgroup_attach+0x70/0x70
[  607.635711]  __perf_remove_from_context+0x3e/0x90
[  607.635783]  ? event_sched_out.isra.90+0x300/0x300
[  607.635854]  event_function_call+0xbf/0xf0
[  607.635918]  ? event_sched_out.isra.90+0x300/0x300
[  607.635991]  perf_remove_from_context+0x25/0x70
[  607.636060]  perf_event_release_kernel+0xda/0x250
[  607.636132]  ? __dentry_kill+0x10e/0x160
[  607.636192]  perf_release+0x10/0x20
[  607.636249]  __fput+0xdf/0x1e0
[  607.636299]  ____fput+0xe/0x10
[  607.636350]  task_work_run+0x83/0xb0
[  607.636408]  do_exit+0x2bc/0xbc0
[  607.636460]  ? page_add_file_rmap+0xaf/0x200
[  607.636526]  ? alloc_set_pte+0x115/0x4f0
[  607.636587]  do_group_exit+0x3f/0xb0
[  607.636644]  get_signal+0x1cc/0x5c0
[  607.636703]  do_signal+0x37/0x6a0
[  607.636758]  ? __perf_sw_event+0x4f/0x80
[  607.636821]  ? __do_page_fault+0x2e1/0x4d0
[  607.636885]  exit_to_usermode_loop+0x4c/0x92
[  607.636953]  prepare_exit_to_usermode+0x40/0x50
[  607.637023]  retint_user+0x8/0x13
[  607.640312] RIP: 0033:0x40f4a9
[  607.643500] RSP: 002b:00007ffc62d00668 EFLAGS: 00000206 ORIG_RAX: ffffffffffffff02
[  607.646678] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 000000000001100a

[  607.649777] RDX: 00007fd5dd25bae0 RSI: 00007fd5dd259760 RDI: 00007fd5dd25a640
[  607.652791] RBP: 00007ffc62d00680 R08: 00007fd5dd45e740 R09: 0000000000000000
[  607.655709] R10: 00007fd5dd45ea10 R11: 0000000000000246 R12: 0000000000401980
[  607.658530] R13: 00007ffc62d02a80 R14: 0000000000000000 R15: 0000000000000000
[  607.661249] Code: e8 3a f7 d8 ff 0f 0b 48 89 fe 31 c0 48 c7 c7 20 66 cb ac e8 27 f7 d8 ff 0f 0b 48 89 fe 31 c0 48 c7 c7 e0 65 cb ac e8 14 f7 d8 ff <0f> 0b 48 89 fe 31 c0 48 c7 c7 a8 65 cb ac e8 01 f7 d8 ff 0f 0b
[  607.666819] RIP: __list_del_entry_valid+0x7b/0x90 RSP: ffffa6f9352cbad0
[  607.683316] ---[ end trace 34244c35550e0713 ]---
[  607.691830] Fixing recursive fault but reboot is needed!

2:

[  467.942059] unchecked MSR access error: WRMSR to 0x711 (tried to write 0x00000000e8cc0055) at rIP: 0xffffffffac05fbd4 (native_write_msr+0x4/0x30)
[  467.942068] Call Trace:
[  467.942073]  <IRQ>
[  467.942094]  ? snbep_uncore_msr_enable_event+0x54/0x60 [intel_uncore]
[  467.942107]  uncore_pmu_event_start+0x9b/0x100 [intel_uncore]
[  467.942119]  uncore_pmu_event_add+0x235/0x3a0 [intel_uncore]
[  467.942126]  ? sched_clock+0xb/0x10
[  467.942132]  ? sched_clock_cpu+0x11/0xb0
[  467.942140]  event_sched_in.isra.100+0xdf/0x250
[  467.942145]  sched_in_group+0x210/0x390
[  467.942150]  ? sched_in_group+0x390/0x390
[  467.942155]  group_sched_in_flexible_callback+0x17/0x20
[  467.942160]  perf_cpu_tree_iterate+0x45/0x75
[  467.942165]  ctx_sched_in+0x97/0x110
[  467.942169]  perf_event_sched_in+0x77/0x80
[  467.942174]  ctx_resched+0x69/0xb0
[  467.942179]  __perf_event_enable+0x208/0x250
[  467.942184]  event_function+0x93/0xe0
[  467.942188]  remote_function+0x3b/0x50
[  467.942194]  flush_smp_call_function_queue+0x71/0x120
[  467.942200]  generic_smp_call_function_single_interrupt+0x13/0x30
[  467.942206]  smp_call_function_single_interrupt+0x27/0x40
[  467.942212]  call_function_single_interrupt+0x93/0xa0
[  467.942217] RIP: 0010:native_restore_fl+0x6/0x10
[  467.942220] RSP: 0000:ffff88c33ba03e00 EFLAGS: 00000206 ORIG_RAX: ffffffffffffff04
[  467.942224] RAX: ffff88c33c8dca08 RBX: ffff88c33c8dc928 RCX: 0000000000000017
[  467.942227] RDX: 0000000000000000 RSI: 0000000000000206 RDI: 0000000000000206
[  467.942229] RBP: ffff88c33ba03e00 R08: 0000000000000001 R09: 0000000000007151
[  467.942232] R10: 0000000000000000 R11: 000000000000005d R12: ffff88c33c8dca08
[  467.942234] R13: ffff88c33c8dc140 R14: 0000000000000001 R15: 00000000000001d8
[  467.942241]  _raw_spin_unlock_irqrestore+0x16/0x20
[  467.942245]  update_blocked_averages+0x2cf/0x4a0
[  467.942251]  rebalance_domains+0x4b/0x2b0
[  467.942256]  run_rebalance_domains+0x1d7/0x210
[  467.942260]  __do_softirq+0xd1/0x27f
[  467.942267]  irq_exit+0xe9/0x100
[  467.942271]  scheduler_ipi+0x8f/0x140
[  467.942275]  smp_reschedule_interrupt+0x29/0x30
[  467.942280]  reschedule_interrupt+0x93/0xa0
[  467.942284] RIP: 0010:native_safe_halt+0x6/0x10
[  467.942286] RSP: 0000:fffffffface03de0 EFLAGS: 00000246 ORIG_RAX: ffffffffffffff02
[  467.942291] RAX: 0000000000000000 RBX: fffffffface104c0 RCX: 0000000000000000
[  467.942293] RDX: 0000000000000000 RSI: 0000000000000000 RDI: 0000000000000000
[  467.942295] RBP: fffffffface03de0 R08: 0000006d2c5efae3 R09: 0000000000000000
[  467.942298] R10: 0000000000000201 R11: 0000000000000930 R12: 0000000000000000
[  467.942300] R13: fffffffface104c0 R14: 0000000000000000 R15: 0000000000000000
[  467.942302]  </IRQ>
[  467.942308]  default_idle+0x20/0x100
[  467.942313]  arch_cpu_idle+0xf/0x20
[  467.942317]  default_idle_call+0x2c/0x40
[  467.942321]  do_idle+0x158/0x1e0
[  467.942325]  cpu_startup_entry+0x71/0x80
[  467.942330]  rest_init+0x77/0x80
[  467.942338]  start_kernel+0x4a7/0x4c8
[  467.942342]  ? set_init_arg+0x5a/0x5a
[  467.942348]  ? early_idt_handler_array+0x120/0x120
[  467.942352]  x86_64_start_reservations+0x29/0x2b
[  467.942357]  x86_64_start_kernel+0x151/0x174
[  467.942363]  secondary_startup_64+0x9f/0x9f> 

Quoted 4 lines

Thanks,
Mark.

Hi,

Quoted 1 line · Alexey Budankov

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.

Quoted 4 lines

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,

Quoted 2 lines

Signed-off-by Alexey Budankov <[email protected]>

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

Quoted 5 lines

---
  include/linux/perf_event.h |  34 +++-
  kernel/events/core.c       | 386
+++++++++++++++++++++++++++++++++------------
  2 files changed, 315 insertions(+), 105 deletions(-)

<changelog goes here>

Quoted 19 lines

include/linux/perf_event.h +10 -0

index 24a6358..2c1dcf1 100644
@@ -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

include/linux/perf_event.h struct perf_event { · line 596

Quoted 10 lines

include/linux/perf_event.h +10 -0

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

Quoted 10 lines

include/linux/perf_event.h +1 -2

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

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

Quoted 10 lines

include/linux/perf_event.h +10 -0

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

Quoted 32 lines

include/linux/perf_event.h +1 -0

+
  	struct list_head		event_list;
  	int				nr_events;
  	int				nr_active;

kernel/events/core.c +11 -4

index bc63f8d..a3531f9 100644
@@ -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.
+ */

kernel/events/core.c static enum event_type_t · line 1486

Quoted 10 lines

kernel/events/core.c +10 -0

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

Quoted 5 lines

kernel/events/core.c +5 -0

+
+	while (*node) {
+		struct perf_event *node_event =	container_of(*node,
+				struct perf_event, group_node);
+

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1499

Quoted 10 lines

kernel/events/core.c +10 -0

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

Quoted 18 lines

kernel/events/core.c +11 -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);
+}
+
+/*
+ * 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.
+ */

kernel/events/core.c +4 -0

+static void
+perf_cpu_tree_delete(struct rb_root *tree, struct perf_event *event)
+{
+	WARN_ON_ONCE(!tree || !event);

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1526

Quoted 10 lines

kernel/events/core.c +10 -0

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

Quoted 66 lines

kernel/events/core.c +66 -0

+	}
+}
+
+/*
+ * 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;

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 5 lines

kernel/events/core.c +4 -0

+		}
+	}
+
+	return 0;
  }

If you need to iterate over every event, you can use the list that threads the whole tree.

Quoted 7 lines

/*

kernel/events/core.c +0 -0

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

kernel/events/core.c list_add_event(struct perf_event *event, · line 1623

Quoted 10 lines

kernel/events/core.c +3 -3

  	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?

Quoted 5 lines

kernel/events/core.c +0 -0

  	}
 

  	list_update_cgroup_event(event, ctx, true);

kernel/events/core.c +0 -0

@@ -1680,8 +1809,12 @@ list_del_event(struct perf_event *event,
 struct perf_event_context *ctx)

kernel/events/core.c list_del_event(struct perf_event *event, · line 1817

Quoted 10 lines

kernel/events/core.c +5 -2

 
  	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.

Quoted 20 lines · Mark Rutland

Quoted 19 lines · Alexey Budankov

kernel/events/core.c +19 -0

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

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 5 lines

kernel/events/core.c +4 -0

+		}
+	}
+
+	return 0;
 }

If you need to iterate over every event, you can use the list that threads the whole tree.

Could you please explain more on that?

Quoted 30 lines · Alexey Budankov

Quoted 20 lines · Mark Rutland

Quoted 19 lines · Alexey Budankov

kernel/events/core.c +19 -0

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

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 5 lines

kernel/events/core.c +4 -0

+		}
+	}
+
+	return 0;
  }

If you need to iterate over every event, you can use the list that threads the whole tree.

Quoted 1 line

Could you please explain more on that?

In Peter's original suggestion, we'd use a threaded tree rather than a tree of lists.

i.e. you'd have something like:

struct threaded_rb_node {
	struct rb_node   node;
	struct list_head head;
};

... with the tree and list covering all nodes, in the same order:

Tree:

      3
     / \
    /   \

1 5
/ \ / \
0 2 4 6

List:

0 - 1 - 2 - 3 - 4 - 5 - 6

... that way you can search using the tree, and iterate using the list, even when you wan to iterate over sub-lists.

Thanks,
Mark.

Quoted 36 lines · Mark Rutland

Quoted 30 lines · Alexey Budankov

Quoted 20 lines · Mark Rutland

Quoted 19 lines · Alexey Budankov

kernel/events/core.c +19 -0

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

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 5 lines

kernel/events/core.c +4 -0

+		}
+	}
+
+	return 0;
 }

If you need to iterate over every event, you can use the list that threads the whole tree.

Quoted 1 line

Could you please explain more on that?

In Peter's original suggestion, we'd use a threaded tree rather than a tree of lists.

Quoted 6 lines

i.e. you'd have something like:

struct threaded_rb_node {
	struct rb_node   node;
	struct list_head head;
};

Is this for every group leader?

Which objects does the head keep?

Quoted 39 lines · Alexey Budankov

Quoted 38 lines · Mark Rutland

Quoted 30 lines · Alexey Budankov

Quoted 20 lines · Mark Rutland

Quoted 19 lines · Alexey Budankov

kernel/events/core.c +19 -0

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

Quoted 8 lines

kernel/events/core.c static enum event_type_t get_event_type(struct perf_event *event) · line 1597

Quoted 5 lines

kernel/events/core.c +4 -0

+		}
+	}
+
+	return 0;
  }

If you need to iterate over every event, you can use the list that threads the whole tree.

Quoted 1 line

Could you please explain more on that?

In Peter's original suggestion, we'd use a threaded tree rather than a tree of lists.

i.e. you'd have something like:

Quoted 6 lines

Quoted 4 lines

struct threaded_rb_node {
	struct rb_node   node;
	struct list_head head;
};

Is this for every group leader?

Yes; *every* group leader would be directly in the threaded rb tree.

Quoted 2 lines

Which objects does the head keep?

Sorry, I'm not sure how to answer that. Did the above clarify?

If not, could you rephrase the question?

Thanks,
Mark.