Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1440314 > unrolled thread

Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-11 09:30 +0200
    Re: [PATCH] sched/fair: do not announce throttled next buddy in  dequeue_task_fair Konstantin Khlebnikov <khlebnikov@yandex-team.ru> - 2016-07-11 10:20 +0200
    Re: [PATCH] sched/fair: do not announce throttled next buddy in  dequeue_task_fair Xunlei Pang <xpang@redhat.com> - 2016-07-11 10:30 +0200
      Re: [PATCH] sched/fair: do not announce throttled next buddy in  dequeue_task_fair Xunlei Pang <xpang@redhat.com> - 2016-07-11 10:50 +0200
        Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-11 12:00 +0200
          Re: [PATCH] sched/fair: do not announce throttled next buddy in  dequeue_task_fair Xunlei Pang <xpang@redhat.com> - 2016-07-11 14:20 +0200
            Re: [PATCH] sched/fair: do not announce throttled next buddy in  dequeue_task_fair Konstantin Khlebnikov <khlebnikov@yandex-team.ru> - 2016-07-11 14:30 +0200
              Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair bsegall@google.com - 2016-07-12 19:30 +0200
                Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-13 04:00 +0200
                  Re: [PATCH] sched/fair: do not announce throttled next buddy in  dequeue_task_fair Xunlei Pang <xpang@redhat.com> - 2016-07-13 04:10 +0200
                    Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-13 04:20 +0200
                  Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair bsegall@google.com - 2016-07-13 19:10 +0200
                    Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-14 14:20 +0200
                      Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair bsegall@google.com - 2016-07-14 20:00 +0200
                        Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-15 00:40 +0200
                          Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair bsegall@google.com - 2016-07-15 00:50 +0200
                            Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair Wanpeng Li <kernellwp@gmail.com> - 2016-07-15 01:10 +0200

#1440314 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
> Hierarchy could be already throttled at this point. Throttled next
> buddy could trigger null pointer dereference in pick_next_task_fair().

There is cfs_rq->next check in pick_next_entity(), so how can null
pointer dereference happen?

Regards,
Wanpeng Li

[toc] | [next] | [standalone]

#1440345 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

On 11.07.2016 10:25, Wanpeng Li wrote:
> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>> Hierarchy could be already throttled at this point. Throttled next
>> buddy could trigger null pointer dereference in pick_next_task_fair().
>
> There is cfs_rq->next check in pick_next_entity(), so how can null
> pointer dereference happen?
>

If we nominate task from throttled hiearchy as a next buddy then at some
level in pick_next_task_fair we could pick cfs_rq which has no runnable
entities - in pick_next_entiry both "curr" and "left" are NULL.

-- 
Konstantin

[toc] | [prev] | [next] | [standalone]

#1440353 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

On 2016/07/11 at 15:25, Wanpeng Li wrote:
> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>> Hierarchy could be already throttled at this point. Throttled next
>> buddy could trigger null pointer dereference in pick_next_task_fair().
> There is cfs_rq->next check in pick_next_entity(), so how can null
> pointer dereference happen?

I guess it's the following code leading to a NULL se returned:
pick_next_entity():
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

Regards,
Xunlei

> Regards,
> Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1440370 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

On 2016/07/11 at 16:22, Xunlei Pang wrote:
> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>> Hierarchy could be already throttled at this point. Throttled next
>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>> There is cfs_rq->next check in pick_next_entity(), so how can null
>> pointer dereference happen?
> I guess it's the following code leading to a NULL se returned:

s/NULL/empty-entity cfs_rq se/

> pick_next_entity():
>     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>         se = cfs_rq->next;
>
> Regards,
> Xunlei
>
>> Regards,
>> Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1440406

Hi Konstantin, Xunlei,
2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>> Hierarchy could be already throttled at this point. Throttled next
>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>> pointer dereference happen?
>> I guess it's the following code leading to a NULL se returned:
>
> s/NULL/empty-entity cfs_rq se/
>
>> pick_next_entity():
>>     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
            ^^^^^^^^^^^^^
I think this will return false.

Regards,
Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1440518 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

