jump label: 2.6.38 updates

include/linux/jump_label.h extern void jump_label_unlock(void); · line 49

Quoted 11 lines · Jason Baron

include/linux/jump_label.h +5 -1

+struct jump_label_key {
+	int state;
+};
+
 #define JUMP_LABEL(key, label)			\
 do {						\
-	if (unlikely(*key))			\
+	if (unlikely(((struct jump_label_key *)key)->state))		\
 		goto label;			\
 } while (0)

Anything that uses JUMP_LABEL() should pass in a pointer to a struct jump_label_key. Hence, remove the typecast. That can only lead to hard to find bugs.

-- Steve

include/linux/jump_label.h +8 -15

+}
+
 extern struct jump_entry __start___jump_table[];
 extern struct jump_entry __stop___jump_table[];
 

@@ -42,11 +47,12 @@ struct jump_label_key {
 	int state;
 };
 
-#define JUMP_LABEL(key, label)			\
-do {						\
-	if (unlikely(((struct jump_label_key *)key)->state))		\
-		goto label;			\
-} while (0)
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	if (unlikely(key->state))
+		return true;
+	return false;
+}
 
 static inline int jump_label_enabled(struct jump_label_key *key)
 {

@@ -78,14 +84,4 @@ static inline void jump_label_unlock(void) {}
 
 #endif
 
-#define COND_STMT(key, stmt)					\
-do {								\
-	__label__ jl_enabled;					\
-	JUMP_LABEL_ELSE_ATOMIC_READ(key, jl_enabled);		\
-	if (0) {						\
-jl_enabled:							\
-		stmt;						\
-	}							\
-} while (0)
-
 #endif

include/linux/jump_label_ref.h +0 -0

index 8a76e89..5178696 100644
@@ -7,19 +7,23 @@
 struct jump_label_key_counter {
 	atomic_t ref;
 	struct jump_label_key key;

Quoted 6 lines · Jason Baron

include/linux/jump_label.h +0 -0

index 152f7de..0ad9c2e 100644
@@ -22,6 +22,11 @@ struct module;
 

include/linux/jump_label.h struct module; · line 27

Quoted 5 lines

include/linux/jump_label.h +3 -0

 #ifdef HAVE_JUMP_LABEL
 
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	return __static_branch(key);

Not very important, but __static_branch() would be more self-explained if it was called arch_static_branch().

Quoted 7 lines · Frederic Weisbecker

Quoted 6 lines · Jason Baron

include/linux/jump_label.h +0 -0

index 152f7de..0ad9c2e 100644
@@ -22,6 +22,11 @@ struct module;
 

Quoted 8 lines

include/linux/jump_label.h struct module; · line 27

Quoted 5 lines

include/linux/jump_label.h +3 -0

 #ifdef HAVE_JUMP_LABEL
 
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	return __static_branch(key);

Not very important, but __static_branch() would be more self-explained if it was called arch_static_branch().

I disagree, I think it is very important ;-)

Yes, the kernel has been moving to adding "arch_" to functions that are implemented dependently by different archs. Please change this to "arch_static_branch()".

Quoted 17 lines · Steven Rostedt

Quoted 7 lines · Frederic Weisbecker

Quoted 6 lines · Jason Baron

include/linux/jump_label.h +0 -0

index 152f7de..0ad9c2e 100644
@@ -22,6 +22,11 @@ struct module;
 

Quoted 8 lines

include/linux/jump_label.h struct module; · line 27

Quoted 5 lines

include/linux/jump_label.h +3 -0

 #ifdef HAVE_JUMP_LABEL
 
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	return __static_branch(key);

Not very important, but __static_branch() would be more self-explained if it was called arch_static_branch().

Quoted 6 lines

I disagree, I think it is very important ;-)

Yes, the kernel has been moving to adding "arch_" to functions that are implemented dependently by different archs. Please change this to "arch_static_branch()".

Indeed. This hugely simplifies knowing where to look and whose responsibility it is.

-hpa

include/linux/jump_label.h struct module; · line 27

Quoted 11 lines · Jason Baron

include/linux/jump_label.h +3 -0

index 152f7de..0ad9c2e 100644
@@ -22,6 +22,11 @@ struct module;
 
 #ifdef HAVE_JUMP_LABEL
 
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	return __static_branch(key);

Not very important, but __static_branch() would be more self-explained if it was called arch_static_branch().

Quoted 46 lines

include/linux/jump_label.h +8 -15

+}
+
 extern struct jump_entry __start___jump_table[];
 extern struct jump_entry __stop___jump_table[];
 

@@ -42,11 +47,12 @@ struct jump_label_key {
 	int state;
 };
 
-#define JUMP_LABEL(key, label)			\
-do {						\
-	if (unlikely(((struct jump_label_key *)key)->state))		\
-		goto label;			\
-} while (0)
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	if (unlikely(key->state))
+		return true;
+	return false;
+}
 
 static inline int jump_label_enabled(struct jump_label_key *key)
 {

@@ -78,14 +84,4 @@ static inline void jump_label_unlock(void) {}
 
 #endif
 
-#define COND_STMT(key, stmt)					\
-do {								\
-	__label__ jl_enabled;					\
-	JUMP_LABEL_ELSE_ATOMIC_READ(key, jl_enabled);		\
-	if (0) {						\
-jl_enabled:							\
-		stmt;						\
-	}							\
-} while (0)
-
 #endif

include/linux/jump_label_ref.h +0 -0

index 8a76e89..5178696 100644
@@ -7,19 +7,23 @@
 struct jump_label_key_counter {
 	atomic_t ref;
 	struct jump_label_key key;

include/linux/jump_label_ref.h line 17

Quoted 10 lines

include/linux/jump_label_ref.h +5 -2

-}
+};
 
 #ifdef HAVE_JUMP_LABEL
 
-#define JUMP_LABEL_ELSE_ATOMIC_READ(key, label, counter) JUMP_LABEL(key, label)
+static __always_inline bool static_branch_else_atomic_read(struct jump_label_key *key, atomic_t *count)
+{
+	return __static_branch(key);
+}

How about having only static_branch() but the key would be handled only by ways of get()/put().

Simple boolean key enablement would work in this scheme as well as branches based on refcount. So that the users could avoid maintaining both key and count, this would be transparently handled by the jump label API.

Or am I missing something?

Introduce:

static __always_inline bool static_branch(struct jump_label_key *key)

to replace the old JUMP_LABEL(key, label) macro.

The new static_branch(), simplifies the usage of jump labels. Since, static_branch() returns a boolean, it can be used as part of an if() construct. It also, allows us to drop the 'label' argument from the prototype. Its probably best understood with an example, here is the part of the patch that converts the tracepoints to use unlikely_switch():

include/linux/tracepoint.h +1 -3

