Received: by 2002:a05:6a10:6744:0:0:0:0 with SMTP id w4csp3848859pxu; Tue, 20 Oct 2020 01:58:38 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxqbUhuzR+58LtSlzA1RvBgFtqZkR4mBLljXmyYRzWPzwWWAc/04WmqvlH9STFlnTq9hY43 X-Received: by 2002:a17:906:4d44:: with SMTP id b4mr1982164ejv.131.1603184317796; Tue, 20 Oct 2020 01:58:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1603184317; cv=none; d=google.com; s=arc-20160816; b=mOh1mKXWnIW2bGceGiX/cslLyj9Yq8jhsk1gP8sMo/k42vIdQUJUs6bLVvGK5qRBAD /tdz7+ghH4CYnxK/dBgDULg4Ih6Nd0yQozjhzsNhG715Y2Aqcu+1Jm7jSMAzUcbfYhTV P5L99IA9Shew7KA1FtH4CPeIPe1EcehPBW2t2bZpPklhWjRIakG/62jYfzgiUe9955BP ySPy9BKRk8cQlc6XeRkfmImbTfYUtfcFh20YSn9EBE6kRsW/XtCYaB8eRxQzg+QFcIVR jbuszmtRm5Ocb/1nckN1yGlkaUvp9OR4EBE1KuB0QZ0uozwBjMVqPX+dA5Dmtb7niM+u Oteg== 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=kai6LEhoowEkYAyWXOkgFyHVjnTcmhqIrNCagJPIJMg=; b=m9uwxp/enLz7MZKfAvWQ3yot9fF61lf5EudxWmn2A+sNIYFkF9Q8o6imNHjr2PoV7P DlGbBu1zWN7DqoUgIE/hf9bJd0lF4Vajw72T90nz7ZP1tGNFfhVSSdvZDi4gWX+E+r8m HcFaAnGEMsprKWeazY6Xbng2bHdYoaNuNw1iQeEZtsUXTkxC8zEzN7mx0zGd1yEawNSC qvf64F3MkidjTzScZdmrrnUIm7rVUzhjMXCn5kn/n9hfDyPg/1SPDA7ZwRB88CdajgHj uaSFNlplxh8LCzRVKmH59Ef+Xl+MfdTX+MQ1ABXK4jAYghc3Ivsnu0ufYHWfkCQJuE6l L3Sw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@joelfernandes.org header.s=google header.b=T3AyRDkG; 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 Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id cf8si798960ejb.203.2020.10.20.01.58.15; Tue, 20 Oct 2020 01:58:37 -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=@joelfernandes.org header.s=google header.b=T3AyRDkG; 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 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390168AbgJTBoG (ORCPT + 99 others); Mon, 19 Oct 2020 21:44:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34586 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728305AbgJTBoD (ORCPT ); Mon, 19 Oct 2020 21:44:03 -0400 Received: from mail-io1-xd42.google.com (mail-io1-xd42.google.com [IPv6:2607:f8b0:4864:20::d42]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5281FC0613CE for ; Mon, 19 Oct 2020 18:44:01 -0700 (PDT) Received: by mail-io1-xd42.google.com with SMTP id b15so527568iod.13 for ; Mon, 19 Oct 2020 18:44:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=joelfernandes.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=kai6LEhoowEkYAyWXOkgFyHVjnTcmhqIrNCagJPIJMg=; b=T3AyRDkGPNT8/4S5wLWSjQ2vzkW1Wg1cNpYOy395bn22IsuRT5bbEqqoF5QfymuIvB pQXkf2UB0lGTVKyP34cN3iSOT1WeCzgNOopsSLKmUTRYRq+ryphyiGU2TVA6qYxiXDza JTov8qtPUudj0DP6ZIe4UjvO+pk8SeBmLmyv4= 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:mime-version:content-transfer-encoding; bh=kai6LEhoowEkYAyWXOkgFyHVjnTcmhqIrNCagJPIJMg=; b=XKMz/iRGw9+6JJEYPbsqsbhUajgXicCL3oNZ8/jAB4iBWHfeEn5WQCdbP8SemStTz5 RxdaheU5dkEK1Z/Ui34sSqxu2ydXUOkKv49OiQk4nZO627L8PTKsjo+EkuXWBeGzbbqM 7qHMR+8j5guJWSJffJzvpTfNhesbi7hBBtw3ihOjNQIQ1F2jrxEHDPzPlm3NLdGEMFAL wONqxWB7pHi/ABcn1N0/zvDbA6FfwwZyXUXuwQo6Z63yoy4TnB5kCiC9CGW6dp1DN2UX XCiAOrqFJu+UkAU0ekFpQziuYLGQ0vrXqP4S4WC2pBcO/ZgOwmGkAunl2dO50iZJsvaS H1cA== X-Gm-Message-State: AOAM532uXU+IvQFGaH+pASowDkOWKQrFZG+xI3BIqRB9F9BRaFcLYw4+ DbWR1ieKp1tH5hfPExiFo7bwLw== X-Received: by 2002:a02:6062:: with SMTP id d34mr479946jaf.84.1603158240632; Mon, 19 Oct 2020 18:44:00 -0700 (PDT) Received: from joelaf.cam.corp.google.com ([2620:15c:6:12:cad3:ffff:feb3:bd59]) by smtp.gmail.com with ESMTPSA id t22sm485306ili.9.2020.10.19.18.43.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 19 Oct 2020 18:44:00 -0700 (PDT) From: "Joel Fernandes (Google)" To: Nishanth Aravamudan , Julien Desfossez , Peter Zijlstra , Tim Chen , Vineeth Pillai , Aaron Lu , Aubrey Li , tglx@linutronix.de, linux-kernel@vger.kernel.org Cc: mingo@kernel.org, torvalds@linux-foundation.org, fweisbec@gmail.com, keescook@chromium.org, kerrnel@google.com, Phil Auld , Valentin Schneider , Mel Gorman , Pawan Gupta , Paolo Bonzini , joel@joelfernandes.org, vineeth@bitbyteword.org, Chen Yu , Christian Brauner , Agata Gruza , Antonio Gomez Iglesias , graf@amazon.com, konrad.wilk@oracle.com, dfaggioli@suse.com, pjt@google.com, rostedt@goodmis.org, derkling@google.com, benbjiang@tencent.com, Alexandre Chartre , James.Bottomley@hansenpartnership.com, OWeisse@umich.edu, Dhaval Giani , Junaid Shahid , jsbarnes@google.com, chris.hyser@oracle.com, Vineeth Remanan Pillai , Aubrey Li , "Paul E. McKenney" , Tim Chen Subject: [PATCH v8 -tip 05/26] sched: Basic tracking of matching tasks Date: Mon, 19 Oct 2020 21:43:15 -0400 Message-Id: <20201020014336.2076526-6-joel@joelfernandes.org> X-Mailer: git-send-email 2.29.0.rc1.297.gfa9743e501-goog In-Reply-To: <20201020014336.2076526-1-joel@joelfernandes.org> References: <20201020014336.2076526-1-joel@joelfernandes.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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). Tested-by: Julien Desfossez 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 393db0690101..c3563d7cab7f 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 /* diff --git a/kernel/sched/core.c b/kernel/sched/core.c index cecbf91cb477..a032f481c6e6 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -78,6 +78,141 @@ __read_mostly int scheduler_running; 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: * @@ -136,6 +271,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 */ /* @@ -1624,6 +1764,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); @@ -1638,6 +1781,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 b4bc82f46fe7..58f670e5704d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -258,33 +258,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) @@ -445,33 +423,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 85c8472b5d00..4964453591c3 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1053,6 +1053,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 }; @@ -1132,6 +1136,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.29.0.rc1.297.gfa9743e501-goog