Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Jeff Garzik]

Linux Kernel Mailing List wrote:
> commit e6022603b9aa7d61d20b392e69edcdbbc1789969
> tree f94b059e312ea7b2f3c4d0b01939e868ed525fb0
> parent 304c4c841a31c780a45d65e389b07706babf5d36
> author Andrew Morton <akpm@osdl.org> Fri, 23 Jun 2006 16:05:32 -0700
> committer Linus Torvalds <torvalds@g5.osdl.org> Fri, 23 Jun 2006 21:43:05 -0700
> 
> [PATCH] ext3_clear_inode(): avoid kfree(NULL)
> 
> Steven Rostedt <rostedt@goodmis.org> points out that `rsv' here is usually
> NULL, so we should avoid calling kfree().
> 
> Also, fix up some nearby whitespace damage.
> 
> Signed-off-by: Andrew Morton <akpm@osdl.org>
> Signed-off-by: Linus Torvalds <torvalds@osdl.org>

Dumb question...  why?  kfree(NULL) has always been explicitly allowed.

	Jeff

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Andrew Morton]

On Fri, 23 Jun 2006 14:51:03 -0400
Jeff Garzik <jeff@garzik.org> wrote:

> Linux Kernel Mailing List wrote:
> > commit e6022603b9aa7d61d20b392e69edcdbbc1789969
> > tree f94b059e312ea7b2f3c4d0b01939e868ed525fb0
> > parent 304c4c841a31c780a45d65e389b07706babf5d36
> > author Andrew Morton <akpm@osdl.org> Fri, 23 Jun 2006 16:05:32 -0700
> > committer Linus Torvalds <torvalds@g5.osdl.org> Fri, 23 Jun 2006 21:43:05 -0700
> > 
> > [PATCH] ext3_clear_inode(): avoid kfree(NULL)
> > 
> > Steven Rostedt <rostedt@goodmis.org> points out that `rsv' here is usually
> > NULL, so we should avoid calling kfree().
> > 
> > Also, fix up some nearby whitespace damage.
> > 
> > Signed-off-by: Andrew Morton <akpm@osdl.org>
> > Signed-off-by: Linus Torvalds <torvalds@osdl.org>
> 
> Dumb question...  why?  kfree(NULL) has always been explicitly allowed.
> 

Because at that callsite, NULL is the common case.  We avoid a do-nothing
function call most of the time.  It's a nano-optimisation.

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Arjan van de Ven]

> 
> Because at that callsite, NULL is the common case.  We avoid a do-nothing
> function call most of the time.  It's a nano-optimisation.

but a function call is basically free, while an if () is not... even
with unlikely()...

sounds like a misoptimization to me.

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Steven Rostedt]

On Sat, 24 Jun 2006, Arjan van de Ven wrote:

>
> >
> > Because at that callsite, NULL is the common case.  We avoid a do-nothing
> > function call most of the time.  It's a nano-optimisation.
>
> but a function call is basically free, while an if () is not... even
> with unlikely()...
>
> sounds like a misoptimization to me.
>

How is a function call free when an if is not?  Especially if that
function does the exact same if?

The problem is that in these cases the pointer is NULL several thousands
of times for every time it is not NULL (if ever).  The non-NULL case is
where an error occurred or something very special.  So I don't see how
the if here is a problem?

-- Steve

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Arjan van de Ven]

On Sat, 2006-06-24 at 08:20 -0400, Steven Rostedt wrote:
> On Sat, 24 Jun 2006, Arjan van de Ven wrote:
> 
> >
> > >
> > > Because at that callsite, NULL is the common case.  We avoid a do-nothing
> > > function call most of the time.  It's a nano-optimisation.
> >
> > but a function call is basically free, while an if () is not... even
> > with unlikely()...
> >
> > sounds like a misoptimization to me.
> >
> 
> How is a function call free when an if is not? 

in general, a function call is 100% predictable without any real control
flow dependencies for the processor, and thus there is no real issue in
the execution pipeline. An if is a conditional branch, which breaks up
the execution pipeline if mispredicted...

>  Especially if that
> function does the exact same if?

sure; 

but to call this code an optimization ... it's just extra code.

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Steven Rostedt]

On Sat, 24 Jun 2006, Arjan van de Ven wrote:

> On Sat, 2006-06-24 at 08:20 -0400, Steven Rostedt wrote:
> > On Sat, 24 Jun 2006, Arjan van de Ven wrote:
> >
> > >
> > > >
> > > > Because at that callsite, NULL is the common case.  We avoid a do-nothing
> > > > function call most of the time.  It's a nano-optimisation.
> > >
> > > but a function call is basically free, while an if () is not... even
> > > with unlikely()...
> > >
> > > sounds like a misoptimization to me.
> > >
> >
> > How is a function call free when an if is not?
>
> in general, a function call is 100% predictable without any real control
> flow dependencies for the processor, and thus there is no real issue in
> the execution pipeline. An if is a conditional branch, which breaks up
> the execution pipeline if mispredicted...

