From patchwork Tue Oct 3 10:42:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: tip-bot2 for Thomas Gleixner X-Patchwork-Id: 147804 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:612c:2a8e:b0:403:3b70:6f57 with SMTP id in14csp1992775vqb; Tue, 3 Oct 2023 03:43:00 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHTp/F0kJzCBnTjxJGY9HmVkLxw77LS9pPbTk96oFfAU7+0OYtjesW66CdzegGETmFqDLgv X-Received: by 2002:a05:6a21:33a4:b0:161:7a0c:3c26 with SMTP id yy36-20020a056a2133a400b001617a0c3c26mr16273976pzb.27.1696329780290; Tue, 03 Oct 2023 03:43:00 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1696329780; cv=none; d=google.com; s=arc-20160816; b=BEdwk7K9FLCiglPLZQ4bWvnLTDxF0zEHQ0YElxD/IAVzwdLx8MQqpPKrI4IJrivPAs e9eawOqXilCIzzK0zIIcMlj5TB6ieSxJxxsC20merYzMA6cfFMQewwOqzb+5YYz7VsHC NJ5NwzAlIcrgxdQBo3nNVD0PJFhY4w7eZ3D7kLp3E++rfIzORFqKSMR5dhoPQF7e337t /oLOEaSPZMQ9qmQ5pn+lCHtZGyMKT1fAAwtn/XiyQsHNkz8kXXtj+JIfmJD/8q8R3Et2 EnmY6BO/w+1f4Qu7NHay/9mB/snnbGfK1enlCuYApSUAMm5WGp7AbqnsQ8Cx2SVXSFV3 YNxA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:robot-unsubscribe :robot-id:message-id:mime-version:references:in-reply-to:cc:subject :to:reply-to:sender:from:dkim-signature:dkim-signature:date; bh=X9ftg0JpBJiHaMhlIbJUcgMI8xyvm5PQSTdqLJVFKz8=; fh=vJHlbD/W9GC5/H9ChKR4gZgcxjVkniUboCTfwstvRqI=; b=Mrzphqv9hO//0i+DdshDOh0NzT0wQntHr9eEH6s2V1x+TO9RiyKMxX7ecy2UdA7CU7 muhHllClAvVXApoTQvXiJL8rFEGLD3eRShUEaT37AKZl/kuMHAftxfHcLFp993JUVvSK CARRgQ8n7IBaMPRTfoRHhqRog7VzqlrzG1Ru+jP6G6Mc0eu1hvTko1QsULScJvf9MZd1 L9WmYi+8flnvCk0SYapFaN1SsOLl4fSt+pB/7hmOLdhZauKIlDx0HjuhRqnlqXghbGCh kVaH7EvHC5uZ5idGahn8qvpChd5kjWfNM1HYrtdeoY/T6TRdd3JUPyP52Uel5QsAg8Zo OkWg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=HsjtQn6s; dkim=neutral (no key) header.i=@linutronix.de header.s=2020e header.b=Q156DRbV; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: from snail.vger.email (snail.vger.email. [2620:137:e000::3:7]) by mx.google.com with ESMTPS id c5-20020a056a000ac500b0068a692b67b0si1312008pfl.104.2023.10.03.03.42.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 03 Oct 2023 03:43:00 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7; Authentication-Results: mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=HsjtQn6s; dkim=neutral (no key) header.i=@linutronix.de header.s=2020e header.b=Q156DRbV; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id 8A873815D7EC; Tue, 3 Oct 2023 03:42:59 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231812AbjJCKmu (ORCPT + 19 others); Tue, 3 Oct 2023 06:42:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35476 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230215AbjJCKmo (ORCPT ); Tue, 3 Oct 2023 06:42:44 -0400 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F4170B4; Tue, 3 Oct 2023 03:42:39 -0700 (PDT) Date: Tue, 03 Oct 2023 10:42:36 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1696329758; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=X9ftg0JpBJiHaMhlIbJUcgMI8xyvm5PQSTdqLJVFKz8=; b=HsjtQn6sY+Uu1njmyST3TlmSi4K+fkU6XS+P1MSJcuXgH0VLxcR9ZNGxX3fgnICHvDfr+3 WwBaBH2kaO/JC62LXFWeRidfLnwfFlM9hRrYbfp8frbBl43kW3u0mUriUo8RRGqCfBel/o 7bATTnPSpbFo54ivO/xMR17/0oDNzQro12uH7tDW6nO43HORMAqAFolqdTKzkXg9ykMhUg mDe86KIeB2Bv18ZwVf2x0RHVesYaOp0Ns27lUbT2WddZ7EEnO3jv6dUncECGR/oQHhkyuX v3NS+mzyJwAXWMjChp7/2v/4aw6+nbhqQSQdgg/+rjQpet5NDcLECXjC6wNqhA== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1696329758; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=X9ftg0JpBJiHaMhlIbJUcgMI8xyvm5PQSTdqLJVFKz8=; b=Q156DRbVBEdSef9Eix2GX4vhTT3t9BOg2GC0v99IaTa2dEWjjuW8WdAeOJLqvK4n4QsyBK xT5xaRyTpA6Ou9Cg== From: "tip-bot2 for Benjamin Segall" Sender: tip-bot2@linutronix.de Reply-to: linux-kernel@vger.kernel.org To: linux-tip-commits@vger.kernel.org Subject: [tip: sched/urgent] sched/fair: Fix pick_eevdf() Cc: Ben Segall , "Peter Zijlstra (Intel)" , x86@kernel.org, linux-kernel@vger.kernel.org In-Reply-To: References: MIME-Version: 1.0 Message-ID: <169632975707.3135.15953962497014148115.tip-bot2@tip-bot2> Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Tue, 03 Oct 2023 03:42:59 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1778730696031693615 X-GMAIL-MSGID: 1778730696031693615 The following commit has been merged into the sched/urgent branch of tip: Commit-ID: 561c58efd2394d76a32254d91e4b1de8ecdeb5c8 Gitweb: https://git.kernel.org/tip/561c58efd2394d76a32254d91e4b1de8ecdeb5c8 Author: Benjamin Segall AuthorDate: Fri, 29 Sep 2023 17:09:30 -07:00 Committer: Peter Zijlstra CommitterDate: Tue, 03 Oct 2023 12:32:30 +02:00 sched/fair: Fix pick_eevdf() The old pick_eevdf() could fail to find the actual earliest eligible deadline when it descended to the right looking for min_deadline, but it turned out that that min_deadline wasn't actually eligible. In that case we need to go back and search through any left branches we skipped looking for the actual best _eligible_ min_deadline. This is more expensive, but still O(log n), and at worst should only involve descending two branches of the rbtree. I've run this through a userspace stress test (thank you tools/lib/rbtree.c), so hopefully this implementation doesn't miss any corner cases. Fixes: 147f3efaa241 ("sched/fair: Implement an EEVDF-like scheduling policy") Signed-off-by: Ben Segall Signed-off-by: Peter Zijlstra (Intel) Link: https://lkml.kernel.org/r/xm261qego72d.fsf_-_@google.com --- kernel/sched/fair.c | 72 +++++++++++++++++++++++++++++++++++--------- 1 file changed, 58 insertions(+), 14 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index ef7490c..929d21d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -872,14 +872,16 @@ struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) * * Which allows an EDF like search on (sub)trees. */ -static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) +static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq) { struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node; struct sched_entity *curr = cfs_rq->curr; struct sched_entity *best = NULL; + struct sched_entity *best_left = NULL; if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr))) curr = NULL; + best = curr; /* * Once selected, run a task until it either becomes non-eligible or @@ -900,33 +902,75 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) } /* - * If this entity has an earlier deadline than the previous - * best, take this one. If it also has the earliest deadline - * of its subtree, we're done. + * Now we heap search eligible trees for the best (min_)deadline */ - if (!best || deadline_gt(deadline, best, se)) { + if (!best || deadline_gt(deadline, best, se)) best = se; - if (best->deadline == best->min_deadline) - break; - } /* - * If the earlest deadline in this subtree is in the fully - * eligible left half of our space, go there. + * Every se in a left branch is eligible, keep track of the + * branch with the best min_deadline */ + if (node->rb_left) { + struct sched_entity *left = __node_2_se(node->rb_left); + + if (!best_left || deadline_gt(min_deadline, best_left, left)) + best_left = left; + + /* + * min_deadline is in the left branch. rb_left and all + * descendants are eligible, so immediately switch to the second + * loop. + */ + if (left->min_deadline == se->min_deadline) + break; + } + + /* min_deadline is at this node, no need to look right */ + if (se->deadline == se->min_deadline) + break; + + /* else min_deadline is in the right branch. */ + node = node->rb_right; + } + + /* + * We ran into an eligible node which is itself the best. + * (Or nr_running == 0 and both are NULL) + */ + if (!best_left || (s64)(best_left->min_deadline - best->deadline) > 0) + return best; + + /* + * Now best_left and all of its children are eligible, and we are just + * looking for deadline == min_deadline + */ + node = &best_left->run_node; + while (node) { + struct sched_entity *se = __node_2_se(node); + + /* min_deadline is the current node */ + if (se->deadline == se->min_deadline) + return se; + + /* min_deadline is in the left branch */ if (node->rb_left && __node_2_se(node->rb_left)->min_deadline == se->min_deadline) { node = node->rb_left; continue; } + /* else min_deadline is in the right branch */ node = node->rb_right; } + return NULL; +} - if (!best || (curr && deadline_gt(deadline, best, curr))) - best = curr; +static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) +{ + struct sched_entity *se = __pick_eevdf(cfs_rq); - if (unlikely(!best)) { + if (!se) { struct sched_entity *left = __pick_first_entity(cfs_rq); if (left) { pr_err("EEVDF scheduling fail, picking leftmost\n"); @@ -934,7 +978,7 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) } } - return best; + return se; } #ifdef CONFIG_SCHED_DEBUG