[PATCH/RFC 0/2] jump label: simplify API

[PATCH/RFC 0/2] jump label: simplify API

[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 unlikely_switch(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 (unlikely_switch(&jump_key))
		do unlikely code

enable/disale via:

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

that's it!

Thanks to H. Peter Anvin for suggesting the simpler 'unlikely_switch()'
function.

thanks,

-Jason


Jason Baron (2):
  jump label: make enable/disable o(1)
  jump label: introduce unlikely_switch()

 arch/x86/include/asm/jump_label.h |   22 +++--
 arch/x86/kernel/jump_label.c      |    2 +-
 include/linux/dynamic_debug.h     |   24 ++----
 include/linux/jump_label.h        |   72 ++++++++++-------
 include/linux/jump_label_ref.h    |   41 ++++++----
 include/linux/perf_event.h        |   25 +++---
 include/linux/tracepoint.h        |    8 +-
 kernel/jump_label.c               |  159 ++++++++++++++++++++++++++++++-------
 kernel/perf_event.c               |    4 +-
 kernel/tracepoint.c               |   22 ++---
 10 files changed, 243 insertions(+), 136 deletions(-)

[PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Jason Baron]

Previously, I allowed any variable type to be used as the 'key' for
the jump label. However, by enforcing a type, we can make use of the
contents of the 'key'. This patch thus introduces:

struct jump_label_key {
       void *ptr;
};

The 'ptr' is used a pointer into the jump label table of the
corresponding addresses that need to be updated. Thus, when jump labels
are enabled/disabled we have a constant time algorithm. There is no
longer any hashing.

When jump lables are disabled we simply have:

struct jump_label_key {
        int state;
};

I've also defined an analogous structure for ref counted jump labels as
per a request from Peter.

struct jump_label_keyref {
       void *ptr;
};

And for the jump labels disabled case:


struct jump_label_keyref {
        atomic_t refcount;
};

The reason I've introduced an additional structure for the reference counted
jump labels is twofold:

1) For the jump labels disabled case, reference counted jump labels use an
atomic_read(). I didn't want to impact the jump labels disabled case for
tracepoints which simply accesses an 'int'.

2) By introducing a second type, we have two parallel APIs:

extern void jump_label_enable(struct jump_label_key *key);
extern void jump_label_disable(struct jump_label_key *key);

static inline void jump_label_inc(struct jump_label_keyref *key)
static inline void jump_label_dec(struct jump_label_keyref *key)

In this way, we can't mix up the reference counted API, with the straight
enable/disable API since they accept different types.


I tested enable/disable times on x86 on a quad core via:

 time echo 1 > /sys/kernel/debug/tracing/events/enable

With this patch, runs average .03s. Prior to the jump label infrastructure
this command averaged around .01s.

We can speed this path up further via batching the enable/disables.

thanks,

-Jason

Signed-off-by: Jason Baron <jbaron@redhat.com>
---
 include/linux/dynamic_debug.h  |    6 +-
 include/linux/jump_label.h     |   50 +++++++++----
 include/linux/jump_label_ref.h |   26 ++++---
 include/linux/perf_event.h     |    4 +-
 include/linux/tracepoint.h     |    6 +-
 kernel/jump_label.c            |  157 +++++++++++++++++++++++++++++++++-------
 kernel/perf_event.c            |    4 +-
 kernel/tracepoint.c            |   22 ++----
 8 files changed, 196 insertions(+), 79 deletions(-)

diff --git a/include/linux/dynamic_debug.h b/include/linux/dynamic_debug.h
index a90b389..ddf7bae 100644
--- a/include/linux/dynamic_debug.h
+++ b/include/linux/dynamic_debug.h
@@ -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)));
 
 
@@ -50,7 +50,7 @@ extern int ddebug_remove_module(const char *mod_name);
 	__used								\
 	__attribute__((section("__verbose"), aligned(8))) =		\
 	{ KBUILD_MODNAME, __func__, __FILE__, fmt, __LINE__,		\
-		_DPRINTK_FLAGS_DEFAULT };				\
+		_DPRINTK_FLAGS_DEFAULT, JUMP_LABEL_INIT };		\
 	JUMP_LABEL(&descriptor.enabled, do_printk);			\
 	goto out;							\
 do_printk:								\
@@ -66,7 +66,7 @@ out:	;								\
 	__used								\
 	__attribute__((section("__verbose"), aligned(8))) =		\
 	{ KBUILD_MODNAME, __func__, __FILE__, fmt, __LINE__,		\
-		_DPRINTK_FLAGS_DEFAULT };				\
+		_DPRINTK_FLAGS_DEFAULT, JUMP_LABEL_INIT };		\
 	JUMP_LABEL(&descriptor.enabled, do_printk);			\
 	goto out;							\
 do_printk:								\
diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
index 7880f18..3e56668 100644
--- a/include/linux/jump_label.h
+++ b/include/linux/jump_label.h
@@ -2,6 +2,15 @@
 #define _LINUX_JUMP_LABEL_H
 
 #if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)
+
+struct jump_label_key {
+	void *ptr;
+};
+
+struct jump_label_keyref {
+	void *ptr;
+};
+
 # include <asm/jump_label.h>
 # define HAVE_JUMP_LABEL
 #endif
@@ -13,6 +22,8 @@ enum jump_label_type {
 
 struct module;
 
+#define JUMP_LABEL_INIT { 0 }
+
 #ifdef HAVE_JUMP_LABEL
 
 extern struct jump_entry __start___jump_table[];
@@ -23,33 +34,40 @@ 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 int jump_label_enabled(struct jump_label_key *key);
+extern void jump_label_enable(struct jump_label_key *key);
+extern void jump_label_disable(struct jump_label_key *key);
+extern void __jump_label_inc(struct jump_label_key *key);
+extern void __jump_label_dec(struct jump_label_key *key);
 
 #else
 
+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)
 
-#define jump_label_enable(cond_var)	\
-do {					\
-       *(cond_var) = 1;			\
-} while (0)
+static inline int jump_label_enabled(struct jump_label_key *key)
+{
+	return key->state;
+}
 
-#define jump_label_disable(cond_var)	\
-do {					\
-       *(cond_var) = 0;			\
-} while (0)
+static inline void jump_label_enable(struct jump_label_key *key)
+{
+	key->state = 1;
+}
+
+static inline void jump_label_disable(struct jump_label_key *key)
+{
+	key->state = 0;
+}
 
 static inline int jump_label_apply_nops(struct module *mod)
 {
diff --git a/include/linux/jump_label_ref.h b/include/linux/jump_label_ref.h
index e5d012a..2dc9ddc 100644
--- a/include/linux/jump_label_ref.h
+++ b/include/linux/jump_label_ref.h
@@ -6,36 +6,38 @@
 
 #ifdef HAVE_JUMP_LABEL
 
-static inline void jump_label_inc(atomic_t *key)
+static inline void jump_label_inc(struct jump_label_keyref *key)
 {
-	if (atomic_add_return(1, key) == 1)
-		jump_label_enable(key);
+	__jump_label_inc((struct jump_label_key *)key);
 }
 
-static inline void jump_label_dec(atomic_t *key)
+static inline void jump_label_dec(struct jump_label_keyref *key)
 {
-	if (atomic_dec_and_test(key))
-		jump_label_disable(key);
+	__jump_label_dec((struct jump_label_key *)key);
 }
 
 #else /* !HAVE_JUMP_LABEL */
 
-static inline void jump_label_inc(atomic_t *key)
+struct jump_label_keyref {
+	atomic_t refcount;
+};
+
+static inline void jump_label_inc(struct jump_label_keyref *key)
 {
-	atomic_inc(key);
+	atomic_inc(&key->refcount);
 }
 
-static inline void jump_label_dec(atomic_t *key)
+static inline void jump_label_dec(struct jump_label_keyref *key)
 {
-	atomic_dec(key);
+	atomic_dec(&key->refcount);
 }
 
 #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))))			\
+	      __builtin_types_compatible_p(typeof(key), struct jump_label_keyref *),\
+	      atomic_read(&(((struct jump_label_keyref *)key)->refcount)), (((struct jump_label_key *)key)->state))))			\
 		goto label;						\
 } while (0)
 
