jump label: introduce default true branch

RFC PATCH In review Jason Baron 3 participants 9 messages Dec 21, 2011 – Feb 21, 2012

Subsystems (4)

perf events Tracing Scheduler Static branch/call

lore

Share & tools

lore

Jason Baron

author

2011-12-21 19:09 UTC #0 lore raw

cover jump label: introduce default true branch

Hi Peter,

I've introduced a new static_branch_def_true() construct, such that the straight line path is the true branch, and we patch a jump to get to the false branch. In order to make jump_label_inc()/dec() work as 'make true'/'make false' with counting, I've had to update some of the core jump label code. This patchset also
introduces: JUMP_LABEL_INIT_TRUE/FALSE, so that keys should be initialized as:

struct jump_label_key true_key = JUMP_LABEL_INIT_TRUE;

struct jump_label_key false_key = JUMP_LABEL_INIT_FALSE;

I think this patch series should address the issues that came up with sched_feat() implementation.

Thanks,

-Jason

Jason Baron (4):
jump label: Introduce default true branch + API update
perf: Make use of updated jump label API.
tracepoints: update to use new jump label API.
sched: Make use of new jump label API.

 include/linux/jump_label.h |   77 ++++++++++++++++++++++++++++++++++++-------
 include/linux/perf_event.h |    6 ++--
 include/linux/tracepoint.h |    4 +-
 kernel/jump_label.c        |   66 +++++++++++++++++++++++++------------
 kernel/sched/core.c        |   12 +++---
 kernel/sched/fair.c        |    2 +-
 kernel/sched/sched.h       |   11 +------
 kernel/tracepoint.c        |   12 +++---
 8 files changed, 128 insertions(+), 62 deletions(-)

Signature · 1 line

1.7.7.3

Jason Baron

author

2011-12-21 19:09 UTC #1 lore raw

PATCH 1/4 jump label: Introduce default true branch + API update

The current static_branch() construct, assumes that the branch will be disabled by default. This means we have a single no-op in the straight line path, and when the branch is made true we patch the no-op with a jump.

There are cases (sched feat code), where we want the branch to default to true, so that the straight line code is the true branch, and the false branch is enabled via a jump.

In order to implement this while having, jump_label_inc(), and jump_label_dec() retain their current meaning, we have to store the initial branch state. I'm using the lowest bit of the 'entries' pointer in the jump_label_key struct, since this points to memory that has to be aligned to the arch pointer size. We could have stored this in the 'struct jump_entry' data structure, but I wanted to avoid adding additional space overhead.

Thus, the new API is initialized as:

	struct jump_label_key true_key = JUMP_LABEL_INIT_TRUE;

			or

	struct jump_label_key false_key = JUMP_LABEL_INIT_FALSE;

Leaving out an initialization, defaults to false, as in:

	struct jump_label_key uninitialized_key;

Then, for the branches we have:

	static_branch_def_false(false_key);

		or

	static_branch_def_true(true_key);

And finally, jump_label_inc(&key), jump_label_dec(&key) are unchanged - 'jump_label_inc()' means 'make true', and jump_label_dec()' means make false, with the expected increment/decrement counting.

Thus, you must use 'true_key' with a 'static_branch_def_true' branch, and a 'false_key' or a 'uninitialized_key' with a 'static_branch_def_false' branch. Mixing different static branches with the same jump_label_key is not allowed.

I've left the old static_branch(), (which is the same as the new static_branch_def_false()), at least until we've converted over all in-tree and pending users.

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

---
 include/linux/jump_label.h |   77 ++++++++++++++++++++++++++++++++++++-------
 kernel/jump_label.c        |   66 +++++++++++++++++++++++++------------
 2 files changed, 109 insertions(+), 34 deletions(-)

include/linux/jump_label.h +64 ~~-13~~