@@ -146,9 +146,7 @@ static inline void tracepoint_update_probe_range(struct tracepoint *begin,
  	extern struct tracepoint __tracepoint_##name;			\
  	static inline void trace_##name(proto)				\
  	{								\
-		JUMP_LABEL(&__tracepoint_##name.key, do_trace);		\
-		return;							\
-do_trace:								\
+		if (static_branch(&__tracepoint_##name.key))		\
  			__DO_TRACE(&__tracepoint_##name,		\
  				TP_PROTO(data_proto),			\
  				TP_ARGS(data_args));			\

I analyzed the code produced by static_branch(), and it seems to be at least as good as the code generated by the JUMP_LABEL(). As a reminder, we get a single nop in the fastpath for -02. But will often times get a 'double jmp' in the -Os case. That is, 'jmp 0', followed by a jmp around the disabled code. We believe that future gcc tweaks to allow block re-ordering in the -Os, will solve the -Os case in the future.

I also saw a 1-2% tbench throughput improvement when compiling with jump labels.

This patch also addresses a build issue that Tetsuo Handa reported where gcc v3.3 currently chokes on compiling 'dynamic debug':

include/net/inet_connection_sock.h: In function `inet_csk_reset_xmit_timer':
include/net/inet_connection_sock.h:236: error: duplicate label declaration do_printk' include/net/inet_connection_sock.h:219: error: this is a previous declaration include/net/inet_connection_sock.h:236: error: duplicate label declaration out' include/net/inet_connection_sock.h:219: error: this is a previous declaration include/net/inet_connection_sock.h:236: error: duplicate label do_printk' include/net/inet_connection_sock.h:236: error: duplicate label out'

Thanks to H. Peter Anvin for suggesting this improved syntax.

Suggested-by H. Peter Anvin<[email protected]>

Signed-off-by Jason Baron<[email protected]>

Tested-by Tetsuo Handa<[email protected]>

---
  arch/sparc/include/asm/jump_label.h |   25 ++++++++++++++-----------
  arch/x86/include/asm/jump_label.h   |   22 +++++++++++++---------
  arch/x86/kernel/jump_label.c        |    2 +-
  include/linux/dynamic_debug.h       |   18 ++++--------------
  include/linux/jump_label.h          |   26 +++++++++++---------------
  include/linux/jump_label_ref.h      |   18 +++++++++++-------
  include/linux/perf_event.h          |   26 +++++++++++++-------------
  include/linux/tracepoint.h          |    4 +---
  kernel/jump_label.c                 |    2 +-
  9 files changed, 69 insertions(+), 74 deletions(-)

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Quoted 3 lines

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon.

From: Steven Rostedt <[email protected]>
Date: Wed, 05 Jan 2011 12:43:59 -0500

Quoted 5 lines · David Daney

Quoted 3 lines

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Quoted 2 lines

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon.

I totally disagree with this assesment. Implementing jump label for sparc64 as early as possible found so much broken stuff that otherwise would have merged in before any other architecture tried supporting it.

Quoted 2 lines · David Daney

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon. This change really needs to get in, and IMO, it is more critical to clean up the jump label code than to have other archs implementing it.

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · David Daney

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Quoted 5 lines

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon. This change really needs to get in, and IMO, it is more critical to clean up the jump label code than to have other archs implementing it.

Ralf is really good... perhaps we can get the conflicts resolved?

Quoted 12 lines · H. Peter Anvin

Quoted 10 lines · Steven Rostedt

Quoted 2 lines · David Daney

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon. This change really needs to get in, and IMO, it is more critical to clean up the jump label code than to have other archs implementing it.

Quoted 1 line

Ralf is really good... perhaps we can get the conflicts resolved?

Yep, the best Git-ish way to handle that is to resolve the conflicts whenever they happen - i.e. whoever merges his tree upstream later. No need for anyone to 'wait' or undo anything.

Quoted 15 lines · Ingo Molnar

Quoted 12 lines · H. Peter Anvin

Quoted 10 lines · Steven Rostedt

Quoted 2 lines · David Daney

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon. This change really needs to get in, and IMO, it is more critical to clean up the jump label code than to have other archs implementing it.

Quoted 6 lines

Quoted 1 line

Ralf is really good... perhaps we can get the conflicts resolved?

Yep, the best Git-ish way to handle that is to resolve the conflicts whenever they happen - i.e. whoever merges his tree upstream later. No need for anyone to 'wait' or undo anything.

There will be no git conflicts, as the affected files are disjoint.

Quoted 23 lines · David Daney

Quoted 21 lines · Ingo Molnar

Quoted 6 lines · H. Peter Anvin

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · David Daney

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Quoted 7 lines

Quoted 5 lines

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon. This change really needs to get in, and IMO, it is more critical to clean up the jump label code than to have other archs implementing it.

Ralf is really good... perhaps we can get the conflicts resolved?

Yep, the best Git-ish way to handle that is to resolve the conflicts whenever they happen - i.e. whoever merges his tree upstream later. No need for anyone to 'wait' or undo anything.

Quoted 1 line

There will be no git conflicts, as the affected files are disjoint.

I regularly resolve semantic conflicts in merge commits - or in the first followup commit.

But I am guessing that neither you, nor Linus, regularly build MIPS kernels with GCC-4.5.x *and* jump label support enabled. So how would such semantic conflict ever be detected? I would expect the conflict to first occur when Linus pulls Ralf's tree.

I don't expect anybody to magically fix such things, so whatever happens, I will test it and submit patches if required.

Quoted 26 lines · Ingo Molnar

Quoted 23 lines · David Daney

Quoted 21 lines · Ingo Molnar

Quoted 6 lines · H. Peter Anvin

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · David Daney

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

Quoted 7 lines

Quoted 5 lines

Can you disable that support for now? As Linus said at Kernel Summit, other archs jumped too quickly onto the jump label band wagon. This change really needs to get in, and IMO, it is more critical to clean up the jump label code than to have other archs implementing it.

Ralf is really good... perhaps we can get the conflicts resolved?

Yep, the best Git-ish way to handle that is to resolve the conflicts whenever they happen - i.e. whoever merges his tree upstream later. No need for anyone to 'wait' or undo anything.

Quoted 5 lines

Quoted 1 line

There will be no git conflicts, as the affected files are disjoint.

I regularly resolve semantic conflicts in merge commits - or in the first followup commit.

But I am guessing that neither you, nor Linus, regularly build MIPS kernels with GCC-4.5.x *and* jump label support enabled. [...]

[...] So how would such semantic conflict ever be detected? I would expect the conflict to first occur when Linus pulls Ralf's tree.

Quoted 66 lines · Jason Baron

Introduce:

static __always_inline bool static_branch(struct jump_label_key *key)

to replace the old JUMP_LABEL(key, label) macro.

The new static_branch(), simplifies the usage of jump labels. Since, static_branch() returns a boolean, it can be used as part of an if() construct. It also, allows us to drop the 'label' argument from the prototype. Its probably best understood with an example, here is the part of the patch that converts the tracepoints to use unlikely_switch():

include/linux/tracepoint.h +1 -3

@@ -146,9 +146,7 @@ static inline void tracepoint_update_probe_range(struct tracepoint *begin,
  	extern struct tracepoint __tracepoint_##name;			\
  	static inline void trace_##name(proto)				\
  	{								\
-		JUMP_LABEL(&__tracepoint_##name.key, do_trace);		\
-		return;							\
-do_trace:								\
+		if (static_branch(&__tracepoint_##name.key))		\
  			__DO_TRACE(&__tracepoint_##name,		\
  				TP_PROTO(data_proto),			\
  				TP_ARGS(data_args));			\

I analyzed the code produced by static_branch(), and it seems to be at least as good as the code generated by the JUMP_LABEL(). As a reminder, we get a single nop in the fastpath for -02. But will often times get a 'double jmp' in the -Os case. That is, 'jmp 0', followed by a jmp around the disabled code. We believe that future gcc tweaks to allow block re-ordering in the -Os, will solve the -Os case in the future.

I also saw a 1-2% tbench throughput improvement when compiling with jump labels.

This patch also addresses a build issue that Tetsuo Handa reported where gcc v3.3 currently chokes on compiling 'dynamic debug':

include/net/inet_connection_sock.h: In function `inet_csk_reset_xmit_timer':
include/net/inet_connection_sock.h:236: error: duplicate label declaration do_printk' include/net/inet_connection_sock.h:219: error: this is a previous declaration include/net/inet_connection_sock.h:236: error: duplicate label declaration out' include/net/inet_connection_sock.h:219: error: this is a previous declaration include/net/inet_connection_sock.h:236: error: duplicate label do_printk' include/net/inet_connection_sock.h:236: error: duplicate label out'

Thanks to H. Peter Anvin for suggesting this improved syntax.

Suggested-by H. Peter Anvin<[email protected]>

Signed-off-by Jason Baron<[email protected]>

Tested-by Tetsuo Handa<[email protected]>

---
  arch/sparc/include/asm/jump_label.h |   25 ++++++++++++++-----------
  arch/x86/include/asm/jump_label.h   |   22 +++++++++++++---------
  arch/x86/kernel/jump_label.c        |    2 +-
  include/linux/dynamic_debug.h       |   18 ++++--------------
  include/linux/jump_label.h          |   26 +++++++++++---------------
  include/linux/jump_label_ref.h      |   18 +++++++++++-------
  include/linux/perf_event.h          |   26 +++++++++++++-------------
  include/linux/tracepoint.h          |    4 +---
  kernel/jump_label.c                 |    2 +-
  9 files changed, 69 insertions(+), 74 deletions(-)

[...]

This patch will conflict with the MIPS jump label support that Ralf has queued up for 2.6.38.

David Daney

Introduce:

static __always_inline bool static_branch(struct jump_label_key *key)

to replace the old JUMP_LABEL(key, label) macro.

The new static_branch(), simplifies the usage of jump labels. Since, static_branch() returns a boolean, it can be used as part of an if() construct. It also, allows us to drop the 'label' argument from the prototype. Its probably best understood with an example, here is the part of the patch that converts the tracepoints to use unlikely_switch():

I analyzed the code produced by static_branch(), and it seems to be at least as good as the code generated by the JUMP_LABEL(). As a reminder, we get a single nop in the fastpath for -02. But will often times get a 'double jmp' in the -Os case. That is, 'jmp 0', followed by a jmp around the disabled code. We believe that future gcc tweaks to allow block re-ordering in the -Os, will solve the -Os case in the future.

I also saw a 1-2% tbench throughput improvement when compiling with jump labels.

This patch also addresses a build issue that Tetsuo Handa reported where gcc v3.3 currently chokes on compiling 'dynamic debug':

Introduce:

static __always_inline bool static_branch(struct jump_label_key *key)

to replace the old JUMP_LABEL(key, label) macro.

The new static_branch(), simplifies the usage of jump labels. Since, static_branch() returns a boolean, it can be used as part of an if() construct. It also, allows us to drop the 'label' argument from the prototype. Its probably best understood with an example, here is the part of the patch that converts the tracepoints to use unlikely_switch():

Hi,

The first patch uses the storage space of the jump label key address as a pointer into the update table. In this way, we can find all the addresses that need to be updated without hashing.

The second patch introduces:

static __always_inline bool static_branch(struct jump_label_key *key);

instead of the old JUMP_LABEL(key, label) macro.

In this way, jump labels become really easy to use:

Define:

        struct jump_label_key jump_key;

Can be used as:

if (static_branch(&jump_key))
do unlikely code

enable/disale via:

        jump_label_enable(&jump_key);
        jump_label_disable(&jump_key);

that's it!

For perf, which also uses jump labels, I've left the reference counting out of the jump label layer, thus removing the 'jump_label_inc()' and 'jump_label_dec()' interface. Hopefully, this is a more palatable solution.

Quoted 30 lines · Jason Baron

Hi,

The first patch uses the storage space of the jump label key address as a pointer into the update table. In this way, we can find all the addresses that need to be updated without hashing.

The second patch introduces:

static __always_inline bool static_branch(struct jump_label_key *key);

instead of the old JUMP_LABEL(key, label) macro.

In this way, jump labels become really easy to use:

Define:

        struct jump_label_key jump_key;

Can be used as:

if (static_branch(&jump_key))
do unlikely code

enable/disale via:

        jump_label_enable(&jump_key);
        jump_label_disable(&jump_key);

that's it!

Quoted 3 lines

For perf, which also uses jump labels, I've left the reference counting out of the jump label layer, thus removing the 'jump_label_inc()' and 'jump_label_dec()' interface. Hopefully, this is a more palatable solution.

Right, lets go with this. Maybe we'll manage to come up with something saner than _else_atomic_read(), but for now its an improvement over what we have.

Thoughts ?

Quoted 2 lines · Mathieu Desnoyers

Thoughts ?

#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)

(quoted diff) +6 -1

+
+struct jump_label_key {
+       void *ptr;
+};
 
 struct jump_label_entry {
        struct hlist_node hlist;
        struct jump_entry *table;
-       int nr_entries;
        /* hang modules off here */
        struct hlist_head modules;
        unsigned long key;
+       u32 nr_entries;
+       int refcount;
 };

#else

(quoted diff) +3 -0

+struct jump_label_key {
+       int state;
+};

#endif

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

Then the enabled case uses if (atomic_inc_return(&key->ptr->refcount) == 1), and the disabled atomic_inc(&key->state).

a bit of history...

For the disabled jump label case, we didn't want to incur an atomic_read() to check if the branch was enabled.

So, I separated the API, to have one for the non-atomic case, and one for the atomic case. Nobody liked that.

So now, I'm proposing to leave the core API based around a non-atomic variable, and have any callers that want to use this atomic interface, to call into the non-atomic interface. If another user besides perf wants to use the same type of atomic interface, we can re-visit the decsion?

Quoted 31 lines · Peter Zijlstra

Quoted 2 lines · Mathieu Desnoyers

Thoughts ?

#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)

(quoted diff) +6 -1

+
+struct jump_label_key {
+       void *ptr;
+};
 
 struct jump_label_entry {
        struct hlist_node hlist;
        struct jump_entry *table;
-       int nr_entries;
        /* hang modules off here */
        struct hlist_head modules;
        unsigned long key;
+       u32 nr_entries;
+       int refcount;
 };

#else

(quoted diff) +3 -0

+struct jump_label_key {
+       int state;
+};

#endif

Quoted 6 lines

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

Then the enabled case uses if (atomic_inc_return(&key->ptr->refcount) == 1), and the disabled atomic_inc(&key->state).

a bit of history...

For the disabled jump label case, we didn't want to incur an atomic_read() to check if the branch was enabled.

So, I separated the API, to have one for the non-atomic case, and one for the atomic case. Nobody liked that.

So now, I'm proposing to leave the core API based around a non-atomic variable, and have any callers that want to use this atomic interface, to call into the non-atomic interface. If another user besides perf wants to use the same type of atomic interface, we can re-visit the decsion?

thanks,

-Jason

Quoted 2 lines · Mathieu Desnoyers

Thoughts ?

#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)

(quoted diff) +6 -1

+
+struct jump_label_key {
+       void *ptr;
+};
 
 struct jump_label_entry {
        struct hlist_node hlist;
        struct jump_entry *table;
-       int nr_entries;
        /* hang modules off here */
        struct hlist_head modules;
        unsigned long key;
+       u32 nr_entries;
+       int refcount;
 };

#else

(quoted diff) +3 -0

+struct jump_label_key {
+       int state;
+};

#endif

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

Then the enabled case uses if (atomic_inc_return(&key->ptr->refcount) == 1), and the disabled atomic_inc(&key->state).

Quoted 27 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 2 lines · Mathieu Desnoyers

Thoughts ?

#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)

(quoted diff) +6 -1

+
+struct jump_label_key {
+       void *ptr;
+};
 
 struct jump_label_entry {
        struct hlist_node hlist;
        struct jump_entry *table;
-       int nr_entries;
        /* hang modules off here */
        struct hlist_head modules;
        unsigned long key;
+       u32 nr_entries;
+       int refcount;
 };

#else

(quoted diff) +3 -0

+struct jump_label_key {
+       int state;
+};

Quoted 8 lines

#endif

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

Then the enabled case uses if (atomic_inc_return(&key->ptr->refcount) == 1), and the disabled atomic_inc(&key->state).

OK, by "enabled" you mean #if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL), and "disabled", the #else.

I guess the only downside is the extra volatile for the atomic_read for the fallback case, which is not really much of problem realistically
speaking: anyway, the volatile is a good thing to have in the fallback case to force the compiler to re-read the variable. Let's go with your idea.

Thanks,

Mathieu

Quoted 48 lines · Mathieu Desnoyers

Quoted 27 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 2 lines · Mathieu Desnoyers

Thoughts ?

#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)

(quoted diff) +6 -1

+
+struct jump_label_key {
+       void *ptr;
+};
 
 struct jump_label_entry {
        struct hlist_node hlist;
        struct jump_entry *table;
-       int nr_entries;
        /* hang modules off here */
        struct hlist_head modules;
        unsigned long key;
+       u32 nr_entries;
+       int refcount;
 };

#else

(quoted diff) +3 -0

+struct jump_label_key {
+       int state;
+};

Quoted 8 lines

#endif

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

Then the enabled case uses if (atomic_inc_return(&key->ptr->refcount) == 1), and the disabled atomic_inc(&key->state).

OK, by "enabled" you mean #if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL), and "disabled", the #else.

I guess the only downside is the extra volatile for the atomic_read for the fallback case, which is not really much of problem realistically
speaking: anyway, the volatile is a good thing to have in the fallback case to force the compiler to re-read the variable. Let's go with your idea.

Thanks,

Quoted 2 lines

Mathieu

ok, I'll try and re-spin the interface based around atomic_t, if we are all agreed...there was also a circular dependency issue with atomic.h including kernel.h which included jump_label.h, and that was why we had a separate, jump_label_ref.h header file, but hopefully I can be resolve that in a clean way.

thanks,

-Jason

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

Quoted 3 lines · Peter Zijlstra

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

So I had a bit of a poke at this because I didn't quite understand why all that stuff was as it was. I applied both Jason's patches and then basically rewrote kernel/jump_label.c just for kicks ;-)

I haven't tried compiling this, let alone running it, but provided I didn't actually forget anything the storage per key is now 16 bytes when modules are disabled and 24 * (1 + mods) bytes for when they are enabled. The old code had 64 + 40 * mods bytes.

I still need to clean up the static_branch_else bits and look at !x86 aside from the already mentioned bits.. but what do people think?

 15 files changed, 333 insertions(+), 456 deletions(-)

Quoted 3 lines · Peter Zijlstra

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

So I had a bit of a poke at this because I didn't quite understand why all that stuff was as it was. I applied both Jason's patches and then basically rewrote kernel/jump_label.c just for kicks ;-)

I haven't tried compiling this, let alone running it, but provided I didn't actually forget anything the storage per key is now 16 bytes when modules are disabled and 24 * (1 + mods) bytes for when they are enabled. The old code had 64 + 40 * mods bytes.

I still need to clean up the static_branch_else bits and look at !x86 aside from the already mentioned bits.. but what do people think?

---

Quoted 14 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

So I had a bit of a poke at this because I didn't quite understand why all that stuff was as it was. I applied both Jason's patches and then basically rewrote kernel/jump_label.c just for kicks ;-)

I haven't tried compiling this, let alone running it, but provided I didn't actually forget anything the storage per key is now 16 bytes when modules are disabled and 24 * (1 + mods) bytes for when they are enabled. The old code had 64 + 40 * mods bytes.

Quoted 4 lines

I still need to clean up the static_branch_else bits and look at !x86 aside from the already mentioned bits.. but what do people think?

---

Generally, I really like this! Its the direction I think the jump label code should be going. The complete removal of the hash table, makes the design a lot better and simpler. We just need to get some of the details cleaned up, and of course we need this to compile :) But I don't see any fundamental problems with this approach.

Things that still need to be sorted out:

1) Since jump_label.h, are included in kernel.h, (indirectly via the dynamic_debug.h) the atomic_t definitions could be problematic, since atomic.h includes kernel.h indirectly...so we might need some header magic.

2) I had some code to disallow writing to module __init section, by setting the 'key' value to 0, after the module->init was run, but before, the memory was freed. And then I check for a non-zero key value when the jump label is updated. In this way we can't corrupt some random piece of memory. I had this done via the 'MODULE_STATE_LIVE' notifier.

3) For 'jump_label_enable()' 'jump_label_disable()' in the tracepoint code, I'm not sure that there is an enable for each disable. So i'm not sure if a refcount would work there. But we can fix this by first checking 'jump_label_enabled()' before calling 'jump_label_eanble()' or jump_label_ref(). This is safe b/c the the tracepoint code is protected using the tracepoint_mutex.