diff --git a/include/linux/perf_event.h b/include/linux/perf_event.h
index dda5b0a..77c4645 100644
--- a/include/linux/perf_event.h
+++ b/include/linux/perf_event.h
@@ -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_keyref perf_swevent_enabled[PERF_COUNT_SW_MAX];
 
 extern void __perf_sw_event(u32, u64, int, struct pt_regs *, u64);
 
@@ -1040,7 +1040,7 @@ have_event:
 	__perf_sw_event(event_id, nr, nmi, regs, addr);
 }
 
-extern atomic_t perf_task_events;
+extern struct jump_label_keyref perf_task_events;
 
 static inline void perf_event_task_sched_in(struct task_struct *task)
 {
diff --git a/include/linux/tracepoint.h b/include/linux/tracepoint.h
index 5a6074f..e6f9793 100644
--- a/include/linux/tracepoint.h
+++ b/include/linux/tracepoint.h
@@ -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 *funcs;
@@ -146,7 +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.state, do_trace);	\
+		JUMP_LABEL(&__tracepoint_##name.key, do_trace);		\
 		return;							\
 do_trace:								\
 			__DO_TRACE(&__tracepoint_##name,		\
@@ -175,7 +175,7 @@ do_trace:								\
 	__attribute__((section("__tracepoints_strings"))) = #name;	\
 	struct tracepoint __tracepoint_##name				\
 	__attribute__((section("__tracepoints"), aligned(32))) =	\
-		{ __tpstrtab_##name, 0, reg, unreg, NULL }
+		{ __tpstrtab_##name, JUMP_LABEL_INIT, reg, unreg, NULL }
 
 #define DEFINE_TRACE(name)						\
 	DEFINE_TRACE_FN(name, NULL, NULL);
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index 3b79bd9..f8869d6 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -26,10 +26,11 @@ 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;
+	u32 nr_entries;
+	int refcount;
 };
 
 struct jump_label_module_entry {
@@ -105,11 +106,16 @@ add_jump_label_entry(jump_label_t key, int nr_entries, struct jump_entry *table)
 
 	hash = jhash((void *)&key, sizeof(jump_label_t), 0);
 	head = &jump_label_table[hash & (JUMP_LABEL_TABLE_SIZE - 1)];
-	e->key = key;
+	e->key = (unsigned long)key;
 	e->table = table;
 	e->nr_entries = nr_entries;
+	e->refcount = 0;
 	INIT_HLIST_HEAD(&(e->modules));
 	hlist_add_head(&e->hlist, head);
+
+	/*point jump_label_key_t here */
+	((struct jump_label_key *)key)->ptr = e;
+
 	return e;
 }
 
@@ -154,37 +160,119 @@ build_jump_label_hashtable(struct jump_entry *start, struct jump_entry *stop)
  *
  */
 
-void jump_label_update(unsigned long key, enum jump_label_type type)
+static void jump_label_update(struct jump_label_entry *entry, enum jump_label_type type)
 {
 	struct jump_entry *iter;
-	struct jump_label_entry *entry;
 	struct hlist_node *module_node;
 	struct jump_label_module_entry *e_module;
 	int count;
 
-	jump_label_lock();
-	entry = get_jump_label_entry((jump_label_t)key);
-	if (entry) {
-		count = entry->nr_entries;
-		iter = entry->table;
+	count = entry->nr_entries;
+	iter = entry->table;
+	while (count--) {
+		if (kernel_text_address(iter->code))
+			arch_jump_label_transform(iter, type);
+		iter++;
+	}
+	/* enable/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 (kernel_text_address(iter->code))
+			if (iter->key && 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++;
-			}
-		}
 	}
+}
+
+static struct jump_label_entry *get_jump_label_entry_key(struct jump_label_key *key)
+{
+	struct jump_label_entry *entry;
+
+	entry = (struct jump_label_entry *)key->ptr;
+	if (!entry) {
+		entry = add_jump_label_entry((jump_label_t)key, 0, NULL);
+		if (IS_ERR(entry))
+			return NULL;
+	}
+	return entry;
+}
+
+int jump_label_enabled(struct jump_label_key *key)
+{
+	struct jump_label_entry *entry;
+	int enabled = 0;
+
+	jump_label_lock();
+	entry = get_jump_label_entry_key(key);
+	if (!entry)
+		goto out;
+	enabled = !!entry->refcount;
+out:
+	jump_label_unlock();
+	return enabled;
+}
+
+
+void jump_label_enable(struct jump_label_key *key)
+{
+	struct jump_label_entry *entry;
+
+	jump_label_lock();
+	entry = get_jump_label_entry_key(key);
+	if (!entry)
+		goto out;
+	if (!entry->refcount) {
+		jump_label_update(entry, JUMP_LABEL_ENABLE);
+		entry->refcount = 1;
+	}
+out:
+	jump_label_unlock();
+}
+
+void jump_label_disable(struct jump_label_key *key)
+{
+	struct jump_label_entry *entry;
+
+	jump_label_lock();
+	entry = get_jump_label_entry_key(key);
+	if (!entry)
+		goto out;
+	if (entry->refcount) {
+		jump_label_update(entry, JUMP_LABEL_DISABLE);
+		entry->refcount = 0;
+	}
+out:
+	jump_label_unlock();
+}
+
+void __jump_label_inc(struct jump_label_key *key)
+{
+	struct jump_label_entry *entry;
+
+	jump_label_lock();
+	entry = get_jump_label_entry_key(key);
+	if (!entry)
+		goto out;
+	if (!entry->refcount++)
+		jump_label_update(entry, JUMP_LABEL_ENABLE);
+out:
+	jump_label_unlock();
+}
+
+void __jump_label_dec(struct jump_label_key *key)
+{
+	struct jump_label_entry *entry;
+
+	jump_label_lock();
+	entry = get_jump_label_entry_key(key);
+	if (!entry)
+		goto out;
+	if (!--entry->refcount)
+		jump_label_update(entry, JUMP_LABEL_DISABLE);
+out:
 	jump_label_unlock();
 }
 
@@ -305,6 +393,7 @@ add_jump_label_module_entry(struct jump_label_entry *entry,
 			    int count, struct module *mod)
 {
 	struct jump_label_module_entry *e;
+	struct jump_entry *iter;
 
 	e = kmalloc(sizeof(struct jump_label_module_entry), GFP_KERNEL);
 	if (!e)
@@ -313,6 +402,13 @@ add_jump_label_module_entry(struct jump_label_entry *entry,
 	e->nr_entries = count;
 	e->table = iter_begin;
 	hlist_add_head(&e->hlist, &entry->modules);
+	if (entry->refcount) {
+		iter = iter_begin;
+		while (count--) {
+			arch_jump_label_transform(iter, JUMP_LABEL_ENABLE);
+			iter++;
+		}
+	}
 	return e;
 }
 
@@ -360,10 +456,6 @@ static void remove_jump_label_module(struct module *mod)
 	struct jump_label_module_entry *e_module;
 	int i;
 
-	/* if the module doesn't have jump label entries, just return */
-	if (!mod->num_jump_entries)
-		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) {
@@ -375,10 +467,21 @@ static void remove_jump_label_module(struct module *mod)
 					kfree(e_module);
 				}
 			}
+		}
+	}
+	/* now check if any keys can be removed */
+	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) {
+			if (!within_module_core(e->key, mod))
+				continue;
 			if (hlist_empty(&e->modules) && (e->nr_entries == 0)) {
 				hlist_del(&e->hlist);
 				kfree(e);
+				continue;
 			}
+			WARN(1, KERN_ERR "jump label: "
+				"tyring to remove used key: %lu !\n", e->key);
 		}
 	}
 }
