[PATCH] likely cleanup: remove unlikely for kfree(NULL)

[PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Hua Zhong]

On my system, it shows about 84K misses and 67K hits. So there are more kfree(NULL) than people realize.

I know some people won't like it, but I think it's not worth the confusion and maintenance burden, so I'm giving it a shot. :-)

Signed-off-by: Hua Zhong <hzhong@gmail.com>

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
diff --git a/mm/slab.c b/mm/slab.c
index e6ef9bd..0fbc854 100644
--- a/mm/slab.c
+++ b/mm/slab.c
@@ -3380,7 +3380,7 @@ void kfree(const void *objp)
  	struct kmem_cache *c;
  	unsigned long flags;

-	if (unlikely(!objp))
+	if (!objp)
  		return;
  	local_irq_save(flags);
  	kfree_debugcheck(objp);

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka Enberg]

On 4/25/06, Hua Zhong <hzhong@gmail.com> wrote:
> diff --git a/mm/slab.c b/mm/slab.c
> index e6ef9bd..0fbc854 100644
> --- a/mm/slab.c
> +++ b/mm/slab.c
> @@ -3380,7 +3380,7 @@ void kfree(const void *objp)
>         struct kmem_cache *c;
>         unsigned long flags;
>
> -       if (unlikely(!objp))
> +       if (!objp)
>                 return;

NAK. Fix the callers instead.

                                              Pekka

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Andreas Mohr]

Hi,

On Wed, Apr 26, 2006 at 10:30:17AM +0300, Pekka Enberg wrote:
> On 4/25/06, Hua Zhong <hzhong@gmail.com> wrote:
> > diff --git a/mm/slab.c b/mm/slab.c
> > index e6ef9bd..0fbc854 100644
> > --- a/mm/slab.c
> > +++ b/mm/slab.c
> > @@ -3380,7 +3380,7 @@ void kfree(const void *objp)
> >         struct kmem_cache *c;
> >         unsigned long flags;
> >
> > -       if (unlikely(!objp))
> > +       if (!objp)
> >                 return;
> 
> NAK. Fix the callers instead.

I don't know. Why then did Wine decide in a lengthy discussion to allow
bogus NULL calls to HeapFree() instead of having NULL checks repeated all over
the place, thus leading to some form of code size bloat?

exit:
	if (foobuffer)
		kfree(foobuffer);
	if (frobbledma)
		kfree(frobbledma);
	if (init_sequence)
		kfree(init_sequence);

	return result;

sure sounds worse than

exit:
	kfree(foobuffer);
	kfree(frobbledma);
	kfree(init_sequence);

	return result;
	
	

Perhaps one way to resolve this would be to add an explanatory comment
to the kfree() NULL check that says that the most frequent NULL abusers
should be fixed (e.g. via call trace profiling), and *only those*?

And drop the (un)likely() in that case, of course, since it's a relatively
"average" decision here.

Andreas Mohr

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Wed, 2006-04-26 at 10:30 +0300, Pekka Enberg wrote:
> On 4/25/06, Hua Zhong <hzhong@gmail.com> wrote:
> > diff --git a/mm/slab.c b/mm/slab.c
> > index e6ef9bd..0fbc854 100644
> > --- a/mm/slab.c
> > +++ b/mm/slab.c
> > @@ -3380,7 +3380,7 @@ void kfree(const void *objp)
> >         struct kmem_cache *c;
> >         unsigned long flags;
> >
> > -       if (unlikely(!objp))
> > +       if (!objp)
> >                 return;
> 
> NAK. Fix the callers instead.

eh dude... they are being fixed... to remove the NULL check :)

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka J Enberg]

On 4/25/06, Hua Zhong <hzhong@gmail.com> wrote:
> > > diff --git a/mm/slab.c b/mm/slab.c
> > > index e6ef9bd..0fbc854 100644
> > > --- a/mm/slab.c
> > > +++ b/mm/slab.c
> > > @@ -3380,7 +3380,7 @@ void kfree(const void *objp)
> > >         struct kmem_cache *c;
> > >         unsigned long flags;
> > >
> > > -       if (unlikely(!objp))
> > > +       if (!objp)
> > >                 return;

> On Wed, 2006-04-26 at 10:30 +0300, Pekka Enberg wrote:
> > NAK. Fix the callers instead.

On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> eh dude... they are being fixed... to remove the NULL check :)

Most of which are on error paths. The problem we're seeing is in handful 
of fastpath offenders which should be fixed either by re-design or adding 
the NULL check along with a big fat comment like Andrew is doing.

					Pekka

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Wed, 2006-04-26 at 11:16 +0300, Pekka J Enberg wrote:
> On 4/25/06, Hua Zhong <hzhong@gmail.com> wrote:
> > > > diff --git a/mm/slab.c b/mm/slab.c
> > > > index e6ef9bd..0fbc854 100644
> > > > --- a/mm/slab.c
> > > > +++ b/mm/slab.c
> > > > @@ -3380,7 +3380,7 @@ void kfree(const void *objp)
> > > >         struct kmem_cache *c;
> > > >         unsigned long flags;
> > > >
> > > > -       if (unlikely(!objp))
> > > > +       if (!objp)
> > > >                 return;
> 
> > On Wed, 2006-04-26 at 10:30 +0300, Pekka Enberg wrote:
> > > NAK. Fix the callers instead.
> 
> On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> > eh dude... they are being fixed... to remove the NULL check :)
> 
> Most of which are on error paths. The problem we're seeing is in handful 
> of fastpath offenders which should be fixed either by re-design or adding 
> the NULL check along with a big fat comment like Andrew is doing.