index 5ce8b14..a885b5f 100644
@@ -9,6 +9,7 @@
 
 struct jump_label_key {
 	atomic_t enabled;
+/* Set lsb bit to 1 if branch is default true, 0 ot */
 	struct jump_entry *entries;
 #ifdef CONFIG_MODULES
 	struct jump_label_mod *next;

@@ -34,17 +35,37 @@ struct module;
 
 #ifdef HAVE_JUMP_LABEL
 
-#ifdef CONFIG_MODULES
-#define JUMP_LABEL_INIT {ATOMIC_INIT(0), NULL, NULL}
-#else
-#define JUMP_LABEL_INIT {ATOMIC_INIT(0), NULL}
-#endif
+#define JUMP_LABEL_TRUE_BRANCH 1UL
+
+static
+inline struct jump_entry *jump_label_get_entries(struct jump_label_key *key)
+{
+	return (struct jump_entry *)((unsigned long)key->entries
+						& ~JUMP_LABEL_TRUE_BRANCH);
+}
+
+static inline bool jump_label_get_branch_default(struct jump_label_key *key)
+{
+	if ((unsigned long)key->entries & JUMP_LABEL_TRUE_BRANCH)
+		return true;
+	return false;
+}
 
 static __always_inline bool static_branch(struct jump_label_key *key)
 {
 	return arch_static_branch(key);
 }
 
+static __always_inline bool static_branch_def_false(struct jump_label_key *key)
+{
+	return arch_static_branch(key);
+}
+
+static __always_inline bool static_branch_def_true(struct jump_label_key *key)
+{
+	return !static_branch_def_false(key);
+}
+
 extern struct jump_entry __start___jump_table[];
 extern struct jump_entry __stop___jump_table[];

@@ -59,17 +80,27 @@ extern int jump_label_text_reserved(void *start, void *end);
 extern void jump_label_inc(struct jump_label_key *key);
 extern void jump_label_dec(struct jump_label_key *key);
 extern void jump_label_dec_deferred(struct jump_label_key_deferred *key);
-extern bool jump_label_enabled(struct jump_label_key *key);
+extern bool jump_label_true(struct jump_label_key *key);
 extern void jump_label_apply_nops(struct module *mod);
 extern void jump_label_rate_limit(struct jump_label_key_deferred *key,
 		unsigned long rl);
 
+#ifdef CONFIG_MODULES
+ #define JUMP_LABEL_INIT_TRUE ((struct jump_label_key) \
+	{ .enabled = ATOMIC_INIT(1), .entries = (void *)1, .next = NULL  })
+ #define JUMP_LABEL_INIT_FALSE ((struct jump_label_key) \
+	{ .enabled = ATOMIC_INIT(0), .entries = (void *)0, .next = NULL })
+#else
+ #define JUMP_LABEL_INIT_TRUE ((struct jump_label_key) \
+	{ .enabled = ATOMIC_INIT(1), .entries = (void *)1  })
+ #define JUMP_LABEL_INIT_FALSE ((struct jump_label_key) \
+	{ .enabled = ATOMIC_INIT(0), .entries = (void *)0 })
+#endif
+
 #else  /* !HAVE_JUMP_LABEL */
 
 #include <linux/atomic.h>
 
-#define JUMP_LABEL_INIT {ATOMIC_INIT(0)}
-
 struct jump_label_key {
 	atomic_t enabled;
 };

@@ -84,7 +115,21 @@ struct jump_label_key_deferred {
 
 static __always_inline bool static_branch(struct jump_label_key *key)
 {
-	if (unlikely(atomic_read(&key->enabled)))
+	if (unlikely(atomic_read(&key->enabled)) > 0)
+		return true;
+	return false;
+}
+
+static __always_inline bool static_branch_def_false(struct jump_label_key *key)
+{
+	if (unlikely(atomic_read(&key->enabled)) > 0)
+		return true;
+	return false;
+}
+
+static __always_inline bool static_branch_def_true(struct jump_label_key *key)
+{
+	if (likely(atomic_read(&key->enabled)) > 0)
 		return true;
 	return false;
 }

@@ -112,9 +157,9 @@ static inline int jump_label_text_reserved(void *start, void *end)
 static inline void jump_label_lock(void) {}
 static inline void jump_label_unlock(void) {}
 
-static inline bool jump_label_enabled(struct jump_label_key *key)
+static inline bool jump_label_true(struct jump_label_key *key)
 {
-	return !!atomic_read(&key->enabled);
+	return (atomic_read(&key->enabled) > 0);
 }
 
 static inline int jump_label_apply_nops(struct module *mod)

@@ -126,9 +171,15 @@ static inline void jump_label_rate_limit(struct jump_label_key_deferred *key,
 		unsigned long rl)
 {
 }
+
+#define JUMP_LABEL_INIT_TRUE ((struct jump_label_key) \
+		{ .enabled = ATOMIC_INIT(1) })
+#define JUMP_LABEL_INIT_FALSE ((struct jump_label_key) \
+		{ .enabled = ATOMIC_INIT(0) })
+
 #endif	/* HAVE_JUMP_LABEL */
 
