Skip to contentSkip to conversation

sched/UMCG

RFC PATCH In review Peter Oskolkov 3 participants 14 messages Jul 16, 2021 – Jul 26, 2021

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

cover sched/UMCG

This is another attempt at implementing UMCG, based on discussion in https://lore.kernel.org/patchwork/cover/1433967/ and
https://lore.kernel.org/lkml/[email protected]/

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.

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: add helpers to work with single-linked lists in userspace Patch 4: 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.

v0.2->v0.3 chages:
- split patch 2 into two paches: atomic ops and llist ops
- rework atomic ops in patch 2 to avoid "stac/clac nonsense"
- make llist kernel-side operations constant time (no indefinite spinning)
- make task wakeup work without spinning/retries

I'm not aware of any issues with this patchset other than what's mentioned below. In short, it seems that "SMP basics":
block/wake detection, worker "scheduling" by servers, etc. all work.

TODO:
- combine cmpxchg_user_32/64 functions into a macro in patch 2
- implement timeout handling
- imlement worker preemption
- more testing
- manpages, docs, and similar
- attach libumbc and selftest patches

Peter Oskolkov (4):
sched: add WF_CURRENT_CPU and externise ttwu
sched/umcg: RFC: add userspace atomic helpers
sched/umcg: RFC: add userspace sll 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              | 259 +++++++++++++
 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                    | 485 +++++++++++++++++++++++++
 kernel/sched/umcg.h                    | 298 +++++++++++++++
 kernel/sys_ni.c                        |   4 +
 14 files changed, 1112 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

#1 lore raw

RFC PATCH 1/4 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
index 0c22cd026440..293f5801bf81 100644
@@ -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
index 11d22943753f..16a9c93e6e82 100644
@@ -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
index 9a1c6aeb9165..80de6836f8ae 100644
@@ -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

#2 lore raw

RFC PATCH 2/4 sched/umcg: RFC: add userspace atomic helpers

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

Note: the current code follows sugestions here:
https://lore.kernel.org/lkml/[email protected]/
with the exception that I couldn't combine __try_cmpxchg_user_32/64 functions into a macro, as my asm foo is not too strong. I'll continue trying to make the macro work, but for the moment I've decided to post this RFC so that other areas of the patchset could be reviewed.

Changelog:
v0.2->v0.3:
- renamed and refactored the helpers a bit, as described above;
- moved linked list/stack operations into a separate patch.

---
 kernel/sched/umcg.h | 169 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 169 insertions(+)
 create mode 100644 kernel/sched/umcg.h
kernel/sched/umcg.h new file +169 -0
new file mode 100644
index 000000000000..288017f5368c
@@ -0,0 +1,169 @@
+/* SPDX-License-Identifier: GPL-2.0+ WITH Linux-syscall-note */
+#ifndef _KERNEL_SCHED_UMCG_H
+#define _KERNEL_SCHED_UMCG_H
+
+#ifdef CONFIG_X86_64
+
+#include <linux/uaccess.h>
+
+#include <asm/asm.h>
+#include <linux/atomic.h>
+
+/* TODO: move atomic operations below into arch/ headers */
+static inline int __try_cmpxchg_user_32(u32 *uval, u32 __user *uaddr,
+						u32 oldval, u32 newval)
+{
+	int ret = 0;
+
+	asm volatile("\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"
+	);
+	*uval = oldval;
+	return ret;
+}
+
+static inline int __try_cmpxchg_user_64(u64 *uval, u64 __user *uaddr,
+						u64 oldval, u64 newval)
+{
+	int ret = 0;
+
+	asm volatile("\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"
+	);
+	*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;
+}
+
+/**
+ * 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 cmpxchg_user_32(u32 __user *uaddr, u32 *old, u32 new)
+{
+	int ret = -EFAULT;
+	u32 __old = *old;
+
+	if (unlikely(!access_ok(uaddr, sizeof(*uaddr))))
+		return -EFAULT;
+
+	pagefault_disable();
+
+	while (true) {
+		__uaccess_begin_nospec();
+		ret = __try_cmpxchg_user_32(old, uaddr, __old, new);
+		user_access_end();
+
+		if (!ret) {
+			ret =  *old == __old ? 0 : -EAGAIN;
+			break;
+		}
+
+		if (fix_pagefault((unsigned long)uaddr, true) < 0)
+			break;
+	}
+
+	pagefault_enable();
+	return ret;
+}
+
+/**
+ * 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 cmpxchg_user_64(u64 __user *uaddr, u64 *old, u64 new)
+{
+	int ret = -EFAULT;
+	u64 __old = *old;
+
+	if (unlikely(!access_ok(uaddr, sizeof(*uaddr))))
+		return -EFAULT;
+
+	pagefault_disable();
+
+	while (true) {
+		__uaccess_begin_nospec();
+		ret = __try_cmpxchg_user_64(old, uaddr, __old, new);
+		user_access_end();
+
+		if (!ret) {
+			ret =  *old == __old ? 0 : -EAGAIN;
+			break;
+		}
+
+		if (fix_pagefault((unsigned long)uaddr, true) < 0)
+			break;
+	}
+
+	pagefault_enable();
+	return ret;
+}
+
+/**
+ * get_user_nosleep - get user value with inline fixup without sleeping.
+ *
+ * get_user() might sleep and therefore cannot be used in preempt-disabled
+ * regions.
+ */
+#define get_user_nosleep(out, uaddr)					\
+({									\
+	int ret = -EFAULT;						\
+									\
+	if (access_ok((uaddr), sizeof(*(uaddr)))) {				\
+		pagefault_disable();					\
+									\
+		while (true) {						\
+			if (!__get_user((out), (uaddr))) {			\
+				ret = 0;				\
+				break;					\
+			}						\
+									\
+			if (fix_pagefault((unsigned long)(uaddr), true) < 0) \
+				break;					\
+		}							\
+									\
+		pagefault_enable();					\
+	}								\
+	ret;								\
+})
+
+#endif  /* CONFIG_X86_64 */
+#endif  /* _KERNEL_SCHED_UMCG_H */