what I would like is kfree to become an inline wrapper that does the
null check inline, that way gcc can optimize it out (and it will in 4.1
with the VRP pass) if gcc can prove it's not NULL.

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Adrian Bunk]

On Wed, Apr 26, 2006 at 10:27:18AM +0200, Arjan van de Ven wrote:
> On Wed, 2006-04-26 at 11:16 +0300, Pekka J Enberg wrote:
> > On 4/25/06, Hua Zhong <hzhong@gmail.com> wrote:
> > > > > diff --git a/mm/slab.c b/mm/slab.c
> > > > > index e6ef9bd..0fbc854 100644
> > > > > --- a/mm/slab.c
> > > > > +++ b/mm/slab.c
> > > > > @@ -3380,7 +3380,7 @@ void kfree(const void *objp)
> > > > >         struct kmem_cache *c;
> > > > >         unsigned long flags;
> > > > >
> > > > > -       if (unlikely(!objp))
> > > > > +       if (!objp)
> > > > >                 return;
> > 
> > > On Wed, 2006-04-26 at 10:30 +0300, Pekka Enberg wrote:
> > > > NAK. Fix the callers instead.
> > 
> > On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> > > eh dude... they are being fixed... to remove the NULL check :)
> > 
> > Most of which are on error paths. The problem we're seeing is in handful 
> > of fastpath offenders which should be fixed either by re-design or adding 
> > the NULL check along with a big fat comment like Andrew is doing.
> 
> what I would like is kfree to become an inline wrapper that does the
> null check inline, that way gcc can optimize it out (and it will in 4.1
> with the VRP pass) if gcc can prove it's not NULL.

In many cases it's not clear at compile time whether it will be NULL.

In such cases, your suggestion would result in bigger code.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Jörn Engel]

On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
> 
> what I would like is kfree to become an inline wrapper that does the
> null check inline, that way gcc can optimize it out (and it will in 4.1
> with the VRP pass) if gcc can prove it's not NULL.

How well can gcc optimize this case?  I guess the effect on text size
of such a patch may give an indication.

Jörn

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

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Wed, 2006-04-26 at 12:05 +0200, Jörn Engel wrote:
> On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
> > 
> > what I would like is kfree to become an inline wrapper that does the
> > null check inline, that way gcc can optimize it out (and it will in 4.1
> > with the VRP pass) if gcc can prove it's not NULL.
> 
> How well can gcc optimize this case? 

if you deref'd the pointer it'll optimize it away (assuming a new enough
gcc, like 4.1)

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka J Enberg]

On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
> > > what I would like is kfree to become an inline wrapper that does the
> > > null check inline, that way gcc can optimize it out (and it will in 4.1
> > > with the VRP pass) if gcc can prove it's not NULL.

On Wed, 2006-04-26 at 12:05 +0200, Jörn Engel wrote:
> > How well can gcc optimize this case? 

On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> if you deref'd the pointer it'll optimize it away (assuming a new enough
> gcc, like 4.1)

Here are the numbers for allyesconfig on my setup.

				Pekka

gcc version 3.4.5 (Gentoo 3.4.5-r1, ssp-3.4.5-1.0, pie-8.7.9)

    text    data     bss     dec      hex filename
24910301 6946478 2092332 33949111 20605b7 vmlinux
24934157 6946530 2092332 33973019 206631b vmlinux-inline-kfree


diff --git a/include/linux/slab.h b/include/linux/slab.h
index 3af03b1..1b4b3bb 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -148,7 +148,14 @@ static inline void *kcalloc(size_t n, si
 	return kzalloc(n * size, flags);
 }
 
-extern void kfree(const void *);
+extern void __kfree(const void *);
+
+static inline void kfree(const void *p)
+{
+	if (unlikely(p))
+		__kfree(p);
+}
+
 extern unsigned int ksize(const void *);
 
 #ifdef CONFIG_NUMA
