Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

From	Tejun Heo <tj@kernel.org>
Newsgroups	linux.kernel
Subject	Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path
Date	2017-05-12 15:20 +0200
Message-ID	<tGiE9-52n-3@gated-at.bofh.it> (permalink)
References	<tFg1I-45Y-19@gated-at.bofh.it> <tFg1I-45Y-27@gated-at.bofh.it> <tFtLj-5MF-11@gated-at.bofh.it> <tFB69-1Xf-11@gated-at.bofh.it> <tFQoy-3dF-9@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

Hello, Vincent.

On Thu, May 11, 2017 at 09:02:22AM +0200, Vincent Guittot wrote:
> Sorry, what i mean is:
> When the group entity of a cfs_rq is enqueued, we are sure that either
> the parents is already enqueued or it will be enqueued in the same
> sequence. We must be sure that no other branch will be enqueued in the
> middle of the sequence and will reset tmp_alone_branch.
> This is true with current implementation but I  wondered it can happen
> if we del/add the cfs_rq out of order
> 
> That said i haven't find a use case that break the sequence

Hmm... a cfs_rq can be removed from leaf list iff it's empty and
dequeued, and enqueueing is always from top down.  If an ancestor is
already enqueued, it's guaranteed to be on the leaf list; otherwise,
it's guaranteed to be enqueued beforehand and thus put on the leaf
list too.  I think it should be fine.

Thanks.

-- 
tejun

Thread

[PATCH v2 for-4.12-fixes 1/2] sched/fair: Use task_groups instead of  leaf_cfs_rq_list to walk all cfs_rqs Tejun Heo <tj@kernel.org> - 2017-05-09 18:20 +0200
  [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in  load balance path Tejun Heo <tj@kernel.org> - 2017-05-09 18:20 +0200
    Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups)  in load balance path Vincent Guittot <vincent.guittot@linaro.org> - 2017-05-10 09:00 +0200
      Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups)  in load balance path Tejun Heo <tj@kernel.org> - 2017-05-10 16:50 +0200
        Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups)  in load balance path Tejun Heo <tj@kernel.org> - 2017-05-10 18:00 +0200
        Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups)  in load balance path Vincent Guittot <vincent.guittot@linaro.org> - 2017-05-11 09:10 +0200
          Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups)  in load balance path Tejun Heo <tj@kernel.org> - 2017-05-12 15:20 +0200
            Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups)  in load balance path Vincent Guittot <vincent.guittot@linaro.org> - 2017-05-12 16:40 +0200
    [PATCH v3 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in  load balance path Tejun Heo <tj@kernel.org> - 2017-05-10 19:40 +0200

csiph-web