On 2016/07/11 at 17:54, Wanpeng Li wrote:
> Hi Konstantin, Xunlei,
> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>> pointer dereference happen?
>>> I guess it's the following code leading to a NULL se returned:
>> s/NULL/empty-entity cfs_rq se/
>>
>>> pick_next_entity():
>>>     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>             ^^^^^^^^^^^^^
> I think this will return false.

With the wrong throttled_hierarchy(), I think this can happen. But after we have the
corrected throttled_hierarchy() patch, I can't see how it is possible.

dequeue_task_fair():
    if (task_sleep && parent_entity(se))
        set_next_buddy(parent_entity(se));

How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
IOW, a task belongs to a throttled hierarchy is running?

Maybe Konstantin knows the reason.

Regards,
Xunlei

[toc] | [prev] | [next] | [standalone]

#1440523 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

On 11.07.2016 15:12, Xunlei Pang wrote:
> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>> Hi Konstantin, Xunlei,
>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>> pointer dereference happen?
>>>> I guess it's the following code leading to a NULL se returned:
>>> s/NULL/empty-entity cfs_rq se/
>>>
>>>> pick_next_entity():
>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>              ^^^^^^^^^^^^^
>> I think this will return false.
>
> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
> corrected throttled_hierarchy() patch, I can't see how it is possible.
>
> dequeue_task_fair():
>      if (task_sleep && parent_entity(se))
>          set_next_buddy(parent_entity(se));
>
> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
> IOW, a task belongs to a throttled hierarchy is running?
>
> Maybe Konstantin knows the reason.

This function (dequeue_task_fair) check throttling but at point it could skip several
levels and announce as next buddy actually throttled entry.
Probably this bug hadn't happened but this's really hard to prove that this is impossible.
->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.

-- 
Konstantin

[toc] | [prev] | [next] | [standalone]

#1441613

Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:

> On 11.07.2016 15:12, Xunlei Pang wrote:
>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>> Hi Konstantin, Xunlei,
>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>> pointer dereference happen?
>>>>> I guess it's the following code leading to a NULL se returned:
>>>> s/NULL/empty-entity cfs_rq se/
>>>>
>>>>> pick_next_entity():
>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>              ^^^^^^^^^^^^^
>>> I think this will return false.
>>
>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>
>> dequeue_task_fair():
>>      if (task_sleep && parent_entity(se))
>>          set_next_buddy(parent_entity(se));
>>
>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>> IOW, a task belongs to a throttled hierarchy is running?
>>
>> Maybe Konstantin knows the reason.
>
> This function (dequeue_task_fair) check throttling but at point it could skip several
> levels and announce as next buddy actually throttled entry.
> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.

sched_setscheduler can call put_prev_task, which then can cause a
throttle outside of __schedule(), then the task blocks normally and
deactivate_task(DEQUEUE_SLEEP) happens and you lose.

The obvious way to avoid these would be to somehow change put_prev so
that it only does throttles in the schedule() path (which is what we
/want/), which would probably involve adding a parameter to put_prev for
just this.

[toc] | [prev] | [next] | [standalone]

#1441954

2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>
>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>> Hi Konstantin, Xunlei,
>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>> pointer dereference happen?
>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>
>>>>>> pick_next_entity():
>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>              ^^^^^^^^^^^^^
>>>> I think this will return false.
>>>
>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>
>>> dequeue_task_fair():
>>>      if (task_sleep && parent_entity(se))
>>>          set_next_buddy(parent_entity(se));
>>>
>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>> IOW, a task belongs to a throttled hierarchy is running?
>>>
>>> Maybe Konstantin knows the reason.
>>
>> This function (dequeue_task_fair) check throttling but at point it could skip several
>> levels and announce as next buddy actually throttled entry.
>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>
> sched_setscheduler can call put_prev_task, which then can cause a
> throttle outside of __schedule(), then the task blocks normally and
> deactivate_task(DEQUEUE_SLEEP) happens and you lose.

The cfs_rq_throttled() check in dequeue_task_fair() will capture the
cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
so nothing lost, where I miss?

Regards,
Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1441964 — Re: [PATCH] sched/fair: do not announce throttled next buddy in dequeue_task_fair