diff --git a/mm/slab.c b/mm/slab.c
index e6ef9bd..1f63787 100644
--- a/mm/slab.c
+++ b/mm/slab.c
@@ -3367,7 +3367,7 @@ void kmem_cache_free(struct kmem_cache *
 EXPORT_SYMBOL(kmem_cache_free);
 
 /**
- * kfree - free previously allocated memory
+ * __kfree - free previously allocated memory
  * @objp: pointer returned by kmalloc.
  *
  * If @objp is NULL, no operation is performed.
@@ -3375,13 +3375,11 @@ EXPORT_SYMBOL(kmem_cache_free);
  * Don't free memory not originally allocated by kmalloc()
  * or you will run into trouble.
  */
-void kfree(const void *objp)
+void __kfree(const void *objp)
 {
 	struct kmem_cache *c;
 	unsigned long flags;
 
-	if (unlikely(!objp))
-		return;
 	local_irq_save(flags);
 	kfree_debugcheck(objp);
 	c = virt_to_cache(objp);
@@ -3389,7 +3387,7 @@ void kfree(const void *objp)
 	__cache_free(c, (void *)objp);
 	local_irq_restore(flags);
 }
-EXPORT_SYMBOL(kfree);
+EXPORT_SYMBOL(__kfree);
 
 #ifdef CONFIG_SMP
 /**

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Wed, 2006-04-26 at 13:57 +0300, Pekka J Enberg wrote:
> On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
> > > > what I would like is kfree to become an inline wrapper that does the
> > > > null check inline, that way gcc can optimize it out (and it will in 4.1
> > > > with the VRP pass) if gcc can prove it's not NULL.
> 
> On Wed, 2006-04-26 at 12:05 +0200, Jörn Engel wrote:
> > > How well can gcc optimize this case? 
> 
> On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> > if you deref'd the pointer it'll optimize it away (assuming a new enough
> > gcc, like 4.1)
> 
> Here are the numbers for allyesconfig on my setup.
> 
> 				Pekka
> 
> gcc version 3.4.5 (Gentoo 3.4.5-r1, ssp-3.4.5-1.0, pie-8.7.9)


this is an ancient gcc without VRP so yeah the growth is expected ;)

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Jörn Engel]

On Wed, 26 April 2006 13:03:34 +0200, Arjan van de Ven wrote:
> On Wed, 2006-04-26 at 13:57 +0300, Pekka J Enberg wrote:
> > On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
> > > > > what I would like is kfree to become an inline wrapper that does the
> > > > > null check inline, that way gcc can optimize it out (and it will in 4.1
> > > > > with the VRP pass) if gcc can prove it's not NULL.
> > 
> > On Wed, 2006-04-26 at 12:05 +0200, Jörn Engel wrote:
> > > > How well can gcc optimize this case? 
> > 
> > On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> > > if you deref'd the pointer it'll optimize it away (assuming a new enough
> > > gcc, like 4.1)
> > 
> > Here are the numbers for allyesconfig on my setup.
> > 
> > 				Pekka
> > 
> > gcc version 3.4.5 (Gentoo 3.4.5-r1, ssp-3.4.5-1.0, pie-8.7.9)
> 
> this is an ancient gcc without VRP so yeah the growth is expected ;)

In other words, we shouldn't do this as long as most users don't have
gcc 4.1 or higher installed.  So this is somewhat pointless at the
moment.

Still, if you could respin this with gcc 4.1 and post the numbers,
Pekka, that would be quite interesting.

Jörn

-- 
The strong give up and move away, while the weak give up and stay.
-- unknown

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Bart Hartgers]

[-- Attachment #1: Type: text/plain, Size: 1936 bytes --]

Jörn Engel wrote:
> On Wed, 26 April 2006 13:03:34 +0200, Arjan van de Ven wrote:
>> On Wed, 2006-04-26 at 13:57 +0300, Pekka J Enberg wrote:
>>> On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
>>>>>> what I would like is kfree to become an inline wrapper that does the
>>>>>> null check inline, that way gcc can optimize it out (and it will in 4.1
>>>>>> with the VRP pass) if gcc can prove it's not NULL.
>>> On Wed, 2006-04-26 at 12:05 +0200, Jörn Engel wrote:
>>>>> How well can gcc optimize this case? 
>>> On Wed, 26 Apr 2006, Arjan van de Ven wrote:
>>>> if you deref'd the pointer it'll optimize it away (assuming a new enough
>>>> gcc, like 4.1)
>>> Here are the numbers for allyesconfig on my setup.
>>>
>>> 				Pekka
>>>
>>> gcc version 3.4.5 (Gentoo 3.4.5-r1, ssp-3.4.5-1.0, pie-8.7.9)
>> this is an ancient gcc without VRP so yeah the growth is expected ;)
> 
> In other words, we shouldn't do this as long as most users don't have
> gcc 4.1 or higher installed.  So this is somewhat pointless at the
> moment.
> 
> Still, if you could respin this with gcc 4.1 and post the numbers,
> Pekka, that would be quite interesting.
> 
> Jörn
> 

What about this:

static inline void my_kfree( void *ptr )
{
        if (__builtin_constant_p(ptr!=NULL)) {
                if (ptr!=NULL)
                        my_fast_free(ptr); /* skips NULL check */
        } else {
                my_checking_free(ptr); /* does a NULL check */
        }
}

That would skip the free when ptr is known to be NULL, and skip the
equal to NULL check if it is known to be not NULL, and do what happened
before otherwise. In other words, it is never worse than what we have now.

Attached is a small testcase in C and the resulting assembly. Note that
my compiler doesn't catch the "not equal to zero" case, but 4.1 is
supposed to do this.

Groeten,
Bart




-- 
Bart Hartgers - TUE Eindhoven - http://plasimo.phys.tue.nl/bart/contact/

