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

Groups > linux.kernel > #1411161 > unrolled thread

Re: [RFC PATCH] sched: fix hierarchical order in rq->leaf_cfs_rq_list

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: [RFC PATCH] sched: fix hierarchical order in rq->leaf_cfs_rq_list Peter Zijlstra <peterz@infradead.org> - 2016-06-01 14:40 +0200
    Re: [RFC PATCH] sched: fix hierarchical order in rq->leaf_cfs_rq_list bsegall@google.com - 2016-06-01 19:50 +0200
      Re: [RFC PATCH] sched: fix hierarchical order in rq->leaf_cfs_rq_list Vincent Guittot <vincent.guittot@linaro.org> - 2016-06-02 09:50 +0200

#1411161 — Re: [RFC PATCH] sched: fix hierarchical order in rq->leaf_cfs_rq_list

On Tue, May 24, 2016 at 11:55:10AM +0200, Vincent Guittot wrote:
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 218f8e8..6d3fbf2 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -290,15 +290,31 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
>  		 * Ensure we either appear before our parent (if already
>  		 * enqueued) or force our parent to appear after us when it is
>  		 * enqueued.  The fact that we always enqueue bottom-up
> +		 * reduces this to two cases and a specila case for the root

'special'

> +		 * cfs_rq.
>  		 */
>  		if (cfs_rq->tg->parent &&
>  		    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
> +			/* Add the child just before its parent */
> +			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
> +				&(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list));
> +			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
> +		} else if (!cfs_rq->tg->parent) {
> +			/*
> +			 * cfs_rq without parent should be
> +			 * at the end of the list
> +			 */
>  			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>  				&rq_of(cfs_rq)->leaf_cfs_rq_list);
> +			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
> +		} else {
> +			/*
> +			 * Our parent has not already been added so make sure
> +			 * that it will be put after us
> +			 */
> +			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
> +				rq_of(cfs_rq)->leaf_alone);
> +			rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
>  		}
>  
>  		cfs_rq->on_list = 1;

Paul, Ben ?

This used to be critical for update_shares() (now
update_blocked_averages), but IIRC is not critical for that since PELT.

I find its more readable with like so..


Also; I feel the comments can use more love; my head hurts ;-)

---
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -286,35 +286,38 @@ static inline struct cfs_rq *group_cfs_r
 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
 	if (!cfs_rq->on_list) {
+		struct rq *rq = rq_of(cfs_rq);
+		int cpu = cpu_of(rq);
+
 		/*
 		 * Ensure we either appear before our parent (if already
 		 * enqueued) or force our parent to appear after us when it is
 		 * enqueued.  The fact that we always enqueue bottom-up
-		 * reduces this to two cases and a specila case for the root
+		 * reduces this to two cases and a special case for the root
 		 * cfs_rq.
 		 */
 		if (cfs_rq->tg->parent &&
-		    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
+		    cfs_rq->tg->parent->cfs_rq[cpu]->on_list) {
 			/* Add the child just before its parent */
 			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
-				&(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list));
-			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
+				&(cfs_rq->tg->parent->cfs_rq[cpu]->leaf_cfs_rq_list));
+			rq->leaf_alone = &rq->leaf_cfs_rq_list;
 		} else if (!cfs_rq->tg->parent) {
 			/*
 			 * cfs_rq without parent should be
 			 * at the end of the list
 			 */
 			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
-				&rq_of(cfs_rq)->leaf_cfs_rq_list);
-			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
+					  &rq->leaf_cfs_rq_list);
+			rq->leaf_alone = &rq->leaf_cfs_rq_list;
 		} else {
 			/*
 			 * Our parent has not already been added so make sure
 			 * that it will be put after us
 			 */
 			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
-				rq_of(cfs_rq)->leaf_alone);
-			rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
+				     rq->leaf_alone);
+			rq->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
 		}
 
 		cfs_rq->on_list = 1;

[toc] | [next] | [standalone]

#1411426

Peter Zijlstra <peterz@infradead.org> writes:

> On Tue, May 24, 2016 at 11:55:10AM +0200, Vincent Guittot wrote:
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index 218f8e8..6d3fbf2 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -290,15 +290,31 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
>>  		 * Ensure we either appear before our parent (if already
>>  		 * enqueued) or force our parent to appear after us when it is
>>  		 * enqueued.  The fact that we always enqueue bottom-up
>> +		 * reduces this to two cases and a specila case for the root
>
> 'special'
>
>> +		 * cfs_rq.
>>  		 */
>>  		if (cfs_rq->tg->parent &&
>>  		    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
>> +			/* Add the child just before its parent */
>> +			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>> +				&(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list));
>> +			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
>> +		} else if (!cfs_rq->tg->parent) {
>> +			/*
>> +			 * cfs_rq without parent should be
>> +			 * at the end of the list
>> +			 */
>>  			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>>  				&rq_of(cfs_rq)->leaf_cfs_rq_list);
>> +			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
>> +		} else {
>> +			/*
>> +			 * Our parent has not already been added so make sure
>> +			 * that it will be put after us
>> +			 */
>> +			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
>> +				rq_of(cfs_rq)->leaf_alone);
>> +			rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
>>  		}
>>  
>>  		cfs_rq->on_list = 1;
>
> Paul, Ben ?
>
> This used to be critical for update_shares() (now
> update_blocked_averages), but IIRC is not critical for that since
> PELT.

Yeah, given that we no longer update_cfs_shares in that path, it
shouldn't be as important (unless new code is being added that it will
be useful for). That said, I honestly don't remember why we don't
update_cfs_shares, as it could affect the load.weight being used in a
parent's computation. Paul, do you remember? Was it just too expensive
and less necessary given the other improvements?

>
> I find its more readable with like so..
>
>
> Also; I feel the comments can use more love; my head hurts ;-)

Yeah


leaf_alone here is basically a temporary for the duration of an
enqueue_task_fair call, yes? A name suggesting that might be useful, or
else a comment mentioning that one of the first two cases will always
clear the otherwise unsafe reference before it can be a problem.

I think this also only barely works with throttling: even if the tg as a
whole is out of runtime, an individual cfs_rq can't be throttled until
just one line after list_add_cfs_rq, and we never list_del until cgroup
destruction. A throttled !on_list cfs_rq would cause us to never reset
leaf_alone, but I don't think that can quite happen.

>
> ---
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -286,35 +286,38 @@ static inline struct cfs_rq *group_cfs_r
>  static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
>  {
>  	if (!cfs_rq->on_list) {
> +		struct rq *rq = rq_of(cfs_rq);
> +		int cpu = cpu_of(rq);
> +
>  		/*
>  		 * Ensure we either appear before our parent (if already
>  		 * enqueued) or force our parent to appear after us when it is
>  		 * enqueued.  The fact that we always enqueue bottom-up
> -		 * reduces this to two cases and a specila case for the root
> +		 * reduces this to two cases and a special case for the root
>  		 * cfs_rq.
>  		 */
>  		if (cfs_rq->tg->parent &&
> -		    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
> +		    cfs_rq->tg->parent->cfs_rq[cpu]->on_list) {
>  			/* Add the child just before its parent */
>  			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
> -				&(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list));
> -			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
> +				&(cfs_rq->tg->parent->cfs_rq[cpu]->leaf_cfs_rq_list));
> +			rq->leaf_alone = &rq->leaf_cfs_rq_list;
>  		} else if (!cfs_rq->tg->parent) {
>  			/*
>  			 * cfs_rq without parent should be
>  			 * at the end of the list
>  			 */
>  			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
> -				&rq_of(cfs_rq)->leaf_cfs_rq_list);
> -			rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
> +					  &rq->leaf_cfs_rq_list);
> +			rq->leaf_alone = &rq->leaf_cfs_rq_list;
>  		} else {
>  			/*
>  			 * Our parent has not already been added so make sure
>  			 * that it will be put after us
>  			 */
>  			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
> -				rq_of(cfs_rq)->leaf_alone);
> -			rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
> +				     rq->leaf_alone);
> +			rq->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
>  		}
>  
>  		cfs_rq->on_list = 1;

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

#1411961

