[PATCHSET sched_ext/for-6.16] sched_ext: Reduce usage of static_keys

[PATCHSET sched_ext/for-6.16] sched_ext: Reduce usage of static_keys

[Tejun Heo]

sched_ext uses static_keys to optimize branches on ops flags and which ops
are implemented. Some of those branches aren't that hot and while others are
hotter, they are unlikely to cause meaningful overhead difference given
everything else that's going on. static_keys were used more because there
was no reason not to use static_keys. However, the planned multiple
hierarchical scheduler support won't work with global static_keys as these
branches would have to be based on the specific ops instance.

This patchset replaces static_key usages with tests on ops.flags and a
bitmap tracking which operation is implemented. I couldn't see performance
difference in numerous hackbench runs on a Ryzen 3990x machine before and
after the patchset.

This patchset contains the following five patches:

 0001-sched_ext-Indentation-updates.patch
 0002-sched_ext-Remove-scx_ops_enq_-static_keys.patch
 0003-sched_ext-Remove-scx_ops_cpu_preempt-static_key.patch
 0004-sched_ext-Remove-scx_ops_allow_queued_wakeup-static_.patch
 0005-sched_ext-Make-scx_has_op-a-bitmap.patch

and is also available in the following git branch:

 git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git scx-remove-static_keys

diffstat follows. Thanks.

 kernel/sched/ext.c |   91 +++++++++++++++++++++++------------------------------
 kernel/sched/ext.h |    8 ----
 2 files changed, 42 insertions(+), 57 deletions(-)

--
tejun

[PATCH 1/5] sched_ext: Indentation updates

[Tejun Heo]

Purely cosmetic.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 3cc5d7b5e3a9..022343518f99 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -163,16 +163,16 @@ enum scx_ops_flags {
 	/*
 	 * CPU cgroup support flags
 	 */
-	SCX_OPS_HAS_CGROUP_WEIGHT = 1LLU << 16,	/* DEPRECATED, will be removed on 6.18 */
-
-	SCX_OPS_ALL_FLAGS	= SCX_OPS_KEEP_BUILTIN_IDLE |
-				  SCX_OPS_ENQ_LAST |
-				  SCX_OPS_ENQ_EXITING |
-				  SCX_OPS_ENQ_MIGRATION_DISABLED |
-				  SCX_OPS_ALLOW_QUEUED_WAKEUP |
-				  SCX_OPS_SWITCH_PARTIAL |
-				  SCX_OPS_BUILTIN_IDLE_PER_NODE |
-				  SCX_OPS_HAS_CGROUP_WEIGHT,
+	SCX_OPS_HAS_CGROUP_WEIGHT	= 1LLU << 16,	/* DEPRECATED, will be removed on 6.18 */
+
+	SCX_OPS_ALL_FLAGS		= SCX_OPS_KEEP_BUILTIN_IDLE |
+					  SCX_OPS_ENQ_LAST |
+					  SCX_OPS_ENQ_EXITING |
+					  SCX_OPS_ENQ_MIGRATION_DISABLED |
+					  SCX_OPS_ALLOW_QUEUED_WAKEUP |
+					  SCX_OPS_SWITCH_PARTIAL |
+					  SCX_OPS_BUILTIN_IDLE_PER_NODE |
+					  SCX_OPS_HAS_CGROUP_WEIGHT,
 };
 
 /* argument container for ops.init_task() */
-- 
2.49.0

[PATCH 2/5] sched_ext: Remove scx_ops_enq_* static_keys

[Tejun Heo]

scx_ops_enq_last/exiting/migration_disabled are used to encode the
corresponding SCX_OPS_ flags into static_keys. These flags aren't hot enough
for static_key usage to make any meaningful difference and are made
static_keys mostly because there was no reason not to. However, global
static_keys can't work with the planned hierarchical multiple scheduler
support. Remove the static_keys and test the ops flags directly.

In repeated hackbench runs before and after static_keys removal on an AMD
Ryzen 3900X, I couldn't tell any measurable performance difference.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext.c | 22 +++++-----------------
 1 file changed, 5 insertions(+), 17 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 022343518f99..1e685e77b5e4 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -924,9 +924,6 @@ static struct sched_ext_ops scx_ops;
 static bool scx_warned_zero_slice;
 
 DEFINE_STATIC_KEY_FALSE(scx_ops_allow_queued_wakeup);