[-- Attachment #2: testje.c --]
[-- Type: text/x-csrc, Size: 395 bytes --]

#define NULL ((void *)(0))

extern void my_fast_free(void *);
extern void my_checking_free(void *);

static inline void my_kfree( void *ptr )
{
	if (__builtin_constant_p(ptr!=NULL)) {
		if (ptr!=NULL)
			my_fast_free(ptr);
	} else {
		my_checking_free(ptr);
	}
}

void test( int *bla )
{
	char *hello = NULL;
	my_kfree(hello);
	my_kfree(bla);
	*bla = 1;	/* now it is !=NULL */
	my_kfree(bla);
}

[-- Attachment #3: testje.S --]
[-- Type: text/plain, Size: 418 bytes --]

	.file	"testje.c"
	.text
	.p2align 4,,15
.globl test
	.type	test, @function
test:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ebx
	subl	$16, %esp
	movl	8(%ebp), %ebx
	pushl	%ebx
	call	my_checking_free
	movl	$1, (%ebx)
	movl	%ebx, 8(%ebp)
	addl	$16, %esp
	movl	-4(%ebp), %ebx
	leave
	jmp	my_checking_free
	.size	test, .-test
	.ident	"GCC: (GNU) 4.0.2 20050901 (prerelease) (SUSE Linux)"
	.section	.note.GNU-stack,"",@progbits

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Bart Hartgers]

[-- Attachment #1: Type: text/plain, Size: 3052 bytes --]

Bart Hartgers wrote:
> Jörn Engel wrote:
>> On Wed, 26 April 2006 13:03:34 +0200, Arjan van de Ven wrote:
>>> On Wed, 2006-04-26 at 13:57 +0300, Pekka J Enberg wrote:
>>>> On Wed, 26 April 2006 10:27:18 +0200, Arjan van de Ven wrote:
>>>>>>> what I would like is kfree to become an inline wrapper that does the
>>>>>>> null check inline, that way gcc can optimize it out (and it will in 4.1
>>>>>>> with the VRP pass) if gcc can prove it's not NULL.
>>>> On Wed, 2006-04-26 at 12:05 +0200, Jörn Engel wrote:
>>>>>> How well can gcc optimize this case? 
>>>> On Wed, 26 Apr 2006, Arjan van de Ven wrote:
>>>>> if you deref'd the pointer it'll optimize it away (assuming a new enough
>>>>> gcc, like 4.1)
>>>> Here are the numbers for allyesconfig on my setup.
>>>>
>>>> 				Pekka
>>>>
>>>> gcc version 3.4.5 (Gentoo 3.4.5-r1, ssp-3.4.5-1.0, pie-8.7.9)
>>> this is an ancient gcc without VRP so yeah the growth is expected ;)
>> In other words, we shouldn't do this as long as most users don't have
>> gcc 4.1 or higher installed.  So this is somewhat pointless at the
>> moment.
>>
>> Still, if you could respin this with gcc 4.1 and post the numbers,
>> Pekka, that would be quite interesting.
>>
>> Jörn
>>
> 
> What about this:
> 
> static inline void my_kfree( void *ptr )
> {
>         if (__builtin_constant_p(ptr!=NULL)) {
>                 if (ptr!=NULL)
>                         my_fast_free(ptr); /* skips NULL check */
>         } else {
>                 my_checking_free(ptr); /* does a NULL check */
>         }
> }
> 
> That would skip the free when ptr is known to be NULL, and skip the
> equal to NULL check if it is known to be not NULL, and do what happened
> before otherwise. In other words, it is never worse than what we have now.
> 
> Attached is a small testcase in C and the resulting assembly. Note that
> my compiler doesn't catch the "not equal to zero" case, but 4.1 is
> supposed to do this.
> 
> Groeten,
> Bart
> 

Sorry about replying to my own mail, but I discovered that at least "gcc
(GCC) 4.1.0 (SUSE Linux)" does not seem to combine the
delete-null-pointer optimisation with the builtin_constant test. The
compiler is happy to eliminate ptr==NULL tests, but does not consider
the expression (ptr==NULL) constant! I managed to hack around this.

See the attached code, and:

bart@gum15:~> gcc -DCASE_A -m32 -O3 -S -o testje-a.S testje.c
bart@gum15:~> gcc -DCASE_B -m32 -O3 -S -o testje-b.S testje.c
bart@gum15:~> diff -u testje-a.S testje-b.S
--- testje-a.S  2006-04-26 14:57:50.000000000 +0200
+++ testje-b.S  2006-04-26 14:57:53.000000000 +0200
@@ -16,7 +16,7 @@
        addl    $4, %esp
        popl    %ebx
        popl    %ebp
-       jmp     my_fast_free
+       jmp     my_slow_free
        .size   test, .-test
        .ident  "GCC: (GNU) 4.1.0 (SUSE Linux)"
        .section        .note.GNU-stack,"",@progbits

Anyway, CASE_A produces optimal code for gcc 4.1, and gcc 4.0 produces
identical code in both cases.

Groeten,
Bart
-- 
Bart Hartgers - TUE Eindhoven - http://plasimo.phys.tue.nl/bart/contact/

[-- Attachment #2: testje.c --]
[-- Type: text/x-csrc, Size: 501 bytes --]

#include <stddef.h>

extern void my_fast_free(void *);
extern void my_checking_free(void *);

static inline void my_kfree( void *ptr )
{
#ifdef CASE_A
	register int is_null = 0;
	if (ptr == NULL)
		is_null = 1;
	if (__builtin_constant_p(is_null)) {
#else /* CASE_B */
	if (__builtin_constant_p(ptr==NULL)) {
#endif
		if (ptr != NULL)
			my_fast_free(ptr);
	} else {
		my_slow_free(ptr);
	}
}

void test( int *bla )
{
	char *hello = NULL;
	my_kfree(hello);
	my_kfree(bla);
	*bla = 1;
	my_kfree(bla);
}

[-- Attachment #3: testje-a.S --]
[-- Type: text/plain, Size: 387 bytes --]

	.file	"testje.c"
	.text
	.p2align 4,,15
.globl test
	.type	test, @function
test:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ebx
	subl	$4, %esp
	movl	8(%ebp), %ebx
	movl	%ebx, (%esp)
	call	my_slow_free
	movl	$1, (%ebx)
	movl	%ebx, 8(%ebp)
	addl	$4, %esp
	popl	%ebx
	popl	%ebp
	jmp	my_fast_free
	.size	test, .-test
	.ident	"GCC: (GNU) 4.1.0 (SUSE Linux)"
	.section	.note.GNU-stack,"",@progbits

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Kyle Moffett]

Here's code that I've found works as well as can be expected under  
both GCC 3 and GCC 4.  If xp is a known-NULL constant the whole  
function will be optimized out completely.  If xp is known-not-NULL,  
then it will optimize to a kfree function without the null check.   
Otherwise it optimizes to call the out-of-line version.

Cheers,
Kyle Moffett

static inline void kfree(void *ptr)
{
	if (__builtin_constant_p((ptr == NULL))) {
		if (ptr)
			kfree_nonnull(ptr);
	} else {
		kfree_unknown(ptr);
	}
}

void kfree_nonnull(void *ptr)
{
	/* kfree code here, no null check */
}

void kfree_unknown(void *ptr)
{
	if (ptr)
		kfree_nonnull(ptr);
}

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka J Enberg]

On Wed, 26 Apr 2006, Kyle Moffett wrote:
> Here's code that I've found works as well as can be expected under both GCC 3
> and GCC 4.  If xp is a known-NULL constant the whole function will be
> optimized out completely.  If xp is known-not-NULL, then it will optimize to a
> kfree function without the null check.  Otherwise it optimizes to call the
> out-of-line version.

Wouldn't it be better to simply remove calls to kfree() with known 
NULL constant?

				Pekka

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Nick Piggin]

Pekka J Enberg wrote:
> On Wed, 26 Apr 2006, Kyle Moffett wrote:
> 
>>Here's code that I've found works as well as can be expected under both GCC 3
>>and GCC 4.  If xp is a known-NULL constant the whole function will be
>>optimized out completely.  If xp is known-not-NULL, then it will optimize to a
>>kfree function without the null check.  Otherwise it optimizes to call the
>>out-of-line version.
> 
> 
> Wouldn't it be better to simply remove calls to kfree() with known 
> NULL constant?

Yes, but this will optimise away the check for known non-NULL.

At the cost of icache footprint.

I think unmeasurable micro-optimisations that go against historic
CPU trends (eg. size for speed) aren't worth wasting too much
sleep over. If it is a 0.0001% speedup today, it'll be a 0.0001%
slowdown tomorrow :)

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

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Bart Hartgers]

