Re: [patch] uninline init_waitqueue_*() functions

Re: [patch] uninline init_waitqueue_*() functions

[Chuck Ebbert]

In-Reply-To: <20060705102633.GA17975@elte.hu>

On Wed, 5 Jul 2006 12:26:33 +0200, Ingo Molnar wrote:

> The rough rule of thumb for inlining is that anything that is larger 
> than one C statement is probably too large for inlining. (but even 
> 1-line statements might be too fat at times)

x86-64 software optimization guide says:

 For functions that create fewer than 25 machine instructions once
 inlined, it is likely that the function call overhead is close to,
 or more than, the time spent executing the function body. In these
 cases, function inlining is recommended.

Of course you need to consider whether the code is speed-critical
to begin with.

-- 
Chuck
 "You can't read a newspaper if you can't read."  --George W. Bush

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

On Thu, 6 Jul 2006 10:23:41 +0200
Ingo Molnar <mingo@elte.hu> wrote:

> uninline more wait.h inline functions.
> 
> allyesconfig vmlinux size delta:
> 
>   text            data    bss     dec          filename
>   20736884        6073834 3075176 29885894     vmlinux.before
>   20721009        6073966 3075176 29870151     vmlinux.after

On my x86_64 typicalconfig
(http://www.zip.com.au/~akpm/linux/patches/stuff/config-x)


everything inlined:

   text    data     bss     dec     hex filename
4079169  702440  280184 5061793  4d3ca1 vmlinux

uninline init_waitqueue_head:

4076921  702456  280184 5059561  4d33e9 vmlinux

uninline init_waitqueue_head+init_waitqueue_entry

box:/usr/src/25> size vmlinux
   text    data     bss     dec     hex filename
4077017  702472  280184 5059673  4d3459 vmlinux

uninline init_waitqueue_head+init_waitqueue_entry+init_waitqueue_func_entry

box:/usr/src/25> size vmlinux
   text    data     bss     dec     hex filename
4077128  702496  280184 5059808  4d34e0 vmlinux


So we only want to uninline init_waitqueue_head().

[patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

Subject: uninline init_waitqueue_*() functions
From: Ingo Molnar <mingo@elte.hu>

uninline more wait.h inline functions.

allyesconfig vmlinux size delta:

  text            data    bss     dec          filename
  20736884        6073834 3075176 29885894     vmlinux.before
  20721009        6073966 3075176 29870151     vmlinux.after

~18 bytes per callsite, 15K of text size (~0.1%) saved.

(as an added bonus this also removes a lockdep annotation.)

Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 include/linux/wait.h |   29 +++--------------------------
 kernel/wait.c        |   26 ++++++++++++++++++++++++--
 2 files changed, 27 insertions(+), 28 deletions(-)

Index: linux/include/linux/wait.h
===================================================================
--- linux.orig/include/linux/wait.h
+++ linux/include/linux/wait.h
@@ -77,32 +77,9 @@ struct task_struct;
 #define __WAIT_BIT_KEY_INITIALIZER(word, bit)				\
 	{ .flags = word, .bit_nr = bit, }
 
-/*
- * lockdep: we want one lock-class for all waitqueue locks.
- */
-extern struct lock_class_key waitqueue_lock_key;
-
-static inline void init_waitqueue_head(wait_queue_head_t *q)
-{
-	spin_lock_init(&q->lock);
-	lockdep_set_class(&q->lock, &waitqueue_lock_key);
-	INIT_LIST_HEAD(&q->task_list);
-}
-
-static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
-{
-	q->flags = 0;
-	q->private = p;
-	q->func = default_wake_function;
-}
-
-static inline void init_waitqueue_func_entry(wait_queue_t *q,
-					wait_queue_func_t func)
-{
-	q->flags = 0;
-	q->private = NULL;
-	q->func = func;
-}
+extern void init_waitqueue_head(wait_queue_head_t *q);
+extern void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p);
+extern void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func);
 
 static inline int waitqueue_active(wait_queue_head_t *q)
 {
Index: linux/kernel/wait.c
===================================================================
--- linux.orig/kernel/wait.c
+++ linux/kernel/wait.c
@@ -10,9 +10,31 @@
 #include <linux/wait.h>
 #include <linux/hash.h>
 
-struct lock_class_key waitqueue_lock_key;
+void init_waitqueue_head(wait_queue_head_t *q)
+{
+	spin_lock_init(&q->lock);
+	INIT_LIST_HEAD(&q->task_list);
+}
+
+EXPORT_SYMBOL(init_waitqueue_head);
+
+void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
+{
+	q->flags = 0;
+	q->private = p;
+	q->func = default_wake_function;
+}
+
+EXPORT_SYMBOL(init_waitqueue_entry);
+
+void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
+{
+	q->flags = 0;
+	q->private = NULL;
+	q->func = func;
+}
 
-EXPORT_SYMBOL(waitqueue_lock_key);
+EXPORT_SYMBOL(init_waitqueue_func_entry);
 
 void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
 {

Re: [patch] uninline init_waitqueue_*() functions

[Adrian Bunk]

On Thu, Jul 06, 2006 at 12:00:09AM +0200, Ingo Molnar wrote:
> 
> * Randy.Dunlap <rdunlap@xenotime.net> wrote:
> 
> > > well, the allnoconfig thing is artificial (and the uninteresting) for a 
> > > number of reasons:
> > 
> > hm, I'd have to say that allyesconfig is also artificial and the 
> > savings numbers are somewhat uninteresting in that case too.
> 
> well the 'allyesconfig' isnt the true allyesconfig but one with most 
> debugging options disabled. It is quite close to a typical distro config 
> - hence very much relevant. (I wanted to use something that is easy to 
> reproduce.) Believe me, for large configs the savings are real.

What is the difference between "most debugging options disabled" and
"all debugging options disabled"?

> 	Ingo

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] uninline init_waitqueue_*() functions

[Linus Torvalds]

On Wed, 5 Jul 2006, Linus Torvalds wrote:
> > 
> >  c0fb6137:       c7 44 24 08 00 00 00    movl   $0x0,0x8(%esp)
> >  c0fb613e:       00
> >  c0fb613f:       c7 44 24 08 01 00 00    movl   $0x1,0x8(%esp)
> >  c0fb6146:       00
> >  c0fb6147:       c7 43 60 00 00 00 00    movl   $0x0,0x60(%ebx)
> >  c0fb614e:       8b 44 24 08             mov    0x8(%esp),%eax
> >  c0fb6152:       89 43 5c                mov    %eax,0x5c(%ebx)

Btw, this is even worse than usual.

I've seen the "create struct on the stack and copy it" before, but looking 
closer, this is doing something I haven't noticed before: that double 
assignment to the stack is _really_ strange.

I wonder why it first stores a zero to the stack location, and then 
overwrites it with the proper spinlock initialized (one).

As far as I can tell, the spinlock initializer should really end up being 
a perfectly normal "(struct spinlock_t) { 1 }", and I don't see where the 
zero comes from.

It may actually be that we're double penalized because for the lock 
"counter", we use a "volatile unsigned int", and that "0" is from some 
internal gcc "initialize all base structures to zero" to make sure that 
any padding gets zeroed, and then the "volatile" means that gcc ends up 
not optimizing it away, even though it was a totally bogus store that 
didn't even exist in the sources.

I wonder if we should remove the "volatile". There really isn't anything 
_good_ that gcc can do with it, but we've seen gcc code generation do 
stupid things before just because "volatile" seems to just disable even 
proper normal working.

[ Test-case built as time passes ]

Try compiling this example file with "-fomit-frame-pointer -O2 -S" to see 
the effect:

	horrid:
	        subl    $16, %esp
	        movl    $1, 12(%esp)
	        movl    12(%esp), %eax
	        movl    %eax, a1
	        movl    $1, b1
	        addl    $16, %esp
	        ret

	notbad:
	        movl    $1, a2
	        movl    $1, b2
	        ret


I really think that "volatile" in the kernel sources is _always_ a kernel 
bug. It certainly seems to be so in this case.

(But at least with the compiler version I'm using, I'm not seeing that 
extra unnecessary "movl $0" - I have gcc version 4.1.1 here)

Does removing just the "volatile" on the "slock" member shrink the size of 
the kernel noticeably? And do you see an extra "movl $0" in this case with 
your compiler version?

Maybe removing the volatile allows us to keep the initializer the way it 
is (although going by past behaviour, I've seen gcc generate horrible code 
in more complicated settings, so maybe the reason it works well on this 
case without the "volatile" is just that it was simple enough that gcc 
wouldn't mess up?)

		Linus
---
struct duh {
	volatile int i;
};

void horrid(void)
{
	extern struct duh a1;
	extern struct duh b1;

	a1 = (struct duh) { 1 };
	b1.i = 1;
}

struct gaah {
	int i;
};

void notbad(void)
{
	extern struct gaah a2;
	extern struct gaah b2;

	a2 = (struct gaah) { 1 };
	b2.i = 1;
}

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Linus Torvalds <torvalds@osdl.org> wrote:

> On Wed, 5 Jul 2006, Ingo Molnar wrote:
> > 
> > yeah, i'd not want to skip over some interesting and still unexplained 
> > effect either, but 35 bytes isnt all that outlandish and from everything 
> > i've seen it's a real win. Here is an actual example:
> > 
> >  c0fb6137:       c7 44 24 08 00 00 00    movl   $0x0,0x8(%esp)
> >  c0fb613e:       00
> >  c0fb613f:       c7 44 24 08 01 00 00    movl   $0x1,0x8(%esp)
> >  c0fb6146:       00
> >  c0fb6147:       c7 43 60 00 00 00 00    movl   $0x0,0x60(%ebx)
> >  c0fb614e:       8b 44 24 08             mov    0x8(%esp),%eax
> >  c0fb6152:       89 43 5c                mov    %eax,0x5c(%ebx)
> >  c0fb6155:       8d 43 64                lea    0x64(%ebx),%eax
> >  c0fb6158:       89 40 04                mov    %eax,0x4(%eax)
> >  c0fb615b:       89 43 64                mov    %eax,0x64(%ebx)
> 
> Ahh, it's _that_ old gcc problem. 
> 
> That's actually a different thing. 
> 
> Gcc is HORRIBLY BAD at doing the simple
> 
> 	some_structure = (struct somestruct) { INITIAL };
> 
> assignments. It is so ludicrously bad that it's sad. It tends to do 
> that as a local "struct somestruct" on the stack that gets 
> initialized, followed by a memcpy().
> 
> In this case, the problem appears to be the spinlock initialization 
> code.
> 
> In other words, I suspect 90% of your improvement was because you got 
> that braindamage out of line.
> 
> It would be _much_ better to just fix "spin_lock_init()" instead. That 
> would help a lot of _other_ users too, not just the waitqueue 
> initializations.
> 
> Making that a real function (and inline only for the non-debug case, 
> at which point it's just a simple and small store) would be much 
> better.

in the debug case it's already a function. (by virtue of lockdep) But 
what happens here is CONFIG_PREEMPT and break_lock and thus we get two 
fields which get initialized in that stupid way. I'll try a better 
initialization sequence. This was with gcc 4.0.1.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Randy.Dunlap <rdunlap@xenotime.net> wrote:

> > well the 'allyesconfig' isnt the true allyesconfig but one with most 
> > debugging options disabled. It is quite close to a typical distro config 
> > - hence very much relevant. (I wanted to use something that is easy to 
> > reproduce.) Believe me, for large configs the savings are real.
> 
> I would expect distros to use something close to all*mod*config (with 
> some debug options disabled).

that's the same as allyesconfig from an inlining cost POV.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Randy.Dunlap]

On Thu, 6 Jul 2006 00:00:09 +0200 Ingo Molnar wrote:

> 
> * Randy.Dunlap <rdunlap@xenotime.net> wrote:
> 
> > > well, the allnoconfig thing is artificial (and the uninteresting) for a 
> > > number of reasons:
> > 
> > hm, I'd have to say that allyesconfig is also artificial and the 
> > savings numbers are somewhat uninteresting in that case too.
> 
> well the 'allyesconfig' isnt the true allyesconfig but one with most 
> debugging options disabled. It is quite close to a typical distro config 
> - hence very much relevant. (I wanted to use something that is easy to 
> reproduce.) Believe me, for large configs the savings are real.

I would expect distros to use something close to all*mod*config
(with some debug options disabled).

---
~Randy

Re: [patch] uninline init_waitqueue_*() functions

[Linus Torvalds]

On Wed, 5 Jul 2006, Ingo Molnar wrote:
> 
> yeah, i'd not want to skip over some interesting and still unexplained 
> effect either, but 35 bytes isnt all that outlandish and from everything 
> i've seen it's a real win. Here is an actual example:
> 
>  c0fb6137:       c7 44 24 08 00 00 00    movl   $0x0,0x8(%esp)
>  c0fb613e:       00
>  c0fb613f:       c7 44 24 08 01 00 00    movl   $0x1,0x8(%esp)
>  c0fb6146:       00
>  c0fb6147:       c7 43 60 00 00 00 00    movl   $0x0,0x60(%ebx)
>  c0fb614e:       8b 44 24 08             mov    0x8(%esp),%eax
>  c0fb6152:       89 43 5c                mov    %eax,0x5c(%ebx)
>  c0fb6155:       8d 43 64                lea    0x64(%ebx),%eax
>  c0fb6158:       89 40 04                mov    %eax,0x4(%eax)
>  c0fb615b:       89 43 64                mov    %eax,0x64(%ebx)

Ahh, it's _that_ old gcc problem. 

That's actually a different thing. 

Gcc is HORRIBLY BAD at doing the simple

	some_structure = (struct somestruct) { INITIAL };

assignments. It is so ludicrously bad that it's sad. It tends to do that 
as a local "struct somestruct" on the stack that gets initialized, 
followed by a memcpy().

In this case, the problem appears to be the spinlock initialization code.

In other words, I suspect 90% of your improvement was because you got that 
braindamage out of line.

It would be _much_  better to just fix "spin_lock_init()" instead. That 
would help a lot of _other_ users too, not just the waitqueue 
initializations.

Making that a real function (and inline only for the non-debug case, at 
which point it's just a simple and small store) would be much better.

		Linus

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Randy.Dunlap <rdunlap@xenotime.net> wrote:

> > well, the allnoconfig thing is artificial (and the uninteresting) for a 
> > number of reasons:
> 
> hm, I'd have to say that allyesconfig is also artificial and the 
> savings numbers are somewhat uninteresting in that case too.

well the 'allyesconfig' isnt the true allyesconfig but one with most 
debugging options disabled. It is quite close to a typical distro config 
- hence very much relevant. (I wanted to use something that is easy to 
reproduce.) Believe me, for large configs the savings are real.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Randy.Dunlap]

On Wed, 5 Jul 2006 23:45:02 +0200 Ingo Molnar wrote:

> 
> * Linus Torvalds <torvalds@osdl.org> wrote:
> 
> > On Wed, 5 Jul 2006, Ingo Molnar wrote:
> > > 
> > > i had CONFIG_DEBUG_INFO (and UNWIND_INFO) disabled in all these build 
> > > tests.
> > 
> > Good, because I just verified: those two together will on their own 
> > increase "text size" by about 17% for me.
> > 
> > I still think Andrew is right: I don't see how an initializer that 
> > should basically be three instructions can possibly be 35 bytes larger 
> > than a function call that should be a minimum of two instructions 
> > (argument setup in %eax and the actual call - and that's totally 
> > ignoring the deleterious effects of a function call on register 
> > liveness).
> > 
> > The fact that with allnoconfig the kernel is _smaller_ (but, quite 
> > franlkly, within the noise) with the inlined version would seem to 
> > back up Andrews position that it really shouldn't matter.
> 
> well, the allnoconfig thing is artificial (and the uninteresting) for a 
> number of reasons:

hm, I'd have to say that allyesconfig is also artificial and the
savings numbers are somewhat uninteresting in that case too.


> - it has REGPARM disabled which penalizes function calls
> 
> - it's UP and hence the inlining cost of init_wait_queue_head() is 
>   significantly smaller.
> 
> - allnoconfig has smaller average function size - increasing the cost of 
>   uninlining
> 
> > So I'm left wondering why it matters for you, and what triggers it. 
> > Maybe there is some secondary issue that could show us an even more 
> > interesting optimization (or some compiler behaviour that we should 
> > try to encourage).
> 
> yeah, i'd not want to skip over some interesting and still unexplained 
> effect either, but 35 bytes isnt all that outlandish and from everything 
> i've seen it's a real win. Here is an actual example:
> 
>  c0fb6137:       c7 44 24 08 00 00 00    movl   $0x0,0x8(%esp)
>  c0fb613e:       00
>  c0fb613f:       c7 44 24 08 01 00 00    movl   $0x1,0x8(%esp)
>  c0fb6146:       00
>  c0fb6147:       c7 43 60 00 00 00 00    movl   $0x0,0x60(%ebx)
>  c0fb614e:       8b 44 24 08             mov    0x8(%esp),%eax
>  c0fb6152:       89 43 5c                mov    %eax,0x5c(%ebx)
>  c0fb6155:       8d 43 64                lea    0x64(%ebx),%eax
>  c0fb6158:       89 40 04                mov    %eax,0x4(%eax)
>  c0fb615b:       89 43 64                mov    %eax,0x64(%ebx)
> 
> versus:
> 
>  c0fb070e:       8d 43 5c                lea    0x5c(%ebx),%eax
>  c0fb0711:       e8 94 98 18 ff          call   c0139faa <init_waitqueue_head>
> 
> so 39 bytes versus 8 bytes - 31 bytes saved. It's a similar win in other 
> cases i checked too. (the only exception is for smaller functions that i 
> mentioned before: where the parameters are not pre-calculated yet so 
> there's no good integration for the function call. In that case it's 
> break even, or in some cases a 3-4 bytes loss.)

---
~Randy

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Linus Torvalds <torvalds@osdl.org> wrote:

> On Wed, 5 Jul 2006, Ingo Molnar wrote:
> > 
> > i had CONFIG_DEBUG_INFO (and UNWIND_INFO) disabled in all these build 
> > tests.
> 
> Good, because I just verified: those two together will on their own 
> increase "text size" by about 17% for me.
> 
> I still think Andrew is right: I don't see how an initializer that 
> should basically be three instructions can possibly be 35 bytes larger 
> than a function call that should be a minimum of two instructions 
> (argument setup in %eax and the actual call - and that's totally 
> ignoring the deleterious effects of a function call on register 
> liveness).
> 
> The fact that with allnoconfig the kernel is _smaller_ (but, quite 
> franlkly, within the noise) with the inlined version would seem to 
> back up Andrews position that it really shouldn't matter.

well, the allnoconfig thing is artificial (and the uninteresting) for a 
number of reasons:

- it has REGPARM disabled which penalizes function calls

- it's UP and hence the inlining cost of init_wait_queue_head() is 
  significantly smaller.

- allnoconfig has smaller average function size - increasing the cost of 
  uninlining

> So I'm left wondering why it matters for you, and what triggers it. 
> Maybe there is some secondary issue that could show us an even more 
> interesting optimization (or some compiler behaviour that we should 
> try to encourage).

yeah, i'd not want to skip over some interesting and still unexplained 
effect either, but 35 bytes isnt all that outlandish and from everything 
i've seen it's a real win. Here is an actual example:

 c0fb6137:       c7 44 24 08 00 00 00    movl   $0x0,0x8(%esp)
 c0fb613e:       00
 c0fb613f:       c7 44 24 08 01 00 00    movl   $0x1,0x8(%esp)
 c0fb6146:       00
 c0fb6147:       c7 43 60 00 00 00 00    movl   $0x0,0x60(%ebx)
 c0fb614e:       8b 44 24 08             mov    0x8(%esp),%eax
 c0fb6152:       89 43 5c                mov    %eax,0x5c(%ebx)
 c0fb6155:       8d 43 64                lea    0x64(%ebx),%eax
 c0fb6158:       89 40 04                mov    %eax,0x4(%eax)
 c0fb615b:       89 43 64                mov    %eax,0x64(%ebx)

versus:

 c0fb070e:       8d 43 5c                lea    0x5c(%ebx),%eax
 c0fb0711:       e8 94 98 18 ff          call   c0139faa <init_waitqueue_head>

so 39 bytes versus 8 bytes - 31 bytes saved. It's a similar win in other 
cases i checked too. (the only exception is for smaller functions that i 
mentioned before: where the parameters are not pre-calculated yet so 
there's no good integration for the function call. In that case it's 
break even, or in some cases a 3-4 bytes loss.)

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Linus Torvalds]

On Wed, 5 Jul 2006, Ingo Molnar wrote:
> 
> i had CONFIG_DEBUG_INFO (and UNWIND_INFO) disabled in all these build 
> tests.

Good, because I just verified: those two together will on their own 
increase "text size" by about 17% for me.

I still think Andrew is right: I don't see how an initializer that should 
basically be three instructions can possibly be 35 bytes larger than a 
function call that should be a minimum of two instructions (argument setup 
in %eax and the actual call - and that's totally ignoring the 
deleterious effects of a function call on register liveness). 

The fact that with allnoconfig the kernel is _smaller_ (but, quite 
franlkly, within the noise) with the inlined version would seem to back up 
Andrews position that it really shouldn't matter.

So I'm left wondering why it matters for you, and what triggers it. Maybe 
there is some secondary issue that could show us an even more interesting 
optimization (or some compiler behaviour that we should try to encourage).

It is, for example, entirely possible that the size reduction is REAL, but 
that it comes from some other interesting source like gcc deciding to not 
inline a function that isn't a leaf function - and that turning those 
init_waitqueue_*() functions into real function calls thus has a secondary 
effect that is the _real_ advantage.

In other words, I think the patch is fine per se, and I wouldn't mind 
applying it at all, but I think it would be good to understand _what_ 
exactly makes for the reduction in size.

In particular, if it is some secondary effect, maybe we'd be better off 
trying to aim for that secondary effect _directly_.

See?

			Linus

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> 
> * Linus Torvalds <torvalds@osdl.org> wrote:
> 
> > 
> > 
> > On Wed, 5 Jul 2006, Andrew Morton wrote:
> > > 
> > > OK, but what happened to the 35-bytes-per-callsite saving?
> > 
> > I really don't think it existed.
> > 
> > Maybe there's something else going on. In particular, I wonder if 
> > sections like the "debug_loc" fection end up being counted towards 
> > text-size? They never actually get _loaded_, but they can be 
> > absolutely enormous if CONFIG_DEBUG_INFO is enabled.
> 
> i had CONFIG_DEBUG_INFO (and UNWIND_INFO) disabled in all these build 
> tests.

hm, maybe KALLSYMS? I had that enabled - disabling it now.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Linus Torvalds <torvalds@osdl.org> wrote:

> 
> 
> On Wed, 5 Jul 2006, Andrew Morton wrote:
> > 
> > OK, but what happened to the 35-bytes-per-callsite saving?
> 
> I really don't think it existed.
> 
> Maybe there's something else going on. In particular, I wonder if 
> sections like the "debug_loc" fection end up being counted towards 
> text-size? They never actually get _loaded_, but they can be 
> absolutely enormous if CONFIG_DEBUG_INFO is enabled.

i had CONFIG_DEBUG_INFO (and UNWIND_INFO) disabled in all these build 
tests.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> Ingo Molnar <mingo@elte.hu> wrote:
> >
> > > > i also tried a config with the best size settings (disabling 
> > > > FRAME_POINTER, enabling CC_OPTIMIZE_FOR_SIZE), and this gives:
> > > > 
> > > >   text            data    bss     dec         filename
> > > >   20777768        6076042 3081864 29935674    vmlinux.x32.size.before
> > > >   20748140        6076178 3081864 29906182    vmlinux.x32.size.after
> > > > 
> > > > or a 34.8 bytes win per callsite (29K total).
> > > > 
> > > 
> > > With gcc-4.1.0 on i686, uninlining those three functions as per the 
> > > below patch _increases_ the allnoconfig vmlinux's .text from 833456 
> > > bytes to 833728.
> > 
> > that's just the effect of CONFIG_REGPARM and CONFIG_CC_OPTIMIZE_FOR_SIZE 
> > not being set in an allnoconfig. Once i set them the text size evens 
> > out:
> > 
> >  431348   60666   27276  519290   7ec7a vmlinux.x32.mini.before
> >  431359   60666   27276  519301   7ec85 vmlinux.x32.mini.after
> > 
> > compiling without CONFIG_REGPARM on i686 (if you care about text size) 
> > makes little sense. It penalizes function calls artificially.
> 
> OK, but what happened to the 35-bytes-per-callsite saving?

there are 3 effects i can see:

firstly, allnoconfig implies SMP off, so the spinlock init in 
init_waitqueue_head() is not done and it becomes a 2-instruction thing.

secondly, the savings depend on the function size. Uninlining from a 
small function (that makes use of the inlined function) can be a loss if 
the function call causes more register clobbering. For large functions 
we clobber all registers anyway so there's no extra stack saving, etc. 

the allnoconfig kernel makes use of these waitqueue ops in smaller 
kernel-core functions as well, where the uninlining is a loss. 
(sleep_on(), etc.) Furthermore, UP kernel tends to decrease function 
sizes too.

larger kernel configs include more non-core subsystems/drivers as well, 
which tend to have larger function sizes. There the uninlining win is 
larger.

there's a third, smaller effect too: gcc manages to do tail-merging of 
the init_waitqueue_head calls, in a handful of cases, further reducing 
the cost. I found no such tail-merges done for the 53 callsites in the 
allnoconfig kernel.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Linus Torvalds]

On Wed, 5 Jul 2006, Andrew Morton wrote:
> 
> OK, but what happened to the 35-bytes-per-callsite saving?

I really don't think it existed.

Maybe there's something else going on. In particular, I wonder if sections 
like the "debug_loc" fection end up being counted towards text-size? They 
never actually get _loaded_, but they can be absolutely enormous if 
CONFIG_DEBUG_INFO is enabled.

Doing "make allnoconfig" would have turned off not only modules, but also 
indirectly turned off gratuitous debug info bloat like that..

				Linus

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

Ingo Molnar <mingo@elte.hu> wrote:
>
> > > i also tried a config with the best size settings (disabling 
> > > FRAME_POINTER, enabling CC_OPTIMIZE_FOR_SIZE), and this gives:
> > > 
> > >   text            data    bss     dec         filename
> > >   20777768        6076042 3081864 29935674    vmlinux.x32.size.before
> > >   20748140        6076178 3081864 29906182    vmlinux.x32.size.after
> > > 
> > > or a 34.8 bytes win per callsite (29K total).
> > > 
> > 
> > With gcc-4.1.0 on i686, uninlining those three functions as per the 
> > below patch _increases_ the allnoconfig vmlinux's .text from 833456 
> > bytes to 833728.
> 
> that's just the effect of CONFIG_REGPARM and CONFIG_CC_OPTIMIZE_FOR_SIZE 
> not being set in an allnoconfig. Once i set them the text size evens 
> out:
> 
>  431348   60666   27276  519290   7ec7a vmlinux.x32.mini.before
>  431359   60666   27276  519301   7ec85 vmlinux.x32.mini.after
> 
> compiling without CONFIG_REGPARM on i686 (if you care about text size) 
> makes little sense. It penalizes function calls artificially.

OK, but what happened to the 35-bytes-per-callsite saving?

Sorry to keep going on about this, but your numbers seem just too big to
me, and the above confirms that, and I don't know what's happening.

It doesn't seem right that uninlining something like this:

static inline void init_waitqueue_func_entry(wait_queue_t *q,
					wait_queue_func_t func)
{
	q->flags = 0;
	q->private = NULL;
	q->func = func;
}

is going to gain us much code size benefit at all.  Let alone
runtime/codegen benefit.

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> > > >   text            data    bss     dec             filename
> > > >   21172153        6077270 3081864 30331287        vmlinux.x32.after
> > > >   21198222        6077106 3081864 30357192        vmlinux.x32.before
> > > > 
> > > > with 851 callsites that's a 30.6 bytes win per call site (total 26K) - 
> > > > still not bad at all.
> > > 
> > > and that was with CONFIG_CC_OPTIMIZE_FOR_SIZE enabled. With 
> > > optimize-for-size disabled the win goes up to 32.6 bytes (total 28K).
> > 
> > i also tried a config with the best size settings (disabling 
> > FRAME_POINTER, enabling CC_OPTIMIZE_FOR_SIZE), and this gives:
> > 
> >   text            data    bss     dec         filename
> >   20777768        6076042 3081864 29935674    vmlinux.x32.size.before
> >   20748140        6076178 3081864 29906182    vmlinux.x32.size.after
> > 
> > or a 34.8 bytes win per callsite (29K total).
> > 
> 
> With gcc-4.1.0 on i686, uninlining those three functions as per the 
> below patch _increases_ the allnoconfig vmlinux's .text from 833456 
> bytes to 833728.

that's just the effect of CONFIG_REGPARM and CONFIG_CC_OPTIMIZE_FOR_SIZE 
not being set in an allnoconfig. Once i set them the text size evens 
out:

 431348   60666   27276  519290   7ec7a vmlinux.x32.mini.before
 431359   60666   27276  519301   7ec85 vmlinux.x32.mini.after

compiling without CONFIG_REGPARM on i686 (if you care about text size) 
makes little sense. It penalizes function calls artificially.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

On Wed, 5 Jul 2006 13:46:30 +0200
Ingo Molnar <mingo@elte.hu> wrote:

> 
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> > > true. I redid my tests with both lockdep and debug-spinlocks turned off:
> > > 
> > >   text            data    bss     dec             filename
> > >   21172153        6077270 3081864 30331287        vmlinux.x32.after
> > >   21198222        6077106 3081864 30357192        vmlinux.x32.before
> > > 
> > > with 851 callsites that's a 30.6 bytes win per call site (total 26K) - 
> > > still not bad at all.
> > 
> > and that was with CONFIG_CC_OPTIMIZE_FOR_SIZE enabled. With 
> > optimize-for-size disabled the win goes up to 32.6 bytes (total 28K).
> 
> i also tried a config with the best size settings (disabling 
> FRAME_POINTER, enabling CC_OPTIMIZE_FOR_SIZE), and this gives:
> 
>   text            data    bss     dec         filename
>   20777768        6076042 3081864 29935674    vmlinux.x32.size.before
>   20748140        6076178 3081864 29906182    vmlinux.x32.size.after
> 
> or a 34.8 bytes win per callsite (29K total).
> 

With gcc-4.1.0 on i686, uninlining those three functions as per the below
patch _increases_ the allnoconfig vmlinux's .text from 833456 bytes to
833728.

Which maybe means it's still worth doing, because a lot of people run with
some debug options nowadays.

But it's a more believable result, and an inexplicable one given your
numbers.  Something's up.



 include/linux/wait.h |   24 +++---------------------
 kernel/fork.c        |   21 +++++++++++++++++++++
 2 files changed, 24 insertions(+), 21 deletions(-)

diff -puN include/linux/wait.h~a include/linux/wait.h
--- a/include/linux/wait.h~a
+++ a/include/linux/wait.h
@@ -82,27 +82,9 @@ struct task_struct;
  */
 extern struct lock_class_key waitqueue_lock_key;
 
-static inline void init_waitqueue_head(wait_queue_head_t *q)
-{
-	spin_lock_init(&q->lock);
-	lockdep_set_class(&q->lock, &waitqueue_lock_key);
-	INIT_LIST_HEAD(&q->task_list);
-}
-
-static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
-{
-	q->flags = 0;
-	q->private = p;
-	q->func = default_wake_function;
-}
-
-static inline void init_waitqueue_func_entry(wait_queue_t *q,
-					wait_queue_func_t func)
-{
-	q->flags = 0;
-	q->private = NULL;
-	q->func = func;
-}
+void init_waitqueue_head(wait_queue_head_t *q);
+void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p);
+void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func);
 
 static inline int waitqueue_active(wait_queue_head_t *q)
 {
diff -puN fs/aio.c~a fs/aio.c
diff -puN kernel/fork.c~a kernel/fork.c
--- a/kernel/fork.c~a
+++ a/kernel/fork.c
@@ -153,6 +153,27 @@ void __init fork_init(unsigned long memp
 		init_task.signal->rlim[RLIMIT_NPROC];
 }
 
+void init_waitqueue_head(wait_queue_head_t *q)
+{
+	spin_lock_init(&q->lock);
+	lockdep_set_class(&q->lock, &waitqueue_lock_key);
+	INIT_LIST_HEAD(&q->task_list);
+}
+
+void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
+{
+	q->flags = 0;
+	q->private = p;
+	q->func = default_wake_function;
+}
+
+void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
+{
+	q->flags = 0;
+	q->private = NULL;
+	q->func = func;
+}
+
 static struct task_struct *dup_task_struct(struct task_struct *orig)
 {
 	struct task_struct *tsk;
_

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> > true. I redid my tests with both lockdep and debug-spinlocks turned off:
> > 
> >   text            data    bss     dec             filename
> >   21172153        6077270 3081864 30331287        vmlinux.x32.after
> >   21198222        6077106 3081864 30357192        vmlinux.x32.before
> > 
> > with 851 callsites that's a 30.6 bytes win per call site (total 26K) - 
> > still not bad at all.
> 
> and that was with CONFIG_CC_OPTIMIZE_FOR_SIZE enabled. With 
> optimize-for-size disabled the win goes up to 32.6 bytes (total 28K).

i also tried a config with the best size settings (disabling 
FRAME_POINTER, enabling CC_OPTIMIZE_FOR_SIZE), and this gives:

  text            data    bss     dec         filename
  20777768        6076042 3081864 29935674    vmlinux.x32.size.before
  20748140        6076178 3081864 29906182    vmlinux.x32.size.after

or a 34.8 bytes win per callsite (29K total).

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> * Andrew Morton <akpm@osdl.org> wrote:
> 
> > > > shrinks fs/select.o by eight bytes.  (More than I expected).  So 
> > > > it does appear to be a space win, but a pretty slim one.
> > > 
> > > there are 855 calls to these functions in the allyesconfig vmlinux i 
> > > did, and i measured a combined size reduction of 34791 bytes. That 
> > > averages to a 40 bytes win per call site. (on i386.)
> > > 
> > 
> > Yes, but that lumps all three together.  init_waitqueue_head() is 
> > obviously the porky one.  And it's porkier with CONFIG_DEBUG_SPINLOCK 
> > and CONFIG_LOCKDEP, which isn't the case to optimise for.
> 
> true. I redid my tests with both lockdep and debug-spinlocks turned off:
> 
>   text            data    bss     dec             filename
>   21172153        6077270 3081864 30331287        vmlinux.x32.after
>   21198222        6077106 3081864 30357192        vmlinux.x32.before
> 
> with 851 callsites that's a 30.6 bytes win per call site (total 26K) - 
> still not bad at all.

and that was with CONFIG_CC_OPTIMIZE_FOR_SIZE enabled. With 
optimize-for-size disabled the win goes up to 32.6 bytes (total 28K).

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> > > > shrinks fs/select.o by eight bytes.  (More than I expected).  So 
> > > > it does appear to be a space win, but a pretty slim one.
> > > 
> > > there are 855 calls to these functions in the allyesconfig vmlinux 
> > > i did, and i measured a combined size reduction of 34791 bytes. 
> > > That averages to a 40 bytes win per call site. (on i386.)
> > 
> > And more importantly it's a function that's called in slowpathes per 
> > definition.  So saving text sounds like a good idea, how minimal it 
> > may be.
> 
> Well yes - as I said, it's a net win.  But 31 bytes per callsite seems 
> weird and makes one wonder what's going on.

that's how big those instructions are roughly, while with the function 
call we likely have those parameters in registers already, mitigating 
some of the function-call overhead. (these tests were done with REGPARM 
turned on)

some of the assignments are also indirect, necessiating further loads, 
such as:

    INIT_LIST_HEAD(&q->task_list);

i roughly expected a net uninlining win of roughly this magnitude.

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

On Wed, 5 Jul 2006 03:44:41 -0700
Andrew Morton <akpm@osdl.org> wrote:

> On Wed, 5 Jul 2006 11:37:56 +0100
> Christoph Hellwig <hch@infradead.org> wrote:
> 
> > On Wed, Jul 05, 2006 at 11:32:59AM +0200, Ingo Molnar wrote:
> > > 
> > > * Andrew Morton <akpm@osdl.org> wrote:
> > > 
> > > > shrinks fs/select.o by eight bytes.  (More than I expected).  So it 
> > > > does appear to be a space win, but a pretty slim one.
> > > 
> > > there are 855 calls to these functions in the allyesconfig vmlinux i 
> > > did, and i measured a combined size reduction of 34791 bytes. That 
> > > averages to a 40 bytes win per call site. (on i386.)
> > 
> > And more importantly it's a function that's called in slowpathes per
> > definition.  So saving text sounds like a good idea, how minimal it
> > may be.
> > 
> 
> Well yes - as I said, it's a net win.  But 31 bytes per callsite seems
> weird and makes one wonder what's going on.

That's 31 bytes *savings*.  After taking the hit of setting up for and
performing the function call.  Which implies more than 40 bytes per callsite
with the inlined functions.

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

On Wed, 5 Jul 2006 11:37:56 +0100
Christoph Hellwig <hch@infradead.org> wrote:

> On Wed, Jul 05, 2006 at 11:32:59AM +0200, Ingo Molnar wrote:
> > 
> > * Andrew Morton <akpm@osdl.org> wrote:
> > 
> > > shrinks fs/select.o by eight bytes.  (More than I expected).  So it 
> > > does appear to be a space win, but a pretty slim one.
> > 
> > there are 855 calls to these functions in the allyesconfig vmlinux i 
> > did, and i measured a combined size reduction of 34791 bytes. That 
> > averages to a 40 bytes win per call site. (on i386.)
> 
> And more importantly it's a function that's called in slowpathes per
> definition.  So saving text sounds like a good idea, how minimal it
> may be.
> 

Well yes - as I said, it's a net win.  But 31 bytes per callsite seems
weird and makes one wonder what's going on.

Re: [patch] uninline init_waitqueue_*() functions

[Christoph Hellwig]

On Wed, Jul 05, 2006 at 11:32:59AM +0200, Ingo Molnar wrote:
> 
> * Andrew Morton <akpm@osdl.org> wrote:
> 
> > shrinks fs/select.o by eight bytes.  (More than I expected).  So it 
> > does appear to be a space win, but a pretty slim one.
> 
> there are 855 calls to these functions in the allyesconfig vmlinux i 
> did, and i measured a combined size reduction of 34791 bytes. That 
> averages to a 40 bytes win per call site. (on i386.)

And more importantly it's a function that's called in slowpathes per
definition.  So saving text sounds like a good idea, how minimal it
may be.

> 
> 	Ingo
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
---end quoted text---

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> > > shrinks fs/select.o by eight bytes.  (More than I expected).  So 
> > > it does appear to be a space win, but a pretty slim one.
> > 
> > there are 855 calls to these functions in the allyesconfig vmlinux i 
> > did, and i measured a combined size reduction of 34791 bytes. That 
> > averages to a 40 bytes win per call site. (on i386.)
> > 
> 
> Yes, but that lumps all three together.  init_waitqueue_head() is 
> obviously the porky one.  And it's porkier with CONFIG_DEBUG_SPINLOCK 
> and CONFIG_LOCKDEP, which isn't the case to optimise for.

true. I redid my tests with both lockdep and debug-spinlocks turned off:

  text            data    bss     dec             filename
  21172153        6077270 3081864 30331287        vmlinux.x32.after
  21198222        6077106 3081864 30357192        vmlinux.x32.before

with 851 callsites that's a 30.6 bytes win per call site (total 26K) - 
still not bad at all.

it's a win even on 64-bit:

  text            data    bss     dec             filename
  21237025        6997266 3327600 31561891        vmlinux.x64.after
  21252773        6997090 3327600 31577463        vmlinux.x64.before

with 755 callsites that's still a 20.8 bytes win per call site (total 
15K).

> With the debug options turned off, even init_waitqueue_head() becomes 
> just three assignments, similar to init_waitqueue_entry() and 
> init_waitqueue_func_entry().  All pretty marginal.

but three assignments could mean 3 offsets embedded in the instructions. 
(for init_waitqueue_entry we also embedd the address of 
default_wake_function) Even 3 assignments can add up to a footprint that 
is far from marginal.

The rough rule of thumb for inlining is that anything that is larger 
than one C statement is probably too large for inlining. (but even 
1-line statements might be too fat at times)

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

On Wed, 5 Jul 2006 11:32:59 +0200
Ingo Molnar <mingo@elte.hu> wrote:

> 
> * Andrew Morton <akpm@osdl.org> wrote:
> 
> > shrinks fs/select.o by eight bytes.  (More than I expected).  So it 
> > does appear to be a space win, but a pretty slim one.
> 
> there are 855 calls to these functions in the allyesconfig vmlinux i 
> did, and i measured a combined size reduction of 34791 bytes. That 
> averages to a 40 bytes win per call site. (on i386.)
> 

Yes, but that lumps all three together.  init_waitqueue_head() is obviously
the porky one.  And it's porkier with CONFIG_DEBUG_SPINLOCK and
CONFIG_LOCKDEP, which isn't the case to optimise for.

With the debug options turned off, even init_waitqueue_head() becomes just
three assignments, similar to init_waitqueue_entry() and
init_waitqueue_func_entry().  All pretty marginal.

Re: [patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> shrinks fs/select.o by eight bytes.  (More than I expected).  So it 
> does appear to be a space win, but a pretty slim one.

there are 855 calls to these functions in the allyesconfig vmlinux i 
did, and i measured a combined size reduction of 34791 bytes. That 
averages to a 40 bytes win per call site. (on i386.)

	Ingo

Re: [patch] uninline init_waitqueue_*() functions

[Andrew Morton]

On Wed, 5 Jul 2006 10:49:14 +0200
Ingo Molnar <mingo@elte.hu> wrote:

> Subject: uninline init_waitqueue_*() functions
> From: Ingo Molnar <mingo@elte.hu>
> 
> some wait.h inlines are way too large: init_waitqueue_entry() and
> init_waitqueue_func_entry() generate 20-30 bytes of inlined code
> per call site, and init_waitqueue_head() is 30-40 bytes (on x86).

20-30 bytes for

> -static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
> -{
> -	q->flags = 0;
> -	q->private = p;
> -	q->func = default_wake_function;
> -}

seem too much.

This:

--- a/fs/select.c~a
+++ a/fs/select.c
@@ -129,6 +129,7 @@ static void __pollwait(struct file *filp
 	entry->filp = filp;
 	entry->wait_address = wait_address;
 	init_waitqueue_entry(&entry->wait, current);
+	init_waitqueue_entry(&entry->wait, current);
 	add_wait_queue(wait_address,&entry->wait);
 }
 

Increases fs/select.o by only seven bytes.


And this:

diff -puN fs/select.c~a fs/select.c
--- a/fs/select.c~a
+++ a/fs/select.c
@@ -128,7 +128,7 @@ static void __pollwait(struct file *filp
 	get_file(filp);
 	entry->filp = filp;
 	entry->wait_address = wait_address;
-	init_waitqueue_entry(&entry->wait, current);
+	xxinit_waitqueue_entry(&entry->wait, current);
 	add_wait_queue(wait_address,&entry->wait);
 }
 
_

shrinks fs/select.o by eight bytes.  (More than I expected).  So it does
appear to be a space win, but a pretty slim one.

[patch] uninline init_waitqueue_*() functions

[Ingo Molnar]

Subject: uninline init_waitqueue_*() functions
From: Ingo Molnar <mingo@elte.hu>

some wait.h inlines are way too large: init_waitqueue_entry() and
init_waitqueue_func_entry() generate 20-30 bytes of inlined code
per call site, and init_waitqueue_head() is 30-40 bytes (on x86).

allyesconfig vmlinux size delta:

  text            data    bss     dec          filename
  21459355        6286210 4520408 32265973     vmlinux.before
  21424564        6281246 4516912 32222722     vmlinux.after

So 34K (0.16%) of kernel text saved. Not too bad.

(as an added bonus this also removes a lockdep annotation.)

Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 include/linux/wait.h |   29 +++--------------------------
 kernel/wait.c        |   26 ++++++++++++++++++++++++--
 2 files changed, 27 insertions(+), 28 deletions(-)

Index: linux/include/linux/wait.h
===================================================================
--- linux.orig/include/linux/wait.h
+++ linux/include/linux/wait.h
@@ -77,32 +77,9 @@ struct task_struct;
 #define __WAIT_BIT_KEY_INITIALIZER(word, bit)				\
 	{ .flags = word, .bit_nr = bit, }
 
-/*
- * lockdep: we want one lock-class for all waitqueue locks.
- */
-extern struct lock_class_key waitqueue_lock_key;
-
-static inline void init_waitqueue_head(wait_queue_head_t *q)
-{
-	spin_lock_init(&q->lock);
-	lockdep_set_class(&q->lock, &waitqueue_lock_key);
-	INIT_LIST_HEAD(&q->task_list);
-}
-
-static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
-{
-	q->flags = 0;
-	q->private = p;
-	q->func = default_wake_function;
-}
-
-static inline void init_waitqueue_func_entry(wait_queue_t *q,
-					wait_queue_func_t func)
-{
-	q->flags = 0;
-	q->private = NULL;
-	q->func = func;
-}
+extern void init_waitqueue_head(wait_queue_head_t *q);
+extern void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p);
+extern void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func);
 
 static inline int waitqueue_active(wait_queue_head_t *q)
 {
Index: linux/kernel/wait.c
===================================================================
--- linux.orig/kernel/wait.c
+++ linux/kernel/wait.c
@@ -10,9 +10,31 @@
 #include <linux/wait.h>
 #include <linux/hash.h>
 
-struct lock_class_key waitqueue_lock_key;
+void init_waitqueue_head(wait_queue_head_t *q)
+{
+	spin_lock_init(&q->lock);
+	INIT_LIST_HEAD(&q->task_list);
+}
+
+EXPORT_SYMBOL(init_waitqueue_head);
+
+void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
+{
+	q->flags = 0;
+	q->private = p;
+	q->func = default_wake_function;
+}
+
+EXPORT_SYMBOL(init_waitqueue_entry);
+
+void init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
+{
+	q->flags = 0;
+	q->private = NULL;
+	q->func = func;
+}
 
-EXPORT_SYMBOL(waitqueue_lock_key);
+EXPORT_SYMBOL(init_waitqueue_func_entry);
 
 void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
 {