sched_ext: Specialize TID and scheduler hashtable compares
Subsystems (3)
cover sched_ext: Specialize TID and scheduler hashtable compares
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(+)
Signature · 1 line
2.53.0-Meta
PATCH 1/2 sched_ext: Specialize the TID hashtable compare
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.
--- kernel/sched/ext/ext.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
kernel/sched/ext/ext.c +11 -0
@@ -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;
Signature · 1 line
2.53.0-Meta
PATCH 2/2 sched_ext: Specialize the scheduler hashtable compare
In reply to Usama Arifscx_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.
--- kernel/sched/ext/ext.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
kernel/sched/ext/ext.c +11 -0
@@ -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 */ };
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH 2/2] sched_ext: Specialize the scheduler hashtable compare
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…
Quoted 8 lines
kernel/sched/ext/ext.c +0
-0@@ -41,10 +41,21 @@ struct scx_sched __rcu *scx_root;LIST_HEAD (scx_sched_all);#ifdef CONFIG_EXT_SUB_SCHED
kernel/sched/ext/ext.c struct scx_sched __rcu *scx_root; · line 53
Quoted 10 lines
kernel/sched/ext/ext.c +10
-0+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?
kernel/sched/ext/ext.c struct scx_sched __rcu *scx_root; · line 60
Quoted 7 lines
kernel/sched/ext/ext.c +1
-0const 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
Tejun Heo
reviewerQuoted 3 lines
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