linux-kernel - Re: [RFC][PATCH 3/3] sched: On-demand tg_shares

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 03 Sep 2010 09:59:36 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Paul Turner <pjt@...gle.com>
Cc:	linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...e.hu>,
	Srivatsa Vaddagiri <vatsa@...ibm.com>,
	Chris Friesen <cfriesen@...tel.com>,
	Vaidyanathan Srinivasan <svaidy@...ux.vnet.ibm.com>,
	Pierre Bourdon <pbourdon@...ellency.fr>
Subject: Re: [RFC][PATCH 3/3] sched: On-demand tg_shares_up()

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 :/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/