From patchwork Fri Jan 13 14:12:33 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vincent Guittot X-Patchwork-Id: 43329 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp294355wrt; Fri, 13 Jan 2023 06:18:27 -0800 (PST) X-Google-Smtp-Source: AMrXdXvquwI47aznFJEe0VQ7YuaPMI9kln2Y0N+xtKO30w8+4pvlsVIJE29tknCQRH57VNoBcI98 X-Received: by 2002:a17:907:d681:b0:7c0:eb38:f8af with SMTP id wf1-20020a170907d68100b007c0eb38f8afmr68881539ejc.2.1673619506905; Fri, 13 Jan 2023 06:18:26 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673619506; cv=none; d=google.com; s=arc-20160816; b=tA2rvYGA37rPJ4QWmC6hR0jw+kc0NQxA735tK4vNrnHJ7FL3ubAaFHTts1W3qZMNOP nN9Q3o1RtewnhamtfuSgsK+/nnykTzIyIYyDPOcH44fk7jsf9HhXwX3pN3N2zYXWSoOx ibKjM5sUFanlFm7b1wEwHVX4/mVj7TRW4YEyyCbv0wrPXms5rGZ+w4rjKfXeO15dq/Os ANwNyZFI3vb+BfCFnmB+d/VI07m3xFCE6sfb329gQWmtgb8aRgPkAVBT/X8Ry6UaO9ZW 5NPjQB5gvR4beLY/5lXHsl4tIaiX/iXM7pz153UVWujV7maQi+ZAeCZn2ANhfEQxW+Mc HphQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=YWiIpOe2nNdT5aWZRMfGm3NcSfCw2CxcRRTzhzpvxrA=; b=XGnylhQPi0t5WZETigWwDdb/TqPqgulg2fWgVHOrZKTfjF0mbO3xCqtvk0uplGvzLL FqpnB4ZyrNKVIeXyhRz6DjxMWKrx6Jja6QZzGqYexssXYtvaPSvNp2g1eUU1k+XgGpvP vlCrVnnK7bD9UFIweeozT0TJ4QyjOoh/uBxwfCsSqDXL+FYiMJdUZz3NvRI8NV5ag2RJ agbDQYZENviyUbTMvhmWi1As7tE0oof6Ubw/3jDxQYO6S7a9QYNUkxlkDNQxHqhjq61o w5sEPDJ0v4aYqyBMSC69h66u/Pw0jcnbJjY5epdQhCUepH3slW3F3EvDjuBv82buLpA/ tFyQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BywjmuYY; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id qo14-20020a170907874e00b007c4fb1332c0si17696500ejc.174.2023.01.13.06.17.54; Fri, 13 Jan 2023 06:18:26 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=BywjmuYY; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S241149AbjAMOP7 (ORCPT + 99 others); Fri, 13 Jan 2023 09:15:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40432 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242066AbjAMONy (ORCPT ); Fri, 13 Jan 2023 09:13:54 -0500 Received: from mail-wm1-x331.google.com (mail-wm1-x331.google.com [IPv6:2a00:1450:4864:20::331]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0F4FB3590A for ; Fri, 13 Jan 2023 06:12:52 -0800 (PST) Received: by mail-wm1-x331.google.com with SMTP id q8so3556792wmo.5 for ; Fri, 13 Jan 2023 06:12:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=YWiIpOe2nNdT5aWZRMfGm3NcSfCw2CxcRRTzhzpvxrA=; b=BywjmuYYDQL0B21BIKa7iT2z+zdJTdpWyljP9Agfj2597r0VBHFUwD+R67fS51aQp7 VbuIrgy3kWGXYiQ+AbS40a9O3nOPS9zQ7D3TFtpaiZfn/uqD3EHq44UHZjX3is0nupNv N3xfnI864WldAvYuq/c2/aof7J0TL/NuZUi6kM22NjmqFjasPhF2FPEtAdcms4XvNet8 itm+i4Y4ADmVmnsCKI+/u+MNMrocBIza8Wircmv8MtKQ4+e0VcHPCl4ioHcGfoq3dnWP fI0NUB55RCG2tu31OHi5U1koTyaUjudyfB8StE8p0F8t3cp3XWaNYF7wC76RWyz9yC5D lgqw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=YWiIpOe2nNdT5aWZRMfGm3NcSfCw2CxcRRTzhzpvxrA=; b=bJ791cHXtPzZfMGMUYx9iY5h4em9Fus5AT1ALo+Aaha8uz5R2i69b5UUC35MLbhkEZ Jdwc+X5URABogMyKk+esSFf17KOpRt7QWFjqI0SGnlvh59opR8a63NpPv68Fm7kqj16o 43F12nzAi3t/dLzPjjQCck+kwGoB2CTrAAHqnymxN0F2x5/1NDFZ2KLkyi4q1aiISR8Y LQVALTqfbDizTFokKEZISWpH+T/ORpBzSZ6/47WZ984uLMOmdx6BWirolUyoQokxcq6e Xmu/b85Jcsn1AY+t3j/3h4juhea77Cras3S4G55KN9vmNi482y28vmXkyGgEDQIOOFYZ kngA== X-Gm-Message-State: AFqh2kooOHOV9z5HjyEK22lkY1zRIfUhPle7pntWXniR7TFGvrK0VG1S CIoSw0ZbQUueVNHooB/ei/IJHg== X-Received: by 2002:a05:600c:510b:b0:3da:2090:d404 with SMTP id o11-20020a05600c510b00b003da2090d404mr2041306wms.18.1673619170540; Fri, 13 Jan 2023 06:12:50 -0800 (PST) Received: from vingu-book.. ([2a01:e0a:f:6020:1563:65bf:c344:661e]) by smtp.gmail.com with ESMTPSA id f7-20020a5d6647000000b002bbeb700c38sm13869919wrw.91.2023.01.13.06.12.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 13 Jan 2023 06:12:49 -0800 (PST) From: Vincent Guittot To: mingo@redhat.com, peterz@infradead.org, juri.lelli@redhat.com, dietmar.eggemann@arm.com, rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de, bristot@redhat.com, vschneid@redhat.com, linux-kernel@vger.kernel.org, parth@linux.ibm.com, cgroups@vger.kernel.org Cc: qyousef@layalina.io, chris.hyser@oracle.com, patrick.bellasi@matbug.net, David.Laight@aculab.com, pjt@google.com, pavel@ucw.cz, tj@kernel.org, qperret@google.com, tim.c.chen@linux.intel.com, joshdon@google.com, timj@gnu.org, kprateek.nayak@amd.com, yu.c.chen@intel.com, youssefesmat@chromium.org, joel@joelfernandes.org, Vincent Guittot Subject: [PATCH v10 8/9] sched/fair: Add latency list Date: Fri, 13 Jan 2023 15:12:33 +0100 Message-Id: <20230113141234.260128-9-vincent.guittot@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230113141234.260128-1-vincent.guittot@linaro.org> References: <20230113141234.260128-1-vincent.guittot@linaro.org> MIME-Version: 1.0 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_NONE, SPF_HELO_NONE,SPF_PASS autolearn=unavailable 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-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1754917248066803425?= X-GMAIL-MSGID: =?utf-8?q?1754917248066803425?= Add a rb tree for latency sensitive entities so we can schedule the most sensitive one first even when it failed to preempt current at wakeup or when it got quickly preempted by another entity of higher priority. In order to keep fairness, the latency is used once at wakeup to get a minimum slice and not during the following scheduling slice to prevent long running entity to got more running time than allocated to his nice priority. The rb tree enables to cover the last corner case where latency sensitive entity can't got schedule quickly after the wakeup. Signed-off-by: Vincent Guittot Tested-by: K Prateek Nayak --- include/linux/sched.h | 1 + kernel/sched/core.c | 1 + kernel/sched/fair.c | 95 +++++++++++++++++++++++++++++++++++++++++-- kernel/sched/sched.h | 1 + 4 files changed, 95 insertions(+), 3 deletions(-) diff --git a/include/linux/sched.h b/include/linux/sched.h index 38decae3e156..41bb92be5ecc 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -548,6 +548,7 @@ struct sched_entity { /* For load-balancing: */ struct load_weight load; struct rb_node run_node; + struct rb_node latency_node; struct list_head group_node; unsigned int on_rq; diff --git a/kernel/sched/core.c b/kernel/sched/core.c index 6798c9a297d6..5c99f67c7e7b 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -4390,6 +4390,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p) p->se.nr_migrations = 0; p->se.vruntime = 0; INIT_LIST_HEAD(&p->se.group_node); + RB_CLEAR_NODE(&p->se.latency_node); #ifdef CONFIG_FAIR_GROUP_SCHED p->se.cfs_rq = NULL; diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index a4bfa03d096c..a8f0e32431e2 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -680,7 +680,76 @@ struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq) return __node_2_se(last); } +#endif + +/************************************************************** + * Scheduling class tree data structure manipulation methods: + * for latency + */ + +static inline bool latency_before(struct sched_entity *a, + struct sched_entity *b) +{ + return (s64)(a->vruntime + a->latency_offset - b->vruntime - b->latency_offset) < 0; +} + +#define __latency_node_2_se(node) \ + rb_entry((node), struct sched_entity, latency_node) + +static inline bool __latency_less(struct rb_node *a, const struct rb_node *b) +{ + return latency_before(__latency_node_2_se(a), __latency_node_2_se(b)); +} + +/* + * Enqueue an entity into the latency rb-tree: + */ +static void __enqueue_latency(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) +{ + + /* Only latency sensitive entity can be added to the list */ + if (se->latency_offset >= 0) + return; + + if (!RB_EMPTY_NODE(&se->latency_node)) + return; + + /* + * An execution time less than sysctl_sched_min_granularity means that + * the entity has been preempted by a higher sched class or an entity + * with higher latency constraint. + * Put it back in the list so it gets a chance to run 1st during the + * next slice. + */ + if (!(flags & ENQUEUE_WAKEUP)) { + u64 delta_exec = se->sum_exec_runtime - se->prev_sum_exec_runtime; + + if (delta_exec >= sysctl_sched_min_granularity) + return; + } + + rb_add_cached(&se->latency_node, &cfs_rq->latency_timeline, __latency_less); +} + +static void __dequeue_latency(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + if (!RB_EMPTY_NODE(&se->latency_node)) { + rb_erase_cached(&se->latency_node, &cfs_rq->latency_timeline); + RB_CLEAR_NODE(&se->latency_node); + } +} + +static struct sched_entity *__pick_first_latency(struct cfs_rq *cfs_rq) +{ + struct rb_node *left = rb_first_cached(&cfs_rq->latency_timeline); + + if (!left) + return NULL; + + return __latency_node_2_se(left); +} +#ifdef CONFIG_SCHED_DEBUG /************************************************************** * Scheduling class statistics methods: */ @@ -4751,8 +4820,10 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) check_schedstat_required(); update_stats_enqueue_fair(cfs_rq, se, flags); check_spread(cfs_rq, se); - if (!curr) + if (!curr) { __enqueue_entity(cfs_rq, se); + __enqueue_latency(cfs_rq, se, flags); + } se->on_rq = 1; if (cfs_rq->nr_running == 1) { @@ -4838,8 +4909,10 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) clear_buddies(cfs_rq, se); - if (se != cfs_rq->curr) + if (se != cfs_rq->curr) { __dequeue_entity(cfs_rq, se); + __dequeue_latency(cfs_rq, se); + } se->on_rq = 0; account_entity_dequeue(cfs_rq, se); @@ -4928,6 +5001,7 @@ set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) */ update_stats_wait_end_fair(cfs_rq, se); __dequeue_entity(cfs_rq, se); + __dequeue_latency(cfs_rq, se); update_load_avg(cfs_rq, se, UPDATE_TG); } @@ -4966,7 +5040,7 @@ static struct sched_entity * pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr) { struct sched_entity *left = __pick_first_entity(cfs_rq); - struct sched_entity *se; + struct sched_entity *latency, *se; /* * If curr is set we have to see if its left of the leftmost entity @@ -5008,6 +5082,12 @@ pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr) se = cfs_rq->last; } + /* Check for latency sensitive entity waiting for running */ + latency = __pick_first_latency(cfs_rq); + if (latency && (latency != se) && + wakeup_preempt_entity(latency, se) < 1) + se = latency; + return se; } @@ -5031,6 +5111,7 @@ static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) update_stats_wait_start_fair(cfs_rq, prev); /* Put 'current' back into the tree. */ __enqueue_entity(cfs_rq, prev); + __enqueue_latency(cfs_rq, prev, 0); /* in !on_rq case, update occurred at dequeue */ update_load_avg(cfs_rq, prev, 0); } @@ -12244,6 +12325,7 @@ static void set_next_task_fair(struct rq *rq, struct task_struct *p, bool first) void init_cfs_rq(struct cfs_rq *cfs_rq) { cfs_rq->tasks_timeline = RB_ROOT_CACHED; + cfs_rq->latency_timeline = RB_ROOT_CACHED; u64_u32_store(cfs_rq->min_vruntime, (u64)(-(1LL << 20))); #ifdef CONFIG_SMP raw_spin_lock_init(&cfs_rq->removed.lock); @@ -12552,8 +12634,15 @@ int sched_group_set_latency(struct task_group *tg, s64 latency) for_each_possible_cpu(i) { struct sched_entity *se = tg->se[i]; + struct rq *rq = cpu_rq(i); + struct rq_flags rf; + + rq_lock_irqsave(rq, &rf); + __dequeue_latency(se->cfs_rq, se); WRITE_ONCE(se->latency_offset, latency); + + rq_unlock_irqrestore(rq, &rf); } mutex_unlock(&shares_mutex); diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 5a4ce8e61f47..186873bb41e2 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -575,6 +575,7 @@ struct cfs_rq { #endif struct rb_root_cached tasks_timeline; + struct rb_root_cached latency_timeline; /* * 'curr' points to currently running entity on this cfs_rq.