Quoted 28 lines · Jason Baron

Quoted 14 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

So I had a bit of a poke at this because I didn't quite understand why all that stuff was as it was. I applied both Jason's patches and then basically rewrote kernel/jump_label.c just for kicks ;-)

I haven't tried compiling this, let alone running it, but provided I didn't actually forget anything the storage per key is now 16 bytes when modules are disabled and 24 * (1 + mods) bytes for when they are enabled. The old code had 64 + 40 * mods bytes.

Quoted 4 lines

I still need to clean up the static_branch_else bits and look at !x86 aside from the already mentioned bits.. but what do people think?

---

Generally, I really like this! Its the direction I think the jump label code should be going. The complete removal of the hash table, makes the design a lot better and simpler. We just need to get some of the details cleaned up, and of course we need this to compile :) But I don't see any fundamental problems with this approach.

Things that still need to be sorted out:

Quoted 4 lines

1) Since jump_label.h, are included in kernel.h, (indirectly via the dynamic_debug.h) the atomic_t definitions could be problematic, since atomic.h includes kernel.h indirectly...so we might need some header magic.

Yes, I remember running into that when I did the jump_label_ref stuff, some head-scratching is in order there.

Quoted 5 lines

2) I had some code to disallow writing to module __init section, by setting the 'key' value to 0, after the module->init was run, but before, the memory was freed. And then I check for a non-zero key value when the jump label is updated. In this way we can't corrupt some random piece of memory. I had this done via the 'MODULE_STATE_LIVE' notifier.

AH! I wondered what that was about.. that wouldn't work now since we actually rely on iter->key to remain what it was.

Quoted 34 lines · Peter Zijlstra

Quoted 32 lines · Jason Baron

Quoted 14 lines · Peter Zijlstra

Quoted 3 lines · Peter Zijlstra

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

So I had a bit of a poke at this because I didn't quite understand why all that stuff was as it was. I applied both Jason's patches and then basically rewrote kernel/jump_label.c just for kicks ;-)

I haven't tried compiling this, let alone running it, but provided I didn't actually forget anything the storage per key is now 16 bytes when modules are disabled and 24 * (1 + mods) bytes for when they are enabled. The old code had 64 + 40 * mods bytes.

Quoted 4 lines

I still need to clean up the static_branch_else bits and look at !x86 aside from the already mentioned bits.. but what do people think?

---

Generally, I really like this! Its the direction I think the jump label code should be going. The complete removal of the hash table, makes the design a lot better and simpler. We just need to get some of the details cleaned up, and of course we need this to compile :) But I don't see any fundamental problems with this approach.

Things that still need to be sorted out:

1) Since jump_label.h, are included in kernel.h, (indirectly via the dynamic_debug.h) the atomic_t definitions could be problematic, since atomic.h includes kernel.h indirectly...so we might need some header magic.

Quoted 3 lines

Yes, I remember running into that when I did the jump_label_ref stuff, some head-scratching is in order there.

yes. i suspect this might be the hardest bit of this...

I remember that atomic_t is defined in types.h now rather than atomic.h. Any reason why you should keep including atomic.h from jump_label.h ?

Quoted 3 lines

I remember that atomic_t is defined in types.h now rather than atomic.h. Any reason why you should keep including atomic.h from jump_label.h ?

Ooh, shiny.. we could probably move the few atomic_{read,inc,dec} users in jump_label.h into out of line functions and have this sorted.

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines

I remember that atomic_t is defined in types.h now rather than atomic.h. Any reason why you should keep including atomic.h from jump_label.h ?

Ooh, shiny.. we could probably move the few atomic_{read,inc,dec} users in jump_label.h into out of line functions and have this sorted.

inc and dec sure, but atomic_read() for the disabled case needs to be inline....

Quoted 9 lines · Jason Baron

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines

I remember that atomic_t is defined in types.h now rather than atomic.h. Any reason why you should keep including atomic.h from jump_label.h ?

Ooh, shiny.. we could probably move the few atomic_{read,inc,dec} users in jump_label.h into out of line functions and have this sorted.

Quoted 2 lines

inc and dec sure, but atomic_read() for the disabled case needs to be inline....

D'0h yes of course, I was thinking about jump_label_enabled(), but there's still the static_branch() implementation to consider.

We could of course cheat implement our own version of atomic_read() in order to avoid the whole header mess, but that's not pretty at all

We could of course cheat implement our own version of atomic_read() in order to avoid the whole header mess, but that's not pretty at all

Quoted 2 lines · Peter Zijlstra

We could of course cheat implement our own version of atomic_read() in order to avoid the whole header mess, but that's not pretty at all

Oh God please no! ;)

atomic_read() is implemented per arch.

Quoted 2 lines · Peter Zijlstra

We could of course cheat implement our own version of atomic_read() in order to avoid the whole header mess, but that's not pretty at all

Oh God please no! ;)

atomic_read() is implemented per arch.

blackfin:
#define atomic_read(v)  __raw_uncached_fetch_asm(&(v)->counter)

blackfin, seems to be doing quite a lot. Not sure if it is required, but that may need a bit of investigating to understand why it does the raw_uncached thing.

mn10300:
#define atomic_read(v) ((v)->counter)

tile:
static inline int atomic_read(const atomic_t *v)

{
       return v->counter;
}

So all but a few have basically (as you said on IRC) #define atomic_read(v) ACCESS_ONCE(v)

Those few are blackfin, s390, powerpc and tile.

s390 probably doesn't need that much of a big hammer with atomic_read() (unless it uses it in its own arch that expects it to be such).

powerpc could probably be converted to just the volatile code as everything else. Not sure why it did it that way. To be different?

blackfin, seems to be doing quite a lot. Not sure if it is required, but that may need a bit of investigating to understand why it does the raw_uncached thing.

From what I can tell its flushing its write cache, invalidating its

Maybe we could move the atomic_read() out of atomic and make it a standard inline for all (in kernel.h)?

Quoted 3 lines · Steven Rostedt

blackfin, seems to be doing quite a lot. Not sure if it is required, but that may need a bit of investigating to understand why it does the raw_uncached thing.

From what I can tell its flushing its write cache, invalidating its d-cache and then issue the read, something which is _way_ overboard.

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines · Steven Rostedt

blackfin, seems to be doing quite a lot. Not sure if it is required, but that may need a bit of investigating to understand why it does the raw_uncached thing.

From what I can tell its flushing its write cache, invalidating its d-cache and then issue the read, something which is _way_ overboard.

not when the cores in a SMP system lack cache coherency

Quoted 6 lines · Mike Frysinger

Quoted 5 lines · Peter Zijlstra

Quoted 3 lines · Steven Rostedt

blackfin, seems to be doing quite a lot. Not sure if it is required, but that may need a bit of investigating to understand why it does the raw_uncached thing.

Quoted 4 lines

Quoted 2 lines

From what I can tell its flushing its write cache, invalidating its d-cache and then issue the read, something which is _way_ overboard.

not when the cores in a SMP system lack cache coherency

But atomic_read() is completely unordered, so even on a non-coherent system a regular read should suffice, any old value is correct.

The only problem would be when you could get cache aliasing and read something totally unrelated.

Quoted 2 lines

So all but a few have basically (as you said on IRC) #define atomic_read(v) ACCESS_ONCE(v)

ACCESS_ONCE(v->counter), but yeah :-)

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines

So all but a few have basically (as you said on IRC) #define atomic_read(v) ACCESS_ONCE(v)

ACCESS_ONCE(v->counter), but yeah :-)

I maintain an out-of-tree architecture where that isn't the case unfortunately [1]. Not expecting any special favours for being out-of-tree of course, but just thought I would add that data point.

[1] Our atomic operations go around the cache rather than through it, so the value of an atomic cannot be read with a normal load instruction.

Quoted 11 lines · Will Newton

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines

So all but a few have basically (as you said on IRC) #define atomic_read(v) ACCESS_ONCE(v)

ACCESS_ONCE(v->counter), but yeah :-)

I maintain an out-of-tree architecture where that isn't the case unfortunately [1]. Not expecting any special favours for being out-of-tree of course, but just thought I would add that data point.

Quoted 3 lines

[1] Our atomic operations go around the cache rather than through it, so the value of an atomic cannot be read with a normal load instruction.

Cannot how? It would observe a stale value? That is acceptable for atomic_read().

Quoted 12 lines · Peter Zijlstra

Quoted 11 lines · Will Newton

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines

So all but a few have basically (as you said on IRC) #define atomic_read(v) ACCESS_ONCE(v)

ACCESS_ONCE(v->counter), but yeah :-)

I maintain an out-of-tree architecture where that isn't the case unfortunately [1]. Not expecting any special favours for being out-of-tree of course, but just thought I would add that data point.

Quoted 6 lines

Quoted 3 lines

[1] Our atomic operations go around the cache rather than through it, so the value of an atomic cannot be read with a normal load instruction.

Cannot how? It would observe a stale value? That is acceptable for atomic_read().

It would observe a stale value, but that value would only be updated when the cache line was reloaded from main memory which would have to be triggered by either eviction or cache flushing. So it could get pretty stale. Whilst that's probably within the spec. of atomic_read I suspect it would lead to problems in practice. I could be wrong though.

It would observe a stale value, but that value would only be updated when the cache line was reloaded from main memory which would have to be triggered by either eviction or cache flushing. So it could get pretty stale. Whilst that's probably within the spec. of atomic_read I suspect it would lead to problems in practice. I could be wrong though.

Quoted 7 lines · Will Newton

It would observe a stale value, but that value would only be updated when the cache line was reloaded from main memory which would have to be triggered by either eviction or cache flushing. So it could get pretty stale. Whilst that's probably within the spec. of atomic_read I suspect it would lead to problems in practice. I could be wrong though.

Right, so the typical scenario that could cause pain is something like:

while (atomic_read(&foo) != n)
cpu_relax();

and the problem is that cpu_relax() doesn't know which particular cacheline to flush in order to make things go faster, hm?

Quoted 7 lines · Will Newton

It would observe a stale value, but that value would only be updated when the cache line was reloaded from main memory which would have to be triggered by either eviction or cache flushing. So it could get pretty stale. Whilst that's probably within the spec. of atomic_read I suspect it would lead to problems in practice. I could be wrong though.

Right, so the typical scenario that could cause pain is something like:

while (atomic_read(&foo) != n)
cpu_relax();

and the problem is that cpu_relax() doesn't know which particular cacheline to flush in order to make things go faster, hm?

Quoted 5 lines

while (atomic_read(&foo) != n)
cpu_relax();

and the problem is that cpu_relax() doesn't know which particular cacheline to flush in order to make things go faster, hm?

But what about any global variable? Can't we also just have:

	while (global != n)
		cpu_relax();

?

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 3 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

In cache aliasing situations, yes I can understand a L1 cache visibility issue being present, but with kernel only stuff that should never happen otherwise we have a bug in the arch cache flushing support.

I guess the issue is, if you use ll/sc on memory, you must always use ll/sc on that memory, otherwise any normal read won't read the proper cache.

Ideally, we would like a single atomic_read() but due to these wacky archs, it may not be possible.

Quoted 4 lines · Steven Rostedt

Ideally, we would like a single atomic_read() but due to these wacky archs, it may not be possible.

#ifdef ARCH_ATOMIC_READ_SUCKS_EGGS?

-hpa

Signature · 3 lines

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Quoted 6 lines · Steven Rostedt

Quoted 4 lines

Ideally, we would like a single atomic_read() but due to these wacky archs, it may not be possible.

Quoted 3 lines

#ifdef ARCH_ATOMIC_READ_SUCKS_EGGS?

-hpa

lol :)

Hrm, I wonder if it might cause problems with combinations of "cmpxchg" and "read" performed on a variable (without using atomic.h).

Quoted 10 lines

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 3 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Quoted 3 lines

In cache aliasing situations, yes I can understand a L1 cache visibility issue being present, but with kernel only stuff that should never happen otherwise we have a bug in the arch cache flushing support.

I guess the issue is, if you use ll/sc on memory, you must always use ll/sc on that memory, otherwise any normal read won't read the proper cache.

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 4 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Quoted 10 lines · On Mon, 14 Feb 2011 13:46:00 -0800 (PST) David Miller <[email protected]>…

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 4 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

Quoted 25 lines · * Matt Fleming ([email protected]) wrote:

Quoted 10 lines · On Mon, 14 Feb 2011 13:46:00 -0800 (PST) David Miller <[email protected]>…

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 4 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Quoted 3 lines

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

If this is true, then we have bugs in lots of xchg/cmpxchg users (which do not reside in atomic.h), e.g.:

fs/fs_struct.c:
int current_umask(void)

{
        return current->fs->umask;
}

EXPORT_SYMBOL(current_umask);

kernel/sys.c:
SYSCALL_DEFINE1(umask, int, mask)

{
        mask = xchg(&current->fs->umask, mask & S_IRWXUGO);
        return mask;
}

The solution to this would be to force all xchg/cmpxchg users to swap to atomic.h variables, which would force the ll semantic on read. But I'd really like to see where this is documented first -- or which PowerPC engineer we should talk to.

Thanks,

Mathieu

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 26 lines · Mathieu Desnoyers

Quoted 25 lines · * Matt Fleming ([email protected]) wrote:

Quoted 10 lines · On Mon, 14 Feb 2011 13:46:00 -0800 (PST) David Miller <[email protected]>…

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 4 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Quoted 3 lines

Quoted 3 lines

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

???

What CPU family are we talking about here? For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

Quoted 3 lines

What CPU family are we talking about here? For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

