Restartable sequences and CPU op vector v11

Here is the last RFC round of the updated rseq patchset containing:

- Restartable sequences system call (x86 32/64, powerpc 32/64, arm 32),
- CPU operation vector system call (x86 32/64, powerpc 32/64, arm 32),
- membarrier shared expedited, and private expedited core serializing commands.

This is *not* yet a PR. I'm submitting the patchset as RFC one last time given that I did a few small fixes, and reordered the patchset, since the last time I sent it as RFC.

You can alternatively find this patchset as a git branch at this location:

https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-rseq.git
branch: v4.14-rseq-20171114

Orion Hodson is currently testing the private expedited core serializing membarrier command on Android, where they have a context synchronization issue reproducer on arm 64. We should know more about this shortly.

Thanks,

Mathieu

Boqun Feng (2):
Restartable sequences: powerpc architecture support Restartable sequences: Wire up powerpc system call

Mathieu Desnoyers (22):
Restartable sequences system call (v11)
Restartable sequences: ARM 32 architecture support Restartable sequences: wire up ARM 32 system call Restartable sequences: x86 32/64 architecture support Restartable sequences: wire up x86 32/64 system call Provide cpu_opv system call (v3)
cpu_opv: Wire up x86 32/64 system call
cpu_opv: Wire up powerpc system call
cpu_opv: Wire up ARM32 system call
cpu_opv: Implement selftests (v2)
Restartable sequences: Provide self-tests (v2) Restartable sequences selftests: arm: workaround gcc asm size guess
membarrier: selftest: Test private expedited cmd (v2)
membarrier: powerpc: Skip memory barrier in switch_mm() (v7)
membarrier: Document scheduler barrier requirements (v5)
membarrier: provide SHARED_EXPEDITED command
membarrier: selftest: Test shared expedited cmd
membarrier: Provide core serializing command
x86: Introduce sync_core_before_usermode (v2)
membarrier: x86: Provide core serializing command (v2)
membarrier: selftest: Test private expedited sync core cmd
membarrier: arm64: Provide core serializing command

 MAINTAINERS                                        |   21 +
 arch/Kconfig                                       |    7 +
 arch/arm/Kconfig                                   |    1 +
 arch/arm/kernel/signal.c                           |    7 +
 arch/arm/tools/syscall.tbl                         |    2 +
 arch/arm64/Kconfig                                 |    1 +
 arch/arm64/kernel/entry.S                          |    4 +
 arch/powerpc/Kconfig                               |    2 +
 arch/powerpc/include/asm/membarrier.h              |   26 +
 arch/powerpc/include/asm/systbl.h                  |    2 +
 arch/powerpc/include/asm/unistd.h                  |    2 +-
 arch/powerpc/include/uapi/asm/unistd.h             |    2 +
 arch/powerpc/kernel/signal.c                       |    3 +
 arch/powerpc/mm/mmu_context.c                      |    7 +
 arch/x86/Kconfig                                   |    3 +
 arch/x86/entry/common.c                            |    1 +
 arch/x86/entry/entry_32.S                          |    5 +
 arch/x86/entry/entry_64.S                          |    8 +
 arch/x86/entry/syscalls/syscall_32.tbl             |    2 +
 arch/x86/entry/syscalls/syscall_64.tbl             |    2 +
 arch/x86/include/asm/processor.h                   |   10 +
 arch/x86/kernel/signal.c                           |    6 +
 arch/x86/mm/tlb.c                                  |    6 +
 fs/exec.c                                          |    1 +
 include/linux/processor.h                          |    6 +
 include/linux/sched.h                              |   89 ++
 include/linux/sched/mm.h                           |   39 +-
 include/trace/events/rseq.h                        |   60 +
 include/uapi/linux/cpu_opv.h                       |  117 ++
 include/uapi/linux/membarrier.h                    |   66 +-
 include/uapi/linux/rseq.h                          |  138 +++
 init/Kconfig                                       |   37 +
 kernel/Makefile                                    |    2 +
 kernel/cpu_opv.c                                   |  968 +++++++++++++++
 kernel/fork.c                                      |    2 +
 kernel/rseq.c                                      |  328 +++++
 kernel/sched/core.c                                |   95 +-
 kernel/sched/membarrier.c                          |  169 ++-
 kernel/sched/sched.h                               |    2 +
 kernel/sys_ni.c                                    |    4 +
 tools/testing/selftests/Makefile                   |    2 +
 tools/testing/selftests/cpu-opv/.gitignore         |    1 +
 tools/testing/selftests/cpu-opv/Makefile           |   17 +
 .../testing/selftests/cpu-opv/basic_cpu_opv_test.c | 1157 ++++++++++++++++++
 tools/testing/selftests/cpu-opv/cpu-op.c           |  348 ++++++
 tools/testing/selftests/cpu-opv/cpu-op.h           |   68 ++
 tools/testing/selftests/lib.mk                     |    4 +
 .../testing/selftests/membarrier/membarrier_test.c |  235 +++-
 tools/testing/selftests/rseq/.gitignore            |    4 +
 tools/testing/selftests/rseq/Makefile              |   23 +
 .../testing/selftests/rseq/basic_percpu_ops_test.c |  333 +++++
 tools/testing/selftests/rseq/basic_test.c          |   55 +
 tools/testing/selftests/rseq/param_test.c          | 1285 ++++++++++++++++++++
 tools/testing/selftests/rseq/rseq-arm.h            |  568 +++++++++
 tools/testing/selftests/rseq/rseq-ppc.h            |  567 +++++++++
 tools/testing/selftests/rseq/rseq-x86.h            |  898 ++++++++++++++
 tools/testing/selftests/rseq/rseq.c                |  116 ++
 tools/testing/selftests/rseq/rseq.h                |  154 +++
 tools/testing/selftests/rseq/run_param_test.sh     |  124 ++
 59 files changed, 8149 insertions(+), 63 deletions(-)
 create mode 100644 arch/powerpc/include/asm/membarrier.h
 create mode 100644 include/trace/events/rseq.h
 create mode 100644 include/uapi/linux/cpu_opv.h
 create mode 100644 include/uapi/linux/rseq.h
 create mode 100644 kernel/cpu_opv.c
 create mode 100644 kernel/rseq.c
 create mode 100644 tools/testing/selftests/cpu-opv/.gitignore
 create mode 100644 tools/testing/selftests/cpu-opv/Makefile
 create mode 100644 tools/testing/selftests/cpu-opv/basic_cpu_opv_test.c
 create mode 100644 tools/testing/selftests/cpu-opv/cpu-op.c
 create mode 100644 tools/testing/selftests/cpu-opv/cpu-op.h
 create mode 100644 tools/testing/selftests/rseq/.gitignore
 create mode 100644 tools/testing/selftests/rseq/Makefile
 create mode 100644 tools/testing/selftests/rseq/basic_percpu_ops_test.c
 create mode 100644 tools/testing/selftests/rseq/basic_test.c
 create mode 100644 tools/testing/selftests/rseq/param_test.c
 create mode 100644 tools/testing/selftests/rseq/rseq-arm.h
 create mode 100644 tools/testing/selftests/rseq/rseq-ppc.h
 create mode 100644 tools/testing/selftests/rseq/rseq-x86.h
 create mode 100644 tools/testing/selftests/rseq/rseq.c
 create mode 100644 tools/testing/selftests/rseq/rseq.h
 create mode 100755 tools/testing/selftests/rseq/run_param_test.sh

2.11.0

Expose a new system call allowing each thread to register one userspace memory area to be used as an ABI between kernel and user-space for two
purposes: user-space restartable sequences and quick access to read the current CPU number value from user-space.

* Restartable sequences (per-cpu atomics)

Restartables sequences allow user-space to perform update operations on per-cpu data without requiring heavy-weight atomic operations.