Kyle Moffett wrote:
> Here's code that I've found works as well as can be expected under both
> GCC 3 and GCC 4.  If xp is a known-NULL constant the whole function will
> be optimized out completely.  If xp is known-not-NULL, then it will
> optimize to a kfree function without the null check.  Otherwise it
> optimizes to call the out-of-line version.
> 
> Cheers,
> Kyle Moffett
> 
> static inline void kfree(void *ptr)
> {
>     if (__builtin_constant_p((ptr == NULL))) {
>         if (ptr)
>             kfree_nonnull(ptr);
>     } else {
>         kfree_unknown(ptr);
>     }
> }
> 
> void kfree_nonnull(void *ptr)
> {
>     /* kfree code here, no null check */
> }
> 
> void kfree_unknown(void *ptr)
> {
>     if (ptr)
>         kfree_nonnull(ptr);
> }

I still think there is an inconsistency in gcc. If I call your kfree
with the following:

void test( char *ptr )
{
        char *null = NULL;
        kfree(ptr);	/* unknown */
        *ptr = 'a';
        kfree(ptr);	/* nonnull */
        kfree(null);	/* should be optimised away */
}

,the compiler (4.1) generates two calls to kfree_unknown instead of one
to kfree_nonnull and one to kfree_unknown. It seems that the
__builtin_constant_p((ptr==NULL)) check does not always trigger, even if
the compiler 'knows' ptr to be equal to NULL. I posted a nasty hack
around this problem yesterday.

Groeten,
Bart

-- 
Bart Hartgers - TUE Eindhoven - http://plasimo.phys.tue.nl/bart/contact/

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Kyle Moffett]