On 2016/07/13 at 09:50, Wanpeng Li wrote:
> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>
>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>> Hi Konstantin, Xunlei,
>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>> pointer dereference happen?
>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>
>>>>>>> pick_next_entity():
>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>              ^^^^^^^^^^^^^
>>>>> I think this will return false.
>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>
>>>> dequeue_task_fair():
>>>>      if (task_sleep && parent_entity(se))
>>>>          set_next_buddy(parent_entity(se));
>>>>
>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>
>>>> Maybe Konstantin knows the reason.
>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>> levels and announce as next buddy actually throttled entry.
>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>> sched_setscheduler can call put_prev_task, which then can cause a
>> throttle outside of __schedule(), then the task blocks normally and
>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
> so nothing lost, where I miss?

cfs_rq_throttled() returns false for child cgroups in the throttled hierarchy, so
throttled_hierarchy() should be relied on in such cases.

Regards,
Xunlei

[toc] | [prev] | [next] | [standalone]

#1441966

2016-07-13 9:58 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
> On 2016/07/13 at 09:50, Wanpeng Li wrote:
>> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>>
>>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>>> Hi Konstantin, Xunlei,
>>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>>> pointer dereference happen?
>>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>>
>>>>>>>> pick_next_entity():
>>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>>              ^^^^^^^^^^^^^
>>>>>> I think this will return false.
>>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>>
>>>>> dequeue_task_fair():
>>>>>      if (task_sleep && parent_entity(se))
>>>>>          set_next_buddy(parent_entity(se));
>>>>>
>>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>>
>>>>> Maybe Konstantin knows the reason.
>>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>>> levels and announce as next buddy actually throttled entry.
>>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>> sched_setscheduler can call put_prev_task, which then can cause a
>>> throttle outside of __schedule(), then the task blocks normally and
>>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
>> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
>> so nothing lost, where I miss?
>
> cfs_rq_throttled() returns false for child cgroups in the throttled hierarchy, so
> throttled_hierarchy() should be relied on in such cases.

Yes, so what's lost in bsegall's reply?

Regards,
Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1442639

Wanpeng Li <kernellwp@gmail.com> writes:

> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>
>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>> Hi Konstantin, Xunlei,
>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>> pointer dereference happen?
>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>
>>>>>>> pick_next_entity():
>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>              ^^^^^^^^^^^^^
>>>>> I think this will return false.
>>>>
>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>
>>>> dequeue_task_fair():
>>>>      if (task_sleep && parent_entity(se))
>>>>          set_next_buddy(parent_entity(se));
>>>>
>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>
>>>> Maybe Konstantin knows the reason.
>>>
>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>> levels and announce as next buddy actually throttled entry.
>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>
>> sched_setscheduler can call put_prev_task, which then can cause a
>> throttle outside of __schedule(), then the task blocks normally and
>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>
> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
> so nothing lost, where I miss?
>
> Regards,
> Wanpeng Li

The cfs_rq_throttled() checks there are done bottom-up, so they will
trigger too late. a/b/t, where t is descheduling and a is throttled can
still cause a set_next_buddy(b);

[toc] | [prev] | [next] | [standalone]

#1443402

2016-07-14 1:06 GMT+08:00  <bsegall@google.com>:
> Wanpeng Li <kernellwp@gmail.com> writes:
>
>> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>>
>>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>>> Hi Konstantin, Xunlei,
>>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>>> pointer dereference happen?
>>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>>
>>>>>>>> pick_next_entity():
>>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>>              ^^^^^^^^^^^^^
>>>>>> I think this will return false.
>>>>>
>>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>>
>>>>> dequeue_task_fair():
>>>>>      if (task_sleep && parent_entity(se))
>>>>>          set_next_buddy(parent_entity(se));
>>>>>
>>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>>
>>>>> Maybe Konstantin knows the reason.
>>>>
>>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>>> levels and announce as next buddy actually throttled entry.
>>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>>
>>> sched_setscheduler can call put_prev_task, which then can cause a
>>> throttle outside of __schedule(), then the task blocks normally and
>>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>>
>> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
>> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
>> so nothing lost, where I miss?
>>
>> Regards,
>> Wanpeng Li
>
> The cfs_rq_throttled() checks there are done bottom-up, so they will
> trigger too late. a/b/t, where t is descheduling and a is throttled can
> still cause a set_next_buddy(b);

