[PATCH] Profile likely/unlikely macros

[PATCH] Profile likely/unlikely macros

[Daniel Walker]

This patch adds a very lightweight profiling feature to the
likely/unlikely macros. It should work in all contexts including
NMI, and during boot. The patch is for 2.6.17-rc2 . 

It has a /proc/likely_prof interface which outputs something like 
the following,

Likely Profiling Results
 --------------------------------------------------------------------
[+- ] Type | # True | # False | Function:Filename@Line
 unlikely |        0|        3  tcp_sacktag_write_queue()@:net/ipv4/tcp_input.c@1215
 unlikely |        0|        3  tcp_sacktag_write_queue()@:net/ipv4/tcp_input.c@1214
 unlikely |        0|        3  tcp_sacktag_write_queue()@:net/ipv4/tcp_input.c@1213
+unlikely |     5050|        0  do_sys_vm86()@:arch/i386/kernel/vm86.c@314
 unlikely |        0|     5050  do_sys_vm86()@:arch/i386/kernel/vm86.c@305
+unlikely |    10100|        0  load_esp0()@:include/asm/processor.h@498
+unlikely |    10100|        0  load_esp0()@:include/asm/processor.h@498
-likely   |        0|     1945  audit_free()@:kernel/auditsc.c@715

You can identify which statments are miss labeled from the + or - in front .

Signed-Off-By: Daniel Walker <dwalker@mvista.com>

Index: linux-2.6.16/include/linux/compiler.h
===================================================================
--- linux-2.6.16.orig/include/linux/compiler.h
+++ linux-2.6.16/include/linux/compiler.h
@@ -53,14 +53,44 @@ extern void __chk_io_ptr(void __iomem *)
 # include <linux/compiler-intel.h>
 #endif
 
+#ifdef CONFIG_PROFILE_LIKELY
+struct likeliness {
+	const char *func;
+	char *file;
+	int line;
+	int type;
+	unsigned int count[2]; 
+	struct likeliness *next;
+};
+
+extern int do_check_likely(struct likeliness *likeliness, int exp);
+
+# define LIKELY_UNSEEN	4
+
+# define __check_likely(exp, is_likely)							\
+	({										\
+		static __attribute__((__section__(".likely.data")))			\
+			struct likeliness likeliness = {				\
+				.func = __func__,					\
+				.file = __FILE__,					\
+				.line = __LINE__,					\
+				.type = is_likely | LIKELY_UNSEEN,			\
+			};								\
+		do_check_likely(&likeliness, !!(exp));					\
+	})
+
+# define likely(x)	__check_likely(x, 1)
+# define unlikely(x)	__check_likely(x, 0)
+#else
 /*
  * Generic compiler-dependent macros required for kernel
  * build go below this comment. Actual compiler/compiler version
  * specific implementations come from the above header files
  */
 
-#define likely(x)	__builtin_expect(!!(x), 1)
-#define unlikely(x)	__builtin_expect(!!(x), 0)
+# define likely(x)	__builtin_expect(!!(x), 1)
+# define unlikely(x)	__builtin_expect(!!(x), 0)
+#endif
 
 /* Optimization barrier */
 #ifndef barrier