--
2.25.1

#3 lore raw

RFC PATCH 3/4 sched/umcg: RFC: add userspace sll helpers

In reply to Peter Oskolkov

The helpers below can work with userspace single-linked lists concurrently without indefinitely spinning in the kernel. Specifically:

push (add to the head of the list):

step = 0
while (++step < N)
old = *head
*next = old
cmp_xchng(head, &old, next)

pop (remove the first element from the list):
mark the node as deleted by flipping its lowest bit without actually removing the node from the list:

curr = *head
step = 0

  while (curr && ++step < N)

next = *curr
if (next & 1)
curr = next & ~1
continue

if (cmp_xchng(curr, next, next | 1))
return curr
else
curr = next & ~1

It is the userspace's responsibility to actually remove the nodes marked as deleted from the list.

v0.2->v0.3 changes:
- removed spinning from the kernel (other than capped cmpxchg).

---
 kernel/sched/umcg.h | 116 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)
kernel/sched/umcg.h +116 -0
index 288017f5368c..435531d751f2 100644
@@ -165,5 +165,121 @@ static inline int cmpxchg_user_64(u64 __user *uaddr, u64 *old, u64 new)
 	ret;								\
 })
 
+/**
+ * umcg_sll_push - push a node onto a single-linked-list (stack) in userspace
+ * @head      - a pointer to the head of the stack;
+ * @node      - a pointer to the node to push;
+ * @max_tries - the maximum number of attempts to push the node onto the list.
+ *
+ * Push a node onto a single-linked list (stack). The function tries
+ * @max_tries times and returns -EAGAIN if too many concurrent updates, so that
+ * the caller may yield the CPU.
+ *
+ * Return:
+ * 0        - success;
+ * -EFAULT  - error;
+ * -EAGAIN  - try again.
+ */
+static inline int umcg_sll_push(u64 __user *head, u64 __user *node, int max_tries)
+{
+	int step;
+
+	for (step = 0; step < max_tries; step++) {
+		int ret;
+		u64 first;
+
+		smp_mb();  /* Make the read below clean. */
+		if (get_user(first, head))
+			return -EFAULT;
+
+		if (put_user(first, node))
+			return -EFAULT;
+		smp_mb();  /* Make the write above visible. */
+
+		ret = cmpxchg_user_64(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;
+	}
+
+	return -EAGAIN;
+}
+
+/**
+ * umcg_sll_pop - pop a node from a single-linked-list (stack) in the userspace
+ * @head      - a pointer to the head of the stack;
+ * @value     - a pointer to where store the popped value;
+ * @max_tries - the maximum number of nodes to try to pop.
+ *
+ * Pop a node from a single-linked list (stack). Internally, popped nodes
+ * are marked as such, and not actually removed from the list, to avoid
+ * the ABA problem. It is the responsibility of the userspace to do GC.
+ *
+ * As an additional protection, the function checks only the first
+ * @max_tries nodes.
+ *
+ * Note: on success, @value should be cast to (u64 __user *) if not zero.
+ *
+ * Return:
+ * 0        - success;
+ * -EFAULT  - error;
+ * -EAGAIN  - try again.
+ */
+static inline int umcg_sll_pop(u64 __user *head, u64 *value, int max_tries)
+{
+	int step;
+	u64 curr;
+
+	smp_mb();  /* Make the read below clean. */
+	if (get_user(curr, head))
+		return -EFAULT;
+
+	for (step = 0; step < max_tries; step++) {
+		int ret;
+		u64 next;
+
+		if (!curr) {
+			*value = 0UL;
+			return 0;
+		}
+
+		if (curr & 1UL)
+			return -EFAULT;  /* Should not happen. */
+
+		smp_mb();  /* Make the read below clean. */
+		if (get_user(next, (u64 __user *)curr))
+			return -EFAULT;
+
+		if (next & 1UL) { /* curr is deleted */
+			curr = next & ~1UL;
+			continue;
+		}
+
+		ret = cmpxchg_user_64((u64 __user *)curr, &next, next | 1UL);
+		if (!ret) {
+			*value = curr;
+			return 0;
+		}
+		if (ret == -EAGAIN) {
+			curr = next & ~1UL;
+			cpu_relax();
+			continue;
+		}
+
+		if (ret)
+			return -EFAULT;
+	}
+
+	return -EAGAIN;
+}
 #endif  /* CONFIG_X86_64 */
 #endif  /* _KERNEL_SCHED_UMCG_H */

--
2.25.1

#4 lore raw

Re: [RFC PATCH 3/4 v0.3] sched/umcg: RFC: add userspace sll helpers

Quoted 25 lines

The helpers below can work with userspace single-linked lists concurrently without indefinitely spinning in the kernel. Specifically:

push (add to the head of the list):

   step = 0
   while (++step < N)
      old = *head
      *next = old
      cmp_xchng(head, &old, next)

pop (remove the first element from the list):
     mark the node as deleted by flipping its lowest bit without actually removing the node from the list:

   curr = *head
   step = 0

   while (curr && ++step < N)

     next = *curr
     if (next & 1)
         curr = next & ~1
         continue

Quoted 7 lines

     if (cmp_xchng(curr, next, next | 1))
         return curr
     else
         curr = next & ~1

It is the userspace's responsibility to actually remove the nodes marked as deleted from the list.

I believe the subsystem called Nemesis introduced a MCS-based queue that could be useful here. The original paper is https://doi.org/10.1109/CCGRID.2006.31

You can also look at this repo for an implementation of the queue.
https://git.uwaterloo.ca/mkarsten/libfibre/-/blob/master/src/runtime/LockFreeQueues.h

While it uses 2 pointers, I believe it would fit well for idle_workers_ptr since the push operation is wait-free, which avoids problems for the kernel. The pop operation requires a lock in userspace *if* multiple servers can consume from the same queue, but I don't believe it's a requirement in general.

#5 lore raw

RFC PATCH 4/4 sched/umcg: RFC: implement UMCG syscalls

In reply to Peter Oskolkov

Define 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 this commit message with more "why" when the general approach is ACKed at a high level.

In this patch I used the approach suggested by peterz@ (should I add a Suggested-by: tag?) in the discussion linked above; specifically, only a single

struct umcg_task __user *umcg_task

pointer is added to struct task_struct.

Comments in include/uapi/linux/umcg.h and kernel/sched/umcg.c provide many details on how UMCG syscalls are to be used.

What is NOT implemented yet:
- timeouts;
- preemption.

All the basics (wait/wake/swap, block/wake detection) seem to be working.

v0.2->v0.3 changes:
- new protocol for working with idle workers and servers is used, to avoid spinning in the kernel;
- waking a UMCG task now does not require spinning.

---
 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              | 259 +++++++++++++
 init/Kconfig                           |  10 +
 kernel/exit.c                          |   7 +
 kernel/sched/Makefile                  |   1 +
 kernel/sched/core.c                    |  17 +-
 kernel/sched/umcg.c                    | 485 +++++++++++++++++++++++++
 kernel/sched/umcg.h                    |  13 +
 kernel/sys_ni.c                        |   4 +
 12 files changed, 813 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
index ce18119ea0d0..0c6c7fd72b0b 100644
@@ -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
index 50db9496c99d..185ad1cdde77 100644
@@ -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
index 050511e8f1f8..f3e1ef8d842f 100644
@@ -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
index 6de5a7fc066b..1a4c9ac0e296 100644
@@ -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 +259 -0

259 lines not on this page · raw message

init/Kconfig +10 -0
index a61c92066c2e..c15a50a61ba6 100644
@@ -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
index fd1c04193e18..dc8398558d87 100644
@@ -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
index 978fcfca5871..e4e481eee1b7 100644
@@ -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
index 293f5801bf81..f7ddeed72e30 100644
@@ -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
 		else
 			io_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
 		else
 			io_wq_worker_running(tsk);
 	}