I'm really curious to know which CPU families too. I've used git blame to see where these lwz/stw instructions were added to powerpc, and it points to:

commit 9f0cbea0d8cc47801b853d3c61d0e17475b0cc89

So let's ping the relevant people to see if there was any reason for making these atomic read/set operations different from other architectures in the first place.

Quoted 8 lines

Quoted 3 lines

What CPU family are we talking about here? For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

I'm really curious to know which CPU families too. I've used git blame to see where these lwz/stw instructions were added to powerpc, and it points to:

Quoted 5 lines

commit 9f0cbea0d8cc47801b853d3c61d0e17475b0cc89

So let's ping the relevant people to see if there was any reason for making these atomic read/set operations different from other architectures in the first place.

lwz is a simple 32-bit load. On PowerPC, such a load is guaranteed to be atomic (except some unaligned cases). stw is similar, for stores. These are the normal insns, not ll/sc or anything.

At the time, volatile tricks were used to make the accesses atomic; this patch changed that. Result is (or should be!) better code generation.

Is there a problem with it?

Quoted 8 lines

Quoted 3 lines

What CPU family are we talking about here? For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

I'm really curious to know which CPU families too. I've used git blame to see where these lwz/stw instructions were added to powerpc, and it points to:

Quoted 5 lines

commit 9f0cbea0d8cc47801b853d3c61d0e17475b0cc89

So let's ping the relevant people to see if there was any reason for making these atomic read/set operations different from other architectures in the first place.

lwz is a simple 32-bit load. On PowerPC, such a load is guaranteed to be atomic (except some unaligned cases). stw is similar, for stores. These are the normal insns, not ll/sc or anything.

At the time, volatile tricks were used to make the accesses atomic; this patch changed that. Result is (or should be!) better code generation.

Is there a problem with it?

[ added Segher Boessenkool and Paul Mackerras to CC list ]

Quoted 33 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 26 lines · Mathieu Desnoyers

Quoted 25 lines · * Matt Fleming ([email protected]) wrote:

Quoted 10 lines · On Mon, 14 Feb 2011 13:46:00 -0800 (PST) David Miller <[email protected]>…

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 4 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Quoted 3 lines

Quoted 3 lines

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

???

Quoted 4 lines

What CPU family are we talking about here? For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

I'm really curious to know which CPU families too. I've used git blame to see where these lwz/stw instructions were added to powerpc, and it points to:

commit 9f0cbea0d8cc47801b853d3c61d0e17475b0cc89

Author: Segher Boessenkool <[email protected]>
Date:   Sat Aug 11 10:15:30 2007 +1000

[POWERPC] Implement atomic{, 64}_{read, write}() without volatile

Instead, use asm() like all other atomic operations already do.

Also use inline functions instead of macros; this actually improves code generation (some code becomes a little smaller, probably because of improved alias information -- just a few hundred bytes total on a default kernel build, nothing shocking).

Signed-off-by Segher Boessenkool <[email protected]>

Signed-off-by Paul Mackerras <[email protected]>

So let's ping the relevant people to see if there was any reason for making these atomic read/set operations different from other architectures in the first place.

Thanks,

Mathieu

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 41 lines · Mathieu Desnoyers

[ added Segher Boessenkool and Paul Mackerras to CC list ]

Quoted 37 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 26 lines · Mathieu Desnoyers

Quoted 25 lines · * Matt Fleming ([email protected]) wrote:

Quoted 10 lines · On Mon, 14 Feb 2011 13:46:00 -0800 (PST) David Miller <[email protected]>…

From: Steven Rostedt <[email protected]>
Date: Mon, 14 Feb 2011 16:39:36 -0500

Quoted 4 lines

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Quoted 3 lines

Quoted 3 lines

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

???

What CPU family are we talking about here? For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

Quoted 3 lines

I'm really curious to know which CPU families too. I've used git blame to see where these lwz/stw instructions were added to powerpc, and it points to:

But lwz and stw instructions are normal non-atomic PowerPC loads and stores. No LL/SC -- those would instead be lwarx and stwcx.

Thanx, Paul

Quoted 29 lines

commit 9f0cbea0d8cc47801b853d3c61d0e17475b0cc89

Author: Segher Boessenkool <[email protected]>
Date:   Sat Aug 11 10:15:30 2007 +1000

[POWERPC] Implement atomic{, 64}_{read, write}() without volatile

Instead, use asm() like all other atomic operations already do.

Also use inline functions instead of macros; this actually improves code generation (some code becomes a little smaller, probably because of improved alias information -- just a few hundred bytes total on a default kernel build, nothing shocking).

Signed-off-by Segher Boessenkool <[email protected]>

Signed-off-by Paul Mackerras <[email protected]>

So let's ping the relevant people to see if there was any reason for making these atomic read/set operations different from other architectures in the first place.

Thanks,

Mathieu

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

What CPU family are we talking about here?  For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

On Mon, Feb 14, 2011 at 11:09 PM, Paul E. McKenney <[email protected]> wrote:

Hi Paul,

Quoted 3 lines

What CPU family are we talking about here?  For cache coherent CPUs, cache coherence really is supposed to work, even for mixed atomic and non-atomic instructions to the same variable.

Is there a specific situation you can think of where this would be a problem? I have to admit to a certain amount of unease with the design our hardware guys came up with, but I don't have a specific case where it won't work, just cases where it is less than optimal.

Quoted 3 lines

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

Quoted 15 lines · Matt Fleming

Quoted 3 lines

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Quoted 3 lines

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

I'm sorry... this doesn't compute.  Either reads can work normally (go through the cache) in which case atomic_read() can simply be a read or they don't, so I don't understand this at all.

The CPU in question has two sets of instructions:

load/store - these go via the cache (write through)
ll/sc - these operate literally as if there is no cache (they do not
hit on read or write)

This may or may not be a sensible way to architect a CPU, but I think it is possible to make it work. Making it work efficiently is more of a challenge.

On 02/15/2011 03:01 AM, Will Newton wrote:

b) Why should we let this particular insane CPU slow ALL OTHER CPUs down?

Quoted 7 lines · Will Newton

The CPU in question has two sets of instructions:

  load/store - these go via the cache (write through)
  ll/sc - these operate literally as if there is no cache (they do not hit on read or write)

Quoted 4 lines

This may or may not be a sensible way to architect a CPU, but I think it is possible to make it work. Making it work efficiently is more of a challenge.

a) What "CPU in question" is this?

b) Why should we let this particular insane CPU slow ALL OTHER CPUs down?

Quoted 16 lines · H. Peter Anvin

Quoted 15 lines · Matt Fleming

Quoted 3 lines

I don't see how cache coherency can possibly work if the hardware behaves this way.

Cache coherency is still maintained provided writes/reads both go through the cache ;-)

The problem is that for read-modify-write operations the arbitration logic that decides who "wins" and is allowed to actually perform the write, assuming two or more CPUs are competing for a single memory address, is not implemented in the cache controller, I think. I'm not a hardware engineer and I never understood how the arbitration logic worked but I'm guessing that's the reason that the ll/sc instructions bypass the cache.

Quoted 7 lines

Quoted 3 lines

Which is why the atomic_t functions worked out really well for that arch, such that any accesses to an atomic_t * had to go through the wrapper functions.

I'm sorry... this doesn't compute. ?Either reads can work normally (go through the cache) in which case atomic_read() can simply be a read or they don't, so I don't understand this at all.

The CPU in question has two sets of instructions:

load/store - these go via the cache (write through)
ll/sc - these operate literally as if there is no cache (they do not
hit on read or write)

This may or may not be a sensible way to architect a CPU, but I think it is possible to make it work. Making it work efficiently is more of a challenge.

Note how the cache and cache coherence protocol are fundamental parts of this operation; if these instructions simply bypassed the cache, they *could not* work correctly - how do you detect when the underlying memory has been modified?

From: Will Simoneau <[email protected]>
Date: Tue, 15 Feb 2011 16:11:23 -0500

Quoted 4 lines

Note how the cache and cache coherence protocol are fundamental parts of this operation; if these instructions simply bypassed the cache, they *could not* work correctly - how do you detect when the underlying memory has been modified?

The issue here isn't L2 cache bypassing, it's local L1 cache bypassing.

The chips in question aparently do not consult the local L1 cache on "ll" instructions.

Therefore you must only ever access such atomic data using "ll" instructions.

Quoted 8 lines · David Miller

From: Will Simoneau <[email protected]>
Date: Tue, 15 Feb 2011 16:11:23 -0500

Quoted 4 lines

Note how the cache and cache coherence protocol are fundamental parts of this operation; if these instructions simply bypassed the cache, they *could not* work correctly - how do you detect when the underlying memory has been modified?

Quoted 7 lines

The issue here isn't L2 cache bypassing, it's local L1 cache bypassing.

The chips in question aparently do not consult the local L1 cache on "ll" instructions.

Therefore you must only ever access such atomic data using "ll" instructions.

(I should not have said "underlying memory", since it is correct that only the L1 caches are the problem here)

That's some really crippled hardware... it does seem like *any* loads from *any* address updated by an sc would have to be done with ll as well, else they may load stale values. One could work this into atomic_read(), but surely there are other places that are problems.

It would be OK if the caches on the hardware in question were to back-invalidate matching cachelines when the sc is snooped from the bus, but it sounds like this doesn't happen?

Quoted 4 lines

That's some really crippled hardware... it does seem like *any* loads from *any* address updated by an sc would have to be done with ll as well, else they may load stale values. One could work this into atomic_read(), but surely there are other places that are problems.

I think it's actually ok, atomics have arch implemented accessors, as do spinlocks and atomic bitops. Those are the only place we do sc so we can make sure we always ll or invalidate manually.

Quoted 5 lines · Will Newton

Quoted 4 lines

That's some really crippled hardware... it does seem like *any* loads from *any* address updated by an sc would have to be done with ll as well, else they may load stale values. One could work this into atomic_read(), but surely there are other places that are problems.

Quoted 3 lines

I think it's actually ok, atomics have arch implemented accessors, as do spinlocks and atomic bitops. Those are the only place we do sc so we can make sure we always ll or invalidate manually.

I'm curious, how is cmpxchg() implemented on this architecture? As there are several places in the kernel that uses this on regular variables without any "accessor" functions.

Quoted 7 lines · Steven Rostedt

Quoted 5 lines · Will Newton

Quoted 4 lines

That's some really crippled hardware... it does seem like *any* loads from *any* address updated by an sc would have to be done with ll as well, else they may load stale values. One could work this into atomic_read(), but surely there are other places that are problems.

Quoted 7 lines

Quoted 3 lines

I think it's actually ok, atomics have arch implemented accessors, as do spinlocks and atomic bitops. Those are the only place we do sc so we can make sure we always ll or invalidate manually.

I'm curious, how is cmpxchg() implemented on this architecture? As there are several places in the kernel that uses this on regular variables without any "accessor" functions.

We can invalidate the cache manually. The current cpu will see the new value (post-cache invalidate) and the other cpus will see either the old value or the new value depending on whether they read before or after the invalidate, which is racy but I don't think it is problematic. Unless I'm missing something...

Quoted 3 lines · Steven Rostedt

I'm curious, how is cmpxchg() implemented on this architecture? As there are several places in the kernel that uses this on regular variables without any "accessor" functions.

We can invalidate the cache manually. The current cpu will see the new value (post-cache invalidate) and the other cpus will see either the old value or the new value depending on whether they read before or after the invalidate, which is racy but I don't think it is problematic. Unless I'm missing something...

Folks, if you want to invent new masochistic programming models like this please do it on an own thread with a reduced cc list.

Well, Andi, since you removed the subject nobody has any idea what thread you are even referring to.

Quoted 10 lines · Will Newton

Quoted 3 lines · Steven Rostedt

I'm curious, how is cmpxchg() implemented on this architecture? As there are several places in the kernel that uses this on regular variables without any "accessor" functions.

We can invalidate the cache manually. The current cpu will see the new value (post-cache invalidate) and the other cpus will see either the old value or the new value depending on whether they read before or after the invalidate, which is racy but I don't think it is problematic. Unless I'm missing something...

If I understand this correctly, the manual invalidates must propagate to all CPUs that potentially read the value, even if there is no contention. Doesn't this involve IPIs? How does it not suck?

Quoted 16 lines · * Will Newton ([email protected]) wrote:

Quoted 7 lines · Steven Rostedt

Quoted 5 lines · Will Newton

Quoted 4 lines

That's some really crippled hardware... it does seem like *any* loads from *any* address updated by an sc would have to be done with ll as well, else they may load stale values. One could work this into atomic_read(), but surely there are other places that are problems.

Quoted 7 lines

Quoted 3 lines

I think it's actually ok, atomics have arch implemented accessors, as do spinlocks and atomic bitops. Those are the only place we do sc so we can make sure we always ll or invalidate manually.

I'm curious, how is cmpxchg() implemented on this architecture? As there are several places in the kernel that uses this on regular variables without any "accessor" functions.

Quoted 5 lines

We can invalidate the cache manually. The current cpu will see the new value (post-cache invalidate) and the other cpus will see either the old value or the new value depending on whether they read before or after the invalidate, which is racy but I don't think it is problematic. Unless I'm missing something...

Assuming the invalidate is specific to a cache-line, I'm concerned about the failure of a scenario like the following:

initially:
foo = 0
bar = 0

CPU A CPU B

xchg(&foo, 1);
ll foo
sc foo

-> interrupt

  if (foo == 1)
    xchg(&bar, 1);
      ll bar
      sc bar
      invalidate bar

                                 lbar = bar;
                                 smp_mb()
                                 lfoo = foo;
                                 BUG_ON(lbar == 1 && lfoo == 0);

invalidate foo

