From patchwork Tue May 24 09:55:10 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vincent Guittot X-Patchwork-Id: 68470 Delivered-To: patch@linaro.org Received: by 10.140.92.199 with SMTP id b65csp535324qge; Tue, 24 May 2016 02:55:23 -0700 (PDT) X-Received: by 10.98.67.93 with SMTP id q90mr5389451pfa.100.1464083723056; Tue, 24 May 2016 02:55:23 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id t129si40249092pfb.113.2016.05.24.02.55.22; Tue, 24 May 2016 02:55:23 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754406AbcEXJzT (ORCPT + 30 others); Tue, 24 May 2016 05:55:19 -0400 Received: from mail-wm0-f47.google.com ([74.125.82.47]:38340 "EHLO mail-wm0-f47.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752594AbcEXJzR (ORCPT ); Tue, 24 May 2016 05:55:17 -0400 Received: by mail-wm0-f47.google.com with SMTP id n129so16877079wmn.1 for ; Tue, 24 May 2016 02:55:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=RpbWvtqDekAXvbOuTqU3hyfNmF4aElHAsc8BLlateCA=; b=fSxv8TdQbXsylQJX1oLX7w2RZFa5MoIeCPh95+yqY51mWlu2FEQ165HvJs+w1kdJID qyDI5SeDb/bE/yV+jjZETlBs7cBuTZJIvICEeQG4+g2AIWpGDLJpuYEm7nASLUT2il/1 hRglFkiViOcjhuoiuN9FoA/d8Tb5bWMS5rdEg= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=RpbWvtqDekAXvbOuTqU3hyfNmF4aElHAsc8BLlateCA=; b=DhmE3gEMPrBPQnWecsQyQ3zlV5NcqtTsgz+y7Y+zUr3vls8+nX9c7SzCy8xjOc8G3M Exo8YodbpGQbOF7GpxyDuLYMw6/MrqEhy5b9Js1rrEpndPE1yHJGLKIie9isc0JLse2t O2UBhbxSRDZdoumdrVS097Gs9wYeekaQWWucHgIxoCZUrF061QhCPUN+d3VQHehMM4Ey q6QC2UnIvpvqye8M0SQWI3G2mS5BgxlV3swosmhiYDylkEAzV50KIp4gZG16Fv3mx27T EGi+xx2hCoZlnxSxydJRRERSMfpOSIvDax79v6A6x2J4qDO/sUwQJoJxDaMiUwsfppLv bLkw== X-Gm-Message-State: AOPr4FXc7w0pNNRYmxnfk4ex1D9fEzr5RcqZ4B+GMEun+3/MI8W048efLzlaoHt998bxmk81 X-Received: by 10.28.153.80 with SMTP id b77mr22071191wme.71.1464083716102; Tue, 24 May 2016 02:55:16 -0700 (PDT) Received: from localhost.localdomain (pas72-3-88-189-71-117.fbx.proxad.net. [88.189.71.117]) by smtp.gmail.com with ESMTPSA id g129sm2518635wme.1.2016.05.24.02.55.13 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 24 May 2016 02:55:14 -0700 (PDT) From: Vincent Guittot To: peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org, pjt@google.com Cc: yuyang.du@intel.com, dietmar.eggemann@arm.com, bsegall@google.com, Vincent Guittot Subject: [RFC PATCH] sched: fix hierarchical order in rq->leaf_cfs_rq_list Date: Tue, 24 May 2016 11:55:10 +0200 Message-Id: <1464083710-4370-1-git-send-email-vincent.guittot@linaro.org> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1464080135-17112-1-git-send-email-vincent.guittot@linaro.org> References: <1464080135-17112-1-git-send-email-vincent.guittot@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Fix the insertion of cfs_rq in rq->leaf_cfs_rq_list to ensure that a child will always called before its parent. The hierarchical order in shares update list has been introduced by commit 67e86250f8ea ("sched: Introduce hierarchal order on shares update list") With the current implementation a child can be still put after its parent. Lets take the example of root \ b /\ c d* | e* with root -> b -> c already enqueued but not d -> e so the leaf_cfs_rq_list looks like: head -> c -> b -> root -> tail The branch d -> e will be added the first time that they are enqueued, starting with e then d. When e is added, its parents is not already on the list so e is put at the tail : head -> c -> b -> root -> e -> tail Then, d is added at the head because its parent is already on the list: head -> d -> c -> b -> root -> e -> tail e is not placed at the right position and will be called the last whereas it should be called at the beginning. Because it follows the bottom-up enqueue sequence, we are sure that we will finished to add either a cfs_rq without parent or a cfs_rq with a parent that is already on the list. We can use this event to detect when we have finished to add a new branch. For the others, whose parents are not already added, we have to ensure that they will be added after their children that have just been inserted the steps before, and after any potential parents that are already in the list. The easiest way is to put the cfs_rq just after the last inserted one and to keep track of it untl the branch is fully added. Signed-off-by: Vincent Guittot --- Hi, Same version but rebased on latest sched/core Regards, Vincent kernel/sched/core.c | 1 + kernel/sched/fair.c | 24 ++++++++++++++++++++---- kernel/sched/sched.h | 1 + 3 files changed, 22 insertions(+), 4 deletions(-) -- 1.9.1 diff --git a/kernel/sched/core.c b/kernel/sched/core.c index 404c078..7b0fbdc 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -7386,6 +7386,7 @@ void __init sched_init(void) #ifdef CONFIG_FAIR_GROUP_SCHED root_task_group.shares = ROOT_TASK_GROUP_LOAD; INIT_LIST_HEAD(&rq->leaf_cfs_rq_list); + rq->leaf_alone = &rq->leaf_cfs_rq_list; /* * How much cpu bandwidth does root_task_group get? * diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 218f8e8..6d3fbf2 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -290,15 +290,31 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) * Ensure we either appear before our parent (if already * enqueued) or force our parent to appear after us when it is * enqueued. The fact that we always enqueue bottom-up - * reduces this to two cases. + * reduces this to two cases and a specila case for the root + * cfs_rq. */ if (cfs_rq->tg->parent && cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) { - list_add_rcu(&cfs_rq->leaf_cfs_rq_list, - &rq_of(cfs_rq)->leaf_cfs_rq_list); - } else { + /* Add the child just before its parent */ + list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list, + &(cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->leaf_cfs_rq_list)); + rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list; + } else if (!cfs_rq->tg->parent) { + /* + * cfs_rq without parent should be + * at the end of the list + */ list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list, &rq_of(cfs_rq)->leaf_cfs_rq_list); + rq_of(cfs_rq)->leaf_alone = &rq_of(cfs_rq)->leaf_cfs_rq_list; + } else { + /* + * Our parent has not already been added so make sure + * that it will be put after us + */ + list_add_rcu(&cfs_rq->leaf_cfs_rq_list, + rq_of(cfs_rq)->leaf_alone); + rq_of(cfs_rq)->leaf_alone = &cfs_rq->leaf_cfs_rq_list; } cfs_rq->on_list = 1; diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index e51145e..30750dc 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -614,6 +614,7 @@ struct rq { #ifdef CONFIG_FAIR_GROUP_SCHED /* list of leaf cfs_rq on this cpu: */ struct list_head leaf_cfs_rq_list; + struct list_head *leaf_alone; #endif /* CONFIG_FAIR_GROUP_SCHED */ /*