Received: by 2002:a05:6902:102b:0:0:0:0 with SMTP id x11csp75478ybt; Tue, 30 Jun 2020 15:09:14 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzfZdMgoMpuyGIv2BL2tMAsho9nzZAcr3w4xhTR3O2HgkrAbKxU1WeTZ9jpPn3hxgtakqfF X-Received: by 2002:a50:cd1a:: with SMTP id z26mr26384468edi.120.1593554510876; Tue, 30 Jun 2020 15:01:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1593554510; cv=none; d=google.com; s=arc-20160816; b=WbpSCaUQJIVWsEzyzqf6VrGfkS1l79zRUn5FjbmVBnREgoJrFZEAasdeiyUAHH639j 5idp066xroI/2kUnDrDwLGtNhrEscoNV/H6Jx7qRRwi9j7NOPET8NBCxnliTNz4UGbFv aaJ2Do7Gn6vakcIzqe4Nxulnlbxi3fBUoLX6S6b+ei4uUPRtVUJb1d8U1po7HscKJQOY L9DDrhvkMVfxVF37Ufw3XhmHrSynTjpCEoUP8+Mo1ISs9G/Bk5ROk4DGFTactZu9cM1V BDPj9w+O/yoIYF66du2/vufimk2W4aRWCkHAAao3d30tTkWdORxVtSWvZo6MNHArAEb4 a9hA== 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=7QY1wQ1eyKuHxnCmngdykN0kML5Tdn5GmTEAfMzyRIo=; b=J80gvb8uOPg2NmsFoYQVqLABgXvR4/eo7srkUW/RjsyLBcrK5vPSS9wO9McTMng3ht EsZV99HSDmZdFLgeioq4QqjGkz5Wdhp8BsEwW06fO63sDULckUYwXueVUWHimVONlG3B mApRcX7OxI02WCvJkvLede3mXwI9HoyaXpw53sG99P6At/R6ke0w43epenFiQzx4GqLx wPA4o05yPHaR1E0tLaEXL2WuhtcVIPhi7/0EpuEa0Udg3K1AUwaa+1SswWj4Ivu7lqcY IlMx0QZTXT69+y0m9/P2gkfYc1h5ScDMYVt9TOPi9hP+UHKDyVVEchbtP0GzHeHsJFpA zsfA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@digitalocean.com header.s=google header.b=JSPkxnuW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 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. [23.128.96.18]) by mx.google.com with ESMTP id lo14si2555776ejb.244.2020.06.30.15.01.25; Tue, 30 Jun 2020 15:01:50 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; dkim=pass header.i=@digitalocean.com header.s=google header.b=JSPkxnuW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 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 S1728055AbgF3VdT (ORCPT + 99 others); Tue, 30 Jun 2020 17:33:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34364 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728033AbgF3VdM (ORCPT ); Tue, 30 Jun 2020 17:33:12 -0400 Received: from mail-pl1-x643.google.com (mail-pl1-x643.google.com [IPv6:2607:f8b0:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 09B0DC03E97A for ; Tue, 30 Jun 2020 14:33:12 -0700 (PDT) Received: by mail-pl1-x643.google.com with SMTP id h4so2923928plt.9 for ; Tue, 30 Jun 2020 14:33:12 -0700 (PDT) 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=7QY1wQ1eyKuHxnCmngdykN0kML5Tdn5GmTEAfMzyRIo=; b=JSPkxnuWb48gqwgBkWvFScNXQ+5vDbR8hMbr77t3tGeulUHGZMfItG/CI3c07E9MMV 4nX41wpw8DlRdfrqi8b/oPV8D7ZOOXSG1OYLFd1bvtN4PtohYR4XtP7gGyoPAetph3aY Ys5wn9bnRkHJ+c46zRylkfuTmGzKR8ex2ayW8= 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=7QY1wQ1eyKuHxnCmngdykN0kML5Tdn5GmTEAfMzyRIo=; b=clhotQ/0/MpTI6IIJrxr4/ui8CdugNLWSGOFtEVebz//V7uR16fJh5NHWV/4pZR0Ii QOTGgn4OszjanfyOGWTRlVaEewvSoTXEgdjXYlZNnLh5v6OJYPVNXjV/wwuLw0Y0fKje gDzTWkrVwSCuhxHB5sHx1QPbNvP2xLc/oGtdZKCqsuEwgTWfPGIf9ym/GXGpy7Uhh8Et /+P8yOM6JIUMzvG1KuF175DgaZM1S8YbpZXJ7WCg+HX6t6uiKvsA4s98hPaYtBYyPG4C qnbPMOeB55ADh8SK2kYkvRRhGQeEEuEVw2EzlbAF0ar7nmAFMgphaEcgyut6spYoxudr ZqrQ== X-Gm-Message-State: AOAM5330CTu818ivkCEyFwi17GLZumD8x65nld+uXS3ZnzYKOEh45UcI EM7BdWZpxWz30ofyIWGky/S+cw== X-Received: by 2002:a17:90b:94f:: with SMTP id dw15mr18328315pjb.199.1593552791377; Tue, 30 Jun 2020 14:33:11 -0700 (PDT) Received: from vpillai-dev.sfo2.internal.digitalocean.com ([138.68.32.68]) by smtp.gmail.com with ESMTPSA id w11sm3584943pfc.79.2020.06.30.14.33.10 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 30 Jun 2020 14:33:10 -0700 (PDT) From: Vineeth Remanan Pillai 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, subhra.mazumdar@oracle.com, fweisbec@gmail.com, keescook@chromium.org, kerrnel@google.com, Phil Auld , Aaron Lu , Aubrey Li , Valentin Schneider , Mel Gorman , Pawan Gupta , Paolo Bonzini , Joel Fernandes , joel@joelfernandes.org, vineethrp@gmail.com, Chen Yu , Christian Brauner , Vineeth Remanan Pillai Subject: [RFC PATCH 05/16] sched: Basic tracking of matching tasks Date: Tue, 30 Jun 2020 21:32:26 +0000 Message-Id: <2ae4e2f2d2b027d186365ce9d98abd6c430aaa0e.1593530334.git.vpillai@digitalocean.com> 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 4418f5cb8324..3c8dcc5ff039 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -683,10 +683,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 4b81301e3f21..b21bcab20da6 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 */ /* @@ -1347,6 +1487,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); @@ -1361,6 +1504,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 e44a43b87975..ae17507533a0 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -260,33 +260,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) @@ -447,33 +425,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 66e586adee18..c85c5a4bc21f 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1033,6 +1033,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 }; @@ -1112,6 +1116,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