sched_ext: Specialize the DSQ hashtable compare
Subsystems (3)
PATCH 1/1 sched_ext: Specialize the DSQ hashtable compare
rhashtable is a generic container: it does not know what a key is, so it carries the key's shape as data. dsq_hash_params declares key_len, key_offset and head_offset and nothing else, so lookups fall back to rhashtable_compare(), which reads both the offset and the length back out of ht->p at runtime:
memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len)
The key is one naturally aligned u64, but neither the offset nor the length is a compile-time constant there, so the compiler cannot narrow the call and emits an out-of-line memcmp() for every element walked - two loads, a call and a length dispatch to compare eight bytes. The interpretation costs more than the comparison it is interpreting.
find_user_dsq() sits on the __schedule() path, and scx_layered calls scx_bpf_dsq_nr_queued() once per layer per dispatch decision. On Meta's fleet the lookup has a significant cost and shows up in fleet wide profile.
Let's supply an obj_cmpfn. dsq_hash_params is a const object passed by value into the __always_inline __rhashtable_lookup(), so params.obj_cmpfn is a compile-time constant, the ternary that selects it folds away and the callback inlines: the compare becomes a single cmp against dsq->id. Every consumer of the result only tests it against zero, so the ordering memcmp() also carries is never observed. No functional change intended.
An in-kernel A/B over the DSQ ids scx_layered creates, both parameter sets compiled into the same kernel, makes the lookup 2.9x faster.
--- kernel/sched/ext/ext.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
kernel/sched/ext/ext.c +11 -0
@@ -189,10 +189,21 @@ static DEFINE_PER_CPU(struct scx_tid_alloc, scx_tid_alloc);*/ static DEFINE_PER_CPU(struct task_struct *, direct_dispatch_task); +static __always_inline int dsq_cmpfn(struct rhashtable_compare_arg *arg, +const void *ptr) +{ +const struct scx_dispatch_q *dsq = ptr; + + BUILD_BUG_ON(sizeof_field(struct scx_dispatch_q, id) != sizeof(u64)); + +return dsq->id != *(const u64 *)arg->key; +} +static const struct rhashtable_params dsq_hash_params = { .key_len = sizeof_field(struct scx_dispatch_q, id), .key_offset = offsetof(struct scx_dispatch_q , id), .head_offset = offsetof(struct scx_dispatch_q , hash_node), + .obj_cmpfn = dsq_cmpfn, };static LLIST_HEAD (dsqs_to_free);
base-commit: d9ecc8c5e754065159bdd5cb580eb9295f7256b2
Signature · 1 line
2.53.0-Meta
Applied to sched_ext/for-7.4 with the dsq_cmpfn() signature joined onto one line.
scx_tid_hash and scx_sched_hash have the same u64 key and also fall back to rhashtable_compare(). scx_bpf_tid_to_task() sits on hot paths too. Do you want to do the same for them as a follow-up?
Thanks.
--
tejun
Quoted 6 lines · Tejun Heo
Applied to sched_ext/for-7.4 with the
dsq_cmpfn()signature joined onto one line.
scx_tid_hashandscx_sched_hashhave the same u64 key and also fall back torhashtable_compare().scx_bpf_tid_to_task()sits on hot paths too. Do you want to do the same for them as a follow-up?
Yes, let me send those as follow-ups! Thanks!
Quoted 5 lines
Thanks.
--
tejun