throttle cfs_rq is up-bottom, so when a is throttled, b and c are not
yet, then task_sleep && se && !throttled_hierarchy(cfs_rq) still can't
prevent a set_next_buddy(b).

Regards,
Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1443649

Wanpeng Li <kernellwp@gmail.com> writes:

> 2016-07-14 1:06 GMT+08:00  <bsegall@google.com>:
>> Wanpeng Li <kernellwp@gmail.com> writes:
>>
>>> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>>>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>>>
>>>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>>>> Hi Konstantin, Xunlei,
>>>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>>>> pointer dereference happen?
>>>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>>>
>>>>>>>>> pick_next_entity():
>>>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>>>              ^^^^^^^^^^^^^
>>>>>>> I think this will return false.
>>>>>>
>>>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>>>
>>>>>> dequeue_task_fair():
>>>>>>      if (task_sleep && parent_entity(se))
>>>>>>          set_next_buddy(parent_entity(se));
>>>>>>
>>>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>>>
>>>>>> Maybe Konstantin knows the reason.
>>>>>
>>>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>>>> levels and announce as next buddy actually throttled entry.
>>>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>>>
>>>> sched_setscheduler can call put_prev_task, which then can cause a
>>>> throttle outside of __schedule(), then the task blocks normally and
>>>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>>>
>>> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
>>> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
>>> so nothing lost, where I miss?
>>>
>>> Regards,
>>> Wanpeng Li
>>
>> The cfs_rq_throttled() checks there are done bottom-up, so they will
>> trigger too late. a/b/t, where t is descheduling and a is throttled can
>> still cause a set_next_buddy(b);
>
> throttle cfs_rq is up-bottom, so when a is throttled, b and c are not
> yet, then task_sleep && se && !throttled_hierarchy(cfs_rq) still can't
> prevent a set_next_buddy(b).
>
> Regards,
> Wanpeng Li

They don't race or anything, everything's under rq->lock.
throttled_hierarchy will register properly, the issue is that a parent
is the one cfs_rq_throttled(), not the current cfs_rq, and
set_next_buddy will set cfs_rq->next to an se that is !on_rq.

In the other order (set_next_buddy then throttle), throttle_cfs_rq will
call dequeue which will clear the problematic buddy.

[toc] | [prev] | [next] | [standalone]

#1443816

2016-07-15 1:54 GMT+08:00  <bsegall@google.com>:
> Wanpeng Li <kernellwp@gmail.com> writes:
>
>> 2016-07-14 1:06 GMT+08:00  <bsegall@google.com>:
>>> Wanpeng Li <kernellwp@gmail.com> writes:
>>>
>>>> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>>>>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>>>>
>>>>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>>>>> Hi Konstantin, Xunlei,
>>>>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>>>>> pointer dereference happen?
>>>>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>>>>
>>>>>>>>>> pick_next_entity():
>>>>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>>>>              ^^^^^^^^^^^^^
>>>>>>>> I think this will return false.
>>>>>>>
>>>>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>>>>
>>>>>>> dequeue_task_fair():
>>>>>>>      if (task_sleep && parent_entity(se))
>>>>>>>          set_next_buddy(parent_entity(se));
>>>>>>>
>>>>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>>>>
>>>>>>> Maybe Konstantin knows the reason.
>>>>>>
>>>>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>>>>> levels and announce as next buddy actually throttled entry.
>>>>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>>>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>>>>
>>>>> sched_setscheduler can call put_prev_task, which then can cause a
>>>>> throttle outside of __schedule(), then the task blocks normally and
>>>>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>>>>
>>>> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
>>>> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
>>>> so nothing lost, where I miss?
>>>>
>>>> Regards,
>>>> Wanpeng Li
>>>
>>> The cfs_rq_throttled() checks there are done bottom-up, so they will
>>> trigger too late. a/b/t, where t is descheduling and a is throttled can
>>> still cause a set_next_buddy(b);
>>
>> throttle cfs_rq is up-bottom, so when a is throttled, b and c are not
>> yet, then task_sleep && se && !throttled_hierarchy(cfs_rq) still can't
>> prevent a set_next_buddy(b).
>>
>> Regards,
>> Wanpeng Li
>
> They don't race or anything, everything's under rq->lock.
> throttled_hierarchy will register properly, the issue is that a parent
> is the one cfs_rq_throttled(), not the current cfs_rq, and
> set_next_buddy will set cfs_rq->next to an se that is !on_rq.

