From patchwork Fri Sep 27 18:54:50 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Connor Kuehl X-Patchwork-Id: 1168692 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=lists.ubuntu.com (client-ip=91.189.94.19; helo=huckleberry.canonical.com; envelope-from=kernel-team-bounces@lists.ubuntu.com; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=canonical.com Received: from huckleberry.canonical.com (huckleberry.canonical.com [91.189.94.19]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 46g1G10nCMz9sPD; Sat, 28 Sep 2019 04:55:35 +1000 (AEST) Received: from localhost ([127.0.0.1] helo=huckleberry.canonical.com) by huckleberry.canonical.com with esmtp (Exim 4.86_2) (envelope-from ) id 1iDvOq-0008GQ-V3; Fri, 27 Sep 2019 18:55:28 +0000 Received: from youngberry.canonical.com ([91.189.89.112]) by huckleberry.canonical.com with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.86_2) (envelope-from ) id 1iDvOo-0008G6-AM for kernel-team@lists.ubuntu.com; Fri, 27 Sep 2019 18:55:26 +0000 Received: from mail-pf1-f198.google.com ([209.85.210.198]) by youngberry.canonical.com with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.86_2) (envelope-from ) id 1iDvOn-0001fV-WF for kernel-team@lists.ubuntu.com; Fri, 27 Sep 2019 18:55:26 +0000 Received: by mail-pf1-f198.google.com with SMTP id o73so2545368pfg.5 for ; Fri, 27 Sep 2019 11:55:25 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=52mq8BNLs59HFIUJxCTU/mMerfkrZ9+YAXb4w1rM31k=; b=CEvPErk5KJ03sT5ASd19eJWfJHMihBYvBKzUfXEF2ELXdaLrjMwi6N/JsY7l4cRPE5 eNKmVlh5H0saEK/fSJFTxcBaageJL3wBaS8q/yifEiOOqMW7MqUu43cbGeIZFoNTqDbq zGg4zpKtZlaiu/SeCE7WwTJl0vPPhGQ4ZnNpt5aIkObVL1cysiJ4J3kJ6s4/nspQZJpo BIoEDRYAd6XZfthaZ/YhZ7u3A3Gw4rvRQKfgGPYmVnN20BekX9jJ+9ckMb0cruYxcjjF 6U5O+A1kwJ8PK1zhHPFQDns/9MiNofQb7KOB6VumcNvGUTYHDD58zJWNSI0gJmKxGfwk h7+A== X-Gm-Message-State: APjAAAU4kUvbn3oyiQTGDeUrJUvG04lFzcUJqeeLVJR6uoJfr1Je+bmq ZJVeMTAfbp0wwcZxN13c4abRx37F6ptClzu0kxgLC3Wgpbdacg+NJUcJ8Nw33rTHpttS5Cdtx0X 8rEhrDKLw00FqF5ztbI8oZx+ljhAnPjgV577CmCikjA== X-Received: by 2002:a17:90a:19c9:: with SMTP id 9mr11734459pjj.49.1569610524080; Fri, 27 Sep 2019 11:55:24 -0700 (PDT) X-Google-Smtp-Source: APXvYqx6Zy/MS6o6upZb7+DXewf/Qp9MX4n2SAnP5UVlstbw6Mcr6Nm4lOJeWzgMxTHH74ohgWOcUg== X-Received: by 2002:a17:90a:19c9:: with SMTP id 9mr11734435pjj.49.1569610523774; Fri, 27 Sep 2019 11:55:23 -0700 (PDT) Received: from localhost.localdomain (c-71-63-171-240.hsd1.or.comcast.net. [71.63.171.240]) by smtp.gmail.com with ESMTPSA id g7sm4585017pfm.176.2019.09.27.11.55.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 Sep 2019 11:55:23 -0700 (PDT) From: Connor Kuehl To: kernel-team@lists.ubuntu.com Subject: [Xenial][SRU][CVE-2018-20784][PATCH 1/1] sched/fair: Fix infinite loop in update_blocked_averages() by reverting a9e7f6544b9c Date: Fri, 27 Sep 2019 11:54:50 -0700 Message-Id: <20190927185450.29493-2-connor.kuehl@canonical.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190927185450.29493-1-connor.kuehl@canonical.com> References: <20190927185450.29493-1-connor.kuehl@canonical.com> X-BeenThere: kernel-team@lists.ubuntu.com X-Mailman-Version: 2.1.20 Precedence: list List-Id: Kernel team discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: kernel-team-bounces@lists.ubuntu.com Sender: "kernel-team" From: Linus Torvalds CVE-2018-20784 Zhipeng Xie, Xie XiuQi and Sargun Dhillon reported lockups in the scheduler under high loads, starting at around the v4.18 time frame, and Zhipeng Xie tracked it down to bugs in the rq->leaf_cfs_rq_list manipulation. Do a (manual) revert of: a9e7f6544b9c ("sched/fair: Fix O(nr_cgroups) in load balance path") It turns out that the list_del_leaf_cfs_rq() introduced by this commit is a surprising property that was not considered in followup commits such as: 9c2791f936ef ("sched/fair: Fix hierarchical order in rq->leaf_cfs_rq_list") As Vincent Guittot explains: "I think that there is a bigger problem with commit a9e7f6544b9c and cfs_rq throttling: Let take the example of the following topology TG2 --> TG1 --> root: 1) The 1st time a task is enqueued, we will add TG2 cfs_rq then TG1 cfs_rq to leaf_cfs_rq_list and we are sure to do the whole branch in one path because it has never been used and can't be throttled so tmp_alone_branch will point to leaf_cfs_rq_list at the end. 2) Then TG1 is throttled 3) and we add TG3 as a new child of TG1. 4) The 1st enqueue of a task on TG3 will add TG3 cfs_rq just before TG1 cfs_rq and tmp_alone_branch will stay on rq->leaf_cfs_rq_list. With commit a9e7f6544b9c, we can del a cfs_rq from rq->leaf_cfs_rq_list. So if the load of TG1 cfs_rq becomes NULL before step 2) above, TG1 cfs_rq is removed from the list. Then at step 4), TG3 cfs_rq is added at the beginning of rq->leaf_cfs_rq_list but tmp_alone_branch still points to TG3 cfs_rq because its throttled parent can't be enqueued when the lock is released. tmp_alone_branch doesn't point to rq->leaf_cfs_rq_list whereas it should. So if TG3 cfs_rq is removed or destroyed before tmp_alone_branch points on another TG cfs_rq, the next TG cfs_rq that will be added, will be linked outside rq->leaf_cfs_rq_list - which is bad. In addition, we can break the ordering of the cfs_rq in rq->leaf_cfs_rq_list but this ordering is used to update and propagate the update from leaf down to root." Instead of trying to work through all these cases and trying to reproduce the very high loads that produced the lockup to begin with, simplify the code temporarily by reverting a9e7f6544b9c - which change was clearly not thought through completely. This (hopefully) gives us a kernel that doesn't lock up so people can continue to enjoy their holidays without worrying about regressions. ;-) [ mingo: Wrote changelog, fixed weird spelling in code comment while at it. ] Analyzed-by: Xie XiuQi Analyzed-by: Vincent Guittot Reported-by: Zhipeng Xie Reported-by: Sargun Dhillon Reported-by: Xie XiuQi Tested-by: Zhipeng Xie Tested-by: Sargun Dhillon Signed-off-by: Linus Torvalds Acked-by: Vincent Guittot Cc: # v4.13+ Cc: Bin Li Cc: Mike Galbraith Cc: Peter Zijlstra Cc: Tejun Heo Cc: Thomas Gleixner Fixes: a9e7f6544b9c ("sched/fair: Fix O(nr_cgroups) in load balance path") Link: http://lkml.kernel.org/r/1545879866-27809-1-git-send-email-xiexiuqi@huawei.com Signed-off-by: Ingo Molnar (backported from commit c40f7d74c741a907cfaeb73a7697081881c497d0) [ Connor Kuehl: context adjustments were required to remove 'cfs_rq_is_decayed()' and to merge the changes to 'update_blocked_averages()'. Also, I had to manually update old instances of 'for_each_leaf_cfs_rq_safe' to its successor which is introduced by this patch 'for_each_leaf_cfs_rq'. ] Signed-off-by: Connor Kuehl --- kernel/sched/fair.c | 44 ++++++++++---------------------------------- 1 file changed, 10 insertions(+), 34 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 7ad5fa326de1..3433cbe3e96c 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -313,10 +313,9 @@ static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq) } } -/* Iterate thr' all leaf cfs_rq's on a runqueue */ -#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \ - list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list, \ - leaf_cfs_rq_list) +/* Iterate through all leaf cfs_rq's on a runqueue: */ +#define for_each_leaf_cfs_rq(rq, cfs_rq) \ + list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list) /* Do the two (enqueued) entities belong to the same group ? */ static inline struct cfs_rq * @@ -409,8 +408,8 @@ static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq) { } -#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \ - for (cfs_rq = &rq->cfs, pos = NULL; cfs_rq; cfs_rq = pos) +#define for_each_leaf_cfs_rq(rq, cfs_rq) \ + for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL) static inline struct sched_entity *parent_entity(struct sched_entity *se) { @@ -6034,27 +6033,10 @@ static void attach_tasks(struct lb_env *env) #ifdef CONFIG_FAIR_GROUP_SCHED -static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq) -{ - if (cfs_rq->load.weight) - return false; - - if (cfs_rq->avg.load_sum) - return false; - - if (cfs_rq->avg.util_sum) - return false; - - if (cfs_rq->runnable_load_sum) - return false; - - return true; -} - -static void update_blocked_averages(int cpu) +static inline bool cfs_rq_istatic void update_blocked_averages(int cpu) { struct rq *rq = cpu_rq(cpu); - struct cfs_rq *cfs_rq, *pos; + struct cfs_rq *cfs_rq; unsigned long flags; raw_spin_lock_irqsave(&rq->lock, flags); @@ -6064,7 +6046,7 @@ static void update_blocked_averages(int cpu) * Iterates the task_group tree in a bottom up fashion, see * list_add_leaf_cfs_rq() for details. */ - for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) { + for_each_leaf_cfs_rq(rq, cfs_rq) { /* throttled entities do not contribute to load */ if (throttled_hierarchy(cfs_rq)) @@ -6073,12 +6055,6 @@ static void update_blocked_averages(int cpu) if (update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq)) update_tg_load_avg(cfs_rq, 0); - /* - * There can be a lot of idle CPU cgroups. Don't let fully - * decayed cfs_rqs linger on the list. - */ - if (cfs_rq_is_decayed(cfs_rq)) - list_del_leaf_cfs_rq(cfs_rq); } raw_spin_unlock_irqrestore(&rq->lock, flags); } @@ -8484,10 +8460,10 @@ const struct sched_class fair_sched_class = { #ifdef CONFIG_SCHED_DEBUG void print_cfs_stats(struct seq_file *m, int cpu) { - struct cfs_rq *cfs_rq, *pos; + struct cfs_rq *cfs_rq; rcu_read_lock(); - for_each_leaf_cfs_rq_safe(cpu_rq(cpu), cfs_rq, pos) + for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq) print_cfs_rq(m, cpu, cfs_rq); rcu_read_unlock(); }