Messages in this thread Patch in this message | | | Date | Wed, 8 Mar 2017 09:37:20 +0100 | From | Ingo Molnar <> | Subject | [RFC PATCH] sched/wait: Introduce new, more compact wait_event*() primitives |
| |
* Linus Torvalds <torvalds@linux-foundation.org> wrote:
> On Fri, Mar 3, 2017 at 12:13 PM, Linus Torvalds > <torvalds@linux-foundation.org> wrote: > > > > The fact that you can include <linux/wait.h>, and then cannot use the > > wait event functions because you're missing "signal_pending()" is > > complete garbage. This needs to be fixed. > > Here's a (totally untested) patch that tries to do exactly that.
Sorry, I didn't forget about this problem, I worked on it over the weekend, it just turned out to be a lot more complex than I expected.
I took a more radical approach than you, and here's the patches I have so far:
0c32c5717beb sched/wait: Introduce new, more compact wait_event*() primitives 67b01ca3fda2 sched/wait: Disambiguate wq_entry->task_list and wq_head->task_list naming 48af925509bc sched/wait: Move bit_wait_table[] and related functionality from sched/core.c to sched/wait_bit.c bc151d1fd3e9 sched/wait: Split out the wait_bit*() APIs from <linux/wait.h> into <linux/wait_bit.h> b2d294b5824c sched/wait: Re-adjust macro line continuation backslashes in <linux/wait.h> e9bbf53778c2 sched/wait: Improve the bit-wait API parameter names in the API function prototypes 6a6899db8e5a sched/wait: Standardize wait_bit_queue naming 8e060b6e033c sched/wait: Standardize 'struct wait_bit_queue' wait-queue entry field name 139793f6ac6f sched/wait: Standardize internal naming of wait-queue heads bb393b1a7e11 sched/wait: Standardize internal naming of wait-queue entries 28376289373c sched/wait: Rename wait_queue_t => wait_queue_entry_t
You can find the latest (WIP, frequently rebased) version in:
git git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git WIP.sched/core
The first 10 patches reshape the waitqueue code to be more hackable (to me!), because I kept bumping into confusing names all the time, but the real change you'd be most interested in is, in an RFC (to be rebased!) form, the following one:
0c32c5717beb sched/wait: Introduce new, more compact wait_event*() primitives
I've attached that patch below as well.
The idea is to allow call sites to supply the 'condition' function as free-form C code, while pushing everything else into non-macro form: there's a 'struct wait_event_state' on stack, and a state machine. The waiting logic is converted from procedural form to a state machine, because we have to call out into the 'condition' code in different circumstances.
It's a pretty weird construct, but it works I think, and has quite a few advantages (and a few disadvantages ...).
There's a lot of caveats with this RFC patch:
- Not signed off, I'm not 100% sure it's fully correct yet, but superficial testing suggests that it appears to boot - but PeterZ saw a boot hang on a server machine ...
- NOTE: the v1/v2 structure is just a hack to make it easier to test - the final version wouldn't have such a construct.
- Peter doesn't like the bool's in the struct - we could use char instead.
- It needs a proper state machine diagram and more documentation - this is just a very quick prototype to see whether the concept has any chance of working.
The main advantage is the much reduced call site overhead, plus the fact that we move much of the logic into the .c space.
Right now event_wait() [which is in fact the smallest wait-event primitive!] generates this humunguous amount of inlined code on x86-64 defconfig:
long test_flag;
DECLARE_WAIT_QUEUE_HEAD(test_waitqueue_head);
void test_function(void) { wait_event(test_waitqueue_head, test_flag != 0); }
00000000000084e0 <test_function>: 84e0: 55 push %rbp 84e1: 48 89 e5 mov %rsp,%rbp 84e4: 48 83 ec 28 sub $0x28,%rsp
84e8: 65 8b 05 00 00 00 00 mov %gs:0x0(%rip),%eax # 84ef <test_function+0xf> 84ef: 85 c0 test %eax,%eax 84f1: 74 4f je 8542 <test_function+0x62> 84f3: 48 83 3d 00 00 00 00 cmpq $0x0,0x0(%rip) # 84fb <test_function+0x1b> 84fa: 00 84fb: 74 02 je 84ff <test_function+0x1f>
84fd: c9 leaveq 84fe: c3 retq
84ff: 48 8d 7d d8 lea -0x28(%rbp),%rdi 8503: 31 f6 xor %esi,%esi 8505: e8 00 00 00 00 callq 850a <test_function+0x2a> 850a: eb 05 jmp 8511 <test_function+0x31> 850c: e8 00 00 00 00 callq 8511 <test_function+0x31> 8511: 48 8d 75 d8 lea -0x28(%rbp),%rsi 8515: ba 02 00 00 00 mov $0x2,%edx 851a: 48 c7 c7 00 00 00 00 mov $0x0,%rdi 8521: e8 00 00 00 00 callq 8526 <test_function+0x46> 8526: 48 83 3d 00 00 00 00 cmpq $0x0,0x0(%rip) # 852e <test_function+0x4e> 852d: 00 852e: 74 dc je 850c <test_function+0x2c> 8530: 48 8d 75 d8 lea -0x28(%rbp),%rsi 8534: 48 c7 c7 00 00 00 00 mov $0x0,%rdi 853b: e8 00 00 00 00 callq 8540 <test_function+0x60> 8540: c9 leaveq 8541: c3 retq 8542: e8 00 00 00 00 callq 8547 <test_function+0x67> 8547: eb aa jmp 84f3 <test_function+0x13>
That's 5 inlined function calls (!).
Note that it's even worse with some of the more complex wait_event*() constructs, for example the popular wait_event_interruptible_timeout() API generates this much code per call site:
00000000000084d0 <test_function_timeout>: 84d0: 55 push %rbp 84d1: 48 89 e5 mov %rsp,%rbp 84d4: 53 push %rbx 84d5: 48 83 ec 28 sub $0x28,%rsp 84d9: 65 8b 05 00 00 00 00 mov %gs:0x0(%rip),%eax # 84e0 <test_function_timeout+0x10> 84e0: 85 c0 test %eax,%eax 84e2: 0f 84 a0 00 00 00 je 8588 <test_function_timeout+0xb8> 84e8: 48 83 3d 00 00 00 00 cmpq $0x0,0x0(%rip) # 84f0 <test_function_timeout+0x20> 84ef: 00 84f0: 74 07 je 84f9 <test_function_timeout+0x29> 84f2: 48 83 c4 28 add $0x28,%rsp 84f6: 5b pop %rbx 84f7: 5d pop %rbp 84f8: c3 retq 84f9: 48 8d 7d d0 lea -0x30(%rbp),%rdi 84fd: 31 f6 xor %esi,%esi 84ff: bb 10 27 00 00 mov $0x2710,%ebx 8504: e8 00 00 00 00 callq 8509 <test_function_timeout+0x39> 8509: 48 8d 75 d0 lea -0x30(%rbp),%rsi 850d: ba 01 00 00 00 mov $0x1,%edx 8512: 48 c7 c7 00 00 00 00 mov $0x0,%rdi 8519: e8 00 00 00 00 callq 851e <test_function_timeout+0x4e> 851e: 48 83 3d 00 00 00 00 cmpq $0x0,0x0(%rip) # 8526 <test_function_timeout+0x56> 8525: 00 8526: 0f 95 c2 setne %dl 8529: 31 c9 xor %ecx,%ecx 852b: 84 d2 test %dl,%dl 852d: 75 42 jne 8571 <test_function_timeout+0xa1> 852f: 84 c9 test %cl,%cl 8531: 75 3e jne 8571 <test_function_timeout+0xa1> 8533: 48 85 c0 test %rax,%rax 8536: 75 ba jne 84f2 <test_function_timeout+0x22> 8538: 48 89 df mov %rbx,%rdi 853b: e8 00 00 00 00 callq 8540 <test_function_timeout+0x70> 8540: 48 8d 75 d0 lea -0x30(%rbp),%rsi 8544: ba 01 00 00 00 mov $0x1,%edx 8549: 48 c7 c7 00 00 00 00 mov $0x0,%rdi 8550: 48 89 c3 mov %rax,%rbx 8553: e8 00 00 00 00 callq 8558 <test_function_timeout+0x88> 8558: 48 83 3d 00 00 00 00 cmpq $0x0,0x0(%rip) # 8560 <test_function_timeout+0x90> 855f: 00 8560: 0f 95 c2 setne %dl 8563: 48 85 db test %rbx,%rbx 8566: 0f 94 c1 sete %cl 8569: 84 d2 test %dl,%dl 856b: 74 c2 je 852f <test_function_timeout+0x5f> 856d: 84 c9 test %cl,%cl 856f: 74 ba je 852b <test_function_timeout+0x5b> 8571: 48 8d 75 d0 lea -0x30(%rbp),%rsi 8575: 48 c7 c7 00 00 00 00 mov $0x0,%rdi 857c: e8 00 00 00 00 callq 8581 <test_function_timeout+0xb1> 8581: 48 83 c4 28 add $0x28,%rsp 8585: 5b pop %rbx 8586: 5d pop %rbp 8587: c3 retq 8588: e8 00 00 00 00 callq 858d <test_function_timeout+0xbd> 858d: e9 56 ff ff ff jmpq 84e8 <test_function_timeout+0x18>
Which is about 50 instructions (!!!), and about 180 bytes of text overheaed.
We have over 1,900 wait_event() call sites:
triton:~/tip> git grep -E 'wait_event.*\(' | wc -l 1972
which means that with an average per call site overhead of 100 bytes code, this means a total text bloat of about ~190 KB...
This was pretty much hidden from common forms of bloat and overhead analysis so far, because it's all inlined at the CPP level and hidden 'inside' various normal functions.
With my patch it's just a loop with a single function call, and much lower call site impact:
0000000000008490 <test_function>: 8490: 55 push %rbp 8491: 48 89 e5 mov %rsp,%rbp 8494: 48 83 ec 38 sub $0x38,%rsp
8498: c6 45 c8 00 movb $0x0,-0x38(%rbp) 849c: 31 d2 xor %edx,%edx 849e: 48 83 3d 00 00 00 00 cmpq $0x0,0x0(%rip) # 84a6 <test_function+0x16> 84a5: 00 84a6: 48 8d 75 c8 lea -0x38(%rbp),%rsi 84aa: 48 c7 c7 00 00 00 00 mov $0x0,%rdi 84b1: 0f 95 c2 setne %dl 84b4: e8 00 00 00 00 callq 84b9 <test_function+0x29> 84b9: 80 7d ca 00 cmpb $0x0,-0x36(%rbp) 84bd: 74 dd je 849c <test_function+0xc>
84bf: c9 leaveq 84c0: c3 retq
Which is about 9 instructions.
So with the wait-event state machine it's a very sweet, compact construct with only a single function call - 9 instructions total, even with more complex API variants. The original version generates over 20-50 instructions depending on complexity.
Also note that if we uninline much of the iterator with my approach, we could more aggressively inline _that_ central state machine function and get rid of the many function calls it does internally.
I.e. it's not just debloating but an all around speedup for the actual-waiting case, which does happen frequently. For the doesn't-wait case there's a bit more overhead due to the extra function call.
But, the never ending quest of an uncaring universe makes our life more difficult, because there are disadvantages of a state machine as well:
- State machines are so hellishly difficult to read, to get right and to maintain.
- While most wait_event() constructs actually do end up schedule()ing for real, but still the 'wait condition is already true' case gets burdened with an extra function call, because we have to call into wait.c. We could inline that first check, at the cost of more inlining overhead.
OTOH with this method we'd only have to get the state machine right roughly once, and have all the API variants in the wait.c space. We could use proper function pointers with inlining and other meta coding constructs within wait.c to reduce the number of variants in the source code space without adding runtime overhead. In fact I think we could optimize and form these functions a lot better within wait.c than in the macro space.
In any case, it's clear that this stuff is in no way v4.11 material, so as a bridging fix I propose we add a sched/signal.h include to wait.h (or just move signal_pending() temporarily), until it's all resolved for real for v4.12.
Thoughts?
Thanks,
Ingo
=================> From 0c32c5717beb4a5895cd80b3941246867afe1004 Mon Sep 17 00:00:00 2001 From: Ingo Molnar <mingo@kernel.org> Date: Sun, 5 Mar 2017 14:28:09 +0100 Subject: [PATCH] sched/wait: Introduce new, more compact wait_event*() primitives
Turn the wait_event() interface into a state machine.
Only very lightly tested, but should demonstrate the principle.
Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: linux-kernel@vger.kernel.org NOT-Signed-off-by: Ingo Molnar <mingo@kernel.org> --- include/linux/wait.h | 29 +++++++++++++++++++++++++- kernel/sched/wait.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 86 insertions(+), 1 deletion(-)
diff --git a/include/linux/wait.h b/include/linux/wait.h index ead731ef5632..285f282c928e 100644 --- a/include/linux/wait.h +++ b/include/linux/wait.h @@ -225,6 +225,31 @@ void __wake_up_sync(struct wait_queue_head *wq_head, unsigned int mode, int nr); extern void init_wait_entry(struct wait_queue_entry *wq_entry, int flags); +struct wait_event_state { + bool queued; + bool prepared; + bool done; + + long ret; + struct wait_queue_entry wq_entry; +}; + +extern long wait_event_loop(struct wait_queue_head *wq_head, struct wait_event_state *wes, int condition); + +#define wait_event_v2(wq_head, condition) \ +({ \ + struct wait_event_state __wes; \ + long __ret; \ + \ + __wes.queued = 0; \ + \ + do { \ + __ret = wait_event_loop(&(wq_head), &__wes, (condition) != 0); \ + } while (!__wes.done); \ + \ + __ret; \ +}) + /* * The below macro ___wait_event() has an explicit shadow of the __ret * variable when used from the wait_event_*() macros. @@ -277,7 +302,7 @@ __out: __ret; \ * wake_up() has to be called after changing any variable that could * change the result of the wait condition. */ -#define wait_event(wq_head, condition) \ +#define wait_event_v1(wq_head, condition) \ do { \ might_sleep(); \ if (condition) \ @@ -285,6 +310,8 @@ do { \ __wait_event(wq_head, condition); \ } while (0) +#define wait_event wait_event_v2 + #define __io_wait_event(wq_head, condition) \ (void)___wait_event(wq_head, condition, TASK_UNINTERRUPTIBLE, 0, 0, \ io_schedule()) diff --git a/kernel/sched/wait.c b/kernel/sched/wait.c index 48794482d9ac..4542d9f6a5a4 100644 --- a/kernel/sched/wait.c +++ b/kernel/sched/wait.c @@ -293,6 +293,64 @@ static inline bool is_kthread_should_stop(void) } /* + * The main wait_event*() event loop iteration state machine. + * + * Note that this function itself does not loop, it returns to + * the caller to evaluate the call site dependent condition in + * every iteration. + */ +long wait_event_loop(struct wait_queue_head *wq_head, struct wait_event_state *wes, int condition) +{ + if (!wes->queued) { + might_sleep(); + + /* + * If we are not initialized yet and the condition is already + * met, we can return immediately: + */ + if (condition) { + wes->done = 1; + return 0; + } + + /* Set up the wait-queue entry: */ + init_wait_entry(&wes->wq_entry, 0); + + wes->done = 0; + wes->queued = 1; + wes->prepared = 0; + wes->ret = 0; + } else { + /* Here is where we notice an updated wait condition: */ + if (condition) { + finish_wait(wq_head, &wes->wq_entry); + wes->done = 1; + return 0; + } + } + + if (!wes->prepared) { +prepare_again: + wes->ret = prepare_to_wait_event(wq_head, &wes->wq_entry, 0); + wes->prepared = 1; + + return 0; + } + + if (___wait_is_interruptible(0) && wes->ret) { + /* We already got dequeued, so mark it done: */ + wes->done = 1; + + /* But return any eventual interruption code: */ + return wes->ret; + } + + schedule(); + goto prepare_again; +} +EXPORT_SYMBOL_GPL(wait_event_loop); + +/* * DEFINE_WAIT_FUNC(wait, woken_wake_func); * * add_wait_queue(&wq_head, &wait);
| |