On Apr 27, 2006, at 04:17:50, Bart Hartgers wrote:
> Kyle Moffett wrote:
>> static inline void kfree(void *ptr)
>> {
>>     if (__builtin_constant_p((ptr == NULL))) {
>>         if (ptr)
>>             kfree_nonnull(ptr);
>>     } else {
>>         kfree_unknown(ptr);
>>     }
>> }
>>
>> void kfree_nonnull(void *ptr)
>> {
>>     /* kfree code here, no null check */
>> }
>>
>> void kfree_unknown(void *ptr)
>> {
>>     if (ptr)
>>         kfree_nonnull(ptr);
>> }
>
> I still think there is an inconsistency in gcc. If I call your  
> kfree with the following:
>
> void test( char *ptr )
> {
>         char *null = NULL;
>         kfree(ptr);	/* unknown */
>         *ptr = 'a';
>         kfree(ptr);	/* nonnull */
>         kfree(null);	/* should be optimised away */
> }
>
> ,the compiler (4.1) generates two calls to kfree_unknown instead of  
> one to kfree_nonnull and one to kfree_unknown. It seems that the  
> __builtin_constant_p((ptr==NULL)) check does not always trigger,  
> even if the compiler 'knows' ptr to be equal to NULL. I posted a  
> nasty hack around this problem yesterday.

I know.  You can "fix" this problem by changing the if statement to  
this:

if (__builtin_constant_p(ptr) || __builtin_constant_p((ptr == NULL)))

On the other hand, calling kfree(ptr) on a non-NULL constant pointer  
is a bug and will crash, and calling kfree(ptr) on a NULL constant  
ptr is just dead code and we should find and kill that separately.   
There's no reason to ever call kfree(<constant>).

Cheers,
Kyle Moffett

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka J Enberg]

On Wed, 26 Apr 2006, Jörn Engel wrote:
> Still, if you could respin this with gcc 4.1 and post the numbers,
> Pekka, that would be quite interesting.

I can do that, certainly. I'll send them tomorrow.

				Pekka

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka J Enberg]

On Wed, 26 Apr 2006, Jörn Engel wrote:
> Still, if you could respin this with gcc 4.1 and post the numbers,
> Pekka, that would be quite interesting.

Inlining kfree the way I did doesn't pay off in 4.1 either.

   text    data     bss     dec     hex filename
24910301 6946478 2092332 33949111 20605b7 vmlinux-gcc-3.4.5
24934157 6946530 2092332 33973019 206631b vmlinux-inline-kfree-gcc-3.4.5
24171004 6484710 2090188 32745902 1f3a9ae vmlinux-gcc-4.1.0
24185925 6484722 2090188 32760835 1f3e403 vmlinux-inline-kfree-gcc-4.1.0

				Pekka

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Nick Piggin]

Pekka J Enberg wrote:
> On Wed, 26 Apr 2006, Jörn Engel wrote:
> 
>>Still, if you could respin this with gcc 4.1 and post the numbers,
>>Pekka, that would be quite interesting.
> 
> 
> Inlining kfree the way I did doesn't pay off in 4.1 either.

Not to dispute your conclusions or method, but I think doing a
defconfig or your personal config might be more representative
of % size increase of text that will actually be executed. And
that is the expensive type of text.

eg. core code may contain many more instances of checks that
cannot be optimised away, meaning it may be a more significant
cache footprint increase than the 0.05% increase in your test.

Of course, it is equally possible that the instances in core
code do not represent often-executed code, so it is a bit of a
fudge either way.

>    text    data     bss     dec     hex filename
> 24910301 6946478 2092332 33949111 20605b7 vmlinux-gcc-3.4.5
> 24934157 6946530 2092332 33973019 206631b vmlinux-inline-kfree-gcc-3.4.5
> 24171004 6484710 2090188 32745902 1f3a9ae vmlinux-gcc-4.1.0
> 24185925 6484722 2090188 32760835 1f3e403 vmlinux-inline-kfree-gcc-4.1.0

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

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Pekka J Enberg]

On Thu, 27 Apr 2006, Nick Piggin wrote:
> Not to dispute your conclusions or method, but I think doing a
> defconfig or your personal config might be more representative
> of % size increase of text that will actually be executed. And
> that is the expensive type of text.

True but I was under the impression that Arjan thought we'd get text 
savings with GCC 4.1 by making kfree() inline.

				Pekka

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
> On Thu, 27 Apr 2006, Nick Piggin wrote:
> > Not to dispute your conclusions or method, but I think doing a
> > defconfig or your personal config might be more representative
> > of % size increase of text that will actually be executed. And
> > that is the expensive type of text.
> 
> True but I was under the impression that Arjan thought we'd get text 
> savings with GCC 4.1 by making kfree() inline.

not savings in text size, I'll settle for the same size.
What we gain is less branches in the hotpath... eg a kfree that gets
optimized now has one less branch. Note that the branch predictor isn't
going to help you for these 100% cases, since the same branch "slot" is
shared between all callers; with this inline the branch predictor at
least gets to keep stats for each of the callers individually.
That is where the gain is....

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Adrian Bunk]

On Thu, Apr 27, 2006 at 08:50:40AM +0200, Arjan van de Ven wrote:
> On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
> > On Thu, 27 Apr 2006, Nick Piggin wrote:
> > > Not to dispute your conclusions or method, but I think doing a
> > > defconfig or your personal config might be more representative
> > > of % size increase of text that will actually be executed. And
> > > that is the expensive type of text.
> > 
> > True but I was under the impression that Arjan thought we'd get text 
> > savings with GCC 4.1 by making kfree() inline.
> 
> not savings in text size, I'll settle for the same size.
>...

