Received: by 2002:a25:c205:0:0:0:0:0 with SMTP id s5csp4704304ybf; Wed, 4 Mar 2020 09:03:29 -0800 (PST) X-Google-Smtp-Source: ADFU+vvMnB2dknPwbeLjjJuY420xY2PenjTwqyPf6kzkeDP25/BorSkI5fRH0Ia61pR+H27eR2oT X-Received: by 2002:a9d:5e8a:: with SMTP id f10mr3308550otl.143.1583341409052; Wed, 04 Mar 2020 09:03:29 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1583341409; cv=none; d=google.com; s=arc-20160816; b=N3HsDDbMch2RMXBMRRlBbpFN2PCuAu8w+OcJ5DVtqvAsDCL5utTjEOVWqaex69ugD1 2Z8VlLCTH1UXZ5c4Ytt5+eiUcGWknAQiwJpt91W0453XlIP5GoJ4kA0xp2wchSzI4HYw a9ItJ/SjATXnFhFVXWawfupzgtpZieXaDqgTkSoR14E8DpN7/KnnMuxdLLFN9OYb/n4L 3qKDMRaTsJcnMqTg1yO7dbUm36pf1ghMo2UwsuWrEMWJ1fInjIdMG1cw0cAn7f4G61a4 QAX08NZ5+lHhEZLI0m6JoYli5gVp/nVxk5g1Fhydh7dxE1Fgr5kwlZbMG3R2J9UVJI61 JtfA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:dkim-signature; bh=ZyHCgpJWx2dM8bJksmjsLOIcKqB79U5Ve9vzVTtYcyE=; b=xFFd2LkM5I5mtVJHU9Pxim2akUKf0RDNvO9K0C/CHh+KoWxyv9Ra1Jbz2BwnqshxA4 1YK7SilJdfNqCov0ON/Dhtn8oEmi5Rhn4ZPaIcBT4g+hMQcjEgIBgPO6YGqHaqrWMVVB Z+kCqXGSYDo+jW+8R8yB54/Ri/KP82Z8K9VGiQKXii2YUnNbw9Jo6l77LBNP8Dx6NHLp r4IXulY+vdnGkPYVQ1ve4729v7qsQYwB4Eu4AIvduTEkYDrY3uOU+DLnAwWyqPD/BIqX 0tl/0qWOL9F/O6zbjL3j9KQhu+7gjGU+SifYtaFA9YMmIkQHyToaiY/JbK773zu39mkD 82uQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@digitalocean.com header.s=google header.b=bAiZVvmr; 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=REJECT sp=REJECT dis=NONE) header.from=digitalocean.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id s6si1521267otq.115.2020.03.04.09.03.11; Wed, 04 Mar 2020 09:03:29 -0800 (PST) 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=@digitalocean.com header.s=google header.b=bAiZVvmr; 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=REJECT sp=REJECT dis=NONE) header.from=digitalocean.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2388444AbgCDRAo (ORCPT + 99 others); Wed, 4 Mar 2020 12:00:44 -0500 Received: from mail-qv1-f67.google.com ([209.85.219.67]:46749 "EHLO mail-qv1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2388350AbgCDRAP (ORCPT ); Wed, 4 Mar 2020 12:00:15 -0500 Received: by mail-qv1-f67.google.com with SMTP id m2so1082539qvu.13 for ; Wed, 04 Mar 2020 09:00:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=digitalocean.com; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :in-reply-to:references; bh=ZyHCgpJWx2dM8bJksmjsLOIcKqB79U5Ve9vzVTtYcyE=; b=bAiZVvmrcVvDix3MF/oHACreryqJJQ+SaV82wOvf2c15qef5AR2gNC5QANTivavI+K QVUUAekhg2pFGjOB5WwPqYgZcbkVFF/c5pVlBwCFtS90s3WrG4TScxhud96pGHQnhqWP WmOfnxTVWF2aoIhYKJwDGnp1DcqpkwIcAVskw= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:in-reply-to:references; bh=ZyHCgpJWx2dM8bJksmjsLOIcKqB79U5Ve9vzVTtYcyE=; b=RlTEz5cdubX7Gg1jS8PQt+FJKTgiRftSMbLfUXJVjoKkW7XIzAuGAyz6h9fvfRDxNt PQ1ibiA2RR8caEDrXX791U6+Ns8/6D3u93aWSCw4/Pz36DR6p41FeWHKQ4/2r/rkcspX zRNTzay8epxLTqtGJ1ZcK1wKAXdkg1oJ8Rbp9eIQs33ftXs9fhJDCoiESLRiS1AXck6H GHIh8ek1BKOS1zrzQcFEDNMZ5tPp0/O4bQq9Dk2f4yA3zn7w4Z4RdIP9ND9ilbrLuq2d sP5eMO1SS+Ig6EUweU6wyl3jwKcnZrspdTHVILgyp8XkxetBdspHDyiJ+mMaxiobry/3 WZ0g== X-Gm-Message-State: ANhLgQ3iXe29KqH4Je3SN2lBRH+iiORe9F7OB9rp/3Ysa5XLlf/zsmK9 +xO1jDhgg/sUqkCBratu3pqDIw== X-Received: by 2002:ad4:4b21:: with SMTP id s1mr2919346qvw.81.1583341212380; Wed, 04 Mar 2020 09:00:12 -0800 (PST) Received: from s2r5node9 ([162.243.188.99]) by smtp.gmail.com with ESMTPSA id t1sm12421866qtr.94.2020.03.04.09.00.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 04 Mar 2020 09:00:11 -0800 (PST) From: vpillai To: Nishanth Aravamudan , Julien Desfossez , Peter Zijlstra , Tim Chen , mingo@kernel.org, tglx@linutronix.de, pjt@google.com, torvalds@linux-foundation.org Cc: linux-kernel@vger.kernel.org, fweisbec@gmail.com, keescook@chromium.org, kerrnel@google.com, Phil Auld , Aaron Lu , Aubrey Li , aubrey.li@linux.intel.com, Valentin Schneider , Mel Gorman , Pawan Gupta , Paolo Bonzini , Joel Fernandes , joel@joelfernandes.org, Vineeth Remanan Pillai Subject: [RFC PATCH 05/13] sched: Basic tracking of matching tasks Date: Wed, 4 Mar 2020 16:59:55 +0000 Message-Id: X-Mailer: git-send-email 2.17.1 In-Reply-To: References: In-Reply-To: References: Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Peter Zijlstra Introduce task_struct::core_cookie as an opaque identifier for core scheduling. When enabled; core scheduling will only allow matching task to be on the core; where idle matches everything. When task_struct::core_cookie is set (and core scheduling is enabled) these tasks are indexed in a second RB-tree, first on cookie value then on scheduling function, such that matching task selection always finds the most elegible match. NOTE: *shudder* at the overhead... NOTE: *sigh*, a 3rd copy of the scheduling function; the alternative is per class tracking of cookies and that just duplicates a lot of stuff for no raisin (the 2nd copy lives in the rt-mutex PI code). Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Vineeth Remanan Pillai Signed-off-by: Julien Desfossez --- include/linux/sched.h | 8 ++- kernel/sched/core.c | 146 ++++++++++++++++++++++++++++++++++++++++++ kernel/sched/fair.c | 46 ------------- kernel/sched/sched.h | 55 ++++++++++++++++ 4 files changed, 208 insertions(+), 47 deletions(-) diff --git a/include/linux/sched.h b/include/linux/sched.h index 716ad1d8d95e..80ec54706282 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -680,10 +680,16 @@ struct task_struct { const struct sched_class *sched_class; struct sched_entity se; struct sched_rt_entity rt; + struct sched_dl_entity dl; + +#ifdef CONFIG_SCHED_CORE + struct rb_node core_node; + unsigned long core_cookie; +#endif + #ifdef CONFIG_CGROUP_SCHED struct task_group *sched_task_group; #endif - struct sched_dl_entity dl; #ifdef CONFIG_UCLAMP_TASK /* Clamp values requested for a scheduling entity */ diff --git a/kernel/sched/core.c b/kernel/sched/core.c index ba17ff8a8663..452ce5bb9321 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -77,6 +77,141 @@ int sysctl_sched_rt_runtime = 950000; DEFINE_STATIC_KEY_FALSE(__sched_core_enabled); +/* kernel prio, less is more */ +static inline int __task_prio(struct task_struct *p) +{ + if (p->sched_class == &stop_sched_class) /* trumps deadline */ + return -2; + + if (rt_prio(p->prio)) /* includes deadline */ + return p->prio; /* [-1, 99] */ + + if (p->sched_class == &idle_sched_class) + return MAX_RT_PRIO + NICE_WIDTH; /* 140 */ + + return MAX_RT_PRIO + MAX_NICE; /* 120, squash fair */ +} + +/* + * l(a,b) + * le(a,b) := !l(b,a) + * g(a,b) := l(b,a) + * ge(a,b) := !l(a,b) + */ + +/* real prio, less is less */ +static inline bool prio_less(struct task_struct *a, struct task_struct *b) +{ + + int pa = __task_prio(a), pb = __task_prio(b); + + if (-pa < -pb) + return true; + + if (-pb < -pa) + return false; + + if (pa == -1) /* dl_prio() doesn't work because of stop_class above */ + return !dl_time_before(a->dl.deadline, b->dl.deadline); + + if (pa == MAX_RT_PRIO + MAX_NICE) { /* fair */ + u64 vruntime = b->se.vruntime; + + /* + * Normalize the vruntime if tasks are in different cpus. + */ + if (task_cpu(a) != task_cpu(b)) { + vruntime -= task_cfs_rq(b)->min_vruntime; + vruntime += task_cfs_rq(a)->min_vruntime; + } + + return !((s64)(a->se.vruntime - vruntime) <= 0); + } + + return false; +} + +static inline bool __sched_core_less(struct task_struct *a, struct task_struct *b) +{ + if (a->core_cookie < b->core_cookie) + return true; + + if (a->core_cookie > b->core_cookie) + return false; + + /* flip prio, so high prio is leftmost */ + if (prio_less(b, a)) + return true; + + return false; +} + +static void sched_core_enqueue(struct rq *rq, struct task_struct *p) +{ + struct rb_node *parent, **node; + struct task_struct *node_task; + + rq->core->core_task_seq++; + + if (!p->core_cookie) + return; + + node = &rq->core_tree.rb_node; + parent = *node; + + while (*node) { + node_task = container_of(*node, struct task_struct, core_node); + parent = *node; + + if (__sched_core_less(p, node_task)) + node = &parent->rb_left; + else + node = &parent->rb_right; + } + + rb_link_node(&p->core_node, parent, node); + rb_insert_color(&p->core_node, &rq->core_tree); +} + +static void sched_core_dequeue(struct rq *rq, struct task_struct *p) +{ + rq->core->core_task_seq++; + + if (!p->core_cookie) + return; + + rb_erase(&p->core_node, &rq->core_tree); +} + +/* + * Find left-most (aka, highest priority) task matching @cookie. + */ +static struct task_struct *sched_core_find(struct rq *rq, unsigned long cookie) +{ + struct rb_node *node = rq->core_tree.rb_node; + struct task_struct *node_task, *match; + + /* + * The idle task always matches any cookie! + */ + match = idle_sched_class.pick_task(rq); + + while (node) { + node_task = container_of(node, struct task_struct, core_node); + + if (cookie < node_task->core_cookie) { + node = node->rb_left; + } else if (cookie > node_task->core_cookie) { + node = node->rb_right; + } else { + match = node_task; + node = node->rb_left; + } + } + + return match; +} + /* * The static-key + stop-machine variable are needed such that: * @@ -135,6 +270,11 @@ void sched_core_put(void) mutex_unlock(&sched_core_mutex); } +#else /* !CONFIG_SCHED_CORE */ + +static inline void sched_core_enqueue(struct rq *rq, struct task_struct *p) { } +static inline void sched_core_dequeue(struct rq *rq, struct task_struct *p) { } + #endif /* CONFIG_SCHED_CORE */ /* @@ -1354,6 +1494,9 @@ static inline void init_uclamp(void) { } static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags) { + if (sched_core_enabled(rq)) + sched_core_enqueue(rq, p); + if (!(flags & ENQUEUE_NOCLOCK)) update_rq_clock(rq); @@ -1368,6 +1511,9 @@ static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags) static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags) { + if (sched_core_enabled(rq)) + sched_core_dequeue(rq, p); + if (!(flags & DEQUEUE_NOCLOCK)) update_rq_clock(rq); diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index cffc59a8b481..d6c932e8d554 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -247,33 +247,11 @@ const struct sched_class fair_sched_class; */ #ifdef CONFIG_FAIR_GROUP_SCHED -static inline struct task_struct *task_of(struct sched_entity *se) -{ - SCHED_WARN_ON(!entity_is_task(se)); - return container_of(se, struct task_struct, se); -} /* Walk up scheduling entities hierarchy */ #define for_each_sched_entity(se) \ for (; se; se = se->parent) -static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) -{ - return p->se.cfs_rq; -} - -/* runqueue on which this entity is (to be) queued */ -static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) -{ - return se->cfs_rq; -} - -/* runqueue "owned" by this group */ -static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) -{ - return grp->my_q; -} - static inline void cfs_rq_tg_path(struct cfs_rq *cfs_rq, char *path, int len) { if (!path) @@ -434,33 +412,9 @@ find_matching_se(struct sched_entity **se, struct sched_entity **pse) #else /* !CONFIG_FAIR_GROUP_SCHED */ -static inline struct task_struct *task_of(struct sched_entity *se) -{ - return container_of(se, struct task_struct, se); -} - #define for_each_sched_entity(se) \ for (; se; se = NULL) -static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) -{ - return &task_rq(p)->cfs; -} - -static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) -{ - struct task_struct *p = task_of(se); - struct rq *rq = task_rq(p); - - return &rq->cfs; -} - -/* runqueue "owned" by this group */ -static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) -{ - return NULL; -} - static inline void cfs_rq_tg_path(struct cfs_rq *cfs_rq, char *path, int len) { if (path) diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index a3941b2ee29e..a38ae770dfd6 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1004,6 +1004,10 @@ struct rq { /* per rq */ struct rq *core; unsigned int core_enabled; + struct rb_root core_tree; + + /* shared state */ + unsigned int core_task_seq; #endif }; @@ -1083,6 +1087,57 @@ DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); #define cpu_curr(cpu) (cpu_rq(cpu)->curr) #define raw_rq() raw_cpu_ptr(&runqueues) +#ifdef CONFIG_FAIR_GROUP_SCHED +static inline struct task_struct *task_of(struct sched_entity *se) +{ + SCHED_WARN_ON(!entity_is_task(se)); + return container_of(se, struct task_struct, se); +} + +static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) +{ + return p->se.cfs_rq; +} + +/* runqueue on which this entity is (to be) queued */ +static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) +{ + return se->cfs_rq; +} + +/* runqueue "owned" by this group */ +static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) +{ + return grp->my_q; +} + +#else + +static inline struct task_struct *task_of(struct sched_entity *se) +{ + return container_of(se, struct task_struct, se); +} + +static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) +{ + return &task_rq(p)->cfs; +} + +static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) +{ + struct task_struct *p = task_of(se); + struct rq *rq = task_rq(p); + + return &rq->cfs; +} + +/* runqueue "owned" by this group */ +static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) +{ + return NULL; +} +#endif + extern void update_rq_clock(struct rq *rq); static inline u64 __rq_clock_broken(struct rq *rq) -- 2.17.1