Skip to contentSkip to conversation

perf: Store active software events in a hashlist

PATCH Superseded Frederic Weisbecker 3 participants 15 messages Apr 5, 2010 – Apr 8, 2010 perf events

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 perf: Store active software events in a hashlist

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

Cc Peter Zijlstra <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Paul Mackerras <[email protected]>
Cc Ingo Molnar <[email protected]>
---
 include/linux/perf_event.h |   12 +++
 kernel/perf_event.c        |  226 +++++++++++++++++++++++++++++++------------
 2 files changed, 175 insertions(+), 63 deletions(-)
include/linux/perf_event.h +12 -0
index 6e96cc8..03e87c4 100644
@@ -589,6 +589,14 @@ enum perf_group_flag {
 	PERF_GROUP_SOFTWARE = 0x1,
 };
 
+#define SWEVENT_HLIST_BITS	8
+#define SWEVENT_HLIST_SIZE	((1 << (SWEVENT_HLIST_BITS + 1)) - 1)
+
+struct swevent_hlist {
+	struct hlist_head	heads[SWEVENT_HLIST_SIZE];
+	struct rcu_head		rcu_head;
+};
+
 /**
  * struct perf_event - performance event kernel representation:
  */
@@ -597,6 +605,7 @@ struct perf_event {
 	struct list_head		group_entry;
 	struct list_head		event_entry;
 	struct list_head		sibling_list;
+	struct hlist_node		hlist_entry;
 	int				nr_siblings;
 	int				group_flags;
 	struct perf_event		*group_leader;
@@ -744,6 +753,9 @@ struct perf_cpu_context {
 	int				active_oncpu;
 	int				max_pertask;
 	int				exclusive;
+	struct swevent_hlist		*swevent_hlist;
+	struct mutex			hlist_mutex;
+	struct kref			hlist_refcount;
 
 	/*
 	 * Recursion avoidance:
kernel/perf_event.c +163 -63

315 lines not on this page · raw message

Signature · 1 line
1.6.2.3
maintainer
#1 lore raw
Quoted 5 lines · Frederic Weisbecker

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

Quoted 7 lines

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

So we have a hash-table per-cpu, each event takes a ref on the hash table, when the thing is empty we free it.

When the event->cpu == -1 (all cpus) we take a ref on all possible cpu's hash-table (should be online I figure, but that requires adding a hotplug handler).

Then on event enable/disable we actually add the event to the hash-table belonging to the cpu the event/task gets scheduled on, since each event can only ever be active on one cpu.

Right?

So looks good, altough I think we want to do that online/hotplug thing.

maintainer
#2 lore raw
Quoted 21 lines · Peter Zijlstra
Quoted 5 lines · Frederic Weisbecker

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

Quoted 7 lines

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

So we have a hash-table per-cpu, each event takes a ref on the hash table, when the thing is empty we free it.

When the event->cpu == -1 (all cpus) we take a ref on all possible cpu's hash-table (should be online I figure, but that requires adding a hotplug handler).

Quoted 7 lines

Then on event enable/disable we actually add the event to the hash-table belonging to the cpu the event/task gets scheduled on, since each event can only ever be active on one cpu.

Right?

So looks good, altough I think we want to do that online/hotplug thing.

Alternatively, you can simply but the hash table into the per-cpu structure and not allocate it, its only a single page (half a page if you use 32bit or actually use 8 bits.

#3 lore raw
Quoted 26 lines · Peter Zijlstra
Quoted 25 lines · Peter Zijlstra
Quoted 5 lines · Frederic Weisbecker

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

Quoted 7 lines

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

So we have a hash-table per-cpu, each event takes a ref on the hash table, when the thing is empty we free it.

When the event->cpu == -1 (all cpus) we take a ref on all possible cpu's hash-table (should be online I figure, but that requires adding a hotplug handler).

Then on event enable/disable we actually add the event to the hash-table belonging to the cpu the event/task gets scheduled on, since each event can only ever be active on one cpu.

Quoted 7 lines
Quoted 3 lines

Right?

So looks good, altough I think we want to do that online/hotplug thing.

Alternatively, you can simply but the hash table into the per-cpu structure and not allocate it, its only a single page (half a page if you use 32bit or actually use 8 bits.

As you prefer. This would indeed make it more simple, but that would also make these pages unused most of the time.

maintainer
#4 lore raw
Quoted 31 lines · Frederic Weisbecker
Quoted 30 lines · Peter Zijlstra
Quoted 28 lines · Peter Zijlstra
Quoted 5 lines · Frederic Weisbecker

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

Quoted 7 lines

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

So we have a hash-table per-cpu, each event takes a ref on the hash table, when the thing is empty we free it.

When the event->cpu == -1 (all cpus) we take a ref on all possible cpu's hash-table (should be online I figure, but that requires adding a hotplug handler).

Then on event enable/disable we actually add the event to the hash-table belonging to the cpu the event/task gets scheduled on, since each event can only ever be active on one cpu.

Right?

So looks good, altough I think we want to do that online/hotplug thing.

Quoted 7 lines
Quoted 3 lines

Alternatively, you can simply but the hash table into the per-cpu structure and not allocate it, its only a single page (half a page if you use 32bit or actually use 8 bits.

As you prefer. This would indeed make it more simple, but that would also make these pages unused most of the time.

True I suppose,.. have a go at that hotplug stuff, the only thing I worried about was that refcount stuff getting rather ugly.

#5 lore raw

PATCH v2 1/1 perf: Store active software events in a hashlist

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

v2: - Fix SWEVENT_HLIST_SIZE definition (and re-learn some basic
maths along the way)
- Only allocate hlist for online cpus, but keep track of the refcount on offline possible cpus too, so that we allocate it if needed when it becomes online.
- Drop the kref use as it's not adapted to our tricks anymore.

Cc Peter Zijlstra <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Paul Mackerras <[email protected]>
Cc Ingo Molnar <[email protected]>
---
 include/linux/perf_event.h |   12 ++
 kernel/perf_event.c        |  251 +++++++++++++++++++++++++++++++++-----------
 2 files changed, 200 insertions(+), 63 deletions(-)
include/linux/perf_event.h +12 -0
index 6e96cc8..bf896d0 100644
@@ -589,6 +589,14 @@ enum perf_group_flag {
 	PERF_GROUP_SOFTWARE = 0x1,
 };
 
+#define SWEVENT_HLIST_BITS	8
+#define SWEVENT_HLIST_SIZE	(1 << SWEVENT_HLIST_BITS)
+
+struct swevent_hlist {
+	struct hlist_head	heads[SWEVENT_HLIST_SIZE];
+	struct rcu_head		rcu_head;
+};
+
 /**
  * struct perf_event - performance event kernel representation:
  */
@@ -597,6 +605,7 @@ struct perf_event {
 	struct list_head		group_entry;
 	struct list_head		event_entry;
 	struct list_head		sibling_list;
+	struct hlist_node		hlist_entry;
 	int				nr_siblings;
 	int				group_flags;
 	struct perf_event		*group_leader;
@@ -744,6 +753,9 @@ struct perf_cpu_context {
 	int				active_oncpu;
 	int				max_pertask;
 	int				exclusive;
+	struct swevent_hlist		*swevent_hlist;
+	struct mutex			hlist_mutex;
+	int				hlist_refcount;
 
 	/*
 	 * Recursion avoidance:
kernel/perf_event.c +188 -63

352 lines not on this page · raw message

Signature · 1 line
1.6.2.3
#6 lore raw

Le jeudi 08 avril 2010 à 21:39 +0200, Frederic Weisbecker a écrit :

...

kernel/perf_event.c static void __cpuinit perf_event_init_cpu(int cpu) · line 5512

Quoted 7 lines
kernel/perf_event.c +3 -0
@@ -5401,6 +5507,16 @@ static void __cpuinit perf_event_init_cpu(int cpu)
 	spin_lock(&perf_resource_lock);
 	cpuctx->max_pertask = perf_max_events - perf_reserved_percpu;
 	spin_unlock(&perf_resource_lock);
+
+	mutex_lock(&cpuctx->hlist_mutex);
+	if (&cpuctx->hlist_refcount > 0) {
	if (cpuctx->hlist_refcount > 0)
Quoted 8 lines
kernel/perf_event.c +7 -0
+		struct swevent_hlist *hlist;
+
+		hlist = kzalloc(sizeof(*hlist), GFP_KERNEL);
+		WARN_ON_ONCE(!hlist);
+		rcu_assign_pointer(cpuctx->swevent_hlist, hlist);
+	}
+	mutex_unlock(&cpuctx->hlist_mutex);
 }
#7 lore raw
Quoted 4 lines · Eric Dumazet

Le jeudi 08 avril 2010 à 21:39 +0200, Frederic Weisbecker a écrit :

...

Quoted 10 lines

kernel/perf_event.c static void __cpuinit perf_event_init_cpu(int cpu) · line 5512

Quoted 7 lines
kernel/perf_event.c +3 -0
@@ -5401,6 +5507,16 @@ static void __cpuinit perf_event_init_cpu(int cpu)
 	spin_lock(&perf_resource_lock);
 	cpuctx->max_pertask = perf_max_events - perf_reserved_percpu;
 	spin_unlock(&perf_resource_lock);
+
+	mutex_lock(&cpuctx->hlist_mutex);
+	if (&cpuctx->hlist_refcount > 0) {
	if (cpuctx->hlist_refcount > 0)

Doh! Thanks, will fix.

Quoted 12 lines
Quoted 9 lines
kernel/perf_event.c +7 -0
+		struct swevent_hlist *hlist;
+
+		hlist = kzalloc(sizeof(*hlist), GFP_KERNEL);
+		WARN_ON_ONCE(!hlist);
+		rcu_assign_pointer(cpuctx->swevent_hlist, hlist);
+	}
+	mutex_unlock(&cpuctx->hlist_mutex);
 }
#8 lore raw
In reply to Peter Zijlstra
Quoted 21 lines · Peter Zijlstra
Quoted 5 lines · Frederic Weisbecker

Each time a software event triggers, we need to walk through the entire list of events from the current cpu and task contexts to retrieve a running perf event that matches.
We also need to check a matching perf event is actually counting.

Quoted 7 lines

This walk is wasteful and makes the event fast path scaling down with a growing number of events running on the same contexts.

To solve this, we store the running perf events in a hashlist to get an immediate access to them against their type:event_id when they trigger.

So we have a hash-table per-cpu, each event takes a ref on the hash table, when the thing is empty we free it.

When the event->cpu == -1 (all cpus) we take a ref on all possible cpu's hash-table (should be online I figure, but that requires adding a hotplug handler).

Quoted 5 lines

Then on event enable/disable we actually add the event to the hash-table belonging to the cpu the event/task gets scheduled on, since each event can only ever be active on one cpu.

Right?

Exactly.

Quoted 2 lines

So looks good, altough I think we want to do that online/hotplug thing.

That would let us allocate on online cpus instead of possibles? Yeah right.

maintainer
#9 lore raw
Quoted 6 lines · Frederic Weisbecker
Quoted 3 lines

So looks good, altough I think we want to do that online/hotplug thing.

That would let us allocate on online cpus instead of possibles? Yeah right.

Right, so if you want to go this route (and not simply embed it in the percpu data), the complication I thought of is that you want the refcount on offline cpus but not the allocation, since its very hard to reconstruct the number of events that had event->cpu == -1.

#10 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Frederic Weisbecker
Quoted 3 lines

So looks good, altough I think we want to do that online/hotplug thing.

Quoted 6 lines
Quoted 1 line

That would let us allocate on online cpus instead of possibles? Yeah right.

Right, so if you want to go this route (and not simply embed it in the percpu data), the complication I thought of is that you want the refcount on offline cpus but not the allocation, since its very hard to reconstruct the number of events that had event->cpu == -1.

Ok, right I can do that.

maintainer
#11 lore raw
In reply to Frederic Weisbecker

include/linux/perf_event.h enum perf_group_flag { · line 593

Quoted 2 lines · Frederic Weisbecker
include/linux/perf_event.h +2 -0
+#define SWEVENT_HLIST_BITS     8
+#define SWEVENT_HLIST_SIZE     ((1 << (SWEVENT_HLIST_BITS + 1)) - 1)

That seems to result in 9 bits worth, doesn't it?

#12 lore raw
Quoted 5 lines · Peter Zijlstra

include/linux/perf_event.h enum perf_group_flag { · line 593

Quoted 2 lines · Frederic Weisbecker
include/linux/perf_event.h +2 -0
+#define SWEVENT_HLIST_BITS     8
+#define SWEVENT_HLIST_SIZE     ((1 << (SWEVENT_HLIST_BITS + 1)) - 1)

That seems to result in 9 bits worth, doesn't it?

Oh right, I was confused, will zapp the + 1.

maintainer
#13 lore raw
Quoted 10 lines · Frederic Weisbecker
Quoted 5 lines · Peter Zijlstra

include/linux/perf_event.h enum perf_group_flag { · line 593

Quoted 2 lines · Frederic Weisbecker
include/linux/perf_event.h +2 -0
+#define SWEVENT_HLIST_BITS     8
+#define SWEVENT_HLIST_SIZE     ((1 << (SWEVENT_HLIST_BITS + 1)) - 1)

That seems to result in 9 bits worth, doesn't it?

Oh right, I was confused, will zapp the + 1.

Also, what you're computing seems to be a mask, not a size

So with BITS = 8, you want
SIZE = 1<<BITS = 256
MASK = SIZE-1 = 255

right?

#14 lore raw
Quoted 12 lines · Peter Zijlstra
Quoted 10 lines · Frederic Weisbecker
Quoted 5 lines · Peter Zijlstra

include/linux/perf_event.h enum perf_group_flag { · line 593

Quoted 2 lines · Frederic Weisbecker
include/linux/perf_event.h +2 -0
+#define SWEVENT_HLIST_BITS     8
+#define SWEVENT_HLIST_SIZE     ((1 << (SWEVENT_HLIST_BITS + 1)) - 1)

That seems to result in 9 bits worth, doesn't it?

Oh right, I was confused, will zapp the + 1.

Quoted 7 lines

Also, what you're computing seems to be a mask, not a size

So with BITS = 8, you want
SIZE = 1<<BITS = 256
MASK = SIZE-1 = 255

right?

Oh right... damn I suck in maths...