Why b is !on_rq after throttle a?

Regards,
Wanpeng Li

[toc] | [prev] | [next] | [standalone]

#1443818

Wanpeng Li <kernellwp@gmail.com> writes:

> 2016-07-15 1:54 GMT+08:00  <bsegall@google.com>:
>> Wanpeng Li <kernellwp@gmail.com> writes:
>>
>>> 2016-07-14 1:06 GMT+08:00  <bsegall@google.com>:
>>>> Wanpeng Li <kernellwp@gmail.com> writes:
>>>>
>>>>> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>>>>>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>>>>>
>>>>>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>>>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>>>>>> Hi Konstantin, Xunlei,
>>>>>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>>>>>> pointer dereference happen?
>>>>>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>>>>>
>>>>>>>>>>> pick_next_entity():
>>>>>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>>>>>              ^^^^^^^^^^^^^
>>>>>>>>> I think this will return false.
>>>>>>>>
>>>>>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>>>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>>>>>
>>>>>>>> dequeue_task_fair():
>>>>>>>>      if (task_sleep && parent_entity(se))
>>>>>>>>          set_next_buddy(parent_entity(se));
>>>>>>>>
>>>>>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>>>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>>>>>
>>>>>>>> Maybe Konstantin knows the reason.
>>>>>>>
>>>>>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>>>>>> levels and announce as next buddy actually throttled entry.
>>>>>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>>>>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>>>>>
>>>>>> sched_setscheduler can call put_prev_task, which then can cause a
>>>>>> throttle outside of __schedule(), then the task blocks normally and
>>>>>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>>>>>
>>>>> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
>>>>> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
>>>>> so nothing lost, where I miss?
>>>>>
>>>>> Regards,
>>>>> Wanpeng Li
>>>>
>>>> The cfs_rq_throttled() checks there are done bottom-up, so they will
>>>> trigger too late. a/b/t, where t is descheduling and a is throttled can
>>>> still cause a set_next_buddy(b);
>>>
>>> throttle cfs_rq is up-bottom, so when a is throttled, b and c are not
>>> yet, then task_sleep && se && !throttled_hierarchy(cfs_rq) still can't
>>> prevent a set_next_buddy(b).
>>>
>>> Regards,
>>> Wanpeng Li
>>
>> They don't race or anything, everything's under rq->lock.
>> throttled_hierarchy will register properly, the issue is that a parent
>> is the one cfs_rq_throttled(), not the current cfs_rq, and
>> set_next_buddy will set cfs_rq->next to an se that is !on_rq.
>
> Why b is !on_rq after throttle a?
>
> Regards,
> Wanpeng Li

a is !on_rq (because of throttle), but set_next_buddy will set ->next up
the entire tree.

[toc] | [prev] | [next] | [standalone]

#1443820