But doesn't the unlikely help the prediction?  Like I stated, the if may
never succeed.

-- Steve

>
> >  Especially if that
> > function does the exact same if?
>
> sure;
>
> but to call this code an optimization ... it's just extra code.
>
>
>

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Arjan van de Ven]

On Sat, 2006-06-24 at 08:33 -0400, Steven Rostedt wrote:
> On Sat, 24 Jun 2006, Arjan van de Ven wrote:
> 
> > On Sat, 2006-06-24 at 08:20 -0400, Steven Rostedt wrote:
> > > On Sat, 24 Jun 2006, Arjan van de Ven wrote:
> > >
> > > >
> > > > >
> > > > > Because at that callsite, NULL is the common case.  We avoid a do-nothing
> > > > > function call most of the time.  It's a nano-optimisation.
> > > >
> > > > but a function call is basically free, while an if () is not... even
> > > > with unlikely()...
> > > >
> > > > sounds like a misoptimization to me.
> > > >
> > >
> > > How is a function call free when an if is not?
> >
> > in general, a function call is 100% predictable without any real control
> > flow dependencies for the processor, and thus there is no real issue in
> > the execution pipeline. An if is a conditional branch, which breaks up
> > the execution pipeline if mispredicted...
> 
> But doesn't the unlikely help the prediction? 

nope none at all, at least not on x86/x86-64.
(in fact there is no way to help the prediction on those architectures
that actually works)

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Steven Rostedt]

On Sat, 24 Jun 2006, Arjan van de Ven wrote:

> > >
> > > in general, a function call is 100% predictable without any real control
> > > flow dependencies for the processor, and thus there is no real issue in
> > > the execution pipeline. An if is a conditional branch, which breaks up
> > > the execution pipeline if mispredicted...
> >
> > But doesn't the unlikely help the prediction?
>
> nope none at all, at least not on x86/x86-64.
> (in fact there is no way to help the prediction on those architectures
> that actually works)
>

But doesn't gcc optimize it. That is, it puts the code in the if block
as the jump. So if you never take the if, the pipeline is not hurt.

-- Steve

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Arjan van de Ven]

On Sat, 2006-06-24 at 14:46 +0200, Arjan van de Ven wrote:
> On Sat, 2006-06-24 at 08:33 -0400, Steven Rostedt wrote:
> > On Sat, 24 Jun 2006, Arjan van de Ven wrote:
> > 
> > > On Sat, 2006-06-24 at 08:20 -0400, Steven Rostedt wrote:
> > > > On Sat, 24 Jun 2006, Arjan van de Ven wrote:
> > > >
> > > > >
> > > > > >
> > > > > > Because at that callsite, NULL is the common case.  We avoid a do-nothing
> > > > > > function call most of the time.  It's a nano-optimisation.
> > > > >
> > > > > but a function call is basically free, while an if () is not... even
> > > > > with unlikely()...
> > > > >
> > > > > sounds like a misoptimization to me.
> > > > >
> > > >
> > > > How is a function call free when an if is not?
> > >
> > > in general, a function call is 100% predictable without any real control
> > > flow dependencies for the processor, and thus there is no real issue in
> > > the execution pipeline. An if is a conditional branch, which breaks up
> > > the execution pipeline if mispredicted...
> > 
> > But doesn't the unlikely help the prediction? 
> 
> nope none at all, at least not on x86/x86-64.
> (in fact there is no way to help the prediction on those architectures
> that actually works)

ok that's not entirely accurate, there's some basic heuristics you can
tweak to; eg often the assumption is "if you jump backwards the branch
is taken" and stuff like that, but that's generally useful in loops, not
so much in if () statements.... since for if () both your branches are
forward.

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Steven Rostedt]

On Sat, 24 Jun 2006, Arjan van de Ven wrote:

> > >
> > > But doesn't the unlikely help the prediction?
> >
> > nope none at all, at least not on x86/x86-64.
> > (in fact there is no way to help the prediction on those architectures
> > that actually works)
>
> ok that's not entirely accurate, there's some basic heuristics you can
> tweak to; eg often the assumption is "if you jump backwards the branch
> is taken" and stuff like that, but that's generally useful in loops, not
> so much in if () statements.... since for if () both your branches are
> forward.
>

I just tried this code:

