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

[Rik van Riel <riel@redhat.com>]

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.