kernel/sched/umcg.c new file +485 -0

485 lines not on this page · raw message

kernel/sched/umcg.h +13 -0
index 435531d751f2..619ba02be1d4 100644
@@ -9,6 +9,19 @@
 #include <asm/asm.h>
 #include <linux/atomic.h>
 
+#ifdef CONFIG_UMCG
+
+struct task_struct;
+
+/*
+ * 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);
+
+#endif  /* CONFIG_UMCG */
+
 /* TODO: move atomic operations below into arch/ headers */
 static inline int __try_cmpxchg_user_32(u32 *uval, u32 __user *uaddr,
 						u32 oldval, u32 newval)
kernel/sys_ni.c +4 -0
index 0ea8128468c3..cd1be6356e42 100644
@@ -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

#6 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 32 lines

/**
  * @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.
  *
  * This is a single-linked list (stack): head->next->next->next->NULL.
  * "next" nodes are idle_servers_ptr fields in struct umcg_task.
  *
  * Example:
  *
  *  a running worker             idle server 1        idle server 2
  *
  * struct umct_task:             struct umcg_task:    struct umcg_task:
  *    state                         state state
  *    api_version                   api_version api_version
  *    ...                           ...                  ...
  *    idle_servers_ptr --> head --> idle_servers_ptr --> idle_servers_ptr --> NULL *    ...                           ...                  ...
  *
  *
  * Due to the way struct umcg_task is aligned, idle_servers_ptr
  * is aligned at 8 byte boundary, and so has its first byte as zero
  * when it holds a valid pointer.
  *
  * When pulling idle servers from the list, the kernel marks nodes as
  * "deleted" by ORing the node value (the pointer) with 1UL atomically.
  * If a node is "deleted" (i.e. its value AND 1UL is not zero),
  * the kernel proceeds to the next node.
  *
  * The kernel checks at most [nr_cpu_ids * 2] first nodes in the list.

Quoted 8 lines

  *
  * It is NOT considered an error if the kernel cannot find an idle
  * server.
  *
  * The userspace is responsible for cleanup/gc (i.e. for actually
  * removing nodes marked as "deleted" from the list). */
