sched: Introduce hierarchal order on shares update list
authorPaul Turner <pjt@google.com>
Mon, 15 Nov 2010 23:47:05 +0000 (15:47 -0800)
committerIngo Molnar <mingo@elte.hu>
Thu, 18 Nov 2010 12:27:48 +0000 (13:27 +0100)
commit67e86250f8ea7b8f7da53ac25ea73c6bd71f5cd9
tree9e429bdc568172f00e81aa4dcb57796ed0d404dd
parente33078baa4d30ad1d0e46d1f62b9e5a63a3e6ee3
sched: Introduce hierarchal order on shares update list

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: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <20101115234938.022488865@google.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
kernel/sched_fair.c