From patchwork Mon Oct 17 09:14:09 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vincent Guittot X-Patchwork-Id: 77720 Delivered-To: patch@linaro.org Received: by 10.140.97.247 with SMTP id m110csp299965qge; Mon, 17 Oct 2016 02:15:29 -0700 (PDT) X-Received: by 10.66.10.228 with SMTP id l4mr30867875pab.115.1476695729082; Mon, 17 Oct 2016 02:15:29 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id c3si25006371paw.162.2016.10.17.02.15.28; Mon, 17 Oct 2016 02:15:29 -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 S933883AbcJQJPQ (ORCPT + 27 others); Mon, 17 Oct 2016 05:15:16 -0400 Received: from mail-lf0-f46.google.com ([209.85.215.46]:36601 "EHLO mail-lf0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933791AbcJQJPF (ORCPT ); Mon, 17 Oct 2016 05:15:05 -0400 Received: by mail-lf0-f46.google.com with SMTP id b75so278089414lfg.3 for ; Mon, 17 Oct 2016 02:15:04 -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=CUop05/3rKoMFxALomCPnDkkxV9/Zp6ZWpv62t92XaM=; b=FGbsqGRxvqkMB1kplP2d2DjtdVDgO32RhaDXndaqVyMU3pdxBKHB3SHmxB0/6zHwAm LxfElYjMF9YKyWQBIR6oquvhMbkNLoAluT48iuvdDnZy0tRlDQqLmgxMSHgwSxy4wW36 UgWC7Vykp6UtQPFxC7gulJoGQ7nZcwZ54S988= 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=CUop05/3rKoMFxALomCPnDkkxV9/Zp6ZWpv62t92XaM=; b=fD0048vUeDyktZlx4IF1cbFnBDGEyajFcfyBOXKp2cXxqlPJ99DvZJy9ff8I/f6DLc /Q4OiO7bas/nZ5XqsZ669L6OuUsOMs/0+AKmap1PlpzcfjHDtS/Y8DvXrkwRGUU6t8wW EuMtTNTUVJfn6N1DXOLSl7418FUFcnns+x86o0qmfJf3Idw8cVwx5PEnnKOqal0eM+/Y XDlV2QdgHT+Rw/vAk/sEpaT6OxdTz0wD7dWJfOYFhvJTPQ5r6xtRXvOJNhSml8mTTVgX X8D8FkH90bijhgIR9+He3Rr0oYZ1p+mH9pCPyso0O4FEPRya1idbhBX3rFRqgsWIpDo7 AhsQ== X-Gm-Message-State: AA6/9RlcHeYoTC4M7zkp0mvkJGUG+73qcHQ7pDZ7pAry1WD1dsEvmNWXYYUVtgJoecvGQQCG X-Received: by 10.28.16.65 with SMTP id 62mr7241604wmq.130.1476695703382; Mon, 17 Oct 2016 02:15:03 -0700 (PDT) Received: from localhost.localdomain ([2a01:e35:8bd4:7750:80a0:ca36:f872:d659]) by smtp.gmail.com with ESMTPSA id f2sm51341206wjr.2.2016.10.17.02.15.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 17 Oct 2016 02:15:02 -0700 (PDT) From: Vincent Guittot To: peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org, dietmar.eggemann@arm.com Cc: yuyang.du@intel.com, Morten.Rasmussen@arm.com, linaro-kernel@lists.linaro.org, pjt@google.com, bsegall@google.com, kernellwp@gmail.com, Vincent Guittot Subject: [PATCH 2/6 v5] sched: fix hierarchical order in rq->leaf_cfs_rq_list Date: Mon, 17 Oct 2016 11:14:09 +0200 Message-Id: <1476695653-12309-3-git-send-email-vincent.guittot@linaro.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1476695653-12309-1-git-send-email-vincent.guittot@linaro.org> References: <1476695653-12309-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 be 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 --- kernel/sched/core.c | 1 + kernel/sched/fair.c | 54 +++++++++++++++++++++++++++++++++++++++++++++------- kernel/sched/sched.h | 1 + 3 files changed, 49 insertions(+), 7 deletions(-) -- 2.7.4 diff --git a/kernel/sched/core.c b/kernel/sched/core.c index aae08ce..59bce4f 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -7582,6 +7582,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->tmp_alone_branch = &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 584b86f..ecc66d6 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -290,19 +290,59 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) { if (!cfs_rq->on_list) { + struct rq *rq = rq_of(cfs_rq); + int cpu = cpu_of(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. + * enqueued. The fact that we always enqueue bottom-up + * reduces this to two cases and a special case for the root + * cfs_rq. Furthermore, it also means that we will always reset + * tmp_alone_branch either when the branch is connected + * to a tree or when we reach the beg of the tree */ 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 { + cfs_rq->tg->parent->cfs_rq[cpu]->on_list) { + /* + * If parent is already on the list, we add the child + * just before. Thanks to circular linked property of + * the list, this means to put the child at the tail + * of the list that starts by parent. + */ + list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list, + &(cfs_rq->tg->parent->cfs_rq[cpu]->leaf_cfs_rq_list)); + /* + * The branch is now connected to its tree so we can + * reset tmp_alone_branch to the beginning of the + * list. + */ + rq->tmp_alone_branch = &rq->leaf_cfs_rq_list; + } else if (!cfs_rq->tg->parent) { + /* + * cfs rq without parent should be put + * at the tail of the list. + */ list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list, - &rq_of(cfs_rq)->leaf_cfs_rq_list); + &rq->leaf_cfs_rq_list); + /* + * We have reach the beg of a tree so we can reset + * tmp_alone_branch to the beginning of the list. + */ + rq->tmp_alone_branch = &rq->leaf_cfs_rq_list; + } else { + /* + * The parent has not already been added so we want to + * make sure that it will be put after us. + * tmp_alone_branch points to the beg of the branch + * where we will add parent. + */ + list_add_rcu(&cfs_rq->leaf_cfs_rq_list, + rq->tmp_alone_branch); + /* + * update tmp_alone_branch to points to the new beg + * of the branch + */ + rq->tmp_alone_branch = &cfs_rq->leaf_cfs_rq_list; } cfs_rq->on_list = 1; diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 19b9986..f1185c3 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -623,6 +623,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 *tmp_alone_branch; #endif /* CONFIG_FAIR_GROUP_SCHED */ /*