uint64_t    idle_servers_ptr;    /* r/w */

I don't understand the reason for using this ad-hoc scheme, over using a simple eventfd to do the job. As I understand it, the goal here is to let servers that cannot find workers to run, block instead of spinning. Isn't that exactly what the eventfd interface is for?

Have you considered an idle_fd field, the kernel writes 1 to the fd when a worker is appended to the idle_workers_ptr? Servers that don't find work can read the fd or alternatively use select/poll/epoll. Multiple workers are expected to share fds, either a single global fd, one fd per server, or any other combination the scheduler may fancy.

#7 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 43 lines · Thierry Delisle
Quoted 16 lines

/**
* @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. *
* This is a single-linked list (stack): head->next->next->next->NULL.
* "next" nodes are idle_servers_ptr fields in struct umcg_task. *
* Example:
*
* a running worker idle server 1 idle server 2
*
* struct umct_task: struct umcg_task: struct umcg_task:

Quoted 4 lines
 *    state                         state state
 *    api_version                   api_version api_version
 *    ...                           ...                  ...
 *    idle_servers_ptr --> head --> idle_servers_ptr -->

idle_servers_ptr --> NULL

Quoted 13 lines

* ... ... ...
*
*
* Due to the way struct umcg_task is aligned, idle_servers_ptr
* is aligned at 8 byte boundary, and so has its first byte as zero
* when it holds a valid pointer.
*
* When pulling idle servers from the list, the kernel marks nodes as
* "deleted" by ORing the node value (the pointer) with 1UL atomically.
* If a node is "deleted" (i.e. its value AND 1UL is not zero),
* the kernel proceeds to the next node.
*
* The kernel checks at most [nr_cpu_ids * 2] first nodes in the list.

Quoted 8 lines

*
* It is NOT considered an error if the kernel cannot find an idle
* server.
*
* The userspace is responsible for cleanup/gc (i.e. for actually
* removing nodes marked as "deleted" from the list). */
uint64_t idle_servers_ptr; /* r/w */

Quoted 7 lines

I don't understand the reason for using this ad-hoc scheme, over using a simple
eventfd to do the job. As I understand it, the goal here is to let servers that
cannot find workers to run, block instead of spinning. Isn't that exactly what
the eventfd interface is for?