It should be valid to expect that every time "bar" read by CPU B is 1, then "foo" is always worth 1. However, in this case, the lack of invalidate on foo is keeping the cacheline from reaching CPU B. There seems to be a problem with interrupts/NMIs coming right between sc and invalidate, as Ingo pointed out.

Hmm, I think that is miss-coding ll/sc.
If I understand correctly, usually cache invalidation should be done right before storing value, as MSI protocol does.
(or, sc should atomically invalidate the cache line)

Quoted 6 lines · Masami Hiramatsu

Hmm, I think that is miss-coding ll/sc.
If I understand correctly, usually cache invalidation should be done right before storing value, as MSI protocol does.
(or, sc should atomically invalidate the cache line)

I suspect in this case one should flush the cache line before ll (a cache flush will typically invalidate the ll/sc link.)

-hpa

Signature · 2 lines

H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

* Will Newton ([email protected]) wrote:

initially:
foo = 0
bar = 0

CPU A CPU B

xchg(&foo, 1);
ll foo
sc foo

-> interrupt

  if (foo == 1)
    xchg(&bar, 1);
      ll bar
      sc bar
      invalidate bar

                                 lbar = bar;
                                 smp_mb()

                                 lfoo = foo;

                                 BUG_ON(lbar == 1 && lfoo == 0);

invalidate foo

It should be valid to expect that every time "bar" read by CPU B is 1, then "foo" is always worth 1. However, in this case, the lack of invalidate on foo is keeping the cacheline from reaching CPU B. There seems to be a problem with interrupts/NMIs coming right between sc and invalidate, as Ingo pointed out.

Thanks,

Mathieu

[ Removed Andi as I believe this is the mysterious thread he was talking about. Anyone else want to be removed? ]

Quoted 20 lines · Mathieu Desnoyers

* Will Newton ([email protected]) wrote:

initially:
foo = 0
bar = 0

CPU A CPU B

xchg(&foo, 1);
ll foo
sc foo

-> interrupt

  if (foo == 1)
    xchg(&bar, 1);
      ll bar
      sc bar
      invalidate bar

Quoted 2 lines

                                 lbar = bar;
                                 smp_mb()

Question: Does a mb() flush all cache or does it just make sure that read/write operations finish before starting new ones?

Quoted 2 lines

                                 lfoo = foo;

IOW, will that smp_mb() really make lfoo read the new foo in memory? If foo happens to still be in cache and no coherency has been performed to flush it, would it just simply read foo straight from the cache?

-- Steve

Quoted 13 lines

                                 BUG_ON(lbar == 1 && lfoo == 0);

invalidate foo

It should be valid to expect that every time "bar" read by CPU B is 1, then "foo" is always worth 1. However, in this case, the lack of invalidate on foo is keeping the cacheline from reaching CPU B. There seems to be a problem with interrupts/NMIs coming right between sc and invalidate, as Ingo pointed out.

Thanks,

Mathieu

Quoted 6 lines

Quoted 2 lines

                                 lfoo = foo;

IOW, will that smp_mb() really make lfoo read the new foo in memory? If foo happens to still be in cache and no coherency has been performed to flush it, would it just simply read foo straight from the cache?

If we were to deploy the Linux kernel on an architecture without coherent caches, I think smp_mb() should imply a cacheline invalidation, otherwise we completely mess up the order of data writes vs their observability from each invididual core POV.

From: Will Simoneau <[email protected]>
Date: Tue, 15 Feb 2011 16:11:23 -0500

Quoted 4 lines

Note how the cache and cache coherence protocol are fundamental parts of this operation; if these instructions simply bypassed the cache, they *could not* work correctly - how do you detect when the underlying memory has been modified?

The issue here isn't L2 cache bypassing, it's local L1 cache bypassing.

The chips in question aparently do not consult the local L1 cache on "ll" instructions.

Therefore you must only ever access such atomic data using "ll" instructions.

Quoted 13 lines · David Miller

From: Will Simoneau <[email protected]>
Date: Tue, 15 Feb 2011 16:11:23 -0500

Quoted 4 lines

Note how the cache and cache coherence protocol are fundamental parts of this operation; if these instructions simply bypassed the cache, they *could not* work correctly - how do you detect when the underlying memory has been modified?

The issue here isn't L2 cache bypassing, it's local L1 cache bypassing.

The chips in question aparently do not consult the local L1 cache on "ll" instructions.

Quoted 2 lines

Therefore you must only ever access such atomic data using "ll" instructions.

Note that it's actually a reasonable design choice to not consult the L1 in these case .... as long as you invalidate it on the way. That's how current powerpcs do it afaik, they send a kill to any matching L1 line along as reading from the L2. (Of course, L1 has to be write-through for that to work).

Just curious: how does this work if there's an interrupt (or NMI) right after the invalidate instruction but before the 'll' instruction? The IRQ/NMI may refill the L1. Or are the two instructions coupled by hw (they form a single instruction in essence) and irqs/NMIs are inhibited inbetween?

Quoted 6 lines · Ingo Molnar

Just curious: how does this work if there's an interrupt (or NMI) right after the invalidate instruction but before the 'll' instruction? The IRQ/NMI may refill the L1. Or are the two instructions coupled by hw (they form a single instruction in essence) and irqs/NMIs are inhibited inbetween?

http://en.wikipedia.org/wiki/Load-link/store-conditional

If this is true, then we have bugs in lots of xchg/cmpxchg users (which do not reside in atomic.h), e.g.:

fs/fs_struct.c:
int current_umask(void)

{
        return current->fs->umask;
}

EXPORT_SYMBOL(current_umask);

kernel/sys.c:
SYSCALL_DEFINE1(umask, int, mask)

{
        mask = xchg(&current->fs->umask, mask & S_IRWXUGO);
        return mask;
}

The solution to this would be to force all xchg/cmpxchg users to swap to atomic.h variables, which would force the ll semantic on read. But I'd really like to see where this is documented first -- or which PowerPC engineer we should talk to.

From: Mathieu Desnoyers <[email protected]>
Date: Mon, 14 Feb 2011 18:03:01 -0500

Quoted 17 lines

If this is true, then we have bugs in lots of xchg/cmpxchg users (which do not reside in atomic.h), e.g.:

fs/fs_struct.c:
int current_umask(void)

{
        return current->fs->umask;
}

EXPORT_SYMBOL(current_umask);

kernel/sys.c:
SYSCALL_DEFINE1(umask, int, mask)

{
        mask = xchg(&current->fs->umask, mask & S_IRWXUGO);
        return mask;
}

Quoted 4 lines

The solution to this would be to force all xchg/cmpxchg users to swap to atomic.h variables, which would force the ll semantic on read. But I'd really like to see where this is documented first -- or which PowerPC engineer we should talk to.

We can't wholesale to atomic_t because we do this on variables of all sizes, not just 32-bit ones.

We do them on pointers in the networking for example.

* David Miller ([email protected]) wrote:

Quoted 4 lines

We can't wholesale to atomic_t because we do this on variables of all sizes, not just 32-bit ones.

We do them on pointers in the networking for example.

We have atomic_long_t for this, but yeah, it would kind of suck to have to create

union {
	atomic_long_t atomic;
	void *ptr;
}

all around the place. Let's see if we can get to know which PowerPC processor family all this fuss is about, and where this rumour originates from.

Thanks,

Mathieu

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 6 lines · Steven Rostedt

Quoted 5 lines

while (atomic_read(&foo) != n)
cpu_relax();

and the problem is that cpu_relax() doesn't know which particular cacheline to flush in order to make things go faster, hm?

Quoted 6 lines

But what about any global variable? Can't we also just have:

	while (global != n)
		cpu_relax();

?

Matt Fleming answered this for me on IRC, and I'll share the answer here (for those that are dying to know ;)

Seems that the atomic_inc() uses ll/sc operations that do not affect the cache. Thus the problem is only with atomic_read() as

	while(atomic_read(&foo) != n)
		cpu_relax();

Will just check the cache version of foo. But because ll/sc skips the cache, the foo will never update. That is, atomic_inc() and friends do not touch the cache, and the CPU spinning in this loop will is only checking the cache, and will spin forever.

Thus it is not about global, as global is updated by normal means and will update the caches. atomic_t is updated via the ll/sc that ignores the cache and causes all this to break down. IOW... broken hardware ;)

Quoted 8 lines · Steven Rostedt

mn10300:
#define atomic_read(v) ((v)->counter)

tile:
static inline int atomic_read(const atomic_t *v)

{
       return v->counter;
}

Yeah, I already send email to the respective maintainers telling them they might want to fix this ;-)

Quoted 2 lines

So all but a few have basically (as you said on IRC) #define atomic_read(v) ACCESS_ONCE(v)

ACCESS_ONCE(v->counter), but yeah :-)

Quoted 4 lines

Those few are blackfin, s390, powerpc and tile.

s390 probably doesn't need that much of a big hammer with atomic_read() (unless it uses it in its own arch that expects it to be such).

Right, it could just do the volatile thing..

Quoted 16 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 11 lines · Jason Baron

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines

I remember that atomic_t is defined in types.h now rather than atomic.h. Any reason why you should keep including atomic.h from jump_label.h ?

Ooh, shiny.. we could probably move the few atomic_{read,inc,dec} users in jump_label.h into out of line functions and have this sorted.

inc and dec sure, but atomic_read() for the disabled case needs to be inline....

D'0h yes of course, I was thinking about jump_label_enabled(), but there's still the static_branch() implementation to consider.

Quoted 3 lines

We could of course cheat implement our own version of atomic_read() in order to avoid the whole header mess, but that's not pretty at all

OK, so the other way around then : why does kernel.h need to include dynamic_debug.h (which includes jump_label.h) ?

I don't need an atomic_read() in the disabled case for dynamic debug, and I would be ok, #ifdef CONFIG_JUMP_LABEL, in dynamic_debug.h. Its not the prettiest solution. But I can certainly live with it for now, so that we can sort out the atomic_read() issue independently.

Peter, Mathieu, are you guys ok with this?

Quoted 6 lines · Jason Baron

I don't need an atomic_read() in the disabled case for dynamic debug, and I would be ok, #ifdef CONFIG_JUMP_LABEL, in dynamic_debug.h. Its not the prettiest solution. But I can certainly live with it for now, so that we can sort out the atomic_read() issue independently.

Peter, Mathieu, are you guys ok with this?

Yeah, lets see where that gets us.

Quoted 3 lines · Peter Zijlstra

So why can't we make that jump_label_entry::refcount and jump_label_key::state an atomic_t and be done with it?

So I had a bit of a poke at this because I didn't quite understand why all that stuff was as it was. I applied both Jason's patches and then basically rewrote kernel/jump_label.c just for kicks ;-)

I haven't tried compiling this, let alone running it, but provided I didn't actually forget anything the storage per key is now 16 bytes when modules are disabled and 24 * (1 + mods) bytes for when they are enabled. The old code had 64 + 40 * mods bytes.

I still need to clean up the static_branch_else bits and look at !x86 aside from the already mentioned bits.. but what do people think?

---
 arch/sparc/include/asm/jump_label.h |   25 +-
 arch/x86/include/asm/jump_label.h   |   22 +-
 arch/x86/kernel/jump_label.c        |    2 +-
 arch/x86/kernel/module.c            |    3 -
 include/linux/dynamic_debug.h       |   10 +-
 include/linux/jump_label.h          |   71 +++---
 include/linux/jump_label_ref.h      |   36 +--
 include/linux/module.h              |    1 +
 include/linux/perf_event.h          |   28 +-
 include/linux/tracepoint.h          |    8 +-
 kernel/jump_label.c                 |  516 +++++++++++++----------------------
 kernel/module.c                     |    7 +
 kernel/perf_event.c                 |   30 ++-
 kernel/timer.c                      |    8 +-
 kernel/tracepoint.c                 |   22 +-
 15 files changed, 333 insertions(+), 456 deletions(-)

arch/sparc/include/asm/jump_label.h +14 -11

index 427d468..e4ca085 100644
@@ -7,17 +7,20 @@
 
 #define JUMP_LABEL_NOP_SIZE 4
 
-#define JUMP_LABEL(key, label)					\
-	do {							\
-		asm goto("1:\n\t"				\
-			 "nop\n\t"				\
-			 "nop\n\t"				\
-			 ".pushsection __jump_table,  \"a\"\n\t"\
-			 ".align 4\n\t"				\
-			 ".word 1b, %l[" #label "], %c0\n\t"	\
-			 ".popsection \n\t"			\
-			 : :  "i" (key) :  : label);\
-	} while (0)
+static __always_inline bool __static_branch(struct jump_label_key *key)
+{
+		asm goto("1:\n\t"
+			 "nop\n\t"
+			 "nop\n\t"
+			 ".pushsection __jump_table,  \"a\"\n\t"
+			 ".align 4\n\t"
+			 ".word 1b, %l[l_yes], %c0\n\t"
+			 ".popsection \n\t"
+			 : :  "i" (key) :  : l_yes);
+	return false;
+l_yes:
+	return true;
+}
 
 #endif /* __KERNEL__ */
 

arch/x86/include/asm/jump_label.h +13 -9

index 574dbc2..3d44a7c 100644
@@ -5,20 +5,24 @@
 
 #include <linux/types.h>
 #include <asm/nops.h>
+#include <asm/asm.h>
 
 #define JUMP_LABEL_NOP_SIZE 5
 
 # define JUMP_LABEL_INITIAL_NOP ".byte 0xe9 \n\t .long 0\n\t"
 