The restartable critical sections (percpu atomics) work has been started by Paul Turner and Andrew Hunter. It lets the kernel handle restart of critical sections. [1] [2] The re-implementation proposed here brings a few simplifications to the ABI which facilitates porting to other architectures and speeds up the user-space fast path. A second system call, cpu_opv(), is proposed as fallback to deal with debugger single-stepping. cpu_opv() executes a sequence of operations on behalf of user-space with preemption disabled.

Here are benchmarks of various rseq use-cases.

Test hardware:

arm32: ARMv7 Processor rev 4 (v7l) "Cubietruck", 2-core
x86-64: Intel E5-2630 [email protected], 16-core, hyperthreading

The following benchmarks were all performed on a single thread.

* Per-CPU statistic counter increment

getcpu+atomic (ns/op) rseq (ns/op) speedup

arm32:                344.0                 31.4          11.0
x86-64:                15.3                  2.0           7.7

* LTTng-UST: write event 32-bit header, 32-bit payload into tracer per-cpu buffer

getcpu+atomic (ns/op) rseq (ns/op) speedup

arm32:               2502.0                 2250.0         1.1
x86-64:               117.4                   98.0         1.2

* liburcu percpu: lock-unlock pair, dereference, read/compare word

getcpu+atomic (ns/op) rseq (ns/op) speedup

arm32:                751.0                 128.5          5.8
x86-64:                53.4                  28.6          1.9

* jemalloc memory allocator adapted to use rseq

Using rseq with per-cpu memory pools in jemalloc at Facebook (based on rseq 2016 implementation):

The production workload response-time has 1-2% gain avg. latency, and the P99 overall latency drops by 2-3%.

* Reading the current CPU number

Speeding up reading the current CPU number on which the caller thread is running is done by keeping the current CPU number up do date within the cpu_id field of the memory area registered by the thread. This is done by making scheduler preemption set the TIF_NOTIFY_RESUME flag on the current thread. Upon return to user-space, a notify-resume handler updates the current CPU value within the registered user-space memory area. User-space can then read the current CPU number directly from memory.

Keeping the current cpu id in a memory area shared between kernel and user-space is an improvement over current mechanisms available to read the current CPU number, which has the following benefits over alternative approaches:

- 35x speedup on ARM vs system call through glibc
- 20x speedup on x86 compared to calling glibc, which calls vdso executing a "lsl" instruction,
- 14x speedup on x86 compared to inlined "lsl" instruction,
- Unlike vdso approaches, this cpu_id value can be read from an inline assembly, which makes it a useful building block for restartable sequences.
- The approach of reading the cpu id through memory mapping shared between kernel and user-space is portable (e.g. ARM), which is not the case for the lsl-based x86 vdso.

On x86, yet another possible approach would be to use the gs segment selector to point to user-space per-cpu data. This approach performs similarly to the cpu id cache, but it has two disadvantages: it is not portable, and it is incompatible with existing applications already using the gs segment selector for other purposes.

Benchmarking various approaches for reading the current CPU number:

ARMv7 Processor rev 4 (v7l)
Machine model: Cubietruck
- Baseline (empty loop): 8.4 ns
- Read CPU from rseq cpu_id: 16.7 ns
- Read CPU from rseq cpu_id (lazy register): 19.8 ns
- glibc 2.19-0ubuntu6.6 getcpu: 301.8 ns
- getcpu system call: 234.9 ns

x86-64 Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz:

- Baseline (empty loop):                                    0.8 ns
- Read CPU from rseq cpu_id:                                0.8 ns
- Read CPU from rseq cpu_id (lazy register):                0.8 ns
- Read using gs segment selector:                           0.8 ns
- "lsl" inline assembly:                                   13.0 ns
- glibc 2.19-0ubuntu6 getcpu:                              16.6 ns
- getcpu system call:                                      53.9 ns

- Speed (benchmark taken on v8 of patchset)

Running 10 runs of hackbench -l 100000 seems to indicate, contrary to expectations, that enabling CONFIG_RSEQ slightly accelerates the scheduler:

Configuration: 2 sockets * 8-core Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz (directly on hardware, hyperthreading disabled in BIOS, energy saving disabled in BIOS, turboboost disabled in BIOS, cpuidle.off=1 kernel parameter), with a Linux v4.6 defconfig+localyesconfig, restartable sequences series applied.

* CONFIG_RSEQ=n

avg.:      41.37 s
std.dev.:   0.36 s

* CONFIG_RSEQ=y

avg.:      40.46 s
std.dev.:   0.33 s

- Size

On x86-64, between CONFIG_RSEQ=n/y, the text size increase of vmlinux is 567 bytes, and the data size increase of vmlinux is 5696 bytes.

On x86-64, between CONFIG_CPU_OPV=n/y, the text size increase of vmlinux is 5576 bytes, and the data size increase of vmlinux is 6164 bytes.

[1] https://lwn.net/Articles/650333/
[2] http://www.linuxplumbersconf.org/2013/ocw/system/presentations/1695/original/LPC%20-%20PerCpu%20Atomics.pdf

---

Changes since v1:
- Return -1, errno=EINVAL if cpu_cache pointer is not aligned on sizeof(int32_t).
- Update man page to describe the pointer alignement requirements and update atomicity guarantees.
- Add MAINTAINERS file GETCPU_CACHE entry.
- Remove dynamic memory allocation: go back to having a single getcpu_cache entry per thread. Update documentation accordingly.
- Rebased on Linux 4.4.

Changes since v2:
- Introduce a "cmd" argument, along with an enum with GETCPU_CACHE_GET and GETCPU_CACHE_SET. Introduce a uapi header linux/getcpu_cache.h defining this enumeration.
- Split resume notifier architecture implementation from the system call wire up in the following arch-specific patches.
- Man pages updates.
- Handle 32-bit compat pointers.
- Simplify handling of getcpu_cache GETCPU_CACHE_SET compiler barrier:
set the current cpu cache pointer before doing the cache update, and set it back to NULL if the update fails. Setting it back to NULL on error ensures that no resume notifier will trigger a SIGSEGV if a migration happened concurrently.

Changes since v3:
- Fix __user annotations in compat code,
- Update memory ordering comments.
- Rebased on kernel v4.5-rc5.

Changes since v4:
- Inline getcpu_cache_fork, getcpu_cache_execve, and getcpu_cache_exit.
- Add new line between if() and switch() to improve readability.
- Added sched switch benchmarks (hackbench) and size overhead comparison to change log.

Changes since v5:
- Rename "getcpu_cache" to "thread_local_abi", allowing to extend this system call to cover future features such as restartable critical sections. Generalizing this system call ensures that we can add features similar to the cpu_id field within the same cache-line without having to track one pointer per feature within the task struct.
- Add a tlabi_nr parameter to the system call, thus allowing to extend the ABI beyond the initial 64-byte structure by registering structures with tlabi_nr greater than 0. The initial ABI structure is associated with tlabi_nr 0.
- Rebased on kernel v4.5.

Changes since v6:
- Integrate "restartable sequences" v2 patchset from Paul Turner.
- Add handling of single-stepping purely in user-space, with a fallback to locking after 2 rseq failures to ensure progress, and by exposing a __rseq_table section to debuggers so they know where to put breakpoints when dealing with rseq assembly blocks which can be aborted at any point.
- make the code and ABI generic: porting the kernel implementation simply requires to wire up the signal handler and return to user-space hooks, and allocate the syscall number.
- extend testing with a fully configurable test program. See param_spinlock_test -h for details.
- handling of rseq ENOSYS in user-space, also with a fallback to locking.
- modify Paul Turner's rseq ABI to only require a single TLS store on the user-space fast-path, removing the need to populate two additional registers. This is made possible by introducing struct rseq_cs into the ABI to describe a critical section start_ip, post_commit_ip, and abort_ip.
- Rebased on kernel v4.7-rc7.

Changes since v7:
- Documentation updates.
- Integrated powerpc architecture support.
- Compare rseq critical section start_ip, allows shriking the user-space fast-path code size.
- Added Peter Zijlstra, Paul E. McKenney and Boqun Feng as co-maintainers.
- Added do_rseq2 and do_rseq_memcpy to test program helper library.
- Code cleanup based on review from Peter Zijlstra, Andy Lutomirski and Boqun Feng.
- Rebase on kernel v4.8-rc2.