@@ -470,7 +573,7 @@ void jump_label_apply_nops(struct module *mod)
 
 struct notifier_block jump_label_module_nb = {
 	.notifier_call = jump_label_module_notify,
-	.priority = 0,
+	.priority = 1, /* higher than tracepoints */
 };
 
 static __init int init_jump_label_module(void)
diff --git a/kernel/perf_event.c b/kernel/perf_event.c
index 11847bf..d8b6188 100644
--- a/kernel/perf_event.c
+++ b/kernel/perf_event.c
@@ -38,7 +38,7 @@
 
 #include <asm/irq_regs.h>
 
-atomic_t perf_task_events __read_mostly;
+struct jump_label_keyref 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;
@@ -4821,7 +4821,7 @@ fail:
 	return err;
 }
 
-atomic_t perf_swevent_enabled[PERF_COUNT_SW_MAX];
+struct jump_label_keyref perf_swevent_enabled[PERF_COUNT_SW_MAX];
 
 static void sw_perf_event_destroy(struct perf_event *event)
 {
diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c
index e95ee7f..d54b434 100644
--- a/kernel/tracepoint.c
+++ b/kernel/tracepoint.c
@@ -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);
 }
 
-- 
1.7.1

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Peter Zijlstra]

On Thu, 2010-12-16 at 13:25 -0500, Jason Baron wrote:
> Previously, I allowed any variable type to be used as the 'key' for
> the jump label. However, by enforcing a type, we can make use of the
> contents of the 'key'. This patch thus introduces:
> 
> struct jump_label_key {
>        void *ptr;
> };
> 
> The 'ptr' is used a pointer into the jump label table of the
> corresponding addresses that need to be updated. Thus, when jump labels
> are enabled/disabled we have a constant time algorithm. There is no
> longer any hashing.
> 
> When jump lables are disabled we simply have:
> 
> struct jump_label_key {
>         int state;
> };
> 
> I've also defined an analogous structure for ref counted jump labels as
> per a request from Peter.
> 
> struct jump_label_keyref {
>        void *ptr;
> };
> 
> And for the jump labels disabled case:
> 
> 
> struct jump_label_keyref {
>         atomic_t refcount;
> };
> 
> The reason I've introduced an additional structure for the reference counted
> jump labels is twofold:
> 
> 1) For the jump labels disabled case, reference counted jump labels use an
> atomic_read(). I didn't want to impact the jump labels disabled case for
> tracepoints which simply accesses an 'int'.
> 
> 2) By introducing a second type, we have two parallel APIs:
> 
> extern void jump_label_enable(struct jump_label_key *key);
> extern void jump_label_disable(struct jump_label_key *key);
> 
> static inline void jump_label_inc(struct jump_label_keyref *key)
> static inline void jump_label_dec(struct jump_label_keyref *key)
> 
> In this way, we can't mix up the reference counted API, with the straight
> enable/disable API since they accept different types.

But why do we want to have two APIs?

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Jason Baron]

On Thu, Dec 16, 2010 at 08:10:02PM +0100, Peter Zijlstra wrote:
> On Thu, 2010-12-16 at 13:25 -0500, Jason Baron wrote:
> > Previously, I allowed any variable type to be used as the 'key' for
> > the jump label. However, by enforcing a type, we can make use of the
> > contents of the 'key'. This patch thus introduces:
> > 
> > struct jump_label_key {
> >        void *ptr;
> > };
> > 
> > The 'ptr' is used a pointer into the jump label table of the
> > corresponding addresses that need to be updated. Thus, when jump labels
> > are enabled/disabled we have a constant time algorithm. There is no
> > longer any hashing.
> > 
> > When jump lables are disabled we simply have:
> > 
> > struct jump_label_key {
> >         int state;
> > };
> > 
> > I've also defined an analogous structure for ref counted jump labels as
> > per a request from Peter.
> > 
> > struct jump_label_keyref {
> >        void *ptr;
> > };
> > 
> > And for the jump labels disabled case:
> > 
> > 
> > struct jump_label_keyref {
> >         atomic_t refcount;
> > };
> > 
> > The reason I've introduced an additional structure for the reference counted
> > jump labels is twofold:
> > 
> > 1) For the jump labels disabled case, reference counted jump labels use an
> > atomic_read(). I didn't want to impact the jump labels disabled case for
> > tracepoints which simply accesses an 'int'.
> > 
> > 2) By introducing a second type, we have two parallel APIs:
> > 
> > extern void jump_label_enable(struct jump_label_key *key);
> > extern void jump_label_disable(struct jump_label_key *key);
> > 
> > static inline void jump_label_inc(struct jump_label_keyref *key)
> > static inline void jump_label_dec(struct jump_label_keyref *key)
> > 
> > In this way, we can't mix up the reference counted API, with the straight
> > enable/disable API since they accept different types.
> 
> But why do we want to have two APIs?

its not 2 APIS doing the same thing...one does refcounting, the other is
a straight enable/disable.

For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
to check if enabled. While other consumers (tracepoints) are just using an
'int'. I didn't want hurt the jump label disabled case for tracepoints.
If we can agree to use atomic ops for tracepoints, or drop atomics from
perf, that would simplify things.

For the jump albel enabled case, there is no issue.

thanks,

-Jason

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Peter Zijlstra]

On Thu, 2010-12-16 at 14:23 -0500, Jason Baron wrote:
> 
> For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
> to check if enabled. While other consumers (tracepoints) are just using an
> 'int'. I didn't want hurt the jump label disabled case for tracepoints.
> If we can agree to use atomic ops for tracepoints, or drop atomics from
> perf, that would simplify things. 