Index: linux-2.6.16/lib/Kconfig.debug
===================================================================
--- linux-2.6.16.orig/lib/Kconfig.debug
+++ linux-2.6.16/lib/Kconfig.debug
@@ -223,3 +223,10 @@ config RCU_TORTURE_TEST
 	  at boot time (you probably don't).
 	  Say M if you want the RCU torture tests to build as a module.
 	  Say N if you are unsure.
+config	PROFILE_LIKELY 
+	bool "Record return values from likely/unlikely macros"
+	default n
+	help
+	  Adds profiling on likely/unlikly macros . To see the
+	  results of the profiling you can view the following,
+		/proc/likely_prof
Index: linux-2.6.16/lib/Makefile
===================================================================
--- linux-2.6.16.orig/lib/Makefile
+++ linux-2.6.16/lib/Makefile
@@ -49,6 +49,8 @@ obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o
 
 obj-$(CONFIG_SWIOTLB) += swiotlb.o
 
+obj-$(CONFIG_PROFILE_LIKELY) += likely_prof.o
+
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
 
Index: linux-2.6.16/lib/likely_prof.c
===================================================================
--- /dev/null
+++ linux-2.6.16/lib/likely_prof.c
@@ -0,0 +1,134 @@
+/*
+ * This code should enable profiling the likely and unlikely macros.
+ *
+ * Output goes in /prof/likely_prof
+ *
+ * Authors:
+ * Daniel Walker <dwalker@mvista.com> 
+ * Hua Zhong <hzhong@gmail.com>
+ * Andrew Morton <akpm@osdl.org>
+ */
+
+#include <linux/init.h>
+#include <linux/types.h>
+#include <linux/fs.h>
+#include <linux/seq_file.h>
+#include <linux/proc_fs.h>
+#include <asm/bug.h>
+#include <asm/atomic.h>
+
+#define WAS_UNLIKELY	0	
+#define WAS_LIKELY	1
+
+static struct likeliness *likeliness_head = NULL; 
+
+static atomic_t likely_lock = ATOMIC_INIT(1);
+
+int do_check_likely(struct likeliness *likeliness, int ret)
+{
+	if (ret)
+		likeliness->count[1]++;
+	else
+		likeliness->count[0]++;
+
+	if (likeliness->type & LIKELY_UNSEEN) {
+		if (atomic_dec_and_test(&likely_lock)) {
+			if (likeliness->type & LIKELY_UNSEEN) {
+				likeliness->type &= (~LIKELY_UNSEEN);
+				likeliness->next = likeliness_head;
+				likeliness_head = likeliness;
+			}
+		}
+		atomic_inc(&likely_lock);
+	}
+
+	return ret;
+}
+
+static void * lp_seq_start(struct seq_file *out, loff_t *pos)
+{
+
+	if (!*pos) {
+
+		seq_printf(out, "Likely Profiling Results\n");
+		seq_printf(out, " --------------------------------------------------------------------\n");
+		seq_printf(out, "[+- ] Type | # True | # False | Function:Filename@Line\n");
+
+		out->private = (void *)likeliness_head;
+	}
+
+	return out->private;
+}
+
+static void * lp_seq_next(struct seq_file *out, void *p, loff_t *pos)
+{
+	struct likeliness * entry = (struct likeliness *) p;
+
+	if (entry->next) {
+		++(*pos);
+		out->private = (void *)entry->next;
+	} else 
+		out->private = NULL;
+
+	return (out->private);
+}
+
+static int lp_seq_show(struct seq_file *out, void *p)
+{
+	struct likeliness * entry = (struct likeliness *)p;
+	int true = entry->count[1], false = entry->count[0];
+	
+	if (entry->type == WAS_UNLIKELY) {
+		if (true > false)
+			seq_printf(out, "+");
+		else
+			seq_printf(out, " ");
+
+		seq_printf(out, "unlikely ");
+	}
+	else if (entry->type == WAS_LIKELY) {
+		if (true < false)
+			seq_printf(out, "-");
+		else
+			seq_printf(out, " ");
+
+		seq_printf(out, "likely   ");
+	} 
+
+	seq_printf(out, "|%9u|%9u\t%s()@:%s@%d\n", true, false,
+			entry->func, entry->file, entry->line); 
+
+	return 0;
+}
+
+static void lp_seq_stop(struct seq_file *m, void *p) { }
+
+struct seq_operations likely_profiling_ops = {
+	.start  = lp_seq_start,
+	.next   = lp_seq_next,
+	.stop   = lp_seq_stop,
+	.show   = lp_seq_show
+};
+
+static int lp_results_open(struct inode *inode, struct file *file)
+{
+	return seq_open(file, &likely_profiling_ops);
+}
+
+static struct file_operations proc_likely_operations  = {
+	.open           = lp_results_open,
+	.read           = seq_read,
+	.llseek         = seq_lseek,
+	.release        = seq_release,
+};
+
+static int __init init_likely(void)
+{
+	struct proc_dir_entry *entry;
+	entry = create_proc_entry("likely_prof", 0, &proc_root);
+	if (entry) 
+		entry->proc_fops = &proc_likely_operations;
+
+	return 0;
+}
+__initcall(init_likely);

Re: [PATCH] Profile likely/unlikely macros

[Andrew Morton]

Daniel Walker <dwalker@mvista.com> wrote:
>
>  +	if (likeliness->type & LIKELY_UNSEEN) {
>  +		if (atomic_dec_and_test(&likely_lock)) {
>  +			if (likeliness->type & LIKELY_UNSEEN) {
>  +				likeliness->type &= (~LIKELY_UNSEEN);
>  +				likeliness->next = likeliness_head;
>  +				likeliness_head = likeliness;
>  +			}
>  +		}
>  +		atomic_inc(&likely_lock);

hm, good enough I guess.  It does need a comment explaining why we
don't just do spin_lock().

It'd be a bit saner to do

	if (!test_and_set_bit(&foo, 0)) {
		...
		clear_bit(&foo, 0);
	}

Re: [PATCH] Profile likely/unlikely macros

[Daniel Walker]

On Mon, 2006-04-24 at 20:06 -0700, Andrew Morton wrote:
> Daniel Walker <dwalker@mvista.com> wrote:
> >
> >  +	if (likeliness->type & LIKELY_UNSEEN) {
> >  +		if (atomic_dec_and_test(&likely_lock)) {
> >  +			if (likeliness->type & LIKELY_UNSEEN) {
> >  +				likeliness->type &= (~LIKELY_UNSEEN);
> >  +				likeliness->next = likeliness_head;
> >  +				likeliness_head = likeliness;
> >  +			}
> >  +		}
> >  +		atomic_inc(&likely_lock);
> 
> hm, good enough I guess.  It does need a comment explaining why we
> don't just do spin_lock().
> 
> It'd be a bit saner to do
> 
> 	if (!test_and_set_bit(&foo, 0)) {
> 		...
> 		clear_bit(&foo, 0);
> 	}

Ok .. Also a mistaken "define" in the compiler.h .. I'll fix that as
well ..


Daniel

Re: [PATCH] Profile likely/unlikely macros

[Nick Piggin]

Andrew Morton wrote:
> Daniel Walker <dwalker@mvista.com> wrote:
> 
>> +	if (likeliness->type & LIKELY_UNSEEN) {
>> +		if (atomic_dec_and_test(&likely_lock)) {
>> +			if (likeliness->type & LIKELY_UNSEEN) {
>> +				likeliness->type &= (~LIKELY_UNSEEN);
>> +				likeliness->next = likeliness_head;
>> +				likeliness_head = likeliness;
>> +			}
>> +		}
>> +		atomic_inc(&likely_lock);
> 
> 
> hm, good enough I guess.  It does need a comment explaining why we
> don't just do spin_lock().

I guess it is so it can be used in NMIs and interrupts without turning
interrupts off (so is somewhat lightweight).

But please Daniel, just use spinlocks and trylock. This is buggy because
it doesn't get the required release consistency correct.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

RE: [PATCH] Profile likely/unlikely macros

[Hua Zhong]

 

> Andrew Morton wrote:
> > Daniel Walker <dwalker@mvista.com> wrote:
> > 
> >> +	if (likeliness->type & LIKELY_UNSEEN) {
> >> +		if (atomic_dec_and_test(&likely_lock)) {
> >> +			if (likeliness->type & LIKELY_UNSEEN) {
> >> +				likeliness->type &= (~LIKELY_UNSEEN);
> >> +				likeliness->next = likeliness_head;
> >> +				likeliness_head = likeliness;
> >> +			}
> >> +		}
> >> +		atomic_inc(&likely_lock);
> > 
> > 
> > hm, good enough I guess.  It does need a comment explaining why we 
> > don't just do spin_lock().
> 
> I guess it is so it can be used in NMIs and interrupts 
> without turning interrupts off (so is somewhat lightweight).
> 
> But please Daniel, just use spinlocks and trylock. This is 
> buggy because it doesn't get the required release consistency correct.

Could you elaborate a bit what's wrong here? (memory barriers, etc? What about the test_and_set_bit() thing Andrew suggested?)

Trylock is a bit more dirty because we need to avoid recursion (it used likely/unlikely too). While there are ways to work around
it, atomic operations seem to be cleaner.

Re: [PATCH] Profile likely/unlikely macros

[Daniel Walker]

On Tue, 2006-04-25 at 20:11 +1000, Nick Piggin wrote:

> I guess it is so it can be used in NMIs and interrupts without turning
> interrupts off (so is somewhat lightweight).
> 
> But please Daniel, just use spinlocks and trylock. This is buggy because
> it doesn't get the required release consistency correct.


To use spinlock we would need to used the __raw_ types . As Hua
explained all of the vanilla spinlock calls use the unlikely macro. The
result is that we end up using atomic operations. So using them directly
seems like the cleanest method .

I'm not exactly sure what you mean by "release consistency" ?

Daniel

Re: [PATCH] Profile likely/unlikely macros

[Nick Piggin]

Daniel Walker wrote:

>On Tue, 2006-04-25 at 20:11 +1000, Nick Piggin wrote:
>
>
>>I guess it is so it can be used in NMIs and interrupts without turning
>>interrupts off (so is somewhat lightweight).
>>
>>But please Daniel, just use spinlocks and trylock. This is buggy because
>>it doesn't get the required release consistency correct.
>>
>
>
>To use spinlock we would need to used the __raw_ types . As Hua
>explained all of the vanilla spinlock calls use the unlikely macro. The
>result is that we end up using atomic operations. So using them directly
>seems like the cleanest method .
>

Ah, I see. Then you should be OK with either your current scheme, or
Andrew's suggestion, so long as you have a memory barrier before the
unlock (eg. smp_mb__before_clear_bit()).

>
>I'm not exactly sure what you mean by "release consistency" ?
>

Without a barrier, the stores to the linked list may be visible to another
CPU after the store that unlocks the atomic_t. Ie. the critical section can
leak out of the lock.

--

Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Profile likely/unlikely macros

[Jörn Engel]

On Wed, 26 April 2006 11:08:09 +1000, Nick Piggin wrote:
> Daniel Walker wrote:
> 
> Ah, I see. Then you should be OK with either your current scheme, or
> Andrew's suggestion, so long as you have a memory barrier before the
> unlock (eg. smp_mb__before_clear_bit()).
> 
> >I'm not exactly sure what you mean by "release consistency" ?
> 
> Without a barrier, the stores to the linked list may be visible to another
> CPU after the store that unlocks the atomic_t. Ie. the critical section can
> leak out of the lock.

Admitted, I'm a bit slow at times.  But why does this matter?
According to my fairly limited brain, you take a potentially expensive
barrier, so you pay with a bit of runtime.  What you buy is a smaller
critical section, so you can save some runtime on other cpus.  When
optimizing for the common case, which is one cpu, this is a net loss.

There must be some correctness issue hidden that I cannot see.  Can
you explain that to me?

Jörn

-- 
A victorious army first wins and then seeks battle.
-- Sun Tzu

Re: [PATCH] Profile likely/unlikely macros

[Nick Piggin]

Jörn Engel wrote:

> Admitted, I'm a bit slow at times.  But why does this matter?
> According to my fairly limited brain, you take a potentially expensive
> barrier, so you pay with a bit of runtime.  What you buy is a smaller
> critical section, so you can save some runtime on other cpus.  When
> optimizing for the common case, which is one cpu, this is a net loss.
> 
> There must be some correctness issue hidden that I cannot see.  Can
> you explain that to me?

Another CPU may find the bit clear, enter the critical section,
and load the old `likeliness_head' (value before being changed
by this CPU).

Then it stores the old value to likeliness->next, and overwrites
likeliness_head.

One CPU's update has now gotten lost.

(there are probably other examples, like missing likliness->type)

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

RE: [PATCH] Profile likely/unlikely macros

[Chen, Kenneth W]

Nick Piggin wrote on Tuesday, April 25, 2006 3:11 AM
> Andrew Morton wrote:
> > Daniel Walker <dwalker@mvista.com> wrote:
> > 
> >> +	if (likeliness->type & LIKELY_UNSEEN) {
> >> +		if (atomic_dec_and_test(&likely_lock)) {
> >> +			if (likeliness->type & LIKELY_UNSEEN) {
> >> +				likeliness->type &= (~LIKELY_UNSEEN);
> >> +				likeliness->next = likeliness_head;
> >> +				likeliness_head = likeliness;
> >> +			}
> >> +		}
> >> +		atomic_inc(&likely_lock);
> > 
> > 
> > hm, good enough I guess.  It does need a comment explaining why we
> > don't just do spin_lock().
> 
> I guess it is so it can be used in NMIs and interrupts without turning
> interrupts off (so is somewhat lightweight).
> 
> But please Daniel, just use spinlocks and trylock. This is buggy because
> it doesn't get the required release consistency correct.


It looks to me that there is really no need to construct a linked list for
"unseen" likely/unlikely usage.  The information is already in the struct
"likeliness".  do_check_likely always increment one of the counter, so if
both count values are zero, you know it is "unseen" and can be skipped while
printing the profile.  So you can get rid of all that code by beefing up
seq_next().

- Ken

Re: [PATCH] Profile likely/unlikely macros

[Andreas Mohr]

Hi,

On Mon, Apr 24, 2006 at 07:57:47PM -0700, Daniel Walker wrote:
> This patch adds a very lightweight profiling feature to the
> likely/unlikely macros. It should work in all contexts including
> NMI, and during boot. The patch is for 2.6.17-rc2 . 

Wow, very nice! I had actually had that idea myself, so it's nice to see
it already implemented, and with very nice output.
Rest assured that I'll do my fair share of testing with it!

Thanks a lot!

Andreas Mohr

Re: [PATCH] Profile likely/unlikely macros

[Roland Dreier]

    Daniel> It has a /proc/likely_prof interface which outputs
    Daniel> something like the following,

If we're thinking of applying this to mainline then probably this file
should be in debugfs...

 - R.

Re: [PATCH] Profile likely/unlikely macros

[Mikael Pettersson]

On Mon, 24 Apr 2006 19:57:47 -0700, Daniel Walker wrote:
>+	if (likeliness->type & LIKELY_UNSEEN) {
>+		if (atomic_dec_and_test(&likely_lock)) {
>+			if (likeliness->type & LIKELY_UNSEEN) {
>+				likeliness->type &= (~LIKELY_UNSEEN);
>+				likeliness->next = likeliness_head;
>+				likeliness_head = likeliness;
>+			}
>+		}
>+		atomic_inc(&likely_lock);
>+	}

I'm pretty sure one can do this (prepending an element to a list)
w/o fiddling with locks by using CAS and looping until successful.

/Mikael