Changes since v8:
- clear rseq_cs even if non-nested. Speeds up user-space fast path by removing the final "rseq_cs=NULL" assignment.
- add enum rseq_flags: critical sections and threads can set migration, preemption and signal "disable" flags to inhibit rseq behavior.
- rseq_event_counter needs to be updated with a pre-increment: Otherwise misses an increment after exec (when TLS and in-kernel states are initially 0).

Changes since v9:
- Update changelog.
- Fold instrumentation patch.
- check abort-ip signature: Add a signature before the abort-ip landing address. This signature is also received as a new parameter to the rseq system call. The kernel uses it ensures that rseq cannot be used as an exploit vector to redirect execution to arbitrary code.
- Use rseq pointer for both register and unregister. This is more symmetric, and eventually allow supporting a linked list of rseq struct per thread if needed in the future.
- Unregistration of a rseq structure is now done with RSEQ_FLAG_UNREGISTER.
- Remove reference counting. Return "EBUSY" to the caller if rseq is already registered for the current thread. This simplifies implementation while still allowing user-space to perform lazy registration in multi-lib use-cases. (suggested by Ben Maurer)
- Clear rseq_cs upon unregister.
- Set cpu_id back to -1 on unregister, so if rseq user libraries follow an unregister, and they expect to lazily register rseq, they can do so.
- Document rseq_cs clear requirement: JIT should reset the rseq_cs pointer before reclaiming memory of rseq_cs structure.
- Introduce rseq_len syscall parameter, rseq_cs version field:
Allow keeping track of the registered rseq struct length, for future extensions. Add rseq_cs version as first field. Will allow future extensions.
- Use offset and unsigned arithmetic to save a branch: Save a conditional branch when comparing instruction pointer against a rseq_cs descriptor's address range by having post_commit_ip as an offset from start_ip, and using unsigned integer comparison. Suggested by Ben Maurer.
- Remove event counter from ABI. Suggested by Andy Lutomirski.
- Add INIT_ONSTACK macro: Introduce the RSEQ_FIELD_u32_u64_INIT_ONSTACK() macros to ensure that users correctly initialize the upper bits of RSEQ_FIELD_u32_u64() on their stack to 0 on 32-bit architectures.
- Select MEMBARRIER: Allows user-space rseq fast-paths to use the value of cpu_id field (inherently required by the rseq algorithm) to figure out whether membarrier can be expected to be available. This effectively allows user-space fast-paths to remove extra comparisons and branch testing whether membarrier is enabled, and thus whether a full barrier is required (e.g. in userspace RCU implementation after rcu_read_lock/before rcu_read_unlock).
- Expose cpu_id_start field: Checking whether the (cpu_id < 0) in the C preparation part of the rseq fast-path brings significant overhead at least on arm32. We can remove this extra comparison by exposing two distinct cpu_id fields in the rseq TLS:

The field cpu_id_start always contain a *possible* cpu number, although it may not be the current one if, for instance, rseq is not initialized for the current thread. cpu_id_start is meant to be used in the C code for the pointer chasing to figure out which per-cpu data structure should be passed to the rseq asm sequence.

The field cpu_id values -1 means rseq is not initialized, and -2 means initialization failed. That field is used in the rseq asm sequence to confirm that the cpu_id_start value was indeed the current cpu number. It also ends up confirming that rseq is initialized for the current thread, because values -1 and -2 will never match the cpu_id_start possible cpu number values.

This allows checking the current CPU number and rseq initialization state with a single comparison on the fast-path.

Changes since v10:

- Update rseq.c comment, removing reference to event_counter.

Man page associated:

RSEQ(2) Linux Programmer's Manual RSEQ(2)

NAME
rseq - Restartable sequences and cpu number cache

SYNOPSIS

       #include <linux/rseq.h>

       int rseq(struct rseq * rseq, uint32_t rseq_len, int flags, uint32_t sig);

DESCRIPTION
The rseq() ABI accelerates user-space operations on per-cpu data by defining a shared data structure ABI between each user- space thread and the kernel.

It allows user-space to perform update operations on per-cpu data without requiring heavy-weight atomic operations.

Restartable sequences are atomic with respect to preemption (making it atomic with respect to other threads running on the same CPU), as well as signal delivery (user-space execution contexts nested over the same thread).

It is suited for update operations on per-cpu data.

It can be used on data structures shared between threads within a process, and on data structures shared between threads across different processes.

Some examples of operations that can be accelerated or improved by this ABI:

· Memory allocator per-cpu free-lists,

· Querying the current CPU number,

· Incrementing per-CPU counters,

· Modifying data protected by per-CPU spinlocks,

· Inserting/removing elements in per-CPU linked-lists,

· Writing/reading per-CPU ring buffers content.

· Accurately reading performance monitoring unit counters with
respect to thread migration.

The rseq argument is a pointer to the thread-local rseq struc‐ ture to be shared between kernel and user-space. A NULL rseq value unregisters the current thread rseq structure.

The layout of struct rseq is as follows:

Structure alignment
This structure is aligned on multiples of 32 bytes.

Structure size
This structure is extensible. Its size is passed as parameter to the rseq system call.

Fields

cpu_id_start
Optimistic cache of the CPU number on which the current thread is running. Its value is guaranteed to always be a possible CPU number, even when rseq is not initial‐ ized. The value it contains should always be confirmed by reading the cpu_id field.

cpu_id
Cache of the CPU number on which the current thread is running. -1 if uninitialized.

rseq_cs
The rseq_cs field is a pointer to a struct rseq_cs. Is is NULL when no rseq assembly block critical section is active for the current thread. Setting it to point to a critical section descriptor (struct rseq_cs) marks the beginning of the critical section.

flags
Flags indicating the restart behavior for the current thread. This is mainly used for debugging purposes. Can be either:

· RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT

· RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL

· RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE

The layout of struct rseq_cs version 0 is as follows:

Structure alignment
This structure is aligned on multiples of 32 bytes.

Structure size
This structure has a fixed size of 32 bytes.

Fields

version
Version of this structure.

flags
Flags indicating the restart behavior of this structure. Can be either:

· RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT

· RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL

· RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE

start_ip
Instruction pointer address of the first instruction of the sequence of consecutive assembly instructions.

post_commit_offset
Offset (from start_ip address) of the address after the last instruction of the sequence of consecutive assembly instructions.

abort_ip
Instruction pointer address where to move the execution flow in case of abort of the sequence of consecutive assembly instructions.

The rseq_len argument is the size of the struct rseq to regis‐ ter.

The flags argument is 0 for registration, and RSEQ_FLAG_UNREG‐ ISTER for unregistration.

The sig argument is the 32-bit signature to be expected before the abort handler code.

A single library per process should keep the rseq structure in a thread-local storage variable. The cpu_id field should be initialized to -1, and the cpu_id_start field should be ini‐ tialized to a possible CPU value (typically 0).

Each thread is responsible for registering and unregistering its rseq structure. No more than one rseq structure address can be registered per thread at a given time.

In a typical usage scenario, the thread registering the rseq structure will be performing loads and stores from/to that structure. It is however also allowed to read that structure from other threads. The rseq field updates performed by the kernel provide relaxed atomicity semantics, which guarantee that other threads performing relaxed atomic reads of the cpu number cache will always observe a consistent value.

RETURN VALUE
A return value of 0 indicates success. On error, -1 is returned, and errno is set appropriately.

ERRORS
EINVAL Either flags contains an invalid value, or rseq contains
an address which is not appropriately aligned, or rseq_len contains a size that does not match the size received on registration.

ENOSYS The rseq() system call is not implemented by this ker‐
nel.

EFAULT rseq is an invalid address.

EBUSY Restartable sequence is already registered for this
thread.

EPERM The sig argument on unregistration does not match the
signature received on registration.

VERSIONS
The rseq() system call was added in Linux 4.X (TODO).