I had a quick look at the tracepoint stuff but got lost, but surely it
has a reference count somewhere as well, it needs to know when the last
probe goes away.. or does it check if the list is empty?

Anyway, tracepoint enable/disable isn't a real fast-path, surely it
could suffer an atomic op?

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Jason Baron]

On Thu, Dec 16, 2010 at 08:33:51PM +0100, Peter Zijlstra wrote:
> On Thu, 2010-12-16 at 14:23 -0500, Jason Baron wrote:
> > 
> > For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
> > to check if enabled. While other consumers (tracepoints) are just using an
> > 'int'. I didn't want hurt the jump label disabled case for tracepoints.
> > If we can agree to use atomic ops for tracepoints, or drop atomics from
> > perf, that would simplify things. 
> 
> I had a quick look at the tracepoint stuff but got lost, but surely it
> has a reference count somewhere as well, it needs to know when the last
> probe goes away.. or does it check if the list is empty?
> 
> Anyway, tracepoint enable/disable isn't a real fast-path, surely it
> could suffer an atomic op?

It is the atomic_read() at the tracepoint site that I am concerned
about.

thanks,

-Jason

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Peter Zijlstra]

On Thu, 2010-12-16 at 14:36 -0500, Jason Baron wrote:
> On Thu, Dec 16, 2010 at 08:33:51PM +0100, Peter Zijlstra wrote:
> > On Thu, 2010-12-16 at 14:23 -0500, Jason Baron wrote:
> > > 
> > > For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
> > > to check if enabled. While other consumers (tracepoints) are just using an
> > > 'int'. I didn't want hurt the jump label disabled case for tracepoints.
> > > If we can agree to use atomic ops for tracepoints, or drop atomics from
> > > perf, that would simplify things. 
> > 
> > I had a quick look at the tracepoint stuff but got lost, but surely it
> > has a reference count somewhere as well, it needs to know when the last
> > probe goes away.. or does it check if the list is empty?
> > 
> > Anyway, tracepoint enable/disable isn't a real fast-path, surely it
> > could suffer an atomic op?
> 
> It is the atomic_read() at the tracepoint site that I am concerned
> about.

Look at the implementation :-), its just wrapper foo, its a regular read
for everything except some really weird archs (you really shouldn't care
about).

static inline int atomic_read(const atomic_t *v)
{
        return (*(volatile int *)&(v)->counter);
}

The volatile simply forces a load to be emitted.

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Jason Baron]

On Thu, Dec 16, 2010 at 08:41:41PM +0100, Peter Zijlstra wrote:
> On Thu, 2010-12-16 at 14:36 -0500, Jason Baron wrote:
> > On Thu, Dec 16, 2010 at 08:33:51PM +0100, Peter Zijlstra wrote:
> > > On Thu, 2010-12-16 at 14:23 -0500, Jason Baron wrote:
> > > > 
> > > > For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
> > > > to check if enabled. While other consumers (tracepoints) are just using an
> > > > 'int'. I didn't want hurt the jump label disabled case for tracepoints.
> > > > If we can agree to use atomic ops for tracepoints, or drop atomics from
> > > > perf, that would simplify things. 
> > > 
> > > I had a quick look at the tracepoint stuff but got lost, but surely it
> > > has a reference count somewhere as well, it needs to know when the last
> > > probe goes away.. or does it check if the list is empty?
> > > 
> > > Anyway, tracepoint enable/disable isn't a real fast-path, surely it
> > > could suffer an atomic op?
> > 
> > It is the atomic_read() at the tracepoint site that I am concerned
> > about.
> 
> Look at the implementation :-), its just wrapper foo, its a regular read

i did.

> for everything except some really weird archs (you really shouldn't care
> about).

right, I wasn't sure how much those mattered.

> 
> static inline int atomic_read(const atomic_t *v)
> {
>         return (*(volatile int *)&(v)->counter);
> }
> 
> The volatile simply forces a load to be emitted.

Mathieu, what do you think? Are you ok with an atomic_read() for
checking if a tracepoint is enabled, when jump labels are disabled?

thanks,

-Jason

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Steven Rostedt]

On Thu, 2010-12-16 at 14:48 -0500, Jason Baron wrote:
>  
> > static inline int atomic_read(const atomic_t *v)
> > {
> >         return (*(volatile int *)&(v)->counter);
> > }
> > 
> > The volatile simply forces a load to be emitted.
> 
> Mathieu, what do you think? Are you ok with an atomic_read() for
> checking if a tracepoint is enabled, when jump labels are disabled?

Note, I'm fine with this method too. An atomic_read() is extremely fast.
The worse that it does is to prevent gcc from optimizing a little, which
we already cause it to do due to the asm goto that we use.

-- Steve

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Mathieu Desnoyers]

* Jason Baron (jbaron@redhat.com) wrote:
> On Thu, Dec 16, 2010 at 08:41:41PM +0100, Peter Zijlstra wrote:
> > On Thu, 2010-12-16 at 14:36 -0500, Jason Baron wrote:
> > > On Thu, Dec 16, 2010 at 08:33:51PM +0100, Peter Zijlstra wrote:
> > > > On Thu, 2010-12-16 at 14:23 -0500, Jason Baron wrote:
> > > > > 
> > > > > For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
> > > > > to check if enabled. While other consumers (tracepoints) are just using an
> > > > > 'int'. I didn't want hurt the jump label disabled case for tracepoints.
> > > > > If we can agree to use atomic ops for tracepoints, or drop atomics from
> > > > > perf, that would simplify things. 
> > > > 
> > > > I had a quick look at the tracepoint stuff but got lost, but surely it
> > > > has a reference count somewhere as well, it needs to know when the last
> > > > probe goes away.. or does it check if the list is empty?
> > > > 
> > > > Anyway, tracepoint enable/disable isn't a real fast-path, surely it
> > > > could suffer an atomic op?
> > > 
> > > It is the atomic_read() at the tracepoint site that I am concerned
> > > about.
> > 
> > Look at the implementation :-), its just wrapper foo, its a regular read
> 
> i did.
> 
> > for everything except some really weird archs (you really shouldn't care
> > about).
> 
> right, I wasn't sure how much those mattered.
> 
> > 
> > static inline int atomic_read(const atomic_t *v)
> > {
> >         return (*(volatile int *)&(v)->counter);
> > }
> > 
> > The volatile simply forces a load to be emitted.
> 
> Mathieu, what do you think? Are you ok with an atomic_read() for
> checking if a tracepoint is enabled, when jump labels are disabled?

volatiles are also ordered one with respect to another by the compiler,
so I'd like to avoid doing the volatile read on the fast path unless
utterly necessary for architectures not supporting static jump patching
yet.

Tracepoints keep their own reference counts for enable/disable, so a
simple "enable/disable" is fine as far as tracepoints are concerned. Why
does perf need that refcounting done by the static jumps ?

I'd be tempted to use a "char" instead of a int/atomic_t for the key,
and keep the reference counter out of the picture (and leave that to the
caller). A single byte can be updated and read atomically. This should
save memory for the jump label tables.

Thoughts ?

Thanks,

Mathieu

> 
> thanks,
> 
> -Jason

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

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Peter Zijlstra]

