Skip to contentSkip to conversation

User Managed Concurrency Groups

RFC PATCH In review Peter Oskolkov 2 participants 11 messages Jan 13, 2022 – Jan 27, 2022

Subsystems (9)
Memory management x86 VFS Scheduler +5 more subsystems
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 83872f95a1ea..04525933de94 100644
@@ -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
index 095b0aa378df..4b70cf8f1ec3 100644
@@ -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
index de53be905739..77f67d09b946 100644
@@ -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
#2 lore raw

RFC PATCH v2 2/5 x86/uaccess: Implement unsafe_try_cmpxchg_user()

In reply to Peter Oskolkov

From: 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
index ac96f9b2d64b..8277ec05be02 100644
@@ -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
#3 lore raw

RFC PATCH v2 3/5 sched: User Mode Concurency Groups

In reply to Peter Oskolkov

From: 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
index 976dd6b532bf..34a398f5a57b 100644
@@ -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
index fe8f8dd157b4..3d96af7e67cc 100644
@@ -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
index ebec69c35e95..f480e43c8bdf 100644
@@ -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
index 537d92c41105..1749f0f74fed 100644
@@ -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
index 2e2b8d6140ed..6318b0461cd2 100644
@@ -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
index 528a478dbda8..3ba0af15e223 100644
@@ -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
index 73a6f34b3847..8fdc4a1fa9a5 100644
@@ -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
index 4557a8b6086f..495949af981e 100644
@@ -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
index 41a728debdbd..15d1e330fdb9 100644
@@ -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
index bad713684c2e..7d7bd5c300b1 100644
@@ -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
index f702a6a63686..4bdd51c75aee 100644
@@ -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
index c7421f2d05e1..c03eea9bc738 100644
@@ -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
index 04525933de94..6e10080dc25a 100644
@@ -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
index d1944258cfc0..a4029e05129b 100644
@@ -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
#4 lore raw

RFC PATCH v2 4/5 sched: UMCG: add a blocked worker list

In reply to 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.

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
index a994bbb062d5..93fccb44283b 100644
@@ -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
#9 lore raw

RFC PATCH v2 5/5 sched: UMCG: allow to sys_umcg_kick UMCG servers

In reply to Peter Oskolkov

Add 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
index 93fccb44283b..a29e5e91a251 100644
@@ -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
index b85dec6b82e4..e33ec9eddc3e 100644
@@ -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
maintainer
#5 lore raw

Re: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list

In reply to Peter Oskolkov
Quoted 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...

#6 lore raw

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_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...

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.

maintainer
#7 lore raw

Re: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list

In reply to Peter Oskolkov
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 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_tas
 		return -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) {
maintainer
#10 lore raw

Re: [RFC PATCH v2 5/5] sched: UMCG: allow to sys_umcg_kick UMCG servers

In reply to Peter Oskolkov
Quoted 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
index 93fccb44283b..a29e5e91a251 100644
@@ -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
index b85dec6b82e4..e33ec9eddc3e 100644
@@ -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;
 }
#8 lore raw

Re: [RFC PATCH v2 4/5] sched: UMCG: add a blocked worker list

In reply to Peter Zijlstra
Quoted 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_tas
                return -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) {