User Managed Concurrency Groups
Subsystems (9)
v2 cover User Managed Concurrency Groups
This adds two small patches on top of peterz@'s RFC from
https://lore.kernel.org/lkml/[email protected]/
The new patches are not fully tested - I'm still working on it. I'll post another patch shortly that adds worker timeouts in sys_umcg_wait().
Sending this out just to break the silence and to assess if the approach I'm taking here is not strongly NACKed.
Peter Oskolkov (3):
sched/umcg: add WF_CURRENT_CPU and externise ttwu
sched: UMCG: add a blocked worker list
sched: UMCG: allow to sys_umcg_kick UMCG servers
Peter Zijlstra (2):
x86/uaccess: Implement unsafe_try_cmpxchg_user()
sched: User Mode Concurency Groups
arch/x86/Kconfig | 1 + arch/x86/entry/syscalls/syscall_64.tbl | 3 + arch/x86/include/asm/thread_info.h | 2 + arch/x86/include/asm/uaccess.h | 57 ++ fs/exec.c | 1 + include/linux/entry-common.h | 6 + include/linux/sched.h | 86 +++ include/linux/syscalls.h | 4 + include/linux/thread_info.h | 2 + include/uapi/asm-generic/unistd.h | 9 +- include/uapi/linux/umcg.h | 161 +++++ init/Kconfig | 15 + kernel/entry/common.c | 18 +- kernel/exit.c | 5 + kernel/sched/Makefile | 1 + kernel/sched/core.c | 12 +- kernel/sched/fair.c | 4 + kernel/sched/sched.h | 15 +- kernel/sched/umcg.c | 913 +++++++++++++++++++++++++ kernel/sys_ni.c | 5 + 20 files changed, 1305 insertions(+), 15 deletions(-) create mode 100644 include/uapi/linux/umcg.h create mode 100644 kernel/sched/umcg.c
base-commit: 85538cc07d6b6dcffc1df64a22308fcb05ecddf4
Signature · 1 line
2.34.1.703.g22d0c6ccf7-goog
RFC PATCH v2 1/5 sched/umcg: add WF_CURRENT_CPU and externise ttwu
From: Peter Oskolkov <[email protected]>
Add WF_CURRENT_CPU wake flag that advices the scheduler to move the wakee to the current CPU. This is useful for fast on-CPU context switching use cases such as UMCG.
In addition, make ttwu external rather than static so that the flag could be passed to it from outside of sched/core.c.
--- kernel/sched/core.c | 3 +-- kernel/sched/fair.c | 4 ++++ kernel/sched/sched.h | 15 +++++++++------ 3 files changed, 14 insertions(+), 8 deletions(-)
kernel/sched/core.c +1 -2
@@ -3980,8 +3980,7 @@ bool ttwu_state_match(struct task_struct *p, unsigned int state, int *success)* Return: %true if @p->state changes (an actual wakeup was done), * %false otherwise. */ -static int -try_to_wake_up (struct task_struct *p,unsigned int state,int wake_flags) +int try_to_wake_up (struct task_struct *p,unsigned int state,int wake_flags) {unsigned long flags;int cpu, success =0 ;
kernel/sched/fair.c +4 -0
@@ -6838,6 +6838,10 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags)if (wake_flags &WF_TTWU ) {record_wakee (p); +if ((wake_flags &WF_CURRENT_CPU ) && +cpumask_test_cpu (cpu, p->cpus_ptr)) +return cpu; +if (sched_energy_enabled ()) { new_cpu =find_energy_efficient_cpu (p, prev_cpu);if (new_cpu >=0 )
kernel/sched/sched.h +9 -6
@@ -2052,13 +2052,14 @@ static inline int task_on_rq_migrating(struct task_struct *p) }/* Wake flags. The first three directly map to some SD flag value */ -#define WF_EXEC 0x02/* Wakeup after exec; maps to SD_BALANCE_EXEC */ -#define WF_FORK 0x04/* Wakeup after fork; maps to SD_BALANCE_FORK */ -#define WF_TTWU 0x08/* Wakeup; maps to SD_BALANCE_WAKE */ +#define WF_EXEC 0x02/* Wakeup after exec; maps to SD_BALANCE_EXEC */ +#define WF_FORK 0x04/* Wakeup after fork; maps to SD_BALANCE_FORK */ +#define WF_TTWU 0x08/* Wakeup; maps to SD_BALANCE_WAKE */ -#define WF_SYNC 0x10/* Waker goes to sleep after wakeup */ -#define WF_MIGRATED 0x20/* Internal use, task got migrated */ -#define WF_ON_CPU 0x40/* Wakee is on_cpu */ +#define WF_SYNC 0x10/* Waker goes to sleep after wakeup */ +#define WF_MIGRATED 0x20/* Internal use, task got migrated */ +#define WF_ON_CPU 0x40/* Wakee is on_cpu */ +#define WF_CURRENT_CPU 0x80/* Prefer to move the wakee to the current CPU. */ #ifdef CONFIG_SMP static_assert (WF_EXEC ==SD_BALANCE_EXEC );
@@ -3112,6 +3113,8 @@ static inline bool is_per_cpu_kthread(struct task_struct *p)extern void swake_up_all_locked (struct swait_queue_head *q);extern void __prepare_to_swait (struct swait_queue_head *q,struct swait_queue *wait); +extern int try_to_wake_up (struct task_struct *tsk,unsigned int state,int wake_flags); +#ifdef CONFIG_PREEMPT_DYNAMIC extern int preempt_dynamic_mode;extern int sched_dynamic_mode (const char *str);
Signature · 1 line
2.34.1.703.g22d0c6ccf7-goog
RFC PATCH v2 2/5 x86/uaccess: Implement unsafe_try_cmpxchg_user()
In reply to Peter OskolkovFrom: Peter Zijlstra <[email protected]>
Do try_cmpxchg() loops on userspace addresses.
--- arch/x86/include/asm/uaccess.h | 57 ++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+)
arch/x86/include/asm/uaccess.h +57 -0
@@ -342,6 +342,24 @@ do { \ : [umem] "m" (__m(addr)) \ : : label) +#define __try_cmpxchg_user_asm (itype, _ptr, _pold, _new, label) ({ \ + bool success; \ + __typeof__(_ptr) _old = (__typeof__(_ptr))(_pold); \ + __typeof__(*(_ptr)) __old = *_old; \ + __typeof__(*(_ptr)) __new = (_new); \ + asm_volatile_goto("\n" \ + "1: " LOCK_PREFIX "cmpxchg"itype" %[new], %[ptr]\n"\ + _ASM_EXTABLE_UA(1b, %l[label]) \ + : CC_OUT(z) (success), \ + [ptr] "+m" (*_ptr), \ + [old] "+a" (__old) \ + : [new] "r" (__new) \ + : "memory", "cc" \ + : label); \ + if (unlikely(!success)) \ + *_old = __old; \ + likely(success); }) +#else // !CONFIG_CC_HAS_ASM_GOTO_OUTPUT #ifdef CONFIG_X86_32
@@ -407,6 +425,30 @@ do { \ : [umem] "m" (__m(addr)), \ "0" (err)) +#define __try_cmpxchg_user_asm (itype, _ptr, _pold, _new, label) ({ \ + int __err = 0; \ + bool success; \ + __typeof__(_ptr) _old = (__typeof__(_ptr))(_pold); \ + __typeof__(*(_ptr)) __old = *_old; \ + __typeof__(*(_ptr)) __new = (_new); \ + asm volatile("\n" \ + "1: " LOCK_PREFIX "cmpxchg"itype" %[new], %[ptr]\n"\ + CC_SET(z) \ + "2:\n" \ + _ASM_EXTABLE_TYPE_REG(1b, 2b, EX_TYPE_EFAULT_REG, \ + %[errout]) \ + : CC_OUT(z) (success), \ + [errout] "+r" (__err), \ + [ptr] "+m" (*_ptr), \ + [old] "+a" (__old) \ + : [new] "r" (__new) \ + : "memory", "cc"); \ + if (unlikely(__err)) \ + goto label; \ + if (unlikely(!success)) \ + *_old = __old; \ + likely(success); }) +#endif // CONFIG_CC_HAS_ASM_GOTO_OUTPUT /* FIXME: this hack is definitely wrong -AK */
@@ -501,6 +543,21 @@ do { \ } while (0)#endif // CONFIG_CC_HAS_ASM_GOTO_OUTPUT +extern void __try_cmpxchg_user_wrong_size (void ); + +#define unsafe_try_cmpxchg_user (_ptr, _oldp, _nval, _label) ({ \ + __typeof__(*(_ptr)) __ret; \ + switch (sizeof(__ret)) { \ + case 4: __ret = __try_cmpxchg_user_asm("l", (_ptr), (_oldp), \ + (_nval), _label); \ + break; \ + case 8: __ret = __try_cmpxchg_user_asm("q", (_ptr), (_oldp), \ + (_nval), _label); \ + break; \ + default: __try_cmpxchg_user_wrong_size(); \ + } \ + __ret; }) +/* * We want the unsafe accessors to always be inlined and use * the error labels - thus the macro games.
Signature · 1 line
2.34.1.703.g22d0c6ccf7-goog
RFC PATCH v2 3/5 sched: User Mode Concurency Groups
In reply to Peter OskolkovFrom: Peter Zijlstra <[email protected]>
User Managed Concurrency Groups is an M:N threading toolkit that allows constructing user space schedulers designed to efficiently manage heterogeneous in-process workloads while maintaining high CPU utilization (95%+).
XXX moar changelog explaining how this is moar awesome than traditional user-space threading.
The big thing that's missing is the SMP wake-to-remote-idle.
The big assumption this whole thing is build on is that pin_user_pages() preserves user mappings in so far that pagefault_disable() will never generate EFAULT (unless the user does munmap() in which case it can keep the pieces).
shrink_page_list() does page_maybe_dma_pinned() before try_to_unmap() and as such seems to respect this constraint.
unmap_and_move() however seems willing to unmap otherwise pinned (and hence unmigratable) pages. This might need fixing.
--- arch/x86/Kconfig | 1 + arch/x86/entry/syscalls/syscall_64.tbl | 3 + arch/x86/include/asm/thread_info.h | 2 + fs/exec.c | 1 + include/linux/entry-common.h | 6 + include/linux/sched.h | 86 +++ include/linux/syscalls.h | 4 + include/linux/thread_info.h | 2 + include/uapi/asm-generic/unistd.h | 9 +- include/uapi/linux/umcg.h | 143 ++++ init/Kconfig | 15 + kernel/entry/common.c | 18 +- kernel/exit.c | 5 + kernel/sched/Makefile | 1 + kernel/sched/core.c | 9 +- kernel/sched/umcg.c | 868 +++++++++++++++++++++++++ kernel/sys_ni.c | 5 + 17 files changed, 1171 insertions(+), 7 deletions(-) create mode 100644 include/uapi/linux/umcg.h create mode 100644 kernel/sched/umcg.c
arch/x86/Kconfig +1 -0
@@ -248,6 +248,7 @@ config X86 select HAVE_RSEQ select HAVE_SYSCALL_TRACEPOINTS select HAVE_UNSTABLE_SCHED_CLOCK + select HAVE_UMCG if X86_64 select HAVE_USER_RETURN_NOTIFIER select HAVE_GENERIC_VDSO select HOTPLUG_SMT if SMP
arch/x86/entry/syscalls/syscall_64.tbl +3 -0
@@ -371,6 +371,9 @@ 447 common memfd_secret sys_memfd_secret 448 common process_mrelease sys_process_mrelease 449 common futex_waitv sys_futex_waitv +450 common umcg_ctl sys_umcg_ctl +451 common umcg_wait sys_umcg_wait +452 common umcg_kick sys_umcg_kick # # Due to a historical design error, certain syscalls are numbered differently
arch/x86/include/asm/thread_info.h +2 -0
@@ -83,6 +83,7 @@ struct thread_info {#define TIF_NEED_RESCHED 3/* rescheduling necessary */ #define TIF_SINGLESTEP 4/* reenable singlestep on user return*/ #define TIF_SSBD 5/* Speculative store bypass disable */ +#define TIF_UMCG 6/* UMCG return to user hook */ #define TIF_SPEC_IB 9/* Indirect branch speculation mitigation */ #define TIF_SPEC_L1D_FLUSH 10/* Flush L1D on mm switches (processes) */ #define TIF_USER_RETURN_NOTIFY 11/* notify kernel of userspace return */
@@ -107,6 +108,7 @@ struct thread_info {#define _TIF_NEED_RESCHED (1 << TIF_NEED_RESCHED)#define _TIF_SINGLESTEP (1 << TIF_SINGLESTEP)#define _TIF_SSBD (1 << TIF_SSBD) +#define _TIF_UMCG (1 << TIF_UMCG)#define _TIF_SPEC_IB (1 << TIF_SPEC_IB)#define _TIF_SPEC_L1D_FLUSH (1 << TIF_SPEC_L1D_FLUSH)#define _TIF_USER_RETURN_NOTIFY (1 << TIF_USER_RETURN_NOTIFY)
fs/exec.c +1 -0
@@ -1838,6 +1838,7 @@ static int bprm_execve(struct linux_binprm *bprm, current->fs->in_exec =0 ; current->in_execve =0 ;rseq_execve (current); +umcg_execve (current);acct_update_integrals (current);task_numa_free (current, false);return retval;
include/linux/entry-common.h +6 -0
@@ -22,6 +22,10 @@# define _TIF_UPROBE (0)#endif +#ifndef _TIF_UMCG +# define _TIF_UMCG (0) +#endif +/* * SYSCALL_WORK flags handled in syscall_enter_from_user_mode() */
@@ -42,11 +46,13 @@ SYSCALL_WORK_SYSCALL_EMU | \ SYSCALL_WORK_SYSCALL_AUDIT | \ SYSCALL_WORK_SYSCALL_USER_DISPATCH | \ + SYSCALL_WORK_SYSCALL_UMCG | \ ARCH_SYSCALL_WORK_ENTER)#define SYSCALL_WORK_EXIT (SYSCALL_WORK_SYSCALL_TRACEPOINT | \ SYSCALL_WORK_SYSCALL_TRACE | \ SYSCALL_WORK_SYSCALL_AUDIT | \ SYSCALL_WORK_SYSCALL_USER_DISPATCH | \ + SYSCALL_WORK_SYSCALL_UMCG | \ SYSCALL_WORK_SYSCALL_EXIT_TRAP | \ ARCH_SYSCALL_WORK_EXIT)
include/linux/sched.h +86 -0
110 lines not on this page · raw message
include/linux/syscalls.h +4 -0
@@ -72,6 +72,7 @@ struct open_how;struct mount_attr ;struct landlock_ruleset_attr ;enum landlock_rule_type ; +struct umcg_task ;#include <linux/types.h> #include <linux/aio_abi.h>
@@ -1057,6 +1058,9 @@ asmlinkage long sys_landlock_add_rule(int ruleset_fd, enum landlock_rule_type ru const void __user *rule_attr, __u32 flags);asmlinkage long sys_landlock_restrict_self (int ruleset_fd,__u32 flags);asmlinkage long sys_memfd_secret (unsigned int flags); +asmlinkage long sys_umcg_ctl (u32 flags,struct umcg_task __user *self,clockid_t which_clock); +asmlinkage long sys_umcg_wait (u32 flags,u64 abs_timeout); +asmlinkage long sys_umcg_kick (u32 flags,pid_t tid);/* * Architecture-specific system calls
include/linux/thread_info.h +2 -0
@@ -46,6 +46,7 @@ enum syscall_work_bit {SYSCALL_WORK_BIT_SYSCALL_AUDIT ,SYSCALL_WORK_BIT_SYSCALL_USER_DISPATCH ,SYSCALL_WORK_BIT_SYSCALL_EXIT_TRAP , + SYSCALL_WORK_BIT_SYSCALL_UMCG, };#define SYSCALL_WORK_SECCOMP BIT(SYSCALL_WORK_BIT_SECCOMP)
@@ -55,6 +56,7 @@ enum syscall_work_bit {#define SYSCALL_WORK_SYSCALL_AUDIT BIT(SYSCALL_WORK_BIT_SYSCALL_AUDIT)#define SYSCALL_WORK_SYSCALL_USER_DISPATCH BIT(SYSCALL_WORK_BIT_SYSCALL_USER_DISPATCH)#define SYSCALL_WORK_SYSCALL_EXIT_TRAP BIT(SYSCALL_WORK_BIT_SYSCALL_EXIT_TRAP) +#define SYSCALL_WORK_SYSCALL_UMCG BIT(SYSCALL_WORK_BIT_SYSCALL_UMCG)#endif #include <asm/thread_info.h>
include/uapi/asm-generic/unistd.h +8 -1
@@ -883,8 +883,15 @@ __SYSCALL(__NR_process_mrelease, sys_process_mrelease)#define __NR_futex_waitv 449 __SYSCALL(__NR_futex_waitv, sys_futex_waitv) +#define __NR_umcg_ctl 450 +__SYSCALL(__NR_umcg_ctl, sys_umcg_ctl) +#define __NR_umcg_wait 451 +__SYSCALL(__NR_umcg_wait, sys_umcg_wait) +#define __NR_umcg_kick 452 +__SYSCALL(__NR_umcg_kick, sys_umcg_kick) +#undef __NR_syscalls -#define __NR_syscalls 450 +#define __NR_syscalls 453/* * 32 bit systems traditionally used different
include/uapi/linux/umcg.h new file +143 -0
143 lines not on this page · raw message
init/Kconfig +15 -0
@@ -1686,6 +1686,21 @@ config MEMBARRIER If unsure, say Y. +config HAVE_UMCG + bool + +config UMCG + bool "Enable User Managed Concurrency Groups API" + depends on 64BIT + depends on GENERIC_ENTRY + depends on HAVE_UMCG + default n + help + Enable User Managed Concurrency Groups API, which form the basis + for an in-process M:N userspace scheduling framework. + At the moment this is an experimental/RFC feature that is not + guaranteed to be backward-compatible. + config KALLSYMS bool "Load all symbols for debugging/ksymoops" if EXPERT default y
kernel/entry/common.c +14 -4
@@ -6,6 +6,7 @@#include <linux/livepatch.h> #include <linux/audit.h> #include <linux/tick.h> +#include <linux/sched.h> #include "common.h"
@@ -76,6 +77,9 @@ static long syscall_trace_enter(struct pt_regs *regs, long syscall,if (unlikely (work &SYSCALL_WORK_SYSCALL_TRACEPOINT ))trace_sys_enter (regs, syscall); +if (work &SYSCALL_WORK_SYSCALL_UMCG ) +umcg_sys_enter (regs, syscall); +syscall_enter_audit (regs, syscall);return ret ? : syscall;
@@ -155,8 +159,7 @@ static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,* Before returning to user space ensure that all pending work * items have been completed. */ -while (ti_work &EXIT_TO_USER_MODE_WORK ) { - + do { local_irq_enable_exit_to_user(ti_work); if (ti_work & _TIF_NEED_RESCHED)
@@ -168,6 +171,10 @@ static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,if (ti_work & _TIF_PATCH_PENDING)klp_update_patch_state (current); +/* must be before handle_signal_work(); terminates on sigpending */ +if (ti_work & _TIF_UMCG) +umcg_notify_resume (regs); +if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))handle_signal_work (regs, ti_work);
@@ -188,7 +195,7 @@ static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,tick_nohz_user_enter_prepare (); ti_work =read_thread_flags (); - } + }while (ti_work &EXIT_TO_USER_MODE_WORK );/* Return the latest work state for arch_exit_to_user_mode() */ return ti_work;
@@ -203,7 +210,7 @@ static void exit_to_user_mode_prepare(struct pt_regs *regs)/* Flush pending rcuog wakeup before the last need_resched() check */ tick_nohz_user_enter_prepare (); -if (unlikely (ti_work &EXIT_TO_USER_MODE_WORK )) +if (unlikely (ti_work & (EXIT_TO_USER_MODE_WORK | _TIF_UMCG))) ti_work =exit_to_user_mode_loop (regs, ti_work);arch_exit_to_user_mode_prepare (regs, ti_work);
@@ -253,6 +260,9 @@ static void syscall_exit_work(struct pt_regs *regs, unsigned long work) step =report_single_step (work);if (step || work &SYSCALL_WORK_SYSCALL_TRACE )arch_syscall_exit_tracehook (regs, step); + +if (work &SYSCALL_WORK_SYSCALL_UMCG ) +umcg_sys_exit (regs); }/*
kernel/exit.c +5 -0
@@ -749,6 +749,10 @@ void __noreturn do_exit(long code)if (unlikely (!tsk->pid))panic ("Attempted to kill the idle task!" ); +/* Turn off UMCG sched hooks. */ +if (unlikely (tsk->flags &PF_UMCG_WORKER )) + tsk->flags &= ~PF_UMCG_WORKER ; +/* * If do_exit is called because this processes oopsed, it's possible * that get_fs() was left as KERNEL_DS, so reset it to USER_DS before
@@ -786,6 +790,7 @@ void __noreturn do_exit(long code)io_uring_files_cancel ();exit_signals (tsk);/* sets PF_EXITING */ +umcg_handle_exit ();/* sync mm's RSS info before statistics gathering */ if (tsk->mm)
kernel/sched/Makefile +1 -0
@@ -41,3 +41,4 @@ obj-$(CONFIG_MEMBARRIER) += membarrier.o obj-$(CONFIG_CPU_ISOLATION) += isolation.o obj-$(CONFIG_PSI) += psi.o obj-$(CONFIG_SCHED_CORE) += core_sched.o +obj-$(CONFIG_UMCG) += umcg.o
kernel/sched/core.c +7 -2
@@ -4272,6 +4272,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p) p->wake_entry.u_flags =CSD_TYPE_TTWU ; p->migration_pending =NULL ;#endif +umcg_clear_child (p); }DEFINE_STATIC_KEY_FALSE (sched_numa_balancing);
@@ -6330,9 +6331,11 @@ static inline void sched_submit_work(struct task_struct *tsk)* If a worker goes to sleep, notify and ask workqueue whether it * wants to wake up a task to maintain concurrency. */ -if (task_flags & (PF_WQ_WORKER |PF_IO_WORKER )) { +if (task_flags & (PF_WQ_WORKER |PF_IO_WORKER |PF_UMCG_WORKER )) {if (task_flags &PF_WQ_WORKER )wq_worker_sleeping (tsk); +else if (task_flags &PF_UMCG_WORKER ) +umcg_wq_worker_sleeping (tsk);else io_wq_worker_sleeping (tsk); }
@@ -6350,9 +6353,11 @@ static inline void sched_submit_work(struct task_struct *tsk)static void sched_update_worker (struct task_struct *tsk) { -if (tsk->flags & (PF_WQ_WORKER |PF_IO_WORKER )) { +if (tsk->flags & (PF_WQ_WORKER |PF_IO_WORKER |PF_UMCG_WORKER )) {if (tsk->flags &PF_WQ_WORKER )wq_worker_running (tsk); +else if (tsk->flags &PF_UMCG_WORKER ) +umcg_wq_worker_running (tsk);else io_wq_worker_running (tsk); }
kernel/sched/umcg.c new file +868 -0
868 lines not on this page · raw message
kernel/sys_ni.c +5 -0
@@ -273,6 +273,11 @@ COND_SYSCALL(landlock_create_ruleset);COND_SYSCALL (landlock_add_rule);COND_SYSCALL (landlock_restrict_self); +/* kernel/sched/umcg.c */ +COND_SYSCALL (umcg_ctl); +COND_SYSCALL (umcg_wait); +COND_SYSCALL (umcg_kick); +/* arch/example/kernel/sys_example.c */ /* mm/fadvise.c */
Signature · 1 line
2.34.1.703.g22d0c6ccf7-goog
RFC PATCH v2 4/5 sched: UMCG: add a blocked worker list
In reply to Peter OskolkovThe original idea of a UMCG server was that it was used as a proxy for a CPU, so if a worker associated with the server is RUNNING, the server itself is never ever was allowed to be RUNNING as well; when umcg_wait() returned for a server, it meant that its worker became BLOCKED.
In the new (old?) "per server runqueues" model implemented in the previous patch in this patchset, servers are woken when a previously blocked worker on their runqueue finishes its blocking operation, even if the currently RUNNING worker continues running.
As now a server may run while a worker assigned to it is running, the original idea of having at most a single worker RUNNING per server, as a means to control the number of running workers, is not really enforced, and the server, woken by a worker doing BLOCKED=>RUNNABLE transition, may then call sys_umcg_wait() with a second/third/etc. worker to run.
Support this scenario by adding a blocked worker list:
when a worker transitions RUNNING=>BLOCKED, not only its server is woken, but the worker is also added to the blocked worker list of its server.
This change introduces the following benefits:
- block detection how behaves similarly to wake detection; without this patch worker wakeups added wakees to the list and woke the server, while worker blocks only woke the server without adding blocked workers to a list, forcing servers to explicitly check worker's state;
- if the blocked worker woke sufficiently quickly, the server woken on the block event would observe its worker now as RUNNABLE, so the block event had to be inferred rather than explicitly signalled by the worker being added to the blocked worker list;
- it is now possible for a single server to control several RUNNING workers, which makes writing userspace schedulers simpler for smaller processes that do not need to scale beyond one "server";
- if the userspace wants to keep at most a single RUNNING worker per server, and have multiple servers with their own runqueues, this model is also naturally supported here.
So this change basically decouples block/wake detection from M:N threading in the sense that the number of servers is now does not have to be M or N, but is more driven by the scalability needs of the userspace application.
Why keep this server/worker model at all then, and not use something like io_uring to deliver block/wake events to the userspace? The main benefit of this model is that servers are woken synchronously on-cpu when an event happens, while io_uring is more of an asynchronous event framework, so latencies in this model are potentially better.
In addition, "multiple runqueues" type of scheduling is much easier to implement with this method than with io_uring.
--- include/uapi/linux/umcg.h | 10 ++++- kernel/sched/umcg.c | 90 ++++++++++++++++++++++++++++----------- 2 files changed, 75 insertions(+), 25 deletions(-)
include/uapi/linux/umcg.h +9 -1
@@ -116,6 +116,14 @@ struct umcg_task {__u64 blocked_ts;/* w */ __u64 runnable_ts;/* w */ +/** +* @blocked_workers_ptr: a single-linked list of blocked workers. +* +* Readable/writable by both the kernel and the userspace: the +* kernel adds items to the list, userspace removes them. +*/ +__u64 blocked_workers_ptr;/* r/w */ +/** * @runnable_workers_ptr: a single-linked list of runnable workers. *
@@ -124,7 +132,7 @@ struct umcg_task {*/ __u64 runnable_workers_ptr;/* r/w */ -__u64 __zero[3 ]; +__u64 __zero[2 ]; } __attribute__((packed, aligned(UMCG_TASK_ALIGN)));
kernel/sched/umcg.c +66 -24
114 lines not on this page · raw message
Signature · 1 line
2.34.1.703.g22d0c6ccf7-goog
RFC PATCH v2 5/5 sched: UMCG: allow to sys_umcg_kick UMCG servers
In reply to Peter OskolkovAdd enum umcg_kick_flags:
@UMCG_KICK_RESCHED: reschedule the task; used for worker preemption @UMCG_KICK_TTWU: wake the task; used to wake servers.
It is sometimes useful to wake UMCG servers from the userspace, for example when a server detects a worker wakeup and wakes an idle server to run the newly woken worker.
--- include/uapi/linux/umcg.h | 10 ++++++++++ kernel/sched/umcg.c | 7 +++++-- 2 files changed, 15 insertions(+), 2 deletions(-)
include/uapi/linux/umcg.h +10 -0
@@ -148,4 +148,14 @@ enum umcg_ctl_flag { UMCG_CTL_WORKER = 0x10000, }; +/** +* enum umcg_kick_flag - flags to pass to sys_umcg_kick +* @UMCG_KICK_RESCHED: reschedule the task; used for worker preemption +* @UMCG_KICK_TTWU: wake the task; used to wake servers +*/ +enum umcg_kick_flag { +UMCG_KICK_RESCHED =0x001 , +UMCG_KICK_TTWU =0x002 , +}; +#endif /* _UAPI_LINUX_UMCG_H */
kernel/sched/umcg.c +5 -2
@@ -669,12 +669,15 @@ SYSCALL_DEFINE2(umcg_kick, u32, flags, pid_t, tid)if (!task)return -ESRCH ; -if (flags) +if (flags !=UMCG_KICK_RESCHED && flags !=UMCG_KICK_TTWU )return -EINVAL ;#ifdef CONFIG_SMP -smp_send_reschedule (task_cpu (task)); +if (flags ==UMCG_KICK_RESCHED ) +smp_send_reschedule (task_cpu (task));#endif +if (flags ==UMCG_KICK_TTWU ) +try_to_wake_up (task,TASK_NORMAL ,0 );return 0 ; }
Signature · 1 line
2.34.1.703.g22d0c6ccf7-goog
Peter Zijlstra
maintainerRe: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list
In reply to Peter OskolkovQuoted 42 lines · Peter Oskolkov
The original idea of a UMCG server was that it was used as a proxy for a CPU, so if a worker associated with the server is RUNNING, the server itself is never ever was allowed to be RUNNING as well; when
umcg_wait()returned for a server, it meant that its worker became BLOCKED.In the new (old?) "per server runqueues" model implemented in the previous patch in this patchset, servers are woken when a previously blocked worker on their runqueue finishes its blocking operation, even if the currently RUNNING worker continues running.
As now a server may run while a worker assigned to it is running, the original idea of having at most a single worker RUNNING per server, as a means to control the number of running workers, is not really enforced, and the server, woken by a worker doing BLOCKED=>RUNNABLE transition, may then call
sys_umcg_wait()with a second/third/etc. worker to run.Support this scenario by adding a blocked worker list:
when a worker transitions RUNNING=>BLOCKED, not only its server is woken, but the worker is also added to the blocked worker list of its server.This change introduces the following benefits:
- block detection how behaves similarly to wake detection; without this patch worker wakeups added wakees to the list and woke the server, while worker blocks only woke the server without adding blocked workers to a list, forcing servers to explicitly check worker's state;
- if the blocked worker woke sufficiently quickly, the server woken on the block event would observe its worker now as RUNNABLE, so the block event had to be inferred rather than explicitly signalled by the worker being added to the blocked worker list;
- it is now possible for a single server to control several RUNNING workers, which makes writing userspace schedulers simpler for smaller processes that do not need to scale beyond one "server";
- if the userspace wants to keep at most a single RUNNING worker per server, and have multiple servers with their own runqueues, this model is also naturally supported here.
Quoted 4 lines
So this change basically decouples block/wake detection from M:N threading in the sense that the number of servers is now does not have to be M or N, but is more driven by the scalability needs of the userspace application.
So I don't object to having this blocking list, we had that early on in the discussions.
*However*, combined with WF_CURRENT_CPU this 1:N userspace model doesn't really make sense, also combined with Proxy-Exec (if we ever get that sorted) it will fundamentally not work.
More consideration is needed I think...
Re: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list
Quoted 2 lines · Peter Zijlstra
On Thu, Jan 13, 2022 at 03:39:39PM -0800, Peter Oskolkov wrote:
[...]
Quoted 6 lines
Quoted 5 lines
So this change basically decouples block/wake detection from M:N threading in the sense that the number of servers is now does not have to be M or N, but is more driven by the scalability needs of the userspace application.
Quoted 8 lines
So I don't object to having this blocking list, we had that early on in the discussions.
*However*, combined with
WF_CURRENT_CPUthis 1:N userspace model doesn't really make sense, also combined with Proxy-Exec (if we ever get that sorted) it will fundamentally not work.More consideration is needed I think...
I was not very clear here. The intent of this change is not to make 1:N a good general approach, but to make "several running workers per single server" a viable option.
My guess, based on some numbers/benchmarks from another project, is that having a single server/runqueue per four or eight running workers, properly aligned with (= affined to) an AMD chiplet, will be the most performant solution, comparing to both a runqueue per single running worker and to a global runqueue. On Intel this will probably look like a single runqueue per core (2 running workers/HT threads).
So in this model a "server" represents a runqueue.
I'll reply to other active umcg discussions shortly.
Peter Zijlstra
maintainerRe: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list
In reply to Peter OskolkovQuoted 7 lines · Peter Oskolkov
This change introduces the following benefits:
- block detection how behaves similarly to wake detection; without this patch worker wakeups added wakees to the list and woke the server, while worker blocks only woke the server without adding blocked workers to a list, forcing servers to explicitly check worker's state;
Quoted 5 lines
- if the blocked worker woke sufficiently quickly, the server woken on the block event would observe its worker now as RUNNABLE, so the block event had to be inferred rather than explicitly signalled by the worker being added to the blocked worker list;
This I think is missing the point, there is no race if the server checks curr->state == RUNNING.
Quoted 4 lines
- it is now possible for a single server to control several RUNNING workers, which makes writing userspace schedulers simpler for smaller processes that do not need to scale beyond one "server";
How about something like so on top?
include/linux/sched.h +1 -0
@@ -1298,6 +1298,7 @@ struct task_struct {#ifdef CONFIG_UMCG /* setup by sys_umcg_ctrl() */ +u32 umcg_flags;clockid_t umcg_clock;struct umcg_task __user *umcg_task;
include/uapi/linux/umcg.h +4 -0
@@ -119,6 +119,8 @@ struct umcg_task {* * Readable/writable by both the kernel and the userspace: the * kernel adds items to the list, userspace removes them. +* +* Only used with UMCG_CTL_MULTI. */ __u64 blocked_workers_ptr;/* r/w */
@@ -147,11 +149,13 @@ enum umcg_wait_flag {* @UMCG_CTL_REGISTER: register the current task as a UMCG task * @UMCG_CTL_UNREGISTER: unregister the current task as a UMCG task * @UMCG_CTL_WORKER: register the current task as a UMCG worker +* @UMCG_CTL_MULTI: allow 1:n worker relations, enables blocked_workers_ptr */ enum umcg_ctl_flag {UMCG_CTL_REGISTER =0x00001 ,UMCG_CTL_UNREGISTER =0x00002 ,UMCG_CTL_WORKER =0x10000 , +UMCG_CTL_MULTI =0x20000 , };#endif /* _UAPI_LINUX_UMCG_H */
kernel/sched/umcg.c +29 -3
@@ -335,7 +335,7 @@ static inline int umcg_enqueue_runnable( }/* -* Enqueue @tsk on it's server's blocked list +* Enqueue @tsk on it's server's blocked list OR ensure @tsk == server::next_tid * * Must be called in umcg_pin_pages() context, relies on tsk->umcg_server. *
@@ -346,10 +346,34 @@ static inline int umcg_enqueue_runnable(* Returns: * 0: success * -EFAULT +* -ESRCH server::next_tid is not a valid UMCG task +* -EINVAL server::next_tid doesn't match @tsk */ static inline int umcg_enqueue_blocked (struct task_struct *tsk) { -return umcg_enqueue (tsk, true/* blocked */ ); +struct task_struct *next; +u32 next_tid; +int ret; + +if (tsk->umcg_server->umcg_flags &UMCG_CTL_MULTI ) +return umcg_enqueue (tsk, true/* blocked */ ); + +/* +* When !MULTI, ensure this worker is the current worker, +* ensuring the 1:1 relation. +*/ +if (get_user (next_tid, &tsk->umcg_server_task->next_tid)) +return -EFAULT ; + + next =umcg_get_task (next_tid); +if (!next) +return -ESRCH ; + + ret = (next == tsk) ?0 : -EINVAL ; + +put_task_struct (next); + +return ret; }/* pre-schedule() */
@@ -911,6 +934,8 @@ static int umcg_register(struct umcg_tasreturn -EINVAL ; } + current->umcg_flags = flags; +if (current->umcg_task || !self)return -EINVAL ;
@@ -1061,7 +1086,7 @@ SYSCALL_DEFINE3(umcg_ctl, u32, flags, st flags &= ~UMCG_CTL_CMD ; -if (flags & ~(UMCG_CTL_WORKER )) +if (flags & ~(UMCG_CTL_WORKER |UMCG_CTL_MULTI ))return -EINVAL ;switch (cmd) {
Peter Zijlstra
maintainerRe: [RFC PATCH v2 5/5] sched: UMCG: allow to sys_umcg_kick UMCG servers
In reply to Peter OskolkovQuoted 36 lines · Peter Oskolkov
--- include/uapi/linux/umcg.h | 10 ++++++++++ kernel/sched/umcg.c | 7 +++++-- 2 files changed, 15 insertions(+), 2 deletions(-)include/uapi/linux/umcg.h +10
-0@@ -148,4 +148,14 @@ enum umcg_ctl_flag { UMCG_CTL_WORKER = 0x10000, }; +/** +* enum umcg_kick_flag - flags to pass to sys_umcg_kick +* @UMCG_KICK_RESCHED: reschedule the task; used for worker preemption +* @UMCG_KICK_TTWU: wake the task; used to wake servers +*/ +enum umcg_kick_flag { +UMCG_KICK_RESCHED =0x001 , +UMCG_KICK_TTWU =0x002 , +}; +#endif /* _UAPI_LINUX_UMCG_H */ kernel/sched/umcg.c +1
-1@@ -669,12 +669,15 @@ SYSCALL_DEFINE2(umcg_kick, u32, flags, pid_t, tid)if (!task)return -ESRCH ; -if (flags) +if (flags !=UMCG_KICK_RESCHED && flags !=UMCG_KICK_TTWU )return -EINVAL ;
kernel/sched/umcg.c SYSCALL_DEFINE2(umcg_kick, u32, flags, pid_t, tid) · line 683
Quoted 10 lines
kernel/sched/umcg.c +4
-1#ifdef CONFIG_SMP -smp_send_reschedule (task_cpu (task)); +if (flags ==UMCG_KICK_RESCHED ) +smp_send_reschedule (task_cpu (task));#endif +if (flags ==UMCG_KICK_TTWU ) +try_to_wake_up (task,TASK_NORMAL ,0 );return 0 ; }
I'm thinking the simpler thing is this..
(also note the task ref leak fixed)
kernel/sched/umcg.c +10 -4
@@ -719,16 +719,22 @@ void umcg_notify_resume(struct pt_regs **/ SYSCALL_DEFINE2(umcg_kick, u32, flags, pid_t, tid) { -struct task_struct *task =umcg_get_task (tid); -if (!task) -return -ESRCH ; +struct task_struct *task;if (flags)return -EINVAL ; + + task =umcg_get_task (tid); +if (!task) +return -ESRCH ; +if (!try_to_wake_up (task,TASK_NORMAL ,WF_CURRENT_CPU )) {#ifdef CONFIG_SMP -smp_send_reschedule (task_cpu (task)); +smp_send_reschedule (task_cpu (task));#endif + } + +put_task_struct (task);return 0 ; }
Re: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list
In reply to Peter ZijlstraQuoted 19 lines · Peter Zijlstra
Quoted 7 lines · Peter Oskolkov
This change introduces the following benefits:
- block detection how behaves similarly to wake detection; without this patch worker wakeups added wakees to the list and woke the server, while worker blocks only woke the server without adding blocked workers to a list, forcing servers to explicitly check worker's state;Quoted 5 lines
- if the blocked worker woke sufficiently quickly, the server woken on the block event would observe its worker now as RUNNABLE, so the block event had to be inferred rather than explicitly signalled by the worker being added to the blocked worker list;
This I think is missing the point, there is no race if the server checks
curr->state== RUNNING.
Quoted 6 lines
Quoted 4 lines
- it is now possible for a single server to control several RUNNING workers, which makes writing userspace schedulers simpler for smaller processes that do not need to scale beyond one "server";
How about something like so on top?
This will work, I think. Thanks!
----------
On a more general note, it looks like the original desire to keep state in the userspace memory (TLS) instead of in task_struct has lead to a lot of pain and complexity due to the difficulty of updating the userspace from non-preemptible/sched contexts. And a bunch of stuff still trickled down to task_struct.
Is it too late to revisit the design? If all state is kept in task_struct, most of the complexity in the patchset will go away.
The only extra thing will be the fact that the kernel will maintain the list of blocked/runnable workers, and so there will be an additional syscall to get it out of the kernel and into the userspace. But all the pain of pinning pages and related mm changes will go away...
Quoted 101 lines
include/linux/sched.h +1
-0@@ -1298,6 +1298,7 @@ struct task_struct {#ifdef CONFIG_UMCG /* setup by sys_umcg_ctrl() */ +u32 umcg_flags;clockid_t umcg_clock;struct umcg_task __user *umcg_task;include/uapi/linux/umcg.h +4
-0@@ -119,6 +119,8 @@ struct umcg_task {* * Readable/writable by both the kernel and the userspace: the * kernel adds items to the list, userspace removes them. +* +* Only used with UMCG_CTL_MULTI. */ __u64 blocked_workers_ptr;/* r/w */ @@ -147,11 +149,13 @@ enum umcg_wait_flag {* @UMCG_CTL_REGISTER: register the current task as a UMCG task * @UMCG_CTL_UNREGISTER: unregister the current task as a UMCG task * @UMCG_CTL_WORKER: register the current task as a UMCG worker +* @UMCG_CTL_MULTI: allow 1:n worker relations, enables blocked_workers_ptr */ enum umcg_ctl_flag {UMCG_CTL_REGISTER =0x00001 ,UMCG_CTL_UNREGISTER =0x00002 ,UMCG_CTL_WORKER =0x10000 , +UMCG_CTL_MULTI =0x20000 , };#endif /* _UAPI_LINUX_UMCG_H */ kernel/sched/umcg.c +29
-3@@ -335,7 +335,7 @@ static inline int umcg_enqueue_runnable( }/* -* Enqueue @tsk on it's server's blocked list +* Enqueue @tsk on it's server's blocked list OR ensure @tsk == server::next_tid * * Must be called in umcg_pin_pages() context, relies on tsk->umcg_server. * @@ -346,10 +346,34 @@ static inline int umcg_enqueue_runnable(* Returns: * 0: success * -EFAULT +* -ESRCH server::next_tid is not a valid UMCG task +* -EINVAL server::next_tid doesn't match @tsk */ static inline int umcg_enqueue_blocked (struct task_struct *tsk) { -return umcg_enqueue (tsk, true/* blocked */ ); +struct task_struct *next; +u32 next_tid; +int ret; + +if (tsk->umcg_server->umcg_flags &UMCG_CTL_MULTI ) +return umcg_enqueue (tsk, true/* blocked */ ); + +/* +* When !MULTI, ensure this worker is the current worker, +* ensuring the 1:1 relation. +*/ +if (get_user (next_tid, &tsk->umcg_server_task->next_tid)) +return -EFAULT ; + + next =umcg_get_task (next_tid); +if (!next) +return -ESRCH ; + + ret = (next == tsk) ?0 : -EINVAL ; + +put_task_struct (next); + +return ret; }/* pre-schedule() */ @@ -911,6 +934,8 @@ static int umcg_register(struct umcg_tasreturn -EINVAL ; } + current->umcg_flags = flags; +if (current->umcg_task || !self)return -EINVAL ;@@ -1061,7 +1086,7 @@ SYSCALL_DEFINE3(umcg_ctl, u32, flags, st flags &= ~UMCG_CTL_CMD ; -if (flags & ~(UMCG_CTL_WORKER )) +if (flags & ~(UMCG_CTL_WORKER |UMCG_CTL_MULTI ))return -EINVAL ;switch (cmd) {