[PATCH 0/2] sched_ext: Specialize TID and scheduler hashtable compares

[PATCH 0/2] sched_ext: Specialize TID and scheduler hashtable compares

[Usama Arif]

scx_tid_hash and scx_sched_hash both use naturally aligned u64 keys but
do not provide obj_cmpfn callbacks. As a result, rhashtable falls back
to rhashtable_compare() for each object visited during a lookup:

  memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len)

Although only eight bytes are compared, the generic path loads the key
offset and length at runtime and emits an out-of-line memcmp() call.

The first patch adds a specialized comparison for scx_tid_hash. This
turns comparisons in scx_bpf_tid_to_task() into direct equality tests
against scx->tid. The kfunc can be used from hot scheduling paths, so
avoiding the generic comparison is particularly useful there. The
specialized comparison also covers duplicate checks during insertion.

The second patch specializes scx_sched_hash by comparing keys directly
against ops.sub_cgroup_id. This removes the generic comparison from
scx_find_sub_sched(), which is used when dispatching child schedulers
and by the sub-scheduler capability and management kfuncs.

In both cases, the const rhashtable parameters allow the compiler to
inline the callback and reduce each object comparison to a single u64
compare. Disassembly confirms that the lookup loops no longer call
memcmp() or an out-of-line comparator.

No functional change intended.

Usama Arif (2):
  sched_ext: Specialize the TID hashtable compare
  sched_ext: Specialize the scheduler hashtable compare

 kernel/sched/ext/ext.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

-- 
2.53.0-Meta

[PATCH 1/2] sched_ext: Specialize the TID hashtable compare

[Usama Arif]

scx_tid_hash_params does not provide an object comparison function, so
rhashtable falls back to rhashtable_compare(). Although the key is one
naturally aligned u64, the generic comparison reads the key offset and
length from the table parameters at runtime and emits an out-of-line
memcmp() for each element walked.

scx_bpf_tid_to_task() can sit on hot scheduling paths. Supply an
obj_cmpfn so the const parameters passed into the inlined rhashtable
lookup specialize the comparison to a single equality test against
scx->tid.

The result is only tested against zero, so the ordering provided by
memcmp() is not observable. No functional change intended.

Suggested-by: Tejun Heo <tj@kernel.org>
Signed-off-by: Usama Arif <usama.arif@linux.dev>
---
 kernel/sched/ext/ext.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 646affba4e3c4..288d6b80bbca0 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -52,10 +52,21 @@ struct rhashtable scx_sched_hash;
 #endif
 
 /* see SCX_OPS_TID_TO_TASK */
+static __always_inline int scx_tid_cmpfn(struct rhashtable_compare_arg *arg,
+					 const void *ptr)
+{
+	const struct sched_ext_entity *scx = ptr;
+
+	BUILD_BUG_ON(sizeof_field(struct sched_ext_entity, tid) != sizeof(u64));
+
+	return scx->tid != *(const u64 *)arg->key;
+}
+
 static const struct rhashtable_params scx_tid_hash_params = {
 	.key_len		= sizeof_field(struct sched_ext_entity, tid),
 	.key_offset		= offsetof(struct sched_ext_entity, tid),
 	.head_offset		= offsetof(struct sched_ext_entity, tid_hash_node),
+	.obj_cmpfn		= scx_tid_cmpfn,
 	.insecure_elasticity	= true,	/* inserted/removed under scx_tasks_lock */
 };
 static struct rhashtable scx_tid_hash;
-- 
2.53.0-Meta

[PATCH 2/2] sched_ext: Specialize the scheduler hashtable compare

[Usama Arif]

scx_sched_hash_params does not provide an object comparison function,
so rhashtable falls back to rhashtable_compare(). Although the
sub-cgroup ID key is one naturally aligned u64, the generic comparison
reads the key offset and length from the table parameters at runtime and
emits an out-of-line memcmp() for each element walked.

Supply an obj_cmpfn so lookups specialize to a single equality test
against ops.sub_cgroup_id. ext.c and sub.c are included in the same
build_policy.c translation unit, so the compiler can fold the const
callback into scx_find_sub_sched() even though its source is in sub.c.

The result is only tested against zero, so the ordering provided by
memcmp() is not observable. No functional change intended.

Suggested-by: Tejun Heo <tj@kernel.org>
Signed-off-by: Usama Arif <usama.arif@linux.dev>
---
 kernel/sched/ext/ext.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 288d6b80bbca0..87fa09c71eb0f 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -41,10 +41,21 @@ struct scx_sched __rcu *scx_root;
 LIST_HEAD(scx_sched_all);
 
 #ifdef CONFIG_EXT_SUB_SCHED
+static __always_inline int scx_sched_cmpfn(struct rhashtable_compare_arg *arg,
+					   const void *ptr)
+{
+	const struct scx_sched *sch = ptr;
+
+	BUILD_BUG_ON(sizeof_field(struct scx_sched, ops.sub_cgroup_id) != sizeof(u64));
+
+	return sch->ops.sub_cgroup_id != *(const u64 *)arg->key;
+}
+
 const struct rhashtable_params scx_sched_hash_params = {
 	.key_len		= sizeof_field(struct scx_sched, ops.sub_cgroup_id),
 	.key_offset		= offsetof(struct scx_sched, ops.sub_cgroup_id),
 	.head_offset		= offsetof(struct scx_sched, hash_node),
+	.obj_cmpfn		= scx_sched_cmpfn,
 	.insecure_elasticity	= true,	/* inserted under scx_sched_lock */
 };
 
-- 
2.53.0-Meta

Re: [PATCH 2/2] sched_ext: Specialize the scheduler hashtable compare

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1477 bytes --]

> diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
> index 124bf827791ed..705a937268505 100644
> --- a/kernel/sched/ext/ext.c
> +++ b/kernel/sched/ext/ext.c
> @@ -41,10 +41,21 @@ struct scx_sched __rcu *scx_root;
>  LIST_HEAD(scx_sched_all);
>
>  #ifdef CONFIG_EXT_SUB_SCHED
> +static __always_inline int scx_sched_cmpfn(struct rhashtable_compare_arg *arg,
> +					   const void *ptr)
> +{
> +	const struct scx_sched *sch = ptr;
> +
> +	BUILD_BUG_ON(sizeof_field(struct scx_sched, ops.sub_cgroup_id) != sizeof(u64));
> +
> +	return sch->ops.sub_cgroup_id != *(const u64 *)arg->key;
> +}
> +

This isn't a bug, but scx_sched_cmpfn() and scx_tid_cmpfn() (added in
the preceding patch, twenty lines below in this file) differ only in the
container type and field -- would a small generator macro be worth it
here, or is spelling both out clearer at two instances?

>  const struct rhashtable_params scx_sched_hash_params = {
>  	.key_len		= sizeof_field(struct scx_sched, ops.sub_cgroup_id),
>  	.key_offset		= offsetof(struct scx_sched, ops.sub_cgroup_id),
>  	.head_offset		= offsetof(struct scx_sched, hash_node),
> +	.obj_cmpfn		= scx_sched_cmpfn,
>  	.insecure_elasticity	= true,	/* inserted under scx_sched_lock */
>  };


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35676595280

Re: [PATCH 0/2] sched_ext: Specialize TID and scheduler hashtable compares

[Tejun Heo]

> Usama Arif (2):
>   sched_ext: Specialize the TID hashtable compare
>   sched_ext: Specialize the scheduler hashtable compare

Applied 1-2 to sched_ext/for-7.4 with the scx_tid_cmpfn() signature joined
onto one line.

Thanks.

--
tejun