On Thu, 2010-12-16 at 15:36 -0500, Mathieu Desnoyers wrote:
> Tracepoints keep their own reference counts for enable/disable, so a
> simple "enable/disable" is fine as far as tracepoints are concerned. Why
> does perf need that refcounting done by the static jumps ?

Because the refcount is all we have... Why not replace that tracepoint
refcount with the jumplabel thing?

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Mathieu Desnoyers]

* Peter Zijlstra (peterz@infradead.org) wrote:
> On Thu, 2010-12-16 at 15:36 -0500, Mathieu Desnoyers wrote:
> > Tracepoints keep their own reference counts for enable/disable, so a
> > simple "enable/disable" is fine as far as tracepoints are concerned. Why
> > does perf need that refcounting done by the static jumps ?
> 
> Because the refcount is all we have... Why not replace that tracepoint
> refcount with the jumplabel thing?

The reason why tracepoints need to keep their own refcount is because
they support dynamically loadable modules, and hence the refcount must
be kept outside of the modules, in a table internal to tracepoints,
so we can attach a probe to a yet unloaded module. Therefore, relying on
this lower level jump label to keep the refcount is not appropriate for
tracepoints, because the refcount only exists when the module is live.

I know that your point of view is "let users of modules suffer", but
this represents a very large portion of Linux users I am not willing to
let suffer knowingly.

Thanks,

Mathieu

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

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Peter Zijlstra]

On Thu, 2010-12-16 at 15:50 -0500, Mathieu Desnoyers wrote:
> * Peter Zijlstra (peterz@infradead.org) wrote:
> > On Thu, 2010-12-16 at 15:36 -0500, Mathieu Desnoyers wrote:
> > > Tracepoints keep their own reference counts for enable/disable, so a
> > > simple "enable/disable" is fine as far as tracepoints are concerned. Why
> > > does perf need that refcounting done by the static jumps ?
> > 
> > Because the refcount is all we have... Why not replace that tracepoint
> > refcount with the jumplabel thing?
> 
> The reason why tracepoints need to keep their own refcount is because
> they support dynamically loadable modules, and hence the refcount must
> be kept outside of the modules, in a table internal to tracepoints,
> so we can attach a probe to a yet unloaded module. Therefore, relying on
> this lower level jump label to keep the refcount is not appropriate for
> tracepoints, because the refcount only exists when the module is live.

That's not a logical conclusion, you can keep these jump_label keys
outside of the module just fine.

> I know that your point of view is "let users of modules suffer", but
> this represents a very large portion of Linux users I am not willing to
> let suffer knowingly.

Feh, I'd argue to remove this special tracepoint crap, the only
in-kernel user (ftrace) doesn't even make use of it. This weird ass
tracepoint semantic being different from the ftrace trace_event
semantics has caused trouble before.

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Jason Baron]

On Thu, Dec 16, 2010 at 09:56:25PM +0100, Peter Zijlstra wrote:
> On Thu, 2010-12-16 at 15:50 -0500, Mathieu Desnoyers wrote:
> > * Peter Zijlstra (peterz@infradead.org) wrote:
> > > On Thu, 2010-12-16 at 15:36 -0500, Mathieu Desnoyers wrote:
> > > > Tracepoints keep their own reference counts for enable/disable, so a
> > > > simple "enable/disable" is fine as far as tracepoints are concerned. Why
> > > > does perf need that refcounting done by the static jumps ?
> > > 
> > > Because the refcount is all we have... Why not replace that tracepoint
> > > refcount with the jumplabel thing?
> > 
> > The reason why tracepoints need to keep their own refcount is because
> > they support dynamically loadable modules, and hence the refcount must
> > be kept outside of the modules, in a table internal to tracepoints,
> > so we can attach a probe to a yet unloaded module. Therefore, relying on
> > this lower level jump label to keep the refcount is not appropriate for
> > tracepoints, because the refcount only exists when the module is live.
> 
> That's not a logical conclusion, you can keep these jump_label keys
> outside of the module just fine.
> 
> > I know that your point of view is "let users of modules suffer", but
> > this represents a very large portion of Linux users I am not willing to
> > let suffer knowingly.
> 
> Feh, I'd argue to remove this special tracepoint crap, the only
> in-kernel user (ftrace) doesn't even make use of it. This weird ass
> tracepoint semantic being different from the ftrace trace_event
> semantics has caused trouble before.
> 
> 

Hi,

since atomic_t is just an 'int' from include/linux/types.h, so for all
arches. We can cast any refernces to an atomic_t in
include/linux/jump_label_ref.h

So for when jump labels are disabled case we could have
one struct:

struct jump_label_key {
	int state;
}

and then we could then have (rough c code):

jump_label_enable(struct jump_label_key *key)
{
	key->state = 1;
}

jump_label_disable(struct jump_label_key *key)
{
	key->state = 0;
}

jump_label_inc(struct jump_label_key *key)
{
	atomic_inc((atomic_t *)key)
}

jump_label_dec(struct jump_label_key *key)
{
	atomic_dec((atomic_t *)key)
}

bool unlikely_switch(struct jump_label_key *key)
{
	if (key->state)
		return true;
	return false;
}