It will always be bigger since there are cases where it's unknown at 
compile time whether it will be NULL when called.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Thu, 2006-04-27 at 10:31 +0200, Adrian Bunk wrote:
> On Thu, Apr 27, 2006 at 08:50:40AM +0200, Arjan van de Ven wrote:
> > On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
> > > On Thu, 27 Apr 2006, Nick Piggin wrote:
> > > > Not to dispute your conclusions or method, but I think doing a
> > > > defconfig or your personal config might be more representative
> > > > of % size increase of text that will actually be executed. And
> > > > that is the expensive type of text.
> > > 
> > > True but I was under the impression that Arjan thought we'd get text 
> > > savings with GCC 4.1 by making kfree() inline.
> > 
> > not savings in text size, I'll settle for the same size.
> >...
> 
> It will always be bigger since there are cases where it's unknown at 
> compile time whether it will be NULL when called.

if it's "unknown" you could call into a separate kfree() which does
check out of line. (sure that's a dozen bytes bigger but that is
noise ;)

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Adrian Bunk]

On Thu, Apr 27, 2006 at 10:41:12AM +0200, Arjan van de Ven wrote:
> On Thu, 2006-04-27 at 10:31 +0200, Adrian Bunk wrote:
> > On Thu, Apr 27, 2006 at 08:50:40AM +0200, Arjan van de Ven wrote:
> > > On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
> > > > On Thu, 27 Apr 2006, Nick Piggin wrote:
> > > > > Not to dispute your conclusions or method, but I think doing a
> > > > > defconfig or your personal config might be more representative
> > > > > of % size increase of text that will actually be executed. And
> > > > > that is the expensive type of text.
> > > > 
> > > > True but I was under the impression that Arjan thought we'd get text 
> > > > savings with GCC 4.1 by making kfree() inline.
> > > 
> > > not savings in text size, I'll settle for the same size.
> > >...
> > 
> > It will always be bigger since there are cases where it's unknown at 
> > compile time whether it will be NULL when called.
> 
> if it's "unknown" you could call into a separate kfree() which does
> check out of line. (sure that's a dozen bytes bigger but that is
> noise ;)

It's noise and _much work.

So in the end, we are removing the current kfree() and replacing them 
with one kfree_can_be_null() and one kfree_cannot_be_null()
(one of them might continue to be called kfree())?

Keeping kfree() as it is today has the advantages:
- smallest code
- noone can forget the NULL check
- KISS

Do you have any benchmarks where your approach brings a measurable 
benefit? I wouldn't have expected kfree() being in many hotpaths.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

On Thu, 2006-04-27 at 10:56 +0200, Adrian Bunk wrote:
> On Thu, Apr 27, 2006 at 10:41:12AM +0200, Arjan van de Ven wrote:
> > On Thu, 2006-04-27 at 10:31 +0200, Adrian Bunk wrote:
> > > On Thu, Apr 27, 2006 at 08:50:40AM +0200, Arjan van de Ven wrote:
> > > > On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
> > > > > On Thu, 27 Apr 2006, Nick Piggin wrote:
> > > > > > Not to dispute your conclusions or method, but I think doing a
> > > > > > defconfig or your personal config might be more representative
> > > > > > of % size increase of text that will actually be executed. And
> > > > > > that is the expensive type of text.
> > > > > 
> > > > > True but I was under the impression that Arjan thought we'd get text 
> > > > > savings with GCC 4.1 by making kfree() inline.
> > > > 
> > > > not savings in text size, I'll settle for the same size.
> > > >...
> > > 
> > > It will always be bigger since there are cases where it's unknown at 
> > > compile time whether it will be NULL when called.
> > 
> > if it's "unknown" you could call into a separate kfree() which does
> > check out of line. (sure that's a dozen bytes bigger but that is
> > noise ;)
> 
> It's noise and _much work.

not if the compiler can do it. The *compiler* knows a lot (4.1 at
least)..

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Bart Hartgers]