On 1 June 2016 at 19:42,  <bsegall@google.com> wrote:
> Peter Zijlstra <peterz@infradead.org> writes:
>
>> On Tue, May 24, 2016 at 11:55:10AM +0200, Vincent Guittot wrote:
>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>> index 218f8e8..6d3fbf2 100644
>>> --- a/kernel/sched/fair.c
>>> +++ b/kernel/sched/fair.c
>>> @@ -290,15 +290,31 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
>>>               * Ensure we either appear before our parent (if already
>>>               * enqueued) or force our parent to appear after us when it is
>>>               * enqueued.  The fact that we always enqueue bottom-up
>>> +             * reduces this to two cases and a specila case for the root
>>
>> 'special'
>>
>>> +             * cfs_rq.
>>>               */
>>>              if (cfs_rq->tg->parent &&
>>>                  cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
>>> +                    /* Add the child just before its parent */
>>> +                    list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>>> +                            &(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list));
>>> +                    rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
>>> +            } else if (!cfs_rq->tg->parent) {
>>> +                    /*
>>> +                     * cfs_rq without parent should be
>>> +                     * at the end of the list
>>> +                     */
>>>                      list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>>>                              &rq_of(cfs_rq)->leaf_cfs_rq_list);
>>> +                    rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
>>> +            } else {
>>> +                    /*
>>> +                     * Our parent has not already been added so make sure
>>> +                     * that it will be put after us
>>> +                     */
>>> +                    list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
>>> +                            rq_of(cfs_rq)->leaf_alone);
>>> +                    rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
>>>              }
>>>
>>>              cfs_rq->on_list = 1;
>>
>> Paul, Ben ?
>>
>> This used to be critical for update_shares() (now
>> update_blocked_averages), but IIRC is not critical for that since
>> PELT.
>
> Yeah, given that we no longer update_cfs_shares in that path, it
> shouldn't be as important (unless new code is being added that it will
> be useful for). That said, I honestly don't remember why we don't
> update_cfs_shares, as it could affect the load.weight being used in a
> parent's computation. Paul, do you remember? Was it just too expensive
> and less necessary given the other improvements?
>
>>
>> I find its more readable with like so..
>>
>>
>> Also; I feel the comments can use more love; my head hurts ;-)
>
> Yeah
>
>
> leaf_alone here is basically a temporary for the duration of an
> enqueue_task_fair call, yes? A name suggesting that might be useful, or

yes it is

> else a comment mentioning that one of the first two cases will always
> clear the otherwise unsafe reference before it can be a problem.

ok, i will add a comment

>
> I think this also only barely works with throttling: even if the tg as a
> whole is out of runtime, an individual cfs_rq can't be throttled until
> just one line after list_add_cfs_rq, and we never list_del until cgroup
> destruction. A throttled !on_list cfs_rq would cause us to never reset
> leaf_alone, but I don't think that can quite happen.

yes, i don't see how this can happen too

>
>>
>> ---
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -286,35 +286,38 @@ static inline struct cfs_rq *group_cfs_r
>>  static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
>>  {
>>       if (!cfs_rq->on_list) {
>> +             struct rq *rq = rq_of(cfs_rq);
>> +             int cpu = cpu_of(rq);
>> +
>>               /*
>>                * Ensure we either appear before our parent (if already
>>                * enqueued) or force our parent to appear after us when it is
>>                * enqueued.  The fact that we always enqueue bottom-up
>> -              * reduces this to two cases and a specila case for the root
>> +              * reduces this to two cases and a special case for the root
>>                * cfs_rq.
>>                */
>>               if (cfs_rq->tg->parent &&
>> -                 cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
>> +                 cfs_rq->tg->parent->cfs_rq[cpu]->on_list) {
>>                       /* Add the child just before its parent */
>>                       list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>> -                             &(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list));
>> -                     rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
>> +                             &(cfs_rq->tg->parent->cfs_rq[cpu]->leaf_cfs_rq_list));
>> +                     rq->leaf_alone = &rq->leaf_cfs_rq_list;
>>               } else if (!cfs_rq->tg->parent) {
>>                       /*
>>                        * cfs_rq without parent should be
>>                        * at the end of the list
>>                        */
>>                       list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
>> -                             &rq_of(cfs_rq)->leaf_cfs_rq_list);
>> -                     rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list;
>> +                                       &rq->leaf_cfs_rq_list);
>> +                     rq->leaf_alone = &rq->leaf_cfs_rq_list;
>>               } else {
>>                       /*
>>                        * Our parent has not already been added so make sure
>>                        * that it will be put after us
>>                        */
>>                       list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
>> -                             rq_of(cfs_rq)->leaf_alone);
>> -                     rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
>> +                                  rq->leaf_alone);
>> +                     rq->leaf_alone = &cfs_rq->leaf_cfs_rq_list;
>>               }
>>
>>               cfs_rq->on_list = 1;

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web