--- code ---
extern void marker1(void);
extern void marker2(void);

extern void callme(void *p);

#define unlikely(x)     __builtin_expect(!!(x), 0)

void predictme(void *t)
{
        marker1();
        if (unlikely (t))
                callme(t);
        marker2();

        return;
}
--- end code ---


Compiled it like:

 $ gcc -O2 -c predict.c

Then did objdump and got this:

--- objdump ---
00000000 <predictme>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   53                      push   %ebx
   4:   83 ec 04                sub    $0x4,%esp
   7:   8b 5d 08                mov    0x8(%ebp),%ebx
   a:   e8 fc ff ff ff          call   b <predictme+0xb>
                        b: R_386_PC32   marker1
   f:   85 db                   test   %ebx,%ebx
  11:   75 08                   jne    1b <predictme+0x1b>
  13:   58                      pop    %eax
  14:   5b                      pop    %ebx
  15:   5d                      pop    %ebp
  16:   e9 fc ff ff ff          jmp    17 <predictme+0x17>
                        17: R_386_PC32  marker2
  1b:   89 1c 24                mov    %ebx,(%esp)
  1e:   e8 fc ff ff ff          call   1f <predictme+0x1f>
                        1f: R_386_PC32  callme
  23:   eb ee                   jmp    13 <predictme+0x13>
--- end objdump --


The jne is expected to fail, so we will always continue to 0x13. Now is
this a problem with x86/x86_64?


BTW: taking out the unlikely I get this:

--- objdump ---
00000000 <predictme>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   53                      push   %ebx
   4:   83 ec 04                sub    $0x4,%esp
   7:   8b 5d 08                mov    0x8(%ebp),%ebx
   a:   e8 fc ff ff ff          call   b <predictme+0xb>
                        b: R_386_PC32   marker1
   f:   85 db                   test   %ebx,%ebx
  11:   74 08                   je     1b <predictme+0x1b>
  13:   89 1c 24                mov    %ebx,(%esp)
  16:   e8 fc ff ff ff          call   17 <predictme+0x17>
                        17: R_386_PC32  callme
  1b:   58                      pop    %eax
  1c:   5b                      pop    %ebx
  1d:   5d                      pop    %ebp
  1e:   e9 fc ff ff ff          jmp    1f <predictme+0x1f>
                        1f: R_386_PC32  marker2
--- end objdump ---

So it seems that gcc tries to keep the likely's from jumping.

-- Steve

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Arjan van de Ven]

> 
> The jne is expected to fail, so we will always continue to 0x13. Now is
> this a problem with x86/x86_64?

I'm not saying there is a problem; likely/unlikely do have an effect for
sure, it's just not a "make it free" thing....

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Nick Piggin]

Arjan van de Ven wrote:
>>The jne is expected to fail, so we will always continue to 0x13. Now is
>>this a problem with x86/x86_64?
> 
> 
> I'm not saying there is a problem; likely/unlikely do have an effect for
> sure, it's just not a "make it free" thing....

On x86 I think the main saving is the icache one. However I guess
gcc would try to align with the branch prediction behaviour for
unknown branches too.

The microoptimisation is that the call avoids the unlikely branch
in kfree. Maybe for x86 this isn't going to matter, but for some
architectures in might.

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

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Jeremy Fitzhardinge]

Arjan van de Ven wrote:
> nope none at all, at least not on x86/x86-64.
> (in fact there is no way to help the prediction on those architectures
> that actually works)
>   
The branch prediction hint prefixes (2e & 3e) don't work?

    J

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Arjan van de Ven]

On Sat, 2006-06-24 at 09:49 -0700, Jeremy Fitzhardinge wrote:
> Arjan van de Ven wrote:
> > nope none at all, at least not on x86/x86-64.
> > (in fact there is no way to help the prediction on those architectures
> > that actually works)
> >   
> The branch prediction hint prefixes (2e & 3e) don't work?

last I read they are both actively discouraged and ignored by all
"current" processors from both AMD and Intel. (see the optimization
guide PDF that Intel publishes)
Note: this is based on me reading public documentation, not on me
reading Intel internal stuff or asking the relevant chip architects, so
don't take this as a fully authoritative statement.

Re: [PATCH] ext3_clear_inode(): avoid kfree(NULL)

[Pekka Enberg]

On 6/24/06, Arjan van de Ven <arjan@infradead.org> wrote:
> >
> > Because at that callsite, NULL is the common case.  We avoid a do-nothing
> > function call most of the time.  It's a nano-optimisation.
>
> but a function call is basically free, while an if () is not... even
> with unlikely()...

Yeah, but the called function has an if statement too...

                                   Pekka