RFC: sched/UMCG
Subsystems (5)
cover RFC: sched/UMCG
This is another attempt at implementing UMCG, based on discussion in https://lore.kernel.org/patchwork/cover/1433967/
Most of the "why" is covered here (some details are obsolete):
https://lore.kernel.org/patchwork/cover/1433967/#1632328
At a high level, UMCG servers/workers provide the foundation for an M:N threading library, as described in the link above.
In addition, servers without workers can be used as "basic" UMCG tasks if wait/wake/context-switch are the only desired operations.
Joel Fernandes has also once mentioned that he had a use case for a wake+bring-the-wakee-to-the-current-CPU operation, so this is now also supported via UMCG_WF_CURRENT_CPU flag (patch 3).
Patch 1: add WF_CURRENT_CPU and tweak ttwu - same as last time Patch 2: add X86_64 helpers to work atomically with userspace values Patch 3: implement UMCG kernel-side
In this version of the patchset I used only userspace/TLS data, as suggested by Peter Zijlstra. With the exception of one issue (see patch 3 commit message) everything seems to be working great.
This TLS-only approach makes the userspace code a bit more involved, so I'm not posting libumcg/selftests with this patchset to focus on the kernel side only.
TODO:
- put atomic helpers from patch 2 into their proper place (unless keeping them in kernel/sched/umcg.h is OK)
- fix the wake server issue in preempt disable block (see patch 3)
- implement timeout handling
- imlement worker preemption
- more testing
- manpages, docs, and similar
- attach libumbc and selftest patches
Peter Oskolkov (3):
sched: add WF_CURRENT_CPU and externise ttwu
sched/umcg: RFC: add userspace atomic helpers
sched/umcg: RFC: implement UMCG syscalls
arch/x86/entry/syscalls/syscall_64.tbl | 2 + include/linux/sched.h | 6 + include/linux/syscalls.h | 4 + include/uapi/asm-generic/unistd.h | 8 +- include/uapi/linux/umcg.h | 246 +++++++++++++ init/Kconfig | 10 + kernel/exit.c | 7 + kernel/sched/Makefile | 1 + kernel/sched/core.c | 20 +- kernel/sched/fair.c | 4 + kernel/sched/sched.h | 15 +- kernel/sched/umcg.c | 481 +++++++++++++++++++++++++ kernel/sched/umcg.h | 271 ++++++++++++++ kernel/sys_ni.c | 4 + 14 files changed, 1068 insertions(+), 11 deletions(-) create mode 100644 include/uapi/linux/umcg.h create mode 100644 kernel/sched/umcg.c create mode 100644 kernel/sched/umcg.h
--
2.25.1
RFC PATCH 1/3 sched: add WF_CURRENT_CPU and externise ttwu
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
@@ -3680,8 +3680,7 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* 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
@@ -6836,6 +6836,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
@@ -2031,13 +2031,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 );
@@ -3037,6 +3038,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);
--
2.25.1
RFC PATCH 2/3 sched/umcg: RFC: add userspace atomic helpers
In reply to Peter OskolkovAdd helper functions to work atomically with userspace 32/64 bit values - there are some .*futex.* named helpers, but they are not exactly what is needed for UMCG; I haven't found what else I could use, so I rolled these.
At the moment only X86_64 is supported.
Note: the helpers should probably go into arch/ somewhere; I have them in kernel/sched/umcg.h temporarily for convenience. Please let me know where I should put them and how to name them.
--- kernel/sched/umcg.h | 264 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 264 insertions(+) create mode 100644 kernel/sched/umcg.h
kernel/sched/umcg.h new file +264 -0
@@ -0,0 +1,264 @@ +/* SPDX-License-Identifier: GPL-2.0+ WITH Linux-syscall-note */ +#ifndef _KERNEL_SCHED_UMCG_H +#define _KERNEL_SCHED_UMCG_H + +#ifdef CONFIG_UMCG +#ifdef CONFIG_X86_64 + +#include <linux/sched.h> +#include <linux/uaccess.h> +#include <linux/umcg.h> + +#include <asm/asm.h> +#include <linux/atomic.h> + +/* TODO: move atomic operations below into arch/ headers */ +static inline int umcg_atomic_cmpxchg_32 (u32 *uval,u32 __user *uaddr, +u32 oldval,u32 newval) +{ +int ret =0 ; + +if (!user_access_begin (uaddr,sizeof (u32))) +return -EFAULT ; + asmvolatile ("\n" +"1:\t" LOCK_PREFIX "cmpxchgl %4, %2\n" +"2:\n" +"\t.section .fixup, \"ax\"\n" +"3:\tmov %3, %0\n" +"\tjmp 2b\n" +"\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "+r" (ret), "=a" (oldval), "+m" (*uaddr) + : "i" (-EFAULT), "r" (newval), "1" (oldval) + : "memory" + ); +user_access_end (); + *uval = oldval; +return ret; +} + +static inline int umcg_atomic_cmpxchg_64 (u64 *uval,u64 __user *uaddr, +u64 oldval,u64 newval) +{ +int ret =0 ; + +if (!user_access_begin (uaddr,sizeof (u64))) +return -EFAULT ; + asmvolatile ("\n" +"1:\t" LOCK_PREFIX "cmpxchgq %4, %2\n" +"2:\n" +"\t.section .fixup, \"ax\"\n" +"3:\tmov %3, %0\n" +"\tjmp 2b\n" +"\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "+r" (ret), "=a" (oldval), "+m" (*uaddr) + : "i" (-EFAULT), "r" (newval), "1" (oldval) + : "memory" + ); +user_access_end (); + *uval = oldval; +return ret; +} + +static inline int fix_pagefault (unsigned long uaddr,bool write_fault) +{ +struct mm_struct *mm = current->mm; +int ret; + +mmap_read_lock (mm); + ret =fixup_user_fault (mm, uaddr, write_fault ?FAULT_FLAG_WRITE :0 , +NULL ); +mmap_read_unlock (mm); + +return ret <0 ? ret :0 ; +} + +static inline int umcg_get_user_32 (u32 __user *uaddr,u32 *val) +{ +while (true) { +int ret; +u32 out; + +pagefault_disable (); + ret =__get_user (out, uaddr); +pagefault_enable (); + +if (!ret) { + *val = out; +return 0 ; + } + +if (WARN_ONCE (ret != -EFAULT ,"Unexpected error" )) +return -EFAULT ; + + ret =fix_pagefault ((unsigned long )uaddr, false); +if (ret) +return -EFAULT ; + } +} + +/** +* umcg_cmpxchg_32_user - compare_exchange 32-bit values +* +* Return: +* 0 - OK +* -EFAULT: memory access error +* -EAGAIN: @expected did not match; consult @prev +*/ +static inline int umcg_cmpxchg_32_user (u32 __user *uaddr,u32 *prev,u32 val) +{ +while (true) { +int ret; +u32 expected = *prev; + +pagefault_disable (); + ret =umcg_atomic_cmpxchg_32 (prev, uaddr, expected, val); +pagefault_enable (); + +if (!ret) +return *prev == expected ?0 : -EAGAIN ; + +if (WARN_ONCE (ret != -EFAULT ,"Unexpected error" )) +return -EFAULT ; + + ret =fix_pagefault ((unsigned long )uaddr, true); +if (ret) +return -EFAULT ; + } +} + +/** +* umcg_cmpxchg_64_user - compare_exchange 64-bit values +* +* Return: +* 0 - OK +* -EFAULT: memory access error +* -EAGAIN: @expected did not match; consult @prev +*/ +static inline int umcg_cmpxchg_64_user (u64 __user *uaddr,u64 *prev,u64 val) +{ +while (true) { +int ret; +u64 expected = *prev; + +pagefault_disable (); + ret =umcg_atomic_cmpxchg_64 (prev, uaddr, expected, val); +pagefault_enable (); + +if (!ret) +return *prev == expected ?0 : -EAGAIN ; + +if (WARN_ONCE (ret != -EFAULT ,"Unexpected error" )) +return -EFAULT ; + + ret =fix_pagefault ((unsigned long )uaddr, true); +if (ret) +return -EFAULT ; + } +} + +/** +* atomic_stack_push_user - push a node onto the stack +* @head - a pointer to the head of the stack; +* @node - a pointer to the node to push. +* +* Push a node onto a single-linked list (stack). Atomicity/correctness +* is guaranteed by locking the head via settings its first bit (assuming +* the pointer is aligned). +* +* Return: 0 on success, -EFAULT on error. +*/ +static inline int atomic_stack_push_user (u64 __user *head,u64 __user *node) +{ +while (true) { +int ret; +u64 first; + +smp_mb ();/* Make the read below clean. */ +if (get_user (first, head)) +return -EFAULT ; + +if (first &1UL ) { +cpu_relax (); +continue ;/* first is being deleted. */ + } + +if (put_user (first, node)) +return -EFAULT ; +smp_mb ();/* Make the write above visible. */ + + ret =umcg_cmpxchg_64_user (head, &first, (u64 )node); +if (!ret) +return 0 ; + +if (ret == -EAGAIN ) { +cpu_relax (); +continue ; + } + +if (WARN_ONCE (ret != -EFAULT ,"unexpected umcg_cmpxchg result" )) +return -EFAULT ; + +return -EFAULT ; + } +} + +/** +* atomic_stack_pop_user - pop a node from the stack +* @head - a pointer to the head of the stack; +* @value - a pointer to where store the popped value. +* +* Pop a node from a single-linked list (stack). Atomicity/correctness +* is guaranteed by locking the head via settings its first bit (assuming +* the pointer is aligned). +* +* Note: on success, @value should be cast to (u64 __user *) if not zero. +* +* Return: 0 on success, -EFAULT on error. +*/ +static inline int atomic_stack_pop_user (u64 __user *head,u64 *value) +{ +while (true) { +int ret; +u64 next, first; + +smp_mb ();/* Make the read below clean. */ +if (get_user (first, head)) +return -EFAULT ; + +if (!first) { + *value =0UL ; +return 0 ; + } + +if (first &1UL ) { +cpu_relax (); +continue ;/* first is being deleted. */ + } + + ret =umcg_cmpxchg_64_user (head, &first, first |1UL ); +if (ret == -EAGAIN ) { +cpu_relax (); +continue ; + } + +if (ret) +return -EFAULT ; + +if (get_user (next, (u64 __user *)first)) +return -EFAULT ; + + first |=1UL ; + + ret =umcg_cmpxchg_64_user (head, &first, next); +if (ret) +return -EFAULT ; + + *value = first & ~1UL ; +return 0 ; + } +} +#endif /* CONFIG_X86_64 */ +#endif /* CONFIG_UMCG */ +#endif /* _KERNEL_SCHED_UMCG_H */
--
2.25.1
Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
Quoted 10 lines · Peter Oskolkov
Add helper functions to work atomically with userspace 32/64 bit values - there are some .*futex.* named helpers, but they are not exactly what is needed for UMCG; I haven't found what else I could use, so I rolled these.
At the moment only
X86_64is supported.Note: the helpers should probably go into
arch/somewhere; I have them inkernel/sched/umcg.htemporarily for convenience. Please let me know where I should put them and how to name them.
Instead of open-coding spinlocks in userspace memory like this (which some of the reviewers will probably dislike because it will have issues around priority inversion and such), I wonder whether you could use an actual futex as your underlying locking primitive?
The most straightforward way to do that would probably be to make the head structure in userspace look roughly like this?
struct umcg_head {
u64 head_ptr;
u32 lock;
};
and then from kernel code, you could build a fastpath that directly calls cmpxchg_futex_value_locked() and build a fallback based on do_futex(), or something like that.
There is precedent for using futex from inside the kernel to communicate with userspace: See mm_release(), which calls do_futex() with FUTEX_WAKE for the clear_child_tid feature.
Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
Quoted 26 lines · Jann Horn
Quoted 10 lines · Peter Oskolkov
Add helper functions to work atomically with userspace 32/64 bit values - there are some .*futex.* named helpers, but they are not exactly what is needed for UMCG; I haven't found what else I could use, so I rolled these.
At the moment only
X86_64is supported.Note: the helpers should probably go into
arch/somewhere; I have them inkernel/sched/umcg.htemporarily for convenience. Please let me know where I should put them and how to name them.Instead of open-coding spinlocks in userspace memory like this (which some of the reviewers will probably dislike because it will have issues around priority inversion and such), I wonder whether you could use an actual futex as your underlying locking primitive?
The most straightforward way to do that would probably be to make the head structure in userspace look roughly like this?
struct
umcg_head{
u64head_ptr;
u32 lock;
};
Quoted 7 lines
and then from kernel code, you could build a fastpath that directly calls
cmpxchg_futex_value_locked()and build a fallback based ondo_futex(), or something like that.There is precedent for using futex from inside the kernel to communicate with userspace: See
mm_release(), which callsdo_futex()withFUTEX_WAKEfor theclear_child_tidfeature.
Hi Jann,
Thanks for the note!
The approach you suggest will require locking every operation, I believe, while in the scheme I have pushes/inserts are lock-free if there are no concurrent pops/deletes. And the kernel does mostly pushes (waking workers, and there can be a lot of workers), while pops are rare (idle servers, and there is no reason for the number of servers to exceed the number of CPUs substantially, and if there is contention here, it will be very short-lived), while the userspace will pop the entire stack of idle workers in one op (so a short lock as well). So I think my approach scales better. And priority inversion should not matter here, because this is for userspace scheduling, and so the userspace scheduler should worry about it, not the kernel.
Am I missing something?
Thanks,
Peter
Peter Zijlstra
maintainerRe: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
In reply to Peter OskolkovQuoted 94 lines · Peter Oskolkov
kernel/sched/umcg.h new file +92
-0+static inline int umcg_atomic_cmpxchg_64 (u64 *uval,u64 __user *uaddr, +u64 oldval,u64 newval) +{ +int ret =0 ; + +if (!user_access_begin (uaddr,sizeof (u64))) +return -EFAULT ; + asmvolatile ("\n" +"1:\t" LOCK_PREFIX "cmpxchgq %4, %2\n" +"2:\n" +"\t.section .fixup, \"ax\"\n" +"3:\tmov %3, %0\n" +"\tjmp 2b\n" +"\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "+r" (ret), "=a" (oldval), "+m" (*uaddr) + : "i" (-EFAULT), "r" (newval), "1" (oldval) + : "memory" + ); +user_access_end (); + *uval = oldval; +return ret; +} +static inline int fix_pagefault (unsigned long uaddr,bool write_fault) +{ +struct mm_struct *mm = current->mm; +int ret; + +mmap_read_lock (mm); + ret =fixup_user_fault (mm, uaddr, write_fault ?FAULT_FLAG_WRITE :0 , +NULL ); +mmap_read_unlock (mm); + +return ret <0 ? ret :0 ; +} +static inline int umcg_cmpxchg_64_user (u64 __user *uaddr,u64 *prev,u64 val) +{ +while (true) { +int ret; +u64 expected = *prev; + +pagefault_disable (); + ret =umcg_atomic_cmpxchg_64 (prev, uaddr, expected, val); +pagefault_enable (); + +if (!ret) +return *prev == expected ?0 : -EAGAIN ; + +if (WARN_ONCE (ret != -EFAULT ,"Unexpected error" )) +return -EFAULT ; + + ret =fix_pagefault ((unsigned long )uaddr, true); +if (ret) +return -EFAULT ; + } +} + +/** +* atomic_stack_push_user - push a node onto the stack +* @head - a pointer to the head of the stack; +* @node - a pointer to the node to push. +* +* Push a node onto a single-linked list (stack). Atomicity/correctness +* is guaranteed by locking the head via settings its first bit (assuming +* the pointer is aligned). +* +* Return: 0 on success, -EFAULT on error. +*/ +static inline int atomic_stack_push_user (u64 __user *head,u64 __user *node) +{ +while (true) { +int ret; +u64 first; + +smp_mb ();/* Make the read below clean. */ +if (get_user (first, head)) +return -EFAULT ; + +if (first &1UL ) { +cpu_relax (); +continue ;/* first is being deleted. */ + } + +if (put_user (first, node)) +return -EFAULT ; +smp_mb ();/* Make the write above visible. */ + + ret =umcg_cmpxchg_64_user (head, &first, (u64 )node); +if (!ret) +return 0 ; + +if (ret == -EAGAIN ) {
kernel/sched/umcg.h line 205
Quoted 10 lines
kernel/sched/umcg.h new file +10
-0+cpu_relax (); +continue ; + } + +if (WARN_ONCE (ret != -EFAULT ,"unexpected umcg_cmpxchg result" )) +return -EFAULT ; + +return -EFAULT ; + } +}
This is horrible... Jann is absolutely right, you do not, *ever* do userspace spinlocks. What's wrong with the trivial lockless single linked list approach?
On top of that, you really want to avoid all that endless stac/clac nonsense and only have that once, at the outer edges of things.
Something like the *completely* untested below (except it needs lots of extra gunk to support compilers without asm-goto-output, and more widths and ...
#define __try_cmpxchg_user_size(ptr, oldp, new, size, label) \
({ \
_Bool __success; \
__chk_user_ptr(ptr); \
__typeof__(ptr) _old = (__typeof__(ptr))(oldp); \
__typeof__(*(ptr)) __old = *_old; \
__typeof__(*(ptr)) __new = (new); \
switch (size) { \
case 8: \
volatile u64 *__ptr = (volatile u64 *)(ptr); \
asm_volatile_goto("1: " LOCK_PREFIX "cmpxchgq %[new], %[ptr]" \
CC_SET(z) \
_ASM_EXTABLE_UA(1b, %l[label]) \
: CC_OUT(x) (__success), \
[ptr] "+m" (*__ptr), \
[old] "+a" (__old), \
: [new] "r" (__new) \
: "memory" \
: label); \
break; \
} \
if (unlikely(!success)) \
*_old = __old; \
__success; \
})#define unsafe_try_cmpxchg_user(ptr, oldp, new, label) \ __try_cmpxchg_user_size((ptr), (oldp), (new), sizeof(*(ptr)), label);
int user_llist_add(u64 __user *new, u64 __user *head)
{
u64 first;
int ret;
if (unlikely(!access_ok(new, sizeof(*new)) ||
!access_ok(head, sizeof(*head))))
return -EFAULT;again:
__uaccess_begin_nospec();
unsafe_get_user(first, head, Efault_head);
do {
unsafe_put_user(first, new, Efault_new);
} while (!unsafe_try_cmpxchg_user(head, &first, new, Efault_head));
user_access_end();
return 0;Efault_new:
user_access_end(); ret = fixup_fault(new); if (ret < 0) return ret; goto again;
Efault_head:
user_access_end(); ret = fixup_fault(head); if (ret < 0) return ret; goto again; }
Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
Quoted 104 lines · Peter Zijlstra
Quoted 101 lines · Peter Oskolkov
kernel/sched/umcg.h new file +99
-0+static inline int umcg_atomic_cmpxchg_64 (u64 *uval,u64 __user *uaddr, +u64 oldval,u64 newval) +{ +int ret =0 ; + +if (!user_access_begin (uaddr,sizeof (u64))) +return -EFAULT ; + asmvolatile ("\n" +"1:\t" LOCK_PREFIX "cmpxchgq %4, %2\n" +"2:\n" +"\t.section .fixup, \"ax\"\n" +"3:\tmov %3, %0\n" +"\tjmp 2b\n" +"\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "+r" (ret), "=a" (oldval), "+m" (*uaddr) + : "i" (-EFAULT), "r" (newval), "1" (oldval) + : "memory" + ); +user_access_end (); + *uval = oldval; +return ret; +} +static inline int fix_pagefault (unsigned long uaddr,bool write_fault) +{ +struct mm_struct *mm = current->mm; +int ret; + +mmap_read_lock (mm); + ret =fixup_user_fault (mm, uaddr, write_fault ?FAULT_FLAG_WRITE :0 , +NULL ); +mmap_read_unlock (mm); + +return ret <0 ? ret :0 ; +} +static inline int umcg_cmpxchg_64_user (u64 __user *uaddr,u64 *prev,u64 val) +{ +while (true) { +int ret; +u64 expected = *prev; + +pagefault_disable (); + ret =umcg_atomic_cmpxchg_64 (prev, uaddr, expected, val); +pagefault_enable (); + +if (!ret) +return *prev == expected ?0 : -EAGAIN ; + +if (WARN_ONCE (ret != -EFAULT ,"Unexpected error" )) +return -EFAULT ; + + ret =fix_pagefault ((unsigned long )uaddr, true); +if (ret) +return -EFAULT ; + } +} + +/** +* atomic_stack_push_user - push a node onto the stack +* @head - a pointer to the head of the stack; +* @node - a pointer to the node to push. +* +* Push a node onto a single-linked list (stack). Atomicity/correctness +* is guaranteed by locking the head via settings its first bit (assuming +* the pointer is aligned). +* +* Return: 0 on success, -EFAULT on error. +*/ +static inline int atomic_stack_push_user (u64 __user *head,u64 __user *node) +{ +while (true) { +int ret; +u64 first; + +smp_mb ();/* Make the read below clean. */ +if (get_user (first, head)) +return -EFAULT ; + +if (first &1UL ) { +cpu_relax (); +continue ;/* first is being deleted. */ + } + +if (put_user (first, node)) +return -EFAULT ; +smp_mb ();/* Make the write above visible. */ + + ret =umcg_cmpxchg_64_user (head, &first, (u64 )node); +if (!ret) +return 0 ; + +if (ret == -EAGAIN ) { +cpu_relax (); +continue ; + } + +if (WARN_ONCE (ret != -EFAULT ,"unexpected umcg_cmpxchg result" )) +return -EFAULT ; +
Quoted 8 lines
kernel/sched/umcg.h line 62
Quoted 3 lines
kernel/sched/umcg.h new file +3
-0+return -EFAULT ; + } +}This is horrible... Jann is absolutely right, you do not, *ever* do userspace spinlocks. What's wrong with the trivial lockless single linked list approach?.
I'm not sure how to get around the ABA problem with a lockless single linked list: https://en.wikipedia.org/wiki/ABA_problem
Our semantics can probably be relied on to prevent ABA from happening with idle workers (popped/removed by the userspace), but idle servers can trivially have it:
(initial state): head => Server A => Server B => NULL
task1 :
- read head (get A), read A (get B), {/* delayed */}
tasks 2-3-4:
- pop A, pop B, push A
task 1:
- cmp_xchg(head, A /* old */, B /* new */) - succeeds, now B is in the list erroneously
Quoted 7 lines
On top of that, you really want to avoid all that endless stac/clac nonsense and only have that once, at the outer edges of things.
Something like the *completely* untested below (except it needs lots of extra gunk to support compilers without asm-goto-output, and more widths and ...
I'll try the approach you suggest below once it is clear how to deal with the ABA issue (and the wake server issue raised in patch 3).
Quoted 70 lines
#define __try_cmpxchg_user_size(ptr, oldp, new, size, label) \ ({ \ _Bool __success; \ __chk_user_ptr(ptr); \ __typeof__(ptr) _old = (__typeof__(ptr))(oldp); \ __typeof__(*(ptr)) __old = *_old; \ __typeof__(*(ptr)) __new = (new); \ switch (size) { \ case 8: \ volatile u64 *__ptr = (volatile u64 *)(ptr); \ asm_volatile_goto("1: " LOCK_PREFIX "cmpxchgq %[new], %[ptr]" \ CC_SET(z) \ _ASM_EXTABLE_UA(1b, %l[label]) \ : CC_OUT(x) (__success), \ [ptr] "+m" (*__ptr), \ [old] "+a" (__old), \ : [new] "r" (__new) \ : "memory" \ : label); \ break; \ } \ if (unlikely(!success)) \ *_old = __old; \ __success; \ })#define unsafe_try_cmpxchg_user(ptr, oldp, new, label) \ __try_cmpxchg_user_size((ptr), (oldp), (new), sizeof(*(ptr)), label);int
user_llist_add(u64 __user *new, u64 __user *head){ u64 first; int ret; if (unlikely(!access_ok(new, sizeof(*new)) || !access_ok(head, sizeof(*head)))) return -EFAULT;again:
__uaccess_begin_nospec(); unsafe_get_user(first, head, Efault_head); do { unsafe_put_user(first, new, Efault_new); } while (!unsafe_try_cmpxchg_user(head, &first, new, Efault_head)); user_access_end(); return 0;
Efault_new:user_access_end(); ret = fixup_fault(new); if (ret < 0) return ret; goto again;
Efault_head:user_access_end(); ret = fixup_fault(head); if (ret < 0) return ret; goto again; }
Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
Quoted 3 lines · Peter Oskolkov
Quoted 1 line · Peter Zijlstra
[...]
Quoted 15 lines
Quoted 2 lines
What's wrong with the trivial lockless single
linked list approach?.I'm not sure how to get around the ABA problem with a lockless single linked list: https://en.wikipedia.org/wiki/ABA_problem
Our semantics can probably be relied on to prevent ABA from happening with idle workers (popped/removed by the userspace), but idle servers can trivially have it:
(initial state): head => Server A => Server B => NULL
task1 :
- read head (get A), read A (get B), {/* delayed */}
Quoted 6 lines
tasks 2-3-4:
- pop A, pop B, push Atask 1:
-cmp_xchg(head, A /* old */, B /* new */)- succeeds, now B is in the list erroneously
I think the kernel can just mark "popped" servers as such (by setting the lowest bit of its "next" pointer to one) without actually removing them from the list, and letting the userspace do the cleanup/GC. With hard-limiting the max length of idle servers at 2*NUM_CPUs or similar, this may work out OK. I'll work on this approach. Please have a look at patch 3. :)
Quoted 12 lines
Quoted 8 lines
On top of that, you really want to avoid all that endless stac/clac nonsense and only have that once, at the outer edges of things.
Something like the *completely* untested below (except it needs lots of extra gunk to support compilers without asm-goto-output, and more widths and ...
I'll try the approach you suggest below once it is clear how to deal with the ABA issue (and the wake server issue raised in patch 3).
[...]
Peter Zijlstra
maintainerRe: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
In reply to Peter OskolkovQuoted 8 lines · Peter Oskolkov
Quoted 3 lines · Peter Zijlstra
This is horrible... Jann is absolutely right, you do not, *ever* do userspace spinlocks. What's wrong with the trivial lockless single linked list approach?.
I'm not sure how to get around the ABA problem with a lockless single linked list: https://en.wikipedia.org/wiki/ABA_problem
I'm familiar with the problem. I'm just not sure how we got there.
Last time we had umcg_blocked_ptr / umcg_runnable_ptr which were kernel append, user clear single linked lists used for RUNNING->BLOCKED and BLOCKED->RUNNABLE notifications.
But those seem gone, instead we now have idle_servers_ptr / idle_workers_ptr. I've not yet fully digested things, but they seem to implement some 'SMP' policy. Can we please forget about the whole SMP thing for now and focus on getting the basics sorted?
So if we implement the bits outlined here:
https://lore.kernel.org/linux-api/[email protected]/
https://lore.kernel.org/linux-api/[email protected]/
Then what is mising for full N:1 (aka UP) ?
One thing I've considered is that we might want to add u64 timestamps for the various state transitions, such that userspace can compute elapsed time which is useful for more dynamic scheduling policies.
Another is preemption; I'm thinking we can drive that with signals, but that does give complications -- signals are super gross API wise. Another method would be much preferred I think. We could add another syscall which allows userspace (from eg. SIGALRM/SIGPROF/SIGVTALRM) to force a worker to do a RUNNING->RUNNABLE transition and schedule back to the server.
Then lets consider N:M (aka SMP). The basics of SMP is sharing work between servers. For a large part userspace can already do that by keeping a shared ready queue. Servers that go idle pick up a work, re-assign it to themselves and go.
The pain-point seems to be *efficient* BLOCKED->RUNNABLE notifications across servers. Inefficient options include the userspace servers iterating all known other servers and trying to steal their umcg_runnable_ptr and processing it. This is 'difficult' in that there is no natural wakeup and hence letting a server do IDLE will increase latency and destroy work concervance.
The alternative seems to be to let the kernel do the server iteration, looking for a RUNNING one and using that umcg_runnable_ptr field and kicking it. For that we can set up an immutable linked list between struct umcg_task's, a circular single linked list that the kernel iterates until it's back where it started. Then there is no dymaic state.
Hmm?
Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers
Quoted 13 lines · Peter Zijlstra
Quoted 8 lines · Peter Oskolkov
Quoted 3 lines · Peter Zijlstra
This is horrible... Jann is absolutely right, you do not, *ever* do userspace spinlocks. What's wrong with the trivial lockless single linked list approach?.
I'm not sure how to get around the ABA problem with a lockless single linked list: https://en.wikipedia.org/wiki/ABA_problem
I'm familiar with the problem. I'm just not sure how we got there.
Quoted 8 lines
Last time we had
umcg_blocked_ptr/umcg_runnable_ptrwhich were kernel append, user clear single linked lists used forRUNNING->BLOCKEDandBLOCKED->RUNNABLEnotifications.But those seem gone, instead we now have
idle_servers_ptr/idle_workers_ptr. I've not yet fully digested things, but they seem to implement some 'SMP' policy. Can we please forget about the whole SMP thing for now and focus on getting the basics sorted?
Hmm... yes, I was always working on the M:N model, i.e. multiple servers, i.e. SMP. Apologies if this was not clear.
I think I'm close to having "SMP basics sorted" - I believe it will take me longer now to go back to "UP" and then extend this to SMP. And the result can probably be not as clean as having SMP there from the beginning. Just give me another couple of days, please!
Quoted 11 lines
So if we implement the bits outlined here:
https://lore.kernel.org/linux-api/[email protected]/
https://lore.kernel.org/linux-api/[email protected]/Then what is mising for full N:1 (aka UP) ?
One thing I've considered is that we might want to add u64 timestamps for the various state transitions, such that userspace can compute elapsed time which is useful for more dynamic scheduling policies.
Tagging state transitions with unique-per-task tags (counters) will simplify a lot of things in the userspace, as these can be used to sort out block/wakeup/swap races easily. If these tags have timestamp semantics (e.g. nanos), even better - as you suggest, scheduling can be tweaked, tracing/instrumentation will naturally use these, etc.
Synchronizing state+timestamp updates will be a challenge, unless we share a 64-bit field for state + timestamp: 6 bytes for the timestamp and two bytes for the state (I think one byte for the state is too tight, although it will be enough initially). 6 bytes of nanos will cycle over in a couple of days (if my math is right), so should not be an issue for uniqueness; and I guess the userspace can always easily restore the higher two bytes of the timestamp if needed.
So... should I convert u32 state into u64 state+timestamp field?
Quoted 7 lines
Another is preemption; I'm thinking we can drive that with signals, but that does give complications -- signals are super gross API wise. Another method would be much preferred I think. We could add another syscall which allows userspace (from eg. SIGALRM/SIGPROF/SIGVTALRM) to force a worker to do a
RUNNING->RUNNABLEtransition and schedule back to the server.
I haven't looked into preemption yet, so I'll try any approach you suggest (after the "basics" are sorted out).
Quoted 12 lines
Then lets consider N:M (aka SMP). The basics of SMP is sharing work between servers. For a large part userspace can already do that by keeping a shared ready queue. Servers that go idle pick up a work, re-assign it to themselves and go.
The pain-point seems to be *efficient*
BLOCKED->RUNNABLEnotifications across servers. Inefficient options include the userspace servers iterating all known other servers and trying to steal theirumcg_runnable_ptrand processing it. This is 'difficult' in that there is no natural wakeup and hence letting a server do IDLE will increase latency and destroy work concervance.
Quoted 6 lines
The alternative seems to be to let the kernel do the server iteration, looking for a RUNNING one and using that
umcg_runnable_ptrfield and kicking it. For that we can set up an immutable linked list between struct umcg_task's, a circular single linked list that the kernel iterates until it's back where it started. Then there is no dymaic state.
In full utilization scenarios, which are typical in our use cases (custom scheduling is not that useful if there are idle CPUs/servers), the kernel will quite often find no idle servers, so having a dynamic list/stack of idle servers is more efficient. I'll post what I have in mind (the kernel marks servers as deleted, the userspace does cleanup/gc) soon.
RFC PATCH 3/3 sched/umcg: RFC: implement UMCG syscalls
In reply to Peter OskolkovDefine struct umcg_task and sys_umcg_ctl/sys_umcg_wait syscalls.
This is another attempt at implementing UMCG, based on discussion in https://lore.kernel.org/patchwork/cover/1433967/
Most of the "why" is covered here (some details are obsolete):
https://lore.kernel.org/patchwork/cover/1433967/#1632328
I'll update the commit message with more "why" when the general approach is ACKed at a high level.
The "how": in this patch I used the approach suggested by peterz@ in the discussion linked above; specifically, only a single
struct umcg_task __user *umcg_task
pointer is added to struct task_struct.
I tried to make inline doc-comments to be more clear and detailed this time - hopefuly they answer the "how" better now.
Pretty much everything works, with one issue: when a worker blocks, we need to wake its server in umcg_wq_worker_sleeping called from sched_submit_work within preempt_disable block. As the server_tid is set by the userspace, it can point to a running/spinning task, and so wake_server will hang waiting for ttwu() to succeed. I do not think this is appropriate, but I am not sure at the moment how to resolve this. Any sugestions?
Other than the issue above, I need to implement timeout handling and do more testing before this is ready for a fully detailed technical review - at the moment this is just an RFC.
And also worker preemption - haven't looked at it at all yet.
--- arch/x86/entry/syscalls/syscall_64.tbl | 2 + include/linux/sched.h | 6 + include/linux/syscalls.h | 4 + include/uapi/asm-generic/unistd.h | 8 +- include/uapi/linux/umcg.h | 246 +++++++++++++ init/Kconfig | 10 + kernel/exit.c | 7 + kernel/sched/Makefile | 1 + kernel/sched/core.c | 17 +- kernel/sched/umcg.c | 481 +++++++++++++++++++++++++ kernel/sched/umcg.h | 7 + kernel/sys_ni.c | 4 + 12 files changed, 790 insertions(+), 3 deletions(-) create mode 100644 include/uapi/linux/umcg.h create mode 100644 kernel/sched/umcg.c
arch/x86/entry/syscalls/syscall_64.tbl +2 -0
@@ -368,6 +368,8 @@ 444 common landlock_create_ruleset sys_landlock_create_ruleset 445 common landlock_add_rule sys_landlock_add_rule 446 common landlock_restrict_self sys_landlock_restrict_self +447 common umcg_ctl sys_umcg_ctl +448 common umcg_wait sys_umcg_wait # # Due to a historical design error, certain syscalls are numbered differently
include/linux/sched.h +6 -0
@@ -66,6 +66,7 @@ struct sighand_struct;struct signal_struct ;struct task_delay_info ;struct task_group ; +struct umcg_task ;/* * Task state bitmask. NOTE! These bits are also
@@ -1223,6 +1224,10 @@ struct task_struct {unsigned long rseq_event_mask;#endif +#ifdef CONFIG_UMCG +struct umcg_task __user *umcg_task; +#endif +struct tlbflush_unmap_batch tlb_ubc;union {
@@ -1599,6 +1604,7 @@ extern struct pid *cad_pid;#define PF_KTHREAD 0x00200000/* I am a kernel thread */ #define PF_RANDOMIZE 0x00400000/* Randomize virtual address space */ #define PF_SWAPWRITE 0x00800000/* Allowed to write to swap */ +#define PF_UMCG_WORKER 0x01000000/* UMCG worker */ #define PF_NO_SETAFFINITY 0x04000000/* Userland is not allowed to meddle with cpus_mask */ #define PF_MCE_EARLY 0x08000000/* Early kill for mce process policy */ #define PF_MEMALLOC_PIN 0x10000000/* Allocation context constrained to zones which allow long term pinning. */
include/linux/syscalls.h +4 -0
@@ -71,6 +71,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>
@@ -1050,6 +1051,9 @@ asmlinkage long sys_landlock_create_ruleset(const struct landlock_ruleset_attr _asmlinkage long sys_landlock_add_rule (int ruleset_fd,enum landlock_rule_type rule_type,const void __user *rule_attr,__u32 flags);asmlinkage long sys_landlock_restrict_self (int ruleset_fd,__u32 flags); +asmlinkage long sys_umcg_ctl (u32 flags,struct umcg_task __user *self); +asmlinkage long sys_umcg_wait (u32 flags,u64 abs_timeout); +/* * Architecture-specific system calls
include/uapi/asm-generic/unistd.h +7 -1
@@ -873,8 +873,14 @@ __SYSCALL(__NR_landlock_add_rule, sys_landlock_add_rule)#define __NR_landlock_restrict_self 446 __SYSCALL(__NR_landlock_restrict_self, sys_landlock_restrict_self) +#define __NR_umcg_ctl 447 +__SYSCALL(__NR_umcg_ctl, sys_umcg_ctl) +#define __NR_umcg_wait 448 +__SYSCALL(__NR_umcg_wait, sys_umcg_wait) + +#undef __NR_syscalls -#define __NR_syscalls 447 +#define __NR_syscalls 449/* * 32 bit systems traditionally used different
include/uapi/linux/umcg.h new file +246 -0
246 lines not on this page · raw message
init/Kconfig +10 -0
@@ -1662,6 +1662,16 @@ config MEMBARRIER If unsure, say Y. +config UMCG + bool "Enable User Managed Concurrency Groups API" + depends on X86_64 + 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/exit.c +7 -0
@@ -744,6 +744,13 @@ void __noreturn do_exit(long code)if (unlikely (!tsk->pid))panic ("Attempted to kill the idle task!" ); +#ifdef CONFIG_UMCG +if (unlikely (tsk->flags &PF_UMCG_WORKER )) + tsk->flags &= ~PF_UMCG_WORKER ; + + tsk->umcg_task =NULL ; +#endif +/* * 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
kernel/sched/Makefile +1 -0
@@ -37,3 +37,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 +15 -2
@@ -26,6 +26,7 @@#include "pelt.h" #include "smp.h" +#include "umcg.h" /* * Export tracepoints that act as a bare tracehook (ie: have no trace event
@@ -3961,6 +3962,10 @@ 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 +#ifdef CONFIG_UMCG + p->umcg_task =NULL ; + p->flags &= ~PF_UMCG_WORKER ; +#endif }DEFINE_STATIC_KEY_FALSE (sched_numa_balancing);
@@ -5975,10 +5980,14 @@ static inline void sched_submit_work(struct task_struct *tsk)* in the possible wakeup of a kworker and because wq_worker_sleeping() * requires it. */ -if (task_flags & (PF_WQ_WORKER |PF_IO_WORKER )) { +if (task_flags & (PF_WQ_WORKER |PF_IO_WORKER |PF_UMCG_WORKER )) {preempt_disable ();if (task_flags &PF_WQ_WORKER )wq_worker_sleeping (tsk); +#ifdef CONFIG_UMCG + else if (task_flags & PF_UMCG_WORKER) + umcg_wq_worker_sleeping(tsk); +#endif elseio_wq_worker_sleeping (tsk );preempt_enable_no_resched ();
@@ -5997,9 +6006,13 @@ 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); +#ifdef CONFIG_UMCG + else if (tsk->flags & PF_UMCG_WORKER) + umcg_wq_worker_running(tsk); +#endif elseio_wq_worker_running (tsk ); }
kernel/sched/umcg.c new file +481 -0
481 lines not on this page · raw message
kernel/sched/umcg.h +7 -0
@@ -12,6 +12,13 @@#include <asm/asm.h> #include <linux/atomic.h> +/* +* umcg_wq_worker_[sleeping|running] are called in core.c by +* sched_submit_work() and sched_update_worker(). +*/ +void umcg_wq_worker_sleeping (struct task_struct *tsk); +void umcg_wq_worker_running (struct task_struct *tsk); +/* TODO: move atomic operations below into arch/ headers */ static inline int umcg_atomic_cmpxchg_32 (u32 *uval,u32 __user *uaddr,u32 oldval,u32 newval)
kernel/sys_ni.c +4 -0
@@ -272,6 +272,10 @@ 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); +/* arch/example/kernel/sys_example.c */ /* mm/fadvise.c */
--
2.25.1
Re: [RFC PATCH 3/3 v0.2] sched/umcg: RFC: implement UMCG syscalls
On Thu, Jul 8, 2021 at 12:46 PM Peter Oskolkov <[email protected]> wrote:
[...]
Quoted 7 lines
Pretty much everything works, with one issue: when a worker blocks, we need to wake its server in
umcg_wq_worker_sleepingcalled fromsched_submit_workwithinpreempt_disableblock. As theserver_tidis set by the userspace, it can point to a running/spinning task, and sowake_serverwill hang waiting forttwu()to succeed. I do not think this is appropriate, but I am not sure at the moment how to resolve this. Any sugestions?
[...]
I think I can solve this by carefully ordering state changes (both umcg state and task state) and maybe sending a signal to the wakee if not enough. I'll try this approach in v0.3.
Re: [RFC PATCH 3/3 v0.2] sched/umcg: RFC: implement UMCG syscalls
In reply to Peter OskolkovQuoted 1 line
Let's move the discussion to the new thread.
I'm happy to start a new thread. I'm re-responding to my last post because many of my questions are still unanswered.
Quoted 7 lines
+ * State transitions:
+ *
+ * RUNNING => IDLE: the current RUNNING task becomes IDLE by calling
+ *sys_umcg_wait();[...]
include/uapi/linux/umcg.h line 244
Quoted 10 lines
include/uapi/linux/umcg.h new file +10
-0+/** +* enum umcg_wait_flag - flags to pass to sys_umcg_wait +* @UMCG_WAIT_WAKE_ONLY: wake @self->next_tid, don't put @self to sleep; +* @UMCG_WF_CURRENT_CPU: wake @self->next_tid on the current CPU +* (use WF_CURRENT_CPU); @UMCG_WAIT_WAKE_ONLY must be set. +*/ +enum umcg_wait_flag { + UMCG_WAIT_WAKE_ONLY = 1, + UMCG_WF_CURRENT_CPU = 2, +};
What is the purpose of using sys_umcg_wait without next_tid or with UMCG_WAIT_WAKE_ONLY? It looks like Java's park/unpark semantics to me, that is worker threads can use this for synchronization and mutual exclusion. In this case, how do these compare to using FUTEX_WAIT/FUTEX_WAKE?
Quoted 17 lines
include/uapi/linux/umcg.h new file +15
-0+struct umcg_task { + /** + * @server_tid: the TID of the server UMCG task that should be + * woken when this WORKER becomes BLOCKED. Can be zero. + * + * If this is a UMCG server, @server_tid should + * contain the TID of @self - it will be used to find + * the task_struct to wake when pulled from + * @idle_servers. + * + * Read-only for the kernel, read/write for the userspace. + */ + uint32_t server_tid; /* r */ + /** + * @idle_servers_ptr: a single-linked list pointing to the list
include/uapi/linux/umcg.h line 219
Quoted 10 lines
include/uapi/linux/umcg.h new file +9
-0+* of idle servers. Can be NULL. +* +* Readable/writable by both the kernel and the userspace: the +* userspace adds items to the list, the kernel removes them. +* +* TODO: describe how the list works. +*/ + uint64_t idle_servers_ptr; /* r/w */ +} __attribute__((packed, aligned(8 * sizeof(__u64))));
From the comments and by elimination, I'm guessing that idle_servers_ptr is somehow used by servers to block until some worker threads become idle. However, I do not understand how the userspace is expected to use it. I also do not understand if these link fields form a stack or a queue and where is the head.
Quoted 8 lines
+/**
+ *sys_umcg_ctl: (un)register a task as a UMCG task.
+ * @flags: ORed values from enumumcg_ctl_flag; see below;
+ * @self: a pointer to structumcg_taskthat describes this
+ * task and governs the behavior ofsys_umcg_waitif
+ * registering; must be NULL if unregistering.
+ *
+ * @flags &UMCG_CTL_REGISTER: register a UMCG task:
Quoted 8 lines
+ * UMCG workers:
+ * -self->statemust beUMCG_TASK_IDLE
+ * - @flags &UMCG_CTL_WORKER
+ *
+ * If the conditions above are met,sys_umcg_ctl()immediately returns
+ * if the registered task is a RUNNING server or basic task; an IDLE
+ * worker will be added toidle_workers_ptr, and the worker put to
+ * sleep; an idle server fromidle_servers_ptrwill be woken, if any.
This approach to creating UMCG workers concerns me a little. My understanding is that in general, the number of servers controls the amount of parallelism in the program. But in the case of creating new UMCG workers, the new threads only respect the M:N threading model after sys_umcg_ctl has blocked. What does this mean for applications that create thousands of short lived tasks? Are users expcted to create pools of reusable UMCG workers?
I would suggest adding at least one uint64_t field to the struct umcg_task that is left as-is by the kernel. This allows implementers of user-space schedulers to add scheduler specific data structures to the threads without needing some kind of table on the side.
Re: [RFC PATCH 3/3 v0.2] sched/umcg: RFC: implement UMCG syscalls
Quoted 20 lines · Thierry Delisle
Quoted 2 lines
Let's move the discussion to the new thread.
I'm happy to start a new thread. I'm re-responding to my last post because many
of my questions are still unanswered.Quoted 5 lines
+ * State transitions:
+ *
+ * RUNNING => IDLE: the current RUNNING task becomes IDLE by calling
+ *sys_umcg_wait();Quoted 7 lines
[...]
+/**
+ * enumumcg_wait_flag- flags to pass tosys_umcg_wait
+ * @UMCG_WAIT_WAKE_ONLY: wake @self->next_tid, don't put @self to sleep;
+ * @UMCG_WF_CURRENT_CPU: wake @self->next_tid on the current CPU
+ * (useWF_CURRENT_CPU); @UMCG_WAIT_WAKE_ONLYmust be set.
Quoted 12 lines
include/uapi/linux/umcg.h line 244
Quoted 5 lines
+ */
include/uapi/linux/umcg.h new file +4
-0+enum umcg_wait_flag { +UMCG_WAIT_WAKE_ONLY =1 , +UMCG_WF_CURRENT_CPU =2 , +};What is the purpose of using
sys_umcg_waitwithoutnext_tidor withUMCG_WAIT_WAKE_ONLY? It looks like Java's park/unpark semantics to me, that is
worker threads can use this for synchronization and mutual exclusion. In this
case, how do these compare to using FUTEX_WAIT/FUTEX_WAKE?
sys_umcg_wait without next_tid puts the task in UMCG_IDLE state; wake wakes it. These are standard sched operations. If they are emulated via futexes, fast context switching will require something like FUTEX_SWAP that was NACKed last year.
Quoted 28 lines
Quoted 28 lines
include/uapi/linux/umcg.h new file +23
-0+struct umcg_task { +/** +* @server_tid: the TID of the server UMCG task that should be +* woken when this WORKER becomes BLOCKED. Can be zero. +* +* If this is a UMCG server, @server_tid should +* contain the TID of @self - it will be used to find +* the task_struct to wake when pulled from +* @idle_servers. +* +* Read-only for the kernel, read/write for the userspace. +*/ +uint32_t server_tid;/* r */ +/** +* @idle_servers_ptr: a single-linked list pointing to the list +* of idle servers. Can be NULL. +* +* Readable/writable by both the kernel and the userspace: the +* userspace adds items to the list, the kernel removes them. +* +* TODO: describe how the list works. +*/ +uint64_t idle_servers_ptr;/* r/w */
Quoted 8 lines
Quoted 1 line
+}
__attribute__((packed, aligned(8 * sizeof(__u64))));From the comments and by elimination, I'm guessing that
idle_servers_ptris
somehow used by servers to block until some worker threads become idle. However,
I do not understand how the userspace is expected to use it. I also do not understand if these link fields form a stack or a queue and where is the head.
When a server has nothing to do (no work to run), it is put into IDLE state and added to the list. The kernel wakes an IDLE server if a blocked worker unblocks.
Quoted 23 lines
Quoted 8 lines
+/**
+ *sys_umcg_ctl: (un)register a task as a UMCG task.+ * @flags: ORed values from enum umcg_ctl_flag; see below; + * @self: a pointer to struct umcg_task that describes this + * task and governs the behavior of sys_umcg_wait if + * registering; must be NULL if unregistering.Quoted 7 lines
+ *
+ * @flags &UMCG_CTL_REGISTER: register a UMCG task:
+ * UMCG workers:
+ * -self->statemust beUMCG_TASK_IDLE
+ * - @flags &UMCG_CTL_WORKER
+ *
+ * If the conditions above are met,sys_umcg_ctl()immediately returns
Quoted 1 line
+ * if the registered task is a RUNNING server or basic task;
an IDLE
Quoted 1 line
+ * worker will be added to
idle_workers_ptr, and the workerput to
Quoted 1 line
+ * sleep; an idle server from
idle_servers_ptrwill bewoken, if any.
Quoted 9 lines
This approach to creating UMCG workers concerns me a little. My understanding
is that in general, the number of servers controls the amount of parallelism in the program. But in the case of creating new UMCG workers, the new threads
only respect the M:N threading model aftersys_umcg_ctlhas blocked. What does
this mean for applications that create thousands of short lived tasks? Are users expcted to create pools of reusable UMCG workers?
Yes: task/thread creation is not as lightweight as just posting work items onto a preexisting pool of workers.
Quoted 7 lines
I would suggest adding at least one
uint64_tfield to the structumcg_taskthat
is left as-is by the kernel. This allows implementers of user-space schedulers to add scheduler specific data structures to the threads without needing some kind of table on the side.
This is usually achieved by embedding the kernel struct into a larger userspace/TLS struct. For example:
struct umcg_task_user {
struct umcg_task umcg_task;
extra_user_data d1;
extra_user_ptr p1;
/* etc. */
} __aligned(...);
Re: [RFC PATCH 3/3 v0.2] sched/umcg: RFC: implement UMCG syscalls
Quoted 4 lines
sys_umcg_waitwithoutnext_tidputs the task inUMCG_IDLEstate; wake wakes it. These are standard sched operations. If they are emulated via futexes, fast context switching will require something likeFUTEX_SWAPthat was NACKed last year.
I understand these wait and wake semantics and the need for the fast context-switch(swap). As I see it, you need 3 operations:
- SWAP: context-switch directly to a different thread, no scheduler involved
- WAIT: block current thread, go back to server thread
- WAKE: unblock target thread, add it to scheduler, e.g. through idle_workers_ptr
There is no existing syscalls to handle SWAP, so I agree sys_umcg_wait is needed for this to work.
However, there already exists sys_futex to handle WAIT and WAKE. When a worker calls either sys_futex WAIT or sys_umcg_wait next_tid == NULL, in both case the worker will block, SWAP to the server and wait for FUTEX_WAKE, UMCG_WAIT_WAKE_ONLY respectively. It's not obvious to me that there would be performance difference and the semantics seem to be the same to me.
So what I am asking is: is UMCG_WAIT_WAKE_ONLY needed?
Is the idea to support workers directly context-switching among each other, without involving server threads and without going through idle_servers_ptr?
If so, can you explain some of the intended state transitions in this case.
Quoted 7 lines
Quoted 3 lines
However, I do not understand how the userspace is expected to use it. I also do not understand if these link fields form a stack or a queue and where is the head.
When a server has nothing to do (no work to run), it is put into IDLE state and added to the list. The kernel wakes an IDLE server if a blocked worker unblocks.
From the code in umcg_wq_worker_running (Step 3), I am guessing users are expected to provide a global head somewhere in memory and umcg_task.idle_servers_ptr points to the head of the list for all workers. Servers are then added in user space using atomic_stack_push_user. Is this correct? I did not find any documentation on the list head.
I like the idea that each worker thread points to a given list, it allows the possibility for separate containers with their own independent servers, workers and scheduling. However, it seems that the list itself could be implemented using existing kernel APIs, for example a futex or an event fd. Like so:
struct umcg_task {
[...]
/**
* @idle_futex_ptr: pointer to a futex user for idle server threads. *
* When waking a worker, the kernel decrements the pointed to futex value
* if it is non-zero and wakes a server if the decrement occurred. *
* Server threads that have no work to do should increment the futex
* value and FUTEX_WAIT
*/
uint64_t idle_futex_ptr; /* r/w */
[...]
} __attribute__((packed, aligned(8 * sizeof(__u64))));
I believe the futex approach, like the list, has the advantage that when there are no idle servers, checking the list requires no locking. I don't know if that can be achieved with eventfd.
Re: [RFC PATCH 3/3 v0.2] sched/umcg: RFC: implement UMCG syscalls
Quoted 25 lines · Thierry Delisle
Quoted 5 lines
sys_umcg_waitwithoutnext_tidputs the task inUMCG_IDLEstate; wake wakes it. These are standard sched operations. If they are emulated via futexes, fast context switching will require something likeFUTEX_SWAPthat was NACKed last year.I understand these wait and wake semantics and the need for the fast context-switch(swap). As I see it, you need 3 operations:
- SWAP: context-switch directly to a different thread, no scheduler involved
- WAIT: block current thread, go back to server thread
- WAKE: unblock target thread, add it to scheduler, e.g. throughidle_workers_ptrThere is no existing syscalls to handle SWAP, so I agree
sys_umcg_waitis needed for this to work.However, there already exists
sys_futexto handle WAIT and WAKE. When a worker
calls eithersys_futexWAIT orsys_umcg_waitnext_tid== NULL, in both case the worker will block, SWAP to the server and wait forFUTEX_WAKE,UMCG_WAIT_WAKE_ONLYrespectively. It's not obvious to me that there would be
performance difference and the semantics seem to be the same to me.
Quoted 1 line
So what I am asking is: is
UMCG_WAIT_WAKE_ONLYneeded?
Because the approach you described has been tried last year and was NACKed:
https://lore.kernel.org/lkml/[email protected]/
In short, futex maintainers do not want to touch the existing futex code at all other than for bugfixes. No new futex functionality, period. See e.g. futex2 efforts:
https://lore.kernel.org/lkml/[email protected]/
Quoted 2 lines
Is the idea to support workers directly context-switching among each other, without involving server threads and without going through
idle_servers_ptr?
Yes.
Quoted 1 line
If so, can you explain some of the intended state transitions in this case.
Cooperative scheduling: workers can yield to each other (i.e. swap). This allows building very fast concurrency primitives (mutexes, producer-consumer queues, etc.). For example: a producer-consumer
queue: a producer: prepare an item, contex-switch to a consumer on CPU
synchronously: this can be done much faster than waking the consumer asynchronously; helps a lot to reduce latency (throughput? not so much)
Quoted 12 lines
Quoted 3 lines
Quoted 3 lines
However, I do not understand how the userspace is expected to use
it. I also
Quoted 1 line
Quoted 1 line
do not understand if these link fields form a stack or a queue and
where is
Quoted 5 lines
Quoted 1 line
the head.
When a server has nothing to do (no work to run), it is put into IDLE state and added to the list. The kernel wakes an IDLE server if a blocked worker unblocks.
Quoted 5 lines
From the code in
umcg_wq_worker_running(Step 3), I am guessing users are
expected to provide a global head somewhere in memory and umcg_task.idle_servers_ptr points to the head of the list for all workers. Servers are then added in user space usingatomic_stack_push_user. Is this correct? I did not find any documentation on the list head.
This is going to change somewhat. I'll post a new patchset soon-ish (later this week?)
Quoted 26 lines
I like the idea that each worker thread points to a given list, it allows the
possibility for separate containers with their own independent servers, workers
and scheduling. However, it seems that the list itself could be implemented using existing kernel APIs, for example a futex or an event fd. Like so:struct umcg_task { [...] /** * @idle_futex_ptr: pointer to a futex user for idle server threads. * * When waking a worker, the kernel decrements the pointed to futex value * if it is non-zero and wakes a server if the decrement occurred. * * Server threads that have no work to do should increment the futex * value and FUTEX_WAIT */ uint64_t idle_futex_ptr; /* r/w */ [...] } __attribute__((packed, aligned(8 * sizeof(__u64))));
Quoted 4 lines
I believe the futex approach, like the list, has the advantage that when there
are no idle servers, checking the list requires no locking. I don't know if that can be achieved with eventfd.
As mentioned above, a futex-based solution was rejected by maintainers. Believe me, I tried. Not only tried, we have a working userspace scheduling stack on top of FUTEX_SWAP deployed internally at Google, with some actual usage (mostly testing/debugging workloads). I suggest we stop discussing futexes in this context - I do not see the maintainers changing their position. And the approach used in this patchset seems to work (and I actually like how the code is shaping up).
Peter Zijlstra
maintainerRe: [RFC PATCH 3/3 v0.2] sched/umcg: RFC: implement UMCG syscalls
Quoted 11 lines · Peter Oskolkov
Quoted 1 line · Thierry Delisle
So what I am asking is: is
UMCG_WAIT_WAKE_ONLYneeded?Because the approach you described has been tried last year and was NACKed:
https://lore.kernel.org/lkml/[email protected]/In short, futex maintainers do not want to touch the existing futex code at all other than for bugfixes. No new futex functionality, period. See e.g. futex2 efforts:
https://lore.kernel.org/lkml/[email protected]/
These are two orthogonal issues. We do not want to make the futex multiplex monster worse, but that's not the reason for rejecting FUTEX_SWAP.
The problem with FUTEX_SWAP is that it doesn't even begin to solve the posed problem, namely N:M threading that natively allows blocking syscalls (IOW without wrapping all syscalls).
This means we need kernel->user notification of tasks that block and wakeup, such that the userspace scheduler can adequately react. This is not something that sanely fits in futex.
It also requires an additional kernel side block point such that tasks that blocked in-kernel, will not resume userspace when the userspace scheduler decided to run another task in its stead.
These things are what resulted in UMCG.