CONFORMING TO
rseq() is Linux-specific.

SEE ALSO

       sched_getcpu(3)

Linux 2017-11-06 RSEQ(2)

---
 MAINTAINERS                 |  11 ++
 arch/Kconfig                |   7 +
 fs/exec.c                   |   1 +
 include/linux/sched.h       |  89 ++++++++++++
 include/trace/events/rseq.h |  60 ++++++++
 include/uapi/linux/rseq.h   | 138 +++++++++++++++++++
 init/Kconfig                |  14 ++
 kernel/Makefile             |   1 +
 kernel/fork.c               |   2 +
 kernel/rseq.c               | 328 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/core.c         |   4 +
 kernel/sys_ni.c             |   3 +
 12 files changed, 658 insertions(+)
 create mode 100644 include/trace/events/rseq.h
 create mode 100644 include/uapi/linux/rseq.h
 create mode 100644 kernel/rseq.c

index 2811a211632c..c9f95f8b07ed 100644
@@ -11497,6 +11497,17 @@ F:	include/dt-bindings/reset/
 F:	include/linux/reset.h
 F:	include/linux/reset-controller.h
 
+RESTARTABLE SEQUENCES SUPPORT
+M:	Mathieu Desnoyers <mathieu.desnoyers-vg+e7yoeK/dWk0Htik3J/[email protected]>
+M:	Peter Zijlstra <[email protected]>
+M:	"Paul E. McKenney" <[email protected]>
+M:	Boqun Feng <[email protected]>
+L:	[email protected]
+S:	Supported
+F:	kernel/rseq.c
+F:	include/uapi/linux/rseq.h
+F:	include/trace/events/rseq.h
+
 RFKILL
 M:	Johannes Berg <[email protected]>
 L:	[email protected]

index 057370a0ac4e..b5e7f977fc29 100644
@@ -258,6 +258,13 @@ config HAVE_REGS_AND_STACK_ACCESS_API
 	  declared in asm/ptrace.h
 	  For example the kprobes-based event tracer needs this API.
 
+config HAVE_RSEQ
+	bool
+	depends on HAVE_REGS_AND_STACK_ACCESS_API
+	help
+	  This symbol should be selected by an architecture if it
+	  supports an implementation of restartable sequences.
+
 config HAVE_CLK
 	bool
 	help