bool unlikely_switch_atomic(struct jump_label_key *key)
{
	if (atomic_read((atomic_t *)key)
		return true;
	return false;
}

can we agree on something like this?

thanks,

-Jason	

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[David Daney]

On 12/17/2010 12:07 PM, Jason Baron wrote:
> On Thu, Dec 16, 2010 at 09:56:25PM +0100, Peter Zijlstra wrote:
>> On Thu, 2010-12-16 at 15:50 -0500, Mathieu Desnoyers wrote:
>>> * Peter Zijlstra (peterz@infradead.org) wrote:
>>>> On Thu, 2010-12-16 at 15:36 -0500, Mathieu Desnoyers wrote:
>>>>> Tracepoints keep their own reference counts for enable/disable, so a
>>>>> simple "enable/disable" is fine as far as tracepoints are concerned. Why
>>>>> does perf need that refcounting done by the static jumps ?
>>>>
>>>> Because the refcount is all we have... Why not replace that tracepoint
>>>> refcount with the jumplabel thing?
>>>
>>> The reason why tracepoints need to keep their own refcount is because
>>> they support dynamically loadable modules, and hence the refcount must
>>> be kept outside of the modules, in a table internal to tracepoints,
>>> so we can attach a probe to a yet unloaded module. Therefore, relying on
>>> this lower level jump label to keep the refcount is not appropriate for
>>> tracepoints, because the refcount only exists when the module is live.
>>
>> That's not a logical conclusion, you can keep these jump_label keys
>> outside of the module just fine.
>>
>>> I know that your point of view is "let users of modules suffer", but
>>> this represents a very large portion of Linux users I am not willing to
>>> let suffer knowingly.
>>
>> Feh, I'd argue to remove this special tracepoint crap, the only
>> in-kernel user (ftrace) doesn't even make use of it. This weird ass
>> tracepoint semantic being different from the ftrace trace_event
>> semantics has caused trouble before.
>>
>>
>
> Hi,
>
> since atomic_t is just an 'int' from include/linux/types.h, so for all
> arches. We can cast any refernces to an atomic_t in
> include/linux/jump_label_ref.h
>

Not acceptable I would think.

How about:

union fubar {
    int key_as_non_atomic;
    atomic_t key_as_atomic;
};

Now explain the exact semantics of this thing including how you 
guarantee no conflicting accesses *ever* occur.


> So for when jump labels are disabled case we could have
> one struct:
>
> struct jump_label_key {
> 	int state;
> }
>
> and then we could then have (rough c code):
>
> jump_label_enable(struct jump_label_key *key)
> {
> 	key->state = 1;
> }
>
> jump_label_disable(struct jump_label_key *key)
> {
> 	key->state = 0;
> }
>
> jump_label_inc(struct jump_label_key *key)
> {
> 	atomic_inc((atomic_t *)key)
> }
>
> jump_label_dec(struct jump_label_key *key)
> {
> 	atomic_dec((atomic_t *)key)
> }
>
> bool unlikely_switch(struct jump_label_key *key)
> {
> 	if (key->state)
> 		return true;
> 	return false;
> }
>
> bool unlikely_switch_atomic(struct jump_label_key *key)
> {
> 	if (atomic_read((atomic_t *)key)
> 		return true;
> 	return false;
> }
>
> can we agree on something like this?

I get a sick feeling whenever casting is used to give types with well 
defined semantics (atomic_t) poorly defined semantics (your usage).

David Daney

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Steven Rostedt]

On Fri, 2010-12-17 at 12:51 -0800, David Daney wrote:
> On 12/17/2010 12:07 PM, Jason Baron wrote:

> Not acceptable I would think.
> 
> How about:
> 
> union fubar {
>     int key_as_non_atomic;
>     atomic_t key_as_atomic;
> };

I don't even like this union.

> 
> Now explain the exact semantics of this thing including how you 
> guarantee no conflicting accesses *ever* occur.

I don't like the mixed semantics at all.

> 
> 
> > So for when jump labels are disabled case we could have
> > one struct:
> >
> > struct jump_label_key {

	atomic_t state;

> > }
> >
> > and then we could then have (rough c code):
> >
> > jump_label_enable(struct jump_label_key *key)
> > {

	if (atomic_read(&key->state))
		return;
	atomic_inc(&key->state);

> > }
> >
> > jump_label_disable(struct jump_label_key *key)
> > {

	if (!atomic_read(&key->state))
		return;
	atomic_dec(&key->state);
	WARN_ON(atomic_read(&key->state);

> > }
> >
> > jump_label_inc(struct jump_label_key *key)
> > {

 	atomic_inc(&key->state)

> > }
> >
> > jump_label_dec(struct jump_label_key *key)
> > {

 	atomic_dec((&key->state)

> > }
> >
> > bool unlikely_switch(struct jump_label_key *key)
> > {

 	if (atomic_read(&key->state))

> > 		return true;
> > 	return false;
> > }
> >

There, now you are guaranteed that you have proper semantics.

> >
> > can we agree on something like this?
> 
> I get a sick feeling whenever casting is used to give types with well 
> defined semantics (atomic_t) poorly defined semantics (your usage).

Exactly, I like to avoid (void*) anything or even worse, casting one
type to another for some strange semantics. This is guaranteed nightmare
of maintenance.

-- Steve

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Jason Baron]

On Fri, Dec 17, 2010 at 04:12:21PM -0500, Steven Rostedt wrote:
> > On 12/17/2010 12:07 PM, Jason Baron wrote:
> 
> > Not acceptable I would think.
> > 
> > How about:
> > 
> > union fubar {
> >     int key_as_non_atomic;
> >     atomic_t key_as_atomic;
> > };
> 
> I don't even like this union.
> 
> > 
> > Now explain the exact semantics of this thing including how you 
> > guarantee no conflicting accesses *ever* occur.
> 
> I don't like the mixed semantics at all.
> 
> > 
> > 
> > > So for when jump labels are disabled case we could have
> > > one struct:
> > >
> > > struct jump_label_key {
> 
> 	atomic_t state;
> 
> > > }
> > >
> > > and then we could then have (rough c code):
> > >
> > > jump_label_enable(struct jump_label_key *key)
> > > {
> 
> 	if (atomic_read(&key->state))
> 		return;
> 	atomic_inc(&key->state);
> 
> > > }
> > >
> > > jump_label_disable(struct jump_label_key *key)
> > > {
> 
> 	if (!atomic_read(&key->state))
> 		return;
> 	atomic_dec(&key->state);
> 	WARN_ON(atomic_read(&key->state);
> 
> > > }
> > >
> > > jump_label_inc(struct jump_label_key *key)
> > > {
> 
>  	atomic_inc(&key->state)
> 
> > > }
> > >
> > > jump_label_dec(struct jump_label_key *key)
> > > {
> 
>  	atomic_dec((&key->state)
> 
> > > }
> > >
> > > bool unlikely_switch(struct jump_label_key *key)
> > > {
> 
>  	if (atomic_read(&key->state))
> 
> > > 		return true;
> > > 	return false;
> > > }
> > >
> 

hmmm...we were trying to avoid having the atomic_read() for tracepoints
b/c of potential extra cost that Mathieu was concerned about.

> There, now you are guaranteed that you have proper semantics.
> 
> > >

The other issue here was that jump_label.h gets included by
asm/atomic.h, so there a dependency issue to be addressed here as
well....

thanks,

-Jason

Re: [PATCH/RFC 1/2] jump label: make enable/disable o(1)

[Mathieu Desnoyers]

* Jason Baron (jbaron@redhat.com) wrote:
> On Thu, Dec 16, 2010 at 08:41:41PM +0100, Peter Zijlstra wrote:
> > On Thu, 2010-12-16 at 14:36 -0500, Jason Baron wrote:
> > > On Thu, Dec 16, 2010 at 08:33:51PM +0100, Peter Zijlstra wrote:
> > > > On Thu, 2010-12-16 at 14:23 -0500, Jason Baron wrote:
> > > > > 
> > > > > For the jump label disabled case, perf is using atomic_inc/dec and atomic_read
> > > > > to check if enabled. While other consumers (tracepoints) are just using an
> > > > > 'int'. I didn't want hurt the jump label disabled case for tracepoints.
> > > > > If we can agree to use atomic ops for tracepoints, or drop atomics from
> > > > > perf, that would simplify things. 
> > > > 
> > > > I had a quick look at the tracepoint stuff but got lost, but surely it
> > > > has a reference count somewhere as well, it needs to know when the last
> > > > probe goes away.. or does it check if the list is empty?
> > > > 
> > > > Anyway, tracepoint enable/disable isn't a real fast-path, surely it
> > > > could suffer an atomic op?
> > > 
> > > It is the atomic_read() at the tracepoint site that I am concerned
> > > about.
> > 
> > Look at the implementation :-), its just wrapper foo, its a regular read
> 
> i did.
> 
> > for everything except some really weird archs (you really shouldn't care
> > about).
> 
> right, I wasn't sure how much those mattered.
> 
> > 
> > static inline int atomic_read(const atomic_t *v)
> > {
> >         return (*(volatile int *)&(v)->counter);
> > }
> > 
> > The volatile simply forces a load to be emitted.
> 
> Mathieu, what do you think? Are you ok with an atomic_read() for
> checking if a tracepoint is enabled, when jump labels are disabled?

[Steven:]

Note, I'm fine with this method too. An atomic_read() is extremely fast.
The worse that it does is to prevent gcc from optimizing a little, which
we already cause it to do due to the asm goto that we use.

[my reply to Steven]

How does the asm goto we use prohibit the compiler from moving code in
any way more than an standard branch ? It's not an "asm volatile goto",
just an asm goto.

Thanks,

Mathieu


> 
> thanks,
> 
> -Jason

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

[PATCH/RFC 2/2] jump label: introduce unlikely_switch()

[Jason Baron]

Introduce:

static __always_inline bool unlikely_switch(struct jump_label_key *key);

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

The new unlikely_switch(), simplifies the usage of jump labels. Since
unlikely_switch() 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():

--- a/include/linux/tracepoint.h
+++ b/include/linux/tracepoint.h
@@ -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 (unlikely_switch(&__tracepoint_##name.key))		\
 			__DO_TRACE(&__tracepoint_##name,		\
 				TP_PROTO(data_proto),			\
 				TP_ARGS(data_args));			\


The name 'unlikely_switch' is meant to invoke the notion of 'unlikely', in that
we expect this code path to be disabled most of the time. The 'switch' notion is
that we really have a switch here that can be flipped, by patching either a
'nop' or a 'jmp' at the switchpoint.

I analyzed the code produced by unlikely_switch(), 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 in the -02 case.

Thanks to H. Peter Anvin for suggesting this improved syntax as well as
the name 'switchpoint'.

Suggested-by: H. Peter Anvin <hpa@linux.intel.com>
Signed-off-by: Jason Baron <jbaron@redhat.com>
---
 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    |   19 +++++++++++--------
 include/linux/perf_event.h        |   21 ++++++++++-----------
 include/linux/tracepoint.h        |    4 +---
 kernel/jump_label.c               |    2 +-
 8 files changed, 52 insertions(+), 62 deletions(-)

diff --git a/arch/x86/include/asm/jump_label.h b/arch/x86/include/asm/jump_label.h
index f52d42e..172af9b 100644
--- a/arch/x86/include/asm/jump_label.h
+++ b/arch/x86/include/asm/jump_label.h
@@ -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,  \"a\" \n\t"\
-			_ASM_PTR "1b, %l[" #label "], %c0 \n\t" \
-			".popsection \n\t"			\
-			: :  "i" (key) :  : label);		\
-	} while (0)
+static __always_inline bool __unlikely_switch(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__ */
 
diff --git a/arch/x86/kernel/jump_label.c b/arch/x86/kernel/jump_label.c
index 961b6b3..dfa4c3c 100644
--- a/arch/x86/kernel/jump_label.c
+++ b/arch/x86/kernel/jump_label.c
@@ -4,13 +4,13 @@
  * Copyright (C) 2009 Jason Baron <jbaron@redhat.com>
  *
  */
-#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>
 
diff --git a/include/linux/dynamic_debug.h b/include/linux/dynamic_debug.h
index ddf7bae..71d18a8 100644
--- a/include/linux/dynamic_debug.h
+++ b/include/linux/dynamic_debug.h
@@ -44,34 +44,24 @@ int ddebug_add_module(struct _ddebug *tab, unsigned int n,
 extern int ddebug_remove_module(const char *mod_name);
 
 #define dynamic_pr_debug(fmt, ...) do {					\
-	__label__ do_printk;						\
-	__label__ out;							\
 	static struct _ddebug descriptor				\
 	__used								\
 	__attribute__((section("__verbose"), aligned(8))) =		\
 	{ KBUILD_MODNAME, __func__, __FILE__, fmt, __LINE__,		\
 		_DPRINTK_FLAGS_DEFAULT, JUMP_LABEL_INIT };		\
-	JUMP_LABEL(&descriptor.enabled, do_printk);			\
-	goto out;							\
-do_printk:								\
-	printk(KERN_DEBUG pr_fmt(fmt),	##__VA_ARGS__);			\
-out:	;								\
+	if (unlikely_switch(&descriptor.enabled))			\
+		printk(KERN_DEBUG pr_fmt(fmt),	##__VA_ARGS__);		\
 	} while (0)
 
 
 #define dynamic_dev_dbg(dev, fmt, ...) do {				\
-	__label__ do_printk;						\
-	__label__ out;							\
 	static struct _ddebug descriptor				\
 	__used								\
 	__attribute__((section("__verbose"), aligned(8))) =		\
 	{ KBUILD_MODNAME, __func__, __FILE__, fmt, __LINE__,		\
 		_DPRINTK_FLAGS_DEFAULT, JUMP_LABEL_INIT };		\
-	JUMP_LABEL(&descriptor.enabled, do_printk);			\
-	goto out;							\
-do_printk:								\
-	dev_printk(KERN_DEBUG, dev, fmt, ##__VA_ARGS__);		\
-out:	;								\
+	if (unlikely_switch(&descriptor.enabled))			\
+		dev_printk(KERN_DEBUG, dev, fmt, ##__VA_ARGS__);	\
 	} while (0)
 
 #else
diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
index 3e56668..5da64b7 100644
--- a/include/linux/jump_label.h
+++ b/include/linux/jump_label.h
@@ -26,6 +26,11 @@ struct module;
 
 #ifdef HAVE_JUMP_LABEL
 
+static __always_inline bool unlikely_switch(struct jump_label_key *key)
+{
+	return __unlikely_switch(key);
+}
+
 extern struct jump_entry __start___jump_table[];
 extern struct jump_entry __stop___jump_table[];
 
@@ -48,11 +53,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 unlikely_switch(struct jump_label_key *key)
+{
+	if (unlikely(key->state))
+		return true;
+	return false;
+}
 
 static inline int jump_label_enabled(struct jump_label_key *key)
 {
@@ -84,14 +90,4 @@ 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)
-
 #endif
diff --git a/include/linux/jump_label_ref.h b/include/linux/jump_label_ref.h
index 2dc9ddc..c1ae838 100644
--- a/include/linux/jump_label_ref.h
+++ b/include/linux/jump_label_ref.h
@@ -16,6 +16,11 @@ static inline void jump_label_dec(struct jump_label_keyref *key)
 	__jump_label_dec((struct jump_label_key *)key);
 }
 
+static __always_inline bool unlikely_switch_refcount(struct jump_label_keyref *key)
+{
+	return __unlikely_switch((struct jump_label_key *)key);
+}
+
 #else /* !HAVE_JUMP_LABEL */
 
 struct jump_label_keyref {
@@ -32,14 +37,12 @@ static inline void jump_label_dec(struct jump_label_keyref *key)
 	atomic_dec(&key->refcount);
 }
 
-#undef JUMP_LABEL
-#define JUMP_LABEL(key, label)						\
-do {									\
-	if (unlikely(__builtin_choose_expr(				\
-	      __builtin_types_compatible_p(typeof(key), struct jump_label_keyref *),\
-	      atomic_read(&(((struct jump_label_keyref *)key)->refcount)), (((struct jump_label_key *)key)->state))))			\
-		goto label;						\
-} while (0)
+static __always_inline bool unlikely_switch_refcount(struct jump_label_keyref *key)
+{
+	if (unlikely(atomic_read(&key->refcount)))
+		return true;
+	return false;
+}
 
 #endif /* HAVE_JUMP_LABEL */
 
diff --git a/include/linux/perf_event.h b/include/linux/perf_event.h
index 77c4645..142e9b2 100644
--- a/include/linux/perf_event.h
+++ b/include/linux/perf_event.h
@@ -1029,30 +1029,29 @@ 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 (unlikely_switch_refcount(&perf_swevent_enabled[event_id])) {
+		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 struct jump_label_keyref 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 (unlikely_switch_refcount(&perf_task_events))
+		__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 (unlikely_switch_refcount(&perf_task_events))
+		__perf_event_task_sched_out(task, next);
 }
 
 extern void perf_event_mmap(struct vm_area_struct *vma);
diff --git a/include/linux/tracepoint.h b/include/linux/tracepoint.h
index e6f9793..f1bcc5e 100644
--- a/include/linux/tracepoint.h
+++ b/include/linux/tracepoint.h
@@ -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 (unlikely_switch(&__tracepoint_##name.key))		\
 			__DO_TRACE(&__tracepoint_##name,		\
 				TP_PROTO(data_proto),			\
 				TP_ARGS(data_args));			\
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index f8869d6..0c9f4d5 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -4,7 +4,6 @@
  * Copyright (C) 2009 Jason Baron <jbaron@redhat.com>
  *
  */
-#include <linux/jump_label.h>
 #include <linux/memory.h>
 #include <linux/uaccess.h>
 #include <linux/module.h>
@@ -13,6 +12,7 @@
 #include <linux/slab.h>
 #include <linux/sort.h>
 #include <linux/err.h>
+#include <linux/jump_label.h>
 
 #ifdef HAVE_JUMP_LABEL
 
-- 
1.7.1

Re: [PATCH/RFC 0/2] jump label: simplify API

[Mathieu Desnoyers]

* Jason Baron (jbaron@redhat.com) wrote:
> 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 unlikely_switch(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 (unlikely_switch(&jump_key))
> 		do unlikely code

Ah, yes, that's an improvement!

I'm just wondering about the terminology here. Isn't that more a
"branch" than a "switch" ?

I'm concerned about the fact that if we ever want to use the asm goto
ability to jump to multiple targets (which is closer to a statically
computed switch than a branch), we might want to reserve "switch" name
for that rather than the branch.

I wonder if the "if (unlikely_switch(&jump_key))" you propose above is
the right thing to do. Why does the unlikely_ have to be included in the
name ? Maybe there is a good reason for it, but it would be nice to have
it spelled out. We might consider:

if (unlikely(static_branch(&jump_key)))
  ...

instead.

For the switch statement, from the top of my head the idea would be to
get something close to the following:

static __always_inline
int static_switch_{3,4,5,6...}(struct jump_label_key *key);

e.g.:

static __always_inline
int static_switch_3(struct jump_label_key *key)
{
	asm goto("1:"
		JUMP_LABEL_INITIAL_NOP
		".pushsection __switch_table_3,  \"a\" \n\t"
		_ASM_PTR "%c0, 1b, %l[l_1], %l[l_2] \n\t"
		".popsection \n\t"
		: :  "i" (key) : : l_1, l_2 );
	return 0;
l_1:
	return 1;
l_2:
	return 2;
}

switch(static_switch_3(&switch_key)) {
	case 0: .....
		break;
	case 1: .....
		break;
	case 2: .....
		break;
}

(I have not tried to give that to gcc 4.5.x to see how the resulting
assembly looks like. It would be interesting to see if it handles this
case well)

Thoughts ?

Thanks,

Mathieu

> 
> enable/disale via:
> 
> 	jump_label_enable(&jump_key);
> 	jump_label_disable(&jump_key);
> 
> that's it!
> 
> Thanks to H. Peter Anvin for suggesting the simpler 'unlikely_switch()'
> function.
> 
> thanks,
> 
> -Jason
> 
> 
> Jason Baron (2):
>   jump label: make enable/disable o(1)
>   jump label: introduce unlikely_switch()
> 
>  arch/x86/include/asm/jump_label.h |   22 +++--
>  arch/x86/kernel/jump_label.c      |    2 +-
>  include/linux/dynamic_debug.h     |   24 ++----
>  include/linux/jump_label.h        |   72 ++++++++++-------
>  include/linux/jump_label_ref.h    |   41 ++++++----
>  include/linux/perf_event.h        |   25 +++---
>  include/linux/tracepoint.h        |    8 +-
>  kernel/jump_label.c               |  159 ++++++++++++++++++++++++++++++-------
>  kernel/perf_event.c               |    4 +-
>  kernel/tracepoint.c               |   22 ++---
>  10 files changed, 243 insertions(+), 136 deletions(-)
> 

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

Re: [PATCH/RFC 0/2] jump label: simplify API

[Steven Rostedt]

On Thu, 2010-12-16 at 14:22 -0500, Mathieu Desnoyers wrote:
> * Jason Baron (jbaron@redhat.com) wrote:
> > 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 unlikely_switch(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 (unlikely_switch(&jump_key))
> > 		do unlikely code
> 
> Ah, yes, that's an improvement!
> 
> I'm just wondering about the terminology here. Isn't that more a
> "branch" than a "switch" ?
> 
> I'm concerned about the fact that if we ever want to use the asm goto
> ability to jump to multiple targets (which is closer to a statically
> computed switch than a branch), we might want to reserve "switch" name
> for that rather than the branch.

Good point.

> 
> I wonder if the "if (unlikely_switch(&jump_key))" you propose above is
> the right thing to do. Why does the unlikely_ have to be included in the
> name ? Maybe there is a good reason for it, but it would be nice to have
> it spelled out. We might consider:
> 
> if (unlikely(static_branch(&jump_key)))
>   ...
> 
> instead.


Hmm, I see your point here too.


> For the switch statement, from the top of my head the idea would be to
> get something close to the following:
> 
> static __always_inline
> int static_switch_{3,4,5,6...}(struct jump_label_key *key);
> 
> e.g.:
> 
> static __always_inline
> int static_switch_3(struct jump_label_key *key)
> {
> 	asm goto("1:"
> 		JUMP_LABEL_INITIAL_NOP
> 		".pushsection __switch_table_3,  \"a\" \n\t"
> 		_ASM_PTR "%c0, 1b, %l[l_1], %l[l_2] \n\t"
> 		".popsection \n\t"
> 		: :  "i" (key) : : l_1, l_2 );
> 	return 0;
> l_1:
> 	return 1;
> l_2:
> 	return 2;
> }
> 
> switch(static_switch_3(&switch_key)) {
> 	case 0: .....
> 		break;
> 	case 1: .....
> 		break;
> 	case 2: .....
> 		break;
> }
> 
> (I have not tried to give that to gcc 4.5.x to see how the resulting
> assembly looks like. It would be interesting to see if it handles this
> case well)

Something to think about later (when we need such a thing). But I do
agree, perhaps calling it static_branch() instead, is a better idea.

-- Steve