Re: [RFC -v6 PATCH 2/8] sched: limit the scope of clear_buddies

Rik van Riel
2011-01-24T18:05:08Z

On 01/24/2011 12:57 PM, Peter Zijlstra wrote:
> On Thu, 2011-01-20 at 16:33 -0500, Rik van Riel wrote:
>> The clear_buddies function does not seem to play well with the concept
>> of hierarchical runqueues. In the following tree, task groups are
>> represented by 'G', tasks by 'T', next by 'n' and last by 'l'.
>>
>> (nl)
>> / \
>> G(nl) G
>> / \ \
>> T(l) T(n) T
>>
>> This situation can arise when a task is woken up T(n), and the previously
>> running task T(l) is marked last.
>>
>> When clear_buddies is called from either T(l) or T(n), the next and last
>> buddies of the group G(nl) will be cleared. This is not the desired
>> result, since we would like to be able to find the other type of buddy
>> in many cases.
>>
>> This especially a worry when implementing yield_task_fair through the
>> buddy system.
>>
>> The fix is simple: only clear the buddy type that the task itself
>> is indicated to be. As an added bonus, we stop walking up the tree
>> when the buddy has already been cleared or pointed elsewhere.
>>
>> Signed-off-by: Rik van Riel<riel@redhat.coM>
>> ---
>> kernel/sched_fair.c | 30 +++++++++++++++++++++++-------
>> 1 files changed, 23 insertions(+), 7 deletions(-)
>>
>> diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
>> index f4ee445..0321473 100644
>> --- a/kernel/sched_fair.c
>> +++ b/kernel/sched_fair.c
>> @@ -784,19 +784,35 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>> __enqueue_entity(cfs_rq, se);
>> }
>>
>> -static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
>> +static void __clear_buddies_last(struct sched_entity *se)
>> {
>> - if (!se || cfs_rq->last == se)
>> - cfs_rq->last = NULL;
>> + for_each_sched_entity(se) {
>> + struct cfs_rq *cfs_rq = cfs_rq_of(se);
>> + if (cfs_rq->last == se)
>> + cfs_rq->last = NULL;
>> + else
>> + break;
>> + }
>> +}
>>
>> - if (!se || cfs_rq->next == se)
>> - cfs_rq->next = NULL;
>> +static void __clear_buddies_next(struct sched_entity *se)
>> +{
>> + for_each_sched_entity(se) {
>> + struct cfs_rq *cfs_rq = cfs_rq_of(se);
>> + if (cfs_rq->next == se)
>> + cfs_rq->next = NULL;
>> + else
>> + break;
>> + }
>> }
>>
>> static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
>> {
>> - for_each_sched_entity(se)
>> - __clear_buddies(cfs_rq_of(se), se);
>> + if (cfs_rq->last == se)
>> + __clear_buddies_last(se);
>> +
>> + if (cfs_rq->next == se)
>> + __clear_buddies_next(se);
>> }
>>
>
> Right, I think this sorta matches with something the Google guys talked
> about, they wanted to change pick_next_task() no always start from the
> top but only go up one level when the current level ran out.
>
> It looks ok, just sad that we can now have two hierarchy traversals (and
> 3 with the next patch).

On the other hand, I don't think we'll actually _do_ the
hierarchy traversal most of the time, since pick_next_entity
calls clear_buddies, every step of the way down the tree.

A hierarchy traversal will only be done if a task already
has one type of buddy set, and then gets another type of
buddy set, before it is rescheduled.

Eg. a task can have ->last set and then call yield, causing
the ->yield buddy to get pointed at itself. When doing that,
it will walk up the tree, clearing ->last.

I suspect that with this patch, we'll end up doing less
tree traversal than before.