Latency/efficiency: on worker wakeup an idle server can be picked from the list and context-switched into synchronously, on the same CPU. Using FDs and select/poll/epoll will add extra layers of abstractions; synchronous context-switches (not yet fully implemented in UMCG) will most likely be impossible. This patchset seems much more efficient and lightweight than whatever can be built on top of FDs.

Quoted 7 lines

Have you considered an idle_fd field, the kernel writes 1 to the fd when a worker is appended to the idle_workers_ptr? Servers that don't find work can read the fd or alternatively use select/poll/epoll. Multiple workers are expected to share fds, either a single global fd, one fd per server, or any other combination the scheduler may fancy.

#8 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 6 lines

Latency/efficiency: on worker wakeup an idle server can be picked from the list and context-switched into synchronously, on the same CPU. Using FDs and select/poll/epoll will add extra layers of abstractions; synchronous context-switches (not yet fully implemented in UMCG) will most likely be impossible. This patchset seems much more efficient and lightweight than whatever can be built on top of FDs.

I can believe that.

Are you planning to support separate scheduling instances within a single user space? That is having multiple sets of server threads and workers can only run within a specific set.

I believe the problem with the idle_servers_ptr as specified is that it is not possible to reclaim used nodes safely. I don't see any indication of which nodes the kernel can concurrently access and on which some memory reclamation scheme could be based.

What is the benefit of having users maintain themselves a list of idle servers rather than each servers marking themselves as 'out of work' and having the kernel maintain the list?

#9 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 8 lines · Thierry Delisle
Quoted 7 lines

Latency/efficiency: on worker wakeup an idle server can be picked from the list and context-switched into synchronously, on the same CPU. Using FDs and select/poll/epoll will add extra layers of abstractions; synchronous context-switches (not yet fully implemented in UMCG) will most likely be impossible. This patchset seems much more efficient and lightweight than whatever can be built on top of FDs.

Quoted 7 lines

I can believe that.

Are you planning to support separate scheduling instances within a single user
space? That is having multiple sets of server threads and workers can only run
within a specific set.

Yes, this is naturally supported in the current patchset on the kernel side, and is supported in libumcg (to be posted, later when the kernel side is settled); internally at Google, some applications use different "groups" of workers/servers per NUMA node.

Quoted 7 lines

I believe the problem with the idle_servers_ptr as specified is that it is not
possible to reclaim used nodes safely. I don't see any indication of which nodes the kernel can concurrently access and on which some memory reclamation
scheme could be based.

Please see the attached atomic_stack.h file - I use it in my tests, things seem to be working. Specifically, atomic_stack_gc does the cleanup. For the kernel side of things, see the third patch in this patchset.

Quoted 5 lines

What is the benefit of having users maintain themselves a list of idle servers
rather than each servers marking themselves as 'out of work' and having the kernel maintain the list?

To keep the kernel side light and simple. To also protect the kernel from spinning if userspace misbehaves. Basically, the overall approach is to delegate most of the work to the userspace, and keep the bare minimum in the kernel.

/* SPDX-License-Identifier: GPL-2.0 */

#ifndef __ATOMIC_STACK_H
#define __ATOMIC_STACK_H

#include <assert.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#include <stdio.h>
#include <stdlib.h>

/*
* Atomic Stack: a sigle-linked stack that allows fully concurrent
* push/pop operations.
*
* The stack is simple: head->node->node->NULL.
*
*
* Sample usage:
*
* struct my_stack_node {
* type1 val1;
* type2 val2;
* uint64_t next;
* } __attribute__((aligned(8)));
*
* uint64_t head = 0UL;
* struct my_stack_node *node;
*
* node = malloc(sizeof(struct my_stack_node));
* node->val1 = xxx;
* node->val2 = yyy;
* atomic_stack_push(&head, &node->next);
*
* assert(node == container_of(atomic_stack_pop(&head),
* struct my_stack_node, next));
*/

/**
* atomic_stack_is_empty - check if the stack is empty
* @head - a pointer to the head of the stack. */
static inline bool atomic_stack_is_empty(uint64_t *head)

{
	uint64_t curr = atomic_load_explicit(head, memory_order_acquire);

	do {
		uint64_t next;

		if (!curr)
			return true;

		assert(!(curr & 1UL));
		next = atomic_load_explicit((uint64_t *)curr, memory_order_acquire);
		if (!(next & 1UL))
			return false;  /* found a non-deleted node */

		curr = next & ~1UL;
	} while (true);
}

/**
* atomic_stack_push - push a node onto the stack
* @head - a pointer to the head of the stack;
* @node - a pointer to the node to push.
*/
static inline void atomic_stack_push(uint64_t *head, uint64_t *node)