-# define JUMP_LABEL(key, label)					\
-	do {							\
-		asm goto("1:"					\
-			JUMP_LABEL_INITIAL_NOP			\
-			".pushsection __jump_table,  \"aw\" \n\t"\
-			_ASM_PTR "1b, %l[" #label "], %c0 \n\t" \
-			".popsection \n\t"			\
-			: :  "i" (key) :  : label);		\
-	} while (0)
+static __always_inline bool __static_branch(struct jump_label_key *key)
+{
+	asm goto("1:"
+		JUMP_LABEL_INITIAL_NOP
+		".pushsection __jump_table,  \"a\" \n\t"
+		_ASM_PTR "1b, %l[l_yes], %c0 \n\t"
+		".popsection \n\t"
+		: :  "i" (key) : : l_yes );
+	return false;
+l_yes:
+	return true;
+}
 
 #endif /* __KERNEL__ */
 

arch/x86/kernel/jump_label.c +1 -1

index 961b6b3..dfa4c3c 100644
@@ -4,13 +4,13 @@
  * Copyright (C) 2009 Jason Baron <[email protected]>
  *
  */
-#include <linux/jump_label.h>
 #include <linux/memory.h>
 #include <linux/uaccess.h>
 #include <linux/module.h>
 #include <linux/list.h>
 #include <linux/jhash.h>
 #include <linux/cpu.h>
+#include <linux/jump_label.h>
 #include <asm/kprobes.h>
 #include <asm/alternative.h>
 

arch/x86/kernel/module.c +0 -3

index ab23f1a..0e6b823 100644
@@ -230,9 +230,6 @@ int module_finalize(const Elf_Ehdr *hdr,
 		apply_paravirt(pseg, pseg + para->sh_size);
 	}
 
-	/* make jump label nops */
-	jump_label_apply_nops(me);
-
 	return 0;
 }
 

include/linux/dynamic_debug.h +5 -5

index 1c70028..2ade291 100644
@@ -33,7 +33,7 @@ struct _ddebug {
 #define _DPRINTK_FLAGS_PRINT   (1<<0)  /* printk() a message using the format */
 #define _DPRINTK_FLAGS_DEFAULT 0
 	unsigned int flags:8;
-	char enabled;
+	struct jump_label_key enabled;
 } __attribute__((aligned(8)));
 
 

@@ -48,8 +48,8 @@ extern int ddebug_remove_module(const char *mod_name);
 	__used								\
 	__attribute__((section("__verbose"), aligned(8))) =		\
 	{ KBUILD_MODNAME, __func__, __FILE__, fmt, __LINE__,		\
-		_DPRINTK_FLAGS_DEFAULT };				\
-	if (unlikely(descriptor.enabled))				\
+		_DPRINTK_FLAGS_DEFAULT, JUMP_LABEL_INIT };		\
+	if (static_branch(&descriptor.enabled))				\
 		printk(KERN_DEBUG pr_fmt(fmt),	##__VA_ARGS__);		\
 	} while (0)
 

@@ -59,8 +59,8 @@ extern int ddebug_remove_module(const char *mod_name);
 	__used								\
 	__attribute__((section("__verbose"), aligned(8))) =		\
 	{ KBUILD_MODNAME, __func__, __FILE__, fmt, __LINE__,		\
-		_DPRINTK_FLAGS_DEFAULT };				\
-	if (unlikely(descriptor.enabled))				\
+		_DPRINTK_FLAGS_DEFAULT, JUMP_LABEL_INIT };		\
+	if (static_branch(&descriptor.enabled))				\
 		dev_printk(KERN_DEBUG, dev, fmt, ##__VA_ARGS__);	\
 	} while (0)
 

include/linux/jump_label.h +38 -33

index 7880f18..a1cec0a 100644
@@ -2,19 +2,35 @@
 #define _LINUX_JUMP_LABEL_H
 
 #if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)
+
+struct jump_label_key {
+	atomic_t enabled;
+	struct jump_entry *entries;
+#ifdef CONFIG_MODULES
+	struct jump_module *next;
+#endif
+};
+
 # include <asm/jump_label.h>
 # define HAVE_JUMP_LABEL
 #endif
 
 enum jump_label_type {
+	JUMP_LABEL_DISABLE = 0,
 	JUMP_LABEL_ENABLE,
-	JUMP_LABEL_DISABLE
 };
 
 struct module;
 
+#define JUMP_LABEL_INIT { 0 }
+
 #ifdef HAVE_JUMP_LABEL
 
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	return __static_branch(key);
+}
+
 extern struct jump_entry __start___jump_table[];
 extern struct jump_entry __stop___jump_table[];
 

@@ -23,37 +39,31 @@ extern void jump_label_unlock(void);
 extern void arch_jump_label_transform(struct jump_entry *entry,
 				 enum jump_label_type type);
 extern void arch_jump_label_text_poke_early(jump_label_t addr);
-extern void jump_label_update(unsigned long key, enum jump_label_type type);
-extern void jump_label_apply_nops(struct module *mod);
 extern int jump_label_text_reserved(void *start, void *end);
-
-#define jump_label_enable(key) \
-	jump_label_update((unsigned long)key, JUMP_LABEL_ENABLE);
-
-#define jump_label_disable(key) \
-	jump_label_update((unsigned long)key, JUMP_LABEL_DISABLE);
+extern void jump_label_enable(struct jump_label_key *key);
+extern void jump_label_disable(struct jump_label_key *key);
 
 #else
 
-#define JUMP_LABEL(key, label)			\
-do {						\
-	if (unlikely(*key))			\
-		goto label;			\
-} while (0)
+struct jump_label_key {
+	atomic_t enabled;
+};
 
-#define jump_label_enable(cond_var)	\
-do {					\
-       *(cond_var) = 1;			\
-} while (0)
+static __always_inline bool static_branch(struct jump_label_key *key)
+{
+	if (unlikely(atomic_read(&key->state)))
+		return true;
+	return false;
+}
 
-#define jump_label_disable(cond_var)	\
-do {					\
-       *(cond_var) = 0;			\
-} while (0)
+static inline void jump_label_enable(struct jump_label_key *key)
+{
+	atomic_inc(&key->state);
+}
 
-static inline int jump_label_apply_nops(struct module *mod)
+static inline void jump_label_disable(struct jump_label_key *key)
 {
-	return 0;
+	atomic_dec(&key->state);
 }
 
 static inline int jump_label_text_reserved(void *start, void *end)

@@ -66,14 +76,9 @@ static inline void jump_label_unlock(void) {}
 
 #endif
 
-#define COND_STMT(key, stmt)					\
-do {								\
-	__label__ jl_enabled;					\
-	JUMP_LABEL(key, jl_enabled);				\
-	if (0) {						\
-jl_enabled:							\
-		stmt;						\
-	}							\
-} while (0)
+static inline bool jump_label_enabled(struct jump_label_key *key)
+{
+	return !!atomic_read(&key->state);
+}
 
 #endif

include/linux/jump_label_ref.h +11 -25

index e5d012a..5178696 100644
@@ -4,41 +4,27 @@
 #include <linux/jump_label.h>
 #include <asm/atomic.h>
 
-#ifdef HAVE_JUMP_LABEL
+struct jump_label_key_counter {
+	atomic_t ref;
+	struct jump_label_key key;
+};
 
-static inline void jump_label_inc(atomic_t *key)
-{
-	if (atomic_add_return(1, key) == 1)
-		jump_label_enable(key);
-}
+#ifdef HAVE_JUMP_LABEL
 
-static inline void jump_label_dec(atomic_t *key)
+static __always_inline bool static_branch_else_atomic_read(struct jump_label_key *key, atomic_t *count)
 {
-	if (atomic_dec_and_test(key))
-		jump_label_disable(key);
+	return __static_branch(key);
 }
 
 #else /* !HAVE_JUMP_LABEL */
 
-static inline void jump_label_inc(atomic_t *key)
+static __always_inline bool static_branch_else_atomic_read(struct jump_label_key *key, atomic_t *count)
 {
-	atomic_inc(key);
+	if (unlikely(atomic_read(count)))
+		return true;
+	return false;
 }
 
-static inline void jump_label_dec(atomic_t *key)
-{
-	atomic_dec(key);
-}
-
-#undef JUMP_LABEL
-#define JUMP_LABEL(key, label)						\
-do {									\
-	if (unlikely(__builtin_choose_expr(				\
-	      __builtin_types_compatible_p(typeof(key), atomic_t *),	\
-	      atomic_read((atomic_t *)(key)), *(key))))			\
-		goto label;						\
-} while (0)
-
 #endif /* HAVE_JUMP_LABEL */
 
 #endif /* _LINUX_JUMP_LABEL_REF_H */

include/linux/module.h +1 -0

index 9bdf27c..eeb3e99 100644
@@ -266,6 +266,7 @@ enum module_state
 	MODULE_STATE_LIVE,
 	MODULE_STATE_COMING,
 	MODULE_STATE_GOING,
+	MODULE_STATE_POST_RELOCATE,
 };
 
 struct module

include/linux/perf_event.h +15 -13

index dda5b0a..26fe115 100644
@@ -1000,7 +1000,7 @@ static inline int is_software_event(struct perf_event *event)
 	return event->pmu->task_ctx_nr == perf_sw_context;
 }
 
-extern atomic_t perf_swevent_enabled[PERF_COUNT_SW_MAX];
+extern struct jump_label_key_counter perf_swevent_enabled[PERF_COUNT_SW_MAX];
 
 extern void __perf_sw_event(u32, u64, int, struct pt_regs *, u64);
 

