• V
    sched/fair: Fix hierarchical order in rq->leaf_cfs_rq_list · 9c2791f9
    Vincent Guittot 提交于
    Fix the insertion of cfs_rq in rq->leaf_cfs_rq_list to ensure that a
    child will always be called before its parent.
    
    The hierarchical order in shares update list has been introduced by
    commit:
    
      67e86250 ("sched: Introduce hierarchal order on shares update list")
    
    With the current implementation a child can be still put after its
    parent.
    
    Lets take the example of:
    
           root
            \
             b
             /\
             c d*
               |
               e*
    
    with root -> b -> c already enqueued but not d -> e so the
    leaf_cfs_rq_list looks like: head -> c -> b -> root -> tail
    
    The branch d -> e will be added the first time that they are enqueued,
    starting with e then d.
    
    When e is added, its parents is not already on the list so e is put at
    the tail : head -> c -> b -> root -> e -> tail
    
    Then, d is added at the head because its parent is already on the
    list: head -> d -> c -> b -> root -> e -> tail
    
    e is not placed at the right position and will be called the last
    whereas it should be called at the beginning.
    
    Because it follows the bottom-up enqueue sequence, we are sure that we
    will finished to add either a cfs_rq without parent or a cfs_rq with a
    parent that is already on the list. We can use this event to detect
    when we have finished to add a new branch. For the others, whose
    parents are not already added, we have to ensure that they will be
    added after their children that have just been inserted the steps
    before, and after any potential parents that are already in the list.
    The easiest way is to put the cfs_rq just after the last inserted one
    and to keep track of it untl the branch is fully added.
    Signed-off-by: NVincent Guittot <vincent.guittot@linaro.org>
    Signed-off-by: NPeter Zijlstra (Intel) <peterz@infradead.org>
    Acked-by: NDietmar Eggemann <dietmar.eggemann@arm.com>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Morten.Rasmussen@arm.com
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: bsegall@google.com
    Cc: kernellwp@gmail.com
    Cc: pjt@google.com
    Cc: yuyang.du@intel.com
    Link: http://lkml.kernel.org/r/1478598827-32372-3-git-send-email-vincent.guittot@linaro.orgSigned-off-by: NIngo Molnar <mingo@kernel.org>
    9c2791f9
sched.h 46.5 KB