{
	while (true) {
		uint64_t first = atomic_load_explicit(head,
				memory_order_acquire);

		atomic_store_explicit(node, first, memory_order_release);

		if (atomic_compare_exchange_weak_explicit(head, &first,
					(uint64_t)node,
					memory_order_acq_rel,
					memory_order_relaxed))
			return;
	}
}

/**
* atomic_stack_pop - pop a node from the stack
* @head - a pointer to the head of the stack.
*
* Returns a pointer to the popped node (to be used in container_of), or NULL
* if the stack is empty.
*/
static inline uint64_t* atomic_stack_pop(uint64_t *head)

{
	uint64_t *curr = (uint64_t *)atomic_load_explicit(head,
					memory_order_acquire);

	do {
		uint64_t next;

		if (!curr)
			return NULL;

		assert(!((uint64_t)curr & 1UL));
		next = atomic_load_explicit(curr, memory_order_acquire);

		if (next & 1UL) { /* curr is deleted */
			curr = (uint64_t *)(next & ~1UL);
			continue;
		}

		if (atomic_compare_exchange_strong_explicit(curr,
				&next, next | 1UL,
				memory_order_release, memory_order_relaxed))
			return curr;

		curr = (uint64_t *)(next & ~1UL);
	} while (true);
}

static inline bool atomic_stack_remove(uint64_t *head, uint64_t *node)

{
	uint64_t *curr = (uint64_t *)atomic_load_explicit(head,
					memory_order_acquire);

	do {
		uint64_t next;

		if (!curr)
			return false;

		next = atomic_load_explicit(curr, memory_order_acquire);

		if (next & 1UL) { /* curr is deleted */
			if (curr == node)
				return false;
			curr = (uint64_t *)(next & ~1UL);
			continue;
		}

		if (curr == node)
		       return atomic_compare_exchange_strong_explicit(
					curr, &next, next | 1UL,
					memory_order_release,
					memory_order_relaxed);

		curr = (uint64_t *)(next & ~1UL);
	} while (true);
}

/**
* atomic_stack_pop_all - pop all nodes from the stack
* @head - a pointer to the head of the stack.
*
* Returns a pointer to the first node (to be used in container_of), or NULL
* if the stack is empty.
*/
static inline uint64_t* atomic_stack_pop_all(uint64_t *head)

{
	while (true) {
		bool ok;
		uint64_t first = atomic_load_explicit(head,
				memory_order_acquire);

		if (!first)
			return NULL;

		ok = atomic_compare_exchange_strong_explicit(head, &first, 0UL,
				memory_order_release, memory_order_relaxed);
		assert(ok);
		return (uint64_t *)(first);
	}
}

/**
* atomic_stack_gc - remove popped/deleted elements from the stack
* @head - a pointer to the head of the stack.
*
* Note: it is most likely unsafe to run several instances
* of atomic_stack_gc() concurrently, but a single instance
* should be safe to run concurrently with push/pop/remove. */
static inline void atomic_stack_gc(uint64_t *head)

{
	uint64_t *prev = head;

	while (true) {
		uint64_t curr, next;

		assert (!(1UL & (uint64_t)prev));
		curr = atomic_load_explicit(prev, memory_order_acquire);

		if (!curr)
			return;

		if (curr & 1UL) {
			prev = head;  /* prev marked deleted; restart */
			continue;
		}

		next = atomic_load_explicit((uint64_t *)curr, memory_order_acquire);
		if (!next)
			return;

		if (next & 1UL) {  /* curr marked deleted */
			if (atomic_compare_exchange_strong_explicit(prev,
					&curr, next & ~1UL,
					memory_order_release,
					memory_order_relaxed)) {
				continue;
			}

			prev = head;  /* prev marked as deleted; restart */
			continue;
		}

		prev = (uint64_t *)curr;
	}
}

static inline void atomic_stack_print(uint64_t *head, const char *ctx)

{
	uint64_t curr = (uint64_t)head;
int cnt = 0;
	fprintf(stderr, "%s stack: ", ctx);
	do {
if (++cnt > 6) break;
		fprintf(stderr, "0x%lx => ", curr);

		if (curr & 1UL)
			curr &= ~1UL;

		if (!curr)
			break;

		curr = *(uint64_t *)curr;
	} while (curr);

	fprintf(stderr, " (nil)\n");
}

#endif /* __ATOMIC_STACK_H */

#10 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 4 lines

Yes, this is naturally supported in the current patchset on the kernel side, and is supported in libumcg (to be posted, later when the kernel side is settled); internally at Google, some applications use different "groups" of workers/servers per NUMA node.

Good to know. Cforall has the same feature, where we refer to these groups as "clusters". https://doi.org/10.1002/spe.2925 (Section 7)