-static DEFINE_STATIC_KEY_FALSE(scx_ops_enq_last);
-static DEFINE_STATIC_KEY_FALSE(scx_ops_enq_exiting);
-static DEFINE_STATIC_KEY_FALSE(scx_ops_enq_migration_disabled);
 static DEFINE_STATIC_KEY_FALSE(scx_ops_cpu_preempt);
 
 static struct static_key_false scx_has_op[SCX_OPI_END] =
@@ -2144,14 +2141,14 @@ static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags,
 		goto direct;
 
 	/* see %SCX_OPS_ENQ_EXITING */
-	if (!static_branch_unlikely(&scx_ops_enq_exiting) &&
+	if (!(scx_ops.flags & SCX_OPS_ENQ_EXITING) &&
 	    unlikely(p->flags & PF_EXITING)) {
 		__scx_add_event(SCX_EV_ENQ_SKIP_EXITING, 1);
 		goto local;
 	}
 
 	/* see %SCX_OPS_ENQ_MIGRATION_DISABLED */
-	if (!static_branch_unlikely(&scx_ops_enq_migration_disabled) &&
+	if (!(scx_ops.flags & SCX_OPS_ENQ_MIGRATION_DISABLED) &&
 	    is_migration_disabled(p)) {
 		__scx_add_event(SCX_EV_ENQ_SKIP_MIGRATION_DISABLED, 1);
 		goto local;
@@ -3022,8 +3019,8 @@ static int balance_one(struct rq *rq, struct task_struct *prev)
 	 * Didn't find another task to run. Keep running @prev unless
 	 * %SCX_OPS_ENQ_LAST is in effect.
 	 */
-	if (prev_on_rq && (!static_branch_unlikely(&scx_ops_enq_last) ||
-	     scx_rq_bypassing(rq))) {
+	if (prev_on_rq &&
+	    (!(scx_ops.flags & SCX_OPS_ENQ_LAST) || scx_rq_bypassing(rq))) {
 		rq->scx.flags |= SCX_RQ_BAL_KEEP;
 		__scx_add_event(SCX_EV_DISPATCH_KEEP_LAST, 1);
 		goto has_tasks;
@@ -3228,7 +3225,7 @@ static void put_prev_task_scx(struct rq *rq, struct task_struct *p,
 		 * which should trigger an explicit follow-up scheduling event.
 		 */
 		if (sched_class_above(&ext_sched_class, next->sched_class)) {
-			WARN_ON_ONCE(!static_branch_unlikely(&scx_ops_enq_last));
+			WARN_ON_ONCE(!(scx_ops.flags & SCX_OPS_ENQ_LAST));
 			do_enqueue_task(rq, p, SCX_ENQ_LAST, -1);
 		} else {
 			do_enqueue_task(rq, p, 0, -1);
@@ -4728,9 +4725,6 @@ static void scx_disable_workfn(struct kthread_work *work)
 	for (i = SCX_OPI_BEGIN; i < SCX_OPI_END; i++)
 		static_branch_disable(&scx_has_op[i]);
 	static_branch_disable(&scx_ops_allow_queued_wakeup);
-	static_branch_disable(&scx_ops_enq_last);
-	static_branch_disable(&scx_ops_enq_exiting);
-	static_branch_disable(&scx_ops_enq_migration_disabled);
 	static_branch_disable(&scx_ops_cpu_preempt);
 	scx_idle_disable();
 	synchronize_rcu();
@@ -5372,12 +5366,6 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
 
 	if (ops->flags & SCX_OPS_ALLOW_QUEUED_WAKEUP)
 		static_branch_enable(&scx_ops_allow_queued_wakeup);
-	if (ops->flags & SCX_OPS_ENQ_LAST)
-		static_branch_enable(&scx_ops_enq_last);
-	if (ops->flags & SCX_OPS_ENQ_EXITING)
-		static_branch_enable(&scx_ops_enq_exiting);
-	if (ops->flags & SCX_OPS_ENQ_MIGRATION_DISABLED)
-		static_branch_enable(&scx_ops_enq_migration_disabled);
 	if (scx_ops.cpu_acquire || scx_ops.cpu_release)
 		static_branch_enable(&scx_ops_cpu_preempt);
 
-- 
2.49.0

[PATCH 3/5] sched_ext: Remove scx_ops_cpu_preempt static_key

[Tejun Heo]

scx_ops_cpu_preempt is used to encode whether ops.cpu_acquire/release() are
implemented into a static_key. These tests aren't hot enough for static_key
usage to make any meaningful difference and are made to use a static_key
mostly because there was no reason not to. However, global static_keys can't
work with the planned hierarchical multiple scheduler support. Remove the
static_key and instead use an internal ops flag SCX_OPS_HAS_CPU_PREEMPT to
record and test whether ops.cpu_acquire/release() are implemented.

In repeated hackbench runs before and after static_keys removal on an AMD
Ryzen 3900X, I couldn't tell any measurable performance difference.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 1e685e77b5e4..1adf5c299cce 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -173,6 +173,11 @@ enum scx_ops_flags {
 					  SCX_OPS_SWITCH_PARTIAL |
 					  SCX_OPS_BUILTIN_IDLE_PER_NODE |
 					  SCX_OPS_HAS_CGROUP_WEIGHT,
+
+	/* high 8 bits are internal, don't include in SCX_OPS_ALL_FLAGS */
+	__SCX_OPS_INTERNAL_MASK		= 0xffLLU << 56,
+
+	SCX_OPS_HAS_CPU_PREEMPT		= 1LLU << 56,
 };
 
 /* argument container for ops.init_task() */
@@ -924,7 +929,6 @@ static struct sched_ext_ops scx_ops;
 static bool scx_warned_zero_slice;
 
 DEFINE_STATIC_KEY_FALSE(scx_ops_allow_queued_wakeup);
-static DEFINE_STATIC_KEY_FALSE(scx_ops_cpu_preempt);
 
 static struct static_key_false scx_has_op[SCX_OPI_END] =
 	{ [0 ... SCX_OPI_END-1] = STATIC_KEY_FALSE_INIT };
@@ -2931,7 +2935,7 @@ static int balance_one(struct rq *rq, struct task_struct *prev)
 	rq->scx.flags |= SCX_RQ_IN_BALANCE;
 	rq->scx.flags &= ~(SCX_RQ_BAL_PENDING | SCX_RQ_BAL_KEEP);
 
-	if (static_branch_unlikely(&scx_ops_cpu_preempt) &&
+	if ((scx_ops.flags & SCX_OPS_HAS_CPU_PREEMPT) &&
 	    unlikely(rq->scx.cpu_released)) {
 		/*
 		 * If the previous sched_class for the current CPU was not SCX,
@@ -3160,7 +3164,7 @@ static void switch_class(struct rq *rq, struct task_struct *next)
 	 */
 	smp_store_release(&rq->scx.pnt_seq, rq->scx.pnt_seq + 1);
 #endif
-	if (!static_branch_unlikely(&scx_ops_cpu_preempt))
+	if (!(scx_ops.flags & SCX_OPS_HAS_CPU_PREEMPT))
 		return;
 
 	/*
@@ -4725,7 +4729,6 @@ static void scx_disable_workfn(struct kthread_work *work)
 	for (i = SCX_OPI_BEGIN; i < SCX_OPI_END; i++)
 		static_branch_disable(&scx_has_op[i]);
 	static_branch_disable(&scx_ops_allow_queued_wakeup);
-	static_branch_disable(&scx_ops_cpu_preempt);
 	scx_idle_disable();
 	synchronize_rcu();
 
@@ -5367,7 +5370,7 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
 	if (ops->flags & SCX_OPS_ALLOW_QUEUED_WAKEUP)
 		static_branch_enable(&scx_ops_allow_queued_wakeup);
 	if (scx_ops.cpu_acquire || scx_ops.cpu_release)
-		static_branch_enable(&scx_ops_cpu_preempt);
+		scx_ops.flags |= SCX_OPS_HAS_CPU_PREEMPT;
 
 	/*
 	 * Lock out forks, cgroup on/offlining and moves before opening the
-- 
2.49.0

[PATCH 4/5] sched_ext: Remove scx_ops_allow_queued_wakeup static_key

[Tejun Heo]

scx_ops_allow_queued_wakeup is used to encode SCX_OPS_ALLOW_QUEUED_WAKEUP
into a static_key. The test is gated behind scx_enabled(), and, even when
sched_ext is enabled, is unlikely for the static_key usage to make any
meaningful difference. It is made to use a static_key mostly because there
was no reason not to. However, global static_keys can't work with the
planned hierarchical multiple scheduler support. Remove the static_key and
instead test SCX_OPS_ALLOW_QUEUED_WAKEUP directly.

In repeated hackbench runs before and after static_keys removal on an AMD
Ryzen 3900X, I couldn't tell any measurable performance difference.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext.c | 12 +++++++-----
 kernel/sched/ext.h |  8 +-------
 2 files changed, 8 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 1adf5c299cce..f0ed0cec4c98 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -928,8 +928,6 @@ DEFINE_STATIC_KEY_FALSE(__scx_switched_all);
 static struct sched_ext_ops scx_ops;
 static bool scx_warned_zero_slice;
 
-DEFINE_STATIC_KEY_FALSE(scx_ops_allow_queued_wakeup);
-
 static struct static_key_false scx_has_op[SCX_OPI_END] =
 	{ [0 ... SCX_OPI_END-1] = STATIC_KEY_FALSE_INIT };
 
@@ -4414,6 +4412,13 @@ bool task_should_scx(int policy)
 	return policy == SCHED_EXT;
 }
 
+bool scx_allow_ttwu_queue(const struct task_struct *p)
+{
+	return !scx_enabled() ||
+		(scx_ops.flags & SCX_OPS_ALLOW_QUEUED_WAKEUP) ||
+		p->sched_class != &ext_sched_class;
+}
+
 /**
  * scx_softlockup - sched_ext softlockup handler
  * @dur_s: number of seconds of CPU stuck due to soft lockup
@@ -4728,7 +4733,6 @@ static void scx_disable_workfn(struct kthread_work *work)
 	static_branch_disable(&__scx_enabled);
 	for (i = SCX_OPI_BEGIN; i < SCX_OPI_END; i++)
 		static_branch_disable(&scx_has_op[i]);
-	static_branch_disable(&scx_ops_allow_queued_wakeup);
 	scx_idle_disable();
 	synchronize_rcu();
 
@@ -5367,8 +5371,6 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
 		if (((void (**)(void))ops)[i])
 			static_branch_enable(&scx_has_op[i]);
 
-	if (ops->flags & SCX_OPS_ALLOW_QUEUED_WAKEUP)
-		static_branch_enable(&scx_ops_allow_queued_wakeup);
 	if (scx_ops.cpu_acquire || scx_ops.cpu_release)
 		scx_ops.flags |= SCX_OPS_HAS_CPU_PREEMPT;
 
diff --git a/kernel/sched/ext.h b/kernel/sched/ext.h
index 1bda96b19a1b..3053cdd61eb9 100644
--- a/kernel/sched/ext.h
+++ b/kernel/sched/ext.h
@@ -21,6 +21,7 @@ void scx_rq_activate(struct rq *rq);
 void scx_rq_deactivate(struct rq *rq);
 int scx_check_setscheduler(struct task_struct *p, int policy);
 bool task_should_scx(int policy);
+bool scx_allow_ttwu_queue(const struct task_struct *p);
 void init_sched_ext_class(void);
 
 static inline u32 scx_cpuperf_target(s32 cpu)
@@ -36,13 +37,6 @@ static inline bool task_on_scx(const struct task_struct *p)
 	return scx_enabled() && p->sched_class == &ext_sched_class;
 }
 
-static inline bool scx_allow_ttwu_queue(const struct task_struct *p)
-{
-	return !scx_enabled() ||
-		static_branch_likely(&scx_ops_allow_queued_wakeup) ||
-		p->sched_class != &ext_sched_class;
-}
-
 #ifdef CONFIG_SCHED_CORE
 bool scx_prio_less(const struct task_struct *a, const struct task_struct *b,
 		   bool in_fi);
-- 
2.49.0

[PATCH 5/5] sched_ext: Make scx_has_op a bitmap

[Tejun Heo]

scx_has_op is used to encode which ops are implemented by the BPF scheduler
into an array of static_keys. While this saves a bit of branching overhead,
that is unlikely to be noticeable compared to the overall cost. As the
global static_keys can't work with the planned hierarchical multiple
scheduler support, replace the static_key array with a bitmap.

In repeated hackbench runs before and after static_keys removal on an AMD
Ryzen 3900X, I couldn't tell any measurable performance difference.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext.c | 22 ++++++++++------------
 1 file changed, 10 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index f0ed0cec4c98..8ae85ec6d9a2 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -928,8 +928,7 @@ DEFINE_STATIC_KEY_FALSE(__scx_switched_all);
 static struct sched_ext_ops scx_ops;
 static bool scx_warned_zero_slice;
 
-static struct static_key_false scx_has_op[SCX_OPI_END] =
-	{ [0 ... SCX_OPI_END-1] = STATIC_KEY_FALSE_INIT };
+static DECLARE_BITMAP(scx_has_op, SCX_OPI_END);
 
 static atomic_t scx_exit_kind = ATOMIC_INIT(SCX_EXIT_DONE);
 static struct scx_exit_info *scx_exit_info;
@@ -1055,7 +1054,7 @@ static __printf(3, 4) void __scx_exit(enum scx_exit_kind kind, s64 exit_code,
 #define scx_error(fmt, args...)							\
 	__scx_error(SCX_EXIT_ERROR, fmt, ##args)
 
-#define SCX_HAS_OP(op)	static_branch_likely(&scx_has_op[SCX_OP_IDX(op)])
+#define SCX_HAS_OP(op)	test_bit(SCX_OP_IDX(op), scx_has_op)
 
 static long jiffies_delta_msecs(unsigned long at, unsigned long now)
 {
@@ -1774,7 +1773,7 @@ static void touch_core_sched_dispatch(struct rq *rq, struct task_struct *p)
 	lockdep_assert_rq_held(rq);
 
 #ifdef CONFIG_SCHED_CORE
-	if (SCX_HAS_OP(core_sched_before))
+	if (unlikely(SCX_HAS_OP(core_sched_before)))
 		touch_core_sched(rq, p);
 #endif
 }
@@ -2156,7 +2155,7 @@ static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags,
 		goto local;
 	}
 
-	if (!SCX_HAS_OP(enqueue))
+	if (unlikely(!SCX_HAS_OP(enqueue)))
 		goto global;
 
 	/* DSQ bypass didn't trigger, enqueue on the BPF scheduler */
@@ -2972,7 +2971,7 @@ static int balance_one(struct rq *rq, struct task_struct *prev)
 	if (consume_global_dsq(rq))
 		goto has_tasks;
 
-	if (!SCX_HAS_OP(dispatch) || scx_rq_bypassing(rq) || !scx_rq_online(rq))
+	if (unlikely(!SCX_HAS_OP(dispatch)) || scx_rq_bypassing(rq) || !scx_rq_online(rq))
 		goto no_tasks;
 
 	dspc->rq = rq;
@@ -3373,7 +3372,7 @@ static int select_task_rq_scx(struct task_struct *p, int prev_cpu, int wake_flag
 		return prev_cpu;
 
 	rq_bypass = scx_rq_bypassing(task_rq(p));
-	if (SCX_HAS_OP(select_cpu) && !rq_bypass) {
+	if (likely(SCX_HAS_OP(select_cpu)) && !rq_bypass) {
 		s32 cpu;
 		struct task_struct **ddsp_taskp;
 
@@ -4638,7 +4637,7 @@ static void scx_disable_workfn(struct kthread_work *work)
 	struct task_struct *p;
 	struct rhashtable_iter rht_iter;
 	struct scx_dispatch_q *dsq;
-	int i, kind, cpu;
+	int kind, cpu;
 
 	kind = atomic_read(&scx_exit_kind);
 	while (true) {
@@ -4731,8 +4730,7 @@ static void scx_disable_workfn(struct kthread_work *work)
 
 	/* no task is on scx, turn off all the switches and flush in-progress calls */
 	static_branch_disable(&__scx_enabled);
-	for (i = SCX_OPI_BEGIN; i < SCX_OPI_END; i++)
-		static_branch_disable(&scx_has_op[i]);
+	bitmap_zero(scx_has_op, SCX_OPI_END);
 	scx_idle_disable();
 	synchronize_rcu();
 
@@ -5328,7 +5326,7 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
 
 	for (i = SCX_OPI_CPU_HOTPLUG_BEGIN; i < SCX_OPI_CPU_HOTPLUG_END; i++)
 		if (((void (**)(void))ops)[i])
-			static_branch_enable_cpuslocked(&scx_has_op[i]);
+			set_bit(i, scx_has_op);
 
 	check_hotplug_seq(ops);
 	scx_idle_update_selcpu_topology(ops);
@@ -5369,7 +5367,7 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
 
 	for (i = SCX_OPI_NORMAL_BEGIN; i < SCX_OPI_NORMAL_END; i++)
 		if (((void (**)(void))ops)[i])
-			static_branch_enable(&scx_has_op[i]);
+			set_bit(i, scx_has_op);
 
 	if (scx_ops.cpu_acquire || scx_ops.cpu_release)
 		scx_ops.flags |= SCX_OPS_HAS_CPU_PREEMPT;
-- 
2.49.0

Re: [PATCHSET sched_ext/for-6.16] sched_ext: Reduce usage of static_keys

[Changwoo Min]

Hi Tejun,

Thank you for the cleanup. Looks good to me.

Acked-by: Changwoo Min <changwoo@igalia.com>

Regards,
Changwoo Min

On 4/9/25 08:06, Tejun Heo wrote:
> sched_ext uses static_keys to optimize branches on ops flags and which ops
> are implemented. Some of those branches aren't that hot and while others are
> hotter, they are unlikely to cause meaningful overhead difference given
> everything else that's going on. static_keys were used more because there
> was no reason not to use static_keys. However, the planned multiple
> hierarchical scheduler support won't work with global static_keys as these
> branches would have to be based on the specific ops instance.
> 
> This patchset replaces static_key usages with tests on ops.flags and a
> bitmap tracking which operation is implemented. I couldn't see performance
> difference in numerous hackbench runs on a Ryzen 3990x machine before and
> after the patchset.
> 
> This patchset contains the following five patches:
> 
>   0001-sched_ext-Indentation-updates.patch
>   0002-sched_ext-Remove-scx_ops_enq_-static_keys.patch
>   0003-sched_ext-Remove-scx_ops_cpu_preempt-static_key.patch
>   0004-sched_ext-Remove-scx_ops_allow_queued_wakeup-static_.patch
>   0005-sched_ext-Make-scx_has_op-a-bitmap.patch
> 
> and is also available in the following git branch:
> 
>   git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git scx-remove-static_keys
> 
> diffstat follows. Thanks.
> 
>   kernel/sched/ext.c |   91 +++++++++++++++++++++++------------------------------
>   kernel/sched/ext.h |    8 ----
>   2 files changed, 42 insertions(+), 57 deletions(-)
> 
> --
> tejun
> 

Re: [PATCH 5/5] sched_ext: Make scx_has_op a bitmap

[Andrea Righi]

On Tue, Apr 08, 2025 at 01:06:05PM -1000, Tejun Heo wrote:
> scx_has_op is used to encode which ops are implemented by the BPF scheduler
> into an array of static_keys. While this saves a bit of branching overhead,
> that is unlikely to be noticeable compared to the overall cost. As the
> global static_keys can't work with the planned hierarchical multiple
> scheduler support, replace the static_key array with a bitmap.
> 
> In repeated hackbench runs before and after static_keys removal on an AMD
> Ryzen 3900X, I couldn't tell any measurable performance difference.

At this point I'm wondering if we should just do something like:

 #define SCX_HAS_OP(op) (scx_ops.op != NULL)

Do you think the bitmap can provide some measurable benefits? For the most
frequently used hot paths (enqueue, dispatch, select_cpu, running,
stopping) we likely have to fetch scx_ops.op anyway, so cache-wise the
difference should be minimal.

Thanks,
-Andrea

> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> ---
>  kernel/sched/ext.c | 22 ++++++++++------------
>  1 file changed, 10 insertions(+), 12 deletions(-)
> 
> diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
> index f0ed0cec4c98..8ae85ec6d9a2 100644
> --- a/kernel/sched/ext.c
> +++ b/kernel/sched/ext.c
> @@ -928,8 +928,7 @@ DEFINE_STATIC_KEY_FALSE(__scx_switched_all);
>  static struct sched_ext_ops scx_ops;
>  static bool scx_warned_zero_slice;
>  
> -static struct static_key_false scx_has_op[SCX_OPI_END] =
> -	{ [0 ... SCX_OPI_END-1] = STATIC_KEY_FALSE_INIT };
> +static DECLARE_BITMAP(scx_has_op, SCX_OPI_END);
>  
>  static atomic_t scx_exit_kind = ATOMIC_INIT(SCX_EXIT_DONE);
>  static struct scx_exit_info *scx_exit_info;
> @@ -1055,7 +1054,7 @@ static __printf(3, 4) void __scx_exit(enum scx_exit_kind kind, s64 exit_code,
>  #define scx_error(fmt, args...)							\
>  	__scx_error(SCX_EXIT_ERROR, fmt, ##args)
>  
> -#define SCX_HAS_OP(op)	static_branch_likely(&scx_has_op[SCX_OP_IDX(op)])
> +#define SCX_HAS_OP(op)	test_bit(SCX_OP_IDX(op), scx_has_op)
>  
>  static long jiffies_delta_msecs(unsigned long at, unsigned long now)
>  {
> @@ -1774,7 +1773,7 @@ static void touch_core_sched_dispatch(struct rq *rq, struct task_struct *p)
>  	lockdep_assert_rq_held(rq);
>  
>  #ifdef CONFIG_SCHED_CORE
> -	if (SCX_HAS_OP(core_sched_before))
> +	if (unlikely(SCX_HAS_OP(core_sched_before)))
>  		touch_core_sched(rq, p);
>  #endif
>  }
> @@ -2156,7 +2155,7 @@ static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags,
>  		goto local;
>  	}
>  
> -	if (!SCX_HAS_OP(enqueue))
> +	if (unlikely(!SCX_HAS_OP(enqueue)))
>  		goto global;
>  
>  	/* DSQ bypass didn't trigger, enqueue on the BPF scheduler */
> @@ -2972,7 +2971,7 @@ static int balance_one(struct rq *rq, struct task_struct *prev)
>  	if (consume_global_dsq(rq))
>  		goto has_tasks;
>  
> -	if (!SCX_HAS_OP(dispatch) || scx_rq_bypassing(rq) || !scx_rq_online(rq))
> +	if (unlikely(!SCX_HAS_OP(dispatch)) || scx_rq_bypassing(rq) || !scx_rq_online(rq))
>  		goto no_tasks;
>  
>  	dspc->rq = rq;
> @@ -3373,7 +3372,7 @@ static int select_task_rq_scx(struct task_struct *p, int prev_cpu, int wake_flag
>  		return prev_cpu;
>  
>  	rq_bypass = scx_rq_bypassing(task_rq(p));
> -	if (SCX_HAS_OP(select_cpu) && !rq_bypass) {
> +	if (likely(SCX_HAS_OP(select_cpu)) && !rq_bypass) {
>  		s32 cpu;
>  		struct task_struct **ddsp_taskp;
>  
> @@ -4638,7 +4637,7 @@ static void scx_disable_workfn(struct kthread_work *work)
>  	struct task_struct *p;
>  	struct rhashtable_iter rht_iter;
>  	struct scx_dispatch_q *dsq;
> -	int i, kind, cpu;
> +	int kind, cpu;
>  
>  	kind = atomic_read(&scx_exit_kind);
>  	while (true) {
> @@ -4731,8 +4730,7 @@ static void scx_disable_workfn(struct kthread_work *work)
>  
>  	/* no task is on scx, turn off all the switches and flush in-progress calls */
>  	static_branch_disable(&__scx_enabled);
> -	for (i = SCX_OPI_BEGIN; i < SCX_OPI_END; i++)
> -		static_branch_disable(&scx_has_op[i]);
> +	bitmap_zero(scx_has_op, SCX_OPI_END);
>  	scx_idle_disable();
>  	synchronize_rcu();
>  
> @@ -5328,7 +5326,7 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
>  
>  	for (i = SCX_OPI_CPU_HOTPLUG_BEGIN; i < SCX_OPI_CPU_HOTPLUG_END; i++)
>  		if (((void (**)(void))ops)[i])
> -			static_branch_enable_cpuslocked(&scx_has_op[i]);
> +			set_bit(i, scx_has_op);
>  
>  	check_hotplug_seq(ops);
>  	scx_idle_update_selcpu_topology(ops);
> @@ -5369,7 +5367,7 @@ static int scx_enable(struct sched_ext_ops *ops, struct bpf_link *link)
>  
>  	for (i = SCX_OPI_NORMAL_BEGIN; i < SCX_OPI_NORMAL_END; i++)
>  		if (((void (**)(void))ops)[i])
> -			static_branch_enable(&scx_has_op[i]);
> +			set_bit(i, scx_has_op);
>  
>  	if (scx_ops.cpu_acquire || scx_ops.cpu_release)
>  		scx_ops.flags |= SCX_OPS_HAS_CPU_PREEMPT;
> -- 
> 2.49.0
> 

Re: [PATCH 5/5] sched_ext: Make scx_has_op a bitmap

[Tejun Heo]

Hello,

On Wed, Apr 09, 2025 at 09:57:59AM +0200, Andrea Righi wrote:
> On Tue, Apr 08, 2025 at 01:06:05PM -1000, Tejun Heo wrote:
> > scx_has_op is used to encode which ops are implemented by the BPF scheduler
> > into an array of static_keys. While this saves a bit of branching overhead,
> > that is unlikely to be noticeable compared to the overall cost. As the
> > global static_keys can't work with the planned hierarchical multiple
> > scheduler support, replace the static_key array with a bitmap.
> > 
> > In repeated hackbench runs before and after static_keys removal on an AMD
> > Ryzen 3900X, I couldn't tell any measurable performance difference.
> 
> At this point I'm wondering if we should just do something like:
> 
>  #define SCX_HAS_OP(op) (scx_ops.op != NULL)
> 
> Do you think the bitmap can provide some measurable benefits? For the most
> frequently used hot paths (enqueue, dispatch, select_cpu, running,
> stopping) we likely have to fetch scx_ops.op anyway, so cache-wise the
> difference should be minimal.

Performance-wise, unlikely. However, we need to be able to enable ops in
stages during init - CPU hotplug ops need to be enabled before other ops. We
can do that by setting the op pointers in stages but the code was already
structured in a way which is easy to convert to bitmap, so that was the path
of least resistance. We surely can change it.

Thanks.

-- 
tejun

Re: [PATCH 5/5] sched_ext: Make scx_has_op a bitmap

[Andrea Righi]

On Wed, Apr 09, 2025 at 08:51:24AM -1000, Tejun Heo wrote:
> Hello,
> 
> On Wed, Apr 09, 2025 at 09:57:59AM +0200, Andrea Righi wrote:
> > On Tue, Apr 08, 2025 at 01:06:05PM -1000, Tejun Heo wrote:
> > > scx_has_op is used to encode which ops are implemented by the BPF scheduler
> > > into an array of static_keys. While this saves a bit of branching overhead,
> > > that is unlikely to be noticeable compared to the overall cost. As the
> > > global static_keys can't work with the planned hierarchical multiple
> > > scheduler support, replace the static_key array with a bitmap.
> > > 
> > > In repeated hackbench runs before and after static_keys removal on an AMD
> > > Ryzen 3900X, I couldn't tell any measurable performance difference.
> > 
> > At this point I'm wondering if we should just do something like:
> > 
> >  #define SCX_HAS_OP(op) (scx_ops.op != NULL)
> > 
> > Do you think the bitmap can provide some measurable benefits? For the most
> > frequently used hot paths (enqueue, dispatch, select_cpu, running,
> > stopping) we likely have to fetch scx_ops.op anyway, so cache-wise the
> > difference should be minimal.
> 
> Performance-wise, unlikely. However, we need to be able to enable ops in
> stages during init - CPU hotplug ops need to be enabled before other ops. We
> can do that by setting the op pointers in stages but the code was already
> structured in a way which is easy to convert to bitmap, so that was the path
> of least resistance. We surely can change it.

Ah good point about the init stages. In that case, I agree that it's safer
to introduce the bitmap for now and, later, we can refactor the code to use
pointers if we want. Thanks for the clarification.

Acked-by: Andrea Righi <arighi@nvidia.com>

-Andrea

Re: [PATCHSET sched_ext/for-6.16] sched_ext: Reduce usage of static_keys

[Tejun Heo]

On Tue, Apr 08, 2025 at 01:06:00PM -1000, Tejun Heo wrote:
> sched_ext uses static_keys to optimize branches on ops flags and which ops
> are implemented. Some of those branches aren't that hot and while others are
> hotter, they are unlikely to cause meaningful overhead difference given
> everything else that's going on. static_keys were used more because there
> was no reason not to use static_keys. However, the planned multiple
> hierarchical scheduler support won't work with global static_keys as these
> branches would have to be based on the specific ops instance.
> 
> This patchset replaces static_key usages with tests on ops.flags and a
> bitmap tracking which operation is implemented. I couldn't see performance
> difference in numerous hackbench runs on a Ryzen 3990x machine before and
> after the patchset.
> 
> This patchset contains the following five patches:
> 
>  0001-sched_ext-Indentation-updates.patch
>  0002-sched_ext-Remove-scx_ops_enq_-static_keys.patch
>  0003-sched_ext-Remove-scx_ops_cpu_preempt-static_key.patch
>  0004-sched_ext-Remove-scx_ops_allow_queued_wakeup-static_.patch
>  0005-sched_ext-Make-scx_has_op-a-bitmap.patch

Applied to sched_ext/for-6.16.

Thanks.

-- 
tejun