index 3e14ba25f678..3faf8ff0fc6d 100644
@@ -1803,6 +1803,7 @@ static int do_execveat_common(int fd, struct filename *filename,
 	current->fs->in_exec = 0;
 	current->in_execve = 0;
 	membarrier_execve(current);
+	rseq_execve(current);
 	acct_update_integrals(current);
 	task_numa_free(current);
 	free_bprm(bprm);

index 3c1faaa2af4a..cbedfb91b40a 100644
@@ -1400,6 +1400,20 @@ config MEMBARRIER
 
 	  If unsure, say Y.
 
+config RSEQ
+	bool "Enable rseq() system call" if EXPERT
+	default y
+	depends on HAVE_RSEQ
+	select MEMBARRIER
+	help
+	  Enable the restartable sequences system call. It provides a
+	  user-space cache for the current CPU number value, which
+	  speeds up getting the current CPU number from user-space,
+	  as well as an ABI to speed up user-space operations on
+	  per-CPU data.
+
+	  If unsure, say Y.
+
 config EMBEDDED
 	bool "Embedded system"
 	option allnoconfig_y

index 172d151d429c..3574669dafd9 100644
@@ -112,6 +112,7 @@ obj-$(CONFIG_CONTEXT_TRACKING) += context_tracking.o
 obj-$(CONFIG_TORTURE_TEST) += torture.o
 
 obj-$(CONFIG_HAS_IOMEM) += memremap.o
+obj-$(CONFIG_RSEQ) += rseq.o
 
 $(obj)/configs.o: $(obj)/config_data.h
 

index 07cc743698d3..1f3c25e28742 100644
@@ -1862,6 +1862,8 @@ static __latent_entropy struct task_struct *copy_process(
 	 */
 	copy_seccomp(p);
 
+	rseq_fork(p, clone_flags);
+
 	/*
 	 * Process group and session signals need to be delivered to just the
 	 * parent before the fork or both the parent and the child after the

index d17c5da523a0..6bba05f47e51 100644
@@ -1179,6 +1179,8 @@ void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
 	WARN_ON_ONCE(!cpu_online(new_cpu));
 #endif
 
+	rseq_migrate(p);
+
 	trace_sched_migrate_task(p, new_cpu);
 
 	if (task_cpu(p) != new_cpu) {

@@ -2581,6 +2583,7 @@ prepare_task_switch(struct rq *rq, struct task_struct *prev,
 {
 	sched_info_switch(rq, prev, next);
 	perf_event_task_sched_out(prev, next);
+	rseq_sched_out(prev);
 	fire_sched_out_preempt_notifiers(prev, next);
 	prepare_lock_switch(rq, next);
 	prepare_arch_switch(next);

@@ -3341,6 +3344,7 @@ static void __sched notrace __schedule(bool preempt)
 	clear_preempt_need_resched();
 
 	if (likely(prev != next)) {
+		rseq_preempt(prev);
 		rq->nr_switches++;
 		rq->curr = next;
 		/*

index b5189762d275..bfa1ee1bf669 100644
@@ -259,3 +259,6 @@ cond_syscall(sys_membarrier);
 cond_syscall(sys_pkey_mprotect);
 cond_syscall(sys_pkey_alloc);
 cond_syscall(sys_pkey_free);
+
+/* restartable sequence */
+cond_syscall(sys_rseq);

2.11.0

Really dumb question -- and one I'm sorry to bring up at the last minute. Should we consider making the syscall name something more generic "register_tls_abi"? I'm assuming that if we ever want to use a per-thread userspace/kernel ABI we'll want to use this field given the difficulty of getting adoption of registration, the need to involve glibc, etc. It seems like there could be future use cases of this TLS area that have nothing to do with rseq.

I proposed that approach back in 2016 ("tls abi" system call), and the feedback I received back then is that it was preferred to have a dedicated "rseq" system call than an "open ended" and generic "tls abi" system call.

Thanks,

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Ultimately I'm fine either way. I do think that in the past few months of review it has become clear that creating this tls abi requires a fair bit of work. It'd be a shame to see a future attempt to use such an ABI made difficult by forcing the author to figure out the registration process yet again. I assume the maintainers of glibc would also like to avoid the need to register multiple ABIs.

-b

(apologies for the duplicate email, the previous one bounced as it was accidentally using HTML formatting)

If I understand correctly this is run on every context switch so we probably want to make it really fast

Yes, more precisely, it runs on return to user-space, after every context switch going back to a registered rseq thread.

If we detect this situation, the rseq_need_restart caller will end up sending a SIGSEGV signal to user-space. Note that the two nested if() checks are only executing in the unlikely case where the NO_RESTART_ON_SIGNAL flag is set.

Given that those are not requests impacting the ABI presented to user-space, I'm tempted to keep these optimizations for the following 4.16 merge window. Is that ok with you ?

Thanks,

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

I should as well make all those a bitmask within a "u32 rseq_event_mask" then, sounds fair ?

Thanks,

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Sure, whatever works and isn't _Bool ;-)

So something along those lines should do the trick (including the mask request from Ben Maurer):

index b995a3b..44aef30 100644
@@ -982,7 +982,7 @@ struct task_struct {
        struct rseq __user *rseq;
        u32 rseq_len;
        u32 rseq_sig;
-       bool rseq_preempt, rseq_signal, rseq_migrate;
+       u32 rseq_event_mask;
 #endif
 
        struct tlbflush_unmap_batch     tlb_ubc;

@@ -1676,6 +1676,16 @@ static inline void set_task_cpu(struct task_struct *p, un
 #endif
 
 #ifdef CONFIG_RSEQ
+/*
+ * Map the event mask on the user-space ABI enum rseq_cs_flags
+ * for direct mask checks.
+ */
+enum rseq_event_mask {
+       RSEQ_EVENT_PREEMPT      = RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT,
+       RSEQ_EVENT_SIGNAL       = RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL,
+       RSEQ_EVENT_MIGRATE      = RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE,
+};
+
 static inline void rseq_set_notify_resume(struct task_struct *t)
 {
        if (t->rseq)

@@ -1718,16 +1728,16 @@ static inline void rseq_sched_out(struct task_struct *t)
 }
 static inline void rseq_signal_deliver(struct pt_regs *regs)
 {
-       current->rseq_signal = true;
+       current->rseq_event_mask |= RSEQ_EVENT_SIGNAL;
        rseq_handle_notify_resume(regs);
 }
 static inline void rseq_preempt(struct task_struct *t)
 {
-       t->rseq_preempt = true;
+       t->rseq_event_mask |= RSEQ_EVENT_PREEMPT;
 }
 static inline void rseq_migrate(struct task_struct *t)
 {
-       t->rseq_migrate = true;
+       t->rseq_event_mask |= RSEQ_EVENT_MIGRATE;
 }
 #else
 static inline void rseq_set_notify_resume(struct task_struct *t)

index 6f0d48c..d773003 100644
@@ -159,7 +159,7 @@ static bool rseq_get_rseq_cs(struct task_struct *t,
 static int rseq_need_restart(struct task_struct *t, uint32_t cs_flags)
 {
        bool need_restart = false;
-       uint32_t flags;
+       uint32_t flags, event_mask;
 
        /* Get thread flags. */
        if (__get_user(flags, &t->rseq->flags))

@@ -174,26 +174,17 @@ static int rseq_need_restart(struct task_struct *t, uint32
         * a preempted signal handler could fail to restart the prior
         * execution context on sigreturn.
         */
-       if (flags & RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL) {
-               if (!(flags & RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE))
-                       return -EINVAL;
-               if (!(flags & RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT))
+       if (unlikely(flags & RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL)) {
+               if ((flags & (RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE
+                               | RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT))
+                       != (RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE
+                                | RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT))
                        return -EINVAL;
        }
-       if (t->rseq_migrate
-                       && !(flags & RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE))
-               need_restart = true;
-       else if (t->rseq_preempt
-                       && !(flags & RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT))
-               need_restart = true;
-       else if (t->rseq_signal
-                       && !(flags & RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL))
-               need_restart = true;
-
-       t->rseq_preempt = false;
-       t->rseq_signal = false;
-       t->rseq_migrate = false;
-       if (need_restart)
+       event_mask = t->rseq_event_mask;
+       t->rseq_event_mask = 0;
+       event_mask &= ~flags;
+       if (event_mask)
                return 1;
        return 0;
 }

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Yes, exactly. The user-space TLS should be inherited from that of the calling thread.

At kernel-level, the only thing that's not inherited here is the task struct rseq_event_mask, which tracks whether a restart is needed. But this would only be relevant if fork() can be invoked from a signal handler, or if fork() could be invoked from a rseq critical section (which really makes little sense).

Should I copy the current->rseq_event_mask on process fork just to be on the safe side though ?

Thanks,

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Whether it makes sense or not does not matter much, especially in context of user space. You cannot make assumptions like that. When something can be done, then it's bound to happen sooner than later because somebody thinks he is extra clever.

The first priority is robustness in any aspect which has to do with user space.

I think so, unless you let fork() fail when invoked from a rseq critical section.

Thanks,

tglx

Allright, I'll set the rseq_event_mask to 0 explicitly on exec() and thread-fork, and copy it from the parent on process-fork.

Thanks,

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Yes it could, but last time I checked a __put_user of a u64 did not guarantee single-copy atomicity of each of the two 32-bit words on 32-bit architectures, so I figured that it would be better to postpone that optimization to a point where architectures would provide a u64 __put_user that guarantee single-copy atomicity of each 32-bit word on 32-bit architectures.

I can do the following on the caller side instead:

        if (!rseq_get_rseq_cs(t, &start_ip, &post_commit_offset, &abort_ip,
                        &cs_flags))
                return -EFAULT;

Yep.

ok for adding newlines.

I usually never space-align with open parenthesis "(". Is it a coding style requirement of the kernel for multi-line if () conditions ?

Would the following replatement code be ok ?

        if (unlikely(flags & RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL)) {
                if ((flags & (RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE
                                | RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT)) !=
                                (RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE
                                | RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT))
                        return -EINVAL;
        }
        event_mask = t->rseq_event_mask;
        t->rseq_event_mask = 0;
        event_mask &= ~flags;
        if (event_mask)
                return 1;
        return 0;

I'm uneasy with the wall of text caused by the flags. And based on your comment, I should align on the if ( parenthesis. Style improvement ideas are welcome. An alternative would be:

        if (unlikely(flags & RSEQ_CS_FLAG_NO_RESTART_ON_SIGNAL)) {
                if ((flags & (RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE
                    | RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT)) !=
                    (RSEQ_CS_FLAG_NO_RESTART_ON_MIGRATE
                     | RSEQ_CS_FLAG_NO_RESTART_ON_PREEMPT))
                        return -EINVAL;
        }

[...]

ok

Good point. Tracing right before instruction_pointer_set() would make sense. I can remove the "ret" parameter too.

Now that both ip and start_ip are unsigned long, I simply can do:

if (ip - start_ip >= post_commit_offset)
...

Will do, I'll use unsigned long instead,

Thanks!

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Not sure, but it is the predominant pattern in most of the code.

I really prefer the operator at the end,

git grep "&&$" | wc -l
40708

git grep "^[[:space:]]*&&" | wc -l
3901

ok

Something like this ?

#ifdef __BYTE_ORDER

# if (__BYTE_ORDER == __BIG_ENDIAN)
#  define RSEQ_BYTE_ORDER_BIG_ENDIAN
# else
#  define RSEQ_BYTE_ORDER_LITTLE_ENDIAN
# endif
#else
# ifdef __BIG_ENDIAN
#  define RSEQ_BYTE_ORDER_BIG_ENDIAN
# else
#  define RSEQ_BYTE_ORDER_LITTLE_ENDIAN
# endif
#endif

#ifdef __LP64__

# define RSEQ_FIELD_u32_u64(field)                      uint64_t field
# define RSEQ_FIELD_u32_u64_INIT_ONSTACK(field, v)      field = (intptr_t)v
#else
# ifdef RSEQ_BYTE_ORDER_BIG_ENDIAN
#  define RSEQ_FIELD_u32_u64(field)     uint32_t field ## _padding, field
#  define RSEQ_FIELD_u32_u64_INIT_ONSTACK(field, v)     \
        field ## _padding = 0, field = (intptr_t)v
# else
#  define RSEQ_FIELD_u32_u64(field)     uint32_t field, field ## _padding
#  define RSEQ_FIELD_u32_u64_INIT_ONSTACK(field, v)     \
        field = (intptr_t)v, field ## _padding = 0
# endif
#endif

I'll move the tail comments to their own line.

ok

Proposed update:

/*
* Restartable sequences cpu_id_start field. Updated by the
* kernel, and read by user-space with single-copy atomicity
* semantics. Aligned on 32-bit. Always contains a value in the
* range of possible CPUs, although the value may not be the
* actual current CPU (e.g. if rseq is not initialized). This
* CPU number value should always be compared against the value
* of the cpu_id field before performing a rseq commit or
* returning a value read from a data structure indexed using
* the cpu_id_start value.
*/
uint32_t cpu_id_start;

Update:

/*
* Restartable sequences cpu_id field. Updated by the kernel,
* and read by user-space with single-copy atomicity semantics.
* Aligned on 32-bit. Values RSEQ_CPU_ID_UNINITIALIZED and
* RSEQ_CPU_ID_REGISTRATION_FAILED have a special semantic: the
* former means "rseq uninitialized", and latter means "rseq
* initialization failed". This value is meant to be read within
* rseq critical sections and compared with the cpu_id_start
* value previously read, before performing the commit instruction,
* or read and compared with the cpu_id_start value before returning
* a value loaded from a data structure indexed using the
* cpu_id_start value.
*/
uint32_t cpu_id;

The kernel sets it back to NULL when it encounters a non-NULL ptr, independently of whether it was nesting over a rseq c.s. or not. Updating to:

* Updated by user-space, which sets the address of the currently
* active rseq_cs at the beginning of assembly instruction sequence
* block, and set to NULL by the kernel when it restarts an assembly
* instruction sequence block, as well as when the kernel detects that
* it is preempting or delivering a signal outside of the range
* targeted by the rseq_cs. Also needs to be set to NULL by user-space
* before reclaiming memory that contains the targeted struct rseq_cs.

Update:

* Read and set by the kernel with single-copy atomicity semantics.
* Set by user-space with single-copy atomicity semantics. Aligned
* on 64-bit.

If you're closely inspecting a program with single-stepping, and the user really want to single-step through the rseq c.s., those flags can be set by the user or debugger to allow this single-stepping to proceed. It's then up to the user/tool to ensure mutual exclusion with other rseq c.s. by other means. One of its uses is for implementers of rseq c.s. assembly code, where they may want to single-step through that code while ensuring consistency through other mechanisms (e.g. mutual exclusion, or running single-threaded).

Update:

 *   Steps [1]-[3] (inclusive) need to be a sequence of instructions in
 *   userspace that can handle being interrupted between any of those
 *   instructions, and then resumed to the abort_ip.

ok

Updated to:

 *                     init(rseq_cs)
 *                     cpu = TLS->rseq::cpu_id_start
 *   [1]               TLS->rseq::rseq_cs = rseq_cs
 *   [start_ip]        ----------------------------
 *   [2]               if (cpu != TLS->rseq::cpu_id)
 *                             goto abort_ip;
 *   [3]               <last_instruction_in_cs>
 *   [post_commit_ip]  ----------------------------

*
* The address of jump target abort_ip must be outside the critical
* region, i.e.:
*
* [abort_ip] < [start_ip] || [abort_ip] >= [post_commit_ip]

Actually, given that this all needs to be in an inline assembly, it makes no sense to talk about "compiler barrier" anymore. I'll update the last part.

The "[start_ip] tag moves just after the paragraph at "1.".

"Branching to abort_ip" would be better indeed.

ok

It should have been "at or after":

 *       If the sequence is preempted or interrupted by a signal
 *       at or after start_ip and before post_commit_ip, then the kernel
 *       clears TLS->__rseq_abi::rseq_cs, then resumes execution at the
 *       abort_ip.

You bring a good point. Although it has no impact in practice, the "start_ip" can indicate the address right *after* the store to rseq_cs. I'll change the documentation and user-space implementation accordingly.

Updated to:

 *       If the sequence is preempted or interrupted by a signal
 *       at or after start_ip and before post_commit_ip, then the kernel
 *       clears TLS->__rseq_abi::rseq_cs, and sets the user-space return
 *       ip to abort_ip before returning to user-space, so the preempted
 *       execution resumes at abort_ip.

I use abort_ip everywhere. Not sure where you saw "fail_ip".

I'll add the following enum to uapi rseq.h:

enum rseq_cpu_id_state {
RSEQ_CPU_ID_UNINITIALIZED = -1,
RSEQ_CPU_ID_REGISTRATION_FAILED = -2,
};

And use it both in the user-space library and in the kernel "reset" code.

ok, fixed.

done.

ok

moving all return values to "int", and propagating result.

done

Updating to:

        /*
         * The rseq_cs field is set to NULL on preemption or signal
         * delivery on top of rseq assembly block, as well as on top
         * of code outside of the rseq assembly block. This performs
         * a lazy clear of the rseq_cs field.
         *
         * Set rseq_cs to NULL with single-copy atomicity.
         */
        ptr = 0;
        ret = __put_user(ptr, &t->rseq->rseq_cs);
        if (ret)
                return ret;

All the discussion about not fixing up while executing signal handler was relevant with Paul Turner's original approach, but now that we have rseq critical section descriptors that contain the start_ip and post_commit_offset, guaranteeing that the rseq_cs pointer is cleared before returning to a signal handler is not relevant anymore.

I'll use __put_user rather than clear_user() in order to be consistent with all other updates that provide single-copy atomicity guarantees.

ok

I'll add this check to ensure that abort_ip is not within the rseq c.s., which would be invalid:

        /* Ensure that abort_ip is not in the critical section. */
        if (rseq_cs.abort_ip - rseq_cs.start_ip < rseq_cs.post_commit_offset)
                return false;

Following peterz' advice, I use unsigned long type now.

ok

I don't think xor is the operation we want here. But yes, using masks tremendously simplifies the code. I did those changes following peterz' feedback:

        event_mask = t->rseq_event_mask;
        t->rseq_event_mask = 0;
        event_mask &= ~flags;
        if (event_mask)
                return 1;
        return 0;

yes.

Changed to an "int".

Changed to "int", returning the callee return value.

done. It becomes:

        ret = rseq_need_restart(t, cs_flags);
        if (ret <= 0)
                return ret;

done as per peterz's feedback.

Yes, must.

done

ok. Will do:

                /* Already registered. */
                return -EBUSY; 

ok

Thanks a lot for the thorough review Thomas !!

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Call the rseq_handle_notify_resume() function on return to userspace if TIF_NOTIFY_RESUME thread flag is set.

Increment the event counter and perform fixup on the pre-signal frame when a signal is delivered on top of a restartable sequence critical section.

---
 arch/arm/Kconfig         | 1 +
 arch/arm/kernel/signal.c | 7 +++++++
 2 files changed, 8 insertions(+)

index d1346a160760..1469f3f39475 100644
@@ -87,6 +87,7 @@ config ARM
 	select HAVE_PERF_USER_STACK_DUMP
 	select HAVE_RCU_TABLE_FREE if (SMP && ARM_LPAE)
 	select HAVE_REGS_AND_STACK_ACCESS_API
+	select HAVE_RSEQ
 	select HAVE_SYSCALL_TRACEPOINTS
 	select HAVE_UID16
 	select HAVE_VIRT_CPU_ACCOUNTING_GEN

index b67ae12503f3..cc3260f475b0 100644
@@ -518,6 +518,12 @@ static void handle_signal(struct ksignal *ksig, struct pt_regs *regs)
 	int ret;
 
 	/*
+	 * Increment event counter and perform fixup for the pre-signal
+	 * frame.
+	 */
+	rseq_signal_deliver(regs);
+
+	/*
 	 * Set up the stack frame
 	 */
 	if (ksig->ka.sa.sa_flags & SA_SIGINFO)

@@ -637,6 +643,7 @@ do_work_pending(struct pt_regs *regs, unsigned int thread_flags, int syscall)
 			} else {
 				clear_thread_flag(TIF_NOTIFY_RESUME);
 				tracehook_notify_resume(regs);
+				rseq_handle_notify_resume(regs);
 			}
 		}
 		local_irq_disable();

2.11.0

Wire up the rseq system call on 32-bit ARM.

This provides an ABI improving the speed of a user-space getcpu operation on ARM by skipping the getcpu system call on the fast path, as well as improving the speed of user-space operations on per-cpu data compared to using load-linked/store-conditional.

---
 arch/arm/tools/syscall.tbl | 1 +
 1 file changed, 1 insertion(+)

index 0bb0e9c6376c..fbc74b5fa3ed 100644
@@ -412,3 +412,4 @@
 395	common	pkey_alloc		sys_pkey_alloc
 396	common	pkey_free		sys_pkey_free
 397	common	statx			sys_statx
+398	common	rseq			sys_rseq

2.11.0

Call the rseq_handle_notify_resume() function on return to userspace if TIF_NOTIFY_RESUME thread flag is set.

Increment the event counter and perform fixup on the pre-signal frame when a signal is delivered on top of a restartable sequence critical section.

---
 arch/x86/Kconfig         | 1 +
 arch/x86/entry/common.c  | 1 +
 arch/x86/kernel/signal.c | 6 ++++++
 3 files changed, 8 insertions(+)

index 2fdb23313dd5..01f78c1d40b5 100644
@@ -173,6 +173,7 @@ config X86
 	select HAVE_REGS_AND_STACK_ACCESS_API
 	select HAVE_RELIABLE_STACKTRACE		if X86_64 && FRAME_POINTER_UNWINDER && STACK_VALIDATION
 	select HAVE_STACK_VALIDATION		if X86_64
+	select HAVE_RSEQ
 	select HAVE_SYSCALL_TRACEPOINTS
 	select HAVE_UNSTABLE_SCHED_CLOCK
 	select HAVE_USER_RETURN_NOTIFIER

index 03505ffbe1b6..4c717bdd1139 100644
@@ -160,6 +160,7 @@ static void exit_to_usermode_loop(struct pt_regs *regs, u32 cached_flags)
 		if (cached_flags & _TIF_NOTIFY_RESUME) {
 			clear_thread_flag(TIF_NOTIFY_RESUME);
 			tracehook_notify_resume(regs);
+			rseq_handle_notify_resume(regs);
 		}
 
 		if (cached_flags & _TIF_USER_RETURN_NOTIFY)

index b9e00e8f1c9b..991017d26d00 100644
@@ -687,6 +687,12 @@ setup_rt_frame(struct ksignal *ksig, struct pt_regs *regs)
 	sigset_t *set = sigmask_to_save();
 	compat_sigset_t *cset = (compat_sigset_t *) set;
 
+	/*
+	 * Increment event counter and perform fixup for the pre-signal
+	 * frame.
+	 */
+	rseq_signal_deliver(regs);
+
 	/* Set up the stack frame */
 	if (is_ia32_frame(ksig)) {
 		if (ksig->ka.sa.sa_flags & SA_SIGINFO)

2.11.0

On Tue, 14 Nov 2017, Mathieu Desnoyers wrote:

Please fix the subject line:

x86: Add support for restartable sequences

or something like that.

And for the actual rseq patches please come up with a proper short susbsytem prefix for restartable sequences. There is no point in occupying half of the subject space for a prefix.

Other than that.

ok. done.

Thanks! Should I apply the reviewed-by only to the x86 patches, or patch 01 (rseq: Introduce restartable sequences system call) as well ?

Thanks,

Mathieu

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

This one of course. I've certainly not yet reviewed your next version :)

Wire up the rseq system call on x86 32/64.

This provides an ABI improving the speed of a user-space getcpu operation on x86 by removing the need to perform a function call, "lsl" instruction, or system call on the fast path, as well as improving the speed of user-space operations on per-cpu data.

---
 arch/x86/entry/syscalls/syscall_32.tbl | 1 +
 arch/x86/entry/syscalls/syscall_64.tbl | 1 +
 2 files changed, 2 insertions(+)

index 448ac2161112..ba43ee75e425 100644
@@ -391,3 +391,4 @@
 382	i386	pkey_free		sys_pkey_free
 383	i386	statx			sys_statx
 384	i386	arch_prctl		sys_arch_prctl			compat_sys_arch_prctl
+385	i386	rseq			sys_rseq

index 5aef183e2f85..3ad03495bbb9 100644
@@ -339,6 +339,7 @@
 330	common	pkey_alloc		sys_pkey_alloc
 331	common	pkey_free		sys_pkey_free
 332	common	statx			sys_statx
+333	common	rseq			sys_rseq
 
 #
 # x32-specific system call numbers start at 512 to avoid cache impact

2.11.0

From: Boqun Feng <[email protected]>

Call the rseq_handle_notify_resume() function on return to userspace if TIF_NOTIFY_RESUME thread flag is set.

Increment the event counter and perform fixup on the pre-signal when a signal is delivered on top of a restartable sequence critical section.

---
 arch/powerpc/Kconfig         | 1 +
 arch/powerpc/kernel/signal.c | 3 +++
 2 files changed, 4 insertions(+)

index cb782ac1c35d..41d1dae3b1b5 100644
@@ -219,6 +219,7 @@ config PPC
 	select HAVE_SYSCALL_TRACEPOINTS
 	select HAVE_VIRT_CPU_ACCOUNTING
 	select HAVE_IRQ_TIME_ACCOUNTING
+	select HAVE_RSEQ
 	select IRQ_DOMAIN
 	select IRQ_FORCED_THREADING
 	select MODULES_USE_ELF_RELA

index e9436c5e1e09..17a994b801b1 100644
@@ -133,6 +133,8 @@ static void do_signal(struct task_struct *tsk)
 	/* Re-enable the breakpoints for the signal stack */
 	thread_change_pc(tsk, tsk->thread.regs);
 
+	rseq_signal_deliver(tsk->thread.regs);
+
 	if (is32) {
         	if (ksig.ka.sa.sa_flags & SA_SIGINFO)
 			ret = handle_rt_signal32(&ksig, oldset, tsk);

@@ -161,6 +163,7 @@ void do_notify_resume(struct pt_regs *regs, unsigned long thread_info_flags)
 	if (thread_info_flags & _TIF_NOTIFY_RESUME) {
 		clear_thread_flag(TIF_NOTIFY_RESUME);
 		tracehook_notify_resume(regs);
+		rseq_handle_notify_resume(regs);
 	}
 
 	if (thread_info_flags & _TIF_PATCH_PENDING)

2.11.0

From: Boqun Feng <[email protected]>

Wire up the rseq system call on powerpc.

This provides an ABI improving the speed of a user-space getcpu operation on powerpc by skipping the getcpu system call on the fast path, as well as improving the speed of user-space operations on per-cpu data compared to using load-reservation/store-conditional atomics.

---
 arch/powerpc/include/asm/systbl.h      | 1 +
 arch/powerpc/include/asm/unistd.h      | 2 +-
 arch/powerpc/include/uapi/asm/unistd.h | 1 +
 3 files changed, 3 insertions(+), 1 deletion(-)

index 449912f057f6..964321a5799c 100644
@@ -389,3 +389,4 @@ COMPAT_SYS_SPU(preadv2)
 COMPAT_SYS_SPU(pwritev2)
 SYSCALL(kexec_file_load)
 SYSCALL(statx)
+SYSCALL(rseq)

index 9ba11dbcaca9..e76bd5601ea4 100644
@@ -12,7 +12,7 @@
 #include <uapi/asm/unistd.h>
 
 
-#define NR_syscalls		384
+#define NR_syscalls		385
 
 #define __NR__exit __NR_exit
 

index df8684f31919..b1980fcd56d5 100644
@@ -395,5 +395,6 @@
 #define __NR_pwritev2		381
 #define __NR_kexec_file_load	382
 #define __NR_statx		383
+#define __NR_rseq		384
 
 #endif /* _UAPI_ASM_POWERPC_UNISTD_H_ */

2.11.0

This new cpu_opv system call executes a vector of operations on behalf of user-space on a specific CPU with preemption disabled. It is inspired from readv() and writev() system calls which take a "struct iovec" array as argument.

The operations available are: comparison, memcpy, add, or, and, xor, left shift, right shift, and mb. The system call receives a CPU number from user-space as argument, which is the CPU on which those operations need to be performed. All preparation steps such as loading pointers, and applying offsets to arrays, need to be performed by user-space before invoking the system call. The "comparison" operation can be used to check that the data used in the preparation step did not change between preparation of system call inputs and operation execution within the preempt-off critical section.

The reason why we require all pointer offsets to be calculated by user-space beforehand is because we need to use get_user_pages_fast() to first pin all pages touched by each operation. This takes care of faulting-in the pages. Then, preemption is disabled, and the operations are performed atomically with respect to other thread execution on that CPU, without generating any page fault.

A maximum limit of 16 operations per cpu_opv syscall invocation is enforced, so user-space cannot generate a too long preempt-off critical section. Each operation is also limited a length of PAGE_SIZE bytes, meaning that an operation can touch a maximum of 4 pages (memcpy: 2 pages for source, 2 pages for destination if addresses are not aligned on page boundaries). Moreover, a total limit of 4216 bytes is applied to operation lengths.

If the thread is not running on the requested CPU, a new push_task_to_cpu() is invoked to migrate the task to the requested CPU. If the requested CPU is not part of the cpus allowed mask of the thread, the system call fails with EINVAL. After the migration has been performed, preemption is disabled, and the current CPU number is checked again and compared to the requested CPU number. If it still differs, it means the scheduler migrated us away from that CPU. Return EAGAIN to user-space in that case, and let user-space retry (either requesting the same CPU number, or a different one, depending on the user-space algorithm constraints).

---

Changes since v1:
- handle CPU hotplug,
- cleanup implementation using function pointers: We can use function pointers to implement the operations rather than duplicating all the user-access code.
- refuse device pages: Performing cpu_opv operations on io map'd pages with preemption disabled could generate long preempt-off critical sections, which leads to unwanted scheduler latency. Return EFAULT if a device page is received as parameter
- restrict op vector to 4216 bytes length sum: Restrict the operation vector to length sum of:
- 4096 bytes (typical page size on most architectures, should be enough for a string, or structures)
- 15 * 8 bytes (typical operations on integers or pointers). The goal here is to keep the duration of preempt off critical section short, so we don't add significant scheduler latency.
- Add INIT_ONSTACK macro: Introduce the CPU_OP_FIELD_u32_u64_INIT_ONSTACK() macros to ensure that users correctly initialize the upper bits of CPU_OP_FIELD_u32_u64() on their stack to 0 on 32-bit architectures.
- Add CPU_MB_OP operation:
Use-cases with:
- two consecutive stores,
- a mempcy followed by a store,
require a memory barrier before the final store operation. A typical use-case is a store-release on the final store. Given that this is a slow path, just providing an explicit full barrier instruction should be sufficient.
- Add expect fault field:
The use-case of list_pop brings interesting challenges. With rseq, we can use rseq_cmpnev_storeoffp_load(), and therefore load a pointer, compare it against NULL, add an offset, and load the target "next" pointer from the object, all within a single req critical section.

Life is not so easy for cpu_opv in this use-case, mainly because we need to pin all pages we are going to touch in the preempt-off critical section beforehand. So we need to know the target object (in which we apply an offset to fetch the next pointer) when we pin pages before disabling preemption.

So the approach is to load the head pointer and compare it against NULL in user-space, before doing the cpu_opv syscall. User-space can then compute the address of the head->next field, *without loading it*.

The cpu_opv system call will first need to pin all pages associated with input data. This includes the page backing the head->next object, which may have been concurrently deallocated and unmapped. Therefore, in this case, getting -EFAULT when trying to pin those pages may
happen: it just means they have been concurrently unmapped. This is an expected situation, and should just return -EAGAIN to user-space, to user-space can distinguish between "should retry" type of situations and actual errors that should be handled with extreme prejudice to the program (e.g. abort()).

Therefore, add "expect_fault" fields along with op input address pointers, so user-space can identify whether a fault when getting a field should return EAGAIN rather than EFAULT.
- Add compiler barrier between operations: Adding a compiler barrier between store operations in a cpu_opv sequence can be useful when paired with membarrier system call.

An algorithm with a paired slow path and fast path can use sys_membarrier on the slow path to replace fast-path memory barriers by compiler barrier.

Adding an explicit compiler barrier between operations allows cpu_opv to be used as fallback for operations meant to match the membarrier system call.

Changes since v2:

- Fix memory leak by introducing struct cpu_opv_pinned_pages. Suggested by Boqun Feng.
- Cast argument 1 passed to access_ok from integer to void __user *, fixing sparse warning.

---
 MAINTAINERS                  |   7 +
 include/uapi/linux/cpu_opv.h | 117 ++++++
 init/Kconfig                 |  14 +
 kernel/Makefile              |   1 +
 kernel/cpu_opv.c             | 968 +++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/core.c          |  37 ++
 kernel/sched/sched.h         |   2 +
 kernel/sys_ni.c              |   1 +
 8 files changed, 1147 insertions(+)
 create mode 100644 include/uapi/linux/cpu_opv.h
 create mode 100644 kernel/cpu_opv.c

index c9f95f8b07ed..45a1bbdaa287 100644
@@ -3675,6 +3675,13 @@ B:	https://bugzilla.kernel.org
 F:	drivers/cpuidle/*
 F:	include/linux/cpuidle.h
 
+CPU NON-PREEMPTIBLE OPERATION VECTOR SUPPORT
+M:	Mathieu Desnoyers <mathieu.desnoyers-vg+e7yoeK/dWk0Htik3J/[email protected]>
+L:	[email protected]
+S:	Supported
+F:	kernel/cpu_opv.c
+F:	include/uapi/linux/cpu_opv.h
+
 CRAMFS FILESYSTEM
 W:	http://sourceforge.net/projects/cramfs/
 S:	Orphan / Obsolete

index cbedfb91b40a..e4fbb5dd6a24 100644
@@ -1404,6 +1404,7 @@ config RSEQ
 	bool "Enable rseq() system call" if EXPERT
 	default y
 	depends on HAVE_RSEQ
+	select CPU_OPV
 	select MEMBARRIER
 	help
 	  Enable the restartable sequences system call. It provides a

@@ -1414,6 +1415,19 @@ config RSEQ
 
 	  If unsure, say Y.
 
+config CPU_OPV
+	bool "Enable cpu_opv() system call" if EXPERT
+	default y
+	help
+	  Enable the CPU preempt-off operation vector system call.
+	  It allows user-space to perform a sequence of operations on
+	  per-cpu data with preemption disabled. Useful as
+	  single-stepping fall-back for restartable sequences, and for
+	  performing more complex operations on per-cpu data that would
+	  not be otherwise possible to do with restartable sequences.
+
+	  If unsure, say Y.
+
 config EMBEDDED
 	bool "Embedded system"
 	option allnoconfig_y

index 3574669dafd9..cac8855196ff 100644
@@ -113,6 +113,7 @@ obj-$(CONFIG_TORTURE_TEST) += torture.o
 
 obj-$(CONFIG_HAS_IOMEM) += memremap.o
 obj-$(CONFIG_RSEQ) += rseq.o
+obj-$(CONFIG_CPU_OPV) += cpu_opv.o
 
 $(obj)/configs.o: $(obj)/config_data.h
 

index 6bba05f47e51..e547f93a46c2 100644
@@ -1052,6 +1052,43 @@ void do_set_cpus_allowed(struct task_struct *p, const struct cpumask *new_mask)
 		set_curr_task(rq, p);
 }
 
+int push_task_to_cpu(struct task_struct *p, unsigned int dest_cpu)
+{
+	struct rq_flags rf;
+	struct rq *rq;
+	int ret = 0;
+
+	rq = task_rq_lock(p, &rf);
+	update_rq_clock(rq);
+
+	if (!cpumask_test_cpu(dest_cpu, &p->cpus_allowed)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	if (task_cpu(p) == dest_cpu)
+		goto out;
+
+	if (task_running(rq, p) || p->state == TASK_WAKING) {
+		struct migration_arg arg = { p, dest_cpu };
+		/* Need help from migration thread: drop lock and wait. */
+		task_rq_unlock(rq, p, &rf);
+		stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
+		tlb_migrate_finish(p->mm);
+		return 0;
+	} else if (task_on_rq_queued(p)) {
+		/*
+		 * OK, since we're going to drop the lock immediately
+		 * afterwards anyway.
+		 */
+		rq = move_queued_task(rq, &rf, p, dest_cpu);
+	}
+out:
+	task_rq_unlock(rq, p, &rf);
+
+	return ret;
+}
+
 /*
  * Change a given task's CPU affinity. Migrate the thread to a
  * proper CPU and schedule it away if the CPU it's executing on