Quoted 4 lines

Please see the attached atomic_stack.h file - I use it in my tests, things seem to be working. Specifically, atomic_stack_gc does the cleanup. For the kernel side of things, see the third patch in this patchset.

I don't believe the atomic_stack_gc function is robust enough to be offering any guarantee. I believe that once a node is unlinked, its next pointer should be reset immediately, e.g., by writing 0xDEADDEADDEADDEAD. Do your tests work if the next pointer is reset immediately on reclaimed nodes?

As far as I can tell, the reclaimed nodes in atomic_stack_gc still contain valid next fields. I believe there is a race which can lead to the kernel reading reclaimed nodes. If atomic_stack_gc does not reset the fields, this bug could be hidden in the testing.

An more aggressive test is to put each node in a different page and remove read permissions when the node is reclaimed. I'm not sure this applies when the kernel is the one reading.

Quoted 4 lines

To keep the kernel side light and simple. To also protect the kernel from spinning if userspace misbehaves. Basically, the overall approach is to delegate most of the work to the userspace, and keep the bare minimum in the kernel.

I'll try to keep this in mind then.

After some thought, I'll suggest a scheme to significantly reduce complexity. As I understand, the idle_workers_ptr are linked to form one or more Multi-Producer Single-Consumer queues. If each head is augmented with a single volatile tid-sized word, servers that want to go idle can simply write their id in the word. When the kernel adds something to the idle_workers_ptr list, it simply does an XCHG with 0 or any INVALID_TID. This scheme only supports one server blocking per idle_workers_ptr list. To keep the "kernel side light and simple", you can simply ask that any extra servers must synchronize among each other to pick which server is responsible for wait on behalf of everyone.

#11 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 14 lines · Thierry Delisle
Quoted 5 lines

Yes, this is naturally supported in the current patchset on the kernel side, and is supported in libumcg (to be posted, later when the kernel side is settled); internally at Google, some applications use different "groups" of workers/servers per NUMA node.

Good to know. Cforall has the same feature, where we refer to these groups as "clusters". https://doi.org/10.1002/spe.2925 (Section 7)

Quoted 4 lines

Please see the attached atomic_stack.h file - I use it in my tests, things seem to be working. Specifically, atomic_stack_gc does the cleanup. For the kernel side of things, see the third patch in this patchset.

Quoted 7 lines

I don't believe the atomic_stack_gc function is robust enough to be offering
any guarantee. I believe that once a node is unlinked, its next pointer should
be reset immediately, e.g., by writing 0xDEADDEADDEADDEAD. Do your tests work
if the next pointer is reset immediately on reclaimed nodes?

In my tests reclaimed nodes have their next pointers immediately set to point to the list head. If the kernel gets a node with its @next pointing to something else, then yes, things break down (the kernel kills the process); this has happened occasionally when I had a bug in the userspace code.

Quoted 6 lines

As far as I can tell, the reclaimed nodes in atomic_stack_gc still contain valid next fields. I believe there is a race which can lead to the kernel reading reclaimed nodes. If atomic_stack_gc does not reset the fields, this bug
could be hidden in the testing.

Could you, please, provide a bit more details on when/how the race can happen? Servers add themselves to the list, so there can be no races there (servers going idle: add-to-the-list; wait; gc (under a lock); restore @next; do stuff).

Workers are trickier, as they can be woken by signals and then block again, but stray signals are so bad here that I'm thinking of actually not letting sleeping workers wake on signals. Other than signals waking queued/unqueued idle workers, are there any other potential races here?

Quoted 15 lines

An more aggressive test is to put each node in a different page and remove read
permissions when the node is reclaimed. I'm not sure this applies when the kernel is the one reading.

Quoted 4 lines

To keep the kernel side light and simple. To also protect the kernel from spinning if userspace misbehaves. Basically, the overall approach is to delegate most of the work to the userspace, and keep the bare minimum in the kernel.

I'll try to keep this in mind then.

Quoted 17 lines

After some thought, I'll suggest a scheme to significantly reduce complexity.
As I understand, the idle_workers_ptr are linked to form one or more Multi-Producer Single-Consumer queues. If each head is augmented with a single
volatile tid-sized word, servers that want to go idle can simply write their id
in the word. When the kernel adds something to the idle_workers_ptr list, it
simply does an XCHG with 0 or any INVALID_TID. This scheme only supports one
server blocking per idle_workers_ptr list. To keep the "kernel side light and
simple", you can simply ask that any extra servers must synchronize among each
other to pick which server is responsible for wait on behalf of everyone.

