mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: "Jan H. Schönherr" <schnhrr@cs.tu-berlin.de>
To: Ingo Molnar <mingo@elte.hu>, Peter Zijlstra <peterz@infradead.org>
Cc: "Paul Turner" <pjt@google.com>,
	linux-kernel@vger.kernel.org,
	"Jan H. Schönherr" <schnhrr@cs.tu-berlin.de>
Subject: [PATCH 2/2] sched: Prevent removal of leaf CFS runqueues with on_list children
Date: Mon, 18 Jul 2011 12:50:58 +0200	[thread overview]
Message-ID: <1310986258-29985-3-git-send-email-schnhrr@cs.tu-berlin.de> (raw)
In-Reply-To: <1310986258-29985-1-git-send-email-schnhrr@cs.tu-berlin.de>

From: Jan H. Schönherr <schnhrr@cs.tu-berlin.de>

Currently there are (at least) two situations where a parent gets removed
from the list of leaf CFS runqueues although some of its children are
still on the list.

This patch adds a counter for children depending on a parent, preventing
the parent from being removed too early.

Consider three task groups with these parent pointers:
tg1 --> tg2 --> tg3

Situation 1:

1. Enqueue task A in tg1
2. Dequeue task A
3. Enqueue task B in tg2

In step 1 all three runqueues are added as leaves.

In step 2 the primary reason for being on the list vanishes, but all
three runqueues are kept on the list.

In step 3 we call enqueue_entity() for tg2. There, we call
update_cfs_load() before increasing nr_running. Therefore tg2 can be
removed from the leaf list. Note that enqueue_entity() will re-add tg2
at the end, but this will mix up the order as we do not provide tg1
as prev_cfs_rq.

Situation 2:

There is no guarantee that cfs_rq->load_avg of tg1 drops to zero before
that of tg2. Hence, tg2 can be removed before tg1. If something is
enqueued in tg2 after its removal, it would be added at the wrong
position. Enqueuing something in tg1 before it is removed would further
prevent the situation from sorting out itself.

Signed-off-by: Jan H. Schönherr <schnhrr@cs.tu-berlin.de>
---
 kernel/sched.c      |    1 +
 kernel/sched_fair.c |   10 +++++++++-
 2 files changed, 10 insertions(+), 1 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index 9769c75..88c83b8 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -344,6 +344,7 @@ struct cfs_rq {
 	 * list is used during load balance.
 	 */
 	int on_list;
+	int children_on_list;
 	struct list_head leaf_cfs_rq_list;
 	struct task_group *tg;	/* group that "owns" this runqueue */
 
diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index d021c75..1c7dd1d 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -166,14 +166,22 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq,
 		list_add_rcu(&cfs_rq->leaf_cfs_rq_list, prev_leaf_cfs_rq);
 
 		cfs_rq->on_list = 1;
+		if (cfs_rq->tg->parent) {
+			int cpu = cpu_of(rq_of(cfs_rq));
+			cfs_rq->tg->parent->cfs_rq[cpu]->children_on_list++;
+		}
 	}
 }
 
 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
-	if (cfs_rq->on_list) {
+	if (cfs_rq->on_list && !cfs_rq->children_on_list) {
 		list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
 		cfs_rq->on_list = 0;
+		if (cfs_rq->tg->parent) {
+			int cpu = cpu_of(rq_of(cfs_rq));
+			cfs_rq->tg->parent->cfs_rq[cpu]->children_on_list--;
+		}
 	}
 }
 
-- 
1.7.3.4


      parent reply	other threads:[~2011-07-18 10:52 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-07-18 10:50 [PATCH 0/2] Enforce hierarchical order of leaf CFS runqueues Jan H. Schönherr
2011-07-18 10:50 ` [PATCH 1/2] sched: Enforce " Jan H. Schönherr
2011-07-18 23:24   ` Paul Turner
2011-07-19 13:08     ` Peter Zijlstra
2011-07-19 17:48       ` Paul Turner
2011-07-19 15:17     ` Jan Schönherr
2011-07-19 17:53       ` Paul Turner
2011-07-21 13:20     ` Jan H. Schönherr
2011-07-21 13:20       ` [PATCH RFC 1/3] list, treewide: Rename __list_del() to __list_link() Jan H. Schönherr
2011-07-21 13:20       ` [PATCH RFC 2/3] rcu: More rcu-variants for list manipulation Jan H. Schönherr
2011-07-22 16:21         ` Paul E. McKenney
2011-07-23 18:41           ` Jan Schönherr
2011-07-21 13:20       ` [PATCH RFC 3/3] sched: Handle on_list ancestor in list_add_leaf_cfs_rq() Jan H. Schönherr
2011-07-18 10:50 ` Jan H. Schönherr [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1310986258-29985-3-git-send-email-schnhrr@cs.tu-berlin.de \
    --to=schnhrr@cs.tu-berlin.de \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@elte.hu \
    --cc=peterz@infradead.org \
    --cc=pjt@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®