Re: [RFC][PATCH 3/3] sched: On-demand tg_shares_up()

[Peter Zijlstra <peterz@infradead.org>]

On Fri, 2010-09-03 at 02:52 +0100, Paul Turner wrote:
> > +static void update_shares(int cpu)
> > +{
> > +       struct cfs_rq *cfs_rq;
> > +       struct rq *rq = cpu_rq(cpu);
> > +
> > +       rcu_read_lock();
> > +       for_each_leaf_cfs_rq(rq, cfs_rq) {
> > +               struct task_group *tg = cfs_rq->tg;
> > +
> > +               do {
> > +                       tg_shares_up(tg, cpu);
> > +                       tg = tg->parent;
> > +               } while (tg);
> > +       }
> 
> This will multiply visit taskgroups:
> 
> In the case of a-b-task, both {a} and {b} will be on the leaf cfs_rq
> list.  Resulting in a being visited both as b's parent and as a leaf
> entity.
> 
> Rather than juggling to avoid this, it seems easier to maintain an
> ordering on rq->leaf_cfs_rq_list.
> 
> That is:
> 
> When an entity is added:
> a) If it has a parent, insert it immediately before the parent in the list.
> b) Otherwise it is attached to the root, attach it to the tail of
> rq->leaf_cfs_rq_list
> 
> This can actually be simplified to: if no parent insert at the tail,
> otherwise insert at the head, since we know the parent will always
> have been processed prior to the child.

Except we enqueue things bottom up, so: A-B-C-task would end up as:

add(C) - has parent on head: C
add(B) - has parent on head: B-C
add(A) - has no parent, on tail: B-C-A

Whereas we'd wanted: C-B-A

Which also means your rule (a) doens't work, can't enqueue it before the
parent if the parent itself isn't yet enqueued.

> Traversing the list in order should then ensure that all child
> entities have been processed for the 'next' entity at any given time
> and that its update is coherent. 

Right. I'm sure we can get something like this to work, just need to
come up with something that actually works, and a cold has currently
stopped everything but the very basic brain functions :/