I'm not yet convinced that the single-linked-list approach is infeasible. And if it is, a simple fix would be to have two pointers per list in struct umcg_task: head and next.

Thanks,
Peter

#12 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 5 lines

In my tests reclaimed nodes have their next pointers immediately set to point to the list head. If the kernel gets a node with its @next pointing to something else, then yes, things break down (the kernel kills the process); this has happened occasionally when I had a bug in the userspace code.

I believe that approach is fine for production, but for testing it may not detect some bugs. For example, it may not detect the race I detail below.

Quoted 4 lines

Could you, please, provide a bit more details on when/how the race can happen? Servers add themselves to the list, so there can be no races there (servers going idle: add-to-the-list; wait; gc (under a lock); restore @next; do stuff).

I believe the race can happen if the kernel attempts to wake an idle server concurrently with a call to gc.

Here's an example list where the head points to a list of 3 items denoted A, B, C, and the second character denotes whether the element is marked for deletion: 'x' means marked, 'o' means unmarked. 'H' denotes the head.

        H -> Ax -> Bo -> Co

Now, atomic_stack_gc is expected to unlink node 'A' so it can be reclaimed, leading to "H -> Bo -> Co". Once 'A' is unlinked it can be either deleted or pushed back on the list at a later time.

In the following snippet of the atomic_stack_pop function (trimmed for space):

     static inline uint64_t* atomic_stack_pop(uint64_t *head) {
         uint64_t *curr = (uint64_t *)atomic_load_explicit(head);

         do {
             if (!curr) return NULL;

             // <--- Pause
             uint64_t next = atomic_load_explicit(curr);

At the location marked "<--- Pause", assume the code has the address of node 'A' and is about to dereference it to get the address of node 'B'. If the thread running this code pauses for any reason, a different CPU can run atomic_stack_gc and delete node 'A'. At that point, the pop function resumes and dereferences a node that no longer exists.

The thread pause can have many causes; in user-space, preemption is the most obvious, but hardware interrupts or even last-level cache misses can cause enough of a slowdown for this to happen.

The fundamental problem is that there is nothing to prevent multiple threads from manipulating the list AND concurrently attempting to reclaim nodes. As far as I know, this requires locking or a lock-free memory reclamation scheme where nodes are unlinked and then consensus is established that no thread can reach the unlinked data before reclaiming the unlinked node. While both approaches are do-able, it requires extra communication between the kernel and user-space.

In general, the kernel needs to be robust to misbehaving users and their concurrent operations. Hence, I would be wary of any looping in kernel involving an atomic operation, which requires cooperation among threads to avoid starvation.

Quoted 5 lines

Workers are trickier, as they can be woken by signals and then block again, but stray signals are so bad here that I'm thinking of actually not letting sleeping workers wake on signals. Other than signals waking queued/unqueued idle workers, are there any other potential races here?

Timeouts on blocked threads is virtually the same as a signal I think. I can see that both could lead to attempts at waking workers that are not blocked.

I haven't looked too much at the state transitions yet. I think the guarantees offered by the two lists will result in potential races in the rest of the code.

Thierry

#13 lore raw

Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls

Quoted 10 lines · Thierry Delisle
Quoted 6 lines

In my tests reclaimed nodes have their next pointers immediately set to point to the list head. If the kernel gets a node with its @next pointing to something else, then yes, things break down (the kernel kills the process); this has happened occasionally when I had a bug in the userspace code.

I believe that approach is fine for production, but for testing it may not detect some bugs. For example, it may not detect the race I detail below.

While I think I have the idle servers list working, I now believe that what peterz@ was suggesting is not much slower in the common case (many idle workers; few, if any, idle servers) than having a list of idle servers exposed to the kernel: I think having a single idle server at head, not a list, is enough: when a worker is added to idle workers list, a single idle server at head, if present, can be "popped" and woken; the userspace can maintain the list of idle servers itself; having the kernel wake only one is enough - it will pop all idle workers and decide whether any other servers are needed to process the newly available work.

[...]

Quoted 9 lines
Quoted 5 lines

Workers are trickier, as they can be woken by signals and then block again, but stray signals are so bad here that I'm thinking of actually not letting sleeping workers wake on signals. Other than signals waking queued/unqueued idle workers, are there any other potential races here?

Timeouts on blocked threads is virtually the same as a signal I think. I can see that both could lead to attempts at waking workers that are not blocked.

I've got preemption working well enough to warrant a new RFC patchset (also have timeouts done, but these were easy). I'll clean things up, change the idle servers logic to only one idle server exposed to the kernel, not a list, add some additional documentation (state transitions, userspace code snippets, etc.) and will post v0.4 RFC patchset to LKML later this week.

[...]