@@ -1029,30 +1029,32 @@ perf_sw_event(u32 event_id, u64 nr, int nmi, struct pt_regs *regs, u64 addr)
 {
 	struct pt_regs hot_regs;
 
-	JUMP_LABEL(&perf_swevent_enabled[event_id], have_event);
-	return;
-
-have_event:
-	if (!regs) {
-		perf_fetch_caller_regs(&hot_regs);
-		regs = &hot_regs;
+	if (static_branch_else_atomic_read(&perf_swevent_enabled[event_id].key,
+					 &perf_swevent_enabled[event_id].ref)) {
+		if (!regs) {
+			perf_fetch_caller_regs(&hot_regs);
+			regs = &hot_regs;
+		}
+		__perf_sw_event(event_id, nr, nmi, regs, addr);
 	}
-	__perf_sw_event(event_id, nr, nmi, regs, addr);
 }
 
-extern atomic_t perf_task_events;
+extern struct jump_label_key_counter perf_task_events;
 
 static inline void perf_event_task_sched_in(struct task_struct *task)
 {
-	COND_STMT(&perf_task_events, __perf_event_task_sched_in(task));
+	if (static_branch_else_atomic_read(&perf_task_events.key,
+					   &perf_task_events.ref))
+		__perf_event_task_sched_in(task);
 }
 
 static inline
 void perf_event_task_sched_out(struct task_struct *task, struct task_struct *next)
 {
 	perf_sw_event(PERF_COUNT_SW_CONTEXT_SWITCHES, 1, 1, NULL, 0);
-
-	COND_STMT(&perf_task_events, __perf_event_task_sched_out(task, next));
+	if (static_branch_else_atomic_read(&perf_task_events.key,
+					   &perf_task_events.ref))
+		__perf_event_task_sched_out(task, next);
 }
 
 extern void perf_event_mmap(struct vm_area_struct *vma);

include/linux/tracepoint.h +3 -5

index 97c84a5..6c8c747 100644
@@ -29,7 +29,7 @@ struct tracepoint_func {
 
 struct tracepoint {
 	const char *name;		/* Tracepoint name */
-	int state;			/* State. */
+	struct jump_label_key key;
 	void (*regfunc)(void);
 	void (*unregfunc)(void);
 	struct tracepoint_func __rcu *funcs;

@@ -146,9 +146,7 @@ void tracepoint_update_probe_range(struct tracepoint * const *begin,
 	extern struct tracepoint __tracepoint_##name;			\
 	static inline void trace_##name(proto)				\
 	{								\
-		JUMP_LABEL(&__tracepoint_##name.state, do_trace);	\
-		return;							\
-do_trace:								\
+		if (static_branch(&__tracepoint_##name.key))		\
 			__DO_TRACE(&__tracepoint_##name,		\
 				TP_PROTO(data_proto),			\
 				TP_ARGS(data_args),			\

@@ -181,7 +179,7 @@ do_trace:								\
 	__attribute__((section("__tracepoints_strings"))) = #name;	\
 	struct tracepoint __tracepoint_##name				\
 	__attribute__((section("__tracepoints"))) =			\
-		{ __tpstrtab_##name, 0, reg, unreg, NULL };		\
+		{ __tpstrtab_##name, JUMP_LABEL_INIT, reg, unreg, NULL };\
 	static struct tracepoint * const __tracepoint_ptr_##name __used	\
 	__attribute__((section("__tracepoints_ptrs"))) =		\
 		&__tracepoint_##name;

kernel/jump_label.c +193 -323

index 3b79bd9..29b34be 100644
@@ -2,9 +2,9 @@
  * jump label support
  *
  * Copyright (C) 2009 Jason Baron <[email protected]>
+ * Copyright (C) 2011 Peter Zijlstra <[email protected]>
  *
  */
-#include <linux/jump_label.h>
 #include <linux/memory.h>
 #include <linux/uaccess.h>
 #include <linux/module.h>

@@ -13,32 +13,13 @@
 #include <linux/slab.h>
 #include <linux/sort.h>
 #include <linux/err.h>
+#include <linux/jump_label.h>
 
 #ifdef HAVE_JUMP_LABEL
 
-#define JUMP_LABEL_HASH_BITS 6
-#define JUMP_LABEL_TABLE_SIZE (1 << JUMP_LABEL_HASH_BITS)
-static struct hlist_head jump_label_table[JUMP_LABEL_TABLE_SIZE];
-
 /* mutex to protect coming/going of the the jump_label table */
 static DEFINE_MUTEX(jump_label_mutex);
 
-struct jump_label_entry {
-	struct hlist_node hlist;
-	struct jump_entry *table;
-	int nr_entries;
-	/* hang modules off here */
-	struct hlist_head modules;
-	unsigned long key;
-};
-
-struct jump_label_module_entry {
-	struct hlist_node hlist;
-	struct jump_entry *table;
-	int nr_entries;
-	struct module *mod;
-};
-
 void jump_label_lock(void)
 {
 	mutex_lock(&jump_label_mutex);

@@ -64,7 +45,7 @@ static int jump_label_cmp(const void *a, const void *b)
 }
 
 static void
-sort_jump_label_entries(struct jump_entry *start, struct jump_entry *stop)
+jump_label_sort_entries(struct jump_entry *start, struct jump_entry *stop)
 {
 	unsigned long size;
 

@@ -73,118 +54,25 @@ sort_jump_label_entries(struct jump_entry *start, struct jump_entry *stop)
 	sort(start, size, sizeof(struct jump_entry), jump_label_cmp, NULL);
 }
 
-static struct jump_label_entry *get_jump_label_entry(jump_label_t key)
-{
-	struct hlist_head *head;
-	struct hlist_node *node;
-	struct jump_label_entry *e;
-	u32 hash = jhash((void *)&key, sizeof(jump_label_t), 0);
-
-	head = &jump_label_table[hash & (JUMP_LABEL_TABLE_SIZE - 1)];
-	hlist_for_each_entry(e, node, head, hlist) {
-		if (key == e->key)
-			return e;
-	}
-	return NULL;
-}
+static void jump_label_update(struct jump_label_key *key, int enable);
 
-static struct jump_label_entry *
-add_jump_label_entry(jump_label_t key, int nr_entries, struct jump_entry *table)
+void jump_label_enable(struct jump_label_key *key)
 {
-	struct hlist_head *head;
-	struct jump_label_entry *e;
-	u32 hash;
-
-	e = get_jump_label_entry(key);
-	if (e)
-		return ERR_PTR(-EEXIST);
-
-	e = kmalloc(sizeof(struct jump_label_entry), GFP_KERNEL);
-	if (!e)
-		return ERR_PTR(-ENOMEM);
-
-	hash = jhash((void *)&key, sizeof(jump_label_t), 0);
-	head = &jump_label_table[hash & (JUMP_LABEL_TABLE_SIZE - 1)];
-	e->key = key;
-	e->table = table;
-	e->nr_entries = nr_entries;
-	INIT_HLIST_HEAD(&(e->modules));
-	hlist_add_head(&e->hlist, head);
-	return e;
-}
+	if (atomic_inc_not_zero(&key->enabled))
+		return;
 
-static int
-build_jump_label_hashtable(struct jump_entry *start, struct jump_entry *stop)
-{
-	struct jump_entry *iter, *iter_begin;
-	struct jump_label_entry *entry;
-	int count;
-
-	sort_jump_label_entries(start, stop);
-	iter = start;
-	while (iter < stop) {
-		entry = get_jump_label_entry(iter->key);
-		if (!entry) {
-			iter_begin = iter;
-			count = 0;
-			while ((iter < stop) &&
-				(iter->key == iter_begin->key)) {
-				iter++;
-				count++;
-			}
-			entry = add_jump_label_entry(iter_begin->key,
-							count, iter_begin);
-			if (IS_ERR(entry))
-				return PTR_ERR(entry);
-		 } else {
-			WARN_ONCE(1, KERN_ERR "build_jump_hashtable: unexpected entry!\n");
-			return -1;
-		}
-	}
-	return 0;
+	jump_label_lock();
+	if (atomic_add_return(&key->enabled) == 1)
+		jump_label_update(key, JUMP_LABEL_ENABLE);
+	jump_label_unlock();
 }
 
-/***
- * jump_label_update - update jump label text
- * @key -  key value associated with a a jump label
- * @type - enum set to JUMP_LABEL_ENABLE or JUMP_LABEL_DISABLE
- *
- * Will enable/disable the jump for jump label @key, depending on the
- * value of @type.
- *
- */
-
-void jump_label_update(unsigned long key, enum jump_label_type type)
+void jump_label_disable(struct jump_label_key *key)
 {
-	struct jump_entry *iter;
-	struct jump_label_entry *entry;
-	struct hlist_node *module_node;
-	struct jump_label_module_entry *e_module;
-	int count;
+	if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex))
+		return;
 
-	jump_label_lock();
-	entry = get_jump_label_entry((jump_label_t)key);
-	if (entry) {
-		count = entry->nr_entries;
-		iter = entry->table;
-		while (count--) {
-			if (kernel_text_address(iter->code))
-				arch_jump_label_transform(iter, type);
-			iter++;
-		}
-		/* eanble/disable jump labels in modules */
-		hlist_for_each_entry(e_module, module_node, &(entry->modules),
-							hlist) {
-			count = e_module->nr_entries;
-			iter = e_module->table;
-			while (count--) {
-				if (iter->key &&
-						kernel_text_address(iter->code))
-					arch_jump_label_transform(iter, type);
-				iter++;
-			}
-		}
-	}
+	jump_label_update(key, JUMP_LABEL_DISABLE);
 	jump_label_unlock();
 }
 

@@ -197,77 +85,30 @@ static int addr_conflict(struct jump_entry *entry, void *start, void *end)
 	return 0;
 }
 
-#ifdef CONFIG_MODULES
-
-static int module_conflict(void *start, void *end)
-{
-	struct hlist_head *head;
-	struct hlist_node *node, *node_next, *module_node, *module_node_next;
-	struct jump_label_entry *e;
-	struct jump_label_module_entry *e_module;
-	struct jump_entry *iter;
-	int i, count;
-	int conflict = 0;
-
-	for (i = 0; i < JUMP_LABEL_TABLE_SIZE; i++) {
-		head = &jump_label_table[i];
-		hlist_for_each_entry_safe(e, node, node_next, head, hlist) {
-			hlist_for_each_entry_safe(e_module, module_node,
-							module_node_next,
-							&(e->modules), hlist) {
-				count = e_module->nr_entries;
-				iter = e_module->table;
-				while (count--) {
-					if (addr_conflict(iter, start, end)) {
-						conflict = 1;
-						goto out;
-					}
-					iter++;
-				}
-			}
-		}
-	}
-out:
-	return conflict;
-}
-
-#endif
-
-/***
- * jump_label_text_reserved - check if addr range is reserved
- * @start: start text addr
- * @end: end text addr
- *
- * checks if the text addr located between @start and @end
- * overlaps with any of the jump label patch addresses. Code
- * that wants to modify kernel text should first verify that
- * it does not overlap with any of the jump label addresses.
- * Caller must hold jump_label_mutex.
- *
- * returns 1 if there is an overlap, 0 otherwise
- */
-int jump_label_text_reserved(void *start, void *end)
+static int __jump_label_text_reserved(struct jump_entry *iter_start,
+		struct jump_entry *iter_stop, void *start, void *end)
 {
 	struct jump_entry *iter;
-	struct jump_entry *iter_start = __start___jump_table;
-	struct jump_entry *iter_stop = __start___jump_table;
-	int conflict = 0;
 
 	iter = iter_start;
 	while (iter < iter_stop) {
-		if (addr_conflict(iter, start, end)) {
-			conflict = 1;
-			goto out;
-		}
+		if (addr_conflict(iter, start, end))
+			return 1;
 		iter++;
 	}
 
-	/* now check modules */
-#ifdef CONFIG_MODULES
-	conflict = module_conflict(start, end);
-#endif
-out:
-	return conflict;
+	return 0;
+}
+
+static void __jump_label_update(struct jump_label_key *key, 
+		struct jump_entry *entry, int enable)
+{
+	for (; entry->key == (jump_label_t)key; entry++) {
+		if (WARN_ON_ONCE(!kernel_text_address(iter->code)))
+			continue;
+
+		arch_jump_label_transform(iter, enable);
+	}
 }
 
 /*

@@ -277,141 +118,155 @@ void __weak arch_jump_label_text_poke_early(jump_label_t addr)
 {
 }
 
-static __init int init_jump_label(void)
+static __init int jump_label_init(void)
 {
-	int ret;
 	struct jump_entry *iter_start = __start___jump_table;
 	struct jump_entry *iter_stop = __stop___jump_table;
+	struct jump_label_key *key = NULL;
 	struct jump_entry *iter;
 
 	jump_label_lock();
-	ret = build_jump_label_hashtable(__start___jump_table,
-					 __stop___jump_table);
-	iter = iter_start;
-	while (iter < iter_stop) {
+	jump_label_sort_entries(iter_start, iter_stop);
+
+	for (iter = iter_start; iter < iter_stop; iter++) {
 		arch_jump_label_text_poke_early(iter->code);
-		iter++;
+		if (iter->key == (jump_label_t)key)
+			continue;
+
+		key = (struct jump_label_key *)iter->key;
+		atomic_set(&key->enabled, 0);
+		key->entries = iter;
+#ifdef CONFIG_MODULES
+		key->next = NULL;
+#endif
 	}
 	jump_label_unlock();
-	return ret;
+
+	return 0;
 }
-early_initcall(init_jump_label);
+early_initcall(jump_label_init);
 
 #ifdef CONFIG_MODULES
 
-static struct jump_label_module_entry *
-add_jump_label_module_entry(struct jump_label_entry *entry,
-			    struct jump_entry *iter_begin,
-			    int count, struct module *mod)
-{
-	struct jump_label_module_entry *e;
-
-	e = kmalloc(sizeof(struct jump_label_module_entry), GFP_KERNEL);
-	if (!e)
-		return ERR_PTR(-ENOMEM);
-	e->mod = mod;
-	e->nr_entries = count;
-	e->table = iter_begin;
-	hlist_add_head(&e->hlist, &entry->modules);
-	return e;
-}
+struct jump_label_mod {
+	struct jump_label_mod *next;
+	struct jump_entry *entries;
+	struct module *mod;
+};
 
-static int add_jump_label_module(struct module *mod)
+static int __jump_label_mod_text_reserved(void *start, void *end)
 {
-	struct jump_entry *iter, *iter_begin;
-	struct jump_label_entry *entry;
-	struct jump_label_module_entry *module_entry;
-	int count;
+	struct module *mod;
 
-	/* if the module doesn't have jump label entries, just return */
-	if (!mod->num_jump_entries)
+	mod = __module_text_address(start);
+	if (!mod)
 		return 0;
 
-	sort_jump_label_entries(mod->jump_entries,
+	WARN_ON_ONCE(__module_text_address(end) != mod);
+
+	return __jump_label_text_reserved(mod->jump_entries,
 				mod->jump_entries + mod->num_jump_entries);
-	iter = mod->jump_entries;
-	while (iter < mod->jump_entries + mod->num_jump_entries) {
-		entry = get_jump_label_entry(iter->key);
-		iter_begin = iter;
-		count = 0;
-		while ((iter < mod->jump_entries + mod->num_jump_entries) &&
-			(iter->key == iter_begin->key)) {
-				iter++;
-				count++;
-		}
-		if (!entry) {
-			entry = add_jump_label_entry(iter_begin->key, 0, NULL);
-			if (IS_ERR(entry))
-				return PTR_ERR(entry);
-		}
-		module_entry = add_jump_label_module_entry(entry, iter_begin,
-							   count, mod);
-		if (IS_ERR(module_entry))
-			return PTR_ERR(module_entry);
+}
+
+static void __jump_label_mod_update(struct jump_label_key *key, int enable)
+{
+	struct jump_label_mod *mod = key->next;
+
+	while (mod) {
+		__jump_label_update(key, mod->entries, enable);
+		mod = mod->next;
 	}
-	return 0;
 }
 
-static void remove_jump_label_module(struct module *mod)
+/***
+ * apply_jump_label_nops - patch module jump labels with arch_get_jump_label_nop()
+ * @mod: module to patch
+ *
+ * Allow for run-time selection of the optimal nops. Before the module
+ * loads patch these with arch_get_jump_label_nop(), which is specified by
+ * the arch specific jump label code.
+ */
+static void jump_label_apply_nops(struct module *mod)
 {
-	struct hlist_head *head;
-	struct hlist_node *node, *node_next, *module_node, *module_node_next;
-	struct jump_label_entry *e;
-	struct jump_label_module_entry *e_module;
-	int i;
+	struct jump_entry *iter_start = mod->jump_entries;
+	struct jump_entry *iter_stop = mod->jump_entries + mod->num_jump_entries;
+	struct jump_entry *iter;
 
 	/* if the module doesn't have jump label entries, just return */
-	if (!mod->num_jump_entries)
+	if (iter_start == iter_stop)
 		return;
 
-	for (i = 0; i < JUMP_LABEL_TABLE_SIZE; i++) {
-		head = &jump_label_table[i];
-		hlist_for_each_entry_safe(e, node, node_next, head, hlist) {
-			hlist_for_each_entry_safe(e_module, module_node,
-						  module_node_next,
-						  &(e->modules), hlist) {
-				if (e_module->mod == mod) {
-					hlist_del(&e_module->hlist);
-					kfree(e_module);
-				}
-			}
-			if (hlist_empty(&e->modules) && (e->nr_entries == 0)) {
-				hlist_del(&e->hlist);
-				kfree(e);
-			}
+	jump_label_sort_entries(iter_start, iter_stop);
+
+	for (iter = iter_start; iter < iter_stop; iter++)
+		arch_jump_label_text_poke_early(iter->code);
+}
+
+static int jump_label_add_module(struct module *mod)
+{
+	struct jump_entry *iter_start = mod->jump_entries;
+	struct jump_entry *iter_stop = mod->jump_entries + mod->num_jump_entries;
+	struct jump_entry *iter;
+	struct jump_label_key *key = NULL;
+	struct jump_label_mod *jlm;
+
+	for (iter = iter_start; iter < iter_stop; iter++) {
+		if (iter->key == (jump_label_t)key)
+			continue;
+
+		key = (struct jump_label_key)iter->key;
+
+		if (__module_address(iter->key) == mod) {
+			atomic_set(&key->enabled, 0);
+			key->entries = iter;
+			key->next = NULL;
+			continue;
 		}
+
+		jlm = kzalloc(sizeof(struct jump_label_mod), GFP_KERNEL);
+		if (!jlm)
+			return -ENOMEM;
+
+		jlm->mod = mod;
+		jlm->entries = iter;
+		jlm->next = key->next;
+		key->next = jlm;
+
+		if (jump_label_enabled(key))
+			__jump_label_update(key, iter, JUMP_LABEL_ENABLE);
 	}
+
+	return 0;
 }
 
-static void remove_jump_label_module_init(struct module *mod)
+static void jump_label_del_module(struct module *mod)
 {
-	struct hlist_head *head;
-	struct hlist_node *node, *node_next, *module_node, *module_node_next;
-	struct jump_label_entry *e;
-	struct jump_label_module_entry *e_module;
+	struct jump_entry *iter_start = mod->jump_entries;
+	struct jump_entry *iter_stop = mod->jump_entries + mod->num_jump_entries;
 	struct jump_entry *iter;
-	int i, count;
+	struct jump_label_key *key = NULL;
+	struct jump_label_mod *jlm, **prev;
 
-	/* if the module doesn't have jump label entries, just return */
-	if (!mod->num_jump_entries)
-		return;
+	for (iter = iter_start; iter < iter_stop; iter++) {
+		if (iter->key == (jump_label_t)key)
+			continue;
+
+		key = (struct jump_label_key)iter->key;
+
+		if (__module_address(iter->key) == mod)
+			continue;
+
+		prev = &key->next;
+		jlm = key->next;
+
+		while (jlm && jlm->mod != mod) {
+			prev = &jlm->next;
+			jlm = jlm->next;
+		}
 
-	for (i = 0; i < JUMP_LABEL_TABLE_SIZE; i++) {
-		head = &jump_label_table[i];
-		hlist_for_each_entry_safe(e, node, node_next, head, hlist) {
-			hlist_for_each_entry_safe(e_module, module_node,
-						  module_node_next,
-						  &(e->modules), hlist) {
-				if (e_module->mod != mod)
-					continue;
-				count = e_module->nr_entries;
-				iter = e_module->table;
-				while (count--) {
-					if (within_module_init(iter->code, mod))
-						iter->key = 0;
-					iter++;
-				}
-			}
+		if (jlm) {
+			*prev = jlm->next;
+			kfree(jlm);
 		}
 	}
 }

@@ -424,61 +279,76 @@ jump_label_module_notify(struct notifier_block *self, unsigned long val,
 	int ret = 0;
 
 	switch (val) {
-	case MODULE_STATE_COMING:
+	case MODULE_STATE_POST_RELOCATE:
 		jump_label_lock();
-		ret = add_jump_label_module(mod);
-		if (ret)
-			remove_jump_label_module(mod);
+		jump_label_apply_nops(mod);
 		jump_label_unlock();
 		break;
-	case MODULE_STATE_GOING:
+	case MODULE_STATE_COMING:
 		jump_label_lock();
-		remove_jump_label_module(mod);
+		ret = jump_label_add_module(mod);
+		if (ret)
+			jump_label_del_module(mod);
 		jump_label_unlock();
 		break;
-	case MODULE_STATE_LIVE:
+	case MODULE_STATE_GOING:
 		jump_label_lock();
-		remove_jump_label_module_init(mod);
+		jump_label_del_module(mod);
 		jump_label_unlock();
 		break;
 	}
 	return ret;
 }
 
+struct notifier_block jump_label_module_nb = {
+	.notifier_call = jump_label_module_notify,
+	.priority = 1, /* higher than tracepoints */
+};
+
+static __init int jump_label_init_module(void)
+{
+	return register_module_notifier(&jump_label_module_nb);
+}
+early_initcall(jump_label_init_module);
+
+#endif /* CONFIG_MODULES */
+
 /***
- * apply_jump_label_nops - patch module jump labels with arch_get_jump_label_nop()
- * @mod: module to patch
+ * jump_label_text_reserved - check if addr range is reserved
+ * @start: start text addr
+ * @end: end text addr
  *
- * Allow for run-time selection of the optimal nops. Before the module
- * loads patch these with arch_get_jump_label_nop(), which is specified by
- * the arch specific jump label code.
+ * checks if the text addr located between @start and @end
+ * overlaps with any of the jump label patch addresses. Code
+ * that wants to modify kernel text should first verify that
+ * it does not overlap with any of the jump label addresses.
+ * Caller must hold jump_label_mutex.
+ *
+ * returns 1 if there is an overlap, 0 otherwise
  */
-void jump_label_apply_nops(struct module *mod)
+int jump_label_text_reserved(void *start, void *end)
 {
-	struct jump_entry *iter;
+	int ret = __jump_label_text_reserved(__start___jump_table,
+			__stop___jump_table, start, end);
 
-	/* if the module doesn't have jump label entries, just return */
-	if (!mod->num_jump_entries)
-		return;
+	if (ret)
+		return ret;
 
-	iter = mod->jump_entries;
-	while (iter < mod->jump_entries + mod->num_jump_entries) {
-		arch_jump_label_text_poke_early(iter->code);
-		iter++;
-	}
+#ifdef CONFIG_MODULES
+	ret = __jump_label_mod_text_reserved(start, end);
+#endif
+	return ret;
 }
 
-struct notifier_block jump_label_module_nb = {
-	.notifier_call = jump_label_module_notify,
-	.priority = 0,
-};
-
-static __init int init_jump_label_module(void)
+static void jump_label_update(struct jump_label_key *key, int enable)
 {
-	return register_module_notifier(&jump_label_module_nb);
-}
-early_initcall(init_jump_label_module);
+	struct jump_entry *entry = key->entries;
 
-#endif /* CONFIG_MODULES */
+	__jump_label_update(key, entry, enable);
+
+#ifdef CONFIG_MODULES
+	__jump_label_mod_update(key, enable);
+#endif
+}
 
 #endif

kernel/module.c +7 -0

index efa290e..890cadf 100644
@@ -2789,6 +2789,13 @@ static struct module *load_module(void __user *umod,
 		goto unlock;
 	}
 
+	err = blocking_notifier_call_chain(&module_notify_list,
+			MODULE_STATE_POST_RELOCATE, mod);
+	if (err != NOTIFY_DONE) {
+		err = notifier_to_errno(err);
+		goto unlock;
+	}
+
 	/* This has to be done once we're sure module name is unique. */
 	if (!mod->taints)
 		dynamic_debug_setup(info.debug, info.num_debug);

kernel/perf_event.c +21 -9

index a353a4d..7bacdd3 100644
@@ -117,7 +117,7 @@ enum event_type_t {
 	EVENT_ALL = EVENT_FLEXIBLE | EVENT_PINNED,
 };
 
-atomic_t perf_task_events __read_mostly;
+struct jump_label_key_counter perf_task_events __read_mostly;
 static atomic_t nr_mmap_events __read_mostly;
 static atomic_t nr_comm_events __read_mostly;
 static atomic_t nr_task_events __read_mostly;

@@ -2383,8 +2383,10 @@ static void free_event(struct perf_event *event)
 	irq_work_sync(&event->pending);
 
 	if (!event->parent) {
-		if (event->attach_state & PERF_ATTACH_TASK)
-			jump_label_dec(&perf_task_events);
+		if (event->attach_state & PERF_ATTACH_TASK) {
+			if (atomic_dec_and_test(&perf_task_events.ref))
+				jump_label_disable(&perf_task_events.key);
+		}
 		if (event->attr.mmap || event->attr.mmap_data)
 			atomic_dec(&nr_mmap_events);
 		if (event->attr.comm)

@@ -4912,7 +4914,7 @@ fail:
 	return err;
 }
 
-atomic_t perf_swevent_enabled[PERF_COUNT_SW_MAX];
+struct jump_label_key_counter perf_swevent_enabled[PERF_COUNT_SW_MAX];
 
 static void sw_perf_event_destroy(struct perf_event *event)
 {

@@ -4920,7 +4922,8 @@ static void sw_perf_event_destroy(struct perf_event *event)
 
 	WARN_ON(event->parent);
 
-	jump_label_dec(&perf_swevent_enabled[event_id]);
+	if (atomic_dec_and_test(&perf_swevent_enabled[event_id].ref))
+		jump_label_disable(&perf_swevent_enabled[event_id].key);
 	swevent_hlist_put(event);
 }
 

@@ -4945,12 +4948,15 @@ static int perf_swevent_init(struct perf_event *event)
 
 	if (!event->parent) {
 		int err;
+		atomic_t *ref;
 
 		err = swevent_hlist_get(event);
 		if (err)
 			return err;
 
-		jump_label_inc(&perf_swevent_enabled[event_id]);
+		ref = &perf_swevent_enabled[event_id].ref;
+		if (atomic_add_return(1, ref) == 1)
+			jump_label_enable(&perf_swevent_enabled[event_id].key);
 		event->destroy = sw_perf_event_destroy;
 	}
 

@@ -5123,6 +5129,10 @@ static enum hrtimer_restart perf_swevent_hrtimer(struct hrtimer *hrtimer)
 	u64 period;
 
 	event = container_of(hrtimer, struct perf_event, hw.hrtimer);
+
+	if (event->state < PERF_EVENT_STATE_ACTIVE)
+		return HRTIMER_NORESTART;
+
 	event->pmu->read(event);
 
 	perf_sample_data_init(&data, 0);

@@ -5174,7 +5184,7 @@ static void perf_swevent_cancel_hrtimer(struct perf_event *event)
 		ktime_t remaining = hrtimer_get_remaining(&hwc->hrtimer);
 		local64_set(&hwc->period_left, ktime_to_ns(remaining));
 
-		hrtimer_cancel(&hwc->hrtimer);
+		hrtimer_try_to_cancel(&hwc->hrtimer);
 	}
 }
 

@@ -5713,8 +5723,10 @@ done:
 	event->pmu = pmu;
 
 	if (!event->parent) {
-		if (event->attach_state & PERF_ATTACH_TASK)
-			jump_label_inc(&perf_task_events);
+		if (event->attach_state & PERF_ATTACH_TASK) {
+			if (atomic_add_return(1, &perf_task_events.ref) == 1)
+				jump_label_enable(&perf_task_events.key);
+		}
 		if (event->attr.mmap || event->attr.mmap_data)
 			atomic_inc(&nr_mmap_events);
 		if (event->attr.comm)

kernel/timer.c +3 -5

index 343ff27..c848cd8 100644
@@ -959,7 +959,7 @@ EXPORT_SYMBOL(try_to_del_timer_sync);
  *
  * Synchronization rules: Callers must prevent restarting of the timer,
  * otherwise this function is meaningless. It must not be called from
- * hardirq contexts. The caller must not hold locks which would prevent
+ * interrupt contexts. The caller must not hold locks which would prevent
  * completion of the timer's handler. The timer's handler must not call
  * add_timer_on(). Upon exit the timer is not queued and the handler is
  * not running on any CPU.

@@ -971,12 +971,10 @@ int del_timer_sync(struct timer_list *timer)
 #ifdef CONFIG_LOCKDEP
 	unsigned long flags;
 
-	raw_local_irq_save(flags);
-	local_bh_disable();
+	local_irq_save(flags);
 	lock_map_acquire(&timer->lockdep_map);
 	lock_map_release(&timer->lockdep_map);
-	_local_bh_enable();
-	raw_local_irq_restore(flags);
+	local_irq_restore(flags);
 #endif
 	/*
 	 * don't use it in hardirq context, because it

kernel/tracepoint.c +8 -14

index 68187af..13066e8 100644
@@ -251,9 +251,9 @@ static void set_tracepoint(struct tracepoint_entry **entry,
 {
 	WARN_ON(strcmp((*entry)->name, elem->name) != 0);
 
-	if (elem->regfunc && !elem->state && active)
+	if (elem->regfunc && !jump_label_enabled(&elem->key) && active)
 		elem->regfunc();
-	else if (elem->unregfunc && elem->state && !active)
+	else if (elem->unregfunc && jump_label_enabled(&elem->key) && !active)
 		elem->unregfunc();
 
 	/*

@@ -264,13 +264,10 @@ static void set_tracepoint(struct tracepoint_entry **entry,
 	 * is used.
 	 */
 	rcu_assign_pointer(elem->funcs, (*entry)->funcs);
-	if (!elem->state && active) {
-		jump_label_enable(&elem->state);
-		elem->state = active;
-	} else if (elem->state && !active) {
-		jump_label_disable(&elem->state);
-		elem->state = active;
-	}
+	if (active)
+		jump_label_enable(&elem->key);
+	else if (!active)
+		jump_label_disable(&elem->key);
 }
 
 /*

@@ -281,13 +278,10 @@ static void set_tracepoint(struct tracepoint_entry **entry,
  */
 static void disable_tracepoint(struct tracepoint *elem)
 {
-	if (elem->unregfunc && elem->state)
+	if (elem->unregfunc && jump_label_enabled(&elem->key))
 		elem->unregfunc();
 
-	if (elem->state) {
-		jump_label_disable(&elem->state);
-		elem->state = 0;
-	}
+	jump_label_disable(&elem->key);
 	rcu_assign_pointer(elem->funcs, NULL);
 }