2016-07-15 6:49 GMT+08:00  <bsegall@google.com>:
> Wanpeng Li <kernellwp@gmail.com> writes:
>
>> 2016-07-15 1:54 GMT+08:00  <bsegall@google.com>:
>>> Wanpeng Li <kernellwp@gmail.com> writes:
>>>
>>>> 2016-07-14 1:06 GMT+08:00  <bsegall@google.com>:
>>>>> Wanpeng Li <kernellwp@gmail.com> writes:
>>>>>
>>>>>> 2016-07-13 1:25 GMT+08:00  <bsegall@google.com>:
>>>>>>> Konstantin Khlebnikov <khlebnikov@yandex-team.ru> writes:
>>>>>>>
>>>>>>>> On 11.07.2016 15:12, Xunlei Pang wrote:
>>>>>>>>> On 2016/07/11 at 17:54, Wanpeng Li wrote:
>>>>>>>>>> Hi Konstantin, Xunlei,
>>>>>>>>>> 2016-07-11 16:42 GMT+08:00 Xunlei Pang <xpang@redhat.com>:
>>>>>>>>>>> On 2016/07/11 at 16:22, Xunlei Pang wrote:
>>>>>>>>>>>> On 2016/07/11 at 15:25, Wanpeng Li wrote:
>>>>>>>>>>>>> 2016-06-16 20:57 GMT+08:00 Konstantin Khlebnikov <khlebnikov@yandex-team.ru>:
>>>>>>>>>>>>>> Hierarchy could be already throttled at this point. Throttled next
>>>>>>>>>>>>>> buddy could trigger null pointer dereference in pick_next_task_fair().
>>>>>>>>>>>>> There is cfs_rq->next check in pick_next_entity(), so how can null
>>>>>>>>>>>>> pointer dereference happen?
>>>>>>>>>>>> I guess it's the following code leading to a NULL se returned:
>>>>>>>>>>> s/NULL/empty-entity cfs_rq se/
>>>>>>>>>>>
>>>>>>>>>>>> pick_next_entity():
>>>>>>>>>>>>      if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
>>>>>>>>>>              ^^^^^^^^^^^^^
>>>>>>>>>> I think this will return false.
>>>>>>>>>
>>>>>>>>> With the wrong throttled_hierarchy(), I think this can happen. But after we have the
>>>>>>>>> corrected throttled_hierarchy() patch, I can't see how it is possible.
>>>>>>>>>
>>>>>>>>> dequeue_task_fair():
>>>>>>>>>      if (task_sleep && parent_entity(se))
>>>>>>>>>          set_next_buddy(parent_entity(se));
>>>>>>>>>
>>>>>>>>> How does dequeue_task_fair() with DEQUEUE_SLEEP set(true task_sleep) happen to a throttled hierarchy?
>>>>>>>>> IOW, a task belongs to a throttled hierarchy is running?
>>>>>>>>>
>>>>>>>>> Maybe Konstantin knows the reason.
>>>>>>>>
>>>>>>>> This function (dequeue_task_fair) check throttling but at point it could skip several
>>>>>>>> levels and announce as next buddy actually throttled entry.
>>>>>>>> Probably this bug hadn't happened but this's really hard to prove that this is impossible.
>>>>>>>> ->set_curr_task(), PI-boost or some tricky migration in balancer could break this easily.
>>>>>>>
>>>>>>> sched_setscheduler can call put_prev_task, which then can cause a
>>>>>>> throttle outside of __schedule(), then the task blocks normally and
>>>>>>> deactivate_task(DEQUEUE_SLEEP) happens and you lose.
>>>>>>
>>>>>> The cfs_rq_throttled() check in dequeue_task_fair() will capture the
>>>>>> cfs_rq which is throttled in sched_setscheduler::put_prev_task path,
>>>>>> so nothing lost, where I miss?
>>>>>>
>>>>>> Regards,
>>>>>> Wanpeng Li
>>>>>
>>>>> The cfs_rq_throttled() checks there are done bottom-up, so they will
>>>>> trigger too late. a/b/t, where t is descheduling and a is throttled can
>>>>> still cause a set_next_buddy(b);
>>>>
>>>> throttle cfs_rq is up-bottom, so when a is throttled, b and c are not
>>>> yet, then task_sleep && se && !throttled_hierarchy(cfs_rq) still can't
>>>> prevent a set_next_buddy(b).
>>>>
>>>> Regards,
>>>> Wanpeng Li
>>>
>>> They don't race or anything, everything's under rq->lock.
>>> throttled_hierarchy will register properly, the issue is that a parent
>>> is the one cfs_rq_throttled(), not the current cfs_rq, and
>>> set_next_buddy will set cfs_rq->next to an se that is !on_rq.
>>
>> Why b is !on_rq after throttle a?
>>
>> Regards,
>> Wanpeng Li
>
> a is !on_rq (because of throttle), but set_next_buddy will set ->next up
> the entire tree.

Got it, thanks for your explanation. :)

Regards,
Wanpeng Li

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web