-#define jump_label_key_enabled	((struct jump_label_key){ .enabled = ATOMIC_INIT(1), })
-#define jump_label_key_disabled	((struct jump_label_key){ .enabled = ATOMIC_INIT(0), })
+#define JUMP_LABEL_INIT JUMP_LABEL_INIT_FALSE
+#define jump_label_enabled jump_label_true
 
 #endif	/* _LINUX_JUMP_LABEL_H */

kernel/jump_label.c +45 ~~-21~~

150 lines not on this page · raw message

Signature · 1 line

1.7.7.3

Jason Baron

author

2011-12-21 19:10 UTC #2 lore raw

PATCH 2/4 perf: Make use of updated jump label API.

In reply to Jason Baron

Use new jump label API.

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

---
 include/linux/perf_event.h |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

include/linux/perf_event.h +3 -3

index 564769c..a91989f 100644
@@ -1055,7 +1055,7 @@ perf_sw_event(u32 event_id, u64 nr, struct pt_regs *regs, u64 addr)
 {
 	struct pt_regs hot_regs;
 
-	if (static_branch(&perf_swevent_enabled[event_id])) {
+	if (static_branch_def_false(&perf_swevent_enabled[event_id])) {
 		if (!regs) {
 			perf_fetch_caller_regs(&hot_regs);
 			regs = &hot_regs;

@@ -1069,7 +1069,7 @@ extern struct jump_label_key_deferred perf_sched_events;
 static inline void perf_event_task_sched_in(struct task_struct *prev,
 					    struct task_struct *task)
 {
-	if (static_branch(&perf_sched_events.key))
+	if (static_branch_def_false(&perf_sched_events.key))
 		__perf_event_task_sched_in(prev, task);
 }

@@ -1078,7 +1078,7 @@ static inline void perf_event_task_sched_out(struct task_struct *prev,
 {
 	perf_sw_event(PERF_COUNT_SW_CONTEXT_SWITCHES, 1, NULL, 0);
 
-	if (static_branch(&perf_sched_events.key))
+	if (static_branch_def_false(&perf_sched_events.key))
 		__perf_event_task_sched_out(prev, next);
 }

Signature · 1 line

1.7.7.3

Jason Baron

author

2011-12-21 19:09 UTC #3 lore raw

PATCH 3/4 tracepoints: update to use new jump label API.

In reply to Jason Baron

Update tracepoints.

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

---
 include/linux/tracepoint.h |    4 ++--
 kernel/tracepoint.c        |   12 ++++++------
 2 files changed, 8 insertions(+), 8 deletions(-)

include/linux/tracepoint.h +2 -2

index df0a779..d167ec2 100644
@@ -143,7 +143,7 @@ static inline void tracepoint_synchronize_unregister(void)
 	extern struct tracepoint __tracepoint_##name;			\
 	static inline void trace_##name(proto)				\
 	{								\
-		if (static_branch(&__tracepoint_##name.key))		\
+		if (static_branch_def_false(&__tracepoint_##name.key))	\
 			__DO_TRACE(&__tracepoint_##name,		\
 				TP_PROTO(data_proto),			\
 				TP_ARGS(data_args),			\

@@ -176,7 +176,7 @@ static inline void tracepoint_synchronize_unregister(void)
 	__attribute__((section("__tracepoints_strings"))) = #name;	 \
 	struct tracepoint __tracepoint_##name				 \
 	__attribute__((section("__tracepoints"))) =			 \
-		{ __tpstrtab_##name, JUMP_LABEL_INIT, reg, unreg, NULL };\
+		{ __tpstrtab_##name, JUMP_LABEL_INIT_FALSE, reg, unreg, NULL };\
 	static struct tracepoint * const __tracepoint_ptr_##name __used	 \
 	__attribute__((section("__tracepoints_ptrs"))) =		 \
 		&__tracepoint_##name;

kernel/tracepoint.c +6 -6

index db110b8..bc7f0ea 100644
@@ -256,9 +256,9 @@ static void set_tracepoint(struct tracepoint_entry **entry,
 {
 	WARN_ON(strcmp((*entry)->name, elem->name) != 0);
 
-	if (elem->regfunc && !jump_label_enabled(&elem->key) && active)
+	if (elem->regfunc && !jump_label_true(&elem->key) && active)
 		elem->regfunc();
-	else if (elem->unregfunc && jump_label_enabled(&elem->key) && !active)
+	else if (elem->unregfunc && jump_label_true(&elem->key) && !active)
 		elem->unregfunc();
 
 	/*

@@ -269,9 +269,9 @@ static void set_tracepoint(struct tracepoint_entry **entry,
 	 * is used.
 	 */
 	rcu_assign_pointer(elem->funcs, (*entry)->funcs);
-	if (active && !jump_label_enabled(&elem->key))
+	if (active && !jump_label_true(&elem->key))
 		jump_label_inc(&elem->key);
-	else if (!active && jump_label_enabled(&elem->key))
+	else if (!active && jump_label_true(&elem->key))
 		jump_label_dec(&elem->key);
 }

@@ -283,10 +283,10 @@ static void set_tracepoint(struct tracepoint_entry **entry,
  */
 static void disable_tracepoint(struct tracepoint *elem)
 {
-	if (elem->unregfunc && jump_label_enabled(&elem->key))
+	if (elem->unregfunc && jump_label_true(&elem->key))
 		elem->unregfunc();
 
-	if (jump_label_enabled(&elem->key))
+	if (jump_label_true(&elem->key))
 		jump_label_dec(&elem->key);
 	rcu_assign_pointer(elem->funcs, NULL);
 }

Signature · 1 line

1.7.7.3

Jason Baron

author

2011-12-21 19:09 UTC #4 lore raw

PATCH 4/4 sched: Make use of new jump label API.

In reply to Jason Baron

Update scheduler.

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

---
 kernel/sched/core.c  |   12 ++++++------
 kernel/sched/fair.c  |    2 +-
 kernel/sched/sched.h |   11 +----------
 3 files changed, 8 insertions(+), 17 deletions(-)

kernel/sched/core.c +6 -6

index c7ea688..9b8c4fd 100644
@@ -161,8 +161,8 @@ static int sched_feat_show(struct seq_file *m, void *v)
 
 #ifdef HAVE_JUMP_LABEL
 
-#define jump_label_key__true  jump_label_key_enabled
-#define jump_label_key__false jump_label_key_disabled
+#define jump_label_key__true  JUMP_LABEL_INIT_TRUE
+#define jump_label_key__false JUMP_LABEL_INIT_FALSE
 
 #define SCHED_FEAT(name, enabled)	\
 	jump_label_key__##enabled ,

@@ -175,13 +175,13 @@ struct jump_label_key sched_feat_keys[__SCHED_FEAT_NR] = {
 
 static void sched_feat_disable(int i)
 {
-	if (jump_label_enabled(&sched_feat_keys[i]))
+	if (jump_label_true(&sched_feat_keys[i]))
 		jump_label_dec(&sched_feat_keys[i]);
 }
 
 static void sched_feat_enable(int i)
 {
-	if (!jump_label_enabled(&sched_feat_keys[i]))
+	if (!jump_label_true(&sched_feat_keys[i]))
 		jump_label_inc(&sched_feat_keys[i]);
 }
 #else

@@ -899,7 +899,7 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 	delta -= irq_delta;
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
-	if (static_branch((&paravirt_steal_rq_enabled))) {
+	if (static_branch_def_false((&paravirt_steal_rq_enabled))) {
 		u64 st;
 
 		steal = paravirt_steal_clock(cpu_of(rq));

@@ -2760,7 +2760,7 @@ void account_idle_time(cputime_t cputime)
 static __always_inline bool steal_account_process_tick(void)
 {
 #ifdef CONFIG_PARAVIRT
-	if (static_branch(&paravirt_steal_enabled)) {
+	if (static_branch_def_false(&paravirt_steal_enabled)) {
 		u64 steal, st = 0;
 
 		steal = paravirt_steal_clock(smp_processor_id());

kernel/sched/fair.c +1 -1

index a4d2b7a..877c2ec 100644
@@ -1405,7 +1405,7 @@ static struct jump_label_key __cfs_bandwidth_used;
 
 static inline bool cfs_bandwidth_used(void)
 {
-	return static_branch(&__cfs_bandwidth_used);
+	return static_branch_def_false(&__cfs_bandwidth_used);
 }
 
 void account_cfs_bandwidth_used(int enabled, int was_enabled)

kernel/sched/sched.h +1 ~~-10~~

index d8d3613..d2f930c 100644
@@ -600,20 +600,11 @@ enum {
 #undef SCHED_FEAT
 
 #if defined(CONFIG_SCHED_DEBUG) && defined(HAVE_JUMP_LABEL)
-static __always_inline bool static_branch__true(struct jump_label_key *key)
-{
-	return likely(static_branch(key)); /* Not out of line branch. */
-}
-
-static __always_inline bool static_branch__false(struct jump_label_key *key)
-{
-	return unlikely(static_branch(key)); /* Out of line branch. */
-}
 
 #define SCHED_FEAT(name, enabled)					\
 static __always_inline bool static_branch_##name(struct jump_label_key *key) \
 {									\
-	return static_branch__##enabled(key);				\
+	return static_branch_def_##enabled(key);				\
 }
 
 #include "features.h"

Signature · 1 line

1.7.7.3

Peter Zijlstra

2011-12-21 19:49 UTC #5 lore raw

In reply to Jason Baron

Quoted 7 lines · Jason Baron

Hi Peter,
I've introduced a new static_branch_def_true() construct, such that the straight line path is the true branch, and we patch a jump to get to the false branch.
I think this patch series should address the issues that came up with sched_feat() implementation.

Nice trick, I've only casually read patch 1 because my brain gave up for the day, but I'll have a closer look tomorrow.

H. Peter Anvin

2012-02-20 22:48 UTC #6 lore raw

In reply to Jason Baron

Quoted 8 lines · Jason Baron

Hi Peter,
I've introduced a new static_branch_def_true() construct, such that the straight line path is the true branch, and we patch a jump to get to the false branch. In order to make jump_label_inc()/dec() work as 'make true'/'make false' with counting, I've had to update some of the core jump label code. This patchset also
introduces: JUMP_LABEL_INIT_TRUE/FALSE, so that keys should be initialized as:

Quoted 9 lines

struct jump_label_key true_key = JUMP_LABEL_INIT_TRUE;
or
struct jump_label_key false_key = JUMP_LABEL_INIT_FALSE;
I think this patch series should address the issues that came up with sched_feat() implementation.

Hi,

Did this ever get addressed?

-hpa

Signature · 2 lines

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

Peter Zijlstra

2012-02-20 22:51 UTC #7 lore raw

Quoted 15 lines · H. Peter Anvin

Quoted 14 lines · Jason Baron
Hi Peter,
I've introduced a new static_branch_def_true() construct, such that the straight line path is the true branch, and we patch a jump to get to the false branch. In order to make jump_label_inc()/dec() work as 'make true'/'make false' with counting, I've had to update some of the core jump label code. This patchset also
introduces: JUMP_LABEL_INIT_TRUE/FALSE, so that keys should be initialized as:
struct jump_label_key true_key = JUMP_LABEL_INIT_TRUE;
or
struct jump_label_key false_key = JUMP_LABEL_INIT_FALSE;

Quoted 7 lines

Quoted 3 lines
I think this patch series should address the issues that came up with sched_feat() implementation.
Hi,
Did this ever get addressed?

I actually tried to push that stuff to Ingo, he figured it all should have different names. Jason and Ingo went back and forth for a while and afaik settled on something. Jason then went off to implement, but I haven't yet seen a new version.

Jason Baron

author

2012-02-21 14:36 UTC #8 lore raw

Quoted 20 lines · Peter Zijlstra

Quoted 19 lines · H. Peter Anvin
Quoted 17 lines · Jason Baron
Hi Peter,
I've introduced a new static_branch_def_true() construct, such that the straight line path is the true branch, and we patch a jump to get to the false branch. In order to make jump_label_inc()/dec() work as 'make true'/'make false' with counting, I've had to update some of the core jump label code. This patchset also
introduces: JUMP_LABEL_INIT_TRUE/FALSE, so that keys should be initialized as:
struct jump_label_key true_key = JUMP_LABEL_INIT_TRUE;
or
struct jump_label_key false_key = JUMP_LABEL_INIT_FALSE;
I think this patch series should address the issues that came up with sched_feat() implementation.

Quoted 10 lines

Quoted 3 lines
Hi,
Did this ever get addressed?
I actually tried to push that stuff to Ingo, he figured it all should have different names. Jason and Ingo went back and forth for a while and afaik settled on something. Jason then went off to implement, but I haven't yet seen a new version.

I'll post a patch series later today.

Thanks,

-Jason