• Paul Turner's avatar
    sched: Introduce hierarchal order on shares update list · 67e86250
    Paul Turner authored
    Avoid duplicate shares update calls by ensuring children always appear before
    parents in rq->leaf_cfs_rq_list.
    
    This allows us to do a single in-order traversal for update_shares().
    
    Since we always enqueue in bottom-up order this reduces to 2 cases:
    
    1) Our parent is already in the list, e.g.
    
       root
         \
          b
          /\
          c d* (root->b->c already enqueued)
    
    Since d's parent is enqueued we push it to the head of the list, implicitly ahead of b.
    
    2) Our parent does not appear in the list (or we have no parent)
    
    In this case we enqueue to the tail of the list, if our parent is subsequently enqueued
    (bottom-up) it will appear to our right by the same rule.
    Signed-off-by: default avatarPaul Turner <pjt@google.com>
    Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
    LKML-Reference: <20101115234938.022488865@google.com>
    Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    67e86250
sched_fair.c 105 KB