[PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Before waking up the tty line discipline idle queue first check if the queue is
active (non empty). This prevents unnecessary entering the critical section in
the wake_up() function and therefore avoid needless scheduling overhead on a
PREEMPT_RT system caused by two processes being in the same critical section.

Signed-off-by: Ivo Sieben <meltedpianoman@gmail.com>
---

 Remark:
 This patch has kind of a long history... I first tried to prevent the critical
 section in the wakeup() function itself by a change in the scheduler. But after
 review remarks from Oleg Nesterov it turned out that using the
 waitqueue_active() was a much nicer way to prevent it. See also
 https://lkml.org/lkml/2012/10/25/159

 drivers/tty/tty_ldisc.c |    4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/drivers/tty/tty_ldisc.c b/drivers/tty/tty_ldisc.c
index c578229..e96d187 100644
--- a/drivers/tty/tty_ldisc.c
+++ b/drivers/tty/tty_ldisc.c
@@ -64,7 +64,9 @@ static void put_ldisc(struct tty_ldisc *ld)
 		return;
 	}
 	raw_spin_unlock_irqrestore(&tty_ldisc_lock, flags);
-	wake_up(&ld->wq_idle);
+
+	if (waitqueue_active(&ld->wq_idle))
+		wake_up(&ld->wq_idle);
 }
 
 /**
-- 
1.7.9.5

[PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Before waking up the tty line discipline idle queue first check if the queue is
active (non empty). This prevents unnecessary entering the critical section in
the wake_up() function and therefore avoid needless scheduling overhead on a
PREEMPT_RT system caused by two processes being in the same critical section.

Signed-off-by: Ivo Sieben <meltedpianoman@gmail.com>
---

 Remark:
 This patch has kind of a long history... I first tried to prevent the critical
 section in the wakeup() function itself by a change in the scheduler. But after
 review remarks from Oleg Nesterov it turned out that using the
 waitqueue_active() was a much nicer way to prevent it. See also
 https://lkml.org/lkml/2012/10/25/159

 drivers/tty/tty_ldisc.c |    4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/drivers/tty/tty_ldisc.c b/drivers/tty/tty_ldisc.c
index c578229..e96d187 100644
--- a/drivers/tty/tty_ldisc.c
+++ b/drivers/tty/tty_ldisc.c
@@ -64,7 +64,9 @@ static void put_ldisc(struct tty_ldisc *ld)
 		return;
 	}
 	raw_spin_unlock_irqrestore(&tty_ldisc_lock, flags);
-	wake_up(&ld->wq_idle);
+
+	if (waitqueue_active(&ld->wq_idle))
+		wake_up(&ld->wq_idle);
 }
 
 /**
-- 
1.7.9.5

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Jiri Slaby]

On 12/18/2012 03:48 PM, Ivo Sieben wrote:
> Before waking up the tty line discipline idle queue first check if the queue is
> active (non empty). This prevents unnecessary entering the critical section in
> the wake_up() function and therefore avoid needless scheduling overhead on a
> PREEMPT_RT system caused by two processes being in the same critical section.
> 
> Signed-off-by: Ivo Sieben <meltedpianoman@gmail.com>
> ---
> 
>  Remark:
>  This patch has kind of a long history... I first tried to prevent the critical
>  section in the wakeup() function itself by a change in the scheduler. But after
>  review remarks from Oleg Nesterov it turned out that using the
>  waitqueue_active() was a much nicer way to prevent it. See also
>  https://lkml.org/lkml/2012/10/25/159
> 
>  drivers/tty/tty_ldisc.c |    4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
> 
> diff --git a/drivers/tty/tty_ldisc.c b/drivers/tty/tty_ldisc.c
> index c578229..e96d187 100644
> --- a/drivers/tty/tty_ldisc.c
> +++ b/drivers/tty/tty_ldisc.c
> @@ -64,7 +64,9 @@ static void put_ldisc(struct tty_ldisc *ld)
>  		return;
>  	}
>  	raw_spin_unlock_irqrestore(&tty_ldisc_lock, flags);
> -	wake_up(&ld->wq_idle);
> +
> +	if (waitqueue_active(&ld->wq_idle))
> +		wake_up(&ld->wq_idle);

Looks good, but I would prefer the layer to provide us with
wake_up_if_active...

-- 
js
suse labs

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Alan Cox]

> Looks good, but I would prefer the layer to provide us with
> wake_up_if_active...

Seconded - this is a problem for the wake up logic in the RT tree. Why
would we ever do anything else ?

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Hi Jiri & Alan,

2013/1/2 Alan Cox <alan@lxorguk.ukuu.org.uk>:
>
>> Looks good, but I would prefer the layer to provide us with
>> wake_up_if_active...
>
> Seconded - this is a problem for the wake up logic in the RT tree. Why
> would we ever do anything else ?

I don't understand your responses: do you suggest to implement this
"if active" behavior in:
* A new wake_up function called wake_up_if_active() that is part of
the waitqueue layer?
* Implement this behavior in the existing wake_up() function as part
of the RT patch?

Regards,
Ivo

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Jiri Slaby]

On 01/02/2013 04:21 PM, Ivo Sieben wrote:
> I don't understand your responses: do you suggest to implement this
> "if active" behavior in:
> * A new wake_up function called wake_up_if_active() that is part of
> the waitqueue layer?

Sounds good.

-- 
js
suse labs

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Oleg, Peter, Ingo, Andi & Preeti,

2013/1/2 Jiri Slaby <jslaby@suse.cz>:
> On 01/02/2013 04:21 PM, Ivo Sieben wrote:
>> I don't understand your responses: do you suggest to implement this
>> "if active" behavior in:
>> * A new wake_up function called wake_up_if_active() that is part of
>> the waitqueue layer?
>
> Sounds good.
>
> --
> js
> suse labs

I want to ask you 'scheduler' people for your opinion:

Maybe you remember my previous patch where I suggested an extra
'waitqueue empty' check before entering the critical section of the
wakeup() function (If you do not remember see
https://lkml.org/lkml/2012/10/25/159)

Finally Oleg responded that a lot of callers do

	if (waitqueue_active(q))
		wake_up(...);

what made my patch pointless and adds a memory barrier. I then decided
to also implement the 'waitqueue_active' approach for my problem.

But now I get a review comment by Jiri that he would like to hide this
'if active behavior' in a wake_up_if_active() kind of function. I
think he is right that implementing this check in the wakeup function
would clean things up, right?

I would like to have your opinion on the following two suggestions:
- We still can do the original patch on the wake_up() that I
suggested. I then can do an additional code cleanup patch that removes
the double 'waitqueue_active' call (a quick grep found about 150 of
these waitqueue active calls) on several places in the code.
- Or - as an alternative - I could add extra _if_active() versions of
all wake_up() functions, that implement this extra test.

Regards,
Ivo

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Oleg Nesterov]

On 01/03, Ivo Sieben wrote:
>
> Oleg, Peter, Ingo, Andi & Preeti,
>
> 2013/1/2 Jiri Slaby <jslaby@suse.cz>:
> > On 01/02/2013 04:21 PM, Ivo Sieben wrote:
> >> I don't understand your responses: do you suggest to implement this
> >> "if active" behavior in:
> >> * A new wake_up function called wake_up_if_active() that is part of
> >> the waitqueue layer?
> >
> > Sounds good.
> >
> > --
> > js
> > suse labs
>
> I want to ask you 'scheduler' people for your opinion:
>
> Maybe you remember my previous patch where I suggested an extra
> 'waitqueue empty' check before entering the critical section of the
> wakeup() function (If you do not remember see
> https://lkml.org/lkml/2012/10/25/159)
>
> Finally Oleg responded that a lot of callers do
>
> 	if (waitqueue_active(q))
> 		wake_up(...);
>
> what made my patch pointless and adds a memory barrier.

Plus this change doesn't look 100% correct, at least in theory.

> I then decided
> to also implement the 'waitqueue_active' approach for my problem.

Well, if you ask me I think this is the best solution ;)

But I won't insist.

> But now I get a review comment by Jiri that he would like to hide this
> 'if active behavior' in a wake_up_if_active() kind of function. I
> think he is right that implementing this check in the wakeup function
> would clean things up, right?
>
> I would like to have your opinion on the following two suggestions:
> - We still can do the original patch on the wake_up() that I
> suggested. I then can do an additional code cleanup patch that removes
> the double 'waitqueue_active' call (a quick grep found about 150 of
> these waitqueue active calls) on several places in the code.

In this case we should also fix some users of add_wait_queue().

> - Or - as an alternative - I could add extra _if_active() versions of
> all wake_up() functions, that implement this extra test.

Not sure this will actually help to make the code cleaner. The last
patch you sent looks simple and clean. IMHO it doesn't make sense
to create _if_active helper for each wake_up*.

Oleg.

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Hi

2013/1/3 Oleg Nesterov <oleg@redhat.com>:
>> I want to ask you 'scheduler' people for your opinion:
>>
>> Maybe you remember my previous patch where I suggested an extra
>> 'waitqueue empty' check before entering the critical section of the
>> wakeup() function (If you do not remember see
>> https://lkml.org/lkml/2012/10/25/159)
>>
>> Finally Oleg responded that a lot of callers do
>>
>>       if (waitqueue_active(q))
>>               wake_up(...);
>>
>> what made my patch pointless and adds a memory barrier.
>
> Plus this change doesn't look 100% correct, at least in theory.
>
>> I then decided
>> to also implement the 'waitqueue_active' approach for my problem.
>
> Well, if you ask me I think this is the best solution ;)
>
> But I won't insist.
>
>> But now I get a review comment by Jiri that he would like to hide this
>> 'if active behavior' in a wake_up_if_active() kind of function. I
>> think he is right that implementing this check in the wakeup function
>> would clean things up, right?
>>
>> I would like to have your opinion on the following two suggestions:
>> - We still can do the original patch on the wake_up() that I
>> suggested. I then can do an additional code cleanup patch that removes
>> the double 'waitqueue_active' call (a quick grep found about 150 of
>> these waitqueue active calls) on several places in the code.
>
> In this case we should also fix some users of add_wait_queue().
>
>> - Or - as an alternative - I could add extra _if_active() versions of
>> all wake_up() functions, that implement this extra test.
>
> Not sure this will actually help to make the code cleaner. The last
> patch you sent looks simple and clean. IMHO it doesn't make sense
> to create _if_active helper for each wake_up*.
>
> Oleg.
>

The comments by Oleg point out to me that the 'if waitqueueu_active'
is a common practice for checking a waitqueue to be non empty. It is
applied this way on several places in the kernel code.

@Jiri, Alan, Greg:
Don't you agree my patch makes sense?
It solves an issue for me, and I really would like this patch to be approved.

Regards,

Ivo Sieben

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Oleg Nesterov]

On 01/15, Ivo Sieben wrote:
>
> It solves an issue for me, and I really would like this patch to be approved.

Agreed.

And even if we want a helper to hide the waitqueue_active(), we can add it
later and convert more users, not just put_ldisc().

Oleg.

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Preeti U Murthy]

Hi Ivo,
Can you explain how this problem could create a scheduler overhead?
I am a little confused, because as far as i know,scheduler does not come
in the picture of the wake up path right? select_task_rq() in
try_to_wake_up() is where the scheduler comes in,and this is after the
task wakes up.

On 01/03/2013 03:19 PM, Ivo Sieben wrote:
> Oleg, Peter, Ingo, Andi & Preeti,
> 
> 2013/1/2 Jiri Slaby <jslaby@suse.cz>:
>> On 01/02/2013 04:21 PM, Ivo Sieben wrote:
>>> I don't understand your responses: do you suggest to implement this
>>> "if active" behavior in:
>>> * A new wake_up function called wake_up_if_active() that is part of
>>> the waitqueue layer?
>>
>> Sounds good.
>>
>> --
>> js
>> suse labs
> 
> I want to ask you 'scheduler' people for your opinion:
> 
> Maybe you remember my previous patch where I suggested an extra
> 'waitqueue empty' check before entering the critical section of the
> wakeup() function (If you do not remember see
> https://lkml.org/lkml/2012/10/25/159)
> 
> Finally Oleg responded that a lot of callers do
> 
> 	if (waitqueue_active(q))
> 		wake_up(...);
> 
> what made my patch pointless and adds a memory barrier. I then decided
> to also implement the 'waitqueue_active' approach for my problem.
> 
> But now I get a review comment by Jiri that he would like to hide this
> 'if active behavior' in a wake_up_if_active() kind of function. I
> think he is right that implementing this check in the wakeup function
> would clean things up, right?
> 
> I would like to have your opinion on the following two suggestions:
> - We still can do the original patch on the wake_up() that I
> suggested. I then can do an additional code cleanup patch that removes
> the double 'waitqueue_active' call (a quick grep found about 150 of
> these waitqueue active calls) on several places in the code.

I think this is a good move.

> - Or - as an alternative - I could add extra _if_active() versions of
> all wake_up() functions, that implement this extra test.

Why add 'extra' if_active versions? Why not optimize this within the
existing wake_up() functions?
> 
> Regards,
> Ivo

Regards
Preeti U Murthy
> 

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Hi Preeti,

2013/1/16 Preeti U Murthy <preeti@linux.vnet.ibm.com>:
> Hi Ivo,
> Can you explain how this problem could create a scheduler overhead?
> I am a little confused, because as far as i know,scheduler does not come
> in the picture of the wake up path right? select_task_rq() in
> try_to_wake_up() is where the scheduler comes in,and this is after the
> task wakes up.
>

Everytime the line discipline is dereferenced, the wakeup function is
called. The wakeup() function contains a critical section protected by
spinlocks. On a PREEMPT_RT system, a "normal" spinlock behaves just
like a mutex: scheduling is not disabled and it is still possible that
a new process on a higher RT priority is scheduled in. When a new -
higher priority - process is scheduled in just when the put_ldisc() is
in the critical section of the wakeup function, the higher priority
process (that uses the same TTY instance) will finally also
dereference the line discipline and try to wakeup the same waitqueue.
This causes the high priority process to  block on the same spinlock.
Priority inheritance will solve this blocked situation by a context
switch to the lower priority process, run until that process leaves
the critical section, and a context switch back to the higher priority
process. This is unnecessary since the waitqueue was empty after all
(during normal operation the waitqueue is empty most of the time).
This unnecessary context switch from/to the high priority process is
what a mean with "scheduler overhead" (maybe not a good name for it,
sorry for the confusion).

Does this makes sense to you?

Regards,
ivo Sieben

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Preeti U Murthy]

Hi Ivo,

On 01/16/2013 02:46 PM, Ivo Sieben wrote:
> Hi Preeti,
> 
> 2013/1/16 Preeti U Murthy <preeti@linux.vnet.ibm.com>:
>> Hi Ivo,
>> Can you explain how this problem could create a scheduler overhead?
>> I am a little confused, because as far as i know,scheduler does not come
>> in the picture of the wake up path right? select_task_rq() in
>> try_to_wake_up() is where the scheduler comes in,and this is after the
>> task wakes up.
>>
> 
> Everytime the line discipline is dereferenced, the wakeup function is
> called. The wakeup() function contains a critical section protected by
> spinlocks. On a PREEMPT_RT system, a "normal" spinlock behaves just
> like a mutex: scheduling is not disabled and it is still possible that
> a new process on a higher RT priority is scheduled in. When a new -
> higher priority - process is scheduled in just when the put_ldisc() is
> in the critical section of the wakeup function, the higher priority
> process (that uses the same TTY instance) will finally also
> dereference the line discipline and try to wakeup the same waitqueue.
> This causes the high priority process to  block on the same spinlock.
> Priority inheritance will solve this blocked situation by a context
> switch to the lower priority process, run until that process leaves
> the critical section, and a context switch back to the higher priority
> process. This is unnecessary since the waitqueue was empty after all
> (during normal operation the waitqueue is empty most of the time).
> This unnecessary context switch from/to the high priority process is
> what a mean with "scheduler overhead" (maybe not a good name for it,
> sorry for the confusion).
> 
> Does this makes sense to you?

Yes.Thank you very much for the explanation :) But I dont see how the
context switching goes away with your patch.With your patch, when the
higher priority thread comes in when the lower priority thread is
running in the critical section,it will see the wait queue empty and
"continue its execution" without now wanting to enter the critical
section.So this means it will preempt the lower priority thread because
it is not waiting on a lock anyway.There is a context switch here right?
I dont see any problem in scheduling due to this,but I do think your
patch is essential.

The entire logic of
wakelist_active()
  wake_up()

could be integrated into wake_up(). I dont understand why we need a
separate function to check the emptiness of the wake list. But as Oleg
pointed out we must identify the places for this optimization.

Regards
Preeti U Murthy

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

2013/1/16 Preeti U Murthy <preeti@linux.vnet.ibm.com>:
>
> Yes.Thank you very much for the explanation :) But I dont see how the
> context switching goes away with your patch.With your patch, when the
> higher priority thread comes in when the lower priority thread is
> running in the critical section,it will see the wait queue empty and
> "continue its execution" without now wanting to enter the critical
> section.So this means it will preempt the lower priority thread because
> it is not waiting on a lock anyway.There is a context switch here right?
> I dont see any problem in scheduling due to this,but I do think your
> patch is essential.
>

I don't have a problem that there is a context switch to the high
priority process: it has a higher priority, so it probably is more
important.
My problem is that even when the waitqueue is empty, the high priority
thread has a risk to block on the spinlock needlessly (causing context
switches to low priority task and back to the high priority task)

Regards,
Ivo Sieben

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Preeti U Murthy]

On 01/16/2013 05:32 PM, Ivo Sieben wrote:
> 2013/1/16 Preeti U Murthy <preeti@linux.vnet.ibm.com>:
>>
>> Yes.Thank you very much for the explanation :) But I dont see how the
>> context switching goes away with your patch.With your patch, when the
>> higher priority thread comes in when the lower priority thread is
>> running in the critical section,it will see the wait queue empty and
>> "continue its execution" without now wanting to enter the critical
>> section.So this means it will preempt the lower priority thread because
>> it is not waiting on a lock anyway.There is a context switch here right?
>> I dont see any problem in scheduling due to this,but I do think your
>> patch is essential.
>>
> 
> I don't have a problem that there is a context switch to the high
> priority process: it has a higher priority, so it probably is more
> important.
> My problem is that even when the waitqueue is empty, the high priority
> thread has a risk to block on the spinlock needlessly (causing context
> switches to low priority task and back to the high priority task)
> 
Fair enough Ivo.I think you should go ahead with merging the
waitqueue_active()
  wake_up()
logic into the wake_up() variants.

Regards
Preeti U Murthy

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Oleg Nesterov]

On 01/17, Preeti U Murthy wrote:
>
> On 01/16/2013 05:32 PM, Ivo Sieben wrote:
> >
> > I don't have a problem that there is a context switch to the high
> > priority process: it has a higher priority, so it probably is more
> > important.
> > My problem is that even when the waitqueue is empty, the high priority
> > thread has a risk to block on the spinlock needlessly (causing context
> > switches to low priority task and back to the high priority task)
> >
> Fair enough Ivo.I think you should go ahead with merging the
> waitqueue_active()
>   wake_up()
> logic into the wake_up() variants.

This is not easy. We can't simply change wake_up*() helpers or modify
__wake_up().

I can't understand why do you dislike Ivo's simple patch. There are
a lot of "if (waitqueue_active) wake_up" examples. Even if we add the
new helpers (personally I don't think this makes sense) , we can do
this later. Why should we delay this fix?

Oleg.

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Preeti U Murthy]

On 01/18/2013 09:15 PM, Oleg Nesterov wrote:
> On 01/17, Preeti U Murthy wrote:
>>
>> On 01/16/2013 05:32 PM, Ivo Sieben wrote:
>>>
>>> I don't have a problem that there is a context switch to the high
>>> priority process: it has a higher priority, so it probably is more
>>> important.
>>> My problem is that even when the waitqueue is empty, the high priority
>>> thread has a risk to block on the spinlock needlessly (causing context
>>> switches to low priority task and back to the high priority task)
>>>
>> Fair enough Ivo.I think you should go ahead with merging the
>> waitqueue_active()
>>   wake_up()
>> logic into the wake_up() variants.
> 
> This is not easy. We can't simply change wake_up*() helpers or modify
> __wake_up().

Hmm.I need to confess that I don't really know what goes into a change
such as this.Since there are a lot of waitqueue_active()+wake_up()
calls,I was wondering why at all have a separate logic as
waitqueue_active(),if we could do what it does in wake_up*(). But you
guys can decide this best.
> 
> I can't understand why do you dislike Ivo's simple patch. There are
> a lot of "if (waitqueue_active) wake_up" examples. Even if we add the
> new helpers (personally I don't think this makes sense) , we can do
> this later. Why should we delay this fix?

Personally i was concerned about how this could cause a scheduler
overhead.There does not seem to be much of a problem here.Ivo's patch
for adding a waitqueue_active() for his specific problem would also do
well,unless there is a dire requirement for a clean up,which I am unable
to evaluate.

> 
> Oleg.
> 

Thank you

Regards
Preeti U Murthy

Re: [PATCH] tty: Only wakeup the line discipline idle queue when queue is active

[Ivo Sieben]

Hi,

2013/1/18 Oleg Nesterov <oleg@redhat.com>:
>
> I can't understand why do you dislike Ivo's simple patch. There are
> a lot of "if (waitqueue_active) wake_up" examples. Even if we add the
> new helpers (personally I don't think this makes sense) , we can do
> this later. Why should we delay this fix?
>

FYI: Greg has added my patch to his tty-next branch, so my fix has
been approved.
Thank you all for reviewing.

Regards,
Ivo Sieben