[-- Attachment #1: Type: text/plain, Size: 2008 bytes --]

Arjan van de Ven wrote:
> On Thu, 2006-04-27 at 10:56 +0200, Adrian Bunk wrote:
>> On Thu, Apr 27, 2006 at 10:41:12AM +0200, Arjan van de Ven wrote:
>>> On Thu, 2006-04-27 at 10:31 +0200, Adrian Bunk wrote:
>>>> On Thu, Apr 27, 2006 at 08:50:40AM +0200, Arjan van de Ven wrote:
>>>>> On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
>>>>>> On Thu, 27 Apr 2006, Nick Piggin wrote:
>>>>>>> Not to dispute your conclusions or method, but I think doing a
>>>>>>> defconfig or your personal config might be more representative
>>>>>>> of % size increase of text that will actually be executed. And
>>>>>>> that is the expensive type of text.
>>>>>> True but I was under the impression that Arjan thought we'd get text 
>>>>>> savings with GCC 4.1 by making kfree() inline.
>>>>> not savings in text size, I'll settle for the same size.
>>>>> ...
>>>> It will always be bigger since there are cases where it's unknown at 
>>>> compile time whether it will be NULL when called.
>>> if it's "unknown" you could call into a separate kfree() which does
>>> check out of line. (sure that's a dozen bytes bigger but that is
>>> noise ;)
>> It's noise and _much work.
> 
> not if the compiler can do it. The *compiler* knows a lot (4.1 at
> least)..

I would think so too. Unfortunately this is what I found for make
allyesconfig on 2.6.16.9:

   text    data     bss     dec     hex filename
21615935 7929490 2187672 31733097        1e43569 vmlinux-3.3.5-new
21616824 7929298 2187672 31733794        1e43822 vmlinux-3.3.5-old
21546713 7616546 2184984 31348243        1de5613 vmlinux-4.1.0-new
21546551 7616458 2184984 31347993        1de5519 vmlinux-4.1.0-old

Where "old" is the original one, and "new" the one with the included
patch applied. So the patch is a small win with gcc-3.3.5 and a small
loss on gcc-4.1.0. I don't really understand why 4.1.0 produces larger
code with the patch, but I triple-checked...

Groeten,
Bart




-- 
Bart Hartgers - TUE Eindhoven - http://plasimo.phys.tue.nl/bart/contact/

[-- Attachment #2: null-check.patch --]
[-- Type: text/x-patch, Size: 1125 bytes --]

--- linux-2.6.16.9/include/linux/slab.h	2006-04-19 08:10:14.000000000 +0200
+++ linux-2.6.16.9-kfree/include/linux/slab.h	2006-04-27 11:19:00.000000000 +0200
@@ -123,7 +123,18 @@
 	return kzalloc(n * size, flags);
 }
 
-extern void kfree(const void *);
+extern void __kfree(const void *);
+
+static inline void kfree(const void *ptr)
+{
+	if (__builtin_constant_p(ptr==NULL)) {
+		if (ptr)
+			__kfree(ptr);
+	} else {
+		__kfree(ptr);
+	}
+}
+
 extern unsigned int ksize(const void *);
 
 #ifdef CONFIG_NUMA
--- linux-2.6.16.9/mm/slab.c	2006-04-27 11:24:38.000000000 +0200
+++ linux-2.6.16.9-kfree/mm/slab.c	2006-04-27 11:17:06.000000000 +0200
@@ -3267,7 +3267,7 @@
 EXPORT_SYMBOL(kmem_cache_free);
 
 /**
- * kfree - free previously allocated memory
+ * __kfree - free previously allocated memory
  * @objp: pointer returned by kmalloc.
  *
  * If @objp is NULL, no operation is performed.
@@ -3275,7 +3275,7 @@
  * Don't free memory not originally allocated by kmalloc()
  * or you will run into trouble.
  */
-void kfree(const void *objp)
+void __kfree(const void *objp)
 {
 	struct kmem_cache *c;
 	unsigned long flags;

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Adrian Bunk]

On Thu, Apr 27, 2006 at 11:08:05AM +0200, Arjan van de Ven wrote:
> On Thu, 2006-04-27 at 10:56 +0200, Adrian Bunk wrote:
> > On Thu, Apr 27, 2006 at 10:41:12AM +0200, Arjan van de Ven wrote:
> > > On Thu, 2006-04-27 at 10:31 +0200, Adrian Bunk wrote:
> > > > On Thu, Apr 27, 2006 at 08:50:40AM +0200, Arjan van de Ven wrote:
> > > > > On Thu, 2006-04-27 at 09:28 +0300, Pekka J Enberg wrote:
> > > > > > On Thu, 27 Apr 2006, Nick Piggin wrote:
> > > > > > > Not to dispute your conclusions or method, but I think doing a
> > > > > > > defconfig or your personal config might be more representative
> > > > > > > of % size increase of text that will actually be executed. And
> > > > > > > that is the expensive type of text.
> > > > > > 
> > > > > > True but I was under the impression that Arjan thought we'd get text 
> > > > > > savings with GCC 4.1 by making kfree() inline.
> > > > > 
> > > > > not savings in text size, I'll settle for the same size.
> > > > >...
> > > > 
> > > > It will always be bigger since there are cases where it's unknown at 
> > > > compile time whether it will be NULL when called.
> > > 
> > > if it's "unknown" you could call into a separate kfree() which does
> > > check out of line. (sure that's a dozen bytes bigger but that is
> > > noise ;)
> > 
> > It's noise and _much work.
> 
> not if the compiler can do it. The *compiler* knows a lot (4.1 at
> least)..

But for using your suggested "separate kfree() which does check out of 
line" for not having the (otherwise unavoidable) space increast, we have 
to manually change kfree() callers.

My main question repeated:
Do you have any benchmarks where your approach brings a measurable
benefit? I wouldn't have expected kfree() being in many hotpaths.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Arjan van de Ven]

> But for using your suggested "separate kfree() which does check out of 
> line" for not having the (otherwise unavoidable) space increast, we have 
> to manually change kfree() callers.

I don't follow you. Sorry.

Re: [PATCH] likely cleanup: remove unlikely for kfree(NULL)

[Nick Piggin]

Pekka J Enberg wrote:

> On Wed, 26 Apr 2006, Arjan van de Ven wrote:
> 
>>if you deref'd the pointer it'll optimize it away (assuming a new enough
>>gcc, like 4.1)
> 
> 
> Here are the numbers for allyesconfig on my setup.

25k out of 25,000k isn't _too_ bad.

On my kernel that should be less than 5k (unless drivers/fses
have a very different ratio of size change versus core code).

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