LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: tip-bot for Rik van Riel <riel@redhat.com>
To: linux-tip-commits@vger.kernel.org
Cc: linux-kernel@vger.kernel.org, riel@redhat.com, hpa@zytor.com,
	mingo@redhat.com, a.p.zijlstra@chello.nl, riel@redhat.com,
	tglx@linutronix.de, mingo@elte.hu
Subject: [tip:sched/core] sched: Limit the scope of clear_buddies
Date: Thu, 3 Feb 2011 14:11:54 GMT	[thread overview]
Message-ID: <tip-2c13c919d9e9a3db9896143a501f83dcbbe1ced4@git.kernel.org> (raw)
In-Reply-To: <20110201094837.6b0962a9@annuminas.surriel.com>

Commit-ID:  2c13c919d9e9a3db9896143a501f83dcbbe1ced4
Gitweb:     http://git.kernel.org/tip/2c13c919d9e9a3db9896143a501f83dcbbe1ced4
Author:     Rik van Riel <riel@redhat.com>
AuthorDate: Tue, 1 Feb 2011 09:48:37 -0500
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Thu, 3 Feb 2011 14:20:32 +0100

sched: Limit the scope of clear_buddies

The clear_buddies function does not seem to play well with the concept
of hierarchical runqueues.  In the following tree, task groups are
represented by 'G', tasks by 'T', next by 'n' and last by 'l'.

     (nl)
    /    \
   G(nl)  G
   / \     \
 T(l) T(n)  T

This situation can arise when a task is woken up T(n), and the previously
running task T(l) is marked last.

When clear_buddies is called from either T(l) or T(n), the next and last
buddies of the group G(nl) will be cleared.  This is not the desired
result, since we would like to be able to find the other type of buddy
in many cases.

This especially a worry when implementing yield_task_fair through the
buddy system.

The fix is simple: only clear the buddy type that the task itself
is indicated to be.  As an added bonus, we stop walking up the tree
when the buddy has already been cleared or pointed elsewhere.

Signed-off-by: Rik van Riel <riel@redhat.coM>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <20110201094837.6b0962a9@annuminas.surriel.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_fair.c |   30 +++++++++++++++++++++++-------
 1 files changed, 23 insertions(+), 7 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 4de9905..a785e08 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -995,19 +995,35 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		list_add_leaf_cfs_rq(cfs_rq);
 }
 
-static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
+static void __clear_buddies_last(struct sched_entity *se)
 {
-	if (!se || cfs_rq->last == se)
-		cfs_rq->last = NULL;
+	for_each_sched_entity(se) {
+		struct cfs_rq *cfs_rq = cfs_rq_of(se);
+		if (cfs_rq->last == se)
+			cfs_rq->last = NULL;
+		else
+			break;
+	}
+}
 
-	if (!se || cfs_rq->next == se)
-		cfs_rq->next = NULL;
+static void __clear_buddies_next(struct sched_entity *se)
+{
+	for_each_sched_entity(se) {
+		struct cfs_rq *cfs_rq = cfs_rq_of(se);
+		if (cfs_rq->next == se)
+			cfs_rq->next = NULL;
+		else
+			break;
+	}
 }
 
 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	for_each_sched_entity(se)
-		__clear_buddies(cfs_rq_of(se), se);
+	if (cfs_rq->last == se)
+		__clear_buddies_last(se);
+
+	if (cfs_rq->next == se)
+		__clear_buddies_next(se);
 }
 
 static void

  reply	other threads:[~2011-02-03 14:12 UTC|newest]

Thread overview: 25+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-02-01 14:44 [PATCH -v8a 0/7] directed yield for Pause Loop Exiting Rik van Riel
2011-02-01 14:47 ` [PATCH -v8a 1/7] sched: check the right ->nr_running in yield_task_fair Rik van Riel
2011-02-03 14:11   ` [tip:sched/core] sched: Check the right ->nr_running in yield_task_fair() tip-bot for Rik van Riel
2011-02-01 14:48 ` [PATCH -v8a 2/7] sched: limit the scope of clear_buddies Rik van Riel
2011-02-03 14:11   ` tip-bot for Rik van Riel [this message]
2011-02-01 14:50 ` [PATCH -v8a 4/7] sched: Add yield_to(task, preempt) functionality Rik van Riel
2011-02-01 15:52   ` Peter Zijlstra
2011-02-03 12:58   ` Peter Zijlstra
2011-02-03 14:12   ` [tip:sched/core] " tip-bot for Mike Galbraith
2011-02-26  0:43     ` Venkatesh Pallipadi
2011-02-26  5:44       ` Rik van Riel
2011-02-28  9:26         ` Mike Galbraith
2011-03-02  0:28           ` [PATCH] sched: resched proper CPU on yield_to Venkatesh Pallipadi
2011-03-02  3:33             ` Rik van Riel
2011-03-02  3:37               ` Venkatesh Pallipadi
2011-03-02  3:52             ` Rik van Riel
2011-03-04 11:50             ` [tip:sched/core] sched: Resched proper CPU on yield_to() tip-bot for Venkatesh Pallipadi
2011-02-01 14:51 ` [PATCH -v8a 3/7] sched: use a buddy to implement yield_task_fair Rik van Riel
2011-02-01 15:53   ` Peter Zijlstra
2011-02-03 12:58   ` Peter Zijlstra
2011-02-03 14:12   ` [tip:sched/core] sched: Use a buddy to implement yield_task_fair() tip-bot for Rik van Riel
2011-02-01 14:51 ` [PATCH -v8a 5/7] export pid symbols needed for kvm_vcpu_on_spin Rik van Riel
2011-02-01 14:52 ` [PATCH -v8a 6/7] kvm: keep track of which task is running a KVM vcpu Rik van Riel
2011-02-01 14:53 ` [PATCH -v8a 7/7] kvm: use yield_to instead of sleep in kvm_vcpu_on_spin Rik van Riel
2011-02-07  9:08 ` [PATCH -v8a 0/7] directed yield for Pause Loop Exiting Avi Kivity

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=tip-2c13c919d9e9a3db9896143a501f83dcbbe1ced4@git.kernel.org \
    --to=riel@redhat.com \
    --cc=a.p.zijlstra@chello.nl \
    --cc=hpa@zytor.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-tip-commits@vger.kernel.org \
    --cc=mingo@elte.hu \
    --cc=mingo@redhat.com \
    --cc=tglx@linutronix.de \
    --subject='Re: [tip:sched/core] sched: Limit the scope of clear_buddies' \
    /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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).